Au secours, je suis piégé dans une usine infinie!

26

Ce défi est vaguement inspiré par le jeu Zachtronics Infinifactory .

Vous obtenez une vue de haut en bas d'une grille rectangulaire de convoyeurs, représentée par >v<^. Il peut y avoir des cellules sans convoyeurs, représentées par des espaces. Voici un exemple:

> <vv    <
 v ^ >v v 
  >v^^>vv^
    ^>^ v 
>  v<v  >>
  >v v<^  

Cette configuration est implicitement entourée d'un nombre infini d'espaces.

De plus, on vous donne les dimensions d'une cargaison rectangulaire qui est placée sur les convoyeurs dans le coin supérieur gauche de la grille. Votre tâche consiste à déterminer si la cargaison finit par s'arrêter ou si elle finira par se déplacer en boucle.

Bien sûr, la cargaison est susceptible de couvrir plusieurs convoyeurs à la fois, voici donc les règles pour déterminer la direction de la cargaison à chaque étape:

  1. Les convoyeurs opposés s'annulent. Donc, si une cargaison 3x2 couvre l'un des correctifs suivants (délimités par des traits d'union et des tuyaux pour plus de clarté), le résultat serait le même:

    +---+   +---+   +---+
    |>>^|   |  ^|   |v^^|
    |^<<|   |^  |   |^^v|
    +---+   +---+   +---+
    

    Il en va de même pour ceux-ci:

    +---+   +---+   +---+
    |v^<|   |   |   |><>|
    |>>>|   |>> |   |>><|
    +---+   +---+   +---+
    

    Étant donné que la position exacte d'un convoyeur sous la cargaison n'est pas pertinente, peu importe les paires que vous annulez.

    Cette annulation s'applique avant les autres règles. Par conséquent, pour les autres règles, il n'y aura que des convoyeurs dans au plus deux directions.

  2. Si la cargaison ne recouvre aucun convoyeur (soit parce que tous les convoyeurs annulent, parce qu'elle ne couvre que les espaces, soit parce qu'elle s'est complètement éloignée de la grille), elle s'arrête.
  3. Si la cargaison couvre plus de convoyeurs dans une direction que dans l'autre, la cargaison se déplace dans cette direction. Par exemple, si une cargaison 3x2 couvrait le patch suivant

    >>
    ^>^
    

    il se déplacerait vers la droite, car il y en a plus >que ^. D'un autre côté, s'il couvrait

    >>^
      ^
    

    cette règle ne s'appliquerait pas, car il y a un lien entre >et ^.

  4. Cela ne laisse que les cas où il y a un lien entre des directions adjacentes (un lien entre des directions opposées aurait été annulé). Dans ce cas, la cargaison continue de se déplacer le long de l'axe dans lequel elle se déplace déjà. Par exemple, si une cargaison 3x2 se déplaçant à droite ou à gauche recouvre maintenant le patch

    >>^
    ^  
    

    il se déplacerait vers la droite. S'il était arrivé sur ce patch en montant ou en descendant, il se déplacerait maintenant à la place. Si ce type de conflit se produit à la toute première étape de la simulation, supposez que la cargaison se déplaçait vers la droite.

Exemples détaillés

Considérez la grille du convoyeur en haut et une cargaison 3x2. Ce qui suit est une visualisation étape par étape du processus. Chaque étape se compose de la grille, avec la cargaison représentée par #, une petite boîte qui montre les convoyeurs couverts par la cargaison, une autre boîte avec les convoyeurs après annulation, et la règle qui détermine où la cargaison se déplace:

 ###vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <
 ###^ >v v     ###^ >v v      v ^ >v v      v ^ >v v      v ^ >v v      v ^ >v v 
   >v^^>vv^    ###v^^>vv^    ###v^^>vv^     ###^^>vv^      ###^>vv^      >###>vv^
     ^>^ v         ^>^ v     ### ^>^ v      ###^>^ v       ###>^ v        ###^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>
   >v v<^        >v v<^        >v v<^        >v v<^        >v v<^        >v v<^  

+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+
|> <|  |   |  | v |  | v |  |  >|  |  >|  | >v|  | >v|  |>v^|  |> ^|  |v^^|  | ^^|
| v |  | v |  |  >|  |  >|  |   |  |   |  |   |  |   |  |  ^|  |   |  | ^>|  |  >|
+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+

   Rule 3        Rule 4        Rule 3        Rule 4        Rule 4        Rule 3

 ================================================================================

 > <vv    <    > <###   <    > <vv    <
  v ###v v      v ###v v      v ###v v 
   >###>vv^      >v^^>vv^      >###>vv^
     ^>^ v         ^>^ v         ^>^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>
   >v v<^        >v v<^        >v v<^  

+---+  +---+  +---+  +---+  +---+  +---+
|^ >|  |  >|  |vv |  | v |  |^ >|  |  >|
|v^^|  | ^^|  |^ >|  |  >|  |v^^|  | ^^|
+---+  +---+  +---+  +---+  +---+  +---+

   Rule 3        Rule 4        Rule 3

À ce stade, la cargaison entre dans une boucle entre les deux dernières images.

Considérez maintenant un cargo 2x3 à la place:

 ##<vv    <    >##vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <
 ## ^ >v v      ##^ >v v      ##^ >v v      v ^ >v v      v ^ >v v      v ^ >v v 
 ##>v^^>vv^     ##v^^>vv^     ##v^^>vv^     ##v^^>vv^      ##^^>vv^      >v^^>vv^
     ^>^ v         ^>^ v      ## ^>^ v      ## ^>^ v       ##^>^ v       ##^>^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>    >##v<v  >>    > ##<v  >>    > ##<v  >>
   >v v<^        >v v<^        >v v<^        >v v<^        >v v<^        ## v<^  

 +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+
 |> |  |> |    | <|  |  |    |v |  |v |    | >|  | >|    |>v|  |>v|    |  |  |  |
 | v|  | v|    |v |  |v |    | >|  | >|    |  |  |  |    |  |  |  |    | v|  | v|
 |  |  |  |    | >|  |  |    |  |  |  |    |  |  |  |    | v|  | v|    |>v|  |>v|
 +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+

   Rule 4        Rule 3        Rule 4        Rule 3        Rule 3        Rule 3

 ================================================================================

 > <vv    <    > <vv    <    > <vv    <
  v ^ >v v      v ^ >v v      v ^ >v v 
   >v^^>vv^      >v^^>vv^      >v^^>vv^
     ^>^ v         ^>^ v         ^>^ v 
 > ##<v  >>    >  v<v  >>    >  v<v  >>
   ## v<^        ## v<^        >v v<^  
   ##            ##            ##
                 ##            ##
                               ##

 +--+  +--+    +--+  +--+    +--+  +--+
 | v|  | v|    |>v|  |>v|    |  |  |  |
 |>v|  |>v|    |  |  |  |    |  |  |  |
 |  |  |  |    |  |  |  |    |  |  |  |
 +--+  +--+    +--+  +--+    +--+  +--+

   Rule 3        Rule 4        Rule 2

Dans la dernière étape, la règle 2 s'applique parce que la cargaison a quitté la grille, donc elle s'arrête et il n'y aura pas de boucle.

Règles et hypothèses

Votre entrée sera la grille du convoyeur comme décrit ci-dessus ainsi que la largeur et la hauteur de la cargaison. Vous pouvez prendre ces trois paramètres dans n'importe quel ordre et format pratique. Pour la grille, cela signifie que vous pouvez lire une seule chaîne avec des lignes séparées par des sauts de ligne ou d'autres caractères, ou un tableau de chaînes, ou un tableau de tableaux de caractères, tant que les cellules de la grille individuelles sont toujours représentées par les caractères >v<^et les espaces.

Vous devez sortir une valeur véridique si la configuration aboutit à une boucle d'au moins deux images ou une valeur falsifiée si la cargaison s'arrête .

Vous pouvez supposer que la grille sera remplie d'un rectangle avec des espaces et que la cargaison s'insérera initialement dans la grille.

Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), la valeur de retour de la fonction ou le paramètre de la fonction (out).

Il s'agit du code golf, donc la réponse la plus courte (en octets) l'emporte.

Cas de test

Les cas de test sont regroupés par grilles.

Grid (2x2):

>v
^<

Width  Height  Loop?
1      1       True
1      2       True
2      1       True
2      2       False

Grid (3x3):

> v

^ <

Width  Height  Loop?
1      1       False
1      2       False
1      3       False
2      1       False
2      2       True
2      3       True
3      1       False
3      2       True
3      3       False

Grid (4x3):

>^>v
v^v 
^ <<

Width  Height  Loop?
2      2       False

Grid (6x5):

>v>v>v
^v^v^v
^v^v^v
^>^>^v
^<<<<<

Width  Height  Loop?
1      1       True
1      2       False
2      1       True
2      2       True
2      4       True
2      5       False
3      1       False
3      2       True
3      3       True
3      5       True
6      2       False
6      3       True
6      5       False

Grid (10x6):

> <vv    <
 v ^ >v v 
  >v^^>vv^
    ^>^ v 
>  v<v  >>
  >v v<^  

Width  Height  Loop?
1      1       False
2      3       False
2      6       False
3      2       True
5      4       False
6      1       True
10     6       False

En tant qu'ensemble supplémentaire de cas de test, considérez que toute entrée où la grille se compose uniquement d'espaces doit donner un résultat falsifié.

J'ai vérifié tous les cas de test manuellement, alors faites-moi savoir si vous pensez que j'ai fait une erreur.

Martin Ender
la source
10
Fitting music
Fatalize
4
@Fatalize Je reçois des flashbacks Pokémon Twitch Plays ...
undergroundmonorail
"Votre entrée sera la grille de convoyeur comme décrit ci-dessus ainsi que la largeur et la hauteur de la cargaison. Vous pouvez prendre ces trois paramètres dans n'importe quel ordre et format pratique." - cela signifie-t-il que la grille du convoyeur peut être prise comme un tableau de réseaux? Autrement dit, une grille 2x2 avec [^^/v<]devient [[0,1] [0,1];[0,-1] [-1,0]]? Ou voulez-vous dire que c'est à nous de décider si c'est STDIN, une entrée de chaîne, une entrée de tableau de caractères, etc., mais cela doit toujours être sous la forme de ^, v,> et <?
Glen O
@GlenO Vous pouvez prendre une chaîne séparée par une nouvelle ligne (ou un autre caractère), un tableau de chaînes ou un tableau de tableaux de caractères, mais chaque cellule doit toujours être représentée par les caractères ><^vou un espace. Je vais clarifier cela.
Martin Ender
Alors, que se passe-t-il si la cargaison entre dans un conflit où la direction continue n'est pas l'un des choix? Autrement dit, s'il se déplaçait à droite, et doit maintenant choisir entre haut et gauche.
Joshua

Réponses:

7

Rubis, 306 298 251 204 198

->g,w,h{m=->y,x,d,v=[]{q=y,x
r=->s{([""]*h+g)[y+h,h].map{|l|(?x*w+l)[x+w,w]}.join.count s}
z=k=r[?v]-r[?^],j=r[?>]-r[?<]
q[d=[d,1,0][j*j<=>k*k]]+=z[d]<=>0
v&[q<<d]!=[]?q!=v[-1]:m[*q,v<<q]}
m[0,0,1]}

Edit: Merci beaucoup à Ventero qui a beaucoup raccourci le code en appliquant des astuces incroyables!

Entrée et sortie

Le code représente une fonction ruby ​​qui prend trois paramètres:

  • la grille, représentée comme un tableau de chaînes (chaque ligne est une chaîne différente)
  • la largeur de la cargaison
  • la hauteur de la cargaison

Il revient 1(véridique) s'il y a une boucle, ou nil(faux) si la cargaison se repose.

Les tests

Ici, il passe tous les tests de Martin: http://ideone.com/zPPZdR

Explication

Il n'y a aucune astuce intelligente dans le code; c'est une mise en œuvre assez simple des règles.

Dans le code ci-dessous, moveest une fonction récursive qui effectue un mouvement selon les règles, et:

  • retourne véridique en cas de boucle
  • renvoie la fausse en cas de repos
  • sinon, s’appelle pour exécuter le prochain mouvement

Une version plus lisible est disponible ici .

Remarque: le code golfé a subi plusieurs modifications et n'est plus similaire à la version lisible.

Cristian Lupascu
la source
Puisqu'il n'importe pas s'il rcontient des entrées supplémentaires en plus des quatre directions, r[y>=0&&x>=0&&g[y]&&g[y][x]]+=1devrait économiser quelques octets.
Ventero
J'ai pris la liberté de jouer au golf un peu plus loin, j'espère que cela ne vous dérange pas: ideone.com/k69BmH
Ventero
@Ventero Wow, vous avez fait des choses incroyables au code. Je n'aurais jamais pensé à transformer le hachage en lambda. J'essayais certaines de mes idées pour raccourcir le programme, mais j'étais loin de ce que vous avez fait. Merci beaucoup!
Cristian Lupascu
2
Je suis descendu à 200 grâce à une gestion un peu plus courte des indices négatifs, je suppose que je vais en rester là pour l'instant: ideone.com/k69BmH
Ventero
2
En fait, 198: ideone.com/ptKrzf :)
Ventero
8

