18
\$\begingroup\$

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2015 Day 10.

Here's why I'm posting and not Bubbler


The Elves are playing a variation of the game called look-and-say. In plain look-and-say, they take turns making sequences by reading aloud the previous sequence and using that reading as the next sequence. For example, 211 is read as "one two, two ones", which becomes 1221 (1 2, 2 1s).

But this time it's somewhat different. Given a sequence written on a piece of paper, an Elf reads the sequence, and for each chunk of digits, they write the count on the left side and the digit on the right side. And the next Elf does the same on the entire sequence of digits!

For example, if the current sequence is 211333:

Original sequence    : 211333
Read 2 (one two)     : 1(211333)2
Read 1 (two ones)    : 21(211333)21
Read 3 (three threes): 321(211333)213

So the next sequence would be 321211333213.

If the Elves start with the single digit of 1, what will the sequence look like on the paper after n turns?

Input: The non-negative integer n. (Or a positive integer, if you choose to treat 1 as the 1st iteration.)

Output: The resulting list of digits. Can be in any acceptable format, such as a list of numbers or a single string. Be sure to handle multi-digit numbers that appear since iteration 7 - if you're returning a list of digits, make sure that these multi-digit numbers have been split into single digit numbers.

The sequence goes on like this:

1
111
31111
413111131
114111413111131413131
111111114111312114111413111131413131141413131413131
1111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131
11111111111111111111111111111111112111111111111121111111411131211131811131113171141111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131121413121318141312141413131413131414131314131314131214141313141313141413131413131
11111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111121111111111111211111114111312111318111311131711412111313111311131711313411111111111111111111111111111111112111111111111121111111411131211131811131113171141111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131121413121318141312141413131413131414131314131314131214141313141313141413131413131121214131213181313171412141312131814131214141313141313141413131413131413121414131314131314141313141313121413121318141312141413131413131414131314131314131214141313141313141413131413131
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111121111111111111211111114111312111318111311131711412111313111311131711313411112111313111311121113131113111317113133180111111111111111111111111111111111111111111111111111111111111111111111111111111112111111111111111111111111111111111211111111111112111111141113121113181113111317114121113131113111317113134111111111111111111111111111111111121111111111111211111114111312111318111311131711411111111111111211111114111312111318111111114111312114111413111131413131141413131413131141312141413131413131414131314131311214131213181413121414131314131314141313141313141312141413131413131414131314131311212141312131813131714121413121318141312141413131413131414131314131314131214141313141313141413131413131214131213181413121414131314131314141313141313141312141413131413131414131314131311212121413121318131317141213131313171313412121413121318131317141214131213181413121414131314131314141313141313141312141413131413131414131314131312141312131814131214141313141313141413131413131413121414131314131314141313141313121214131213181313171412141312131814131214141313141313141413131413131413121414131314131314141313141313121413121318141312141413131413131414131314131314131214141313141313141413131413131

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$

23 Answers 23

7
\$\begingroup\$

05AB1E, 9 bytes

$FDÅγRŠ)S

Outputs as a list of digits (except for \$n=0\$ resulting in 1 instead of [1]).

Try it online or verify the test cases in the range \$[0,10]\$.

Explanation:

$          # Push 1 and the input-integer
 F         # Pop and loop the input amount of times:
  D        #  Duplicate the current list (or 1 in the first iteration)
   Åγ      #  Pop and run-length encode it, pushing the list of digits and list
           #  of lengths separately to the stack
     R     #  Reverse the list of lengths at the top
      Š    #  Triple-swap the stack: a,b,c to c,a,b
       )   #  Wrap all three values into a list
        S  #  And convert it to a flattened list of digits
           # (after the loop, the result is output implicitly)
\$\endgroup\$
5
\$\begingroup\$

Jelly, 12 bytes

1ŒrUj@ƒƊDFƊ¡

Try it online!

Fixed thanks to pxeger

1         Ɗ¡    Repeatedly apply the given number of times, starting from 1:
 Œr             Encode as a list of [digit, run length] pairs,
   U            reverse each pair,
    j@ƒƊ        join each of them around the original value in sequence,
        D       decompose the elements of their results into digits,
         F      and flatten them.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ "if you're returning a list of digits, make sure that these multi-digit numbers have been split into single digit numbers." Your answer doesn't do this, and it also gives incorrect outputs for n>7 \$\endgroup\$
    – pxeger
    Dec 3, 2021 at 7:19
  • 1
    \$\begingroup\$ @pxeger Thanks; I compared my output to hyper's but didn't think to actually make sure that worked :P \$\endgroup\$ Dec 3, 2021 at 7:26
5
\$\begingroup\$

Rust (1.53+), 124 bytes

|s:&str|{let(mut r,mut x)=(s.into(),0);s.chars().chain([' ']).reduce(|a,b|{x+=1;if a!=b{r=format!("{}{}{}",x,r,a);x=0}b});r}

Try it online!

This only works on Rust 1.53 and newer as older Rust versions did not implement IntoIterator for arrays, but only for array references. This can be fixed by adding a single & to [' '], in which case this might run on 1.51+ since that's when reduce was stabilized.

In the future if group_by is stabilized, this can go down to 96 bytes.

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

JavaScript (ES6),  67  62 bytes

Saved 3 bytes thanks to @MarcMush

0-indexed.

f=n=>s=n?f(n-1).replace(/(.)\1*/g,q=>s=q.length+s+q[0])&&s:"1"

Try it online!

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

Retina, 49 bytes

K`1
"$+"{`$
¶$`¶$`
2%`(.)\1*
$1
0%^`(.)\1*
$.&
¶

Try it online! No test suite due to the way the program uses history. Explanation:

K`1

Replace the input with 1.

"$+"{`

Repeat the originally input number of times.

$
¶$`¶$`

Triplicate the current string.

2%`

Only in the third copy...

(.)\1*
$1

... remove all adjacent duplicates.

0%`

Only in the first copy...

^`

... reversing the list results before reinserting them...

(.)\1*
$.&

... count the runs of repeated digits.

Join everything together.

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

Wolfram Language (Mathematica), 65 55 bytes

Nest[Join[Length/@Reverse[s=Split@#],#,#&@@@s]&,{1},#]&

Try it online!

-10 bytes from @att

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 55 bytes \$\endgroup\$
    – att
    Dec 3, 2021 at 7:14
3
\$\begingroup\$

Python 3.8 (pre-release), 113 bytes

g=lambda c,o,r:r and g(1+c-c*(b:=r[1:2]!=r[0]),b*str(c)+o+r[:b],r[1:])or o
f=lambda n:n and g(1,*2*[f(n-1)])or'1'

Try it online!

Very loosely based on @tsh's answer.

\$\endgroup\$
2
  • \$\begingroup\$ Python 3.8 was released two years ago. ? \$\endgroup\$ Dec 3, 2021 at 16:26
  • \$\begingroup\$ @NickMatteo don't tell me, tell the friendly chaps at TIO ;D \$\endgroup\$
    – loopy walt
    Dec 3, 2021 at 18:38
3
\$\begingroup\$

Ruby, 55 bytes

->n{a=?1;n.times{a.scan(/(.)\1*/){a=[$&.size,$1]*a}};a}

Try it online!

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

BQN, 43 bytes

{({∾•Fmt¨(≠¨∘⌽∾𝕩∾⊑¨)𝕩⊔˜+`»𝕩≠«𝕩}-⟜'0')⍟𝕩"1"}

Try It!

does some heavy lifting here.

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

APL (Dyalog Unicode), 32 29 bytes

Thanks to Razetime for -3 bytes!

{∊⍕¨(≢¨∘⌽,⍵,⊃¨)⍵⊂⍨1,2≠/⍵}⍣⎕⍕1

Try it online!

{ ... }⍣⎕⍕1: Starting with '1', iterate the function input times.

