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

[Pavlovsky]

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

Формально, полученный массив не соответствует определению ортогонального массива силы 2 индекса 2. Так как по определению любая упорядоченная пара должна встречаться в любых двух столбцах ровно два раза.

Я согласен на ортогональные массивы силы 2 индекса 2, построенные по формальному определению! Только, пожалуйста, не предлагайте два одинаковых ортоганальных массива с индексом 1, поставленных друг на друга. Полупрямоугольники должны быть распределены равномерно, желательно не больше двух повторов в любых двух строках.

-- Чт авг 02, 2012 12:37:32 --

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

Ничего не понимаю! И в том, и в другом определении речь идёт о n^2 столбцах.

Я пользуюсь таким опредлением ортогонального массива.
http://ru.wikipedia.org/wiki/%D0%9E%D1% ... 0%B8%D0%B2

[whitefox]

Nataly-Mak
Приведённое Вами определение полностью соответствует определению ортогональной таблицы Холла, но отличается от определения ортогонального массива из http://designtheory.org/library/encyc/glossary/#oa

[Pavlovsky]

Граница между теми кто умеет читать?!

Цитата:

31 Stefan Falkner 16.305200 06-08-2012 @ 02:58:38
32 Quimey Vivas 12.694400 07-12-2012 @ 22:13:26

[whitefox]

И снова магическое число 31

[Nataly-Mak]

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

Nataly-Mak
Приведённое Вами определение полностью соответствует определению ортогональной таблицы Холла, но отличается от определения ортогонального массива из http://designtheory.org/library/encyc/glossary/#oa

Так ведь определение, данное в моей статье, я и взяла, наверное (!), из книги Холла.
Получается, что в других источниках ортогональный массив определяется по-другому, нежели у Холла?

-- Чт авг 02, 2012 12:13:24 --

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

Я пользуюсь таким опредлением ортогонального массива.
http://ru.wikipedia.org/wiki/%D0%9E%D1% ... 0%B8%D0%B2

Явно не для ёжиков

Ну и статья, однако! Из одного определения состоит.
Неужели никто не может написать об ортогональных массивах чуть подробнее?

Лентяи!!

[Pavlovsky]

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

Получается, что в других источниках ортогональный массив определяется по-другому, нежели у Холла?

Ваше определение ОА(n,s), совпадает с определением ортогональной таблицы по Холлу.

В других источниках дается расширенное понятие ОА. В нем 4 параметра.
Если strength=2 index=1, то получается ваше опредление ОА.

[Nataly-Mak]

Ага, спасибо, что-то начинает проясняться.
Заглянула в английскую Вики. Так там хоть пример приведён, в таблице как раз параметры фигурируют.

Не, ну наши могли бы хоть пример привести

То есть при strength=2 index=1 мы получаем именно ортогональную таблицу (ортогональный массив) по Холлу, а по-нашему - С-сильно окрашенный прямоугольник.

-- Чт авг 02, 2012 12:40:18 --

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

Вот такая идея, построения решений С+1, С+2.
Строим ортогональный массив degree С, strength 2, and index 2. Находим все полупрямоугольники и уничтожаем их вставкой символа С+1 (С+2). В крайнем случае удаляем трудные строки.

А дальше - С+3?
Вот из 9-сильной раскраски 81х10 мы получили:
1. легко 10-сильную раскраску 82х10 (класс 2);
2. не очень легко 10-сильную раскраску 83х10 (класс 3).

Дело за 10-сильной раскраской 84х10 (класс 4). Такую раскраску тоже некоторые конкурсанты получили.
Меня весьма интересут, как они это сделали. Ну, алгоритм отжига не предлагать! Это уже известно.

И дальше - 10-сильная раскраска 85х10 (класс 5). Такую вроде ещё никто не нашёл.
Наконец, красная жар-птица, за которой многие гонятся, - 10-сильная раскраска 90х10
Существует ли? Удастся ли кому-нибудь поймать эту жар-птицу?

[Nataly-Mak]

Когда-то решение C10N93 казалось недосягаемым
Сейчас проделала эксперимент.
Взяла 9-сильную раскраску 81х10, добавила к ней одноцветную строку (цвета 10), получила 10-сильную раскраску 82х10.

[кстати, своё решение C10N92 во втором классе я получала совсем по-другому]

Теперь надо добавить ещё одну строку к 10-сильной раскраске 82х10. Красивого метода я не знаю, поэтому применяю алгоритм отжига. Программе хватило 5 минут, чтобы найти 10-сильную раскраску 83х10! И решение C10N93 (класс 3) готово.

Замечу, что и это решение я получала по-другому, а именно: из 85-символьной строки Pavlovsky.
Кстати, из этой строки 10-сильная раскраска 82х10 получилась с ходу, а вот с раскраской 83х10 пришлось повозиться. Да, и раскраска 85х10 у меня содержит всего 19 ошибок!

Покажу фрагмент 10-сильной раскраски 83х10 (пока решение C10N93 ещё не всеми найдено, не могу показывать полностью );
хорошо видно добавленные две строки; первая добавленная строка была сначала одноцветной (цвет J), но программа её "разбавила".

[whitefox]

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

То есть при strength=2 index=1 мы получаем именно ортогональную таблицу (ортогональный массив) по Холлу, а по-нашему - С-сильно окрашенный прямоугольник.

Верно, если абстрагироваться от такой мелочи как:

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

Понял чем отличается ортогональный массив от ортогональной таблицы. Массив - стоит, таблица - лежит.

Впрочем, в некоторых источниках ортогональный массив тоже "лежит". А "лежачий" массив силы 2 индекса 1 уже не будет сильно-окрашенным, только "стоячий".

[Pavlovsky]

Цитата:

13 Juha Saukkola 19.638600 07-31-2012 @ 13:06:51
14 Yirmy Yasovsky 19.490800 08-02-2012 @ 16:05:01

Учитесь трудолюбию. Люди ежедневно вводят несколько новых результатов. И их труд вознагражден. Juha Saukkola выполнил норматив первого класса. Yirmy Yasovsky близок к этому.

[Nataly-Mak]

Оного трудолюбия тут явно недостаточно
Нужна ещё, как минимум, мощная техника. На моём компьютере далеко не уедешь.
Всего два ядра и 2,4 Ггц. Больше двух программ нормально выполнять не может. Если запускаю три, уже всё тормозится со страшной силой, в Интернете висну, Ворд и тот виснет, работать уже совершенно невозможно.

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

Далее ещё думалку хорошую надо иметь, не на уровне ёжиков
Чтобы уметь не только написанное в статьях реализовать, но и что-то своё, оригинальное придумать.

[Pavlovsky]

Читаю про разностные матрицы и абелевы группы.
topic12959-480.html
Мозг скоро взорвется.

[Nataly-Mak]

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

Читаю
topic12959-480.html
Мозг скоро взорвется.

Pavlovsky
я на ортогональных ЛК 14-го порядка по Тодорову чуть не свихнулась
Наверное, месяца три на всех форумах всех просила растолковать, как же он их построил, ничего никто не говорил.
Даже Тодорову письмо писала (адрес прислала дама из Швеции), увы, он не ответил.

Эх, ну и помучилась я с этими ЛК Даже стишок у меня есть, написанный в это время.

Потом, наконец, в тему пришёл tolstopuz. О! Это был настоящий праздник! Он мне всё и растолковал. Тогда я и по Тодорову построила ортогональные ЛК, и ещё много других одолела. Там ещё эти квази-разностные матрицы. Тоже весьма любопытные объекты. Кстати, именно с помощью квази-разностных матриц я предлагала решать задачу века: построение группы из трёх попарно ортогональных ЛК 10-го порядка. Тут нужны мощные вычислительные ресурсы, которых у меня ни тогда не было, ни теперь нет.
А tolstopuz написал программу по моей идее, там где-то есть его подробный отчёт о том, что у него получилось.

-- Чт авг 02, 2012 16:44:21 --

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

Вот пример.



Справа пример сильноокрашенного прямоуголника С=5 25х6, построенного по стандартной схеме с использованием полей. Пять последних строк добавлены произвольно. Можно ли в нем уничтожить все полупрямоугольники??

Да, "тряской" (алгоритм отжига) это делается легко:

(Оффтоп)

6,30,A,F,F,E,B,F,A,C,B,A,C,A,C,D,F,B,D,A,D,E,C,C,E,A,E,A,D,D,A,A,F,F,C,B,C,C,B,F,D,C,D,B,C,C,E
,D,E,B,D,D,A,E,A,B,E,B,B,B,B,B,A,B,A,D,D,C,B,A,B,E,E,C,C,B,C,A,A,F,D,C,D,F,B,C,E,D,E,C,C,F,F,
D,D,A,E,D,A,E,E,B,A,D,C,A,A,C,B,D,B,B,F,F,C,D,E,C,C,E,D,D,F,C,F,C,A,E,B,D,C,D,B,E,C,E,D,E,C,E
,D,A,E,A,D,E,E,F,A,F,E,E,F,B,E,E,F,A,E,E,F,A,F,C,D,F,B,D,F,D,F,E,B,F,D,F,A,A,C,F,F,B

Только я ваши последние 5 строк не вводила в исходную раскраску, исходной у меня была ваша 5-сильная раскраска 25х6. Программа сама добавляет 5 строк рандомом.

Таким образом, делаем вывод: добавление С строк к С-сильной раскраске вполне возможно.

-- Чт авг 02, 2012 17:05:00 --

И это ещё не всё!
Ввожу 6-сильную раскраску 30х6 в программу и программа мгновенно добавляет ещё одну строку:

(Оффтоп)

6,31,A,F,F,E,B,F,A,C,B,A,C,A,C,D,F,B,D,A,D,E,C,C,E,A,E,A,D,D,A,A,F,F,C,B,C,C,B,F,D,C,D,B,C,C,E
,D,E,B,D,D,A,E,A,B,E,B,B,B,B,B,A,B,A,D,D,C,B,A,B,E,E,C,C,B,C,A,A,F,D,C,D,F,B,C,E,D,E,C,C,F,F,
D,D,A,E,D,A,E,E,B,A,D,C,A,A,C,B,D,B,B,F,F,C,D,E,C,C,E,D,D,F,C,F,C,A,E,B,D,C,D,B,E,C,E,D,E,C,E
,D,A,E,A,D,E,E,F,A,F,E,E,F,B,E,E,F,A,E,E,F,A,F,C,D,F,B,D,F,D,F,E,B,F,D,F,A,A,C,F,F,B,B,C,A,B,F,F

И опять 31 строка!

А вот дабавить ещё одну строку и получить 6-сильную раскраску 32х6 вряд ли удастся.
Всё почему-то заканчивается на 31-ой строке.

[dimkadimon]

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

Дело за 10-сильной раскраской 84х10 (класс 4). Такую раскраску тоже некоторые конкурсанты получили.
Меня весьма интересут, как они это сделали. Ну, алгоритм отжига не предлагать! Это уже известно.

А почему вы решили что конкурсанты получили 10-силную 84х10? Я например нашел решение 94х94, но 10-силную 84х10 не нашел.

[Nataly-Mak]

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

А почему вы решили что конкурсанты получили 10-силную 84х10? Я например нашел решение 94х94, но 10-силную 84х10 не нашел.

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

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