15
\$\begingroup\$

Given a ragged list of positive integers return a full cycle of recursive rotations starting with the unchanged input and ending with the state immediately before revisiting the initial state.

Examples:

[[2,3],4,5,5] -> [[2,3],4,5,5] , [4,5,5,[3,2]] , [5,5,[2,3],4] , [5,[3,2],4,5]

[1,10,[2,2,4],6,[[5,6],7],1] -> [1,10,[2,2,4],6,[[5,6],7],1] , [10,[2,4,2],6,[7,[6,5]],1,1] , [[4,2,2],6,[[5,6],7],1,1,10] , [6,[7,[6,5]],1,1,10,[2,2,4]] , [[[5,6],7],1,1,10,[2,4,2],6] , [1,1,10,[4,2,2],6,[7,[6,5]]]

[[5,6],[6,5]] -> [[5,6],[6,5]]

[1,[2,3,4,5,6],[7,8]] -> [1,[2,3,4,5,6],[7,8]] , [[3,4,5,6,2],[8,7],1] , [[7,8],1,[4,5,6,2,3]] , [1,[5,6,2,3,4],[8,7]] , [[6,2,3,4,5],[7,8],1] , [[8,7],1,[2,3,4,5,6]] , [1,[3,4,5,6,2],[7,8]] , [[4,5,6,2,3],[8,7],1] , [[7,8],1,[5,6,2,3,4]] , [1,[6,2,3,4,5],[8,7]] , [[2,3,4,5,6],[7,8],1] , [[8,7],1,[3,4,5,6,2]] , [1,[4,5,6,2,3],[7,8]] , [[5,6,2,3,4],[8,7],1] , [[7,8],1,[6,2,3,4,5]] , [1,[2,3,4,5,6],[8,7]] , [[3,4,5,6,2],[7,8],1] , [[8,7],1,[4,5,6,2,3]] , [1,[5,6,2,3,4],[7,8]] , [[6,2,3,4,5],[8,7],1] , [[7,8],1,[2,3,4,5,6]] , [1,[3,4,5,6,2],[8,7]] , [[4,5,6,2,3],[7,8],1] , [[8,7],1,[5,6,2,3,4]] , [1,[6,2,3,4,5],[7,8]] , [[2,3,4,5,6],[8,7],1] , [[7,8],1,[3,4,5,6,2]] , [1,[4,5,6,2,3],[8,7]] , [[5,6,2,3,4],[7,8],1] , [[8,7],1,[6,2,3,4,5]]

Rules:

Direction of rotation is your choice but must be consistent across layers.

You must start with the initial state and stop immediately before it reappears.

States are completely determined by their values, cf. example 3 to see what I mean by that.

Destroying the input is ok but different iterations cannot be the same object (if that makes any sense in your language - me only speak Python).

Other than the above standard code golf loopholes and I/O apply.

Promises:

Lists and sublists will be nonempty and finite as will be the nesting.

Scoring:

Code golf: shortest in bytes per language wins.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ May we output in reverse order? \$\endgroup\$
    – att
    Commented Mar 16, 2022 at 6:15
  • \$\begingroup\$ @att you may choose the direction of rotation but you must start with the initial state and terminate before it reappars. \$\endgroup\$
    – loopy walt
    Commented Mar 16, 2022 at 6:22
  • \$\begingroup\$ May we assume that every depth of a list contains at least two elements? \$\endgroup\$
    – pajonk
    Commented Mar 16, 2022 at 7:22
  • \$\begingroup\$ @pajonk I lean towards saying no to that. One: yes. Two: no. \$\endgroup\$
    – loopy walt
    Commented Mar 16, 2022 at 7:27
  • \$\begingroup\$ Could you add a test case where an inner list is larger than the outer list (e.g. [1,[2,3,4,5,6],[7,8]])? And I assume this would result in this (30 steps, too many for this comment)? \$\endgroup\$ Commented Mar 16, 2022 at 8:44

13 Answers 13

6
\$\begingroup\$

Wolfram Language (Mathematica), 52 bytes

If[#!=##2,#0[Map[RotateLeft,#,{0,-2}],##2,#],{##2}]&

Try it online!

Uses an approach from this answer to RotateLeft on every level.


If the initial state can be last instead, 48 bytes:

If[#!=##2,Map[RotateLeft,#,{0,-2}]~#0~##,{##2}]&

Try it online!

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

K (ngn/k), 23 bytes

{(`i>@x)(o',/|0 1_)/x}\

Try it online!

{(`i>@x)(o',/|0 1_)/x}\    Iterate and collect until it returns to the input...
 (`i>@x)(         )/x        Apply once if x is not an integer atom...
         o',/|0 1_             Rotate once and apply recursively to each item

Not quite sure if I can circumvent the explicit type checking.

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

Ruby, 69 bytes

r=->l{l*0==0?l:l.rotate.map(&r)}
f=->l,x=l{l!=r[x]?[x]+f[l,r[x]]:[x]}

Try it online!

r => rotate ragged list
l*0==0?l
If input is a value return it.
Else is an array, so rotate and map by r.

f => recursively build an array of the steps.

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

R, 124 115 112 101 bytes

r=\(l)"if"(is.list(l),Map(r,c(l[-1],l[1])),l)
`+`=list
f=\(l,a=+l,b=r(l))"if"(+b%in%a,a,f(b,c(a,+b)))

Attempt This Online!

-12 bytes thanks to Dominic van Essen. -11 bytes thanks to pajonk.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Nice! You can save a byte by re-assigning list, and don't forget about Map... Also, do you actually need the any()? \$\endgroup\$ Commented Mar 17, 2022 at 10:10
  • \$\begingroup\$ @DominicvanEssen I really have to get it through my head that Map is the same as lapply. The any is a relic from an older version (which didn't work, something like any(sapply(a,identical,b))) before I corrected it to list(b)%in%a. \$\endgroup\$
    – Giuseppe
    Commented Mar 17, 2022 at 11:14
  • 1
    \$\begingroup\$ I think you can still get 3 bytes less if you re-assign to + instead, and then get rid of el... \$\endgroup\$ Commented Mar 17, 2022 at 13:03
  • \$\begingroup\$ @DominicvanEssen you're quite right. Didn't even think of that (obviously) \$\endgroup\$
    – Giuseppe
    Commented Mar 17, 2022 at 13:18
  • 1
    \$\begingroup\$ You may want to shorten your r: ato.pxeger.com/… TBH I got just this part for this challenge and didn't make it for the second part :) \$\endgroup\$
    – pajonk
    Commented Mar 18, 2022 at 13:28
4
\$\begingroup\$

Vyxal, 16 15 10 bytes

≬Iȧ[vxǓ]İǔ

Try it Online!

All because there's a bug with ǔ and nested lists. Gotta love bug fixes.

Explained

≬Iȧ[vxǓ]İǔ
≬       İ    # Apply the following on the input while the result is unique, collecting iterations:
 Iȧ          #   Either push lambda arugment spaces or split a list into two halves. Then remove all whitespace.
   [   ]     #   If that's truthy (that is, the item is a list):
    vx       #    Apply this lambda to each item recursively
      Ǔ      #    And rotate the result of that left once
        ǔ    # Rotate the resulting list right
\$\endgroup\$
1
  • \$\begingroup\$ Uh, why the semicolon? Also, how does that not cause a parsing error? \$\endgroup\$
    – emanresu A
    Commented Mar 17, 2022 at 1:34
3
\$\begingroup\$

05AB1E, 25 bytes

[="ИÊi®δ.V}DdiëÀ"©.VDIQ#

Outputs the states each on a separated newline.

Try it online or verify all test cases.

Explanation:

Yet another 05AB1E monstrosity..

[              # Loop indefinitely:
 =             #  Print the current list with trailing newline (without popping)
               #  (which will be the implicit input-list in the first iteration)
  "..."        #  Create the recursive-string explained below
       ©       #  Store it in variable `®` (without popping)
        .V     #  Evaluate and execute it as 05AB1E code
          DIQ  #  If it's now equal to the input:
             # #   Stop the infinite loop
               #
Ð              # Triplicate the current list/item
 ˜             # Flatten the top copy
  Êi           # If the top two lists are NOT equal (so there is an inner list):
     δ         #  Map over each inner item:
    ® .V       #   Do a recursive call
   }           # After the if-statement, whether we've executed it or not
    Ddië       # If the current item is NOT an integer (so it's a list):
               # (necessary to prevent rotation on multi-digit integers)
        À      #  Rotate this list once towards the left
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 42 bytes

⊞υθFυFΦι⁺κ⟦⟧⊞υκW¬⁼θω«≔∨ω×¹θω⟦⭆¹θ⟧FυUMκ§κ⊕μ

Try it online! Link is to verbose version of code. Would save 1 byte if the initial state could be last instead. Explanation:

⊞υθFυFΦι⁺κ⟦⟧⊞υκ

Collect the list and all of the sublists.

W¬⁼θω«

Repeat until the current value equals the original value.

≔∨ω×¹θω

Actually save a clone of the original value the first time through the loop, so that the above comparison fails to start with and then succeeds when the original value returns.

⟦⭆¹θ⟧

Pretty-print the list, since Charcoal's default list output format doesn't suit ragged lists.

FυUMκ§κ⊕μ

Rotate the list and all of its sublists.

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

Jelly, 9 bytes

ṙ1ßI¡€
ÇƬ

A monadic Link that accepts a ragged list of numbers and yields the recursivesly rotated states in a list.

Try it online!

Note that this still works if ragged lists and their sublists may be empty.

How

ṙ1ßI¡€ - Helper Link, one recursive rotation: ragged list of numbers A
ṙ1     - rotate A left by one
     € - for each element:
    ¡  -   repeat... (utilised as an if statement, as described below)
   I   -   ...number of times: forward differences
                               given either a number or a list containing up to one
                                 number and nothing else we get an empty list which
                                 is falsey, so we don't do the "action"
                               given any other list get a non-empty list
                                 which is truthy, so we do the "action" once
  ß    -   ...action: call this Link (with the element)

ÇƬ - Main Link: ragged list of numbers, R
 Ƭ - start with R and collect inputs up while distinct applying:
Ç  -   call the last Link (our helper) as a monad - f(current)
\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 73 bytes

a->b=a;until(a==b=t(b),print(b))
t(a)=if(#a',[t(a[i%#a+1])|i<-[1..#a]],a)

Attempt This Online!

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

Javascript, 110 Bytes

Solution

    j=JSON.stringify
    f=x=>-x+x?[...x.slice(1),x[0]].map(f):x
    g=(x,y=[])=>y.includes(j(x))?y+"":g(f(x),[...y,j(x)])

Explanation

    j=JSON.stringify 
    f=x=>
      -x+x                     // If x is a number, then -x+x is 0 (i.e.
                               // falsey), but if x is an array, then -x+x is
                               // a non-empty string (i.e. truthy)

        ? [...x.slice(1),x[0]].map(f) // Rotate array and recurse if x is an
                                      // array
        :x                     // return as is otherwise

    g=(x,y=[])=>
      y.includes(j(x))          // Stop when y includes current array
        ? y+""                  // Equivalent to y.join(",")
        : g(f(x),[...y,j(x)])   // Recurse

Tests

// 110 Bytes, solution in g(x)

j=JSON.stringify
f=x=>-x+x?[...x.slice(1),x[0]].map(f):x
g=(x,y=[])=>y.includes(j(x))?y+"":g(f(x),[...y,j(x)])

// Test Cases

input1 = [[2,3],4,5,5]
input2 = [1,10,[2,2,4],6,[[5,6],7],1]
input3 = [[5,6],[6,5]]
input4 = [1,[2,3,4,5,6],[7,8]]

console.log(g(input1))
console.log(g(input2))
console.log(g(input3))
console.log(g(input4))

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

Factor + math.unicode, 80 bytes

[ dup '[ dup . [ dup array? [ 1 rotate ] when ] deep-map dup _ ≠ ] loop drop ]

Try it online!

The key to this is the deep-map combinator which is like map except instead of acting on the surface elements of a sequence, it uses a depth-first search algorithm to perform the mapping. We need to check if the element is a list and only perform the rotation if so (since rotating an atom causes an error).

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

Python3, 124 bytes:

f=lambda x:x if int==type(x)else(j:=[f(i)for i in x])[1:]+j[:1]
g=lambda x,c=0:[x]+([]if(y:=f(x))==(c or x)else g(y,c or x))

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 116 bytes (took out test suite because the link was too long, but it worked when I ran it.) \$\endgroup\$
    – Aiden Chow
    Commented Mar 17, 2022 at 0:23
  • \$\begingroup\$ 109 bytes \$\endgroup\$
    – Aiden Chow
    Commented Mar 17, 2022 at 1:03
  • \$\begingroup\$ 104 bytes \$\endgroup\$
    – Aiden Chow
    Commented Mar 17, 2022 at 2:28
1
\$\begingroup\$

Python 3, 81 bytes

Your OP's reference implementation

f=lambda L,*t:t*(L in t)or f(g(L),*t,L)
g=lambda L:L*-1*-1or[*map(g,L[1:]+L[:1])]

Try it online!

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