It seems that you're using an outdated browser. Some things may not work as they should (or don't work at all).
We suggest you upgrade newer and better browser like: Chrome, Firefox, Internet Explorer or Opera

×
avatar
nicode: No, ten - time to have some sleep *g*
You can put negative numbers in the x/y? Hmmm... Although it certainly does hint at how it works, and quite curious too, reminds me of what i'd do if i wanted a single for loop for a bunch of combinations but didn't want to do 3-6 inner for loops, and instead broke the large number down to individual parts. This is effectively what's happening.

Makes me wonder, we need to write down all the nuances of the machine that we discover, which helps with these little optimizations.
avatar
rtcvb32: This is effectively what's happening.
In the cycle-perfect solution a value must be written out in every cycle (even in the very first cycle with undocumented behavior). So you need at least 3 nodes with 7 instructions. The left node has to spit out the terminator (-1) and the next position (0, ACC) in the right moment. So it must be deferred with a wait loop. In the earlier solution you can clearly see what happens. It needs 3 instructions just for increasing ACC (row). It took me a while to get rid of all 3 instructions by finding a loop logic that doesn't need SAV/SWP and leaves the loop with an ACC increased by one: We need rows from 1..17 (+1 for not hitting 0); so the loop counter uses a step width of 18; we need 29 loops for the sync; so at the beginning the current ACC is reduced by 29*18-1 (-1 for leaving the loop with old ACC+1); and the loop condition just checks if ACC is restored/increased (greater than zero).
And all this stuff only to reduce cycles/nodes/instruction of a virtual machine :)
avatar
rtcvb32: Makes me wonder, we need to write down all the nuances of the machine that we discover, which helps with these little optimizations.
There are many things you need to find/try/fix to get better scores (integer over-/underflow, JRO over-/underflow).
But optimization is a very advanced topic, and the thread goes more and more off-topic here...
Post edited July 25, 2015 by nicode
So some machine specific nuances i've noted with experimentation so far:

Accepting an external read takes 1 cycle, while writing it takes 2 (execute and write being separate). Taking a single node with 'mov any, acc' surrounded by mov's that try to push numbers, it will alternate left and right. Adding a nop (after receiving from any) changes the behavior so it's always reading from the left.

So:
Read preferences (from any) is Left, Right, Up, and Down. - See pad
Write preferences (from any) is Up, Left, Right, Down - see pad

The stack memory reads ALL inputs/ports in the same cycle, in the same order as the read preferences.
The stack will only output 1 number, in the order of the write preference
The stack also holds a max of 15 numbers.
The stack will output before it accepts inputs.
see pad

I was reluctant to use the any/last for source, but the last port is ONLY updated when reading/writing using any. So accepting an input from any, and referring the data to another function, you can then return an answer using last afterwards.
Post edited July 26, 2015 by rtcvb32
avatar
wongheiming: Being a non-programmer, will this game be too difficult? Will I learn how to programming (or on conceptual level) by playing this?
The only "programming" I know is bash scripting. At first I was unsure about the game, but after watching a video on YT where someone went through the first to puzzles I decided to buy it. I haven't tried it yet as it's almost midnight here, but it's seems to be a game I might easily spend some time playing and having fun with.
avatar
dokterw: The only "programming" I know is bash scripting.
Assembly and bash have a mighty big leap there. I still say it's worth it to try your hand at solving some common simple tasks...
I bought the game before the discount gone and decided to try it soon. Read the manual last night but too tried to understand it, will read again in weekend.
The manual feels like real technical document. I read it on a tablet and it seems there is sort of next page "fade printing" in the background? It should print reversely and make it like a book...
And I think I should rewrite the manual on my wording too...

Meanwhile I'm stuck in Spacechem again. I think switching game to keep brain fresh is a good idea. But it maybe too heavy for my little brain :)
avatar
wongheiming: I bought the game before the discount gone and decided to try it soon. Read the manual last night but too tried to understand it, will read again in weekend.
The manual feels like real technical document. I read it on a tablet and it seems there is sort of next page "fade printing" in the background? It should print reversely and make it like a book...
And I think I should rewrite the manual on my wording too...
Well considering the manual is suppose to look and seem like a technical manual with some written in notes or highlighting, there's honestly nothing wrong with it. Mind you i haven't read many specs or manuals from the 70's, but i have gone through Intel's Pentium manual (3 books!) and that gets very technical. Honestly since i was writing an assembler i didn't go through 2 of them and scoured the opcode book the most :P In comparison, the complexity is tiny... Probably similar to RISC (Reduced Instruction Set Computing) and CISC (Complex Instruction Set Computing).

Anyways, if this is your first step into programming, your primary resource is going to be your ACCumulator register, and occasionally your BAcKup register. Since there is no control register (to hold the results of compares, above, below, zero, overflow, carry, etc) it's all reduced to jumps which do a compare on the fly.

The only part of the whole thing that is a bit of a brain tease at first, is you have up to 12 parallel processes working at the same time. This means you can divide the work up two or three ways using a central controller and then forward the results, making it faster (which curiously is a bit how GPU's work); However optimizing won't be your goal. Your goal is to just get it to work. Quite often, take the simplest approach, break it into 3-4 parts, and then have it do the work along the way taking your 15-ish instructions to about 13 per node (or about 39-52), but some problems WILL require you to use extra nodes simply because you can't store numbers or use the BAK register to adding/subtracting; The min/max (peak detector?) for example.

As for more advanced features... Avoid the JRO, it's a curiosity that lets you treat a node as a set of functions that does multiple things waiting for commands, but you will have to change the offsets of every node connected to it if you change anything, so unless you get the node correctly beforehand, it will just generate headaches.

Labels... don't make large labels, shorten them to 1-2 letters. W for work, A for add, S for subtract, G for get, P to push off. L for less, G for greater, ect. If that's not enough then WK for work, AD for add, SB for subtract, GT for get, PU for push, LZ or less, GZ for greater, etc. The reason is you have limited width for your commands, and if you make long complex labels before hand they will take up a whole command of precious space... Which is important later and not so much earlier. You'll see what i mean.
Post edited July 28, 2015 by rtcvb32
I start the adventure few days back and solve 5 puzzles so far.
However on the fourth puzzle Signal Comparator it took me an hour, and my own solution is far below average. After a few goolging I rewrite the code and par with average.
On the fifth puzzle it took half an hour, way below average. Another 10 mins rewriting it is slightly better but far from average. Anyone can review my codes and teach me how to think like a machine?
Attachments:
avatar
wongheiming: I start the adventure few days back and solve 5 puzzles so far.
However on the fourth puzzle Signal Comparator it took me an hour, and my own solution is far below average. After a few goolging I rewrite the code and par with average.
I'd recommend just solving the puzzles, don't worry about optimizing... But since you're going to insist anyways

avatar
wongheiming: On the fifth puzzle it took half an hour, way below average. Another 10 mins rewriting it is slightly better but far from average. Anyone can review my codes and teach me how to think like a machine?
The reason the code you have is so slow, is because all the work is being done on the first 3 input nodes. A large portion of the TIS-100 is that you work in parallel. This means trying to even out the load as much as possible. My main solution usually involves block 7 (mov any, down) instead has move left, acc and add right, before moving down. The middle block then just becomes a little mechenism to tell the left and right sides if they should return the number or return 0.

Another big thing of optimizing is i notice you have:

[code]
JEZ 0
JGZ 1
JLZ -1
[/code]

which encompasses numeric labels. I'd recommend shortening them to the last 2 letters of the result or a more concise label name. 1-2 letters is more than enough to make it more obvious. Plus JRO doesn't follow labels, so doing the above would result in code that doesn't work and you don't know why.

Alright so back to the three compares. Don't compare for all 3 results, instead check for the 1 result you're interested in. So... Block 2 you'd be interested in JLZ, once you do that jump to the working part of your code. All other results (EZ, GZ) are immediately after JLZ code. So if i re-write it:

[code]
START:
MOV UP, ACC
SAV
MOV RIGHT, ACC
JLZ W
JMP START
W: SWP
MOV ACC, DOWN
[/code]

Another thing is you aren't working with the result, so it would probably be better if you work with it once you have an answer, which removes SAV/SWP

[code]
START:
MOV RIGHT, ACC
JLZ W
JEZ Z
MOV UP, NIL
JMP START
W: MOV UP, DOWN
JMP START
Z: MOV UP, RIGHT
[/code]

If you don't mind going down the road of insanity and working with JRO, you can do the following:
[code]
ST: JRO RIGHT
NOP
MOV UP, RIGHT
JMP ST
NOP
NOP
MOV UP, NIL
[/code]

while block 3 has:

[code]
ST: MOV UP, ACC
ADD 2
ADD ACC
MOV ACC, LEFT
MOV ACC, RIGHT
SUB 4
JEZ Z
JMP ST
Z: ADD LEFT
ADD RIGHT
MOV ACC, DOWN
[/code]

Let's explain this. JRO jumps X number of instructions as specified by an input. 0 is your problem input because it just repeats JRO immediately with no context of what to do. SO:
ADD +2:
-1 -> 1
0 -> 2
1 -> 3

ADD ACC:
1 -> 2
2 -> 4
3 -> 6

Lastly i check for 0 at the end by subtracting 4, if it is zero I'm getting the value back so i just add what's left and shove it down.

So finally, multi-tasking. Even if your code is bad, or even optimized you can in some cases get more work done simply by copy/pasting the code and working with it afterwards. This assumes you have room for a few instructions, and your path that you work isn't odd, in this example the pathing is a little odd, but a previous one for just doubling the numbers you'd do:

[code]
MOV UP, ACC
ADD ACC
MOV ACC, DOWN
[/code]

Well, if you forward a value first you can then be working on it in another block, and then forward the after result afterwards. Takes up more space but you're working twice as hard. Not always efficient though.

[code]
@2:
MOV UP, DOWN #forward 1st value
MOV UP, ACC
ADD ACC
MOV ACC, DOWN

@6:
MOV UP, ACC
ADD ACC
MOV ACC, DOWN
MOV UP, DOWN #forward tail second value's result
[/code]

Limiting how many cycles your code works in and trying to do a little of the load, even if it's insignificant and then moving it to the next step could make the entire thing faster.

With that in mind, a lot of low level tricks take a while to build up and just learn from mistakes, and just seeing the answer doesn't mean it sinks in unless you came up with that result that does as well, or in a few rare cases even better than the best known result. (i have at least 2).

edit: Glancing at the other code after i wrote this i see you did some of the improvements already to some degree... So sorry on that.

edit2: Wow, just wow. Just re-wrote the solution and got it much faster than i expected... Here's the code
Attachments:
22280.png (110 Kb)
Post edited August 05, 2015 by rtcvb32
avatar
wongheiming: I start the adventure few days back and solve 5 puzzles so far.
However on the fourth puzzle Signal Comparator it took me an hour, and my own solution is far below average. After a few goolging I rewrite the code and par with average.
avatar
rtcvb32: I'd recommend just solving the puzzles, don't worry about optimizing... But since you're going to insist anyways
Solving the puzzles is my primary goal, performance fall bewteen the histograms as secondary, falling outside make me sad and upset.
I'm not aiming a world class code solution, apparently I haven't met the secondary goal yet.

avatar
rtcvb32: The reason the code you have is so slow, is because all the work is being done on the first 3 input nodes. A large portion of the TIS-100 is that you work in parallel.
After playing with Spacechem I believe using more nodes should shorten the cycle. But the histograms shows most people using 5 nodes, fewer instruction and the cycle is about 300. My assumption is most people using the straight thinking apporach (5 nodes) instead of paralleling (7 nodes), still get a fare cycle count. Obviously there is something wrong with my 7 nodes code.

avatar
rtcvb32: Alright so back to the three compares. Don't compare for all 3 results, instead check for the 1 result you're interested in. So... Block 2 you'd be interested in JLZ, once you do that jump to the working part of your code. All other results (EZ, GZ) are immediately after JLZ code. So if i re-write it:

[code]
START:
MOV UP, ACC
SAV
MOV RIGHT, ACC
JLZ W
JMP START
W: SWP
MOV ACC, DOWN
[/code]
Then I should think in "If, then, else" and write them in "If, else, then", quit the procedure asap if the statement is false?

avatar
rtcvb32: Another thing is you aren't working with the result, so it would probably be better if you work with it once you have an answer, which removes SAV/SWP
Interesting. Should consider what to grab first instead of grabing all the stuff in first place...

avatar
rtcvb32: If you don't mind going down the road of insanity and working with JRO, you can do the following:
I will skip JRO at this moment and review later. It is an advance topic to me...

avatar
rtcvb32: With that in mind, a lot of low level tricks take a while to build up and just learn from mistakes, and just seeing the answer doesn't mean it sinks in......
Totally agree on that!
But a weird thing in my Spacechem experience is that I made a really bad solution (way~~~ below histograms) on the late world early mission, and then come up with an above average on later mission with much less planning time.
That's why I want to sharpen my skill by improving the code before moving on.
avatar
rtcvb32: I'd recommend just solving the puzzles, don't worry about optimizing... But since you're going to insist anyways
avatar
wongheiming: Solving the puzzles is my primary goal, performance fall bewteen the histograms as secondary, falling outside make me sad and upset.
I'm not aiming a world class code solution, apparently I haven't met the secondary goal yet.

avatar
rtcvb32: The reason the code you have is so slow, is because all the work is being done on the first 3 input nodes. A large portion of the TIS-100 is that you work in parallel.
avatar
wongheiming: After playing with Spacechem I believe using more nodes should shorten the cycle. But the histograms shows most people using 5 nodes, fewer instruction and the cycle is about 300. My assumption is most people using the straight thinking apporach (5 nodes) instead of paralleling (7 nodes), still get a fare cycle count. Obviously there is something wrong with my 7 nodes code.
Yeah... As a programmer i know i can do better, and i did assembly language programming as a hobby for 2 years (making an assembler) so you do some tricks to avoid making a new memory slot by using an extra 16-bit register that otherwise was inaccessible. It's interesting, but ultimately pointless when you go to a slightly higher and better supported language like C/C++.

The Histogram is interesting. It only shows the best of the results for all your solutions. So you could do a minimal 5 block just to get it done to get the minimum node/instruction solution, then use all the blocks to get the fastest solution. I'd personally be unconcerned about the number of nodes, it's the speed that's the most important by far. After that, nodes (if there was some type of power concern like making code for a wristwatch), and finally instructions. Although sometimes the simplest solutions offer the best results.

avatar
wongheiming: Then I should think in "If, then, else" and write them in "If, else, then", quit the procedure asap if the statement is false?
I suppose. Part of it involves that you have a silent jump going to the beginning of the code at the end and the behavior of this pseudo chip. If we go back to assembly x86 where you have registers and flags to consider, you'd do a check like so:
[code]
MOV AX, [INT1]
MOV BX, [INT2]
CMP AX, BX
JNE ELSE

JMP ENDIF
ELSE:

ENDIF:
[/code]

Maybe that doesn't clean up a bunch, but reducing how many comparisons and checks you have depends on how much complexity there is. Rearranging code can give marginal improvements. Some code works faster and better if you know an assumption and then check if it's not true and changing it afterwards.

[code]
int b = min(x,y); //assume we want the minimum, asked 4/5 times

if (code==MAXIMUM)
b=max(x,y);

//vs
int b;

if (code == MINIMUM)
b=min(x,y);
else if (code==MAXIMUM)
b=max(x,y);
[/code]

avatar
wongheiming: Interesting. Should consider what to grab first instead of grabbing all the stuff in first place...
Well... if you don't need to modify the result, don't move it into the accumulator register. if you have to split the data off with copies or do something with it, then moving it to the accumulator is pretty much unavoidable.

Some of the later puzzles you'll be doing a lot so just having 'mov in, out' as the only line is unlikely.

avatar
wongheiming: But a weird thing in my Spacechem experience is that I made a really bad solution (way~~~ below histograms) on the late world early mission, and then come up with an above average on later mission with much less planning time.
That's why I want to sharpen my skill by improving the code before moving on.
I enjoyed SpaceChem, but it's a bad substitute for a programming and planning. Creating large obscure paths to keep molecules from colliding is fun as a brain teaser but a bad comparison.

Don't be afraid to move forward until you get stumped, perhaps something you've learned will let you code a previous section better. A large number of the puzzles are sort of stepping stones, having you come to solutions for minimum/maximum based on the limited instruction set helps you think the way you need to for the later puzzles.

Honestly i have few issues until i got to where i just needed more ram for instructions, more memory blocks, or perhaps a lot more space just to do simple concepts and being forced to think in more abstract function or master/slave based programming (JRO) to minimize code space within certain chips just because of the layout (or due to error nodes)
Post edited August 05, 2015 by rtcvb32
avatar
wongheiming: After playing with Spacechem I believe using more nodes should shorten the cycle.
No, just using more nodes doesn't improve performance in and of itself. You need to split up the workload between the nodes, so that your solution can process more than one set of data at once.
I'm attaching a copy of my multiplexer solution - as you can see, it has three nodes that perform the same calculations on three sets of inputs at once, resulting in solving the task in 167 cycles. I had a 165 cycle solution at one point, but I kind of ended up overwriting it by accident.

avatar
rtcvb32: Alright so back to the three compares. Don't compare for all 3 results, instead check for the 1 result you're interested in.
A different solution is to add 3 to the input value and then use JRO to create a switch statement. The last node doesn't even need to run any calculations, since the node before it can provide it with the answer. This gets me down to 256 cycles.

It's still not the perfect solution, mind you.
Attachments:
avatar
thefifthhorseman.229: A different solution is to add 3 to the input value and then use JRO to create a switch statement. The last node doesn't even need to run any calculations, since the node before it can provide it with the answer. This gets me down to 256 cycles.
I think my solution is 264 cycles and very similar. Since there's almost always 39 inputs, you can calculate yours takes about 6.5 cycles per number, and mine 6.7. Hmmm a little shifting and tinkering and i might match yours, but it seems pointless, i'm satisfied with a < 300 solution.
TIS-100 is a great game for anyone who enjoys lateral thinking challenges.

The multiplexer is actually quite easy to get a good solution. This was my first attempt and it came in at 204 cycles.

Sometimes you just need a new approach to the problem.
Your thinking may be too reductionist.
Try approaching the problem more holistically.
Also, for best speed, try to do as little in each node as possible, or go into parallel if you can.
Do not handle three cases in a node if you can get away with only handling two and putting it together later.
Attachments: