👾

Doodle Jump

Week 20

You are a competitive speed-runner (someone who tries to complete games as quickly as possible/with the highest score etc) looking to speed run Doodle Jump and similar games - after intensive investigation, you have discovered the memory offsets of the platform data as the game is running

If you are unfamiliar with Doodle Jump, you can play it online here to familiarise yourself

For your program, you will process the platform data in blocks of 25 rows at a time

Your goal is to find all routes that can complete these 25 rows, according to the following rules:

• You start at the bottom row (any column)
• Since you are looking to speed run, each move you have to jump up - you can't go across to another platform in the same row (this requirement to always jump up also means you don't have to consider getting stuck in a loop)
• Your character has a constant jump height of 3 rows - it is therefore better to jump as many rows as possible, since you don't have to wait for gravity to make the character fall back down again - the time units taken:
• Jumping 3 rows takes 3 time units
• Jumping 2 rows takes 4 time units (3 units to go up...and 1 to fall back down 1 row)
• Jumping 1 row takes 5 time units (3 units to go up...and 2 to fall back down 2 rows)
• Each column moved horizontally takes 0.5 time units
• The target is to jump off the top of the board - when in this range, you don't have to consider other platforms, since when you jump up, you will have already passed the goal - for example, suppose there is a platform in row 2 which you have reached and another in row 1 - when you jump on the row 2 platform, you will jump up 3 rows, hence have left the board, so won't fall back down to the platform in row 1

Your program should output the following:

• Number of routes
• The time units and full path of that route, ordered from fastest (least time units) to slowest

For example, suppose we have the following array - letters denote a platform, to make it easy to visualise the route/debug etc

[ [" ", "E", " "], [" ", " ", "D"], [" ", " ", " "], [" ", "C", " "], [" ", " ", " "], ["A", " ", "B"] ]

The expected output would then be:

--- Found 4 Routes --- 8.5 | A C E 8.5 | B C E 11.0 | A C D 11.0 | B C D

For example, looking at the route ACE, we can see that from A to C takes 4.5 time units (4 units to go up 2 rows and 0.5 units to move 1 column horizontally) - then 3 time units to go up from C to E...and finally just a jump of 1 (i.e. 1 time unit, since we don't have to wait for them to fall back down) to leave the top of the board - giving us a score of 8.5 time units for this route

Likewise, the route BCD would take 11 time units: 4.5 from B to C, 4.5 from C to D - it will then take a jump of 2 to leave the board (again, we can ignore platform E in this case, since we would have left the board before we fall back down)

Note that you only have to order by the time units - since e.g. ACE and BCE both take 8.5 time units, then site will accept either ACE or BCE coming first in your output

We can then look at another example below:

[ [" ", "F", " "], [" ", " ", "E"], ["D", " ", " "], [" ", "C", " "], [" ", " ", "B"], [" ", "A", " "] ]

Here is the corresponding output - hopefully you are able to understand how each route is determined and calculated:

--- Found 9 Routes --- 6.5 | A D 8.0 | A C F 10.5 | A C E 10.5 | A B E 12.5 | A C D 13.5 | A B D 15.0 | A B C F 17.5 | A B C E 19.5 | A B C D

The data you should use for the real challenge is below - good luck!

Since the output for this program will be large, there is also an option to load a text file containing your answer instead

[ [" ", " ", "Z"], [" ", "Y", " "], ["X", " ", " "], [" ", " ", "W"], ["V", " ", " "], [" ", " ", " "], [" ", "T", "U"], [" ", " ", " "], ["R", " ", "S"], [" ", "Q", " "], ["O", " ", "P"], ["N", " ", " "], [" ", "M", " "], [" ", "L", " "], [" ", " ", "K"], [" ", " ", " "], [" ", "I", "J"], ["H", " ", " "], ["G", " ", " "], [" ", " ", "F"], [" ", "E", " "], [" ", " ", " "], ["D", " ", " "], [" ", " ", "C"], ["A", "B", " "] ]

Paste your answer below or load in a text file containing your answer

...or...

Submit Answer

Hints

Hints will be released at the start of each of the following days - e.g. the start of day 3 is 48 hours after the challenge starts

Release Day	Hint
2	You might find recursion useful for this challenge
3	For example, a recursive jump module that takes the current path, row, height and number of time units to reach this point would be a good start
4	You could check all 3 columns in the bottom row to see if they contain a platform - if they do, call your recursive module on that
5	The base case would be if they are less than 3 or less rows from the end (i.e. rows 0, 1 or 2) - then they will simply be able to jump up to victory and you can add this current path/time units to some kind of successful rout array
6	The general case would be to call the recursive module again on all valid platforms - i.e. between 1 and 3 platforms above their current position, passing the correct parameters to the new calls
7	There are multiple ways to calculate/determine the vertical and horizontal time unit cost - e.g. a a calculation, hashmap (dictionary/object/associative array), selection (switch/case/if) statement, function, absolute value of column difference etc
8	You will then have to sort your routes - the easiest way would be using your programming language's built in sort method/function and giving it a custom sorting rule/comparison logic - e.g. sorting by the time unit column/attribute of your routes data structure