L'autre jour, notre équipe s'est rendue dans une salle d'évasion. L'un des casse-tête impliquait une carte de six interrupteurs mécaniques où vous deviez trouver la bonne combinaison d'activation et de désactivation afin de déverrouiller une boîte, un peu comme ceci:

-v-v-v-
-v-v-v-

En tant que développeurs, nous avons décidé qu'il serait plus efficace d'essayer chacune des combinaisons 2 ^ 6 = 64 que de résoudre le puzzle. Nous avons donc assigné un pauvre gars pour faire un comptage binaire:

-v-v-v-
-v-v-v-

-v-v-v-
-v-v-^-

-v-v-v-
-v-^-v-

-v-v-v-
-v-^-^-

etc.

Le défi
Écrivez un programme qui, étant donné que les commutateurs sont tous en position d'arrêt sous forme de chaîne formatée comme ci-dessus, génère toutes les combinaisons d'activation et de désactivation dans n'importe quel ordre.

Vous pouvez écrire soit un programme complet soit une fonction. Ainsi, votre programme peut soit prendre en entrée via stdin, un fichier, soit en tant qu'argument de chaîne unique, et retourner ou imprimer la sortie. S'il est retourné, la sortie peut être dans une liste / tableau / etc. plutôt qu'une seule chaîne. Si la sortie est une seule chaîne, les tableaux doivent être séparés par des retours à la ligne (les retours à la ligne sont autorisés.)

Les chaînes d'entrée correspondront à l'expression régulière r'((-v)+-)(\n(-v)+-)*' et représenteront une carte avec tous les commutateurs désactivés. Cela signifie qu'il n'y a pas de cas zéro et que les commutateurs sont alignés à gauche. Chaque ligne peut ne pas avoir le même nombre de commutateurs.

Chaque carte de sortie doit avoir exactement le même format que l'entrée, sauf que les v peuvent être remplacés par des ^ si nécessaire. Les cartes de sortie peuvent être séparées par un nombre quelconque de sauts de ligne.

Étant donné que l'exécution est naturellement O (2 ^ n) dans le nombre de commutateurs, votre code ne sera pas testé sur plus de 10 commutateurs dans n'importe quel arrangement.

C'est le code-golf, donc le code le plus court en nombre d'octets gagne.

Exemples d'entrées et de sorties

Contribution:

-v-

Sortie possible:

-v-
-^-

Contribution:

-v-
-v-

Sortie possible:

-^-
-^-
-^-
-v-

-v-
-^-


-v-
-v-

Puisqu'il est extrêmement fastidieux de vérifier votre réponse pour un plus grand nombre de commutateurs, voici un script Python en tant qu'outil de vérification d'intégrité. (J'ai inclus un extrait actuellement commenté pour générer la sortie attendue à partir d'un fichier d'entrée donné au cas où vous voudriez plus de cas de test.) C'est un peu moins flexible en termes d'entrée et de sortie que la spécification, malheureusement; placez la chaîne d'entrée dans un fichier nommé 'input' et la sortie séparée par la nouvelle ligne (désolé, pas de formatage de liste) dans un fichier nommé 'output' dans le même répertoire et exécutez python3 sanitycheck.py.

Haskell , 25 24 23 17 octets

mapM$min"^v".pure

Essayez-le en ligne!

-1 octet grâce à @ H.PWiz

-1 octet grâce à @nimi

Renvoie une liste de chaînes. Le TIO a 2 octets supplémentaires pour la déclaration de fonction - j'ai vu d'autres personnes le laisser de côté quand ils écrivent la fonction sans point donc je fais la même chose sauf indication contraire.

Réponse précédente (25 octets)

g 'v'="v^"
g x=[x]
mapM g

Les explications sont toutes pour la réponse précédente, qui fonctionne à peu près de la même manière, sauf que j'ai souligné la définition de g. La façon dont gfonctionne est maintenant en utilisant la comparaison lexical de remplacer ^vpour vet garder tout le reste le même.

Fait intéressant, cela fonctionne pour les standards arbitraires:

>>> mapM g "-----^-----"
  ["-----v-----", "-----^-----"]

Explication (courte)

g 'v'="v^" -- for 'v', choose between 'v' or '^'
g x=[x]    -- for any other character, choose just that character
mapM g     -- find all ways to choose characters using g on the given input

Explication (longue)

mapMest une fonction assez effrayante pour ceux qui ne connaissent pas Haskell. Mais ce n'est pas difficile à comprendre dans ce contexte. En le faisant agir sur les Strings (qui dans Haskell sont des listes de caractères), je l'ai spécialisé dans sa définition des listes. Donc, dans ce contexte, sa signature de type est

mapM :: (a -> [b]) -> [a] -> [[b]]
--      ^^^^^^^^^^                  arg 1: a function from any a to a list of b
--                    ^^^           arg 2: a list of a
--                           ^^^^^ return: a list of list of b

Il est en fait encore plus spécialisé dans mon utilisation - aet bles deux Char- afin que nous puissions voir la signature de type comme

mapM :: (Char -> String) -> String -> [String]

Voyons rapidement ce qui se gpasse avant d'expliquer comment cela mapMfonctionne.

g :: Char -> String
g 'v' = "v^"
g  x  = [x]

gutilise la correspondance de motifs pour convertir le Char 'v'en chaîne "v^"; tout le reste est converti en une chaîne singleton (rappelez-vous, les chaînes ne sont que des listes de Chars, nous pouvons donc mettre xune liste singleton). En testant sur le REPL, on trouve que c'est le cas

>>> g 'a'
  "a"
>>> g 'b'
  "b"
>>> g 'v'
  "v^"

Notez que g a le bon type pour être un argument mapM(sans surprise!).

Nous allons explorer comment cela mapMfonctionne en lui donnant get l'argument

"-v-\n-v-"

comme entrée.

mapMmappe d'abord gsur le String, et parce que gconvertit Chars en Strings, cela nous donne une liste deStrings

["-", "v^", "-", "\n", "-", "v^", "-"]

