From 6bd718f8c5ad5283f5a4c62d304d533bb0f0fc2e Mon Sep 17 00:00:00 2001 From: Andinus Date: Fri, 4 Dec 2020 10:58:50 +0530 Subject: Add day 1 solution --- 2020/day-01/README.org | 142 ++++++++++++++++++++++++++++++++++ 2020/day-01/day-01.raku | 23 ++++++ 2020/day-01/input | 200 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 365 insertions(+) create mode 100644 2020/day-01/README.org create mode 100644 2020/day-01/day-01.raku create mode 100644 2020/day-01/input diff --git a/2020/day-01/README.org b/2020/day-01/README.org new file mode 100644 index 0000000..1171801 --- /dev/null +++ b/2020/day-01/README.org @@ -0,0 +1,142 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+TITLE: Day 01 - Report Repair + +* Puzzle +- This puzzle is taken from: https://adventofcode.com/2020/day/1 + +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: +#+BEGIN_SRC +1721 +979 +366 +299 +675 +1456 +#+END_SRC + +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? +** Part 2 +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 +979, 366, 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? +* Solution +Slurping the input file to =@inputs=. =@inputs= will contain an array of +integers from the input file which were seperated by a newline. +#+BEGIN_SRC raku +my @inputs; +@inputs = "input".IO.lines>>.Int; +#+END_SRC + +Iterate over all possible combinations of =@inputs=, so 2 nested =for= loop +would've solved it. But a better solution would be to remove elements +from =@inputs= while iterating over it. + +Consider this list: (=1, 2=). A nested =for= loop on it means we have to +check for (=1, 1=, =1, 2=, =2, 1=, =2, 2=). But =1 + 2= is the same as =2 + 1= so we +could've dropped either the 1st or the 2nd index from that array. + +We do just that by =pop='ing the value from =@inputs= while iterating. That +way we just check for (=1, 1=, =1, 2=, =2, 2=). (=1, 2=) is skipped because =1= +was =pop='ed out in =while= loop. + +#+BEGIN_SRC raku +while pop @inputs -> $num_1 { + my Int $diff = 2020 - $num_1; + for @inputs -> $num_2 { + say "Part 1: ", $num_2 * $num_1 if $diff == $num_2; + } +} +#+END_SRC + +Also, =$diff= is calculated to be =2020 - $num_1= & checked for =$diff= being +equal to =$num_2=. The check should be =$num_1 + $num_2= being equal to +=2020=. But that would mean this addition would be run the number of times +=for= loop is run. It is optimized by calculating =$diff= once for each =for= +iteration. + +For example, consider this list: (=1, 2=). Without this optimization we go +through these steps: +#+BEGIN_SRC +## first iteration through while loop +if 1 + 1 == 2020 then print 1 * 1 # for loop 1 +if 1 + 2 == 2020 then print 1 * 2 # for loop 2 + +## second iteration through while loop +if 2 + 2 == 2020 then print 2 * 2 # for loop 1 +#+END_SRC + +But with the optimization we go through these steps: +#+BEGIN_SRC +## first iteration through while loop +diff = 2020 - 1 +if 1 == diff then print 1 * 1 # for loop 1 +if 2 == diff then print 1 * 2 # for loop 2 + +## second iteration through while loop +diff = 2020 - 2 +if 2 == diff then print 2 * 2 # for loop 2 +#+END_SRC + +You see what changes? We replaced all that addition in each =for= +iteration with a single subtraction. In our example list, instead of 3 +addition operations we just perform 2 subtraction operations but the +optimization will better work on longer list. + +Now this is not the best solution, we could do some more optimization +but I'll leave it at this. +** Part 2 +Input is again slurped to =@inputs=. This time 3 nested for loops are +implemented instead. This was the simplest solution that came to my +mind. +#+BEGIN_SRC raku +@inputs = "input".IO.lines>>.Int; +for @inputs -> $num_1 { + for @inputs -> $num_2 { + for @inputs -> $num_3 { + if 2020 == $num_1 + $num_2 + $num_3 { + say "Part 2: ", ($num_1 * $num_2 * $num_3); + exit; + } + } + } +} +#+END_SRC diff --git a/2020/day-01/day-01.raku b/2020/day-01/day-01.raku new file mode 100644 index 0000000..7ab6c49 --- /dev/null +++ b/2020/day-01/day-01.raku @@ -0,0 +1,23 @@ +#!/usr/bin/env raku + +my @inputs; +@inputs = "input".IO.lines>>.Int; + +while pop @inputs -> $num_1 { + my Int $diff = 2020 - $num_1; + for @inputs -> $num_2 { + say "Part 1: ", $num_2 * $num_1 if $diff == $num_2; + } +} + +@inputs = "input".IO.lines>>.Int; +for @inputs -> $num_1 { + for @inputs -> $num_2 { + for @inputs -> $num_3 { + if 2020 == $num_1 + $num_2 + $num_3 { + say "Part 2: ", ($num_1 * $num_2 * $num_3); + exit; + } + } + } +} diff --git a/2020/day-01/input b/2020/day-01/input new file mode 100644 index 0000000..cd21524 --- /dev/null +++ b/2020/day-01/input @@ -0,0 +1,200 @@ +1544 +1560 +1947 +1659 +1972 +1940 +1977 +1689 +1916 +1638 +1804 +1543 +1789 +545 +968 +1959 +1783 +1869 +1581 +1976 +1859 +1660 +1793 +69 +1653 +1866 +1541 +1920 +1751 +1681 +1829 +2009 +1752 +680 +1864 +1628 +1917 +1876 +2002 +1974 +1827 +1791 +1552 +1669 +1849 +1167 +1744 +1764 +1913 +1782 +1926 +1795 +1738 +1877 +1811 +1746 +1682 +1943 +1761 +1850 +983 +1617 +1901 +1750 +1842 +1588 +1679 +1759 +1994 +1847 +1657 +1981 +1648 +1996 +1572 +1953 +1555 +1665 +1680 +1872 +1826 +1316 +1962 +1893 +1545 +1535 +1895 +1819 +1891 +1919 +1853 +1831 +704 +1978 +1780 +1722 +1652 +1625 +478 +1030 +1985 +1720 +1817 +264 +1988 +1892 +1712 +1222 +1840 +1894 +1906 +1890 +1846 +1939 +1991 +1835 +1799 +1865 +1663 +1908 +1575 +1970 +1956 +1556 +1688 +1558 +1698 +1771 +1807 +1878 +1707 +1770 +1823 +1802 +1930 +1703 +1136 +1910 +1998 +1973 +1611 +1979 +1612 +1838 +1715 +1885 +1879 +1904 +1941 +1734 +1900 +1809 +1691 +1848 +1683 +1754 +1874 +1975 +1896 +1567 +1785 +1644 +1922 +1651 +1046 +1971 +1600 +1933 +1857 +1960 +1948 +1675 +1828 +1633 +1868 +1615 +1884 +1674 +1860 +1775 +995 +1596 +2006 +1737 +1649 +1997 +1767 +1784 +1705 +1664 +1766 +1839 +1533 +1935 +1796 +1781 +1589 +1594 +1987 +1769 -- cgit 1.4.1-2-gfad0