[newbie] Recursive algorithm - review

[Wiktor]

Hi,
it's my first post on this newsgroup so welcome everyone.

I'm still learning Python (v3.3), and today I had idea to design (my first)
recursive function, that generates board to 'Towers' Puzzle:
http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/towers.html
(so I could in future write algorithm to solve it ;-))

I'm pretty proud of myself - that it works, and that took me only 4 hours
to debug. ;-)
But on Project Euler site sometimes I'm also proud, that I solved some
problem in 30-line script, and then on forum there's one lined solution...

So maybe You might look at this script, and tell me if this can be more
pythonic. It's nothing urgent. I can wait - it works after all. ;-)


Idea is that function "generate()" 'finds' one number at a time (well,
besides first row), then checks if there are no repetitions in column
(because in row there cannot be by design - I pop out numbers from shuffled
list [1, 2, 3, ..., size] for every row.)
If no repetition - calls the same function to find next number, and so on.
If there is repetition at some point - recursion jumps back, and try
different number on previous position.



import random


def check(towers, x=None):
if x:
c = x % len(towers) # check only column with
column = [] # value added on pos. x
for i in range(len(towers)):
column.append(towers[c])
column = [x for x in column if x != 0]
# print(column) # debugging leftovers ;-)
return len(column) == len(set(column))
else:
for c in range(len(towers)): # 'x' not provided,
column = [] # so check all columns
for i in range(len(towers)):
column.append(towers[c])
column = [x for x in column if x != 0]
# print(column)
if len(column) != len(set(column)):
return False
return True


def generate(size=4, towers=None, row=None, x=0):
if not towers: # executed only once.
row = [a for a in range(1, size+1)] # Then I'll pass towers list
random.shuffle(row) # at every recursion
towers = []
# not so pretty way to generate
for i in range(size): # matrix filled with 0's
towers.append([]) # I tried: towers = [[0]*size]*size
for j in range(size): # but this doesn't work. ;-)
towers.append(0) # I don't know how to do this with
# list comprehension (one inside
row_ = row[:] # other?)
towers[0] = row_ # after adding first row, columns will be
row = [] # always unique, so I add entire row at once.
x = size - 1 # Then I will be adding only one num at time.
# 'x' is pretty much position of last added el.
if not row:
row = [a for a in range(1, size+1)]
random.shuffle(row)

if x + 1 < size**2:
repeat = True
attempt = 0
while repeat:
# print(towers, row, x)
x += 1
num = row.pop(0) # take num from right, and
towers[x // size][x % size] = num # if doesn't match - put
repeat = not check(towers, x) # back (append) on left -
# - to rotate
if repeat: # I'll repeat 'matching' next
row.append(num) # number as long as last
x -= 1 # changed column is unique
attempt += 1
# after some attempts I give
if attempt > len(row) - 1: # up and jump back from
return False # current recursion
else:
if not generate(size, towers, row, x):
repeat = True
row.append(num) # after some failed attempts
x -= 1 # on this 'level' I give up
attempt += 1 # again...

if attempt > len(row) - 1:
return False # ...and jump back one
# more time...
return towers


def main():
towers6by6 = generate(6)
# print(check(towers6by6))
print(towers6by6)

if __name__ == "__main__": main()



Footnote: English isn't my native language, so forgive me my bad grammar
and/or vocabulary.

 

[Chris Angelico]

Hi,
it's my first post on this newsgroup so welcome everyone.

Hi! Welcome!

I'm still learning Python (v3.3), and today I had idea to design (my first)
recursive function, that generates board to 'Towers' Puzzle:
http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/towers.html
(so I could in future write algorithm to solve it ;-))

Yep, that's the way to do things. When I wrote some code for a sort of
"binary sudoku" system (they're a lot of fun, btw), I went through
this sequence:

0) Figure out a data structure to hold a board state
1) Write code that will ascertain whether a given board state is valid
2) Write code that will deduce more information from a given board state
3) Write code that will completely solve a board
4) Write code that can "solve" an empty board, thus generating a puzzle.

But on Project Euler site sometimes I'm also proud, that I solved some
problem in 30-line script, and then on forum there's one lined solution...

That's not a problem in itself. In fact, in many situations the
30-liner is better. But mainly, once you get a
working-but-slightly-verbose script, it's fairly straight-forward to
simplify it a little bit at a time.

def check(towers, x=None):
column = [] # value added on pos. x
for i in range(len(towers)):
column.append(towers[c])
column = [x for x in column if x != 0]

Any time you iterate over range(len(something)), you probably want to
iterate over the thing instead:

for t in towers:
column.append(t[c])

And any time you iterate over something and append to another list,
you probably want a list comprehension:

column = [t[c] for t in towers]

And two comprehensions can usually be combined into one:

column = [t[c] for t in towers if t[c] != 0]

That has a little bit of redundancy in there (mentioning t[c] twice),
but I think it's cleaner than having the separate pass. Finally, since
you're working here with integers, you can drop the "!= 0" check and
simply test the truthiness of t[c] itself:

column = [t[c] for t in towers if t[c]]

for c in range(len(towers)): # 'x' not provided,
column = [] # so check all columns

I wouldn't normally wrap a comment onto an unrelated line; I'd put the
comment above the loop, since it's too long to be a part of the loop
header itself. It goes as much with the "else" as with the loop,
anyhow.

This is one case where you probably _do_ want to iterate up to
range(len(towers)), though, which is why I said "probably" above.

for i in range(len(towers)):
column.append(towers[c])
column = [x for x in column if x != 0]

This is the same code you had above, so it can benefit from the same
translation. But maybe it'd be even cleaner to simply call yourself?

if not check(towers, i): return False

# print(column)
if len(column) != len(set(column)):
return False
return True

And in fact, you might want to turn this whole branch into something
that harks to a more functional programming style:

return all((check(towers, i) for i in range(len(towers)))

But that's a stylistic choice.

def generate(size=4, towers=None, row=None, x=0):
if not towers: # executed only once.
row = [a for a in range(1, size+1)] # Then I'll pass towers list

row = list(range(1, size+1))

random.shuffle(row) # at every recursion

Again, I wouldn't wrap comments onto unrelated lines. You see how
confusing this looks, now that I take this line out of context? Same
will happen if it throws an exception.

towers = []
# not so pretty way to generate
for i in range(size): # matrix filled with 0's
towers.append([]) # I tried: towers = [[0]*size]*size
for j in range(size): # but this doesn't work. ;-)
towers.append(0) # I don't know how to do this with
# list comprehension (one inside
row_ = row[:] # other?)
towers[0] = row_ # after adding first row, columns will be
row = [] # always unique, so I add entire row at once.
x = size - 1 # Then I will be adding only one num at time.
# 'x' is pretty much position of last added el.

When you multiply a list of lists, you get references to the same
list, yes. But you could use multiplication for one level:

towers = [[0]*size for _ in range(size)]

That'll give you independent lists. I'm not wholly sure what the rest
of your code is trying to do here, so I can't comment on it.

if not row:
row = [a for a in range(1, size+1)]
random.shuffle(row)

This is the same as you have at the top of 'if not towers'. Can you be
confident that row is None any time towers is None? If so, just move
this up above the other check and save the duplication.

num = row.pop(0) # take num from right, and
towers[x // size][x % size] = num # if doesn't match - put
repeat = not check(towers, x) # back (append) on left -
# - to rotate
if repeat: # I'll repeat 'matching' next
row.append(num) # number as long as last
x -= 1 # changed column is unique

Hmm, I'm slightly confused by your comments here. You pop(0) and
append(), and describe that as taking from the right and putting on
the left. Normally I'd write a list like this:
[20, 30, 40]

And then pop(0) takes the zeroth element:
20

And append() puts that back on at the end:
[30, 40, 20]

So I would describe that as taking from the left and putting on the right.

Footnote: English isn't my native language, so forgive me my bad grammar
and/or vocabulary.

Your English looks fine. Usually, people who apologize for their
non-native English are far more competent with the language than those
whose English is native and sloppy In fact, the effort required to
learn a second language almost certainly means that you're both better
with English and better with Python than you would otherwise be.

ChrisA

 

[Wiktor]

def check(towers, x=None):
column = [] # value added on pos. x
for i in range(len(towers)):
column.append(towers[c])
column = [x for x in column if x != 0]

Any time you iterate over range(len(something)), you probably want to
iterate over the thing instead:

for t in towers:
column.append(t[c])

Right, /facepalm/ I've done it so many times. Don't know why not this time.

And any time you iterate over something and append to another list,
you probably want a list comprehension:

column = [t[c] for t in towers]
[...]
column = [t[c] for t in towers if t[c] != 0]
[...]
column = [t[c] for t in towers if t[c]]
Nice.

for c in range(len(towers)): # 'x' not provided,
column = [] # so check all columns

I wouldn't normally wrap a comment onto an unrelated line; I'd put the
comment above the loop, since it's too long to be a part of the loop
header itself. It goes as much with the "else" as with the loop,
anyhow.

My mistake. I know, that sometimes comment doesn't relate to line that is
next to, but for one second I belived that it would be more readable ('talk'
about the code whitout providing more unnecessary whitespace). Now I see that
it isn't.

This is one case where you probably _do_ want to iterate up to
range(len(towers)), though, which is why I said "probably" above.

for i in range(len(towers)):
column.append(towers[c])
column = [x for x in column if x != 0]

This is the same code you had above, so it can benefit from the same
translation. But maybe it'd be even cleaner to simply call yourself?

if not check(towers, i): return False

You're right. It's cleaner this way.

And in fact, you might want to turn this whole branch into something
that harks to a more functional programming style:

return all((check(towers, i) for i in range(len(towers)))

Great. I didn't know all() before.
Now check() function looks very neat.
Although 'if' statement must now looks like: 'if x is not None:'. Earlier x
never was going to be 0. Now it can be.

Again, I wouldn't wrap comments onto unrelated lines. You see how
confusing this looks, now that I take this line out of context? Same
will happen if it throws an exception.

Yeap. Now I see it. Never gonna do that again.

When you multiply a list of lists, you get references to the same
list, yes. But you could use multiplication for one level:

towers = [[0]*size for _ in range(size)]

That'll give you independent lists.

Got it!

if not row:
row = [a for a in range(1, size+1)]
random.shuffle(row)

This is the same as you have at the top of 'if not towers'. Can you be
confident that row is None any time towers is None? If so, just move
this up above the other check and save the duplication.

row is None at start, but later it is list - sometimes an empty list. For
that cases this if statement was written. If row == [] -> generate new random
row that I can pop out from.

num = row.pop(0) # take num from right, and
towers[x // size][x % size] = num # if doesn't match - put
repeat = not check(towers, x) # back (append) on left -
# - to rotate
if repeat: # I'll repeat 'matching' next
row.append(num) # number as long as last
x -= 1 # changed column is unique

Hmm, I'm slightly confused by your comments here. You pop(0) and
append(), and describe that as taking from the right and putting on
the left. Normally I'd write a list like this:

Of course, of course. I was thinking one, writing another. I switched left
and right in my explanation. It looks stupid now. ;-)

Thank you for all Your comments.

 

[Chris Angelico]

Great. I didn't know all() before.
Now check() function looks very neat.

Sometimes they aren't any help at all (puns intended), but sometimes
any() and all() are exactly what you want.

Although 'if' statement must now looks like: 'if x is not None:'. Earlier x
never was going to be 0. Now it can be.

Nicely spotted, I hadn't thought of that implication.

Yeap. Now I see it. Never gonna do that again.

Please note that I didn't intend this as criticism, or a "this is the
rule so follow it" directive, just as advice I'm not bearing down
on you with a sergeant-major's string of orders, just offering some
tips that you're free to ignore if you like. And in fact, you probably
WILL ignore some of them, at some points, even if you believe them to
be good advice now - every stylistic rule must be secondary to the
overriding rule "Make it work and be readable", and should be broken
if it violates the prime directive.

This is the same as you have at the top of 'if not towers'. Can you be
confident that row is None any time towers is None? If so, just move
this up above the other check and save the duplication.

row is None at start, but later it is list - sometimes an empty list. For
that cases this if statement was written. If row == [] -> generate new random
row that I can pop out from.

Yes, but will you ever pass a non-None row and a None towers? If not,
you can deduplicate that bit of code by simply checking one before the
other.

Thank you for all Your comments.

My pleasure! Always happy to help out.

ChrisA

 

[Wiktor]

This is the same as you have at the top of 'if not towers'. Can you be
confident that row is None any time towers is None? If so, just move
this up above the other check and save the duplication.

row is None at start, but later it is list - sometimes an empty list. For
that cases this if statement was written. If row == [] -> generate new random
row that I can pop out from.

Yes, but will you ever pass a non-None row and a None towers? If not,
you can deduplicate that bit of code by simply checking one before the
other.

Oh, now I understand what You mean.
I rewrote that part.

def generate(size=4, towers=None, row=None, x=0):

if not row:
row = [a for a in range(1, size+1)]
random.shuffle(row)

if not towers:
towers = [[0]*size for _ in range(size)]
towers[0] = row[:]
random.shuffle(row)
x = size - 1

if x + 1 < size**2:
# [...]

Much more cleaner.
Thanks!

 

[Wiktor]

My pleasure! Always happy to help out.

I'm aware, that at my point of education there's no sense in optimizing code
to squeeze from it every millisecond, but Project Euler gave me habit to
compare time consumption of script every time I make serious change in it.

Your tune-ups made this script (mostly check() I guess) about 20% faster. So
it's not only 'more readable' profit.