I'm trying to solve the 9-tile puzzle using as functional an approach
as possible. I've recently finished reading SICP and am deliberately
avoiding easy python-isms for the more convoluted scheme/functional
methods. The following function is trivial to do with for loops and
directly accessing arrays with [] syntax. I'm trying to limit myself
to the types of idioms/semantics one finds in minimal scheme, such as
in SICP. I want eventually to port this to scheme, but I know python
better, so that's where I'm starting.
My current problem is the following. The 9-tile puzzle consists of a
list of lists like this [[1,2,3],[4,5,6],[7,8,0]], where the numbers
can be jumbled up. I'm looking for the location of the zero using
*only* recursion and operators that are similar to car/cdr. The
return value should be the row,col of the zero. For example above the
return value would be (2,2).
I'm also trying to define a single "linear_search(...)" function which
does the search for within the row (an inner list above) and within
the whole list. linear_search takes as an argument a "truth_function"
which does the actual work. What's tricky is that the truth function
for the array-as-a-whole is also the linear_search for a row. Once
I'm in linear_search for the array, I also call linear_search for each
row.
The problem is the line where it says acc.insert(0,idx) looks fishy to
me. It works fine and returns the row,col of the location of the zero
tile, but it seems to be mutating a variable, and that's the thing I'm
trying to avoid. In a sense, it's not hard enough and python is
making this too easy :) (although it took a bit of mind-wrenching to
get to this point. Recursion makes you either dumber or smarter, I'm
not sure which).
How do I accumulate the inner value of the search so it pops out at
the end, without resorting to a mutable variable? I did a bit of
search and the word "monad" came up, but I'm not sure what that is (I
know it relates to haskell and some other purely functional stuff, but
I get very lost when trying to read that stuff).
def linear_search(array, truth_func, acc):
# Goes through each element of array and applies truth_func.
# Returns index if found, otherwise returns None
def linear_search_iter(idx, truth_func, arr, acc):
if arr:
tf = truth_func(arr[0])
if tf or type(tf) is int:
acc.insert(0,idx)
return idx, acc+[idx]
else:
return linear_search_iter(idx+1, truth_func,
arr[1:], acc)
return linear_search_iter(0, truth_func, array, acc)
def locate_zero(p):
# Locates empty tile. Returns (r,c) tuple
def find_zero_in_row(row):
return linear_search(row, lambda x: x==0, acc)
acc = []
ls = linear_search(p, find_zero_in_row, acc)
print acc
return acc
locate_zero(def linear_search(array, truth_func, acc):
# Goes through each element of array and applies truth_func.
# Returns index if found, otherwise returns None
def linear_search_iter(idx, truth_func, arr, acc):
if arr:
tf = truth_func(arr[0])
if tf or type(tf) is int:
acc.insert(0,idx)
return idx, acc+[idx]
else:
return linear_search_iter(idx+1, truth_func,
arr[1:], acc)
return linear_search_iter(0, truth_func, array, acc)
def locate_zero(p):
# Locates empty tile. Returns (r,c) tuple
def find_zero_in_row(row):
return linear_search(row, lambda x: x==0, acc)
acc = []
ls = linear_search(p, find_zero_in_row, acc)
print acc
return acc
locate_zero([[5, 3, 4], [2, 0, 1], [8, 6, 7]])
returns the correct value of [1,1].
Any suggestions please?
thanks
Michael
--
http://mail.python.org/mailman/listinfo/python-list
