跳到主内容

advent of code

Advent of code 2021

  • Advent of code is a coding challenge in December of each year.
  • One puzzle per day from Dec 1 to Dec 25.
  • No programming language limitation.
  • First half questions seems simple and don't need much knowledge of advanced algorithms.
  • I feel the questions are a good exercise for kids to learn python.
  • hence I prepare this notebook that will prepare some knowledge for students in middle school to finish.

set up python editor

  • pycharm
  • mu editor

register github account

  • use github account to login advent of code
  • create a new repo to record the code for advent of code

learn git

# some simple git flow

# check repo status
git status

# add file to commit
git add .
git commit -m "new updates"

# push to github
git push origin

Day 1

In [ ]:
# read input into python
with open("day01_input.txt", "r") as f:
    lines_input = f.readlines() 
    # lines_input is a list of strings, 
    # each string is one line in the input.txt
    lines = [int(a) for a in lines_input]
    # lines is list of list of integer.
    # here we used `list comprehension`. will discuss it later.
In [ ]:
# example of for loop
# suppose we have 3 lists: part1, part2, part3, all have same size of 10
# we want to add first element of all 3 lists, 
# second elements of all 3 lists, etc

output = [] # we need somewhere to put the outputs
for i in range(10):
    o = part1[i] + part2[i] + part3[i]
    output.append(o)
    
# method2: use list comprehension instead of `for loop`
output = [a+b+c for (a, b, c) in zip(part1, part2, part3)]

# another example of list comprehension
l2 = [a*2 for a in l1]
    

Day 3

In [2]:
# binary string to integer
b_str = "0b1001" # add "0b" prefix
i_num = int(b_str, 2)

print("{} == {}".format(b_str, i_num))
0b1001 == 9
In [3]:
# use recursive function to solve problem.
# The benefit is that you only think one step.
# and the final step where it stops and return.

# a good tutorial at: https://realpython.com/python-thinking-recursively/

# example function 
def fibonacci_recursive(n):
    print("Calculating F", "(", n, ")", sep="", end=", ")

    # Base case. This is where the function will stop
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # Recursive case
    else:
        # note the parameters are decreasing
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

Day 15

  • need A* search algorithm.
  • Python Algorithms by Magnus Lie Hetland, p204
In [5]:
from heapq import heappush, heappop

# example of heapq. 
# you can use it get point with least loss at this moment.

#   (loss, (y, x))
a = (12, (9, 10))
b = (8, (3, 4))
c = (1, (1, 1))

loss = []
heappush(loss, a)
heappush(loss, b)
print("initialized heap: {}".format(loss))

least_loss = heappop(loss)
print("current least loss: {}".format(least_loss))
print("heap after pop: {}".format(loss))

heappush(loss, c)
print("heap after push c: {}".format(loss))
initialized heap: [(8, (3, 4)), (12, (9, 10))]
current least loss: (8, (3, 4))
heap after pop: [(12, (9, 10))]
heap after push c: [(1, (1, 1)), (12, (9, 10))]

Day 25

  • not difficult
  • you may want to use copy.deepcopy to keep a copy of map at each move. For example, if we loop from left to right,
    • >..>
    • .>.>
    • should we move the last one? if you look the updated map, it shows vacancy. but we should look at the original map, which shows no move for the last one.
  • it is fun to print frame by frame like animation.

reference

  • I wrote some code for AoC2021, you can find it here

评论

Comments powered by Disqus