Интересная задача на Yandex cup 2021

24.02.22

Разработка - Математика и алгоритмы

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

Условие задачи такое(своими словами дабы не нарушать авторских прав):

Дается лабиринт в котором нужно найти путь к выходу. Лабиринт каждый раз при обновлении страницы генерируется новый.

Также даются 5 асинхронных методов. Двигаться вверх(up), вниз(down), влево(left), вправо(right), осмотреться(state).

Метод state возвращает объект (finish-если оно true, то это и есть выход)

{bottom: true
finish: false
left: true
right: true
start: false
top: false}

Решение нужно писать в определенной функции, которую после написания нужно отправить на проверку.

Также в этой функции было показан пример как пользоваться методами. В примере делаем 5 шагов вправо и возвращается координаты с выходом (но понятное дело тут будет finish=false)

export default function main(game, start) {
     return game.right(start.x, start.y)
         .then(() => game.right(start.x + 1, start.y))
         .then(() => game.right(start.x + 2, start.y))
         .then(() => game.right(start.x + 3, start.y))
         .then(() => game.right(start.x + 4, start.y))
         .then(() => game.right(start.x + 5, start.y))
         .then(() => ({ x: start.x + 6, y: start.y }));
}

Результат можно посмотреть тут: https://labyrinth-y.web.app/

Решение:

Первое с чем столкнулся, это с тем что это не простые методы, а асинхронные, т.е. к ним можно обратиться как в примере цепочкой промисов(Promise), но в эту цепочку цикл не вставить. 

Поэтому пойдем другим путем, нужно перейти в асинхронную функция и оттуда вызвать эти методы как асинхронные выражения, с ожиданием результата по каждому из них.

 

 

export default function main(game, start) {
   
    let st = {};

    const state = async (x,y) => {
        return game.state(x, y) 
        .then((st1) => { 
            st=st1
        })
        .then(() => ({ x: x, y: y }));
    }

    const right = async (x,y) => {
        return game.right(x, y);
    }

    const left = async (x,y) => {
        return game.left(x, y);
    }

    const down = async (x,y) => {
        return game.down(x, y);
    }

    const up = async (x,y) => {
        return game.up(x, y);
    }


    const mainFunction = async () => {
        
        await right(start.x + 1,start.y)
        await right(start.x + 2,start.y)
        await right(start.x + 3,start.y)
        await right(start.x + 4,start.y)
        await right(start.x + 5,start.y)
        return await state(start.x + 6,start.y)
                
    }
    return mainFunction()
}

 

Добавим цикл. После получения объекта state (см. в условии задачи) записываю его в двумерный массив карты лабиринта 50*50(т.е. создаю свою карту лабиринта), также преобразую объект state в массив, исключаю из него finish и start и добавляю его к карте. Далее вместо второго элемента массива 'true' я начинаю записывать сколько раз ходил в данном направлении на этой клетке лабиринта.

[
['top', true]
['bottom', true]
['right', true]
]
 

 

const mainFunction = async () => {
        let xx = 0;
        let yy = 0;
        const map = new Array(50);
        for (var i = 0; i < map.length; i++) {
            map[i] = new Array(50);
        }
        while (true) {
            if (map[xx][yy]==undefined){
                await state(xx,yy)
                map[xx][yy] = Object.assign({}, st);
            }

            const ar_st = Object.entries(map[xx][yy]);
            const ar_st2 = ar_st.filter((el)=>{
                return el[1]===true && el[0]!='start' && el[0]!='finish'
            })
            if (map[xx][yy].arr==undefined){
                map[xx][yy].arr = ar_st2 
            }
            
            const step = 0;  

            //считаю сколько раз был на клетке
            map[xx][yy].arr[step][1] = map[xx][yy].arr[step][1] + 1


            if (st.finish) {
                return await state(xx,yy)
            }
            else if (map[xx][yy].arr[step][0] == 'right' ) {
                await right(xx,yy)
                xx = xx + 1
            } 
            else if (map[xx][yy].arr[step][0] == 'bottom' ) {
                await down(xx,yy)
                yy = yy + 1
            } 
            else if (map[xx][yy].arr[step][0] == 'left' ) {
                await left(xx,yy)
                xx = xx - 1
            } 
            else if (map[xx][yy].arr[step][0] == 'top' ) {
                await up(xx,yy)
                yy = yy - 1
            }
            else {
                console.log(1)
            }
            
        }  
    }

 

Теперь немного ходим по лабиринту, но до первого тупика, в котором все зацикливается. Добавим функцию (blockDeadEnd) исключающую повторный заход в один и тот же тупик.

 
  const blockDeadEnd = (stepOutOfDeadEnd,arr) => {
        if (stepOutOfDeadEnd=='right') {
            arr = arr.filter((el)=>{
                return el[0]!='left'
            })
        } else if (stepOutOfDeadEnd=='left') {
            arr = arr.filter((el)=>{
                return el[0]!='right'
            })
        } else if (stepOutOfDeadEnd=='bottom') {
            arr = arr.filter((el)=>{
                return el[0]!='top'
            })
        } else if (stepOutOfDeadEnd=='top') {
            arr = arr.filter((el)=>{
                return el[0]!='bottom'
            })
        }
        return arr
    }

   
    const mainFunction = async () => {
        let xx = 0;
        let yy = 0;
        let stepOutOfDeadEnd = '' 
        const map = new Array(50);
        for (var i = 0; i < map.length; i++) {
            map[i] = new Array(50);
        }
        while (true) {
            if (map[xx][yy]==undefined){
                await state(xx,yy)
                map[xx][yy] = Object.assign({}, st);
            }

            const ar_st = Object.entries(map[xx][yy]);
            const ar_st2 = ar_st.filter((el)=>{
                return el[1]===true && el[0]!='start' && el[0]!='finish'
            })
            if (map[xx][yy].arr==undefined){
                map[xx][yy].arr = ar_st2 
            }
            
            if (stepOutOfDeadEnd!='') {
                map[xx][yy].arr = blockDeadEnd(stepOutOfDeadEnd,map[xx][yy].arr)
            }

            const step = 0;  

            //считаю сколько раз был на клетке
            map[xx][yy].arr[step][1] = map[xx][yy].arr[step][1] + 1

            //если тупик то запоминаю
            if (map[xx][yy].arr.length==1){
                stepOutOfDeadEnd = map[xx][yy].arr[step][0]
            } else {
                stepOutOfDeadEnd = ''
            }

            if (st.finish) {
                return await state(xx,yy)
            }
            else if (map[xx][yy].arr[step][0] == 'right' ) {
                await right(xx,yy)
                xx = xx + 1
            } 
            else if (map[xx][yy].arr[step][0] == 'bottom' ) {
                await down(xx,yy)
                yy = yy + 1
            } 
            else if (map[xx][yy].arr[step][0] == 'left' ) {
                await left(xx,yy)
                xx = xx - 1
            } 
            else if (map[xx][yy].arr[step][0] == 'top' ) {
                await up(xx,yy)
                yy = yy - 1
            }
            else {
                console.log(1)
            }
            
        }  
    }

 

Теперь намного лучше ходим по лабиринту в тупики второй раз не заходим, но не знаем куда идти, случайным образом бродим по коридорам. Добавим функцию (firstToUndefined) поиска мест где мы еще небыли.

 

 

export default function main(game, start) {
    // return game.right(start.x, start.y)
    //     .then(() => game.right(start.x + 1, start.y))
    //     .then(() => game.right(start.x + 2, start.y))
    //     .then(() => game.right(start.x + 3, start.y))
    //     .then(() => game.right(start.x + 4, start.y))
    //     .then(() => game.right(start.x + 5, start.y))
    //     .then(() => ({ x: start.x + 6, y: start.y }));


    let st = {};

    const state = async (x,y) => {
        return game.state(x, y) 
        .then((st1) => { 
            st=st1
        })
        .then(() => ({ x: x, y: y }));
    }

    const right = async (x,y) => {
        return game.right(x, y);
    }

    const left = async (x,y) => {
        return game.left(x, y);
    }

    const down = async (x,y) => {
        return game.down(x, y);
    }

    const up = async (x,y) => {
        return game.up(x, y);
    }

    const blockDeadEnd = (stepOutOfDeadEnd,arr) => {
        if (stepOutOfDeadEnd=='right') {
            arr = arr.filter((el)=>{
                return el[0]!='left'
            })
        } else if (stepOutOfDeadEnd=='left') {
            arr = arr.filter((el)=>{
                return el[0]!='right'
            })
        } else if (stepOutOfDeadEnd=='bottom') {
            arr = arr.filter((el)=>{
                return el[0]!='top'
            })
        } else if (stepOutOfDeadEnd=='top') {
            arr = arr.filter((el)=>{
                return el[0]!='bottom'
            })
        }
        return arr
    }

    const firstToUndefined = (arr,map,xx,yy) => {
        arr.forEach(el=>{
            if (el[0]=='right' && map[xx+1][yy]==undefined) {
                el[1]=0
            }
            else if (el[0]=='left' && map[xx-1][yy]==undefined) {
                el[1]=0
            } 
            else if (el[0]=='bottom' && map[xx][yy+1]==undefined) {
                el[1]=0
            }
            else if (el[0]=='top' && map[xx][yy-1]==undefined) {
                el[1]=0
            }
        })

        if (yy==0) {
            const bottom1 = arr.find(el=>el[0] === 'bottom')
            if (bottom1!=undefined && bottom1[1]==0) {
                arr.sort((a, b) => a[0].localeCompare(b[0]))
            }    
        } else {
            arr = arr.sort((a, b) => {
                return a[1] > b[1] ? 1 : -1
            })
        }

        return arr
    }

    const mainFunction = async () => {
        let xx = 0;
        let yy = 0;
        let stepOutOfDeadEnd = '' 
        const map = new Array(50);
        for (var i = 0; i < map.length; i++) {
            map[i] = new Array(50);
        }
        while (true) {
            if (map[xx][yy]==undefined){
                await state(xx,yy)
                map[xx][yy] = Object.assign({}, st);
            }

            const ar_st = Object.entries(map[xx][yy]);
            const ar_st2 = ar_st.filter((el)=>{
                return el[1]===true && el[0]!='start' && el[0]!='finish'
            })
            if (map[xx][yy].arr==undefined){
                map[xx][yy].arr = ar_st2 
            }
            
            if (stepOutOfDeadEnd!='') {
                map[xx][yy].arr = blockDeadEnd(stepOutOfDeadEnd,map[xx][yy].arr)
            }

            const step = 0;  
            map[xx][yy].arr = firstToUndefined(map[xx][yy].arr,map,xx,yy)

            //считаю сколько раз был на клетке
            map[xx][yy].arr[step][1] = map[xx][yy].arr[step][1] + 1

            //если тупик то запоминаю
            if (map[xx][yy].arr.length==1){
                stepOutOfDeadEnd = map[xx][yy].arr[step][0]
            } else {
                stepOutOfDeadEnd = ''
            }

            if (st.finish) {
                return await state(xx,yy)
            }
            else if (map[xx][yy].arr[step][0] == 'right' ) {
                await right(xx,yy)
                xx = xx + 1
            } 
            else if (map[xx][yy].arr[step][0] == 'bottom' ) {
                await down(xx,yy)
                yy = yy + 1
            } 
            else if (map[xx][yy].arr[step][0] == 'left' ) {
                await left(xx,yy)
                xx = xx - 1
            } 
            else if (map[xx][yy].arr[step][0] == 'top' ) {
                await up(xx,yy)
                yy = yy - 1
            }
            else {
                console.log(1)
            }
            
        }  
    }
    return mainFunction()

}

 

Упустил важное условие в задачи выход нужно найти за 10 секунд.

Поэтому исправил алгоритм добавил рекурсию. Теперь есть главный искатель, который идет по верхней линии и вызывает новых искателей (рекурсия).

 

 

export default function main(game, start) {
    // return game.right(start.x, start.y)
    //     .then(() => game.right(start.x + 1, start.y))
    //     .then(() => game.right(start.x + 2, start.y))
    //     .then(() => game.right(start.x + 3, start.y))
    //     .then(() => game.right(start.x + 4, start.y))
    //     .then(() => game.right(start.x + 5, start.y))
    //     .then(() => ({ x: start.x + 6, y: start.y }));

    let rezult = undefined;

    const state = async (x,y) => {
        return game.state(x, y) 
        .then((st1) => { 
            return st1
        })
    }

    const state2 = async (x,y) => {
        return game.state(x, y) 
        .then(() => ({ x: x, y: y }));
    }

    const right = async (x,y) => {
        return game.right(x, y);
    }

    const left = async (x,y) => {
        return game.left(x, y);
    }

    const down = async (x,y) => {
        return game.down(x, y);
    }

    const up = async (x,y) => {
        return game.up(x, y);
    }

    const blockDeadEnd = (stepOutOfDeadEnd,arr) => {
        if (stepOutOfDeadEnd=='right') {
            arr = arr.filter((el)=>{
                return el[0]!='left'
            })
        } else if (stepOutOfDeadEnd=='left') {
            arr = arr.filter((el)=>{
                return el[0]!='right'
            })
        } else if (stepOutOfDeadEnd=='bottom') {
            arr = arr.filter((el)=>{
                return el[0]!='top'
            })
        } else if (stepOutOfDeadEnd=='top') {
            arr = arr.filter((el)=>{
                return el[0]!='bottom'
            })
        }
        return arr
    }

    const firstToUndefined = (arr,map,xx,yy,main) => {
        arr.forEach(el=>{
            if (el[0]=='right' && map[xx+1][yy]==undefined) {
                el[1]=0
            }
            else if (el[0]=='left' && map[xx-1][yy]==undefined) {
                el[1]=0
            } 
            else if (el[0]=='bottom' && map[xx][yy+1]==undefined) {
                el[1]=0
            }
            else if (el[0]=='top' && map[xx][yy-1]==undefined) {
                el[1]=0
            }
        })

        if (yy==0 && !main) {
            const bottom1 = arr.find(el=>el[0] === 'bottom')
            if (bottom1!=undefined && bottom1[1]==0) {
                arr.sort((a, b) => a[0].localeCompare(b[0]))
            }    
        } else {
            arr = arr.sort((a, b) => {
                return a[1] > b[1] ? 1 : -1
            })
        }

        return arr
    }

    const blockDown = (arr) => {
        arr = arr.filter((el)=>{
            return el[0]!='bottom'
        })
        return arr
    }

    const mainFunction = async (main,xx = 0,yy = 0,trash=false) => {
        let stepOutOfDeadEnd = '' 
        while (true) {
            if (main && rezult != undefined) {
                return rezult
            }
            if ((!main && yy==0 && trash)||(!main && rezult)) {
                return
            }
            if (yy==25) {
                trash=true
            }
            
            let st = {};
            if (map[xx][yy]==undefined){
                st = await state(xx,yy)
                map[xx][yy] = Object.assign({}, st);
            }

            if (st.bottom && main && yy==0) {
                mainFunction(false,xx,yy)
            }

            const ar_st = Object.entries(map[xx][yy]);
            const ar_st2 = ar_st.filter((el)=>{
                return el[1]===true && el[0]!='start' && el[0]!='finish'
            })
            if (map[xx][yy].arr==undefined){
                map[xx][yy].arr = ar_st2 
            }
            
            if (stepOutOfDeadEnd!='') {
                map[xx][yy].arr = blockDeadEnd(stepOutOfDeadEnd,map[xx][yy].arr)
            }

            if (yy>26) {
                map[xx][yy].arr = blockDown(map[xx][yy].arr)
            }

            const step = 0;  
            map[xx][yy].arr = firstToUndefined(map[xx][yy].arr,map,xx,yy,main)

            //считаю сколько раз был на клетке
            map[xx][yy].arr[step][1] = map[xx][yy].arr[step][1] + 1

            //если тупик то запоминаю
            if (map[xx][yy].arr.length==1){
                stepOutOfDeadEnd = map[xx][yy].arr[step][0]
            } else {
                stepOutOfDeadEnd = ''
            }

            if (st.finish) {
                rezult = await state2(xx,yy)
                return rezult
            }
            else if (map[xx][yy].arr[step][0] == 'right' ) {
                await right(xx,yy)
                xx = xx + 1
            } 
            else if (map[xx][yy].arr[step][0] == 'bottom' ) {
                await down(xx,yy)
                yy = yy + 1
            } 
            else if (map[xx][yy].arr[step][0] == 'left' ) {
                await left(xx,yy)
                xx = xx - 1
            } 
            else if (map[xx][yy].arr[step][0] == 'top' ) {
                await up(xx,yy)
                yy = yy - 1
            }
            else {
                console.log(1)
            }
            
        }  
    }
    const map = new Array(50);
    for (var i = 0; i < map.length; i++) {
        map[i] = new Array(50);
    }
    return mainFunction(true)

}

 

Результат можно посмотреть тут: https://labyrinth-y.web.app/

Исходники лабиринта без решения: тут

Yandex cup Лабиринт JavaScript

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7461    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7804    dusha0020    8    

70

Алгоритмы распределения сумм (наивная методика, Алгоритм Кэхэна)

Математика и алгоритмы Россия Бесплатно (free)

Многим встречалась задача распределения суммы и вытекающая из нее проблема округления, каждый решал ее по-своему, все ли способы вам известны?

08.07.2021    8183    con-men    33    

25
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. handscenter 59 12.10.21 11:21 Сейчас в теме
2. brr 182 12.10.21 11:26 Сейчас в теме
Огонь, побольше бы таких статей.
3. etmarket 890 12.10.21 11:34 Сейчас в теме
Было бы шикарно в общих чертах узнать актуальные задачи из каждого направления этого CUP: Front-End, Back-End, Mobile Development, Analytics, Algorithm, Machine Learning.
56. John_d 5277 15.10.21 10:14 Сейчас в теме
(52) прикольные соревнования. Я так понял это в Китае.
57. RustIG 1351 15.10.21 12:26 Сейчас в теме
(56) задача лабиринтов имеет практическое применение - особенно в роботизации - поиск людей при завалах, шпионские мини-роботы, протяжка новых трубопроводов или коаксильных интернет -кабелей в зданиях и под землей...
Просто их алгоритмы засекречены - надо своих Кулибиных подключать.
4. Jimbo 9 12.10.21 11:43 Сейчас в теме
5. John_d 5277 12.10.21 11:44 Сейчас в теме
6. etmarket 890 12.10.21 11:48 Сейчас в теме
Посмотрел веб-приложение. Видно же, что путь получается неоптимальным. Следующий уровень - найти кратчайший. Можно использовать какой-либо алгоритм сегментации изображения лабиринта.
7. CyberCerber 852 12.10.21 12:04 Сейчас в теме
(6) Как один из вариантов оптимизации: "Если непройденная область, в которой нет центра лабиринта, окружена пройденной, смысла заходить в нее нет"
8. John_d 5277 12.10.21 12:17 Сейчас в теме
(7) еще можно оптимизировать, не спускаться ниже середины лабиринта.
Но у меня более универсальное решение (вдруг что-то поменяется и выход будет не в центре)
9. CyberCerber 852 12.10.21 12:19 Сейчас в теме
(8) Ну про ниже середины не факт. Вдруг выход к центру только с правого нижнего угла? Или я что-то пропустил в условии задачи?
11. John_d 5277 12.10.21 12:36 Сейчас в теме
(9) нет такого условия, но если генерировать разные лабиринты, то можно заметить, что основной подход сверху. Но немного спускаться ниже середины нужно, не слишком глубоко.
13. John_d 5277 12.10.21 13:20 Сейчас в теме
(9) можете посмотреть добавил условие не спускаюсь ниже y<27
labyrinth-y.web.app
10. CagoBHuK 32 12.10.21 12:22 Сейчас в теме
Автор, не увидел в твоем коде ни эвристики, ни A*-search. Подобие эвристики есть в последнем куске кода, где "мест где мы еще небыли", но вообще рекомендую прочитать про оптимальные алгоритмы поиска кратчайшего пути, и в частности про эвристику. Решение, предложенное автором, не тянет даже на четверочку.
e.kogan; EliasShy; rpgshnik; bilex; starik-2005; zhuntovda; +6 Ответить
12. John_d 5277 12.10.21 12:41 Сейчас в теме
21. s22 19 12.10.21 17:06 Сейчас в теме
(10)
Автор, не увидел в твоем коде ни эвристики, ни A*-search. Подобие эвристики есть в последнем куске кода, где "мест где мы еще небыли", но вообще рекомендую прочитать про оптимальные алгоритмы поиска кратчайшего пути, и в частности про эвристику. Решение, предложенное автором, не тянет даже на четверочку.


вы не видите весь лабиринт стразу как я понял. Поэтому алгоритмы поиска кратчайшего пути будут во многом не применимы
RustIG; insurgut; John_d; +3 Ответить
24. John_d 5277 12.10.21 17:19 Сейчас в теме
(21) Все верно. Видим выходы только той клетки в которой находимся.
25. CagoBHuK 32 12.10.21 17:25 Сейчас в теме
(21) В таком случае breadth-first search простым методом стека, делается буквально несколькими строчками. Описано тут.
55. John_d 5277 15.10.21 10:06 Сейчас в теме
(25) по этому алгоритму не возможно вернуться назад когда зайдешь в тупик.
Но можно попробовать после захода в тупик ликвидировать искателя и рекурсивно начинать поиск с начала. (нужно пробовать)
53. RustIG 1351 15.10.21 09:13 Сейчас в теме
14. starik-2005 3033 12.10.21 13:22 Сейчас в теме
В девстве на бейсике делал заливку простым стековым методом - все куда проще было (строк 10 кода). Фактически, функция fill. Можно к ней рандому нагнать, только особого смысла нет...
adhocprog; +1 Ответить
16. etmarket 890 12.10.21 15:36 Сейчас в теме
(14) все остальные мальчики в девстве думали о другом)
smit1c; torbeev; +2 Ответить
54. RustIG 1351 15.10.21 09:15 Сейчас в теме
(16) не всем быть Биллом Гейтсом, Илоном Маском, Стивом Джобсом.... почитайте биографии этих выдающихся людей...
62. starik-2005 3033 19.10.21 11:30 Сейчас в теме
(16)
в девстве думали о другом
У меня времени на все хватало в отличие от "остальных мальчиков". Так что искренне сочувствую.
63. etmarket 890 19.10.21 12:28 Сейчас в теме
(62) не стоит оскорбляться из-за милой шутки. Самоирония - конёк интеллектуалов ;-) Уважение вам за столь ранее увлечение программированием!
64. starik-2005 3033 19.10.21 13:34 Сейчас в теме
(63)
оскорбляться
Поворот! )))
15. SerVer1C 748 12.10.21 13:53 Сейчас в теме
Тут надо использовать обычный backtracking алгоритм. Если на очередной клетке > 1 пути, рекурсивно идем далее.
18. gybson 12.10.21 16:00 Сейчас в теме
(15)для того и асинхронность очень пригодится
17. CheBurator 3119 12.10.21 15:47 Сейчас в теме
так вроде для такого вида лаибиринта правило правой руки сработает...?
19. PanKir 70 12.10.21 16:03 Сейчас в теме
(17) не всегда, если правая стенка окажется "отдельно стоящей" от всех остальных, то просто зациклимся, но я тоже считаю, что не стоит забывать это правило при оптимизации
33. CheBurator 3119 12.10.21 18:59 Сейчас в теме
(19) ну так в этом лабиринте вроде такой ситуации нет...?
39. PanKir 70 13.10.21 10:40 Сейчас в теме
(33) ну, как я понял, лабиринт рандомный, то есть при каждом обновлении страницы - новый лабиринт, а какие там заложены алгоритмы создания - знает только Яндекс :)
так что нельзя исключать вероятность того, что когда-нибудь сформируется "совсем плохой" лабиринт для правила правой/левой руки...
42. CheBurator 3119 13.10.21 11:09 Сейчас в теме
(39) ну, тогда можно не исключать что сформируется лабиринт без выхода..
20. uno-c 234 12.10.21 16:16 Сейчас в теме
22. Tatitutu 3855 12.10.21 17:18 Сейчас в теме
Отличное решение +

Когда тоже "баловался" вот обработка лабиринт для 1С 8.2-8,3 (обычные формы) код открыт
Прикрепленные файлы:
v8Labirint.epf
PeRom; brr; Bessondo; +3 Ответить
23. s22 19 12.10.21 17:19 Сейчас в теме
async function processArray(array) {
// делаем "map" массива в промисы
const promises = array.map(delayedLog);
// ждем когда всё промисы будут выполнены
await Promise.all(promises);
console.log('Done!');
}

Может аналогично этому?
и просто передать сразу все точки карты
26. John_d 5277 12.10.21 17:31 Сейчас в теме
(23) откуда возьмутся все точки карты.
К примеру стоим в ячейке (х=1,y=1) мы можем вызвать метод state (посмотреть, где выходы из этой ячейки) только для ячейки (х=1,y=1.). Если попытаемся вызвать state для (х=1,y=2) получим сообщение "нет доступа". Нужно сделать шаг вниз и только тогда вызвать state (х=1,y=2)
27. s22 19 12.10.21 17:39 Сейчас в теме
(26)
Нужно сделать шаг вниз и только тогда вызвать state (х=1,y=2)

В примере вроде не так
28. s22 19 12.10.21 17:39 Сейчас в теме
Да и зачем тогда передавать координаты?
29. John_d 5277 12.10.21 17:45 Сейчас в теме
(28) (27) В этом примере?
return game.right(start.x, start.y)
         .then(() => game.right(start.x + 1, start.y))
         .then(() => game.right(start.x + 2, start.y))
         .then(() => game.right(start.x + 3, start.y))
         .then(() => game.right(start.x + 4, start.y))
         .then(() => game.right(start.x + 5, start.y))
         .then(() => ({ x: start.x + 6, y: start.y }));


это return из функции main(game, start), т.е. в этой точке { x: start.x + 6, y: start.y } должен быть обязательно finish=true, если он false то выход не найден и все конец.
30. s22 19 12.10.21 17:49 Сейчас в теме
(29)

return await state(start.x + 6,start.y)
31. John_d 5277 12.10.21 17:57 Сейчас в теме
(30) для начал нужно сделать пять шагов вправо чтобы выполнить return await state(start.x + 6,start.y), иначе "нет доступа"
32. s22 19 12.10.21 18:53 Сейчас в теме
(31)
(30) для начал нужно сделать пять шагов вправо чтобы выполнить return await state(start.x + 6,start.y), иначе "нет доступа"


А нужно посетить сейчас или достаточно, что бы узел был когда либо посещен?
37. John_d 5277 13.10.21 09:10 Сейчас в теме
(32) lдостаточно.
Вот точное условие задачи:

В задаче требуется написать функцию для выхода из лабиринта (гарантируется, что выход есть всегда).

Далее описание функции и параметров дано на Typescript, но функцию требуется написать на JS.

// Функция должна вернуть точку x, y, для которой game.state(x, y).finish === true
// start - некая начальная точка.
// Не деструктурируйте game, ваше решение не будет проходить тесты.
module.exports = function main(game: Game, start: Point): Promise<Point> {

}
У game есть асинхронные функции, которые позволяют двигаться от любой ячейки влево/вправо/вверх/вниз (при попытке шагнуть в стену или шагнуть из не посещенной клетки кидает ошибку). А также асинхронная функция получения состояния ячейки (работает только для посещенных ячеек, для остальных кидает ошибку).

Ось x в лабиринте идет слева-направа, y - сверху-вниз.

Формат данных
export interface Point {
x: number;
y: number;
}

export interface Game {
// Попытаться шагнуть из клетки лабиринта вверх
up(x: number, y: number): Promise<void>;
// Попытаться шагнуть из клетки лабиринта вниз
down(x: number, y: number): Promise<void>;
// Попытаться шагнуть из клетки лабиринта влево
left(x: number, y: number): Promise<void>;
// Попытаться шагнуть из клетки лабиринта вправо
right(x: number, y: number): Promise<void>;

// Получить состояние клетки лабиринта
state(x: number, y: number): Promise<{
top: boolean; // можно ли шагать вверх
bottom: boolean; // можно ли шагать вниз
left: boolean; // можно ли шагать влево
right: boolean; // можно ли шагать вправо
start: boolean; // ячейка - стартовая
finish: boolean; // ячейка - финиш
}>;
}
Для тестирования решения скачивайте приложенный файл labyrinth-tester.zip (ссылка "Скачать условие задачи" ниже), в нем в файле src/main.js можно писать решение и визуализировать прохождение лабиринта.
66. John_d 5277 21.10.21 12:21 Сейчас в теме
(32) Исправил алгоритм на рекурсию со множеством искателей
abyrinth-y.web.app
34. rpgshnik 3631 13.10.21 07:52 Сейчас в теме
Не увидел ограничения в задаче на количество одновременных вызовов? Код не читал, язык не знаком, но на визуализации алгоритма "серый искатель" один и ищет выход "красный куб" последовательно и долго, а можно было при каждом шаге запускать новых "сырых искателей" равных количеству выходов из "куба", если "серый искатель" заходил в тупик то самоуничтожался, в таком случае заполнение происходило бы быстрее в разы.
35. John_d 5277 13.10.21 09:05 Сейчас в теме
(34) не получится мы ограничены условием задачи, т.к. решение пишем в определенной функции export default function main(game, start)..
В этой функции у нас один искатель и получить второго нету никакой возможности и в конце пути этот искатель должен вернуть координаты выхода finish=true, чтобы их вернуть он сам должен оказаться в этих координатах.
36. rpgshnik 3631 13.10.21 09:06 Сейчас в теме
38. John_d 5277 13.10.21 10:37 Сейчас в теме
(36) может быть, нужно пробовать.
46. Serg O. 224 14.10.21 09:38 Сейчас в теме
(38) сделать 1 функцию движения до "развилки" ... на развилке, где есть 2 или 3 направления
вызываем эту же функцию (тем более она асинхронная) в каждом направлении...
про шаг вправо-влево-вверх-вниз... откуда мы идём 1 направление уже вычитается и не нужно его же проверять 1/4 экономии.

и да, уже писали выше - алгоритм выхода из лабиринта (если нет круговых) - по правилу правой руки... (или левой) - т.е. на развилке всегда выбираем 1 направление (из 2х или 3х)
про запись в массив где мы были и поиск в нём как-то не очень оптимальное решение...
можно и без этого обойтись, а при поиске по дереву, всегда идём только туда, где не были "автоматически".

всё в 1 функцию засунуто... это тем более на JavaScript не смотрится... где использование "асинх" вообще не видно
куча if else можно на выбор case или цикл из 3х направлений заменить... if долго работает в любых языках

но главное работает и поздравляем с участием в Yandex CUP !
69. John_d 5277 21.10.21 13:03 Сейчас в теме
(46)
всё в 1 функцию засунуто...


Эту функцию нужно отправлять на автопроверку.
65. John_d 5277 21.10.21 12:20 Сейчас в теме
(36) Вы оказались правы. Переделал на рекурсия.
abyrinth-y.web.app
rpgshnik; +1 Ответить
40. s22 19 13.10.21 10:42 Сейчас в теме
(35)
координаты


посылаем сразу 200 случайных движений (можно 3 вперед, 3 вправо,3 назад, 3 влево)

после окончания всех собираем стайты и смотрим на выход на границу области после чего запускам предыдущий алгоритм
47. Serg O. 224 14.10.21 09:44 Сейчас в теме
(40) тут задача была просто найти выход, а не оптимальный
да, есть такой "Муравьиный" алгоритм для поиска мин.длины маршрута.
https://ru.wikipedia.org/wikiМуравьиный_алгоритм

Оптимальнее наверное не сразу 200 разных, а только на развилках разделять...
на 2, максимум 3 направления дальнейшего движения.
41. s22 19 13.10.21 10:43 Сейчас в теме
Плюс в том, что мы не ждем окончания предыдущего шага, а значит ценой существенно большего количества шагов мы игнорируем задержку запросов
43. gzharkoj 502 13.10.21 12:06 Сейчас в теме
Плюс за тематику алгоритмов.
44. s22 19 13.10.21 14:05 Сейчас в теме
Тут вероятно как то зашла бы нейронка.

