Ponder This

April 2025 - Challenge

<< March AprilMay >>

In the game of Klumpengeist, the player controls a giant cube (the "Klumpengeist"), which can devour inanimate objects and grow larger as a result. The larger the cube becomes, the larger the objects it can devour. Its goal: either eat all the objects in its vicinity as quickly as possible or grow as large as possible within a specific amount of time.

The size of the cube is determined by its growth points (GP). The initial value of GP is 1, and the size of the cube is the largest n such that n^2 is less than or equal to its GP. For GP 1, the size is 1; for GP 13, the size is 3; for GP 25, the size is 5, and so on.

We represent the game board as an array of numbers, e.g.,

0 1 1 2
1 3 0 1
2 0 0 4
0 2 1 3

The player begins in the top-left corner. The numbers on the board represent the sizes of the objects in each cell; 0 denotes an empty cell. To enter a cell, the Klumpengeist must be of a size greater than or equal to the size of the object in that cell. In this case, it devours the object, the cell becomes empty, and that object's size is added to the Klumpengeist's GP.

In the example above, the Klumpengeist can go RIGHT or DOWN at the beginning, but going DOWN will result in it having GP 2, which is not enough to continue moving DOWN again. However, if it returns UP to the first row and moves RIGHT and then RIGHT again, it will reach GP 4. This means it will reach a size of 2 and be able to devour the 2 in the upper-right corner.

An example of a path for the Klumpengeist that devours all the objects on the board is:

RRDRULLLDDURDDRRU

This path contains 17 steps.

Your goal: Find a path with at most 500 steps that devours all the objects on the board

 0  0  1  5  1  0  0  0  0  0  1 19  0  7  4  2  7 12  7  1
 2  6  0  0  1  8  0  8  1  2  1  0  8  9  1  7 10 13 10  6
 4 11  6  7  5  5 14  1 12  1  0  2  0  2  2  5  1 10  0 14
15 12  2  5 18  6 19 16 18 11 14  3  1  2  3  3  8  2  1  9
 5  6  8 18  4 17  7 16 14 13  4 13  8  1  2  2  7  5 11 12
 6  7 13 16  1 14  7 17 18  9 14  6 16 10  0  3  2  0  6  5
11  5 11  3 14 19 19  4 17 16  3 12 17 17  1  2 12  6  7 11
18  6  6  3 19 13  7  9  5 13  4  4  2 13  2  0  0  5  4  6
17 19  7  2  4  3  4  1 16  9 13 17 17 15  6  9  1  5  2  0
 8  8 17 18 10 12 10  0  0 13 13 10  8  0  0  7 18 10  6  3
13  3 19  3  5  9 17 16 12  2 19  9  1 17  3  0 10 11  4 19
14  5 11 13 15  6  5 10  6  1  7  3  4 15 10 10 13  4  9  7
 2 12  5  7  7 16  3  2 18 14 11 18 12 15  4  2 12 15 10  6
12  5  2 15  8  9 18  9  5  1 17 17  1  0  8  9  5  6  8 13
 9 13  5  3  9  8 18 15 10  6 12 18 11 15  2 12  6  8 12 15
14  4  2  0 13  2 18 12 16  2  4 13  0  3 16 15 15 16  7  7
 6 12  1 14  4 12  8 14 10  0 15 16 13  4  5 12  5  2 16 12
 5  5  3  0  8  0  5 16 11  4 17 13 18 17  0  9  8 16 13  6
15 13 13  5  6  7  9 15 12 18  2 12 19  4  9  5  6  8  9  3
12 10 11  2  5  8 11  7 16 12  0 14 10  5  9  0 15  4 11  3

Provide your result as a string of "U", "D", "R", and "L", as shown in the example above.

A bonus "*" will be awarded for finding a path of at most 150 steps that reaches a size of 30 on the following board:

 0  1  0  0  0  5 16  8 15  4  5  5 17 17  7 11 18  4 16 15  9 17  1  3 19  6  4 16  3  7
 6  3 13 11  1  5 10 18  8 18  8  8  3 10 18  4  2  8  3  1 11 12 11 15 12  8 14  5  4  9
 9  0 15  4  1 11  1 11 17  8  4  6  4 12 16 19  9  8  4  2 18 12  1  4  4 10 10  4  9  2
