투명 종이 접기

코드 2021의 출현 13일차

시뮬레이터를 사용해보십시오

X에 대해 풉니다. 여기서:

X = an eight-letter code

입력:

여러 줄 문자열

그것은 나타낸다

한 장의 점을 나타내는 x,y 좌표 목록

접기 지침의 순서 목록

접는 요령?

각 명령은 x 또는 y 축을 따라 가상의 종이 조각을 반으로 '접습니다'

.

접을 때마다 좌표 영역이 절반으로 줄어듭니다

.

마지막 접기가 완료되면 겹치는 점이 8개의 대문자를 나타내는 패턴으로 정렬됩니다.

...#..#..#.   #.##.|#..#.   #####   O
....#......   #...#|.....   #...#
...........   .....|#...#   #...#
#..........   #...#|.....   #...#
...#....#.#   .#.#.|#.###   #####
...........   .....|.....   .....
........... ^ .....|.....   .....
----------- |
........... |    <<---
........... |
.#....#.##.
....#......
......#...#
#..........
#.#........

초기 알고리즘 과제

'종이'의 너비와 높이 결정

각 '접기' 수행

너비와 높이

모든 x 좌표를 수집하고 최대값을 결정합니다. y에 대해서도 동일하게 수행하십시오.

각 접기가 중간점에 있으므로 각 변의 길이는 각 축의 첫 번째 접기 값이어야 합니다...두 배...더하기 1: 배열 길이 5의 중간점은 2: 2 * 2 + 1 = 5 ;

끔찍한 시간 및 공간 복잡성으로 각 '접기' 수행

Setup:
  Create a 2D array
  Fill it with `.` to indicate transparent cells
  For each coordinate, update the corresponding cell's value in the array  to `#` to indicate a dot

Fold:
  If instruction is to fold vertically, bottom-over-top:
    For each row in the array (below the fold line)
      For each cell in the row
        If the value in the cell equally far from - and on the opposite side of - the fold line has a #:
          Continue
        Else if it has a . and the value in this cell has a #:
          Replace the cell's value with this one's
    Copy the array, including only the first half of rows
  If instruction is to fold horizontally, right-over-left:
    For each row in the array
      For each cell in the row (right of the fold line)
        If the value in the cell equally far from - and on the opposite side of - the fold line has a #:
          Continue
        Else if it has a . and the value in this cell has a #:
          Replace the cell's value with this one's
    Copy the array, including only the first half of cells in each row

이것은 내 입력에 대한 정답을 생성하지 못했습니다.

나는 파트 1에 대한 답을 생성하는 다른 알고리즘을 생각할 수 없었습니다. 한 번 접은 후 페이지의 점 수를 결정합니다.

웅변적인 솔루션에 대한 간략한 검색

JavaScript 솔버 Pandicon의 솔루션을 보자마자 더 일찍 보지 못한 부끄러움에 머리를 긁적였습니다!

너비와 높이를 잊어 버리십시오.

이 문제를 풀기 위해 용지의 너비와 높이를 알 필요는 없습니다!

2D 배열 추적은 잊어라

명령 축을 기반으로 각 쌍에서 올바른 좌표의 제자리 업데이트를 수행할 수 있습니다!

각 fold는 가상의 종이의 너비와 길이에 관계없이 동일한 N 연산입니다

마지막fold 이후에 용지 크기는 일련의 점으로 구성된 8개의 대문자를 포함할 만큼 충분히 작아서 렌더링하는 데 전혀 '비용'이 들지 않습니다

.

현명한 방법으로 접기 수행

If the fold is along the x axis (right over left):
  If the x coordinate is greater than the midpoint's value:
    Update the x coordinate's value to the difference of:
      The midpoint's value and
      The absolute value of the result from subtracting:
        The x coordinate's value from the midpoint's value

If the fold is along the y axis (bottom over top):
  If the y coordinate is greater than the midpoint's value:
    Update the y coordinate's value to the difference of:
      The midpoint's value and
      The absolute value of the result from subtracting:
        The y coordinate's value from the midpoint's value

복잡해 보이지만 간단하게 표현하면 다음과 같다.

target_xy = (this_xy > coord) ? coord - Math.abs(coord - this_xy) : target_xy

종이 접기를 실시간으로 관찰

2부 퍼즐을 풀고 난 후 코드가 6행 40열에 걸쳐 있음을 발견했습니다

퍼즐러의 입력을 받아들이고 필요한 접기를 한 번에 한 단계씩 수행할 수 있는 웹 앱을 만들고 싶었습니다

왼쪽 상단 6개 행과 해당 행 내 40개 셀만 표시합니다

.

접을 때마다 # 접기

에서 나타나는 결과로 더 많은dots가 나타납니다.

마지막으로 접을 때 코드가 사용자에게 표시됩니다.

시뮬레이터를 사용해보십시오

교훈

말 그대로 퍼즐을 풀려고 하지 마세요. 대신 각 단계에서 필요한 최소한의 정보에 대해 비판적으로 생각하십시오

.

게임 영역 크기에 대한 지침에서 단서를 찾으십시오. 그런 다음 그것이 중요한지 다시 한 번 생각해 보십시오!

중간점을 기준으로 현재 셀에서 등거리에 있는 셀을 찾기 위한 편리한 공식