Bien qu'il s'agisse du type de sortie correct, il en mapMfait un peu plus. Vous pouvez le considérer comme formant tous les Strings que vous pourriez créer à partir de cette liste si vous deviez choisir un seul caractère de chaqueString (dans l'ordre).

Donc, pour le premier élément, vous n'avez pas d'autre choix que de choisir le Char '-'. Pour le deuxième élément, vous pouvez choisir entre'v' et '^', ainsi de suite et ainsi de suite.

Il est à peu près équivalent à ce code python:

result = []
for x1 in "-":
  for x2 in "v^":
    for x3 in "-":
      ...
        result.append(''.join([x1, x2, x3, x4, x5, x6, x7]))

Sauf que depuis Haskell sépare entre Chars et Strings, quand il met leChar s dans une liste, il n'en a pas besoin join.

Donc, la sortie finale est

["-v-\n-v-", "-v-\n-^", "-^-\n-v-", "-^-\n-^-"]

comme voulu.

Perl 6 , 32 octets

{[X~] .comb».&{$_,('^'if /v/)}}

Essayez-le en ligne!

• .comb divise la chaîne en caractères.
• ».&{...} mappe les caractères selon la fonction entre les accolades.
• $_, ('^' if /v/)produit une liste de suppléants pour chaque caractère. N'a vqu'un remplaçant:^ .
• [X~]réduit cette liste avec l'opérateur de produit croisé de concaténation de chaînes X~.

Gelée , 7 octets

«Ƭ€”^Œp

Essayez-le en ligne!

La sortie est une liste de chaînes Jelly.

Explication:

«Ƭ€”^Œp  Arguments: 1
«Ƭ€”^    Dyad-nilad pair
  €       Map over left argument
 Ƭ         Apply repeatedly until a result that has previously been seen is seen
           again, return original and intermediate results
«           Dyad: Minimum of arguments
   ”^     Nilad: Literal: '^'
         Note: 'v' is the only character that is greater than '^' and can
         appear in the input, so, while for every character c other than 'v'
         this operation returns [c], for 'v' it returns ['v', '^']. In this way,
         duplicates are never going to appear in the output.
     Œp  Monad: Cartesian product of elements

Perl 5 , 29 octets

sub{glob"\Q@_"=~s/v/{v,^}/gr}

Essayez-le en ligne!

Ma première soumission!

Normalement, les golfeurs de Perl 5 soumettent des programmes au lieu de fonctions pour éviter d'avoir à inclure sub{}au minimum. Mais ils doivent ajouter say, say␠,say for ousay for␠ en échange.

En allant sous l'approche, je pourrais raccourcir

say for glob"\Q$_"=~s/v/{v,^}/gr        # Perl 5, -0n, 32 bytes

à

sub{glob"\Q@_"=~s/v/{v,^}/gr}           # Perl 5, 29 bytes

L'explication est assez simple. Perl 5 a un globopérateur intégré qui accepte un modèle glob de type shell qui peut être utilisé pour générer des listes de noms de fichiers (par exemple foo*.txt) ou une liste de chaînes (par exemple {a,b,c}). Le hic, c'est que la nouvelle ligne doit être échappée, ce que j'ai fait en utilisant quotemeta(as \Q).

K (ngn / k) , 27 25 octets

{?(,/,/:\:)/x,'"^"/"v"\x}

Essayez-le en ligne!

"^"/"v"\ remplacer "v" par"^"

x,' zip avec les caractères d'origine

(,/,/:\:)/ produit cartésien terminé

? uniq

APL (Dyalog Classic) , 21 17 15 octets

⊃⊢∘.,.∪'v'⎕r'^'

Essayez-le en ligne!

semblable à ma solution k

renvoie un tableau de chaînes à n dimensions (n ​​= nombre de commutateurs)

sous une forme plus facile à expliquer: ⊃(∘.,⌿ ⊢ ∪¨ 'v'⎕r'^')

'v'⎕r'^'remplacer vs par ^s

⊢ ∪¨... des unions avec chacun des personnages originaux. c'est un vecteur de chaînes de longueur 1 ou 2

∘.,⌿ réduction du produit cartésien

⊃ divulguer

pour arriver à la version entièrement golfée, nous suivons le modèle f⌿ A g¨ B-> A f.g B:

∘.,⌿ ⊢ ∪¨ 'v'⎕r'^' -> ⊢ ∘.,.∪ 'v'⎕r'^'

comme effet secondaire les parenthèses ne sont plus nécessaires

J , 42 octets

]`('v'I.@e.~[)`[}"1'v^'{~2#:@i.@^1#.e.&'v'

Essayez-le en ligne!

explication

]`('v' I.@e.~ [)`[}"1 ('v^' {~ 2 #:@i.@^ 1 #. e.&'v')

Laisse prendre

-v-
-v-

comme notre exemple d'entrée.

