# Help Indiana Jones to get the treasure

## Story

Indiana Jones was exploring a cave where a precious treasure is located. Suddenly, an earthquake was happen.

When the earthquake was ended, he noticed that some rocks fell from the ceiling blocked his way to the treasure. He also noticed that he could push a stone, but since stones were very heavy, he couldn't push two consecutive stones.

Your object is to help Indiana Jones and get the treasure. Since it's very hard to push even a single stone, the number of pushes is very important.

## Problem

Find the best way (where Indiana Jones push stones in least amount), to find the treasure.

## Map (input)

It's `m` by `n` (both larger than 1) matrix where it contains five kinds of cell:

• `0` which means the blank cell,
• `1` which means the wall,
• `2` which Indiana Jones is located in (only one exists),
• `3` which the treasure is located in (only one exists),
• and `4`, which means the rock.

In the first row of the map, the dimension of the map is specified like `4 6`, and from the second row to the last row of the map, the structure of the cave is specified something like this.

``````110131
104040
100101
200000
``````

Therefore, the full map is:

``````4 6
110131
104040
100101
200000
``````

which means

The map is given by stdin, a file (you can specify the name of the file), or an array in the code which contains only above information.

## Output

The minimum amount Indiana Jones should push. If there's no such way, output `X`.

In above case, he can push a stone in the left upward, then he can push a stone in the right rightward to get the treasure. Therefore, the output in this case is `2`.

However. in this case :

``````4 6
111131
104040
100101
200000
``````

(look below section) he can't push right stone because it will destroy the treasure. Also, pushing left stone rightward changes nothing. Therefore, the output is `X`.

## Rules

• He can move in only four direction, up, down, left, and right.
• He can't push two consecutive stones.
• He can't pull any stone, and he can push a stone only in one direction('forward').
• He can't go through walls. Only places he can go are blank cells and the treasure cell.
• The stone can't be placed on the treasure. That will destroy the treasure. :(
• He can't go outside of the map.

## Goals

Program which can handle most maps (provided at the 'Example' section + others) in reasonable time (in specific, 10s) and outputs the right answer wins.

Here 'others' means examples inputs provided in answers. This means you should make a smart algorithm so that other programs can't solve maps what your program can solve, and maps solved by other programs can be solved by your program. However, putting solutions in the code will not considered as valid.

## Note

This was originally a mid-term project of an AI class which I listened to, only one thing was different : it was said that there was only two rocks.

It was said that this problem is NP, but it was also said that good heuristic algorithm can solve the problem quite efficiently. I used some ideas and heuristics to solve the problem efficiently, and my code could find all solutions of samples very quickly (less than a second).

However, when there was more than two rocks, there were some cases where the code couldn't find the answer in a reasonable time. I had some ideas, but some of those were 'wrong', and I couldn't express other ideas to the code. I wanted to see what smart algorithms exist to solve this problem, so I wrote this.

Since I already completed the project (btw, images are not mine - I googled those), you don't have to worry about that.

## Examples

Examples can be seen at here. You can also see examples, and test your results at here (however, it was tested only on the Google Chrome). You can get the map in the format described above, by typing `whatisthis()` in the JS console.

http://bit.sparcs.org/~differ/sokoban/#0 ~ http://bit.sparcs.org/~differ/sokoban/#19 contains examples which it was originally the class provided.

## Result

Sorry, I was late.. quite a lot actually. :P (I was quite too lazy to score. Sorry..)

Below is the result. (X: wrong, O: right, ?: takes at least 10s, halted)

``````Map#: 0 1 2 3 4 5 12 15 19 T1 T2 T3 T4 T5 T6 T7
Ruby: X O O ? O O  O  X  ?  ?  O  ?  ?  ?  ?  ?
Java: O O X O X X  O  O  ?  ?  O  O  O  X  O  O
``````

(Java 19: took 25s, the result was correct.) (I used ruby 1.9.3 and javac 1.7.0_13)

It seems that the Java algorithm was indeed better.. (By the way, I thought a similar method, but I realized that a kind of maps like test map 5 exists.)

-
That's a difficult one. – FUZxxl Dec 3 '11 at 19:26
This makes me want to write a random number generator based on the complexity of the puzzle, always undershooting... people would make up hard puzzles, then scratch their heads for days wondering how my program solved it with only 4 pushes... :) – Nathan Wheeler Apr 25 '12 at 14:51
@NathanWheeler, yeah, build a indeterminstic solver. It works, but you have to run it in a quantum computer. :P – Neil Apr 26 '12 at 10:10
It'd have to compute it starting Indiana Jones at the treasure and working backwards, like you would solve a maze. The difference being that state isn't determined only by position but also by rock positioning (I can pass same place twice if rocks have since been moved). Hmm, I'll have to think more about this.. – Neil Apr 26 '12 at 10:15

## Java - A bit smarter / faster

Quite a bit of code there. I's trying to be faster by evaluating the pushes in order of "how likely is this to free a way to the treasure", which itself is based on two Dijkstra traversals (one stops when encountering rocks, the other ignores rocks). It's working pretty nicely, and the one example from the pastebin that appears to be troublesome for the author is solved in circa 2 seconds by this implementation. Some other examples take up to 30-40 seconds, which I still find too long, but I couldn't find a way to improve on that without breaking the stuff :)

I've split my stuff in several files to get a better structure out (also why I switched to Java from ruby):

Entry point:

``````import java.util.Date;
public class IndianaJones {
public static void main(final String[] args) throws Exception {
final Maze maze = new Maze(System.in);
final Date startAt = new Date();
final int solution = maze.solve();
final Date endAt = new Date();
System.out.printf("Found solution: %s in %d ms.",
solution < Integer.MAX_VALUE ? solution : "X",
endAt.getTime() - startAt.getTime());
}
}
``````

Direction helper enum:

``````enum Direction {
UP(-1, 0), DOWN(1, 0), LEFT(0, -1), RIGHT(0, 1);

public final int drow;
public final int dcol;

private Direction(final int drow, final int dcol) {
this.drow = drow;
this.dcol = dcol;
}

public final Direction opposite() {
switch (this) {
case UP:
return DOWN;
case DOWN:
return UP;
case LEFT:
return RIGHT;
case RIGHT:
return LEFT;
}
return null;
}
}
``````

An abstract class to represent a located part of the "maze":

``````abstract class PointOfInterest {
public final int row;
public final int col;

protected PointOfInterest(final int row, final int col) {
this.row = row;
this.col = col;
}

public final boolean isAt(final int row, final int col) {
return this.row == row && this.col == col;
}

@Override
public final String toString() {
return getClass().getSimpleName() + "(" + row + ", " + col + ")";
}

@Override
public final int hashCode() {
return row ^ col;
}

@Override
public final boolean equals(Object obj) {
if (this == obj)
return true;
if (!(obj instanceof PointOfInterest))
return false;
if (!getClass().equals(obj.getClass()))
return false;
final PointOfInterest other = (PointOfInterest) obj;
return row == other.row && col == other.col;
}
}
``````

And finally, the maze itself:

``````import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class Maze {
private static final char WALL = '1';
private static final char INDY = '2';
private static final char GOAL = '3';
private static final char ROCK = '4';

private final Maze parent;
private final Set<Maze> visited;
private final boolean[][] map;
private final int[][] dijkstra;
private int[][] dijkstraGhost;
private String stringValue = null;

private int shortestSolution = Integer.MAX_VALUE;

private Goal goal = null;
private Indy indy = null;
private Set<Rock> rocks = new HashSet<>();

private Maze(final Maze parent, final Rock rock, final Direction direction) {
this.parent = parent;
this.visited = parent.visited;
map = parent.map;
dijkstra = new int[map.length][map[rock.row].length];
for (final int[] part : dijkstra)
Arrays.fill(part, Integer.MAX_VALUE);
goal = new Goal(parent.goal.row, parent.goal.col);
indy = new Indy(rock.row, rock.col);
for (final Rock r : parent.rocks)
if (r == rock)
rocks.add(new Rock(r.row + direction.drow, r.col + direction.dcol));
else
updateDijkstra(goal.row, goal.col, 0, true);
}

public Maze(final InputStream is) {
this.parent = null;
this.visited = new HashSet<>();
final String[] sizeParts = line.split(" ");
final int height = Integer.parseInt(sizeParts[0]);
final int width = Integer.parseInt(sizeParts[1]);
map = new boolean[height][width];
dijkstra = new int[height][width];

int row = 0;
while ((line = br.readLine()) != null) {
for (int col = 0; col < line.length(); col++) {
final char c = line.charAt(col);
map[row][col] = c == WALL;
dijkstra[row][col] = Integer.MAX_VALUE;
if (c == INDY) {
if (indy != null)
throw new IllegalStateException("Found a second indy!");
indy = new Indy(row, col);
} else if (c == GOAL) {
if (goal != null)
throw new IllegalStateException("Found a second treasure!");
goal = new Goal(row, col);
} else if (c == ROCK) {
}
}
row++;
}

updateDijkstra(goal.row, goal.col, 0, true);
} catch (final IOException ioe) {
throw new RuntimeException("Could not read maze from InputStream", ioe);
}
}

