Rust helped me escape Cthulhu!

I just downloaded the game Lovecraft Quest on my Android tablet, and was enjoying the puzzles, until I got to the final one, and that got me, ahem, *frustrated*. I found a walk-through where the reviewers admitted to more or less clicking randomly on the screen for one hour until it worked:

I actually managed to solve the puzzle the first time quickly with sheer luck, but on the second run I was stumped. So I followed the only reasonable course of action: let the computer solve the puzzle for me!

The puzzle is as follows: there is a square (4 rows, 4 columns) of gold bars that can be either in horizontal or vertical position. You can make one bar pivot, but when you do that all the bars in the same row and column pivot too! You need to get all bars to the vertical position for the door to open to reveal... Cthulhu itself!

So let us use Rust for this puzzle, and see if a brute force approach can work. 
Let's first define a few types. A grid is a 4x4 array of booleans and a position is a tuple. We'll have positions ranging from (0,0) to (3,3). A grid is solved is all elements are true (so true means vertical position for a bar).

	pub type Grid = [[bool;4];4];
	pub type Pos = (usize,usize);
	fn is_solved(grid: Grid) -> bool {
	grid.iter().all(|r| r.iter().all(|c| *c))
	}

view raw lib.rs hosted with ❤ by GitHub

Then let's implement the swapping operation. We'll take one Grid reference and return a new Grid with the proper bars swapped.

	fn swap(grid: &Grid, pos: Pos) -> Grid {
	let mut grid = grid.clone();
	for a in 0..4 {
	grid[pos.0][a] = !grid[pos.0][a];
	}
	for a in 0..4 {
	grid[a][pos.1] = !grid[a][pos.1];
	}
	grid[pos.0][pos.1] = !grid[pos.0][pos.1];
	grid
	}

view raw lib.rs hosted with ❤ by GitHub

Note that we swap again the position we chose since we swapped it twice already, one for the columns and once for the rows. Not very elegant maybe but simple

The main solving function is as follows: we're given a grid and we return a list of positions to swap to solve the puzzle. If the grid is already solved we return an empty vec. Otherwise we keep two structures: a map of grids to a vector of positions (showing how we got to that particular grid from the start grid) and a list of grids to process. We use a Deque here so we can put new grids at the end but process grids from the start, to do a breadth-first traversal of all possible grids.

	use std::collections::HashMap;
	use std::collections::VecDeque;
	pub fn solve(grid: Grid) -> Vec<Pos> {
	if is_solved(grid){
	return vec!();
	}
	let mut ret = None;
	let mut seen=HashMap::new();
	seen.insert(grid,Vec::new());
	let mut todo=VecDeque::new();
	todo.push_back(grid);
	while ret.is_none(){
	match todo.pop_front(){
	Some(g)=> {
	ret = try_all(&g,&mut seen,&mut todo);
	},
	None=>panic!("no more grids to do"),
	}
	}
	ret.expect("no result!")
	}

view raw lib.rs hosted with ❤ by GitHub

The try_all function will do all possible swaps on the given grid and store all the results with the path used to get to them. We store for all grids the shortest path we used to get to it. New grids get added at the end of the todo list. We return the path if we end up with a winning grid.

	fn try_all(grid: &Grid,
	seen: &mut HashMap<Grid,Vec<Pos>>,
	todo: &mut VecDeque<Grid>
	) -> Option<Vec<Pos>> {
	let path= match seen.get(grid){
	Some(p) => p.clone(),
	None => panic!("no path to grid!")
	};
	for a in 0..4 {
	for b in 0..4 {
	let g =swap(&grid,(a,b));
	let mut path = path.clone();
	path.push((a,b));
	match seen.get(&g){
	Some(v) => if v.len()>path.len() {
	seen.insert(g,path.clone());
	},
	None => {
	seen.insert(g,path.clone());
	todo.push_back(g);
	},
	}
	if is_solved(g){
	return Some(path);
	}
	}
	}
	None
	}

view raw lib.rs hosted with ❤ by GitHub

To simplify calling the program, we'll just pass a string made of 16 characters, with 1s and 0s indicating the position of the bars we see on the screen. Parsing this string into a Grid instance is easy enough with the help of chunks():

	pub fn parse_grid(grid_desc :&str) -> Grid {
	let mut grid: Grid = [[false;4];4];
	grid_desc.chars().collect::<Vec<char>>().chunks(4).
	enumerate().for_each(|(a,cs)| {
	cs.iter().enumerate().for_each(|(b,c)| {
	if *c == '1' {
	grid[a][b]=true;
	}
	})
	});
	grid
	}

view raw lib.rs hosted with ❤ by GitHub

And we can pass then that string as a argument to our binary program, and print the result:

	use lovecraft::{
	solve,
	parse_grid,
	};
	use std::env;
	fn main() {
	let args: Vec<String> = env::args().collect();
	let grid_desc = &args[1];
	let moves = solve(parse_grid(grid_desc));
	println!("{:?}",moves);
	println!("{} moves",moves.len());
	}

view raw main.rs hosted with ❤ by GitHub

In my case, the program ran and gave me the solution: only 12 moves!

This Rust code is probably fairly naive in places, since I only have a couple of weeks of evenings learning it. I'm not too happy with the number of clone() calls I had to add to make the borrow checker happy, on top of the ones I thought I needed anyway. Maybe immutable structures would in fact be easier to use here! Of course this code could be made parallel but since it gave me my answer in a few seconds I didn't need to improve it further.

Happy Rust Hacking!