Imaginez un chemin composé de <et >et se terminant par un @, par exemple ,
><>@
Un marcheur démarre sur la cellule la plus à gauche. Il parcourra le chemin comme suit:
- Si le marcheur est sur une
@cellule, il a atteint le but et c'est fait. - Si le marcheur se trouve sur une
>cellule, le chemin entier se déplace d'un pas vers la droite, cycliquement, en emmenant le marcheur avec lui . - Si le marcheur se trouve sur une
<cellule, le chemin entier se déplace d'un pas vers la gauche, cycliquement, en emmenant le marcheur avec lui . - Ensuite, le promeneur fait un pas. S'il est à l'une ou l'autre extrémité du chemin, il s'éloigne de la fin. Sinon, il continue de se déplacer dans la direction dans laquelle il s'est déplacé au dernier pas (en ignorant la rotation), en marchant à droite au départ.
Examinons l'exemple ci-dessus. La position du marcheur est marquée par ^:
><>@ --rotate--> @><>
^ ^
step right (first step):
@><> --rotate--> ><>@
^ ^
step right:
><>@ --rotate--> @><>
^ ^
step left (dead end):
@><> --rotate--> ><>@
^ ^
step left:
><>@ --rotate--> @><>
^ ^
step left:
@><> Goal reached!
^
Le marcheur a visité 6 cellules dans le processus (y compris la cellule de départ ainsi que la @, et en comptant chaque cellule aussi souvent qu'elle est visitée).
Voici un petit exemple, où le marcheur est transporté sur les bords par une rotation:
>>@ --rotate--> @>>
^ ^
step right (first step):
@>> --rotate--> >@>
^ ^
step right (dead end):
>@> Goal reached!
^
Cette fois, le promeneur a visité 3 cellules.
Nous pouvons facilement transformer cela en une séquence entière:
- On vous donne un entier positif N , par exemple
9. - Vous calculez la représentation binaire de cet entier, par exemple
1001. - Ensuite , tournez
1dans>et0en<et ajouter un@:><<>@. - Nous associons à N le nombre de cellules visitées par le promeneur dans le nombre ainsi construit.
Les premiers éléments de la séquence résultante sont:
2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7
Cela peut sembler assez arbitraire, mais la séquence résultante se révèle en réalité avoir beaucoup de structure:
Pour référence, vous pouvez trouver les 2048 premiers numéros de la séquence dans cette boîte à pâte .
Le défi
Vous l'avez deviné: vous devez calculer la séquence ci-dessus. Vous pouvez le faire de trois manières:
- Vous pouvez produire une séquence infinie (alors que la mémoire le permet), soit en émettant en continu (séparés par des caractères non numériques) des valeurs ou en utilisant une certaine forme de générateur infini dans les langues qui les prennent en charge. Si vous imprimez un flux infini sur STDOUT, vous n'êtes pas obligé d'imprimer les nombres un par un, mais assurez-vous que chaque numéro sera imprimé après une durée limitée (et dans l'ordre). Si vous utilisez cette option, vous ne devez prendre aucune entrée.
- Vous pouvez prendre un entier N en entrée et produire le N ème terme de la séquence.
- Vous pouvez prendre un nombre entier N en entrée et tout produit jusqu'à la N ième terme de la séquence, que ce soit sous forme de liste ou d'une chaîne à l' aide d' un séparateur non ambiguë.
Comme je ne veux pas pénaliser les langages qui ne peuvent pas facilement être convertis entre les bases, au lieu de l'entier N, vous pouvez plutôt prendre la représentation binaire de N , en utilisant 0s et 1s comme d'habitude (comme une liste ou une chaîne), avec le plus - bit significatif en premier.
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).
Les règles de code-golf standard s'appliquent.
Contexte
Cela calcule en fait le nombre de "ticks" qu'un interprète direct de mon langage de programmation ésotérique Labyrinth aurait besoin d'interpréter le "chemin" comme code source. Dans ce cas, le "marcheur" est simplement le pointeur d'instruction (qui a une position et une direction), la @commande termine le programme <et ce >sont des commandes de modification du code source.
Réponses:
Gelée , 10 octets
Cette fonction accepte en entrée un seul entier sous la forme de la liste de ses chiffres binaires.
L'algorithme est équivalent à celui de la réponse de @ Agawa001 .
Essayez-le en ligne! ou générer les premiers 2048 nombres .
Contexte
Énumérer les positions sous le chemin de 0 à L , donnant un total de L + 1 positions. L coïncide avec le nombre de chiffres binaires du nombre N qui code le chemin. Avec cette notation, le promeneur commence à la position 0 , l'objectif à la position L .
À chaque pas que le marcheur fait, il se rapproche du but (dans la direction où il marche actuellement). De plus, à chaque pas de décalage, selon qu'il marche avec ou contre la direction de changement, il incrémente ou décrémente sa position de 2 modulo L + 1 , ou il reste dans la position actuelle.
Pour changer de direction, il doit atterrir sur la position L - 1 (face à L ) ou la position 1 (face à 0 ), puis se déplacer dans sa direction. La prochaine étape qu'il prendra le ramènera à sa position précédente, face à la direction opposée.
Si L est pair, L - 1 est impair, il ne peut donc pas passer directement de sa position initiale à L - 1 . La seule façon de l'atteindre est de passer par L , de se porter à 0 et de passer à l'étape suivante pour atterrir sur 1 , puis d'avancer à droite. Cela nécessite d'avancer des positions de 2L , ce qui peut être fait en pas moins de L étapes.
Cependant, après avoir fait L pas sans changer de direction, il aura atteint le but. En ajoutant un pour la cellule de départ, nous obtenons un total de L + 1 cellules visitées dans ce cas.
Si L est impair, L - 1 est pair, il peut donc atteindre cette position en se déplaçant (L - 1) / 2 fois vers la droite. Si la position L-1 est en dessous d'un 1 à ce moment-là, il sera déplacé vers la position L , se retournera et marchera sur la position L-1 (face à gauche).
Cela peut ou non se produire avant qu'il n'atteigne son objectif, il y a donc deux cas à analyser:
S'il y a moins de (L + 1) / 2 occurrences de 1 dans l'expansion binaire de N , prendre des pas L ne suffira pas pour tourner la direction. Étant donné que ces étapes L amènent le marcheur à son objectif, en ajoutant une pour la cellule de départ, nous obtenons un total de L + 1 cellules visitées dans ce cas.
S'il y a au moins (L + 1) / 2 occurrences de 1 dans l'expansion binaire de N , passer à la ((L + 1) / 2) ème occurrence nécessitera I étapes, où I est la position initiale de cette occurrence de 1 .
Ainsi, après avoir fait I pas, le marcheur est en position L - 1 , face à gauche. Pour tourner à nouveau les directions, il devait marcher vers la gauche jusqu'à la position 1 . Cependant, comme dans le cas pair, puisque (L - 1) - 1 est impair, cela nécessitera de passer par 0 et de prendre pas moins de tha L étapes.
Étant donné que la distance initiale au but dans la direction gauche est de 1 , après avoir fait I pas, le marcheur se trouve à une distance de I + 1 du but après avoir changé de direction. Puisque I <L , nous avons que I + 1 ≤ L , donc les prochaines étapes I + 1 l'amèneront au but.
Cela donne un total de I + I + 1 = 2I + 1 pas effectués. En ajoutant un pour la cellule de départ, nous obtenons un total de 2I + 1 + 1 = 2 (I + 1) cellules visitées dans ce cas.
Comment ça fonctionne
la source
Matlab (score = 230, n = inf)
infsi vous voulez continuer à l'infini).h=1000000000000000000000000000000000000000000000000000;w(h,h+1)pour vous en assurer.L'algorithme suit une approche mathématique que j'expliquerai plus tard, et il confirme la liste référencée de Martin, basée sur ce programme:
Étant donné que l'algorithme vérifie les 2048 premiers cas de test, je supposerai aveuglément qu'il le ferait pour n'importe quel cas de test, donc mon algorithme fonctionne concernant peu de propriétés que j'ai découvertes dans ce processus sans la douleur de déplacer et de déplacer le pointeur:
1- si le double du nombre de 1 en traduction binaire ne dépasse pas la longueur de la séquence
L, la sortie estL+12- Si la longueur de la séquence est paire et que la condition précédente n'est pas définie, la sortie est la même
L+13- sinon, la sortie est deux fois le
L/2th index de 1.la source
a=dec2bin(input(''));c=find(a=='1');g=nnz(a)+1;if nnz(c)<g/2|mod(g,2);g,else,2*c(g/2),end, ce qui ne donne qu'un seul élément de la séquence.Python,
122119113 113110108107103 octetsPrend la saisie sous forme de liste de chiffres binaires. Fonction d'aide pour tester:
Nous remercions Lynn pour avoir économisé 7 octets.
la source
p-d-1in[-2,w]économise un octet.d*=2*(1!=d-p>~w)-1économise quatre autres! ° v °Python 2, 99 octets
Port Python d'Agawa001: la réponse brillante.
Version lisible:
la source
MATL,
31, 25 octetsCeci est juste une version MATL de l'algorithme d'Agawa001, sauf qu'il prend une entrée entière N et retourne le N-ème terme dans la séquence. C'était difficile de suivre tous les éléments de la pile! J'ai dû recourir à un presse-papiers pour éviter de devenir fou. Vous pouvez essayer en ligne!
Peut être transformé en une boucle imprimant les N premiers termes en ajoutant
:"@avant le code, et]Daprès.Merci à Luis Mendo d'avoir sauvé 6 octets entiers!
la source
Julia 0,4, 4̷4̷ 42 octets
Cette fonction accepte en entrée un seul entier sous la forme de la liste de ses chiffres binaires.
L'algorithme est équivalent à celui de la réponse de @ Agawa001 et de ma réponse Jelly .
Essayez-le en ligne!
Comment ça fonctionne
find(x)renvoie les indices basés sur 1 de tous les éléments non nuls de x . Nous essayons d'accéder au tableau résultant à l'index k / 2 et, en cas de succès, d'écraser k avec le double de l'index sélectionné.Cela échouera si et seulement si l'une des conditions suivantes est vraie:
k / 2 est un flottant non intégral, donc InexactError est levé.
Le tableau d'index a moins de k / 2 éléments, donc une BoundsError est levée.
Dans les deux cas, l'écrasement de k échouera, donc sa valeur d'origine sera retournée.
la source
JavaScript (ES6), 65 octets
Accepte une chaîne binaire. Utilise la vérification du rebond des diverses autres réponses.
la source
Python 2, 74 octets
Cette fonction accepte en entrée un seul entier sous la forme de la liste de ses chiffres binaires.
L'algorithme est équivalent à celui de la réponse de @ Agawa001 et de ma réponse Jelly .
Testez-le sur Ideone .
Comment ça fonctionne
nexttente de trouver le premier entier 2i pour lequelk==2*sum(x[:i])renvoie vrai. Puisquex[:i]contient i éléments, cela donne l'indice basé sur 1 du (k / 2) th 1 .nextéchouera si k / 2 n'est pas intégral ou si x en contient moins de k / 2 . Dans ce cas, la valeur par défaut k est retournée.la source
> <> , 63 octets
À partir du moment où j'ai vu l'exemple de modèle dans ce défi, je savais quelle langue utiliser :)
Utiliser N pour obtenir le N ème terme.
L'entrée est supposée être en binaire sur la pile. Plutôt que de déplacer le déambulateur, cette solution repose principalement sur le déplacement du ruban sous le déambulateur.
Essayez-le en ligne!
la source