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

[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]

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

[spamsink]

Я опубликовал ответ.

[kcmamu.livejournal.com]

Про 7 делается и умозрительно очевидным образом.

Сперва составляем схему из честных полусумматоров и полных сумматоров (A...L входы, Ui, Di, Qi внутренние переменные, относящиеся к разрядам единиц-двоек-четверок, {OO,QQ,DD,UU} выход):

{D1,U1} = HA(A,B)
{D2,U2} = FA(U1,C,D)
{D3,U3} = FA(U2,E,F)
{D4,U4} = FA(U3,G,H)
{D5,U5} = FA(U4,I,J)
{D6,UU} = FA(U5,K,L)
{Q1,D7} = HA(D1,D2)
{Q2,D8} = FA(D7,D3,D4)
{Q3,DD} = FA(D8,D5,D6)
{OO,QQ} = FA(Q1,Q2,Q3)

Теперь 1-й, 3-й и 5-й операторы расписываем отдельно для каждого выхода:

D1 = A&B
U1 = A^B
{D2,U2} = FA(U1,C,D)
D3 = MAJ(U2,E,F)
U3 = U2^E^F
{D4,U4} = FA(U3,G,H)
D5 = MAJ(U4,I,J)
U5 = U4^I^J
{D6,UU} = FA(U5,K,L)
{Q1,D7} = HA(D1,D2)
{Q2,D8} = FA(D7,D3,D4)
{Q3,DD} = FA(D8,D5,D6)
{OO,QQ} = FA(Q1,Q2,Q3)

И "вклеиваем" их туда, куда эти выходы подключаются:

{D2,U2} = FA(A^B,C,D)
{D4,U4} = FA(U2^E^F,G,H)
{D6,UU} = FA(U4^I^J,K,L)
{Q1,D7} = HA(A&B,D2)
{Q2,D8} = FA(D7,MAJ(U2,E,F),D4)
{Q3,DD} = FA(D8,MAJ(U4,I,J),D6)
{OO,QQ} = FA(Q1,Q2,Q3)

Получается 7 операций с 2 выходами и не более чем 5 входами.

[spamsink]

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

[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.
Понятно, что в более сложных случаях результаты одних функций придется передавать в качестве аргументов в другие функции, и т.д.

[rezkiy.livejournal.com]

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

[mtve.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-й, то есть формат немного недодуман]

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

[no more turtles (from livejournal.com)]

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

[spamsink]

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

[no more turtles (from livejournal.com)]

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

[spamsink]

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

[spamsink]

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

[ftdf.livejournal.com]

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

[spamsink]

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

[ftdf.livejournal.com]

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

[spamsink]

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