Wednesday, August 22, 2007

HSS: Generating moves

I've added some functions to generate all possible moves at a given board position for Haskell Spider Solitare (link to source code at right as usual). Here's the relavant bits:

--
-- generate list of all cards that could possibly be moved
--
movable [] _ _ = []
movable (x:xs) col row = if (c_cluster x) == 0
then cur_nsm : movable xs col (row + 1)
else []
where
cur_nsm = Normal_Spider_Move (Tableau_Location col row)
(-1) -- not valid yet.
Nothing
(row + 1)

all_movable sg = am_helper (tableau sg) 0
where
am_helper [] _ = []
am_helper (x:xs) col = (movable x col 0) ++ am_helper xs (col + 1)

--
-- see where they can move to
--
where_plays sg nsm = wp_helper nsm (tableau sg) 0
where
wp_helper _ [] _ = []
wp_helper nsm@(Normal_Spider_Move from to _ _)
(cur_col:rest_cols)
colnum =
(if ((t_col from) == colnum) ||
(length cur_col) > 0 &&
not (plays_on_match (from_card sg nsm) (head cur_col))
then []
else [nsm{sm_to = colnum}] ) ++ rest
where
rest = wp_helper nsm rest_cols (colnum + 1)

where_plays_all nsm_list sg =
foldr (++) [] (map (where_plays sg) nsm_list)
Comments: I need to settle down with the indentation, and pick either 4 or 8 and stick with it. I am at least trying to stick with 80 columns, which makes blog posting easier too.

I'm not complely happy with the tableau data structure, which is just a list of lists of cards. See how I'm threading through the column number in movable and where_plays? I suppose I could replace that with something like: '9 - (length xs)', but that bothers me a little bit too. The whole integer indexes into lists bothered me a bit with the Common Lisp version too. Not that I'd know how I could change it.

As always, any comments on style, or suggestions to make the code shorter and more clear are welcome.

Next task is to decide how to represent the entire tree of moves. I've just downloaded Purely Functional Data Structures[PDF] by Chris Okasaki, but I haven't dug into that yet. We will want to be able to move up and down through the tree easily.

1 comment:

Porges said...

"We will want to be able to move up and down through the tree easily."

This screams zipper :)
The Haskell wikibook has the best description I've come across: http://en.wikibooks.org/wiki/Haskell/Zippers

"pick either 4 or 8"

4 please, I'm already having trouble reading this in Google's Reader :)