# Help Indiana Jones to get the treasure

## Story

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

When the earthquake ended, he noticed that some rocks that had fallen 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 objective is to help Indiana Jones 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 pushes stones as little as possible), to find the treasure.

## Map (input)

The map is an m by n (both larger than 1) matrix which can contain 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 a 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 the most maps (provided at the 'Example' section + others) in a reasonable time (specifically, 10 seconds) and outputs the right answer wins.

Here 'others' means example inputs provided in answers. This means you should make a smart algorithm so that other programs can't solve maps that 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 were only two rocks.

It was said that this problem is NP, but it was also said that a 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 were 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 (this should work in modern browsers). 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 of a similar method, but I realized that maps like test map 5 exist.)

• That's a difficult one. Dec 3, 2011 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... :) Apr 25, 2012 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, 2012 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, 2012 at 10:15

# 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 = []
attr_reader :mapdata, :indy_r, :indy_c, :prev

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 ? [email protected] : 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. ## 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.io.InputStreamReader; 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 rocks.add(new Rock(r.row, r.col)); updateDijkstra(goal.row, goal.col, 0, true); } public Maze(final InputStream is) { this.parent = null; this.visited = new HashSet<>(); try (final BufferedReader br = new BufferedReader(new InputStreamReader(is))) { String line = br.readLine(); 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) { rocks.add(new Rock(row, col)); } } 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()); visited.add(this); 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));
rockStore.get(rock).add(comingFrom);
}
return;
}
}
if (comingFrom != null)
checked[row][col].add(comingFrom);
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;
}
}


## C++ 14 out of 16

The algorithm is inefficient and memory hungry. Additionally I couldn't afford the time to tidy it up, but I will when I have more time ;) An interesting point is that my algorithm fails at the same test maps as the questioner's. On my ancient notebook the process starts swapping for the T4 and T6 maps. Map 3 takes quite long, but is solved in time. All others are solved nearly instant. So I'll have to figure out how to solve T4 and T6 and try the algorithm on a machine with more memory. Eventually I can solve T4 and T6 there. I'll keep the post updated...

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
C++  (foobar): O O O O O O  O  O  O  O  O  O  ?  O  ?  O
Ruby (Romain): X O O ? O O  O  X  ?  ?  O  ?  ?  ?  ?  ?
Java (Romain): O O X O X X  O  O  ?  ?  O  O  O  X  O  O


As the source code is quite long and not really nice to read... Basically it just looks for all rocks that can be reached by Indiana Jones. For the rocks that can be reached, it stores the information into which directions it can be moved. So a list of possible moves for the current map is created. For each of these possible moves a copy of the map is created and the move applied. For the newly created maps, the algorithm will check again which moves can be applied... This is done until either no further moves are possible or a way to the treasure chest is found. As the algorithm first tries all moves that would only take one movement to reach the chest, then all that would take two, and so on... the first way found is also automatically the shortest. To prevent loops, the algorithm remembers for every map what moves could be applied. If another map is created that results in a list of moves that were already found before, then they're silently dropped, as they're already being processed. Unfortunately it's not possible to execute every move only once, as there could be maps that require a rock to be moved over the same field several times. Otherwise I could save a lot of memory. Additionally to solve maps like map 3 in time, the algorithm ignores all rocks that can be walked around... So on map 3 the rock in the middle of nowhere will be moved around, but only until there are no more walls around it. The code can be compiled with g++ --std=c++0x with g++ version 4.4.3 or newer.

#include <vector>
#include <iostream>
#include <iterator>
#include <sstream>
#include <unordered_set>
#include <utility>

enum class dir : char {
up, down, left, right
};

enum class field : char {
floor, wall, indiana, treasure, rock, border, visited
};

class pos {
private:
int x, y;
field f_type;

public:
pos() : x{-1}, y{-1}, f_type{field::border} {}
pos(int x, int y, field f_type) : x{x}, y{y}, f_type{f_type} {}

const field& get() {
return f_type;
}

friend class map;
friend class move;

bool operator==(const pos& other) const {
return x == other.x && y == other.y && f_type == other.f_type;
}
};

class move {
private:
pos position;
dir direction;

public:
move(pos& position, dir&& direction) : position(position), direction(direction) {}

bool operator==(const move& other) const {
return position == other.position && direction == other.direction;
}

int int_value() const {
return static_cast<char>(direction) + position.x + position.y + static_cast<char>(position.f_type);
}

std::string str() const;

friend class map;
};

std::string move::str() const {
std::string direction_str;
switch(direction) {
case dir::up: direction_str = "up"; break;
case dir::down: direction_str = "down"; break;
case dir::left: direction_str = "left"; break;
case dir::right: direction_str = "right"; break;
}
std::ostringstream oss{};
oss << "move x" << position.x << " y" << position.y << " " << direction_str;
return oss.str();
}

std::ostream& operator<<(std::ostream& os, const move& move_object) {
return os << move_object.str();
}

namespace std {
template<> struct hash< ::move> {
size_t operator()(const ::move& o) const {
return hash<int>()(o.int_value());
}
};
}

class constellation {
private:
const std::unordered_set<move> moves;

public:
constellation(const std::unordered_set<move>& moves) : moves(moves) {}

bool operator==(const constellation& other) const {
if (moves.size() != other.moves.size()) return false;
for (auto i = moves.begin(); i != moves.end(); ++i) {
if (!other.moves.count(*i)) return false;
}
return true;
}

int int_value() const {
int v = 0;
for (auto i = moves.begin(); i != moves.end(); ++i) {
v += i->int_value();
}
return v;
}
};

namespace std {
template<> struct hash< ::constellation> {
size_t operator()(const ::constellation& o) const {
return hash<int>()(o.int_value());
}
};
}

class map {

private:
pos* previous;
pos start, border;
std::vector< std::vector<pos> > rep;
void init(const std::string&);

public:
map(std::istream& input) : previous{} {
init(static_cast<std::stringstream const&>(std::stringstream() << input.rdbuf()).str());
}

map& move(const move& m) {
pos source = m.position;
pos& target = get(source, m.direction);
target.f_type = source.f_type;
source.f_type = field::indiana;
rep[start.y][start.x].f_type = field::floor;
start = source;
rep[start.y][start.x].f_type = field::indiana;
return *this;
}

std::string str() const;

pos& get() { return start; }

pos& get(pos& position, const dir& direction) {
int tx = position.x, ty = position.y;
switch(direction) {
case dir::up: --ty; break;
case dir::down: ++ty; break;
case dir::left: --tx; break;
case dir::right: ++tx; break;
}
previous = &position;
if (tx >= 0 && ty >= 0 && static_cast<int>(rep.size()) > ty && static_cast<int>(rep[ty].size()) > tx) {
pos& tmp = rep[ty][tx];
return tmp;
}
border.x = tx;
border.y = ty;
return border;
}

pos& prev() {
return *previous;
}

void find_moves(std::unordered_set< ::move>& moves, bool& finished) {
map copy = *this;
auto& rep = copy.rep;
bool changed = true;

while (changed) {
changed = false;
for (auto row = rep.begin(); row != rep.end(); ++row) {
for (auto col = row->begin(); col != row->end(); ++col) {
// check if the field is of interest
if (col->f_type == field::floor || col->f_type == field::treasure || col->f_type == field::rock) {
// get neighbours
pos& up = copy.get(*col, dir::up);
pos& down = copy.get(*col, dir::down);
pos& left = copy.get(*col, dir::left);
pos& right = copy.get(*col, dir::right);
// ignore uninteresting rocks
if (col->f_type == field::rock && (up.f_type == field::floor || up.f_type == field::indiana || up.f_type == field::visited) && (down.f_type == field::floor || down.f_type == field::indiana || down.f_type == field::visited) && (left.f_type == field::floor || left.f_type == field::indiana || left.f_type == field::visited) && (right.f_type == field::floor || right.f_type == field::indiana || right.f_type == field::visited)) {
pos& upper_left = copy.get(up, dir::left);
pos& lower_left = copy.get(down, dir::left);
pos& upper_right = copy.get(up, dir::right);
pos& lower_right = copy.get(down, dir::right);
if ((upper_left.f_type == field::floor || upper_left.f_type == field::indiana || upper_left.f_type == field::visited) && (lower_left.f_type == field::floor || lower_left.f_type == field::indiana || lower_left.f_type == field::visited) && (upper_right.f_type == field::floor || upper_right.f_type == field::indiana || upper_right.f_type == field::visited) && (lower_right.f_type == field::floor || lower_right.f_type == field::indiana || lower_right.f_type == field::visited)) {
continue;
}
}
// check if the field can be reached
if (up.f_type == field::visited || up.f_type == field::indiana) {
if (col->f_type == field::rock && (down.f_type == field::visited || down.f_type == field::floor || down.f_type == field::indiana)) {
auto insertion = moves.insert( ::move(*col, dir::down));
if (insertion.second) {
changed = true;
}
}
else if (col->f_type == field::floor) {
changed = true;
col->f_type = field::visited;
}
else if (col->f_type == field::treasure) {
finished = true;
return;
}
}
if (down.f_type == field::visited || down.f_type == field::indiana) {
if (col->f_type == field::rock && (up.f_type == field::visited || up.f_type == field::floor || up.f_type == field::indiana)) {
auto insertion = moves.insert( ::move(*col, dir::up));
if (insertion.second) {
changed = true;
}
}
else if (col->f_type == field::floor) {
changed = true;
col->f_type = field::visited;
}
else if (col->f_type == field::treasure) {
finished = true;
return;
}
}
if (left.f_type == field::visited || left.f_type == field::indiana) {
if (col->f_type == field::rock && (right.f_type == field::visited || right.f_type == field::floor || right.f_type == field::indiana)) {
auto insertion = moves.insert( ::move(*col, dir::right));
if (insertion.second) {
changed = true;
}
}
else if (col->f_type == field::floor) {
changed = true;
col->f_type = field::visited;
}
else if (col->f_type == field::treasure) {
finished = true;
return;
}
}
if (right.f_type == field::visited || right.f_type == field::indiana) {
if (col->f_type == field::rock && (left.f_type == field::visited || left.f_type == field::floor || left.f_type == field::indiana)) {
auto insertion = moves.insert( ::move(*col, dir::left));
if (insertion.second) {
changed = true;
}
}
else if (col->f_type == field::floor) {
changed = true;
col->f_type = field::visited;
}
else if (col->f_type == field::treasure) {
finished = true;
return;
}
}
}
}
}
}
}

};

