# 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