Hi all,
since the 3.18.1 release, there has been many improvements and cleanups on the
fc-solve trunk. It all started when I did some random, minor, cleanups of
adding "const" (see
http://en.wikipedia.org/wiki/Constant_%28programming%29 )
annotations to variables, and avoiding predeclarations at the top. Then, after
refactoring the prelude compilation function to avoid it destroying the
input string, I discovered a bug where the prelude compilation was called
several times and fixed it.
I also noticed a case where I kept dereferencing a pointer
("ptr_state_kv->key") instead of using it directly in a variable, and remedied
it.
My big breakthrough however came after I decided to take a look at the Simple
Simon code in simpsim.c and refactor it. This code was pretty old and suffered
from a lot of neglect as I was focusing on Freecell. I started adding const,
and avoiding pre-declarations and converting long if's to «if (!COND())
{ continue; }», and then noticed that:
1. The file had a lot of duplicate code.
2. There were many searches for Simple Simon true parents (i.e: cards that
are higher by one in rank and of the same suit) across the entire card set in
the board (~52 cards) where it could find it in O(1) using a reverse lookup,
which had been implemented for Freecell.
So I went to first avoid a lot of the duplicate code by extracting functions
and C macros, and then went to implement the more efficient searches and
lookups.
The latter proved fruitful as the results of the brute (including overhead)
runtime of a range of Simple Simon deals proved:
[SHELL]
shlomif_at_telaviv1:~/Arcs$ perl -0777 -nalE 'my _at_matches = map
{ s/^T=//r; } /(T=[^\n]+)/g; say $matches[-1]-$matches[0]' fc-solve-Simple-Simon--old-dump.txt
169.769564390182
shlomif_at_telaviv1:~/Arcs$ perl -0777 -nalE 'my _at_matches = map
{ s/^T=//r; } /(T=[^\n]+)/g; say $matches[-1]-$matches[0]' fc-solve-Simple-Simon--new-dump.txt
94.3558139801025
shlomif_at_telaviv1:~/Arcs$ improvement-percent from 169.769564390182 to
94.3558139801025
79.9248580760297%
shlomif_at_telaviv1:~/Arcs$
[/SHELL]
So an improvement of roughly 80% and like I said - it is an improvement to the
brute run - the Net improvement is likely even better. In the course, several
bugs were fixed and some of the solutions changed.
Cheers, all.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Stop Using MSIE - http://www.shlomifish.org/no-ie/
Vizzini: He didn’t fall?! Inconceivable!
Inigo Montoya: You keep using that word. I do not think it means what you
think it means.
— http://en.wikiquote.org/wiki/The_Princess_Bride_%28film%29
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Sun Jun 23 2013 - 05:07:29 IDT