Home ›

Q*Bert chrismas tree puzzle

Christian Harms's picture
by Christian Harms on Mon, 12/19/2011 - 13:28
in

This is a short coding puzzle with q*bert (who is q*bert?) and an chrismas tree.

the qbert question

qbert chrismas tree coding puzzle
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:

  1. chrismasTree = [[75],
  2.               [95,64],
  3.             [17,47,82],
  4.           [18,35,87,10],
  5.         [20, 4,82,47,65],
  6.       [19, 1,23,75, 3,34] ]
  7. 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?

  1. tri = []
  2. peUrl = "http://projecteuler.net/project/triangle.txt"
  3. for line in urllib.urlopen(peUrl).readlines():
  4.     tri.append([int(x) for x in line.strip().split(" ")])
  5. 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.

Comments

Robin Houston's picture
How do you get 244 for the
Robin Houston (not verified) - Mon, 12/19/2011 - 12:18

How do you get 244 for the small example? I make it 465: 75 + 64 + 82 + 87 + 82 + 75. What have I got wrong?

Christian's picture
copy - paste - error
Christian (not verified) - Mon, 12/19/2011 - 12:46

you are right! Best way is 75+64+82+87+82+75 = 465, second best way is 75+95+47+87+82+75 = 461.

undu's picture
Yes, I get the same here.
undu (not verified) - Mon, 12/19/2011 - 13:06

Yes, I get the same here.

Anonymous's picture
Spoiler
Anonymous (not verified) - Mon, 12/19/2011 - 13:50

  1. 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')

Nico Heid's picture
gung'f n ovg areql ;)
Nico Heid - Thu, 01/12/2012 - 08:46

gung'f n ovg areql ;)

Marius Gedminas's picture
Dynamic programming?
Marius Gedminas (not verified) - Mon, 12/19/2011 - 20:15

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).

Matthias Reuter's picture
With Javascript
Matthias Reuter - Tue, 12/20/2011 - 07:04

  1. christmastree.reduceRight(function (a, b) {
  2.     return b.map(function (n, i) {
  3.         return n + Math.max(a[i], a[i+1]);
  4.     });
  5. })[0];

Willyfrog's picture
different problems
Willyfrog (not verified) - Fri, 12/23/2011 - 08:33

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 ;)

Nico Heid's picture
the java (people) solution
Nico Heid - Fri, 12/30/2011 - 16:14

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. :D (otherwise just iterate over the tree row times)

  1. public class Treecalc {
  2.     public static void main(String[] args) {
  3.  
  4.         int[][] tree = {{75},
  5.                 {95, 64},
  6.                 {17, 47, 82},
  7.                 {18, 35, 87, 10},
  8.                 {20, 4, 82, 47, 65},
  9.                 {19, 1, 23, 75, 3, 34}};
  10.  
  11.         new Treecalc().calculate(tree, tree.length - 1);
  12.  
  13.     }
  14.  
  15.  
  16.     public void calculate(int[][] tree, int row) {
  17.         if (row == 0) {
  18.             System.out.println(tree[0][0]);
  19.         } else {
  20.             for (int i = 0; i < tree[row - 1].length; i++) {
  21.                 tree[row - 1][i] += Math.max(tree[row][i], tree[row][i + 1]);
  22.             }
  23.             calculate(tree, row - 1);
  24.         }
  25.     }
  26. }