rtg-path.js

const GENERATOR = 'G';
const MICROCHIP = 'C';
const G = require('generatorics');

class Floor {
	constructor(elements = []) {
		this.generators = [];
		this.microchips = [];
		elements.forEach(({ type, element }) => {
			if (type === GENERATOR) {
				this.generators.push(element);
			} else {
				// Chip
				this.microchips.push(element);
			}
		});
	}

	isValid() {
		const is_empty = !this.generators.length && !this.microchips.length;
		const only_gens = this.generators.length && !this.microchips.length;
		const only_chips = !this.generators.length && this.microchips.length;
		if (is_empty || only_gens || only_chips) {
			return true;
		}

		// Otherwise, check that the mix of chips and gens cancel each other out
		if (this.microchips.length > this.generators.length) {
			// If we have more chips than gens, it has to be invalid
			return false;
		}

		// We have an equal amount of chips, or maybe less, loop through chips and see if we have a matching gen
		for (let element of this.microchips) {
			if (!this.generators.includes(element)) {
				return false;
			}
		}

		// We looped through all chips, if we are here, they had a matching generator, return true
		return true;
	}

	toString() {
		return this.microchips.length + ',' + this.generators.length;
	}

	clone() {
		let new_floor = new Floor();
		new_floor.microchips = this.microchips.slice(0);
		new_floor.generators = this.generators.slice(0);

		return new_floor;
	}

	canMove(chips = 0, generators = 0) {
		return this.microchips.length >= chips && this.generators.length >= generators;
	}

	cloneAndRemove(chips = [], generators = []) {
		let new_floor = this.clone();

		if (chips.length) {
			new_floor.microchips = new_floor.microchips.filter(c => !chips.includes(c));
		}

		if (generators.length) {
			new_floor.generators = new_floor.generators.filter(g => !generators.includes(g));
		}

		return new_floor;
	}

	cloneAndAdd(chips = [], generators = []) {
		let new_floor = this.clone();

		if (chips.length) {
			new_floor.microchips.push(...chips);
		}

		if (generators.length) {
			new_floor.generators.push(...generators);
		}

		return new_floor;
	}
}

class ArrangementNode {
	constructor(elevator, floors, clone = true) {
		this.elevator = elevator;
		this.floors;

		if (clone) {
			this.floors = floors.map(f => f.clone());
		} else {
			this.floors = floors;
		}

		// 0-indexed
		this.MAX_FLOOR = this.floors.length - 1;

		this.str = `${this.elevator};${this.floors.map(f => f.toString()).join(',')}`;
	}

	/**
	 * Returns _valid_ neighbors, along with some optimizations:
	 *
	 * - If we can't move up or down, takes that into consideration.
	 * - If a move results in an invalid state (more chips than generators, if gens is non-zero), does not return that move.
	 * - If our elevator is at floor 2, and floor 1 is empty, does not move down. Similarly if at 3 and floors 2 and 1 are empty.
	 *
	 * Does _not_ take into account previously visted states.
	 */
	getNeighbors() {
		const valid_nodes = [];
		const current_floor = this.floors[this.elevator];

		let directions = [
			{
				direction: this.elevator + 1,
				canMove: this.elevator < this.MAX_FLOOR,
			},
			{
				direction: this.elevator - 1,
				canMove: this.elevator > 0 && this.hasItemsBeneathCurrentPosition(),
			},
		];

		for (let { direction, canMove } of directions) {
			if (canMove) {
				// Chip + Gen
				// @todo rewrite to the `continue` paradigm like the other move types
				if (current_floor.canMove(1, 1)) {
					// If moving both, we _have_ to move same element of the chip and generator
					// So, just loop through chips, find a matching generator (if it exists), and move
					let new_floor;
					let current_floor_removal;
					for (let chip of G.combination(current_floor.microchips, 1)) {
						if (chip.every(c => current_floor.generators.includes(c))) {
							// We have a matching generator, we can move it!

							// Microoptimization, reuse `chip` in place of `generators` array since we are moving the same element
							new_floor = this.floors[direction].cloneAndAdd(chip, chip);
							current_floor_removal = current_floor.cloneAndRemove(chip, chip);
						} else {
							new_floor = undefined;
							current_floor_removal = undefined;
						}

						if (new_floor && current_floor_removal) {
							let new_floors = [];
							for (let i = 0; i < this.floors.length; i++) {
								if (i === this.elevator) {
									new_floors.push(current_floor_removal);
								} else if (i === direction) {
									new_floors.push(new_floor);
								} else {
									new_floors.push(this.floors[i].clone());
								}
							}

							if (this.validateFloors(new_floors)) {
								valid_nodes.push(new ArrangementNode(direction, new_floors, false));
								break;
							}
						}
					}
				}

				// 1 Chip
				if (current_floor.canMove(1)) {
					for (let chip of G.combination(current_floor.microchips, 1)) {
						let new_floor = this.floors[direction].cloneAndAdd(chip);
						if (!new_floor.isValid()) {
							continue;
						}

						let current_floor_removal = current_floor.cloneAndRemove(chip);
						if (!current_floor_removal.isValid()) {
							continue;
						}

						// We we are here, both floors are valid
						let new_floors = [];
						for (let i = 0; i < this.floors.length; i++) {
							if (i === this.elevator) {
								new_floors.push(current_floor_removal);
							} else if (i === direction) {
								new_floors.push(new_floor);
							} else {
								new_floors.push(this.floors[i].clone());
							}
						}

						valid_nodes.push(new ArrangementNode(direction, new_floors, false));
						break;
					}
				}

				// 2 Chips
				if (current_floor.canMove(2)) {
					for (let chips of G.combination(current_floor.microchips, 2)) {
						let new_floor = this.floors[direction].cloneAndAdd(chips);
						if (!new_floor.isValid()) {
							continue;
						}

						let current_floor_removal = current_floor.cloneAndRemove(chips);
						if (!current_floor_removal.isValid()) {
							continue;
						}

						// We we are here, both floors are valid
						let new_floors = [];
						for (let i = 0; i < this.floors.length; i++) {
							if (i === this.elevator) {
								new_floors.push(current_floor_removal);
							} else if (i === direction) {
								new_floors.push(new_floor);
							} else {
								new_floors.push(this.floors[i].clone());
							}
						}

						valid_nodes.push(new ArrangementNode(direction, new_floors, false));
						break;
					}
				}

				// 1 Generator
				if (current_floor.canMove(0, 1)) {
					for (let gen of G.combination(current_floor.generators, 1)) {
						let new_floor = this.floors[direction].cloneAndAdd(undefined, gen);
						if (!new_floor.isValid()) {
							continue;
						}

						let current_floor_removal = current_floor.cloneAndRemove(undefined, gen);
						if (!current_floor_removal.isValid()) {
							continue;
						}

						// We we are here, both floors are valid
						let new_floors = [];
						for (let i = 0; i < this.floors.length; i++) {
							if (i === this.elevator) {
								new_floors.push(current_floor_removal);
							} else if (i === direction) {
								new_floors.push(new_floor);
							} else {
								new_floors.push(this.floors[i].clone());
							}
						}

						valid_nodes.push(new ArrangementNode(direction, new_floors, false));
						break;
					}
				}

				// 2 Generators
				if (current_floor.canMove(0, 2)) {
					for (let gens of G.combination(current_floor.generators, 2)) {
						let new_floor = this.floors[direction].cloneAndAdd(undefined, gens);
						if (!new_floor.isValid()) {
							continue;
						}

						let current_floor_removal = current_floor.cloneAndRemove(undefined, gens);
						if (!current_floor_removal.isValid()) {
							continue;
						}

						// We we are here, both floors are valid
						let new_floors = [];
						for (let i = 0; i < this.floors.length; i++) {
							if (i === this.elevator) {
								new_floors.push(current_floor_removal);
							} else if (i === direction) {
								new_floors.push(new_floor);
							} else {
								new_floors.push(this.floors[i].clone());
							}
						}

						valid_nodes.push(new ArrangementNode(direction, new_floors, false));
						break;
					}
				}
			}
		}

		return valid_nodes;
	}

	hasItemsBeneathCurrentPosition(current_position = this.elevator) {
		let total_items_beneath_current_position = 0;
		for (let i = 0; i < current_position; i++) {
			total_items_beneath_current_position +=
				this.floors[i].microchips.length + this.floors[i].generators.length;
		}

		return total_items_beneath_current_position > 0;
	}

	validateFloors(floors = this.floors) {
		for (let floor of floors) {
			if (!floor.isValid()) {
				return false;
			}
		}

		return true;
	}

	// @example "2;0,0,1,1,1,2,2,1"
	toString() {
		return this.str;
	}

	/**
	 * For debugging purposes.
	 *
	 * @example "2; |0,0| |1,1| |1,2| |2,1|"
	 */
	toLongString() {
		let floors_str = '';
		for (let floor of this.floors) {
			floors_str += '|' + floor.toString() + '| ';
		}

		// Trim trailing space
		let floors = floors_str.substring(0, floors_str.length - 1);
		return this.elevator + '; ' + floors;
	}

	// @example "3;0,0,0,0,0,0,3,3"
	calculateEndingFloorStateString() {
		let chips_gens_total = this.floors.reduce(
			(sum, floor) => [sum[0] + floor.microchips.length, sum[1] + floor.generators.length],
			[0, 0]
		);
		let floors_str = '';
		for (let i = 0; i < this.floors.length - 1; i++) {
			floors_str += '0,0,';
		}

		floors_str += chips_gens_total[0] + ',' + chips_gens_total[1];
		return floors_str;
	}
}

class RTGPath {
	constructor(starting_arrangement) {
		this.frontier = [];
		const { elevator, floors } = starting_arrangement;
		const start = new ArrangementNode(elevator, floors);
		this.frontier.push(start);

		// Calculate this so we know when we are at the end
		this.endingStateString = start.MAX_FLOOR + ';' + start.calculateEndingFloorStateString();

		// Keys are `ArrangementNode.toString()`, and value is `{ node, from, length }`, where
		// `node` is a reference to the ArrangementNode as indicated by the key,
		// `from` is the ArrangementNode we came from,
		// `length` is what step we are at.
		this.visted = {};
		this.visted[start.str] = { node: start, from: null, length: 0 };

		this.goal = this.searchToEnd();
	}

	searchToEnd() {
		while (this.frontier.length > 0) {
			const current_node = this.frontier.shift();
			const current_node_str = current_node.str;
			const current_node_length = this.visted[current_node_str].length;

			const neighbors = current_node.getNeighbors();
			for (let next_node of neighbors) {
				const next_node_str = next_node.str;
				if (!this.visted[next_node_str]) {
					this.frontier.push(next_node);
					this.visted[next_node_str] = {
						node: next_node,
						from: current_node,
						length: current_node_length + 1,
					};

					// If we have reached the end, exit our loop immediately. BFS guarantees we won't find a shorter route.
					if (next_node_str === this.endingStateString) {
						return this.visted[next_node_str];
					}
				}
			}
		}
	}

	getShortestLengthToFourthFloor() {
		return this.goal && this.goal.length;
	}

	getPathFromVistedNode(node) {
		let path = [];
		while (node) {
			path.push(node.node.toLongString());
			node = this.visted[node.from && node.from.str];
		}

		path.reverse();
		path = path.map((c, i) => (i < 10 ? ' ' : '') + i + ' - ' + c);

		return path.join('\n');
	}

	static parseInputStringToStartingArrangementObject(str = '') {
		str = String(str).trim();
		const lines = str.split('\n');
		const floors = [];
		for (let line of lines) {
			let [, items] = line.split(' contains ');
			if (!items) {
				throw new Error(`Invalid line: ${line}`);
			}

			// @see https://github.com/tc39/proposal-string-matchall

			const gen_regex = / ([^\s]+) generator/g;
			const gens = [];
			const gen_last_indexes = {};
			let gen;
			gen_last_indexes[gen_regex.lastIndex] = true;
			while ((gen = gen_regex.exec(items))) {
				gen_last_indexes[gen_regex.lastIndex] = true;

				// Only capture group is the element type, so pop that off
				// @example `gen = [ "cobalt generator", "cobalt" ]`
				gens.push({ type: GENERATOR, element: gen.pop() });
			}

			const chip_regex = / ([^\s]+)-compatible microchip/g;
			const chips = [];
			const chip_last_indexes = {};
			let chip;
			chip_last_indexes[chip_regex.lastIndex] = true;
			while ((chip = chip_regex.exec(items))) {
				chip_last_indexes[chip_regex.lastIndex] = true;

				// Only capture group is the element type, so pop that off
				// @example `gen = [ "cobalt-compatible microchip", "cobalt" ]`
				chips.push({ type: MICROCHIP, element: chip.pop() });
			}

			if (chips.length || gens.length) {
				floors.push(new Floor(chips.concat(gens)));
			} else if (items === 'nothing relevant.') {
				floors.push(new Floor());
			} else {
				throw new Error(`Invalid line: ${line}`);
			}
		}

		return {
			elevator: 0,
			floors,
		};
	}
}

module.exports = {
	RTGPath,
	Floor,
	GENERATOR,
	MICROCHIP,
};