Setting out to learn Python. Anyone wanna join?

Yeah, unused variables are intended to be entered as dummy_... for the machine grader. I like to piss it off though and refuse to cater to its mechanical needs.

LiquidMantis wrote:

Oh, I'm also curious how you guys initiate your scores list of lists, which is related to this question. I don't particularly love my version.

I wound up with this:

scores = [0] * board.get_dim() scores = [[row, row, row] for row in scores]

I should mention I got penalized -4 for a list index out of range somewhere though. Don't think it's related but thought I should mention.

As far as the rest of it is concerned . . . it would be helpful if you didn't answer your own questions less than an hour after you post them.

I actually just finished the tic tac toe project yesterday . . . RL interfering and whatnot but I actually wound up not using any more functions than what they had defined. I started writing others but ended up deleting them as they were unneeded.

Yeah, I was single-handedly keeping the thread alive today.

The problem with your code is it only works for a 3x3 grid. If it's size 4 you'll end up with 4 rows of 3 columns.
This looks like it works for any size though and neatly avoids aliasing issues somehow:

size = board.get_dim() scores = [0] * size scores = [[row] * size for row in scores]

I played around with different methods of initializing score but I kept getting tied up in alias issues rather than copying lists and I don't know why. I've built a multidimensional array before this way but today I kept getting tripped up. Rather than wasting more time on that when I had other issues to solve I just ended up with this:

def build_scores(): """ Creates list of lists for scores """ board_size = board.get_dim() scores = [] for _row in range(board_size): scores.append(board_size * [0]) return scores

Obviously I'm not good with list comprehensions or lambdas still.

Oh, I'm also curious how you guys initiate your scores list of lists, which is related to this question. I don't particularly love my version.

Having found out about 'dummy' variables when I ran into the issue a week or two ago (thanks, Boogle!), this is the code I used to create the nested score list for Tic Tac Toe:

scores = [[0 for dummyrow in range(dimension)] for dummycol in range(dimension)]

I love list comprehensions. That's a really, really nice Python feature.

This week's project was coming along nicely, I had it working pretty well, and then Chromium crashed on me, and I lost a ton of work. I'd fixed a bunch of bugs since my last save, and I couldn't remember everything I fixed, so between that and the loss of a bunch of new code I'd written, I couldn't get the program working properly again the way it had an hour before.

I was tired and frustrated, so I packed it in, and I'll probably pick it up again tomorrow. Maybe I'll just start again from scratch.... it's not a very long program.

Malor wrote:

This week's project was coming along nicely, I had it working pretty well, and then Chromium crashed on me, and I lost a ton of work.

I had a minor "OH sh*t!" moment today that reminded me why I hate working in CodeSkulptor. I was juggling tabs between my program, the description, and the doc for the included class and functions when I accidently hit back on my program and reverted to the last save. It could have been much, much worse than it was but it still was a serious wake-up call.

I kept getting tied up in alias issues rather than copying lists

Yeah, I have that happen all the time. The way I often get around it is with the list() command, that is:

>>> a = [1,2,3,4,5] >>> b = list(a) >>> a is b False

That seems to guarantee the construction of a new copy of the list.

In some old Python notes I took when first learning the language, I wrote down another way that should work: to take a slice of the first list that happens to be the whole list. This is the actual note I wrote for my future self, back in 2007:

To actually copy a list, do b = a[:]... you will get back separate values, and a is b will be false.

edit to add:

when I accidently hit back on my program and reverted to the last save.

Oh, yeah! I had that happen in my first week in the new course. Lost about an hour. Ooh, I was steamed at myself.

Malor wrote:

Yeah, I have that happen all the time. The way I often get around it is with the list() command, that is:

>>> a = [1,2,3,4,5] >>> b = list(a) >>> a is b False

That seems to guarantee the construction of a new copy of the list.

In some old Python notes I took when first learning the language, I wrote down another way that should work: to take a slice of the first list that happens to be the whole list. This is the actual note I wrote for my future self, back in 2007:

To actually copy a list, do b = a[:]... you will get back separate values, and a is b will be false.

I was doing that! Let me see if I can find the code I was working with. Here we go:

board_size = board.get_dim() scores = board_size * [liist(board_size * [0])]

That still is three aliases to the same single list. I played with a few variants but I was just too brain-fried to suss it out and just went to the fallback.

[Edit] Weird, the forum hides the list function even though it's in code tags. Changed to 'liist'.

[Edit2] Okay, I think I'm starting to see the problem there. Those n rows may not equal the original 'board_size * [0]' but they all point to the same output of list(board_size * [0]).

Yeah, I'm seeing the same thing, where the list comprehension builds it correctly. This code seems to work okay, although I may have my rows and my cols backward:

board_size = 3 scores = [] col = [0] * board_size for row in range(board_size): scores.append(list(col))

and instead of list(col), you can also use col[:]. But if you try to multiply the list directly, by saying scores = col * board_size, you get three more aliases pointed at col. And if you multiply the result of list(col), you get a new list, with three aliases. It does break the link with col, but the results are all aliases amongst themselves.

It looks like Python makes one new list per call to list or [:], and multiplies make aliases, so you have to actually execute the line multiple times, instead.

Maybe the list comprehension works because it's really just pretty syntax around nested for loops??

LiquidMantis wrote:

The problem with your code is it only works for a 3x3 grid. If it's size 4 you'll end up with 4 rows of 3 columns.

Ooh, you're right. Maybe that's where my out of range came from. Nice solution though.

Malor wrote:

Maybe the list comprehension works because it's really just pretty syntax around nested for loops??

That's my understanding of what it does. I actually usually write the nested loops first before simplifying to list comp as my brain understands it better that way. Could be wrong though. There's also the copy module that might be worth looking at for aliasing.

Yeah, after thinking about it some more, I believe that is indeed why it works with the comprehension.

I believe this code:

scores = [[0 for dummyrow in range(dimension)] for dummycol in range(dimension)]

produces the same result as this code, sans the leftover 'col' alias to the last row in scores:

scores = [] for dummyrow in range(dimension): col = [] for dummycol in range(dimension): col.append[0] scores.append(col)

Also, I think I lifted that comprehension from the provided class for the assignment. If I had actually written it, I'd probably have used dummy_col and dummy_row. I don't remember copying it, but that naming isn't something I'd do, so I must have.

I'm not sure if it was there before, or if it's been added, but I'm realizing that the requirements for this week are written in a way I'm not sure I understand.

I see no way to do subscripts, so here's a screenshot:

IMAGE(http://www.malor.com/gamerswithjobs/principles_week_3.png)

I'm reading that as 'the results have to be sorted, low value first'. Is that accurate?

Funny you should post that, as for this project I've recently started rewording everything they write in the instructions as I found I spent half my time trying to understand what they were asking multiple times as I went back to reference them. I've only implemented score so far this week (seem to always be a few days behind) but here are my notes from parsing that paragraph, first sentence somewhat technical, second in natural language:

Takes (hand) and returns all (hand - subset) sequences in low - high order.

If I get rid of dice, what combinations are possible with what's left? If everything's different (ie. 1, 2, 3, 4, 5) just generate all hand - subset sequences.

Again no idea if I'm right, but I find that hammering my head against my own reworded idea of what's being asked at least helps me better understand where I might be going wrong if I hit a wall and need to go back to the actual instructions (or heaven forbid, their horrible math pages -- just google their topics on mathisfun.com). In any case it's better trying to implement my own understanding than implementing the wrong thing because they're so bad at explaining things that are actually quite simple.

ugh, I got as far as score() before hitting a brick wall and I needed an English to English translation from the forum for that one too.

f*ck these people and their f*cking math tests. I got a perfect score on the project, but then they're asking me sh*t like this:

If the set T has n members, how many distinct sets S are subsets of T? You may want to figure out the answer for a few specific values of n first. Enter the answer below as a math expression in n.

I know how to figure that out, but I don't know how to write it as a f*cking equation. I don't know what's acceptable. I haven't proved it to myself yet, but I believe it's basically n + (n-1) + (n-2) and so on, but I don't know how to write that in a format they'll accept.

edit: oh, and yes, the question in the screen shot there? That does translate down to 'sort the returned tuples'.

These guys are really kind of assholes.

Oh, and f*ck, look at this question:

Pascal's triangle is a triangular array of numbers in which the entry on one row of the triangle corresponds to the sum of the two entries directly above the entry. This program prints out the first few rows of Pascal's triangle.
Enter a math expression in m and n using factorial (!) that represents the value of the nth entry of the mth row of Pascal's triangle. (Both the row numbers and entry numbers are indexed starting at zero.)

What the f*ck does that have to do with f*cking programming? Assholes.

Well, with a little web searching, I was able to pull out a perfect score on that one, but I think those questions were absolutely unreasonable. I'm supposed to be solving the modern formula for Pascal's Triangle, on my own, and historic mathematicians are famous for figuring out ways to do that.

Yes, I realize it's related to the other work, but you wouldn't know that until after you solved it.

I actually think it's more ignorance of how to teach well. The problem is the things they're writing make perfect sense . . . to someone who already understands exactly what they're talking about.

Well, I'm no scholar but even having studied math it takes a time to sift through. Notation is no prophylactic against confusion. Do the Coursera forums help with this, at least?

Well, this week is interesting, in that we're moving into things that I had no exposure to, before. Pathfinding is generally interesting, useful in all sorts of areas... it's something I've thought about, but hadn't really come up with a solution that I liked. And generators are a very useful Pythonism that I had no idea existed.

Do the Coursera forums help with this, at least?

I haven't had much luck there, other than for testing suites. There's one Chinese student in particular who's making some very nice ones. (well, I assume he is a Chinese male from the name, which I can't recall just now: this could be an incorrect assumption on my part.)

