15

Considérons un graphique quadrillé n par n qui ressemble à ceci.

graphique en grille

Il est important de noter que ce graphique est 11 par 11 .

À un moment donné, un homme se tient à une intersection et il ne se déplace que verticalement ou horizontalement d'un pas à la fois jusqu'à la prochaine intersection. Malheureusement, il a un peu trop bu alors il choisit la direction dans laquelle il se déplace au hasard parmi les 4 directions possibles (haut, bas, gauche, droite). Cela peut aller jusqu'à 4 comme s'il se tenait contre un mur, il n'a bien sûr que 3 options et dans un coin, il n'en a que 2.

Il commence dans le coin inférieur gauche et son objectif est de rentrer à la maison qui est le coin supérieur droit. Le temps est simplement le nombre de pas qu'il lui faut.

Cependant, vous êtes un adversaire malveillant qui veut qu'il rentre le plus lentement possible. Vous pouvez supprimer n'importe quel nombre d'arêtes du graphique à tout moment pendant sa marche. La seule restriction est que vous devez toujours lui laisser un moyen de rentrer à la maison et vous ne pouvez pas supprimer un bord qu'il a déjà utilisé.

Le défi consiste à imaginer un adversaire aussi malveillant que possible, puis à le tester sur un graphique ~~100~~ x ~~100~~ 20 x 20 avec un marcheur ivre au hasard. Votre score est simplement le temps moyen qu'il faut au marcheur aléatoire pour rentrer à la maison sur 10 1000 courses.

Vous pouvez utiliser n'importe quelle langue et bibliothèque que vous aimez tant qu'elles sont librement disponibles et facilement installables sous Linux.

De quoi ai-je besoin pour mettre en œuvre?

Vous devez implémenter du code pour le marcheur aléatoire et également pour l'adversaire et le code doit être combiné de sorte que la sortie lors de l'exécution soit simplement la moyenne de 1000 exécutions en utilisant votre code d'adversaire. Le code du marcheur aléatoire devrait être très simple à écrire car il choisit simplement parmi (x-1, y), (x + 1, y), (x, y-1) et (x, y + 1) en s'assurant que aucun de ceux-ci n'a été supprimé ou est hors de portée.

Le code de l'adversaire est bien sûr plus difficile et doit également se souvenir des bords que l'ivrogne a déjà traversés pour qu'il n'essaie pas de supprimer l'un d'eux et de s'assurer qu'il y a toujours un chemin de retour pour l'ivrogne, ce qui est un peu plus délicat. faire vite.

L'addendum 10 ne suffit pas, mais je ne voulais pas punir les gens qui ont réussi à faire de très longues promenades. Je l'ai maintenant augmenté à 1000 en raison d'une demande populaire. Cependant, si votre marche est si longue que vous ne pouvez pas faire 1000 pistes en un temps réaliste, veuillez simplement indiquer le nombre maximum de pistes que vous pouvez.

Tableau des meilleurs scores pour 100 par 100.

976124.754 par Optimizer.
103000363.218 par Peter Taylor.

Modifier 1. Changement de la taille du graphique à 20 par 20 pour aider à la durée des tests des personnes. Je ferai un nouveau score de table élevé pour cette taille lorsque les gens soumettront les scores.

Tableau des meilleurs scores pour 20 par 20.

230,794.38 (100k runs) by justhalf
227,934 by Sparr 
213,000 (approx) by Peter Taylor
199,094.3 by stokastic
188,000 (approx) by James_pic
 64,281 by Geobits

code-challenge graph-theory
la source

2

Je ne comprends pas; ne pouvez-vous pas simplement supprimer tous les bords au début, sauf ceux qui forment le chemin le plus long?

Peter Olson

3

Je ne vois aucune règle montrant que l'ivrogne ne peut pas re-marcher deux fois le même bord. S'il peut emprunter deux fois le même chemin entre deux points et choisit des virages au hasard, alors le graphique avec la moyenne (aléatoire) la plus longue n'est-il pas celui qui a le plus d'arêtes? Autrement dit, le graphique optimal (le plus long) ne serait-il pas celui sans arêtes supprimées?

millinon

3

Je ne suis pas fan d'exiger que chaque entrée réinvente la roue (déambulateur). Si quelqu'un publie un faisceau / cadre de test, je les voterai et je les utiliserai.

Sparr

1

L'avantage de retirer une partie d'un chemin pour le faire revenir en arrière pour parcourir le long chemin est complètement perdu lorsque son chemin est aléatoire; soi-disant, il est tout aussi probable qu'il revienne à un moment donné sans que vous ayez besoin d'enlever un bord. J'aimerais voir des données de test montrant le temps moyen sans aucun bord supprimé, puis avec certains bords supprimés comme vous semblez le suggérer. En ce qui concerne ce défi, je pense qu'il serait beaucoup plus intéressant si le chemin de l'ivrogne était déterministe.

millinon

3

10 tours n'est pas suffisant. Même avec un labyrinthe statique de 10x10, sans parler d'un adversaire intelligent et d'un labyrinthe de 100x100, l'écart-type est d'environ 50% du cas moyen. Je fais 10000 tours et je ne considère toujours pas les résultats comme dignes de comparaison.

Sparr

10

230 794,38 sur 20x20, 100 000 courses

Dernière mise à jour: j'ai finalement créé une solution dynamique parfaite à 2 voies. J'ai dit parfait car la version précédente n'est en fait pas symétrique, il était plus facile d'obtenir un chemin plus long si l'ivrogne a pris un chemin par rapport à l'autre. L'actuel est symétrique, il peut donc obtenir un plus grand nombre attendu d'étapes. Après quelques essais, il semble être d'environ 230k, une amélioration par rapport au précédent qui est d'environ 228k. Mais statistiquement parlant, ces chiffres sont toujours dans leur écart énorme, donc je ne prétends pas que ce soit nettement mieux, mais je pense que cela devrait être mieux que la version précédente.

Le code est au bas de cet article. Il est mis à jour pour être beaucoup plus rapide que la version précédente, effectuant 1000 exécutions en 23 secondes.

Ci-dessous, un échantillon et un labyrinthe d'échantillons:

Perfect Walker
Moyenne: 230794.384
Max: 1514506
Min: 25860
Terminé en 2317.374s
 _ _ _ _ _ _ _ _ _ _ _ _ _. 
| | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | _ | | _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | _ | | _ | | _ | | _ | | _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ | | _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Soumissions précédentes

Enfin, je peux égaler le résultat de Sparr! = D

Sur la base de mes expériences précédentes (voir en bas de cet article), la meilleure stratégie consiste à avoir un double chemin et à en fermer un lorsque l'ivrogne atteint l'un d'eux, et la variable vient de la façon dont nous pouvons prédire dynamiquement où l'ivrogne ira. augmenter les chances de lui de prendre un chemin plus long.

Donc, basé sur ma DOUBLE_PATHstratégie, j'en ai construit un autre, qui change le labyrinthe (mon DOUBLE_PATHlabyrinthe était facilement modifiable) en fonction du mouvement de l'ivrogne. Comme il emprunte un chemin avec plus d'une option disponible, je vais fermer les chemins afin de ne laisser que deux options possibles (dont une d'où il vient, une autre non explorée).

Cela ressemble à ce que Sparr a réalisé, comme le montre le résultat. La différence avec la sienne est trop petite pour qu'elle soit considérée comme meilleure, mais je dirais que mon approche est plus dynamique que lui, car mon labyrinthe est plus modifiable que celui de Sparr =)

Le résultat avec un échantillon de labyrinthe final:

EXTREME_DOUBLE_PATH
Moyenne: 228034.89
Max: 1050816
Min: 34170
Terminé en 396.728s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Section Expériences

Le meilleur se révèle être la même stratégie que stokastic, je suis fier d'expérimenter en utilisant différentes stratégies et d'imprimer de belles sorties :)

Chacun des labyrinthes imprimés ci-dessous est le dernier labyrinthe après que l'ivrogne est arrivé à la maison, ils peuvent donc être légèrement différents d'une course à l'autre en raison du caractère aléatoire du mouvement de l'ivrogne et de la dinamicité de l'adversaire.

Je décrirai chaque stratégie:

Chemin unique

Il s'agit de l'approche la plus simple, qui créera un chemin unique de l'entrée à la sortie.

SINGLE_PATH
Moyenne: 162621.612
Max: 956694
Min: 14838
Terminé en 149.430s
 _ _ _ _ _ _ _ _ _ _
| | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Île (niveau 0)

Il s'agit d'une approche qui tente de piéger l'ivrogne dans une île presque isolée. Ne fonctionne pas aussi bien que prévu, mais c'est une de mes premières idées, donc je l'inclus.

Il y a deux chemins menant à la sortie, et lorsque l'ivrogne se rapproche de l'un d'eux, l'adversaire la ferme, le forçant à trouver l'autre sortie (et peut-être à nouveau pris au piège dans l'île)

ÎLE
Moyenne: 74626.070
Max: 428560
Min: 1528
Terminé en 122,512s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Chemin double

C'est la stratégie la plus discutée, qui consiste à avoir deux chemins de longueur égale vers la sortie et à fermer l'un d'eux lorsque l'ivrogne se rapproche de l'un d'eux.

DOUBLE_PATH
Moyenne: 197743.472
Max: 1443406
Min: 21516
Terminé en 308.177s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Île (niveau 1)

Inspiré par les multiples chemins de l'île et le nombre élevé de promenades en un seul chemin, nous connectons l'île à la sortie et faisons un labyrinthe à un seul chemin dans l'île, créant au total trois chemins pour sortir, et comme dans le cas précédent, fermez l'un des sortir quand l'ivrogne s'approche.

Cela fonctionne légèrement mieux que le chemin simple pur, mais ne bat toujours pas le chemin double.

ÎLE
Moyenne: 166265.132
Max: 1162966
Min: 19544
Terminé en 471.982s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ | _
| | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |  
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Île (niveau 2)

En essayant d'élargir l'idée précédente, j'ai créé une île imbriquée, créant au total cinq chemins, mais cela ne semble pas bien fonctionner.

ÎLE
Moyenne: 164222.712
Max: 927608
Min: 22024
Terminé en 793,591s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ | _ |  
| | | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Île (niveau 3)

Remarquant que le double chemin fonctionne mieux que le chemin simple, faisons l'île en double chemin!

Le résultat est une amélioration par rapport à Island (niveau 1), mais il ne bat toujours pas le double chemin pur.

A titre de comparaison, le résultat du double trajet de la taille de l'île est de 131 134,42 mouvements en moyenne. Cela ajoute donc un nombre assez important de mouvements (environ 40k), mais pas assez pour battre le double chemin.

ÎLE
Moyenne: 171730.090
Max: 769080
Min: 29760
Terminé en 587.646s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |  
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Île (niveau 4)

Encore une fois, expérimenter avec une île imbriquée, et encore une fois, cela ne fonctionne pas si bien.

ÎLE
Moyenne: 149723.068
Max: 622106
Min: 25752
Terminé en 830.889s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |  
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Conclusion

Dans l'ensemble, cela prouve que le fait d'avoir un seul chemin long de la position actuelle de l'ivrogne à la sortie fonctionne mieux, ce qui est réalisé par la stratégie à double chemin, car après avoir fermé une sortie, l'ivrogne devra parcourir la distance maximale possible pour se rendre à La sortie.

Cela suggère en outre que la stratégie de base doit toujours être à double chemin, et nous ne pouvons que modifier la façon dont les chemins sont créés, ce qui a été fait par Sparr. Je crois donc que sa stratégie est la voie à suivre!

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {

    enum Strategy{
        SINGLE_PATH,
        ISLAND,
        DOUBLE_PATH,
        EXTREME_DOUBLE_PATH,
        PERFECT_DOUBLE_PATH,
    }

    int width,height;
    int x,y; //walker's position
    int dX,dY; //destination
    Point[][] points;
    int stepCount = 0;

    public static void main(String[]args){
        int side = 20;
//      runOnce(side, Strategy.EXTREME_DOUBLE_PATH, 0);
        runOnce(side, Strategy.PERFECT_DOUBLE_PATH, 0);
//      for(Strategy strategy: Strategy.values()){
//          runOnce(side, strategy, 0);
//      }
//      runOnce(side, Strategy.ISLAND, 1);
//      runOnce(side, Strategy.ISLAND, 2);
//      Scanner scanner = new Scanner(System.in);
//      System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      while(scanner.hasNext()){
//          side = scanner.nextInt();
//          Strategy strategy = Strategy.valueOf(scanner.next());
//          int level = scanner.nextInt();
//          scanner.nextLine();
//          runOnce(side, strategy, level);
//          System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      }
//      scanner.close();
    }

    private static Walker runOnce(int side, Strategy strategy, int level) {
        Walker walker = null;
        long total = 0;
        int max = 0;
        int min = Integer.MAX_VALUE;
        double count = 1000;
        long start = System.currentTimeMillis();
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, strategy, level, false);
            total += walker.stepCount;
            max = Math.max(walker.stepCount, max);
            min = Math.min(walker.stepCount, min);
//          System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("%s\nAverage: %.3f\nMax: %d\nMin:%d\n",strategy, total/count, max, min);
        System.out.printf("Completed in %.3fs\n", (System.currentTimeMillis()-start)/1000.0);
        walker.printPath();
        return walker;
    }

    private void createIsland(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY+1; i<topRightY; i++){
            if(i>botLeftY+1) deletePath(points[botLeftX][i].right());
            if(i<topRightY-1) deletePath(points[topRightX][i].left());
        }
        for(int i=botLeftX+1; i<topRightX; i++){
            if(i>botLeftX+1) deletePath(points[i][botLeftY].up());
            if(i<topRightX-1) deletePath(points[i][topRightY].down());
        }
    }

    private void createSinglePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==0){
                for(int j=botLeftX; j<topRightX; j++){
                    if(j==topRightX-1 && (j-botLeftX)%2==0){
                        deletePath(points[topRightX][topRightY].down());
                    } else {
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    }
                }
            } else {
                for(int j=botLeftX+(i-botLeftY)%2; j<topRightX+((i-botLeftY)%2); j++){
                    deletePath(points[j][i].up());
                }
            }
        }
    }

    private void createDoublePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i>botLeftY && (width%4!=1 || i<topRightY-1)) deletePath(points[width/2-1][i].right());
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==1){
                for(int j=botLeftX; j<topRightX; j++){
                    if((j-botLeftX)%2==0 || j<topRightX-1){
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    } else {
                        deletePath(points[topRightX-1][topRightY-1].right());
                    }
                }
            } else {
                if((i-botLeftY)%2==0){
                    for(int j=botLeftX+1; j<topRightX; j++){
                        deletePath(points[j][i].up());
                    }
                } else {
                    for(int j=botLeftX; j<topRightX+1; j++){
                        if(j!=width/2 && j!=width/2-1){
                            deletePath(points[j][i].up());
                        }
                    }
                }
            }
        }
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, Strategy strategy, int level, boolean animate){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        points = new Point[width][height];
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                points[x][y] = new Point(x,y);
            }
        }
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                if(x<width-1) new Edge(points[x][y], points[x+1][y]);
                if(y<height-1) new Edge(points[x][y], points[x][y+1]);
            }
        }

        if(strategy == Strategy.SINGLE_PATH) createSinglePath(0,0,width-1,height-1);

        if(strategy == Strategy.DOUBLE_PATH) createDoublePath(0,0,width-1,height-1);

        List<EdgeList> edgeLists = new ArrayList<EdgeList>();
        if(strategy == Strategy.ISLAND){
            List<Edge> edges = new ArrayList<Edge>();
            if(level==0){
                createIsland(0,0,width-1,height-1);
                deletePath(points[width-2][height-2].right());
                deletePath(points[width-2][height-2].up());
            } else {
                for(int i=0; i<level; i++){
                    createIsland(i,i,width-1-i, height-1-i);
                }
                createDoublePath(level,level,width-1-level,height-1-level);
                for(int i=height-1; i>=height-level; i--){
                    edges.add(points[i-2][i].right());
                    edges.add(points[i][i-2].up());
                    edgeLists.add(new EdgeList(points[i-1][i].right(), points[i][i-1].up()));
                }
            }
            edges.add(points[width-1-level][height-1-level].down());
            edges.add(points[width-1-level][height-1-level].left());
            edgeLists.add(new EdgeList(edges.toArray(new Edge[0])));
        }

        int[] availableVerticals = new int[height];
        if(strategy == Strategy.EXTREME_DOUBLE_PATH){
            for(int i=1; i<width-1; i++){
                deletePath(points[i][0].up());
            }
            availableVerticals[0] = 2;
            for(int i=1; i<height; i++){
                availableVerticals[i] = width;
            }
        }

        boolean[][] available = new boolean[width][height];
        if(strategy == Strategy.PERFECT_DOUBLE_PATH){
            for(int x=0; x<width; x++){
                for(int y=0; y<height; y++){
                    if(x%2==1 && y%2==1){
                        available[x][y] = true;
                    } else {
                        available[x][y] = false;
                    }
                }
            }
        }
