# Animal-Alphabetical Sequence

The Animal-Alphabetical Sequence is an infinite string of letters built accordingly to the following procedure:

1. Start with the letter A;

2. Replace each letter with the name of the animal starting with such letter in the table below;

3. Go back to step 2.

For instance, the first four steps of the procedure give:

• A

• ADDAX

• ADDAXDINGODINGOADDAXXERUS

• ADDAXDINGODINGOADDAXXERUSDINGOINDRINYALAGECKOOTTERDINGOINDRINYALAGECKOOTTERADDAXDINGODINGOADDAXXERUSXERUSEAGLEROBINURIALSQUID

Note that the string obtained at each step is a prefix of the string obtained at the next step. Hence, the procedure does indeed converge to a well-defined infinite string:

ADDAXDINGODINGOADDAXXERUSDINGOIND...

# The Challenge

Write a function that takes as input an integer n in the range [0, 2^31 - 1] and returns as output the n-th letter of the Animal-Alphabetical Sequence.

# Notes

• The first letter is the 0-th.

• Letters can be uppercase or lowercase.

• It must be possible to run the program in the Try It Online interpreter and get the result in at most 5 minutes.

# Test Cases

1511763812 -> M
1603218999 -> I
2049234744 -> X
2060411875 -> K
2147483647 -> D


# Table of Animal Names

ADDAX
BISON
CAMEL
DINGO
EAGLE
FOSSA
GECKO
HORSE
INDRI
JAMBU
KOALA
LEMUR
MOUSE
NYALA
OTTER
PRAWN
QUAIL
ROBIN
SQUID
TIGER
URIAL
VIXEN
WHALE
XERUS
YAPOK
ZEBRA

• Note that the 3rd rule can't be enforced on TIO, which times out at 1 minute. Dec 18, 2020 at 10:57
• Small golfing tip for anyone doing this challenge: FOSSA, JAMBU, VIXEN, and ZEBRA can be ignored, because none of the other animal names contain these letters and it always starts with A. (And as mentioned by @Arnauld, TIO always times out after 60 seconds, so is the time limit we'll have to work with 60 seconds or 300 seconds?) Dec 18, 2020 at 11:04
• Instead of indexing can we just return the string? Some languages (Haskell) allow for infinite strings. Dec 18, 2020 at 11:18
• "The first letter is the 0-th." - it's probably best to just allow 1-indexing (where the first letter is the 1st, like "first" suggests :)). Dec 18, 2020 at 12:53
• "It must be possible to run the program in the Try It Online interpreter and get the result in at most 5 minutes." - TIO times out at 1 minute. Dec 18, 2020 at 12:54

# Charcoal, 83 bytes

≔AηＦ↨Ｎ⁵≔§⁺η§⪪”$⌊∧Ｘ;F‖ρ=ＪD θ⊘⊙～'ΣV⦄Ｋ◨｜]≕‖◨⟧TJρ¿¿C´!⁸⁶S/Ｕ¶V×Ｗ⧴a“,=6；‴*Þ↓h!�{≦”⁴⌕αηιηη  Try it online! Link is to verbose version of code. Explanation: ≔Aη  Start with A at the 0th index. Ｆ↨Ｎ⁵  Input n, convert it to base 5 and loop over the digits. ≔§⁺η§⪪”...”⁴⌕αηιη  Get the current animal from the compressed string of all animal suffixes (excluding EBRA) and lookup the appropriate letter from the current digit. η  Output the final letter. # JavaScript (Node.js), 168 bytes n=>[...n.toString(5)].reduce((c,k)=>'DIAIA-EON-OEOYTRUOQIR-HEADSMNG-CRD-AMUATAABUGI-ARPAOEGL-KSR-LUSLEWIIIEA-LUOXNLOE-OEI-AREARNLNDRL-ESK'[Buffer(c)[0]-90+k*25]||c,'A')  Try it online! ### How? The lookup string (let's call it S) is built as 4 sub-strings of 25 characters as follows: ABCDEFGHIJKLMNOPQRSTUVWXY ------------------------- DIAIA-EON-OEOYTRUOQIR-HEA --> 2nd letter of each word DSMNG-CRD-AMUATAABUGI-ARP --> 3rd letter of each word AOEGL-KSR-LUSLEWIIIEA-LUO --> 4th letter of each word XNLOE-OEI-AREARNLNDRL-ESK --> 5th letter of each word  Therefore: S[Buffer(c)[0] - 90 + k * 25] // equivalent to S[Buffer(c)[0] - 65 + (k - 1) * 25]  is undefined if k = 0, in which case we leave c unchanged as expected (the first letter of the word that starts with c is c). # Haskell, 170 162 bytes Thanks to AZTECCO for helping me index the lookup shorter f 0='A' f n|x<-f$div n 5=(x:drop(4*length['B'..x])"DDAXISONAMELINGOAGLEOSSAECKOORSENDRIAMBUOALAEMUROUSEYALATTERRAWNUAILOBINQUIDIGERRIALIXENHALEERUSAPOK")!!mod n 5


Try it online!

This exceeds TIO's output capacity nearly instantly, so I think this is safe on timing. My quick analysis tells me the algorithm should be $$\O(n)\$$. That is if you input a number of length $$\n\$$ bits it should take about the $$\n\$$ time to find the answer.

I'm not the best at golfing data encoding so I think that is where I am losing the most bytes.

This gets a lot easier to read if we just say we have a function u which gives the word for a letter. Then it is:

f 0='A'
f n=u(f$div n 5)!!mod n 5  • Can't you get rid of 'Y' in ['A'..'Y'] ? Dec 18, 2020 at 13:23 • @AZTECCO I think it would theoretically work however it needs to iterate through all of the characters which I think is quite a big number so it times out on TIO. Dec 18, 2020 at 13:40 • Oh, it worked for small numbers, anyway you can use 4*length['B'..x] instead of sum[4|l<-['A'..'Y'],l<x] Dec 18, 2020 at 14:57 • How can the complexity be so low? The solutions based on base-5 representation have complexity O(log(n)). Dec 18, 2020 at 16:54 • @Jyenas You are right in a way, this is O(n). This is also base 5 representation and I suspect they are also O(n) as well. This is because with n bits the largest number that can be represented is (2^n)-1, and since each number recurrs with 1/5 it's size the result is the logarithm of that. O(log_5(2^n)) is equivalent by base conversion to O(n). Dec 18, 2020 at 17:46 # Python 3 2, 160 159 158 bytes s="ABCDEGHIKLMNOPQRSTUWXYDIAIAEONOEOYTRUOQIRHEADSMNGCRDAMUATAABUGIARPAOEGLKSRLUSLEWIIIEALUOXNLOEOEIAREARNLNDRLESK" f=lambda n:s[n and s.find(f(n/5))::22][n%5]  Try it online! -1 thanks to @ovs • You can save one byte with str.find. – ovs Jan 24, 2021 at 10:23 # 05AB1E, 78 77 bytes 'aI5вvA…fjvмSD.•13ôºå}Æ ë¾‚pu®×ÌмĀαù·o×#·Îg4™Ā8%+ÚONp:rƒÜ∊₁Œ¿ÝøuÏādûá•4ôøJ‡yè  -1 byte thanks to @Arnauld. Output in lowercase. Explanation: 'a '# Push string "a" I # Push the input-integer 5в # Convert it to base-5 as list v # Loop y over each digit in this list: A # Push the lowercase alphabet …fjvм # Remove the letters 'f', 'j', and 'v' S # Convert it to a list of characters D # Duplicate this list .•13ôºå}Æ ë¾‚pu®×ÌмĀαù·o×#·Îg4™Ā8%+ÚONp:rƒÜ∊₁Œ¿ÝøuÏādûá• # Push compressed string "ddaxisonamelingoagleeckoorsendrioalaemurouseyalatterrawnuailobinquidigerrialhaleerusapok" 4ô # Split the string into parts of 4 characters ø # Create pairs with the alphabet-list (the trailing 'z' is ignored) J # Join each pair together to a single 5-char string ‡ # Transliterate the current character to the animal name # (again ignoring the trailing 'z') yè # And index digit y into this string for the next iteration # (after the loop, the resulting character is output implicitly)  See this 05AB1E tip of mine (section How to compress strings not part of the dictionary?) to understand why .•13ôºå}Æ ë¾‚pu®×ÌмĀαù·o×#·Îg4™Ā8%+ÚONp:rƒÜ∊₁Œ¿ÝøuÏādûá• is "ddaxisonamelingoagleeckoorsendrioalaemurouseyalatterrawnuailobinquidigerrialhaleerusapok". • Do you really need to remove the 'z'? Dec 18, 2020 at 12:49 • @Arnauld Ah, good point, thanks for -1! :) The ø will simply ignore the trailing parts of unequal length lists, so the 'z' is simply removed, and the ‡ will ignore that trailing 'z' as well. Dec 18, 2020 at 13:16 # Perl 5, 175 bytes sub f{my$n=pop;$_=substr$n?f(1,$n/5):ADDAX,$n%5,1;@_?$_.[DDAXISONAMELINGOAGLE_ECKOORSENDRI_OALAEMUROUSEYALATTERRAWNUAILOBINQUIDIGERRIAL_HALEERUSAPOK=~/_|.{4}/g]->[-65+ord]:$_}


Try it online!

Somewhat ungolfed. Added whitespace and moved dictionary string into variable $animals: sub f {$animals='DDAXISONAMELINGOAGLE_ECKOORSENDRI_OALAEMUROUSE'
.'YALATTERRAWNUAILOBINQUIDIGERRIAL_HALEERUSAPOK';
my $n=pop; #arg$_=substr                           #put letter into $_$n ? f(1,$n/5) : ADDAX, #next word is word at n/5 or first word$n%5,1;                           #get letter at pos n%5 of word
@_                                  #if recursed ...
?$_.[$animals=~/_|.{4}/g]->[-65+ord]#then return letter + its 4 letters in dict
:$_ #else return just letter }  About runtime: on my "vintage" laptop the five test cases spends about 0.025 sec in total. If I change $n/5 into int$n/5 this is reduced to 0.0016 sec (because then it doesn't need to keep dividing by 5 until the decimals disappears, thus far fewer recursions) # C# (Visual C# Interactive Compiler), 254234230229228209199 198 bytes string f(int v,int p=-1){var h=v>-p?f(v/5,v%5):"ADDAX";return p<0?h[..1]:h[p]+"DDAXISONAMELINGOAGLEOSSAECKOORSENDRIAMBUOALAEMUROUSEYALATTERRAWNUAILOBINQUIDIGERRIALIXENHALEERUSAPOK"[(h[p]*4-260)..];}  Try it online! How? char f(int v, int p = -1) { var h = v > -p ? f(v / 5, v % 5) : "ADDAX"; return p < 0 ? h[..1] : h[p] + "DDAXISONAMELINGOAGLEOSSAECKOORSENDRIAMBUOALAEMUROUSEYALATTERRAWNUAILOBINQUIDIGERRIALIXENHALEERUSAPOK"[(h[p] * 4 - 260)..]; }  This version is a complete rewrite of my original solution. Inspired from other submissions, I decided to use a recursive function. The gist is still converting v to base 5 and use the digits to point to the correct words. When v and p are both equal to 0, the conversion is complete, so we take ADDAX and stop the recursion. Zebra was removed from the list because it is not reachable. Updates: • Saved 20 bytes removing the first letter from each word in the string literal. • Replacing do/while with a for loop reduced the size by 4 bytes • -1 byte using a tuple to assign b and g • -1 byte replacing 'A' with 65 • -1 byte replacing [((h[b] - 65) * 4)..] with [(h[b]*4 - 260)..] • -10 bytes using a recursive function • -1 byte replacing v+p>0 with v>-p (thanks to @ceilingcat) • Welcome to Code Golf, nice first answer! You may want to check out our Tips for golfing in C# (although this already looks really well golfed!). Dec 21, 2020 at 0:50 # Julia 1.0, 153 bytes f(n)=*('A':'Y'...,"DIAIAOEONAOEOYTRUOQIRIHEADSMNGSCRDMAMUATAABUGIXARPAOEGLSKSRBLUSLEWIIIEAELUOXNLOEAOEIUAREARNLNDRLNESK")[n<1||f(n÷5)-'@':25:end][1+n%5]  Try it online! # PowerShell, 185182179177174 173 Bytes -1 byte thanks to mazzy! for($f=[char]65;!($x=$f[$args])){$f=$f|%{,$_+"DDAXISONAMELINGOAGLEOSSAECKOORSENDRIAMBUOALAEMUROUSEYALATTERRAWNUAILOBINQUIDIGERRIALIXENHALEERUSAPOK"[($i=$_%65*4)..($i+3)]}}$x


Could probably be shortened, but I got stumped. If 0 can be ignored as an input, you can drop the [char] in [char]65 to save 4 bytes.

• nice golf. you can save 1 byte if you move the $f=$f|... to the for-body Try it online! Dec 19, 2020 at 12:19
• @mazzy thanks again! Dec 20, 2020 at 20:35