[newbie] Recursive algorithm - review

[Wiktor]

On Sat, 4 Jan 2014 13:02:37 +1100, Chris Angelico wrote:

>> 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])

  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[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

  You're right. It's cleaner this way.
 
>>             # 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)))

  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.
 
>>         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.

  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.

-- 
Best regards,     Wiktor Matuszewski
'py{}@wu{}em.pl'.format('wkm', 'ka') # email spam trap