El otro día, nuestro equipo fue a una sala de escape. Uno de los acertijos involucraba una placa de seis interruptores mecánicos donde tenía que encontrar la combinación correcta de encendido y apagado para desbloquear una caja, algo así:

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

Como desarrolladores, decidimos que sería más eficiente probar cada una de las combinaciones 2 ^ 6 = 64 que resolver el rompecabezas. Entonces le asignamos a un pobre tipo que haga un recuento binario:

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

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

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

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

y así.

El desafío
Escriba un programa que, dado que todos los interruptores están en la posición de apagado como una cadena con el formato anterior, genera todas las combinaciones de encendido y apagado en cualquier orden.

Puede escribir un programa completo o una función. Por lo tanto, su programa puede recibir la entrada a través de stdin, un archivo o como un argumento de cadena única, y puede devolver o imprimir la salida. Si se devuelve, la salida puede estar en una lista / matriz / etc. en lugar de una sola cadena. Si la salida es una sola cadena, los tableros deben estar separados por nuevas líneas (se permiten nuevas líneas finales).

Las cadenas de entrada coincidirán con la expresión regular r'((-v)+-)(\n(-v)+-)*'y representarán una placa con todos los interruptores apagados. Esto significa que no hay mayúsculas y cero, y los interruptores están alineados a la izquierda. Es posible que cada fila no tenga el mismo número de interruptores.

Cada placa de salida debe tener exactamente el mismo formato que la entrada, excepto que las v se pueden reemplazar por ^ 's según sea necesario. Las placas de salida se pueden separar por cualquier número de nuevas líneas.

Dado que el tiempo de ejecución es naturalmente O (2 ^ n) en la cantidad de interruptores, su código no se probará en más de 10 interruptores en ninguna disposición.

Este es el código de golf, por lo que gana el código más corto en número de bytes.

Muestra de entradas y salidas

Entrada:

-v-

Salida posible:

-v-
-^-

Entrada:

-v-
-v-

Salida posible:

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

-v-
-^-


-v-
-v-

Dado que es extremadamente tedioso verificar su respuesta para un mayor número de interruptores, aquí hay un script de Python como una herramienta de verificación de cordura. (He incluido un fragmento actualmente comentado para generar la salida esperada de un archivo de entrada dado en caso de que desee más casos de prueba). Desafortunadamente, es un poco menos flexible en términos de entrada y salida que la especificación; coloque la cadena de entrada en un archivo llamado 'input' y la salida separada por la nueva línea (lo siento, sin formato de lista) en un archivo llamado 'output' en el mismo directorio y ejecútelo python3 sanitycheck.py.

Haskell , 25 24 23 17 bytes

mapM$min"^v".pure

Pruébalo en línea!

-1 byte gracias a @ H.PWiz

-1 byte gracias a @nimi

Devuelve una lista de cadenas. El TIO tiene 2 bytes adicionales para la declaración de función: he visto a otras personas dejarlo cuando escriben la función sin puntos, así que estoy haciendo lo mismo a menos que se indique lo contrario.

Respuesta anterior (25 bytes)

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

Las explicaciones son todas para la respuesta anterior, que funciona más o menos de la misma manera, excepto que subrayé la definición de g. La manera gfunciona ahora es mediante el uso de comparación léxica de sustituir ^vpor vy mantener todo lo demás igual.

Curiosamente, esto funciona para cuadros de distribución arbitrarios:

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

Explicación (corta)

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

Explicación (larga)

mapMes una función bastante aterradora para aquellos que no están familiarizados con Haskell. Pero no es difícil de entender en este contexto. Al hacerlo actuar en Strings (que en Haskell son listas de caracteres), lo he especializado en su definición de listas. Entonces, en este contexto, su firma de tipo es

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

En realidad, es aún más especializado en mi uso, ay bson ambos Char, por lo que podemos ver la firma de tipo como

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

Veamos rápidamente qué ghace antes de explicar cómo mapMfunciona.

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

gutiliza la coincidencia de patrones para convertir el Char 'v'en la cadena "v^"; todo lo demás se convierte en una cadena singleton (recuerde, las cadenas son solo listas de Chars, por lo que podemos ponerlas xen una lista singleton). Al probar REPL, encontramos que este es el caso

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

