Advent of Code 2015 - Day 12

Useful Links

Concepts and Packages Demonstrated

Problem Intro

We’re told that Santa’s needs some help balancing the books. His accounting data is stored in JSON format, made up of:

Type	E.g.
Arrays	[1,2,3]
Objects	{“a”:1, “b”:2}
Numbers	1
Strings	“whatever”

Take a look at the image above for an indication of what our sample data looks like.

Part 1

What is the sum of all numbers in the input document?

Once again, I’ve opted to do a bit of recursion.

First, note that the data types in our JSON input directly correlate to Python data types:

Type	E.g.	Python Data Type
Arrays	[1,2,3]	list
Objects	{“a”:1, “b”:2}	dict
Numbers	1	int
Strings	“whatever”	str

My plan of action is as follows:

Read in the json input and store it as a Python data type.
Identify whether the current data element is a dictionary, list, str or int.
If…
- An int, just add it to the running total.
- A str, ignore. (We’re told strings in the JSON will never contain a number.)
- A dict, then we need to dive into this dict. Recursively call this method, for each value in the dict. (Only values can possibly contain numbers, or other nested JSON objects.)
- A list, then we need to dive into this list. Recurisvely call this method for all elements in the list. (These could be int values, or other nested JSON objects.)

First, let’s read in the JSON:

import os
import time
import json

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

def main():
    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        j = json.load(f)

    result = process_json(j)
    print(f"Total of all numbers: {result}")

Here we’re using json.load(f) to read in the JSON input file, and return it as a Python dictionary. It always returns a dict because the JSON data always has { and } at the outermost level.

We pass our JSON dict to our process_json(data) method:

def process_json(json_input):
    """ Recursively processes json input. 
    Identifies all int values stored in a json object, and adds them up.

    Args:
        json_input (str): any valid json input

    Returns:
        int: Sum of all ints in this object
    """
    num_total = 0

    if isinstance(json_input, dict):
        for key in json_input:
            num_total += process_json(json_input[key], ignore)
    elif isinstance(json_input, list):
        for element in json_input:
            num_total += process_json(element, ignore) 
    elif isinstance(json_input, int):
        num_total += json_input     # base case that doesn't recurse
    
    # Might also be str type, but we don't care about those, so we can ignore this case.

    return num_total

The only new thing to mention here is the use of isinstance(some_object, some_python_object_type), which returns True if the object passed in matches the specified type.

That was easy enough!

Part 2

We’re told we must ignore any object - including all of its children - that has any property with the value red.

We’re told to do this for objects ({ ... }) and not for arrays ([ ... ]).

We can do this with very little additional coding. Since we’re told to only ignore objects, this means we only need to apply this red rule for dict values in our data.

My solution is to add an optional parameter to our function, allowing us to pass in a value that we should ignore in any dictionary types:

def process_json(json_input, ignore=None):
    """ Recursively processes json input. 
    Identifies all int values stored in a json object, and adds them up.

    Args:
        json_input (str): any valid json input
        ignore (str, optional): Ignore any collection or value that has an element with this value.
                                Defaults to None.

    Returns:
        int: Sum of all ints in this object
    """
    num_total = 0

    if isinstance(json_input, dict):
        if ignore and ignore in json_input.values():
            return 0

        for key in json_input:
            num_total += process_json(json_input[key], ignore)
    elif isinstance(json_input, list):
        for element in json_input:
            num_total += process_json(element, ignore) 
    elif isinstance(json_input, int):
        num_total += json_input     # base case that doesn't recurse
    
    # Might also be str type, but we don't care about those, so we can ignore this case.

    return num_total

And then we just need to call this same function, and pass in the string value we want to ignore:

# Part 2
result = process_json(j, "red")
print(f"Total of all numbers: {result}")

And that’s it!

Here’s the output:

Total of all numbers: 111754
Total of all numbers: 65402
Execution time: 0.0035 seconds

That’s pretty darn fast!

‹›