How many triangles? Part 2

An algorithm for finding the abnormals

Before you begin this post, please check out my previous post, “How many triangles.” This post is a continuation of that post and you’ll need to have read that one to better understand this one.

In my previous post, I discussed a mathematical formula I developed to calculate the number of triangles that can be drawn on a n by n dot grid. The basic definition of the formula was: number of possible sets of 3 dots that can be formed - number of those sets that contain collinear dots. In the comments section, a reader pointed out that the formula didn’t account for the total number of sets containing collinear dots for grids of side magnitude n>4 (that is, some collinear dots were not recorded in the formula). Upon a careful look, I noticed that the claim was true. I therefore had to make a post to correct that error: this is that post. In this post, I’ll discuss the behavior of these new sets of collinear dots and an algorithm I devised to count them.

First let’s take a look at the collinear points that were initially identified: vertical dots, horizontal dots and diagonal dots.

Figure 1: A 5 by 5 dot grid showing sets of collinear dots accounted for in formula

From figure 1, it can be seen that to form the red lines, you start at any point (a,b) and jump 1 unit on the y-axis and 0 unit on the x-axis (for the vertical dots) or 0 unit on the y-axis and 1 unit on the x-axis (for the horizontal dots). The yellow lines are formed by moving 1 unit on the y-axis and 1 unit on the x-axis from any point (c,d). It turns out the yellow lines were not the only possible diagonals that could be formed: “there is another” *in Yoda’s voice*

Figure 2: A 5 by 5 dot grid showing collinear points unaccounted for in formula

Figure 2 shows another possible diagonal. This diagonal is formed by moving at a speed of (2,1). For other dot grids of greater side lengths, other diagonals of different speeds that also move rectangularly can be formed. Unlike the red lines and the yellow lines, these new collinear dots do not meet or cross each other at an angle of 90 degrees. Because of that I called them the abnormals (not normal to each other lol). These abnormals have a lot of properties in common. Let’s look at a few properties that influenced the algorithm.

Properties of abnormals that influenced the algorithm

• The speed of an abnormal is given by (i,j), where i,j are whole numbers such that min( i,j) >0 and max(i,j)>1. Also i and j should be mutually prime; this means they should have only one common factor, which is 1. i represents the vertical jumps and j represents the horizontal jumps.
• For any n by n dot grid, the abnormal with the maximum speed has a speed of (round down(n-1/2), round down(n-1/2)-1). For example, a 10 by 10 dot grid will have abnormals of speed: (4,3), (4,1), (3,2), (3,1) and (2,1). (4,2) is not added because it is just twice of (2,1): this is why the components of the speed need to be mutually prime.
• Abnormals of the same speed can have different lengths. For example, the abnormals of speed (2,1) in a 10 by 10 dot grid can have lengths of 5, 4 and 3 units.
• Abnormals of smaller lengths may be subsets of those of bigger lengths if and only if they have the same speed.
• I did the positioning of the dots in a n by n dot grid such that the top left most dot has a position of (0,0) and the bottom right most dot has a position of (n-1,n-1).
• In figure 2, the number of lines of speed (2,1) that are heading to the right side (the lines that start from (0,0), (0,1) and (0,2)) are the same as the lines heading to the left (the lines that start from (0,2), (0,3) and (0,4)). It can also be seen that the same pattern is formed laterally. Therefore the total number of abnormals there can be calculated by just multiplying the first three abnormals by 4. All other abnormals behave similarly.

The Algorithm

Given the side length of a dot grid, the first thing the algorithm does is that it calculates the speed of the fastest abnormal. Starting from the (0,0) dot, it moves to the right, finding and storing all the right abnormals on that row of that speed. When it reaches the end of the row, it does the same thing for subsequent rows. This process is repeated for all different sized abnormals of that speed. However before an abnormal is collected, the algorithm checks whether the abnormal is a subset of an already collected abnormal. The abnormal is only added if it is not a subset of any previously collected abnormal. The shortest abnormals are 3 dots long. Once those have been collected, the second component of speed is reduced by 1. And the whole process is performed for this new speed to collecte new abnormals. When the second component of the speed reaches 1, the first component is reduced by 1 and the second component is set to one less than the first component. The process continues until the last speed, (2,1). Once the process comes to an end, one fourth of all the abnormals of a given dot grid would have been collected and stored in a list. The function then just returns the length of that list times 4, which is the total number of abnormals in the dot grid. Check out the Python implementation of the algorithm below.

Figure 3: Python implementation of the algorithm

I tested the algorithm for dot grids of side lengths 5, 6, 7 and 8 and it worked for all these.

Figure 4: Testing algorithm for n= 4 and 5

You can also perform your own tests by comparing a manually calculated number of abnormals to the one the algorithm spits out. I feel there might be a way to do this with recursion. That would shorten the code and definitely make it more elegant, but I’m no good at that… yet.

Well, this brings us to the end of this post. Hope you enjoyed the ride :D

I would love to see questions and additions in the comments section. Don’t forget to leave a clap too :)