This work is licensed under a
Creative CommonsAttribution-ShareAlike 4.0 International License
Source: codeberg.org/andybalaam
Maths: the fun parts
Andy Balaam
element.io
element.io
This work is licensed under a
Creative CommonsMaths is:
Maths is:
Sets are groups of things
Throw out what you know from programming
Is x a member of A?
interface Set {
contains(element: any): boolean;
}
x is a member of A:
expect(A.contains(x)).toBe(true);
x is not a member of A:
expect(A.contains(x)).toBe(false);
x is a member of A:
x is not a member of A:
class Set123 extends Set {
contains(element: any): boolean {
return (
element === 1 ||
element === 2 ||
element === 3
);
}
}
const s = new Set123();
expect(s.contains(1)).toBe(true);
expect(s.contains(3)).toBe(true);
expect(s.contains(0)).toBe(false);
expect(s.contains(4)).toBe(false);
const s = new ArrSet(["X", "Y", "Z"]);
expect(s.contains("X")).toBe(true);
expect(s.contains("A")).toBe(false);
expect(s.contains(3)).toBe(false);
expect(s.contains(new EmptySet())).toBe(false);
class Intersection implements Set {
constructor(
private set1: Set,
private set2: Set,
) {}
contains(element: any): boolean {
return (
this.set1.contains(element) &&
this.set2.contains(element)
);
}
}
Intersection of A and B:
Intersection of A and B:
Intersection of A and B:
Intersection of A and B:
class Union implements Set {
constructor(
private set1: Set,
private set2: Set,
) {}
contains(element: any): boolean {
return (
this.set1.contains(element) ||
this.set2.contains(element)
);
}
}
Union of A and B:
Union of A and B:
Subsets
is_subset_of(other: Set): boolean {
for (const element of this) {
if (!other.contains(element)) {
return false;
}
}
return true;
}
Subsets
is_subset_of(other: Set): boolean {
for (const element of this) {
if (!other.contains(element)) {
return false;
}
}
return true;
}
Subsets
abstract class IterableSet implements Set, Iterable {
abstract contains(element: any): boolean;
abstract [Symbol.iterator](): Iterator;
is_subset_of(other: Set): boolean {
// ...
For all
A is a subset of B
Infinite sets
class Evens implements Set {
contains(element: any): boolean {
return (
typeof element === "number" &&
element % 2 === 0
);
}
}
All elements of this set?
class Evens implements Set {
*[Symbol.iterator](): Iterator {
yield 0;
let i = 1;
while (true) {
yield i * 2;
yield -i * 2;
i++;
}
}
}
Sets can contain sets
export class AllSets implements Set {
contains(element: any): boolean {
// We consider anything with a
// contains property to be a set!
return !!element.contains;
}
}
Sets can contain sets
const s = new AllSets();
expect(s.contains(new EmptySet())).toBe(true);
expect(s.contains(new Set123())).toBe(true);
expect(s.contains(3)).toBe(false);
AllSets is a member of itself
const s = new AllSets();
expect(s.contains(s)).toBe(true);
Algebra replaces numbers with variables
Algebra replaces numbers with variables
But what about the "+"?
We can replace that with a variable too
interface Group {
set(): Set;
op(left: any, right: any): any;
identity(): any;
}
A Group is:
Binary operation
class PlusMod5 extends Group {
...
op(left: any, right: any): any {
return (left + right) % 5;
}
...
}
Binary operation
const g = new PlusMod5();
expect(g.op(1, 2)).toBe(3);
expect(g.op(4, 3)).toBe(2);
Binary operation
PlusMod5
0, 1, 2, 3, 4
+(mod 5)
Rule 1: Closed
Rule 1: Closed
class PlusMod5 extends Group {
Rule 1: Closed
class PlusMod5 extends IterableGroup {
...
}
for (const x of g) {
Rule 1: Closed
for (const x of g) {
for (const y of g) {
const z = g.op(x, y);
expect(g.set().contains(z)).toBe(true);
}
}
PlusMod5 is closed
3 +(mod 5) 4 = 2
Rule 2: Identity
const idt = g.identity();
for (const x of g) {
expect(g.op(idt, x)).toEqual(x);
expect(g.op(x, idt)).toEqual(x);
}
Rule 2: Identity
Rule 2: Identity
PlusMod5 has an identity
2 +(mod 5) 0 = 2
0 +(mod 5) 2 = 2
Rule 3: Inverses
for (const x of g) {
expect(has_inverse(x, g).toBe(true);
}
Rule 3: Inverses
function has_inverse(e: any, g: Group): boolean {
for (const y of g) {
if (
g.op(e, y) === g.identity() &&
g.op(y, e) === g.identity()
) {
return true;
}
}
return false;
}
Rule 3: Inverses
PlusMod5 has inverses
2 +(mod 5) 3 = 0
4 +(mod 5) 1 = 0
Rule 4: Associative
PlusMod5 is associative
2 +5 (3 +5 1) = 1
(2 +5 3) +5 1 = 1
Optional: Commutative
PlusMod5 is commutative
1 +5 3 = 3 +5 1
A non-commutative group: D6
Things you can do to a triangle
A non-commutative group: D6
A non-commutative group: D6
rot120 + hflip = tlflip
A non-commutative group: D6
hflip + rot120 = trflip
A non-commutative group: Rubik's Cube Group
A non-commutative group: Rubik's Cube Group
Number of members:
43,252,003,274,489,856,000
Infinite groups:
The real numbers under multiplication
Famous groups:
Elliptic Curve group
Famous groups:
Elliptic Curve group
Dots and lines
Vertices and edges
interface FiniteGraph<V> {
vertices(): Array<V>;
edges(): Array<[V, V]>;
}
class K3 implements FiniteGraph<string> {
vertices(): Array<string> {
return ["a", "b", "c"];
}
edges(): Array<[string, string]> {
return [
["a", "b"],
["b", "c"],
["a", "c"],
];
}
}
Connected
Disconnected
function is_connected<T>(g: FiniteGraph<T>): boolean {
const found = [g.vertices()[0]];
for (const path of all_paths_from(g, g.vertices()[0])) {
for (const n of path) {
if (!found.includes(n)) {
found.push(n);
if (found.length === g.vertices().length) {
return true;
} } } }
return found.length === g.vertices().length;
}
Degree of a vertex
deg(v) = 4
Degree of a vertex
function degree<V>(v: V, g: FiniteGraph<V>): number {
let ret = 0;
for (const [from, to] of g.edges()) {
if (from === v || to === v) {
ret++;
}
}
return ret;
}
Eulerian circuit
Eulerian circuit
Eulerian circuit
Eulerian circuit
Eulerian circuit
Eulerian circuit
Eulerian circuit
Eulerian circuit
Eulerian circuit
Eulerian trail
(Obviously?)
Every time you enter, you leave again
(Obviously.)
Euler's Theorem (Carl Heirholzer)
Directed graphs
Secret Santa
Secret Santa
Secret Santa
Secret Santa
Secret Santa
Secret Santa
Directed graph of who can give to whom
Secret Santa
Directed graph of who can give to whom
Secret Santa
Secret Santa
This is called a Hamiltonian circuit
Santa Circles!
Finding Hamiltonian circuits in Rust
See my PR in petgraph[1]
Implementation is based on Frank Rubin's[2]
Rubin's algorithm to find Hamiltonian circuits
Rubin's algorithm to find Hamiltonian circuits
If one edge definitely leaves a vertex, no others do.
Rubin's algorithm to find Hamiltonian circuits
If two definite edges go to the same place, stop.
