?

Log in

No account? Create an account
 

Задачка для интересу - swizard

About Задачка для интересу

Previous Entry Задачка для интересу 19 апр, 2016 @ 00:38 Next Entry
Чёто вакансия вызвала интерес у удивительно малого количества народу, я даже затрудняюсь объяснить этот феномен :) Все так недолюбливают Эрланг? Но у меня же ещё Elm и Rust, и вообще, потенциально определённая свобода в этом плане. Пишите, когда ещё вам предложат попрограммировать с пользой на чём-то неунылом за деньги :)

Для подогрева интереса к вакансии выкладываю тестовую задачку для потенциальных кандидатов. А то чё я её зря что ли придумывал.
UPD 2016-04-20: добавил "sample_9".
UPD 2016-04-21: пофиксил рефенсные тайминги.

Итак, задачка из трёх частей, в порядке увеличения сложности. Делать надо на эрланге, если умеете эрланг, или на чём угодно, если не умеете. Ориентировочные критерии оценки такие:
  • Если человек сделал первую часть, то хорошо: с ним уже есть о чём говорить.
  • Если получилась вторая — очень хорошо.
  • Если третья — совсем круто!

Общее условие

Дана программа в виде упрощённого S-expression (что это?), например:

sample_1() -> <<"(+ (* 4 4) (* 2 (- 7 5)) 1)">>.

где первый элемент каждого списка — это операция (всего их три вида):
  1. сложение: атом "+"
  2. вычитание: атом "-"
  3. умножение: атом "*"
Все остальные возможные атомы — это целые числа.
Ещё примеры:

sample_2() -> <<"10">>.
sample_3() -> <<"(* 10 (- 0 1))">>.
sample_4() -> <<"(- (+ 10 10) -5 0)">>.
sample_5() -> <<"(+ (- (* (+ (- (* 1))))))">>.
sample_6() -> <<"(* 2 (+ (- 10 9) (- 3 (* 2 1))) (+ (- 10 9) (- 3 (* 2 1))))">>.
sample_7() -> <<"(+ (* 2 1) (+ 8 8) (- (+ 4 3 2 1) (* 3 3) (* 2 2)) (* 5 7))">>.
sample_8() -> <<"(- (+ (+ 3 3) (- 3 3) (+ 3 3) (- 3 3)) (* 2 2))">>.
sample_9() -> <<"(+ (- 6 1) (+ 0 1 1) (- 7 2) (* 3 4 5) (- 3 1) (+ 2) (- 0 10))">>.

Задача 1

Реализуйте функцию-интерпретатор "interpret/1" и вычислите результаты вышеприведённых программ.

Например:
interpret(sample_1()). --> 21
interpret(sample_2()). --> 10
interpret(sample_3()). --> -10
interpret(sample_4()). --> 25
interpret(sample_5()). --> 1
interpret(sample_6()). --> 8
interpret(sample_7()). --> 50
interpret(sample_8()). --> 8
interpret(sample_9()). --> 66

Задача 2

Представим, что все операции в программе имеют константную задержку, которая не зависит от процессора. Например, это некоторого рода длительная сетевая активность.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)":
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_network/1", которая вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_network(sample_1()). --> 21 (delay 15 s)
interpret_network(sample_2()). --> 10 (delay 0 s)
interpret_network(sample_3()). --> -10 (delay 13 s)
interpret_network(sample_4()). --> 25 (delay 5 s)
interpret_network(sample_5()). --> 1 (delay 30 s)
interpret_network(sample_6()). --> 8 (delay 25 s)
interpret_network(sample_7()). --> 50 (delay 15 s)
interpret_network(sample_8()). --> 8 (delay 13 s)
interpret_network(sample_9()). --> 66 (delay 12 s)

Задача 3

Представим, что все операции в программе имеют константную задержку, которая зависит от процессора. Например, это некоторого рода тяжелые вычисления, выедающие 100% ядра процессора.
Наша машина оборудована N физическими ядрами.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)", при этом максимальное количество "одновременно выполняющихся" операций должно быть меньше или равно N:
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_cpu/2", которая, используя процессор максимально оптимальным образом, вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_cpu(sample_1(), 2). --> 21 (delay 15 s)
interpret_cpu(sample_2(), 2). --> 10 (delay 0 s)
interpret_cpu(sample_3(), 2). --> -10 (delay 13 s)
interpret_cpu(sample_4(), 2). --> 25 (delay 5 s)
interpret_cpu(sample_5(), 2). --> 1 (delay 30 s)
interpret_cpu(sample_6(), 2). --> 8 (delay 28 s)
interpret_cpu(sample_6(), 3). --> 8 (delay 25 s)
interpret_cpu(sample_7(), 2). --> 50 (delay 26 s)
interpret_cpu(sample_7(), 3). --> 50 (delay 22 s)
interpret_cpu(sample_7(), 4). --> 50 (delay 15 s)
interpret_cpu(sample_8(), 2). --> 8 (delay 15 s)
interpret_cpu(sample_8(), 3). --> 8 (delay 13 s)
interpret_cpu(sample_9(), 2). --> 66 (delay 15 s)


Приглашаю всех желающих порешать, код выкладывайте на какой-нибудь gist и давайте ссылку в комменты. Свой вариант я выложу ближе к концу недели.
Оставить комментарий
From:(Anonymous)
Date:Апрель, 18, 2016 21:51 (UTC)
(Link)
> я даже затрудняюсь объяснить этот феномен

Возиться с проприетарщиной в 21 веке? Фи. Это ж даже в резюме потом толком не включишь - работал на хрен пойми кого делал не пойми что. Оно мне надо?
[User Picture Icon]
From:nponeccop
Date:Апрель, 18, 2016 21:57 (UTC)
(Link)
Ну это зависит от. Я знаю места, в которых считают что опенсорс говно и не нужен (только стек от вендоров, типа MS и IBM), и использование программистом опенсорсового стека (условно, gcc и всего собранного с его участием) считается проклятьем в резюме. Я уж не говорю об участии кандидата в опенсорс-проектах.
[User Picture Icon]
From:thesz
Date:Апрель, 18, 2016 22:03 (UTC)
(Link)
Так Эрланг это скучно.

Совершать раз за разом одни и те же ошибки, "защищаясь" от них OTP - что в этом интересного?
[User Picture Icon]
From:swizard
Date:Апрель, 18, 2016 22:30 (UTC)
(Link)
Ну эрланг в любом случае нужен в данной ситуации, потому что мне нужно передать проект, и его уже слишком накладно переписывать на что-то другое (если это вообще имеет смысл, в чём я сомневаюсь).

В любых других задачах разумная свобода: можно использовать любой целесообразный задаче инструмент (хоть хаскель), главное, чтобы его использование было объективно оправдано.
Я так принёс в репо elm и rust.
From:dmzlj
Date:Апрель, 19, 2016 03:10 (UTC)
(Link)
О, Elm. Вы его правда используете? Его можно в продакшн?
[User Picture Icon]
From:swizard
Date:Апрель, 19, 2016 13:18 (UTC)
(Link)
Правда используем, с cowboy'ем на бекенде, через websockets.

Я не вижу препятствий использовать его в продакшне: он существенно проще того же purescript, там просто нечему ломаться :)
(Удалённый комментарий)
[User Picture Icon]
From:swizard
Date:Апрель, 19, 2016 13:21 (UTC)
(Link)
Теоретически, наверно, и удалёнку можно рассмотреть. Но надо понимать, что (при прочих равных) преимущество будет у территориально более близкого кандидата :(
[User Picture Icon]
From:quadium
Date:Апрель, 19, 2016 09:56 (UTC)
(Link)
Я не соискатель, но первую "задачку для интересу" быстренько соорудил на перле.
https://gist.github.com/anonymous/2f7adbb7fc3e96ff6850e279c420d928
[User Picture Icon]
From:swizard
Date:Апрель, 19, 2016 13:30 (UTC)
(Link)
Ну как-то так, да. Хотя на перле я бы что-нибудь веселее сделал: например, раз ты там всё равно используешь eval, можно было бы не строить сначала ast, а сразу регулярками исходную программу превратить в валидный perl :)

Попробуй вторую часть, она интереснее.
From:tancorko
Date:Апрель, 19, 2016 12:57 (UTC)
(Link)
Первую накидал.
https://gist.github.com/yury-pachin/fca00489bc25621aecbaf6b961ef5740
Во вторую как-то не въехал.
[User Picture Icon]
From:worm_ii
Date:Апрель, 19, 2016 13:04 (UTC)
(Link)
Я тоже не соискатель, но заинтересовала 2-я задача, конкретно, вот эта строчка:

interpret_network(sample_8()). --> 8 (delay 13 s)

За счёт чего достигается такая маленькая задержка? Правильно ли я понимаю, что здесь допускается кэширование ранее вычисленных результатов (которое работает не только внутри функции interpret_network, но и глобально, между их вызовами)?
From:(Anonymous)
Date:Апрель, 19, 2016 13:21 (UTC)
(Link)
2*2 за 10, внешний минус за 3, итого 13 и надо за <=10 посчитать (+ (+ 3 3) (- 3 3) (+ 3 3) (- 3 3)), а оно считается за 3+2+2+2=9<10

а вообще изи у вас задачки какие-то
[User Picture Icon]
From:theiced
Date:Апрель, 19, 2016 14:45 (UTC)
(Link)
первая часть: (eval sexp) :]
From:fshashin
Date:Апрель, 20, 2016 01:12 (UTC)
(Link)
А вот вам в бочку изящных функциональных решений ложечку наколеночного однопроходного императивного кода:

Задача раз: https://www.dropbox.com/s/8gm3cxtu2s75mhe/task1.py?dl=0
Задача два: https://www.dropbox.com/s/c8nu21otjygo9ps/task2.py?dl=0
Задача три: а аналитическое решение у неё есть?

Edited at 2016-04-20 01:24 (UTC)
[User Picture Icon]
From:theiced
Date:Апрель, 20, 2016 08:21 (UTC)
(Link)
есть конечно. это оптимизация гант чарта в чистом виде.
[User Picture Icon]
From:kodt_rsdn
Date:Апрель, 20, 2016 11:45 (UTC)
(Link)
Первые две задачки решил как одну
На питоне, с использованием хака - распарсил выражение средствами питона.

https://bitbucket.org/nickolaym/swizardcontest/src/922578464955950e023e5d95ee894ede465c1ed3/swizardcalc.py?at=master&fileviewer=file-view-default

последнюю задачку - тут надо подумать: она NP-полная, можно для прикола устроить полный перебор, но лучше бы сперва задуматься об эвристиках.
From:fshashin
Date:Апрель, 20, 2016 13:14 (UTC)
(Link)
А вот и задача 3 в суровом императивном исполнении с возможность вывода оптимального плана загрузки ядер: https://www.dropbox.com/s/fzwgkvh7khiplgu/task3.py?dl=0

Задачи годные, мне понравилось, спасибо!

Пойду учить Erlang c Rust-ом и писать резюме.

Edited at 2016-04-20 13:35 (UTC)
[User Picture Icon]
From:swizard
Date:Апрель, 20, 2016 13:51 (UTC)
(Link)
Очень круто, молодец :)

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

Смотри, я там добавил в условие ещё один пример: "sample_9". Твой планировщик для двух ядер на нём составил расписание в 16 секунд, раскидав на одно ядро все вычитания, а на другое сложение и умножение. Но там же можно положить три вычитания и два сложения на одно ядро, и умножение и вычитание на второе — тогда общее расписание будет в 15 секунд.
Re: Про NP - (Анонимно) Развернуть
[User Picture Icon]
From:nponeccop
Date:Апрель, 20, 2016 19:29 (UTC)

Чисто поржать

(Link)
http://nponeccop.livejournal.com/483389.html - компиляция в Makefile прокатит? Результаты там посчитать мейкфайлом тоже тривиально
[User Picture Icon]
From:nponeccop
Date:Апрель, 21, 2016 02:57 (UTC)

типа-акторы на ноде

(Link)
https://gist.github.com/nponeccop/9de969e517a336559fd7de9d6ba20ed9

Такое решение как я понимаю требовалось для 2-й и 3-й задач? Или всё же вариант thesz?

Edited at 2016-04-21 03:20 (UTC)
[User Picture Icon]
From:swizard
Date:Апрель, 21, 2016 12:03 (UTC)

Re: типа-акторы на ноде

(Link)
Да, всё правильно. На футурах тоже всё красиво должно выглядеть.
Вариант thesz опционален для некандидатов и для языков, где нет акторов/футуров/зелёных тредов (ну или мучительно ими пользоваться).

Только я не очень понял у тебя в коде, он для (+ 1 2 3) на 2 секунды заснёт, или на 4?
From:(Anonymous)
Date:Апрель, 21, 2016 07:57 (UTC)

Еще решение на Erlang

(Link)
https://gist.github.com/ciiol/4b364e5dd4c3a98e70775749b7e677fb

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

К слову об оптимальности и аналитическом решении. Простая стратегия lifo в шедулере , для "interpret_cpu(sample_7(), 2)" дает 26 секунд, а не 27, как в примере.
[User Picture Icon]
From:swizard
Date:Апрель, 21, 2016 12:13 (UTC)

Re: Еще решение на Erlang

(Link)
Круто выглядит. Судя по-всему, у вас большой опыт работы с эрлангом.

Перебором тоже подойдёт, его ведь, на самом деле, тоже ни разу не тривиально запрограммировать :)

C таймингом на "sample_7()" меня уже пристыдили — я поправил числа в условии.
From:(Anonymous)
Date:Март, 9, 2017 12:17 (UTC)

My supplementary website

(Link)
My new blog project
war game online ШіЩѓШіЩЉ ЩѕЩ€Ш±Щ† plus size pantys
http://sissyabuse.blogporn.in/?view.devin
adult toy party to my aunt sissy feminization video hormone treatment for prostate cancer free gay hentai fashion accessories women estrogen breast cream plate frames
(Оставить комментарий)
Top of Page Разработано LiveJournal.com