30
\$\begingroup\$

The look-say sequence is a sequence of lists of numbers where each element is the previous element with run length encoding. Run length encoding is the process of grouping together like elements and then giving the element and the size of the group for each group. So for example:

1 1 1 2 2 1

To run length encode this we group like elements together

1 1 1 | 2 2 | 1

And then replace each group with its size and the element:

3 1 | 2 2 | 1 1

Then we concatenate these back together:

3 1 2 2 1 1

The look-say sequence starting from just 1 goes:

1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1
...

But we can start with different values. For example we could start with 2

2
1 2
1 1 1 2
3 1 1 2
1 3 2 1 1 2
1 1 1 3 1 2 2 1 1 2
3 1 1 3 1 1 2 2 2 1 1 2
1 3 2 1 1 3 2 1 3 2 2 1 1 2
1 1 1 3 1 2 2 1 1 3 1 2 1 1 1 3 2 2 2 1 1 2

Or we could even start it with 3 3 3:

3 3 3
3 3
2 3
1 2 1 3
1 1 1 2 1 1 1 3
3 1 1 2 3 1 1 3
1 3 2 1 1 2 1 3 2 1 1 3
1 1 1 3 1 2 2 1 1 2 1 1 1 3 1 2 2 1 1 3

In this task you are going to be given a sequence and your job will be to trace it back as far as you can to get a starting point. That is you are going to undo operations until you get a list of numbers that could not have been produced by run length encoding another list.

As some examples:

  • 3 3 3 is not a possible run length encoding since it has an odd number of terms.
  • 1 2 2 2 is not a possible run length encoding since expanding it out gives 2 2 2 which would be encoded as 3 2 instead.

As input you will receive a list of positive integers less than 4. You should output all the terms of the look-say sequence up to and including the input. Your output may be in forwards or backwards order.

There is one case where the input can be traced back indefinitely 2 2. What your program does on this input is undefined behavior.

This is the goal is to minimize the size of your source code as measured in bytes.

Test cases

1:
1

1 1 1 2 1 1 1 3:
3 3 3
3 3
2 3
1 2 1 3
1 1 1 2 1 1 1 3

1 2 2 1 1 3 1 1 1 2:
1 2 2 2
1 1 3 2
2 1 1 3 1 2
1 2 2 1 1 3 1 1 1 2

1 2 1 3 1 2 1 1:
3 3 3 1 1 1
3 3 3 1
3 3 1 1
2 3 2 1
1 2 1 3 1 2 1 1
\$\endgroup\$
5
  • \$\begingroup\$ Closely related \$\endgroup\$
    – emanresu A
    Oct 27, 2022 at 19:19
  • \$\begingroup\$ Shouldn't there be one additional step in your last test case? I mean 3 3 3 1 1 1 can still become 3 3 3 1 1 1 1 right? \$\endgroup\$
    – JvdV
    Oct 28, 2022 at 11:06
  • 1
    \$\begingroup\$ @JvdV - look at the second example after 'As some examples' in the description. \$\endgroup\$ Oct 28, 2022 at 11:28
  • 1
    \$\begingroup\$ @JvdV To maybe clarify it a bit: if the current list is \$L\$, we first determine it's run-length decoded list \$L_d\$. If we run-length encode this decoded list (\$L_e(L_d)\$) and it's equal to the original list (\$L==L_e(L_d)\$), we'll continue with the decoded list in the next iteration: \$L=L_d\$. If this was not the case (\$L\neq L_e(L_d)\$), the loop stops. E.g. 1) \$L=[1×2,1×3,1×2,1×1]\$ → \$L_d=[2,3,2,1]\$ → \$L_e(L_d)=[1×2,1×3,1×2,1×1]\$ → \$L==L_e(L_d)\$ → continue (\$L=L_d\$). 2) \$L=[3×3,3×1,1×1]\$ → \$L_d=[3,3,3,1,1,1,1]\$ → \$L_e(L_d)=[3×3,4×1]\$ → \$L\neq L_e(L_d)\$ → stop. \$\endgroup\$ Oct 28, 2022 at 11:50
  • 1
    \$\begingroup\$ @KevinCruijssen, I got it. Thanks for that clarification! Helps a lot. \$\endgroup\$
    – JvdV
    Oct 28, 2022 at 12:00

