순록 올림픽

코드 출현 2015 14일차

1 부

modulo의 운동

정답은... 몇 초 일찍?!

정답은... 정시에!

모듈로 연습

Comet can fly 14 km/s for 10 seconds, but then must rest for 127 seconds.

수학이 작동하는 방식:

주어진 10 + 127초 동안 혜성은 첫 번째10를 비행하고 다른 하나127를 쉬고 있습니다.

따라서 알고리즘은 다음과 같을 수 있습니다.

Set distance to 0
For i from 0 up to but not including the specified duration
  If the remainder after dividing i by the sum of seconds flying and resting is equal to 0
    For j from 0 up to but not including the seconds spent flying
      Increment distance by the km/s

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

// Inside input.reduce()
let distance = 0
for (let second = 0; second < target; i++) {
  if (second % (flying + resting) == 0) {
    for (let i = 0; i < flying; i++) {
      distance += kmps
    }
  }
}

이 알고리즘은 각 순록이 이동한 거리에 따라 최대 숫자를 누적하는 reduce() 내부에 있습니다.

예제 입력에 대한 정답을 생성합니다

.

하지만 내 퍼즐 입력에 대한 오답

정답은... 몇 초 일찍?!

흥미롭게도:

target에서 2503로 2501를 이동하면 정답이 생성됩니다!

왜 그런 겁니까?

...

정답은... 정시에!

오, 이유를 알 것 같습니다.

내 가장 안쪽for 루프가 매번 같은 횟수

만큼 증가합니다distance.

하지만 목표 초에 가까워지면 목표 초에 도달할 때까지 몇 초만 증가해야 하고distance 더 이상 증가하지 않아야 합니다

.

JavaScript에서 내 업데이트된 알고리즘:

let distance = 0
for (let second = 0; second < target; i++) {
  if (second % (flying + resting) == 0) {
    for (let i = 0; i < flying; i++) {
      if (second + i < target) {
        distance += kmps
      }
    }
  }
}

원하는 대로 올바른 목표 초에 정답을 생성합니다!

2 부

한 번에 모두가 아니라 전체적으로

일련의 루프

한꺼번에가 아니라 전체적으로

1부의 알고리즘이 각 순록의 경로를 개별적으로 완료합니다

.

이제 어떻게든 한 번에 1초씩 각 순록의 경로를 함께 완료해야 합니다

.

각 순록의 비행 시간(초) 목록을 생성하도록 알고리즘의 용도를 변경할 수 있습니다

.

별도의 루프를 사용하여 각 순록의 지점과 이동한 거리를 계산합니다

.

일련의 루프

첫 번째 루프는 km/s 및 초기 이동 거리 0과 함께 각 순록의 비행 시간(초) 목록을 생성합니다.

// Inside input.map()
let seconds_awake = []
for (let second = 0; second < target; i++) {
  if (second % (flying + resting) == 0) {
    for (let i = 0; i < flying; i++) {
      if (second + i < target) {
        seconds_awake.push(i + j)
      }
    }
  }
}
return { 
  kmps: kmps, 
  secs: seconds_awake, 
  distance: 0 
}

다음으로 각 순록의 점수를 추적할 배열이 필요합니다.

let points = new Array(input.length).fill(0)

마지막으로 레이스 및 포인트 수집 알고리즘:

For second from 0 to the target, again
  For each reindeer
    If second is a number in the list of seconds spend flying
      Increment distance by kmps
    Else, increment by 0
  Create a list of only the reindeer's distances travelled
  Calculate the furthest distance travelled
  For each point
    If the distance in the same position as point matches the furthest distance travelled
      Increment point by 1
    Else, increment by 0
Return the largest value in points

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

for (let second = 0; second < 2503; second++) {
  reindeer = reindeer.map(r => {
    r.distance += r.secs.includes(second) ? r.kmps : 0
    return r
  })
  let distances = reindeer.map(r => r.distance)
  let leader = Math.max(...distances)
  points = points.map((point, i) => {
    return point += distances[i] == leader ? 1 : 0
  })
}
return Math.max(...points)

처음에는 거리에 포인트가 추가된 것으로 잘못 생각했고 여전히 가장 큰 거리가 예상 답변이었습니다

.

그래서 제출한 첫 번째 답변이 너무 높았습니다

.

하지만 읽은 후 파트 2는 매 초마다 부여된 점수의 결과에만 신경을 썼습니다

.

위에 표시된 내 업데이트된 알고리즘이 정답을 생성했습니다!

해냈어!!

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

modulo를 활용하여 순록이 깨어 날아가는 시간을 초당 결정하는 방법을 이해하면 됩니다!

그리고 첫 번째 알고리즘을 이동 거리를 과도하게 증가시키지 않도록 수정했습니다!

그리고 포인트를 이동 거리와 결합하지 않도록 두 번째 알고리즘을 수정했습니다!

내 여정에서 이렇게 새로운 느낌을 주는 퍼즐을 만나는 것은 정말 놀라운 일입니다!

물론 익숙한 알고리즘 및 수학적 도구를 사용하여 풀었지만 퍼즐 자체는 지금까지 만난 다른 퍼즐과 다른 느낌이었습니다.

올해 하반기에는 내가 너무 익숙해진 몇 가지 주제에 대해 약간의 반전을 제공할 수 있기를 바랍니다.