Created
March 13, 2024 17:46
-
-
Save expectancyViolation/4987b10530d11e148e39ee41eb013c06 to your computer and use it in GitHub Desktop.
solve wooden cube
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from dataclasses import dataclass | |
| from itertools import product | |
| from typing import Tuple, Dict | |
| # directions are elements of {-1,0,1}^3 s.t. exactly 1 element is nonzero | |
| def get_dir(i, s): | |
| res = [0, 0, 0] | |
| res[i] = s | |
| return tuple(res) | |
| def to_instruction(dir_, step_len): | |
| for x, axis in zip(dir_, "xyz"): | |
| if x == 0: | |
| continue | |
| direction = "-" if x < 0 else "+" | |
| return f"step {step_len} into {direction}{axis}" | |
| all_directions = [get_dir(i, s) for i in range(3) for s in (-1, 1)] | |
| def dot(t1, t2): | |
| return sum(x * y for x, y in zip(t1, t2)) | |
| def add(d1, d2): | |
| return tuple([x + y for x, y in zip(d1, d2)]) | |
| def gen_nb_inds(dir_): | |
| for i, d in enumerate(all_directions): | |
| if dot(d, dir_) == 0: | |
| yield i | |
| NEIGHBOR_LOOKUP = [{*gen_nb_inds(all_directions[i])} for i in | |
| range(len(all_directions))] | |
| CUBE_SIZE = 3 | |
| def pos_to_index(pos): | |
| if any((x < 0) or (x > CUBE_SIZE - 1) for x in pos): | |
| return -1 | |
| return CUBE_SIZE ** 2 * pos[0] + CUBE_SIZE * pos[1] + pos[2] | |
| @dataclass(frozen=True) | |
| class CubeState: | |
| filled_coords_indices: Tuple[bool, ...] | |
| curr_pos: Tuple[int, int, int] | |
| curr_dir_index: int | |
| def gen_steps(pos: Tuple[int, int, int], dir_ind: int, piece_len: int): | |
| dir_ = all_directions[dir_ind] | |
| for _ in range(piece_len): | |
| pos = add(pos, dir_) | |
| yield pos | |
| def gen_neighbors(cube_state: CubeState, piece_len: int): | |
| for nb_ind in NEIGHBOR_LOOKUP[cube_state.curr_dir_index]: | |
| steps = [*gen_steps(cube_state.curr_pos, nb_ind, piece_len)] | |
| assert len(steps) == piece_len | |
| step_inds = [pos_to_index(s) | |
| for s in steps] | |
| if any(step_ind == -1 for step_ind in step_inds): | |
| continue | |
| if any(cube_state.filled_coords_indices[step_ind] for step_ind in | |
| step_inds): | |
| continue | |
| new_filled = [*cube_state.filled_coords_indices] | |
| for step_ind in step_inds: | |
| new_filled[step_ind] = True | |
| new_state = CubeState(tuple(new_filled), steps[-1], nb_ind) | |
| yield new_state | |
| def gen_initial_states(): | |
| for p in product(range(CUBE_SIZE), repeat=3): | |
| # noinspection PyTypeChecker | |
| pos: Tuple[int, int, int] = tuple(p) | |
| initial_filled = [False] * (CUBE_SIZE ** 3) | |
| initial_filled[pos_to_index(pos)] = True | |
| for dir_index in range(len(all_directions)): | |
| cs = CubeState(filled_coords_indices=tuple(initial_filled), | |
| curr_pos=pos, | |
| curr_dir_index=dir_index) | |
| yield cs | |
| def step(curr_states, piece_len: int, preds: Dict[CubeState, CubeState]): | |
| new_states = set() | |
| for state in curr_states: | |
| for new_state in gen_neighbors(state, piece_len): | |
| new_states.add(new_state) | |
| preds[new_state] = state | |
| return new_states | |
| def gen_solve(cube_seq): | |
| curr_states = [*gen_initial_states()] | |
| preds = {} | |
| for x in cube_seq: | |
| curr_states = step(curr_states, x, preds) | |
| sol = next(state for state in curr_states) | |
| sol_chain = [sol] | |
| while sol in preds: | |
| sol = preds[sol] | |
| sol_chain.append(sol) | |
| # skip last element as initial state has bogus direction | |
| yield from sol_chain[:-1][::-1] | |
| def solve(cube_seq): | |
| for i, (x, step_len) in enumerate(zip(gen_solve(cube_seq), cube_seq)): | |
| inst = to_instruction(all_directions[x.curr_dir_index], step_len) | |
| print(f"STEP {i:02n}:{inst}") | |
| def main(): | |
| cube_seq = (2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2) | |
| solve(cube_seq) | |
| if __name__ == "__main__": | |
| main() |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
STEP 00:step 2 into +z
STEP 01:step 1 into +x
STEP 02:step 1 into -z
STEP 03:step 2 into +y
STEP 04:step 1 into +x
STEP 05:step 2 into -y
STEP 06:step 1 into +z
STEP 07:step 1 into +y
STEP 08:step 2 into -x
STEP 09:step 2 into -z
STEP 10:step 1 into +x
STEP 11:step 1 into -y
STEP 12:step 1 into +x
STEP 13:step 2 into +y
STEP 14:step 2 into -x
STEP 15:step 2 into +z
STEP 16:step 2 into +x