19
\$\begingroup\$

Alienese refers to two "languages" in the show Futurama. In actuality, they are two ciphers of English text with a pictographic alphabet. The first is a simple substitution cipher, but the second is slightly more complex. The second is a type of autokey cipher that follows these steps:

  • Take a word to be encrypted, e.g. FUTURAMA
  • Replace each letter with its 0-index in the alphabet: [5, 20, 19, 20, 17, 0, 12, 0]
    • Note that, due to the next step, zero indexing is important and 1 indexing cannot be used
  • Take the cumulative sums of the array: [5, 25, 44, 64, 81, 81, 93, 93]
  • Modulo each term by 26 to bring it within bounds: [5, 25, 18, 12, 3, 3, 15, 15]
  • Index into the alphabet: FZSMDDPP

We can iterate this process until we reach our original word again. For example, for FUTURAMA, the full list, space separated, is

FUTURAMA FZSMDDPP FEWILODS FJFNYMPH FOTGEQFM FTMSWMRD FYKCYKBE FDNPNXYC FIVKXUSU FNISPJBV FSASHQRM FXXPWMDP FCZOKWZO FHGUEAZN FMSMQQPC FRJVLBQS FWFALMCU FBGGRDFZ FGMSJMRQ FLXPYKBR FQNCAKLC FVIKKUFH FAISCWBI FFNFHDEM FKXCJMQC FPMOXJZB FUGURAZA FZFZQQPP FEJIYODS FJSAYMPH FOGGEQFM FTZFJZEQ FYXCLKOE FDACNXLP FIIKXUFU FNVFCWBV FSNSUQRM FXKCWMDP FCMOKWZO FHTHRNMA FMFMDQCC FRWILBDF FWSALMPU FBTTEQFZ FGZSWMRQ FLKCYKBR FQACAKLC FVVXXHSU FAVSPWOI FFASHDRZ FKKCJMDC FPZBKWZB FUTUEAZA FZSMQQPP FEWIYODS FJFNLZCU FOTGRQSM FTMSJZRD FYKCLKBE FDNPAKLP FIVKKUFU FNISCWBV FSASUQRM FXXPJZQC FCZOXWMO FHGURNZN FMSMDQPC FRJVYODF FWFAYMPU FBGGEQFZ FGMSWMRQ FLXPLXOE FQNCNKYC FVIKXHFH FAISPWBI FFNFUQRZ FKXCWMDC FPMOKWZB FUGUEAZA FZFZDDCC FEJILOQS FJSALZPH FOGGRQFM FTZFWMRD FYXCYKBE FDACAKLP FIIKKUFU FNVFPJOI FSNSHQEM FXKCJZDP FCMOXWZO FHTHEAZN FMFMQQPC FRWIYODF FWSAYMPU FBTTRDSM FGZSJMEQ FLKCLXBR FQACNKLC FVVXKUFH FAVSCWBI FFASUQRZ FKKCWMDC FPZBXJMO

and takes 104 steps to return to FUTURAMA. I conjecture that, for any non-empty string of letters, this process always returns to the original string in a finite number of steps.


You are to "prove" this conjecture. That is, write a program that takes a non-empty string of letters (ABCDEFGHIJKLMNOPQRSTUVWXYZ, or abcdefghijklmnopqrstuvwxyz, you may choose), and outputs the number of steps to return to the original input, by iterating this autokey cipher. Note that, by listing the terms, the list should either start or end with the input, which counts as either the first or last step.

You may take input in any convenient format, including taking the input as an array of characters. You may only take the input as an array of code points if you are unable to input as characters or as a string (e.g. brainfuck).

This is , so the shortest code in bytes wins.

Test cases

J -> 1
NK -> 2
TQR -> 52
NAK -> 4
AAAQ -> 1
CGCC -> 13
CAIRD -> 26
NNNNX -> 8
FUTURAMA -> 104
ALIENESE -> 104
NANNANNAN -> 16
ZBDMBCWJQJPWF -> 208
MUJJEKIBPULKWRHW -> 2704
HWGYIBRBRBLADVYTXL -> 5408

Interestingly, it appears as almost all words result in a number of steps either equal to 1 (a fixed point) or divisible by 13. We say a word is "interestingly-aliense" if this isn't the case, i.e. it is neither a fixed point, nor has a cycle length divisible by 13. We can see, by brute forcing all combinations of words with 2 or 3 letters, that the full list of these words is

NA NB NC ND NE NF NG NH NI NJ NK NL NM NN NO NP NQ NR NS NT NU NV NW NX NY NZ ANA ANB ANC AND ANE ANF ANG ANH ANI ANJ ANK ANL ANM ANN ANO ANP ANQ ANR ANS ANT ANU ANV ANW ANX ANY ANZ NAA NAB NAC NAD NAE NAF NAG NAH NAI NAJ NAK NAL NAM NAN NAO NAP NAQ NAR NAS NAT NAU NAV NAW NAX NAY NAZ NNA NNB NNC NND NNE NNF NNG NNH NNI NNJ NNK NNL NNM NNN NNO NNP NNQ NNR NNS NNT NNU NNV NNW NNX NNY NNZ

All of which either result in 2 or 4. We can also see that all of these contain the letter N. Indeed, we can try out some guesses for longer "interestingly-alienese" words based on this. For example, NNNNX has a cycle of 8 (NNNNX, NANAX, NNAAX, NAAAX, NNNNK, NANAK, NNAAK, NAAAK), and NANNANNAN has a cycle of 16, as shown above. Can you find any more, potentially with longer cycles?

\$\endgroup\$
12
  • 5
    \$\begingroup\$ "We can also see that all of these contain the letter N." Could that have something to do with N being at index 13 in the alphabet? \$\endgroup\$
    – Mayube
    Nov 10 at 21:05
  • 2
    \$\begingroup\$ Every string of some number of Ns and As, followed by an arbitrary final letter, containing an N prior to the final \$2^k\$ letters has a cycle of at least \$2^{k+1}\$. \$\endgroup\$
    – att
    Nov 10 at 22:16
  • 3
    \$\begingroup\$ By linearity, every string has a period dividing the period of BAAAA...A. I suspect that the period of BAAA...A can be proven rigorously using Lucas's Theorem. \$\endgroup\$
    – Nitrodon
    Nov 10 at 22:52
  • 2
    \$\begingroup\$ @Jonah taking the cumulative sum is readily reversible (the modulo doesn't change that) meaning that left of the two Bs in your exapmle there has to be the same word. \$\endgroup\$
    – loopy walt
    Nov 11 at 5:30
  • 5
    \$\begingroup\$ I think I've managed to prove a closed form solution. The greatest power of two dividing the answer is the smallest power of two strictly greater than the number of letters after the first occurrence of one of BDFHJLNPRTVXZ. This number of letters is treated as 0 if none of those characters are in the word. A similar statement holds for powers of 13 and letters other than AN. \$\endgroup\$
    – Nitrodon
    Nov 11 at 15:17

21 Answers 21

11
\$\begingroup\$

K (ngn/k), 13 12 bytes

#(26!+\)\65!

Try it online!

Git gud, Jelly. Only one byte ahead of an ASCII-only language? :P

Takes uppercase input and computes the length of the loop. -1 byte thanks to ZippyMagician's observation that subtract 65 == mod 65.

#(26!+\)\65!     input: a string
         65!     modulo 65 ('A') from each letter (gives a numeric list)
 (     )\        repeat and collect until loop is found:
  26!+\            cumulative sum mod 26
#                length of the result
\$\endgroup\$
4
  • \$\begingroup\$ Is this running the computation or did you find the mathematical formula? If the latter, can you explain? \$\endgroup\$
    – Jonah
    Nov 10 at 23:49
  • 2
    \$\begingroup\$ @Jonah It just computes what is specified in the challenge, without the step of converting everything back to A-Z. \$\endgroup\$
    – Bubbler
    Nov 10 at 23:52
  • 1
    \$\begingroup\$ K's beaten golflangs before (Not Jelly in that one :P) \$\endgroup\$
    – emanresu A
    Nov 11 at 4:38
  • 1
    \$\begingroup\$ @Jonah This was actually my first approach for Charcoal but in that case it turned out to be golfier (although much slower) to convert everything back to letters, as Charcoal's cyclic indexing avoids wasting bytes on an explicit modulo operation. \$\endgroup\$
    – Neil
    Nov 11 at 8:34
8
+100
\$\begingroup\$

Wolfram Language (Mathematica), 60 bytes

If[#!=##2,1+Accumulate@#~Mod~26~#0~##,0]&[LetterNumber@#-1]&

Try it online!

Input a list of characters. Determines the period through recursion. Times out (or reaches the recursion limit) for larger test cases.


Wolfram Language (Mathematica), 69 65 63 bytes

s1//.j_/;!Drop[LetterNumber@s-1,-j]~Mod~#1:>j#&//#@2#@13&

Try it online!

Input a list of characters. Computes the period. The private-use characters are \[Function] and \[VectorLess].

                                              &             g: i =>
1//.j_/;!                                 :>j#                least power of i (=j) such that
         Drop[LetterNumber@s-1,-j]~Mod~#1                      no elements divisible by i outside the final j
                                               //#@2#@13&   g(2)*g(13)

Explanation:

Denote the \$n\$th accumulation of the list \$A=(a_1,a_2,...,a_l)\$ by \$A[n]=(a[n]_1,a[n]_2,...,a[n]_l)\$, and the length of the cycle of \$A\$ modulo \$m\$ by \$c_m(A)\$. Then, in general,
\$a[n]_k=\displaystyle\sum_{i=0}^{k-1}\frac{n^{(i)}}{1^{(i)}}a_{k-i}=a_k+\sum_{i=1}^{k-1}\frac{n^{(i)}}{1^{(i)}}a_{k-i}\$, where \$x^{(y)}\$ is the rising factorial. (These are the diagonals of Pascal's triangle).
By definition of a cycle, for any \$n\$ where \$A[n]\equiv A\pmod m\$, that is, \$a[n]_k\equiv a_k\pmod{m}\$ for all \$k\$, \$c_m(A)\mid n\$.

Since 2 and 13 are relatively prime, \$c_{26}(A)=\operatorname{LCM}(c_2(A),c_{13}(A))\$.

First consider cycles mod 2. Let \$2^x\$ be the least integer power of 2 such that \$2\mid a_i\$ for all \$a_i\le l-2^x\$, i.e. the final \$2^x\$ elements contain all those not divisible by 2. Consider the \$2^x\$th accumulation \$A[2^x]\$:
\$\begin{align*} a[2^x]_k&=a_k+\sum_{i=1}^{k-1}\frac{(2^x)^{(i)}}{1^{(i)}}a_{k-i}\\ &=a_k+\sum_{\substack{1\le &i<k\\&i<2^x}}\frac{(2^x)^{(i)}}{1^{(i)}}a_{k-i} \end{align*}\$
It can be fairly easily be shown that \$2\mid\frac{(2^x)^{(i)}}{1^{(i)}}\$ for all \$0<i<2^x\$, so \$A[2^x]\equiv A\pmod2\$ and \$c_2(A)\mid2^x\$.

Because of the way we defined \$2^x\$ there exists minimal \$p\$ such that \$a_p\not\equiv0\pmod2\$ and \$2^{x-1}\le l-p<2^x\$. Then
\$\begin{align*} a[2^{x-1}]_{p+2^{x-1}}&=a_{p+2^{x-1}}&&+\sum_{i=1}^{p+2^{x-1}-1}\frac{(2^{x-1})^{(i)}}{1^{(i)}}a_{p+2^{x-1}-i}\\ &=a_{p+2^{x-1}}&&+\sum_{i=1}^{2^{x-1}-1}\underbrace{\frac{(2^{x-1})^{(i)}}{1^{(i)}}}_{\equiv0\pmod2}a_{p+2^{x-1}-i}\\ &&&+\underbrace{\frac{(2^{x-1})^{(2^{x-1})}}{1^{(2^{x-1})}}a_p}_{\text{both }\not\equiv0\pmod2}\\ &&&+\sum_{i=1}^{p-1}\frac{(2^{x-1})^{(i+2^{x-1})}}{1^{(i+2^{x-1})}}\underbrace{a_{p-i}}_{\equiv0\pmod2}\\ &\not\equiv a_{p+2^{x-1}}&&\pmod2,\\ \end{align*}\$
using primality of 2 to show that the middle term must \$\not\equiv0\pmod2\$.

Therefore \$A[2^{x-1}]\not\equiv A\pmod2\$, so \$c_2(A)\not\mid2^{x-1}\$. Since 2 is prime, \$c_2(A)=2^x\$.
(\$p\$ does not exist if \$2^x=1\$, but in that case the only integer \$c_2(A)\mid1\$ is \$c_2(A)=1\$).

An analogous argument works mod 13, so we can let \$c_{13}(A)=13^y\$, where \$13^y\$ is defined in a similar fashion to \$2^x\$, and \$c_{26}(A)=2^x13^y\$.

\$\endgroup\$
2
  • \$\begingroup\$ Whoa! So if I'm reading this right you did it, you found a closed form solution, correct? \$\endgroup\$
    – Jonah
    Nov 11 at 22:38
  • \$\begingroup\$ @Jonah I believe so. Nitrodon also seems to have commented the same solution on the main post. \$\endgroup\$
    – att
    Nov 11 at 22:51
4
\$\begingroup\$

Jelly, 14 12 bytes

ØAiⱮ’Ä%26ƊƬL

Try it online!

\$\endgroup\$
3
4
\$\begingroup\$

Ruby, 69 64 bytes

->s{g=h=s.bytes;1.step.find{r=0;g==h=h.map{|b|(r+=b-13)%26+65}}}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 3.8 (pre-release), 83 bytes

lambda s:(g:=lambda r,i=1:all(ord(c)%r==~r%2for c in s[:-i])or g(r,i*r)*r)(2)*g(13)

Try it online!

Port of my second Mathematica solution, and probably a bit easier to understand. Python plays nicer with out-of-bounds slices.

\$\endgroup\$
3
\$\begingroup\$

QBasic, 119 bytes

INPUT w$
n$=w$
1s=0
FOR i=1TO LEN(n$)
s=s+ASC(MID$(n$,i))-65
MID$(n$,i)=CHR$(s MOD 26+65)
NEXT
r=r+1
IF n$<>w$GOTO 1
?r

Try it at Archive.org!

Explanation

INPUT w$
n$ = w$

Input w$ (the original word) and set n$ (the next encrypted form) to w$.

1 s = 0

Label 1 is the start of our main loop. Initialize s (the cumulative sum) as 0.

FOR i = 1 TO LEN(n$)

Loop over the indices of the characters in n$.

s = s + ASC(MID$(n$, i)) - 65

Get the ASCII code of the ith character of n$, subtract 65, and add to the cumulative sum.

MID$(n$, i) = CHR$(s MOD 26 + 65)

Take s mod 26, add 65, convert from ASCII code, and set the ith character of n$ to that character.

NEXT
r = r + 1

End of FOR loop. Increment r (the number of repetitions we've gone through).

IF n$ <> w$ THEN GOTO 1

If the next encrypted form is different from the original word, loop.

PRINT r

Otherwise, print the number of repetitions.


In QB64, we can get down to 106 bytes using the extended forms of ASC instead of MID$:

INPUT w$
n$=w$
1s=0
FOR i=1TO LEN(n$)
s=s+ASC(n$,i)-65
ASC(n$,i)=s MOD 26+65
NEXT
r=r+1
IF n$<>w$GOTO 1
?r
\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js),  62  61 bytes

Expects the input in lowercase, as suggested by @UnrelatedString (-1 byte).

f=(s,q)=>s!=q&&1+f(Buffer(s).map(c=>(t+=c+7)%26+97,t=0),q||s)

Try it online!

Or 56 bytes by taking a Buffer as input.

Commented

f = (s,            // s = input string
        q) =>      // q = reference string, initially undefined
  s != q &&        // stop as soon as s == q
  1 +              // otherwise: increment the final result
  f(               // do a recursive call:
    Buffer(s)      //   turn s into a Buffer
    .map(c =>      //   for each ASCII code c in the Buffer:
      (t += c + 7) //     add c + 7 to t
                   //     (where 7 is -(97 mod 26) + 26)
      % 26         //     reduce t modulo 26
      + 97,        //     add the ASCII code of 'a'
      t = 0        //     start with t = 0
    ),             //   end of map()
    q              //   pass the reference string q,
    || s           //   or s if q is still undefined (1st iteration)
  )                // end of recursive call
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 61 with lowercase input \$\endgroup\$ Nov 10 at 22:22
2
\$\begingroup\$

Joy, 166 bytes

DEFINE i == rotate 1 + rotate [0]swap[[dup dup size 1 - at]dip +[]cons concat]step rest[26 rem]map.
DEFINE a == 0 swap[ord 65 -]map dup i[equal not][i]while pop pop.

Crashes on the longer inputs, but as far as I can tell that's because of the implementation.
Explanation:

DEFINE sumScan == [0]swap[[dup dup size 1 - at]dip +[]cons concat]step rest.
DEFINE iter == rotate 1 + rotate (* increment counter *)
    sumScan[26 rem]map. (* sum scan, then mod 26 *)
DEFINE alienese == 0 swap[ord 65 -]map (* convert to numbers and set counter *)
    dup iter[equal not][iter]while pop pop. (* iterate until it's equal again, then pop off values that aren't counter *)
\$\endgroup\$
2
\$\begingroup\$

Python 3, 136 bytes

s=k=input();n=1
while 1:
 l=[ord(x)-65for x in s];s=''.join(chr(sum(l[:x+1])%26+65)for x in range(len(l)))
 if s==k:break
 n+=1
print(n)

Try it online!

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

Pari/GP, 79 bytes

s->d=Mod(1-x,x^#s);p=Mod(Polrev(Vecsmall(s))-65/d,26);i=1;while(p*d^i!=p,i++);i

Try it online!

Convert the string to an element \$P\$ in the ring \$\mathbb{Z}[X]/(26,X^n)\$, where \$n\$ is the length of the string, and find the smallest \$i>0\$ such that \$P*(1-X)^i=P\$.

\$\endgroup\$
7
  • \$\begingroup\$ What’s the connection between the scan sum and 1-X? \$\endgroup\$
    – Jonah
    Nov 11 at 15:26
  • 1
    \$\begingroup\$ @Jonah Scan sum is actually \$P \mapsto P*(1+X+X^2+X^3+\cdots) = P/(1-X)\$. \$P \mapsto P*(1-X)\$ is the inverse of scan sum. \$\endgroup\$
    – alephalpha
    Nov 11 at 15:32
  • \$\begingroup\$ So does this mean that there is no efficient/closed form way to compute the target inverse? \$\endgroup\$
    – Jonah
    Nov 11 at 15:35
  • 1
    \$\begingroup\$ @Jonah I'm not sure if there is a closed form for the the cycle length. \$\endgroup\$
    – alephalpha
    Nov 11 at 15:43
  • 1
    \$\begingroup\$ @Jonah There is a closed form when the input is of the form BAAA.... In this case the cycle length is \$2^a 13^b\$, where \$a, b\$ are the smallest integers such that \$2^a \ge n, 13^b \ge n\$. This can be proved using Lucas's Theorem. I don't know about the general case. \$\endgroup\$
    – alephalpha
    Nov 11 at 16:03
2
\$\begingroup\$

Husk, 16 bytes

LU¡₁m(-65D
m%26∫

Try it online!

Explanation:

    m(-65D    # map codepoint - 65
LU¡₁          # length of longest unique prefix of iteration of function on next line
m%26∫         # map %26 on cumsum
\$\endgroup\$
1
  • \$\begingroup\$ I'm surprised you can't do LU¡om%26∫m(-65D for -1 byte \$\endgroup\$ Nov 28 at 20:11
1
\$\begingroup\$

Pyth, 23 bytes

l.usmC+65%sd26._m-Cd65N

Try it online!

l.usmC+65%sd26._m-Cd65N         # Full program
 .u                             # Collect until input found
                m     N         # Map over current value (variable d)
                  Cd            # Code point of d
                 -  65          # Minus 65 (Index of alphabet)
              ._                # Prefixes
    m                           # Map over (on prefixes with d)
          sd                    # Sum current prefix
         %  26                  # Modulo 26
      +65                       # Add 65 (Code point)
     C                          # ASCII char
   s                            # Join list
l                               # Length of whole scan-fixedpoint
\$\endgroup\$
2
  • \$\begingroup\$ 18 bytes \$\endgroup\$
    – Neil
    Nov 11 at 10:19
  • \$\begingroup\$ 17 bytes with lowercase \$\endgroup\$
    – hakr14
    Nov 28 at 4:40
1
\$\begingroup\$

05AB1E, 17 15 bytes

1µAskηOAsèDIQ}N

-2 bytes thanks to @Neil.

Input as a lowercase list of characters.

Try it online or verify all test cases (except for the last two, which time out).

Slightly faster minor alternative (thanks to @Neil):

Ask©1µηO₂%D®Q}N

Try it online or verify all test cases (except for the last two, which still time out).

Explanation:

1µ            # Loop until the counter is 1:
    k         #  Get the indices
   s          #  of the current list of characters (this will be the implicit
              #                                     input in the first iteration)
  A           #  in the lowercase alphabet
     η        #  Get the prefixes of this list
      O       #  And sum each inner prefix-list
       Asè    #  Modular index this list into the lowercase alphabet
          D   #  Duplicate it
           IQ #  Pop the copy, and check if it's equal to the input
              #  (if this is truthy, implicitly increase the counter by 1)
 }N           # After the loop: output the last 0-based index of the loop
              # (after which it is output implicitly as result)
\$\endgroup\$
3
  • \$\begingroup\$ The ₂% seems unnecessary, assuming 05AB1E has cyclic indexing? \$\endgroup\$
    – Neil
    Nov 11 at 10:21
  • \$\begingroup\$ Alternative, also 15 bytes \$\endgroup\$
    – Neil
    Nov 11 at 10:24
  • \$\begingroup\$ @Neil Ah, of course.. And nice alternative. :) \$\endgroup\$ Nov 11 at 11:00
1
\$\begingroup\$

Python, 108 bytes

i=s=[ord(c)-65for c in input()];a=0
while a<1or s!=i:s=[sum(s[:j+1])%26for j in range(len(i))];a+=1
print(a)

Attempt This Online!

This isn't a very interesting answer.

If only Python wasn't bad, we could have this for 105 bytes:

lambda s:1+len([*iter(lambda:(t:=([sum(t[:j+1])%26for j in range(len(s))])),(t:=[ord(c)-65for c in s]))])

Explanation:

lambda s:                      # xxx
[ord(c)-65for c in s]          # convert input string to list of alphabet indeces
(t:=)                          # assign to `t` initially
iter(lambda: ,)                # repeat until t recurs:
            [sum(t[:j+1])%26   # cumulative sums of `t`
      for j in range(len(s))]  
           (t:=)               # reassign to `t`
1+len([*])                     # length of repeating segment

But in the inner lambda, the list comprehension binds t as a free variable to the inner lambda, rather than a free variable to the outer lambda. If there was a way to do nonlocal in a lambda, we could avoid this.

Here's a bit of a hack that does actually work: Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

Japt v1.4.5, 24 bytes

;@=mnB å+ £BgXu26Ã eNg}a

Try it Switched to array of characters to save 1

;       - 2nd set of predef. Vars
@...}a  - repeat until true
          return number of times
=       - reassign U(input) by
mnB       * index each in ALPHA
å+        * cumulative sum
£Bg       * each: get[ABCD..]
Xu26Ã       at X%26
eNg     -  compare to orignal input
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 32 28 25 bytes

IΠE⟦²¦¹³⟧XιL↨⌈E⮌θ∧﹪⌕αλιμι

Try it online! Link is to verbose version of code. Explanation: Uses @Nitrodon/@att's closed form formula: for each of the prime factors of 26, the offset from the end of the word of the first letter whose alphabet index is not divisible by that prime is rounded up to the next power of the prime and the two values are multiplied together.

   ⟦²¦¹³⟧                   Literal list `2,13`
  E                         Map over the two primes
          ι                 Current prime
         X                  Raised to power
                θ           Input word
               ⮌            Reversed
              E             Map over letters
                     λ      Current letter
                   ⌕α       Index in alphabet
                  ﹪         Modulo
                      ι     Current prime
                 ∧          Logical And
                       μ    Current index
             ⌈              Take the maximum
            ↨               Converted to base
                        ι   Current prime
           L                Take the length
 Π                          Take the product
I                           Cast to string
                            Implicitly print

Conveniently base conversion of zero is the empty list with length zero so that the prime power is simply 1 for a single letter or a word only containing the letter A.

Previous 28-byte brute-force version:

W¬№υθ«⊞υθ≔⭆θ§αΣE…θ⊕λ⌕αμθ»ILυ

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

W¬№υθ«

Repeat until a cycle is detected. (Since cumulative sum is invertible, this will always be the original word.)

⊞υθ

Save the previous value.

≔⭆θ§αΣE…θ⊕λ⌕αμθ

For each letter, take the prefix so far, convert each letter to its alphabet index, take the sum, and take the letter at that index.

»ILυ

Output the cycle length.

Much faster 36 32-byte version:

≔ES⌕αιθW¬№υθ«⊞υθ≔﹪EθΣ…θ⊕λ²⁶θ»ILυ

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

≔ES⌕αιθ

Map the input letters to their alphabet index.

W¬№υθ«

Repeat until a cycle is detected. (Since cumulative sum is invertible, this will always be the original word.)

⊞υθ

Save the previous value.

≔﹪EθΣ…θ⊕λ²⁶θ

Calculate the cumulative sum modulo 26.

»ILυ

Output the cycle length.

The intermediate values for a string of n+1 Ns can be read from the columns below, with N represented by 1 and A by 0:

0   1(1...)
1   10(10...)
2   1100(1100...)
3   1000(1000...)
4   11110000(11110000...)
5   10100000(10100000...)
6   11000000(11000000...)
7   10000000(10000000...)
8   1111111100000000(...)
    (...)
11  1000100000000000(...)
12  1111000000000000(...)
    (...)
15  1000000000000000(...)
    (...)

The 2ᵏᵗʰ row consists of a cycle of twice its length given by 2ᵏ 1s and 2ᵏ 0s. Over the next 2ᵏ-1 rows the 1s decay into a single 1 as they did for the first 2ᵏ rows, and then the next row doubles in cycle length.

\$\endgroup\$
1
\$\begingroup\$

ayr, 14 bytes

Unfortunately can't beat Bubbler's K answer, but it comes close. This is practically a direct translation, except for the fact that 65| is the same as _65+ in this specific case. Takes capital input.

:#(26|+\)$:65|

Explanation

:                    A non J-style train
                65|  Input mod 65
       ( ... )$:     Fixpoint
     +\                Cumulative sum
  26|                  Mod 26
 #                   Size
\$\endgroup\$
0
\$\begingroup\$

Haskell, 89 bytes

import Data.Char
s!o|t==o=1|True=1+t!o where t=scanl1(\x y->chr$(ord x+ord y)`mod`26+65)s

Try it online

(65 * 2 mod 26 conveniently equals 0.)

\$\endgroup\$
0
\$\begingroup\$

TI-Basic, 129 131 bytes

Input Str1
"ABCDEFGHIJKLMNOPQRSTUVWXYZ→Str2
Str1
Repeat Ans=Str1
cumSum(seq(inString(Str2,sub(Ans,I,1))-1,I,1,length(Ans
1+remainder(Ans,26→R
J+1→J
sub(Str2,ʟR(1),1
For(I,2,dim(ʟR
Ans+sub(Str2,ʟR(I),1
End
End
J

+1 byte if not run on a TI-84+/SE with the 2.53 MP OS by replacing remainder(Ans,26 with 26fPart(Ans/26.

Output is stored in Ans and displayed.

\$\endgroup\$
0
\$\begingroup\$

Burlesque, 32 bytes

m{**65.%}J1{{++26.%}pa}C~[-jFi+.

Try it online!

m{      # Map each char
 **     # Ord(a)
 65.%   # Mod 65
}       # <-- converted to alphabet index
J       # Duplicate
1       # Prefix Arg to infinite loop
{       #
 {      #
  ++    # Sum
  26.%  # Mod 26
 }      #
 pa     # Partial (applied to each init)
}       #
C~      # Infinite list of function evaluated successively on arg
[-      # Drop first element (original converted string)
j       # Swap in duplicated original
Fi      # Find index of original in list
+.      # Increment by 1 (0 indexed)
\$\endgroup\$
0
\$\begingroup\$

Python3, 101 bytes:

import itertools as i
s,c=(n:=[ord(j)-65for j in n]),1
while(s:=[j%26for j in i.accumulate(s)])!=n:c+=1

If anything, a cleaner and more efficient way to produce the cumulative sums.

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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