[newbie] Recursive algorithm - review

[Chris Angelico]

On Sat, Jan 4, 2014 at 11:13 AM, Wiktor <look at signature.invalid> wrote:
> 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[i][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[i][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[i].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:

>>> a
[20, 30, 40]

And then pop(0) takes the zeroth element:

>>> a.pop(0)
20

And append() puts that back on at the end:

>>> a.append(_)
>>> a
[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