Projects
-
Works In Progress: Generating a Maze in Python
Last year I was messing around with maze generation. I thought I was going to make another game (more on that later). I didn’t get very far, but I did learn how to use the recursive backtracking algorithm to create a 2D maze. I was thinking about that algorithm again during Advent of Code, as many of the problems turn out to be maze/traversal problems, and, well, I’ve been meaning to write this up anyway. It’s not really a complete project, but I found it interesting, and maybe you will as well?
There are a lot of maze algorithms out there. The recursive backtracking one is one of the easiest, I’m told.
The general gist: Start with a grid of possible spaces. Choose one to start, and “knock down” the wall between it and a random neighbor. Choose another direction at random, and if it has not yet been visited, knock down the wall there. Once all locations at a given square have been visited, backtrack; once the algorithm reaches the starting point the maze is complete.
Implementing it in Python looks like this:
DX={"N":0,"S":0,"E":1,"W":-1} DY={"N":-1,"S":1,"E":0,"W":0} class Maze(): def __init__(self, size, seed="default"): #init the maze self.size = size self.game_map=np.zeros(shape=(self.size,self.size),dtype=object) for y,row in enumerate(self.game_map): for x, square in enumerate(row): self.game_map[y][x] = Room(x, y) #this is not strictly necessary, I wanted my maze Room class to have some other features that I will discuss later start_x = random.randint(0,self.size-1) start_y = random.randint(0,self.size-1) self.make_the_maze(start_x,start_y) def make_the_maze(x,y): current_room=self.get_room(x,y) #returns an instance of the Room class with these xy coordinates current_room.visited=True directions = ["N","S","E","W"] random.shuffle(directions) for direction in directions: new_x = x+DX[direction] new_y = y+DY[direction] if (0<=new_y and new_y<self.size) and (0<=new_x and new_x<self.size) and not self.get_room(new_x,new_y).visited: #recurse self.make_the_maze(new_x,new_y) maze = Maze(3)This allows us to declare a square maze of length and width
nand create a maze where all squares are visited at least once and with one entry and exit. This implementation doesn’t really do anything, though – ideally we would be, oh, counting the number of valid, unique paths from point A to point B, for example. Or rendering it on a screen.
What I wanted to do with this maze, though, is turn it into a text adventure. By saving each room’s doors (e.g.
doors: {'N':True,'S':False}etc…) I can use that to generate an Inky file:#still in the Maze class def render_text(self, start_x, start_y): with open("game.ink","w+") as inkfile: inkfile.write("You are about to enter the spooky maze!\n") inkfile.write(f"+[Go in] -> room_{start_x}_{start_y}\n") for room in self.get_all_rooms(): self.write_room(inkfile, room) def write_room(self, inkfile, room): x = room.x y = room.y inkfile.write(f"===room_{x}_{y}===\n") if room.is_finish: inkfile.write("You have found the exit and/or the amazing treasure!->END") else: inkfile.write("You are standing in a maze of twisty passages, all alike.\n") doors = room.get_doors() exits = [direction for direction in doors if doors[direction]] if len(exits)>1: inkfile.write(f"There are exits to the {','.join(exits)}\n") else: inkfile.write(f"There is an exit to the {exits[0]}.\n") for door in exits: new_x = x+DX[door] new_y = y+DY[door] inkfile.write(f"+[Go {door}] -> room_{new_x}_{new_y}\n")An
.inkfile is used by the Inky editor to create narrative adventures. The Inky editor uses a Markdown-ish syntax to create choose-your-own-adventure style games.I had this idea that I could make a procedurally-generated choose-your-own-adventure (with more interesting narration than the “maze of twisty passages” stuff, of course) and then, using the same seed, create a visual representation of the same maze, that two players would solve together. The
Roomclass would be essential for this and would contain things like: does this room contain a locked door, or a key, or a monster, or a landmark? I haven’t gotten around to implementing it yet but you get the general idea.So, it’s pretty bare-bones and doesn’t do anything yet, but to my knowledge (and upheld by a very quick Google–please reach out if I missed you) this is one of the earliest examples of procedurally generated Inky games. I hope to have some time to get back to this eventually, but *waves hands* life has been getting in the way. For now, I’m happy to have had a chance to learn a maze algo.
Resources
I am indebted to Jamis Buck’s ‘Buckblog’ post on maze generation; his writeup in Ruby was the only thing that helped me make sense of doing the same in Python. It should be noted that he has an entire book about mazes that I am probably going to be buying shortly.
-
Building My Blogging Habit, With Toys
I would like to be writing more, and most self-help books about productivity say the same thing: If you’d like to encourage a good habit, you need to remove friction. To that end I’m trying out a few portable Bluetooth keyboards, under the idea that if it is easier to type on my phone on the go, I will type more on my phone on the go.
The Arteck that I borrowed from my husband is just okay. I am typing on it right now, and it wobbles a little on my lap, and makes quite a ruckus as I bang away on the keys. It is also a little on the large side for stowing in a purse, although it’s light as a feather and so would be easy to toss in a larger bag. I have high hopes for the Plugable folding keyboard, which Redditors recommend, and which I grabbed on eBay (but has not yet arrived).
Either way, one of these should make it easier to at least draft thoughts. I’m sure I’ll publish them from a laptop.
Now to find out if I have anything to say…
-
The Wrong Reason (and the Right One) to Blog
I wish I looked this relaxed when I worked on this blog. Photo by Vardan Papikyan on UnsplashYou should keep a blog.
Yes, you. You introverted developer.
A blog helps you learn in public.
The concept of learning in public is often discussed in tech circles (and rarely, in my experience, outside of tech circles). Popularized by Shawn Wang in 2018, the term basically boils down to: document your learnings.
Doesn’t matter if you document through a blog, podcast, Twitch stream, newsletter, Github gist, whatever – the recommendation is just to do it where people can see. (So for the rest of this post, when I say ‘blog’, feel free to substitute your content type of choice – although I personally find blogging the easiest type of content to create, especially compared to a podcast or video, I realize that is not true for everyone.)
Why should you do this? I’ll tell you why you shouldn’t blog, first, then tell you why you should.
Why you should not blog
You shouldn’t blog because you think you might become a thought leader. Some folks read Learn in Public and decided that they would build a multi-million dollar brand.
Start blogging, the logic goes, and people will notice you and start helping you, because it’s rewarding to watch someone grow in public. You build your brand, because you’re ‘out there’, and eventually people will pay you for your thoughts/opinions/expertise, because you now have a public brand and have established yourself as an expert. Then you will suddenly make a million bucks a year. It’s easy. 🙄🙄🙄
“But I don’t want to become a content creator!” Me neither, buddy.
“But I don’t care about fame and fortune!” I don’t 100% believe you, but it doesn’t matter, because you’re not keeping a blog to become famous.
The reality is, 99% of people who start learning in public are not going to grow a brand that does anything. They are not going to quit their day jobs to become full time content creators.
If you start a blog and this happens to you, please come back and tell me. But for most of us, this is not going to happen. And that’s okay, because that isn’t why you should have a blog. There is a much more important, realistic reason to keep blogging.
-
Advent of Code Day 14: That Won't Work
I guess finding the answer to part 2 manually is not going to work.
Imagine this GIF goes up to iteration 4999….
-
Composing Functions in Python
Beethoven did not compose any functions, that I know of.I have not done a lot of functional programming, although someone I used to volunteer with was very into it. This weekend, while attempting to solve Advent of Code, I came back across some functional techniques.
I probably should have solved the day’s puzzle (a variation on the missing operators puzzle) with these tools. (Did I? Reader, I did not - I concatenated a giant string and then
eval()ed it. I am a massive hack.) But let’s talk about composing functions, because I think it’ll be useful someday.What does it mean to compose a function?
Composing functions does not have anything to do with writing music. It simply means to create a function that returns another function as its result. (I have also heard this described as a higher-order function.)
So if you have:
def square(x): return x*x def add_one(x): return x+1The normal way of invoking both of these functions might be:
x=2 x=square(x) #x is now 4 x=add_one(x) #x is now 5But using composability, we could:
def compose(*fns): return functools.reduce(lambda func1, func2: lambda x: (func2(func1(x))), fns) square_and_add_one=compose(square,add_one) square_and_add_one(2) #result is 5If this looks like witchcraft to you, it also did to me at first. Let’s break down what’s going on in
compose.composetakes one parameter,fns, which is prefixed by the splat operator, which means we unpack each item passed to it into a list. (Similar-ish to...spreadsyntax in Javascript). Then we use thereducefunction on the list.I’m much more familiar with a reducer from math operations. For example, if you have
[1,2,3,4,5]and want to know the product of 1*2*3*4*5, you can write:nums=[1,2,3,4,5] result = functools.reduce(lambda acc, num: num*acc, nums)Or in other words, for every item in
nums, multiply it by the accumulated (reduced) result.1*2=2 2*3=6 6*4=24 24*5=120Our
composereducer does the same thing, but instead of performing a multiply operation, it returns a new function whose function is to call the previous function.So if we do
square_and_add_one=compose(square,add_one)the result is a function that first squares its input, then adds one to it. It would be the equivalent of:add_one(square(x))Cool. Why do we care?
I initially thought I could solve the Advent of Code puzzle by composing functions. As I said, the puzzle was essentially the following:
Given the numbers (for example) 81, 40, and 27, what combination of multiplication and addition will create the desired total, in this case 3267?
With three numbers and only two possible operators, this is easy enough to brute force by hand, but of course the real challenge has 10+ digits in each line. I was hoping that I could get every combination of length n of the two operators (e.g.
"+,+,+,+,+,+,+,+,+,+","+,*,+,+,+,+,+,+,+,+", and so on) and toss those into a compose, and see what popped out.This did not work for a number of reasons. One, because if you want your composed functions to take more than one parameter, you have to do some fancy work.
Two, and this is more important, I don’t actually want to do
add(multiply(81,40,27)). What I want isadd(multiply(add(81,40),27))and that subtle distinction is actually quite a big difference. I won’t say there isn’t a way to get that result with composing functions, because there is almost certainly a way to do everything, every way, in code. But by that point I’d been hacking away at the problem for a bit and I decided to just make a silly naive solution.I also think that unless you’re very careful, composing functions can lead to abstractions that are hard to read and debug, as cool as they look.
I am not sure I will be making heavy use of this technique in my own work but I’m glad to have messed around with it, if only to recognize this pattern when I see it in the wild.