Solve the task from JS interview about the labyrinth | Maze
HTML-код
- Опубликовано: 8 сен 2024
- Одна из частых задач на JS собеседованиях - задача про лабиринт. Есть очень много различных вариаций таких задач. В одних необходимо найти самое короткое решение, в других - первое попавшееся. В этом видео мы разберем задачу, в которой нужно ответить в принципе, имеет ли данный лабиринт решение или нет.
Даже эта задача имеет множество различных алгоритмов решений, мы рассмотрим вариант с рекурсией.
Мне попадалась эта задача в очень разных интерпретациях, одна из них была поставлена, как будто бы лабиринт - это полупроводниковая дорожка, по которой может протекать ток, но по этой дорожке разбросаны дефекты, как пиксели. По ним ток не течет. И необходимо понять: при данном расположении дефектов проводит ли эта дорожка сигнал.
Код с решением: codepen.io/puz...
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
И обязательно подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-scienc...
#leetcode, #алгоритмы, #javascript #itсобеседование
![Как сделать Генератор Лабиринта на Python. Алгоритм поиска в Глубину [ Pygame ]](http://i.ytimg.com/vi/yaWksgYZvWM/mqdefault.jpg)
Друзья, пишите под видео свои решения! Очень полезно и интересно их все читать!
Обожаю решать ваши задачи. Некоторые из них заставляют сильно попотеть)
Обожаем такие комментарии! :)
как обычно, супер. Спасибо за труды)
Тебе спасибо! )
Спасибо за задачу, минут 30 потратил и вот что получилось без рефакторинга
function maze(start, end) {
const lab = [
[1,1,1,0,0,0],
[0,0,0,1,0,1],
[0,1,0,0,0,1],
[0,1,1,1,1,1],
[0,0,0,0,0,0]
]
function step(pos) {
start.x = pos.x
start.y = pos.y
lab[pos.y][pos.x] = 2
const top = { x:pos.x, y:pos.y - 1 }
const left = { x:pos.x - 1, y:pos.y }
const right = { x:pos.x + 1, y:pos.y }
const bottom = { x:pos.x, y:pos.y + 1 }
if (lab[top.y] !== undefined && !lab[top.y][top.x])
step(top)
if (lab[left.y][left.x] !== undefined && !lab[left.y][left.x])
step(left)
if (lab[right.y][right.x] !== undefined && !lab[right.y][right.x])
step(right)
if (lab[bottom.y] !== undefined && !lab[bottom.y][bottom.x])
step(bottom)
}
step(start)
return (start.x === end.x && start.y === end.y)
}
console.log(maze({ x:3, y:0 }, { x:5, y:4 }))
Решения , пока своего нету ) Но видео классное!
Спасибо большое, но мой мозг сломалась🤯🤯
Спасибо за задачи! У меня вышло такое решение:
function checkPath(start, end) {
function step(x, y) {
// Если вышли за пределы
if (y < 0) return false;
if (y >= maze.length) return false;
if (maze[y][x] === undefined) return false;
// Если пошли по неверному пути
if (maze[y][x] === 1) return false;
if (maze[y][x] === 'x') return false;
if (x === end.x && y === end.y) return true;
maze[y][x] = 'x';
return step(x + 1, y) || step(x - 1, y) || step(x, y + 1) || step(x, y - 1);
}
return step(start.x, start.y);
}
Чуть заморочился над чистотой функции и иммутабельностью внешнего объекта maze. Вот, что получилось:
const checkPath = (entrance, exit, maze) => {
const map = Array.from(Array(maze.length), (_, y) => maze[y].map(v => v === 0));
map.isVisitable = function({x, y}) {
return this[y]?.hasOwnProperty(x) && this[y][x];
};
if (!map.isVisitable(entrance) || !map.isVisitable(exit)) {
return false;
}
(function traversing({x, y}, end, map) {
map[y][x] = false;
if (x === end.x && y === end.y) return;
const directions = [
{x: x + 1, y: y}, // right
{x: x, y: y + 1}, // down
{x: x - 1, y: y}, // left
{x: x, y: y - 1}, // up
];
for (const variant of directions) {
if (map.isVisitable(variant)) {
traversing(variant, end, map);
}
}
}(entrance, exit, map))
return !map[exit.y][exit.x];
};
Рекурсия - это весело, но лучше было бы использовать оценку расстояний (Дейкстры или в ширину вроде называется), тогда стек не надо забивать. #муравьиныйалгоритм
А чем это лучше? Особенно для собеседования? У нас нет условия с ограничением по памяти.
spasibo
шикарно
🤘
Возможно такой вариант является более простым для понимания или я неправильно понял условие? Но отрабатывает он как надо:
function checkPath(start, end) {
let {x, y} = start;
while (true) {
if (x === end.x && y === end.y) {
return true;
}
if (maze[y][x] === 0 && maze[y + 1][x] === 0) {
y++;
x = 0;
} else {
if (x === maze[0].length - 1) {
return false;
} else {
x++;
}
}
}
}
Такой вариант к сожалению не будет работать на лабиринтах где путь не идет всегда по направлению к выходу. На примере который был в видео - это решение не проходит.
function checkPath(start, end){
const n = maze.length - 1;
const {x, y} = start;
const moveTo = (x, y) => {
if (x < 0 || y < 0 || x > n || y > n || maze[y][x] !== 0) {
return false;
}
maze[y][x] = 5;
if (x === end.x && y === end.y) {
return true;
}
return moveTo(x - 1, y)
|| moveTo(x + 1, y)
|| moveTo(x, y - 1)
|| moveTo(x, y + 1);
}
return moveTo(x, y);
}
Самооценка[stonks]=‘dawn’
Вот скажите, только честно, как долго вы думали над алгоритмом ?
я уже не помню. Давно было. Но вообще сам алгоритм не сложен и очень известен. Эту задачу можно решить либо с помощью DFS либо BFS. Это очень популярные алгоритмы для решения такого рода задач.
Я сходу допер только до условий в которых происходит осматривание соседних клеток и формируется массив возможных ходов, до рекурсии не догадался.
Четыре if прям как то больно выглядят. Сделать бы массив ходов и пробегаться циклом по нему. И там же добавлять только 0 значения лабиринта, без фильтра.
С одной стороны соглашусь что 4 if выглядят не самым приятным образом - с другой стороны, решение где мы будем проходиться циклом по возможным ходам, будет намного сложней в понимании что же происходит. Если задачу решать именно на собеседовании - настоятельно рекомендую не оптимизировать а оставлять явным образом if'ы.
1:08 - 5 минут назад ты сказал, что осталось 2 минуты.
Пробую на Java, не всегда срабатывает, где то логика у моего скрипта захромала. Если есть идеи как пофиксить, помогите. Спасибо.
Код:
import java.util.Arrays;
public class Maze {
public static void main(String[] args) {
// 1 приход
// 0 не проходной
// Вход [0, 0], выход [4, 4]
int[][] maze = {
{1, 0, 0, 0},
{1, 1, 0, 0},
{0, 1, 1, 1},
{1, 1, 1, 1}
};
int[][] maze1 = {
{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{0, 1, 0, 1},
{1, 1, 1, 1}
};
int[][] grid = {
{1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
{1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1},
{1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
System.out.println(checkMaze(maze1, 0, 0, 4, 3));
Arrays.stream(maze1).forEach(arrayElement -> System.out.println(Arrays.toString(arrayElement)));
System.out.println(checkMaze(maze, 0, 0, 3, 3));
Arrays.stream(maze).forEach(arrayElement -> System.out.println(Arrays.toString(arrayElement)));
System.out.println(checkMaze(grid, 0, 0, 12, 7));
Arrays.stream(grid).forEach(arrayElement -> System.out.println(Arrays.toString(arrayElement)));
}
private static boolean checkMaze(int[][] maze, int col, int row, int endCol, int endRow) {
maze[col][row] = 5;
if (col == endCol && row == endRow) {
return true;
}
boolean result = false;
// up
if (isValid(col, row - 1, maze) && maze[col][row - 1] != 5
|| (isValid(col, row - 2, maze) && maze[col][row - 1] == 5)
) {
row--;
result = checkMaze(maze, col, row, endCol, endRow);
}
// down
if (isValid(col, row + 1, maze) && !result && maze[col][row + 1] != 5
|| (isValid(col, row + 2, maze) && maze[col][row + 1] == 5)
) {
row++;
result = checkMaze(maze, col, row, endCol, endRow);
}
// left
if (isValid(col - 1, row, maze) && !result && maze[col - 1][row] != 5
|| (isValid(col, row, maze) && maze[col - 1][row] == 5)) {
col--;
result = checkMaze(maze, col, row, endCol, endRow);
}
// right
if (isValid(col + 1, row, maze) && !result && maze[col + 1][row] != 5
|| (isValid(col, row, maze) && maze[col + 1][row] == 5)) {
col++;
result = checkMaze(maze, col, row, endCol, endRow);
}
//System.out.println("col = " + col + " " + "row = " + row);
return result;
}
private static boolean isValid(int col, int row, int[][] maze) {
return col >= 0 && col < maze.length && row >= 0 && row < maze[0].length && maze[col][row] == 1;
}
}
В этот раз достаточно трудная задачка для меня, спасибо за ваши труды.
Вот мое решение. Сейчас буду смотреть ваше.
function checkPath(start, end) {
function canIgo(x, y) {
return x < 6 && x >= 0 && y < 6 && y >= 0 && maze[y][x] === 0
// определяем есть ли эта позиция и можно ли идти сюда
}
function step(x, y) {
if (x === end.x && y === end.y) return true; // если добрались в конец возвращаем true
const roads = []; // создаем массив возможных путей
if (canIgo(x + 1, y)) { //проверяем возможно ли перейти на все возможные позиции
roads.push([x + 1, y]);
}
if (canIgo(x - 1, y)) {
roads.push([x - 1, y]);
}
if (canIgo(x, y + 1)) {
roads.push([x, y + 1]);
}
if (canIgo(x, y - 1)) {
roads.push([x, y - 1]);
}
maze[y][x] = 9; // отмечаем 9-кой текущую позицию как пройденную
if (roads.length === 0) return false; // если идти больше некуда возвращаем false
// в зависимости от кол-ва доступных дорог проходим по ним всем
if (roads.length === 1) return step(roads[0][0], roads[0][1]);
if (roads.length === 2) return step(roads[0][0], roads[0][1]) ||
step(roads[1][0], roads[1][1]);
if (roads.length === 3) return step(roads[0][0], roads[0][1]) ||
step(roads[1][0], roads[1][1]) ||
step(roads[2][0], roads[2][1]);
}
return step(start.x, start.y);
}
console.log(checkPath({x : 3, y: 0},{x: 5, y: 5}));
console.log(maze);
Благодарю за решение! Круто что вначале сами решили!
function checkPath(start, end) {
maze[start.y][start.x] = 5
const siblings = getValidSib(start);
if (siblings.length === 0) return false;
for (let i = 0; i < siblings.length; i++) {
const {x, y} = siblings[i];
const isSolved = y === end.y && x === end.x
if (isSolved || checkPath({x, y}, end)) return true;
}
}
function getValidSib(cord) {
const {x, y} = cord, cords = [];
if (maze[y - 1]?.[x] === 0) cords.push({x, y: y - 1});
if (maze[y + 1]?.[x] === 0) cords.push({x, y: y + 1});
if (maze[y][x - 1] === 0) cords.push({x: x - 1, y});
if (maze[y][x + 1] === 0) cords.push({x: x + 1, y});
return cords;
}
Спасибо
function checkPath(start, end) {
const forbiddenCoordinates = {};
function isForbiddenCoordinates(y, x) {
return forbiddenCoordinates[y]?.includes(x);
}
function isAvailableCoordinates(level, x) {
return level?.[x] === 0;
}
function move(position) {
const {x, y} = position;
if (x === end.x && y === end.y) return true;
const level = maze[y];
const nextLevel = maze?.[y + 1];
const availableCoordinates = [];
if (isAvailableCoordinates(level, x - 1) && !isForbiddenCoordinates(y, x - 1)) availableCoordinates.push({x: x - 1, y});
if (isAvailableCoordinates(level, x + 1) && !isForbiddenCoordinates(y, x + 1)) availableCoordinates.push({x: x + 1, y});
if (isAvailableCoordinates(nextLevel, x) && !isForbiddenCoordinates(y + 1, x)) availableCoordinates.push({x: x, y: y + 1});
forbiddenCoordinates[y] ? forbiddenCoordinates[y].push(x) : forbiddenCoordinates[y] = [x];
if (availableCoordinates.length === 0) {
return false;
}
for(let coordinate of availableCoordinates) {
if (move(coordinate)) return true;
}
return false;
}
return move(start);
}
function road(arr, position = {x: 5, y: 0}, finish = {x: 5, y: 5}) {
try {
let array = [...arr]
let pos = {...position}
let fin = {...finish}
array[pos.y][pos.x] = 5
//Зачищаємо 9 шоб була видима тільки лінія правильного шляху
if (pos.x === fin.x && pos.y === pos.x) return array.map(el=>el.map(num=>{
if (num === 9) return 0
return num
}))
const left = {x: pos.x - 1, y: pos.y}
const right = {x: pos.x + 1, y: pos.y}
const up = {x: pos.x, y: pos.y - 1}
const down = {x: pos.x, y: pos.y + 1}
const objDirections = {
left, right, up, down
}
const objKeys = Object.keys(objDirections)
function isEmpty() {
for (let i = 0; i < objKeys.length; i++) {
if (array[objDirections[objKeys[i]].x] !== undefined
&& array[objDirections[objKeys[i]].y] !== undefined
&& array[objDirections[objKeys[i]].y][objDirections[objKeys[i]].x] === 0) {
pos = {...objDirections[objKeys[i]]}
return true
}
}
array[pos.y][pos.x] = 9
//Коли впираємось в тупік повертаємось і йдемо назд по 5-кам пока не зустріним 0. Спочатку нас цікавить 0 а потім 5 шоб не піти назад
for (let i = 0; i < objKeys.length; i++) {
if (array[objDirections[objKeys[i]].x] !== undefined
&& array[objDirections[objKeys[i]].y] !== undefined
&& array[objDirections[objKeys[i]].y][objDirections[objKeys[i]].x] === 5) {
pos = {...objDirections[objKeys[i]]}
return true
}
}
return false
}
if (isEmpty()) {
return road(array, pos, fin)
}
return array
} catch (err) {
return false
}
}
Вау круто вышло! Отлично работает!
it's my solution .it's not the best but at least works
let maze = [
[1, 1, 1, 0, 0, 1],
[1, 1, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 0],
];
function checkPath(start,end){
if(start.x=maze.length){
return false
}
if(start.y=maze.length){
return false
}
if(maze[start.y][start.x]!==0){
return false
}
if(start.x===end.x&&start.y===end.y&&maze[start.x][start.y]===0){
return true;
}
maze[start.y][start.x]=2;
return checkPath({x:start.x+1,y:start.y}, { x: 5, y: 5 })||checkPath({x:start.x,y:start.y+1}, { x: 5, y: 5 })||
checkPath({x:start.x-1,y:start.y}, { x: 5, y: 5 })||checkPath({x:start.x,y:start.y-1}, { x: 5, y: 5 })
}
debugger;
console.log(checkPath({ x: 3, y: 0 }, { x: 5, y: 5 }));
console.log(maze);