title: Mahjong Checker

text:
# Question
Title: Mahjong Checker
Mahjong is a tabletop game played using tiles. It features three "number" suits (pins, sous, mans, represented as `p`, `s` and `m`) from 1 to 9, and one "honor" suit `z` of seven distinct tiles. Note that contrary to western card games, tiles are not unique.

To complete a hand and win, the 13 tiles in your hand are combined with 1 newly drawn tile and must result in one of the following winning configurations:

* 4 sets and 1 pair, self-explanatory
* seven pairs, where all pairs are distinct (twice the same pair wouldn't qualify)
* kokushi musou: one of each of the 1 and 9 of each number suit, one of every seven honors, the remaining tile forming a pair (e.g. `19m19p19s11234567z`)

A pair is any of the two same tiles: `11m`, `33s`, `44p`, `55z`, etc.

A set consists of 3 tiles of the same suit. It can either be a run: 3 number tiles (p, s or m) in a connected run like `123s` or `234s`, but not `1m 2p 3s` or `234z`; or a triplet of any suit, not necessarily numbers, like `111z`, `222m`.

So honor tiles (non-numbers, represented by `z`) can only form pairs or triplets, but not runs. `567z` is not a set, `555z` is a valid set, `55z` is a valid pair.

A single tile can only be counted as part of one set or pair: there is no sharing or reusing.

Given a sorted hand of 13 tiles and one tile, check whether the 14 tiles make up a completed hand.

## Input & Output

* You are given a sequence of numbers and letters, a space, then a tile of a number and a letter
* Output `True`/`1` if the set is a match, else `False`/`0`

## Others:

* You are allowed to input the sequence and tile+letter as a list/array

## Test Cases:

Truthy

```
222888m444p2277z 7z
234m45789p45688s 6p
11m4477p8899s116z 6z
19m19p19s1234567z 6z
123345567789m3p 3p

```

Falsey

```
1122335778899m 1m
888m55s11222333z 4z
234m2233445566p 4p
19m139p19s123567z 4z
11m4477p8899s666z 6z

```

Credits to Unihedron for the puzzle!

## Scoring

This is code-golf, so shortest code wins!

# Answer
# JavaScript (Node.js), ~~248~~ ~~246~~ 245 bytes

```
s=>s.sort().every((t,i)=>t==s[i^1]&t!=s[n=12,i+2])|A(s)|[...new Set(s)].length>n
A=y=>y.some(t=>R(y,t,t,t)|t[n+=t>'2'&t<'9'&t[1]<A,1]<A&R(y,t,t[0]-1+t[1],t[0]-2+t[1]))|y[0]==y[1]&!y[2]
R=(s,p,q,r,z=0,k=s.filter(y=>y!=p||z++))=>p?z&&R(k,q,r):A(s)

```

Try it online!

Every answer is in js...

`f` is the main function, relying on `A` modifying `n` for non-1919191234567 check

`A` check if it's 3+3+3+3+2

`R` removes some triplet and go on `A`ing
> 5 votes

# Answer
# Javascript (SpiderMonkey), 807 bytes

```
[a,[b,c]]=readline(j=m=0).split` `
d=[...h='mpsz'].map(k=>!~(i=a.indexOf(k))?'':a.slice([j,j=i+1][0],i))
d[i=h.indexOf(c)]=[...d[i]].concat(b).sort().join``
if(~(''+d).search`(1+9+,){3}1+2+3+4+5+6+7`|d.every(k=>/^(?:(.)\1(?!\1))*$/.test(k)))print(1);else A:{a=/(.)(\1*)/g;e=d.pop();while(n=a.exec(e))if(!n[2]){print(0);break A}else if(n[2].length==1)if(m){print(0);break A}else m=1
f=l=>{if(!l.length)return;var[h,n,b]=l;if((a=n-h)>1)return 1;i=l.indexOf(+n+1);if(a==1)return!~i?1:f(l.slice(2,i)+l.slice(i+1));if(~i){c=l.slice(1,i)+l.slice(i+1,i=l.indexOf(+n+2))+l.slice(i+1);if(~i&&!f(c))return}return n-b||f(l.slice(3))};m=d.filter(k=>{if(!(c=k.length%3))return f(k);else if(c==2){r=/(.)\1/g;while(n=r.exec(k))if(!f(k.slice(0,n.index)+k.slice(r.lastIndex)))return m=1,0}return 1}).length?0:m
print(m?1:0)}

```

Try it online!

First js post!
> 3 votes

# Answer
# JavaScript, 348 bytes

```
a=>[[(P=f=>w=>f(w)&&1-w.some((n,i)=>n>1&!f(W=[...w],W[i]-=2))/2)(w=>w.some(n=>([p,q]=[q,(n-p-q)%3],1/q<0),p=q=0)),P(w=>w.some(n=>n%3)),],[w=>w.some(n=>n&-3)],[w=>w.some((n,i)=>i%8==1^n>0),w=>w.some((n,i)=>0<i&i<8^n>0)]].some(([i,I=i])=>i(n`m`)+i(n`p`)+i(n`s`)+I(n`z`)<1,n=t=>[...a.matchAll(`\\d(?=\\d*${t})`)].map(i=>s[i]++,s=Array(12).fill(0))&&s)

```

Passed all testcases. Though it may still be buggy. Comment any failed testcases, and I will try to fix them.

```
a=>[[
  // given count of each tiles in same suit
  // return 1 if it is not a valid hand
  // return 0.5 if it is a valid hand with a pair
  // return 0 if it is a valid hand without a pair
  (P=f=>w=>f(w)&&1-w.some((n,i)=>n>1&!f(W=[...w],W[i]-=2))/2)
  // for m, p, s
   (w=>w.some(n=>([p,q]=[q,(n-p-q)%3],1/q<0),p=q=0)),
  // for z
  P(w=>w.some(n=>n%3)),
],[
  // for 7 pairs rule
  w=>w.some(n=>n&-3)
],[
  // for 13 orphan rule
  w=>w.some((n,i)=>i%8==1^n>0),
  w=>w.some((n,i)=>0<i&i<8^n>0)
]].some(([i,I=i])=>i(n`m`)+i(n`p`)+i(n`s`)+I(n`z`)<1,
  // Parse `112233456666m` -> `[0, 2, 2, 2, 1, 1, 4, 0, 0, 0, 0, 0]`
  n=t=>[...a.matchAll(`\\d(?=\\d*${t})`)].map(i=>s[i]++,s=Array(12).fill(0))&&s
);

```
> 1 votes

---
Tags: code-golf, decision-problem, game
---


# Question
Title: What are you waiting for? (A mahjong solver)
*Idea thanks to @MartinBüttner from a discussion in chat*

Mahjong is a tile game that is immensely popular in Asia. It is typically played with four players, and the goal of the game is to be the first person to complete a valid hand using the tiles. For this challenge, we will consider a simplified version of the game — PPCG mahjong.

In PPCG mahjong, there are three suits – `m`, `p` and `s` – and the tiles are numbered from `1` to `9`. There are exactly four copies of each tile, and the tiles are denoted by its number followed by its suit (e.g. `3m`, `9s`).

A completed PPCG mahjong hand consists of four sets of three and a pair, for a total of 14 tiles.

A set of three can be either:

* Three of the same tile (e.g. `4s 4s 4s`, but not `4m 4p 4s`), or
* A sequence of three consecutive tiles in the same suit (e.g. `1s 2s 3s` or `6p 7p 8p` but not `3s 4m 5m` or `3p 5p 7p`). Sequences do not wrap (so `9m 1m 2m` is invalid).

A pair is simply two identical tiles (e.g. `5s 5s`).

## The challenge

Your program will receive a space-separated hand of 13 tiles, with each tile appearing no more than four times. You may write either a full program or a function which takes in a string.

Your task is to find all possible 14th tiles ("waits") which, when added to the hand, would form a completed PPCG mahjong hand. The outputted tiles should be space-separated, but can be in any order. Leading or trailing whitespace is allowed.

Your program should run in a reasonable amount of time, no longer than a minute.

## Examples

```
Input: 1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s
Output: 9s

Input: 1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p
Output:

Input: 1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s
Output: 1s

Input: 1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m
Output: 1m 2m 3m 4m 5m 6m 7m 8m 9m

Input: 1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s
Output: 1m 4m 6s 9s

```

In the first example, the `1m 4s 7p 3m` all form existing triplets, leaving the lone `9s` to form a pair.

In the second example, the `2s 3s` and `7p 8p` can only form sequences, and the remaining tiles can only form triplets. Hence no pair can be formed, and there is no output.

In the third example, the hand splits into `1m2m3m 2m3m4m 3m3m 1s1s 9s9s9s`. Normally this would be a wait for `3m 1s`, but as all four `3m` have been used, the only available wait is `1s`.

In the fourth example, all of the `m` tiles complete the hand. For example, for `1m`, one could have `1m1m1m 1m2m3m 4m5m6m 7m8m9m 9m9m` which is a completed hand.

Try to work out the rest of the fourth example and the fifth example :)

## Scoring

This is , so the solution in the fewest bytes wins. Standard loopholes apply.

# Answer
## Python, ~~312~~ 281 bytes

```
def W(S):H=lambda C,n=0,t=1:sum([m<C[0]and H([c-s for c in C][:l]+C[l:],n+1,u)for m,s,l,u in(2,3,1,t),(t,2,1,4),(4-5*all(C[:3]),1,3,t)])|H(C[1:],n,t)if C[2:]and max(C)<5else n>4;T=[i+s for s in"mps"for i in"12345678900"];return" ".join(t for t in T if("1"<t)*H(map((S+t).count,T)))

```

`W` takes a string as input and returns a string as output.

The small number of tiles (27) makes it fast enough to test if each of them completes the hand. The problem becomes to check if a hand is valid. The function uses a simple backtracking algorithm that considers all possible choices of sets and checks if any of them adds up to a complete hand.

Hands are represented as tile histograms, i.e. a list of tile counts (for all the tiles, not only the ones present in the hand.) This makes it easy to both check if we have a certain number of a certain tile, and if we have a sequence of adjacent tiles (padding between tiles of different suits prevent multi-suit sequences.)
> 4 votes

# Answer
# JavaScript (E6) 306

```
F=h=>(
  R=(a,p,n=1)=>(a=[...a]).splice(p,n)&&a,
  K=(t,d=3)=>
    !t[0]
    |t.some(
      (v,p)=>
        v==t[p+1]&v==t[p+d-1]&&
        K(R(t,p,d))
      ||
        ~((r=t.indexOf((x=-~v[0])+v[1]))|(s=t.indexOf(-~x+v[1])))&&
        K(R(R(R(t,s),r),p))
    ),
  o=[],
  [for(s of'mps')for(i of'123456789')h.replace(t=i+s,s,'g')[34]
  &&K([t,...h.split(' ')].sort(),2)&&o.push(t)
  ],o
)

```

**Explained**

```
F=hand=>(
  Remove=(a,p,n=1)=>                // function to remove 1 or more element from an array, returning a new shorter array
    ((a=[...a]).splice(p,n), a),    // using array.splice on a new created array

  Check=(ckHand, dim)=>  // recursive function to check hand.
                         // removing pairs (at iteration 0) or sequence of three, if at last the hand remain empty then success
                         // parameter dim is 2 or 3 indicating how many equal elements are to be removed
    !ckHand[0]           // check if empty (element 0 does not exist)
    |ckHand.some(        // else traverse all array checking what can be removed
      (value, position)=>
        value == ckHand[position + 1]
        & value == ckHand[position + dim-1] &&   // look for 3 (or 2) equal elements
        Check(Remove(ckHand, position, dim), 3)   // if found, then remove elements and check again
      ||
        ~((r = ckHand.indexOf((x=-~value[0]) + value[1]))     // value[0] is number, value[1] is suit
        |(s = ckHand.indexOf(-~x + value[1]))) &&              // look for an ascending sequence in following elements (the array is sorted)
        Check(Remove(Remove(Remove(ckHand, s), r), position),3) // if sequence found, remove elements and check again
    ),
  output=[], // start with an empty solution list
  [ // using array comprehension to implement a double loop
    for(s of'mps')        // loop for all suits
    for(i of'123456789')  // loop for all numbers
    (
       tile=i+s, // current tile
       (hand.replace(tile,' ','g').length > 34)      // if tile is present 4 times in hand, the replaced length is 38-4 == 34
       && (                                       // else proceed with check
         ckHand = hand.split(' '),
         ckHand.push(tile),    // in ckHand (as an array) the hand to be checked, that is base hand + current tile
         ckHand.sort(),        // sorting the array simplfy the checks
         Check(ckHand, 2)      // start checks looking for a pair
       )
       &&
         output.push(tile)   // if check ok, add tile to the solution list
    )
  ],
  output // last expression in list is the function return value
)

```

**Test** in FireFox/FireBug console

```
;["1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s", "1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p",
 "1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s", "1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m",
 "1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s"].forEach(s=>console.log(s+' => '+F(s)))

```

*Output*

```
1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s => 9s
1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p =>
1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s => 1s
1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m => 1m,2m,3m,4m,5m,6m,7m,8m,9m
1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s => 1m,4m,6s,9s

```
> 2 votes

# Answer
# JavaScript (Node.js), 241 bytes

```
s=>[...Array(i=27)].flatMap(_=>A([...s,k=--i%9+1+'mps'[i/9|0]])>/^(..)(.*\1){4}/.test(k+s)?k:[])
A=s=>s.some(t=>R(s,t,t,t)|t[1]<'z'&R(s,t,t[0]-1+t[1],t[0]-2+t[1]))|s[0]==s[1]&!s[2]
R=(s,p,q,r,z=0,k=s.filter(y=>y!=p||z++))=>p?z&&R(k,q,r):A(s)

```

Try it online!

Came from the more complex checker and made small changes
> 0 votes

---
Tags: code-golf, game
---


title: Print the Lost numbers

text:
# Question
Title: Print the Lost numbers
As a big fan of the Lost TV series, I always got intrigued by the sequence of numbers that repetitively appears on the episodes. These numbers are:

\\$ 4, 8, 15, 16, 23, 42\\$ (A104101)

Using any programming language, write a code that outputs these numbers.

### Scoring:

* Shortest answer wins
* The output must not contain any other numbers or letters. You may use any other character as separator, or even no separator at all.
* You cannot separate digits of the same number. \\$ 48\\\_15162342 \\$ is a valid answer, but \\$481\\\_5162342\\$ is not.
* You must respect the order.
* If your code does not contain any of the numbers from the sequence, reduce your score by 30%. This rule does allow you to enter the digits separately. E.g.:

```
abcde1fg5h

```

Is a valid candidate because the answer does not contain the number \\$15\\$, only its digits. However, any \\$4\\$ or \\$8\\$ will invalidate the bonus.
* If the code does not contain any digit at all, reduce your score by 50%. Other characters like \\$¹\\$, \\$²\\$ or \\$³\\$ are still valid for this bonus.

# Answer
# Lost, ~~29~~ 27/2 = 13.5 bytes

```
%?\>>>>>>>>>>
>>\"*"@"

```

Try it online! or verify that it is deterministic

Seemed like the right language to use.

### Explanation:

Lost is a 2D language where the pointer starts *anywhere*, going in *any* direction. This generally leads to a lot of double checking that the pointer hasn't entered a section early.

```
...>>>>>>>>>>  These arrows filter all pointers that appear on the top line
.............  Or going vertically

%............  This flips the flag so that the program can end
.............  This stops premature termination

.?\..........  Clear the stack by skipping if a value popped from the stack is positive
.............  When the stack is empty, the \ directs the pointer down

.............  The \ directs the pointer right
..\"*"..  The string literal pushes all the Lost values to the stack

..\..........  The @ terminates the program if the % flag is switched
>>\........@.  Otherwise it clears the stack and repeats

.............  The quote here is to prevent the pointer getting stuck
............"  This happens when the pointer starts between the other quotes

```
> 34 votes

# Answer
# Jelly, 7/2 = 3.5 bytes

```
“ƲÞIȥ’Ḥ

```

Prints the numbers without separator, i.e., the integer \\$4815162342\\$.

Try it online!

### How it works

`“ƲÞIȥ’` is bijective base-250 integer literal.
`Ʋ`, `Þ`, `I`, and `ȥ` have (1-based) indices \\$154\\$, \\$21\\$, \\$74\\$, and \\$171\\$ in Jelly's code page, so they encode the integer \\$250^3\cdot154+250^2\cdot21+250\cdot74+171=2407581171\\$.

Finally,  (unhalve) doubles the integer, yielding \\$2\cdot2407581171=4815162342\\$.

Doubling is necessary, because encoding the output directly leads to `“¡9)Ƙ[’`, which contains a digit.
> 11 votes

# Answer
# Neim, ~~6~~ 5 bytes, ~~3~~ 2.5 points

```
Jσς§A

```

Explanation:

```
J     Push 48
 σ    Push 15
  ς   Push 16
   §  Push 23
    A Push 42
      Implicitly join the contents
      of the stack together and print

```

Try it online!
> 9 votes

# Answer
# Python 3, 25 bytes, 12.5 points

```
print(*map(ord,'ዏٗ*'))

```

Try it online!

（髒, ⿰馬葬）, （謚, ⿰言⿱⿵八一皿） cost 4 bytes, but U+0657 only cost 2 bytes...

---

# Python 3, 29 bytes, 14.5 points

```
print(ord('')*ord('湡'))

```

Try it online!

（⿰馬葬） is variant character of 髒 which means "dirty". 湡 is the name of a river. And they are nothing related to this question as I known.
> 6 votes

# Answer
# 05AB1E, score: ~~10~~ ~~9~~ 7 bytes / 2 = 3.5

```
•‘o]Ê•·

```

Try it online.

Or **7 bytes alternative**:

```
•’µ[%•R

```

Try it online.

Both outputting the integer `4815162342`.

**Explanation:**

```
•‘o]Ê•     # Compressed integer 2407581171
      ·    # Doubled

•’µ[%•     # Compressed integer 2432615184
      R    # Reversed

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•‘o]Ê•` is `2407581171` and `•’µ[%•` is `2432615184`.

---

Old **9 bytes** answer outputting the list `[4,8,15,16,23,42]`:

```
•ΓƒÇ²•т;в

```

-1 byte (and therefore -0.5 score) thanks to *@Emigna*.

Longer than the other 05AB1E answer, but this outputs the list `[4,8,15,16,23,42]` instead of the integer `4815162342`.

Try it online.

**Explanation:**

```
•ΓƒÇ²•       # Compressed integer 1301916192
      т;     # Integer 50 (100 halved)
        в    # Convert the first integer to Base-50 (arbitrary): [4,8,15,16,23,42]

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer-lists?*) to understand why `•ΓƒÇ²•` is `1301916192`, and `•ΓƒÇ²•50в` is `[4,8,15,16,23,42]`.
> 6 votes

# Answer
# JavaScript (ES7), 34/2 = 17 bytes

```
_=>eval(atob`NjUwNTgxMDErNDEqKjY`)

```

Try it online!

This decodes and evaluates the expression `"65058101+41**6"`, which does not contain any digit once encoded in base-64.

$$65058101+41^6=65058101+4750104241=4815162342$$

---

# JavaScript (ES6), 13 bytes

Boring obvious solution.

```
_=>4815162342

```

Try it online!
> 6 votes

# Answer
# Brain-Flak, 52/2 == 26 bytes

```
(((((((((()()()())){})){}[()])())[]()()())){}[[]]())

```

Try it online!
> 4 votes

# Answer
# Java 8, score: ~~12~~ 11.9 (70% of 17 bytes)

```
v->767*6277917L+3

```

-0.1 score thanks to *@RickHitchcock*.

Try it online.

**Explanation:**

```
v->               // Method with empty unused parameter and long return-type
  767             //  767
     *6277917L    //  multiplied by 6277917 (as long)
              +3  //  And then 3 is added

```

---

**Old answer with a score of: 12 (50% of 24 bytes):**

```
v->(long)''*'Ⓥ'*'䧶'

```

Contains an unprintable character `0x1B`.

Try it online.

**Explanation:**

```
v->                   // Method with empty unused parameter and long return-type
  (long)              //  Cast the character (and therefore the result) to a long
        ''            //  27
           *'Ⓥ'       //  Multiplied by 9419
                *'䧶'  //  Multiplied by 18934

```

In Java, characters can be autoboxed to integers holding their unicode value. Unfortunately, the maximum supported unicode for characters is `65,535`, so I can't use just two characters to multiply (since the largest two numbers that divide the expected `4,815,162,342` are `56,802` and `84,771`, where the `84,771` unfortunately exceeds the maximum `65,535`.
In addition, since the maximum size of an `int` is 322-1 (`2,147,483,647`) and the result `4,815,162,342` is larger than that, an explicit cast to `long`, which can hold up to 642-1 (`9,223,372,036,854,775,807`), is required.

---

Boring answer would have been **14 bytes** without any bonuses:

```
v->4815162341L

```

Try it online.
> 4 votes

# Answer
# R, 18x0.7 = 12.6 score

```
cat(9*2*267509019)

```

Fairly self explanatory, just does some arithmetic avoiding the numbers in question.
> 4 votes

# Answer
# , 10 bytes, 27 characters

```
115160723426754314105574033

```

Try it online!

The packed representation of this program on disk is (`xxd` format):

```
00000000: 269c 3a71 6f63 308b 7c0d                 &.:qoc0.|.

```

## Explanation

We've seen this sequence of numbers before, in Automate Saving the World, which was about printing the numbers at regular intervals, making it interesting via requiring the use of a very old language. Much newer languages can have their own twists that make this challenge interesting, though. (Yes, this paragraph, and in fact the reason I started writing this answer, is effectively just a way to get all the related challenges to show up together in the sidebar; normally people do that using comments but I don't have enough rep.)

The first thing to note is that 7 is made entirely of digits, so going for the bonuses here is unlikely to work (although if you view the program as a sequence of octets, none of them correspond to ASCII representations of any of the original numbers, so you could claim the bonus in that sense). The next thing to note is that 7 has commands to recreate the command sequence likely to have produced a specific piece of data; so could we possibly interpret the Lost numbers `4815162342` as a section of a 7 program itself?

The answer is "not quite". The most problematic part is that second number, `8`. 7 programs are written in octal; there's no such number as 8. So the very start of the string will have to be printed differently.

The base of the program is therefore based on the 7 "Hello world" program:

```
5431410557403
543141055          string literal
         7         separate data from code
          4        rearrange stack: {program's source}, empty element, {literal}
           0       escape {the literal}, appending it to {the empty element}
            3      output {the escaped literal}, pop {the program's source}

```

with the escaped literal being in a domain-specific language that's interpreted as follows:

```
5                  output format: US-TTY using pairs of digits in the string
 43                select character set: digits and common symbols
   14              "4"
     10            "8"
       55          forget the set output format

```

After this comes an extra `3`, which outputs the remaining stack element (and exits due to insufficient remaining stack). That element is specified at the start of the program, and to avoid the unmatched `6` (which works a bit like a closing bracket), we generate it using code, rather than writing it directly as data. (Note that there are two implied `7` characters at the start of the program, which is relevant here):

```
{77}115160723426
 7                 empty stack element
  7 11516          append "1151"
         0         append "6"
          723246   append "2324"

```

That produces the following literal:

```
115162324
1                  set output format: literally as octal
 15162324          "15162324"

```

which gets printed out.
> 4 votes

# Answer
# 05AB1E, 6\*0.7 = 4.2 bytes

```
•1Z&ð“

```

Try it online!

Prints the number uncompressed from base-255
> 3 votes

# Answer
# MASM 8088 Assembly source, (93 bytes - 50%) = 46.5 bytes

Using no numbers or the sequence in the source:

```
MOV AH,'P'-'G'
LEA DX,L
INT '!'
RET
T EQU '-'-'+'
L DW 'ph'/T,'jb'/T,'lb'/T,'fd'/T,'dh'/T,'$'

```

Output:

```
A>LOST.COM
4815162342

```
> 3 votes

# Answer
# Charcoal, 13 bytes / 2 = 6.5

```
ＩＥTPIHA.⁻⁸⁸℅ι

```

Try it online! Link is to verbose version of code. Works by subtracting the ASCII codes of the string `TPIHA.` from 88 and casting to string.
> 2 votes

# Answer
# Aheui (esotope), 45 bytes(15 chars) * 0.5 = 22.5 points

```
반밤밪박밭빠따받발따밣뱣히망어

```

Try it online!

---

Explanation:

See this also; Aheui Reference(English)

```
Aheui program starts with default stack '아'(or none)

반: push 2, move cursor right by 1(→).
밤: push 4, →
밪: push 3, →
박: push 2, →
밭: push 4, →
빠: dup, →
따: pop 2, push mul result(16).
받: push 3, →
발: push 5, →
따: pop 2, push mul result(15).
밣: push 8, →
뱣: push 4, move cursor right by 2(→→).
히: end.
망: pop 1, print, → (if stack is empty, move cursor left by 1.)
어: move cursor left by 1(←).

```

Note that ㅁ(print instruction) moves cursor by reverse direction if stack(or queue) is empty.
> 2 votes

# Answer
# Perl 5, 16 bytes - 30% = 11.2

```
say 0x5FAB2EA2*3

```

Try it online!
> 2 votes

# Answer
# PowerShell, 12 bytes * 0.7 = 8.4

```
0x5FAB2EA2*3

```

Try it online!

"Port" of Xcali's answer to have a better Powershell answer.
> 2 votes

# Answer
## `j`, 7 / 2 = 3.5 points

I updated the ord to support W's own code page.

```
0“„√*"C

```

## Explanation

0“„√*"  % Define a string
      C % Convert to codepoints [48,15,16,23,42]

Flag:j  % Join the output list without a separator
```
</code></pre>
> 2 votes

# Answer
# naz, 46 bytes, score 32.2

```
2a2a1o2m1o7s1o5m1o2s2s1o6m1o2s2s1o1a1o1a1o2s1o

```

Simply outputs each digit in `4815162342` one at a time.
> 2 votes

# Answer
# MAWP, 24 bytes

```
4!:2W!:2W!1A!::7M!:2W4A:

```

Try it!
> 2 votes

# Answer
## JavaScript, 143 bytes (not sure how to score)

```
(g=`${2*2}`)=>g.repeat(6).replace(/(.)/g,(m,p,i,k='')=>
  (k=m*[g-3,g-2,g,g,+g+2,g*3-1][i]
  ,RegExp(`${g-2}|${g}`).test(i)?k-1:i==+g+1?k-(g/2):k))

```

Try it online!

Start with six `4`'s, multiply, add, subtract by, to, from `4` to derive output.
> 1 votes

# Answer
## JavaScript (SpiderMonkey), 67 bytes / 2 = 33.5 60 bytes / 2 = 30 58 bytes / 2 = 29 48 bytes / 2 = 24

*-7 bytes/3.5*, *-2 bytes/1* courtesy of @JoKing, *-10 bytes/5* courtesy of @tsh

```
print(a=-~-~-~-~[],a+=a,b=a+~-a,a+a,a+b,--b+b+b)

```

Try it online!
> 1 votes

# Answer
# PHP, 35/2=17.5

```
<?=zzzzzzzzzzzzzzz^NVBVKOVKLVHIVNH;

```

a digital approach: **40\*.7=28**

```
<?=2+2,_,5+3,_,17-2,_,17-1,_,17+6,_,7*6;

```

no digits, no strings: **68/2 = 34**

```
<?=$p++,!$p++,$p+=$p,_,$p+=$p,_,~-$q=$p+$p,_,$q,_,--$p+$q,_,$p*~-$p;

```

---

Try them online.
> 1 votes

# Answer
# Japt, ~~10~~ 9 bytes / 2 = 4.5

```
"0¢*"mc

```

Test it
> 1 votes

# Answer
# APL(Dyalog Unicode), 18/2 = 9 bytes

```
×/⎕UCS'湡'

```

Just boring old character multiplication.

Try it online!
> 1 votes

# Answer
# Whitespace, score: ~~49~~ 41 bytes / 2 = 20.5

```
[S S S T    S S S T T   T   T   T   S S S S S S S T T   S S S T S T T   T   T   T   S S T   T   S N
_Push_4815162342][T N
S T _Print_number]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

**Pseudo-code:**

```
Integer i = 4815162342
Print i as number to STDOUT

```

**Explanation:**

In whitespace, a number is pushed as follows:

* `S`: Enable Stack Manipulation
* `S`: Push number
* `S`/`T`: Positive/negative respectively
* Some `T`/`S` followed by a single `N`: Decimal as binary, where `T` is 1 and `S` is 0

After that it is simply printed with `TNST`:

* `TN`: Enable I/O
* `S`: Output the top of the stack
* `T`: As number
> 1 votes

# Answer
# JavaScript (ES6), 16 * 0.7 = 11.2 bytes

```
_=>767*6277917+3

```

Outputs the digits with no delimiters.

Try It Online!
> 1 votes

# Answer
# F#, 45 bytes = 22.5 points

Just a run-of-the-mill `for` loop that prints the digits:

```
for c in"DHOPWj"do printf"%d"(int c-int '@')

```

The above is a complete program that can be compiled into an executable.

In a REPL (read-eval-print loop), e.g. FSI (F# Interactive), the following shorter version will work, as the REPL will output a representation of the expression evaluated; it has 35 bytes = 17.5 points:

```
[for c in"DHOPWj"->int c-int '@'];;

```
> 1 votes

# Answer
# Python 3, ~~44~~ ~~38~~ ~~19~~ 18.5 bytes

-6 bytes thanks to @Jo King
-50% bytes thanks to @ouflak for pointing out the 50% bonus
-1 byte thanks to @Dennis

```
for i in'밗ɯ*':print(ord(i),end='')

```

Try it online!
> 1 votes

# Answer
# Pyke, 3 points

```
77 91 f8 86 98 06

```

Try it here!

The first byte signals to read in base 128 until a byte without the high bit is set.

Finally, 32 is subtracted from the result (for historical reasons).

This allows for the generation of large numbers in very small amounts of space
> 1 votes

# Answer
# MathGolf, 7 bytes * 0.5 = 3.5

```
ÿ≤┼ÇÅ$∞

```

Try it online!

## Explanation

Note that this code doesn't yet work on TIO. I have made some changes to MathGolf recently, including adding the `$` operator. Once it gets pulled to TIO you can run it there, I'll make an update to this answer then. It runs perfectly in the terminal

```
ÿ≤┼ÇÅ     Push "≤┼ÇÅ"
     $    pop(a), push ord(a) (pushes 2407581171)
      ∞   pop a, push 2*a

```

I utilize the fact that MathGolf has 1-byte literals for creating strings of up to length 4. If I wanted to convert the entire number from a base-256 string, I would have needed to use two `"`, and the string would have been 5 characters. This way, I save 2 bytes, but I lose one byte by having the doubling operator in the end.
> 1 votes

# Answer
# Python 3 34 Points

```
b=len("  ");c=b*b;d=c*b;e=d*b;g=e+d-b//b;print(c,d,e-b//b,e,g,g*b-c)

```
> 1 votes

# Answer
# C# (.NET Core), 17 bytes \*.7 = 11.9 bytes.

Ascii-Only's version.

```
()=>0x5FAB2EA2l*3

```

Try it online!

# C# (.NET Core), 42 bytes, score = 42/2 = 21

Uses the F386 and BC17 characters.

```
()=>{return $"{(int)'밗'}{(int)''}";};

```

Try it online!
> 1 votes

# Answer
# Befunge-98 (FBBI), 15 bytes / 2 = 7.5 points

```
"*H/!k-"*.*+..@

```

Try it online!

## Explanation:

First push the ASCII values of the characters '\*+H/!k- (42, 72, 47, 33, 107, 45) in this order to the stack. Then compute \\$4815 = 45 \cdot 107\\$ and \\$1623 = 33\cdot 47+72\\$, and output.
> 1 votes

# Answer
# Runic Enchantments, 15/2 = 7.5

```
\>`*`
Rn$!;

```

Try it online!

Simply encodes the values in as few bytes as possible. `42`, `16`, `15`, `8`, and `4`, coerces them to numerical values, and prints them in reverse order. `4 8 15 16 42` without any spaces, as `48151642` was an acceptable output format.

`4` and `8` could not be combined (`48`) as that is a numerical `0` and was not allowed to be used. It is possible to combine the 15, 16, and 42 into 2 characters (instead of 3) `ʂ` at the expense of +1 byte, which wasn't worth it.
> 1 votes

# Answer
# Keg, 8 - 50% = 4 bytes

```
밗..

```

Try it online!

## Answer History

### 10 - 50% = 5 bytes

```

```

Try it online!

Literally just prints the number `4815162342` using the push'n'print method.
> 1 votes

# Answer
# Intcode, 33 bytes

```
4,0,104,8,104,16,104,23,104,42,99

```

Basic hardcoded answer (`104` means "output the number after this in the sequence"). Getting the bonus would be very hard (although probably possible), given that `4` is the output instruction ...
> 1 votes

# Answer
# Python 2, 16 bytes

```
print 4815162342

```

Try it online!
> 0 votes

# Answer
# Red, 50 bytes / 2 = 25

```
foreach c"abcdcefgaf"[prin index? find"cfgade.b"c]

```

Try it online!

Prints the numbers without separator
> 0 votes

# Answer
# perl -M5.010 -Mre=eval, 32/2 == 16 bytes

This program is mostly unprintable characters -- characters which aren't even Unicode characters. Here is a hexdump of the program:

```
$ od -x solution
0000000      2727    7e3d    277e    c0d7    8c84    869e    cbd8    c7d3
0000020      ced3    d3ca    c9ce    cdd3    d3cc    cdcb    82d8    27d6
0000040
$

```

And here's the program to create the solution:

```
#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

my $q = ~"(?{say'4,8,15,16,23,42'})";
print "''=~~'$q'";

__END__

```
> 0 votes

# Answer
# Z80Golf, 17 bytes * 0.5 = 8.5

```
00000000: 1b17 1e1a 1e19 1d1c 1b1d 2676 0a03 c5ee  ..........&v....
00000010: 2f                                       /

```

Try it online!

Assembly:

```
db 0x2F ^ '4'	;1b dec de
db 0x2F ^ '8'	;17 rla
db 0x2F ^ '1'	;1e ld e,
db 0x2F ^ '5'	;1a  0x1a
db 0x2F ^ '1'	;1e ld e,
db 0x2F ^ '6'	;19  0x19
db 0x2F ^ '2'	;1d dec e
db 0x2F ^ '3'	;1c inc e
db 0x2F ^ '4'	;1b dec de
db 0x2F ^ '2'	;1d dec e
ld h, 0x76	;halt

ld a, (bc)	;load the next digit. The first char in addr in 0x0
inc bc		;get next digit
push bc		;return to the next digit which is basically a nop
xor 0x2F	;decode the digit
		;fall through into putchar. Putchar (0x8000), prints the char in register a

```

Assembly
> 0 votes

# Answer
# Wolfram Language (Mathematica), 68 bytes (score 34)

```
#&@@@"distinctive pattern nothing is known about"~StringPosition~"t"

```

Try it online!

Prints the list `{4,8,15,16,23,42}`.
> 0 votes

# Answer
# T-SQL, 20 bytes - 30% bonus = 14

```
PRINT 2.*9*267509019

```

Contains none of the sequence directly. Factored via this web site. The period is in there as an implicit conversion to float so we don't overflow an INT.

This is just slightly better that the trivial solution (**16 bytes, no bonus**):

```
PRINT 4815162342

```
> 0 votes

# Answer
# Perl 6, 17 bytes * 0.5 = 8.5

```
say ords "*"

```

Try it online!

This gets the ordinal values of a lot of unprintables and gets the no digits bonus. Using the no numbers from the sequence bonus, we can get 16 * 0.7 = 11.2 points:

```
say 0x5FAB2EA2*3

```

Try it online!

Which in turn beats the plain solution of 14 bytes:

```
say 4815162342

```

Try it online!
> 0 votes

# Answer
# Python 2, ~~38 * 0.5 = 19 score~~ 34 bytes * 0.5 = 17 score

```
print map(`int`.find,"ent t'ypey")

```

Try it online!

Outputs a list of the digits in the sequence; i.e. the list `[4, 8, 1, 5, 1, 6, 2, 3, 4, 2]`.

Because it's more interesting to satisfy the 'no digits' approach, regardless of the score.

# Python 2, 23 bytes - 30% = 16.1 score

```
print int('27mtn1i',36)

```

Try it online!
> 0 votes

# Answer
# Lua, 69 bytes / 2 = 34.5 points

```
a={"","","","","","*"}s=" "for i=#s,#a do print(s.byte(a[i]))end

```

Try it online!
> 0 votes

# Answer
# Powershell, 10 bytes, score 10

```
4815162342

```
> 0 votes

# Answer
# SmileBASIC, 13 - 30% = 9.1 bytes

```
?&h1CB35ACA;2

```

Uses a hexadecimal number to avoid any of the numbers in the sequence. The final `2` needs to be printed separately because `4815162342` doesn't fit into a 32 bit signed integer.
> 0 votes

# Answer
# brainfuck, 55 bytes

```
-[>+<-----]>+.++++.-------.++++.----.+++++.----.+.+.--.

```

Try it online!
> 0 votes

# Answer
# Gol\>\<\>, 12 bytes, score 6

```
"*"lRn;

```

Pretty simple, I just used whitespace to encode and outputted it in order, I believe the score is correct, since it said to set it to 50% if you don't use any numbers, and this only has ascii characters!

Try it online!
> 0 votes

# Answer
## VBA (Excel), ~~38~~ 66 bytes - 50% = 33 points

Using Immediate Window

~~`?Join(Split("4 8 1 5 1 6 2 3 4 2"),"")`~~

```
a="         ":For Each x in Split(a):b=b &Asc(x):Next:?b
```
> 0 votes

# Answer
# \>\<\>, 29/2 = 14.5 bytes

```
','a+'a''a'*a+:f+f+f+f+c-**n;

```

Forms on the stack 3 numbers `54` `9419` `9467`, multiplies them and outputs `4815162342`.

Try it online!
> 0 votes

---
Tags: number, code-challenge, integer
---


title: How do I change my stove's temperature?

text:
# Question
Title: How do I change my stove's temperature?
My stovetop has 10 different settings of heat (0 through 9) and a very odd way of cycling through them.

* When I hit plus (`+`) it increments the number, *unless* the number is 9 in which case it becomes 0, or the number is 0 in which case it becomes 9.
* When I hit minus (`-`) it decrements the number, *unless* the number is zero in which case it becomes 4.

There are no other temperature control buttons.

So when I am cooking on one temperature and I want to change to another, it's always a bit of a puzzle to figure out what the easiest way to get to that temperature is.

In this challenge you will take a starting temperature and a desired temperature and give the shortest sequence of button presses to get from the starting temperature to the desired temperature.

You should take input as two integers on the range 0-9 and output a sequence of instructions. You may output the instructions either as the characters/strings `+` and `-` or as the numbers `1` and `-1`. If there are two equally minimal sequences you may output either or both.

This is so the goal is to minimize the size of your source code as counted by the number of bytes.

## Test cases

```
0 0 -> ""
0 1 -> "----"
0 2 -> "---"
0 3 -> "--"
0 4 -> "-"
0 5 -> "-+"
0 6 -> "-++"
0 7 -> "+--"
0 8 -> "+-"
0 9 -> "+"
1 0 -> "-"
1 1 -> ""
1 2 -> "+"
1 3 -> "++"
1 4 -> "--"
1 5 -> "--+"
1 6 -> "--++"
1 7 -> "-+--"
1 8 -> "-+-"
1 9 -> "-+"
2 0 -> "--"
2 1 -> "-"
2 2 -> ""
2 3 -> "+"
2 4 -> "++"
2 5 -> "+++"
2 6 -> "++++"
2 7 -> "+++++" or "--+--"
2 8 -> "--+-"
2 9 -> "--+"
8 0 -> "++"
8 1 -> "++----"
8 2 -> "++---"
8 3 -> "++--"
8 4 -> "++-"
8 5 -> "---"
8 6 -> "--"
8 7 -> "-"
8 8 -> ""
8 9 -> "+"
9 0 -> "+"
9 1 -> "+----"
9 2 -> "+---"
9 3 -> "+--"
9 4 -> "+-"
9 5 -> "+-+"
9 6 -> "---"
9 7 -> "--"
9 8 -> "-"
9 9 -> ""

```

# Answer
# JavaScript (ES6),  ~~88 86 75~~  74 bytes

Expects `(desired_temp)(starting_temp)`.

```
b=>g=a=>a-b?"+-"[q=a>b^b<"7489001156"[a]^!a^a<4]+g(a?q?a-1:-~a%10:9>>q):""

```

Try it online! (test cases)

Try it online! (all cases, checked against an ungolfed brute force search)

### How?

The most natural behavior is to hit `+` when the desired temperature \\$b\\$ is greater than the current temperature \\$a\\$, and to hit `-` when it's lower.

Below are all the cases where we need to do the opposite of the natural behavior, along with the corresponding test on \\$b\\$ according to \\$a\\$:

```
   | 0 1 2 3 4 5 6 7 8 9 | test
---+---------------------+-------
 0 | X X X X X X X - - - | b < 7
 1 | - - - - X X X X X X | b > 3
 2 | - - - - - - - - X X | b > 7
 3 | - - - - - - - - - X | b > 8
 4 | - - - - - - - - - - | none
 5 | - - - - - - - - - - | none
 6 | X - - - - - - - - - | !b
 7 | X - - - - - - - - - | !b
 8 | X X X X X - - - - - | b < 5
 9 | X X X X X X - - - - | b < 6

```

This can be encoded with the following lookup table:

```
[b < 7, b > 3, b > 7, b > 8,,, !b, !b, b < 5, b < 6][a]

```

By normalizing all tests to \\$b\<t\_a\\$ and inverting the result when \\$a\in\\{1,2,3\\}\\$, this can be further optimized to:

```
b < "7489001156"[a] ^ !a ^ a < 4

```

The result is XOR'ed (again) with the test `a > b`, leading to either \\$0\\$ for `+` or \\$1\\$ for `-`.

We then do a recursive call where \\$a\\$ is updated using the same logic as in my answer to the reverse challenge and keep going that way until \\$a=b\\$.
> 10 votes

# Answer
# JavaScript, 146 144 bytes

```
(a,b)=>{for(z=2;i=a;++z){y=z.toString(2).slice(1);for(x of y)i=x>0?i++?i%10:9:i--?i:4;if(i==b)return a-b?y[r='replaceAll'](0,'-')[r](1,'+'):''}}

```

## Demo

This snippet recreates the test cases from the post.

```
let f =

(a,b)=>{for(z=2;y=z.toString(2,i=a).slice(1);++z){for(x of y)i=x>0?i++?i%10:9:i--?i:4;if(i==b)return a-b?y[r='replaceAll'](0,'-')[r](1,'+'):''}}

// Test all cases from the original challenge
for (const startVal of [0,1,2,8,9]){
    for (const endVal of [...Array(10).keys()]){
        console.log(`${startVal} ${endVal} -> "${f(startVal,endVal)}"`)
    }
}
```

## Explanation

This is my first time golfing, but hey, there has to be a first time for everything.

To explain the code, I'll first format the code and rename variables:

```
function stove(startVal, endVal) {
    for (iterator = 2; y = iterator.toString(2, currentVal = startVal).slice(1); ++iterator) {
        for (x of y) currentVal = x > 0 ? currentVal++ ? currentVal % 10 : 9 : currentVal-- ? currentVal : 4;
        if (currentVal - endVal == 0) return startVal-endVal?y[r = 'replaceAll'](0, '-')[r](1, '+'):''
    }
}

```

and then break it apart to a non-golfed version with comments

```
function stove(startVal, endVal) {
    // Iterate through all possible stove inputs, starting from the shortest
    for (let iterator = 2; true; iterator++) {
        // Reset the currentVal variable every loop
        let currentVal = startVal;

        // Convert iterator to binary to convert it to stove inputs later on
        let bin = iterator.toString(2);
        // Start the iterator at 2 and remove the first character
        // This allows for combinations such as 000/--- to appear when they normally wouldn't
        let buttonSequence = bin.slice(1);

        // Run the stove simulation
        for (const button of buttonSequence) {
            currentVal = button > 0 ? currentVal++ ? currentVal % 10 : 9 : currentVal-- ? currentVal : 4
        }

        // If currentVal and endVal are the same, meaning we've reached the desired end state
        if (currentVal - endVal == 0) {
          // Replace ones and zeroes in the button combination with plusses and minuses, then return
          // If currentVal and endVal are the same, return '' instead, because no button pushes are required
          return (startVal-endVal) ? buttonSequence.replaceAll('0', '-').replaceAll('1', '+') : '';
        }
    }
}

```

Funnily enough, implementing the game was the easiest part, `i=x>0?i++?i%10:9:i--?i:4` runs one round of the entire game, so here's a breakdown of that:

```
// This is true for the string '1' and false for '0'
if (button > 0) {
    // The + button was pressed
    if (currentVal > 0) {
        // If the value is not 0, increase it by one and mod 10 so 9 becomes 0
        currentVal = (currentVal + 1) % 10;
    } else {
        // If the value is 0, set it to 9 as the rules require
        currentVal = 9;
    }
} else {
    // The - button was pressed
    if (currentVal > 0) {
        // If the value is not 0, decrease it
        currentVal--;
    } else {
        // If the value is 0, set it to 4
        currentVal = 4;
    }
}

```
> 10 votes

# Answer
# Haskell, 89 bytes

```
g s=f[[s]]
f((w:a):x)e|e==w=a|1>0=f(x++[w!d:a++[d]|d<-[1,-1]])e
9!1=0
0!1=9
0!_=4
t!d=t+d

```

Try it online!
> 7 votes

# Answer
# JavaScript (node.js), 125 bytes

```
g=(q,r)=>(o=[],f=((v,r)=>!o[r]||v.length<o[r].length?(o[r]=v,f(v+'+',r?(r+1)%10:9),f(v+'-',r?r-1:4)):0),f('',q),q==r?'':o[r])

```

Try it online!
> 5 votes

# Answer
# JavaScript (Node.js), 65 bytes

```
t=>g=(s,o='',...r)=>s-t?g(...r,s%9?s+1:9-s,o+'+',s?s-1:4,o+'-'):o

```

Try it online!

---

# Python 3, 82 bytes

```
f=lambda t,s,o="",*r:s-t and f(t,*r,[9-s,s+1][0<s<9],o+"+",[4,s-1][0<s],o+"-")or o

```

Try it online!
> 5 votes

# Answer
# Jelly,  ~~28~~  25 bytes

```
o8r4¤+⁹ị@%⁵
ȷŒPḂo-çƒ³⁼ɗƇḢ

```

A full program that accepts the from and to values which prints a list of `-1`s and `1`s.

Don't try it online (it's checking \\$2^{1000}\\$ instruction strings, for golf!)

**Try it online!** (with a reduction from the powerset of \\$1000\\$ items to just \\$12\\$ so it runs in time)

Or try 10 at a time, from the given value to all others. (Takes about 20 seconds; as above, but also uses the register, `®`, in place of the second program argument, , since that's not mutable.)

Lastly, this 26 byter that only forms strings up to length six is much faster.

### How?

```
o8r4¤+⁹ị@%⁵ - Link 1, make a move: current value, V ([0,9]); button, B (+/-1)
 8r4¤       - [8,7,6,5,4]
o           - V logical OR that (either [V,V,V,V,V] or [8,7,6,5,4] if V=0)
     +⁹     - add B to each of those values
       ị@   - use B to index into that list
              (1-indexed and modular: if B=1 the first; if B=-1 the fourth)
         %⁵ - modulo 10

ȷŒPḂo-çƒ³⁼ɗƇḢ - Main Link: from, F ([0,9]); to, T ([0,9])
ȷ             - 1000 (saves a byte over `12`)
 ŒP           - powerset (shorter strings come first)
   Ḃ          - modulo 2
    o-        - logical OR -1 (vectorises)
           Ƈ  - filter keep those for which:
          ɗ   -   last three links as a dyad - f(instruction, T)
        ³     -     first program argument, V
       ƒ      -     reduce [V]+instruction by:
      ç       -       call last Link (Link 1) as a dyad
         ⁼    -     equals T?
            Ḣ - head (gets a/the shortest string)

```
> 4 votes

# Answer
# , 149 bytes

Or **\>=4.1, 135 bytes** by replacing two `function` occurrences with `\`s.

```
function(a,b,x=combn(rep(-1:1,6),6),y=x[,apply(x,2,function(t){for(i in t)a=(a+i)%%10+"if"(i>0,8,-5)*i*!a;a==b})],z=y[,order(colSums(!!y))[1]])z[!!z]

```

Try it online!

Brute-force approach. Probably porting one of the clever non-brute-force solutions would be shorter.

Borrows some code from Xi'an's answer to the related challenge.
> 2 votes

# Answer
# 05AB1E, ~~29~~ 27 bytes

```
®X‚6иæé.Δ¹svDy+T%Ƶ₆yè‚s_è}Q

```

Input as two separated integers; output as as a list of `-1,1` for `-+` respectively.

Try it online or verify all test cases.

Since I was curious: a hard-coded approach of all test cases would be **52 bytes** in comparison:

```
•‡fsΣï6ÿîœ½Ii†_³•„+-Åв•3o₂₁∞5û±Õ¸ôk,ƒ
cÆмÄœº•0š£ITβè

```

Input as a pair; output as a list of `-+` characters.

Try it online or verify all test cases.

**Explanation:**

```
®X‚            # Push pair [-1,1]
   6и          # Repeat it 6 times as list: [-1,1,-1,1,-1,1,-1,1,-1,1,-1,1]
     æ         # Take the powerset of this
      é        # Sort it by length
.Δ             # Find the first/shortest list that is truthy for:
  ¹            #  Push the first input
   s           #  Swap so the list is at the top again
    v          #  Loop over each of its items `y`:
     D         #   Duplicate the current result
      y+       #   Add `y` to the copy
        T%     #   Modulo-10
      Ƶ₆       #   Push 194
        yè     #   Index `y` into it (1→9; -1→4)
          ‚    #   Pair the two together
           s   #   Swap so the result is at the top again
            _  #   Check if it's 0 (1 if 0; 0 otherwise)
             è #   Index it into the pair
    }          #  Close the loop
     Q         #  Check if it's now equal to the (implicit) second input
               # (after which the found list is output implicitly as result)

