쥐라기 퍼즐

Advent of Code 2020 Day 20

Try the simulator!


작업: X에 대한 해답, 그중에서...
제1부

X = the product of the four ID numbers of the four identified corner tiles

제2부분

X = the number of # characters that are not part of a sea monster pattern

샘플 입력

Tile 1234:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###

...more tiles

대표적인 기능은 다음과 같습니다.

몇 개의 작은 사각형 이미지 블록을 더 큰 사각형 이미지로 조합

섹션 1: 구석 타일 찾기

수동 작업 방법 설명

컴파일 작업 알고리즘

구축 시뮬레이터

이 작업을 수동으로 수행하는 방법 설명

네모난 벽돌

벽돌당 일치하는 모서리는 2/4개

각 타일은 서로 인접한 타일

에 맞게 회전하거나 뒤집어야 할 수 있습니다.
각 타일의 사변을 분석하다

Tile 1234:

    Side 1
  ..##.#..#.
  ##..#.....
S #...##..#. S
i ####.#...# i
d ##.##.###. d
e ##...#.### e
  .#.#.#..##
4 ..#....#.. 2
  ###...#.#.
  ..###..###
    Side 3

Due to the rotation and flipping caveat...

Side 1's match could be:
..##.#..#. or .#..#.##..

Side 2's match could be:
...#.##..# or #..##.#...

Side 3's match could be:
..###..### or ###..###..

Side 4's match could be:
.#####..#. or .#..#####.

주어진 한 쪽이 일치하는 것을 찾기 위해서, 다른 스티커 중 한 쪽만 일치하는 것을 가정하십시오.이 절차는 여러 타일의 측면이 일치하는 경우 더욱 복잡해집니다.

Compare the current side's string - both directions - with each of the four sides of each of the other input tiles
  If we find a match
    Record the tile name and side
    Break
  Else - there is no match
    Record the lack of match

네 개의 각괴를 분석한 타일

If a tile has 0 unmatched sides, it is an inner piece
If a tile has 1 unmatched side, it is an edge piece
If a tile has 2 unmatched sides, it is a corner piece

네 개의 각도 블록의 ID를 곱하여 섹션 1의 정답을 결정합니다.

작업 알고리즘 작성

메스꺼움: 만력 느낌

총량: 톤당 회로가 있음

쿨: 끊임없이 같은 수조로 변이

다행이다.그것은 예시적인 입력과 나의 입력을 위해 정답을 생성한다.

Split the input at each pair of new line characters to create an array of tile strings

Split each tile string at the new line character to change the string into an array of strings

Change each array of strings into an array with two elements:
  1. A string that stores the tile's 4-digit ID
  2. An array that stores four strings: each string representing the ordered set of . or # characters for a tile's four sides

Change each two-item array into an array with two elements:
  1. A string that stores the tile's 4-digit ID
  2. An array that stores the existence of - or lack thereof - a matching side from another tile...for each side of each tile

Change the array to only contain a subset of its items
  Where the second element - the array of four values - has, after filtering it for non-existent matches, only two items

Return the product of each of the remaining four values' number-coerced ID

이것은 나의 알고리즘이 어떻게 일을 하는지를 가시화하는 것이다


시뮬레이터 구축

대형 오징어 빙고와 유사하게 설치

나는 매번 교체할 때마다 한 변을 검사하는 것이지 매번 교체할 때마다 한 변을 실행하는 것이 아니다

각 타일의 측면 업데이트를 보는 것은 흥미롭다. 두 측면이 일치하지 않을 때 그 중 네 개의 타일이 녹색으로 변한다

스크립트에서 오류를 발견하는 데 도움이 됩니다.

JavaScript의 map 그룹 방법이 어떻게 작동하는지 생각납니다. 이것은 초기, 변경되지 않은 그룹의 모든 항목을 조작합니다..변경된 그룹만 끝에서 되돌려줍니다

Try the simulator!


섹션 2: 통합 실패

회전 및 뒤집기 어레이

정확하게 배열해 보기

성과를 경축하는 동시에 실패를 인정한다

반전 및 회전 문자열 배열

Flip vertically:
Reverse the array

Flip horizontally:
Split each string into an array
  Reverse the array
    Concatenate each element into a string

Rotate counter-clockwise:
For each string in the array
  Return a new string that is the concatenation of each character at the location in each string matching the index of the current string

Rotate clockwise:
For each string in the array
  Return a new string that is the concatenation of each character at the location in each string - of a reversed array - matching the index of the current string

이 부분들을 정확하게 배열해 보아라

내 알고리즘은 곧 통제력을 잃는다

Store an ordered list of each parsed tile
Store an ordered list of each pairing of tile ID and it's matching sides as calculated from Part 1
Store the size of the image by calculating the square root of the length of the list of tiles
Create two arrays of matching dimensions:
  1. To eventually hold each properly oriented tile array
  2. To eventually hold each tile id in its proper slot

Pick any of the four corner tiles to place in the top-left slot of the both grid arrays
  While it's top and left sides are not both marked as 'No match'
    Rotate it clockwise
    Shift the side instructions array such that the last item is moved to the front

For each row in the grid
  For each column in the row
    If in the top row:
      If proceeding to the right in the same row:
        Look-up the id of the tile to the left
        Store its matching tile from the list of tiles
        While its top side is not marked as 'No match'
          Rotate the tile clockwise
          Shift the side instructions array such that the last item is moved to the front
        If the characters along the right edge of the tile to the left don't match up with the characters along the left edge of the current tile
          Flip the current tile vertically
        Add the current tile and its id to the respective grid arrays
    If in the left-most column and not in the top row:
      Look-up the id of the tile above
      Store its matching tile from the list of tiles
      While its left and bottom sides are not marked as 'No match'
        Rotate the tile clockwise
        Shift the side instructions array such that the last item is moved to the front
      If the characters along the bottom edge of the tile above don't match up with the characters along the top edge of the current tile
        Flip the current tile horizontally
      Add the current tile and its id to the respective grid arrays

그게 내가 할 수 있는 일이야.

예시 입력을 테스트로 사용하면 왼쪽 아래에 있는 스티커를 정확하게 포지셔닝할 수 없어서 오른쪽 스티커를 정확하게 할 수 없다

만약에...else hell

성취를 경축하는 동시에 실패를 인정하다

해결된 1/2 부품

제1부분

을 위한 작업 시뮬레이터 1개

컴파일러 그룹 회전 및 회전 알고리즘 연습

충분한 지속성을 가지고 프로그래밍 방식으로 이미지 격자를 거의 채울 수 있다

나의 경솔한 코드에 대해 고장 제거를 하면 우아한 코드의 중요성을 충분히 인식할 수 있다

언젠가는 내가 너를 찾을 거야, 해괴야!

업데이트: 섹션 2 재시도: 성공!

내가 멈춘 곳에서 계속

퍼즐 형성, 현재 해괴 찾기

찾았다!아직 모자라서요.응?

시뮬레이터 a.k.a. 제3부분

계속해서 제가 아까 말씀드렸던 거.

나는 이 난제를 멈출 수 없다

예시 입력을 시뮬레이션하기 위해 작은 종이 조각을 만들었다

이렇게 하면 내 알고리즘이 멀지 않은 걸 볼 수 있어

코드를 자세히 분석하고 필요할 때 다시 작성해야 한다

다음은 내가 필요로 하는 타일 방향과 배치 알고리즘이다.

Setup algorithm:
Create an array to store the parsed tile strings
Complete Part 1 again to attain an array mapping each tile's side to between two and four other tiles' sides
Determine the full image's width/height by calculating the square root of either array
Create two more arrays:
  1. To store correctly placed and oriented tile strings in a multi-dimensional array
  2. To store the IDs of each correctly placed tile in a multi-dimensional array
Pick one of the four corner pieces - it doesn't matter which -  from the array mapping tile sides
Shift the elements in its side mapping array until the elements marking 'No match' are in locations 1 and 4 - the slots representing its top and left sides
Add an element to both of the new arrays:
  1. The tile string to the first array in the first nested array
  2. The ID to the first string in the first nested array
Create two legends:
  1. When attempting to align the next right-adjacent tile's known matching side with the recently placed tile, refer to an array mapping the side to the number of necessary clockwise moves to perform
  1. When attempting to align the next bottom-adjacent tile's known matching side with the recently placed tile, refer to an array mapping the side to the number of necessary clockwise moves to perform

Image-building algorithm:
Do as many times as the image is tall
  Do as many times as the image is wide
    As long as the current cell is not in the left-most location:
      Look-up the id of the tile in the cell to the left
      Look-up that tile's newly-shifted right-matching side
      Look-up the corresponding tile string
      Rotate the tile string clockwise - and shift its matching sides array - according to the legend until its identified matching side is in location 4 - representing left - of it's matching sides array
      If the strings of this tile's left side and the left adjacent tile's right side are reversed:
        Flip the tile's string vertically
        Swap the matching side array elements at locations 1 and 3 - top and bottom
      Add an element to both multi-dimensional arrays:
        1. The tile string of this tile
        2. The ID of this tile
    As long as the current cell is in the left-most location, and not in the top row:
      Look-up the id of the tile in the cell to above
      Look-up that tile's newly-shifted bottom-matching side
      Look-up the corresponding tile string
      Rotate the tile string clockwise - and shift its matching sides array - according to the legend until its identified matching side is in location 1 - representing top - of it's matching sides array
      If the strings of this tile's top side and the top adjacent tile's bottom side are reversed:
        Flip the tile's string horizontally
        Swap the matching side array elements at locations 2 and 4 - right and left
      Add an element to both multi-dimensional arrays:
        1. The tile string of this tile
        2. The ID of this tile

다음은 설정 및 이미지 생성 알고리즘의 시각화입니다.

마지막으로, 새로 채워진tilestring 그룹의 모든 요소를 합쳐서 재단해야 합니다.
다음은 JavaScript에서 단일하고 높은 방법으로 연결하는 작업입니다.

image.map(row => row.map(tile => {
        return tile.slice(1, 9).map(line => line.slice(1,9))
      })).map(row => row.reduce((accumulator, current) => {
        current.forEach((line, index) => {
          accumulator[index] += line
        })
        return accumulator
      }, Array(8).fill(null).map(el => '')).flat(1)).flat(1)

퍼즐이 형성되었으니 이제 해괴를 찾아가자.
지침에 따라 새로 만든 이미지의 문자열 연결 복사본에서 다음 모드의 각 인스턴스를 검색해야 합니다.

                  # 
#    ##    ##    ###
 #  #  #  #  #  #   

나에게 있어서 이것은 내가 가장 불편한 컴퓨터 과학의 주제인 정규 표현식을 섭렵해야 한다는 것을 의미한다.
고맙게도 RegExr 같은 도구는 이 과정을 재미있고 식견이 있으며 교육적 의의가 있게 만들었다.
다음은 이 문제를 해결하기 위해 내가 만든 정규 표현식입니다.

/.*(?<head>.{18}#.).*\n.*(?<body>#.{4}##.{4}##.{4}###).*\n.*(?<feet>.#.{2}#.{2}#.{2}#.{2}#.{2}#.{3}).*/g

나는 내가 임무를 완성하는 데 도움을 줄 수 있도록 replaceAll의 선택할 수 있는 함수 파라미터를 어떻게 사용하는지 연구하는 데 많은 시간을 들였다.
유감스럽게도, 나는 이 방법과 함수를 각각 사용해서 나의 정규 표현식에서 세 개의 포획 그룹을 업데이트하는 방법을 찾지 못했다.
반대로 나는 어쩔 수 없이 수동으로 조작했다.매우 수동적이다.
예를 들어, 내 정규 표현식이 이 하위 문자열에서 해괴를 발견했다고 가정하면, 예시 입력에서 나온 것이다

Searched this:
.#.#...#.###...#.##.##..
#.#.##.###.#.##.##.#####
..##.###.####..#.####.##

Matched this:
                    #   
  #    ##    ##    ###  
   #  #  #  #  #  #     

나의 목표는 프로그래밍을 통해 이 세 줄의 모든 해괴가 산열된 위치를 찾고 다른 비주기적인 문자로 그것들을 대체하는 것이다.
이를 위해 나는 반드시 다음과 같이 해야 한다.

Calculate the indexed location of the hash in the second line of the pattern, since it represents the left-most character in the pattern - and is therefore a reliable left edge
Use that number to create reference points for the first and third lines of the pattern from which to start
Additionally, store all three indexed first locations of the strings within which all three lines of the pattern reside - to know how far from which to indent
Furthermore, store the width of each line - since it now includes a new line character

Replace the joined string representing the image using a series of substring concatenations which craft a new string by joining each fragment of the most recent string with Os replacing each of the 18 characters in the matched sea monster pattern

그들을 찾았다!아직 모자라서요.응?
좋은 소식과 의외의 나쁜 소식:

좋은 소식:

예시 입력에서 이 알고리즘을 실행하면 정답이 생성됩니다. 273

나쁜 소식:

내 입력에서 이 알고리즘을 실행하면'너무 높은'오류 답이 나온다

지침에 따르면:you might need to rotate or flip your image before it's oriented correctly to find sea monsters이것은 한 방향의 이미지를 제외하고 모든 방향에 일치하는 해괴 도안이 0개라고 가정해 보겠습니다.
잘못했어요.
나는 몇몇 방향에 해괴 도안이 포함될 수도 있다는 것을 곧 발견했다.
그러나 한 방향은 더 실질적인 영향을 미칠 것이다.

더 나쁜 의외의 소식은:

내 정규 표현식에서 일치하는 항목을 모두 찾지 못했다

만약 두 모드 사이에 중첩이 있다면, 일치하는 세 줄 중 어느 곳이 다른 한 줄이나 여러 줄이고 문자열의 다른 곳이 수평이라는 것을 의미한다. 이것은 한 줄만 일치할 것이다

내가 정규 표현식을 사용한 경험이 부족하다는 것을 감안하면, 나의 엉터리 해결 방안은 무엇입니까?

이미지 문자열에서 정규 표현식을 몇 번 실행하고 일치하는 항목을 찾으십시오

그래서 나는 나의 정규 표현식 알고리즘을 하나의 순환에 포장하여 세 번 임의로 운행할 수 있다.
그리고 비올라!정답 생성...내가 그림 문자열을 정확하게 수동으로 위치를 정할 수만 있다면

시뮬레이터 a.k.a. 제3부분 건조
이 시뮬레이터에 대한 나의 기대:

버튼

을 클릭하여 1부와 2부를 순서대로 자동 실행

시뮬레이터 처리 속도를 조절하는 슬라이더

포함

섹션 2의 경우 이미지 문자열 재배치 버튼

버튼 중 하나를 누를 때마다 처리된 이미지

의 각 행에 대한 점진적 렌더링을 시뮬레이션합니다.

원본 이미지를 표시하지 않고 해괴만 표시

리디렉션과 처리된 이미지 문자열에서 찾은 최소 식별 해시 문자 수 - 제2부분

의 답안을 추적한다.
저는 #2밖에 없어요.
근데 괜찮아.
사용자에게 스피드 슬라이더를 제공하는 정책에서 메모리 유출을 발견했기 때문이다.
안타깝게도 나는 빈틈을 복구할 수 없다.

부팅 후 지속적인 실행 간격을 중지하고 제거할 수 없음clearInterval반대로 이 시뮬레이터에 대해서는 지금까지:

슬라이더를 뜯었어

나는 그다지 빠르지도 느리지도 않은 간격 지연을 하드코딩했다

나는'종점으로 이동'단추를 추가했다. 남은 순환을 반복해서 실행하고 간격을 지우고 삭제하며 제2부분

에 단계를 설정한다.

계속 전진할 때가 되었다.이번에 나는 자랑스럽게 서 있다!

나는 이 두 부분의 알고리즘에 대해 약 230줄

이 있다.

내 에뮬레이터 자바스크립트는 약 500줄

제가 이 퍼즐을 만드는 데 반주가 걸렸어요.

제1부는 1일 동안 구해와 시뮬레이션을 했다

제2부는 1일 동안 구해와 시뮬레이션을 했다

내 일을 완성하는 데 이틀이 걸렸다는 것을 나타낸다

고맙습니다. 이것은 감동적인 여정입니다. 지금까지 가장 도전적인 수수께끼이자 지금까지 제가 만든 가장 멋진 시뮬레이터입니다.

Try the simulator!