title: First they came

text:
# Question
Title: First they came
"First they came..." is a poem by Martin Niemöller:

```
First they came for the Socialists, and I did not speak out-
Because I was not a Socialist.

Then they came for the Trade Unionists, and I did not speak out-
Because I was not a Trade Unionist.

Then they came for the Jews, and I did not speak out-
Because I was not a Jew.

Then they came for me-and there was no one left to speak for me.

```

Your task is to output the above. This is , so shortest code in bytes wins!

# Rules

* You may include extra whitespace that does not affect appearance. A single trailing newline is allowed.
* Otherwise, the output must match exactly, including the location of newlines.
* As per meta standards, you may output a list of strings. However, you must include the empty lines.

Note that I personally believe this is not a dupe because of how the poem is laid out - it needs some creativity to golf. Meta discussion about whether this is a dupe or not can be found here.

# Answer
> 8 votes
# SOGL V0.12, ~~103~~ ~~102~~ 101 bytes

```
 →∑‘¾ο╤Ε9‘}ψ⁴‘¹"4¡‘Q°‘:¹¹I{ū_:¹"Eā/}l6⁸SÆ□⁴↔b⅜╬I℮;YΥηκ*█⅞F^Κ⅜⁸{x⅔⁵⅟╚?Z‘O}"Ι╚╬√⅔δηvΧχ⁷⁾Η<υL┼!Ο'μΠ⁵╝⁷‘⁾

```

Try it Here!

Explanation (here I replaced the compressed strings with `..` to save space):

```
..‘.‘..‘                              push "socialist", "trade unionist" and "jew"
        ¹                             wrap in an array: ["socialist", "trade unionist", "jew"]
         "..‘..‘                      push "first" and "then"
                :                     duplicate the then
                 ¹                    wrap in an array: ["first","then","then"]
                  ¹                   wrap those two in an array: [["socialist", "trade unionist", "jew"], ["first","then","then"]]
                   I                  rotate clockwise: [[first,socialist], [then,trade unionist], [then,jew]]
                    {         }       for each do, pushing the array
                     ū                  uppercase the 1st letter of each word in the array - ["First", "Socialist"]
                      _                 splat the contents on the stack   "First", "Socialist"
                       :                duplicate the 2nd one             "First", "Socialist", "Socialist"
                        ¹               wrap in an array                  ["First", "Socialist", "Socialist"]
                         "..‘           push "ŗ they came for the ŗs, and I did not speak out-\nBecause I was not a ŗ." with ŗ replaced with its appropriate item in the array
                             O          output that
                               "..‘   push "then they came for me-and there was no one left to speak for me."
                                   ⁾  uppercase the 1st letter of it
                                      implicitly output it in a new line

```

# Answer
> 7 votes
# 6502 machine code (C64), 229 bytes

Kind of boring, still doable on a C64 with a *somewhat* decent amount of bytes :)

```
00 C0 A9 17 8D 18 D0 A2 2C 86 FE A6 FE A0 C0 BD B6 C0 20 1E AB C6 FE 10 F2 60
C6 49 52 53 54 20 00 D4 48 45 4E 20 00 54 48 45 20 00 54 48 45 59 20 43 41 4D
45 20 00 46 4F 52 20 00 53 50 45 41 4B 20 00 41 4E 44 20 C9 20 44 49 44 20 4E
4F 54 20 00 4F 55 54 2D 0D 00 C2 45 43 41 55 53 45 20 C9 20 57 41 53 20 4E 4F
54 20 41 20 00 4D 45 2D 41 4E 44 20 54 48 45 52 45 20 57 41 53 20 4E 4F 20 4F
4E 45 20 4C 45 46 54 20 54 4F 20 00 4D 45 2E 00 2E 0D 00 53 2C 20 00 D3 4F 43
49 41 4C 49 53 54 00 D4 52 41 44 45 20 D5 4E 49 4F 4E 49 53 54 00 CA 45 57 00
0D 00 8C 35 3A 6B 2A 1F B4 90 B0 56 50 3A 41 93 B0 25 35 2A 1F B4 90 A1 56 50
3A 41 93 A1 25 35 2A 1F B4 90 97 56 50 3A 41 93 97 25 35 2A 18

```

### Online demo

Usage: `SYS49152`

**Explanation:**

As this contains mostly data, instead of a meaningless disassembly listing, here's the `ca65`-style assembly source that creates this machine code:

```
.segment "LDADDR"
                .word   $c000           ; load address
.code
                lda     #$17            ; upper/lower mode
                sta     $d018           ; store in VIC register
                ldx     #revpoemsize    ; initialize ...
                stx     $fe             ; ... counter
loop:           ldx     $fe             ; load current position
                ldy     #$c0            ; highbyte of strings always same
                lda     revpoem,x       ; load lowbyte from table
                jsr     $ab1e           ; output 0-terminated string
                dec     $fe             ; decrement position
                bpl     loop            ; >=0 ? -> repeat
                rts                     ; done

first:          .byte   "First ", 0
then:           .byte   "Then ", 0
the:            .byte   "the ", 0
came:           .byte   "they came ", 0
for:            .byte   "for ", 0
speak:          .byte   "speak ", 0
didnot:         .byte   "and I did not ", 0
out:            .byte   "out-", $d, 0
wasnot:         .byte   "Because I was not a ", 0
noone:          .byte   "me-and there was no one left to ", 0
me:             .byte   "me.", 0
period:         .byte   ".", $d, 0
comma:          .byte   "s, ", 0
socialist:      .byte   "Socialist", 0
unionist:       .byte   "Trade Unionist", 0
jew:            .byte   "Jew", 0
p:              .byte   $d, 0

revpoem:        .byte   <me, <for, <speak, <noone, <came, <then, <p
                .byte   <period, <jew, <wasnot, <out, <speak, <didnot
                .byte   <comma, <jew, <the, <for, <came, <then, <p, <period
                .byte   <unionist, <wasnot, <out, <speak, <didnot, <comma
                .byte   <unionist, <the, <for, <came, <then, <p, <period
                .byte   <socialist, <wasnot, <out, <speak, <didnot, <comma
                .byte   <socialist, <the, <for, <came, <first
revpoemsize     = * - revpoem - 1

```

# Answer
> 6 votes
# Python 3, 209 bytes

```
t='they came for '
s='First '
for i in'Socialist','Trade Unionist','Jew':s+=t+f'the {i}s, and I did not speak out-\nBecause I was not a {i}.\n\nThen '
print(s+t+'me-and there was no one left to speak for me.')

```

Try it online!

-5 thanks to Felipe Nardi Batista.

# Answer
> 4 votes
## Perl 5, 185 bytes

```
print join" they came for ",First,(map"the ${_}s, and I did not speak out-
Because I was not a $_.

Then",Socialist,"Trade Unionist",Jew),"me-and there was no one left to speak for me."

```

Try it online!

Thanks to @Massa for -3 bytes!

# Answer
> 4 votes
# Perl 6, 193 bytes

```
say join ' they came for ','First',«Socialist "Trade Unionist" Jew».map({"the {$_}s, but I did not speak out-
because I was not a $_.

Then"}),'me- and there was no one left to speak for me.'

```

Try it online!

# Answer
> 3 votes
# C, 248 bytes

*Thanks to @Zacharý for saving 9 bytes.*

```
p(x,y){printf("%s they came for the %ss, and I did not speak out-\nBecause I was not a %s.\n\n",x,y,y);}f(){p("First","Socialist");p("Then","Trade Unionist");p("Then","Jew");puts("Then they came for me-and there was no one left to speak for me.");}

```

Try it online!

# Answer
> 3 votes
# C# (.NET Core), 248 246 242 bytes

```
a=>{string b=@", and I did not speak out-
Because I was not a ",c=" they came for ",d="Socialist",e="Trade Unionist";return$@"First{c+d}s{b+d}.

Then{c+e}s{b+e}.

Then{c}the Jews{b}Jew.

Then{c}me-and there was no one left to speak for me.";}

```

Actual newlines saved me a few bytes.

Try it online!

Saved 2 bytes thanks to *Business Cat*

# Answer
> 3 votes
# Python 3, 203 bytes

```
print('First',*[f'the {s}s, and I did not speak out-\nBecause I was not a {s}.\n\nThen'for s in['Socialist','Trade Unionist','Jew']],'me-and there was no one left to speak for me.',sep=' they came for ')

```

Try it online!

# Answer
> 3 votes
# Befunge-93, 348 bytes

```
".em rof kaeps ot tfel eno on saw ereht dna-em rof emac yeht nehT"52*:v
v"d not speak out-"*25"Because I was not a "<   p5-2*89p1-2*89"vvJew."<
> "id I dna ">",sweJ>v"67+2p66+5p     v     ^p2-2*89"vTrade Unionist."<
>"tsriF">:#,v>",stsinoinU edarTv"67+3pv     ^   p3+66p40"^_Socialist."<
>"nehT"52*: v>",stsilaicoS@"67+3p     >" eht rof emac yeht "

```

Try it online!

# Answer
> 3 votes
# Befunge, ~~293~~ ~~274~~ 270 bytes

```
62574732594932584832001v_@#:\0\!<
0-*84g+3/"P"\%"P"::+p00<_|#:-1g0
84!-"*":g+3/"P"\%"P"::+1\<+1_$#:^#-2\,-**
&First0 they came for %the Qs, and I did not speak out-*Because I was not a (.**
ThenOme-and there was no one left to speak for me.*$Jew*Socialist/Trade Unionist

```

Try it online!

This is a different approach to the existing Befunge solution. It uses a kind of linked list to store a dictionary of the common phrases, and then just has a simple list of values on the stack representing the order in which the phrases should be output.

# Answer
> 2 votes
# Gaia, ~~179~~ 175 bytes

```
⇓“the ”3ṁ“s, and I did not speak out-¶Because I was not a ”2ṃ“.¶¶Then
“ they came for
First”“Socialist“Trade Unionist“Jew”↓¦⇑“me-and there was no one left to speak for me.”]$

```

Try it online!

### Explanation

3 functions are defined here (1 per line). The bottom one is called first.  gets replaced by newlines.

```
⇓“the ”3ṁ“...”2ṃ“.¶¶Then  First helper function. Argument: s
⇓                         Push "Then they came for "
 “the ”                   Push "the "
       3ṁ                 Bring s to the top
         “...”            Push "s, and I did not speak out-¶Because I was not a "
              2ṃ          Push a copy of s
                “.¶¶Then  Push ".¶¶Then"

“ they came for   Helper function. No arguments.
“ they came for   Push " they came for "

First”“..“..“..”↓¦⇑“...”]$  Main function.
First”                      Push "First"
      “..“..“..”            Push the list ["Socialist" "Trade Unionist" "Jew"]
                ↓¦          Call the first helper function on each.
                  ⇑         Push "Then they came for "
                   “...”    Push "me-and there was no one left to speak for me."
                        ]$  Wrap the stack in a list and join with no separator.

```

# Answer
> 2 votes
# JavaScript (ES6), ~~231~~ ~~227~~ ~~223~~ 221 bytes

```
_=>`First${t=" they came for "}the Socialist${a=`s, and I did not speak out-
Because I was not a `}Socialist${t=`.

Then`+t}the ${(u="Trade Unionist")+a+u+t}the Jew${a}Jew${t}me-and there was no one left to speak for me.`

```

---

## Try it

```
o.innerText=(
_=>`First${t=" they came for "}the Socialist${a=`s, and I did not speak out-
Because I was not a `}Socialist${t=`.

Then`+t}the ${(u="Trade Unionist")+a+u+t}the Jew${a}Jew${t}me-and there was no one left to speak for me.`
)()
```

```
<pre id=o>
```

# Answer
> 2 votes
# Bubblegum, ~~149~~ ~~132~~ 129 bytes

```
00000000: 9d4d b515 0241 14cc af8a c991 1e70 0991  .M...A.......p..
00000010: 02fe bbfd e7b7 cb1a 523d ee0e d9f8 7453  ........R=....tS
00000020: 631d 5cc2 2b84 5432 2265 760c 6315 a654  c.\.+.T2"ev.c..T
00000030: a4d6 d92a 480a 0c20 5201 a91c ec8c 2987  ...*H.. R.....).
00000040: f2ae 1634 3924 6f79 6b2e c8ee 4dba 14eb  ...49$oyk...M...
00000050: 4130 4958 3ed9 9e18 128c a94c 95fc e3e0  A0IX>......L....
00000060: b6fd fa65 c88b 1fa7 7795 e77b 25d7 488a  ...e....w..{%.H.
00000070: 9d68 f898 8792 8c82 2307 a78e bb87 647d  .h......#.....d}
00000080: 03                                       .

```

Try it online!

Boring Bubblegum answer. Already beaten by SOGL, so that's good.

Credit for -17 bytes goes to Dom Hastings

-3 bytes by ovs

# Answer
> 2 votes
# Retina, 176 bytes

```

 Socialists, Trade Unionists, Jews,1me-and there was no one left to2for me.
( .+?)s,
1the$& and I did not2out-¶Because I was not a$1.¶¶Then
^
First
1
 they came for
2
 speak

```

Try it online! Explanation: The `1` and `2` are just repeated strings which are long enough to be worth deduplicating. The `First` is added later to make it easier to select the placeholder for the repetitive portion, "they came for the \[group\]s, and I did not speak out-Because I was not a \[group\]. Then", which is expanded by the second stage.

# Answer
> 2 votes
# JavaScript (ES6), ~~210~~ ~~207~~ ~~206~~ 203 bytes

A different approach to my other solution so figured it was worth editing it out to its own answer now that the challenge has been reopened.

```
_=>`First${["Socialist","Trade Unionist","Jew"].map(x=>t+`the ${x}s, and I did not speak out-
Because I was not a ${x}.

Then`,t=` they came for `).join``+t}me-and there was no one left to speak for me.`

```

---

## Try it

```
o.innerText=(
_=>`First${["Socialist","Trade Unionist","Jew"].map(x=>t+`the ${x}s, and I did not speak out-
Because I was not a ${x}.

Then`,t=` they came for `).join``+t}me-and there was no one left to speak for me.`
)()
```

```
<pre id=o>
```

# Answer
> 2 votes
# Java 8, ~~250~~ 236 bytes

```
o->{String t=" they came for ",r="First";for(String s:"Socialist,Trade Unionist,Jew".split(","))r+=t+"the "+s+"s, and I did not speak out-\nBecause I was not a "+s+".\n\nThen";return r+t+"me-and there was no one left to speak for me.";}

```

Try it here.

# Answer
> 2 votes
# PowerShell, 211 202 198 bytes

-13 bytes thanks to @Veskah

```
$a,$b='First',' they came for'
'Socialist','Trade Unionist','Jew'|%{"$a$b the $_`s, and I did not speak out-
Because I was not a $_.
";$a='Then'}
"$a$b me-and there was no one left to speak for me."
```

Try it online!

I'm sure this can be golfed down a little bit.

# Answer
> 2 votes
# SQL 269 bytes

```
declare @ char(18)='They came for the ',@a char(49)='s, and I did not speak out-
Because I was not a '
print'First '+@+'Socialist'+@a+'Socialist.

'+@+'Trade Unionist'+@a+'Trade Unionist.

'+@+'Jew'+@a+'Jew.

'+@+' me-and there was no one left to speak for me.'

```

# Answer
> 1 votes
# Proton, 219 bytes

```
t='they came for'for i:'Socialist','Trade Unionist','Jew'print(i[0]=='S'? 'First':'Then',t,'the',i+'s, and I did not speak out-
Because I was not a',i+'.
')print('Then',t,'me-and there was no one left to speak for me.')

```

Try it online!

# Answer
> 1 votes
## Python 2, 246 bytes

First time I tried compressing the string an returning it. Aparently it takes more bytes than other approaches. Is there anything left to golf?

```
import zlib,base64
print zlib.decompress(base64.b64decode('eJyd0DEOwjAMBdA9p/gHoD0EAxJdgQNYiatGtDaKU1XcvikUdSkDjLb/f4NPMVlG7vgJTwOj1bRMuKiP1EfLdgBJwBkhBohm2IPpDh1z5Y7saTQux4nsdaStWDt37Vh27JtElT/oT++73PD0K1oq+97A1QKVZeI1DxVGz215mK7uO1nPf1Zu5g=='))

```

Try it online!

# Answer
> 1 votes
# Japt, ~~153~~ ~~150~~ ~~149~~ 147 bytes

```
`{=` ey ¯´ f `}´-d tre °s no e ¤ft  speak f ´.`i`Sáû\E
TÎè UÍát
Jew`·rÈ+U+`e {Y}s, d I ¹d not speak t-
Be¯«e I °s not a {Y}.

Tn`}`Fir¡

```

Test it

1 byte saved thanks to Oliver

# Answer
> 1 votes
# Röda, 204 bytes

```
{t="Then"c=" they came for";["First","Socialist",t,"Trade Unionist",t,"Jew"]|[`$_$c the ${_}s, and I did not speak out-
Because I was not a $_2.

`];[`$t$c me-and there was no one left to speak for me.`]}

```

Try it online!

# Answer
> 1 votes
# PHP, 194 bytes

```
First<?=$t=" they came for ";foreach([Socialist,"Trade Unionist",Jew]as$s)echo"the ${s}s, and I did not speak out-
Because I was not a $s.

Then$t"?>me-and there was no one left to speak for me.

```

Try it online.

# Answer
> 1 votes
# C (gcc), 244 bytes

```
f(c){for(c=0;c<3;printf("%s they came for the %ss, and I did not speak out-\nBecause I was not a %2$s.\n\n",c++?"Then":"First",c^2?c?"Trade Unionist":"Socialist":"Jew"));puts("Then they came for me-and there was no one left to speak for me.");}

```

Try it online!

# Answer
> 1 votes
# Python 3, 208 bytes

```
print(' they came for '.join(["First"]+[f"the {i}s, and I did not speak out-\nBecause I was not a {i}.\n\nThen"for i in['Socialist','Trade Unionist','Jew']]+['me-and there was no one left to speak for me.']))

```

Try it online!

-1 thanks to @Step Hen

# Answer
> 1 votes
# Clojure, 285 bytes

```
(fn[](doseq[i(range 4):let[c["Socialist""Trade Unionist""Jew"""]f #(if(< i 3)% %2)]](println(if(= i 0)"First""Then")"they came for"(str(f(str"the "(c i)"s, ")"me-")(f"and I did not speak out-\n""and there was no one left to speak for me.")(f(str"Because I was not a "(c i)".\n")"")))))

```

This was a fun little challenge. I ended up almost entirely rewriting most of it a couple of times because I realized I was doing something overly roundabout. There are still a couple areas that could probably be touched up, but I'm pretty happy with how it turned out, even if I'm only "compressing" the original by 54 bytes.

repl.io

See the pre-golfed code for an explanation:

```
(defn ftc []
  ; Loop over the lines numbers for reference
  (doseq [i (range 4)
          :let [; Added a dummy last "class" since "me-" wasn't necessary,
                ;  and only having 3 elements was causing OOB errors.
                classes ["Socialist" "Trade Unionist" "Jew" ""]

                ; A helper function that executes either its first or second argument
                ;  depending on if the current line is one of the first 3 lines.
                if-first-three-lines #(if (< i 3) % %2)]]

    ; An implicit space is inserted between each of the args to println
    (println
      ; Decide on the opener
      (if (= i 0) "First" "Then")

      "they came for"

      ; Start string concatenation because the implicit space
      ;  begins complicating things.
      (str
        ; Decide which "class" the line belongs to
        (if-first-three-lines
          (str "the " (classes i) "s, ")
          "me-")

        ; Decide on the line ending
        (if-first-three-lines
          "and I did not speak out-\n"
          "and there was no one left to speak for me.")

        ; Then pick the trailer
        (if-first-three-lines
          (str "Because I was not a " (classes i) ".\n")
          "")))))

```

# Answer
> 1 votes
# 05AB1E, ~~124~~ 119 bytes

```
.•RYÁ Wö∍®Ø’áÅÚ)’Òü•'x¡™vy„€Û‚½#NĀè™“ÿ€»‹é€‡€€ ÿs,€ƒ Iƒ§€–¡´€Ä-“©¶y“ƒ« I€¥€–€… ÿ.“.ª¶¶}®19£“€á-and€Ç€¥€¸€µ…¸€„¡´€‡€á.“J

```

Try it online.

**Explanation:**

```
.•RYÁ Wö∍®Ø’áÅÚ)’Òü•
                  # Push compressed string "socialistxtrade unionistxjew"
 'x¡             '# Split it on "x": ["socialist","trade unionist","jew"]
    ™             # Convert each word to Titlecase: ["Socialist","Trade Unionist","Jew"]
v                 # Loop `y` over each of these strings:
 y                #  Push string `y`
 „€Û‚½            #  Push dictionary string "first then"
      #           #  Split on spaces: ["first","then"]
       N          #  Push the index of the loop
        Ā         #  Truthify it (0 remains 0; every other number becomes 1)
         è        #  Use it to index into the list
          ™       #  Titlecase it
 “ÿ€»‹é€‡€€ ÿs,€ƒ Iƒ§€–¡´€Ä-“
                  #  Push dictionary string "ÿ they came for the ÿs, and I did not speak out-"
                  #  where the "ÿ" are automatically filled with the strings at the top of the stack
  ©               #  Save it in the register (without popping)
 ¶                #  Push a newline "\n"
 y                #  Push string `y` again
 “ƒ« I€¥€–€… ÿ.“  #  Push dictionary string "because I was not a ÿ."
                  #  where the "ÿ" is automatically filled again with the string
  .ª              #  Sentence case it: "because" becomes "Because"
 ¶¶               #  Push two newline characters "\n\n"
}                 # After the loop:
®                 # Push the string from the register:
                  #  "Then they came for the Jews, and I did not speak out-"
 19£              # Only leave the first 19 characters: "Then they came for "
“€á-and€Ç€¥€¸€µ…¸€„¡´€‡€á.“
                  # Push dictionary string "me-and there was no one left to speak for me."
J                 # Then join everything on the stack together (and output implicitly)

```

See this 05AB1E tip of mine (sections *How to use the dictionary?* and *How to compress strings not part of the dictionary?*) to understand why:

* `.•RYÁ Wö∍®Ø’áÅÚ)’Òü•` is `"socialistxtrade unionistxjew"`
* `„€Û‚½` is `"first then"`
* `“ÿ€»‹é€‡€€ ÿs,€ƒ Iƒ§€–¡´€Ä-“` is `"ÿ they came for the ÿs, and I did not speak out-"`
* `“ƒ« I€¥€–€… ÿ.“` is `"because I was not a ÿ."`
* `“€á-and€Ç€¥€¸€µ…¸€„¡´€‡€á.“` is `"me-and there was no one left to speak for me."`

# Answer
> -4 votes
# Text, 348 bytes

```
First they came for the Socialists, and I did not speak out-
Because I was not a Socialist.

Then they came for the Trade Unionists, and I did not speak out-
Because I was not a Trade Unionist.

Then they came for the Jews, and I did not speak out-
Because I was not a Jew.

Then they came for me-and there was no one left to speak for me.

```

This is the shortest possible version in its language, and is on par with the Befunge-93 answer at time of writing.

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


title: Sliding retrieval

text:
# Question
Title: Sliding retrieval
# Thanks, Uncle (the story)

My slightly mad uncle recently left for the space colonies, and passed his pallet goods business to me. The rectangular warehouse is full of pallets of goods except for the one square by the door, and I've just received the first list of pallets ordered by customers to be sent out today.

Fortunately I have a carefully written map of where each pallet is, and my mad uncle engineered several mini robots which can move a pallet into an adjacent space, much like a sliding 15-puzzle. I don't care where the pallets end up, though, I just want the pallets on the list to arrive in order by the door.

The question is, what series of commands must I give the robots in order to retrieve the required pallets?

# The challenge

Given

* the size of the grid (rows, cols)
* a list of pallets (by their current location) to retrieve in order

You must output a list of grid positions corresponding to which position is to be moved, and which direction. If there is only 1 direction available you may optionally omit that. The pallets will be removed immediately upon arrival by the door (at one corner, index N in the examples).

# Worked example

```
01 02   label the contents  A B
03 04                       C D
05[  ]                      E _

Request: 03 (contents is C)

Command 0: 04
D moves into the (only) adjacent space at index 06
Result: A B
        C _
        E D

Command 1: 03
C moves into the (only) adjacent space at index 04
Result: A B
        _ C
        E D

Command 2: 05
        A B
        E C
        _ D
Command 3: 06
        A B
        E C
        D _
Command 4: 04
        A B
        E _
        D[C]
(C removed having arrived by the door)

```

# Limits and freedoms

* Maximum grid size is 100x100
* Challenge is code-golf
* Solution must execute within 2 minutes on some real-world machine
* You can choose your indexing, command syntax, input structures and so on, as long as it's consistent.
* I've chosen to use the grid locations for the commands, but conceivably you could emit the value in the element instead (plus a direction) as they are unique.
* If you wanted to make an animation of the state (especially for a large grid), I'm sure that would be entertaining!

# Examples

## A: 3x2, 1 pallet

```
01  02
03  04
05 [__]

Request: pallet at 03

Valid solution: 05,03,04,06,05

This leaves the following state:

01  02
04  05
__ [03]

```

## B: 15-puzzle, 1 box

```
01 02 03 04 05
06 07 08 09 10
11 12 13 14[  ]

Request: box 01

Valid solution: 14,13,12,11,06,01,02,07,12,11,06,07,12,11,06,07,08,13,12,11,06,07,08,09,14,13,08,09,10,15,14

02 07 03 04 05
08 12 13 10 14
06 11 09 __[01]

```

## C: 3x2, 4 boxes

```
01 02
03 04
05[  ]

Request: 02,04,01,05

Valid solution: 04,02,01,03,05,06,04,05,02,06,03S,05E
Pallet taken at:                    ^  ^     ^       ^

Indicating directions with NSEW

Final state:

03 __
__ __
__ __

```

## D: 10x10, 2 boxes

```
10x10, request boxes at 13,12 (row 1, cols 2 & 1 with 0-index)

Valid solution: (90,80..20, 19,18..12, 22,32..92, 93,94..100) x 15, 90.

```

## E: 4x1, all

```
4x1: 01 02 03 [ ]
Req: 03,02,01 (only valid order)
Optimal solution: 03,02,03E,01,02E,03E

```

## F: 100x100, 3 near the door

```
100x100
Req: 9900,9899,9898
Result: 9000,9989,9000S,9898,9898E,9000S

```

Sandbox link

# Answer
> 3 votes
## JavaScript (Node.js) - ~~425~~ ~~424~~ ~~420~~ 395

```
(n,m,L)=>(s=Math.sign,G=[...Array(n*m).keys()],i=k=n*m-1,G[k]=-1,R=[],M=j=>{-G[j]-1&&R.push([j,i]);[G[i],G[j]]=[G[j],G[i]];i=j},X=j=>{while(i%n-j%n)M(i+s(j%n-i%n))},Y=j=>{while(y(i)-y(j))M(i+n*s(y(j)-y(i)))},y=i=>(i-i%n)/n,L.map(e=>{J=()=>j=G.indexOf(e);while(J()%n-n+1){m>1&&y(j)-y(i)||M(y(i)?i-n:i+n);X(j+1);Y(j);M(j);m<2?i=k:0}while(J()+1-n*m){X(n-2);Y(j+n);X(n-1);M(j);n<2?i=k:0}G[k]=-1}),R)

```

Try it online!

Takes n,m and an array of pallets, returns a list of commands where each command is a 2-element array of the location of the pallet to move and the location of the space to move it to.

There's probably a better strategy than what I used, but posting as is for now.

---
Tags: code-golf, sliding-puzzle
---


title: Divisor Rich and Poor Numbers

text:
# Question
Title: Divisor Rich and Poor Numbers
### Introduction

In the strange world of integer numbers, divisors are like assets and they use to call "rich" the numbers having more divisors than their reversal, while they call "poor" the ones having less divisors than their reversal.

For example, the number \\$2401\\$ has five divisors : \\$1,7,49,343,2401\\$, while its reversal, \\$1042\\$, has only four : \\$1,2,521,1042\\$.
So \\$2401\\$ is called a **rich** number, while \\$1042\\$ a **poor** number.

Given this definition, we can create the following two integer sequences of rich and poor numbers :

```
(here we list the first 25 elements of the sequences)

 Index | Poor | Rich
-------|------|-------
     1 |   19 |   10
     2 |   21 |   12
     3 |   23 |   14
     4 |   25 |   16
     5 |   27 |   18
     6 |   29 |   20
     7 |   41 |   28
     8 |   43 |   30
     9 |   45 |   32
    10 |   46 |   34
    11 |   47 |   35
    12 |   48 |   36
    13 |   49 |   38
    14 |   53 |   40
    15 |   57 |   50
    16 |   59 |   52
    17 |   61 |   54
    18 |   63 |   56
    19 |   65 |   60
    20 |   67 |   64
    21 |   69 |   68
    22 |   81 |   70
    23 |   82 |   72
    24 |   83 |   74
    25 |   86 |   75
   ... |  ... |  ...

```

**Notes :**

* as "reversal" of a number we mean its *digital reverse*, i.e. having its digits in base-10 reversed. This means that numbers ending with one or more zeros will have a "shorter" reversal : e.g. the reversal of `1900` is `0091` hence `91`
* we intentionally exclude the integer numbers having the same number of divisors as their reversal i.e. the ones belonging to OEIS:A062895

### Challenge

Considering the two sequences defined above, your task is to write a program or function that, given an integer `n` (you can choose 0 or 1-indexed), returns the n-th poor and n-th rich number.

### Input

* An integer number (`>= 0` if 0-indexed or `>= 1` if 1-indexed)

### Output

* 2-integers, one for the poor sequence and one for the rich sequence, in the order you prefer as long as it is consistent

### Examples :

```
INPUT          |   OUTPUT
----------------------------------
n (1-indexed)  |   poor    rich
----------------------------------
1              |   19      10
18             |   63      56
44             |   213     112
95             |   298     208
4542           |   16803   10282
11866          |   36923   25272
17128          |   48453   36466
22867          |   61431   51794
35842          |   99998   81888

```

### General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

# Answer
> 9 votes
# 05AB1E, 16 bytes

```
∞.¡ÂÑgsÑg.S}¦ζsè

```

Try it online!

---

**0-indexed \[rich,poor\]:**

```
∞                # Push infinite list.
 .¡        }     # Split into three lists by...
   ÂÑgsÑg.S      # 1 if rich, 0 if nothing, -1 if poor.
            ¦ζ   # Remove list of nothings, and zip rich/poor together.
              sè # Grab nth element.

```

Maybe someone can explain why this version doesn't seem to terminate, but when I click "cancel execution" on TIO it finishes with the correct answer, or if you wait 60 seconds you get the correct answer. For a version that terminates "correctly" you could use: `T+nL.¡ÂÑgsÑg.S}¦ζsè` +3 bytes

# Answer
> 6 votes
# JavaScript (ES6),  ~~121 115 113~~  111 bytes

Input is 1-indexed. Outputs as `[poor, rich]`.

```
x=>[(s=h=(n,i=x)=>i?h(++n,i-=(g=(n,k=n)=>k&&!(n%k)*~-s+g(n,k-1))(n)>g([...n+''].reverse().join``)):n)``,h(s=2)]

```

Try it online!

## Commented

### Helper function

```
g = (n,                   // g is a helper function taking n and returning either the
        k = n) =>         // number of divisors or its opposite; starting with k = n
  k &&                    // if k is not equal to 0:
    !(n % k)              //   add either 1 or -1 to the result if k is a divisor of n
    * ~-s                 //   use -1 if s = 0, or 1 if s = 2
    + g(n, k - 1)         //   add the result of a recursive call with k - 1

```

### Main

```
x => [                    // x = input
  ( s =                   // initialize s to a non-numeric value (coerced to 0)
    h = (n,               // h is a recursive function taking n
            i = x) =>     // and using i as a counter, initialized to x
      i ?                 // if i is not equal to 0:
        h(                //   do a recursive call ...
          ++n,            //     ... with n + 1
          i -=            //     subtract 1 from i if:
            g(n)          //       the number of divisors of n (multiplied by ~-s within g)
            >             //       is greater than
            g(            //       the number of divisors of the reversal of n obtained ...
              [...n + ''] //         ... by splitting the digits
              .reverse()  //             reversing them
              .join``     //             and joining back
            )             //       (also multiplied by ~-s within g)
        )                 //   end of recursive call
      :                   // else:
        n                 //   we have reached the requested term: return n
  )``,                    // first call to h for the poor one, with n = s = 0 (coerced)
  h(s = 2)                // second call to h for the rich one, with n = s = 2
]                         // (it's OK to start with any n in [0..9] because these values
                          // are neither poor nor rich and ignored anyway)

```

# Answer
> 4 votes
# Wolfram Language (Mathematica), 152 bytes

```
(a=b=k=1;m=n={};p=AppendTo;While[a<=#||b<=#,#==#2&@@(s=0~DivisorSigma~#&/@{k,IntegerReverse@k++})||If[#<#2&@@s,m~p~k;a++,n~p~k;b++]];{m[[#]],n[[#]]}-1)&

```

Try it online!

If the conjecture is true, then this ***140 bytes*** solution also works

```
(a=k=1;m=n={};p=AppendTo;While[a<=#,#==#2&@@(s=0~DivisorSigma~#&/@{k,IntegerReverse@k++})||If[#<#2&@@s,m~p~k;a++,n~p~k]];{m[[#]],n[[#]]}-1)&

```

Try it online!

Here is ***poor vs rich*** plot

# Answer
> 4 votes
# Jelly, 22 bytes

```
ṚḌ;⁸Æd
Ç>/$Ɠ©#żÇ</$®#Ṫ

```

Try it online!

A full program taking 1-indexed \\$n\\$ on stdin and returning a list of the n-th poor and rich integers in that order.

### Explanation

```
ṚḌ;⁸Æd | Helper link: take an integer and return the count of divisors fof its reverse and the original number in that order

Ṛ      | Reverse
 Ḍ     | Convert back from decimal digits to integer
  ;⁸   | Concatenate to left argument
    Æd | Count divisors

Ç>/$Ɠ©#żÇ</$®#Ṫ | Main link

    Ɠ©          | Read and evaluate a line from stdin and copy to register
   $  #         | Find this many integers that meet the following criteria, starting at 0 and counting up
Ç               | Helper link
 >/             | Reduce using greater than (i.e. poor numbers)
       ż        | zip with
           $®#  | Find the same number of integers meeting the following criteria
        Ç       | Helper link
         </     | Reduce using less than (i.e. rich numbers)
              Ṫ | Finally take the last pair of poor and rich numbers

```

# Answer
> 3 votes
# Python 2, ~~158~~ 153 bytes

<sup> -2 bytes thanks to shooqie</sup>

```
n=input()
p=[];r=[];c=1
while min(len(p),len(r))<=n:[[],r,p][cmp(*[sum(x%-~i<1for i in range(x))for x in c,int(str(c)[::-1])])]+=[c];c+=1
print p[n],r[n]

```

Try it online!

Input is 0-indexed. Outputs as `poor rich`.

# Answer
> 3 votes
# Perl 6, 81 bytes

```
{(*>*,* <*).map(->&c {grep
{[[&c]] map {grep $_%%*,1..$_},$_,.flip},1..*})»[$_]}

```

Try it online!

* `* > *` is an anonymous function that returns true if its first argument is greater than its second. Similarly for `* < *`. The former will select numbers that belong to the rich sequence, the latter will select those that belong to the poor sequence.
* `(* > *, * < *).map(-> &c { ... })` produces a pair of infinite sequences, each based on one of the comparator functions: the rich sequence and the poor sequence, in that order.
* `»[$_]` indexes into both of those sequences using `$_`, the argument to the top-level function, returning a two-element list containing the `$_`th member of the rich sequence and the `$_`th member of the poor sequence.
* `grep $_ %% *, 1..$_` produces a list of the divisors of `$_`.
* `map { grep $_ %% *, 1..$_ }, $_, .flip` produces a two-element list of the divisors of `$_`, and the divisors of `$_` with its digits reversed ("flipped").
* `[[&c]]` reduces that two-element list with the comparator function `&c` (either greater-than or less-than), producing a boolean value indicating whether this number belongs to the rich sequence of the poor sequence.

# Answer
> 3 votes
# Python 2, ~~142~~ 141 bytes

```
f=lambda i,n=1,a=[[],[]]:zip(*a)[i:]or f(i,n+1,[a[j]+[n]*(cmp(*[sum(x%y<1for y in range(1,x))for x in int(`n`[::-1]),n])==1|-j)for j in 0,1])

```

Try it online!

---

---

Non-recursive alternative (very similar to the other Python answers)

# Python 2, 143 bytes

```
i=input()
a=[[],[]];n=1
while~i+len(zip(*a)):([[]]+a)[cmp(*[sum(x%i<1for i in range(1,x))for x in int(`n`[::-1]),n])]+=n,;n+=1
print zip(*a)[i]

```

Try it online!

# Answer
> 2 votes
# Ruby, 128 bytes

Input is *zero-indexed*. Outputs as \[poor, rich\].

```
->n,*a{b=[];i=0;d=->z{(1..z).count{|e|z%e<1}};(x=d[i+=1];y=d[i.digits.join.to_i];[[],b,a][x<=>y]<<i)until a[n]&b[n];[a[n],b[n]]}

```

### Explanation

```
->n,*a{                             # Anonymous function, initialize poor array
       b=[];i=0;                    # Initialize rich array and counter variable
    d=->z{(1..z).count{|e|z%e<1}};  # Helper function to count number of factors
    (                               # Start block for while loop
     x=d[i+=1];                     # Get factors for next number
     y=d[i.digits.join.to_i];       # Factors for its reverse
                                    # (digits returns the ones digit first, so no reversing)
     [[],b,a][x<=>y]                # Fetch the appropriate array based on
                                    #  which number has more factors
                    <<i             # Insert the current number to that array
    )until a[n]&b[n];               # End loop, terminate when a[n] and b[n] are defined
    [a[n],b[n]]                     # Array with both poor and rich number (implicit return)
}                                   # End function

```

Try it online!

# Answer
> 2 votes
# Perl 6, 76 bytes

```
{classify({+(.&h <=>h .flip)},^($_*3+99)){-1,1}[*;$_]}
my&h={grep $_%%*,^$_}

```

Try it online!

I didn't see Sean's Perl 6 answer, but this works in a different way. Note that I've hardcoded the upperbound as `n*3+99`, which is probably not strictly correct. However, I could replace the `*3` with `³` for no extra bytes, which would make the program far less efficient, if more correct.

# Answer
> 2 votes
# Python 2, 152 bytes

```
def f(n):
 a,b=[],[];i=1
 while not(a[n:]and b[n:]):[[],b,a][cmp(*[sum(m%-~i<1for i in range(m))for m in i,int(`i`[::-1])])]+=[i];i+=1
 return a[n],b[n]

```

Try it online!

Ends up being pretty similar to Rod's answer. Returns zero-indexed `n`th poor, rich tuple.

# Answer
> 2 votes
# Icon, ~~180~~ 175 bytes

```
procedure f(n)
a:=[];b:=[];k:=1
while{s:=t:=0
i:=1to k+(m:=reverse(k))&(k%i=0&s+:=1)|(m%i=0&t+:=1)&\x
s>t&n>*a&push(a,k)
s<t&n>*b&push(b,k)
k+:=1;n>*a|n>*b}
return[!b,!a];end

```

Try it online!

# Answer
> 2 votes
# , ~~152~~ 137 bytes

-12 bytes thanks to Giuseppe -3 bytes thanks to digEmAll

```
n=scan()
F=i=!1:2
`?`=sum
while(?n>i)if(n==?(i[s]=i[s<-sign((?!(r=?rev((T=T+1)%/%(e=10^(0:log10(T)))%%10)*e)%%1:r)-?!T%%1:T)]+1))F[s]=T
F

```

Try it online!

`T` is the integer currently being tried; the latest poor and rich numbers are stored in the vector `F`.

The shortest way I could find of reversing an integer was converting it to digits in base 10 with modular arithmetic, then converting back with powers of 10 inverted, but I expect to be outgolfed on this and other fronts.

Explanation (of previous, similar version):

```
n=scan() # input
i=0*1:3  # number of poor, middle class, and rich numbers so far
S=sum
while(S(n>i)){ # continue as long as at least one of the classes has less than n numbers
  if((i[s]=i[
    s<-2+sign(S(!(           # s will be 1 for poor, 2 for middle class, 3 for rich
      r=S((T<-T+1)%/%10^(0:( # reverse integer T with modular arithmetic
        b=log10(T)%/%1       # b is number of digits
        ))%%10*10^(b:0))
      )%%1:r)-               # compute number of divisors of r
      S(!T%%1:T))            # computer number of divisors of T
    ]+1)<=n){                # check we haven't already found n of that class
    F[s]=T
  }
}
F[-2] # print nth poor and rich numbers

```

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

```
{⍵⌷⍉1↓⊢⌸{×-/{≢∪⍵∨⍳⍵}¨⍵,⍎⌽⍕⍵}¨⍳1e3}

```

Try it online!

Thanks to Adám and ngn for helping me golf this monstrosity.

TIO times out for the bigger indices (which require `⍳1e5` or `⍳1e6`) , but given enough time and memory the function will terminate correctly.

# Answer
> 1 votes
# JavaScript (Node.js), ~~190~~ 180 bytes

Outputs as `[poor, rich]`.

```
n=>{let p,r,f=h=i=0;while(f<n){k=d(i),e=d(+(i+"").split``.reverse().join``);if(k<e){p=i;f++}if(k>e&&h<n){r=i;h++}i++}return[p,r]}
d=n=>{c=0;for(j=1;j<=n;j++)if(n%j==0)c++;return c}

```

Try it online!

## Explanation

### `d(n)` Function

This helper finds the number of factors that a number has.

```
d=n=>{              // Equivalent to `function d(n) {
  c=0;              // Counter
  for(j=1;j<=n;j++) // Check every integer from 1 to n
    if(n%j==0)c++;  // If the number is a factor, add 1 to the counter
  return c
};

```

### Main Function

```
n=>{
  let p,r,f=h=i=0; // p -> the poor number, r -> the rich number, f -> the number of poor numbers found, h -> the number of rich numbers found, i -> the current number being checked
  while(f<n){ // While it's found less than n poor numbers (assumes that it will always find the rich number first)
    k=d(i),        // k -> number of factors of i
    e=d(+((i+"").split``.reverse().join``)); // e -> number of factors of reversed i
    if(k<e){p=i;f++}  // If it hasn't found enough poor numbers and i is poor, save it and count it
    if(k>e&&h<n){r=i;h++}  // If it hasn't found enough rich numbers and i is rich, save it and count it
    i++
  };
  return[p,r]
}

```

# Answer
> 1 votes
## C# (Visual C# Interactive Compiler), 221 bytes

```
n=>{int g,h,i,j=9,k,l,m,o,r,p;m=o=r=p=0;while(m<n||o<n){k=g=h=0;l=++j;while(l!=0){k=k*10+l%10;l/=10;}for(i=2;i<j+k;i++){if(j%i<1&&i<j)g++;if(k%i<1&&i<k)h++;}if(g<h&&o<n){o++;p=j;}if(g>h&&m<n){m++;r=j;}}return new{n,p,r};}

```

Try it online!

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


title: Havel-to-da-Hakimi

text:
# Question
Title: Havel-to-da-Hakimi
It was a dark and stormy night. Detective Havel and Detective Hakimi arrived at the scene of the crime.

Other than the detectives, there were 10 people present. They asked the first person, "out of the 9 other people here, how many had you already met before tonight?" The person answered "5". They asked the same question of the second person, who answered "3". And so on. The 10 answers they got from the 10 people were:

```
5 3 0 2 6 2 0 7 2 5

```

The detectives looked at the answers carefully and deduced that there was an inconsistency, and that somebody must be lying. (For the purpose of this challenge, assume that nobody makes mistakes or forgets, and if X has met Y, that means Y has also met X.)

Your challenge for today is, given a sequence of answers to the question "how many of the others had you met before tonight?", apply the Havel-Hakimi algorithm to determine whether or not it's possible that everyone was telling the truth.

If you're feeling up to it, skip ahead to the Challenge section below. Otherwise, try as many of the optional warmup questions as you want first, before attempting the full challenge.

**Optional Warmup 1: eliminating 0's.** Given a sequence of answers, return the same set of answers with all the 0's removed.

```
warmup1([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]) => [5, 3, 2, 6, 2, 7, 2, 5]
warmup1([4, 0, 0, 1, 3]) => [4, 1, 3]
warmup1([1, 2, 3]) => [1, 2, 3]
warmup1([0, 0, 0]) => []
warmup1([]) => []

```

If you want to reorder the sequence as you do this, that's fine. For instance, given `[4, 0, 0, 1, 3]`, then you may return `[4, 1, 3]` or `[1, 3, 4]` or \[`4, 3, 1]` or any other ordering of these numbers.

**Optional Warmup 2: descending sort** Given a sequence of answers, return the sequence sorted in descending order, so that the first number is the largest and the last number is the smallest.

```
warmup2([5, 1, 3, 4, 2]) => [5, 4, 3, 2, 1]
warmup2([0, 0, 0, 4, 0]) => [4, 0, 0, 0, 0]
warmup2([1]) => [1]
warmup2([]) => []

```

**Optional Warmup 3: length check** Given a number `N` and a sequence of answers, return true if `N` is greater than the number of answers (i.e. the length of the sequence), and false if `N` is less than or equal to the number of answers. For instance, given `7` and `[6, 5, 5, 3, 2, 2, 2]`, you would return `false`, because 7 is less than or equal to 7.

```
warmup3(7, [6, 5, 5, 3, 2, 2, 2]) => false
warmup3(5, [5, 5, 5, 5, 5]) => false
warmup3(5, [5, 5, 5, 5]) => true
warmup3(3, [1, 1]) => true
warmup3(1, []) => true
warmup3(0, []) => false

```

**Optional Warmup 4: front elimination** Given a number `N` and a sequence in descending order, subtract 1 from each of the first `N` answers in the sequence, and return the result. For instance, given `N = 4` and the sequence `[5, 4, 3, 2, 1]`, you would subtract 1 from each of the first 4 answers (5, 4, 3, and 2) to get 4, 3, 2, and 1. The rest of the sequence (1) would not be affected:

```
warmup4(4, [5, 4, 3, 2, 1]) => [4, 3, 2, 1, 1]
warmup4(11, [14, 13, 13, 13, 12, 10, 8, 8, 7, 7, 6, 6, 4, 4, 2]) => [13, 12, 12, 12, 11, 9, 7, 7, 6, 6, 5, 6, 4, 4, 2]
warmup4(1, [10, 10, 10]) => [9, 10, 10]
warmup4(3, [10, 10, 10]) => [9, 9, 9]
warmup4(1, [1]) => [0]

```

You may assume that `N` is greater than 0, and no greater than the length of the sequence. Like in warmup 1, it's okay if you want to reorder the answers in your result.

Challenge: the Havel-Hakimi algorithm Perform the Havel-Hakimi algorithm on a given sequence of answers. This algorithm will return true if the answers are consistent (i.e. it's possible that everyone is telling the truth) and false if the answers are inconsistent (i.e. someone must be lying):

Remove all 0's from the sequence (i.e. warmup1).

If the sequence is now empty (no elements left), stop and return true.

Sort the sequence in descending order (i.e. warmup2).

Remove the first answer (which is also the largest answer, or tied for the largest) from the sequence and call it N. The sequence is now 1 shorter than it was after the previous step.

If `N` is greater than the length of this new sequence (i.e. warmup3), stop and return false.

Subtract 1 from each of the first `N` elements of the new sequence (i.e. warmup4).

Continue from step 1 using the sequence from the previous step.

Eventually you'll either return true in step 2, or false in step 5.

You don't have to follow these steps exactly: as long as you return the right answer, that's fine. Also, if you answered the warmup questions, you may use your warmup solutions to build your challenge solution, but you don't have to.

```
hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]) => false
hh([4, 2, 0, 1, 5, 0]) => false
hh([3, 1, 2, 3, 1, 0]) => true
hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16]) => true
hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12]) => true
hh([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3]) => false
hh([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1]) => false
hh([2, 2, 0]) => false
hh([3, 2, 1]) => false
hh([1, 1]) => true
hh([1]) => false
hh([]) => true

```

Detailed example Here's the first pass through the algorithm using the original example:

`[5, 3, 0, 2, 6, 2, 0, 7, 2, 5]` \- Starting sequence

`[5, 3, 2, 6, 2, 7, 2, 5]` \- After step 1, removing 0's.

Step 2: This sequence is not empty, so go on to step 3.

`[7, 6, 5, 5, 3, 2, 2, 2]` \- After step 3, sorting in descending order.

`[6, 5, 5, 3, 2, 2, 2]` \- After step 4, removing the first answer `N = 7`.

Step 5: N (7) is less than or equal to the number of answers remaining in the sequence (7), so go on to step 6.

`[5, 4, 4, 2, 1, 1, 1]` \- After step 6, subtracting 1 from each of the first 7 answers (which is all of them in this case).

At this point you would start over at step 1 with the sequence `[5, 4, 4, 2, 1, 1, 1]`. After your second pass through the algorithm, your sequence will be `[3, 3, 1, 0, 0, 1]`, so start back at step 1 with this sequence. After your third pass you'll have `[2, 0, 0]`. On your fourth pass, you'll stop at step 5, because you'll have `N = 2` and an empty sequence (`[]`), and 2 \> 0, so you will return false.

~ ***Thought this would be fun to golf***

* Shortest code wins.

# Answer
# Jelly,  ~~23~~  12 bytes

```
ṢṚḢ-€+ƊƊƬ>-Ȧ

```

A monadic Link accepting a list which yields `1` if the answers are consistent otherwise `0`.

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

### How?

```
ṢṚḢ-€+ƊƊƬ>-Ȧ - Link: list of integers
        Ƭ    - collect up while results change:
       Ɗ     -   last three links as a monad i.e. f(L):
Ṣ            -     sort                      [min(L),...,max(L)]
 Ṛ           -     reverse                   [max(L),...,min(L)]
      Ɗ      -     last three links as a monad i.e. f([a,b,c,...,x]):
  Ḣ          -       pop head                          a
   -€        -       -1 for each                       [-1,-1,...,-1] (length a)
     +       -       add (vectorises)                  [b-1,c-1,...,x-1,-1,-1,...]
         >-  - greater than -1? (vectorises)
           Ȧ - Any and all? (0 if empty or contains a 0 when flattened, else 1)

```
> 1 votes

# Answer
# Jelly, 22 bytes

```
ḟ0ṢṚ0_1x$}ß`ɗL<¥?Ḣ$1L?

```

Try it online!

A full program that takes the input list of answers as its argument and returns 1 for valid and 0 for impossible.

Thanks to @JonathanAllan for noting an issue with the second version.
> 1 votes

# Answer
# Ruby, 90 bytes

Forgoes zero-pruning in favor of saving 2 bytes. Who needs that, anyways? Instead, I count how many I've decremented (skipping over zeroes) and if I haven't decremented the current largest number fully, then it's a false.

I really hoped that I could forgo sorting as well but alas, things don't always work as planned...

```
->a{b=1;(a.sort_by!(&:-@);i=a.shift;a.map!{|e|i>0&&e>0?(i-=1;e-1):e};b&&=i<1)while[]!=a;b}

```

Try it online!
> 1 votes

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


title: Save my secrets!

text:
# Question
Title: Save my secrets!
I have so many secrets and nowhere to keep them!

The goal is simple: write a program that lets you save a string and have it be protected by a password.

The program will take an alias, password and (optional) secret as parameters.

If this is the first time the program is called with a given alias, then it will store/remember the secret, and output whatever you want.

If the program is called with an alias that has been used before, then it will output the secret for that alias iff the password is the same as the first time the program was run with that alias.

## Other cases

* If its the first time being called with a certain alias and no secret is given - store nothing.
* If the program is called with an alias that has been used, and the password is incorrect - return any kind of error or nothing at all.
* If the program is called with an alias that has been used, the password is correct and a new secret is supplied - output the old secret and replace it with the new one so that next time only the new secret is output.
* If the program is called with an alias that has been used, the password is correct and no new secret is supplied - output the old secret and make sure it doesn't get replaced.

Note: These secrets/passwords do not need to be stored securely

Also note: any alphanumeric input for aliases passwords and secrets should be accepted

Standard rules apply, good luck!

# Answer
# JavaScript (ES6),  ~~60~~  50 bytes

*Saved 10 bytes thanks to @JonasWilms!*

Takes input as either `(alias,password,secret)` or `(alias,password)`. Returns *undefined* the first time a secret is stored, or *false* if the password is incorrect.

```
f=(a,p,s,[P,v]=f[a]||[p])=>p==P&&(f[a]=[P,s||v],v)

```

Try a 1st test case online!

Try a 2nd test case online!

### How?

We define a named function \\$f\\$ whose underlying object is also used to store the passwords and the secrets.

### Commented

```
f = (             // f = named function whose underlying object is used for storage
  a,              // a = alias
  p,              // p = password
  s,              // s = optional secret
  [P, v] = f[a]   // if f[a] is defined, retrieve the password P and the secret v
           || [p] // otherwise, copy p in P
) =>              //
  p == P && (     // if p is not equal to P, yield false; else:
    f[a] = [      //   update f[a]:
      P,          //     save the new password (or leave it unchanged)
      s || v      //     save the new secret if it's defined, or keep the previous one
    ],            //
    v             //   return the previous secret
  )               //

```
> 10 votes

# Answer
# Python 2, ~~94~~ 93 bytes

```
def f(a,p,s=0,d={}):
 q,t=d.get(a,(0,0))
 if q==p:d[a]=p,s or t;return t
 elif q<1<s:d[a]=p,s

```

Try it online!

For once, Python's weird default dict parameter works in my favor...
> 6 votes

# Answer
# Ruby, 64 bytes

Builds a hash for aliases to a single key-pair of `password => secret`. Probably could be more elegant.

```
->a,w,s=p{@q||={};(b=@q[a])?s&&b[w]?b[w]=s:b[w]:s&&@q[a]={w=>s}}

```

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), 34 bytes

```
(c=#~g~#2;#3!=##3||(#~g~#2=#3);c)&

```

Try it online!
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~140~~ ~~138~~ 134 bytes

<sup>-2 bytes thanks to @Expired Data</sup>

```
a=>p=>s=>(a=P.ContainsKey(a)?P[a]:P[a]=new[]{p,s},o:p==a[0]?a[1]:p,s==""?s:p==a[0]?a[1]=s:s).o;var P=new Dictionary<string,string[]>()

```

Try it online!
> 1 votes

# Answer
# Python 2, 77 bytes

```
def f(a,p,s=0,d={}):
 P,S=d.get(a,(p,0))
 if p==P:
	if s>0:d[a]=p,s
	return S

```

Try it online!

Similar to Chas Brown's method.
> 0 votes

---
Tags: code-golf, stateful
---


title: Compressing RLE data to draw ASCII art

text:
# Question
Title: Compressing RLE data to draw ASCII art
> This question is based on what I came up with to answer another question.

Sometimes the questions here ask to draw some ASCII art. One simple way to store the data for the art is RLE (run-length encoding). So:

```
qqqwwwwweeerrrrrtttyyyy

```

becomes:

```
3q5w3e5r3t4y

```

Now to draw a big ASCII art you maybe be getting data like this (ignoring the new line characters):

```
19,20 3(4)11@1$20 11@19,15"4:20 4)19,4:20 11@
   ^^^
   Note that this is "20 whitespaces"

(Character count: 45)

```

The characters used for the ASCII art are never going to be lowercase or uppercase letters or numbers, only signs, marks and symbols but always in the printable ASCII character set.

You want to save some space in that string, so you replace the numbers with the uppercase character set (being 'A' equals to 1, 'B' equals to 2 until 'Z' equals to 26), because you are never going to get more than 26 repetitions of a character. So you get:

```
S,T C(D)K@A$T K@S,O"D:T D)S,D:T K@

(Character count: 34)

```

And finally you notice that some groups of (letter+symbol) are repeating, so you substitute the groups that appear 3 times or more in the string by the lowercase character set, in order or appearance in the string, but storing in a buffer the substitutions made (in the format "group+substitution char" for each substitution), and leaving the rest of the string as is. So the following groups:

```
S, (3 times)
T  (4 times)
K@ (3 times)

```

gets substituted by 'a', 'b' and 'c', respectively, because there are never going to be more than 26 groups repeating. So finally you get:

```
S,aT bK@c
abC(D)cA$bcaO"D:bD)aD:bc

(Character count: 9+24=33)

```

\[The last step only saves 1 byte because the groups that actually save characters after being substituted are the ones appearing 4 times or more.\]

### The challenge

Given a string containing the RLE data to draw an ASCII art (with the restrictions proposed), write the shortest program/function/method you can in order to compress it as described. The algorithm must print/return two strings: the first one containing the dictionary used for the compression, and the second one being the resulting compressed string. You may return the strings as a Tuple, an array, List or whatever, in the given order.

Note that if the string cannot be compressed in the step 2, the algorithm must return an empty string as first return value and the result of the step 1 as second return value.

You do not need to include the result of step 1 in the output values, I just include them in the examples for clarification purposes.

This is , so may the shortest answer for each language win!

### Another test case

```
Input:                   15,15/10$15,15/10"10$10"10$10"10$10"15,15/

Output of step 1:        O,O/J$O,O/J"J$J"J$J"J$J"O,O/

Final algorithm output:  O,aO/bJ$cJ"d
                         abcabdcdcdcdab

---

Input:                   15,15/10$15,15/10"

Output of step 1:        O,O/J$O,O/J"

Final algorithm output:  <empty string>
                         O,O/J$O,O/J"

```

# Answer
## JavaScript (ES6), ~~168~~ 167 bytes

Returns an array of two strings: `[dictionary, compressed_string]`.

```
s=>[(a=(s=s.replace(/\d+/g,n=>C(n|64),C=String.fromCharCode)).match(/../g)).map(v=>s.split(v)[a[v]||3]>=''?D+=v+(a[v]=C(i++)):0,i=97,D='')&&D,a.map(v=>a[v]||v).join``]

```

### Test cases

```
let f =

s=>[(a=(s=s.replace(/\d+/g,n=>C(n|64),C=String.fromCharCode)).match(/../g)).map(v=>s.split(v)[a[v]||3]>=''?D+=v+(a[v]=C(i++)):0,i=97,D='')&&D,a.map(v=>a[v]||v).join``]

console.log(f('19,20 3(4)11@1$20 11@19,15"4:20 4)19,4:20 11@'))
console.log(f('15,15/10$15,15/10"10$10"10$10"10$10"15,15/'))
```
> 3 votes

# Answer
# Python 2, ~~269~~ ~~280~~ ~~268~~ 266 bytes

Nothing fancy going on here. Good opportunity to use some simple regular expressions.

The first version failed for strings containing special characters that were interpreted within the regex. Second version (using re.escape) works with all the test cases. That correction cost 11 bytes.

Second version did not assign substitution characters in order, as required in the problem specification, and as pointed out by @CarlosAlejo. So, back to the drawing board.

## Corrected version, further golfed

* -6 bytes saved by not printing output on two lines
* +3 bytes: Switching to code substitutions via a string to allow meeting the challenge as specified.
* -4 bytes: Since I'm no longer calling re.findall twice, I don't need to rename it
* -5 bytes: switching from for loops to while loops.
* -2 bytes thanks to @Comrade Sparkle Pony

```
import re
S=re.sub
b=a=input()
for i in re.findall('\d{1,2}',a):
 b=S(i, chr(64+int(i)),b)
n,s,p=96,'',0
while p<len(b):
 c=b[p:p+2];f=b.count(c)
 if f>2and not c in s:n+=1;s+=c+chr(n)
 p+=2
p=0
while p<len(s):k=s[p:p+2];v=s[p+2];b=S(re.escape(k),v,b);p+=3
print s,b

```

Try it online!
> 3 votes

# Answer
# Lua, 215 bytes

Just a good bit of pattern matching.

I think Lua's underrated when it comes to golfing... look at all those statements squished together!

```
g,c=string.gsub,string.char
u=g(arg[1],"%d%d?",function(n)return c(n+64)end)l,d=97,""g(u,"..",function(m)n,e=0,g(m,".", "%%%0")g(u,e,function()n=n+1 end)if n>2 then
l,s=l+1,c(l)d,u=d..m..s,g(u,e,s)end
end)print(u,d)

```
> 0 votes

# Answer
# Python 2, 186 bytes

```
from re import*
S=sub('\d+',lambda m:chr(int(m.group(0))+64),input())
Q=[]
for p in findall('[A-Z].',S):
 if S.count(p)>2:a=chr(len(Q)+97);Q+=[p+a];S=sub(escape(p),a,S)
print''.join(Q),S

```

I was hoping to finally find use for `re.subn` :C

```
# first step - convert all numbers to uppercase letters
S=sub('\d+',lambda m:chr(int(m.group(0))+64),input())
# empty list to hold encoding of second step
Q=[]
# find every encoded pair (uppercase letter and some char)
for p in findall('[A-Z].',S):
 # if it occures 3 or move times
 if S.count(p)>2:
  # get lowercase letter to substitute with
  a=chr(len(Q)+97)
  # store encoding into list
  Q+=[p+a]
  # update string - substitute pair with lowercase letter
  S=sub(escape(p),a,S)
# output
# encodings of second step, space, result
# if nothing was compressed at step 2, space would prepend result (of step 1)
print''.join(Q),S

```

Compressed at step 2

Not compressed at step 2

---

# Python 2, 246 bytes

Whole second step done in repl lambda of re.sub. Just for fun.

```
from re import*
Q=[]
S=sub('\d+',lambda m:chr(int(m.group(0))+64),input())
S=sub('[A-Z].',lambda m:(lambda m:S.count(m)>2and(m in Q or not Q.append(m))and chr(Q.index(m)+97)or m)(m.group(0)),S)
print''.join(Q[i]+chr(i+97)for i in range(len(Q))),S

```

Try it online!
> 0 votes

# Answer
# Perl 5 `-pl`, 81 bytes

```
s/\d+/chr$&+64/ge;$b=a;for$a(/([A-Z].)(?=.*\1.*\1)/g){s/\Q$a/$b/g&&($\.=$a.$b++)}

```

Try it online!

Prints the encoded string on the first line, the triples on the second line
> 0 votes

# Answer
# Ruby `-p`, 133 bytes

```
gsub(/(\d+)(.)/){(64+$1.to_i).chr+$2}
c=?`;s=''
$_.scan(/(..)(?=.*\1.*\1)/){s+=$&+c.succ!if !s[$&]}
puts s.scan(/(..)(.)/){gsub$1,$2}

```

Try it online!
> 0 votes

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


title: Hungry Blobs KoTH

text:
# Question
Title: Hungry Blobs KoTH
**Contest Finished! Read comments on blobs to view their score.**

This KoTH is loosely inspired by Primer's Natural Selection Simulation. Your bot is a blob. In order to survive, you must eat pellets to regain energy, which is used to move. With extra energy, blobs can split into two.

### Energy and Movement

Your blob starts off each round with 100 energy, and it has no limit on the amount of energy it can collect. Each round is run in turns, with each blob having the option to move North, East, South, or West in any given turn, or stand still. Moving uses 1 energy, and standing still uses 0.25 energy. The map's side length is `ceil(0.25 * blobCount) * 2 - 1` units, with a minimum of 9 units. All blobs start on the edge of the map, with one placed in each corner and every subsequent blob being placed 2 units away from any others. Every 30 turns, a wave of pellets are placed in random spots around the map, at least 1 unit from any edge. Each time a wave of pellets appears, the quantity of pellets (originally twice the number of blobs or the width of the map, whichever is larger) in the next wave is decreased by 1, forcing the number of blobs to decrease over time. Each pellet restores between 5 and 15 energy. When a blob's energy is less than or equal to 0, it dies.

### Eating

If two or more blobs attempt to occupy the same location, the one with the most energy will eat the others, receiving their energy. If both have equal energy, both vanish.

### Detection and Information

Blobs can see any pellets or other blobs within a distance of 4 units. When their functions are called, blobs are provided with:

* The side length of the map
* The position of the blob on the map
* The positions of all pellets within their search radius, as well as their values
* The positions of all blobs within their search radius, as well as their energy and UIDs
* The energy, UID, and locations of the blob whose function is being executed
* A storage object unique to the blob
* A storage object shared by all blobs related to the blob through splitting

### Splitting

If a blob has more than 50 energy, it can choose to split. Splitting costs 50 energy, and any remaining energy is divided evenly between the two blobs. All blobs are either originals or split copies, with every copy tracing back to an original. All of these together are "relatives." All relatives have one communal storage object. Relatives can still eat each other, and can split, use their own storage object, or collect energy without affecting others.

### Energy Transfer

If two blobs are next to each other (after moving), one of the bots can transfer energy to the other. This is done by returning `SendNorth(amt)`, `SendEast(amt)`, `SendSouth(amt)`, or `SendWest(amt)`, with `amt` being a number representing the amount sent. This can be any amount that the sender can afford, including all of their energy. It is recommended that the blob who is receiving energy is told to stay still through communal storage, so that it does not move away when the energy is being transferred (though the energy would not be deducted from the sender's total in this case).

### Functions, Storage, and UIDs

In order to allow more complex learning behaviors, all blobs will be given an integer UID (Unique Identifer). These UIDs will be randomly generated each map, preventing strategies based on individual targets. When a blob's function is called, it is passed four arguments:

1. The side length of the map as an integer
2. An object with two arrays: `pellets`, and `blobs`. Both arrays contain objects, both having a `pos` property containing the pellet or blob's position formatted as `[x,y]`. Pellets will have an `energy` property, while blobs will have a `uid` property and an `energy` property
3. An object containing various properties of the blob it is passed to: `energy`, `uid`, and `pos`. The `pos` array is formatted as `[x,y]`
4. An object containing the two storage objects of the blob. A `self` property contains an individual storage object which can be modified however the blob sees fit (by manipulating properties of the object that is passed), and a `communal` property which can be modified by any relative.

Blobs are not moved immediately to prevent earlier/later turns having an advantage. All movements are processed in groups (All collisions/eating, then all pellets, then splitting, etc.) If a blob lands on a pellet or smaller blob and, in the process uses its last energy, the blob will still consume the pellet/energy independent of whether that would would bring its total energy above 0.

In order for relative blobs to recognize one another, the communal storage must be used for each blob to record its UID in an array, or through some other system.

### Return Values

In order to move or split, the return value of the function is used. First, the meaning of the cardinal directions in terms of coordinates:

* North = -Y
* East = +X
* South = +Y
* West = -X

Note that `[0,0]` is the *top left corner*, and Y increases as you go down. The return value of the function should follow these rules:

* **To do Nothing:** Return nothing, 0, null, undefined, false, or any other value that equates to false
* **To Move:** Return one of four global variables: North, East, South, or West, which equate to "north", "east", "south", or "west" (which could also be used as a return value)
* **To Split:** Return the global variable SplitNorth, SplitEast, SplitSouth, or SplitWest, the direction indicating where to place the new blob

If a split command is returned and the amount of energy required is greater than or equal to the energy of the blob, nothing will happen. Blobs will not be able to leave the map.

### Predefined Library Functions

There are a few basic functions available by default, to save some time:

**taxiDist(pt1, pt2)**

Returns the taxicab distance between two points (X distance plus Y distance).

```
taxiDist([0, 0], [2, 2]) //4
taxiDist([3, 4], [1, 5]) //3
taxiDist([1.25, 1.3], [1.3, 1.4]) //0.15
taxiDist([0, 0], [5, 2.5], 2.5) //3
taxiDist([0, 0], [2, 4], 2.5) //2.4

```

**hypotDist(pt1, pt2)**

Returns distance between two points according to the pythagorean theorem

```
hypotDist([0, 0], [5, 12]) //13
hypotDist([4, 6], [8, 9]) //5
hypotDist([0, 1], [2, 1]) //2
hypotDist([1, 1], [2, 2]) //sqrt(2)

```

**modDir(dir, amt)**

Takes the inputted direction, rotates 90 degrees clockwise `amt` times, then returns the new value.

```
modDist(North, 1) //East
modDist(East, 2) //West
modDist(West, 3) //South
modDist(South, 4) //South

```

### Example Blob

This blob will not move until it finds a pellet nearby. Then, it will move in the direction it thinks is most likely to reward it. If its energy is ever above 150, it will split.

```
function(map, near, me, storage) {
    if (me.energy > 150)
        return SplitNorth;
    if (!near.pellets.length)
        return null;
    var dirs = [0, 0, 0, 0];
    for (let p, i = 0; i < near.pellets.length; i++) {
        p = near.pellets[i];
        dirs[0] += me.pos[1] - p.pos[1];
        dirs[1] += p.pos[0] - me.pos[0];
        dirs[2] += p.pos[1] - me.pos[1];
        dirs[3] += me.pos[0] - p.pos[0];
    }
    return [North, East, South, West][dirs.indexOf(Math.max(...dirs))];
}

```

### Rules

* Standard Loopholes are prohibited. Also, no Unstandard Loopholes.
* No blob may attempt to modify or read any data not passed to it via its parameters
* No blob may attempt to modify a return-value variable to sabotage other blobs
* A round lasts until the only remaining blobs are relatives
* No blob may modify data by injecting functions into its parameters which modify values using the `this` keyword
* All submissions must either be in Javascript or a language which is not too different from Javascript (Python, for example). All answers will be converted to Javascript for the competition.
* The winner is the blob which has collected the highest amount of energy in total across all rounds (from either pellets or consuming smaller blobs that are not relatives)

**Controller:** https://gist.github.com/Radvylf/1facc0afe24c5dfd3ada8b8a2c493242

**Chatroom:** https://chat.stackexchange.com/rooms/93370/hungry-blobs-koth

# Answer
> 3 votes
# Introvert

The Introvert doesn't like other blobs. When it sees an unrelated blob, it eats it if it can, and begrudgingly accepts its presence it if it can't, though running away if it sees signs of aggression. When it sees a *related* blob, it distances itself. However, it can't help but split apart a lot.

### Technical Details

The core feature of this blob is to split apart and spread out so as to maximize the combined vision of the blobs. It also employs a system to prevent two of them from competing over a pellet.

```
function introvert(mapSize, vision, self, storage) {
  if (!storage.communal.friends)
    storage.communal.friends = {};
  if (!storage.communal.claims)
    storage.communal.claims = {};
  storage.communal.friends[self.uid] = true;
  for (var i in storage.communal.claims)
    if (storage.communal.claims[i] === self.uid) {
      storage.communal.claims = {};
      break;
    }
  var food = {};
  for (var p of vision.pellets) {
    var score = p.energy - taxiDist(p.pos, self.pos);
    if (score > 0)
      food[p.pos] = score;
  }
  var danger = {};
  for (var i = 0; i < mapSize; i++) {
    danger['-1,' + i] = true;
    danger[mapSize + ',' + i] = true;
    danger[i + ',' + mapSize] = true;
    danger[i + ',-1'] = true;
  }
  var relatives = {};
  for (var b of vision.blobs) {
    if (b.uid in storage.communal.friends) {
      relatives[b.pos] = true;
    } else if (!storage.self.justSplit && b.energy < self.energy - taxiDist(b.pos, self.pos) * 0.75) {
      var score = b.energy - taxiDist(b.pos, self.pos) * 1.25;
      if (score > 0)
        food[b.pos] = score;
    } else {
      danger[b.pos] = true;
      danger[b.pos[0] + ',' + (b.pos[1] - 1)] = true;
      danger[b.pos[0] + 1 + ',' + b.pos[1]] = true;
      danger[b.pos[0] + ',' + (b.pos[1] + 1)] = true;
      danger[b.pos[0] - 1 + ',' + b.pos[1]] = true;
    }
  }
  storage.self.justSplit = !danger[self.pos] && self.energy > 150;
  function fromData(n) {
    return n.split(',').map(s => parseInt(s));
  }
  function fs(f) {
    return food[f] / taxiDist(f, self.pos);
  }
  var target = Object.keys(food).filter(f => !(f in storage.communal.claims)).map(fromData).sort((a, b) => fs(b) - fs(a))[0];
  if (target)
    storage.communal.claims[target] = self.uid;
  function ms(m) {
    if (danger[m])
      return 99999999;
    var dists = Object.keys(relatives).map(r => hypotDist(fromData(r), m));
    return (target ? taxiDist(target, m) : 0) - (dists.length ? dists.reduce((a, b) => a + b) / dists.length : 0);
  }
  var candidates = [
    {p: self.pos},
    {p: [self.pos[0], self.pos[1] - 1], d: storage.self.justSplit ? SplitNorth : North},
    {p: [self.pos[0] + 1, self.pos[1]], d: storage.self.justSplit ? SplitEast : East},
    {p: [self.pos[0], self.pos[1] + 1], d: storage.self.justSplit ? SplitSouth : South},
    {p: [self.pos[0] - 1, self.pos[1]], d: storage.self.justSplit ? SplitWest : West}
  ];
  if (storage.self.justSplit)
    candidates.shift();
  return candidates.sort((a, b) => ms(a.p) - ms(b.p))[0].d;
}

```

# Answer
> 1 votes
## Animated Meal

A simple bot, just to start off the competition. Finds the nearest coin, and goes toward it. Based off the example bot.

```
function(map, near, me, storage) {
    var targs = near.pellets.map(el => taxiDist(el.pos, me.pos));
    var targ = near.pellets[targs.indexOf(Math.max(...targs))].pos;
    if (targ[0] == me.pos[0])
        return targ[1] < me.pos[1] ? North : South;
    return targ[0] < me.pos[0] ? West : East;
}

```

# Answer
> 1 votes
# bloblib tester

```
function(map, near, me, storage) {
    // BlobLib, the main purpose of this post
    const bloblib = {
        // Returns only pellets and blobs that are within the immediate neighbourhood (within 1 space of) me
        getNeighbours: (known) => {
            let neighbours = {};
            neighbours.pellets = known.pellets.filter(x => x.pos[0] >= me.pos[0] - 1 && x.pos[0] <= me.pos[0] + 1 && x.pos[1] >= me.pos[1] - 1 && x.pos[1] <= me.pos[1] + 1);
            neighbours.blobs = known.blobs.filter(x => x.pos[0] >= me.pos[0] - 1 && x.pos[0] <= me.pos[0] + 1 && x.pos[1] >= me.pos[1] - 1 && x.pos[1] <= me.pos[1] + 1);
            return neighbours;
        },
        // Gets the blob or pellet at the given location
        getByPos: (pos, known) => {
            let pellets = known.pellets.filter(x => x.pos[0] == pos[0] && x.pos[1] == pos[1]);
            let blobs = known.blobs.filter(x => x.pos[0] == pos[0] && x.pos[1] == pos[1]);
            if (blobs.length) return blobs[0];
            if (pellets.length) return pellets[0];
            return null;
        },
        // Returns a 2d array of size, containing any known blobs or pellets
        areaMatrix: (size, known) => {
            let matrix = [];
            for (let x = 0; x < size; x++) {
                let row = [];
                for (let y = 0; y < size; y++) {
                    let realPos = [me.pos[0] - (x + Math.floor(size / 2)), me.pos[1] - (y + Math.floor(size / 2))];
                    row.push(getByPos(realPos, known));
                }
                matrix.push(row);
            }
            return matrix;
        },
        // Gets a cardinal direction pointing from from to to
        cardDirTo: (to, from = me.pos) => {
            let diff = bloblib.multiDist(from, to);

            if (diff[0] == 0 && diff[1] == 0) return null;

            if (Math.abs(diff[0]) > Math.abs(diff[1])) {
                // Gunna be east or west
                return diff[0] > 0
                    ? East
                    : West;
            } else {
                return diff[1] > 0
                    ? South
                    : North;
            }
        },
        // Returns a vector of the X and Y distances between from and to
        multiDist: (from, to) => {
            return [to[0] - from[0], to[1] - from[1]]
        },
        // Gets the closest object in objs to position to
        getClosest: (objs, to = me.pos) => {
            if (!objs || !objs.length) return null;

            let sorted = objs.concat().sort((a, b) => taxiDist(a.pos, to) - taxiDist(b.pos, to));
            return sorted[0];
        },
        // Should be run at startup. Calculates which directions are unsafe to move in
        dangerSense: (origin) => {
            let neighbours = bloblib.getNeighbours(near);
            let matrix = bloblib.areaMatrix(3, neighbours);

            if (me.pos[1] == 0 || (matrix[1,0] && isThreat(matrix[1,0]))) bloblib.unsafeDirs.push(North);
            if (me.pos[0] == map - 1 || (matrix[2,1] && isThreat(matrix[2,1]))) bloblib.unsafeDirs.push(East);
            if (me.pos[0] == 0 || (matrix[0,1] && isThreat(matrix[0,1]))) bloblib.unsafeDirs.push(West);
            if (me.pos[1] == map - 1 || (matrix[1,2] && isThreat(matrix[1,2]))) bloblib.unsafeDirs.push(South);
        },
        isThreat: (blob) => {
            if (!blob.uid) return false;
            if (storage.communal.blobs.includes(blob.uid)) return true;

            return blob.energy >= me.energy - 1;
        }
        // Attempts to move in the given direction
        // Rotates the direction 90 if it can't safely move
        attemptMove: (dir = North) => {
            for (let i = 0; i < 4; i++) {
                if (bloblib.unsafeDirs.includes(dir)) dir = modDir(dir, i);
                else return dir;
            }
            return null;
        },
        // Attempts to split in the given direction
        // Rotates the direction 90 if it can't safely split
        attemptSplit: (dir = SplitNorth) => {
            for (let i = 0; i < 4; i++) {
                if (bloblib.unsafeDirs.includes(dir)) dir = modDir(dir, i);
                else return dir;
            }
            return null;
        },
        // Returns the next direction in which to move toward pos
        // Don't bother checking if we have enough energy, because if
        // we have < 1 energy we're basically dead anyway
        moveTo: (pos) => {
            return bloblib.performAction(bloblib.attemptMove(bloblib.cardDirTo(pos)));
        },
        // Simply registers the action in communal history, then returns it unmodified
        performAction: (action) => {
            storage.communal.history[me.uid].push(action);
            return action;
        },

        // Stores directions in which there is another blob
        // This wouldn't make sense to store across turns, so we don't bother
        unsafeDirs: []
    };
    bloblib.dangerSense(me.pos);

    // Register this blob
    if (!storage.communal.blobs) storage.communal.blobs = [];
    if (!storage.communal.blobs.includes(me.uid)) storage.communal.blobs.push(me.uid);

    // Register history for this blob
    if (!storage.communal.history) storage.communal.history = {};
    if (!storage.communal.history[me.uid]) storage.communal.history[me.uid] = [];

    // Split if we can and there are fewer than 10 blobs in our community
    if (me.energy > 150 && storage.communal.blobs.length < 10) {
        let split = bloblib.getSplit();
        if (split) return split;
    }

    // If we can't see any pellets or blobs, don't do anything
    if (!near.pellets.length && !near.blobs.length) return null;

    // Move toward the nearest pellet
    return bloblib.moveTo(bloblib.getClosest(near.pellets));
}

```

The actual bot is fairly simple, but this is more designed as a proof of concept of `bloblib`, a collection of functions and functionality I plan to use and develop across other bots (feel free to use/expand on it yourself too)

In short, this bot does the following:

```
If energy > 150 and blobs_in_team < 10: Try to split
If visible_pellets = 0 and visible_blobs = 0: do nothing
Move toward the closest pellet in a safe way
    that avoids moving into other stronger or equal blobs
    or off the edge of the map

```

# Answer
> 1 votes
# Greedy Coward

```
import random

def greedy_coward(map_length, near, me, storage):
    interesting_objects = [] #objects I can eat
    bad_objects = [] #objects that eat me
    allowed_directions = ["North", "East", "South", "West"]

    # add pellets to objects that I'm interested in
    for i in near.pellets:
        interesting_objects.append(i)

    # figure out which blobs are good and which are bad
    for i in near.blobs:
        # if I'm under or equal powered, add it to bad_objects
        if i.energy >= me.energy:
            bad_objects.append(i)
        # if I can eat it, add it to interesting objects.
        else:
            interesting_objects.append(i)

    # if there are any bad objects, process them.
    if not len(bad_objects) == 0:

        # find the nearest bad object and make sure I don't move towards it
        bad_objects_distances = []
        for i in bad_objects:
            bad_objects_distances.append(taxiDist(i.pos, me.pos))
        worst_object = bad_objects[bad_objects_distances.index(min(bad_objects))]

        # find the direction of the worst object
        bad_object_xy_distance = [worst_object.pos[0] - me.pos[1], worst_object.pos[1] - me.pos[1]]
        closest_number = min(bad_object_xy_distance)
        bad_object_direction_vague = [["West","East"],["North","South"]][bad_object_xy_distance.index(closest_number)]
        if closest_number < 0:
            bad_object_direction = bad_object_direction_vague[1]
        else:
            bad_object_direction = bad_object_direction_vague[0]

        # remove bad object direction from allowed directions
        allowed_directions.remove(bad_object_direction)

    # process interesting objects if they exist
    if not len(interesting_objects) == 0:

        # find the nearest interesting object
        interesting_objects_distances = []
        for i in interesting_objects:
            interesting_objects_distances.append(taxiDist(me.pos, i.pos))
            interesting_object = interesting_objects[interesting_objects_distances.index(min(interesting_objects_distances))]

        # find the direction of the best object
            good_object_xy_distance = [interesrting_object.pos[0] - me.pos[1], interesting_object.pos[1] - me.pos[1]]
            closest_number = min(good_object_xy_distance)
            good_object_direction_vague = [["West","East"],["North","South"]][good_object_xy_distance.index(closest_number)]
            if closest_number < 0:
                good_object_direction = good_object_direction_vague[1]
            else:
                good_object_direction = good_object_direction_vague[0]

        # if the good and bad objects are in the same direction, move randomly in a different direction
        if good_object_direction == bad_object_direction:
            return random.choice(allowed_directions)
        else: # otherwise go towards the good object.
            return good_object_direction

    return 0 # when in doubt, stay still

```

Or, in JavaScript,

```
function(map_length, near, me, storage) {
    var interesting_objects = []; //objects I can eat
    var bad_objects = []; //objects that eat me
    var allowed_directions = ["north", "east", "south", "west"];

    //add pellets to objects that I'm interested in
    for (let i in near.pellets) {
        interesting_objects.push(near.pellets[i]);
    }

    //figure out which blobs are good and which are bad
    for (let i in near.blobs) {
        //if I'm under or equal powered, add it to bad_objects
        if (near.blobs[i].energy >= me.energy) {
            bad_objects.push(near.blobs[i]);
        }
        //if I can eat it, add it to interesting objects.
        else {
            interesting_objects.push(near.blobs[i]);
        }
    }

    //if there are any bad objects, process them.
    if (bad_objects.length) {

        //find the nearest bad object and make sure I don't move towards it
        var bad_objects_distances = [];
        for (i in bad_objects) {
            bad_objects_distances.push(taxiDist(bad_objects[i].pos, me.pos));
        }
        var worst_object = bad_objects[bad_objects_distances.indexOf(Math.min(...bad_objects_distances))];

        //find the direction of the worst object
        var bad_object_xy_distance = [worst_object.pos[0] - me.pos[1], worst_object.pos[1] - me.pos[1]];
        var closest_number = Math.min(...bad_object_xy_distance.map(el => Math.abs(el)));
        var bad_object_direction_vague = [["west","east"],["north","south"]][bad_object_xy_distance.map(el => Math.abs(el)).indexOf(closest_number)];
        if (closest_number < 0) {
            var bad_object_direction = bad_object_direction_vague[1];
        } else {
            var bad_object_direction = bad_object_direction_vague[0];
        }

        //remove bad object direction from allowed directions
        allowed_directions = allowed_directions.filter(el => el !== bad_object_direction);

    }

    //process interesting objects if they exist
    if (interesting_objects.length) {

        //find the nearest interesting object
        var interesting_objects_distances = [];
        for (i in interesting_objects) {
            interesting_objects_distances.push(taxiDist(me.pos, interesting_objects[i].pos))
        }
        var interesting_object = interesting_objects[interesting_objects_distances.indexOf(Math.min(...interesting_objects_distances))];

        //find the direction of the best object
        var good_object_xy_distance = [interesting_object.pos[0] - me.pos[1], interesting_object.pos[1] - me.pos[1]];
        var closest_number = Math.min(...good_object_xy_distance.map(el => Math.abs(el)));
        var good_object_direction_vague = [["west","east"],["north","south"]][good_object_xy_distance.map(el => Math.abs(el)).indexOf(closest_number)];
        if (closest_number < 0) {
            var good_object_direction = good_object_direction_vague[1];
        } else {
            var good_object_direction = good_object_direction_vague[0];
        }

        //if the good and bad objects are in the same direction, move randomly in a different direction
        if (good_object_direction == bad_object_direction) {
            return allowed_directions[allowed_directions.length * Math.random() | 0];
        } else{ //otherwise go towards the good object.
            return good_object_direction;
        }

    }

    return 0; //when in doubt, stay still
}

```

This bot isn't very interesting. It acts according to two priorities:

1. Don't get eaten.
2. Eat the nearest thing.

It never spits to maximize its ability to eat other things.

# Answer
> 1 votes
# SafetyBlob

This bot uses some of the same logic as Safetycoin from the previous KOTH.

### How it functions

This bot will head towards food which it can either reach before any bigger bots do or at the same time/before a smaller bot. If it can't see any food which meets these criteria, it will move in a random direction(biased towards the center). If it gets to 150 energy and can not see safe food, it will split in one of the directions it has labeled as safe to move.

This bot doesn't keep track of its own children but they should not collide anyway due to the safety mechanisms.

```
 function SafetyBlob(map,local,me,stor){
  var center=(map/2|0)+1;
  var [x,y]=me.pos
  var uid=me.uid
  var others=local.blobs;
  var pellets=local.pellets;
  //Bot doesnt use storage because it just tries to find what it can.
  var willSplit=me.energy>150;
  var bestSafePelletValue=0;
  var bestSafePellet=null;
  var pellet;
  var other;
  //Head towards the best valued pellet (energy/distance) which can be reached before any larger or equal sized blobs or can be reached at the same time as smaller blobs
  for(i=0;i<pellets.length;i++){
    pellet=pellets[i]
    if(bestSafePelletValue<=pellet.energy/taxiDist(pellet.pos,me.pos)){
      for(j=0;j<others.length;j++){
        other=others[j];
        if(other.energy<me.energy){
          if(taxiDist(pellet.pos,me.pos)<=taxiDist(other.pos,pellet.pos)){
            if(taxiDist(pellet.pos,me.pos)<taxiDist(bestSafePellet.pos,me.pos)){
              bestSafePellet=pellet;
              bestSafePelletValue=pellet.energy/taxiDist(pellet.pos,me.pos);
            }
          }
        }
        if(other.energy>=me.energy){
          if(taxiDist(pellet.pos,me.pos)<taxiDist(other.pos,pellet.pos)){
            if(taxiDist(pellet.pos,me.pos)<taxiDist(bestSafePellet.pos,me.pos)){
              bestSafePellet=pellet;
              bestSafePelletValue=pellet.energy/taxiDist(pellet.pos,me.pos);
            }
          }
        }
      }
    }
  }

  if(bestSafePellet){
    [xPellet,yPellet]=bestSafePellet.pos;
    if(x<xPellet&&Math.abs(x-xPellet)>=Math.abs(y-yPellet)){
      return East;
    }
    if(x<xPellet&&Math.abs(x-xPellet)>=Math.abs(y-yPellet)){
      return West;
    }
    if(y<yPellet&&Math.abs(x-xPellet)<Math.abs(y-yPellet)){
      return South;
    }
    if(y<yPellet&&Math.abs(x-xPellet)<Math.abs(y-yPellet)){
      return North;
    }
  }

  var validMoves=["North","East","South","West","Stay"];
  var removeIndex=0;
  var safeEnergy;
  if(x==0)
    validMoves.splice(validMoves.indexOf("West"));
  if(x==map)
    validMoves.splice(validMoves.indexOf("East"));
  if(y==0)
    validMoves.splice(validMoves.indexOf("North"));
  if(y==map)
    validMoves.splice(validMoves.indexOf("South"));

  var possibleMoves=[...validMoves];
  possibleMoves.splice(possibleMoves.indexOf("Stay"));
  //If there is no safe pellet try to stick somewhat towards the middle
  //Ignore enemies unless at 2 distance from self and there is no safe pellet
  for(i=0;i<others.length;i++){
    other=others[i];
    safeEnergy=willSplit?(me.energy-50)/2:me.energy;
    if((other.energy>=safeEnergy)&&(taxiDist(me.pos,other.pos)<=2)){
      if(taxiDist(me.pos,other.pos)==1){
        if((removeIndex=validMoves.indexOf("Stay"))>=0){
          validMoves.splice(removeIndex,1)
        }
      }
      if(other.pos[0]<x){
        if((removeIndex=validMoves.indexOf("West"))>=0){
          validMoves.splice(removeIndex,1)
        }
      }
      if(other.pos[1]<y){
        if((removeIndex=validMoves.indexOf("South"))>=0){
          validMoves.splice(removeIndex,1)
        }
      }
      if(other.pos[0]>x){
        if((removeIndex=validMoves.indexOf("East"))>=0){
          validMoves.splice(removeIndex,1)
        }
      }
      if(other.pos[1]>y){
        if((removeIndex=validMoves.indexOf("North"))>=0){
          validMoves.splice(removeIndex,1)
        }
      }
    }
  }
  //If there are no safe moves move in a random direction (Reduce energy as much as possible with a slight chance of survival)
  if(!validMoves.length){
    switch (possibleMoves[Math.random()*possibleMoves.length|0]){
      case "North":
        return North;
      case "South":
        return South;
      case "East":
        return East;
      case "West":
        return West;
    }
  }
  //If there are safe moves bias towards moving towards the center block of 1/3 of the way from the sides
  if(!willSplit){
    //bias moving towards near the center
    biasedMoves=[];
    for(var i=0;i<validMoves.length;i++){
      switch(validMoves[i]){
        case "North":
          biasedMoves=biasedMoves.concat(y>center?"0".repeat(center/3|0).split``:"0".repeat(y-center).split``);
          break;
        case "South":
          biasedMoves=biasedMoves.concat(y<center?"2".repeat(center/3|0).split``:"2".repeat(center-y).split``);
          break;
        case "East":
          biasedMoves=biasedMoves.concat(y>center?"1".repeat(center/3|0).split``:"1".repeat(x-center).split``);
          break;
        case "West":
          biasedMoves=biasedMoves.concat(y<center?"3".repeat(center/3|0).split``:"3".repeat(center-x).split``);
          break;
        case "Stay":
          biasedMoves=biasedMoves.concat(["4"]);
          break;
      }
    }
  }
  if(willSplit){
    switch (biasedMoves[Math.random()*biasedMoves.length|0]){
      case "0":
        return SplitNorth;
      case "2":
        return SplitSouth;
      case "1":
        return SplitEast;
      case "3":
        return SplitWest;
      case "4":
        return Stay;
    }
  }
  else{
    switch (biasedMoves[Math.random()*biasedMoves.length|0]){
      case "0":
        return North;
      case "2":
        return South;
      case "1":
        return East;
      case "3":
        return West;
      case "4":
        return Stay;
    }
  }
}

```

---
Tags: king-of-the-hill
---