В игре Flood Paint, цель игры - сделать так, чтобы все поле было одинакового цвета за как можно меньшее число ходов.
Игра начинается с доски, которая выглядит примерно так:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 3[3]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
В настоящее время число (представляющее цвет) в центре доски равно 3. Каждый ход квадрат в центре будет менять цвет, и все квадраты одного цвета, которые достижимы из центра, перемещаясь по горизонтали или по вертикали ( т.е. в зоне затопления центральной площади) будет меняться с ним цвета. Так что если центральный квадрат меняет цвет на 5:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 5[5]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
тогда 3, которая была слева от центра 3, также изменит цвет. Теперь из центральной можно добраться до семи пятерок, и поэтому, если мы затем изменим цвет на 4:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 4 4 4 4 1 4
6 2 4 4[4]1 1 6 6
5 5 1 2 4 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
окрашенная область снова резко увеличивается в размерах.
Ваша задача - создать программу, которая будет принимать сетку цветов 19 на 19 от 1 до 6 в любой выбранной вами форме:
4 5 1 1 2 2 1 6 2 6 3 4 2 3 2 3 1 6 3
4 2 6 3 4 4 5 6 4 4 5 3 3 3 3 5 4 3 4
2 3 5 2 2 5 5 1 2 6 2 6 6 2 1 6 6 1 2
4 6 5 5 5 5 4 1 6 6 3 2 6 4 2 6 3 6 6
1 6 4 4 4 4 6 4 2 5 5 3 2 2 4 1 5 2 5
1 6 2 1 5 1 6 4 4 1 5 1 3 4 5 2 3 4 1
3 3 5 3 2 2 2 4 2 1 6 6 6 6 1 4 5 2 5
1 6 1 3 2 4 1 3 3 4 6 5 1 5 5 3 4 3 3
4 4 1 5 5 1 4 6 3 3 4 5 5 6 1 6 2 6 4
1 4 2 5 6 5 5 3 2 5 5 5 3 6 1 4 4 6 6
4 6 6 2 6 6 2 4 2 6 1 5 6 2 3 3 4 3 6
6 1 3 6 3 5 5 3 6 1 3 4 4 5 1 2 6 4 3
2 6 1 3 2 4 2 6 1 1 5 2 6 6 6 6 3 3 3
3 4 5 4 6 6 3 3 4 1 1 6 4 5 1 3 4 1 2
4 2 6 4 1 5 3 6 4 3 4 5 4 2 1 1 4 1 1
4 2 4 1 5 2 2 3 6 6 6 5 2 5 4 5 4 5 1
5 6 2 3 4 6 5 4 1 3 2 3 2 1 3 6 2 2 4
6 5 4 1 3 2 2 1 1 1 6 1 2 6 2 5 6 4 5
5 1 1 4 2 6 2 5 6 1 3 3 4 1 6 1 2 1 2
и верните последовательность цветов, которую центральный квадрат будет менять для каждого хода, снова в формате по вашему выбору:
263142421236425431645152623645465646213545631465
В конце каждой последовательности ходов квадраты в сетке 19 на 19 должны быть одного цвета.
Ваша программа должна быть полностью детерминированной; разрешены псевдослучайные решения, но программа должна генерировать один и тот же вывод каждый раз для одного и того же теста.
Программа-победитель предпримет наименьшее общее количество шагов для решения всех 100 000 тестовых случаев, найденных в этом файле (заархивированный текстовый файл, 14,23 МБ). Если два решения предпримут одинаковое количество шагов (например, если они оба нашли оптимальную стратегию), победит более короткая программа.
BurntPizza написал программу на Java для проверки результатов теста. Чтобы использовать эту программу, запустите ваше представление и передайте вывод в файл с именем steps.txt
. Затем запустите эту программу с steps.txt
и floodtest
файл в том же каталоге. Если ваша запись верна и дает правильные решения для всех файлов, она должна пройти все тесты и вернутьсяAll boards solved successfully.
import java.io.*;
import java.util.*;
public class PainterVerifier {
public static void main(String[] args) throws FileNotFoundException {
char[] board = new char[361];
Scanner s = new Scanner(new File("steps.txt"));
Scanner b = new Scanner(new File("floodtest"));
int lineNum = 0;
caseloop: while (b.hasNextLine()) {
for (int l = 0; l < 19; l++) {
String lineb = b.nextLine();
if (lineb.isEmpty())
continue caseloop;
System.arraycopy(lineb.toCharArray(), 0, board, l * 19, 19);
}
String line = s.nextLine();
if (line.isEmpty())
continue;
char[] steps = line.toCharArray();
Stack<Integer> nodes = new Stack<Integer>();
for (char c : steps) {
char targetColor = board[180];
char replacementColor = c;
nodes.push(180);
while (!nodes.empty()) {
int n = nodes.pop();
if (n < 0 || n > 360)
continue;
if (board[n] == targetColor) {
board[n] = replacementColor;
if (n % 19 > 0)
nodes.push(n - 1);
if (n % 19 < 18)
nodes.push(n + 1);
if (n / 19 > 0)
nodes.push(n - 19);
if (n / 19 < 18)
nodes.push(n + 19);
}
}
}
char center = board[180];
for (char c : board)
if (c != center) {
s.close();
b.close();
System.out.println("\nIncomplete board found!\n\tOn line " + lineNum + " of steps.txt");
System.exit(0);
}
if (lineNum % 5000 == 0)
System.out.printf("Verification %d%c complete...\n", lineNum * 100 / 100000, '%');
lineNum++;
}
s.close();
b.close();
System.out.println("All boards solved successfully.");
}
}
Кроме того, табло, так как результаты на самом деле не отсортированы по баллам, и здесь это действительно имеет большое значение:
- 1,985,078 - smack42, Java
- 2,075,452 - user1502040, C
- 2,098,382 - тигру, C #
- 2155834 - CoderTao, C #
- 2,201,995 - MrBackend, Java
- 2,383,569 - CoderTao, C #
- 2,384,020 - Herjan, C
- 2,403,189 - Origineil, Java
- 2,445,761 - Herjan, C
- 2,475,056 - Джереми Лист, Хаскелл
- 2 480 714 - SteelTermite, C (2 395 байт)
- 2 480 714 - Herjan, Java (4 702 байта)
- 2,588,847 - BurntPizza, Java (2748 байт)
- 2,588,847 - Gero3, node.js (4,641 байт)
- 2 979 145 - Теун Пронк, Delphi XE3
- 4,780,841 - BurntPizza, Java
- 10 800 000 - Джо З., Питон
Ответы:
Ява - 1 985 078 шагов
https://github.com/smack42/ColorFill
Еще одна поздняя запись. Файл результатов, содержащий 1 985 078 шагов, можно найти здесь .
Некоторая справочная информация:
Я обнаружил эту проблему несколько лет назад, когда начал программировать свой собственный клон игры Flood-it.
«лучший из неполных» алгоритм DFS и A *
С самого начала я хотел создать хороший алгоритм решения для этой игры. Со временем я мог бы улучшить свой решатель, включив несколько стратегий, которые выполняли разные неполные поиски (аналогичные тем, которые использовались в других программах здесь), и используя лучший результат этих стратегий для каждого решения. Я даже повторно реализовал алгоритм A * от tigrou в Java и добавил его в свой решатель, чтобы получить в целом лучшие решения, чем результат tigrou.
Исчерпывающий алгоритм DFS
Затем я остановился на алгоритме, который всегда находит оптимальные решения. Я потратил много усилий, чтобы оптимизировать свою исчерпывающую стратегию поиска в глубину. Чтобы ускорить поиск, я включил хэш-карту, в которой хранятся все исследуемые состояния, чтобы при поиске можно было не исследовать их снова. Хотя этот алгоритм работает отлично и достаточно быстро решает все головоломки 14x14, он использует слишком много памяти и работает очень медленно с головоломками 19x19 в этой задаче кода.
Алгоритм Puchert A *
Несколько месяцев назад я связался с Аароном и Саймоном Puchert, чтобы посмотреть на решение Flood-It . Эта программа использует алгоритм A * -типа с допустимой эвристикой (в отличие от алгоритма Тигроу) и сокращением перемещения, аналогично поиску в Jump-Point. Я быстро заметил, что эта программа очень быстрая и находит оптимальные решения !
Конечно, мне пришлось заново реализовать этот замечательный алгоритм и добавить его в свою программу. Я попытался оптимизировать свою Java-программу так, чтобы она работала так же быстро, как и оригинальная C ++ программа братьев Пухертов. Тогда я решил сделать 100 000 тестовых случаев этого испытания. На моей машине программа работала более 120 часов, чтобы найти 1 985 078 шагов, используя мою реализацию алгоритма Puchert A * .
Это должно быть наилучшим возможным решением этой проблемы, если в программе нет ошибок, которые могут привести к неоптимальным решениям. Любые отзывы приветствуются!
изменить: добавлены соответствующие части кода здесь:
Класс AStarPuchertStrategy
часть класса AStarSolver
часть класса AStarNode
источник
C # - 2 098 382 шага
Я пробую много вещей, большинство из них терпят неудачу и до недавнего времени просто не работали вообще. Я получил что-то достаточно интересное, чтобы опубликовать ответ.
Есть, конечно, способы улучшить это еще больше. Я думаю, что идти по шагам 2M возможно.
Потребовалось около,
7 hours
чтобы получить результаты. Вот текстовый файл со всеми решениями, на случай, если кто-то захочет их проверить: results.zipПодробнее о том, как это работает:
Используется алгоритм A * Pathfinding .
Что сложно, так это найти хорошего
heuristic
. Еслиheuristic
он недооценивает стоимость, он будет работать почти как Дейкстра алгоритм , и из-за сложности доски 19x19 с 6 цветами он будет работать вечно. Если он переоценит стоимость, он быстро сойдет к решению, но не даст хороших (что-то вроде 26 ходов из 19 возможных).heuristic
Лучше всего было бы найти идеальное решение , дающее точное оставшееся количество шагов для достижения решения (это было бы быстро и дало бы наилучшее возможное решение). Это (если я не ошибаюсь) невозможно. На самом деле сначала нужно решить саму доску, а вы на самом деле пытаетесь это сделать (проблема с курицей и яйцом).Я перепробовал много вещей, вот что сработало для
heuristic
:node
представляет собой набор смежных квадратов одного цвета. Используя этоgraph
, я могу легко вычислить точное минимальное расстояние от центра до любого другого узла. Например, расстояние от центра до верхнего левого угла будет равно 10, потому что их разделяют как минимум 10 цветов.heuristic
: я играю на текущей доске до конца. Для каждого шага я выбираю цвет, который минимизирует сумму расстояний от корня до всех остальных узлов.Количество ходов, необходимое для достижения этой цели, составляет
heuristic
.Estimated cost
(используется A *) =moves so far
+heuristic
Он не идеален, поскольку слегка переоценивает стоимость (поэтому неоптимальное решение найдено). В любом случае это быстро рассчитать и дать хорошие результаты.
Мне удалось добиться огромного улучшения скорости, используя график для выполнения всех операций. В начале у меня был
2-dimension
массив. Я заливаю его и пересчитываю график при необходимости (например: для расчета эвристики). Теперь все делается с помощью графика, который рассчитывается только в начале. Для имитации шагов заливка больше не нужна, вместо этого я объединяю узлы. Это намного быстрее.источник
code blocks
чтобы подчеркнуть текст. У нас есть курсив и смелый для этого.Python - 10 800 000 шагов
В качестве последнего эталонного решения рассмотрим следующую последовательность:
Циклический переход во все времена цвета
n
означает, что каждый квадратn
будет иметь тот же цвет, что и центральный квадрат. Каждый квадрат находится на расстоянии не более 18 шагов от центра, поэтому 18 циклов гарантируют, что все квадраты будут одного цвета. Скорее всего, он закончится меньше, но программа не обязана останавливаться, как только все квадраты одного цвета; это гораздо выгоднее. Эта постоянная процедура составляет 108 шагов на тестовый пример, что в общей сложности составляет 10 800 000.источник
1 2 3 4 5 6 ...
вместо вашего текущего решения, которое дает123456...
.Ява - 2 480 714 шагов
Я сделал небольшую ошибку раньше (я поставил одно важное предложение перед циклом, а не в цикле:
источник
С - 2 075 452
Я знаю, что я крайне опоздал на вечеринку, но я видел этот вызов и хотел попробовать.
Алгоритм основан на Поиске дерева Монте-Карло с выборкой Томпсона и таблице транспонирования для сокращения пространства поиска. На моей машине это занимает около 12 часов. Если вы хотите проверить результаты, вы можете найти их по адресу https://dropfile.to/pvjYDMV .
источник
hash ^= zobrist_table[i][(int)solution[i]];
перейтиhash ^= zobrist_table[i%len][(int)solution[i]];
на исправление сбоя программы.Ява - 2
434108288847 шаговВ настоящее время выигрывает (~ 46K впереди Herjan) по состоянию на 4/26Уэлп, так что мистер Бакенд не только победил меня, но и обнаружил ошибку, которая дала обманчиво хороший результат. Это сейчас исправлено (тоже было в верификаторе! Ack), но, к сожалению, у меня сейчас нет времени, чтобы попытаться вернуть корону. Попробую позже.
Это основано на моем другом решении, но вместо того, чтобы рисовать цветом, наиболее распространенным для краев заливки, оно рисует цветом, который приведет к экспонированию краев, имеющих много смежных квадратов одного цвета. Назовите это LookAheadPainter. Я буду играть в гольф позже, если это необходимо.
РЕДАКТИРОВАТЬ: я написал верификатор, не стесняйтесь использовать, он ожидает файл steps.txt, содержащий шаги, которые выводит ваша программа, а также файл переброса: Edit-Edit: (см. OP)
Если кто-то обнаружит проблему, сообщите мне об этом!
источник
C - 2 480 714 шагов
Все еще не оптимально, но теперь оно быстрее и лучше.
источник
Джава -
245529 2201995 шаговПараллельное и кэшируемое дерево поиска на глубине 5, сводя к минимуму количество «островков». Поскольку улучшение с глубины 4 до глубины 5 было таким маленьким, я не думаю, что есть смысл улучшать его намного больше. Но если бы это потребовало улучшения, мое внутреннее чувство говорит о том, чтобы работать с вычислением количества островов как разность между двумя состояниями, а не пересчитывать все.
В настоящее время выводит на стандартный вывод, пока я не знаю формат ввода верификатора.
источник
24
привело бы к гораздо более эффективному времени выполнения.Мой последний вход: C - 2 384 020 шагов
На этот раз «проверка всех возможностей» ... Этот показатель получается при глубине, установленной на 3. Глубина при 5 должна дать ~ 2,1 млн шагов ... СЛИШКОМ МЕДЛЕННО. Глубина 20+ дает наименьшее количество возможных шагов (он просто проверяет все совпадения и самые короткие выигрыши в ходе) ... У него наименьшее количество шагов, хотя я его ненавижу, поскольку он лишь немного лучше, но производительность отстой. Я предпочитаю другую запись C, которая также есть в этом посте.
Еще один улучшенный ИИ, написанный на C - 2,445,761 шагов
Основано на SteelTermite's:
источник
Ява - 2
610 797610 4 841 шагов(Fill-Bug исправлен, оценка теперь значительно хуже -_-)
Это мой базовый эталонный алгоритм отправки, он просто составляет гистограмму квадратов по краям окрашенной области и рисует наиболее распространенным цветом. Запускает 100к за пару минут.
Очевидно, что не победит, но это, конечно, не последний. Я, вероятно, сделаю еще одну подачу для умных вещей. Не стесняйтесь использовать этот алгоритм в качестве отправной точки.
Откомментируйте закомментированные строки для полного вывода. По умолчанию распечатывается количество шагов.
Гольф до 860 символов (не включая новые строки для форматирования), но можно было бы уменьшить его, если бы я захотел:
источник
Haskell - 2 475 056 шагов
Алгоритм аналогичен предложенному MrBackend в комментариях. Разница в том, что его предложение находит самый дешевый путь к квадрату с наивысшей стоимостью, моя жадно уменьшает эксцентриситет графика на каждом шаге.
источник
C # - 2 383 569
Это глубокий обход возможных решений, который примерно выбирает путь наилучшего улучшения (аналогично / как в записи Херьяна C), за исключением того, что я умно изменил порядок генерации кандидатов в решения после того, как Herjan разместил те же цифры. Занимает больше 12 часов, чтобы бежать.
источник
Ява - 2 403 189
Это должно было быть моей попыткой грубой силы. Но! Моя первая реализация «лучшего» выбора одной глубины дала:
Код, используемый для обоих, одинаков с грубой силой, хранящей «снимок» других возможных ходов и запускающей алгоритм для всех из них.
При работе с «многократным» проходом случаются случайные сбои. Я настраиваю первые 100 записей головоломки в модульном тесте и могу выполнить 100% проход, но не 100% времени. Чтобы компенсировать это, я просто отслеживал текущий номер головоломки во время сбоя и запускал новую тему, где остановился последний. Каждый поток записал свои соответствующие результаты в файл. Затем пул файлов был сжат в один файл.
Node
представляет плитку / квадрат доски и хранит ссылку на всех ее соседей. Отслеживайте триSet<Node>
переменные:Remaining
,Painted
,Targets
. Каждая итерация рассматриваетTargets
возможность группировки всехcandidate
узлов по значению, выбираяtarget value
количество «затронутых» узлов. Эти затронутые узлы затем становятся целями для следующей итерации.Источник разбросан по многим классам, и фрагменты не очень значимы вне контекста целого. Мой источник может быть просмотрен через GitHub . Я также возился с JSFiddle демонстрацией для визуализации.
Тем не менее, мой метод рабочей лошадки из
Solver.java
:источник
C # - 2
196462 2155834По сути, это тот же подход «искать лучшего потомка», что и у моего другого решателя, но с несколькими оптимизациями, которые с помощью параллелизма едва позволяют ему перейти на глубину 5 за чуть менее 10 часов. В ходе тестирования я также обнаружил в оригинале ошибку, из-за которой алгоритм иногда брал неэффективные маршруты до конечного состояния (он не учитывал глубину состояний со счетом = 64; обнаружен при игре с результатами глубины). = 7).
Основное различие между этим и предыдущим решателем заключается в том, что он сохраняет в памяти состояния Flood Game, поэтому ему не нужно восстанавливать 6 ^ 5 состояний. Основываясь на использовании процессора во время работы, я вполне уверен, что он перешел с привязки процессора к пропускной способности памяти. Большое удовольствие. Так много грехов.
Изменить: По причинам, алгоритм 5 глубины не всегда дает лучший результат. Чтобы улучшить производительность, давайте просто сделаем глубину 5 ... и 4 ... и 3 и 2 и 1, и посмотрим, что лучше. Брился еще 40к ходов. Поскольку глубина 5 составляет большую часть времени, добавление 4 к 1 только увеличивает время выполнения с ~ 10 часов до ~ 11 часов. Ура!
источник
Delphi XE3 2 979 145 шагов
Итак, это моя попытка. Я называю изменяющуюся часть каплей, каждый ход она будет делать копию массива и проверять каждый возможный цвет, чтобы увидеть, какой цвет даст самый большой шарик.
Запускает все головоломки за 3 часа и 6 минут
Думая о методе брутфорса.
Может быть, весело на эти выходные ^^
источник
Javascript / node.js - 2 588 847
Алгоритм немного отличается от большинства здесь, поскольку он использует предварительно вычисленные области и различия состояний между вычислениями. Он работает менее 10 минут, если вы беспокоитесь о скорости из-за JavaScript.
источник
C-код, который гарантированно найдет оптимальное решение с помощью простой грубой силы. Работает для сеток произвольного размера и всех входов. Занимает очень, очень много времени, чтобы работать на большинстве сеток.
Заполнение паводка крайне неэффективно и зависит от рекурсии. Возможно, вам придется увеличить ваш стек, если он очень маленький. Система грубой силы использует строку для хранения чисел и простое добавление с переносом, чтобы перебрать все возможные варианты. Это также крайне неэффективно, поскольку повторяет большинство шагов в квадриллионы раз.
К сожалению, я не смог проверить его на всех тестовых случаях, так как умру от старости до того, как он закончится.
Насколько я могу сказать, это текущий победитель. Конкурс требует, чтобы:
Проверьте
Так как это всегда находит наименьшее количество шагов для завершения каждой доски, и ни один из остальных не делает, это в настоящее время впереди. Если кто-то может предложить более короткую программу, он может выиграть, поэтому я представляю следующую оптимизированную по размеру версию. Выполнение немного медленнее, но время выполнения не является частью условий победы:
источник