cd
and ls
, allowing me to practice throughout my entire day, little by little!
With a little bit of vim trickery on my .zsh_history
file, I noticed that I was averaging over 100 commands a day in my terminal. A little more massaging and I saw that most of these commands were in the set $\{\text{ls},\text{cd},\text{git},\text{python},\text{make}\}$. Hmm I thought. I could alias each CMD
to something like alias CMD="./precmd_program; CMD"
to run some code before they executed. I could make a study program, and this would allow me to spread my studying thinly over the course of many hours. I wouldn't even feel like I was studying, ideally.
I wrote a short node.js
script that does the following: 80% of the time, it does nothing. 20% of the time (this is a parameter of course), it prints out "How do you say __ in Portuguese?" and waits until you type in an answer. It keeps asking you questions until you answer $n$ correctly, at which point the original command is allowed to run.
You wouldn't want this pre-command script to run on every command because it would seriously interrupt your work flow. But if you instead ask many questions ($n$) at a time less frequently, amortized, you're studying the same amount, but you're much less annoyed at the interruptions.
This script reads from a CSV-esque file of the following form: question,answer,# correct answers,# wrong answers
. For Portuguese vocabulary, this looks something like:
goodbye,tchau,0,0
yes,sim,0,0
your,seu,0,0
who,quem,0,0
good afternoon,boa tarde,1,0
You first write down all your question/answer pairs (omitting the numbers, they'll default to 0,0
automatically), one pair per line. Then, as the script asks you questions, it keeps track of how many times you're missing each question. It quizzes you on questions with low correct/incorrect
ratios more frequently than questions with high ratios. Stated differently, it asks you the questions you struggle with more frequently than those you find easy.
For the full source code of this script and some example aliases in a .zshrc
/.bash_profile
/etc, check out this gist.
Yeah so some math came up as I was implementing this (as math tends to do). Specifically, given an array of questions sorted by their correct/incorrect
ratio, how can I randomly select a question, such that the question with the highest ratio is selected $f$ times less frequently than the question with the lowest ratio?
For simplicity, I can map each question to $[0,1)$ by dividing each question index by the number of questions, and I can arbitrarily decide that my PDF, $PDF(x)$, over this interval will be linear. If the intercept is at $(0,y_{max})$, then $PDF(1)=y_{max}/f$ by definition.
Since this is a probability distribution function, we know that the integral from $0$ to $1$ must be $1$, which contrains the value of $y_{max}$. Using this, we can write a formula for our PDF and integrate it to find the CDF, which in this case will be a quadratic function.
Finally, we can take the inverse $CDF^{-1}(x)$ and use inverse transform sampling to sample according to $PDF(x)$. Then, we convert our result, which will be in the range $0$ to $1$, back into a question index and return the corresponding question.
This was a fun quick project that will hopefully help me learn Portuguese a lot more easily. I think of this script as forcing me to have brief flash-card study sessions every few minutes. I'd love to hear your thoughts if you try this out and like/dislike it!
Also, just to give a sense of what else you could use this for, it doesn't just need to be used for questions; another idea I had was to print out one sentence of a book with every terminal command you ran. A lot of people say they "don't have time to read", but with something like this, there's no excuse (effectiveness yet to be tested). Até a próxima vez!
]]>You can find the files here: https://github.com/turbomaze/word2vecjson/tree/master/data
First, I downloaded a 1.6 GB .bin
containing word vectors for nearly 3 million words. Then, I wrote a Java program that loaded frequency information for around 150,000 English words. Given an input of $n$, that program would read through the large .bin
file and output the word vectors for the $n$ most common English words in JSON. I ran the program for various values of $n$ — 1000, 5000, 10000, and 25000 — and uploaded the results.
You can play around with word vectors in your browser here: http://turbomaze.github.io/word2vecjson/
You can do things like "berlin" + ("france" - "paris")
and get logical answers, like "germany"
. The difference of two word vectors is a relationship that often applies to other word vectors. "france" - "paris"
is the country to capital city relationship.
For more info about word vectors you can check out the project here: https://code.google.com/p/word2vec/.
]]>Tic tac toe is a two-dimensional game because you play it on a piece of paper. A line of $x$'s or $o$'s on the paper is a win. In three dimensions, you're still trying to form lines, but there are significantly more ways to win because you're playing in a cube and not on a flat sheet.
If you're having trouble visualizing this, take out a $3\times 3\times 3$ Rubik's cube. Instead of writing $x$'s and $o$'s with a pen, you're putting an $x$ or an $o$ inside of a Rubik's cube piece -- either a center, an edge, or a corner. Three-dimensional tic tac toe has one additonal spot, though: the very middle of the cube, hidden from the outside.
There are a whole bunch of different ways to win in this version. You could look at each slice of the cube as a standard $3\times 3$ board and win in the normal ways, or you could form lines that span multiple slices. For instance, three in a row down the central column, or three in a row from corner to corner through the middle.
If you want to play in three dimensions on a sheet of paper, all you need to do is draw three standard tic tac toe boards on top of one another. Each board represents a layer of the cube, and the winning lines are the same. Players take turns writing in $x$'s and $o$'s in the squares just like in the normal version of the game.
Please have a clear sense of why the above two lines are winning arrangements. It's going to get a lot more confusing later on...
Playing on paper is perfectly fine, but I recommend trying to play in your head with a friend! Yup, with your eyes closed, visualizing the tic tac toe cube in your mind. This isn't too strange of an idea. After all, some people can play chess in their heads, and chess is a lot more complicated. To play blindfold chess, participants take turns stating their moves in an agreed upon format (like algebraic chess notation). "Blindfold" 3D tic tac toe works in the same way.
Whereas in chess there are a bunch of different piece types, in tic tac toe, all that matters is the location of an $x$ or an $o$. You could assign each three-dimensional grid space a letter of the alphabet so long as you and your friend are consistent, but the most general, extensible method is to use coordinates.
In the above image, there's a yellow axis, a cyan axis, and a magenta axis ($\color{goldenrod} x$, $\color{turquoise} y$, and $\color{magenta} z$ respectively). The axes intersect at $(\color{goldenrod} 0,\color{turquoise} 0,\color{magenta} 0)$, which is the location of the bottom-left-most grid space and the red sphere. Each grid space is $1$ unit further away, so for a $3\times 3\times 3$ cube, the coordinates range from $0$ to $2$. Take a moment to determine the coordinates of the blue sphere under this system. It's .
To play, take turns stating coordinates with another person. Keep track of all of the coordinates that have been said so far, imagining the cube and the pieces within it in your head. With a bit of practice, playing mentally becomes a piece of cake. It's a great way to improve your spatial reasoning and visualization skills, and it'll enable you play 3D tic tac toe wherever you are.
Okay. Now for the fun part! We're going to add yet another dimension! Four-dimensional tic tac toe. I feel like another t-- word is in order. Tic tac toe toc maybe? One per dimension?
It's essential at this point that you are totally comfortable with tic tac toe in three dimensions, including playing it mentally. For the 3D version, I explained the game visually with figure 1 before explaining how to play it in your head. For four dimensions however, it's best to start with the mental version because at this point we're really stretching the capabilities of our 2D computer screens. If you're already comfortable thinking in 4D, skip to the game. Otherwise, read on.
Figures 1 and 3 may appear clearly three-dimensional, but they're just flat projections. We perceive 3D objects through 2D mediums all the time (literally all the time; our eyes can't see 3D), so we don't have a problem doing this, but projecting four dimensions down to two is a huge challenge.
A spatial dimension is a line you can move along. Think: left and right, front and back. Multiple lines means multiple dimensions, but only if those lines are mutually perpendicular. A piece of paper is two-dimensional because if you only have one line, there are regions of the paper you'll never be able to reach. Adding a second line perpendicular to the first gives you the freedom to move not just left and right but also up and down. Two lines encompass the entire sheet. Two dimensions.
But two lines aren't enough to move around a cube; we would always be stuck on the bottom layer. We need a third line, bringing us to three dimensions total. If we wanted to state the location of a point in this cube, we would need to say how far we moved along each line. Three lines, three coordinates, three dimensions.
Extending this idea to four dimensions would be easy if not for the requirement that these lines be mutually perpendicular. In fact, it's impossible for four lines to be mutually perpendicular in three dimensions. So in your head, do not try and visualize a fourth axis! Instead, focus on the idea of movement.
When we move along a single dimension, our position in every other dimension remains constant. If you move left or right on a sheet of paper, you don't change how far up or down you are, for instance. So when we move through the fourth dimension, we actually stay right where we are in the first three.
Let's pretend I'm a four-dimensional creature and you're your normal 3D self. You're in your room, which remains constant in the fourth dimension. I proceed to hover a glowing, 3D green cube right in front of your face, and I place a red cube in the same spot further along in the fourth dimension. Remember: you're 3D, so you can't see the red cube.
At this point, I use my alien tendrils to give you a nudge in the fourth dimension. Suddenly, the green cube pops out of existence. There's no warning -- no smooth fade to nothingness and no shrinkage. It just disappears. Why? Because it was 3D and its coordinates took the form $(x_g, y_g, z_g, w_g)$, where $_g$ signifies that these coordinates are for the green cube. Initially, your position in the fourth dimension -- the $w$ dimension -- matched that of the cube, so you could see it. But the second my slimy alien fingers gave you that push, you moved through the fourth dimension to $w_g+\Delta w$. Your 3D coordinates are exactly the same, but since your $w$ coordinate changed, the cube is no longer in your line of sight. You're 3D.
Eventually, you drift to $w_r$, where I stop you. Now, there's a red cube in front of you, and it popped into existence out of nowhere. At no point in this journey did you leave your room. All that appeared to change was the color of the cube in front of you. Imagine me pushing you back and forth between the two; your body feels the acceleration of my push, and you alternatingly see the green and red cubes.
Those cubes were 3D, which means they only existed in particular slices of the fourth dimension, just as a sheet of paper appears to have no depth in three dimensions. But now I'm going to use my alien tehnology to generate a 4D cube, a tesseract, in front of you. What color tesseract? An infinitely colored, rainbow one! Sort of like this:
This cube's color depends on where you're looking along the left-right axis. The far left is yellow, and the far right is red. Pretend this were a stack of post it notes. The first note is bright yellow and the note at the very bottom is red. Imagine flipping through the notes; each individual post it is a solid color, but flipping through them quickly yields a smooth gradient.
You're back in your room, still your 3D self, but this time you're faced with a red cube initially. If I didn't already tell you this were a tesseract, you would have no idea there was something special about this cube. That is, until the 4D push.
Since this cube does exist in four dimensions, it doesn't disappear when your $w$ coordinate changes. The cube stays in precisely the same spot as you move along the $w$ axis, but it changes color, first red, then orange, then yellow and green and blue and violet. I did say it was a rainbow tesseract, after all.
Think back to the post it note example. We flipped through two-dimensional slices -- pieces of paper -- along the third dimension and saw a smooth transition from yellow to red. This time, we're moving along the fourth dimension and seeing a 3D object change color. It's important that you're making an effort to see this in your mind's eye and not just reading.
I continue pushing you, but once you pass blue and violet, the cube disappears. What happened? This was a finite tesseract, so it's possible to move beyond it in the fourth dimension. At that point, it would be behind you and thus not visible. If I pushed you in the other direction, you would see violet, blue, ... , orange, red and then nothing. The tesseract would be "in front" of you in the fourth dimension and again, not visible. Normally, you can see things that are in front of you, but you can't see "forward" in the $w$ direction with your normal, human eyes. Therefore, the cube blips out into the unknown.
And now for the final step! Using advanced alien technology, I upload your consciousness into a four-dimensional body complete with eyes that can see along $x$, $y$, $z$, and $w$. Let's examine how this changes your perception of the green-red example.
Consider what's it's like to look at objects along a dimension. If you had a dozen identical cars lined up along a straight road, the cars that were further away would appear smaller than the cars right in front of you.
Here's the glowing green and red cubes I placed in front of you earlier, but this time, there isn't any four-dimensional monkey business. There are just two cubes, one near and one far. Internalize the fact that the further away an object is, the smaller it appears.
If you're next to a race car just as it's about it zoom straight ahead, away from you, it would begin large and then get smaller and smaller as it moved down the track.
Now consider a race car traveling along a hundred mile straight track in the $w$ dimension. It's only moving along the fourth dimension, so its 3D position shouldn't change. Even though it'll zoom away from you, its wheels will always be right in front of your feet.
What then do you see? Well, we know that the farther away an object is, the smaller it appears, and it doesn't matter if I'm a hundred miles in front of you, a hundred miles above you, or a hundred miles away along $w$; regardless of the direction, far is far. So as this special race car zooms onwards, it will appear to shrink right in front of your eyes. Imagine that!
Back to the cube example. You're in your room. In front of you is a glowing green cube, and in the same exact 3D spot further in the fourth dimension is a red cube. What do you see with your new 4D eyes? Seriously, try and figure it out.
You see a small red cube inside of a large green cube. The red cube is further away after all, so the rules of perspective say it should appear smaller.
The cubes aren't actually transparent, but just as humans' 3D eyes enable them to see 2D surfaces, our alien 4D eyes let us see in legitimate 3D. That is to say, we can see inside of solid 3D objects. We can see the 3D red cube inside the 3D green cube even though they're both opaque.
You are now armed with the necessary intuition to extend tic tac toe into 4D. First, picture an empty 3D grid as you normally would. Then, picture another in the exact same spot, just slightly smaller. Finally, imagine one more, even smaller. Can you do it? (Why did we stop at three grids? Think for a moment if you don't already know.)
If you can visualize that, mad props, but for me, that's just way too crowded. We haven't even placed any pieces yet! Instead, I recommend playing mental 4D in the same way that we played on-paper 3D. We stacked three ordinary two-dimensional grids and just thought extra hard about how the different slices related to one another. For 4D, picture three 3D grids side by side, left to right. Isn't that so much easier?
As far as coordinates go, you just need to make one minor change. Add a $\color{yellowgreen} w$ coordinate that designates which of the three 3D grids each piece goes into. Let $\color{yellowgreen} {w=0}$ signify the leftmost grid and $\color{yellowgreen} {w=2}$ the rightmost.
You now know how to plot 4D coordinates in a modified 4D grid, and you know what that grid would actually look like in four dimensions. The final step is learning to identify winning lines in 4D. As we saw with 2D → 3D, all the lower dimensional winning lines remain, but we have a bunch of extra options available to us. I'm only going to explain lines that extend across the fourth dimension, which means there will be one piece per 3D grid (per "slice").
The top-left-front corner of each slice, corresponding to $(\color{goldenrod} 0,\color{turquoise} 2,\color{magenta} 0,\color{yellowgreen} 0)$, $(\color{goldenrod} 0,\color{turquoise} 2,\color{magenta} 0,\color{yellowgreen} 1)$, and $(\color{goldenrod} 0,\color{turquoise} 2,\color{magenta} 0,\color{yellowgreen} 2)$? That's a winning line. It's difficult, but visualize these pieces in 4D perspective. The larger the $w$ coordinate, the smaller the piece would be and the closer it would be to the center. They would form a literal line of pieces in the top-left-front-ish corner. The line would point to the exact center of the 4D grid.
What about $(\color{goldenrod} 0,\color{turquoise} 1,\color{magenta} 2,\color{yellowgreen} 0)$, $(\color{goldenrod} 1,\color{turquoise} 1,\color{magenta} 1,\color{yellowgreen} 1)$, and $(\color{goldenrod} 2,\color{turquoise} 1,\color{magenta} 0,\color{yellowgreen} 2)$? Take as much time as you need to plot each of these coordinates in the modified 4D grid. Then try and view it in 4D perspective. It's also a winning combination.
And now for the coolest way to win, one of the many long diagonals: $(\color{goldenrod} 2,\color{turquoise} 0,\color{magenta} 2,\color{yellowgreen} 0)$, $(\color{goldenrod} 1,\color{turquoise} 1,\color{magenta} 1,\color{yellowgreen} 1)$, and $(\color{goldenrod} 0,\color{turquoise} 2,\color{magenta} 0,\color{yellowgreen} 2)$. Make sure you see the line before moving on.
The game below requires WebGL. If it doesn't work, upgrade to a modern browser like Chrome. Left click and drag to rotate. Scroll to zoom in and out. To move around, right click and drag or ←↑→↓. Enter piece coordinates in the color-coded form below.
Unfortunately, there's a strategy that allows the player who goes first to guarantee a win in $3\times 3\times 3$. I'm not going to tell you what it is because I had fun figuring it out, but you should know that if you want to have fair 3D and 4D games with your friends, you need to prohibit $(1,1,1)$ in 3D and and $(1,1,1,w)$, $(x,1,1,1)$, $(1,y,1,1)$, and $(1,1,z,1)$ in 4D on the first move.
Alternatively (this is what I did with my friends), you can increase the size of the grid and graduate to $4\times 4\times 4$ and $4\times 4\times 4\times 4$ games. If you've followed along this far, you should have no problem figuring out what that entails.
When I first started playing 3D tic tac toe, the first thing I wondered was how many ways there were to win. There are $8$ ways to win in normal tic tac toe, and counting those ways is straightforward. But in three dimensions, counting is a whole lot harder.
Where $D$ is the number of dimensions and $S$ is the size of the grid, $2$ and $3$ in standard tic tac toe respectively, the following table summarizes the number of winning arrangements:
D=2 | D=3 | D=4 | D=5 | |
---|---|---|---|---|
S=2 | 6 | 28 | 120 | 496 |
S=3 | 8 | 49 | 272 | 1441 |
S=4 | 10 | 76 | 520 | 3376 |
S=5 | 12 | 109 | 888 | 6841 |
There are more than $30$ times the number of ways to win in four-dimensional $3\times 3\times 3\times 3$ than there are in ordinary tic tac toe. As someone who has played many 4D games, believe me when I say that this difference is what makes 4D so interesting. You're always on the lookout for sneaky lines, and there are far too many to just scan the grid procedurally. (Note: lots of math up ahead)
In order to count the total number of ways to win, we need to look at the various types of winning lines. In normal tic tac toe, I claim that there are just two: 1) diagonals and 2) horizontals and verticals. Yes, horizontal and verical lines are in the same category. Do you see the distinction? Draw a picture and try to figure out the key difference.
Hint: it has to do with dimensionality.
Lines are one-dimensional by definition, but they can span more than one dimension if they're rotated relative to the coordinate system. Horizontal tic tac toe lines only take up space in one dimension, the left-right dimension (up-down for vertical lines). Diagonal lines in contrast move both left-right and up-down.
Continuing along this train of thought, consider 3D tic tac toe. Are there other types of winning lines? We have our horizontal, vertical, and in-your-face lines. They span just one dimension. And then we have the diagonal lines across slices of our cube. The fact that they exist on a slice means they don't move in the direction in which the slice is skinny.
Take any $3\times 3$ slice and draw its two diagonals; they span two dimensions.
Lastly, there are the long diagonals, from corner to opposite corner, which span all three dimensions. Three dimensions, three types of winning lines.
More generally, for tic tac toe in $n$ dimensions, there are $n$ different types of lines which correspond to lines spanning dimensions $1$ to $n$. If we can count each of these types, then we'll be finished.
The easiest line to count is the long diagonal, the line that spans all $n$ dimensions. There are two such lines in $3\times 3$ tic tac toe and four in $3\times 3\times 3$. Long diagonals begin at a corner, so we have an upper bound of the total number of corners. For a cube in $n$ dimensions, the number of corners is $2^n$. Since long diagonals also end at a corner, we're counting each of them twice. Thus, the total number of long-diagonals for an $n$-hypercube is $\frac{1}{2}2^n$.
Luckily for us, all line types are instances of long diagonals. I called the line in Figure 7 a short diagonal because there were longer ones, but within its 2D slice, it's a long diagonal. Even horizontal and vertical lines are diagonals, just in one dimension instead of two or three.
If we can count the number of 2D slices in a 3D cube, multiplying by $\frac{1}{2}2^2$ will give the number of lines that span two dimensions. Similarly, we need to count the number of 1D "slivers". So far, we've focused on the dimensions in which a line changes, labeling lines as spanning either 1D, 2D, or 3D depending on how many dimensions it moves in. However, for the purposes of counting, I think it's easier to look at the dimensions in which a line doesn't move. A 1D line doesn't move in two of the three dimensions, and a 3D long diagonal moves in all of them. For a 1D line, two dimensions are the same for all of its constituent points.
This brings us to a key question: in how many ways can two dimensions be the same? For a 3D cube, answering this question will give us the number of 1D slivers.
Various pairs of dimensions can be the same: $\langle x,y\rangle$, $\langle x,z\rangle$, and $\langle y,z\rangle$. Each of these dimensions can take on values from $0$ to $S-1$, where $S$ is the side length, so there are $S^2$ slivers for each of the three pairings. This yields $27$ one-dimensional slivers for a 3D cube. Since the number of long diagonals in one dimension is $\frac{1}{2}2^1=1$, there are $27$ horizontal, vertical, and in-your-face lines for $3\times 3\times 3$.
Let's go back and examine the number of 2D slices in a 3D cube. We now know this is equivalent to finding the number of ways that one dimension can be the same. That constant dimension can be $\langle x\rangle$, $\langle y\rangle$, or $\langle z\rangle$, each of which can take on $S=3$ different values, giving us $9$ slices total. There are $\frac{1}{2}2^2=2$ long diagonals per slice, giving us $18$ "two-dimensional" lines in a $3\times 3\times 3$ cube.
Since there's just one way for zero dimensions to be the same, there are $\frac{1}{2}2^3=4$ "three-dimensional" lines in a $3\times 3\times 3$. Summing these values gives $27+18+4=49$ ways to win in three-dimensional tic tac toe ($S=3$).
For a general solution, we need an expression that gives the number of ways in which $C$ dimensions can be the same for a $D$-dimensional hypercube of side length $S$. First, we count the number of unique ways there are to choose $C$ dimensions out of $D$. That's just ${D \choose C}$. Then, since each of those $C$ dimensions can take $S$ possible values, we multiply by $S^C$ to get ${D \choose C}S^C$.
Since $C$ dimensions are the same, $D-C$ dimensions can vary. The number of long diagonals in this space is $\frac{1}{2}2^{D-C}$. Multiplying these two expressions tells us that when you hold $C$ dimensions constant, you can create $\frac{1}{2}{D \choose C} 2^{D-C} S^C$ lines.
Anywhere from $C=0$ to $C=D-1$ dimensions can be constant, so to get our final answer we just need to sum up all those possibilities. The total number of ways to win in $D$-dimensional tic tac toe (side length $S$) is:
$$\frac{1}{2}\sum\limits_{C=0}^{D-1} {D \choose C} 2^{D-C} S^C\tag{1}$$
If you've ever implemented $3\times 3$ tic tac toe, you know about that annoying moment when you have to decide how you're going to detect winning moves. Since there are only eight ways to win, writing an if
statement for each possibility is easy and pain free. But it's also ugly and terribly inelegant. You could be a little more clever and write two loops, one for the vertical lines and one for the horizontals, checking diagonals separately, but that would be more work for little benefit. Heck, it'd probably take more lines of code.
In three-dimensional tic tac toe there are $49$ cases to consider ($S=3$). Yeaahhh. Clearly, you can't hardcode each individual configuration in an if
like you could with $3\times 3$. Perhaps you could store winning lines in a condensed format, like [3,14,25]
where each number corresponds to a cell in the grid, but that would be tedious and again, inelegant. And what if you wanted to expand your game to support $4\times 4\times 4$? Abstracting out the idea of slices and writing a series of loops would probably be best. Unlike $3\times 3$, there's enough repetition in 3D tic tac toe to warrant looping over the different types of lines.
Do you see where I'm going with this? For four-dimensional tic tac toe ($S=3$), you would need to check $272$ cases. There is no way you're listing all those lines out. As far as scaling back and looking at the grid's constituent layers and 3D slices goes, it's a lot harder to program something you can't visualize.
It's easy to check for lines on the six faces of a cube (and the middle slices) because we can see them, but the analogy in four dimensions is that there are eight "surface" cubes on a tesseract. Finding those faces and looping over them is incredibly confusing. And don't forget, you still have your 2D layers and 1D slivers like you did before! When you can't point to the geometry you're working with, it's hard to reason about what your algorithm should even be checking for.
I spent a lot of time thinking about this problem back when I started playing 4D tic tac toe, and I knew that I wanted to find an algorithm that generalized to any size hypercube in any number of dimensions. The solution is based off the method we used to count the number of ways to win. That is to say, given the game grid as a whole, we pick and choose dimensions to hold constant in order to reduce the problem to a lower dimensional space.
Before I explain the algorithm, I need to explain the data structure I chose to store the game state. It's a $D$-dimensional array whose elements correspond to grid spaces and are either $-1$, meaning empty, $0$, meaning player 1 has a piece there, or $1$, meaning player 2 has a piece there. For two-dimensional tic tac toe, it's just an everyday two-dimensional array. However, setting $D=4$ makes it an array of an array of an array of an array. I wrote a special function to access elements of this high-dimensional array given an array of coordinates.
There are two key ideas we discovered when we found the formula for the number of ways to win. The first idea is that all winning lines vary in at least one dimension. The second idea is that some dimensions may have the exact same coordinate value for all of the points in a winning line. For example, one of the four-dimensional winning lines we examined earlier:
$$\text{P}_1(\color{goldenrod} 0,\color{turquoise} {\underline 1},\color{magenta} 2,\color{yellowgreen} 0)$$ $$\text{P}_2(\color{goldenrod} 1,\color{turquoise} {\underline 1},\color{magenta} 1,\color{yellowgreen} 1)$$ $$\text{P}_3(\color{goldenrod} 2,\color{turquoise} {\underline 1},\color{magenta} 0,\color{yellowgreen} 2)$$
Notice how the $\color{turquoise} y$ coordinate is the same for all of the points. When we hold one dimension constant in three dimensions, we get a slice. When we hold one constant in four dimensions as we just did, we ought to get a 3D slice... but good luck visualizing where this cube fits. Good thing we don't need to! Notice how every single other dimension is different in points $\text{P}_1$ to $\text{P}_3$. These points describe a long diagonal of a 3D slice of a tesseract. I'll save you the trouble and just tell you that we'll only ever need to check for long diagonals!
How do you check for those in $n$ dimensions? First, generate the coordinates of all the corners. Pair each up with its exact opposite (for corners, each coordinate is either $0$ or $S-1$; two corners oppose each other if none of their corresponding coordinates are the same). Then, move grid space by grid space from one corner to the other.
Now we can start to sketch out an algorithm. First, check all the long diagonals in $n$-space for lines. Then, pick a dimension to hold constant. Set it constant for each value from $0$ to $S-1$ and recurse on the now-smaller dimensional space. Do this for each of the $D$ dimensions.
That's pretty much it. The base case is when $n=1$ since all you can do is iterate through the line. One way to implement this algorithm is to keep track of two arrays in each function call: one stores the dimensions that are allowed to vary and the other stores the values at which every other dimension is held constant. How freaking cool is it that we can write algorithms that can find lines we'll likely never be able to see (in seven dimensions, for instance)?
This algorithm as posed has its fair share of problems. For starters, it needlessly checks some lines more than once. By far the biggest issue though is that it checks every possible spot a line could be in, even if there aren't any pieces near that region of the hypercube. For three and four dimensions this really isn't that big of a deal because there are so few grid spaces in the first place.
Consider that a typical high-dimensional game of tic tac toe will have a dozen to a couple dozen placed pieces. At most, there could be $27$ pieces in 3D and $81$ in 4D (S=3), so around $15\%$ to $30\%$ of the board would be filled. Now consider a five dimensional grid with $S=7$: there are $16807$ grid spaces, resulting in an expected $0.1\%$ fill rate. This algorithm would waste so much time on empty space.
Ideally, I'd write an algorithm that found lines between sets of points. Instead of checking the grid, I would check the pieces that have actually been placed. Regardless of the number of dimensions or size of hypercube, the number of player 1 points and player 2 points would be small, so I can't imagine you'd need to do too much work. If any of you readers have implemented this, I'd be very interested in seeing your code.
Tic tac toe is great, higher dimensions are great, and math and computer science are great. I strongly encourage you to fork this project on Github and make something neat. All the rendering is taken care of; you can focus on your game ideas! Try making three-player 4D. Maybe that would nullify player 1's advantage. Hmm. Or you could write an AI and have computers play each other! Anyway, this is my longest blog post yet by far so I oughta stop thinking out loud.
]]>CR is meant to assess students' comprehension skills, which, to the College Board, means seeing if they know a million esoteric vocabulary words. I analyzed a few official SAT practice tests and found that around $30\%$ of the CR section is direct vocabulary assessment. But that's not the only reason learning new words is essential to doing well. A strong vocabulary will help you articulate your thoughts on the essay and breeze through the passages featured on the test.
I'm a programmer, so in the months prior to my SAT date, I wrote a bunch of programs to help me study vocabulary, my Achille's heel. I made websites, Android apps, and desktop programs to optimize my studying as much as possible. Yet as hard as I had tried to find a secret, hyper-efficient method, my creations only ever made it mildly easier to study. The problem with vocabulary is that there's nothing conceptual about it. It's all about memory, so there aren't any elegant shortcuts to speed up learning.
I'll bet you've heard your teachers tell you, "Reading is the best way to learn new words!" Admittedly, the logic is sound. Vocabulary is about memory, and it's easy to remember a word if you're constantly exposed to it. Therefore, reading challenging books expands your vocabulary because doing so inundates you with words you don't know... right? I'm sure you don't need me to tell you that this is a very unsatisfying answer.
It's not that I disagree, but rather that this "indirect" style of learning fails to provide an immediate sense of progress. Not to mention you, like me, don't have time in your schedule to read a couple of additional books a week. Don't worry though, there's hope. According to this article:
... if you go online and visit web pages in one day - which is a simple task when you could email, blogs, youtube etc - you'll see on average words; War & Peace was only 460,000 words
$200$ pages means you'll "see" approximately $500,000$ words a day. You won't necessarily read and think about them. Let's estimate a clean $10\%$ read rate (depends on reading speed and engagement). I'll even give you Sundays off. This means on average, you'll read $50,000$ words a day and $300,000$ words a week through your internet browser (including mobile browsers). This is equivalent to the number of words in the entire Hunger Games trilogy. So, no. You really don't have time to read a couple extra books a week. You have time to read three.
Of course, it's not so simple. Sure, you're reading hundreds of thousands of words, but I doubt the random web pages on the world wide web push you to your lexical limits. To really take advantage of this phenomenon, we need to figure out a way to increase the quality of words we're reading. It'd be impossible and silly to contact every single publisher of words on the internet, so our solution must work within our own computers. Manipulating words on websites? Making them "smarter"? This is right up natural language processing's alley! Let's make a Chrome extension.
Here's the high level strategy: look at every single word on a webpage and replace simple ones with more complex words that mean, more or less, the same thing. This should expose us to the types of vocabulary words we long to know without negatively impacting our internet experience. This strategy sounds fine to me, but there are a couple problems. How will we know if a word is simple? What does that even mean in this context? How will we know if a "complex" replacement really is more complex? How the heck are we going to find words that mean the same thing?
If we assume that people use simple words more than they use advanced words, then this isn't too difficult a quantity to estimate. We just need to look at which words get used the most to find simple words and the least for complicated words. Argh... but now we have another question to answer. How can we possibly know how many times a word has been used?
In natural language processing, corpora (plural of corpus) are used whenever you need to do... anything. A text corpus is a huge collection of words, sentences, or passages, often annotated with linguistic information and organized by source (e.g. oral, written, fiction). All we need to do is download a diverse, few-million word corpus and count the number of occurences of each word. If our corpus draws from a variety of language sources, we should get a good approximation of English word frequencies.
This is what synonyms were made for! All we need is access to a thesaurus and we'll be set.
...except we have high standards and blind thesaurus bashing is unlikely to be very effective. Consider the following scenario. We have the sentence:
Leaves fall down in fall.
and a desire to spice up the repeated word, "fall". If we blindly consult a thesaurus, we might end up with something like:
Leaves descend down in descend.
Remember: computers aren't smart enough to realize it doesn't make sense to use this word in both scenarios! We haven't been nearly explicit enough. Errors abound in our current system because it has no conception of part of speech (POS). Quality thesauruses will separate synonyms by POS, so as long as the computer knows the POS of each word, our system should work.
Leaves descend down in autumn.
Unfortunately computing POS is a pretty difficult problem. Even humans have trouble tagging really confusing sentences! It's not as if we can keep a list of the parts of speech of every word and just look it up when we need it. POS depends on context. To solve this problem, we really will need NLP. The technical details of how various POS tagging algorithms work are beyond the scope of this article, but here's a quick run down of a common method:
First, we need a sufficiently large corpus. Our corpus needs to have thousands of sentences, and it must include the correct parts of speech of every single word.
Then we need to pore through this corpus and keep track of a few things. How often is each word each POS? For instance, perhaps "fall" is a verb 70% of the time and a noun the rest. Next, how often does each POS follow each other POS? If we know that nouns are very likely to follow adjectives, then we can make some pretty good predictions.
That rule came from the top of my head because I'm a native English speaker. Computers can come up with hundreds of such rules because they have the benefit of speed (and an inability to feel boredom). If we wanted to be fancy, we might even ask, "If I saw an 1) adverb and then I saw a 2) verb, how likely am I to see a 3) noun next?" for all possible POS combinations.
The next bit is the hard part. If we guess the POS of each word randomly, we can assess the quality of our guess with all the probabilities we calculated from our corpus. We just need to go through each word and consider: is this word likely to be this POS? Is this POS likely to follow the previous POS? How likely is this POS to follow the previous two POS? The specifics might sound confusing, but they're unimportant.
Its' pretty clear guessing randomly isn't going to cut it. We do want the best possible POS assignments, after all. Seriously, what are the odds of guessing the correct POS for a $20$ word sentence? This is left as an exercise for the reader. There are just way too many possible POS combinations. Too many to check blindly, even if we use a really fast computer. Thankfully, this clever dude invented the Viterbi algorithm, which solves our exact problem.
We know how to find appropriate words with equivalent meanings and we know how to assess word complexity. We have all the tools we need to finish the extension, but let's take a step back and reconsider our intent.
We're making this extension specifically to help us with SAT vocabulary. There are SAT word lists. Why learn random "big" words when we can learn specifically the ones we need? The word list I used when I first made this extension included both SAT and GRE words, but it's no longer available online. That's not a problem though because there are tons of free lists.
Here's a new strategy that takes advantage of our insight. For every word on a webpage, if it's a SYNONYM of an SAT word AND the same POS, replace it with that SAT word. We're ignoring the whole bit about word difficulty because that was never the priority. Complexity was a proxy to our real goal - success with SAT words, something we now have direct access to.
As much as we'd like for this extension to produce perfectly fluid webpages, it doesn't. It's analogous to using a thesaurus to trick others into thinking you have a massive vocabulary. Not only must a word's meaning make sense, but also its context. The algorithm I proposed doesn't address this very important language feature, so there's no way its results can be perfect.
That isn't to say it isn't useful. All we need to do is make it so our SAT word replacements appear in a little hovering box.
This way, we retain the fluidity of the original webpage while easily exposing ourselves to SAT words in relevant, memorable contexts.
You can check out my Smart Words browser extension on the Chrome webstore or, if you're already keen to try it, . This was an immense help last year when I was studying for the SAT, and I'm sure that'll be the case for you too, if you're committed and stick with it.
This extension would have taken way longer to make if not for a few fantastic projects.
Stacking up a few of these 2-dimensional waves forms a dark blob.
Combining a few dozen more creates a graceful -- still unrecognizable -- shape. As we add more and more waves, notice how each image relates to the last.
The fact that we're dealing with waves means our image is very smooth (i.e. no sharp transitions) and fluid-like. However, by the time we're up to a few hundred 2D waves, the image's main shapes are clearly defined.
A couple thousand waves tells us we're definitely looking at a face, though it's not yet clear who we're looking at.
If we have one wave for each pixel in this $256\times 256$ image ($65,536$ waves in this case), then we can define it perfectly. Believe it or not, this was an image of the Youtuber Grace Helbig all along!
When an image is drawn to your screen, it's drawn pixel by pixel. A pixel is a tiny square of color, and it's difficult to see individual pixels because they blend together perfectly to form images. Pixels are spatial. They occupy some specific location in 2D space (3D pixels are called voxels), and they have a specific color associated with them. Thus, to talk about an image in terms of its pixels is to talk about it in terms of its spatial domain. But as we just learned, there are other ways to talk about images.
We learned how to describe an image as a combination of waves, which are pretty simple mathematical objects. Waves have frequency (how "wavy" they are) and phase (what direction they're going). Here's a wave with a very high frequency:
Here's that same wave with a different phase:
When we talk about an image's constituent waves, we're talking about its frequency domain, in contrast to its spatial domain, pixels. Pixels and waves are two valid and useful ways of thinking about images. The natural question is how do we move between these two totally different representations? How did I chose those few hundred waves that resulted in a blurry Grace Helbig?
Space and frequency are two languages equally capable of talking about images. The spatial domain is Spanish. The frequency domain is French. The Fourier Transform is a Spanish to French translator (fun fact: Joseph Fourier was a French mathematician!). The Inverse Fourier Transform is, you guessed it, a French to Spanish translator.
The unfortunate problem with this ultra-convenient translator Fourier gave us is that's it's super slow. If you wanted to translate the pixels of a $1920\times 1080$ image into a bunch of waves, it'd take your computer a week or two to do the math! The Fast Fourier Transform, on the other hand, could do the same thing in a few seconds.
I've always been interested in random, computer-generated art pieces because it challenges the idea that art is something that is strictly human. I've explored this and created a demo based off of traditional ideas, but I wanted to give this problem another go with some of my own.
Generating a random image is super duper easy. Watch, here's one:
Boom! Here's another:
I'm willing to bet that not only do you believe the first image is more random than the second, but also that the second is more "artistic". I assure you, the only difference between the two images is the size of the rectangles. In the first image, the rectangles are all $1\times 1$, so you don't even know they're there. In the second, the rectangles are of random sizes, meaning many of them are large and easy to see. In this way, the second image is even more random than the first. I also brightened up the colors of the second image, but that's besides the point.
The point is art is always based on some sort of pattern, however subtle or blatant. Patterns are comforting, which is why the second image and its large areas of constant color are more pleasing, aesthetically, than the first.
These images are random in the spatial domain because I generated them by randomly picking physical spots for each rectangle. If you translate the pixels to French, err, the frequency domain, it turns out the waves you get are also pretty random. There are high and low frequency waves alike, with no clear patterns visible whatsoever.
By definition, patterns are restrictive. They include some very specific shapes, sounds, and ideas and reject all others. A question I had was whether this definition went both ways. Do restrictions necessarily result in patterns? If we restrict the frequency domain to low frequencies only, will we get white-noise-esque garbage or something more attractive? Will it matter which frequencies we choose so long as they are low?
This project explores how randomness in one domain (frequency) translates to art in another (spacial).
A genetic algorithm is one that borrows ideas from evolution (biological evolution). In this demo, you'll be presented with images composed of a bunch of low frequency waves. You'll choose your favorite, "killing" the rest of the images as they weren't fit enough to survive (to earn your approval. Yeah, evolution is brutal). The image you choose seeds the next generation, meaning it's used as the basis for all the new pictures. New pictures are slightly mutated versions of your choice. In this way, your creations inch towards the optimal image you have in mind. Warning: it may take a few million years to get decent results, depending on your standards.
Click on your favorite picture. Avoid clicking the top left image whenever possible to maximize diversity.
If you'd like to play around with this project, check out its github repository. I've already added multi-color functionality, but at this stage, I prefer black and white. See if you can make some awesome color images with this web app!
]]>Brainfuck is an incredibly confusing language that uses just 8 characters: +
, -
, >
, <
, .
, ,
, [
, and ]
. The language was made with this esoterism in mind, making it very difficult for humans to write programs in it. The natural question is: would a computer be similarly confused?
Traditionally, genetic programming has been applied strictly to languages that are hierarchical in nature and therefore conducive to crossover (a post explaining genetic programming is coming soon). For example, Lisp. But that's been done a million times before. I wanted to see if GP could be applied to procedural languages. Would GP offer any benefit over randomly generated programs? And if so, would this benefit be significant enough to surpass my own ability to write Brainfuck?
Genetic programming is a fancy, super cool, bio-inspired search algorithm. Ignoring all the analogies to real world evolution, it's nothing more than a method of traversing some space of possible answers. For this problem, that answer space is the set of all possible Brainfuck programs. If we require that each program be $32$ characters long, then there are $8^{32}=7.9\times10^{28}$ potential answers because each character can be one of $8$ commands. Keep in mind that not all strings in this answer space are valid programs. Here are a few examples of $32$ character long programs that are:
$$>,<+,[+[+.>>]].-<[-,<]+.+.-->..<$$
$$[+[.-.]<->,-]>[..++<-..-.]++>+,.$$
$$++<.[[-]..[>.]],.>,.--[<]<,.>..-$$
$$>+[++[..-.]>],-..->+.--.>..<,..+$$
Imagine a billion billion billion of those. Now imagine going through all billion billion billion of those and finding one that solves the problem at hand. Genetic programming doesn't iterate through every possibility, but it still arrives at pretty good answers. It's based on the idea that okay solutions are similar to good solutions which are similar to great solutions. GP relies on the fact that success builds up. This has been shown to be absolutely true for high level languages with clear, tree-like structures, but it isn't immediately obvious that this property applies to Brainfuck.
Another method is to search randomly. This is superior to an organized, one after another approach because you don't have to waste any time probing unsuccessful regions of the search space. As long as you keep track of the best program you've seen so far, you can take a comprehensive survey of the answer space with very little work. Keep in mind, search spaces are often tremendous, so this approach is unlikely to work well.
My hypothesis that genetic programming is better than chance (for Brainfuck) can be tested by comparing how long it takes each method to solve a certain problem. For simplicity's sake, I chose the problem of symbolic regression, which is the process of finding an equation to model some data set. I tested how long it took randomly generated programs to model a simple set of points, and then I looked at how long it took genetic programming to converge on the solution to that same set of points.
This table shows various measures of how long it took each method to solve a simple symbolic regression problem. The genetic programmer was run with a maximum program size of $32$ characters and a population size of $50$. Each method underwent $50$ trials. As these are all times, smaller numbers are better.
Method | Avg (s) | Min (s) | Max (s) | Std. Dev. |
---|---|---|---|---|
GP | 7.653 | 2.015 | 20.536 | 4.317 |
Chance | 44.765 | 0.970 | 179.37 | 46.877 |
Both methods solved the problem pretty quickly some of the time, but GP maxed out at around $20$ seconds while random chance took as long as $3$ minutes. Comparing their averages, GP performed $5.85$ times as quickly. The following is a smoothed histogram^{*} displaying the percentage of trials that took a certain amount of time to run.
Genetic programming is the clear winner.
^{*}Note: the data was smoothed heavily, so area isn't proportional to number of samples like it should be.
At this point, I knew that using GP to write Brainfuck wasn't a waste of time, so I began competing with it to answer my second question. Before explaining the test cases I chose, I'll describe Brainfuck's language features. There's no formal specification of the language, so not all implementations define each of the eight commands in the same way. I'll describe my interpreter, which is pretty standard.
Brainfuck is characterized by its ultra-simple method of keeping track of information. Each program begins with a couple hundred cells all filled with the value $0$. Programs can only focus on one cell at a time, moving between them with the >
and <
characters, right and left. The +
character increments the current cell by one, and the -
character decrements it. Cell values are capped at $255$, looping around to $0$ whenever they overflow.
Brainfuck also has input and output, with the ,
and .
characters, respectively. My ,
character reads bytes from an input stream (one byte per ,
) and loads them into the current cell. My .
character adds the current cell's value to an accumulator, which starts at $0$ and is returned when the program terminates.
Lastly, there are the [
and ]
characters, which work together to enable loops. The Brainfuck code they sandwich is run again and again until the cell that's in focus at the end of the loop is $0$. The program:
$$++[>++<-]>.$$
increments the first cell to two and loops the following subroutine twice: add two to the cell to the right, move back left, and decrement. Then, it moves to the cell it was incrementing and outputs it. If this program were written in Javascript, it'd look something like:
var cell_0 = 0, cell_1 = 0;
cell_0++;
cell_0++;
while (cell_0 !== 0) {
cell_1++;
cell_1++;
cell_0--;
}
console.log(cell_1);
A simpler version would be "$++++.$". There's always the risk of infinite loops, so I opted for the simple solution of setting a time limit to the execution of a Brainfuck program.
I knew the limitations of my Brainfuck implementation, so I didn't choose very glamorous test cases. I tested the genetic programmer on constant generation (outputting a constant number like $86$ for instance), on adding a constant to an input, on summing two inputs, and on multiplying two inputs. I was able to write Brainfuck programs that did all these things pretty easily, and so was the genetic programmer. Then I tried division by two.
I gave myself a half hour to solve the problem, but I wasn't able to come up with a Brainfuck program that did what I wanted! The best I was able to do was "$,[>+.-<--]$", which works for even numbers only. The genetic programmer, however, was able to do it:
$$,[-[->+>.<.>]<-<].+$$
I still don't understand how its division algorithm works. I've implemented the algorithm in Javascript and followed its execution, but I still lack a clear understanding of why it works.
Hmm, I thought. If only I could recognize even and odd numbers, then I could write programs for each of the two separate cases and combine them. So began the next challenge, finding the remainder of a number when divided by two. I wasn't able to solve this problem either (only solved it for even numbers). But of course the genetic programmer was:
$$,[-<+.>[--][>->.,[-]<<]],$$
In eleven minutes, even (pun intended)! Something that amazes me about this specific program is that it purposely puts itself in an infinite loop for even numbers, because when I first evolved this program, my interpreter output $0$ if programs took more than a few milliseconds to run. $0$ just so happens to be the correct answer for even numbers, so it works! Evolution cares about one thing and one thing only: practicality. The genetic programmer found a niche, timing out to force a $0$ output, and it exploited it perfectly to solve the problem at hand.
Here's an interpreter for my flavor of Brainfuck. It only supports integer outputs so you can't work with characters, but you'd literally have to modify less than five lines of code if you wanted ASCII output. All you'd need to do is change the behavior of the .
command. Fork this project on github.
The ,
character loads the leftmost unseen input into the current cell. Inputs must be integers in the range $[0,256)$.
Try copy pasting the divide-by-two program, loading the dividend in the first input section. Then play around with the program's source to see which characters are essential and which aren't. The programs work, but by no means are they optimal.
I initially wrote the genetic algorithm in Java back in 2012, and I only recently ported it to JavaScript. I have a generic UI I use to visualize genetic algorithms/programs I write for the web, but I need to modify it slightly to provide meaningful information on the Brainfuck genetic programmer. It's also significantly slower than my Java implementation, so it isn't as able to solve interesting problems in reasonable amounts of time. In the meantime, I'm currently working on a general blog post on genetic algorithms/programming, so stay tuned for that.
]]>The demo below requires WebGL. If it doesn't work, upgrade to a modern browser like Chrome. Use W
, A
, S
, and D
to move around. Use Space
and Shift
to fly up and down. Use the arrow keys to rotate. Click to focus and begin, and click outside to exit.
The Sink
The first thing people notice when they walk into the band room is the random sink to the right of the door. The first issue with the sink is its placement. It is impossible for wheelchair users to navigate around it in its current orientation. Also, its position in the middle of what should be an open clearing poses a hazard for people with impaired vision.
The easiest fix is to push the sink against the wall because doing so moves it out of the way and provides people with wheelchairs easier access. To accommodate this change, an automated faucet would need to be installed. For maximum comfort, the entire desk/sink should be closer to the ground, and there should be room beneath the sink to allow wheelchair users to slide in close. In my opinion, these changes make the sink a much more attractive fixture of the room, showing how adhering to the Social Minority Model (SMM) can inspire creative design solutions for everyone.
The Air Filter
The current band room’s layout is very confusing, with all of its twists, turns, and level changes, so I installed a purposely loud air filter as an audible landmark. I placed it at the beginning of the room so people would instantly be able to tell how far into the band room they are.
The air filter will also help people with allergies, like me, but everyone benefits from cleaner air. This demonstrates the fact that modifications that level the playing-field make everyone’s lives easier. If people don’t include others on their own, then learning about the Disability Rights Movement teaches them to do so for their own benefit.
The Ramps
Another unique characteristic of the band room is its multi-layered structure. There are three floors of desks, and no easy way for wheelchair users to navigate between them. Also, the steps could be quite jarring for blind people if their canes don’t make it immediately clear that there’s a drop.
To fix the first problem, I installed ramps on both sides of the room. This way, people entering can take the shortest route to their desired destination, and people can loop around the entire room if necessary.
The Borders
To prevent the problem of tripping and falling, I created a border material on the edges of the steps. This way, people will know when they’re getting close to an edge. I also specifically colored each level of ramp a darker pink than the level above it because people with depth perception issues might not realize there’s a downward slope. Darker colors are an intuitive representation of depth.
At first, it was only obvious that the room needed one ramp. But by reflecting on the decisions of the Ed Roberts campus, I realized two ramps were optimal because of the difficulty people in wheelchairs have turning around. Keeping disabled people in mind when designing buildings teaches people to be more empathetic.
The Piano and Desk
The piano and front desk were moved to reduce the clutter near the front of the classroom. This clears the way for wheelchair uses and makes the room look nicer overall. Likewise, the whiteboard was removed and a projection system was installed on the wall above the piano and desk. This makes it easier for everyone to read in-class presentations.
The Doors
Making the manual doors automatic is a trivial change but an important one. I made all of the doors in the band room larger and automatic to give people in wheelchairs plenty of clearance when entering and exiting the building.
The Glass
The band room currently looks pretty grim from the inside, so I replaced the back wall with glass. This will let in natural light during the day and allow people to see inside the newly designed building as they walk around the gym.
The Ceiling
One big problem with the band room is how reverberant it is. Whenever a few people sing and play instruments together, the loudest person’s echoes drown out everyone else. The echoes make it hard to stay focused on the music, which impedes practices. Even worse, it’s impossible for two groups of people to play different pieces at the same time because each group can hear the other.
To fix these issues, I installed a stretchy fabric material under the ceiling to absorb the noise (not shown in the images due to the impracticality of setting up ceiling-specific light sources and the fact that it would just be a flat plane). This feature wouldn’t interfere with nearby sounds, but it would prevent noises from echoing and traveling too far. Again, this benefits everybody, but people with difficulty hearing would benefit the most. This speaks to the fact that universal design isn’t specific to disability but rather to humans (and maybe animals too).
What are the ways in which the Social Minority Model, the Disability Rights Movement, and a study of Disability expand our understanding and enrich our world?
The Social Minority Model increases people’s understanding by opening their eyes to diversity. By making simple changes to the environment instead of to the people, the SMM shows everyone how easy it is to be inclusive. It consequently gives disabled people the option to preserve their identities, enabling them to actively participate in the rest of society. The SMM therefore makes it easier for Disability activists to fight for their rights.
The Disability Rights Movement is an excellent source of upstanders. It inspires repressed people everywhere not because it involves disabled people but because it saw great success despite ancient stigmas hindering its progress. Lastly, it’s important to study Disability because it challenges one’s prejudices. I didn’t have any ill feelings towards disabled people before this unit in Psychology class, but I never thought critically about Disability before either. Now that I’ve thought significantly more about it, I am more confident in my ability to be a tolerant human being.
]]>One-dimensional CA were first popularized by Stephen Wolfram, who wrote a book about them called A New Kind of Science. It's quite lengthy, but there are tons of cool pictures and lots of new ideas (I had never even heard of 1D CA before reading it). For example, the 1D CA with neighbor distance $1$ and rule $01101110_2=110_{10}$ (if you don't know what these terms mean just hang tight) is capable of simulating all computable functions, meaning given enough resources, it's basically a computer. I've yet to use rule $110_{10}$ for computation, but it certainly looks very cool (see for yourself below).
I recommend leaving all the boxes blank for your first run. Defaults will be inserted in blank boxes. Then you can play around with the values to see what each option does. Note: colors must be input in the following format, "#FE624A". If you're on a mobile device, I recommend clicking the image link for optimal viewing.
To save the background image, click on the link and type ctrl
+s. If you want to generate another random rule, make sure to delete the current one.
Start out with a row of zeroes and ones.
\(\require{color}\)
$$1010101110$$
Add a row of blank spots beneath it to denote the next generation. We can make two-dimensional images by stacking subsequent generations on top of each other.
$$1010101110$$
$$0000000000$$
For each $0$ in our new row, we're going to look at the previous row to decide whether or not it stays a $0$ or becomes a $1$. Here's where the "Neighbor distance" part comes in: we're only going to look at bits in the vicinity of the bit directly above the current $0$.
$$101\color{red}010\color{black}1110$$
$$0000\color{red}0\color{black}00000$$
We look at the bit directly above no matter what. But see how our view extends one to the left and one to the right? That's the neighbor distance. So now we need to decide whether or not the current $0$ should be a $1$ based on the pattern $010$. How do we do that? It's super easy. Cellular automata are defined by their rules, and their rules tell us exactly which patterns get turned into $1$s. I won't describe this in too much detail, but imagine listing out every possible pattern for a given neighbor distance:
$$000,001,010,011,100,101,110,111$$
And highlighting the patterns that you want to result in $1$s.
$$000,001,\color{red}010\color{black},011,100,101,\color{red}110\color{black},111$$
Now, write $0$s for all the unhighlighted patterns and $1$s for those that are.
$$\text{Rule: }00100010$$
All we have to do is apply this rule a million times and we'll have a nice new background image to show off. Aren't you glad you're not a computer?
Here's the strategy: Draw a unit circle (radius of $1$), and pay attention to the portion in the top right quadrant. The area of the square that surrounds this quarter-circle is $1$ because each of the sides is $1$ (see the image below). The area of the circle is $\pi r^2=\pi\times 1=\pi$. So, the area of the quarter-circle is $\frac{\pi}{4}$. The ratio of the area between the quarter-circle and the square is then $\frac{\pi}{4}:1=\frac{\pi}{4}$. This means if we were to hang these shapes on a wall and throw darts at them randomly, $\frac{\pi}{4}\approx75.5\%$ of them would be within the quarter-circle. So once we finish throwing a bunch of darts, all we need to do is multiply the quarter-circle:square ratio that we observe by $4$ to approximate $\pi$.
Techniques like this one that use random sampling to solve problems are called "Monte Carlo methods". Why the randomness? Why not just throw darts procedurally down each row and column? That would work well for this problem because we wouldn't have to test too many points. A $400\times 400$ image has $160,000$ pixels, which would be easy to run through on a modern computer. However, for some problems, running through every possibility would take far too much time. Monte Carlo methods are hugely beneficial in these cases because they allow you to get a good sense of what the sample-space looks like without actually sampling every single point.
]]>This program is a Gridworld^{1} Critter (named FlowerHunter) that hunts Flowers by using an artificial neural network (ANN) to make decisions. A genetic algorithm is used to improve the ANNs.
FlowerHunters are able to sense the immediate 8 spaces around them. They use their brains (ANNs) to decide where to move (they can only move to blank spots or spots with Flowers). All decisions are made by their brains (they have no hardcoded motivation to move towards Flowers).
The ANN consists of an input layer (inputs are Doubles), a configurable number of hidden layers (size of each layer is configurable as well), and an output layer. This is a boolean ANN, meaning each neuron outputs a 1 or a 0. Currently the neurons have no activation function; each neuron simply fires (outputs a 1) if the weighted sum of all its connected neurons is greater than its threshold. This means the output layer is a bunch of zeroes and ones, but it can easily be interpreted as a list of Integers or Strings.
Each FlowerHunter has an ANN for a brain. There are 25 inputs in the current implementation: for each of the 8 possible neighboring locations, 1 x coord, 1 y coord, and a number signifying whether or not the Actor (or null) at this location is a Flower. This makes 8*3 = 24 inputs, and the 25th input is the output of Java's Math.random() to vary the behavior each time. Each FlowerHunter begins with randomly assigned weights and thresholds, so initially, their brains aren't very good at figuring out how to eat Flowers. There are 3 outputs because 3 outputs -> 3 bits -> 8 possibilities -> which of the 8 neighboring locations to choose (this explanation is incomplete so look at the implementation for specifics).
This program is essentially a cartesian genetic programmer, except instead of many different function nodes, there's just one (weighted sum function in the neurons of the ANN).
When the program starts (Generation #1), 5 random FlowerHunters (random brains) are created. Each FlowerHunter is placed on a grid randomly populated with Flowers and allowed to act a specific number of times. Once it's finished, the number of Flowers consumed is computed and treated as that FlowerHunter's score. This process is repeated dozens and dozens of times for each FlowerHunter in order to calculate an accurate average score. From these initial 5 FlowerHunters, the highest scoring one is chosen as the seed for the next generation. It is taken and mutated (the weights and thresholds of its brain are changed slightly) 4 times to produce the next generation of 5 FlowerHunters. This process is repeated every time the user clicks the "step" button.
The fact that only FlowerHunters that score well are chosen means there's an environmental pressure to score well. Successive generations get better and better scores because only high scoring FlowerHunters surive to the next round. The important point to note here is that the motivation to consume Flowers comes from the outside. There's no code within each FlowerHunter that tells it to eat Flowers.
Currently, there's no way to see the FlowerHunters in action. The hundreds of trials necessary for each generation take milliseconds to run, so clicking the "step" button leaves the Grid in whatever state the last FlowerHunter left it in.
This means there's no way to qualitatively describe the behavior of successful FlowerHunters. I'm really intersted in seeing what kinds of strategies the CGP develops. Do brains always favor Flowers over empty spots? Do the FlowerHunters move towards the center of the Grid when there's nothing else they can do? The easiest way to answer these questions is to add a super slow-mo version of the program where each step of each trial of each FlowerHunter of each generation is rendered individually. Alternatively, the ability to export brains could be added, and then a separate program could be written that's nothing more than a FlowerHunter with that brain.
^{1} Gridworld is a Java program used to teach AP Computer Science to highschool students. It gives students the chance to work with a relatively large codebase without having to write a whole bunch of code themselves.
]]>Click your favorite picture. Avoid choosing the top left image whenever possible (when other images are exactly the same).
Some examples:
The most famous fractal out there is probably the Mandelbrot set.
It is incredibly self similar, as the above image demonstrates. Look at how the bulbs appear to repeat, shrinking and shrinking right to left. The bulbs themselves appear to have limbs, which recur all along their perimeters.
The Burning Ship fractal (BSF) can be thought of as the Mandelbrot set's sister. As we'll see later, the equations that describe them are essentially the same. Yet somehow, the fractals themselves appear totally different!
Unfortunately I didn't save the coordinates for this image, but I found a few more hearts in the window:
var graphWindow = {x_min: 1.7720029688446448,
x_max: 1.7720029688449772,
y_min: -0.040912002694266925,
y_max: -0.04091200269450447};
If this is the first you're hearing about fractals, then you probably think that it's extremely difficult to draw them. What If I told you that a picture of the Mandelbrot set can be described with the following equation and a few sentences:
$$z_{n+1}=z_n^2+c \tag{1}$$
$z$ and $c$ are complex numbers. The real and imaginary parts of $c$ represent each pixel's x and y-coordinate, respectively. Starting with $z_0=0$, we compute each successive $z$ value as per $(1)$ and observe $z_n$ to see if it spirals out of control. If a certain $c$ value leads to a sequence that doesn't stop growing, then we color the corresponding pixel white. All other $c$ values correspond to pixels that are in the Mandelbrot set and are consequently colored black.
If you were to take the absolute value of the real and imaginary parts of each $z_n$, you'd get the Burning Ship Fractal's equation:
$$z_{n+1}=(|\operatorname{Re}(z_n)|+i|\operatorname{Im}(z_n)|)^2+c \tag{2}$$
A natural question is whether or not pixel coordinates can be plugged in as is. The answer is no because the Mandelbrot set occupies a small, $\approx 3\times 2$ unit rectangle in the complex plane. Pixel values have to be mapped to this range.
If you know the dimensions of an image, the coordinates of a pixel can be transformed to a complex number within some window through the use of a map function which takes a number in one range and outputs a number a propotional distance within another range.
/* Given n in [d1, d2], return the corresponding number in [r1, r2]. I encourage you to rewrite this and explain the math on your own. */
function map(n, d1, d2, r1, r2) {
var Rd = d2-d1;
var Rr = r2-r1;
return (Rr/Rd)*(n - d1) + r1;
}
//all the points in this window represent complex numbers
var graphWindow = {
x_min: -2.5, x_max: 1, y_min: -1.25, y_max: 1.25
};
var w = 800; //width of the image
var h = 600; //height
var x = 0; //the pixel's x location, x in [0, w)
var y = 0; //" " y location, y in [0, h)
//the real part of the corresponding complex number
var re = map(x, 0, w, graphWindow.x_min, graphWindow.x_max);
/* Notice the the order of the h and 0; this is due to the fact that image y coordinates increase going down, not going up as in math.*/
var im = map(y, h, 0, graphWindow.y_min, graphWindow.y_max);
I'll leave it up to you to apply this process to all the pixels in a $w\times h$ image.
Next, you need to know how exactly you determine if a point "spirals out of control". By that, I mean if the magnitude of $z_n$ tends toward infinity. But how can you possibly know that? What if $|z_{791}|=10^9$ so you say close enough and stop, when $|z_{840}|$ would have settled back down to $30$, where it would have stayed? Well, there's this property that says that if $|z_n| > 2$, then it will spiral out of control. So all you need to do is see if $z_n$ stays below $2$ for a few hundred generations because if it does, then there's a good chance it's in the set.
This is all the information you need to write your own fractal painter, but it's a lot more fun if you add color. One way to do this is to say, points whose magnitudes exceed $2$ after $20$ iterations are green, after $40$ are red, and after $60$ are orange. Points whose $|z_n|$ stays below $2$ for all tested iterations are assumed to be in the set and are black. This works, but it leads to images with bands of color:
Sometimes this effect is desired, but usually people want to see images that are colored smoothly. You can do this by not only paying attention to how many iterations it takes a point to exceed the magical value of $2$, but also by paying attention to just how much it exceeds $2$ when it does. I'm not going to explain this any further because of all the images I've generated, my favorite one resulted from a faulty smooth coloring algorithm.
I didn't think much of this picture at the time, so I fixed my algorithm and moved on (I had not yet heard of version control). If you make the same mistake I did and start generating images like these, please send me a message and tell me how you did it!
Here's my implementation of a fractal explorer, 100% in Javascript. Scroll with your mouse to zoom in and out. Click and drag to move around. The images don't generate instantly, so don't try and do too many things at once. Play around with the settings below and see what they do.
To blob-save the image, right click and "copy" the image once you've pressed the button. Then paste it in some image editor and save that. About the colors: I've already made it easy to change the color scheme with Javascript, but I haven't gotten around to adding that feature to the GUI.
^{1} While it's true you can zoom arbitrarily deep into fractals like the Mandlebrot set, in practice the maximum zoom level depends on the strength of your computer and the fractal-viewer that you're using. This JS implementation is limited by the fact that JS Doubles are 64 bits.
]]>