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

[swizard]

Чёто вакансия вызвала интерес у удивительно малого количества народу, я даже затрудняюсь объяснить этот феномен :) Все так недолюбливают Эрланг? Но у меня же ещё 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 и давайте ссылку в комменты. Свой вариант я выложу ближе к концу недели.