this post was submitted on 25 Dec 2023
1 points (100.0% liked)

Advent Of Code

761 readers
17 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2023

Solution Threads

M T W T F S S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
 

Day 25: Snowverload

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

you are viewing a single comment's thread
view the rest of the comments
[โ€“] [email protected] 0 points 10 months ago

Python (Not C...)

(Posting from an alt because SDF is having issues)

A graph problem ๐Ÿ˜ฌโ€‹. There are well-known algorithms but none trivial to implement in C.

I tried dividing the nodes into two groups and then moving the node with the worst in-group/out-group edge balance - a Wish version of the Kernighan-Lin algorithm. As expected, it got stuck in a local optimum for the real input and random prodding didn't help.

Programming is programming and libraries are fair game so I went to Python and used NetworkX which was my first time using the library but so easy to use! Maybe I'll go back and do it in C someday and implement the algorithm myself.

#!/usr/bin/env python3
import sys
import re
from networkx import Graph
from networkx.algorithms.community import greedy_modularity_communities

G = Graph()

for line in sys.stdin.readlines():
  words = re.findall("\\w+", line)
  for to in words[1:]:
    G.add_edge(words[0], to)

coms = greedy_modularity_communities(G, best_n=2)

print("25:", len(coms[0]) * len(coms[1]))

https://github.com/sjmulder/aoc/tree/master/2023/python/day25.py