Brain going crazy with recursive functions

[5lvqbwl02]

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

 

[James Stroud]

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

thanks
Michael

I am honestly getting lost in your code. The following fulfills your
requirements as far as I can tell. It uses None as a sentinel for the
truth function matching no elements of the array. Some assignments are
made within the code simply to make it more readable. They are not
necessary. The first element that the truth function evaluates to True
is returned.

I hope it helps.

James

def linear_search(array, truth_func, loc=(0,0)):
idx1, idx2 = loc
if idx1 >= len(array):
return None
if idx2 >= len(array[idx1]):
return linear_search(array, truth_func, (idx1+1, 0))
value = array[idx1][idx2]
tf = truth_func(value)
if tf:
return loc
else:
return linear_search(array, truth_func, (idx1, idx2+1))

a = [[5, 3, 4], [2, 0, 1], [8, 6, 7]]
linear_search(a, lambda x: x==0)

 

[James Stroud]

def linear_search(array, truth_func, loc=(0,0)):
idx1, idx2 = loc
if idx1 >= len(array):
return None
if idx2 >= len(array[idx1]):
return linear_search(array, truth_func, (idx1+1, 0))
value = array[idx1][idx2]
tf = truth_func(value)
if tf:
return loc
else:
return linear_search(array, truth_func, (idx1, idx2+1))

a = [[5, 3, 4], [2, 0, 1], [8, 6, 7]]
linear_search(a, lambda x: x==0)

PS: If I just made it to easy for you, you can practice by generalizing
this to an N-dimensional array using recursion. I'm tempted to do it
myself but I'm going to try to resist instead and do some work that pays.