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

[Nataly-Mak]

Следующий эксперимент с решением Павловского, игра № 19:

Pavlovsky,"19","19:
i22,k22,k23,p20,i20,k21,h19,j19,i20,h18,i19,o20,o21,o23,k22,p22,i18,n19,h13,j12,j12,j13,
m15,n13,l13,p13,k12,n10,j11,m11,l14,o13,k16,l13,i16,o16,k10,h6,i8,m8,m7,j6,o7,k8,l6,o6,
o7,p7,m5,k4,k4,j4,h3,i3,n3,m2,m2,n4,p1,o2,j1,m0,m1,p2,p20,p18,n17,o14,n15,n13,p14,o14,
p13,p12,o10,p11,m9,p10,o9,p9,m8,p8,p7,o5,p5,p4,p4,p5,p0,p0
"6213"

Это первое наугад выбранное решение.

Исходную позицию выбрала такую:

I22,J22,I21,P20,I20,J21,H19,H18,I20,G18,I19,N20,M23,N22,J23,P22,I18,M19,H13,I12,H13,
I13,K15,L13,K13,M13,J12,M10,H10,M11,L14,N12,J13,J15,I16,N16,K10,F10,H8,L8,K7,J6,M7,
K8,K6,O6,N7,M7,M5,J5,J5,I4,H3,I3,K0,L2,M2,N4,O1,N0,I1,J1,K1,K20,P20,P18,M17,O14

[13 вариантов первого хода]

Запускаю программу полного перебора окончаний, на 12-ой минуте получаю результат 6217:

19:I22,J22,I21,P20,I20,J21,H19,H18,I20,G18,I19,N20,M23,N22,J23,P22,I18,M19,H13,I12,H13,
I13,K15,L13,K13,M13,J12,M10,H10,M11,L14,N12,J13,J15,I16,N16,K10,F10,H8,L8,K7,J6,M7,K8,
K6,O6,N7,M7,M5,J5,J5,I4,H3,I3,K0,L2,M2,N4,O1,N0,I1,J1,K1,K20,P20,P18,M17,O14,L16,M14,
N14,O14,P13,P12,O10,P11,M9,O10,P9,P9,P8,L8,P7,N5,M6,N9,P7,P4,L0,M0

[Nataly-Mak]

Изменена дата начала следующего конкурса, вместо 1 июня конкурс начнётся 29 мая.
Не прозевать

[Nataly-Mak]

Ничего не понимаю!
У меня сегодня 29 мая, а у вас?

Новый конкурс обещано начать 29 мая.
Захожу на главную страницу, вижу там:

Цитата:

0 days, 21 hours, 15 minutes until the next contest begins (29-MAY-2012).

Здесь говорится, что до начала нового конкурса ещё 21 час.
И в то же время говорится, что он начнётся 29 мая.

Кто-нибудь может объяснить, когда конкурс начнётся? Или уже начался, просто я не там смотрю

[Nataly-Mak]

А, ну да... в принципе он может начаться в 21:00 29 мая (у нас в это время будет уже 30 мая).

[Nataly-Mak]

Итак, до начала конкурса осталось 1 час 27 минут.

Господа программисты! На старт! Внимание!..

Любопытно, конечно, увидеть новую задачу, попытаться решить.

[Nataly-Mak]

Ну наконец-то стартовал новый конкурс
http://infinitesearchspace.dyndns.org/monosquares

Товарищи, прошу помочь с переводом.
Сейчас буду пытаться перевести в Гугле и разобраться с описанием задачи.

-- Ср май 30, 2012 06:16:40 --

Спят ещё все в России?

Задачу вроде поняла, даже уже ввела решение для C=2.
Но совсем не понимаю, как пользоваться приложенной программой для ручной игры.

[Nataly-Mak]

Ввела все решения (от C=2 до C=21), решения минимальные.
Пока и эти пойдут
Дальше надо думать.

Хоть раз побывала на первом месте



-- Ср май 30, 2012 07:40:32 --

Как программой ручного составления квадратов пользоваться?
Кто-нибудь же посмотрите, пожалуйста

И первый максимум придумала, для C=2, N=16. Это просто.

[Nataly-Mak]

Ввела в программу решение C=3, N=100, в нём, понятно, полно ошибок.



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

Для C=3 пока сочинила только квадрат 5х5, то есть N=5, что соответствует 25 очкам. А максимум уже 100 очков.

[Pavlovsky]

Щелкаешь мышкой по ячейке.

-- Ср май 30, 2012 09:54:22 --

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

Для C=3 пока сочинила только квадрат 5х5

По ссылкам в описании есть решение 10х10 для С=3. Доказано, что это максимум.

-- Ср май 30, 2012 10:06:31 --

Интересная задача. Судя по статьям проблемы поиска максимума начинаются уже при C=4. Как тогда искать максимум для C=21??

Juha Saukkola нашел решение 17х17 для C=4. В статьях проблема 17х17 для C=4 числится как открытая. Вот так всегда. Кто то начинает с абсолютного нуля, а у кого то есть сильные домашние заготовки.

[Nataly-Mak]

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

Щелкаешь мышкой по ячейке.

Спасибо. Я пыталась, ничего не получается. Может, у меня программа не работает?
Кстати, по-моему, программа и ошибки показывает в большинстве случаев неправильно.
Например, показывает такую ошибку:

A A
A B

Но тут ведь нет ошибки!
А всамделишние ошибки не показывает.

-- Ср май 30, 2012 09:54:22 --

Цитата:

По ссылкам в описании есть решение 10х10 для С=3. Доказано, что это максимум.

Ну, содрать готовое решение - это неинтересно

[Pavlovsky]

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

Кстати, по-моему, программа и ошибки показывает в большинстве случаев неправильно.Например, показывает такую ошибку:Код:A AA BНо тут ведь нет ошибки! А всамделишние ошибки не показывает.

Какой то косяк есть. Остаются данные от предыдущего решения. Надо пощелкать по ячейке, после чего подсчет неправилиных прямоугольников становится верным.

-- Ср май 30, 2012 10:28:17 --

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

Ну, содрать готовое решение - это неинтересно

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

[Nataly-Mak]

Ага, получилось изменять значения в ячейках

О! Ярослав Вроблевский пришёл! И уже на первом месте.

Сочинила для C=3, N=49.

Пойду, однако, завтракать

-- Ср май 30, 2012 09:55:42 --

Что-то не поняла...
ввела сейчас решение, состоящее из 3-х символов - A,B,C, расположенных в квадрате 8х8.
У меня это решение засчиталось для C=4, написалось так: C=4, N=64.

Но это же решение для трёх цветов!

Вот таблица моих результатов:

2 16 1.000000 05-30-2012 @ 07:37:46
3 36 0.360000 05-30-2012 @ 08:43:15
4 64 0.197531 05-30-2012 @ 09:50:27
5 25 0.040000 05-30-2012 @ 06:24:20
6 36 0.042806 05-30-2012 @ 06:26:42
7 49 0.020408 05-30-2012 @ 06:27:57
8 64 0.030246 05-30-2012 @ 06:29:49
9 81 0.202500 05-30-2012 @ 06:31:18
10 100 0.250000 05-30-2012 @ 06:34:40

Для C=3 сочинила решение, когда три символа A,B,C расположены в квадрате 7х7, этого решения почему-то нет, оно ведь тоже для C=3! Или я чего-то не так поняла?

А сейчас ввела решение для тех же трёх символов, расположенных в квадрате 8х8, мне написали, что я улучшила результат с 49 до 64.

-- Ср май 30, 2012 10:12:51 --

Вот решение прямо в программе сделала вручную, оттуда же скопировала:

A,B,B,A,C,A,C,C,
,C,C,A,A,B,B,C,
,A,B,B,A,C,B,C,
,C,A,A,B,C,C,A,
,B,C,A,C,B,A,B,
,B,C,C,A,C,B,A,
,B,C,B,B,A,C,A,
,B,A,C,A,A,A,C

Разве это решение для C=4? Здесь же всего три цвета - A, B, C.
По идее это решение: C=3, N=64.

Ничего не понимаю!

-- Ср май 30, 2012 10:20:13 --

Похоже, у меня программа, которую с конкурса скачала, вообще косая:



Написано, что цветов 3, размер доски 8х8, а решение чёрт знает какое получилось, сикись-накись.

[Nataly-Mak]

Ха!
А на конкурсе это решение приняли как для C=4, N=64.

А-а-а... кажется, понимаю, почему оно так засчитано.
Вот, само собой решение получилось для C=4

[Alexu007]

1. А чё это за конкурс программистов, если программа готовая уже выложена? Что программить то?
2. Что программа делает? Буковки в квадратах очевидно разные цвета, как они раставляются изначально и что куда по каким правилам потом двигать? Почему в первом столбце только одна буква? Что значит X/Y = 6/5?

Пояните для носорогов на примере 3х3 или 4х4.

[Nataly-Mak]

Программа выложена для ручной работы

А программировать надо, чтобы программа сама это всё делала, то есть составляла квадраты из разных цветов.

Пример для N=3, C=2 приведён в описании задачи.
В квадрате 3х3 надо расставить 2 разных символа (соответствующие двум разным цветам) так, чтобы в вершинах ни одного прямоугольника не оказались все 4 одинаковых символа. Вот и вся задача

-- Ср май 30, 2012 11:02:52 --

Таблица максимумов

2 4 16  Wes Sampson @ 05:33:15 on 05-30-2012
3 10 100  Mark Mammel @ 06:40:27 on 05-30-2012
4 18 324  Juha Saukkola @ 09:15:48 on 05-30-2012
5 25 625  Jarek Wroblewski @ 09:04:36 on 05-30-2012
6 29 841  Mark Mammel @ 08:03:48 on 05-30-2012
7 49 2401  Jarek Wroblewski @ 09:05:38 on 05-30-2012
8 46 2116  Mark Mammel @ 09:02:09 on 05-30-2012
9 30 900  Juha Saukkola @ 10:23:50 on 05-30-2012
10 30 900  Juha Saukkola @ 10:22:25 on 05-30-2012
11 121 14641  Jarek Wroblewski @ 09:06:25 on 05-30-2012
12 54 2916  Tom Sirgedas @ 07:43:33 on 05-30-2012
13 169 28561  Jarek Wroblewski @ 09:07:27 on 05-30-2012
14 30 900  Ray Hartung @ 08:18:25 on 05-30-2012
15 30 900  Ray Hartung @ 08:18:47 on 05-30-2012
16 30 900  Ray Hartung @ 08:19:05 on 05-30-2012
17 289 83521  Jarek Wroblewski @ 09:13:49 on 05-30-2012
18 30 900  Ray Hartung @ 08:19:42 on 05-30-2012
19 361 130321  Jarek Wroblewski @ 09:19:13 on 05-30-2012
20 120 14400  Wes Sampson @ 09:02:12 on 05-30-2012
21 120 14400  Wes Sampson @ 08:51:48 on 05-30-2012

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

Созерцая такие рекорды на старте, что-то уже и соревноваться совсем не хочется