//      printPath();
        while(!walk()){
            if(animate)try{Thread.sleep(500);}catch(InterruptedException e){}
            if(strategy == Strategy.ISLAND){
                if(x==y && (x==1 || (x>=2 && x<=level))){
                    if(!hasBeenWalked(points[x][x].down())){
                        deletePath(points[x][x].down());
                    } else if(!hasBeenWalked(points[x][x].left())){
                        deletePath(points[x][x].left());
                    }
                }
            }
            if(strategy == Strategy.EXTREME_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(untravelled>1){
                    if(cur.up()!=null && availableVerticals[y]>2 && !cur.up().walked){
                        deletePath(cur.up());
                        availableVerticals[y]--;
                    }
                    if(cur.down()!=null && !cur.down().walked){
                        deletePath(cur.down());
                        availableVerticals[y-1]--;
                    }
                    if(cur.up()!=null && cur.left()!=null && !cur.left().walked){
                        deletePath(cur.left());
                        deletePath(points[x][y+1].left());
                    }
                    if(cur.up()!=null && cur.right()!=null && !cur.right().walked){
                        deletePath(cur.right());
                        if(y<height-1) deletePath(points[x][y+1].right());
                    }
                }
            }
            if(strategy == Strategy.PERFECT_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(x%2!=1 || y%2!=1){
                    if(untravelled>1){
                        if(cur.down()==null && hasBeenWalked(cur.right())){
                            if(canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.down()==null && hasBeenWalked(cur.left())){
                            if(x%2==0 && y%2==1 && canBeDeleted(cur.right())) deletePath(cur.right());
                            else if(cur.right()!=null && canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.up())){
                            if(canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.down())){
                            if(x%2==1 && y%2==0 && canBeDeleted(cur.up())) deletePath(cur.up());
                            else if (cur.up()!=null && canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                    }
                } else {
                    if(!hasBeenWalked(cur.left())){
                        if(x>1 && available[x-2][y]){
                            if(untravelled>1){
                                available[x-2][y] = false;
                                deletePath(cur.up());
                            }
                        } else if(cur.up()!=null){
                            if(canBeDeleted(cur.left())) deletePath(cur.left());
                            if(canBeDeleted(points[x][y+1].left())) deletePath(points[x][y+1].left());
                        }
                    }
                    if(!hasBeenWalked(cur.down())){
                        if(y>1 && available[x][y-2]){
                            if(untravelled>1){
                                available[x][y-2] = false;
                                deletePath(cur.right());
                            }
                        } else if(cur.right()!=null){
                            if(canBeDeleted(cur.down())) deletePath(cur.down());
                            if(canBeDeleted(points[x+1][y].down())) deletePath(points[x+1][y].down());
                        }
                    }
                }
            }
            if(strategy == Strategy.DOUBLE_PATH || strategy == Strategy.EXTREME_DOUBLE_PATH
                    || strategy == Strategy.PERFECT_DOUBLE_PATH){
                if(x==width-2 && y==height-1 && points[width-1][height-1].down()!=null){
                    deletePath(points[width-1][height-1].left());
                }
                if(x==width-1 && y==height-2 && points[width-1][height-1].left()!=null){
                    deletePath(points[width-1][height-1].down());
                }
            } else if(strategy == Strategy.ISLAND){
                for(EdgeList edgeList: edgeLists){
                    boolean deleted = false;
                    for(Edge edge: edgeList.edges){
                        if(edge.start.x == x && edge.start.y == y){
                            if(!hasBeenWalked(edge)){
                                deletePath(edge);
                                edgeList.edges.remove(edge);
                                if(edgeList.edges.size() == 1){
                                    edgeLists.remove(edgeList);
                                }
                                deleted = true;
                                break;
                            }
                        }
                    }
                    if(deleted) break;
                }
            }
            if(animate)printPath();
        }
    }

    public boolean hasBeenWalked(Edge edge){
        if(edge == null) return false;
        return edge.walked;
    }

    public boolean canBeDeleted(Edge edge){
        if(edge == null) return false;
        return !edge.walked;
    }

    public List<Edge> getAdjacentUntravelledEdges(){
        List<Edge> result = new ArrayList<Edge>();
        for(Edge edge: points[x][y].edges){
            if(edge!=null && !hasBeenWalked(edge)) result.add(edge); 
        }
        return result;
    }

    public void printPath(){
        StringBuilder builder = new StringBuilder();
        for(int y=height-1; y>=0; y--){
            for(int x=0; x<width; x++){
                Point point = points[x][y];
                if(this.x==x && this.y==y){
                    if(point.up()!=null) builder.append('?');
                    else builder.append('.');
                } else {
                    if(point.up()!=null) builder.append('|');
                    else builder.append(' ');
                }
                if(point.right()!=null) builder.append('_');
                else builder.append(' ');
            }
            builder.append('\n');
        }
        System.out.print(builder.toString());
    }

    public boolean walk(){
        ArrayList<Edge> possibleMoves = new ArrayList<Edge>();
        Point cur = points[x][y];
        for(Edge edge: cur.edges){
            if(edge!=null) possibleMoves.add(edge);
        }
        int random = (int)(Math.random()*possibleMoves.size());
        Edge move = possibleMoves.get(random);
        move.walked = true;
        if(move.start == cur){
            x = move.end.x;
            y = move.end.y;
        } else {
            x = move.start.x;
            y = move.start.y;
        }
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(points[x][y]);
        reachable.add(points[x][y]);
        while(next.size()>0){
            Point cur = next.poll();
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(cur.up()!=null) neighbors.add(cur.up().end);
            if(cur.right()!=null) neighbors.add(cur.right().end);
            if(cur.down()!=null) neighbors.add(cur.down().start);
            if(cur.left()!=null) neighbors.add(cur.left().start);
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor == points[dX][dY]) return true;
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean deletePath(Edge toDelete){
        if(toDelete == null) return true;
//      if(toDelete.walked){
//          System.err.println("Edge already travelled!");
//          return false;
//      }
        int startIdx = toDelete.getStartIdx();
        int endIdx = toDelete.getEndIdx();
        toDelete.start.edges[startIdx] = null;
        toDelete.end.edges[endIdx] = null;
//      if(!isSolvable()){
//          toDelete.start.edges[startIdx] = toDelete;
//          toDelete.end.edges[endIdx] = toDelete;
//          System.err.println("Invalid deletion!");
//          return false;
//      }
        return true;
    }

    static class EdgeList{
        List<Edge> edges;

        public EdgeList(Edge... edges){
            this.edges = new ArrayList<Edge>();
            this.edges.addAll(Arrays.asList(edges));
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;
        boolean walked;

        public Edge(Point start, Point end){
            walked = false;
            this.start = start;
            this.end = end;
            this.start.edges[getStartIdx()] = this;
            this.end.edges[getEndIdx()] = this;
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        public Edge(int x1, int y1, int x2, int y2){
            this(new Point(x1,y1), new Point(x2,y2));
        }

        public boolean exists(){
            return start.edges[getStartIdx()] != null || end.edges[getEndIdx()] != null;
        }

        public int getStartIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 0;
                else return 2;
            } else {
                if(start.x < end.x) return 1;
                else return 3;
            }
        }

        public int getEndIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 2;
                else return 0;
            } else {
                if(start.x < end.x) return 3;
                else return 1;
            }
        }

        public boolean isVertical(){
            return start.x==end.x;
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        Edge[] edges;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
            edges = new Edge[4];
        }

        public Edge up(){ return edges[0]; }
        public Edge right(){ return edges[1]; }
        public Edge down(){ return edges[2]; }
        public Edge left(){ return edges[3]; }

        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}

juste la moitié
la source

C'est très impressionnant. Combien de temps faut-il pour courir? Si les entrées gagnantes restent aussi proches, nous devrons augmenter le nombre de runs pour voir si nous pouvons les séparer.

1

Le timing est déjà inclus dans l'extrait. Environ 400s pour 1000 runs. Cela inclut un contrôle de solvabilité à chaque suppression de chemin. Je peux supprimer cela pour avoir environ 170s pour 1000 courses. Je peux donc faire 20 000 courses en une heure environ.

moitié du

En fait, en optimisant davantage, je pourrais peut-être exécuter 100k en 3,5 heures.

moitié du

Mon score est de 100 km et a pris 10 minutes. @justhalf très agréable sur le labyrinthe à double chemin le plus flexible. Je sais comment faire encore mieux, mais je n'ai pas la patience de le mettre en œuvre pour le moment.

Sparr

2

Heureux de voir la solution symétrique implémentée. J'ai encore une autre idée pour améliorer cette solution, et cette fois je pense que je pourrais l'implémenter moi-même :)

Sparr

10

227934 (20x20)

Ma troisième tentative. Utilise la même approche générale que @stokastic avec deux chemins vers la sortie. Lorsque le promeneur atteint la fin d'un chemin, il se ferme, l'obligeant à revenir pour se rendre à la fin de l'autre chemin pour sortir. Mon amélioration consiste à générer les chemins au fur et à mesure que le marcheur progresse, de sorte que le chemin qu'il progresse plus loin dans la première moitié du processus finira par être plus long que l'autre chemin.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 8:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'?';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'*';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                maze[r][c]=0;
            }
        }
        maze[1][1]=9;
        maze[1][2]=1;
        maze[2][1]=1;
        maze[1][3]=8;
        maze[3][1]=8;
        int progress_l = 0;
        int progress_r = 0;
        int side = 0;
        int closed_exit = 0;
        x=0;
        y=0;
        if (DEBUG) print_maze();
        long long turn = 0;
        int in = 0;
        while (x!=X-1||y!=Y-1) {
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int dx=0, dy=0;
            if (DEBUG) {
                std::cin>>in;
                switch(in) {
                    case 0:
                        dy=-1; dx=0; break;
                    case 1:
                        dy=0; dx=1; break;
                    case 2:
                        dy=1; dx=0; break;
                    case 3:
                        dy=0; dx=-1; break;
                    default:
                        dy=0; dx=0; break;
                }
            } else {
                int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
                int exit_choice = -1;
                do {
                    if (rand()%exits == 0) {
                        exit_choice = exits;
                        break;
                    } else {
                        exits--;
                    }
                }while(exits);

                --exits;

                if (maze[r-1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = -1;
                        dx = 0;
                    }
                }
                if (maze[r][c+1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = 1;
                    }
                }
                if (maze[r+1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 1;
                        dx = 0;
                    }
                }
                if (maze[r][c-1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = -1;
                    }
                }
            }

            x+=dx;
            y+=dy;

            if(x==X-1 && y==Y-1) continue;

            if (x==0&&y==1) side=-1;
            if (x==1&&y==0) side=1;
            if (maze[y*2+1][x*2+1]==8) { // room needs another exit, maybe
                if (side==-1) { // left half of maze
                    if (y==1) { // top of a column
                        if (x%2) { // going up, turn right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // going right, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-1) { // bottom of a column
                        if (x%2 && x<(X-progress_r-3)) { // going right, turn up if there's room
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                            progress_l=x+1;
                        } else { // going down or exiting, go right
                            if (x!=X-2 or closed_exit==1) {
                                maze[y*2+1][x*2+2]=1;
                                maze[y*2+1][x*2+3]=8;
                            } else {
                                closed_exit = -1;
                            }
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }
                } else { // right half of maze
                    if (y==0) { // top row
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-2) { // heading right to the exit
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            if (x!=X-1 or closed_exit==-1) {
                                maze[y*2+2][x*2+1]=1;
                                maze[y*2+3][x*2+1]=8;
                            } else {
                                closed_exit = 1;
                            }
                        }
                    } else if (y==Y-3) { // bottom of a column
                        if (x>progress_l+1) { // do we have room for another column?
                            if (!(x%2)&&y>1) { // going left, turn up
                                maze[y*2+0][x*2+1]=1;
                                maze[y*2-1][x*2+1]=8;
                            } else { // going down, turn left
                                maze[y*2+1][x*2+0]=1;
                                maze[y*2+1][x*2-1]=8;
                                progress_r=X-x-1;
                            }
                        } else { // abort, move down to escape row
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==1) { // top of a column
                        if (!(x%2)) { // going up, turn left
                            maze[y*2+1][x*2+0]=1;
                            maze[y*2+1][x*2-1]=8;
                        } else { // going left, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }

                }
                maze[y*2+1][x*2+1]=9;
            }

            if (DEBUG) print_maze();
        }
        // print_maze();
        printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    printf("%d rounds in a %d*%d maze\n",ROUNDS,X,Y);
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}

sortie (avec le temps):

...
turns:194750
turns:506468
turns:129684
turns:200712
turns:158664
turns:156550
turns:311440
turns:137900
turns:86948
turns:107134
turns:81806
turns:310274
100000 rounds in a 20*20 maze
average:     227934
stddev:      138349
real    10m54.797s
...

exemple de mon labyrinthe, avec des longueurs à peu près égales au chemin, montrant le chemin gauche / inférieur coupé de la sortie (en bas à droite):

  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 |  _   _   _   _   _   _   _   _   _  |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | |_| |_| |_| |_| |_|
 | | | | | | | | | |_ _ _ _ _ _ _ _ _ _
 |_| |_| |_| |_| |_ _ _ _ _ _ _ _ _ _  !

PS: Je suis conscient d'une amélioration très mineure de cet algorithme qui nécessite un code plus intelligent pour générer une forme différente pour les deux chemins, des escaliers au lieu de zig zags à hauteur constante.

Sparr
la source

La couleur m'a impressionné. Vous avez mon vote monsieur!

Stokastic

1

C'est assez impressionnant. Rappelez-vous quand nous avons juste dessiné sur les visages des ivrognes?

Dennis

Il est assez difficile de discerner votre graphique, peut-être pouvez-vous changer l'impression de votre graphique en quelque chose de similaire au mien?

moitié du

1

@justhalf votre souhait est ma commande

Sparr

1

@justhalf Je l'ai tiré sur papier. Il suffit d'écrire la logique. Si je ne le fais pas dans quelques jours, je vais vous donner le croquis? :)

Sparr

6

135.488.307,9 pour 98x98

199094.3 pour 20x20

J'ai mis en œuvre une solution qui crée deux chemins vers la fin et ferme exactement l'un d'eux une fois que l'ivrogne l'atteint. Cela simule une longueur de chemin qui, à tout le moins, sera 1,5 fois la longueur d'un chemin unique du début à la fin. Après 27 runs, j'ai atteint une moyenne d'environ 135 millions. Malheureusement, cela prend plusieurs minutes par marche, je devrai donc le faire fonctionner pendant les prochaines heures. Une mise en garde - mon générateur de double chemin ne fonctionne que si la taille du graphique est sous la forme 4 * n + 2, ce qui signifie que le plus proche possible de 100 est 102 ou 98. Je vais publier des résultats en utilisant 98, ce à quoi je m'attends pour toujours dépasser la méthode du chemin en zigzag. Je travaillerai plus tard sur un meilleur système de cheminement. Affiche actuellement les résultats sous la forme (numSteps, currentAverage) après chaque promenade.

EDIT: corrigé pour que le code fonctionne désormais sur des tailles de graphique qui sont un multiple de 2, plutôt que 4 * n + 2.

Code: (ajoutez l'argument 'True' au constructeur de marcheur à la ligne 187 pour le dessin de tortue du graphique).

import random
import turtle

WIDTH  = 20
HEIGHT = 20
L, U, R, D = 1, 2, 4, 8

def delEdge(grid, x1, y1, x2, y2):

    # check that coordinates are in-bounds
    if not (0 <= x1 < WIDTH):  return False
    if not (0 <= y1 < HEIGHT): return False
    if not (0 <= x2 < WIDTH):  return False
    if not (0 <= y2 < HEIGHT): return False

    # swap order such that x1 <= x2 and y1 <= y2
    if x2 < x1:
        x2 ^= x1
        x1 ^= x2
        x2 ^= x1
    if x2 < x1: print "Swap failure: {}, {}".format(x1, x2)

    if y2 < y1:
        y2 ^= y1
        y1 ^= y2
        y2 ^= y1
    if y2 < y1: print "Swap failure: {}, {}".format(y1, y2)

    # check that only one of the deltas is = 1
    dx = x2 - x1
    dy = y2 - y1

    if dx and dy:       return False
    if not (dx or dy):  return False
    if dx > 1:          return False
    if dy > 1:          return False

    #print "<{}, {}>, <{}, {}>".format(x1, y1, x2, y2)

    if dx > 0:
        try: grid[x1][y1].remove(R)
        except: pass
        try: grid[x2][y2].remove(L)
        except: pass
    if dy > 0:
        try: grid[x1][y1].remove(D)
        except: pass
        try: grid[x2][y2].remove(U)
        except: pass

    return True

def newGrid():

    grid = [[[] for y in xrange(HEIGHT)] for x in xrange(WIDTH)]

    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            if x > 0:
                grid[x][y].append(L)
            if x < WIDTH-1:
                grid[x][y].append(R)
            if y > 0:
                grid[x][y].append(U)
            if y < HEIGHT-1:
                grid[x][y].append(D)

    return grid

class walker:

    def __init__(self, grid, mode, draw=False):
        self.x  = 0
        self.y  = 0
        self.dx = WIDTH-1
        self.dy = HEIGHT-1

        self.grid     = grid
        self.mode     = mode
        self.draw     = draw
        self.numSteps = 0

        self.initGrid()

    def initGrid(self):
        if self.mode == 0:
            #pass
            if self.draw: drawGrid(grid)

        elif self.mode == 1:

            for y in xrange(HEIGHT-1):
                if y % 2 == 0:
                    for x in xrange(WIDTH - 1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(1, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            if self.draw: drawGrid(grid)

        elif self.mode == 2:
            for y in xrange(HEIGHT/2):
                if y % 2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(2, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(HEIGHT/2, HEIGHT-1):
                if y%2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(0, WIDTH-2):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(1, HEIGHT-1):
                midpoint = HEIGHT/2
                if HEIGHT % 4 == 0: 
                    midpoint = HEIGHT/2 + 1
                if y < midpoint:
                    delEdge(grid, 0, y, 1, y)
                else:
                    delEdge(grid, WIDTH-1, y, WIDTH-2, y)
            if self.draw: drawGrid(grid)

    def walk(self):
        self.numSteps += 1
        choices = grid[self.x][self.y]
        direction = random.choice(choices)
        #print (self.x, self.y), grid[self.x][self.y], direction
        if direction   == L: self.x -= 1
        elif direction == U: self.y -= 1
        elif direction == R: self.x += 1
        elif direction == D: self.y += 1

    def main(self):
        hasBlocked = False
        while (self.x, self.y) != (self.dx, self.dy):
            #print (self.x, self.y), (self.dx, self.dy)
            self.walk()
            if self.mode == 2:
                if not hasBlocked:
                    if (self.x, self.y) == (WIDTH-2, HEIGHT-1):
                        delEdge(self.grid, WIDTH-2, HEIGHT-1, WIDTH-1, HEIGHT-1)
                        hasBlocked = True
                    elif (self.x, self.y) == (WIDTH-1, HEIGHT-2):
                        delEdge(self.grid, WIDTH-1, HEIGHT-1, WIDTH-1, HEIGHT-2)
                        hasBlocked = True

        return self.numSteps

def drawGrid(grid):
    size = 3
    turtle.speed(0)
    turtle.delay(0)
    turtle.ht()
    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            dirs = grid[x][y]
            for dir in dirs:
                if dir == L:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x-1)*4, y*4))
                elif dir == R:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x+1)*4, y*4))
                elif dir == U:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y-1)*4))
                elif dir == D:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y+1)*4))
    turtle.mainloop()

numTrials  = 100
totalSteps = 0.0
i = 0
try:
    while i < numTrials:
        grid = newGrid()

        w = walker(grid, 2)
        steps = w.main()
        totalSteps += steps
        print steps, totalSteps/(i+1)
        i += 1

    print totalSteps / numTrials

except KeyboardInterrupt:
    print totalSteps / i

Données brutes: (numSteps actuel, moyenne courante)

358796490 358796490.0
49310430 204053460.0
106969130 171692016.667
71781702 146714438.0
49349086 127241367.6
40874636 112846912.333
487607888 166384194.571
56423642 152639125.5
71077302 143576700.667
101885368 139407567.4
74423642 133499937.818
265170542 144472488.167
59524778 137938048.923
86919630 134293876.143
122462528 133505119.6
69262650 129489965.25
85525556 126903823.529
161165512 128807250.667
263965384 135920836.632
128907594 135570174.5
89535930 133378067.619
97344576 131740181.636
98772132 130306788.174
140769524 130742735.5
198274280 133443997.28
95417374 131981434.846
226667006 135488307.852

stokastic
la source

J'ai réduit la taille du graphique à 20 par 20 pour accélérer les temps d'exécution. J'espère que ça aide.

Vous

Votre score de 20 sur 20 est-il supérieur à 1000 pistes?

@Lembik oui c'est ça.

stokastic

1

@Dennis au contraire :)

Sparr

6

Approche à 4 voies, 213k

L'approche à sens unique est

Ligne droite de S à E

et marque une moyenne de N^2.

L'approche à deux voies est

Boucle avec S et E face à face

mais la première fois que l'ivrogne arrive à portée du point final, il est coupé:

La boucle est coupée pour donner une ligne courbe de S à E

Il marque une moyenne de (N/2)^2 + N^2.

L'approche à quatre voies utilise deux coupes:

Boucles imbriquées, réunies en deux fourches, un de chaque côté de E Coupez l'une des fourches du côté E De l'autre côté, coupez la fourche du côté non-E. Cela laisse un chemin alambiqué

Supposons que la boucle externe est de longueur xNet la boucle interne de longueur (1-x)N. Pour plus de simplicité, je vais normaliserN=1 .

Du début à la première coupe, la moyenne est de (x/2)^2. De la première coupe à la deuxième coupe a deux options, de longueurs xet 1-x; cela donne une moyenne de (1-x)x^2 + x(1-x)^2 = x-x^2. Enfin le chemin restant donne 1. Donc, le score total est N^2 (1 + x - 3/4 x^2).

J'ai d'abord supposé que garder les chemins disponibles de longueur égale à chaque étape serait optimal, donc mon approche initiale a utilisé x = 1/2un score de 1.3125 N^2. Mais après avoir fait l'analyse ci-dessus, il s'avère que la répartition optimale est donnée x = 2/3avec le score 1.3333 N^2.

~~1000 walks with average 210505.738 in 202753ms~~

1000 walks with average 212704.626 in 205191ms

avec code

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
public class RandomWalker {
    private static final int SIZE = 19;
    private static final Point dest = new Point(SIZE, SIZE);

    private final Random rnd = new Random();
    private Point p = new Point(0, 0);
    private int step = 0;
    private Set<Set<Point>> edges;
    private Map<Set<Point>, String> cuttableEdgeNames;
    private Set<String> cutSequences;
    private String cutSequence = "";

    public static void main(String[] args) {
        long start = System.nanoTime();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            RandomWalker rw = new RandomWalker();
            total += rw.walk();
            walks++;
        }

        long timeTaken = System.nanoTime() - start;
        System.out.println(walks + " walks with average " + total / (double)walks + " in " + (timeTaken / 1000000) + "ms");
    }

    RandomWalker() {
        loadMaze(
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+-+-+",
            "| | | | | | | | | | | | |             |",
            "+ + + + + + + + + + + + + +-+ +-+ +-+ +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+-+ + + + + + +",
            "| | | | | | | | | | | |     | | | | | |",
            "+ + + + + + + + + + + + +-+ + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "|                     | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | d",
            "+ + + + + + + + + + + + + + +-+ +-+ +c+",
            "| | | | | | | | | | | | | |           |",
            "+ + + + + + + + + + + + + +-+-+-+-+-+ +",
            "| | | | | | | | | | | | |           f b",
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+e+a+"
        );
        cutSequences = new HashSet<String>();
        cutSequences.add("ac");
        cutSequences.add("ad");
        cutSequences.add("be");
        cutSequences.add("bf");
    }

    private void loadMaze(String... row) {
        edges = new HashSet<Set<Point>>();
        cuttableEdgeNames = new HashMap<Set<Point>, String>();

        // Horizontal edges
        for (int y = 0; y <= SIZE; y++) {
            for (int x0 = 0; x0 < SIZE; x0++) {
                char ch = row[y * 2].charAt(x0 * 2 + 1);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x0, y));
                edge.add(new Point(x0 + 1, y));
                edges.add(edge);
                if (ch != '-') cuttableEdgeNames.put(edge, "" + ch);
            }
        }

        // Vertical edges
        for (int y0 = 0; y0 < SIZE; y0++) {
            for (int x = 0; x <= SIZE; x++) {
                char ch = row[y0 * 2 + 1].charAt(x * 2);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x, y0));
                edge.add(new Point(x, y0 + 1));
                edges.add(edge);
                if (ch != '|') cuttableEdgeNames.put(edge, "" + ch);
            }
        }
    }

    int walk() {
        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        Set<Point> edge = new HashSet<Point>();
        edge.add(p1);
        edge.add(p2);

        // Is it cuttable?
        String id = cuttableEdgeNames.get(edge);
        if (id != null) {
            String prefix = cutSequence + id;
            for (String seq : cutSequences) {
                if (seq.startsWith(prefix)) {
                    // Cut it
                    cutSequence = prefix;
                    edges.remove(edge);
                    return false;
                }
            }
        }

        return edges.contains(edge);
    }
}

Peter Taylor
la source

Ah, je vois, c'est pourquoi mon approche d'île ne fonctionne pas, je n'ai pas équilibré la longueur du chemin. Juste pour clarifier ma compréhension, la longueur de fà cdans votre code est d'environ N/2, que ce soit par e(et d) ou non, non?

moitié du

comment est la longueur du chemin yE N au lieu de la longueur N / 2?

Sparr

@justhalf, oui. Il y a 400 sommets, donc il y a 401 arêtes (après une coupe, le graphique est un cycle hamiltonien); les deux trajets extérieurs ont chacun 100 arêtes, et la boucle intérieure a donc 101 arêtes.

