On Sat, Jan 12, 2008 at 01:07:23PM -0800, SJS wrote:
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.
The results I gave were equivalent to that. In lisp, you generally use the
lisp interpreter as your shell and give your expressions there to evaluate.
I haven't even figured out yet how to make a standalone program (I did a
hello world), or parse arguments and such.
Lisp's time uses the same system call to get the time as time, so I would
expect the same results.
A suduko solver seems like a good fit for a lispy language. :)
I've already moved on to directory parsing and tree walking...
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?
Yes. But, solved-board wouldn't have to be a constant.
[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...
It would be, except for some strange bugs. It should be:
(defun compute-cookie (board)
(loop for item across board
for power = 1 then (* power full-size)
sum (* power (or item 0))))
The power needs to increase by the full-size, and the empty square counts
as zero. My old one works on the 3x3 board because the power is 1 too big,
so the empty square being 1 too big didn't hurt anything either. I put the
10 in there temporarily so I could see the result nicely in base-10, and
forgot to take it out.
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?
Looks right, well at least in this case. A 'for' clause in the loop
describes what the variable does for each iteration through the loop.
'across' iterates through something, and also terminates the loop when the
sequence ends. A expr then expr2 evalues expr the first time, and then
expr2 each time after that.
You can also just use 'for name = expr' to compute something each
iteration.
I actually like LOOP in lisp. The following (using sbcl's posix library)
uses the posix opendir/readdir/closedir to read all of the names in a
directory.
(defun fake-dir-p (name)
(or (string-equal name ".")
(string-equal name "..")))
(defun list-directory (path)
(let ((dir (sb-posix:opendir path)))
(unwind-protect
(sort (loop for dirent = (sb-posix:readdir dir)
until (sb-alien:null-alien dirent)
for name = (sb-posix:dirent-name dirent)
while (stringp name)
unless (fake-dir-p name) collect name)
#'string<)
(sb-posix:closedir dir))))
It nicely handles the two different exit conditions (the dirent can either
be null, or the string inside of it invalid). It also handles the
conditional collection (to skip "." and ".."). Later in the code I collect
files and directories separately.
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.
Yes, that's a bug. The 10 was just for debugging, and I forgot it.
Although there are far bigger problems with larger boards, such as utterly
rediculous amounts of memory needed.
For larger puzzles, a smarter algorithm is definitely needed. There are
actually fairly simple algorithms to always solve the puzzle, but they
won't necessarily have the smallest number of moves.
Dave
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
