Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #63096 > unrolled thread

Re: [newbie] Recursive algorithm - review

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [newbie] Recursive algorithm - review Chris Angelico <rosuav@gmail.com> - 2014-01-04 13:02 +1100
    Re: [newbie] Recursive algorithm - review Wiktor <look@signature.invalid> - 2014-01-04 12:09 +0100
      Re: [newbie] Recursive algorithm - review Chris Angelico <rosuav@gmail.com> - 2014-01-04 22:18 +1100
        Re: [newbie] Recursive algorithm - review Wiktor <look@signature.invalid> - 2014-01-04 12:53 +0100
        Re: [newbie] Recursive algorithm - review Wiktor <look@signature.invalid> - 2014-01-04 14:01 +0100

#63096 — Re: [newbie] Recursive algorithm - review

On Sat, Jan 4, 2014 at 11:13 AM, Wiktor <look@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

[toc] | [next] | [standalone]

#63127

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

[toc] | [prev] | [next] | [standalone]

#63128

On Sat, Jan 4, 2014 at 10:09 PM, Wiktor <look@signature.invalid> wrote:
> On Sat, 4 Jan 2014 13:02:37 +1100, Chris Angelico wrote:
>> 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.

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.

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

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

[toc] | [prev] | [next] | [standalone]

#63131

On Sat, 4 Jan 2014 22:18:09 +1100, Chris Angelico wrote:

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

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

[toc] | [prev] | [next] | [standalone]

#63132

On Sat, 4 Jan 2014 22:18:09 +1100, Chris Angelico wrote:

>>   Thank you for all Your comments.
> 
> 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. :-)

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web