Coincidentally, my algorithm learning journey which began in 2017 has occurred in parallel with the publication of Tim Roughgarden's (TR) 4-book series about algorithms and data structures. Over these years, I've purchased, studied, and provided feedback on TR's books. I was totally stoked when TR sent me a free copy of his 4th book for review before publication in 2020! I'm amazed by what can be done in near-linear time (ie. the amount of time to perform an algorithm is on the order of time to simply read the input), and it's awesome we can leverage these "for-free primitives" based upon computationally tractable problems as "building blocks" towards more complex solutions to computationally intractable (NP-Hard) problems via selective compromise on generality, correctness, and speed (ie. pick 2 of 3). 💡 Can we do better?
📚 Lectures
- MergeSort: Motivation and Example (Section 1.4, part 1)
- MergeSort: Pseudocode (Section 1.4, part 2)
- MergeSort: Analysis (Section 1.5)
🎯 Solutions
Kotlin
fun sort(A: IntArray): IntArray {
fun merge(A: IntArray, B: IntArray): IntArray {
var C = mutableListOf<Int>()
var i = 0
var j = 0
while (i < A.size && j < B.size)
if (A[i] < B[j])
C.add(A[i++])
else
C.add(B[j++])
A.slice(i..A.lastIndex).forEach { C.add(it) }
B.slice(j..B.lastIndex).forEach { C.add(it) }
return C.toIntArray()
}
fun go(A: IntArray): IntArray {
var N = A.size
if (N < 2)
return A
var half = Math.floor(N / 2.0).toInt()
var first = go(A.slice(0 until half).toIntArray())
var second = go(A.slice(half until N).toIntArray())
return merge(first, second)
}
return go(A)
}
fun main(args: Array<String>) {
sort(intArrayOf(5,3,8,9,1,7,0,2,6,4)).forEach { print("$it ") } // 0 1 2 3 4 5 6 7 8 9
println()
}Javascript
let sort = A => {
let go = A => {
let N = A.length;
if (N < 2)
return A;
let half = Math.floor(N / 2);
let first = go([...A.slice(0, half)]),
second = go([...A.slice(half, N)]);
return merge(first, second);
};
let merge = (A, B, C = []) => {
let M = A.length,
N = B.length;
let i = 0,
j = 0;
while (i < M && j < N)
C.push(A[i] < B[j] ? A[i++] : B[j++]);
C.push(...A.slice(i, M));
C.push(...B.slice(j, N));
return C;
};
return go(A);
};
console.log(sort([5,3,8,9,1,7,0,2,6,4])); // (10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]Python3
from math import floor
def sort(A):
def go(A):
N = len(A)
if N < 2:
return A
half = floor(N / 2)
first = go(A[:half])
second = go(A[half:])
return merge(first, second)
def merge(A, B):
C = []
i = 0
j = 0
while i < len(A) and j < len(B):
if A[i] < B[j]:
C.append(A[i]); i += 1
else:
C.append(B[j]); j += 1
C.extend(A[i:])
C.extend(B[j:])
return C
return go(A)
print(sort([5,3,8,9,1,7,0,2,6,4])) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]C++
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
using VI = vector<int>;
VI mergesort(VI& A) {
return go(move(A));
}
private:
VI go(VI&& A) {
auto N = A.size();
if( N < 2 )
return A;
auto half = A.begin() + (N / 2);
auto first = go({ A.begin(), half }),
second = go({ half, A.end() });
return merge(first, second);
}
VI merge(VI& A, VI& B, VI C = {}) {
auto i{ 0 },
j{ 0 };
while (i < A.size() && j < B.size())
C.push_back(A[i] < B[j] ? A[i++] : B[j++]);
C.insert(C.end(), A.begin() + i, A.end());
C.insert(C.end(), B.begin() + j, B.end());
return C;
}
};
int main() {
Solution::VI A{ 3,5,7,1,3,9,2,0 };
auto ans = Solution().mergesort(A);
copy(ans.begin(), ans.end(), ostream_iterator<int>(cout, " ")), cout << endl; // 0 1 2 3 4 5 6 7 8 9
return 0;
}📚 Lectures
- The Divide-and-Conquer Paradigm (Section 3.1; part 1 of Section 3.2)
- Counting Inversions in O(n log n) Time (Section 3.2, part 2)
🎯 Solutions
Kotlin
import java.io.File
fun sort(A: IntArray): Pair<IntArray, Long> {
fun merge(A: IntArray, B: IntArray): Pair<IntArray, Long> {
var C = mutableListOf<Int>()
var inv: Long = 0
var i = 0
var j = 0
while (i < A.size && j < B.size)
if (A[i] < B[j]) {
C.add(A[i++])
} else {
inv += A.size - i // ⭐️ B[j] comes before all remaining A[i...], thus all remaining A[i...] are inversions
C.add(B[j++])
}
A.slice(i..A.lastIndex).forEach { C.add(it) }
B.slice(j..B.lastIndex).forEach { C.add(it) }
return Pair(C.toIntArray(), inv)
}
fun go(A: IntArray): Pair<IntArray, Long> {
var N = A.size
if (N < 2)
return Pair(A, 0)
var half = Math.floor(N / 2.0).toInt()
var (first, inv1) = go(A.slice(0 until half).toIntArray())
var (second, inv2) = go(A.slice(half until N).toIntArray())
var (third, inv3) = merge(first, second)
return Pair(third, inv1 + inv2 + inv3)
}
return go(A)
}
fun run(filename: String): Long {
var A = mutableListOf<Int>()
File(filename).forEachLine { A.add(it.toInt()) }
var (_, inv) = sort(A.toIntArray())
return inv
}
fun main() {
println("problem3.5test.txt: " + run("problem3.5test.txt")) // problem3.5test.txt: 28
println("problem3.5.txt: " + run("problem3.5.txt")) // problem3.5.txt: 2407905288
}Javascript
let sort = A => {
let go = A => {
let N = A.length;
if (N < 2)
return [A, 0];
let half = Math.floor(N / 2);
let [first, inv1] = go([...A.slice(0, half)]),
[second, inv2] = go([...A.slice(half, N)]),
[third, inv3] = merge(first, second);
return [third, inv1 + inv2 + inv3];
};
let merge = (A, B, C = [], inv = 0) => {
let M = A.length,
N = B.length;
let i = 0,
j = 0;
while (i < M && j < N)
if (A[i] < B[j])
C.push(A[i++]);
else
inv += M - i, // ⭐️ B[j] comes before all remaining A[i...], thus all remaining A[i...] are inversions
C.push(B[j++]);
C.push(...A.slice(i, M));
C.push(...B.slice(j, N));
return [C, inv];
};
return go(A);
};
let run = filename => {
let A = [];
require('fs').readFileSync(filename, 'utf-8').split(/\r?\n/).forEach(line => A.push(Number(line)));
let [_, inv] = sort(A);
return inv;
}
console.log(`problem3.5test.txt: ${run('problem3.5test.txt')}`); // problem3.5test.txt: 28
console.log(`problem3.5.txt: ${run('problem3.5.txt')}`); // problem3.5.txt: 2407905288Python3
from math import floor
def sort(A):
def go(A):
N = len(A)
if N < 2:
return [A, 0]
half = floor(N / 2)
first, inv1 = go(A[:half])
second, inv2 = go(A[half:])
third, inv3 = merge(first, second)
return [third, inv1 + inv2 + inv3]
def merge(A, B, inv = 0):
C = []
i = 0
j = 0
while i < len(A) and j < len(B):
if A[i] < B[j]:
C.append(A[i]); i += 1
else:
inv += len(A) - i # ⭐️ B[j] comes before all remaining A[i...], thus all remaining A[i...] are inversions
C.append(B[j]); j += 1
C.extend(A[i:])
C.extend(B[j:])
return [C, inv]
return go(A)
def run(filename):
A = []
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
A.append(int(line))
_, inv = sort(A)
return inv
print(f"problem3.5test.txt: {run('problem3.5test.txt')}") # problem3.5test.txt: 28
print(f"problem3.5.txt: {run('problem3.5.txt')}") # problem3.5.txt: 2407905288C++
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
class Solution {
public:
using VL = vector<long>;
using Pair = pair<VL, long>;
using fun = function<Pair(VL&&)>;
Pair merge(VL& A, VL& B, VL C = {}, long inv = 0) {
auto i = 0,
j = 0;
while (i < A.size() && j < B.size()) {
if (A[i] < B[j]) {
C.push_back(A[i++]);
} else {
inv += A.size() - i; // ⭐️ B[j] comes before all remaining A[i...], thus all remaining A[i...] are inversions
C.push_back(B[j++]);
}
}
C.insert(C.end(), A.begin() + i, A.end());
C.insert(C.end(), B.begin() + j, B.end());
return { C, inv };
}
Pair inversions(VL& A) {
fun go = [&](VL&& A) -> Pair {
int N = A.size();
if (N < 2)
return { A, 0 };
int half = N / 2;
auto [first, inv1] = go({ A.begin(), A.begin() + half });
auto [second, inv2] = go({ A.begin() + half, A.end() });
auto [third, inv3] = merge(first, second);
return { third, inv1 + inv2 + inv3 };
};
return go(move(A));
}
};
long run(string filename) {
Solution solution;
Solution::VL A;
fstream fin{ filename };
for (string line; fin >> line; A.push_back(stol(line)));
auto [_, inv] = solution.inversions(A);
return inv;
}
int main() {
cout << "problem3.5test.txt: " << run("problem3.5test.txt") << endl // problem3.5test.txt: 28
<< "problem3.5.txt: " << run("problem3.5.txt") << endl; // problem3.5.txt: 2407905288
return 0;
}📚 Lectures
- QuickSort: Overview (Section 5.1)
- Partitioning Around a Pivot Element (Section 5.2)
- Choosing a Good Pivot (Sections 5.3 and 5.4)
- QuickSort Analysis (Part 1) (Section 5.5, part 1)
- QuickSort Analysis (Part 2) (Section 5.5, part 2)
- QuickSort Analysis (Part 3) (Section 5.5, part 3)
- Sorting Requires Omega(n log n) Comparisons (Section 5.6)
- Proofs by Induction and the Correctness of QuickSort (Appendix A)
- Quick Review of Discrete Probability (Appendix B)
🎯 Solutions
Kotlin
import java.io.File
typealias PivotFunc = (A: MutableList<Int>, L: Int, R: Int) -> (Int)
var pivotLeft: PivotFunc = { _: MutableList<Int>, L: Int, _: Int -> L }
var pivotRight: PivotFunc = { _: MutableList<Int>, _: Int, R: Int -> R }
fun _pivotMedian(A: MutableList<Int>, L: Int, R: Int): Int {
var M = L + (R - L) / 2
var cand = intArrayOf(A[L], A[M], A[R])
cand.sort()
var target = cand[1]
if (target == A[L]) return L
if (target == A[M]) return M
if (target == A[R]) return R
return -1
}
var pivotMedian: PivotFunc = { A: MutableList<Int>, L: Int, R: Int -> _pivotMedian(A, L, R) }
fun partition(A: MutableList<Int>, L: Int, R: Int, choosePivot: (A: MutableList<Int>, L: Int, R: Int) -> (Int)): Int {
var i = L + 1
var j = L + 1
var k = choosePivot(A, L, R)
A[k] = A[L].also { A[L] = A[k] } // swap pivot A[k] with first element of subarray A[L]
while (j <= R) {
if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j]
A[i] = A[j].also { A[j] = A[i] }
++i
}
++j
}
A[L] = A[i - 1].also { A[i - 1] = A[L] } // swap pivot A[L] with last value less-than pivot A[i - 1]
return i - 1
}
fun quicksort(A: MutableList<Int>, L: Int, R: Int, choosePivot: (A: MutableList<Int>, L: Int, R: Int) -> (Int)): Int {
if (R <= L)
return 0
var k = partition(A, L, R, choosePivot)
return (R - L) + quicksort(A, L, k - 1, choosePivot) + quicksort(A, k + 1, R, choosePivot)
}
fun run(filename: String, choosePivot: (A: MutableList<Int>, L: Int, R: Int) -> (Int)): Int {
var A = mutableListOf<Int>()
File(filename).forEachLine { A.add(it.toInt()) }
return quicksort(A, 0, A.size - 1, choosePivot)
}
fun main() {
var filename = "problem5.6.txt"
println(" left: ${run(filename, pivotLeft)}") // left: 162085
println(" right: ${run(filename, pivotRight)}") // right: 164123
println("median: ${run(filename, pivotMedian)}") // median: 138382
}Javascript
let pivotLeft = (A, L, R) => L;
let pivotRight = (A, L, R) => R;
let pivotMedian = (A, L, R) => {
let M = L + Math.floor((R - L) / 2);
let cand = [A[L], A[M], A[R]].sort((a, b) => a - b),
target = cand[1];
if (target == A[L]) return L;
if (target == A[M]) return M;
if (target == A[R]) return R;
};
let partition = (A, L, R, choosePivot) => {
let i = L + 1,
j = L + 1,
k = choosePivot(A, L, R);
[A[L], A[k]] = [A[k], A[L]]; // swap pivot A[k] with first element of subarray A[L]
while (j <= R) {
if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j]
[A[i], A[j]] = [A[j], A[i]];
++i;
}
++j;
}
[A[L], A[i - 1]] = [A[i - 1], A[L]]; // swap pivot A[L] with last value less-than pivot A[i - 1]
return i - 1;
};
let quicksort = (A, L, R, choosePivot) => {
if (R <= L)
return 0;
let k = partition(A, L, R, choosePivot);
return (R - L) + quicksort(A, L, k - 1, choosePivot)
+ quicksort(A, k + 1, R, choosePivot);
};
let run = (filename, choosePivot) => {
let A = [];
let LineByLine = require("n-readlines");
let input = new LineByLine(filename);
for (let line; line = input.next(); A.push(Number(line)));
return quicksort(A, 0, A.length - 1, choosePivot);
}
let filename = 'problem5.6.txt';
console.log(` left: ${run(filename, pivotLeft)}`); // left: 162085
console.log(` right: ${run(filename, pivotRight)}`); // right: 164123
console.log(`median: ${run(filename, pivotMedian)}`); // median: 138382Python3
def pivotLeft(A, L, R): return L
def pivotRight(A, L, R): return R
def pivotMedian(A, L, R):
M = L + (R - L) // 2
cand = sorted([A[L], A[M], A[R]])
target = cand[1]
if target == A[L]: return L
if target == A[M]: return M
if target == A[R]: return R
def partition(A, L, R, choosePivot):
i = L + 1
j = L + 1
k = choosePivot(A, L, R)
A[L], A[k] = A[k], A[L] # swap pivot A[k] with first element of subarray A[L]
while j <= R:
if A[j] < A[L]: # maintain loop invariant A[i] < pivot < A[j]
A[i], A[j] = A[j], A[i]
i += 1
j += 1
A[L], A[i - 1] = A[i - 1], A[L] # swap pivot A[L] with last value less-than pivot A[i - 1]
return i - 1
def quicksort(A, L, R, choosePivot):
if R <= L:
return 0
k = partition(A, L, R, choosePivot)
return (R - L) + quicksort(A, L, k - 1, choosePivot) + quicksort(A, k + 1, R, choosePivot)
def run(filename, choosePivot):
A = []
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
A.append(int(line))
return quicksort(A, 0, len(A) - 1, choosePivot)
filename = 'problem5.6.txt'
print(f' left: {run(filename, pivotLeft)}') # left: 162085
print(f' right: {run(filename, pivotRight)}') # right: 164123
print(f'median: {run(filename, pivotMedian)}') # median: 138382C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
using VI = vector<int>;
using fun = function<int(VI&, int, int)>;
fun pivotLeft = [](VI& A, int L, int R) { return L; };
fun pivotRight = [](VI& A, int L, int R) { return R; };
fun pivotMedian = [](VI& A, int L, int R) {
auto M = L + (R - L) / 2;
VI cand{ A[L], A[M], A[R] };
sort(cand.begin(), cand.end());
auto target = cand[1];
if (target == A[L]) return L;
if (target == A[M]) return M;
if (target == A[R]) return R;
};
int partition(VI& A, int L, int R, fun choosePivot) {
auto i = L + 1,
j = L + 1,
k = choosePivot(A, L, R);
swap(A[L], A[k]); // swap pivot A[k] with first element of the subarray A[L]
while (j <= R) {
if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j]
swap(A[i], A[j]);
++i;
}
++j;
}
swap(A[L], A[i - 1]); // swap pivot A[L] with last value less-than pivot A[i - 1]
return i - 1;
}
int quicksort(VI& A, int L, int R, fun choosePivot) {
if (R <= L)
return 0;
auto k = partition(A, L, R, choosePivot);
return (R - L) + quicksort(A, L, k - 1, choosePivot)
+ quicksort(A, k + 1, R, choosePivot);
}
int run(string& filename, fun choosePivot) {
VI A;
fstream fin{ filename };
for (string line; fin >> line; A.push_back(stoi(line)));
int N = A.size();
return quicksort(A, 0, N - 1, choosePivot);
}
int main() {
string filename{ "problem5.6.txt" };
cout << " left: " << run(filename, pivotLeft) << endl // left: 162085
<< " right: " << run(filename, pivotRight) << endl // right: 164123
<< "median: " << run(filename, pivotMedian) << endl; // median: 138382
return 0;
}📚 Lectures
- Randomized Linear-Time Selection (Section 6.1)
- Randomized Linear-Time Selection (Analysis) (Section 6.2)
🎯 Solutions
Kotlin
import java.io.File
import kotlin.random.Random
fun partition(A: MutableList<Int>, L: Int, R: Int): Int {
var i = L + 1
var j = L + 1
var k = Random.nextInt(L, R + 1) // +1 for L..R inclusive
A[L] = A[k].also { A[k] = A[L] } // swap pivot A[k] with first element of subarray A[L]
while (j <= R) {
if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j]
A[i] = A[j].also { A[j] = A[i] }
++i
}
++j
}
A[L] = A[i - 1].also { A[i - 1] = A[L] } // swap pivot A[L] with last value less-than pivot A[i - 1]
return i - 1
}
fun rselect(A: MutableList<Int>, i: Int, L_: Int, R_: Int): Int {
var L = L_
var R = R_
var k = partition(A, L, R)
if (i == k)
return A[k] // 🎯 lucky guess
if (i < k)
R = k - 1
else
L = k + 1
return rselect(A, i, L, R)
}
fun run(filename: String, i: Int): Int {
var A = mutableListOf<Int>()
File(filename).forEachLine { A.add(it.toInt()) }
var N = A.size
return rselect(A, i - 1, 0 , N - 1) // -1 for 0-based indexing
}
fun main() {
println("problem6.5test1.txt: " + run("problem6.5test1.txt", 5)) // problem6.5test1.txt: 5469
println("problem6.5test2.txt: " + run("problem6.5test2.txt", 50)) // problem6.5test2.txt: 4715
}Javascript
let random = (L, R) => Math.floor(Math.random() * (R + 1 - L) + L); // +1 for L..R inclusive
let partition = (A, L, R) => {
let i = L + 1,
j = L + 1,
k = random(L, R);
[A[L], A[k]] = [A[k], A[L]]; // swap pivot A[k] with first element of subarray A[L]
while (j <= R) {
if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j]
[A[i], A[j]] = [A[j], A[i]];
++i;
}
++j;
}
[A[L], A[i - 1]] = [A[i - 1], A[L]]; // swap pivot A[L] with last value less-than pivot A[i - 1]
return i - 1;
};
let rselect = (A, i, L, R) => {
let k = partition(A, L, R);
if (i == k)
return A[k]; // 🎯 lucky guess
if (i < k)
R = k - 1;
else
L = k + 1;
return rselect(A, i, L, R);
}
let run = (filename, i) => {
let A = [];
let LineByLine = require("n-readlines");
let input = new LineByLine(filename);
for (let line; line = input.next(); A.push(Number(line)));
let N = A.length;
return rselect(A, i - 1, 0, N - 1); // -1 for 0-based indexing
};
console.log(`problem6.5test1.txt: ${run('problem6.5test1.txt', 5)}`); // problem6.5test1.txt: 5469
console.log(`problem6.5test2.txt: ${run('problem6.5test2.txt', 50)}`); // problem6.5test2.txt: 4715Python3
from random import uniform
from math import floor
def partition(A, L, R):
i = L + 1
j = L + 1
k = floor(uniform(L, R))
A[L], A[k] = A[k], A[L] # swap pivot A[k] with first element of subarray A[L]
while j <= R:
if A[j] < A[L]: # maintain loop invariant A[i] < pivot < A[j]
A[i], A[j] = A[j], A[i]
i += 1
j += 1
A[L], A[i - 1] = A[i - 1], A[L] # swap pivot A[L] with last value less-than pivot A[i - 1]
return i - 1
def rselect(A, i, L, R):
k = partition(A, L, R)
if i == k:
return A[k] # 🎯 lucky guess
if i < k:
R = k - 1
else:
L = k + 1
return rselect(A, i, L, R)
def run(filename, i):
A = []
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
A.append(int(line))
N = len(A)
return rselect(A, i - 1, 0, N - 1) # -1 for 0-based indexing
print('problem6.5test1.txt:', run('problem6.5test1.txt', 5)) # problem6.5test1.txt: 5469
print('problem6.5test2.txt:', run('problem6.5test2.txt', 50)) # problem6.5test2.txt: 4715C++
#include <iostream>
#include <fstream>
#include <vector>
#include <random>
using namespace std;
using VI = vector<int>;
int random(int L, int R) {
random_device rd;
mt19937 gen{ rd() };
uniform_int_distribution dist(L, R);
return dist(gen);
}
int partition(VI& A, int L, int R) {
auto i = L + 1,
j = L + 1,
k = random(L, R);
swap(A[L], A[k]); // swap pivot A[k] with first element of the subarray A[L]
while (j <= R) {
if (A[j] < A[L]) // maintain loop invariant A[i] < pivot < A[j]
swap(A[i++], A[j]);
++j;
}
swap(A[L], A[i - 1]); // swap pivot A[L] with last value less-than pivot A[i - 1]
return i - 1;
}
int rselect(VI& A, int i, int L, int R) {
auto k = partition(A, L, R);
if (i == k)
return A[k]; // 🎯 lucky guess
if (i < k)
R = k - 1;
else
L = k + 1;
return rselect(A, i, L, R);
}
int run(string filename, int i, VI A = {}) {
fstream fin{ filename };
for (string line; fin >> line; A.push_back(stoi(line)));
int N = A.size();
return rselect(A, i - 1, 0, N - 1); // -1 for 0-based indexing
}
int main() {
cout << "problem6.5test1.txt: " << run("problem6.5test1.txt", 5) << endl; // problem6.5test1.txt: 5469
cout << "problem6.5test2.txt: " << run("problem6.5test2.txt", 50) << endl; // problem6.5test2.txt: 4715
return 0;
}
📚 Lectures
- Graphs: The Basics (from 2:06 to 6:39) (Sections 7.1 and 7.2)
- Graph Representations (Sections 7.3 and 7.4)
- Graph Search Overview (Section 8.1)
- Breadth-First Search (Section 8.2, Part 1)
- Depth-First Search (Section 8.4)
- Topological Sort (Section 8.5)
🎯 Solutions
Kotlin
import java.util.Queue
import java.util.LinkedList
class Solution(val adj: MutableMap<Char, List<Char>>) {
var N: Int
var color: Int
var m = mutableMapOf<Char, Int>()
var seen = mutableSetOf<Char>()
init {
N = adj.size
color = 0
}
fun init(start: Int) {
color = start
m.clear()
seen.clear()
}
fun topoSortBFS(): String {
init(1) // 👉 color forward from 1..N
bfs()
return toString()
}
fun topoSortDFS(): String {
init(N) // 👈 color reverse from N..1 (as the recursive stack unwinds)
adj.forEach{ (u, _) -> dfs(u) }
return toString()
}
fun bfs() {
var degree = mutableMapOf<Char, Int>()
adj.forEach{ (_, neighbors) ->
neighbors.forEach{ v ->
degree[v] = 1 + degree.getOrDefault(v, 0)
}
}
var q: Queue<Char> = LinkedList(adj.map{ (u, _) -> u }.filter{ !degree.contains(it) })
while (0 < q.size) {
var u = q.poll()
m[u] = color++
adj[u]!!.forEach{ v ->
degree[v] = degree[v]!!.minus(1)
if (degree[v] == 0 && !seen.contains(v)) {
q.add(v); seen.add(v)
}
}
}
}
fun dfs(u: Char) {
if (seen.contains(u))
return
seen.add(u)
adj[u]!!.forEach{ v ->
dfs(v)
}
m[u] = color--
}
override fun toString(): String {
var s = mutableListOf<String>()
adj.forEach{ (u, _) ->
s.add("$u: ${m[u]}")
}
return s.joinToString("\n")
}
}
fun main() {
var adj = mutableMapOf<Char, List<Char>>(
's' to listOf<Char>('v', 'w'),
'v' to listOf<Char>('t'),
'w' to listOf<Char>('t'),
't' to listOf<Char>()
)
var solution = Solution(adj)
println("BFS:\n${solution.topoSortBFS()}\n\nDFS:\n${solution.topoSortDFS()}")
// BFS:
// s: 1
// v: 2
// w: 3
// t: 4
// DFS:
// s: 1
// v: 3
// w: 2
// t: 4
}Javascript
class Solution {
constructor(adj) {
this.adj = adj;
this.N = this.adj.size;
}
init(start) {
this.color = start;
this.seen = new Set();
this.m = new Map();
}
topo_sort_bfs() {
this.init(1); // 👉 color forward from 1..N
this.bfs();
return this.to_string();
}
topo_sort_dfs() {
this.init(this.N); // 👈 color reverse from N..1 (as the recursive stack unwinds)
for (let [u, _] of [...this.adj])
this.dfs(u);
return this.to_string();
}
bfs() {
let degree = new Map();
for (let [u, _] of [...this.adj]) {
degree.set(u, (degree.get(u) || 0));
for (let v of this.adj.get(u))
degree.set(v, 1 + (degree.get(v) || 0));
}
let q = [...this.adj].map(([u, _]) => u).filter(u => !degree.get(u));
let seen = new Set(q);
while (q.length) {
let u = q.shift();
this.m.set(u, this.color++);
for (let v of this.adj.get(u)) {
degree.set(v, -1 + degree.get(v));
if (!degree.get(v) && !seen.has(v))
q.push(v), seen.add(v);
}
}
}
dfs(u) {
if (this.seen.has(u))
return;
this.seen.add(u);
for (let v of this.adj.get(u))
if (!this.seen.has(v))
this.dfs(v);
this.m.set(u, this.color--);
}
to_string() {
let s = [];
for (let [u, color] of [...this.m])
s.push(`${u}: ${color}`);
return s.join('\n');
}
}
let adj = new Map();
adj.set('s', ['v', 'w']);
adj.set('v', ['t']);
adj.set('w', ['t']);
adj.set('t', []);
let solution = new Solution(adj);
console.log(`BFS:\n${solution.topo_sort_bfs()}\n\nDFS:\n${solution.topo_sort_dfs()}`);
// BFS:
// s: 1
// v: 2
// w: 3
// t: 4
// DFS:
// t: 4
// v: 3
// w: 2
// s: 1Python3
from collections import deque
class Solution:
def __init__(self, adj):
self.adj = adj
self.N = len(adj)
self.seen = set()
self.m = {}
def init(self, start):
self.color = start
self.seen.clear()
self.m.clear()
def topo_sort_bfs(self):
self.init(1) # 👉 color forward from 1..N
self.bfs()
return self.to_string()
def topo_sort_dfs(self):
self.init(self.N) # 👈 color reverse from N..1 (as the recursive stack unwinds)
for u, _ in self.adj.items():
self.dfs(u)
return self.to_string()
def bfs(self):
degree = {}
for _, neighbors in self.adj.items():
for v in neighbors:
degree[v] = 1 + (degree[v] if v in degree else 0)
q = deque(u for u, _ in self.adj.items() if u not in degree)
self.seen.update(*q)
while q:
u = q.popleft()
self.m[u] = self.color; self.color += 1
for v in adj[u]:
degree[v] -= 1
if not degree[v] and v not in self.seen:
q.append(v); self.seen.add(v)
def dfs(self, u):
if u in self.seen:
return
self.seen.add(u)
for v in adj[u]:
self.dfs(v)
self.m[u] = self.color; self.color -= 1
def to_string(self):
s = []
for u, color in self.m.items():
s.append(f'{u}: {color}')
return '\n'.join(s)
#
# graph from Quiz 8.3 on page 45 of Algorithms Illuminated: Part 2
#
adj = {
's': ['v', 'w'],
'v': ['t'],
'w': ['t'],
't': []
}
solution = Solution(adj)
print(f'BFS:\n{solution.topo_sort_bfs()}\n\nDFS:\n{solution.topo_sort_dfs()}')
# BFS:
# s: 1
# v: 2
# w: 3
# t: 4
# DFS:
# t: 4
# v: 3
# w: 2
# s: 1C++
#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
using VI = vector<int>;
using AdjList = unordered_map<char, VI>;
using Set = unordered_set<char>;
using Map = unordered_map<char, int>;
using Queue = queue<char>;
using fun = function<void(char)>;
class Solution {
private:
AdjList adj;
const int N;
Map m;
Set seen;
int color;
public:
Solution(AdjList& adj) : adj{ adj }, N{ int(adj.size()) } {
}
void init(int start) {
m.clear();
seen.clear();
color = start;
}
string topo_sort_bfs() {
init(1); // 👉 color forward from 1..N
bfs();
return to_string();
}
string topo_sort_dfs() {
init(N); // 👈 color reverse from N..1 (as the recursive stack unwinds)
for (auto [u, _]: adj)
dfs(u);
return to_string();
}
void bfs() {
Map degree;
for (auto [_, neighbors]: adj)
for (auto v: neighbors)
++degree[v];
Queue q;
for (auto [u, _]: adj)
if (!degree[u] && seen.insert(u).second)
q.push(u);
while (q.size()) {
auto u = q.front(); q.pop();
m[u] = color++;
for (auto v: adj[u])
if (!--degree[v] && seen.insert(v).second)
q.push(v);
}
}
void dfs(char start) {
fun go = [&](auto u) {
if (!seen.insert(u).second)
return;
for (auto v: adj[u])
go(v);
m[u] = color--;
};
go(start);
}
string to_string() {
ostringstream os;
for (auto [u, color]: m)
os << u << ": " << color << endl;
return os.str();
}
};
int main() {
//
// graph from Quiz 8.3 on page 45 of Algorithms Illuminated: Part 2
//
AdjList adj{
{ 's', { 'v', 'w' } },
{ 'v', { 't' } },
{ 'w', { 't' } },
{ 't', {} }
};
Solution solution{ adj };
cout << "BFS:" << endl << solution.topo_sort_bfs() << endl
<< "DFS:" << endl << solution.topo_sort_dfs() << endl;
// BFS:
// t: 4
// w: 3
// v: 2
// s: 1
//
// DFS:
// s: 1
// w: 2
// v: 3
// t: 4
return 0;
}📚 Lectures
🎯 Solutions
Kotlin
import java.util.Stack
import java.io.File
class RecursiveSolution(var adj: MutableMap<Int, MutableList<Int>>, var rev: MutableMap<Int, MutableList<Int>>) {
fun topo_sort(): MutableList<Int> {
var list = mutableListOf<Int>()
var seen = mutableSetOf<Int>()
fun go(u: Int) {
if (seen.contains(u))
return
seen.add(u)
for (v in rev[u]!!)
go(v)
list.add(0, u)
}
for ((u, _) in rev)
go(u)
return list
}
fun kosaraju(): MutableList<List<Int>> {
var lists = mutableListOf<List<Int>>()
var seen = mutableSetOf<Int>()
fun go(u: Int, list: MutableList<Int>) {
if (seen.contains(u))
return
list.add(u); seen.add(u)
for (v in adj[u]!!)
go(v, list)
}
for (u in topo_sort()) {
if (seen.contains(u))
continue
var list = mutableListOf<Int>()
go(u, list)
lists.add(list.toList())
}
return lists
}
}
class IterativeSolution(var adj: MutableMap<Int, MutableList<Int>>, var rev: MutableMap<Int, MutableList<Int>>) {
fun topo_sort(): MutableList<Int> {
var list = mutableListOf<Int>()
var seen = mutableSetOf<Int>()
for ((u, _) in rev) {
if (seen.contains(u))
continue
var stack = Stack<Int>()
stack.push(u); seen.add(u)
while (!stack.empty()) {
var u = stack.last()
for (v in rev[u]!!) {
if (!seen.contains(v)) {
stack.push(v); seen.add(v)
}
}
if (u == stack.last())
list.add(0, stack.pop())
}
}
return list
}
fun kosaraju(): MutableList<List<Int>> {
var lists = mutableListOf<List<Int>>()
var seen = mutableSetOf<Int>()
for (u in topo_sort()) {
if (seen.contains(u))
continue
var list = mutableListOf<Int>()
var stack = Stack<Int>()
stack.push(u); seen.add(u)
while (!stack.empty()) {
var u = stack.last()
for (v in adj[u]!!) {
if (!seen.contains(v)) {
stack.push(v); seen.add(v)
}
}
if (u == stack.last())
list.add(stack.pop())
}
lists.add(list.toList())
}
return lists
}
}
fun run(filename: String) {
var adj = mutableMapOf<Int, MutableList<Int>>()
var rev = mutableMapOf<Int, MutableList<Int>>()
File(filename).forEachLine {
var (u, v) = it.trim().split(" ").map{ it.toInt() }
if (!adj.contains(u)) adj[u] = mutableListOf(); if (!adj.contains(v)) adj[v] = mutableListOf()
if (!rev.contains(u)) rev[u] = mutableListOf(); if (!rev.contains(v)) rev[v] = mutableListOf()
adj[u]!!.add(v)
rev[v]!!.add(u)
}
// var solution = RecursiveSolution(adj, rev)
var solution = IterativeSolution(adj, rev)
var A = solution.kosaraju()
A.sortWith(Comparator{ a: List<Int>, b: List<Int> -> b.size - a.size })
println(filename + ": " + A.map{ it.size }.slice(0 until Math.min(A.size, 5)).joinToString(" "))
}
fun main() {
run("section8.6.5page64.txt"); // Graph from section 8.6.5 on page 64 of Algorithms Illuminated: Part 2
run("problem8.10test1.txt"); // Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0
run("problem8.10test2.txt"); // Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0
run("problem8.10test3.txt"); // Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0
run("problem8.10test4.txt"); // Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0
run("problem8.10test5.txt"); // Test case #5: A 12-vertex 20-edge graph. Top 5 SCC sizes: 6,3,2,1,0
run("problem8.10.txt"); // Challenge data set: Vertices are labeled as positive integers from 1 to 875714
// section8.6.5page64.txt: 4 3 3 1
// problem8.10test1.txt: 3 3 3
// problem8.10test2.txt: 3 3 2
// problem8.10test3.txt: 3 3 1 1
// problem8.10test4.txt: 7 1
// problem8.10test5.txt: 6 3 2 1
// problem8.10.txt: 434821 968 459 313 211
}Javascript
class BaseSolution {
constructor(adj, rev) {
this.adj = adj;
this.rev = rev;
}
}
class RecursiveSolution extends BaseSolution {
constructor(adj, rev) {
super(adj, rev);
}
topo_sort() {
let list = [];
let seen = new Set();
let go = u => {
if (seen.has(u))
return;
seen.add(u);
for (let v of [...this.rev.get(u)])
go(v);
list.unshift(u);
};
for (let [u, _] of [...this.rev])
go(u);
return list;
}
kosaraju() {
let lists = [];
let seen = new Set();
let go = (u, list) => {
if (seen.has(u))
return;
seen.add(u);
list.push(u);
for (let v of [...this.adj.get(u)])
go(v, list);
};
for (let u of this.topo_sort()) {
let list = [];
go(u, list);
lists.push([...list]);
}
lists.sort((a, b) => b.length - a.length);
return lists;
}
}
class IterativeSolution extends BaseSolution {
constructor(adj, rev) {
super(adj, rev);
}
topo_sort() {
let list = [];
let seen = new Set();
for (let [u, _] of [...this.rev]) {
if (seen.has(u))
continue;
let stack = [ u ]; seen.add(u);
stack.back = () => stack[stack.length - 1];
while (stack.length) {
let u = stack.back();
for (let v of [...this.rev.get(u)])
if (!seen.has(v))
stack.push(v), seen.add(v);
if (u == stack.back())
list.unshift(stack.pop());
}
}
return list;
}
kosaraju() {
let lists = [];
let seen = new Set();
for (let u of this.topo_sort()) {
if (seen.has(u))
continue;
let list = [];
let stack = [ u ]; seen.add(u);
stack.back = () => stack[stack.length - 1];
while (stack.length) {
let u = stack.back();
for (let v of [...this.adj.get(u)])
if (!seen.has(v))
stack.push(v), seen.add(v);
if (u == stack.back())
list.push(stack.pop());
}
lists.push([...list]);
}
lists.sort((a, b) => b.length - a.length);
return lists;
}
}
let run = filename => {
let adj = new Map(),
rev = new Map();
let LineByLine = require('n-readlines');
let input = new LineByLine(filename);
let line;
while (line = input.next()) {
let [u, v] = String.fromCharCode(...line).split(' ').map(Number);
if (!adj.has(u)) adj.set(u, []); if (!adj.has(v)) adj.set(v, []);
if (!rev.has(u)) rev.set(u, []); if (!rev.has(v)) rev.set(v, []);
adj.get(u).push(v);
rev.get(v).push(u);
}
// let A = new RecursiveSolution(adj, rev).kosaraju();
let A = new IterativeSolution(adj, rev).kosaraju();
console.log(`${filename}: ${A.slice(0, Math.min(A.length, 5)).map(scc => scc.length).join(' ')}`);
};
run('section8.6.5page64.txt') // Graph from section 8.6.5 on page 64 of Algorithms Illuminated: Part 2
run('problem8.10test1.txt') // Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0
run('problem8.10test2.txt') // Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0
run('problem8.10test3.txt') // Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0
run('problem8.10test4.txt') // Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0
run('problem8.10test5.txt') // Test case #5: A 12-vertex 20-edge graph. Top 5 SCC sizes: 6,3,2,1,0
run('problem8.10.txt') // Challenge data set: Vertices are labeled as positive integers from 1 to 875714
// section8.6.5page64.txt: 4 3 3 1
// problem8.10test1.txt: 3 3 3
// problem8.10test2.txt: 3 3 2
// problem8.10test3.txt: 3 3 1 1
// problem8.10test4.txt: 7 1
// problem8.10test5.txt: 6 3 2 1
// problem8.10.txt: 434821 968 459 313 211Python3
from collections import deque
from functools import cmp_to_key
class BaseSolution:
def __init__(self, adj, rev):
self.adj = adj
self.rev = rev
class RecursiveSolution(BaseSolution):
def topo_sort(self):
list = deque()
seen = set()
def go(u):
if u in seen:
return
seen.add(u)
for v in self.rev[u]:
go(v)
list.appendleft(u)
for u in self.rev.keys():
go(u)
return list
def kosaraju(self):
lists = []
seen = set()
def go(u, list):
if u in seen:
return
seen.add(u)
list.append(u)
for v in self.adj[u]:
go(v, list)
for u in self.topo_sort():
list = []
go(u, list)
lists.append(list.copy())
lists.sort(key = cmp_to_key(lambda a, b: len(b) - len(a)))
return lists
class IterativeSolution(BaseSolution):
def topo_sort(self):
list = deque()
seen = set()
for u in self.rev.keys():
if u in seen:
continue
stack = [ u ]; seen.add(u)
while len(stack):
u = stack[-1]
for v in self.rev[u]:
if v not in seen:
stack.append(v); seen.add(v)
if u == stack[-1]:
list.appendleft(stack.pop())
return list
def kosaraju(self):
lists = []
seen = set()
for u in self.topo_sort():
if u in seen:
continue
list = deque()
stack = [ u ]; seen.add(u)
while len(stack):
u = stack[-1]
for v in self.adj[u]:
if v not in seen:
stack.append(v); seen.add(v)
if u == stack[-1]:
list.appendleft(stack.pop())
lists.append(list.copy())
lists.sort(key = cmp_to_key(lambda a, b: len(b) - len(a)))
return lists
def run(filename):
adj, rev = {}, {}
with open(filename) as fin:
while True:
line = fin.readline().strip()
if not line:
break
u, v = [int(x) for x in line.split()]
if u not in adj: adj[u] = []
if v not in adj: adj[v] = []
if u not in rev: rev[u] = []
if v not in rev: rev[v] = []
adj[u].append(v)
rev[v].append(u)
# solution = RecursiveSolution(adj, rev)
solution = IterativeSolution(adj, rev)
A = solution.kosaraju()
print(filename + ': ' + ' '.join(str(len(scc)) for scc in A[:5]))
run('section8.6.5page64.txt') # Graph from section 8.6.5 on page 64 of Algorithms Illuminated: Part 2
run('problem8.10test1.txt') # Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0
run('problem8.10test2.txt') # Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0
run('problem8.10test3.txt') # Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0
run('problem8.10test4.txt') # Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0
run('problem8.10test5.txt') # Test case #5: A 12-vertex 20-edge graph. Top 5 SCC sizes: 6,3,2,1,0
run('problem8.10.txt') # Challenge data set: Vertices are labeled as positive integers from 1 to 875714
# section8.6.5page64.txt: 4 3 3 1
# problem8.10test1.txt: 3 3 3
# problem8.10test2.txt: 3 3 2
# problem8.10test3.txt: 3 3 1 1
# problem8.10test4.txt: 7 1
# problem8.10test5.txt: 6 3 2 1
# problem8.10.txt: 434821 968 459 313 211C++
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
using List = deque<int>;
using Lists = deque<List>;
using AdjList = unordered_map<int, List>;
using Set = unordered_set<int>;
using Map = unordered_map<int, int>;
namespace Base {
class Solution {
protected:
AdjList adj, rev;
public:
Solution(AdjList& adj, AdjList& rev) : adj{ adj }, rev{ rev } {}
};
}
namespace Recursive {
struct Solution : public Base::Solution {
Solution(AdjList& adj, AdjList& rev) : Base::Solution{ adj, rev } {}
Lists kosaraju() {
Lists lists;
Set seen;
using fun = function<void(int, List&)>;
fun go = [&](auto u, auto& list) {
if (!seen.insert(u).second)
return;
list.push_back(u);
for (auto v: adj[u])
go(v, list);
};
for (auto u: topo_sort()) {
List list;
go(u, list);
lists.emplace_back(list);
}
sort(lists.begin(), lists.end(), [](auto& a, auto& b) { return b.size() < a.size(); });
return lists;
}
List topo_sort() {
List list;
Set seen;
using fun = function<void(int)>;
fun go = [&](auto u) {
if (!seen.insert(u).second)
return;
for (auto v: rev[u])
go(v);
list.push_front(u);
};
for (auto [u, _]: rev)
go(u);
return list;
}
};
}
namespace Iterative {
struct Solution : public Base::Solution {
Solution(AdjList& adj, AdjList& rev) : Base::Solution{ adj, rev } {}
Lists kosaraju() {
Lists lists;
Set seen;
for (auto u: topo_sort()) {
if (seen.find(u) != seen.end())
continue;
List list;
List stack{ u }; seen.insert(u);
while (stack.size()) {
auto u = stack.back();
for (auto v: adj[u])
if (seen.insert(v).second)
stack.push_back(v);
if (u == stack.back())
list.push_back(u), stack.pop_back();
}
lists.emplace_back(list);
}
sort(lists.begin(), lists.end(), [](auto& a, auto& b) { return b.size() < a.size(); });
return lists;
}
List topo_sort() {
List list;
Set seen;
for (auto [u, _]: rev) {
if (seen.find(u) != seen.end())
continue;
List stack{ u }; seen.insert(u);
while (stack.size()) {
auto u = stack.back();
for (auto v: rev[u])
if (seen.insert(v).second)
stack.push_back(v);
if (u == stack.back())
list.push_front(stack.back()), stack.pop_back();
}
}
return list;
}
};
}
void run(string filename) {
int u, v;
AdjList adj, rev;
fstream fin{ filename };
for (string line; fin >> u >> v;) {
adj[u].push_back(v);
rev[v].push_back(u);
}
auto A = Iterative::Solution{ adj, rev }.kosaraju();
A.resize(min(A.size(), size_t(5)));
cout << filename << ": ";
for (auto i{ 0 }; i < A.size(); cout << A[i++].size() << " ");
cout << endl;
}
int main() {
run("section8.6.5page64.txt"); // Graph from section 8.6.5 on page 64 of Algorithms Illuminated: Part 2
run("problem8.10test1.txt"); // Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0
run("problem8.10test2.txt"); // Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0
run("problem8.10test3.txt"); // Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0
run("problem8.10test4.txt"); // Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0
run("problem8.10test5.txt"); // Test case #5: A 12-vertex 20-edge graph. Top 5 SCC sizes: 6,3,2,1,0
run("problem8.10.txt"); // Challenge data set: Vertices are labeled as positive integers from 1 to 875714
// section8.6.5page64.txt: 4 3 3 1
// problem8.10test1.txt: 3 3 3
// problem8.10test2.txt: 3 3 2
// problem8.10test3.txt: 3 3 1 1
// problem8.10test4.txt: 7 1
// problem8.10test5.txt: 6 3 2 1
// problem8.10.txt: 434821 968 459 313 211
return 0;
}📚 Lectures
- Shortest Paths and Dijkstra's Algorithm (Sections 9.1 and 9.2, Part 1)
- Dijkstra's Algorithm: Examples (Section 9.2, Part 2)
- Correctness of Dijkstra's Algorithm (Section 9.3)
- Implementation and Running Time of Dijkstra's Algorithm (0:00-4:30) (Section 9.4)
- Data Structures Overview (Section 10.1)
- Heaps: Operations and Applications (Sections 10.2 and 10.3)
- Speeding Up Dijkstra's Algorithm With Heaps (4:30-26:27) (Section 10.4)
- Heaps: Implementation Details (Section 10.5)
🎯 Solutions
Kotlin
import java.io.File
import java.util.PriorityQueue
var INF = (1e9 + 7).toInt()
interface BaseSolution {
fun run(filename: String, queries: Array<Int>): String
}
class NaiveSolution : BaseSolution {
fun dijkstra(E: List<Triple<Int, Int, Int>>): MutableMap<Int, Int> {
var dist = mutableMapOf<Int, Int>()
var seen = mutableSetOf<Int>()
var start = 1
dist[start] = 0; seen.add(start)
var found: Boolean;
do {
found = false
var best_v = INF
var best_w = INF
for ((u, v, w) in E) {
if (!seen.contains(u) || seen.contains(v))
continue
found = true
if (best_w > dist[u]!! + w) {
best_v = v
best_w = dist[u]!! + w
}
}
var v = best_v
var w = best_w
dist[v] = w; seen.add(v)
} while (found)
return dist
}
override fun run(filename: String, queries: Array<Int>): String {
var E = mutableListOf<Triple<Int, Int, Int>>()
File(filename).forEachLine {
var words = it.trim().split("\t")
var u = words[0].toInt()
for (i in 1 until words.size) {
var (v, w) = words[i].split(",").map{ it.toInt() }
E.add(Triple(u, v, w))
}
}
var dist = dijkstra(E.toList())
return queries.map{ dist[it] }.joinToString(" ")
}
}
class HeapSolution : BaseSolution {
fun dijkstra(adj: MutableMap<Int, MutableList<Pair<Int, Int>>>): MutableMap<Int, Int> {
var dist = mutableMapOf<Int, Int>()
var seen = mutableSetOf<Int>()
var start = 1
dist[start] = 0
var q = PriorityQueue<Pair<Int, Int>>(Comparator{ a: Pair<Int, Int>, b: Pair<Int, Int> -> a.first.compareTo(b.first) })
q.add(Pair(0, start))
while (0 < q.size) {
var (cost, u) = q.poll()
if (seen.contains(u))
continue
dist[u] = cost; seen.add(u)
for ((w, v) in adj[u]!!) {
if (seen.contains(v))
continue
q.add(Pair(cost + w, v))
}
}
return dist
}
override fun run(filename: String, queries: Array<Int>): String {
var adj = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()
File(filename).forEachLine {
var words = it.trim().split("\t")
var u = words[0].toInt()
if (!adj.contains(u))
adj[u] = mutableListOf()
for (i in 1 until words.size) {
var (v, w) = words[i].split(",").map{ it.toInt() }
adj[u]!!.add(Pair(w, v))
}
}
var dist = dijkstra(adj)
return queries.map{ dist[it] }.joinToString(" ")
}
}
fun run(solution: BaseSolution) {
println(solution.run("problem9.8test.txt", arrayOf(1, 2, 3, 4, 5, 6, 7, 8)))
println(solution.run("problem9.8.txt", arrayOf(7, 37, 59, 82, 99, 115, 133, 165, 188, 197)))
}
fun main() {
run(NaiveSolution())
// 0 1 2 3 4 4 3 2
// 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068
run(HeapSolution())
// 0 1 2 3 4 4 3 2
// 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068
}Javascript
let LineByLine = require('n-readlines');
let INF = Number(1e9 + 7);
class NaiveSolution {
dijkstra(E) {
let dist = new Map();
let seen = new Set();
let start = 1;
dist[start] = 0; seen.add(start);
for (;;) {
let found = false;
let best_v = INF,
best_w = INF;
for (let [u, v, w] of E) {
if (!seen.has(u) || seen.has(v))
continue;
found = true;
if (best_w > dist[u] + w)
best_v = v,
best_w = dist[u] + w;
}
if (!found)
break;
let [v, w] = [best_v, best_w];
dist[v] = w; seen.add(v);
}
return dist;
}
run(filename, queries) {
let E = [];
let input = new LineByLine(filename);
let line;
while (line = input.next()) {
let words = String.fromCharCode(...line).trim().split(/\s+/);
let u = Number(words[0]);
for (let i = 1; i < words.length; ++i) {
let [v, w] = words[i].split(',').map(Number);
E.push([ u, v, w ]);
}
}
let dist = this.dijkstra(E);
return queries.map(x => dist[x]).join(' ');
}
}
let heapkey = x => Array.isArray(x) ? x[0] : x;
let heappush = (A, x, f = Math.min) => {
let P = i => Math.floor((i - 1) / 2); // parent
A.push(x);
let N = A.length,
i = N - 1;
while (0 < i && heapkey(A[i]) == f(heapkey(A[i]), heapkey(A[P(i)]))) {
[A[i], A[P(i)]] = [A[P(i)], A[i]];
i = P(i);
}
};
let heappop = (A, f = Math.min) => {
let L = i => 2 * i + 1, // children
R = i => 2 * i + 2;
let N = A.length,
i = 0;
let top = A[0];
[A[0], A[N - 1]] = [A[N - 1], A[0]], A.pop(), --N;
let ok = true;
do {
ok = true;
let left = f == Math.min ? Infinity : -Infinity,
right = left;
if (L(i) < N && heapkey(A[i]) != f(heapkey(A[i]), heapkey(A[L(i)]))) ok = false, left = heapkey(A[L(i)]);
if (R(i) < N && heapkey(A[i]) != f(heapkey(A[i]), heapkey(A[R(i)]))) ok = false, right = heapkey(A[R(i)]);
if (!ok) {
let j = left == f(left, right) ? L(i) : R(i);
[A[i], A[j]] = [A[j], A[i]];
i = j;
}
} while (!ok);
return top;
};
class HeapSolution {
dijkstra(adj) {
let dist = {};
let seen = new Set();
let start = 1;
let q = [[ 0, start ]];
while (q.length) {
let [cost, u] = heappop(q);
if (seen.has(u))
continue;
dist[u] = cost, seen.add(u);
for (let [w, v] of (adj[u] || []))
heappush(q, [ dist[u] + w, v ]);
}
return dist;
}
run(filename, queries) {
let adj = {};
let input = new LineByLine(filename);
let line;
while (line = input.next()) {
let words = String.fromCharCode(...line).trim().split('\t');
let u = Number(words[0]);
if (!(u in adj))
adj[u] = [];
for (let i = 1; i < words.length; ++i) {
let [v, w] = words[i].split(',').map(Number);
adj[u].push([ w, v ]);
}
}
let dist = this.dijkstra(adj);
return queries.map(x => dist[x]).join(' ');
}
}
let run = solution => {
console.log(solution.run('problem9.8test.txt', [1, 2, 3, 4, 5, 6, 7, 8]));
console.log(solution.run('problem9.8.txt', [7, 37, 59, 82, 99, 115, 133, 165, 188, 197]));
};
run(new NaiveSolution());
// 0 1 2 3 4 4 3 2
// 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068
run(new HeapSolution());
// 0 1 2 3 4 4 3 2
// 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068Python3
from abc import ABC, abstractmethod
from heapq import heappush, heappop
INF = int(1e9 + 7)
class BaseSolution(ABC):
@abstractmethod
def run(self, filename, queries):
raise NotImplementedError
class NaiveSolution(BaseSolution):
def dijkstra(self, E):
dist = {}
seen = set()
start = 1
dist[start] = 0; seen.add(start)
while True:
found = False
best_v = INF
best_w = INF
for u, v, w in E:
if u not in seen or v in seen:
continue
found = True
if best_w > dist[u] + w:
best_v = v
best_w = dist[u] + w
if not found:
break
v, w = best_v, best_w
dist[v] = w; seen.add(v)
return dist
def run(self, filename, queries):
E = []
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
words = line.split()
u = int(words[0])
for i in range(1, len(words)):
v, w = map(int, words[i].split(','))
E.append([ u, v, w ])
dist = self.dijkstra(E)
return ' '.join(str(dist[x]) for x in queries)
class HeapSolution(BaseSolution):
def dijkstra(self, adj, start = 1):
dist = {}
seen = set()
q = [[ 0, start ]]
while len(q):
cost, u = heappop(q)
if u in seen:
continue
dist[u] = cost; seen.add(u)
for w, v in adj[u]:
if v not in seen:
heappush(q, [ dist[u] + w, v ])
return dist
def run(self, filename, queries):
adj = {}
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
words = line.split()
u = int(words[0])
if u not in adj:
adj[u] = []
for i in range(1, len(words)):
v, w = map(int, words[i].split(','))
adj[u].append([ w, v ])
dist = self.dijkstra(adj)
return ' '.join(str(dist[x]) for x in queries)
def run(solution):
print(solution.run('problem9.8test.txt', [1, 2, 3, 4, 5, 6, 7, 8]))
print(solution.run('problem9.8.txt', [7, 37, 59, 82, 99, 115, 133, 165, 188, 197]))
run(NaiveSolution())
# 0 1 2 3 4 4 3 2
# 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068
run(HeapSolution())
# 0 1 2 3 4 4 3 2
# 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068C++
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
using Queries = vector<int>;
using Distance = unordered_map<int, int>;
using Set = unordered_set<int>;
class BaseSolution {
protected:
static constexpr auto INF = int(1e9 + 7);
public:
virtual string run(string filename, Queries&& queries) = 0;
};
class NaiveSolution : public BaseSolution {
using Edge = tuple<int, int, int>;
using Edges = vector<Edge>;
public:
Distance dijkstra(Edges& E) {
Distance dist;
Set seen;
auto start{ 1 };
dist[start] = 0, seen.insert(start);
for (;;) {
auto found = false;
auto best_v = INF,
best_w = INF;
for (auto [u, v, w]: E) {
if (seen.find(u) == seen.end() || seen.find(v) != seen.end())
continue;
found = true;
if (best_w > dist[u] + w)
best_v = v,
best_w = dist[u] + w;
}
if (!found)
break;
auto [v, w] = tie(best_v, best_w);
dist[v] = w, seen.insert(v);
}
return dist;
}
string run(string filename, Queries&& queries) {
Edges E;
fstream fin{ filename };
string line;
int u, v, w;
char _;
while (getline(fin, line)) {
istringstream is{ line };
for (is >> u; is >> v >> _ >> w; E.push_back({ u, v, w }));
}
auto dist = dijkstra(E);
ostringstream os;
transform(queries.begin(), queries.end(), ostream_iterator<int>(os, " "), [&](auto x) { return dist[x]; });
return os.str();
}
};
class HeapSolution : public BaseSolution {
using Pair = pair<int, int>;
using Pairs = vector<Pair>;
using AdjList = unordered_map<int, Pairs>;
priority_queue<Pair, Pairs, std::greater<Pair>> q;
public:
Distance dijkstra(AdjList& adj) {
Distance dist;
Set seen;
for (auto [u, _]: adj)
dist[u] = INF;
auto start{ 1 };
q.push({ 0, start });
while (q.size()) {
auto [cost, u] = q.top(); q.pop();
if (!seen.insert(u).second)
continue;
dist[u] = cost;
for (auto [w, v]: adj[u])
if (seen.find(v) == seen.end())
q.push({ dist[u] + w, v });
}
return dist;
}
string run(string filename, Queries&& queries) {
AdjList adj;
fstream fin{ filename };
string line;
int u, v, w;
char _;
while (getline(fin, line)) {
istringstream is{ line };
for (is >> u; is >> v >> _ >> w; adj[u].push_back({ w, v }));
}
auto dist = dijkstra(adj);
ostringstream os;
transform(queries.begin(), queries.end(), ostream_iterator<int>(os, " "), [&](auto x) { return dist[x]; });
return os.str();
}
};
void run(BaseSolution&& solution) {
cout << "problem9.8test.txt: " << solution.run("problem9.8test.txt", Queries{1, 2, 3, 4, 5, 6, 7, 8 }) << endl
<< "problem9.8.txt " << solution.run("problem9.8.txt", Queries{7, 37, 59, 82, 99, 115, 133, 165, 188, 197 }) << endl;
}
int main() {
run(NaiveSolution());
// problem9.8test.txt: 0 1 2 3 4 4 3 2
// problem9.8.txt 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068
run(HeapSolution());
// problem9.8test.txt: 0 1 2 3 4 4 3 2
// problem9.8.txt 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068
return 0;
}
📚 Lectures
- Introduction to Greedy Algorithms (Section 13.1)
- A Scheduling Problem (Section 13.2)
- Developing a Greedy Algorithm (Section 13.3)
- Scheduling: Correctness Proof (Part 1) (Section 13.4, Part 1)
- Scheduling: Correctness Proof (Part 2) (Section 13.4, Part 2)
- Scheduling: Correctness Proof (Part 3) (Section 13.4, Part 3)
🎯 Solutions
Kotlin
import java.io.File
data class Job(val weight: Long, val length: Long)
class Solution {
fun minSum(jobs: Array<Job>): Pair<Long, Long> {
class Diff: Comparator<Job> {
override fun compare(a: Job?, b: Job?): Int {
if (a == null || b == null)
return 0
var first = a.weight - a.length
var second = b.weight - b.length
return if (first == second) b.weight.compareTo(a.weight) else second.compareTo(first) // sort by descending difference, break ties in favor of jobs with larger weights
}
}
class Ratio: Comparator<Job> {
override fun compare(a: Job?, b: Job?): Int {
if (a == null || b == null)
return 0
var first = a.weight.toDouble() / a.length
var second = b.weight.toDouble() / b.length
return if (first == second) b.weight.compareTo(a.weight) else second.compareTo(first) // sort by descending difference, break ties in favor of jobs with larger weights
}
}
return Pair(calcSum(jobs, Diff()), calcSum(jobs, Ratio()))
}
private fun calcSum(jobs: Array<Job>, comp: Comparator<Job>): Long {
jobs.sortWith(comp)
var time: Long = 0
var total: Long = 0
jobs.forEach { job ->
time += job.length
total += job.weight * time
}
return total
}
}
fun run(filename: String) {
var jobs = mutableListOf<Job>()
var first = true
File(filename).forEachLine {
if (!first) {
var words = it.trim().split(" ").map{ it.toLong() }
var (weight, length) = words
jobs.add(Job(weight, length))
} else {
first = false
}
}
var (diff, ratio) = Solution().minSum(jobs.toTypedArray())
println("$diff, $ratio") // sub-optimal, optimal
}
fun main() {
run("problem13.4test1.txt") // 23, 22
run("problem13.4test2.txt") // 68615, 67247
run("problem13.4.txt") // 69119377652, 67311454237
}Javascript
let LineByLine = require('n-readlines');
class Job {
constructor(weight, length) {
this.weight = weight;
this.length = length;
}
}
class Solution {
minSum(jobs) {
let diff = (a, b) => {
let first = a.weight - a.length,
second = b.weight - b.length;
return first == second ? b.weight - a.weight : second - first; // sort by descending difference, break ties in favor of jobs with larger weights
};
let ratio = (a, b) => {
let first = a.weight / a.length,
second = b.weight / b.length;
return first == second ? b.weight - a.weight : second - first; // sort by descending ratio, break ties in favor of jobs with larger weights
};
return [ this._calcSum(jobs, diff), this._calcSum(jobs, ratio) ];
}
_calcSum(jobs, comp, time = 0) {
jobs.sort((a, b) => comp(a, b));
return jobs.reduce((total, job) => total + job.weight * (time += job.length), 0);
}
}
let run = filename => {
let jobs = [];
let input = new LineByLine(filename);
let line = input.next(); // N
while (line = input.next()) {
let words = String.fromCharCode(...line).trim().split(' ');
let [weight, length] = words.map(Number);
jobs.push(new Job(weight, length));
}
let [diff, ratio] = new Solution().minSum(jobs);
console.log(`${diff}, ${ratio}`); // sub-optimal, optimal
};
run('problem13.4test1.txt'); // 23, 22
run('problem13.4test2.txt'); // 68615, 67247
run('problem13.4.txt'); // 69119377652, 67311454237Python3
from functools import cmp_to_key
class Job:
def __init__(self, weight, length):
self.weight = weight
self.length = length
class Solution:
def minSum(self, jobs):
def diff(a, b):
first = a.weight - a.length
second = b.weight - b.length
return b.weight - a.weight if first == second else second - first # sort by descending difference, break ties in favor of jobs with larger weights
def ratio(a, b):
first = a.weight / a.length
second = b.weight / b.length
return b.weight - a.weight if first == second else second - first # sort by descending difference, break ties in favor of jobs with larger weights
return [ self._calcSum(jobs, diff), self._calcSum(jobs, ratio) ]
def _calcSum(self, jobs, comp, time = 0, total = 0):
jobs.sort(key = cmp_to_key(lambda a, b: comp(a, b)))
for job in jobs:
time += job.length
total += job.weight * time
return total
def run(filename):
jobs = []
with open(filename) as fin:
line = fin.readline() # N
while True:
line = fin.readline().strip()
if not line:
break
words = line.split()
weight, length = [int(x) for x in words]
jobs.append(Job(weight, length))
diff, ratio = Solution().minSum(jobs)
print(f'{diff}, {ratio}') # sub-optimal, optimal
run('problem13.4test1.txt') # 23, 22
run('problem13.4test2.txt') # 68615, 67247
run('problem13.4.txt') # 69119377652, 67311454237C++
#include <iostream>
#include <fstream>
#include <vector>
#include <numeric>
using namespace std;
using LL = long long;
struct Job {
LL weight, length;
Job(LL weight, LL length) : weight{ weight }, length{ length } {}
};
using Jobs = vector<Job>;
class Solution {
public:
using Pair = pair<LL, LL>; // sub-optimal, optimal
Pair minSum(Jobs& jobs) {
auto diff = [](auto& a, auto& b) {
auto first = a.weight - a.length,
second = b.weight - b.length;
return first == second ? b.weight < a.weight : second < first; // sort by descending difference, break ties in favor of jobs with larger weights
};
auto ratio = [](auto& a, auto& b) {
auto first = double(a.weight) / a.length,
second = double(b.weight) / b.length;
return first == second ? b.weight < a.weight : second < first; // sort by descending ratio, break ties in favor of jobs with larger weights
};
return { calcSum(jobs, diff), calcSum(jobs, ratio) };
}
private:
template<typename Comp>
LL calcSum(Jobs& jobs, Comp comp, LL time = 0LL) {
sort(jobs.begin(), jobs.end(), comp);
return accumulate(jobs.begin(), jobs.end(), 0LL, [&](LL total, auto& job) {
return total += job.weight * (time += job.length);
});
}
};
void run(const string& filename) {
Jobs jobs;
LL N, weight, length;
fstream fin{ filename };
for (fin >> N; fin >> weight >> length; jobs.emplace_back(Job{ weight, length }));
auto [diff, ratio] = Solution().minSum(jobs);
cout << diff << ", " << ratio << endl;
}
int main() {
run("problem13.4test1.txt"); // 23, 22
run("problem13.4test2.txt"); // 68615, 67247
run("problem13.4.txt"); // 69119377652, 67311454237
return 0;
}📚 Lectures
- Codes (Section 14.1)
- Codes as Trees (Section 14.2)
- Huffman's Greedy Algorithm (Part 1) (Section 14.3, Part 1)
- Huffman's Greedy Algorithm (Part 2) (Section 14.3, Part 2)
- Huffman's Algorithm: Correctness Proof (Part 1) (Section 14.4, Part 1)
- Huffman's Algorithm: Correctness Proof (Part 2) (Section 14.4, Part 2)
🎯 Solutions
Kotlin
import java.io.File
import java.util.PriorityQueue
import java.util.Queue
import java.util.LinkedList
var INF = (1e9 + 7).toInt()
data class Tree(val weight: Int, val left: Tree? = null, val right: Tree? = null)
/*
fun encode(A: List<Int>): Tree {
var q = PriorityQueue<Tree>(Comparator{ a: Tree, b: Tree -> a.weight.compareTo(b.weight) })
for (weight in A)
q.add(Tree(weight))
while (1 < q.size) {
var a = q.poll()
var b = q.poll()
var c = Tree(a.weight + b.weight, a, b)
q.add(c)
}
return q.poll()
}
*/
/*
* Problem 14.5: Give an implementation of Huffman's greedy algorithm that uses a single invocation
* of a sorting subroutine, followed by a linear amount of additional work.
*/
fun encode(A: MutableList<Int>): Tree {
A.sort()
var first: Queue<Tree> = LinkedList<Tree>(A.map{ weight -> Tree(weight) }.toList())
var second: Queue<Tree> = LinkedList<Tree>()
var next = mutableListOf<Tree>()
while (1 < first.size + second.size) {
next.clear()
do {
if (0 < first.size && 0 < second.size) {
if (first.peek().weight < second.peek().weight) next.add(first.poll()) else next.add(second.poll())
}
else if (0 < first.size) next.add(first.poll())
else if (0 < second.size) next.add(second.poll())
} while (next.size < 2)
var (a, b) = next
var c = Tree(a.weight + b.weight, a, b)
second.add(c)
}
return second.poll()
}
fun run(filename: String): Pair<Int, Int> {
var A = mutableListOf<Int>()
var first = true
File(filename).forEachLine {
if (!first) {
var weight = it.trim().toInt()
A.add(weight)
} else {
first = false
}
}
var tree = encode(A.toMutableList())
var lo = INF
var hi = -INF
fun go(root: Tree? = tree, depth: Int = 0) {
if (root == null)
return
var isLeaf = { node: Tree? -> node?.left == null && node?.right == null }
if (isLeaf(root)) {
lo = Math.min(lo, depth)
hi = Math.max(hi, depth)
} else {
go(root.left, depth + 1)
go(root.right, depth + 1)
}
}
go()
return Pair(lo, hi)
}
fun main() {
for (filename in listOf("problem14.6test1.txt", "problem14.6test2.txt", "problem14.6.txt")) {
var (lo, hi) = run(filename)
println("$filename: $lo, $hi") // min, max encoding length in the corresponding optimal prefix-free tree
}
}
// problem14.6test1.txt: 2, 5
// problem14.6test2.txt: 3, 6
// problem14.6.txt: 9, 19Javascript
let LineByLine = require('n-readlines');
class Tree {
constructor(weight, left = null, right = null) {
this.weight = weight;
this.left = left;
this.right = right;
}
}
/*
let key = x => Array.isArray(x) ? x[0] : x;
let heappush = (A, x, f = Math.min) => {
let P = i => Math.floor((i - 1) / 2); // parent
A.push(x);
let N = A.length,
i = N - 1;
while (0 < i && key(A[i]) == f(key(A[i]), key(A[P(i)]))) {
[A[i], A[P(i)]] = [A[P(i)], A[i]];
i = P(i);
}
};
let heappop = (A, f = Math.min) => {
let L = i => 2 * i + 1, // children
R = i => 2 * i + 2;
let N = A.length,
i = 0;
let top = A[0];
[A[0], A[N - 1]] = [A[N - 1], A[0]], A.pop(), --N;
let ok;
do {
ok = true;
let left = f == Math.min ? Infinity : -Infinity,
right = left;
if (L(i) < N && key(A[i]) != f(key(A[i]), key(A[L(i)]))) ok = false, left = key(A[L(i)]);
if (R(i) < N && key(A[i]) != f(key(A[i]), key(A[R(i)]))) ok = false, right = key(A[R(i)]);
if (!ok) {
let j = left == f(left, right) ? L(i) : R(i);
[A[i], A[j]] = [A[j], A[i]];
i = j;
}
} while (!ok);
return top;
};
let encode = A => {
let T = [];
for (let weight of A)
heappush(T, [ weight, new Tree(weight) ]);
while (1 < T.length) {
let [ a, b ] = [ heappop(T), heappop(T) ];
let c = [ a[0] + b[0], new Tree(a[0] + b[0], a[1], b[1]) ];
heappush(T, c);
}
return T[0][1];
};
*/
/*
* Problem 14.5: Give an implementation of Huffman's greedy algorithm that uses a single invocation
* of a sorting subroutine, followed by a linear amount of additional work.
*/
let encode = A => {
A.sort((a, b) => a - b)
let first = A.map(weight => new Tree(weight)),
second = [];
while (1 < first.length + second.length) {
let next = [];
while (next.length < 2) {
if (first.length && second.length) {
next.push(first[0].weight < second[0].weight ? first.shift() : second.shift());
}
else if (first.length) next.push(first.shift());
else if (second.length) next.push(second.shift());
}
let [a, b] = next;
let c = new Tree(a.weight + b.weight, a, b);
second.push(c);
}
return second.shift();
};
let run = filename => {
let A = [];
let input = new LineByLine(filename);
let line;
line = input.next(); // N
while (line = input.next()) {
let weight = Number(String.fromCharCode(...line).trim());
A.push(weight);
}
let tree = encode(A);
let [lo, hi] = [Infinity, -Infinity];
let go = (root = tree, depth = 0) => {
if (!root)
return;
let isLeaf = root => !root.left && !root.right;
if (isLeaf(root))
lo = Math.min(lo, depth),
hi = Math.max(hi, depth);
else
go(root.left, depth + 1),
go(root.right, depth + 1);
};
go();
return [ lo, hi ];
}
for (let filename of [ 'problem14.6test1.txt', 'problem14.6test2.txt', 'problem14.6.txt' ]) {
let [lo, hi] = run(filename);
console.log(`${filename}: ${lo}, ${hi}`); // min, max encoding length in the corresponding optimal prefix-free tree
}
// problem14.6test1.txt: 2, 5
// problem14.6test2.txt: 3, 6
// problem14.6.txt: 9, 19Python3
class Tree:
def __init__(self, weight, left = None, right = None):
self.weight = weight
self.left = left
self.right = right
def __lt__(self, other):
return self.weight < other.weight
#
# priority queue
#
# from heapq import heappush
# from heapq import heappop
# def encode(A):
# T = []
# for weight in A:
# heappush(T, Tree(weight))
# while 1 < len(T):
# a, b = heappop(T), heappop(T)
# c = Tree(a.weight + b.weight, a, b)
# heappush(T, c)
# return heappop(T)
#
# Problem 14.5: Give an implementation of Huffman's greedy algorithm that uses a single invocation
# of a sorting subroutine, followed by a linear amount of additional work.
#
from collections import deque
def encode(A):
A.sort()
first, second = deque([Tree(weight) for weight in A]), deque()
while 1 < len(first) + len(second):
next = []
while len(next) < 2:
if len(first) and len(second):
next.append(first.popleft() if first[0].weight < second[0].weight else second.popleft())
elif len(first): next.append(first.popleft())
elif len(second): next.append(second.popleft())
a, b = next
c = Tree(a.weight + b.weight, a, b)
second.append(c)
return second.popleft()
def run(filename):
A = []
with open(filename) as fin:
N = int(fin.readline())
while True:
line = fin.readline()
if not line:
break
weight = int(line.strip())
A.append(weight)
tree = encode(A)
lo, hi = float('inf'), float('-inf')
def go(root = tree, depth = 0):
nonlocal lo, hi
if not root:
return
isLeaf = lambda root: not root.left and not root.right
if isLeaf(root):
lo = min(lo, depth)
hi = max(hi, depth)
else:
go(root.left, depth + 1)
go(root.right, depth + 1)
go()
return [ lo, hi ]
for filename in [ 'problem14.6test1.txt', 'problem14.6test2.txt', 'problem14.6.txt' ]:
lo, hi = run(filename)
print(f'{filename}: {lo}, {hi}') # min, max encoding length in the corresponding optimal prefix-free tree
# problem14.6test1.txt: 2, 5
# problem14.6test2.txt: 3, 6
# problem14.6.txt: 9, 19C++
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#define PRIORITY_QUEUE // O(N * logN)
#ifndef PRIORITY_QUEUE
#define TWO_QUEUES // O(N)
#endif
using namespace std;
using LL = long long;
using Weight = LL;
using Weights = vector<Weight>;
struct Tree;
using TreePtr = shared_ptr<Tree>;
struct Tree {
Weight weight;
TreePtr left, right;
Tree(Weight weight, TreePtr left = nullptr, TreePtr right = nullptr) :
weight{ weight }, left{ left }, right{ right } {}
};
using TreePtrs = vector<TreePtr>;
#ifdef PRIORITY_QUEUE
struct Comp {
size_t operator()(const TreePtr& a, const TreePtr& b) const {
return b->weight < a->weight;
}
};
using Queue = priority_queue<TreePtr, TreePtrs, Comp>;
TreePtr encode(const Weights& A, Queue q = {}) {
for (auto weight: A)
q.emplace(make_shared<Tree>(weight));
while (1 < q.size()) {
auto a = q.top(); q.pop();
auto b = q.top(); q.pop();
auto c = make_shared<Tree>(a->weight + b->weight, a, b);
q.emplace(c);
}
return q.top();
}
#else // TWO_QUEUES
/*
* Problem 14.5: Give an implementation of Huffman's greedy algorithm that uses a single invocation
* of a sorting subroutine, followed by a linear amount of additional work.
*/
using Queue = queue<TreePtr>;
TreePtr encode(Weights& A, Queue first = {}, Queue second = {}) {
sort(A.begin(), A.end());
for (auto weight: A)
first.push(make_shared<Tree>(weight));
TreePtrs next;
auto takeFirst = [&]() { next.push_back(first.front()), first.pop(); };
auto takeSecond = [&]() { next.push_back(second.front()), second.pop(); };
while (1 < first.size() + second.size()) {
next.clear();
do {
if (first.size() && second.size()) {
if (first.front()->weight < second.front()->weight) takeFirst(); else takeSecond();
}
else if (first.size()) takeFirst();
else if (second.size()) takeSecond();
} while (next.size() < 2);
auto [a, b] = tie(next[0], next[1]);
auto c = make_shared<Tree>(a->weight + b->weight, a, b);
second.emplace(c);
}
return second.front();
}
#endif
using MinMax = pair<LL, LL>;
constexpr auto Min = numeric_limits<LL>::min();
constexpr auto Max = numeric_limits<LL>::max();
MinMax run(const string& filename) {
Weights A; // weight of each symbol
fstream fin{ filename };
LL N, weight;
for (fin >> N; fin >> weight; A.push_back(weight));
auto tree = encode(A);
LL lo = Max,
hi = Min;
using fun = function<void(TreePtr, int)>;
fun go = [&](auto root, LL depth) {
if (!root)
return;
auto isLeaf = [](auto root) { return !root->left && !root->right; };
if (isLeaf(root))
lo = min(lo, depth),
hi = max(hi, depth);
else
go(root->left, depth + 1),
go(root->right, depth + 1);
};
go(tree, 0);
return make_pair(lo, hi);
}
int main() {
for (auto& filename: { "problem14.6test1.txt", "problem14.6test2.txt", "problem14.6.txt" }) {
auto [lo, hi] = run(filename);
cout << filename << ": " << lo << ", " << hi << endl; // min, max encoding length in the corresponding optimal prefix-free tree
}
// problem14.6test1.txt: 2, 5
// problem14.6test2.txt: 3, 6
// problem14.6.txt: 9, 19
return 0;
}📚 Lectures
- Minimum Spanning Trees: Problem Definition (Section 15.1)
- Prim's MST Algorithm (Section 15.2)
- Speeding Up Prim's Algorithm via Heaps (Part 1) (Section 15.3, Part 1)
- Speeding Up Prim's Algorithm via Heaps (Part 2) (Section 15.3, Part 2)
- Prim's Algorithm: Correctness Proof (Part 1) (Section 15.4, Part 1) [Note: this video provides an alternative treatment to that in the book.]
- Prim's Algorithm: Correctness Proof (Part 2) (Section 15.4, Part 2) [Note: this video provides an alternative treatment to that in the book.]
🎯 Solutions
Kotlin
import java.io.File
import java.util.PriorityQueue
import java.util.Random
fun prim(N: Int, adj: MutableMap<Int, MutableList<Pair<Int, Int>>>): Int {
var total: Int = 0
var start = Random().nextInt(N) + 1
var q = PriorityQueue<Pair<Int, Int>>(Comparator{ a: Pair<Int, Int>, b: Pair<Int, Int> -> a.first.compareTo(b.first) })
var seen = mutableSetOf<Int>(start)
for ((w, v) in adj[start]!!)
q.add(Pair(w, v))
while (0 < q.size) {
var (cost, u) = q.poll()
if (seen.contains(u))
continue
total += cost; seen.add(u)
for ((w, v) in adj[u]!!)
if (!seen.contains(v))
q.add(Pair(w, v))
}
return total
}
fun run(filename: String) {
var N: Int = 0
var adj = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()
var first = true
File(filename).forEachLine { line ->
if (!first) {
var (u, v, w) = line.split(" ").map{ it.toInt() }
if (!adj.contains(u)) adj[u] = mutableListOf<Pair<Int, Int>>()
if (!adj.contains(v)) adj[v] = mutableListOf<Pair<Int, Int>>()
adj[u]!!.add(Pair(w, v))
adj[v]!!.add(Pair(w, u))
} else {
var (numVertex, _) = line.split(" ").map{ it.toInt() }
N = numVertex
first = false
}
}
var cost = prim(N, adj)
println("$filename: $cost")
}
fun main() {
run("problem15.9test.txt") // problem15.9test.txt: 14
run("problem15.9.txt") // problem15.9.txt: -3612829
}Javascript
let LineByLine = require('n-readlines');
let key = x => Array.isArray(x) ? x[0] : x;
let heappush = (A, x, f = Math.min) => {
let P = i => Math.floor((i - 1) / 2); // parent
A.push(x);
let N = A.length,
i = N - 1;
while (0 < i && key(A[i]) == f(key(A[i]), key(A[P(i)]))) {
[A[i], A[P(i)]] = [A[P(i)], A[i]];
i = P(i);
}
};
let heappop = (A, f = Math.min) => {
let L = i => 2 * i + 1, // children
R = i => 2 * i + 2;
let N = A.length,
i = 0;
let top = A[0];
[A[0], A[N - 1]] = [A[N - 1], A[0]], A.pop(), --N;
let ok;
do {
ok = true;
let left = f == Math.min ? Infinity : -Infinity,
right = left;
if (L(i) < N && key(A[i]) != f(key(A[i]), key(A[L(i)]))) ok = false, left = key(A[L(i)]);
if (R(i) < N && key(A[i]) != f(key(A[i]), key(A[R(i)]))) ok = false, right = key(A[R(i)]);
if (!ok) {
let j = left == f(left, right) ? L(i) : R(i);
[A[i], A[j]] = [A[j], A[i]];
i = j;
}
} while (!ok);
return top;
};
let prim = (N, adj, q = [], seen = new Set(), total = 0) => {
let start = Math.ceil(N * Math.random());
seen.add(start);
for (let [w, v] of adj.get(start))
heappush(q, [w, v]);
while (q.length) {
let [cost, u] = heappop(q);
if (seen.has(u))
continue;
total += cost; seen.add(u);
for (let [w, v] of adj.get(u))
if (!seen.has(v))
heappush(q, [w, v]);
}
return total;
};
let run = filename => {
let adj = new Map();
let input = new LineByLine(filename);
let line = input.next();
let [N, M] = String.fromCharCode(...line).trim().split(' ').map(Number);
while (line = input.next()) {
let [u, v, w] = String.fromCharCode(...line).trim().split(' ').map(Number);
if (!adj.has(u)) adj.set(u, []);
if (!adj.has(v)) adj.set(v, []);
adj.get(u).push([w, v]);
adj.get(v).push([w, u]);
}
let cost = prim(N, adj);
console.log(`${filename}: ${cost}`);
}
run('problem15.9test.txt') // problem15.9test.txt: 14
run('problem15.9.txt') // problem15.9.txt: -3612829Python3
from random import randint
from heapq import heappush, heappop
def prim(N, adj, total = 0):
q = []
seen = set()
start = randint(1, N); seen.add(start)
for w, v in adj[start]:
heappush(q, [w, v])
while q:
cost, u = heappop(q)
if u in seen:
continue
total += cost; seen.add(u)
for w, v in adj[u]:
if v not in seen:
heappush(q, [w, v])
return total
def run(filename):
adj = {}
first = True
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
words = line.split()
if not first:
u, v, w = [int(x) for x in words]
if u not in adj: adj[u] = []
if v not in adj: adj[v] = []
adj[u].append([w, v])
adj[v].append([w, u])
else:
N, M = [int(x) for x in words]
first = False
cost = prim(N, adj)
print(f'{filename}: {cost}')
run('problem15.9test.txt') # problem15.9test.txt: 14
run('problem15.9.txt') # problem15.9.txt: -3612829C++
#include <iostream>
#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <random>
using namespace std;
using Pair = pair<int, int>;
using Pairs = vector<Pair>;
using AdjList = unordered_map<int, Pairs>;
using Queue = priority_queue<Pair, Pairs, std::greater<Pair>>;
using Set = unordered_set<int>;
constexpr auto INF = int(1e9 + 7);
int getRandom(int N) {
default_random_engine generator;
uniform_int_distribution<int> distribution(1, N);
return distribution(generator);
}
int prim(int N, AdjList& adj, Queue q = {}, Set seen = {}, int total = 0) {
auto start = getRandom(N);
seen.insert(start);
for (auto [w, v]: adj[start])
q.push({ w, v });
while (q.size()) {
auto [cost, u] = q.top(); q.pop();
if (!seen.insert(u).second)
continue;
total += cost;
for (auto [w, v]: adj[u])
if (seen.find(v) == seen.end())
q.push({ w, v });
}
return total;
}
void run(const string& filename) {
AdjList adj;
fstream fin{ filename };
int N, M; fin >> N >> M; // N vertices and M edges
int u, v, w; // edge u -> v of weight w
while (fin >> u >> v >> w) {
adj[u].emplace_back(w, v);
adj[v].emplace_back(w, u);
}
auto cost = prim(N, adj);
cout << filename << ": " << cost << endl;
}
int main() {
run("problem15.9test.txt"); // problem15.9test.txt: 14
run("problem15.9.txt"); // problem15.9.txt: -3612829
return 0;
}📚 Lectures
- Minimum Spanning Trees: Problem Definition (Section 15.1)
- Kruskal's MST Algorithm (Section 15.5)
- Speeding Up Kruskal's Algorithm via Union-Find (Part 1) (Section 15.6, Part 1)
- Speeding Up Kruskal's Algorithm via Union-Find (Part 2) (Section 15.6, Part 2) [Note: this video provides an alternative treatment to that in the book.]
- Lazy Unions (Section 15.6, Part 3) [Note: this video is closer to the union-find implementation in the book.]
- Kruskal's Algorithm: Correctness Proof (Section 15.7) [Note: this video provides an alternative treatment to that in the book.]
- Application: Single-Link Clustering (Section 15.8)
🎯 Solutions
Kotlin
import java.io.File
fun kruskal(E: MutableList<Triple<Int, Int, Int>>): Int {
var total: Int = 0
var M = E.size
var P = IntArray(M) { it } // 🙂 parent representatives of 1..M disjoint sets
fun find(x: Int): Int {
P[x] = if (P[x] == x) x else find(P[x])
return P[x]
}
fun union(a: Int, b: Int): Boolean {
var x = find(a)
var y = find(b)
if (x == y)
return false
P[x] = y // 🎲 arbitrary choice
return true
}
E.sortWith(Comparator{ a, b -> a.third.compareTo(b.third) }) // sort edges by nondecreasing weight
for ((u, v, w) in E)
if (union(u, v))
total += w
return total
}
fun run(filename: String) {
var E = mutableListOf<Triple<Int, Int, Int>>()
var first = true
File(filename).forEachLine { line ->
if (!first) {
var (u, v, w) = line.trim().split(" ").map{ it.toInt() }
E.add(Triple(u, v, w))
} else {
first = false // ignore first line with N vertices and M edges
}
}
var cost = kruskal(E)
println("$filename: $cost")
}
fun main() {
run("problem15.9test.txt") // problem15.9test.txt: 14
run("problem15.9.txt") // problem15.9.txt: -3612829
}Javascipt
let LineByLine = require('n-readlines');
let kruskal = E => {
let total = 0;
let M = E.length;
let P = [...Array(M).keys()]; // 🙂 parent representatives of 1..M disjoint sets
let find = x => P[x] = P[x] == x ? x : find(P[x]);
let union = (a, b) => {
a = find(a);
b = find(b);
if (a == b)
return false;
P[a] = b; // 🎲 arbitrary choice
return true;
};
E.sort((first, second) => { // sort edges by nondecreasing weight
let [u1, v1, w1] = first,
[u2, v2, w2] = second;
return w1 - w2;
});
for (let [u, v, w] of E)
if (union(u, v))
total += w;
return total;
};
let run = filename => {
let E = [];
let input = new LineByLine(filename);
let line = input.next(); // ignore first line with N vertices and M edges
while (line = input.next()) {
let [u, v, w] = String.fromCharCode(...line).trim().split(' ').map(Number);
E.push([ u, v, w ]);
}
let cost = kruskal(E);
console.log(`${filename}: ${cost}`);
};
run('problem15.9test.txt'); // problem15.9test.txt: 14
run('problem15.9.txt'); // problem15.9.txt: -3612829Python3
from functools import cmp_to_key
def kruskal(E, total = 0):
M = len(E)
P = [i for i in range(M)] # 🙂 parent representatives of 1..M disjoint sets
def find(x):
P[x] = P[x] if P[x] == x else find(P[x])
return P[x]
def union(a, b):
a = find(a)
b = find(b)
if a == b:
return False
P[a] = b # 🎲 arbitary choice
return True
E.sort(key = cmp_to_key(lambda first, second: first[2] - second[2])) # sort edges by nondecreasing weight
for u, v, w in E:
if union(u, v):
total += w
return total
def run(filename):
E = []
first = True
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
values = [int(x) for x in line.strip().split()]
if not first:
u, v, w = values # edge u -> v of weight w
E.append([ u, v, w ])
else:
first = False # ignore first line with N vertices and M edges
cost = kruskal(E)
print(f'{filename}: {cost}')
run('problem15.9test.txt') # problem15.9test.txt: 14
run('problem15.9.txt') # problem15.9.txt: -3612829C++
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <numeric>
using namespace std;
using Edge = tuple<int, int, int>;
using Edges = vector<Edge>;
using Parents = vector<int>;
using fun = function<int(int)>;
int kruskal(Edges& E, int total = 0) {
auto M = E.size();
Parents P(M); iota(P.begin(), P.end(), 0); // 🙂 parent representatives of 1..M disjoint sets
fun find = [&](auto x) {
return P[x] = P[x] == x ? x : find(P[x]);
};
auto join = [&](auto a, auto b) {
a = find(a);
b = find(b);
if (a == b)
return false;
P[a] = b; // 🎲 arbitrary choice
return true;
};
sort(E.begin(), E.end(), [](auto& first, auto& second) { // sort edges by nondecreasing weight
auto [u1, v1, w1] = first;
auto [u2, v2, w2] = second;
return w1 < w2;
});
for (auto [u, v, w]: E)
if (join(u, v))
total += w;
return total;
}
void run(const string& filename, Edges E = {}) {
fstream fin{ filename };
int N, M; fin >> N >> M; // ignore first line with N vertices and M edges
int u, v, w; // edge u -> v of weight w
while (fin >> u >> v >> w)
E.emplace_back(u, v, w);
auto cost = kruskal(E);
cout << filename << ": " << cost << endl;
}
int main() {
run("problem15.9test.txt"); // problem15.9test.txt: 14
run("problem15.9.txt"); // problem15.9.txt: -3612829
return 0;
}📚 Lectures
🎯 Solutions
Kotlin
import java.io.File
fun topDown(A: MutableList<Long>): Long {
var N = A.size
var m = mutableMapOf<Int, Long>()
fun go(i: Int = N - 1): Long {
if (m.contains(i)) // 🤔 memo
return m[i]!!
if (i < 0) { // 🛑 empty set
m[i] = 0
return 0
}
if (i == 0) { // 🛑 single set
m[i] = A[0]
return A[0]
}
var include = go(i - 2) + A[i] // ✅ include A[i]
var exclude = go(i - 1) // 🚫 exclude A[i]
m[i] = Math.max(include, exclude) // 🎯 best
return m[i]!!
}
return go()
}
fun bottomUp(A: MutableList<Long>): Long {
var N = A.size
var dp = LongArray(N + 1) // 🤔 memo
dp[0] = 0 // 🛑 empty set
dp[1] = A[0] // 🛑 single set
for (i in 2..N) {
var include = dp[i - 2] + A[i - 1] // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist)
var exclude = dp[i - 1] // 🚫 exclude A[i]
dp[i] = Math.max(include, exclude) // 🎯 best
}
return dp[N]
}
fun bottomUpMemOpt(A: MutableList<Long>): Long {
var N = A.size
var a: Long = 0 // 🤔 memo + 🛑 empty set
var b: Long = A[0] // 🤔 memo + 🛑 single set
var c: Long = -1
for (i in 2..N) {
var include = a + A[i - 1] // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist)
var exclude = b // 🚫 exclude A[i]
c = Math.max(include, exclude) // 🎯 best
a = b; b = c // 👈 slide window
}
return c
}
fun run(filename: String) {
var A = mutableListOf<Long>()
var first = true
File(filename).forEachLine { line ->
if (!first) {
A.add(line.toLong())
} else {
first = false
}
}
var a = topDown(A)
var b = bottomUp(A)
var c = bottomUpMemOpt(A)
assert(a == b && b == c) // 💩 sanity check
println("$filename: $a")
}
fun main() {
run("problem16.6test.txt") // problem16.6test.txt: 2617
run("problem16.6.txt") // problem16.6.txt: 2955353732
}Javascript
const assert = require('assert');
const LineByLine = require('n-readlines');
let top_down = (A, m = {}) => {
let N = A.length;
let go = (i = N - 1) => {
if (m[i]) // 🤔 memo
return m[i];
if (i < 0) return m[i] = 0; // 🛑 empty set
if (!i) return m[i] = A[0]; // 🛑 single set
let include = go(i - 2) + A[i], // ✅ include A[i]
exclude = go(i - 1); // 🚫 exclude A[i]
return m[i] = Math.max(include, exclude); // 🎯 best
};
return go();
};
let bottom_up = A => {
let N = A.length;
let dp = Array(N + 1); // 🤔 memo
dp[0] = 0; // 🛑 empty set
dp[1] = A[0]; // 🛑 single set
for (let i = 2; i <= N; ++i) {
let include = dp[i - 2] + A[i - 1], // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist)
exclude = dp[i - 1]; // 🚫 exclude A[i]
dp[i] = Math.max(include, exclude); // 🎯 best
}
return dp[N];
};
let bottom_up_memopt = A => {
let N = A.length;
let a = 0, // 🤔 memo + 🛑 empty set
b = A[0], // 🤔 memo + 🛑 single set
c = -1;
for (let i = 2; i <= N; ++i) {
let include = a + A[i - 1], // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist)
exclude = b; // 🚫 exclude A[i]
c = Math.max(include, exclude); // 🎯 best
a = b, b = c; // 👈 slide window
}
return c;
};
let run = filename => {
let A = [];
let input = new LineByLine(filename);
let line;
let first = true;
while (line = input.next()) {
if (!first) {
A.push(Number(line.toString('ascii')));
} else {
first = false;
}
}
let a = top_down(A),
b = bottom_up(A),
c = bottom_up_memopt(A);
assert(a == b && b == c); // 💩 sanity check
console.log(`${filename}: ${a}`);
};
run('problem16.6test.txt'); // problem16.6test.txt: 2617
run('problem16.6.txt'); // problem16.6.txt: 2955353732Python3
from functools import lru_cache
def top_down(A):
N = len(A)
@lru_cache # 🤔 memo
def go(i = N - 1):
if i < 0: return 0 # 🛑 empty set
if i == 0: return A[0] # 🛑 single set
include = go(i - 2) + A[i] # ✅ include A[i]
exclude = go(i - 1) # 🚫 exclude A[i]
return max(include, exclude) # 🎯 best
return go()
def bottom_up(A):
N = len(A)
dp = [0] * (N + 1) # 🤔 memo
dp[0] = 0 # 🛑 empty set
dp[1] = A[0] # 🛑 single set
for i in range(2, N + 1):
include = dp[i - 2] + A[i - 1] # ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist)
exclude = dp[i - 1] # 🚫 exclude A[i]
dp[i] = max(include, exclude) # 🎯 best
return dp[N]
def bottom_up_memopt(A):
N = len(A)
a = 0 # 🤔 memo + 🛑 empty set
b = A[0] # 🤔 memo + 🛑 single set
c = -1
for i in range(2, N + 1):
include = a + A[i - 1] # ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist)
exclude = b # 🚫 exclude A[i]
c = max(include, exclude) # 🎯 best
a = b; b = c # 👈 slide window
return c
def run(filename):
A = []
with open(filename) as fin:
first = True
while True:
line = fin.readline()
if not line:
break
x = int(line)
if not first:
A.append(x)
else:
first = False
N = x
a = top_down(A)
b = bottom_up(A)
c = bottom_up_memopt(A)
assert(a == b and b == c) # 💩 sanity check
print(f'{filename}: {a}')
run('problem16.6test.txt') # problem16.6test.txt: 2617
run('problem16.6.txt') # problem16.6.txt: 2955353732C++
#include <cassert>
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;
using LL = long long;
using List = vector<LL>;
using Map = unordered_map<int, LL>;
namespace TopDown {
LL best(List& A, Map m = {}) {
int N = A.size();
using fun = function<LL(int)>;
fun go = [&](auto i) {
if (m[i]) return m[i]; // 🤔 memo
if (i < 0) return m[i] = 0LL; // 🛑 empty set
if (!i) return m[i] = A[0]; // 🛑 single set
auto include = go(i - 2) + A[i], // ✅ include A[i]
exclude = go(i - 1); // 🚫 exclude A[i]
return m[i] = max(include, exclude); // 🎯 best
};
return go(N - 1);
}
}
namespace BottomUp {
LL best(List& A, Map m = {}) {
int N = A.size();
List dp(N + 1); // 🤔 memo
dp[0] = 0LL; // 🛑 empty set
dp[1] = A[0]; // 🛑 single set
for (auto i{ 2 }; i <= N; ++i) {
auto include = dp[i - 2] + A[i - 1], // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist)
exclude = dp[i - 1]; // 🚫 exclude A[i]
dp[i] = max(include, exclude); // 🎯 best
}
return dp[N];
}
}
namespace BottomUpMemOpt {
LL best(List& A) {
int N = A.size();
LL a = 0LL, // 🤔 memo + 🛑 empty set
b = A[0], // 🤔 memo + 🛑 single set
c = -1;
for (auto i{ 2 }; i <= N; ++i) {
auto include = a + A[i - 1], // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist)
exclude = b; // 🚫 exclude A[i]
c = max(include, exclude); // 🎯 best
a = b, b = c; // 👈 slide window
}
return c;
}
}
void run(const string& filename) {
List A;
fstream fin{ filename };
int N; fin >> N;
copy_n(istream_iterator<LL>(fin), N, back_inserter(A));
auto a = TopDown::best(A),
b = BottomUp::best(A),
c = BottomUpMemOpt::best(A);
assert(a == b && b == c); // 💩 sanity check
cout << filename << ": " << a << endl;
}
int main() {
run("problem16.6test.txt"); // problem16.6test.txt: 2617
run("problem16.6.txt"); // problem16.6.txt: 2955353732
return 0;
}📚 Lectures
🎯 Solutions
Kotlin
import java.io.File
var INF = (1e9 + 7).toInt()
fun top_down(A: List<Pair<Int, Int>>, K: Int): Int {
var N = A.size
var m = mutableMapOf<String, Int>()
fun go(i: Int = 0, k: Int = K): Int {
if (i == N) // 🛑 empty set
return 0
var key = "$i,$k"
if (m.contains(key)) // 🤔 memo
return m[key]!!
var (value, weight) = A[i]
var include = if (0 <= k - weight) go(i + 1, k - weight) + value else -INF // ✅ include A[i]
var exclude = go(i + 1, k) // 🚫 exclude A[i]
m[key] = Math.max(include, exclude) // 🎯 best
return m[key]!!
}
return go()
}
fun bottom_up(A: List<Pair<Int, Int>>, K: Int): Int {
var N = A.size
var dp = Array(N + 1){ Array(K + 1){ -INF } } // 🤔 memo
for (k in 0..K) // 🛑 empty set
dp[0][k] = 0
for (i in 1..N) {
for (k in 0..K) {
var (value, weight) = A[i - 1]
var include = if (0 <= k - weight) dp[i - 1][k - weight] + value else -INF // ✅ include A[i]
var exclude = dp[i - 1][k] // 🚫 exclude A[i]
dp[i][k] = Math.max(include, exclude) // 🎯 best
}
}
return dp[N][K]
}
fun bottom_up_memopt(A: List<Pair<Int, Int>>, K: Int): Int {
var N = A.size
var pre = Array(K + 1) { 0 } // 🤔 memo + 🛑 empty set
for (i in 1..N) {
var cur = Array(K + 1) { -INF }
for (k in 0..K) {
var (value, weight) = A[i - 1]
var include = if (0 <= k - weight) pre[k - weight] + value else -INF // ✅ include A[i]
var exclude = pre[k] // 🚫 exclude A[i]
cur[k] = Math.max(include, exclude) // 🎯 best
}
pre = cur.also { cur = pre }
}
return pre[K]
}
fun run(filename: String) {
var A = mutableListOf<Pair<Int, Int>>()
var K = 0
var N = 0
var first = true
File(filename).forEachLine { line ->
if (!first) {
var (value, weight) = line.trim().split(" ").map{ it -> it.toInt() }
A.add(Pair(value, weight))
} else {
var (a, b) = line.trim().split(" ").map{ it -> it.toInt() }
K = a
N = b
first = false
}
}
var a = top_down(A, K)
var b = bottom_up(A, K)
var c = bottom_up_memopt(A, K)
assert(a == b && b == c) // 💩 sanity check
println("$filename: $a")
}
fun main() {
run("problem16.7test.txt") // problem16.7test.txt: 2493893
}Javascript
const assert = require('assert');
const LineByLine = require('n-readlines');
let top_down = (A, K, m = new Map()) => {
let N = A.length;
let go = (i = 0, k = K) => {
if (i == N) // 🛑 empty set
return 0;
let key = `${i},${k}`;
if (m.has(key)) // 🤔 memo
return m.get(key);
let [value, weight] = A[i];
let include = 0 <= k - weight ? go(i + 1, k - weight) + value : -Infinity, // ✅ include A[i]
exclude = go(i + 1, k); // 🚫 exclude A[i]
return m.set(key, Math.max(include, exclude)) // 🎯 best
.get(key);
};
return go();
};
let bottom_up = (A, K) => {
let N = A.length;
let dp = [...Array(N + 1)].map(_ => Array(K + 1).fill(-Infinity)); // 🤔 memo
for (let k = 0; k < K; dp[0][k++] = 0); // 🛑 empty set
for (let i = 1; i <= N; ++i) {
for (let k = 0; k <= K; ++k) {
let [value, weight] = A[i - 1];
let include = 0 <= k - weight ? dp[i - 1][k - weight] + value : -Infinity, // ✅ include A[i]
exclude = dp[i - 1][k]; // 🚫 exclude A[i]
dp[i][k] = Math.max(include, exclude); // 🎯 best
}
}
return dp[N][K];
};
let bottom_up_memopt = (A, K) => {
let N = A.length;
let pre = Array(K + 1).fill(0); // 🤔 memo + 🛑 empty set
for (let i = 1; i <= N; ++i) {
let cur = Array(K + 1).fill(-Infinity);
for (let k = 0; k <= K; ++k) {
let [value, weight] = A[i - 1];
let include = 0 <= k - weight ? pre[k - weight] + value : -Infinity, // ✅ include A[i]
exclude = pre[k]; // 🚫 exclude A[i]
cur[k] = Math.max(include, exclude); // 🎯 best
}
[pre, cur] = [cur, pre];
}
return pre[K];
};
let run = filename => {
let A = [];
const input = new LineByLine(filename)
let [K, N] = input.next().toString().split(' ').map(Number); // K capacity, N items
let line;
while (line = input.next()) {
let [value, weight] = line.toString().split(' ').map(Number);
A.push([value, weight]);
}
let a = top_down(A, K),
b = bottom_up(A, K),
c = bottom_up_memopt(A, K);
assert(a == b && b == c); // 💩 sanity check
console.log(`${filename}: ${a}`);
};
run('problem16.7test.txt') // problem16.7test.txt: 2493893Python3
from functools import lru_cache
def top_down(A, K):
N = len(A)
total = [0] * N
@lru_cache(maxsize = None) # 🤔 memo
def go(i = 0, k = K):
if i == N: # 🛑 empty set
return 0
value, weight = A[i]
include = go(i + 1, k - weight) + value if 0 <= k - weight else float('-inf') # ✅ include A[i]
exclude = go(i + 1, k) # 🚫 exclude A[i]
return max(include, exclude) # 🎯 best
return go()
def bottom_up(A, K):
N = len(A)
dp = [[float('-inf')] * (K + 1) for _ in range(N + 1)] # 🤔 memo
for j in range(K): # 🛑 empty set
dp[0][j] = 0
for i in range(1, N + 1):
for k in range(1, K + 1):
value, weight = A[i - 1]
include = dp[i - 1][k - weight] + value if 0 <= k - weight else float('-inf') # ✅ include A[i]
exclude = dp[i - 1][k] # 🚫 exclude A[i]
dp[i][k] = max(include, exclude) # 🎯 best
return dp[N][K]
def bottom_up_memopt(A, K):
N = len(A)
pre = [0] * (K + 1) # 🤔 memo + 🛑 empty set
for i in range(1, N + 1):
cur = [float('-inf')] * (K + 1)
for k in range(1, K + 1):
value, weight = A[i - 1]
include = pre[k - weight] + value if 0 <= k - weight else float('-inf') # ✅ include A[i]
exclude = pre[k] # 🚫 exclude A[i]
cur[k] = max(include, exclude) # 🎯 best
pre, cur = cur, pre
return pre[K]
def run(filename):
A = []
with open(filename) as fin:
line = fin.readline()
[K, N] = [int(word) for word in line.split()] # K capacity, N items
while True:
line = fin.readline()
if not line:
break
value, weight = [int(word) for word in line.split()]
A.append([value, weight])
a = top_down(A, K)
b = bottom_up(A, K)
c = bottom_up_memopt(A, K)
assert(a == b and b == c) # 💩 sanity check
print(f'{filename}: {a}')
run('problem16.7test.txt') # problem16.7test.txt: 2493893C++
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <unordered_map>
using namespace std;
using Pair = pair<int, int>; // value, weight
using Pairs = vector<Pair>;
using fun = function<int(int, int)>;
using Map = unordered_map<string, int>;
int INF = 1e9 + 7;
int top_down(Pairs& A, int K, Map m = {}) {
auto N = A.size();
fun go = [&](auto i, auto k) {
if (i == N) // 🛑 empty set
return 0;
stringstream key; key << i << "," << k;
if (m.find(key.str()) != m.end()) // 🤔 memo
return m[key.str()];
auto [value, weight] = A[i];
auto include = 0 <= k - weight ? go(i + 1, k - weight) + value : -INF, // ✅ include A[i]
exclude = go(i + 1, k); // 🚫 exclude A[i]
return m[key.str()] = max(include, exclude); // 🎯 best
};
return go(0, K);
}
int bottom_up(Pairs& A, int K) {
auto N = A.size();
using VI = vector<int>;
using VVI = vector<VI>;
VVI dp(N + 1, VI(K + 1, -INF)); // 🤔 memo
for (auto k{ 0 }; k < K; dp[0][k++] = 0); // 🛑 empty set
for (auto i{ 1 }; i <= N; ++i) {
for (auto k{ 0 }; k <= K; ++k) {
auto [value, weight] = A[i - 1];
auto include = 0 <= k - weight ? dp[i - 1][k - weight] +value : -INF, // ✅ include A[i]
exclude = dp[i - 1][k]; // 🚫 exclude A[i]
dp[i][k] = max(include, exclude); // 🎯 best
}
}
return dp[N][K];
}
int bottom_up_memopt(Pairs& A, int K) {
auto N = A.size();
using VI = vector<int>;
VI pre(K + 1, 0); // 🤔 memo + 🛑 empty set
for (auto i{ 1 }; i <= N; ++i) {
VI cur(K + 1, -INF);
for (auto k{ 0 }; k <= K; ++k) {
auto [value, weight] = A[i - 1];
auto include = 0 <= k - weight ? pre[k - weight] +value : -INF, // ✅ include A[i]
exclude = pre[k]; // 🚫 exclude A[i]
cur[k] = max(include, exclude); // 🎯 best
}
swap(pre, cur);
}
return pre[K];
}
void run(const string& filename) {
Pairs A;
fstream fin{ filename };
int K, N; // K capacity, N items
fin >> K >> N;
for (int value, weight; fin >> value >> weight; A.emplace_back(value, weight));
auto a = top_down(A, K),
b = bottom_up(A, K),
c = bottom_up_memopt(A, K);
assert(a == b && b == c); // 💩 sanity check
cout << filename << ": " << a << endl;
}
int main() {
run("problem16.7test.txt"); // problem16.7test.txt: 2493893
return 0;
}
📚 Lectures
🎯 Solutions
Kotlin
import java.io.File
import java.util.LinkedList
import java.util.Queue
// bellman-ford: N - 1 edge relaxations (u -> v of cost w) [ie. attempting to relax M edges N - 1 times] given N vertices
fun bell(E: Array<Triple<Int, Int, Int>>, N: Int, start: Int = 1, INF: Int = (1e6).toInt()): IntArray {
var dist = IntArray(N) { INF }
dist[start] = 0
var K = N - 1
while (0 < K--)
E.forEach{ (u, v, w) -> dist[v] = Math.min(dist[v], dist[u] + w)}
return dist
}
// shortest-paths faster algorithm: only attempt to relax candidate edges (note: adjacency list needed)
fun spfa(E: Array<Triple<Int, Int, Int>>, N: Int, start: Int = 1, INF: Int = (1e6).toInt()): IntArray {
var dist = IntArray(N) { INF }
dist[start] = 0
var adj = Array<MutableList<Pair<Int, Int>>>(N) { mutableListOf<Pair<Int, Int>>() }
for ((u, v, w) in E)
adj[u].add(Pair(v, w))
var q: Queue<Int> = LinkedList<Int>(listOf(start))
while (0 < q.size) {
var u = q.poll()
for ((v, w) in adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w; q.add(v)
}
}
}
return dist
}
fun run(filename: String): IntArray {
var N = 0
var E = mutableListOf<Triple<Int, Int, Int>>()
File(filename).forEachLine {
var A = ArrayDeque(it.trim().split("\t"))
var u = A.removeFirst().toInt()
for ((v, w) in A.map{ it.split(",").map{ it.toInt() } })
E.add(Triple(u, v, w))
++N;
}
var A = E.toTypedArray()
var a = bell(A, N + 1) // +1 for 1-based indexing
var b = spfa(A, N + 1)
assert(a == b) // 💩 sanity check: single source shortest paths are the same
return b
}
fun main() {
var dist = run("test.txt")
println(listOf(7, 37, 59, 82, 99, 115, 133, 165, 188, 197).map{ dist[it] }.joinToString(",")) // 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068
}Javascript
const assert = require('assert');
const zip = require('lodash/zip');
const LineByLine = require('n-readlines');
// bellman-ford: N - 1 edge relaxations (u -> v of cost w) [ie. attempting to relax M edges N - 1 times] given N vertices
let bell = (E, N, start = 1, INF = Number(1e6)) => {
let dist = Array(N).fill(INF);
dist[start] = 0;
let K = N - 1;
while (K--)
E.forEach(([u, v, w]) => dist[v] = Math.min(dist[v], dist[u] + w));
return dist;
};
// shortest-paths faster algorithm: only attempt to relax candidate edges (note: adjacency list needed)
let spfa = (E, N, start = 1, INF = Number(1e6)) => {
let dist = Array(N).fill(INF);
dist[start] = 0;
let adj = [...Array(N)].map(_ => []);
E.forEach(([u, v, w]) => adj[u].push([v, w]));
let q = [start];
while (q.length) {
let u = q.shift();
for (let [v, w] of adj[u])
if (dist[v] > dist[u] + w)
dist[v] = dist[u] + w, q.push(v);
}
return dist;
};
let run = filename => {
let N = 0;
let E = [];
let input = new LineByLine(filename);
let line;
while (line = input.next()) {
let A = line.toString('ascii').split('\t').filter(it => it.length);
let u = Number(A.shift());
A.map(pair => pair.split(',').map(Number)).forEach(([v, w]) => E.push([u, v, w]));
++N;
}
let a = bell(E, N + 1), // +1 for 1-based indexing
b = spfa(E, N + 1);
zip(a, b).forEach(([x, y]) => assert(x == y)); // 💩 sanity check: single source shortest paths are the same
return a;
};
let dist = run('test.txt');
console.log([7, 37, 59, 82, 99, 115, 133, 165, 188, 197].map(x => dist[x]).join(',')); // 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068Python3
from collections import deque
# bellman-ford: N - 1 edge relaxations (u -> v of cost w) [ie. attempting to relax M edges N - 1 times] given N vertices
def bell(E, N, start = 1, INF = int(1e6)):
dist = [INF] * N
dist[start] = 0
k = N - 1
while k:
for u, v, w in E:
dist[v] = min(dist[v], dist[u] + w)
k -= 1
return dist
# shortest-paths faster algorithm: only attempt to relax candidate edges (note: adjacency list needed)
def spfa(E, N, start = 1, INF = int(1e6)):
dist = [INF] * N
dist[start] = 0
adj = {i: [] for i in range(N)}
for u, v, w in E:
adj[u].append([v, w])
q = deque([start])
while q:
u = q.popleft()
for v, w in adj[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w; q.append(v)
return dist
def run(filename):
E = []
N = 0
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
line = line.strip()
A = [word for word in line.split('\t') if len(word)]
u = int(A[0])
for i in range(1, len(A)):
v, w = [int(x) for x in A[i].split(',')]
E.append([u, v, w])
N += 1
a = bell(E, N + 1) # +1 for 1-based indexing
b = spfa(E, N + 1)
assert(a == b)
return b
dist = run('test.txt')
print(','.join(str(dist[x]) for x in [7, 37, 59, 82, 99, 115, 133, 165, 188, 197])) # 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068C++
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
using VI = vector<int>;
using VS = vector<string>;
using Edge = tuple<int, int, int>;
using Edges = vector<Edge>;
using Pair = pair<int, int>;
using Pairs = vector<Pair>;
using AdjList = unordered_map<int, Pairs>;
using Queue = queue<int>;
// bellman-ford: N - 1 edge relaxations (u -> v of cost w) [ie. attempting to relax M edges N - 1 times] given N vertices
VI bell(Edges& E, int N, int start = 1, int INF = 1e6) {
VI dist(N, INF);
dist[start] = 0;
auto K = N - 1;
while (K--)
for (auto [u, v, w]: E)
dist[v] = min(dist[v], dist[u] + w);
return dist;
}
// shortest-paths faster algorithm: only attempt to relax candidate edges (note: adjacency list needed)
VI spfa(Edges& E, int N, int start = 1, int INF = 1e6, AdjList adj = {}) {
VI dist(N, INF);
dist[start] = 0;
for (auto [u, v, w]: E)
adj[u].emplace_back(v, w);
Queue q{{ start }};
while (q.size()) {
auto u = q.front(); q.pop();
for (auto [v, w]: adj[u])
if (dist[v] > dist[u] + w)
dist[v] = dist[u] + w, q.push(v);
}
return dist;
}
VI run(const string& filename) {
auto N = 0;
Edges E;
fstream fin{ filename };
VS A;
for (string line; getline(fin, line); A.emplace_back(line));
for (auto& s: A) {
transform(s.begin(), s.end(), s.begin(), [](auto c) { return c == ',' ? ' ' : c; });
stringstream ss{ s };
auto [u, v, w] = make_tuple(0, 0, 0);
ss >> u;
while (ss >> v >> w)
E.emplace_back(u, v, w);
++N;
}
auto a = bell(E, N + 1), // +1 for 1-based indexing
b = spfa(E, N + 1);
assert(a == b);
return b;
}
int main() {
auto dist = run("test.txt");
VI A{ 7, 37, 59, 82, 99, 115, 133, 165, 188, 197 };
transform(A.begin(), A.end(), A.begin(), [&](auto x) { return dist[x]; });
copy(A.begin(), A.end(), ostream_iterator<int>(cout, ",")); // 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068,
return 0;
}📚 Lectures
🎯 Solutions
Kotlin
import java.io.File
var key = { i: Int, j: Int -> "$i,$j" }
var INF = (1e9 + 7).toInt()
fun floyd_warshall(E: MutableMap<String, Int>, N: Int): Array<IntArray> {
var dp = Array(N + 1) { Array(N + 1) { IntArray(N + 1) { INF } } }
for (i in 0..N)
for (j in 0..N)
if (i == j)
dp[0][i][j] = 0
else
if (E.contains(key(i, j)))
dp[0][i][j] = E[key(i, j)]!!
for (k in 1..N)
for (i in 1..N)
for (j in 1..N)
dp[k][i][j] = Math.min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j])
return dp[N]
}
fun floyd_warshall_memopt(E: MutableMap<String, Int>, N: Int): Array<IntArray> {
var pre = Array(N + 1) { IntArray(N + 1) { INF } }
for (i in 0..N)
for (j in 0..N)
if (i == j)
pre[i][j] = 0
else
if (E.contains(key(i, j)))
pre[i][j] = E[key(i, j)]!!
for (k in 1..N) {
var cur = Array(N + 1) { IntArray(N + 1) { INF } }
for (i in 1..N)
for (j in 1..N)
cur[i][j] = Math.min(pre[i][j], pre[i][k] + pre[k][j])
pre = cur.also{ cur = pre }
}
return pre
}
fun run(filename: String) {
var N = 0
var E = mutableMapOf<String, Int>()
var first = true
File(filename).forEachLine {
if (!first) {
var (u, v, w) = it.trim().split(" ").map{ it.toInt() }
E[key(u, v)] = w
} else {
N = it.trim().split(" ").map{ it.toInt() }[0]
first = false
}
}
var a = floyd_warshall_memopt(E, N)
var b = floyd_warshall(E, N)
for (i in 1..N)
for (j in 1..N)
assert(a[i][j] == b[i][j]) // 💩 sanity check
var cycle = false
for (i in 1..N)
if (a[i][i] < 0)
cycle = true
if (cycle) {
println("$filename: contains a negative cycle")
return
}
var best = INF
for (i in 1..N)
for (j in 1..N)
best = Math.min(best, a[i][j])
println("$filename: $best")
}
fun main() {
run("problem18.8test1.txt"); // problem18.8test1.txt: -2
run("problem18.8test2.txt"); // problem18.8test2.txt: contains a negative cycle
run("problem18.8file1.txt"); // problem18.8file1.txt: contains a negative cycle
run("problem18.8file2.txt"); // problem18.8file2.txt: contains a negative cycle
run("problem18.8file3.txt"); // problem18.8file3.txt: -19
// run("problem18.8file4.txt");
}Javascript
const LineByLine = require('n-readlines');
const assert = require('assert');
let key = (i, j) => `${i},${j}`;
let floyd_warshall = (E, N) => {
let dp = [...Array(N + 1)].map(_ => [...Array(N + 1)].map(_ => Array(N + 1).fill(Infinity)));
for (let i = 1; i <= N; ++i)
for (let j = 1; j <= N; ++j)
if (i == j)
dp[0][i][j] = 0;
else
if (E.has(key(i, j)))
dp[0][i][j] = E.get(key(i, j));
for (let k = 1; k <= N; ++k)
for (let i = 1; i <= N; ++i)
for (let j = 1; j <= N; ++j)
dp[k][i][j] = Math.min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
return dp[N];
};
let floyd_warshall_memopt = (E, N) => {
let pre = [...Array(N + 1)].map(_ => Array(N + 1).fill(Infinity));
for (let i = 1; i <= N; ++i)
for (let j = 1; j <= N; ++j)
if (i == j)
pre[i][j] = 0;
else
if (E.has(key(i, j)))
pre[i][j] = E.get(key(i, j));
for (let k = 1; k <= N; ++k) {
let cur = [...Array(N + 1)].map(_ => Array(N + 1).fill(Infinity));
for (let i = 1; i <= N; ++i)
for (let j = 1; j <= N; ++j)
cur[i][j] = Math.min(pre[i][j], pre[i][k] + pre[k][j]);
[pre, cur] = [cur, pre];
}
return pre;
};
let run = filename => {
let E = new Map();
let input = new LineByLine(filename);
let [N, _] = input.next().toString('ascii').split(' ').map(Number);
let line;
while (line = input.next()) {
let [u, v, w] = line.toString('ascii').split(' ').map(Number);
E.set(key(u, v), w);
}
let a = floyd_warshall_memopt(E, N),
b = floyd_warshall(E, N);
for (let i = 1; i <= N; ++i)
for (let j = 1; j <= N; ++j)
assert(a[i][j] == b[i][j]);
let cycle = false;
for (let i = 1; i <= N; ++i)
if (a[i][i] < 0)
cycle = true;
if (cycle) {
console.log(`${filename}: contains a negative cycle`);
return;
}
var best = Infinity;
for (row of a)
best = Math.min(best, ...row);
console.log(`${filename}: ${best}`);
};
run('problem18.8test1.txt'); // problem18.8test1.txt: -2
run('problem18.8test2.txt'); // problem18.8test2.txt: contains a negative cycle
run('problem18.8file1.txt'); // problem18.8file1.txt: contains a negative cycle
run('problem18.8file2.txt'); // problem18.8file2.txt: contains a negative cycle
run('problem18.8file3.txt'); // problem18.8file3.txt: -19
// run('problem18.8file4.txt');Python3
key = lambda i, j: f'{i},{j}'
def floyd_warshall(E, N):
dp = [[[float('inf')] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, N + 1):
if i == j:
dp[0][i][j] = 0
elif key(i, j) in E:
dp[0][i][j] = E[key(i, j)]
for k in range(1, N + 1):
for i in range(1, N + 1):
for j in range(1, N + 1):
dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j])
return dp[N]
def floyd_warshall_memopt(E, N):
pre = [[float('inf')] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, N + 1):
if i == j:
pre[i][j] = 0
elif key(i, j) in E:
pre[i][j] = E[key(i, j)]
for k in range(1, N + 1):
cur = [[float('inf')] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, N + 1):
cur[i][j] = min(pre[i][j], pre[i][k] + pre[k][j])
pre, cur = cur, pre
return pre
def run(filename):
E = {}
N = 0
first = True
with open(filename) as fin:
while True:
line = fin.readline()
if not line:
break
if not first:
u, v, w = [int(x) for x in line.strip().split(' ')]
E[key(u, v)] = w
else:
N = [int(x) for x in line.strip().split(' ')][0]
first = False
a = floyd_warshall_memopt(E, N)
b = floyd_warshall(E, N)
for i in range(1, N + 1):
for j in range(1, N + 1):
assert(a[i][j] == b[i][j]) # 💩 sanity check
cycle = False
for i in range(1, N + 1):
if a[i][i] < 0:
cycle = True
if cycle:
print(f'{filename}: contains a negative cycle')
return
best = float('inf')
for row in a:
best = min(best, *row)
print(f'{filename}: {best}')
run('problem18.8test1.txt') # problem18.8test1.txt: -2
run('problem18.8test2.txt') # problem18.8test2.txt: contains a negative cycle
run('problem18.8file1.txt') # problem18.8file1.txt: contains a negative cycle
run('problem18.8file2.txt') # problem18.8file2.txt: contains a negative cycle
run('problem18.8file3.txt') # problem18.8file3.txt: -19
# run('problem18.8file4.txt')C++
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <unordered_map>
#define PERF_TEST
using namespace std;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
using Edges = unordered_map<string, LL>;
LL INF = 1e9 + 7;
string key(int i, int j) {
stringstream ss; ss << i << "," << j;
return ss.str();
}
VVL floyd_warshall(Edges& E, int N) {
VVVL dp(N + 1, VVL(N + 1, VL(N + 1, INF)));
for (auto i{ 1 }; i <= N; ++i)
for (auto j{ 1 }; j <= N; ++j)
if (i == j)
dp[0][i][j] = 0;
else
if (E.find(key(i, j)) != E.end())
dp[0][i][j] = E[key(i, j)];
for (auto k{ 1 }; k <= N; ++k)
for (auto i{ 1 }; i <= N; ++i)
for (auto j{ 1 }; j <= N; ++j)
dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
return dp[N];
}
VVL floyd_warshall_memopt(Edges& E, int N) {
VVL pre(N + 1, VL(N + 1, INF));
for (auto i{ 1 }; i <= N; ++i)
for (auto j{ 1 }; j <= N; ++j)
if (i == j)
pre[i][j] = 0;
else
if (E.find(key(i, j)) != E.end())
pre[i][j] = E[key(i, j)];
for (auto k{ 1 }; k <= N; ++k) {
VVL cur(N + 1, VL(N + 1, INF));
for (auto i{ 1 }; i <= N; ++i)
for (auto j{ 1 }; j <= N; ++j)
cur[i][j] = min(pre[i][j], pre[i][k] + pre[k][j]);
swap(pre, cur);
}
return pre;
}
void run(const string& filename) {
Edges E;
fstream fin{ filename };
int N, M; fin >> N >> M;
for (int u, v, w; fin >> u >> v >> w; E[key(u, v)] = w);
#ifdef PERF_TEST
auto a = floyd_warshall_memopt(E, N);
#else
auto a = floyd_warshall_memopt(E, N),
b = floyd_warshall(E, N);
assert(a == b); // 💩 sanity check
#endif
auto cycle = false;
for (auto i{ 1 }; i <= N && !cycle; ++i)
cycle = a[i][i] < 0;
if (cycle) {
cout << filename << ": contains a negative cycle" << endl;
return;
}
auto best = INF;
for (auto& row: a)
best = min(best, *min_element(row.begin(), row.end()));
cout << filename << ": " << best << endl;
}
int main() {
run("problem18.8test1.txt"); // problem18.8test1.txt: -2
run("problem18.8test2.txt"); // problem18.8test2.txt: contains a negative cycle
run("problem18.8file1.txt"); // problem18.8file1.txt: contains a negative cycle
run("problem18.8file2.txt"); // problem18.8file2.txt: contains a negative cycle
run("problem18.8file3.txt"); // problem18.8file3.txt: -19
// run("problem18.8file4.txt");
return 0;
}