# Question
Title: Mozilla/1.0 Mozilla/2.0 Mozilla/3.0 Mozilla/4.0 Mozilla/5.0
> In the beginning there was NCSA Mosaic, and Mosaic called itself **`NCSA_Mosaic/2.0 (Windows 3.1)`**, and Mosaic displayed pictures along with text, and there was much rejoicing.

***15 years later...***

> And then Google built Chrome, and Chrome used Webkit, and it was like Safari, and wanted pages built for Safari, and so pretended to be Safari. And thus Chrome used WebKit, and pretended to be Safari, and WebKit pretended to be KHTML, and KHTML pretended to be Gecko, and all browsers pretended to be Mozilla, and Chrome called itself **`Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US) AppleWebKit/525.13 (KHTML, like Gecko) Chrome/0.2.149.27 Safari/525.13`**, and the user agent string was a complete mess, and near useless, and everyone pretended to be everyone else, and confusion abounded.

Read full story here...

Given a User Agent string, return the browser that it corresponds to.

You must support:

* Chrome/Chromium\*
* Opera
* Firefox
* IE
* Edge
* Safari

Your code only needs satisfy all of these test cases.

```
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/603.2.4 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.4
Safari

Mozilla/5.0 (Windows NT 10.0; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Windows NT 6.1; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Windows NT 6.3; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 6.1; WOW64; Trident/7.0; rv:11.0) like Gecko
IE

Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/603.3.8 (KHTML, like Gecko) Version/10.1.2 Safari/603.3.8
Safari

Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.79 Safari/537.36 Edge/14.14393
Edge

Mozilla/5.0 (Windows NT 6.3; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/56.0.2924.87 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/52.0.2743.116 Safari/537.36 Edge/15.15063
Edge

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 6.3; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Windows NT 6.1; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; rv:11.0) like Gecko
IE

Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36
Chrome

Mozilla/5.0 (X11; Linux x86_64; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0
Firefox

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/603.2.5 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.5
Safari

Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/59.0.3071.109 Chrome/59.0.3071.109 Safari/537.36
Chromium

Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Windows NT 6.1; Trident/7.0; rv:11.0) like Gecko
IE

Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.78 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_3) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/603.1.30 (KHTML, like Gecko) Version/10.1 Safari/603.1.30
Safari

Mozilla/5.0 (Windows NT 5.1; rv:52.0) Gecko/20100101 Firefox/52.0
Firefox

Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Firefox/52.0
Firefox

Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Firefox/45.0
Firefox

Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 10.0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_5) AppleWebKit/603.2.5 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.5
Safari

Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.86 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36 OPR/46.0.2597.57
Opera

Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.86 Safari/537.36 OPR/46.0.2597.32
Opera

Mozilla/5.0 (Windows NT 6.2; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 6.3; WOW64; Trident/7.0; rv:11.0) like Gecko
IE

Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.104 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.109 Safari/537.36
Chrome

Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.0; Trident/5.0;  Trident/5.0)
IE

Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.1; Trident/5.0;  Trident/5.0)
IE

Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:54.0) Gecko/20100101 Firefox/54.0
Firefox

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/603.3.8 (KHTML, like Gecko) Version/10.1.2 Safari/603.3.8
Safari

Mozilla/5.0 (Windows NT 6.1; rv:52.0) Gecko/20100101 Firefox/52.0
Firefox

Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.78 Safari/537.36
Chrome

Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/58.0.3029.110 Chrome/58.0.3029.110 Safari/537.36
Chromium

Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36 OPR/46.0.2597.39
Opera

Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; Touch; rv:11.0) like Gecko
IE

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.106 Safari/537.36
Chrome

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36
Chrome

Mozilla/5.0 (Windows NT 10.0; WOW64; rv:53.0) Gecko/20100101 Firefox/53.0
Firefox

Mozilla/5.0 (Windows NT 6.1; WOW64; rv:53.0) Gecko/20100101 Firefox/53.0
Firefox

```

Remember, this is , so the code with the least bytes wins.

---

<sup>* Chromium and Chrome can be interchanged.</sup>

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

```
.+Tr.+
IE
.+E.+
Edge
.+P.+
Opera
.+?([CFS]\w+).+
$1

```

Try it online! Explanation: Opera can be identified by its `(O)P(R/)` platform and IE by its `Tr(ident)` engine. The other browsers include their full name in their user agent, but Edge puts theirs last so it has to be processed separately from the others. Edit: Saved 1 byte by detecting Edge after Trident and 1 byte by detecting Opera using just the `P` both thanks to @ThePirateBay.
> 7 votes

# Answer
# Jelly, 27 bytes

```
-7ịO%25ị“ðh³`Ẹ|Ḥ©®jḋƝ,Ṁ⁵»Ḳ¤

```

A monadic link accepting and returning lists of characters.

**Try it online!** or see a test suite (shows `expected output -> output`; tests sorted by browser).

### How?

```
-7ịO%25ị“ðh³`Ẹ|Ḥ©®jḋƝ,Ṁ⁵»Ḳ¤ - Link: list of character, userAgentString
-7ị                         - -7 index into userAgentString (last character is 0)
   O                        - cast to ordinal
    %25                     - modulo by 25
                          ¤ - nilad followed by link(s) as a nilad:
        “ðh³`Ẹ|Ḥ©®jḋƝ,Ṁ⁵»   - compression of dictionary words:
                            -   = "IE Firefox Opera Safari Chrome Edge"
                         Ḳ  - split at spaces
       ị                    - index into (1-indexed and modular)

```
> 3 votes

# Answer
# JavaScript, ~~113~~ ~~83~~ 82 bytes

Same approach as the Retina answer by Neil.

```
f=_=>_[x=`includes`]`P`?`Opera`:_[x]`Tr`?`IE`:_[x]`E`?`Edge`:_.match(/[CFS]\w+/)[0]

```

Previous attempts:

```
// With String.prototype.test, 83 bytes
f=_=>/P/.test(_)?`Opera`:/Tr/.test(_)?`IE`:/E/.test(_)?`Edge`:_.match(/[CFS]\w+/)[0]

// With array filtering, 113 bytes
f=_=>_[o=`Opera`,i=`includes`]`P`?o:[o,`Edge`,`Firefox`,`Chromium`,`Chrome`,`Safari`].filter(b=>_[i](b))[0]||`IE`

```

## Try it:

```
const f=_=>_[x=`includes`]`P`?`Opera`:_[x]`Tr`?`IE`:_[x]`E`?`Edge`:_.match(/[CFS]\w+/)[0]

const testData = {
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/603.2.4 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.4': 'Safari',
  'Mozilla/5.0 (Windows NT 10.0; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.1; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.3; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 6.1; WOW64; Trident/7.0; rv:11.0) like Gecko': 'IE',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/603.3.8 (KHTML, like Gecko) Version/10.1.2 Safari/603.3.8': 'Safari',
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.79 Safari/537.36 Edge/14.14393': 'Edge',
  'Mozilla/5.0 (Windows NT 6.3; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/56.0.2924.87 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/52.0.2743.116 Safari/537.36 Edge/15.15063': 'Edge',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 6.3; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.1; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; rv:11.0) like Gecko': 'IE',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (X11; Linux x86_64; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0': 'Firefox',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/603.2.5 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.5': 'Safari',
  'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/59.0.3071.109 Chrome/59.0.3071.109 Safari/537.36': 'Chromium',
  'Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.1; Trident/7.0; rv:11.0) like Gecko': 'IE',
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.78 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_3) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/603.1.30 (KHTML, like Gecko) Version/10.1 Safari/603.1.30': 'Safari',
  'Mozilla/5.0 (Windows NT 5.1; rv:52.0) Gecko/20100101 Firefox/52.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Firefox/52.0': 'Firefox',
  'Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Firefox/45.0': 'Firefox',
  'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 10.0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_5) AppleWebKit/603.2.5 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.5': 'Safari',
  'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.86 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36 OPR/46.0.2597.57': 'Opera',
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.86 Safari/537.36 OPR/46.0.2597.32': 'Opera',
  'Mozilla/5.0 (Windows NT 6.2; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 6.3; WOW64; Trident/7.0; rv:11.0) like Gecko': 'IE',
  'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.104 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.109 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.0; Trident/5.0;  Trident/5.0)': 'IE',
  'Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.1; Trident/5.0;  Trident/5.0)': 'IE',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:54.0) Gecko/20100101 Firefox/54.0': 'Firefox',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/603.3.8 (KHTML, like Gecko) Version/10.1.2 Safari/603.3.8': 'Safari',
  'Mozilla/5.0 (Windows NT 6.1; rv:52.0) Gecko/20100101 Firefox/52.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.78 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/58.0.3029.110 Chrome/58.0.3029.110 Safari/537.36': 'Chromium',
  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36 OPR/46.0.2597.39': 'Opera',
  'Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; Touch; rv:11.0) like Gecko': 'IE',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.106 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36': 'Chrome',
  'Mozilla/5.0 (Windows NT 10.0; WOW64; rv:53.0) Gecko/20100101 Firefox/53.0': 'Firefox',
  'Mozilla/5.0 (Windows NT 6.1; WOW64; rv:53.0) Gecko/20100101 Firefox/53.0': 'Firefox'
}

Object.keys(testData).forEach(ua => {
  console.log('Expected: %s; actual: %s (input: %s)', testData[ua], f(ua), ua)
})
```
> 0 votes

# Answer
# Perl 5, 64 + 1 (-p) = 65 bytes

```
$_=/P/&&Opera||/Edge|Firefox/&&$&||/C/&&Chrome||/Tr/&&IE||Safari

```

Try it online!

The header and the -l in the TIO link are just to make the output easier to read when feeding the entire list of User-Agents. Without those, this meets the challenge, taking one string and returning the browser name.
> 0 votes

# Answer
# Kotlin, ~~133~~ ~~130~~ 128 bytes

```
"Tr|IE_E|Edge_P|Opera_mi|Chromium_C|Chrome_A|Safari".split("_").map{it.split("|")}.firstOrNull{it[0] in this}?.get(1)?:"Firefox"

