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

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

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:

[sleeping-death.livejournal.com]

не-а. ноль?

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

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

[unbe.livejournal.com]

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

[sleeping-death.livejournal.com]

первое ноль - переходим на луп2 - 3 не обнулено.

[paracloud.livejournal.com]

Хотя, тонкость как подсказали выше - если требуется при сложении работать и с нулевыми аргументами.
Тогда, плюс две инструкции на обход циклов, если аргументы равны нулю:

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


[sleeping-death.livejournal.com]

баги? какие баги?))

[unbe.livejournal.com]

у меня - 3 не там обнуляю. У вас - не знаю, пока не нашёл, но должны же быть?

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

[paracloud.livejournal.com]

n_r_dreams успел подсказать первым :)

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

А что ноль?

[dims12.livejournal.com]

А, дошло.

[dims12.livejournal.com]

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

[avva.livejournal.com]

Вы наоборот поняли смысл инструкции J (вы и еще почти все остальные до сих пор). Сила шаблона!

[paracloud.livejournal.com]

Ноль багов - это тоже баги, неотрицательные, не так ли? ;)

[meshko.livejournal.com]

J 0,3, XZero

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

[paracloud.livejournal.com]

Ахаха, да, точно. При сравнении с нулём!

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

[(Anonymous)]

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

[meshko.livejournal.com]

Я зато первый это у себя заметил :)))

[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

[avva.livejournal.com]

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