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

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

D>собеседование в CQG detected
Хотел я упомянуть про CQG, но не стал. Видимо зря.
ДА! ДА! ДА!
В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую.
Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.

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

SM>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.

Давайте,конечно

PS Я в CQG не собираюсь

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

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


SM>>>В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую.
SM>>>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.

D>>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

SM>А поподробнее идейку можно расписать?

Обычный поиск в ширину: http://en.wikipedia.org/wiki/Breadth_first_search
В качестве вершин графа — состояние игры. Ребра существуют, если возможно из одного состояния получить другое за один наклон доски. В данной игре за состояние можно взять совокупность координат шариков. Их в свою очередь можно представить в виде целого числа (шариков максимум 8, каждая координата — 2 бита). Чтобы определить, посещали ли мы уже текущее состояние, можно завести хэш-таблицу. На самом деле различных состояний будет на порядки меньше 2^32 из-за особенностей игрового поля и правил игры, поэтому должно шустро работать.

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

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


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

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

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

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

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

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

SM>В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую.
SM>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.

ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

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

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

SM>>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.

B>Давайте,конечно

B>PS Я в CQG не собираюсь

как и обещал, вот второе задание

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


SM>>В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую.
SM>>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.

D>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

А поподробнее идейку можно расписать?

SM>А поподробнее идейку можно расписать?

http://en.wikipedia.org/wiki/State_space_search

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

_DA>В данной игре за состояние можно взять совокупность координат шариков.
Нельзя.
Нужно еще дырки учитывать. Ибо при попадании шарика в дырку дырку и шарик нужно удалять.

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

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

_DA>>В данной игре за состояние можно взять совокупность координат шариков.
WH>Нельзя.
WH>Нужно еще дырки учитывать. Ибо при попадании шарика в дырку дырку и шарик нужно удалять.

Я нашёл ещё вот такой алгоритм здесь
Что думаете?

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

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

_DA>>В данной игре за состояние можно взять совокупность координат шариков.
WH>Нельзя.
WH>Нужно еще дырки учитывать. Ибо при попадании шарика в дырку дырку и шарик нужно удалять.

А в чем проблема? Если у шарика такая же координата, что и у дырки, то считаем, что шарик в дырке. Координаты у дырок константные, так что никаких проблем с этим нет.

_DA>А в чем проблема? Если у шарика такая же координата, что и у дырки, то считаем, что шарик в дырке. Координаты у дырок константные, так что никаких проблем с этим нет.

не, в одной позиции могут быть 2 шарика -- один в дырке, другой сверху. Нужна еще информация кто где.

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


_DA>>А в чем проблема? Если у шарика такая же координата, что и у дырки, то считаем, что шарик в дырке. Координаты у дырок константные, так что никаких проблем с этим нет.

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

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

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


SM>>В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую.
SM>>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.

D>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

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

_DA>>>А в чем проблема? Если у шарика такая же координата, что и у дырки, то считаем, что шарик в дырке. Координаты у дырок константные, так что никаких проблем с этим нет.

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

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

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

D>>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

SM>Т.е. я так понимаю сначала надо построить дерево.

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

Во вторых, граф сразу целиком конечно не нужно строить. Нужно двигаться волной и динамически строить новые состояния в которые можно попадаешь.

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

D>>>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

SM>>Т.е. я так понимаю сначала надо построить дерево.

D>там не дерево. Там граф с циклами. Ты же можешь совершить цепочку ходов и прийти в ту же позицию в которой уже был.
Ну я так понимаю что как раз в туже позицию ходть не надо. Иначе можно зацмклиться. Разве нет?

D>>там не дерево. Там граф с циклами. Ты же можешь совершить цепочку ходов и прийти в ту же позицию в которой уже был.
SM>Ну я так понимаю что как раз в туже позицию ходть не надо. Иначе можно зацмклиться. Разве нет?

да. Я имел в виду, что сам граф состояний это не дерево. Ты идешь по нему волной как в breadth-first search, ты не ходишь на позиции в которых уже был.

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

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

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

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

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

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

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

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

D>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

Ужас! Неужели ожидаемое решение — полный перебор?

Если бы я был царь, то я бы сделал поиск с приоритетами.

Состояние = карта + пробег (количество итераций от исходной карты).
Карте соответствует дальность — нижняя оценка расстояния до финальной карты, равная сумме кратчайших путей всех шариков до своих лунок, без учёта коллизий.
Состоянию соответсвует вес = пробег + дальность.

Заведём реестр карта->пробег встреченных карт и приоритетную очередь вес->состояние.

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

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

К>Ужас! Неужели ожидаемое решение — полный перебор?

Оно не такое уж и плохое. Для такой карты количество вариантов совсем маленькое.

К>Состояние = карта + пробег (количество итераций от исходной карты).
К>Карте соответствует дальность — нижняя оценка расстояния до финальной карты, равная сумме кратчайших путей всех шариков до своих лунок, без учёта коллизий.

Без учета коллизий — это значит мы не учитываем другие шарики?

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

А,B — шарики
1,2 — лунки для A,B

C учетом других шариков - наклон влево, затем вниз
. B A .
. . . .
. 1 . .
2 . . .

Без учета других шариков - пути нет.
. . A .
. . . .
. 1 . .
. . . .

Или под коллизиями понималось что-то другое?

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

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

D>>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

К>Ужас! Неужели ожидаемое решение — полный перебор?

Нет, полный перебор — это brute force. А здесь bfs.

К>Если бы я был царь, то я бы сделал поиск с приоритетами.

А я бы сделал так, как описал выше, и работать будет быстро.

К>Ужас! Неужели ожидаемое решение — полный перебор?

К>Если бы я был царь, то я бы сделал поиск с приоритетами.

К>Состояние = карта + пробег (количество итераций от исходной карты).
К>Карте соответствует дальность — нижняя оценка расстояния до финальной карты, равная сумме кратчайших путей всех шариков до своих лунок, без учёта коллизий.

не ясны детали.
Нужно найти минимальное расстояние, а не "приблизительно" минимальное расстояние.
То есть надо быть уверенным что более короткого нет.
Я не совсем понял деталей как ты будешь давать минимальную оценку расстояния.
Во первых, за один ход шарики катятся "до упора".
Поэтому тривиальная нижняя оценка обычна равна 2, 3 или 4.
По моему учет этой оценки будет давать околонулевой выигрыш при значительно усложняющемся коде.

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

D>не ясны детали.
D>Нужно найти минимальное расстояние, а не "приблизительно" минимальное расстояние.

Приблизительно минимальное (оценка снизу) нужно для упорядочивания очереди.
Ибо, фронт разрастается экспоненциально, и надо сперва проверять наиболее симпатичные состояния.

D>Во первых, за один ход шарики катятся "до упора".

Упс! Этот момент я как-то упустил. Почему-то решил, что шарики ходят, как в игре lines.
Тогда буду думать по-новой

К>Ибо, фронт разрастается экспоненциально

можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

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

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

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

К>>Ибо, фронт разрастается экспоненциально

D>можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

D>Первая проблема -- обратный ход дает не одно состояние а несколько, а иногда и очень много.. Но обычно их не очень много и их можно быстро найти, если аккуратно реализовать это. Но еще проблема в том что эффективно реализовать "обратный ход" очень трудоемко.

D>P.S.
D>Еще полезно использовать свойство идемпотентности хода -- сделать ход 2 раза в одну сторону это все равно что сделать ход 1 раз. Из этого следует простой но полезный факт что если состояние принадлежит цепочке решения, то найдется такой ход для которого это состояние явлется неподвижной точкой.

Тоже думал об этом, но обратный ход дает очень много вариантов, которые сложно просчитывать. Хотя, может оказаться, существенно меньше, чем быстро разрастающие варианты прямых ходов. Хотя бы тот пример с тремя лунками. На последнем ходу мог закатиться один шар, тогда он мог закатиться из 7 положений (без стенок, со стенками может быть меньше). Можно ограничиться, правда, не 7-ю а меньшим числом вариантов, т.к. шар должен касаться стенки или другого шара на каждом шаге (будет, правда, усложнение алгоритма просчета). На последнем ходу могло закатиться 2 шара (3 варианта выбора какие именно два). Из скольки положений -- они катились с одной стороны, например, сверху, каждый из ui вариантов. Т.е. будет что-то u1*u2+r1*r2+d1*d2+l1*l2 вариантов. Но тут надо еще учесть, что лунки могут стоять рядом. Для трех шаров еще куча вариантов. Для каждого варианта еще один ход назад даст еще тучу вариантов. Короче, если и просчитывать так, то надо следующим образом: просчитать один ход назад, посмотреть, сколько вариантов получилось, и считать сначала, пока не наберется такое же число вариантов. Далее просчитать еще на один ход назад, снова считать вперед, пока не компенсирует, и т.д.

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

D>можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

D>Первая проблема -- обратный ход дает не одно состояние а несколько, а иногда и очень много.. Но обычно их не очень много и их можно быстро найти, если аккуратно реализовать это.

А как проверить, что задача не решаема?

D>>можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

D>>Первая проблема -- обратный ход дает не одно состояние а несколько, а иногда и очень много.. Но обычно их не очень много и их можно быстро найти, если аккуратно реализовать это.

AJD>А как проверить, что задача не решаема?

дождаться пока фронт выдохнется

Выделить один тред для "обратного" фронта может быть полезно и с точки зрения определения нерешимости задачи. Можно придумать много примеров когда человеку с пары взглядов на доску ясно что задача решения не имеет (например дырка просто заперта стенками), а при этом "прямой" фронт займет тысячу лет. В этом случае тред занимающийся "обратным" фронтом поможет.

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

К>>Ибо, фронт разрастается экспоненциально

D>можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

А можно вопрос.. Какую именно экспоненту мы пробуем половинить?

D>Первая проблема -- обратный ход дает не одно состояние а несколько, а иногда и очень много.. Но обычно их не очень много и их можно быстро найти, если аккуратно реализовать это. Но еще проблема в том что эффективно реализовать "обратный ход" очень трудоемко.

D>P.S.
D>Еще полезно использовать свойство идемпотентности хода -- сделать ход 2 раза в одну сторону это все равно что сделать ход 1 раз. Из этого следует простой но полезный факт что если состояние принадлежит цепочке решения, то найдется такой ход для которого это состояние явлется неподвижной точкой.

_DA>А можно вопрос.. Какую именно экспоненту мы пробуем половинить?

хороший вопрос. Ту экспоненту которая растет с каждым ходом из-за 3 вариантов ходов.
Конечно она гасится тем что состояния повторяются и все ограничено общим кол-вом состояний. Поэтому если общее кол-во состояний не велико, то как бы экспонента уже погашена.

Но в формулировке задачи которую я получал от CQG в свое время размер поля был ограничен 40x40, с неограниченным кол-вом стенок и дырок.

Может подскажите, как запоминать положение шариков на доске, чтобы хранить их(положения) для всех состояний пройденного пути у дерева? Каждый узел нижнего уровня хранить все состояния доски пройденного пути от корня. Нужно для того, чтобы избежать зацикливания. Запоминать координаты всех шариков на доске и хранить их в векторе накладно, т.к. путь до решения может быть довольно долгим. Замечу, что именно координаты шариков не нужны, нужен некий "слепок", чтобы в каждом состоянии можно было посмотреть, а не было ли такого же состояния ранее при спуске. Первое, что пришло на ум, это hash функция. Но как её подобрать, какая вероятность колизий при спуске через 1600 вершин? Пока на доске 1600 клеток, в худшем случае шарик пройдет все 1600 клеток до цели. Но шариков может быть и больше.

C>Может подскажите, как запоминать положение шариков на доске, чтобы хранить их(положения) для всех состояний пройденного пути у дерева? Каждый узел нижнего уровня хранить все состояния доски пройденного пути от корня. Нужно для того, чтобы избежать зацикливания. Запоминать координаты всех шариков на доске и хранить их в векторе накладно, т.к. путь до решения может быть довольно долгим. Замечу, что именно координаты шариков не нужны, нужен некий "слепок", чтобы в каждом состоянии можно было посмотреть, а не было ли такого же состояния ранее при спуске. Первое, что пришло на ум, это hash функция. Но как её подобрать, какая вероятность колизий при спуске через 1600 вершин? Пока на доске 1600 клеток, в худшем случае шарик пройдет все 1600 клеток до цели. Но шариков может быть и больше.

Не понимаю зачем хранить все состояния пройденного пути до корня.
В каждом узле нужно хранить указатель на предыдущее состояние (чтобы когда/если прийдешь в конечное состояние можно было отследить путь которым пришел).
Кроме того нужно вести один глобальный std::set содержащий все посещенные состояния (чтобы не зациклиться).

(С учетом того что нужно параллелить алгоритм, то нужно сделать lock striping этого множества).

Здравствуйте, dilmah, Вы писали:
D>Не понимаю зачем хранить все состояния пройденного пути до корня.

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

D>В каждом узле нужно хранить указатель на предыдущее состояние (чтобы когда/если прийдешь в конечное состояние можно было отследить путь которым пришел).
В самом состоянии можно хранить пройденный путь, как пример: NWEW... . При обходе в ширину нет необходимости хранить уже пройденные состояния, их можно просто уничтожать. Т.е. нет необходимости хранить дерево целиком в памяти. Используется принцип FIFO. Помещаем вершину в очередь, забераем её оттуда, считаем следующие состояния, помещаем их в эту очередь, а саму вершину уничтожаем, в каждом состоянии запоминаем, что мы прошли через вершину, и т.д.

D>Кроме того нужно вести один глобальный std::set содержащий все посещенные состояния (чтобы не зациклиться).
Я хотел немного другого: в каждом состоянии хранит в vector<что-то> по чему я мог узнать были ли у меня шарики в такой расстановке уже или нет.
Но с глобальным set тоже интересно: Проходя, допустим по правой ветке 10 уровня в глубину и встретив состояние уже находящееся в set можно остановить дальнейший обход этой ветки и считать этот путь не верным, даже если это состояние сформировалось вообще в другой части дерева.

D>(С учетом того что нужно параллелить алгоритм, то нужно сделать lock striping этого множества).

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

От безисходности готов для доски 40*40 просто представить все положения шариков единичными битами, а пустые клетки 0. Собрать все это в int-ы и поместить в структуру, но размер структуры получится 200 б. Теряюсь, не знаю как лудше сделать

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

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

Есть тип marbles_coord_t -- это пара char -- хранит координату.

Есть тип marbles_state_t -- это сути дела std::vector< marbles_coord_t >, в котором положения всех шариков.

И наконец волна -- состоит из:

std::map< marbles_state_t, const marbles_state_t * > some_map;
std::vector< const marbles_state_t * > some_vec[2];

Допустим начальное состояние это marbles_state_t S;
В some_map изначально кладем пару S->NULL. Второй компонент пары -- это указатель на предшествующее состояние, для начального состояния это 0.

some_vec[0] сперва содержит указатель на S (который лежит в some_map, а как известно добавления в some_map не инвалидируют ни итераторы, ни указатели на элементы some_map)
some_vec[1] сперва пусто.
В цикле проходятся все элементы some_vec[0].
Допустим там есть элемент X -- пытаемся сделать 4 возможных хода, получается 4 новых состояния. Проверяем есть ли такие состояния в some_map, если уже есть то игнорируем их. Если нет, то кладем в some_map пару новое состояние -> указатель на предыдущее состояние X. Кроме того кладем указатель на это новое состояние в some_vec[1]. Если новое состояние совпадает с целевым состоянием, то мы нашли решение.
Так продолжаем пока не пройдем все элементы some_vec[0], после этого очищаем some_vec[0] и делаем some_vec[0].swap(some_vec[1]).
И продолжаем пока либо не найдем решение, либо some_vec[0] не окажется пустым.

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

Здравствуйте, dilmah, Вы писали:
D>И наконец волна -- состоит из:
Не встречал раньше такого термина, это что? Если не сложно в 2х словах или ссылку.


D> std::map< marbles_state_t, const marbles_state_t * > some_map;
D> std::vector< const marbles_state_t * > some_vec[2];
Здесь все понятно,но:

D>Допустим начальное состояние это marbles_state_t S;
D>В some_map изначально кладем пару S->NULL. Второй компонент пары -- это указатель на предшествующее состояние, для начального состояния это 0.

Т.е. some_map[S] = NULL, по записи выглядит именно так. Далее:

D>some_vec[0] сперва содержит указатель на S (который лежит в some_map,

Каким образом мы получим этот указатель? Вот при такой записи some_map[S] = NULL для S будет использован конструктор копирования, чтобы поместить его как ключ в map.

>а как известно добавления в some_map не инвалидируют ни итераторы, ни указатели на элементы some_map)

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

D>>И наконец волна -- состоит из:
C>Не встречал раньше такого термина, это что? Если не сложно в 2х словах или ссылку.

выше писали, что это breadth-first search http://ru.wikipedia.org/wiki/Поиск_в_ширину
some_vec[0] и some_vec[1] можно рассматривать как 2 поколения такой движущейся волны.

C>Т.е. some_map[S] = NULL, по записи выглядит именно так. Далее:
D>>some_vec[0] сперва содержит указатель на S (который лежит в some_map,
C>Каким образом мы получим этот указатель? Вот при такой записи some_map[S] = NULL для S будет использован конструктор копирования, чтобы поместить его как ключ в map.

вставить пару в map можно не только some_map[S] = NULL, но и так:
std::map< marbles_state_t, const marbles_state_t * >::iterator it = some_map.insert(std::make_pair(S, NULL)).first;

после этого искомый указатель можно взять как &(it->first)

>>а как известно добавления в some_map не инвалидируют ни итераторы, ни указатели на элементы some_map)
C>Яндекс говорит что так, я сейчас точно не помню, в каком случае итераторы становятся не действительными, буду благодарен если напомните.

у контейнеров типа map или list итераторы на элемент становятся недействительными только когда непосредственно этот элемент удаляется. Добавлять и удалять другие элементы можно безопасно. Это контрастирует с vector, где можно добавить новый элемент и внезапно инвалидировать итераторы на все остальные элементы.

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

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

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

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

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

А>Что-то из условия я не совсем понял, а дырку с отличным номером шарик может пересечь или её надо обходить?

да, нужно обходить. Если шарик попал не в свою лунку, то это проигрышное состояние.

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

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

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

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



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

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

А>Здравствуйте, 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, а по одному на каждую часть.

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

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

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

Здравствуйте, 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>>Может подскажете как это лучше сделать?

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

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

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

Б>

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

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

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

Здравствуйте господа. Недавно тоже пришлось решать данную задачку. Решал полностью самостоятельно, сюда не заглядывал. Сказали для меня мест нет, но не сказали в чем моя проблема. Покритикуйте пожалуйста решение и код. Самому трудно увидеть собственные косяки. Старался сделать в ООП стиле, как того требовалось, только распараллелить не успел. Алгоритм тут вроде уже набросали. Перебор с возможностью отката и сохранением хэшов состоянии, чтобы избежать зацикливании.
Вот проект для VS2008
Прогоняйте для своих входных данных и сообщите о результатах, если не затруднит
За последние 2 месяца прошел 5 собеседовании, вроде хорошо ответил на большинство вопросов, но не зовут. Неужели у меня все так плохо? У меня уже комплекс неполноценности начинается

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

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

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

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

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

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

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

Б>>

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

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

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

В данном случае стоит исходить из физики процесса, наклонили влево -- "катить" начинаем с самых левых шаров постепенно перебираясь вправо (выше ниже значения не имеет, ибо катим строго по прямой, и как следствие взаимодействуют только шарики из одной строки/столбца). Аналогично для остальных направлений.

здесь

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

I>Здравствуйте господа. Недавно тоже пришлось решать данную задачку. Решал полностью самостоятельно, сюда не заглядывал. Сказали для меня мест нет, но не сказали в чем моя проблема. Покритикуйте пожалуйста решение и код. Самому трудно увидеть собственные косяки. Старался сделать в ООП стиле, как того требовалось, только распараллелить не успел. Алгоритм тут вроде уже набросали. Перебор с возможностью отката и сохранением хэшов состоянии, чтобы избежать зацикливании.
I>Вот проект для VS2008
I>Прогоняйте для своих входных данных и сообщите о результатах, если не затруднит
I>За последние 2 месяца прошел 5 собеседовании, вроде хорошо ответил на большинство вопросов, но не зовут. Неужели у меня все так плохо? У меня уже комплекс неполноценности начинается

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

1. Используйте "precompiled headers".
2. Не используйте (НИКОГДА) using namespace в хедерах (а std под страхом смертной казни!) -- потомки проклянут!
3. Активнее используете коллекции

static const int MaxAllowedSteps = 1000;
static char sequence[MaxAllowedSteps];
//array of pointers to cell
Cell** m_ppCells;
//array of pointers to marble
Marble** m_ppMarbles;

все это спокойно меняется на std::vector/string заодно уходит статика.

4. Неоправданно использование макроса #define STEP(d). В данном случае легко заменяется на ф-цию.
5. Достаточно запутанная схема реализации состояний и их сношения с рекурсивной ф-цией.

Возможно что-то упустил. Плюс стиль оформления слабоват -- смелее используйте разделители и комментарии.

S>здесь

ээ.. ну во первых непонятно что это за язык. Выглядит как С++ в котором заменили & на ^

Смущает то что на каждую клетку выделен отдельный класс. Учитывая что состояние большого количества досок нужно хранить это выглядит неуместно -- по памяти будет оверхед на порядок.

смущает, что при этом чрезмерном выделении классов, не был выделен отдельный тип для направлений, и имеется ряд функций MoveN, MoveE, MoveW, MoveS.

Многопоточности не заметил.

Ну и наконец кракозябры (видимо, русские буквы) в комментариях убили.

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

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

_>1. Используйте "precompiled headers".
Всегда так делаю в реальных проектах, но думаю для данной задачи это было не критично.

_>2. Не используйте (НИКОГДА) using namespace в хедерах (а std под страхом смертной казни!) -- потомки проклянут!
Вредная привычка, да.

_>3. Активнее используете коллекции

_> static const int MaxAllowedSteps = 1000;
_> static char sequence[MaxAllowedSteps];
_> //array of pointers to cell
_> Cell** m_ppCells;
_> //array of pointers to marble
_> Marble** m_ppMarbles;

_>все это спокойно меняется на std::vector/string заодно уходит статика.
Т.е. контейнеры всегда предпочтительнее, даже если в них нет строгой необходимости?

_>4. Неоправданно использование макроса #define STEP(d). В данном случае легко заменяется на ф-цию.
Не совсем понял, в данном конкретном случае в чем превосходство функции над макросом? Вроде так оптимальнее же.

_>5. Достаточно запутанная схема реализации состояний и их сношения с рекурсивной ф-цией.
Я просто делаю вид, что работаю со стеком состоянии. Всего 3 операции PushState, PopState, RestoreState, но реализация самых функции слегка запутанно, да. Просто сначала хотел сделать по другому, потом изменил и добавил хэш.

_>Возможно что-то упустил. Плюс стиль оформления слабоват -- смелее используйте разделители и комментарии.
А насколько важна стилистика, если задача решена в целом верно? Я легко могу адаптироваться под стандарты данной команды. Но мне просто шанса не дают себя проявить, а таким тонкостям можно научится только работая в команде с профессионалами. В той конторе, где сейчас работаю нету у кого поучится, получается я там самый крутой и это очень плохо

И да, спасибо вам

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

S>здесь
Для входа

3 2 1
1 0
0 0
2 0
2 1
2 0 2 1

ответ не верен.

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

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

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

_>>1. Используйте "precompiled headers".
I>Всегда так делаю в реальных проектах, но думаю для данной задачи это было не критично.
см. ниже

_>>2. Не используйте (НИКОГДА) using namespace в хедерах (а std под страхом смертной казни!) -- потомки проклянут!
I>Вредная привычка, да.
см.ниже

_>>3. Активнее используете коллекции

_>> static const int MaxAllowedSteps = 1000;
_>> static char sequence[MaxAllowedSteps];
_>> //array of pointers to cell
_>> Cell** m_ppCells;
_>> //array of pointers to marble
_>> Marble** m_ppMarbles;

_>>все это спокойно меняется на std::vector/string заодно уходит статика.
I>Т.е. контейнеры всегда предпочтительнее, даже если в них нет строгой необходимости?
контейнеры всегда предпочтительнее (за тем исключением, когда вам нужно писать код чтобы их "обмануть", тогда имеет смысл подумать о вариантах)

_>>4. Неоправданно использование макроса #define STEP(d). В данном случае легко заменяется на ф-цию.
I>Не совсем понял, в данном конкретном случае в чем превосходство функции над макросом? Вроде так оптимальнее же.
попробуйте отладить макрос А оптимальность -- спорный вариант, компилятор и так встроит все, что нужно

_>>5. Достаточно запутанная схема реализации состояний и их сношения с рекурсивной ф-цией.
I>Я просто делаю вид, что работаю со стеком состоянии. Всего 3 операции PushState, PopState, RestoreState, но реализация самых функции слегка запутанно, да. Просто сначала хотел сделать по другому, потом изменил и добавил хэш.

_>>Возможно что-то упустил. Плюс стиль оформления слабоват -- смелее используйте разделители и комментарии.
I>А насколько важна стилистика, если задача решена в целом верно? Я легко могу адаптироваться под стандарты данной команды. Но мне просто шанса не дают себя проявить, а таким тонкостям можно научится только работая в команде с профессионалами. В той конторе, где сейчас работаю нету у кого поучится, получается я там самый крутой и это очень плохо
тут скорее речь не о конкретном стиле, а об его отсутствии Что-то порекомендовать трудно, просто код плохочитабелен -- трудно разбивается на функциональные части

I>И да, спасибо вам

Да, собственно, не за что.

Прежде всего, люди которые дают вам задание хотят увидеть чего вы стоите как специалист.
Т.е. они ожидают, что вы напишите код, который от вас можно ожидать в коммерческом продукте. Допуская все эти детские ошибки (и возможно какие-то другие) вы оставляете о себе впечатление "джуниора", вне зависимости от вашего фактического уровня

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

Запрос про разбор полетов можете перепостить в основную ветку форума по ++, возможно там набегут более опытные комментаторы... Ну или просто флейма на пару десятков страниц

Удачи! Относитесь к собеседованиям серьезнее!