No outro dia, nossa equipe foi para uma sala de fuga. Um dos quebra-cabeças envolvia uma placa de seis interruptores mecânicos, onde era necessário encontrar a combinação correta de ligar e desligar para destravar uma caixa, mais ou menos assim:

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

Sendo desenvolvedores, decidimos que seria mais eficiente tentar todas as combinações 2 ^ 6 = 64 do que realmente resolver o enigma. Então, designamos um cara pobre para fazer uma contagem binária:

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

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

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

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

e assim por diante.

O desafio
Escreva um programa que, considerando todos os interruptores na posição desligado, como uma string formatada como acima, gere todas as combinações de ligado e desligado em qualquer ordem.

Você pode escrever um programa completo ou uma função. Portanto, seu programa pode receber entradas através de stdin, um arquivo ou como um argumento de cadeia única e retornar ou imprimir a saída. Se retornado, a saída pode estar em uma lista / array / etc. em vez de uma única sequência. Se a saída for uma única sequência, as placas deverão ser separadas por novas linhas (novas linhas finais são permitidas).

As seqüências de entrada corresponderão ao regex r'((-v)+-)(\n(-v)+-)*'e representarão uma placa com todos os interruptores desativados. Isso significa que não há zero caso, e os comutadores estão alinhados à esquerda. Cada linha pode não ter o mesmo número de opções.

Cada placa de saída deve ter exatamente o mesmo formato da entrada, exceto que os vs podem ser substituídos por ^ 's conforme necessário. As placas de saída podem ser separadas por qualquer número de novas linhas.

Como o tempo de execução é naturalmente O (2 ^ n) no número de comutadores, seu código não será testado em mais de 10 comutadores em qualquer organização.

Este é o código-golfe, pelo que o código mais curto em número de bytes vence.

Amostras de entradas e saídas

Entrada:

-v-

Saída possível:

-v-
-^-

Entrada:

-v-
-v-

Saída possível:

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

-v-
-^-


-v-
-v-

Como é extremamente tedioso verificar sua resposta para um número maior de opções, aqui está um script Python como uma ferramenta de verificação de integridade. (Incluí um trecho comentado no momento para gerar a saída esperada de um determinado arquivo de entrada, caso você queira mais casos de teste.) É um pouco menos flexível em termos de entrada e saída do que a especificação, infelizmente; coloque a string de entrada em um arquivo chamado 'input' e a saída separada por nova linha (desculpe, sem formatação de lista) em um arquivo chamado 'output' no mesmo diretório e execute python3 sanitycheck.py.

Haskell , 25 24 23 17 bytes

mapM$min"^v".pure

Experimente online!

-1 byte graças a @ H.PWiz

-1 byte graças a @nimi

Retorna uma lista de strings. O TIO possui 2 bytes extras para a declaração da função - vi outras pessoas desativando-as quando escrevem a função sem pontos, então estou fazendo o mesmo, a menos que seja dito o contrário.

Resposta anterior (25 bytes)

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

As explicações são todas para a resposta anterior, que funciona praticamente da mesma maneira, exceto que eu descrevi a definição de g. A forma como gfunciona agora é usando comparação lexical de substituir ^vpor ve manter tudo o mais o mesmo.

Curiosamente, isso funciona para quadros de distribuição arbitrários:

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

Explicação (Breve)

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

Explicação (longa)

mapMé uma função bastante assustadora para aqueles que não estão familiarizados com Haskell. Mas não é difícil de entender neste contexto. Ao fazê-lo agir sobre Strings (que em Haskell são listas de caracteres), eu o especializei em sua definição para listas. Portanto, nesse contexto, sua assinatura de tipo é

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

Na verdade, ele é ainda mais especializado em meu uso - ae bambos Char- para que possamos ver a assinatura do tipo como

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

Vamos analisar rapidamente o que gfaz antes de explicar como mapMfunciona.

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

gusa a correspondência de padrões para converter Char 'v'a string "v^"; todo o resto é convertido em uma string singleton (lembre-se, strings são apenas listas de Chars, para que possamos colocar xuma lista singleton). Testando no REPL, descobrimos que este é o caso

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

Observe que gtem o tipo certo para ser um argumento mapM(sem surpresa!).

Vamos explorar como mapMfunciona, fornecendo-o ge o argumento

"-v-\n-v-"

como entrada.

mapMprimeiros mapas gsobre Stringe, como gconverte Chars para Strings, isso nos fornece uma lista deStrings

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

Embora este seja o tipo de saída correto, mapMfaz um pouco mais. Você pode pensar nisso como formando todos os Strings que você poderia criar nesta lista se tivesse que escolher um único caractere para cada um deles String(em ordem).

Portanto, para o primeiro elemento, você não tem outra escolha senão escolher o Char '-'. Para o segundo elemento, você pode escolher entre 'v'e '^'assim por diante.

É aproximadamente equivalente a este código python:

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

Exceto que desde separa Haskell entre Chars e Strings, quando ele coloca os Chars em uma lista, ele não precisa joindeles.

Portanto, a saída final é

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

como desejado.

Perl 6 , 32 bytes

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

Experimente online!

• .comb divide a string em caracteres.
• ».&{...} mapeia os caracteres de acordo com a função entre os chavetas.
• $_, ('^' if /v/)produz uma lista de alternativas para cada caractere. Só vtem uma alternativa: ^.
• [X~]reduz essa lista com o operador de produto cruzado de concatenação de cadeias X~.

Geléia , 7 bytes

«Ƭ€”^Œp

Experimente online!

Saída é uma lista de seqüências de caracteres Jelly.

Explicação:

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

Experimente online!

Minha primeira submissão!

Normalmente, os golfistas do Perl 5 enviam programas em vez de funções para evitar a necessidade de incluir sub{}no mínimo. Mas eles têm que adicionar say, say␠, say forou say for␠em troca.

