Help understanding triangle path code

Hi Everyone,

I’m about two weeks in to Elixir and have gotten stuck on understanding the triangle path code from rosetta code:

defmodule Maximum do
  def triangle_path(text) do
    text
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      line
      |> String.split()
      |> Enum.map(&String.to_integer(&1))
    end)
    |> Enum.reduce([], fn x,total ->
         [0]++total++[0]
         |> Enum.chunk_every( 2, 1)
         |> Enum.map(&Enum.max(&1))
         |> Enum.zip(x)
         |> Enum.map(fn{a,b} -> a+b end)
       end)
    |> Enum.max()
  end
end

Basically I’ve deconstructed it line by line and adding one line at a time to see how it progresses. It’s all ok until I get to Enum.reduce where I pipe the following data to it:

iex> c = [[1], [2, 3], [4, 5, 6]]
iex> c |> Enum.reduce([], fn x, total -> [0]++total++[0] end)
[0, 0, 0, 0, 0, 0]

Trying to figure out why it’s all zeros, but the number of elements is equal so I sort of see the pattern.

Then:

iex> c |> Enum.reduce([], fn x, total -> [0]++total++[0] |> Enum.chunk_every(2,1) end)
[
[0, [0, [0, 0]]],
[[0, [0, 0]], [[0, 0], [0]]],
[[[0, 0], [0]], [[0], 0]],
[[[0], 0], [0]],
[[0], 0],
[0]
]

This seems to be a recursive chunking, which I can sort of understand
next:

iex> c |> Enum.reduce([], fn x, total -> [0]++total++[0] |> Enum.chunk_every(2,1) |> Enum.map(&Enum.max(&1)) end)
[0, 0, 0, 0, 0, 0]

Now I’m starting to get lost as I’m not sure why we’re calling map on max since it’s all zeroes

Then finally:

c |> Enum.reduce([], fn x, total -> [0]++total++[0] |> Enum.chunk_every(2,1) |> Enum.map(&Enum.max(&1)) |> Enum.zip(x) end)
[{{{0, 1}, 2}, 4}, {{{0, 1}, 3}, 5}, {{{0, 1}, 3}, 6}]

Now I’m really confused as the numbers appear and appear in the right order as well. Not all elements appear tho, for example, there’s no 1,2,5 which is a valid path.

I’m missing something here and I’m not so sure what it is, can someone please explain to how this code does what it does?

2 Likes

Hello, welcome to the forum

For the first part, I can tell You x is never used… You just cumulate total… 3 times

iex(1)> [0]++[]++[0]  
[0, 0]
iex(2)> [0]++[0, 0]++[0]
[0, 0, 0, 0]
iex(3)> [0]++[0, 0, 0, 0]++[0]
[0, 0, 0, 0, 0, 0]

It could as well be

c |> Enum.reduce([], fn _x, total -> [0]++total++[0] end)
2 Likes

The reason your answer is so much different from the one that the original function computes, is because Enum.reduce(a_collection, [], fn x, total -> ... end) uses [] as the value for total during the initial iteration, but whatever the function returns for the second iteration.

So attempting to understand what it does by removing the latter part of the Enum.reduce function body will not help, because after the initial iteration it will no longer do what the original function would do.

What might help somewhat, is to add an IO.inspect-statement after the final line of the function in the reduce (After the |> Enum.map(fn{a,b} -> a+b end) line).
Calling the function then (using the input that is given on the RosettaCode page), prints the following subsequent outputs:

'7'
[149, 103]
[244, 179, 199]
[321, 315, 225, 266]
[418, 334, 391, 304, 311]
[425, 454, 470, 407, 348, 379]
[473, 461, 479, 488, 477, 405, 385]
[491, 545, 558, 534, 547, 556, 434, 475]
[511, 621, 645, 569, 579, 563, 563, 524, 493]
[538, 704, 703, 680, 650, 590, 588, 620, 553, 578]
[552, 768, 740, 799, 707, 661, 648, 676, 712, 596, 633]
[554, 858, 771, 859, 847, 756, 702, 722, 745, 748, 680, 656]
[646, 908, 906, 861, 895, 906, 798, 801, 817, 768, 830, 757, 698]
[702, 986, 946, 986, 934, 981, 908, 872, 883, 883, 831, 833, 812, 770]
[746, 1011, 1053, 1070, 1057, 1048, 992, 969, 923, 940, 941, 922, 873, 868, 806]
[831, 1043, 1078, 1155, 1127, 1105, 1132, 1027, 1016, 1002, 958, 942, 923, 972,
 957, 858]
[837, 1114, 1106, 1230, 1249, 1175, 1169, 1142, 1050, 1067, 1008, 1006, 995,
 990, 1046, 1055, 873]