• ('v^' {~ 2 #:@i.@^ 1 #. e.&'v')crée tous les combos possibles uniquement des commutateurs, en ignorant le format d'entrée. pour notre exemple, il produit:

  vv
  v^
  ^v
  ^^
  

  • 1 #. e.&'v'compte le nombre de vs dans l'entrée.
  • 2 #:@i.@^élève 2 à cette puissance, produit les entiers de 0 à ce nombre i.et les convertit en binaire#:
  • 'v^' {~modifications apportées aux chiffres binaires vet^
• ]`('v' I.@e.~ [)`[}"1modifie l'entrée d'origine, en produisant une copie pour chaque ligne du résultat décrit à l'étape précédente (c'est-à-dire tous les combos v/ possibles ^). Dans chaque copie, l' ventrée d'origine est remplacée par une séquence possible de v/ ^.

Java, 202 197 189 191 octets

Oui, c'est un langage relativement verbeux, mais c'est ce que je considère comme du golf classique:

import java.util.function.Function;

public class SwitchBored
{
    public static void main(String[] args)
    {
        Function<String, String> f = s->{byte i,j,k,m=1,u='^',d='v',a[]=(s+"\n\n").getBytes();for(i=0,s="";i<m;i++,s+=new String(a))for(j=0,k=0;k<a.length;k++){if(a[k]==d||a[k]==u){a[k]=(i&1<<j++)!=0?u:d;m<<=i>0?0:1;}}return s;};

        //System.out.println(f.apply("-v-"));
        System.out.println(f.apply("-v-v-v-\n-v-v-v-"));
        //System.out.println(f.apply("-v-v-v-\n-v-v-"));
        //System.out.println(f.apply("-v-v-v-v-v-\n-v-"));
        //System.out.println(f.apply("-v-v-v-v-v-\n-v-v-v-v-v-"));
    }
}

Je pensais qu'une façon "simple" de traiter les sauts de ligne nécessaires pour obtenir une mise en page correcte était de réutiliser le tableau de caractères d'entrée d'origine et de le remplir uniquement avec 'v's et'^' s aux positions appropriées.

Mises à jour:

Il s’est avéré que le fait de ne pas stocker les positions permet d’abandonner les intdéclarations des variables et du tableau (au prix de vérifier si chaque position du tableau contient unv ou ^à la volée), économisant 5 octets.

8 octets supplémentaires enregistrés en calculant la limite supérieure (1<<numberOfSwitches) supérieure de manière plus compacte.

Selon la règle mentionnée dans le commentaire, la déclaration de fonction doit être comptée, alors maintenant c'est un lambda ...

J , 41 40 24 octets

[:>@,@{<@(,'^'$~'v'=])"0

Essayez-le en ligne!

Python 2 , 87 octets

def f(s):i=s.find('v');return(i>=0and f(s[:i].replace('^','v')+'^'+s[i+1:])+'\n'or'')+s

Essayez-le en ligne!

Une approche non regex.

C (gcc) , 75 74 70 octets

-5 octets grâce à @ceilingcat

*b=0;f(char*s){b=b?b:s;*s?f(s+1),*s>46?*s=94,f(s+1),*s='v':0:puts(b);}

Essayez-le en ligne!

nécessite que les spoints de mémoire soient accessibles en écriture

Python 3.8 (pré-version) , 129117116110 octets

-10 octets grâce à @Chas Brown

f=lambda s:{s.replace('v','{}').format(*['v^'[c<'1']for c in bin(x+i)[::-1]])for i in range(x:=1<<len(s))}

Essayez-le en ligne!

C (gcc) , 102 octets

i,j,l;f(char*s){for(l=j=0;l++<1<<j;puts(""))for(i=j=0;s[i];i++)putchar(s[i]>64?l&1<<j++?118:94:s[i]);}

Essayez-le en ligne!

K4 , 44 octets

Solution:

-1{@[x;&w;:;]@'"v^"@a\:'!*/a:(+/w:"v"=x)#2};

Exemples:

q)k)-1{@[x;&w;:;]@'"v^"@a\:'!*/a:(+/w:"v"=x)#2}"-v-";
-v-
-^-

q)k)-1{@[x;&w;:;]@'"v^"@a\:'!*/a:(+/w:"v"=x)#2}"-v-\n-v-";
-v-
-v-
-v-
-^-
-^-
-v-
-^-
-^-

q)k)-1{@[x;&w;:;]@/:"v^"@a\:'!*/a:(+/w:"v"=x)#2}"-v-v-\n-v-v-v-\n-v-";
-v-v-
-v-v-v-
-v-
-v-v-
-v-v-v-
-^-
-v-v-
-v-v-^-
-v-
-v-v-
-v-v-^-
-^-
-v-v-
-v-^-v-
-v-
-v-v-
-v-^-v-
-^-
-v-v-
-v-^-^-
-v-
-v-v-
-v-^-^-
-^-
-v-v-
-^-v-v-
-v-
-v-v-
-^-v-v-
-^-
-v-v-
-^-v-^-
-v-
-v-v-
-^-v-^-
-^-
-v-v-
-^-^-v-
-v-
-v-v-
-^-^-v-
-^-
-v-v-
-^-^-^-
-v-
-v-v-
-^-^-^-
-^-
-v-^-
-v-v-v-
-v-
-v-^-
-v-v-v-
-^-
-v-^-
-v-v-^-
-v-
-v-^-
-v-v-^-
-^-
-v-^-
-v-^-v-
-v-
-v-^-
-v-^-v-
-^-
-v-^-
-v-^-^-
-v-
-v-^-
-v-^-^-
-^-
-v-^-
-^-v-v-
-v-
-v-^-
-^-v-v-
-^-
-v-^-
-^-v-^-
-v-
-v-^-
-^-v-^-
-^-
-v-^-
-^-^-v-
-v-
-v-^-
-^-^-v-
-^-
-v-^-
-^-^-^-
-v-
-v-^-
-^-^-^-
-^-
-^-v-
-v-v-v-
-v-
-^-v-
-v-v-v-
-^-
-^-v-
-v-v-^-
-v-
-^-v-
-v-v-^-
-^-
-^-v-
-v-^-v-
-v-
-^-v-
-v-^-v-
-^-
-^-v-
-v-^-^-
-v-
-^-v-
-v-^-^-
-^-
-^-v-
-^-v-v-
-v-
-^-v-
-^-v-v-
-^-
-^-v-
-^-v-^-
-v-
-^-v-
-^-v-^-
-^-
-^-v-
-^-^-v-
-v-
-^-v-
-^-^-v-
-^-
-^-v-
-^-^-^-
-v-
-^-v-
-^-^-^-
-^-
-^-^-
-v-v-v-
-v-
-^-^-
-v-v-v-
-^-
-^-^-
-v-v-^-
-v-
-^-^-
-v-v-^-
-^-
-^-^-
-v-^-v-
-v-
-^-^-
-v-^-v-
-^-
-^-^-
-v-^-^-
-v-
-^-^-
-v-^-^-
-^-
-^-^-
-^-v-v-
-v-
-^-^-
-^-v-v-
-^-
-^-^-
-^-v-^-
-v-
-^-^-
-^-v-^-
-^-
-^-^-
-^-^-v-
-v-
-^-^-
-^-^-v-
-^-
-^-^-
-^-^-^-
-v-
-^-^-
-^-^-^-
-^-

Explication:

Remplacement sur place de "^". Déterminer le nombre de combinaisons de commutateurs (par exemple 2 ^ n), compter en binaire, remplacer les commutateurs ...

-1{@[x;&w;:;]@'"v^"@a\:'!*/a:(+/w:"v"=x)#2}; / the solution
-1                                         ; / print to STDOUT, swallow -1
  {                                       }  / lambda taking implicit x
                                        #2   / take 2
                             (         )     / do this together
                                  "v"=x      / does input = "v" ?
                                w:           / save as w
                              +/             / sum up
                           a:                / save as a
                         */                  / product
                        !                    / range 0..n
                    a\:'                     / convert each to base-2
               "v^"@                         / index into "v^"
             @'                              / apply each
   @[x;&w;:;]                                / apply assignment to x at indexes where w is true

R , 116 octets

function(x,u=utf8ToInt(x))apply(expand.grid(rep(list(c(118,94)),sum(u>45))),1,function(i)intToUtf8(`[<-`(u,u>45,i)))

Essayez-le en ligne!

Fonction renvoyant un vecteur de planches séparées par une nouvelle ligne

JavaScript, 88 octets

s=>(g=n=>n--?g(n)+`
`+s.replace(/v/g,_=>'v^'[i=n&1,n>>=1,i]):'')(2**~-s.split`v`.length)

Essayez-le en ligne!

Retina 0.8.2 , 29 octets

T`¶v`;#
+%1`#
v$'¶$`^
%`;|$
¶

Essayez-le en ligne! Explication:

T`¶v`;#

Changez les sauts de ligne en ;s et les vs en #marqueurs.

+%1`#

Remplacez le #s un à la fois de gauche à droite.

v$'¶$`^

Changez chaque ligne en deux lignes, une #remplacée par un v, une remplacée par un ^.

%`;|$
¶

Remplacez les ;s par de nouvelles lignes et séparez les résultats.

Perl 5 -0 , 51 octets

$_=<>;s/\s/P/g;s/v/{v,^}/g;say s/P|$/\n/gr for glob

Essayez-le en ligne!

JavaScript (Node.js) , 80 73 68 octets

f=([x,...y],g=c=>f(y).map(z=>c+z))=>x?g(x).concat(x>'a'?g`^`:[]):[y]

Essayez-le en ligne!

Python 3 - construction, 203 octets

def f(a):
 b=[0]
 for l in a.split():b+=[b[-1]+l.count('v')]
 return'\n'.join(''.join(f"{k:b}".zfill(b[-1])[x:y]+'-\n'for x,y in zip(b,b[1:]))for k in range(2**b[-1])).replace('0','-v').replace('1','-^')

Essayez-le en ligne!

Essayez d'abord, pas très petit mais ça marche. Il n'y a pas de remplacement de chaîne élégant en Python ...

La première boucle construit un mappage de lignes en index de bits, c'est-à-dire que pour chaque ligne, l'index du premier bit d'un compteur de bits est stocké. Ceci est utilisé pour indexer le compteur de bits dans la boucle suivante.

La deuxième boucle exécute un compteur binaire, extrait les bits pour chaque ligne et itération et les joint. Après avoir tout réuni, il est retransformé au format de carte de commutateur, en utilisant le remplacement de chaîne.

Je suppose qu'il existe un moyen plus élégant de réutiliser la chaîne d'entrée au lieu de la reconstruire encore et encore.

Edit: inspiré par la réponse Python 3.8 , voici une version de remplacement beaucoup plus courte

Python 3 - remplacer, 123 octets

def f(a):r=range;n=a.count('v');return'\n'.join(a.replace('v','{}').format(*('v^'[k&2**i>0]for i in r(n)))for k in r(2**n))

Essayez-le en ligne!

Rubis , 64 octets

Renvoie un tableau. Obtient des nombres de$1$ à $2^v$ (où $v$ est le nombre de "v" dans l'entrée) et bascule les commutateurs en fonction de la $v$bits les moins significatifs. Cela nous permet d'économiser un octet sur l'itération de$0$ à $2^v-1$, parce que le $v$ bits les moins significatifs $2^v$ sont tous nuls.

Dans Ruby, i[j]retourne le je bit ià partir du bit le moins significatif, c'est-à-dire qu'il est équivalent à (i>>j)&1.

->s{(1..2**s.count(?v)).map{|i|j=-1;s.gsub(/v/){'v^'[i[j+=1]]}}}

Essayez-le en ligne!

Fusain , 28 octets

⪫ＥＸ²№θv⭆θ⎇⁼λv§v^÷ιＸ²№…θμv붶

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication:

   ²                            Literal 2
  Ｘ                             Raised to power
    №                           Count of
      v                         Literal `v`
     θ                          In input string
 Ｅ                              Map over implicit range
        θ                       Input string
       ⭆                        Map over characters and join
           λ                    Current character
          ⁼                     Equal to
            v                   Literal `v`
         ⎇                      Then
              v^                Literal `v^`
             §                  Circularly indexed by
                 ι              Outer index
                ÷               Integer divided by
                   ²            Literal 2
                  Ｘ             Raised to power
                    №           Count of
                        v       Literal `v`
                      θ         In input string
                     …          Truncated to length
                       μ        Inner index
                         λ      Else current character
⪫                         ¶¶    Join with newlines
                                Implicitly print

PHP , 93 octets

for(;$j<1<<$x;$j+=print$s)for($x=0,$s=$argv[1];$i=strpos($s,v,$i+1);$s[$i]=$j&1<<$x++?'^':v);

Essayez-le en ligne!

Programme autonome, entrée via la ligne de commande.

Boucle le nombre de permutations possibles de la chaîne d'entrée en fonction du nombre de v. Pendant le décompte en binaire, remplacez chaque binaire 1par un ^et chaque binaire 0par un vdans la chaîne d'entrée.