Seguindo a sub-abordagem, eu poderia reduzir

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

para

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

A explicação é bastante simples. O Perl 5 possui um globoperador interno que aceita um padrão glob do tipo shell que pode ser usado para gerar listas de nomes de arquivos (por exemplo foo*.txt) ou lista de strings (por exemplo {a,b,c}). O problema é que a nova linha precisa ser escapada, o que eu fiz usando quotemeta(as \Q).

K (ngn / k) , 27 25 bytes

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

Experimente online!

"^"/"v"\substitua "v"por"^"

x,' zip com os caracteres originais

(,/,/:\:)/ produto cartesiano

? uniq

APL (Dyalog Classic) , 21 17 15 bytes

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

Experimente online!

semelhante à minha solução k

retorna uma matriz n-dimensional de cadeias (n = número de opções)

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

'v'⎕r'^'substitua vs por ^s

⊢ ∪¨... uniões com cada um dos personagens originais. é um vetor de cadeias de comprimento 1 ou 2

∘.,⌿ redução de produto cartesiano

⊃ divulgar

para chegar à versão completa, seguimos o padrão f⌿ A g¨ B-> A f.g B:

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

como efeito colateral, os parênteses não são mais necessários

J , 42 bytes

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

Experimente online!

explicação

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

Vamos dar

-v-
-v-

como nosso exemplo de entrada.

• ('v^' {~ 2 #:@i.@^ 1 #. e.&'v')cria todos os combos possíveis apenas dos comutadores, ignorando o formato de entrada. para o nosso exemplo, ele produz:

  vv
  v^
  ^v
  ^^
  

  • 1 #. e.&'v'conta os números de vs na entrada.
  • 2 #:@i.@^aumenta 2 para esse poder, produz os números inteiros de 0 para esse número i.e os converte em binários#:
  • 'v^' {~muda para dígitos binários para ve^
• ]`('v' I.@e.~ [)`[}"1altera a entrada original, produzindo uma cópia para cada linha do resultado descrito na etapa anterior (ou seja, todos os possíveis v/ ^combos). Em cada cópia, a ventrada original é substituída por uma sequência possível de v/ ^.

Java, 202 197 189 191 bytes

Sim, é uma linguagem comparativamente detalhada, mas é isso que considero como golfe clássico:

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

Eu pensei que uma maneira "simples" de lidar com as quebras de linha necessárias para obter o layout adequado era realmente reutilizar a matriz de caracteres de entrada original e preenchê-la apenas com 'v' s e '^'s nas posições apropriadas.

Atualizações:

Descobriu-se que não armazenar as posições permite abandonar as intdeclarações de variáveis ​​e array (ao custo de verificar cada posição do array se ele contém umv ou ^em movimento), economizando 5 bytes.

Outros 8 bytes salvos ao calcular o limite superior (1<<numberOfSwitches) superior de forma mais compacta.

De acordo com a regra mencionada no comentário, a declaração da função deve ser contada, então agora é uma lambda ...

J , 41 40 24 bytes

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

Experimente online!

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

Experimente online!

Uma abordagem não regular.

C (gcc) , 75 74 70 bytes

-5 byte graças 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);}

Experimente online!

requer que os spontos de memória sejam graváveis

Python 3.8 (pré-lançamento) , 129 117 116 110 106 bytes

-10 bytes graças 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))}

Experimente online!

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

Experimente online!

K4 , 44 bytes

Solução:

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

Exemplos:

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

Explicação:

Substituição no local de "^". Determine o número de combinações de comutadores (por exemplo, 2 ^ n), conte em binário, substitua comutadores ...

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

Experimente online!

Função retornando um vetor de placas separadas por nova linha

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)

Experimente online!

Retina 0.8.2 , 29 bytes

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

Experimente online! Explicação:

T`¶v`;#

Altere as novas linhas em ;s e vs em #marcadores.

+%1`#

Substitua os #um de cada vez, da esquerda para a direita.

v$'¶$`^

Mude cada linha em duas linhas, uma com a #substituída por a v, uma com a substituída por a ^.

%`;|$
¶

Mude as ;costas para novas linhas e espace os resultados.

Perl 5 -0 , 51 bytes

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

Experimente online!

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]

Experimente online!

Python 3 - construção, 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','-^')

Experimente online!

Primeira tentativa, não muito pequena, mas funciona. Não há substituição de string elegante no Python ...

O primeiro loop constrói um mapeamento de linhas para índices de bits, ou seja, para cada linha, o índice do primeiro bit em um contador de bits é armazenado. Isso é usado para indexar o contador de bits no próximo loop.

O segundo loop executa um contador binário, extrai os bits para cada linha e iteração e os une. Depois de juntar tudo, ele é convertido de volta para o formato do mapa de comutador, usando a substituição de string.

Eu acho que existe uma maneira mais elegante de reutilizar a string de entrada em vez de reconstruí-la repetidamente.

Edit: inspirado na resposta do Python 3.8 , aqui está uma versão de substituição muito mais curta

Python 3 - substituir, 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))

Experimente online!

Rubi , 64 bytes

$1$$2^v$$v$$v$$0$$2^v-1$$v$$2^v$ são todos zero.

Em Ruby, i[j]retorna o jth bit da ipartida do bit menos significativo, ou seja, é equivalente a (i>>j)&1.

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

Experimente online!

Carvão , 28 bytes

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

Experimente online! Link é a versão detalhada do código. Explicação:

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

Experimente online!

Programa autônomo, entrada via linha de comando.

Loop o número de permutações possíveis da sequência de entrada com base no número de v's. Enquanto conta em binário, substitua cada binário 1por a ^e cada binário 0por a vna sequência de entrada.