```

## Beautified

```
    "Tr|IE_E|Edge_P|Opera_mi|Chromium_C|Chrome_A|Safari"
        .split("_")
        .map { it.split("|") }
        .firstOrNull {
            it[0] in this
        }?.get(1) ?: "Firefox"

```

## Test

```
fun String.f(): String =
"Tr|IE_E|Edge_P|Opera_mi|Chromium_C|Chrome_A|Safari".split("_").map{it.split("|")}.firstOrNull{it[0] in this}?.get(1)?:"Firefox"

data class Test(val input: String, val output: String)

val tests = listOf(
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/603.2.4 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.4",
                "Safari"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.3; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; WOW64; Trident/7.0; rv:11.0) like Gecko",
                "IE"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/603.3.8 (KHTML, like Gecko) Version/10.1.2 Safari/603.3.8",
                "Safari"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.79 Safari/537.36 Edge/14.14393",
                "Edge"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.3; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/56.0.2924.87 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/52.0.2743.116 Safari/537.36 Edge/15.15063",
                "Edge"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.3; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; rv:11.0) like Gecko",
                "IE"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/603.2.5 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.5",
                "Safari"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/59.0.3071.109 Chrome/59.0.3071.109 Safari/537.36",
                "Chromium"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; Trident/7.0; rv:11.0) like Gecko",
                "IE"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.78 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_3) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/603.1.30 (KHTML, like Gecko) Version/10.1 Safari/603.1.30",
                "Safari"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 5.1; rv:52.0) Gecko/20100101 Firefox/52.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Firefox/52.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Firefox/45.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_5) AppleWebKit/603.2.5 (KHTML, like Gecko) Version/10.1.1 Safari/603.2.5",
                "Safari"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.86 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36 OPR/46.0.2597.57",
                "Opera"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.86 Safari/537.36 OPR/46.0.2597.32",
                "Opera"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.2; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.3; WOW64; Trident/7.0; rv:11.0) like Gecko",
                "IE"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.104 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.109 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.0; Trident/5.0;  Trident/5.0)",
                "IE"
        ),
        Test(
                "Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.1; Trident/5.0;  Trident/5.0)",
                "IE"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:54.0) Gecko/20100101 Firefox/54.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/603.3.8 (KHTML, like Gecko) Version/10.1.2 Safari/603.3.8",
                "Safari"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; rv:52.0) Gecko/20100101 Firefox/52.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.78 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/58.0.3029.110 Chrome/58.0.3029.110 Safari/537.36",
                "Chromium"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36 OPR/46.0.2597.39",
                "Opera"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; Touch; rv:11.0) like Gecko",
                "IE"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.106 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/59.0.3071.115 Safari/537.36",
                "Chrome"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 10.0; WOW64; rv:53.0) Gecko/20100101 Firefox/53.0",
                "Firefox"
        ),
        Test(
                "Mozilla/5.0 (Windows NT 6.1; WOW64; rv:53.0) Gecko/20100101 Firefox/53.0",
                "Firefox"
        ))

fun main(args: Array<String>) {
    val answers = tests
        .map { (i, o) -> Triple(i, o, i.f()) }
    val t = answers
        .groupBy { it.second }
        .mapValues { it.value.groupBy { it.second == it.third }.mapValues { it.value.size } }
    for (f in t) {
        println(f)
    }
    println(answers.groupBy { it.second == it.third }.mapValues { it.value.size })
}

```

## TIO

TryItOnline

## Edits

* -3 jrtapsell \- Swapped destructuring for array access
* -2 jrtapsell \- Replaced contains with in
> 0 votes

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


title: Do the circles intersect?

text:
# Question
Title: Do the circles intersect?
This question is similar to Do the circles overlap?, except your program should return True if the circumference of one circle intersects the other, and false if they do not. If they touch, this is considered an intersection. Note that concentric circles only intersect when both radii are equal

Input is two x, y coordinates for the circle centres and two radius lengths, as either 6 floats or ints, in any order, and output a boolean value, (you may print True or False if you choose)

test cases are in format (x1, y1 x2, y2, r1, r2):

these inputs should output true:

```
0 0 2 2 2 2
1 1 1 5 2 2
0.55 0.57 1.97 2.24 1.97 2.12

```

these should output false:

```
0 0 0 1 5 3
0 0 5 5 2 2
1.57 3.29 4.45 6.67 1.09 3.25

```

# Answer
# Mathematica 67 bytes

This checks whether the area of the intersection of two disks is positive.

```
RegionMeasure@RegionIntersection[{#,#2}~Disk~#3,{#4,#5}~Disk~#6]>0&

```
> 3 votes

# Answer
# APL (Dyalog), 20 bytes

Uses Anders Kaseorg's formula: 0≤(*x*₁−*x*₂)²−(*r*₁−*r*₂)²+(*y*₁−*y*₂)²≤4*r**r*

Takes (*x*₁, *r*₁, *y*₁) as left argument and (*x*₂, *r*₂, *y*₂) as right argument.

```
(-/2*⍨-)(≤∧0≤⊣)4×2⊃×

```

Try it online!

The overall function's structure is a fork (3-train) where the tines are `-/2*⍨-` and `≤∧0≤⊣` and `4×2⊃×`\*. The middle tine takes the results of the side tines as arguments. The side tines use the overall function's arguments.

Right tine:
`×` multiply the arguments (*x**x*₂, *r**r*₂, *y**y*₂)
`2⊃` pick the second element (*r**r*₂)
multiply by four (4*r**r*₂)

Left tine:
`-` subtract the arguments (*x*₁−*x*₂, *r*₁−*r*₂, *y*₁−*y*₂)
`2*⍨` square ((*x*₁−*x*₂)², (*r*₁−*r*₂)², (*y*₁−*y*₂)²)
`-/` minus reduction i.e. alternate sum\* ((*x*₁−*x*₂)²−((*r*₁−*r*₂)²−(*y*₁−*y*₂)²))

Now we use these results as arguments to the middle tine:
`0≤⊣` is the left argument greater than or equal to zero
and
the left argument smaller than or equal to the right argument?

---

* due to APL's right associativity
> 3 votes

# Answer
# APL (Dyalog Classic), 17 bytes

```
(+/∧.≥+⍨)⎕,|0j1⊥⎕

```

Try it online!

expects two lines of input: `x1 y1 x2 y2` and `r1 r2`

read and evaluate a line

`0j1` imaginary constant i=sqrt(-1)

`0j1⊥` decode from base-i, thus computing: i3x1 \+ i2y1 \+ i1x2 \+ i0y2 = -i x1 \- y1 \+ ix2 \+ y2 = i(x2-x1) + (y2-y1)

`|` magnitude of that complex number, i.e. distance between the two points

`⎕,` read the two radii and prepend them, so we have a list of 3 reals

`(+/∧.≥+⍨)` flat-tolerant triangle inequality: the sum (`+/`) must be greater than or equal to () the double of each side (`+⍨`), and all these results must be true (`∧.`)
> 3 votes

# Answer
# Python 3, ~~56~~ 55 bytes

```
lambda X,Y,x,y,R,r:0<=(X-x)**2+(Y-y)**2-(R-r)**2<=4*r*R

```

Try it online!
> 2 votes

# Answer
# GolfScript, 20 bytes

```
~@- 2?@@- 2?+@@+2?>!

```

Try it online!

Takes arguments in the following form `r1 r2 x1 y1 x2 y2`

Implements the formula below

GolfScript **Does not** inherently support floating point types. See this post for more details about passing floats https://codegolf.stackexchange.com/a/26553

My original intention was to use GolfScript's zip and fold operations.

# GolfScript, 26 bytes

```
1:a;~zip{{a*+2?-1:a;}*}/+>

```

Try it online!
> 2 votes

# Answer
# JavaScript, 52 bytes

```
(X,Y,x,y,R,r)=>4*r*R/((X-x)**2+(Y-y)**2-(R-r)**2)>=1

```

Some how Based on Anders Kaseorg Python solution
> 1 votes

# Answer
# Scala, 59 bytes

**This might be golfable.**

```
val u=(a-x)*(a-x)+(b-y)*(b-y)
(q-r)*(q-r)<=u&u<=(q+r)*(q+r)

```

Try it online!

# Scala, 66 bytes

I do like this one, but sadly the previous was shorter. I hate Scala for forcing defining parameter type...

```
var p=math.pow(_:Double,2)
val u=p(a-x)+p(b-y)
p(q-r)<=u&u<=p(q+r)

```

Try it online!
> 0 votes

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


title: Alice's Tea Party

text:
# Question
Title: Alice's Tea Party
There are *n* places set around a circular table. Alice is sat on one of them. At each place, there's a cake. Alice eats her cake, but it doesn't taste very nice. Then the Mad Hatter comes in. He gives Alice a list of *n*-1 numbers, each between 1 and *n*-1. For each item *i* in the list, Alice has to move around *i* places and eat the cake there if there is one. However, Alice will be able to choose whether to move clockwise or anticlockwise for each item in the list. She doesn't like the cakes, so she is trying not to eat them.

Given an integer *n*, output all the possible lists the Mad Hatter could use to force Alice to eat all the cakes (represented as a tuple/list of tuples/lists of integers or some tuples/lists of integers separated by newlines). Note that it is possible for the Mad Hatter to force Alice to eat all the cakes if and only if *n* is a power of two, so you may assume that *n* is a power of two. Make your code as short as possible.

You may also take in *x* such that 2^*x*=*n* if that helps. For example, you may take in 2 instead of 4, 3 instead of 8, etc.

The order in which your program returns the possible lists does not matter.

### Test Cases

```
1 -> [[]]
2 -> [[1]]
4 -> [[2, 1, 2], [2, 3, 2]]
8 -> [[4, 2, 4, 1, 4, 2, 4], [4, 2, 4, 1, 4, 6, 4], [4, 6, 4, 1, 4, 2, 4], [4, 6, 4, 1, 4, 6, 4], [4, 2, 4, 3, 4, 2, 4], [4, 2, 4, 5, 4, 2, 4], [4, 2, 4, 7, 4, 2, 4], [4, 2, 4, 3, 4, 6, 4], [4, 6, 4, 3, 4, 2, 4], [4, 2, 4, 5, 4, 6, 4], [4, 6, 4, 5, 4, 2, 4], [4, 2, 4, 7, 4, 6, 4], [4, 6, 4, 7, 4, 2, 4], [4, 6, 4, 3, 4, 6, 4], [4, 6, 4, 5, 4, 6, 4], [4, 6, 4, 7, 4, 6, 4]]

```

# Answer
# Python 3, ~~235~~ ~~191~~ ~~177~~ ~~136~~ ~~134~~ ~~122~~ 119 bytes

```
lambda n:[*product(*[[*(i==n/2and range(1,n,2)or[[n/4,3*n/4],[n/2]][i%2])]for i in range(1,n)])]
from itertools import*

```

Try It Online

Thanks To Dennis for -31 bytes and ChasBrown for -14 bytes and Mr.XCoder for -1 byte.

Numbers appear in the decimal form, eg:4.0.
> 2 votes

# Answer
# Perl, ~~78~~ ~~75~~ 72 bytes

Includes `+1` for `n`

```
perl -nE '$"=",";say<@{[map"{@{[map$`*($_-.5)/@z,@z=1..$_&-$_]}}",/$/..$_-1]}\\ >' <<< 8

```

Prints a space separated sequence of comma separated numbers (replace the final space by `\n` for a more readable output)

Uses a string substitution inside a string substitution.
> 2 votes

# Answer
# Jelly, 18 bytes

```
żN$Œp+\€%ṬȦ
’ṗ’çÐf

```

This is a brute-force solution that tests all **(n - 1)n - 1** potential solutions one by one.

Try it online!

### Verification

```
$ time jelly eun 'żN$Œp+\€%ṬȦ¶’ṗ’çÐf' 8
[[4, 2, 4, 1, 4, 2, 4], [4, 2, 4, 1, 4, 6, 4], [4, 2, 4, 3, 4, 2, 4], [4, 2, 4, 3, 4, 6, 4], [4, 2, 4, 5, 4, 2, 4], [4, 2, 4, 5, 4, 6, 4], [4, 2, 4, 7, 4, 2, 4], [4, 2, 4, 7, 4, 6, 4], [4, 6, 4, 1, 4, 2, 4], [4, 6, 4, 1, 4, 6, 4], [4, 6, 4, 3, 4, 2, 4], [4, 6, 4, 3, 4, 6, 4], [4, 6, 4, 5, 4, 2, 4], [4, 6, 4, 5, 4, 6, 4], [4, 6, 4, 7, 4, 2, 4], [4, 6, 4, 7, 4, 6, 4]]

real    85m33.780s
user    85m35.903s
sys     0m0.060s

```

### How it works

```
’ṗ’çÐf       Main link. Argument: n (integer)

’ ’          Yield n-1.
 ṗ           Cartesian power; yield all vector of length n-1 over [1, ..., n-1].
   çÐf       Filter; keep vectors v for which the helper link, called with left
             argument v and right argument n, returns a truthy value.

żN$Œp+\€%ṬȦ  Helper link. Left argument: v (vector). Right argument: n (integer)

żN$          Zip v with -v, mapping [v(1), ... v(n-1)] to
             [[v(1), -v(1)], ..., [v(n-1), -v(n-1)]].
   Œp        Take the Cartesian product of all pairs.
     +\€     Take the cumulative sum of each resulting vector.
        %    Take all cumulative sums modulo n.
             A valid solution results in a permutation of [1, ..., n-1].
         Ṭ   Untruth; map each resulting vector to a Boolean array with 1's at
             the specified indices, 0's elsewhere.
          Ȧ  Test if the resulting array contains only non-zero integers.

```
> 1 votes

# Answer
# Python 2,~~130~~ ~~129~~ ~~127~~ ~~123~~ 121 bytes

```
f=lambda n:n>1and(lambda D:[l+[k]+r for l in D for r in D for k in range(1,n,2)])([[i*2for i in a]for a in f(n/2)])or[[]]

```

Try it online!

Edited: Takes as input n (which must be a power of 2) as the number of seats at the Hatter's table.
> 1 votes

# Answer
# Python 2, 81 bytes

```
f=lambda n,i=1,*l:i/n*[l]or sum([f(n,i+1,x,*l)for x in range(n)if x*i%n==n/2],[])

```

Try it online!

---

# Python 2, 92 bytes

```
f=lambda n,c=1:[x+[c*y]+z for y in range(1,n,2)for x in f(n/2,c*2)for z in f(n/2,c*2)]or[[]]

```

Try it online!
> 1 votes

# Answer
# Clean, ~~194~~ ... 172 bytes

Still in the progress of cutting more off.

```
import StdEnv

```

#

```
\n=let?_[]_=1>0;?l[i:j]m=all((\e= ?(updateAt e(1<0)l)j e&&l!!e)o\e=e-e/n*n)[m+i,n+m-i]in[k\\k<-iter(n-1)(\e=[[h:t]\\h<-[1..n],t<-e])[[]]| ?[q>1\\q<-[1..n]]k 0]

```

Try it online!

Lambda function which does a brute-force over every combination of indices up to length `n-1`.
It still runs in about 5 seconds, because of compiler magic.
> 0 votes

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


title: Help golfing this solution further

text:
# Question
Title: Help golfing this solution further
We are doing a PCG challenge at work, and I'm submitting answers in C#. This is a modification of the "M'Kay" challenge. My solution has been deemed correct by the requirements, I'm just trying to shrink it further if possible.

> A filler word is an apparently meaningless word, phrase, or sound that marks a pause or hesitation in speech.
>
> Your task is to create a function that has a 30%-50% chance of adding a random filler word to a block of text after the punctuation marks , ; . ? and !; and when added is followed by the same punctuation. The same filler word must be used for each replacement within a single execution of the function.
>
> If the filler word occurs after a sentence completing punctuation mark such as . ? or ! the filler word must have the first letter capitalized. If the filler word occurs after a sentence pausing punctuation mark such as , or ; the filler word must be in lowercase.
>
> Fillers: um, literally, you know, er, okay, right, ah, like

My submitted code:

```
string p(string i,int z=-1){string w="Um|Literally|You know|Er|Okay|Right|Ah|Like".Split('|')[i.Length %8],s="?,!;.",o="";foreach(var c in i){var x=s.IndexOf(c);o+=(z>0&&i[z]>'9'&&x>-1&&(1&z)<1?c+" "+(x%2>0?" "+w.ToLower():w):"")+c;z++;}return o;}

```

> **Original input text:** We heard tales of Americans like Coast Guard Petty Officer Ashlee Leppert, who is here tonight in the gallery with Melania. Ashlee was aboard one of the first helicopters on the scene in Houston during Hurricane Harvey. Through 18 hours of wind and rain, Ashlee braved live power lines and deep water, to help save more than 40 lives. Thank you, Ashlee.
>
> **With fillers added:** We heard tales of Americans like Coast Guard Petty Officer Ashlee Leppert, *okay*, who is here tonight in the gallery with Melania. Ashlee was aboard one of the first helicopters on the scene in Houston during Hurricane Harvey. *Okay*. Through 18 hours of wind and rain, Ashlee braved live power lines and deep water, *okay*, to help save more than 40 lives. Thank you, Ashlee.

Clarification comments welcome, I don't know what else I need to include.

# Answer
> 6 votes
> ```
> string ... s="?,!;." ... var x=s.IndexOf(c);
>
> ```

`s` is used only once, so could be inlined.

---

> ```
> var x=s.IndexOf(c); ... &&x>-1&& ... c+" "+(x%2>0?" "+w.ToLower():w):"")+c;
>
> ```

Change `"?,!;."` to `",;?!."` and the test `x%2>0` can be simplified to `x<2`.

Where in the spec does it require double-space after sentence-terminating punctuation? IMO you could lose the `" "+` inside the parentheses.

---

Given the IMO ridiculous interpretation which they're allowing of "*random*", I don't see why you do such complicated stuff with `z`. Just use the character index modulo 3. A direct change to

```
string p(string i){int n=i.Length,j,x;string w="Um|Literally|You know|Er|Okay|Right|Ah|Like".Split('|')[n%8],o="";for(j=0;j<n;j++){var c=i[j];x=",;.?!".IndexOf(c);o+=(x>-1&&j%3<1?c+" "+(x<2?" "+w.ToLower():w):"")+c;}return o;}

```

gives a further nice saving. An alternative using Linq also saves a lot by exploiting fat arrow syntax, and would be cheaper if they give you free `using` statements:

```
using System.Linq;string p(string s)=>string.Join("",s.Select((c,i)=>{var w="Um|Literally|You know|Er|Okay|Right|Ah|Like".Split('|')[s.Length%8];var x=",;.?!".IndexOf(c);return(x>=0&&i%3<1?c+" "+(x<2?" "+w.ToLower():w):"")+c;}));

```

---
Tags: code-golf, tips, c#
---


title: Create an omnifix calculator

text:
# Question
Title: Create an omnifix calculator
Inspiration. Inverse.

Evaluate a given omnifix expression.

Omnifix is like normal mathematics' infix notation, but with additional copies of each symbol surrounding the arguments. The outer symbols take the place of parentheses, and there is therefore no need for additional parentheses.

You must support addition, subtraction, multiplication, division, and positive real numbers (negative ones can be written `-0-n-`) within a reasonable range for your language.

Plus and minus must be `+` and `-`, but you may use `*` or `×` for times and `/` or `÷` for divide. Other reasonable symbols will be allowed upon request.

Brownie points for explanation and additional features (like additional operations, negative numbers, strings, etc.) Even if your answer does not have these features, feel free to show how it could.

Please provide a link to test your solution if at all possible.

### Examples

For clarity, the explanations below use high minus (`¯`) to indicate negative numbers. You may return negative numbers using any reasonable format.

`-5-2-``3`

`+2+×3×2×+``8` (`+2+×3×2×+``+2+6+``8`)

`-14--3-1--``12` (`-4--3-1--``-14-2-``12`)

`+2.1+×3.5×2.2×+``9.8` (`+2.1+×3.5×2.2×+``+2.1+7.7+``9.8`)

`×3×÷-0-6-÷2÷×``-9` (`×3×÷-0-6-÷2÷×``×3×÷¯6÷2÷×``×3×¯3×``¯9`)

`÷4÷-3-÷1÷2÷-÷``1.6` (`÷4÷-3-÷1÷2÷-÷``÷4÷-3-0.5-÷``÷4÷2.5÷``1.6`)

# Answer
> 4 votes
# Python 3, ~~159~~ ~~158~~ ~~152~~ ~~144~~ ~~136~~ ~~135~~ 132 bytes

```
def t(i,a=1):
 while'-'<l[i]!='/':i+=1;a=0
 if a:l[i]='(';i=t(t(i+1));l[i-1]=')'
 return-~i
*l,=input()
t(0)
print(eval(''.join(l)))

```

Try it online!

Doesn't allow negative numbers (though `-0-5-` works of course) and requires python operators.

# Answer
> 4 votes
# C# (.NET Core), 198 197 188 bytes

```
float O(string s){try{return float.Parse(s);}catch{var f=s[0];int i=s.IndexOf(f,1);float a=O(s.Substring(1,i-1)),b=O(s.Substring(i+1,s.Length-i-2));return f<43?a*b:f<44?a+b:f<46?a-b:a/b;}}

```

Try it online!

Uses `*` and `/`.

A recursive function. It first tries to parse the input string as a `float`. If it fails, it calls itself recursively passing as arguments the first and second operands and then performs the selected operation on the results.

* 1 byte saved thanks to Mr. Xcoder!
* 9 bytes saved thanks to TheLethalCoder!

# Answer
> 3 votes
# Retina, ~~290~~ ~~287~~ 286 bytes

```
\d+
¦$&$*
¯¦
¯
{`\+([¯¦]1*)\+([¯¦]1*)\+
-$1-¯$2-
-(¯|¦)(1*)-([¯¦]+1*\2)-
-¯$3-¯$1$2-
(×|÷)¯(1*\1)([¯¦]1*\1)
$1¦$2¯$3
×¦×[¯¦]1*×|¯¯¦?
¦
¯¦|¦¯
¯
+`-((¯|¦)1*)(1*)-\2\3-
$1
-([¯¦]1*)-[¯¦](1*)-
$1$2
×¦1(1*)×([¯¦]1*)×
+×¦$1×$2×+$2+
}`÷¦(?=1*÷(¯|¦)(1+)÷)(\2)*1*÷\1\2÷
$1$#3$*
((¯)|¦)(1*)
$2$.3

```

Try it online! Note: Only capable of integer arithmetic, so some of the test cases have been removed. Accepts and returns negative numbers using the `¯` prefix. Edit: Saved ~~3~~ 4 bytes thanks to @Cowsquack. Explanation:

```
\d+
¦$&$*

```

I needed some way of handling zero, so I use `¦` as a positive number prefix. The numbers are then converted to unary.

```
¯¦
¯

```

But negative numbers only need a `¯` prefix.

```
{`\+([¯¦]1*)\+([¯¦]1*)\+
-$1-¯$2-

```

Quoting `+`s gets ugly, so I turn additions into subtractions.

```
-(¯|¦)(1*)-([¯¦]+1*\2)-
-¯$3-¯$1$2-

```

If the absolute value of the LHS of a subtraction is less than the RHS, switch them around and negate both sides.

```
(×|÷)¯(1*\1)([¯¦]1*\1)
$1¦$2¯$3

```

Also if the LHS of a multiplication or division is negative, negate both sides.

```
×¦×[¯¦]1*×|¯¯¦?
¦

```

Also if the LHS of a multiplication is zero, then the result is zero. Also, two minuses make a plus.

```
¯¦|¦¯
¯

```

But a minus and a plus (or vice versa) make a minus.

```
+`-((¯|¦)1*)(1*)-\2\3-
$1

```

Subtract two numbers of the same sign. Do this repeatedly until there are no such subtractions left.

```
-([¯¦]1*)-[¯¦](1*)-
$1$2

```

If there's still a subtraction, the signs must be different, so add the numbers together. (But only do this once, since this may reveal a subtraction of two numbers of the same sign again.)

```
×¦1(1*)×([¯¦]1*)×
+×¦$1×$2×+$2+

```

Perform multiplication by repeated addition.

```
}`÷¦(?=1*÷(¯|¦)(1+)÷)(\2)*1*÷\1\2÷
$1$#3$*

```

Perform integer division. One of the above steps will have simplified the expression, so loop back until there are no operations left.

```
((¯)|¦)(1*)
$2$.3

```

Convert back to decimal.

# Answer
> 2 votes
# PHP, ~~116~~ ~~114~~ 109 bytes

*-5 thanks to Martin Ender*

```
for($s=$argv[$o=1];$o!=$s;)$s=preg_replace('#([*+/-])(([\d.]+|(?R))\1(?3))\1#','($2)',$o=$s);eval("echo$s;");

```

Uses `*` for multiplication and `/` for division. Negative numbers happen to work despite me making no specific attempts for that to be the case.

Try it online!

### Ungolfed and Explained

```
for($s=$argv[$o=1];   # Initialize with $s = input and $o = 1;
    $o!=$s;)          # While $o != $s
    # Set $o to $s and set $s to be $s after this regex replacement:
    $s=preg_replace('#([*+/-])(([\d.]+|(?R))\1(?3))\1#','($2)',$o=$s);
    # i.e., continue to do this replacement until the result is the same on two consecutive
    # steps (no replacement was made)
# Once $o == $s (i.e. no more replacement can be made), eval the result and print
eval("echo$s;");

```

I'll also explain the regex because it's a bit magical:

```
([*+/-])(([\d.]+|(?R))\1(?3))\1

```

```
([*+/-])

```

First, we want to match any of the four operators: `*+/-`

```
([\d.]+|(?R))

```

Then, we need to match either a number `[\d.]+` or another valid omnifix expression `(?R)`.

```
\1

```

Then, we match the same operator that was at the beginning.

```
(?3)

```

Then we do the same thing we did in group 3: match a number or an omnifix expression.

```
\1

```

Finally, match the initial operator again.

Whatever matches this is replaced with `($2)`. This takes the part inside the surrounding operators and puts it inside brackets, so it looks like normal infix notation.

# Answer
> 2 votes
# QuadR, ~~33~~ ~~32~~ 27 bytes

-1 thanks to Cows Quack. -5 thanks to Erik the Outgolfer.

```
((.)[\d¯\.]+){2}\2
⍎¯1↓1↓⍵M

```

with the argument/flag

Try it online!

This is equivalent to the 40-byte Dyalog APL solution:

```
'((.)[\d¯\.]+){2}\2'⎕R{⍕⍎1↓¯1↓⍵.Match}⍣≡

```

Try it online!

### Explanation

(parenthesised text refers to Dyalog APL instead of QuadR)

`(``){2}\2` the following pattern twice, and the whole match twice too:
`(.)` any character
`[``]+` followed by one or more of the following set of characters:
`\d`**d**igits,
`¯` high minus (negative sign)
`\.` period

(`⎕R` is **R**eplaced with:)

(`{``}` the result of the following anonymous function applied to the namespace ⍵:)

`⍵M` (`⍵.Match`) the text of the **M**atch
`¯1↓` drop the last character (the symbol `+` `-` `×` or `÷`)
`1↓` drop the first character (symbol)
execute as APL code
( stringify)

(`⍣≡`) repeat the replacement until no more changes happen

# Answer
> 1 votes
# Haskell, 132 chars

(134 bytes, because `×` and `÷` take two bytes in UTF-8)

```
f y|(n@(_:_),r)<-span(`elem`['.'..'9'])y=(read n,r)
f(c:d)|(l,_:s)<-f d,(m,_:r)<-f s=(o[c]l m,r)
o"+"=(+)
o"-"=(-)
o"×"=(*)
o"÷"=(/)

```

Try it online!

`f` parses as much of the input as it can and yields the result as well as the remaining string (which is empty in the test cases). If that's not rule-conformant, strip the unparseable remainder string with

# Haskell, 139 chars

```
...
g=fst.f

```

# Answer
> 0 votes
# Perl, ~~64~~ 53 bytes

Include `+1` for `-p`

```
perl -pe 's%([*-/])(([\d.]+|(?0))\1(?3))\1%($2)%&&redo;$_=eval' <<< "/4/-3-/1/2/-/"

```

Accidentally also implements `,` (throws away the first argument) and sometimes `.` (append the arguments together). `.` doesn't work very reliable though since it interferes with decimal point both at the parsing level and at the evaluation level

# Answer
> 0 votes
# Java 8, ~~205~~ 200 bytes

```
float O(String s){try{return new Float(s);}catch(Exception e){int f=s.charAt(0),i=s.indexOf(f,1);float a=O(s.substring(1,i)),b=O(s.substring(i+1,s.length()-1));return f<43?a*b:f<44?a+b:f<46?a-b:a/b;}}

```

Port of *@Charlie*'s C# answer.
-5 bytes thanks to *@ceilingcat*.

Try it online.

---
Tags: code-golf, math, arithmetic, repeated-transformation
---


title: Telegraphy Golf: Decode Baudot Code

text:
# Question
Title: Telegraphy Golf: Decode Baudot Code
# Background

In 1870 Émile Baudot invented Baudot Code, a fixed-length character encoding for telegraphy. He designed the code to be entered from a manual keyboard with just five keys; two operated with the left hand and three with the right:

The right index, middle and ring fingers operate the *I*, *II*, and *III* keys, respectively, and the left index and middle fingers operate *IV* and . (Henceforth I'll use the more familiar numerals 1–5.) Characters are entered as chords. To enter the letter "C," for example, the operator presses the *1*, *3*, and *4* keys simultaneously, whereupon a rotating brush arm reads each key in sequence and transmits a current or, for keys not depressed, no current. In modern terms, this is a 5-bit least-significant-bit-first binary encoding, in which our example, "C," is encoded as `10110`.

## 5 bits??

You might be thinking that 5 bits, which can express at most 32 unique symbols, isn't enough for even all of the English letters and numerals, to say nothing of punctuation. Baudot had a trick up his sleeve, though: His character set is actually *two* distinct sets: *Letters* and *Figures*, and he defined two special codes to switch between them. *Letter Shift* (LS), which switches to Letters mode, is activated by pressing the *5* key alone (`00001`), and *Figure Shift* (FS) is activated with the *4* key (`00010`).

# Challenge

Your challenge is to write a program or function that decodes Baudot Code transmissions.

A real transmission would begin with some initialization bits, plus a start and stop bit before and after each character, but we're going to skip those and only worry about the 5 unique bits for each character. Input and output formats are discussed below.

## Baudot's Code

There are two different versions of Baudot Code: Continental and U.K. We're going use the U.K. version, which *doesn't* include characters like "É" from Baudot's native French. We're also going to leave out all of the symbols in the U.K. version that aren't among the printable ASCII characters. You will only have to decode the characters in the table below, all of which are printable ASCII characters except the final three control characters that are explained below the table.

The "Ltr" column shows the characters in Letter mode and "Fig" shows the Figure mode characters:

```
        Encoding             Encoding
Ltr Fig  12345       Ltr Fig  12345
--- --- --------     --- --- --------
 A   1   10000        P   +   11111
 B   8   00110        Q   /   10111
 C   9   10110        R   -   00111
 D   0   11110        S       00101
 E   2   01000        T       10101
 F       01110        U   4   10100
 G   7   01010        V   '   11101
 H       11010        W   ?   01101
 I       01100        X       01001
 J   6   10010        Y   3   00100
 K   (   10011        Z   :   11001
 L   =   11011        -   .   10001
 M   )   01011        ER  ER  00011
 N       01111        FS  SP  00010
 O   5   11100        SP  LS  00001
 /       11000

```

The last three rows in the right column are control characters:

* **`ER`** is *Erasure*. Baudot's telegraphy machines would print an asterisk-like symbol for this character to tell the reader that the preceding character should be ignored, but we're going to be even nicer to the reader and *actually omit (do not print) the preceding character*. It acts the same in both Letter and Figure mode.
* **`FS`** is *Figure Shift*. This switches the character set from Letters to Figures. If the decoder is *already* in Figure mode, FS is treated as a *Space* (ergo `SP` in the "Ltr" column). When the decoder is in Figure mode it stays in Figure mode until an LS character is received.
* **`LS`** is *Letter Shift*. It switches the character set from Figures to Letters. If the decoder is already in Letter mode, LS is treated as a *Space*. When in Letter mode the decoder stays in Letter mode until an FS character is received.

The decoder always starts in Letter mode.

Here's an example with Figure Shift, Letter Shift, and Space:

```
01011 10000 00100 00001 00010 10000 11100 00001 10101 11010
  M     A     Y   LS/SP FS/SP   1     5   LS/SP   T     H

```

This yields the message `MAY 15TH`. As you can see, the first `00001` (Letter Shift/Space) character acts as a space, because the decoder is already in Letter mode. The next character, `00010` (Figure Shift/Space) switches the decoder to Figure mode to print `15`. Then `00001` appears again, but this time it acts as Letter Shift to put the decoder back in Letter mode.

For your convenience, here are the characters in a format that's perhaps easier to digest in an editor, sorted by code:

```
A,1,10000|E,2,01000|/,,11000|Y,3,00100|U,4,10100|I,,01100|O,5,11100|FS,SP,00010|J,6,10010|G,7,01010|H,,11010|B,8,00110|C,9,10110|F,,01110|D,0,11110|SP,LS,00001|-,.,10001|X,,01001|Z,:,11001|S,,00101|T,,10101|W,?,01101|V,',11101|ER,ER,00011|K,(,10011|M,),01011|L,=,11011|R,-,00111|Q,/,10111|N,,01111|P,+,11111

```

## Input

Input will be a string, array, or list of bits in least-significant-bit-first order. Each character will be represented by a quintet of 5 bits. Bits may be in any reasonable format, e.g. a binary string, an array of `0`s and `1`s, a string of `"0"` and `"1"` characters, a single very large number, etc., as long as it maps directly to the bits of the transmission.

Every transmission will have at least one printable quintet and at most 255 quintets (printable or otherwise), i.e. 5–1,275 bits inclusive.

The input can contain *only* the bits of the transmission, with two allowed exceptions: Any number of leading or trailing `0` bits and/or, for string input, a single trailing newline may be added to the transmission. Leading or trailing bits or characters *cannot* be added before or after each quintet, i.e. you cannot pad each quintet to 8 bits (or take each quintet as a single number in an array—unless your language has a 5-bit integer type) or separate quintets with any additional bits, e.g. `"01111\n11100"`.

### Notes & edge cases

1. The transmission will contain only the characters in the "Ltr" and "Fig" columns in the table above. You will never receive e.g. `01110` in Figure mode, because it is absent from the "Fig" column.
2. It is assumed that the decoder will always be in Letter mode at the beginning of a transmission. However, the first character *may* be an FS character to switch to Figure mode immediately.
3. When the decoder is in Letter mode, it may receive an LS character, and when it is in Figure mode it may receive an FS character. In either event a Space character must be printed (see Output).
4. The ER character will never be the first character in a transmission, nor will it ever immediately follow an LS, FS, or another ER.
5. An FS character may immediately follow an LS character and vice versa.
6. Neither the LS nor FS character will be the last character in any transmission.
7. The `/` and `-` characters may be received in either Letter mode (codes `11000` and `10001`, respectively) or Figure mode (`10111` and `00111`).

## Output

Output may be in any reasonable format, the most reasonable being ASCII (or UTF-8, for which all of the represented characters are the same as ASCII). Please indicate in your answer if your output is in another encoding or format.

### Notes

* The space character (see 3. above) should be an ASCII space (0x20) or your encoding's equivalent, i.e. what you get when you press the space bar.

# Winning

This is . The shortest code in bytes wins.

# Restrictions

* Standard loopholes are forbidden.
* Trailing spaces and/or a single trailing newline are allowed. Leading spaces or other characters (that are not part of the transmission) are disallowed.
* You may not use any built-in or library functions that decode Baudot Code (or any of its descendants, e.g. Murray Code, ITA-1, etc.).

# Test Cases

```
Input: 001101000010100111101110010101
Output: BAUDOT

```

```
Input: 11010010001001100011110111101111100
Output: HELLO

```

```
Input: 01011100000010000001000101000011100000011010111010
Output: MAY 15TH

```

```
Input: 0001000100010000001000001011101110011100101010010110101010001111100101
Output: 32 FOOTSTEPS

```

```
Input: 10110000110101011100111100001111011010000001101110
Output: GOLF

```

```
Input: 000100011000001111100000100010110111001100010110010000111111
Output: 8D =( :P

```

```
Input: 0000100001000010000100010001111011111011000011100010001
Output (4 leading spaces):     -/=/-

```

# Answer
# Pyth, ~~98~~ ~~97~~ ~~95~~ ~~93~~ ~~90~~ ~~83~~ 80 bytes

The code contains unprintable characters, so here is a reversible `xxd` hexdump:

```
00000000: 753f 7133 4a69 4832 5047 2b47 3f3c 334a  u?q3JiH2PG+G?<3J
00000010: 4040 6332 2e22 275a 75ae 5751 fb4e 3cd7  @@c2."'Zu.WQ.N<.
00000020: 02ce 8719 aac1 e0e0 fe1f 09e5 85bc a767  ...............g
00000030: 8e0c 1f47 508a cad1 1acb b26f 951e e5d6  ...GP......o....
00000040: 225a 4a2a 5c20 715a 3d5a 744a 637a 356b  "ZJ*\ qZ=ZtJcz5k

```

Try it online. Test suite.

Quite long, but the lookup table does take up ~~most~~ half of the space.

For 117 bytes, here's the same thing without unprintables (needs ISO-8859-1, though):

```
u?q3JiH2PG+G?<3J@@c2."'Zu®WQûN<×\x02Î\x87\x19ªÁààþ\x1f\tå\x85¼§g\x8e\x0c\x1fGP\x8aÊÑ\x1aË²o\x95\x1eåÖ"ZJ*\ qZ=ZtJcz5k

```

Or, for 93 bytes, with no compression on the lookup table:

```
u?q3JiH2PG+G?<3J@@c2"OVDPYSBREXGMIWFNA-JKUTCQ/ZHL5'0+3;8-2;7);?;;1.6(4;9/;:;="ZJ*\ qZ=ZtJcz5k

```
> 7 votes

# Answer
# JavaScript (ES6),  ~~160 158 153~~  149 bytes

```
s=>s.replace(m=/.{5}/g,s=>["? !YSBREXGMIWFNA-JKUTCQ/ZHLOVDP? ?!3 8-2 7) ?  1.6(4 9/ : =5'0+"[(n='0b'+s-1)<2?m^n?~(m^=1):1:m<<5|n]]).replace(/.!/g,'')

```

Try it online!
> 6 votes

# Answer
# Chip, 1069 bytes

It's a big'n, but was quite fun to write.

Takes input as a string of `"1"`'s and `"0"`'s. (Though it really only looks at the low bit.)

```
 AZZZZ,-o.AZZZZ  AZZZZ,o-.AZZZZ
*\\\\\]oo[\/\\\**//\\\]oo[/\\\\*
*\\\\/]oo[\/\\/**//\\/]oo[/\\\/*
*\\\//]oo[\/\//**//\//]oo[/\\//*
*\\\/\]oo[\/\/\**//\/\]oo[/\\/\*
*\\//\]oo[\///\**////\]oo[/\//\*
*\\///]oo[\////**/////]oo[/\///*
*\\/\/]oo[\//\/**///\/]oo[/\/\/*
*\\/\\]oo[\//\\**///\\]oo[/\/\\*
=
        o--------K-----o
      ,oo.   z---+~S  ,oo.
     ,LooR. !ZZZZ'   ,LooR.
    ,LLooRR.        ,LLooRR.
   ,LLLooRRR.      ,LLLooRRR.
  ,LLLLooRRRR.    ,LLLLooRRRR.
 ,LLLLLooRRRRR.  ,LLLLLooRRRRR. ,~Z
,LLLLLLooRRRRRR.,LLLLLLooRRRRRR.>m'
|||||||oo||||||||||||||oo||||||)/Rz.
xxxxxxxxxxxxxxx)xxxxxxxxxxxxxxxx\^-^S
x)x))))))))))))xx)))))))))))))xx\g
xx)xxxxxxxxxxxxxxxxxxxxxxxxxxx))\f
xxxxxx))xxxxxxxxxxxxx)))))))))xx\e
xx)x))x)xxxxx))x)))))xxxxxxx)))x\d
xx))x))xxx)))xxxxx)))xxxx)))xx)x\c
xx)xx)xx))x))x)xx)xx)xx))x))x)xx\b
x)))))))x)xx)xxxx)x)xx)x)xx)xx)x\a
x)x)x))))))x)x))x)))x)))xx))x))x/f
x)x)x))))))x)x)xxx)xxxxxxxx)x)xx/e
xxxxxxxx))xxxxxx))))x)))xxx)x))x/d
xxxxx))xxxxx)x)xxx)xxx))xx))xx)x/c
xxx)xxx)xxxx)x)xxxxxx))xxx))x))x/b
x)xxx)x)x)xx)xxxxx))x)))xx))xxxx/a

```

Try it online!

Note: Erasure uses the ASCII backspace character (`\x08`), which means that they'll look funny in TIO, but they look fine in, say, xterm.

### Basic Structure

At the top, above the `=` line, is the input decoder. It turns the input into one of 32 separate signals. These are sent from the `o`'s above the `=` to those below.

The triangular mountains of `L`'s and `R`'s just rotate the pattern from separate rows to columns. The grid below that translates each column to its output character. For unknown signals, NUL (`\x00`) is produced. For the special shifts, instead of printing a character, the little blob to the right changes the mode.

The cable-car like thing between the two mountains suppresses any printing between each quintet, otherwise, this would attempt to decode all overlapping quintets too. Try replacing the `!` with a `*` to see this for yourself. (Running in verbose mode `-v` may also be of interest here.)

I'm not sure how to make this smaller at the moment; it's already quite dense for its size.
> 6 votes

# Answer
## Batch, ~~306~~ 304 bytes

```
@echo off
set/pc=
set r=
set d=! !!YSBREXGMIWFNA-JKUTCQ/ZHLOVDP!! !3!8-2!7)!?!!1.6(4!9/!:!=5'0+
set s=2
:l
set/an=(s^&32)+0%c:~,2%%%6*8+0x%c:~2,3%%%14
set c=%c:~5%
if %n%==%s% set/as^^=35&goto l
call set r=%%r%%%%d:~%n%,1%%
if %r:~-1%==! set r=%r:~,-2%&goto l
if not "%c%"=="" goto l
echo %r%

```

Takes input on STDIN. Since Batch has no binary conversion, I have to fake it using octal and hex conversion.

* The first two digits are converted from octal (I can't use decimal because the first digit might be `0`). Possible values are `00`, `01`, `10` and `11`. The latter two have value `8` and `9` but I want `2` or `3` so I take the remainder modulo `6`.
* The last three digits are converted from hexadecimal. Digits are either `14` or `252` times their desired value, to I take the remainder modulo `14` (`252=14*18`).
* `c` is the coded string
* `r` is the result so far
* `d` is the decoding array
* `s` is the the index (taking the shift state into account) of the character that switches shift state
* `n` is the binary decode plus bit 5 of `s`, which either equals the shift state, in which case the shift state is toggled, or indexes into the decoding array to find the next character (or ! to erase)
> 5 votes

# Answer
# PHP, 206 Bytes

```
foreach(str_split($argv[1],5)as$s)($k="# f*YSBREXGMIWFNA-JKUTCQ/ZHLOVDP#l *3#8-2#7)#?##1.6(4#9/#:#=5'0+"[32*$f+bindec($s)])=="*"?array_pop($a):($k=="f"?$f=1:($k=="l"?$f=0:($k=="#"?:$a[]=$k)));echo join($a);

```
> 3 votes

# Answer
# GNU sed, 334 + 1 = 335 bytes

+1 byte for `-r` flag. Takes input on STDIN.

Looking over old challenges I realized this one would be pretty easy with sed, and good for practice. I haven't attempted any compression, so the lookup table is more than half the code.

```
s|.*|#@&;01000E211000/%00100Y310100U401100I%11100O500010f 10010J601010G711010H%00110B810110C901110F%00001 l10001-.01001X%11001Z:00101S%10101T%01101W?11101V'00011<<10011K(01011M)11011L=00111R-10111Q/01111N%11111P+10000A111110D0|
:
s/@([01]{5})(.*;.*\1)(..)/\3@\2\3/
t
s/@;.*//
s/#f /@/
s/@ l/#/
s/#(.)./\1#/
s/@.(.)/\1@/
t
s/.<|[#@]//g

```

Try it online!

## Explanation

The code works in two phases: First, it replaces each run of 5 binary digits with the corresponding two characters (letter and figure) from a lookup table. The lookup table is in the format … where is a binary digit and and are the corresponding letter and figure, respectively. `%` stands in for missing characters (this could be any character other than newline). `FS/SP` is represented by `f<space>` and `SP/LS` is `<space>l`. `ER` is represented by `<<`.

Then it steps through each pair with a "cursor" corresponding to the current mode—`#` for letter mode, `@` for figure mode. The `#` cursor removes the second character of the pair and then advances to the next pair, and the `@` removes the first and advances. In other words, `#A1B8` becomes `A#B8` and then `AB#`, and `@A1B8` becomes `1@B8` and then `18@`. When the `#` cursor encounters `f<space>` it deletes it and replaces itself with the `@` cursor, and vice versa when `@` encounters `<space>l`.

When no pairs remain, the final cursor is removed along with any characters followed by `<`.

```
# Setup: Append a lookup table to the line.
# Also prepends "#" and "@" which we'll use as "cursors" later.
s|.*|#@&;01000E211000/%00100Y310100U401100I%11100O500010f 10010J601010G711010H%00110B810110C901110F%00001 l10001-.01001X%11001Z:00101S%10101T%01101W?11101V'00011<<10011K(01011M)11011L=00111R-10111Q/01111N%11111P+10000A111110D0|

# Phase 1
:
  # Using "@" as a "cursor", substitute for each run of 5 binary digits the
  # two corresponding characters from the lookup table.
  s/@([01]{5})(.*;.*\1)(..)/\3@\2\3/
  t   # Loop (branch to `:`) as long as substitutions are made.

s/@;.*//       # Delete the "@" and lookup table

# Phase 2
s/#f /@/       # FS (f ) in letter mode (#); delete and switch to figure mode (@ cursor).
s/@ l/#/       # LS ( l) in figure mode (@); delete and switch to letter mode (# cursor).
s/#(.)./\1#/   # Letter mode; replace pair with first of pair; advance cursor.
s/@.(.)/\1@/   # Figure mode; replace pair with second of pair; advance cursor.
t              # If any substitutions were made, branch (loop) to `:`.

# Teardown
s/.<|[#@]//g   # Delete characters followed by < (ER) and cursor.

```
> 0 votes

---
Tags: code-golf, binary, encoding
---


title: Fibonacci-style matrix expansion

text:
# Question
Title: Fibonacci-style matrix expansion
For each row and then column of a matrix, we can add an extra entry with the sum of the last two entries in that row or column. For example with the following input matrix:

```
[ 1 1 1 ]
[ 2 3 4 ]

```

The resulting matrix would be:

```
[ 1 1 1 2 ]
[ 2 3 4 7 ]
[ 3 4 5 9 ]

```

Given an input of an integer N and an \[X,Y\] matrix of size at least 2x2, perform the above expansion N times and output the result. The resulting matrix will always be of size \[X+N,Y+N\].

### Examples:

```
Input:                     Output:

2, [ 0 0 ]                 [ 0 0 0 0 ]
   [ 0 0 ]                 [ 0 0 0 0 ]
                           [ 0 0 0 0 ]
                           [ 0 0 0 0 ]

3, [ 1 1 1 ]               [ 1  1  1  2  3  5 ]
   [ 2 3 4 ]               [ 2  3  4  7 11 18 ]
                           [ 3  4  5  9 14 23 ]
                           [ 5  7  9 16 25 41 ]
                           [ 8 11 14 25 39 64 ]

```

# Answer
> 8 votes
# MATL, 13 ~~14~~ ~~15~~ ~~16~~ ~~20~~ ~~21~~ bytes

```
2*:"!tP2:Y)sv

```

Thanks @Zgarb for removing 1 byte!

**Try it online!**

```
2*         % implicitly input number N and multiply by 2
:          % create vector [1,2,...,2*N]
"          % for loop: do this 2*N times
  !        %   transpose. Implicitly input matrix in the first iteration
  tP       %   duplicate and flip vertically
  2:       %   vector [1,2]
  Y)       %   pick submatrix formed by the first two rows
  s        %   sum of each column
  v        %   append as a new row
           % end for
           % implicit display

```

# Answer
> 6 votes
## J, 19 bytes

```
(v"1@v=.,[+&{:}:)^:

```

This defines an adverb, which takes the number on its left, and produces a verb taking the matrix on its right. For the second example, it gives

```
  3 ((v"1@v=.,[+&{:}:)^:) 2 3 $ 1 1 1 2 3 4
1  1  1  2  3  5
2  3  4  7 11 18
3  4  5  9 14 23
5  7  9 16 25 41
8 11 14 25 39 64

```

## Explanation

```
(v"1@v=.,[+&{:}:)^:  Left argument x, right argument y
(               )^:  Repeat x times:
     v=.               Bind the following verb to v, and apply to y:
         [    }:         y and y-without-last-item
          +&{:           Sum of their last items
        ,                Append that to y
                       (v automatically threads to rows)
 v"1@                  then apply v to columns

```

# Answer
> 3 votes
# K, 23 bytes

```
{x(2({x,+/-2#x}'+)/)/y}

```

In action:

```
  {x(2({x,+/-2#x}'+)/)/y}[3;(1 1 1;2 3 4)]
(1 1 1 2 3 5
 2 3 4 7 11 18
 3 4 5 9 14 23
 5 7 9 16 25 41
 8 11 14 25 39 64)

```

Try it here.

# Answer
> 3 votes
# Jelly, ~~15~~ ~~13~~ 12 bytes

*-1 byte by @Dennis*

```
ṫ-S;@"Z
ÇḤ}¡

```

Like @LuisMendo's MATL answer, this transposes the array before doing the transformation along one axis. Therefore, we need to call the function 2\*n times.

```
ṫ-S;@"Z       Helper link. Input: x (2D array)
 -              Numeric literal: -1
ṫ               Get x[-1:], i.e. last two rows in x
  S             Sum
   ;@"          Append each to x. " is 'zipWith'; @ switches argument order.
      Z         Transpose the array.
ÇḤ}¡          Main link. Input: a, n
Ç               Call the last link on a
 Ḥ}             2n
   ¡            times.

```

Try it here.

# Answer
> 2 votes
## ES6, 134 bytes

```
(n,a)=>[...a.map(b=>[...b,...Array(n)].map(c=>(c<1/0?0:c=a+d,d=a,a=c))),...Array(n)].map(b=>(b?0:b=[...a].map((c,j)=>c+d[j]),d=a,a=b))

```

Explanation:

```
(n,a)=> // arguments n is number to expand, a is original array
    [...
        a.map(b=> // for each row in a
            [...b,...Array(n)] // append n elements to the row
            .map(c=>(c<1/0?0:c=a+d,d=a,a=c))) // scan the elements and fill the new ones by summing the previous two
        ,...Array(n)] // append n rows
    .map(b=>(b?0:b=[...a].map((c,j)=>c+d[j]),d=a,a=b)) // scan the rows and fill the new rows by summing the previous two rows

```

# Answer
> 2 votes
## CJam, ~~17~~ 16 bytes

```
q~2*{~_2$.+]z}*p

```

Input format is the matrix first (as a CJam-style 2D array) and the number of iterations afterwards.

Test it here.

### Explanation

Turns out this is the same solution as everyone else's:

```
q~      e# Read and evaluate input.
2*      e# Double the iteration count.
{       e# Run this block that many times...
  ~     e#   Dump all rows on the stack.
  _     e#   Copy the last row.
  2$    e#   Copy the penultimate row.
  .+    e#   Vectorised addition.
  ]     e#   Wrap all rows in a new array.
  z     e#   Transpose such that the next iteration processes the other dimension.
}*
p       e#   Pretty-print.

```

# Answer
> 2 votes
## Haskell, 67 bytes

```
o%m=m++[o(+)(last m)$last$init m]
(!!).iterate(map(id%).(zipWith%))

```

Usage example:

```
*Main> ( (!!).iterate(map(id%).(zipWith%)) ) [[1,1,1],[2,3,4]] 3
[[1,1,1,2,3,5],[2,3,4,7,11,18],[3,4,5,9,14,23],[5,7,9,16,25,41],[8,11,14,25,39,64]]

```

How it works:

```
(!!).iterate(    ...         )  -- repeatedly apply ... to the first agrument and
                                -- pick the iteration defined by the second arg
                   (zipWith%)   -- for one iteration add a new row and
          map(id%)              -- then a new element at the end of each each row

o%m                             -- add row or element at the end of a row resp.
                                -- argument o is a "modify function"
                                --          m the whole matrix or a row
 m++[    (last m)(last$init m)] -- take m and append the result of combining the
                                -- last and 2nd last element of m
     o(+)                       -- with a modified version of (+)
                                -- modification is none (aka. id) when adding an
                                -- element to the end of a row and
                                -- zipping elementwise (zipWith) when adding a row

```

# Answer
> 1 votes
## Seriously, 20 bytes

```
,,τ"┬`;d@d@X+@q`M"£n

```

Takes input the matrix (as a 2D list), then `N`. Outputs a 2D list.

This version doesn't work on the online interpreter for some reason, but does work with this pre-challenge commit.

A version that works online, for 23 bytes:

```
,τ",┬`;d@d@X+@q`M"nkΣ£ƒ

```

Takes input in the opposite order (`N`, then matrix).

Try it online!

I will add an explanation after I sleep for a little while. Working around interpreter bugs is never fun.

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

```
u+Rs>2dCGyEQ

```

Try it online. Test suite.

Uses the same algorithm to most answers. Takes as input the matrix as a 2D array on the first line and `n` on the second line.

### Explanation

```
u        yEQ     do 2*N times, starting with input matrix:
       CG          transpose
 +R                append to each row:
   s                 sum of
    >2d              last 2 elements of row

```

# Answer
> 1 votes
# Matlab, 60 bytes

I was first messing about with Matlab's fancy indexing methods (i.e., `A(end+1,:)=sum...`) before I figured that in this rare case, simple concatenation is actually cheaper in Matlab. Too bad I had to convert this into an actual function. Should work with Octave as well.

```
function A=f(A,n)
for i=1:2*n
A=[A;sum(A(end-1:end,:))]';end

```

I suppose this is a prime example of how **not** to make algorithms. For A=2x2, n=1000 this algorithm already takes 5 seconds on my laptop, n=2000 it's almost 50 seconds! (or approximately 30s if A is a `gpuArray` thanks to my trusty Quadro 1000M)

# Answer
> 1 votes
# Java, 2179 bytes

Just Worked it out:- This code is on Java Language.

```
import java.util.Scanner;

public class FebonnaciMatrix {
        static Scanner scan=new Scanner(System.in);

        public static void main(String[] args) {

        int x,y;
        System.out.println("For the Array to Work Upon:- ");

        System.out.println("Enter the Row:- ");
        int row=scan.nextInt();
        System.out.println("Enter the Column:- ");
        int col=scan.nextInt();

        int inpArr[][]=new int[row][col];

        System.out.println("Enter the values");
        inpArr=inpValues(row,col);

        System.out.println("The Input Array is:- ");
        display(inpArr,row,col);

        System.out.println("Input the Array size of Febonacci Array ");

        System.out.println("Enter the Row");
        int frow=scan.nextInt();
        System.out.println("Enter the Column");
        int fcol=scan.nextInt();

        int febArr[][]=new int[frow][fcol];
        febArr=copyValue(inpArr,febArr,row,col);

        for(x=0;x<row;x++)
        {
            for(y=col;y<fcol;y++)
                febArr[x][y]=febArr[x][y-2]+febArr[x][y-1];
        }

        for(x=row;x<frow;x++)
        {
            for(y=0;y<fcol;y++)
                febArr[x][y]=febArr[x-2][y]+febArr[x-1][y];
        }

        System.out.println();
        System.out.println("The Febonacci Array:-");
        display(febArr,frow,fcol);
    }

    static void display(int[][] arr,int row,int col)
    {
        int x,y;
        for(x=0;x<row;x++)
        {
            for(y=0;y<col;y++)
                System.out.print(arr[x][y]+"\t");
            System.out.println();
        }
    }

    static int[][] inpValues(int row,int col)
    {
        int arr[][]=new int[row][col];
        int x,y;
        for(x=0;x<row;x++)
        {
            for(y=0;y<col;y++)
            {
                System.out.print("Enter the value:- ");
                arr[x][y]=scan.nextInt();
            }
        }
        return arr;
    }

    static int[][] copyValue(int[][] old, int[][] ne, int row,int col)
    {
        int x,y;
        for(x=0;x<row;x++)
        {
            for(y=0;y<col;y++)
                ne[x][y]=old[x][y];

        }
        return ne;
    }

}

```

# Answer
> 1 votes
# Python, 103 ~~105~~ bytes

```
f=lambda n,L:f(n-1,[l+[sum(l[-2:])]for l in L])if n else L
lambda n,L:zip(*f(n,map(list,zip(*f(n,L)))))

```

Anonymous function takes list of list and passes to recursive function `f`. Output is transposed and then passed to `f` again, then the output of the second go is re-transposed. Output is a list of tuples

Saved two bytes thanks to bakuriu

# Answer
> 1 votes
# APL (Dyalog Classic), 17 bytes

```
{⍉⍵,⊢/2+/⍵}⍣2⍣⎕⊢⎕

```

Try it online!

# Answer
> 0 votes
# Perl 6,  ~~87 73~~  71 bytes

```
->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m.push: [map {[+] m[*X-1,2;$_]},m[0].keys]};m}
->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m[+*]=[m[*-2;*] »+«m[*-1]]};m}
->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m[+*]=[m[*-2;*]Z+m[*-1;*]]};m}

```

```
-> \c, \m {
  for ^c { # 0 ..^ c

    # each row
    .[+*]                            # new column at the end of row ($_)
          = [+] .[ * X- 1,2 ]        # add up the last two entries in row ($_)
                              for m; # for every row

    # too bad this was longer than the above code
    # m[*;+*]=map *+*,m[*;*-2,*-1]

    # each column
    m[ +* ]                 # add new row
            = [             # make it an Array rather than a List
                m[ *-2; * ] # the second to last row
                »+«         # added columnwise with
                m[ *-1 ]    # the last row
              ]
  };

  m # return the result
}

```

### Usage:

```
use v6.c;
# give it a lexical name
my &code = ->\c,\m{ … }

my @return = code 3,[[1,1,1],[2,3,4]];

put '[ ', $_».fmt('%2d'), ' ]' for @return;

put '';

put @return.perl ~~ {S:g/' '//};

```

```
[  1  1  1  2  3  5 ]
[  2  3  4  7 11 18 ]
[  3  4  5  9 14 23 ]
[  5  7  9 16 25 41 ]
[  8 11 14 25 39 64 ]

[[1,1,1,2,3,5],[2,3,4,7,11,18],[3,4,5,9,14,23],[5,7,9,16,25,41],[8,11,14,25,39,64]]

```

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


title: The NX source-length problem

text:
# Question
Title: The NX source-length problem
On PPCG, we have had lots of challenges where the length of your output is dependent on the length of your source code. For the purposes of this challenge, we will call these *Source-length problems*. The two most well known examples of source-length problems are

More simply, the `NX` source length problem is the challenge of creating a program whose output is exactly **N** times (**X**) the length of the source code. There have even been some variants on this type of challenge, for example

These usually tend to be pretty interesting, although fairly simple to implement. However, we've never had a *generalized* source-length problem. Until today that is. Here is your challenge for today:

> Given a positive integer **N**, output an answer to the NX source-length problem in the same language.

For example, let's say you wrote a submission in the language *foo*. If your program or function was given the input 3, you must output a new foo program or function **s**, that takes no input and whose output is exactly 3 times the length of **s**. Borrowing Martin's rules on the first challenge, here are some requirements for **s**:

* Your code and your **s** may use any consistent encoding you like. However, **s** may only output bytes in the printable ASCII range (0x20 to 0x7E, inclusive), or newlines (0x0A or 0x0D).
* **s** must not be a quine, so the code and the output must differ in at least one byte.
* **s** must be at least one byte long.
* If your output contains trailing newlines, those are part of the byte count.
* The output doesn't always have to be the same, as long as you can show that every possible output satisfies the above requirements.
* Usual quine rules *don't* apply. You may read the source code or its size, but I doubt this will be shorter than hardcoding it in most languages.

And adding a few rules of my own

* Output from errors does *not* count towards output length.
* If your solution fails for large **N** because of integer size restrictions, this is OK. Keep in mind, that this does not mean you can abuse native number types.

I highly recommend testing your code with inputs that are a different number of digits, since naive approaches that work for 1 digit **N**s will fail for 2 digit **N**s. Please also include an explanation of how you know your program is valid. Although this isn't mandatory, it is encouraged.

Since this task will be much easier in REPL languages, if you do answer in a REPL, please post your answer as

```
# Foo REPL, N bytes

```

so that it is distinguished from a regular answer in foo.

Of course, since this is a challenge, try to write the shortest possible answer in bytes as you can!

## Leaderboard

Please format your answer like this so that it shows up in the leaderboard:

```
# <Language-name>, <n> bytes

    code
    code

```

```
/* Configuration */

var QUESTION_ID = 154961; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 31716; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

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

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

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

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body {
  text-align: left !important;
  display: block !important;
}

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

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

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

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

# Answer
> 9 votes
# , 4 bytes

```
;“ x

```

For input **n**, this prints the program `**n** x`.

Try it online!

The program `**n** x` sets its argument and return value to **n**, then executes the `x` atom to repeat **n** **n** times, resulting in an array of **n** **n**'s.

Try it online!

### Proof of validity

Let **d** be the number of digits of **n**, so the program `**n** x` is **d+2** bytes long.

Python 3 (and, therefore, M) prints an array of **n** **n**'s like `[n, ..., n]`.

Since all **n** copies of `n` are **d** bytes long, the first **n-1** copies of **n** are followed by `,` (**2** bytes), and `[]` surrounds the array (**2** bytes), the output is **nd + 2(n-1) + 2 = nd + 2n = n(d+2)** bytes long.

# Answer
> 4 votes
# Operation Flashpoint scripting language, 68 bytes

```
f={format["g={i=0;s={};while{i<%1}do{i=i+1;s=s+{    }+g};s}",_this]}

```

A function that takes a number *n* as input and outputs a function *g* that produces output with *n* times the length of its own source code.

**Example:**

```
3 call f

```

outputs

```
g={i=0;s={};while{i<3}do{i=i+1;s=s+{    }+g};s}

```

which outputs

```
    i=0;s={};while{i<3}do{i=i+1;s=s+{    }+g};s    i=0;s={};while{i<3}do{i=i+1;s=s+{    }+g};s    i=0;s={};while{i<3}do{i=i+1;s=s+{    }+g};s

```

### Alternative version ( ~~75~~  71 bytes):

```
f={format[{g={i=0;s={};while{i<%1}do{i=i+1;s=s+"g={"+g+"}"};s}},_this]}

```

Outputs a function *g* which outputs its own source code *n* times.

**Example:**

```
3 call f

```

outputs

```
g={i=0;s={};while{i<3}do{i=i+1;s=s+"g={"+g+"}"};s}

```

which outputs (when called with `hint call g`)

# Answer
> 4 votes
# MATL, ~~20~~ ~~19~~ 18 bytes

```
`@G*qVn4+@-}3M'Z"'h

```

This ouputs a program of the form

```
*abc*
Z"

```

followed by a newline, where *`abc`* represents a positive integer. The function `Z"` gives a string of that many spaces, which is implicitly printed with a trailing newline.

Try it online!

Examples:

* Input `142` produces the program

```
993
Z"

```

(plus newline). Try it online with footer code that changes space to `!` for visibility.

The program length is `7` (including the newline), and its output has `994` characters (`993` spaces and `1` newline), which equals `142*7`.
* Input `143` produces the program

```
1143
Z"

```

with a trailing newline. Try it online with the same modification.

The program length is `8` (including the trailing newline), and its output has `1144` characters (`1143` spaces and `1` newline), which equals `143*8`.

### Explanation

The most difficult part is, given input `N`, computing the number *`abc`*. Let `f` denote the function "number of digits of". The code finds the first positive integer `K` that satisfies

```
f(K*N-1)+4 = K

```

The `1` above accounts for the trailing newline which is output by the produced program after the string of spaces, and the `4` accounts for the length of the `Z"` statement and the two newlines in the produced program. The number *`abc`* to be included in the output program is then `K*N-1`.

In the examples above:

* For `N=142` the obtained `K` is `7`, which gives `K*N-1 = 993`.
* For `N=143` the obtained `K` is `8`, which gives `K*N-1 = 1143`.

### Commented code

```
`         % Do...while
  @       %   Push iteration index. This is a potential K
  G       %   Push input, N
  *       %   Multiply
  q       %   Subtract 1
  V       %   Convert to string (*)
  n       %   Number of characters
  4       %   Push 4
  +       %   Add
  @       %   Push K
  -       %   Subtract. This is the loop condition. If 0 (meaning the
          %   condition f(K*N-1)+3 = K is fulfilled) the loop is exited
}         % Finally (execute on loop exit)
  3M      %   Push string (*) from automatic clipboard
  'Z"'    %   Push string 'Z"'
  h       %   Concatenate horizontally
          % End (implicit). Display with trailing newline (implicit)

```

# Answer
> 3 votes
# Befunge-98, ~~22 21~~ 14 bytes

Edit: Didn't see that the output has to be printable ASCII only. Funnily enough, this saved a byte.

Edit: I was being stupid. What do you do if you to do something X times, N times? You do it X times N, times, duh.

Edit: Just realised this won't work with 10 or 13, because they print newlines, so I changed to the alternate version:

```
"&3*1-''5k,@.k

```

which can't print newlines.

Try it online! Try it N = , ,  and 100

The NX program is in the form:

```
'N k.@

```

Where N is the char code of the inputted number. Prints N\*3\*("0 ")

### Old version:

```
"&''fk,@.k7p01-1_@#!:

```

Try it online! Try N = , , and

# Answer
> 2 votes
# Haskell, 55 bytes

```
f n="'a'<$[1.."++show(n*(10+length(show$n*10+10)))++"]"

```

Try it online!

# Answer
> 1 votes
# Zsh, ~~28~~ 22 bytes

```
repeat $1 echo rev \$0

```

For input **n**, this prints **n** copies of `rev $0` and a linefeed.

Try it online!

The generated programs print **n** reversed copies of themselves.

Try it online!

# Answer
> 1 votes
## JavaScript (ES6), 51 bytes

```
n=>`_=>("${n}"[r="repeat"](2)+" "[r](41))[r](${n})`

```

Outputs (e.g.) `_=>("42"[r="repeat"](2)+" "[r](38))[r](42)` which has length 42 and whose output has length 1764.

# Answer
> 1 votes
# Python 2, 56 bytes

```
f=lambda n:"print`f`*"+`n*n`+','+'#'*(33*n-9-len(`n*n`))

```

Creates a string of the form

```
print`f`*<number>################...#####

```

where the number is `n^2` and there are enough #s to make the string `33n` characters long. Depending on the way your OS stores memory addresses, the `33` might need to change.

There's also that annoying `+','` in the middle so that it conforms to the newline requirement; if anyone can figure out how to shorten that it would be much appreciated.

There's a less iffy version with 58 bytes in the following form:

```
f=lambda n:"print`id`*"+`n*n`+','+'#'*(22*n-10-len(`n*n`))

```

which functions identically and more reliably, but at the cost of using "id" instead of "f" as the function and having to subtract 10 instead of 9, using an extra character.

An explanation of this technique is given here.

# Answer
> 0 votes
# Clean, 117 bytes

```
import StdEnv
$l n="import StdEnv\nf={#'0'\\\\_<-[1.."+++fromInt n+++"],_<-[0.."+++fromInt l+++"]}"

```

#

```
\n= $(size($99n))n

```

Try it online!

An anonymous function taking `Int` and giving the source for a function returning a string of the requisite length, having the signature `f :: String`. While this is technically reliant on the native integer type having less than 256 bits, I don't believe that this qualifies as abuse thereof.

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