This is a short coding puzzle with q*bert (who is q*bert?) and an chrismas tree.
the qbert question
The task: Our 2011 q*bert can only jump down. He start from the top and has to find the path to the bottom of the chrismas tree with collecting the most points available (while jumping left-or-right down). Find the way with the highest sum.
Input:
chrismasTree = [[75],
[95,64],
[17,47,82],
[18,35,87,10],
[20, 4,82,47,65],
[19, 1,23,75, 3,34] ]
print qbertRun(chrismasTree)
The sum is 465 – try to solve it with a little program. The brute force method will be possible with this small tree.
Does your solution solve the task with larger data?
Project Euler offers the same question (Problem 67) with a larger triangle. Does work your solution with this data set?
tri = []
peUrl = "http://projecteuler.net/project/triangle.txt"
for line in urllib.urlopen(peUrl).readlines():
tri.append([int(x) for x in line.strip().split(" ")])
print qbertRun(tri)
If you solved the larger data set and had fun register on project euler and try out other problems. Feel free to link your solution from you blog to this article and write a comment. My solution will published this year.
Christian Harms
Latest posts by Christian Harms (see all)
- google code jam 2013 – tic-tac-toe-Tomek solution - April 16, 2013
- Google code jam 2013 – the lawnmower - April 14, 2013
- code puzzles and permutations - April 11, 2013
How do you get 244 for the small example? I make it 465: 75 + 64 + 82 + 87 + 82 + 75. What have I got wrong?
you are right! Best way is 75+64+82+87+82+75 = 465, second best way is 75+95+47+87+82+75 = 461.
Yes, I get the same here.
print r'''Kqrs d(gerr):K fby = [0]*(yra(gerr)+1)K sbe ynlre va erirefrq(gerr):K fby = [k + znk(fby[v:v+2]) sbe (v,k) va rahzrengr(ynlre)]K erghea fby[0]K'''.decode('rot13').replace('X', '\n')It looks like this should be efficiently solvable using dynamic programming. For every position the best score
S(r, c) = max(S(r-1, c), S(r-1, c-1)) + christmasTree[r][c]
and to handle corner cases
S(r, 0) = S(r-1, c) + christmasTree[r][0]
S(0, 0) = christmasTree[0][0]
and the final answer is max(S(r, c) for c in range(r + 1)) where r = len(christmasTree) – 1. All you need to do is calculate those S(r, c) in the right order (i.e. increasing r).
christmastree.reduceRight(function (a, b) { return b.map(function (n, i) { return n + Math.max(a[i], a[i+1]); }); })[0];What you are asking in your problem, and the one for projet euler are in fact different problems, being yours slightly more difficult. The difference would be that yours is asking for the path to get the maximum sum, and PE’s one is only asking for the actual sum. Obviuosly not taking into account the size of the data sample.
Almost the same, but not quite
As I’m a real fan up bottom up for this solution, I’ll just add the max of the tow numbers to the row above and work my way up. I left the recursion just because I can, not because it’s necessary.
(otherwise just iterate over the tree row times)
public class Treecalc { public static void main(String[] args) { int[][] tree = {{75}, {95, 64}, {17, 47, 82}, {18, 35, 87, 10}, {20, 4, 82, 47, 65}, {19, 1, 23, 75, 3, 34}}; new Treecalc().calculate(tree, tree.length - 1); } public void calculate(int[][] tree, int row) { if (row == 0) { System.out.println(tree[0][0]); } else { for (int i = 0; i < tree[row - 1].length; i++) { tree[row - 1][i] += Math.max(tree[row][i], tree[row][i + 1]); } calculate(tree, row - 1); } } }gung’f n ovg areql