title: Totally Cubular

text:
# Question
Title: Totally Cubular
Create a program or function to unjumble a 9x9x9 cube of digits by rotating individual 3x3 cubes within it.

This is similar to (but, I suspect, a bit harder than) my Flippin' Squares question.

## Input

Input will be a 9x9x9 cube. I'm not going to be as strict over the input as I was last time, 3d arrays are allowed, arrays of strings are allowed, arrays of arrays of characters are allowed, etc.

I will be strict on **what** you can input into your program though - only the digits that make up the cube. No additional information like dimensions or anything else can be given as input.

Here is an example cube:

```
123456789   234567891   345678912
234567891   345678912   456789123
345678912   456789123   567891234
456789123   567891234   678912345
567891234   678912345   789123456
678912345   789123456   891234567
789123456   891234567   912345678
891234567   912345678   123456789
912345678   123456789   234567891

456789123   567891234   678912345
567891234   678912345   789123456
678912345   789123456   891234567
789123456   891234567   912345678
891234567   912345678   123456789
912345678   123456789   234567891
123456789   234567891   345678912
234567891   345678912   456789123
345678912   456789123   567891234

789123456   891234567   912345678
891234567   912345678   123456789
912345678   123456789   234567891
123456789   234567891   345678912
234567891   345678912   456789123
345678912   456789123   567891234
456789123   567891234   678912345
567891234   678912345   789123456
678912345   789123456   891234567

```

The 9x9 square in the top left is the cross-section of the bottom layer of the cube. The square in the top-middle is the next layer up, then the top-right, the middle-left and so on through to the bottom-right, which is the top layer.

This cube is the target state. As you can see the digits increase in the positive x, y and z directions, looping back to `1` when they pass `9`.

## Sub-cubes

You solve this puzzle by manipulating 3x3 sub-cubes within the main cube.
Each sub-cube is identified by the `X Y Z` position of its centre within the main cube. Because each sub-cube must be a 3x3 cube, `X`, `Y` and `Z` can only be between 1 and 7 (inclusive). Point `0 0 0` is at the back-bottom-left and the values increase to the right, upwards and toward the front.

Example sub-cubes from the target state (all other values set to `0` to highlight the cube in question):

```
1 1 1:

123000000   234000000   345000000
234000000   345000000   456000000
345000000   456000000   567000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

7 1 1:

000000789   000000891   000000912
000000891   000000912   000000123
000000912   000000123   000000234
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

1 7 1:

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

789000000   891000000   912000000
891000000   912000000   123000000
912000000   123000000   234000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

1 1 7:

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
789000000   891000000   912000000
891000000   912000000   123000000
912000000   123000000   234000000

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000
000000000   000000000   000000000

```

## Manipulation

Each move you make will be a rotation of one of the sub-cubes. You will be able to rotate a cube around any one of its axes; 1, 2 or 3 quarter turns.
Rotation will be specified by first naming the axis you wish to rotate around, then the number of quarter turns you wish to rotate.

Example rotations (using unique values for each item here to make the rotations more obvious):

```
ABC   JKL   STU
DEF   MNO   VWX
GHI   PQR   YZ*

X1

STU   VWX   YZ*
JKL   MNO   PQR
ABC   DEF   GHI

```

X rotations rotate towards the back (or anti-clockwise as viewed from the left-hand side).

```
ABC   JKL   STU
DEF   MNO   VWX
GHI   PQR   YZ*

Y1

CFI   LOR   UX*
BEH   KNQ   TWZ
ADG   JMP   SVY

```

Y rotations rotate anti-clockwise as viewed from above.

```
ABC   JKL   STU
DEF   MNO   VWX
GHI   PQR   YZ*

Z1

SJA   TKB   ULC
VMD   WNE   XOF
YPG   ZQH   *RI

```

Z rotations rotate anti-clockwise as viewed from the front.

## Output

Your output should be a list of moves required to take the given input back to the target state.
Each move should name the sub-cube and how it should be rotated:

```
111X1

Block at X=1, Y=1, Z=1, rotated 1 quarter turn around the X axis.

426Y3

Block at X=4, Y=2, Z=6, rotated 3 quarter turns around the Y axis.

789Z2

Block at X=7, Y=8, Z=9, rotated 2 quarter turn around the Z axis.

```

So an example output might be something like:

```
111X1
789Z2
426Y3

```

This is my preferred output - a list of newline separated moves where each line describes one move - and this is the kind of output my verification program will expect. That said, I'll be somewhat flexible on the output, so a long string of moves (for example) is okay (it'll just take me a little longer to verify).

I think this is probably enough of a challenge as it is, but let's make it just to spice it up a bit more.

## Utilities

This is a program that will generate a random scrambling of the cube. It outputs the scrambled cube, the sequence of moves that generated it and those moves reversed as a possible solution.
Alternatively, it has a function that will take a scrambled function and a sequence of moves as input and then verify that it returns the target cube.

The program, along with a couple of files containing a test input solution for verification, the target cube and a cube I used to test the rotate functions, can be found at: https://github.com/gazrogers/CodegolfCubularRandomiser

```
import random

target = [[['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8']], [['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8'], ['1', '2', '3', '4', '5', '6', '7', '8', '9']], [['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1']], [['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2']], [['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3']], [['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4']], [['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5']], [['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6']], [['9', '1', '2', '3', '4', '5', '6', '7', '8'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7']]]

# Because of how we read the data in,
# the first index into the 3D array is the y-index (bottom layer first, top layer last),
# then the z-index (back first, front last),
# then the x-index (left first, right last)
def getinput(filename):
    f = open(filename)
    string = f.read().split('\n\n')
    cube = '\n\n'.join(string[:-1])
    solution = string[-1]
    lists = [list(z) for y in [x.split('\n') for x in cube.split('\n\n')] for z in y]
    return [[lists[i:i + 9] for i in xrange(0, len(lists), 9)], solution]

def output(data):
    return '\n'.join([''.join(row) for layer in data for row in layer+[[]]])

def getsubcube(cube, x, y, z):
    x = clamp(x, 1, 7)
    y = clamp(y, 1, 7)
    z = clamp(z, 1, 7)
    return [[[char for char in row[x-1:x+2]] for row in layer[z-1:z+2]] for layer in cube[y-1:y+2]]

def replacesubcube(cube, subcube, x, y, z):
    newcube = cube
    for ypos in range(y-1, y+2):
        for zpos in range(z-1, z+2):
            for xpos in range(x-1, x+2):
                newcube[ypos][zpos][xpos] = subcube[ypos-y+1][zpos-z+1][xpos-x+1]
    return newcube

def clamp(n, minn, maxn):
    return max(min(n, maxn), minn)

def rotateX(cube, n):
    newcube = cube
    for _ in range(n):
        newcube = [
            [newcube[2][0], newcube[1][0], newcube[0][0]],
            [newcube[2][1], newcube[1][1], newcube[0][1]],
            [newcube[2][2], newcube[1][2], newcube[0][2]]
        ]
    return newcube

# algorithm shamelessly stolen from http://stackoverflow.com/a/496056/618347
def rotateY(cube, n):
    newcube = cube
    for _ in range(n):
        newcube = [zip(*x)[::-1] for x in newcube]
    return newcube

# Easier to define in terms of rotateX and rotateY
def rotateZ(cube, n):
    newcube = cube
    for _ in range(n):
        newcube = rotateY(rotateX(rotateY(newcube, 1), 3), 3)
    return newcube

def randomisecube(cube):
    newcube = cube
    generator = ""
    solution = ""
    funclist = [[rotateX, "X"], [rotateY, "Y"], [rotateZ, "Z"]]
    for _ in range(random.randint(10, 100)):
        x = random.randint(1, 7)
        y = random.randint(1, 7)
        z = random.randint(1, 7)
        rotateFunc = random.choice(funclist)
        numRots = random.randint(1,3)
        subcube = getsubcube(newcube, x, y, z)
        subcube = rotateFunc[0](subcube, numRots)
        newcube = replacesubcube(newcube, subcube, x, y, z)
        generator = generator + str(x) + str(y) + str(z) + rotateFunc[1] + str(numRots) + '\n'
        solution = str(x) + str(y) + str(z) + rotateFunc[1] + str(4-numRots) +'\n' + solution
    return [generator, solution, newcube]

def verifysoltuion(cube, solution):
    newcube = cube
    funclist = {"X": rotateX, "Y": rotateY, "Z": rotateZ}
    for move in solution.split('\n'):
        movelist = list(move)
        subcube = getsubcube(newcube, int(movelist[0]), int(movelist[1]), int(movelist[2]))
        subcube = funclist[movelist[3]](subcube, int(movelist[4]))
        newcube = replacesubcube(newcube, subcube, int(movelist[0]), int(movelist[1]), int(movelist[2]))
    return newcube == target

# Code to generaterandom cubes - Uncomment/Comment as necessary
# answer = randomisecube(target)
# print "Cube:"
# print output(answer[2])
# print "Generated by:"
# print answer[0]
# print "Possible solution:"
# print answer[1]

# Code to verify solution - Uncomment/Comment as necessary
[cube, solution] = getinput('testsolution.txt')
print verifysoltuion(cube, solution)

```

## Tests

These tests were generated by the above randomiser, and so were scrambled by at most 100 moves. Your solution can be as long as it needs to be, but maybe the 100 move limit will help optimise your solution?

Please provide the solutions to these 3 test input in your answer.

```
Test input 1:
123456789
234567891
345678912
456789123
789891234
876912567
452123456
891234345
912345678

234567343
567878432
494519521
389891234
678212563
787823898
876934747
932145456
143256789

367178219
656269321
585491432
473539887
567643478
841298787
999145658
341256567
569367891

671784748
589855639
476966521
932129776
343778327
234145696
583991565
492312891
121498912

782395434
678214325
219761216
121656732
654283676
147858989
454789143
543678762
432565123

893989123
767391214
188896395
932595488
823214582
982397151
323654737
456562673
567456234

782193876
843218765
952931654
145859915
954823491
165758963
212517631
567651264
678912345

893214987
936727876
145326765
234941691
365634212
476732473
565696714
678789145
789123456

912345678
121478789
232345891
321834912
474787123
585498214
678919195
789123456
891234567

Test input 2:
185636789
678739121
519278992
141447183
589128734
633462125
784723456
891234567
912345678

298549121
267393832
455767823
567871244
867759645
269367236
178936767
912349478
123474589

369458912
654952363
543641434
432916575
732127236
821952912
939567891
367876789
414545691

476757893
562797914
678584189
782123678
697416367
714369554
821896365
258525219
323656712

517897654
698914565
282863873
563618741
236599478
188638387
934513698
145691383
256345123

645954345
762323456
158232167
732595252
743256541
452348691
349698262
414719873
593828934

787489436
878954347
989147298
193981213
288582371
585432832
678817943
789923554
698734145

891298567
914981178
115494319
652149626
145671787
476352173
569121634
678732645
787643556

912345678
123452789
214265178
395226739
494989628
167211984
454915125
523121236
891234567

Test input 3:
123451989
234569191
345328252
456234741
237343128
126936765
713843412
828754587
912345678

234262871
367173982
623782193
512398873
571216319
277388484
619218545
986145456
126436789

567671782
178986783
955897676
544226619
969891856
881294145
592347934
153289345
235341671

678567523
745167854
363476523
465341976
168816567
979317432
524498132
452368119
355244782

789823434
654758929
914871838
846936797
967127256
828876952
652985148
586792767
257965893

678934345
712597456
163996745
967168692
823779385
784193941
565874315
476963894
345158234

789165456
895276195
214325294
891861983
936319871
125176912
454789123
367128954
691219765

891254367
912387678
345476589
932157991
143498162
276987493
789456912
678725843
745854654

912343278
123476589
456565491
123914312
234165123
567328234
678934321
767123432
856212543

```

# Answer
> 46 votes
# Rust, ~~38250~~ 14716 bytes

