08

https://adventofcode.com/2024/day/8

Prob1

題目

給定一個盤面，上面有些點有上不同的顏色。

對於任兩個相同顏色的點$AB$，我們把符合下面條件的格子點 $X$ 標出來：

1. $X$ 在 $AB$ 外面 （這是我加的，否則按照題目定義應該要產生$4$個反節點，而不是$2$個）
2. $XAB$ 在一直線上
3. $2|\overline{XA}|=|\overline{XB}|$

計算這些點的數量，相同位置算同一個，產生在上色的點也算。

範例

Input

......
.A.a..
A...a.
......

Output

把產生的點標出來 x

..x...
.A.a..
A...a.
.....x

所以會產生 2 個

2

解法

對任兩同色點對計算 $2A-B$。

import sys

from typing import List, Dict, Tuple, Set


pt_map: Dict[str, List[Tuple[int, int]]] = {}

y_max = 0
x_max = 1

for line in sys.stdin:
  line = line.strip()
  x_max = len(line)
  for x, c in enumerate(line):
    if c == '.':
      continue
    pt_map.setdefault(c, list()).append((x + 1, y_max + 1))
  y_max += 1


a_set: Set[Tuple[int, int]] = set()

for _, pts in pt_map.items():
  n = len(pts)
  for i in range(n):
    for j in range(n):
      if i == j:
        continue
      x1, y1 = pts[i]
      x2, y2 = pts[j]
    
      x3 = 2*x2 - x1
      y3 = 2*y2 - y1
      if x3 < 1 or x3 > x_max or y3 < 1 or y3 > y_max:
        continue

      a_set.add((x3, y3))
      print(x3, y3)

print(len(a_set))

Prob2

題目

給定一個盤面，上面有些點有上不同的顏色。

對於任兩個相同顏色的點$AB$，把所有在同一線上的格子標出來。

總共多少格子點？

範例

Input

......
.A....
A...a.
.....a

Output

把產生的點標出來 x

..x...
.A.x..
A...a.
.....a

所以會產生 2 個

2

解法

枚舉同色點對，然後計算每個 row 是哪個點和 $AB$ 相交。

我當下沒考慮兩點都在同一 row ，但測資沒出現 🤣

import sys

from typing import List, Dict, Tuple, Set


pt_map: Dict[str, List[Tuple[int, int]]] = {}

y_max = 0
x_max = 1

for line in sys.stdin:
  line = line.strip()
  x_max = len(line)
  for x, c in enumerate(line):
    if c == '.':
      continue
    pt_map.setdefault(c, list()).append((x + 1, y_max + 1))
  y_max += 1


a_set: Set[Tuple[int, int]] = set()

for _, pts in pt_map.items():
  n = len(pts)
  for i in range(n):
    for j in range(n):
      if i == j:
        continue
      x1, y1 = pts[i]
      x2, y2 = pts[j]

      dx = x2 - x1
      dy = y2 - y1

      for x3 in range(1, 51):
        # y3 = dy*(x3 - x2)/dx + y2
        v = dy*(x3 - x2)
        if v % dx != 0:
          continue

        y3 = v//dx + y2

        if x3 < 1 or x3 > x_max or y3 < 1 or y3 > y_max:
          continue
    
        a_set.add((x3, y3))
        print(x3, y3)

print(len(a_set))

Changelog

Last edited about 1 month ago

View full history

fba0b10-Update