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

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

а тексты были такие:

#1
ni the nnniiggeb odg treedca the vsnheea nda the trhea. het trhea wsa
uronmfed nda void, ssrnkeda wsa on the feca of the peed, nda the
trpiis of odg vroheed vroe the usrfeca of the wtrea. nhet odg sida,
tel trhee eb tlihg; nda trhee wsa tlihg. odg wsa ttha the tlihg wsa
oogd, nda odg viieddd the tlihg romf the ssrnkeda. odg lledca the
tlihg yad, nda the ssrnkeda he lledca tihgn. os trhee wsa vnnigee, nda
trhee wsa ronnmig, one yda

#2
yutrdaas ronnmig wsa omec, nda lla the usrmme wrold wsa trihgb nda
srhfe, nda rnmmiigb wtih life. rheet wsa a song ni yvree trhea; nda if
the trhea wsa yuong the usmic ussied ta the spli. rheet wsa rheec ni
yvree feca nda a srpnig ni yvree tspe. het uttssroleec- wree ni oomlb
nda the rrngfecaa of the sssoomlb llifed the ria. riffdac llih, yonedb
the vlligea nda voeba ti, wsa rngee wtih vttonigeea nda ti yla utsj
rfa uonhge ywaa to smee a tlleeecbad ndal, yrmeda, usrpolfee, nda
vtnniiig.

#3
rheet onec vlied a rpoo trolia, woh hda a son lledca nliddaa, a
ssrleeca, lied yob woh wuold od tonnihg utb ypla lla yda onlg ni the
ttssree wtih ttllie lied ysob lkie smlihfe. siht so vrigeed the
trhfea ttha he iedd; yte, ni tspie of sih tsromhe' tsrea nda ysrrpea,
nliddaa idd ton nmed sih ywsa. neo yda, wnhe he wsa ypnliga ni the
ttssree sa uusla, a tsrrngea skeda mih sih gea, nda if he wree ton the
son of utsphaam the trolia.

Здравствуйте, мыщъх, Вы писали:

М>а задание было такое. даны три зашифрованных текста.

Шифрование заключается в сортировке букв в словах?

Здравствуйте, мыщъх, Вы писали:

М>а тексты были такие:

М>#1
М>ni the nnniiggeb odg treedca the vsnheea nda the trhea. het trhea wsa
in the beginning god created the heaven and the earth... <чёт дальше не интересно>

М>uronmfed nda void, ssrnkeda wsa on the feca of the peed, nda the
М>trpiis of odg vroheed vroe the usrfeca of the wtrea. nhet odg sida,

Здравствуйте, мыщъх, Вы писали:

М> odg

Есть сомнения, что программу, которая верно определит, что это за слово — "dog" или "god" — , можно написать за один час. Только если человек ранее не занимался natural language processing.
А так общий алгоритм бы бы таков: все комбинации зашифрованного слова отправлять в гугл, и то слово, которое выдает больше все результатов, считать искомым.

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

Q>Здравствуйте, мыщъх, Вы писали:

М>>а тексты были такие:

М>>#1
М>>ni the nnniiggeb odg treedca the vsnheea nda the trhea. het trhea wsa
Q>in the beginning god created the heaven and the earth... <чёт дальше не интересно>

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

Здравствуйте, мыщъх, Вы писали:

М>дальше неинтересно или вы забуксовали? вообще-то, предполагалось, что это будет делать программа. с учетом того, что в последнем тексте встречаются совсем не английские имена (сюрприз!) то английского словаря для реконструкции недостаточно.

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

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

AM>Здравствуйте, мыщъх, Вы писали:

М>>а задание было такое. даны три зашифрованных текста.

AM>Шифрование заключается в сортировке букв в словах?
угу. все буквы отсортированы задом наперед и никакой логики в этом нет, что делает невозможным реконструкцию "трудных" слов (в частности, не английских имен) на основе реконструкции "легких" слов, т.к. информация о порядке букв утрачена.

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

Здравствуйте, мыщъх, Вы писали:

М>дальше неинтересно или вы забуксовали?

Неинтересно. Реально уныло, уж извини

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

A>Здравствуйте, мыщъх, Вы писали:

М>> odg

A>Есть сомнения, что программу, которая верно определит, что это за слово — "dog" или "god"
программа может пользоваться интернетом. и тащить все оттуда.

A>А так общий алгоритм бы бы таков: все комбинации зашифрованного слова отправлять в гугл,
A>и то слово, которое выдает больше все результатов, считать искомым.
гугл борется с ботами. с яху в этом плане намного проще. но как бы да, и тот хлопец, и я -- оба пользовали поисковые системы для получения ответа на вопрос кто сотворил землю -- пес смердящий или господь бог.

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

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

Q>Здравствуйте, мыщъх, Вы писали:

М>>дальше неинтересно или вы забуксовали? вообще-то, предполагалось, что это будет делать программа. с учетом того, что в последнем тексте встречаются совсем не английские имена (сюрприз!) то английского словаря для реконструкции недостаточно.

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

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

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

А>Здравствуйте, мыщъх, Вы писали:

М>>дальше неинтересно или вы забуксовали?
А>Неинтересно. Реально уныло, уж извини
это не ответ. я так и теорему ферма могу доказать, сославшись на то, что это же очевидно, но лень писать доказательство.

Здравствуйте, мыщъх, Вы писали:

М> текст номер три снова переводной и переводов сильно больше одного. так что при всем уважении, ваш алгоритм не работает.

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

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

A>Сразу общий алгоритм в таком случае написать не получится.
Извините, но в трудоустройстве вам отказано

Здравствуйте, мыщъх, Вы писали:

М>в этом топике народ отказывается верить, что жизнь не малина и работодатели тащат через океан все, что работает.
Да тащат-то они все, только работа в большинстве случаев сводится к "добавить вот тут валидацию аргументов да и вообще, работа не главное, главное — быть членом нашей дружной команды".
Про Гугл вот хорошая цитата есть:

I used to joke with my colleagues that Larry & Sergey go out on their yachts — tie them together, sit back on the same recliners you'll find on their jumbo jet, each on his own yacht/set of yachts, smoke cigars, and put up pictures of Googlers with little snippets like "was a GM at muti-national telecomm company, got a Harvard MBA and is now answering Orkut tickets." and then they would erupt in laughter and clink their cigars & Scotch together in celebration. This, of course, is highly unlikely given neither of them would ever smoke a cigar or drink Scotch. Remainder is plausible.

М>а тексты были такие:
М>[поскипано]
и? буквы местами переставлены. соответственно, для расшифровки нужна база по статистике и некая примитивная база по корреляциям. можно взять гугл или любой другой поисковик.
1. Для каждого "слова" перебрать возможные комбинации, отсеиваем то, что словами не является. Получаем список "кандидатов" для каждого слова. Определяем "коэффициент уверенности", как отношение частоты лучшего кандидата к частоте следующего. Т.е., например odg может быть и god и dog, а вот с "nnniiggeb" понятно, что это beginning.
2. Начинаем со слов с наибольшим коэффициентов. Для неоднозначных слов смотрим не только на частоту использования самих слов, но и на корелляцию — т.е. сравниваем относительные частоты "dog beginning created" с "god beginning created".

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

Только вот толку с того? Все равно это собеседование — первый и последний шанс для сотрудника воспользоваться мозгом. Работа скорее всего быстро скатится в просиживание штанов, вечные митинги ни о чем и фикс мелких багов...

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

А мне понравилось, по-моему очень неплохой тест. Поскольку test cases всего 3, проблемы написать программу вообще никакой:

if (text == "ni the nnniiggeb odg treedca <...>") return "in the beginning god created <...>"

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

Если требуется generic алгоритм, тут уже будет сложнее и лично я за час не управлюсь, тем более на незнакомом языке (питоне).

Общая идея простая. Поскольку это явно один связный текст, в конечном итоге нужно будет найти (search) именно заданный отрывок.