The solution I ended up with for last week's project was kind of interesting. Normally, for combinations of things, I use recursive algorithms, because they're reasonably straightforward, and work to any depth. Basically, if you've got a pile of things, you can compute all the combinations by grabbing a thing, and then calculating all the combinations of that thing plus the combinations of the remaining things, and so on, down to having just one thing in the pile, which has only one combination. This translates well to recursion, although all the extra calling can be a little painful.... it can be nice to use globals for the final result, though that's not allowed in this course.

I did my usual recursive solution, and it was working, but then Chromium crashed, I lost a ton of work, and I wasn't able to get it running properly again. I had some odd bugs that I just couldn't chase down, some subtle thing I'd changed that I had forgotten. So I tried redoing the whole thing from scratch, using a variant of their iterative solution for generating combinations.

Their solution basically works like this: start with a set with one empty tuple. For each item in the desired length output, loop over that set. (so just starting with one iteration). Create a new set, and with each item in the old set, loop over all the possible digit choices, adding the item plus the digit to the new set. Once that new set is fully generated, replace the old set with the new one, and then start the loop for the next digit. You end up creating several 'generations' of sets, one generation per digit. This works as well as a recursive solution, being able to handle any number of digits and any number of choices, but it runs faster, possibly a lot faster if it's a big set.

So what I did for gen_all_holds was a variation on that: instead of storing a set of tuples, I used a list, composed of tuples-of-two-tuples. The starting point was creating a list like this:

holds = [(tuple(),tuple(hand))]

So that's starting as a list with a tuple of an empty tuple (for 'held' items) and a tuple containing all the digits in hand. (the 'available' items.)

Then, it did the generation loops, except this time it looped a number of times equal to len(hand). (if there's five things in hand, you need to loop five times.) It created a new list, and then, with each item in the old list, it first stored the 'held' tuple with an empty 'available' tuple; this covers the instances of holding just 1 die and stopping, and then holding 2 dice and stopping, and so on. Then it looped over the right tuple, moving one item from right to left each time, sorted it, and stored both. In other words, if it started out as ((3,4),(1,2)), it would generate ((3,4),()), ((1,3,4),(2)) and ((2,3,4),(1)). When finished, it set the old list to be the new list, and started the next counted loop.

After that was finished, I had a long list of tuple pairs, each of which had a value I cared about (the left 'held' tuple), and one I didn't (an empty 'available' tuple.) So I returned a set this way:

return set([item[0] for item in holds])

... pulling out just what I cared about, converting it into a set, and returning it, all on one line.

Python isn't very fast, but it sure makes some things easy to write.

Malor wrote:

The solution I ended up with for last week's project was kind of interesting. Normally, for combinations of things, I use recursive algorithms, because they're reasonably straightforward, and work to any depth. Basically, if you've got a pile of things, you can compute all the combinations by grabbing a thing, and then calculating all the combinations of that thing plus the combinations of the remaining things, and so on, down to having just one thing in the pile, which has only one combination. This translates well to recursion, although all the extra calling can be a little painful.... it can be nice to use globals for the final result, though that's not allowed in this course.

I did my usual recursive solution, and it was working, but then Chromium crashed, I lost a ton of work, and I wasn't able to get it running properly again. I had some odd bugs that I just couldn't chase down, some subtle thing I'd changed that I had forgotten. So I tried redoing the whole thing from scratch, using a variant of their iterative solution for generating combinations.

Their solution basically works like this: start with a set with one empty tuple. For each item in the desired length output, loop over that set. (so just starting with one iteration). Create a new set, and with each item in the old set, loop over all the possible digit choices, adding the item plus the digit to the new set. Once that new set is fully generated, replace the old set with the new one, and then start the loop for the next digit. You end up creating several 'generations' of sets, one generation per digit. This works as well as a recursive solution, being able to handle any number of digits and any number of choices, but it runs faster, possibly a lot faster if it's a big set.

So what I did for gen_all_holds was a variation on that: instead of storing a set of tuples, I used a list, composed of tuples-of-two-tuples. The starting point was creating a list like this:

holds = [(tuple(),tuple(hand))]

So that's starting as a list with a tuple of an empty tuple (for 'held' items) and a tuple containing all the digits in hand. (the 'available' items.)

Then, it did the generation loops, except this time it looped a number of times equal to len(hand). (if there's five things in hand, you need to loop five times.) It created a new list, and then, with each item in the old list, it first stored the 'held' tuple with an empty 'available' tuple; this covers the instances of holding just 1 die and stopping, and then holding 2 dice and stopping, and so on. Then it looped over the right tuple, moving one item from right to left each time, sorted it, and stored both. In other words, if it started out as ((3,4),(1,2)), it would generate ((3,4),()), ((1,3,4),(2)) and ((2,3,4),(1)). When finished, it set the old list to be the new list, and started the next counted loop.

After that was finished, I had a long list of tuple pairs, each of which had a value I cared about (the left 'held' tuple), and one I didn't (an empty 'available' tuple.) So I returned a set this way:

return set([item[0] for item in holds])

... pulling out just what I cared about, converting it into a set, and returning it, all on one line.

Python isn't very fast, but it sure makes some things easy to write.

Pssst.

Sadly, we don't have itertools on Coursera; we have to do it manually.

But thanks!

edit: and wow, that's crazy fast, almost like a real language.

itertools is the bomb.
I have a good 300 lines or so of custom iterator funcs I plug in.

itertools is the bomb.

It would have made last week's project into probably a 20-minute job. I basically spent several hours (over two attempts) writing a much slower version of itertools.permutations.

If it makes you feel any better, the Pascal / Permutation boondoggle inoculates you a number of Project Euler problems, if you continue with those.

Turns out further investigations into the triangle lead to traps where traditional or first-instinct approaches are massive time-sinks. Then you get clever and it pops out a solution in no time. That damn triangle bleeds into a lot of topics.

Yeah, actually, I got some distance into Project Euler, which is where I first wrote the recursive permutation algorithm that I was originally using for last week's project. itertools would have been a lot faster. (!)

I have solutions for most of the puzzles up through #67, but it got to the point that I couldn't even understand the questions anymore. It felt a lot like last week's Coursera test, in fact; they kept using syntax I don't know how to read. (This week's was much fairer; I thought; you needed to understand concepts, but you didn't have to write actual equations.)

Project Euler never promised anything else, so it didn't annoy me; I knew it had a lot of math, so once it seemed well and truly over my head, I just stopped, no biggie. With the Principles class, I was much more annoyed, because they didn't say you needed formal math up front, and they seem to be going out of their way to be as confusing as possible.

That whole screenshotted requirement for "you need to sort your answer tuples" was more than a little nuts.

Well, this week's project came together pretty easy.... I had a couple of annoying bugs to track down (forgot to return a value from one function, and got rows and columns mixed up in initial grid generation), but it didn't take that long.

But as far as I can tell, the algorithm they wanted us to use for the zombie search was needlessly complex. They're wanting us to use "breadth-first search" on a grid, and they describe the algorithm this way:

while boundary is not empty: current_cell ← dequeue boundary for all neighbors neighbor_cell of current_cell: if neighbor_cell is not in visited: add neighbor_cell to visited enqueue neighbor_cell onto boundary

But when I started to write that, I realized that the visited grid is not needed. A data structure they require, which isn't mentioned there, is a 2D list of distance-from-X values (where X is either human or zombie).

So, you start by filling your distance list with an impossibly large value (we used row_height * row_width). Then you loop through either humans or zombies, depending, add their locations to the 'boundary' queue, and set the distance values at their locations to be 0.

Then you keep looping through your boundary cells as long as there are any. For each cell, check all the neighbors; if their distance value is less than the current distance + 1, that means that you either haven't visited that cell, or you've found a better path to get there. In either case, you need to evaluate it, so you add it to the boundary queue, and update its distance to current_distance + 1.

And that's it. Voila, you've got a distance function that works, with no "visited" grid.

So I'm really confused about why they wanted us to use one. If you only check each cell once, it seems like you might miss a better path. Admittedly, because the boundary queue is a queue, not a stack, and because all distances are defined as 1, it may not be possible to ever find a better path than one you've already found. Even so, I still don't see the need for the visited grid.

Am I missing something?

edit: clarified the algorithm a little.

You're too fast, today I'm finally getting to implement the last 3 functions in last week's project. (After a few rounds of Ikaruga, of course.)

Malor wrote:

The solution I ended up with for last week's project was kind of interesting. . . .
Python isn't very fast, but it sure makes some things easy to write.

That's an interesting solution. I wound up using their iterative solution, though I'm not sure I understand how it fully works even now after writing it. I did have an issue when I finally submitted it in that I was modifying a set while iterating over it, but that just required a copy of the set and a reassignment at the end of the loop. It worked fine before though, Owltest just complained.

Any interest in sharing what you wrote for gen_all_holds?

Hmm, are we allowed to post our code in public? Maybe it would be okay after the hard deadline?

Oh, I was thinking PM. Not a big deal if you arent comfortable though.