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

[Nataly-Mak]

Pavlovsky
спасибо за краткое изложение алгоритмов, которые опубликовал Herbert.
Ну, хоть примерно будем знать, как работает мысль одного из лидеров конкурса

[Zealint]

(Nataly-Mak)

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

Но не вы ли тут выступали против такого решения, когда я сказала: "Своей головой надо думать, господа"? Вспомните: компьютер, паяльник...
Если вы начнёте заниматься магическими квадратами и всё будете решать с нуля, вам жизни не хватит. Потому что у магических квадратов многовековая история. Всё начинать с нуля, по-моему, глупо.

Нет, вы все не так поняли. Я не собирался стать специалистом по магическим квадратам. Просто взял и начал разбираться сам, часто такая стратегия сразу приводит к новым научным результатам. В квадратах я посмотрел, что к чем и сделал для себя выводы, знаю как можно получить новые результаты, но не будут этим заниматься. Если захочу стать специалистом, начну изучать литературу. В этой же задаче всё наоборот, она связана с Дезарговыми плоскостями, которые косвенно связаны с моими научными интересами. Близкие к ней задачи я уже исследовал самостоятельно. Поэтому мне интересно теперь изучить наследие предков. Но, к сожалению, отдать всё время этой задаче не могу, так как сейчас занимаюсь другой. Я не следую каким-то жёстким догматическим правилам в своём выборе. Иногда делаю так, а иногда наоборот. Зависит от внутренних убеждений.

[Nataly-Mak]

Ой, туплю...

Если квадрат NxN c-coloring повернуть на 90 градусов, он ведь останется c-coloring.
Так, а если прямоугольник 50х100 10-coloring повернуть на 90 градусов, он ведь тоже останется 10-coloring?
То есть я имею прямоугольник 100х50 10-coloring. Или не имею?

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

Да, всё верно.
Взяла сейчас прямоугольник 81х9 strong 9-coloring, понятно, что он будет и 9-coloring.
Сначала проверила его в программе Эда, как прямоугольник 81х9, а затем, как прямоугольник 9х81. В обоих случаях ошибок не обнаружено.

Дык, вроде очевидный факт

Пойду смотреть на свой прямоугольник 50х100 10-coloring.
Ежели его повернуть, то будет прямоугольник 100х50 10-coloring. Это уже хороший прямоугольничек. Может, даже полезный

Хэ-х...А программа Эда не поворачивает прямоугольник, она с ним делает нечто другое.

[dimkadimon]

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

Ой, туплю...

Если квадрат NxN c-coloring повернуть на 90 градусов, он ведь останется c-coloring.
Так, а если прямоугольник 50х100 10-coloring повернуть на 90 градусов, он ведь тоже останется 10-coloring?
То есть я имею прямоугольник 100х50 10-coloring. Или не имею?

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

Да, всё верно.
Взяла сейчас прямоугольник 81х9 strong 9-coloring, понятно, что он будет и 9-coloring.
Сначала проверила его в программе Эда, как прямоугольник 81х9, а затем, как прямоугольник 9х81. В обоих случаях ошибок не обнаружено.

Дык, вроде очевидный факт

Пойду смотреть на свой прямоугольник 50х100 10-coloring.
Ежели его повернуть, то будет прямоугольник 100х50 10-coloring. Это уже хороший прямоугольничек. Может, даже полезный

Хэ-х...А программа Эда не поворачивает прямоугольник, она с ним делает нечто другое.

Всё верно. НО если повернуть прямоугольник strong c-coloring то он может не стать strong c-coloring.

[Nataly-Mak]

dimkadimon в сообщении #590237 писал(а):

Всё верно. НО если повернуть прямоугольник strong c-coloring то он может не стать strong c-coloring.

Спасибо.
Да, про strong c-coloring понятно. Это свойство при повороте может оказаться нарушенным.

А можно в программе Эда повернуть прямоугольник на 90 градусов?

[dimkadimon]

Мне Ед написал. Можно CTRL+right click чтобы увидеть все команды для под-квадратов. Скоро будет новая версия программы. Все опции можно узнать в инструкциях, но у меня сейчас нет времени перевести.

[Pavlovsky]

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

А можно в программе Эда повернуть прямоугольник на 90 градусов?

Ставишь в subgrid N. Тогда весь квадрат становится подквадратом.

[Nataly-Mak]

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

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

А можно в программе Эда повернуть прямоугольник на 90 градусов?

Ставишь в subgrid N. Тогда весь квадрат становится подквадратом.

Пока ничего не поняла.
У меня есть прямоугольник 100х50, 100 строк, 50 столбцов.
При вводе его в программу Эда пишу в самом начале: 50,100,... (у него размер по Х - это количество столбцов, размер по Y - это количество строк).
Так, ввела прямоугольник 100х50.
Дальше что делать?

Достроила свой прямоугольник 100х20 10-coloring:



Хороший прямоугольник получился

Итак, с первым пунктом алгоритма разобрались все: прямоугольников 100х20 10-coloring уже много настроили.
Прямоугольник Zealint'а - раз. Мой прямоугольник - два.
В прямоугольнике dimkadimon 100x30 содержится сразу 3 разных прямоугольника 100х20.
В моём прямоугольнике 100х50 содержится 10 разных прямоугольников 100х20.

Все прямоугольники являются 10-coloring.

Внимание, svb!

Я выкладываю алгоритм построения квадрата 100х100 10-coloring.
Конечно, алгоритм не "эпохальный", как вы однажды изволили выразиться о моём алгоритме в конкурсе с картами. Ну, на эпохальность не претендую
Более того: вообще не гарантирую, что алгоритм приведёт к успеху даже при очень хорошей реализации.
А успеха может не быть по той простой причине, например, что квадрат 100х100 10-coloring не существует. Такое может быть? А кто сказал, что он существует? Это кем-нибудь уже доказано? Где? Когда? В какой статье написано?

Итак:

1. построить прямоугольник 100х20 10-coloring;
Этот пункт легко реализуем. Тут уже показано несколько таких прямоугольников. И их можно настроить море.

2. Прямоугольник 100х20 10-coloring не годится для применения леммы 4.3 даже в том усиленном варианте, который мы с вами вроде тут изобрели
Поэтому его надо доработать, чтобы он годился.
Не уверена, что эти прямоугольники поддаются такой доработке. Не пыталась это делать, да и программы у меня нет такой.
Но почему бы нет? Ведь квадраты (прямоугольники) с-coloring с ошибками поддаются доработке в программе Эда, ошибки "убиваются".
Будем предполагать оптимистический вариант: прямоугольники доработке поддаются.

3. Применить к доработанному прямоугольнику лемму 4.3.
Этот пункт выполняется элементарно.

Так что, в алгоритме сложным является только пункт 2.

Можно в пункте 1 строить прямоугольники 100х50 c-coloring. Такие прямоугольники тоже строятся, один я уже построила.
В таких прямоугольниках другие условия для повторяющихся цветов, нежели в прямоугольниках 100х20.

Какие прямоугольники строить проще и, главное, какие проще дорабатывать, могли бы показать эксперименты. Но экспериментаторов пока не имеется

Другой путь: не выполнять пункт 2. Сразу применяем к прямоугольнику 100х20 (или к прямоугольнику 100х50) лемму 4.3 и получаем квадрат 100х100, в котором будет много ошибок. Пытаемся "вытрясти" ошибки из этого квадрата.

[Zealint]

(У нас уже более 30 миллионов этих прямоугольников!)

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

В прямоугольнике dimkadimon 100x30 содержится сразу 3 разных прямоугольника 100х20.

У меня есть странное подозрение, что в нём все-таки 30 045 015 прямоугольников размером 100x20.

-- Пт июн 29, 2012 12:03:01 --

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

Другой путь: не выполнять пункт 2. Сразу применяем к прямоугольнику 100х20 (или к прямоугольнику 100х50) лемму 4.3 и получаем квадрат 100х100, в котором будет много ошибок. Пытаемся "вытрясти" ошибки из этого квадрата.

Уже пытался. Мой метод все ошибки не вытряхивает.

[Nataly-Mak]

Zealint в сообщении #590285 писал(а):

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

В прямоугольнике dimkadimon 100x30 содержится сразу 3 разных прямоугольника 100х20.

У меня есть странное подозрение, что в нём все-таки 30 045 015 прямоугольников размером 100x20.

Я посчитала примитивно, прямо готовые прямоугольники, просто комбинации разных столбцов - блоками по 10 штук.
Ваше замечание не изменяет ничего! Я тоже сказала о том, что таких прямоугольников можно построить море.

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

Другой путь: не выполнять пункт 2. Сразу применяем к прямоугольнику 100х20 (или к прямоугольнику 100х50) лемму 4.3 и получаем квадрат 100х100, в котором будет много ошибок. Пытаемся "вытрясти" ошибки из этого квадрата.

Цитата:

Уже пытался. Мой метод все ошибки не вытряхивает.

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

Проще простого сказать, что этот алгоритм не работает. Вы уже это сказали.

У вас есть альтернативный алгоритм, который работает?

Да, а пункт 2 вы уже тоже пытались выполнять? Более 30 миллионов прямоугольников попробовали доработать? Неужели ни один не доработался? Вот какие гадкие прямоугольники!
Тогда можно ещё 30 миллионов новых настроить, потом ещё 30 миллионов и ещё... Вот когда около миллиарда прямоугольников проверите и ни один не доработается, тогда можете сказать, что это не работает.

[Zealint]

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

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

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

[Nataly-Mak]

Да, есть у меня ещё один алгоритм, но пока не выкладываю
Просто жалко его, критики насядут опять...

По этому алгоритму я и построила прямоугольник 100х20 10-coloring. Можно дальше расширять прямоугольник тем же способом, расширение происходит блоками сразу по 10 столбцов. То есть следующий прямоугольник будет 100х30, потом 100х40 и т.д.

Замечу ещё раз, что прямоугольник 100х20 10-coloring построился этим методом очень легко.

-- Пт июн 29, 2012 13:50:49 --

Zealint в сообщении #590289 писал(а):

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

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

Проверил несколько миллиардов : )

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

Zealint в сообщении #590004 писал(а):

Нет, такой программы не делал. Как-то раз я подумал, что такой перебор будет даже сложнее, чем перебор в полном квадрате. Поэтому даже не пытался, хотя идею рассматривал.

[Zealint]

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

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

В смысле проверял те, которые надо трясти в конце. Те, которые не надо трясти по моим оценкам строить сложнее. Можете сами попробовать.

[Nataly-Mak]

Вот он - симпатичный прямоугольничек 50х100 10-coloring:



Теперь мне его надо повернуть и будет прямоугольник 100х50 10-coloring.
Так и не поняла, можно ли это сделать в программе Эда.
Придётся в другом месте поворачивать

Да, так вот интересно: много ли в этом прямоугольнике 100х50 будет ошибок, то есть несоответствий требованиям усиленной леммы 4.3? И можно ли эти ошибки "убить"?

Если бы его можно было "довести до кондиции", тогда просто применить к нему лемму и квадрат 100х100 готов.

Вот ведь полквадрата готово уже

[dimkadimon]

Zealint в сообщении #590285 писал(а):

(У нас уже более 30 миллионов этих прямоугольников!)

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

В прямоугольнике dimkadimon 100x30 содержится сразу 3 разных прямоугольника 100х20.

У меня есть странное подозрение, что в нём все-таки 30 045 015 прямоугольников размером 100x20.

-- Пт июн 29, 2012 12:03:01 --

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

Другой путь: не выполнять пункт 2. Сразу применяем к прямоугольнику 100х20 (или к прямоугольнику 100х50) лемму 4.3 и получаем квадрат 100х100, в котором будет много ошибок. Пытаемся "вытрясти" ошибки из этого квадрата.

Уже пытался. Мой метод все ошибки не вытряхивает.

Хочу добавить что я тоже уже пытался. Я пробовал трясти прямоугольники strong c-coloring и те по вашей лемме. Их так же сложно, и может даже сложнее, трясти как обычные квадраты. У меня достаточно ефективный метод тряски которым я нашел 93х93, поэтому думаю тут нужен другой подход.