Wprowadzenie

Twoim zadaniem jest kradzież tajnych planów od nowego startupu technologicznego Dejavu. Przekradasz się przez tylną ścianę, ale znajdujesz drzwi, które do otwarcia wymagają szpilki. Rozpoznajesz markę zamka i wiesz, że wymaga on 5-cyfrowego kodu PIN, używając wszystkich cyfr od 0 do 4. Po każdej wprowadzonej cyfrze zamek sprawdza ostatnie 5 wprowadzonych cyfr i otwiera się, jeśli kod jest poprawny. Musisz szybko ominąć tę blokadę.

Superpermutacje w pigułce

Permutacja to wszystkie możliwe kombinacje określonego zestawu cyfr. na przykład wszystkie permutacje cyfr 0, 1, 2 to:

012, 021, 102, 120, 201 i 210.

Jeśli połączymy wszystkie te permutacje razem, otrzymamy superpermutację:

012021102120201210

ta superpermutacja zawiera wszystkie permutacje 0, 1, 2, ale możliwe jest, aby jedna była krótsza od tej. Pominę tutaj trochę, ale najkrótsza superpermutacja tych cyfr to:

012010210

Dla naszych celów i celów jest to zasadniczo najkrótszy ciąg cyfr, który zawiera wszystkie możliwe kombinacje tych cyfr, tj. Superpermutację.

Zadanie

Twoje zadanie jest nieco trudniejsze niż przykład superpermutacji, jak pokazano powyżej, ponieważ masz jeszcze dwie cyfry do zmartwienia. - Jeśli nie czytałeś o superpermutacjach lub mój powyższy przykład był nieco niejasny, gorąco polecam przeczytanie tego wspaniałego artykułu Patricka Honnera na ten temat (wyzwanie to było dość mocno zainspirowane jego artykułem, więc chwała mu): https://www.quantamagazine.org/unscrambling-the-hidden-secrets-of-superpermutations-20190116/ . Twoim celem jest napisanie możliwie najkrótszego programu, który generuje superpermutację cyfr od 0 do 4.

Punktacja

Twój program nie pobiera żadnych danych wejściowych i generuje superpermutację cyfr od 0 do 4. Wynikowa superpermutacja musi zostać wydrukowana na konsoli lub widocznie wyświetlona użytkownikowi w zakresie podanym przez wybrany język. To nie musi być najkrótsza możliwa permutacja, musi to być tylko prawidłowa superpermutacja. Z tego powodu celem jest napisanie najkrótszego programu z najkrótszą superpermutacją, więc powinieneś obliczyć swój wynik w następujący sposób:

rozmiar pliku (bajty) * wygenerowana długość superpermutacji (cyfry)

na przykład, jeśli miałbym program 40-bajtowy, a moja superpermutacja ma długość 153 cyfr, mój wynik wyniesie:

40 * 153 = 6120

jak zawsze, celem jest uzyskanie jak najniższego wyniku.

Szablon

Oto jak powinieneś opublikować swoją odpowiedź:

Język | Wynik

link do kodu w środowisku pracy (jeśli to możliwe)

code snippet

objaśnienie kodu itp.

Finały

To jedno z moich pierwszych pytań na tej stronie. Więc proszę powiedz mi, czy coś mi brakuje, lub część mojego wyzwania jest niejasna. Dziękuję i baw się dobrze grając w golfa!

05AB1E , wynik = 1673 (7 bajtów · 239)

žBœ∊{3ý

Wypróbuj online!

Jak to działa

žB          push 1024
  œ         permutations: ["1024", "1042", …, "4201"]
   ∊        vertically mirror: ["1024", "1042", …, "4201", "4201", …, "1042", "1024"]
    {       sort: ["0124", "0124", "0142", "0142", …, "4210", "4210"]
     3      push 3
      ý     join: "01243012430142301423…3421034210"

Pyth , wynik = 1944 (9 bajtów · 216)

s+R+4d.p4

Wypróbuj online!

Jak to działa

 +R   .p4   append to each permutation d of [0, 1, 2, 3]:
   +4d        [4] + d
s           concatenate

Brachylog , wynik = 2907 (19 bajtów × 153)

4⟦pᶠP∧~l.g;Pz{sᵈ}ᵐ∧

Zbyt powolny, aby cokolwiek zobaczyć, ale po zmianie 4przez 2można go przetestować: Spróbuj online!

Znajduje najkrótszą superpermutację jako taką:

4⟦                   The range [0,1,2,3,4]
  pᶠP                P is the list of all permutations of this range
     ∧
      ~l.            Try increasing lengths for the output
         g;Pz        Zip the output with P
             {sᵈ}ᵐ   For each permutation, it must be a substring of the output
                  ∧

JavaScript (ES6), 26975 (325 * 83 bajtów)

Dzięki temu systemowi punktacji nie ma miejsca na coś pomiędzy „kodowaniem optymalnym supermutacji na twardo” a „po prostu użyciem krótkiego wbudowanego do łączenia wszystkich permutacji” , przynajmniej w wersjach innych niż esolangi.

To i tak próba.

f=(a=[0,1,2,3,4],p=r='')=>a.map((v,i)=>f(a.filter(_=>i--),p+v))|~r.search(p)?r:r+=p

Wypróbuj online!

Generuje ciąg 325 bajtów:

012340124301324013420142301432021340214302314023410241302431031240314203214032410341203421
041230413204213042310431204321102341024310324103421042310432201342014320314203412041320431
210342104330124301423021430241304123042131024310423201432041321044012340132402134023140312
4032141023410324201342031421034301243021431024320143210

Python 2 , Wynik: 24327 15147 12852 12628 (154 * 82 bajtów)

S=str(int('OH97GKT83A0GJRVO309F4SGSRWD0S2T292S1JBPVKJ6CRUY8O',36))
print S+S[::-1]

Wypróbuj online!

Również:

Python 2 , 12628 (154 * 82 bajtów)

S=oct(int('FS02C3XQJX14OTVMGM70CGCPWU41MNJZ0CO37ZMU0A0Y',36))[:-1]
print S+S[::-1]

Wypróbuj online!

05AB1E , wynik: 5355 2160 (216 * 10 bajtów )

3ÝœJε4yJ}J

Port odpowiedzi Pyth @AndersKaseorg , więc upewnij się, że go głosujesz!

Wypróbuj online.

Wyjaśnienie:

3Ý           # Push a list in the range [0,3]: [0,1,2,3]
  œ          # Get all possible permutations of this list
   J         # Join each inner list together to a single string
    ε        # Map each string `y` to:
             #  (Push string `y` implicitly)
     4       #  Push 4
      y      #  Push string `y` again
       J     #  Join all three together
        }J   # After the map: Join all strings together to a single string
             # (and output it implicitly as result)

Oktawa , 27 x 442 = 11934

'01234'(perms(1:5)'(4:445))

Wypróbuj online!

Okazuje się, że naiwnie generuje wszystko permutacji, a następnie obcinanie do najkrótszego podłańcucha, który wciąż jest prawidłową superpermutacją, jest krótsze niż generowanie najkrótszej superpermutacji. Niestety, tym razem wynik nie jest palindromem.

Oktawa , 97 x 153 = 14841

a=sym(9);while i<120
i=0;a+=1;q='01234';for t=q(perms(1:5))'
i+=any(regexp(char(a),t'));end
end
a

Wypróbuj online!

Wpis zaktualizowano o kilka rzeczy

• a++ nie jest zaimplementowany dla liczb symbolicznych.
• contains()nie jest zaimplementowany w Octave. Zamieniono naany(regexp()) .
• W łączu online ręcznie awpisałem bardzo zbliżone do superpermutacji o długości 153. Umożliwia to weryfikację rozwiązania.

CJam (6 * 240 = 1440)

5e!72>

Demo online , sprawdzanie poprawności (wyświetla indeks, przy którym 0..4można znaleźć każdą permutację ; musi spłaszczyć dane wyjściowe, ponieważ oryginalny program podaje odpowiednie wyjście na standardowe wyjście, ale to, co umieszcza na stosie, nie jest bezpośrednio użyteczne).

Podejście skradzione z Sanchises , chociaż kolejność permutacji CJam jest inna, co daje inne podciągi.

CJam (22 * 207 = 4554)

0a4{)W@+W+1$)ew\a*W-}/

Demo online , sprawdzanie poprawności .

Sekcja

Wykorzystuje prostą konstrukcję rekurencyjną.

0a       e# Start with a superpermutation of one element, [0]
4{       e# for x = 0 to 3:
  )      e#   increment it: n = x+1
  W@+W+  e#   wrap the smaller superpermutation in [-1 ... -1]
  1$)ew  e#   split into chunks of length n+1
  \a*    e#   insert an n between each chunk
  W-     e#   remove the -1s from the ends
}/

Galaretka , 3000 (600 * 5 bajtów)

5ḶŒ!F

Wypróbuj online!

Węgiel drzewny , 29 bajtów, długość wyjściowa 153, wynik 4437

”)⊞⧴�r3⁼Ｈ⁴↓¦σ✳ＬïpＷＳ [Ｔ↑ZωÞ”‖Ｏ

Wypróbuj online!Link jest do pełnej wersji kodu. Objaśnienie: Podobnie jak @TFeld, po prostu drukuję połowę superpermutacji i odbijam ją. Obliczyłem superpermutację za pomocą następującego kodu:

Push(u, w);
for (u) {
    Assign(Plus(Plus(i, Length(i)), i), h);
    Assign(Ternary(i, Join(Split(w, i), h), h), w);
    Assign(Incremented(Length(i)), z);
    if (Less(z, 5)) for (z) Push(u, Slice(h, k, Plus(k, z));
}
Print(w);

To przekłada się na 45-bajtowy program w Charcoal, więc zdobyłby 6885.

MATL , 16 x 442 = 7072

4Y25:Y@!)K442&:)

Wypróbuj online!

Port MATL mojej odpowiedzi Octave. -442 dzięki Luisowi Mendo

Japt-P, 2376 (11 x 216)

4o ¬á Ë+4+D

Spróbuj!

-1 bajt dzięki @ Shaggy!

Port Anders Kaseorg znajduje Pyth odpowiedź .

Perl 6 , 7191 (153 * 47 bajtów)

say first *.comb(permutations(5).all.join),0..*

Wypróbuj online!

Znajduje pierwszą liczbę, która zawiera wszystkie permutacje cyfr od 0 do 4. Wykonanie tej operacji zajmie dużo czasu, ale możesz ją przetestować za pomocą dwóch pierwszych permutacji 0i0,1

Wolfram Language (Mathematica) , 153 * 95 bajtów, 14535

Nest[Flatten[Join[#,{Max@#+1},#]&/@Partition[#,Max@#+1,1]]//.{b__,a__,a__,c__}:>{b,a,c}&,{0},4]

Wypróbuj online!