melody's stats

fn main() {
	let mut seq = vec![1,2,2];
	let mut i = 2;
	while seq.len() < 100 {
		let n = 3 - seq.last().unwrap();
		let m = seq[i];
		i += 1;
		for _ in 0..m {
			seq.push(n);
		}
	}
	println!("{:?}", &seq[..100]);
	// check validity
	assert_eq!(seq[..100], [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2]);
}

struct Polyomnio(Vec<(i8,i8)>);
impl Polyomnio {
	fn normalize_translation(&mut self) {
		let (min_x, min_y) = self.0.iter().fold((127,127),|(x,y),(z,w)| (x.min(*z),y.min(*w)));
		for (x, y) in &mut self.0 {
			*x -= min_x;
			*y -= min_y;
		}
	}
	fn push_superominos(&self, v: &mut Vec<Polyomnio>) {
		for xy in &self.0 {
			for dxy in [(0,-1),(0,1),(1,0),(-1,0)] {
				let new_xy = (xy.0+dxy.0, xy.1+dxy.1);
				if self.0.contains(&new_xy) { continue; }
				let mut new_polyomino = self.0.clone();
				new_polyomino.push(new_xy);
				v.push(Polyomnio(new_polyomino));
			}
		}
	}
}
impl PartialEq for Polyomnio {
	fn eq(&self, rhs: &Self) -> bool {
		if self.0.len() != rhs.0.len() {
			return false;
		}
		let (max_x, max_y) = self.0.iter().fold((0,0), |(x,y),(z,w)| (x.max(*z),y.max(*w)));
		fn test_under_transformation(a: &Polyomnio, b: &Polyomnio, f: impl Fn(i8,i8)->(i8,i8)) -> bool {
			for xy in &a.0 {
				if !b.0.contains(&f(xy.0, xy.1)) {
					return false;
				}
			}
			true
		}
		test_under_transformation(self, rhs, |x,y| (x,y))
		|| test_under_transformation(self, rhs, |x,y| (max_x-x,y))
		|| test_under_transformation(self, rhs, |x,y| (max_x-x,max_y-y))
		|| test_under_transformation(self, rhs, |x,y| (x,max_y-y))
		|| test_under_transformation(self, rhs, |x,y| (y,x))
		|| test_under_transformation(self, rhs, |x,y| (max_y-y,x))
		|| test_under_transformation(self, rhs, |x,y| (max_y-y,max_x-x))
		|| test_under_transformation(self, rhs, |x,y| (y,max_x-x))
	}
}

fn polyominos_of_size_n(n: usize) -> Vec<Polyomnio> {
	match n {
		0 => return vec![],
		1 => return vec![Polyomnio(vec![(0,0)])],
		_ => (),
	};
	let previous = polyominos_of_size_n(n-1);
	let mut polyominos = vec![];
	for p in previous {
		p.push_superominos(&mut polyominos);
	}
	// translate so min_x == 0 and min_y == 0
	for p in &mut polyominos {
		p.normalize_translation();
	}
	// deduplicate
	for i in (0..polyominos.len()).rev() {
		for j in 0..i {
			if polyominos[i] == polyominos[j] {
				polyominos.remove(i);
				break;
			}
		}
	}
	polyominos
}


fn main() {
	for n in 0..=10 {
		println!("number of {}-omnios: {}", n, polyominos_of_size_n(n).len());
	}
}