Digital Plumber — Python — #adventofcode Day 12
Series
This post is part of the series Advent of Code 2017
- Reflections on #aoc2017
- The Halting Problem — Python — #adventofcode Day 25
- Electromagnetic Moat — Rust — #adventofcode Day 24
- Coprocessor Conflagration — Haskell — #adventofcode Day 23
- Sporifica Virus — Rust — #adventofcode Day 22
- Fractal Art — Python — #adventofcode Day 21
- Particle Swarm — Python — #adventofcode Day 20
- A Series of Tubes — Rust — #adventofcode Day 19
- Duet — Haskell — #adventofcode Day 18
- Spinlock — Rust/Python — #adventofcode Day 17
- Permutation Promenade — Julia — #adventofcode Day 16
- Dueling Generators — Rust — #adventofcode Day 15
- Disk Defragmentation — Haskell — #adventofcode Day 14
- Packet Scanners — Haskell — #adventofcode Day 13
- > Digital Plumber — Python — #adventofcode Day 12 <
- Hex Ed — Python — #adventofcode Day 11
- Knot Hash — Haskell — #adventofcode Day 10
- Stream Processing — Haskell — #adventofcode Day 9
- I Heard You Like Registers — Python — #adventofcode Day 8
- Recursive Circus — Ruby — #adventofcode Day 7
- Memory Reallocation — Python — #adventofcode Day 6
- A Maze of Twisty Trampolines — C++ — #adventofcode Day 5
- High Entropy Passphrases — Python — #adventofcode Day 4
- Spiral Memory — Go — #adventofcode Day 3
- Corruption Checksum — Python — #adventofcode Day 2
- Inverse Captcha — Coconut — #adventofcode Day 1
- Advent of Code 2017: introduction
Today’s challenge has us helping a village of programs who are unable to communicate. We have a list of the the communication channels between their houses, and need to sort them out into groups such that we know that each program can communicate with others in its own group but not any others. Then we have to calculate the size of the group containing program 0 and the total number of groups.
!!! commentary This is one of those problems where I’m pretty sure that my algorithm isn’t close to being the most efficient, but it definitely works! For the sake of solving the challenge that’s all that matters, but it still bugs me.
By now I’ve become used to using fileinput to transparently read data either from files given on the command-line or standard input if no arguments are given.
import fileinput as fi
First we make an initial pass through the input data, creating a group for each line representing the programs on that line (which can communicate with each other). We store this as a Python set.
groups = []
for line in fi.input():
head, rest = line.split(' <-> ')
group = set([int(head)])
group.update([int(x) for x in rest.split(', ')])
groups.append(group)
Now we iterate through the groups, starting with the first, and merging any we find that overlap with our current group.
i = 0
while i < len(groups):
current = groups[i]
Each pass through the groups brings more programs into the current group, so we have to go through and check their connections too. We make several merge passes, until we detect that no more merges took place.
num_groups = len(groups) + 1
while num_groups > len(groups):
j = i+1
num_groups = len(groups)
This inner loop does the actual merging, and deletes each group as it’s merged in.
while j < len(groups):
if len(current & groups[j]) > 0:
current.update(groups[j])
del groups[j]
else:
j += 1
i += 1
All that’s left to do now is to display the results.
print("Number in group 0:", len([g for g in groups if 0 in g][0]))
print("Number of groups:", len(groups))
Webmentions
You can respond to this post, "Digital Plumber — Python — #adventofcode Day 12", by:
liking, boosting or replying to a tweet or toot that mentions it; or
sending a webmention from your own site to https://erambler.co.uk/blog/day-12/
Comments
Powered by Cactus Comments 🌵