Новый конкурс программистов

[Pavlovsky]

Nataly-Mak в сообщении #597048 писал(а):

Кстати, хотела спросить: строка из 85 символов - это максимум для n=10? Вы выполнили полный перебор?

Полагаю, что максимум, для того подхода, что использую. Правда перебор я прервал.
В строках явно просматриваются закономерности. Перебор с учетом этих закономерностей сделал полностью. 85 максимум.

-- Пт июл 20, 2012 08:52:19 --

Кстати о закономерностях в строках. Ранее показывалась строка для С=9, сложенная в квадрат 9х9.
Если сложить строку в прямоугольник с 10-ю колонками, то получится не менее интересная картина.

(Оффтоп)

То есть в строке явно просматривается период длинной 10.

Если посмотреть все строки. То для С=p^s, в строке прослеживается закономерность с периодом С+1. Для остальных (С=6,10) закономерность идет с периодом С. Причем если C<>p^s, то построить строку длины C^2 невозможно.

-- Пт июл 20, 2012 09:07:06 --

Nataly-Mak в сообщении #597004 писал(а):

Уф!
Ответила Тому на их форуме.

Надо ещё посмотреть все его ссылки. Интересные результаты!

Игра пошла в открытую!!

Вот неизвестный доброжелатель выложил результат 146 единиц для 27х27.

Цитата:

Here's a rectangle free 27x27 with 146 entries, and diagonal symmetry:

http://content.screencast.com/users/Tom ... 27_146.png
As text: http://pastebin.com/0UwWVxAb

[Pavlovsky]

whitefox в сообщении #597044 писал(а):

Pavlovsky
Вы нашли замечательную строку.
Она позволила найти решение C10N93.

Браво! Ваше трудолюбие, упорство и настойчивость известны уже во всем мире.
Придется мне вернуться к этой теме. Что то часто, в последнее время, стал поспешно ставить идеям пометку "бесперспективно".

[Nataly-Mak]

Pavlovsky в сообщении #597128 писал(а):

Правда перебор я прервал.

Значит, всё-таки может быть и больше символов?

Цитата:

Вот неизвестный доброжелатель выложил результат 146 единиц для 27х27.

Tom Sirgedas тоже выложил. Я ещё вчера привела копию его результата со 146 единичками в квадрате 27х27.
Хотя судя по ссылке последний результат тоже вроде Тома (?)

-- Пт июл 20, 2012 08:58:04 --

Цитата:

Ранее показывалась строка для С=9, сложенная в квадрат 9х9.

Pavlovsky
А вы пробовали строить 9-цветные раскраски по этой строке? Строка длинная. Она может дать квадрат больше чем 81х81? Или для данного алгоритма квадрат C^2xC^2 максимум?

[Pavlovsky]

Nataly-Mak в сообщении #597132 писал(а):

А вы пробовали строить 9-цветные раскраски по этой строке? Строка длинная. Она может дать квадрат больше чем 81х81? Или для данного алгоритма квадрат C^2xC^2 максимум?

Алгоритм может давать максимум C^2xC^2. Это его теоретический предел. Уверен алгоритм для C=p^s гарантировано дает решение C^2, но кому это нужно?!

[Nataly-Mak]

Россияне ходят парами
И американцы тоже.

Цитата:

1 Artem Karavaev 19.974300 07-11-2012 @ 17:37:19
2 Alex Chernov 19.941800 07-07-2012 @ 20:56:57
3 Herbert Kociemba 19.926300 07-07-2012 @ 14:29:57
4 Jarek Wroblewski 19.880200 07-09-2012 @ 09:37:20
5 Dmitry Kamenetsky 19.825800 06-22-2012 @ 15:14:03
6 Nick Gardner 19.797800 07-16-2012 @ 21:49:47
7 Natalya Makarova 19.797800 07-19-2012 @ 19:16:50
8 Valery Pavlovsky 19.792000 07-03-2012 @ 07:37:12
9 Wes Sampson 19.776900 07-07-2012 @ 00:50:31
10 Tom Sirgedas 19.704500 06-07-2012 @ 07:11:18

Пока положение россиян в таблице рейтинга вполне приличное - четверо в десятке сильнейших! Удастся ли сохранить это к концу конкурса?

По наблюдениям за развитием событий на конкурсе можно сделать вывод, что результаты за пределами двух джентльменских наборов даются не так просто. Лидеры конкурса давно не обновляли результаты. Может быть, просто придерживают пока

-- Пт июл 20, 2012 09:19:41 --

Pavlovsky в сообщении #597137 писал(а):

Алгоритм может давать максимум C^2xC^2. Это его теоретический предел. Уверен алгоритм для C=p^s гарантировано дает решение C^2, но кому это нужно?!

Жаль, что не может давать больше.
Я пробовала ещё вашу строку для C=6, прямоугольник 37х36 6-coloring получился легко.
Дальше загнала этот прямоугольник в программу Эда, дополнила до квадрата 37х37, покрутила. Удивительно, но всё опять застопорилось на 36 ошибках, как и в том прямоугольнике 37х36, который я построила давно из своего решения 36х36.

У меня из экспериментов с квадратами 37х37 вызревает гипотеза: любой квадрат 37х37, раскрашенный в 6 цветов, содержит как минимум 36 ошибок.

Кто-нибудь экспериментировал с квадратами 37х37, раскрашенными в 6 цветов? Интересно, какие получены результаты.

[whitefox]

Pavlovsky в сообщении #597131 писал(а):

Браво! Ваше трудолюбие, упорство и настойчивость известны уже во всем мире.
Придется мне вернуться к этой теме. Что то часто, в последнее время, стал поспешно ставить идеям пометку "бесперспективно".

Я тоже не особо рассчитывал на этот метод, но когда Nataly-Mak сообщила о найденном решении C10N93 (предположительно этим методом), решил к нему вернуться.
Две минуты интенсивной работы "напильником", и - результат получен
Сегодня решил проверить, что это не случайность - запустил "напильник" по новой. На повторение результата снова ушло не более пары минут.

[dimkadimon]

Nataly-Mak в сообщении #597138 писал(а):

У меня из экспериментов с квадратами 37х37 вызревает гипотеза: любой квадрат 37х37, раскрашенный в 6 цветов, содержит как минимум 36 ошибок.

Кто-нибудь экспериментировал с квадратами 37х37, раскрашенными в 6 цветов? Интересно, какие получены результаты.

Правда интересно - у меня пока тоже меньше 36 ошибок для 37х37 не получается...

[Nataly-Mak]

На форуме конкурса выложили решение C5N26, заполнены 4 цвета, каждый цвет занимает 137 ячеек, 128 ячеек пустые.
http://infinitesearchspace.dyndns.org/c ... uares-n-c2
Автор Roland Postle.

В приближении нет ошибок.
Вот вам и квадрат 26х26 с 137 единичками!

Это решение в программе Эда выглядит так:



-- Пт июл 20, 2012 12:46:48 --

Заполнила пустые ячейки в этом решении C5N26 цветом E, возникло 143 ошибки.
Мастера по "вытряхивнию" ошибок могут потрясти
Это решение перспективное, т.к. в нём размещение первых 4-х цветов хорошее.
По крайней мере, можно начать с любого из 4-х цветов, занимающих 137 ячеек, и строить решение дальше.

[Nataly-Mak]

Кажется, Nick Gardner стал вторым конкурсантом, получившим решение C10N94.

На очереди решение C10N95. Кто первый?

[Nataly-Mak]

О-о-о-о!
Эту абракадабру кто-нибудь может изложить нормальным русским языком?

Цитата:

C6N37 229 одно colouringIt может оказаться невозможным. Мой поисковик не может найти тот, который вызывает удивление (не понимаю, что я даже не пытался одного до сегодняшнего дня). Там, по крайней мере 15distinct способы, чтобы соответствовать 228 клеток в 37x37, и они имеют хорошее сочетание ofvarious строки / столбцы составляет от 4 до 7. До сих пор в С3-С5 сетей диапазона I'vefound, что при достижении плотной упаковке есть только 1-3 различных waysto ее достижения, а также строка / столбец итоговые обычно отличаются лишь на 1 (thedensity распространено "ровно"). Но, возможно, перестает быть решетки случае forbigger. Лучшее, что я получу за 229 клеток является одной с 2 ошибки / rectanglesand мой искатель достигает почти каждый раз, когда очень быстро, поэтому, возможно, это ahuge местного бассейна минимум не давая ему никогда не достигая 0 ошибка solution.There автора 38x38 прямоугольник без сетки с 237 клетками , вы можете удалить 1 ряд and1 колонки, чтобы получить ... только 228, еще один короткий Хмм. Кажется, что всем направлениям от 229 * должны * возможно Существует по крайней мере 3 различных ячейки 358 прямоугольник 50х50 без сетки, которая необходима для wouldbe C7N50, также не выглядят особенно плотной. Infact есть alsoa 359 ячейка, которую я только что нашел. И есть 51x51 372 ячейки с только 2errors, очень четко мой поисковик застревает в глубокий минимум есть, но thatdoesn't neccessarily означает, что это не в последнюю очередь, ошибка конфигурации

[dimkadimon]

Nataly-Mak в сообщении #597416 писал(а):

О-о-о-о!
Эту абракадабру кто-нибудь может изложить нормальным русским языком?

Он говорит что нашел только 2 уникальных решения для 26х26 с 138 единичками. Предлагает выложить свой алгоритм для проверки дупликатов.

[dimkadimon]

А в другом посте он написал что нашел 15 разных заполнений 37х37 228ю единичками, но ни одного с 229 единичками (хотя близко).

Кстати Nick Gardner теперь нашел 136х136. А я все ниже и ниже опускаюсь...

[Nataly-Mak]

Информация для размышления

Строю раскраски 10-strong одним и тем же методом (метод пока не озвучиваю ).
Получается любопытная закономерность:

81х10 - без ошибок
82х10 - 36 ош.
83х10 - 72 ош.
84х10 - 108 ош.
85х10 - 144 ош.
86х10 - 180 ош.
87х10 - 216 ош.
88х10 - 252 ош.
89х10 - 288 ош.
90х10 - 324 ош.
91х10 - 360 ош.

Вообще-то у меня уже есть 82х10 и 83х10 без ошибок. Сейчас пытаюсь построить 84х10 без ошибок. Увы, пока безуспешно. Но такая раскраска должна существовать, судя по тому, что существует решение C10N94.

Если бы удалось вытрясти ошибки из 90х10, то решение C10N100 было бы в кармане. Многовато ошибок

[Nataly-Mak]

Тот же метод, но с другими исходными данными:

81х10 - без ошибок
82х10 - 1 ош.
83х10 - 22
84х10 - 50
85х10 - 78
86х10 - 114
87х10 - 150
88х10 - 186
89х10 - 222
90х10 - 258
91х10 - 294
92х10 - 339

Тоже, начиная с 85х10, количество ошибок увеличивается на 36; только в последнем переходе закономерность нарушается.

Меня сейчас очень сильно интересуют раскраски 84х10
Итак, имею одну со 108 ошибками, вторую с 50 ошибками. Пока плохо.

-- Вс июл 22, 2012 16:32:41 --

Третий источник дал такие результаты:

81х10 - без ошибок
82х10 - без ошибок
83х10 - без ошибок
84х10 - 20
85х10 - 52
86х10 - 85
87х10 - 119
88х10 - 154
89х10 - 191
90х10 - 228
91х10 - 267
92х10 - 307
93х10 - 350

Уже лучше

Кстати, о регулярных и нерегулярных решениях для С=10.
Я получила регулярные решения в классах $C+1$, $C+2$.
Причём это не только для С=10, но и для всех следующих С: 12,14,18,20. Закономерность проходит для всей серии раскрасок.

В классе $C+3$ найденное мной решение для С=10 нерегулярное.
alexBlack сообщал, что он знает в этом классе регулярные решения. Я долго ломала голову над этим, так ничего и не придумала. Должно быть просто, но...

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

Вот так, возможно, и здесь: все те же исходные данные, но строим как-нибудь не совсем одинаково. И то, что очевидно для alexBlack, совсем не очевидно для меня.

В общем, я не стала до конца доламывать свою голову, она мне ещё пригодится
Бросила пока думать над этими регулярными решениями.

Вопрос интересен такой: а в классе $C+4$ кто-нибудь знает регулярные решения для этой серии раскрасок: С=10,12,14,18,20?
У нас решения в этом классе нашёл Zealint.

Zealint
вы писали, что у вас нет детерминированного алгоритма построения этих решений.
Надо ли это понимать так, что ваши решения нерегулярные?

[Zealint]

Nataly-Mak в сообщении #597881 писал(а):

Zealint
вы писали, что у вас нет детерминированного алгоритма построения этих решений.
Надо ли это понимать так, что ваши решения нерегулярные?

Я пришёл к выводу, что не знаю, что такое регулярное решение.

Детерминированного алгоритма у меня нет. Но мы же все понимаем, что любая программа, написанная на компьютере, становится детерминированной. Мой алгоритм является недетерминированным, так как в его описании присутствует рандом. Но в программе есть только генератор псевдостучайных чисел, поэтому алгоритм совершенно точно работает по заранее известному плану. То есть полученные мной решения строятся по совершенно чёткой схеме... В этой схеме всего несколько десятков или сотен миллиардов последовательных действий. Можно ли считать такое решение регулярным?

Если хотите говорить на эту тему, нужно будет дать чёткие определения.