교차 전선

코드 출현 2019 3일차

작업: X에 대해 풀기 여기서...

1 부

X = the Manhattan distance from the central port to the closest intersection

2 부

X = the fewest combined steps the wires must take to reach an intersection

예시 입력

R8,U5,L5,D3
U7,R6,D4,L4

다음을 나타냅니다.

두 세트의 방향, 각 와이어에 대해 하나씩

각 단계는 네 방향 중 하나를 나타냅니다.

1 부

정확한 정보: 방문한 모든 좌표 캡처

내 작업 알고리즘에 대한 서면 설명

내 작업 알고리즘의 시각적 묘사

약간 벗어났습니다: 방문한 모든 좌표를 저장하는 데이터 구조

나는 정확했다 : 모든 방문한 좌표를 캡처

두 와이어가 교차하는 정확한 지점을 식별하는 것이 제가 아는 유일한 방법입니다

.

고맙게도 2020년과 2021년의 퍼즐은 비슷한 문제를 제기했습니다...그래서 저는 이 알고리즘 작성에 익숙했습니다

.

내 작업 알고리즘에 대한 서면 설명

Split the input at the only newline character to create an array with two strings
  Split each string at each comma character to create nested arrays with strings

Create a legend mapping each of the four directions with an amount between -1 and 1 to adjust a current x,y coordinate

For each of the wires
  Initialize a coordinate at 0,0
  Initialize an array that will store stringified representations of the coordinates
  For each instruction in the wire's list of instructions
    Extract the first character as the direction
    For i from 1 to the integer associated with the direction
      Add to the array of coordinates a stringified representation of the current coordinate moved one step in the current direction
    Update the current coordinate so it matches the one represented by the last value in the array of coordinates
  Return the generated list of visited coordinates

Filter the first list of visited coordinates
  Only keep values that also appear in the second list of visited coordinates

Generate a list of numbers using the filtered list
  Each number will equal the sum of the absolute value of each visited coordinate's x,y positions

Sort the list in ascending order

Return the first number (the smallest number)

내 작업 알고리즘의 시각적 묘사

나는 조금 벗어났습니다 : 모든 방문한 좌표를 저장하는 데이터 구조

위의 알고리즘을 실행하는 데 거의 2분이 걸립니다. 이런!

왜 그렇게 오래 걸립니까?

방문한 좌표를 배열로 저장합니다

.

다른 와이어의 방문한 좌표 목록에서 각 좌표를 찾아 한 와이어의 방문한 좌표 목록을 필터링하려고 합니다

.

내 퍼즐 입력의 경우 첫 번째 와이어 목록은 ~150,000개 값입니다

.

이들 각각에 대해 내 프로그램은 일치하는 다른 목록(유사한 수량일 가능성이 있음)을 검색하려고 시도합니다

.

150,000번의 검색, 각각 0~150,000개의 값을 검사해야 함

부품에 거의 120초가 걸리는 것도 당연합니다

또 다른 JavaScript 솔버인 NullDev는 저와 비슷한 알고리즘을 작성했습니다. 한 가지 차이점이 있습니다.

내 알고리즘이 정렬된 방문 좌표 목록을 저장하기 위해 배열을 사용한 경우

그들의 알고리즘은 키를 문자열 좌표로, 값을 좌표를 방문할 때까지의 경로 길이로 사용하는 객체를 사용했습니다

.

NullDev의 알고리즘은 약 1초 안에 완료됩니다.

NullDev의 알고리즘이 왜 그렇게 빠릅니까?

필터링 단계는 방문한 좌표를 경로 길이에 매핑하는 개체 간에 일치하는 키를 찾습니다

.

100,000개 이상의 키가 있는 개체의 키를 찾는 작업은 100,000개 이상의 값이 있는 배열에서 일치 항목을 검색하는 것과 비교할 때 거의 즉각적입니다

.

이 퍼즐이 이러한 깨달음을 얻는 데 도움이 되어서 너무 기쁩니다.

2 부

배열 대신 개체를 사용하여 약간 수정한 작업 알고리즘에 대한 서면 설명

내 작업 알고리즘의 시각적 묘사

배열 대신 개체를 사용하여 약간 수정된 작업 알고리즘에 대한 서면 설명

Split the input at the only newline character to create an array with two strings
  Split each string at each comma character to create nested arrays with strings

Create a legend mapping each of the four directions with an amount between -1 and 1 to adjust a current x,y coordinate

For each of the wires
  Initialize a coordinate at 0,0
  Initialize an object, locations, that will map stringified representations of the coordinates to the length of the path by the time that coordinate is reached
  Initialize length at 0
  For each instruction in the wire's list of instructions
    Extract the first character as the direction
    For i from 1 to the integer associated with the direction
      Increment length by 1
      Add to locations a key whose label is a stringified representation of the current coordinate moved one step in the current direction, and whose value is set to length
    Update the current coordinate so it matches the most recently added key in locations
  Return locations

Create a list containing all the keys from the locations object generated from the first wire's visited coordinates
  Filter the list, keeping only values that are also keys in the locations object generated from the second wire's visited coordinates

Generate a list of numbers using the filtered list
  Each number will equal the sum of the length of each path at the shared coordinate value of both wires

Sort the list in ascending order

Return the first number (the smallest number)

내 작업 알고리즘의 시각적 묘사

시뮬레이터가 없습니까?

나는 시뮬레이터를 만들고 싶은 유혹을 받았다.

하지만 배의 경로를 그리는 비슷한 퍼즐을 위한 시뮬레이터를 만들었습니다.

그리고 두 알고리즘을 두 번 작성하고 GIF를 만들었을 때, 저는 이 퍼즐에서 벗어날 준비가 되었습니다.