24
\$\begingroup\$

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
Improve this question
\$\endgroup\$
9
  • 7
    \$\begingroup\$ Note that the 3rd rule can't be enforced on TIO, which times out at 1 minute. \$\endgroup\$ Commented Dec 18, 2020 at 10:57
  • 11
    \$\begingroup\$ 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?) \$\endgroup\$ Commented Dec 18, 2020 at 11:04
  • 3
    \$\begingroup\$ Instead of indexing can we just return the string? Some languages (Haskell) allow for infinite strings. \$\endgroup\$ Commented Dec 18, 2020 at 11:18
  • 5
    \$\begingroup\$ "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 :)). \$\endgroup\$ Commented Dec 18, 2020 at 12:53
  • 5
    \$\begingroup\$ "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. \$\endgroup\$ Commented Dec 18, 2020 at 12:54

9 Answers 9

Reset to default
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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).

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Can't you get rid of 'Y' in ['A'..'Y'] ? \$\endgroup\$ Commented Dec 18, 2020 at 13:23
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 18, 2020 at 13:40
  • 1
    \$\begingroup\$ Oh, it worked for small numbers, anyway you can use 4*length['B'..x] instead of sum[4|l<-['A'..'Y'],l<x] \$\endgroup\$ Commented Dec 18, 2020 at 14:57
  • \$\begingroup\$ How can the complexity be so low? The solutions based on base-5 representation have complexity O(log(n)). \$\endgroup\$ Commented Dec 18, 2020 at 16:54
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ Commented Dec 18, 2020 at 17:46
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You can save one byte with str.find. \$\endgroup\$ Commented Jan 24, 2021 at 10:23
2
\$\begingroup\$

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.

Try it online or verify all test cases.

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".

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Do you really need to remove the 'z'? \$\endgroup\$ Commented Dec 18, 2020 at 12:49
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 18, 2020 at 13:16
2
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

C# (Visual C# Interactive Compiler), 254 234 230 229 228 209 199 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)
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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!). \$\endgroup\$ Commented Dec 21, 2020 at 0:50
1
\$\begingroup\$

Julia 1.0, 153 bytes

f(n)=*('A':'Y'...,"DIAIAOEONAOEOYTRUOQIRIHEADSMNGSCRDMAMUATAABUGIXARPAOEGLSKSRBLUSLEWIIIEAELUOXNLOEAOEIUAREARNLNDRLNESK")[n<1||f(n÷5)-'@':25:end][1+n%5]

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 185 182 179 177 174 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.

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.