Est-ce un remaniement?

19

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,2a le même ordre relatif à toutes les autres cartes dans sa partition. 2est 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 1et 2changez leur ordre, tandis que dans la deuxième partition 2et 3changez 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 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
Assistant de blé
la source
1
La sortie peut-elle être incohérente, mais véridique / fausse dans notre langue? Comme (Python, où, parmi les nombres entiers, seul 0 est faux) 0pour faux mais n'importe quel entier [1, +∞)pour vrai?
M. Xcoder
1
@ Mr.Xcoder Je n'aime pas les valeurs véridiques / fausses car elles sont assez difficiles à bien définir. Les réponses doivent respecter les règles actuelles.
Wheat Wizard
Cas de test suggéré: [3,1,4,2,5].
Ørjan Johansen
9
Désolé à ce sujet, mais: [2,3,6,1,4,5].
Ørjan Johansen
1
Pouvons-nous prendre des permutations de [0, ..., n-1]au lieu de [1, ..., n]comme entrée?
Dennis

Réponses:

8

JavaScript (ES6), 47 octets

Prend l'entrée comme un tableau d'entiers. Renvoie un booléen.

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

Cas de test

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:

  • Nous vérifions si z est égal à x + 1 ou y + 1 . Si oui, nous incrémentons le compteur correspondant.
  • Sinon: si y n'est pas encore défini, nous l'initialisons à z .
  • Sinon: nous faisons échouer le test.
Arnauld
la source
6

Haskell , 41 octets

n%h=n+0^(n-h)^2
f l=elem(foldl(%)0$l++l)l

Essayez-le en ligne!

Vérifie si la liste concaténée à elle-même contient les nombres 0..n-1dans l'ordre comme sous-séquence.

xnor
la source
5

Haskell , 43 octets

sprend une liste d'entiers comme dans les exemples OP et retourne a Bool.

s p=or[f(<x)p++f(>=x)p<[1..]|x<-p]
f=filter

Essayez-le en ligne!

Comment ça fonctionne

  • La compréhension de la liste essaie chaque élément xde ptour et vérifie si elle peut être le premier élément de la deuxième partition du remaniement. orRetourne ensuite Truesi l'un des chèques était True.
  • La compréhension le fait en partitionnant (avec filter) des pé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.
  • La vérification pour savoir si la liste résultante [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.
Ørjan Johansen
la source
5

Gelée , 13 6 octets

ỤIṢḊRẠ

Essayez-le en ligne!

Version alternative, défi postdates, 5 octets

Ụ>ƝSỊ

Essayez-le en ligne!

Comment ça fonctionne

ỤIṢḊRẠ  Main link. Argument: A (permutation of [1, ..., n])

Ụ       Grade up; sort the indices of A by their respective values.
        For shuffles, the result is the concatenation of up to two increasing
        sequences of indices.
 I      Compute the forward differences.
        In a shuffle, only one difference may be negative.
  Ṣ     Sort the differences.
   Ḋ    Dequeue; remove the first (smallest) difference.
    R   Range; map each k to [1, ..., k].
        This yields an empty array for non-positive values of k.
     Ạ  All; check if all resulting ranges are non-empty.
Dennis
la source
4

Brachylog , 9 octets

o~cĊ⟨⊆⊇⟩?

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'imprime false.. 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é.

   Ċ         Some length-two list
 ~c          which concatenated
o            is the input sorted
    ⟨        satisfies the condition that its first element
     ⊆       is an ordered not-necessarily-contiguous sublist
        ?    of the input
      ⊇      which is an ordered superlist of
       ⟩     the list's second element.

J'ai l'impression qu'il y a quelque chose dans l'esprit ⊆ᵐqui devrait fonctionner à la place de la construction "sandwich" à quatre octets ⟨⊆⊇⟩.

Chaîne indépendante
la source
1
Je pense que vous êtes la première personne à utiliser un sandwich dans une réponse PPCG (et c'est une belle symétrie :))
Fatalize
3

Python 2 , 75 60 47 octets

merci à Dennis pour -13 octets

x={0}
for v in input():x=x-{v-1}|{v}
len(x)<3>q

Essayez-le en ligne!

La sortie se fait via un code de sortie.

ovs
la source
2

Rubis , 35 octets

->l{l.any?{|a|l&[*1..a]|l==l.sort}}

Essayez-le en ligne!

Comment?

  • l & [*1..a] | lapplique une intersection puis une union: obtenez d'abord les éléments de lqui sont <=apuis ajoutez les éléments restants de lsans changer l'ordre. Si a est le nombre que nous recherchons, cette opération est identique au tri l.
GB
la source
2

Pyth, 5 octets

}SQy+

Suite de tests

}SQy+

    +QQ  concatenated two copies of the (implicit) input
   y     all subsequences of it
}        contain an element equaling
 SQ      the input list sorted 

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 +QQplutôt que *2Q.

xnor
la source
5 octets: }SQy+. Il est étendu à }SQy+QQ.
Erik the Outgolfer le
@EriktheOutgolfer Nice one, thanks.
xnor
1

Pyth , 9 octets

!t-.+xLQS

Suite de tests.

Enregistré 3 octets grâce à isaacg .

Pyth , 14 octets

}SQm.nS.Tcd2./

Essayez-le ici! ou Vérifiez tous les cas de test.

Sorties Trueet respectivement Falsepour riffle-shuffle et non-riffle-shuffle.

Comment?

} SQm.nS.Tcd2./ ~ Programme complet. Lit les entrées de STDIN et les sorties vers STDOUT.

            ./ ~ Retourne toutes les divisions de l'entrée en sous-chaînes disjointes (partition).
   m ~ Carte ci-dessus à l'aide d'une variable d.
         cd2 ~ Coupez d en listes à deux éléments.
       .T ~ Transposition justifiée, ignorant les absences.
      S ~ Tri (lexicographiquement).
    .n ~ Aplatir en profondeur.
} ~ Vérifiez si ce qui précède contient ...
 SQ ~ L'entrée triée.
M. Xcoder
la source
De plus, <#0peut être remplacé par -pour 2 octets supplémentaires.
isaacg
@isaacg Oh ouais facepalm merci. Édité. Édité.
M. Xcoder
0

Perl, 28 octets

Comprend +1 poura

Entrée sur STDIN, 1 basée

perl -aE '$.+=$_==$.for@F,@F;say$.>@F' <<< "3 1 2 4"

Utilise l'algorithme de xnor

Ton Hospel
la source
0

C (gcc) , 61 octets

a,b,B;f(int*A){for(a=b=B=1;*A;A++)a-*A?B*=*A>b,b=*A:++a;b=B;}

Essayez-le en ligne!

Jonathan Frech
la source