Python 2, 207 octets

def f(L,w,h,u=0,v=0,D=1,S=[]):a,b,c,d=map(`[r[u*(u>0):u+w]for r in L[v*(v>0):v+h]]`.count,"v^><");D=cmp(abs(a-b),abs(c-d))<D;T=u,v,D;return T in S or a-b|c-d and f(L,w,h,u+cmp(c,d)*D,v+cmp(a,b)*0**D,D,S+[T])

Saisissez la grille sous forme de liste de lignes, par exemple

['>v>v>v', '^v^v^v', '^v^v^v', '^>^>^v', '^<<<<<']

suivi de la largeur et de la hauteur. Renvoie 0ou en Trueconséquence.

Explication

def f(L,          # Grid
      w,h,        # Width, height of cargo
      u=0,v=0,    # Position of top-left of cargo, initially (0, 0)
      D=1,        # Moving left/right = 1, up/down = 0
      S=[]        # Seen (pos, axis) pairs, initially empty
     ):     

     # Arrows under cargo - no need for "".join since we only need to count v^<>
     A = `[r[u*(u>0):u+w]for r in L[v*(v>0):v+h]]`

     # Count for each arrow
     a,b,c,d=map(A.count,"v^><")

     # Golfed form of abs(a-b) < abs(c-d) or (abs(a-b) == abs(c-d) and D == 1)
     D=cmp(abs(a-b),abs(c-d))<D
     T=u,v,D

     return (T in S                # Return True if (pos, axis) previously seen
             or a-b|c-d               # Return 0 if all conveyors cancel
             and f(L,w,h,             # Otherwise, recurse
                   u+cmp(c,d)*D,      # Update u if moving left/right
                   v+cmp(a,b)*0**D,   # Update v if moving up/down
                   D,
                   S+[T]          # Add (pos, axis) to seen
                  )
            )
Sp3000
la source
Vous ne pouvez pas le raccourcir en l'assignant cmpà une variable?
Blue
Est-il suffisant de détecter des cycles en vérifiant les positions déjà visitées? Sur la base de la règle 4, l'étape suivante peut également être influencée par la direction précédente. Il semble donc possible que vous puissiez arriver à la même position deux fois, mais ne pas avoir de cycle parce que vous vous déplacez dans des directions différentes en fonction de différentes directions précédentes.
Reto Koradi
@muddyfish Ça n'atteindrait que l'équilibre
Sp3000
@RetoKoradi Avec un peu de chance
Sp3000
Oui, l'ajout Dà la clé de position devrait le faire.
Reto Koradi
8

Julia - 394 300 246 214 octets

f(A,x,y)=(Z=sign;(S,T)=size(A);X=x+1;Y=y+1;G=fill(5,S+2y,T+2x);G[Y:S+y,X:T+x]=A;C=0G;D=1;while C[Y,X]!=D C[Y,X]=D;i,j=sum(i->1-[19 8]i%82%3,G[Y:Y+y-1,X:X+x-1]);D=Z(2i^2-2j^2+(i!=0)D);X+=Z(i+D*i);Y+=Z(j-D*j)end;D^2)

Renvoie 1 si la cargaison fait une boucle et 0 si elle s'arrête. Ce n'est pas "strictement" vrai / faux, en ce que Julia n'autorise pas 0 et 1 dans des contextes booléens ... mais je considère les valeurs xqui bool(x)==truesont vraies et bool(x)==falsesont fausses.

L'entrée Adoit prendre la forme d'un tableau de caractères. Si vous copiez / collez la grille du convoyeur, vous devrez la mettre sous la forme appropriée. Pour vous éviter d'avoir à le manipuler manuellement, utilisez ce qui suit:

A=foldl(hcat,map(collect,split("""(PASTE GRID HERE)""","\n")))'

Où évidemment, (PASTE GRID HERE) devrait être remplacé par la grille elle-même. Revérifiez les espaces à la fin de chaque ligne, pour vous assurer qu'il a réellement tous les espaces (il ne vérifie pas que toutes les lignes sont de longueur égale). Notez que cette ligne ne fait pas partie du code de solution réel, juste un morceau de code pratique pour faciliter l'utilisation du code de solution.

Non golfé:

function f(A,x,y)
  # Determine size of grid for use later
  (S,T)=size(A)
  # Initialise starting position (performed here to save characters)
  X=x+1
  Y=y+1
  # Create an expanded field that is functionally "spaces" (to provide
  # spaces at edges for the cargo to stop in)
  G=fill(5,S+2y,T+2x)
  # Put the conveyor grid into centre of the expanded field
  G[Y:S+y,X:T+x]=A
  # Create an array storing the most recent movement direction:
  # will use 1=horizontal, -1=vertical, 0=stopped
  C=0G
  # Initialise current direction (same system as C)
  D=1
  # Loop until it finds itself repeating a coordinate/direction pair
  while C[Y,X]!=D
    # Mark current coordinate/direction pair in array
    C[Y,X]=D
    # Determine the net coordinate pairing, stored in two variables
    # for golf purposes *SEE NOTE*
    i,j=sum(i->1-[19 8]i%82%3,G[Y:Y+y-1,X:X+x-1])
    # Determine new movement axis (if D=0, cargo stopped)
    D=sign(2i^2-2j^2+(i!=0)D)
    # Update X or Y depending on signs of D and the appropriate direction
    X+=sign(i+D*i)
    Y+=sign(j-D*j)
  end
  # if D=±1, return 1 (cargo is still moving), otherwise return 0
  return D^2
end

Remarque: 1-[19 8]i%82%3a été choisi pour mapper les cinq caractères possibles aux paires de coordonnées appropriées par la méthode la plus efficace que j'ai pu trouver. C'est aussi la raison d'utiliser 5 pour remplir les espaces lors de la création G- c'est un caractère à un chiffre qui correspond à [0 0].

Exemple d'utilisation:

julia> A=foldl(hcat,map(collect,split(""">v>v>v
       ^v^v^v
       ^v^v^v
       ^>^>^v
       ^<<<<<""","\n")))';

julia> f(A,2,1)
true

julia> f(A,3,3)
true

julia> f(A,5,2)
false
Glen O
la source
f(A,x,y)=est plus court que f=(A,x,y)->.
Alex A.
@AlexA. - vrai, mais alors, je supprimerai probablement le f=et en ferai une fonction anonyme lorsque j'aurai fini de jouer au golf.
Glen O
1
Ce sera la même longueur s'il s'agit d'une fonction nommée par rapport à une fonction anonyme lorsqu'il y a plusieurs paramètres. f()=contre ()->.
Alex A.