Categories
Programming What I’m Up To

My solution to Advent of Code 2020’s Day 1 challenge, in Python

 

December has arrived, and so has the great programming exercise known as the Advent of Code!

Think of it as an Advent calendar, but chocolates (or cheese, or wine), you’re presented with a new programming puzzle every day between the start of December and Christmas Day, in which you try to save Santa’s mission. You can use whatever programming language you want, and you don’t need to be an expert — as the site says, “just a little programming knowledge and some problem solving skills will get you pretty far.”

Advent of Code started in 2015, and has been taking place every year ever since. The 2020 edition began on Tuesday, December 1st at 12:00 midnight Eastern time (UTC-5).

Not only do I plan on participating in this year’s Advent of Code, but I might even use a couple of the challenges in the Python class I’m currently teaching on behalf of Computer Coach.

You have to sign in to play

In order to take on Advent of Code’s challenges, you have to sign in using an account from one of these popular “federated ID” services:

  • Github
  • Google
  • Twitter
  • Reddit

This is for a couple of reasons:

  • Signing in makes it easier for the site to keep track of your progress. Advent of Code is structures so that you must successfully complete challenge n before taking on challenge (n+1).
  • While everyone has to solve the same problem, each user gets their own (presumably) unique data set.

Once you’ve signed in, you can start on the first challenge…

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 1 challenge.

The Day 1 challenge, part one

Here’s the text from part one of the challenge:

Day 1: Report Repair

After saving Christmas five years in a row, you’ve decided to take a vacation at a nice resort on a tropical island. Surely, Christmas will go on without you.

The tropical island has its own currency and is entirely cash-only. The gold coins used there have a little picture of a starfish; the locals just call them stars. None of the currency exchanges seem to have heard of them, but somehow, you’ll need to find fifty of these coins by the time you arrive so you can pay the deposit on your room.

To save your vacation, you need to get all fifty stars by December 25th.

Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn’t quite adding up.

Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.

For example, suppose your expense report contained the following:

1721
979
366
299
675
1456

In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is 514579.

Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?

Here are the expense numbers that were provided for my account:

1140
1736
1711
1803
1825
1268
1651
2007
1923
1661
1788
1876
2003
1752
1988
1955
1568
1478
1699
1717
1828
1636
1387
1870
1658
1572
1703
1185
1569
1515
1142
1407
1587
1608
1827
1546
1808
1937
1815
1957
1401
1763
1970
1960
1853
1987
1865
1567
1664
1961
1771
1846
1971
1416
1897
633
1708
1606
515
1397
1873
1374
1969
1918
1170
1660
1494
1764
2002
1938
1396
1926
1714
1659
1805
1593
1899
1850
1644
1877
1561
1895
1985
1353
395
1919
1522
1745
1721
901
1765
1939
2009
1949
1852
1792
1749
1675
1883
1240
1868
1615
1693
1720
1388
1325
1337
867
1751
1408
1715
1942
1706
1894
1260
1945
1700
1148
1373
351
1790
1861
1755
1155
1622
1743
1872
1979
1262
1789
1305
1311
1729
1929
823
1623
2005
1932
1814
1909
1728
1592
1712
1363
1338
1804
1402
1198
264
1117
1791
1419
1229
1924
1838
1785
1982
1683
1950
1199
1984
1830
1921
1980
1834
1341
1282
1989
1854
1395
1847
1900
1913
1777
1779
1333
1800
1966
1543
1882
1375
1811
1673
1679
889
1670
1879
1312
1741
1772
1663
1776
1642
1674
1472
1580
1264
1738
1999
1637

I decided to use a Jupyter notebook running a Python kernel solve the problem.

Importing the data

My first step was to copy the numbers above, paste them into a triple-quoted string, and assign that string to the variable raw_input:

raw_input = """1140
1736
1711
1803
1825
1268
1651
2007
1923
1661
1788
1876
2003
1752
1988
1955
1568
1478
1699
1717
1828
1636
1387
1870
1658
1572
1703
1185
1569
1515
1142
1407
1587
1608
1827
1546
1808
1937
1815
1957
1401
1763
1970
1960
1853
1987
1865
1567
1664
1961
1771
1846
1971
1416
1897
633
1708
1606
515
1397
1873
1374
1969
1918
1170
1660
1494
1764
2002
1938
1396
1926
1714
1659
1805
1593
1899
1850
1644
1877
1561
1895
1985
1353
395
1919
1522
1745
1721
901
1765
1939
2009
1949
1852
1792
1749
1675
1883
1240
1868
1615
1693
1720
1388
1325
1337
867
1751
1408
1715
1942
1706
1894
1260
1945
1700
1148
1373
351
1790
1861
1755
1155
1622
1743
1872
1979
1262
1789
1305
1311
1729
1929
823
1623
2005
1932
1814
1909
1728
1592
1712
1363
1338
1804
1402
1198
264
1117
1791
1419
1229
1924
1838
1785
1982
1683
1950
1199
1984
1830
1921
1980
1834
1341
1282
1989
1854
1395
1847
1900
1913
1777
1779
1333
1800
1966
1543
1882
1375
1811
1673
1679
889
1670
1879
1312
1741
1772
1663
1776
1642
1674
1472
1580
1264
1738
1999
1637"""

Now that I had the data in a string, I could split the string into an array, using the newline character as the delimiter. I named the array split_input:

>>> split_input = raw_input.split("\n")
>>> split_input
['1140', '1736', '1711', '1803', '1825', '1268', '1651', '2007', '1923', '1661', '1788', '1876', '2003', '1752', '1988', '1955', '1568', '1478', '1699', '1717', '1828', '1636', '1387', '1870', '1658', '1572', '1703', '1185', '1569', '1515', '1142', '1407', '1587', '1608', '1827', '1546', '1808', '1937', '1815', '1957', '1401', '1763', '1970', '1960', '1853', '1987', '1865', '1567', '1664', '1961', '1771', '1846', '1971', '1416', '1897', '633', '1708', '1606', '515', '1397', '1873', '1374', '1969', '1918', '1170', '1660', '1494', '1764', '2002', '1938', '1396', '1926', '1714', '1659', '1805', '1593', '1899', '1850', '1644', '1877', '1561', '1895', '1985', '1353', '395', '1919', '1522', '1745', '1721', '901', '1765', '1939', '2009', '1949', '1852', '1792', '1749', '1675', '1883', '1240', '1868', '1615', '1693', '1720', '1388', '1325', '1337', '867', '1751', '1408', '1715', '1942', '1706', '1894', '1260', '1945', '1700', '1148', '1373', '351', '1790', '1861', '1755', '1155', '1622', '1743', '1872', '1979', '1262', '1789', '1305', '1311', '1729', '1929', '823', '1623', '2005', '1932', '1814', '1909', '1728', '1592', '1712', '1363', '1338', '1804', '1402', '1198', '264', '1117', '1791', '1419', '1229', '1924', '1838', '1785', '1982', '1683', '1950', '1199', '1984', '1830', '1921', '1980', '1834', '1341', '1282', '1989', '1854', '1395', '1847', '1900', '1913', '1777', '1779', '1333', '1800', '1966', '1543', '1882', '1375', '1811', '1673', '1679', '889', '1670', '1879', '1312', '1741', '1772', '1663', '1776', '1642', '1674', '1472', '1580', '1264', '1738', '1999', '1637']

split_input is an array of strings which needed to be converted into integer values.

In many other languages, I’d do this by using the map function to apply a “convert a string to its integer value” function to every item in the array, creating a resulting array called expenses. Here’s the Python version of that approach:

>>> expenses = list(map(int, split_input))
>>> expenses
[1140, 1736, 1711, 1803, 1825, 1268, 1651, 2007, 1923, 1661, 1788, 1876, 2003, 1752, 1988, 1955, 1568, 1478, 1699, 1717, 1828, 1636, 1387, 1870, 1658, 1572, 1703, 1185, 1569, 1515, 1142, 1407, 1587, 1608, 1827, 1546, 1808, 1937, 1815, 1957, 1401, 1763, 1970, 1960, 1853, 1987, 1865, 1567, 1664, 1961, 1771, 1846, 1971, 1416, 1897, 633, 1708, 1606, 515, 1397, 1873, 1374, 1969, 1918, 1170, 1660, 1494, 1764, 2002, 1938, 1396, 1926, 1714, 1659, 1805, 1593, 1899, 1850, 1644, 1877, 1561, 1895, 1985, 1353, 395, 1919, 1522, 1745, 1721, 901, 1765, 1939, 2009, 1949, 1852, 1792, 1749, 1675, 1883, 1240, 1868, 1615, 1693, 1720, 1388, 1325, 1337, 867, 1751, 1408, 1715, 1942, 1706, 1894, 1260, 1945, 1700, 1148, 1373, 351, 1790, 1861, 1755, 1155, 1622, 1743, 1872, 1979, 1262, 1789, 1305, 1311, 1729, 1929, 823, 1623, 2005, 1932, 1814, 1909, 1728, 1592, 1712, 1363, 1338, 1804, 1402, 1198, 264, 1117, 1791, 1419, 1229, 1924, 1838, 1785, 1982, 1683, 1950, 1199, 1984, 1830, 1921, 1980, 1834, 1341, 1282, 1989, 1854, 1395, 1847, 1900, 1913, 1777, 1779, 1333, 1800, 1966, 1543, 1882, 1375, 1811, 1673, 1679, 889, 1670, 1879, 1312, 1741, 1772, 1663, 1776, 1642, 1674, 1472, 1580, 1264, 1738, 1999, 1637]

It works, but from a Python programming point of view, it just doesn’t feel right.

The Pythonic approach would involve using a list comprehension instead of map (and then using the resulting iterator into a list). It just seems more readable:

>>> expenses = [int(string) for string in split_input]
>>> expenses
[1140, 1736, 1711, 1803, 1825, 1268, 1651, 2007, 1923, 1661, 1788, 1876, 2003, 1752, 1988, 1955, 1568, 1478, 1699, 1717, 1828, 1636, 1387, 1870, 1658, 1572, 1703, 1185, 1569, 1515, 1142, 1407, 1587, 1608, 1827, 1546, 1808, 1937, 1815, 1957, 1401, 1763, 1970, 1960, 1853, 1987, 1865, 1567, 1664, 1961, 1771, 1846, 1971, 1416, 1897, 633, 1708, 1606, 515, 1397, 1873, 1374, 1969, 1918, 1170, 1660, 1494, 1764, 2002, 1938, 1396, 1926, 1714, 1659, 1805, 1593, 1899, 1850, 1644, 1877, 1561, 1895, 1985, 1353, 395, 1919, 1522, 1745, 1721, 901, 1765, 1939, 2009, 1949, 1852, 1792, 1749, 1675, 1883, 1240, 1868, 1615, 1693, 1720, 1388, 1325, 1337, 867, 1751, 1408, 1715, 1942, 1706, 1894, 1260, 1945, 1700, 1148, 1373, 351, 1790, 1861, 1755, 1155, 1622, 1743, 1872, 1979, 1262, 1789, 1305, 1311, 1729, 1929, 823, 1623, 2005, 1932, 1814, 1909, 1728, 1592, 1712, 1363, 1338, 1804, 1402, 1198, 264, 1117, 1791, 1419, 1229, 1924, 1838, 1785, 1982, 1683, 1950, 1199, 1984, 1830, 1921, 1980, 1834, 1341, 1282, 1989, 1854, 1395, 1847, 1900, 1913, 1777, 1779, 1333, 1800, 1966, 1543, 1882, 1375, 1811, 1673, 1679, 889, 1670, 1879, 1312, 1741, 1772, 1663, 1776, 1642, 1674, 1472, 1580, 1264, 1738, 1999, 1637]

Now that I had the expenses in a Python list (that’s Pythonese for “array”), I could work with them.

Combinations to the rescue!

Once again, the goal of the challenge was to find the two numbers in the expense report whose sum was 2020.

To solve this problem, we need a way to generate all the possible combinations of two numbers taken from the list. I could write this code, but Python’s itertools module has a combinations() method that can do just that.

Here’s a quick demo of combinations() in action. Given a list containing a small number of integers, it generates a list of the possible 2-number combinations you can get from the list, without repetition (that is, a number can’t appear more than once in any combination):

>>> from itertools import *
>>> simple_list = [1, 3, 5, 7, 9]
>>> list(combinations(simple_list, 2))
[(1, 3), (1, 5), (1, 7), (1, 9), (3, 5), (3, 7), (3, 9), (5, 7), (5, 9), (7, 9)]

itertools also has a combinations_with_replacement() method. Rather than tell you what it does, let me show you:

>>> list(combinations_with_replacement(simple_list, 2))
[(1, 1), (1, 3), (1, 5), (1, 7), (1, 9), (3, 3), (3, 5), (3, 7), (3, 9), (5, 5), (5, 7), (5, 9), (7, 7), (7, 9), (9, 9)]

With that in mind, I used combinations() to generate a list of all the possible two-number combinations in expenses, which I assigned to a variable named all_expense_pairs:

>>> all_expense_pairs = list(combinations(expenses, 2))
>>> len(all_expense_pairs)
19900

Now that we have all the possible two-number combinations from the expense report, we can try to find the one(s) whose numbers add up to 2020.

Any time you’re in a situation where you need to find values in an array that match some criteria, you should think about applying a filter() function. I did just that: I used a filter() to extract a list of only those pairs summed to 2020…

def sums_to_2020(values):
    return sum(values) == 2020

>>> result = list(filter(sums_to_2020, all_expense_pairs))
>>> result
[(1387, 633)]

The resulting list had one tuple, (1387, 633), whose values sum to 2020. I entered the product of these two numbers — 877971 — and completed the first challenge.

The Day 1 challenge, part two

Here’s the text from part two:

The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had left over from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.

Using the above example again, the three entries that sum to 2020 are 979366, and 675. Multiplying them together produces the answer, 241861950.

In your expense report, what is the product of the three entries that sum to 2020?

Had I solved the problem from first principles, the solution might have taken a lot of extra work. Thanks to the use of itertools.combinations(), the solution for part two took three lines of code:

>>> all_expense_triplets = list(combinations(expenses, 3))
>>> result2 = list(filter(sums_to_2020, all_expense_triplets))
>>> result2
[(867, 264, 889)]

Once again, the resulting list had one tuple, (867, 264, 889), and its values, added up, were 2020. I entered the product of these three numbers — 203481432 — and completed the second challenge.

Feeling simultaneously proud and soiled

Thanks to Python (and remembering that it had a library that could do combinations and permutations),  I made a personal best in solving the Day 1 puzzles. I’m pretty pleased, but at the same time, I did so little work that it feels as if I’ve cheated. I may have to try solving the problem from first principles — if I have the time.

Other days’ solutions:

Here are my solutions for other days in Advent of Code 2020:

2 replies on “My solution to Advent of Code 2020’s Day 1 challenge, in Python”

Thanks for introducing to combinations. But given that you are creating combinations for all possible values where inputs are huge dont we run into performance issues?

Leave a Reply

Your email address will not be published. Required fields are marked *