AZsPCs: Hexagonal Neighbors

[dmd]

Стартовал новый конкурс: заполняем шестиугольные сетки

http://azspcs.com/Contest/HexagonalNeighbors

[dobrichev]

Используется синтаксис Python

 1 . . . . . . 1 . . . . . . 1 . . .
. . . 1 . . . . . . 1 . . . . . . 1
 . . . . . 1 . . . . . . 1 . . . . .
. 1 . . . . . . 1 . . . . . . 1 . .
 . . . 1 . . . . . . 1 . . . . . . 1
. . . . . . 1 . . . . . . 1 . . . .
 . 1 . . . . . . 1 . . . . . . 1 . .
. . . . 1 . . . . . . 1 . . . . . .
 . . . . . . 1 . . . . . . 1 . . . .
. . 1 . . . . . . 1 . . . . . . 1 .
 . . . . 1 . . . . . . 1 . . . . . .

On infinite plane 1 must be placed not rarely than once in each 7 cells.
In the above example the rest of the cells could be safely populated by 2.

[dobrichev]

Actually filling the whole plane with 1,2,3,4,5,6,7 in this way is trivial.

[dmd]

Нам же надо не тривиальное заполнение, а оптимальное - чтоб сумма была максимальна. Другой момент, наложите на бесконечную плоскость фактическую сетку конкретного n. Где гарантия, что в итоге граничные ячейки будут иметь всех нужных соседей?

[dobrichev]

This was only a first approximation for the upper limit under assumption that the patches required for fixing the borders don't penetrate to the central cells.
Filling the plane with the following pattern gives average value of 4 per cell.

Используется синтаксис C

 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6
7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1
 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5
4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3
 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1
2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7
 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3
6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4
 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7
5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2
 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4
 

I wouldn't be surprised if any usage of 7 leads to a non-optimal distribution for honeycombs of finite size.

[12d3]

Можно получить верхнюю оценку на сумму чисел.
Из каждой клетки нарисуем стрелочки до некоторых ее соседей таким образом: если в клетке число $k$, то проводим $k-1$ стрелочек, по одной в $1,2, ... , k-1$. Например, если у клетки с $4$ соседи $(1,1,2,3,5,7)$, то проводим три стрелки - одну в любую из единиц, одну в двойку и одну в тройку. Тогда суммаррное количестве стрелок равно сумме чисел в клетках минус количество клеток, т.е. равно оценке, которую мы получим за расстановку. Но количество стрелок не превосходит количества пар соседних клеток, коих $(3n-3)(3n-2)$. Полученные участниками оценки находятся довольно близко к этому пределу.

[dimkadimon]

Интересная задача, но боюсь слишком простая для 3х месяцев. Оценка $(3n-3)(3n-2)$ хорошая.

[dimkadimon]

Я поспешил с оценкой сложности. Похоже что задача лёгкая только для лидера, а для остальных ещё есть над чем потрудиться. Нашёл первые 4 оптимальных решения и пока что не вижу никаких простых закономерностей. Кстати 7 в них присутствуют.

[jcmeyrignac]

On larger grids, patterns are obvious.

[dimkadimon]

Does that mean that the problem is pretty much dead and we will see many people reach 25.00?

[dmd]

Вчера N11 сменилось с 900 на 901, и это был не лидер. Но сегодня N11 лидер уже подтянул.

[dimkadimon]

dmd в сообщении #1352791 писал(а):

Вчера N11 сменилось с 900 на 901, и это был не лидер. Но сегодня N11 лидер уже подтянул.

Верно. А N27 увеличилось от 6062 до 6066 за последние дни. Значит еще есть небольшая надежда улучшить результаты.

[dimkadimon]

За один день изменилось 4 рекорда.

[12d3]

Тут даже N8 увеличивалось недавно. Что особенно печально, потому что мой якобы полный перебор новый рекорд не находит.

[Herbert Kociemba]

Using pencil and paper to find the optimal solution for N=3 (which took me some days) was very helpful to develop some ideas how to approach the problem with a computer program which I started coding yesterday. I impose some restriction how the numbers are placed and the program runs better than I thought. Up to N=7 it gives "optimal" solutions within less than a minute, but for N=8 it gives only score 441 instead of 442 (also in less than 1 min). More by accident I found the 442 somehow by trying some program modifications. Nevertheless I will try the original version on larger N and will see if it gives some reasonable good solutions (or solutions at all...)