DEV Community: Yuan Gao

Advent of Code 2021: Day 07 with Python, cheating by using scipy

Yuan Gao — Tue, 07 Dec 2021 11:32:22 +0000

Link to challenge on Advent of Code 2021 website

Loading the data

The number is again, comma-separated, so np.loadtxt() does the job

from numpy import np
pos = np.loadtxt("day_7.txt", delimiter=",")

Part 1

So....this is where I cheat. I'd like to get the job done quickly and go about my day. Python has some great libraries for data science, like scipy which has a nice selection of optimizers. We can use one of them.

The problem boils down to an optimization problem where we are to minimize the distance between a collection of 1D points and some target point. We're trying to minimize the sum of target - position for each of the points.

from scipy.optimize import minimize_scalar
res = minimize_scalar(lambda x: np.abs(round(x)-pos).sum())

Job done.

Part 2

Part 2 tells us the cost function isn't linear target - position but is triangle numbers n(n+1) so we simply adjust our cost function accordingly:

res = minimize_scalar(lambda x: (np.abs(round(x)-pos)*(np.abs(round(x)-pos)+1)/2).sum())

Full Code

import numpy as np
from scipy.optimize import minimize_scalar 

pos = np.loadtxt("day_7.txt", delimiter=",", dtype="int32")

res = minimize_scalar(lambda x: np.abs(round(x)-pos).sum())
print("Part 1 result:", round(res.fun))

res = minimize_scalar(lambda x: (np.abs(round(x)-pos)*(np.abs(round(x)-pos)+1)/2).sum())
print("Part 2 result:", round(res.fun))

Advent of Code 2021: Day 06 with Python, and numpy.roll()

Yuan Gao — Mon, 06 Dec 2021 12:34:19 +0000

Link to challenge on Advent of Code 2021 website

Loading the data

The data is a comma-separated list, so we can load this using numpy's np.loadtext() again. We set dtype to uint32 as we'll be using these numbers for indexes later and they'll need to be whole numbers.

lines = np.loadtxt("day_6.txt", delimiter=",", dtype="uint32")

Part 1

Part 1 asks us to track the number of exponentially reproducing fish. While it's possible at this stage to keep an array of every fish, since every fish of the same age behaves the same, we can just keep track of groups of them.

The demo data gives these fish ages: 3,4,3,1,2, this can be reduced to an array of fish, where the index is the age, and the value are their count: [0, 1, 1, 2, 1, 0, 0, 0]

The benefit of this approach is that when fish age, we can simply roll the array around:

Initial: [0, 1, 1, 2, 1, 0, 0, 0]
  Day 1: [1, 1, 2, 1, 0, 0, 0, 0]
  Day 2: [1, 2, 1, 0, 0, 0, 1, 1]
  Day 3: [2, 1, 0, 0, 0, 1, 2, 1]
                            ^  ^
  old fish get added here --^  ^
     new fish get added here --^

To assemble the fish, we can use numpy's np.unique() to return a frequency count of the fish:

fish = np.zeros(9)
age, count = np.unique(lines, return_counts=True)
fish[age] = count

And to implement the roll, we can use np.roll():

gen = np.copy(fish)
for _ in range(80):
    gen[7] += gen[0]
    gen = np.roll(gen, -1)
result = sum(gen)

Taking the sum of the array gives us the total fish.

Part 2

Exactly the same as Part 1, but simulated to 256 generations. I assume the reason for part 2 like this is to trip up anyone who implemented Part 1 inefficiently, since it would take a lot of RAM to keep track of individual fish without grouping them.

gen = np.copy(fish)
for _ in range(256):
    gen[7] += gen[0]
    gen = np.roll(gen, -1)
result = sum(gen)

Full Code

import numpy as np

lines = np.loadtxt("day_6.txt", delimiter=",", dtype="uint32")
fish = np.zeros(9)
age, count = np.unique(lines, return_counts=True)
fish[age] = count

gen = np.copy(fish)
for _ in range(80):
    gen[7] += gen[0]
    gen = np.roll(gen, -1)
result = sum(gen)
print("Part 1 result:", result)

gen = np.copy(fish)
for _ in range(256):
    gen[7] += gen[0]
    gen = np.roll(gen, -1)
result = sum(gen)
print("Part 2 result:", result)

Advent of Code 2021: Day 05 with Python, even more numpy

Yuan Gao — Sun, 05 Dec 2021 06:30:16 +0000

Link to challenge on Advent of Code 2021 website

Loading the data

This time, there's no shortcuts to loading data, it's regex time. The data is a pair of coordinates, and an arrow, and then another pair of coordinates:

578,391 -> 578,322
274,585 -> 651,962
482,348 -> 294,348

We can read this in using regex pattern (\d+),(\d+) -> (\d+),(\d+). We also grab the max bounds of the coordinates as well.

lines = open("day_5.txt").readlines()
coords = np.array([re.match('(\d+),(\d+) -> (\d+),(\d+)', line).groups() for line in lines]).astype(int)
size = np.max(coords)+1

Part 1

Part 1 asks us to draw these lines on the grid, and find out how many lines overlap. It also asks us to only consider horizontal and vertical lines.

Horizontal and vertical lines are characterized by having x or y coordinates equal, so we can filter those out:

hv = coords[(coords[:, 0] == coords[:, 2]) | (coords[:, 1] == coords[:, 3])]

Then for each of these, we increment the specific indices of the array that they cover:

def rrange(start, stop):
    return range(start, stop+1) if stop >= start else range(start, stop-1, -1)

grid = np.zeros((size, size))
for x1, y1, x2, y2 in hv:
    grid[rrange(y1, y2), rrange(x1, x2)] += 1
result = (grid >= 2).sum()

The rrange() function is a small helper to allow range() to run backwards properly. Because range(1, 5) works fine, but range(5, 1) does not unless specifying the step size as -1 with range(5, 1, -1). The coordinates are also adjusted to make the values inclusive.

Once the grid values have been incremented, we can find all the grid elements with values greater or equal to 2, giving the answer.

Part 2

Part 2 asks us to look at not just horizontal and vertical lines, but also diagonal ones. Oddly, we already wrote the code in a way that's general, so no extra code is needed, we just iterate over the original unfiltered coordinates rather than the ones filtered for only horizontal/vertical lines

grid = np.zeros((size, size))
for x1, y1, x2, y2 in coords:
    grid[rrange(y1, y2), rrange(x1, x2)] += 1
result = (grid >= 2).sum()

Full code

import numpy as np
import re

lines = open("day_5.txt").readlines()
coords = np.array([re.match('(\d+),(\d+) -> (\d+),(\d+)', line).groups() for line in lines]).astype(int)
size = np.max(coords)+1

def rrange(start, stop):
    return range(start, stop+1) if stop >= start else range(start, stop-1, -1)

grid = np.zeros((size, size))
hv = coords[(coords[:, 0] == coords[:, 2]) | (coords[:, 1] == coords[:, 3])]
for x1, y1, x2, y2 in hv:
    grid[rrange(y1, y2), rrange(x1, x2)] += 1
result = (grid >= 2).sum()
print("Part 1 result:", result)

grid = np.zeros((size, size))
for x1, y1, x2, y2 in coords:
    grid[rrange(y1, y2), rrange(x1, x2)] += 1
result = (grid >= 2).sum()
print("Part 2 result:", result)

Advent of Code 2021: Day 04 with Python, and numpy masked arrays

Yuan Gao — Sat, 04 Dec 2021 18:08:51 +0000

Link to challenge on Advent of Code 2021 website

Loading the data

The data comes as a text file with two distinct chunks. The first line is a comma-separated list of numbers that will be used for bingo number draws. The rest of the file contains several bingo grids.

An example of the data is:

7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1

22 13 17 11  0
 8  2 23  4 24
21  9 14 16  7
 6 10  3 18  5
 1 12 20 15 19

 3 15  0  2 22
 9 18 13 17  5
19  8  7 25 23
20 11 10 24  4
14 21 16 12  6

14 21 17 24  4
10 16 15  9 19
18  8 23 26 20
22 11 13  6  5
 2  0 12  3  7

The draws can be read easily using a single fp.readline() which reads a single line of text from an open file. We can .split(",") this string to chop it up into individual values, and then we can apply int() to each of those elements (using map()) to turn it back into a number. (the extra list() is needed to turn the iterator returned by map() into an actual list, since we have to use this list twice.

with open("day_4.txt") as fp:
    draws = list(map(int, fp.readline().split(",")))

The bingo boards themselves, we can read in using numpy's np.mat() function, which takes a space/semicolon separated string and turns it into a numpy matrix. For example: np.mat("1 2 3; 4 5 6; 7 8 9") returns a 3x3 matrix with those numbers in it.

So we use fp.read() which by default reads all the lines of the open file as an array of strings, and split it using double newlines: fp.read()[1:-1].split("\n\n") (we have to ignore the first and last entry of the file to avoid the empty lines

This will return an array of board strings, for example:

[
  '90  8  2 34 41\n11 67 74 71 62\n47 42 44  1 17\n21 55 12 91  6\n60 69 75 92 56',
'49 29 60 45 31\n94 51 73 33 67\n21 92 53 95 96\n 2 55 52  8 87\n 4 36 76 83 42', '23 66 50 84 58\n62 98 81 76 57\n24  2 56 79  6\n55  0 16 64 38\n12 67  5 97 60',

From there we can replace the newlines with semicolons, and put it through np.mat() to retrieve a numpy matrix of the data.

The final import code is:

with open("day_4.txt") as fp:
    draws = list(map(int, fp.readline().split(",")))
    boards = [np.mat(board.replace("\n", ";")) for board in fp.read()[1:-1].split("\n\n")]

Part 1

Part 1 asks which board will win at bingo. So we will play bingo, iterating over each draw, and each board, and "marking" the matching values.

Fortunately, numpy has a useful feature called masked_array() which will maintain a matrix or array and a mask, allowing you to easily mask the data or get the sum of unmasked data.

We can construct a masked array using np.ma.masked_array(board) which initializes the mask to all False. We'll use False as meaning "not yet drawn", and True as "drawn".

To work out whether a drawn number draw is inside the mask, we can do board.data == draw (board.data in a masked array is the original unmasked data) this will return a 5x5 matrix of False or True if that element matches. So something like:

matrix([[False, False, False, False, False],
        [False, False, False, False, False],
        [False,  True, False, False, False],
        [False, False, False, False, False],
        [False, False, False, False, False]])

We can use this to directly update the mask, using a boolean operation: board.mask |= board.data == draw. This will perform a binary OR operation between the above, and the current mask. In effect, it'll turn the mask to True for any value matching the draw. As the game progresses, more and more of the mask will be turned to True.

To work out whether we have a win, we can use numpy's sum(axis) method to sum the mask along certain axes. It'll do all five rows or columns at once. so, board.mask.sum(0) will give us how many masked values are in each column. If the mask was the above, then:

board.mask.sum(0):

matrix([[0, 1, 0, 0, 0]])

board.mask.sum(1):

matrix([[0],
        [0],
        [1],
        [0],
        [0]])

It can be seen that if any of these row or column sums reaches 5, then there is a bingo. So to test for both, we can check if any of the values returned is a 0: if np.any(board.mask.sum(0) == 5) or np.any(board.mask.sum(5) == 0):

The code is therefore:

for draw, board in product(draws, [np.ma.masked_array(board) for board in boards]):
    board.mask |= board.data == draw
    if np.any(board.mask.sum(0) == 5) or np.any(board.mask.sum(1) == 5):
        result = board.sum()*draw
        break

Here, we're using itertools.product to combine the for loops for both the draw and the board, this makes it a bit easier to break out of the loop.

The question calls for the sum of the remaining undrawn numbers. multiplied by the last drawn number. Numpy's masked arrays have a sum() method which will sum unmasked numbers directly, so the result can be simply calculated above as board.sum()*draw

Part 2

In part 2, it asks which is the board that will win last if the game continues even if boards have a bingo. To this we can reuse the above, but track which boards have won, and pull out the last board to win.

Only a few modifications are needed:

won_boards = set()
for draw, (idx, board) in product(draws, enumerate([np.ma.masked_array(board) for board in boards])):
    board.mask |= board.data == draw
    if np.any(board.mask.sum(0) == 5) or np.any(board.mask.sum(1) == 5):
        if idx not in won_boards and len(won_boards) == len(boards) -1:
            result = board.sum()*draw
            break
        won_boards.add(idx)

Firstly, boards that have won are tracked in the won_boards set. Next, we also fetch the index number of the board using an enumerate() on the boards. This index is what is added to won_boards if the board wins. Then, the last win can be detected using if idx not in won_boards and len(won_boards) == len(boards) -1:, giving us the result of the last win.

Full Code

import numpy as np
from itertools import product

with open("day_4.txt") as fp:
    draws = list(map(int, fp.readline().split(",")))
    boards = [np.mat(board.replace("\n", ";")) for board in fp.read()[1:-1].split("\n\n")]

for draw, board in product(draws, [np.ma.masked_array(board) for board in boards]):
    board.mask |= board.data == draw
    if np.any(board.mask.sum(0) == 5) or np.any(board.mask.sum(1) == 5):
        result = board.sum()*draw
        break
print("Part 1 result:", result)

won_boards = set()
for draw, (idx, board) in product(draws, enumerate([np.ma.masked_array(board) for board in boards])):
    board.mask |= board.data == draw
    if np.any(board.mask.sum(0) == 5) or np.any(board.mask.sum(1) == 5):
        if idx not in won_boards and len(won_boards) == len(boards) -1:
            result = board.sum()*draw
            break
        won_boards.add(idx)
print("Part 2 result:", result)

Advent of Code 2021: Day 03 with Python, and more numpy

Yuan Gao — Fri, 03 Dec 2021 06:23:07 +0000

Link to challenge on Advent of Code 2021 website

Loading the data

The data is a big list of binary values, but we actually need to load the data as a big matrix of 1 or 0 to be able to efficiently slice the matrix while doing calculations.

To do this, we can have numpy fix the data for us. A regular import of lines using "U" format code for strings, imports the data as an array of strings. We also want to know how many bits are in each value, which we get from the first entry.

lines = np.loadtxt("day_3.txt", "U")
bits = int(len(lines[0]))

Resulting in:

array(['011010010110', '101110100110', '011011011110', '100011010001',
       '011011100111', '011000100101', '101101011001', '010001001001',
       '100010110111', '001110110101', '100111011001',

Then, we can make a view of the data, which will give us a single large array containing one character per entry, and we also cast it to int type:

lines.view('U1').astype(int)

Resulting in:

array([0, 1, 1, ..., 1, 1, 0])

Finally, we need to put this back into the right shape that it was in before, so we reshape it. The final import code is:

lines = np.loadtxt("day_3.txt", "U")
bits = int(len(lines[0]))
data = lines.view('U1').astype(int).reshape(lines.shape[0], bits)

Binary array to int conversion

For both parts of the question, we need to convert an array of bits, like [0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0] into a number like 1602. There are several ways of doing it, the way I've chosen is to multiply the array by another array that is made up of powers of 2: [..., 32, 16, 8, 4, 2, 1]. So I will pre-calculate pow2 early on in the code:

pow2 = 1<<np.arange(bits)[::-1]

Other methods involve converting the array into a string, and using python's built-in int() function to convert it. int has base-conversion abilities:

bin2dec = lambda x: int("".join(map(str,x.astype(int))),2)

Finally, numpy actually has a function to pack bits back into bytes, however it's a little awkward to use as you need to pad it out to the correct number of values for your eventual type.

bin2dec = lambda x: np.packbits(np.pad(x,[32-bits, 0])).view('>u4')

I'll be using the pow2 method, precalculating it, and doing pow2.dot(x) any time I want to convert x to a number.

Part 1

Part 1 requires counting the number of 0 or 1 in each column and comparing them to see which one is more. Since numpy can directly tell us all the elements that have a given value, and it can also do this per axis.

So the number of 1 in every bit position is:

ones = (data == 1).sum(axis=0)

The result is a count for each column:

array([483, 487, 485, 467, 513, 509, 492, 532, 508, 497, 490, 506])

Doing the same for zeros, and then comparing the two produces an array of true/false, and this can be turned back into a number my doing a dot product against pow2 which was precalculated earlier.

ones = (data == 1).sum(axis=0)
zeros = (data == 0).sum(axis=0)
result = pow2.dot(ones > zeros) * pow2.dot(ones < zeros)

Part 2

Part 2 is...long. I don't even know if I can paraphrase the problem exactly. The idea is to take each column of bits successively, and test to see if each row has a bit value that is the same as the majority of other bits, and discard the value if not. Repeating for the minority case.

To achieve this, we loop through the columns using a for loop:

for idx in range(bits):
  column = data[:, idx]

And then for this columm of pixels, we figure out whether there are more 1 than 0 by taking the sum of the column, and seeing if that number is greater than half the size of the column:

column.sum()*2 >= column.size

This will return True if the 1s are more common than the 0s. Since we need to then collect all the entries that match this value, we can do:

column == (column.sum()*2 >= column.size)

This will return an array of True or False depending on whether the value in column is the same as the majority value or not.

Then, we can select just these entries out of our data matrix, and discard the rest, by using this array as the subscript when accessing the data matrix:

data[column == (column.sum()*2 >= column.size)]

We have to apply this algorithm iteratively over the columns of the array, and stop when data gets to 1 row

for idx in range(bits):
  column = data[:, idx]
  data = data[column == (column.sum()*2 >= column.size)]
  if len(data) == 1:
    break

However, we have to repeat this for the minority case as well. So the final code looks like:

a = b = data
for idx in range(bits):
    acol = a[:, idx]
    bcol = b[:, idx]
    a = a[acol == (acol.sum()*2 >= acol.size)] if len(a) > 1 else a
    b = b[bcol == (bcol.sum()*2 < bcol.size)] if len(b) > 1 else b
result = pow2.dot(a[0] == 1) * pow2.dot(b[0] == 1)

Full Code

import numpy as np

lines = np.loadtxt("day_3.txt", "U")
bits = int(len(lines[0]))
data = lines.view('U1').astype(int).reshape(lines.shape[0], bits)
pow2 = 1 << np.arange(bits)[::-1]

ones = (data == 1).sum(axis=0)
zeros = (data == 0).sum(axis=0)
result = pow2.dot(ones > zeros) * pow2.dot(ones < zeros)
print("Part 1 result:", result)

a = b = data
for idx in range(bits):
    acol = a[:, idx]
    bcol = b[:, idx]
    a = a[acol == (acol.sum()*2 >= acol.size)] if len(a) > 1 else a
    b = b[bcol == (bcol.sum()*2 < bcol.size)] if len(b) > 1 else b
result = pow2.dot(a[0]) * pow2.dot(b[0])
print("Part 2 result:", result)

Advent of Code 2021: Day 02 with Python, numpy, and affine transformation matrices

Yuan Gao — Thu, 02 Dec 2021 09:23:42 +0000

Link to challenge on Advent of Code 2021 website

Loading the data

The input file consists of a direction, and a number on each line, which we can split into an array using line.split(), and iterate over using file.readlines(). Note: in-line opening a file like this with open() outside a context manager is generally bad practice, but relatively benign in a small script like this.

lines = [line.split() for line in open('day_2.txt').readlines()]

Part 1

Part 1 involves interpreting the input file as directions and distances, adding together the distance travelled. If we think about this in mathematical terms, this involves adding together vectors representing depth and forward distance.

When we deal with 2-vectors, Python gives us a little shortcut: native support for complex numbers. We can use a single complex number to represent a 2-vector, and do arithmetic on it as normal. The two are functionally equivalent:

a = [0, 1]
b = [1, 1]
c = [a[0] + b[0], a[1] + b[1]]

a = 0 + 1j
b = 1 + 1j
c = a + b

To start, we create a dictionary of moves. This helps us look up the correct move vector without having to do an if statement

moves = dict(forward=1, down=1j, up=-1j)

Then, we apply (map()) a function that multiplies together one of these move vectors and the distance number provided in the file. And then sum together all the resultant vectors for the final position of the sub.

pos = sum(map(lambda line: moves[line[0]]*int(line[1]), lines))

The result the question asks for is the two position components multiplied together.

multiplied = pos.real * pos.imag

Part 2

Part 2 introduces the idea that there is an "aim" state, and the instructions can change this aim instead of moving the position of the sub. There are many ways to solve this problem, since I already started on using vectors, I've chosen to continue with that in Part 2, treating this as an affine transformation problem, and using numpy dot product to move the sub and its internal "aim" state.

The moves can be expressed as:

# down move
new_aim = aim + amount

# up move
new_aim = aim - amount

# forward move
new_dist = dist + amount
new_depth = depth + depth * aim

In terms of affine transformation matrices, with our augmented vector being [dist, depth, aim, 1] (a is the amount we're moving by)

# down move
[1, 0, 0, 0] # dist
[0, 1, 0, 0] # depth
[0, 0, 1, a] # aim
[0, 0, 0, 1] # 1

# up move
[1, 0, 0, 0] # dist
[0, 1, 0, 0] # depth
[0, 0, 1,-a] # aim
[0, 0, 0, 1] # 1

# forward move
[1, 0, 0, a] # dist
[0, 1, a, 0] # depth
[0, 0, 1, 0] # aim
[0, 0, 0, 1] # 1

To make this a little easier, we can decompose these moves down to the Identity plus the amount multiplied by the non-diagonal matrix: I_4 + amount * M

In code, producing a moves dictionary containing just the non-diagonal unit matrix:

moves = defaultdict(lambda: np.zeros([4, 4]))
moves["down"][2, 3] = 1
moves["up"][2, 3] = -1
moves["forward"][0:2, 2:4] = [[0,1],[1,0]]

Here, defaultdict is used to help us set up the matrices without having to write out every element, since it is sparse.

We can now iterate over each line, fetching the correct transformation matrix, and applying a dot product with the position vector. Using reduce() to avoid writing out a loop.

pos = reduce(lambda pos, line: (np.identity(4)+moves[line[0]]*int(line[1])).dot(pos), lines, [0, 0, 0, 1])

The result, as before, is the first two elements of the position vector multiplied

multiplied = pos[0]*pos[1]

Full Code:

lines = [x.split() for x in open('day_2.txt').readlines()]

moves = dict(forward=1, down=1j, up=-1j)
pos = sum(map(lambda line: moves[line[0]]*int(line[1]), lines))
result = pos.real * pos.imag
print("Part 1 result:", result )

from collections import defaultdict
from functools import reduce
import numpy as np

moves = defaultdict(lambda: np.zeros([4, 4]))
moves["down"][2, 3] = 1
moves["up"][2, 3] = -1
moves["forward"][0:2, 2:4] = [[0,1],[1,0]]

pos = reduce(lambda pos, line: (np.identity(4)+moves[line[0]]*int(line[1])).dot(pos), lines, [0, 0, 0, 1])
result = pos[0]*pos[1]
print("Part 2 result:", result )

Advent of Code 2021: Day 01 with Python and numpy's convolution function

Yuan Gao — Wed, 01 Dec 2021 13:10:36 +0000

Link to challenge on Advent of Code 2021 website

Loading the data

Loading the data is straightforward with numpy, which by default can load new-line separated numbers into a numpy array and do the string-to-number conversion in one go:

import numpy as np

lines = np.loadtxt("day_1.txt")

Part 1

Part 1 involves finding how many numbers in a list are greater than the previous number. With Numpy, this is actually quite simple, because it'll do element-wise calculations on whole lists for you.

So writing lines[1:] > lines[:-1] means "do the greater-than comparison for each element on a list that is a shifted version of the data and itself (minus the last element, to match up the lengths)". The result is an array of True or False depending on whether that position had an increase or not. We can sum those (effectively counting the True values) to find the result:

increases = (lines[1:] > lines[:-1]).sum()

Part 2

In part 2, the question introduces a sliding window sum to smooth out the values. The task is to check if the sliding window sum goes up or down. An easy way to implement this is to recognize that a sliding window is a convolution operation with the kernel [1, 1, 1]. The "valid" argument ensures there's no extra padding either side the result, so it's the same size as the input data.

convolved = np.convolve(lines, [1, 1, 1], "valid")

The result is an array containing the moving window sums, which we can compute the number of increased values like before:

increases = (convolved[1:] > convolved[:-1]).sum()

Part 2 alternative solution

Another way to approach Part 2 is to realize that comparing two sliding windows is the same as comparing the unique values in them. If I were to write out the calculation going on, it would look like:

a[i+1] + a[i+2] + a[i+3] > a[i] + a[i+1] + a[i+2]

It can be seen that a[i+1] and a[i+2] appear on both sides, and therefore cancel out, leaving just a[i+3] > [ai]. Therefore Part 2 can be achieved using the same element-wise calculation as Part 1, by shifting the lists by 3 rather than 1, skipping needing to do any convolution:

increases = (lines[3:] > lines[:-3]).sum()

Full code:

import numpy as np
lines = np.loadtxt("day_1.txt")

increases = (lines[1:] > lines[:-1]).sum()
print("Part 1 result:", increases)

increases = (lines[3:] > lines[:-3]).sum()
print("Part 2 result:", increases)

Collecting and processing user-submitted images with Airtable and Firebase

Yuan Gao — Wed, 01 Sep 2021 08:15:39 +0000

A quick weekend project writeup. Loungeware is a community-developed Warioware-style game, with contributions of art, code, and music from the GameMaker community. The game features user-submitted images of a character known as Larold.

// Detect dark theme var iframe = document.getElementById('tweet-1422712107259334658-985'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1422712107259334658&theme=dark" }

Previously, Larolds were submitted as .png files sent over Discord, which had to be handled through a multi-step process:

Ensure images were 200x200px
Ensure images stuck to a 2-color palette (no Anti Aliasing)
Collect contributor name and other metadata into an array in the code
Copy the image into a frame of the sprite, ensuring the sprite's image index matches the metadata array
Separately copy the image and metadata over to the website repository for the online gallery/credits

The process, though simple, is times-consuming and error-prone, so I desired to automate it. To do so, I'm going to use Airtable, which allows me to create a web-based form for users to submit images and other data; and Firebase functions, to both process and store the processed images.

Airtable

Airtable is an online service that's a combination of a spreadsheet and a database. It lets you create databases that you can query with an API. It can also create submission forms, which is what we're after here.

I create a simple database for Larold submissions, this is the Grid View (i.e. spreadsheet view) of the data, showing the columns that I've set up.

Once this is set up, I can create a new public Form that allows users to submit data into the database. While the data and grid view are private, the public form can be used by users to post their new Larold submissions. Those familiar with Google Docs will see that this is very similar to Google Forms

A nice view, which only admins get to see, is the Gallery view, which shows a larger view of the image.

API access to Airtable

Automation wouldn't be possible without programatic access to the data. My reason for picking Airtable is its easy-to-use API for accessing the data.

First we must generate an API key via my account settings

Next, I can try out fetching the data via HTTP request, using Postman!

From the screenshot above, it can be seen that records in the database come out as JSON structures in a records array, with the full field name as the key; with the uploaded images available as a public URL on Airtable's CDN.

Processing the images

Because some of these images are not the right dimensions or right colours, we're going to process the images. I've been a long-time user of Imagemagick, a command-line image processing tool. Fortunately Firebase function's execution environment actually has Imagemagick installed in it, meaning we can use it to process images (in fact, the environment includes ffmpeg too!). I use a firebase function, which when triggered, will do the following things:

Fetch the latest data from Airtable
Sync the data to Firestore so that the metadata is available to the website for the gallery
Process the images if required, and then store them in Cloud Storage so the data is available to the gallery
Generate a sprite strip containing all of the Larold images on one PNG image
Return the sprite strip and metadata json as a .zip file

Step 1: Fetch the latest data from Airtable

To make things easier, I'm using the official Airtable npm package to access the API. When

Using the Airtable package, setting up access is relatively straightforward:

const functions = require("firebase-functions");
const Airtable = require("airtable");

Airtable.configure({
  endpointUrl: "https://api.airtable.com",
  apiKey: functions.config().airtable.api_key,
});
const base = Airtable.base(functions.config().airtable.base);

async function doSync() {
  const records = await base("Larolds").select({
    view: "Grid view",
  }).all();
}

Here, I'm using firebase's functions.config() to fetch secrets from the environment to avoid hard-coding sensitive values in the code. Once this is set up, base("Larolds").select().all(); fetches all the records (handling pagination for us). The result is a structure of records that can be iterated over.

Step 2: Sync with Firestore

I'll skip Firestore setup (there are other guides for that!) Because I'm synchronizing all the records, unfortunately I have to do a slightly awkward thing of fetching all records out of a Firestore collection, checking their modified dates, and then writing any changes back. This is awkward because Firestore isn't particularly well suited for situations where you always update all the records at once. In reality, I should be writing all this data to a single firestore document to optimize for access costs. However, for a low-traffic site, I will go with individual documents for now, and update later if necessary:

const records = await base("Larolds").select({
    view: "Grid view",
  }).all();

  functions.logger.info("Got larolds from airtable", {count: records.length});

  const existingDocuments = await laroldStore.listDocuments();
  const existingData = Object.fromEntries(existingDocuments.map((doc) => [doc.id, doc.data]));

  // Update image
  const laroldData = await Promise.all(records
      .filter((record) => (record.get("Image file").length > 0 && record.get("Confirmed for use") == "Yes"))
      .map(async (record, idx) => {
        const image = record.get("Image file")[0];
        const id = image.id; // use the image unique ID as id
        const modified = record.get("Last modified");

        // Check if updated
        let doc;
        if (!existingData[id] || existingData[id].modified != modified) {
          const imageUrl = image.url;
          const {warnings, destination} = await processImage(imageUrl, image.filename, id);
          doc = {
            id: id,
            name: record.get("Larold name"),
            attribution: record.get("Attribution name"),
            submitter: record.get("Submitter"),
            imageUrl,
            modified,
            idx: idx+1,
            warnings,
            destination,
          };
          await laroldStore.doc(id).set(doc);
        } else {
          doc = existingData[id];
        }

        return doc;
      }));
  const updatedIds = laroldData.map((doc) => doc.id);
  functions.logger.info("Updated larolds in store", {updatedIds});

  // Remove old ones
  const deleteDocs = existingDocuments.filter((doc) => !updatedIds.includes(doc.id));
  const deletedIds = deleteDocs.map((doc) => doc.id);
  await Promise.all(deleteDocs.map((doc) => doc.delete()));

This big chunk of of a script fetches all the records from Airtable, and from Firestore, iterates over them, and figures out which documents need updating (and updates them), which ones are stale (and deletes them), and also returns the data as an object to be returned in the zip.

Note there's a line const {warnings, destination} = await processImage(imageUrl, image.filename, id); in the code above which is covered in the next step. The reason this code is inside this if check is to avoid having to process an image that was already processed.

The results can be seen with Firebase's excellent local emulators, which allow testing functions and firestore locally:

Step 3 Process image

Processing the image will use ImageMagick via the https://www.npmjs.com/package/gm, the details for this are covered in an official Firebase tutorial. Unfortunately ImageMagick itself is a little hard to learn to begin with due to there being a lot of outdated, and frankly quite hard to follow instructions, combined with gm being also outdated and not good documentation. Luckily my familiarity of ImageMagick combined with some digging around the source code helped me figure this one out.

The image processing is split into three further steps, we need to:

Generate a palette image, which is needed to re-map any "unauthorized" colors to the limited two-color palette that Larold images must use.
Count the number of colors in the image so that warnings can be generated, so we can alert the artist that their images are wrong, should they wish to update them
Resize and remap the image and upload to a bucket.

Step 3.0 Generate palette image

We only need to do this once, and I actually encountered a race-hazard trying to do this, because two iterations will try to generate the palette at the same time) so I've had to wrap it in a mutex (via the async-mutex npm package)

async function drawPalette() {
  const palettePath = "/tmp/palette.png";

  await paletteMutex.runExclusive(async () => {
    try {
      await fs.access(palettePath);
    } catch (error) {
      await new Promise((resolve, reject) => {
        gm(2, 1, "#1A1721FF")
            .fill("#FFC89C")
            .drawPoint(1, 0)
            .write(palettePath, (err, stdout) => {
              if (err) {
                reject(err);
              } else {
                functions.logger.info("Created palette file", {palettePath, stdout});
                resolve(stdout);
              }
            });
      });
    }
  });

  return palettePath;
}

This function asks gm/imagemagick to draw a 2x1 pixel PNG file containing the colors #1A1721 and #FFC89C the two authorized colors of larolds.

Step 3.2 Count the number of colors

gm/imagemagick's identify() function will quickly read out how many actual colors used in the image, and return it

async function countColors(file) {
  return new Promise((resolve, reject) => {
    gm(file).identify("%k", (err, colors) => {
      if (err) {
        reject(err);
      } else {
        resolve(colors);
      }
    });
  });
}

Step 3.3 Process it

The following function pulls these pieces together, and uses axios to fetch the image from URL, writes to temporary files, does the resize and remap conversion, uploads to bucket storage, and returns any warnings generated

async function processImage(url, originalFilename, id) {
  const tempFileIn = `/tmp/${id}_${originalFilename}`;
  const tempFileOut = `/tmp/${id}.png`;

  // get file
  const res = await axios.get(url, {responseType: "arraybuffer"});
  await fs.writeFile(tempFileIn, res.data);
  functions.logger.info("Got file", {url, tempFileIn});

  // check colors
  const colors = await countColors(tempFileIn);

  // make palette
  const palettePath = await drawPalette();

  // do conversion
  await new Promise((resolve, reject) => {
    gm(tempFileIn)
        .resize(200, 200, ">")
        .in("-remap", palettePath)
        .write(tempFileOut, (err, stdout) => {
          if (err) {
            reject(err);
          } else {
            functions.logger.info("Processed image", {tempFileOut, stdout});
            resolve(stdout);
          }
        },
        );
  });

  // upload
  const destination = `larolds/${id}.png`;
  await bucket.upload(tempFileOut, {destination});

  // assemble warnings
  const warnings = [];
  if (colors != 2) {
    warnings.push(`Incorrect number of colors (${colors}) expected 2`);
  }

  await fs.unlink(tempFileIn);
  // await fs.unlink(tempFileOut); // might use this for cache

  functions.logger.info("Uploaded image", {destination, warnings});
  return {
    warnings,
    destination,
  };
}

Strictly speaking this should be broken out to more functions to be cleaner.

Step 4: Generate sprite strip

Finally, once all images are processed, and safely uploaded to the bucket, we can generate the sprite strip.

This code will take in a data structure created by Step 2, and either pull down the image from bucket storage, or conveniently find the processed output file that was left in the tmp folder

async function makeComposite(laroldData) {
  // ensure images are downloaded
  const localPaths = await Promise.all(laroldData.map(async (doc) => {
    const localPath = `/tmp/${doc.id}.png`;
    try {
      await fs.access(localPath);
    } catch (error) {
      functions.logger.info("Downloading image", {destination: doc.destination});
      await bucket.file(doc.destination).download({destination: localPath});
    }
    return localPath;
  }));

  // montage
  const buffer = new Promise((resolve, reject) => {
    localPaths.slice(0, -1)
        .reduce((chain, localPath) => chain.montage(localPath), gm(localPaths[localPaths.length -1]))
        .geometry(200, 200)
        .in("-tile", "x1")
        .toBuffer("PNG", (err, buffer) => {
          if (err) {
            reject(err);
          } else {
            resolve(buffer);
          }
        },
        );
  });

  // cleanup
  await Promise.all(localPaths.map((localPath) => fs.unlink(localPath)));

  return buffer;
}

A fun thing done here is the use of slice and reduce to assemble the method chain needed to montage the images together. The code would normally be this for a three-image montage: gm(image2).montage(image0).montage(image1), and for some reason it puts the image in the argument of gm() to the right. So to handle arbitrary length chains, we can loop over the values:

let chain = gm(localPaths[localPaths.length -1]);
for (let i = 0; i < localPaths.length-1; i++) {
  chain = chain.montage(localPaths[i]);
}

Which can be simplified using reduce:

localPaths.slice(0, -1).reduce((chain, localPath) => chain.montage(localPath), gm(localPaths[localPaths.length -1]))

Step 5: Generate zip

Handling zip files uses the jszip npm library, which conveniently can asynchronously return a zip inside a nodebuffer, which Firebase Function's express.js runtime can return directly.

  // generate composite and zip
  const zip = new JSZip();
  zip.file("larolds.json", JSON.stringify(laroldData, null, 2));

  if (laroldData.length > 0) {
    const compositeBuffer = await makeComposite(laroldData);
    zip.file(`larolds_strip${laroldData.length}.png`, compositeBuffer, {binary: true});
  }

  functions.logger.info("Done sync", {laroldData});
  return zip.generateAsync({type: "nodebuffer"});

And done! I've deliberately not included the full source file as it's quite large, but hopefully the above code examples are useful to someone who wants to also use gm/imagemagick inside firebase functions to process images from Airtable. I've found the execution to require slightly more RAM than the default 256MB that Firebase functions are set up with, it's currently running happily at 512MB RAM, but may need to be bumped up for handling larger images.

The current usage is to simply download the zip file when needed, but in a future iteration, we may have CI/CD download this zip file and commit them into the repo for every merge into main branch, to make this even more automated.

How to set up custom Github webhook notifications on Discord (via Firebase)

Yuan Gao — Tue, 24 Aug 2021 19:27:59 +0000

When working in a team, or a public project, sometimes you want to see github activity notifications in your discord chats (because who pays attention to github notification emails? got too many emails as it is). Discord actually provides this functionality out of the box as part of webhooks, you can set up a webhook with github and immediately start receiving notifications, which look like this:

However, you don't have much control over how this notification is presented, and you only get coarse-grain control over what notifications are sent, or people to ping. So I threw up a small firebase function (written in Javascript) to serve as an intermediary between GitHub and Discord to give me this control. Here's how I did it:

Step 1: Set up new/existing Firebase project

I won't go into it here, but you can pretty much drive the whole thing from the firebase CLI (docs), and goes something like this:

With node.js and NPM installed, npm install -g firebase-tools to install the firebase CLI tools
Then firebase login to log in (following the prompts)
Then firebase init functions in a new folder to set up a new project with Firebase functions. You can either select an existing firebase project from the menu (if you created a new firebase project online or previously), or the CLI will let you create a new firebase project. I selected Javascript, and some other default settings.

Step 2: Install some stuff

Github provides a convenient library for webhooks called @octokit/webhooks to make processing them easily, which can be installed using npm install @octokit/webhooks from inside the new functions folder that firebase creates.

It's also possible to install discord.js library which helps you format the outgoing webhooks to Discord API, but I've decided not to use this as the use-case is relatively simple, and I didn't want to install quite a large library unnecessarily. Had the use-case been more complicated (if we had more than one type/format of notification to send), I would have gone with it.

Step 3: Add a github webhook receiving endpoint

Inside the index.js file I added the following boilerplate for handling github webhooks using the octokit webhooks library:

const functions = require("firebase-functions");
const octokit = require("@octokit/webhooks");

const webhooks = new octokit.Webhooks({
  secret: functions.config().github_webhook.secret,
});

const runtimeOpts = {
  memory: "128MB",
};

exports.githubNotifier = functions.runWith(runtimeOpts)
    .https.onRequest((request, response) => {
      const event = request.headers["x-github-event"];
      const hook = {
        id: request.headers["x-github-delivery"],
        name: event,
        payload: request.rawBody.toString(),
        signature: request.headers["x-hub-signature-256"],
      };

      return webhooks.verifyAndReceive(hook).then(() => {
        response.status(200).send("Webhook handled");
      }).catch((err) => {
        functions.logger.error(err);
        response.status(500).send("Webhook not processed");
      });
    });

This code by itself will validate webhooks from github, checking that the secret value is what is provided. At the moment there's no actual code to handle the webhooks, but it will at least receive and validate them. The secret is important, as it will prevent other people who don't know your secret from arbitrarily pinging your webhook and sending random unauthorized notifications to your discord.

The secret value in the code above uses functions.config().github_webhook.secret which reads a secret value from firebase config. You can set the value using cli by running the command (come up with some suitable secret/password here):

firebase functions:config:set github_webhook.secret="<insert your secret here>"

This avoids having to paste secret values into your code, perfect for when your code might be open source or a community project - other contributors or the public will be able to see your code but won't be able to see your secrets.

At this point, you can deploy this function to check everythings good. This can be done from the cli by using the command:

firebase deploy

OR if you're in a project with other firebase stuff in it, you can deploy just this function, rather than everything else.

firebase deploy --only "functions:githubNotifier"

Step 4: Set up webhooks on Github

Once the function is deployed, you can find its HTTP url on the Firebase web console:

This is the URL that you want Github to send webhooks to. Copy this, then go over to your github hooks in your repository (Settings > Webhooks, then Add webhook)

Set the Payload URL to the address from firebase. Set the content type to application/json. Set the Secret to the secret set in the previous step.

Optionally, select Let me select individual events and then select just the events you want to notify on. You don't have to do this as you can filter out the events in the functions in a sec. But it may be nicer to restrict it here to save on how many times your function will have to trigger. I have it set to notify on: "Issues", "Issue comments", "Pull requests", and "Releases".

Step 5: Send some test webhooks

Once you've set it up, you can try create a PR or an issue, or anything that triggers the webhook, and go over to the "Recent Deliveries" tab of the webhook, where you can inspect the delivery status and payload of the webhook

Over on Firebase functions, you can inspect the logs for the function that was deployed to check that it correctly handled the incoming webhook. You should see the standard set of logs that firebase produces whenever it handles an event

Step 6: Set up incoming webhooks on Discord

Now that it's confirmed that github webhooks can trigger firebase functions correctly, it's time to hook up actual functionality and send hooks to Discord. Discord API allows incoming webhooks to send messages into a specific channel on Discord. You can set these up in the Server settings > Integrations > Webhooks. Create one, and copy the webhook URL:

I'm going to store this URL as a Firebase config as well, to hide it from prying eyes.

firebase functions:config:set discord_hook.url="<webhook url>"

Step 7: Draw the rest of the owl

Next, since this is an HTTP requets that needs to be made, I install axios to make it, with npm install axios.

I can add a simple function for sending webhooks to discord:

const axios = require("axios");

function sendWebhook(author, icon, description, title, body, url) {
  const request = {
    "username": "Larbot Gitrold",
    "avatar_url": "<snip>",
    "embeds": [{
      "color": 0xFFC89C,
      "author": {
        "name": author,
        "icon_url": icon,
      },
      "title": description,
      "fields": [{
        "name": title,
        "value": body,
      }],
      "url": url,
    }],
  };

  functions.logger.info("Sending discord webhook", {request});
  return axios.post(functions.config().discord_hook.url, request)
      .then((res) => {
        functions.logger.info("Discord webhook send successful", {res});
      }).catch((err) => {
        functions.logger.error("Discord webhook failed", {err});
      });
}

This function, when invoked, will send an HTTP request to Discord, causing a message to show up in the configured webhooks channel!

Next, I just need to trigger this function from a github webhook.
Octokit/webhooks uses an event system to handle the webhooks, which is actually very convenient, so I'm able to add a handler for specific:

webhooks.on(
    ["pull_request.opened", "pull_request.reopened", "pull_request.closed"],
    ({id, name, payload}) => {
      functions.logger.info("Handling Pull Request", {id, name, payload});
      sendWebhook(
          payload.pull_request.user.login,
          payload.pull_request.user.avatar_url,
          `Pull Request #${payload.pull_request.number} ${payload.action}`,
          payload.pull_request.title,
          payload.pull_request.body,
          payload.pull_request.html_url
      );
    }
);

Here, I'm telling octokit/webhooks that I want to trigger this whenever pull requests are opened, reopened, or closed. I pull out all the relevant user info, avatar URLs, and pull requests details from the incoming github payload, and then trigger the outgoing discord webhook function.

The result looks something like this. I since added pings to a discord role so that certain people will be notified, and a few other goodies.

It's easy to add additional handlers for the different events, by registering more events/handlers with the webhook. here's a comparison between Discord's built-in github webhook handler for closing an issue, which doesn't show the contents of an issue, and this custom one that does:

And that's it! The final code looks like this:

const axios = require("axios");
const functions = require("firebase-functions");
const octokit = require("@octokit/webhooks");

const webhooks = new octokit.Webhooks({
  secret: functions.config().github_webhook.secret,
});

const runtimeOpts = {
  memory: "128MB",
};

exports.githubNotifier = functions.runWith(runtimeOpts)
    .https.onRequest((request, response) => {
      const event = request.headers["x-github-event"];
      const hook = {
        id: request.headers["x-github-delivery"],
        name: event,
        payload: request.rawBody.toString(),
        signature: request.headers["x-hub-signature-256"],
      };

      return webhooks.verifyAndReceive(hook).then(() => {
        response.status(200).send("Webhook handled");
      }).catch((err) => {
        functions.logger.error(err);
        response.status(500).send("Webhook not processed");
      });
    });

function sendWebhook(author, icon, description, title, body, url) {
  const request = {
    "username": "Larbot Gitrold",
    "avatar_url": "<snip>",
    "embeds": [{
      "color": 0xFFC89C,
      "author": {
        "name": author,
        "icon_url": icon,
      },
      "title": description,
      "fields": [{
        "name": title,
        "value": body,
      }],
      "url": url,
    }],
  };

  functions.logger.info("Sending discord webhook", {request});
  return axios.post(functions.config().discord_hook.url, request)
      .then((res) => {
        functions.logger.info("Discord webhook send successful", {res});
      }).catch((err) => {
        functions.logger.error("Discord webhook failed", {err});
      });
}

webhooks.on(
    ["pull_request.opened", "pull_request.reopened", "pull_request.closed"],
    ({id, name, payload}) => {
      functions.logger.info("Handling Pull Request", {id, name, payload});
      sendWebhook(
          payload.pull_request.user.login,
          payload.pull_request.user.avatar_url,
          `Pull Request #${payload.pull_request.number} ${payload.action}`,
          payload.pull_request.title,
          payload.pull_request.body,
          payload.pull_request.html_url
      );
    }
);

PEG Parsers: sometimes more appropriate than Regex

Yuan Gao — Sun, 22 Aug 2021 12:44:06 +0000

Had a quick project recently, that inspired me to write a quick blog post about PEG parsers. Diving right in:

The problem/why I did this

Some friends have a little game project called Loungeware, a wario-ware collection of minigames, with contributions from the GameMaker community.

Its website needs a gallery of the games, and we wanted a way to keep this gallery up to date without someone having to manually go through the contributed games and copying over the metadata.

The data already exists in the repository in the form of code files for the game, so why can't we just process these and pull the data out for the website? That way the website can easily be kept up to date simply by reading the code that's already there! That's the basis of the problem.

How to solve this?

The game is written in GML, a C-syntax dynamic language, it shares some resemblance to Javascript. Here's what we have to extract:

As you can see, this is more or less indistinguishable from Javascript. It's really tempting to just feed this through as javascript, but that would lead to some weird code execution vulnerabilities.

So what are our options? Regex? It's the first thing that comes to mind when faced with some sort of data extraction problem. Can we just Regex this whole thing? I guess we could, but it would result in an incredibly long and complex Regex pattern.

Ok, so to reduce the complexity of a long Regex pattern, maybe we could split the task up into individual parts? Search for each occurance of microgame_register and then take the text after that and feed that through individual Regex patterns to extract each key? This would be better, it would make the Regex patterns more managable, and we can rely on the structure of the code to help us with decoding it.

Ok, so why not take this to the logical extreme? If the code is, at the end of the day, well-structured. What if we defined the rules for how the code should be put together? Let's say we defined rules like "An array starts with [ followed by some number of variables separated by commas and ending with ]"? This. This is exactly what PEG is for.

PEG.js

In past blog posts, where I've written about PEG, I've used Parsimonious in Python, such as three of my solutions to the 2020 Advent Of Code challenges (here, (here)[https://dev.to/meseta/advent-of-code-day-18-finally-using-peg-grammar-in-python-in-the-way-it-s-supposed-to-3253], and (here)[https://dev.to/meseta/advent-of-code-day-19-abusing-peg-grammar-in-python-the-way-it-s-not-supposed-to-2beg]). This time, because the rest of the website is javascript, I will be using PEG.js instead to avoid adding an extra programming language to the codebase.

PEG.js has a distinct advantage over parsimonious in that it has a nice web-based tool to help you write your grammar. I'll be using this online tool to walk you through how I went about writing a PEG grammar needed to process the above GML code into JSON.

Step 1: Whitespace

I like to go from inside->out. Take the smallest and most primitive elements and then build upwards. Since a lot of my data is in the form of numbers. I need to add PEG rules for matching and extracting them. Since unlike parsimonious which lets you use full-on regex for pattern, PEG.js only allows much simpler pattern matches, I'm going to define two rules, one for integers, and one for floats:

Number
  = Float / Integer

Float
  = "-"? ([0-9]+ "." [0-9]* / [0-9]* "." [0-9]+) { return parseFloat(text()); }

Integer
  = "-"? [0-9]+ { return parseInt(text(), 10); }

PEG matches from top down. And the text must match the first rule in its entirety. So at the moment, this PEG grammar will match a single Float or Integer. I use Javascript's handy parseInt() and parseFloat() functions to turn the captured text into an actual Javascript number.

Note: this pattern ([0-9]+ "." [0-9]* / [0-9]* "." [0-9]+) matches .0 and 0. but not .

Step 2: variable names

Some of the values in the data point to specific variables. These are easy to match, since they only allow characters a-z, A-Z, 0-9 and _, the so-called "word" characters.

Word
  = [a-zA-Z0-9_]+ { return text(); }

This is going to return the string of the variable name, which is fine by us because we don't actually need to resolve them for this use-case. If we were actually building a programming language rather than just extracting data, we'd probably at this point need to return an object representing a variable to distinguish it from a string literal. But in our case here, we are okay to treat variables like string literals.

Step 3: Booleans

We have a few booleans in our text. These are simple too, we just need to match true or false and return a javascript boolean

Boolean
  = bool:("true" / "false") { return bool === 'true' }

Step 4: String literals

String literals are much harder because we have to be able to match escaped quotes like this: "hello \"world\"" so we can't just find all the text between two double-quotes. To do this, we have to define a new rule that matches either regular characters, or specifically escaped quotes:

StringLiteral
  = str:("\"" CharDoubleQuoted* "\"") { return str[1].join(""); }

CharDoubleQuoted
  =  "\\\"" / [^"]

the str[1] is needed because we want to return the string without the quotes. and the .join("") is needed because it'll return an array of characters.

We actually have to duplicate this to support both double and single quoted characters. so the rules end up looking like this:

StringLiteral
  = str:("\"" CharDoubleQuoted* "\"" / "'" CharSingleQuoted* "'") { return str[1].join(""); }

CharDoubleQuoted
  =  "\\\"" / [^"]

CharSingleQuoted
  =  "\\'" / [^']

Step 5: Putting them together

So a value could be any one of the above rules. We can define now a rule that says "a Value can be any of these"

Value
  = Boolean / StringLiteral / Number / Word

StringLiteral
  = str:("\"" CharDoubleQuoted* "\"" / "'" CharSingleQuoted* "'") { return str[1].join(""); }

CharDoubleQuoted
  =  "\\\"" / [^"]

CharSingleQuoted
  =  "\\'" / [^']

Boolean
  = bool:("true" / "false") { return bool === 'true' }

Word
  = [a-zA-Z0-9_]+ { return text(); }

Number
  = Float / Integer

Float
  = "-"? [0-9]* "." [0-9]* { return parseFloat(text()); }

Integer
  = "-"? [0-9]+ { return parseInt(text(), 10); }

This PEG doesn't do anything particularly interesting. It'll convert numbers into actual numbers (rather than just strings of unmbers), bools into bools, correctly capture escaped strings, and turns variables into string literals. But nevertheless, we needed all this as the building blocks.

Step 6: Arrays

An array is simply any number of the above Value, surrounded by square brackets, and separated with commas. Oh, and there's a bunch of extra whitespace.

Array
  = "[" _ items:(Value _ "," _)* last:(Value) _ "]" {
      return items.map(v => v[0]).concat([last]);
    }

_ "whitespace"
  = [ \t\n\r]*

Unfortunately it's a bit harder to handle due to the fact that there's a comma after each value except for the last one. If we wrote just (Value ",")* then each value, including the last one would need a comma after it (e.g. [1,2,3,]. So we have to handle that edge-case separately with (Value ",")* Value. Incidentally, a rule like this doesn't match empty arrays, but I'm going to ignore that for now.

We can also add "Array" to our "Value" pattern to allow for nested arrays! At this point, our PEG pattern can match string, number, and boolean literals, variable names, and arrays that are made up of these things.

Step 7: Structs

In GML, Structs are a lot like javascript object notation. or Key:Value pairs surrounded by curly brackets, and separated with commas.

Struct
  = "{" _ items:(Item _ "," _)* last:(Item) _ "}" {
      return Object.fromEntries(items.map(v => v[0]).concat([last]));
    }

Item
  = key:Word _ ":" _ value:Value { return [key, value] }

Here, I'm having the Item match key:value pairs, and return an array, which Struct can turn into an Object using .fromEntries() method.

Adding this to our "Value" pattern now allows nested structs too!

Step 8: Game registration

So, we could keep going and define all the language features like function calls and algebraic expressions. But in our case here we don't need to because these files should only contain struct literals and value literals. So we're going to take a shortcut and make a rule for specifically the microgame_register() function:

Registration
  = _ "microgame_register(" _ name:StringLiteral _ "," _ config:Struct _ ")" _ ";"? _ {
      return {name: name, config: config} ;
    }

Since we did all the groundwork, that's all it takes! We know that the first argument is always a string literal, and we know the second argument is always a Struct, so we just say so.

As can be seen in the screenshot, our PEG parser is now able to parse a single invocation of microgame_register() and spit out the name and config struct as a Javascript object.

Step 9: Multiple registrations per file

The final step is that a single fine can contain multiple registrations, so all we need is a new top-level rule. The first rule in the PEG file is important, as this rule must match the whole input, so it's something of a "parent".

All
  = reg:Registration* { return reg; }

And that's it! This now lets us handle multiple "Registration" in a file.

In its entirety, the PEG grammar is:

All
  = reg:Registration* { return reg; }

Registration
  = _ "microgame_register(" _ name:StringLiteral _ "," _ config:Struct _ ")" _ ";"? _ {
        return {name: name, config: config} ;
    }

Value
  = Struct / Array /Boolean / StringLiteral / Number / Word

Struct
  = "{" _ items:(Item _ "," _)* last:(Item) _ "}" {
      return Object.fromEntries(items.map(v => v[0]).concat([last]));
    }

Item
  = key:Word _ ":" _ value:Value { return [key, value] }

Array
  = "[" _ items:(Value _ "," _)* last:(Value) _ "]" {
      return items.map(v => v[0]).concat([last]);
    }

StringLiteral
  = str:("\"" CharDoubleQuoted* "\"" / "'" CharSingleQuoted* "'") { return str[1].join(""); }

CharDoubleQuoted
  =  "\\\"" / [^"]

CharSingleQuoted
  =  "\\'" / [^']

Boolean
  = bool:("true" / "false") { return bool === 'true' }

Word
  = [a-zA-Z0-9_]+ { return text(); }

Number
  = Float / Integer

Float
  = "-"? [0-9]* "." [0-9]* { return parseFloat(text()); }

Integer
  = "-"? [0-9]+ { return parseInt(text(), 10); }

_ "whitespace"
  = [ \t\n\r]*

A set of easy-to-explain rules can come together to extract the structure of the GML code, and produce a Javascript object containing the data we want.

I hope this has been helpful in explaining a little about the process you can take to write your own PEG grammar to parse whatever it is that you needed to parse, and how PEG grammars may be an alternative to an unwieldy regex pattern.

As a rule of thumb, I suggest thinking like this: if the document you are matching has a lot of structure, like a programming language, or a data format, then PEG grammars are more appropriate and a lot more flexible than Regex, since you can make use of this structure to help you match the data. Good luck!

Cover Photo by Quaritsch Photography on Unsplash

LGTM Devlog 39: Planning the story

Yuan Gao — Thu, 11 Feb 2021 11:31:10 +0000

Planning out the writing, I would like this chapter to contain a main quest arc, a few short side-quests, and possibly a collection of unrelated side-quests. So Here's what I have so far:

Six main characters, six side-characters, a main quest arc, character exposition quests, side-quests.

The plan will be to lay out the key points for each of these, before diving into each in detail and writing out the dialogue for them, and implementing any remaining features needed in Python.

LGTM Devlog 38: Sprint 5 Plan

Yuan Gao — Tue, 09 Feb 2021 10:59:09 +0000

Sprint 5 is content, content, content! With enough framework in place to produce simple quests, my aim for Sprint 5 is get fully underway with content generation. So I'm not even putting together tickets for this one.

Faye @JavaScriptCoff1 has also offered to help with the writing, so hopefully we can put together a killer story.

GitHub storytelling

The ultimate aim of LGTM is to teach git and GitHub, but there are also plenty of good resources and tutorials that do this already, why is LGTM different? My feeling is that a lot of those existing tutorials are hard to relate to and very dry and theoretical. Fine if you know what you want from git and just need the technical details, but lacks the emotional investment in it for those who don't fully know what they want. And that makes it difficult to learn or stick with a course.

Therefore I feel LGTM should contain a fictional narrative to engage the audience while they do tasks on git. This also meshes with my desire as a hobbyist gamedev, to tell a story (the whole reason. So now I have to consider...what story do I tell?

There's a few technical limitations to consider: git and GitHub's comment system allows for a type of story-telling in the form of character dialogue: a character can speak to you, the player, or to each other over the comments system. But I don't want the player to have to imagine themselves "in-world", where similar interactive fiction games has the player imagine themselves as a character inside a world, exploring it, and directly having a conversation with other characters. I want the player to play as themselves, sitting in front of a computer, having a chat over GitHub about git-related tasks, that happen to have a backstory in the game's lore.

There's also unlikely to be a place to send too many images, or any non-dialogue narration, as that would run against how git/GitHubare used normally. But, what I can do is have "found journal" storytelling, where I can leave small amounts of text and world-building in the form of journals that someone might store in their git repo for the players to find.

Setting

When it comes to world setting, I think it may become too contrived to fit using git into the lore of a high-fantasy world, and may require too much investment from the player to explore this world. I want to keep the game setting and the tasks the player is involved in to one in which it is believable that git would be used, as fundamentally we must teach git, and teach git in a way that allows the player to relate what they're doing to similar real-world tasks.

This means the setting would be relatively contemporary, on Earth, and in a situation where computers and git could be used, though we have some leeway in what kind of information is on git - perhaps notes and to-do lists, though not the typical thing you'd find on git, isn't too much of a stretch of the imagination.

The Plot

My initial thoughts for driving the plot is some kind of peril (global? local?) it's tried and tested, and also the approach that Uplink took, a game that I draw a lot of inspiration from. The player starts out helping out these characters with various git tasks, and then gets pulled into a larger plot. Although I did write code for branching storyline, I think it's best if the player can't pick sides (makes it easier to write), and instead works together with the characters to prevent some global/local catastrophe.

I think perhaps the emphasis should be more on the characters, and less on the plot that's happening in the background, since the game being heavily dialogue-based, it'll be easier to write about the characters responding to the events of the plot rather than than writing about those events directly, so maybe it's easier for players to engage with the characters than the events.

Chapters

Since I currently only have the game mechanics for Type 1 quests, and not yet Type 2 or 3, I think what I could do is write a Chapter 1 of the story which is still self-contained enough, but open-ended for future chapters. That way I can aim to release Chapter 1 of LGTM sooner, rather than have to wait to implement and write out the whole thing.

Example

Here's an example of possibly the first quest. I've blanked out the player input. Here I'm testing what happens when you give the wrong value - the characters have a set of randomized responses for when you get answers wrong.

This sprint, the task will be to lay out the skeleton of this writing, something I'm not familiar with, so I won't be setting tasks for the sprint other than "figure out how to start writing". Though I may do a bit of code tidyup. Expect there to be fewer devlog updates during this sprint.