# Question
Title: I'm walking around manhattan, how far am I from my hotel?
**The unnecessary and convoluted story**

I am walking around manhattan, block by block and my feet have gotten tired and want to go back home.

The traffic is pretty bad, but fortunately I'm very rich and I have a helicopter on standby at the hotel. But I need them to know how much fuel to pack for the flight and for that they need to know my direct distance from the hotel. I did remember which blocks I walked and can tell them what route I took. This distance needs to be precise though, if they are too short we won't make it back, too long and I've bought fuel I can't use.

Can you write me a program to convert that into the distance they will have to travel on their flight to fetch me?

**Specification:**

Write me a function that:

1. Accepts a list or string of blocks walked relative to an arbitrary grid:
    * **U** p, **D** own, **L** eft and **R** ight.
    * Can be either upper or lower case - eg. if its shorter to use `u` instead of `U` go ahead.
    * An invalid direction has undefined behaviour - eg. a direction of **X** can cause a failure.
2. Returns a float/decimal/double that is twice the straight line distance from the point of origin.

For illustration and clarification:

My trip could have just as easily been recorded as `"luluu..."` or `['l','u','l'...]` but it must be recorded as Up, Down, Left, Right.

# Answer
> 34 votes
### J, 17 characters

```
2*|+/0j1^'urdl'i.

```

Uses the fact, that the powers of `j` represent the proper directions.

* `'urdl'i.` take string and calculate indices (0 for 'u', 1 for 'r', ...)
* `0j1^` transforms into the direction in the complex plane using the corresponding power of `j`.
* `+/` sums up the single steps
* `2*|` two times the modulus

Example:

```
> 2*|+/0j1^'urdl'i.'uuuudrrrl'
7.2111

```

# Answer
> 14 votes
## Python 2.7 56 58 56 51 48

With the stolen Number One Dime from Scrooge McDuck, I made my fortune and now have more wealth than Scrooge.

```
y=lambda s:2*abs(sum(1j**(ord(i)%15)for i in s))

```

## Python 2.7 - 61 53 50 (case insensitive)

```
y=lambda s:2*abs(sum(1j**(ord(i)%16%9)for i in s))

```

**Implementation**

```
>>> from random import sample
>>> y=lambda s:2*abs(sum((-1j)**(ord(i)%15)for i in s))
>>> path=sample('RLUD'*1000, 100)
>>> y(path)
20.0
>>> path=sample('RLUD'*1000, 100)
>>> y(path)
34.058772731852805

```

# Answer
> 5 votes
## APL (29)

```
{|+/2 0j2×-⌿2 2⍴+/'URDL'∘.=⍵}

```

e.g.

```
     {|+/2 0j2×-⌿2 2⍴+/'URDL'∘.=⍵} 'UUUUDRRRL'
7.211102551

```

Explanation:

* `+/'URDL'∘.=⍵`: see how often the characters `URDL` occur in the argument
* `-⌿2 2⍴`: subtract the `U` value from the `D` value, and the `R` value from the `L` value
* `2 0j2×`: multiply the vertical value by `2` and the horizontal value by `2i`
* `+/`: sum
* `|`: magnitude

# Answer
> 5 votes
# Ruby 1.9+ (67)

```
f=->s{2*(((g=s.method :count)[?U]-g[?D])**2+(g[?R]-g[?L])**2)**0.5}

```

Example

```
f["DRUULULLULL"] => 10.0
f["UUUUDRRRL"] => 7.211102550927978

```

# Answer
> 4 votes
## perl6: 44 chars

```
2*abs [+] i <<**>>%(<U R D L>Z ^4){get.comb}

```
* `get.comb` gets one line of input and splits into characters
* `<U R L D>` is a list of words, chars in this case
* `(1,2,3) Z (4,5,6)` == `(1,2), (2,5), (3,6)`, so it zips 2 lists into each other, making a list of parcels that `%()` turns into a hash
* `<<**>>` does pairwise `**`, extending the shorter list to fit the longer. Shorter list happens to only be `i`
* `[+]` sums all elements of a list, `abs` takes the modulus for complex numbers

Yes, I removed all possible spaces.

# Answer
> 3 votes
# Mathematica ~~92~~ 49

Calle deserves full credit for streamlining the code.

```
f@l_:=2 N@Norm[Tr[l/.{"r"→1,"l"→-1,"u"→I,"d"→-I}]]

```

**Example**

```
f[{"u", "u", "u", "u", "d", "r", "r", "r", "l"}]

```

> 7.2111

# Answer
> 3 votes
## PHP, 67

```
function f($a){foreach($a as$d)@$$d++;return 2*hypot($U-$D,$L-$R);}

```

Example:

```
<?php
var_dump(f(array('U', 'U', 'U', 'U', 'D', 'R', 'R', 'R', 'L')));

>float(7.211102550928)

```

# Answer
> 3 votes
# Julia, 45

```
f(l)=2*abs(sum([im^(c=='d'?3:c) for c in l]))

```

Stole the `i` to powers trick. Also all the characters except d have values that work as acceptable powers for `i`.

# Answer
> 2 votes
## Python 2.7 - 65

Nice and short one, this uses complex numbers to step through the plane:

```
x=lambda s:2*abs(sum([[1,-1,1j,-1j]['RLUD'.index(i)]for i in s]))

```

Props to DSM and Abhijit in other questions that showed me the use of `1j` to calculate this.

# Answer
> 2 votes
### R, ~~86~~ ~~74~~ 56 characters

Ok it's actually way shorter with imaginary numbers indeed:

```
2*Mod(sum(sapply(scan(,""),switch,u=1i,d=-1i,l=-1,r=1)))

```

Usage:

```
> 2*Mod(sum(sapply(scan(,""),switch,u=1i,d=-1i,l=-1,r=1)))
1: u u u u d r r r l
10:
Read 9 items
[1] 7.211103

```

**Old solution at 74 characters with xy coords:**

```
2*sqrt(sum(rowSums(sapply(scan(,""),switch,u=0:1,d=0:-1,l=-1:0,r=1:0))^2))

```

Usage:

```
> 2*sqrt(sum(rowSums(sapply(scan(,""),switch,u=0:1,d=0:-1,l=-1:0,r=1:0))^2))
1: u u u u d r r r l
10:
Read 9 items
[1] 7.211103

```

Takes input as stdin, need to be lower-case and space-separated. Use x-y coordinates starting from (0,0).

# Answer
> 2 votes
# k (~~50~~ 49)

```
{2*sqrt x$x:0 0f+/("udlr"!(1 0;-1 0;0 -1;0 1))@x}

```

Example

```
{2*sqrt x$x:0 0f+/("udlr"!(1 0;-1 0;0 -1;0 1))@x}"uuuudrrrl"
7.211103

```

# Answer
> 2 votes
## Java, 185, 203, 204, 217, 226

```
class A{public static void main(String[] a){int x=0,y=0;for(int i=0;i<a[0].length();i++) switch(a[0].charAt(i)){case'U':y++;break;case'D':y--;break;case'L':x++;break;case'R':x--;}System.out.print(Math.hypot(x,y)*2);}}

```

I did assume that each "U" was "1 up", so two units up would be "UU"

Edit: swapped out switch for ifs

```
class A{public static void main(String[]a){int x=0,y=0;for(int i=0;i<a[0].length();i++){int c=a[0].charAt(i);if(c=='U')y++;if(c=='D')y--;if(c=='L')x++;if(c=='R')x--;}System.out.print(Math.hypot(x,y)*2);}}

```

Moved for iterator

```
class A{public static void main(String[]a){int x=0,y=0;for(int i=0;i<a[0].length();){int c=a[0].charAt(i++);if(c=='U')y++;if(c=='D')y--;if(c=='L')x++;if(c=='R')x--;}System.out.print(Math.hypot(x,y)*2);}}

```

No longer takes input as string, rather array of directions

```
class A{public static void main(String[]a){int x=0,y=0;for(String s:a){char c=s.charAt(0);if(c=='U')y++;if(c=='D')y--;if(c=='L')x++;if(c=='R')x--;}System.out.print(Math.hypot(x,y)*2);}}

```

# Answer
> 2 votes
# T-SQL, 158

```
IF PATINDEX('%[^UDLR]%', @s)=0 select 2*sqrt(power(LEN(REPLACE(@s,'U',''))-LEN(REPLACE(@s,'D','')),2)+power(LEN(REPLACE(@s,'L',''))-LEN(REPLACE(@s,'R','')),2))

```

The @s is the input string of varchar(max) type

# Answer
> 2 votes
## ES6, ~~77~~ 69

Definition:

```
f=s=>{u=d=l=r=0;for(c of s)eval(c+'++');return 2*Math.hypot(u-d,l-r)}

```

Usage:

```
>>> f('uuuudrrrl')
7.211102550927979
>>> f( 'uuuudrrrl'.split('') )
7.211102550927979

```
* Accepts string OR array (lowercase)
* Doesn't use imaginary numbers
* *Would not have been possible just 3 days before OP posted the question*; that is, it only runs in Firefox 27+ (and maybe also Chrome with experimental stuff enabled, haven't tested :)!!

(Inspired partially by Boann's answer.)

# Answer
> 2 votes
## JavaScript - 142 characters - no eval()

```
function r(a){return Math.sqrt(Math.pow(a.match(/u/g).length-a.match(/d/g).length,2)+Math.pow(a.match(/l/g).length-a.match(/r/g).length,2))*2}

```

where a is a string like 'uudrrl'

use like this -

```
a='uudrrl'
r(a)

```

Test in browser console.

```
var x = "luluurrrrurd"
r(x)
8.48528137423857

```

# Answer
> 2 votes
# C# - 90 characters

Fresh from LINQPad.

```
int x=0,y=0;input.Max(i=>i==85?y++:i==82?x++:i==68?y--:x--);(Math.Sqrt(x*x+y*y)*2).Dump();

```

Where input is a valid string.

```
>string input = "LULUURRRRURD";

>8.48528137423857

```

# Answer
> 2 votes
# Jelly, ~~10~~ 9 bytes

```
O:3 ı*SḤA

```

Try it online!

I fiddled around with other functions to see if I could get rid of the space by finding a different one-byte dyad that would take a two-digit number on the left rather than the right, but it turned out that `:` doesn't need two digits to produce the desired values.

```
O            Codepoints of the input
 :3          floor divided by 3.
    ı*       Raise sqrt(-1) to the power of each,
      S      sum,
       Ḥ     double,
        A    and take the absolute value.

```

# Answer
> 1 votes
## J, 29 characters

```
+:+&.*:/-/_2[\#/.~/:~'ruld'i.

```

Only works with lower case directions and any characters other than `r`, `u`, `l`, and `d` will cause it to give a wrong answer.

Usage:

```
   +:+&.*:/-/_2[\#/.~/:~'ruld'i.'uuuudrrrl'
7.2111

```

**Explanation:**

`'ruld'i.'uuuudrrrl'` The dyadic form of `i.` finds the index of items from the right argument in the left argument. In this case:

```
   'ruld'i.'uuuudrrrl'
1 1 1 1 3 0 0 0 2

```

`/:~` sorts this list into ascending order:

```
   /:~'ruld'i.'uuuudrrrl'
0 0 0 1 1 1 1 2 3

```

`#/.~` counts the number of occurrences of each number:

```
   #/.~/:~'ruld'i.'uuuudrrrl'
3 4 1 1

```

`_2[\` chops it into 2 rows:

```
   _2[\#/.~/:~'ruld'i.'uuuudrrrl'
3 4
1 1

```

`-/` subtracts the bottom from the top

```
   -/_2[\#/.~/:~'ruld'i.'uuuudrrrl'
2 3

```

`+&.*:` borrows a trick from another J answer I saw this morning, and squares the items, then sums them, then performs a square root. See under `&.` documentation:

```
   +&.*:/-/_2[\#/.~/:~'ruld'i.'uuuudrrrl'
3.60555

```

`+:` doubles the result:

```
   +:+&.*:/-/_2[\#/.~/:~'ruld'i.'uuuudrrrl'
7.2111

```

# Answer
> 1 votes
### Matlab, 51 characters

My Matlab submission, works only with captial letters. This was a fun one! The hardest part was converting the string into an array of complex numbers to be summed.

**Function:**

```
f=@(s)abs(sum(fix((s-76.5)/8.5)+((s-79)*i/3).^-99))

```

**Usage:**

```
>> f=@(s)abs(sum(fix((s-76.5)/8.5)+((s-79)*i/3).^-99))
>> f('UURDL')
ans =

     1
>>

```

# Answer
> 1 votes
# Javascript, 136

```
function z(a){var x=a.split('u').length-a.split('d').length;var y=a.split('r').length-a.split('l').length;return Math.sqrt(x*x+y*y)*2;};

```

Example:

```
document.write(z('uuuudrrrwl'));
7.211102550927978

```

# Answer
> 1 votes
## JavaScript, 89

```
function f(a){U=D=L=R=0;for(d in a)eval(a[d]+'++');return 2*Math.sqrt((U-=D)*U+(L-=R)*L)}

```

Example:

```
<script>
document.write(f(['U', 'U', 'U', 'U', 'D', 'R', 'R', 'R', 'L']));
</script>

>7.211102550927978

```

# Answer
> 1 votes
# C, 120

```
float d(char *p){int v=0,h=0;while(*p){v+=*p=='U'?1:*p=='D'?-1:0,h+=*p=='R'?1:*p=='L'?-1:0,++p;}return 2*sqrt(v*v+h*h);}

```

`d("LULUURRRRURD")` -\> `8.485281`

# Answer
> 1 votes
# JavaScript (no ES6, no eval) - 131

```
f=function(h){for(i=0,a=[0,,0,0,0];i<h.length;++i)++a[(h.charCodeAt(i)>>2)-25];x=a[0]-a[4];y=a[2]-a[3];return Math.sqrt(x*x+y*y)*2}

```

Test:

```
console.log(f('uuuudrrrl'));     // 7.211102550927978
console.log(f('luluurrrrurd'));  // 8.48528137423857

```

# Answer
> 1 votes
# Perl 5 `-p`, 44 bytes

```
$_=2*sqrt((y/R//-y/L//)**2+(y/U//-y/D//)**2)

```

Try it online!

# Answer
> 0 votes
# Befunge-93 (65)

It has 65 non-whitespace characters (217 with whitespace, though that can be reduced by a more compact layout (for 69/176 chars)). It takes some liberality with the output format, but is undeniably accurate. Doesn't seem worth the effort to implement/steal a square root implementation.

```
v                  >$:*\:*+88*4*5-2.,.@
               >3-:|
           >6-:|
       >8-:|
>~"D"-:|
       $   $   $   $
           \   \
       1   1   1   1
       -   -   +   +
           \   \
^      <   <   <   <

```

`echo 'UUDLLUU' | ./befungee.py ../man` outputs 2√13 (actually implementation seems to have issue with the extended ASCII though).

---
Tags: code-golf
---


title: 2D Dungeon Crawler

text:
# Question
Title: 2D Dungeon Crawler
Your program has to take a multi-lined string, like this:

```
#############
#           #
#     p     #
#           #
#############

```

`p` is the player and `#` is a block.

Now under that in the terminal should be an input line saying:

```
How do you want to move?

```

If the player types `l` he has to walk left when there isn't a block, else, when there is a block, he can't go through and doesn't move of course, now the output in the terminal has to be updated (and the previous output cleared/overwritten):

```
#############
#           #
#    p      #
#           #
#############

```

He can type `l` for left, `r` for right, `u` for up and `d` for down.

The input will always be multiline, but won't always be padded with spaces into a perfect rectangle. In addition, the hashes can be anywhere in the string, and won't always be connected to each other. For example:

```
##  ##
#  #
## p
     #

```

is a valid dungeon. (note the lack of trailing spaces on each line)

If the player goes outside of the string, he doesn't have to be displayed. But if he comes back later, he must be displayed again.

And the boundaries of "outside" the string are the `length(longest_line)` by `number_of_lines` rectangle, so even if one line isn't padded with spaces on the right, that location isn't considered out of bounds. Example using the earlier dungeon:

```
##  ##
#  #p
##
     #

```

The second line didn't have a space where the p is now, but that doesn't matter.

Finally, your program must loop forever taking input.

## Test cases

Test case 1:

```
####
# p#
#
####

How do you want to move?
d

####
#  #
# p
####

```

Test case 2:

```
####
  p#
   #
####

How do you want to move?
l

####
 p #
   #
####

How do you want to move?
d

####
   #
 p #
####

How do you want to move?
l

####
   #
p  #
####

How do you want to move?
l

####
   #
   #
####

How do you want to move?
r

####
   #
p  #
####

```

Of course, these aren't complete. Your code should loop forever and **clear the screen between each output**.

Your output is allowed to prompt for input as `How do you want to move?\n<input>` or `How do you want to move?<input>` (i.e. you don't need the input on a blank line), and you don't need a empty line between the final line of the dungeon and the prompt. (they can't be on the same line however)

Standard loopholes are disallowed ! This is code-golf, so the shortest code in bytes wins!

# Answer
> 4 votes
# Haskell :: 799 703 bytes

Hi

This is my first code-golf submission.

It reads the initial grid from a text file.

Golfed:

```
    import Data.List
    x=maximum
    n=minimum
    r=filter
    s=length
    pad i r=r++(' '<$[1..(i-s r)])
    f l=let{w=x.map s$l;h=s l}in r((/=' ').snd).zip(flip(,)<$>[h,h-1..]<*>[1..w]).(pad w=<<)$l
    sh b=let{t=x.map(snd.fst)$b;d=n.map(snd.fst)$b;l=n.map(fst.fst)$b;sr _ []=[];sr i xb@((x,c):b)|x==i=c:sr(i+1)b|1>0=' ':sr(i+1)xb}in putStr.unlines.map(sr l.sort).map(\r->[(x,c)|((x,y),c)<-b,y==r])$[t,t-1..d]
    x!b|x`elem`map fst b=b|1>0=(x,'p'):r((/='p').snd)b
    b?i=let((x,y):_)=[x|(x,'p')<-b]in(case i of{'r'->(x+1,y);'l'->(x-1,y);'u'->(x,y+1);'d'->(x,y-1);_->(x,y)})!b
    m b=do{putStrLn"How do you want to move?";i<-getChar;putStr"\ESC[2J";let{d=b?i};sh d;m d}
    main = do{l<-readFile"s.txt";let{s=f.lines$l};sh s;m s}

```

An arguably more readable version:

```
import Data.List (sort)

data Board = Board [((Int,Int),Char)]

fromList l =
    let width = maximum . map length $ l
        height = length l
        coords = zip
            [(x,y) | y <- [height,height-1..1], x <- [1..width]]
            (concat (map (pad width ' ') l))
        clean = filter (\((_,_),c) -> c /= ' ') coords
    in Board clean

instance Show Board where
    show (Board xs) =
        let top = maximum . map (\((_,y),_) -> y) $ xs
            bottom = minimum . map (\((_,y),_) -> y) $ xs
            left = minimum . map (\((x,_),_) -> x) $ xs
            rows = map (\r -> [(x,c) | ((x,y),c) <- xs, y == r]) [top,top-1..bottom]
            showrow _ [] = []
            showrow i xxs@((x,c):xs)
                | x == i = c : showrow (i+1) xs
                | otherwise = ' ' : showrow (i+1) xxs
        in unlines . map ((showrow left) . sort) $ rows

insert z (Board zs) = Board (z:zs)

remove y (Board xs) = Board [(x,c) | (x,c) <- xs, x /= y]

at x (Board xs) =
    let match = [c | (x',c) <- xs, x' == x]
        ifempty [] = ' '
        ifempty (c:_) = c
    in ifempty match

move from@(x1,y1) to@(x2,y2) cur@(Board zs)
    | to `elem` [x | (x,c) <- zs] = cur
    | otherwise =
        let c = at from cur
        in insert (to,c) . remove from $ cur

find c (Board b) = [(x,y) | ((x,y),c') <- b, c' == c]

main = do
    startlist <- readFile "start.txt"
    let start = fromList . lines $ startlist
    print start
    maingameloop start

maingameloop board = do
    putStrLn "Where would you like to move?"
    inp <- getChar
    putStr "\ESC[2J"
    let newboard = movePlayer board inp
    print newboard
    maingameloop newboard

movePlayer board inp =
    let (cur@(x,y):[]) = find 'p' board
    in case inp of
        'r' -> move cur (x+1,y) board
        'l' -> move cur (x-1,y) board
        'u' -> move cur (x,y+1) board
        'd' -> move cur (x,y-1) board
        _ -> board

pad :: Int -> a -> [a] -> [a]
pad i c cs = cs ++ replicate (i - length cs) c

```

# Answer
> 1 votes
# **MATLAB, ~~268~~ ~~247~~ 246 bytes**

Probably not competitive, but it was fun. Golfed version:

```
function f(s);d=char(split(s,'\n'));[y,x]=ind2sub(size(d),find(d=='p'));while 1;d
c=uint8(input('How do you want to move?','s'))-100;v=y+~c-(c==17);w=x+(c==14)-(c==8);try;d(y,x)=' ';end;try;if'#'==d(v,w);v=y;w=x;end;d(v,w)='p';end;y=v;x=w;clc;end

```

Readable version:

```
function f(s)
% Split the string on newlines and convert to a padded char array
d = char(split(s,'\n'));

% Get the initial indices of p
[y,x] = ind2sub(size(d),find(d=='p'));

% Loop forever
while 1
    % Implicitly display the dungeon
    d

    % Get the ASCII of the user input, minus 100 (saves a few bytes in
    % the comparisons)
    c=uint8(input('How do you want to move?','s'))-100;

    % Get the new y from the ASCII
    v = y+~c-(c==17);

    % Get the new x from the ASCII
    w = x+(c==14)-(c==8);

    % Clear the player from the dungeon if they are in it
    try
        d(y,x)=' ';
    end

    % Check if new position is a #, and revert to old position if so
    try
        if '#'==d(v,w)
            v=y;w=x;
        end
        d(v,w)='p';
    end
    % Update x and y
    y=v;
    x=w;

    % Clear the screen
    clc;
end

```

The `try` blocks are to prevent the function from crashing on out of bounds errors. I'm sure that two of them is overkill, but I can't golf it down any better than that.

It's worth noting that MATLAB will expand the array downwards and to the right, but the player will disappear when moving to an 'unexplored' area for the first time. For example, if you move outside the dungeon's current boundaries to the right by one space, you will disappear, but next turn MATLAB will expand the array to include the new column (or row, if you are moving downwards). `'#'==d(y,x)` saves a byte compared to `d(y,x)=='#'`, since you don't need a space between `if` and `'#'`

# Answer
> 1 votes
# Coffee-script: 580 Bytes

I've squeezed everything I could out of this particular algorithm and my tired brain. I need a holiday.

```
C=console
e='length'
N=null
f=(S)->
    x=y=X=Y=N
    q=(c,v)->
        X=[x+c,N][+(-1<x+c<w)]
        Y=[y+v,N][+(-1<y+v<h)]
        try L[y+v][x+c]!='#'catch
            1
    r=(s)->
        if (X||Y)
            return
        L[y]=((t=L[y].split '')[x]=s)
        L[y]=t.join ''
    while 1
        L=S.split '\n'
        [h,w]=[L[e],L[0][e]]
        x=[X,x][+(x?)]
        y=[Y,y][+(y?)]
        for k in[0..h*w-1]
            if L[k//h][k%w]=='p'
                x=k%w
                y=k//h
        C.clear()
        C.log S
        r(' ')
        switch prompt("How do you want to move?")
            when'l'
                q(-1,0)&&x--
            when'r'
                q(1,0)&&x++
            when'u'
                q(0,-1)&&y--
            when'd'
                q(0,1)&&y++
        r('p')
        S=L.join '\n'

```

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


title: NATO phonetic spelling can take long

text:
# Question
Title: NATO phonetic spelling can take long
NATO phonetic alphabet is a spelling alphabet that associate to each of the 26 letters of the English alphabet one word (table below) that is easy to understand over the radio or telephone. For example, if you want to communicate the word `CAT` over the telephone, you do the following spelling:

`CHARLIE ALFA TANGO`

But what if you are unsure if the spelling was understood correctly? Well, you do the spelling of the spelling:

`CHARLIE HOTEL ALFA ROMEO LIMA INDIA ECHO ALFA LIMA FOXTROT ALFA TANGO ALFA NOVEMBER GOLF OSCAR`

But now you are worry that the spelling of the spelling was not understood correctly, so you cannot help yourself but doing the spelling of the spelling of the spelling:

`CHARLIE HOTEL ALFA ROMEO LIMA INDIA ECHO HOTEL OSCAR TANGO ECHO LIMA ALFA LIMA FOXTROT ALFA ROMEO OSCAR MIKE ECHO OSCAR LIMA INDIA MIKE ALFA INDIA NOVEMBER DELTA INDIA ALFA ECHO CHARLIE HOTEL OSCAR ALFA LIMA FOXTROT ALFA LIMA INDIA MIKE ALFA FOXTROT OSCAR XRAY TANGO ROMEO OSCAR TANGO ALFA LIMA FOXTROT ALFA TANGO ALFA NOVEMBER GOLF OSCAR ALFA LIMA FOXTROT ALFA NOVEMBER OSCAR VICTOR ECHO MIKE BRAVO ECHO ROMEO GOLF OSCAR LIMA FOXTROT OSCAR SIERRA CHARLIE ALFA ROMEO`

**Challenge:** Write a function that takes as input a word and returns as output the number of letters of the 100th iteration of NATO spelling. Examples:

```
MOUSE -> 11668858751132191916987463577721689732389027026909488644164954259977441
CAT -> 6687458044694950536360209564249657173012108297161498990598780221215929
DOG -> 5743990806374053537155626521337271734138853592111922508028602345135998

```

**Notes:**

* Whitespaces do not count. Only letters do.
* Both uppercase and lowercase letters are fine (including combinations of uppercase and lowercase).
* If you want to use a programming language without support for large integers, returning the result modulo `2^32` is fine too.
* The result must be an exact integer, not an approximation (like floating point).
* The first iteration of `CAT` is `CHARLIE ALFA TANGO` (`CAT` is the 0th iteration).

# Big Note:

If your program stores the spelling string, there's no way it is not going to run out of memory: the 100th iteration of `MOUSE` requires more than `10^70` bytes; the whole data on the Internet is estimated to be below `10^30` bytes.

**NATO spelling Table:**

```
A -> ALFA
B -> BRAVO
C -> CHARLIE
D -> DELTA
E -> ECHO
F -> FOXTROT
G -> GOLF
H -> HOTEL
I -> INDIA
J -> JULIETT
K -> KILO
L -> LIMA
M -> MIKE
N -> NOVEMBER
O -> OSCAR
P -> PAPA
Q -> QUEBEC
R -> ROMEO
S -> SIERRA
T -> TANGO
U -> UNIFORM
V -> VICTOR
W -> WHISKEY
X -> XRAY
Y -> YANKEE
Z -> ZULU

```

# Answer
> 31 votes
## SageMath, ~~260~~ ~~255~~ ~~253~~ ~~247~~ ~~246~~ ~~241~~ ~~236~~ ~~234~~ ~~233~~ 231 bytes

```
m=map
f=lambda w:sum(vector(m(w.count,m(chr,(65..90))))*(matrix(26,m([sum(ZZ([*m(ord,'v8^x$ 2??&:#Jd;2Nv&=4-wB/yY$4I"o^_bufTTZ fn"U(J1W:ZRYG=/p,ZTRn[RHJA$jbGn-ul2zeVJ')],92).digits(27)[:i])for i in(0..111)].count,(0..675)))+1)^100)

```

This constructs the transition matrix

```
[2 1 1 1 0 0 0 0 1 0 0 1 0 0 1 2 0 0 1 1 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0]
[0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 1 1 0 0 1 0 1 0 0 1 2 0 0 2 1 1 0 0 0 1 0 2 0]
[1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0]
[0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 0 0 2 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0]
[1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0]
[0 1 0 0 1 2 1 1 0 0 1 0 0 1 1 0 0 2 0 1 1 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 2 0 1 1 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0]
[0 0 0 1 0 2 0 1 0 2 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2]
[0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]

```

and raises it to the 100th power, then multiplies the matrix by the column vector representing the letter-frequencies of the input word, and finally computes the 1-norm.

It’s not the shortest entry, but it is fairly efficient: it takes about 4 ms to compute `f("MOUSE")` on my computer:

```
sage: %time f("MOUSE")
CPU times: user 4.11 ms, sys: 25 µs, total: 4.13 ms
Wall time: 4.14 ms
11668858751132191916987463577721689732389027026909488644164954259977441

```

This can almost certainly be shortened further. I bet there’s a more concise way to represent the matrix. (*See the third and fifth edits below…*)

---

**edit** (255): It’s shorter to use `sum(v)` than `v.norm(1)` to compute the 1-norm of a vector.

**edit** (253): We can pass a generator object to the `vector()` constructor, rather than a list, saving a `[]` pair.

**edit** (247): Use a more efficient string representation of the data, grouping the codewords into threes and representing each of the three with a different section of the ascii range: so the three words in a group are represented by characters from the ranges 33–58, 59–84, and 85–110 respectively.

**edit** (246): Changing the start of the ascii range we’re using from 33 to 39 means that none of the characters in the string need to be escaped, which saves one character since previously there was an escaped backslash `\\`. This has the pleasing side-effect that one codeword in three is now in plain text.

**edit** (241): Represent the matrix with a string in a completely different way: using a base-95 encoding of the lengths of the gaps between consecutive 1's, when the matrix is read by columns. In order to make the column-first order work without extra code, I’ve transposed everything, so now it’s multiplying a *row* vector by the 100th power of the *transposed* transition matrix.

The encoded list of numbers is:

```
[5, 6, 15, 14, 3, 4, 5, 4, 3, 1, 3, 6, 9, 4, 7, 8, 9, 5, 7, 26, 0, 3, 2, 0, 4, 8, 6, 3, 16, 7, 3, 5, 7, 3, 5, 5, 17, 4, 3, 8, 0, 1, 14, 3, 3, 12, 8, 4, 18, 4, 2, 17, 3, 0, 8, 2, 3, 4, 5, 2, 15, 1, 8, 0, 15, 12, 1, 2, 0, 16, 10, 8, 2, 0, 12, 4, 4, 9, 0, 9, 6, 7, 1, 17, 3, 4, 1, 1, 3, 11, 6, 6, 3, 2, 11, 3, 1, 2, 8, 6, 2, 17, 7, 2, 4, 0, 6, 3, 24, 9, 0]

```

This list is treated as a sequence of digits in base 27, for encoding purposes.

Where there is a `2` in the (transition matrix minus the identity), we represent that by a `0` in this list. After all, what is a two but a pair of ones at zero distance from each other?

Sadly this version is a few milliseconds slower – but we are playing golf, after all, not racing.

**edit** (236): Use a slightly different base-95 encoding that allows for a terser decoder, taking advantage of the fact that the integer constructor `ZZ(digits, base)` doesn’t mind if some of the digits are ≥ base. So we use digits in the printable range (32–126), even though the base is 95. The final (most significant) digit is 5, which therefore cannot be subject to this treatment, so we add it separately.

One could save an additional character by inserting a literal `^E` character at the end of the string and removing the `,5` following it, but surely one must maintain *some* decorum.

**edit** (234): It turns out that using base 92, rather than 95, means the encoded string consists entirely of printable ascii characters that do not need to be escaped.

**edit** (233): `map(w.count,map(chr,(65..90)))` is one character shorter than `w.count(chr(c))for c in(65..90)`.

**edit** (231): Now we’re using the `map` function four times, it’s worth abbreviating.

# Answer
> 11 votes
# Julia 1.0, ~~223~~ ~~218~~ 214 bytes

actually finishes by storing already computed values in a dictionnary

function name is `>`, for example `>("MOUSE")`

```
t=Dict()
>(s,n=99)=sum(x->big(get!(()->n<0||split("LFA RAVO HARLIE ELTA CHO OXTROT OLF OTEL NDIA ULIETT ILO IMA IKE OVEMBER SCAR APA UEBEC OMEO IERRA ANGO NIFORM ICTOR HISKEY RAY ANKEE ULU")[x-'@']x>n-1,t,x=>n)),s)

```

Try it online!

Ungolfed version:

```

dict = Dict()

function f(str, n=100)
    c = big(0)
    for x in str

        # if (x,n) is not in dict, execute the function below (in do...end) and store the result in dict
        c += get!(dict, (x,n)) do
            if n < 1
                true
            else
                words = split("LFA RAVO HARLIE ELTA CHO OXTROT OLF OTEL
NDIA ULIETT ILO IMA IKE OVEMBER SCAR APA UEBEC OMEO IERRA ANGO NIFORM
ICTOR HISKEY RAY ANKEE ULU")
                word = x * words[x - ('A'-1)]
                f(word, n-1)
            end
        end
    end
    return c
end

```

Try it online!

## Shorter but non-finishing version:

# Julia 1.0, 188 bytes

same approach but no storing of already computed results

```
>(s,n=99)=sum(x->big(n<0||split("LFA RAVO HARLIE ELTA CHO OXTROT OLF OTEL NDIA ULIETT ILO IMA IKE OVEMBER SCAR APA UEBEC OMEO IERRA ANGO NIFORM ICTOR HISKEY RAY ANKEE ULU")[x-'@']x>n-1),s)

```

Try it online! (depth 8 so that it can finish)

# Answer
> 9 votes
# , ~~260~~ ~~259~~ ~~236~~ ~~235~~ 232 bytes

*Edit: -3 bytes thanks to Robin Ryder, and -23 bytes using a version of Arnauld's trick of dropping the first letter of each word*

```
a=scan(,'')
lfa ravo harlie elta cho oxtrot olf otel ndia uliett ilo ima ike ovember scar apa uebec omeo ierra ango niform ictor hiskey ray ankee ulu

v=!!1:26
f=function(w)sum(v[utf8ToInt(w)-96])%%2^32
for(i in 0:99)v=v+sapply(a,f)

```

Try it online!

Function `f` that returns output modulo `2^32` (as allowed by rules) to stay within range of integer accuracy in .

```
a=scan(,'')                 # fill vector a with
alfa bravo charlie...       # NATO phonetic alphabet
                            # (need a newline to stop filling vector)
v=rep(1,26)                 # initialize vector v of values with 1s
f=function(w)               # f = function to calculate value of a word
  sum(v[                    # sum of elements of v at indices given by
    utf8ToInt(w)-96])       # utf8 values of letters, minus 96,
    %%2^32                  # modulo 2^32
for(i in 1:100)             # now perform 100 iterations of
  v=                        # updating v with
    sapply(a,f)             # the value of each word in a,
                            # calculated with the current v

```

# Answer
> 7 votes
# Charcoal, ~~133~~ 130 bytes

```
Ｆ¹⁰⁰≔Ｅ⪪”$±ＤuaＢ``ＩＹ″²÷⸿↓⪪∧⮌9Ｐπx¦⸿Ｓ1lＪ｜#←¹Ｆι´³Ａs¦L₂≕⬤m⍘Ｍ▶⭆dω{ⅈ⊟Ｃ0cO\⟦；⊟⁼`→<¬ＵＰνρＬ⊖¦N↷jOh⧴0r↨J9α➙n\²`⟧ＪξＵL≕φ5u”¶ΣＥκ∨¬ι§θ⌕αμθＩΣＥＳ§θ⌕αι

```

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

```
Ｆ¹⁰⁰

```

Loop 100 times.

```
≔Ｅ⪪”...”¶ΣＥκ∨¬ι§θ⌕αμθ

```

Calculate the cost of each letter in each word of the NATO phonetic alphabet using `1` on the first pass and the previous cost for that letter on subsequent passes.

```
ＩΣＥＳ§θ⌕αι

```

Print the total cost of all the letters in the input word.

# Answer
> 6 votes
# JavaScript (Node.js),  ~~257 248~~  244 bytes

The case of the input string doesn't matter. Returns a BigInt.

```
f=(s,C=(n=100,A="XLfaRavoHarlieEltaChoOxtrotOlfOtelNdiaUliettIloImaIkeOvemberScarApaUebecOmeoIerraAngoNiformIctorHiskeyRayAnkeeUlu".match(/.[a-z]*/g)).map(_=>1n),g=s=>Buffer(s).reduce((t,c)=>t+C[c&31],0n))=>n--?f(s,A.map((w,i)=>C[i]+g(w))):g(s)

```

Try it online!

### Commented

The array `A[]` consists of all NATO words without the leading letter and with an extra dummy entry at index 0:

```
A = "XLfaRavoHarlieEltaCho...AnkeeUlu".match(/.[a-z]*/g)
// -> [ "X", "Lfa", "Ravo", "Harlie", "Elta", "Cho", ..., "Ankee", "Ulu" ]

```

Main function:

```
f = (                 // f is a recursive function taking:
  s,                  //   s = input string
  C = (               //   C[] = array of letter costs, initially
                      //         filled with 1n (BigInt literal)
    n = 100,          //   n = number of iterations
    A = ...           //   A[] = NATO dictionary (as defined above)
  ).map(_ => 1n),     //
  g = s =>            //   g = helper function taking a string s
    Buffer(s)         //
    .reduce((t, c) => //     for each character c in s:
      t + C[c & 31],  //       add the cost of this character to t
      0n              //       starting with t = 0
    )                 //     end of reduce()
) =>                  //
  n-- ?               // decrement n; if it was not equal to 0:
    f(                //   do a recursive call:
      s,              //     pass s unchanged
      A.map((w, i) => //     for each entry w at position i in A[]:
        C[i] +        //       get the cost of the leading letter
        g(w)          //       add the cost of the other letters
      )               //     end of map()
    )                 //   end of recursive call
  :                   // else:
    g(s)              //   stop the recursion and return g(s)

```

# Answer
> 6 votes
# 05AB1E, ~~93~~ 86 bytes

Takes input in lowercase.

-7 bytes thanks to Kevin Cruijssen!!

```
тFA.•_7R₆"9~úCĆ~'ÍΩ₃M¿jŽ×Øûå…{×}ζ¥ny†–År{è˜dÉ4sK%<0•“ÿ¼¯¤œ®ÈŠˆƒ‹Š™—……ÍÐ—¼°µ†¸šÉµ“#{‡]g

```

Try it online! with 7 iterations.

**Commented:**

```
                    # implicit input: the starting word
т                   # push 100
 F         ]        # loop that many times:
  A                 #   push the alphabet "abc ... xyz"
   .•8Á ... Ôò•     #   push compressed alphabet string "alfa bravo foxtrot juliett kilo lima papa romeo tango whiskey xray yankee zulu"
      “ ¼¯ .. Éµ“   #   push compressed dictionary string "charlie delta echo golf hotel india mike november oscar quebec sierra uniform victor"
       ÿ            #   with the other string concatenated to the front
        #           #   split on spaces
         {          #   sort the words
          ‡         #   transliterate: replace each character of the alphabet with the word at same index in the current string
                    #     a->alfa, b->bravo, ..., z->zulu
            g       # after the loop: take the length

```

# Answer
> 6 votes
# Perl 5, ~~279~~ 222 bytes

```
sub f{my($c,$_,$n)=(0,@_,100);$c+=$d{$_,$n}//=$n<1||f($_.(LFA,RAVO,HARLIE,ELTA,CHO,OXTROT,OLF,OTEL,NDIA,ULIETT,ILO,IMA,IKE,OVEMBER,SCAR,APA,UEBEC,OMEO,IERRA,ANGO,NIFORM,ICTOR,HISKEY,RAY,ANKEE,ULU)[-65+ord],$n-1)for/./g;$c}

```

Try it online!

...which is a translation of the Julia answer from @MarcMush

My own approach was 279 bytes: Try it online!

# Answer
> 5 votes
# Jelly, ~~79~~ 77 bytes

```
“¡þƓẠı$1ƇẆÇ£ėƬỵ⁸ŀƘṣHỌŻ×²ıÞṆ]q1@ƒḳ0JñỴngṙƑ§ƥỵ⁼@¬TQñɱ⁼=Œ¬⁴RȦȧ¡⁸ƒƈẈ»ŒlḲị@OFµȷ2¡L

```

Try it online!

This times out on TIO, but Try it online! with only 9 iterations

Takes input in lowercase

-2 bytes thanks to Unrelated String

## How it works

```
“¡þƓ...ƒƈẈ»ŒlḲị@OFµȷ2¡L - Main link. Takes a string S on the left
                  µȷ2¡  - Do 100 times, updating the left argument each time, starting with S:
“¡þƓ...ƒƈẈ»             -   The compressed string "India Juliett kilo mail Mike November Oscar papa Quebec Romeo sierra tango uniform Victor whiskey rayx Yankee Zulu alfa bravo Charlie delta echo foxtrot golf hotel"
           Œl           -   Lowercase
             Ḳ          -   Split on spaces
                O       -   Get the char code of each character in the left argument
              ị@        -   1-based, modular index into the list of phonetic spellings
                 F      -   Flatten
                      L - Length

```

# Answer
> 5 votes
# Python 2, ~~292~~ 276 bytes

This is a little longer than the other Python answer, but finishes instantly.

```
w=[input()]+'LFA RAVO HARLIE ELTA CHO OXTROT OLF OTEL NDIA ULIETT ILO IMA IKE OVEMBER SCAR APA UEBEC OMEO IERRA ANGO NIFORM ICTOR HISKEY RAY ANKEE ULU'.split()
s=[1]+[0]*26
exec"s=[i and v+sum(j*c.count(chr(i+64))for j,c in zip(s,w))for i,v in enumerate(s)];"*101
print sum(s)

```

Try it online!

# Answer
> 4 votes
# Husk, ~~98~~ ~~95~~ 94 bytes

*Edit: -3 bytes thanks to caird coinheringaahing*

```
L!100¡ṁS:o!₁c
w¨nḋ?ẏ_₇↑₇Ø¹Ṁ≥ÏΣ⁶Ḃ€żẎ,Ä₄ βże⁶ŻθŻ₂»Żβ∞Ξ⌈¬¹¢»ÿ¿k»aΨ₈2≡≥⁷_⁷‡@ƒΨ▼«± ¦τaċ‼₀xt►Φ₀lf₀£t

```

Try it online! (but with only 9 iterations)

Unfortunately TIO errors with a 'stack overflow' at the 10th iteration, but the program/algorithm should run if provided with a (substantially) larger stack. Remove the initial `L` to check the actual string at each iteration like this.

```
L                   # get the length of
 !100               # the 100th element of
     ¡              # repeatedly applying this function:
      ṁȯ            # map & concatenate
        !₁          # each element of ₁ (see below) at index of
          c         # codepoint of each character of input

                    # function ₁:
w                   # split on whitespace
 ¨ḋα⌋...«ḣĖ         # compressed string:
                    # "india juliett kilo ... foxtrot golf hotel"

```

# Answer
> 4 votes
# Python 3, ~~286~~ \\$\cdots\\$ ~~238~~ 214 bytes

Saved a whopping ~~44~~ ~~48~~ 72! bytes thanks to Jitse!!!

```
f=lambda s,n=100:n and sum(f(c+"LFA RAVO HARLIE ELTA CHO OXTROT OLF OTEL NDIA ULIETT ILO IMA IKE OVEMBER SCAR APA UEBEC OMEO IERRA ANGO NIFORM ICTOR HISKEY RAY ANKEE ULU".split()[ord(c)-65],n-1)for c in s)or len(s)

```

Try it online!

Times out on TIO and is still running on my laptop. ~~Will post my running time when it finishes.~~ As Arnauld correctly predicted, it tried to melt my computer into a wormhole but it valiantly defended itself with a `MemoryError`! :))) Have added smaller (\\$1\\$ iteration and \\$10\\$ iterations) testcases to check that it does indeed work in theory.

# Answer
> 3 votes
# Icon, ~~379~~ ~~354~~ 351 bytes

```
procedure f(s)
v:=list(26,0)
b:=[]
"ALFA BRAVO CHARLIE DELTA ECHO FOXTROT GOLF HOTEL INDIA JULIETT KILO LIMA MIKE NOVEMBER OSCAR PAPA QUEBEC ROMEO SIERRA TANGO UNIFORM VICTOR WHISKEY XRAY YANKEE ZULU "?while put(b,tab(upto(" ")))&move(1)
v[ord(!s)-64]+:=1&\z;|1\100&{t:=list(26,0)
t[ord(!b[i:=1to*v])-64]+:=v[i]&\z
v:=t}&\z;(s:=0)+:=!v&\z
return s
end

```

Try it online!

# Answer
> 3 votes
# Jelly, 85 bytes

```
ċⱮØA
Çæ×“¢ị⁼Ɱ4ɦȷ3æ⁷ŀṣ⁶LṬⱮGṾxƬḟṬƊÆUFṡẉ⁴lṂṃȷỵḥṘ¤ʠḟẠṅṫSæßṠdċṣçẓẊẆPḲDṂƑĠṆṾ⁼Ɓ»ŒuḲÇ€æ*ȷ2¤FS

```

Try it online!

I couldn't figure out how to compress the matrix itself better than the dictionary could, so this probably can't get shorter than caird's solution, but I figured it's worth posting anyways since it's considerably faster. There might still be a bit of room to golf, though, since I was already able to knock a byte off by manually fiddling with the uncompressed string.

```
ċⱮØA    Monadic helper link, convert string to letter frequencies:
 Ɱ      for each element of
  ØA    "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
ċ       count how many times it occurs in the argument.

Çæ×“...»ŒuḲÇ€æ*ȷ2¤FS    Main link:
 æ×                     matrix multiply
Ç                       the input's letter frequencies
                 ¤      by:
   “...»                "alfa bravo Charlie delta echo foxtrot golf hotel India Juliett kilo mail Mike November Oscar papa Quebec Romeo sierra tango uniform Victor whiskey rayx Yankee Zulu"
        Œu              uppercased
          Ḳ             and split on spaces,
           Ç€           with each word converted to letter frequencies
             æ*ȷ2       and the resulting matrix multiplied by itself 100 times.
                  F     Flatten the resulting vector
                   S    and return its sum.

```

# Answer
> 2 votes
# C (gcc) (`-lgmp`), ~~464~~ ~~456~~ 452 bytes

* -8 by using `mpz_array_init()`
* -4 by @ceilingcat

As C doesn't have a native bignum library, I'm using GMP. To speed up the calculations, I memoize each stage of the computation.

```
#import<gmp.h>
*l[]={"ALFA","BRAVO","CHARLIE","DELTA","ECHO","FOXTROT","GOLF","HOTEL","INDIA","JULIETT","KILO","LIMA","MIKE","NOVEMBER","OSCAR","PAPA","QUEBEC","ROMEO","SIERRA","TANGO","UNIFORM","VICTOR","WHISKEY","XRAY","YANKEE","ZULU"};mpz_t t[2600];g(i,s,o,v,j)char*s;mpz_t*v,o;{for(;*s;mpz_add(o,o,*v))v=t+i*26+(j=*s++-65),mpz_sgn(*v)?:i?g(i-1,l[j],*v):mpz_set_ui(*v,strlen(l[j]));}f(s,o)mpz_t o;{mpz_init(o);mpz_array_init(*t,2600,512);g(99,s,o);}

```

Try it online!

# Answer
> 0 votes
# Java (OpenJDK 8), 397 392 bytes

```
String[]A=new String[26];char i=123,k;int S(String X){for(;--i>96;)A[i-97]=i+"lfa ravo harlie elta cho oxtrot olf otel ndia uliett ilo ima ike ovember scar apa uebec omeo ierra ango niform ictor hiskey ray ankee ulu".split(" ")[i-97];for(char d:X.toCharArray())i+=U(d<96?d+32:d,100);return i-96;}int U(int c,int i){if(i==-1)return 1;k=0;for(char d:A[c-97].toCharArray())k+=U(d,i-1);return k;}

```

Try it online!

Input is a String. **Outputs in 32 bit cap** (rules weren't entirely clear on if it's required, as BigInteger does exist in Java). It takes in unimaginable time to complete, but here's a faster solution that loads comparably instant:

# Java (OpenJDK 8), 511 506 bytes

```
String[]A=new String[26];Integer[][]B=new Integer[26][];int i=-1,j;int S(String X){for(;i++<25;)A[i]=(char)(i+97)+"lfa ravo harlie elta cho oxtrot olf otel ndia uliett ilo ima ike ovember scar apa uebec omeo ierra ango niform ictor hiskey ray ankee ulu".split(" ")[i];for(;i-->0;)B[i]=new Integer[101];for(char d:X.toCharArray())i+=U(d<96?d+32:d,100);return i;}int U(int c,int i){if(i==-1)return 1;j=97;if(B[c-j][i]==null){B[c-j][i]=0;for(char d:A[c-j].toCharArray())B[c-j][i]+=U(d,i-1);}return B[c-j][i];}

```

Try it online!

edit: Found a shortcut for .toLowerCase() for both

---
Tags: code-golf, alphabet
---


title: Calculate COVID spread

text:
# Question
Title: Calculate COVID spread
Because the coronavirus is still at large, I thought it would be fitting to have a epidemic-themed challenge.

## Challenge

You are given a 2D array of people, where `1` represents someone with the virus, and `0` represents someone without the virus. Every day, the people with the virus infect their neighbours. You must calculate, given such a grid, how many days it will take to infect the population (i.e., every item is `1`).

## Rules

* The input counts as Day 0, and every day after increases by 1 (you can count the first day as Day 1 if you want, but indicate that in your answer).
* The grid items don't have to be `1`s and `0`s, they can be any truthy/falsy values. Every item in the grid is randomized to one of those values. Please specify which truthy/falsy values your program will/will not accept.
* The input grid can be any size between 2x2 and 100x100. The grid does not have to be square. The grid size is randomized (i.e. you can't choose).
* Diagonal squares do not count as adjacent.
* This is , so the shortest answer wins!

## Examples

```
[[1, 0, 0, 0, 1],  # Input
 [0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 1, 0]]

[[1, 1, 0, 1, 1],  # Day 1
 [1, 1, 1, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 0, 1, 1, 1]]

[[1, 1, 1, 1, 1],  # Day 2
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 1, 1, 1, 1]]

[[1, 1, 1, 1, 1],  # Day 3
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1]]

output = 3

```

```
[[1, 0],  # Input
 [0, 0],
 [0, 0]]

[[1, 1],  # Day 1
 [1, 0],
 [0, 0]]

[[1, 1],  # Day 2
 [1, 1],
 [1, 0]]

[[1, 1],  # Day 3
 [1, 1],
 [1, 1]]

output = 3

```

---

# Answer
> 11 votes
# Stencil , 2 bytes

```
×v

```

Try it online!

tallies the number of necessary steps (including the initial state) until stability is reached. This command line argument isn't counted towards the byte count, as per Meta consensus.

Each cell's next state is determined by:

`×` the sign of
`v` the sum of all values in its **v**on Neumann neighbourhood (including itself)

# Answer
> 11 votes
# Jelly, 10 bytes

```
ŒJạ€ŒṪ§Ṃ€Ṁ

```

Try it online!

-2 bytes thanks to Sisyphus

Calculate the Manhattan differences from all 0s to all 1s, and the answer is the maximum of the minimums (each row's minimum is the number of stages until it gets infected, so the number of stages needed is the maximum of the stages needed for each person).

Conveniently, if all elements are 1, this returns 0 since that's the default value for minmax.

If no person is infected in the initial state, this also returns 0.

# Explanation

```
ŒJạ€ŒṪ§Ṃ€Ṁ  Main Link
ŒJ          Get all indices in the grid (2D indices in a matrix)
    ŒṪ      Get all truthy indices in the grid (finds all infected people)
  ạ€  §     Manhattan distance between each point to each truthy point
       Ṃ€   Minimum of each (minimum number of days for each person to get infected)
         Ṁ  Maximum (of each point's required days to get infected)

```

# Answer
> 11 votes
# Wolfram Language (Mathematica), ~~90~~ 78 bytes

```
f=Length@FixedPointList[ListConvolve[CrossMatrix@1,#,{2,2},0,Times,Max]&,#]-2&

```

Try it online!

-12 bytes, because of course there is a built-in `CrossMatrix` to construct the kernel \\$K\\$.

Defines a pure function `f` that takes a matrix as input. If no one is infected, return `0`. Uses list convolution to spread the disease day-by-day and a Mathematica built-in to loop until a fixed point is reached (i.e. everyone is infected). Explanation:

To spread the disease, use a kernel

$$K=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$

and list convolution. For example, if we start at

$$I\_0=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$$

then applying

```
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0] &

```

results in

$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 2 & 2 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$

We don't actually need to know whether a person is infected multiple times, so within the list convolution, instead of summing, we'll just take the maximum

```
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0, Times, Max] &

```

which gives

$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$

Then we just need to iterate it until a fixed point is reached, i.e. everyone is infected to no new infections can occur. There's (as usual) a handy built-in in Mathematica, `FixedPointList`, which gives a list of all the iterations until a fixed point is reached. Since this list contains the input and the fixed point twice, just subtract two from the list length to get the answer.

As a sidenote, the parameters in `ListConvolve` ensure that the convolution works well with the kernel. With the default parameters, convolving

$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$

with the kernel

$$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$

gives rather uselessly

$$\begin{pmatrix} 0 & 0 \\ b & c \end{pmatrix}.$$

To at least preserve the dimensions, we'll add the parameter `{1,1}`, which now gives

$$\begin{pmatrix} 0 & d & e & f \\ 0 & g & h & i \\ 0 & 0 & 0 & 0 \\ 0 & a & b & c \\ \end{pmatrix}.$$

This time, the problem is that the convolution starts at the top-left corner instead of at the center of the kernel, so let's change the `{1,1}` to `{2,2}`, which gives

$$\begin{pmatrix} g & h & i & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$

This is almost what we need, but the bottom of the kernel overflows to the top. To fix this, we'll just add a padding parameter `0`. Finally

$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$

# Answer
> 9 votes
# Octave, 26 bytes

```
@(x)max(bwdist(x,'ci')(:))

```

Try it online!

For each cell, compute the distance to the nearest nonzero cell under the \\$L\_1\\$ norm (taxicab metric). The solution is the maximum value.

# Answer
> 7 votes
# APL (Dyalog Extended), 20 bytes

```
{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}

```

Try it online!

Uses the Manhattan Distance method from HyperNeutrino's Jelly answer.

Input is a binary matrix.

## Explanation

```
{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}
     ⍵           ~⍵  input and input negated
               ⍥⍸    coordinates of truthy values
      ∘.             outer product using
        (1⊥∘|-)      Manhattan distance function (APLcart)
   ⌊⌿                Minimum of each column
 ⌈/                  Maximum of the minima

```

# Answer
> 4 votes
# C (gcc), ~~270~~ \\$\cdots\\$ ~~214~~ 213 bytes

Saved a whopping ~~31~~ ~~39~~ ~~40~~ ~~44~~ ~~56~~ 57 bytes thanks to ceilingcat!!!

```
z;C;i;j;n;d;*p;f(a,r,c)int*a;{p=calloc(C=c+2,4*r+8);for(n=d=0;d<r*c;++n){for(d=0,i=r;i--;)for(j=c;j--;)a[i*c+j]?p[i*C-~j]=p[(i+2)*C-~j]=p[z=j-~i*C]=p[z+2]=1:0;for(;++i<r*c;)d+=a[i/c*c+i%c]=p[1-~(i/c)*C+i%c];}d=n;}

```

Try it online!

Inputs the population grid as a pointer to an array of `int`s, that are either \\$1\\$ for infected or \\$0\\$ otherwise, along with the number of rows and columns. Returns the number of days it will take to infect the population.

### How?

Creates a shadow array `p` that has a one element boarder around it so we don't have to worry about the neighbours not being there when we're at the edges. Initialises all of its elements to \\$0\\$. For each day we then go though the input population grid row-by-row and column-by-column checking for infected elements. For everyone found we mark that position in the shadow array and its \\$4\\$ neighbours as infected. After that, on the same day, we then go through the input array again, copying over the corresponding shadow elements and counting the total number of infected for that day. Returns the number of days passed until all are infected.

# Answer
> 3 votes
# , 35 bytes

```
1-~&#<@_>./@:(|.!.0)~&(0,(,-)=i.2)]

```

Try it online!

* `(0,(,-)=i.2)`: `0 0,1 0,0 1,-1 0,0 -1`
* `<@_ f&dirs ]` repeat `input f dirs` until the result does not change, and return all intermediate steps.
* `>./@:(|.!.0)~` shift the board along the directions (with `0`s getting shifted in at the borders), and take the maximum of them all.
* `1-~&#` count the steps minus 1.

# Answer
> 2 votes
# JavaScript (ES6),  ~~97~~  95 bytes

```
f=m=>/0/.test(a=[1,...m,1])&&1+f(m.map((r,y)=>r.map((v,x)=>v|r[x-1]|r[x+1]|a[y][x]|a[y+2][x])))

```

Try it online!

### Commented

```
f = m =>              // m[] = matrix
  /0/.test(           // if there's still a zero in
    a = [1, ...m, 1]  //   a[] which is defined as m[] with two dummy border rows
  ) &&                // then:
  1 + f(              //   increment the final result and do a recursive call:
    m.map((r, y) =>   //     for each row r[] at position y in m[]:
      r.map((v, x) => //       for each value v at position x in r[]:
                      //         the cell is set if:
        v |           //           it's already set
        r[x - 1] |    //           or the cell on the left is set
        r[x + 1] |    //           or the cell on the right is set
        a[y][x] |     //           or the cell above is set
        a[y + 2][x]   //           or the cell below is set
                      //           NB: both a[0][x] and a[a.length - 1][x] are
                      //               undefined (falsy) for any x
      )               //       end of inner map()
    )                 //     end of outer map()
  )                   //   end of recursive call

```

# Answer
> 1 votes
# Python 3, 131 bytes

```
lambda a,e=enumerate:max([min([abs(x-X)+abs(y-Y)for X,I in e(a)for Y,J in e(I)if J]or[0])for x,i in e(a)for y,j in e(i)if j<1]+[0])

```

Try it online!

If nobody is infected in the original, this will return 0.

-11 bytes thanks to caird coinheringaahing

Try it online!

Older method using recursion:

# Python 3, 199 bytes

```
f=lambda a,c=0:all(sum(a,[]))and c or f([[g(a,x,y+1)+g(a,x,y-1)+g(a,x+1,y)+g(a,x-1,y)+g(a,x,y)for y in range(len(a[x]))]for x in range(len(a))],c+1)
g=lambda q,x,y:len(q)>x>=0<=y<len(q[x])and q[x][y]

```

Try it online!

If there is nobody infected in the original, this will recursion overflow.

# Answer
> 1 votes
# Charcoal, 39 bytes

```
Ｉ⌈Ｅθ∨⌈Ｅ⌕Ａι⁰∨⌊ΦＥθ⌊Ｅ⌕Ａν¹⁺↔⁻ξκ↔⁻πλ¬⁼νＩν⁰¦⁰

```

Try it online! Link is to verbose version of code. Uses the Manhattan distance method again. Charcoal can't flatten lists, plus it returns `None` for the minimum or maximum of an empty list, which complicates the code somewhat. Explanation:

```
  Ｅθ                                    For each row
      Ｅ⌕Ａι⁰                             For each `0` value in that row
              Ｅθ                        For each row
                 Ｅ⌕Ａν¹                  For each `1` value in that row
                       ↔⁻ξκ↔⁻πλ         Calculate the Manhattan distance
                ⌊                       Take the minimum
             Φ                 ¬⁼νＩν    Filter out `None` values
            ⌊                           Take the minimum
           ∨                        ⁰   Or zero if the list was empty
     ⌈                                  Take the maximum
    ∨⌈                                ⁰ Or zero if the list was empty
 ⌈                                      Take the maximum
Ｉ                                       Cast to string
                                        Implicitly print

```

# Answer
> 1 votes
# K (oK), 41 bytes

```
{|/&/{+/x|-x}''u-\:/:(1=x.)#u:+!(#x),#*x}

```

Try it online!

Maximum of the minimums of the Manhattan distance of each point to each truthy point.

```
{                                        } \ a function with parameter x
                                      #*x  \ length of the first row
                                     ,     \ appended to
                                 (#x)      \ the number of rows
                                !          \ odometer (coordinates of the points)
                               +           \ transpose
                             u:            \ assign to u
                            #              \ filter
                      (1=x.)               \ the coordinates of the truthy points
                u-\:/:                     \ find the differences of the cooridinates
                                           \ of each point to each truthy point
      {+/x|-x}''                           \ find the absolute value and sum
    &/                                     \ minimum of the Manhattan distances
                                           \ to each truthy point
  |/                                       \ maximum

```

# Answer
> 1 votes
# Java 8, 204 bytes

```
m->{int r=0,f=1,l=m[0].length,i,t,I,J,n;for(;f>0;r++)for(n=f,f=0,i=m.length*l;i-->0;)for(t=4;m[I=i/l][J=i%l]==n&t-->0;)try{m[I-=t-t%3*t>>1][J-=t<2?1-2*t:0]+=m[I][J]<1?f=n+1:0;}finally{continue;}return r;}

```

Minor modification of my answer here.

Outputs the result including the first step.

Try it online.

**Explanation:**

```
m->{                          // Method with integer-matrix parameter and integer return-type
  int r=0,                    //  Result-integer, starting at 0
      f=1,                    //  Flag-integer, starting at 1
      l=m[0].length,          //  Amount of rows
      i,t,I,J,n;              //  Temp integers
  for(;f>0;                   //  Loop as long as the flag is NOT 0:
      r++)                    //    After every iteration: increase the result by 1
    for(n=f,                  //   Set `n` to the current flag-value
        f=0,                  //   And then reset the flag to 0
        i=m.length*l;i-->0;)  //   Loop over the cells of the matrix:
      for(t=4;                //    Set the temp integer `t` to 4
          m[I=i/l][J=i%l]==n  //    If the current cell contains value `n`
          &t-->0;)            //     Loop `t` in the range (4,0]:
        try{m                 //      Get the cell at a location relative to the current cell:
             [I-=t-t%3*t>>1]  //       If `t` is 3:
                              //        Take the cell above
                              //       Else-if `t` is 2:
                              //        Take the cell below
             [J-=t<2?1-2*t:0] //       Else-if `t` is 0:
                              //        Take the cell left
                              //       Else-if `t` is 1:
                              //        Take the cell right
              +=m[I][J]<1?    //      And if this cell contains a 0:
                  f=n+1       //       Fill it with `n+1`,
                              //       And set the flag to `n+1` as well
                 :            //      Else:
                  0;          //       Keep the value the same by increasing with 0
        }finally{continue;}   //      Catch and ignore ArrayIndexOutOfBoundsExceptions
                              //      (saves bytes in comparison to manual boundary checks)
  return r;}                  //  And after the loop: return the result

```

# Answer
> 1 votes
# 05AB1E, 18 bytes

```
ΔĀ2FøJTÂ‚12Â‚:€S]N

```

Outputs the result including the first step.

Try it online or verify all test cases.

**Explanation:**

```
Δ                # Loop until the result no longer changes,
                 # using the (implicit) input-matrix in the first iteration
 Ā               #  Python-style truthify each integer, changing all potential 2s to 1s
  2F             #  Loop 2 times:
    ø            #   Zip/transpose; swapping rows/columns
     J           #   Join each row of digits together to a string
      TÂ‚        #   Pair 10 with its reversed: ["10","01"]
         12Â‚    #   Do the same for 12: ["12","21"]
             :   #   Replace all "10" with "12" and all "01" with "21" in all rows
              €S #   And convert each row back to a list of digits
]                # Close the nested loops
 N               # And push the 0-based index of the outer loop
                 # (note that the loop until the result no longer changes will loop an
                 #  additional time, which is why this results in the correct result
                 #  despite having 0-based indexing instead of 1-based)
                 # (after which it is output implicitly as result)

```

# Answer
> 1 votes
# , ~~105~~ 101 bytes

*Edit: -4 bytes thanks to Giuseppe*

```
function(m)max(apply(as.matrix(dist(which(m<2,T)[order(-!m),],"man"))[f<-1:sum(!m),-f,drop=F],1,min))

```

Try it online!

```
covidsteps=
function(m,             # m is input matrix
e=m<1)                  # e is uninfected cells
max(                    # get the max of the distances from each uninfected cell
                        # to its closest infected cell, by
 apply(...,1,min)       # getting the minima of
  as.matrix(
  dist(...,"man")       # the pairwise manhattan distances between
  which(m<2,T)          # all coordinates
  [order(-e),])         # ordered with infected cells first
  [                     # and selecting only distances between
   f<-1:sum(e),         # uninfected cells (rows in the distance matrix)
   -f,                  # and infected cells (cols of the distance matrix)
  drop=F])

```

# Answer
> 0 votes
# Retina 0.8.2, 100 bytes

```
^
¶
{1s`¶(1.*0|0.*1)
_$&
}`(?<=(.)*)0(?=(.*¶(?<-1>.)*(?(1)$))?1|(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
1
_

```

Try it online! Takes input as a rectangular digit array. Explanation:

```
^
¶

```

Prepend a newline to provide a work area to build up the result. (While I can append the result instead, that complicates the regular expressions, so it's not any golfier.)

```
{`
}`

```

Repeat until a stable position is reached (either all `0`s or all `1`s).

```
1s`¶(1.*0|0.*1)
_$&

```

If the position contains a mixture of `0`s and `1`s then increment the number of days.

```
(?<=(.)*)0

```

If there is a `0` that ...

```
(?=(.*¶(?<-1>.)*(?(1)$))?1|

```

... is directly next to a `1` which either to the right or below, or ...

```
(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))

```

... is either directly to the right of a `1` or directly below a `1`...

```
1

```

... then replace it with a `1`.

```
_

```

Output the number of days in decimal.

The above/below checks are made using .NET balancing groups. The initial `(?<=(.)*)` grabs the column number into `$#1`, and then we have two cases:

* `.*¶(?<-1>.)*(?(1)$)1` advances to the next line, advances one character for every column, checks for the correct column (`$` can't possibly match before `1`, so `(?(1)$)` can only match if there are no columns left to advance), and then matches `1`.
* `(?<=¶(?(1)^)(?<-1>.)*1.*¶.*)` is a lookbehind, so is matched right-to-left: first it advances to the previous line, then finds a `1`, then advances and checks for the correct column (`^` can't match after  because we're not in multiline mode, but `$` would also work), then checks for the start of the line (it won't be the start of the buffer because of the  added at the beginning of the program).

# Answer
> 0 votes
# CJam, 68 bytes

```
{__{,,:)}:M~\zMm*\_{{_M.*}%\z}2*..{_{a+}{;;}?}:~f{\f{.-:z:+}$0=}$W=}

```

Try it online!

If only I knew how to properly manipulate 2D arrays in this language...

Calculates the maximum of each minimum Manhattan distance from each point to each infected point.

# Answer
> 0 votes
# Perl 5 `-00p`, ~~63~~, 60 bytes

Saved some bytes thanks to Dom Hastings.

```
/
/;$,='.'x"@-";$\++while s/(?<=1$,)0|1\K0|0(?=$,1|1)/1/gs}{

```

Try it online!

# Answer
> 0 votes
# Python 3, 115 bytes

```
f=lambda a,e=enumerate:all(map(all,a))or-~f([[1in[0,*r][j:j+3]+[0,*c][i:i+3]for j,c in e(zip(*a))]for i,r in e(a)])

```

Try it online!

1-indexed recursive solution. Replaces each item with `True` if itself or any of its orthogonal neighbours are `1` (==`True`). Recursion stops when all values in the array are `True`.

---
Tags: code-golf, binary-matrix
---


title: Gluttonous Colluding Numbers

text:
# Question
Title: Gluttonous Colluding Numbers
Here's an easy one, with just enough complexity to make golfing non-trivial.

## Input

1. A list of non-negative numbers representing people waiting in line for Thanksgiving dessert. The first (leftmost) number is first in line, and the list can contain repeats (think of each number as a person's first name):

```
Note: Pie not part of actual input.

        (
         )
    __..---..__
,-='  /  |  \  `=-.
:--..___________..--;   6 4 3 1 2 3 0
\.,_____________,./

```
2. A non-empty subset of that list, representing a group of colluding friends who will "chat and cut" to skip ahead in line. All colluders will move just behind the friend already closest to the front of the line, but otherwise retain their relative positions. Everyone they skip past will also retain their relative position.

## Output

The new list, after a successful (possibly multi-way) chat and cut. For example, in the list above, for a friend group of `0 2 4`, the output would be:

```
6 4 2 0 3 1 3

```

If the friend group was `4 3`, the output would be:

```
6 4 3 3 1 2 0

```

### Notes

This is code golf with standard site rules.

* A single colluder `x` in the colluder list makes everyone in line with that number a colluder.
* The list of people waiting may contain repeats.
* The colluder list will not contain repeats.
* The colluder list may not be sorted.
* The colluder list will have between 2 and U items, where U is the number of unique elements in the queuer list.

## Test Cases

The format is:

1. People in line.
2. List of colluders.
3. Output.

```
5 4 3 2 1 0
3 1
5 4 3 1 2 0

1 2 1 3 1 9
1 9
1 1 1 9 2 3

1 2 3 4 5
4 5
1 2 3 4 5

7 6 1 5 2 4 3
4 5 6
7 6 5 4 1 2 3

7 6 1 5 2 4 3
1 2 3
7 6 1 2 3 5 4

7 6 1 5 2 4 3
3 6
7 6 3 1 5 2 4

1 2 3 4
1 2 3 4
1 2 3 4

1 2 3 4 5 4
5 4
1 2 3 4 5 4

```

# Answer
# 05AB1E, ~~9~~ 8 bytes

```
ΣåDi©}®‹

```

-1 byte thanks to *@ovs*.

Try it online or verify all test cases.

**Explanation:**

```
Σ        # (Stable) sort the first (implicit) input-list by:
 å       #  Check that the current item is in the second (implicit) input-list
         #  (1 if truthy; 0 if falsey)
  Di }   #  Duplicate it, pop this copy, and if it's 1:
    ©    #   Store 1 in variable `®` (without popping) (variable `®` is -1 by default)
      ®‹ #  Check that the duplicated check is smaller than `®`
         #  (1 if truthy; 0 if falsey)

```

Here the same TIOs with map instead of sort-by, so you can see any leading non-friends become `0`, all friends become `0` as well, and any non-friends after the first friend become `1`:
Try it online or verify all test cases.
> 10 votes

# Answer
# , 12 bytes

*-1 thanks to FrownyFrog!*

```
[/:OR\@e.-e.

```

Try it online!

For `6 4 3 1 2 3 0` and `0 2 4`:

```
[/:OR\@e.-e.
   OR        OR …
     \       each prefix of …
      @e.    the bitmask of friends, or:
   OR\@e.    after the first friend? (0 1 1 1 1 1 1)
          e. the bitmask of friends  (0 1 0 0 1 0 1)
         -   minus                   (0 0 1 1 0 1 0)
[/:          (stable) sort the people based on the list
                                     (6 4 3 1 2 3 0)

```
> 12 votes

# Answer
# , ~~49~~ ~~47~~ ~~45~~ 42 bytes

*Edit: -2 bytes, and then -3 more bytes, thanks to Giuseppe*

```
function(l,f)l[order(cummax(p<-l%in%f)-p)]

```

Try it online!

**Commented:**

```
function(l,f`           # function with arguments:
                        # l = line
                        # f = friends
p=l%in%f)               # define p as TRUE at positions of friends in the line
l[order                 # now output l, in the order of (lowest>highest):
-(                      # minus (so now highest>lowest)
p                       # 1 for each friend
+2*!cumsum(p)           # +2 for anyone ahead of the first friend
))]                     # (so, in the end, anyone ahead of all friends gets -2,
                        # the friends get -1,
                        # and anyone else behind the first friend gets zero).

```

---

**Previous approach: , ~~67~~ ~~59~~ 54 bytes**

*Edit: -8 bytes thanks to Giuseppe, then -5 more bytes thanks to Robin Ryder*

```
function(l,f,p=which(l%in%f))c(l[z<-c(1:p-1,p)],l[-z])

```

Try it online!
> 9 votes

# Answer
# Python 2, ~~79~~ 72 bytes

```
def f(x,y):m=min(map(x.index,y));print x[:m]+sorted(x[m:],cmp,y.count,1)

```

*-7 bytes thanks to @ovs*

Try it online! All testcases.

I take a unique approach here using Python's `sorted` function, which performs a stable sort. Might not be the shortest Python approach, but it is interesting.

```
def f(x,y):  # x = input line, y = list of colluders
  m = min(map(x.index,y)) # index of the first colluder in line
  print
    x[:m] # The first m people do not change positions
    sorted(
      x[m:],   # we sort the people after the first m
      cmp,    # default comparison function
      y.count, # key function is y.count: returns 0 for numbers not in y
                 # and 1 for numbers in y
      1        # sort in descending order
    )

```
> 7 votes

# Answer
# Jelly, 9 bytes

```
e€»\_$Ụị⁸

```

Try it online!

More or less a translation of xash's J answer.

```
e€           For each person in line, are they a friend?
    _        Subtract that from
  »\ $       its cumulative maxima,
      Ụ      sort the indices,
       ị⁸    index back into the line.

```

`iⱮ»\_$Ụị` almost saves a byte by taking colluders on the left and the line on the right, but it doesn't succeed at preserving the order of duplicate colluders in cases such as `[1,2,3,4,5,4], [5,4]`.

# Jelly, 12 bytes

```
iⱮṂœṖ⁸e¬¥Þ€F

```

Try it online!
> 7 votes

# Answer
# Haskell, 59 bytes

```
(h:t)%c|all(/=h)c=h:t%c
l%c=[x|b<-[1<0..],x<-l,elem x c/=b]

```

Try it online!

Test cases and inspiration from ovs's solution.

We use `[1<0..]` to generate the list `[False,True]`. Having handled the prefix of non-colluding numbers, we then pass over the remainder twice, first to take colluding numbers, then to take non-colluding ones. A same-length alternative is:

**59 bytes**

```
(h:t)%c|all(/=h)c=h:t%c
l%c=[x|b<-[id,not],x<-l,b$elem x c]

```

Try it online!
> 7 votes

# Answer
# Haskell, 65 bytes

```
q!c|f<-(`elem`c),(h,t)<-span(not.f)q=h++((`filter`t)=<<[f,not.f])

```

Try it online!

**Commented**:

```
q!c|
    f<-(`elem`c),        -- f is a function to check whether a number is a colluder
    (h,t)<-span(not.f)q  -- h is the longest prefix of non-colluders, t the remaining list
   =
    h++                  -- the result is h and ...
    (  =<<               -- ... the concatenation of the results of ...
     (`filter`t)         -- ... filtering the remaining list by ...
         [f,not.f])      -- ... f and not f (colluders and not colluders in t)

```

---

# Haskell, 66 bytes

With some inspiration from xnor's and AZTECCO's answers I came up with a pointfree function that is just 1 byte longer.

```
(takeWhile<>g.(not.)<>((.).g<*>dropWhile)).flip(all.(/=))
g=filter

```

Try it online! In GHC version 8.4.1 and above `(<>)` is included in the Prelude, in the old version on TIO it has to be imported manually.
> 5 votes

# Answer
# Factor, 62 bytes

```
[ '[ _ member? ] 2dup find . swapd cut rot partition 3append ]

```

Try it online!

The extensive `sequences` library is quite helpful here. Takes `line cheaters` on the stack, and returns the modified line through the stack. Prints a garbage to stdout each time it is run.

### Ungolfed

```
[                  ! ( line cheaters ) start anonymous lambda definition
  '[ _ member? ]   ! ( line fun ) convert cheaters array to membership function
  2dup find .      ! ( line fun idx ) find index of first cheater
  swapd cut        ! ( fun left right ) cut line at that index
  rot partition    ! ( left cheaters rest ) partition the right into
                   !   cheaters and non-cheaters, using the membership function
  3append          ! ( ans ) concatenate the three arrays
]                  ! end anonymous lambda definition

```

---

# Factor, 74 bytes

```
[ dupd '[ _ member? 1 0 ? ] map dup cum-max swap v- zip sort-values keys ]

```

Try it online!

Factor's standard library is feature-rich enough that it can almost directly replicate xash's J solution. Except that it's 5~10 times bloated byte-count-wise.

### Ungolfed

```
: glutton ( line cheaters -- line' )  ! takes two arrays on the stack
                                      ! and returns the cheated line as an array
  dupd                       ! duplicate line under cheaters
  '[ _ member? 1 0 ? ] map   ! for each number in line, 1 if it is a cheater,
                             ! 0 otherwise
  dup cum-max swap v-        ! cumulative maximum minus self (of the above)
  zip sort-values keys       ! sort line by the above
;

```
> 5 votes

# Answer
# Racket, 145 bytes

```
(λ(a b)(let([m(apply min(map(λ(x)(index-of a x))b))])(append(take
a m)(call-with-values(λ()(partition(λ(x)(member x b))(drop a m)))append))))

```

Try it online!

That's even longer than my Red solution :)

It's insane that `partition` returns two separate values rather than a list with two sublists - that's why I need to use `call-with-values` and put `partition` within an additional lambda...
> 4 votes

# Answer
# Ruby 2.7, 39 bytes

```
->q,c{q.flat_map{c-[_1]!=c ?q-q-=c:_1}}

```

Try it online! (40 bytes because TIO's Ruby version doesn't support numbered block parameters)

Relies on the `Array::-` method, which returns all elements of the first array not present in the second. Given a queue `q` and colluders `c`, the ordered lists of non-colluders and colluders are `q-c` and `q-(q-c)`, respectively.

```
->q,c{
  q.flat_map{ # For each person in the queue
    c-[_1]!=c # Are they a colluder?
      ?q-q-=c # If they are the first colluder, replace them with all colluders (in same order as they appear in the queue) and remove remaining colluders from the queue in one fell swoop. Second and subsequent colluders will be replaced by an empty array.
      :_1     # If not a colluder, leave them alone
  }
}

```
> 3 votes

# Answer
# K (oK), 20 bytes

```
{x@<{(|\x)-x}x in y}

```

Try it online!

An experiment in making a K port of xash's J answer \- please upvote his/hers solution!
> 3 votes

# Answer
# Haskell, ~~83~~ 72 bytes

```
import Data.List.Split
q?c|h:t<-splitOneOf c q=id=<<h:filter(`elem`c)q:t

```

Try it online!

* Longer than @xnor and @ovs great answers but I think it's worth posting because it's quite short and it has a simple and interesting approach.
* Thanks to @ovs for the precious advices, saved a lot and looks more golfy now!

```
q?c ... =             - infix function taking q-ueue and c-olluders lists
|h:t<-splitOneOf c q  - split queue at colluders
id=<<                 - concat map :
h:filter(`elem`c)q:t    - first split, colluders and the remaining

```
> 3 votes

# Answer
# Perl 5, 75 bytes

```
sub{$f=1;map$_%1e5,sort map$_+1e5*++$r+1e9*($_~~@_&&($f=2)?1:$f),@{+shift}}

```

Try it online!

```
sub{
  $f=1;           #f = 1 if first colluder not found, = 2 after 1st colluder
  map$_%1e5,      #remove part used for sort, input elems remain in sorted order
  sort            #sorts numerically as all elems have same number of digits now
  map             #converts each elem in input queue to sum of:
    $_            #the elem itself
   +1e5 * ++$r    #plus 100000 times the input rank in the queue
   +1e9 * (       #plus 1 billion times the "rank overriding number" which is:
      $_~~@_&&($f=2) #true if current elem is colluder (if so, set $f=2)
      ? 1         #...1 if colluder
      : $f        #...or $f if not colluder (f is 1 before 1st colluder, 2 after)
    ),
    @{+shift}     #input queue
}

```

Works for input elems 0-99999 and for queues up to 10000 elems. Increase 1e5 and 1e9 to 1e8 and 1e16 accordingly (spending one more byte of code) to avoid this, after which computer memory size becomes a bottleneck for most setups I guess.
> 3 votes

# Answer
# JavaScript (ES10), 60 bytes

Expects `(people)(subset)`, where `people` is an array and `subset` is a Set.

```
a=>b=>a.flatMap(i=>b.has(i)?j=a.filter(x=>j&b.has(x)):i,j=1)

```

Try it online!

Or Try it with map() to get a better picture of the process.

### How?

The variable `j` is initially set to `1`.

We walk through the queue with `flatMap()`. Each identifier `i` that is not included in the group of friends is copied as-is:

```
b.has(i) ? … : i

```

As soon as a guy from the group of friends is reached, we append all friends at once in their order of appearance in the queue, and assign the result to `j`:

```
j = a.filter(x => j & b.has(x))

```

Arrays holding at least two elements are turned into `NaN` when coerced to a number. So the next time a friend is encountered, `j & b.has(x)` will be falsy(1) and `filter()` will return an empty array. As a result, all following friends are ignored as expected.

---

(1): It could actually be truthy if `j` is updated to a singleton array holding an odd identifier. But that would mean that there's only one friend in the queue, so the test `b.has(i)` would not be triggered another time in that case anyway.
> 2 votes

# Answer
# C (gcc), ~~201~~ \\$\cdots\\$ ~~172~~ 171 bytes

Saved ~~12~~ a whopping ~~29~~ 30 bytes thanks to ceilingcat!!!

```
#define z 0;for(i=-1;++i<n;
#define P&&printf("%d ",l[i]
q;p;i;j;f(l,n,c,m)int*l,*c;{q=p=z!p P))for(j=m;j--;)l[i]==c[j]?q=p?q:i,l[i]^=p=-1:z)0>l[i]P^-1);z)i>=q&0<=l[i]P);}

```

Try it online!

Function takes a list of people waiting in line, its length, a list of colluding friends, and its length. Prints the new list to `stdout`.
> 2 votes

# Answer
# Charcoal, 26 bytes

```
≔⁻θ⁻θηε≔⌕θ§ε⁰ζＩ…θζＩεＩ✂⁻θηζ

```

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

```
≔⁻θ⁻θηε

```

Get the sublist of the colluding friends. This is actually calculated by removing the entries of colluding friends from the original list, then removing those entries from the original list.

```
≔⌕θ§ε⁰ζ

```

Get the position of the first of the colluding friends in the original list.

```
Ｉ…θζ

```

Output everyone ahead of the first of the colluding friends.

```
Ｉε

```

Output the colluding friends.

```
Ｉ✂⁻θηζ

```

Output everyone else who wasn't ahead. (We already calculated this list but it actually costs a byte to save this rather than recalculating it.)
> 1 votes

# Answer
# Red, 124 bytes

```
func[a b][m: 0 until[m: m + 1 find b a/:m]rejoin[take/part a m - 1
collect[foreach c a[if find b c[keep c]]]difference a b]]

```

Try it online!
> 1 votes

---
Tags: code-golf
---


title: Convert between balanced bases!

text:
# Question
Title: Convert between balanced bases!
## Balanced bases:

Balanced bases are essentially the same as normal bases, except that digits can be positive or negative, while in normal bases digits can only be positive.

From here on, balanced bases of base `b` may be represented as `balb` \- so balanced base 4 = `bal4`.

In this challenge's definition, the range of digits in a balanced base of base `b` is from `-(k - 1)` to `b - k`, where

```
k = ceil(b/2)

```

Examples of the range of digits in various balanced bases:

```
bal10:
  k = ceil(10/2) = 5
  range = -(5 - 1) to 10 - 5 = -4 to 5
        = -4, -3, -2, -1, 0, 1, 2, 3, 4, 5
bal5:
  k = ceil(5/2) = 3
  range = -(3 - 1) to 5 - 3 = -2 to 2
        = -2, -1, 0, 1, 2

```

Representations of numbers in balanced bases is basically the same as normal bases. For example, the representation of the number `27` (base 10) to `bal4` (balanced base 4) is `2 -1 -1`, because

```
  2 -1 -1 (bal4)
= 2 * 4^2 + -1 * 4 + -1 * 1
= 32 + (-4) + (-1)
= 27 (base 10)

```

## Task:

Your task is, given three inputs:

* the number to be converted (`n`)
    + this input can be flexible, see "I/O Flexibility"
* the base which `n` is currently in (`b`)
* the base which `n` is to be converted to (`c`)

Where `2 < b, c < 1,000`.

Return the number in balanced base `c` representation of `n`. The output can also be flexible.

The program/function must determine the length of `n` from the input itself.

### I/O Flexibility:

Your input `n` and output can be represented in these ways:

* your language's definition of an array
* a string, with any character as a separator (e.g. spaces, commas)

## Examples:

*Note that these use a Python array as `n` and the output. You may use whatever fits your language, as long as it fits within "I/O Flexibility"'s definition.*

```
[2, -1, -1] 4 7 = [1, -3, -1]
[1, 2, 3, 4] 9 5 = [1, 2, 2, -1, 2]
[10, -9, 10] 20 5 = [1, 1, 1, -2, 1, 0]

```

This is , so shortest code in bytes wins!

# Answer
# Mathematica, 85 bytes

```
#~FromDigits~#2~IntegerDigits~#3//.{p___,a_:0,b_,q___}/;b>⌊#3/2⌋:>{p,a+1,b-#3,q}&

```

**Explanation**

```
#~FromDigits~#2

```

Convert `#1` (1 is implied--input 1, a list of digits) into an integer base `#2` (input 2).

```
... ~IntegerDigits~#3

```

Convert the resulting integer into base `#3` (input 3), creating a list of digits.

```
... //.{p___,a_:0,b_,q___}/;b>⌊#3/2⌋:>{p,a+1,b-#3,q}

```

Repeatedly replace the list of digits; if a digit is greater than floor(`#3`/2), then subtract `#3` from it and add `1` to the digit to the left. If there is nothing on the left, insert a `0` and add `1`.
> 3 votes

# Answer
# APL (Dyalog Unicode), 47 bytes

```
{z↓⍨⊥⍨0=⌽z←m+u⊤v-⍺⊥m←⌈.5×1-u←⍺⍴⍨1+⌈⍺⍟1⌈|v←⍺⍺⊥⍵}

```

Try it online!

A dop that takes `n`, `b`, `c` as three separate values. Call it like `c (b f) n` where `f` is the submission.

Dyalog APL has a dfns library function `bt` that does various arithmetic in balanced ternary. Part of it is encode/decode, i.e. conversion between balanced ternary and plain integer:

```
encode←{                            ⍝ balanced ternary from integer.
    digs←1+⌈3⍟1⌈|⍵                  ⍝ number of ternary digits.
    tlz ¯1+(digs⍴3)⊤⍵+3⊥digs⍴1      ⍝ vector of bt digits.
}                                   ⍝ :: ∇ num → bt
decode←{3⊥⍵}                        ⍝ integer from balanced ternary.

```

(the hidden function `tlz` trims leading zeros.)

This submission is just a generalization of the above code.

### Ungolfed with comments

```
{                    ⍝ Input: ⍵←n, ⍺⍺←b, ⍺←c
    v←⍺⍺⊥⍵           ⍝ v← plain integer from base b

    u←⍺⍴⍨1+⌈⍺⍟1⌈|v   ⍝ u← copies of c with the size enough to fit the answer
              1⌈|v   ⍝ max(1,abs(v)) so that it works well with log(⍟)
           ⌈⍺⍟       ⍝ number of digits enough to fit v in plain base c
         1+          ⍝ ...enough to fit v in balanced base c
      ⍺⍴⍨            ⍝ that many copies of c

    m←⌈.5×1-u    ⍝ m← the minimum value in balanced base c with that many digits

    z←m+u⊤v-⍺⊥m  ⍝ z← n in balanced base c, possibly with leading zeros
            ⍺⊥m  ⍝ m as plain integer
          v-     ⍝ subtract from v (or, since m<0, add abs(m) to v)
        u⊤       ⍝ encode that value to plain base c, with that many digits
      m+         ⍝ revert the offset

    z↓⍨⊥⍨0=⌽z    ⍝ remove leading zeros from z and return it
       ⊥⍨0=⌽z    ⍝ count trailing zeros (⊥⍨) on reversed z
    z↓⍨          ⍝ drop that many items from z
}

```
> 3 votes

# Answer
# Perl 6, 121 bytes

```
->\n,\b,\c{sub f{sum [R,](@^n)Z*($^b X**0..*)}
first {f(b,n)==f c,$_},map {[$_-($_>floor c/2)*c for .base(c).comb]},0..*}

```

Slow brute-force solution.

How it works:

* `map {[ .base(c).comb]}, 0..*` -- Generate the lazy infinite sequence of natural numbers in base `c`, with each number represented as an array of digits.
* `$_ - ($_ > floor c/2) * c` -- Transform it by subtracting `c` from each digit that is greater than floor(c / 2).
* `first { f(b, n) == f(c, $_) }, ...` -- Get the first array of that sequence which when interpreted as a base `c` number, equals the input array `n` interpreted as a base `b` number.
* `sub f { sum [R,](@^n) Z* ($^b X** 0..*) }` -- Helper function that turns an array `@^n` into a number in base `$^b`, by taking the sum of the products yielded by zipping the reversed array with the sequence of powers of the base.
> 2 votes

# Answer
# SageMath, 53 bytes

```
f=lambda a,b,c:ZZ(a[::-1],b).balanced_digits(c)[::-1]

```

I’d be (pleasantly) surprised if there is a more concise way to write this in Sage than the obvious one. The only complication here is that Sage represents numbers as lists of digits with the least-significant digit first, whereas this challenge assumes most-significant first. So the digit lists need to be reversed.
> 2 votes

# Answer
## Mathematica, 118 114 bytes

```
IntegerDigits[#3~FromDigits~#2,k=⌊#/2⌋;#]//.{{a_,x___}/;a>k:>{1,a-#,x},{x___,a_,b_,y___}/;b>k:>{x,a+1,b-#,y}}&

```

and  are the 3-byte characters `U+230A` and `U+230B`, respectively. Converts `#3` to base `10` from base `#2`, then converts to base `#` (so the argument order is reversed from the examples). If any digit is greater than the maximum allowed digit `k=⌊#/2⌋`, decrement that digit by `#` and increment the next digit up (may need to prepend `1`). Keep doing this until all the digits are less than `k`.
> 1 votes

# Answer
## JavaScript (ES6), 89 bytes

```
(n,b,c,g=(n,d=n%c,e=d+d<c)=>[...(n=n/c+!e|0)?g(n):[],e?d:d-c])=>g(n.reduce((r,d)=>r*b+d))

```

100 bytes works for negative values of `n`.

```
(n,b,c,g=(n,d=(n%c+c)%c)=>[...(n-=d,n/=c,d+d<c||(d-=c,++n),n?g(n):[]),d])=>g(n.reduce((r,d)=>r*b+d))

```
> 1 votes

# Answer
# APL (Dyalog Unicode), ~~55~~ ~~51~~ 49 bytes

*Saved 4 bytes thanks to ovs*

```
{2↓((⊃(⊢,⍨⍵÷⍨-)x-⍨(⍵|(x←⌊⍵÷2)+⊃)),1∘↓)⍣(=⍥⊃)⍺⊥⍺⍺}

```

Try it online! (The  has been replaced by a `C` in the link because TIO has an older version of APL).

## Without a train, ~~55~~ ~~54~~ 52 bytes (SBCS)

*Saved a byte here too thanks to ovs*

```
{c←⍵⋄2↓{m←x-⍨c|⊃⍵+x←⌊c÷2⋄(c÷⍨⊃⍵-m),m,1↓⍵}⍣(=⍥⊃)⍺⊥⍺⍺}

```

Try it online!

There's already a better APL answer here, but here's mine anyway.

Can be invoked with `b (n f) c`.

`⍺⊥⍺⍺` converts `n` from base `b` to base 10. `(...)⍣(=⍥⊃)` repeatedly takes a vector whose first element is the rest of the number to be converted and whose other elements are the digits of the result. It repeats until the first digit of the created vector is 0 (given by `(=⍥⊃)`).

The `2↓` at the beginning is because the function is applied one extra time, so there's 2 zeroes at the start of the vector.

In the top snippet, `m` represents the new leading digit. It's just \\$(r + x (\mod c)) - x\\$ where \\$x\\$ is \\$\lfloor \frac{c}{2} \rfloor\\$ and \\$r\\$ is the head of the vector, the leftover part from last time.

To get the new leftover part, it's \\$\frac{(r - m)}{c}\\$ (this is guaranteed to be an integer since \\$r-m\\$ is divisible by \\$c\\$). Then we join this leftover part with `m` and `1↓⍵` (to drop last time's leftovers).
> 1 votes

# Answer
# , ~~105~~ ~~102~~ ~~101~~ 96 bytes

*Edit: -5 bytes thanks to Giuseppe*

```
function(a,b,c){x=a%*%b^(sum(a|1):1-1)
e={}
while(x){e=c(r<-x%%c-c*(x%%c>c/2),e);x=(x-r)%/%c}
e}

```

Try it online!

```
toFromBalBase=
function(a,b,c){
x=sum(a*b^(sum(a|1):1-1))   # get value x after conversion from balanced base b
e=NULL                      # initialze empty output vector of values
while(x){                   # repeat while x is not yet zero:
  e=c(...,e)                # prepend output vector with
    r<-(r=x%%c)             # define r as x mod c (base to convert to)
    -(r>c/2)*c              # adjusted to be balanced
  x=(x-r)%/%c}              # and update x to result of division,
                            # after accounting for possibly-negative remainder.
e}                          # finally, output e = output vector with all positive and negative
                            # remainders prepended

```
> 1 votes

---
Tags: code-golf, math, base-conversion
---


title: just a caesar cipher... with a twist

text:
# Question
Title: just a caesar cipher... with a twist
I have been going to puzzling.se, and people over there write stuff in rot13 a lot, sot this gave me an idea:
Write a program that takes 2 inputs, a string and integer:

1. the message to encode or decode
2. how far to shift

You can input in a function call, and output in any legal way twist:
it **must** work with any printable ascii character. Example code:

```
def ceasar_cipher(message,shift):
    o = ""
    for n in message:
        o+=(chr(ord(n)+shift))
    return o

```

python 3 examples:

input:

> ceasar\_cipher(“hello, world”,13):

output:

> "uryy|9-\x84|\x7fyq."

This is code-golf, so shortest code in bytes wins.
The output should be a string
-Can raise an error if it will go past ASCII-characters, or just not shift said characters
Good luck!

# Answer
> 9 votes
# BQN, 1 byte

Anonymous tacit infix function. Order of arguments doesn't matter.

```
+

```

Try BQN!

# Answer
> 5 votes
# 05AB1E, ~~4~~ 3 bytes

crossed out 4 is still regular 4 ;(

*-1 byte thanks to @Kevin Cruijssen.*

```
Ç+ç

```

Try it online!

```
Ç+ç  # full program
 +   # increment...
Ç    # charcodes of...
     # implicit input
 +   # by...
     # implicit input
  ç  # convert to chars
     # implicit output

```

# Answer
> 4 votes
# , 4 bytes

Anonymous tacit function taking two arguments in any order.

```
`c$+

```

Try K!

`+` add the arguments (this implicitly converts the characters to code points

`$` cast to…

``c` character

# Answer
> 3 votes
# C (gcc), 32 bytes

```
f(s,n)char*s;{for(;*s;*s+++=n);}

```

Try it online!

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

```
FromCharacterCode[ToCharacterCode@#+#2]&

```

Try it online!

# Answer
> 2 votes
# Vyxal, `s`, 3 bytes

```
C+C

```

## Explained

```
C     # Convert input string to a list of ord values
 +    # Add implicit number shift
  C   # Convert back to a list of chars and output

```

If it must absolutely be a function:

# 7 bytes

```
λ2|C+C;

```

## Explained

```
λ2|C+C;
λ2|      # Start a lambda with two arguments
   C+C   # Same as the full program
      ;  # Close lambda

```

# Answer
> 2 votes
# Stax, 4 bytes

```
{n+m

```

Run and debug it

a downside of `m` printing stuff with newline is that you need an explicit bracket.

# Answer
> 1 votes
# Jelly, 3 bytes

```
O+Ọ

```

Try it online!

## Explanation

```
O+Ọ  Main Link
O    chr->ord of left argument
 +   add (left with right; implicit vectorization)
  Ọ  ord->chr of left argument

```

# Answer
> 1 votes
# Charcoal, 8 bytes

```
⭆η℅⁺Ｉθ℅ι

```

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

```
 η          Second input
⭆           Map over characters and join
       ι    Current character
      ℅     Ordinal
   ⁺        Plus
     θ      First input
    Ｉ       Cast to integer
  ℅         Character
            Implicitly print

```

# Answer
> 1 votes
# Retina, 18 bytes

```
"$+"+T` -þ`!-ÿ
0A`

```

Try it online! Works on all ISO-8859-1 characters as long as the result does not exceed U+00FF. Add 2 bytes to extend the output range to U+07FF. Add a further 2 bytes to extend the output range to UCS-2 characters up to U+FFFF. Explanation:

```
"$+"+`

```

Repeat the given number of times.

```
T` -þ`!-ÿ

```

Bump all the supported code points up by 1.

```
0A`

```

Delete the count.

# Answer
> 1 votes
# Husk, 6 bytes

```
mȯc+⁰c

```

Try it online!

```
m       # map over each element in arg 2
 ȯ      # 3 functions:
     c  # convert character to value
   +⁰   # add arg 1
  c     # convert back to character

```

# Answer
> 1 votes
# Ruby 2.7, ~~33~~ 30 bytes

```
->w,s{w.bytes.map{(_1+s).chr}}

```

Try it online!

Returns an array of chars. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves two bytes.

---
Tags: code-golf, alphabet, cryptography, text-processing
---


title: Change the rules of Life

text:
# Question
Title: Change the rules of Life
Life-like cellular automaton are cellular automaton that are similar to Conway's Game of Life, in that they operate on a (theoretically) infinitely large square grid, where each cell has exactly 8 neighbours, and is one of 2 states, namely alive and dead.

However, these Like-like versions are different in a crucial way: the rules for a given cell to come alive and the rules for a given cell to survive to the next generation.

For example, classic Game of Life uses the rule `B3/S23`, meaning that it takes 3 alive cells to birth a new one, and either 2 or 3 living neighbours to survive. For this challenge, we will assume that neighbours do not include itself, so each cell has exactly 8 neighbours.

Your task is, given a starting configuration, a birth rule, a survival rule and a positive integer (the number of generations to be run), simulate the Life-like automaton using those rules for the number of generations given in the shortest code possible. The starting configuration will be a square matrix/2-dimensional array or a multiline string, you may choose. The others may be given in any reasonable format and method.

For example, if the birth rule was `12345678` (any living neighbours), the survival rule was `2357` and the starting configuration was

```
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

```

the next two generations would be

```
Generation 1:           Generation 2:

0 0 0 0 0               1 1 1 1 1
0 1 1 1 0               1 1 0 1 1
0 1 0 1 0               1 0 1 0 1
0 1 1 1 0               1 1 0 1 1
0 0 0 0 0               1 1 1 1 1

```

If the number of generations given was 10, the output would be something along the lines of

```
0 1 1 1 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 1 1 1 0

```

You do not have to handle changes that happen outside of the bounds given by the input matrix, however, all cells outside the matrix begin dead. Therefore, the input matrix may be any size, up to the maximum value your language can support. You do not have to output the board between generations.

This is a so the shortest code wins.

## Test cases

These use the `B/S` notation to indicate the rules used

`B2/S2`, `generations = 100`, configuration:

```
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0

```

Output:

```
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0
1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

```

---

`B1357/S2468`, `generations = 12`, configuration:

```
1 0 1 0 1 0
0 1 1 0 1 0
1 0 0 0 0 0
0 0 0 0 0 1
1 1 1 1 1 0
0 1 1 0 0 1

```

Output:

```
0 1 0 0 0 0
0 1 1 1 1 0
0 1 0 1 1 0
1 1 1 0 0 0
0 0 1 1 1 0
0 1 1 0 0 0

```

If you need to generate more test cases, you can use this wonderful simulator. Please make sure to limit the board size

# Answer
# MATL, ~~24~~ 23 bytes

```
xx:"tt3Y6Z+1Gm<8M2Gmb*+

```

Inputs are:

* Array with birth rule
* Array with survival rule
* Number of generations
* Matrix with initial cell configuration, using `;` as row separator.

**Try it online!** Or see test cases: **1**, **2**.

For a few bytes more you can see the **evolution in ASCII art**.

### Explanation

```
xx      % Take two inputs implicitly: birth and survival rules. Delete them
        % (but they get copied into clipboard G)
:"      % Take third input implicitly: number of generations. Loop that many times
  tt    %   Duplicate twice. This implicitly takes the initial cell configuration
        %   as input the first time. In subsequent iterations it uses the cell
        %   configuration from the previous iteration
  3Y6   %   Push Moore neighbourhood: [1 1 1; 1 0 1; 1 1 1]
  Z+    %   2D convolution, maintaining size
  1G    %   Push first input from clipboard G: birth rule
  m     %   Ismember: gives true for cells that fulfill the birth rule
  <     %   Less than (element-wise): a cell is born if it fulfills the birth rule
        %   *and* was dead
  8M    %   Push result of convolution again, from clipboard M
  2G    %   Push second input from clipboard G: survival rule
  m     %   Ismember: gives true for cells that fulfill the survival rule
  b     %   Bubble up the starting cell configuration
  *     %   Multiply (element-wise): a cell survives if it fulfills the survival
        %   rule *and* was alive
  +     %   Add: a cell is alive if it has been born or has survived, and those
        %   are exclusive cases. This produces the new cell configuration
        % Implicit end loop. Implicit display

```
> 10 votes

# Answer
# Wolfram Language (Mathematica), ~~144~~ 122 bytes

```
CellularAutomaton[{Tr[2^#&/@Flatten@MapIndexed[2#+2-#2[[1]]&,{#2,#3},{2}]],{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},#,{{#4}}]&

```

Try it online!

Example usage:

```
%[RandomInteger[1, {10, 10}], {2, 3}, {3}, 5]

```

uses a 10x10 random grid as a start, survives with either 2 or 3 neighbors, births with 3 neighbors, plot result at 5 iterations.
> 3 votes

# Answer
# , 256 bytes

```
function(x,B,S,r){y=cbind(0,rbind(0,x,0),0)
n=dim(y)[1]
z=c(1,n)
f=function(h){w=-1:1
b=h%%n+1
a=(h-b+1)/n+1
'if'(a%in%z|b%in%z,0,sum(x[w+b,w+a])-x[b,a])}
while(r){x=y
for(i in 1:n^2){u=f(i-1)
y[i]=u%in%B
y[i]=(y[i]&!x[i])|(x[i]&(u%in%S))}
r=r-1}
y[-z,-z]}

```

Try it online!

Sadly, this does not look as golfed as I'd hoped.

**Input**: an R matrix, and the challenge parameters. **Output**: the matrix after R generations.

The algorithm pads the matrix with zeros to handle the boundaries. Then, iteratively: 1st) it applies the Birth rule and 2nd) it kills the pre-existing cells that did not pass the Survival rule. Padding is removed when returning.
> 2 votes

# Answer
# Python 2, ~~156~~ ~~149~~ 146 bytes

```
lambda R,g,c:g and f(R,g-1,[[`sum(sum(l[y+y/~y:y+2])for l in c[x+x/~x:x+2])-c[x][y]`in R[c[x][y]]for y,_ in e(c)]for x,_ in e(c)])or c
e=enumerate

```

Try it online!

Takes input:

* `R`ules: `[birth,survial]` rules as list of `string`. eg.(`['135','246']`)
* `g`enerations: `int`
* `c`onfiguration: Square 2D array of `1/0` or `True/False`

Returns 2d array of `True/False`
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~38~~ ~~36~~ 34 bytes (SBCS)

* Saved ~~2~~ 4 bytes thanks to @ovs!

```
{(((1⊥,)∊⍺(⍵+1)⊃⍨4⊃,)⍤⊢⌺3 3⍣⍵⍵)⍺⍺}

```

Try it online!

Can be invoked with `birth_rule (start_grid f epochs) survival_rule`, where `f` is the operator. Requires 0-indexing.

~~For some reason, using the trains `(+/,)` and `(4⊃,)` to make it 36 bytes doesn't work.~~ As ovs explained, it's because  calls functions dyadically. Anyway, their new solution is 34 bytes.

---

can repeatedly apply a function some number of times, given a starting value. In this case, the starting value is the left operand, and the right operand tells it how many times to repeat.

`((1⊥,)∊⍺(⍵+1)⊃⍨4⊃,)⍤⊢⌺3 3` computes the next generation. The stencil operator () creates windows of a given shape (a 3x3 square here), applies a function on each of them, and puts them back together into a matrix. For cells on the edge of the grid, it will use zeroes, which works well with this challenge.

The train `((1⊥,)∊⍺(⍵+1)⊃⍨4⊃,)⍤⊢` is applied to each of those windows. `⍤⊢` applies the stuff before it to the second argument. `1⊥,` calculates the number of neighbors (including the cell) by turning the 2D window into a vector (`,`) and then summing it (`1⊥`).  checks if that the number of neighbors is in either the birth rule or survival rule vector. Whether the birth rule or survival rule is chosen depends on the train `⍺(⍵+1)⊃⍨4⊃,`.

`4⊃,` turns the window into a vector and chooses the 5th cell, which is the cell we are calculating the next generation of. `⍺(⍵+1)` is an array where the first element is the birth rule and the second element is the survival rule, but with its elements increased by one (because we're including the current cell). Then `⊃⍨` uses the current cell/5th cell/middle cell to index into this array, so if the cell's dead (0) the birth rule will be used, and if the cell is alive (1) the survival rule will be used.
> 1 votes

---
Tags: code-golf, game, cellular-automata, game-of-life, binary-matrix
---