m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2020-12-25 15:03:47 +0100
committerMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2020-12-25 15:03:47 +0100
commit4ca4d2f3bc6a01a84cd6719bcdc1ead5ed808a7e (patch)
tree58135307f90ad61c474ce847a1a512f29af231bf
Add day 1
-rw-r--r--01/a.c80
-rw-r--r--01/b.c127
-rw-r--r--01/input.txt199
3 files changed, 406 insertions, 0 deletions
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 <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#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 <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#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