Skip to content

Instantly share code, notes, and snippets.

@shadowimmage
Last active December 1, 2017 23:28
Show Gist options
  • Save shadowimmage/91315eff7da04b2f4126a67bb2e7f391 to your computer and use it in GitHub Desktop.
Save shadowimmage/91315eff7da04b2f4126a67bb2e7f391 to your computer and use it in GitHub Desktop.
Solution code for 2017 Advent of Code day 1 (from: http://adventofcode.com/2017)
""" 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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment