StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Actually the problem here is one instance of a much more general class of problems/algorithms which are incidentally quite important in some fields nobody would believe from this example ;)</p> <p>Basically you can regard your triangle above as a matrix. Ie the second number in the L row (the 3) would be (0,1), 3rd value in the E row would be (3,2). If you look at it you see that every value except the start values depend on exactly two other nodes, which makes this a 2-point stencil. There are some extremely intriguing algorithms out there for this kind of problem - eg a cache oblivious, parallel algorithm for higher-order stencils (LBMHD uses 13-points or something).</p> <p>Anyways that stuff is completely out of your league I fear (don't ask me about details either~) - there are even more or less recent papers about this ;)</p> <p>PS: And my personal small implementation. Can't get much simpler and has the typical structure of a simple recursive program. You call it with getVal(0, 5); or more generally getVal(0, startVals.length - 1). Just think about it as working backwards from the solution to the start. We want to know what the right field in the first row has. To get this we need to know two the values of two other fields which we have to compute first in the same manner. This is done until we get to a field where we already know the result - ie our start values.</p> <pre><code>private int[] startVals; // contains start values for all 6 letters. // for your example startVals[0] == 2; startVals[5] == 0 public int getVal(int row, int col) { if (col == 0) return startVals[row]; return getVal(row, col-1) + getVal(row + 1, col - 1); } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload