コンパスキューブ

コード2020日17の出現

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

X = the number of cubes in an active state after 6 cycles

例入力

.#.
..#
###

表す

アクティブのキューブ# または不活発な. 州

無限3次元格子内のキューブの3 x 3 x 1領域

26隣接キューブの可視化

Top-down view of a center cube's neighboring cubes

Top     Middle  Bottom
***     ***     ***
***     * *     ***
***     ***     ***

9 * 3 - 1 = 27 - 1 = 26

状態変更条件

Stay active if:
  Count of neighbors in active state is 2
  or Count of neighbors in active state is 3

Stay inactive if:
  Count of neighbors in active state is not 3

Otherwise, maintain current state

第1サイクルのためのグリッドの可視化

Input:

.#.
..#
###

As cube:

Top     Middle   Bottom
  .       .        .
 . .     # #      . .
. . .   . . #    . . .
 . .     . #      . .
  .       #        .

Becomes:
#.#
.##
.#.

Wait. What? No it doesn't!

For example:
- the top-left cube is inactive
- there is only one active cube adjacent to it
- so it stays inactive
- but the example diagram suggests it switches to active

自分の頭の傷の後、私はAdvent of Code Sub-Reddit's Solution Mega-thread このパズル.
ありがたいことに、コミッショナーの一人が私の混乱を共有しました.

どのように、5つのアクティブな隣人で、中間立方体はアクティブになります-規則が不活発な立方体が正確に3つの活発な隣人を必要とすると述べるとき、状態を変えます?

よりありがたいことに、回答者は、例のダイアグラムが描くと思うことに反して、入力の中のドットによって表される立方体がz=0 ダイヤグラムafter 1 cycle .
私はそれを引き出す必要があった.

Input:
.#.
..#
###

Just those 9 cubes become:
...
#.#
.##

But the grid is infinite...
...so we must expand our view

Input expanded:
.....
..#..
...#.
.###.
.....

All 25 cubes become:
.....
.....
.#.#.
..##.
..#..

したがって、z=0 レイヤーオブレイヤーAfter 1 cycle 今は理にかなっている.
著者は、すべてのアクティブキューブを包含する、そのレイヤの3 x 3部分を表示することを選んだ.

#.#
.##
.#.

元の3 x 3部分の代わりに:

...
#.#
.##

ミニミッション

ルールの理解を確認する

少なくとも1つのサイクルの新しい州を再確認してください

拡張立方体を表現するためのデータ構造の構築方法の考察

Input:
.#.
..#
###

As array:
[['.','#','.'],
 ['.','.','#'],
 ['#','#','#']]

As middle layer of a 3x3 cube:
[[['.','.','.'],
  ['.','.','.'],
  ['.','.','.']],
 [['.','#','.'],
  ['.','.','#'],
  ['#','#','#']],
 [['.','.','.'],
  ['.','.','.'],
  ['.','.','.']]]

As middle layer of a 5x5 cube:
[[[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’#’,’.’,’.’],
  [‘.’,’.’,’.’,’#’,’.’],
  [‘.’,’#’,’#’,’#’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]]]

すべての26隣接キューブをチェックする

For x as each of these three relative positions:
[-1,0,1]

Check all 9 cubes along [y, z] axes according to these relative positions:
[-1,-1]
[ 0,-1]
[ 1,-1]
[-1, 0]
[ 0, 0]
[ 1, 0]
[-1, 1]
[ 0, 1]
[ 1, 1]

Except [0,0] if x is 0

So, nested [-1,0,1] loops?

私は、同時に完全であると感じます.
それは1日のアルゴリズム思考のために十分です.
はい、それを返します.

Part 1アルゴリズムの擬似符号における第一パス

Setup:
1. Process the input into an array of arrays of binary values:
  Split the input on each new line character
  Split each string into an array of characters
  Coerce each # and . character into a 1 and 0 respectively
2. Add padding to the array so it gains a 1-element-sized border
3. Create two additional layers of equal size - filling both with all 0 values

セットアップアルゴリズムの可視化の試み

Before 1:
.#.
..#
###

After 1:
[[0,1,0],
 [0,0,1],
 [1,1,1]]

After 2:
[[0,0,0,0,0],
 [0,0,1,0,0],
 [0,0,0,1,0],
 [0,1,1,1,0]
 [0,0,0,0,0]]

After 3
[[[0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
  [0,0,0,0,0]],
 [[0,0,0,0,0],
  [0,0,1,0,0],
  [0,0,0,1,0],
  [0,1,1,1,0]
  [0,0,0,0,0]]
 [[0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
  [0,0,0,0,0]]]

Main loop:
1. Add padding in all three dimensions, turning the current array into the core of a 1-element-greater-sized shape
2. Keeping scope only to the new core, check each cube's 26 adjacent cubes, tracking the tallies of active cubes
3. Change the state of any cubes that meet the criteria

主ループアルゴリズムの可視化の試み

End of setup:
[[[0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
  [0,0,0,0,0]],
 [[0,0,0,0,0],
  [0,0,1,0,0],
  [0,0,0,1,0],
  [0,1,1,1,0]
  [0,0,0,0,0]]
 [[0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
  [0,0,0,0,0]]]

After 1:
[[[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,1,0,0,0],
  [0,0,0,0,1,0,0],
  [0,0,1,1,1,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]]]

After 2:
[[[0,0,0,0,0],
  [0,0,0,0,0],
  [0,!,0,0,0],
  [0,0,0,!,0]
  [0,0,!,0,0]],
 [[0,0,0,0,0],
  [0,0,!,0,0],
  [0,!,0,1,0],
  [0,!,1,1,0]
  [0,0,!,0,0]]
 [[0,0,0,0,0],
  [0,0,0,0,0],
  [0,!,0,0,0],
  [0,0,0,!,0]
  [0,0,!,0,0]]]

After 3:
[[[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,1,0,0,0,0],
  [0,0,0,0,1,0,0],
  [0,0,0,1,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,1,0,1,0,0],
  [0,0,0,1,1,0,0],
  [0,0,0,1,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,1,0,0,0,0],
  [0,0,0,0,1,0,0],
  [0,0,0,1,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]]]

最後に

Repeat main loop 6 times
Count the number of 1s across all arrays
Return the count

パート1 :実際のアルゴリズムの記述

単一原点キューブのすべての隣接するキューブをチェックする

スイッチを必要とするキューブのリストの生成

余分な1要素サイズのラッパーで配列をパディングする

最初のステップ最後:最初のコンウェイキューブを生成する

パート1に対する私の完全作業アルゴリズムの概要

パート1の旅

シミュレータ?第二部

単一原点キューブのすべての隣接するキューブをチェックする

Starting from the 3-element list `[-1,0,1]`
  Generate a flattened 27-element list, where each element -  except 1: at the origin point `[0,0,0]` - contains the relative coordinates of all 26 adjacent cubes.

For each relative coordinate
  Look-up the value in the 3D array at that location
  And replace the coordinate with that value

JavaScriptで書かれたアルゴリズムはこちら

const adjacents = [-1,0,1].flatMap(
  x => [-1,0,1].flatMap(
    y => [-1,0,1].map(
      z => [x,y,z].every(el => el == 0) 
        ? null : [x,y,z])))
  .filter(el => el != null)

const checkAdjacentCubes = ([X,Y,Z] = coordinate, cube) =>
  adjacents.map(([x,y,z] = c) => cube[X + x][Y + y][Z + z])

スイッチを必要とするキューブのリストの生成

Create an empty list of cubes needing switched
For each layer of the cube except the first and last
  For each row except the first and last
    For each column except the first and last
      Generate the list containing all adjacent cubes' values
      Filter it to only include active cubes
      Return and store the count of active cubes
      Perform the rule checking and, if it passes given this cube's state:
        Add to the coordinates of this cube to the list
For each coordinate in the list
  Switch the value at that coordinate from 0 to 1 or vice versa

JavaScriptで書かれたアルゴリズムはこちら

let switchers = []
for (let X = 1; X < grid.length - 1; X++) {
  for (let Y = 1; Y < grid[X].length - 1; Y++) {
    for (let Z = 1; Z < grid[X][Y].length - 1; Z++) {
      let actives = checkAdjacentCubes([X,Y,Z], grid)
                      .filter(el => el == 1).length
      grid[X][Y][Z] == 1 
        ? [2,3].includes(actives) 
        ? null : switchers.push([X,Y,Z]) :
        actives == 3 ? switchers.push([X,Y,Z]) : null
    }
  }
}
switchers.forEach(
  ([X,Y,Z] = s) => grid[X][Y][Z] = 1 - grid[X][Y][Z]
)

余分な1要素サイズのラッパーで配列をパディングする

Generate a template array that is two elements wider and taller than a source array
Create two independent copies to eventually act as 'buns' sandwiching the original array

For each row in each nested array
  Insert a 0 at the beginning and end of the row
For each nested array
  Insert an array filled with 0s and matching the new length of each row at the beginning and end of the array
Insert the 'buns' at the beginning and end of the outer-most array

JavaScriptで書かれたアルゴリズムはこちら

const padArray = (RA) => {
  let template = new Array(RA[0].length + 2)
    .fill(new Array(RA[0][0].length + 2).fill(0))
  let topPlane = template.slice().map(r => r.slice())
  let bottomPlane = template.slice().map(r => r.slice())
  RA = RA.map(
    plane => plane.map(
      row => [0, ...row, 0]))
    .map(plane => {
      let template = new Array(plane[0].length).fill(0)
      let topRow = template.slice()
      let bottomRow = template.slice()
      return [topRow, ...plane, bottomRow]
  })
  RA.unshift(topPlane) && RA.push(bottomPlane)
  conway = RA
}

最初のステップ最後：最初のコンウェイキューブを生成する

Enclose in an array the result of the following:
  Process the input as a string
  Replace all '.' characters with 0s
  Replace all '#' characters with 1s
  Split the string at each new line character
  For each string
    Split the string at each character
    Coerce to a number: 0 or 1

JavaScriptで書かれたアルゴリズムはこちら

let conway = [
  fs.readFileSync('input.txt', 'utf-8')
  .replaceAll(/\./g,0)
  .replaceAll(/#/g,1)
  .split('\n')
  .map(line => line.split('').map(Number))
]

パート1に対する私の完全作業アルゴリズムの概要

Generate the conway cube from the input
Generate the list of 26 adjacent cube relative coordinates
Pad the conway cube

Do 6 times:
  Pad the conway cube
  Switch the appropriate cubes
    Check all adjacent cubes of each cube - except the outer-most layer
    Track which cubes need to be switched
    Perform the switch

Return the count of cubes who's state is active - a.k.a. 1

カウント表示

console.log(conway.flat(3).filter(el => el == 1).length)

パート1の旅

例証が示すものを認識しない欲求不満から..

...理解に向かって、戦略を開発し、いくつかの小さなアルゴリズムを実装する私の方法を記録する.

...正しい答えを生成する

私はかなり素晴らしい感じです!

シミュレータ?第二部

シミュレーター:私はちょうど1つを作る動機を感じていません、特に、それは多次元配列をテキストのいくつかの積み重ねられて歪んだ面に翻訳することが多くの仕事であるように思えます.もう一つの時間.

第二部まあ、私は見なければならない.正しい?

第2部

それで、私はちょうどもう1つの入れ子になった配列を説明する必要がありますか?

一度に一つのサブルーチンを試してみましょう

80隣接するキューブの相対座標を識別します.

const adjacents = [-1,0,1].flatMap(
  x => [-1,0,1].flatMap(
    y => [-1,0,1].flatMap(
      z => [-1,0,1].map(
        w => [x,y,z,w].every(el => el == 0) 
        ? null : [x,y,z,w])))
      )
  .filter(el => el != null)

作品!
すべての80の隣接したキューブをチェックしてください

const checkAdjacentCubes = ([X,Y,Z,W] = coordinate, cube) =>
  adjacents.map(([x,y,z,w] = c) => cube[X + x][Y + y][Z + z][W + w])

動作するはずです!
すべてのフラグを有効にします.

const switchCubes = () => {
  let switchers = []
  for (let X = 1; X < conway.length - 1; X++) {
    for (let Y = 1; Y < conway[X].length - 1; Y++) {
      for (let Z = 1; Z < conway[X][Y].length - 1; Z++) {
        for (let W = 1; W < conway[X][Y][Z].length - 1; W++) {
          let actives = checkAdjacentCubes([X,Y,Z,W], conway)
                        .filter(el => el == 1).length
          conway[X][Y][Z][W] == 1 
            ? [2,3].includes(actives) 
            ? null : switchers.push([X,Y,Z,W]) :
            actives == 3 ? switchers.push([X,Y,Z,W]) : null
        }
      }
    }
  }
  switchers.forEach(([X,Y,Z,W] = s) => conway[X][Y][Z][W] = 1 - conway[X][Y][Z][W])
}

動作するはずです!
パッドを配列

???

ここでは、最も難しい部分、私はかなり把握できなかった

あまりに多くのネストした配列

私は、私のすべての連鎖呼び出しによって混乱しましたArray().fill.map() and slice()

ああ,まあ.
私はこの仕事をまだ誇りに思っている.
そして、少なくとも第1部を解決する.特に、パート2を潜在的に解決するために私をよくセットアップした方法で.
時間、最後に移動する!