title: Manchester encode a data stream

text:
# Question
Title: Manchester encode a data stream
Manchester coding is a telecom protocol used in radio communications that guarantees bit transitions at a regular interval so a receiver can recover the clock rate from the data itself. It doubles the bitrate, but is cheap and simple to implement. It is widely used by amateur radio operators.

The concept is very simple: at a hardware level, the clock and data lines are simply XORed together. In software, this is portrayed as converting an input stream of bits into a double-rate output stream, with each input '1' translated to a '01' and each input '0' translated to a '10'.

This is an easy problem, but open to a lot of implementations because of its bitstream nature. That is, the encoding is conceptually a bit-by-bit process instead of a byte-by-byte process. So we all agree on endianness, the least significant bits of the input become the least significant byte of the output.

Golfing time! Write a function that, given an arbitrary length array of bytes, returns an array of that data manchester encoded.

Input and output should be considered little-endian, least significant byte first, and least significant BIT first in the bit stream.

**ASCII bitstream drawing**:

```
bit #      5 4 3 2 1 0                                5  4  3  2  1  0
IN ------- 1 0 1 0 1 1 ---> [manchester encoder] ---  01 10 01 10 01 01 ----> OUT

```

**Examples**:

```
Example 1 (hex):
       LSB              MSB     <-- least sig BYTE first
IN : [0x10, 0x02]
OUT: [0xAA, 0xA9, 0xA6, 0xAA]

Example 1 (binary):
      msb  lsb                      msb  lsb  <-- translated hex, so msb first
BIN: [00010000, 00000010]                     <-- least sig NIBBLE...
BIN: [10101010, 10101001, 10100110, 10101010] <-- becomes least sig BYTE
         LSB                           MSB

Example 2
IN :  [0xFF, 0x00, 0xAA, 0x55]
OUT: [0x55, 0x55, 0xAA, 0xAA, 0x66, 0x66, 0x99, 0x99]

Example 3
IN : [0x12, 0x34, 0x56, 0x78, 0x90]
OUT: [0xA6, 0xA9, 0x9A, 0xA5, 0x96, 0x99, 0x6A, 0x95, 0xAA, 0x69]

Example 4
IN : [0x01, 0x02, 0x03, 0xF1, 0xF2, 0xF3]
OUT: [0xA9, 0xAA, 0xA6, 0xAA, 0xA5, 0xAA, 0xA9, 0x55, 0xA6, 0x55, 0xA5, 0x55]

```

**Rules**:

* Solution only requires algorithm to convert input to output.
* Acquiring input and printing output are NOT a required part of the solution, but may be included. You are encouraged to provide your test/print code if not included in your solution.
* Input is an array of 8-bit bytes (whatever that may mean in your language of choice), NOT a text string. You can use strings as the storage format if convenient in your language, but non-printable characters (i.e. 0xFF) must be supported. Input can also take a length if necessary.
* Memory for output must be allocated by your routine, not provided. **edit: unnecessary requirement**
* Output is also an array of 8-bit bytes, and a length if necessary.
* Must support at least 16KB input
* Performance must not be too horrible: \< 10s for 16KB
* Least-significant byte first in memory.

**Side-channel challenge**:

* Challenge another user's answer by proving your code is faster, more memory efficient, or produces a smaller binary!

## **Get golfing! Shortest code wins!**

# Answer
## GolfScript 28 characters

```
{2{base}:|~4|43691-~256|~\}%

```

Equivalent version without obfuscating optimization:

```
{2base 4base 43691-~256base~\}%

```

The code accept input as an array of integers, and return ditto.

For each number in the array the number is converted to base 2 array form, it is then converted back to a number as if it was base 4, this has the effect of spacing out the bits with a 0 in between each. 43691 is then subtracted from the number, and the result is binary inverted, this is equivalent to subtracting the number from 43690 (43690 = 0b1010101010101010). The number is then split into two parts by converting it to a base 256 array, the array is decomposed and the order of the two resulting numbers is inverted.

Example input:

```
[1 2 3 241 242 243]

```

Example output:

```
[169 170 166 170 165 170 169 85 166 85 165 85]

```
> 6 votes

# Answer
## c -- 224 characters

I believe that this is functional, including the allocation of memory requirement since dropped.

```
#include <stdlib.h>
int B(char i){int16_t n,o=0xFFFF;for(n=0;n<8;++n)o^=((((i>>n)&1)+1))<<(2*n);
return o;}char* M(char*i,int n){char*o=calloc(n+1,2),*p=o;do{int r=B(*i++);
*p++=0xFF&r;*p++=(0xFF00&r)>>8;}while(--n);return o;}

```

The working part of the code is a loop over the bits of each character, noting that ((bit+1) exclusive-or 3) is the output bit pair, and applying lots of shifting and masking logic to get everything to line up.

As is c's wont, it works on the data as characters. The test scaffold won't accept 0 bytes (because c treats them as string ending), but the working code has no such limitation.

It might be golfed little more by copy the byte conversion work inline.

Test run (with improved test scaffold):

```
$ gcc -g manchester_golf.c
$ ./a.out AB xyz U
'AB':
[ 0x41, 0x42 ]
[ 0xa9, 0x9a, 0xa6, 0x9a ]
'xyz':
[ 0x78, 0x79, 0x7a ]
[ 0x6a, 0x95, 0x69, 0x95, 0x66, 0x95 ]
'U':
[ 0x55 ]
[ 0x99, 0x99 ]

```

Commented, less machine dependent, and with test scaffold

```
/* manchester.c
 *
 * Manchester code a bit stream least significant bit first
 *
 * Manchester coding means that bits are expanded as {0,1} --> {10, 01}
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdint.h>
#include <string.h>

/* Caller must insure that out points to a valid, writable two byte
   buffer filled with 0xFF */
int16_t manByte(char i){
  int16_t n,o=0xFFFF;
  printf("Manchester coding byte 0x%hx...\n",i);
  for(n=0; n<CHAR_BIT; ++n)
    o ^= (
      (
       (
        (i>>n)&1) /* nth bit of i*/
       +1) /* +1 */
      ) <<(2*n) /* shifted up 2*n bits */
      ;
  printf("\tas 0x%hx\n",o);
  return o;
}

char* manBuf(const char*i, int n){
  char*o=calloc(n+1,2),*p=o;
  do{
    int16_t r=manByte(*i++);
    *p++= 0xFF&r;
    *p++=(0xFF00&r)>>8;
  } while(--n);
  return o;
}

void pbuf(FILE* f, char *buf, int len){
  int i;
  fprintf(f,"[");
  for(i=0; i<len-1; i++)
    fprintf(f," 0x%hhx,",buf[i]);
  fprintf(f," 0x%hhx ]\n",buf[len-1]);
}

int main(int argc, char**argv){
  int i;
  for(i=1; i<argc; i++){
    int l=strlen(argv[i]);
    char *o=manBuf(argv[i],l);
    printf("'%s':\n",argv[i]);
    pbuf(stdout,argv[i],l);
    pbuf(stdout,o,l*2);
    free(o);
  }
  return 0;
}

```
> 3 votes

# Answer
# J, 36

```
,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)

```

Outline of explanation (See J Vocabulary for reference):

* `,@:(3 :'...'"0)` applies the ... to each input "byte" as y, resulting in two bytes (integers) each. The result is flattened by `,`.
* `y#:~8#2` is equivalent to `2 2 2 2 2 2 2 2 #: y`, or vector of the 8 least significant base-2 digits of y.
* `4|.` swaps the front and back 4 bits by rotating by 4 positions.
* `(,.~-.)` is equivalent to `3 :'(-. y) ,. y'`, or not of the argument 'stitched' to the argument (taking on shape 8 2).
* `#.2 8$,` flattens the result giving the bitstream, reshapes to 2 rows of 8, and converts from base 2.

Example usage (J, interactive):

```
    ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0) 1 2 3 241 242 243
,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0) 1 2 3 241 242 243
169 170 166 170 165 170 169 85 166 85 165 85

```

Speed information (J, interactive):

```
   manchester =: ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)
manchester =: ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)
   data =: 256 | i. 16384
data =: 256 | i. 16384
   100 (6!:2) 'manchester data'
100 (6!:2) 'manchester data'
0.243138

```

Mean time for 16kb is just under .25s, Intel Core Duo 1.83Ghz or similar.
> 3 votes

# Answer
# OCaml + Batteries, 138 117 characters

```
let m s=Char.(String.(of_enum[?chr(170-Enum.sum[?d land
p*p|p<-List:[1;2;4;8]?])|c<-enum s/@code;d<-List:[c;c/16]?]))

```

**Tests:**

With

```
let hex s = String.(enum s/@(Char.code|-Printf.sprintf "%02x")|>List.of_enum|>join" ")

```

The results are:

```
m "\x12\x34\x56\x78\x90" |> hex;;
- : string = "a6 a9 9a a5 96 99 6a 95 aa 69"
m "\x10\x02" |> hex;;
- : string = "aa a9 a6 aa"
m "\xFF\x00\xAA\x55" |> hex;;
- : string = "55 55 aa aa 66 66 99 99"
m "\x12\x34\x56\x78\x90" |> hex;;
- : string = "a6 a9 9a a5 96 99 6a 95 aa 69"
m "\x01\x02\x03\xF1\xF2\xF3" |> hex;;
- : string = "a9 aa a6 aa a5 aa a9 55 a6 55 a5 55"

```

As a benchmark, with:

```
let benchmark n =
  let t = Unix.gettimeofday() in
  assert(2*n == String.(length (m (create n))));
  Unix.gettimeofday() -. t

```

I get:

```
# benchmark 16_384;;
- : float = 0.115520954132080078

```

on my MacBook.
> 3 votes

# Answer
## Haskell, 76 characters

```
import Bits
z a=170-sum[a.&.p*p|p<-[1,2,4,8]]
y a=[z a,z$a`div`16]
m=(>>=y)

```

Test runs:

```
> testAll
input      [10, 02]
encoded    [AA, A9, A6, AA]
  pass
input      [FF, 00, AA, 55]
encoded    [55, 55, AA, AA, 66, 66, 99, 99]
  pass
input      [12, 34, 56, 78, 90]
encoded    [A6, A9, 9A, A5, 96, 99, 6A, 95, AA, 69]
  pass
input      [01, 02, 03, F1, F2, F3]
encoded    [A9, AA, A6, AA, A5, AA, A9, 55, A6, 55, A5, 55]
  pass

```

Performance is well within spec. at 1MB in ~1.2s on my oldish laptop. It suffers because the input is convert to and from a list, rather then processed as a `ByteArray`.

```
> dd bs=1m count=1 if=/dev/urandom | time ./2040-Manchester > /dev/null
1+0 records in
1+0 records out
1048576 bytes transferred in 1.339130 secs (783028 bytes/sec)
        1.20 real         1.18 user         0.01 sys

```

The source, 2040-Manchester.hs, includes the code, tests, and main function for a command line filter.
> 3 votes

# Answer
## Python, 87 chars

`M` is the function requested in the problem. It calls `N` for each nybble and splices everything back into a list.

```
N=lambda x:170-(x&1|x*2&4|x*4&16|x*8&64)
M=lambda A:sum([[N(a),N(a>>4)]for a in A],[])

print map(hex,M([0x10,0x02]))
print map(hex,M([0xff,0x00,0xaa,0x55]))
print map(hex,M([0x12, 0x34, 0x56, 0x78, 0x90]))
print map(hex,M([0x01, 0x02, 0x03, 0xF1, 0xF2, 0xF3]))

```

generates

```
['0xaa', '0xa9', '0xa6', '0xaa']
['0x55', '0x55', '0xaa', '0xaa', '0x66', '0x66', '0x99', '0x99']
['0xa6', '0xa9', '0x9a', '0xa5', '0x96', '0x99', '0x6a', '0x95', '0xaa', '0x69']
['0xa9', '0xaa', '0xa6', '0xaa', '0xa5', '0xaa', '0xa9', '0x55', '0xa6', '0x55', '0xa5', '0x55']

```
> 1 votes

# Answer
# APL (Dyalog Extended), 22 bytes

```
∊(⌽(2⍴256)⊤43690-4⊥⊤)¨

```

Try it online!

Port of the GolfScript answer.

```
∊(⌽(2⍴256)⊤43690-4⊥⊤)¨       Monadic train:
  ⌽(2⍴256)⊤43690-4⊥⊤         Define a helper function taking an integer n:
                    ⊤           Convert n to base 2. Monadic ⊤ is an Extended feature.
                  4⊥            Convert the result from base 4.
                                This puts the 1 digits of n
                                in odd indices of the intermediate result.
            43960-              Subtract from 43690.
    (2⍴256)⊤                    Convert to 2 base-256 digits, corresponding to
                                nibbles of n.
  ⌽                            Reverse the order of these bytes.
 (                   )¨       Call the helper function for each element of the input
∊                             and flatten the results into a list.

```
> 1 votes

# Answer
# C, 164 bytes

Takes in a series of hex bytes and converts to manchester binary stream.

```
#include <stdio.h>
main(int c,char **v){int i,b,x,j=0;while(++j<c{sscanf(v[j],"%x",&b);x=b^0xff;for(i=9;--i;){printf("%d%d",x&1,b&1);x=x>>1;b=b>>1;}printf("\n");}}

```

---

```
#include <stdio.h>
main(int c,char **v){
int i,b,x,j=0;
while(++j<c){
    sscanf(v[j],"%x",&b);
    x=b^0xff;
    for(i=9;--i;){
        printf("%d%d",x&1,b&1);
        x=x>>1;b=b>>1;}
    printf("\n");}}

```

---

Test:

```
./a.out 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00 10 20 30 40 50 60 70 80 90 a0 b0 c0 d0 e0 f0

```

Output:

```
1010101010101010
0110101010101010
1001101010101010
0101101010101010
1010011010101010
0110011010101010
1001011010101010
0101011010101010
1010100110101010
0110100110101010
1001100110101010
0101100110101010
1010010110101010
0110010110101010
1001010110101010
0101010110101010
1010101010101010
1010101001101010
1010101010011010
1010101001011010
1010101010100110
1010101001100110
1010101010010110
1010101001010110
1010101010101001
1010101001101001
1010101010011001
1010101001011001
1010101010100101
1010101001100101
1010101010010101
1010101001010101

```

---

16kb test data set generator:

test\_data.c:

```
#include <stdio.h>
void main()
{
int i=16*1024;
while(i--)
{
    printf("0x%02x ", i&0xFF);
}
printf("\n");
}

```

---

```
cc test_data.c -o test_data

```

1.6G i5dual core time trial:

```
time ./a.out `./test_data` > test.out
real    0m0.096s
user    0m0.090s
sys 0m0.011s

```
> 0 votes

# Answer
# PHP, 156 bytes

```
function f($i){foreach($i as$n){$b=str_split(str_replace([0,1,2],[2,'01',10],
str_pad(decbin($n),8,0,0)),8);$o[]=bindec($b[1]);$o[]=bindec($b[0]);}return$o;}

```

Given the input `[0, 1, 2, 3, 4, 5]`, it returns:

```
[170, 170, 169, 170, 166, 170, 165, 170, 154, 170, 153, 170]

```

It encodes 16 KiB of data in 0.015 seconds and 1 MiB of data in about 0.9 seconds.

The ungolfed code, another implementation (longer and about twice slower) and the test cases can be found on my code-golf solutions page on Github.
> 0 votes

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


title: Indexing the Extended Fibonacci Numbers

text:
# Question
Title: Indexing the Extended Fibonacci Numbers
You've probably heard of Fibonacci numbers. Ya know, that integer sequence that starts with `1, 1`, and then each new number is the sum of the last two?

```
1 1 2 3 5 8 13...

```

And so on. Challenges about Fibonacci numbers are pretty popular 'round here. But who says that the Fibonacci numbers have to start with `1, 1`? Why couldn't they start with `0, 1`? Alright, let's redefine them to start at 0:

```
0 1 1 2 3 5 8 13...

```

But... We don't have to stop there either! If we can add the last two numbers to get the next one, we could also subtract the first number from the second number to prepend a new number. So it could start with `1, 0`:

```
1 0 1 1 2 3 5 8 13...

```

We can even end up with negatives:

```
-1 1 0 1 1 2 3 5 8 13...

```

And this series also goes on forever. I think it's interesting how it ends up kinda mirroring the regular Fibonacci numbers, just with every other number made negative:

```
13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13...

```

Let's call this series the "Extended Fibonacci Number", or **EFN**. Since there isn't really an obvious negative number to start this series on, we'll say that **0** shows up at **0**, the regular Fibonacci numbers extend in to the positive indices, and the negative (half-negative?) Fibonacci numbers extend in to the negative indices, like so:

```
Indices: ...-7  -6 -5  -4 -3  -2 -1  0  1  2  3  4  5  6  7 ...
Values:  ...13  -8  5  -3  2  -1  1  0  1  1  2  3  5  8  13...

```

This leads into today's challenge:

> Given an integer **N**, return *every* index at which **N** appears in the **EFN** series.

Some random observations on this task:

* **1** appears more times in the **EFN** than any other number: `[-1, 1, 2]`. No number will appear in more than 3 places.
* Every Fibonacci number \> 1 will show up either once (3, 8, 21, etc.) or twice (2, 5, 13, etc.)

## Rule Clarifications:

* If `abs(N)` is not a Fibonacci number, it will never appear in the **EFN** series, so you must output nothing/an empty collection if possible, or if that is not possible in your language, you can output some constant non-numeric value.
* If **N** appears at multiple places in the **EFN**, your output does not need to be sorted. Although each index must appear exactly once.
* Although most challenges allow you to choose whether you want to use 1-based or 0-based indexing, this challenge *must* use the indexing described (where 0 appears at 0).
* You may take I/O through any standard format.

## Test Cases

```
-13: []
-12: []
-11: []
-10: []
-9: []
-8: [-6]
-7: []
-6: []
-5: []
-4: []
-3: [-4]
-2: []
-1: [-2]
0: 0
1: [-1, 1, 2]
2: [-3, 3]
3: [4]
4: []
5: [-5, 5]
6: []
7: []
8: [6]
9: []
10: []
11: []
12: []
13: [-7, 7]

```

And some larger test cases:

```
89: [-11, 11]
1836311903: [46]
10000: []
-39088169: [-38]

```

As usual, shortest answer in bytes wins!

# Answer
> 9 votes
# Haskell, 78 bytes

*4 bytes saved thanks to nimi*

```
a#b=a:b#(a-b)
f 0=[0]
f a=do{(i,x)<-zip[0..a*a+1]$0#1;[-i|x==a]++[i|abs x==a]}

```

Try it online!

First we set up `(#)`, `(#)` takes two parameters, `a` and `b`, and returns the a list starting with `a` and followed by `b#(a-b)`. This creates an infinite list, but because Haskell is lazy we don't need to wory about it looping forever. This essentially works backwards creating the Fibonacci sequence before a certain pair. For example `(0#1)` would be the list of all the Fibonacci numbers with negative index.

From here we make `f`. `f` takes a argument `a` which is the number we are trying to find in the sequence. Here we use `do` notation to do a list comprehension. We start by taking the first `a*a+1` elements of the list `0#1`1. Since the function `a*a+1` grows faster than the inverse of the Fibonacci sequence we can be sure that if we check within this bound we will find all the results. This prevents us from searching an infinite list. Then for each value `x` and index `i`, if `x==a` we found `a` in the negative half of the sequence so we return `-i`, and if `abs x==a` we return `i` as well because the absolute value of the negative half is the positive half so we found it there.

Since this makes the list `[0,0]` for `0` we hardcode the correct output for that one.

1: This trick is taken from Οurous' Clean answer. The same speedup aplies here as there, replace `a*a+1` with `abs a+1` to save a lot of time.

# Answer
> 5 votes
# Clean, ~~132~~ ~~120~~ 109 bytes

```
import StdEnv
g n|n<2=n=g(n-1)+g(n-2)
?k=[e\\p<-[0..k*k+1],e<-if(isOdd p)([~p,p]%(0,k))[p*sign k]|g p==abs k]

```

Try it online!

`g :: Int -> Int` is the Fibonacci function.
`? :: Int -> [Int]` just indexes into the elements of the EFN within `k^2+1` of `0`.

For a version that runs in a sane ammount of time, change `k*k+1` to `abs k+1`.

# Answer
> 3 votes
# Jelly, 11 bytes

```
A‘ŒRÆḞẹ_A_2

```

Try it online!

# Answer
> 2 votes
# JavaScript (ES6),  ~~94~~  93 bytes

```
n=>(g=a=>a*a<n*n?g(b,b+=a,i++):a%n)(i=0,b=1)?[]:i&1?n<0?~n?[]:-2:i-1?[-i,i]:[-i,i,2]:n<0?-i:i

```

Try it online!

Or **92 bytes** if we can return \\$-0\\$ for \\$n=0\\$.

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

Requires `⎕IO←0`

```
{X-⍨⍸⍵=F,⍨⌽0,F×1 ¯1⍴⍨≢F←{⍵≤1:1⋄+/∇¨⍵-1 2}¨⍳X←1+|⍵}

```

Try it online!

# Answer
> 1 votes
# Retina 0.8.2, ~~104~~ 102 bytes

```
[1-9].*
$*
(-)?(\b1|(?>\3?)(\2))*(1)$|(0)?.*
$5$1$4$4$#2$*
-1(11)+$

^1(11)+$
-$&,$&
1+
$.&
^2$
-1,1,2

```

Try it online! Explanation:

```
[1-9].*
$*

```

Convert to unary, unless the input is zero.

```
(-)?(\b1|(?>\3?)(\2))*(1)$|(0)?.*
$5$1$4$4$#2$*

```

Calculate the Fibonacci index of the absolute value, but if the number is not a Fibonacci number then delete it, unless it was zero. This uses @MartinEnder's Fibonacci-testing regex.

```
-1(11)+$

```

Delete negative numbers whose absolute values are odd Fibonacci numbers.

```
^1(11)+$
-$&,$&

```

Add negative indices for odd positive Fibonacci numbers.

```
1+
$.&

```

Convert to decimal.

```
^2$
-1,1,2

```

Add the extra indices for `1`.

# Answer
> 1 votes
# Actually, 34 bytes

```
;╗3*;±kSix⌠;;AF@;1&@0>*YτD(s**╜=⌡░

```

Brute-force saves the day

Explanation:

```
;╗3*;±kSix⌠;;AF@;1&@0>*YτD(s**╜=⌡░
;╗                                  save a copy of the input (let's call it N) to register 0 (the main way to get additional values into functions)
  3*;±                              -3*N, 3*N
      kSi                           push to list, sort, flatten (sort the two values on the stack so that they are in the right order for x)
         x                          range(min(-3*N, 3*N), max(-3*N, 3*N))
          ⌠;;AF@;1&@0>*YτD(s**╜=⌡░  filter (remove values where function leaves a non-truthy value on top of the stack):
           ;;                         make two copies of parameter (let's call it n)
             AF                       absolute value, Fib(|n|)
               @;                     bring a copy of n to the top of the stack and make another copy
                 1&                   0 if n is divisible by 2 else 1
                   @0>                1 if n is negative else 0 (using another copy of n)
                      *               multiply those two values (acts as logical AND: is n negative and not divisible by 2)
                       YτD            logical negate, double, decrement (maps [0, 1] to [1, -1])
                          (s          sign of n (using the last copy)
                            **        multiply Fib(|n|), sign of n, and result of complicated logic (deciding whether or not to flip the sign of the value for the extended sequence)
                              ╜=      push value from register 0, equality comparison (1 if value equals N else 0)

```

Try it online!

# Answer
> 1 votes
# Python 3, 92 bytes

```
f=lambda x,l=[],i=0,a=0,b=1:i<x*x+2and f(x,l+[i][:a==x]+[-i][:i%2*2*a-a==x],i+1,b,a+b)or{*l}

```

Try it online!

Returns a set of indices.

# Answer
> 1 votes
# Python 2, ~~87~~ 85 bytes

```
f=lambda v,a=0,b=1,i=1:v*v>=a*a and[i]*(v==b)+[1-i]*((-1)**i*a==v)+f(v,b,a+b,i+1)or[]

```

Try it online!

# Answer
> 0 votes
# 05AB1E, 36 bytes

```
x*ÝʒÅfIÄQ}Ii®šë1KIdiÐ`ÉiD(ì}ëD`Èi(ë¯

```

There has to be a better approach.. \>.\> There are six (or seven if we include `0`) different scenarios for this challenge, and it's killing me..

Try it online or verify all test cases.

**Explanation:**

```
x*Ý            # Create a list in the range [0, (implicit) input * input * 2]
   ʒ     }     # Filter this list by:
    Åf         #  Where the Fibonacci value at that index
      IÄQ      #  Is equal to the absolute value of the input
Ii             # If the input is exactly 1:
  ®š           #  Prepend -1 to the list
ë              # Else:
 1K            #  Remove all 1s (only applies to input -1)
 Idi           #  If the input is non-negative:
    Ð`Éi   }   #   If the found index in the list is odd:
        D(ì    #    Prepend its negative index to the list
   ë           #  Else (the input is negative):
    D`Èi       #   If the found index in the list is even:
        (      #    Negate the found index
       ë       #   Else (found index is odd):
        ¯      #    Push an empty array
               # (Output the top of the stack implicitly as result)

```

Some step-by-step examples:

```
Input:  Filtered indices:  Path it follows (with actions) and result:

-8      [6]                NOT 1 → neg → even index → negate index: [-6]
-5      [5]                NOT 1 → neg → odd index → push empty array: []
-1      [1,2]              NOT 1 → (remove 1) neg → even remaining index: negate index: [-2]
0       [0]                NOT 1 → even index → negate index: [0]
1       [1,2]              1 → prepend -1: [-1,1,2]
5       [5]                NOT 1 → non-neg → odd index → Prepend neg index: [-5,5]
8       [6]                NOT 1 → non-neg → even index → (nothing): [6]

```

# Answer
> 0 votes
# Python 2, ~~95~~ ~~92~~ 94 bytes

```
x=input()
i=a=0;b=1
while x*x>=a:
 if 0<a==x:print i
 if[-a,a][i%2]==x:print-i
 a,b=b,a+b;i+=1

```

Try it online!

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 144 bytes

```
o=>{int c=0,n=1,i=0,k=Math.Abs(o);for(;c<k;i++,n+=c,c=n-c);return new[]{c>k|o<0?0.1:i,(i>0|o<0)&i%2>0&c==k?-i:0.1,o==1?2:0.1}.Where(p=>p!=0.1);}

```

Try it online!

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


title: Help Notwen simulate gravity!

text:
# Question
Title: Help Notwen simulate gravity!
Notwen wants to study the kinematics of bodies thrown from big heights in a uniform gravitational field but unfortunately he doesn't have the technical possibility to go to sufficiently high places and observe the objects while falling. But who doesn't want to see advances in science so... Let's help Notwen build a gravity simulator!

## Physical Background

An object dropped from a height \\$h\\$ (**without initial velocity**) in a uniform gravitational field, neglecting atmospheric effects such as drag or wind gains velocity and speeds up towards the ground with time. This "rate of change" of velocity in a unit of time is called gravitational acceleration. Near the surface of Earth, it is approximately equal to \\$g\approx9.8\frac{m}{s^2}\\$, but for the purposes of this challenge we will use the value \\$10\frac{m}{s^2}\\$, meaning that in a single second, an object increases its velocity by about \\$10 \frac{m}{s}\\$. Consider having a height \\$h\\$, which is a multiple of \\$100m\\$ and imagine dividing that height into equal intervals, each \\$100\\$ meters long. Notwen wants to measure how long it takes for the object to fall through each of those intervals, so that's what we aim to compute as well. Modern kinematics – skipping technicalities – tells us that: $$\Delta h\_k=v\_kt\_k+\dfrac{1}{2}gt\_k^2$$ where \\$\Delta h\_k\equiv\Delta h=100m\\$ for all values of \\$k\\$ in our case, \\$v\_k\\$ is the initial velocity at the beginning of our \\$k^\text{th}\\$ interval and \\$t\_k\\$ is the duration of the \\$k^\text{th}\\$ time interval (for reference, indexing starts at \\$0\\$ with \\$v\_0=0\\$). We also know that \\$v\_k\\$ has the following expression: $$v\_k=\sqrt{2g(\Delta h\_0+\Delta h\_1+\cdots+\Delta h\_{k-1})}=\sqrt{2gk\Delta h}$$ Numerically, we get \\$v\_k=\sqrt{2000k}\frac{m}{s}\\$ and plugging into the first equation and solving for \\$t\_k\\$ gives $$\color{red}{\boxed{t\_k=2\sqrt{5}\left(\sqrt{k+1}-\sqrt{k}\right)s}}\tag{\*}$$ So the object travels the first interval (\\$k=0\\$) in \\$4.4721s\\$, the second interval (\\$k=1\\$) in \\$1.8524s\\$ and so on (pastebin with more values).

## The challenge

**Input:** The height \\$h\\$ from which the object is thrown as either: a positive integer multiple of \\$100\\$, \\$h\\$ **or** the number of intervals \\$N=\frac{h}{100}\\$ (so either \\$700\\$ or \\$7\\$ would mean that \\$h=700m\\$) – which one is up to you.

**Output:** An ASCII art animation of a falling object, dropped from a height \\$h\\$ (details below).

The structure of an output frame must be as follows:

* \\$N\\$ newlines preceding the "ground", represented by at least one non-whitespace character (e.g. `@`). At least one of the characters of the ground must lie on the vertical that the object falls on.
* Another non-whitespace character representing the object (e.g. `X`), other than the one you chose for the ground.
* **Optionally**, a character at the beginning of each line representing the vertical axis or the wall made on \\$N\\$ lines. Any amount of leading and trailing spaces are fine as long as they are consistent between frames, as well as any amount of spaces between the wall and the object. Examples of valid frames include1 (for \\$h=700m\\$ or \\$N=7\\$):
```
| X                                       >
|                             @           >   A
|                                         >
|        or            or           or    >
|               O                         >
|                                         >
|                                         >
@@@             ^           -----            &&&

```

The object must start on the first line of the first frame, then after \\$t\_0\approx 4.47s\\$ the output should be flushed and your program should display the object on the same vertical but on the next line in the second frame; then after \\$t\_1\approx 1.85s\\$ the output should be flushed again and your program should display the object on the same vertical but on the next line in the third frame and so on, until the object reaches the line right above the ground. Example:

### Rules

* The output should be some text written to an interactive (flushable) console, a GIF, a separate file for each frame or some other reasonable technique of output.
* Each frame should completely overwrite the last frame and be in the same location.
* You can assume that the time required for the compiler / interpreter to output the text is negligible and the minimum precision permitted for computing the square roots is to 2 decimal places.
* You can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is , so try to complete the task in the least bytes you can manage in your language of choice.

---

1: I'm lenient about what constitutes a valid frame because I want to allow whatever suits your solution best and I'm not trying to add superfluous stuff to the challenge. If anything is unclear, ask in the comments.

# Answer
## JavaScript (ES7) + CSS + HTML, 340 bytes

```
f=n=>{o.style.height=n+'em';x.style.animationDuration=(n*20)**.5+'s';o.appendChild(x,x.remove())}
```

```
pre{position:relative;border:1px solid;height:5em;overflow:hidden}span{position:absolute;top:0;animation:x 10s cubic-bezier(0.33,0,0.67,0.33)both}@keyframes x{to{top:100%}}
```

```
<input type=number value=5 oninput=f(this.value)><pre id=o><span id=x>X
```

If I've got my sums right then the animation duration is \\$ \sqrt { 20 N } \\$ and then the CSS cubic-bezier does the rest.
> 3 votes

# Answer
# Charcoal, 28 bytes

```
Ｎθ↓θ⁴Ｆθ«Ｊ²ιＰXＲ⌊×φ×₂²⁰⁻₂⊕ι₂ι

```

Try it online! Link is to verbose version of code. Note: trailing space. You can observe the delay on TIO but you can't watch the animation so you'll have to imagine that from the output. Takes `N` as input. Explanation:

```
Ｎθ

```

Input `N`.

```
↓θ⁴

```

Print the wall and the ground, so that the output's shape is consistent.

```
Ｆθ«

```

Loop over each interval.

```
Ｊ²ιＰX

```

Place an `X` at the appropriate height.

```
Ｒ⌊×φ×₂²⁰⁻₂⊕ι₂ι

```

Output the current canvas contents and wait for the appropriate amount of time (truncated to the nearest millisecond).

```

```

Overwrite the `X` with a space.
> 2 votes

# Answer
# Perl 6, 81 bytes

```
{say "\e[s{"\n"x$_}-";map {say "\e[u{" \n"x 4.9e-6*$_²}o";sleep .01},^452*.sqrt}

```

"Try it online!", but TIO cannot handle the animation.

## Explanation

I chose a bit different approach (and I think it's for the better, though I don't know for sure). Instead of sleeping for times given by the formula in the OP, I just draw the appropriate situation "every 10 ms" (± errors induced by `sleep`).

That means that there are 100 frames a second, so if we denote the frame number by \\$k\\$, it must be \\$t=k/100\\$. And since we divide the vertical distance into 100 meter blocks, we can write the height as \\$h = 100n\\$, where \\$n\\$ is the number of blocks (given as an input). The height traveled in time \\$t\\$ is given by \\$h = gt^2/2\\$, so the number of blocks traveled is $$ n = \frac{1}{100} \tfrac 1 2 g t^2 = \tfrac 1 2 g \times 10^{-6} k^2 \approx 4.905\times 10^{-6} k^2. $$ We can invert it to get the total number of frames we need to render: $$ k = \frac{\sqrt n}{\sqrt{4.905\times 10^{-6}}} \approx 452 \times \sqrt n.$$

This suffices to write the function. It takes one argument, the number of blocks to render, i. e. \\$n\\$. First, we do `say "\e[s{"\n"x$_}-"`. That prints an ANSI escape sequence called *Save Cursor*, then it prints \\$n\\$ newlines, and after that, it prints a dash (the ground) and a newline. (This uses the cool feature of double quotes in Perl 6: you can inline result of any code right into the string by writing that code inside curly braces.)

After that, we make a sequence from 0 to \\$452\sqrt n\\$ (automatically truncated to integer) with `^452*.sqrt`, and we map over it. In each iteration, we print an *Unsave Cursor* ANSI sequence (which puts the cursor at the position where it was last saved), write \\$4.9\times 10^{-6} k^2\\$ strings "space+newline" (automatically truncated once again) and finally an `o` that denotes the object. Then we sleep for 10 ms, rinse and repeat.

Due to the automatic truncation, it just Does The Right Thing™ and moves the "o" only after each full 100 m of the fall.
> 2 votes

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

-3 bytes Thanks to "Don't be a x-triple dot" and "Jonathan Frech"

```
import time
h=input()
for k in range(h):print'\33[2J'+'\n'*k+'O'+'\n'*(h-k)+'^';time.sleep(2*5**.5*((k+1)**.5-k**.5))

```

Try it online!
> 1 votes

# Answer
# C# (.NET Core), ~~201~~, 180+13 = 193 bytes

Needs using System; for 13 additional bytes.

Strangely, Console.Clear() does not seem to be working for me on TIO. However, this runs perfectly in a console app under VS2017.

EDIT: Thanks to Embodiment of Ignorance for shortening up the loop, pointing out my unnecessary variable assign and unnecessary using System.Threading; statement (leftover from VS copying), and pointing out that the ground was required! Total of 8 bytes golfed thus far with the addition of the ground. Ty Ty!

```
x=>{for(var j=x;j>0;System.Threading.Thread.Sleep((int)(4470*(Math.Sqrt(x-j+1)-Math.Sqrt(x-j--))))){Console.Clear();Console.Write("X".PadLeft(x-j+1,'\n').PadRight(x+1,'\n')+"-");}}

```

Try it online!
> 1 votes

# Answer
## Haskell, 145 bytes

```
import Control.Concurrent
a!b=[a..b]>>"\n"
f h=mapM(\k->putStr("\27[2J"++1!k++'O':k!h++"-")>>threadDelay(round$4472135*(sqrt(k+1)-sqrt k)))[1..h]

```

Needs to be run in an ANSI terminal. The input is the number of intervals.

`threadDelay`'s parameter is in nanoseconds, so a literal `4472135` is shorter than `2*sqrt 5*10^6`. Unfortunately `46**4 = 4477456` is not within the limit of the required precision.
> 1 votes

---
Tags: code-golf, ascii-art, animation, physics
---


title: Tetris! Final heights (Day 3)

text:
# Question
Title: Tetris! Final heights (Day 3)
Challenge Taken from my university code challenge contest

This is actually Day 0 but yesterdays' challenge was too easy and can be a dupe of another question here.

---

Tetris is a video game that became popular in the 80s. It consists of placing a series of pieces with different shapes that fall on a board, so that they fit in the most compact way possible.

In this problem we will assume a sequence of pieces that fall, each in a certain position and with a certain orientation that can not be changed. The pieces are piled up as they fall and the complete rows are not eliminated (as in the original game). The objective is to determine the final height of each column of the board after all the pieces fall.

There are a total of 7 different pieces, shown in the figure:

**Challenge**

Given a list of pieces, output the height of all the columns from the board after all pieces falls

A piece consists of three numbers: I, R and P. The first number, I, is the identifier of the piece (a number between 1 and 7, in the same order as in the figure). The second number, R, is the rotation of the piece. It can take the values 0, 90, 180 or 270 and represents the angle of rotation of the piece in the anti-clockwise direction. The third number, P, indicates the position of the piece. Represents the column on the left occupied by the piece (this can be 1 or 0 Index. Please specify).

**Example and Test case (1 Index)**

* Given `[[1, 0, 1], [4, 0, 1], [5, 90, 4]]`

* Output `[3, 3, 1, 3, 2]`

---

* Given `[[6, 270, 4], [1, 180, 5], [1, 90, 6], [7, 0, 4]]`

* Output `[0, 0, 0, 9, 9, 8, 3, 3]`

---

* Given `[[3,0,1],[3,180,3]]` Output `[1,1,4,4,4]`
* Given `[[2,180,1],[2,0,3]]` Output `[2,2,4,3,3]`

**Notes**

* This is
* Row/Column can be 1 or 0 Index. Please specify.
* You can redefine input values (maybe you want to call piece 1 as A, etc..). In that case please specify

**Questions**

* Can we use any 4 distinct values instead of an angle in degrees?: *Yes*
* Are we supposed to handle "holes" if a piece doesn't exactly fit over the previous ones?: *Yes*
* Is the height or the width of the board bounded? *No. Neither the width nor the height are bounded*

---

Thanks @Arnauld for the images and the test cases \*.\*

# Answer
> 10 votes
# JavaScript (Node.js),  ~~286 284 270~~  266 bytes

Pieces and positions are 0-indexed. Angles are in \\$\[0..3\]\\$.

```
a=>a.map(([p,r,x])=>(g=y=>y>3?g(+!Y--):b[Y+y]&(m[y]=('0x'+`717433667233ff4717333327661${1e12+0x5e7056a566ffff57efa65n.toString(4)}`[(p*2+r*56+y*99+13)%113])<<x)?m.map(v=>(g=x=>v&&g(x+1,H[x]=v&1?Y:~~H[x],v>>=1))(0,b[++Y]|=v)):g(y+1))(Y=a.length*4),m=[b=[-1]],H=[])&&H

```

Try it online! or try an enhanced version that also displays the final board.

### Shape encoding

All pieces are stored as exactly 4 nibbles (4x4 bits) with the rows sorted in reverse order and the leftmost pixel mapped to the least significant bit. In other words, the binary representation of the shape is mirrored both vertically and horizontally.

Example:

### Hash function and lookup table

Given a piece \\$p \in \[0..6\]\\$, a rotation \\$r \in \[0..3\]\\$ and a row \\$y \in \[0..3\]\\$, we use the following hash function to get the index \\$n\\$ of the corresponding bitmask from a lookup table:

$$n=(2p+56r+99y+13)\bmod 113$$

Only the first \\$82\\$ entries are explicitly stored. Everything else is set to \\$0\\$.

These entries are packed as:

```
`717433667233ff4717333327661${1e12+0x5e7056a566ffff57efa65n.toString(4)}`

```

which expands to the following 82 nibbles:

```
"717433667233ff47173333276611000000000000113213001112221112123333333311133233221211"

```

Using hexadecimal in the final format is only required for the two horizontal representations of the \\$I\\$ piece, hence the `"ff"` in the above string.

The parameters of the hash function were brute-forced in a way that optimizes leading and trailing zeros. The fact that the string can be compressed some more by using `1e12` for the zeros in the middle and a conversion from base-16 to base-4 for the right part is just a welcome but unexpected side effect. :-)

**Here is a demonstration** of the unpacking process for all pieces and all rotations.

### Commented

```
a => a.map(([p, r, x]) => (     // for each piece p with rotation r and position x:
  g = y =>                      //   g = recursive function taking y
    y > 3 ?                     //   if y is greater than 3:
      g(+!Y--)                  //     reset y to 0, decrement Y and try again
    :                           //   else:
      b[Y + y] & (              //     test if we have a collision of the board with
        m[y] =                  //     the y-th row m[y] of the current piece
          ('0x' + `717...`[     //     which is extracted from a lookup table
            (p * 2 + r * 56 +   //     using the hash function described in the
             y * 99 + 13) % 113 //     previous paragraph
          ]) << x               //     and shifted to the left according to x
      ) ?                       //     if we have a collision:
        m.map(v => (            //       we iterate again on the piece rows stored in m[]
          g = x =>              //         g = recursive function taking x
            v &&                //         if v is not equal to 0:
            g(                  //           do a recursive call:
              x + 1,            //             increment x
              H[x] =            //             update the height at x:
                v & 1 ?         //               if this bit is set:
                  Y             //                 set it to Y
                :               //               else:
                  ~~H[x],       //                 leave it unchanged or force it to 0
                                //                 if it was still undefined
              v >>= 1           //             shift v to the right
            )                   //           end of recursive call
          )(0,                  //         initial call to g with x = 0
               b[++Y] |= v)     //         increment Y and copy the piece row to the board
        )                       //     end of map()
      :                         //   else (no collision):
        g(y + 1)                //     do a recursive call to test the next row
  )(Y = a.length * 4),          //   initial call to g with y = Y = 4 * the number of pieces
                                //   (assuming the worst case: piled vertical I pieces)
  m = [b = [-1]], H = []        //   initialize m[], b[] and H[]
                                //   we set a full line at the bottom of b[]
) && H                          // end of map(); return H[]

```

# Answer
> 7 votes
# C (clang), ~~253~~ ~~239~~ ~~221~~ 212 bytes

```
t(*a,*b,c){char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVWhUEQVRTYTUU";for(size_t*p,f,n,y,i;c--;b++){f=1<<(8-*b)/3;p=z+*b++*8+*b++%f*2;f=n=*p;for(y=i=0;i<=f%4;y=fmax(y,a[*b+i++]+n%4))n/=4;for(;i--;a[*b+i]=y+n%4)n/=4;}}

```

Try it online!

p.s. Actually the code size is 221 bytes (but 212 chars) because of UNICODE chars coded in UTF-8. But **tio.run** treats it as 212 byte code...

Code size on my computer is 209 chars (218 bytes). But I couldn't replace `\225` by visible char in **tio.run**

## Ungolfed code

```
// a - output array (must be zeroed), b - array of block info, c - number of blocks

// Figure codes: 2->0, 3->1, 6->2, 1->3, 5->4, 7->5, 4->6 (0,1 are L-figures, 2 is is T-figure, 3 is a line 1x4; 4,5 are zigzags; 6 is a cube 2x2)
// Vertical and horizontal positions are zero-indexed, angles = 0..3

t(*a,*b,c)
{
  char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVWhUEQVRTYTUU";  // UTF-8
//char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVW\1hU\26EQVRTYTUU";  // 3 bytes longer (use it if you can't copy previous string correctly) :)
  // Blocks
  for(size_t*p,f,n,y,i;c--;b++){
    f=1<<(8-*b)/3;  // number of figure variants
    p=z+*b++*8+*b++%f*2;
    // Get top base line position (y)
    f=n=*p;  // figure width, TBLs and HATs
    for(y=i=0;i<=f%4;
      y=fmax(y,a[*b+i++]+n%4))
      n/=4;
    // Add heights (HATs)
    for(;i--;
      a[*b+i]=y+n%4)
      n/=4;
  }
}  // 215 chars (224 bytes)
```

## Description

Let's found top base line (**TBL**) of each figure and describe it as a number of cells below TBL for each horizontal position. Also let's describe number of cells (height) above TBL (**HAT**).

E.g.:

```
                       ________                                      ________
_[]_____ HAT = 1,0,0    [][][]  HAT = 0,0,0   ___[][]_ HAT = 0,1,1    [][][]  HAT = 0,0,0
 [][][]  TBL = 1,1,1    []      TBL = 2,1,1    [][]    TBL = 1,1,0      []    TBL = 1,2,1
```

Let's describe TBLs and HATs for each figure and each rotation angle:

```
Width  TBLs     HATs
-----  -------  -------
L-figures:
  3    1 1 1    1 0 0    // 0°
  2    1 1      0 2      // 90°
  3    1 1 2    0 0 0    // 180°
  2    3 1      0 0      // 270°

  3    1 1 1    0 0 1    // 0°
  2    1 3      0 0      // 90°
  3    2 1 1    0 0 0    // 180°
  2    1 1      2 0      // 270°

T-figure:
  3    1 1 1    0 1 0    // 0°
  2    1 2      0 1      // 90°
  3    1 2 1    0 0 0    // 180°
  2    2 1      1 0      // 270°

Line:
  4    1 1 1 1  0 0 0 0  // 0°, 180°
  1    4        0        // 90°, 270°

Zigzags:
  3    1 1 0    0 1 1    // 0°, 180°
  2    1 2      1 0      // 90°, 270°

  3    0 1 1    1 1 0    // 0°, 180°
  2    2 1      0 1      // 90°, 270°

Cube:
  2    2 2      0 0      // any angle
```

Now we should encode these numbers as a sequences of 2 bits and put into an array (replacing `4 0` by `3 1` for 90° angle of "line" to fit in 2 bits – result will be the same; and decrease widths by 1).

We'll encode in order: **width** (in 2 LSB), **TBLs**, **HATs** (backward for backward loop). E.g. `2 2 1 1 0` for 270° angle of T-figure will be encoded as `1 0 1 2 1` (last *1* is *width-1*): `0b0100011001 = 281`.

**updated 12.02:**

a) I've converted an array to a string and saved 18 chars (you can see previous 239 bytes code) :))

b) More optimization, code is shrinked by 9 chars.
*This is my last attempt (I think so, lol!)*

# Answer
> 5 votes
# C# (Visual C# Interactive Compiler), 308 bytes

```
a=>{var o=new int[a.Max(x=>x.Item3+4)];foreach(var(i,r,p)in a){var b="\"4TqzŒª!\0\0HSš	Ó\0$\n\0!“A“š š@";int m=0,n=b[i],t=0,u=n/8+r%(n%8),v=b[u*=2]<<8|b[u-1];for(;t<v/8%8;m=m>n?m:n)n=o[p+t]+v%8-(n=(u=v>>6+3*t++)/2&1)-(n&u);for(;t-->0;)o[p+t]=m-(n=(u=v>>6+3*t)/4&1)-(n&u);}return o;}

```

Try it online!

OK - That was madness... I submitted an answer that used run-of-the-mill code-golf techniques. But when I saw what others were submitting, I realized there was a better way.

Each `(shape, rotation)` tuple is encoded into a C# string literal with duplicates removed. The encoding process captures each of these configurations in 2 bytes.

The lowest 3 bits store height and the next 3 store width. Since each of these values is never more than 4, they can be read directly from the 3 bits without any conversion. Here are some examples:

```
  W   H
010 010 (2x2)
010 011 (2x3)
001 100 (1x4)
011 010 (3x2)
100 001 (4x1)

```

Next, each column is stored in 3 bits. The most useful thing for me to store was the number of missing squares from the top and bottom of the column.

```
// missing squares per column

+------ 0 top / 0 bottom
|+----- 0 top / 1 bottom
||+---- 0 top / 1 bottom
|||
HHH (L-Shape)         HH (Jagged-Shape)
H                    HH
                     |||
1 top / 0 bottom ----+||
0 top / 0 bottom -----+|
0 top / 1 bottom ------+

```

There is never more than 2 squares missing from the top or bottom, and there is never more than 1 square missing from both at the same time. Given this set of constraints, I came up with the following encoding:

```
// column encoding of missing squares per column

000: none missing
100: 1 missing on top
101: 2 missing on top
010: 1 missing on bottom
011: 2 missing on bottom
110: 1 missing on top and bottom

```

Since we have to account for at most 3 columns with missing squares above or below, we can encode each `(shape, rotation)` tuple in 15 bits.

```
 C3  C2  C1   W   H
000 000 000 010 010 - 2x2 with no missing squares
000 000 000 100 001 - 4x1 with no missing squares
100 000 100 011 010 - 3x2 with missings square on top of columns 1 and 3
000 110 000 010 011 - 2x3 with missing squares on top and bottom of column 2

```

Lastly, duplicate shapes have been removed. The follow example show how multiple `(shape,rotation)` tuples can produce duplicate outputs for the same shape at different rotations:

```
// Square
HH  (0, 90, 180, 270)
HH
#-------------------------------#
// ZigZag
HH  (0, 180)    H  (90, 270)
 HH            HH
               H
#-------------------------------#
// T
 H  (0)        HHH  (180)
HHH             H

 H  (90)       H    (270)
HH             HH
 H             H

```

All unique outputs are determined and saved to a `byte[]` and converted to a C# string literal. In order to quickly lookup where a shape is based on `I` and `R`, the first 7 bytes of the array consist of an encoded lookup key.

Below is a link to the program that I used to compress the pieces.

Try it online!

Less golfed and commented code:

```
// a: input list of (i,r,p) tuples
a=>{
  // create an output array that 4 more than
  // the largest position. this may result
  // in some trailing 0's
  var o=new int[a.Max(x=>x.Item3+4)];

  // iterate over each (i,r,p) tuple
  foreach(var(i,r,p)in a){
    // escaped string
    var b="\"4Tqzª!\0\0HS   Ó\0$\n\0!A @";
    // declare several variables that will be used later
    int m=0,n=b[i],t=0,
      // u is the decoded index into b for the current (i,r) pair
      u=n/8+r%(n%8),
      // convert 2 bytes from b into an encoded (shape,rotation) pair
      v=b[u*=2]<<8|b[u-1];
    // iterate over the columns, determining the top of the current
    // piece. The formula here is:
    //   piece_top = max(column_height + shape_height - shape_space_bottom)
    for(;t<v/8%8;m=m>n?m:n)
      n=o[p+t]+v%8-(n=(u=v>>6+3*t++)/2&1)-(n&u);
    // iterate over the columns again, saving the the new height
    // in each column. The formula here is:
    //   new_column_height = piece_top - shape_space_top
    for(;t-->0;)
      o[p+t]=m-(n=(u=v>>6+3*t)/4&1)-(n&u);
  }
  return o;
}

```

# Answer
> 5 votes
# Common Lisp, 634 bytes

```
(let((w(make-hash-table))(r 0))(defun z(c)(or(gethash c w)0))(defun x(c v)(setf r(max r c))(setf(gethash c w)v))(defun m(s)(dolist(c s)(apply(lambda(n u p)(let*((i(let*((j'(2 2 2))(k'(3 3))(l'(2 3))(m'(3 2))(o(case n(1(list'(1 1 1 1)'(4)))(2(list j k'(1 1 2)'(3 1)))(3(list j'(1 3)'(2 1 1)k))(4(list'(2 2)))(5(list'(2 2 1)l))(6(list j l'(1 2 1)m))(7(list'(1 2 2)m)))))(setf(cdr(last o))o)))(o(nth(+ u 2)i))(b(nth u i))(s(length o))(d 0)(h 0))(dotimes(i s)(let*((w(nth i b))(g(z(+ i p)))(m(+ g w)))(when(> m d)(setf d m)(setf h(- g(-(apply'max b)w))))))(dotimes(i s)(x(-(+ s p)i 1)(+(nth i o)h)))))c))(dotimes(i r)(print(z (+ i 1))))))

```

## Verbose

```
(defun circular (list)
  (setf (cdr (last list)) list))

(defun get-piece (piece-number)
  (circular (case piece-number
              (1 (list '(1 1 1 1)
                       '(4)))
              (2 (list '(2 2 2)
                       '(3 3)
                       '(1 1 2)
                       '(3 1)))
              (3 (list '(2 2 2)
                       '(1 3)
                       '(2 1 1)
                       '(3 3)))
              (4 (list '(2 2)))
              (5 (list '(2 2 1)
                       '(2 3)))
              (6 (list '(2 2 2)
                       '(2 3)
                       '(1 2 1)
                       '(3 2)))
              (7 (list '(1 2 2)
                       '(3 2))))))

(let ((world (make-hash-table))
      (rightmost-column 0))
  (defun get-world-column (column)
    (or (gethash column world) 0))

  (defun set-world-column (column value)
    (setf rightmost-column (max rightmost-column column))
    (setf (gethash column world) value))

  (defun drop-piece (piece-number rotation position)
    (let* ((piece (get-piece piece-number))
           (top (nth (+ rotation 2) piece))
           (bottom (nth rotation piece))
           (size (length top))
           (max-combined-height 0)
           (contact-height 0))
      (dotimes (i size)
        (let* ((down-distance (nth i bottom))
               (height (get-world-column (+ i position)))
               (combined-height (+ height down-distance)))
          (when (> combined-height max-combined-height)
            (setf max-combined-height combined-height)
            (setf contact-height
                  (- height
                     (- (apply #'max bottom)
                        down-distance))))))
      (dotimes (i size)
        (set-world-column (- (+ size position) i 1)
                          (+ (nth i top) contact-height)))))

  (defun drop-pieces (pieces)
    (dolist (piece pieces)
      (apply #'drop-piece piece)))

  (defun print-world ()
    (loop for i from 1 to rightmost-column
          do (print (get-world-column i)))))

(defun play-tetris (pieces)
  (drop-pieces pieces)
  (print-world))

```

Test it

The pieces are circular-lists of lists of numbers. These sub-lists each represent a side of the shape, the numbers indicating how far they are from the opposite side. They are left to right when that side is on the bottom, right to left when on top, top to bottom when on left, and bottom to top when on right. These design choices eliminate the need to write code for rotation. Unfortunately, the lack of rotation code does not seem to have made up for the lengthy shape representations, or the somewhat complicated logic I used for calculating new column heights.

Rotation is a non-negative integer. 0=0 degrees, 1=90 degrees, 2=180 degrees, 4=270 degrees

# Answer
> 4 votes
# Charcoal, 98 bytes

```
Ｆθ«≔§⪪§⪪”)¶∧↷"e«↨U∧0%3；D∧⁼~h⊟⁵h/₂dΦ↗(EＦ”2⊟ι1⊟ιη≔⊟ιζＷ‹Ｌυ⁺ζＬη⊞υ⁰≔⌈Ｅη⁻§υ⁺ζλ﹪Ｉκ³εＦＬη§≔υ⁺ζκ⁺ε⊕÷Ｉ§ηκ³»Ｉυ

```

Try it online! Link is to verbose version of code. Takes input as an array of \[P, R, I\] values, where I is from 0 to 6, R is from 0 o 3 and P is also 0-indexed. Explanation:

```
Ｆθ«

```

Loop over the input pieces.

```
≔§⪪§⪪”)¶∧↷"e«↨U∧0%3；D∧⁼~h⊟⁵h/₂dΦ↗(EＦ”2⊟ι1⊟ιη

```

Extract the description of the current piece and rotation. (See below.)

```
≔⊟ιζ

```

Extract the position.

```
Ｗ‹Ｌυ⁺ζＬη⊞υ⁰

```

Ensure that there is enough horizontal room to place the piece.

```
≔⌈Ｅη⁻§υ⁺ζλ﹪Ｉκ³ε

```

Ensure that there is enough vertical room to place the piece.

```
ＦＬη§≔υ⁺ζκ⁺ε⊕÷Ｉ§ηκ³

```

Calculate the new heights of the affected columns.

```
»Ｉυ

```

When all the pieces have been processed, output the final list of column heights on separate lines.

The compressed string represents the original string `00001923001061443168200318613441602332034173203014614341642430137`. Here the `2`s are `I` separators and the `1`s are `R` separators. The pieces therefore decode as follows:

```
P\R  0    1    2    3
0    0000 9
1    300  06   443  68
2    003  86   344  60
4    33
5    034  73
6    030  46   434  64
7    430  37

```

Missing `R` values are automatically filled cyclically by Charcoal. Each digit then maps to two values, overhang and total height, according to the following table:

```
\ O H
0 0 1
3 0 2
4 1 2
6 0 3
7 1 3
8 2 3
9 0 4

```

The overhang and total height relate to the column heights as follows: Given a piece that we want to place at a given position `e`, it may be possible to place the piece even though one of the columns is taller than `e`. The amount of spare space is given by the overhang. The new height of the column after placing the piece is simply the placed position plus the total height.

Example: Suppose we start by placing a `5` piece in column 1. Since there is nothing else yet the piece is therefore placed at position 0 and columns 1 and 3 now have height 1 while column 2 has height 2. We then want to place a `6` piece with `1` rotation in column 0. Here we can actually place this piece at position 0; although column 1 has a height of 1, the piece has an overhang of 1, and so there is enough space to place it. Column 0 ends up with a height of 2 and column 1 ends up with a height of 3.

---
Tags: code-golf, tetris
---


# Question
Title: Write a function/method that takes in a string and spells that word out using the NATO Phonetic Alphabet. Titlecase optional
Write a program that takes in a string and spells that word out using the NATO Phonetic Alphabet.

The mapping is as follows:

```
'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'

```

Example:

`'Hello World' -> ['Hotel', 'Echo', 'Lima', 'Lima', 'Oscar', 'Whiskey', 'Oscar', 'Romeo', 'Lima', 'Delta']`

The input can be any string, but will always be comprised of only letters and spaces. Case is irrelevant in the output, but the input may contain letters in uppercase, lowercase, or both. Spaces should be ignored in the output.

You can output in any reasonable format, but it must be a delimited set of NATO callsigns.

# Answer
# sfk, ~~78~~ ~~59~~ 57 bytes

```
+filt
+spell -nato
+xed _ph_f_ _et_ett_ _-__ "*: [keep]""

```

Try it online!

Just use the right tool.

Output is the phonetics separated by one or more spaces.
> 13 votes

# Answer
# x86-16 machine code, IBM PC DOS, 192 bytes

```
be80 00ad 8ac8 ac51 24df 8ad0 2c40 3c1b 7321 8af0 b024 b18b 9090 bf37 01f2 aefe
ce75 fab4 02cd 218b d7b4 09cd 21b2 20b4 02cd 2159 e2d0 c324 6c66 6124 7261 766f
2468 6172 6c69 6524 656c 7461 2463 686f 246f 7874 726f 7424 6f6c 6624 6f74 656c
246e 6469 6124 756c 6965 7474 2469 6c6f 2469 6d61 2469 6b65 246f 7665 6d62 6572
2473 6361 7224 6170 6124 7565 6265 6324 6f6d 656f 2469 6572 7261 2461 6e67 6f24
6e69 666f 726d 2469 6374 6f72 2468 6973 6b65 7924 7261 7924 616e 6b65 6524 756c
7524

    MOV  SI, 80H            ; point SI to DOS PSP
    LODSW                   ; load arg length into AL, advance SI to 82H
    MOV  CL, AL             ; set up loop counter
SEARCH:
    LODSB                   ; load next char from DS:SI into AL, advance SI
    PUSH CX                 ; save outer loop position
    AND  AL, 0DFH           ; uppercase the input letter
    MOV  DL, AL             ; save for output
    SUB  AL, 'A'-1          ; convert letter to one-based index (A=1, Z=26, etc)
    CMP  AL, 27             ; if greater than 26, not a valid char
    JNC  NOTFOUND           ; if not, move to next
    MOV  DH, AL             ; DH is loop counter
    MOV  AL, '$'            ; search for string delimiter
    MOV  CL, LNATO          ; repeat search through length of word data
    MOV  DI, OFFSET NATO    ; re-point SCASB to beginning of word data
SCANLOOP:
    REPNZ SCASB             ; search until delimiter in AL is found ES:DI, advance DI
    DEC  DH                 ; delimiter found, decrement counter
    JNZ  SCANLOOP           ; if counter reached 0, index has been found
    MOV  AH, 02H            ; display first char
    INT  21H
    MOV  DX, DI             ; put found string memory location to DX for display
    MOV  AH, 09H            ; display string function
    INT  21H
    MOV  DL, ' '            ; display a space between words
    MOV  AH, 02H
    INT  21H
NOTFOUND:
    POP  CX                 ; restore outer loop counter
    LOOP SEARCH             ; move to next char in input
    RET
NATO    DB  '$lfa$ravo$harlie$elta$cho$oxtrot$olf$otel$ndia$'
        DB  'uliett$ilo$ima$ike$ovember$scar$apa$uebec$omeo$'
        DB  'ierra$ango$niform$ictor$hiskey$ray$ankee$ulu$'
LNATO   EQU $-NATO

```

Test output:

```
A>NATO abc aaa
Alfa Bravo Charlie Alfa Alfa Alfa
A>NATO abc DefG1HIJ
Alfa Bravo Charlie Delta Echo Foxtrot Golf Hotel India Juliett
A>NATO Alfa Bravo!
Alfa Lima Foxtrot Alfa Bravo Romeo Alfa Victor Oscar

```
> 6 votes

# Answer
# 05AB1E, ~~102~~ ~~96~~ 95 bytes

```
álSA”AlfaÐ†vo¼¯¤œ®È¨›trotŠˆƒ‹Š™ÈŸtt Kilo´àma—……ÍÐ—Žêpa¼°«Äoµ†Çâgo¸šÉµ Whiskey Xrayµ‹nkeeâ¸lu”#‡

```

Output is a list of Titlecased NATO words.

Try it online.

**Explanation:**

```
á              # Only leave the letters of the (implicit) input
 l             # Convert it to lowercase
  S            # Split it to a list of characters
   A           # Push the alphabet
    ”...”      # Push all the NATO words in titlecase and space-delimited
         #     # Split the string by spaces
          ‡    # Transliterate; map all letters in the lowercase input with this
               # list at the same indices (and output the resulting list implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `”AlfaÐ†vo¼¯¤œ®È¨›trotŠˆƒ‹Š™ÈŸtt Kilo´àma—……ÍÐ—Žêpa¼°«Äoµ†Çâgo¸šÉµ Whiskey Xrayµ‹nkeeâ¸lu”` is `"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"`. Credit of this compressed dictionary string goes to *@ErikTheGolfer* in this comment (with an added `t` for `Juliett` instead of `Juliet`).
> 5 votes

# Answer
# Jelly,  ~~80~~  77 bytes

```
ḟ⁶O%32ị“¡µQỤ(cɠṘwlṁ;Ɗœ<NẸ½ṗN¬ṙẋxḶb¤*O~Æƒ¹.ß8Ḋ¡tJ|Ḷ<İİḂ^1eȷjċbY9TYƭ¹Ẉ¥¤K0¹f»Ḳ¤

```

**Try it online!** (The footer formats the list by joining with spaces to avoid implicit smashing print when run as a full program)
> 4 votes

# Answer
# JavaScript (ES6), ~~181~~ 189 bytes

```
s=>s.match(/\w/g).map(c=>'IndiAlfABravOscaRomeOQuebeCharliEchODeltAGolFoxtroTangOHoteLimAJulietTKilOZulUniforMikENovembeRPapASierrAVictoRWhiskeYankeEXraY'.match(c.toUpperCase()+'.*?[A-Z]'))

```

Since output case doesn't matter, we can save bytes by running words together:

```
... GolFoxtroTangO ...

```

Try it online!
> 4 votes

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

```
n=>n.ToUpper().Select(x=>"AlfaBravoCharlieDeltaEchoFoxtrotGolfHotelIndiaJuliettKiloLimaMikeNovemberOscarPapaQuebecRomeoSierraTangoUniformVictorWhiskeyXrayYankeeZulu".SkipWhile(k=>x!=k).TakeWhile((k,l)=>l<1|k>96&k<123))

```

Try it online!

# Alternate version using Split(), 194 bytes

```
n=>n.ToUpper().Select(x=>x>64?x+"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(',')[x%65]:x+"")

```

Try it online!
> 2 votes

# Answer
# Perl 6, ~~176 170~~ 166 bytes

```
*.comb>>.&{$_~:128[q`>$RbD[Orlo~Q1nX,OVq8x9'6%h'1.I$83ua7	vsD=s-{W}{>iQ:Js37py)hNN,i{Pt\~#f4<>`.ords].base(35).split('J')[.ord%32]}.words

```

Try it online!

Outputs in uppercases with the first letter in the original case. Compresses the string, which only saves 6 bytes over the simpler plain text:

```
*.comb>>.&{$_~ <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>[.ord%32-1]if ' 'ne$_}

```

Try it online!

### Explanation:

```
*.comb>>.&{                 }         # Map each letter to
           $_~                        # The letter plus
              <...>[.ord%32]          # The letter indexed into the list of words
                             .words   # And remove the extra spaces

```
> 2 votes

# Answer
# Python 3, ~~250~~ 191 bytes

-47 bytes thanks to @Jo King, -2 more thanks to @Jonathan Allen

It goes through all non-space characters of the input, and for each of them it selects the relevant phrase for the letter, which can be reduced a bit because the first letter of each phrase is the character itself. Splits a string instead of storing the phrases as an array to save bytes from the unnecessary `'`s and `,`s.

```
lambda s:[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)%32-1]for c in s if' '<c]

```

Try it online!

Original solution

```
lambda s:[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'][ord(c)-65]for c in s.replace(" ", "").upper()]

```

Try it online!
> 2 votes

# Answer
# Red, ~~210~~ 193 bytes

```
func[s][foreach c trim/all s[prin c print pick[: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]c% 32]]

```

Try it online!

## Explanation:

`foreach` iterates over the string after all whitespaces are removed by `trim/all`. `prin` prints the character (no newline). `print` prints a symbol, `pick`ed from the list of get-word!s (symbols) using the character mapped to the range 1..26 as an index.
> 2 votes

# Answer
# Charcoal, 99 bytes

```
ＥΦ↥Ｓ№αι⁺ι§⪪”&⌊%w⁸D⦃σν:…ⅈ$|@Ｈ¦χＴ⸿]ECrΣＭ^¿←←&⁵↘⁼s(ＪＦ8X´▷⧴⎚Ｐ0V÷AＷχπ¶⌈≧\"dＪ^ZU{M≔⁴｜<¶⁹Ｂ⊞⊟1ＬPH⪪∨Y3`”j⌕αι

```

Try it online! Link is to verbose version of code. Outputs in proper case. Explanation:

```
   Ｓ                    Input string
  ↥                     Uppercased
 Φ                      Filtered where
     α                  Predefined uppercase alphabet
    №                   Contains
      ι                 Current character
Ｅ                       Mapped over characters
        ι               Current character
       ⁺                Concatenated with
           ”...”        Compressed string
          ⪪             Split on
                j       Literal string `j`
         §              Indexed by
                 ⌕      Index of
                   ι    Current character
                  α     In uppercase alphabet
                        Implicitly print each word on its own line

```
> 2 votes

# Answer
# Clean, 218 bytes

```
import StdEnv
$s=[takeWhile((<=)c)(dropWhile((<)c)['ZuluYankeeXrayWhiskeyVictorUniformTangoSierraRomeoQuebecPapaOscarNovemberMikeLimaKiloJuliettIndiaHotelGolfFoxtrotEchoDeltaCharlieBravoAlfa'])\\c<-map toUpper s|c>' ']

```

Try it online!
> 2 votes

# Answer
# C++, ~~229~~ 228 bytes

```
[](auto s){for(;auto t=*s?"LfaRavoHarlieEltaChoOxtrotOlfOtelNdiaUliettIloImaIkeOvemberScarApaUebecOmeoIerraAngoNiformIctorHiskeyRayAnkeeUlu":0;s++)if(int c=*s&31){for(cout<<*s;*t>96||--c;t++);for(;cout<<*t,*++t>96;);cout<<' ';}}

```

Try it online!

Ungolfed:

```
[](const char *s)
{
    const char *table = "LfaRavoHarlieEltaChoOxtrotOlfOtelNdiaUliettIloImaIkeOvemberScarApaUebecOmeoIerraAngoNiformIctorHiskeyRayAnkeeUlu";
    for (; *s; s++)
    {
        char c = *s & 0x1F;
        if (c != 0)
        {
            cout << *s;
            const char *w = table;
            while (*w >= 'a' || --c)
                w++;
            do
                cout << *w;
            while (*++w >= 'a');
            cout << ' ';
        }
    }
}

```

Output:

```
TAngo hOtel eCho qUebec uNiform iNdia cHarlie kIlo bRavo rOmeo oScar wHiskey nOvember fOxtrot oScar xRay jUliett uNiform mIke pApa eCho dElta oScar vIctor eCho rOmeo tAngo hOtel eCho lIma aLfa zUlu yAnkee dElta oScar gOlf
JUliett aLfa cHarlie kIlo dElta aLfa wHiskey sIerra lIma oScar vIctor eCho mIke yAnkee bRavo iNdia gOlf sIerra pApa hOtel iNdia nOvember xRay oScar fOxtrot qUebec uNiform aLfa rOmeo tAngo zUlu

```

Clean-capitalization version (**234 bytes**):

```
[](auto s){for(;auto t=*s?"LfaRavoHarlieEltaChoOxtrotOlfOtelNdiaUliettIloImaIkeOvemberScarApaUebecOmeoIerraAngoNiformIctorHiskeyRayAnkeeUlu":0;s++)if(int c=*s&31){for(cout<<*s;*t>96||--c;t++);for(;putchar(*t|32),*++t>96;);cout<<' ';}}

```

Try it online!

Output:

```
Tango hotel echo quebec uniform india charlie kilo bravo romeo oscar whiskey november foxtrot oscar xray juliett uniform mike papa echo delta oscar victor echo romeo tango hotel echo lima alfa zulu yankee delta oscar golf
Juliett alfa charlie kilo delta alfa whiskey sierra lima oscar victor echo mike yankee bravo india golf sierra papa hotel india november xray oscar foxtrot quebec uniform alfa romeo tango zulu

```
> 2 votes

# Answer
# IBM PC DOS 8088 machine language, 165 bytes

This is directly based on gwaugh's answer, but I shaved off 26 bytes by omitting the `$` delimiters from the "NATO" word table and an extra 1 byte by not skipping the first character of the command-line parameter string (which will always be either `/` or  and thus will be ignored by the program anyway). The program ended up being exactly the same length to be able to process the table in this format (in which the words are delimited only by uppercase characters, which serve the double purpose of also being the second letter of each word), or 2 bytes longer if the output capitalization is kept the same as before. The table is 26 bytes smaller.

In the following program dump, concatenation by `:` is used to show each sequence of consecutive bytes corresponding to an instruction:

```
0000  BE:80:00 AC 91 AC 24:DF 8A:D0 2C:40 3C:1A 77:21  ······$···,@<·w!
0010  8A:F0 B4:02 CD:21 56 BE:34:01 AC A8:20 75:FB FE: ·····!V·4··· u··
0020 :CE 75:F7 8A:D0 CD:21 AC A8:20 75:F7 B2:20 CD:21  ·u····!·· u·· ·!
0030  5E E2:D2 C3 4C 66 61 52 61 76 6F 48 61 72 6C 69  ^···LfaRavoHarli
0040  65 45 6C 74 61 43 68 6F 4F 78 74 72 6F 74 4F 6C  eEltaChoOxtrotOl
0050  66 4F 74 65 6C 4E 64 69 61 55 6C 69 65 74 74 49  fOtelNdiaUliettI
0060  6C 6F 49 6D 61 49 6B 65 4F 76 65 6D 62 65 72 53  loImaIkeOvemberS
0070  63 61 72 41 70 61 55 65 62 65 63 4F 6D 65 6F 49  carApaUebecOmeoI
0080  65 72 72 61 41 6E 67 6F 4E 69 66 6F 72 6D 49 63  erraAngoNiformIc
0090  74 6F 72 48 69 73 6B 65 79 52 61 79 41 6E 6B 65  torHiskeyRayAnke
00A0  65 55 6C 75 40                                   eUlu@

```

Download the DOS NATO.COM executable:
With uncorrected capitalization (165 bytes)
With clean capitalization (167 bytes)
Bonus version that capitalizes the first letter of each word the same as the input (167 bytes)

Unassembled:

```
    .MODEL TINY            ; .COM program, maximum addressing space 65536 bytes
    .CODE
    ORG 100h
start:
    MOV  SI, 80h           ; Point SI to DOS PSP (Program Segment Prefix).
    LODSB                  ; Load command-line parameter (input string) length
                           ; into AL; assume AX=0 before this, which is true
                           ; in most versions of DOS; advance SI to first char
                           ; of parameter, which is either '/' or ' '.
    XCHG CX, AX            ; Set up loop counter with length of input string.
search:
    LODSB                  ; Load next character from [SI] into AL; advance SI.
    AND  AL, NOT ('A' XOR 'a')  ; Make this character uppercase.
    MOV  DL, AL            ; Save character for output. Move this before the
                           ; AND instruction to capitalize the first letter of
                           ; each word identically to how it is in the input.
    SUB  AL, 'A'-1         ; convert letter to one-based index (A=1, Z=26, etc)
    CMP  AL, 'Z'-'A'+1     ; Is this an alphabetical character?
    JA   notFound          ; If not, move to next character.
    MOV  DH, AL            ; Set up DH as our word-finding loop counter.
    MOV  AH, 02h           ; AH=02h, INT 21h: Write character to STDOUT
    INT  21h               ; Display first character of this NATO word.
    PUSH SI                ; Save our current position in the input string.
    MOV  SI, OFFSET table  ; Point LODSB to beginning of word data.
scanLoop:                  ; Find the word in the table corresponding to our
                           ; current character.
    LODSB                  ; Load next character from [SI] into AL; advance SI.
    TEST AL, 'A' XOR 'a'   ; Is this character uppercase?
    JNZ  scanLoop          ; If not, move to next character.
    DEC  DH                ; Delimiter (uppercase) found; decrement counter.
    JNZ  scanLoop          ; Keep looping until counter reaches 0.
    OR   AL, 'A' XOR 'a'   ; Make this character lowercase. This is not
                           ; required by the challenge's specification, and
                           ; this instruction can be removed.
wordLoop:
    MOV  DL, AL            ; Display next character from NATO word.
    INT  21h               ; (We still have AH=02h from before.)
    LODSB
    TEST AL, 'A' XOR 'a'   ; Is this character lowercase?
    JNZ  wordLoop          ; If so, continue the loop.
    MOV  DL, ' '           ; Display a space between words.
    INT  21h               ; (We still have AH=02h from before.)
    POP  SI                ; Restore our current position in the input string.
notFound:
    LOOP search            ; Move to next character in input string.
    RET
table   DB  'LfaRavoHarlieEltaChoOxtrotOlfOtelNdia'
        DB  'UliettIloImaIkeOvemberScarApaUebecOmeo'
        DB  'IerraAngoNiformIctorHiskeyRayAnkeeUlu'
        DB  '@'            ; Terminate the list to make sure that uninitialized
                           ; memory doesn't cause a problem.
    END start

```

Sample input:

```
>NATO The quick brown fox jumped over the lazy dog.
>NATO Jackdaws love my big sphinx of quartz.

```

Output (165 byte version):

```
TAngo hOtel eCho qUebec uNiform iNdia cHarlie kIlo bRavo rOmeo oScar wHiskey nOvember fOxtrot oScar xRay jUliett uNiform mIke pApa eCho dElta oScar vIctor eCho rOmeo tAngo hOtel eCho lIma aLfa zUlu yAnkee dElta oScar gOlf
JUliett aLfa cHarlie kIlo dElta aLfa wHiskey sIerra lIma oScar vIctor eCho mIke yAnkee bRavo iNdia gOlf sIerra pApa hOtel iNdia nOvember xRay oScar fOxtrot qUebec uNiform aLfa rOmeo tAngo zUlu

```

Clean-capitalization version (167 bytes):

```
Tango Hotel Echo Quebec Uniform India Charlie Kilo Bravo Romeo Oscar Whiskey November Foxtrot Oscar Xray Juliett Uniform Mike Papa Echo Delta Oscar Victor Echo Romeo Tango Hotel Echo Lima Alfa Zulu Yankee Delta Oscar Golf
Juliett Alfa Charlie Kilo Delta Alfa Whiskey Sierra Lima Oscar Victor Echo Mike Yankee Bravo India Golf Sierra Papa Hotel India November Xray Oscar Foxtrot Quebec Uniform Alfa Romeo Tango Zulu

```

Clean-capitalization version with same capitalization as input (167 bytes):

```
Tango hotel echo quebec uniform india charlie kilo bravo romeo oscar whiskey november foxtrot oscar xray juliett uniform mike papa echo delta oscar victor echo romeo tango hotel echo lima alfa zulu yankee delta oscar golf
Juliett alfa charlie kilo delta alfa whiskey sierra lima oscar victor echo mike yankee bravo india golf sierra papa hotel india november xray oscar foxtrot quebec uniform alfa romeo tango zulu

```
> 2 votes

# Answer
# Japt, ~~108~~ 106 bytes

```
¸®¬Ë+u cg`ovem¼rws¯r°pawue¼cÙ o±ØÇ¯fmØtØkeyÙ°nkeewªuwlfaæ1ÃÉr¦e³ltawÖoxÉwolfÙ*lÙAawªieâ-¹µ±ke`qw

```

Try it

The backticks contains the compressed string:

```
ovemberwscarwapawuebecwomeowierrawangowniformwictorwhiskeywraywankeewuluwlfawravowharlieweltawchowoxtrotwolfwotelwndiawuliettwilowimawike

```
> 1 votes

# Answer
# PowerShell, ~~187~~ 183 bytes

```
$args|% t*y|%{'AlfaBravoCharlieDeltaEchoFoxtrotGolfHotelIndiaJuliettKiloLimaMikeNovemberOscarPapaQuebecRomeoSierraTangoUniformVictorWhiskeyXrayYankeeZulu'-csplit'(?=[A-Z])'-like"$_*"}

```

Try it online!

Test script:

```
$f = {
$args|% t*y|%{'AlfaBravoCharlieDeltaEchoFoxtrotGolfHotelIndiaJuliettKiloLimaMikeNovemberOscarPapaQuebecRomeoSierraTangoUniformVictorWhiskeyXrayYankeeZulu'-csplit'(?=[A-Z])'-like"$_*"}
}

@(
    ,('Hello World', 'Hotel', 'Echo', 'Lima', 'Lima', 'Oscar', 'Whiskey', 'Oscar', 'Romeo', 'Lima', 'Delta')
) | % {
    $s,$expected = $_
    $result = &$f $s
    "$result"-eq"$expected"
    "$result"
}

```

Output:

```
True
Hotel Echo Lima Lima Oscar Whiskey Oscar Romeo Lima Delta

```
> 1 votes

# Answer
# PHP, ~~209~~ ~~205~~ 206 bytes

```
while($l=$argv[1][$x++])echo$l!=' '?$l.preg_split('/([A-Z][a-z]*)/',ALfaRavoHarlieEltaChoOxtrotOlfOtelNdiaUliettIloImaIkeOvemberScarApaUebecOmeoIerraAngoNiformIctorHiskeyRayAnkeeUlu,0,3)[31&ord($l)].' ':'';

```

Try it online!

Output:

```
"Hello World" => "HOtel eCho lIma lIma oScar WHiskey oScar rOmeo lIma dElta"

```

Or **195** bytes, with spaces not fully removed:

```
while($l=$argv[1][$x++])echo$l,preg_split('/([A-Z][a-z]*)/',ALfaRavoHarlieEltaChoOxtrotOlfOtelNdiaUliettIloImaIkeOvemberScarApaUebecOmeoIerraAngoNiformIctorHiskeyRayAnkeeUlu,0,3)[31&ord($l)].' ';

```

Try it online!

Output:

```
"Hello World" => "HOtel eCho lIma lIma oScar   WHiskey oScar rOmeo lIma dElta"

```
> 1 votes

# Answer
# JavaScript, 179 bytes

```
s=>s.match(/\w/g).map(c=>c+'LfaRavoHarlieEltaChoOxtrotOlfOtelNdiaUliettIloImaIkeOvemberScarApaUebecOmeoIerraAngoNiformIctorHiskeyRayAnkeeUlu'.match(/.[a-z]+/g)[parseInt(c,36)-10])

```

Try it online!
> 1 votes

# Answer
# TSQL, 313 bytes

Golfed:

```
DECLARE @ varchar(max)='Hello World'

DECLARE @x INT=len(@)WHILE @x>0SELECT @=stuff(@,@x,1,substring(@,@x,1)+choose(ascii(substring(@,@x,1))%32,'lfa','eta','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-=1PRINT @

```

Ungolfed:

```
DECLARE @ varchar(max)='Hello World'

DECLARE @x INT=len(@)
WHILE @x>0
  SELECT @=stuff(@,@x,1,substring(@,@x,1)+choose(ascii(substring(@,@x,1))%32,
    'lfa','eta','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-=1

PRINT @

```

**Try it out**

Output ends with semicolon
> 0 votes

# Answer
# PowerShell, 228 225 bytes

-3 bytes thanks to @mazzy

```
"$args".ToLower()-replace' '|% T*y|%{$a+=$_+((-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")[('a'..'z').IndexOf($_)])+' '};$a

```

Try it online!

This is quite possibly the ugliest piece of code I have ever written. In addition, this can certainly get a lot shorter. In my defense, I'm still recovering from final exams.
> 0 votes

# Answer
# PHP, 212 bytes

```
while($c=ord($argn[$i++]))echo[_,Alpha,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][$c&31]," ";

```

Run as pipe with `-nR` or try it online.

Yields warnings in PHP 7.2; put array elements in quotes to fix.

Will print an underscore for spaces.
> 0 votes

# Answer
# C (clang), ~~309~~ 283 bytes

*-26 bytes thanks to @ceilingcat*

```
*k[]={"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"};i;main(z,v)char**v;{for(;z=toupper(v[1][i]);i++)z>64&z<92&&printf("%c%s ",z,k[z-65]);}

```

Try it online!
> 0 votes

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