17 Answers 17

7
\$\begingroup\$

Pyth, 19 16 bytes

-3 bytes thanks to Mukundan314

W.A.+%2t
Q=r9cQ2

Try it online!

Prints in reverse order.

Explanation

W                   while:
 .A                    zero is not in
   .+                  the deltas of
     %2tQ              every second element of implicitly printed Q
          =r9cQ2    set Q to the length decoding of itself
\$\endgroup\$
4
  • 1
    \$\begingroup\$ why does this break on 3 3 3? It works correctly, but I don't see how it's meeting the condition "zero in deltas of every second element of Q," since we have only 1 second element in that case. Are you looking at all pairs with distance two apart? \$\endgroup\$
    – Jonah
    Oct 27, 2022 at 22:28
  • 3
    \$\begingroup\$ @Jonah It isn't breaking with the "if" in that case. The length decoding is erroring, which breaks the # loop. \$\endgroup\$ Oct 27, 2022 at 23:09
  • \$\begingroup\$ 16 bytes \$\endgroup\$ Oct 31, 2022 at 4:00
  • \$\begingroup\$ @Mukundan314 personally I find .A to be cleaner than *F but that's just me. Nice shaves, moving the print inside the conditional is smart. \$\endgroup\$ Oct 31, 2022 at 15:59
6
\$\begingroup\$

Excel (ms365), 374 bytes

enter image description here enter image description here enter image description here

Formula in A3:

=LET(x,CONCAT(1:1),y,TOCOL(SCAN(x,SEQUENCE(1048575),LAMBDA(a,b,LET(c,SEQUENCE(LEN(a)/2,,,2),IF(ISODD(LEN(a)),NA(),CONCAT(REPT(MID(a,c+1,1),MID(a,c,1))))))),3),z,MAP(y,LAMBDA(d,LET(e,SEQUENCE(LEN(d)),f,MID(d,e,1),g,TEXTSPLIT(CONCAT(f&IF(f<>MID(d,e+1,1),"|","")),"|",,1),CONCAT(LEN(g)&LEFT(g))))),MID(FILTER(VSTACK(x,y),VSTACK(1,z=VSTACK(x,DROP(y,-1)))),SEQUENCE(1,LEN(x)),1))

All one has to do is change the input in 1st row.

  • 'x-varibale' - CONCAT(1:1) - Concatenate all values from row 1 into a string;
  • 'y-variable' - TOCOL(SCAN(x,SEQUENCE(1048575),LAMBDA(a,b,LET(c,SEQUENCE(LEN(a)/2,,,2),IF(ISODD(LEN(a)),NA(),CONCAT(REPT(MID(a,c+1,1),MID(a,c,1))))))),3) - Will go over 1048575 possibilities (max rows in ms365 if one include the input at the end) and will get each number from every even position and repeat it n-times where n == its neighboring digit on the left;
  • 'z-variable' - MAP(y,LAMBDA(d,LET(e,SEQUENCE(LEN(d)),f,MID(d,e,1),g,TEXTSPLIT(CONCAT(f&IF(f<>MID(d,e+1,1),"|","")),"|",,1),CONCAT(LEN(g)&LEFT(g))))) - Loop over elements from y and reverse it's value into it's logical predecessor;
  • MID(FILTER(VSTACK(x,y),VSTACK(1,z=VSTACK(x,DROP(y,-1)))),SEQUENCE(1,LEN(x)),1) - Finally we can check each value against the elements in y and filter what is not a possible run length encoding string. All strings are then cut into seperate integers again.

No doubt other Excel-fanatics can beat this, but my brain is fried! I'm not even sure an answer like this length belongs on CG...

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

Pip -p, 33 bytes

T$|_=BMPDQUWg|%#gg:_@1RL@_MF<>Pgg

Takes the initial sequence as separate command-line arguments; prints the sequences from there on back as far as possible to stdout as lists. Try It Online!

Explanation

The basic structure of the program is

T <cond> <body> g

that is, loop until <cond> becomes true, executing <body> each time, and at the end of the loop, output the final value of g. (The original value of g is a list of the command-line arguments.)

The condition is:

$|_=BMPDQUWg|%#g
         UWg      Unweave g into two lists, each containing every other value
       DQ         Get the latter of the two (the values at odd indices)
     MP           Map this function to each adjacent pair of values in that list:
  _=B               The first equals the second
$|                Fold on logical OR: true if any of the equality checks are true
            |     OR:
              #g  The length of g
             %    Is odd

The loop body is:

g:_@1RL@_MF<>Pg
             Pg  Print the current value of g
           <>    Group into chunks of length 2
         MF      Map this function to each chunk and flatten the resulting list:
       @_          The first number in the chunk
     RL            Create a list containing that many copies of
  _@1              The second number in the chunk
g:               Assign the resulting list back to g
\$\endgroup\$
2
  • \$\begingroup\$ Just an headsup but the link showed an error for me. Is that something on my end maybe? \$\endgroup\$
    – JvdV
    Oct 28, 2022 at 11:22
  • \$\begingroup\$ @JvdV It works fine for me, so it's probably something on your end, yes. I know with DSO, you do have to wait for it to finish loading everything before you click Run (you can tell when it's ready because the spinning gear icon next to "Select language" goes away). It's also possible there was an error while loading the interpreter. DSO runs on the client side, so if your computer can't access GitHub, I think that would prevent it from loading correctly. \$\endgroup\$
    – DLosc
    Oct 28, 2022 at 15:38
3
\$\begingroup\$

MATL, 18 17 bytes

This uses CursorCoercer's idea of testing if increments are zero.

The output is in backwards order.

`t0h2L&)Y"6Mdyh]x

Verify test cases: 1, 2, 3, 4.

Explanation

`         % Do... while
  t       %   Duplicate current list of numbers (*). This takes input implicitly in
          %   the first iteration
  0h      %   Append a 0
  2L&)    %   Push the subarray of entries at (1-based) even positions (**), then
          %   the subarray of entries at odd positions (***)
  Y"      %   Run-length decoding using those two subarrays as inputs, cyclically
          %   reusing the shorter of the two if needed. The result will contain
          %   zeros if and only if (*) had odd length
  6M      %   Push (**) again
  d       %   Consecutive differences
  y       %   Duplicate from below: pushes again the result of run-length decoding 
  h       %   Concatenate horizontally
]         % End. A new iteration is run of the top of the stack contains no zeros
x         % Delete. This removes the last array, which is not valid. Implicit display
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES10), 91 bytes

Inspired by CursorCoercer's answer.

f=a=>[...a.every((v,i)=>a[i%2-~i]^i%2*v)?f(a.flatMap((v,i)=>Array(i&1&&p).fill(p=v))):[],a]

Try it online!

Commented

Testing if a[] is still valid:

a.every((v, i) =>   // for each value v at position i in a[]:
  a[i % 2 - ~i]     //   get a[i + 1] if i is even, or a[i + 2] if i is odd
  ^                 //   and make sure it's different from
  i % 2 * v         //   0 (or undefined) if i is even, or v if i is odd
)                   // end of every()

Run-length decoding of a[]:

a.flatMap((v, i) => // for each value v at position i in a[]:
  Array(i & 1 && p) //   build an array of p entries if i is odd,
                    //   or an empty array if i is even
  .fill(p = v)      //   fill it with v and copy v to p
)                   // end of flatMap()

JavaScript (ES6), 91 bytes

A version without .flatMap().

f=a=>[...a.every((v,i)=>a[j=i%2,b.push(...Array(j&&p).fill(p=v)),j-~i]^j*v,b=[])?f(b):[],a]

Try it online!

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

R, 70 69 bytes

Edit: -1 byte thanks to pajonk

f=function(v)if(all(w<-c(print(v),0)[!1:0],diff(w)))f(rep(w,v[!0:1]))

Try it online!

f=function(v,                       # f is recursive function with arg vector v;
                 print(v)           #   first print v
             w=c(          )[!1:0]) #   and set w to every second element of v,
                         ,0         #   followed by a zero if length is odd.
if(              )                  # now, check if v is valid:
   all(w,       )                   #   there shouldn't be a final zero
         diff(w)                    #   and every second element should be different to its neighbour
                  f(              ) # if so, recurse
                    rep(w,v[!0:1])  #   with even numbered elemnts of v
                                    #   repeated odd numbered elements of v times
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think 3 3 3 1 1 1 is the correct endpoint (see the last test case), because 3 3 3 1 1 1 1 should be look-said as 3 3 4 1, so there isn't a valid sequence that'd be look-said as 3 3 3 1 1 1. \$\endgroup\$ Oct 28, 2022 at 11:25
  • \$\begingroup\$ -1 byte \$\endgroup\$
    – pajonk
    Oct 28, 2022 at 11:59
2
\$\begingroup\$

05AB1E, 17 15 bytes

[=ιÂ`ÅΓ©Åγ‚RÊ#®

Outputs in 'reversed' order compared to the challenge description.

Try it online or verify all test cases.

Explanation:

I basically run-length decode and then encode it again, and see if it's unchanged.

[         # Start an infinite loop:
 =        #  Print the current list with trailing newline (without popping)
          #  (which will be the implicit input-list in the first iteration)
  ι       #  Uninterleave the copy into 2 parts: [lengths,values]
   Â      #  Bifurcate (short for Duplicate & Reverse copy) this pair of lists
    `     #  Pop and push the reversed pair of lists to the stack
     ÅΓ   #  Pop both the values & length lists, and run-length decode them
       ©  #  Store this list in variable `®` (without popping)
   Åγ     #  Run-length encode it again, pushing the list of values and lengths
          #  separated to the stack
     ‚R   #  Pair them together in reversed order: [lengths,values]
   Ê      #  If the two pairs of lists are NOT the same:
    #     #   Stop the infinite loop
 ®        #  (else) Push the list of variable `®` for the next iteration
    
\$\endgroup\$
0
2
\$\begingroup\$

Pyth, 13 bytes

Wq
Qsr8=r9cQ2

Try it online!

Explanation

Q is initialized to input

Wq\nQsr8=r9cQ2
W              # while
  \nQ          #   print(Q)
 q             #     ==
     sr8=r9cQ2 #   run_length_encode(Q = run_length_decode(Q)):
               #  pass
\$\endgroup\$
2
\$\begingroup\$

Japt, 28 bytes

OpU;Êv ©Uó Ìän e ©ßUò crÈo{Y

Try it

I imagine there's room for improvement. Outputs in "reverse" order.

Explanation:

OpU;Êv ©Uó Ìän e ©ßUò crÈo{Y
OpU;                         # Print the input followed by a newline
    Ê                        # The length of the input
     v                       # Is divisible by 2
       ©                     # Break if false
        Uó                   # Separate the input into "sizes" and "elements"
           Ì                 # Take just the array of elements
            än               # Calculate the consecutive differences
               e             # Check that they are all non-zero
                 ©           # Break if false
                  ß          # Otherwise repeat the program with new input:
                   Uò        #  Split the current input into size,element pairs
                      cr     #  Run the following on each pair, then flatten:
                        Èo   #   An array with length equal to the first number
                          {Y #   Where each element is the second number

I've made an alternative which builds an array instead of printing in each loop, but it's currently longer.

\$\endgroup\$
1
  • \$\begingroup\$ Oh, we can definitely do better than this! And, just as soon as I figure out the challenge, I'll be back to help you! Straight away, though, the OpU is annoying me; we should be able to ditch that and build an array instead. \$\endgroup\$
    – Shaggy
    Oct 28, 2022 at 22:52
1
\$\begingroup\$

Charcoal, 42 bytes

W∧⊞Oυθ¬∨﹪Lθ²⊙✂θ³Lθ²⁼κ§θ⊕⊗λ≔ΣE⪪θ²⁺⊟κE⊟κ⁰θIυ

Attempt This Online! Link is to verbose version of code. Outputs the lists in reverse order; each element is printed on its own line and lists are double-spaced from each other. Explanation:

W∧⊞Oυθ¬∨

Push the current list to the predefined empty list, and while neither...

﹪Lθ²

... the length of the list is odd, nor...

⊙✂θ³Lθ²⁼κ§θ⊕⊗λ

... any of the third, fifth, seventh etc. entries equals the entry two previous, then...

≔ΣE⪪θ²⁺⊟κE⊟κ⁰θ

... run-length decode the list.

Iυ

Output all of the collected lists.

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

Haskell, 86 bytes

r!(a:b:t)|r==b=[0]|k<-b<$[1..a]=k++b!t
r![]=[]
r!x=[0]
g l|0`elem`0!l=[l]|1>0=l:g(0!l)

Try it online!

r!list compares r with element to replicate, if they are equal inserts a 0 in the resulting list, same does if it matches an odd list.

Function g repeatedly apply 0! and stops if there is a 0 in the result.

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

Ruby, 73 bytes

-15 bytes thanks to AZTECCO

F=->a,y=0{a.all?&&(p a)&&F[a.each_slice(2).flat_map{y!=_2&&[y=_2]*_1},y]}

Attempt This Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 73 bytes \$\endgroup\$
    – AZTECCO
    Oct 28, 2022 at 15:05
1
\$\begingroup\$

Jelly, 14 bytes

Ṅṭ2/Ḋm2IẠƲ¡Œṙß

A full program that accepts a list of integers from \$[1,4]\$ and prints the results in Jelly's list format separated by newlines.

Try it online!

How?

Inspired by CursorCoercer's Pyth answer.

Œṙ, run-length decode, will error if given a list of integers or a list containing a singleton list. The code ensures that if the current list identifies the same value to be repeated twice in a row then the former will be true and, otherwise, if the current list is of odd length when the latter will be true.

Ṅṭ2/Ḋm2IẠƲ¡Œṙß - Main Link: list of integers, S
Ṅ              - print S
          ¡    - repeat...
         Ʋ     - ...number of times: last four links as a monad:
    Ḋ          -                       dequeue
     m2        -                       modulo-two slice
       I       -                       deltas
        Ạ      -                       all non-zero?
  2/           - ...action: pairwise reduce by:
 ṭ             -              tack
           Œṙ  - run-length decode
             ß - call this link again with that as S
\$\endgroup\$
1
\$\begingroup\$

Python, 126 124 120 113 110 bytes

i=lambda t,x,a,b,*c:b and i(t&(b!=c[1]),x+(b,)*a,*c)or(x,a*t)
j=lambda l,t=1:t*[0]and j(*i(1,(),*l,1,0,0))+[l]

Attempt This Online!

The recursive function i simultaneously undoes the look-and-say sequence and also determines whether it's a valid sequence -- the last element of the return value is 1 if the sequence is valid and 0 if it's not.

This is then used in the main function j to undo the calculation until hitting a stopping point.

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

Raku, 60 bytes

{$_,*.flatmap(*Rxx*)...{$_%2|{any $_ Z==.skip}(.[1,3...*])}}

Try it online!

This is a lazily generated sequence of the form first-element, generator ... termination-condition.

  • The first element is $_, the list argument to the function.
  • *.flatmap(* Rxx *) takes the previous element and flatmaps over it two elements at a time using the anonymous function * Rxx *. Rxx is the Reversed version of the replication operator xx; it produces a number of copies of its right-hand side given by its left-hand side.
  • The termination condition is an anonymous function that returns true if $_ % 2--that is, if the number of elements in the last list is odd--or if .[1, 3 ... *], the odd-indexed elements of the last list, satisfies the condition any $_ Z== .skip--that is, if any two adjacent elements are equal.
\$\endgroup\$
1
\$\begingroup\$

Rust, 146 bytes

|a|while dbg!(&a).len()%2<1{let(c,mut r,mut p)=(a.chunks_exact(2),vec![],9);for
t in c{if p==t[1]{return}p=t[1];r.extend([p].repeat(t[0]));}*a=r;}

Playground

This is a fn(&mut Vec<usize>).

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

Python, 93 bytes

f=lambda a:(a,*(eval("0"+(l:=len(b:=a[1::2]))*"!=%d"%b)*a[~l:l]and f(eval(l*"+%d*(%d,)"%a))))

Attempt This Online!

Returns the history newest to oldest.

Python, 80 bytes

def f(a):print(a);f(eval(eval((l:=len(b:=a[1::2]))*".0!=%d"%b)*l*"+%d*(%d,)"%a))

Attempt This Online!

Prints the history line-by-line newest to oldest. Exits with an error.

How?

Nothing clever here. Using eval because control structures in general and in particular concatenation of a list of strings or pairwise iteration over a list or chained comparisons are all rather verbose when done "the proper way" in Python.

The second, semi-legal version does away with a few stop conditions (like odd number of terms) because the function crashes at the right time anyway when any of these conditions are met.

\$\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.