Hier, j'ai posé cette question au sujet des shuffles de fusils. Il semble que la question d'hier était un peu trop difficile, donc cette question est une tâche connexe mais beaucoup plus facile.
Aujourd'hui, on vous demande de déterminer si une permutation est en fait un shuffle de fusil. Notre définition du shuffle de fusil est adaptée de notre dernière question:
La première partie du remaniement est la division. Dans la partition de division, le jeu de cartes en deux. Les deux sous-sections doivent être continues, mutuellement exclusives et exhaustives. Dans le monde réel, vous voulez rendre votre partition aussi proche que possible, mais dans ce défi, ce n'est pas une considération, toutes les partitions, y compris celles qui sont dégénérées (une partition est vide) sont d'égale considération.
Après avoir été partitionnées, les cartes sont assemblées de telle sorte que les cartes conservent leur ordre relatif dans la partition à laquelle elles appartiennent . Par exemple, si la carte A est avant la carte B dans le jeu et que les cartes A et B sont dans la même partition, la carte A doit être avant la carte B dans le résultat final, même si le nombre de cartes entre elles a augmenté. Si A et B sont dans des partitions différentes, ils peuvent être dans n'importe quel ordre, quel que soit leur ordre de départ, dans le résultat final.
Chaque mélange de fusils peut ensuite être considéré comme une permutation du jeu de cartes d'origine. Par exemple la permutation
1,2,3 -> 1,3,2
est un remaniement rapide. Si vous divisez le jeu comme ça
1, 2 | 3
nous voyons que chaque carte dans 1,3,2
a le même ordre relatif à toutes les autres cartes dans sa partition. 2
est toujours après 1
.
D'un autre côté, la permutation suivante n'est pas un shuffle de fusil.
1,2,3 -> 3,2,1
Nous pouvons le voir parce que pour les deux partitions (non triviales)
1, 2 | 3
1 | 2, 3
il y a une paire de cartes qui ne maintiennent pas leur ordre relatif. Dans la première partition 1
et 2
changez leur ordre, tandis que dans la deuxième partition 2
et 3
changez leur ordre.
Tâche
Étant donné une permutation via une méthode raisonnable, déterminez si elle représente un shuffle de fusil valide. Vous devez sortir deux valeurs constantes distinctes, une pour "Oui, c'est un shuffle riffle" et une pour "Non, ce n'est pas un shuffle riffle".
Il s'agit de code-golf donc les réponses seront notées en octets avec moins d'octets étant meilleurs.
Cas de test
1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False
la source
0
pour faux mais n'importe quel entier[1, +∞)
pour vrai?[3,1,4,2,5]
.[2,3,6,1,4,5]
.[0, ..., n-1]
au lieu de[1, ..., n]
comme entrée?Réponses:
JavaScript (ES6), 47 octets
Prend l'entrée comme un tableau d'entiers. Renvoie un booléen.
Cas de test
Afficher l'extrait de code
Comment?
Le tableau d'entrée A est un shuffle riffle valide s'il se compose d'au plus deux séquences entrelacées distinctes d'entiers consécutifs.
Les règles de défi spécifient que l'on nous donne une permutation de [1 ... N] . Nous n'avons donc pas besoin de vérifier en plus que l'union triée de ces séquences aboutit réellement à une telle plage.
Nous utilisons un compteur x initialisé à A [0] et un compteur y initialement non défini.
Pour chaque entrée z dans A , en commençant par la 2ème:
la source
Haskell , 41 octets
Essayez-le en ligne!
Vérifie si la liste concaténée à elle-même contient les nombres
0..n-1
dans l'ordre comme sous-séquence.la source
Haskell , 43 octets
s
prend une liste d'entiers comme dans les exemples OP et retourne aBool
.Essayez-le en ligne!
Comment ça fonctionne
x
dep
tour et vérifie si elle peut être le premier élément de la deuxième partition du remaniement.or
Retourne ensuiteTrue
si l'un des chèques étaitTrue
.filter
) desp
éléments plus petits et plus grands que (ou égaux à)x
, en concaténant et en vérifiant si la liste résultante est[1..length p]
, c'est-à-dire les éléments en ordre.[1..length p]
est effectuée en voyant si le résultat est strictement inférieur à la liste infinie[1..] == [1,2,3,etc.]
, ce qui donne le même résultat pour toute permutation.la source
Gelée ,
136 octetsEssayez-le en ligne!
Version alternative, défi postdates, 5 octets
Essayez-le en ligne!
Comment ça fonctionne
la source
Python 2 , 39 octets
Essayez-le en ligne!
Prend la liste indexée 0 et sort via le code de sortie.
la source
Brachylog , 9 octets
Essayez-le en ligne!
Le prédicat réussit si l'entrée représente une lecture aléatoire et échoue dans le cas contraire, ce qui signifie entre autres que si le prédicat est exécuté comme un programme complet, le succès s'imprime
true.
et l'échec s'imprimefalse.
. L'entrée est considérée comme une liste de toutes sortes d'éléments et l'interprète comme représentant une permutation de lui-même trié.J'ai l'impression qu'il y a quelque chose dans l'esprit
⊆ᵐ
qui devrait fonctionner à la place de la construction "sandwich" à quatre octets⟨⊆⊇⟩
.la source
Python 2 ,
756047 octetsmerci à Dennis pour -13 octets
Essayez-le en ligne!
La sortie se fait via un code de sortie.
la source
Rubis , 35 octets
Essayez-le en ligne!
Comment?
l & [*1..a] | l
applique une intersection puis une union: obtenez d'abord les éléments del
qui sont<=a
puis ajoutez les éléments restants del
sans changer l'ordre. Si a est le nombre que nous recherchons, cette opération est identique au tril
.la source
Nettoyer ,
5655 octetsEssayez-le en ligne!
la source
Pyth, 5 octets
Suite de tests
Vérifie si la liste d'entrée doublée contient une version triée d'elle-même en tant que sous-séquence.
Merci à Erik l'Outgolfer pour 1 octet qui profite mieux de l'entrée implicite avec
+QQ
plutôt que*2Q
.la source
}SQy+
. Il est étendu à}SQy+QQ
.Pyth , 9 octets
Suite de tests.
Enregistré 3 octets grâce à isaacg .
Pyth , 14 octets
Essayez-le ici! ou Vérifiez tous les cas de test.
Sorties
True
et respectivementFalse
pour riffle-shuffle et non-riffle-shuffle.Comment?
la source
<#0
peut être remplacé par-
pour 2 octets supplémentaires.Husk , 7 octets
Suite de tests!
la source
Perl, 28 octets
Comprend
+1
poura
Entrée sur STDIN, 1 basée
Utilise l'algorithme de xnor
la source
C (gcc) , 61 octets
Essayez-le en ligne!
la source