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

← →
Dennis I. Komarov © (2014-02-13 13:25) [160]

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

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

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

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

← →
Dennis I. Komarov © (2014-02-13 13:48) [161]

> а проекцию в два,

пардонтес, в пол байта

← →
Sha © (2014-02-13 14:25) [162]

проще договориться вводить данные из Memo (сейчас это модно),
а привязка к N=4 для учебной задачи даже хорошо,
можно посмотреть, как структура данных влияет на скорость

← →
Dennis I. Komarov © (2014-02-13 14:55) [163]

> проще договориться вводить данные из Memo (сейчас это модно),

ввод - ерунда, вот вывод множества...

> а привязка к N=4 для учебной задачи даже хорошо,
> можно посмотреть, как структура данных влияет на скорость

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

← →
Sha © (2014-02-13 15:25) [164]

> Dennis I. Komarov © (13.02.14 14:55) [163]
> ввод - ерунда, вот вывод множества...

можно выводить количество и последний найденный,
хотя даже для [130] у меня не получается вручную подсчитать
количество решений

> ну если задачу рассматривать как обучение битовым операциям...

а че лень-то, там все решение в 10 строчек уложится ))

← →
Dennis I. Komarov © (2014-02-13 16:29) [165]

> можно выводить количество и последний найденный,
> хотя даже для [130] у меня не получается вручную подсчитать
>
> количество решений
>

там 256 потенциальных решений, из них нужно исключить те, которые противоречат исходным проекциям. Кроме как перебирать варианты, я пока ничего не придумал.
Если я не ошибаюсь, то там будет 2 * 2^6 = 128 решений, но это вычислено логически, а не математически.

> а че лень-то, там все решение в 10 строчек уложится ))

Если писать нормально, тогда не верю. У меня уже >50 и это без перебора.

← →
brother © (2014-02-13 16:36) [166]

> Как твой метод догадается, что куб внутри пустой? :)

надо вводить доп. обозначения - штрихпунктир...

← →
Sha © (2014-02-13 16:41) [167]

> Dennis I. Komarov © (13.02.14 16:29) [165]
> Если писать нормально, тогда не верю.
> У меня уже >50 и это без перебора.

вечером напишу

← →
GEN++ © (2014-02-13 16:51) [168]

>[156] Куда складывать решения?
В исходном варианте задания было так
"Наити решение (я)" где кол-во оствшихся в фигуреи кубиков будет минимально"
Но чтобы найти минимальное решение надо проверить все

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

В точку

Эту задачу давали при приеме на работу в одной Зеленоградской фирме
Условие было такое вот задание, срок 2 недели - решаете берем на работу
иначе - ну тут понятно.

← →
Dennis I. Komarov © (2014-02-13 17:10) [169]

> Но чтобы найти минимальное решение надо проверить все

А вот и нет...

← →
Rouse_ © (2014-02-13 17:37) [170]

> GEN++ © (13.02.14 16:51) [168]
> Эту задачу давали при приеме на работу в одной Зеленоградской
> фирме
> Условие было такое вот задание, срок 2 недели - решаете
> берем на работу
> иначе - ну тут понятно.

Вообще суровые у вас критерии отбора :)
Хотя фиг знает, я же специфики не знаю - вероятно именно такой подход в чем-то оправдан (в данном случае).
У нас с этим как-то проще, мы по другим критериям отбор ведем :)

← →
Dennis I. Komarov © (2014-02-13 18:06) [171]

> У нас с этим как-то проще, мы по другим критериям отбор
> ведем :)

Количество и качество коньяка? :)))

← →
Rouse_ © (2014-02-13 18:09) [172]

> Dennis I. Komarov © (13.02.14 18:06) [171]
> Количество и качество коньяка? :)))

Это уже на психологическую совместимость с коллективом (тоже важный момент, кстати) :)

← →
Sha © (2014-02-13 18:12) [173]

вот те самые 10 строчек, поехал домой дописывать остальное)

count:=0; sol:=-1; repeat; sol:=(sol+1) or cube; for d:=0 to dim do begin; temp:=-1; for p:=0 to bnd do temp:=mask[d,p] and sol shr (p*plane[d]) and temp; if temp<>proj[d] then goto next; end; inc(count); next: until sol=-1;

← →
Dennis I. Komarov © (2014-02-13 19:57) [174]

> вот те самые 10 строчек, поехал домой дописывать остальное)

У мни дома IDE нету... даже окон не осталось

а xCode пока не освоил...

А коменты к коду можно? Так без Розыча не разобрать, коньяк у него...

← →
Sha © (2014-02-13 20:22) [175]

