Конкурс Зиммерманна о перекладывании карт

[Pavlovsky]

Vitaly12

Объясни плиз вот эту фразу:

Цитата:

b[i] contains the *sum* of the preceding and succeeding pancakes

-- Пт янв 14, 2011 17:22:50 --

Разобрался. Круто. Должно работать в разы быстрее!

[venco]

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

Разобрался. Круто. Должно работать в разы быстрее!

Увы. Нет произвольного доступа, так что линейность остаётся.

[Vitaly12]

venco в сообщении #399926 писал(а):

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

Разобрался. Круто. Должно работать в разы быстрее!

Увы. Нет произвольного доступа, так что линейность остаётся.

Ага. Есть все же некоторое улучшение

[Pavlovsky]

Еще такая проблемка. Какому классу задач принадлежить текущая проблема?

Первое что хочется проверить, является текущая задача NP- полной.

И сходу возникли проблемы. А принадлежит ли данная задача классу NP???

Пусть дана перестановка P порядка n. Определить верно ли утверждение |run(P)|>K?
Чтобы текущая задача принадлежала классу NP надо чтобы процедура определения |run(P)|>K выполнялась за полиномиальное время O(P(n)). Для этого надо чтобы либо длина пути не превышала O(P(n)) либо придумать гораздо более эффективную процедуру вычисления количества инверсий для перестановки P.

[svb]

Цитата:

I'm in 9'th place with a score of 23.59. That score hasn't changed
for several days now which leads me to observe two things:

1) It hasn't gone down, which means the overall best scores have probably just
about leveled out.

2) It hasn't gone up, which is because I haven't been able to improve on my
personal bests for the last few hundred hours of CPU time!

These contests are all about finding the right algorithm, having the right
insight. Raw CPU power - well, it helps get the last few tenths of a point but
it is secondary to thinking the right way. On this occasion inspiration has
clearly passed me by. And to be honest, I'm plumb out of ideas.

So I've decided to give the computer a rest and just watch from the sidelines in
sincere admiration as the leaders consolidate their positions. Go guys! (Unless
that inspiration does strike out of the blue, in which case it'll be back to the
editor with a vengeance...)

I look forward eagerly to reading the reports from the 24 club explaining their
search algorithms after the contest ends.

In the meantime, here are the scores for my current, and almost certainly final,
entries:

19 221
23 382
29 655
31 757
37 1174
41 1537
43 1733
47 2188
53 2923
59 3974
61 4288
67 5236
71 6134
73 6541
79 7934
83 8857
89 10951
97 13856

John Morris

[dvorkin_sacha]

Подтверждаю, что первые 4 результата имеют место быть, хотя для 29 и 31 у меня и лучшие результаты имеютя (например, для n = 29 у меня результат близок к 700, а для 19 я здесь решение опубликовал). Хочу отметить, что интересными экстремальными свойствами для n = 23 обладает несколько иное решение. На кластере эти результаты получить - раз плюнуть.

[svb]

dvorkin_sacha в сообщении #409203 писал(а):

На кластере эти результаты получить - раз плюнуть.

Mark Beyleveld (2 место):

Цитата:

Not everybody has access to supercomputers

I'm using a 3GHz i7, msdev c++ (but could as easily be c)

I can add my congratulations both both Jarek and Tom. As Jim has previously
remarked, they are both formidable competitors

Mark

[dvorkin_sacha]

svb

Я про то, что карячиться не надо. А начиная с n = 37 задача вообще уже не интересна.

[Pavlovsky]

На форуме Зимермана, народ требует продления сроков соревнования. Как к этой идее относятся русскоязычные участники конкурса?

[Nataly-Mak]

Я против.
Времени было больше чем достаточно.
Новые результаты у всех участников получаются уже с большим трудом (судя по верхним строчкам таблицы результатов, в особенности по результатам Ярослава Вроблевского; он уже примерно месяц вводит новые результаты, но почти всё время остаётся с тем же количеством баллов; было долго 24,84, сейчас, кажется, 24,86; он, конечно, находит всё новые рекорды для больших n, но при этом ему за них уже ничего не начисляется, ибо это всё тот же 1 балл за каждый новый рекорд).

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

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

Об итогах расскажу чуть позже.

[Nataly-Mak]

Финал конкурса:

Rank  Score  Contestant  Last Improvement
  
1 24.80 Jarek Wroblewski Wroclaw, Poland 8 Feb 2011 16:37 
2 24.72 Tomas Rokicki Palo Alto, California, United States 12 Feb 2011 15:45 
3 24.42 Mark Beyleveld Sugar Land, Texas, United States 12 Feb 2011 14:23 
4 24.30 Hermann Jurksch Recklinghausen, Germany 8 Feb 2011 20:08 
5 23.80 Alex Chernov Penza, Russia 12 Feb 2011 09:17 
6 23.79 Eugene Vasilchenko North Potomac, Maryland, United States 1 Feb 2011 16:11 
7 23.73 Markus Sigg Freiburg, Germany 12 Feb 2011 15:23 
8 23.64 René van de Veerdonk Fremont, California, United States 12 Feb 2011 07:05 
9 23.52 John Morris Simi Valley, California, United States 29 Jan 2011 06:19 
10 23.26 Arul Murugan Sunnyvale, California, United States 12 Feb 2011 14:05 
11 23.06 Wes Sampson La Jolla, California, United States 29 Jan 2011 01:10 
12 23.00 Lukas Kunze Gilching, Bavaria, Germany 5 Feb 2011 06:54 
13 22.88 Karl Grill Vienna, Austria 11 Feb 2011 10:44 
14 22.88 Kalachev Gleb Moscow, Russia 31 Jan 2011 14:09 
15 22.85 Igor Covganet Chisinau, Moldova 14 Jan 2011 13:54 
16 22.80 Johan Roos Lund, Sweden 7 Jan 2011 08:35 
17 22.79 Natalia Makarova Saratov, Russia 3 Feb 2011 09:48 
18 22.69 Giuliano Bertoletti Parma, Italy 2 Jan 2011 09:17 
19 22.51 Tristrom Cooke Adelaide, Australia 10 Feb 2011 21:30 
20 22.44 David Bonnet Strasbourg, France 12 Feb 2011 12:32 
. . . . . . . . . . . .

Jarek
поздравляю с победой!
Я за вас болела

У меня к вам просьба: расскажите, пожалуйста, о своих алгоритмах. Думаю, это многим будет интересно.

---------

Поздравляю также россиянина, занявшего 5-ое место. Здорово!

В прошлом конкурсе наша команда была первая среди россиян, ну... то были магические квадраты
Теперь мы третьи среди россиян.
И всего только 17-ые в мире. Если учесть, что в прошлом конкурсе было 148 участников и мы были на 18-ом месте, а в этом конкурсе 360 участников, то занятое нами место совсем неплохое.

Хотя лично я результатами команды не довольна. Могли выступить гораздо лучше. Сказались объективные и субъективные причины...

Сейчас напишу об итогах, о программах.

-- Вс фев 13, 2011 05:10:57 --

Результаты нашей команды:

19:[]:221: 12,15,11,1,10,17,19,2,5,8,9,4,18,13,16,7,3,14,6
23:[]:370: 4,17,5,12,11,14,19,22,6,21,9,15,10,7,2,13,1,23,20,16,3,8,18
29:[]:609: 7,16,17,18,9,21,6,22,20,11,13,2,8,10,4,15,5,12,27,3,14,19,28,26,1,29,25,24,23
31:[]:741: 4,17,5,12,11,14,19,22,6,21,9,15,10,7,2,13,26,23,20,16,3,8,18,28,1,29,31,30,25,24,27
37:[]:1080: 8,16,13,7,14,12,15,3,2,4,23,10,5,22,6,9,30,24,20,11,25,19,17,21,18,33,36,29,1,34,26,28,35,31,32,37,27
41:[]:1468: 20,27,31,23,19,22,26,24,25,1,39,36,30,35,37,41,33,32,34,40,28,29,7,11,17,16,13,10,5,18,12,4,3,21,8,15,2,9,14,6,38
43:[]:1700: 36,37,43,39,40,27,24,25,30,31,29,33,28,18,8,3,16,20,23,26,13,2,7,10,15,9,21,6,22,19,14,11,12,5,17,4,42,32,35,1,38,34,41
47:[]:2118: 10,42,40,12,17,20,26,28,7,2,9,13,16,8,21,4,22,6,14,11,5,32,29,25,24,23,35,33,18,27,19,3,15,30,43,34,31,39,47,38,37,41,46,36,1,44,45
53:[]:2759: 2,8,10,14,6,20,23,9,7,18,16,27,25,29,22,32,26,31,24,30,5,19,11,13,17,21,3,15,12,4,28,33,37,43,49,42,40,39,35,34,36,38,41,53,46,48,52,51,50,47,45,44,1
59:[]:3789: 33,46,41,20,26,5,40,7,6,27,45,42,25,30,31,39,47,50,44,24,15,3,21,11,28,10,36,29,19,16,4,22,8,35,51,58,12,17,2,23,13,49,59,55,52,37,34,38,43,54,48,57,1,56,18,9,14,32,53
61:[]:4017: 35,31,32,41,42,39,44,40,25,12,22,20,11,17,46,36,38,54,47,45,43,52,53,48,49,57,59,51,50,60,55,1,56,58,61,30,33,37,24,26,13,5,4,19,10,15,7,2,3,18,21,23,6,29,27,28,34,14,8,16,9
67:[]:5092: 13,28,8,34,31,26,22,24,33,7,23,14,6,19,32,18,3,16,5,10,35,46,20,11,4,9,12,30,52,41,21,25,15,36,27,42,38,37,29,53,51,56,55,49,2,43,45,39,40,44,17,50,57,47,48,58,54,64,66,61,1,63,65,62,67,59,60
71:[]:5831: 6,29,27,28,34,14,18,4,2,21,23,9,16,8,7,15,10,19,3,5,13,26,24,37,33,30,35,31,32,41,42,39,44,40,25,12,22,20,11,17,46,36,38,54,47,45,43,52,53,48,49,57,59,51,50,60,55,70,56,58,1,68,66,61,62,64,69,67,71,63,65
73:[]:6172: 71,67,63,61,62,69,66,68,72,65,73,58,56,64,55,60,50,51,59,57,49,48,53,52,43,45,47,54,38,36,46,17,11,20,22,12,25,40,44,39,42,41,32,31,35,30,33,37,24,26,13,5,3,19,10,15,7,8,16,9,23,21,2,4,18,14,34,28,27,29,6,1,70
79:[]:7565: 74,68,79,69,66,75,78,58,57,62,67,70,63,64,56,61,71,60,65,59,51,50,44,53,48,52,55,49,2,7,8,19,16,12,5,9,13,17,20,18,10,11,14,3,4,26,6,15,22,23,30,37,24,46,47,54,34,40,45,42,43,36,32,38,33,39,35,41,29,27,25,31,28,21,72,77,1,76,73
83:[]:8590: 20,23,6,44,15,11,32,3,34,7,29,33,36,43,37,19,18,30,28,2,9,27,8,14,12,24,22,10,40,4,54,47,16,41,48,17,13,31,26,35,25,38,45,49,39,42,5,21,46,55,53,51,62,50,52,63,59,57,72,64,60,56,58,61,67,68,69,65,70,73,77,66,71,80,79,75,74,83,1,82,76,78,81
89:[]:10410: 54,41,27,72,83,76,1,84,86,81,87,80,89,85,88,49,25,60,20,17,63,51,42,29,57,10,39,14,3,34,44,46,28,43,36,62,4,8,32,31,73,15,6,56,58,64,67,70,23,68,59,38,48,61,26,18,11,45,37,22,33,2,66,65,52,40,69,79,47,50,55,5,12,24,21,13,7,30,35,78,77,75,53,19,9,16,74,71,82
97:[]:12811: 25,31,28,21,72,77,83,76,73,88,82,80,81,91,89,92,97,85,87,93,84,90,86,96,95,27,29,41,35,39,33,38,32,36,43,42,45,40,34,54,47,46,24,37,30,23,22,15,6,26,4,3,14,11,10,18,20,17,13,9,5,12,16,19,8,7,2,49,55,52,48,53,44,50,51,59,65,60,71,61,56,64,63,70,67,62,57,58,78,75,66,69,79,68,74,1,94

[Nataly-Mak]

Конкурс для меня был интересен не только собственно решением задачи.
Я узнала много нового.
В самом начале темы мелькнуло слово «кластер». Я даже и не знала, что это такое.
На форуме scilog.ru меня просветили. Там же возникла очень бурная и интересная дискуссия на эту тему.

Нужен ли кластер в решении конкурсной задачи? Да, безусловно!
Конечно, задачу можно решать и на обычном компьютере, что многие и делали, я в том числе. Но полученные результаты весьма скромные. Даже тот товарищ, которого здесь цитировал svb, занял только третье место.
Кроме того, важна также и мощность компьютера, его быстродействие, наличие многоядерного процессора.
Даже и не знала, что у меня процессор одноядерный. Теперь знаю.

Разумеется, важны алгоритмы. Но всё перечисленное не менее (а в данной задаче даже более!) важно.

Далее, встреча с интересными людьми, которые заинтересовались конкурсом и написали мне.
Один из товарищей (он пожелал остаться неизвестным) прочитал дискуссию на форуме scilog.ru, написал мне, а потом блестяще реализовал мою идею тотальной проверки последовательностей, которую я изложила на указанном форуме. Программа написана для многоядерного процессора (как минимум два ядра), но работает прекрасно и на моём компьютере с одноядерным процессором. В программе параллельно работают два алгоритма – поиск вглубь и поиск вширь. (Назову автора программы Х.) Так вот, у Х двуядерный процессор, загрузка процессора при работе программы 100%.
Когда Х прислал мне эту программу, я очень долго не могла от неё оторваться, это был восторг! Я ещё никогда не видела, как работает программа для многоядерного процессора. Программа имеет прекрасный интерфейс, в программе можно задавать несколько параметров, например: лимит времени на один переход, максимальное количество добавляемых карт.
Затем Х сделал блокирование второго алгоритма (поиск вглубь), и я работала только с одним алгоритмом – поиск вширь. Большинство моих результатов найдено по этой программе.
Х прислал мне и отдельные программы для этих двух алгоритмов.

Ещё один товарищ тоже прислал письмо и подключился к решению задачи. Правда, уже почти в конце конкурса, поэтому много сделать он не успел. Написал программу для алгоритма поиска вглубь. Так у меня оказалось три программы, реализующие этот алгоритм.

Теперь о формате и программах. Небольшая критика.

Формат доставил мне очень много хлопот. Как известно, последовательность для ввода на конкурс должна задаваться с запятыми, разделяющими числа:

12,15,11,1,10,17,19,2,5,8,9,4,18,13,16,7,3,14,6

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

25 C=372: 9 12 6 7 2 14 8 19 11 13 5 4 15 16 10 3 24 17 22 18 21 25 1 23 2

а у Х такой:

25:[]:400: 8,16,13,7,14,12,15,3,2,4,23,10,5,22,6,9,1,24,20,11,25,19,17,21,18

Ну, это уже, конечно, неизбежно – каждый человек делает удобный ему формат. Тут нельзя роптать.
Но вот разные форматы у svb – это, конечно, никуда не годится. Много я критиковала его за это в личной переписке, но, по-моему, он не внял,
так и оставил разные форматы.

Теперь о программах.
Самый главный минус – это постоянно повторяющийся недостаток многих авторов. Ещё давно столкнулась с этим у ice00, когда он делал по моей просьбе программы для построения магических квадратов.
Итак, вот есть программа проверки чего-нибудь (квадрата, или последовательности, или ещё чего-то). Понятно, что проверить надо не один объект, а сотни или даже тысячи однородных объектов.
Дальше все уже догадались, в чём дело. Программу пишут для проверки только одного объекта! Получается, что если я хочу проверить тысячу объектов, то мне надо 1000 раз выполнить программу, каждый раз по новой задавая командную строку. Тогда мне один товарищ подсказал, что надо воспользоваться пакетным файлом. С тех пор много времени прошло, я освоилась с пакетными файлами. Но разве это выход? Надо задавать в программе считывание исходных данных из входного файла.

В процессе сотрудничества с svb это был постоянный бич. Это было и в программах с магическими квадратами, и в прошлом конкурсе Зиммерманна.

С тем же самым встретилась и в программе Х. Тоже задаётся (в отдельной программе поиска вширь) командная строка и в ней только одна (!) последовательность для обработки. Делала, конечно, пакетный файл. Хорошо, что я обрабатывала несколько десятков последовательностей, а не тысячи. Представила, какой надо было бы в этом случае делать пакетный файл

Далее, всегда надо стремиться к тому, чтобы формат объекта в выходном файле был таким же, какой он во входном файле, чтобы без проблем можно было брать объекты из выходного файла и снова их обрабатывать, помещая во входной файл.

О выходном файле svb.

1) последовательности должны записываться по порядку n и, кроме того, в порядке возрастания количества шагов;
2) совершенно одинаковые последовательности не должны записываться в файл.

Так сделано в выходном файле у Х (в программе тотальной проверки последовательностей).
Вот, например, маленький фрагмент из выходного файла программы Х:

50:[]:1882: 22,27,23,37,29,38,28,26,31,3,21,30,16,11,44,41,7,24,39,35,12,10,18,19,17,8,20,4,14,33,9,6,13,36,42,5,25,2,34,32,15,40,46,43,50,49,48,1,45,47
50:[]:1882: 38,40,37,39,50,29,28,30,36,33,32,25,22,31,21,19,26,24,23,27,11,16,12,10,9,6,17,5,7,8,3,2,4,14,15,18,20,13,43,35,44,34,42,41,47,1,46,49,48,45
50:[]:1883: 9,10,12,16,11,25,23,24,22,6,17,5,7,8,3,2,4,14,15,18,20,13,19,21,29,28,33,42,35,26,30,36,34,31,27,32,46,44,40,43,39,37,38,41,49,48,50,45,1,47
50:[]:1884: 32,35,31,28,23,25,33,26,21,2,10,6,8,16,3,15,19,24,12,4,7,20,11,14,18,9,22,27,17,13,5,29,30,42,40,39,46,37,41,36,43,44,38,34,49,48,50,45,1,47
50:[]:1887: 10,6,2,5,28,21,9,27,14,7,4,3,18,13,26,31,35,38,37,29,33,42,32,36,41,44,46,34,23,24,30,17,22,20,25,12,8,15,40,1,49,50,48,16,11,19,39,43,45,47

Когда я выбирала из выходного файла программы svb последовательности для базы данных (или для дальнейшей обработки по программе Х), мне пришлось лазить по всему файлу, который был уже огромным. Если бы последовательности записывались по порядку, было бы намного удобнее их выбирать.

[Nataly-Mak]

Здесь итоги конкурса у Зиммерманна.

[dvorkin_sacha]

Как я и предполагал, решение для n = 23 в виде "цифры" 384 оказалось мифом. А для n = 29 "цифра" 689 определяется не одним, а тремя решениями, но самое главное, что Hermann Jurksch "додул" до весьма нетривиального алгоритма (как и для n = 31).

[Nataly-Mak]

Мне стало любопытно, откуда взялся предполагаемый максимум для $n=23$, равный 384. Посмотрела свои рабочие файлы, свои бумаги. Посчитанный мной вначале (по моему результату) предполагаемый максимум был равен 350.
Потом я получила письмо от svb. Вот цитата из него:

Цитата:

Нашел на форуме оценку рекордов аналогичную вашей - вот на текущий момент:

19 220 202 0.92
23 384 325 0.85
29 662 584 0.88
31 748 624 0.83
37 1144 1029 0.90
. . . . . . . . . . . . . . . . .

По этой информации я и исправила все предполагаемые максимумы.
Хорошо, что письмо svb у меня сохранилось.
А то припишут мне этот миф, который мне совсем не принадлежит

Да, кстати, dvorkin_sacha, где же ваш супералгоритм, который вы обещали опубликовать ровно за сутки до окончания конкурса?

-- Вс фев 13, 2011 18:12:28 --

Хочу поблагодарить участника нашей команды, коллегу по магическим квадратам из Италии Стефана Тогнон (ice00) за большую помощь в решении конкурсной задачи. Он выполнял переходы с добавлением 12 и 13 карт, которые у меня выполняются очень долго.

Сегодня Стефано прислал письмо, он где-то там увидел вот такое:

Цитата:

Okay, for those who haven't had enough of TOPSWOPS:

I will award one 19th-century Morgan Silver Dollar (probably
AU condition or thereabouts) to the person who finds the
best permutation of length 10,000.

Please post your scores here (unless Al deems that's
too much) and email me the permutations. I will not
enter (but I may play with the problem---at least to
the point of getting a scorer going!)

In the case that I can neither verify nor disprove the person
who claims the highest score, they will win (that is, I am
not guaranteeing that I can score all entries, and if
the "good" entries are beyond my abilities, the one who
claims the highest number, along with a sequence that I
cannot execute to completion, will win.)

Your entry is due by midnight, Pacific Standard Time on
March 15th (the Ides of March). But for fun post the
scores you get here.

I don't anticipate too many people will enter, so this might
be a really easy silver dollar for someone out there.

Please put TOPSWOPS 10K in the subject line of your
email.

-tom

Как я поняла из перевода, сделанного а Гугле, здесь предлагается найти максимальную последовательность длины 10000. Это для тех, кому было мало topswops у Зиммерманна