From 4ca4d2f3bc6a01a84cd6719bcdc1ead5ed808a7e Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Fri, 25 Dec 2020 15:03:47 +0100 Subject: Add day 1 --- 01/a.c | 80 ++++++++++++++++++++++++ 01/b.c | 127 ++++++++++++++++++++++++++++++++++++++ 01/input.txt | 199 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 406 insertions(+) create mode 100644 01/a.c create mode 100644 01/b.c create mode 100644 01/input.txt diff --git a/01/a.c b/01/a.c new file mode 100644 index 0000000..7bac442 --- /dev/null +++ b/01/a.c @@ -0,0 +1,80 @@ +#include +#include +#include +#include +#include + +#define BUF_SIZE 2000 + +char buf[BUF_SIZE]; +int input[200]; +int length; + +void read_input() { + int fd = open("input.txt", O_RDONLY); + ssize_t bytes_read = read(fd, buf, BUF_SIZE-1); + if (bytes_read <= 0) { + printf("Error reading input\n"); + exit(1); + } + buf[bytes_read] = '\0'; +} + +void parse_input() { + int offset = 0; + int done = 0; + int buf_offset = 0; + int i = 0; + char current[10]; + + while (!done) { + int current_offset = 0; + while (buf[buf_offset] != '\n' && buf[buf_offset] != '\0') { + current[current_offset++] = buf[buf_offset++]; + } + if (buf[buf_offset] == '\0') { + done = 1; + } else { + buf_offset++; + current[current_offset] = '\0'; + input[i++] = atoi(current); + length = i; + } + } +} + +int int_less(const void *a, const void *b) { + return *(int *)a - *(int *)b; +} + +void sort_input() { + qsort(input, length, sizeof(int), int_less); +} + +int search_2020() { + int small_pointer = 0; + int large_pointer = length - 1; + int sum = input[small_pointer] + input[large_pointer]; + while (sum != 2020 && small_pointer != large_pointer) { + if (sum > 2020) { + large_pointer--; + } else { + small_pointer++; + } + sum = input[small_pointer] + input[large_pointer]; + } + return input[small_pointer] * input[large_pointer]; +} + +void print_input() { + for (int i = 0; i < length; i++) { + printf("%d\n", input[i]); + } +} + +int main() { + read_input(); + parse_input(); + sort_input(); + printf("%d\n", search_2020()); +} diff --git a/01/b.c b/01/b.c new file mode 100644 index 0000000..773ab73 --- /dev/null +++ b/01/b.c @@ -0,0 +1,127 @@ +#include +#include +#include +#include +#include + +#define BUF_SIZE 2000 + +char buf[BUF_SIZE]; +int input[200]; +int length; + +void read_input() { + int fd = open("input.txt", O_RDONLY); + ssize_t bytes_read = read(fd, buf, BUF_SIZE-1); + if (bytes_read <= 0) { + printf("Error reading input\n"); + exit(1); + } + buf[bytes_read] = '\0'; +} + +void parse_input() { + int offset = 0; + int done = 0; + int buf_offset = 0; + int i = 0; + char current[10]; + + while (!done) { + int current_offset = 0; + while (buf[buf_offset] != '\n' && buf[buf_offset] != '\0') { + current[current_offset++] = buf[buf_offset++]; + } + if (buf[buf_offset] == '\0') { + done = 1; + } else { + buf_offset++; + current[current_offset] = '\0'; + input[i++] = atoi(current); + length = i; + } + } +} + +int int_less(const void *a, const void *b) { + return *(int *)a - *(int *)b; +} + +void sort_input() { + qsort(input, length, sizeof(int), int_less); +} + +int bin_search(int small_pointer, int large_pointer) { + int small = input[small_pointer]; + int big = input[large_pointer]; + int mid = (large_pointer + small_pointer) / 2; + int sum = small + big + input[mid]; + while (sum != 2020 && small_pointer < large_pointer) { + if (sum > 2020) { + large_pointer = mid - 1; + mid = (large_pointer + small_pointer) / 2; + } else { + small_pointer = mid + 1; + mid = (large_pointer + small_pointer) / 2; + } + sum = small + big + input[mid]; + } + + if (sum == 2020) { + return mid; + } else { + return -1; + } +} + +int search_2020() { + int small_pointer = 0; + int large_pointer = length - 1; + int sum_small = input[small_pointer] + input[small_pointer + 1] + input[large_pointer]; + int sum_large = input[small_pointer] + input[large_pointer] + input[large_pointer - 1]; + int done = 0; + int mid; + while (sum_large != 2020 && sum_small != 2020 && small_pointer + 1 != large_pointer && !done) { + if (sum_small > 2020) { + large_pointer--; + } else if (sum_large < 2020) { + small_pointer++; + } else { + mid = bin_search(small_pointer, large_pointer); + if (mid > 0) { + done = 1; + } else { + mid = bin_search(small_pointer + 1, large_pointer); + if (mid > 0) { + done = 1; + } else { + mid = bin_search(small_pointer, large_pointer - 1); + if (mid > 0) { + done = 1; + } else { + small_pointer++; + large_pointer--; + } + } + } + } + + sum_small = input[small_pointer] + input[small_pointer + 1] + input[large_pointer]; + sum_large = input[small_pointer] + input[large_pointer] + input[large_pointer - 1]; + } + return input[small_pointer] * input[large_pointer] * input[mid]; +} + +void print_input() { + for (int i = 0; i < length; i++) { + printf("%d\n", input[i]); + } +} + +int main() { + read_input(); + parse_input(); + sort_input(); + printf("%d\n", search_2020()); +} + diff --git a/01/input.txt b/01/input.txt new file mode 100644 index 0000000..cebd722 --- /dev/null +++ b/01/input.txt @@ -0,0 +1,199 @@ +1732 +1660 +1658 +1878 +367 +2010 +1989 +431 +1946 +1614 +2003 +945 +1856 +1934 +1937 +1781 +1947 +1991 +1917 +1604 +1707 +1966 +1959 +1182 +1828 +1880 +1908 +1942 +1687 +1611 +1922 +1913 +1803 +1976 +1718 +1885 +1971 +2000 +1912 +1981 +1776 +1901 +1941 +1935 +1977 +1907 +1893 +1898 +1975 +2001 +1833 +1951 +1939 +1988 +1870 +1985 +1932 +1930 +1938 +1926 +1931 +1982 +76 +1979 +657 +1872 +1933 +1961 +1987 +1998 +1994 +418 +1914 +1929 +1810 +2009 +1712 +830 +1990 +1900 +1876 +1753 +1859 +1965 +1963 +1905 +1921 +1685 +1694 +697 +1899 +1997 +1964 +1927 +1952 +1894 +1960 +1986 +1883 +1616 +1993 +1892 +1943 +2005 +1995 +1915 +1663 +1954 +1902 +1191 +1948 +1875 +1850 +1955 +1962 +1984 +1957 +1969 +1887 +1953 +1786 +1638 +1909 +1881 +603 +1973 +1784 +1869 +1925 +1968 +1737 +1807 +1950 +1992 +1936 +1918 +1891 +1897 +1940 +1919 +1910 +1862 +1958 +1832 +1904 +1791 +1920 +1874 +1729 +1643 +2007 +1871 +1999 +1584 +1890 +1924 +1974 +1701 +1906 +143 +1725 +1945 +1783 +1873 +1903 +167 +1855 +1633 +1956 +1996 +1808 +1884 +1916 +829 +2002 +1852 +1835 +1889 +1983 +1949 +1970 +1774 +1764 +1609 +1882 +1857 +2004 +1911 +1896 +1980 +2006 +1967 +2008 +1972 +1648 +1923 +1978 +1675 +1831 -- cgit v1.2.3