Code Golf Asked by Isaac C on January 2, 2022

You’re a criminal tasked with stealing some secret plans from the new tech startup Dejavu. You sneak in over the back wall, but find a door that requires a pin to open it. You recognize the make of the lock and know that it takes a 5 digit pin using all numbers from 0 to 4. After each digit entered, the lock checks the last 5 digits entered and opens if the code is correct. You have to get past this lock, and fast.

A permutation is all possible combinations of a certain set of digits. for example, all the permutations of the digits 0, 1, 2 are:

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

If we concatenate all these permutations together, we get a superpermutation:

012021102120201210

this superpermutation contains all the permutations of 0, 1, 2, but it’s possible to make one shorter than this. I’m going to skip a bit here, but the shortest superpermutation of these digits is:

012010210

For our intents and purposes, this is essentially the shortest string of digits that contains all possible permutations of those digits, i.e. a superpermutation.

Your task is a bit harder than the superpermutation example as shown above, because you have two more digits to worry about. – If you haven’t read about superpermutations, or my example above was a bit unclear, I highly suggest you read this great article by Patrick Honner on the subject (this challenge was quite heavily inspired by his article, so kudos to him): https://www.quantamagazine.org/unscrambling-the-hidden-secrets-of-superpermutations-20190116/. Your goal is to write the shortest program possible that generates a superpermutation of the digits 0 to 4.

Your program does not take any input of any sort, and produce a superpermutation of the digits from 0 to 4. This resulting superpermutation must be printed to the console or visibly displayed to the user to the extent provided by your language of choice. This doesn’t have to be the shortest permutation possible, it just has to be a valid superpermutation. Because of this, the goal is to write the shortest program with the shortest superpermutation, so you should calculate your score like so:

**file size (bytes) * generated superpermutation length (digits)**

for example, if I had a 40 byte program, and my superpermutation is 153 digits long, my score will be:

**40 * 153 = 6120**

as always, the goal is to get this score as low as possible.

Here is how you should post your answer:

## Language | Score

link to code in working environment (if possible)

`code snippet`

code explanation, etc.

This is one of my first questions on this site. So please tell me if I’m missing anything or a section of my challenge is unclear. Thank you, and have fun golfing!

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

Answered by ZaMoC on January 2, 2022

```
5e!72>
```

Online demo, validation (outputs the index at which each permutation of `0..4`

can be found; it needs to flatten the output because the original program gives suitable output to stdout but what it places on the stack is not directly usable).

Approach stolen from Sanchises, although the permutation order of CJam is different, giving a different substring.

```
0a4{)W@+W+1$)ewa*W-}/
```

This uses a simple recursive construction.

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

Answered by Peter Taylor on January 2, 2022

Answered by Sanchises on January 2, 2022

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

Try it online! Link is to verbose version of code. Explanation: Like @TFeld, I just print half of a superpermutation and mirror it. I calculated the superpermutation using the following code:

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

This translates to a 45-byte program in Charcoal so would have scored 6885.

Answered by Neil on January 2, 2022

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

So, it turns out, naively generating *all* the permutations and then truncating to the shortest substring that is still a valid superpermutation is shorter than generating the shortest superpermutation. Sadly, this time the score is not a palindrome.

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

Entry updated for a few things

`a++`

is not implemented for symbolic numbers.`contains()`

is not implemented in Octave. Replaced with`any(regexp())`

.- In the online link, I manually entered an
`a`

very close to the 153-length superpermutation. This allows for the solution to be verified.

Answered by Sanchises on January 2, 2022

```
4o ¬á Ë+4+D
```

-1 byte thanks to @ Shaggy!

Port of Anders Kaseorg's Pyth answer.

Answered by dana on January 2, 2022

With this scoring system, there's little room for something between *'hardcode the optimal supermutation'* and *'just use a short built-in to concatenate all permutations'*, at least in non-esolangs.

Here's an attempt anyway.

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

It generates a string of 325 bytes:

```
012340124301324013420142301432021340214302314023410241302431031240314203214032410341203421
041230413204213042310431204321102341024310324103421042310432201342014320314203412041320431
210342104330124301423021430241304123042131024310423201432041321044012340132402134023140312
4032141023410324201342031421034301243021431024320143210
```

Answered by Arnauld on January 2, 2022

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

Too slow to see anything, but if you change `4`

by `2`

you can test it: Try it online!

This finds the shortest superpermutation as such:

```
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
∧
```

Answered by Fatalize on January 2, 2022

```
ž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"
```

```
s+R+4d.p4
```

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

Answered by Anders Kaseorg on January 2, 2022

Answered by Arnauld on January 2, 2022

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

Finds the first number that contains all permutations of the digits 0 to 4. This will take a *long* time to execute, but you can test it with the first two permutations `0`

and `0,1`

Answered by Jo King on January 2, 2022

```
3ÝœJε4yJ}J
```

Port of *@AndersKaseorg*'s Pyth answer, so make sure to upvote him!

**Explanation:**

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

Answered by Kevin Cruijssen on January 2, 2022

7 Asked on October 27, 2021 by don-thousand

1 Asked on October 27, 2021

32 Asked on October 27, 2021

11 Asked on October 27, 2021 by somnium

2 Asked on October 27, 2021 by superjedi224

1 Asked on October 27, 2021

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP