42
\$\begingroup\$

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
\$\endgroup\$
15
  • 1
    \$\begingroup\$ can we accept input in lowercase? \$\endgroup\$
    – Razetime
    Nov 20, 2020 at 10:46
  • 7
    \$\begingroup\$ @SunnyMoon No, those are the official spellings, to make it easier for people that are not familiar with the English/French pronunciation of ph and to force Frenchmen into pronouncing the final t. \$\endgroup\$
    – Adám
    Nov 20, 2020 at 10:46
  • 4
    \$\begingroup\$ Welcome to Code Golf Stack Exchange. Nice first question. However, as you can see, you're getting a few requests for clarification. That's why it is highly recommended to first post proposed challenges in the Sandbox. \$\endgroup\$
    – Adám
    Nov 20, 2020 at 10:49
  • 1
    \$\begingroup\$ If you want to use a programming language without support for large integers, returning the result modulo 2^32 It's not a good idea to penalize a language just because it has support for large integers. I suggest you allow the modulo 2^32 possibility for any language \$\endgroup\$
    – Luis Mendo
    Nov 20, 2020 at 10:56
  • 2
    \$\begingroup\$ What is the first iteration? CAT or CHARLIE ALFA TANGO? \$\endgroup\$
    – SunnyMoon
    Nov 20, 2020 at 11:29

15 Answers 15

31
\$\begingroup\$

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.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ "I bet there’s a more concise way to represent the matrix." Believe me, I tried... but that being said, some approach might still work in a language without dictionary compression. It's worth observing that the 1s are kinda sparse, the 2s are way sparser, and there are no elements greater than 2. The main approach I tried was to reconstitute the matrix of non-zero values from (deltas of) indices then add the twos in on top of that, but compressing to binary and adding the 2s in the same way could also work? \$\endgroup\$ Nov 20, 2020 at 19:11
  • 3
    \$\begingroup\$ That's how I have done it: using the transition matrix (although I have used python). By the way, the eigenvalues and eigenspaces of the matrix gives some extra info about the grown rate and about which words grown more or less \$\endgroup\$
    – user38141
    Nov 20, 2020 at 21:51
  • 1
    \$\begingroup\$ Welcome to the site, nice first answer! \$\endgroup\$
    – vrintle
    Nov 21, 2020 at 2:49
  • 1
    \$\begingroup\$ @UnrelatedString I think I’ve now found a significantly more concise way to represent the matrix, but I don’t know if it will beat dictionary compression. \$\endgroup\$ Nov 23, 2020 at 21:20
  • \$\begingroup\$ I have already tried something vaguely similar, but I haven't tried transposing or otherwise fiddling with it too much, so I'll give it another shot. Thanks! \$\endgroup\$ Nov 23, 2020 at 23:35
11
\$\begingroup\$

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)

\$\endgroup\$
9
\$\begingroup\$

R, 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 R.

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 
\$\endgroup\$
6
  • 1
    \$\begingroup\$ rep(1,26) can be !!1:26 for -3 bytes \$\endgroup\$ Nov 20, 2020 at 14:35
  • \$\begingroup\$ @RobinRyder Very nice! Thanks! \$\endgroup\$ Nov 20, 2020 at 14:39
  • \$\begingroup\$ 122 bytes with the DescTools package (which isn't installed on TIO, unfortunately, but this works on my local install). The StrSpell function in DescTools contains the NATO alphabet as a built-in. \$\endgroup\$ Nov 21, 2020 at 9:41
  • \$\begingroup\$ DescTools is installed at rdrr.io, but for some reason it gives an error... \$\endgroup\$ Nov 21, 2020 at 9:44
  • \$\begingroup\$ ...but you should definitely submit this if you can get it to run! How on earth you discovered the NATO alphabet as a built-in is amazing! \$\endgroup\$ Nov 21, 2020 at 9:45
7
\$\begingroup\$

Charcoal, 133 130 bytes

F¹⁰⁰≔E⪪”$±DuaB``IY″²÷⸿↓⪪∧⮌9Pπx¦⸿S1lJ|#←¹Fι´³As¦L₂≕⬤m⍘M▶⭆dω{ⅈ⊟C0cO\⟦;⊟⁼`→<¬UPνρL⊖¦N↷jOh⧴0r↨J9α➙n\²`⟧JξUL≕φ5u”¶ΣEκ∨¬ι§θ⌕αμθIΣES§θ⌕αι

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

F¹⁰⁰

Loop 100 times.

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

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.

IΣES§θ⌕αι

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

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 87 bytes by using the á and builtins, and reversing the words in the compressed string (input as lowercase). \$\endgroup\$ Nov 23, 2020 at 8:17
  • \$\begingroup\$ @KevinCruijssen Very nice, thanks a lot! Is the á really necessary, it seems to work fine without it? \$\endgroup\$
    – ovs
    Nov 23, 2020 at 9:46
  • \$\begingroup\$ Ah, you're completely right, the á isn't necessary. Based on the rule "Whitespaces do not count. Only letters do." I assumed the input could contain spaces, but apparently the input is always a single word. In that case you indeed don't need the á. \$\endgroup\$ Nov 23, 2020 at 9:52
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
  • 4
    \$\begingroup\$ Any reason for the downvote? \$\endgroup\$ Nov 20, 2020 at 14:18
  • \$\begingroup\$ 77 bytes. I messed with the uncompressed string by hand a bit, and in particular capitalized some stuff--turns out there are enough proper nouns in there that it offsets the cost of turning it back to lower case. Also, ȷ2 for 100. \$\endgroup\$ Nov 20, 2020 at 16:58
  • \$\begingroup\$ @UnrelatedString It looks like that compressed string has rayx and mail in it? Edit: Never mind, just realised it doesn't matter what order the letters are in \$\endgroup\$ Nov 20, 2020 at 17:02
  • \$\begingroup\$ Indeed, as well as mail for lima, since the order of letters doesn't affect anything. \$\endgroup\$ Nov 20, 2020 at 17:03
4
\$\begingroup\$

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"
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Husk has modular indexing right? You can remove the %32 and just start the compressed string with india (if Husk uses 1-based indexing) \$\endgroup\$ Nov 20, 2020 at 12:30
  • \$\begingroup\$ @cairdcoinheringaahing - that is a super suggestion, thanks a lot! I now need to go back over all my previous golfs and apply it there, too! \$\endgroup\$ Nov 20, 2020 at 12:46
4
\$\begingroup\$

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.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ I'm not sure it's going to complete within the lifespan of the universe. With an optimistic branching factor of ~5, this is going to take \$5^{100}\approx8\times10^{69}\$ iterations. \$\endgroup\$
    – Arnauld
    Nov 20, 2020 at 12:34
  • \$\begingroup\$ (It does work in theory, though.) \$\endgroup\$
    – Arnauld
    Nov 20, 2020 at 12:36
  • \$\begingroup\$ @Arnauld what is the general rule on codegolf? Are programs that cannot terminate in a human time be accepted? \$\endgroup\$
    – user38141
    Nov 20, 2020 at 12:38
  • 1
    \$\begingroup\$ @user38141 I think that answers that only work in theory are OK unless explicitly specified otherwise in the challenge. Here is a related meta post about theoretically large values. (But with this challenge, even a single letter cannot be computed in a reasonable time with that kind of approach.) \$\endgroup\$
    – Arnauld
    Nov 20, 2020 at 12:46
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Can you replace char*l[] with char**l ? \$\endgroup\$
    – CSM
    Nov 22, 2020 at 15:21
  • \$\begingroup\$ GMP has a C++ wrapper; it defaults to zero, and allows mpz_class a,b; a+= b;. This might save a few bytes \$\endgroup\$
    – CSM
    Nov 22, 2020 at 15:26
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.