sherpawmc.cl interview challenge

sherpa-challenge-v0.js

// On-interview challenge: not working

// ratón encontrar queso en laberinto
// representación de datos corre por mi cuenta

// asumo laberinto cuadrado
// asumo no se mueve en diagonal
const laberinto = [
	// [0, 0, 2],
	// [0, 1, 1],
	// [0, 0, 1],
	[0, 0, 1],
	[0, 1, 1],
	[0, 0, 2],
	];

// 0, 0 - 1, 0 - 1, 1 - 2, 1 - 2, 2

// let isOut = false;

let posx = 0;
let posy = 0;

const positions = [];
const dontTake = [];
const len = laberinto.length - 1;

const canMove = (posx, posy, noTakeList) => {
	for (let i = 0; i < noTakeList.length; i++) {
		if (noTakeList[i][0] === posx && noTakeList[i][1] === y) {
			return false;
		}
	}
	return true;
};

while (true) {
	console.log(`trying x: ${posx}, y: ${posy}`);

	if (laberinto[posx][posy] === 2) {
		console.log(`Found at ${posx}, ${posy}`);
		break;
	}

	positions.push([posx, posy]);

	console.log(posx, posy);

	if (posy < len && (laberinto[posx][posy + 1] === 0 || laberinto[posx][posy + 1] === 2)) {
		if (canMove(posx, posy + 1, dontTake)) {
			posy = posy + 1;
		}
	} else if (posx < len && (laberinto[posx + 1][posy] === 0 || laberinto[posx + 1][posy] === 2)) {
		if (canMove(posx + 1, posy, dontTake)) {
			posx = posx + 1;
		}
	} else if (posx > 0 && (laberinto[posx - 1][posy] === 0 || laberinto[posx - 1][posy] === 2)) {
		if (canMove(posx - 1, posy, dontTake)) {
			posx -= 1;
		}
	} else if (posy > 0 && (laberinto[posx][posy - 1] === 0 || laberinto[posx][posy - 1] === 2)) {
		if (canMove(posx, posy - 1, dontTake)) {
			posy -= 1;
		}
	} else {
		dontTake.push(positions.pop());
		posx = positions[positions.length - 1][0];
		posy = positions[positions.length - 1][1];
		console.log('Back!', posx, posy);
	}

}

sherpa-challenge-v3.js

// given a labyrinth with a cheese inside, make the mouse find it
// labyrinth is a square matrix of `0`, `1` or `2` values, where:
// `0` means can move there
// `1` means cannot move there
// `2` means there's cheese and can move there

const deepStrictEqual = require('assert').deepStrictEqual;

// Note: a Map() key can be any value, but in my experience, testing if a map
// `.has()` an object, doesn't work for literal objects. Hence these two:
const buildKeyFrom = position => `${position.x},${position.y}`;
const buildPositionFrom = key => {
	[x, y] = key.split(',');
	return { x, y };
};

const getValue = (position, labyrinth) => labyrinth[position.x][position.y];

const isCheese = value => value === 2;
const isPassable = value => value === 0;
const canMove = value => isPassable(value) || isCheese(value);

// TODO? should make it match a cartesian axis?
const getUp = position => ({ x: position.x - 1, y: position.y });
const getDown = position => ({ x: position.x + 1, y: position.y });
const getLeft = position => ({ x: position.x, y: position.y - 1});
const getRight = position => ({ x: position.x, y: position.y + 1 });

// in: labyrinth matrix, position dictionary
// out: array of positions
const getPossibleMoves = (labyrinth, position) => {
	const possibleMoves = [];
	const last = labyrinth.length - 1;

	if (position.x > 0) {
		const up = getUp(position);
		const upVal = getValue(up, labyrinth);
		canMove(upVal) && possibleMoves.push(up);
	}

	if (position.x < last) {
		const down = getDown(position);
		const downVal = getValue(down, labyrinth);
		canMove(downVal) && possibleMoves.push(down);
	}
	
	if (position.y > 0) {
		const left = getLeft(position);
		const leftVal = getValue(left, labyrinth);
		canMove(leftVal) && possibleMoves.push(left);
	}
	
	if (position.y < last) {
		const right = getRight(position);
		const rightVal = getValue(right, labyrinth);
		canMove(rightVal) && possibleMoves.push(right);
	}

	return possibleMoves;
};

// in: possible moves array (can be empty)
// out: false or the position where the cheese is
const getCheesePosition = (labyrinth, possibleMoves) => {
	const hasCheese = pos => labyrinth[pos.x][pos.y] === 2;

	const cheese = possibleMoves.filter(hasCheese);
	return cheese.length ? cheese[0] : false;
};

// in: map: Map()
// out: position: {x, y}
const getLastFollowablePosition = map => {
	const entries = map.entries();

	let entry = entries.next();
	let prev = null;

	while (! entry.done) {
		if (entry.value[1].follow) {
			prev = entry;
		}
		entry = entries.next();
	}

	return buildPositionFrom(prev.value[0]);
};

// in: position: {x, y}, movesHistory: array of past positions
// out: boolean
const didThis = (position, history) => {
	// TODO should use the map?
	return history.some(p => p.x === position.x && p.y === position.y);
};

// in: labyrinth matrix
// out: position: {x, y}
const findCheese = labyrinth => {
	// fixed starting position
	let pos = {
		x: 0,
		y: 0,
	};

	// using a Map cause is ordered, so I can backtrack to the last inserted
	// position
	const map = new Map();
	const movesHistory = [];

	while (true) {
		const key = buildKeyFrom(pos); 
		let possibleMoves = null;

		if (map.has(key)) { // path already travelled
			possibleMoves = map.get(key).possibleMoves;
		} else {
			possibleMoves = getPossibleMoves(labyrinth, pos).filter(pos => ! didThis(pos, movesHistory));
			map.set(key, { follow: true, possibleMoves });
		}

		const cheesePosition = getCheesePosition(labyrinth, possibleMoves);
		if (cheesePosition) {
			movesHistory.push(cheesePosition);
			return cheesePosition;
		} else {
			movesHistory.push(pos);
			if (possibleMoves.length) {
				// check the moves is a follow = true with a while
				pos = possibleMoves.shift();
			} else { // no more moves from this position, backtrack!
				// mark this position as a no-go
				map.get(key).follow = false;
				pos = getLastFollowablePosition(map);
			}
		}
	}
};

const l1 = [ // multipath
	[0, 0, 2],
	[0, 1, 1],
	[0, 0, 1],
];

const l2 = [ // multipath
	[0, 0, 1],
	[0, 1, 1],
	[0, 0, 2],
];

const l3 = [ // single path
	[0, 1, 0],
	[0, 0, 1],
	[1, 0, 2],
];

// const l4 = [ // TODO no solution
	// [0, 1, 2],
	// [1, 1, 1],
	// [1, 1, 1],
// ];

const msg = path => `Couldn't find cheese on path ${path}`;

deepStrictEqual(findCheese(l1), { x: 0, y: 2 }, msg(l1));
deepStrictEqual(findCheese(l2), { x: 2, y: 2 }, msg(l2));
deepStrictEqual(findCheese(l3), { x: 2, y: 2 }, msg(l3));