Balle de microgravité

33

Vous êtes sur une station spatiale intergalactique avancée. Un de vos amis qui est mineur dans l’étude de la gravité vient de créer un jeu qui consiste à utiliser la microgravité comme moyen de déplacer une balle.

Elle vous tend un petit contrôleur avec quatre flèches directionnelles et un labyrinthe ressemblant à une structure avec un ballon assis à gauche. Elle commence à expliquer le fonctionnement du jeu.

  • Vous avez 2 boutons directionnels, gauche <et droite >.
  • Vous avez également 2 boutons de gravité, de haut en ^bas v(au moins de votre cadre de référence)
  • Vous utiliserez ces boutons fléchés pour déplacer la balle sur votre écran.

"Maintenant, il y a des règles à suivre." elle dit

  1. Toutes les plates-formes doivent être traversées avant d'arriver à la tasse \ /
  2. Les flèches < > ^ vseront utilisées pour spécifier le mouvement de la balle
  3. La gravité est ^ v(de haut en bas). Cela déplace le ballon jusqu'à la prochaine plate-forme dans cette direction. (La distance n'est pas calculée pour monter et descendre)
  4. Perdre le ballon, c'est mauvais! Ne tombez pas sur le bord et ne modifiez pas la gravité trop tôt pour que votre balle n'atteigne jamais une plateforme.
  5. Le mouvement est compté en pas de < >
  6. La balle peut entrer dans la coupe de n'importe quelle direction tant que la Règle 1 est suivie
  7. Vous devez spécifier la direction de la gravité afin que votre balle ne flotte pas
  8. Le mouvement peut être aléatoire tant que les règles 1 et 4 sont suivies
  9. Pour les cas qui ne peuvent pas être résolus, indiquez False ou Invalid.

Exemple simple de ballon, plateforme et coupe:

v
o
---\ /

v>

 o
---\ /

v>>

  o
---\ /

v>>>

   o
---\ /

v>>>>


---\o/

Exemple de nouveau passage sur la même plate-forme.

v    

 o
 ----

\ /-------

v>   

  o
 ----

\ /-------

v>>

   o
 ----

\ /-------

v>>>

    o
 ----

\ /-------

v>>>>


 ----
     o
\ /-------

v>>>>>


 ----
      o
\ /-------

v>>>>>>


 ----
       o
\ /-------

v>>>>>>>


 ----
        o
\ /-------

v>>>>>>>>


 ----
         o
\ /-------

v>>>>>>>><<<<<<<< # move all the way to the left to get to the cup


 ----

\o/-------

Exemple de gravité de commutation

v
   --/ \

o
----

v>
   --/ \

 o
----

v>>
   --/ \

  o
----

v>>>
   --/ \

   o
----

v>>>^
   --/ \
   o

----

v>>>^>
   --/ \
    o

----

v>>>^>>
   --/ \
     o

----

v>>>^>>>
   --/o\


----

Tâche

Votre tâche est de créer un programme qui utilisera une représentation ASCII d’un cours. Et la sortie d' une série de flèches <>^vreprésentant la direction et l' attraction gravitationnelle de déplacer une boule odans l' ensemble platformsdans une tasse.

Les règles de golf standard s'appliquent

Cas de test

Entrée (situation dans laquelle la gravité est activée)

         ----   --/ \
---    --
o

  ------    -----

Sortie

^>>v>>>>>^>>>>>v>>>>^>>>

entrez la description de l'image ici

Entrée (une situation où la direction est changée)

       ---
o   
----
    ---

     -----  

    --\ /

Sortie

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

entrez la description de l'image ici

Entrée (situation dans laquelle vous devez traverser deux fois la même plate-forme)

 o
 ------

  ------

 ------ 

\ /------

Sortie

v>>>>>><<<<<<>>>>>>><<<<<<

entrez la description de l'image ici

Mauvais cas, le programme doit produire Falsy pour ces

Le ballon n'a aucun moyen de se rendre à la prochaine plateforme

o
--- ---

La balle flotterait dans l'espace

---
o
   ---

Une situation où la balle arrive à la coupe, mais toutes les plates-formes ne sont pas traversées.

o
----
    ----
        \ /----
code-golf ascii-art decision-problem tisaconundrum
la source
4
La règle 1 rend cela assez difficile ... hmmm ...
JungHwan Min
Le puzzle sera-t-il toujours résoluble? De plus, je pense que vous devriez inclure un scénario de test nécessitant un retour en arrière.
FryAmTheEggman
Oui, les énigmes devraient toujours pouvoir être résolues. Les lacunes ou les sauts qui perdent la balle ou les situations qui rendent le labyrinthe insoluble ne seront pas résolus.
tisaconundrum
4
@JungHwanMin La règle 1 est exactement la raison pour laquelle c'est un défi et non pas trivial.
Erik l'Outgolfer
2
Je ne me suis jamais senti aussi loin dans un terrier de lapin à propos d'une question de
code sportif

Réponses:

11

Pyth, 431 octets

C’est mon premier programme Pyth (c’est en fait mon premier programme dans n’importe quel langage de code-golf), ce qui signifie qu’il peut probablement encore être amélioré.

Jmmck\:cd\%c.Z"xÚU±Ã@DÅ W,J áDPáÒ­V`ýüw{g$ÍÀÞÇr§o.÷å8èÝÇr{øºy{~1åõ:noßÃú/.yçíäÂ'ëL¢êF¸èÆ\ka´QÒnÒ@tãÒÁµÆ¾õö»bÍH¥¦$¨%5Eyîÿ}ó§ûrh³oÄåËÄqõ XÔHû"\_KYDrGHFN@JGIn=bm:d.*NHHRb)RHDiNTR.turNG.tT;M:jH)hh@JG0DXGHN=Ti+3qG\^HI!},GTK aK,GT aY+eKNI&!g5T}\EjT)N.q;D(GHNT)INIqHhT=ZrGhtTInZhtTXHZ+eTN))).?I&nHhTgGhtTXHhtT+eTH; aK,di2i1r0.z aY+eKk#=N.(Y0(6\vkN)(7\^kN)(8\v\<N)(9\v\>N)(10\^\<N)(11\^\>N

Essayez-le ici (le dernier cas de test a besoin de trop de temps, il doit être testé avec une installation Pyth locale).

Dex Hex du code (utilisé xxd -r <filename>pour décoder):

