CODEWITHSUNDEEP
python
louie mcconnell
louie mcconnell

Reputation: 761

Python Repeated Lists

First things first, here's my code:

row_1 = [3]
row_2 = [7, 4]
row_3 = [2, 4, 6]
row_4 = [8, 5, 9, 3]

for element in row_3:
    key = row_3.index(element)
    row_3[key] = element + max(row_4[key], row_4[key + 1])

for element in row_2:
    key = row_2.index(element)
    row_2[key] = element + max(row_3[key], row_3[key + 1])

for element in row_1:
    key = row_1.index(element)
    row_1[key] = element + max(row_2[key], row_2[key + 1])

print(row_1)

This code works, so far. As you may notice, there is quite a bit of repitition, and I was wondering how I could compress it. Ideally, I would like something like 

for element in row_x:
    key = row_x.index(element)
    row_x[key] = element + max(row_(x+1)[key], row_(x+1)[key + 1])

I know that this is completely wrong, but it was just what I had in my head. I would greatly appreciate all insights.

Oh, by the way, this code maxizes the sum of the two adjacent numbers in a pyramid (see here: http://projecteuler.net/problem=18)

Upvotes: 1

Views: 90

Answers (3)

utdemir
utdemir

Reputation: 27216

Here is exactly the translation of what you say(eliminating loop repetition):

l = [[3],
     [7, 4],
     [2, 4, 6],
     [8, 5, 9, 3]]

for row in range(len(l)-2, -1, -1)
    for key, element in enumerate(l[row]):
        l[row][key] = element + max(l[row+1][key], l[row+1][key+1])

print(l[0][0])

Your mistake was storing the triangle on separate data structrures, just use a nested list and iterate over it.

Also, if you need both the element and the index when iterating over an iterable, use enumerate function.

  • Since range(start, end, step) iterates from start to end(without including end), and step is the increment, range(range(len(l)-2, -1, -1) iterates like "len(l)-2 -> len(l)-3 -> ... -> 1 -> 0". Note that we want 0 to be included, so we pass -1 as a parameter. A good mnemonic for both the range function and slices is "you pass the first parameter you want, and the first parameter you don't want".
  • Also, as @user2357112 said, tuple packing-unpacking is a pretty nice feature of Python. Basically, when RHS of the assignment is an iterable, you can use a tuple on LHS and the elements will be assigned accordingly. You can omit parantheses and there are a little more syntactic sugars:

Like:

In [1]: a, b, *c, d = range(5)

In [2]: a, b, d
Out[2]: (0, 1, 4)

In [3]: c
Out[3]: [2, 3]

And you can use the unpacking in loops too:

In [1]: l = ["enumerate", "is", "a", "nice", "builtin"]

In [2]: list(enumerate(l))
Out[2]: [(0, 'enumerate'), (1, 'is'), (2, 'a'), (3, 'nice'), (4, 'builtin')]

In [3]: for i, v in enumerate(l):
   ...:     print(i, "->", v)
   ...:     
0 -> enumerate
1 -> is
2 -> a
3 -> nice
4 -> builtin

Upvotes: 2

Shoikana
Shoikana

Reputation: 605

This answer is based on the problem in the link, not on your code, so it might not be of any use to you.

Sounds to me like a "reverse" Dijkstra's algorithm problem (Dijkstra's algorithm usually looks for the shortest path, not the maximum path, and is usually applied to a graph, but it can be adjusted for your pyramid.)
Dijkstra's looks like this:

  1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.

  2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes.

  3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.

  4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.

  5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished. Select the unvisited node that is marked with the smallest tentative distance, and set it as the new "current node" then go back to step 3.

These steps are from Wikipedia's page on Dijkstra's algorithm

Upvotes: 0

Addison
Addison

Reputation: 1075

Try putting all the rows into a list, then reverse iterate through them:

row_1 = [3]
row_2 = [7, 4]
row_3 = [2, 4, 6]
row_4 = [8, 5, 9, 3]

rows = [row_1, row_2, row_3, row_4]

for row_index, row in reversed(list(enumerate(rows[:-1]))):
  for key, elem in enumerate(row):
    lower_row = rows[row_index+1]
    row[key] = elem + max(lower_row[key], lower_row[key+1])

print rows[0]

Upvotes: 1

Related Questions