1,2≠/⍵: Binary vector with 1's at the start of runs of equal items.
⍵⊂⍨: Using that boolean mask split the current value into chunks.
( ... ): Apply inner function to the nested list: ≢¨∘⌽: The lengths of each run, reversed, : the current value, ⊃¨: and the first value in each run.
⍕¨: Format each value as a string.
: Join into a single string.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ ' '~⍨⍕∊⍕¨ for -3 \$\endgroup\$
    – Razetime
    Dec 3, 2021 at 9:56
2
\$\begingroup\$

Pari/GP, 89 bytes

f(n)=if(n,s=f(n-1);c=k=0;[if(c==d,k++,k&&s=Str(k,s,c);c=d;k=1)|d<-Vec(s)];Str(k,s,c),"1")

Try it online!

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

Python 2, 124 bytes

g=lambda s,c,t,l=0:t and(t[0]==s[:1]and g(s[1:],c,t,l+1)or g(s,`l`+c+t[0],s))or c
f=lambda n,s='1':n and f(n-1,g(s,s,s))or s

Try it online!

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

TypeScript Types, 302 271 bytes

//@ts-ignore
type I<S,D,T=S,N=[0]>=S extends `${D}${infer S}`?I<S,D,T,[...N,0]>:S extends`${infer C}${infer S}`?I<S,C,`${N["length"]}${T}${D}`>:`${N["length"]}${T}${D}`;type M<N,C=[],S="1">=N extends C["length"]?S:S extends `${infer A}${infer B}`?M<N,[...C,0],I<B,A,S>>:0

Try it online!

Ungolfed / Explanation

type Iterate<
  Str, // the remainder of the string
  Char, // the current char being counted
  Out = Str, // the output string being worked on
  Count = [0], // the current count of the characterChar
> =
  Str extends `${Char}${infer Rest}`
    // If Str starts with Char, add one to Count and continue
    ? Iterate<Rest, Char, Out, [...Count,0]>
    : Str extends`${infer NewChar}${infer Rest}`
          // Otherwise, if Str is non-empty, add Count and Char to Out, reset Count, and continue
      ? Iterate<Rest, NewChar, `${Count["length"]}${Out}${Char}`>
      // Otherwise, add Count and Char to Out and return it
      :`${Count["length"]}${Out}${Char}`

type Main<
  N, // the inputted number
  Counter = [], // how many times the string has been operated on
  Str = "1", // the current string
> =
  N extends Counter["length"]
    // If N == Counter, return Str
    ? Str
    // Otherwise, iterate on Str
    : Str extends `${infer FirstChar}${infer Tail}` ? Main<N, [...Counter,0], Iterate<Tail, FirstChar, Str>> : never
\$\endgroup\$
2
\$\begingroup\$

Jelly, 15 bytes

1ŒrZṚU1¦$jƲDFƊ¡

Try It Online!

fixed for +3 bytes thanks to Unrelated String, and I can't be bothered to golf or re-explain it anymore

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

Pip, 24 bytes

LaLR`(.)\1*`ooPU#$0PB$1o

0-indexed. Try it online!

Explanation

LaLR`(.)\1*`ooPU#$0PB$1o
                          a is command-line arg; o is 1 (implicit)
La                        Loop a times:
  LR`      `               Loop over each regex match of
     (.)                    a character
        \1*                 followed by the same character 0 or more times
            o              in o:
             oPU            Push to the front of o
                #$0         the number of characters in the match
                   PB       and push to the back of o
                     $1     the first character in the match
                       o  After the loop, output the final value of o
\$\endgroup\$
1
\$\begingroup\$

Jelly, 15 bytes

ŒrZU2¦ṚżWDF
1Ç¡

Attempt This Online!

Explanation:

ŒrZU2¦ṚżWDF  inner link

Œr           run-length encode (list of pairs of [element, frequency])
  Z          zip (produces [[list of elements], [list of corresponding frequencies]])
   U2¦       reverse the second element
      Ṛ      flat-reverse (changes to [list of corresponding frequencies], [list of elements])
       żW    interleave with the input, producing [[[elements], [input]], [frequencies]]
                NB: due to a bit of a quirk with Jelly's interleave function and vectorisation,
                    this makes [[a, b], c] not [a, b, c] as one would expect
         D   get digits of each item (in case an item has >=10 consecutive occurrences)
          F  flatten (smooths out both the oddity with interleave, and flattens the lists of digits)

