2x2x2 Rubik's cube

[EvilBro]

Ik heb meer "Rubik's cubes" dan een normaal mens nodig heeft (meer dan nul dus). Een van de kubussen die ik heb is een Pocket cube. Nu vroeg ik mij af hoeveel stappen je maximaal nodig hebt om de kubus op te lossen. Nou zou ik natuurlijk de wiki-pagina kunnen lezen en dan staat daar dat je maximaal 14 kwart-slagen nodig hebt (11 als je ook half-slagen toestaat), maar helaas heb ik bedacht dat ik het zelf uit wil rekenen.

Hoe ik dit aanpak: ik begin met een opgeloste Pocket cube. Nu genereer ik 6 nieuwe toestanden door het rechtervlak met de klok mee te draaien en tegen de klok in te draaien, en zo ook met het achtervlak en het ondervlak. Ik heb nu alle toestanden die ik vanuit de opgeloste kubus kan bereiken.

Nu herhaal ik de procedure voor elk van de nieuwe toestanden. Hiermee vind ik de kubustoestanden op afstand 2 van de oplossing. Dit proces herhaal ik, waarbij ik eerder gepasseerde toestanden negeer, totdat er geen nieuwe toestanden meer ontstaan.

Mijn haskell-programma:

Code: Selecteer alles

import qualified Data.Set as Set

cube2x2 = [(2,-1,1,0),(2,1,1,1),(2,1,-1,2),(2,-1,1,3),(-2,-1,1,4),(-2,1,1,5),(-2,1,-1,6),(-2,-1,1,7)]

rotateR = map (\(x,y,z,n) -> if (y>0) then (-z,y,x,n) else (x,y,z,n))

rotateRinv = rotateR . rotateR . rotateR

  

rotateD = map (\(x,y,z,n) -> if (z<0) then (-y,x,z,n) else (x,y,z,n))

rotateDinv = rotateD . rotateD . rotateD

rotateB = map (\(x,y,z,n) -> if (x<0) then (x,-z,y,n) else (x,y,z,n))

  

rotateBinv = rotateB . rotateB . rotateB

nextStep (us,ts) = (Set.filter (\a -> False == Set.member a ts) ns, Set.union ts ns)

where

ns = applyfs us [rotateR, rotateRinv, rotateB, rotateBinv, rotateD, rotateDinv]

startSet = (Set.fromList [cube2x2], Set.fromList [cube2x2])

countSteps n (us,ts) | Set.null us = (n, Set.size ts)

 | otherwise = countSteps (n+1) (nextStep (us,ts))

applyfs us [] = Set.empty

applyfs us (f:fs) = Set.union (Set.map f us) (applyfs us fs)

solution = countSteps 0 startSet

En dan nu het probleem: Mijn oplossing wijkt af van wat op wikipedia staat. Ik vermoed dus dat er ergens iets foutgaat bij mij. Het alternatief is dat wiki fout is (acht ik onwaarschijnlijk). Heeft iemand goede suggesties?

[EvilBro]

Ik zie het al. Ik heb bij het definieren van de kubus een fout gemaakt. (2,-1,1,3) moet (2,-1,-1,3) zijn...

[EvilBro]

Hmmmm, stiekem toch niet. Laatste code voor mensen die mee kunnen denken:

Code: Selecteer alles

import qualified Data.Set as Set



cube2x2 = [(2,-1,1),(2,1,1),(2,1,-1),(2,-1,-1),(-2,-1,1),(-2,1,1),(-2,1,-1),(-2,-1,-1)]



rotateR = map (\(x,y,z) -> if (y>0) then (-z,y,x) else (x,y,z))

flipR = rotateR . rotateR

rotateRinv = rotateR . rotateR . rotateR

						  

rotateD = map (\(x,y,z) -> if (z<0) then (-y,x,z) else (x,y,z))

flipD = rotateD . rotateD

rotateDinv = rotateD . rotateD . rotateD



rotateB = map (\(x,y,z) -> if (x<0) then (x,-z,y) else (x,y,z))				  

flipB = rotateB . rotateB

rotateBinv = rotateB . rotateB . rotateB



nextStep (us,ts) = (Set.filter (\a -> not $ Set.member (cubehash a) ts) ns, Set.union ts (Set.map (cubehash) ns))

	where

		 ns = applyfs us [rotateR, rotateRinv, rotateB, rotateBinv, rotateD, rotateDinv]

		

countSteps cube = countSteps' 0 (Set.fromList [cube], Set.fromList [cubehash cube])

countSteps' n (us,ts) | Set.null us = (n, Set.size ts)

					  | otherwise = countSteps' (n+1) (nextStep (us,ts))



applyfs us [] = Set.empty

applyfs us (f:fs) = Set.union (applyfs us fs) (Set.map f us)



cubehash cube =  product [((primes !! a)^(position (cube !! a)))*((primes !! (13-a))^(orientation (cube !! a))) | a <- [0..7]]



primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43]



orientation (x,y,z) | (abs x) == 2 = 0

					| (abs y) == 2 = 1

			   	 | (abs z) == 2 = 2



position (x,y,z) | u == (1,-1,1) = 0

				 | u == (1,1,1)  = 1

				 | u == (1,1,-1) = 2

				 | u == (1,-1,-1) = 3

				 | u == (-1,-1,1) = 4

				 | u == (-1,1,1)  = 5

				 | u == (-1,1,-1) = 6

				 | u == (-1,-1,-1) = 7				

	where

		u = (x `div` (abs x), y `div` (abs y), z `div` (abs z))