public int getShortestSolution() {
Maze ptr = this;
while (ptr.parent != null)
ptr = ptr.parent;
return ptr.shortestSolution;
}

public void setShortestSolution(int shortestSolution) {
Maze ptr = this;
while (ptr.parent != null)
ptr = ptr.parent;
ptr.shortestSolution = Math.min(ptr.shortestSolution, shortestSolution);
}

private final boolean isRepeat(final Maze maze) {
return this.visited.contains(maze);
}

private final void updateDijkstra(final int row, final int col, final int value, final boolean force) {
if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
return;
if (map[row][col] || isRockPresent(row, col))
return;
if (dijkstra[row][col] <= value && !force)
return;

dijkstra[row][col] = value;
updateDijkstra(row - 1, col, value + 1, false);
updateDijkstra(row + 1, col, value + 1, false);
updateDijkstra(row, col - 1, value + 1, false);
updateDijkstra(row, col + 1, value + 1, false);
}

private final void updateDijkstraGhost(final int row, final int col, final int value, final boolean force) {
if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
return;
if (map[row][col] || isRockPresent(row, col))
return;
if (dijkstraGhost[row][col] <= value && !force)
return;

dijkstraGhost[row][col] = value;
updateDijkstraGhost(row - 1, col, value + 1, false);
updateDijkstraGhost(row + 1, col, value + 1, false);
updateDijkstraGhost(row, col - 1, value + 1, false);
updateDijkstraGhost(row, col + 1, value + 1, false);
}

private final int dijkstraScore(final int row, final int col) {
if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
return Integer.MAX_VALUE;
return dijkstra[row][col];
}

private final int dijkstraGhostScore(final int row, final int col) {
if (dijkstraGhost == null) {
dijkstraGhost = new int[map.length][map[indy.row].length];
for (final int[] part : dijkstraGhost)
Arrays.fill(part, Integer.MAX_VALUE);
updateDijkstraGhost(goal.row, goal.col, 0, true);
}
if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
return Integer.MAX_VALUE;
return dijkstraGhost[row][col];
}

private boolean isRockPresent(final int row, final int col) {
for (final Rock rock : rocks)
if (rock.isAt(row, col))
return true;
return false;
}

public boolean isEmpty(final int row, final int col) {
if (row < 0 || col < 0 || row >= map.length || col >= map[row].length)
return false;
return !map[row][col] && !isRockPresent(row, col) && !goal.isAt(row, col);
}

public int solve() {
return solve(0);
}

private int solve(final int currentDepth) {
System.out.println(toString());
if (isSolved()) {
setShortestSolution(currentDepth);
return 0;
}
if (currentDepth >= getShortestSolution()) {
System.out.println("Aborting at depth " + currentDepth + " because we know better: "
+ getShortestSolution());
return Integer.MAX_VALUE;
}
final Map<Rock, Set<Direction>> nextTries = indy.getMoveableRocks();
int shortest = Integer.MAX_VALUE - 1;
for (final Map.Entry<Rock, Set<Direction>> tries : nextTries.entrySet()) {
final Rock rock = tries.getKey();
for (final Direction dir : tries.getValue()) {
final Maze next = new Maze(this, rock, dir);
if (!isRepeat(next)) {
final int nextSolution = next.solve(currentDepth + 1);
if (nextSolution < shortest)
shortest = nextSolution;
}
}
}
return shortest + 1;
}

public boolean isSolved() {
return indy.canReachTreasure();
}

@Override
public String toString() {
if (stringValue == null) {
final StringBuilder out = new StringBuilder();
for (int row = 0; row < map.length; row++) {
if (row == 0) {
out.append('\u250C');
for (int col = 0; col < map[row].length; col++)
out.append('\u2500');
out.append("\u2510\n");
}
out.append('\u2502');
for (int col = 0; col < map[row].length; col++) {
if (indy.isAt(row, col))
out.append('*');
else if (goal.isAt(row, col))
out.append("\$");
else if (isRockPresent(row, col))
out.append("@");
else if (map[row][col])
out.append('\u2588');
else
out.append(base64(dijkstra[row][col]));
}
out.append("\u2502\n");
if (row == map.length - 1) {
out.append('\u2514');
for (int col = 0; col < map[row].length; col++)
out.append('\u2500');
out.append("\u2518\n");
}
}
stringValue = out.toString();
}
return stringValue;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (!obj.getClass().equals(getClass()))
return false;
final Maze other = (Maze) obj;
if (other.map.length != map.length)
return false;
for (int row = 0; row < map.length; row++) {
if (other.map[row].length != map[row].length)
return false;
for (int col = 0; col < map[row].length; col++)
if (other.map[row][col] != map[row][col])
return false;
}
return indy.equals(other.indy) && rocks.equals(other.rocks) && goal.equals(other.goal);
}

@Override
public int hashCode() {
return getClass().hashCode() ^ indy.hashCode() ^ goal.hashCode() ^ rocks.hashCode();
}

private final class Goal extends PointOfInterest {
public Goal(final int row, final int col) {
super(row, col);
}
}

private final class Indy extends PointOfInterest {
public Indy(final int row, final int col) {
super(row, col);
}

public boolean canReachTreasure() {
return dijkstraScore(row, col) < Integer.MAX_VALUE;
}

public SortedMap<Rock, Set<Direction>> getMoveableRocks() {
final SortedMap<Rock, Set<Direction>> out = new TreeMap<>();
@SuppressWarnings("unchecked")
final Set<Direction> checked[][] = new Set[map.length][map[row].length];
lookForRocks(out, checked, row, col, null);
return out;
}

private final void lookForRocks(final Map<Rock, Set<Direction>> rockStore,
final Set<Direction>[][] checked,
final int row,
final int col,
final Direction comingFrom) {
if (row < 0 || col < 0 || row >= checked.length || col >= checked[row].length)
return;
if (checked[row][col] == null)
checked[row][col] = EnumSet.noneOf(Direction.class);
if (checked[row][col].contains(comingFrom))
return;
for (final Rock rock : rocks) {
if (rock.row == row && rock.col == col) {
if (rock.canBeMoved(comingFrom) && rock.isWorthMoving(comingFrom)) {
if (!rockStore.containsKey(rock))
rockStore.put(rock, EnumSet.noneOf(Direction.class));
}
return;
}
}
if (comingFrom != null)
for (final Direction dir : Direction.values())
if (comingFrom == null || dir != comingFrom.opposite())
if (isEmpty(row + dir.drow, col + dir.dcol) || isRockPresent(row + dir.drow, col + dir.dcol))
lookForRocks(rockStore, checked, row + dir.drow, col + dir.dcol, dir);
}
}

private final class Rock extends PointOfInterest implements Comparable<Rock> {
public Rock(final int row, final int col) {
super(row, col);
}

public boolean canBeMoved(final Direction direction) {
return isEmpty(row + direction.drow, col + direction.dcol);
}

public boolean isWorthMoving(final Direction direction) {
boolean worthIt = false;
boolean reachable = false;
int emptyAround = 0;
for (final Direction dir : Direction.values()) {
reachable |= (dijkstraScore(row, col) < Integer.MAX_VALUE);
emptyAround += (isEmpty(row + dir.drow, col + dir.dcol) ? 1 : 0);
if (dir != direction && dir != direction.opposite()
&& dijkstraScore(row + dir.drow, col + dir.dcol) < Integer.MAX_VALUE)
worthIt = true;
}
return (emptyAround < 4) && (worthIt || !reachable);
}

public int proximityIndice() {
final int ds = min(dijkstraScore(row - 1, col),
dijkstraScore(row + 1, col),
dijkstraScore(row, col - 1),
dijkstraScore(row, col + 1));
if (ds < Integer.MAX_VALUE)
return ds;
else
return min(dijkstraGhostScore(row - 1, col),
dijkstraGhostScore(row + 1, col),
dijkstraGhostScore(row, col - 1),
dijkstraGhostScore(row, col + 1));
}

@Override
public int compareTo(Rock o) {
return new Integer(proximityIndice()).compareTo(o.proximityIndice());
}
}

private static final char base64(final int i) {
if (i >= 0 && i <= 9)
return (char) ('0' + i);
else if (i < 36)
return (char) ('A' + (i - 10));
else
return ' ';
}

private static final int min(final int i1, final int i2, final int... in) {
int min = Math.min(i1, i2);
for (final int i : in)
min = Math.min(min, i);
return min;
}
}
``````
-

# Ruby - Huge & blostered

Somewhat naive implementation that brute-forces it's way through the labyrinth. It's not super fast in some (not so) weird cases. It can be improved by finding better heuristics than just "if it's closer to the treasure, we'll want to investigate first", but the general ideas are there.

It'll also show you how Indiana got his hands on the treasure in case he can, that's bonus.

``````EMPTY = '0'
WALL = '1'
INDY = '2'
GOAL = '3'
ROCK = '4'

map=%q|8 8
00001000
00000100
00000010
00000010
03004040
10000010
10000100
10000102|

def deep_dup(arr)
dupl = arr.dup
(0..dupl.size-1).to_a.each do |i|
dupl[i] = dupl[i].dup
end
return dupl
end

class Map
@@visited = []

def self.parse(str)
lines = str.split("\n")
mapdata = []
indy_r = -1
indy_c = -1
lines[1..-1].each_with_index do |line, idx|
row = ((mapdata ||= [])[idx] ||= [])
line.split(//).each_with_index do |c, cidx|
if c==INDY
indy_r = idx
indy_c = cidx
row[cidx] = EMPTY
else
row[cidx] = c
end
end
end
return Map.new(mapdata, indy_r, indy_c)
end

def initialize(mapdata, indy_r, indy_c, prev = nil, pushed = false)
@mapdata = mapdata
@mapdata.freeze
@mapdata.each {|x| x.freeze}
@indy_r = indy_r
@indy_c = indy_c
@prev = prev
@pushed = pushed
end

def visit!
@@visited << self
end

def visited?
@@visited.include?(self)
end

def pushes
pushes = @pushed ? 1 : 0
if @prev
pushes += @prev.pushes
end
return pushes
end

def history
return @prev ? 1+@prev.history : 0
end

def next_maps
maps = []
[[-1, 0], [1, 0], [0, -1], [0, 1]].each do |dr, dc|
new_i_r = self.indy_r + dr
new_i_c = self.indy_c + dc
if new_i_r >= 0 && new_i_r < @mapdata.size && new_i_c >= 0 && new_i_c < @mapdata[0].size
new_map = nil
pushed = false
case @mapdata[new_i_r][new_i_c]
when EMPTY, GOAL then new_map = @mapdata
when ROCK then
if @mapdata[new_i_r+dr] && @mapdata[new_i_r+dr][new_i_c+dc] == EMPTY
new_map = deep_dup(@mapdata)
new_map[new_i_r][new_i_c] = EMPTY
new_map[new_i_r+dr][new_i_c+dc] = ROCK
pushed = true
end
end
if new_map && !@@visited.include?(new_map = Map.new(new_map, new_i_r, new_i_c, self, pushed))
maps << new_map
end
end
end
return maps
end

def wins?
return @mapdata[@indy_r][@indy_c] == GOAL
end

def to_s
str = ''
@mapdata.each_with_index do |row, r|
row.each_with_index do |col, c|
if r == @indy_r and c == @indy_c then
str += 'I'
else
case col
when EMPTY then str += '_'
when WALL then str+= '#'
when ROCK then str += 'O'
when GOAL then str += '\$'
end
end
end
str += "\n"
end
return str
end

def ==(other)
return (self.mapdata == other.mapdata) &&
(self.indy_r == other.indy_r) &&
(self.indy_c == other.indy_c)
end

def dist_to_treasure
if @distance.nil?
@mapdata.each_with_index do |r, ri|
r.each_with_index do |c, ci|
if c == GOAL
@distance = Math.sqrt((ri - @indy_r)**2 + (ci - @indy_c)**2)
return @distance
end
end
end
end
return @distance
end

def <=>(other)
dist_diff = self.dist_to_treasure <=> other.dist_to_treasure
if dist_diff != 0
return dist_diff
else
return self.pushes <=> other.pushes
end
end
end

scored = nil
root = Map.parse(map)
to_visit = [root]
until to_visit.empty?
state = to_visit.pop
next if state.visited?
if state.wins? && (scored.nil? || scored.pushes > state.pushes)
scored = state
end
state.visit!
to_visit += state.next_maps
to_visit.reject! {|x| x.visited? || (scored && scored.pushes <= x.pushes) }
to_visit.sort!
to_visit.reverse!
end

puts scored ? scored.pushes : 'X'
exit(0) unless scored
steps = [scored]
curr = scored
while curr = curr.prev
steps << curr
end
puts "\nDetails of the path:"
steps.reverse.each_with_index do |step, idx|
puts "Step ##{idx} (history: #{step.history}, pushes so far: #{step.pushes})"
puts step
puts
end
``````

Edit: I though of ways to possibly greatly improve the performance of this in non-obvious situations (where it currently sucks green eggs) by dropping simple movement evaluation (e.g. only care about when indy pushes rocks and/or gets to the treasure). I'll probably update the code later, once I've had time to implement.

-