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
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
2020and 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
2020are1721and299. Multiplying them together produces1721 * 299 = 514579, so the correct answer is514579.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
2020are979,366, and675. 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”
[…] This year’s puzzles are about saving the well-earned vacation you’re taking, after having saved Christmas five years in a row. Day 1’s puzzles had you fix an expense report that you had to deal with before you could go on vac… […]
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?