Récit

Indiana Jones explorait une grotte où se trouve un trésor précieux. Soudainement, un tremblement de terre s'est produit.

À la fin du tremblement de terre, il s’aperçut que des rochers tombés du plafond lui bloquaient le chemin vers le trésor. Il a également remarqué qu'il pouvait pousser une pierre, mais comme les pierres étaient très lourdes, il ne pouvait pas pousser deux pierres consécutives .

Votre objectif est d'aider Indiana Jones à obtenir le trésor. Comme il est très difficile de pousser même une seule pierre, le nombre de poussées est très important.

Problème

Trouvez le meilleur moyen (où Indiana Jones pousse le moins possible les pierres) pour trouver le trésor.

Carte (entrée)

La carte est une matrice mde n(plus que 1) pouvant contenir cinq types de cellules:

• 0 ce qui signifie la cellule vide,
• 1 ce qui signifie le mur,
• 2 dans lequel se trouve Indiana Jones (un seul existe),
• 3 dans lequel se trouve le trésor (un seul existe),
• et 4, ce qui signifie un rocher.

Dans la première ligne de la carte, la dimension de la carte est spécifiée comme 4 6, et de la deuxième ligne à la dernière ligne de la carte, la structure de la grotte est spécifiée à peu près comme ceci.

110131
104040
100101
200000

Par conséquent, la carte complète est:

4 6
110131
104040
100101
200000

ce qui signifie

La carte est donnée par stdin, un fichier (vous pouvez spécifier le nom du fichier) ou un tableau dans le code contenant uniquement les informations ci-dessus.

Sortie

Le montant minimum qu'Indiana Jones devrait pousser. S'il n'y a pas moyen, sortie X.

Dans le cas ci-dessus , il peut pousser une pierre dans la gauche vers le haut, puis il peut pousser une pierre dans la droite pour récupérer le trésor. Par conséquent, la sortie dans ce cas est 2.

Toutefois. dans ce cas :

4 6
111131
104040
100101
200000

(voir section ci-dessous) il ne peut pas pousser la pierre droite car elle détruira le trésor. De plus, pousser la pierre de gauche à droite ne change rien. Par conséquent, la sortie est X.

Règles

• Il ne peut se déplacer que dans quatre directions: haut, bas, gauche et droite.
• Il ne peut pas pousser deux pierres consécutives .
• Il ne peut tirer aucune pierre et il ne peut pousser une pierre que dans une seule direction («en avant»).
• Il ne peut pas traverser les murs. Seuls les endroits où il peut aller sont les cellules vides et la cellule de trésor.
• La pierre ne peut pas être placée sur le trésor. Cela va détruire le trésor. :(
• Il ne peut pas sortir de la carte.

Buts

Programme qui peut gérer le plus grand nombre de cartes (fourni à la section «Exemple» + autres) dans un délai raisonnable (plus précisément, 10 secondes) et produit la bonne réponse gagne.

Ici, 'autres' signifie des exemples d'entrées fournies dans les réponses. Cela signifie que vous devez créer un algorithme intelligent afin que d'autres programmes ne puissent pas résoudre les cartes que votre programme peut résoudre, et les cartes résolues par d'autres programmes peuvent être résolues par votre programme. Cependant, mettre des solutions dans le code ne sera pas considéré comme valide.

Remarque

C'était à l'origine un projet à mi-parcours d'une classe d'IA que j'ai écouté, une seule chose était différente: on disait qu'il n'y avait que deux roches.

Il a été dit que ce problème est NP, mais il a également été dit qu'un bon algorithme heuristique peut résoudre le problème assez efficacement. J'ai utilisé des idées et des méthodes heuristiques pour résoudre le problème efficacement et mon code a pu trouver toutes les solutions d'échantillons très rapidement (moins d'une seconde).

Cependant, quand il y avait plus de deux roches, il y avait des cas où le code ne pouvait pas trouver la réponse dans un délai raisonnable. J'avais des idées, mais certaines étaient "fausses" et je ne pouvais pas exprimer d'autres idées dans le code. Je voulais voir quels algorithmes intelligents existent pour résoudre ce problème, alors j'ai écrit ceci.

Depuis que j'ai déjà terminé le projet (d'ailleurs, les images ne sont pas les miennes - je les ai trouvées sur Google), vous n'avez pas à vous en préoccuper.

Exemples

Des exemples peuvent être vus ici. Vous pouvez également voir des exemples et tester vos résultats ici (cela devrait fonctionner dans les navigateurs modernes). Vous pouvez obtenir la carte dans le format décrit ci-dessus en tapant whatisthis()dans la console JS.

http://bit.sparcs.org/~differ/sokoban/#0 ~ http://bit.sparcs.org/~differ/sokoban/#19 contient des exemples dont il s'agissait à l'origine de la classe fournie.

Résultat

Désolé, j'étais en retard ... beaucoup en fait. : P (j'étais trop paresseux pour marquer. Désolé.)

Voici le résultat. (X: faux, O: correct,?: Prend au moins 10 secondes, arrêté)

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: a pris 25 secondes, le résultat était correct.) (J'ai utilisé ruby ​​1.9.3 et javac 1.7.0_13)

Il semble que l'algorithme Java était effectivement meilleur. (Au fait, j'ai pensé à une méthode similaire, mais je me suis rendu compte que des cartes similaires à la carte test 5 existent.)

Java - Un peu plus intelligent / plus rapide

Un peu de code là-bas. Je tente d’être plus rapide en évaluant les poussées dans l’ordre suivant: "quelle est la probabilité que cela libère un chemin vers le trésor", qui est lui-même basé sur deux traversées de Dijkstra (l’une s’arrête lorsque vous rencontrez des rochers, l’autre ignore les rochers). Cela fonctionne plutôt bien, et l'exemple de la commande pastebin qui semble gênant pour l'auteur est résolu en 2 secondes environ par cette implémentation. Certains autres exemples prennent jusqu'à 30 à 40 secondes, ce que je trouve encore trop long, mais je ne pouvais pas trouver un moyen d'améliorer cela sans casser des trucs :)

J'ai divisé mes données en plusieurs fichiers pour obtenir une meilleure structure (et pourquoi je suis passé de Java à Ruby):

Point d'accès:

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());
    }
}

Enum assistant de direction:

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;
    }
}

Une classe abstraite pour représenter une partie localisée du "labyrinthe":

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;
    }
}

Et enfin, le labyrinthe lui-même:

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;
    }
}

Ruby - Énorme et bloster

Une mise en œuvre quelque peu naïve qui force brute son chemin à travers le labyrinthe. Ce n'est pas très rapide dans certains cas (pas si) étranges. Il peut être amélioré en trouvant de meilleures heuristiques que simplement "si c'est plus proche du trésor, nous voudrons étudier en premier", mais les idées générales sont là.

Cela vous montrera également comment Indiana a mis la main sur le trésor au cas où il le pourrait, c'est un 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: J’ai trouvé un moyen d’améliorer considérablement les performances de cette situation dans des situations non évidentes (où elle aspire actuellement des œufs verts) en laissant tomber une simple évaluation du mouvement (par exemple, ne vous souciez que du moment où l’indy pousse des rochers et / ou va au trésor). Je mettrai probablement le code à jour plus tard, une fois que j'aurai eu le temps de le mettre en œuvre.

C ++ 14 sur 16

L'algorithme est inefficace et gourmand en mémoire. De plus, je ne pouvais pas me permettre le temps de tout ranger, mais je le ferai quand j'ai plus de temps;) Un point intéressant est que mon algorithme échoue aux mêmes cartes de test que le questionneur. Sur mon ancien carnet de notes, le processus commence par la permutation des cartes T4 et T6. La carte 3 prend beaucoup de temps, mais se résout dans le temps. Tous les autres sont résolus presque instantanément. Je vais donc devoir comprendre comment résoudre T4 et T6 et essayer l'algorithme sur une machine disposant de plus de mémoire. Finalement, je peux résoudre T4 et T6. Je garderai le message à jour ...

Voici le résultat. (X: faux, O: correct,?: Prend au moins 10 secondes, arrêté)

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

Comme le code source est assez long et pas très agréable à lire ... En gros, il ne recherche que tous les rochers pouvant être atteints par Indiana Jones. Pour les roches pouvant être atteintes, il stocke les informations dans lesquelles il peut être déplacé. Ainsi, une liste de déplacements possibles pour la carte actuelle est créée. Pour chacun de ces déplacements possibles, une copie de la carte est créée et le déplacement est appliqué. Pour les cartes nouvellement créées, l'algorithme vérifie à nouveau quels mouvements peuvent être appliqués ... Ceci est fait jusqu'à ce que plus aucun mouvement ne soit possible ou jusqu'à ce qu'un chemin vers le coffre au trésor soit trouvé. Lorsque l'algorithme tente d'abord tous les mouvements qui ne prendraient qu'un mouvement pour atteindre la poitrine, tous ceux qui en prendraient deux, et ainsi de suite ... le premier moyen trouvé est aussi automatiquement le plus court. Pour éviter les boucles, l’algorithme mémorise pour chaque carte les déplacements pouvant être appliqués. Si une autre carte crée une liste de déplacements déjà trouvés auparavant, ils sont supprimés en mode silencieux car ils sont déjà en cours de traitement. Malheureusement, il n'est pas possible d'exécuter chaque mouvement une seule fois, car il se peut que certaines cartes nécessitent de déplacer une roche plusieurs fois sur le même champ. Sinon, je pourrais économiser beaucoup de mémoire. En plus de résoudre des cartes telles que la carte 3 dans le temps, l'algorithme ignore toutes les roches qui peuvent être parcourues ... Ainsi, sur la carte 3, la roche au milieu de nulle part sera déplacée, mais jusqu'à ce qu'il n'y ait plus de murs autour. Le code peut être compilé avec g ++ --std = c ++ 0x avec g ++ version 4.4.3 ou plus récente. s Il n’est pas possible d’exécuter chaque mouvement une seule fois, car il se peut que certaines cartes nécessitent de déplacer plusieurs fois une pierre sur le même champ. Sinon, je pourrais économiser beaucoup de mémoire. En plus de résoudre des cartes telles que la carte 3 dans le temps, l'algorithme ignore toutes les roches qui peuvent être parcourues ... Ainsi, sur la carte 3, la roche au milieu de nulle part sera déplacée, mais jusqu'à ce qu'il n'y ait plus de murs autour. Le code peut être compilé avec g ++ --std = c ++ 0x avec g ++ version 4.4.3 ou plus récente. s Il n’est pas possible d’exécuter chaque mouvement une seule fois, car il se peut que certaines cartes nécessitent de déplacer plusieurs fois une pierre sur le même champ. Sinon, je pourrais économiser beaucoup de mémoire. En plus de résoudre des cartes telles que la carte 3 dans le temps, l'algorithme ignore toutes les roches qui peuvent être parcourues ... Ainsi, sur la carte 3, la roche au milieu de nulle part sera déplacée, mais jusqu'à ce qu'il n'y ait plus de murs autour. Le code peut être compilé avec g ++ --std = c ++ 0x avec g ++ version 4.4.3 ou plus récente. mais seulement jusqu'à ce qu'il n'y ait plus de murs autour. Le code peut être compilé avec g ++ --std = c ++ 0x avec g ++ version 4.4.3 ou plus récente. mais seulement jusqu'à ce qu'il n'y ait plus de murs autour. Le code peut être compilé avec g ++ --std = c ++ 0x avec g ++ version 4.4.3 ou plus récente.

#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: le programme tire son entrée de stdin et ignore la première ligne contenant la taille de la carte. Il vérifie si seuls les caractères autorisés sur la carte sont utilisés, mais ne vérifie pas qu'il n'y ait qu'un seul Indiana Jones et un seul coffre au trésor. Il est donc possible de placer plus d'un mouvement et le moins de mouvements requis pour atteindre l'un des coffres est imprimé sur la sortie standard. Tous les caractères non valides de la carte sont ignorés et le programme essaiera de calculer le moins de déplacements possible pour la carte obtenue. Le calcul commence lorsque stdin est fermé (sur mon système, ctrl + d).