void map::init(const std::string& in) {
bool first = true;

for(auto i = in.begin(); i != in.end(); ++i) {
if (*i == '\n') {
first = false;
rep.push_back({});
continue;
}
else if (first) continue;

field tmp(static_cast<field>(*i - '0'));
pos current(rep.back().size(), rep.size() - 1, tmp);
switch(tmp) {
case field::indiana:
start = current;
case field::floor:
case field::wall:
case field::treasure:
case field::rock:
rep.back().push_back(current);
break;
default: std::cerr << "Invalid field value '" << (char) (static_cast<char>(tmp) + 48) << '\'' << std::endl;
}
}
}

std::string map::str() const {
std::string t{};
for (auto row = rep.begin(); row != rep.end(); ++row) {
for (auto col = row->begin(); col != row->end(); ++col) {
t += static_cast<char>(col->f_type) + '0';
}
t += '\n';
}
return t;
}

std::ostream& operator<<(std::ostream& os, const map& map_object) {
return os << map_object.str();
}

int solve(map&& data) {
int moves_taken = -1;
bool finished = false;
std::vector<map> current_maps{data}, next_maps;
std::unordered_set<constellation> known_constellations;

while (!finished && !current_maps.empty()) {
for (auto i = current_maps.begin(); i != current_maps.end(); ++i) {
std::unordered_set<move> moves;
i->find_moves(moves, finished);
auto result = known_constellations.insert(constellation(moves));
if (!result.second) {
continue; // this map constellation was already seen. prevent loops...
}

if (finished) break;
for (auto m = moves.begin(); m != moves.end(); ++m) {
map map_copy = *i;
map_copy.move(*m);
next_maps.push_back(map_copy);
}

}
++moves_taken;
current_maps = std::move(next_maps);
}
if (!finished && current_maps.empty()) return -1;
return moves_taken;
}

int main(int argc, char* argv[]) {
map data{std::cin};

int moves_taken = solve(std::move(data));
if (moves_taken == -1) std::cout << "X" << std::endl;
else std::cout << moves_taken << std::endl;

return 0;
}


Edit: The program takes its input from stdin and ignores the first line containing the size of the map. It checks if only allowed characters in the map are used, but doesn't verify that there's only one Indiana Jones and one treasure chest. So it's possible to place more than one and the least moves required to reach one of the chests is printed to stdout. Any invalid characters in the map are skipped and the program will try to calculate the least amount of moves for the resulting map. The calculation will start when stdin is closed (on my system ctrl + d).

• Nice resurrection :). It's always fun to see a clever heuristic. Mar 29, 2014 at 13:34
• I'm kind of sad about my upvote. It pushed your reputation 10 higher than a perfect 1000 Jul 29, 2017 at 20:40