[864, 1116, 1206, 1253, 1257, 1320, 1251, 1253, 1157, 1119, 1159, 1071, 1087,
 1005, 1090, 1065, 1124, 966]

(Note that '7' is the same as [55] but printed as a character list)
Clearly, the result of every iteration is a list containing each of the totals if the path to that particular element was picked.

An annotated version:

Enum.reduce(triangular_list_of_lines, [], fn x,total ->
  [0]++total++[0] # Ensure `chunk` also emits a full two-element chunk at the start and end of the list.
  |> Enum.chunk_every( 2, 1) # Turns the list into one where each two-element sublist indicates the two choices that chould be made from this position.
  |> Enum.map(&Enum.max(&1)) # Only consider the possibility that is larger.
  |> Enum.zip(x) # Combine with the list of current-row elements we have. Also drops the final `[0]`. We now have a list where each element is `{largest_parent_path, value}`.
  |> Enum.map(fn{a,b} -> a+b end) # Add the element's value to the path.
end)

The insight here is thus that we look for each element towards the two possibilities that might arrive at it.
I still find this algorithm a bit confusing and hard to understand as well; maybe there is a simpler variant, but that is how it works.

6 Likes

The code is clever. It can deal with negative numbers. When I am trying to understand such a piece of code, I am putting |> IO.inspect everywhere to check what the transformations do. It doesn’t make sense to check line by line because the transformation is not finished and you get jibberish output.

[[1], [2, 3], [4, 5, 6]]
|> Enum.reduce([], fn x, total ->
  ([0] ++ total ++ [0])
  |> IO.inspect(label: "totals")
  |> Enum.chunk_every(2, 1)
  |> IO.inspect(label: "chunked")
  |> Enum.map(&Enum.max(&1))
  |> IO.inspect(label: "maximums")
  |> Enum.zip(x)
  |> IO.inspect(label: "zipped")
  |> Enum.map(fn {a, b} -> a + b end)
  |> IO.inspect(label: "new totals")
end)
|> Enum.max()
|> IO.inspect()

outputs

totals: [0, 0]
chunked: [[0, 0], [0]]
maximums: [0, 0]
zipped: [{0, 1}]
new totals: [1]
totals: [0, 1, 0]
chunked: [[0, 1], [1, 0], [0]]
maximums: [1, 1, 0]
zipped: [{1, 2}, {1, 3}]
new totals: [3, 4]
totals: [0, 3, 4, 0]
chunked: [[0, 3], [3, 4], [4, 0], [0]]
maximums: [3, 4, 4, 0]
zipped: [{3, 4}, {4, 5}, {4, 6}]
new totals: '\a\t\n'
10

I am reading it like this:
For every line in the triangle, we try to substitute it with the max value we can get walking to that point.

total should be called totals. It is a list where instead of the element we have the biggest sum that we can get going from top.

  • For [1] it is [1]
  • For [2, 3] it is [3, 4] because there is only one way to get there via 1.
  • For [4, 5, 6] it is [7, 9, 10] because 4 has only one parent 2. It is total was 3 so 2+3=7, 5 has two parents 2 and 3, their running totals 3 and 4. 4 is bigger so 5 + 4 = 9. 10 has one parent: 3. The total for 3 was 4, so 6 + 4 = 10.

So there are already four cases.

  • There can be no parent at the top of the triangle.
  • There can be one parent on the right in the beginning,
  • Two parents in the middle
  • Or one on the left at the end.

This is where the clever part comes:

[0]++total++[0]

ensures that every number has always two parents instead of dealing with cases.

We start with an empty list of totals, so the first one will have two parents [0, 0].
After the whole iteration, we get the running totals: [1] so the next line will have parents [0, 1, 0].
The last line has running totals [3, 4] so the list of parents will be [0, 3, 4, 0].

This way we can do the chunking to compute both parents of the given value. E.g. last line has three values: [4, 5, 6] and the respective list of parent totals are [[0, 3], [3, 4], [4, 0], [0]]. That last zero won’t be used. We could run Enum.chunk_every(2, 1, :discard) to get rid of it. But it doesn’t hurt us either.

In the next step, we take bigger of the two parents with Enum.map(&Enum.max(&1)) and we get only the bigger from the two parent totals [3, 4, 4, 0]. Again, the zero is there by accident but it doesn’t hurt because next, we do the zip(total, x) to get tuples [{max_total_for_element, element}]. Zip stops when one of the lists ends, so we get rid of that unwanted zero at the end.

Next, we sum the running total with element Enum.map(fn{a,b} -> a+b end) and we get the row with totals instead of elements.

I think the biggest problem was that you were trying to understand the solution by deleting some lines. The unfinished transformation in reduce produced more and more jibberish with every iteration. IO.inspect is a surprisingly good tool to gather understanding. Especially given the label option that adds to output without breaking the pipe flow.

7 Likes

Thank you everyone for your help.

1 Like