Ходи оно всё конём!
Показал малому новое развлечение: обходить шахматную доску ходом коня. Как фигуры ходят, он уже знает.
Когда-то в средних классах я этим развлекался, но обойти доску 8х8 обычно не выходило (7х8, кстати, обходится гораздо легче). А тут назвался груздем и... с первого раза обошёл. Сам не понял, как :)
Обошёл я её в виде заполненной цифрами бумажки, а малой потом сам воспроизводил маршрут уже по доске: передвигал коня, а заодно собрал все мелкие монетки в доме и добавил к своей сокровищнице, чтобы отмечать обойдённые клетки.
Развлечение зашло: однажды, когда я предложил походить по шахматной доске ходом коня, малой немедленно бросил мультик!
Поскольку мой первоначальных успех в тетрадке в клеточку был уже изрядно замалёван, малой требовал новых маршрутов, а повторить с налёту первый успех не вышло - пришлось вспомнить, что яжпрограммист. Написал небольшую программку для поиска маршрутов вглубь. Запустил. Отловил парочку off-by-one ошибок. Оно ещё попыхтело, но за приемлемое время ничего не нашло.
Вспомнил, что яжсиньорпрограммист. Усложнил программу: первый ход по-прежнему в A1 (да, это вряд ли оптимально для поиска незамкнутых маршрутов, но я всегда так делаю наверное, потому у меня обычно и не получается), второй - в B3 (потому что C2 - это точно то же самое, с точностью до симметрии), третьего хода доступно 5 вариантов, их я раздал параллельным потокам (ибо ядер у моего старого походного ноута всего 4). Оно ещё попыхтело, выдало первый маршрут в виде последовательности клеток. Отнёс этот маршрут малому, нарисовал ему в тетрадке доску с большими клетками, и он пол вечера заполнял доску номерами ходов (заодно потренировал концепцию координат, рукописание цифр, а также, надеюсь, таки запомнил первые 8 латинских букв)
Потом я ещё раз вспомнил, что яжмегасиньорпрограммист. Переписал программу с объектов на примитивы, и увидел я, что это хорошо: скорость генерации новых маршрутов возросла в разы. Потом оно ещё попыхтело и нагенерило мне, прежде чем я его остановил, ещё несколько десятков тысяч маршрутов.
Лог начинается так:
Thread Thread-0 started with: [A1, B3, D2]
Thread Thread-1 started with: [A1, B3, D4]
Thread Thread-2 started with: [A1, B3, A5]
Thread Thread-3 started with: [A1, B3, C1]
Thread Thread-4 started with: [A1, B3, C5]
Продолжается же лог десятками тысяч маршрутов, но все они начинаются одинаково: [A1, B3, C1,... Все эти успешные результаты (полученные при поиске вглубь с такой уж процедурой перебора очередных ходов, какую я в неё засунул) выданы одним поисковым потоком, которому повезло начать с какой-то особенно удачной точки. Остальные 4 поисковика (в первую, однопоточную попытку я начал фактически с одного из них, а до остальных начальных отрезков дело дошло бы очень нескоро), пыхтя наравне с этим удачливым, не нашли за то время, пока я их гонял, ничего.
В общем, тот чувак из притчи, который не продолжал скакать на дохлой лошади до конца копал один колодец на нужную глубину, а начинал много колодцев в разных местах (но ни один из них не докопал), был не так уж и не прав. Хотя свою задачу о многоруком бандите (1, 2) он в той притче проиграл.
x-post: https://livelight.dreamwidth.org/565196.html
Когда-то в средних классах я этим развлекался, но обойти доску 8х8 обычно не выходило (7х8, кстати, обходится гораздо легче). А тут назвался груздем и... с первого раза обошёл. Сам не понял, как :)
Обошёл я её в виде заполненной цифрами бумажки, а малой потом сам воспроизводил маршрут уже по доске: передвигал коня, а заодно собрал все мелкие монетки в доме и добавил к своей сокровищнице, чтобы отмечать обойдённые клетки.
Развлечение зашло: однажды, когда я предложил походить по шахматной доске ходом коня, малой немедленно бросил мультик!
Поскольку мой первоначальных успех в тетрадке в клеточку был уже изрядно замалёван, малой требовал новых маршрутов, а повторить с налёту первый успех не вышло - пришлось вспомнить, что яжпрограммист. Написал небольшую программку для поиска маршрутов вглубь. Запустил. Отловил парочку off-by-one ошибок. Оно ещё попыхтело, но за приемлемое время ничего не нашло.
Вспомнил, что яжсиньорпрограммист. Усложнил программу: первый ход по-прежнему в A1 (да, это вряд ли оптимально для поиска незамкнутых маршрутов, но я всегда так делаю наверное, потому у меня обычно и не получается), второй - в B3 (потому что C2 - это точно то же самое, с точностью до симметрии), третьего хода доступно 5 вариантов, их я раздал параллельным потокам (ибо ядер у моего старого походного ноута всего 4). Оно ещё попыхтело, выдало первый маршрут в виде последовательности клеток. Отнёс этот маршрут малому, нарисовал ему в тетрадке доску с большими клетками, и он пол вечера заполнял доску номерами ходов (заодно потренировал концепцию координат, рукописание цифр, а также, надеюсь, таки запомнил первые 8 латинских букв)
Потом я ещё раз вспомнил, что яжмегасиньорпрограммист. Переписал программу с объектов на примитивы, и увидел я, что это хорошо: скорость генерации новых маршрутов возросла в разы. Потом оно ещё попыхтело и нагенерило мне, прежде чем я его остановил, ещё несколько десятков тысяч маршрутов.
Лог начинается так:
Thread Thread-0 started with: [A1, B3, D2]
Thread Thread-1 started with: [A1, B3, D4]
Thread Thread-2 started with: [A1, B3, A5]
Thread Thread-3 started with: [A1, B3, C1]
Thread Thread-4 started with: [A1, B3, C5]
Продолжается же лог десятками тысяч маршрутов, но все они начинаются одинаково: [A1, B3, C1,... Все эти успешные результаты (полученные при поиске вглубь с такой уж процедурой перебора очередных ходов, какую я в неё засунул) выданы одним поисковым потоком, которому повезло начать с какой-то особенно удачной точки. Остальные 4 поисковика (в первую, однопоточную попытку я начал фактически с одного из них, а до остальных начальных отрезков дело дошло бы очень нескоро), пыхтя наравне с этим удачливым, не нашли за то время, пока я их гонял, ничего.
В общем, тот чувак из притчи, который не продолжал скакать на дохлой лошади до конца копал один колодец на нужную глубину, а начинал много колодцев в разных местах (но ни один из них не докопал), был не так уж и не прав. Хотя свою задачу о многоруком бандите (1, 2) он в той притче проиграл.
x-post: https://livelight.dreamwidth.org/565196.html