```

```
•‡fsΣï6ÿîœ½Ii†_³•
            # Push 664379026224093486851406838200392383
 „+-Åв      # Convert it to custom base-"+-"
            # (basically convert it to base-2, and index into "+-")
  •3o₂₁∞5û±Õ¸ôk,ƒ\ncÆмÄœº•
            # Push 4321233211012234432210123454326543321011543233210
   0š       # Convert it to a list of digits, and prepend a 0
     £      # Split the list of "+-" into lists of that size
      I     # Push the input-pair
       Tβ   # Convert it from a base-10 list to an integer
         è  # Use that to index into the earlier list
            # (after which the list is output implicitly as result)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ƶ₆` is `194`; `•‡fsΣï6ÿîœ½Ii†_³•` is `664379026224093486851406838200392383`; and `•3o₂₁∞5û±Õ¸ôk,ƒ\ncÆмÄœº•` is `4321233211012234432210123454326543321011543233210`.
> 2 votes

# Answer
# Python 3, 97 bytes

```
f=lambda a,b,*c:a!=b<10>len(c)and min((f((-i%7+3,a+i)[a>0]%10,b,*c,i)for i in(-1,1)),key=len)or c

```

Try it online!
> 1 votes

# Answer
# Perl 5, 131 bytes

```
sub{($_,$w,$s,@t)=@_;@t=sort{length$$b[1]<=>length$$a[1]}@t,[$_?$_-1:4,"$s-"],[$_++?$_%10:9,"$s+"]and($_,$s)=@{pop@t}while$_-$w;$s}

```

Try it online!
> 1 votes

# Answer
# Charcoal, 46 bytes

```
Ｎθ⊞υ⟦Ｎω⟧ＦυＦ²Ｆ¬⊙υ№λθ⊞υＥι⎇ν⁺μ§+-κ⎇κ⊖∨μ⁵﹪⊕∨μ⁸χ⊟⊟υ

```

Try it online! Link is to verbose version of code. Takes the desired temperature first and the starting temperature second. Explanation:

```
Ｎθ

```

Input the desired temperature.

```
⊞υ⟦Ｎω⟧Ｆυ

```

Start a breadth-first search with the starting temperature and no button presses.

```
Ｆ²

```

Check each button.

```
Ｆ¬⊙υ№λθ

```

Stop processing once all the desired temperature has been found.

```
⊞υＥι⎇ν⁺μ§+-κ⎇κ⊖∨μ⁵﹪⊕∨μ⁸χ

```

Calculate the next temperature and push that with its updated list of button presses.

```
⊟⊟υ

```

Output the button presses that reached the desired temperature.
> 1 votes

# Answer
# Brachylog, 40 bytes

```
;X≜{∧1w₄&{0∧9!|9∧0|+₁}|∧_1w₄&{0∧4|-₁}}ⁱ⁾

```

Try it online!

Starting temperature through input variable, target temperature through output variable, prints solution at end of program (+3 bytes if the `1`/`-1` format doesn't extend to strings; if it's permitted with a separator just replace both `w`s with s). Brute-forces all sequences shortest first until one reaches the target.

Can probably be shorter. Checked against Arnauld's JS solution.
> 1 votes

# Answer
# Python3, 168 bytes:

```
lambda *x:min(f(*x),key=len)
def f(a,b,c=''):
 if a==b:yield c
 if len(c)<10:
  yield from f([a+1,[9,0][a==9]][a in[0,9]],b,c+'+')
  yield from f([4,a-1][a!=0],b,c+'-')

```

Try it online!
> 0 votes

# Answer
# T-SQL, 190 bytes

```
WITH C as(SELECT @ a,cast(''as VARCHAR(max))r
UNION ALL
SELECT(a+iif(a=0,4-5*~p/2,p))%10,r+CHAR(44-p)FROM
C,(VALUES(1),(-1))X(p)WHERE len(r)<6)SELECT
top 1r FROM C WHERE @2=a ORDER BY len(r)

```

**Try it online**
> 0 votes

---
Tags: code-golf
---


title: Markov Chain Quine

text:
# Question
Title: Markov Chain Quine
A simple Markov Model will be used in this question. For more information about Markov Chains, see http://setosa.io/ev/markov-chains/.

Take a string. For this example, we will use the word:

```
reader

```

Now, for each character, take the characters that appear after each occurence of the character in the string. (``^`` represents the start of the string and ``$`` represents the end)

```
`^` -> {'r'}       # After the start of the string, there is an `r`.
'r' -> {'e', `$`}  # After the first `r` (*r*eader), there is an `e`
                   # after the second (reade*r*), there is the end of the string.
'e' -> {'a', 'r'}
'a' -> {'d'}
'd' -> {'e'}

```

Now, starting from the start of the string, pick randomly from one of the characters in the next set. Append this character and then pick from the characters in its next set, and so on until you get to the end. Here are some example words:

```
r
rereader
rer
readereader

```

If a character appears after another character multiple times, it is more likely to be chosen. For example, in `cocoa can`, after a `c`, there is a two thirds of a chance of getting an `o` and a one thirds chance of getting an `a`.

```
'c' -> {'o', 'o', 'a'}

```

# Challenge

Create a program that takes no input and outputs a random string generated using a Markov Chain, like above, where the input to the chain is the program's source.

1. The program must have at least two characters, two of which must be the same (To prevent "boring" chains that only have one output)
2. You can modify the model to use bytes instead of characters if you wish, but change "characters" to "bytes" in rule 1
3. The program should output strings randomly with the expected frequency in theory

This is , so the shortest program wins!

# Answer
> 6 votes
## Pip, 64 bytes

This was fun.

```
t:V Y\"m:"Yt@0T9=A OyY@>RC(t(Xy).'.)"ST["t:V Y"RPy";Vm"C9]\";Vm<tab>

```

`<tab>` represents a literal tab character (`0x09`). Try it online!

### How?

TL;DR: escaped-string syntax, repr, and eval.

For strings that need to contain literal `"` characters, Pip has *escaped strings*, using `\"` as the delimiter. A standard quine using escaped strings would look like this:

```
V Y\""V Y".RPy\"

```

That is: `Y`ank (storing as `y`) a string containing `"V Y".RPy` and e`V`al it. `RPy` takes the repr of `y`, to which we prepend the literal string `V Y`. Finally, output the result of the eval.

The structure of the Markov quine is similar, except that we want to save the code instead of outputting it and then do some stuff with it afterwards. `t:V Y\"...\"` assigns the eval result to `t`. Inside the eval'd code, `m:"..."` assigns a string of code to `m`, which we will evaluate at the end with `Vm`.

`ST["t:V Y"RPy";Vm"C9]` builds a list containing

```
"t:V Y"  Literal string
RPy      Repr(y)
";Vm"    Literal string
C9       Tab character

```

and converts it to a string, which by default concatenates all the items. This section is equivalent to `"V Y".RPy` in the original quine. Since it is the last expression in the big eval string, its value is what the `V` operator returns, and thus what gets assigned to `t`.

Thus, after the eval and assignment, `t` is equal to the full code, and `m` contains

```
Yt@0T9=A OyY@>RC(t(Xy).'.)

```

Now `Vm` evaluates that as code. Let's break down what happens.

```
                            We'll use y to hold the current character in the chain
Yt@0                        Yank first character of t into y (chain always starts there)
         Oy                 Output y without newline each time we...
    T9=A                    Loop till ASCII code of y equals 9 (tab)
                            Since there's only one literal tab, at the end of the program,
                              this satisfies the Markov chain ending requirement
                   Xy       Generate a regex that matches y
                  (  ).'.   Concatenate . to regex: now matches y followed by any character
                (t       )  Find all matches in t (returns a list)
              RC            Random choice from that list
           Y@>              Slice off the first character and yank the remaining one into y

```

A couple notes:

* Ending the code with a literal tab was shorter than doing a regex test for "next character or end of string."
* The regex I used does not work properly if there are doubled characters in the code; for instance, applying it to `xxy` would return only `xx` and not `xy` in the matches. Fortunately, however, there are no doubled characters in this code, so it doesn't matter.

# Answer
> 8 votes
# JavaScript, ~~217~~ 215 bytes

```
a="a=q;a=a.replace('q',uneval(a));for(b=c='a';d=a.split(c),c=d[Math.random()*~-d.length+1|0][0];b+=c);alert(b)";a=a.replace('q',uneval(a));for(b=c='a';d=a.split(c),c=d[Math.random()*~-d.length+1|0][0];b+=c);alert(b)
```

Note that this uses `uneval`, which is only supported by Firefox. Sample runs:

```
a=ale(a.lend[Ma=d[Macepla.ler(b+=c)b=q;fom(a=q;a=dort(b+1|0],c);a.lit(a)
at(c=c;d[0],c=q;ath+1|0][0];dorerac=ac=d[Ma),c;)*~-d[Ma=alenepl(b+=ac=c;a=c;d[2];d.re(c;fom()
a="a[0],und=d=a)
angt(b),und=d.l(b=a)
a)
ale(a.rth.revanepleplit(b)
ac);fore(b)*~-d.r(b+1|0];fora';a)*~-d.splalith+=dorth+=c=";ath+=a.length+=';ale(b)
a.r(b=c=a)b+1|0],und[0][0];d.splerath.spleneva)";ath.r(ceneplith+=d=aceple(c;)*~-d=';ala';)b='ac;fom(b=c;a.ler(b=d=d[Ma.rt(c=cendor()*~-d='a=";ac;a.spla)b=ceva=';a=d.rt(angt(alength+1|0],c;angt()
al(ac=dorth+1|0][0][0][0][Ma.split()

```

As you can see, it's mostly gibberish, but that is to be expected ;) The OP has created a JSFiddle which demonstrates that the chance of an output being syntactically valid JS is about 6.3%.

---

If self-reading functions were allowed, this could be 78 bytes of ES6:

```
f=(c="f",p=("f="+f).split(c),q=p[Math.random()*~-p.length+1|0][0])=>q?c+f(q):c

```

Very, very rarely, this outputs syntactically valid JS:

```
f=>e?c+f():c
f=>e?c=>engt():c
f=>e?c=(e):c
f=>e?c=>e=>ength.split():c
f=p=>q?c+f():c
f(q).sp=",p[Mat(q?c=(),plith.lith.sp.sp[0]).lendom().lith+f=>q=p.lendom(",p=p=>q?c+f():c
f(q),q?c=(c=(q)*~-p[0]):c
f().random(),q?c=(c=p[0]):c
f=>q?c=(q="+f"+f).rath.split(c):c
f="+1|0])=().lith.rat()*~-p=>q?c=p[Mat(c=",q?c=p.rath.splendom()*~-plength.splith.lendom(c):c

```

My favorite of the function names it's created is `.splendom()` (`split` \+ `length` \+ `random`)

# Answer
> 5 votes
## MS-DOS machine code (.COM file), 126 bytes

(A 63-byte variant would be possible if the program was allowed to read its own code.)

The first half (63 bytes) of the program are code and look like this:

```
FC BE<3F>01 AC 50 88 C2 B4 02 CD 21 E8 1A 00 59
4E AC 81 FE<7E>01 7C 03 BE<3F>01 38 C1 75 F2 FE
CA 75 EE 81 FE<3F>01 75 DB 8A 16 00 80 31 C0 8E
D8 31 C9 AC 00 C2 E2 FB 0E 1F 88 16 00 80 C3

```

The second half (63 bytes) are data and are a 1:1 copy of the code.

(In the 63-byte variant reading its own code, the bytes marked with "\<\>" have different values and the second half of the program is not present.)

I'm also not sure about the random generator's probability distribution:

The program uses the fact that the clock counters and other information modified by interrupts are stored in segment 0 to generate random numbers.

Converted to assembly code the program looks like this:

```
# 0x100:
    cld                # Ensure SI is being incremented
    mov si, programEnd # Move SI to the first byte of the copy of the program
nextOutput:
    lodsb              # Load one byte of the program ...
    push ax            # ... save it to the stack ...
    mov dl, al         # ... and output it!
    mov ah, 2
    int 0x21
    call pseudoRandom  # Create a random number (in DL)
    pop cx             # Take the stored byte from the stack
    dec si             # Go back to the last byte loaded
nextSearch:
    lodsb              # Load the next byte
                       # If we loaded the last byte ...
    cmp si, 2*programEnd-0x100
    jl notEndOfProgram # ... the next byte to be loaded ...
    mov si, programEnd # ... is the first byte of the program.
notEndOfProgram:
    cmp cl, al         # If the byte loaded is not equal to ...
                       # ... the last byte written then ...
    jne nextSearch     # ... continue at nextSearch!
    dec dl             # Decrement the random number and ...
    jnz nextSearch     # ... continue at nextSearch until the ...
                       # ... originally random number becomes zero.
    cmp si, programEnd # If the last byte read was not the last byte ...
    jnz nextOutput     # ... of the program then output the next ...
                       # ... byte!

    # Otherwise fall through to the random number generator
    # whose "RET" instruction will cause the program to stop.

    # The random number generator:
pseudoRandom:
    mov dl, [0x8000]   # Load the last random number generated
                       # (Note that this is uninitialized when
                       # this function is called the first time)
    xor ax, ax         # We use segment 0 which contains the ...
    mov ax, ds         # ... clock information and other data ...
                       # ... modified by interrupts!
    xor cx, cx         # Prepare for 0x10000 loops so ...
                       # ... all bytes in the segment are processed ...
                       # ... once and the value of SI will be ...
                       # ... unchanged in the end!
randomNext:
    lodsb              # Load one byte
    add dl, al         # Add that byte to the next random number
    loop randomNext    # Iterate over all bytes
    push cs            # Restore the segment
    pop ds
    mov [0x8000], dl   # Remember the random number
    ret                # Exit sub-routine

programEnd:
    ## Place a copy of the code as data here ##

```

# Answer
> 4 votes
# Perl 5, 81 bytes

Based on the standard quine and my answer to this question:

```
$_=q{@$=a^E;@$="\$_=q{$_};eval"=~/(?<=\Q$@\E).?/g,print$@while$@=$$[rand@$]};eval

```

Try it online!

As with the faux source code answer, this sometimes produces valid Perl, but very infrequently (\<2%):

```
$$$_=al
$_=a^E;eval
$_=al
$$=q{$$]};eval
$@=a^E;@whil
$_=q{@\E;e$]};evaleva^E;eval
$$=q{@\$_=a^E;evant$@$="=$$]};evaleval
$_=q{@whind@$_=$]};eval
$_=q{@\$@=~/(?<=\$[rilevale$=ant$[rint$_};evaleval
$_=aleval
$_=q{@$_};@whil
$$=q{@$=q{@$=\E;evand@whint$_};eva^E).?<=$=~/g,prand@$_=al"\E;e$@\E).?/g,prant$_};evaleval
$_=\$_=~/g,prind@=q{$]};@$@\Q$$$_};e$@$_=q{@$_=~/g,pril
$_=q{$=aleval"\E;evaleva^E;eva^E).?/g,pra^E;eva^E).?/(?/g,print$@$_};eval
$@=q{$_=~/(?<="\$_};eval

```

# Answer
> 4 votes
# C, 306 ~~328~~ ~~585~~ ~~611~~ ~~615~~ ~~623~~ ~~673~~ ~~707~~ bytes

Source code:

```
p[256][256]={0};char*X="p[256][256]={0};char*X=%c%s%c,Y[999],c,j,*a;main(){sprintf(Y,X,34,X,34);for(a=Y;*a;a++)p[*a][*(a+1)]++;for(j=*Y;putchar(c=j);)while(p[c][++j]<<16<rand());}",Y[999],c,j,*a;main(){sprintf(Y,X,34,X,34);for(a=Y;*a;a++)p[*a][*(a+1)]++;for(j=*Y;putchar(c=j);)while(p[c][++j]<<16<rand());}

```

With newlines and whitespace added for legibility/explanation:

```
01  p[256][256]={0};
02  char*X="p[256][256]={0};char*X=%c%s%c,Y[999],c,j,*a;main(){sprintf(Y,X,34,X,34);for(a=Y;*a;a++)p[*a][*(a+1)]++;for(j=*Y;putchar(c=j);)while(p[c][++j]<<16<rand());}",
03  Y[999],c,j,*a;
04  main(){
05      sprintf(Y,X,34,X,34);
06      for(a=Y;*a;a++)p[*a][*(a+1)]++;
07      for(j=*Y;putchar(c=j);)
08          while(p[c][++j]<<16<rand());
09  }

```

## Explanation

`Line 01`: `p[][]` holds the counts of one character following another.

`Line 02`: `X` contains the program's source, escaped with `%c%s%c`.

`Line 03`: `Y` will contain the program's literal source. `c`, `j`, `*a` are counting variables.

`Line 05`: Set `Y` to contain the quine.

`Line 06`: Count letter occurrences in `p[][]`.

`Line 07`: Print the current state.

`Line 08`: Find the next character randomly, proportional to the counts in `p[][]`.

Sample output:

`p[++);p[99]=Y;putfor(aind(a++j,*a+j=j,c][c,*an(arile(pr*Y,Y[256]<<1);)][*Y,Y;)wha+++j=*aintfor*Y;prin(a+j]=j][256<1)pr(a;a;f(p[char(Y;for());};a;ma;ma=%s%chain(Y;ar(j][256<<<1)p[256<<raile(cha][9]<rin(j,34,34,Y[256]+j,Y,34,Y,c=Y,*a;*a;for(){0}`

# Answer
> 2 votes
# Ruby, 152 bytes

```
0;s="0;s=%p<<33
0until putc($/=Hash[[*(s%%s).chars.each_cons(2)].shuffle][$/])==?"<<33
0until putc($/=Hash[[*(s%s).chars.each_cons(2)].shuffle][$/])==?!

```

Sample output:

```
0;s.c($/=Has(s).ears(2).ch[*(2)=Hacontc(2).ears.eas=Has==Hars%putc($/]).ears%sh_chuffl puns=Hachach[$/==?!

```

or

```
0;s.ch[*($/=%pufl puns($/=%s.shas($/=Harsh_chutilears)])].e]).s)=Hac($/=="<<33\ntile].chufffle][[$/=Hars%sh_c(2)=%p<<<<<33
0;s)].ears)=Hars).c(s).eacon0un0;sh_c($/][*(s.s=Hacons=?!

```

Quines using string formatting via `"s%s"`, and does the Markov chaining by taking all two-character slices, shuffling them, and turning them into a Hash dictionary, where for duplicate keys the last appearance defines the value. To avoid adding extra logic for the beginning, I track the most recently output character using `$/`, which is automatically initialized to a newline, and ensure that newlines are always followed in the code by `0`, the same character the code starts with. For the end, I manipulate the source code so that there's only one `!` so we always end after the bang, using `<<33` to add it without the literal. This could be golfed further using an unprintable single-digit character instead of ASCII 33, but that seemed too annoying.

# Answer
> 2 votes
# Rust, 564 bytes (not competitive)

```
extern crate rand;fn main(){let t=("extern crate rand;fn main(){let t=", ";let mut s=format!(\"{}{:?}{}\",t.0,t,t.1).into_bytes();s.push(0);let mut r=rand::thread_rng();let mut c=s[0];while c!=0{print!(\"{}\",c as char);let u=s.windows(2);c=rand::sample(&mut r,u.filter(|x|x[0]==c),1)[0][1];}}");let mut s=format!("{}{:?}{}",t.0,t,t.1).into_bytes();s.push(0);let mut r=rand::thread_rng();let mut c=s[0];while c!=0{print!("{}",c as char);let u=s.windows(2);c=rand::sample(&mut r,u.filter(|x|x[0]==c),1)[0][1];}}

```

Since I already had written a pretty neat Rust quine for another question, I thought I'd adapt it for this, since it seemed simple enough. While the original was small, though, for this I have made very little attempt to minimize size. Here's an expanded version to explain what's going on:

```
// Random numbers are removed from the standard library in Rust,
// I had to make a cargo project to even compile this...
// Rust is hardly a golfing language.
extern crate rand;

fn main(){

    // The quine is fairly simple, we just make a tuple with
    // "everything before this tuple" as first element, and
    // "everything after this tuple" with any quotes escaped
    // as second. That makes it really easy to print.
    let t=("[...before...]", "[...after...]");

    // Instead of printing it, we save it as a byte vector
    // and append 0
    let mut s=format!("{}{:?}{}",t.0,t,t.1).into_bytes();
    s.push(0);

    // Start with the first character
    let mut c=s[0];
    let mut r=rand::thread_rng();

    while c!=0 {
        print!("{}",c as char);

        // We slide a 2 wide window over it to save a vector
        // of all bigrams.
        let u=s.windows(2);

        // Filter it to only those which have the current character
        // as first. Take one at random, its second is our next
        // character.
        c=rand::sample(&mut r, u.filter(|x|x[0]==c), 1)[0][1];

        // Keep at it until the 0 byte is generated.
    }
}

```

Sample output 1:

```
eran(),0{ller=samarin chas c).pr,teteran mut madoletet manthilaplerng().wind_byt.wit();let.u.0][*s=[*s.plleas.wshit, rnd:Vec<_byte mputextet ut t leat=r,t rant!=r().filllet rng();lar("{}{let.ind_byt.what amusarando_ramut!=st ct!(\").0]=colet!(&lec<_ret.plec=s.whrararandormpr=saile ret=r,0]=r);le(\"),t und;fint.prilt!();ler(2).forap(&ler=s(),t ut rat mu:t=ramund:Ve s.putec==[0];wst and_byt sh(\"et c s[1), munwhras[0];c=s=s="etornws(2)[0, ain(|x|x[0,0,0];fowile c ct(&l=",tes().co_byt().wrmat ash(|x|x[*s.lethrant.wrarmu.file(\"et, r==[1);uterile().0,t ando_rinwhas=[0{}"ect.wilant!("{ple mut, mut mamprmant,0];le(&lec=s.1),t co_>=fin mamustec!(\",c=[0];}}",0];leteteat.ust(",ternwhashrarmut ler("erat,0]==file and_reter==s.utet an letet.ut=", ras.1);fin("{:?}"et t letes[*sado_bytet rnd::Verain s[0];whant(){}{}\"echin s(2);lerad;wst reth(\",t u.iletermat c 1];}{}

```

Sample output 2:

```
et!().0][0][0{}

```

# Answer
> 2 votes
# Python 2, 211 bytes

Outputs the result to `stderr`.

```
import random;X='q=[(list(t)+["$$"])[i+1]for i in range(len(t))if t[i]==c];c=random.choice(q)\nif c=="$$":exit(o)\no+=c\nexec X';s='import random;X=%r;s=%r;q=t=s%%(s,X);o=c="i";exec X';q=t=s%(s,X);o=c="i";exec X

```

**Try it online**

**Sample output:**

```
i+[(s,X)));exenit(or;q=rt(t(t(t);o='ic\n(q)+1]=c\ndor randort))\ngeno));X)\nge(st))ic]=";oic=%ran(s%%(s%rt(q)\ngexe(s=st(t[(s=[if X=%(ompoiforanom;e(t X="$"$"ic="$"i";X=c rt X

```

**Brief Explanation:**

* This program uses the `s='s=%r;print s%%s';print s%s` quine format. I create a string `s`, which will contain the entire program.
* The string `X` contains the procedure to execute recursively.
* The procedure builds the output string `o`, which will be printed to `stderr` upon reaching the end of the Markov chain.
* The end of the chain is represented by the string `$$`, using two characters so that the program will work for all strings. I could have used a character not in my program like `chr(0)`, but I think that's longer.
* The character chosen each execution is placed in `c`, which (along with `o`) is initialized to the first character of the program.
* The list of characters that follow each occurrence of choice `c` in the string `t` (the variable holding the quine of the source code) is `q`, which will be chosen from for the next selection of `c`.

# Answer
> 1 votes
## PHP, ~~144~~ ~~135~~ ~~130~~ ~~120~~ ~~272~~ ~~220~~ 212 bytes

```
<?$e='$p=$n="";foreach(str_split($s)as$w)$p=$m[$p][]=$w;do echo$n=$m[$n][array_rand($m[$n])];while("\n"!=$n);
';$s='<?$e=%c%s%1$c;$s=%1$c%s%1$c;$s=sprintf($s,39,$e,$s);eval($e);';$s=sprintf($s,39,$e,$s);eval($e);

```

Or, formatted for readability:

```
<?$e='$p = $n = "";
foreach (str_split($s) as $w) {
    $p = $m[$p][] = $w;
}
do {
    echo $n = $m[$n][array_rand($m[$n])];
} while ("\n" != $n);
';$s='<?$e=%c%s%1$c;$s=%1$c%s%1$c;$s=sprintf($s,39,$e,$s);eval($e);';$s=sprintf($s,39,$e,$s);eval($e);

```

**Sample output:**

```
<?p=')ay_r_gecorr_splililen]=$p=$w;

```

and:

```
<?p=$n=$ntststs$m[$n=$m[ay_r_chondo$n=$ph(s$nt(fitstr_r_geantentr_s('m[$n=$n"!=$p etstsp][$w;d(fililile(s$w)$nt(sphor_str_getrarast(''''m[$n='m[$m';

```

and:

```
<?p=$who eay_re($n=$n=$nt(')];d(fililileando et($m[]=$pleay_ch(')aray_ren='''))ay_st_r_s($m[$m[asp])ay_co$m[$p $phorentechitr_rean)][$n=$nd("\n"!=$n=$wh(filend('')ay_gen=$ndo$nt_rasp=$n][$p=$whp=$n='m[$n"\n)))))][$w;dorechph(';dorracho$ple_s$w;fil

```

and:

```
<?ph($n);

```

**PHP Cheating, 117**

For the curious, if we cheat by reading our own source, we can do 117:

```
<?=$p=$n='';foreach(str_split(file('m')[0])as$w)$p=$m[$p][]=$w;do echo$n=$m[$n][array_rand($m[$n])];while("\n"!=$n);

```

# Answer
> 1 votes
# Vyxal `D`, 18 bytes

```
`{Ȯq‛DĖ+$/Ḣ℅h:₴`DĖ

```

Try it Online!

## Sample outputs:

```
`{Ȯq‛DĖ
`DĖ
`{Ȯq‛DĖ+$/Ḣ℅h:₴`{Ȯq‛DĖ
`DĖ+$/Ḣ℅h:₴`{Ȯq‛DĖ+$/Ḣ℅h:₴`DĖ+$/Ḣ℅h:₴`{Ȯq‛DĖ+$/Ḣ℅h:₴`DĖ
`DĖ+$/Ḣ℅h:₴`{Ȯq‛DĖ

```

## Explanation:

```
`              `D  # push this string to the stack and triplicate => [ <code> , <code> , <code> ]
                 Ė # Execute the top => [ <code>, <code> ]
 {                 # While true
  Ȯ                # push the second to last item on the stack => [ <code> , <code> , <code> ]
   q‛DĖ+           # quote and add ‛DĖ => [ <code> , <code> , `<code>`DĖ ]
        $          # swap => [ <code> , `<code>`DĖ , <code> ]
         /Ḣ        # split and discard the first element => [ <code> , [`DĖ] ]
           ℅h      # choose at random an element and get it's first element => [ <code> , ` ]
             :₴    # duplicate and print without a newline => [ <code> , ` ]
## on loop ##
 {                 # While true
  Ȯ                # push the second to last item on the stack => [ <code> , ` , <code> ]
   q‛DĖ+           # quote and add ‛DĖ => [ <code> , ` , `<code>`DĖ ]
        $          # swap => [ <code> , `<code>`DĖ , ` ]
         /Ḣ        # split and discard the first element => [ <code> , [<code>, DĖ] ]
           ℅h      # choose at random an element and get it's first element (or error and stop the program) => [ <code> , <char> ]
             :₴    # duplicate and print without a newline => [ <code> , <char> ]

```

## Also 18 bytes

```
`q‛:Ė+:{h~/$₴Ḣ℅`:Ė

```

Try it Online!

# Answer
> 1 votes
# Julia 1.7, 103 bytes

```
(c='(';a=:((c = (q = "(c='(';a=:($(a)))|>eval")[(print(c) != 1) + rand(findall(c, q))]):eval(a)))|>eval

```

Try it online!

All those spaces are painful but necessary because the code is stored in an `Expr` (AST), which will add spaces when interpolated. Replace `print(c)` with `println(q)` to check the validity of the quine.

based on this quine:
`(a=:(print("(a=:($(a)))|>eval")))|>eval` Try it online!

# Answer
> 0 votes
# Python 3.8 (pre-release), ~~103~~ 102 bytes

```
exec(s:="from random import*;c='e'\nwhile c:print(end=c);c=choice(f'exec(s:={s!r})'.split(c)[1:])[0]")

```

Try it online!

the program stops by crashing due to an `IndexError`. To avoid crashing, `[0]` must be replaced by `[:1]` for the cost of 1 byte

## How it works?

* I started from the quine `exec(s:="print('exec(s:=%r)'%s)")`

then the core program is the following :

```
from random import*
c='e'
while c:
  print(end=c)
  c=choice('<the quine string>'.split(c)[1:])[0]

```
* I assign `c` to the first letter of our quine (`e`).

while c is not the empty string :

* I print `c`
* I randomly choose a successor of `c` beween all possible successor

to choose a successor :

* let say our string is `"abacbdeb"` and I want a successor of `'b'`:
* I split the string using `'b'` as separator : `['a','ac','de','']`
* I remove the first substing which corresponds to the char before the first occurence of `b` : `['ac','de','']`
* I take up to 1 char of these substring : `['a','d','']`

If the char is at the end of a string, it will have the empty string as potential successor and will crash the program when atempting to get its first character. It only works beacuse no char is repeated twice.

---
Tags: code-golf, quine, markov-chain
---


title: Decompress a ragged list

text:
# Question
Title: Decompress a ragged list
Your input is a ragged list of possibly empty lists of non-negative integers. For example, `[[2,0],[[]],[[[],[1],[]],[]]]` is a valid input. This input is a "compressed" ragged list. What this means is that when we have a list of numbers, we interpret those as a list of indices, indexing the output.

For example, if `I=[[2,0],[[]],[[[],[1],[]],[]]]` then the decompressed list is `O=[[[[],[[]],[]],[[]],[[[],[[]],[]],[]]]`, because if we replace `[2,0]` with `O[2][0]=[[],[[]],[]]` and `[1]` with `O[1]=[[]]` in the input list, we get `O` as the output.

The naïve method is just to have the input as a working list and then iteratively replace lists of numbers with by indexing the working list. However this runs into two potential problems:

First, consider an input like `I=[[1,0,0,0],[2],[[[[]]]]]`. Here if we index this input like so: `I[1][0][0][0]` we will get an index error. We would have to first replace `[2]` with `I[2]` giving `tmp=[[1,0,0,0],[[[[]]]],[[[[]]]]]`. Now we can replace `[1,0,0,0]` with `tmp[1][0][0][0]` giving `O=[[],[[[[]]]],[[[[]]]]]` as the output.

Another difficulty is that we can get a form of co-recursion with inputs like `[1],[[0,1],[]]`. This decompresses to `[[[],[]],[[],[]]]`

Full blown infinite recursion like `[[0]]` or `[[1],[[0],[0]]]` won't happen though.

# Rules

Your input is a ragged list `I` that may contain lists consisting of only numbers. Your task is to find a ragged list `O`, containing only lists, where if you replace every list `L` of numbers in `I` by `O[L]` you get `O` as the output. Your program must output `O`. You may assume that a unique solution exists.

You can choose between 0- and 1-based indexing. You can also choose the order of the indices, i.e. whether `[2,3,4]` corresponds to `O[2][3][4]` or `O[4][3][2]`.

This is so shortest code wins.

# Examples

```
[] -> []
[[],[[],[]]] -> [[],[[],[]]]
[[[],[]],[[0],[0]],[[1],[1]]] -> [[[],[]],[[[],[]],[[],[]]],[[[[],[]],[[],[]]],[[[],[]],[[],[]]]]]
[[[],[[],[],[[]]]],[0,1,2]] -> [[[],[[],[],[[]]]],[[]]]
[[1,0,0,0],[2],[[[[]]]]] -> [[],[[[[]]]],[[[[]]]]]
[[1],[[],[0,0]]] -> [[[],[]],[[],[]]]
[[1],[[2,0,2],[0,0],[]],[[1],[0]]] -> [[[],[],[]],[[],[],[]],[[[],[],[]],[[],[],[]]]]

```

# Answer
# JavaScript (Node.js), ~~94~~ ~~90~~ ~~87~~ ~~86~~ 85 bytes

```
f=(x,n,s=(g=y=>y[0]>=' '?n=y.map(b=>e=e[b]||0,e=x)<e.map?e:y:y.map(g))(x))=>n?f(s):s

```

Try it online!

After `y[0]>=` is U+00A0
> 3 votes

# Answer
# Python 2, 138 bytes

```
def f(x):
 def g(y):y[:]=h(x,y)if[]<y<[f]else map(g,y)*0+y
 h=lambda z,y:h(x,z+y)if[]<z<[f]else(h(z[y[0]],y[1:])if y[1:]else z[y[0]]);g(x)
```

Attempt This Online!

"Decompresses" the list in-place.

Function `g` does the main recursion. Function `h` looks ahead to resolve individual multi-step compressions where needed. The main purpose of function `f` is to put `x` in the closures of `g` and `h`.
> 1 votes

# Answer
# Clojure, 126 bytes

```
#(loop[a %](letfn[(g[x](let[y(get-in a x)](cond(=[]x)x(coll? y)y(every? coll? x)(mapv g x)1 x)))](if(= a(g a))a(recur(g a)))))

```

Try it online!
> 1 votes

# Answer
# Python3, 353 bytes:

```
from itertools import*
S=str
g=lambda x:[x]if x and int==type(x[0])else[j for k in x for j in g(k)]
def r(v,p):
 for i in p:
  try:
   l=v
   for x in i:
    l=l[x]
   v=eval(S(v).replace(S(i),S(l)))
  except:return 0
 return [0,v][all(i in'[], 'for i in S(v))]
f=lambda x:i[0]if(i:=[l for i in permutations(g(x),len(g(x)))if(l:=r(eval(S(x)),i))])else i

```

Try it online!
> 0 votes

---
Tags: code-golf, ragged-list
---


title: Write a spam-detection program

text:
# Question
Title: Write a spam-detection program
You work for a social media platform, and are told to create a program in a language of your choice that will automatically flag certain post titles as "spam".

Your program must take the title as a string as input and output a truthy value if the title is spam, and a falsey value if not.

To qualify as non-spam, a title must conform to the following rules, otherwise it is spam:

* A title can only contain spaces and the following characters: a-z, A-Z, 0-9, `-`, `_`, `.`, `,`, `?`, `!`
* A title cannot have more than one Capital Letter per word
* A title cannot have more than one exclamation mark or question mark
* A title cannot have more than three full-stops (`.`)
* A title cannot have more than one comma (`,`)

Test cases:

```
Input: How On eaRth diD tHis happeN
Output: False

Input: How on earth did this happen
Output: True

Input: How ON earth did this happen
Output: True

Input: How on earth did this happen??
Output: True

Input: How on earth did this happen?!
Output: True

Input: How on earth did this happen!!
Output: True

Input: How! on! earth! did! this! happen!
Output: True

Input: How on earth did this happen! !
Output: True

Input: How on earth did this happen?
Output: False

Input: How on earth did this happen!
Output: False

Input: How on earth did this happen...
Output: False

Input: How.on.earth.did.this.happen
Output: True

Input: How.on.earth.did this happen
Output: False

Input: How, on, earth did this happen
Output: True

Input: How, on earth did this happen
Output: False

Input: How_on_earth_did_this_happen
Output: False

Input: How-on-earth-did-this-happen
Output: False

Input: How on earth did (this) happen
Output: True

Input: How on earth did "this" happen
Output: True

Input: How on earth did 'this' happen
Output: True

Input: How on earth did *this* happen
Output: True

Input: How on earth did [this] happen
Output: True

```

# FAQ

**Q:** What is a valid title?

**A:** Single-character titles are valid. Your program has to validate a string that is not completely whitespace against the bullet-point rules above.

**Q:** What is a word?

**A:** Split the title string by a space. Each item in the resulting array is considered a word.

---

This is , so the shortest answer in bytes wins.

# Answer
# 05AB1E, ~~38~~ ~~37~~ 36 bytes

```
žj…,!?©… -.JÃÊ·IS#.uOI®S¢ā£OI'.¢;M2@

```

Try it online or verify all test cases.

**Explanation:**

```
žj              # "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_"
  …,!?          # Push string ",!?"
      ©         # Store it in variable `®` (without popping)
       … -.     # Push string " -."
           J    # Join all three strings on the stack together
            Ã   # Only keep those characters from the (implicit) input
             Ê  # Check if it's now NOT equal to the (implicit) input
              · # Double it (2 if truthy; 0 if falsey)
I               # Push the input
 S              # Convert it to a list of characters
  #             # Split it on spaces
   .u           # Check for each character if it's an uppercased letter
     O          # Sum those checks for each word
 ®S             # Push [",","!","?"] (variable `®` as list of characters)
I  ¢            # Count these characters in the input
    ā           # Push a list in the range [1,length] (without popping): [1,2,3]
     £          # Split the counts into those parts: [[a],[b,c],[]]
                # (a=count of ","; b=count of "!"; c=count of "?")
      O         # Sum each inner list: [a,b+c,0]
I               # Push the input yet again
 '.¢           '# Count the amount of "." in the input
    ;           # Halve it
M               # Push the largest number of the stack (including within lists)
 2@             # Check if this max is ≥2
                # (after which it is output implicitly as result)

```
> 4 votes

# Answer
# JavaScript (Node.js), ~~72 71 68~~ 64 bytes

-1 byte thanks to @ThisFieldIsRequired

-3 bytes inspired by @Neil's Retina answer

-2 bytes thanks to @emanresuA (see @Neil's answer)

-2 bytes by modifying final test slightly

```
m=>/[^\w-.,?! ]|[A-Z]\S*[A-Z]|[!?].*[!?]|,.*,|(\..*){4}/.test(m)

```

Try it online!

Regex abuse FTW.

Here's how it works:

* `[^\w-.,?! ]` matches any character that isn't allowed.
* `[A-Z]\S*[A-Z]` matches two uppercase letters without a space in between, i.e. two capitals in a single word
* `[!?].*[!?]` matches two exclamation/question marks with anything in between
* `,.*,` matches two commas with anything in between
* `(\..*){4}` matches four periods with anything in between

If you put these together in a single regex as alternates, you get a spam filter that matches all criteria.
> 6 votes

# Answer
# C (gcc), ~~251~~ ~~219~~ ~~215~~ ~~199~~ ~~197~~ ~~193~~ ~~189~~ ~~184~~ 181 bytes

-32 bytes thanks to @ceilingcat

-4 bytes by subtracting 43 from `c`

-16 bytes by moving comparisons inside ternaries

-2 bytes by removing unneeded brackets

-4 bytes by realising that `++x>1` is equivalent to `x++`

-4 bytes by rearranging outer ternary and adjusting subtracted amount

-5 bytes by moving checks inside loop condition

-3 bytes by using the `n` array for storing the output.

```
#define C(l,h)c>l&c<h?n[l]++
f(char*s){int c,n[64]={1};while((c=*s++)&&!(c-=41,c+9?*n=c+8&&c-22?C(55,82)<0:C(23,50):C(6,17)<0:C(4,6)>2:C(2,4):c-4&&c-54:n[1]++:(n[23]=0)));return*n;}

```

Try it online!

The C macro increments a counter for a character class. I used decimal literals instead of char literals. When a space is encountered the uppercase counter is reset.
> 6 votes

# Answer
# Retina 0.8.2, ~~55~~ ~~53~~ 51 bytes

```
[^-.,?!\w ]|[?!].*[?!]|,.*,|(\..*){4}|[A-Z]\S*[A-Z]

```

Try it online! Link includes test cases. Edit: Saved 2 bytes thanks to @Ausername and another 2 bytes thanks to @nununoisy. Simply reports on the number of banned patterns it finds, so for some spam the truthy value might be greater than `1`; if this is undesirable, `1`` can be prefixed to the program which limits the count to `1`. Explanation:

```
[^-.,?!\w ]     Check for illegal characters.
[?!].*[?!]      Check for two question or exclamation marks.
,.*,            Check for two commas.
(\..*){4}       Check for four or more full stops.
[A-Z]\S*[A-Z]   Check for two uppercase letters in the same word.

```
> 5 votes

# Answer
# Python, ~~177~~ 171 bytes

This requires the `re` module, so that adds an additional 9 bytes.

```
lambda i:any([re.search('[^a-zA-Z0-9\-.\,\?\! ]',i),*[len(re.findall("[A-Z]",w))>1for w in i.split(" ")],len(re.findall('[?!]'))>1,i.count(".")>3,i.count(",")>1])
```

Attempt This Online!
> 4 votes

# Answer
# Charcoal, 52 bytes

```
⌈⟦⊙θ¬№⁺ !,-.?_⭆⁶²⍘λφι‹¹⁺№θ!№θ?‹¹№θ,‹³№θ.⊙⪪θ ‹¹ＬΦι№αλ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for spam, nothing if not. Explanation:

```
⌈⟦

```

Output if any of the following is true.

```
⊙θ¬№⁺ !,-.?_⭆⁶²⍘λφι

```

Check whether any characters aren't contained in the permitted list including the 62 alphanumeric characters used by default for base conversion.

```
‹¹⁺№θ!№θ?

```

Check whether there is more than one exclamation or question mark.

```
‹¹№θ,

```

Check whether there is more than one comma.

```
‹³№θ.

```

Check whether there are more than three full stops.

```
⊙⪪θ ‹¹ＬΦι№αλ

```

Check whether any word has more than one upper case letter.
> 4 votes

# Answer
# Burlesque (no RegEx), ~~103~~ ~~88~~ ~~81~~ ~~76~~ 74 bytes

```
Jwd{qsnfl2.<}aljJbc".,?!"qCNZ]^p.+1<=j1<=&&j3<=&&jNBqrifn" -_.,?!"\\z?&&&&

```

Try it online!

Almost certainly a shorter answer possible. This is pretty brute force.

```
Jwd{qsnfl2.<}alj  # Check double caps

J       # Duplicate input
wd      # Split into words
{
 qsn    # isUpper
 fl     # filter length
 2.<    # <2
}       #
al      # All
j       # Swap input to top of stack

Jbc".,?!"qCNZ]^p.+1<=j1<=&&j3<=&&j  # Check char counts

J       # Duplicate input
bc      # Box and repeat infinitely
".,?!"  # String
qCN     # Count occurences
Z]      # Zip with count (return list of counts for each)
^p      # Push list to stack
.+      # Add ?s and !s
1<=j    # ?+! <= 1
1<=&&j  # , <= 1
3<=&&   # . <= 3

NBqrifn" -_.,?!"\\z?  # Check valid chars

NB          # Remove duplicates
qri         # Quoted is alphanum
fn          # Filter not
" -_.,?!"   # Valid non-letter
\\          # List diff
z?          # Empty

&&&&        # Reduce all 3 by ands

```
> 3 votes

# Answer
# JavaScript (Node.js), 132 bytes

```
n=>n.split` `.some(w=>/[^\w-.,?!]/.test(w)+(F=C=>w.split(C).length-1,c+=F`.`,d+=F(/[?!]/),e+=F`,`,F(/[A-Z]/)>1),c=d=e=0)|c>3|d>1|e>1

```

Try it online!

If you want to be completely sure that the answer works, add a backslash before the dash in the first regular expression. The code above passes all test cases, but a comment on the python answer seems to indicate that there should be a backslash or space before the dash. If anyone could confirm or disprove the statement above, it would be very helpful.
> 2 votes

# Answer
# Vyxal, ~~62~~ ~~58~~ ~~57~~ 56 bytes

```
`[^\w.,?! -]`ẎL‛?!øB?ẎL1>?⌈ƛ`[A-Z]`nẎL1>;a?\.O3>?\,O1>Wa

```

Try it Online!

My first Vyxal answer, and I'm loving this language. So much more intuitive than Jelly. 99% sure this can be golfed more.

Explanation:

```
`[^\w.,?! -]`?ẎL‛?!øB?ẎL1>?⌈ƛ`[A-Z]`nẎL1>;a?\.O3>?\,O1>Wa ; Takes the word as input
`[^\w.,?! -]`ẎL                                          ; Length of any matched of illegal characters (0 if no matches)
               ‛?!                                       ; The string '?!'
                  øB                                     ; Bracketify: converts '?!' to '[?!]'
                    ?ẎL                                  ; Find all '?' and '!' and count them
                       1>                                ; More than 1?
                         ?⌈                              ; Split the input on spaces
                           ƛ            ;                ; Mapping lambda: maps all the words using the following criteria
                            `[A-Z]`nẎL                   ; How many capital letters in the word?
                                      1>                 ; More than 1?
                                         a               ; Any truthy? (i.e. any words with more than 1 capital letter?)
                                          ?\.O           ; Count full stops in string
                                              3>         ; More than 3?
                                                ?\,O     ; Count commas in string
                                                    1>   ; More than 1?
                                                      W  ; Turn the stack into a list
                                                       a ; Any truthy? (i.e. are any of the conditions true?)

```

# Vyxal, 56 bytes

```
`[^\w-.,?! ]|[A-Z]\S*[A-Z]|[!?].*[!?]|,.*,|(\..*){4}`?ẎL

```

Try it Online!

A different version based off of the regex Node.js answer
> 2 votes

---
Tags: code-golf, string, decision-problem
---


# Question
Title: Find a factorial with n trailing zeros, quickly
## Problem

A fact you may have noticed about factorials is that as \\$n\\$ gets larger \\$n!\\$ will have an increasing number of \\$0\\$s at the end of it's base \\$10\\$ representation. In fact this is true for any base.

In this challenge you will be given a base \\$b \> 1\\$ and an integer \\$n \> 0\\$ and you will determine the smallest \\$x\\$ such that \\$x!\\$ has at least \\$n\\$ trailing \\$0\\$s in its base \\$b\\$ representation.

Of course you can easily do this by just checking larger and larger factorials. But this is super slow. The actual challenge is to do this quickly. So in order to be a valid answer you must have a worst case asymptotic complexity of \\$O(\log(n)^3)\\$ where \\$n\\$ is the number of trailing \\$0\\$s and \\$b\\$ is fixed. You should assume that *basic* arithmetic operations (addition, subtraction, multiplication, integer division, and modulo) are linear to the number of bits in the input.

This is so the goal is to minimize your source code as measured in bytes.

## Examples

For a small example if \\$b=2\\$ and \\$n=4\\$ then the answer is \\$6\\$ since \\$5!=120\\$ which is not divisible by \\$2^4=16\\$, but \\$6!=720\\$ which is divisible by \\$16\\$.

For a bigger example if \\$b=10\\$ and \\$n=1000\\$ then the answer is \\$4005\\$, since \\$4004!\\$ has only \\$999\\$ trailing zeros in base 10, and multiplying by \\$4005\\$ is obviously going to introduce another \\$0\\$.

# Answer
> 6 votes
# Python, 209 bytes

```
lambda b,n:max(h(g(b).count(s)*n,s,1)for s in g(b))
def h(n,s,*S,o=0):
 while S[-1]<n:S+=S[-1]*s+1,
 while S:*S,t=S;o+=n//t;o*=s;n%=t
 return o
g=lambda b,p=2,m=0:(b-p)*[0]and g(b,p+1)if b%p else[p]+g(b//p,p)

```

Attempt This Online!

Not very golfed yet. Hope to find time later.

`g` is based on one of @Lynn's neat tips and does prime factor decomposition of `b`. As \`b´ is fixed it is technically O(1).

The main function `f` goes through all prime factors and lets `h` compute the smallest `n` such that that prime factor occurs sufficiently often in the factorial. It then simply takes the max. As `b` is fixed the complexity is that of `h`.

`h` works on `p` the current prime factor and `n` where `n` is the requested number of trailing zeros times the multiplicity of `p` in `b`. It is easy to convince oneself that `p!` has `1` `p`,`p^2!` has `p+1` `p`s `p^3!` has `p(p+1)+1` etc. So what we want to do is something like writing `n` in the mixed base (1,p+1,p(p+1)+1,...) and then reinterpret the digits in base `p`. Which is what `h` does, though I wish I had a few more test cases.

Complexity:

Disclaimer, I always get those wrong. But if I'm not mistaken this would be O(log(n)^2) (O(log(n)) steps in the while loop and O(log(n)) digits in the arithmetic operations.

# Answer
> 6 votes
# JavaScript (Node.js), ~~136~~ ~~128~~ 117 bytes

```
b=>n=>eval("h=x=>x&&x+h(x/p);p=2n;for(e=m=0n;b>1;)if(b%p)e=p-p++;else{b/=p;for(x=n*~-p*++e;h(x++/p)<n*e;)m=m<x?x:m}")

```

Try it online!

Shortened by @Cool guy.

I'm not entirely clear about Wheat Wizard's time bound, but I think this is within it. To explain the method: the number of zeroes at the end of \\$n!\\$ in base *b* is equal to the minimum number of zeroes at the end of \\$n!\\$ in any prime power base dividing *b*, so I look at all prime powers dividing *b*, find the minimum possible *x* for all of them and take the maximum. Counting up the factors of *p* in the factors of \\$x!\\$ shows you that the number of zeroes at the end of \\$x!\\$ in a prime base *p* is $$\phi(x):=\sum\_{j\ge 1} \lfloor{\frac{x}{p^j}}\rfloor \le \frac{x}{p-1},$$ meaning that the smallest possible *x* in a prime power base \\$p^e\\$ definitely can't be any smaller than \\$n e (p-1) \\$. So, for each prime power factor \\$p^e\\$ of *b*, I start with \\$n e (p-1)\\$ and count up by ones until I find a working *x*. Since the difference between \\$\phi(x)\\$ and \\$x/(p-1)\\$ is logarithmic in *x*, and \\$\phi(x)\\$ increases by at least one when *x* is increased by *p*, only a logarithmic number of iterations are necessary. (Each iteration means recomputing \\$\phi(x)\\$, which uses \\$O(\log{x})\\$ additions and divisions by *p*.)

# Answer
> 3 votes
# JavaScript (Node.js), 118 bytes

```
n=>b=>(g=(p,k)=>b-!k?b%p?g(p+1,0,r=k&&(h=m=>H=N>=m&&(h(m*p+1)+(N-(N%=m))/m)*p)(1,N=n*k)>r?H:r):g(p,k+1,b/=p):r)(2,r=0)

```

Try it online!

Maybe \\$O(\log(n))\\$?

1. For every \\$p^k\\$ where \\$p\\$ is prime, \\$k\\$ is an integer, \\$p^k\\$ is a factor of \\$b\\$. Calculate \\$F\_p(k\cdot n)\\$ using following steps; the answer is \\$\max\\$ of all results.
2. Convert \\$k\cdot n\\$ to a strange base \\$\overline{d\_md\_{m-1}\dots d\_1}\\$ where $$ k\cdot n = \sum\_{i=1}^m\left(d\_i \cdot \frac{p^i-1}{p-1} \right) $$ $$ 0\le d\_i \le p $$ $$ d\_1=0 $$
3. Read the number \\$\overline{d\_md\_{m-1}\dots d\_1}\\$ as base \\$p\\$, while digits \\$p\\$ is treated as \\$10\_{(p)}\\$.

I know the code should be able to golf more. But the formula should just like this.

---
Tags: code-golf, math, restricted-complexity, factorial
---


title: Cubax Folding Game

text:
# Question
Title: Cubax Folding Game
Your task is to solve a new puzzle called Cubax. This toy is actually a Chinese puzzle whose expected “final” state is a simple cube. During the festivities, Cubax unfolded, because it cannot move when folded.

Cubax is composed of  smaller cubes (elements) linked together in a kind of doubly linked chain. The chain has two ends, it doesn't loop.

3 successive elements of Cubax are either:

* always aligned
* always at a right angle (90°)

Thus a simple way of defining Cubax's structure is to provide the successive number of aligned blocks, starting from the first element.

For example, representing `S` as the starting elements, `E` as the ending element and `X` as other elements, the structure defined as `332` could take any of the following 2D shapes:

```
  XE   EX
  X     X
SXX   SXX   SXX   SXX
              X     X
             EX     XE

```

Another example: `434` could be represented as:

```
S E
X X
X X
XXX

```

Note: Counting the successive the number of aligned elements implies that elements in an angle are counted twice. In the last example `434`, there are actually only `4+3-1+4-1=9` elements.

To provide the output solution, use the following rules.

For each series of aligned blocks, one character representing the direction where it has to point to is written:

* `U` Direction Up (increasing y)
* `D` Direction Down (decreasing y)
* `R` Direction Right (increasing x)
* `L` Direction Left (decreasing x)
* `F` Direction Front (increasing z)
* `B` Direction Back (decreasing z)

Considering a 3D representation (x,y,z), we will only be interested in the solutions where the first element is located at `(1,1,1)` and where the last element is located at `(N,N,N)`

Note: As a consequence, there will be no valid solution starting by `D`, `L` or `B`.

## Example

For the input `3332`, the output `RDRD` corresponds to the following planar shape:

```
SXX
  X
  XXX
    E

```

For the same input `3332`, the output `RDLU` corresponds to:

```
SXX
E X
XXX

```

## Input & Output

Your program has to read the initial shape of Cubax and provide the moves to apply so as to pack it back to a full cube of side length `N`.

You are given an integer `N`, the side length of the cube, and a string that contains a string of Blocks -\> each character providing the successive number of aligned blocks

You are to output the alphabetically-sorted list of all solutions, one solution per line

# Test cases:

```
# 2*2*2 cube

2
2222222
->
FRBULFR
FUBRDFU
RFLUBRF
RULFDRU
UFDRBUF
URDFLUR

# 3*3*3 cube

3
232333232223222233
->
FRFLUBRFDRBLBRDRUF
FUFDRBUFLUBDBULURF
RFRBULFRDFLBLFDFUR
RURDFLURBULDLUBUFR
UFUBRDFULFDBDFLFRU
URULFDRUBRDLDRBRFU

# 4*4*4 cube

4
3232242323232222222233222223422242322222222242
->
FRBULFDRBUBDBRFUFDFULBUBRDRULDFURDFLULDBLFUBRF
FUBRDFLUBRBLBUFRFLFRDBRBULURDLFRULFDRDLBDFRBUF
RFLUBRDFLULDLFRURDRUBLULFDFUBDRUFDRBUBDLBRULFR
RULFDRBULFLBLURFRBRFDLFLUBUFDBRFUBRDFDBLDRFLUR
UFDRBULFDRDLDFURULURBDRDFLFRBLURFLUBRBLDBURDFU
URDFLUBRDFDBDRUFUBUFLDFDRBRFLBUFRBULFLBDLUFDRU

```

## Others:

* You are allowed to output the moves in a string or list/array
* You are allowed to input the aligned blocks numbers via list/array as well
* You may assume there will always be at least 1 solution to the puzzle
* You are allowed to take in the input as 2 lines or on the same line as a list/array/string representation

Credits to the codingame community for the puzzle!

## Scoring

This is code-golf, so shortest code wins!

# Answer
# 05AB1E, 75 bytes

```
"BDFLRU"¹gãʒ3Å0UÝ¨3ãsÇ13%¹<øε`иε9%y*yy±*7%y83(%y%)4%<`()Xs-DU}}€`KJJ_X>²ªË*

```

Port of *@ovs*' (first) Python answer, so make sure to upvote him as well!

No TIO, since it even times out for the 2x2x2 test case. To verify it works as intended, here two separated TIOs, so both parts of the program can be verified independently:

* `"BDFLRU"¹gã`: Generate all possible move-sets that we're going to filter - try it online.
* `3Å0U²Ý¨3ã³Ç13%¹<øε`иε9%y*yy±*7%y83(%y%)4%<`()Xs-DU}}€`KJJ_X>²ªË*`: Verify a move-set (which we take as additional third input here) - try it online.

**Explanation:**

```
"BDFLRU"     # Push string "BDFLRU"
 ¹g          # Push the length of the first input-list
   ã         # Cartesian product to create all possible move-sets
ʒ            # Filter this list of strings by:
 3Å0         #  Push [0,0,0]
    U        #  Pop and store it in variable `X`
 ²Ý¨         #  Push a list in the range [0, second input-integer)
    3ã       #  Create all possible triplets of this ranged list
 s           #  Swap so the string is at the top again
  Ç          #  Convert it to a list of codepoint-integers
   13%       #  Modulo-13 each
      ¹      #  Push the first input-list again
       <     #  Decrease each of its values by 1
        ø    #  Create pairs at the same positions of these two lists
 ε           #  Map over each pair [y,z]:
  `и         #   Pop the pair, and create a list of `z` amount of `y`s
    ε        #   Map over each integer `a` in this list:
     9%y*    #    Push y%9*y
     yy±*7%  #    Push y*~y%7 (where `~` is the bitwise-NOT)
     y83(%y% #    Push y%-83%y
     )       #    Wrap all three into a list
      4%<    #    Modulo-4 and then decrement each
         `() #    Negate the last item of the triplet:
      Xs-    #    Subtract them from triplet `X` at the same positions
             #     [a,b,c] → [a-(y%9*y%4-1),b-(y*~y%7%4-1),c+(y%-83%y%4-1)]
         DU  #    Store it as new triplet `X` (without popping)
    }        #   Close the inner map
 }           #  Close the outer map
  €`         #  Flatten it one level down to a list of triplets
    K        #  Remove all those from the earlier list of triplets
     JJ_     #  Check if only [0,0,0] is left as item
 X           #  Push the final triplet `X`
  >          #  Increase each of its values by 1
   ²ª        #  Append the second input-integer
     Ë       #  Check if all four values are the same
        *    #  Check if both checks are truthy
             # (after which the filtered list of strings is output implicitly)

```
> 4 votes

# Answer
# Python, ~~269~~ ~~240~~ 232 bytes

```
from itertools import*
P=product
def f(n,q):
 for w in P(*['BDFLRU']*len(q)):x=y=z=0;{*P(*[range(n)]*3)}-{(x:=x-E%9*E%4+1,y:=y-E*~E%7%4+1,z:=z+E%-83%E%4-1)for d,p in zip(w,q)for E in[ord(d)%13]*~-p}=={(0,)*3}!=n-1==x==y==z!=print(w)
```

Attempt This Online! This is too slow for the side length 3 cube.

---

# Python, 382 bytes

Slighly optimized for speed, but still too slow to run the last case in a minute.

```
D=dict(zip('BDFLRU',zip((0,0,0,-1,1,0),(0,-1,0,0,0,1),(-1,0,1,0,0,0))))
def f(n,q):
 S=[('',a:=(0,)*3,{a})]
 for i in q:
  N=[]
  for p,w,c in S:
   for d,(X,Y,Z) in D.items():
    nc=c|c;x,y,z=w
    for _ in' '*~-i:
     x+=X;y+=Y;z+=Z;nc|={a:=(x,y,z)}
     if n<=max(a)or x|y|z<0 or a in c:break
    else:N+=(p+d,(x,y,z),nc),
   S=N
 return[p for p,(x,y,z),_ in S if x==y==z==n-1]
```

Attempt This Online!
> 5 votes

# Answer
# Python3, ~~2040~~ 1759 bytes

```
B=input();R=range;X=str.maketrans;j=None;e=sum(int(i)-1for i in B)+1;s=round(e**(1/3));l=(s**3)-1
def q(x,y,z):return x+y*s+z*s*s
class P:
 def __init__(s,x=0,y=0,z=0):s.x,s.y,s.z=x,y,z
 def q(s):return q(s.x,s.y,s.z)
 def u(s,v):return P(s.x+v.x,s.y+v.y,s.z+v.z)
 def v(f):return f.x>-1+f.y>-1+f.z>-1+f.x<s+f.y<s+f.z<s
 def I(s):
  r=[]
  for d in P(z=1),P(z=-1),P(y=1),P(y=-1),P(x=1),P(x=-1):
   n=s.u(d)
   if n.v():r+=n,
  return r
n=[0]*e;K=[{}for _ in R(e)]
def I(t):return s>t>-1
for x in R(s):
 for y in R(s):
  for z in R(s):
   p=P(x,y,z);k=p.q();n[k]=len(p.I())
   if I(x-1):K[P(x-1,y,z).q()]["R"]=k
   if I(x+1):K[P(x+1,y,z).q()]["L"]=k
   if I(y-1):K[P(x,y-1,z).q()]["U"]=k
   if I(y+1):K[P(x,y+1,z).q()]["D"]=k
   if I(z-1):K[P(x,y,z-1).q()]["F"]=k
   if I(z+1):K[P(x,y,z+1).q()]["B"]=k
class A:
 def __init__(s,f=j):
  if f:s.E=f.E[:];s.b=f.b;s.N=f.N[:];s.y=f.y;s.g=f.g;s.f=f.f;s.G=f.G
  else:s.E=[0]*e;s.b=e;s.N=n[:];s.G=j;s.y=0;s.e();s.g=0;s.f=""
 def w(s):return A(f=s)
 def t(s,h):
  for c in h:
   s.f+=c;a=[int(c)-1for c in B][s.g];s.g+=1
   for _ in R(a):
    try:s.y=K[s.y][c];s.e()
    except:return
   return 1
 def l(s):return s.b<1
 def e(s):
  k=s.y
  if s.E[k]:g
  s.E[k]=1
  if s.G==k:s.G=j
  elif s.G!=j:g
  s.N[k]=0;s.b-=1;h=K[k]
  for d in h:
   k=h[d]
   if not s.E[k]:
    n=s.N[k]
    if k!=l+n<3:
     if s.G!=j:g
     s.G=k;s.N[k]=n-1
   if s.b>=1and s.E[l]:g
def p(_,z,N):
 N+=1
 for C in{"L":"BDFU","R":"BDFU","U":"BFLR","D":"BFLR","F":"DLRU","B":"DLRU"}[_]:
  c=z.w()
  if c.t(C):
   if c.l():m.append(c.f)
   else:p(C,c,N)
*m,N=0,;S=A()
S.t("FU")
p("U",S,N);T="FBLRUD"
for s in m[:]:m+=s.translate(X(T,"FBDURL")),
for s in m[:]:m+=s.translate(X(T,"UDLRFB")),;m+=s.translate(X(T,"RLBFUD")),
print("\n".join(sorted(m)))

```

Try it online!

-18 thx to @Unrelatedstring

-65 thx to @TheFifthMarshal

-1 thx to @AidenChow
> 4 votes

---
Tags: code-golf, array, puzzle-solver
---