David Brown wrote: > On Tue, Jan 08, 2008 at 11:25:18AM -0800, Brad Beyenhof wrote: >> On Jan 8, 2008 11:05 AM, Barry Gershenfeld <[EMAIL PROTECTED]> wrote: >>> real 0m37.930s >>> user 0m0.000s >>> sys 0m0.000s >> [snip] >>> (Okay peanut gallery, this is where you post /your/ time...) >> >> I didn't use any gcc options when compiling, and it's running on my >> Ubuntu 7.10 server (a Linode VPS). I changed my "blank" character in >> the source code to an underscore so I wouldn't have to quote the >> arguments: >> >> $ time ./a.out 2468135_7 12345678_ > sli.txt >> >> real 0m4.711s >> user 0m3.070s >> sys 0m0.190s > > Ok, my turn. The code, in Common Lisp, is attached below. Running this > interactively with SBCL on a 2.4Ghz Intel Core 2 DUO. > > For the given example > > (time (solve '(2 4 6 8 1 3 5 nil 7))) > Evaluation took: > 0.628 seconds of real time > 0.600038 seconds of user run time > 0.028002 seconds of system run time > [Run times include 0.188 seconds GC run time.] > 0 calls to %EVAL > 0 page faults and > 83,066,512 bytes consed. > > I may have to look at the other solutions, since this thing is > significantly faster than either solution posted so far. I didn't try > any > optimization. > > I spent probably 8 hours last night learning enough common lisp (I know > scheme), and then about 5 hours this evening writing this. > > Interestingly, the full space search > > (time (solve '(1 2 3 4 5 6 8 7 nil))) > > is 0.828 seconds. (It doesn't print anything if there is no solution). > It runs quite a bit slower if you print out the boards during the run, or > even time the printing of the solution. I'm not surprised by this at all. Modern LISP implementations are quite efficient, and this is a good problem for LISP. My solution does do a full space search initially, and it does it in about the same amount of time as yours. Mine also uses the Boost Graph stuff which actually slows things down (I'm thinking of a more useful way to use the graph stuff as I refactor the code) with tons of lookups that are slower than just computing what possible moves one can do. > So, any ideas on what I should write next? This was a perfect problem > for > learning this language. Another good one for the language is a CLOS based equivalent to "find".
--Chris -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