> Dennis I. Komarov © (13.02.14 19:57) [174]
> А коменты к коду можно?

Это быстрый вариант тупого перебора. Просто подсчитывает количество решений в count. В переменной sol сидит очередной 64-битный кандидат. Единственное достоинство этого варианта перебора в том, что благодаря инвертированному представлению данных (1 означает осутствие кубика), он позволяет при помощи (... or cube) проскакивать биты, где заведомо не может стоять кубик. Но тем не менее он делает много лишнего (а в свете [168] - очень много лишнего), например, он начинает перебор с 0, хотя очевидно, что минимальное необходимое число кубиков превышает максимальную площадь проекций. По идее тут нужна комбинация двоичного поиска для выбора числа кубиков и перебора сочетаний для этого числа кубиков.
Другое: цикл по d - цикл по количеству измерений (проекций), temp - проекция кандидата на решение, цикл по p - цикл по слоям текущего измерения, mask[d,p] - маски слоев (индикаторы принадлежности бита слою p измерения d), plane[d] - расстояние между соседними слоями по измерению d, proj[d] - проекция по измерению d.

← →
Rouse_ © (2014-02-13 20:24) [176]

> А коменты к коду можно? Так без Розыча не разобрать, коньяк
> у него...

Коньяк да, у меня, а воть декларация переменных у Сани, я сам пока что не вкуриваю в чего он тут наваял :)

← →
Sha © (2014-02-13 20:37) [177]

тама все 64-битное, окромя переменных цикла и plane[]

← →
Rouse_ © (2014-02-13 20:53) [178]

> Sha © (13.02.14 20:37) [177]
> тама все 64-битное, окромя переменных цикла и plane[]

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

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

← →
Sha © (2014-02-13 21:01) [179]

> Rouse_ © (13.02.14 20:53) [178]
> Пусть так, но алгоритм не читабелен

Есть такое дело. Ща ввод допишу уже, наверно, будет чуть яснее.

← →
Dennis I. Komarov © (2014-02-13 21:23) [180]

Ну идею я понял, но трэйсить в голове это...
Однако сей подход противоречит решению задачи, просто перебрать все варианты. Некие инъекции логики в этот подход будет довольно сложно реализовать :) А прочесть еще сложнее :)

← →
Sha © (2014-02-13 21:30) [181]

> Dennis I. Komarov © (13.02.14 21:23) [180]
> Некие инъекции логики в этот подход

Этот подход любые инъекции только замедлят.
Годный подход описан в [175].

//Объемный куб состоит из 4х4х4 кубиков единичного размера. Некоторые из них прозрачные. //По 3-м заданным проекциям (фронтальная, сверху, справа) определить количество возможных фигур. //Ввод данных - в виде 3-х послойных матриц 4х4, вывод - в виде 4-х матриц. //Время вычислений - не более 1 часа. Найти решение с минимальным количеством кубиков. unit Cube4x4Form; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; const dim= 2; //номер последней проекции или размерность пространства - 1 )) bnd= 3; //номер последней строки (столбца, слоя) в проекции type TForm1 = class(TForm) memInput: TMemo; memDebug: TMemo; memOutput: TMemo; btnInput: TButton; btnSolution: TButton; procedure btnInputClick(Sender: TObject); procedure btnSolutionClick(Sender: TObject); end; var Form1: TForm1; implementation {$R *.dfm} // вид спереди, вид сверху, вид справа, // ближний слой ближний слой дальний слой // 0 1 2 3 0 16 32 48 0 16 32 48 // 4 5 6 7 1 17 33 49 4 20 36 52 // 8 9 10 11 2 18 34 50 8 24 40 56 // 12 13 14 15 3 19 35 51 12 28 44 60 //коэффициенты = расстояния между var // (спереди, сверху, справа) col: array[0..dim] of integer= (1, 16, 16); row: array[0..dim] of integer= (4, 1, 4); plane: array[0..dim] of integer= (16, 4, 1); zerocount: array[0..255] of byte; var //маски для выбора кубиков нужного слоя в нужном измерении mask: array[0..dim, 0..bnd] of int64; //проекции (спереди, сверху, справа), //после ввода инвертируем: единичный биты соответствуют сквозным дыркам proj: array[0..dim] of int64; //максимально заполненный куб, //после ввода инвертируем: единичный бит означает запрет размещения кубика на данном месте cube: int64; dataOK: boolean= false; const CRLF= #13#10; function GetData(const txt: AnsiString): boolean; var SL: TStringList; s: array[0..dim] of AnsiString; t: AnsiString; //u, v: AnsiString; ch: AnsiChar; d, c, r, p, i: integer; temp, extent: int64; begin; Result:=false; SL:=TStringList.Create; try SL.Text:=txt; for i:=SL.Count-1 downto 0 do begin; t:=Trim(SL[i]); if t="" then SL.Delete(i) else begin; if Length(t)<>1+bnd then exit; for c:=0 to bnd do if not (t[1+c] in ["0","1"]) then exit; SL[i]:=t; end; end; if SL.Count<>(dim+1)*(bnd+1) then exit; for d:=0 to dim do begin; SetLength(s[d],(bnd+1)*(bnd+1)*(bnd+1)); for r:=0 to bnd do begin; for c:=0 to bnd do begin; ch:=SL[d*(1+bnd)+r][1+c]; i:=r*row[d]+c*col[d]; for p:=0 to bnd do begin; s[d][1+i+p*plane[d]]:=ch; end; end; end; end; cube:=-1; extent:=0; for d:=0 to dim do begin; proj[d]:=0; for r:=0 to bnd do begin; for c:=0 to bnd do begin; i:=r*row[d]+c*col[d]; ch:=s[d][1+i]; //plane[0] temp:=1; temp:=temp shl i; if ch="1" then proj[d]:=proj[d] or temp; mask[d,0]:=mask[d,0] or temp; end; end; temp:=0; for p:=0 to bnd do begin; i:=p*plane[d]; temp:=temp or proj[d] shl i; if p<>0 then mask[d,p]:=mask[d,0] shl i; end; cube:=cube and temp; extent:=extent or temp; end; for d:=0 to dim do begin; temp:=-1; for p:=0 to bnd do begin; temp:=mask[d,p] and extent shr (p*plane[d]) and temp; end; if temp<>proj[d] then exit; //ошибка в исходных данных (проекции не согласованы) end; { t:=""; for d:=0 to dim do t:=t+s[d]+CRLF; Form1.memDebug.Text:=t; SetLength(t,(bnd+1)*(bnd+1)*(bnd+1)); SetLength(u,(bnd+1)*(bnd+1)*(bnd+1)); SetLength(v,(bnd+1)*(bnd+1)*(bnd+1)); temp:=cube; for i:=0 to (bnd+1)*(bnd+1)*(bnd+1)-1 do begin; t[1+i]:=AnsiChar(ord("0")+(temp and 1)); u[1+i]:=AnsiChar(ord("0")+i div 10); v[1+i]:=AnsiChar(ord("0")+i mod 10); temp:=temp shr 1; end; Form1.memDebug.Lines.Add(""); Form1.memDebug.Lines.Add(t); Form1.memDebug.Lines.Add(u); Form1.memDebug.Lines.Add(v); } cube:=not cube; for d:=0 to dim do proj[d]:=mask[d,0] and not proj[d]; for i:=0 to 255 do begin; d:=i; r:=0; for c:=0 to 7 do begin; if d and 1=0 then inc(r); d:=d shr 1; end; zerocount[i]:=r; end; Result:=true; finally SL.Free; end; end;

function GetSolutionText(const Solution: int64): AnsiString; var s: AnsiString; r, p, i, len: integer; temp: int64; begin; len:=(bnd+1)*(bnd+1)*(bnd+1); SetLength(s,len); temp:=not Solution; for i:=0 to len-1 do begin; s[1+i]:=AnsiChar(temp and 1 + ord("0")); temp:=temp shr 1; end; Result:=""; i:=1; for p:=0 to bnd do begin; Result:=Result + CRLF; for r:=0 to bnd do begin; Result:=Result+copy(s,i,bnd+1)+CRLF; i:=i+(bnd+1); end; end; end; function GetSolutionSize(const Solution: int64): integer; var i: integer; begin; Result:=0; i:=SizeOf(Solution)*8; repeat; i:=i-8; Result:=Result + zerocount[Solution shr i and 255]; until i=0; end; //Это быстрый вариант тупого перебора. Просто подсчитывает количество решений в Count. //В переменной sol сидит очередной кандидат. Единственное достоинство этого варианта перебора в том, //что благодаря инвертированному представлению данных (1 означает отсутствие кубика), //он позволяет при помощи (... or cube) проскакивать биты, где заведомо не может стоять кубик. //Он делает много лишнего, например, начинает перебор с 0, хотя очевидно, что необходимое //число кубиков не менее максимальной площади проекций. Вероятно, тут лучше подойдет //перебор сочетаний для возможных чисел кубиков. //Другое: цикл по d - цикл по количеству измерений (проекций), temp - проекция кандидата на решение, //цикл по p - цикл по слоям текущего измерения, mask[d,p] - маски слоев (индикаторы принадлежности //бита слою p измерения d), plane[d] - расстояние между соседними слоями по измерению d, //proj[d] - проекция по измерению d. procedure FindSolution(var Solution, Total, Count: int64; var Size: integer); var sol, temp: int64; d, p, i: integer; label next; begin; Total:=0; Size:=MaxInt; sol:=-1; repeat; sol:=(sol+1) or cube; for d:=0 to dim do begin; temp:=-1; for p:=0 to bnd do temp:=mask[d,p] and sol shr (p*plane[d]) and temp; if temp<>proj[d] then goto next; end; inc(Total); i:=GetSolutionSize(sol); if Size>=i then begin; if Size>i then begin; Size:=i; Solution:=sol; Count:=0; end; inc(Count); end; next: until sol=-1; end; procedure TForm1.btnInputClick(Sender: TObject); const InputMessages: array[boolean] of AnsiString= ("Oшибка во входных данных", "Данные введены успешно"); begin; memOutput.Text:=""; dataOK:=GetData(memInput.Text); memOutput.Lines.Add(InputMessages[dataOK]); end; procedure TForm1.btnSolutionClick(Sender: TObject); var Solution, Total, Count: int64; Size: integer; begin; if dataOK then begin; FindSolution(Solution, Total, Count, Size); memOutput.Lines.Add(Format("Всего найдено %d решений", [Total])); if Count>0 then begin; memOutput.Lines.Add(Format("Из них %d решений из %d кубиков", [Count, Size])); memOutput.Lines.Add("Одно из них приведено ниже"); memOutput.Lines.Add("(вид спереди, ближний слой - первый)"); memOutput.Lines.Add(GetSolutionText(Solution)); end; end; end; end.

Вход 0000 0110 0110 0000 0000 0110 0110 0000 0000 0110 0110 0000 Выход Данные введены успешно Всего найдено 35 решений Из них 2 решений из 4 кубиков Одно из них приведено ниже (вид спереди, ближний слой - первый) 0000 0000 0000 0000 0000 0010 0100 0000 0000 0100 0010 0000 0000 0000 0000 0000

>[168] Вообще суровые у вас критерии отбора :)
Хотя фиг знает, я же специфики не знаю - вероятно именно такой подход в чем-то оправдан (в данном случае).
У нас с этим как-то проще, мы по другим критериям отбор ведем :)

К счастью это не у нас. Начало, как Вы могли заметить интригующее
но вот концовка в совковом стиле:
2 с лишним года назад у меня сын заканчивал вуз и подыскивал себе
работу на будущее, имея средний опыт написания кода и для PC
и для микроконтроллеров. Так вот повозившись с этой задачей и написав
для решения код с ГУЕМ (я в задаче принимал участие в качестве скептика
из мозгового штурм) представил его в фирму. Директор направил его к
сотрудникам для оценки. Оценили работу так (эту задачу давали у них, как выяснилось, многим):
такой быстрый и находящий такое кол-во решений код еще не писал никто. После ознакомления с выводами сотрудников директор заявил (почти дословно)
"Ну ты это, проработай у нас пока так (т.е. бесплатно) а если мы увидим что ты прибыль приносишь то будем может быть и и зарплату (причем без указания размера) давать"

Так что "У нас с этим как-то проще, мы по другим критериям отбор ведем "
это обнадеживает.

Найдена опечатка в
procedure TForm1.btnSolutionClick(Sender: TObject); напечатано if Count>0 then begin; должно быть if Total>0 then begin;

> Выход
>
> Данные введены успешно
> Всего найдено 35 решений
> Из них 2 решений из 4 кубиков
> Одно из них приведено ниже
> (вид спереди, ближний слой - первый)

А время?

Но для внутреннего кубика 3х3х3 ищет уже около 3 сек.

И еще, если кто будет играть с приведенным кодом,
советую выкинуть из процедуры ввода проверку противоречивости проекций:

for d:=0 to dim do begin; temp:=-1; for p:=0 to bnd do begin; temp:=mask[d,p] and extent shr (p*plane[d]) and temp; end; if temp<>proj[d] then exit; //ошибка в исходных данных (проекции не согласованы) end;

Похоже, что-то я перемудрил там, а и без нее все прекрасно работает и отсекается.

← →
демотиватор (2014-02-17 15:13) [190]

А стоят ли такие выпендрежи и мозгодробилки, ну вот вы прошли отбор и вас взяли неизвестно куда в супер-пупер НИИ на з/п. в 20 тыс. рублей ... остановитесь и одумайтесь оно вам нужно жизнь то одна стоит ли ее в богом забытых конторах проводить за непонятные фуфелки?

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