[Icfp04-discuss] Ant optimizers?

[Finn Wilcox]

On Thu, 10 Jun 2004, Jack Diederich wrote:

> Did anyone write a state optimizer?  I didn't, but I just banged
> one out (50 lines of python, I'm sure someone could write a one-liner
> in perl).  If two lines are the same, anyone that goes to one could
> go to the other instead.  These two are interchangeable:
> 
> line 10:  Sense Ahead 10 15 Food
> ..
> line 99:  Sense Ahead 10 15 Food
> 
> So any place w/ a target of 99 could have a target of 10 instead
> 
> On *nix, to find the _minimum_ number of duplicate states,
> > sort -u name.ant | wc -l
> 
> But once you do that substitution, some more lines are likely identical.
> Rinse and repeat.
> 
> The sample ant goes from 400 states down to 160.
> The fatest ant I've seen (phANTomas-2.ant) goes from 8671 lines down
> to 949,  11% of it's original size.
> 
> Oops, I just checked dunkosmiloolump-1.ant and it reduces by zero,
> so at least one team wrote an ant optimizer (either post optimizer
> or built into their generator).
> 
Yes I did exactly the same.
I also removed redundant sensing, so

9: turn right 10
10: sense ahead 12 12 food

becomes

9: turn right 12

you can get these redundant senses as a result of removing duplicates.