ドッキングデータ

コード2020日14の出現

シミュレータをお試しください！

タスク：Xのどこに解決する.

X = the sum of all values left in memory after initialization completes

例入力

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

表す

ビットマスク

メモリ内のアドレスに割り当てる一連の10進値

第1部

ビットマスクの仕組みを理解する

いくつかの小さなアルゴリズムの構築

完全に今:作業アルゴリズムを書く

シミュレータの構築

ビットマスクの仕組みを理解する

この例では、ビットマスクは以下の通りです:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X

36文字ロング

から成るX s0 と1 s

X 透明なマスクを示します:以下の値を上書きしないでください

0 と1 sは不透明なマスクを意味します0 or 1

最初の命令は

mem[8] = 11

メモリのアドレス8に整数11を割り当てる

以下に例を示します.

mask:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X

decimal 11 as bits:
1011

decimal 11 as bits, padded with 0s to be 36 characters long:
000000000000000000000000000000001011

areas of overlap:
                             1    0

decimal 11 as bits, masked:
000000000000000000000000000001001001

new bits without padding:
1001001

converted to decimal:
73

いくつかの小さなアルゴリズムの構築

各命令の重要な部分をキャプチャ

10進数を2進数に変換する

バイナリを10進数に変換する

我々のマスクと一致するためにスタートで番号をパディングすること

文字列からバイナリ番号を解析する

適切な文字列を上書きする

各命令の重要な部分をキャプチャ

入力のストリームの中に2行テンプレートの1つがあります.

mask = それから36文字の文字列を含むX s 0 S1 s

mem それから、括弧で囲まれた整数= , それからもう一つの整数

この正規表現はテンプレートにマッチし、重要な要素の1つまたは両方をキャプチャします

/mask = ([01X]+)|mem\[(\d+)\] = (\d+)/g

10進数を2進数に変換する

どうやって11 into 1011 , or 101 into 1100101 ?
JavaScriptでは、我々はtoString() 組み込みメソッドNumber オブジェクトプロトタイプ.
起動toString() 数で、引数として数を渡すと、指定されたベース、または基数で呼び出し元の番号を返すことを試みます.
したがって、呼び出しtoString() 議論で2 は10進数に変換します.

(11).toString(2)  // '1011'
(101).toString(2) // '1100101'

バイナリを10進数に変換する

どうやって逆を行うのか1011 into 11 ?
JavaScriptでは、parseInt() 数値メソッド.

バイナリの数値

バイナリ番号のベース

このように使えます.

parseInt('1011', 2)    // 11
parseInt('1100101', 2) // 101

我々のマスクと一致するためにスタートで番号をパディングすること

どうやって'000000000000000000000000000000001011' から1011 ?
JavaScriptでは、padStart() stringメソッド

新しい文字列の長さ.

それぞれの新しい空間に記入するのに用いられる文字

したがって、呼び出しpadStart() 文字列のバイナリ数を引数として表します36 and 0 , マスク文字列の長さにマッチできます:

'1011'.padStart(36,0)    // '000000000000000000000000000000001011'
'1100101'.padStart(36,0) // '000000000000000000000000000001100101'

文字列からバイナリ番号を解析する

どうやって11 から'000000000000000000000000000000001011' ?
ありがたいことに、我々は使用できますparseInt() 以下のように同じです.

parseInt('000000000000000000000000000000001011', 2) // 11
parseInt('000000000000000000000000000001100101', 2) // 101

適切な文字列を上書きする

どのように我々はこの計算を実行するか?

Start:
000000000000000000000000000000001011

Compare to:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X

End:
000000000000000000000000000001001001

適切な文字列を上書きする

Split the mask into an array of characters
For each character in the mask
  If the character is an 'X'
    Change it to the character at the same location in the padded, binary-represented decimal
  Else - the character is a '0' or '1'
    Keep the character
Join each character together to form a string again

以下はJavaScriptの例です

mask  = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X'
value = '000000000000000000000000000000001011'
value = mask.split('').map((c, i) => c == 'X' ? value[i] : c).join('')
//.     '000000000000000000000000000001001001'

完全に今：作業アルゴリズムを書く

Store the input as one long string of text
Find all matches within the string from the regular expression
Create a new object, mem
Create an empty string, mask
For each match
  If there is a match for the first of the three capture groups
    Re-assign mask the string from the first capture group
  Else
    Create or re-assign to the key in mem equivalent to the number from the second capture group the result of processing the number from the second capture group as follows:
      Convert the captured string to a number
      Convert it to a string from the number in base 2
      Extend the string from the start to become 36 characters long, filling in any spaces with 0s
      Create a copy of the string currently assigned to mask, such that:
        For each character an array containing the characters from the current string assigned to mask:
          If the character is an X
            Change it to the character in the same location from the padded binary version of the number
          Else - if the character is a 1 or 0
            Keep that character
        Join all characters to form a string again
      Parse the string as a number in base 2 to convert it to a decimal
Extract an array containing all values from mem
For each value in that array
  Accumulate a sum - starting at 0
Return the sum

シミュレータの構築

このシミュレータの私の意図は、変換プロセスの各部分を表示することでした

そして、すべての小数点の累積合計を表示するには

私は、1つの10進とマスクのデータ入力を可能にするために、またはいくつかのユニークなパズル入力の処理のためにそれを構築しました

Try the simulator!

第2部

ビットマスクが今回どのように機能するかを理解する

浮動ビットアルゴリズムの構築

ビットマスクが今回どのように機能するかを理解する

第1部X 記号化された透明性:パッド化されたバイナリ変換文字からの文字を保つ

さて、X メモリ内のアドレスに対して新たに変更された10進数を格納するための1つの追加値の分岐を示す

以下のように動作する代わりに:

mask:
000000000000000000000000000000X1001X

changing the 100 in
mem[42] = 100:
000000000000000000000000000001100100

to:
000000000000000000000000000000110010

次のように動作します.

mask:
000000000000000000000000000000X1001X

changing the 42 in
mem[42] = 100:
000000000000000000000000000001100100

to storing 100 to the following addresses:
000000000000000000000000000000011010
000000000000000000000000000000011011
000000000000000000000000000000111010
000000000000000000000000000000111011

私が見る命令は

Count the number of X's
Multiply 2 by the number of X's in the mask to determine the number of permutations
For each permutation
  Overwrite each character whose location corresponds to an 'X' in the mask with a 0 or 1

課題は

どのようなパターンは、0と1 sの順列の完全な範囲を生成するために存在しますか?

私はこのパターンに気づいた.

For 2 X's, the values are:
0..0
0..1
1..0
1..1

For 3 X's, the values are:
0..0..0
0..0..1
0..1..0
0..1..1
1..0..0
1..0..1
1..1..0
1..1..1

それらは、0から2(2 * n - 1)の2進数である.ここで、sは最大数として同じ数の文字に対して0で埋められたxsの数である

浮動ビットアルゴリズムの構築

Split the mask into an array of characters
  Accumulate an array of indices - starting as empty
    If the value is an 'X', add its index to the accumulating list
Multiply 2 by N number of X's and store in permutations
For i from 0 to permutations
  Convert the number to binary
  Pad it from the start with 0s to the length equivalent to the number of characters in the binary-converted number one less than permutations
  Split that number into an array of numbers
  Create a copy of the string currently assigned to mask, such that:
    For each character in an array containing the characters from the current string assigned to mask:
      If the character is an X
        Change it to the number in the array of numbers generated from i who's index matches that of the index of this character in the accumulated list of indices of only X characters
      Join all characters to form a string again
    Parse the string as a number in base 2 to convert it to a decimal
    Store in this new decimal address the value to the right side of the = on the same line from the input string

私のアルゴリズムの可視化を示します.

私の楽しい驚きには、そのアルゴリズムは、私のパズル入力のための正しい答えを生成!
私は、このパズルに既に費やしているどのくらいの時間を与えられた、これらの順列のそれぞれを示すためにシミュレータを更新することに興味はありません.

両方完成

シミュレータ作成

GIF作成

時間を移動する!