# Question
Title: Finding the period of a recurring element in an array
Given an array `A` of integers, there exists at least one positive integer p such that `A[i] == A[j]` for all `i` and `j` for which `i % p == j % p == 0`. Find the smallest p.

Examples:

* Input array: `[1, _, 1, _, 1, _, 1, _, 1]`. Output: 2
* Input array: `[1, _, _, 1, _, _, 1, _, _]`. Output: 3.
* Input array: `[1, _, _, _, 1, _, _, _, 1]`. Output: 4

# Answer
# Python 3, 47 bytes

```
f=lambda l,d=1:f(l,d+1)if~-len({*l[::d]})else d

```

Try It Online
> 1 votes

# Answer
# Python 3, 43 bytes

```
f=lambda l,n=1:2>len({*l[::n]})or-~f(l,n+1)

```

Try it online!

Assumes the list is non-empy. Outputs `True` as `1`, though for 1 byte this can be fixed by changing `2>` to `1//`.

**44 bytes:**

```
f=lambda l,n=1:{l[0]}=={*l[::n]}or-~f(l,n+1)

```

Try it online!

```
f=lambda l,n=1:l[:-n:n]==l[n::n]or-~f(l,n+1)

```

Try it online!
> 1 votes

# Answer
# Jelly, 6 bytes

Assuming this is meant to be for now.

```
mJE€TḢ

```

**Try it online!**
> 0 votes

# Answer
# Python 3, 64 Bytes

A recursive approach.

```
f=lambda x,s=1:s if x[::s].count(x[0])==len(x[::s])else f(x,s+1)

```

Try it Online

# Python 3, ~~82~~ 81 Bytes

-1 byte thanks to Jakob!

```
lambda x:[x[::i].count(x[0])==len(x[::i])for i in range(1,len(x)+1)].index(1>0)+1

```

Try it Online!
> 0 votes

# Answer
# Pyth, 7 bytes

```
f!t{%TQ

```

Try it here. Pyth is at a disadvantage because it uses only printable ASCII; optimally encoded this would be \\$7 * \log\_{256} 95 = 5.749\\$ bytes.

```
f             Find the first positive integer T such that
 !t           there is only one element in
   {          the list obtained by taking unique elements
    %TQ       of every Tth element of the input.

```
> 0 votes

# Answer
# Java 8, 85 bytes

A lambda from a primitive array type to `int`.

```
l->{for(int d=0,i;;)for(i=++d;;i+=d){if(i>=l.length)return d;if(l[i]!=l[i-d])break;}}

```

Try It Online

## Ungolfed

```
l -> {
    for (int d = 0, i; ;)
        for (i = ++d; ; i += d) {
            if (i >= l.length)
                return d;
            if (l[i] != l[i - d])
                break;
        }
}

```
> 0 votes

# Answer
# Japt, 10 bytes

```
@ëX â ÊÉ}f

```

Try it online!

Explanation:

```
@       }f    :Get the first integer X which returns 0 from:
 ëX           : Get every Xth item in the input
    â         : Get the unique values of that list
      Ê       : Count how many there are
       É      : Subtract 1

```
> 0 votes

# Answer
# Japt, 6 bytes

I think this is right, the spec isn't all that clear. Assumes, as the spec would seem to suggest, that the number we're looking for will always appear first in the array and the `_`s must all be different from that number.

```
ð¶Ug)æ

```

Try it

```
           :Implicit input of array U
ð          :0-based indices of elements
 ¥         :  Equal to
  Ug       :  First element of U
    )      :End indexing
     æ     :First truthy (non-zero) element

```
> 0 votes

# Answer
# Powershell, 82 bytes

```
(($a=$args)|%{($i++)}|?{"$a"-match"^(\d+)(( -?\d+){$_} \1)*( -?\d+){0,$_}$"})[0]+1

```

Test script:

```
$f = {

(($a=$args)|%{($i++)}|?{"$a"-match"^(\d+)(( -?\d+){$_} \1)*( -?\d+){0,$_}$"})[0]+1

}

@(
    ,(1 , 1,1,1,1,1)
    ,(2 , 1,-2,1,3,1,-4,1,5)
    ,(2 , 1,-2,1,3,1,-4,1,5,1)
    ,(3 , 1,-2,1,1,3, 4,1,5,1)  # 1 may be in place '_'
    ,(4 , 1,-2,3,4,1, 5,1,6,1)
    ,(5 , 1,2,3,4,5,1)
) | % {
    $expected, $a = $_
    $result = &$f @a
    "$($result-eq$expected): $result"

}

```

Explanation:

`Regexp` match on `array.toString()` which equivalent `array.join(' ')`.
> 0 votes

---
Tags: code-golf, array
---


title: Most Populated WordSearch

text:
# Question
Title: Most Populated WordSearch
Write a program to generate a rectangular word-search of size 6x9. Words may go downwards, rightwards and diagonally (downwards and to the right), they may also overlap on the board.

The challenge is to include as many different English words as possible from https://www.ef.co.uk/english-resources/english-vocabulary/top-3000-words Your program may select desirable words itself to include. You score 1 point per word included.

---

For example:

For clarity I've used "." symbols below instead of random letters.

```
dolphin..
o.....o..
g.....u..
.....ono.
.........
.........

```

The above word-search contains {'do', 'dog', 'dolphin', 'hi', 'i', 'in', 'no', 'noun', 'on', and 'phi'} so from what is filled in so far scores 10 points.

In the unlikely event of a tie the shortest code size will be used to choose a winner.

# Answer
# Jelly, 20 bytes, score  ~~53~~  57

```
“¦/œḌ⁼ƥ~ẹµḲ5&Ċd@ṡ»ḲY

```

**Try it online!**

Wordsearch:

```
a d m i s s i o n
h o u s e h o l d
s o m e t h i n g
g e n e r a l l y
p o t e n t i a l
t h e r e f o r e

```

Words:

```
admission generally household potential something therefore
general mission
house stair there thing
ally gene here hill hold miss some tent thin
air all due era for hat her ill oil old one pot see set son ten the use
ad ah at do go he hi ie in me ms oh on or so to us
i

```

---

**Previous**
...the dictionary referenced in the question has changed since this was posted so this would drop to a score of 33.

# Jelly, 23 bytes, score  ~~150 154 158~~  160

```
“RʂȥḄ0ḣq⁾÷yḊzIḥẊḥYx »ḲY

```

**Try it online!**

Used Python to search for boards; there are, no doubt, higher scores possible though.

The board:

```
donations
beverages
placement
performed
metallica
thousands

```

The words:

```
['a', 'ac', 'ace', 'ae', 'ag', 'age', 'ages', 'al', 'all', 'am', 'an', 'and', 'ar', 'art', 'as', 'at', 'ati', 'au', 'b', 'be', 'beverage', 'beverages', 'bp', 'c', 'ca', 'cd', 'ce', 'cement', 'cf', 'd', 'da', 'das', 'db', 'do', 'don', 'donation', 'donations', 'ds', 'e', 'ec', 'ed', 'ee', 'eh', 'el', 'em', 'en', 'ent', 'er', 'era', 'es', 'et', 'ev', 'eve', 'ever', 'f', 'fa', 'fo', 'for', 'form', 'formed', 'g', 'ge', 'gem', 'h', 'ho', 'i', 'ia', 'ic', 'in', 'io', 'ion', 'l', 'la', 'lace', 'le', 'lee', 'li', 'll', 'ls', 'm', 'me', 'med', 'men', 'ment', 'met', 'meta', 'metal', 'metallic', 'metallica', 'mi', 'min', 'mr', 'mt', 'n', 'na','nat', 'nation', 'nations', 'nd', 'ne', 'nec', 'ns', 'nt', 'nv', 'o', 'oe', 'og', 'ol', 'on', 'ons', 'or', 'ou', 'p', 'pe', 'per', 'perform', 'performed', 'pl', 'place', 'placement', 'pm', 'pp', 'ppm', 'r', 'ra', 'rage', 're', 'rf', 'rl', 'rm', 'rt', 's', 'sa', 'san', 'sand', 'ss', 'st', 'std', 't', 'ta', 'tall', 'td', 'th', 'thou', 'thousand', 'thousands', 'ti', 'tion', 'tions', 'to', 'tr', 'treo', 'u', 'us', 'usa', 'v', 'va', 'var', 've', 'ver']

```

---

### The search

Note `LIMIT_TO_N_BEST_NINES` limits the search - lower numbers try fewer boards by never using the lower scoring rows (nine letter words) which will find "good" scores quicker, while higher numbers (up to 909 - the number of 9 letter words in the dictionary) will search more boards (and likely never complete!).

```
f = open(filePath, 'r')
ws = set(w.replace('\n', '').lower() for w in f.readlines())

def iterSubWords(w, ws):
    for l in range(1,len(w)+1):
        for s in range(len(w)-l+1):
            if w[s:s+l] in ws: yield w[s:s+l]

nines = sorted([w for w in ws if len(w) == 9], key=lambda w:len(tuple(iterSubWords(w, ws))), reverse=1)

def diags(rows):
    for rs in range(len(rows)):
        yield ''.join(rows[rs + x][x] for x in range(min(len(rows) - rs, len(rows[0]))))
    for cs in range(1, len(rows[0])):
        yield ''.join(rows[x][cs + x] for x in range(min(len(rows[0]) - cs, len(rows))))

def diagWords(rows, validWords):
    for d in diags(rows):
        for sw in iterSubWords(d, validWords): yield sw

def allWordsOnBoard(rows, validWords):
    r = set()
    for row in list(rows) + [''.join(col) for col in zip(*rows)]:
        for validWord in iterSubWords(row, validWords): r.add(validWord)
    for validWord in diagWords(rows, validWords): r.add(validWord)
    return r

from itertools import combinations, permutations

LIMIT_TO_N_BEST_NINES = 107

m = 0
for wl in combinations(nines[:LIMIT_TO_N_BEST_NINES], 6):
    fws = allWordsOnBoard(wl, ws)
    if len(fws) > m:
        for p in permutations(wl):
            fws = allWordsOnBoard(p, ws)
            if len(fws) > m:
                m = len(fws)
                print(m, p)

```
> 2 votes

# Answer
# Lua, 73 bytes - 49 66 74 75 words

```
print("abraiders\nscrapings\nsheathers\ncarabiner\nbrahmanis\nrelapsers")

```

Try it online!

I got the words from another StackExchange question on the Puzzles site. Prints:

```
abraiders
scrapings
sheathers
carabiner
brahmanis
relapsers

```

So it's a minimum of eight words each row for 48 words, plus the indefinite article 'a' for 49 words horizontally. **Edit**: It seems there was an edit to the challenge and there now may be a limit to a list of very specific words and, unlike all of the words forming my list, not all of those words are actually even English. *sigh* Might just leave this here for posterity.

**Edit** Words formed horizontally:

```
i (pronoun 'I')
id
aid
aide
raid
aider
braid
aiders
raider
raiders
braiders
abraiders

la
lap
laps
lapse
elapse
relapse
relapser
relapsers

in
pin
rap
ping
crap
pings
aping
scrap
raping
craping
scraping
scrapings

at
he
eat
her
she
the
eath
heat
hers
heath
sheath
sheathe
sheather
sheathers

a
ab
rab
bin
car
arab
arabi
arabin
arabine
carabine
carabiner

is
ra
rah
man
bra
rahm
brahm
brahma
brahman
brahmani
brahmanis

```

Words formed vertically:

```
as
aha
are
ass
era
char
hare

```
> 1 votes

---
Tags: code-challenge, word-search
---


# Question
Title: Kolmogorov Flexibility. A.K.A. Sale! \$38\%\$ Off All Codegolf While Stocks Last!
This is a , , challenge to produce a fixed output with no input.

The output format, however, is flexible - it may be printed to standard out, printed to standard error, returned as a list of characters, returned as a list of bytes, or returned as a list of integers. If you think anything else seems reasonable just ask in the comments!

Here is a simple, big-letter ASCII art **CODEGOLF**:

```
 CCCC   OOO   DDDD   EEEEE   GGG    OOO   L      FFFFF
C      O   O  D   D  E      G      O   O  L      F
C      O   O  D   D  EEE    G  GG  O   O  L      FFF
C      O   O  D   D  E      G   G  O   O  L      F
 CCCC   OOO   DDDD   EEEEE   GGGG   OOO   LLLLL  F

```

Without any newlines (or trailing spaces on any lines) it is 256 characters long:

```
 CCCC   OOO   DDDD   EEEEE   GGG    OOO   L      FFFFFC      O   O  D   D  E      G      O   O  L      FC      O   O  D   D  EEE    G  GG  O   O  L      FFFC      O   O  D   D  E      G   G  O   O  L      F CCCC   OOO   DDDD   EEEEE   GGGG   OOO   LLLLL  F

```

The (0-based) indices of the non-space characters are:

```
1, 2, 3, 4, 8, 9, 10, 14, 15, 16, 17, 21, 22, 23, 24, 25, 29, 30, 31, 36, 37, 38, 42, 49, 50, 51, 52, 53, 54, 61, 65, 68, 72, 75, 82, 89, 93, 96, 103, 104, 111, 115, 118, 122, 125, 126, 127, 132, 135, 136, 139, 143, 146, 153, 154, 155, 156, 163, 167, 170, 174, 177, 184, 188, 191, 195, 198, 205, 207, 208, 209, 210, 214, 215, 216, 220, 221, 222, 223, 227, 228, 229, 230, 231, 235, 236, 237, 238, 242, 243, 244, 248, 249, 250, 251, 252, 255

```

You **may not use any of these 97 bytes in your code** but must produce a list (or similarly output) these bytes, in this order, with the missing bytes replaced by the 32nd byte in the code page you are using (in many, many code-pages a space character).

You may include the pretty-printing\* newlines (but no trailing spaces on the lines) if it helps.

For example using the Jelly code-page this output is acceptable:

```
 ¢£¤¥   ®µ½   ÇÐÑ×   ßæçðı   øœþ    $%&   *      12345
6      =   A  D   H  K      R      Y   ]  `      g
h      o   s  v   z  }~¶    ⁴  ⁷⁸  ⁻   Ɓ  Ƒ      ƲȤɓ
ƈ      ɲ   ʂ  ȥ   Ẹ  Ḳ      Ṭ   Ỵ  Ḃ   Ḟ  İ      Ṡ
 ẆẊẎŻ   ẹḥị   ṇọṛṣ   ẉỵẓȧḃ   ḟġḣŀ   ṗṙṡ   ẏż«»‘  ”

```

...but so is:

```
 ¢£¤¥   ®µ½   ÇÐÑ×   ßæçðı   øœþ    $%&   *      123456      =   A  D   H  K      R      Y   ]  `      gh      o   s  v   z  }~¶    ⁴  ⁷⁸  ⁻   Ɓ  Ƒ      ƲȤɓƈ      ɲ   ʂ  ȥ   Ẹ  Ḳ      Ṭ   Ỵ  Ḃ   Ḟ  İ      Ṡ ẆẊẎŻ   ẹḥị   ṇọṛṣ   ẉỵẓȧḃ   ḟġḣŀ   ṗṙṡ   ẏż«»‘  ”

```

...and so is:

```
[32, 1, 2, 3, 4, 32, 32, 32, 8, 9, 10, 32, 32, 32, 14, 15, 16, 17, 32, 32, 32, 21, 22, 23, 24, 25, 32, 32, 32, 29, 30, 31, 32, 32, 32, 32, 36, 37, 38, 32, 32, 32, 42, 32, 32, 32, 32, 32, 32, 49, 50, 51, 52, 53, 54, 32, 32, 32, 32, 32, 32, 61, 32, 32, 32, 65, 32, 32, 68, 32, 32, 32, 72, 32, 32, 75, 32, 32, 32, 32, 32, 32, 82, 32, 32, 32, 32, 32, 32, 89, 32, 32, 32, 93, 32, 32, 96, 32, 32, 32, 32, 32, 32, 103, 104, 32, 32, 32, 32, 32, 32, 111, 32, 32, 32, 115, 32, 32, 118, 32, 32, 32, 122, 32, 32, 125, 126, 127, 32, 32, 32, 32, 132, 32, 32, 135, 136, 32, 32, 139, 32, 32, 32, 143, 32, 32, 146, 32, 32, 32, 32, 32, 32, 153, 154, 155, 156, 32, 32, 32, 32, 32, 32, 163, 32, 32, 32, 167, 32, 32, 170, 32, 32, 32, 174, 32, 32, 177, 32, 32, 32, 32, 32, 32, 184, 32, 32, 32, 188, 32, 32, 191, 32, 32, 32, 195, 32, 32, 198, 32, 32, 32, 32, 32, 32, 205, 32, 207, 208, 209, 210, 32, 32, 32, 214, 215, 216, 32, 32, 32, 220, 221, 222, 223, 32, 32, 32, 227, 228, 229, 230, 231, 32, 32, 32, 235, 236, 237, 238, 32, 32, 32, 242, 243, 244, 32, 32, 32, 248, 249, 250, 251, 252, 32, 32, 255]

```

(This last one is a valid list output in any language with any code-page, and one may use any reasonable list-formatting too.)

---

Here is Python 3 code which shows the unavailable ASCII bytes.

* Although the printing itself might not actually be all that pretty!

# Answer
> 7 votes
# Python 2, ~~321~~ 203 bytes

```
print map(lambda(i,x):(x>'0'and i-8-8-8-8)+8+8+8+8,enumerate(bin(int(reduce(lambda x,y:x+repr('abcdefijkl'.find(y)),'cfjdbljcibkeajjejiljjlcbjddlafklebajjlceljdeadficijflealkeklkljadfbbckjebclkf','')))))

```

Try it online!

---

**Explanation:**

from the inside out:

`cfjdbljcibkeajjejiljjlcbjddlafklebajjlceljdeadficijflealkeklkljadfbbckjebclk` is the number `25731972618407747697792173390589410779249734035626759409848989703511287412985` encoded with allowed characters. (No `123456`'s allowed)

`reduce(lambda x,y:x+repr('abcdefijkl'.find(y)),'cfjdbl..bclkf','')` maps the string to its decimal string:

* `reduce(lambda x,y:x+y,'..','')` is the same as `''.join('..')` (No `o`'s allowed)
* `repr('..')` instead of `str('..')` (No `s`'s allowed)
* `'abcdefijkl'.find(y)` maps a char to a digit.

`enumerate(bin(int(...)))` converts the number string to a binary string, and enumerates. This gives the pairs `[(0,0), (1,b), (2,1), (3,1), ...]`

`map(lambda(i,x):(x>'0'and i-8-8-8-8)+8+8+8+8, ... )` converts the enumerated list to the final result.

* `map(lambda(i,x):.. , .. )` instead of `[... for(i,x)in ...]` (No `o]`'s allowed)
* `lambda(i,x): ..` converts each (index,value) pair to either the index or `32`.
* `(x>'0'and i-8-8-8-8)+8+8+8+8` is the same as:
    + `x>'0'and i or 8+8+8+8`, (No `o`'s allowed)
    + `[8+8+8+8,i][x>'0']` or `[8<<9-7,i][x>'0']`, (No `]`'s allowed)
* `8+8+8+8` = `32` (No `23`'s allowed)

This means that the program is essentially the same as:

```
print[[32,i][x>'0']for i,x in enumerate(bin(25731972618407747697792173390589410779249734035626759409848989703511287412985))]

```

# Answer
> 7 votes
# C (gcc), 318 bytes

```
main(_){--_<88+80+88?printf((int[:>){77707-989908070??>,((int[:>){0xE8E8C79E^0xB0B0080,0xC07E0870^0xE0000C00,0xCC08099C^0xEE0C008E,0xE8888989^0xCC00808,0x9E088990^0x800C0000,0x990C8888^0x080ECC00,0xF9C7a088^0x080000C0,0x9F8C78F8^0x900000??>[_>>(0xC^0x9):>>>(_<<9+9+9>>9+9+9))<<(70^89)>>(70^89)?_:' '),main(_+9-7):0;??>

```

Try it online!

This one is a bit of a journey...

### 1. Compressing the list

Somehow we will need to check if a given integer is one of the special code points. Any 'naked' list will be far too long, so we use a check list. This list has a non-zero value at code points that are 'restricted' and a zero value at those that aren't.

Unfortunately this still takes 512 bytes just to have the list (it looks like `0,0,7,7,0,7,0,...`). This can be shortened with a bitmask.

To make use of the bitmask we will break each byte into two pieces. The first 3 bits will pick a mask from an array while the last 5 will pick a bit in the array. We can't shrink the array any further because the 32-bit integers used by default don't support any more than 2^5=32 bits.

Using a reference implementation I wrote:

```
int main() {
    int i;
    int vals[] = {1, 2, 3, 4, 8, 9, 10, 14, 15, 16, 17, 21, 22, 23, 24, 25, 29, 30, 31, 36, 37, 38, 42, 49, 50, 51, 52, 53, 54, 61, 65, 68, 72, 75, 82, 89, 93, 96, 103, 104, 111, 115, 118, 122, 125, 126, 127, 132, 135, 136, 139, 143, 146, 153, 154, 155, 156, 163, 167, 170, 174, 177, 184, 188, 191, 195, 198, 205, 207, 208, 209, 210, 214, 215, 216, 220, 221, 222, 223, 227, 228, 229, 230, 231, 235, 236, 237, 238, 242, 243, 244, 248, 249, 250, 251, 252, 255, 0};

    for (i = 0; i <= 0xFF; ++i) {
        int j,f;
        f = 0;
        for (j = 0; vals[j]; ++j)
            if (vals[j] == i)
                f = 1;
        if (f)
            printf("1");
        else
            printf("0");

        if (i%32 == 31)
            printf("\n");
    }

    return 0;
}

```

I was able to generate the appropriate values for this new array using the command `echo "obase=16;ibase=2;$(./a.out | rev)" | bc`. This passes the output of the above program (`./a.out`) to the `rev` program, which reverses each line. It prints this along with a header to bc that sets the output base to 16 and input base to 2. Thus bc converts the binary digits to a hexadecimal bitmask.

The resulting array is can be seen in this 'beta' solution:

```
f(){
    int x;
    int arr[] = {0xE3E3C71E, 0x207E0470, 0x22040912, 0xE4488181, 0x1E048990, 0x91024488, 0xF1C7A048, 0x9F1C78F8};
    for (x=0; x<=0xFF; ++x) {
        int mask = arr[x >> 5];
        int bit = mask >> (x & 0x1F);

        if (bit & 1)
            printf("%c", x);
        else
            printf(" ");
    }
}

```

### 2. Dealing with the constraints

There are a lot of constraints that need to be placed on the above code. Here I go through each of them 1-by-1.

1. No assignment

This is felt by other languages as well, without assignment in C it is very hard to get any guaranteed values into variables. The easiest way for us is to write our function as a full program. The first argument of `main` will be passed the value of `argc` which will be 1 if called with no arguments.

2. No looping

The only looping constructs in C are `for`, `while`, and `goto` all of which contain restricted characters. This leaves us with using recursion. The main function will start at 1 and recurse until the argument is \>256, meanwhile it will decrement the argument internally to use a 0-indexed value.

3. Hex values

The values in the above array are hexadecimal, even when converted to decimal, these contain some restricted symbols, most notably 123456 (AD can be lower-cased). To work around this each constant is XORed with another such that the restricted characters are removed. 1 becomes 9^B, 2 becomes C^E, 3 becomes B^8, 4 becomes 8^C, 5 becomes 9^C, and 6 becomes 9^F (there are more ways to do it, I chose this way).

4. Printing

The restrictions don't leave many printing functions left to us. `putchar` and `puts` are both restricted, leaving `printf`. Unfortunately we have to send `printf` a format string, ideally "%c". All such strings have that pesky percent sign that we wish to remove. Luckily we assume a little-endian machine (because apparently that's what TIO uses, and that's pretty typical). By constructing the integer whose bytes in memory are 0x25 (%), 0x63 (c), 0x00 (\0), anything (doesn't matter, its after the null terminator) we can just pass its address to `printf` and it will assume it is a string. One such number that works is -989830363 (0xC5006325). This is easy to create under the restrictions as 77707-989908070.

There's still the issue that we can't reference any values (because we can't assign them and because we can't use &), so we have to use an array literal (int\[\]){...}. We actually use this for the bitmask array above as well.

5. Closing brackets

We can't use '\]' or '}' to close either our arrays or functions. Luckily C has digraphs and trigraphs that work. `:>` will become `]`, while `??>` will become `}`. This requires gcc to take the `-trigraphs` switch, as it ignores trigraphs by default (in violation of the standard).

6. Bitwise operations

We can't use `&` to mask bits off of our index, nor can we use `%` to get there the old-fashioned way. Therefore we rely on implementation specific behaviour. In particular we shift our 32-bit integers far enough to the left to lose bits, then back to the right. For example to get the last 5 bits of our number we first shift it left 27 bits (leaving `abcde00000...`) then shift it back to the right by 27 bits (leaving `...00000abcde`).

7. Miscellaneous values

We need a few more literal values throughout the code - these are taken from Arnauld's JS answer, plus 27 (for the reason above) is added by me as `9+9+9`.

### 3. Putting it together

Here is the description of the source with all of these changes together.

```
main(_){                // This is our main entry point
--_<88+80+88            // This subtracts 1 from the argument (_) and checks if it is less than 256
    ?                   // If it is less than 256 we 'continue'
printf(                 // first we call printf with...
    (int[:>){           // An integer array that will be interpreted as a string
    77707-989908070     // With the value we determined above, to represent "%c\0\xC5"
    ??>,                // This is a trigraph for }, just as the :> above is a digraph for ]
    ((int[:>){          // We immediately create another integer array
0xE8E8C79E^0xB0B0080,   // Each row is the bit-mask for 32 characters
0xC07E0870^0xE0000C00,
0xCC08099C^0xEE0C008E,
0xE8888989^0xCC00808,
0x9E088990^0x800C0000,
0x990C8888^0x080ECC00,
0xF9C7a088^0x080000C0,
0x9F8C78F8^0x900000??>
[_>>(0xC^0x9):>         // This is {arr}[_>>5] just in a roundabout way
>>(_<<9+9+9>>9+9+9))    // Similarly this is (...)>>(_&0x1F)
<<(70^89)>>(70^89)      // This is <<31>>31 or &1, to check the last bit
?_:' ')                 // If its 1, we print the character, otherwise we print a space
,main(_+9-7):0;         // We recurse, the :0 is the other branch of the if, it terminates execution
??>

```

# Answer
> 6 votes
# brainfuck, 635 bytes

```
++++++++++++++++++++++++++++++++.>+.+.+.+.<...>++++.+.+.<...>++++.+.+.+.<...>++++.+.+.+.+.<...>++++.+.+.+....++++.+.+.<...>++++.<......>+++++++.+.+.+.+.+.<......>+++++++.<...>++++.<..>+++.<...>++++.<..>+++.<......>+++++++.<......>+++++++.<...>++++.<..>+++.<......>+++++++.+.<......>+++++++.<...>++++.<..>+++.<...>++++.<..>+++.+.+.<....>+++++.<..>+++.+.<..>+++.<...>++++.<..>+++.<......>+++++++.+.+.+.<......>+++++++.<...>++++.<..>+++.<...>++++.<..>+++.<......>+++++++.<...>++++.<..>+++.<...>++++.<..>+++.<......>+++++++.<.>++.+.+.+.<...>++++.+.+.<...>++++.+.+.+.<...>++++.+.+.+.+.<...>++++.+.+.+.<...>++++.+.+.<...>++++.+.+.+.+.<..>>-.

```

Try it online!

In response to finally being beaten by Javascript, I have golfed what I can out of this:

1 byte saved by having 32 in cell 0 and incrementing cell 1 (the only reason I initially had it the other way was because of a quick fix when OrjanJohansen pointed out I couldn't use `]`)

1 byte saved by decrementing a third cell (initially at 0) to generate `255` = `-1`

2 bytes saved by printing spaces between characters 31 and 36 without using `<>` but instead simply stopping at 32 to print from cell 0 when incrementing from 31 through 33.

# brainfuck, 639 bytes

```
>++++++++++++++++++++++++++++++++.<+.+.+.+.>...<++++.+.+.>...<++++.+.+.+.>...<++++.+.+.+.+.>...<++++.+.+.>....<+++++.+.+.>...<++++.>......<+++++++.+.+.+.+.+.>......<+++++++.>...<++++.>..<+++.>...<++++.>..<+++.>......<+++++++.>......<+++++++.>...<++++.>..<+++.>......<+++++++.+.>......<+++++++.>...<++++.>..<+++.>...<++++.>..<+++.+.+.>....<+++++.>..<+++.+.>..<+++.>...<++++.>..<+++.>......<+++++++.+.+.+.>......<+++++++.>...<++++.>..<+++.>...<++++.>..<+++.>......<+++++++.>...<++++.>..<+++.>...<++++.>..<+++.>......<+++++++.>.<++.+.+.+.>...<++++.+.+.>...<++++.+.+.+.>...<++++.+.+.+.+.>...<++++.+.+.+.>...<++++.+.+.>...<++++.+.+.+.+.>..<+++.

```

Try it online!

First we generate the number 32. Then we just go through incrementing one cell and switching the printing between that cell and the one containing 32. Steadily increasing numbers are something Brainfuck does well.

It's nice to beat Javascript with Brainfuck, it doesn't happen often!

# Answer
> 5 votes
# JavaScript (SpiderMonkey), ~~1918~~ ~~1598~~ ~~1487~~ 1431 bytes

*Saved 56 bytes thanks to @user202729*

```
print(8<<98,7/7,9-7,7>>97,8>>97,8<<98,8<<98,8<<98,8,9,0xa,8<<98,8<<98,8<<98,0xe,0xf,7+9,8+9,8<<98,8<<98,8<<98,7+0xe,7+0xf,8+0xf,9+0xf,78^87,8<<98,8<<98,8<<98,77^80,70^88,70^89,8<<98,8<<98,8<<98,8<<98,9<<98,70^99,77>>97,8<<98,8<<98,8<<98,98-070,8<<98,8<<98,8<<98,8<<98,8<<98,8<<98,9^070,80^98,80^99,87^99,87^98,9^077,8<<98,8<<98,8<<98,8<<98,8<<98,8<<98,70-9,8<<98,8<<98,8<<98,7^70,8<<98,8<<98,9^77,8<<98,8<<98,8<<98,7^79,8<<98,8<<98,70^0xd,((8<<98)+' ').repeat(8^0xe)+(8^90),((8<<98)+' ').repeat(8^0xe)+89,8<<98,8<<98,8<<98,7^90,8<<98,8<<98,7+89,((8<<98)+' ').repeat(8^0xe)+(7|97),7+97,((8<<98)+' ').repeat(8^0xe)+(77|98),8<<98,8<<98,8<<98,80|99,8<<98,8<<98,8^0x7e,8<<98,8<<98,8<<98,0x7a,8<<98,8<<98,0x7d,0x7e,0x7f,8<<98,8<<98,8<<98,8<<98,7+0x7d,8<<98,8<<98,0x87,0x88,8<<98,8<<98,0x8b,8<<98,8<<98,8<<98,0x8f,8<<98,8<<98,7+0x8b,((8<<98)+' ').repeat(8^0xe)+0x99,0x9a,0x9b,0x9c,((8<<98)+' ').repeat(8^0xe)+(7+0x9c),8<<98,8<<98,8<<98,0xa7,8<<98,8<<98,0xaa,8<<98,8<<98,8<<98,0xae,8<<98,8<<98,78+99,((8<<98)+' ').repeat(8^0xe)+0xb8,8<<98,8<<98,8<<98,0xbc,8<<98,8<<98,0xbf,8<<98,8<<98,8<<98,97+98,8<<98,8<<98,99+99,((8<<98)+' ').repeat(8^0xe)+0xcd,8<<98,0xcf,0xd0,7+0xca,7+0xcb,8<<98,8<<98,8<<98,7+0xcf,0xd7,0xd8,8<<98,8<<98,8<<98,0xdc,0xdd,0xde,0xdf,8<<98,8<<98,8<<98,7+0xdc,7+0xdd,7+0xde,7+0xdf,0xe7,8<<98,8<<98,8<<98,0xeb,0xec,0xed,0xee,8<<98,8<<98,8<<98,7+0xeb,7+0xec,7+0xed,8<<98,8<<98,8<<98,0xf8,0xf9,0xfa,0xfb,0xfc,8<<98,8<<98,0xff)

```

Try it online!

### How?

The fact that `=` is not allowed is a show-killer in JS. We can't do any variable assignment, and we also can't use any arrow function.

The above code is instead computing each number separately, using the allowed digits in either decimal, octal or hexadecimal (\\$0\\$, \\$7\\$, \\$8\\$, \\$9\\$ and **0xa** to **0xf**) and the following operators: `+`, `-`, `/`, `|`, `^`, `<<` and `>>`.

```
  1 = 7/7     |   50 = 80^98   |  136 = 0x88    |  216 = 0xd8
  2 = 9-7     |   51 = 80^99   |  139 = 0x8b    |  220 = 0xdc
  3 = 7>>97   |   52 = 87^99   |  143 = 0x8f    |  221 = 0xdd
  4 = 8>>97   |   53 = 87^98   |  146 = 7+0x8b  |  222 = 0xde
  8 = 8       |   54 = 9^077   |  153 = 0x99    |  223 = 0xdf
  9 = 9       |   61 = 70-9    |  154 = 0x9a    |  227 = 7+0xdc
 10 = 0xa     |   65 = 7^70    |  155 = 0x9b    |  228 = 7+0xdd
 14 = 0xe     |   68 = 9^77    |  156 = 0x9c    |  229 = 7+0xde
 15 = 0xf     |   72 = 7^79    |  163 = 7+0x9c  |  230 = 7+0xdf
 16 = 7+9     |   75 = 70^0xd  |  167 = 0xa7    |  231 = 0xe7
 17 = 8+9     |   82 = 8^90    |  170 = 0xaa    |  235 = 0xeb
 21 = 7+0xe   |   89 = 89      |  174 = 0xae    |  236 = 0xec
 22 = 7+0xf   |   93 = 7^90    |  177 = 78+99   |  237 = 0xed
 23 = 8+0xf   |   96 = 7+89    |  184 = 0xb8    |  238 = 0xee
 24 = 9+0xf   |  103 = 7|97    |  188 = 0xbc    |  242 = 7+0xeb
 25 = 78^87   |  104 = 7+97    |  191 = 0xbf    |  243 = 7+0xec
 29 = 77^80   |  111 = 77|98   |  195 = 97+98   |  244 = 7+0xed
 30 = 70^88   |  115 = 80|99   |  198 = 99+99   |  248 = 0xf8
 31 = 70^89   |  118 = 8^0x7e  |  205 = 0xcd    |  249 = 0xf9
 32 = 8<<98   |  122 = 0x7a    |  207 = 0xcf    |  250 = 0xfa
 36 = 9<<98   |  125 = 0x7d    |  208 = 0xd0    |  251 = 0xfb
 37 = 70^99   |  126 = 0x7e    |  209 = 7+0xca  |  252 = 0xfc
 38 = 77>>97  |  127 = 0x7f    |  210 = 7+0xcb  |  255 = 0xff
 42 = 98-070  |  132 = 7+0x7d  |  214 = 7+0xcf  |
 49 = 9^070   |  135 = 0x87    |  215 = 0xd7    |

```

**Note:** Bitwise shifts are processed modulo \\$32\\$. This is explicitly stated in the ECMAScript specification:

> Let *shiftCount* be the result of masking out all but the least significant 5 bits of *rnum*, that is, compute *rnum* & 0x1F.

For instance, `8<<98` really does `8<<2` (which is \\$32\\$).

# Answer
> 4 votes
## Haskell, ~~623~~ ~~617~~ ~~614~~ ~~594~~ ~~360~~ 342 bytes

Edit: -234 bytes thanks to @Lynn by finding a pattern encoding as a string. -18 bytes thanks to @Ørjan Johansen.

```
map(\i->cycle(8+8+8+8:filter(\_->" XXXX   XXX   XXXX   XXXXX   XXX    XXX   X      XXXXXX      X   X  X   X  X      X      X   X  X      XX      X   X  X   X  XXX    X  XX  X   X  X      XXXX      X   X  X   X  X      X   X  X   X  X      X XXXX   XXX   XXXX   XXXXX   XXXX   XXX   XXXXX  X"!!i>' ')(pure i))!!9)(take(0xf8+8)(iterate(9-8+)0))

```

Try it online!

How it works

```
map(\i->    )                   -- map the lambda over the
        (take(0xf8+8)           -- first 256 elements of
           (iterate(9-8+)0))    -- the list [0,1,2,....]

                                -- the lambda is:

    cycle                       -- make an infinite list by repeating the list
      8+8+8+8:                  -- wih element 32 followed by
                  pure i        -- the singleton list with 'i'
       filter                   -- but keep 'i' only if
          \_->" XXXX..."!!i>' ' -- the pattern has an 'X' at index 'i', else
                                -- remove it to make an empty list
                                -- i.e. the cycled list is, if the pattern is
                                -- a space: [32,32,32,32,32,32,32,32,32,32,...]
                                -- an 'X':  [32, i,32, i,32, i,32, i,32, i,...]
                                --                                       ^
                                --                        9th element ---/
                      !!9       -- pick the 9th element which is the result
                                -- of the lambda

```

# Answer
> 3 votes
# Brain-Flak -r, ~~4190~~ 4188 bytes

```
(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((())())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())())())())())())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())())())()<((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))>()()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())())())())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())()<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()())()<(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())>())())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())()<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()())())())())())()<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()())

```

Try it online!

This one is a little bit difficult for Brain-flak since we can't use `]` or `}`. Meaning the only useful characters are `<>()`.

Here's a Haskell program that helped me write this

It just counts up skipping where spaces need to be and pushing those individually.

# Answer
> 3 votes
# JavaScript (SpiderMonkey), ~~1001~~ ~~919~~ ~~789~~ 441 bytes

```
print(/u/.exec().map.call('0777700077700077770007777700077700007770007000000777777000000700070070007007000000700000070007007000000770000007000700700070077700007007700700070070000007777000000700070070007007000000700070070007007000000707777000777000777700077777000777700077700077777007',''.repeat.bind(Number)).map(/u/.exec().find.bind(/()/.exec().fill(Number.bind(0,88-070)).fill(/u/.exec().fill,!0),''.indexOf)).map(Map.call.bind(Map.call)))

```

Try it online!

Finally beats BF!!!

### General idea

Convert each character of the long string string to its index or 32, depends on the value.

### `Array.prototype.map`? How to get array

Brute force to see which objects are accessible by accessing object properties (because `]` is not allowed, so only properties with name matching an identifier is accessible).

`RegExp.prototype.exec` returns an array-like object when there is a match. When no argument is provided, the argument defaults to `undefined`, so `/u/.exec()` matches and return an array.

### Get 2 arbitrary distinct values on 2 different characters

We want to have `(x,y)=>x=='0'?32:y`, but we can't use `=`.

Instead, we're going to do

```
new Array(a)
    .map(x=>x=='0'?()=>32:function()this)
    .map((x,y,z)=>x.call(y,z))

```

We can `map` the string over some function, but `=>` is not allowed, so only a few functions can be used. It may have bound `this` and some bound arguments (so it has the form `(x,y,z)=>pre_filled_function.call(pre,filled,args,etc,x,y,z)`)

After considering a list of functions (`repeat exec bind create map indexOf replace fill find reduce filter findIndex call bind apply`), I decide that the following functions will be used (after considering all other combinations)

* `repeat`: number -\> different strings.
* `find`: thisArg -\> first element in array match.

The general idea would be:

```
[].map.call('07070707...', (x,y,z)=>[elem1,elem2].find(somefunction,x,y,z)

```

where `somefunction` considers the `this` argument (`x`) and the first argument (`elem1` or `elem2`) and return whether it matches.

The last arrow function is rewritten to `[].find.bind([elem1,elem2],somefunction)`.

### Array literal

We can use regex exec to get an array, and `fill` it with different values. For example `/()/.exec()` returns a length-2 array, then we can fill it as we need.

### Which `somefunction` do we need?

We need one that returns a truthy/falsy value depends on `this` (which is 1 of 2 functions we're going to return) and first argument (must be a string or array).

For that, I used `indexOf` -- it returns falsy value iff the first argument is a prefix of the `this` argument.

### Represent the function literals

# Answer
> 2 votes
# TI-Basic (83 series), 578 bytes

```
8XFact8-ΔTbl
seq(X and XX≤8+8 or 8≤X and X≤Xmax or 7+7≤X and X<9+9 or 7+7+7≤X and X<8π or 9π<X and X<πXmax or 9 nCr 7≤X and X+X<77 or X=7²-7 or 7²≤X and X≤7*9-9 or X=70-9 or X=8²+ΔTbl or X=78-Xmax or X=9*8 or X=89-7-7 or X=89-7 or X=89 or X=900-807 or X=88+8 or 809-707<X and X≤97+77-70 or 9X=999 or 8X=990-70 or X=888-770 or X=899-777 or 8*7+77-8≤X and X+X<Ans or 7²X/77=77+7 or 999+77<8X and 7X<970-9-7 or 8²X=8888+8 or X+X=99+99+88 or 7X=9099-8077 or 9+8≤X/9 and X<997-770-70 or X=99+8² or X=87+80 or X=80+90 or X=87+87 or X=87+90 or X=87+97 or X=98+90 or X=999-808 or X=97+98 or X=99+99 or X=99+99+7 or 9²8<πX and X+X+X≤70*9 or 70π-π-π<Xand X+X+X≤9²8 or 70π<X and X<70π+π or 997-770≤X and X+X+X≤99*7 or 77+79+79≤X and X+8+9≤Ans or 77π<X and X<Ans-Xmax or 7*8*9-8≤X+X and X+X≤7*8*9 or X=Ans,X,0,Ans
8XFact+Ansseq(X,X,⁻8XFact,70π+π

```

TI-Basic has its own very special "code-page" with weird design choices like moving the space character over to 0x29 so that 0x20 can be the `randM(` command.

It's tricky to figure out how to get TI-Basic to output the right kind of object. Strings wouldn't work for multiple reasons: there's no way to reference a token without using the token, and also we're not allowed the `"` character. We can't just write a list, because `{` and `}` are forbidden. We are allowed the `[` and `]` characters for matrices, but a 1 by 256 matrix doesn't work, since matrices are allowed at most 99 rows and columns. We can't use  to assign to variables, and we can't get at the list variables `ʟ` or `L₁` through `L₆` anyway.

So here, we write down a complicated logical formula with inequalities that says when a character is one of the ones we want to output. Then we use the `seq(` command to generate a list with `1` in those positions and `0` elsewhere. From there, another `seq(` command and some arithmetic finishes the job.

That was the exciting part; the rest is golfing the constants and I probably haven't done that as much as possible. One of the tricks I use is that by default, `Xmax` is 10, `XFact` is 4, and `ΔTbl` is 1.

# Answer
> 1 votes
# Brain-Flak -r, 3894 bytes

```
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())<((())((()())()))>)))(((((((()()()()()()()())(()()()()()()()()())(()()()()()()()()()())()()()()())))<((((((((()()()()()()()()()()()()()())((((((((((()()()()()()()()()()()()()()())((()()()()()()()()()()()()()()()())()))))<((((((((((((()()()()()()()()()()()()()()()()()()()()())())())())())()()()()()()())))<((((((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()())())())()))))()()()())())())>)))()()()()()()()()()())>))))))()()())())())())())())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())>)))())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())())())<((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))>()()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())())())())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())<((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))))))>()()()()()()())<(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())>()())())())())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())())())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())())())())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())())())())())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())())())())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())())())<(((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())))>()()()())())())())())<((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()))>()()())

```

Try it online!

I wrote a program to generate the optimal Brain-Flak program for any output. Assume that:

* `<>` is not used
* My program is correct

, then this solution is optimal.

However, I was a bit lazy and implement a solution that is not very hard to come up with, and it ends up running in 1m13s (takes time \\$O(n^5)\\$ or so). I may look for more efficient solution later.

# Answer
> 1 votes
# Python 2, ~~162~~ 157 bytes

*Warning*: Unprintable characters ahead!

```
print map(lambda(i,x):(x>'0'and i-0xe0/7)+0xe0/7,enumerate(bin(reduce(lambda x,y:(x<<0xd-7)-x+y,bytearray('7?QcZ;+BqiQJUS!?B0W![<LBU7X!frQd(SQdB\0')))))

```

Try it online!

Based on TFeld's existing answer, but with a few changes:

A `bytearray` is similar to a `str` that it's iterable, however, iterating it gives integers, not characters. We can use it to encode a base-N literal and `reduce(lambda x,y: x*N+y, my_bytearray)` to decode it.

Because Python 2 files don't have an encoding by default, only characters in ASCII (0..127) can be used. Null byte, newlines, backslashes and quotes take 1 more byte.

Also, it's not possible to use all bases.

I wrote a program to find the shortest representation of `n`, given those restrictions.

---
Tags: code-golf, kolmogorov-complexity, restricted-source
---


title: Sort a list, poorly

text:
# Question
Title: Sort a list, poorly
Don't you hate it when you're trying to roughly sort a list based on user data, but you have to poll the user for thousands of comparisons?

Hate no more, because the answers to this challenge are (going to be) here!

## Method

The sorted-ness of a list is defined by how many possible comparisons it has which are correct.

Let's have an example. The list `[1, 2, 4, 3]` has the possible comparisons `1 <= 2`, `1 <= 4`, `1 <= 3`, `2 <= 4`, `2 <= 3` and `4 <= 3`. 1 out of those 6 comparisons are incorrect, so this list is (5 / 6) * 100 = 83.33% sorted.

## Challenge

Create a program or function that sorts a given list (but not necessarily 100%) and sorts all of the below test cases by at least 75%.

If your program sorts a list by less than 75% that is not in the test cases, that's okay, but try not to hard-code to the test-cases although I can't ban you from doing so.

You must use a comparison sort. Pretend the numbers are black boxes that only support comparison operations.

Your program may sort the list backwards, which means if it's is able to sort all of the test cases by less than 25%, you can post it as a backwards sort.

For programs that perform STDIO, the list should be taken and printed as base-10 integers with some kind of separator, with optional text at the start and end (for example `1\n2\n3` or `[1, 2, 3]`)

You may also return or print a list of indices that correspond to the sorted list (e.g. `[1, 3, 2]` when sorted is indices `[0, 2, 1]`)

You may not compare any of the elements of the list with any constant values.

The defaults for I/O and standard loopholes apply as usual.

## Scoring

This is a , not a . Your code is scored by the highest number of comparisons your code needs to be able to sort across all of the test cases.

A comparison is defined as any operation that involves a value `x` from the given list and another value `y` which may or may not also be from the given list, and does a boolean check of one of `x < y`, `x <= y`, `x == y`, `x >= y` or `x > y` *or* returns a result depending on whether `x < y`, `x == y` or `x > y`. This includes any expressions, including mathematical equations, that have the same effect of comparison.

The test cases are here.

To verify your sorted lists, use this program.

The lowest score wins. Good luck!

# Answer
> 3 votes
# Python 3, score 244

```
def sort_func(l):
	num_pieces = 9

	medians = [median5(l[5*i : 5*(i+1)]) for i in range(num_pieces)]

	center = median(medians)

	lows = []
	highs = []

	for x in l:
		if x < center:
			lows.append(x)
		else:
			highs.append(x)

	for d in range(9):
		for lst in [lows, highs]:
			if lst[d] > lst[~d]:
				lst[d], lst[~d] = lst[~d], lst[d]

	l[:] = lows + highs

def median(lst):
	lst.sort()
	return lst[len(lst)//2]

def median5(l):
	a, b, c, d, e = l

	if a > b: a,b=b,a
	if c > d: c,d=d,c

	if a < c:
		a = e
		if a > b: a,b=b,a
	else:
		c = e
		if c > d: c,d=d,c

	if a < c:
		if b > c:return c
		else: return b
	else:
		if d > a:return a
		else: return d

```

Try it online! Thanks to user202729 for making the comparison-counting class for verification.

The algorithm has 3 parts:

* Estimate the median of the list (~76 comparisons if unlucky)
* Compare each element to the estimated median and put it in the low or high sub-list (150 comparisons, 1 per list element)
* Tweak each of the low and high lists by swapping the first and last elements if they are other of order, then the 2nd and 2nd to last, up to the 9th and 9th-to-last (18 comparisons)
* Output the concatenated low and high list

The idea is that if we knew the median of the list, we could partition the list into its low and high halves by comparing each element to the median. Then, putting the high half after the low half, any comparison between elements from different halves is correct. On average half the within-half comparisons happen to be right, so a random comparison has about a 75% chance of being correct overall.

Sometimes though we get unlucky in the random comparisons for a given list. So, we improve each half a little by swapping the first and last element if they happen to be out of order, since this is the highest-impact swap for one comparison. Then, do the same for the 2nd and 2nd-to-last element, and so on. It turns out that doing this for 9 elements on each end for each half is enough to bring us over the 75% mark for all the test cases.

The median used is an estimate, since finding the actual median is too expensive, which also contributed to getting worse-than-average scores. It's estimated by taking 9 groups of 5 elements, finding the median of each, and then finding the median of those values.

The median of 5 is found using an worst-case-optimized algorithm that uses a maximum of 6 comparisons. The median of 9 is computed naively by sorting, which is surely inefficient. There are algorithms that use 14 comparisons in the worst cases, but I haven't found code for one.

A potential improvement would be to used the information gained in the median-finding step in the sorting step. We already know how the median compares to itself, the 8 other elements in the list of medians, and the 4 other elements in its group. This would save 13 comparisons, for a score of 231.

Further information could be gleaned using elements that were found smaller (resp, bigger) than a median that is itself smaller than the median-of-medians. We could also put each element used in the median finding into its estimated rank position in the final list.

Another potential improvement would be to use the full `cmp` comparisons rather than just `<` to better handle the case when elements are equal, for exactly by putting elements equal to the estimate median into the middle.

# Answer
> 3 votes
# Python 3, score = ~~172~~ 164

```
def shell(a, cmp):
    for step in [148, 138, 107, 43]:
        for i in range(len(a) - step):
            if cmp(a[i], a[i + step]) > 0:
                a[i], a[i + step] = a[i + step], a[i]

```

Try it online!

Four passes of Shellsort.

# Python 3, score = ~~229~~ 196

```
def insert(x, a, cmp):
    if not a:
        return [x]
    m = len(a)//2
    c = cmp(x, a[m])
    if c < 0:
        return insert(x, a[:m], cmp) + a[m:]
    elif c > 0:
        return a[:m + 1] + insert(x, a[m + 1:], cmp)
    else:
        return a[:m] + [x] + a[m:]

def ford_johnson(a, cmp):
    if len(a) <= 1:
        return a
    m = len(a)//2
    cmp1 = lambda x, y: cmp(x[-1], y[-1])
    b = ford_johnson([insert(x, [y], cmp) for x, y in zip(a[:m], a[m:2*m])], cmp1)
    if len(a) % 2:
        b += [[a[-1], None]]
    for k in range(m, len(a)):
        l, i, (x, y) = max((-i.bit_length(), i, t) for i, t in enumerate(b) if len(t) == 2)
        b[:i + 1] = insert([x], b[:i], cmp1) + [[y]]
    if len(a) % 2:
        b.pop()
    return [x for x, in b]

def thirty_four(a, cmp):
    for i in range(34):
        a[i::34] = ford_johnson(a[i::34], cmp)

```

Try it online!

Consider the list as 34 interleaved lists and sort each independently, using the Ford–Johnson merge-insertion sort.

# Answer
> 0 votes
# Python 3, score 757

```
def f(l):
	a = 0  # we are going to sort the first (a) elements
	n = len(l)
	while (
			a*(a-1)//2  # there are ~ pairs that is guaranteed to be in order
			<=
			n*(n-1)//2  # total number of pairs
			*0.75):  # it's possible to compute this in O(1), but I'm lazy
		a+=1
	return sorted(l[:a])+l[a:]

```

Try it online!

The solution simply sorts about first ~75% of the array, so that it's guaranteed to be valid.

Python `sorted` takes about O(n log n) comparison.

# Answer
> 0 votes
# JavaScript (Node.js), 669

```
cnt=0;
function wtf(arr){return arr.length*~-arr.length}
function finished(arr) {
  x = 150*149*.25; // toleration
  for (i in arr) x-=wtf(arr[i]);
  return x>=0;
}
function cut(arr) {
  rnd=(Math.sin(arr.length)*1237812731+127317823102)%arr.length|0;
  tmp=[[],[arr[rnd]], []];
  for(i=0; i<arr.length; i++) if(i!=rnd) {
    cnt++;
    //tmp[arr[i]<arr[0]?0:1].push(arr[i]);
    if(arr[i]<arr[rnd]) tmp[0].push(arr[i]); else
    if(arr[i]>arr[rnd]) tmp[tmp.length-1].push(arr[i]); else
    tmp.splice(1,0,[arr[i]]);
  }
  //console.log(arr.length+','+t)
  return tmp;
}
function nesort(arr) {
  e=[arr];
  while(!finished(e)){
    x*=-5;
    t=0;
    for(i in e) if(e[i].length>e[t].length)t=i;
    for(i in e) if(e[i].length<e[t].length && wtf(e[i])>x)t=i;
    e.splice(t,1,...cut(e[t]));
  }
  return (e+'').match(/\d+/g).map(parseFloat);
}

```

Try it online!

---
Tags: code-challenge, array
---


title: Arbitrary Randomness

text:
# Question
Title: Arbitrary Randomness
Randomness is fun. Challenges with no point are fun.

Write a function that, given integer input `n`, will output a **set** (unordered, unique) of exactly `n` random integers between `1` and `n^2` (inclusive) such that the sum of all integers is equal to `n^2`.

Randomness does *not* have to be uniform, provided each valid set has a non-zero chance to occur.

Shortest answer in bytes (per each language) wins.

## Examples

```
Input (n) = 1, Target (n^2) = 1
Sample of possible outputs:
1

Input = 2, Target = 4
Sample of possible outputs:
3, 1
1, 3

Input = 3, Target = 9
Sample of possible outputs:
6, 1, 2
3, 5, 1
4, 3, 2

Input = 4, Target = 16
Sample of possible outputs:
1, 3, 5, 7
2, 4, 1, 9
8, 3, 1, 4

Input = 5, Target = 25
Sample of possible outputs:
11, 4, 7, 1, 2
2, 3, 1, 11, 8
6, 1, 3, 7, 8

Input = 8, Target = 64
Sample of possible outputs:
10, 3, 9, 7, 6, 19, 8, 2
7, 16, 2, 3, 9, 4, 13, 10
7, 9, 21, 2, 5, 13, 6, 1

```

**Bonus Task:** Is there a formula to calculate the number of valid permutations for a given `n`?

# Answer
> 9 votes
# Brachylog (v2), 15 bytes (random) or 13 bytes (all possibilities)

## Random

```
~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

```

Try it online!

Function submission (seen in TIO with a wrapper making it into a full program).

### Explanation

```
~lℕ₁ᵐA+√?∧A≜₁ᵐ≠
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              and it is composed entirely of
  ℕ₁                 integers ≥ 1,
       √           for which the square root of the
      +              sum of the list
        ?              is the input.
     A   ∧A      Restricting yourself to lists with that property,
           ≜₁      pick random possible values
             ᵐ       for each element in turn,
              ≠    until you find one whose elements are all distinct.

```

## All possibilities

```
~lℕ₁ᵐ<₁.+√?∧≜

```

Try it online!

Function submission, which generates all possible outputs.

### Explanation

```
~lℕ₁ᵐ<₁.+√?∧≜
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              it is composed entirely of
  ℕ₁                 integers ≥ 1,
     <₁            it is strictly increasing,
         √         and the square root of the
        +            sum of the list
          ?            is the input.
       .   ∧≜    Generate all specific lists with that property.

```

I'm fairly surprised that `∧≜` works (you'd normally have to write `∧~≜` in order to brute-force the output rather than the input), but it turns out that  has an input=output assumption so it doesn't matter which way round you run it.

## Bonus task

In order to get some insight into the sequence of the number of possibilities, I created a different TIO wrapper which runs the program on successive integers to give the sequence of output counts:

```
1,1,3,9,30,110,436,1801,7657,33401

```

A trip to OEIS discovers that this is already a known sequence, A107379, described pretty much as in the question (apparently you get the same sequence if you restrict it to odd numbers). The page lists several formulas for the sequence (although none is particularly simple; the second looks like a direct formula for the value but I don't understand the notation).

# Answer
> 7 votes
# 05AB1E, 11 bytes

```
nÅœʒDÙQ}sùΩ

```

Try it online or verify all test cases.

**Explanation:**

```
n             # Take the square of the (implicit) input
              #  i.e. 3 → 9
 Åœ           # Get all integer-lists using integers in the range [1, val) that sum to val
              #  i.e. 9 → [[1,1,1,1,1,1,1,1,1],...,[1,3,5],...,[9]]
   ʒ   }      # Filter the list to only keep lists with unique values:
    D         # Duplicate the current value
     Ù        # Uniquify it
              #  i.e. [2,2,5] → [2,5]
      Q       # Check if it's still the same
              #  i.e. [2,2,5] and [2,5] → 0 (falsey)
        s     # Swap to take the (implicit) input again
         ù    # Only leave lists of that size
              #  i.e. [[1,2,6],[1,3,5],[1,8],[2,3,4],[2,7],[3,6],[4,5],[9]] and 3
              #   → [[1,2,6],[1,3,5],[2,3,4]]
          Ω   # Pick a random list from the list of lists (and output implicitly)

```

# Answer
> 5 votes
# , ~~68, 75~~ 48 bytes (random) and 70 bytes (deterministic)

@Giuseppe's rejection sampling method:

```
function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}

```

Try it online!

Golfed original:

```
function(n,m=combn(1:n^2,n))m[,sample(which(colSums(m)==n^2)*!!1:2,1)]

```

Try it online!

The `*!!1:2` business is to avoid the odd way `sample` act when the first argument has length 1.

# Answer
> 5 votes
# Python (2 or 3), 85 bytes

```
def f(n):r=sample(range(1,n*n+1),n);return(n*n==sum(r))*r or f(n)
from random import*

```

**Try it online!**

# Answer
> 4 votes
# Jelly, 9 bytes

```
²œcS=¥Ƈ²X

```

Try it online!

Generate all n-combinations of the list \[1..n²\], filter to keep those with sum n², then pick a random one.

# Answer
> 4 votes
# Java 10, ~~250~~ ~~242~~ 222 bytes

```
import java.util.*;n->{for(;;){int i=n+1,r[]=new int[i],d[]=new int[n];for(r[n<2?0:1]=n*n;i-->2;r[i]=(int)(Math.random()*n*n));var S=new HashSet();for(Arrays.sort(r),i=n;i-->0;)S.add(d[i]=r[i+1]-r[i]);if(!S.contains(0)&S.size()==n)return S;}}

```

-20 bytes thanks to *@nwellnhof*.

Watch out, Java coming through.. It's 'only' five times as long as the other four answers combined, so not too bad I guess.. rofl.
It does run `n=1` through `n=25` (combined) in less than 2 seconds though, so I'll probably post a modified version to the speed version of this challenge (that's currently still in the Sandbox) as well.

Try it online.

**Explanation:**

In pseudo-code we do the following:

1) Generate an array of size `n+1` containing: `0`, `n` squared, and `n-1` amount of random integers in the range `[0, n squared)`
2) Sort this array
3) Create a second array of size `n` containing the forward differences of pairs
These first three steps will give us an array containing `n` random integers (in the range `[0, n squared)` that sum to `n` squared.
4a) If not all random values are unique, or any of them is 0: try again from step 1
4b) Else: return this differences array as result

As for the actual code:

```
import java.util.*;      // Required import for HashSet and Arrays
n->{                     // Method with int parameter and Set return-type
  for(;;){               //  Loop indefinitely
    int i=n+1,           //   Set `i` to `n+1`
        r[]=new int[i];  //   Create an array of size `n+1`
    var S=new HashSet(); //   Result-set, starting empty
    for(r[n<2?           //   If `n` is 1:
           0             //    Set the first item in the first array to:
          :              //   Else:
           1]            //    Set the second item in the first array to:
             =n*n;       //   `n` squared
        i-->2;)          //   Loop `i` in the range [`n`, 2]:
      r[i]=              //    Set the `i`'th value in the first array to:
           (int)(Math.random()*n*n);
                         //     A random value in the range [0, `n` squared)
    for(Arrays.sort(r),  //   Sort the first array
        i=n;i-->0;)      //   Loop `i` in the range (`n`, 0]:
      S.add(             //    Add to the Set:
        r[i+1]-r[i]);    //     The `i+1`'th and `i`'th difference of the first array
    if(!S.contains(0)    //   If the Set does not contain a 0
       &S.size()==n)     //   and its size is equal to `n`:
      return S;}}        //    Return this Set as the result
                         //   (Implicit else: continue the infinite loop)

```

# Answer
> 4 votes
# Perl 6, 41 bytes

```
{first *.sum==$_²,(1..$_²).pick($_)xx*}

```

Try it online!

* `(1 .. $_²)` is the range of numbers from 1 to the square of the input number
* `.pick($_)` randomly chooses a distinct subset of that range
* `xx *` replicates the preceding expression infinitely
* `first *.sum == $_²` selects the first of those number sets that sums to the square of the input number

# Answer
> 2 votes
# Pyth, ~~13~~ 12 bytes

```
Ofq*QQsT.cS*

```

Try it online here. Note that the online interpreter runs into a MemoryError for inputs greater than 5.

```
Ofq*QQsT.cS*QQQ   Implicit: Q=eval(input())
                 Trailing QQQ inferred
          S*QQQ   [1-Q*Q]
        .c    Q   All combinations of the above of length Q, without repeats
 f                Keep elements of the above, as T, where the following is truthy:
      sT            Is the sum of T...
  q                 ... equal to...
   *QQ              ... Q*Q?
O                 Choose a random element of those remaining sets, implicit print

```

*Edit: saved a byte by taking an alternative approach. Previous version:* `Of&qQlT{IT./*`

# Answer
> 2 votes
# Python 3, ~~136 134 127 121~~ 114 bytes

```
from random import*
def f(n):
	s={randint(1,n*n)for _ in range(n)}
	return len(s)==n and sum(s)==n*n and s or f(n)

```

Try it online!

A commenter corrected me, and this now hits recursion max depth at f(5) instead of f(1). Much closer to being a real competing answer.

I've seen it do f(5) *once*, and I'm working on trying to implement this with shuffle.

I tried making some lambda expressions for `s=...`, but that didn't help on bytes. Maybe someone else can do something with this: `s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)`

Thanks to Kevin for shaving off another 7 bytes.

# Answer
> 2 votes
# APL (Dyalog Unicode), 20 bytesSBCS

Anonymous prefix lambda.

```
{s=+/c←⍵?s←⍵*2:c⋄∇⍵}

```

Try it online!

`{``}` "dfn";  is argument

`⍵*2` square the argument

`s←` assign to `s` (for **s**quare)

`⍵?` find `n` random indices from 1…`s` without replacement

`c←` assign to `c` (for **c**andidate)

`+/` sum them

`s=` compare to `s`

`:` if equal

`c` return the candidate

else

`∇⍵` recurse on the argument

# Answer
> 2 votes
# APL (Dyalog Classic), 18 bytes

```
(≢?≢×≢)⍣(0=+.-∘≢)⍳

```

Try it online!

uses `⎕io←1`

generates the numbers `1 2 ... n`

`(`...`)⍣(`...`)` keep applying the function on the left until the function on the right returns true

length, i.e. `n`

`≢?≢×≢` choose randomly `n` distinct integers between 1 and `n`2

`+.-∘≢` subtract the length from each number and sum

`0=` if the sum is 0, stop looping, otherwise try again

# Answer
> 1 votes
# Japt, 12 bytes

```
²õ àU ö@²¥Xx

```

Try it

```
                 :Implicit input of integer U
²                :U squared
 õ               :Range [1,U²]
   àU            :Combinations of length U
      ö@         :Return a random element that returns true when passed through the following function as X
        ²        :  U squared
         ¥       :  Equals
          Xx     :  X reduced by addition

```

# Answer
> 1 votes
# MATL, ~~18~~ 13 bytes

```
`xGU:GZrtsGU-

```

Try it online!

```
`	# do..while:
x	# delete from stack. This implicitly reads input the first time
	# and removes it. It also deletes the previous invalid answer.
GU:	# paste input and push [1...n^2]
GZr	# select a single combination of n elements from [1..n^2]
tsGU-	# is the sum equal to N^2? if yes, terminate and print results, else goto top

```

# Answer
> 1 votes
# Java (JDK), 127 bytes

```
n->{for(int s;;){var r=new java.util.TreeSet();for(s=n*n;s>0;)r.add(s-(s-=Math.random()*n*n+1));if(r.size()==n&s==0)return r;}}

```

Try it online!

Infinite loop until a set with the criteria matches.

I hope you have the time, because it's very sloooooow! It can't even go to 10 without timing out.

# Answer
> 1 votes
## JavaScript, ~~647~~ ~~291~~ ~~261~~ ~~260~~ ~~259~~ ~~251~~ 239 bytes

*Thanks to @Veskah for -10 bytes at original version and "Oh yeah, you're outputting all the sets whereas the challenge asks for a random one to be returned"*

```
(n,g=m=n**2,r=[...Array(g||1)].map(_=>m--).sort(_=>.5-Math.random()).slice(-n),c=_=>eval(r.join`+`),i=_=>r.includes(_))=>[...{*0(){while(g>1&&c()!=g){for(z of r){y=c();r[m++%n]=y>g&&!(!(z-1)||i(z-1))?z-1:y<g&&!i(z+1)?z+1:z}}yield*r}}[0]()]

```

Try it online!

Create an array of `n^2` 1-based indexes, sort array randomly, slice `n` elements from array. While the sum of the random elements does not equal `n^2` loop array of random elements; if sum of array elements is greater than `n^2` and current element `-1` does not equal zero or current element `-1` is not in current array, subtract `1`; if sum of array is less than `n^2` and current element `+1` is not in array, add `1` to element. If array sum is equal to `n^2` break loop, output array.

# Answer
> 1 votes
## Batch, ~~182~~ 145 bytes

```
@set/an=%1,r=n*n,l=r+1
@for /l %%i in (%1,-1,1)do @set/at=n*(n-=1)/2,m=(r+t+n)/-~n,r-=l=m+%random%%%((l-=x=r+1-t)*(l^>^>31)+x-m)&call echo %%l%%

```

Explanation: Calculates the minimum and maximum allowable pick, given that the numbers are to be picked in descending order, and chooses a random value within the range. Example for an input of `4`:

* We start with 16 left. We can't pick 11 or more because the remaining 3 picks must add to at least 6. We also need to pick at least 6, because if we only pick 5, the remaining 3 picks can only add to 9, which isn't enough for 16. We pick a random value from 6 to 10, say 6.
* We have 10 left. We can't pick 8 or more because the remaining 2 picks must add to at least 3. As it happens, we can't pick 6 or more because we picked 6 last time. We also need to pick at least 5, because if we only pick 4, the remaining 2 picks can only add to 5, for a grand total of 15. We pick a random value from 5 to 5, say 5 (!).
* We have 5 left. We can't pick 5 or more because the remaining pick must add to at least 1, and also because we picked 5 last time. We also need to pick at least 3, because if we only pick 2, the remaining pick can only be 1, for a grand total of 14. We pick a random value from 3 to 4, say 4.
* We have 1 left. As it turns out, the algorithm chooses a range of 1 to 1, and we pick 1 as the final number.

# Answer
> 0 votes
# Japt, 20 bytes

```
²õ ö¬oU íUõ+)Õæ@²¥Xx

```

Try it online!

Extremely heavily takes advantage of "Non-uniform" randomness, almost always outputs the first `n` odd numbers, which happens to sum to `n^2`. In theory it can output any other valid set, though I've only been able to confirm that for small `n`.

Explanation:

```
²õ                      :Generate the range [1...n^2]
   ö¬                   :Order it randomly
     oU                 :Get the last n items
        í   )Õ          :Put it in an array with...
         Uõ+            : The first n odd numbers
              æ_        :Get the first one where...
                  Xx    : The sum
                ²¥      : equals n^2

```

# Answer
> 0 votes
# C (gcc), ~~128~~ 125 bytes

```
p(_){printf("%d ",_);}f(n,x,y,i){x=n*n;y=1;for(i=0;++i<n;p(y),x-=y++)while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(x);}

```

Try it online!

-3 bytes thanks to ceilingcat

NOTE: The probability is very very far from uniform. See explanation for what I mean and a better means to test that it works (by making the distribution closer to uniform \[but still a far cry from it\]).

### How?

The basic idea is to only choose increasing numbers so as to not worry about duplicates. Whenever we pick a number we have a non-zero chance of 'skipping' it if allowable.

To decide if we can skip a number we need to know `x` the total left to be reached, `k` the number of elements we still have to use, and `y` the current candidate value. The smallest possible number that we could still pick would consist of $$y+(y+1)+(y+2)+...$$ added to the current value. In particular we require the above expression to be less than `x`. The formula will be $$\frac{k(k+1)}{2}+k(y+1)+y\<x$$ Unfortunately we have to be a bit careful about rearranging this formula due to integer truncation in C, so I couldn't really find a way to golf it.

Nonetheless the logic is to have a chance to discard any `y` that satisfies the above equation.

### The code

```
p(_){printf("%d ",_);}  // Define print(int)
f(n,x,y,i){             // Define f(n,...) as the function we want
    x=n*n;              // Set x to n^2
    y=1;                // Set y to 1
    for(i=0;++i<n;){    // n-1 times do...
        while(rand()&&  // While rand() is non-zero [very very likely] AND
            (n-i)*      // (n-i) is the 'k' in the formula
            (n-i+1)/2+  // This first half takes care of the increment
            (n-i)*(y+1) // This second half takes care of the y+1 starting point
            +y<x)       // The +y takes care of the current value of y
        y++;            // If rand() returned non-zero and we can skip y, do so
    p(y);               // Print y
    x-=y++;             // Subtract y from the total and increment it
    }p(x);}             // Print what's left over.

```

The trick I mentioned to better test the code involves replacing `rand()&&` with `rand()%2&&` so that there is a 50-50 chance that any given y is skipped, rather than a 1 in `RAND_MAX` chance that any given y is used.

# Answer
> 0 votes
# Ruby, 46 bytes

```
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}

```

Try it online!

# Answer
> 0 votes
# Clean, 172 bytes

```
import StdEnv,Math.Random,Data.List
? ::!Int->Int
?_=code{
ccall time "I:I"
}
$n=find(\s=length s==n&&sum s==n^2)(subsequences(nub(map(inc o\e=e rem n^2)(genRandInt(?0)))))

```

Try it online!

# Answer
> 0 votes
# Python (2 or 3), 84 bytes

```
from random import*;l=lambda n,s=[]:(sum(s)==n*n)*s or l(n,sample(range(1,n*n+1),n))

```

**Try it online!**

Hits max recursion depth at around l(5)

# Answer
> 0 votes
# Mathematica 40 bytes

```
RandomChoice[IntegerPartitions[n^2, {n}]]

```

# Answer
> 0 votes
# Kotlin, 32 bytes

```
{(1..it*it).shuffled().take(it)}

```

Try it online!

# Answer
> 0 votes
# Wolfram Language (Mathematica), 49 bytes

```
(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&

```

Try it online!

Golfed version by @J42161217.

---

# Wolfram Language (Mathematica), 62 bytes

```
Range[#-1,0,-1]+RandomChoice@IntegerPartitions[#*(#+1)/2,{#}]&

```

Try it online!

### How it works

Mainly based on this Math.SE question. In order to get partitions of \\$n^2\\$ into \\$n\\$ distinct parts, get partitions of \\$n^2 - (n^2-n)/2 = (n^2+n)/2\\$ instead and add \\$0 \cdots n-1\\$ to each element. Since Mathematica gives the partitions in decreasing order, \\$n-1 \cdots 0\\$ is added instead.

---

# The answer to the Bonus Task

> **Bonus Task:** Is there a formula to calculate the number of valid permutations for a given `n`?

Yes. Define \\$part(n,k)\\$ as the number of partitions of \\$n\\$ into exactly \\$k\\$ parts. Then it satisfies the following recurrence relation:

$$ part(n,k) = part(n-1,k-1) + part(n-k,k) $$

You can understand it as "If a partition contains a 1, remove it; otherwise, subtract 1 from every term". More explanation here on another Math.SE question. Combined with the initial conditions \\$ part(n,1) = 1 \\$ and \\$ n \< k \Rightarrow part(n,k) = 0 \\$, you can compute it with a program. The desired answer will be:

$$ part(\frac{n^2+n}{2}, n) $$

which is, in Mathematica:

```
Length@IntegerPartitions[#*(#+1)/2,{#}]&

```

Try it online!

---
Tags: code-golf, random, combinatorics
---


title: Fibonacci with n numbers instead of 2

text:
# Question
Title: Fibonacci with n numbers instead of 2
## How to

Given an integer `n` start with `n` ones (i.e. 4 -\> `1 1 1 1`). Then sum up the last `n` numbers, and repeat.

For `n = 4` this looks like this:

Start with `1 1 1 1`, sum up the last 4 numbers resulting in `1 1 1 1 4`, then sum up the last 4 numbers resulting in `1 1 1 1 4 7`, then sum up the last 4 numbers resulting in `1 1 1 1 4 7 13` and so on.

## The task

Write a program or function that produces the first 30 numbers of this sequence given `n` as input (either as argument, stdin, command line argument, on the stack, ...)

The 30 terms for n = 4 are:

`1 1 1 1 4 7 13 25 49 94 181 349 673 1297 2500 4819 9289 17905 34513 66526 128233 247177 476449 918385 1770244 3412255 6577333 12678217 24438049 47105854`

The 30 terms for n = 5 are:

`1 1 1 1 1 5 9 17 33 65 129 253 497 977 1921 3777 7425 14597 28697 56417 110913 218049 428673 842749 1656801 3257185 6403457 12588865 24749057 48655365`

In case `n` is smaller than two or larger than 30 the behaviour can be undefined.

# Answer
> 2 votes
# JavaScript (ES6), 64 bytes

```
f=(n,i,a=[])=>i>29?a:f(n,-~i,[...a,(g=_=>n--&&a[--i]+g())()||1])

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 12 bytes

```
Å1 30FDO¸«ć,

```

Try it online!

**Explanation**

```
Å1            # push a list of n 1s
  30F         # 30 times do:
     D        # duplicate
      O       # sum
       ¸«     # append
         ć,   # extract and print the head

```

# Answer
> 1 votes
# Tidy, 35 bytes

```
{x:30^recur(*tile(x,c(1)),sum@c,x)}

```

Try it online!

## Explanation

```
{x:30^recur(*tile(x,c(1)),sum@c,x)}
{x:                               }   lambda taking parameter `x`
   30^                                take the first 30 terms of...
      recur(                     )        a recursive function
            *tile(x,c(1))                 whose seed is `x` `1`s
                                x         with a window of `x`
                          sum@c           and the functor takes the sum of its arguments

```

# Answer
> 1 votes
# Python 2, 60 bytes

```
lambda n:reduce(lambda a,c:a+[sum(a[-n:])],'.'*(30-n),[1]*n)

```

Try it online!

# Answer
> 1 votes
# Clean, 81 bytes

```
import StdEnv
$n=reverse(while((>)30o length)(\l=[sum(take n l):l])(repeatn n 1))

```

Try it online!

`(repeatn n 1)` gives us `n` ones in a list, which we repeatedly prepend the sum of the first `n` elements to (with `(\l=[sum(take n l):l])`), while it has less than 30 elements.
As the list is backwards, we reverse it and return.

---
Tags: code-golf, fibonacci
---


title: Shortest Unique Substring

text:
# Question
Title: Shortest Unique Substring
Given (on STDIN, as command line arguments, or as function arguments) two distinct non-empty strings, find and return the shortest substring of the first string which is not a substring of the second. If no such substring exists, you may return the empty string, return any string which isn't a substring of the original string, or throw an exception. If you are returning from a function, you may also return null (or undefined, None, etc.) in this case. If multiple such substrings are tied for the shortest, you may return any one of them.

Strings can consist of any printable ascii characters.

Input given on STDIN will be given with one string on each line. At your request, a single empty line may be added at the end of the input.

This is code golf, so the shortest valid program wins.

# SOME TEST CASES

INPUT:

```
STRING ONE
STRING TWO

```

OUTPUT:

```
E

```

INPUT:

```
A&&C
A&$C

```

VALID OUTPUTS:

```
&&
&C

```

INPUT:

(Two randomly-generated 80-letter strings)

```
QIJYXPYWIWESWBRFWUHEERVQFJROYIXNKPKVDDFFZBUNBRZVUEYKLURBJCZJYMINCZNQEYKRADRYSWMH
HAXUDFLYFSLABUCXUWNHPSGQUXMQUIQYRWVIXGNKJGYUTWMLLPRIZDRLFXWKXOBOOEFESKNCUIFHNLFE

```

ALL VALID OUTPUTS:

```
AD
BJ
BR
CZ
DD
EE
ER
EY
EY
FF
FJ
FW
FZ
HE
IJ
IN
IW
JC
JR
JY
KL
KP
KR
KV
LU
MH
MI
NB
NQ
OY
PK
PY
QE
QF
QI
RA
RB
RF
RO
RV
RY
RZ
SW
UE
UH
UN
UR
VD
VQ
VU
WB
WE
WI
WU
XN
XP
YI
YK
YK
YM
YS
YW
YX
ZB
ZJ
ZN
ZV

```

# Answer
# Brachylog, 23 bytes

```
:1foh.,{,.[A:B]hs?'~sB}

```

Works on the old Java transpiler. Expects the two strings in a list as input, unifies the output with the substring. If no substring is found, returns false.

Unfortunately I have not yet coded the subset built-in in the new Prolog transpiler.

### Explanation

```
:1f               Find all bindings which satisfy predicate 1 with that binding as input and
                  with the Input of the main predicate as output.
   oh.,           Order that list of bindings, and unify the output with the first one.

{
 ,.[A:B]          Unify the output with the list [A,B]
        hs?       Unify the input with a subset of A
           '~sB   Check that no subset of B can be unified with the input
               }

```
> 4 votes

# Answer
# Python, ~~119~~ ~~115~~ 91

```
lambda a,b:[a[m:m+n]for n in range(1,len(a)+1)for m in range(len(a))if a[m:m+n]not in b][0]

```

Test cases:

```
| Input 1  | Input 2     | Output        |
|----------+-------------+---------------|
| 'abcd'   | 'abc'       |  'd'          |
| 'abcd'   | 'dabc'      |  'cd'         |
| 'abcd'   | 'dcbabbccd' |  'abc'        |
| 'abcdf'  | 'abcdebcdf' |  'abcdf'      |
| 'abc'    | 'abc'       |  (IndexError) |

```

Working on making it shorter, but this is my brain instinct. Not really much of a golfer yet.

Thanks to @user81655 and @NonlinearFruit for the extra bytes.

**Edit**:

Dang. Tried this code:

```
def z(a,b):
 for s in [a[m:m+n]for n in range(1,len(a)+1)for m in range(len(a)-n+1)]:
  if s not in b:return s
 return''

```

Thought it was a few bytes shorter. Turns out it was 1 byte longer than what I had before the edit.
> 4 votes

# Answer
# Python, ~~87~~ 86 bytes

```
lambda s,t,e=enumerate:[s[i:i-~j]for j,_ in e(s)for i,_ in e(s)if(s[i:i-~j]in t)<1][0]

```

If it exists, this will return the leftmost of all shortest unique substrings.

If there is no unique substring, an *IndexError* is raised.

Test it on Ideone.
> 3 votes

# Answer
## JavaScript (ES6), 79 bytes

```
f=
(a,b)=>[...a].some((_,i,c)=>c.some((_,j)=>b.indexOf(s=a.substr(j,i+1))<0))?s:''
```

```
<div oninput=o.textContent=f(a.value,b.value)><input id="a"/><input id="b"/><pre id=o>
```

If returning `false` is acceptable, save 2 bytes by using `&&s` instead of `?s:''`.
> 3 votes

# Answer
# Python, 82 bytes

```
g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''}
f=lambda s,t:min(g(s)-g(t),key=len)

```

Usage: `f('A&&C', 'A&$C')` -\> returns `'&&'`

Raises ValueError if there is no suitable substring.

Explanation:

`g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''}` recursively creates a set of the substrings of `u` `f=lambda s,t:min(g(s)-g(t),key=len)` takes the shortest substring from the set difference
> 3 votes

# Answer
# Pyth, 11 bytes

```
Jwhf!}TJ.:z

```

Try it online!
> 1 votes

# Answer
# JavaScript (Firefox), 80 bytes

```
solution=

a=>b=>[for(_ of(i=0,a))for(_ of(j=!++i,a))if(b.includes(s=a.substr(j++,i)))s][0]

document.write("<pre>"+
[ [ "test", "best" ], [ "wes", "west" ], [ "red", "dress" ] ]
.map(c=>c+": "+solution(c[0])(c[1])).join`\n`)
```

Test works only in Firefox. Returns `undefined` if there is no substring.
> 1 votes

# Answer
## Retina, 37 bytes

```
M!&`\G(.+?)(?!.*¶.*\1)
O$#`.+
$.&
G1`

```

Output is empty if no valid substring is found in `A`.

Try it online! (Slightly modified to run several test cases at once. The input format is actually linefeed separated, but test suites are easiest to write with one test case per line. The test framework turns the space into a linefeed before the actual code starts.)

### Explanation

```
M!&`\G(.+?)(?!.*¶.*\1)

```

For each possible starting position in `A`, match the shortest substring which does not appear in `B`. The `&` is for overlapping matches, such that we actually try every starting position, even if a match is longer than one character. The `\G` ensures that we don't skip any positions - in particular, this way we have to stop at the linefeed, such that we don't get additional matches from `B` itself. The reason this doesn't mess things up is actually quite subtle: because if there's a starting position in `A` where we can't find any valid substring, then that's also a failure which will cause `\G` to stop checking any further positions. However, if (from the current starting position) all substrings appear in `B`, so will all substrings that start further right of the current position, so discarding those is not an issue (and actually improves performance).

Due to the `M!` configuration, all of these matches will be returned from the stage, joined with linefeeds.

```
O$#`.+
$.&

```

This sorts the lines of the previous result by length. This is done by matching the line with `.+`. Then `$` activates a form of "sort-by", such that the match is substituted with `$.&` for determining sort order. The `$.&` itself replaces the match with its length. Finally, the `#` option tells Retina to sort numerically (otherwise, it would treat the resulting numbers as strings and sort them lexicographically).

```
G1`

```

Finally, we simply keep only first line, by using a grep stage with an empty regex (which always matches) and a limit of `1`.
> 1 votes

# Answer
# Perl, ~~87~~ 85

```
sub{(grep{$_[1]!~/\Q$_/}map{$}=$_;map{substr($_[0],$_,$})}@}}(@}=0..length$_[0]))[0]}

```

This is an anonymous function which returns the first (by position) of the shortest substrings of `$_[0]` that do not occur in `$_[1]`, or `undef` if no such substring exists.

Test program with strings taken from @iAmMortos's answer, tested with Perl 5.22.1:

```
#!/usr/bin/perl -l
use strict;
use warnings;

my $f = <see above>;
print $f->('abcd', 'abc');
print $f->('abcd', 'dabc');
print $f->('abcd', 'dcbabbccd');
print $f->('abcdf', 'abcdebcdf');
print $f->('abc', 'abc');

```
> 1 votes

# Answer
## Haskell, 72 bytes

```
import Data.Lists
a#b=argmin length[x|x<-powerslice a,not$isInfixOf x b]

```

Usage example: `"abcd" # "dabc"`-\> `"cd"`.

A straightforward implementation: build all substrings of `a` and keep those which do not appear in `b`. `argmin` returns an element of a list which minimizes the function given a the 2nd argument, here: `length`.
> 1 votes

# Answer
# Pyth - ~~9~~ 6 bytes

```
h-Fm.:

```

Try it online here.
> 0 votes

# Answer
## C#, 152 bytes

```
string f(string a,string b){int x=a.Length;for(int i=1;i<=x;i++)for(int j=0;j<=x-i;j++){var y=a.Substring(j,i);if(!b.Contains(y))return y;}return null;}

```
> 0 votes

# Answer
# Ruby, 70 bytes

Collects all substrings of a certain length from the first string, and if there is one that isn't in the second string, return it.

```
->a,b{r=p;(1..l=a.size).map{|i|(0...l).map{|j|b[s=a[j,i]]?0:r||=s}};r}

```
> 0 votes

# Answer
## Burlesque - 26 bytes

Right now the shortest way I can come up with is:

```
lnp^sujbcjz[{^p~[n!}f[-][~

```
> 0 votes

# Answer
# Japt, 14 bytes

```
Êõ!ãU c k!èV g

```

Try it online!

Returns `undefined` if there is no valid substring. This is distinct from returning the string "undefined", though the difference is only visible because of the -Q flag.

Explanation:

```
Ê                 :Length of the first input
 õ                :For each number in the range [1...length]:
  !ãU             : Get the substrings of the first input with that length
      c           :Flatten to a single array with shorter substrings first
        k         :Remove ones which return non-zero to:
         !èV      : Number of times that substring appears in second input
             g    :Return the shortest remaining substring

```
> 0 votes

# Answer
# Japt `-h`, 11 bytes

```
à f@øX «VøX

```

Try it

```
                :Implicit input of strings U & V
à               :All combinations of U
  f@            :Filter each as X
    øX          :  Does U contain X?
       «        :  Logical AND with the negation of
        VøX     :  Does V contain X?
                :Implicit output of last element

```
> 0 votes

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