Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 11 12 13 14 15 16 [17] 18 19 20   вперед  Ctrl
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Не вызывает вопросов почему при доле удачи на 46 порядков меньше, не удаётся промахнуться? С отладкой ГУИ, обычн наоборот, сколько его ни тестируй, юзер в первый же день наткнётся на фигню.
29 сен 17, 13:55    [20831708]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Интересно взглянуть с т.зр. теории кодирования. С какого момента нач-ая позиция становится префиксным кодом? Подразумеваю, что кодируем 2 значения, т.е. как бы имеем 2 вида хэшей - прав и неправ. Мож надо грамотней сформулировать ...
29 сен 17, 14:08    [20831753]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98
Ошибки точно нет? другие подтверждают подобное?


Ошибки нет. Четверть поставленных ферзей еще оставляет достаточно степеней свободы для поиска завершения. Примерно при 15000 ферзей завершения уже находятся не с первой попытки, а затем и вовсе перестают находиться.

Кто другие? Скомпилируй и стань другим )
29 сен 17, 14:14    [20831778]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Aleksandr Sharahov
Скомпилируй и стань другим )
кто доказал, что исходники без ош?

Но я другое хотел сказать, может твоя статистика про 25% в этом русле.
Давным-давно возникала т.н. "алгоритмическая проблема разрешимости для полугрупп с конечным числом образующих" (не знаю, возможно, что на сегодня она породила кучу детализированных подпроблем )

У нас же группа, т.е. частный случай ПГ.
Так вот был результат, вроде такого (за диапазоны не ручаюсь), что если образующие налезают друг на друга до 1/4 своей длины, то проблема разрешима. Если от 1/3 - нет. В промежутке - как сложится.
ПГ представляются в виде слов из алфавита + определяющие комбинации слов наподобие таблицы умножения. Более точно формализовать наш случай сейчас не смогу. Просто вывод сходный: чем больше начальных данных, тем надёжней классифицировать, если доля неоднозначностей не очень большая.
29 сен 17, 14:38    [20831855]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98
кто доказал, что исходники без ош?


Совсем не требуется, чтобы исходники были без ошибок )

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

Вещи кажутся невероятными до тех пор, пока к ним не привыкли. Но это проходит.
29 сен 17, 14:47    [20831881]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Если проверялка в другой проге, то мой вопрос доказательства был о ней. Правдободобность не означает достоверности. А для 10 тыс глазками проверять - стал быть д.б. прога, хоть бы и в эксэл, я так думаю.
29 сен 17, 15:24    [20832010]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98
Если проверялка в другой проге, то мой вопрос доказательства был о ней. Правдободобность не означает достоверности. А для 10 тыс глазками проверять - стал быть д.б. прога, хоть бы и в эксэл, я так думаю.


Не надо проверять ни другой прогой, ни глазами.
Достаточно вызвать простую функцию вроде этой:
function IsSolutionValid: boolean;
var
  i, r, c: integer;
begin;
  FillChar(CountCol[0], BoardSize, 0);
  FillChar(CountDiagP[0], 2*BoardSize-1, 0);
  FillChar(CountDiagM[1-BoardSize], 2*BoardSize-1, 0);
  for i:=0 to BoardSize-1 do with QueenColRow[i] do begin;
    c:=QueenCol;
    r:=QueenRow;
    if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;
    if CountCol[c]<>0 then exit;
    CountCol[c]:=1;
    if CountDiagP[c+r]<>0 then exit;
    CountDiagP[c+r]:=1;
    if CountDiagM[c-r]<>0 then exit;
    CountDiagM[c-r]:=1;
    end;
  Result:=true;
  end;
29 сен 17, 16:39    [20832260]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
Aleksandr Sharahov, потерял строчку в начале функции
function IsSolutionValid: boolean;
var
  i, r, c: integer;
begin;
  Result:=false;
  FillChar(CountCol[0], BoardSize, 0);
  FillChar(CountDiagP[0], 2*BoardSize-1, 0);
  FillChar(CountDiagM[1-BoardSize], 2*BoardSize-1, 0);
  for i:=0 to BoardSize-1 do with QueenColRow[i] do begin;
    c:=QueenCol;
    r:=QueenRow;
    if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;
    if CountCol[c]<>0 then exit;
    CountCol[c]:=1;
    if CountDiagP[c+r]<>0 then exit;
    CountDiagP[c+r]:=1;
    if CountDiagM[c-r]<>0 then exit;
    CountDiagM[c-r]:=1;
    end;
  Result:=true;
  end;
29 сен 17, 16:42    [20832267]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
См. мой предыдущий пост.

З.Ы. Ну и довольно, ведь так в лом было признаться, мол, питаем доверие к процедуре.
Типа см. сам и тоже питай доверие. Особенно, учитывая загадочные QueenColRow и CountDiagM ...

Если есть спортивный интерес, то ...
для N=9 самыми популярными разложениями оказались вида Card(4+4+1)=13 / 42 и Card(8+1)=16 / 42. Даже не удивлюсь, если заполнять ими (или пятёрками) до 60% , что всё равно будут ответы.
для 4+5 =1 /42, наверное доска маленькая, даже удивился
1+3+5 =9 / 42
9+0 =6 / 42
29 сен 17, 17:16    [20832346]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98
См. мой предыдущий пост.
З.Ы. Ну и довольно, ведь так в лом было признаться, мол, питаем доверие к процедуре.
Типа см. сам и тоже питай доверие. Особенно, учитывая загадочные QueenColRow и CountDiagM ...


Загадочный QueenColRow - массив положений ферзей,
а CountCol, CountDiagM, CountDiagM, - счетчики ферзей в столбцах и на диагоналях.

Да, я "питаю доверие" к оператору сложения, а ты?
29 сен 17, 17:29    [20832367]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Tactical Nuclear Penguin
Member

Откуда: холодно тут
Сообщений: 2422
Aleksandr Sharahov
Aleksandr Sharahov, потерял строчку в начале функции
function IsSolutionValid: boolean;
var
  i, r, c: integer;
begin;
  Result:=false;
  FillChar(CountCol[0], BoardSize, 0);
  FillChar(CountDiagP[0], 2*BoardSize-1, 0);
  FillChar(CountDiagM[1-BoardSize], 2*BoardSize-1, 0);
  for i:=0 to BoardSize-1 do with QueenColRow[i] do begin;
    c:=QueenCol;
    r:=QueenRow;
    if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;
    if CountCol[c]<>0 then exit;
    CountCol[c]:=1;
    if CountDiagP[c+r]<>0 then exit;
    CountDiagP[c+r]:=1;
    if CountDiagM[c-r]<>0 then exit;
    CountDiagM[c-r]:=1;
    end;
  Result:=true;
  end;


простите, а зачем писать так:
begin;
30 сен 17, 05:30    [20833015]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
Tactical Nuclear Penguin
Aleksandr Sharahov
Aleksandr Sharahov, потерял строчку в начале функции
function IsSolutionValid: boolean;
var
  i, r, c: integer;
begin;
  Result:=false;
  FillChar(CountCol[0], BoardSize, 0);
  FillChar(CountDiagP[0], 2*BoardSize-1, 0);
  FillChar(CountDiagM[1-BoardSize], 2*BoardSize-1, 0);
  for i:=0 to BoardSize-1 do with QueenColRow[i] do begin;
    c:=QueenCol;
    r:=QueenRow;
    if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;
    if CountCol[c]<>0 then exit;
    CountCol[c]:=1;
    if CountDiagP[c+r]<>0 then exit;
    CountDiagP[c+r]:=1;
    if CountDiagM[c-r]<>0 then exit;
    CountDiagM[c-r]:=1;
    end;
  Result:=true;
  end;


простите, а зачем писать так:
begin;


простите, а почему вас не смущает, что написано так:
  Result:=true;
  end;
30 сен 17, 09:42    [20833093]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Tactical Nuclear Penguin
а зачем писать так:
begin;
а в запросах я часто пишу так
where  2=2
   and .... 
и зачем так делаю ...

автор
Да, я "питаю доверие" к оператору сложения, а ты?
остаётся питать доверие к "дельфийскому" оракулу.
По-видимому, ВБУ нас просто развели. Получается, что у каждого решения есть свой "родственник" - не решение. Ясно, что при N-1 уже не найдётся, а какая-нить прапрабабушка - да.

Вместо, чтоб искать завершение расстановок, надо искать начальные положения, к-рые невозможно завершить. А точнее, найти минимальное такое начальное положение, к-рое притворяется правильным. Начиная с 10к. Вот, к примеру, задачка в отдельную тему на 2,6 млн, баки клянчить у того же клейна.
2 окт 17, 12:10    [20835949]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2412
exp98
Вместо, чтоб искать завершение расстановок, надо искать начальные положения, к-рые невозможно завершить. А точнее, найти минимальное такое начальное положение, к-рое притворяется правильным. Начиная с 10к. Вот, к примеру, задачка в отдельную тему на 2,6 млн, баки клянчить у того же клейна.
откуда такой вывод? их по идее куда больше
2 окт 17, 13:23    [20836190]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Не знаю, это фантазия, во всяк Дмитрий затрудняется получить такую позу. Будет интересно узнать, что это не так.
А у меня, не вдаваясь в детали, первой реакцие было как раз, чо этого не мб. А теперь думаю наоборот, что возможно по причине редкости у каждой законченной позы и найдётся не очень близкий предок - их же много больше. Правда правильные позы не равномерн распределены, в каких-то разложениях они гуще. Тем интереснее.
Основываюсь только на словах в теме.
2 окт 17, 13:53    [20836313]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
У Александра Ш, не дмитрия, то есть,
2 окт 17, 13:54    [20836317]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
exp98
Вместо, чтоб искать завершение расстановок, надо искать начальные положения, к-рые невозможно завершить.


Вот, например, если взять решение для доски 5х5 и поместить в центр доски NxN (N-нечетное), то его можно будет завершить только при N>=25.

Или, например, решение для доски 6х6, помещенное в центр доски NxN (N-четное), невозможно завершить при N<=28 (при N>28 не проверял).

И что это дает?
2 окт 17, 23:48    [20837680]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
Aleksandr Sharahov
Или, например, решение для доски 6х6, помещенное в центр доски NxN (N-четное), невозможно завершить при N<=28 (при N>28 не проверял).


Проверил: при N=30 завершения есть.
3 окт 17, 00:03    [20837692]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
exp98
Member

Откуда:
Сообщений: 1170
Aleksandr Sharahov
И что это дает?
отдельную тему на 2,6 млн, других задумок не было/
3 окт 17, 10:53    [20838259]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35705
Продолжаю свою мысль о permutations с пропусками. Нарисую поясняющую картинку.
6 окт 17, 21:23    [20849621]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35705
Как-то так. Главное - как оптимизировать копирование массивов в рекурсию.

К сообщению приложен файл. Размер - 40Kb
6 окт 17, 23:03    [20849932]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35705
У меня не хватило терпенья нарисовать все 24 листа. Но 2 решения я обозначил.
Здесь выполняются условия оптимизации. Имеют места "отсечения" (по типу альфа-бет) заведомо тупиковых веток.
И процедура проверки "ферзей" под боем не зависит линейно от N=1000. Чему равна
средняя глубина дерева - можно прикинуть экспериментально.

Для 1000-й доски возможно не хватит стека чтобы сохранять состояние этого автомата
поэтому придется использовать Heap. В наихудшем случае это будет прогрессия 1000,999,998 e.t.c.
Тоесть приблизительно - полу-площадь шахматной доски. 500 тыс элементов. Для short
типа данных - это (2 байта на элемент) будет примерно 500 000 * 2 = 1 000 000 байт
или примерно 1 мегабайт стека массивов.

Алтернативный вариант - модифицировать вектор ферзей при каждом погружении
в рекурсию а при выходе наверх - восстанавливать. И возможно это не вектор а list.
Или версионный list.
7 окт 17, 14:29    [20850797]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
mayton,

неясно, это поиск с возвратом или что-то другое?
7 окт 17, 18:59    [20851156]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35705
Определённо это поиск. И возврат тоже есть. Но это не самые главные вопросы.
7 окт 17, 21:09    [20851347]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
если это выглядит как утка ... ))
7 окт 17, 21:22    [20851369]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 11 12 13 14 15 16 [17] 18 19 20   вперед  Ctrl
Все форумы / Программирование Ответить