title: Duck, duck, gone!

text:
# Question
Title: Duck, duck, gone!
Here is the (quite scary) Five little ducks song(it is not long):

```
Five little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only four little ducks came back.

Four little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only three little ducks came back.

Three little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only two little ducks came back.

Two little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only one little duck came back.

One little duck went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but none of the little ducks came back.

Mother duck herself went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
and all of the little ducks came back.

```

Your task is not to output this song. You should take a verse and output the next verse, cyclically (the next verse of the last verse is the first verse).

## Rules

* No standard loopholes, please.
* Input/output will be taken via our standard input/output methods.
* The *exact* verse must be outputted, and there should be no differences when compared to the song lyrics. The input will not be different when it is compared to the song lyrics too.

## Examples

```
Mother duck herself went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
and all of the little ducks came back.

```

Expected:

```
Five little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only four little ducks came back.

```

---

```
Three little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only two little ducks came back.

```

Expected:

```
Two little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only one little duck came back.

```

## The Catalogue

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

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

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

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](https://esolangs.org/wiki/Fish), 121 bytes

```

```
/* Configuration */

var QUESTION_ID = 193467; // 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 = 8478; // 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: 500px;
  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
# Stax, ~~115~~ 111 bytes

```
τ*^&k─Zè0µ9┬$█◘çl╟☼:Drσ59ò╠▄┴╢Q♂╔¡ô╜Oa╣▀yèA÷╨%^♀█Ö+╡◄ì=∙%╧o▌Θ<▲Çα¿╗√;1°┼╤V◘ú┐♥▒ÇM☼b╩░o]YaL4░ƒ%(Æ♫Q0æÆä⌂¡╘○Eâó╪¡

```

Run and debug it

All the verses as test cases
> 4 votes

# Answer
# JavaScript (ES9), 227 bytes

This is similar to the Node version below but uses a formula based on `parseInt()` instead of `Buffer()` to identify the input verse.

This is ES2018 (aka ES9) because we're using a regular expression with the `/s` flag (dotAll).

```
s=>'Mother duck herself1and all23,,Three4two3,Five4four3,Four4three3,One01but none23,Two4one0'.split`,`[parseInt(s,30)&7].replace(/\d/g,n=>[x=' little duck',y=/ w.*\n/s.exec(s),' of the',x+='s',x+y+'but only '][n])+s.slice(-11)

```

Try it online!

### How?

In this version, we parse the entire input verse as base 30 (`0` to `t`) and perform a bitwise AND with 7. The parsing stops on the first invalid character, leading to:

```
 verse | valid part | base 30 -> decimal | AND 7
-------+------------+--------------------+-------
   0   |  'fi'      |            468     |   4
   1   |  'fo'      |            474     |   2
   2   |  'three'   |       23973734     |   6
   3   |  't'       |             29     |   5
   4   |  'one'     |          22304     |   0
   5   |  'mother'  |      554838747     |   3

```

---

# JavaScript (Node.js),  ~~233 231~~  227 bytes

*Saved 2 bytes thanks to @Shaggy*

```
s=>'Three4two3,Four4three3,Mother duck herself1and all23,One01but none23,,,Two4one0,,Five4four3'.split`,`[Buffer(s)[2]%9].replace(/\d/g,n=>[x=' little duck',y=/ w.*\n/s.exec(s),' of the',x+='s',x+y+'but only '][n])+s.slice(-11)

```

Try it online!

### How?

The third character of each input verse can be used as a unique identifier. By taking its ASCII code modulo 9, we get:

```
 verse | 3rd char. | ASCII code | MOD 9
-------+-----------+------------+-------
   0   |    'v'    |     118    |   1
   1   |    'u'    |     117    |   0
   2   |    'r'    |     114    |   6
   3   |    'o'    |     111    |   3
   4   |    'e'    |     101    |   2
   5   |    't'    |     116    |   8

```

The output verses are encoded with the following templates:

```
 verse | template
-------+---------------------------------
   0   | 'Five4four3'
   1   | 'Four4three3'
   2   | 'Three4two3'
   3   | 'Two4one0'
   4   | 'One01but none23'
   5   | 'Mother duck herself1and all23'

```

Where each digit is replaced with a string according to the following table:

```
 digit | replaced with
-------+---------------------------------------------------
   0   | ' little duck'
   1   | / w.*\n/s.exec(s)
   2   | ' of the'
   3   | ' little ducks'
   4   | ' little ducks' + / w.*\n/s.exec(s) + 'but only '

```

Where the regular expression `/ w.*\n/s` extracts this common part from the input:

```
  went out one day,[LF]
 over the hills and up away.[LF]
 Mother Duck said, "Quack Quack Quack Quack",[LF]

```

We finally add the last 11 characters of the input, which is `" came back."`.
> 20 votes

# Answer
# Python 3, ~~267 263~~ 254 bytes

*4 bytes saved thanks to @ovs*

```
def f(s):
 for a in zip(T[2:]+T,T):s=s.replace(*a)
 return s
T="8:9:and allHO1BnoneHT2No1T3Nt2F4Nt3FiveINf4MotherD herself"
for r in "H of theI,4ourI,3hreeI,2woI,1neL:,ILs:,L littleD,D duck,NBonly ,Bbut ".split(','):T=T.replace(r[0],r[1:])
T=T.split(':')

```

Try it online!

Works by replacing the relevant parts by the respective parts of the next verse.

After the preinitialisation, `T` is `['8', '9', 'and all of the little ducks', 'One little duck', 'but none of the little ducks', 'Two little ducks', 'but only one little duck', 'Three little ducks', 'but only two little ducks', 'Four little ducks', 'but only three little ducks', 'Five little ducks', 'but only four little ducks', 'Mother duck herself']`.

# Alternative Python 2, 252 bytes

*by @ovs*

```
lambda s:reduce(lambda s,a:s.replace(*a),zip(T[2:]+T,T),s)
T="8:9:and allHO1BnoneHT2No1T3Nt2F4Nt3FiveINf4MotherD herself"
for r in "H of theI,4ourI,3hreeI,2woI,1neL:,ILs:,L littleD,D duck,NBonly ,Bbut ".split(','):T=T.replace(r[0],r[1:])
T=T.split(':')

```

Try it online!
> 11 votes

# Answer
# QuadR, ~~257~~ 242 bytes

-14 thanks to Black Owl Kai, -1 thanks to Kevin Cruijssen

```
ive
Four
hree
Two( little duck)s
One little( duck)
Mother( duck) herself
four
two( little duck)s
only on(e little duck)
but none
and all of the
our
Three
wo
One\1
Mother\1 herself
Five little\1s
three
one\1
none of th\1s
and all
but only four

```

Try it online!
> 9 votes

# Answer
# T-SQL, ~~407 390 388~~ 382 bytes

```
DECLARE @ CHAR(999)=REPLACE(REPLACE('SELECT CASE LEFT(v,2)WHEN''Fi74,''Four''),122,4,''three'')WHEN''Fo74,''Three''),123,5,''two'')WHEN''Th75,''Two''),121,16,''on#'')WHEN''Tw716,''On#''),115,20,''none of th#s'')WHEN''On715,''Mother duck herself''),115,8,''and all'')WHEN''Mo719,''Fiv#s''),113,14,''but only four'')END FROM i',7,'''THEN STUFF(STUFF(v,1,'),'#','e little duck')EXEC(@)

```

Input is via a pre-existing table \\$i\\$ with `VARCHAR(MAX)` field \\$v\\$, per our IO rules.

After a couple of byte-saving `REPLACE`s, executes the following as dynamic SQL:

```
SELECT CASE LEFT(v,2)
       WHEN'Fi'THEN STUFF(STUFF(v,1,4,'Four'),122,4,'three')
       WHEN'Fo'THEN STUFF(STUFF(v,1,4,'Three'),123,5,'two')
       WHEN'Th'THEN STUFF(STUFF(v,1,5,'Two'),121,16,'one little duck')
       WHEN'Tw'THEN STUFF(STUFF(v,1,16,'One little duck'),115,20,'none of the little ducks')
       WHEN'On'THEN STUFF(STUFF(v,1,15,'Mother duck herself'),115,8,'and all')
       WHEN'Mo'THEN STUFF(STUFF(v,1,19,'Five little ducks'),113,14,'but only four')END
FROM i

```

Uses a `CASE` statement and `STUFF` commands to insert/overwrite characters at the listed positions.

**EDITS**:

1. Replace original (below) with an entirely different strategy
2. Saved two bytes by switching to `LEFT` instead of `SUBSTRING` and eliminating a space
3. Saved 6 bytes by changing variable to `CHAR` and moving an extra letter into the second `REPLACE` (thanks, @CDC!)

Here's my first version, using a different method (post-replacement, formatted):

```
DECLARE @ VARCHAR(MAX)
SELECT @=v FROM i
SELECT @=REPLACE(@,PARSENAME(value,2),PARSENAME(value,1))
FROM string_split('e.but none.and all
                  -e.One little duck.Mother duck herself
                  -o.only one little duck.none of the little ducks
                  -o.Two little ducks.One little duck
                  -r.two little ducks.one little duck
                  -r.Three.Two
                  -u.three.two
                  -u.Four.Three
                  -v.four.three
                  -v.Five.Four
                  -t.and all of the.but only four
                  -t.Mother duck herself.Five little ducks','-')
WHERE LEFT(value,1)=SUBSTRING(@,3,1)
PRINT @

```

`STRING_SPLIT` and `PARSENAME` are used to break a string into rows and columns via `-` and `.` separators.

The first column is a key character that is matched against the 3rd letter of the input verse (thanks for the idea, @Night2). The second and third are the replacements being performed for that verse.
> 8 votes

# Answer
# Java 10, 347 bytes

```
s->{String L=" little duck",M="Mother duck herself";int i=9;for(var t:("ive;Four;hree;Two"+L+"s;One"+L+";four;two"+L+"s;only one"+L+";but none;and all of the;"+M).split(";"))s=s.replace(t,++i+"");for(var t:("Five"+L+"s;but only four;and all;none of the"+L+"s;one"+L+";three;"+M+";One"+L+";wo;Three;our").split(";"))s=s.replace(i--+"",t);return s;}

```

Try it online.

**Explanation:**

We first replace all parts one by one with integers in the range \\$\[10,21\]\\$, and then these integers back to their replacements. The reason this is done in two steps, is because we would otherwise replace replacements.

```
s->{                     // Method with String as both parameter and return-type
  String L=" little duck",M="Mother duck herself";
                         //  Two temp strings to save bytes
  int i=9;               //  Temp replacement integer, starting at 9
  for(var t:("ive;Four;hree;Two"+L+"s;One"+L+";four;two"+L+"s;only one"+L+";but none;and all of the;"+M).split(";"))
                         //  Loop over the parts to replace:
    s=s.replace(t,       //   Replace the part,
                ++i+""); //   with the integer pre-incremented by 1
  for(var t:("Five"+L+"s;but only four;and all;none of the"+L+"s;one"+L+";three;"+M+";One"+L+";wo;Three;our").split(";"))
                         //  Then loop over the parts to replace with in reverse:
    s=s.replace(i--+"",  //   Replace the (post-decrementing) integer,
    t);                  //   with the replacement-part
  return s;}             //  And then return the modified String as result

```
> 7 votes

# Answer
# PHP (7.4), ~~253~~ 247 bytes

-6 bytes by improving how the replacements array is built with more help from "Unpacking inside arrays".

```
<?=strtr($argv[1],array_combine([0,1,...$a=[Five.$l=($o=" little duck").s,($b="but only ").four.$l,Four.$l,$b.three.$l,Three.$l,$b.two.$l,Two.$l,$b.one.$o,One.$o,"but none of the$l","Mother duck herself","and all of the$l"]],[...$a,$a[0],$a[1]]));

```

Try it online!

This creates an array of every possible replacement (12 used + 2 unused) in a `key=>value` format. Example: `['Mother duck herself' => 'Five little ducks', etc...]` and then just replaces those using strtr.

The only interesting thing is my first ever usage of "Unpacking inside arrays" which is a new feature in PHP 7.4.

---

# PHP, 264 bytes

```
<?=str_replace(($a=[[Five.$l=($o=" little duck").s,($b="but only ").four.$l],[Four.$l,$b.three.$l],[Three.$l,$b.two.$l],[Two.$l,$b.one.$o],[One.$o,"but none of the$l"],["Mother duck herself","and all of the$l"]])[$i=strpos(vuroet,($v=$argv[1])[2])],$a[++$i%6],$v);

```

Try it online!

I have stored different words of each verse in an array. I find which verse the input is using third character of the input as it is unique (`vuroet`). Then I simply replace different words of that verse with different words of the next verse.
> 6 votes

# Answer
# Python 2, 1034 bytes

This is my code! It employs a simple dictionary. After running this code, you can enter any verse and it will output the next verse.

PS: I am new to this channel and this is my first post. I really liked this challenge so decided to give it a try. Please feel free to correct me.

```
import sys
i=sys.stdin.readlines()
s={"Mother":"""Five little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only four little ducks came back.""",
"Five":"""Four little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only three little ducks came back.""",
"Four":"""Three little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only two little ducks came back.""",
"Three":"""Two little ducks went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but only one little duck came back.""",
"Two":"""One little duck went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
but none of the little ducks came back.""",
"One":"""Mother duck herself went out one day,
over the hills and up away.
Mother Duck said, "Quack Quack Quack Quack",
and all of the little ducks came back."""}
print s[i[0].split(" ")[0]]

```
> 6 votes

# Answer
# Clean, 352 bytes

```
import StdEnv,Text
$n={#"Five"+e+"four"+d,"Four"+e+"three"+d,"Three"+e+"two"+d,"Two"+e+"one"+a,"One"+a+b+"but none"+f,"Mother duck herself"+b+"and all"+f}.[indexOf{n.[2]}"tvuroe"]+" came back."
a=" little duck"
b=" went out one day,\nover the hills and up away.\nMother Duck said, \"Quack Quack Quack Quack\",\n"
d=a+"s"
e=d+b+"but only "
f=" of the"+d

```

Try it online!
> 5 votes

# Answer
# C# (Visual C# Interactive Compiler), 262 bytes

```
x=>$@"{l[g=x[2]*37%724%7]}{g-5:; little} duck{g-4: herself;s;\} went out one day,
{(x=x.Split('\n'))[1]}
{x[2]}
{g-5:and;but} {g-4:all;only;none} {(g>3?"of the":l[g+1].ToLower())} little duc{g%3:ks;;k} came back.";var l=" Four Three Two One Mother".Split();int g

```

Try it online!
> 5 votes

# Answer
# PowerShell, ~~356~~ ~~343~~ ~~340~~ 336 bytes

```
param($p)$l,$M=' little duck','Mother duck herself'
("ive!our;four!three;hree!wo;Four!Three;two!one;s c! c;Two!One;s w! w;only one!none of the;k c!ks c;One$l!$M;but none!and all;$M!Five$l`s;and all of the!but only four"-split';')[$(switch -r($p){^Fi{0,1}^Fo{2,3}^Th{2,4,5}^Tw{6..9}^O{10,11}^M{12,13}})]|%{$p=$p-creplace($_-split'!')}
$p

```

Try it online.

**More readable version:**

```
param($p)
$l, $M = ' little duck', 'Mother duck herself'
$replacements = @"
ive!our
four!three
hree!wo
Four!Three
two!one
s c! c
Two!One
s w! w
only one!none of the
k c!ks c
One$l!$M
but none!and all
$M!Five$l`s
and all of the!but only four
"@ -split '\n'
$i = switch -regex ($p) { ^Fi { 0, 1 }
                          ^Fo { 2, 3 }
                          ^Th { 2, 4, 5 }
                          ^Tw { 6..9 }
                          ^O  { 10, 11 }
                          ^M  { 12, 13 } }
$replacements[$i] | % { $p = $p -creplace ( $_ -split '!' ) }
$p

```
> 3 votes

# Answer
# PowerShell, ~~265~~ ~~263~~ ~~255~~ ~~251~~ 246 bytes

```
$d='Five1four2s,Four1three2s,Three1two2s,Two1one2,One23but none52s,Mother duck herself3and all52s'-split','
'2s34',' little duck',-join($args-split'(\s)')[5..39],'but only ',' of the'|%{$d=$d-replace++$i,$_}
$d[+"$args"[2]*37%724%7]+' came back.'

```

Try it online!

I used the brute force to find the expression `+"$args"[2]*37%724%7`.

```
 verse | 3rd char. | ASCII code | *37%724%7
-------+-----------+------------+-----------
   0   |    'v'    |     118    |   1
   1   |    'u'    |     117    |   2
   2   |    'r'    |     114    |   3
   3   |    'o'    |     111    |   4
   4   |    'e'    |     101    |   5
   5   |    't'    |     116    |   0

```

Thanks @Arnauld for the `3rd char`.
> 3 votes

# Answer
# 05AB1E, 134 bytes

```
“€µ‚•„í†ìˆÈ“#’ „ê Ðœs’δJć¨…î¥Ðœº¶s‚ìðδJD…€³€É δì¨¦“€ƒ€Ÿ€‚€€““€³Šª€‚€€“‚’ „ê Ðœs ’δJì…‹é‚ƒ.δJU.•4Ôāl•|н2èk©è.ª?I„
ý#3.$17£ðý„
¶:,X®è?

```

Try it online!

Since i'm relatively new to 05AB1E, this can maybe be golfed a lot

```
                ### Preparation of the output strings ###
“€µ‚•„í†ìˆÈ“        push "one two three four five"
#                   split that by spaces
’ „ê Ðœs’           push " little ducks"
δJ                  join each number with " little ducks"
ć¨                  separate "one little ducks" and drop the "s"
…î¥Ðœº¶             push "mother duck herself"
s                   swap it with "one little duck"
‚ì                  prepend both strings to the list ["mother duck herself", "one little duck", "two little ducks" ... ]
ðδJ                 append a space to each list entry
D                   duplicate it
…€³€É               push "but only "
δì                  prepend "but only " to each list entry
¨¦                  drop the first and last list entry
“€ƒ€Ÿ€‚€€“          push "and all of the"
“€³Šª€‚€€“          push "but none of the"
‚                   push the two strings into a list
’ „ê Ðœs ’δJ        append " little ducks " to each
ì                   prepend it to the sentence list ["and all of the little ducks ", "but none of the little ducks ", "but only one little duck " ...]
…‹é‚ƒ.              push "came back."
δJ                  append that to each list entry
U                   save that list in X for later use

                ### Determine which verse has to be answered ###
.•4Ôāl•             push "eoruvt"
|н2è                get the third letter of the input
k                   get the index of that letter in "eoruvt". Now we know which verse we must return
©                   save that index in ® for later use

                ### Print the answer strings ###
è.ª?                print that index of the first sentence list (first three words of answer)
I„                  join the four input strings by <space><newline>
ý
#                   split that by spaces
3.$                 cut off the first three words
17£                 keep only the next 17 words
ðý                  join remaining words by spaces
„
¶:                  replace <space><newline> by only <newline>
,                   print that ("went out ... Quack\",")
X®è?                print the last line of answer

```
> 3 votes

# Answer
# Bash, ~~373~~ 355 bytes

Nothing too crazy here. An easy few byte reduction would be to replace the two-character variables (a1,a2,a3,e1..e6) with single character ones.

```
read a{1..3} b
read c
read d
read e{1..6}
W="$e1 $e2"
X="${e3^} $a2 $a3"
Y="$e5 $e6"
Z="$e4 $Y"
p=$X
case $a1 in M*)p="Five ${Y::12}";s="but only four $Y";;O*)p="${d::11} herself";s="and all of $Z";;Tw*)p=${X/s};s="$e1 none of the $a2 ducks $e6";;Th*)s="$W one $e4 duck $e6";;Fo*)s="$W two $Z";;Fi*)s="$W three $Z";;esac
echo $p $b;echo $c;echo $d;echo $s

```

Try it online!

~~Try it online!~~
> 2 votes

# Answer
# Japt v2.0a0, 143 bytes

Tried encoding a single verse with replacements but, in the end, adapting Arnauld's solution ended up being shorter. Have another idea that might, hopefully, work out shorter again but don't know when I'll get to try it.

```
tBn)i`Fr4È(e3
Two4e0
MÇ@r Ýõ Êelf1d a¥23
O01¿t Í
23
TËG4two3
Five4fr3`·g`v`b¢Î)r\dÈ°g[V=` Ò¤ Ýõ`W=Uf/ w.*\n/s `  e`V±'sV+W+`¿t § `]

```

Try it \- includes all verses
> 2 votes

# Answer
# Charcoal, 156 bytes

```
≔⌕tvuroe§θ²δ§⪪”↶0∨↘»≔xj➙⌈´βＸPＮLA‽⟦O⧴＆▷V'¦³≧ψZρ⊞t”¶δＦ‹δ⁵”↶↧V4ⅉＨ‴G%”Ｆ‹δ⁴s⮌…⮌θ¹⁸⸿η⸿ζ⸿§⪪”}∧h⁴ＮＱ≕Q^⪫ΦＧ✂q'ⅉＭG./_⸿s⁵6P⁴″⊟±ＮNpOfBz↷Ｆι‖ＴM→⁻γ？k⁴ς!d⁵º'E,θ}x§-υ”¶δ✂ε±¹¹

```

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

```
≔⌕tvuroe§θ²δ

```

Look at the third character of the first line to work out which verse we want.

```
§⪪”↶0∨↘»≔xj➙⌈´βＸPＮLA‽⟦O⧴＆▷V'¦³≧ψZρ⊞t”¶δＦ‹δ⁵”↶↧V4ⅉＨ‴G%”Ｆ‹δ⁴s⮌…⮌θ¹⁸

```

Output the first part of the first line by indexing into the list of strings `Five`, `Four`, `Three`, `Two`, `One`, `Mother duck herself`. Then print `little duck` and `s` as appropriate, followed by the last 18 characters of the input line (which are always the same on each verse).

```
⸿η⸿ζ⸿

```

The middle two lines are always the same on each verse.

```
§⪪”}∧h⁴ＮＱ≕Q^⪫ΦＧ✂q'ⅉＭG./_⸿s⁵6P⁴″⊟±ＮNpOfBz↷Ｆι‖ＴM→⁻γ？k⁴ς!d⁵º'E,θ}x§-υ”¶δ✂ε±¹¹

```

For the last line it turns out to be golfier to include `little ducks` in the list of alternatives for some reason, but the last 11 characters are still copied from the input.
> 2 votes

# Answer
# Perl 6, 247 bytes

```
{S:i/ne\sl.*?<(s//}o{m/..(.)(\S*)**3%\s(.**92).*(.**11)/;[(my$l=" little ducks")~$3 XR~"Mother duck herself$2and all of the","One{$l~=$2}but none of the","Five{$l~="but only "}four","Four{$l}three","Three{$l}two","Two{$l}one"]["eotvur".index($0)]}

```

Try it online!

Definitely golfable, especially the last 5 elements in the list in the form `"num $l num-1"`, or the starting regex that matches the right parts of the old input.
> 1 votes

# Answer
# ink, 353 bytes

```
=d(v)
~temp n=(v?"Fi")+(v?"F")*4+(v?"Th")+(v?"T")*2+(v?"O")
{n-1:{n:{n-5:{n-4:{n-3:One|Two}|Three}|Four}|Five} little duck{n-2:s}|Mother duck herself} went out one day,
over the hills and up away,
Mother Duck said "Quack Quack Quack Quack",
{n-1:but {n-2:only {n:{n-5:{n-4:one|two}|three}|four}|none of the}|and all of the} little duck{n-3:s} came back.

```

Try it online!

First, uses substring checks to figure out what verse we're in - that's easy enough thanks to the capitalisation of the numbers at the start - `F`, `T` and `O` don't occur in any other places, and you can distinguish the second and fourth verse from the first and third by also checking for `Fi` and `Th` respectively.

Then we just do what ink does best and print plain text specked with conditionals. I tried using switch statements at first, but while that looked nicer, it actually ended up longer.
You'd think the `Quack`s would be a good place to use variables, what with a string being repeated a bunch, but variables come with enough overhead that every way I tried to do that made the code longer. Maybe that's a sign I'm not supposed to golf in ink.
> 1 votes

# Answer
# Zsh, 270 bytes

```
read {a..d}
read e
read f
set `cat`
case $a in
M*)a=Five
b=$5
c=$6
set but only four ${@:5};;O*)a=Mother
b=$c
c=herself
1=and
2=all;;*o)a=One
c=duck
set but none of the ${@:4}
6+=s;;T*)a=Two
3=one
5=duck;;*r)a=Three
3=two;;*)a=Four
3=three;;esac
<<Q
$a $b $c $d
$e
$f
$@

```

Try it online!

Explanation:

<pre><code># {a..d} expands to a b c d
# so, read four words and assign them to a, b, c, and d
# (d also gets all the extra words beyond the 4th)
read {a..d}

# read two lines and store them in e and f
read e
read f

# assign the words in the remainder of the input
# to the numbered variables 1...
set `cat`

# if the first word...
case $a in
    # starts with M (i.e. Mother)
    M*)
        a=Five
        b=$5  # "little"
        c=$6  # "ducks"
        # set the numbered variables
        # ${@:5} is the existing numbered vars from 5 onwards
        set but only four ${@:5}
    ;;
    # One
    O*)
        a=Mother
        b=$c       # "duck"
        c=herself
        1=and
        2=all
    ;;
    # ends with o (Two)
    *o)
        a=One
        c=duck
        set but none of the ${@:4}
        # "duck" -> "ducks"
        6+=s
    ;;
    # Three
    T*)
        a=Two
        3=one
        5=duck
    ;;
    # Four
    *r)
        a=Three
        3=two
    ;;
    # anything else (Five)
    *)
        a=Four
        3=three
    ;;
esac

# now print:
<<Q
$a $b $c $d
$e
$f
$@
```
</code></pre>
> 0 votes

---
Tags: code-golf, string, kolmogorov-complexity
---


title: Largest Error Message in 100 bytes

text:
# Question
Title: Largest Error Message in 100 bytes
The goal is to raise the error message with the most bytes! The error message may not be generated by the program itself, such as Python's `raise`. errors that do not terminate the program are not allowed unless they do not show an error message.

Here is an example in python that raises 243041 bytes of error code:

```
def a(m):
    try:-''
    except:
        if m>0:
            a(m-1)
        else:-''
a(900)

```

you can try it here.

# Answer
# Python 3, \\$\approx\\$A(A(A(9,9),A(9,9)),A(A(9,9),A(99,99))) where A is the Ackermann function,or limited by RAM

```
A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
a='.'*(A(A(A(9,9),A(9,9)),A(A(9,9),A(99,99))))
exec(a)

```

Don't try it online!

Stole the Ackermann function from here.

More manageable version to demonstrate:

```
A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
a='.'*(9999)
exec(a)

```

Try it online!

Admittedly I'm not certain this approach is arbitrarily extendible in practice.
> 4 votes

# Answer
# Jelly, a huge number \\$ + 1605\\$ bytes

```
ȷ!!!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡!¡”.xŒV

```

Try it online!

More specifically, this outputs an error message which is 1605 bytes long, plus two occurrences of massive chains of `...`. Unsurprisingly, this does not actually show an error really no matter where you run it, but in theory it will

I'm not entirely sure just how large this number is, aside from being significantly larger than \\$1000!\_{1000!\_{(1000!)!}}\\$, where \\$n!\_k\\$ represents applying \\$!\\$ to \\$n\\$ \\$k\\$ times e.g. \\$3!\_3 = ((3!)!)! = (6!)! = 720! = 2.6 \times 10^{1746}\\$
> 3 votes

# Answer
# APL (Dyalog Unicode), limited only by available memory

Full program. Causes error message a bit bigger than twice the given number.

```
⍎2e6⍴⎕A

```

Try it online!

`⎕A` the uppercase **A**lphabet

`2e6⍴` cyclically **r**eshape to a string with two million characters

execute

This causes an error of the form:

```
VALUE ERROR: Undefined name: *string*
      *string*
```
> 2 votes

# Answer
## Java 11, repeat error message \[231 \- 1\] times

String's Maximum length in Java is `Integer.MAX_VALUE` i.e. == 231 \- 1, or less, it depends on *server max memory size* and other conditions otherwise it produces `OutOfMemoryError`.

1. You can throw some `Error` with the certain message, for example:

```
throw new Error("fatal".repeat(Integer.MAX_VALUE/5));

```

Number of times to `repeat` is `Integer.MAX_VALUE` / 5 - because `"fatal"` is 5 chars.
2. You can return something like this. It is not the error itself, but the error message:

```
for(int i=0;i<Integer.MAX_VALUE;i++){
    String m="fatal"+i;
    out.println(m.repeat(Integer.MAX_VALUE/m.length()-1));
}

```
> 0 votes

# Answer
# Zsh, \\$4\times(9\times10^{307})^{32}+47\\$ bytes

```
alias r=repeat\ 9e307
r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r a+=1111
let $a

```

Try it online!

Generates a string containing \\$4\times(9\times10^{307})^{32}\\$ ones, then tries to evaluate it as an integer.

In practice you will obviously run into memory limitations. Here is a more manageable version:

```
repeat 9e1 repeat 9e1 a+=1
let $a

```
* `alias r=repeat\ 9e307` allows us to nest more `repeats` in the 100 bytes we have
* `9e307` (\\$9\times10^{307}\\$) is the largest compact finite floating-point number `zsh` might be able to count to
> 0 votes

---
Tags: code-challenge, restricted-source, busy-beaver, error-message
---


title: Prefix divisibility

text:
# Question
Title: Prefix divisibility
Inspiration

Given a positive integer \\$1 \le n \le 9\\$, output all positive \\$n\\$-digit integers \\$i\\$ for which the following is true:

* Each digit from \\$1\\$ to \\$n\\$ appears exactly once in \\$i\\$. Therefore, \\$i\\$'s digits are a permutation of the digits from \\$1\\$ to \\$n\\$.
* \\$i\\$ is divisible by \\$n\\$
* Removing the rightmost digit from \\$i\\$ yields another integer \\$i\_{\text{trunc}(1)}\\$ which is divisible by \\$n-1\\$
* Removing the rightmost digit from \\$i\_{\text{trunc}(1)}\\$ yields another integer \\$i\_{\text{trunc}(2)}\\$ which is divisible by \\$n-2\\$
* And so on, until \\$i\_{\text{trunc}(n-1)}\\$, which is divisible by 1.

For example, for \\$n = 3\\$, one such integer is \\$321\\$, as \\$321\\$ is divisible by \\$3\\$, \\$32\\$ by \\$2\\$ and \\$3\\$ by 1.

For \\$n = 4, 5, 7\\$, there are no such integers. In this case, you may output anything that cannot be confused with a possible output (e.g. `0`, `[]`, nothing, etc.). For \\$n = 3, 6\\$, you may output the two numbers in any format in which the two numbers are clearly separated from one another.

This is so the shortest code in bytes wins.

If you use a lookup table method, brownie points\\${}^\dagger\\$ are awarded if you also include a version that calculates the correct output.

\\${}^\dagger\\$Brownie points may or may not be in the form of an upvote

## Test cases

These cases are exhaustive, so you will never receive (or have to handle) an input not included here.

```
n -> i
1 -> [1]
2 -> [12]
3 -> [123, 321]
4 -> []
5 -> []
6 -> [123654, 321654]
7 -> []
8 -> [38165472]
9 -> [381654729]

```

# Answer
# 05AB1E, 8 bytes

```
LœJʒηāÖP

```

Try it online!

**Commented**:

```
L         # push [1..n]
 œ        # push all permutations
  J       # join each permutation into a number
   ʒ      # filter those numbers on:
    η     #   each prefix ...
      Ö   #   ... is divisible ...
     ā    #   ... by its index
       P  #   take the product (all)

```
> 5 votes

# Answer
# Python 2, 68 bytes

```
lambda n:[`s`[:n]for s in 321654,381654729,123654][380712>>n*2&3::2]

```

Try it online!

Outputs a list a strings.

---

**71 bytes**

```
lambda n:[0,1,12,[123,321],0,0,[123654,321654],0,38165472,381654729][n]

```

Try it online!

Just a boring straight hardcode. Outputs a single number, or a list of two numbers, or 0 for no output.

None of the other methods I tried seemed likely to be shorter than this. For instance, one idea is to generate numbers as prefixes of a single number, generating like `123654/10**(6-i)`.

An object method gives the same length. Unfortunately we can't use the much shorter `.pop` because it make the function not reusable because it modifies the list with each call.

```
[0,1,12,[123,321],0,0,[123654,321654],0,38165472,381654729].__getitem__

```

Try it online!

Aliasing the longest constant also gives the same length:

```
lambda n,c=381654729:[0,1,12,[123,321],0,0,[123654,321654],0,c/10,c][n]

```

Try it online!
> 5 votes

# Answer
# , 42 37 bytes

Calculates the numbers.

```
0({:#~0=[:+/#\|])@|:i.@!10&#.\@A.1+i.

```

Try it online!

* `1+i.` 1…n
* `i.@!…@A.` all possible permutations of 1…n
* `10&#.\` convert every prefix of a permutation to a number
* `0(…)@|:` transpose the matrix and …
* `#\|]` 1…n mod the prefixes, e.g. `1 2 3 | 1 12 123`
* `0=[:+/` sum the result; is it 0?
* `{:#~` then take the last prefix of the permutation (the permutation itself)
> 4 votes

# Answer
# Scala, ~~81~~ 80 bytes

```
| =>1.to(|).mkString.permutations.filter{i=>1 to|forall(r=>i.take(r).toInt%r<1)}

```

Try it in Scastie

Explanation:

```
| =>                          //n, the input
  1.to(|)                     //Range to n
    .mkString                 //Turn it into a string
    .permutations             //Get all permutations
    .filter{ i =>             //Filter them
      1 to | forall(r =>      //For every r from 1 to n
        i.take(r).toInt       //The number made from i's first r digits
          % r < 1             //Should be divisible by r
      )
    }

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 78 bytes

```
(f=FromDigits)/@Select[Permutations@Range[s=#],f@#[[;;k]]~Mod~k~Sum~{k,s}<1&]&

```

Try it online!

-8 bytes from @att
> 2 votes

# Answer
# Jelly,  ~~11~~  10 bytes

-1 thanks to caird coinheringaahing!

This is a naive method, there could be a more terse one.

```
Œ!JḍḌƤẠƲƇḌ

```

A monadic Link accepting \\$n\\$ which yields `0` if none are found or a list of valid numbers.

**Try it online!** Or see the test-suite.

### How?

```
Œ!JḍḌƤẠƲƇḌ - Link: n
Œ!         - all permutations of [1..n]
        Ƈ  - filter keep those (p for p in Œ!) for which:
       Ʋ   -   last four links as a monad f(p):
  J        -     range of length = [1..n]
     Ƥ     -     apply to prefixes (of p):
    Ḍ      -       un-decimal
   ḍ       -     divides? (vectorises)
      Ạ    -     all truthy?
         Ḍ - un-decimal

```
> 2 votes

# Answer
# C (gcc) -lm, ~~67~~ ~~101~~ 96 bytes

Added 34 bytes to fix a bug kindly pointed out by xnor.
Saved 5 bytes thanks to ceilingcat!!!

```
f(n){write(1,"321654",n-3&&n-6?0:n);n=n<4?123/exp10(3-n):n>7?381654729/exp10(9-n):n-6?0:123654;}

```

Try it online!

Total lookup based solution. If there are two solutions: outputs one to `stdout`, and returns the other. If there's only one answer it's simply returned. Returns \\$0\\$ if there's no answer.

## Bonus round for brownie points

# C (gcc), ~~232~~ 212 bytes

Saved a whopping 20 bytes thanks to ceilingcat!!!

```
p;m;j;char b[9],c[9];d;i;f(n){for(d=0,i=n;i;)d+=9*d+i--;for(sprintf(c,"%d",d);d/++i;)if(sprintf(b,"%d",i),qsort(b,n,1,L"\xf06be0f\xd02917beǃ"),!strcmp(b,c)){for(p=0,m=n,j=i;j;j/=10)p|=j%m--;p||printf("%d ",i);}}

```

Try it online!

Computes the correct numbers through calculation and outputs them to `stdout`. Outputs nothing if there's no answer. Times out on TIO for \\$n=9\\$ but does all of them in `3m36.499s` on my laptop.
> 2 votes

# Answer
# Charcoal, 25 bytes

```
ＮθΦＥＸχθＩι⬤…·¹θ›№ιＩλ﹪Ｉ…ιλλ

```

Try it online! Link is to verbose version of code. Too slow for `n>5` on TIO. Explanation:

```
Ｎθ

```

Input `n`.

```
ΦＥＸχθＩι

```

List all integers `i` up to `10ⁿ`, such that...

```
⬤…·¹θ

```

... for each integer `l` from `1` to `n`...

```
›№ιＩλ﹪Ｉ…ιλλ

```

`l` is a digit of `i` and the `l`-character prefix of `i` is divisible by `l`.

Slightly faster 28-byte version:

```
ＮθΦＥＸ⊕θθ⍘ι⊕θ⬤…·¹θ›№ιＩλ﹪Ｉ…ιλλ

```

Try it online! Link is to verbose version of code. Explanation: Generates the digits in base `n+1` instead of base `10`, thus making it possible to complete `n=6` on TIO.

Fastest 29-byte version using a compressed lookup table:

```
§⪪”)‴a3HSＧS⸿Dπ¬Z⦄O<ε≔<πUθ8”0Ｎ

```

Try it online! Link is to verbose version of code.
> 2 votes

# Answer
# Husk, 15 bytes

```
mdföΛIṠz¦ŀmdḣPḣ

```

Try it online!

Almost the same as the other question, except with parameters.
> 2 votes

# Answer
# Perl 5, 64 bytes

```
sub{grep"@_"==y///c,1,12,123,321,123654,321654,$x=38165472,$x.9}

```

Try it online!
> 1 votes

# Answer
# JavaScript (V8), 97 bytes

A recursive function that computes and prints the matching integers.

```
f=(n,s='987654321'.slice(-n),d,p)=>p%d?0:s?[...s].map(v=>f(n,s.replace(v,''),-~d,[p]+v)):print(p)

```

Try it online!

---

# JavaScript (ES6), 59 bytes

Hard-coding is obviously shorter.

```
n=>[,1,12,[321,123],,,[321654,123654],,q=38165472,q+[9]][n]

```

Try it online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 71 bytes

```
f[s_:0,l_:0]=0!=##2&&l∣s&&If[l<#,##~f[10s+i,l+1]~i~Do~{i,#},Print@s]&

```

Try it online!

Call as `f[][n]`. Prints the results.
> 1 votes

# Answer
# Stax, 13 bytes

```
║è[⌐•^∩╖[ª╫√°

```

Run and debug it

Same brute force algorithm. Nothing clever.
> 1 votes

# Answer
# Excel, 64 bytes

```
=CHOOSE(A1,1,12,"123,321",,,"123654,321654",,38165472,381654729)

```

Input is in `A1`. Hard-coded answer is shorter than calculation would be.
> 0 votes

---
Tags: code-golf, number, integer, division
---


title: You are the Host of the Olympics!

text:
# Question
Title: You are the Host of the Olympics!
You host the Olympic Games, and need to build a fantastic pool for the sake of the occasion, but the supervisors often change their mind regarding the dimensions, and need a quick way to rebuild it with the requested size!

---

Given two integers, `L` and `x`, your task is to build a swimming pool of length `L` and `x` lanes.

# How is a pool built?

* It contains an inner square, whose horizontal walls are made of `L` consecutive dashes(`-`) , and whose vertical walls are made out of `3x - 1` bars (`|`). Additionally, 4 `+` signs lie in each corner. Let's have an example (`L = 10, x = 2`):

```
+----------+
|          |
|          |
|          |
|          |
|          |
+----------+

```
* *Each lane* has a width of 2 vertical units. The inner square is filled with `x-1` lane separators, consisting of `L` horizontally consecutive `:` symbols. After putting the lane separators, our pool should look like this:

```
+----------+
|          |
|          |
|::::::::::|
|          |
|          |
+----------+

```
* A pool also contains a *padding* (an outer square), whose horizontal walls are (L+4) `-`s and whose vertical walls are (3x + 1) `|`s, that surrounds the inner square:

```
+--------------+
| +----------+ |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| +----------+ |
+--------------+

```

And that's our olympic-sized\** swimming pool!

---

# Specs:

* For design and functionality purposes, you are guaranteed that `100 ≥ L ≥ 10` and `15 ≥ x ≥ 2`.
* The output must be exactly as shown. Outputting a "vertically-built"\* pool is disallowed.
* Trailing and leading spaces are allowed.
* You may take input and provide output through any standard method.
* Default Loopholes apply.

---

# Examples / Test cases:

```
L = 20, x = 3

+------------------------+
| +--------------------+ |
| |                    | |
| |                    | |
| |::::::::::::::::::::| |
| |                    | |
| |                    | |
| |::::::::::::::::::::| |
| |                    | |
| |                    | |
| +--------------------+ |
+------------------------+

L = 50, x = 5:

+------------------------------------------------------+
| +--------------------------------------------------+ |
| |                                                  | |
| |                                                  | |
| |::::::::::::::::::::::::::::::::::::::::::::::::::| |
| |                                                  | |
| |                                                  | |
| |::::::::::::::::::::::::::::::::::::::::::::::::::| |
| |                                                  | |
| |                                                  | |
| |::::::::::::::::::::::::::::::::::::::::::::::::::| |
| |                                                  | |
| |                                                  | |
| |::::::::::::::::::::::::::::::::::::::::::::::::::| |
| |                                                  | |
| |                                                  | |
| +--------------------------------------------------+ |
+------------------------------------------------------+

L = 10, x =15

+--------------+
| +----------+ |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| |::::::::::| |
| |          | |
| |          | |
| +----------+ |
+--------------+

```

This is , so the shortest code *in bytes* wins!

\*The water could flow out if it is built vertically :P

\**Yes, I am aware that the more the lanes are and the shorter the pool is, the less the drawing looks like a pool!

# Answer
# Charcoal, 32 bytes

```
ＮθＮη↓Ｅθ×η:  Ｂ⁺θ²⁺×³η¹↖←Ｂ⁺θ⁶⁺×³η³

```

Try it online!

-4 thanks to Neil.

AST:

```
Program
├Ｎ: Input Number
│└θ: Identifier θ
├Ｎ: Input Number
│└η: Identifier η
├Print
│├↓: Down
│└Ｅ: Map
│ ├θ: Identifier θ
│ └×: Product
│  ├η: Identifier η
│  └':  ': String ':  '
├Ｂ: Box
│├⁺: Sum
││├θ: Identifier θ
││└2: Number 2
│└⁺: Sum
│ ├×: Product
│ │├3: Number 3
│ │└η: Identifier η
│ └1: Number 1
├Move
│└↖: Up Left
├Move
│└←: Left
└Ｂ: Box
 ├⁺: Sum
 │├θ: Identifier θ
 │└6: Number 6
 └⁺: Sum
  ├×: Product
  │├3: Number 3
  │└η: Identifier η
  └3: Number 3

```
> 13 votes

# Answer
# Charcoal, 40 39 37 bytes

```
ＮθＮηＢ⁺θ⁶⁺×³η³↘→Ｂ⁺θ²⁺×³η¹→Ｆ⁻η¹«Ｍ³↓Ｐ×:θ

```

Try it online!

I know Neil already has a Charcoal answer of around the same length, but I took a bit of a different approach so I figured I may as well also post mine.

## Explanation

```
ＮθＮηＢ⁺θ⁶⁺×³η³↘→Ｂ⁺θ²⁺×³η¹→Ｆ⁻η¹«Ｍ³↓Ｐ×:θ
ＮθＮη                                         take the two inputs as numbers in θ and η
      Ｂ⁺θ⁶⁺×³η³                               draw a rectangle θ + 6 by 3η + 3
                                               (characters default to |, - and +)
                ↘→                             move the cursor down one and right two
                   Ｂ⁺θ²⁺×³η¹                  draw a rectangle θ + 2 by 3η + 1
                             Ｆ⁻η¹«            for ι (unused) from 0 up until η - 1:
                                   Ｍ³↓            move the cursor down by 3
                                       Ｐ×:θ       print θ :s without moving the cursor
                                               [implicit end of for]

```
> 12 votes

# Answer
# Charcoal, ~~40~~ ~~38~~ ~~36~~ 31 bytes

```
Ａ⁺²ＮθＡ⁺¹×³ＮηＵＯθη:¶¶Ｂθη↖←Ｂ⁺⁴θ⁺²η

```

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

```
Ａ⁺²Ｎθ       Assign(Plus(2, InputNumber()), q);

```

Charcoal's drawing primitives use the overall character count including `+`s, however the input is just the number of `-`s, so we need to add 2 to obtain the width of the inner wall.

```
Ａ⁺¹×³Ｎη     Assign(Plus(1, Times(3, InputNumber())), h);

```

Calculate the height of the inner wall, again, inclusive of the bottom row, so three per lane plus one.

```
ＵＯθη:¶¶     Oblong(q, h, ":\n\n");

```

Draw the lanes. This is simply a rectangle filled with `:`s vertically separated by two blank lines (the pilcrows represent newline characters).

```
Ｂθη         Box(q, h);

```

The `Rectangle` command is exactly what we need to draw the inner wall. Edit: `Box` allows you to omit its third parameter, saving me 2 bytes.

```
↖           Move(:UpLeft);
←           Move(:Left);
Ｂ⁺⁴θ⁺²η     Box(Plus(4, q), Plus(2, h));

```

And again to draw the outer wall, except slightly wider and taller, and centred on the inner wall.
> 11 votes

# Answer
# JavaScript (ES6), ~~137~~ 124 bytes

Golfed it down a bit on my phone, more to follow.

```
x=>y=>`+--0--+
| +0+ |
${((a=`| |1| |
`)+a+`| |2| |
`).repeat(y-1)+a+a}| +0+ |
+--0--+`.replace(/\d/g,n=>"- :"[n].repeat(x))

```

---

## Try it

```
f=
x=>y=>`+--0--+
| +0+ |
${((a=`| |1| |
`)+a+`| |2| |
`).repeat(y-1)+a+a}| +0+ |
+--0--+`.replace(/\d/g,n=>"- :"[n].repeat(x))
oninput=_=>o.innerText=f(+i.value)(+j.value);o.innerText=f(i.value=50)(j.value=5)
```

```
input{font-family:sans-serif;margin:0 5px 0 0;width:50px;}
```

```
<label for=i>L: </label><input id=i type=number><label for=j>x: </label><input id=j type=number><pre id=o>
```
> 8 votes

# Answer
# T-SQL, ~~284~~ 281 bytes

```
DECLARE @ INT,@x INT,@S VARCHAR(MAX)='+--d--+b| +d+ |b'SELECT @=L,@x=x FROM t
P:SET @S+='| |s| |b| |s| |b| |c| |b'SET @x-=1IF @x>0GOTO P
PRINT REPLACE(REPLACE(REPLACE(REPLACE(LEFT(@S,LEN(@S)-6)+'+d+ |b+--d--+','d',REPLICATE('-',@)),'b',CHAR(13)),'s',SPACE(@)),'c',REPLICATE(':',@))

```

Input is taken from INT columns **L** and **x** in preexisting table **t**, per our allowed input methods.

Basically I'm creating a long string with letters representing the repeated characters (d=dashes, s=spaces, c=colons, b=line break), then REPLACE them all at the end with the appropriate fillers.

Formatted:

```
DECLARE @ INT,@x INT,@S VARCHAR(MAX)='+--d--+b| +d+ |b'
SELECT @=L,@x=x FROM t
P:
    SET @S+='| |s| |b| |s| |b| |c| |b'
    SET @x-=1
IF @x>0 GOTO P
PRINT REPLACE(REPLACE(REPLACE(REPLACE( LEFT(@S,LEN(@S)-6)+'+d+ |b+--d--+'
     ,'d',REPLICATE('-',@))
     ,'b',CHAR(13))
     ,'s',SPACE(@))
     ,'c',REPLICATE(':',@))

```

Inside the loop I append 2 rows of blanks and 1 row of colons, then at the end I chop off that divider row and append the pool border before performing the replaces.

**EDIT**: Saved 3 bytes by switching `@` to the most-often used variable, and swapping initialization order.
> 8 votes

# Answer
# Python 2, ~~124~~ ~~120~~ 117 bytes

-2 bytes thanks to Hyper Neutrino

```
l,x=input()
o='+--%s--+\n| +%s+ |\n'%(('-'*l,)*2)
print o+'| |%s| |\n'*(x*3-1)%((' '*l,' '*l,':'*l)*x)[:-1]+o[-2::-1]

```

Try it online!
> 6 votes

# Answer
# Python 2, ~~128~~ 126 bytes

```
L,x=input()
k='+'+'-'*(L+4)+'+\n| +'+'-'*L+'+ |\n'
f=lambda k:'| |'+k*L+'| |\n'
print k+f(':').join([f(' ')*2]*x)[:-1]+k[::-1]

```

Try it online!

-2 bytes thanks to @Mr.Xcoder
> 4 votes

# Answer
# SOGL V0.12, ~~52~~ 51 bytes

```
:┌* +1Ο;@*┐1ΟG∙⁴++⁰
b3*Ie4+⁰b3*He⁰32žbH∫3*2+4;e :*ž

```

Try it Here!
Not bad considering that 20 bytes of this is a rectangle function, which charcoal has a built-in for.

Explanation:

```
Rectangle function: (example: on stack 4, 2)
:                   duplicate the top of stack (X pos)      [4, 2, 2]
 ┌*                 get that many "-"es                     [4, 2, "--"]
    +               push "+"                                [4, 2, "--", "+"]
     1Ο             wrap the dashes in pluses               [4, 2, "+--+"]
       ;            get the duplicated X position           [4, "+--+", 2]
        @*          get that many spaces                    [4, "+--+", "  "]
          ┐         push "|"                                [4, "+--+", "  ", "|"]
           1Ο       wrap the spaces with "|"                [4, "+--+", "|  |"]
             G      get the Y value ontop                   ["+--+", "|  |", 4]
              ∙     get an array with that many strings     ["+--+", ["|  |", "|  |", "|  |", "|  |"]]
               ⁴    duplicate the dashes wrapped in pluses  ["+--+", ["|  |", "|  |", "|  |", "|  |"], "+--+"]
                ++  add everything to one array             [["+--+", "|  |", "|  |", "|  |", "|  |", "+--+"]]
Main function: (example input: 2, 5)
b3*                              push variable B (input 1, Y length) multiplied by 3                     [6]
   I                             increase it                                                             [7]
    e4+                          push variable E (input 2, X length) + 4                                 [7, 9]
       ⁰                         execute the rectangle function [in X: E+4, Y: b*3+1]                    [["+---------+","|         |","|         |","|         |","|         |","|         |","|         |","|         |","+---------+"]]
        b3*                      push variable B * 3                                                     [["+---------+",..,"+---------+"], 6]
           H                     decrease it                                                             [["+---------+",..,"+---------+"], 5]
            e                    push variable E                                                         [["+---------+",..,"+---------+"], 5, 5]
             ⁰                   execute the rectangle function [on X: E, Y: B*3-1]                      [["+---------+",..,"+---------+"], ["+-----+","|     |","|     |","|     |","|     |","|     |","+-----+"]]
              32ž                at coordinates [3;2] (1-indexed) in the first rectangle put in the 2nd  [["+---------+",
                                                                                "| +-----+ |",
                                                                                "| |     | |",
                                                                                "| |     | |",
                                                                                "| |     | |",
                                                                                "| |     | |",
                                                                                "| |     | |",
                                                                                "| +-----+ |",
                                                                                "+---------+"]
                 bH∫             iterate over the numbers from 1 to B-1:                                 [[...], 1]
                    3*2+           push pop()*3+2                                                        [[...], 5]
                        4;         push 4 one below the stack                                            [[...], 4, 5]
                          e        push the variable E (X length)                                        [[...], 4, 5, 5]
                            :*     get that many colons                                                  [[...], 4, 5, ":::::"]
                              ž    insert [at coordinates [4; cIter*3+2] the colons]

```
> 4 votes

# Answer
# C# (.NET Core), 202 bytes

```
(L,x)=>{char p='+',n='\n',e=' ';string v="|",r="",s=p+new string('-',L+4)+p+n,q=v+e+p+new string('-',L)+p+e+v+n;r+=s+q;for(int i=0;i<3*x-1;)r+=v+e+v+new string(i++%3<2?e:':',L)+v+e+v+n;r+=q+s;return r;}

```

Try it online!
> 4 votes

# Answer
# PHP, 153 bytes

```
for(;$i-2<$z=3*$argv[2]+1;$i++)echo str_pad(strrev($r=["--+","+ |","| |"][!($b=$i>1&$i<$z)?$i&&$i<$z+1?1:0:2]),$argv[1]+3,"- :"[$b?$i%3!=1?1:2:0])."$r
";

```

Try it online!
> 3 votes

# Answer
# Python 2, 97 bytes

```
L,x=input()
for i in'01'+'223'*~-x+'2210':r=('+|||-   -+||'+L*'-- :')[int(i)::4];print r+r[2::-1]

```

Try it online!

---

# Python 2, 98 bytes

```
L,x=input()
s='+---| +-%s+-+---'%'|:'.join(['| '*5]*x)
while s:print s[:3]+s[3]*L+s[2::-1];s=s[4:]

```

Try it online!
> 3 votes

# Answer
# Charcoal, 36 bytes

```
ＮθＮηＦη«Ｍ³↑Ｐ×θ:»←Ｂ⁺θ²⁺×³η¹↖←Ｂ⁺θ⁶⁺×³η³

```

Try it online!

This is a more Charcoal-y algorithm than my other answer.
> 2 votes

# Answer
# C (gcc), 195 bytes

```
#define P printf
y;f(L,l){char s[L+1],t[L+1];memset(s,45,L);memset(t,58,L);t[L]=s[L]=0;P("+-%s-+\n|+%s+|\n",s,s);for(y=3*l;y-->1;y%3?P("||%*c||\n",L,32):P("||%s||\n",t));P("|+%s+|\n+-%s-+",s,s);}

```

Try it online!
> 2 votes

# Answer
# Perl 5, 124 + 1 (-a) = 125 bytes

```
say$o='+'.'-'x($l=pop@F),$t="----+
",$i="| $o+ |
",$e=($d="| |").$"x$l.$d,$/,$e;say$d.':'x$l."$d
$e
$e"for 2..$_;say$i,$o,$t

```

Try it online!
> 1 votes

# Answer
# APL (Dyalog Unicode), 72 bytes

```
{g' '∘,∘⌽∘⍉⍣4(g←{'+'@(⊂1 1)∘⌽∘⍉⍣4⊃(⍪∘⌽∘⍉)/'-|-|',⊂⍵})↑(¯1+3×⍵)⍺⍴⍺/'  :'}

```

Try it online!

A function that takes L on the left and x on the right.
> 0 votes

# Answer
# Haskell, 111 bytes

```
r=replicate
a?b=a++b++reverse a
l!x=unlines$map(?r l '-')["+--","| +"]?map("| |"?)(tail$concat$r x$r l<$>":  ")

```

Try it online!
> 0 votes

---
Tags: code-golf, string, ascii-art
---


title: Compute modular inverse

text:
# Question
Title: Compute modular inverse
Given two positive numbers \\$x\\$ and \\$n\\$ with \\$x\<2^n\\$, write the shortest possible function to compute \\$x^{-1} \mod 2^n\\$. In other words, find \\$y\\$ such that \\$xy=1 \mod 2^n\\$.

Your function must complete in a reasonable time for at least \\$n=64\\$, so exhaustive search will not work.

If the inverse does not exist, you must indicate that to the caller somehow (throw an exception, return a sentinel value, etc).

If you're wondering where to start, try the Extended Euclidean Algorithm.

# Answer
> 1 votes
## Python 95 89

`c` is your function. Returns 0 if there is no inverse (i.e. when x is even).

```
p=lambda x,y,m:y and p(x,y/2,m)**2*x**(y&1)%m or 1
c=lambda x,n:[0,p(x,2**n-1,2**n)][x%2]

```

# Answer
> 3 votes
# Python, 29 bytes

```
lambda x,n:pow(x,2**n-1,2**n)

```

This returns 0 for even *x*. It uses Euler’s theorem, with the observation that 2^*n* − 1 is divisible by 2^(*n* − 1) − 1, via Python’s builtin fast modular exponentiation. This is plenty fast enough for *n* up to 7000 or so, where it starts taking more than about a second.

# Answer
> 3 votes
# Python 3.8 (pre-release), 25 bytes

```
lambda a,b:pow(a,-1,2**b)

```

Try it online!

# Answer
> 2 votes
## Mathematica - 22

```
f=PowerMod[#,-1,2^#2]&

```

`f[x,n]` returns `y` with `x*y=1 mod 2^n`, otherwise `x is not invertible modulo 2^n`

# Answer
> 2 votes
## GolfScript (23 chars)

```
{:^((1${\.**2^?%}+*}:f;

```

The sentinel result for a non-existent inverse is `0`.

This is a simple application of Euler's theorem. \\$x^{\varphi(2^n)} \equiv 1 \pmod {2^n}\\$, so \\$x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}\\$

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is \\$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x\\$ and we have a choice of base case: either `k=1` with

```
{1\:^(@{\.**2^?%}+*}:f;

```

or `k=2` with

```
{:^((1${\.**2^?%}+*}:f;

```

---

I'm working on another approach, but the sentinel is more difficult.

The key observation is that we can build the inverse up bit by bit: if \\$xy \equiv 1 \pmod{2^{k-1}}\\$ then \\$xy \in \\{ 1, 1 + 2^{k-1} \\} \pmod{2^k}\\$, and if \\$x\\$ is odd we have \\$x(y + xy-1) \equiv 1 \pmod{2^k}\\$. (If you're not convinced, check the two cases separately). So we can start at any suitable base case and apply the transformation \\$y' = (x+1)y - 1\\$ a suitable number of times.

Since \\$0x \equiv 1 \pmod {2^0}\\$ we get, by induction

\\$x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}\\$

where the inverse is the sum of a geometric sequence. I've shown the derivation to avoid the rabbit-out-of-a-hat effect: given this expression, it's easy to see that (given that the bracketed value is an integer, which follows from its derivation as a sum of an integer sequence) the product on the left must be in the right equivalence class if \\$x+1\\$ is even.

That gives the 19-char function

```
{1$)1$?@/~)2@?%}:f;

```

which gives correct answers for inputs which have an inverse. However, it's not so simple when \\$x\\$ is even. One potentially interesting option I've found is to add `x&1` rather than `1`.

```
{1$.1&+1$?@/~)2@?%}:f;

```

This seems to give sentinel values of either \\$0\\$ or \\$2^{n-1}\\$, but I haven't yet proved that.

Taking that one step further, we can ensure a sentinel of \\$0\\$ for even numbers by changing the expression \\$1 - (x+1)^n\\$ into \\$1 - 1^n\\$:

```
{1$.1&*)1$?@/~)2@?%}:f;

```

That ties with the direct application of Euler's theorem for code length, but is going to have worse performance for large \\$n\\$. If we take the arguments the other way round, as `n x f`, we can save one character and get to **22 chars**:

```
{..1&*)2$?\/~)2@?%}:f;

```

# Answer
> 1 votes
## Ruby - 88 characters

Use the function `f`.

```
def e a,b;a%b==0?[0,1]:(x,y=e(b,a%b);[y,x-(y*(a/b))])end
def f x,n;e(x,2**n)[0]*(x%2)end

```

Simply the recursive function from the linked wiki page, returns 0 on error.

# Answer
> 1 votes
# Haskell, 42 bytes

```
_!1=1
x!n|r<-x!div(n+1)2=(2-r*x)*r`mod`2^n

```

Using an algorithm based on Hensel’s lemma that doubles the number of digits in every iteration, this runs in under a second for *n* up to about 30 *million*!

# Answer
> 1 votes
# Pyth, 9 bytes

```
.^Et^2Q^2

```

Try it here!

Takes input in reverse order. Or, 9 bytes too: `.^EtK^2QK`.

# Explanation

```
.^Et^2Q^2  - Full program.

.^         - Pow function. The same in Python (pow).
  E        - The second input.
    ^2Q    - And 2 ^ first input.
   t       - Decremented.
       ^2  - And 2 ^ first input again.

```

# Answer
> 1 votes
# Jelly, 5 bytes

```
2*æi@

```

Try it online!

Takes input with \\$n\\$ first and \\$x\\$ second, returns \\$0\\$ if no such inverse exists. The Footer in the TIO link reverses the input for you and formats the test cases.

## How it works

```
2*æi@ - Main link. Takes n on the left and x on the right
2*    - Yield 2*n
  æi@ - Modular inverse of x, modulo 2*n, or if none exists, 0.

```

# Answer
> 0 votes
# GAP, 39 bytes

```
f:=function(x,n)return 1/x mod 2^n;end;

```

`f(x,n)` returns the inverse of `x` modulo `2^n` and gives an error message

```
Error, ModRat: for <r>/<s> mod <n>, <s>/gcd(<r>,<s>) and <n> must be coprime

```

if no inverse exists.

# Answer
> 0 votes
# GolfScript, 10 9 bytes

```
2\?:q(?q%

```

Try it online!

A port of Mr. XCoder's solution, to GS. Stack manipulation is a little messy, could probably be done with a little tomfoolery. Takes in input as X N.

V 1.1 : Improved stack manip, it sucks a lot less now.

```
2\?:q(?q% #Multiplicative Inverse
2\        #Move "2" to the second pos on the stack. X 2 N
  ?       #Exponentiate. X 2^N
   :q     #Remember, q is 2^N.
     (    #Decrement. X 2^N-1
      ?   #Exponentiate. X^(2^N-1)
       q? #Mod by 2^N.

# X^([2^N] -1) % 2^N is the multiplicative inverse, since
# X^([2^N] -1)*X = X^(2^N)
# which is 1 mod 2^N if X and 2^N are coprime.

```

If there is no M.I., it will return 0.

# Answer
> 0 votes
# Python 3, ~~77~~ 57 bytes

```
f=lambda x,n,b=1,i=1:n and f(x,n-1,b-(b&i)*~-x,i+i)or b%i

```

Outgolfed all you snek users (except for the `pow(x, -1, 2**n)` cheapshots) with nothing but pure algorithm.

Try it online! (Only uses Python 3.8 for comparison against `pow(a,-1,2**n)`)

Ungolfed version:

```
def func(value, shift, acc = 1, mask = 1):
    if value != 0:
        return func(value, shift - 1, acc - (acc & mask) * (value - 1), mask << 1)
    else:
        return acc & (mask - 1)

```

Or, as a loop with size hacks removed:

```
def func(value, exponent):
    value -= 1
    acc = 1
    for i in range(exponent):
        if acc & (1 << i):
            acc -= value << i
    return acc & ((1 << i) - 1)

```

## Explanation

The function is a lambda called `f`. It takes two positive integers, and returns either the multiplicative modular inverse or zero.

You may be wondering what the heck is going on. This uses a different, faster, and smaller algorithm for modular inverse for powers of 2 instead of the Euclidian approach.

I'm not going to go too far into the details of *why* it works, as it is really complex and explained better by others. Translation: even I don't fully understand it.

This set of algorithms is explained here on algassert with a related algorithm explained here on Crypto SE with some interesting papers linked.

This algorithm actually uses no true multiplication (just shifts), the multiplication is just a shortcut for size.

This naturally returns `0` for even numbers, as the *odd* subtraction (we start with `x - 1`) causes a chain reaction of trailing with `0b0`, which, when masked off, turns the result to zero. No need for a manual sentinel.

```
0000 0001 - 0000 1101 -> 1111 0010
1111 0010 - 0001 1010 -> 1110 0000

```

---
Tags: code-golf, math, number-theory
---


title: Make a number palindrome

text:
# Question
Title: Make a number palindrome
Write a function that takes a number as an argument and makes it a palindrome by appending minimum number of digits. The number will be at max of 100 digits.

```
Sample Inputs
12
122
232
2323
1012121
Sample Outputs
121
1221
232
23232
101212101

```

# Answer
## J, 50, 32 26 characters!

```
f=:{.@(,"1(-:|.)\.#|.@}:\)

```

eg

```
f '12'
121
f '232'
232
f '2323'
23232
f '1012121'
101212101

```

### How it works (by example)

```
y =: '1012121'

[\.y   NB. Sub lists of y
1012121
012121
12121
2121
121
21
1

|.\. y  NB> Reverses of sub lists of y
1212101
121210
12121
1212
121
12
1

([\. y) -:"1 (|. \. y) NB. Which of them are equal? (those are palindromes)
                       NB. ( -:"1 ) checks equality item by item
0 0 1 0 1 0 1

(-:  |.)\. y NB. Shortcut of the above
0 0 1 0 1 0 1

(0 0 1 0 1 0 1) # }:\y NB. Choose (#) the palindrome prefixes (\)
10
1012
101212

y, |.'10'   NB. Reverse and append the first prefix.
101212101

```
> 4 votes

# Answer
## Perl, 32 chars

```
s/((.)(?1)\2|.?)$/$&.reverse$`/e

```

Needs Perl 5.10 or later for regex features, but no special command-line switch.

Sample use:

```
$ perl -pe 's/((.)(?1)\2|.?)$/$&.reverse$`/e' << EOT
> 12
> 232
> 2323
> 1012121
> EOT
121
232
23232
101212101

```

Uses Perl 5.10's recursive regex extensions to match the longest trailing palindrome as such:

```
m/
    (      # paren 1 - a palindrome is either:
      (.)  # paren 2 - a character
      (?1) # a palindrome as defined in paren 1
      \2   # the same character as in paren 2
    |        # or:
      .?   # a 0- or 1-character string
    )
    $      # at end of string
/x

```

It then replaces it with itself (`$&`) and appends whatever the string started with (`$``), reversed.
> 10 votes

# Answer
# Brachylog 2, 8 bytes, language postdates challenge

```
ẹ;AcB↔Bc

```

Try it online! The question asks for a function, so I provided one; the TIO link takes an argument that runs a function like a full program.

## Explanation

```
ẹ;AcB↔Bc
ẹ          Split {the input} into digits
 ;Ac       Append {the shortest possible} list
    B↔B    to produce a palindrome
       c   then concatenate the resulting list of digits back into a number

```
> 5 votes

# Answer
## Python, 88 chars

```
def f(x):
 x,y=list(str(x)),[]
 while x!=x[::-1]:y+=x.pop(0)
 return''.join(y+x+y[::-1])

```
> 3 votes

# Answer
## Python (101 96)

**edit:** Shortened based on @gnibbler's solution

```
def p(n):s=str(n);r=s[::-1];l=len(s);return[int(s+r[l-i:])for i in range(l)if s[i:]==r[:l-i]][0]

```

Original:

```
def p(n):
 s=str(n);r=s[::-1];l=len(s)
 for i in range(l):
  if s[i:]==r[:l-i]:return int(s+r[l-i:])

```
> 2 votes

# Answer
## Python - 98 chars

Based on Hoa's answer :)

```
def p(n):s=str(n);r=s[::-1];l=len(s);return next(int(s+r[l-i:])for i in range(l)if s[i:]==r[:l-i])

```
> 1 votes

# Answer
## Golfscript - 32 chars

```
{`:s-1%:r,,{s<r+..-1%=*}%{}?~}:f

```
> 1 votes

# Answer
## Haskell, 85

Using the same algorithm as most everyone else:

```
import List
r=reverse
f s=s++(r.snd.head.filter g.zip(tails s)$inits s)
g(s,_)=s==r s

```

Examples from problem description:

```
*Main> map (f.show) [12,232,2323,1012121]
["121","232","23232","101212101"]

```
> 1 votes

# Answer
## Ruby 1.9, 72 chars

```
f=->x{x=x.to_s.split'';99.times{|i|x.insert~i,x[i]if x!=x.reverse};x*''}

```
> 1 votes

# Answer
### JavaScript (ES6), ~~145~~ 126 chars

```
 p=a=>{S=x=>x.split``.reverse();for(s=String(a),i=0;i<s.length;i++)if(x=s+S(s.substring(0,i)).join``,x==S(x).join``)return x}

```

Commented:

```
function palindrome(n){
  s = String(n);
  for(i=0;i<s.length;i++)
  {
    x=s+s.substring(0,i).split("").reverse().join("") //take first n characters, reverse and append to the end
    if(x==x.split("").reverse().join("")) //is the number a palindrome?
      return x;
  }
}

```
> 1 votes

# Answer
# Ruby, 70 bytes

```
f=->x{x=x.to_s.chars;99.times{|i|x.insert~i,x[i]if x!=x.reverse};x*''}

```

Try it online!

Based on YOU'S answer, with chars instead of .split'' to gain 2 chars. And i'm sure there's way to squeeze just a bit more \>\<
> 1 votes

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

*-18 bytes thanks to @Razetime.*

```
ηí«.ΔÂQ

```

Try it online!

```
ηí«.ΔÂQ  # full program
   .Δ    # find first element in...
  «      # joined...
 í       # reversed...
η        # prefixes of...
         # implicit input...
   .Δ    # where...
      Q  # it's equal to...
     Â   # itself reversed
         # implicit output

```
> 1 votes

# Answer
# Java, 174 bytes

```
x->{Function<String,String>r=t->new StringBuilder(t).reverse().toString();String y=r.apply(x),z=x;int m=x.length();while(!z.equals(r.apply(z)))z=x+y.substring(--m);return z;}

```

Ungolfed:

```
x -> {
        Function<String, String> r = t -> new StringBuilder(t).reverse().toString();
        String y = r.apply(x), z=x;
        int m = x.length();
        while (!z.equals(r.apply(z))) z = x+y.substring(--m);
        return z;
    }

```

I have a feeling it could be a lot tighter but it's not immediately obvious to me how. The Function eats up a lot of space but I needed it in two places.

This works for any string, not just numbers, and it can be any length.
> 0 votes

# Answer
# PHP, 64 Bytes

```
for(;strrev($p=$argn.strrev(substr($argn,0,$i++)))!=$p;);echo$p;

```

Try it online!
> 0 votes

# Answer
# Jelly, 11 bytes

```
D;ⱮUƤ$ŒḂƇḢḌ

```

Try it online!

## How it works

```
D;ⱮUƤ$ŒḂƇḢḌ - Main link. Takes n on the left
D           - Digits of n
     $      - To the digits of n:
    Ƥ       -   Yield the prefixes
   U        -   Reverse
 ;Ɱ         -   Concatenate with the digits
      ŒḂƇ   - Keep the palindromes
         Ḣ  - Take the first (i.e. the shortest)
          Ḍ - Convert from digits

```
> 0 votes

---
Tags: code-golf, optimized-output, palindrome
---


title: Numbers, Sums, Products

text:
# Question
Title: Numbers, Sums, Products
Given a 20×20 grid of non-negative integers, find a 3×3 sub-grid where the product of the sums of the individual lines hits the maximum. Spoken in formulas:

Given the 3×3 sub-grid

$$\mathfrak{U} = \left(\begin{matrix} x\_{11} & x\_{12} & x\_{13} \\ x\_{21} & x\_{22} & x\_{23} \\ x\_{31} & x\_{32} & x\_{33} \end{matrix}\right)$$

the function to maximize is

$$\begin{align} f(\mathfrak{U}) & = \left(\begin{matrix} \underbrace{(x\_{11} + x\_{12} + x\_{13})}\_\cdot \\ \overbrace{\underbrace{(x\_{21} + x\_{22} + x\_{23})}}\_\cdot \\ \overbrace{(x\_{31} + x\_{32} + x\_{33})} \\ \end{matrix}\right) \\ & = (x\_{11} + x\_{12} + x\_{13}) \cdot (x\_{21} + x\_{22} + x\_{23}) \cdot (x\_{31} + x\_{32} + x\_{33}) \end{align}$$

Per line the sum is calculated and the individual sums are then multiplied.

An example (only 5×5):

$$\begin{matrix} 40 & 30 & 42 & 22 & 74 \\ 294 & 97 & \color{red} {35} & \color{red}{272} & \color{red}{167} \\ 52 & 8 & \color{red}{163} & \color{red}{270} & \color{red}{242} \\ 247 & 130 & \color{red}{216} & \color{red} {68} & \color{red}{266} \\ 283 & 245 & 164 & 53 & 148 \\ \end{matrix}$$

The part highlighted in red is the part where the value of the function \\$f(\mathfrak{U})\\$ is largest for the entire grid:

> \\$(35 + 272 + 167) ⋅ (163 + 270 + 242) ⋅ (216 + 68 + 266) = 175972500\\$

**Input**

Input is given on standard input and consists of 20 lines, each containing 20 numbers, separated by a space character (U+0020). The numbers are small enough that a 32-bit signed integer is sufficient to compute the result.

You may assume input to be given redirected from a file.

**Output**

Output is the result of the function \\$f(\mathfrak{U})\\$ for the 3×3 sub-grid that gives the largest result. In above example this would have been \\$175972500\\$.

**Sample input 1**

```
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

```

**Sample output 1**

```
3375

```

**Sample input 2**

```
40 30 42 222 74 265 93 209 115 274 139 177 7 274 12 15 103 36 236 91
294 97 35 272 167 126 18 262 292 48 8 296 85 93 245 4 4 240 276 153
52 8 163 270 242 224 142 72 99 240 199 26 224 198 96 242 295 70 56 247
247 130 216 68 266 142 93 214 30 8 12 163 59 84 40 287 233 65 30 242
283 245 164 53 148 282 73 186 296 3 9 233 184 30 205 221 92 96 5 101
132 228 43 91 228 37 266 140 159 109 10 230 40 114 264 3 266 164 219 283
70 207 218 28 299 78 279 30 179 118 196 138 61 229 110 55 203 73 124 112
16 232 28 187 292 78 194 70 65 203 255 227 176 21 32 225 11 15 92 151
58 237 261 41 213 171 170 111 4 209 99 194 40 108 267 137 179 31 35 221
184 209 264 275 163 268 261 40 198 185 45 188 280 273 54 79 270 286 273 121
208 83 66 156 104 62 188 68 53 194 46 279 280 170 266 148 272 285 178 245
210 130 213 118 165 210 213 66 54 189 166 193 57 213 14 101 143 109 172 101
80 193 287 4 140 65 208 111 8 206 107 285 109 29 211 78 170 247 290 193
148 123 15 164 28 153 222 67 156 165 6 163 114 77 165 17 143 209 278 100
3 102 58 148 82 181 84 29 2 236 231 195 118 278 252 257 179 123 276 287
143 141 254 142 200 243 171 32 164 195 235 260 269 191 190 46 65 166 82 146
69 194 65 220 234 110 45 135 125 208 138 20 233 291 256 162 148 216 247 138
10 53 164 107 2 270 226 227 88 206 193 13 41 130 218 249 76 35 207 91
199 36 207 256 58 215 28 277 234 29 198 148 219 244 136 16 30 258 219 264
183 118 48 218 15 125 279 103 73 8 86 113 9 157 239 273 146 208 50 86

```

**Sample output 2**

```
328536000

```

**Sample input 3**

```
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

```

**Sample output 3**

```
185193

```

**Sample input 4**

```
242 248 292 60 9 45 94 97 294 202 219 118 115 243 207 81 288 289 241 232
236 225 205 227 242 85 139 63 5 162 170 121 208 133 22 235 125 288 209 270
31 182 108 170 88 268 297 66 249 158 285 157 267 117 150 18 44 66 117 223
205 32 93 132 33 99 209 282 222 272 255 1 80 270 202 54 117 35 139 273
87 74 113 146 177 14 154 92 282 4 192 60 171 286 66 299 89 276 138 289
60 16 143 277 202 284 77 296 215 96 200 10 226 143 136 131 218 246 254 20
244 118 299 218 81 195 129 93 205 202 264 141 196 150 214 72 231 136 243 192
236 157 176 187 104 182 134 29 151 234 81 143 22 119 45 241 17 225 197 7
156 284 92 13 131 60 113 77 228 65 200 83 3 63 83 88 241 113 115 198
62 101 242 270 121 122 119 78 105 273 55 7 239 236 37 252 66 164 56 44
70 57 100 87 34 298 140 259 36 257 1 204 110 299 245 56 43 121 192 10
240 36 272 255 10 194 143 66 27 131 22 78 57 71 128 5 1 155 236 122
281 160 42 147 272 151 196 240 291 280 209 245 271 46 103 35 85 145 78 140
155 74 232 205 235 223 147 39 171 240 56 187 184 70 28 81 293 125 283 159
297 203 75 46 221 77 106 12 268 94 220 156 78 97 266 208 228 137 212 49
4 157 69 51 225 23 61 202 19 23 41 260 161 218 142 251 299 187 283 158
118 136 71 77 21 199 110 87 103 120 153 157 213 234 155 141 135 24 120 199
16 204 292 245 54 260 294 159 254 15 209 41 154 54 231 167 87 291 31 26
212 274 99 199 170 184 47 227 64 2 117 275 67 84 143 214 143 125 24 61
205 250 133 88 210 112 4 160 3 287 54 143 293 94 287 42 105 94 76 169

```

**Sample output 4**

```
311042813

```

For the interested, the lengths of the submissions we got in our contest:

> 120 – AWK
> 124 – C
> 133 – Haskell
> 174 – C
> 270 – VB.NET

And our own (unranked) solutions:

> 55 – Golfscript
> 118 – Ruby
> 192 – PowerShell

# Answer
## J, 38

```
":@(>./@,@(3*/\3+/\"1".;._2))&.stdin''

```

Sample use:

```
$ jconsole nsp.ijs <g1
3375
$ jconsole nsp.ijs <g2
328536000
$ jconsole nsp.ijs <g3
185193

```

Rough explanations:

* `".;._2` converts raw input to matrix, `":` converts the result to raw output
* `3+/\"1` sums column-wise, 3 by 3
* `3*/\` multiplies row-wise, 3 by 3
* `,` flattens the result
* `>./` extracts the maximum
* `&.stdin''` makes a filter out of it
> 5 votes

# Answer
# Python - 146 characters

```
g=[map(int,raw_input().split(' '))for i in' '*20]
r=range(18)
print max(reduce(int.__mul__,[sum(v[j:j+3])for v in g[i:i+3]])for j in r for i in r)

```
> 6 votes

# Answer
# Java, 299 Chars

```
    class M{public static void main(String[]a){java.util.Scanner s=new java.util.Scanner(System.in);int i,j,k,p,m,t=20,x[][]=new int[t][t];for(i=m=0;i<t*t;i++)x[i/t][i%t]=s.nextInt();for(i=0;i<18;i++)for(j=0;j<18;j++,m=p>m?p:m)for(p=1,k=i;k<i+3;k++)p*=x[k][j]+x[k][j+1]+x[k][j+2];System.out.print(m);}}

```
> 3 votes

# Answer
# C#, ~~324~~ ~~321~~ 308 chars

```
using System;using System.Linq;class X{static void Main(){int m=0,v,x=0,y;Func<int[],int>f=t=>t[x]+t[x+1]+t[x+2];var a=Console.In.ReadToEnd().Trim().Split('\n').Select(l=>l.Split(' ').Select(int.Parse).ToArray()).ToList();for(;x<18;x++)for(y=0;y<18;m=m>v?m:v)v=f(a[y])*f(a[++y])*f(a[y+1]);Console.Write(m);}}

```

## Readable:

```
using System;
using System.Linq;
class X
{
    static void Main()
    {
        int m = 0, v, x = 0, y;
        Func<int[], int> f = t => t[x] + t[x + 1] + t[x + 2];
        var a = Console.In.ReadToEnd().Trim().Split('\n').Select(l =>
            l.Split(' ').Select(int.Parse).ToArray()).ToList();
        for (; x < 18; x++)
            for (y = 0; y < 18; m = m > v ? m : v)
                v = f(a[y]) * f(a[++y]) * f(a[y + 1]);
        Console.Write(m);
    }
}

```

14 characters could be shaved off by removing both calls to `.Trim()` if you can guarantee that the input will only use `\n` (no `\r`) and there is no newline after the last row of numbers.

### Edits

* **(333 → 324 chars)** Realised I could add `x, y` to the declaration at the top instead of declaring each in the `for` statement; that I could change *one* of the `ToArray`s to `ToList`; that I could increment `y` inside the call to `f` and thus get rid of it in the `for`.
* **(324 → 321 chars)** Move the assignment to `m` into the `for` statement, getting rid of a semicolon and two curlies.
* **(321 → 308 chars)** Joey’s suggestions in the comments. Thanks!
> 3 votes

# Answer
## Python (202)

```
import sys;g=map(lambda l:map(int,l.split()),sys.stdin.readlines())
r=range(18)
for j in range(20):l=g[j];g[j]=[sum(l[i:i+3])for i in r]
g=[g[i][j]*g[i+1][j]*g[i+2][j]for i in r for j in r]
print max(g)

```

**Edit:** Fixed r to be range(18) instead of 17.
> 2 votes

# Answer
# C ~~184~~ 171 Characters

```
#define f(i,b)for(i=0;i<b;i++)
i,j,k,l,m,M,s,a[400];main(){f(i,400)scanf("%d",a+i);f(i,18)f(j,18){m=1;f(k,3){s=0;f(l,3)s+=a[(i+k)*20+j+l];m*=s;}M=m>M?m:M;}printf("%d",M);}

```
> 2 votes

# Answer
# Windows PowerShell, 116 ~~117~~ ~~124~~ ~~152~~ ~~170~~

```
$g=-split$input
(0..359|?{$_%20-le17}|%{$i=$_
(0..2|%{$g[($a=$i+20*$_)..($a+2)]-join'+'|iex})-join'*'|iex}|sort)[-1]

```

Fairly straightforward, actually.
> 2 votes

# Answer
# Ruby, 106 characters

```
k=$<.read.split.map &:to_i;p (0..358).map{|a|a%20>17?0:(0..2).map{|i|k[20*i+a,3].inject:+}.inject(:*)}.max

```

Yet another straightforward solution.

* Edit: Previous solution produced incorrect results for some edge cases.
* Edit: (114 -\> 106) Use a flat array, check `index%20` to prevent overflows into the next row.
> 2 votes

# Answer
# Ruby - 78 chars

```
g=*$<
p (0..324).map{|i|eval g[i/18,3].map{|r|eval r.split[i%18,3]*?+}*?*}.max

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 22 bytesSBCS

Complete program.

```
⌈/,{×/+/⍵}⌺3 3↑⍎20⍴'⎕'

```

Try it online!

`20⍴'⎕'` reshape the character  (which stands for evaluated input from stdin) to length 20

execute that (gives use 20 lists)

mix the lists into a matrix

`{``}⌺3 3` on each 3-by-3 sub-matrix:

`+/⍵` sum the rows

`×/` multiply the sums

`,` flatten the matrix of sums

`⌈/` find the maximum
> 2 votes

# Answer
## J+tr, 84+10

```
y=:20 20$".(1!:1)3
s=:3 :'(y&((][;.0~3 3,:~[)~))"1(,."0/~i.18)'
>./,([:*/+/"1)"2 s y

```

runs like this `< golfdata tr \\n ' '| ./test.ijs` so I consider the `tr \\n ' '` part as part of the program.

```
y=: 40 30 43 ...
>./,([:*/+/"1)"2 s y
328536000

z =: 20 20 $>:i.20
>./,([:*/+/"1)"2 s z
185193

```
> 1 votes

# Answer
## Golfscript, 48 chars

```
n%"{~}%:^,,{^>3<}%":|~{{+}*}%20/zip|~{{*}*}%$)p;

```

previous one

```
n%{' '%"{~}%:^,,{^>3<}%":|~{{+}*}%}%zip|~{{*}*}%$)p;

```

Some explanations, but I am still newbie in golfscript, some might not be correct, please correct me, if you see something wrong.

```
n%                 #.lines
{                  #.each
   ' '%               #.split ' '
   "                  #"... literal string start
      {~}%               #.flatten
      :^                 #assign to variable ^
      ,                  #.size
      ,                  #.times
      {                  #.each
         ^>                 #^[n:]
         3<                 #[:3]
      }%                 #.map end
   "                  #..." literal string end
   :|                 #assign literal string to variable | to reuse later
   ~                  #eval
   {                  #.each
      {+}                #sum
      *                  #.fold
   }%                 #.map end
}%                 #.map end
zip                #.zip
|~                 #eval variable | against result of .zip
{                  #.each
   {*}                #product
   *                  #.fold
}%                 #.map end
$                  #.sort
)                  #uncons / .pop
p                  #puts
;                  #discard top item from stack

```

Tests

```
$ cat sample-1159-1.txt | golfscript codegolf-1159.gs
3375

$ cat sample-1159-2.txt | golfscript codegolf-1159.gs
328536000

$ cat sample-1159-3.txt | golfscript codegolf-1159.gs
185193

```
> 1 votes

# Answer
## Haskell, 129 characters

```
import List
t f z@(_:y@(_:x))=zipWith3((f.).f)z y x
main=interact$show.maximum.(t(*)=<<).transpose.map(t(+).map read.words).lines

```
> 1 votes

# Answer
# Jelly, 18 bytes

```
ƈLÐ¿ḊỴḲ€V+3\€×3\FṀ

```

Try it online!

Takes input from STDIN, space and newline separated

---

# Jelly, 9 bytes

```
+3\€×3\FṀ

```

Try it online!

Takes a 20x20 matrix of integers as input. +4 bytes to input as a space and newline separated grid

## How it works

```
+3\€×3\FṀ - Main link. Takes a matrix M on the left
   €      - Over each row r:
 3\       -   Over each overlapping triple:
+         -     Take the sum
     3\   - Over each overlapping triple:
    ×     -   Take the product
       F  - Flatten
        Ṁ - Take the maximum

```
> 1 votes

# Answer
# Powershell, 103 bytes

```
(($x=-split($args-replace'(\d+)(?= (\d+) (\d+))','$1+$2+$3')|iex)|%{$_*$x[$j+20]*$x[$j+++40]}|sort)[-1]

```

Explanation:

* The regexp transforms each string like `1 2 3 4 5 6` to the string like `1+2+3 2+3+4 3+4+5 5 6`;
* Then the script splits the string `1+2+3 2+3+4 3+4+5 5 6` by spaces and evaluates each element by `iex` (alias for Invoke-Expression). A result is an array like `6,9,11,5,6`;
* Finally, the script concatenates all arrays to one, calulates a products and returns a maximum.

It is essential that we need a *maximum* of products of sum of *non-negative integers*. So we don't need to filter out the last 2 values in each row and last 2 rows.

## Less golfed test script

```
$f = {

$x=-split($args-replace'(\d+)(?= (\d+) (\d+))','$1+$2+$3')|iex
($x|%{$_*$x[$j+20]*$x[$j+++40]}|sort)[-1]

}

@(
    ,(  3375,
        "1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "4 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
        "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1")
    ,(  328536000,
        "40 30 42 222 74 265 93 209 115 274 139 177 7 274 12 15 103 36 236 91",
        "294 97 35 272 167 126 18 262 292 48 8 296 85 93 245 4 4 240 276 153",
        "52 8 163 270 242 224 142 72 99 240 199 26 224 198 96 242 295 70 56 247",
        "247 130 216 68 266 142 93 214 30 8 12 163 59 84 40 287 233 65 30 242",
        "283 245 164 53 148 282 73 186 296 3 9 233 184 30 205 221 92 96 5 101",
        "132 228 43 91 228 37 266 140 159 109 10 230 40 114 264 3 266 164 219 283",
        "70 207 218 28 299 78 279 30 179 118 196 138 61 229 110 55 203 73 124 112",
        "16 232 28 187 292 78 194 70 65 203 255 227 176 21 32 225 11 15 92 151",
        "58 237 261 41 213 171 170 111 4 209 99 194 40 108 267 137 179 31 35 221",
        "184 209 264 275 163 268 261 40 198 185 45 188 280 273 54 79 270 286 273 121",
        "208 83 66 156 104 62 188 68 53 194 46 279 280 170 266 148 272 285 178 245",
        "210 130 213 118 165 210 213 66 54 189 166 193 57 213 14 101 143 109 172 101",
        "80 193 287 4 140 65 208 111 8 206 107 285 109 29 211 78 170 247 290 193",
        "148 123 15 164 28 153 222 67 156 165 6 163 114 77 165 17 143 209 278 100",
        "3 102 58 148 82 181 84 29 2 236 231 195 118 278 252 257 179 123 276 287",
        "143 141 254 142 200 243 171 32 164 195 235 260 269 191 190 46 65 166 82 146",
        "69 194 65 220 234 110 45 135 125 208 138 20 233 291 256 162 148 216 247 138",
        "10 53 164 107 2 270 226 227 88 206 193 13 41 130 218 249 76 35 207 91",
        "199 36 207 256 58 215 28 277 234 29 198 148 219 244 136 16 30 258 219 264",
        "183 118 48 218 15 125 279 103 73 8 86 113 9 157 239 273 146 208 50 86")
    ,(  185193,
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20",
        "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20")
    ,(  311042813,
        "242 248 292 60 9 45 94 97 294 202 219 118 115 243 207 81 288 289 241 232",
        "236 225 205 227 242 85 139 63 5 162 170 121 208 133 22 235 125 288 209 270",
        "31 182 108 170 88 268 297 66 249 158 285 157 267 117 150 18 44 66 117 223",
        "205 32 93 132 33 99 209 282 222 272 255 1 80 270 202 54 117 35 139 273",
        "87 74 113 146 177 14 154 92 282 4 192 60 171 286 66 299 89 276 138 289",
        "60 16 143 277 202 284 77 296 215 96 200 10 226 143 136 131 218 246 254 20",
        "244 118 299 218 81 195 129 93 205 202 264 141 196 150 214 72 231 136 243 192",
        "236 157 176 187 104 182 134 29 151 234 81 143 22 119 45 241 17 225 197 7",
        "156 284 92 13 131 60 113 77 228 65 200 83 3 63 83 88 241 113 115 198",
        "62 101 242 270 121 122 119 78 105 273 55 7 239 236 37 252 66 164 56 44",
        "70 57 100 87 34 298 140 259 36 257 1 204 110 299 245 56 43 121 192 10",
        "240 36 272 255 10 194 143 66 27 131 22 78 57 71 128 5 1 155 236 122",
        "281 160 42 147 272 151 196 240 291 280 209 245 271 46 103 35 85 145 78 140",
        "155 74 232 205 235 223 147 39 171 240 56 187 184 70 28 81 293 125 283 159",
        "297 203 75 46 221 77 106 12 268 94 220 156 78 97 266 208 228 137 212 49",
        "4 157 69 51 225 23 61 202 19 23 41 260 161 218 142 251 299 187 283 158",
        "118 136 71 77 21 199 110 87 103 120 153 157 213 234 155 141 135 24 120 199",
        "16 204 292 245 54 260 294 159 254 15 209 41 154 54 231 167 87 291 31 26",
        "212 274 99 199 170 184 47 227 64 2 117 275 67 84 143 214 143 125 24 61",
        "205 250 133 88 210 112 4 160 3 287 54 143 293 94 287 42 105 94 76 169")
) | % {
    $expected, $a = $_
    $result = &$f @a
    "$($result-eq$expected): $result"
}

```

## Output

```
True: 3375
True: 328536000
True: 185193
True: 311042813

```

---

# Powershell, 105 bytes, no-regexp alternative

The tribute to the smart expression `|?{$_%20-le17}` in the Joey's answer:

```
(($x=($y=-split$args)|?{$i++%20-le17}|%{+$y[$i-1]+$y[$i]+$y[$i+1]})|%{$_*$x[$j+18]*$x[$j+++36]}|sort)[-1]

```
> 0 votes

# Answer
# Stax, 19 bytes

```
┬░╩íΩ{\ë╔B_m♦½─Γe╧¼

```

Run and debug it

Input is given directly, no quotes.

## Explanation

```
L{eL3B{|+mmM{3B{:*mm$|M Input: STDIN, auto split on newlines, pushed to stack
L                       listify the stack
 {        m             map each line to:
 {e       m             evaluate it
   L                    listify the stack
    3B                  overlapping slices of length 3
      {|+m              map those to their sums
           M            transpose
            {      m    map to:
             3B         overlapping slices of length 3
               {:*m     mapped to products
                    $   flatten
                     |M maximum

```
> 0 votes

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


# Question
Title: Write a program that checks the consistency of modern mathematics
Modern mathematics has been formalised using set theory by various systems of axioms. Zermelo Frankel set theory with the axiom of choice (ZFC) forms an intuitive set of axioms and is hence most popular, though stronger choices exist.

Inspiration: A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory by Adam Yedidia and Scott Aaronson

In this paper, a 7918-state Turing machine has been discovered that "checks" the consistency of ZFC. More specifically, it has been proven impossible to prove the machine as either halting or non-halting within ZFC. Note that if the program actually halts in a finite number of steps, its behaviour is also provably halting in any reasonable axiomatic system since we can enumerate this finite number of steps explicitly. Therefore halting can only mean an inconsistency in ZFC itself.

A 1919-state TM was also discovered subsequently

The method they've used (for the 8000 state machine) is to identify a mathematical statement whose truth has been proven to imply the consistency of ZFC, in this case Friedman's mathematical statement on graphs (section 3.1 of the paper), then written a program in a higher level language to check that, then converted it to a Turing machine

Your task: **Write a program in any accepted language on this site (not necessarily a Turing machine) which cannot be proven as halting or non-halting within ZFC.** This is code golf, so shortest program wins.

Your program must be deterministic, it cannot use "random" numbers or take external "random" input.

Likely method to go about this would be to identify a mathematical statement which is already known to be independent of ZFC or a stronger system, and check that - though this is by no means the only way to go about it. Here's a list of such statements to get you started.

Related: Analogous challenge for Peano arithmetic

# Answer
# NQL: 335 characters

In *The Busy Beaver Frontier* page 12, Scott Aaronson mentions that Stefan O'Rear found a 748-state Turing machine that halts iff ZF is inconsistent. Here is the code that compiles to that Turing machine from a higher-level programming language called **NQL**, based on Laconic. I'm not very familiar with this language, but applying basic golfing techniques yields **397 characters**:

```
global x;global lcm;global l;global num;global denom;global i;global a;global b;global c;global d;proc main(){lcm=1;while(true){x=x+1;l=lcm;while(lcm!=(lcm/l)*l||lcm!=(lcm/x)*x){lcm=lcm+1;}if(x>253){num=0;denom=1;i=1;while(i<=lcm){num=num*i+denom;denom=denom*i;i=i+1;}a=num-denom*x;a=a*a;b=denom*denom;c=0;d=1;i=1;while(i<=x){c=c*i+d;d=d*i;i=i+1;}c=c*c;c=c*c*x;d=d*d;d=d*d;if(a*d>b*c){return;}}}}

```

I confirmed that the same output is produced as the original program with

```
diff <(python3 nqlaconic.py --print-tm riemann-matiyasevich-aaronson.nql) \
<(python3 nqlaconic.py --print-tm riemann-matiyasevich-aaronson-golfed.nql)

```

Applying variable name shortening (this changes the output) yields **335 characters**:

```
global x;global v;global l;global z;global y;global i;global a;global b;global c;global d;proc main(){v=1;while(true){x=x+1;l=v;while(v!=(v/l)*l||v!=(v/x)*x){v=v+1;}if(x>253){z=0;y=1;i=1;while(i<=v){z=z*i+y;y=y*i;i=i+1;}a=z-y*x;a=a*a;b=y*y;c=0;d=1;i=1;while(i<=x){c=c*i+d;d=d*i;i=i+1;}c=c*c;c=c*c*x;d=d*d;d=d*d;if(a*d>b*c){return;}}}}

```

Given its C-like syntax, I imagine the code could be easily adapted to other languages and shortened further.
> 7 votes

---
Tags: code-golf, logic
---