00000000: 4a6d 6d63 6b5c 3a63 645c 2563 2e5a 2278  Jmmck\:cd\%c.Z"x
00000010: da55 8eb1 8ac3 400c 447f c58d 2057 2c99  [email protected]... W,.
00000020: 4aa0 e144 50e1 d2ad 5660 87fd 84fc 7f77  J..DP...V`.....w
00000030: 7b67 1f24 cdc0 8319 de1c c772 a76f 2ef7  {g.$.......r.o..
00000040: e538 e8dd c772 7bf8 9eba 797b 7e31 e5f5  .8...r{...y{~1..
00000050: 8e3a 6e8f 6fdf c3fa 2f2e 0c79 e717 ede4  .:n.o.../..y....
00000060: c21f 27eb 8395 189a 4c15 140b a28d ea82  ..'.....L.......
00000070: 46b8 e8c6 5c05 1b6b 1d61 b490 0251 d28c  F...\..k.a...Q..
00000080: 6ed2 4087 74e3 1ad2 c1b5 c6be f5f6 1cbb  [email protected]...........
00000090: 6286 cd48 a5a6 24a8 2535 4579 eeff 7df3  b..H..$.%5Ey..}.
000000a0: 8a8a 1613 a7fb 7204 68b3 6fc4 e51b 160c  ......r.h.o.....
000000b0: 1304 cbc4 8a71 f57f 2058 d448 fb22 5c5f  .....q.. X.H."\_
000000c0: 4b59 4472 4748 464e 404a 4749 6e3d 626d  KYDrGHFN@JGIn=bm
000000d0: 3a64 2e2a 4e48 4852 6229 5248 4469 4e54  :d.*NHHRb)RHDiNT
000000e0: 522e 7475 724e 472e 7454 3b4d 3a6a 4829  R.turNG.tT;M:jH)
000000f0: 6868 404a 4730 4458 4748 4e3d 5469 2b33  hh@JG0DXGHN=Ti+3
00000100: 7147 5c5e 4849 217d 2c47 544b 2061 4b2c  qG\^HI!},GTK aK,
00000110: 4754 2061 592b 654b 4e49 2621 6735 547d  GT aY+eKNI&!g5T}
00000120: 5c45 6a54 294e 2e71 3b44 2847 484e 5429  \EjT)N.q;D(GHNT)
00000130: 494e 4971 4868 543d 5a72 4768 7454 496e  INIqHhT=ZrGhtTIn
00000140: 5a68 7454 5848 5a2b 6554 4e29 2929 2e3f  ZhtTXHZ+eTN))).?
00000150: 4926 6e48 6854 6747 6874 5458 4868 7454  I&nHhTgGhtTXHhtT
00000160: 2b65 5448 3b20 614b 2c64 6932 6931 7230  +eTH; aK,di2i1r0
00000170: 2e7a 2061 592b 654b 6b23 3d4e 2e28 5930  .z aY+eKk#=N.(Y0
00000180: 2836 5c76 6b4e 2928 375c 5e6b 4e29 2838  (6\vkN)(7\^kN)(8
00000190: 5c76 5c3c 4e29 2839 5c76 5c3e 4e29 2831  \v\<N)(9\v\>N)(1
000001a0: 305c 5e5c 3c4e 2928 3131 5c5e 5c3e 4e    0\^\<N)(11\^\>N

Explication

L'idée principale de ce programme était d'utiliser des expressions régulières pour modifier les entrées. Pour économiser de l'espace, toutes ces expressions régulières sont contenues dans une chaîne compressée. La première étape du programme consiste à décompresser la chaîne et à la diviser dans une expression régulière unique et les chaînes de remplacement correspondantes.

            .Z"..."     Decompress the string
           c       \_   Split the result into pieces (separator is "_")
  m    cd\%             Split all pieces (separator is "%")
 m ck\:                 Split all sub-pieces (separator is ":")
J                       Assign the result to variable J

Le contenu de la variable Jest alors:

[[['\\\\ /', '=M='], ['/ \\\\', '=W=']],
 [[' (?=[V6M=-])', 'V'], ['o(?=[V6M=-])', '6']],
 [['(?<=[A9W=-]) ', 'A'], ['(?<=[A9W=-])o', '9'], ['(?<=[X0W=-])V', 'X'], ['(?<=[X0W=-])6', '0']],
 [['6V', 'V6'], ['0X', 'X0'], ['6-', '6='], ['0-', '0='], ['6M', 'VE'], ['0M', 'XE']],
 [['A9', '9A'], ['X0', '0X'], ['-9', '=9'], ['-0', '=0'], ['W9', 'EA'], ['W0', 'EX']],
 [['[MW-]']],
 [['[60]']],
 [['[90]']],
 [['V6', '6V'], ['V0', '6X'], ['X6', '0V'], ['X0', '0X']],
 [['6V', 'V6'], ['0V', 'X6'], ['6X', 'V0'], ['0X', 'X0']],
 [['A9', '9A'], ['A0', '9X'], ['X9', '0A'], ['X0', '0X']],
 [['9A', 'A9'], ['0A', 'X9'], ['9X', 'A0'], ['0X', 'X0']]]

KY   Set the variable K to an empty list

La fonction rapplique les substitutions de regex de la liste stockée dans Jl'index Gà toutes les chaînes de la liste H. Il revient dès qu'une des chaînes a été changée.

DrGH                         Define the function r(G,H)
    FN@JG              )     Loop for all entries in J[G]
             m:d.*NH         Regex substitution, replace N[0] with N[1] in all strings in list H
           =b                Store the result in variable b
         In         HRb      If b != H return b
                        RH   Return H

La fonction iest similaire à fonctionner ravec 2 différences. Il applique les substitutions sur une liste transposée (verticale plutôt que horizontale). Il effectue également les substitutions à plusieurs reprises tant que tout est changé.

DiNT          ;   Define the function i(N,T)
           .tT    Transpose the list T
       urNG       Apply r(N,...) repeatedly as long as something changes
    R.t           Transpose the result back and return it

La fonction gvérifie si l'expression régulière de la liste stockée dans Jl'index Gpeut être trouvée dans une chaîne quelconque de la liste H.

M             Define the function g(G,H)
     hh@JG    Get the single regex stored in J[G]
  jH)         Join all strings in H
 :        0   Check if the regex is found anywhere in the joined string

Le reste du code contient la logique de programme réelle. Il effectue une recherche approfondie des mouvements possibles jusqu'à ce qu'une solution soit trouvée. La position dans l'arbre de recherche est uniquement définie par la direction de la gravité et une copie modifiée de l'entrée du programme. Pour éviter le traitement de la même position à plusieurs reprises, les positions traitées sont stockées dans la liste globale K. Les positions qui doivent encore être traitées sont stockées avec la partie correspondante de la solution dans la liste Y.

La modification de l'entrée et l'initialisation de Ket Yest effectuée par le code suivant:

           .z          Get all input as a line list
     i2i1r0            Apply the regular expressions stored in J[0] horizontally, and the the ones from J[1] and J[2] vertically
   ,d                  Create a list with " " (represents "no gravity set") and the modifed input
 aK                    Append the result to the list K
                 eK    Retrieve the appended list again
                +  k   Append "" to the list (represents the empty starting solution)
              aY       Append the result to the list Y

La modification d’entrée fait quelque chose comme ce qui suit. L'entrée:

         ----   --/ \
---    --
o

  ------    -----

est transformé en:

VVVVVVVVV----VVV--=W=
---VVVV--AAAXVVVXAAAA
9AXVVVVXAAAAXVVVXAAAA
AAXVVVVXAAAAXVVVXAAAA
AA------AAAA-----AAAA

Les valeurs ont la signification suivante:

  • - Plate-forme qui doit encore être visitée
  • = Plateforme qui n'a plus besoin d'être visitée
  • M Tasse pouvant être entrée avec la gravité réglée sur "down"
  • W Coupe pouvant être entrée avec la gravité réglée sur "up"
  • V Sans danger pour se déplacer à cet endroit avec la gravité réglée sur "vers le bas"
  • A Sans danger pour se déplacer à cet endroit avec la gravité réglée à "up"
  • X Coffre-fort pour se déplacer à cet endroit indépendamment du réglage de la gravité
  • 6 Ball sur un endroit qui serait marqué comme V
  • 9 Ball sur un endroit qui serait marqué comme A
  • 0 Ball sur un endroit qui serait marqué comme X

La logique utilise des expressions régulières pour effectuer les mouvements. Dans l'exemple ci-dessus, si la gravité est réglée sur "up", nous pouvons remplacer "9A" par "A9" par une expression régulière pour déplacer le ballon vers la droite. Cela signifie qu'en essayant d'appliquer l'expression rationnelle, nous pouvons trouver tous les mouvements possibles.

La fonction Xeffectue des mouvements à billes verticale en fonction du réglage de la gravité actuelle, stocke le résultat dans les listes mondiales Ket Y, et vérifie si une solution a été trouvée.

DXGHN                                             ;   Define the function X(G,H,N)
        +3qG\^                                        Select the correct set of regular expressions based on the current gravity setting G (3 for "v" and 4 for "^")
     =Ti      H                                       Apply i(...,H) and store the result in T 
               I!},GTK                                If [G,T] not in K
                       aK,GT                          Store [G,T] in K 
                             aY+eKN                   Store [G,T,N] in Y 
                                   I&!g5T}\EjT)       If J[5] not found in T and T contains "E" (all platforms visited and ball in cup)
                                               N.q    Print N and exit

La fonction (implémente des contrôles pour les 4 boutons directionnels / gravité. Vous ne pouvez appuyer sur les boutons de gravité que si la gravité actuelle change et si la balle est dans un endroit sûr pour modifier la gravité. Vous ne pouvez appuyer sur les touches directionnelles que si vous pouvez vous déplacer en toute sécurité à l'endroit correspondant.

D(GHNT)                                                    ;   Define the function ( (G,H,N,T)
       IN                           )                          If N is not empty (contains either "<" or ">" representing directional buttons)
         IqHhT                     )                           If H (gravity setting for which this test is performed) is equal T[0] (the current gravity)
              =ZrGhtT                                          Apply r(G,T[1]) and store the result in Z (G is the appropriate regex index for the combination of gravity and directional button, T[1] is the current modified input) 
                     InZhtT       )                            If Z != T[1] (the regex operation changed something, meaning we found a valid move)
                           XHZ+eTN                             Call X(H,Z,[T[2],N]) 
                                     .?                        Else (gravity button pressed)
                                       I                       If ...
                                         nHhT                  H (new gravity setting) is not equal T[0] (current gravity setting) 
                                        &                      ... and ...
                                             gGhtT             J[G] found in T[1] (ball is in an appropriate place to switch gravity) 
                                                  XHhtT+eTH    Call X(H,T[1],[T[2],H])

Enfin la boucle principale. Le premier élément de Yest supprimé à plusieurs reprises et des contrôles sont effectués pour tous les déplacements possibles.

#                                                        Loop until error (Y empty)
 =N.(Y0                                                  Pop first element of Y and store it in the variable N
       (6\vkN)                                           Call ( (6,"v","",N)
              (7\^kN)                                    Call ( (7,"^","",N)
                     (8\v\<N)                            Call ( (8,"v","<",N)
                             (9\v\>N)                    Call ( (9,"v",">",N)
                                     (10\^\<N)           Call ( (10,"^","<",N)
                                              (11\^\>N   Call ( (11,"^",">",N)
Sleafar
la source
Ai-je raison de penser que vous supposez que chaque entrée est soluble? Comme la question dit toujours que les intrants insolubles doivent être détectés, les commentaires suggèrent toutefois que chaque intrant sera résoluble. Je ne sais pas quel est le cas, bien que je pense que votre code ne détecte aucune insolvabilité.
Jonathan Frech
@ JonathanFrech Si l'entrée est insoluble, il n'y aura pas de sortie. Lorsque toutes les possibilités ont été cochées, la Yliste sera vide, la pop générera une erreur et la #boucle se terminera.
Sleafar
1
Lorsque vous supprimez la tasse de l'entrée (`/ \`), le puzzle devient insoluble (car vous ne pouvez pas atteindre la tasse), mais votre programme génère toujours une sortie.
Jonathan Frech
Je ne voulais pas dire ce que votre programme fait, je mentionne que cette entrée de puzzle insoluble génère une sortie.
Jonathan Frech
@ JonathanFrech Vous avez raison. J'essaie simplement de résoudre ce problème, mais j'ai des problèmes d'encodage avec la chaîne compressée.
Sleafar