Еще момент, как я понял в лабиринт нельзя добавить не одной стенки не нарушив связность.
45. John_d 5277 13.10.21 17:50 Сейчас в теме
(44) да, мы вообще не можем влиять на лабиринт.
49. s22 19 14.10.21 15:43 Сейчас в теме
(45)
(44) да, мы вообще не можем влиять на лабиринт.



"Еще момент, как я понял в лабиринт нельзя добавить не одной стенки не нарушив связность. "
этой информацией можно пользоваться.

А какой критерий победы?
время поиска пути?
50. John_d 5277 14.10.21 16:53 Сейчас в теме
(49)Есть следующие ограничения:
Ограничение времени: 10 секунд
Ограничение памяти: 64.0 Мб


Найти выход за 10 секунд сам упустил такое ограничение, чуток изменил свой алгоритм начала поиска пути (вроде стал укладываться).
labyrinth-y.web.app (На всякий случай почистите кэш)
48. hobi 615 14.10.21 14:01 Сейчас в теме
Алгоритм поиска пути выхода из лабиринта (своебразный вариант игры "Life"):

Делаем матрицу размером количество ячеек + количество перегородок.
Первоначально заполняем матрицу - если там перегородка, значение 0,
если ячейка - значение 1.
Потом сканируем матрицу построчно/поколоночно.
Если рядом со сканируемой ячейкой есть хотя бы две со значением 1
или одна из них - это ячейка выхода или центральная, то сканируемая ячейка
"жива", если нет - умирает.

Через некоторое количество сканирований останется только решение с путем
выхода из лабиринта. Конец итераций - когда количество "смертей"
в итерации равно нулю.

Несколько раз просканировать матрицу и все "неправильные" пути сами умрут,
останутся только правильные. И "правильные" пути будут найдены все,
даже если их несколько. А потом уже можно выбрать из них самый короткий.
Да, еще останутся зацикленные (круговые пути), не связанные с точкой
выхода и центральной точкой. Но их может и не быть, зависит от формы лабиринта.
Проверка зацикленного пути - если при обходе пути повторно проходим
через одну и ту же ячейку. Но на решение задачи зацикленные
пути не влияют, т.к. после окончания итераций решения будем
находить, перемещаясь от центральной точки.
eeeio; brr; papami; John_d; +4 Ответить
51. hobi 615 14.10.21 20:34 Сейчас в теме
(48)
Быстродействие алгоритма можно оценить по прототипу в онлайне:
http://www.michurin.net/online-tools/life-game.html
готовый код игры на JS:
https://github.com/pmav/game-of-life/tree/master/assets/js

Для решения задачи выхода из лабиринта нужно (кроме инициализации матрицы и наложения результатов
на матрицу с лабиринтом) изменить правила "Жизни":
оставить только "смерть" и добавить правило смерти:
"рядом с точками старта и выхода не умирают".

Мы не ищем легких путей. Ждем когда трудные сами сдохнут.
58. DarkAn 1079 15.10.21 12:33 Сейчас в теме
Супер, но не всегда работает?
Прикрепленные файлы:
59. John_d 5277 15.10.21 14:52 Сейчас в теме
(58) Исправил.
Это я (50) оптимизировал запретил по x>30. Сейчас поставил x>40
67. John_d 5277 21.10.21 12:30 Сейчас в теме
(58) Исправил алгоритм на рекурсию.
60. obmanOZ 33 18.10.21 09:35 Сейчас в теме
Первый лабиринт прошелся ) после обновы страницы завис на такой картинке
Прикрепленные файлы:
61. John_d 5277 18.10.21 09:40 Сейчас в теме
(60) почистите кэш и запустите еще раз.
Сделал чтобы мог правее дальше проходить.
Прикрепленные файлы:
68. John_d 5277 21.10.21 12:30 Сейчас в теме
(60)Исправил алгоритм на рекурсию.
70. obmanOZ 33 21.10.21 15:28 Сейчас в теме
(68) Прикольно ) ток лабиринт проходится даже в случае когда уже найдет выход )
71. John_d 5277 21.10.21 15:38 Сейчас в теме
(70) Да, не завершил остальных искателей.
Исправил.
72. user1784192 22.06.22 20:16 Сейчас в теме
(71) Приветствую, а не могли бы прислать итоговый исправленный код, чтобы полностью разобраться?
73. John_d 5277 23.06.22 11:27 Сейчас в теме
(72) код есть в статье. Это последний блок кода. Я его добавил в статью уже потом.
Упустил важное условие в задачи выход нужно найти за 10 секунд.
Поэтому исправил алгоритм добавил рекурсию. Теперь есть главный искатель, который идет по верхней линии и вызывает новых искателей (рекурсия).
user1784192; +1 Ответить
Оставьте свое сообщение