Peter Taylor

je l'ai. deux observations: a) des labyrinthes plus grands bénéficieraient de plus de 2 ^ n trajets. b) si vous rendez votre longueur de chemin dynamique, vous battrez les leaders actuels avec des solutions dynamiques à deux chemins (moi-même et @justhalf)

Sparr

@Sparr: c'est N^2 pas 2^N. Et oui, rendre cette dynamique la rendra meilleure, le défi est de savoir comment la rendre dynamique tout en conservant la propriété à quatre chemins. @PeterTaylor: Belles images!

moitié du

5

J'ai essayé de découper la grille presque entièrement à travers tous les k . Ce qu'il convertit efficacement en quelque chose de semblable à une marche aléatoire sur un kpar N * N/kgrille. L'option la plus efficace consiste à découper chaque ligne afin de forcer l'ivrogne à zigzaguer.

Pour le boîtier 20x20 (SIZE=19 ) j'ai

time java RandomWalker 
1000 walks with average 148577.604

real    0m14.076s
user    0m13.713s
sys     0m0.360s

avec code

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
// This handles a simpler problem where the grid is mutilated before the drunkard starts to walk.
public class RandomWalker {
    private static final int SIZE = 19;
    private final Random rnd = new Random();

    public static void main(String[] args) {
        RandomWalker rw = new RandomWalker();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            total += rw.walk();
            walks++;
        }

        System.out.println(walks + " walks with average " + total / (double)walks);
    }

    int walk() {
        Point dest = new Point(SIZE, SIZE);
        Point p = new Point(0, 0);
        int step = 0;

        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        return p1.x != p2.x || p1.x == SIZE * (Math.max(p1.y, p2.y) & 1);
    }
}

Peter Taylor
la source

Ai-je raison de penser que toute la suppression des bords se produit avant le début de la marche dans votre solution?

@Lembik, oui. Je pensais que le commentaire en haut clarifierait cela.

Peter Taylor

Oui, merci. Je me demande quelle différence vous pouvez faire en supprimant les bords pendant la marche.

Par curiosité, combien de temps cela prend-il pour courir (au total et par course)?

stokastic

@stokastic, environ 3 secondes par exécution.

Peter Taylor

3

Pour ceux qui ne veulent pas réinventer la roue

Ne t'inquiète pas! Je vais le réinventer pour vous :)

C'est en Java, soit dit en passant.

J'ai créé une classe Walker qui traite de la marche au hasard. Il comprend également une méthode utile pour déterminer si un mouvement est valide (s'il a déjà été suivi).

Je suppose que vous tous intelligents pouvez trouver des chiffres aléatoires pour le constructeur, je vous laisse le soin de tester certains cas. Aussi, appelez simplement la fonction walk () pour (vous l'avez deviné!) Faire marcher l'ivrogne (au hasard).

J'implémenterai la fonction canComeHome () une autre fois. De préférence, après avoir recherché la meilleure façon de le faire.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {
    int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    int dX,dY; //destination
    TreeSet<Edge> pathsNoLongerAvailable = new TreeSet<Edge>();
    TreeSet<Edge> previouslyTraveled = new TreeSet<Edge>();
    int stepCount = 0;

    public static void main(String[]args){
        int side = 10;
        Walker walker = null;
        int total = 0;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        while(!walk()){
            // Do something
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = (int)(Math.random()*possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge){
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}

Stretch Maniac
la source

Cela contient quelques bugs et incohérences. previouslyTraveled.add(new int[]{x,y,move[0],move[1]})devrait être x+move[0]et y+move[1]. Le Width-1et Height-1, et l'inefficacité dans la vérification des chemins supprimés. J'ai édité votre code (avec une fonction supplémentaire pour imprimer le labyrinthe). N'hésitez pas à revenir en arrière si vous pensez que c'est inapproprié.

moitié du

Votre Edgen'implémente pas correctement Comparable<Edge>. Si vous souhaitez que les arêtes soient égales, même si vous les inversez, vous devez également prendre en compte l'inversion dans le cas différent. La façon la plus simple de procéder serait de changer le constructeur pour garder les points ordonnés.

Peter Taylor

@PeterTaylor: Merci pour l'avertissement. J'ai un peu pensé au cas non égal, mais je n'ai pas réussi à comprendre pourquoi il est important. Savez-vous où je peux rechercher les exigences d'implémentation Comparable?

moitié du

1

docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html La clé est qu'il doit définir une commande totale. Mais si Aet Bsont le même bord inversé et Cdifférent, vous pouvez obtenir A.compareTo(B) == B.compareTo(A) == 0mais A.compareTo(C) < 0et B.compareTo(C) > 0.

Peter Taylor

Et maintenant? J'ai ajouté une autre classe. Et j'ai ajouté une fonction pour vérifier si elle est résoluble (ou canComeHome())

juste le

3

64,281

Mise à jour depuis la modification de la grille de 100x100 à 20x20 (1000 tests). Le score sur 100x100 (100 tests) était d'environ 36M.

Bien que cela ne puisse pas battre une marche 1D, je voulais jouer avec une idée que j'avais.

L'idée de base est que la grille est divisée en pièces carrées, avec un seul chemin menant «à la maison» de chacune. Le chemin est ouvert selon l'état d' ébriété se rapproche de la dernière , ce qui signifie qu'il doit explorer toutes les sorties possibles, seulement pour tous , mais l' un d'eux a claqué dans son visage.

Après avoir joué avec la taille des pièces, je suis arrivé à la même conclusion que Peter, le couper plus petit est mieux. Les meilleurs scores viennent avec une taille de chambre de 2.

Average score over 100 trials: 36051265

Le code est bâclé, ne vous occupez pas du désordre. Vous pouvez SHOWactionner l' interrupteur et il affichera une image des chemins à chaque SHOW_INTétape afin que vous puissiez le regarder en action. Une exécution terminée ressemble à quelque chose comme:

entrez la description de l'image ici

(Il s'agit de l'image de la grille précédente de 100x100. 20x20 est exactement comme ça, mais, bien, plus petit. Le code ci-dessous a été mis à jour pour de nouvelles tailles / exécutions.)

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.image.*;
import java.util.*;
import javax.swing.*;

public class DrunkWalk {

    boolean SHOW = false;
    int SHOW_INT = 10;
    int SIZE = 20;
    Random rand = new Random();
    Point pos;
    int[][] edges;
    int[][] wally;
    int[] wallx;
    int roomSize = 2;
    JFrame frame;
    final BufferedImage img;

    public static void main(String[] args){
        long total=0,runs=1000;
        for(int i=0;i<runs;i++){
            int steps = new DrunkWalk().run();
            total += steps;
            System.out.println("("+i+") "+steps);
        }
        System.out.println("\n Average " + (total/runs) + " over " + runs + " trials.");
    }

    DrunkWalk(){
        edges = new int[SIZE][SIZE];
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if(x>0) edges[x][y] |= WEST;
                if(x+1<SIZE) edges[x][y] |= EAST;
                if(y>0) edges[x][y] |= NORTH;
                if(y+1<SIZE) edges[x][y] |= SOUTH;
            }
        }
        wallx = new int[SIZE/roomSize+1];
        wally = new int[SIZE/roomSize+1][SIZE/roomSize+1];
        pos = new Point(SIZE-1,SIZE-1);
        img = new BufferedImage(SIZE*6+1,SIZE*6+1, BufferedImage.TYPE_INT_RGB);
        frame = new JFrame(){
            public void paint(Graphics g) {
                g.drawImage(img, 50, 50, null);
            }
        };
        frame.setSize(700,700);
        if(SHOW)
            frame.show();
    }

    void draw(){
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        Graphics g = img.getGraphics();
        g.setColor(Color.WHITE);
        g.clearRect(0, 0, img.getWidth(), img.getHeight());
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if((edges[x][y]&EAST)==EAST)
                    g.drawLine(x*6, y*6, x*6+5, y*6);
                if((edges[x][y]&SOUTH)==SOUTH)
                    g.drawLine(x*6, y*6, x*6, y*6+5);
            }
        }
        g.setColor(Color.RED);
        g.drawOval(pos.x*6-2, pos.y*6-2, 5, 5);
        g.drawOval(pos.x*6-1, pos.y*6-1, 3, 3);
        frame.repaint();
    }

    int run(){
        int steps = 0;
        Point home = new Point(0,0);
        while(!pos.equals(home)){
            if(SHOW&&steps%SHOW_INT==0){
                System.out.println(steps);
                draw();
            }
            step();
            adversary();
            steps++;
        }
        if(SHOW)
            draw();
        return steps;
    }

    void adversary(){
        int rx = pos.x / roomSize;
        int ry = pos.y / roomSize;
        int maxWalls = roomSize - 1;
        if(wally[rx][ry] < maxWalls){
            if(pos.y%roomSize==0)
                if(delete(pos.x,pos.y,NORTH))
                    wally[rx][ry]++;
        }
        maxWalls = SIZE-1;
        if(pos.x%roomSize==0){
            if(wallx[rx] < maxWalls)
                if(delete(pos.x, pos.y,WEST))
                    wallx[rx]++;


        }       
    }

    void step(){
        List<Integer> choices = getNeighbors(pos);
        Collections.shuffle(choices);
        int dir = choices.get(0);
        pos.x += dir==WEST?-1:dir==EAST?1:0;
        pos.y += dir==NORTH?-1:dir==SOUTH?1:0;
    }

    boolean delete(int x, int y, int dir){
        if((edges[x][y] & dir) != dir)
            return false;
        edges[x][y] -= dir;
        if(dir == NORTH)
            if(y>0) edges[x][y-1] -= SOUTH;
        if(dir == SOUTH)
            if(y+1<SIZE) edges[x][y+1] -= NORTH;
        if(dir == EAST)
            if(x+1<SIZE) edges[x+1][y] -= WEST;
        if(dir == WEST)
            if(x>0) edges[x-1][y] -= EAST;
        return true;
    }

    List<Integer> getNeighbors(Point p){
        if(p.x==SIZE || p.y==SIZE){
            System.out.println("wtf");
            System.exit(0);
        }
        List<Integer> choices = new ArrayList<Integer>();
        if((edges[p.x][p.y] & NORTH) == NORTH)
            choices.add(NORTH);
        if((edges[p.x][p.y] & SOUTH) == SOUTH)
            choices.add(SOUTH);
        if((edges[p.x][p.y] & EAST) == EAST)
            choices.add(EAST);
        if((edges[p.x][p.y] & WEST) == WEST)
            choices.add(WEST);
        return choices;
    }

    final static int NORTH=1,EAST=2,SOUTH=4,WEST=8;
}

