Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Ernö Rubiks Zauberwürfelalgorithmen (Algorithmen)

Schreiben Sie ein Programm, das von einem Algorithmus für den Zauberwürfel die Ordnugszahl ermittelt.

Rubiks Cube
 
Die Ordnungszahl ist diejenige Anzahl, wie oft der Algorithmus ausgeführt werden muss, damit der Würfel in seinen Startzustand gelangt. Mit anderen Worten: Wenn ich einen gelösten Würfel habe und immer wieder den selben Algorithmus darauf anwende: Wie lange dauert es, bis der Würfel wieder gelöst ist.

Ein Algorithmus für den Zauberwürfel besteht aus verschiedenen Drehungen. Diese werden meist durch
links
rechts
hinten
vorne
oben
unten
und durch
90, 180 oder 270 Grad Drehungen angegeben.

Natürlich muss noch abgemacht werden ob die mittleren Ebenen auch gedreht werden dürfen, und in welche Richtung jeweils gedreht wird. Doch die Notation überlassen wir in dieser Aufgabe komplett der Programmiererin bzw. dem Programmierer.
Netz des Rubiks-Cube
Schreiben Sie also nun ein Programm, das einen Algorithmus in einer wohldefinierten Notation entgegen nimmt und den Algorithmus solange anwendet, bis der Würfel wieder gelöst ist. Die Ausgabe des Programmes ist dann die Ordnungszahl des Algorithmus.

Wer lernen will, wie man den Rubiks-Cube löst, kann sich hier schlau machen: https://www.youtube.com/watch?v=3hXWa6eeLSE

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

1 Lösung(en)

package ch.programmieraufgaben.algorithmen.rubiks;

import java.util.*;

/**
 * @author phi@gress.ly
 * @date   2018-10-15
 * 
 * a) Change something like "r'U2Xb" to a sequence like
 *    [Move.r_INV, Move.U, Move.U, Move.X, Move.b]
 * b) apply an array of Moves to a cube 
 * c) count how many times you have to apply your algorithmn until
 *    the cube is solved again (grade).
 */

public class CubeAlgorithm {

	public static void main(String[] args) {
		new CubeAlgorithm().top();
	}

	void top() {
		Scanner sc = new Scanner(System.in);
		System.out.println("Bitte Algorithmus eingeben:");
		String algo = sc.nextLine().trim();
		sc.close();
		List<Move> moves = toMoveArray(algo);
		CubeImplementation c = new CubeImplementation();
		apply(c, moves);
		System.out.println(c);
		// move Count until solved again
		long cnt = 1;
		while(! c.isSolved()) {
			apply(c, moves);
			cnt++;
		}
		System.out.println("Algorithm grade: " + cnt + ".") ;
		System.out.println("Move count     : " + cnt*moves.size() + ".");
	}

	public void apply(CubeImplementation c, List<Move> algorithm) {
		for(Move m : algorithm) {
			//System.out.println("Applying " + m);
			c.move(m);
		}
	}

	/**
	 * Converts a Speedcuber String (eg. "RUDU") into a
	 * List of Moves (see enum Move below).
	 */
	public List<Move> toMoveArray(String algorithm) {
		List<Move> algo = new ArrayList<Move>();
		int readPos = 0;
		while(readPos < algorithm.length()) {
			char mv = algorithm.charAt(readPos);
			char modifier = 0; // no Modifier found
			if(readPos < algorithm.length() - 1) {
				modifier = algorithm.charAt(readPos + 1);
				if('\'' != modifier && '2' != modifier) {
					// not a Modifier!
					modifier = 0;
				} else {
					readPos++; // valid modifier found, so increase read pos
				}
			}
			Move move;
			if('\'' == modifier) {
				move = findMoveByNameInverted(mv);
			} else { 
				move = findMoveByName(mv);
			}
			if(null == move) {
				System.out.println("ERROR IN ALGO: " + algorithm  );
				System.out.println("       at pos: " + (readPos+1));
				return null;
			}
			if('2' == modifier) {
				algo.add(move);
			}
			algo.add(move);
			readPos++;
		}
		return algo;
	}

	private Move findMoveByName(char move) {
		Move m = null;
		if('R' == move) m = Move.R;
		if('L' == move) m = Move.L;
		if('B' == move) m = Move.B;
		if('F' == move) m = Move.F;
		if('D' == move) m = Move.D;
		if('U' == move) m = Move.U;

		if('r' == move) m = Move.r;
		if('l' == move) m = Move.l;
		if('b' == move) m = Move.b;
		if('f' == move) m = Move.f;
		if('d' == move) m = Move.d;
		if('u' == move) m = Move.u;

		if('X' == move) m = Move.X;
		if('Y' == move) m = Move.Y;
		if('Z' == move) m = Move.Z;
		if('M' == move) m = Move.M;
		if('E' == move) m = Move.E;
		if('S' == move) m = Move.S;

		if(null == m) {
			System.out.println("ERROR: MOVE UNKNOWN: " + move);
		}
		return m;
	}

	private Move findMoveByNameInverted(char move) {
		Move m = null;
		if('R' == move) m = Move.R_INV;
		if('L' == move) m = Move.L_INV;
		if('B' == move) m = Move.B_INV;
		if('F' == move) m = Move.F_INV;
		if('D' == move) m = Move.D_INV;
		if('U' == move) m = Move.U_INV;

		if('r' == move) m = Move.r_INV;
		if('l' == move) m = Move.l_INV;
		if('b' == move) m = Move.b_INV;
		if('f' == move) m = Move.f_INV;
		if('d' == move) m = Move.d_INV;
		if('u' == move) m = Move.u_INV;

		if('X' == move) m = Move.X_INV;
		if('Y' == move) m = Move.Y_INV;
		if('Z' == move) m = Move.Z_INV;
		if('M' == move) m = Move.M_INV;
		if('E' == move) m = Move.E_INV;
		if('S' == move) m = Move.S_INV;

		if(null == m) {
			System.out.println("ERROR: MOVE UNKNOWN: " + move);
		}
		return m;
	}

} // end of class Cube

enum Move {
	R    , L    , U    , D    , F    , B    , 
	R_INV, L_INV, U_INV, D_INV, F_INV, B_INV,
	r    , l    , u    , d    , f    , b    ,
	r_INV, l_INV, u_INV, d_INV, f_INV, b_INV,

	// M (middle)   Mitte zwischen R & L (Richtung L)
	// E (equator)  Mitte zwischen U & D (Richtung D)
	// S (standing) Mitte zwischen F & B (Richtung F)
	M    , E    , S    ,
	M_INV, E_INV, S_INV,

	// X, wie R, aber ganzer Würfel
	// Y, wie U, aber ganzer Würfel
	// Z, wie F, aber ganzer Würfel
	X,     Y,     Z    ,
	X_INV, Y_INV, Z_INV;

} // end of enum Move

enum Color {
	RED, GREEN, ORANGE, BLUE, WHITE, YELLOW;
} // end of enum Color

class CubeImplementation {

	Color[][] cube;

	public static void main(String[] args) {
		new CubeImplementation().top();
	}

	public CubeImplementation() {
		cube = new Color[12][9];
		// orange:
		cube[3][0] = cube[ 4][0] = cube[ 5][0] =
		cube[3][1] = cube[ 4][1] = cube[ 5][1] =
		cube[3][2] = cube[ 4][2] = cube[ 5][2] = Color.ORANGE;
		// yellow:
		cube[3][3] = cube[ 4][3] = cube[ 5][3] =
		cube[3][4] = cube[ 4][4] = cube[ 5][4] =
		cube[3][5] = cube[ 4][5] = cube[ 5][5] = Color.YELLOW;
		// blue:
		cube[0][3] = cube[ 1][3] = cube[ 2][3] =
		cube[0][4] = cube[ 1][4] = cube[ 2][4] =
		cube[0][5] = cube[ 1][5] = cube[ 2][5] = Color.BLUE;
		// red;
		cube[3][6] = cube[ 4][6] = cube[ 5][6] =
		cube[3][7] = cube[ 4][7] = cube[ 5][7] =
		cube[3][8] = cube[ 4][8] = cube[ 5][8] = Color.RED;
		// green;
		cube[6][3] = cube[ 7][3] = cube[ 8][3] =
		cube[6][4] = cube[ 7][4] = cube[ 8][4] =
		cube[6][5] = cube[ 7][5] = cube[ 8][5] = Color.GREEN;
		// white;
		cube[9][3] = cube[10][3] = cube[11][3] =
		cube[9][4] = cube[10][4] = cube[11][4] =
		cube[9][5] = cube[10][5] = cube[11][5] = Color.WHITE;
	}

	void printNet() {
		System.out.println(this.toString());
	}


	String visible = "rgobwy";
	@Override
	public String toString() {
		String representation = "";
		for(int y = 0; y < 9; y++) {
			for(int x = 0; x < 12; x ++) {
				if(null == cube[x][y]) {
					representation += "-";
				} else {
					representation += visible.charAt(cube[x][y].ordinal());
				}
			}
			representation += '\n';
		}
		return representation;
	}

