Little Man Computer Code Golf

MartinBraendli

@chopper100 created a great implementation of the Little Man Computer. For those who don't know LMC (like me about 2 hours ago), it is basically a very simple machine language with its own assembly language. More on wikipedia, worth a read.

To make use of choppers project, I challenge you to some Code Golf.

Rules:
- Write a program in choppers LMC, that gives you the n-th number of the fibonacci sequence for any given n.
- The program should take exactly 1 input and return exactly 1 output. The I/O relation should be:

0 => 0  
1 => 1
2 => 1
3 => 2
4 => 3
...
16 => 987

- values bigger than 17 dont have to give the right output (so dont worry about overflow).
- Winner is, who ever can achieve this with the fewest lines of code.

Pro tip: Use a external text editor for writing code and import it into the “Program” list, then press the green flag to update. Its quite hard to change code with the “built in” editor.

My best mark is 19 lines of code, but i think everything below 25 is quite good.

PS: Feel free to post your own challenge here!

EDIT: Wikipedia article linked
EDIT2: Protip

Last edited by MartinBraendli (Oct. 17, 2015 02:25:37)

Check out my newest project:
Photorealistic 3d Renderer

iamunknown2

function(x){z=0;y=1;n=1;for(i=0;i<x;i++){z=y;y=x;x=y+z};return(y)}

Probably doesn't work, haven't tested

Edit: Edited code. Didn't work.
Edit: I give up.

Last edited by iamunknown2 (Oct. 17, 2015 13:43:39)

| My website | Using Geany | A Christian | Running Ubuntu MATE 14.04 with Flash 18.0 (release 0) | Search this with quotation marks on Google to view my posts: “ellipsepostpianolizard” (some posts may not show up) |

Moving on from Scratch? Learn Python/a scripting language (e.g Perl, JavaScript), then move on to a C derivative

MartinBraendli

iamunknown2 wrote:
function(x){z=0;y=1;n=1;for(i=0;i<x;i++){z=y;y=x;x=y+z};return(y)}
Probably doesn't work, haven't tested
Edit: Edited code. Didn't work.
Edit: I give up.

This isnt LMC. LMC Assembly looks something like

INP
STA N
LOOP LDA A
SUB N
BRP ENDLOOP
LDA A

Go to the linked project and try to understand the default code first (it calculates the product of 2 integers). Programming Machine Code/ Assembly might be hard at first, but its not much harder than high level languages. Programming in Assembly also helps you to understand, how a Computer works.

Check out my newest project:
Photorealistic 3d Renderer

MegaApuTurkUltra

Yay, 27 25 22 lines

        INP
        SUB ONE
START   SUB ONE
        BRZ QUIT
        STA COUNTER
        BRP LOOP0
QUIT    LDA CURRENT
        OUT
        HLT
LOOP0   LDA CURRENT
        STA TEMP
        ADD OLD
        STA CURRENT
        LDA TEMP
        STA OLD
        LDA COUNTER
        BRA START
COUNTER DAT
OLD     DAT 1
CURRENT DAT 1
TEMP    DAT
ONE     DAT 1

Last edited by MegaApuTurkUltra (Oct. 17, 2015 18:42:41)

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

MartinBraendli

MegaApuTurkUltra wrote:
Yay, 27 25 22 lines

Congrats! Happy to see someone accepted the challenge.
I've never programmed in Assembly before, but I like the hunt for those “wasted lines”. 30-40 years ago this must have been a big part of a programmers job.
I think 18 lines might be possible somehow, but if someone manages to get 17 i'd be really surprised. When I reached 19 i googled for other solutions and i couldnt find any with less than 21 lines (and the one with 21 was a bit flawed).

Check out my newest project:
Photorealistic 3d Renderer

MegaApuTurkUltra

MartinBraendli wrote:
MegaApuTurkUltra wrote:
Yay, 27 25 22 lines
Congrats! Happy to see someone accepted the challenge.
I've never programmed in Assembly before, but I like the hunt for those “wasted lines”. 30-40 years ago this must have been a big part of a programmers job.
I think 18 lines might be possible somehow, but if someone manages to get 17 i'd be really surprised. When I reached 19 i googled for other solutions and i couldnt find any with less than 21 lines (and the one with 21 was a bit flawed).

I've never tried assembly before so I'm not going to attempt to shorten mine any more. I've already removed 5 lines :P I'll leave further golfing to the assembly pros.
I lied

        INP
        SUB ONE
        SUB ONE
START   STA COUNTER
        LDA CURRENT
        ADD OLD
        STA CURRENT
        SUB OLD
        STA OLD
        LDA COUNTER
        SUB ONE
        BRP START
        LDA CURRENT
        OUT
COUNTER DAT
OLD     DAT 0
CURRENT DAT 1
ONE     DAT 1

19 18 lines

This uses a dirty hack that probably isn't portable (add a HLT after OUT to make it valid). Let me explain:
For the input case 1, the program goes through the entire thing and prints 1, then goes over the DAT spaces which are all 1 until it reaches space 19 which is a 0 since the program doesn't use it. Then, it halts
For the input case 1, the program goes over the entire thing and prints 1, then it goes over the DAT space for COUNTER which is 0 at this point, so it halts.
For all other valid input cases, the program loops as necessary until COUNTER is 0 and then uses COUNTER as a HLT.
Now the hacky case is where input is 1, because the interpreter has to go over a bunch of unknown commands. But, it works in chooper100's interpreter so I'm going to assume it's valid

————————————–
If printing unnecessary output is allowed, here's a 17 16 line version that uses the same dirty hack

        INP
        SUB ONE
START   SUB ONE
        STA COUNTER
        LDA CURRENT
        ADD OLD
        STA CURRENT
        OUT
        SUB OLD
        STA OLD
        LDA COUNTER
COUNTER DAT << the hack; if it's 0 then the program halts, otherwise the interpreter skips over it
        BRA START
OLD     DAT 0
CURRENT DAT 1
ONE     DAT 1

Last edited by MegaApuTurkUltra (Oct. 18, 2015 02:50:36)

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

MartinBraendli

MegaApuTurkUltra wrote:

        INP
        SUB ONE
        SUB ONE
START   STA COUNTER
        LDA CURRENT
        ADD OLD
        STA CURRENT
        SUB OLD
        STA OLD
        LDA COUNTER
        SUB ONE
        BRP START
        LDA CURRENT
        OUT
COUNTER DAT
OLD     DAT 0
CURRENT DAT 1
ONE     DAT 1

Nice solution! So against me prediction, a solution <18 IS possible. With some minor changes you might adapt it to the rules. Input 0 has to give output 0, yours gives 1.
Using code that only works on choppers implementation is totally legit though (imo).

My Code is actually quite similar:

	INP
LOOP 	STA N
	BRZ DONE
	LDA FIB1
	STA TMP
	LDA FIB2
	STA FIB1
	ADD TMP
	STA FIB2
	LDA N
	SUB ONE
	BRA LOOP
DONE 	LDA FIB2
	OUT
N 	DAT
ONE	DAT 1
FIB1	DAT 1
FIB2	DAT 0
TMP	DAT

What makes your code shorter/better is that you didn't use a third (“TEMP”) variable for shifting OLD/FIB1 to CURRENT/FIB2. If i apply this to my code, i get 17 lines.

	INP
LOOP 	STA N
	BRZ DONE
	LDA FIB2
	ADD FIB1
	STA FIB2
	SUB FIB1
	STA FIB1
	LDA N
	SUB ONE
	BRA LOOP
DONE 	LDA FIB2
	OUT
N 	DAT
ONE	DAT 1
FIB1	DAT 1
FIB2	DAT 0

MegaApuTurkUltra wrote:
If printing unnecessary output is allowed, here's a 17 16 line version that uses the same dirty hack

The reason why I added “exacly one input, exactly 1 output” rule is the following:

	INP
	LDA N
LOOP	OUT
	ADD ONE
	BRA LOOP
N	DAT 0
ONE	DAT 1

For any valid input, this WILL output the corresponding fibonacci number. However, it will also output every other natural number and wont even terminate. But without the 1-IN/1-OUT rule, this would (technically) be a valid solution.

EDIT: Anyway, thank you for your participating. I enjoyed seeing your code progress and finally beat mine.
EDIT2: If you write machine code instead of assembly, you could bring it down to legit 16 lines, since you wouldnt have to initialize FIB2/ OLD since its 0 anyway. Just use 316 and 516 to store/load.

Last edited by MartinBraendli (Oct. 18, 2015 08:33:19)

Check out my newest project:
Photorealistic 3d Renderer

MegaApuTurkUltra

MartinBraendli wrote:
My Code is actually quite similar:
	INP
LOOP 	STA N
	BRZ DONE
	LDA FIB1
	STA TMP
	LDA FIB2
	STA FIB1
	ADD TMP
	STA FIB2
	LDA N
	SUB ONE
	BRA LOOP
DONE 	LDA FIB2
	OUT
N 	DAT
ONE	DAT 1
FIB1	DAT 1
FIB2	DAT 0
TMP	DAT
What makes your code shorter/better is that you didn't use a third (“TEMP”) variable for shifting OLD/FIB1 to CURRENT/FIB2. If i apply this to my code, i get 17 lines.

That infinite loops for me on chooper's impl.

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

MartinBraendli

MegaApuTurkUltra wrote:
MartinBraendli wrote:
My Code is actually quite similar:
	INP
LOOP 	STA N
	BRZ DONE
	LDA FIB1
	STA TMP
	LDA FIB2
	STA FIB1
	ADD TMP
	STA FIB2
	LDA N
	SUB ONE
	BRA LOOP
DONE 	LDA FIB2
	OUT
N 	DAT
ONE	DAT 1
FIB1	DAT 1
FIB2	DAT 0
TMP	DAT
What makes your code shorter/better is that you didn't use a third (“TEMP”) variable for shifting OLD/FIB1 to CURRENT/FIB2. If i apply this to my code, i get 17 lines.
That infinite loops for me on chooper's impl.

Ah, i added formatig after testing it. Looks like it cant handle the tabs. try it without tabs:

INP
LOOP STA N
BRZ DONE
LDA FIB1
STA TMP
LDA FIB2
STA FIB1
ADD TMP
STA FIB2
LDA N
SUB ONE
BRA LOOP
DONE LDA FIB2
OUT
N DAT
ONE DAT 1
FIB1 DAT 1
FIB2 DAT 0
TMP DAT

Same for the 17 line version:

INP
LOOP STA N
BRZ DONE
LDA FIB2
ADD FIB1
STA FIB2
SUB FIB1
STA FIB1
LDA N
SUB ONE
BRA LOOP
DONE LDA FIB2
OUT
N DAT
ONE DAT 1
FIB1 DAT 1
FIB2 DAT 0

Check out my newest project:
Photorealistic 3d Renderer

MegaApuTurkUltra

I removed the tabs already because Scratch's list import thinks it's a CSV if they're there.

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

MartinBraendli

So it still doesnt work for you? Strange…
If I import the code like its written in post #9, the program terminates and also gives the expected output.

Check out my newest project:
Photorealistic 3d Renderer

MegaApuTurkUltra

Ah those work. Nvm

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

Jonathan50

Wait so @chooper100 made a Virtual Machine in Scratch!?
Or does it just interpret the Assembly?
Can you actually run binary on it?

Not yet a Knight of the Mu Calculus.

MegaApuTurkUltra

Jonathan50 wrote:
Wait so @chooper100 made a Virtual Machine in Scratch!?
Or does it just interpret the Assembly?
Can you actually run binary on it?

MartinBraendli wrote:
@chopper100 created a great implementation of the Little Man Computer. For those who don't know LMC (like me about 2 hours ago), it is basically a very simple machine language with its own assembly language. More on wikipedia, worth a read.

Last edited by MegaApuTurkUltra (Oct. 19, 2015 00:30:17)

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

Jonathan50

MegaApuTurkUltra wrote:
Jonathan50 wrote:
Wait so @chooper100 made a Virtual Machine in Scratch!?
Or does it just interpret the Assembly?
Can you actually run binary on it?
MartinBraendli wrote:
@chopper100 created a great implementation of the Little Man Computer. For those who don't know LMC (like me about 2 hours ago), it is basically a very simple machine language with its own assembly language. More on wikipedia, worth a read.

That doesn't answer my question

I guess chooper100's implementation doesn't compile the Assembly and run the machine code but rather interprets the Assembly (so I don't think that qualifies as a Virtual Machine).

Not yet a Knight of the Mu Calculus.

Firedrake969

A virtual machine is a software computer that, like a physical computer, runs an operating system and applications. The virtual machine is comprised of a set of specification and configuration files and is backed by the physical resources of a host.

No.

'17 rickoid

bf97b44a7fbd33db070f6ade2b7dc549

Jonathan50

Firedrake969 wrote:
A virtual machine is a software computer that, like a physical computer, runs an operating system and applications. The virtual machine is comprised of a set of specification and configuration files and is backed by the physical resources of a host.
No.

Lol
But if chooper100's LMC implementation executed the numerical machine code, it would be a virtual machine

Not yet a Knight of the Mu Calculus.

Firedrake969

It can be considered a “process virtual machine”, in a stretched sense.

'17 rickoid

bf97b44a7fbd33db070f6ade2b7dc549

MegaApuTurkUltra

Jonathan50 wrote:
MegaApuTurkUltra wrote:
Jonathan50 wrote:
Wait so @chooper100 made a Virtual Machine in Scratch!?
Or does it just interpret the Assembly?
Can you actually run binary on it?
MartinBraendli wrote:
@chopper100 created a great implementation of the Little Man Computer. For those who don't know LMC (like me about 2 hours ago), it is basically a very simple machine language with its own assembly language. More on wikipedia, worth a read.
That doesn't answer my question
I guess chooper100's implementation doesn't compile the Assembly and run the machine code but rather interprets the Assembly (so I don't think that qualifies as a Virtual Machine).

It's a virtual machine for running LMC code, not just any assembly.

LMC code is numerical but unlike normal assembly, it's in base 10. Instructions are the first base 10 digit and the second 2 base 10 digits for instructions that take an argument specify the RAM address of the argument.

Chooper100's code actually compiles the assembly into numerical decytecode (just made that word up) and then interprets that, so yes, it counts as both a kind of assembler and a VM.

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

gtoal

MartinBraendli wrote:

INP
LOOP STA N
BRZ DONE
LDA FIB2
ADD FIB1
STA FIB2
SUB FIB1
STA FIB1
LDA N
SUB ONE
BRA LOOP
DONE LDA FIB2
OUT
N DAT
ONE DAT 1
FIB1 DAT 1
FIB2 DAT 0

The only improvement I see here is:

N INP
LOOP STA N
BRZ DONE
LDA FIB2
ADD FIB1
STA FIB2
SUB FIB1
STA FIB1
LDA N
SUB ONE
BRA LOOP
DONE LDA FIB2
OUT
ONE DAT 1
FIB1 DAT 1
FIB2 DAT 0

to save 1 line. Most of my usual assembly tricks don't work because of the poor choice of instruction encoding and the undefined behaviour for illegal instructions.

Last edited by gtoal (Oct. 29, 2015 12:45:18)

Discuss Scratch