14 min. read
Computer Science is mathematics with extra steps. Everything is math with extra steps, but it matters what the extra steps actually are. This article will detail how to properly understand and implement mathematical concepts and how to use them in your programming algorithms efficiently and effectively.
Keep in mind, you don’t need to be a mathematics genius. AI nowadays will do that for you, but it’s pretty important that you actually nuderstand what slop your AI is actually generating in order to properly be effective in today’s professional landscape. So, let’s get right in.
The Combinatory Map Search Algorithm is described as a Recursive DFS Search Algorithm with Combinatorial Operations. Here’s the code for reference:
suspend fun findValues(
grid: Array<DoubleArray>,
functions: List<Operation>,
sx: Int,
sy: Int
): Set<Double> = coroutineScope {
val size = grid.size
require(grid.isNotEmpty()) { "Grid must have at least one row" }
require(grid[0].isNotEmpty()) { "Grid must have at least one column" }
require(sx in grid.indices) { "Starting X Coordinate must be within the grid" }
require(sy in grid[0].indices) { "Starting Y Coordinate must be within the grid" }
require(grid.all { row -> row.size == size }) { "Grid must be square" }
val channel = Channel<Double>()
val visited = mutableSetOf<Pair<Int, Int>>()
val values = mutableSetOf<Double>()
suspend fun exploreValue(value: Double, cx: Int, cy: Int, operations: List<Operation>) {
var hasMoved = false
directions.forEach directions@{ (dx, dy) ->
val nx = cx + dx
val ny = cy + dy
if (nx < 0.0 || nx >= size) return@directions
if (ny < 0.0 || ny >= size) return@directions
if (grid[nx][ny] == 0.0) return@directions
if ((nx to ny) in visited) return@directions
visited.add(nx to ny)
val nv = grid[nx][ny]
operations.forEach { o ->
val newValue = o(value, nv)
if (newValue in values) return@forEach
values.add(newValue)
channel.send(newValue)
val remaining = operations.toMutableList()
remaining.removeAt(remaining.indexOf(o))
exploreValue(newValue, nx, ny, remaining)
hasMoved = true
}
visited.remove(nx to ny)
}
if (!hasMoved || operations.isEmpty())
channel.send(value)
}
val sv = grid[sx][sy]
launch {
exploreValue(sv, sx, sy, functions)
channel.close()
}
for (value in channel)
values.add(value)
return@coroutineScope values
}
Now, what the hell does that mean? Let’s break it down:
The algorithm recursively explores all paths from a starting point as inputted by its parameters. It uses a visited set to avoid cycles and repeated paths, and uses hasMoved to track dead ends and ensure terminal values are captured.
At each step, it tries all possible operations with neighbors, determining an end value result. After using an operation, it removes it from the list to prevent repetition.
Finally, it applies mathematical transformations as part of the search. The algorithm builds a set of all reachable results via these operations.
Finally, it uses Kotlin’s Channel to emit values as they’re found, which allows for non-blocking collection while the recursive algorithm runs.
Now, I’ll be honest: I ChatGPT’d this mathematical explanation. But now I understand what kind of mathematical attributes my algorithm has, which allows me to calculate the time (O((4m)^k)) and space complexity (O(m(k!)) + O(n^2) + O(k)) of the algorithm. Now, this is Kotlin, which is a high-level language where memory and space management is done automatically. However, understanding these mathematical attributes about your algorithms is still vitally important.
The cmdfx game engine allows you to draw and implement different shapes and functions drawn in your own terminal. One of those functions is the ability to draw an arc in the terminal:
void Canvas_arc(int x1, int y1, int rx, int ry, double xrot, int arcflag, int sweepflag, int x2, int y2, char c) {
if (rx == 0) return;
if (ry == 0) return;
if (x1 < 0) return;
if (y1 < 0) return;
if (x2 < 0) return;
if (y2 < 0) return;
if (arcflag < 0) return;
if (arcflag > 1) return;
if (sweepflag < 0) return;
if (sweepflag > 1) return;
double phi = xrot * M_PI / 180.0;
double cosp = cos(phi);
double sinp = sin(phi);
// Step 1: Compute (x1', y1')
double dx = (x1 - x2) / 2.0;
double dy = (y1 - y2) / 2.0;
double x1p = cosp * dx + sinp * dy;
double y1p = -sinp * dx + cosp * dy;
// Ensure radii are large enough
double rx2 = rx * rx;
double ry2 = ry * ry;
double x1p2 = x1p * x1p;
double y1p2 = y1p * y1p;
double lambda = (x1p2 / rx2) + (y1p2 / ry2);
if (lambda > 1) {
double scale = sqrt(lambda);
rx *= scale;
ry *= scale;
rx2 = rx * rx;
ry2 = ry * ry;
}
// Step 2: Compute (cx', cy')
double sign = (arcflag == sweepflag) ? -1 : 1;
double num = rx2 * ry2 - rx2 * y1p2 - ry2 * x1p2;
double denom = rx2 * y1p2 + ry2 * x1p2;
double factor = sign * sqrt(fmax(0, num / denom));
double cxp = factor * (rx * y1p) / ry;
double cyp = factor * (-ry * x1p) / rx;
// Step 3: Compute (cx, cy)
double cx = cosp * cxp - sinp * cyp + (x1 + x2) / 2.0;
double cy = sinp * cxp + cosp * cyp + (y1 + y2) / 2.0;
// Step 4: Compute start and sweep angles
double theta1 = atan2((y1p - cyp) / ry, (x1p - cxp) / rx);
double theta2 = atan2((-y1p - cyp) / ry, (-x1p - cxp) / rx) - theta1;
if (sweepflag && theta2 < 0) theta2 += 2 * M_PI;
else if (!sweepflag && theta2 > 0) theta2 -= 2 * M_PI;
// Step 5: Draw arc as line segments
int prevX = x1;
int prevY = y1;
for (int i = 1; i <= 100; i++) {
double t = (double) i / 100;
double angle = theta1 + t * theta2;
double xt = rx * cos(angle);
double yt = ry * sin(angle);
// Rotate and translate back
double x = cosp * xt - sinp * yt + cx;
double y = sinp * xt + cosp * yt + cy;
Canvas_line(prevX, prevY, (int) (x + 0.5), (int) (y + 0.5), c);
prevX = (int) (x + 0.5);
prevY = (int) (y + 0.5);
}
}
This algorithm is a little bit easier for me to understand because I wrote this offline while on the plane. All I had with me was my MacBook, VSCode, and a mathematics textbook. That being said, ChatGPT will do a much better explaining what is going on.
The algorithm’s parameters have (rx, ry), starting X and Y coordinates, arc rotation in degrees, and flags for (counter) clockwise rotation (sweepflag) and a bigger/smaller arc (arcflag).
The coordinate rotation will follow the formula
[x′] = [ cos(ϕ) sin(ϕ) ][x]
[y′] = [ −sin(ϕ) cos(ϕ) ][y]
to find x prime (cx') and y prime (cy').
After the algorithm solves for the center of the ellipse using the transformed coordinates, it ensures that the ellipse fully spans from (x1, y1) to (x2, y2), even when rx and ry are too small, by scaling them up using a λ check. Then, it computes angles θ (theta1) and Δθ (theta2) using atan2 to get start and sweep angles for the arc.
After we got all of the mathematics jardon down, we use the following parametric formula to start drawing the arc:
x(t) = rxcos(t)
y(t) = rysin(t)
t in this instance is any decimal between 0 and 1 because the arc formula has a detail of 100 different line segments according to the for loop. Understanding the mathematical components of this formula was literally important becuase it literally uses math as apart of its formula. Because of this, I was able to take the AI slop of the initial formula and optimize it out so that it wasn’t drawing the different parts of the arc slow.
Here is a classic Merge Sort algorithm used as apart of my benchmarks side project:
function merge(arr, left, mid, right) {
const n1 = mid - left + 1;
const n2 = right - mid;
const L = new Array(n1);
const R = new Array(n2);
for (let i = 0; i < n1; i++)
L[i] = arr[left + i];
for (let j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
let i = 0, j = 0;
let k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, left, right) {
if (left >= right)
return;
const mid = Math.floor(left + (right - left) / 2);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
This algorithm is relativly simple: it repeatedly divides the array into smaller arrays and searches for them. Merge Sort typically has O(n log(n)) complexity because it may repeat over elements a few times, but it’s still pretty good.
This was a short article about mathematics in programming. Get out there, geniuses, and start doing some math!