Géobits
la source

Je viens de remarquer qu'il devrait aller de bot / gauche-> haut / droite, tandis que le mien va bot / droite-> haut / gauche. Je peux le changer si ça compte vraiment, mais ...

Geobits

C'est très bien et c'est la première solution dynamique je pense. Je suis intéressé par le fait que votre chemin ne soit pas aussi long que celui statique.

Si par «pas tout à fait aussi long», vous entendez ~ 1/3 aussi longtemps que l'un et ~ 36x plus long l'autre? : P

Geobits

3

188k, avec 2 chemins

Les meilleures entrées semblent toutes adopter l'approche consistant à générer 2 chemins, puis à en couper un lorsque l'ivrogne approche de la fin du chemin. Je ne pense pas que je peux battre l'entrée de moitié seulement, mais je ne pouvais pas m'empêcher de me demander: Pourquoi 2 chemins? Pourquoi pas 3, 5 ou 20?

TL; DR : 2 chemins semblent être optimaux

J'ai donc fait une expérience. Basé sur le framework Stretch Maniac, j'ai écrit une entrée pour tester différents nombres de chemins. Vous pouvez modifier le featureSizeparamètre pour faire varier le nombre de chemins. Un featureSizede 20 donne 1 chemin, 10 donne 2 chemins, 7 donne 3, 5 donne 4, etc.

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;

public class Walker {
    final int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    final int dX,dY; //destination
    final int featureSize;
    Set<Edge> pathsNoLongerAvailable = new HashSet<>();
    Set<Edge> previouslyTraveled = new HashSet<>();
    int stepCount = 0;
    private final BitSet remainingExits;

    public static void main(String[]args){
        int side = 20;
        Walker walker = null;
        int total = 0;
        int featureSize = 10;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, featureSize);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, int featureSize){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        this.featureSize = featureSize;

        deleteBars();

        remainingExits = new BitSet();
        for (int yy = 0; yy < height; yy++) {
            if (!pathsNoLongerAvailable.contains(new Edge(width - 2, yy, width - 1, yy))) {
                remainingExits.set(yy);
            }
        }

        while(!walk()){
            if (x == width - 2
                    && remainingExits.get(y)
                    && remainingExits.cardinality() > 1) {
                deletePath(x, y, x + 1, y);
                remainingExits.set(y, false);
            }
        }
    }

    private void deleteBars() {
        for (int xx = 0; xx < width - 1; xx++) {
            for (int yy = 0; yy < height / featureSize + 1; yy++) {
                if (xx != 0) deletePath(xx, featureSize * yy + featureSize - 1, xx, featureSize * yy + featureSize);
                boolean parity = xx % 2 == 0;
                if (yy == 0) parity ^= true; // First path should be inverted
                for (int i = 0; i < featureSize && featureSize * yy + i < height; i++) {
                    if (i == 0 && !parity) continue;
                    if ((i == featureSize - 1 || featureSize * yy + i == height - 1) && parity) continue;
                        deletePath(xx, featureSize * yy + i, xx + 1, featureSize * yy + i);
                }
            }
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = ThreadLocalRandom.current().nextInt(possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        Set<Point> reachable = new HashSet<>();
        Queue<Point> next = new LinkedList<>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge) {
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    public static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }

        @Override
        public String toString() {
            return start.toString() + "-" + end.toString();
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 83 * hash + Objects.hashCode(this.start);
            hash = 83 * hash + Objects.hashCode(this.end);
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Edge other = (Edge) obj;
            if (!Objects.equals(this.start, other.start)) {
                return false;
            }
            if (!Objects.equals(this.end, other.end)) {
                return false;
            }
            return true;
        }


    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
        @Override
        public String toString() {
            return "(" + x + "," + y + ")";
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 23 * hash + this.x;
            hash = 23 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }


    }
}

Il y a quelques optimisations que je pourrais faire mais que je n'ai pas faites, et cela ne prend en charge aucune des ruses adaptatives que la moitié utilise.

Quoi qu'il en soit, voici les résultats pour différentes featureSizevaleurs:

20 (1 path):  156284 
10 (2 paths): 188553
7 (3 paths):  162279
5 (4 paths):  152574
4 (5 paths):  134287
3 (7 paths):  118843
2 (10 paths): 94171
1 (20 paths): 64515

Et voici une carte avec 3 chemins:

 _   _   _   _   _   _   _   _   _    
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|_   _   _   _   _   _   _   _   _   _|
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|  _   _   _   _   _   _   _   _   _  |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
|_| |_| |_| |_| |_| |_| |_| |_| |_| | |

James_pic
la source

Merci pour cela. Il semble que tout l'argent soit maintenant dans la supercherie adaptative :)

Pourquoi coupez-vous le chemin en bas? Vous pouvez couper le chemin entre le chemin inférieur et le chemin du milieu pour un meilleur score, je pense.

moitié du

@justhalf Oui, je pense que oui. J'ai décidé de ne pas le faire, car cela aurait rendu le code plus compliqué, et cela n'aurait pas été une entrée gagnante de toute façon.

James_pic

1

Les trois chemins (en supposant un chemin optimal à 3) seront en moyenne identiques à un chemin unique: Nsoit la longueur du chemin (qui est n^2-1), le chemin unique nécessitera en moyenne des N^2déplacements, tandis que les trois chemins (N/3)^2 + (2N/3)^2 + (2N/3)^2 = N^2plus une valeur relativement petite, donc trois chemins n'a pas de gain significatif sur un seul chemin, encore moins double chemin. (Le calcul est basé sur le résultat de probabilité qui indique que le déplacement aléatoire sur la voie 1-D de longueur Nnécessite en moyenne de N^2déplacement d'une extrémité à l'autre.)

justhalf

@justhalf Nice. J'avais du mal à trouver un bon argument de premier principe pour expliquer pourquoi 2 était le meilleur, mais cela le résume.

James_pic

2

131k (20x20)

Ma première tentative a été de supprimer tous les bords horizontaux à l'exception des rangées supérieure et inférieure, puis chaque fois que le promeneur atteignait le bas d'une colonne, je retirais le bord devant lui, jusqu'à ce qu'il ait visité le bas de chaque colonne et enfin pouvoir atteindre la sortie. Cela s'est traduit par une moyenne de 1/8 d'autant d'étapes que l'approche de marche 1d de @ PeterTaylor.

Ensuite, j'ai décidé d'essayer quelque chose d'un peu plus détourné. J'ai divisé le labyrinthe en une série de chevrons creux imbriqués et je lui demande de parcourir le périmètre de chaque chevron au moins 1,5 fois. Cela a une durée moyenne d'environ 131k pas.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <math.h>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':' ';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                if (r==0 || r==H-1 || c==0 || c==W-1) maze[r][c]=0; // edges
                else if (r%2) { // rows with cells and E/W paths
                    if (c%2) maze[r][c] = 9; // col with cells
                    else if (r==1 || r==H-2) maze[r][c]=1; // E/W path on N/Smost row
                    else if (c>r) maze[r][c]=1; // E/W path on chevron perimeter
                    else maze[r][c]=0; // cut path between cols
                } else { // rows with N/S paths
                    if (c%2==0) maze[r][c] = 0; // empty space
                    else if (c==1 || c==W-2) maze[r][c]=1; // N/S path on E/Wmost row
                    else if (r>c) maze[r][c]=1; // N/S path on chevron perimeter
                    else maze[r][c]=0;
                }
            }
        }
        int progress = 0;
        int first_cut = 0;
        x=0;
        y=0;
        if(DEBUG) print_maze();
        long long turn = 0;
        while (x!=X-1||y!=Y-1) {
            if(DEBUG) std::cin.ignore();
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
            int exit_choice = -1;
            do {
                if (rand()%exits == 0) {
                    exit_choice = exits;
                    break;
                } else {
                    exits--;
                }
            }while(exits);
            int dx=0, dy=0;
            --exits;
            if (maze[r-1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = -1;
                    dx = 0;
                }
            }
            if (maze[r][c+1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = 1;
                }
            }
            if (maze[r+1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 1;
                    dx = 0;
                }
            }
            if (maze[r][c-1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = -1;
                }
            }
            x+=dx;
            y+=dy;
            if (first_cut==0) {
                if(x==X-1 && y==progress*2+1) {
                    first_cut = 1;
                    maze[y*2+2][x*2+1]=0;
                }
                if(y==Y-1 && x==progress*2+1) {
                    first_cut = 2;
                    maze[y*2+1][x*2+2]=0;
                }
            }
            else if (first_cut==1) {
                if (y==Y-1 && x==progress*2) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
                else if (y==Y-2 && x==progress*2+1) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
            }
            else if (first_cut==2) {
                if (x==X-1 && y==progress*2) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
                else if (x==X-2 && y==progress*2+1) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
            }
            if(DEBUG) print_maze();
        }
        // printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}

Sparr
la source

0

Ne fais rien

Étant donné que l'homme se déplace au hasard, on pourrait penser que la suppression d'un nœud n'augmentera que ses chances de rentrer chez lui à long terme.

Tout d'abord, examinons le cas unidimensionnel, cela peut être réalisé en supprimant les nœuds jusqu'à ce que vous vous retrouviez avec un chemin ondulé, sans délais ni cycles, qui visite (presque) chaque point de grille. Sur une N x Ngrille, la longueur maximale d'un tel chemin est L = N*N - 2 + N%2 (98 pour une grille 10x10). Marcher le long du chemin peut être décrit par une matrice de transition générée par T1d.

(La légère asymétrie rend difficile la recherche d'une solution analytique, sauf pour les matrices très petites ou infinies, mais nous obtenons une solution numérique plus rapidement qu'il ne faudrait de toute façon pour diagonaliser la matrice).
Le vecteur d'état a un seul 1à la position de départ et après les Kétapes (T1d**K) * statenous donne la distribution de probabilité d'être à une certaine distance du départ (ce qui équivaut à faire la moyenne de toutes 2**Kles promenades possibles le long du chemin!)

Exécuter la simulation pour les 10*L**2étapes et enregistrer le dernier élément du vecteur d'état après chaque étape, ce qui nous donne la probabilité d'avoir atteint l'objectif après un certain nombre total d'étapes - la distribution de probabilité cumulée cd(t). La différencier nous donne la probabilité pd'atteindre l'objectif exactement à un certain moment. Pour trouver le temps moyen que nous intégrons t*p(t) dt
Le temps moyen pour atteindre l'objectif est proportionnel à L**2avec un facteur qui va très vite à 1. L'écart type est presque constant à environ 79% du temps moyen.
Ce graphique montre le temps moyen pour atteindre l'objectif pour différentes longueurs de trajet (correspondant à des tailles de grille de 5x5 à 15x15) entrez la description de l'image ici

Voici à quoi ressemble la probabilité d'atteindre l'objectif. La deuxième courbe semble remplie car à chaque pas de temps impair, la position est étrange et ne peut donc pas être au but. entrez la description de l'image ici

De cela, nous pouvons voir que la stratégie à double voie équilibrée fonctionne mieux ici. Pour les grilles plus grandes, où les frais généraux liés à la création de plus de chemins sont négligeables par rapport à leur taille, il serait préférable d'augmenter le nombre de chemins, de la même manière que Peter Taylor l'a décrit, mais en gardant les longueurs équilibrées.

Et si nous ne supprimons aucun nœud?

Nous aurions alors deux fois plus de nœuds praticables, plus quatre directions possibles au lieu de deux. Il semblerait que cela rend très peu probable que vous arriviez à quelque chose. Cependant, les simulations montrent le contraire, après seulement 100 étapes sur une grille 10x10, l'homme est très susceptible d'atteindre son objectif, donc le piéger dans les îles est une tentative futile, car vous traitez un N**2long chemin sinueux potentiel avec un temps d'achèvement moyen de N**4pour une île qui passe par N**2étapes

probabilité d'une marche sur une grille 2D

from numpy import *
import matplotlib.pyplot as plt

def L(N): # maximal length of a path on an NxN grid
    return N*N - 2 + N%2

def T1d(N): # transition along 1d path
    m = ( diag(ones(N-1),1) + diag(ones(N-1),-1) )/2.
    m[1,0] = 1
    m[-2,-1] = 0
    m[-1,-1] = 1
    return m

def walk(stepmatrix, state, N):
    data = zeros(N)
    for i in xrange(N):
        data[i] = state[-1]
        state = dot(stepmatrix, state)
    return data

def evaluate(data):
    rho = diff(data)/data[-1]
    t = arange(len(rho))
    av = sum(rho*t)
    stdev = sum((t-av)**2 * rho)**.5
    print 'average: %f\nstd: %f'%(av, stdev)
    return rho, av, stdev

gridsize = 10
M = T1d(L(gridsize))
initpos = zeros(L(gridsize))
initpos[0] = 1
cd = walk(M, initpos, L(gridsize)**2*5)

plt.subplot(2,1,1)
plt.plot(cd)
plt.title('p of reaching the goal after N steps')
plt.subplot(2,1,2)
plt.plot(evaluate(cd)[0])
plt.title('p of reaching the goal at step N')
plt.show()


''' 
# uncomment to run the 2D simulation
# /!\ WARNING /!\ generates a bunch of images, dont run on your desktop

def links(k,n):
    x = [k-n, k+n]
    if k%n != 0: x.append(k-1)
    if k%n != n-1: x.append(k+1)
    x = [i for i in x if 0<= i <n*n]
    return x

N = 10 # gridsize    

MM = zeros((N*N, N*N)) # build transition matrix
for i in range(N*N):
    temp = links(i,N)
    for j in temp: MM[i,j] = 1./len(temp)
MM[:,-1] = zeros(N*N)
MM[-1,-1] = 1

pos = zeros(N*N)
pos[0] = 1
for i in range(N*N):
    plt.imsave('grid_%.2d'%i, kron(pos.reshape((N,N)), ones((10,10))), cmap='gray')
    pos = dot(MM, pos)
'''

DenDenDo
la source

+1 pour l'effort et de jolis graphiques. Mais cela ne répond pas à la question, et les deux premiers mots sont contradictoires avec la conclusion de votre analyse. Et, vous devez vraiment étiqueter les axes de vos graphiques. Pour quelle taille de grille votre graphique de probabilité est-il applicable?

moitié du

De belles photos mais je ne suis pas sûr que vous ayez la bonne question. Par exemple "Puisque l'homme se déplace au hasard, on pourrait penser que supprimer n'importe quel nœud ne fera qu'augmenter ses chances de rentrer chez lui à long terme.". 1) l'homme finira toujours par rentrer chez lui selon les règles qui sont définies, ce qui ne semble pas pertinent et 2) nous supprimons les arêtes et non les nœuds.

Comment ralentir un ivrogne sur le chemin du retour

Réponses:

230 794,38 sur 20x20, 100 000 courses

Soumissions précédentes

Section Expériences

Chemin unique

Île (niveau 0)

Chemin double

Île (niveau 1)

Île (niveau 2)

Île (niveau 3)

Île (niveau 4)

Conclusion

Code

227934 (20x20)

135.488.307,9 pour 98x98

199094.3 pour 20x20

Approche à 4 voies, 213k

Pour ceux qui ne veulent pas réinventer la roue

64,281

188k, avec 2 chemins

131k (20x20)

Ne fais rien

Et si nous ne supprimons aucun nœud?