Advent of Code 2016 - Day 6

Day 6: Signals and Noise

Useful Links

‹›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

collections.Counterziplambda

Problem Intro

We’re receiving a garbled message from Santa. It seems to be a simple repetition code, where the same message is sent over and over. Our job is to decode it.

The input data is a series of lines, each representing a received message. For example:

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

To decode the message, we need to find the most common character in each column.

Part 1

Given the recording in your puzzle input, what is the error-corrected version of the message being sent?

My strategy is to:

1. Read all the lines of the input file.
2. Transpose the data, so that columns become rows.
3. For each new “row” (which was a column), find the most common character.
4. Concatenate these characters to form the message.

Here’s the Python code that implements this:

import logging
import os
import time
from collections import Counter

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

def main():
    logging.basicConfig(level=logging.DEBUG, format="%(asctime)s:%(levelname)s:	%(message)s")
        
    # input_file = os.path.join(SCRIPT_DIR, SAMPLE_INPUT_FILE)
    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
    transposed = list(zip(*data))
    
    most_common_chars = [] # Part 1
        
    for line in transposed:
        char_counts = Counter(line)
        # Get the most frequent char
        most_common_chars.append(max(char_counts.items(), key=lambda x: x[1])[0])
    
    # Convert to str representation
    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 parts of the code are:

• zip(*data): This is a neat trick to transpose a list of lists (or in this case, a list of strings). The * operator unpacks the data list, so each string is passed as a separate argument to zip. zip then aggregates the elements from each of the iterables.
• collections.Counter: This is a specialized dictionary subclass for counting hashable objects. It’s perfect for this task.
• max(char_counts.items(), key=lambda x: x[1])[0]: This finds the item in the Counter with the highest count. char_counts.items() gives us (character, count) pairs. The key argument tells max to use a custom function for comparison.

A Note on Lambda Functions

In this solution, I’m using a lambda function as the key for the max() and min() functions. A lambda function is a small, anonymous function defined with the lambda keyword. It can have any number of arguments, but can only have one expression.

The syntax is lambda arguments: expression.

In my code, lambda x: x[1] is a function that takes an argument x (which will be a (character, count) tuple from char_counts.items()) and returns the second element, x[1], which is the count.

Using a lambda function here is a concise and readable way to tell the max() and min() functions which part of the tuple to use for comparison, without having to define a separate, named function. It’s a common pattern in Python for sorting and finding min/max values in complex data structures.

Part 2

Now, find the least common character in each position. What is the modified message?

This is a simple modification of Part 1. Instead of finding the max character count, we need to find the min.

Here’s the updated code within the main function:

    least_common_chars = [] # Part 2
        
    for line in transposed:
        char_counts = Counter(line)
        # Get the least frequent char
        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)
    
    logging.info(f"Part 2 message: {least_common}")

The only change is using min() instead of max().

The final output looks like this:

20:39:29:INFO:	Part 1 message: zcreqgiv
20:39:29:INFO:	Part 2 message: pljvorrk
Execution time: 0.0010 seconds

‹›