title: Implement bottom (encode)

text:
# Question
Title: Implement bottom (encode)
# Challenge

The challenge is to implement the bottom encoding (only encoding, not decoding). There is a wide variety of existing implementations in the bottom-software-foundation org.

Bottom is a text encoding where each character is separated into multiple emoji.

| Unicode escape(s) | Character | Value |
| --- | --- | --- |
| `U+1FAC2` |  | 200 |
| `U+1F496` |  | 50 |
| `U+2728` |  | 10 |
| `U+1F97A` |  | 5 |
| `U+002C` | , | 1 |
| `U+2764`, `U+FE0F` | ❤ | 0 |

| Unicode escape(s) | Character | Purpose |
| --- | --- | --- |
| `U+1F449`, `U+1F448` |  | Byte separator |

## Notes on encoding

* The output stream will be a sequence of groups of value characters (see table above) with each group separated by the byte separator character, i.e.
```
✨✨✨,,,,✨✨✨✨,,✨,✨,,,

```
* The total numerical value of each group must equal the decimal value of the corresponding input byte.
    + For example, the numerical value of `,,,,`, as according to the character table above, is `50 + 50 + 1 + 1 + 1 + 1`, or 104. This sequence would thus represent `U+0068` or `h`, which has a decimal value of `104`.
    + Note the ordering of characters within groups. Groups of value characters **must** be in descending order. While character order (within groups) technically does not affect the output in any way, arbitrary ordering can encroach significantly on decoding speed and is considered both illegal and bad form.
* Byte separators that do not follow a group of value characters are illegal, i.e `,,,,` or `,,,,`. As such,  alone is illegal.
* Groups of value characters must be followed by a byte separator. `,,,,` alone is illegal, but `,,,,` is valid.
* The null value must not be followed by a byte separator. `,,,,❤,,,,` and `,,,,❤` alone are valid, but `,,,,❤` is illegal.

Some pseudocode to illustrate how each character is converted:

```
for b in input_stream:
    # Get `b`'s UTF-8 value
    let v = b as number
    let o = new string

    if v == 0:
        o.append("❤")
    else:
        while true:
            if v >= 200:
                o.append("")
                v = v - 200
            else if v >= 50:
                o.append("")
                v = v - 50
            else if v >= 10:
                o.append("✨")
                v = v - 10
            else if v >= 5:
                o.append("")
                v = v - 5
            else if v >= 1:
                o.append(",")
                v = v - 1
            else:
                break

        o.append("")

return o

```

# Rules

1. The standard I/O rules apply.
2. The input must be a string, not a list of bytes.
3. An empty string should return an empty string.
4. It should return the same result as bottom-web for any input with no null bytes (UTF-8 validation is not required).

Some test cases:

* `test` -\> `✨,,✨✨,`
* `Hello World!` -\> `✨✨,,,,,,,,,✨,✨✨✨,,✨✨✨,,✨,✨,,,,,,,✨✨✨,,,`
* -\> `✨✨✨✨,,,,✨✨✨✨,`
* (2 spaces) -\> `✨✨✨,,✨✨✨,,`
* -\> `✨✨✨✨✨✨✨✨,,,,✨✨,,,✨✨✨,,,`
* `⍉⃠` -\> `✨✨,✨✨✨✨,✨✨✨,,✨✨,✨✨✨,✨`
* `X⃩` -\> `✨✨✨,,,✨✨,✨✨✨,✨,,,,`
* `❤` -\> `✨✨,,,✨,,,,✨✨✨,,,,✨✨✨,,,,✨✨✨✨,,,`
* `.\0.` (null byte surrounded by full stops) -\> `✨✨✨✨,❤✨✨✨✨,`

---

This is , so fewest bytes win!

# Answer
> 2 votes
# APL(Dyalog Unicode), 133 bytes SBCS

```
{↑,/{⍵=0:'❤'⋄'',⍨⍬{⍵≥200:(⍺,'')∇⍵-200⋄⍵≥50:(⍺,'')∇⍵-50⋄⍵≥10:(⍺,'✨')∇⍵-10⋄⍵≥5:(⍺,'')∇⍵-5⋄⍵≥1:(⍺,',')∇⍵-1⋄⍺}⍵}¨'UTF-8'⎕ucs⍵}

```

Try it on APLgolf!

-5 thanks to ovs.

# Answer
> 2 votes
# Python 3, ~~134~~ 130 bytes

-4 bytes thanks to bb94!

```
for v in open(0,'rb').read():print(v//200*''+v//50%4*''+v//10%5*'✨'+v//5%2*''+v%5*',',end=0**v*'❤'or'')

```

Try it online! Test case includes a trailing null byte.

`open(0,'rb').read()` is the exact same length as `bytes(input(),'u8')`, but reads the entire input instead of one line.

# Answer
> 2 votes
## JavaScript (newer browsers), ~~166~~ 164 bytes

```
f=
s=>[...new TextEncoder().encode(s)].map(c =>(``[r=`repeat`](c/200)+``[r](c/50%4)+`✨`[r](c/10%5)+``[r](c/5%2)+`,`[r](c%5)||`❤`)+``).join``
```

```
<input oninput=o.textContent=f(this.value)><div id=o>
```

(Only the second line qualifies as the code; the rest is just part of the Stack Snippet.)

Can I Use says that Firefox supported TextEncoder before arrow functions, but I didn't bother to check other browser support.

# Answer
> 2 votes
# 05AB1E, ~~101~~ ~~100~~ ~~90~~ 86 bytes

```
’inÈ¦t("ÿ",î³aries: 1)’.E#εþD_i•yÑáÜ•2äçJë•$Hô}•Ƶ&вvy‰`}1D)•}Ñª—ĆœŒÜ{¹’θǝ₂?••1þÀ•вç×]S

```

Output as a list of characters.

-10 bytes thanks to *@ovs*.

Try it online or verify all test cases.

**Explanation:**

```
’inÈ¦t("ÿ",î³aries: 1)’  # Push dictionary string "inspect("ÿ",binaries: 1)",
                         # where `ÿ` is automatically replaced with the (implicit) input
  .E                     # Execute it as Elixir code
    #                    # Split the result in spaces
     ε                   # Map over each string-part:
      þ                  #  Only leave the digits of the string
       D_i               #  If it's 0 (thus a null-byte):
          •yÑáÜ•         #   Push compressed integer 1008465039
                2ä       #   Split it into 2 parts: [10084,65039]
                  ç      #   Convert each to a character with this codepoint: ["❤",""]
                   J     #   Join the inner pair together: "❤"
         ë               #  Else:
          •$Hô}•         #   Push compressed integer 1626142265
                Ƶ&       #   Push compressed integer 201
                  в      #   Convert 1626142265 to base-201 as list: [200,50,10,5]
                   v     #  Loop over each integer `y`:
                    y‰   #   Take divmod-`y` on the top integer
                         #   (which is the codepoint in the first iteration)
                      `  #   Pop and push the pair separated to the stack: n//y and n%y
                   }1D   #  After the loop: push two 1s
                      )  #  And wrap everything into a list
           •}Ñª—ĆœŒÜ{¹’θǝ₂?•
                         #  Push compressed integer 618452457360154459249099105698966985
             •1þÀ•       #  Push compressed integer 129731
                  в      #  Convert the larger integer to base-129731 as list:
                         #   [129730,128150,10024,129402,44]
                   ç     #  Convert each to a character:
                         #   ["","","✨","",",","",""]
                    ×    #  Repeat each character the divmod-list amount of times
     ]                   # Close the if-else statement and map
      S                  # Convert the list of lists to a flattened list of characters
                         # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to use the dictionary?*; *How to compress large integers?*; and *How to compress integer lists?*) to understand why `’inÈ¦t("ÿ",î³aries: 1)’` is `"inspect("ÿ",binaries: 1)"`; `•yÑáÜ•` is `1008465039`; `•$Hô}•` is `1626142265`; `Ƶ&` is `201`; `•$Hô}•Ƶ&в` is `[200,50,10,5]`; `•}Ñª—ĆœŒÜ{¹’θǝ₂?•` is `618452457360154459249099105698966985`; `•1þÀ•` is `129731`; and `•}Ñª—ĆœŒÜ{¹’θǝ₂?••1þÀ•в` is `[129730,128150,10024,129402,44,128073,128072]`.

# Answer
> 1 votes
# Wolfram Language (Mathematica), 141 bytes

```
Table@@@({Characters@"✨,",#~NumberDecompose~{200,50,10,5,1}})<>If[#>0,"","❤"]&/@Normal@StringToByteArray@#<>""&

```

Try it online!

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

```
s=>[...Buffer(s)].map(n=>n?[200,50,10,5,1].map((v,i)=>[..."✨,"][i].repeat(n/v,n%=v)).join``+"":"❤").join``

```

Try it online!

# Answer
> 0 votes
# Raku, ~~110~~ 112 bytes

```
{[~] map ->\a {[~] "❤✨,".comb Zx(!a,a/200,a/50%4,a/10%5,a/5%2,a%5,?a,?a)},@(.encode)}

```

*+2 bytes to properly implement null byte encoding*

Try it online!

# Answer
> 0 votes
# Lua (LuaJIT), ~~184~~ ~~172~~ 158 bytes

```
r=s.rep;s:gsub('.',function(v)v=v:byte()io.write(r('',v/200),r('',v/50%4),r('✨',v/10%5),r('',v/5%2),r(',',v%5),v~=0 and''or'❤')end)

```

Try it online!

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


# Question
Title: Find the minimum edit distance between two strings
## Explanation

The **edit distance** between two strings is a function of the minimum possible number of insertions, deletions, or substitutions to convert one word into another word.

Insertions and deletions cost 1, and substitutions cost 2.

For example, the distance between `AB` and `A` is 1, because deletions cost 1 and the only edit needed is the deletion of the `B` character.

The distance between `CAR` and `FAR` is 2, because substitutions cost 2. Another way to look at this is one deletion and one insertion.

## Rules

Given two input strings (supplied however is convenient in your language), your program must find the minimum edit distance between the two strings.

You may assume that the strings only contain the characters `A-Z` and have fewer than 100 characters and more than 0 characters.

This is **code golf**, so the shortest solution wins.

## Sample Test Cases

```
ISLANDER, SLANDER
> 1
MART, KARMA
> 5
KITTEN, SITTING
> 5
INTENTION, EXECUTION
> 8

```

# Answer
> 13 votes
## brainfuck, 2680

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

```

Using dynamic programming, of course.

Input strings should be separated by a space, and followed by a new line. For example:

```
INTENTION EXECUTION
008

```

# Answer
> 7 votes
# Brachylog (v2), 14 bytes

```
⟨⊇⊆⟩jg;?clᵐ-ˡṅ

```

Try it online!

This question has a surprising lack of golfing language solutions (there's an APL solution, which is a quasi-golfing language, but it doesn't beat the builtin-based solutions). So here's an attempt to get the ball rolling on that.

I'm not really happy with the golfiness of this; there's a lot of plumbing, as is so often the case when a Brachylog answer takes multiple inputs. In order to comprehensively beat the builtin-based solutions, ideally someone would come up with an answer that's shorter than the word "Levenshtein". Anyone feel like giving that a go?

## Explanation

```
⟨⊇⊆⟩jg;?clᵐ-ˡṅ
⟨  ⟩             Find a value that is related to the first and second inputs:
 ⊇                 {the first input} is a non-continguous superstring of it
  ⊆                it is a non-contiguous substring of {the second input}
    j            Concatenate that value to itself
     g           Form a singleton list containing that value
      ;?c        Append the inputs to that list
         lᵐ      Take the length of each of the three elements
           -ˡ    Left fold by subtraction
             ṅ   Multiply the result by -1

```

The real work is done by the `⟨⊇⊆⟩` at the start, which finds the longest common subsequence of the two inputs (as specified, it just asks for any subsequence, but Brachlog's default tiebreaks will always pick the longest). Let's call the length of this *q*, and the lengths of the inputs *a* and *b*. The edit distance is then equal to *a*-*q*+*b*-*q*; to edit one into the other, we need to delete from one until we reach the common subsequence, then insert until we reach the other (when editing with insertions and deletions, the order doesn't matter).

After our `⟨⊇⊆⟩`, the current implicit variable is a string of length *q*. Doubling this with `j` gives us a string of length 2*q*. After bringing the inputs back into our working value, we have three strings, of lengths \[2*q*, *a*, *b*\], and can replace these with their lengths. Reducing by subtraction then gives 2*q*-*a*-*b* = -(*a*-*q*+*b*-*q*), so we simply need to negate the answer to get the edit distance.

# Answer
> 5 votes
# Python, 138 148 152 characters

Ok, I knew the principle but had never implemented edit distance before, so here goes:

```
x,y=raw_input().split()
d=range(99)
for a in x:
 c=d;d=[d[0]+1]
 for b,p,q in zip(y,c[1:],c):d+=[min(d[-1]+1,p+1,q+2*(a!=b))]
print d[-1]

```

# Answer
> 5 votes
## R 51

This reads in two lines from the user (which are the input) and then just uses the `adist` function to calculate the distance. Since substitutions cost 2 for this problem we need to add a named vector for the costs parameter for adist. Since there is also a counts parameter for adist we can only shorten costs to cos so we still have a unique match for the parameter names.

```
x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))

```

Example use

```
> x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))
MART
KARMA
     [,1]
[1,]    5

```

# Answer
> 4 votes
## PHP, 40

Follows the rules as stated, but not the spirit of the rules:

```
<?=levenshtein($argv[1],$argv[2],1,2,1);

```

Takes it's two parameters as arguments. Example calling: `php edit_dist.php word1 word2`.
Normally `levenshtein()` considers a substitution as one operation, but it has an overloaded form where the insert/sub/delete weights can be specified. In this case, its 1/2/1.

# Answer
> 3 votes
# APL (90 characters)

```
⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞

```

I'm using Dyalog APL as my interpreter, with `⎕IO` set to 1 and `⎕ML` set to 0. The direct function (`{ ... }`) computes, given a row as input, the next row in the distance matrix. (It is started with the initial row: `0,⍳x`.) The power operator () is used to nest the function once for each character in the second string (`⊃⍴b`). After all of that, the final row is reversed (), and its first element is taken ().

Example:

```
      ⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞
LOCKSMITH
BLACKSMITH
3
      ⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞
GATTTGTGACGCACCCTCAGAACTGCAGTAATGGTCCAGCTGCTTCACAGGCAACTGGTAACCACCTCATTTGGGGATGTTTCTGCCTTGCTAGCAGTGCCAGAGAGAACTTCATCATTGTCACCTCATCAAAGACTACTTTTTCAGACATCTCCTGTAG
AAGTACTGAACTCCTAATATCACCAATTCTTCTAAGTTCCTGGACATTGATCCGGAGGAGGATTCGCAGTTCAACATCAAGGTAAGGAAGGATACAGCATTGTTATCGTTGTTGAGATATTAGTAAGAAATACGCCTTTCCCCATGTTGTAAACGGGCTA
118

```

# Answer
> 3 votes
# Husk, ~~10~~ 9 bytes

```
Lṁ-→FnmṖ¹

```

Try it online!

Inspired by ais523's Brachylog solution, finds the longest common (not necessarily contiguous) subsequence and subtracts it from each string.

~~I don't like having to repeat  twice and having to explicitly refer to the two arguments `¹` and `³`, but I couldn't find any shorter alternative.~~ *Now* I'm happy :)

### Explanation

```
Lṁ-→FnmṖ¹     Input: a list containing the two strings
       Ṗ      Get all possible subsequences
      m ¹      for each string
    Fn        Keep only the common ones
   →          Get the last one (which will be the longest)
  -           and subtract it
 ṁ            from each of the inputs, then concatenate the remaining characters
L             Find the length of this

```

Subtracting the longest common substring for each input results in the lists of characters that need to be deleted/inserted. We concatenate these two lists and get the length to calculate the edit distance.

# Answer
> 2 votes
# Jelly, 10 bytes

```
ŒP€f/ṪLạẈS

```

Try it online!

A port to Jelly of my Brachylog answer, saving a few bytes through more convenient plumbing and some convenient builtins (and beating the builtin-based practical language answers by being shorter than the word "Levenshtein"). This is a function submission (although it also works as a full program), taking a list of the two strings.

The algorithm is the same: find the longest common subsequence of the two strings, then add together the differences in lengths between the common subsequence and each of the two original strings.

An odd side effect of this algorithm is that it seems to give an internally consistent definition of the edit difference between three or more strings, as well. I'm not sure if that would be useful for anything, but it's nice to know it exists.

## Explanation

```
ŒP€f/ṪLạẈS
  €          On each of the original strings
ŒP             produce all possible subsequences of the string;
   f         take the list of common elements
    /          between the first and second sets of subsequences;
      L      take the length of
     Ṫ         the last of these common elements;
       ạ     take the absolute differences between that and
        Ẉ      the length of each {of the original strings}
         S   and sum them.

```

Shoutouts to  here for having an implied "each" in it, thus ensuring that Jelly implicitly finds the correct thing to take the length of (if you write `L`, "length", rather than , "length of each", you get the *number* of strings you started with which is not helpful).

Jelly sorts the subsequences in order from shortest to longest, and `f` returns its output in the same order as in its left argument, so the  is guaranteed to find the longest subsequence. We can save any need to subtract from 0 (like the Brachylog submission does), because we have access to an absolute-difference builtin.

# Answer
> 1 votes
# Smalltalk (Smalltalk/X), 34

I am lucky - the standard "String" class already contains levenshtein:

input a, b:

```
a levenshteinTo:b s:2 k:2 c:1 i:1 d:1

```

(the additional parameters allow for different weights on substitution, deletion, etc.)

Test run:

```
#( 'ISLANDER'  'SLANDER'
   'MART'      'KARMA'
   'KITTEN'    'SITTING'
   'INTENTION' 'EXECUTION'
) pairWiseDo:[:a :b|
    a print. ' ' print. b print. ' ' print.
    (a levenshteinTo:b
            s:2 k:2 c:1 i:1 d:1) printCR.
].

```

-\>

```
ISLANDER SLANDER 1
MART KARMA 5
KITTEN SITTING 5
INTENTION EXECUTION 8

```

# Answer
> 1 votes
# Husk, ~~23~~ ~~22~~ 21 bytes

```
`-L+¹³*2▲mλΣz=←¹→)¤*Q

```

Try it online!

```
`-+L¹L³*2▲mλΣz=←¹→)¤*Q
`-                      # reversed minus: a-b
  +L¹L³                 # a = length of arg1 + length of arg2
       *2               # b = 2x
         ▲              # maximum value of
          m             # map function to all elements of list
           λ            # function:
            Σ           # sum of
             z=         # elements that are equal between
               ←¹       # sublist 1 and
                 →)     # sublist 2
                    *   # list: cartesian product of
                   ¤ Q  # all sublists of arg1 and arg2

```

# Answer
> 0 votes
**Ruby 1.9, 124**

```
l=->a,b{a[0]?b[0]?[(a[0]==b[0]?-1:1)+l[a[1..-1],b[1..-1]],l[a[1..-1],b],l[a,b[1..-1]]].min+1: a.size: b.size}
puts l[*ARGV]

```

Golfed version of the slow, recursive Ruby method here, modified to double the weight for substitutions. The fact that it takes 7 characters to remove the first character of a string really hurts, and it'd be cool to replace `(a[0]==b[0]?-1:1)` with something like `-1**a[0]<=>b[0]` but the order of operations is not my friend.

---
Tags: code-golf, string, edit-distance
---


title: Find the nth digit of Euler's number

text:
# Question
Title: Find the nth digit of Euler's number
# Challenge

Given a positive integer `n`, you must calculate the nth digit of \\$e\\$, where \\$e\\$ is Euler's number (2.71828...).

The format of the output can be a number or a string (e.g., `3` or `'3'`)

## Example

```
# e = 2.71828...

nthDigit(3) => 8
nthDigit(1) => 7
nthDigit(4) => 2

```

Shortest code wins.

# Answer
> 9 votes
# 05AB1E, 4 bytes

```
žtsè

```

Pretty convenient builtin ¯\\\_(ツ)\_/¯

Try it online or verify the first ten digits or output the infinite list of digits.

**Explanation:**

```
žt    # Push the infinite list of decimal value of e (including leading 2)
  sè  # And 0-based index the input-integer into it
      # (after which the result is output implicitly)

```

# Answer
> 9 votes
# Python 2, ~~34~~ 32 bytes

*Solution provided by @l4m2*
*-2 bytes thanks to @xnor*

```
lambda n:`(100**n+1)**100**n`[n]

```

Try it online!

Very, very slow.

Verification up to \\$166\\$ digits. The idea for this verification comes from @l4m2: calculates \\$x^{100^n}\\$ by calculating `x=x**10` repeatedly (\\$2n\\$ times), each time truncating \\$x\\$ to a few left most digits (the TIO link uses \\$500\\$ digits). By changing the truncation to round down or up, we obtain the lower and upper bound for the result. If the lower and upper bound agree to \\$n\\$ leftmost digits, we know that the exact calculation will also result in those \\$n\\$ digits.

I have verified that this solution works up to \\$n = 333\\$, using `MAX_DIGITS = 1000`.

**How**

This solution uses the following well known approximation of \\$e\\$: $$ e = \lim\_{x \to \infty} \left(1 + \frac{1}{x} \right)^{x}$$ Substituting \\$x = 100^n\\$, we have: $$ e = \lim\_{n \to \infty} \left(1 + \frac{1}{100^n} \right)^{100^n} = \lim\_{n \to \infty} \frac{\left(100^n + 1 \right)^{100^n}}{\left(100^n\right)^{100^n}}$$ Since the denominator is a power of \\$10\\$, we can ignore it entirely.

According to this analysis on Math SE, the worst case error of this approximation is: $$ \Delta \< \frac{3}{x} = \frac{3}{100^n}$$ which means roughly that every time \\$n\\$ increases by \\$1\\$, we gains 2 digits of precision.

# Answer
> 4 votes
# dc, 66 bytes

```
I?dF+k^1sF2sE2sN[q]sR[1lNlF*dsF/d0=RlE+sElN1+sNlLx]dsLx+lE*0k1/I%p

```

Try it online!

Or print more than 800 digits before TIO times out after a minute.

I've verified these 800 digits against the published value at a NASA web page with 2 million digits of e.

(It may be possible to shorten the code a bit by keeping some of the variables on the stack and accessing them via stack manipulation instead of using dc's registers.)

**Explanation**

```
I     # 10.
?     # Input value.
d     # Push on stack for later.
F+k   # Add 15 and make that the number of decimal places to calculate.
^     # 10 ^ input value, saved on stack for use at end.
1sF   # 1!, stored in F.
2sE   # 2 is starting value for e.
2sN   # for (N=2; ... )
[q]sR # Macro R will be used to end loop.
[     # Start loop L.
  1         # Push 1 for later.
  lNlF*dsF  # F = N! and push on stack.
  /d        # 1 / N!, duplicate on stack
  0=R       # If 1/N! == 0 (to the number of decimal places being computed), end loop.
  lE+sE     # Otherwise e += 1/N!
  lN1+sN    # N++
  lLx       # Go back to start of loop L
]dsLx  # End macro, save it in L, and execute it.
+      # Get rid of extra 0 on stack.
lE     # e, computed with sufficient accuracy
*      # Multiply by 10^input value, which was saved on the stack early on.
0k1/   # Truncate to integer.
I%    # Mod by 10 to get desired digit.
p     # Print digit.

```

# Answer
> 4 votes
# Python 3, ~~146~~ 105 bytes

```
n=int(input())
N=n+3
q=2
e=[1]*N
exec('q=i=0;exec("q,e[i]=divmod(10*e[i]+q,N-i+1);i+=1;"*N);'*n)
print(q)

```

Try it online! (thanks to @SurculoseSputum)

This only uses small integers to calculate digits of \\$e\\$. With a modification to use a lazy upper bound for `N`, it uses the algorithm described in

> A. H. J. Sale. "The calculation of \\$e\\$ to many significant digits." The Computer Journal, Volume 11, Issue 2, August 1968, Pages 229–230, https://doi.org/10.1093/comjnl/11.2.229

Essentially, the idea is that \\$e\\$ can be written in "base-factorial" as \\$1.11111\dots\\$, where digit \\$n\\$ has place value \\$1/n!\\$. The algorithm repeatedly multiplies this number by 10 to extract digits one at a time. In fact, if one were to record each value of `q` in the outer `for` loop, the result would be the first `n` digits of \\$e\\$.

One complexity is that we need to know how many digits in base-factorial to calculate. In this version, \\$n+3\\$ is (more than) sufficient. A previous version of this answer used an estimate from Taylor's theorem, and it looked for a value of `N` such that \\$N!\geq 10^{n}\\$, doing so by calculating all factorials until it exceeds this power of ten.

# Answer
> 2 votes
# 05AB1E, 8 bytes

```
°D>smI<è

```

Try it online!

Very, very slow.

# Answer
> 2 votes
# SageMath, <sup>~~35~~</sup> 33 bytes

```
lambda n:str(N(e,digits=n+9))[-9]

```

Try it online!

Very, very *fast!*

# Answer
> 2 votes
# Python 2, ~~98~~ ~~100~~ ~~72~~, 71 bytes

```
f=lambda n,p=1,q=1,k=1:k<n+9and f(n,p*k+1,q*k,k+1)or str(p*100**n/q)[n]

```

Try it online!

-1 byte, remove unneccesary whitespace.

### older answer

```
f=lambda n,p=1,q=1,k=1:k<n+9and f(n,p*k+1,q*k,k+1) or str(p*100**n/q)[n]

```

Try it online!

-28 bytes simpler formula

Simpler algorithm based on more usual formula:

$$e = 1 + \frac 1 {1!} + \frac 1 {2!} + \frac 1 {3!} + \frac 1 {4!} + \cdots$$

But re-expressed as sequence of approximations:

$$1, 1+1, \frac{(2(1+1)+1)}2, \frac{(3(2(1+1)+1)+1)}{(3\cdot2)}, \frac{(4(3(2(1+1)+1)+1)+1)}{(4\cdot(3\cdot2))},...$$

These can be expressed as ratio of recurrence relations $\frac {p\_k}, where

$$p\_0 = q\_0 = 1 \\ p\_{k+1} = kp\_k + 1, q\_{k+1} = kq\_k, \\: \forall k \ge 1$$

### old answer

```
f=lambda n,p=3,q=1,r=19,s=7,b=10,x=1,y=0:x-y and f(n,r,s,r*b+p,s*b+q,b+4,p*100**n//q,x) or str(x)[n]

```

+2 bytes because I mistakenly omitted `f=`

Try it online!

This approach is based on continued fractions. Not happy with it yet, but it seems good for a few hundred digits.

Based on the continued fraction:

$$e = 3 - \cfrac 2 {7 + \cfrac 1 {10 + \cfrac 1 {14 + \cfrac 1 {18 + \cfrac 1 {22 + \ddots}}}}}$$

Computed by the recurrence relation:

$$\frac {p\_0} {q\_0} = \frac 3 1 , \\: \frac {p\_1} {q\_1} = \frac {19} 7 \\ \frac {p\_{k+1}} {q\_{k+1}} = \frac {p\_k (4k+2) + p\_{k-1}} {q\_k (4k+2) + q\_{k-1}}, \\: \forall k \ge 1$$

which was arrived at after a first reading of An Essay on Continued Fractions by Leonard Euler.

# Answer
> 1 votes
# Jelly, 14 bytes

```
⁵*³
¢‘µ*¢ŒṘḣ³Ṫ

```

Try it online!

A monadic link taking a single integer, plus a niladic helper link.

## Explained

```
⁵*³
¢‘µ*¢ŒṘḣ³Ṫ

Link f:
    *(10, input) # 10 * input

Main Link:
    tail(head(str(*(Increment(f()), f())), input)) # str((f() + 1) * (f()))[:input][-1]

```

# Answer
> 1 votes
# Charcoal, ~~30~~ 12 bytes

```
Ｐ←×ψ⁺²Ｎ¤≕EＴ¹

```

Try it online! Link is to verbose version of code. Inspired by @ASCII-only's comment and his answer to Bake a slice of Pi (compare my answer to Music with pi and e). Explanation:

```
Ｐ←×ψ⁺²Ｎ

```

Input `n` and print `n+2` nulls to the left without moving the cursor, so it remains on the last null.

```
¤≕E

```

Fill the nulls with the expansion of Euler's number.

```
Ｔ¹

```

Trim away everything except the current character.

Previous 30-byte answer calculated the Maclaurin expansion of `100ⁿe` to `n+10` terms:

```
Ｎθ≔Ｘχ⊗θη≔⁰ζＦ⁺χθ«≧⁺ηζ≧÷⊕ιη»§Ｉζθ

```

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

```
Ｎθ

```

Input `n`.

```
≔Ｘχ⊗θη

```

Start with a term of `100ⁿ`.

```
≔⁰ζ

```

Initialise the total to `0`.

```
Ｆ⁺χθ«

```

Repeat `n+10` times.

```
≧⁺ηζ

```

Add the current term to the total.

```
≧÷⊕ιη

```

Divide the term by the number of loop iterations.

```
»§Ｉζθ

```

Print the `n`th digit of the total.

# Answer
> 1 votes
# Wolfram Language (Mathematica), 21 bytes

```
Floor[E 10^#]~Mod~10&

```

Try it online!

# Answer
> 1 votes
# Whispers v3, 52 bytes

```
> Input
> eᵢ
>> ≻1
>> 2ᶠ3
>> 4ⁿ1
>> Output 5

```

Try it on repl.it!

Run with `python3 whispers\ v3.py euler.wisp < input.txt 2> /dev/null`

Input is the first line in input.txt.

Euler digits builtin ftw!

# Answer
> 0 votes
# bc -l, 37 bytes

```
scale=s=read();(e(1)*A^s+scale=0)%A/1

```

Try test cases online!

Input on stdin, output on stdout.

---
Tags: code-golf, math
---


title: Unicode T-square

text:
# Question
Title: Unicode T-square
# Challenge

Create a function or program that, when given an integer `size`, behaves the following way:

If `size` is equal to 1, output

```
┌┐
└┘

```

If `size` is greater than 1, apply the following substitutions :

| Source | Target |
| --- | --- |
|  | `┌┐`
`└┌` |
|  | `┌┐`
`┐┘` |
|  | `┌└`
`└┘` |
|  | `┘┐`
`└┘` |

**Note:** this is basically a Unicode box-drawing version of the T-Square fractal.

If it makes things easier for you, you may make the base case correspond to `0`, as long as you specify in your answer.

The program should output anything that is isomorphic to a grid, so a multiline string, an array of strings, an array of arrays of chars, whichever is more comfortable. You may use a different set of characters than `┌┐└┘` (such as 1234, ABCD, etc.) if you want.

Leading and trailing spaces are allowed if you choose to work with strings.

Please specify what output format your code is returning.

# Test Cases

`1`

```
┌┐
└┘

```

`2`

```
┌┐┌┐
└┌┐┘
┌└┘┐
└┘└┘

```

`3`

```
┌┐┌┐┌┐┌┐
└┌┐┘└┌┐┘
┌└┌┐┌┐┘┐
└┘└┌┐┘└┘
┌┐┌└┘┐┌┐
└┌└┘└┘┐┘
┌└┘┐┌└┘┐
└┘└┘└┘└┘

```

This is , so the lowest byte count for each language wins!

# Answer
> 7 votes
# JavaScript (ES6), 108 bytes

Returns an array of strings, with `0123` instead of `┌┐└┘`.

```
f=(n,a=[w="01","23"])=>n?f(n-1,[...a,...a].map((s,i)=>i<w|i/w/3?s+s:s.slice(0,w)+a[i-w]+s.slice(-w)),w*=2):a

```

Try it online!

### How?

This is a rather straightforward recursive construction of the pattern and is probably not the shortest method.

Below is an example for the 2nd iteration, with **w = 2**.

```
   0123  0123 4567  0123 4567
0  ABCD  ABCD|ABCD  ABCD|ABCD  \__ i < w -> s + s
1  EFGH  EFGH|EFGH  EFGH|EFGH  /
2  IJKL  IJ..|..KL  IJ**A****B**|**C****D**KL  \
3  MNOP  MN..|..OP  MN**E****F**|**G****H**OP   \
         ----+----  ----+----    }-- s.slice(0, w) + a[i - w] + s.slice(-w)
4        AB..|..CD  AB**I****J**|**K****L**CD   /
5        EF..|..GH  EF**M****N**|**O****P**GH  /
6        IJKL|IJKL  IJKL|IJKL  \__ i ≥ 3w -> s + s
7        MNOP|MNOP  MNOP|MNOP  /
```

### Commented

```
f = (                     // f is a recursive function taking:
  n,                      //   n = number of iterations
  a = [                   //   a[] = output array initialized to:
    w = "01",             //     the pattern "01" (we also initialize w to "01")
    "23"                  //     the pattern "23"
  ]                       //
) =>                      //
  n ?                     // if n is not equal to 0:
    f(                    //   do a recursive call:
      n - 1,              //     decrement n
      [...a, ...a]        //     repeat a[] twice
      .map((s, i) =>      //     for each string s at index i in this array:
        i < w |           //       if i is less than w
        i / w / 3 ?       //       or i is greater than or equal to w * 3:
          s + s           //         just double the previous row
        :                 //       else:
          s.slice(0, w) + //         take the first half of s
          a[i - w] +      //         append the row i - w of the previous pattern
          s.slice(-w)     //         append the 2nd half of s
      ),                  //     end of map()
      w *= 2              //     double w
    )                     //   end of recursive call
  :                       // else:
    a                     //   return a[]

```

# Answer
> 6 votes
# Charcoal, ~~29~~ 21 bytes

```
┌Ｆ÷Ｘ²…⁰Ｎ²«Ｃιι‖ＢＯ⌈⊗ι

```

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

Print a quarter of the initial box. This gets fixed up on the first loop iteration. Note that while this character is not in Charcoal's code page, Charcoal has an escape sequence that encodes this character using three bytes; this sequence is not shown although the deverbosifier does account for it correctly.

```
Ｆ÷Ｘ²…⁰Ｎ²«

```

Take the powers of two from `1` up to (but not including) `2ⁿ`, but then integer divide them by 2.

```
Ｃιι

```

Make a copy of the current figure, overwriting the bottom right quarter of the figure. (Except that `i` is zero on the first loop, so nothing happens.)

```
‖ＢＯ⌈⊗ι

```

Reflect the (original three quarters of) the figure to complete the new iteration.

# Answer
> 6 votes
# Ruby, ~~103~~ 101 bytes (UTF 8) or ~~95~~ 93 bytes (ASCII)

```
->n{n<1?%w{┌┐ └┘}:(q=f[n-1];(-k=1<<n)...k).map{|i|s=q[i]*2;(t=i+j=k/2)/2%k<j&&s[j,k]=q[t];s}}

```

A function which returns an array of strings.

For `n=0` the output is as follows:

```
UTF 8 ┌┐      Or   ASCII (my preferred   pq
      └┘            character choice)    bd

```

For higher values of `n` the function is called recursively to build up a square of double the proportions of the previous iteration (total 4 copies) line by line. For the middle rows, the lines are modified as necessary to overwrite a fifth copy of the previous iteration onto the centre of the pattern.

Try it online!

TIO link shows the UTF 8 version for easy verification. substituting the box characters with `pq bd` (or other ASCII characters) reduces the code to 93 bytes.

# Answer
> 3 votes
# , ~~46~~ 42 bytes

```
([`(<@;~@(-:+i.)@#@[)`]},~@,.~)@[&0 i.@2 2

```

Try it online!

* `i.@2 2` returns:

```
 0 1
 2 3

```
* `(...)@[&0` Apply the verb (...) iteratively "input" number of times.
* `(<replace logic> ,~@,.~)` \- `,~@,.~` first zips the current input with itself `,.~`, so with the starting input that becomes:

```
 0 1 0 1
 2 3 2 3

```

and then appends that to itself `,~@`:

```
 0 1 0 1
 2 3 2 3
 0 1 0 1
 2 3 2 3

```

giving us the original input repeated 4 times in a square.
* Next we replace the "center" with the original input. Imagine filling in a hole like so:

```
  0 1 0 1                0 1 0 1
  2     3   +  0 1  =    2 0 1 3
  0     1      2 3       0 2 3 1
  2 3 2 3                2 3 2 3

```
* Here we're using the gerund form of Amend `}`, and all the rest is mechanics to specify which coordinates we replace:
* `(<@;~@(-:+i.)@#@[)` That entire phrase, verbosely, converts (in our example) the 2x2 original input matrix into the J double boxed:

```
 ┌─────────┐
 │┌───┬───┐│
 ││1 2│1 2││
 │└───┴───┘│
 └─────────┘

```

which is how we tell Amend: "Replace the intersection of rows 1 and 2, and columns 1 and 2 with..."

# Answer
> 3 votes
# Wolfram Language (Mathematica), ~~60~~ 55 bytes

```
Nest[Flatten[q/. 5-#->#&/@#&/@#,q]&,q={{1,3},{2,4}},#]&

```

Try it online!

Returns a matrix of integers - uses `1234` for `┌└┐┘`.

# Answer
> 3 votes
# APL(Dyalog Unicode), ~~36~~ 31 bytes SBCS

```
{⊃⍪/,/{⍵@(⌽⍵=⊖)x}¨⍵}⍣⎕⊢x←2 2⍴⍳4

```

Try it online!

A dfn submission which takes the number as left argument.

Uses `⎕IO←0` (0-indexing).

The box is represented as

```
01
23

```

which is then substituted exactly according to the question spec.

-5 bytes from Adám.

## Explanation

```
{⊃⍪/,/{⍵@(⌽⍵=⊖)x}¨⍵}⍣⎕⊢x←2 2⍴⍳4
                       x←2 2⍴⍳4  store 0 1 in x
                                       2 3
                    ⍣⎕⊢          apply the following n times to the value of x:
{                ¨⍵}             substitute each number ⍵ with:
      {⍵@      x}                replace the following with ⍵ in the value of x:
         (⌽⍵=⊖)                  position of ⍵, flipped diagonally
  ⍪/,/                           join all the submatrices together
 ⊃                               and remove boxing.

```

# Answer
> 3 votes
# Python 3, ~~217~~ \\$\cdots\\$ ~~119~~ 102 bytes

Saved ~~9~~ a whopping 35 bytes thanks to Danis!!!
Saved ~~2~~ 5 bytes thanks to att!!!

```
f=lambda n:n and[[(j,c)[j+c==3]for c in r for j in(i,i+1)]for r in f(n-1)for i in(0,2)]or[[0,1],[2,3]]

```

Try it online!

Uses integers \\$0,1,2,3\\$ instead of chars ,,,.
Inputs a zero-base integer \\$n\\$ and returns the \\$2^{n+1}\times 2^{n+1}\\$ T-Square fractal as a list of strings.

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

```
{⍵≡0:2 2⍴⍳4⋄m⊣@((2*⍵-1)+⍳,⍨2*⍵)⍪⍨,⍨m←∇⍵-1}

```

```
{⍵≡0:2 2⍴⍳4⋄m⊣@((2*⍵-1)+⍳,⍨2*⍵)⍪⍨,⍨m←∇⍵-1}
 ⍵≡0:2 2⍴⍳4                                 ⍝ if ⍵ is 0 return the first result
           ⋄                                ⍝ otherwise
                                   m←∇⍵-1   ⍝ assign the last result to m
                               ⍪⍨,⍨         ⍝ duplicate in both directions
               ((2*⍵-1)+⍳,⍨2*⍵)             ⍝ indices corresponding to the middle section
            m⊣@                             ⍝ replace with m

```

Produces the fractal recursively using a pattern I spotted where you make 4 copies of the previous one and replace the middle. (I'm not sure if this works in general though, so if you have outputs for 4+ that would be great)

Try it online!

# Answer
> 1 votes
# 05AB1E, 30 bytes

```
3Ý2ô©IGNoTS-U2δиD«DÅsε®NèXǝ}Xǝ

```

Port of *@Jonah*'s J answer, so make sure to upvote him as well!

Outputs as a matrix, with `0123` for `┌┐└┘` respectively.

Try it online or verify the first input amount of test cases (the footers transliterate it to the unicode boxes to pretty-print).

**Explanation:**

```
3Ý                # Push list [0,1,2,3]
  2ô              # Split it into parts of size 2: [[0,1],[2,3]]
    ©             # Store this 2x2 matrix in variable `®` (without popping)
     IG           # Loop `N` in the range [1,input):
       No         #  Push 2 to the power `N`
         TS-      #  Subtract [1,0] to create a pair: [2^N-1,2^N]
            U     #  Pop and store this pair in variable `X`
        δ         #  Map over each row of the matrix:
       2 и        #   And repeat it
                  #  (i.e. [[0,1],[2,3]] becomes [[0,1,0,1],[2,3,2,3]])
          D«      #  Merge a copy of itself:
                  #   [[0,1,0,1],[2,3,2,3],[0,1,0,1],[2,3,2,3]]
       D          #  Create a copy of the matrix
        Ås        #  Pop and push its middle two rows
          ε       #  Map over those two rows:
           ®      #   Push matrix [[0,1],[2,3]] from variable `®`
            Nè    #   Get the M'th row of this matrix based on the 0-based map-index `M`
              Xǝ  #   Insert those two values at indices `X` into the current row
          }Xǝ     #  After the map: insert the modified middle rows at indices `X` into
                  #  the matrix
                  # (after the loop, the resulting matrix is output implicitly)

```

---
Tags: code-golf, unicode, fractal, recursion
---


title: Next to the middle

text:
# Question
Title: Next to the middle
Given an array of integers, find *"the next to the middle"*.

> The next to the middle is the smallest integer greater than the smallest among mean, median and mode of the given numbers, that is neither the mean, median or mode and is also contained in the array.

For example, in the following array

```
[ 7, 5, 2, 8, 0, 2, 9, 3, 5, 1, 2 ]

Mean: 4
Median: 3
Mode: 2

```

The next to the middle is `5`, because:

* It's greater than 2 (the smallest of the three)
* It is not any of the mean, median, mode
* It's present in the input array
* It's the smallest number matching the above requirements

Another example, given this array

```
[ 2, 5, 1, 11, -1, 2, 13, 5, 1, 0, 5 ]

Mean: 4
Median: 2
Mode: 5

```

The next to the middle is `11`.

## Input

An array containing a sequence of integers.

* You don't need to handle integers larger than those that your language's data type can handle
* The mean could be a floating point number and that's just fine.
* **If the number of elements in the input array is even, you need to handle 2 medians, rather than doing the average of the two values.**
* If more than one integer occurs with the highest frequency, you need to handle multiple values for the mode.

## Output

The *next to the middle*.

If such number doesn't exist you can output either `3.14`, an empty string or any other value that cannot be mistaken for an element of the array (be consistent with that value throughout your program).

Standard rules apply for your answer, with standard I/O conventions, while default Loopholes are forbidden.

It would be nice if you could provide an easy way to try your program and possibly an explanation of how it works.

This is , the shortest wins.

## Test cases

```
[ 7, 5, 2, 8, 0, 2, 9, 3, 5, 1, 2 ]
5

[ 2, 5, 1, 11, -1, 2, 13, 5, 1, 0, 5 ]
11

[ 528, -314, 2, 999, -666, 0, 0, 78 ]
78

[ 528, -314, 2, 999, -666, 0, 0, 79 ]
79

[ 528, -314, 2, 999, -666, 5, -5, 42 ]
NaN

[ -845, 2021, 269, 5, -1707, 269, 22 ]
5

[ -843, 2021, 269, 5, -1707, 269, 22 ]
2021

[-54,-22,-933,544,813,4135,54,-194,544,-554,333,566,566,-522,-45,-45]
333

[95444,-22668,834967,51713,321564,-8365542,-962485,-253387,-761794,-3141592,-788112,533214,51713,885244,522814,-41158,-88659176,654211,74155,-8552445,-22222]
-3141592

[ 1, 2, 3, 9, 8, 7, 9, 8, 5, 4, 6, 0, 6, 7 ]
NaN

```

~~\[ \] // empty array~~
~~NaN~~
You don't need to handle an empty array.

### Answers to comments

* **Is any normal floating point accuracy acceptable?**
Yes. Since you will compare the mean with integers, considering 9,87654321 as mean is the same thing of considering 9.8 as mean.
* **"If such number doesn't exist", can we error?**
Since there's a reusability rule for functions, if you are writing a function, a program needs to be able to call that function multiple times. If you are writing a program, then you can exit on error, but you have to be consistent with this output: you have to exit on error every time that there is no next to the middle.

# Answer
> 4 votes
# Jelly, 20 bytes

```
L‘HịṢ;Æm;ÆṃµṂ³>Ƈḟȯ.Ṃ

```

A full program accepting a list of numbers which prints the *next to the middle* or `0.5` if there is none.

**Try it online!**

Or see the test-suite (uses a functional form which uses the register atoms, `©` and `®`, to replace the use of the program argument atom, `³`).

### How?

```
L‘HịṢ;Æm;ÆṃµṂ³>Ƈḟȯ.Ṃ - Main Link: list, A
L                    - length (A)
 ‘                   - increment
  H                  - halve
    Ṣ                - sort (A)
   ị                 - index into (if A has an even number of elements we get the two in
                                   the middle, due to Jelly's fractional indexing magic)
      Æm             - mean (A)
     ;               - concatenate
         Æṃ          - mode (A)
        ;            - concatenate
           µ         - start a new monadic chain, f(X=medians+[mean,mode])
             ³       - programs argument, A
            Ṃ        - minimum (X)
               Ƈ     - filter (A) keeping if:
              >      -   greater than (minimum (X))
                ḟ    - filter - discard those which are in (X)
                  .  - a half
                 ȯ   - logical OR (replace an empty list with 0.5)
                   Ṃ - minimum

```

# Answer
> 3 votes
# , 76 bytes

Returns an empty list `''` if there is no element.

```
(0{ ::''-./:~@#~-.><./@])({./.~#~[:(=>./)#/.~),(>.@<:@-:@#(-@[}.}.)/:~),+/%#

```

Try it online!

* `+/%#` mean: sum divided by length
* `>.@<:@-:@#(-@[}.}.)/:~` median(s): sort, drop first and last `floor(length % 2 - 1)` elements (can this be shorter?)
* `#/.~` mode(s): group the list by itself, get the length of each group
* `[:(=>./)` the maximum length
* `{./.~#~` take the groups' first element that have the maximum length
* `<./@]` minimum of mean, medians and modes
* `-. #~-.>` get every element that is not in (mean, medians, modes), but also larger,
* `/:~@` sort them and
* `0{ ::''` get the first element – if there is none and an error would occur, return `''` instead

# Answer
> 3 votes
# Jelly, 22 bytes

```
L‘HịṢ;Æm;Æṃ
ḟÇ>ƇÇṂ$ȯ.Ṃ

```

Try it online!

Returns `0.5` for an invalid input.

## Explanation

```
L‘HịṢ;Æm;Æṃ   Auxiliary monadic link
L             Length
 ‘            Increment
  H           Half
   ị          Index into
    Ṣ           the sorted array
     ;        Join with
      Æm        the mean
        ;     Join with
         Æṃ     the mode(s)

ḟÇ>ƇÇṂ$ȯ.Ṃ   Main monadic link
ḟ            Filter out
 Ç             the results of the previous link
   Ƈ         Filter
  >            greater than
      $        (
    Ç            The results of the previous link
     Ṃ           Maximum
      $        )
       ȯ     Logical OR (non-vectorizing) with
        .    0.5
         Ṃ   Minimum

```

# Answer
> 3 votes
# 05AB1E, 21 bytes

```
¢ZQÏIÅAI{Ås)˜WUKʒX›}ß

```

Try it online or verify all test cases.

**Explanation:**

```
        #Mode:
¢       # Count how many times each value occurs in the (implicit) input-list
 Z      # Get the maximum of these counts (without popping the list)
  Q     # Check for each if it's equal to this maximum count
   Ï    # Only leave the values in the (implicit) input-list at the truthy indices
        #Mean:
IÅA     # Push the input; pop and push its mean
        #Median:
I{      # Push the input; sort it
  Ås    # Pop and push the middle (one or two) values
)       # Wrap all three into a list
 ˜      # And flatten it
W       # Push the minimum of this list
 U      # Pop and store it in variable `X`
  K     # Remove all medium, mean, and mode values from the (implicit) input-list
   ʒ    # Filter the remaining values by:
    X›  #  Check if it's larger than `X`
   }ß   # After the filter: pop and push the minimum
        # (after which it is output implicitly)

```

Although 05AB1E does have builtins for all three: mean (`ÅA`); median (`Åm`); and mode (`.M`), the median takes the average of the two values for even-length lists, and the mode only results in a single most frequent value instead of all, which is why we'll do those manually. In the legacy 05AB1E version the `.M` mode builtin did result in all most frequent values instead of just one, but unfortunately the legacy version doesn't have a median nor middle builtin, and doing that manually would be even longer.

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

Returns `undefined` if no valid answer is found.

```
a=>a.sort((a,b)=>a-b).map(c=v=>(n++,t+=v,i=c[v]=-~c[v],i<m?0:m=i,v),m=t=n=0).find(v=>v>Math.min(...A=[t/n,a[n>>1],a[n-1>>1],...a.filter(v=>c[v]==m)])&!A.includes(v))

```

Try it online!

### Commented

```
a =>                     // a[] = input array
  a.sort((a, b) =>       // sort a[] from lowest to highest
    a - b                // so that we can compute the median value(s)
  )                      //
  .map(c = v =>          // for each value v in a[]:
    ( n++,               //   increment the total number of values n
      t += v,            //   add v to the sum t of all values
      i = c[v] = -~c[v], //   update the number i of occurrences of v
      i < m ? 0 : m = i, //   update m to max(m, i)
      v                  //   yield v so that the array is unchanged
    ),                   //   and we can chain with .find()
    m = t = n = 0        //   start with m = t = n = 0
  )                      // end of map()
  .find(v =>             // find the first value v that satisfies:
    v > Math.min(        //   1) it's greater than the minimum of ...
      ...A = [           //        the values stored in A[], which are:
        t / n,           //          - the mean
        a[n >> 1],       //          - the 1st median value
        a[n - 1 >> 1],   //          - the 2nd median value (if any)
        ...a.filter(v => //          - all mode values
          c[v] == m      //            i.e. values that appear m times
        )                //
      ]                  //        end of array
    ) &                  //      end of Math.min()
    !A.includes(v)       //   2) it's not one of the values defined above
  )                      // end of find()

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 81 bytes

```
Min@Cases[#,a_/;a>Min@#&&#~FreeQ~a&@{Mean@#,Sort@#//._[_,a__,_]:>a,Commonest@#}]&

```

Try it online!

Returns `Infinity` if such a number does not exist.

# Answer
> 1 votes
# Charcoal, 61 bytes

```
Ｗ⁻θυＦ№ι⌊ι⊞υ⌊ι≔✂υ⊘⊖Ｌθ⊕⊘Ｌθ¹υ≔Ｅθ№θιηＦ⌕Ａη⌈η⊞υ§θι⊞υ∕ΣθＬθＩ⌊Φ⁻θυ›ι⌊υ

```

Try it online! Link is to verbose version of code. Outputs `None` if no suitable value exists. Explanation: Not an ideal challenge for Charcoal.

```
Ｗ⁻θυ

```

While the sorted list does not contain all of the input values...

```
Ｆ№ι⌊ι⊞υ⌊ι

```

... push the next value to the sorted list according to the number of times it appears.

```
≔✂υ⊘⊖Ｌθ⊕⊘Ｌθ¹υ

```

Slice the middle element(s) from the sorted list.

```
≔Ｅθ№θιη

```

Tabulate how many times each element appears in the list.

```
Ｆ⌕Ａη⌈η

```

Loop over the indices of maximum counts, ...

```
⊞υ§θι

```

... pushing the original value to the list of averages.

```
⊞υ∕ΣθＬθ

```

Finally, push the mean to the list of averages.

```
Ｉ⌊Φ⁻θυ›ι⌊υ

```

Remove all of the averages from the input, then also filter out values lower than all of the averages, and print the minimum of the remainder (if any).

# Answer
> 1 votes
# Stax, 33 bytes

```
Ç∞♫ÑÄ‼ú╘màk■g5øg◘U½¢┴Åû)*ç╨£╨├╡óà

```

Run and debug it

Getting the middle two elements takes most of the space here. Reducing that would significantly improve the score.

---
Tags: code-golf, arithmetic
---


title: Colorize a diff in unified format

text:
# Question
Title: Colorize a diff in unified format
# Introduction

`git diff` is a great way to export patches of the source code, and its outputs are colorized if you don't pass extra arguments to it.

However, when you want to review the exported file with colored output, it would be pretty hard. colordiff is an option, but it acts like the `diff` program itself, also, it is not "multiplatform" considering how many languages this community can code in.

# Challenge

Write a program that takes a diff text input from the user and colorize it. On \*nix, it might mean printing to standard output with ANSI escape sequences. The colored output must be clearly visible to users.

## Details

* Only valid diff texts will be passed. You can make it so other cases are UB.
* The original file line starting with `---` (e.g. `---path/to/example`) should be colored **red and bolded**.
* The new file line starting with `+++` (e.g. `+++path/to/example`) should be colored **green and bolded**.
* The modification lines starting with `+` or `-` (e.g. `+correct` and `-wrong`) should be colored green and red respectively, but not bolded.
* You can color the hunk range information indicated by two `@@`s at the start of a line (e.g. `@@ -22,3 +23,7 @@`) however you like, but it should not be the default color, and it must be consistent throughout the program. The hunk range indicators can be bolded.
* The optional section heading after the hunk range information which is after the second `@@` (e.g. "This is an optional heading" in `@@ -22,3 +23,7 @@ This is an optional heading`) should **NOT** be colored.
* All other lines should **NOT** be colored.
* The program must output the exact text from the input. The only difference is the color.
* You may assume that only new file lines start with `+++`, only original file lines start with `---`, only modification lines start with `+` or `-` (but not `---` or `+++`), and that all lines starting with `@@` denote a hunk information.

## Restriction

Usage of diffutils, patchutils, git tools, or any other external programs are not allowed.

## Test Cases

```
+++ Green and Bolded
++ Green, not Bolded
+ Green
- Red
-- Red, not Bolded
--- Red and Bolded
@@ -123,1 +123,1 @@ <- that was a color different to this color
This should be a sentence that has the same color as the line above and after the second @@
This is not colored: @@ test ---+++ @@ because it doesn't start at the beginning of a line

@@ -12,3 +12,3 @@ <- that should have the same color as the last hunk

```

# Winning Criterion

This is , so the shortest wins!

# Answer
# Perl 5 (`-p`), ~~70~~, 69 bytes

-1 byte dropping 0, as suggested by Dom Hastings

```
s/^([-+@])(\1\1)?(.*?@@|.*)/"[".($2&&"1;").((4*ord)%9+31)."m$&"/e

```

Try it online!
> 9 votes

---
Tags: code-golf, color
---


title: Split Mark's marks

text:
# Question
Title: Split Mark's marks
## Challenge

Mark is a student who receives his `N` marks in a concatenated way in a one single line.

The challenge is to separate his marks, knowing that each mark can only be `0` or `1` or `2` or `3` or `4` or `5` or `6` or `7` or `8` or `9` or `10`.

## Input

`N` natural number and one line.

## Output

A set of natural numbers.

## Example

```
N, One line------------------> Set of marks
3, '843'---------------------> [8, 4, 3]
1, '0'-----------------------> [0]
2, '1010'--------------------> [10,10]
3, '1010'--------------------> [1,0,10] or [10,1,0]
4, '1010'--------------------> [1,0,1,0]
9, '23104441070'-------------> [2, 3, 10, 4, 4, 4, 10, 7, 0]
12,'499102102121103'---------> [4, 9, 9, 10, 2, 10, 2, 1, 2, 1, 10, 3]
5, '71061'-------------------> [7, 1, 0, 6, 1]
11,'476565010684'------------> [4, 7, 6, 5, 6, 5, 0, 10, 6, 8, 4]
4, '1306'--------------------> [1, 3, 0, 6]
9, '51026221084'-------------> [5, 10, 2, 6, 2, 2, 10, 8, 4]
14,'851089085685524'---------> [8, 5, 10, 8, 9, 0, 8, 5, 6, 8, 5, 5, 2, 4]
11,'110840867780'------------> [1, 10, 8, 4, 0, 8, 6, 7, 7, 8, 0]
9, '4359893510'--------------> [4, 3, 5, 9, 8, 9, 3, 5, 10]
7, '99153710'----------------> [9, 9, 1, 5, 3, 7, 10]
14,'886171092313495'---------> [8, 8, 6, 1, 7, 10, 9, 2, 3, 1, 3, 4, 9, 5]
2, '44'----------------------> [4, 4]
4, '9386'--------------------> [9, 3, 8, 6]

```

## Rules

* When several outputs are possible give only one output.
* Only mark of value `10` is on two decimal, others are on one decimal.
* The input and output can be given in any convenient format
* No need to handle invalid input
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an online testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
> 6 votes
# Brachylog, ~~23~~ 21 bytes

*-2 bytes thanks to Fatalize*

```
h~c.{ịℕ≤10&ịṫ?∧}ᵛ&t~l

```

Try it online!

The input is a pair `[Line, N]`.

This is my first Brachylog program, so there is probably a lot room for improvement.

It is very slow when the length of the line \> 7.

Explanation:

```
h~c.{ịℕ≤10&ịṫ?∧}ᵛ&t~l
h                         The first element in the input
 ~c                       is formed by concatenating
   .                      the elements in the output array
   .{         ∧}ᵛ     AND For every element in the output array holds that
     ị                      The element converted to an integer
      ℕ                       is a natural number
       ≤10                    and less than or equal to 10
          &ịṫ?              and it has no leading zeroes (*)
                 &t   AND The second element of the input
                   ~l     is the length of the output

```

(\*) `ịṫ?` checks that there are no leading zeroes. It converts the string to integer and then back to string and compares to the original string.

# Answer
> 5 votes
# , ~~17~~, 12 bytes

```
\ÓòÀGjí1“î…0

```

Try it online!

I was content with 17 bytes, but than 05AB1E came along with 13, and I couldn't let a challenge go unanswered. :D

```
\Ó                      " Put each character on it's own line
  ò                     " Recursively (repeat until an error happens)...
   ÀG                   "   Go to the "n"th line
     j                  "   Move down a line (this will error if there are exactly "n" lines)
      í                 "   Remove...
       1                "     a '1'
        <0x93>          "     START THE MATCH HERE
              î         "     a newline
               <0x85>   "     END THE MATCH HERE
                   0    "     a '0'

```

Hexdump:

```
00000000: 5cd3 f2c0 476a ed31 93ee 8530            \...Gj.1...0

```

Alternate solution:

```
\ÓòÀGjç1î0/J

```

Unfortunately, this replaces `10` with `1 0`

# Answer
> 5 votes
# Perl 6, 25 bytes

```
->\a,\b{b~~/(10|.)**{a}/}

```

Try it online!

Anonymous code block that takes a number and a string and returns as a Match object.

### Explanation:

```
->\a,\b{                }  # Anonymous code block taking params a and b
        b~~/           /   # Match using b
            (10|.)           # 10 or a single digit
                  **{a}      # Exactly a times, being greedy

```

# Answer
> 5 votes
# Python 3, 47 bytes

```
lambda s,n:[*s.replace(b'\1\0',b'\n',len(s)-n)]

```

Try it online!

Takes the "one line" as a bytestring with raw bytes `\x00 - \x09`. If it's not acceptable:

# Python 3, 56 bytes

```
lambda s,n:[x-48for x in s.replace(b'10',b':',len(s)-n)]

```

Try it online!

Takes "one line" as bytestring.

# Answer
> 4 votes
# Python 3, ~~71 68~~ 59 bytes

down another 9 bytes thanks to ovs.

```
lambda n,s:[int(c,11)for c in s.replace('10','a',len(s)-n)]

```

Try it online!

I was iniitially trying to use `str.partition()` recursively, but using `replace` smacked me in the face not too long after. Can anyone improve on this?

Also, here's a TIO link that I used to make the test cases into something more copy/pasteable

# Answer
> 4 votes
# Ruby, 57 bytes

```
->n,m{m.sub!"10",?A while m[n];m.chars.map{|c|c.to_i 16}}

```

Try it online!

This may turn out to be not the golfiest approach, but it looks like a fun idea to temporarily substitute `10` for a hex `A`, which incidentally is also a high mark (if we consider A-F grading system :))

# Answer
> 4 votes
# JavaScript, ~~57~~ 52 bytes

```
n=>g=s=>s[n]?g(s.replace(x=10,`x`)):[...s].map(eval)

```

Try It Online

# Answer
> 4 votes
# Haskell, 68 bytes

```
n!('1':'0':x)|n-2<length x=10:(n-1)!x
n!(s:x)=read[s]:(n-1)!x
n!_=[]

```

Try it online!

Greedily take 10s as long as there are more digits than marks remaining.

# Answer
> 3 votes
# Haskell, 98 bytes

```
n!x=[y|y<-s x,y==take n y]!!0
s('1':'0':x)=do y<-s x;[1:0:y,10:y]
s(x:y)=(read[x]:)<$>s y
s _=[[]]

```

Try it online or test all!

## Explanation

The function `s` does all possible splits, for example: `"1010"` becomes `[[1,0,1,0],[10,1,0],[1,0,10],[10,10]]`, note how the longest splits end up at the beginning (because `1:0:y` comes before `10:y`).

With that in mind, we can take all these values and filter the `y`s out where `y == take n y` which keeps also splits that are shorter than required. For example with `4` we leave the list the same `[[1,0,1,0],[10,1,0],[1,0,10],[10,10]]`.

Now we can just get the first element in that list because the inputs will always be valid (eg. `5!"1010"` would give `[1,0,1,0]` too, but we don't need to handle it).

**Note:** I somehow miscounted.. `y==take n y` is the same length as `length y==n` :S

# Answer
> 3 votes
# , 63 bytes

While the length of the string is larger than `n`, substitute the next 10 you reach for a `":"` (the ASCII character after 9). Then split into numbers by taking the ASCII value of each char in the string.

```
function(n,x){while(nchar(x)>n)x=sub(10,":",x);utf8ToInt(x)-48}

```

Try it online!

# Answer
> 2 votes
# JavaScript (Babel Node),  ~~70 69~~  59 bytes

Takes input as `(n)(line)`.

```
n=>s=>(a=s.match(/10|./g)).flatMap(x=>x>9&&!a[--n]?[1,0]:x)

```

Try it online!

### Commented

```
n => s =>                       // given n and s
  (a = s.match(/10|./g))        // split s into marks; a '1' followed by a '0' is always
                                // interpreted as '10'
  .flatMap(x =>                 // for each mark x:
    x > 9 &&                    //   if x = '10',
    !a[--n] ?                   //   then decrement n; if a[n] is undefined:
      [1, 0]                    //     yield [1, 0]
    :                           //   else:
      x                         //     yield the mark unchanged
  )                             // end of flatMap()

```

---

# JavaScript (ES6),  ~~64~~  59 bytes

*Saved 5 bytes thanks to @guest271314*

Takes input as `(n)(line)`.

```
n=>g=([...s])=>1/s[n]?g(eval(`[${s}]`.replace('1,0',10))):s

```

Try it online!

### Commented

```
n =>                            // main function, taking n
  g = ([...s]) =>               // g = recursive function, taking s
                                //     (which is either a string or an array)
    1 / s[n] ?                  // if s[n] is defined (i.e. we have too many marks):
      g(                        //   do a recursive call to g:
        eval(                   //     build a new array by evaluating ...
          `[${s}]`              //       ... the string representation of s[] where the
          .replace('1,0', 10)   //       first occurrence of '1,0' is replaced with '10'
        )                       //     end of eval()
      )                         //   end of recursive call
    :                           // else:
      s                         //   return s

```

# Answer
> 2 votes
# Perl 5 `-plF`, 39 bytes

```
$a=<>;$_="@F";s/1 0/10/ while$a-1<y/ //

```

Try it online!

# Answer
> 2 votes
# Clean, 128 bytes

```
import StdEnv
@[]=[[]]
@['10':t]=[u++v\\u<-[[10],[1,0]],v<- @t];@[h:t]=[[digitToInt h:v]\\v<- @t]
?n l=hd[e\\e<- @l|length e==n]

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 13 bytes

```
.œsù.ΔïTÝÃJ¹Q

```

Try it online! or as a Test Suite

**Explanation**

```
.œ              # partitions of the first input
  sù            # of a length equal to the second input
    .Δ          # find the first partition that returns true when:
      ï         # each element is converted to integer
       TÝÃ      # and only numbers in [0 ... 10] are kept
          J     # then join it together
           ¹Q   # and compare it to the first input for equality

```

# Answer
> 2 votes
# Java (OpenJDK 8), 78 bytes

A nice one-liner using the streams API.

```
(n,l)->l.join(":",l.split("10",l.length()-n+1)).chars().map(i->i-48).toArray()

```

Try it online!

---

**How it works**

```
(n,l)->                     // Lambda function taking int and string
  l.join(":",               // Join the following array with colons
    l.split("10",           // Split the original string on "10"...
      l.length()-n+1))      // But limit the parts to the difference between the length
                            // and expected length, to only remove  required number of 10s
  .chars()                  // Convert to an intstream of codepoints
  .map(i->i-48)             // Remove 48 to get the numeric value of each codepoint
  .toArray()                // Return an int array

```

# Answer
> 1 votes
# Red, 91 bytes

```
func[n s][while[n < length? s][replace s"10""a"]foreach c s[prin[either c =#"a"[10][c]""]]]

```

Try it online!

# Answer
> 1 votes
# Jelly, 18 bytes

```
Ḍ⁵⁻ƊƝr1ŒpS‘⁼ɗƇḢk⁸Ḍ

```

Try it online!

# Answer
> 1 votes
# Stax, 11 bytes

```
ô 0┤'ï╒Äì√¡

```

Run and debug it

It was very interesting to find a way to outgolf the V answer.

## Explanation

```
|!{11rJj-!}jJ
|!            all array partitions of length n
  {       }j  first element which satisfies:
   11r        range 0-10
      J       joined with spaces
       j      split on spaces
        -     set difference with the current iteration
         !    negated
              is true?
            J join with spaces

```

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


title: Play tic-tac-toe and never lose

text:
# Question
Title: Play tic-tac-toe and never lose
(There exists some challenges that require to use the best strategy, but here we don't. Even if you are able to win, you are allowed to make a tie)

# Challenge

Write a program which plays the game tic-tac-toe. It must not lose (therefore, it should end the game either with a tie or by winning).

# Allowed I/O methods

1. Input may be the current board. You can assume that all previous moves of the 2nd player were played by your engine.
2. Input may be the first player's moves, and your function stores which moves happened in the past. In this case the function is called multiple times, once for each move; or the function/program prompt input for multiple times.
3. You are allowed to take an extra input saying if you are the first player, or write two (possibly related) functions to solve the first-player problem and the second-player one. If your program need use the input method 2 (multiple call), you can decide what is passed in the first call.
4. Output may be the board after your turn.
5. Output may be your move.
6. A move may be represented as a pair of numbers (can be 0-indexing or 1-indexing), a number in range 0~8, or a number in range 1~9.
7. The board may be represented as a 3×3 array, or an array of length 9. Even if the language have 0-indexing array, you can use 1-indexing.
8. The cells on the grid may use any 3 different values to indicate `X`, `O` and empty.

# Winning criteria

Shortest code in each language win.

# Answer
# Befunge, ~~181~~ 168 bytes

```
>>4&5pp20555>>03>16p\::5g8%6p5v
 ^p5.:g605$_ #!<^_|#:-1g61+%8g<
543217539511|:_^#->#g0<>8+00p3+5%09638527419876
v<304p$_v#:->#$$:2`#3_:^
>#\3#13#<111v124236478689189378

```

Positions on the board are numbered 1 to 9. By default you get the first move, but if you want to allow the computer to go first, you can just enter 0 for your first move. When you've made a move, the computer will respond with a number indicating their move.

There are no checks to make sure you don't enter a valid move, and there also no checks to see if anyone has won or lost. Once their are no more moves to be made, the program just goes into an infinite loop.

It's a bit difficult to test this online, since there are no online interpreters with interactive input. However, if you know what moves you're going to make in advance (which assumes you know how the computer is going to respond), you can kind of test on TIO with those moves preprogrammed.

**User plays first:** Try it online!
**Computer plays first:** Try it online!

To makes it easier to see what's going on, I've also got a version that outputs the board between moves.

**User plays first:** Try it online!
**Computer plays first:** Try it online!

Note that you'll have to wait for TIO to timeout before you can see the results.

**Explanation**

The board is stored in the Befunge memory area as a flat array of 9 values, indexed from 1 to 9. This lets us use the zero offset as a special case "no move" when we want to let the computer play first. Player moves are stored as 4, and computer moves as 5. To start with all positions are initialised to 32 (the Befunge memory default), so whenever we access the board we mod with 8, so we'll get back either 0, 4 or 5.

Given that arrangement, if we sum the values of any three positions on the board, we know that the computer is one move away from winning if the total is 10, the player is one move away from winning if the total is 8, and the positions are shared between computer and player (but still one position is free) if the total is 9.

Our entire strategy is based around this concept. We have a routine that takes a list of triples indicating sets of three positions on the board, we calculate the sum of those positions, and if the sum equals a certain total, the computer moves to whichever of the positions in the set is free.

The main list of triples that we test are the winning combinations (1/2/3, 1/5/9, 1/4/7, etc.). We first look for a total of 10 (the computer is about to win), and then a total of 8 (the player is about to win and we need to block that move). Less obviously, we also check for a total of 9 (if the player and computer each have one of the positions, it's a good strategy for the computer to take the third).

Prior to that last scenario, the other strategic move we make is to check all the corner sets (1/2/4, 2/3/6, etc.) as well as two opposing corner combinations (1/8/9 and 3/7/8). If any of these combinations sum to 8, i.e. the player has taken two of the positions, it's a good strategy for the computer to take the remaining free position.

Finally, there are a two special case moves. First, we always try and take the center position before any other move. This is achieved with the same routine as all our other moves, just passing in a single triple, 5/5/5, and a target sum of 0. Additionally, if all other test have failed to find a move, we try to take one of the top corners as a last resort. Again this is simply achieved by testing the triples 1/1/1 and 3/3/3, with a target sum of 0.

I don't think this is necessarily a perfect strategy - there may be games that the computer draws which could potentially have been won - but it's good enough to never lose a match. I've run a test script that tried to play every possible move against the computer, and for every valid sequence of moves, the computer either won or drew the game.
> 6 votes

# Answer
# Python 3, 18 bytes

```
lambda a:a+a%2*2-1

```

Try it online!

This brilliant AI will always force a tie, and sometimes win if you let it. The grid is numbered in a spiral, like so:

```
1 2 3
8 9 4
7 6 5

```

and the computer always goes first. For the first move, input "10". This is a little redundant because it always goes in the same place, but it's already built into the algorithm so ¯\\\_(ツ)\_/¯

By going in the middle first, the game is essentially converted into 1 dimension, with the only way to win being 3 in a row along the sides. The divides all of these remaining 8 squares into pairs, and always goes in the other square in the pair. For example, if you go in square 1, it goes in square 2. If you go in square 2, it goes in square 1. The nice thing about this system is that it will never make an illegal move, as well as never losing.

This was actually from a magic trick invented by Martin Gardner, where you can predict the outcome of a game of tic-tac-toe. Every game ends the exact same, including rotation, or the computer wins. It "never loses".

This is definitely my favorite solution to a code golf that I ever have found, and probably ever will find.
> 5 votes

# Answer
# Python 2: ~~399~~ ~~401~~ ~~349~~ ~~333~~ ~~317~~ 370 bytes

2x Bug Fix: credit to l4m2

-52 chars: credit to undergroundmonorail

-16 chars: credit to Jonathan Frech

-26 chars: credit to user202729

```
def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
 for i in 5,4,2,8,6:
    if i in a:return I(i)
 return I(a[0])

```

Try it Online!

On the first day of a linear algebra course I took last semester, my astute graduate student instructor proposed that if you represent the tic-tac-toe board as the the matrix:

```
4 | 9 | 2
--+---+--
3 | 5 | 7
--+---+--
8 | 1 | 6

```

then getting three in a row is equivalent to picking three numbers in the range \[1,9\] that add up to 15. This answer exploits this idea. The function takes a list containing nine numbers representing the board. 0 indicates an empty space, 1 is occupied by the opponent, and 2 represents a previous play made by the program. The first 3 lines figure out what numbers the program has picked (p), the opposition has picked (o), and are still available (a). It then looks through the available numbers and sees if any of them, combined with two numbers it has already picked add to fifteen. If it does, it will pick that square and win. If there are no immediate winning moves, it will check to see if the opponent can win using the same method. If they can, it will take their winning square. If there is neither a winning nor blocking move available, it will move in a corner. This prevents a fools mate:

```
- - -
- X -
- - -

- O -             # Bad Move
- X -
- - -

- O X
- X -
- - -

- O X
- X -
O - -

- O X
- X -
O - X

```

If none of these situations occur, it will choose a square arbitrarily. The function outputs a number \[0,8\] representing the 0 indexed square chosen by the algorithm.

Edit: The algorithm now prioritizes the center over the diagonal, which will prevent another fools mate possibility pointed out by l4m2 and related strategies.

Edit: To clarify, the function takes in a board in the form of an array and outputs a move as an integer on \[0,8\]. Because this I/O strategy is so clunky , here's a wrapper script that makes it more interactive. It takes a single command line argument, which should be 1 if the player goes first, and 0 if the program goes first.

```
import sys

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
     for i in 5,4,2,8,6:
        if i in a:return I(i)
 return I(a[0])

board = [0,0,0,0,0,0,0,0,0]
rep = {0:"-",1:"X",2:"O"}

turn = int(sys.argv[1])
while True:
    for i in range(3):
        print rep[board[i*3]]+" "+rep[board[i*3+1]]+" "+rep[board[i*3+2]]
        print
    if turn:
        move = int(raw_input("Enter Move [0-8]: "))
    else:
        move = f(board)
    board[move] = turn+1
    turn = (turn+1)%2

```
> 3 votes

# Answer
# Python 3: 341 bytes

So, my first attempt of code golfing, nice challenge! I thought of something similar myself with a complete game in mind though. Here is the AI code:

```
def e(b,t):return any([b[i]==b[i+d]==b[i+2*d]==t for i,d in((0,1),(3,1),(6,1),(0,3),(1,3),(2,3),(0,4),(2,2))])
def n(b,t,d=8):
    if e(b,t):return 0,1
    if e(b,-t):return 0,-1
    if all(b):return 0,0
    x=-2
    for m in range(9):
        if b[m]==0:
            b[m]=t;s,b[m]=-n(b,-t,d-1)[1],0
            if s>x:x,y=s,m
    return y,x

```

**Try online**
Try the code here.
**Input/output**

Function `n` takes a 1D array as input where X and O are represented by 1 and -1, and empty squares by 0. Example board:

```
b = [0, 1, 0, -1, 0, -1, 0, 0, 1]

```

equals

```
[' ', 'X', ' ']
['O', ' ', 'O']
[' ', ' ', 'X']

```

It then outputs the best move (board index 0 to 8) for the given player along with its evaluation:

* Score = 1: Current player wins
* Score = -1: Other player wins
* Score = 0: Draw if both players play perfectly \

**Explanation**
Function 'n' is a Negamax framework where it goes through the entire tree of possible solutions from the given board state until the game is finished (a player wins or board is full). For each possible move it goes depth first and checks all possible outcomes of that move until the end.

If the score from a move is larger than the current best (set to -2 as default to always get a better move to play) the best score and best move is updated. At the end the best move and score is returned. \

**Commented code**

```
# Checks if the given player has 3 in a row and returns 1 if so
def evaluate(board,turn):
    for i, d in (0,1),(3,1),(6,1),(0,3),(1,3),(2,3),(0,4),(2,2):
        if board[i]==b[i+d]==b[i+2*d]==turn: return 1

# Negamax recursive function
def negamax(board, turn, depth=8):

    # Checks if player or opponent has won
    if evaluate(board,turn): return 0,1
    if evaluate(board,-turn): return 0,-1

    # Checks if board is full
    if all(board): return 0,0

    # Goes through all possible moves in the board (available spots)
    best_score = -2
    for index in range(9):
        if board[index]==0:

            # Make the move, evaluate position, and unmake the move
            board[index] = turn
            score = -negamax(board, -turn, depth-1)[1]
            board[index] = 0

            # If score was better than previous best score, update best score and move
            if score > best_score:
                best_score, best_move = score, index

    # Return best move and score after it has gone through all possibilities
    return best_move, best_score

```
> 0 votes

---
Tags: code-golf, board-game, tic-tac-toe
---


title: Polynomial Laplace transform

text:
# Question
Title: Polynomial Laplace transform
This is a repost of this challenge, intended to revamp it for looser I/O formats and updated rules

You are to write a program which takes an integer polynomial in \\$t\\$ as input and outputs the Laplace transform of this polynomial. Some definitions and properties:

* The Laplace transform of a given function \\$f(t)\\$ is

$$\mathcal{L}\\{f(t)\\} = F(s) = \int\_0^\infty f(t)e^{-st}dt$$

* The Laplace transform of \\$f(t) = t^n, \\, n = 0, 1, 2, ...\\$ is

$$\mathcal{L}\\{t^n\\} = \frac{n!}{s^{n+1}}$$

* Laplace transforms distribute over addition:

$$\mathcal{L}\\{f(t)+g(t)\\} = \mathcal{L}\\{f(t)\\} + \mathcal{L}\\{g(t)\\}$$

* The Laplace transform of a constant multiplied by a function equals the constant multiplied by the transform:

$$\mathcal{L}\\{af(t)\\} = a\mathcal{L}\\{f(t)\\}$$

* An integer polynomial is a polynomial where each term has an integer coefficient, and a non-negative order

An worked example:

$$\begin{align} \mathcal{L}\\{3t^4+2t^2+t-4\\} & = \mathcal{L}\\{3t^4\\}+\mathcal{L}\\{2t^2\\}+\mathcal{L}\\{t\\}-\mathcal{L}\\{4\\} \\ & = 3\mathcal{L}\\{t^4\\}+2\mathcal{L}\\{t^2\\}+\mathcal{L}\\{t\\}-4\mathcal{L}\\{1\\} \\ & = 3\left(\frac{4!}{s^5}\right)+2\left(\frac{2!}{s^3}\right)+\left(\frac{1!}{s^2}\right)-4\left(\frac{0!}{s}\right) \\ & = \frac{72}{s^5}+\frac{4}{s^3}+\frac{1}{s^2}-\frac{4}{s} \end{align}$$

---

You may take input in a standard representation of a polynomial. Some examples (for \\$3x^4+2x^2+x-4\\$ as an example) are:

* A list of coefficients. `[-4, 1, 2, 0, 3]` or `[3, 0, 2, 1, -4]`
* Pairs of coefficients and powers. `[[3, 4], [2, 2], [1, 1], [-4, 0]]` and various different orderings
* A string, using whatever variable you like. `3x^4+2x^2+x-4`

Similarly, as the output will be a polynomial with negative orders, you may output in similar formats, such as (using \\$\mathcal{L}\\{3x^4+2x^2+x-4\\} = \frac{72}{s^5}+\frac4{s^3}+\frac1{s^2}-\frac4s\\$):

* A list of coefficients. `[72, 0, 4, 1, -4]` or `[-4, 1, 4, 0, 72]`
* Pairs of coefficients and powers. `[[72, -5], [4, -3], [1, -2], [-4, -1]]` and various different orderings (or the positive versions of the powers)
* A string, using whatever variable you like. `72s^-5+4s^-3+s^-2-4s^-1`

If you have an alternative I/O method you're unsure about, please comment below to ask.

This is so the shortest code in bytes wins.

# Answer
> 7 votes
# Haskell, 25 bytes

```
zipWith(*)$scanl(*)1[1..]

```

Try it online!

Pretty straightforward: Generates the list of factorials `[1,1,2,6,...]` with a `scanl`, then does `zipWith(*)` to multiply each element of the input by the corresponding value.

**32 bytes**

```
foldr(\(i,x)r->x:map((i+1)*)r)[]

```

Try it online!

A pretty folding-based solution. Takes inputs as `(exponent, coefficient)` pairs.

# Answer
> 6 votes
# convey, 15 bytes

```
v"*<
0+1"
 1{*}

```

Try it online!

The two left columns copy `"` 1, 2, 3, … into the top `*`. The value in the top right gets multiplied by that every lap, so we get (starting with an extra 1 = 0!) 1!, 2!, 3!, … copied into the bottom `*`. `{` reads the input, multiplies it with the factorials and outputs them `}`.

# Answer
> 5 votes
# Jelly, 4 bytes

```
J’!×

```

Takes input as list of coefficients.

## Explanation

```
J’!×

J   | Returns an array of elements from 1 to length of input array
 ’  | Subtracts 1 from each
  ! | Factorial each
   ×| Multiply each item in the original array by the created array

```

Try it online!

# Answer
> 5 votes
# APL (Dyalog Unicode), 3 bytes

```
×∘!

```

Try it online!

Takes the liberal I/O to the extreme: takes the polynomial \\$ 3x^4 + 2x^2+x-4 \\$ as two arguments, the coefficients on the left and the powers on the right in decreasing order and including zero terms, as in `3 0 2 1 ¯4 f 4 3 2 1 0`. Returns the polynomial as a vector of coefficients.

# Answer
> 4 votes
# PowerShell, 28 bytes

Input as a list of coefficients

```
$p++;$args|%{$p*$_;$p*=++$i}

```

Try it online!

# Answer
> 3 votes
# Wolfram Language (Mathematica), 10 bytes

```
#2!#&@@@#&

```

Try it online!

Input a list of coefficient/power pairs, including zero coefficients, sorted by power, and output a list of corresponding coefficients.

---

The built-in is longer: **23 bytes**

```
LaplaceTransform[#,t,]&

```

Try it online!

Input a polynomial in terms of `t`, and output one in terms of `Null`.

# Answer
> 3 votes
# APL (Dyalog Unicode), 7 bytes

```
⊢×!∘⍳∘≢

```

Try it online!

Uses `⎕IO←0` (0-indexing)

Input as a list of coefficients.

# Answer
> 2 votes
# JavaScript (ES6),  ~~31~~  29 bytes

I/O: lists of coefficients, from lowest to highest degree.

```
a=>a.map((v,i)=>v*=p=i?p*i:1)

```

Try it online!

### Commented

```
a =>              // a[] = polynomial coefficients
  a.map((v, i) => // for each coefficient v at position i in a[]:
    v *=          //   multiply v by:
      p =         //     the updated factorial p, which is:
        i ?       //       if i > 0:
          p * i   //         multiplied by i
        :         //       else:
          1       //         initialized to 1
  )               // end of map()

```

# Answer
> 2 votes
# Scala 3, ~~52~~ 48 bytes

```
p=>p.indices.scanLeft(1)(_*_.+(1))zip p map(_*_)

```

Try it online!

Input and output as a list of integers, from lowest to highest degree.

`p.indices` gives us a range from 0 to `p.size - 1`. Scanning left with multiplication gives the factorial at each index, but since the first element is 0, we need to add 1 (hence `_.+(1)`). Then all the factorials are zipped with the coefficients and multiplied together.

# Answer
> 2 votes
# Retina, 30 bytes

```
L$`.+
$&$:&*
+`\d+_
$.(*$(_$%'

```

Try it online! I/O is a newline-delimited list of coefficients from lowest to highest degree. Explanation:

```
L$`.+
$&$:&*

```

For each coefficient, append a number of underscores equal to its degree.

```
+`\d+_
$.(*$(_$%'

```

Until no underscores remain, multiply each coefficient by the number of following underscores, deleting one in the process.

# Answer
> 2 votes
# SageMath, ~~27~~ 23 bytes

Saved 4 bytes thanks to ovs!!!

```
lambda f:f.laplace(x,x)

```

Try it online!

Takes a function of \\$x\\$ as input and returns the Laplace transform as a function of \\$x\\$.

# Answer
> 2 votes
# Python 2, 39 bytes

```
p=i=1
while 1:print p*input();p*=i;i+=1

```

Try it online!

Input and output are coefficients, one per line, starting with smallest degree (nearest zero).

Taking in `(coefficient, exponent)` pairs turns out slightly longer.

```
p=1
while 1:x,i=input();print p*x;p*=i+1

```

Try it online!

# Answer
> 2 votes
# Raku, 15 bytes

```
*Z*1,|[\*] 1..*

```

Try it online!

`[\*] 1..*` is the infinite sequence of factorials starting with `1!`. An additional `1` (for `0!`) is pasted on to the front, then the whole thing is zipped-with-multiplication (`Z*`) with the sole input sequence `*`.

# Answer
> 2 votes
# , ~~34~~ ~~28~~ 25 bytes

```
(x=scan())*gamma(seq(!x))

```

Try it online!

Pretty straightforward.
R lacks a short-named factorial function, but has `gamma`.
Generates sequence along `x` using trick from @Giuseppe.

# Answer
> 2 votes
# Japt `-m`, 3 bytes

```
*Vl

```

Try it here

# Answer
> 1 votes
# Charcoal, 12 bytes

```
ＩＥＡ×ιΠ⊞Ｏυ∨κ¹

```

Try it online! Link is to verbose version of code. I/O is a list of coefficients from lowest to highest degree. Explanation:

```
  Ａ             Input array
 Ｅ              Map over elements
    ι           Current element
   ×            Multiplied by
     Π          Product of
        υ       Predefined empty list
      ⊞Ｏ        After pushing
         ∨      Logical Or of
          κ     Current index
           ¹    Literal 1
Ｉ               Cast to string
                Implicitly print

```

# Answer
> 1 votes
# 05AB1E, 4 bytes

```
εN!*

```

Try it online.

Or alternatively:

```
ā<!*

```

Try it online.

Both take a list of coefficients as input.

**Explanation:**

```
ε     # Map over each value of the (implicit) input-list
 N    #  Push the 0-based map-index
  !   #  Pop and take it's faculty
   *  #  Multiply it by the current value
      # (after the map, the resulting list is output implicitly)

ā     # Push a list in the range [1,length] based on the (implicit) input-list
 <    # Decrease each by 1 to make the range [0,length)
  !   # Take the faculty of each
   *  # And multiply it to the values at the same positions in the (implicit) input-list
      # (after which the result is output implicitly)

```

# Answer
> 0 votes
# Pari/GP, 10 bytes

A built-in.

```
serlaplace

```

Try it online!

---
Tags: code-golf, math, polynomials, calculus
---


# Question
Title: Partition a square grid into parts of equal area
This challenge is based on the following puzzle: You are given an `n` by `n` grid with `n` cells marked. Your job is to the partition the grid into `n` parts where each part consists of exactly `n` cells, each containing exactly one marked cell.

# Example

Here is a puzzle on the left and its (unique) solution on the right:

# Challenge

You will be given a set of `n` zero-indexed coordinates in any reasonable format.

```
[(0,0), (0,3), (1,0), (1,1), (2,2)]

```

And your job is to write a program that returns any valid parition (again, in any reasonable format).

```
[
  [(0,0), (0,1), (0,2), (1,2), (1,3)],
  [(0,3), (0,4), (1,4), (2,4), (3,4)],
  [(1,0), (2,0), (3,0), (4,0), (4,1)],
  [(1,1), (2,1), (3,1), (3,2), (4,2)],
  [(2,2), (2,3), (3,3), (4,3), (4,4)]
]

```

If the puzzle has no solution, the program should indicate that by throwing an error or returning an empty solution.

# Input/Output Examples

```
[(0,0)]               => [[(0,0)]]

[(0,0), (1,1)]        => [
                          [(0,0), (1,0)],
                          [(0,1), (1,1)]
                         ]

[(0,0), (0,1), (1,0)] => [] (no solution)

[(0,0), (0,1), (0,2)] => [
                          [(0,0), (1,0), (2,0)],
                          [(0,1), (1,1), (2,1)],
                          [(0,2), (1,2), (2,2)],
                         ]

[(0,0), (0,2), (1,2)] => [
                          [(0,0), (1,0), (2,0)],
                          [(0,1), (0,2), (1,1)],
                          [(1,2), (2,1), (2,2)],
                         ]

```

# Scoring

This is , so shortest code wins.

# Answer
> 4 votes
# Jelly, 26 bytes

```
Jṗ2Œ!s€L_/ƝÆḊ€ỊẠƲ€Ạ$Ƈi"Ạ¥Ƈ

```

Try it online!

This is *wildly* inefficient, around \\$O({n^2}!)\\$ for an input of \\$n\\$ co-ordinates. As such, it times out on TIO for \\$n \ge 3\\$. I've tested it locally for the other test cases and it works as expected.

This takes input 1 indexed, and it returns a list of valid partitions. The Footer adjusts the output for you.

## How it works

```
Jṗ2Œ!s€L_/ƝÆḊ€ỊẠƲ€Ạ$Ƈi"Ạ¥Ƈ - Main link. Takes a list of n coordinates on the left
J                          - [1, 2, ..., n]
 ṗ2                        - All pairs; [[1, 1], [1, 2], ..., [n, n]]
   Œ!                      - All permutations
       L                   - Yield n
     s€                    - Split each permutation into n parts
                   $Ƈ      - Keep the matrices for which the following is true:
                Ʋ€         -   Over each row:
          Ɲ                -     For each overlapping pair:
        _/                 -       Get the successive differences
           ÆḊ€             -     Get the norm for each
              ỊẠ           -     All are between -1 and 1?
                  Ạ        -   This is true for all rows?
                             This filters out matrices of non-adjacent coordinates
                        ¥Ƈ - Keep the matrices for which the following is true:
                     i"    -   Get the indices of each coordinate, or 0, if not in each row
                       Ạ   -   All non-zero?

```

# Answer
> 13 votes
# JavaScript (ES7), 166 bytes

Outputs a matrix of integers that describe the partition, or \\$false\\$ if there's no solution.

```
a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m

```

Try it online!

### How?

We first build a square matrix \\$m\\$ of size \\$N\times N\\$, where \\$N\\$ is the length of the input:

```
m = a.map(_ => [...a])

```

Each row of \\$m\\$ consists of a copy of the input, i.e. an array of \\$N\\$ coordinate pairs. The important point here is that all cells of \\$m\\$ are initialized to non-numeric values. We'll be able to detect them by applying the prefix increment operator `++`.

The recursive function \\$g\\$ takes a pointer \\$n\\$ into the input, the coordinates \\$(X,Y)\\$ of the previous cell, a counter \\$j\\$ that holds the number of filled cells in the current area, and a flag \\$i\\$ that is set when the marked cell is found in the area:

```
g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1

```

We test \\$a\[n\]\\$ to know if all areas have been processed and we test \\$a\[j\]\\$ to know if enough cells have been filled in the current area.

The main part of \\$g\\$ looks for the next cell of \\$m\\$ to fill by iterating on all of them:

```
m.some((r, y) =>          // for each row r[] at position y in m[]:
  r.some((v, x) =>        //   for each cell of value v at position x in r[]:
    ++v |                 //     if this cell is already filled (i.e. v is numeric)
    (X - x) ** 2 +        //     or the squared Euclidean distance between
    (Y - y) ** 2 -        //     (X, Y) and (x, y)
    1 ?                   //     is not equal to 1:
      0                   //       this is an invalid target square: do nothing
    :                     //     else:
      g(                  //       do a recursive call to g:
        r[x] = n,         //         pass n unchanged and fill the cell with n
        x, y,             //         pass the coordinates of the current cell
        j + 1,            //         increment j
        i |               //         update i:
        x + [,y] == a[n]  //         set it if (x, y) = a[n]
      ) ?                 //       if the result of the call is truthy:
        1                 //         return 1
      :                   //       else:
        r[x] = v          //         reset the cell to NaN
  )                       //   end of inner map()
)                         // end of outer map()

```

---
Tags: code-golf, combinatorics, grid, set-partitions
---