Tenga en cuenta que gtiene el tipo correcto para ser un argumento de mapM(¡como era de esperar!).

Exploraremos cómo mapMfunciona dándole gy el argumento

"-v-\n-v-"

como entrada

mapMprimeros mapas gsobre String, y porque gconvierte Chars en Strings, esto nos da una lista deStrings

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

Si bien este es el tipo de salida correcto, mapMhace un poco más. Puede pensar que forma todos los correos Stringelectrónicos que podría crear a partir de esta lista si tuviera que elegir un solo carácter de cada uno Stringen ella (en orden).

Entonces, para el primer elemento, no tiene otra opción que elegir el Char '-'. Para el segundo elemento, puede elegir entre 'v'y '^', y así sucesivamente.

Es más o menos equivalente a este código de Python:

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

Excepto que, dado que Haskell se separa entre Charsy Strings, cuando coloca las Chars en una lista, no las necesita join.

Entonces el resultado final es

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

como se desee.

Perl 6 , 32 bytes

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

Pruébalo en línea!

• .comb divide la cadena en caracteres.
• ».&{...} asigna los caracteres de acuerdo con la función entre llaves.
• $_, ('^' if /v/)produce una lista de alternativas para cada personaje. Sólo vtiene una alternativa: ^.
• [X~]reduce esa lista con el operador de productos cruzados de concatenación de cadenas X~.

Jalea , 7 bytes

«Ƭ€”^Œp

Pruébalo en línea!

La salida es una lista de cadenas Jelly.

Explicación:

«Ƭ€”^Œ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 bytes

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

Pruébalo en línea!

Mi primera sumisión!

Normalmente, los golfistas de Perl 5 envían programas en lugar de funciones para evitar tener que incluir sub{}como mínimo. Pero tienen que añadir say, say␠, say foro say for␠a cambio.

Al ir al enfoque secundario, podría acortar

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

a

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

La explicación es bastante simple. Perl 5 tiene un globoperador incorporado que acepta un patrón de globo tipo shell que puede usarse para generar listas de nombres de archivo (por ejemplo foo*.txt) o una lista de cadenas (por ejemplo {a,b,c}). El problema es que la nueva línea necesita escapar, lo que he hecho usando quotemeta(como \Q).

K (ngn / k) , 27 25 bytes

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

Pruébalo en línea!

"^"/"v"\reemplazar "v"con"^"

x,' zip con los caracteres originales

(,/,/:\:)/ producto cartesiano sobre

? uniq

APL (Dyalog Classic) , 21 17 15 bytes

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

Pruébalo en línea!

similar a mi solución k

devuelve una matriz n-dimensional de cadenas (n = número de conmutadores)

en forma más fácil de explicar: ⊃(∘.,⌿ ⊢ ∪¨ 'v'⎕r'^')

'v'⎕r'^'reemplazar vs con ^s

⊢ ∪¨... uniones con cada uno de los personajes originales. es un vector de cadenas de longitud 1 o 2

∘.,⌿ reducción de productos cartesianos

⊃ revelar

para llegar a la versión totalmente golfizada seguimos el patrón f⌿ A g¨ B-> A f.g B:

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

como efecto secundario los paréntesis ya no son necesarios

J , 42 bytes

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

Pruébalo en línea!

explicación

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

Dejar tomar

-v-
-v-

como nuestro ejemplo de entrada.

• ('v^' {~ 2 #:@i.@^ 1 #. e.&'v')crea todos los combos posibles de solo los interruptores, ignorando el formato de entrada. para nuestro ejemplo produce:

  vv
  v^
  ^v
  ^^
  

  • 1 #. e.&'v'cuenta los números de vs en la entrada.
  • 2 #:@i.@^eleva 2 a esa potencia, produce los enteros de 0 a ese número i.y los convierte en binarios#:
  • 'v^' {~Los cambios en los dígitos binarios vy^
• ]`('v' I.@e.~ [)`[}"1modifica la entrada original, produciendo una copia para cada fila del resultado descrito en el paso anterior (es decir, todos los posibles v/ ^combos). En cada copia, la ventrada original se reemplaza con una posible secuencia de v/ ^.

Java, 202 197 189 191 bytes

Sí, es un lenguaje comparativamente detallado, pero eso es lo que considero como golf clásico:

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-"));
    }
}

Pensé que una manera "simple" de hacer frente a los saltos de línea que son necesarias para lograr que el diseño apropiado era que en realidad re-utilizar la matriz de caracteres de entrada original, y sólo llenarlo con 'v's y '^'S a las posiciones adecuadas.

Actualizaciones:

Resultó que no almacenar las posiciones permite deshacerse de las intdeclaraciones de variables de la matriz (a costa de verificar cada posición de la matriz si contiene una vo ^sobre la marcha), ahorrando 5 bytes.

Otros 8 bytes guardados al calcular el límite (1<<numberOfSwitches)superior de manera más compacta.

De acuerdo con la regla mencionada en el comentario, la declaración de función debe contarse, por lo que ahora es una lambda ...

J , 41 40 24 bytes

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

Pruébalo en línea!

Python 2 , 87 bytes

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

Pruébalo en línea!

Un enfoque no regex.

C (gcc) , 75 74 70 bytes

-5 bytes gracias a @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);}

Pruébalo en línea!

requiere que los spuntos de memoria sean grabables

Python 3.8 (prelanzamiento) , 129117116101 bytes

-10 bytes gracias a @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))}

Pruébalo en línea!

C (gcc) , 102 bytes

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]);}

Pruébalo en línea!

K4 , 44 bytes

Solución:

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

Ejemplos:

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-
-^-^-
-^-^-^-
-^-

Explicación:

Reemplazo en el lugar de "^". Determine el número de combinaciones de interruptores (por ejemplo, 2 ^ n), cuente en binario, reemplace los interruptores ...

-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 bytes

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

Pruébalo en línea!

Función que devuelve un vector de tableros separados de nueva línea

JavaScript, 88 bytes

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

Pruébalo en línea!

Retina 0.8.2 , 29 bytes

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

Pruébalo en línea! Explicación:

T`¶v`;#

Cambie las nuevas líneas en ;sy las vs en #marcadores.

+%1`#

Reemplace el #s uno a la vez de izquierda a derecha.

v$'¶$`^

Cambie cada línea en dos líneas, una con el #reemplazado por a v, otra con el reemplazado por a ^.

%`;|$
¶

;Vuelva a cambiar la s a nuevas líneas y separe los resultados.

Perl 5 -0 , 51 bytes

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

Pruébalo en línea!

JavaScript (Node.js) , 80 73 68 bytes

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

Pruébalo en línea!

Python 3 - construcción, 203 bytes

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','-^')

Pruébalo en línea!

Primer intento, no muy pequeño pero funciona. No hay reemplazo de cuerda elegante en Python ...

El primer bucle crea una asignación de líneas a índices de bits, es decir, para cada línea, se almacena el índice del primer bit en un contador de bits. Esto se usa para indexar el contador de bits en el siguiente ciclo.

El segundo bucle ejecuta un contador binario, extrae los bits para cada línea e iteración y los une. Después de unir todo, se traduce nuevamente al formato de mapa de conmutación, utilizando el reemplazo de cadena.

Supongo que hay una manera más elegante reutilizando la cadena de entrada en lugar de reconstruirla una y otra vez.

Editar: inspirado en la respuesta de Python 3.8 , aquí hay una versión de reemplazo mucho más corta

Python 3 - reemplazar, 123 bytes

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))

Pruébalo en línea!

Ruby , 64 bytes

$1$$2^v$$v$$v$$0$$2^v-1$$v$$2^v$

En Ruby, i[j]devuelve el jbit de iinicio desde el bit menos significativo, es decir, es equivalente a (i>>j)&1.

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

Pruébalo en línea!

Carbón , 28 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

   ²                            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 bytes

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);

Pruébalo en línea!

Programa independiente, entrada por línea de comando.

Repita el número de posibles permutaciones de la cadena de entrada en función del número de v's. Mientras cuenta en binario, reemplace cada binario 1con a ^y cada binario 0con a ven la cadena de entrada.