AoC 2015 - 9일차 - 여행하는 외판원!

9일차는 느슨하게 위장한 여행하는 세일즈맨 퍼즐입니다. 이에 대한 자세한 내용은 Wikipedia에서 확인할 수 있지만 간단히 말해서 우리가 하려는 것은 각 도시를 한 번씩 방문하여 여러 도시 간의 최단 거리를 계산하는 것입니다. 이러한 유형의 퍼즐을 최적화하는 쉬운 방법이 없는 것 같으므로 코드는 실제로 Itertools 라이브러리의 이점을 얻을 수 있습니다. 파트 1:



예제에는 3개의 도시가 있지만 퍼즐 입력에는 8개가 있습니다. 각 줄은 Faerun to Snowdin = 71와 같이 생겼으므로 필요한 것을 쉽게 풀 수 있습니다(원하지 않는 변수를 _에 버릴 수 있음을 기억하십시오).

with open('src/day09.txt') as f:
    for line in f:
        t1, _, t2, _, dist = line.split()
        distances[(t1, t2)] = int(dist)
        distances[(t2, t1)] = int(dist)
        towns.extend([t1, t2])
towns = set(towns)

각 쌍에서 내가 먼저 방문할 도시를 모르기 때문에 나중에 조회 시간을 절약하기 위해 거리를 두 번 저장하고 있습니다. 따라서 Faerun to Snowdin = 71 처리 후 distances{}에 다음이 포함됩니다.

distances{
    ('Faerun', 'Snowdin'): 71,
    ('Snowdin', 'Faerun'): 71
}

마지막 줄은 우리가 목록에서 캡처한 모든 도시 이름을 가져와 고유한 항목만 허용하는 세트로 압축합니다.

다음 단계는 itertools.permutations()를 사용하여 8개 도시의 모든 순열을 제공하는 것입니다(8! = 총 40,320개의 순열). 그런 다음 순열의 각 도시 쌍을 통과하고 완료한 후 총계를 저장하는 경우입니다.

파트 1에 대한 답은 계산된 거리에서 가장 작은 숫자입니다.

perms = list(permutations(towns))
route_lengths = []
for perm in perms:
    route_length = 0
    for town in range(len(perm)-1):
        route_length += distances[(perm[town], perm[town+1])]
    route_lengths.append(route_length)
print(min(route_lengths))

파트 2에 무엇이 있는지 누가 알 수 있기 때문에 거리 카운터 대신 목록을 사용했습니다. 그리고 확실히:



파트 2를 매우 쉽게 만드는 방식으로 솔루션을 실제로 코딩했을 때 멋진 느낌이 들었습니다. 이것은 궁극적인 예에 ​​관한 것입니다.

print(max(route_lengths))

그리고 끝났습니다! 우리는 이미 우리가 필요한 것을 계산했고, 그것을 찾아보기만 하면 됩니다...

나는 megathread 에서 각 순열에서 마을 사이의 거리를 합산하는 이 멋진 한 줄과 같은 약간의 골프를 보았습니다.

route_length = sum(distances[(t1, t2)] for t1, t2 in zip(perm, perm[1:]))

이로 인해 zip() 함수를 좀 더 살펴보고 싶었지만 내 코드에서 시도했을 때 전반적으로 약 10배 더 느리게 실행되었습니다. 이것은 내가 한 줄짜리는 꽤 영리하지만 항상 가장 빠르거나 읽기 쉬운 것은 아닙니다(예: 유지 관리).