Apps
Contact
Seminars
RSS FeedDynamic Programming Puzzle – $20 Amazon Gift Card
[$20 Amazon Gift Card for the first person who solves this one.]
Problem: Find the least cost path from one end of a 1 dimensional hallway to the other. The diagram may be drawn as follows:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
where the left most space is denoted cell 0 and the right most space is denoted cell n-1. The goal is to get from cell 0 to cell n-1.
Constraints:
1) You may walk 1 cell per move, either to the left or to the right. For example if you are in cell 1 you may walk to cell 2 or cell 0. If you are in cell 0 you may walk only to cell 1.
2) Each cell has a cost associated with it (cost >= 0). This cost represents the cost to walk TO the cell. For example, if you walk from cell 1 to cell 2 you incur the cost of cell 2 to walk there. If you move from cell 2 to cell 1, you incur the cost of cell 1 instead.
3) Certain cells may have a cost of -1 associated with them. If this is the case, you can not move to that cell. You can also not cross over that cell.
4) To assist with the -1 cells, certain cells (but not all cells) have teleporters you can use. Teleporters transfer you to a new cell which is specific to that particular teleporter (could be to the right, could be to the left, or even could be to the same cell). If you are in a cell with a teleporter (or multiple teleporters) it is your choice whether or not you will use a teleporter.
5) All teleporters have the same base cost (see constraint 6). When you teleport, the only charge you incur is the teleporter cost, never any cell cost.
6) Each time you use a teleporter the base cost of teleportation increases by 1. As an example, say the base cost of a teleporter is 10 units. The first teleport you take will cost 10 units. The second teleport (whether it is the same teleporter or a different one) will incur a cost of 11 units because you have already teleported once.
7) You may never teleport to a cell that has a cost of -1.
Input: You are given the following at the beginning of the problem
1) The cost of all n cells (Denoted as C(0) … C(n-1))
2) The location of all the teleporters and the cell which they will teleport you to (like 0->4 3->2 3->8 5->8 could represent a list of 4 teleporters). There could be 0 teleporters available.
3) The base cost for teleportation
PS: It is not required to use Dynamic Programming as the only technique. I mention it only because it appears to be a good choice, but then again, there are no strong hunches!