Разбиваем текст на предложения. Внутри каждого предложения будем искать по словам, пробуя все перестановки букв в слове, дабы вывести возможные варианты словосочетаний. На этом этапе возможны всякие оптимизационные ухищрения (например, разбивать по 2 слова, по 3 слова и т.п.), но в прототипе требования к производительности не указаны, а значит, пусть тормозит.

В полученном наборе может быть более чем один вариант конкретного предложения (тот самый случай с dog и god, в интернете же всякое можно найти, в том числе и "in the beginning dog created <...>"). Перебираем все возможные комбинации (с учётом того, что порядок предложений менять мы не можем) в поисках совпадения с конкретным текстом. Если таких совпаденй более одного, выводим все — ибо текст не может быть декодирован однозначно.

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

B>Здравствуйте, мыщъх, Вы писали:

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

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

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

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

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

B>1. Для каждого "слова" перебрать возможные комбинации, отсеиваем то, что словами не является.
перебирать? да вроде бы достаточно взять словрь, каждое слово преобразовать в список. список -- отсортировать. каждое слово исходного текста так же преобразовать в список. затем найти одинаковые списки. алгоритмическая сложность ИМХО минимальна и работает очень шустро. я поленился и загнал все списки в мап. чел с украины реализовал бинарный поиск. но визуально производительность в обоих случаях идентична.

B> Определяем "коэффициент уверенности", как отношение частоты лучшего кандидата к частоте следующего.
да, а при неоднозначности берем _все_ вхождения данного кандидата плюс слова следующие за ним. не может быть так, чтобы во всех вхождениях получился равновероятный результат. однако, как показал отладочный вывод, на заданных текстах достаточно было первого вхождения.

B> Т.е., например odg может быть и god и dog, а вот с "nnniiggeb" понятно, что это beginning.
да, большинство слов декодируются однозначно. используем их в качестве "якоря". за неоднозначными словами лезем в иннет и ищем якорь + неоднозначное слово + якорь. если несколько неоднозначных слов следуют друг за другом, то это делу не мешает. разумеется, подобный алгоритм не в состоянии декодировать "прикольные" тексты, в которых библия переписана так, что мир был сотворен собакой, но для тестового задания это уж слишком.

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


B>Только вот толку с того? Все равно это собеседование — первый и последний шанс
B>для сотрудника воспользоваться мозгом. Работа скорее всего быстро скатится
B>в просиживание штанов, вечные митинги ни о чем и фикс мелких багов...
"а жить на что?" (с). вы хотите сказать, что в рф работа более творческая? классика жанра -- в сша едут не за тем, чтобы работать, а за тем, чтобы жить.

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

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

SD>Если требуется generic алгоритм, тут уже будет сложнее и лично я за час не управлюсь, тем более на незнакомом языке (питоне).
в этом случае вы вряд ли будете метить в группу прототипирования на питоне. кстати, тут за версту несет умением работать со списками. на си решение выглядело бы иначе. в принципе, подумалось мне, что на питоне это решается и через регулярные выражения, но и без них все просто и элегантно -- преообразуем каждое слово исходного текста в список, сортируем. далее берем словарь. сортируем все слова как списки. помещаем их в мап — список_слов_соответствия. ну а дальше просто делаем выборку из мап. впрочем, мап был только у меня. у человека, который проходил это собеседования, был бинарный поиск, но ИМХО мап совсем неплох в своей алгоритмической сложности, хотя хз какая она у него. питон ее не декларирует и разные реализации питона могут делать это по разному.

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

SD>Разбиваем текст на предложения. Внутри каждого предложения будем искать по словам,
SD>пробуя все перестановки букв в слове, дабы вывести возможные варианты словосочетаний.
ИМХО вы тут слегка тупите. достаточно отсорировать словарные слова (операция, выполняемая один раз) и сравнивать словарные слова с исходными, что сводится либо к двоичному поиску (вариан чела с украины), либо это мап (мой вариант). оба варианта работают настолько шустро, что львиная доля времени уходит на в/в и разница между ними нивелируется.

SD>В полученном наборе может быть более чем один вариант конкретного предложения (тот самый случай с dog и god,
SD>в интернете же всякое можно найти, в том числе и "in the beginning dog created <...>"). Перебираем все возможные
SD>комбинации (с учётом того, что порядок предложений менять мы не можем) в поисках совпадения с конкретным текстом.
собака зарыта в том, что никто нам не обещал, что все три текста представлены в интернете. хотя таки да. они там есть. а неоднозначность расшифровки носит фундаментальный характер, т.к. шифрование с потерями. в конце-концов, в библии "оборотней" возможно полное соответветствие ветхому завету за тем исключением, что там везде собака. другими словами, предложенный мной и вами алгоритмы -- эвристика. строго алгоритма не существует, что элементарно доказывается. конечно, можно выдавать все возможные вариации декодирования, но их будет слишком много, особенно если учесть, что у бога могла быть собака и они работали вместе.

SD> Если таких совпаденй более одного, выводим все — ибо текст не может быть декодирован однозначно.
так ведь мы получаем дерево. кол-во неоднозначностей стремительно нарастает по мере углубления в текст. конечно, если выдавать неоднозначности в виде in-line списка [dog, god] created.... [dog, god] said... то на выходе будет один текст. если же генерировать текст по полной, то я не уверен, что он поместится на винчестер.

М>в этом случае вы вряд ли будете метить в группу прототипирования на питоне.

Да я ни в какую группу не собираюсь. Просто поясняю, что задание недоформулировано.

М>при условии, что отрывок есть

Если его нигде нет, как же вы планируете проверять правильность восстановления?

М>ИМХО вы тут слегка тупите. достаточно отсорировать словарные слова

Словаря же у нас нет. Что мы будем сортировать? Если бы словарь был, ваше решение бы имело смысл.

М>собака зарыта в том, что никто нам не обещал, что все три текста представлены в интернете

Тогда у задачи нет однозначного решения.

М>так ведь мы получаем дерево. кол-во неоднозначностей стремительно нарастает по мере углубления в текст. конечно, если выдавать неоднозначности в виде in-line списка [dog, god] created.... [dog, god] said... то на выходе будет один текст. если же генерировать текст по полной, то я не уверен, что он поместится на винчестер.

Если возможны такие неоднозначности, следует указать это в условиях задачи. Как минимум, что делать с ними.

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

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

A>>Сразу общий алгоритм в таком случае написать не получится.
ЖК>Извините, но в трудоустройстве вам отказано

Как работадатель вы потеряли уникального сотрудника

Здравствуйте, мыщъх, Вы писали:
М>в этом топике народ отказывается верить, что жизнь не малина и работодатели тащат через океан все, что работает. наш полк пополнился гарным украинским хлопцем, осевшим на соседнем хуторе в отделе быстрого прототипирования на питоне. показал финальное тестовое задание на которое отводился целый час времени. его оставили одного в комнате с лаптопом и сказали писать. а когда вернулись обратно, выяснилось, что он... играет на компьютере! потому что уже давно написал, отладил и помирал со скуки.
мне кажется в Америке проблема со школой. контроль качества сильно ниже. нет передачи опыта между поколениями разработчиков. старшие быстро отходят в менеджмент, не курируют младших, те в итоге пишут как бог на душу положит, вырастая так до старшего ничего слаще редьки не евшего. Например, большинство наученного в Америке народа считает, что "helper" — это такой очень мощный паттерн проектирования.
один супер старший программист из очень известной компании как-то мне всерьез сказал, что "для того, чтобы проект заработал нормально его нужно минимум 3 раза переписать". а глава нашего смертоносного отдела индусов на мои ревью жалуется, что "он, конечно, все правильно говорит, но внесение всех изменений согласно ревью сильно замедляет разработку. давайте мы будем все чекинить прямо, а потом когда-нибудь выделим дополнительное время и поправим".