Springen naar inhoud

2x2x2 Rubik's cube


  • Log in om te kunnen reageren

#1

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 12 maart 2013 - 09:15

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:
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?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 12 maart 2013 - 12:29

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

#3

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 12 maart 2013 - 16:09

Hmmmm, stiekem toch niet. Laatste code voor mensen die mee kunnen denken:
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))

Veranderd door EvilBro, 12 maart 2013 - 16:10






0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures