11
3
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 code-golf 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
Gareth
Posted 2017-01-25T21:35:39.830
Reputation: 11 678
5Cubular hells – Luis Mendo – 2017-01-25T22:53:21.843