zhaoshengEE/Advent_of_Code_2021

Advent of Code 2021

Day	Title	Takeaways
1	Sonar Sweep	1. In Python, file.read() returns the entire content of file as a string, whereas file.readlines() returns a list where each item is a line from file 2. string.strip() returns a copy of the string with both leading and trailing characters removed
2	Dive	1. Using .replace() and .split() to split the input by two delimiters and store the resulting input into a list
3	Binary Diagnostic	1. Part 1 uses comprehension to count the number of ones and the number of zeros in each bit position 2. int(string, 2) converts a binary string to a decimal integer 3. Part 2 implements recursion to solve the puzzle 4. CAVEAT: If we declare two lists as A = B = [] in Python, and even if we just modify list A later, the list B will be modified accordingly
4	Giant Squid	1. OOP comes into play at this puzzle 2. Everytime we want to initialize class variables and their types, we need to have from __future__ import annotations at the top 3. A class method should have cls as input parameter and can only be called by a class, whereas a property can be called by an object(class instance) 4. The way to convert a 2D list into a set: set.union(*map(set, list)) 5. set.discard(number) is a built-in method, which removes the number from the set 6. *parameter is used to denote the parameter can have 0 or more elements 7. According to this post, we should use named tuples instead of tuples anywhere we think object notation will make our code more pythonic and more easily readable. 8. Make sure to have from typing import NamedTuple on the top when we want to implement named tuple 9. for/else loop also comes into play at this puzzle, the else statement will only be executed when the for loop completes normally(e.g. no break is encountered in this puzzle)
5	Hydrothermal Venture	1. There are two ways to find the maximum in a 2D list: max(map(max, list_name)) and numpy.array(list_name).max()(That's why numpy can make your life easier, eh?) 2. while (x, y) != (x_end, y_end) creates a loop until both x and y satisfy their conditions, it is useful when x and y needs to be modified with the same number of times 3. Think of combining range() and min(), max() when we need to determine the increment is 1 or -1. For example: range(min(x, y), max(x, y) + 1)
6	Lanternfish	1. defaultdict or Counter can be a data structure to ease the time complexity of the algorithm
7	The Treachery of Whales	1. Second time to implement Counter in the algorithm 2. In Python, float("inf") refers to the positive infinity, and float("-inf") represents the negative infinity
8	Seven Segment Search	1. A visual problem that makes full use of set intersection and set reduction 2. Use numpy to covert multidimensional arrar into 1D array: numpyArrayName.flatten() 3. There are two ways to get the key in dictionary given a value: (i). list(mydict.keys())[list(mydict.values()).index(GIVEN_VALUE)] (ii). Invert the original dictionary: invertedMydict = {value : key for key, value in mydict.items()} 4. Difference between sorted() and .sort(): (i) .sort() sorts the variable in place, and can only be used on list (ii). sorted() sorts the variable into a newly created one, and can be used on any iterable 5. CAVEAT: sorted(string_name) will split the orginal string into character, if we still want to keep the string structure, we need to implement this way: ''.join(sorted(string_name))
9	Smoke Basin	1. A graph problem with the help of dictionary structure 2. myDict.get(key, defaultValue) returns defalutValue if key is not in the dictionary 3. If a function has multiple yield, the function will return each yield one by one, and each yield returns a generator which is only be stored on the fly, instead in memory. For more information on yield, please refer to this Stack Overflow post 4. Part 2 involves a BFS with the help of a set and a stack
10	Syntax Scoring	1. Valid Parentheses problem with the usage of stack data structure 2. DAY_10 folder contains the Python codework for implementaion of stack, which will be handy in the future 3. listName.clear() clears the list to an empty list
11	Dumbo Octopus	1. Make full use of numpy to ease the complexity 2. Further use the find_adjacent_points function, which was initially used in DAY_9. Smoke Basin 3. A fruitful of numpy takeaways: (i). If a is a numpy array, a += 1 increments all the elements in the array by 1 (ii). np.any(numpyArray > 9) returns True if any one of the elements in the numpy array is greater than 9, otherwise returns False (iii). If we want to fetch the index with specified condition, use np.where(), such as np.where(numpyArray > 9) (*). If the numpy array is 1D, we can get the index or indices via np.where(numpyArray > 9)[0] (*). If the numpy array is 2D, we can get he index or indices via x, y = np.where(numpyArray > 9) 4. if x in range(0, 10) is the same with 0 <= x < 10 or x >= 0 and x < 10
12	Passage Pathing	1. A graph and DFS problem with the help of defaultdict, set, deque, and two/three-element tuple
13	Transparent Origami	1. Solve the puzzle with the help of defaultdict which only keep tracks of dots' positions instead of the whole grid 2. In defaultdict or dictionary, dict.get(key, default_value) returns dict[key] or default_value but never modifies anything 3. CAVEAT: Do not modify dictionary while looping through dict or defaultdict, if that is necessary, use two dictionaries to solve the problem 4. Get the number of items in dictionary: len(dict) 5. To declare a numpy array with designated initial values: np.full(shape, initial_value, dtype) 6. DAY_13 folder contains a function that prints out 2-D numpy array, which can be handy in the future
14	Extended Polymerization	1. Another puzzle solved with the help of defaultdict 2. defaultdict(int) defines the default value is 0. If we want to set the default value to 1, we can defaultdict(lambda:1)
15	Chiton	1. Find the shortest path or the minimum cost path with the help of Dijkstra's Algorithm and the implementaion of Heap 2. If the Heap consists of Tuples, the Heap will take the first item in each tuple as the priority
16	Packet Decoder	1. Implement recursion to solve the puzzle with multiple base case and recursive case 2. When convert hexadecimal into binary string, it would better to use .zfill(len(hexadecimal) * 4) to fill the binary string with zeros and avoid string index out of bound error
17	Trick Shot	1. An interesting free fall（自由落体） puzzle
18	Snailfish	1. Use regex and tree to solve the puzzle 2. There is a helpful regex tutorial and a useful regex cheatsheet 3. According to this post on stackoverflow, the class name with __double_leading_and_trailing_underscore__ are essentially reserved for Python itself: "Never invent such names; only use them as documented"
19	Beacon Scanner	1. map takes the whole elements in the iterable variable as one variable, while starmap takes each element in the iterable variable as single variable 2. 24 combinations of 3D orientations which satisfy Right-Hand Rule 3. According to this post on stackoverflow, * unpacks a list or tuple into position arguments, and ** unpacks a dictionary into keyword arguments.