Il s'agit d'un casse-tête courant que beaucoup d'entre vous ont résolu manuellement. Maintenant, c'est le moment d'écrire un algorithme pour résoudre le même.
Il y a des bâtons de match de nombre égal alignés sur deux côtés différents face à face. Il y a un seul espace vide entre eux. Dites quelque chose comme la figure suivante (si le nombre total de bâtons de match est de 4).
Chaque bâton peut soit glisser d'un pas vers l'avant (si l'espace avant immédiat est libre), soit sauter par-dessus un bâton à l'avant et atterrir dans l'espace libre (si cet espace est libre). Le déplacement en sens inverse n'est pas possible (même l'espace est libre). Aucun saut inversé n'est également autorisé. Un seul mouvement est autorisé en une seule étape.
Maintenant, vous devez écrire un algorithme pour trouver les étapes minimales requises à l'aide desquelles tous les bâtons de match de gauche se poseront du côté droit et tous les sticks de match du côté droit se poseront du côté gauche.
Par exemple: s'il y a au total 2 bâtons de match (1 de chaque côté), les étapes seront les suivantes:
Remarque: Dans la figure ci-dessus, le manche gauche a été déplacé en premier. Une autre solution existe lorsque le manche droit se déplace en premier. Mais pour ce problème, vous devez donner une seule solution et cela suppose également que le stick latéral gauche se déplace en premier.
La figure suivante décrit les mouvements avec 4 bâtons de match (2 de chaque côté):
Remarque: Dans la figure ci-dessus, le manche gauche a été déplacé en premier. Une autre solution existe lorsque le manche droit se déplace en premier. Mais pour ce problème, vous devez donner une seule solution et cela suppose également que le stick latéral gauche se déplace en premier.
[Hypothèse: L'entrée peut être n'importe quel nombre pair entre 02 et 14 (c'est-à-dire 1 à 7 allumettes de chaque côté). Pour les entrées en dehors de cette plage, vous n'avez pas besoin d'effectuer de validation, ni de fournir de message d'erreur. Remarque: Dans la sortie, chaque étape est séparée par un «|» (pipe). Les programmeurs COBOL doivent toujours supposer que PIC 9 (2) est la taille d'entrée et peuvent également supposer que la sortie doit être d'une longueur maximale fixe de 450 caractères, avec des espaces à droite.]
Exemple d'entrée:
02
Exemple de sortie:
01To02|03To01|02To03|
Exemple d'entrée:
04
Exemple de sortie:
02To03|04To02|05To04|03To05|01To03|02To01|04To02|03To04|
Exemple d'entrée:
06
Exemple de sortie:
03To04|05To03|06To05|04To06|02To04|01To02|03To01|05To03|07To05|06To07|04To06|02To04|03To02|05To03|04To05|
la source
Réponses:
APL 129
Le code ci-dessous prend l'entrée et les sorties d'écran à l'écran dans le format spécifié:
Un bon tiers du code est utilisé pour formater la sortie. La logique est complétée par l'occurrence du symbole ⋄ dans le code.
Voici le résultat pour une entrée de 08 comme vérification:
la source
Javascript
178 174161prompts pournensuitealerts réponse. (Pas de0rembourrage)Dernier:
2:
1:
Cela utilise le concept que le modèle est mis en miroir:
Alors, où
n=2, le modèle de mouvement est:Ce qui équivaut à
Ce modèle se répète comme tel (
n=8)Nous pouvons remarquer quelques modèles ici:
n/2, qui se répète 3 fois, puis redescend à 1.1et le nombre de sauts séquentiels augmentant de 1 àn/2puis diminuant de nouveau à 1.n=14:Exemple de sortie:
f(2):f(8):f(40):Voici un pseudo-code pour illustrer la méthode:
la source
l/L/r/Retm/j. J'aime l'idée de séparer la distance déplacée de la directionC -
216213Ma solution repose sur deux faits:
Le champ "à" est le champ "à partir de" du mouvement précédent (puisque vous créez toujours un emplacement vide dans l'espace d'où vous vous déplacez et que vous vous déplacez toujours vers un emplacement vide)
Les distances et les directions qui sont déplacées sont très régulières. Pour les 3 premiers cas de test, ce sont:
1 -2 11 -2 -1 2 2 -1 -2 11 -2 -1 2 2 1 -2 -2 -2 1 2 2 -1 -2 1Dans cet esprit, j'ai simplement écrit un programme pour produire et continuer ce modèle. Je suis presque sûr qu'il doit y avoir une manière récursive vraiment belle et beaucoup plus élégante d'écrire ceci, mais je ne l'ai pas encore compris:
Et joué au golf (même s'il s'agissait d'un défi de code, pas de golf):
la source
scanf. Je mets à jour ma réponse avec une meilleure version.N(2)=rLr,N(4)=rLlRRlLr,N(6)=rLlRRrLLLrRRlLr, etc.Mathematica
Cette approche construit une
Nestséquence ed de la taille et de la direction des mouvements, formatée en{fromPosition,toPosition}commençant par la positionn, où senréfère au nombre de paires de correspondances. Il s'agit ensuite deFoldla séquence en une fonction qui commence par le mouvement{n, n+1}.Visualisation des swaps
r,,betosont des images ou une correspondance rouge, une correspondance bleue et aucune correspondance, respectivement.Les formats suivants formatent la sortie de
zpour afficher les échanges avec des correspondances.swapsproduit une liste d'états en utilisant les paires ordonnées dezcommandes as pour permuter la liste initiale et les listes suivantes.swapMatchesaffiche les états dans une grille.la source
Javascript 191
Caractères comptés avec
grep =|tr -d \ |wc -cla source
02, les valeurs sont correctes, mais il manque la fin|. Pour les deux autres cas, les valeurs sont loin et la mise en forme de10est également incorrecte. Pas sûr non plus de votre méthode de comptage de caractères. Pourquoi comptez-vous seulement le corps de la fonction moins le retour?tr -d \ |wc -cprend en compte les nouvelles lignes