begin quoting David Brown as of Thu, Jan 10, 2008 at 10:23:26PM -0800:
> On Tue, Jan 08, 2008 at 11:25:18AM -0800, Brad Beyenhof wrote:
[chop]
> 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.
Equivalent features would be nice as well. Something that takes
two strings from the command line and prints out the result in an
easy-for-a-human-to-verify way would be very desirable.
Plus, we could all then time it the same way, using the same "time"
program, giving comparable results.
[snip]
> To be honest, I'm completely surprised by these results. I give this
> language and at least this implementation a lot of credit.
$ time ./a.out '12345678 ' '54321 867' > /dev/null
1.23u 0.05s 0:01.30 98.4%
$ time clisp puzzle
Real time: 36.646008 sec.
Run time: 36.644794 sec.
Space: 41246096 Bytes
GC: 37, GC time: 1.269448 sec.
36.41u 0.28s 0:36.71 99.9%
$
I'm thinking it's the implementation. :)
> So, any ideas on what I should write next? This was a perfect problem for
> learning this language.
Finding a good problem is a wonderful thing.
A suduko solver seems like a good fit for a lispy language. :)
Lemme check my assumptions...
> ----------------------------------------------------------------------
> ;;; Brute-force solution to the 9-square (or 15-square or whatever)
> ;;; problem.
>
[snip]
> ;; A given board is represented as a simple vector with the squares
> ;; given as integers starting at 1. The empty square has the value
> ;; NIL.
>
> (defconstant solved-board
> (let ((nums (loop for i from 1 to full-size
> collect (and (< i full-size) i))))
> (make-array full-size :initial-contents nums))
> "The final solved board")
You don't take arbitrary strings, you take numbers, and the solutions
is always (1 2 3 4 5 6 7 8 nil) for a 3x3 board, yes?
[snip]
> ;; Given a particular board, compute a unique bignum defining the
> ;; possible position. Treats the empty space as value full-size, and
> ;; simply computes the number base (1+ full-size).
> (defun compute-cookie (board)
> (loop for item across board
> for power = 1 then (* power 10)
> sum (* power (or item full-size))))
At first I thought it was the guaranteed way to encode any number
sequence using powers and primes...
The loop with two fors is kind of odd; I think I see what it's doing.
My psuedocode interpretation of the above:
bignum compute-cookie( board ) {
sum = 0
power = 1
foreach item in board {
if ( item is nil ) {
sum = sum + (power * size(board))
} else {
sum = sum + (power * item)
}
power = power * 10
}
return sum
}
Close?
Also, it seems like there's going to be a potential problem when the board
size is > 3x3, as then you'll have items that are bigger than your power
increment.
[chop]
--
It takes a long time in lisp for me to think
Activation energy to get my brain to the brink.
Stewart Stremler
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
