Current Version: 8
Last modified: Monday, September 17, 2:15 am
Changes:
state_checker in regards to the order of cubies and the orientation and permutation of the DBL cornerbowl_a_rama from a list of 12 to 21 integers, inclusive, to a list of 11 to 21 integers, inclusivebowl_a_rama is now a folding question worth 10 points; 1 point is added to every folding question that previously existed;
semiopt_alg is now a karma question; points for part 2 are reducedmedian from int option to float optionbowl_a_rama from a list of 21 integers to a list of 12 to 21 integers, inclusivemode and median from int to int optiondot_product given lists of unequal lengthrec on Part II This problem set has two parts. You should write your solution to each part in a separate file: fold.ml and cube.ml To help get you started, we have provided a stub file for each part on CMS. You should download and edit these files. Once you have finished, submit your solution using CMS, linked from the course website.
Folding is one of the most useful tools in functional programming.
You will use folds many times the semester.
The following exercises are designed to get you comfortable with folds that perform useful computations on lists. Note: All of these functions can be written without folding, but the point of the exercise is to get used to folding, so every function must include a folding function
from the OCaml List library. Note that List.fold_left is tail recursive and List.fold_right is not. For full credit, your solution must not contain the rec keyword.
list_exists using fold, following the same behavior as List.exists.dot_product : int list -> int list -> int that computes the dot product of two vectors inputted as lists.
Recall that the dot product of two vectors is the sum of multiplying their respective components pairwise. For instance, dot_product [1;2;3] [4;5;6] = 1*4 + 2*5 + 3*6 = 32.
Raise an exception Dot_product if the input lists have unequal lengths.
list_flatten tail recursively using fold, following the same behavior as List.flatten (List.flatten is not tail recursive).
mode : int list -> int option that returns the mode of the input list
if a mode exists, and None otherwise.
median : int list -> float option that returns the median of the input list if a median exists and None otherwise. Sorting functions in the List module are not allowed.
bowl_a_rama : int list -> int that uses folding to calculate the score of a game of bowling given a list of how many pins were knocked down for each roll. Assume that the input contains 11 to 21 integers inclusive, and that each integer is between 0 and 10 inclusive. For information on how to score a game of bowling, consult the following helpful resources:
In 1974, Hungarian sculptor and professor of architecture Ernő Rubik invented the Rubik's cube. Since then, millions of copies of the cube and other related twisty puzzles have been sold worldwide. In the non-disjoint set of avid cubers and coders, much computational exploration has been done.
The objective of this part is to construct scramblers and solvers for a Rubik's cube. We will use a 2x2x2 Rubik's cube, since it shares many of the same properties as the 3x3x3 but in the same time much easier to solve.
For full credit, your solutions must not contain the rec keyword.
To be able to talk about cube, we need some definitions. We will use the standard Rubik's cube notation for referring to and turning sides as described here. To summarize:
A scramble is a series of turns applied to a solved cube intended to produce a random state, and an algorithm is a series of turns applied to an arbitrary cube intended to produce another state. Both are represented as turn lists in this assignment.
A 2x2x2 has 8 pieces, as denoted in type piece. Each piece is named by the side intersection in which it lies (eg. UBL = upper back left; DFR = down front right). Note that since all positions are relative, we can always consider one piece to be solved. In this problem set, we take that piece to be DBL, and keep it fixed as other pieces are moved around. This leaves us with 9 possible turns: F, F', F2, U, U', U2, R, R', R2.
To keep track of a cube's state, we need to note two things: orientation and permutation. A corner is a tuple of piece and orientation, and a cubie is defined as a tuple of position and corner. On a solved cube, the piece of the corner is equal to the position in every cubie. For orientation, we consider a corner to be correctly oriented if you can return it to its solved position using only U, R2, and F2. This means that those 3 moves (along with U' and U2) will never affect the orientation. More abstractly speaking, a corner is correctly oriented (O) if a color from either the U or D side is on either the U or D side, oriented clockwise (CW) if you would have to twist a correctly oriented piece 120 degrees clockwise to move the U or D color to where it is, and oriented counterclockwise (CCW) analogously. Note that visual knowledge of orientation is not required to complete this assignment; the function specifications always tell you exactly how to handle each case. Finally, a cube is a list of 8 cubies. A solved cube is represented by:
let solved_cube : cubie list = [(UBL, (UBL,O)); (UBR, (UBR,O)); (UFR, (UFR,O)); (UFL, (UFL,O)); (DBL, (DBL,O)); (DBR, (DBR,O)); (DFR, (DFR,O)); (DFL, (DFL,O))]
Note that the order does not matter, since all cubies tell you where on the cube they are. You may however find it useful to enforce an order, which can be useful when comparing whether two cubes have the same state. For the purpose of this assignment, only worry about random ordering of cubies for the input to state_checker.
Have you ever taken apart a Rubik's cube and randomly reassembled the pieces (surely you did not try peeling the stickers, the much cheaper alternative)? When pieces are randomly put together, it is not guaranteed that the resulting state will be solvable with the allowed turns. Write a function state_checker : cube -> bool that confirms two things: First, ensure that we have a valid cube. Nothing in the type specification forces the cubie list to be of length 8, nor that we have all 8 positions and all 8 corners present. Second, while any permutation of pieces on a 2x2x2 is possible, the same is not true for orientations (useful link; only rule 3 applies to 2x2x2 cubes). In fact, only two "types" of orientations are possible: either 3 corners can all be rotated in the same direction (all CW or all CCW), or a two corners can each be rotated in the opposite direction (one CW and one CCW, or vice versa), or some composition of them. For example, if we find that exactly 2 corners had orientation CW, we know it is not a valid cube state. Similarly, if there are two with orientation CW, and another with orientation CCW, it is not a valid state.
Update: Recall that the order of cubies does not matter in our representation of the cube. Therefore, you should not expect the cubies to be of a certain order. That being said, only worry about the order of cubies in this function. For other functions in this assignment, the positions of cubies in the input cube will be in the same order as solved_cube shown above. Also, recall that the DBL cubie is fixed. As a result, there should always be a (DBL, (DBL,O)) cubie in a valid cube state.
Now we have a checker for valid cube states, let's make it possible to apply turns on a cube. Write a function move : cube -> turn -> cube that given a cube and a turn will return the result of performing the turn on the input cube. To aid you, below are expected outputs to all single turns on a solved cube:
| Turn | Result |
|---|---|
| R | [(UBL, (UBL, O)); (UBR, (UFR, CW)); (UFR, (DFR, CCW)); (UFL, (UFL, O)); (DBL, (DBL, O)); (DBR, (UBR, CCW)); (DFR, (DBR, CW)); (DFL, (DFL, O))] |
| R' | [(UBL, (UBL, O)); (UBR, (DBR, CW)); (UFR, (UBR, CCW)); (UFL, (UFL, O)); (DBL, (DBL, O)); (DBR, (DFR, CCW)); (DFR, (UFR, CW)); (DFL, (DFL, O))] |
| R2 | [(UBL, (UBL, O)); (UBR, (DFR, O)); (UFR, (DBR, O)); (UFL, (UFL, O)); (DBL, (DBL, O)); (DBR, (UFR, O)); (DFR, (UBR, O)); (DFL, (DFL, O))] |
| U | [(UBL, (UFL, O)); (UBR, (UBL, O)); (UFR, (UBR, O)); (UFL, (UFR, O)); (DBL, (DBL, O)); (DBR, (DBR, O)); (DFR, (DFR, O)); (DFL, (DFL, O))] |
| U' | [(UBL, (UBR, O)); (UBR, (UFR, O)); (UFR, (UFL, O)); (UFL, (UBL, O)); (DBL, (DBL, O)); (DBR, (DBR, O)); (DFR, (DFR, O)); (DFL, (DFL, O))] |
| U2 | [(UBL, (UFR, O)); (UBR, (UFL, O)); (UFR, (UBL, O)); (UFL, (UBR, O)); (DBL, (DBL, O)); (DBR, (DBR, O)); (DFR, (DFR, O)); (DFL, (DFL, O))] |
| F | [(UBL, (UBL, O)); (UBR, (UBR, O)); (UFR, (UFL, CW)); (UFL, (DFL, CCW)); (DBL, (DBL, O)); (DBR, (DBR, O)); (DFR, (UFR, CCW)); (DFL, (DFR, CW))] |
| F' | [(UBL, (UBL, O)); (UBR, (UBR, O)); (UFR, (DFR, CW)); (UFL, (UFR, CCW)); (DBL, (DBL, O)); (DBR, (DBR, O)); (DFR, (DFL, CCW)); (DFL, (UFL, CW))] |
| F2 | [(UBL, (UBL, O)); (UBR, (UBR, O)); (UFR, (DFL, O)); (UFL, (DFR, O)); (DBL, (DBL, O)); (DBR, (DBR, O)); (DFR, (UFL, O)); (DFL, (UFR, O))] |
What good does moving do if we don't have scrambles? We will implement two scrambling functions here, one returning all possible scrambles, and the other returning one randomly generated scramble.
gen_scrambles (9 pts)
A scramble is any sequence of turns. Write a function gen_scrambles : int -> bool -> scramble list such that gen_scrambles n b returns a list of scrambles of length n. If the boolean argument to gen_scrambles is true, then you should return all length n combinations of R, R', R2, etc. However, note that applying, say, the turn R followed by the turn R' is an identity — we can cancel them out. Similarly, note that an F followed by an F is the same as an F2, and a U followed by a U2 is the same as a U', and so on. Therefore, if the bool argument is false, you must take this into account for counting moves: [R; U; R; U; R; U] is still of length 6, but in [R; U; F'; U; U'; F2], we can cancel the U and U' and then combine the F' and F2, giving [R; U; F] — a length 3 scramble.
gen_scramble (4 pts)
For practicing solves, cubers like to perform a randomly generated scramble on a solved cube. Write a function gen_scramble : int -> scramble that produces a random scramble of length specified by the int. You may find the OCaml standard Random module useful. You should reduce moves in this part, as you do for gen_scrambles with a false bool argument.
Now that we have a cube and know how to make moves on it, let's try to solve one from any valid state! While there are many methods to solve a Rubik's cube, here we use two of them (one in part 2, one in karma).
The first method (orient_cube_alg, permute_cube_alg, solve_cube_alg) is one of the simplest and most procedural approaches, and it involves using conjugates. We solve the cube in two big steps: orienting all corners, then permuting all corners. The idea is that we solve the cube bit by bit, making a little progress every time toward the finish. Once you know what action needs to be applied to which corners, the hardest part is how to do it. For example, you know that the current corner at UBR has orientation CW and needs to be twisted counterclockwise, and current corner at DFR is CCW and needs to be twisted clockwise, but how do you twist them? This is where conjugate comes to play. Using an algorithm (get_setup_moves UBR DFR), we can bring the two pieces to UFL and UFR respectively while preserving their orientations. Then we use an algorithm (orient_corners) that twists UFL counterclockwise, and UFR clockwise. Finally, we use the inverse of the setup moves to revert corners back to their previous positions, but in their new orientations. In fact, we can keep on using this technique until every corner is oriented correctly. Similar process can be used for permuting corners. For example, the current corner at UFR belongs to UBR. Using an algorithm (get_setup_moves UFR UBR), we can move the two corners at the two positions to UFL and UFR, respectively, while preserving their orientations. This time, we use an algorithm (permute_corners) that swaps the corners at UFL and UFR, then again undo the setup moves to return the two corners to their former positions. As with orienting corners using conjugates, we can permute corners in this fashion until all corners are in the correct positions.
Below are the functions you have to implement for part 2:
gen_inverse_algorithm (3 pts)
Each turn has an inverse. If you perform R and then R', you get an identity, just as if you apply U2 and then another U2. Write a function gen_inverse_algorithm : algorithm -> algorithm that given an algorithm, will return its inverse. That is, if scr is a scramble, then apply_scramble (scr @ (gen_inverse_algorithm scr)) gives you a solved cube (bad coding style used for ease of illustration).
gen_conjugate_algorithm (2 pts)
We have implemented a working gen_conjugate_algorithm for you. However, the current implementation uses the "@" operator, which is often not the ideal way to concatenate lists together, especially on big lists. Reimplement this function to be tail recursive.
orient_cube_alg (12 pts)
Write a function orient_cube_alg : cube -> algorithm that given a cube, returns an algorithm that when applied, makes all cubies on the input cube have the correct orientations.
permute_cube_alg (12 pts)
Write a function permute_cube_alg : cube -> algorithm that given a cube, returns an algorithm that when applied, makes all cubies on the input cube have the correct permutations.
solve_cube_alg (2 pts)
Write a function solve_cube_alg : cube -> algorithm that given a cube, returns an algorithm that when applied, makes all cubies on the input cube have the correct orientations and permutations.
semiopt_algWrite a function semiopt_alg : cube -> algorithm that given a cube, returns an 11-move algorithm that when applied, makes all cubies on the input cube have the correct orientations and permutations.
This method (semiopt_alg) is unlikely to be achievable by hand, and instead requires assistance from computers. The orientation-permutation method, while correct, often requires over 100 moves overall to complete. However, it has been proven that a 2x2x2 cube in any state can be solved using 11 moves or fewer. In this problem set, we will implement a function that always returns a solution of 11 moves (assume that there is an 11-move solution to all 2x2x2 states).
One way to solve is exhaustively searching all possible 11 moves starting from the scrambled state, and check if any reaches the solved state. This is computationally very expensive though. A clever trick similar to a meet-in-the-middle attack (often used in breaking crypto systems) can be used to speed up the search by a huge factor:
Because hash tables are imperative by nature, we have abstracted away calls to the OCaml Hashtbl module, and you should create and modify hash tables only through the helper functions provided.