Une fourmi marche le long des bords (pas des faces) d'un cube en fil de fer. Chaque sommet qu’il rencontre le présente avec une fourche à partir de laquelle deux nouvelles arêtes se ramifient. La fourmi choisit quel chemin tourner - leftou right. Ces directions sont relatives à la fourmi, qui fait face au sommet et se trouve en dehors du cube. Votre but est de déterminer, à partir de la séquence de left/ rightchoix que la fourmi a pris, si elle se termine à la même position qu’elle a commencé.

Par exemple, si la fourmi tourne à gauche quatre fois ( left left left left), elle aura traversé un carré dans le sens anti-horaire et terminé au même endroit où elle a commencé. Mais si ça marche left left left left right, ça finira à un endroit différent du cube. De plus, si cela se produit left right right right left, il se termine sur son bord de départ, mais face au sommet opposé, qui ne compte pas comme la même position.

Le chemin de la fourmi peut répéter des arêtes, y compris l'arête sur lequel elle a commencé, mais ce qui compte est l'endroit où il se termine après la séquence complète.

Ecrivez une fonction nommée qui prend la séquence de tours de la fourmi et indique si la fourmi est revenue à sa position de départ après la séquence. Assigner une fonction sans nom à une variable suffit à en faire une fonction nommée.

(Édition: si votre langue ne peut pas créer de fonction nommée, elle peut également implémenter la fonction avec des entrées et des sorties via STDIN / impression ou la pile. Si cela n'est pas possible, faites-en un extrait dans lequel l'entrée et la sortie sont enregistrées. variables.)

Contribution

Une séquence de left/ rightdécisions de longueur 0à 31inclusive, représentée dans un format de votre choix. Cela peut être une chaîne de lettres R/ L, une liste de nombres 1/ -1ou un tableau de booléens. Rien de plus ringard que de les avoir comme noms de méthode ou chaînes utiles pour votre code.

S'il vous plaît, postez les cas de test dans votre format s'il diffère des cas de test ci-dessous.

Sortie

True/ False, 0/ 1ou les analogues dans votre langue.

Critères gagnants

Le moins d'octets gagne. N'oubliez pas que vous devez donner une fonction nommée. Vous pouvez avoir du code en dehors de la fonction, mais ces octets comptent également. Votre fonction devrait se comporter correctement si elle est appelée plusieurs fois.

Cas de test

True cas (un par ligne, le second est une liste vide):

1 1 1 1

-1 -1 -1 -1
1 -1 1 -1 1 -1
1 1 -1 -1 1 1 -1 -1
-1 1 1 -1 -1 1 1 -1
1 1 1 -1 -1 -1 -1 1
1 -1 -1 1 -1 -1
1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1
-1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

False cas (un par ligne):

1
1 1
1 1 1
-1 1
1 -1 -1 -1 1
1 -1 -1 1 1
-1 1 -1 1
1 1 1 1 -1
-1 -1 1 -1 1 -1 -1 1
1 -1 1 1 1 1 -1 -1 -1 1 1 -1 -1 -1

Voici les mêmes cas de test avec L'et R'.

True cas:

RRRR

LLLL
RLRLRL
RRLLRRLL
LRRLLRRL
RRRLLLLR
RLLRLL
RRRRLLLLRLLRLL
LLLRLLRRLRLRRRRRRRRRRRRRRRRR

False cas:

R
RR
RRR
LR
RLLLR
RLLRR
LRLR
RRRRL
LLRLRLLR
RLRRRRLLLRRLLL

Défi de crédit supplémentaire

Même chose, mais avec un dodécaèdre plutôt qu'un cube. Voir Hunt the Wumpus pour des idées.

GolfScript, 24 caractères (19 pour le corps de la fonction uniquement)

Math FTW!

{3,.@{[+~@\{@}*~]}/=}:f;

Testez cette solution en ligne.

Cette fonction prend en entrée un tableau binaire (0 pour gauche, 1 pour droite) et renvoie 1 pour vrai et 0 pour faux.

Conceptuellement, cela fonctionne en faisant pivoter le cube afin que la fourmi garde toujours la même position et la même orientation, et en vérifiant si le cube se retrouve finalement dans la même orientation que celle dans laquelle il avait commencé.

En particulier, nous pouvons représenter les virages gauche et droit sous la forme de deux cartes linéaires en trois dimensions, où un virage à gauche correspond à une rotation de 90 ° autour de l' axe x , c'est-à-dire la carte ( x , y , z ) → ( x , z , - y ), et un virage à droite correspond à une rotation de 90 ° autour de l’ axe des y , c’est-à-dire la carte ( x , y , z ) → ( z , y , - x ).

Au début de la fonction, nous définissons simplement un vecteur à trois éléments contenant les valeurs positives distinctes (1, 2, 3), lui appliquons la séquence de cartes de rotation et vérifions si le vecteur résultant est égal à celui initial.

(En fait, pour sauver quelques caractères, je transforme les coordonnées de sorte que le vecteur initial soit (0, 1, 2) et que les cartes soient ( x , y , z ) → ( x , z , −1− y ) et ( x , y , z ) → ( z , y , −1− x ), mais le résultat final est identique.)

Ps. Merci à fier haskeller d' avoir repéré le bogue dans la version d'origine de cette solution.

Perl, 58 caractères

Comme demandé dans les commentaires, voici la même solution portée à Perl. (Cette version utilise en fait les coordonnées non transformées, car la transformation n'enregistre aucun caractère en Perl.)

sub f{@a=@b=1..3;@a[$_,2]=($a[2],-$a[$_])for@_;"@a"eq"@b"}

Testez cette solution en ligne.

Bonus: Une fourmi sur un dodécaèdre (GolfScript, 26 caractères)

{5,.@{{2*2%[~\]}*(+}/=}:f;

Testez cette solution en ligne.

Comme la fonction ant-on-a-cube ci-dessus, cette fonction prend en entrée un tableau binaire (0 pour gauche, 1 pour droite) et renvoie 1 si la ant se termine à la même position et à la même orientation qu'au début, ou 0 autrement.

Cette solution utilise une représentation légèrement plus abstraite que la solution de cube ci-dessus. Plus précisément, il tire parti du fait que le groupe de symétrie de rotation du dodécaèdre est isomorphe au groupe alternatif A ₅ , c'est-à-dire au groupe de permutations paires de cinq éléments. Ainsi, chaque rotation possible du dodécaèdre (qui mappe les arêtes sur les arêtes et les sommets sur les sommets) peut être représentée uniquement comme une permutation d’un tableau à cinq éléments, avec des rotations consécutives correspondant à l’application séquentielle des permutations correspondantes.

Il suffit donc de trouver deux permutations L et R pouvant représenter les rotations gauche et droite. Plus précisément, ces permutations doivent être de 5 cycles (pour que leur application soit renvoyées cinq fois à l'état initial), elles ne doivent pas être des puissances les unes des autres (c'est-à-dire R ≠ L ⁿ pour tout n ), et elles doivent satisfaire la relation. ( LR ) ⁵ = (1), où (1) désigne la permutation d'identité. (En réalité, ce critère indique que le chemin LRLRLRLRLRdoit revenir à la position d'origine.)

Fixation de la permutation L à un simple décalage de baril vers la gauche, c’est-à-dire une cartographie ( a , b , c , d , e ) → ( b , c , d , e , a ), puisqu’elle peut être implémentée dans GolfScript en seulement deux chars ( (+), nous trouvons qu'il y a cinq choix possibles pour la permutation de R. Parmi ceux-ci, j'ai choisi la cartographie ( a , b , c , d , e ) → ( c , e , d ,b , a ), car il a également une implémentation GolfScript relativement compacte. (En fait, je le mets en œuvre en commençant par entrelacer les éléments avec 2*2%pour obtenir ( a , c , e , b , d ), puis en permutant les deux derniers éléments avec [~\]et en appliquant enfin la permutation L de manière inconditionnelle pour déplacer un jusqu'à la fin.)

Le lien de démonstration en ligne ci-dessus inclut certains cas de test de chemins valides sur un dodécaèdre qui retournent à l'origine, tels que:

           # empty path
1 1 1 1 1  # clockwise loop
0 0 0 0 0  # counterclockwise loop
1 0 0 0 0 1 1 0 0 0 0 1  # figure of 8
1 0 1 0 1 0 1 0 1 0      # grand circle
1 0 0 0 1 0 0 0          # loop around two faces 
1 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 1 0  # Hamilton cycle

Python, 68

Prend une liste de 1 et -1. Basé sur les rotations 3D: vérifie si le point (3,2,1) se termine à la même position après avoir appliqué une série de rotations. Il y a deux rotations possibles, correspondant à 1 et -1. Chacun se fait en permutant deux coordonnées et en changeant le signe de l'une d'entre elles. Les coordonnées exactes à changer et le signe à permuter ne sont pas importants.

def f(l):
 p=[3,2,1]
 for d in l:p[d],p[0]=-p[0],p[d]
 return[3,2]<p

EDIT: il s’agit essentiellement de la même solution que "Perl, 58".

Mathematica

Inspiré par la solution de Ilmari Karonen. Le groupe de symétrie de rotation d'un cube est isomorphe à S ₄ .

Cube, 51 octets

Fold[Part,r=Range@4,{{2,3,4,1},{3,4,2,1}}[[#]]]==r&

Prend une liste de 1s et -1s en entrée.

Essayez-le en ligne!

Dodécaèdre, 55 octets

Fold[Part,r=Range@5,{{2,3,4,5,1},{3,5,4,2,1}}[[#]]]==r&

Prend une liste de 1s et -1s en entrée.

Essayez-le en ligne!

C (gcc) , 118 116 107 105 octets

-2 octets grâce à ceilingcat

f(char*s){char*p,n[]="@ABCDEFG",y;for(;*s;s++)for(p=n;*p;*p++^=*s^82?y%2+1:4-(y&2))y=*p/2^*p;y=n[2]==66;}

Essayez-le en ligne!

Supposons que nous donnions au cube les coordonnées suivantes:

            (1,1,1)       (1,1,0)
          G +--------------+ C
           /|             /|
          / |            / |
         /  |    (0,1,0)/  |
(0,1,1) +--------------+ D |
      H |   |          |   |
        |   |          |   |
        | F +----------|---+ (1,0,0)
        |  /(1,0,1)    |  / B           x
        | /            | /           y / 
        |/             |/            |/  
      E +--------------+ A      z ---*   
        (0,0,1)       (0,0,0)

Si nous commençons par le coin D, passer à C ou H peut être considéré comme une rotation du cube autour de nous. Se déplacer vers la droite signifierait une rotation dans le sens anti-horaire autour de l'axe Z, et vers la gauche signifierait une rotation dans le sens des aiguilles d'une montre autour de l'axe X. Ce sont les deux seules rotations dont nous devons nous préoccuper. Comme chaque rotation fait exactement 90 degrés, nous pouvons imaginer que les coins «glissent» le long des bords. Pour aller à droite, cela signifie A -> B, B -> C, C -> D, D -> A et E -> F de l'autre côté. Pour aller à gauche, on obtient plutôt A -> E, E - > H etc.

Étant donné que chaque coin ne glisse que le long d'un bord, cela signifie qu'une seule des dimensions de chaque point change pour chaque rotation. Lorsque B se déplace vers C, seule sa composante y change, et lorsque H se déplace vers D, seule sa composante z change, etc. De plus, puisque les coordonnées sont limitées à 0 et 1, nous pouvons considérer chaque point comme un nombre binaire, le bit approprié étant inversé lors du déplacement.

Nous pouvons voir que pour un mouvement à droite, A et C retournent leurs x, tandis que D et B retournent leurs y. Si nous changeons de perspective pour regarder de ce côté de la tête de cube et ignorons le composant z (qui ne change pas pour cette rotation de toute façon), nous obtenons:

D (0,1)         C (1,1)
 +-------------+
 |             |
 |             |
 |             |
 |             |
 |             |
 |             |
 +-------------+
A (0,0)         B (1,0)

Un motif se dégage: pour les points qui retournent leur x, x == y, alors que l'inverse est vrai pour les points qui retournent leur y. Ceci est valable pour l'autre type de rotation, mais avec z au lieu de x.

En d'autres termes:

Right
    if (x == y) x = !x
    if (x != y) y = !y

Left
    if (z == y) z = !z
    if (z != y) y = !y

Maintenant, nous pouvons facilement effectuer toutes les rotations et, à la fin, voir si le dernier D correspond à notre D. initial.

Stocker chaque point en tant que nombre unique est une donnée, mais en C, assigner un tableau de caractères est bien plus compact qu'un tableau int. Nous prenons soin de choisir des caractères dont les trois bits inférieurs correspondent à 000..111, ce qui permet d’ignorer simplement le reste des bits. Pour inverser les coordonnées, il suffit de procéder à une XOR avec le masque de bits approprié.

Python - 110, 150

Prend une liste d'entiers avec -1pour tourner à gauche, 1pour tourner à droite.

Cube, 110:

def f(l):
    c,p='07'
    for d in l:a="100134462634671073525275"[int(c)::8];c,p=a[(a.index(p)+d)%3],c
    return'1'>c

Tester:

l=map(int,'1 1 1 1'.split())
print f(l)

Dodécaèdre, 150:

def f(l):
    c,p='0J'
    for d in l:a="I5H76E8BBA8F76543100JI0J21D3A5C7E9CJI2132H4GF94C6D98AHGBEDGF"[int(c,36)::20];c,p=a[(a.index(p)+d)%3],c
    return'1'>c

Marbelous 188

Vol sans vergogne de l’algorithme d’ Ilmari Karonen dans le but de montrer une nouvelle langue.

Ce script attend une chaîne de 0x00 pour left et de 0x01 pour right sur stdin, suivie de 0x0A (nouvelle ligne). Il génère "0" pour un cas ayant échoué et "1" pour un succès.

......@5@3FF
@0@1@2\\]]@5
010203@4=A@4
&0&0&0&0/\
MVMVMVMV..
@0@1@2@3..!!
:MV
}2}2}1}0}1}0}3
&0&1&0&1~~~~<A@P
{0{1{1{0&1&0=0&1
}0}1}2@P{2{2&030
=1=2=3&2FF}3..//
&2&2&231&2{3
\/\/\/&2!!..//

exemple exécuté:

# echo -e "\x0\x0\x0\x1\x0\x0\x1\x1\x0\x1\x0\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1" | marbelous.py ant-on-a-cube.mbl
1

Python 2 , 57 octets

f=lambda l:reduce(lambda n,x:n%4*64+n/4*16**x%63,l,27)<28

Essayez-le en ligne!

Ceci utilise la représentation de permutation

0: abcd -> dabc
1: abcd -> dcab

où left et right (0 et 1) correspondent à une longueur de 4 cycles sur 4 éléments. Nous itérons sur l'entrée en appliquant la permutation indiquée et vérifions si le résultat est égal à la valeur initiale.

Nous commençons en a,b,c,dtant que liste à quatre éléments 0,1,2,3. Nous les compactons en un seul nombre base-4 n=abcd, avec la valeur initiale n=27correspondant à la 0123base 4. Nous instancions chacun la permutation de manière arithmétique n.

Puisque les deux résultats commencent par d, nous pouvons faire n%4pour extraire d, puis n%4*64pour le déplacer dans la bonne position d___. Les autres chiffres sont abcextraits sous forme de n/4. Nous devons les insérer dans les trois valeurs les plus basses.

Pour la direction x=0, nous insérons abctels quels et pour les x=1faire pivoter cab. La rotation peut être réalisé que *16%63, ce qui prend abcà abc00la cab. (Le %63irait mal sur a==b==c==3, mais ces valeurs ne sont pas possibles.) Depuis que faire %63est un non-op, l'expression dépendant de la direction *16**x%63donne abcou cabau besoin.

Python 2 , 55 octets

f=lambda l:reduce(lambda n,x:n^(n*8%63|7*8**x),l,10)<11

Essayez-le en ligne!

Haskell, 104 103 99 97 96/ 67 64 caractères

Je pense que l'équivalent de droite / gauche serait un type de données Direction comme ceci:

Direction = R | L

J'ai donc supposé dans ma réponse qu'ils étaient disponibles.
edit: a effectivement réalisé que les booléens conduiraient à un code plus court. True représente un virage à gauche et False, un virage à droite (même si, techniquement, le code fonctionnerait de la même manière s'il était inversé; il est symétrique).

96 caractères:

m[p,l,r]b|b=[p%l,7-r-l,r]|0<1=[p%r,l,7-r-l]
p%x|odd$div p x=p-x|0<1=p+x
g l=foldl m[0..2]l<[0,2]

g est une fonction qui, étant donné une liste de directions, rendrait la météo sans que la fourmi ne revienne à sa place.

explication de la représentation de la position: la position de la fourmi est codée sous la forme d'un tuple de trois entiers. le premier entier représente le sommet vers lequel se dirige la fourmi. le premier bit représente si le sommet est dans la moitié haut / bas, le second est la moitié gauche / droite et le troisième est la moitié arrière / avant. ceci est fait de sorte que le passage d'un sommet à un sommet voisin soit effectué en retournant un bit.

le deuxième entier est la quantité que le sommet de la fourmi changerait s'il allait à gauche. Par exemple, si la fourmi était au sommet 3 et que le second entier était 4, alors qu'après avoir tourné à gauche, le sommet serait 7. Notez que cette puissance sera toujours égale à 2, car un bit est inversé en déplaçant un sommet.

le troisième entier est le même, mais pour aller à droite; Je sais que cela peut être calculé par les deux premiers, mais je ne sais pas comment. si vous avez une idée, s'il vous plaît dites-moi.

quelque chose à noter est que, en tournant à gauche, le troisième entier reste le même et le second devient celui compris entre 1 2 et 4 qui n'est ni le second ni le troisième, qui se trouve être identique à 7 - deuxième entier - troisième entier.

J'ai choisi cette façon de représenter une position car (comme on vient de le dire dans le paragraphe précédent), il était trivial de calculer la position suivante.

explication des fonctions:

la fonction (%) est la fonction qui prend le sommet actuel et le montant pour le changer, et le change. il arrive au bit qui va changer et le retourne (de manière très numérique).

la fonction m est une fonction qui prend la position de la fourmi et de la direction, puis renvoie la nouvelle position en utilisant la note notée précédemment.

ensuite, la fonction m est combinée à l'aide de foldl (ce qui est un peu comme reduceen javascript, mais un peu plus expressif) pour créer la fonction g, la réponse à cette question.

Haskell, 64 caractères

inspiré par la réponse de @ alphaalpha, voici sa version portée sur haskell:

m[a,b,c,d]p|p=[b,c,d,a]|0<1=[b,d,a,c]
g l=foldl m[0..3]l<[0,1,3]

edit: Je me sens maintenant incroyablement stupide à cause de la réponse d'Imari Karonen. je vais peut-être porter sa réponse sur haskell. une autre édition: ne se sentait pas aussi stupide que sa réponse est était mauvaise
modifier: commutation de fait à l' aide à l' utilisation des listes tuples comme Ordinstance et le [ ... ]sucre syntaxique rend plus courte

Haskell , 53 octets

f=(<28).foldl(\n x->mod n 4*64+mod(div n 4*16^x)63)27

Essayez-le en ligne!

Même logique que ma réponse Python , même pensée modet divsont plus longues à écrire.

Haskell , 58 octets

r=[1..3]
f=(==r).foldl(\[x,y,z]->(!!)[[x,-z,y],[-z,y,x]])r

Essayez-le en ligne!

APL (Dyalog Unicode) , 22 octets ( SBCS d'Adam )

f←{x∊(-@3∘⌽⌽)/⍵,x←⊂⍳3}

Essayez-le en ligne!

H.PWiz a suggéré que l'inversion des étapes ne faisait aucune différence, ce qui donnait -2 octets.

Eh bien, c’est embarrassant, car il était censé être beaucoup plus court que GolfScript. Au moins j'ai essayé.

La fonction est nommée fet, dans les cas de test, 1représente un virage à gauche (boolean true) et 0représente un virage à droite (boolean false). ⍬représente la liste vide.

APL (Dyalog) , 21 octets

f←{x≡(↓∪⊢∘⌽)/⍵,x←⊂⍳4}

Essayez-le en ligne! (Utilisation de l'environnement de test de la réponse d'Erik the Outgolfer )

Je prends à gauche et à droite au fur 1et à mesure 2. Ceci utilise les permutations suivantes de abcd:

1 : bcda
2 : cdba

J'applique les permutations correspondant à 1et 2à ⍳4 : 1 2 3 4, et vérifie s'il est inchangé

Bash , 71 à 65 octets

f()(a=1234;for i;{ a=`tr 1-4 4$[$i?123:312]<<<$a`;};((a==1234));)

Essayez-le en ligne!

Comme beaucoup de réponses précédentes, utilise une représentation du groupe de rotations du cube généré par 1234-> 4123 et 1234-> 4312. Utilise des chiffres au lieu de lettres pour pouvoir utiliser un opérateur ternaire avec une extension arithmétique. Attend son entrée en tant que 0 et 1 séparés par des espaces et les sorties via le code de sortie.

6 octets sauvés grâce au commentaire de @ manatwork!

brainfuck , 119 octets, 137 octets

$S_4$ . Brainfuck n’ayant aucune fonction, nommée ou autre, il s’agit d’un programme complet qui prend des entrées via STDIN et des sorties vers STDOUT. (Si vous insistez sur une variable, supposez que la valeur de la cellule sur laquelle se termine le programme est une variable.)

Cube, 119 octets

++++>+++>++>+>,[+++[->+++<]<<<<[->>>>+<<<<]>[>]<+[[-]<[->+<]<<<[->>>+<<<]>[>]],]<[[<]>[->]<[>>]<]<[>>-<]-[----->+<]>--.

Essayez-le en ligne!

++++>+++>++>+    Initialize tape as 4 3 2 1

>,[              For each input byte:

  +++[->+++<]       Add 3 and multiply by 3; if input is R, this will be 255

  <<<<[->>>>+<<<<]  Move first number to end (BCDA)

  >[>]<+[           If input wasn't R:

    [-]                Zero input cell (which is now negative 18)

    <[->+<]            Move previously moved number one slot further (BCD_A)

    <<<[->>>+<<<]      Move first number into vacated slot (CDBA)

  >[>]]

,]

<[[<]>[->]<[>>]<]     Determine whether tape is still 4 3 2 1

<[>>-<]               If not: subtract 1 from output cell

-[----->+<]>--.       Create "1" in output cell and output

Dodécaèdre, 137 octets

+++++>++++>+++>++>+>,[+++[->+++<]<<<<<[>>>>>+[<]>-]>[>]<+[[-]<<[[->>+<<]<<]>[>>>>>>+[<]<-]>>[>]],]<[[<]>[->]<[>>]<]<[>>-<]-[----->+<]>--.

Essayez-le en ligne!

Les seules différences entre les deux programmes sont la configuration et les permutations. La permutation de gauche utilisée ici est DCAEB, qui semblait être le conjugué le plus golfeux disponible.

Gelée , 14 octets

3RðW;ṙN1¦ṚƊ/⁼⁸

Essayez-le en ligne!

1 = virage à gauche, 0 = virage à droite. Basé sur ma solution Dyalog.

Malheureusement, Jelly n'a pas de fonctions nommées. Si je ne peux pas utiliser une entrée implicite et dois supposer que c'est dans une variable, cette version de même longueur fera:

3RµW;®ṙN1¦ṚƊ/⁼

Cela suppose que l’entrée est dans le registre (© / ®).

Perl - 120, 214

Prend un tableau (liste) de booléens.

Cube (120):

sub e{$a=$b=0;for$c(@_){$_=(13,62,53,40,57,26,17,'04')[$b];$d=s/$a/($b-1)%8/e;($a,$b)=($b,substr($_,$c^$d,1))}return!$b}

Dodécaèdre (214):

sub e{$a=$b='00';for$c(@_){$_=('01041102090307040500061807160308091502101114121019131714151016081706131819051200'=~/\d{4}/g)[$b];$d=s/$a/sprintf'%02d',($b-1)%20/e;($a,$b)=($b,substr($_,($c^$d)*2,2));}return!($b+0)}