NOTE READ ME
Don't be scared by the length of the answer. Most of it is explaining microprocessor concepts and can be skipped if you understand that stuff. I just didn't want to assume that other readers had specific knowledge, so I pretty much spell out each step in detail. It made this post a bit long, but understandable by pretty much anyone. If you only care about the solution and not my journey getting there, just skip down to the solution part. It might be worth while reading the "Opcode" sections as I do have some logic used in the solution in those sections as well.
Initial Logic
When I first saw this about a month and half back, the memory layout immediately made sense to me as I have done some disassembly and microprocessor research for a project in the past. Looking over the C-SCAN 3000 print out, I had some intuitions about the instructions, but decided to do a little internet digging. After many articles and Wikipedia pages I came across 3 concepts that are used pretty heavily in my answer.
Here are the first two:
Instruction Sets
Accumulator Registers
And the real breakthrough:
The Little Man Computer
More information here and here
The first two concepts are important to understand for real world implementation while the breakthrough concept is more conceptual. The breakthrough concept is what will be the basis for the proposed solution. So I have outlined some of the important points below:
Breakthrough Key Points
1.) A little man is inside of a box. The little man does work
when he gets a "start" signal.
2.) A start signal is sent via a button pressed that is external to
the box the little man is in.
3.) The little man has at his disposal the following:
- Unlimited paper and pencils
- Mailboxes each capable of holding a single piece of paper
at a time
- A mailbox counter showing what mailbox the little man he
should look at next
- A calculator with some lights on it.
- Input and output baskets to...well get input and output
from the outside world.
4.) The calculator displays the result of the last operation.
5.) The calculator lights illuminate based on the result of the last
math operation. They track positive, negative, zero, and
possibly overflow conditions. So performing 2 - 2 would
illuminate the zero light on the calculator while 2 - 3 would
illuminate the negative light and so on.
6.) When the external button is pressed, the mailbox counter resets
to 0.
There might be some other details so I suggest you give it a read and play with the simulator here. What you will notice is our prison gate microprocessor has a very similar structure. It has memory addresses that can store one 7-bit value at a time, an external button that starts execution from memory address 0, input from the gate levers, output to the gate, an accumulator register (ACC) that is capable of holding results from arithmetic calculations. One thing that is not immediately clear is whether ACC keeps its value from a previous run when the gate button is pressed. Until we hear otherwise from the OP, let's assume it is cleared. All we need now is to define what instructions our prison microprocessor supports.
Instruction Set
There has already been some talk about instructions in other answers and I think we are all on the right track. The OP has confirmed that there are 5 different instructions used in this program and all of them are the absolute most basic instructions you can get. We can get a list of these basic instructions from the Instruction Sets link above. They are grouped into three categories.
Data Instructions:
- Load: Load from somewhere. Usually a memory address.
- Store: Store somewhere. Usually a memory address.
- Input: Getting input from some external hardware.
- Output: Sending input to external hardware.
Arithmetic Instructions:
- And: Bit-wise And of two operands.
- Or: Bit-wise Or of two operands.
- Xor: Bit-wise Xor of two operands.
- Add: Adds two operands together.
- Subtract: Subtracts one operand from another.
- Increment: Specialized version of add that just adds 1 to an
operand.
- Decrement: Specialized version of subtract that just
subtracts 1 to an operand.
Control Flow Instructions:
- Unconditional Branch: Branch to another memory address.
- Condition Branch: There are many types like branch when
something is equal or when the last math operation resulted in
an overflow, etc.
- Stop/Halt: Stop the CPU from doing any further execution.
One thing we have to define are the exact semantics of the above instructions. In normal people speak, we need to define details of how each instruction should work in our prison gate microprocessor. You may be thinking, "It seems pretty obvious what all of these instructions do", but I bring it up because it makes a difference for the Increment and Decrement instructions. I'll explain why this is important later on. So with that, let's start matching our five opcodes with instruction labels!
First Three Opcodes
The OP has not officially confirmed this, but @jousle made the assumption that 000 is a Halt instruction and 101 is some kind of Conditional Branch instruction. I think these are reasonable assumptions since they make sense and the OP did not specifically comment on them being wrong as he did with opcode 001 in @jousle's answer. So any memory address where the first 3 bits are 000 is either a Halt instruction or a data slot. So trying to execute a data slot would also halt the program which is good. If you look closely at the memory print out, we can map our third opcode. Each path of the conditional branch terminates, but one path does something slightly different.
|BEGIN BIN DUMP |
|***************|
|0000 001 1111|
|0001 010 1101|
|0010 001 1101|
|0011 001 1100| Branch on line 0100
|0100 101 0111| >---V--->--->---V
| Path 1 |
|0101 010 1101| <---< |
|0110 000 0000| |
|0111 010 1101| <---<---<---<---<
|1000 111 0000| Path 2
|1001 000 0000|
Looking at path 1, we have:
010 1101
000 0000
and looking at path 2, we have:
010 1101
111 0000
000 0000
Path 2 is almost the same, but has one additional instruction. @jousle caught onto this and proposed that it looks like an Output instruction. Basically a signal to the gate to open. The OP has not confirmed this, but I think it is a good guess. With that we have the first 3 opcode matched to their instruction labels. On to the final two opcodes!
The Final Two
The final two opcodes gave me a real headache. My initial thoughts were some type of encryption was going on due to the encryption note at the bottom of the C-SCAN 3000 print out. The OP confirmed that was not the case. My next realization was that the remaining two opcodes can not be Control Flow instructions. If they were the first 4 instructions could possibly terminate the program without ever doing anything useful and definitely without opening the gate. We can also weed out Input as a possibility pretty quick because why would you get input more than once? In addition there looks to be an operand associated with both opcodes where Input and Output do not need any operands as we saw with the 111 opcode at memory address 1000.
Load can also be weeded out as loading into the ACC does not make a lot of sense. In the case of opcode 001 why would you load something and then immediately overwrite it with another Load? In the case of 010 why would you load something and terminate the program without doing anything with the loaded value? Both are illogical actions so we can toss the Load instruction out. This leaves us with the following instructions to choose from: Add, Subtract, Increment, Decrement, and Store. We can eliminate specific combinations of instructions.
For example having one instruction be addition and the other be subtraction would not give you any change in output between runs of the program given the same lever positions as input. We know this can't be the case since the unlucky prisoner from our story would have gotten through the gate when he pressed the button right after the guard using the same lever positions. We can also weed out one of them being an Increment instruction and the other a Decrement instruction. If that were the case, the levers' positions would be irrelevant. One could just smash the button every two seconds until the gate opened up. In the end the reduced list of instruction combinations that actually do something logical is:
001 | 010
--------------------
1. Add | Store
2. Add | Increment
3. Add | Decrement
4. Subtract | Increment
5. Subtract | Decrement
Let's see which of these combinations of instructions actually hold up. In the following, I am going to use decimal numbers for memory addresses and data while the instructions will use 3 character abbreviations just to be able to understand things a little better instead of looking a 010100100101....
Opcode Set 1
I first tried combination #1. It looked very promising because having the Store instruction let's us see the value of ACC which makes it easier to reverse execute the program and find the mystery branch condition. Another benefit of this combination is the fact that the value in ACC gets doubled after finishing lines 0001 and 0010:
|BEGIN BIN DUMP |
|***************|
|0000 ADD 0015|
|0001 STO 0013|----> These two instructions perform the doubling.
|0002 ADD 0013|----> They store X from ACC then add the stored X
|0003 ADD 0012| to itself. So ACC = X + X.
|0004 B?? 0007|
The cool thing about this is it gives us a way fail this combination! Any time you double a number regardless of whether the value before the doubling is odd or even, the end result will always be even. If we ever see an odd number in ACC when we reach line 0011 during our reverse execution, this combination of instructions becomes invalid. With that in mind, I started working backwards from the unlucky prisoner's last attempt.
Instruction Descriptions
ADD: Add value stored at memory address represented by the
operand to ACC value and store in ACC.
B??: Branch on some condition.
OUT: Output signal to open the gate.
HLT: halt execution.
STO: Store ACC value at memory location represented by operand.
Prisoner Attempt: 3
Levers: Up,Down,Down,Up = 0110 = 6
MEM[0013]: 1110 = 14
|BEGIN BIN DUMP |
|***************|
|0000 ADD 0015|
|0001 STO 0013|
|0002 ADD 0013|
|0003 ADD 0012|
|0004 B?? 0007|
|0005 STO 0013|
|0006 HLT |
|0007 STO 0013|
|0008 OUT |
|0009 HLT |
|0010 000 0000|
|0011 000 0000|
|0012 000 13| <- Data Value 13
|0013 000 14| <- Data Value 14
|0014 000 0000|
|0015 000 0110|
|***************|
Reverse Execute MEM[0005]: STO MEM[0013]
ACC = MEM[0013] = 14
ACC = 14
ACC: 14
Reverse Execute MEM[0004]: B?? MEM[0007]
- We know the branch failed and just came from the failed
leg of it. We can move on to the next instruction and
reverse execute it.
ACC: 14
Reverse Execute MEM[0003]: ADD MEM[0012]
ACC = ACC - MEM[0012]
ACC = ACC - 13
ACC = 14 - 13
ACC = 1
Right away our alarm goes off because we know 1 is odd. It is impossible to find a whole number that when doubled gives us 1, so reverse executing the next two steps is impossible. That means this instruction combination is not valid.
Opcode Set 2
Combination #2 utilizes the Increment instruction, so this is a good place to explain why I introduced this nit pick detail about semantics of the Increment and Decrement instructions above. Let's look at Increment as the same logic applies to Decrement. One way of implementing the Increment instruction on a memory address is having the CPU load the value at the target memory address into ACC, adding 1 to it, and then storing it back into memory again. You can think of it as a group execution consisting of a Load, Add, and Store instructions like this:
Load X: Load the value at memory address X into the ACC.
Add 1: Increment the ACC by 1.
Store X: Store the ACC value at memory address X.
The problem may not be immediately obvious until you try to work backwards. You quickly see that you can't determine what was in the ACC register before the "Load X" instruction without some other context prior to the Load. Essentially the Load instruction overwrote the data in ACC. There are ways around this, but the program we were given is not designed in a way that we can determine what ACC was before it was used to increment something. We would be lucky if we had a second register to do increments in, but the OP confirmed to my earlier question that this microprocessor has a single accumulator register and no others.
A second way the Increment instruction could work is by adding 1 "in memory". This would not require the use of the ACC, but would require the microprocessor design to support "in memory" semantics for the Increment and Decrement instruction. The ACC value would be preserved for us to know what it is and we could then reverse execute the program. I'll spoil the surprise now. Without this assumption, there seems to be no solution to the puzzle without adding complex instructions to our initial list defined above. Increment and Decrement are already starting to get into the realm of complex instructions, but they are sometimes found in the simplest of microprocessors. If I have taken us down some dark and dangerous path of reasoning, the OP will most definitely let us know in a comment and clarify the muddy water I have made. Until that happens, let's use this "in memory" assumption and find a working solution to the puzzle!
So without further ado, here is the solution!
Finally A Solution
Combination #1 is the solution to the puzzle using the assumptions above. I won't go into the detail of the other combinations, but try them yourself and you will see there is no clean branch condition that can be used to solve the puzzle. Combination #1 assigns the Add instruction to 001 and Increment instruction to 010 and produces a solution that generates a branch condition for the attempt to open the gate made by the guard, but no branch condition on all of the unlucky prisoner's attempts! Let's reverse execute the program and see what the branch condition is!
Instruction Descriptions
ADD: Add value stored at memory address represented by the operand to ACC value and store in ACC.
B??: Branch on some condition.
OUT: Output signal to open the gate.
HLT: halt execution.
INC: Increment the value at the memory address represented by the operand by 1.
Levers: Down,Up, Down,Down = 1011 = 11
|BEGIN BIN DUMP |
|***************|
|0000 ADD 0015|
|0001 INC 0013|
|0002 ADD 0013|
|0003 ADD 0012|
|0004 B?? 0007|
|0005 INC 0013|
|0006 HLT |
|0007 INC 0013|
|0008 OUT |
|0009 HLT |
|0010 000 0000|
|0011 000 0000|
|0012 000 13| <- Non Changing Data Value 13
|0013 000 14| <- Counter value 14
|0014 000 0000|
|0015 000 0110|
|***************|
Let's assume that when the button is pressed, the program counter and the ACC register are both reset to 0. The only persistent information is what we see in memory. If we focus on the memory and instructions for a second, we can notice that there are two data items that change between runs that are interesting to us. The first is the lever input at memory address 15. We obviously use that. The second is the counter value at memory address 13. It counts up by 2 each time the program is run regardless of whether the gate was opened or not. That means to re-create the prisoner's 3rd attempt we need to just subtract 2 from the counter at MEM[0013] and re-run the program. Doing that we get the following outcome:
Prisoner Attempt: 3
Lever Positions: 0110 = 6
MEM[0013]: 1100 = 12
ACC: 0
Execute MEM[0000]: ADD MEM[0015]
ACC = ACC + MEM[0015]
ACC = ACC + 6
ACC = 0 + 6
ACC = 6
ACC: 6
Execute MEM[0001]: Increment MEM[0013]
MEM[0013] = 12
INC MEM[0013]
MEM[0013] = 13
ACC: 6
Execute MEM[0002]: ADD MEM[0013]
ACC = ACC + MEM[0013]
ACC = ACC + 13
ACC = 6 + 13
ACC = 3
Now you may be wondering why ACC is 3 and not 19? Since we can only store 4 bits of data, when we reach 15 or 1111 everything wraps around back to 0 and counts from there. This is Modulus Addition where the modulus is 16. Depending on the microprocessor, this wrap around, or overflow as it is also known, might be a condition that is recorded. Since we have more math operations before our branch, this particular overflow is not important to us as it only applies to the last math operation.
ACC: 3
Execute MEM[0003]: ADD MEM[0012]
ACC = ACC + MEM[0012]
ACC = ACC + 13
ACC = 3 + 13
ACC = 0
Here we have another overflow condition, but this time it is right before our branch. So we can't say for certain until we test the other attempts, but one condition to open the gate might be using lever positions that do not trigger an overflow on the last addition. The next instruction is the branch which we pass through since we know the gate did not open. The last instruction before the halt takes our counter back up to 14.
We have to go back through all of the prisoner's attempts and the guard's attempts to see if all of the prisoner's attempts produce overflow while the guard's does not. If so then that is one possible solution. Since I have already done this and the process is pretty much the same as the above, I will only do the guard's attempt. You can verify, but the prisoner's attempts all produce overflow conditions. For the guard's attempt, we need to roll back 4 attempts, putting our counter at MEM[0013] to 6.
Guard Attempt
Lever Positions: 1011 = 11
MEM[0013]: 0110 = 6
ACC: 0
Execute MEM[0000]: ADD MEM[0015]
ACC = ACC + MEM[0015]
ACC = ACC + 11
ACC = 0 + 11
ACC = 11
ACC: 11
Execute MEM[0001]: Increment MEM[0013]
MEM[0013] = 6
INC MEM[0013]
MEM[0013] = 7
ACC: 11
Execute MEM[0002]: ADD MEM[0013]
ACC = ACC + MEM[0013]
ACC = ACC + 7
ACC = 11 + 7
ACC = 2
ACC: 2
Execute MEM[0003]: ADD MEM[0012]
ACC = ACC + MEM[0012]
ACC = ACC + 13
ACC = 2 + 13
ACC = 15
Lucky us! No overflow! So one possible solution is to produce no overflow. Using that as the criteria let's see what lever positions our protagonist need to produce in order to escape.
Protagonist Attempt
Lever Positions: ???? = X
MEM[0013]: 1110 = 14
ACC: 0
Execute MEM[0000]: ADD MEM[0015]
ACC = ACC + MEM[0015]
ACC = ACC + X
ACC = 0 + X
ACC = X
ACC: X
Execute MEM[0001]: Increment MEM[0013]
MEM[0013] = 14
INC MEM[0013]
MEM[0013] = 15
ACC: X
Execute MEM[0002]: ADD MEM[0013]
ACC = ACC + MEM[0013]
ACC = ACC + 15
ACC = X + 15
ACC = X + 15
ACC: 2
Execute MEM[0003]: ADD MEM[0012]
ACC = ACC + MEM[0012]
ACC = (X + 15) + 13
Some simple arithmetic shows us that lever combination 0011 or Up, Up, Down, Down will not cause an overflow and get our guy through. His family can also get through if we follow a very specific pattern:
(X + 1) + 13 -> X = 0001 = 1
(X + 3) + 13 -> X = 1111 = 15
(X + 5) + 13 -> X = 1101 = 13
All you need to do to get the next lever position is subtract two from the previous combination represented in numerical form.
Solution 2?
The thought may have crossed your mind in the last section that our protagonist could have used another set of lever positions to escape and you would be correct! In fact every new attempt has two possible combination that open the gate. So the protagonist and his family could use 0010, 0000, 1110, 1100 to open the gate. It is probably the solution, but there could be another answer. When looking closely at the C-SCAN 3000 print out and the guard's attempt to open the gate, I noticed something. The guard produced a final value in ACC of 1111 before the branch happened. When I was analyzing the C-SCAN 3000 print out, I was focused on the lower section as it seemed to provide no value to the problem:
|***************|
|ACC &%#$ ERROR|
|ENCRYPTED VALUE|
| |
|1111 EXT. |
| |
|FURTHER DEBUG. |
|UPGRADE TO C- |
|SCAN 4000+ |
| |
|EOF |
-----------------
I originally focused on the encrypted value part, but the OP told me there was no encryption. I dismissed the whole bottom section, but later realized that the "1111 EXT." part may have a meaning. It could be 1111 Extension or could it be 1111 Exit! Does it mean you have to get ACC to equal 1111 to get the exit to open? If that is true, the solution 1 lever positions produce an ACC value of 1111 and we no longer have multiple lever positions opening the gate ever. Usually this would be done with a compare instruction against some some memory address holding the value 1111, but there could be a custom instruction specific to this microprocessor that checks the ACC for the value 1111. The OP would have to weigh in an address some of these assumptions before we can say for sure.
So there it is! Lever positions that will allow our guy to escape to the next area with his family! I had a lot of fun doing this and look forward to seeing what happens to our protagonist, who needs a cool name btw ;)
