刑務所の逃避のPt。 1(ザ・ドア)

You are currently escaping a prison owned by a mad
scientist.

あなたが大型の鉄製のドアに近づくにつれ、   出口につながると、ガードが影から出てきました。

     

あなたはすぐにあなたの妻の隣にある木製の箱を隠していました。   あなたを心配して待っていた娘。

     

隠れ場所から静かに眺めます。

     

ガードがいくつかのレバーを回転させるのが分かります。
4つありました。
ガードが何らかのPDAを読み取っている間に、2つのレバーが反転しました。ザ
  ガードはレバーの隣に大きな赤いボタンを押した。
2秒が経過すると、騒がしい騒音でドアが滑って聞こえます。

     

警備員がそのドアを歩いていた瞬間、すぐに殴られた   閉ざされ、大きな騒ぎで。

     

レバーの位置をメモします:下へ下へ

     

ガードがパスワードをリセットするのを忘れたと思っていたので、あなたは
  ドアに向かって走っている不安な人物を見てください。彼はボタンを押し、
  何も起こりません。あなたは彼の顔に絶望を見ることができます。
  ボタンを2回押すと、3つのレバーが不規則に反転します。
  3回目に赤いボタンを押すと、2人の警備員が出てきた
  影は彼を遠ざけた。あたかも次のものになるような気がする   彼のように終わる。

     

あなたは夜間まで待つ。 (少なくとも、あなたはそれが夜間だと思う、そこに
  太陽光も時計も時間を追跡することはできません)。

     

あなたがドアに近づく今回、あなたは周りを見回します。誰もいません。

     

何かを触れる前に、新しいレバーの位置をメモします:上へ   下へ

     

ドアコントロールを収納しているパネルを開くと、すべてがきれいです
  ワイヤーが見えませんが、1つの集積回路があります。   あなたはまだあなたのC-SCAN
3000を持っていることを覚えています。   マイクロプロセッサをスキャンし、内部メモリの状態を返します。

     

驚いたことに、それはうまくいった!あなたは熱心に印刷物を裂く   

-----------------
|   -0004502-   |
|MICP @4cyc/s   |
|ARCH: UNK      |
|MEM:  4-bit    |
|INST: 3-bit    |
|               |
|BEGIN BIN DUMP |
|***************|
|0000   001 1111|
|0001   010 1101|
|0010   001 1101|
|0011   001 1100|
|0100   101 0111|
|0101   010 1101|
|0110   000 0000|
|0111   010 1101|
|1000   111 0000|
|1001   000 0000|
|1010   000 0000|
|1011   000 0000|
|1100   000 1101|
|1101   000 1110|
|1110   000 0000|
|1111   000 0110|
|***************|
|ACC &%#$  ERROR|
|ENCRYPTED VALUE|
|               |
|1111 EXT.      |
|               |
|FURTHER DEBUG. |
|UPGRADE TO C-  |
|SCAN 4000+     |
|               |
|EOF            |
-----------------

ドアを開ける次のレバーの位置は?

ボーナス:ドアが一人だけ開いているので、次の3つのレバーポジションを見つけて、家族の誰もが逃げることができます。

これは非常に難しいパズルかもしれませんが、私はヒントを与え、必要に応じて混乱を取り除きます。

[OK]を3ヶ月経つと、私は受け入れ可能なヒントを出すことができると思う:

  • 命令を解読するのは難しいことではありません.Turing-completeコンピュータの基本的な指示は何ですか?
    意味のある有用なプログラムを作成するための絶対的な基本
  • 使用される命令は5つしかないので、多くの可能性が絞り込まれます。
  • 注意:コンピュータは4Hzで動作しますが、常に動作しているわけではありません。プログラムがトリガーされると、 PC は常に0になります。

さらに大きなヒント:

– アセンブリ言語に役立つ指示:入力/出力、数学、分岐、停止/停止
  – 整数オーバーフローと同等の数学演算は何ですか?

ベストアンサー

READ ME

     

答えの長さに怯えてはいけません。そのほとんどはマイクロプロセッサの概念を説明しており、そのことを理解すればスキップすることができます。私はちょうど他の読者が特定の知識を持っていたと仮定したくないので、私はそれぞれのステップを詳しく説明しています。このポストは少し長くなりましたが、かなり多くの人が理解できます。私の旅ではなく、ソリューションだけに気を付けるならば、ソリューションの部分にスキップしてください。
“Opcode”セクションを読んでいる間は、これらのセクションのソリューションにもいくつかのロジックが使われているので価値があるかもしれません。

初期ロジック

私が最初にこれを1ヶ月半前に見たとき、私は過去にプロジェクトの分解とマイクロプロセッサの研究を行っていたので、メモリのレイアウトはすぐにわかりました。
C-SCAN
3000のプリントアウトを見て、私は指示に関する直感を持っていましたが、ちょっとしたインターネット掘り出しをすることに決めました。多くの記事とWikipediaのページの後、私は私の答えでかなり使われている3つの概念に出くわしました。

最初の2つはここにあります:

命令セット
 アキュムレータレジスタ

実際の画期的な進歩:

リトルマンコンピュータ

詳細については、こちらおよびここ

最初の2つの概念は、実際の実装を理解する上で重要ですが、画期的な概念はより概念的です。画期的なコンセプトは、提案されたソリューションの基礎となるものです。だから私は以下の重要なポイントのいくつかを概説しました:

画期的なキーポイント

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.

指図書

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
指図書s 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!

最初の3つのオペコード

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 最終2
opcodes!

最終2

最終2 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….

オペコードセット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.

オペコードセット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!

最後に解決策

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.

解決策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.

だからそこにある!私たちの男は彼の家族と次の領域に逃れることができるレバーの位置!私はこれをやって楽しんでいたし、クールな名前を必要とする私たちの主人公に何が起こるのを楽しみにしている;)

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です