сложить два числа (программистское)

[avva]

Забавная задачка из блога Джона Грэма-Камминга. Он пишет, что ему ее задали на вступительном экзамене на компьютерный факультет
в Оксфорде в 1980-х.

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

У машины есть три инструкции следующего вида:

Z n - обнулить ячейку n
I n - увеличить на 1 содержимое ячейки n
J n,m,стрелка - сравнить ячейки n и m, и если их содержимое различается, то прыгнуть на инструкцию, на которую указывает стрелка (вместо стрелки в тексте можно использовать метки или номера инструкций).

Программа состоит из последовательности инструкций (с метками/номерами). Программа останавливается, когда закончились инструкции. Например, следующая программа копирует в ячейку 0 содержимое ячейки 20 (предполагая, что оно больше нуля), а потом останавливается. Если в ячейке 20 лежит отрицательное число, она никогда не остановится.

Z 0
loop:
I 0
J 0, 20 -> loop

Задание: написать программу, которая складывает два числа. Перед запуском программы числа помещаются в ячейки 0 и 1. В конце работы программы сумма должна лежать в ячейке 2. Про числа известно, что они целые неотрицательные.

Эта задача не будет сложной для опытного программиста, но есть некоторые тонкости. Интересно также посмотреть, как ее можно сделать покороче. Я справился за 16 инструкций.

Update: несколько типичных ошибок: 1) не прочитали внимательно, что делает инструкция J; 2) не работает, когда один из аргументов 0; 3) не работает, когда оба аргумента 0.

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

Comments

[n-r-dreams.livejournal.com]

//кто что, а тестировщик как всегда...
«Если в ячейке 20 лежит отрицательное число, она никогда не остановится.»
Простите, но неположительное, а не отрицательное.

[paracloud.livejournal.com]

Интересно, что там за тонкости и какое решение в 16 инструкций.
У меня получилось 7 инструкций (три чтобы положить в ячейку 2 копию 0, используя пример выше, четыре чтобы добавить туда же столько инкрементов, сколько задано яцейкой 1, используя память 3 как дополнительный счётчик:

Z 2
loop_0:
I 2
J 2, 0 -> loop_0
Z 3
loop_1:
I 2
I 3
J 3, 1 -> loop_1


[sleeping-death.livejournal.com]

не-а. ноль?

[sleeping-death.livejournal.com]

Z 2
Z 3
J 0,3, XZero
L1:
I 2
J 0,2,L1
XZero:
J 1,3,YZero
L2:
I 2
I 3
J 1,3,L2
YZero:

[meshko.livejournal.com]

J 0,3, XZero

перейдет если первое число не 0 и мы его не прибавим

[unbe.livejournal.com]

Z 2
J 2, 0 -> loop2:
loop1:
I 2
J 2, 0 -> loop1
Z 3
J 3, 1 -> end
loop2:
I 2
I 3
J 3, 1 -> loop2
end:

[unbe.livejournal.com]

баги %)
У sleeping_death выше идея та же, но багов меньше.

Z 2

[loqva.livejournal.com]

Z 2
Z 3 // make a counter
J 0,2 ->add1 // Is @0 == 0?
loop: I 2
J 0,2 -> loop
// copied @0 to @2
add1: J 1 3->end // Is @1 ==0?
loop2: I 2
I 3
J 1,3 ->loop2
end: Z 3 // just the end label

[gianthare.livejournal.com]

14 если не требовать команды на сетке end, иначе там можно поставить nop == J 0,0,end
Плюс одна запорченная ячейка номер 3

Z 2
Z3
J 0,2 -> L0 // m_0 <> 0
J 1,2 -> L1 // m_1 <> 0
I 3
J 2,3 -> end // both are zero
L0: I 2 // copy m_0 to m_2
J 0,2,l0
J 1,3 -> L1 // m_1 <> 0
I 3
J 1,3 -> end // m_1 is zero
L1: I 2 // move m_1 to m_2 using m_3 as counter
I 3
J 1,3,l1
End:

[avva.livejournal.com]

Команда на сетке end необходима, прыжок всегда на инструкцию.
Кажется, действительно сэкономил одну инструкцию по сравнению с моей версией, браво :)

[dims12.livejournal.com]

У меня получилось так:

        Z 2
loop1:  I 2
        J 2, 0, loop1
loop2:  Z 3
        I 2
        I 3
        J 1, 3, loop2

[dims12.livejournal.com]

Да, ступил с нулями.

О нет, только не это.

[(Anonymous)]

Чтобы я после рабочего дня ещё этим занимался... Мои мозги это жалкая раздавленная работой лепёшка. Спать.

[toshick.livejournal.com]

по-моему, многие не прочитали, что условие перехода - неравенство, а не равенство операндов
13 инструкций:

Z 2
Z 3 -- буфер цикла
Z 4
I 4 -- гарантированная единица для безусловного перехода

J 0 2 loop1 -- если X0 <> 0, идем суммировать
J 3 4 end1 -- иначе goto end1

Loop1:
I 2 -- поединично переносим X0 в ячейку 2
J 0 2 loop1 -- ячейка 2 - переменная цикла

end1:
J 1 3 loop2 -- если X1 <> 0, идем суммировать
J 3 4 end2 -- иначе goto end2

Loop2:
I 2 -- суммируем в ячейке 2
I 3 -- увеличиваем переменную цикла
J 1 3 loop2 -- ячейка 3 - переменная цикла
end2: -- все

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

[dims12.livejournal.com]

Лично я прочитал, что делает инструкция, просто ступил, что инкремент один раз выполняется в любом случае

[gul-kiev.livejournal.com]

У меня получилось 13.
Ну или 14, если переход всегда должен быть на какую-то инструкцию.

Z 2
Z 4
I 4
J 2 0 l1
J 4 0 l2
l1:
I 2
J 2 0 l1
l2:
Z 3
J 3 1 l3
J 4 1 l4
l3:
I 2
I 3
J 3 1 l3
l4:

[spamsink.livejournal.com]

Более интересной представляется следующая задачка:
Определить, чему равно неопределенное число в ячейке 0, занеся абсолютное значение в ячейку 1, а знак - в ячейку 2.

[avva.livejournal.com]

Притом, что числа неограниченные, да?

Отличное задание! Я вижу в общих чертах, как... надо подумать и написать.

[dims12.livejournal.com]

А вот так?

        Z 3
        Z 2
do2:    I 3
do1:    I 2
        J 2, 3, loop
        Z 3
        Z 2
loop:   J 0, 2, do1
        J 1, 2, do2

думаю...

(нифига)

[gegmopo4.livejournal.com]

11.

    Z 2
    Z 3
    I 3
    J 2, 3 -> b
a:  I 2
b:  J 0, 2 -> a
    Z 4
    J 4, 3 -> d
c:  I 2
    I 4
d:  J 1, 4 -> c

Не ясно, можно ли изменить значения в ячейках 0 и 1. Если можно, возможно есть короче решение.

[unbe.livejournal.com]

А вот это неплохо.

[n-r-dreams.livejournal.com]

Z 2
Z 3
J 0, 3 -> lbl2 //if [0]!=0
lbl1:
J 1, 3 -> lbl3 //if [1]!=0
I 3
J 1, 3 -> lbl4
lbl2:
I 2
J 0, 2 -> lbl2
J 3, 2 -> lbl1
lbl3:
I 2
I 3
J 1, 3 -> lbl3
lbl4:
Z 3

Тоже 14. Помогите найти контрпример, я не верю, что оно работает :)

[meshko.livejournal.com]

;
; Copyright (C) GOLDSOFT Ltd
;
; вроде 15
;
Z 2
Z 3
Z 4
I 4
J 0,3 -> add1 ; JNE
J 3, 4 -> check2 ; JMP
add1:
I 2
I 3
J 0, 3 -> add1 ; JNE
check2:
Z 3
J 1, 3 -> add2 ; JNE
J 3, 4 -> done ; JMP
add2:
I 2
I 3
J 1, 3 -> add2 ; JNE
done:

[radiognome.livejournal.com]

Если не считать метки, то получается вроде бы 15
add1:
Z 2
Z 3
J 0, 2 -> loop1
I 3
J 0, 3 -> add2

loop1:
I 2
Z 0, 2 -> loop1

add2:
Z 3
Z 4
J 1, 3 -> loop2
I 4
Z 1, 4 -> end

loop2:
I 2
I 3
Z 1, 3 -> loop2

end:

7 instructions!

[igorlord.livejournal.com]

Z 2
J 1 2 -> tst0
inc02:
I 0
I 2
J 1 2 -> inc02
inc2:
I 2
tst0:
J 0 2 -> inc2

RE: 7 instructions!

[meshko.livejournal.com]

OMG.
(but... I think while the idea is awesome, the first check is wrong? "J 1 2 -> test0" is trying to skip if 2nd number is 0, but it's the same JE vs JNE confusion everyone is having? no?)

[alexeybobkov]

Вроде так? ("//" означает комментарий, само собой.)

Z 2

J 0, 2 -> label0

// m(0) == 0
J 1, 2 -> label3

// m(0) == 0, m(1) == 0
I 0
J 0, 2 -> end

// m(0) != 0
label0:
J 1, 2 -> label2

// m(0) != 0, m(1) == 0
label1:
I 2
J 0, 2 -> label1
J 0, 1 -> end

// m(0) != 0, m(1) != 0
label2:
I 2
J 0, 2 -> label2
Z 0

// m(0) == 0, m(1) != 0
label3:
I 2
I 0
J 1, 0 -> label3

end:

[alexeybobkov]

А, прочитал, что в конце должна быть ещё одна инструкция. Значит, тоже 16.

9 instructions

[igorlord.livejournal.com]

Z 2
J 1 2 -> inc02

I 1
J 1 2 -> tst0

inc02:
I 0
I 2
J 1 2 -> inc02

inc2:
I 2
tst0:
J 0 2 -> inc2

Re: 9 instructions

[tasmanj.livejournal.com]

Вроде работает, круто!

[pharmazevt.livejournal.com]

Осознал насчет нулей, попытка 2.
Если да, то вот: 

1. Z 2 
2. Z 3 
3. I 4 это хитрый способ сделать не ноль в яч. 4, чтоб из середины можно было прыгнуть сразу в конец
4.J 1,3 --> 7 если второе число не ноль
5. J 0,3 --> 10 если первое число не ноль
6. J 2,4 -->11 так как в яч. 2 ноль, а яч. 4 не ноль, в случае нулей в 1 и 2 прыгаем на инструкцию 11
7. I 0 добавляем единицу к первому числу
8. I 3 добавляем единицу к счетчику.
9. J 1,3 --> 7 пока счетчик не сравняется со вторым числом (которое не ноль)
10. I 2 добавляем единицу в ячейку результата (который не ноль)
11. J 0,2 --> 10 если прыгнули с 6-й строчки, в яч. 0 и 2 одно и то же (ноль), стоп; если прыгнули с 5-й строчки, продолжаем добавлять, пока не будет равно. 

Годится?

[pilpilon.livejournal.com]

Z 2
Z 3
Z 4
I 3
J 2, 3 -> begin
loop1:
I 1
I 2
begin:
J 0, 2 -> loop1
J 3, 4 -> cont
loop2:
I 2
cont:
J 1, 2 -> loop2

9

[shtangen]

Z2
Z3
I3
J2,3 -> g3
g1: I0
g2: I2
g3: J1,2 -> g1
I1
J0,2 -> g2

Re: 9

[i-grigoriev.livejournal.com]

Кажется, не работает, когда равно нулю 2-е слагаемое.

[molnij.livejournal.com]

В лоб за 15, слегка сократив - за 14
Z 4
I 4

Z 2
Z 3

J 0 2 -> loop1
J 2 4 -> p2
loop1:
I 2
J 0 2 -> loop1

p2:
J 1 3 ->loop2
J 3 4 ->p3
loop2:
I 2
I 3
J 1 3 ->loop2
p3:
zzz

[malyj-gorgan.livejournal.com]

Наверняка, уже есть, но на всякий случай:
Z2
loop:
I2
J 0,2,loopA
Z3
loopB:
I3
I2
J1,3,loopB

Семь инструкций, две метки

[malyj-gorgan.livejournal.com]

Блин, "неотрицательные" прочитал как "положительные", тормоз :(