23
https://adventofcode.com/2024/day/23
Prob1
python
import sys
from typing import Dict, Set
tab: Set[str] = set()
def set_conn(x: str, y: str):
tab.add(f'{x}-{y}')
tab.add(f'{y}-{x}')
def get_conn(x: str, y: str) -> bool:
return f'{x}-{y}' in tab
comps: Set[str] = set()
for line in sys.stdin:
a, b = line.strip().split('-')
set_conn(a, b)
comps.add(a)
comps.add(b)
comp_list = sorted(list(comps))
cnt = 0
print(comp_list, len(comp_list))
print(tab)
for i, c1 in enumerate(comp_list):
for j, c2 in enumerate(comp_list[i+1:]):
for k, c3 in enumerate(comp_list[i+j+1:]):
if not get_conn(c1, c2) or not get_conn(c1, c3) or not get_conn(c2, c3):
continue
if c1.startswith('t') or c2.startswith('t') or c3.startswith('t'):
cnt += 1
# print(c1, c2, c3)
print(cnt)
Prob2
python
import sys
from typing import List, Set
tab: Set[str] = set()
def set_conn(x: str, y: str):
tab.add(f'{x}-{y}')
tab.add(f'{y}-{x}')
def get_conn(x: str, y: str) -> bool:
return f'{x}-{y}' in tab
comps: Set[str] = set()
for line in sys.stdin:
a, b = line.strip().split('-')
set_conn(a, b)
comps.add(a)
comps.add(b)
max_set: Set[int] = set()
comp_list = list(comps)
def main():
def dfs(chosed_comp: List[int], last_idx: int):
global max_set
if len(chosed_comp) > len(max_set):
max_set = chosed_comp.copy()
print(','.join(sorted(list(map(lambda x: comp_list[x], max_set)))))
for comp_idx in range(last_idx + 1, len(comp_list)):
ok = True
comp = comp_list[comp_idx]
for ucomp_idx in chosed_comp:
ucomp = comp_list[ucomp_idx]
if not get_conn(comp, ucomp):
ok = False
if not ok:
continue
chosed_comp.append(comp_idx)
dfs(chosed_comp, comp_idx)
chosed_comp.pop()
dfs([], -1)
print(','.join(sorted(list(map(lambda x: comp_list[x], max_set)))))
main()