10 10  2  9  1 19 19 16 19 18  2  4 17  6  8  1 14  9 13  4  1  4 10  2 11  2  7  8 10 15
11  6 14  1  0  8  4  9  3 16  6  6 14  9  5 19 13  5  5  0 17 18  8 17  6  4  5 17  5 15
 0  1  0  0  7  1  8  0  4  3  3  5 10 16  2  9 18 17 17  6 14 15 13 12  1  8 15  1  9  1
 0  1  1  0 19  4  1  0 13  4  4  6  3 11 11  1 19 17 12  7 16 17  0 18  0 14 17 18 17 18
16 14  5  1  3  0 18 12 15  7  2  0  2  2  8 13  3  9 13 13 18  3  1 12 18 19  1  6 16  0
 7 13 15  9  0  1  4 15  8  3 19 12  4  0  2  1 11 19  6  3  0 14  5 15  7  4  3 15 10 15
19 16 11  8  3  2 10 13 10 14 11 12 10 18  6  2  7  9 11 10  4 14 10  6 11  4 12  5 17 10
 9  0 10 19 19 11 14 19 17  3  4  8 11  4  3  6  8 12  4  8  4  3 16 10  4 10 12 10 19  0
18 17  1 17 19  5  3 10 10 19 17  6  6 14  3  2  8  5  1  2  8 10  7  4 18 10  5  3  9  6
10 16  0 17 11 10 14  1 11  1  2 14 16  4  8  2 10  2  8  8 18 12 18 13 18  1 17 18  8  2
 2 11  8 11 12 15  0  5  8  3  4  6  6  7  6 15  7  7 13 18 13 12 14  9 15  0 15  8  1  7
 2  6 17 14  5 14  0  8  1 11 13 13 19 13  5  1  8  9 18  5  1 16 14 11  9  2 12 18 10 19
15  2 15 17  8  5 11 18 16 10  7  1 17 18 19  9  4 13 12  6  3  2  4  5  0 13 13 17 19 12
17  4  4 17  8 14  6 12 18 14 13  7 17  5 19 18  9 11 11 10  6 17 19  6 13 19  7  0 14  5
 8  9 10  2 19  3  7 10  9 14 16  3  6  4  1 15 13  8  5  0 14  8  6  0  1  3 14  1 13 10
12  3 10 18  5 19 17 16  5 12 14 19  6 13 15  3  1 15 15  4 10  9 12  2 19  3 10 13 12  2
19 18 17 19  2 18 16  5  6  4 12 10  0  1  5 12 10 18  3  0  3 12 14  2 16 13  9 15 10 15
17  5 19 16 14  6  2 15  9 14 19 15  7 15 16  6 12  1  8 12  2 14 12 18  4  4  4 12 12 17
 6 12  7 17  0 11 17 11  5 12 13  6  4 13 15 16  9 16 15  3 13 11  3 17 14  9  5  5  5 12
 3  0  4 15 16  4 17  2  2 16  0  1  7  4  3  0  4  2  9 13 13  4 15 10 16  0  1  5  1  2
 6  1  9  6  9  9  8 18  2  5  2  9 19  0 12  7  0 17  4  3 19 10 12 14 10  8  6  6 10 19
 6 11 13  2 17 11  3  1 18 13 12  0 11  7  2 12  9  3 13  8  2  1 17 19 11 19  5  0  2 15
13 19 12 17  9 18 13  9  1 12  6  9 15 13  9  3  4  4  0 15 15  4 16  9 16 13  1 13  4  6
17  5 11  3  3 15  9 16  8  1 15 14  9 12 13  8 17  1 16  7 15 17 18  8 11 16 19 14  7  8
 6 10 18 16  4 10  2 14  6  2  1  1 18  0  6 17  6 15 17  0  5 13 11  4  8 10  8  1 10 13
13  0  3  2  9 14  3  5 14 11  4 13  0  8  5 14 14  8 19  7 14 10 16 14  8 19 19  2  6 19
 5  3  4  5 10 19  2  5  8 10  9  6 11  4  4 12 10 15 17 15  8  9  5 19 14 16 12 16 16  5

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com