My brother gave me a wood puzzle for xmas. I've implemented it in Flash:
http://www.frank-buss.de/trisoli/index.html
and wrote a Lisp solver for it:
http://www.frank-buss.de/trisoli/trisoli.lisp.txt
Maybe you want to write your own solver (but beating the speed would be
difficult, because it solves already many targets in less than a second),
implement the game with an ASCII or GUI interface in Lisp or just having
fun with the game.
BTW: the more I use "loop", the more I like it :-)
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
One comment on your flash interface. I would set it up so that you
can make a move by clicking on an edge, rather than (or in addition
to) clicking on the source shell then the destination. It's still
unambiguous, but it's simpler --- only a single click to determine the
move.
Cheers,
rif
In article <······························@40tude.net>,
Frank Buss <··@frank-buss.de> wrote:
> My brother gave me a wood puzzle for xmas. I've implemented it in Flash:
>
> http://www.frank-buss.de/trisoli/index.html
>
> and wrote a Lisp solver for it:
>
> http://www.frank-buss.de/trisoli/trisoli.lisp.txt
>
> Maybe you want to write your own solver (but beating the speed would be
> difficult, because it solves already many targets in less than a second),
> implement the game with an ASCII or GUI interface in Lisp or just having
> fun with the game.
Hmm. When I tried running (find-path), I got:
path length: 37, path: 02-12 11-02 00-10 02-11 01-02 11-00 02-11 00-01
12-02 01-00 22-12 00-01 11-22 01-00 02-11 00-01 10-00 01-02 20-10 02-01
21-20 01-02 22-21 02-01 11-22 01-02 00-11 02-01 10-00 01-02 20-10 02-01
11-20 01-02 00-01 02-11 12-02
which when plugged into your flash program didn't solve it. It almost
did, but left a blue piece in 10 instead of 00. This is the same place
I get stuck when I try to solve it by hand. :-)
-bcd
Brian Downing wrote:
> which when plugged into your flash program didn't solve it. It almost
> did, but left a blue piece in 10 instead of 00. This is the same place
> I get stuck when I try to solve it by hand. :-)
This is the xmas suprise: I forgot to mention that the goal, like written
on the page (and written in the manual of the original game, too) is not
reachable :-) See http://tinyurl.com/bxykt (sorry, in German) for a
mathematical prove.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> My brother gave me a wood puzzle for xmas. I've implemented it in Flash:
>
> http://www.frank-buss.de/trisoli/index.html
>
> and wrote a Lisp solver for it:
>
> http://www.frank-buss.de/trisoli/trisoli.lisp.txt
>
> Maybe you want to write your own solver (but beating the speed would be
> difficult, because it solves already many targets in less than a second),
> implement the game with an ASCII or GUI interface in Lisp or just having
> fun with the game.
>
> BTW: the more I use "loop", the more I like it :-)
That's the problem with programmers like us: you can't give them game
and have them just play with it, they have to write a program to make
the computer play for them! :-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Frank Buss <··@frank-buss.de> writes:
> My brother gave me a wood puzzle for xmas. I've implemented it in Flash:
>
> http://www.frank-buss.de/trisoli/index.html
>
> and wrote a Lisp solver for it:
>
> http://www.frank-buss.de/trisoli/trisoli.lisp.txt
I solved it in my language Kogut before seeing your code (after seeing
the information that it's insolvable, but it didn't change the way I
would solve that).
The program proves that there is no solution of the original puzzle,
or finds the shortest solution for the target configuration with 00
and 10 swapped, in 0.2s on my machine (Athlon 2000).
It's at http://qrnik.knm.org.pl/~qrczak/tmp/Trisoli.ko
It was written for clarity, not for speed. I will be able to compare
it for speed with Lisp if I get instructions about compiling it with
SBCL with relevant optimizations; I don't use SBCL dailly.
Now I will look at your solution.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> Now I will look at your solution.
It's essentially the same algorithm.
I encode the state by a vector of length 9, while you by an array of
shape 3�3; I encode colors by symbols, while you by integers 0..3;
I map the state to a list of symbols in order to look it up in a set
(lists in Kogut are immutable and compared and hashed by value), while
you map it to an integer and mark a bit in a bit vector; I store the
list of neighboring pairs, while you store lists of directions to
neighbors from each place.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk wrote:
> It's essentially the same algorithm.
yes, it's both a breadth-first-search (BFS), but your solution is shorter
and more functional programming style with some interesting mapping
contructs.
BTW: I've spent one hour yesterday for a depth-first-search, until I
realized that it is too slow, then another one to rewrite it to a BFS and a
last hour trying to find a bug in the program, because it didn't found a
solution for the impossible target board setup :-)
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
<······@knm.org.pl> wrote:
> The program proves that there is no solution of the original puzzle,
> or finds the shortest solution for the target configuration with 00
> and 10 swapped, in 0.2s on my machine (Athlon 2000).
>
> It's at http://qrnik.knm.org.pl/~qrczak/tmp/Trisoli.ko
>
> It was written for clarity, not for speed. I will be able to compare
> it for speed with Lisp if I get instructions about compiling it with
> SBCL with relevant optimizations; I don't use SBCL dailly.
The version at <http://www.cs.helsinki.fi/u/jesnellm/tmp/trisoli.lisp>
fixes the most serious performance problems of the original Lisp code
(from SBCLs point of view; maybe the original performed well on some
other CL implementation). It solves the problem 100 times in 0.9
seconds on an Athlon 64 X2 vs 29 seconds for the original. To run,
just do:
sbcl --userinit trisoli.lisp --eval '(time (dotimes (i 100) (find-path)))'
--
Juho Snellman
If I do
sbcl --userinit trisoli.lisp --eval '(time (dotimes (i 100)
(find-path)))'
at the console I get:
Evaluation took:
4.742 seconds of real time
0.932858 seconds of user run time
0.182972 seconds of system run time
0 page faults and
125,728,712 bytes consed.
If I load trisoli.lisp into Emacs+Slime+sbcl on my P4 2800 and do
(time (dotimes (i 100) (find-path)))
I get:
Evaluation took:
1.331 seconds of real time
0.909861 seconds of user run time
0.183972 seconds of system run time
0 page faults and
125,729,184 bytes consed.
<·····························@justmail.de> wrote:
[ console ]
> 4.742 seconds of real time
> 0.932858 seconds of user run time
> 0.182972 seconds of system run time
[ slime ]
> 1.331 seconds of real time
> 0.909861 seconds of user run time
> 0.183972 seconds of system run time
The user+system time is practically the same for these two runs. Real
time shouldn't be used for benchmarking since it's also affected by
the other processes running on the system.
That said, a 3-4x difference in real time is quite a lot. Maybe you're
using a xterm clone with antialiased fonts, which tends to grind a
computer to its knees when displaying even moderate amounts of text?
In that case redirecting the output to a file will probably cut down
the real time of the non-slime run.
--
Juho Snellman
Juho Snellman <······@iki.fi> writes:
> The version at <http://www.cs.helsinki.fi/u/jesnellm/tmp/trisoli.lisp>
> fixes the most serious performance problems of the original Lisp code
> (from SBCLs point of view; maybe the original performed well on some
> other CL implementation). It solves the problem 100 times in 0.9
> seconds on an Athlon 64 X2 vs 29 seconds for the original. To run,
> just do:
>
> sbcl --userinit trisoli.lisp --eval '(time (dotimes (i 100) (find-path)))'
It runs in 7.9s for me (as reported by SBCL time, i.e. excluding
compilation). My solution runs in 12.5s.
SBCL still displays warnings about lost possibilities of optimization.
I tried to change my solution to encode balls as numbers 0..3 instead
of symbols, which enables encoding states as numbers instead of lists
for the purpose of putting in a set (which is still a HashSet though),
but it got faster only to 11.4s. I checked that it actually allocates
more memory instead of less (624MB instead of 452MB; SBCL does 120MB),
and realized that this is because my implementation of Fold is not
specialized for vectors and uses a general iteration protocol which
allocates temporary memory.
So I improved the library of my language, which can be considered
cheating at this stage, by adding a specialization of Fold and IsEqual
for vectors. The program now runs in 10.7s and allocates 352MB.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
<······@knm.org.pl> wrote:
> Juho Snellman <······@iki.fi> writes:
>> other CL implementation). It solves the problem 100 times in 0.9
>> seconds on an Athlon 64 X2 vs 29 seconds for the original. To run,
>> just do:
>>
>> sbcl --userinit trisoli.lisp --eval '(time (dotimes (i 100) (find-path)))'
>
> It runs in 7.9s for me (as reported by SBCL time, i.e. excluding
> compilation). My solution runs in 12.5s.
Hmm... I wonder where the factor of 10 difference between my SBCL
result and yours is coming from (presumably your timings are on the
Athlon XP 2000+ you mentioned before?). FWIW a 2400 MHz Pentium 4 with
an ancient version of SBCL still only takes 1.5 seconds.
> SBCL still displays warnings about lost possibilities of optimization.
Sure. Like I said, I just fixed the most serious problems.
--
Juho Snellman
Juho Snellman <······@iki.fi> writes:
>> It runs in 7.9s for me (as reported by SBCL time, i.e. excluding
>> compilation). My solution runs in 12.5s.
>
> Hmm... I wonder where the factor of 10 difference between my SBCL
> result and yours is coming from (presumably your timings are on the
> Athlon XP 2000+ you mentioned before?). FWIW a 2400 MHz Pentium 4
> with an ancient version of SBCL still only takes 1.5 seconds.
It's not a factor of 10 but 5. This Athlon has only 1250 MHz,
and it's not Athlon XP I think.
I don't know much about differences between x86 processors. I know
that AMD calls its processors by numbers which are higher than the
MHz clock, as "our processors are faster than Intel processors with
the same clock". Perhaps this processor could be clocked higher.
Perhaps the speed of memory matters more than the processor speed.
This program allocates much but doesn't keep much memoey alive.
My solution allocates 352MB in total, but only up to 0.287MB is alive
at one time (sampled at 17 major GCs), and only 78MB in total is moved
by the GC (I have two generations and both are copied). The GC takes
up 25% of the time. I don't know how to obtain such statistics for SBCL.
This is sbcl-0.9.0.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
<······@knm.org.pl> wrote:
> Juho Snellman <······@iki.fi> writes:
>> Hmm... I wonder where the factor of 10 difference between my SBCL
>> result and yours is coming from (presumably your timings are on the
>> Athlon XP 2000+ you mentioned before?). FWIW a 2400 MHz Pentium 4
>> with an ancient version of SBCL still only takes 1.5 seconds.
>
> It's not a factor of 10 but 5.
The factor of 10 was from the 0.9s on the Athlon X2 vs your result of
7.9s. The Pentium 4 result was just another data point to show that
the X2 result wasn't an outlier.
> This Athlon has only 1250 MHz, and it's not Athlon XP I think.
Ok, maybe that's old enough to explain the performance difference.
Though I don't quite understand why you called that an "Athlon 2000"
in your first message to this thread.
--
Juho Snellman