Алло, мы ищем логических дизайнеров!

[spamsink]

Октябрьская задачка на IBM Ponder This прямо как доктор прописал:

Нужно построить логическую цепь, вычисляющую сумму 12 однобитных значений, использовав минимальное число функций "5 бит -> 2 бита".

Пока рекорд, если верить количеству звездочек в списке решивших задачу, 6 функций (upd: раньше казалось, что 5, но там в одном месте в количестве звездочек была опечатка). ftdf столько может, и я тоже.

А кто сколько может? Кто из программистов может думать в терминах логических цепей?



Пусть 12 входных значений обозначены буквами A-L. Выходы будем обозначать, как это сделал kcmamu в своем решении из 7 функций, буквами U, D, Q, O для разряда единиц, двоек, четверок и восьмерок соответственно, и номером функции. UU, DD, QQ, OO - окончательные результаты.

Первым делом сложим (по модулю 4, с разрядом четверок разберемся позже) две группы по 5 входов:
{D1,U1} = A+B+C+D+E
{D2,U2} = F+G+H+I+J

Теперь как можно быстрее получим окончательное значение разряда единиц (тоже складывая по модулю 4):

{D3,UU} = U1+U2+K+L

Осталось сложить D1, D2, D3 и соответствующие разряды четверок ("Q1", "Q2" и "Q3"), которые нужно как-то образовать.
Заметим, что при сложении 5 однобитных значений для получения разряда четверок достаточно посмотреть на значение суммы по модулю 4 (S) и на два любых входных значения: если S = 2 или S = 3, то разряд четверок гарантированно 0; если S = 0, то достаточно посмотреть на любые 2 входных бита, чтобы отличить 0 от 4 - хотя бы один из них должен быть равен единице, чтобы в результате было 4; если S = 1, то тоже достаточно посмотреть на любые 2 входных бита, чтобы отличить 1 от 5 - оба должны быть равны единице, чтобы в результате было 5. Таким образом, нужно всего 4 входа для получения разряда четверок при суммировании 5 бит, т.е. Qx=f(Dx, Ux, Y, Z), где Y и Z - любые 2 входа при вычислении {Dx,Ux}. Подчеркнём, что Qx и Dx не могут быть равны единице одновременно.

Тогда, виртуальное Q1 (функцию, зависящую от D1, U1 и любых двух входов первой суммы, пусть A и B) можно сложить с D1 (которое уже есть на входе) и с D3 (пятым входом) с помощью одной функции. В результате переноса в третий бит не возникнет, т.к. Q1 и D1 не могут быть равны единице одновременно (это от меня при решении в уме ускользнуло).

{Q4, D4} = 2*"Q1" + D1 + D3, где Q1 = f(D1, U1, A, B)

Осталось сложить D2, D4, "Q2" и "Q3". С Q2, D2 и D4 поступаем аналогично:

{Q5, DD} = 2*"Q2" + D2 + D4, где Q2 = f(D2, U2, F, G)

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

Осталось сложить "Q3", Q4 и Q5. "Q3" получилось в результате суммирования не пяти, а четырех бит, поэтому для того, чтобы Q3 было единице, D3 и UU должны быть равны нулю, а любой произвольный входной бит - единице. Это можно записать и как Q3 = f(D3, UU, U1, 0).

{OO, QQ} = "Q3" + Q4 + Q5, где Q3 = f(D3, UU, U1, 0).

(Описанное решение принадлежит ftdf, мое решение начинается с
{D1,U1} = A+B+(C^D^E)
{D2,U2} = F+G+(H^I^J)
т.е. пользуется разрывом трехбитных сумматоров на две части, как у kcmamu)

Comments

[maksa.livejournal.com]

10 минут ушло на понимание задачи.

Я правильно догадался, что это надо на компьютере решать?

[spamsink]

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

9 функций делается в лоб; чтобы получить из них 8, нужен некий трюк.

[maksa.livejournal.com]

Эх. В другой жизни этим займусь. )

[spamsink]

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

[rezkiy.livejournal.com]

а я вообще так и не понял.

[spamsink]

Рассмотрим простейший пример - сложение трех бит:
bool a1, a2, a3;
В результате должно получиться число в диапазоне от 0 до 3, представимое в виде 2 бит.
bool res_h, res_l;

Младший бит - это бит четности суммы:
res_l = a1 ^ a2 ^ a3;

Старший бит равен 1 только в том случае, если сумма не менее 2, т.е. если как минимум 2 бита истинны одновременно.
res_h = a1&a2 | a2&a3 | a3&a1;

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

pair<bool, bool> f(bool a1, bool a2, bool a3) {
    return make_pair(a1&a2 | a2&a3 | a3&a1, a1 ^ a2 ^ a3);
}

Задача же стоит - реализовать сложение 12 бит, получив в результате 4 бита, с помощью не более чем 9 вызовов функций вида
pair<bool, bool> f(bool a1, bool a2, bool a3, bool a4, bool a5)

Естественно, внутренности функции могут быть любые, например, сумму 5 бит можно представить двумя функциями как

pair<bool, bool> f1(bool a1, bool a2, bool a3, bool a4, bool a5) {
    int sum = 0 + a1 + a2 + a3 + a4 + a5;
    return make_pair<bool, bool>(sum & 2, sum & 1);
}
pair<bool, bool> f2(bool a1, bool a2, bool a3, bool a4, bool a5) {
    int sum = 0 + a1 + a2 + a3 + a4 + a5;
    return make_pair<bool, bool>(sum & 4, false);
}
Результатом будет f2(...).first, f1(...).first, f1(...).second.
Понятно, что в более сложных случаях результаты одних функций придется передавать в качестве аргументов в другие функции, и т.д.

[mtve.livejournal.com]

очень коряво у них сформулировано, "надо мягше"...

например, считаются разные функции или кол-во использованных функций?

[rezkiy.livejournal.com]

так, жесткач, завтра буду пытаться вникнуть. Спасибо за попытку объяснить!

[spamsink]

Количество. А как было бы лучше, и чтобы без хардверного жаргона?

[mtve.livejournal.com]

Мне было бы понятней как-то так:

"Есть булевы функции, n бит на входе, m бит на выходе, назовём их n->m.

Закодируем такую функцию в виде перечня входов, и значений выходов для всех вариантов входов.

Например, если n=3 и m=2, то для трёх входов a, b и c будет 8 вариантов их значений (000, 001 и т.д.), и для всех вариантов входов можно закодировать выходы как какие-то значения функции (например 00, 10, 01, ...) десятичным цифрами, тем самым представить такую функцию можно в виде abc02113302 (где 0 это 00, 2 это 10, и т.д.). Первый бит является самым старшим.

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

Например, [тут описание примера с компаратором]
acd02113302
bef21133123
7 8

Задача: нужно из нескольких произвольных функций 5->2 составить функцию 12->4, которая бы вычисляла сумму входных значений, то есть сделать сумматор. Чем меньше используется функций 5->2 тем лучше, их должно быть не больше 9.

Формат: [тут чёткое описание в каком формате присылать решения]"

И, кстати, когда функций больше 8, то строчных английских букв для выходов не хватит, если например в 9-й функции использовать результаты 8-й, то есть формат немного недодуман]

[mtve.livejournal.com]

хотя наверное нет, снимаются все возражения. если такой тупой что не понял задачи, незачем и соваться)

[spamsink]

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

И, кстати, когда функций больше 8, то строчных английских букв для выходов не хватит, если например в 9-й функции использовать результаты 8-й, то есть формат немного недодуман]

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

[mtve.livejournal.com]

Думаю что верифицируют ответ они всё-таки формально.

Это интересная и сложная хорошая задача. Просто странное описание иногда отталкивает, возникает ощущение снобизма у авторов "догадайся что мы имели в виду". Без Вашей наводки, например, в эту - я даже не стал бы вчитываться, ещё раз спасибо.

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

[spamsink]

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

Я теперь жду-не дождусь увидеть ответы из 5 и 6 функций.

[no more turtles (from livejournal.com)]

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

[spamsink]

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

[no more turtles (from livejournal.com)]

pyevolve позволяет такое примерно за полчасика реализовать. Все же проще чем в уме варианты гонять ;)

[spamsink]

Геном описать не проблема, но неясно, какая должна быть оценочная функция. То ли количество правильных результатов из всех 4096 возможных, то ли сумма модулей или квадратов разностей между каждым полученным и ожидаемым результатом, то ли еще что-нибудь. Если у вас есть полчасика, можете попробовать.

[spamsink]

За часик я написал прототип с нуля на С++, и пока он у меня быстро добегает примерно до 35% правильных результатов и задумывается. На ночь вот оставлю, утром посмотрю.

[no more turtles (from livejournal.com)]

> За часик я написал прототип с нуля на С++
Вы просто монстр какой-то ;) А я вот даже полчасика не нашел. Может на выходных руки дойдут.

Кстати может на плюсах даже лучше, потому как считает раз в 5 примерно быстрее чем питон. Я когда-то с сишной библиотекой работал, она тоже была неплоха, но на скорую руку, там труднее было.

[spamsink]

Ничего хорошего за ночь не вышло (мой С++ гораздо лучше, чем мое генетическое программирование).
Сегодня я попробовал начать с простого: искать функцию сложения трех бит с получением двух бит результата - это находится, а вот сложение 5 бит с получением 3 бит результата с помощью двух функций уже не находится - затыкается на 24 из 32 правильных результатов. Аналогично, 7->3 с помощью 3 функций (это несложно делается руками) затыкается на 80 из 128.

[ftdf.livejournal.com]

Я пока придумал 8, не совсем понимаю, как сделать меньше. Надо думать :)

[spamsink]

Попробуй для тренировки сделать 7->3 тремя элементами.

[ftdf.livejournal.com]

Для тренировки сделал, это было более-менее очевидно.

[spamsink]

Тебе явно пришлось воспользоваться каким-то способом area recovery. Нужно напридумывать несколько таких способов для разных комбинаций входов.