Введение

Вы преступник, которому поручено украсть секретные планы нового технологического стартапа Dejavu. Вы пробираетесь через заднюю стену, но находите дверь, для которой требуется булавка, чтобы открыть ее. Вы узнаете марку замка и знаете, что для этого требуется 5-значный пин-код, используя все цифры от 0 до 4. После каждой введенной цифры замок проверяет последние 5 введенных цифр и открывает, если код правильный. Вы должны пройти этот замок и быстро.

Суперперестановки в двух словах

Перестановка - это все возможные комбинации определенного набора цифр. например, все перестановки цифр 0, 1, 2:

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

Если мы объединим все эти перестановки вместе, мы получим суперперестановку:

012021102120201210

эта суперперестановка содержит все перестановки 0, 1, 2, но можно сделать одну короче этой. Я собираюсь немного пропустить здесь, но самая короткая супермутация из этих цифр:

012010210

Для наших намерений и целей, это, по сути, самая короткая строка цифр, которая содержит все возможные перестановки этих цифр, т.е. суперпермутация.

задача

Ваша задача немного сложнее, чем в примере с суперперестановкой, как показано выше, потому что у вас есть еще две цифры для беспокойства. - Если вы не читали о суперперестановках, или мой приведенный выше пример немного неясен, я настоятельно рекомендую вам прочитать эту замечательную статью Патрика Хоннера на эту тему (этот вызов был в значительной степени вдохновлен его статьей, так что слава ему): https://www.quantamagazine.org/unscrabing-the-hidden-secrets-of-superpermutations-20190116/ . Ваша цель - написать максимально короткую программу, которая генерирует суперперестановку цифр от 0 до 4.

счет

Ваша программа не принимает никаких вводных данных и выдает суперперестановку цифр от 0 до 4. Эта результирующая суперперестановка должна быть распечатана на консоли или визуально отображена для пользователя в той степени, в какой это обеспечивает выбранный вами язык. Это не должно быть самой короткой из возможных перестановок, это просто должна быть действительная суперпермутация. По этой причине цель состоит в том, чтобы написать самую короткую программу с самой короткой супермутацией, поэтому вы должны рассчитать свой результат следующим образом:

размер файла (в байтах) * генерируемая длина суперперестановки (цифры)

например, если у меня была 40-байтовая программа, и моя суперперестановка имеет длину 153 цифры, мой результат будет:

40 * 153 = 6120

как всегда, цель состоит в том, чтобы получить этот счет как можно ниже.

шаблон

Вот как вы должны опубликовать свой ответ:

Язык | Гол

ссылка на код в рабочей среде (если возможно)

code snippet

объяснение кода и т. д.

Finalities

Это один из моих первых вопросов на этом сайте. Поэтому, пожалуйста, скажите мне, если я что-то упустил, или раздел моей задачи неясен. Спасибо, и получайте удовольствие от игры в гольф!

05AB1E , оценка = 1673 (7 байт · 239)

žBœ∊{3ý

Попробуйте онлайн!

Как это работает

ž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 , оценка = 1944 (9 байт · 216)

s+R+4d.p4

Попробуйте онлайн!

Как это работает

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

Брахилог , оценка = 2907 (19 байт × 153)

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

Слишком медленно, чтобы что-то увидеть, но если вы измените 4, 2вы можете проверить это: попробуйте онлайн!

Это находит самую короткую суперперестановку как таковую:

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 байта)

С этой системой подсчета очков мало места для чего-то между «жестким кодом оптимальной перестановки» и «просто использовать короткую встроенную функцию для объединения всех перестановок» , по крайней мере, в несолангах.

Вот попытка в любом случае.

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

Попробуйте онлайн!

Он генерирует строку из 325 байтов:

012340124301324013420142301432021340214302314023410241302431031240314203214032410341203421
041230413204213042310431204321102341024310324103421042310432201342014320314203412041320431
210342104330124301423021430241304123042131024310423201432041321044012340132402134023140312
4032141023410324201342031421034301243021431024320143210

Python 2 , оценка: 24327 15147 12852 12628 (154 * 82 байта)

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

Попробуйте онлайн!

Также:

Python 2 , 12628 (154 * 82 байта)

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

Попробуйте онлайн!

05AB1E , оценка: 5355 2160 (216 * 10 байт )

3ÝœJε4yJ}J

Порт @AndersKaseorg 's Pyth answer , так что обязательно проголосуйте за него!

Попробуйте онлайн.

Объяснение:

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)

Октава , 27 х 442 = 11934

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

Попробуйте онлайн!

Таким образом, получается, наивно генерируя все перестановки, а затем обрезая до самой короткой подстроки, которая все еще является допустимой суперпермутацией, короче, чем генерируя самую короткую суперпермутацию. К сожалению, на этот раз оценка не является палиндромом.

Октава , 97 х 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

Попробуйте онлайн!

Запись обновлена ​​для нескольких вещей

• a++ не реализовано для символических чисел.
• contains()не реализован в октаве. Заменено на any(regexp()).
• В онлайн-ссылке я вручную ввел aочень близкую к суперспеременности 153 длины. Это позволяет проверить решение.

CJam (6 * 240 = 1440)

5e!72>

Демонстрация онлайн , проверка (выводит индекс, по которому каждая перестановка0..4 может быть найдена ; ей нужно сгладить вывод, потому что исходная программа дает подходящий вывод для stdout, но то, что она помещает в стек, не может использоваться напрямую).

Подход, украденный из Sanchises , хотя порядок перестановок CJam отличается, давая другую подстроку.

CJam (22 * 207 = 4554)

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

Демо онлайн , валидация .

рассечение

Это использует простую рекурсивную конструкцию.

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
}/

Желе , 3000 (600 * 5 байт)

5ḶŒ!F

Попробуйте онлайн!

Древесный уголь , 29 байтов, длина вывода 153, оценка 4437

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

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение: Как и @TFeld, я просто печатаю половину суперперестановки и отражаю ее. Я вычислил суперперестановку, используя следующий код:

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

Это переводит 45-байтовую программу в Charcoal, поэтому набрал бы 6885.

MATL , 16 х 442 = 7072

4Y25:Y@!)K442&:)

Попробуйте онлайн!

MATL порт моего октавного ответа. -442 благодаря Луису Мендо

Japt -P, 2376 (11 x 216)

4o ¬á Ë+4+D

Попытайся!

-1 байт благодаря @ Shaggy!

Порт Андерса Касегорга Pyth ответ .

Perl 6 , 7191 (153 * 47 байт)

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

Попробуйте онлайн!

Находит первое число, которое содержит все перестановки цифр от 0 до 4. Это займет много времени для выполнения, но вы можете проверить его с помощью первых двух перестановок 0и0,1

Wolfram Language (Mathematica) , 153 * 95 байт, 14535

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

Попробуйте онлайн!