1Ç¡          main link

1            starting with 1,
  ¡          repeatedly apply
 Ç           the above link

A naïve translation of the question description

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

Charcoal, 47 bytes

≔1ηFN«≔⟦⟧υUMη⊞Oυ⎇∧λ⁼κ§η⊖λ⁺⊟υκκ≔⁺⁺⭆⮌υLκη⭆υ§κ⁰η»η

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

≔1η

Start with the string 1.

FN«

Repeat n times.

≔⟦⟧υ

Start collecting runs of digits.

UMη⊞Oυ⎇∧λ⁼κ§η⊖λ⁺⊟υκκ

For each digit, push a new run if the digit differs but concatenate it to the last run if it's the same.

≔⁺⁺⭆⮌υLκη⭆υ§κ⁰η

Get the run lengths in reverse order, concatenate that with the previous string, and finally append just the digits without repeats.

»η

Output the final string.

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

Python3, 162 bytes:

from itertools import*
lambda n,c=['1']:c if n<2 else f(n-1,c+[''.join((k:=[*zip(*[(a,str(len([*b])))for a,b in groupby(c[-1])])])[1][::-1])+c[-1]+''.join(k[0])])

Try it online

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

Burlesque, 19 bytes

1{XXf:([-)scFLim}C~

Try it online!

1        # Needed by C~
{
 XX      # Explode to digits
 f:      # Count frequencies
 ([-)sc  # Sort by comparing the digit (tail)
 FLim    # Flatten and implode back to number
}C~      # Continue forever
\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 73 bytes

!n=n<2 ? "1" : (s=!~-n;replace(s,r"(.)\1*"=>m->s="$(length(m))$s"m[1]);s)

Try it online!

Similar to Arnauld's JS answer

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

R, 91 90 bytes

Or R>=4.1, 83 bytes by replacing the word function with \.

function(n,s=49){while(n<-n-1)s=c(unlist(Map(utf8ToInt,c(rev((r=rle(s))$l),""))),s,r$v);s}

Try it online!

Outputs a vector of character codes for the digits. Add 3 bytes (-48 at the end) for vector of digits.

See also @Dominic van Essen's (shorter) solution.

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

R, 88 87 83 bytes

Edit: thanks to pajonk for bug-spotting and then for -4 bytes!

g=function(n,x="1")`if`(n,g(n-1,unlist(strsplit(c(rev((y=rle(x))$l),x,y$v),""))),x)

Try it online!

Recursive + character-based alternative to pajonk's iterative R approach using ASCII codes.

Each recursive call gets the lengths & values of the run-length encoding (rle), splits any multi-digit lengths into individual characters (unlist(strsplit(...,""))), before wrapping these around the last previous iteration.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ This doesn't split to single digits as required Try it online! if you're returning a list of digits, make sure that these multi-digit numbers have been split into single digit numbers \$\endgroup\$
    – pajonk
    Dec 3, 2021 at 14:15
  • 1
    \$\begingroup\$ @pajonk - Thanks! I stupidly posted one of my trial attempts (with the digit-splitting applied to the wrong bit of the sandwich). Fixed now (I think...). \$\endgroup\$ Dec 3, 2021 at 16:35
  • 1
    \$\begingroup\$ -4 \$\endgroup\$
    – pajonk
    Dec 3, 2021 at 21:04
  • \$\begingroup\$ @pajonk: Thanks again! \$\endgroup\$ Dec 3, 2021 at 23:35
0
\$\begingroup\$

Japt, 22 bytes

_+ó¥ ÕÎ iZó¥ cʬw}g'1q

Try it

_...}g'1q  - run f(Z) input times starting with ["1"]

+     - append to Z:
ó¥ ÕÎ   * first column of Z splitted on different char
i     - then prepend:
Zó¥ cʬw * lengths reversed
\$\endgroup\$

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.