Интересная задача на 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

+49 –2

См. также

Метод Дугласа-Пойкера

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

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

1 стартмани

30.01.2024 4594 stopa85 12

Алгоритм симплекс-метода

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

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

19.10.2023 9489 user1959478 52

Математический тренажер созданный для тестирования Вашего ребенка на предмет: умножения, деления, сложения и вычитания.

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

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023 4470 maksa2005 8

Регулярки на 1С

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

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

1 стартмани

09.06.2023 12073 8 SpaceOfMyHead 19

Мини-обзор разных решений задач

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

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023 5698 RustIG 9

Тестирование средств 1С для решения СЛАУ

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

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

23.11.2022 4825 gzharkoj 14

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

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

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

1 стартмани

21.03.2022 9286 7 kalyaka 11

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

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

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

16.12.2021 7002 fishca 12

Комментарии

Подписаться на ответы Инфостарт бот

Свернуть все

1. handscenter 68 12.10.21 11:21 Сейчас в теме

Евгений ты крут )

2. brr 184 12.10.21 11:26 Сейчас в теме

Огонь, побольше бы таких статей.

3. etmarket 918 12.10.21 11:34 Сейчас в теме

Было бы шикарно в общих чертах узнать актуальные задачи из каждого направления этого CUP: Front-End, Back-End, Mobile Development, Analytics, Algorithm, Machine Learning.

52. RustIG 1833 15.10.21 09:13 Сейчас в теме

(3)https://www.youtube.com/user/suhu9379

56. John_d 5911 15.10.21 10:14 Сейчас в теме

(52) прикольные соревнования. Я так понял это в Китае.

57. RustIG 1833 15.10.21 12:26 Сейчас в теме

(56) задача лабиринтов имеет практическое применение - особенно в роботизации - поиск людей при завалах, шпионские мини-роботы, протяжка новых трубопроводов или коаксильных интернет -кабелей в зданиях и под землей...
Просто их алгоритмы засекречены - надо своих Кулибиных подключать.

4. Jimbo 11 12.10.21 11:43 Сейчас в теме

Это язык Ява ?

5. John_d 5911 12.10.21 11:44 Сейчас в теме

(4) javaScript

6. etmarket 918 12.10.21 11:48 Сейчас в теме

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

7. CyberCerber 876 12.10.21 12:04 Сейчас в теме

(6) Как один из вариантов оптимизации: "Если непройденная область, в которой нет центра лабиринта, окружена пройденной, смысла заходить в нее нет"

8. John_d 5911 12.10.21 12:17 Сейчас в теме

(7) еще можно оптимизировать, не спускаться ниже середины лабиринта.
Но у меня более универсальное решение (вдруг что-то поменяется и выход будет не в центре)

9. CyberCerber 876 12.10.21 12:19 Сейчас в теме

(8) Ну про ниже середины не факт. Вдруг выход к центру только с правого нижнего угла? Или я что-то пропустил в условии задачи?

11. John_d 5911 12.10.21 12:36 Сейчас в теме

(9) нет такого условия, но если генерировать разные лабиринты, то можно заметить, что основной подход сверху. Но немного спускаться ниже середины нужно, не слишком глубоко.

13. John_d 5911 12.10.21 13:20 Сейчас в теме

(9) можете посмотреть добавил условие не спускаюсь ниже y<27
labyrinth-y.web.app

10. CagoBHuK 33 12.10.21 12:22 Сейчас в теме

Автор, не увидел в твоем коде ни эвристики, ни A*-search. Подобие эвристики есть в последнем куске кода, где "мест где мы еще небыли", но вообще рекомендую прочитать про оптимальные алгоритмы поиска кратчайшего пути, и в частности про эвристику. Решение, предложенное автором, не тянет даже на четверочку.

Ответить

12. John_d 5911 12.10.21 12:41 Сейчас в теме

(10) Спасибо, посмотрю.

21. s22 22 12.10.21 17:06 Сейчас в теме

(10)

вы не видите весь лабиринт стразу как я понял. Поэтому алгоритмы поиска кратчайшего пути будут во многом не применимы

24. John_d 5911 12.10.21 17:19 Сейчас в теме

(21) Все верно. Видим выходы только той клетки в которой находимся.

25. CagoBHuK 33 12.10.21 17:25 Сейчас в теме

(21) В таком случае breadth-first search простым методом стека, делается буквально несколькими строчками. Описано тут.

55. John_d 5911 15.10.21 10:06 Сейчас в теме

(25) по этому алгоритму не возможно вернуться назад когда зайдешь в тупик.
Но можно попробовать после захода в тупик ликвидировать искателя и рекурсивно начинать поиск с начала. (нужно пробовать)

53. RustIG 1833 15.10.21 09:13 Сейчас в теме

(21) как в жизни

14. starik-2005 3096 12.10.21 13:22 Сейчас в теме

В девстве на бейсике делал заливку простым стековым методом - все куда проще было (строк 10 кода). Фактически, функция fill. Можно к ней рандому нагнать, только особого смысла нет...

16. etmarket 918 12.10.21 15:36 Сейчас в теме

(14) все остальные мальчики в девстве думали о другом)

54. RustIG 1833 15.10.21 09:15 Сейчас в теме

(16) не всем быть Биллом Гейтсом, Илоном Маском, Стивом Джобсом.... почитайте биографии этих выдающихся людей...

62. starik-2005 3096 19.10.21 11:30 Сейчас в теме

(16)

в девстве думали о другом

У меня времени на все хватало в отличие от "остальных мальчиков". Так что искренне сочувствую.

63. etmarket 918 19.10.21 12:28 Сейчас в теме

(62) не стоит оскорбляться из-за милой шутки. Самоирония - конёк интеллектуалов ;-) Уважение вам за столь ранее увлечение программированием!

64. starik-2005 3096 19.10.21 13:34 Сейчас в теме

(63)

оскорбляться

Поворот! )))

15. SerVer1C 839 12.10.21 13:53 Сейчас в теме

Тут надо использовать обычный backtracking алгоритм. Если на очередной клетке > 1 пути, рекурсивно идем далее.

18. gybson 12.10.21 16:00 Сейчас в теме

(15)для того и асинхронность очень пригодится

17. CheBurator 2693 12.10.21 15:47 Сейчас в теме

так вроде для такого вида лаибиринта правило правой руки сработает...?

19. PanKir 70 12.10.21 16:03 Сейчас в теме

(17) не всегда, если правая стенка окажется "отдельно стоящей" от всех остальных, то просто зациклимся, но я тоже считаю, что не стоит забывать это правило при оптимизации

33. CheBurator 2693 12.10.21 18:59 Сейчас в теме

(19) ну так в этом лабиринте вроде такой ситуации нет...?

39. PanKir 70 13.10.21 10:40 Сейчас в теме

(33) ну, как я понял, лабиринт рандомный, то есть при каждом обновлении страницы - новый лабиринт, а какие там заложены алгоритмы создания - знает только Яндекс :)
так что нельзя исключать вероятность того, что когда-нибудь сформируется "совсем плохой" лабиринт для правила правой/левой руки...

42. CheBurator 2693 13.10.21 11:09 Сейчас в теме

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

20. uno-c 267 12.10.21 16:16 Сейчас в теме

Красава !

22. Tatitutu 3849 12.10.21 17:18 Сейчас в теме

Отличное решение +

Когда тоже "баловался" вот обработка лабиринт для 1С 8.2-8,3 (обычные формы) код открыт

Прикрепленные файлы:

v8Labirint.epf

23. s22 22 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 5911 12.10.21 17:31 Сейчас в теме

(23) откуда возьмутся все точки карты.
К примеру стоим в ячейке (х=1,y=1) мы можем вызвать метод state (посмотреть, где выходы из этой ячейки) только для ячейки (х=1,y=1.). Если попытаемся вызвать state для (х=1,y=2) получим сообщение "нет доступа". Нужно сделать шаг вниз и только тогда вызвать state (х=1,y=2)

27. s22 22 12.10.21 17:39 Сейчас в теме

(26)

Нужно сделать шаг вниз и только тогда вызвать state (х=1,y=2)

В примере вроде не так

28. s22 22 12.10.21 17:39 Сейчас в теме

Да и зачем тогда передавать координаты?

29. John_d 5911 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 22 12.10.21 17:49 Сейчас в теме

(29)

return await state(start.x + 6,start.y)

31. John_d 5911 12.10.21 17:57 Сейчас в теме

(30) для начал нужно сделать пять шагов вправо чтобы выполнить return await state(start.x + 6,start.y), иначе "нет доступа"

32. s22 22 12.10.21 18:53 Сейчас в теме

(31)

(30) для начал нужно сделать пять шагов вправо чтобы выполнить return await state(start.x + 6,start.y), иначе "нет доступа"

А нужно посетить сейчас или достаточно, что бы узел был когда либо посещен?

37. John_d 5911 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 5911 21.10.21 12:21 Сейчас в теме

(32) Исправил алгоритм на рекурсию со множеством искателей
abyrinth-y.web.app

34. rpgshnik 3815 13.10.21 07:52 Сейчас в теме

Не увидел ограничения в задаче на количество одновременных вызовов? Код не читал, язык не знаком, но на визуализации алгоритма "серый искатель" один и ищет выход "красный куб" последовательно и долго, а можно было при каждом шаге запускать новых "сырых искателей" равных количеству выходов из "куба", если "серый искатель" заходил в тупик то самоуничтожался, в таком случае заполнение происходило бы быстрее в разы.

35. John_d 5911 13.10.21 09:05 Сейчас в теме

(34) не получится мы ограничены условием задачи, т.к. решение пишем в определенной функции export default function main(game, start)..
В этой функции у нас один искатель и получить второго нету никакой возможности и в конце пути этот искатель должен вернуть координаты выхода finish=true, чтобы их вернуть он сам должен оказаться в этих координатах.

36. rpgshnik 3815 13.10.21 09:06 Сейчас в теме

(35) рекурсия?)

38. John_d 5911 13.10.21 10:37 Сейчас в теме

(36) может быть, нужно пробовать.

46. Serg O. 300 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 5911 21.10.21 13:03 Сейчас в теме

(46)

всё в 1 функцию засунуто...

Эту функцию нужно отправлять на автопроверку.

65. John_d 5911 21.10.21 12:20 Сейчас в теме

(36) Вы оказались правы. Переделал на рекурсия.
abyrinth-y.web.app

40. s22 22 13.10.21 10:42 Сейчас в теме

(35)

координаты

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

после окончания всех собираем стайты и смотрим на выход на границу области после чего запускам предыдущий алгоритм

47. Serg O. 300 14.10.21 09:44 Сейчас в теме

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

Оптимальнее наверное не сразу 200 разных, а только на развилках разделять...
на 2, максимум 3 направления дальнейшего движения.

41. s22 22 13.10.21 10:43 Сейчас в теме

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

43. gzharkoj 521 13.10.21 12:06 Сейчас в теме

Плюс за тематику алгоритмов.

44. s22 22 13.10.21 14:05 Сейчас в теме

Тут вероятно как то зашла бы нейронка.

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

45. John_d 5911 13.10.21 17:50 Сейчас в теме

(44) да, мы вообще не можем влиять на лабиринт.

49. s22 22 14.10.21 15:43 Сейчас в теме

(45)

(44) да, мы вообще не можем влиять на лабиринт.

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

А какой критерий победы?
время поиска пути?

50. John_d 5911 14.10.21 16:53 Сейчас в теме

(49)Есть следующие ограничения:
Ограничение времени: 10 секунд
Ограничение памяти: 64.0 Мб

Найти выход за 10 секунд сам упустил такое ограничение, чуток изменил свой алгоритм начала поиска пути (вроде стал укладываться).
labyrinth-y.web.app (На всякий случай почистите кэш)

48. hobi 616 14.10.21 14:01 Сейчас в теме

Алгоритм поиска пути выхода из лабиринта (своебразный вариант игры "Life"):

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

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

Несколько раз просканировать матрицу и все "неправильные" пути сами умрут,
останутся только правильные. И "правильные" пути будут найдены все,
даже если их несколько. А потом уже можно выбрать из них самый короткий.
Да, еще останутся зацикленные (круговые пути), не связанные с точкой
выхода и центральной точкой. Но их может и не быть, зависит от формы лабиринта.
Проверка зацикленного пути - если при обходе пути повторно проходим
через одну и ту же ячейку. Но на решение задачи зацикленные
пути не влияют, т.к. после окончания итераций решения будем
находить, перемещаясь от центральной точки.

51. hobi 616 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 1088 15.10.21 12:33 Сейчас в теме

Супер, но не всегда работает?

Прикрепленные файлы:

59. John_d 5911 15.10.21 14:52 Сейчас в теме

(58) Исправил.
Это я (50) оптимизировал запретил по x>30. Сейчас поставил x>40

67. John_d 5911 21.10.21 12:30 Сейчас в теме

(58) Исправил алгоритм на рекурсию.

60. obmanOZ 33 18.10.21 09:35 Сейчас в теме

Первый лабиринт прошелся ) после обновы страницы завис на такой картинке

Прикрепленные файлы:

61. John_d 5911 18.10.21 09:40 Сейчас в теме

(60) почистите кэш и запустите еще раз.
Сделал чтобы мог правее дальше проходить.

Прикрепленные файлы:

68. John_d 5911 21.10.21 12:30 Сейчас в теме

(60)Исправил алгоритм на рекурсию.

70. obmanOZ 33 21.10.21 15:28 Сейчас в теме

(68) Прикольно ) ток лабиринт проходится даже в случае когда уже найдет выход )

71. John_d 5911 21.10.21 15:38 Сейчас в теме

(70) Да, не завершил остальных искателей.
Исправил.

72. user1784192 22.06.22 20:16 Сейчас в теме

(71) Приветствую, а не могли бы прислать итоговый исправленный код, чтобы полностью разобраться?

73. John_d 5911 23.06.22 11:27 Сейчас в теме

(72) код есть в статье. Это последний блок кода. Я его добавил в статью уже потом.

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

Оставьте свое сообщение

E-mail:

Автор:

Евгений Комиссаров (John_d)

Рейтинг: 5911

Для получения уведомлений о новых публикациях автора подключите телеграм бот: Инфостарт бот

Публикация:

№ 1528864

Создание 12.10.21 10:30

Обновление 24.02.22 09:52

Статистика:

Просмотры 9882

Загрузки 0

Рейтинг 47

Комментарии 73

Характеристики:

Код открыт Да

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

Кому Программист

Тип файла Нет файла

Платформа Не имеет значения

Конфигурация Не имеет значения

Операционная система Не имеет значения

Страна Не имеет значения

Отрасль Не имеет значения

Налоги Не имеет значения

Вид учета Не имеет значения

Доступ к файлу Бесплатно (free)