title: Implement the Zundoko Kiyoshi function

text:
# Question
Title: Implement the Zundoko Kiyoshi function
## Background

The Zundoko Kiyoshi function originates from this tweet by kumiromilk. Translated from Japanese, it reads roughly as follows:

> The test for my Java lecture had a problem that said "Implement and describe your own function". I made it continuously output either "zun" or "doko" randomly; if the sequence "zun", "zun", "zun", "zun", "doko" appears, it outputs "ki-yo-shi!" and terminates. Then I got full marks and earned a unit.

This is in reference to Kiyoshi Hikawa's song Kiyoshi no Zundoko Bushi: when he sings the aforementioned line, the crowd cheers "ki-yo-shi!" in response.

## Task

Write a program or function that takes no input and replicates the behavior outlined in the tweet:

* Repeatedly output either `zun` or `doko`, choosing uniformly randomly each time.
* If the sequence `["zun", "zun", "zun", "zun", "doko"]` appears in the output, output `ki-yo-shi!` and halt.

Example output:

```
doko
zun
zun
doko
doko
zun
zun
zun
zun
zun
doko
ki-yo-shi!

```

## Rules

* This is , so shortest answer in bytes wins.
* Your output can be a list of strings, or each string printed with some delimiter.
* Your output has to be non-deterministic.

# Answer
> 4 votes
# Jelly, 36 bytes

```
2Xµị“zun“doko”Ṅȧ;ɼḄß“ki-yo-shi!”%?32

```

A full program which takes no input and prints as it runs.

**Try it online!**

### How?

```
2Xµị“zun“doko”Ṅȧ;ɼḄß“ki-yo-shi!”%?32 - Main Link (no arguments)
2                                    - literal two
 X                                   - random number in [1..x] -> z = 1 or 2
  µ                                  - start a new monadic chain, f(z)
    “zun“doko”                       - list of strings = ["zun", "doko"]
   ị                                 - index into -> v = "zun" or "doko"
              Ṅ                      - print v and a newline and yield v
               ȧ                     - (v) logical AND (z) -> z
                 ɼ                   - recall from the register (initially 0), apply
                                     -     the following and store the result back
                                     -     into the register:
                ;                    -   concatenate
                  Ḅ                  - convert from base-2 (e.g. [0,2,1,1,1,1,2] -> 96
                                     -     since 0×2⁶+2×2⁵+1×2⁴+1×2³+2×2²+1×2¹+2×2°=96)
                                 ?   - if...
                                % 32 - ...condition: modulo 32 (is non-zero)
                   ß                 - ...then: call this Link again (Main Link)
                    “ki-yo-shi!”     - ...else: string "ki-yo-shi!"
                                     - implicit print

```

# Answer
> 12 votes
# JavaScript (ES6), 72 bytes

```
f=x=>x%17^2?['doko ','zun '][j=Math.random()*2|0]+f(x<<7|j):'ki-yo-shi!'

```

Try it online!

### How?

We keep track of the last 5 words in a 32-bit integer stored in \\$x\\$ (which is initially undefined). At each iteration, we left-shift it by 7 positions and set the LSB to \\$0\\$ for *doko* or \\$1\\$ for *zun*.

The sequence *zun, zun, zun, zun, doko* results in:

```
x = **1**000000**1**000000**1**000000**1**000000**0**
```

or \\$270549120\\$ in decimal, which is the only value for which we have \\$x\equiv 2\pmod{17}\\$, as shown in this table. This is our halt condition.

# Answer
> 8 votes
# 05AB1E, ~~54~~ ~~50~~ 44 ~~43~~ ~~42~~ ~~39~~ 37 bytes

```
[.•BΓßb¥•#TΩDˆè¯J30bÅ¿#}"ki-yo-shi!"»

```

Try it online!

~~I doubt string compression is going to help here. Prove me wrong.~~ It did help. -5 thanks to @Kevin

Forgive me, Adnan, for writing such a long program.

## Explained (old)

```
[1ÝΩ

```

First of all, we start an infinite loop, generate the range `[0, 1]` and pick a random object from that list.

```
D

```

We then duplicates that random number for later use.

```
.•BΓßb¥•#

```

Next, we push the compressed string "doko zun" and split it upon spaces.

```
sè,

```

Then, we swap that splitted string and the randomly generated number from earlier and index the string at that position. `,` prints the word to STDOUT.

```
ˆ¯5.£J

```

Here's where the fun begins. After the indexing and printing, we are left with the original random number on the stack. We append it to the global array and then push the global array to obtain the last 5 items from the list. This will be a string of 1s and 0s. The joining is simply to mould the list into a single string.

```
30b

```

We then convert the number 30 into its binary representation: 11110. This represents four zuns followed by a doko, as that's the order they appear in the compressed string from earlier.

```
Q#]

```

Then, we check to see if the last 5 items (which we joined into a string) is equal to the binary of 30. If it is, the infinite loop will stop, moving on to the next step. Otherwise, the above steps are repeated again.

```
"ki-yo-shi!",

```

At this stage, the loop has finished, meaning all that is left to do is print the required end string.

# Answer
> 7 votes
# C#, ~~347~~ ~~255~~ ~~170~~ ~~119~~ ~~115~~ 92 Bytes

```
for(int k=3;k!=1;Write(k%2<1?"zun ":"doko "))k=k<<7^new Random().Next(2);Write("ki-yo-shi!")

```

# Explanation

```
// Only every 7th bit changes
// k is set to three so that the code won't terminate until
// at least 5 shifts have occured
// Terminate when k is one
// so that every 7th bit matches 00001
for(int k=3;k!=1;){
    k=k<<7;
    // Shift the bits in k
    k=k^new Random().Next(2);
    // Set the last bit to random value
    Write(k%2<1?"zun ":"doko ")
    // Output zun or doko based on last bit
//zun = 0, doko = 1. kiyoshi = 00001
}
//we only get here if we have 00001
Write("ki-yo-shi!")

```

Try it online!

~~Added a TIO link and also saved almost 100 bytes :) (Not counting the `class Program` \+ `static void Main()` declarations and also implied `using System`).~~

~~My friends and I went back and forth with what I had originally and ended up with this. Basically cut the bytes in half. You can potentially run out of memory in the rare scenario that you never get a kiyoshi but whatever.~~

Thanks to Kevin and monicareinstate in the comments, this is now 119 bytes. Using the interactive compiler instead you can put functions outside of the main function and it implies `using`.

Last edit: we got this to 92 bytes! Can't even believe it given how verbose C# is.

# Answer
> 6 votes
# Pyth, 44 ~~42~~ ~~40~~ 38 bytes

```
Wn30i>5Y2%2>"dzoukno"eaYO2;"ki-yo-shi!

```

Try it online!

**Approach**: Repeatedly generate a random number from the set {0, 1} using `O2`. Store that number in the array `Y` and use it to index into the string `"dzoukno"` (which is `"zun"` and `"doko"` interleaved). Once the last five elements of `Y` are `[1,1,1,1,0]`, break the loop and print `"ki-yo-shi!"`.

# Answer
> 6 votes
# K4, ~~56~~ ~~48~~ ~~47~~ 46 bytes

**Solution:**

```
{x,1?$`zun`doko}/[75-2/:<-5#;()],,"ki-yo-shi!"

```

**Example:**

```
q)k){x,1?$`zun`doko}/[75-2/:<-5#;()],,"ki-yo-shi!"
"doko"
"zun"
"doko"
"doko"
"doko"
"doko"
"doko"
"doko"
"doko"
"zun"
"zun"
"zun"
"zun"
"zun"
"zun"
"doko"
"ki-yo-shi!"

```

**Explanation:**

Generate `zun` or `doko` and append to a list whilst the distinct set of the last 5 elements aren't `zun zun zun zun doko`, and add `ki-yo-shi!` to the end.

Indices to order `zun zun zun zun doko` ascending are `4 0 1 2 3`. Converted from base-2 yields 75. Other combinations will not yield the same result.

```
{x,1?$`zun`doko}/[75-2/:<-5#;()],,"ki-yo-shi!" / solution
                                 ,"ki-yo-shi!" / 1-item list of "ki-yo-shi!"
                                ,              / append to
{              }/[          ;  ]               / {function}/[while;starting value]
                             ()                / empty list
                         -5#                   / take last 5 elements
                        <                      / indices to sort ascending
                     2/:                       / convert from base 2
                  75-                          / subtract from 75
     $`zun`doko                                / string ($) -> ("zun";"doko")
   1?                                          / choose (?) 1 item from domain ("zun";"doko")
 x,                                            / append to input

```

**Extra:**

* **K (oK) TIO** for **47 bytes** as we need an extra set of brackets but can drop a colon...

# Answer
> 5 votes
# Python 2, ~~102 101 97 95 92~~ 91 bytes

*-3 bytes thanks to @dingledooper !*
*Thanks @JhynjhiruuRekrap for reminding that Python source code can include unprintable characters!*
*Thanks @xnor for saving 1 byte!*

```
import os
s=1
while~s%32:s+=s-(os.urandom(1)>"");print"dzoukno"[~s%2::2]
print"ki-yo-shi!"

```

Try it online!

Stores the history as bits in the integer s, where 0,1 corresponds to "zun" and "doko". Each time, shift `s` by 1, then subtract the new bit. Stops when the lowest 5 bits of s are 11111, aka `~s%32 == 0`.

Generates a random 0 or 1 by generating a random byte, then checking if the byte is more than 127.

```
 os.urandom(1)>"{unprintable DEL character}"

```

# Answer
> 4 votes
# APL (Dyalog Classic), 54 bytes

```
({⍵⌷'zun' 'doko'}¨⍪∘?∘2⍣{1 1 1 1 2≡¯5↑⍺}⍬)'ki-yo-shi!'

```

Try it online!

## Explanation

```
({⍵⌷'zun' 'doko'}¨⍪∘?∘2 {1 1 1 1 2≡¯5↑⍺} )'ki-yo-shi!'
                                        ⍬              ⍝ Start with an empty list

                       ⍣                               ⍝ Do this until the condition turns true:
                  ⍪∘?∘2                                ⍝ Append a random number in [1..2]
                        {1 1 1 1 2≡¯5↑⍺}               ⍝ Condition: The list ends in "1 1 1 1 2"

                 ¨                                     ⍝ For every item in this list:
 {⍵⌷'zun' 'doko'}                                      ⍝ 1-Index into the list ['zun','doko']

(                                        )'ki-yo-shi!' ⍝ After that: Append the string 'ki-yo-shi!'
                                                       ⍝ To the end of the output list

```

# Answer
> 3 votes
# PowerShell, 67 bytes

```
do{random($a=,'zun'*4+'doko')-ov +o}until("$o"-match$a)'ki-yo-shi!'

```

Try it online!

Unrolled:

```
do{
    $array=,'zun'*4+'doko'          # 'zun','zun','zun','zun','doko'
    random $array -OutVariable +out # choose one element from the array randomly. 'doko' may appear in 20% of cases. it's still random.
                                    # output a result to the output channel (console by default) AND to the variable $out.
                                    # '+out' means adding to $out instead of replacing of $out
                                    # see https://docs.microsoft.com/en-us/powershell/module/microsoft.powershell.core/about/about_commonparameters
}until("$out" -match $array)        # powershell casts the $array to a string implicitly
'ki-yo-shi!'

```

# Answer
> 3 votes
# Ruby, ~~71...59~~ 57 bytes

*-4 bytes thanks to @ValueInk!*

```
$/+=p %w[zun doko].sample until$/=~/n.{9}d/;p'ki-yo-shi!'

```

Try it online!

Stores output history by appending `zun` or `doko` to the string `$/` (the predefined input record separator). Halts when the string contains an `n`, followed by exactly 9 characters, followed by a `d`. This can only occur when the string ends with `zu**n**zunzunzun**d**oko`.

# Answer
> 3 votes
# Retina, 50 bytes

```
/(n¶.+){4}o$/^+?(`\z
zun¶
)`\z
doko¶
\z
ki-yo-shi!

```

Try it online! Explanation:

```
/(n¶.+){4}o$/^+

```

Repeat until the buffer ends with 4 lines ending with `n` and a line ending in `o`. Note that the `$` anchor works like `\Z` or `¶?\z`, so I don't need to match the trailing newline explicitly.

```
?(`
)`

```

Execute one of the inner stages chosen randomly.

```
\z
zun¶
\z
doko¶

```

Append either `zun` or `doko`. Note that I can't use `$` here as I only want to match the very end and the `$` would match before the final newline as well as after it.

```
\z
ki-yo-shi!

```

Finally append `ki-yo-shi!`.

# Answer
> 3 votes
My first attempt at a golf, and using a language not remotely suited for golfing, no less! ~~I can't think of any ways to shrink this~~ because Lua is a verbose, spacey language. But I still love her anyways.

I should give a heads-up: when the Lua interpreter starts, its pRNG seed seems to always default to the same value (rather than polling `/dev/random` or something), so running it once will always provide the same result. TIO, therefore, creates the same output repeatedly. This will change when 5.4 is released.

Credits to manatwork for a 22% reduction over four changes.

# Lua, ~~132~~ ~~123~~ ~~107~~ ~~104~~ 103 bytes

```
z=0repeat if math.random(2)<2then print"zun"z=z+1 else w=z>3z=0print"doko"end until w print"ki-yo-shi!"

```

Try it online!

Explanation, because why not?

```
z=0                           --set a variable to count consecutive "zun"s
repeat                        --loop until we hit the target circumstance
    if math.random(2)<2 then  --pick 1 or 2: 1 = "zun", 2 = "doko"
        print"zun"            --print "zun"
        z=z+1                 --increment the "zun" counter
    else                      --when the pRNG lands 2
        w=z>3                 --after 4 consecutive "zun"s, w will be false
        z=0                   --reset the counter
        print"doko"           --print doko
    end
until w                       --loop kills when w is defined (as true)
                              --execution only gets here if we succeed...
print"ki-yo-shi!"             --...so print "ki-yo-shi!" and halt

```

# Answer
> 2 votes
# C (gcc), ~~104~~ \\$\cdots\\$ ~~96~~ 91 bytes

Saved 2 bytes thanks to Arnauld!!!

Saved a byte thanks to tsh!!!

Saved 5 bytes thanks to ceilingcat!!!

```
f(m){srand(time(0));for(m=3;m%32-1;m+=m+puts(rand()%2?"doko":"zun")-4);puts("ki-yo-shi!");}

```

Try it online!

**How**

\\$m\\$ stores a history of what's randomly been printed over time in its bits, the least-significant bit storing the most recent. A bit in \\$m\\$ at time \\$t\\$ is set to:

$$ m\_t = \left\\{ \begin{array}{ll} 0 & \text{zun} \\ 1 & \text{doko} \end{array} \right. $$ When the binary pattern \\$00001\_2\\$ occurs in the least-significant \\$5\\$ bits of \\$m\\$ the sequence \\$(\text{zun}, \text{zun}, \text{zun}, \text{zun}, \text{doko})\\$ has just appeared. \\$m\\$ is initialised to \\$11\_2\\$ so, at the beginning, it appears as though \\$(\text{doko},\text{doko})\\$ has just occurred forcing at least \\$5\\$ spins before \\$00001\_2\\$ can occur.

# Answer
> 2 votes
# Java 10, ~~148~~ ~~141~~ ~~137~~ ~~136~~ ~~125~~ ~~123~~ ~~112~~ ~~110~~ 107 bytes

```
v->{var r="";for(int k=3;k!=1;r+=k%2<1?"zun/":"doko/")k=k<<7^(int)(Math.random()*2);return r+"ki-yo-shi!";}

```

Golfed version of the approach that *@loohhoo* used in her C# answer.
-4 bytes thanks to *@ceilingcat*.
An additional -11 bytes from *@loohhoo*'s new approach (after I helped her golf it a bit), so make sure to upvote her if you haven't already!
-11 bytes by porting *@Arnauld*'s JavaScript answer (thanks to *@OlivierGrégoire*)
And yet another -3 bytes thanks to *@loohhoo*'s third new approach, haha ;D

Uses `/` instead of newlines as delimiter.

Try it online.

**Explanation:**

```
v->{                      // Method with empty unused parameter and String return-type
  var r="";               //  Result-String, starting empty
  for(int k=3;            //  Bit-mask integer
      k!=1;               //  Loop as long as `k` is not 1 yet:
      ;                   //    After every iteration:
       r+=k%2<1?          //     If `k` is even:
           "zun/"         //      Append "zun" and a "/" to the result
          :               //     Else (`k` is odd):
           "doko/")       //      Append "doko" and a "/" to the result
    k=                    //    Change `k` to:
      k<<7                //     First bit-wise left-shift it by 7
      ^(int)(Math.random()*2);
                          //     And then bitwise-XOR it with a random 0 or 1
  return r                //  Return the result-String
          +"ki-yo-shi!";} //  appended with "ki-yo-shi!"

```

# Answer
> 2 votes
# Python 2, 94 bytes

```
from random import*
s=""
while"zo">s[-21::19]:s+=choice(["zun,","doko,"])
print s+"ki-yo-shi!"

```

Try it online!

This is an improvement based on an older version of Surculose Sputum's answer.

The idea is to identify the ending sequence in the comma-separated string by checking that the 21st and 2nd characters from the end are `z` and `o` respectively.

```
...,zun,zun,zun,zun,doko,
    ^                  ^
    z                  o

```

This is the only ending that satisfies this. To get a `z` in the 21st-to-last position, the last five words must be exactly four `zun,` and one `doko,`, since their lengths of 4 and 5 can add up to 21 only as `4*4+5`. Then, the one `doko,` must be at the end to get `o` in the second-to-last position. Moreover, because `zo` is the largest string that could be made here, we can check inequality with `<` rather than `!=`, saving a byte.

It would be shorter to use `urandom` similarly to Surculose Sputum's new answer.

# Answer
> 2 votes
# Julia 1.0, 92 bytes

A simple recursive implementation. `i` keeps track of how often "zun" has occured.

```
f(i=0)=(r=rand(1:2);println([:zun,:doko][r]);r>1 ? i>3 ? print("ki-yo-shi!") : f() : f(i+1))

```

Try it online!

# Answer
> 2 votes
# Zsh, 83 bytes

```
>zun>doko
49744()<<<ki-yo-shi!>>*
*(){`sum<<<$@`||$@ `ls|shuf -n1|tee -a *`}
z* * *

```

Try it online!

Outputs to the files named `zun` and `doko` (both should be identical).

* `>zun>doko` \- create the files `zun` and `doko`
* `49744()` \- define a function called `49744`
    + `<<<ki-yo-shi!` \- output `ki-yo-shi!`
    + `>>*` \- append to all files
* `*(){}` \- define a function with the names of all the files in the current directory (i.e. `zun` and `doko`)
    + `sum<<<$@` \- take the checksum of the arguments
    + ```` \- try to execute that as a command
        - the checksum of `zun zun zun doko` is `49744`, which is defined as a command. All other combinations are not.
    + `||` \- if that fails (i.e. the arguments are not `zun zun zun doko`):
        - `ls` \- list all files in the current directory
        - `shuf -n1` \- pick one item at random
        - `tee -a *` \- append to all the files in the current directory, as well as being captured by the ````
        - ```` \- then pass that as the last argument to:
            * `$@` \- execute the arguments: the first argument is the command to execute, the remaining ones are passed as arguments. Since the first argument is always either `zun` or `doko`, this actually recurses, passing all but the first argument, with the new random string appended.
* `z* * *` \- initial recursive call - call the function with the name "all files that start with `z`" (i.e. `zun`),
    + `* *` \- with the arguments "all files" and "all files" (i.e. `doko zun doko zun`)

# Answer
> 2 votes
# VBScript, 257 bytes

```
Randomize():z="zun,":d="doko,":Do:a=a&Array(z,d)(Round(Rnd())):Loop While UBound(Split(a,","))<5:Do:a=Split(a,","):a(0)="a":a=Replace(Join(a,",")&Array(z,d)(Round(Rnd())),"a,",e):MsgBox a:Loop While Not Cbool(Instr(a,"zun,zun,zun,doko,")):MsgBox"ki-yo-shi!"

```

# Answer
> 1 votes
# Raku, 61 bytes

```
(<doko zun>[{^2 .pick}...{:2[@_]%32==30}],'ki-yo-shi!')».say

```

Try it online!

# Answer
> 1 votes
# Charcoal, 38 bytes

```
Ｗ›⁴⌕✂υ±⁵Ｌυ¹doko⊞υ‽⪪dokozun⁴υki-yo-shi!

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｗ›⁴⌕✂υ±⁵Ｌυ¹doko

```

Repeat until the string `doko` is the last of the last 5 strings in the initially empty list (thus the first four must all be `zun`)...

```
⊞υ‽⪪dokozun⁴

```

... split the string `dokozun` into substrings of length at most 4 and push one randomly to the list.

```
υki-yo-shi!

```

Output the list and `ki-yo-shi!`. (Charcoal automatically outputs each list element on its own line.)

# Answer
> 1 votes
# ~~161~~ ~~143~~ 69 bytes

An initial & fairly clumsy attempt at a code golf challenge involving text!, and defining

`b=c("doko","zun")`

as a header.

`for(i in -3:which(apply(matrix((a<-sample(0:1,2e5,r=T))[outer(1:5,1:1e5,"+")],5)*2^(0:4),2,sum)==15)[1])cat(b[1+a[i+5]],"\n")
cat("ki-yo-shi!")`

Try it online!

Using the original Japanese characters with

`b=c("ドコ","ズン")`

and

`cat("キヨシ!")`

brings the score down to 137 bytes...

> A better alternative to using `cat(` would be appreciated as the `,"\n"` part wastes 5 bytes for a `newline` command.

A different approach reducing the count

```
e=0
while(e<1){x=rt(1,1)<0)
cat(b[1+x],"\n")
e=e*x-x+(!x&-3>e)}
cat(a)

```

when adding

```
a="ki-yo-shi!"

```

to the header.

Try it online!

# Answer
> 1 votes
# Wolfram Language, 109 bytes

```
Join[NestWhile[#~Join~{RandomChoice@{z,d}}&,{},#[[-5;;]]=!={z,z,z,z,d}&]/.z->"zun"/.d->"doko",{"ki-yo-shi!"}]

```

Try it online!

Pretty straightforward: randomly appends `z` or `d` to a list until the last five elements match `{z,z,z,z,d}`, converts each to the proper string, then appends `"ki-yo-shi!"`.

# Answer
> 1 votes
# ThumbGolf, 53 bytes

Machine code (little endian pairs):

```
2100 de78 0840 bf2c a008 a009 4149 de00
de3a f001 011f 291e d1f3 a001 de00 4770
696b 792d 2d6f 6873 2169 000a 757a 006e
6f64 6f6b 00

```

Commented assembly:

```
        // Include ThumbGolf wrapper macros
        .include "thumbgolf.inc"
        .globl main
        .thumb_func
main:
        // Set our counter bitmask to zero
        movs    r1, #0
.Lloop:
        // Store a 32-bit random integer into r0.
        rand    r0
        // Using lsrs, test the lowest bit.
        lsrs    r0, r0, #1
        // Set up an IT block, checking the carry flag set from lsrs
        ite     cs
          // If the lowest bit was 1, set r0 to "zun"
          adrcs r0, .Lzun
          // Otherwise, set it to "doko"
          adrcc r0, .Ldoko
        // Add to the bitmask using adcs.
        // r1 = r1 * 2 + (rand() & 1)
        adcs    r1, r1
        // Print the string in r0
        puts    r0
        // Print a newline. We could technically put the newline in the strings
        // themselves for a THEORETICALLY identical byte count, but the true
        // reason for this (and the main reason I added this instruction) is to
        // make it so the string literals are aligned, preventing wide ADR.
        putspc  '\n'
        // Mask the lowest 5 bits using wide AND
        and     r1, r1, #0b11111
        // 0b11110 means zun zun zun zun doko, loop while it is not that
        cmp     r1, #0b11110
        bne     .Lloop
.Lloop.end:
        // Print "ki-yo-shi!"
        adr     r0, .Lkiyoshi
        puts    r0
        // Return
        bx      lr
        // These string literals are very carefully placed so that they are
        // all 4 byte aligned. That is the only reason for the trailing newline:
        // it makes kiyoshi an even multiple of 4 bytes.
.Lkiyoshi:
        .asciz "ki-yo-shi!\n"   // 12 bytes (aligned)
.Lzun:
        .asciz "zun"            // 4 bytes (aligned)
.Ldoko:
        .asciz "doko"           // 5 bytes (aligned)

```

Output is to stdout.

It wasn't easy figuring out how to align my string literals, but it was definitely worth it.

<sub>Note that I created ThumbGolf after this question was submitted.</sub>

# Answer
> 1 votes
# Pxem, 66 bytes (filename).

Unprintables are as a backslash followed by its code point in three-digit octal.

```
\001.t.z\002.r.wzun.p.m\001.+.t\001o.r.ao.zdok.p.m\004.xki-yo-shi!.p.d.a\001.tXX.a.a

```

## With comments

```
XX.z
# heap: 1 as counter
.a\001.t.zXX.z
  # choosing either zun or doko
  .a\002.r.wXX.z
    .azun.pXX.z
    # increment counter
    .a.m\001.+.tXX.z
    # push o for next dot-z and get out
    .a\001o.r.aXX.z
  # if empty; then push o and get in
  # else pop it and ignore next block
  .ao.zXX.z
    # reusing the o
    .adok.pXX.z
    # print kiyoshi and exit if counter is >4
    .a.m\004.xki-yo-shi!.p.d.aXX.z
    # else reset counter to 1
    .a\001.tXX.aXX.z
# pop a garbage of an o if any
.a.a

```

Try it online!

# Answer
> 1 votes
# Ly, 96 bytes

```
"ki-oy-shi!">"okod">"nuz">666661[p09?5Gfps[p<0]p<0&:p[o](10)opl[p>0]p>l:rp&s&+lr2=fp*[<<<&o;]p1]

```

Try it online!

This code uses 4 stacks, one for each of the output lines, and one holding `0|1` indicators of the last 4 output choices (picked using random numbers). Then it writes the `ki-oy-shi!` line and exits if the sum of the choices (and last choice) show that the exit pattern was generated.

```
"ki-oy-shi!">"okod">"nuz">       # Push the strings onto separate stacks
66666                            # Initialize the stack to a "not done" state
1[p    ...code...    1]          # An infinite loop pattern
09?5Gfp                          # Pushes 0|1 on the stack randomly
       s                         # Save the choice on the backup stack
        [p<0]p<                  # Shift 1 or 2 stacks, depending on random choice
               0&:p              # Duplicate the stack with a 0 sep, pop the top 0
                   [o](10)op     # Print one copy of the stack, plus LF, pop the 0
l[p>0]p>                         # Restore random choice, shift back 1 or 2 stacks
        l:                       # Restore random choice, duplicate it on stack
          rp                     # Reverse the stack, delete top (remove oldest choice)
            &s&+l                # Save stack, sum the choices, restore stack
                 r2=fp           # Reverse stack to move sum on top, compare to 2
                      *          # Combine with latest choice, if 1 we are done
                       [<<<&o;]  # Time to go, switch stacks, print and exit
                               p # Delete the test results from the stack, then loop...

```

# Answer
> 1 votes
# Vyxal `o`, 36 bytes

```
{₀℅:£J:5NȯB30≠«ǎ⌈8τ«½¥i,|}`ki-yo-∪Ǎ!

```

Try it Online!

-7 thanks to lyxal.

# Answer
> 0 votes
# APL (Dyalog Unicode), 51 bytes

```
(⌷∘'zun' 'doko'¨⍪∘?∘2⍣{(2,⍨4/1)≡¯5↑⍺}⍬)'ki-yo-shi!'

```

Try it online!

Slight improvement on the other solution, since the account is deleted.

# Answer
> 0 votes
# Knight, 54 bytes

```
;=aF;W-30;O I=x%R2"zun""doko"=a%+x*2a 32xO"ki-yo-shi!"

```

Try it online!

Uses the bitmask setup.

```
# Initialize with FALSE. We will coerce it to
# Number later, just get some form of 0.
; = mask FALSE
# loop while mask != 30
; WHILE( - 30
          # chaining ftw
          ; OUTPUT
             : IF (= x % RAND 2){"zun"}{"doko"}
          # mask = ((mask << 1) | x) % 32
          : = mask % (+ x (* 2 mask)) 32
        ) {
    : NOP # we use "x" in the golfed code.
}
: OUTPUT "ki-yo-shi!"

```

---
Tags: code-golf, string, random
---


# Question
Title: Largest Number with No Repeating Digit Pairs
*Inspired by the problem with the same name on Puzzling SE by our very own Dmitry Kamenetsky.*

You are to find the largest number that only uses every digit pair once, in a given base. For example, in ternary we have 2212011002.

**Challenge:** Given a base from 2-10, output the largest number in that base with no repeating digit pairs.

As long as the digits make the number, you may output with anything, or nothing, in between. Whether regularly delimited, or irregularly gibberished.

You may also take input in any reasonable way. For example, you might take the base, the max digit, or an ordered list representing the digits available. For octal, this would mean `8`, `7` or `76543210`. If you feel like a challenge, you can take `octal` as input. I won't complain!

Note that it need only work for bases from 2-10. Invisible points for doing alphanumeric bases like hex, but not at all required.

This is , so least bytes *per language* wins.

#### Test Cases

```
Decimal: 10
99897969594939291908878685848382818077675747372717066564636261605545352515044342414033231302212011009

Octal: 8
77675747372717066564636261605545352515044342414033231302212011007

Quaternary: 4
33231302212011003

Ternary: 3
2212011002

Binary: 2
11001

```

**Edit:** It used to be required for bases 1-10, with the desired output for unary being `00`. However, that was just an obfuscating edge case in some cases when people wanted to manipulate natural numbers. So unary has been dropped; only bases 2-10 required.

# Answer
> 8 votes
# Jelly,  ~~8~~  7 bytes

-1 thanks to Neil (avoid a reverse by reordering to flatten first.)

```
Żj)ŻFṚ;

```

A monadic Link accepting the maximal digit (e.g. `7` for octal) that yields the digits as a list of integers.

**Try it online!**

### How?

Note that if `x` is the base then the least significant (rightmost) digit of `f(x)` is `x-1`, the previous digits are the same as all but the last digit of `f(x-1)` and the digits before that are:
`[x-1, x-1, x-2, x-1, x-3, x-1, x-4, x-1, ..., 0]`, so...

```
Żj)ŻFṚ; - Link: non-negative integer, M (max digit = base - 1)
  )     - for each (x in [1..M]):
Ż       -   zero-range    -> [0,1,2,3,...,x]
 j      -   join (x)      -> [0,x,1,x,2,x,3,x,...,x]
   Ż    - prepend a zero  -> [0,[0,1,1],[0,2,1,2,2],[0,3,1,3,2,3,3],...]
    F   - flatten         -> [0,0,1,1,0,2,1,2,2,0,3,1,3,2,3,3,...]
     Ṛ  - reverse         -> [...,3,3,2,3,1,3,0,2,2,1,2,0,1,1,0,0]
      ; - concatenate (M) -> [...,3,3,2,3,1,3,0,2,2,1,2,0,1,1,0,0,M]

```

# Answer
> 6 votes
# , ~~61~~ ~~52~~ 51 bytes

*Edit: -9 bytes, and then -1 more byte, thanks to Robin Ryder*

```
for(i in 1:scan())F=c(i,rbind(i,i:1-1),F);c(F,F[1])

```

Try it online!

# Answer
> 5 votes
# Japt, ~~14~~ 11 bytes

```
Çò qZÃ¬Ô+´U
Ç           // Exclusive range [0..U) where U is the input, mapped to
 ò          // inclusive range [0..Z] of each item Z
   qZ       // joined together by Z.
     Ã¬Ô    // Join and reverse the result, then
        +´U // append input minus one.

```

Try it here.

# Answer
> 4 votes
# JavaScript (ES6), 55 bytes

```
n=>(g=p=>p--?p+(h=q=>q--?[p]+q+h(q):'')(p)+g(p):~-n)(n)

```

Try it online!

# Answer
> 3 votes
# Jelly, 12 bytes

```
,€`€j0ṚF;Ø0;

```

Try it online!

Takes `base - 1` for input, so `7` for octal. Does not work for unary, as permitted.

```
,€`€j0ṚF;Ø0;  Main Link
   €          For each x from 1 to N
  `           Apply the following to (x, x) rather than (x, N):
 €            - For each y from 1 to x
,             - (y, x)
    j0        Join the list of sublists of pairs on 0
      Ṛ       Reverse the whole thing
       F      Flatten
        ;Ø0   Append 2 zeroes
           ;  Append the input

```

# Answer
> 3 votes
# Jelly, 11 bytes

```
;€`Ṛ)ŻṚj0F;

```

Try it online!

A monadic link taking the max digit and returning a list of digits. Works for unary as well.

## Explanation

```
    )       | For each digit from 1 up to the argument:
;€`         | - Concatenate each digit from 1 to that digit together
   Ṛ        | - Reverse
     Ż      | Prepend zero
      Ṛ     | Reverse
       j0   | Join with zeros
         F  | Flatten
          ; | Concatenate to original argument

```

# Answer
> 3 votes
# Ruby, ~~56~~ 53 bytes

```
->n{(?0..n="#{n}").map{|m|[*?0..m]*m}.join.reverse+n}

```

Try it online!

# Answer
> 2 votes
# Python 3, 97 bytes

```
def f(x):
	k=[]
	for i in range(x,0,-1):k+=sum([[i-j,i]for j in range(i)],[])+[0]
	return k+[0,x]

```

Try it online!

fixed thanks to Jakque

Takes `base - 1` for input, so `7` for octal. Does not work for unary, as permitted.

# Answer
> 2 votes
# Vyxal, 16 bytes

```
ʁ?²›↔'₌ḢṪZ:U⁼;tṅ

```

Try it Online!

Sorry about that. I wayyyy misinterpreted the question.

##### Explanation:

```
ʁ?²›↔'₌ḢṪZ:U⁼;tṅ    # main program

ʁ                   # range 0 to n-1
 ?²›                # base^2 + 1
    ↔               # combination w/ replacement
     '₌ḢṪZ:U⁼;      # filter lambda
      ₌ḢṪ           # a[1:], a[:-1]
         Z          # zip
          :U⁼       # check if the zip is unique
              tṅ    # tail joined by ""

```

This is really slow, so it will only finish for n \<= 3 probably, but it works in theory.

# Answer
> 2 votes
# Husk, ~~15~~ ~~13~~ 11 bytes

*Edit: -2 bytes thanks to Razetime*

```
↔:¹ṁSoJ←ŀḣ→

```

Try it online!

```
↔:¹ṁSoJ←ŀḣ→ # Full program:
   ṁS       # map across
         ḣ→ # each integer n from 1 to input plus 1:
        ŀ   # integers from zero to n,
     oJ←    # joined-together using n plus 1;
 :¹         # then, prefix this with the input,
↔           # and reverse it all.

```

# Answer
> 2 votes
# Charcoal, 13 bytes

```
⮌⁺⊖θ⭆Ｎ⪫…·⁰ιＩι

```

Try it online! Link is to verbose version of code. Takes `b` as input. Works for `b=1`. Explanation:

```
     Ｎ          Input `b`
    ⭆           Map over implicit range and join
       …·⁰ι     Inclusive range from 0 to current index
      ⪫         Joined with
            ι   Current index
           Ｉ    Cast to string
 ⁺              Prefixed with
   θ            Input `b`
  ⊖             Decremented
⮌               Reverse
                Implicitly print

```

# Answer
> 2 votes
# Retina 0.8.2, 51 bytes

```
.+
$*
1
$`¶
¶$

1
$.%_

$.%`
^(.*¶)*
$#1$&
¶

O$^`.

```

Try it online! Link includes test suite that generates results for `b=1..10`. Explanation:

```
.+
$*

```

Convert to unary.

```
1
$`¶

```

List the values from `0` to `b-1` (in unary).

```
¶$

```

Delete the trailing newline that the previous stage generates.

```
1
$.%_

```

Replace each `1` with its line number, so now we have a triangle of digits where there are `n` digits `n` on each line.

```

$.%`

```

Intersperse the digits from `0` to `n` around the existing digits `n`.

```
^(.*¶)*
$#1$&

```

Insert an extra digit `b-1` at the beginning.

Join everything together.

```
O$^`.

```

Reverse the string.

# Answer
> 2 votes
# 05AB1E, ~~13~~ 10 bytes

*-3 thanks to ovs.*

```
ÝεÝy.ý}˜Rš

```

Try it online! Takes input as the maximum digit in the base, and outputs as a strangely arranged list of numbers - this is allowed, since

> As long as the digits make the number

it is valid.

```
ÝεÝy.ý}˜Rš  # full program
         š  # prepend...
        R   # reversed...
       ˜    # flattened...
Ý           # [0, 1, 2, ...,
            # ..., implicit input...
Ý           # ]...
 ε          # with each element replaced by...
  Ý         # [0, 1, 2, ...,
            # (implicit) ..., current element in map...
  Ý         # ]...
    .ý      # joined by...
   y        # current element in map...
         š  # to...
            # implicit input
      }     # exit map
            # implicit output

```

# Answer
> 2 votes
# Python 3, 52 bytes

```
f=lambda a,*b:(b and a+a+a.join(b)+f(*b)[:-1]or a)+a

```

Try it online!

* Take as inputs each individual available digits in descending order.
* Bonus: Base 0 works perfectly fine, so does other bases like Hexadecimal (as long you provide the digits available)

## How it works:

Let say your digits are `"43210"`, the expcted result should be `4(4)3(4)2(4)1(4)0__3(3)2(3)1(3)0__2(2)1(2)0__1(1)0__0__[4]`

* We can see that each segent contains the numbers up to a certain point separated by the leading number.
* These segments repeat in decending order
* The first number is added at the end

From that I construct the recursive program :

* `f=lambda a,*b:`: definition of the function, each individual digit in descending order. Store the first in `a` and the other in `b`
* `b and ... or a` if the digits is just `"0"`, `b` is empty and the expression will be equal to `"0"`, else it will be equal to `...`
* `a+a+a.join(x)+f(b)[:-1]`, return the string of the available digits separated by the first element (`a`), then recurse over the available digits the first element. Then remove the last digit of it.
* `return(...)+a` add the first element of `x` to the result. The previous `[::-1]` is to remove this char from the recursive call but not from the main call.

# Answer
> 1 votes
# Pip, 15 bytes

```
@ORV:0\,_J_MJ,a

```

Try it online!

### Explanation

We construct (most of) the number backwards and then reverse it:

```
                                                      Current value         Output
              a  The base, given via command-line     3
             ,   Range(^)                             [0 1 2]
           MJ    Map this function...
     0\,_          Inclusive-range(0, arg)            [[0] [0 1] [0 1 2]]
         J_        joined on arg                      [0 011 02122]
                 ... and join the results as string   001102122
  RV:            Reverse                              221201100
 O               Output without a newline             221201100             221201100
@                Get the first character              2                     221201100
                 (Autoprint)                                                2212011002

```

# Answer
> 1 votes
# *Acc!!*, 100 bytes

```
N-48
Count i while _+1-i {
Count j while _-i-j {
Write _-i-j+48
Write _-i+48
}
Write 48
}
Write _+48

```

Takes input as (base - 1). Try it online!

### Explanation

```
N-48                     # Input a digit and store its value in the accumulator
Count i while (_+1)-i {  # Loop i from 0 through (acc + 1) - 1
                         #   acc - i is the recurring digit in this block
Count j while (_-i)-j {  # Loop j from 0 through (acc - i) - 1
                         #   acc - i - j is the changing digit in this block
Write (_-i-j)+48         # Write the changing digit
Write (_-i)+48           # Write the recurring digit
}
Write 48                 # End the block with a 0
}
Write _+48               # End the number with a final digit of (base - 1)

```

---
Tags: code-golf, number, sequence, sorting, permutations
---


title: Create Word Lightning

text:
# Question
Title: Create Word Lightning
Sandbox

Inspired by a Codingame challenge I tried (and failed at) about a month ago.

Given a binary tree of words, say:

```
             HELLO
            /     \
        WORLD     EATING
        /         /   \
     ARCH     IDAHO   GUARD
                      /
                   DOOZY
                   /
                ZEPPELIN
                 /    \
             POWER   LIGHT

```
1. Take the root of the tree.
2. Print it in the South direction.

```
H
E
L
L
O

```
3. For each of the tree's children, given iteration index i:
    1. Find the first character in the child that it has in common with the root. If there are multiple occurrences of that character in the root, choose the first occurrence as the join point.
    2. The drawn root word will have to intersect the child at this point.
    3. Draw the left node down to the left, and the right node down to the right.

```
   H
   E
   LA
   LWT
   O  I
  R    N
 L      G
D

```
4. Now, for each of the diagonal words' children, do the same, except always print downward.

```
   H
   E
   LA
   LWT
  AO  I
  R   DN
 LC   A G
D H   H U
      O A
        R
        D

```
5. Go back to step3 and perform the steps again until the tree is complete.

```
   H
   E
   LA
   LWT
  AO  I
  R   DN
 LC   A G
D H   H U
      O A
        R
        D
       O
      O
     Z
    YE
     P
    OP
   W E
  E  L
 R   II
     N G
        H
         T

```

## Clarifications

* No two child words will have the same first common letter.
* Words from different subtrees will never intersect.
* Input will always be a valid binary tree.
* Each parent will always have a common character with both of its children.
* Trees can be taken in any suitable and reasonable format for your language.
* Leading and trailing whitespace is allowed, so long as the structure of the lightning is as shown.
* All words will be given in the same case.

# Testcases

```
PROGRAMMING
|
CHALLENGES
|         \
PUZZLES    CODING

```

```
       P
       R
      PO
      UG C
      ZRHO
      ZA D
      LM I
     LEM N
    E SI G
   N   N
  G    G
 E
S

```

---

```
DIGERIDOO
|        \
GIRDLE    ORNATE
|         |     \
EXQUISITE ROLL   TALONS
|       \
QUEEN    TAPESTRY
         |       \
         PASTE    YELLOW
         |
         ERROR

```

```
         D
         I
         G
        IE
       R R
      D  I
     L   D
    E    O
    X    OR
    Q     ON
   UU     L A
  E I     L  T
 E  S        AE
N   I        L
    T        O
    EA       N
      P P    S
       EA
        S
        TT
        E R
       R   Y
      R    E
     O     L
    R      L
           O
           W

```

# Answer
> 7 votes
# Charcoal, 88 bytes

```
↓§θ⁰⊞υ⁺Ｅ³¦⁰θＦυ«≔¬§ι⁰ηＦΦι›λ³«≔§κ⁰ζ≔§Φζ№§ι³λ⁰εＪ§ι¹§ι²Ｍ⌕§ι³ε✳⁻⁶§ι⁰Ｍ⌕ζε✳⁻²η⊞υ⁺⟦ηⅈⅉ⟧κ✳⁻⁶ηζ≦±η

```

Try it online! Link is to verbose version of code. Explanation:

```
↓§θ⁰

```

Print the first word vertically.

```
⊞υ⁺Ｅ³¦⁰θＦυ«

```

Start a breadth-first traversal of the tree, but prefixing three status variables to each entry for the coordinates and the direction.

```
≔¬§ι⁰η

```

Get the direction of the previously printed word and flip it to 0 (which will become downwards) if it was non-zero or 1 (which will become down left) if it was zero.

```
ＦΦι›λ³«

```

Loop over any child nodes.

```
≔§κ⁰ζ

```

Get the current node's word.

```
≔§Φζ№§ι³λ⁰ε

```

Find the first letter in its word that's shared with its parent's word.

```
Ｊ§ι¹§ι²Ｍ⌕§ι³ε✳⁻⁶§ι⁰Ｍ⌕ζε✳⁻²η

```

Jump to the parent's start, then move to the parent's shared letter, then work back to where this branch's word needs to start.

```
⊞υ⁺⟦ηⅈⅉ⟧κ

```

Concatenate this word's position and direction with the node and push that to the list of nodes to traverse.

```
✳⁻⁶ηζ

```

Print the node's word in the appropriate direction.

```
≦±η

```

Flip the direction in case this word was printed down left and there's a sibling node still to print.

---
Tags: code-golf, ascii-art, binary-tree
---


title: A multiple of n in every base!

text:
# Question
Title: A multiple of n in every base!
In November 2019, Alon Ran published a particularly lovely sequence in the OEIS, A329126:

> \\$a(n)\\$ is the lexicographically earliest string of digits which yields a multiple of \\$n\\$ when read in any numeric base. `1, 110, 101010, 111100, 100010001000100010, 1111110, 10000010000010000010000010000010000010, 11111111000, 1010101010101010100, ...`

For example, \\$a(3) = 101010\\$ because this is the smallest number that is a multiple of \\$3\\$ in every integer base $$ \begin{alignat}{2} 101010\_1 &= 1^5 + 1^3 + 1^1 = 3 &&= 3\cdot1 \\ 101010\_2 &= 2^5 + 2^3 + 2^1 = 42 &&= 3\cdot14 \\ 101010\_3 &= 3^5 + 3^3 + 3^1 = 273 &&= 3\cdot91 \\ 101010\_4 &= 4^5 + 4^3 + 4^1 = 1092 &&= 3\cdot364 \\ 101010\_5 &= 5^5 + 5^3 + 5^1 = 3255 &&= 3\cdot1085 \\ &\hspace{0.4em}\vdots \end{alignat} $$ Another way of conceptualizing this is that the polynomial \\$f(n) = n^5 + n^3 + n\\$ is divisible by \\$3\\$ for every integer \\$n\\$, which you can check manually with modular arithmetic.

---

We can generalize this idea further by looking at polynomials with restricted coefficients. For example, if we allow the coefficients of the polynomial to be \\$\\{-1,0,1\\}\\$, then \\$g(n) = n^4-n^2\\$ is divisible by \\$4\\$ for all integers \\$n\\$.

---

## The challenge!

In any reasonable format of your choosing, you will be given a list of allowed integer coefficients, `coefficients` (which always contains both \\$0\\$ and \\$1\\$), and a positive integer, `k`.

Your job is to find the degree, `d`, of the smallest monic polynomial as measured by degree, $$ p(n) = n^d + c\_{d-1}n^{d-1} + \dots + c\_2n^2 + c\_1n + c\_0, $$ such that each \\$c\_i\\$ is in `coefficients` and \\$p(n)\\$ is a multiple of \\$k\\$ for all integers \\$n \in \mathbb{Z}\\$.

In order to avoid the simplest form of brute-forcing, your program must be able to compute each individual test case from the test data on TIO (or, if TIO does not support your language, on my machine within 60 seconds). This is , so shortest code wins.

## Test data

```
coefficients | k | d  | example
-------------+---+----+--------------------------------------------
[0,1]        | 1 | 0  | 1
[0,1]        | 2 | 2  | x^2  + x
[0,1]        | 3 | 5  | x^5  + x^3  + x
[0,1]        | 4 | 5  | x^5  + x^4  + x^3  + x^2
[0,1]        | 5 | 17 | x^17 + x^13 + x^9  + x^5  + x
[0,1]        | 6 | 6  | x^6  + x^5  + x^4  + x^3  + x^2  + x
[0,1]        | 7 | 37 | x^37 + x^31 + x^25 + x^19 + x^13 + x^7 + x
[-1,0,1]     | 4 | 4  | x^4  - x^2
[-1,0,1]     | 5 | 5  | x^5  - x
[-1,0,1]     | 6 | 3  | x^3  - x
[-1,0,1]     | 7 | 7  | x^7  - x
[-1,0,1]     | 8 | 5  | x^5  - x^3
[-1,0,1]     | 9 | 8  | x^8  - x^6  - x^4 + x^2
[ 0,1,2]     | 4 | 4  | x^4  + x^2  + 2x
[ 0,1,3]     | 5 | 9  | x^9  + x^5  + 3x
[ 0,1,2,3]   | 6 | 3  | x^3  + 3x^2 + 2x

```

# Answer
> 4 votes
# Haskell, 221 bytes

```
import Data.Set
k%g|w<-fromList.fmap(\q->(`mod`k).sum.zipWith(*)q.(<$>[1..]).(^)<$>[1..k]).mapM id=[n|n<-[0..],t<-[div n 2],n>(k-1)^2||size(intersection(w$(0-)<$>g<$[1..t])$w$([0]<$[1..t])++(g<$[1..n-t-1])++[[1]])>0]!!0

```

