식탁의 기사들

코드 출현 2015 13일차

1 부

또 다른 조합 퍼즐?!

가능한 조합은 몇 개입니까?

해당 콤보 생성기 라이브러리 활용

각자의 행복사전 만들기

오른쪽을 보고 왼쪽을 본 다음 추가

또 다른 조합 퍼즐?!

지금쯤이면 내가 지겨워할 거라고 생각할 수도 있겠지

그러나 이것은 올해 지금까지 다른 것들만큼 똑같이 흥미로워 보입니다!

얼마나 많은 조합이 가능합니까?

예제 입력에는 다음 4명이 포함됩니다.

First chair: 4 options
Second chair: 3 options
Third chair: 2 options
Fourth chair: 1 option

4 * 3 * 2 * 1
4!
24 combinations

내 퍼즐 입력에는 8명이 있습니다.

8!
40,320 combinations

따라서 최적의 좌석 배치를 찾기 위해 40,000개가 넘는 조합의 행복 점수를 결정해야 합니다.

해당 콤보 생성기 라이브러리 활용

이전 콤보 테마 퍼즐에서 도움을 얻기 위해 reddit Solution Megathread를 검색했습니다

.

한 JavaScript 솔버 게시물에서 그들은 편리한 라이브러리를 참조했습니다. js-combinatorics

이 퍼즐을 좀 더 쉽게 풀 수 있도록 사용하려고 합니다

.

라이브러리에는 Permutation 메서드가 있습니다. 이 메서드는 문자열을 받아들이고 해당 문자를 정렬할 수 있는 모든 방법의 모음을 반환합니다.

내 입력에서 각 사람의 첫 번째 이니셜을 가져와 문자열로 연결합니다.

const C = require('js-combinatorics')

// Example input: Alice, Bob, Carol, David
const arrangements = [...new C.Permutation('ABCD')]
console.log(arrangements.length) // 24

// Example input: Alice, Bob, Carol, David, Eric, Frank, George, Mallory
const arrangements = [...new C.Permutation('ABCDEFGM')]
console.log(arrangements.length) // 40320

환상적입니다! 각 수집에는 예상 계승 금액이 포함됩니다.

이제 이러한 컬렉션에 대한 계산을 어떻게 수행합니까?

각자의 행복사전 만들기

예제 입력에서 다음은 Alice의 점수입니다.

Alice would gain 54 happiness units by sitting next to Bob.
Alice would lose 79 happiness units by sitting next to Carol.
Alice would lose 2 happiness units by sitting next to David.

이 사전을 만들고 싶습니다.

{
  'A': {
    'B': 54,
    'C': -79,
    'D': -2
  }
}

각 줄에서 네 부분을 추출해야 합니다.

가족초성

gain 또는 lose

행복 단위 금액

인척의 이니셜

정규식을 사용할 수 있지만 각 줄의 단어 수가 같기 때문에 split()를 사용하고 관련 항목에 액세스합니다.

let [X, , sign, amount, , , , , , , Y] = line.split(' ')
X = X[0]
Y = Y[0]
sign = sign == 'gain' ? '+' : '-'
amount = Number(sign + amount)

그런 다음 적절한 키가 아직 없으면 생성하고 적절한 양을 설정해야 합니다.

JavaScript에서 내 전체 사전 생성 알고리즘:

input.reduce((dict, line) => {
  let [X, , sign, amount, , , , , , , Y] = line.split(' ')
  X = X[0]
  Y = Y[0]
  sign = sign == 'gain' ? '+' : '-'
  amount = Number(sign + amount)
  if (!(X in dict)) dict[X] = {}
  dict[X][Y] = amount
  return dict
}, {})

알고리즘은 예제 입력에 대해 이 사전을 생성합니다.

{
  A: { B: 54, C: -79, D: -2 },
  B: { A: 83, C: -7, D: -63 },
  C: { A: -62, B: 60, D: 55 },
  D: { A: 46, B: -7, C: 41 }
}

오른쪽을 보고 왼쪽을 본 다음 추가

지금까지:

좌석 배치의 각 순열

각 가족 구성원의 인접 가족 구성원의 행복 단위

수학을 할 시간입니다!

예제 입력의 첫 번째 순열 사용:

['A','B','C','D']

똑바로 봐:

A -> B: +54
B -> C: -7
C -> D: +55
D -> A: +46
-----------
        148

왼쪽을보다:

D <- A: -2
A <- B: +83
B <- C: +60
C <- D: +41
-----------
        182

그런 다음 다음을 추가하십시오.

        182
       +148
-----------
Total:  330 -> Optimal arrangement!

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


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

arrangements.reduce(
  (optimal, permutation) => 
    Math.max(
      optimal,
      permutation.reduce(
        (sum, seat, index, RA) => 
          sum += happiness[seat][RA[(index + 1) % RA.length]]
        , 0)
    + permutation.reverse().reduce(
        (sum, seat, index, RA) => 
          sum += happiness[seat][RA[(index + 1) % RA.length]]
        , 0)
    )
  , 0)

정답을 생성했습니다!

2 부

퍼즐에 나를 삽입

퍼즐 속에 나를 집어넣어

입력을 조작할 수 있지만 금기시되는 느낌이 듭니다

대신 프로그래밍 방식으로 나를 추가하겠습니다.

happiness['R'] = {}
for (let seat in happiness) {
  // Adding other family members' happiness units toward me
  happiness[seat]['R'] = 0
  // Adding my happiness units toward them
  happiness['R'][seat] = 0
}

9! 대신 8! 조합 생성:

const C = require('js-combinatorics')
const arrangements = [...new C.Permutation('ABCDEFGMR')]

프로그램을 다시 실행...

...정답을 다시 생성합니다!

해냈어!!

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

이전에 사용했던 조합 생성 라이브러리 활용!

그리고 배열을 순환 목록처럼 취급하는 요령이 있습니다!

파트 1에 비해 파트 2의 난이도 상승이 적어 조금 아쉬웠습니다.

처음부터 만든 조합 생성 알고리즘에 대한 스트레스 테스트를 의도한 것일까요?

그럼에도 불구하고 이것은 또 다른 재미있는 콤보 테마 퍼즐이었습니다!