Здравствуйте господа. Недавно тоже пришлось решать данную задачку. Решал полностью самостоятельно, сюда не заглядывал. Сказали для меня мест нет, но не сказали в чем моя проблема. Покритикуйте пожалуйста решение и код. Самому трудно увидеть собственные косяки. Старался сделать в ООП стиле, как того требовалось, только распараллелить не успел. Алгоритм тут вроде уже набросали. Перебор с возможностью отката и сохранением хэшов состоянии, чтобы избежать зацикливании.
Вот проект для 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>И да, спасибо вам

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

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

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

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

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