Use compiler flags `-O2` (I didn't test if `-O` is enough. It might be)

To get the result, evaluate `k%digits`, e.g, `6%[0,1]`. Here's a link to TIO with a `main` function that runs all the tests, except `7%[0,1]`:

Try it online!

The code works by generating all the negations of the possible first halves of the polynomial, and all the possible second halves of the polynomial. Then it evaluates all of them `mod k` at all possible inputs, puts the results in two sets, and checks if they have any intersection.

It also has two spot optimizations: the constant coefficient is always zero, and a polynomial of degree `k^2-2k+2` is always possible.

The code doesn't run to completion on the TIO site. however, it reached 30s on my computer. So I'm waiting for the OP to decide if this program is ok. Also, there is a slightly shorter but less performant version that also might make the cut:

```
import Data.Set
k%g|w<-fromList.fmap(\q->(`mod`k).sum.zipWith(*)q.(<$>[1..]).(^)<$>[1..k]).mapM id=[n|n<-[0..],t<-[div n 2],size(intersection(w$(0-)<$>g<$[1..t])$w$([0]<$[1..t])++(g<$[1..n-t-1])++[[1]])>0]!!0

```

that removes the `k^2-2k+2` optimization.

# Answer
> 8 votes
# Python 3.8+, ~~385~~ 372 bytes

```
from itertools import*
E=enumerate
def f(c,k):
 p=[range(k)]
 while(n:=[a*b%k for a,b in E(p[-1])])not in p:p+=n,;S=[{0}];M=[D:=0]*len(p)
 for d in range(k*k):
  if[]==p[D:]:D=p.index(n)
  if any(all(sum(s)%k<1for s in zip(*T))for T in product(*[[[P*(C+(i==D))for P in p[i]]for C in S[r]]for i,r in E(M)])):return(k!=1)+d
  S+=[{a+b for b in S[-1]for a in c}];M[D]+=1;D+=1

```

Try it online!

This code is surprisingly fast and runs in only about 1.5s on TIO.

*-12 bytes thanks to @ovs*

Python 3.8+ is used for the walrus operator (`:=`), but it costs three bytes because Python 3 doesn't allow mixed tabs and spaces.

## How

A naive way to go about the challenge is to test all possible coefficient combinations at a given degree, then proceed to the next degree. This is viable for all of the test cases except for `[0,1] | 7`, which requires degree `d=37`. This would require brute-forcing more than `2^37` combinations, even if the order is chosen intelligently.

My next approach was to work out what possible sums could be obtained for each `n` then work backwards on sets of coefficients which work for those sums, but that ran into much of a similar problem.

Since only that one test case fails, it would be possible to optimize for coeffs=`[0,1]` specifically, but that seems too cheaty / against the spirit of the challenge.

The method used in this answer relies on the property that the powers of `n` (mod `k`) are periodic, at least after a certain point. As an example for `k=4`:

```
Table of n^i mod k for k=4
i=0 corresponds to the constant term

n\i 0 1 2 3 4 5 6 7 8 9
0   1 0 0 0 0 0 0 0 0 0
1   1 1 1 1 1 1 1 1 1 1
2   1 2 0 0 0 0 0 0 0 0
3   1 3 1 3 1 3 1 3 1 3

```

Thus the powers mod `4` overall have a period of length `2` starting from `i=1`. (Note that `i=0` is never a solution unless `k=1`, and the constant term should always be divisible by `k`, so it should normally be zero).

We use this periodicity to our advantage. For example, in the `[0,1] | 7 | 37` case, we don't need to consider `37` exponents. The powers have a period of length `6` starting from `i=0`, so there are only `6` distinct tuples of residues of of powers.

```
Table of n^i mod k for k=7
i=0 corresponds to the constant term

n\i 1 2 3 4 5 6  7 8 9
0   0 0 0 0 0 0  0 0 0
1   1 1 1 1 1 1  1 1 1
2   2 4 1 2 4 1  2 4 1
3   3 2 6 4 5 1  3 2 6
4   4 2 1 4 2 1  4 2 1
5   5 4 6 2 3 1  5 4 6
6   6 1 6 1 6 1  6 1 6

```

We only need to consider the coefficients with which to weight the six columns `i∊[1...6]`. Now we have to be careful. The coefficients are not just chosen from `[0,1]`. As we proceed to higher degrees, we can reuse the coefficients, so for example the `n` term is the same as the `n^7` term is the same as the `n^13` term; these all have powers in the `1` column. Thus we can use `7` copies of the `1` column to obtain the desired polynomial.

## Ungolfed Code

```
import itertools

def min_degree(coeffs, k):
    if k == 1:
        return 0
    # powers[n-1] will be the tuple of [1...k]^m mod k
    # e.g. for k=4, powers=[(1,2,3),(1,0,1),(1,0,3)]; next power will be (1,0,1) which repeats
    powers = [tuple(range(1, k))]
    # keep computing more powers until two are the same,
    # (we know the sequence of powers must be periodic eventually)
    while (
        next_power := tuple([a * b % k for a, b in enumerate(powers[-1], 1)])
    ) not in powers:
        powers.append(next_power)
    # period_start_index is 0-indexed
    # for k=4, period_start_index=1 and period_length=2
    period_start_index = powers.index(next_power)
    period_length = len(powers) - period_start_index
    # summed_coeffs[i] is all possibilities of sums of i coeffs with replacement.
    # for example for i=2 and coeffs=[0,1,3], summed_coeffs[i]={0,1,2,3,4,6}={0+0,0+1,1+1,0+3,1+3,3+3}
    summed_coeffs = [{0}]
    for i in range(k * k):
        # mod by k here is unnecessary but can theoretically improve speed
        summed_coeffs.append({(a + b) % k for b in summed_coeffs[-1] for a in coeffs})
    max_repeats = [0 for _ in powers]
    # A simple upper bound for d is d ≤ k*φ(k)
    # because Σ_{m=1}^{k}(n^(mφ(k)) always works
    # Since φ(k) ≤ k-1, we know d ≤ k*φ(k) ≤ k*(k-1) < k*k
    for d in range(1, k * k):
        # degree_index is the index of [1...n]^(d-1) mod k in the list `powers`
        # we use d-1 because the `d`-th coefficient must be 1 ∵ monic polynomial
        degree_index = (
            d - 1
            if d - 1 < period_start_index
            else period_start_index + (d - 1 - period_start_index) % period_length
        )
        possible_column_totals = [
            [
                tuple(
                    [p * (coeff + (1 if i == degree_index else 0)) for p in powers[i]]
                )
                for coeff in summed_coeffs[r]
            ]
            for i, r in enumerate(max_repeats)
        ]
        max_repeats[degree_index] += 1
        for column_totals in itertools.product(*possible_column_totals):
            if all(sum(s) % k == 0 for s in zip(*column_totals)):
                return d

```

# Answer
> 4 votes
# JavaScript (ES6),  ~~297 290 286~~  284 bytes

Expects `(coefficients)(k)`.

```
c=>k=>(g=(i,q,d,A,m,h)=>i<n?c.map(c=>c*q&&i>=r|!m&&g(i,q-1,(D=m-~i)>d?D:d,A.map((v,j)=>v+B[i][j]*c),m+n-r,D>d?c:h),g(i+1,q,d,A,0,h)):M=h^!A.some(x=>x%k)|M<d?M:d)(0,k,0,(M=A=>(r=M[A+A])?A.fill(!r--):M(A.map((v,i)=>v*i%k),M[A+A]=n=B.push(A)))([...Array(k)].map((_,i)=>i),B=[]),0)&&M^k<2

```

Try it online!

## Commented

I think this is very close to @fireflame241's solution, although I came up with this independently. The first part was working fine from the beginning. But for some reason, I got the second part poorly written and very slow on my early attempts.

### Step 1

We store in \\$B\[\\:\]\\$ all the distinct tuples \\$(0,1,\dots,k-1)\\$ raised to increasing powers, modulo \\$k\\$. At the end of the process, \\$n\\$ is the number of entries in \\$B\[\\:\]\\$ and \\$r\\$ is the 0-based index at which the sequence restarts.

```
( M = A =>            // M is a recursive function taking a vector A[]
  (r = M[A + A]) ?    // if A[] was already encountered at index r:
    A.fill(!r--)      //   stop the recursion, clear all values in A[]
                      //   and decrement r
  :                   // else:
    M(                //   do a recursive call:
      A.map((v, i) => //     update each value in A[] ...
        v * i % k     //       ... to the next power modulo k
      ),              //     end of map()
      M[A + A] = n =  //     store A[] in M, set n = length of B[] ...
      B.push(A)       //     ... once A[] has been appended to B[]
    )                 //   end of recursive call
)(                    // initial call to M with:
  [...Array(k)]       //   an array filled with all values from 0 to k - 1
  .map((_, i) => i),  //
  B = []              //   initialize B[] to an empty array
)                     //

```

### Step 2

We now use a recursive function \\$g\\$ to find a combination of tuples from \\$B\[\\:\]\\$ multiplied by some coefficients from \\$c\[\\:\]\\$ that sum up to \\$0\\$'s modulo \\$k\\$. We eventually return the lowest degree \\$M\\$ of the corresponding polynomials, ignoring those that are not monic.

By using any tuple that repeats, it's always possible to build a solution with exactly \\$k\\$ terms that lead to the same result modulo \\$k\\$. That's why we use \\$k\\$ as an upper bound for the number of terms in the polynomial.

The initial call to \\$g\\$ is `g(0, k, 0, A, 0)` and the returned value is `M ^ k < 2` to support the edge case \\$k=1\\$.

```
g = (                        // g is a recursive function taking:
  i,                         //   i = pointer in B[]
  q,                         //   q = max. number of terms in the polynomial
  d,                         //   d = degree
  A,                         //   A[] = current vector, initialized to the
                             //         array of k 0's, returned by step 1
  m,                         //   m = number of times B[i] has been used
  h                          //   h = coefficient of the leading term
) =>                         //
  i < n ?                    // if i is less than n:
    c.map(c =>               //   for each coefficient c in c[]:
      c * q &&               //     if both c and q are not 0
      i >= r | !m &&         //     and B[i] can be repeated or m = 0,
      g(                     //     do a recursive call:
        i,                   //       leave i unchanged
        q - 1,               //       decrement q
        (D = m - ~i)         //       D is the degree of the new term
        > d ? D : d,         //       update d to D if D > d
        A.map((v, j) =>      //       update A[]:
          v + B[i][j] * c),  //         add B[i][j] * c to each A[i]
        m + n - r,           //       add the period to m
        D > d ? c : h        //       update the coeff. of the leading term
      ),                     //     end of recursive call
      g(                     //     do another recursive call with:
        i + 1, q, d, A, 0, h //       i + 1, m = 0
      )                      //       all other parameters unchanged
    )                        //   end of map()
  :                          // else (i = n):
    M = h ^                  //   if the leading coeff. is not equal to 1
        !A.some(x => x % k)  //   or some value in A[] is not 0 modulo k
        | M < d ? M          //   or M is less than d, leave M unchanged
                : d          //   else update it do d

```

---
Tags: code-golf, combinatorics, base-conversion, polynomials
---


title: ASCII Art of the Day #1 - Double Knot

text:
# Question
Title: ASCII Art of the Day #1 - Double Knot
Write a full program or a function that takes a positive integer `N` as input via STDIN/command line/ARGV or function arguments and prints an ASCII double knot corresponding to the `N` to STDOUT.

The ASCII double knot looks like this:

```
  __  __  __  __  __  __
 /  \/  \/  \/  \/  \/  \
| /\/ /\/ /\/ /\/ /\/ /\ |
| \/ /\/ /\/ /\/ /\/ /\/ |
 \ \/\ \/\ \/\ \/\ \/\ \/
 /\ \/\ \/\ \/\ \/\ \/\ \
| /\/ /\/ /\/ /\/ /\/ /\ |
| \/ /\/ /\/ /\/ /\/ /\/ |
 \__/\__/\__/\__/\__/\__/

```

The above is for `N = 6`

Here are a few more double knots for other values of `N`:

If `N = 1`, the output double knot looks like:

```
  __
 /  \
| /\ |
| \/ |
 \ \/
 /\ \
| /\ |
| \/ |
 \__/

```

For `N = 2`, its

```
  __  __
 /  \/  \
| /\/ /\ |
| \/ /\/ |
 \ \/\ \/
 /\ \/\ \
| /\/ /\ |
| \/ /\/ |
 \__/\__/

```

For `N = 3`, its

```
  __  __  __
 /  \/  \/  \
| /\/ /\/ /\ |
| \/ /\/ /\/ |
 \ \/\ \/\ \/
 /\ \/\ \/\ \
| /\/ /\/ /\ |
| \/ /\/ /\/ |
 \__/\__/\__/

```

and similarly, the pattern continues and any larger value of `N`.

**Details**:

* The input is always a positive integer greater than `0`.
* Trailing newline is optional
* There should either be no trailing spaces in each line, or enough trailing spaces such that each row's length is `4*N + 2`.
* There should never be any leading space that aren't part of the specified pattern.

This is , so shortest code in bytes wins.

---

# Series Leaderboard

I am converting this into a series of ASCII art challenges and thus adding a leader board for the series (snippet by Martin). To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
/* Configuration */

var QUESTION_IDs = [50484, 50521, 50625, 51123, 51222]; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!.FjwQBrX2KXuFkv6p2lChi_RjzM19";

/* App */

var answers = [], page = 1, currentQ = -1;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_IDs.join(";") + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function getAnswers() {
  $.ajax({
    url: answersUrl(page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      if (data.has_more) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SIZE_REG = /\d+(?=[^\d&]*(?:<(?:s>((?!>).)*<\/s>|((?!>).)+>)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^\n,]+)(?=,)/;//

function shouldHaveHeading(a) {
  var pass = false;
  var lines = a.body_markdown.split("\n");
  try {
    pass |= /^#/.test(a.body_markdown);
    pass |= ["-", "="]
              .indexOf(lines[1][0]) > -1;
    pass &= LANGUAGE_REG.test(a.body_markdown);
  } catch (ex) {}
  return pass;
}

function shouldHaveScore(a) {
  var pass = false;
  try {
    pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
  } catch (ex) {}
  if (!pass) console.log(a);
  return pass;
}

function getAuthorName(a) {
  return a.owner.display_name;
}

function getAuthorId(a) {
  return a.owner.user_id;
}

function process() {
  answers = answers.filter(shouldHaveScore)
                   .filter(shouldHaveHeading);
  answers.sort(function (a, b) {
    var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
        bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
    return aB - bB
  });

  var users = {};
  answers.forEach(function (a) {
    var headline = a.body_markdown.split("\n")[0];
    var question = QUESTION_IDs.indexOf(a.question_id);
    var size = parseInt((headline.match(SIZE_REG)||[0])[0]);
    var language = headline.match(LANGUAGE_REG)[1];
    var user = getAuthorName(a);
    var userId = getAuthorId(a);
    if (!users[userId]) users[userId] = {name: user, nAnswer: 0, answers: []};
    if (!users[userId].answers[question]) {
      users[userId].answers[question] = {size: Infinity};
      users[userId].nAnswer++;
    }
    if (users[userId].answers[question].size > size) {
      users[userId].answers[question] = {size: size, link: a.share_link}
    }
  });

  var sortedUsers = [];
  for (var userId in users)
    if (users.hasOwnProperty(userId)) {
      var user = users[userId];
      user.score = 0;
      user.completedAll = true;
      for (var i = 0; i < QUESTION_IDs.length; ++i) {
        if (user.answers[i])
          user.score += user.answers[i].size;
        else
          user.completedAll = false;
      }
      sortedUsers.push(user);
    }

  sortedUsers.sort(function (a, b) {
    if (a.nAnswer > b.nAnswer) return -1;
    if (b.nAnswer > a.nAnswer) return 1;
    return a.score - b.score;
  });

  var place = 1;
  for (var i = 0; i < sortedUsers.length; ++i) {
    var user = sortedUsers[i];
    var row = '<tr><td>'+ place++ +'.</td><td>'+user.name+'</td>';
    for (var j = 0; j < QUESTION_IDs.length; ++j) {
      var answer = user.answers[j];
      if (answer)
        row += '<td><a href="'+answer.link+'">'+answer.size+'</a></td>';
      else
        row += '<td class="missing"></td>';
    }
    row += '<td></td>';
    if (user.completedAll)
      row += '<td class="total">'+user.score+'</td>';
    else
      row += '<td class="total missing">'+user.score+'</td>';
    row += '</tr>';
    $("#users").append(row);
  }
}
```

```
body { text-align: left !important}

#leaderboard {
  width: 500px;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

td.total {
  font-weight: bold;
  text-align: right;
}

td.missing {
  background: #bbbbbb;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="leaderboard">
  <h2>Leaderboard</h2>
  <p>
    Missing scores are shown as grey cells. A grey total indicates that the user has not participated in all challenges and is not eligible for the overall victory yet.
  </p>
  <table class="_user-list">
    <thead>
      <tr><td></td><td>User</td>
        <td><a href="https://codegolf.stackexchange.com/q/50484/31414">#1</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/50521/31414">#2</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/50625/31414">#3</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/51123/31414">#4</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/51222/31414">#5</a></td>
        <td></td><td>Total</td>
      </tr>
    </thead>
    <tbody id="users">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

---

# Series so far

***1. Double Knot***

***2. Flow Snakes***

***3. Chinese Shrines***

***4. Zodiac Signs***

***5. Random Diamond Tilings***

# Answer
> 12 votes
# CJam, 55 bytes

I got nerd sniped pretty badly by this... anyway, I finally came up with 55 bytes of ISO 8859-1:

```
"²îå<63ÅhbØº¢dräOä[æTZ"246b5b"|_ \/"f=9/4/~2/\ri*2>*zN*

```

or this alternative:

```
"ô/Ht]õDz1M;í,D¯Tmä$:r"246b5b"_/\ |"f=9/2/~+ri*2>\++zN*

```

Initially I tried to do it in plain ASCII, but only got it down to 58 bytes:

```
"C]VA~`+-WIt*n_I?FanSEo*b"128b5b"_/|\ "f=9/4/~2/\ri*2>*zN*

```

and again, an alternative:

```
"1,*Ap7c?UvI$yQHqHqs~=}n"153b5b"_ /|\\"f=9/2/~+ri*2>\++zN*

```

**Explanation:**

The idea is to encode the unique parts (left edge, right edge and middle pattern) in a convenient way, repeat the middle part as needed, and put them together. The code ended up being similar in many ways to Dennis's answer; I didn't try to copy him, but I tried many different approaches (including exploiting more symmetries and repetitions) and this is what worked best.

I put the left and right edges together like this:

```

 /\
|  |
|  |
 \/
 /\
|  |
|  |
 \/

```

The middle pattern has 4 columns, but they are repeated N-0.5 times, i.e. one repetition is cut in half. For convenience, I used this pattern:

```
  __
\/
/ /\
 /\/
/\ \
\/\
/ /\
 /\/
/\__

```

and removed the first half of the first repetition.

So I joined the parts and encoded them in transposed form, as it's easier to work with them that way. The first and third program encode this string:

```
 \/ /\/ /
 / /\/ /\
_ /\ \/\_
_ \/\ \/_
  ||  ||
 /  \/  \
 \  /\  /
  ||  ||

```

(without newlines), which is the transposition of the middle + edges. The second and fourth program (the "alternatives") encode this string:

```
  ||  ||
 /  \/  \
 \  /\  /
  ||  ||
 \/ /\/ /
 / /\/ /\
_ /\ \/\_
_ \/\ \/_

```

again, without newlines, and this is the transposition of edges + middle.

Here's how this common part of the code works:

```
"…"        encoded string (constructed via the reverse process,
           using a suitable base that gives valid characters)
246b       convert the string to an integer, treating each character as a digit
           in base 246 (or other bases in the ASCII versions)
5b         convert the number to base 5, obtaining 72 digits from 0 to 4,
           representing the 5 different characters we have
"|_ \/"f=  convert the digits to their corresponding characters
           (each program uses a different assignment order)
9/         split the resulting strings into 8 strings of 9 characters
           if viewed as lines, they look exactly like the 2 patterns shown above

```

After this, the implementation differs slightly. In the first and third program we have:

```
4/     split the lines into groups of 4 - the middle part and the edges
~      dump the two 4-line parts onto the stack
2/     split the second part (the edges) into 2 groups of 2 lines
       (left edge and right edge)
\      swap the edges with the middle part
ri*    read the input, convert to integer (N) and repeat the middle part N times
2>     remove the first 2 lines (first half of first repetition)
*      join the 2 edges using the repeated middle part as a separator
z      transpose the result back to the desired form
N*     join with newlines

```

In the second and fourth (alternative) programs, we have:

```
2/     split the lines into groups of 2
       (left edge, right edge, middle first half, middle 2nd half)
~      dump all the groups onto the stack
+      join the two middle halves into a single middle group of 4 lines
ri*    read the input, convert to integer (N) and repeat the middle part N times
2>     remove the first 2 lines (first half of first repetition)
\      swap the repeated middle with the right edge
+      concatenate the middle with the right edge
+      concatenate the left edge with the rest
z      transpose the result back to the desired form
N*     join with newlines

```

# Answer
> 23 votes
# CJam, ~~103~~ ~~92~~ ~~83~~ ~~69~~ ~~66~~ 57 bytes

```
"O5àäªÞáKZò,_÷%SJ«Ò"248b5b"/ \_|"f=9/4/~ri*1>W<+2m<zN*

```

Try it online in the CJam interpreter.

### Idea

The pattern becomes a lot more obvious once we transpose rows with columns (padded to the right with spaces).

For input **3**, for example, this gives:

```
  ||  ||
 /  \/  \
_ /\ \/\_
_ \/\ \/_
 \/ /\/ /
 / /\/ /\
_ /\ \/\_
_ \/\ \/_
 \/ /\/ /
 / /\/ /\
_ /\ \/\_
_ \/\ \/_
 \  /\  /
  ||  ||

```

The first two and last two rows are special, but the others repeat the same pattern over and over again.

Thus, for input **N**, all we have to do is repeat

```
 / /\/ /\
_ /\ \/\_
_ \/\ \/_
 \/ /\/ /

```

**N** times, replace the first row with

```
  ||  ||
 /  \/  \

```

the last row with

```
 \  /\  /
  ||  ||

```

and, finally, transpose rows with columns.

### Code

```
"O5àäªÞáKZò,_÷%SJ«Ò"

248b  e# Convert the string (array of code points in base 248) to an integer.
5b    e# Convert the integer to the array of its digits in base 5.

      e# This pushes the following array:

      e# [ 1 2 1 1 0 2 1 1 0 1 1 4 4 1 1 4 4 1 1 1 4 4 1 1
      e#   4 4 1 1 0 1 1 2 0 1 1 2 1 0 1 0 2 0 1 0 2 3 1 0
      e#   2 1 2 0 2 3 3 1 2 0 2 1 2 0 3 1 2 0 1 0 2 0 1 0 ]

"/ \_"

f=    e# Retrieve the chars that correspond to the indexes in the array.

      e# This pushes the following string:

      e# " \  /\  /  ||  ||   ||  ||  /  \/  \ / /\/ /\_ /\ \/\__ \/\ \/_ \/ /\/ /"

9/4/~ e# Divide into groups of 4 strings of length 9.

      e# This pushes the following arrays:

      e# [ " \  /\  /"   "  ||  || "   "  ||  || "   " /  \/  \" ]
      e# [ " / /\/ /\"   "_ /\ \/\_"   "_ \/\ \/_"   " \/ /\/ /" ]

ri    e# Read an integer from STDIN.
*     e# Repeat the last array that many times.
1>W<  e# Remove the first and last string from the array.
+     e# Concatenate both arrays.
2m<   e# Rotate the concatenated arrays two elements to the left.
z     e# Zip the array of strings (transpose rows with columns).
N*    e# Join the strings of the array, separating by linefeeds.

```

# Answer
> 12 votes
# Javascript (*ES7 Draft*), 169 163 160 158 bytes

*Edit: -6 by using a template string to eliminate some repetition from the pattern string.*

*Edit: -3 by switching from `slice(0,-2)` to `slice(2)` by rearranging the pattern string.*

*Edit: -2 by looping through `b` instead of `a` and reducing the `a` string to 4 with a modulo.*

```
F=N=>[(a='  ||'[i%4])+b[i]+`  __0\\/ ${c=' 0/ /\\0 /\\/0/\\'} \\0\\/\\${c}__`.split(0)[i].repeat(N).slice(2)+(b+b)[9-i]+a for(i in b=' /  \\/  \\')].join(`
`)
```

```
<input id="stdin" value="4" />
<button onclick="stdout.innerHTML=F(stdin.value)">Run</button><br />
<pre id="stdout"></pre>
```

**Commented:**

```
F=N=>[ // define function F, start array comprehension to generate each line
    (a = '  ||'[i % 4]) + // first character of the line, store copy in a
    b[i] + // second character of each line
        `  __0\\/ ${c=' 0/ /\\0 /\\/0/\\'} \\0\\/\\${c}__`.
        // list of patterns for each line delimited by 0's
        // results in string: '  __0\/  0/ /\0 /\/0/\ \0\/\ 0/ /\0 /\/0/\__'
        split(0)[i]. // split by 0, get index at i
        repeat(N). // repeat N times
        slice(2) + // chop off the first 2 characters
    (b + b)[9 - i] + // get opposite of second character, b+b to get a space at index 9
    a // repeat first character (a)
    for(i in b = ' /  \\/  \\') // runs for each index in character map b
].join(` // join resulting array with newlines
`)

```

# Answer
> 9 votes
# Perl, ~~134~~ 129

```
print s/...\K.{4}/$&x~-"@ARGV"/er=~y!iolp!| /\\!r,$/for
map/i/?$_.oi:"o$_$_".o,o__o,loop,@x=(iolplolp,ioplolpl),popl,lpop,@x,p__l

```

Takes a command line parameter:

```
$ perl ~/knot.pl 3
  __  __  __
 /  \/  \/  \
| /\/ /\/ /\ |
| \/ /\/ /\/ |
 \ \/\ \/\ \/
 /\ \/\ \/\ \
| /\/ /\/ /\ |
| \/ /\/ /\/ |
 \__/\__/\__/

```

# Answer
> 8 votes
# JavaScript (*ES6*), 165 ~~166~~

Knot elements:

* 2 top rows, based on ' \__' and '/ \\' repeated
* 2 outer rows, based on '/\\/ ' repeated and enclosed in '| ... |'
* 2 inner rows, based on '\\/\ ' repeated and enclosed in '.../' and '/...\\'
* the same 2 outer rows above
* 1 bottom row based on '\\\__/' repeated

**Ungolfed**

```
K=r=>
{
  R = x => x.repeat(r);
  S = d => R(elem).slice(d,d-2); // use global 'elem' that must be assigned before the call
  elem = '/\\/ '
  outer = '\n| ' + S(0) + ' |\n| ' + S(1) + ' |\n '
  elem = '\\ \\/'
  inner = '\\' + S(1) + '/\n /' + S(0) + '\\'
  return R('  __') + '\n ' + R('/  \\') + outer
  + inner + outer + R('\\__/')
}

```

**Golfed**

```
K=r=>(S=d=>(R=e=>e.repeat(r))(e).slice(d,d-2),o=`
| ${S(0,e='/\\/ ')} |
| ${S(1)} |
 `,R('  __')+`
 ${R('/  \\')+o}\\${S(1,e='\\ \\/')}/
 /${S(0)}\\${o}`+R('\\__/'))

// TEST

function go() {
  O.innerHTML=K(I.value)
}

go()
```

```
<input id=I value=5><button onclick='go()'>-></button><br>
<pre id=O></pre>
```

# Answer
> 8 votes
# C++ , 1530 639 479

This looked like a fun challenge I deviated from the brief a little.

```
#include "stdafx.h"
#include <iostream>
#include <sstream>
using namespace std;
string a=" __ ",b="/  \\",c=" /\\",d="/\\/ ",f="\\ \\/",g="/\\\ \\",r="\\__/",o="",e=o,j="|";
string q(int n,string r,string x="",string m=" ",string t=" "){string z=o;for(int i=0;i<n;i++){z+=r;if(i!=n-1)z+=x;}return m+z+t+"\n";}
int main(){int x,y;cin>>x;cin>>y;e+=q(x,a)+q(x,b);for(int i=0;i<y;i++){e+=q(x,c,"/",j," |")+q(x-1,d,o,"| \\/ ",j);if(i!=y-1){e+=q(x,f)+q(x,g);}}e+=q(x,r);cout<<e;}

```

Im not sure how to measure bytes of the size of my application but I will try figure it out and update my answer.

My app could be smaller but it loops in both the x and y, and I kinda like that :D

# Answer
> 6 votes
# Python 2, ~~156~~ ~~151~~ ~~147~~ ~~141~~ 139

edit 1: edited to use input() instead of a function.

edit 2: used str.join and added to var c to remove some redundant characters.

edit 3: removed some unnecessary string escape sequences.

edit 4: used ~-n instead of a=n-1

This was good fun to program, my first code golf!

```
n=input()
a='/\/ '*~-n
b='\ '+'\/\ '*~-n+'\\'
c='\n| '+a+'/\ |\n| \/ '+a+'|'
print'\n '.join(('  __'*n,'/  \\'*n+c,b+'/','/'+b+c,'\__/'*n))

```

save it in an external text editor as n.py in order to remove last newline character in order to reduce file size by 1 byte, run the module, and input your number.

# Answer
> 5 votes
# Python 2, ~~139~~ ~~133~~ 129 bytes

```
n=input()
for i in range(9):w=' ?|'[i&2];s=' / /\/ /\_ /\ \/\__ \/\ \/_ \/ /\/ /'[i::9]*n;s=(s,' %s '%s[1:-1])[i%4>1];print w+s+w

```

This one just builds and prints line by line.

Here's the code in ungolfed form:

```
n=int(input())
# The list with all the knot pieces
l= [' __ ',
    '/  \\',
    ' /\/',
    '/\/ ',
    '\ \/',
    '/\ \\',
    ' /\/',
    '/\/ ',
    '\__/']
# The first and last columns
w = '  ||  || '
# Loop for each row
for i in range(9):
    # Exception for the first and last character in the knot (in some rows)
    s = l[i]*n
    if i % 4 > 1:
        s = ' ' + s[1:-1] + ' '
    # Print the knot for this row
    print(w[i] + s + w[i])

```

**Edit:** I changed the language to python 2, to be compatible with my answer for #3 (and it also saves 6 more bytes)

# Answer
> 3 votes
## C, 159 bytes

```
j,k;f(n){char*t="7>771I;M6CMI93;IIB;;MI1M;M6CMI93;IIB;>MI";for(n*=4;t[j/2];++k,k%=n+3,j+=k-n?k%n<3||k%4-2?1:-3:3)putchar("\n _|/\\"[(t[j/2]-48)/(j%2?1:6)%6]);}

```

With whitespace, and some other readability improvements:

```
#include <stdio.h>

int j, k;

void f(int n) {
    char *t = "7>771I;M6CMI93;IIB;;MI1M;M6CMI93;IIB;>MI", *m = "\n _|/\\";
    for (n *= 4; t[j / 2];
         ++k,
         k %= n + 3,
         j += k - n ? k % n < 3 || k % 4 - 2 ? 1 : -3 : 3)
        putchar(m[(t[j / 2] - 48) / (j % 2 ? 1 : 6 ) % 6]);
}

```

This is primarily template based. The template `t` contains all 9 possible columns of the output, meaning that it encodes 9 * 9 = 81 characters, or 80 without the trailing newline.

Since there are only 6 different characters in the pattern (including newline characters), I packaged pairs of them into one template character, which means that the template can be stored in 40 characters. There are then 6 * 6 = 36 possible pairs of characters, which are encoded as ASCII characters 48 to 73. The translation back to the original character is given by the small lookup table `m`.

The rest of the logic is mainly to repeat the pattern `n` times, which means jumping back 4 characters in the template, while emitting the start and end parts of each row correctly.

# Answer
> 2 votes
# PHP 5.5.3, 488, 466

```
<?php
function k($n){$r=array_fill(0,9,'');for($i=0;$i<$n;$i++){$r[0].=($i==0)?"  __ ":" __ ";$r[1].=($i==0)?" /  \\":"/  \\";$r[2].=($i==0)?"| /\\/":(($i==$n-1)?" /\\ |":" /\\/");$r[3].=($i==0)?"| \/ ":(($i==$n-1)?"/\/ |":"/\/ ");$r[4].=($i==0)?" \\ ":(($i==$n-1)?"\\/\\ \\/":"\\/\\ ");$r[5].=($i==0)?" /\\ ":(($i==$n-1)?"\\/\\ \\":"\\/\\ ");$r[6]=$r[2];$r[7]=$r[3];$r[8].=($i==0)? " \__/":"\__/";}foreach($r as $o){if(strlen($o)-2 !== 4*$n)$o.=" ";echo $o."\n";}}

```

# Answer
> 2 votes
# Prolog (SWI), 285 bytes

```
a(N):-b(N,"  ||  || "," /  \\/  \\","_ /\\ \\/\\_","_ \\/\\ \\/_"," \\/ /\\/ /"," / /\\/ /\\"," \\  /\\  /"). b(N,[A|G],[B|H],[C|I],[D|J],[E|K],[F|L],[Y|Z]):-c(N,[Y,A],[E,F,C,D],T),writef([A,B,C,D|T]),nl,b(N,G,H,I,J,K,L,Z). c(1,L,_,L):-!. c(N,L,X,O):-M is N-1,c(M,L,X,T),append(X,T,O).

```

(With whitespace):

```
a(N):-
    b(N,
    "  ||  || ",
    " /  \\/  \\",
    "_ /\\ \\/\\_",
    "_ \\/\\ \\/_",
    " \\/ /\\/ /",
    " / /\\/ /\\",
    " \\  /\\  /").

b(N,[A|G],[B|H],[C|I],[D|J],[E|K],[F|L],[Y|Z]):-
    c(N,[Y,A],[E,F,C,D],T),
    writef([A,B,C,D|T]),
    nl,
    b(N,G,H,I,J,K,L,Z).

c(1,L,_,L):-!.
c(N,L,X,O):-
    M is N - 1,
    c(M,L,X,T),
    append(X,T,O).

```

I tried a few ways of chopping the strings, but none seemed to beat this naive columns method.

# Answer
> 2 votes
## JavaScript (ES6), ~~158~~ ~~154~~ ~~148~~ 137 bytes

```
n=>`    __
 /\\/ - \\/
 /\\/\\-__/`.replace(/-/g,` \\
| / /\\ |
|  /\\/ |
 \\/\\`).replace(/(..)(....)/g,(_,l,m)=>l+m.repeat(n).slice(2))

```

Edit: Saved 11 bytes thanks to @Bálint.

# Answer
> 1 votes
## PowerShell, 228 207 181 133 bytes

```
%{"  "+"__  "*$_;" "+"/  \"*$_;$b="|"+" /\/"*$_+"`b |";$b;$c="| "+"\/ /"*$_+"`b|";$c;" "+"\ \/"*$_;" "+"/\ \"*$_;$b;$c;" "+"\__/"*$_}

```

Reminder - PowerShell doesn't wait on stdin automatically. You have to pipe something in, e.g. `3|%{...}`

# Answer
> 1 votes
# Java, ~~339~~ 330 bytes

```
class D{int n,i;public static void main(String[]a){new D(new Integer(a[0]));}D(int k){n=k;r("  __");p("\n ");r("/  \\");c();r("\\ \\/");p("\n ");r("/\\ \\");c();r("\\__/");}void c(){p("\n|");--n;r(" /\\/");p(" /\\ |\n| \\/");r(" /\\/");++n;p(" |\n ");}void p(String s){System.out.print(s);}void r(String s){for(i=n;i>0;--i)p(s);}}

```

My first solution had so many "static" keywords in it that it was shorter to make the methods and attributes non-static and run the code in the constructor.

# Answer
> 0 votes
# SmileBASIC, 149 bytes

```
INPUT N?"  __"*N
A$="| / /\ |
B$="|  /\/ |
K" /\/  \
K A$K B$K" \/\ \/
K" /\/\ \
K A$K B$K" \/\__/
DEF K A?SUBST$(A,2,4,MID$(MID$(A,2,4)*N,2,N*9))END

```

Each string contains the pattern `AACCBBDD` which is expanded to form `AABB(CCBB)*DD` The `CCBB` part is repeated N times, then the first 2 characters are removed. (It was shorter to remove characters from the start than from the end)

# Answer
> 0 votes
# Vyxal, 78 bytes

```
‛ _m*ðp,‛/ øṀ*ðp,` /\\`w$ẋf⁋¶\/V\|p‛ |+…Ṙ…£`\/\\`w$ẋfṄðpǔð₴…ð₴ǔ,¥Ḃ,,`\__/`*ðp,

```

Try it Online!

Builds it incrementally. Here's a cool version that makes it a square.

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---