코드 2020의 출현:NetworkX의 20일째,Python의Scipy 상호 관련
61084 단어 pythonadventofcode
1부 도전
Link to challenge on Advent of Code 2020 website
당면한 도전은 같은 이미지 블록을 촬영하고 경계선을 정확하게 맞추는 것이다.이미지 처리에서 이것은 모자이크 조립 문제이다. 예를 들어 항성의 망원경 이미지를 조립하고 대형 문서의 모자이크를 조립하는 데 사용된다(예를 들어 종이 부서진 문서의 법의학 재건 중).다중 뷰 형상, 촬영 측정, 단일 추정 등의 이미지 처리 영역도 있는데 이것은 이런 이미지 처리를 하는 것과 관련이 있지만 3D와 관련된다(이것은 내가 몇 년 동안 사용해 온 것이다).
불행하게도 저는 무인기 사진에서 3D 장면을 재구성하는 작업 지식이 도움이 되지 않았습니다. 왜냐하면 우리의 분야는 주로 3D 구조를 재구성하는 것이지 이런 일치가 아니기 때문입니다.그래서 우리는 기초로 돌아왔다.
데이터 가져오기
데이터는 17일째 데이터와 비슷하기 때문에 우리는 유사한 방식으로 데이터를 가져오고numpy의 view() 방법으로 텍스트를 분할합니다.우리는python의 해구문법 k, *v, _ = some_array을 사용하여 일부 수조를 분해하여 k이 첫 줄을 보존하고 _이 마지막 줄을 보존하며 v이 중간의 모든 내용을 보존하도록 한다.입력을 그림 블록, 제목으로 분해하고, 줄 바꾸기를 제거할 수 있습니다.정규 표현식을 조금 뿌려서 타일 ID를 제거하십시오:
입력 데이터:
Tile 2311:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###
Tile 1951:
#.##...##.
#.####...#
.....#..##
#...######
.##.#....#
.###.#####
###.##.##.
.###....#.
..#.#..#.#
#...##.#..
<snip>
코드:
import re
import numpy as np
data = open("input.txt").read().splitlines()
tiles = {int(re.sub(r"Tile (\d+):", r"\1", k)): np.array(v).view('U1').reshape(10, 10) for k, *v, _ in np.array(data).reshape(-1, 12)}
출력(tiles개)
{2311: array([['.', '.', '#', '#', '.', '#', '.', '.', '#', '.'],
['#', '#', '.', '.', '#', '.', '.', '.', '.', '.'],
['#', '.', '.', '.', '#', '#', '.', '.', '#', '.'],
['#', '#', '#', '#', '.', '#', '.', '.', '.', '#'],
['#', '#', '.', '#', '#', '.', '#', '#', '#', '.'],
['#', '#', '.', '.', '.', '#', '.', '#', '#', '#'],
['.', '#', '.', '#', '.', '#', '.', '.', '#', '#'],
['.', '.', '#', '.', '.', '.', '.', '#', '.', '.'],
['#', '#', '#', '.', '.', '.', '#', '.', '#', '.'],
['.', '.', '#', '#', '#', '.', '.', '#', '#', '#']], dtype='<U1'),
1951: array([['#', '.', '#', '#', '.', '.', '.', '#', '#', '.'],
['#', '.', '#', '#', '#', '#', '.', '.', '.', '#'],
['.', '.', '.', '.', '.', '#', '.', '.', '#', '#'],
['#', '.', '.', '.', '#', '#', '#', '#', '#', '#'],
['.', '#', '#', '.', '#', '.', '.', '.', '.', '#'],
['.', '#', '#', '#', '.', '#', '#', '#', '#', '#'],
['#', '#', '#', '.', '#', '#', '.', '#', '#', '.'],
['.', '#', '#', '#', '.', '.', '.', '.', '#', '.'],
['.', '.', '#', '.', '#', '.', '.', '#', '.', '#'],
['#', '.', '.', '.', '#', '#', '.', '#', '.', '.']], dtype='<U1'),
일치 타일
타일과 일치하기 위해서, 우리는 모든 가장자리를 끌어내어 타일의 다른 가장자리와 비교해야 한다.문제는 말하지 않았지만 잘 어울린다!
경계 ID를 생성하려면 tile의 2D 배열에서 슬라이스를 제거하고 문자열로 변환합니다.예를 들어, 타일 2311의 오른쪽 가장자리는 다음과 같은 방법으로 얻을 수 있습니다.
"".join(tiles[2311][..., -1])
출력
'...#.##..#'
그러나 타일이 뒤집힐 때 이 경계를 처리할 수 있어야 한다.python의 확장 슬라이스 표현을 사용하여 뒤로 슬라이스할 수 있습니다.
"".join(tiles[2311][..., -1][::-1])
출력
'#..##.#...'
오른쪽 가장자리는 색인 (..., -1)...(python의 생략호 대상)은 "이 축의 값을 따라", -1은 "이 축의 마지막 색인"을 나타낸다.편의를 위해 4개의 모서리를 하나의 원조에 저장할 수 있습니다.
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
우리는 포 순환에서 그것들을 교체할 수 있다.우리도 그것들의 뒤집기 형식이 필요하기 때문에, 우리는 더블 for loop이나itertools를 사용할 수 있다.product() 함수:
from itertools import product
for (i, j), f in product(edges, (1, -1)):
border_id = "".join(tile[i, j][::f])
이 주기는 4개의 모서리 중 각 모서리의 8개 조합과 2개의 반전 방향의 각 조합을 생성합니다.
각각의 border id에 대해, 다음에 border id를 다시 볼 때, 우리는 두 개의 스티커를 일치시키고, 모든 일치하는 도형을 만들 수 있도록 스티커 이름과 함께 사전에 놓을 것입니다.저는 networkx 라이브러리를 다시 사용했습니다. 저는 이 시리즈에서 이 라이브러리를 광범위하게 사용했습니다.
import networkx as nx
from itertools import product
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
borders = {}
graph = nx.Graph()
for tile_name, tile in tiles.items():
for (i, j), f in product(edges, (1, -1)):
border_id = "".join(tile[i, j][::f])
if border_id in borders:
graph.add_edge(borders[border_id], tile_name)
else:
borders[border_id] = tile_name
우리는 생성된 도형을 시각화할 수 있다. 실제적으로 이 난제를 해결했고 배열이 어떤 것인지를 직접 그렸다.
pos = nx.nx_agraph.graphviz_layout(graph)
nx.draw(graph, pos=pos, node_color="lightgrey", edge_color="grey", node_size=50, with_labels=True)
(내 퍼즐에서 입력)
도전은 네 개의 뿔의 ID를 곱해야 한다.우리는 실제로 이 그림에서 그것들을 읽을 수 있다.
그러나 두 모서리만 있는 그림의 노드를 보면서 구석점을 찾을 수도 있습니다.
from math import prod
print("prod", prod(tile for tile in graph if len(graph[tile]) == 2))
이 섹션의 전체 코드에 도전합니다.
import numpy as np
import networkx as nx
from itertools import product
from math import prod
import re
data = open("input.txt").read().splitlines()
tiles = {int(re.sub(r"Tile (\d+):", r"\1", k)): np.array(v).view('U1').reshape(10, 10) for k, *v, _ in np.array(data).reshape(-1, 12)}
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
borders = {}
graph = nx.Graph()
for tile_name, tile in tiles.items():
for (i, j), f in product(edges, (1, -1)):
border_id = "".join(tile[i, j][::f])
if border_id in borders:
graph.add_edge(borders[border_id], tile_name)
else:
borders[border_id] = tile_name
print("prod", prod(tile for tile in graph if len(graph[tile]) == 2))
도전의 두 번째
어머, 세상에, 이거 큰 거야.이 도전은 여러 단계를 포함한다.이제 우리는 타일의 도형이 생겼으니, 우리는 먼저 이 타일을 하나의 그림으로 다시 조합해야 한다.일단 조립이 끝나면 테두리는 반드시 잘라내야 한다.그리고 우리는 반드시 그림에서 해괴의 출현을 찾아야 한다.그리고 이미지의 나머지 부분이 몇 개의'#'문자로 구성되어 있는지 찾아냈습니다...
타일을 다시 그림으로 조립하다
이것은 지금까지 가장 지루한 걸음이다.지금까지 우리는 어느 타일이 어느 다른 타일에 연결되었는지, 그리고 어느 경계에 연결되었는지 알고 있기 때문에 이론적으로 우리는 모든 타일이 어느 길로 올라가야 틈새 없이 연결될 수 있는지 정확하게 계산할 수 있다.불행하게도, 이것은 너무 많은 기하학적 기교를 필요로 하고, 나는 어느 방향, 회전, 회전을 둘러싸고 타일을 그릴 수 없다. 왜냐하면 어느 경계가 일치하는지, 그리고 연결된 타일의 전체적인 회전과 회전을 알고 있기 때문이다.
그래서 나는 타일 한 조각을 퐁당 소리를 내고 4개의 가장자리 중 1개를 다음 타일의 8개 가능한 방향과 만력으로 일치시켰을 뿐이다. 그 중 하나만 일치할 수 있다는 것을 알았다.그것은 여전히 선형 시간 해산으로 평균 16배 느리다.
이 점을 하려면 타일의 8개 방향을 교체할 수 있어야 하기 때문에 나는 이 생성기를 만들었다
def orient(tile):
for i in range(4):
yield np.rot90(tile, i)
yield np.fliplr(np.rot90(tile, i))
다음에 나는 한 블록의 한 변과 다른 블록의 대응하는 변을 비교하고 싶어서 뒤집는 검색표를 만들었는데, 이것은 뒤집는 변을 보여 주었다.
돌이켜보면 edge은 이렇다.
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
사실이 증명하듯이 이 가장자리 중 하나를 다른 것으로 바꾸려면 -1을 0으로 바꾸고 0을 -1으로 바꾸면 된다.다음과 같은 찾기표(이상하게 보이는 문법)를 사용하여 이 점을 실현할 수 있습니다.
flip = {
...: ...,
-1 : 0 ,
0 : -1 ,
}
이렇게 나는 이렇게 타일을 비교할 수 있다.
for i, j in edges:
if str(old_tile[i, j]) == str(new_tile[flip[i], flip[j]]):
다음에 일치하는 항목을 찾으면 데이터를 저장해야 합니다.첫 번째 타일의 방향도 정하지 않았고 특정한 각도 선택하지 않았기 때문에 그물은 어느 방향으로든 뻗을 수 있다.구석을 찾아서 정확하게 위치를 정하면 그물이 위아래로 자라서 정확한 메모리 블록을 채워 메모리 효율이 더욱 높아진다.
하지만 나는 매우 게으르다.데이터가 12x12를 차지하기 때문에 만약에 내가 충분한 공간을 만들고 중간부터 시작한다면 나는 그물이 어느 방향으로 자라든지 경계를 넘지 않을 것을 보장할 수 있다.그래서 나는 25x25x10x10의 4차원numpy 격자를 만들고 2차원 방식으로 10x10 타일을 저장했다.
데이터를 저장하기 위해서 나는 격자에서 데이터를 저장하는 방향을 찾아야 한다.만약 일치하는 변이 오른쪽이라면, 나는 새 타일을 낡은 타일의 오른쪽 공간에 그려야 한다.일치하는 모서리가 아래에 있으면 새 타일은 아래에 있어야 합니다.사실이 증명하듯이, 나는 다른 찾기 표를 통해 변수 그룹을 방향 벡터로 변환할 수 있다.
dire = {
...: 0 ,
-1 : 1 ,
0 : -1 ,
}
예를 들어 (...,-1) 주어진 오른쪽 가장자리에서 이 찾기표를 사용하여 벡터(0,1)에 비칩니다.
전체 코드는 다음과 같습니다.
from math import sqrt
dim = int(sqrt(len(tiles)))
first_tile = next(iter(tiles))
result = np.full([2*dim+1, 2*dim+1, 10, 10], "")
result[dim][dim] = tiles[first_tile]
location = {first_tile: np.array([dim, dim])}
for left, right in nx.dfs_edges(graph, first_tile):
if left in location:
old, new = left, right
else:
old, new = right, left
old_loc = location[old]
old_tile = result[old_loc[0], old_loc[1]]
for i, j in edges:
for oriented_tile in orient(tiles[new]):
if str(old_tile[i, j]) == str(oriented_tile[flip[i], flip[j]]):
new_loc = old_loc + np.array([dire[i], dire[j]])
result[new_loc[0], new_loc[1]] = oriented_tile
location[new] = new_loc
break
이곳의 출력은 거대한 24x24x10numpy 진열로 중간 어딘가에 조립된 타일 격자가 있다.
테두리를 잘라 완전한 화면을 이루다
도전은 경계를 제거해야 하기 때문에, 각 스티커는 10x10 진열에서 8x8 진열로 바뀐다.결과는 10x10 어레이로 구성된 25x25 그리드로 구성되므로 한 번에 손쉽게 수행할 수 있습니다.
clipped = result[:,:,1:-1,1:-1]
완전한 화면을 만들기 위해서는 4D 진열을 2D 진열로 접어야 한다.불행하게도, 우리는 이미지를 형성하기 위해 정확한 순서에 따라 축을 접어야 하기 때문에 조심해야 한다.
flat = np.swapaxes(clipped, 1, 2).reshape((2*dim+1)*8, -1)
다음에 25x25 격자는 많은 추가 공간을 포함하고 있으며, 나는 모든 빈 공간을 선택해서 이 공간을 삭제할 수 있다.그러나 이렇게 하면 1D 패턴이 생성되지만 쉽게 재형성할 수 있습니다.
flat_filtered = flat [~(flat == '')].reshape(dim*8, -1)
출력(여기에 3x3 프레젠테이션 데이터 표시):
array([['.', '.', '.', '#', '#', '#', '.', '.', '.', '#', '#', '.', '.', '.', '#', '.', '.', '.', '#', '.', '.', '#', '#', '#'],
['.', '#', '.', '#', '#', '#', '.', '.', '#', '#', '.', '.', '#', '#', '.', '.', '#', '#', '#', '#', '.', '#', '#', '.'],
['#', '.', '#', '#', '.', '.', '#', '.', '.', '#', '.', '.', '.', '#', '.', '.', '#', '#', '#', '#', '.', '.', '.', '#'],
['#', '#', '#', '#', '#', '.', '.', '#', '#', '#', '#', '#', '.', '.', '.', '#', '#', '#', '.', '.', '.', '.', '#', '#'],
['#', '.', '.', '#', '#', '#', '#', '.', '.', '.', '#', '.', '#', '.', '#', '.', '#', '#', '#', '.', '#', '#', '#', '.'],
['.', '.', '#', '.', '#', '.', '.', '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#', '#', '#'],
['.', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.', '#', '.', '#'],
['.', '#', '.', '#', '.', '#', '#', '#', '.', '#', '#', '.', '#', '#', '.', '#', '.', '.', '#', '.', '#', '#', '.', '.'],
['#', '#', '#', '.', '#', '.', '.', '.', '#', '.', '.', '#', '.', '#', '#', '.', '#', '#', '#', '#', '#', '#', '.', '.'],
['.', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#', '#', '.', '#', '.', '.', '.', '#', '#', '#', '.', '#', '#', '.'],
['.', '.', '.', '#', '.', '.', '#', '.', '.', '#', '.', '#', '.', '#', '#', '.', '.', '#', '#', '#', '.', '#', '#', '#'],
['#', '#', '.', '.', '#', '#', '.', '#', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '.'],
['#', '.', '#', '#', '#', '#', '.', '.', '.', '.', '#', '#', '.', '.', '#', '#', '#', '#', '#', '#', '#', '#', '.', '#'],
['#', '#', '#', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#', '#', '#', '#', '#', '#', '.', '#', '.', '.', '#', '#'],
['#', '.', '#', '#', '#', '#', '.', '.', '#', '.', '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '#', '#', '.', '.'],
['#', '.', '.', '#', '.', '#', '#', '.', '.', '#', '.', '.', '#', '#', '#', '.', '#', '.', '#', '#', '.', '.', '.', '.'],
['.', '#', '#', '#', '#', '.', '.', '.', '#', '.', '.', '#', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '#', '.', '.', '.', '#', '#', '.', '.', '#', '.', '#', '.', '#', '#', '#', '.', '.'],
['.', '.', '.', '#', '#', '#', '#', '#', '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '#', '#', '#', '#', '.', '#'],
['#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#', '#', '.', '#', '#', '#', '#', '.', '.', '.', '#', '.', '#', '#'],
['#', '#', '#', '.', '#', '#', '#', '#', '#', '.', '.', '.', '#', '.', '#', '#', '#', '#', '#', '.', '#', '.', '.', '#'],
['#', '#', '.', '#', '#', '.', '#', '#', '#', '.', '#', '.', '#', '.', '.', '#', '#', '#', '#', '#', '#', '.', '.', '.'],
['#', '#', '#', '.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '#', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '#', '.', '#', '.', '.', '#', '.', '#', '#', '.', '.', '.', '#', '.', '#', '#', '.', '.', '#', '#', '#', '#', '#']], dtype='<U1')
그러나 다음 단계에서는 1과 0을 사용하고자 합니다.
image = (flat_filtered == "#").astype(int)
출력
array([[0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1],
[0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0],
[1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
[0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1],
[0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0],
[1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1],
[1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
[1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1],
[1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1]])
몬스터 가져오기
몬스터 가져오기는 타일 가져오기와 유사합니다.이것은 텍스트 파일에 저장되고numpy로 가져옵니다.나중에 사용할 수 있도록 # 기호의 총 수를 알아야 합니다.
monster = (np.array(open("monster.txt").read().splitlines()).view('U1') == "#").reshape((3, -1)).astype(int)
monster_value = monster.sum()
괴물 찾기
마지막으로 몬스터를 찾기 위해 우리는 몬스터 이미지(모든 가능한 다른 방향)와 메인 이미지 사이에서 2D를 실행하면 됩니다.Scipy에는 상호 연관성이 뛰어난 함수가 있습니다.그것은 기본적으로 메인 이미지에서 괴물 이미지를 스캔하고 그것들의 일치 위치를 정리한다.우리는 일치하는 항목이 괴물 중의 '#' 과 같기를 기대한다. 이것은 우리가 이전에 계산한 것이다.
from scipy.ndimage import correlate
correlate(image, monster, mode="constant") == monster_value
이렇게 하면 감지된 몬스터의 각 위치에 대해 True 또는 False가 반환됩니다.불행하게도, 우리가 얻은 것은 모두 잘못된 것이다. 왜냐하면 그림의 방향이 틀렸기 때문이다.우리는 반드시 그림(또는 괴물)의 모든 방향을 옮겨야 한다. 이것은 앞에서 사용한 orient() 함수를 통해 실현할 수 있다.
total_monsters = sum((correlate(image, oriented_monster, mode="constant") == monster_value).sum() for oriented_monster in orient(monster))
마지막으로 우리가 몬스터의 수량이 생기면 우리는 그림의 #을 계산하고 그 중에서 몬스터의 수량을 제거할 수 있다
print("remaining", image.sum() - total_monsters*monster_value)
전체 코드는 다음과 같습니다.
import numpy as np
import networkx as nx
from itertools import product
from math import prod, sqrt
import re
from scipy.ndimage import correlate
data = open("input.txt").read().splitlines()
tiles = {int(re.sub(r"Tile (\d+):", r"\1", k)): np.array(v).view('U1').reshape(10, 10) for k, *v, _ in np.array(data).reshape(-1, 12)}
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
borders = {}
graph = nx.Graph()
for tile_name, tile in tiles.items():
for (i, j), f in product(edges, (1, -1)):
border_id = "".join(tile[i, j][::f])
if border_id in borders:
graph.add_edge(borders[border_id], tile_name)
else:
borders[border_id] = tile_name
def orient(tile):
for i in range(4):
yield np.rot90(tile, i)
yield np.fliplr(np.rot90(tile, i))
flip = {
...: ...,
-1 : 0 ,
0 : -1 ,
}
dire = {
...: 0 ,
-1 : 1 ,
0 : -1 ,
}
dim = int(sqrt(len(tiles)))
first_tile = next(iter(tiles))
result = np.full([2*dim+1, 2*dim+1, 10, 10], "")
result[dim][dim] = tiles[first_tile]
location = {first_tile: np.array([dim, dim])}
for left, right in nx.dfs_edges(graph, first_tile):
if left in location:
old, new = left, right
else:
old, new = right, left
old_loc = location[old]
old_tile = result[old_loc[0], old_loc[1]]
for i, j in edges:
for oriented_tile in orient(tiles[new]):
if str(old_tile[i, j]) == str(oriented_tile[flip[i], flip[j]]):
new_loc = old_loc + np.array([dire[i], dire[j]])
result[new_loc[0], new_loc[1]] = oriented_tile
location[new] = new_loc
break
flat = np.swapaxes(result[:,:,1:-1,1:-1], 1, 2).reshape((2*dim+1)*8, -1)
flat_filtered = flat[~(flat == '')].reshape(dim*8, -1)
image = (flat_filtered == "#").astype(int)
monster = (np.array(open("monster.txt").read().splitlines()).view('U1') == "#").reshape((3, -1)).astype(int)
monster_value = monster.sum()
total_monsters = sum((correlate(image, oriented_monster, mode="constant") == monster_value).sum() for oriented_monster in orient(monster))
print("remaining", image.sum() - total_monsters*monster_value)
이것은 지금까지 가장 길고 지루한 도전이다.
앞으로!
Reference
이 문제에 관하여(코드 2020의 출현:NetworkX의 20일째,Python의Scipy 상호 관련), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/meseta/advent-of-code-day-20-incredibly-tedious-python-code-2dm3
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Tile 2311:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###
Tile 1951:
#.##...##.
#.####...#
.....#..##
#...######
.##.#....#
.###.#####
###.##.##.
.###....#.
..#.#..#.#
#...##.#..
<snip>
import re
import numpy as np
data = open("input.txt").read().splitlines()
tiles = {int(re.sub(r"Tile (\d+):", r"\1", k)): np.array(v).view('U1').reshape(10, 10) for k, *v, _ in np.array(data).reshape(-1, 12)}
{2311: array([['.', '.', '#', '#', '.', '#', '.', '.', '#', '.'],
['#', '#', '.', '.', '#', '.', '.', '.', '.', '.'],
['#', '.', '.', '.', '#', '#', '.', '.', '#', '.'],
['#', '#', '#', '#', '.', '#', '.', '.', '.', '#'],
['#', '#', '.', '#', '#', '.', '#', '#', '#', '.'],
['#', '#', '.', '.', '.', '#', '.', '#', '#', '#'],
['.', '#', '.', '#', '.', '#', '.', '.', '#', '#'],
['.', '.', '#', '.', '.', '.', '.', '#', '.', '.'],
['#', '#', '#', '.', '.', '.', '#', '.', '#', '.'],
['.', '.', '#', '#', '#', '.', '.', '#', '#', '#']], dtype='<U1'),
1951: array([['#', '.', '#', '#', '.', '.', '.', '#', '#', '.'],
['#', '.', '#', '#', '#', '#', '.', '.', '.', '#'],
['.', '.', '.', '.', '.', '#', '.', '.', '#', '#'],
['#', '.', '.', '.', '#', '#', '#', '#', '#', '#'],
['.', '#', '#', '.', '#', '.', '.', '.', '.', '#'],
['.', '#', '#', '#', '.', '#', '#', '#', '#', '#'],
['#', '#', '#', '.', '#', '#', '.', '#', '#', '.'],
['.', '#', '#', '#', '.', '.', '.', '.', '#', '.'],
['.', '.', '#', '.', '#', '.', '.', '#', '.', '#'],
['#', '.', '.', '.', '#', '#', '.', '#', '.', '.']], dtype='<U1'),
"".join(tiles[2311][..., -1])
'...#.##..#'
"".join(tiles[2311][..., -1][::-1])
'#..##.#...'
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
from itertools import product
for (i, j), f in product(edges, (1, -1)):
border_id = "".join(tile[i, j][::f])
import networkx as nx
from itertools import product
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
borders = {}
graph = nx.Graph()
for tile_name, tile in tiles.items():
for (i, j), f in product(edges, (1, -1)):
border_id = "".join(tile[i, j][::f])
if border_id in borders:
graph.add_edge(borders[border_id], tile_name)
else:
borders[border_id] = tile_name
pos = nx.nx_agraph.graphviz_layout(graph)
nx.draw(graph, pos=pos, node_color="lightgrey", edge_color="grey", node_size=50, with_labels=True)
from math import prod
print("prod", prod(tile for tile in graph if len(graph[tile]) == 2))
import numpy as np
import networkx as nx
from itertools import product
from math import prod
import re
data = open("input.txt").read().splitlines()
tiles = {int(re.sub(r"Tile (\d+):", r"\1", k)): np.array(v).view('U1').reshape(10, 10) for k, *v, _ in np.array(data).reshape(-1, 12)}
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
borders = {}
graph = nx.Graph()
for tile_name, tile in tiles.items():
for (i, j), f in product(edges, (1, -1)):
border_id = "".join(tile[i, j][::f])
if border_id in borders:
graph.add_edge(borders[border_id], tile_name)
else:
borders[border_id] = tile_name
print("prod", prod(tile for tile in graph if len(graph[tile]) == 2))
어머, 세상에, 이거 큰 거야.이 도전은 여러 단계를 포함한다.이제 우리는 타일의 도형이 생겼으니, 우리는 먼저 이 타일을 하나의 그림으로 다시 조합해야 한다.일단 조립이 끝나면 테두리는 반드시 잘라내야 한다.그리고 우리는 반드시 그림에서 해괴의 출현을 찾아야 한다.그리고 이미지의 나머지 부분이 몇 개의'#'문자로 구성되어 있는지 찾아냈습니다...
타일을 다시 그림으로 조립하다
이것은 지금까지 가장 지루한 걸음이다.지금까지 우리는 어느 타일이 어느 다른 타일에 연결되었는지, 그리고 어느 경계에 연결되었는지 알고 있기 때문에 이론적으로 우리는 모든 타일이 어느 길로 올라가야 틈새 없이 연결될 수 있는지 정확하게 계산할 수 있다.불행하게도, 이것은 너무 많은 기하학적 기교를 필요로 하고, 나는 어느 방향, 회전, 회전을 둘러싸고 타일을 그릴 수 없다. 왜냐하면 어느 경계가 일치하는지, 그리고 연결된 타일의 전체적인 회전과 회전을 알고 있기 때문이다.
그래서 나는 타일 한 조각을 퐁당 소리를 내고 4개의 가장자리 중 1개를 다음 타일의 8개 가능한 방향과 만력으로 일치시켰을 뿐이다. 그 중 하나만 일치할 수 있다는 것을 알았다.그것은 여전히 선형 시간 해산으로 평균 16배 느리다.
이 점을 하려면 타일의 8개 방향을 교체할 수 있어야 하기 때문에 나는 이 생성기를 만들었다
def orient(tile):
for i in range(4):
yield np.rot90(tile, i)
yield np.fliplr(np.rot90(tile, i))
돌이켜보면
edge은 이렇다.edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
-1을 0으로 바꾸고 0을 -1으로 바꾸면 된다.다음과 같은 찾기표(이상하게 보이는 문법)를 사용하여 이 점을 실현할 수 있습니다.flip = {
...: ...,
-1 : 0 ,
0 : -1 ,
}
for i, j in edges:
if str(old_tile[i, j]) == str(new_tile[flip[i], flip[j]]):
하지만 나는 매우 게으르다.데이터가 12x12를 차지하기 때문에 만약에 내가 충분한 공간을 만들고 중간부터 시작한다면 나는 그물이 어느 방향으로 자라든지 경계를 넘지 않을 것을 보장할 수 있다.그래서 나는 25x25x10x10의 4차원numpy 격자를 만들고 2차원 방식으로 10x10 타일을 저장했다.
데이터를 저장하기 위해서 나는 격자에서 데이터를 저장하는 방향을 찾아야 한다.만약 일치하는 변이 오른쪽이라면, 나는 새 타일을 낡은 타일의 오른쪽 공간에 그려야 한다.일치하는 모서리가 아래에 있으면 새 타일은 아래에 있어야 합니다.사실이 증명하듯이, 나는 다른 찾기 표를 통해 변수 그룹을 방향 벡터로 변환할 수 있다.
dire = {
...: 0 ,
-1 : 1 ,
0 : -1 ,
}
전체 코드는 다음과 같습니다.
from math import sqrt
dim = int(sqrt(len(tiles)))
first_tile = next(iter(tiles))
result = np.full([2*dim+1, 2*dim+1, 10, 10], "")
result[dim][dim] = tiles[first_tile]
location = {first_tile: np.array([dim, dim])}
for left, right in nx.dfs_edges(graph, first_tile):
if left in location:
old, new = left, right
else:
old, new = right, left
old_loc = location[old]
old_tile = result[old_loc[0], old_loc[1]]
for i, j in edges:
for oriented_tile in orient(tiles[new]):
if str(old_tile[i, j]) == str(oriented_tile[flip[i], flip[j]]):
new_loc = old_loc + np.array([dire[i], dire[j]])
result[new_loc[0], new_loc[1]] = oriented_tile
location[new] = new_loc
break
테두리를 잘라 완전한 화면을 이루다
도전은 경계를 제거해야 하기 때문에, 각 스티커는 10x10 진열에서 8x8 진열로 바뀐다.결과는 10x10 어레이로 구성된 25x25 그리드로 구성되므로 한 번에 손쉽게 수행할 수 있습니다.
clipped = result[:,:,1:-1,1:-1]
flat = np.swapaxes(clipped, 1, 2).reshape((2*dim+1)*8, -1)
flat_filtered = flat [~(flat == '')].reshape(dim*8, -1)
array([['.', '.', '.', '#', '#', '#', '.', '.', '.', '#', '#', '.', '.', '.', '#', '.', '.', '.', '#', '.', '.', '#', '#', '#'],
['.', '#', '.', '#', '#', '#', '.', '.', '#', '#', '.', '.', '#', '#', '.', '.', '#', '#', '#', '#', '.', '#', '#', '.'],
['#', '.', '#', '#', '.', '.', '#', '.', '.', '#', '.', '.', '.', '#', '.', '.', '#', '#', '#', '#', '.', '.', '.', '#'],
['#', '#', '#', '#', '#', '.', '.', '#', '#', '#', '#', '#', '.', '.', '.', '#', '#', '#', '.', '.', '.', '.', '#', '#'],
['#', '.', '.', '#', '#', '#', '#', '.', '.', '.', '#', '.', '#', '.', '#', '.', '#', '#', '#', '.', '#', '#', '#', '.'],
['.', '.', '#', '.', '#', '.', '.', '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#', '#', '#'],
['.', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.', '#', '.', '#'],
['.', '#', '.', '#', '.', '#', '#', '#', '.', '#', '#', '.', '#', '#', '.', '#', '.', '.', '#', '.', '#', '#', '.', '.'],
['#', '#', '#', '.', '#', '.', '.', '.', '#', '.', '.', '#', '.', '#', '#', '.', '#', '#', '#', '#', '#', '#', '.', '.'],
['.', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#', '#', '.', '#', '.', '.', '.', '#', '#', '#', '.', '#', '#', '.'],
['.', '.', '.', '#', '.', '.', '#', '.', '.', '#', '.', '#', '.', '#', '#', '.', '.', '#', '#', '#', '.', '#', '#', '#'],
['#', '#', '.', '.', '#', '#', '.', '#', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '.'],
['#', '.', '#', '#', '#', '#', '.', '.', '.', '.', '#', '#', '.', '.', '#', '#', '#', '#', '#', '#', '#', '#', '.', '#'],
['#', '#', '#', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#', '#', '#', '#', '#', '#', '.', '#', '.', '.', '#', '#'],
['#', '.', '#', '#', '#', '#', '.', '.', '#', '.', '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '#', '#', '.', '.'],
['#', '.', '.', '#', '.', '#', '#', '.', '.', '#', '.', '.', '#', '#', '#', '.', '#', '.', '#', '#', '.', '.', '.', '.'],
['.', '#', '#', '#', '#', '.', '.', '.', '#', '.', '.', '#', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '#', '.', '.', '.', '#', '#', '.', '.', '#', '.', '#', '.', '#', '#', '#', '.', '.'],
['.', '.', '.', '#', '#', '#', '#', '#', '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '#', '#', '#', '#', '.', '#'],
['#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#', '#', '.', '#', '#', '#', '#', '.', '.', '.', '#', '.', '#', '#'],
['#', '#', '#', '.', '#', '#', '#', '#', '#', '.', '.', '.', '#', '.', '#', '#', '#', '#', '#', '.', '#', '.', '.', '#'],
['#', '#', '.', '#', '#', '.', '#', '#', '#', '.', '#', '.', '#', '.', '.', '#', '#', '#', '#', '#', '#', '.', '.', '.'],
['#', '#', '#', '.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '#', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '#', '.', '#', '.', '.', '#', '.', '#', '#', '.', '.', '.', '#', '.', '#', '#', '.', '.', '#', '#', '#', '#', '#']], dtype='<U1')
image = (flat_filtered == "#").astype(int)
array([[0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1],
[0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0],
[1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
[0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1],
[0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0],
[1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1],
[1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
[1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1],
[1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1]])
몬스터 가져오기
몬스터 가져오기는 타일 가져오기와 유사합니다.이것은 텍스트 파일에 저장되고numpy로 가져옵니다.나중에 사용할 수 있도록 # 기호의 총 수를 알아야 합니다.
monster = (np.array(open("monster.txt").read().splitlines()).view('U1') == "#").reshape((3, -1)).astype(int)
monster_value = monster.sum()
괴물 찾기
마지막으로 몬스터를 찾기 위해 우리는 몬스터 이미지(모든 가능한 다른 방향)와 메인 이미지 사이에서 2D를 실행하면 됩니다.Scipy에는 상호 연관성이 뛰어난 함수가 있습니다.그것은 기본적으로 메인 이미지에서 괴물 이미지를 스캔하고 그것들의 일치 위치를 정리한다.우리는 일치하는 항목이 괴물 중의 '#' 과 같기를 기대한다. 이것은 우리가 이전에 계산한 것이다.
from scipy.ndimage import correlate
correlate(image, monster, mode="constant") == monster_value
orient() 함수를 통해 실현할 수 있다.total_monsters = sum((correlate(image, oriented_monster, mode="constant") == monster_value).sum() for oriented_monster in orient(monster))
#을 계산하고 그 중에서 몬스터의 수량을 제거할 수 있다print("remaining", image.sum() - total_monsters*monster_value)
import numpy as np
import networkx as nx
from itertools import product
from math import prod, sqrt
import re
from scipy.ndimage import correlate
data = open("input.txt").read().splitlines()
tiles = {int(re.sub(r"Tile (\d+):", r"\1", k)): np.array(v).view('U1').reshape(10, 10) for k, *v, _ in np.array(data).reshape(-1, 12)}
edges = (
(..., -1 ),
(0 , ...),
(..., 0 ),
(-1 , ...),
)
borders = {}
graph = nx.Graph()
for tile_name, tile in tiles.items():
for (i, j), f in product(edges, (1, -1)):
border_id = "".join(tile[i, j][::f])
if border_id in borders:
graph.add_edge(borders[border_id], tile_name)
else:
borders[border_id] = tile_name
def orient(tile):
for i in range(4):
yield np.rot90(tile, i)
yield np.fliplr(np.rot90(tile, i))
flip = {
...: ...,
-1 : 0 ,
0 : -1 ,
}
dire = {
...: 0 ,
-1 : 1 ,
0 : -1 ,
}
dim = int(sqrt(len(tiles)))
first_tile = next(iter(tiles))
result = np.full([2*dim+1, 2*dim+1, 10, 10], "")
result[dim][dim] = tiles[first_tile]
location = {first_tile: np.array([dim, dim])}
for left, right in nx.dfs_edges(graph, first_tile):
if left in location:
old, new = left, right
else:
old, new = right, left
old_loc = location[old]
old_tile = result[old_loc[0], old_loc[1]]
for i, j in edges:
for oriented_tile in orient(tiles[new]):
if str(old_tile[i, j]) == str(oriented_tile[flip[i], flip[j]]):
new_loc = old_loc + np.array([dire[i], dire[j]])
result[new_loc[0], new_loc[1]] = oriented_tile
location[new] = new_loc
break
flat = np.swapaxes(result[:,:,1:-1,1:-1], 1, 2).reshape((2*dim+1)*8, -1)
flat_filtered = flat[~(flat == '')].reshape(dim*8, -1)
image = (flat_filtered == "#").astype(int)
monster = (np.array(open("monster.txt").read().splitlines()).view('U1') == "#").reshape((3, -1)).astype(int)
monster_value = monster.sum()
total_monsters = sum((correlate(image, oriented_monster, mode="constant") == monster_value).sum() for oriented_monster in orient(monster))
print("remaining", image.sum() - total_monsters*monster_value)
앞으로!
Reference
이 문제에 관하여(코드 2020의 출현:NetworkX의 20일째,Python의Scipy 상호 관련), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/meseta/advent-of-code-day-20-incredibly-tedious-python-code-2dm3텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
