On Sat, 06 Dec 2008 23:33:35 -0800, 5lvqbwl02 wrote:
> 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([[5, 3, 4], [2, 0, 1], [8, 6, 7]]) correctly returns (1,1)
In most functional languages, their natural data types differs. For
example, Haskell's list is a linked list, which if expressed in python
would look like this:
Python: [1, 2, 3, 4, 5]
Haskell-in-Python: [1, [2, [3, [4, [5, []]]]]]
linked list is more natural to use with recursive functions, so your
locate zero would be like this:
def search_tile(row, depth = 0):
head, tail = row
if head == 0:
return depth
elif len(tail) == 0:
return None
else:
return search_tile(tail, depth + 1)
def search_row(grid, depth = 0):
head, tail = grid
st = search_tile(head)
if st is not None:
return depth, st
elif tail == []:
return None
else:
return search_row(tail, depth + 1)
Now, you noticed that lots of the code is similar, we want to generalize
it. It's easy:
def search_linear(list_, checker, depth = 0):
head, tail = list_
if checker(head):
return depth, () if checker(head) is True else checker(head)
# I intentionally doesn't factor out checker(head)
# as most functional language would automatically
# do so because side-effect is impossible
elif tail == ():
return ()
else:
return search_linear(tail, checker, depth + 1)
data = (1, (2, (3, (0, ()))))
print search_linear(data, lambda x: x == 0)
# (3, ())
data = (0, (2, (3, (4, ()))))
print search_linear(data, lambda x: x == 0)
#(0, ())
data = (1, (2, (3, (4, ()))))
print search_linear(data, lambda x: x == 0)
#()
data = ((5, (3, (4, ()))), ((2, (0, (1, ()))), ((8, (6, (7, ()))), ())))
print search_linear(data, lambda row: search_linear(row, lambda tile:
tile == 0))
#(1, (1, ()))
--
http://mail.python.org/mailman/listinfo/python-list
