Któregoś dnia nasz zespół poszedł do pokoju ewakuacyjnego. Jedna z zagadek obejmowała tablicę sześciu mechanicznych przełączników, w której trzeba było znaleźć odpowiednią kombinację włączania i wyłączania, aby odblokować pudełko, mniej więcej tak:

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

Jako programiści postanowiliśmy, że bardziej efektywne będzie wypróbowanie każdej z 2 ^ 6 = 64 kombinacji niż rozwiązanie zagadki. Przydzieliliśmy więc jakiegoś biednego faceta do zliczenia binarnego:

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

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

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

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

i tak dalej.

Wyzwanie
Napisz program, który, biorąc pod uwagę wszystkie przełączniki w pozycji wyłączonej jako ciąg sformatowany jak powyżej, generuje wszystkie kombinacje włączania i wyłączania w dowolnej kolejności.

Możesz napisać pełny program lub funkcję. W ten sposób twój program może albo pobierać dane wejściowe przez stdin, plik, albo jako pojedynczy ciąg znaków i zwracać lub drukować dane wyjściowe. Jeśli zostanie zwrócone, dane wyjściowe mogą znajdować się w liście / tablicy / itp. zamiast jednego ciągu. Jeśli wynik jest pojedynczym ciągiem, tablice powinny być oddzielone znakami nowej linii (dozwolone są znaki nowej linii).

Ciągi wejściowe będą pasować do wyrażenia regularnego r'((-v)+-)(\n(-v)+-)*'i będą reprezentować jedną płytkę ze wszystkimi wyłącznikami. Oznacza to brak zerowej wielkości liter, a przełączniki są wyrównane do lewej. Każdy wiersz może nie mieć takiej samej liczby przełączników.

Każda płytka wyjściowa powinna mieć dokładnie taki sam format jak wejście, z tym wyjątkiem, że v można w razie potrzeby zastąpić ^. Tablice wyjściowe można oddzielić dowolną liczbą nowych linii.

Ponieważ środowisko wykonawcze ma naturalnie wartość O (2 ^ n) pod względem liczby przełączników, kod nie będzie testowany na więcej niż 10 przełącznikach w dowolnym układzie.

To jest golf golfowy, więc wygrywa najkrótszy kod w liczbie bajtów.

Przykładowe wejścia i wyjścia

Wkład:

-v-

Możliwe wyjście:

-v-
-^-

Wkład:

-v-
-v-

Możliwe wyjście:

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

-v-
-^-


-v-
-v-

Ponieważ sprawdzanie odpowiedzi w przypadku większej liczby przełączników jest niezwykle uciążliwe, oto skrypt w języku Python jako narzędzie do sprawdzania czystości. (Dołączyłem obecnie skomentowany fragment kodu, aby wygenerować oczekiwane dane wyjściowe z danego pliku wejściowego na wypadek, gdybyś chciał więcej przypadków testowych.) Niestety, jest nieco mniej elastyczny pod względem danych wejściowych i wyjściowych niż specyfikacja; umieść ciąg wejściowy w pliku o nazwie „wejście”, a wyjście oddzielone znakiem nowej linii (przepraszam, brak formatowania listy) w pliku o nazwie „wyjście” w tym samym katalogu i uruchom python3 sanitycheck.py.

Haskell , 25 24 23 17 bajtów

mapM$min"^v".pure

Wypróbuj online!

-1 bajt dzięki @ H.PWiz

-1 bajt dzięki @nimi

Zwraca listę ciągów. TIO ma 2 dodatkowe bajty dla deklaracji funkcji - widziałem, jak inni ludzie ją wyłączają, gdy piszą funkcję bez punktów, więc robię to samo, chyba że powiedziano inaczej.

Poprzednia odpowiedź (25 bajtów)

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

Wyjaśnienia dotyczą poprzedniej odpowiedzi, która działa prawie w ten sam sposób, z tą różnicą, że wstawiłem definicję g. Sposób, w jaki gdziała teraz jest za pomocą porównania leksykalnego zastąpił ^vza vi zachować wszystko inne tak samo.

Co ciekawe, działa to w przypadku dowolnych tablic rozdzielczych:

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

Wyjaśnienie (krótkie)

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

Objaśnienie (długie)

mapMjest dość przerażającą funkcją dla tych, którzy nie znają Haskella. Ale nie jest trudno zrozumieć w tym kontekście. Ustawiając go na Strings (które w Haskell są listami postaci), wyspecjalizowałem się w jego definicji list. Więc w tym kontekście jego podpis typu to

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

W rzeczywistości jest jeszcze bardziej wyspecjalizowany w moim użyciu - ai boba Char- i możemy zobaczyć podpis typu jako

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

Szybko spójrzmy na to, co grobi, zanim wyjaśnimy, jak to mapMdziała.

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

gużywa dopasowania wzorca do konwersji ciągu Char 'v'na ciąg "v^"; wszystko inne zostaje przekonwertowane na ciąg singletonu (pamiętaj, że ciągi to tylko listy Chars, więc możemy umieścić xlistę singletonów). Testując REPL, stwierdzamy, że tak jest

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

Zauważ, że gjest to odpowiedni typ argumentu mapM(nic dziwnego!).

Zbadamy, jak to mapMdziała, podając go gi argument

"-v-\n-v-"

jako dane wejściowe.

mapMpierwsze mapy gnad String, a ponieważ gkonwertuje Chars na Strings, daje nam to listęStrings

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

Chociaż jest to prawidłowy typ wyjściowy, mapMrobi nieco więcej. Możesz myśleć o tym jako o utworzeniu wszystkich Stringliter, które możesz stworzyć z tej listy, jeśli będziesz musiał wybrać po jednym znaku z każdej z nich String(w kolejności).

Tak więc dla pierwszego elementu nie masz innego wyboru niż wybranie Char '-'. Dla drugiego elementu, można wybrać pomiędzy 'v'i '^'tak dalej i tak dalej.

Jest to mniej więcej odpowiednik tego kodu python:

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

Tyle, że ponieważ Haskell rozdziela Chars i Strings, kiedy umieszcza Chars na liście, nie potrzebuje joinich.

Tak więc końcowy wynik to

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

zgodnie z życzeniem.

Perl 6 , 32 bajty

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

Wypróbuj online!

• .comb dzieli ciąg na znaki.
• ».&{...} odwzorowuje znaki zgodnie z funkcją między nawiasami klamrowymi.
• $_, ('^' if /v/)tworzy listę alternatyw dla każdego znaku. Tylko vma zastępcę: ^.
• [X~]zmniejsza tę listę za pomocą operatora krzyżowego łączenia produktów X~.

Galaretka , 7 bajtów

«Ƭ€”^Œp

Wypróbuj online!

Dane wyjściowe to lista ciągów galaretki.

Wyjaśnienie:

«Ƭ€”^Œ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 bajtów

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

Wypróbuj online!

Moje pierwsze zgłoszenie!

Zwykle golfiści Perl 5 przesyłają programy zamiast funkcji, aby zaoszczędzić od konieczności dołączania sub{}co najmniej. Ale trzeba dodać say, say␠, say forlub say for␠w zamian.

Wybierając podejście podrzędne, mogłem skrócić

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

do

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

Wyjaśnienie jest dość proste. Perl 5 ma wbudowany globoperator, który akceptuje wzór globu podobny do powłoki, którego można użyć do wygenerowania list nazw plików (np. foo*.txt) Lub listy ciągów (np {a,b,c}.). Problem polega na tym, że nowa linia musi być zmieniona, co zrobiłem za pomocą quotemeta(as \Q).

K (ngn / k) , 27 25 bajtów

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

Wypróbuj online!

"^"/"v"\wymienić "v"z"^"

x,' zip z oryginalnymi znakami

(,/,/:\:)/ produkt kartezjański zakończony

? uniq

APL (Dyalog Classic) , 21 17 15 bajtów

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

Wypróbuj online!

podobne do mojego rozwiązania k

zwraca n-wymiarową tablicę ciągów (n = liczba przełączników)

w łatwiejszej do wyjaśnienia formie: ⊃(∘.,⌿ ⊢ ∪¨ 'v'⎕r'^')

'v'⎕r'^'zamień vs na ^s

⊢ ∪¨... związki z każdą z oryginalnych postaci. jest to wektor ciągów o długości 1 lub 2

∘.,⌿ redukcja produktu kartezjańskiego

⊃ ujawniać

aby przejść do wersji w pełni golfowej, kierujemy się wzorem f⌿ A g¨ B-> A f.g B:

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

jako efekt uboczny nawiasy nie są już potrzebne

J , 42 bajty

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

Wypróbuj online!

wyjaśnienie

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

Niech weźmie

-v-
-v-

jako nasz przykładowy wkład.

• ('v^' {~ 2 #:@i.@^ 1 #. e.&'v')tworzy wszystkie możliwe kombinacje samych przełączników, ignorując format wejściowy. w naszym przykładzie produkuje:

  vv
  v^
  ^v
  ^^
  

  • 1 #. e.&'v'zlicza liczby vs na wejściu.
  • 2 #:@i.@^podnosi 2 do tej potęgi, produkuje liczby całkowite od 0 do tej liczby i.i konwertuje je na binarne#:
  • 'v^' {~zmiany cyfr binarnych na vi^
• ]`('v' I.@e.~ [)`[}"1zmienia oryginalny wejściowy, tworząc jedną kopię dla każdego rzędu w wyniku opisanego w poprzednim etapie (czyli wszystkie możliwe v/ ^combo). W każdej kopii voryginalne wejście jest zastępowane jedną możliwą sekwencją v/ ^.

Java, 202 197 189 191 bajtów

Tak, jest to dość szczegółowy język, ale to, co uważam za klasyczne golfa:

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

Myślałem, że „prosty” sposób radzenia sobie z podziałów wierszy, które są niezbędne do osiągnięcia celu prawidłowego układu było rzeczywiście ponownie użyć oryginalnego tablicę znaków wejściowych, a tylko wypełnić go z 'v'S i '^'S w odpowiednich pozycjach.

Aktualizacje:

Okazało się, że nie przechowywania stanowisk pozwala na wodowania inti deklaracji zmiennych array (kosztem sprawdzanie każdej pozycji tablicy, czy zawiera on vlub ^w locie), oszczędzając 5 bajtów.

Kolejne 8 bajtów zaoszczędzonych dzięki (1<<numberOfSwitches)bardziej zwartemu obliczeniu górnej granicy .

Zgodnie z regułą wymienioną w komentarzu należy policzyć deklarację funkcji, więc teraz jest to lambda ...

J , 41 40 24 bajtów

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

Wypróbuj online!

Python 2 , 87 bajtów

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

Wypróbuj online!

Podejście inne niż wyrażenia regularne.

C (gcc) , 75 74 70 bajtów

-5 bajtów dzięki @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);}

Wypróbuj online!

wymaga zapisywania spunktów pamięci

Python 3.8 (wersja wstępna) , 129 117 116 110 106 bajtów

-10 bajtów dzięki @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))}

Wypróbuj online!

C (gcc) , 102 bajty

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

Wypróbuj online!

K4 , 44 bajty

Rozwiązanie:

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

Przykłady:

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

Wyjaśnienie:

Wymiana w miejscu "^". Określić liczbę kombinacji przełączników (np. 2 ^ n), policzyć binarnie, wymienić przełączniki ...

-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 bajtów

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

Wypróbuj online!

Funkcja zwracająca wektor tablic rozdzielonych znakiem nowej linii

JavaScript, 88 bajtów

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

Wypróbuj online!

Retina 0.8.2 , 29 bajtów

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

Wypróbuj online! Wyjaśnienie:

T`¶v`;#

Zmień znaki nowej linii na ;s, a vs na #markery.

+%1`#

Wymień je #pojedynczo od lewej do prawej.

v$'¶$`^

Zmień każdą linię na dwie linie, jedną z #zastąpioną przez a v, jedną z zastąpioną przez a ^.

%`;|$
¶

Zmień ;s z powrotem na nowe linie i rozdziel wyniki od siebie.

Perl 5 -0 , 51 bajtów

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

Wypróbuj online!

JavaScript (Node.js) , 80 73 68 bajtów

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

Wypróbuj online!

Python 3 - konstrukcja, 203 bajty

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

Wypróbuj online!

Pierwsza próba, niezbyt mała, ale działa. W Pythonie nie ma eleganckiej zamiany napisów ...

Pierwsza pętla buduje odwzorowanie linii na indeksy bitów, tj. Dla każdej linii przechowywany jest indeks pierwszego bitu w liczniku bitów. Służy do indeksowania licznika bitów w następnej pętli.

Druga pętla uruchamia licznik binarny, wyodrębnia bity dla każdej linii i iteracji i łączy je. Po połączeniu wszystkich elementów jest on ponownie tłumaczony do formatu mapy przełączników, z wykorzystaniem zamiany napisów.

Sądzę, że istnieje bardziej elegancki sposób, poprzez ponowne użycie ciągu wejściowego zamiast jego przebudowywania w kółko.

Edycja: zainspirowana odpowiedzią Python 3.8 , tutaj jest znacznie krótsza wersja zastępująca

Python 3 - zamień, 123 bajty

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

Wypróbuj online!

Rubinowy , 64 bajty

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

W Ruby i[j]zwraca jth izaczynający się od najmniej znaczącego bitu, czyli równoważny (i>>j)&1.

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

Wypróbuj online!

Węgiel drzewny , 28 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

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

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

Wypróbuj online!

Samodzielny program, wprowadzany z wiersza poleceń.

Zapętlić liczbę możliwych permutacji ciągu wejściowego na podstawie liczby v. Podczas liczenia w formacie binarnym zamień każdy plik binarny na „ 1a”, ^a każdy plik binarny na „ 0a” vw ciągu wejściowym.