Advent of Code 2016 - Day 6

Useful Links

Concepts and Packages Demonstrated

collections.Counter zip String Manipulation Logging

Problem Intro

The year is 2016, and we’re helping Santa’s communication system. Due to a local electromagnetic anomaly, messages are being corrupted. We receive a series of messages, but each character in the message has been sent many times, and the most frequent character in each position is the correct one.

Our input consists of a list of corrupted messages, one per line. For example:

eedadn
drvtee
eandsr
raavrd
atevrs
tsrnev
sdttsa
rasrtv
nssdts
ntnada
svetve
tesnvf
vntsnd
vrdear
dvrsen
enarar

Part 1

Given the corrupted messages, what is the error-corrected version of the message?

To solve this, we need to determine the most frequent character in each column of the input data. The problem can be broken down into these steps:

Read all the lines of the input data.
“Transpose” the data so that we can easily access all characters in a given column.
For each column, count the occurrences of each character.
Identify the most frequent character in that column.
Combine these characters to form the error-corrected message.

Here’s the core logic from the solution:

import logging
import os
import time
from collections import Counter

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"

def main():
    logging.basicConfig(level=logging.DEBUG, format="%(asctime)s:%(levelname)s:\t%(message)s")
        
    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        data = f.read().splitlines()
        
    # First, we need to transpose columns to rows.
    # zip(*data) takes an iterable of iterables and aggregates the elements
    # from each of the iterables. For example, if data = ['abc', 'def'],
    # then zip(*data) would produce [('a', 'd'), ('b', 'e'), ('c', 'f')].
    transposed = list(zip(*data))
    
    most_common_chars = [] # Part 1
    
    for line in transposed:
        char_counts = Counter(line)
        # Counter.most_common(1) returns a list of the 1 most common elements
        # and their counts, e.g., [('e', 5)]. We want just the character.
        most_common_chars.append(char_counts.most_common(1)[0][0])
    
    most_common = "".join(str(char) for char in most_common_chars)
    
    logging.info(f"Part 1 message: {most_common}")

if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

The key steps here are:

zip(*data): This elegant Python idiom is used to transpose the rows and columns. If data is a list of strings (each string representing a row), zip(*data) treats each string as an iterable and groups the characters at the same index across all strings. The list() conversion then turns this into a list of tuples, where each tuple represents a column.
collections.Counter: For each transposed “column” (which is now a tuple of characters), Counter efficiently counts the occurrences of each character.
char_counts.most_common(1)[0][0]: This retrieves the most common character. most_common(1) returns a list of the single most common element and its count (e.g., [('e', 5)]). We then access the character itself using [0][0].

Part 2

As a second part of the communication system, we also need to find the original message if the communication system uses a modified repetition code where the character that appears least frequently in each position is the correct one.

Part 2 is a slight variation of Part 1. Instead of finding the most frequent character, we need to find the least frequent character in each column. The collections.Counter object doesn’t have a direct least_common method, but we can achieve this by sorting the items by their counts and picking the first one, or by using min with a custom key.

Here’s how the solution extends to handle Part 2:

    # ... (previous code for reading data and transposing)

    most_common_chars = [] # Part 1
    least_common_chars = [] # Part 2
        
    for line in transposed:
        char_counts = Counter(line)
        # Get the most frequent char (Part 1)
        most_common_chars.append(char_counts.most_common(1)[0][0])
        
        # Get the least frequent char (Part 2)
        # We find the minimum count using a lambda function as the key for min()
        least_common_chars.append(min(char_counts.items(), key=lambda x: x[1])[0])
    
    # Convert to str representation
    least_common = "".join(str(char) for char in least_common_chars)
    most_common = "".join(str(char) for char in most_common_chars)
    
    logging.info(f"Part 1 message: {most_common}")
    logging.info(f"Part 2 message: {least_common}")

The key change for Part 2 is the line:

least_common_chars.append(min(char_counts.items(), key=lambda x: x[1])[0]): This finds the character with the minimum count. char_counts.items() returns key-value pairs (character, count). The key=lambda x: x[1] tells min() to compare these pairs based on their second element (the count). We then extract the character ([0]) from the resulting (character, count) tuple.

This approach efficiently solves both parts of the puzzle by leveraging Python’s built-in zip function for transposition and collections.Counter for frequency analysis.

‹