```
use std::{io::{stdin,Read},ops::{Add,Index,IndexMut,Sub},collections::HashSet,fmt::{self,Write}};use lazy_static::lazy_static;use regex::Regex;use tap::Tap;use hashbag::HashBag;trait Ta:l+Sized{fn V(&mut self,d(A,o,D):d){let mut ha=A;if A[o]>1{ha[o]-=1;}else{ha[o]+=1;}let Da=if o==c::X{c::Y}else{c::X};self.u(d(ha,o,D));self.u(d(A,Da,2));self.u(d(ha,o,-D));self.u(d(A,Da,2));self.u(d(A,o,-D));}fn Bb(&mut self,q:Vec<d>){for m in q{self.V(m);}}}impl<T:l>Ta for T{}trait l{fn get(&self,e:b)->B;fn K(&self,e:b)->B;fn u(&mut self,m:d);fn j(&self)->b;fn ia(&mut self,q:Vec<d>){for m in q{self.u(m);}}}impl<T:l+?Sized>l for&mut T{fn get(&self,e:b)->B{(**self).get(e)}fn K(&self,e:b)->B{(**self).K(e)}fn u(&mut self,m:d){(**self).u(m)}fn j(&self)->b{(**self).j()}}lazy_static!{static ref Ea:[[[B;9];9];9]={#[inline(never)]fn pa<F:Fn((u8,I))->T,I:Copy,T>(N:F)->impl Fn(I)->[T;9]{move|i|{[N((0,i)),N((1,i)),N((2,i)),N((3,i)),N((4,i)),N((5,i)),N((6,i)),N((7,i)),N((8,i)),]}}pa(pa(pa(|(x,(y,(z,_)))|B((x+y+z)%18))))(())};}impl l for[[[B;9];9];9]{fn get(&self,e:b)->B{self[e.0][e.1][e.2]}fn K(&self,e:b)->B{Ea[e.0][e.1][e.2]}fn u(&mut self,mut m:d){m.2=m.2.rem_euclid(4);if m.2==0{return;}let Fa=m.0-b(1,1,1);let Ua:Vec<_>=self.slice(Fa,b(3,3,3)).iter().map(|(p,v)|(p.M(m.1,m.2,3)+Fa,v)).collect();for(e,ja)in Ua{self[e.0][e.1][e.2]=ja;}}fn j(&self)->b{b(9,9,9)}}struct qa<'a,C:l>{g:&'a C,e:b,}impl<'a,C:l>Iterator for qa<'a,C>{type Item=(b,B);fn next(&mut self)->Option<Self::Item>{let j=self.g.j();if self.e.2==j.2{return None;}let Va=Some((self.e,self.g.get(self.e)));self.e.0+=1;if self.e.0>=j.0{self.e.0=0;self.e.1+=1;if self.e.1>=j.1{self.e.1=0;self.e.2+=1;}}Va}fn size_hint(&self)->(usize,Option<usize>){let j=self.g.j();let Ga=j.0*j.1*j.2-self.e.0-self.e.1*j.0-self.e.2*j.0*j.1;(Ga,Some(Ga))}}trait Wa:l+Sized{fn iter<'a>(&'a self)->qa<'a,Self>{qa{g:self,e:b(0,0,0),}}}impl<T:l>Wa for T{}struct ka<C:l>{g:C,o:c,}impl<C:l>ka<C>{fn sa(&self,e:b)->b{e.P(self.o,self.j()[self.o])}}impl<C:l>l for ka<C>{fn get(&self,e:b)->B{self.g.get(self.sa(e))}fn K(&self,e:b)->B{self.g.K(self.sa(e))}fn u(&mut self,mut m:d){m.0=self.sa(m.0);if m.1!=self.o{m.2=-m.2;}self.g.u(m);}fn j(&self)->b{self.g.j()}}trait Xa:l+Sized{fn P(self,o:c)->ka<Self>{ka{g:self,o}}}impl<T:l>Xa for T{}trait Ya:l{fn Cb(&mut self)->bool{self.iter().all(|(e,ja)|ja==self.K(e))}}impl<T:l>Ya for T{}fn main(){let mut Ha=String::new();stdin().read_to_string(&mut Ha).unwrap();let mut g=Ia(Zb(&Ha[..]).unwrap());g.ab();}struct Ia([[[B;9];9];9]);impl l for Ia{fn get(&self,e:b)->B{self.0.get(e)}fn K(&self,e:b)->B{self.0.K(e)}fn j(&self)->b{self.0.j()}fn u(&mut self,m:d){println!("{}",db(&m));self.0.u(m);}}#[derive(Clone)]struct d(b,c,i8);trait eb{fn ba(self)->Self;}impl eb for Vec<d>{fn ba(mut self)->Self{self.reverse();for m in self.iter_mut(){m.2=-m.2;}self}}fn db(d(b(x,y,z),o,D):&d)->String{format!("{}{}{}{}{}",x,y,z,match o{c::X=>"X",c::Y=>"Y",c::Z=>"Z",},D.rem_euclid(4).to_string())}fn Zb(str:&str)->Result<[[[B;9];9];9],String>{let str=str.to_lowercase();let str=str.trim();let charset=if str.contains('a'){"0a1b2c3d4e5f6g7h8i"}else if str.contains('0'){"012345678"}else{"123456789"};let mut z=0;let mut g:[[[B;9];9];9]=Default::default();lazy_static!{static ref fb:Regex=Regex::new(r"\s*\n\s*\n\s*").unwrap();}for ua in fb.split(str){let ua=ua.trim();let mut O=z;for(y,la)in ua.split("\n").enumerate(){let la=la.trim();O=z;let gb=if la.chars().nth(1)==Some(' '){""}else{""};for ra in la.split(gb).filter(|x|*x!=""){let ra=ra.trim();for(x,char)in ra.chars().filter(|x|*x!=' ').enumerate(){if x>=9||y>=9||O>=9{dbg!((x,y,O));return Err(format!("Invalid g j{:?}",(x,y,O)));}let mut ta=if let Some(index)=charset.find(char){index as u8}else{return Err(format!("Invalid character{:?}",char));};if ta%2!=((x+y+O)%2)as u8{if charset.len()==9{ta+=9}else{return Err(format!("Invalid parity at position{:?}",(x,y,O)));}};g[x][y][O].0=ta;}O+=1;}}z=O;}if<[_]>::iter(&g).flatten().flatten().collect::<HashBag<_>>()!=<[_]>::iter(&*Ea).flatten().flatten().collect(){return Err(format!("Invalid piece counts"));}Ok(g)}#[derive(Clone,Copy,PartialEq,Eq,Hash)]struct b(usize,usize,usize);impl b{fn H(mut self,h:c,k:c)->b{let f=self[h];self[h]=self[k];self[k]=f;self}fn P(mut self,o:c,E:usize)->b{self[o]=E-1-self[o];self}fn M(self,o:c,D:i8,E:usize)->b{let mut ca=self;for _ in 0..(D.rem_euclid(4)){ca=match o{c::X=>ca.H(c::Y,c::Z).P(c::Y,E),c::Y=>ca.H(c::Z,c::X).P(c::Z,E),c::Z=>ca.H(c::X,c::Y).P(c::X,E),};}ca}fn parity(self)->usize{(self.0+self.1+self.2)%2}fn va(self,min:b,E:b)->bool{true&&self.0>=min.0&&self.0<=E.0&&self.1>=min.1&&self.1<=E.1&&self.2>=min.2&&self.2<=E.2}}impl Add for b{type Output=b;fn add(self,Q:Self)->Self::Output{b(self.0+Q.0,self.1+Q.1,self.2+Q.2)}}impl Sub for b{type Output=b;fn sub(self,Q:Self)->Self::Output{b(self.0-Q.0,self.1-Q.1,self.2-Q.2)}}#[derive(Copy,Clone,PartialEq,Eq)]enum c{X=0,Y=1,Z=2,}impl Index<c>for b{type Output=usize;fn index(&self,index:c)->&Self::Output{match index{c::X=>&self.0,c::Y=>&self.1,c::Z=>&self.2,}}}impl IndexMut<c>for b{fn index_mut(&mut self,index:c)->&mut Self::Output{match index{c::X=>&mut self.0,c::Y=>&mut self.1,c::Z=>&mut self.2,}}}struct wa<C:l>{g:C,min:b,j:b,}impl<C:l>l for wa<C>{fn get(&self,e:b)->B{self.g.get(e+self.min)}fn K(&self,e:b)->B{self.g.K(e+self.min)}fn u(&mut self,mut m:d){m.0=m.0+self.min;self.g.u(m)}fn j(&self)->b{self.j}}trait hb:l+Sized{fn slice(self,min:b,j:b)->wa<Self>{wa{g:self,min,j,}}}impl<T:l>hb for T{}trait ib:l+Sized{fn ab(&mut self){let j=self.j();let mut min=b(0,0,0);let mut E=j;for&o in[c::Z,c::Y,c::X].iter(){for _ in 0..((j[o]-5+1/*round Eb*/)/2){self.jb(o,min,E);min[o]+=1;}for _ in 0..((j[o]-5)/2){self.kb(o,min,E);E[o]-=1;}}self.slice(min,b(5,5,5)).W(Ja).W(Ka).W(La).W(Ma);}}trait lb:l{fn jb(&mut self,o:c,min:b,E:b){self.slice(min,E-min).H(c::Z,o).W(xa);}fn kb(&mut self,o:c,min:b,E:b){self.slice(min,E-min).H(c::Z,o).P(c::X).P(c::Y).P(c::Z).W(xa);}}impl<T:l>ib for T{}impl<T:l>lb for T{}struct xa;impl aa for xa{fn L<C:l>(&self,g:&C,e:b)->t{let j=g.j();let b(x,y,z)=e;if z!=0{return t::da;};let index=y*j.0+x;if y+2>=j.1{if x+2>=j.0{t::G{index,w:b(j.0-4+j.1-y,j.1-1,5+x-j.0),q:vec![d(b(j.0-2,j.1-2,1),c::X,1),d(b(j.0-2,j.1-2,1),c::Y,-1),d(b(j.0+j.1-5-y,j.1-2,4+x-j.0),c::Y,1,),d(b(j.0-2,j.1-2,1),c::Y,1),d(b(j.0-2,j.1-2,1),c::X,-1),],}}else{t::G{index,w:b(x,j.1-1,5+y-j.1),q:vec![d(b(x+1,j.1-2,1),c::X,1),d(b(x+1,j.1-2,4+y-j.1),c::X,-1),d(b(x+1,j.1-2,1),c::X,-1),],}}}else{if x+2>=j.0{t::G{index,w:b(j.0-1,y,5+x-j.0),q:vec![d(b(j.0-2,y+1,1),c::Y,-1),d(b(j.0-2,y+1,4+x-j.0),c::Y,1),d(b(j.0-2,y+1,1),c::Y,1),],}}else{t::G{index,w:e+b(0,0,2),q:vec![d(e+b(1,1,1),c::Y,-1)],}}}}fn J<C:l>(&self,g:&mut C,h:b,k:b){mb(g.slice(b(0,0,1),g.j()-b(0,0,1)),h-b(0,0,1),k-b(0,0,1),);}}fn mb<C:l>(mut g:C,mut h:b,k:b){if h.parity()!=k.parity(){panic!("Cannot move between positions of different parities");}while h!=k{ya(&mut g,c::X,&mut h,k);ya(&mut g,c::Y,&mut h,k);ya(&mut g,c::Z,&mut h,k);}}fn ya<C:l>(g:C,o:c,h:&mut b,k:b){let nb=g.H(c::X,o);let mut Na=h.H(c::X,o);ob(nb,&mut Na,k.H(c::X,o));*h=Na.H(c::X,o)}fn ob<C:l>(mut g:C,h:&mut b,k:b){let ja=g.get(*h);let j=g.j();while h.0!=k.0{let mut A=b(0,0,0);let D;if h.0<k.0{A.0=h.0+1}else{A.0=h.0-1}if(h.0+1==k.0||k.0+1==h.0)&&h.0!=0&&h.0!=j.0-1{A.0=h.0}if h.1<=1{A.1=h.1+1;D=if h.0<k.0{1}else{3}}else{A.1=h.1-1;D=if h.0<k.0{3}else{1}}if h.2<=1{A.2=1}else{A.2=h.2-1}g.u(d(A,c::Z,D));*h=(*h-(A-b(1,1,1))).M(c::Z,D,3)+(A-b(1,1,1));}}struct Ma;impl aa for Ma{fn J<C:l>(&self,ma:&mut C,h:b,k:b){}fn L<C:l>(&self,ma:&C,e:b)->t{let ea=true&&e.0>=1&&e.0<=3&&e.1>=1&&e.1<=3&&e.2>=1&&e.2<=3&&e.parity()==1&&e.0!=2&&e.1!=2&&e.2!=2;if!ea{return t::na;}let fa=match e{b(1,1,1)=>return t::da,b(3,3,1)=>vec![],b(1,3,1)=>vec![d(b(2,3,2),c::Y,-1)],b(3,1,1)=>vec![d(b(3,2,2),c::X,1)],b(x,y,3)=>vec![d(b(2,2,3),c::Z,if x==1{if y==1{2}else{-1}}else{if y==1{1}else{0}},),d(b(2,3,2),c::Y,1),],_=>unreachable!(),};let mut q=fa.clone();q.extend_from_slice(&pb);q.extend(fa.ba());t::G{index:if e==b(3,2,1){1}else{0},w:b(1,1,1),q,}}fn u<C:l>(&self,g:&mut C,m:d){g.V(m);}}static pb:[d;17]=[d(b(2,3,2),c::Y,-1),d(b(3,2,2),c::X,-1),d(b(2,2,1),c::Z,-1),d(b(3,2,2),c::X,1),d(b(2,2,1),c::Z,-1),d(b(3,2,2),c::X,-1),d(b(2,2,1),c::Z,1),d(b(3,2,2),c::X,1),d(b(2,3,2),c::Y,1),d(b(3,2,2),c::X,-1),d(b(2,2,1),c::Z,1),d(b(3,2,2),c::X,1),d(b(2,2,1),c::Z,-1),d(b(3,2,2),c::X,1),d(b(2,3,2),c::Y,-1),d(b(3,2,2),c::X,-1),d(b(2,3,2),c::Y,1),];struct Ka;impl aa for Ka{fn J<C:l>(&self,g:&mut C,h:b,k:b){fn f(e:b)->i8{if e.0==1{if e.1==1{0}else{1}}else{if e.1==1{3}else{2}}}g.V(d(b(2,2,h.2),c::Z,f(h)-f(k)));if k.2!=h.2{g.V(d(b(2,k.1,2),c::Y,-((k.0+k.2-1)as i8)));}}fn L<C:l>(&self,ma:&C,e:b)->t{let ea=e.va(b(1,1,1),b(3,3,3))&&e.parity()==1;if!ea{return t::na;}match e{b(x,2,2)=>t::G{index:0,w:b(x,1,1),q:vec![d(b(x,2,1),c::X,1),d(b(x,1,2),c::X,-1),d(b(x,2,1),c::X,-1),d(b(x,1,2),c::X,1),],},b(2,y,2)=>t::G{index:0,w:b(1,y,1),q:vec![d(b(1,y,2),c::Y,1),d(b(2,y,1),c::Y,-1),d(b(1,y,2),c::Y,-1),d(b(2,y,1),c::Y,1),],},b(2,2,z)=>t::G{index:0,w:b(1,1,z),q:vec![d(b(2,1,z),c::Z,1),d(b(1,2,z),c::Z,-1),d(b(2,1,z),c::Z,-1),d(b(1,2,z),c::Z,1),],},_=>t::da,}}fn u<C:l>(&self,g:&mut C,m:d){g.V(m);}}struct La;impl aa for La{fn J<C:l>(&self,ma:&mut C,h:b,k:b){}fn L<C:l>(&self,ma:&C,e:b)->t{let ea=e.va(b(1,1,1),b(3,3,3))&&e.parity()==0&&e!=b(2,2,2);if!ea{return t::na;}let fa=match e{b(3,2,1)=>return t::da,b(1,2,1)=>vec![],b(x,y,3)=>vec![d(b(2,2,3),c::Z,if x==3{2}else if y==3{1}else if y==1{-1}else{0},),d(b(1,2,2),c::X,2),],b(x,y,2)=>vec![d(b(2,2,2),c::Z,if x==3{if y==3{1}else{2}}else{if y==3{0}else{-1}},),d(b(1,2,2),c::X,-1),],b(2,y,1)=>vec![d(b(2,2,2),c::X,2),d(b(2,2,3),c::Z,if y==3{-1}else{1}),d(b(1,2,2),c::X,2),],_=>unreachable!(),};let mut q=fa.clone();q.extend_from_slice(&qb);q.extend(fa.ba());t::G{index:if e==b(3,2,1){1}else{0},w:b(3,2,1),q,}}fn u<C:l>(&self,g:&mut C,m:d){g.V(m);}}static qb:[d;14]=[d(b(3,2,2),c::X,-1),d(b(2,2,1),c::Z,1),d(b(3,2,2),c::X,1),d(b(2,2,1),c::Z,-1),d(b(3,2,2),c::X,1),d(b(2,3,2),c::Y,-1),d(b(3,2,2),c::X,2),d(b(2,2,1),c::Z,-1),d(b(3,2,2),c::X,1),d(b(2,2,1),c::Z,-1),d(b(3,2,2),c::X,-1),d(b(2,2,1),c::Z,1),d(b(3,2,2),c::X,1),d(b(2,3,2),c::Y,1),];lazy_static!{static ref za:Vec<d>=vec![d(b(1,2,2),c::Z,1),d(b(2,3,2),c::Z,-1),d(b(1,2,2),c::Z,-1),d(b(2,3,2),c::Z,1),];static ref Oa:Vec<d>=za.clone().ba();}struct Ja;impl aa for Ja{fn J<C:l>(&self,g:&mut C,h:b,k:b){let A=b(2,2,2);if h.parity()!=k.parity(){panic!("Cannot move between positions of different parities");}if h==k{return;}if h.parity()==1{fn Aa(e:b)->bool{((e.0==2)as u8+(e.1==2)as u8+(e.2==2)as u8)==2}if Aa(h){if Aa(k){fn Pa(e:b)->(c,i8){let o=if e.0!=2{c::X}else if e.1!=2{c::Y}else{c::Z};(o,if e[o]==3{1}else{-1})}let(Qa,rb)=Pa(h);let(Ba,sb)=Pa(k);if Qa==Ba{g.u(d(A,if Ba==c::X{c::Y}else{c::X},2,))}else{let(tb,ub)=match(Qa,Ba){(c::X,c::Y)=>(c::Z,1),(c::Y,c::X)=>(c::Z,-1),(c::Z,c::X)=>(c::Y,1),(c::X,c::Z)=>(c::Y,-1),(c::Y,c::Z)=>(c::X,1),(c::Z,c::Y)=>(c::X,-1),_=>unreachable!(),};g.u(d(A,tb,rb*sb*ub));}}else{self.J(g,h,b(2,2,1));g.ia(Oa.clone());self.J(g,b(1,3,1),k);}}else{if Aa(k){self.J(g,h,b(1,3,1));g.ia(za.clone());self.J(g,b(2,2,1),k);}else{fn f(e:b)->i8{if e.0==1{if e.1==1{0}else{1}}else{if e.1==1{3}else{2}}}g.u(d(A,c::Z,f(h)-f(k)));if k.2!=h.2{g.u(d(A,c::Y,-((k.0+k.2-1)as i8)));}}}}else{if h==A{g.ia(Oa.clone());self.J(g,b(1,3,2),k);}else if k==A{self.J(g,h,b(1,3,2));g.ia(za.clone());}else if h.2!=k.2{let mut h=h;while h.2!=k.2{let o=if h.0==2{c::Y}else{c::X};let ga=if o==c::Y{-1}else{1};g.u(d(A,o,ga));h=h.M(o,ga,5);}self.J(g,h,k);}else{fn f(e:b)->i8{if e.0<=2&&e.1==1{3}else if e.0==3&&e.1<=2{2}else if e.0>=2&&e.1==3{1}else{0}}g.u(d(A,c::Z,f(h)-f(k)));}}}fn L<C:l>(&self,g:&C,e:b)->t{match e{b(2,2,2)=>t::G{index:100,w:b(2,2,2),q:vec![],},p if vb(p)=>t::da,_=>match e{p if p.0>=3||p.1>=3=>self.L(g,e.M(c::Z,1,5)).tap_mut(|x|x.M(c::Z,-1,5)),p if p.2>=1=>{let(o,ga)=if p.1==0{(c::X,1)}else{(c::Y,-1)};self.L(g,e.M(o,ga,5)).tap_mut(|x|x.M(o,-ga,5))}p if p.1>p.0=>self.L(g,e.H(c::X,c::Y)).tap_mut(|x|x.H(c::X,c::Y)),b(0,0,0)=>t::G{index:0,w:b(2,2,2),q:vec![d(b(1,1,1),c::Z,2),d(b(1,1,1),c::X,1),],},b(1,0,0)=>t::G{index:1,w:b(2,3,2),q:vec![d(b(1,1,1),c::Z,1),d(b(1,1,1),c::Y,-1),d(b(2,2,2),c::Z,2),d(b(1,1,1),c::Y,1),d(b(1,1,1),c::Z,-1),],},b(2,0,0)=>t::G{index:2,w:b(2,2,2),q:vec![d(b(2,3,2),c::Z,-1),d(b(1,1,1),c::Z,1),d(b(1,1,1),c::Y,-1),d(b(2,3,2),c::Z,1),d(b(1,1,1),c::Y,1),d(b(1,1,1),c::Z,-1),],},b(1,1,0)=>t::G{index:3,w:b(3,3,2),q:vec![d(b(1,1,1),c::Z,1),d(b(1,1,1),c::Y,2),d(b(2,2,2),c::Z,2),d(b(1,1,1),c::Y,2),d(b(1,1,1),c::Z,-1),],},b(2,1,0)=>t::G{index:4,w:b(1,2,2),q:vec![d(b(2,3,2),c::Z,-1),d(b(1,1,1),c::Z,-1),d(b(1,1,1),c::X,2),d(b(2,3,2),c::Z,1),d(b(1,1,1),c::X,2),d(b(1,1,1),c::Z,1),],},b(2,2,0)=>t::G{index:5,w:b(2,3,3),q:vec![d(b(1,1,1),c::Z,1),d(b(1,1,1),c::Y,2),d(b(3,3,2),c::X,1),d(b(1,1,1),c::Y,2),d(b(1,1,1),c::Z,-1),d(b(3,3,2),c::X,-1),],},_=>unreachable!(),},}}}fn vb(p:b)->bool{p.va(b(1,1,1),b(3,3,3))}trait aa{fn L<C:l>(&self,g:&C,e:b)->t;fn J<C:l>(&self,g:&mut C,h:b,k:b);fn u<C:l>(&self,g:&mut C,m:d){g.u(m);}fn wb<C:l>(&self,g:&mut C){let mut oa=<HashSet<b>>::new();let mut Ra:Vec<_>=g.iter().filter_map(|(e,_)|match self.L(g,e){t::G{index,w,q,}=>Some((e,index,w,q)),_=>None,}).collect();Ra.sort_by_key(|x|x.1);for(e,_,w,q)in Ra{oa.insert(e);let Sa=g.K(e);if g.get(e)==Sa{continue;}let h=g.iter().find(|&(p,v)|{v==Sa&&!matches!(self.L(g,p),t::na)&&!oa.contains(&p)}).unwrap().0;if let t::G{q:xb,w:yb,..}=self.L(g,h){for m in xb.ba(){self.u(g,m);}self.J(g,yb,w);}else{self.J(g,h,w);}for m in q{self.u(g,m);}}}}trait zb:l+Sized{fn W<S:aa>(&mut self,bb:S)->&mut Self{bb.wb(self);self}}impl<T:l>zb for T{}enum t{G{index:usize,w:b,q:Vec<d>,},da,na,}impl t{fn H(&mut self,h:c,k:c){match self{Self::G{w,q,..}=>{*w=w.H(h,k);for m in q.iter_mut(){m.2=-m.2;m.0=m.0.H(h,k);if m.1==h{m.1=k;}else if m.1==k{m.1=h;}else{m.1;}}}_=>{}}}fn M(&mut self,o:c,D:i8,E:usize){let D=D.rem_euclid(4);if D==0{return;}match self{Self::G{w,q,..}=>{*w=w.M(o,D,E);for m in q.iter_mut(){m.0=m.0.M(o,D,E);if match(o,D){(c::X,1)|(c::Y,3)=>m.1==c::Z,(c::Y,1)|(c::Z,3)=>m.1==c::X,(c::Z,1)|(c::X,3)=>m.1==c::Y,(_,_)=>m.1!=o,}{m.2=-m.2;}if D!=2{m.1=match(o,m.1){(c::Y,c::Z)|(c::Z,c::Y)=>c::X,(c::Z,c::X)|(c::X,c::Z)=>c::Y,(c::X,c::Y)|(c::Y,c::X)=>c::Z,_=>o,};}}}_=>{}}}}struct Ca<C:l>{g:C,h:c,k:c,}impl<C:l>l for Ca<C>{fn get(&self,e:b)->B{self.g.get(e.H(self.h,self.k))}fn K(&self,e:b)->B{self.g.K(e.H(self.h,self.k))}fn u(&mut self,mut m:d){if self.h!=self.k{m.0=m.0.H(self.h,self.k);m.2=-m.2;if m.1==self.h{m.1=self.k;}else if m.1==self.k{m.1=self.h;}}self.g.u(m)}fn j(&self)->b{self.g.j().H(self.h,self.k)}}trait Ab:l+Sized{fn H(self,h:c,k:c)->Ca<Self>{Ca{g:self,h,k,}}}impl<T:l>Ab for T{}#[derive(PartialEq,Eq,Copy,Clone,Hash,Default)]struct B(u8);

```

The solution is hosted on GitHub. Running `cargo run` in the root directory will take the cube from stdin and output a list of moves that solves the inputted cube. Input can be in any of the forms from the question and this answer. The output will use a modified coordinate system by default, but can be changed to use the question's coordinate system by changing line 27.

If you'd like to play with the cube and see how it's solved, I've created an interactive visualization.

If you'd like to read about how it's solved, I've written a long detailed explanation with interactive illustrations of the process.

## Explanation

### Coordinate System

This explanation will use a slightly different coordinate system than the challenge.

`X` is left-to-right, `Y` is top-to-bottom, and `Z` is front-to-back.

Here are 3 different visualizations of the axes:

```
   z
  / E F
 /  G H
* - - x
| A B
| C D
y

A B  E F
C D  G H

```

```
0 x  z ·
y ·  · ·

```

```
Positions as 'xyz':
000 100   001 101
010 110   011 111

```

Rotations are clockwise looking down the axis (right-hand rule).

Here is a visualization of the 3 unit rotations:

```
cube:       X1(cube):
0 x  z ·    z ·  · ·
y ·  · ·    0 x  y ·

cube:       Y1(cube):
0 x  z ·    x ·  0 z
y ·  · ·    · ·  y ·

cube:       Z1(cube):
0 x  z ·    y 0  · z
y ·  · ·    · x  · ·

```

### 0-indexing

The original challenge 1-indexes the pieces, which complicates the modulo arithmetic. This explanation will use 0-indexing, where the pieces are numbered 0-8.

```
1-indexing
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
...

0-indexing
0 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 0
...

```

### Parity

Pieces are locked in to a checkerboard pattern; pieces from odd places can only go to odd places, and likewise for even.

This means that there are actually 18 kinds of pieces.

```
0 in an even position -->  0 1 2 3 4 5 6 7 8
                           1 2 3 4 5 6 7 8 0 <-- 0 in an odd position
                           ...

```

This brings us to...

### Alternate Notation

Because there are 18 kinds of pieces, it's helpful to have 18 distinct symbols. From now on, this explanation will use an adapted, alpha-numeric notation, where all even-parity pieces are numbers, and all odd-parity pieces are letters.

```
0-indexed
0 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 0
2 3 4 5 6 7 8 0 1
3 4 5 6 7 8 0 1 2
...

Alpha-numeric
0 a 1 b 2 c 3 d 4
a 1 b 2 c 3 d 4 e
1 b 2 c 3 d 4 e 5
b 2 c 3 d 4 e 5 f
...

```

### Links

Throughout this explanation, links to cube states will be used to illustrate the process. Here's a scrambled cube, and a solved cube.

Some links will illustrate a set of moves. First, it will show the goal state, followed by the start state of the cube. Then, for each move, it will first highlight the positions that will be affected, and then show the result of the move. Here's an example of a small algorithm.

Additionally, some links with moves will emphasize certain pieces. The bordered pieces are the focus, and the highlighted pieces are pieces that will/must remain unchanged. Here's an example of the previous algorithm with highlights. Sometimes, only a subset of the unchanged pieces will be highlighted, to make it easier to track the rotations.

### Approach to Solving

To solve the cube, we iterate through the positions in some order and solve each of them without unsolving the previous positions.

Positions can be in two states: solved & unsolved. When solving a position, pieces in solved positions may be moved but must be restored to ensure the solved positions are ultimately unchanged.

A position is solved by the following process:

1. Locate a piece of the correct value in any unsolved position.
2. Move the piece to the correct position without ultimately changing any solved position.

#1 is fairly self-explanatory, so the rest of this explanation focuses on #2.

At various times throughout solving the cube, we'll denote an unsolved section of the cube as the "pool". We'll then divide #2 into 3 parts:

1. Move the piece into the pool.
2. Move the piece around in the pool.
3. Move the piece out of the pool into the correct position.

To accomplish this, we'll need to define two helpers:

1. We'll figure out how to move a piece from any position in the pool to any other position of the same parity in the pool.
2. Then, for each unsolved position outside of the pool, we'll choose a convenient "source" position in the pool and figure out a list of moves that will move a piece from the source position to the position we're solving.

Using these two helpers, we can refine the above process:

1. Move the piece into the pool.
    * Execute the reverse of the moves supplied by helper #2.
2. Move the piece around in the pool.
    * Use helper #1.
3. Move the piece out of the pool into the correct position.
    * Execute the moves supplied by helper #2.

We will now formalize and define this logic.

### Overview

At a high level, the solving method is broken into three stages.

1. Solving the outer shell (everything but the center 5×5×5)
2. Solving the inner shell (the center 5×5×5 excluding the center 3×3×3)
3. Solving the center 3×3×3

Each stage consists of a few steps.

### Step Structure

In each step, the puzzle positions are paritioned into 3 classifications:

1. 'active': unsolved positions that will be solved by the step
2. 'done': previously solved positions
3. 'pool': unsolved positions

A step is executed by iterating through the 'active' positions and solving each position by executing the following prodecure:

1. Locate a piece of the correct value in any unsolved position.
2. Move the piece into the pool.
3. Move the piece within the pool to a 'source' position in the pool.
4. Move the piece from the 'source' position to the target position.

All of the above steps must be performed without ultimately changing any piece in a previously solved 'active' position or any piece in a 'done' position.

### Step Definition

Thus, a step is defined by:

1. A partition of the puzzle pieces
2. A way to move a piece from any 'pool' position to any other 'pool' position of the same parity (without ultimately changing any piece in an 'active' or 'done' position)
3. For each 'active' position:
    * An index indicating when to solve this position
    * A convenient source 'pool' position
    * A list of moves that will move a piece from the specified 'pool' position to this position (without ultimately changing any piece in an 'active' position with a lower index or any piece in a 'done' position)

### Stage 1: Solving the outer shell

In this stage, we'll solve everything but the center 5×5×5.

We'll accomplish this with 12 steps, each step solving a face of the unsolved portion of the 9×9×9. We could go in any order; the implementation follows this ordering (as it looked nice):

1. The `Z=0` plane (after)
2. The `Z=1` plane (after)
3. The `Z=8` plane (after)
4. The `Z=7` plane (after)
5. The `Y=0` plane (after)
6. The `Y=1` plane (after)
7. The `Y=8` plane (after)
8. ...
9. ...
10. ...
11. ...
12. The `X=7` plane (after)

### Stage 1, Step 1: Solving the `Z=0` face

All positions with `Z=0` are 'active', and all other positions are 'pool'.

The most interesting part of this step involves the 'active' positions. The 'active' positions fall into 3 categories based on their location:

```
A A A A A A A A B B
A A A A A A A A B B
A A A A A A A A B B
A A A A A A A A B B
A A A A A A A A B B
A A A A A A A A B B
A A A A A A A A B B
B B B B B B B B C C
B B B B B B B B C C

```

We'll solve each 'active' position from left-to-right, then top-to-bottom.

The examples that follow focus solely on the moves after the piece is moved into the 'source' position.

`A` positions are the easiest to solve, as they only require one rotation; here's an example for one `A` position.

`B` positions are a little more complicated. Because they're near the edge, we can't use the same technique as in `A`. This means that we'll have to move some of the pieces we've previously solved, but we also need to make sure to restore them to the correct position afterwards. Here's an example of how this is accomplished for one `B` position.

If you've played with puzzle cubes before, the technique used in that algorithm may be familiar. Essentially, we're rotating the target position to a more convenient place, moving the piece in, and then undoing the rotation of the target position.

Last and certainly not least, we have `C` positions, which are surrounded on all sides. Solving them is similar to `B` positions, but a little more complicated. Here's an example for one `C` position.

Moving pieces within the pool is rather simple, as there's a lot of room, and the pool is a rectangular prism; here is an example for one case. A full explanation of the algorithm is omitted, as it is not very novel.

### Stage 1, Steps 2-12

These steps follow the same pattern as Step 1, just on different faces within the cube.

### Stage 2: Solving the inner shell

At this point, everything is solved except for the inner 5×5×5. After this stage, everything except the inner 3×3×3 will be solved.

This stage is not part of Stage 1 because some of the algorithms used in Stage 1 require more space than is available in the 5×5×5.

This stage consists of a single step.

All positions outside of in center 5×5×5 are 'done' and will not be changed (even temporarily). Positions in the center 3×3×3 are 'pool', and the remainder are 'active'.

### Stage 2, Moving between 'pool' positions

Moving pieces between 'pool' positions is more complex in this step, because of the limited space. To describe how pieces are moved, we'll first divide the pool into 4 sections, pictured below.

```
P T P  T Q T  P T P
T Q T  Q U Q  T Q T
P T P  T Q T  P T P

```

`P` positions are the corners, `Q` positions are the face centers, `T` positions are the edges, and the singular `U` position is the cube center.

`P` and `Q` positions all have odd parity, and `T` and `U` positions all have even. Thus, pieces can be moved freely between `P` and `Q` positions, and `T` and `U` positions, but not between `P` and `T` positions, `P` and `U` positions, etc.

Thus, there are 8 possible cases:

* P: From a `P` position to another `P` position
* Q: From a `Q` position to another `Q` position
* T: From a `T` position to another `T` position
* U: From the `U` position to itself
* PQ: From a `P` position to a `Q` position
* QP: From a `Q` position to a `P` position
* TU: From a `T` position to the `U` position
* UT: From the `U` position to a `T` position

Case U is very trivial, since it is accomplished by doing nothing. Cases P, Q, T are fairly trivial, and can be accomplished simply by rotating the center 3×3×3.

Cases PQ, QP, TU, UT are where things get interesting — remember that these must be accomplished without ultimately changing any piece outside of the pool, the center 3×3×3.

Cases QP & UT are the reverse of cases PQ & TU, respectively, so we will focus on the later two cases.

Cases PQ & TU are both based off of the following algorithm that we'll call `INTO_CENTER`, which moves a piece from position `X` into position `U` whilst preserving everything outside of the center 3×3×3.

```
· · ·  · · ·  · · ·
· · ·  · U ·  · · ·
· · ·  X · ·  · · ·

```

Here is `INTO_CENTER` in action.

First, Case TU. We can accomplish it with the follwing procedure:

1. Move the piece from the original `T` position to position `V` using Case T.
2. Use `INTO_CENTER` to move the piece from position `V` to position `U`.

```
· · ·  · · ·  · T ·
· · ·  · U ·  · · ·
· · ·  V · ·  · · ·

```

Onto Case PQ. If you look at the moves in `INTO_CENTER` (linked above), you might notice two things:

1. All of the moves rotate around the `Z` axis
2. All of the moves are at `Z=4`

These two properties mean that `INTO_CENTER` has the same effect on the `Z=3` and `Z=5` layers as it does on the `Z=4` layer we focused on.

This means that we can accomplish Case PQ with the following procedure:

1. Move the piece from the original `P` position to position `R`, using Case P.
2. Use `INTO_CENTER` to move the piece from position `R` to position `S`.
3. Move the piece from position `S` to the destination `Q` position, using Case Q.

```
· · ·  · · ·  · · P
· S ·  · · ·  · · ·
R · ·  · Q ·  · · ·

```

### Stage 2, Moving pieces to 'active' positions

Now that we have a method to move pieces between 'pool' positions, we can move on to describing the 'active' positions.

First, we'll break up the 'active' positions into a few categories, and then we'll describe each category.

We'll label the categories `A`-`F`; the partition is pictured below.

```
A B C B A  B D E D B  C E F E C  B D E D B  A B C B A
B D E D B  D · · · D  E · · · E  D · · · D  B D E D B
C E F E C  E · · · E  F · · · F  E · · · E  C E F E C
B D E D B  D · · · D  E · · · E  D · · · D  B D E D B
A B C B A  B D E D B  C E F E C  B D E D B  A B C B A

```

The categories will be solved in alphabetical order; all `A` positions are solved, then all `B` positions, etc.

For each category, we'll focus on the behavior of only one position; all of the others follow by symmetry. Specifically, we'll focus on the following positions:

```
A B C · ·  · · · · ·  · · · · ·  · · · · ·  · · · · ·
· D E · ·  · · · · ·  · · · · ·  · · · · ·  · · · · ·
· · F · ·  · · · · ·  · · · · ·  · · · · ·  · · · · ·
· · · · ·  · · · · ·  · · · · ·  · · · · ·  · · · · ·
· · · · ·  · · · · ·  · · · · ·  · · · · ·  · · · · ·

```

When solving a position, care must be taken to not ultimately change any other position that is outside of the 5×5×5 or in an earlier or current category.

The below diagrams are maps of the 5×5×5. `#` represents a position that must be ultimately unchanged, `+` represents a 'pool' position, and `X` is the 'pool' position that we'll later establish as our source 'pool' position.

First up are `A` positions.

```
A · · · #  · · · · ·  · · · · ·  · · · · ·  # · · · #
· · · · ·  · + + + ·  · + + + ·  · + + + ·  · · · · ·
· · · · ·  · + + + ·  · + X + ·  · + + + ·  · · · · ·
· · · · ·  · + + + ·  · + + + ·  · + + + ·  · · · · ·
# · · · #  · · · · ·  · · · · ·  · · · · ·  # · · · #

```

Solving this position is rather trivial. We'll set our source 'pool' position to be in the center, and to solve the `A` position we'll simply rotate the piece in.

Let's move on to `B` positions.

```
# B · # #  # · · · #  · · · · ·  # · · · #  # # · # #
# · · · #  · + + + ·  · + + + ·  · + + + ·  # · · · #
· · · · ·  · + + + ·  · + + + ·  · + + + ·  · · · · ·
# · · · #  · + + + ·  · + X + ·  · + + + ·  # · · · #
# # · # #  # · · · #  · · · · ·  # · · · #  # # · # #

```

Here, there are more locked-in pieces, meaning that we can't just simply rotate the piece in. Thus, we'll have to do a little bit of maneuvering.

It's getting a bit tighter, but `C` positions are rather similar to `B` positions.

```
# # C # #  # · · · #  # · · · #  # · · · #  # # # # #
# · · · #  · + + + ·  · + + + ·  · + + + ·  # · · · #
# · · · #  · + + + ·  · + X + ·  · + + + ·  # · · · #
# · · · #  · + + + ·  · + + + ·  · + + + ·  # · · · #
# # # # #  # · · · #  # · · · #  # · · · #  # # # # #

```

Onto `D` positions.

```
# # # # #  # # · # #  # · · · #  # # · # #  # # # # #
# D · # #  # + + + #  · + + + ·  # + + + #  # # · # #
# · · · #  · + + + ·  · + + + ·  · + + + ·  # · · · #
# # · # #  # + + + #  · + + + ·  # + + X #  # # · # #
# # # # #  # # · # #  # · · · #  # # · # #  # # # # #

```

It's getting cramped! Time for `E` positions.

```
# # # # #  # # # # #  # # · # #  # # # # #  # # # # #
# # E # #  # + + + #  # + + + #  # + + + #  # # # # #
# # · # #  # + + + #  · X + + ·  # + + + #  # # · # #
# # # # #  # + + + #  # + + + #  # + + + #  # # # # #
# # # # #  # # # # #  # # · # #  # # # # #  # # # # #

```

Finally, `F` positions. There is almost no room to work with here, but we can squeeze the piece in by rotating the corner cube and then one of the edge cubes.

```
# # # # #  # # # # #  # # # # #  # # # # #  # # # # #
# # # # #  # + + + #  # + + + #  # + + + #  # # # # #
# # F # #  # + + + #  # + + + #  # + + + #  # # # # #
# # # # #  # + + + #  # + + + #  # + X + #  # # # # #
# # # # #  # # # # #  # # # # #  # # # # #  # # # # #

```

### Stage 3: Solving the center 3×3×3

At this point, everything but the center 3×3×3 is solved. At the end of this stage, it will be entirely solved.

Stage 3 will be broken into 3 steps:

1. Solving the center cross
2. Solving the edges
3. Solving the corners

### Thin Moves

Before moving on to Step 1, we're going to introduce a very useful set of algorithms: thin moves. These allow us to rotate "flat" 1×3×3 sections of the cube, without affecting other pieces.

In subsequent examples, thin moves are shown as lines labeled with a `t` — this is a shorthand for the sequence of regular moves that comprise the thin move. Here's an example of the shorthand for a quarter-turn rotation on Z.

Here are the moves that comprise the previous thin move.

### Stage 3, Step 1: Solving the center cross

Again, the center cross is this set of pieces.

As a precursor, we're going to solve the center-most piece first, because we can simply use the 'pool'-to-'pool' algorithm from Stage 2, Step 1. Afterwards, everything but the outer shell of the 3×3×3 will be solved and we can proceed to the novel parts of this step.

The partition for this step is as follows:

* 'active': all pieces in the center cross other than the center piece that we just solved.
* 'done': all pieces outside of the center 3×3×3, along with the center piece.
* 'pool': all of the corners and edges.

Here's a diagram of the positions like in the previous stage.

```
X · +   · # ·   + · +
· A ·   # # #   · # ·
+ · +   · # ·   + · +

```

Moving pieces between 'pool' positions is rather simple. We can use thin moves to rotate the corners and edges of a face of the 3×3×3 without affecting the center cross. Here's an example of moving one of the corners.

To move pieces from a 'pool' position to an 'active' position, we use a planar variation of `INTO_CENTER` that uses thin moves (`THINTO_CENTER`).

### Similarity to a Rubik's Cube

At this point, all positions except the corners and edges of the 3×3×3 are solved.

The center 3×3×3 is now rather similar to a Rubik's Cube:

* The center cross is solved, and the unsolved pieces are either edges or corners; in a Rubik's Cube, the center cross is fixed and is therefore always solved.
* Because corners and edges are of different parities, corners cannot swap with edges. Likewise, in a Rubik's Cube, corners cannot swap with edges.
* We can either use thin moves to rotate 1×3×3 slices, or regular moves to rotate the whole 3×3×3. These are the same moves you can make in a Rubik's Cube.

In fact, the rest of the puzzle is simpler than a Rubik's Cube:

* In a Rubik's Cube, every piece in unique, but in this, some of the pieces are interchangable.
* In a Rubik's Cube, corners can be in one of three orientations, and edges can be in one of two; in this, pieces don't have orientations.

To solve the rest of the cube, we'll use thin moves to solve it like a Rubik's Cube, using the Old Pochmann (, ) method.

### Stage 3, Step 2

In this step, the remainder of the cube will be divided as follows, where `A` and `B` represent 'active' positions, and `C` represents the singular 'pool' position.

```
· A ·   A · A   · A ·
B · C   · · ·   A · A
· A ·   A · A   · A ·

```

First, we'll solve all `A` positions. Then, we'll solve the `B` position. Nothing needs to be done to solve the `C` position, as all other pieces of the same parity will have been solved.

We'll focus on this `A` position; other `A` positions are solved similarly:

```
· # ·   # # #   · # ·
# # +   # # #   # # #
· A ·   # # #   · # ·

```

Since the `C` position is the only 'pool' position, our source position will always be `C`.

To solve this `A` position, we'll execute the following procedure:

1. Use thin moves to rotate the piece in this `A` position to the `B` position.
2. Swap the pieces in the `B` and `C` positions.
3. Reverse the moves in #1.

To accomplish #2, we'll use an algortihm known as the T Permutation, which swaps the pieces in the `B` and `C` positions, and swaps the pieces in the `P` and `Q` positions:

```
· · P   · · ·   · · ·
B · C   · · ·   · · ·
· · Q   · · ·   · · ·

```

Thus, the above procedure will swap the pieces in the `B` and `C` positions and swap the pieces in the `P` and `Q` positions. Note that we must be careful not to disturb the pieces in the `P` and `Q` positions in #1, as otherwise #2 will have undesirable effects on the rest of the cube.

As we solve all of the `B` positions, the pieces in the `P` and `Q` positions keep swapping back and forth, but we don't care, as they are both unsolved.

Finally, to solve the `B` and `C` positions, if they're not already solved, we'll apply the T Permutation to swap them.

*Note: usually, Old Pochmann will involve two additional algorithms for this step, the Ja and Jb permutations. These are used to simplify some of the swaps, but are not strictly necessary.*

### Stage 3, Step 3

This step is rather similar to Step 2.

In this step, the remainder of the cube will be divided as follows, where `A` and `B` represent 'active' positions, and `C` represents the singular 'pool' position.

```
C · A   · · ·   A · A
· · ·   · · ·   · · ·
A · B   · · ·   A · A

```

Like the previous step, we'll first solve all `A` positions, and then solve the `B` position. As before, nothing needs to be done to solve the `C` position, as all other pieces of the same parity will have been solved.

We'll focus on this `A` position; other `A` positions are solved similarly:

```
+ # #   # # #   # # #
# # #   # # #   # # #
A # #   # # #   # # #

```

To solve this `A` position, we'll execute the following procedure:

1. Use thin moves to rotate the piece in this `A` position to the `B` position.
2. Swap the pieces in the `B` and `C` positions.
3. Reverse the moves in #1.

To accomplish #2, we'll use an algorithm known as the Y Permutation, which swaps the pieces in the`B` and `C` positions, and swaps the pieces in the `P` and `Q` positions:

```
C P ·   · · ·   · · ·
Q · ·   · · ·   · · ·
· · B   · · ·   · · ·

```

Thus, the above procedure will swap the pieces in the `B` and `C` positions and swap the pieces in the `P` and `Q` positions. The `P` and `Q` positions were previously solved and have the same solved value, so swapping them does nothing.

Finally, to solve the `B` and `C` positions, if they're not already solved, we'll apply the Y Permutation to swap them.

The puzzle is now entirely solved.

*Note: in the Old Pochmann method, there is usually a step in between solving the edges and corners: possibly using the Ra Permutation to resolve parity. However, because the edges that the Y Permutation swaps are of equal value, this is unnecessary in our case.*

### Conclusion

We did it!

Thanks for reading the explanation; I hope you enjoyed it! If you haven't already, I highly suggest checking out the interactive visualization. If you have any questions, comments, or feedback, please leave a comment or ping me in chat!

---
Tags: code-golf, 3d, rubiks-cube
---


title: Show me the trajectory

text:
# Question
Title: Show me the trajectory
Given a list of integers find the "trajectory" that results from indefinitely moving the instructed steps to the right (left if negative), wrapping if necessary, starting at the first element.

A "trajectory", here, is defined as a list containing the elements that are visited only one time, in the order they are visited, and a list containing those visited repeatedly, also in order i.e.:

```
[first, second, ...], [first_of_loop, second_of_loop, ...]

```

Note that:

* Multiple elements may have the same value, yet these are distinct from each other when considering if they have been visited.
* The empty list need not be handled (given an empty list your code may error).

#### Example

Given

```
[6, 0, -6, 2, -9 , 5, 3]

```

we

* start at the first element, the `6`
* step right \\$6\\$ to the `3`,
* step right \\$3\\$ to the `-6`,
* step left \\$6\\$ to the `2`,
* step right \\$2\\$ to the `5`,
* step right \\$5\\$ back to the `2`.

Thus the trajectory is

```
[6, 3, -6], [2, 5]

```

...where the second list shows the final loop (we first encounter `2`, then `5`, then loop forever).

#### Test Cases

```
                                  in  out
                                 [0]  [], [0]
                                 [3]  [], [3]
                             [-1, 2]  [-1], [2]
               [5, 2, 4, 6, 7, 3, 1]  [], [5, 3, 2, 6, 4, 1]
             [6, 0, -6, 2, -9 ,5 ,3]  [6, 3, -6], [2, 5]
              [4, 5, 2, 6, -2, 7, 8]  [4], [-2, 2]
           [6, 10, 10, 0, -9, -4, 6]  [6, 6], [-4, 10, -9, 10]
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]  [], [9, 9, 9, 9]

```

# Answer
# Haskell + hgl, ~~61~~ ~~60~~ 58 bytes

```
(i:y)#x|i?>y=m(x!)&@sp(/=i)(rv y)|u<-(i+x!i)%l x:i:y=u#x
([0]#)

```

hgl is an experimental golfing library I am developing for Haskell. I started a few days ago and this is my first answer, and it's proof there is still a lot of room for improvement.

From this post I've learned that:

* I should probably make a dedicated function for `m.(!)`, since it is likely to come up more than just here.
* I need versions of `sp` (`span`) and `bk` (`break`) that include the element that matches / doesn't match the predicate in the first part. I had to use a hack with `rv`, which is costly and only works in this specific scenario.
* ~~I should make an infix version of `e` (`elem`). It would have saved me at least a byte here.~~ Turns out I had already done this (`(?>)`). Maybe what I actually need is better documentation that makes it easier to find this stuff.
* ~~I should make an infix version of `jB`. It would have saved me at least 2 bytes here.~~ This also existed and I didn't realize (`(&@)`). There might be a pattern here.
* It might be a good idea to make an infix of `sp`. It could have saved me a byte here if I hadn't made an infix of `jB`.
* I have probably overall underestimated the usefulness of infixes and I should in general just make more of them.

### But here's how it actually works:

Vocab:

* `(?>)`: checks if a list contains an element (`elem`)
* `m`: map (`fmap`)
* `(!)`: index a list (sort of `(!!)`)
* `(&@)`: maps function across both parts of a tuple.
* `sp`: splits a list at the first element that matches a predicate (`span`)
* `rv`: reverses a list (`reverse`)
* `(%)`: modulo infix (`mod`, yes Haskell does not have a modulo infix)

So this builds up a list of indices, when a index is added that is already in the list it stops and splits at the last occurrence of that index, and converts the indices to their values.
> 7 votes

# Answer
# , 53 48 bytes

*-5 thanks to Jonah!*

```
(_2{.{~</.~]+./\@e.r)(]~.@,r=.(#@[|]+{~){:)^:_&0

```

Try it online!

* `r=.(#@[|]+{~){:` take the last index (starting with 0 `&0`), get the corresponding value, add it to the index and take the mod.
* `]~.@, … ^:_` append the new value to the indices list and repeat that process until the list does not change after removing duplicates
* `]+./\@e.r` the next index is a duplicate, so we find it in the indices list and have a bitmask: 0 for visited once, 1 for loops.
* `_2{.{~</.~` group the values based on the indices. Because there might be no items that are visited once, we can pad the output with taking the last two items `_2{.`

Another approach would be to not build a list, but just repeat the index-shift-mod-loop `<@#` times, keeping the results, and then search for the loop. But I didn't get it shorter than this.
> 5 votes

# Answer
# JavaScript (ES6), 92 bytes

```
a=>[(g=p=>a=1/(i=g[p%=w=a.length])?[]:[q=a[p],...g(p+q+w*q*q,g[p]=k++)])(k=0).splice(0,i),a]

```

Try it online!

### Commented

```
a => [                 // a[] = input array
  ( g = p =>           // g is a recursive function taking a position p
                       // the underlying object of g is also used to keep
                       // track of the positions that are visited
    a =                // update a[]
      1 / (            //
        i = g[         // reduce the position modulo the length w of the
          p %= w =     // array and load g[p] into i
            a.length   //
        ]              //
      ) ?              // if i is defined:
        []             //   we've found the loop: stop the recursion
      :                // else:
        [              //   update the output array:
          q = a[p],    //     load a[p] into q
          ...g(        //     do a recursive call:
            p + q +    //       add q to p
            w * q * q, //       also add w*q² to make sure it's >= 0
            g[p] = k++ //       save the index k into g[p] and increment k
          )            //     end of recursive call
        ]              //   end of array update
  )(k = 0)             // initial call to g with p = k = 0
  .splice(0, i),       // extract the non-looping part
  a                    // append the looping part
]                      //

```
> 4 votes

# Answer
# Pip -xp, 32 bytes

```
^:iT(Yy+a@y%:#a)NiiPBya@i^@:i@?y

```

Takes the list (formatted like so: `[1;2;-3]`) as a command-line argument, and outputs a list of two lists. Try it here! Or, verify all test cases at TIO.

### Explanation

```
^:iT(Yy+a@y%:#a)NiiPBya@i^@:i@?y
                                  a is cmdline input, eval'd (-x flag);
                                  i is 0, y is "" (implicit)
^:i                               Split i and assign back to i: i is now [0]
   T                              Loop until
      y                            current index
       +a@y                        plus number at current index
           %:                      mod
             #a                    length of list
     Y                             (yank into y, making this the new index)
    (          )Ni                 is already in the list of indices traversed:
                  iPBy              Push the new index onto the list of indices
                                  After the loop, we have the list of unique
                                  indices traversed in i and the first repeated
                                  index in y
                      a@i         Values from a at each index in i
                         ^@:      split at
                            i@?y  the index of y in i

```
> 3 votes

# Answer
# Charcoal, 42 bytes

```
≔⁰ζＷ¬№υζ«⊞υζ≔﹪⁺ζ§θζＬθζ»≔⌕υζζＵＭυ§θιＩ⟦…υζ✂υζ

```

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

```
≔⁰ζ

```

Start at index 0.

```
Ｗ¬№υζ«

```

Repeat until a duplicate index is found.

```
⊞υζ

```

Save the current index.

```
≔﹪⁺ζ§θζＬθζ

```

Calculate the new index.

```
»≔⌕υζζ

```

Find the position of the repeat.

```
ＵＭυ§θι

```

Replace the indices with the values.

```
Ｉ⟦…υζ✂υζ

```

Output the values before and after the repeat as separate arrays.
> 3 votes

# Answer
# Ruby, 91 bytes

```
->l{*r=a=b=0;r<<a until b=r.index(a=(a+l[a])%l.size);[z=r[0,b],r-z].map{|x|l.values_at *x}}

```

Try it online!
> 3 votes

# Answer
# C (clang), 137 bytes

```
a,i,j;
#define f(l,z){int t[z]={i=j=0},h[z];for(;!(a=t[i]);i=(z+i+l[i]%z)%z)h[j]=l[i],t[i]=++j;for(i=0;i<j;)printf("! %d"+!!--a,h[i++]);}

```

Try it online!

```
l : list , z : length
int t[z] : kinda sieve, every step sets the visited item to step number
h[z] : save the trajectory values in order for output
for(;!(a=t[i]) : we iterate until we find a visited item, saving in a the first already visited
;i=(z+i+l[i]%z)%z) : modulo hack

at each iteration :
h[j]=l[i] : add item to output list
,t[i]=++j; : and update sieve

Output
for(i=0;i<j;) : j is the number of items visited
printf("! %d"+!!--a,h[i++])
a is the beginning of loop so we
put a separator by including '!' in format string

```
> 3 votes

# Answer
# Husk, ~~32~~ ~~29~~ ~~25~~ 23 bytes

*Edit: -2 bytes thanks to Razetime*

```
†!¹G-§eoUṠ-UUm←¡Sṙo!¹←ŀ

```

Try it online!

Outputs loop first, then first-visited.

**Piece by piece:**

Make an infinite list of lists of indices by repeatedly shifting by the input value indexed by the first element:

```
¡Sṙo!¹←ŀ

```

And get the first element of each of these: this is the list of indices:

```
m←

```

Now, get the longest non-repeating prefix (this includes one copy of the repeating elements):

```
U

```

And get the repeating indices:

```
oUṠ-U

```

Join these together into a list of 2 lists:

```
§e

```

And remove the first (the repeating indices) from the second (the prefix):

```
G-

```

Finally, use these to index into the original input:

```
†!¹

```
> 3 votes

# Answer
# Python 3, 116 bytes

```
f=lambda a,i=0,k=[]:i in k and[[a[q]for q in x]for x in[k[:k.index(i)],k[k.index(i):]]]or f(a,(i+a[i])%len(a),k+[i])

```

Try it online!
> 2 votes

# Answer
# , ~~121~~ ~~118~~ ~~108~~ ~~102~~ ~~101~~ 99 bytes

*-10 bytes and another -6 thanks to @Dominic van Essen*

```
function(a,t=1){while(!(t=(t+a[t]-1)%%sum(a|1)+1)%in%T)T=c(T,t)
split(a[T],cut(cumsum(T==t),-1:1))}

```

Try it online!

The outputted lists have weird names (two intervals), but it I hope it's ok.
> 2 votes

# Answer
# Jelly, 26 bytes

```
L‘0ị+ị¥%L}ɗƬɗƬ%LḊḣ2fQ,ḟʋ/ị

```

Try it online!

A monadic link taking a list of integers and returning two lists of integers, with the looped integers first.
> 2 votes

# Answer
# Jelly,  ~~23~~  22 bytes

Quite possibly still beatable...

```
ĖUṙFḢƊƬḢ€⁺JœṖ€$§ṪọɗƇLṪ

```

A monadic Link that accepts the list and yields a list of lists.

**Try it online!**

### How?

```
ĖUṙFḢƊƬḢ€⁺JœṖ€$§ṪọɗƇLṪ - Link: list of integers A=[a,b,...,x,y,...]
Ė                      - enumerate -> [[1,a],[2,b],...,[n,x],[m,y],...]
 U                     - upend     -> [[a,1],[b,2],...,[x,n],[y,m],...]
      Ƭ                - collect until a repeat under:
     Ɗ                 -   last three links as a monad, f(current=[[x,n],[y,m],...]):
   F                   -   flatten (current) -> [x,n,y,m,...]
  ṙ                    -   rotate (current) left by (each of [x,n,y,m,...])
    Ḣ                  -   head -> rotation by x
       Ḣ€              - head each -> leftmost of each, [[a,1],...,[x,n],...]
         ⁺             - repeat Ḣ€ -> visited elements in order, [a,...,x,...,last_of_loop]
              $        - last two links as a monad, f(V=[a,...,x,...,last_of_loop]):
          J            -   range of length -> [1,2,...,length(V)]
           œṖ€         -   partition (V) before each (of those) indices
                   Ƈ   - filter (all of these 2-partitions) keeping if:
                    L  -   use length (of A) on the right of...
                  ɗ    -   last three links as a dyad, f(partition, length(A)):
               §       -     sums
                Ṫ      -     tail -> length of the potential loop
                 ọ     -     how many times is that divisible by length(A)?
                             (positive (truthy) if an actual loop, else 0 (falsey))
                     Ṫ - tail

```
> 2 votes

# Answer
# 05AB1E, 22 bytes

```
0¸Δ¤DIsè+Ig%©ªÙ}D®QÅ¡è

```

Try it online!
> 2 votes

# Answer
# PowerShell Core, ~~156~~ 145 bytes

```
for($v=@();!(($s=$v.IndexOf($i))+1);$i%=$l){$v+=,+$i
$t+=,($u=$args[+$i])
$i+=$u+($l=$args.Count)}if(--$l*$s){$t[$s..$l],$t[0..--$s]}else{$t,@()}

```

Try it online!

Takes a list as parameter.

Returns two lists: loop first then trajectory

Saved:

* 2 bytes by swapping the loop / trajectory in the result
* 2 bytes by reusing `$args[$i]` as `$u`
* 1 byte by merging the declaration and first usage of `$l`
* 3 bytes by not initialising `$i` anymore
* 3 bytes thanks to *mazzy*!

#### Not golfed:

```
$index = 0
$length = $args.Count
for ($indices = @(); ($truncateAt = $indices.IndexOf($index)) -eq -1) {
    $indices += , $index
    $trajectory += , $args[$index]
    $index = ($index + $args[$index] + $length) % $length
}
if (--$length -and $truncateAt) {
    ($trajectory[0..--$truncateAt] -join ','), ($trajectory[++$truncateAt..$length] -join ',')
}
else {
    '', ($trajectory -join ',')
}

```
> 2 votes

# Answer
# jq, 146 bytes

```
length as$l|def x:((.[0]+.[1][-1])%$l+$l)%$l;def n:x as$x|.[1]|index($x);. as$i|[0,[],[]]|until(n;[$i[x],.[1]+[x],.[2]+[$i[x]]])|.[2][:n],.[2][n:]

```

Try it online!
> 2 votes

# Answer
# BQN, 39 bytesSBCS

```
↕∘≠⊸{⊏⟜¨2↑⊒⊸/⊸(+`⊑⊸=)⊸⊔0∾⊑˜⍟⟜⊑≠⊸|+}

```

Try it here.

```
↕∘≠⊸{⊏⟜¨2↑⊒⊸/⊸(+`⊑⊸=)⊸⊔0∾⊑˜⍟⟜⊑≠⊸|+} #  is input,  is indices 0,1,..,length-1
↕∘≠⊸{                                 } # pass indices into the main function as
                                ≠⊸|+  # add indices to the input mod the length
                          ⊑˜⍟⟜⊑        # traverse from the first element a number
                                        #  of steps equal to the length,
                                        #  accumulating results
                        0∾              # prepend 0
           ⊒⊸/⊸(+`⊑⊸=)⊸⊔                # find the first value to repeat and
                                        #  partition by occurrences
         2↑                             # take the first 2 groups
     ⊏⟜¨                               # and use them to index into the input

```
> 2 votes

# Answer
# C (gcc), ~~115~~ 131 bytes

```
f(r,n,o,l,j)int*r,**o,*l;{int*t=malloc(4*n);for(*l=j=0;j+=o[0][(t[j]=++*l)-1]=r[j],!t[j=(j%n+n)%n];);*l-=l[1]=t[j]-1;o[1]=*o+l[1];}

```

Try it online!

Outputs `[prefix, loop]` into `o` and `[len(loop), len(prefix)]` into `l`. Expects these to have allocated enough memory to fit the output (though `o[1]` is discarded).
> 1 votes

---
Tags: code-golf, array
---


title: telgif: inverse figlet

text:
# Question
Title: telgif: inverse figlet
`figlet` is utility that converts plain text to an ascii-art representation for use in banners and the like. For example:

```
$ figlet "CODE GOLF"
  ____ ___  ____  _____    ____  ___  _     _____
 / ___/ _ \|  _ \| ____|  / ___|/ _ \| |   |  ___|
| |  | | | | | | |  _|   | |  _| | | | |   | |_
| |__| |_| | |_| | |___  | |_| | |_| | |___|  _|
 \____\___/|____/|_____|  \____|\___/|_____|_|

$

```

Write a program or function that takes the ascii-art output from `figlet` and returns it to its original plain text.

It may be helpful to you to install `figlet`. I have version 2.2.5 which is what you get if you `sudo apt-get install figlet` on Ubuntu 14.04. This figlet actually has several "fonts". For the purposes of this context, we will just be dealing with the default `standard` font.

Input text will be no more that 80 characters wide, and will have been generated from plain text containing only the uppercase characters and space.

Your program may not call `figlet` or its source code in any way.

### Example

Input:

```
    _    ____   ____ ____  _____ _____ ____ _   _ ___
   / \  | __ ) / ___|  _ \| ____|  ___/ ___| | | |_ _|
  / _ \ |  _ \| |   | | | |  _| | |_ | |  _| |_| || |
 / ___ \| |_) | |___| |_| | |___|  _|| |_| |  _  || |
/_/   \_\____/ \____|____/|_____|_|   \____|_| |_|___|

     _ _  ___     __  __ _   _  ___  ____   ___  ____
    | | |/ / |   |  \/  | \ | |/ _ \|  _ \ / _ \|  _ \
 _  | | ' /| |   | |\/| |  \| | | | | |_) | | | | |_) |
| |_| | . \| |___| |  | | |\  | |_| |  __/| |_| |  _ <
 \___/|_|\_\_____|_|  |_|_| \_|\___/|_|    \__\_\_| \_\

 ____ _____ _   ___     ____        ____  ____   _______
/ ___|_   _| | | \ \   / /\ \      / /\ \/ /\ \ / /__  /
\___ \ | | | | | |\ \ / /  \ \ /\ / /  \  /  \ V /  / /
 ___) || | | |_| | \ V /    \ V  V /   /  \   | |  / /_
|____/ |_|  \___/   \_/      \_/\_/   /_/\_\  |_| /____|

```

Output:

```
ABCDEFGHI
JKLMNOPQR
STUVWXYZ

```

Input:

```
 ____ _____  _    ____   __        ___    ____  ____
/ ___|_   _|/ \  |  _ \  \ \      / / \  |  _ \/ ___|
\___ \ | | / _ \ | |_) |  \ \ /\ / / _ \ | |_) \___ \
 ___) || |/ ___ \|  _ <    \ V  V / ___ \|  _ < ___) |
|____/ |_/_/   \_\_| \_\    \_/\_/_/   \_\_| \_\____/

```

Output:

```
STAR WARS

```

---

Note a previous edit of this question allowed inputs containing upper and lower case letters plus numerals. It was pointed out that this caused several points of ambiguity with certain adjacent character combinations. It became obvious that I needed to rigorously find a set of characters with no such collisions so that the contest is actually doable. At first I tried all lowercase letters plus numerals with this shell one-liner:

```
for t in {0..9}{a..z} {a..z}{a..z} {a..z}{0..9} {0..9}{0..9} ; do figlet $t | tr '\n' ':'; echo ; done | sort | uniq -d | tr ':' '\n'

```

This yielded {`j1`, `jl`} and {`i1`, `il`} as ambiguous pairs. So instead with all uppercase letters (as suggested by @AlexA.), there are no ambiguous pairs:

```
for t in {A-Z} ; do figlet $t | tr '\n' ':'; echo ; done | sort | uniq -d | tr ':' '\n'

```

# Answer
# JavaScript, 946 bytes

```
i=>i.split(/\n *\n/).slice(n=0,-1).map(x=>[...(x=x.split`
`)[0]].map((_,i)=>parseInt([0,1,2,3,4].map(j=>"_/\\|".indexOf(x[j][i])+1).join(""),5)).map((n,i,x)=>o[x.slice(i).map(a=>v=v*5+a,v=0).find(v=>o[v])]||"").join``," 0JiivI1d5JysyKgx0X5qyZegzZfZ9mtZfO3288Q9CboCfG28CkO29Q9J1bg3N2d9pLh0dLfL2sLdwH14uLwdU1b4LkyYbbwY1Y2YhY1fjY1Y2YhY1fjY1Y2YhL3nfY126Y1Y2YhY20dY1Y2YhY1fjY1Y2YhR173PjP2P2P7RgjPjP2Fc6FsFtF1rDpcDhdB1ptBhdExgEfE2sSelvS6ySdwJ5wiSr3S6ySdwJaq4Jc21T8zaT1TrT2kA28bA2sAdwT3vT1TrT2kA1ufA1w2TwcT1TrT2kT1xlT1TrT2kA7ccTv58T1TrT2kT1crT1TrT2kT83tT1TrT2kT1crT1TrT2kO48kQ9CboCfG28CkO29Q9AvrtiA2sAdwA21mA1w2AacxM6z18A2cpp6A2sAdwA21mA1w2AacxA7yngA2sAdwA21mA1w2AacxA1ukibA2sAdwA21mA1w2AacxV1brpkV3V4VdV105jV3V4VdV2e9V3V4VdV105jV3V4VdV4md1V3V4VdV105jV3V4VdAruayA2sAdwA21mA1w2AacxAgc25A2sAdwA21mA1w2AacxWozq07rW3W4WdW3hl3vW3W4WdW8de5W3W4WdW3hl3vW3W4WdWg1p5dW3W4WdW3hl3vW3W4Wd".split(/(?=[A-Z ])/).map(x=>o[n+=parseInt(x.slice(1),36)]=x[0],o={})).join`
`

```

Try it online!

Note that `figlet` by default outputs two trailing blank lines; if those can be assumed to not exist, like in the challenge examples, the initial `slice` can be removed for -10 bytes. Otherwise, make sure the blank lines are present in the "Input" field on TIO, or the last line of output will be omitted.

## Explanation

At a high level, this scans the strings for patterns, and outputs the ones it finds.

A single character can have multiple patterns; for example, these are all valid patterns for `A`: (the first and last column are omitted, as they are not necessary for matching)

```
   _
  / \
 / _ \
/ ___ \
_/   \_

```

```
_  _
_|/ \
 / _ \
/ ___ \
_/   \_

```

```
 _____
/ / \ \
 / _ \
/ ___ \
_/   \_

```

The first appears in bare `A`s, or uncombined `A`s such as in `AX`, the second appears in `TA`, and the third appears in e.g. `WAV`:

```
    _      _____  _     __        _____     __
   / \    |_   _|/ \    \ \      / / \ \   / /
  / _ \     | | / _ \    \ \ /\ / / _ \ \ / /
 / ___ \    | |/ ___ \    \ V  V / ___ \ V /
/_/   \_\   |_/_/   \_\    \_/\_/_/   \_\_/
 -------       -------           -------

```

Thus, for every character, there is a pattern for:

* Each triplet of characters with it at the center
* Each pair of characters containing it
* It on it's own

Some of these patterns are identical, for example, the `A`s in `VAV` and `WAV` are identical, and the `A`s in `AX`, `XA`, and `A` are identical.

Each pattern needs a unique representation, and since this is code golf, it should be as compact as possible.

Because the mega-characters have a fixed height of 5, but are not fixed-width, the patterns are defined principally by columns.

First, each of the symbols in the pattern are converted to a single base-5 digit, where  `_/\|` respectively correspond to 0-4, and other symbols are treated as spaces.

```
   _
  / \
 / _ \
/ ___ \
_/   \_

0001000
0020300
0201030
2011103
1200032

```

Then, the 5 base-5 digits in a column are combined to make a single base-5 number.

```
00021, 00202, 02010, 10110, 03010, 00303, 00032

```

Represented in decimal, the column numbers are `11, 52, 255, 655, 380, 78, 16`.

These numbers must be combined into one number that identifies the pattern. The correct way would be to concatenate all of the base-5 numbers (or, equivalently, to treat the list of column numbers as a base-3125 number).

As this is , the correct way will not be used, due to a bug that happened to not break stuff for this set of patterns and is now considered a byte-saving feature.

Thus, the column numbers are combined into one number that identifies the pattern:

```
   11 * 5^6
+  52 * 5^5
+ 255 * 5^4
+ 655 * 5^3
+ 380 * 5^2
+  78 * 5^1
+  16 * 5^0

= 585531

```

Now, these numbers are inserted into a giant lookup table, along with `0` for :

```
{
  0: " ",
  585531: "A",
  591231: "A",
  // ...
}

```

At this point, the table could be serialized and plopped into the code, but it is not very golfy. Thus, this explanation branches into two parts: matching the patterns and compressing the lookup table.

## Matching the Patterns

Matching the patterns is fairly simple. First, the input is split into paragraphs; each paragraph is a line of mega-text. The paragraphs/mega-lines are converted independently, and then joined again with newlines.

Each mega-line is first converted into an array of column numbers:

```
  ____ ___  ____  _____    ____  ___  _     _____
 / ___/ _ \|  _ \| ____|  / ___|/ _ \| |   |  ___|
| |  | | | | | | |  _|   | |  _| | | | |   | |_
| |__| |_| | |_| | |___  | |_| | |_| | |___|  _|
 \____\___/|____/|_____|  \____|\___/|_____|_|

[
  120, 253, 746, 756, 756, 871, 253, 746, 756,
  746, 377, 624, 626, 746, 756, 746, 377, 624,
  626, 771, 781, 856, 756, 504,   0, 120, 253,
  746, 756, 771, 776, 624, 253, 746, 756, 746,
  377, 624, 626, 621,   6,   6,   6, 624, 626,
  729, 780, 770, 750, 500
]

```

Then, this array is iterated across; for every number in the array:

1. If this number is in the lookup table, add the corresponding character to the string and continue iteration.
2. Multiply the number by `5`, and add the next number in the array. Go to #1, and repeat until the number matches or there are no numbers left.

Note that it searches for a character starting at every column, regardless of the previous matches. Additionally, the only way it finds no character starting at a column is if it exhaustively checks all possible ending columns to the end of the array, completely ignoring the fact that no patterns are longer than 12 columns.

After this highly inefficient process completes, the string will be `CODE GOLF`.

## Compressing the Lookup Table

If the lookup table were simply serialized, it would be a whopping 23,094 bytes, which is clearly unacceptable.

The lookup table is transformed as follows:

```
Original:
  0: " "
  12: A
  63: B
  209: A
  1040: C
  30: A
  512: C

Sorted:
  0: " "
  12: A
  30: A
  63: B
  209: A
  512: C
  1040: C

Difference from last:
  +0: " "
  +12: A
  +18: A
  +33: B
  +146: A
  +303: C
  +528: C

Final (numbers are encoded in base 36):
  " 0AcAiBxA42C8fCeo"

```

The final string is:

```
 0JiivI1d5JysyKgx0X5qyZegzZfZ9mtZfO3288Q9CboCfG28CkO29Q9J1bg3N2d9pLh0dLfL2sLdwH14uLwdU1b4LkyYbbwY1Y2YhY1fjY1Y2YhY1fjY1Y2YhL3nfY126Y1Y2YhY20dY1Y2YhY1fjY1Y2YhR173PjP2P2P7RgjPjP2Fc6FsFtF1rDpcDhdB1ptBhdExgEfE2sSelvS6ySdwJ5wiSr3S6ySdwJaq4Jc21T8zaT1TrT2kA28bA2sAdwT3vT1TrT2kA1ufA1w2TwcT1TrT2kT1xlT1TrT2kA7ccTv58T1TrT2kT1crT1TrT2kT83tT1TrT2kT1crT1TrT2kO48kQ9CboCfG28CkO29Q9AvrtiA2sAdwA21mA1w2AacxM6z18A2cpp6A2sAdwA21mA1w2AacxA7yngA2sAdwA21mA1w2AacxA1ukibA2sAdwA21mA1w2AacxV1brpkV3V4VdV105jV3V4VdV2e9V3V4VdV105jV3V4VdV4md1V3V4VdV105jV3V4VdAruayA2sAdwA21mA1w2AacxAgc25A2sAdwA21mA1w2AacxWozq07rW3W4WdW3hl3vW3W4WdW8de5W3W4WdW3hl3vW3W4WdWg1p5dW3W4WdW3hl3vW3W4Wd

```

I haven't done much , so if anyone has ideas on how to compress this further, I'd love to hear them.
> 11 votes

---
Tags: code-golf, ascii-art
---


title: Wicka-wub a string

text:
# Question
Title: Wicka-wub a string
*Inspired by this.*

Given a string as input consisting of only upper and lowercase alphabet characters, **wicka-wub** it.

### How do I wicka-wub a string?

The example text used is "DJMcMayhem".

Split the string before each capital letter, so you get `["D", "J", "Mc", "Mayhem"]`.

Next, take the two halves of the list as sublists. This gives us `[["D", "J"],["Mc", "Mayhem"]]`. If the list is an odd length (i.e. 3), the first sublist will contain the middle substring (i.e. `[[a,b], [c]]`).

Create a list of `wicka`s and `wub`s. The number of `wicka`s should be as many as the length of the first part of the input list (i.e. `["D", "J"] -> ["wicka", "wicka"]`), and the number of `wubs` should be as many as the length of the second part of the input list. In our case, this gives `["wicka", "wicka", "wub", "wub"]`.

Now join the sublists of the input list into single strings and flatten.

We currently have `["DJ", "McMayhem"]` and `["wicka", "wicka", "wub", "wub"]`.

Join the `wicka`/`wub` list with `-`s: `wicka-wicka-wub-wub`. Prepend a `-`. If there is more than one capital letter in the input, append another `-`.

Now we have `["DJ", "McMayhem"]` and `"-wicka-wicka-wub-wub-"`.

Append the `wicka-wub` string to the end of the first item in the input list, to get `["DJ-wicka-wicka-wub-wub-","McMayhem"]`.

Lastly, repeat the characters in the second part of the string by their 0-indexed value in the original input string. In our example, that means the first `M` would be repeated twice, then the `c` three times, and the next `M` four times. Join the list, so the second part (the part you just repeated letters in) is appended to the first part (`"DJ-wicka-wicka-wub-wub-"`).

Final result of input:

```
"DJ-wicka-wicka-wub-wub-MMcccMMMMaaaaayyyyyyhhhhhhheeeeeeeemmmmmmmmm"

```

Total process:

```
["D", "J", "Mc", "Mayhem"] =>
[["D", "J"], ["Mc", "Mayhem"]] =>
["DJ", "McMayhem"] and ["wicka", "wicka", "wub", "wub"] =>
["DJ", "McMayhem"] and "-wicka-wicka-wub-wub-" =>
["DJ-wicka-wicka-wub-wub-", "McMayhem"] =>
"DJ-wicka-wicka-wub-wub-MMcccMMMMaaaaayyyyyyhhhhhhheeeeeeeemmmmmmmmm"

```

## Your task

Your task is, given a string that consists of only upper and lowercase alphabet characters, output the wicka-wubbed version of that string.

## A few rules

* The input may consist entirely of lowercase letters, or entirely of uppercase letters, or any number of each, but no other characters.
* If the input consists of entirely lowercase letters the correct output should simply be the final stage (the string with the characters repeated according to their 0-indexed position). There should be no `wicka` or `wub` in that case.
* Standard rules apply, full programs or functions, up to you.
* This is a so shortest code wins.

`GoodLuck-wicka-wicka-wub-GGGGGGGGooooooooollllllllllfffffffffffeeeeeeeeeeerrrrrrrrrrrrrssssssssssssss`

## Test cases

```
input => output

DJMcMayhem => DJ-wicka-wicka-wub-wub-MMcccMMMMaaaaayyyyyyhhhhhhheeeeeeeemmmmmmmmm
PPCG => PP-wicka-wicka-wub-wub-CCGGG
foobarbaz => fooooobbbbaaaaarrrrrrbbbbbbbaaaaaaaazzzzzzzzz
FooBarBaz => FooBar-wicka-wicka-wub-BBBBBBaaaaaaazzzzzzzz
HelloWorld => Hello-wicka-wub-WWWWWoooooorrrrrrrllllllllddddddddd
Test => Test-wicka
UPPER => UPP-wicka-wicka-wicka-wub-wub-EEERRRR
fooBarBaz => fooBar-wicka-wicka-wub-BBBBBBaaaaaaazzzzzzzz

```

# Answer
# Perl 5, 142 bytes

**130 bytes code + 12 for `-F(?=[A-Z])`.**

This now correctly matches all the test cases provided.

```
map$a+=y///c,@E=($z=/[A-Z]/)?splice@F,0,@F/2+.5:();print@E,("-wicka"x@E,"-wub"x@F,"-"x!!@F)x$z,map$_ x$a++,$z?map/./g,@F:('',/./g)

```

Try it online!

**Note**: TIO includes `-l` to run all tests at once.
> 1 votes

# Answer
# Java 8 (782 bytes)

```
import com.google.common.collect.*;import java.util.*;import java.util.function.*;public class p{Function<String,String>b=s->{List<String>p=Arrays.asList(s.split("(?=[A-Z])"));if(!s.matches("[^A-Z]*[A-Z].+")){String w="";int i=0;for(char c:String.join("",s).toCharArray()){w+=String.join("",Collections.nCopies(i,Character.toString(c)));i++;}return w;}String h="-";List<List<String>>k;if(p.size()!=1){k=Lists.partition(p,2);String w=String.join("",k.get(0))+h+String.join(h,Collections.nCopies(k.get(0).size(),"wicka"))+h+String.join(h,Collections.nCopies(k.get(1).size(),"wub"))+h;int i=String.join("", k.get(0)).length();for(char c:String.join("",k.get(1)).toCharArray()){w+=String.join("",Collections.nCopies(i,Character.toString(c)));i++;}return w;}return p.get(0)+h+"wicka";};}

```

Ungolfed:

```
import com.google.common.collect.*;

import java.util.*;
import java.util.function.*;

public class p {
    Function<String, String> b = s -> {
        List<String> p = Arrays.asList(s.split("(?=[A-Z])"));

        if (!s.matches("[^A-Z]*[A-Z].+")) {
            String w = "";

            int i = 0;

            for (char c : String.join("", s).toCharArray()) {
                w += String.join("", Collections.nCopies(i, Character.toString(c)));

                i++;
            }

            return w;
        }

        String h = "-";

        List<List<String>> k;

        if (p.size() != 1) {
            k = Lists.partition(p, 2);

            String w = String.join("", k.get(0)) + h + String.join(h, Collections.nCopies(k.get(0).size(), "wicka")) + h + String.join(h,    Collections.nCopies(k.get(1).size(), "wub")) + h;

            int i = String.join("", k.get(0)).length();

            for (char c : String.join("", k.get(1)).toCharArray()) {
                w += String.join("", Collections.nCopies(i, Character.toString(c)));

                i++;
            }
            return w;
        }

        return p.get(0) + h + "wicka";
    };
}

```
> 1 votes

# Answer
# Kotlin 1.1 - ~~494~~ 492 bytes

## Submission

```
typealias S=String
fun Iterable<*>.j(s:S="")=this.joinToString(s)
fun s(s:S):S{var c=0
val m=mutableListOf<S>()
var t=""
s.map{if(it.isUpperCase()){c+=1
if(t!=""){m.add(t)
t=""}}
t+=it}
if(c==0)return e(s,1)
m.add(t)
val p=Math.ceil(m.size/2.0).toInt()
val f=m.subList(0,p)
val z=m.subList(p,m.size)
val w=List(f.size,{"wicka"})
val u=List(z.size,{"wub"})
val x=f.j()
var v="-"+(w+u).j("-")
if(c>1)v+="-"
return x+v+e(z.j(),x.length)}
fun e(s:S,o:Int)=s.mapIndexed{c,i->List(c+o,{i}).j()}.j()

```

## Test

```
typealias S=String
fun Iterable<*>.j(s:S="")=this.joinToString(s)
fun s(s:S):S{var c = 0
val m=mutableListOf<S>()
var t=""
s.map{if(it.isUpperCase()){c+=1
if(t!=""){m.add(t)
t=""}}
t+=it}
if(c==0)return e(s,1)
m.add(t)
val p=Math.ceil(m.size/2.0).toInt()
val f=m.subList(0,p)
val z=m.subList(p,m.size)
val w=List(f.size,{"wicka"})
val u=List(z.size,{"wub"})
val x=f.j()
var v="-"+(w+u).j("-")
if(c>1)v+="-"
return x+v+e(z.j(),x.length)}
fun e(s:S,o:Int)=s.mapIndexed{c,i->List(c+o,{i}).j()}.j()

data class TestData(val input: String, val output: String)

fun main(args: Array<String>) {
    val tests = listOf(
            TestData("DJMcMayhem", "DJ-wicka-wicka-wub-wub-MMcccMMMMaaaaayyyyyyhhhhhhheeeeeeeemmmmmmmmm"),
            TestData("PPCG", "PP-wicka-wicka-wub-wub-CCGGG"),
            TestData("foobarbaz", "fooooobbbbaaaaarrrrrrbbbbbbbaaaaaaaazzzzzzzzz"),
            TestData("FooBarBaz", "FooBar-wicka-wicka-wub-BBBBBBaaaaaaazzzzzzzz"),
            TestData("HelloWorld", "Hello-wicka-wub-WWWWWoooooorrrrrrrllllllllddddddddd"),
            TestData("Test", "Test-wicka"),
            TestData("UPPER", "UPP-wicka-wicka-wicka-wub-wub-EEERRRR"),
            TestData("fooBarBaz", "fooBar-wicka-wicka-wub-BBBBBBaaaaaaazzzzzzzz")
    )

    for (test in tests) {
        var out = s(test.input)
        if (out != test.output) {
            System.err.println("TEST FAILED")
            System.err.println("IN  " + test.input)
            System.err.println("EXP " + test.output)
            System.err.println("OUT " + out)
            return
        }
    }
    println("Test Passed")
}

```

## Running

Works on KotlinLang, but not on TryItOnline as 1.1 is not supported

*Ran through my compressor, saved 2 bytes*
> 1 votes

# Answer
# Vyxal , 64 bytes

```
ꜝ[`(?=[A-Z])`ṡḢ:₅½⌈:‟ẎDƛ`≤ȧka-`;∑$∑‹p^ȯ:ƛ‛≤¶;‹∑∇∑f:ẏ∇∇∑L+*÷|ėvΠ÷

```

Try it Online!

Since the stack manipulation is quite complex, I've added a representation of the stack after each step.

```
ꜝ[             # If any letters are uppercase (example input: DJMcMayhem
  `(?=[A-Z])`ṡ # Split before uppercase letters
               # [['','D','J','Mc','Mayhem']]

Ḣ                  # Lop off the first value
                   # [['D','J','Mc','Mayhem']]
 :₅½⌈              # Duplicate and push ceil(length/2)
                   # [['D','J','Mc','Mayhem'],['D','J','Mc','Mayhem'],2]
     :‟Ẏ           # Push a copy on the bottom and slice from the start
                   # [2,['D','J','Mc','Mayhem'],['D','J']]
        Dƛ`≤ȧka-`; # Triplicate and fill one copy with 'wicka-'
                   # [2,['D','J','Mc','Mayhem'],['D','J'],['D','J'],['wicka-','wicka-']]

∑$∑             # Sum these and sum the pair under that
                # [2,['D','J','Mc','Mayhem'],['D','J'],'wicka-wicka-','DJ']
   ‹p           # Add a hyphen and prepend
                # [2,['D','J','Mc','Mayhem'],['D','J'],'DJ-wicka-wicka-']
     ^ȯ         # Reverse the stack and slice
                # ['DJ-wicka-wicka-',['D','J'],['Mc','Mayhem']]
       :ƛ‛≤¶;‹∑ # Duplicate, fill a copy with 'wub-' and sum that
                # ['DJ-wicka-wicka-',['D','J'],['Mc','Mayhem'],'wub-wub-']

∇∑f          # Shift and turn the full second half into a list of characters
             # ['DJ-wicka-wicka-','wub-wub-',['D','J'],['M','c','M','a','y','h','e','m']]
   :ẏ        # Duplicate and make a range of 0...length
             # ['DJ-wicka-wicka-','wub-wub-',['D','J'],['M','c','M','a','y','h','e','m'],[0,1,2,3,4,5,6,7]]
     ∇∇∑L+   # Get the full length of the first half and add it to each item of this range
             # ['DJ-wicka-wicka-','wub-wub-',['M','c','M','a','y','h','e','m'],[2,3,4,5,6,7,8,9]]
          *÷ # Multiply (repeat) (vectorising) and iterate out over the stack
             # ['DJ-wicka-wicka-','wub-wub-','MM','ccc','MMMM','aaaaa','yyyyyy','hhhhhhh','eeeeeeee','mmmmmmmmm']
             # Then the Ṫ flag smash-prints this.

|     # Else...
 ė    # Enumerate (zip with range to length)
  vΠ  # Reduce each by multiplication
    ÷ # Iterate (push each to the stack)
      # Then the Ṫ flag smash-prints this.

```
> 1 votes

# Answer
# Python 3, ~~234~~ ~~281~~ ~~270~~ ~~248~~ 246 bytes

```
s,j=input(),"".join;f=lambda l,n:j(c*i for i,c in enumerate(j(l),n));import re;u=re.split("([A-Z])",s);l=len(u)
m=[j(u[i:i+2])for i in range(1,l,2)];i=-~l//4;d=j(m[:i]);print((j([d+"-wicka"*i+"-wub"*(l//2-i)+"-",f(m[i:],len(d))]),f(u[0],1))[l<2])

```

Try it online!

*Added 47 bytes, thanks to Mr. Xcoder ;)*

*Saved 11 bytes thanks to Jonathan Frech*

*Saved 22 bytes thanks to Halvard Hummel*

*Saved 2 more bytes thanks to Mr. Xcoder*
> 0 votes

---
Tags: code-golf, string
---


title: Chunky palindromes

text:
# Question
Title: Chunky palindromes
Palindromes are fun, but some of the other strings are starting to feel left out. We can turn those strings into *chunky palindromes* by splitting them up into palindromic arrays of chunks.

For example, the string `"abcabca"` isn't a palindrome if we read it character by character, but we have three different ways of making it a *chunky* palindrome:

```
["abcabca"]
["a" "bcabc" "a"]
["a" "bc" "a" "bc" "a"]

```

As you can see, chunky palindromicness is a very inclusive concept; every string can be turned into a chunky palindrome in at least one way.

### Task

Write a program or a function that receives a string as input and returns its *palindromic chunkiness*, i.e., the number of its partitions that are palindromic arrays.

### Test cases

```
 OUTPUT | INPUT
--------+---------------------------------------------
      1 | ""
      1 | "a"
      1 | "ab"
      2 | "aa"
      2 | "aaa"
      3 | "abcabca"
      4 | "abababab"
     28 | "abcabcaabababababcabca"
      1 | "bbbbabababbbbababbbaaaaa"
     20 | "ababbaaaabababbbaaabbbaa"
      5 | "baaabaabababaababaaabbaab"
     62 | "bbaaababbabbabbbabaabaabb"
      2 | "a man a plan a canal panama"
     25 | "ama nap lan aca nal pan ama"
     93 | "SATOR   AREPO   TENET   OPERA   ROTAS"
    976 | "abcabcaabcabcaabcabcaabcabcaabcabcaabcabca"
  28657 | "ababababababababababaababababababababababa"
2097152 | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

```

### Additional rules

* You may assume that the input will consist of 42 or less printable ASCII characters, optionally surrounded by your language's string delimiters and/or followed by a newline.
* For each valid input string, **your code must finish in less than one minute on my machine** (Intel Core i7-3770, 16 GiB RAM, Fedora 21).

With an adequate algorithm, it should be easy to comply with this time limit. However, you will most likely not be able to iterate over all partitions of the input string.
* If you choose to print the output to STDOUT, it may be followed by a single newline.
* Standard rules apply.

# Answer
# Pyth, ~~40~~ ~~34~~ ~~27~~ 22 bytes

```
Lhsmy:bd_df!xb>TbS/lb2

```

Try it in the online interpreter.

Heavily golfed down from initial 40 byte version. Thanks to FryAmTheEggman for pointing out a couple of useful operators (docs are hard to search!) that have saved me 6 bytes total. Thanks to Dennis for a clever single byte saving by interpreting the result of `x` as a truthy/falsy value rather than an index - `!xb>Tb` rather than `q<bT>Tb`.

---

How it works:

We define a function `y` which determines the chunkiness of a string `b` by recursively calling itself on substrings of `b`. Functions are automatically memoized in Pyth, so recursion has very little overhead in terms of time.

```
L                              def y(b): return ___
                 S/lb2         The range [1,2,...,len(b)/2]
          f!xb>Tb              Filter n for which b[:n] == b[-n:]
   m                           Map each n in the list to...
    y:bd_d                     y(b[d:-d])
 hs                            Take the sum and add one (implicit return)

```
> 5 votes

# Answer
# Pip, ~~98~~ 66 bytes

*-32 thanks to @DLosc!*

```
k:{[[z:a]]AL$AL({b:zc:b@<aAL_M(kb@>a)z:bc}M@>(,#a))}#(_QRV_FI(ka))

```

My first Pip answer!
> 3 votes

# Answer
## CJam (41 39 bytes)

```
qM{_,2/,\f{\~_2$>@2$<@~)/(@=\M*j*}1b)}j

```

Online demo

This is "eager" in the sense that it finds the number of chunky palindromes for each "central" string (i.e. the result of removing the same number of characters from both ends of the original string), but because it uses the auto-memoising `j` operator each is calculated once only, giving a very fast program (and saving a few characters over a non-memoised implementation).

Thanks to Dennis for a one byte saving.
> 2 votes

# Answer
# Mathematica, ~~77~~ ~~72~~ 57 bytes

```
1+Tr[#0/@ReplaceList[#,{a__,b___,a__}:>{b}]]&@*Characters

```
> 1 votes

# Answer
# Perl, 86 bytes

84 bytes code + 2 switches

There HAS to be a shorter method, but here goes:

```
perl -lpe 'sub c{my($x,$i)=@_;$x=~/^(.{$i})(.*)\1$/&&c($2,0*++$s)while++$i<length$x}c$_;$_=++$s'

```

Takes input from STDIN, one string per line.

Explanation: For values `1<=$i<length(input string)`, uses the regex `/^(.{$i})(.*)\1$/` to get the left and right chunks and increments the count. Then recursively does the same for the center part of the string.
> 1 votes

---
Tags: code-golf, string, palindrome, set-partitions, restricted-time
---