하룻밤의 모든 것

코드 출현 2015 9일차

1 부

공원 산책

작업 알고리즘 작성

공원에서 산책

오늘의 퍼즐은 쉬움 모드에서 13일차 같은 느낌입니다!

순열 목록 생성

각 A에서 B 점수까지 합산

가장 낮은 점수 식별

작동하는 알고리즘 작성

장소 및 점수 추출

입력의 각 줄은 다음 패턴을 따릅니다.

A to B = C

regex를 사용하는 대신 split()와 배열 분해를 사용하여 세 부분을 추출합니다.

let [A, ,B, ,C] = flight.split(' ')

장소 및 점수 사전 만들기

예제 입력의 경우:

London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141

다음과 같은 사전을 원합니다.

{
  London: { Dublin: 464, Belfast: 518 },
  Dublin: { London: 464, Belfast: 141 },
  Belfast: { London: 518, Dublin: 141 }
}

따라서 각 행에 대해 두 개의 키와 동일한 값을 설정해야 합니다.

dict[A][B] = +C
dict[B][A] = +C

전체적으로 내 reduce()는 다음과 같습니다.

const scores = input.reduce((dict, flight) => {
  let [A, ,B, ,C] = flight.split(' ')
  if (!(A in dict)) dict[A] = {}
  if (!(B in dict)) dict[B] = {}
  dict[A][B] = +score
  dict[B][A] = +score
  return dict
}, {})

가능한 경로 목록 생성

매우 편리한 JavaScript 라이브러리 js-combinatorics 를 다시 사용하겠습니다.

가능한 모든 대상 목록을 전달해야 합니다

.

Object.keys()를 사용하여 해당 목록을 생성하겠습니다.

const C = require('js-combinatorics')
const routes = [...new C.Permutation(Object.keys(scores))]

최단 경로 찾기

의사 코드 내 알고리즘:

For each possible route
  Accumulate a number - starting at Infinity - that should get smaller and smaller
  Set score to 0
  For each destination in the route, except the last
    Increment score by the value associated with the key corresponding to the next item that is a key inside the dictionary corresponding to the current item
  Return the smaller number between the accumulated number and score
Return the accumulated number

내 알고리즘, 애니메이션:


자바스크립트 내 알고리즘:

routes.reduce((shortest, route) => {
  let score = 0
  for (let i = 0; i < route.length - 1; i++) {
    score += scores[route[i]][route[i + 1]]
  }
  return Math.min(shortest, score)
}, Infinity)

정답을 생성했습니다!

2 부

Math.max()에 대한 Math.min() 및 0에 대한 Infinity 교환

두 가지 간단한 변경 사항

그리고 또 하나의 정답!

해냈어!!

두 부분 모두 해결했습니다!

조합 생성 라이브러리 및 reduce()에 대한 친숙함을 감안할 때 기록적인 시간 내에 !

이러한 퍼즐을 거꾸로 풀 때의 유일한 문제는 조합 테마의 퍼즐을 풀기가 점점 재미있어진다는 것입니다.

이제 막 9일차에 접어들었으니 연말이 되기 전에 적어도 하나는 더 나를 기다리고 있는 것 같은 기분이 든다.