Тестовые задания при приёме на работу

← →
Kerk © (2014-02-12 20:45) [120]

> если проекция это только отображение первого слоя

Да елки, проекция - это не отображение первого слоя! Ты на в школе на черчении спал чтоль? :)

← →
Rouse_ © (2014-02-12 20:49) [121]

> Kerk © (12.02.14 20:45) [120]
> Да елки, проекция - это не отображение первого слоя! Ты
> на в школе на черчении спал чтоль? :)

Не спал, поэтому и не понимаю в чем затруднения в моей реализации алгоритма? :)

← →
Rouse_ © (2014-02-12 20:53) [122]

Мне кажется лучше сделать так:
GEN++ даст входные матрицы проекций и тот результат, который должен получится.
Отсюда и будем плясать (бо сам уж заинтересовался - чеж там хитрого такого) :)
Ну а после этого и можно рассмотреть варианты решений.

← →
Dennis I. Komarov © (2014-02-12 21:00) [123]

> Rouse_ © (12.02.14 19:39) [112]
>
> > GEN++ ©
>
> Задача ясна, первое что на вскидку вижу, кубический массив
> заполненный единицами и три прохода по векторам (X, Y, Z)
> со скидыванием в ноль по входным матрицам. В итоге остаются
> инициализированные единицами только те ячейки куба, которые
> соответствуют трем входным матрицам.
> Судя по всему неопределенностей здесь нет и время на реализацию
> минут пятнадцать.
> Я где-то ошибся?

Ну да,
шаг 1 - на полный куб накладываем 0-проекции (пропилы и проелы)
шаг 2 - по каждой стороне проекции вычисляем количество "1" (недоелы)
шаг 3 - в том месте где sum(недоелы) >=3 возможны варианты (т.е. невидимый кубик)
шаг 4 - вычисление значение невидимого кубика из расчета всех проекций
шаг 5 - количество неопределенных кубиков ˆ2 есть количество вариантов

← →
Dennis I. Komarov © (2014-02-12 21:03) [124]

шаг 3 - ..... >=2

← →
Kerk © (2014-02-12 21:04) [125]

> Rouse_ © (12.02.14 20:49) [121]
>
> > Kerk © (12.02.14 20:45) [120]
> > Да елки, проекция - это не отображение первого слоя! Ты
> > на в школе на черчении спал чтоль? :)
>
> Не спал, поэтому и не понимаю в чем затруднения в моей реализации
> алгоритма? :)

Положи тапок на лист бумаги, обведи его карандашом. Убери тапок. Что останется на бумаге? Рентген, верхний слой тапка или все же одна из его проекций? :)

← →
Kerk © (2014-02-12 21:05) [126]

> Dennis I. Komarov © (12.02.14 21:00) [123]

Да, места, где точно, нули определить легко. Дальше перебор. Вся задача сводится к сокращению этого перебора. Копчиком чувствую, что нужно посмотреть в сторону алгоритмов решения судоку :)

← →
Kerk © (2014-02-12 21:08) [127]

Если с тапком не получится, обведи банку с огурцами. Проверь видно ли на проекции, что в банке есть огурцы :)

← →
Dennis I. Komarov © (2014-02-12 21:15) [128]

> Да, места, где точно, нули определить легко. Дальше перебор.
> Вся задача сводится к сокращению этого перебора. Копчиком
> чувствую, что нужно посмотреть в сторону алгоритмов решения
> судоку :)

3. по сумме не нулевых элементов вычисляют где он не один, т.е. возможны различные варианты.
4. эти варианты накладываем на 0-проекции и на S-проекции - там где совпало с 0 или с 1 (на S) элемент однозначно определен, else может принимать оба значения (не противоречит исходным данным)

Все довольно однозначно, никаких переборов

← →
Dennis I. Komarov © (2014-02-12 21:26) [129]

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

Я делал, там сложнее.

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

Тут есть однозначные проекции и куча вариантов ответов, а не единственный правильный.

← →
Rouse_ © (2014-02-12 21:27) [130]

Сходил принял конячку - осмыслил решение :)

Допустим дано три проекции вида:

0000 0110 0110 0000

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

Отсюда строим алгоритм:
1. изначально бьем тунель из нулей по каждой оси
2. (тут два решения - умное и правильное)
2.1: умное - ищем группы кубов и убирая каждый из них - сверяемся с проекциями (оно нам надо?)
2.2: (правильное) Имея на руках только отсеченные кубы, бежим по ним всем и исключаем со сверкой с матрицами. Те кто не прошли сверку - в результат вывода не попадают.

Итого: время на реализацию 30 минут, время работы алгоритма менее секунды.

← →
Dennis I. Komarov © (2014-02-12 21:34) [131]

> Сходил принял конячку - осмыслил решение :)

Тебя допинг-контроль спалил :)

← →
Rouse_ © (2014-02-12 21:40) [132]

> Dennis I. Komarov © (12.02.14 21:34) [131]
> Тебя допинг-контроль спалил :)

Не - жена ща с полями Галуа разбирается, ей точно не до меня :)

← →
Dennis I. Komarov © (2014-02-12 21:51) [133]

> шаг 5 - количество неопределенных кубиков ˆ2 есть количество
> вариантов

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

← →
Dennis I. Komarov © (2014-02-12 21:54) [134]

> Допустим дано три проекции вида:
>
> 0000
> 0110
> 0110
> 0000

По нему 8 элементов однозначно не определены, но так как в любой проекции на них "1" в условиях не должно быть два "0" подряд

← →
Rouse_ © (2014-02-12 21:58) [135]

> Dennis I. Komarov © (12.02.14 21:54) [134]
> По нему 8 элементов однозначно не определены

С какого перепугу?

← →
Inovet © (2014-02-12 22:01) [136]

Проекции  это OR всех слоёв по оси. Я правильно понимаю?

← →
Dennis I. Komarov © (2014-02-12 22:04) [137]

> Проекции — это OR всех слоёв по оси. Я правильно понимаю?

true

← →
Dennis I. Komarov © (2014-02-12 22:08) [138]

> С какого перепугу?

Потому как все три проекции одинаковы (как я понял), и согласно им все крайние грани пусты. Остается внутри куб 2х2 из 8-ми элементов. Где я не прав?

← →
GEN++ © (2014-02-12 22:09) [139]

>Rouse_ ©
>Kerk ©
Я Вам отправил на почту небольшую анимашку с тестовыми заданиями
и возможностью их ручного решения

← →
GEN++ © (2014-02-12 22:09) [140]

← →
Dennis I. Komarov © (2014-02-12 22:09) [141]

> Остается внутри куб 2х2 из 8-ми элементов

2х2х2 разумеется...

← →
Rouse_ © (2014-02-12 22:10) [142]

Ну как минимум в том, что 2 х 2 = 8 :)

← →
Rouse_ © (2014-02-12 22:11) [143]

> Dennis I. Komarov © (12.02.14 22:09) [141]
>
> > Остается внутри куб 2х2 из 8-ми элементов
>
> 2х2х2 разумеется...

Ой плин - эт я затупил - сори, конечно 8 :)))

← →
Rouse_ © (2014-02-12 22:11) [144]

> GEN++ © (12.02.14 22:09) [140]

Угу спасибо - хорошая задачка для разминки мозга :)

← →
Kerk © (2014-02-12 22:42) [145]

> GEN++ © (12.02.14 22:09) [139]

А, это от тебя письмо было :)
Я сразу не понял.

← →
Dennis I. Komarov © (2014-02-12 22:49) [146]

так, ну решение далее такое (совсем без перебора не придумал):

5 - цикл по всем неопределенным вариантам, на каждом формируем S-проекции (обозначим S2). Далее сравниваем если в S2-проекции элемент "0", а в исходной "1", тогда данный вариант противоречит условию

← →
Dennis I. Komarov © (2014-02-12 23:06) [147]

P.S.
Кстати, достаточно вычислить и проверить проекции S2 только этого элемента.

← →
Юрий Зотов © (2014-02-13 00:01) [148]

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

> GEN++ © (12.02.14 10:41) [108]
> Есть варианты где число решений превышает 100
> На это достаточно скоростной код тратит 3-4 минуты

Че-то много)
Можешь хоть один такой вариант привести?

← →
Styx (2014-02-13 00:20) [150]

> Ориентация естественно известна но решение в три строки?
> ???????

Тогда cube[i,j,k]=p1[i,j]*p2[j,k]*p3[i,k] обязательно будет решением.
Но если нужно найти все возможные решения и/или проверить проекции на совместимость - тогда, конечно, не три строки.

> Юрий Зотов © (13.02.14 00:01) [148]
> два профессиональных программиста не понимают механизмов передачи параметров

потамушта задурили людям головы всякой хренью вместо преподавания основ

> [149] Sha © (13.02.14 00:16)
> Можешь хоть один такой вариант привести?

Керк приводил

> [114] Kerk © (12.02.14 19:56)

4*4*4*4=256 вариантов только с 1 единицей в каждом слое отнимем из всего 2^(4*4*4*4). Так что ли? Что-то много получилось.

> Inovet © (13.02.14 00:26) [152]
> Керк приводил

мне кажется, что на расчет приведенного им варианта
потребуется гораздо меньше 3-4х минут

> [153] Sha © (13.02.14 00:33)
> мне кажется, что на расчет приведенного им варианта
> потребуется гораздо меньше 3-4х минут

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

> Inovet © (13.02.14 00:43) [154]
> Ну первое, получается, в реальности вообще невозможно сделать.

Почему невозможно?
Например, представить кубик 4х4х4 как 4 слоя размером 4х4.
Хотя мне больше нравится как int64 )

Может кто-нить накодит "input-output" в GUI?

Стандартизируем условие:
AX, AY, AZ: array[0..N-1, 0..N-1] of Byte; // Проекции куба

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

> Так это самое сложное в этой задаче)

скорее самое нудное и долгое, а время нема...

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

Я думал... ИМХО так проще для понимания алгоритма. Этот кубик можно упаковать в 8 байт, а проекцию в два, но не удобно для восприятия.
И сильно привяжется к N=4

Тестовые задания при приёме на работу Найти похожие ветки