	void top() {
		if(isConsistent()) {
			System.out.println("Cube initialized");
		} else {
			System.out.println("Error in Cube Initilisition: not Consistent!");
			return;
		}
		printNet();
		int cnt = 1;
		move(Move.Y);
		move(Move.R); move(Move.B); move(Move.L); move(Move.F);
	
		while(! isSolved()) {
			cnt++;
			move(Move.R); move(Move.B); move(Move.L); move(Move.F);
		}
		System.out.println("Used " +4*cnt+ " times the Algorithm = " + cnt + " movements");
	
		printNet();
	}

/** Netz des Cube:
-- -- -- 30 40 50 -- -- -- -- -- -- 
-- -- -- 31 41 51 -- -- -- -- -- -- 
-- -- -- 32 42 52 -- -- -- -- -- -- 
03 13 23 33 43 53 63 73 83 93 A3 B3
04 14 24 34 44 54 64 74 84 94 A4 B4
05 15 25 35 45 55 65 75 85 95 A5 B5
-- -- -- 36 46 56 -- -- -- -- -- --
-- -- -- 37 47 57 -- -- -- -- -- -- 
-- -- -- 38 48 58 -- -- -- -- -- -- 
*/

	public void move(Move m) {
		if(Move.r == m) {
			move(Move.X); move(Move.L);
		}
		if(Move.r_INV == m) {move(Move.r); move(Move.r); move(Move.r);}

		if(Move.f == m) {
			move(Move.Z); move(Move.B);
		}
		if(Move.f_INV == m) {move(Move.f); move(Move.f); move(Move.f);}

		if(Move.l == m) {
			move(Move.X_INV); move(Move.R);
		}
		if(Move.l_INV == m) {move(Move.l); move(Move.l); move(Move.l);}

		if(Move.b == m) {
			move(Move.Z_INV); move(Move.F);
		}
		if(Move.b_INV == m) {move(Move.b); move(Move.b); move(Move.b); }

		if(Move.u == m) {
			move(Move.Y); move(Move.D);
		}
		if(Move.u_INV == m) {move(Move.u); move(Move.u); move(Move.u);}

		if(Move.d == m) {
			move(Move.Y_INV); move(Move.U);
		}
		if(Move.d_INV == m) {move(Move.d); move(Move.d); move(Move.d);}

		if(Move.X == m) {
			move(Move.L_INV); move(Move.M_INV); move(Move.R);
		}
		if(Move.X_INV == m) {move(Move.X); move(Move.X); move(Move.X);}

		if(Move.Y == m) {
			move(Move.D_INV); move(Move.E_INV); move(Move.U);
		}
		if(Move.Y_INV == m) {move(Move.Y); move(Move.Y); move(Move.Y);}

		if(Move.Z == m) {
			move(Move.F); move(Move.S); move(Move.B_INV);
		}
		if(Move.Z_INV == m) {move(Move.Z); move(Move.Z); move(Move.Z);}

		if(Move.E == m) { // Equatorial
			move("37>75>51>13");
			move("47>74>41>14");
			move("57>73>31>15");
		}
		if(Move.E_INV == m) {move(Move.E); move(Move.E); move(Move.E);}

		if(Move.M  == m) { // Middle
			move("43>46>A5>40");
			move("44>47>A4>41");
			move("45>48>A3>42");
		}
		if(Move.M_INV == m) {move(Move.M); move(Move.M); move(Move.M);}

		if(Move.S == m) { // Standing
			move("34>64>94>04");
			move("44>74>A4>14");
			move("54>84>B4>24");
		}
		if(Move.S_INV == m) {move(Move.S); move(Move.S); move(Move.S);}

		if(Move.R_INV == m) {move(Move.R); move(Move.R); move(Move.R);}
		if(Move.L_INV == m) {move(Move.L); move(Move.L); move(Move.L);}
		if(Move.D_INV == m) {move(Move.D); move(Move.D); move(Move.D);}
		if(Move.U_INV == m) {move(Move.U); move(Move.U); move(Move.U);}
		if(Move.F_INV == m) {move(Move.F); move(Move.F); move(Move.F);}
		if(Move.B_INV == m) {move(Move.B); move(Move.B); move(Move.B);}

		if(Move.D == m) { // D = Down
			move("93>B3>B5>95");
			move("A3>B4>A5>94");
			move("83>30>05>58");
			move("84>40>04>48");
			move("85>50>03>38");
		}
		if(Move.B == m) { // B = back, not Bottom!
			move("42>31>40>51");
			move("32>30>50>52");
			move("33>03>93>63");
			move("43>13>A3>73");
			move("53>23>B3>83");
		}
		if(Move.F == m) {
			move("46>57>48>37");
			move("56>58>38>36");
			move("35>65>95>05");
			move("45>75>A5>15");
			move("55>85>B5>25");
		}
		if(Move.L == m) {
			move("24>15>04>13");
			move("23>25>05>03");
			move("33>36>B5>30");
			move("34>37>B4>31");
			move("35>38>B3>32");
		}
		if(Move.R == m) {
			move("64>73>84>75");
			move("63>83>85>65");
			move("53>50>95>56");
			move("55>52>93>58");
			move("54>51>94>57");
		}
		if(Move.U == m) {
			move("33>53>55>35");
			move("43>54>45>34");
			move("42>64>46>24");
			move("32>63>56>25");
			move("52>65>36>23");
		}
		if(! isConsistent()) {
			System.out.println("CubeImpl.move(): inconsistent move: " + m);
		}
	}

	private void move(String seq) {
		String[] seqArr = seq.split(">");
		Color tmp = getColorFromStringDesc(seqArr[seqArr.length - 1]);
		for(int pos = seqArr.length - 1; pos > 0; pos --) {
			Color from = getColorFromStringDesc(seqArr[pos - 1]);
			setColorToStringDesc(seqArr[pos], from);
		}
		setColorToStringDesc(seqArr[0], tmp);
	}


	private void setColorToStringDesc(String pos, Color col) {
		int x = getPosFromStringDesc(pos.charAt(0));
		int y = getPosFromStringDesc(pos.charAt(1));
		cube[x][y] = col;
	}

	private Color getColorFromStringDesc(String pos) {
		int x = getPosFromStringDesc(pos.charAt(0));
		int y = getPosFromStringDesc(pos.charAt(1));
		return cube[x][y];
	}

	private int getPosFromStringDesc(char ch) {
		if('A' == ch || 'a' == ch) return 10;
		if('B' == ch || 'b' == ch) return 11;
		if(ch >= '0' && ch <= '9') {
			return ch - '0';
		}
		System.out.println("ERROR: getPosFromString: " + ch + " not Known Position!");
		return -1;
	}

	public boolean isSolved() {
		if(!allMiddle( 1, 4)) return false;
		if(!allMiddle( 4, 1)) return false;
		if(!allMiddle( 4, 4)) return false;
		if(!allMiddle( 4, 7)) return false;
		if(!allMiddle( 7, 4)) return false;
		if(!allMiddle(10, 4)) return false;
		return true;
	}

	private boolean allMiddle(int xCenter, int yCenter) {
		for(int x = xCenter-1; x <= xCenter+1; x++) {
			for(int y = yCenter-1; y <= yCenter+1; y++) {
				if(cube[x][y] != cube[xCenter][yCenter]) {
					return false;
				}
			}
		}
		return true;
	}

	public Color get(int x, int y) {
		return this.cube[x][y];
	}


	public boolean isConsistent() {
		// check count of each color:
		int reds, greens, blues, oranges, yellows, whites;
		reds = greens = blues = oranges = yellows = whites = 0;
		for(int x = 0; x < 12; x++) {
			for(int y = 0; y < 9; y ++) {
				if(cube[x][y] == Color.RED   ) reds   ++;
				if(cube[x][y] == Color.GREEN ) greens ++;
				if(cube[x][y] == Color.BLUE  ) blues  ++;
				if(cube[x][y] == Color.ORANGE) oranges++;
				if(cube[x][y] == Color.YELLOW) yellows++;
				if(cube[x][y] == Color.WHITE ) whites ++;
			}
		}
		if(9 != reds    || 9 != greens  || 9 != blues ||
		   9 != oranges || 9 != yellows || 9 != whites) {
			System.out.println("color count failed: inconsistent");
			return false;
		}

		return true;
	}	

}  // end of class CubeImplementation
                

Lösung von: Philipp Gressly Freimann (SANTIS Training AG)

Verifikation/Checksumme:

Die Speedcuber-Notation steht z. B. hier:
https://speedcube.de/notation.php

Move    |   Orndungszahl
----------------
RUR'    |   4
RULD    | 315
RUF     |  80
RUF2    |  36
RUUFU   | 420

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 8
Schwierigkeit: Schwer
Webcode: vymw-b4k7
Autor: Philipp Gressly Freimann (SANTIS Training AG)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen