Solution code for 2017 Advent of Code day 1 (from: http://adventofcode.com/2017)

advent_of_code_2017-day_01.py

""" Solution code for day 1 of the Advent of Code 2017 from http://adventofcode.com/2017
Run in python console
"""

import timeit #for tracking code runtime
puzzle_input = input("puzzle promopt: ") # Given from the Advent of Code site prompt
sequence = list(map(lambda x: int(x), list(puzzle_input))) # convert pasted string to array of ints

def sum_sequence(sequence):
    """ Day 1 Part 1:
    FROM THE PROMPT:
    ......"review a sequence of digits (your puzzle input) and find the sum of all digits that match 
    the next digit in the list. The list is circular, so the digit after the last 
    digit is the first digit in the list.
    For example:
    - 1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the 
    third digit (2) matches the fourth digit.
    - 1111 produces 4 because each digit (all 1) matches the next.
    - 1234 produces 0 because no digit matches the next.
    - 91212129 produces 9 because the only digit that matches the next one is the last digit, 9."
    
    This soulution runs in O(n) time, for n elements in the input sequence,
    as it makes only one complete pass over the elements in the list, and returns the result.
    """
    start_time = timeit.default_timer()
    total = 0
    # handle the edge case of the last element being the same as the first element in the list
    i = sequence[len(sequence)-1]
    j = sequence[0]
    if i == j:
        total = i
    # reset i and j for running through the rest of the list
    i = 0
    j = 1
    while j < len(sequence):
        if sequence[i] == sequence[j]:
            total += sequence[i]
        i += 1
        j += 1
    print("sum_sequence runtime: " + str(timeit.default_timer() - start_time))
    return total

def sum_half_round_sequence(sequence):
    """ Day 1 Part 2:
    FROM THE PROMPT:
    ......"Now, instead of considering the next digit, consider the digit halfway around 
    the circular list. That is, if your list contains 10 items, only include a digit 
    in your sum if the digit 10/2 = 5 steps forward matches it. Fortunately, your list 
    has an even number of elements.
    For example:
    - 1212 produces 6: the list contains 4 items, and all four digits match the digit 2 items ahead.
    - 1221 produces 0, because every comparison is between a 1 and a 2.
    - 123425 produces 4, because both 2s match each other, but no other digit has a match.
    - 123123 produces 12.
    - 12131415 produces 4."
    
    This solution runs in O(n/2) time for n elements, as it only needs to scan half the list before it
    has a solution. Scanning half of the elements (techically the whole list is looked at, in half the 
    time with two indexes being checked per pass). The half-result can be multipled by two because all
    elements have been visited, and if i or j were to make a complete scan, returning to their starting 
    positions, each element in the list would be visited twice, weith the same result as scanning each 
    element once, and doubling the result.
    """
    start_time = timeit.default_timer()
    total = i = 0
    j = int(len(sequence)/2)
    while j < len(sequence):
        if sequence[i] == sequence[j]:
            total += sequence[i]
        i += 1
        j += 1
    print("half_round runtime: " + str(timeit.default_timer() - start_time))
    return total * 2 #elements cover other half of a circular list
    

print("Part 1 answer: " + str(sum_sequence(sequence)))
print("Part 2 answer: " + str(sum_half_round_sequence(sequence)))