Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, SullenMan, Вы писали:

SM>>Кто-нибудь пробовал решить такую задачку
SM>>Интересует не программный код ессесно, а сам метод (алгоритм) решения.

SM>>Ну первое что приходит на ум — взять любой шарик, составить для него список всех возможных путей и последовательно их проверить. Как только шар попал в дырку, брать любой из оставшихся, опять составить список всех путей до его дырки исходя из текущего (а не первоначального) положения и проверять эти пути.

SM>>Затем из первоначального состояния брать другой шарик и делать то же самое.
SM>>Но как мне кажется это не совсем рацианальный метод решения.
SM>>Господа, математики, может что подскажете.



А>Знатоки математики/алгоритмов, я так понимаю эту задачу можно решить путём полного перебора возможных путей для всех шаров. Ибо кратчайший путь от шара к дырке не всегда ведёт к решению задачи. Или я не прав?


Да и ещё, у кого какие иде как игровое поле лучше представлять?

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

ну, как и в шахматах/шашках -- нужно учитывать состояние всех фигур, а не просто по одной в дамки проводить..

А>Да и ещё, у кого какие иде как игровое поле лучше представлять?

игровое поле состоит из 2 частей: неизменная часть -- конфигурация стенок. Можно ее предобработать как-то чтобы оптимизировать. И конфигурация шаров, которые двигаются на каждом ходу -- их как вектор можно представить.

Здравствуйте, dilmah, Вы писали:

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

D>ну, как и в шахматах/шашках -- нужно учитывать состояние всех фигур, а не просто по одной в дамки проводить..

А>>Да и ещё, у кого какие иде как игровое поле лучше представлять?

D>игровое поле состоит из 2 частей: неизменная часть -- конфигурация стенок. Можно ее предобработать как-то чтобы оптимизировать. И конфигурация шаров, которые двигаются на каждом ходу -- их как вектор можно представить.


Шары при разных поворотах доски в разном порядке надо двигать.
Например если два шарика находятся на одной строке и мы наклоняем доску вправо. Получается надо шары двигать начиная с правого. Иначе для того, что слева клетка правее будет занята.
И ещё как лучше связи между клетками реализоывать?
Может стоит посмотреть в сторону поле — это набор объектов Square. А в них уже ссылки на соседние клетки. Этот же объект может содержать стенку и дырку/шарик

А>Шары при разных поворотах доски в разном порядке надо двигать.
А>Например если два шарика находятся на одной строке и мы наклоняем доску вправо. Получается надо шары двигать начиная с правого. Иначе для того, что слева клетка правее будет занята.

безусловно

А>И ещё как лучше связи между клетками реализоывать?
А>Может стоит посмотреть в сторону поле — это набор объектов Square. А в них уже ссылки на соседние клетки. Этот же объект может содержать стенку и дырку/шарик

имхо, это ненужное усложнение.
У меня был просто 3-х мерный массив pos[i][j][k] который содержал позицию в которую попадает шарик, изначально находящийся в точке (i,j) если его "до упора" до стенки двигать в направлении k.
Для того чтобы сдвинуть шарик, я смотрел в этот массив, а потом, если необходимо проводил коррекцию -- т.е. если шарик попадал на место занятое другим шариком, то откатывал назад.

Здравствуйте, Аноним, Вы писали:

А>Да и ещё, у кого какие идеи как игровое поле лучше представлять?

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

Здравствуйте, Аноним, Вы писали:

Прикольно Не так давно сдавал им же эту задачу. Решал почти 1-в-1 как здесь описано
(до этого данную ветку форума не посещал).

Здравствуйте, saf_e, Вы писали:

А как вы распараллеливали поиск решения?

Здравствуйте, canus, Вы писали:

C>Здравствуйте, saf_e, Вы писали:

C>А как вы распараллеливали поиск решения?

А че там думать-то Каждый шаг решения может выполнятся независимо...

C>>А как вы распараллеливали поиск решения?

_>А че там думать-то Каждый шаг решения может выполнятся независимо...

ну как бы там желательно иметь глобальное хранилище, в котором хранятся состояния шаров в которых уже побывали -- то есть нужно минимизировать lock contention на этом хранилище.

Здравствуйте, canus, Вы писали:

C>Здравствуйте, saf_e, Вы писали:

C>А как вы распараллеливали поиск решения?
Я так понимаю прочитав файл с описанием поля, нодо просто сделать копии этого поля для каждого шарика и отправить эти состояния в отдельные потоки.

C>>А как вы распараллеливали поиск решения?
А>Я так понимаю прочитав файл с описанием поля, нодо просто сделать копии этого поля для каждого шарика и отправить эти состояния в отдельные потоки.

Это уже будет исключительно зависеть от вашей реализации

>ну как бы там желательно иметь глобальное хранилище, в котором хранятся состояния шаров в которых уже >побывали -- то есть нужно минимизировать lock contention на этом хранилище.

Тут уже возможны варианты.

1. Lock-free контейнер
2. Обеспечить синхронный доступ к общему хранилищу (Mutex)
3. Хранить локальную копию, а доступ в хрнилище делать в диспетчер-потоке (более худший вариант)
4. Еще альтернативы?

_>2. Обеспечить синхронный доступ к общему хранилищу (Mutex)

к этому хранилищу легко применить lock striping (разбить его на части, и каждое состояние хранить в части хранилища, вычисляемой по какому-то хэшу, зависящему от состояния. И иметь не глобальный mutex, а по одному на каждую часть.

Здравствуйте, dilmah, Вы писали:


_>>2. Обеспечить синхронный доступ к общему хранилищу (Mutex)

D>к этому хранилищу легко применить lock striping (разбить его на части, и каждое состояние хранить в части хранилища, вычисляемой по какому-то хэшу, зависящему от состояния. И иметь не глобальный mutex, а по одному на каждую часть.

Это если у вас есть "час та надхнення". Писать собственный хеш контейнер.

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

Опят таки, никто не мешает, пока одни потоки ждут доступа в хеш -- остальным продолжать расчеты

Здравствуйте, saf_e, Вы писали:

_>Здравствуйте, dilmah, Вы писали:


_>>>2. Обеспечить синхронный доступ к общему хранилищу (Mutex)

D>>к этому хранилищу легко применить lock striping (разбить его на части, и каждое состояние хранить в части хранилища, вычисляемой по какому-то хэшу, зависящему от состояния. И иметь не глобальный mutex, а по одному на каждую часть.

Хотя, конечно, если сделать размер фиксированный, то можно обойтись без внешнего лока... И таки да, потенциально выигрыш возможен. Его величина на практике будет зависеть от многих критериев -- но для собеседующие, очевидно, будут довольно самим фактом наличия подобной оптимизации

Здравствуйте, SullenMan, Вы писали:

SM>Кто-нибудь пробовал решить такую задачку
SM>Интересует не программный код ессесно, а сам метод (алгоритм) решения.

SM>Ну первое что приходит на ум — взять любой шарик, составить для него список всех возможных путей и последовательно их проверить. Как только шар попал в дырку, брать любой из оставшихся, опять составить список всех путей до его дырки исходя из текущего (а не первоначального) положения и проверять эти пути.

SM>Затем из первоначального состояния брать другой шарик и делать то же самое.
SM>Но как мне кажется это не совсем рацианальный метод решения.
SM>Господа, математики, может что подскажете.


Тоже решил попробовать решить данную задачку.

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

И второй по алгоритму.
Я так понял в задачке придётся перебрать все возможные ходы.
У меня алгоритм примерно такой.
1. Создаю поток для каждого шарика. В каждый поток передаю состояние поля (для первого шага ессесно начальное)
2. Внутри потока пытаюсь загнать шар по самому короткому пути.
3. загнав шарик, для оставшихся опять создаю поток и в него передаю уже текущее состояние игрового поля и последовательность ходов которая дополняется в каждом потоке.
4. после того как не останется ни одного шарика ни в одном из потоков сравниваю последовательности ходов полученные в каждом из потоков и нахожу самую короткую

Как-то так. Или не так?!

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, SullenMan, Вы писали:

SM>>Кто-нибудь пробовал решить такую задачку
SM>>Интересует не программный код ессесно, а сам метод (алгоритм) решения.

SM>>Ну первое что приходит на ум — взять любой шарик, составить для него список всех возможных путей и последовательно их проверить. Как только шар попал в дырку, брать любой из оставшихся, опять составить список всех путей до его дырки исходя из текущего (а не первоначального) положения и проверять эти пути.

SM>>Затем из первоначального состояния брать другой шарик и делать то же самое.
SM>>Но как мне кажется это не совсем рацианальный метод решения.
SM>>Господа, математики, может что подскажете.


А>Тоже решил попробовать решить данную задачку.

А>Есть несколько вопросов
А>Первый по правилам. Если в лунку закатили шарик с нужным номером, другие шарики могут уже кататься по этой дырке? Т.е. после закатывания шарика в дырку можно считать что этой дырки уже нет?

А>И второй по алгоритму.
А>Я так понял в задачке придётся перебрать все возможные ходы.
А>У меня алгоритм примерно такой.
А>1. Создаю поток для каждого шарика. В каждый поток передаю состояние поля (для первого шага ессесно начальное)
А>2. Внутри потока пытаюсь загнать шар по самому короткому пути.
А>3. загнав шарик, для оставшихся опять создаю поток и в него передаю уже текущее состояние игрового поля и последовательность ходов которая дополняется в каждом потоке.
А>4. после того как не останется ни одного шарика ни в одном из потоков сравниваю последовательности ходов полученные в каждом из потоков и нахожу самую короткую

А>Как-то так. Или не так?!

По первому вопросу вам все станет понятно из тест-кейсов

По второму, можно попробовать, но ИМХО, тупиковый путь не учитывающий взаимодейтвия шариков

А>Первый по правилам. Если в лунку закатили шарик с нужным номером, другие шарики могут уже кататься по этой дырке? Т.е. после закатывания шарика в дырку можно считать что этой дырки уже нет?

да

А>И второй по алгоритму.
А>Я так понял в задачке придётся перебрать все возможные ходы.
А>У меня алгоритм примерно такой.
А>1. Создаю поток для каждого шарика. В каждый поток передаю состояние поля (для первого шага ессесно начальное)
А>2. Внутри потока пытаюсь загнать шар по самому короткому пути.
А>3. загнав шарик, для оставшихся опять создаю поток и в него передаю уже текущее состояние игрового поля и последовательность ходов которая дополняется в каждом потоке.
А>4. после того как не останется ни одного шарика ни в одном из потоков сравниваю последовательности ходов полученные в каждом из потоков и нахожу самую короткую

очень сомнительно выглядит. присоединяюсь к мнению saf_e

D>собеседование в CQG detected

Могу добавить, что CQG недавно cменила тестовое задание, так что задачка теперь представляет только академический интерес.

Здравствуйте, Lexey, Вы писали:

D>>собеседование в CQG detected

L>Могу добавить, что CQG недавно cменила тестовое задание, так что задачка теперь представляет только академический интерес.

Не прошло и пол-года

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, SullenMan, Вы писали:

SM>>Т.е. я так понимаю сначала надо построить дерево.
SM>>Может подскажете как это лучше сделать?

Б>В императивных языках лучше на списках делать, а дерево в уме представлять.

Б>Создаем два списка — просмотренные состояния и НЕ просмотренные. Берем по очереди состояния из списка непросмотренных.
Б>Если является ответом — возвращаем ответ. Если нет, то на основе него генерируем новые состояния. Добавляем их в список не просмотренных исключая те, которые ранее были просмотрены (т.е. содержатся в списке просмотренных).

Б>Вот то же самое, но более формально:

Б>

Б>список_НЕпросмотренных := [начальное_состояние] // список из одного элемента
Б>список_просмотренных := []                      // пустой список

Б>пока в список_НЕпросмотренных есть элементы
Б>  текущее_состояние := извлечь первый элемент из список_НЕпросмотренных
Б>  если текущее_состояние удовлетворяет условию задачи, то вернуть ответ
Б>  новые_состояния := сгенерировать новые состояния из текущее_состояние
Б>  для каждого состояния из новые_состояния
Б>    если оно отсутствует в список_просмотренных, то добавить его в конец список_НЕпросмотренных
Б>  конец_для
Б>конец_пока
Б>вернуть ответ "решения нет"
Б>

А откуда начинать путь? В смысле какую клетку/шарик считать первой?!