When I was a student, I would get a sinking feeling whenever I saw a dynamic programming problem. It’s not something I really encounter nowadays, but I ran across a write-up of the top-down technique which felt 100x more intuitive and decided to apply it to a problem.
Generally, I can usually come up with a recursive brute force solution. The sticking point for me is when we move from brute force to “careful brute force”. The main takeaway I had from the breakdown though was to transition by reducing your function arguments and then add caching.
So, let’s try it on a different problem.
Last year (2020), in the Code Jam to I/O for Women, there was a problem that seemed ripe for DP – Interleaved Output: Part 2. I didn’t get to it then, but better late than never. Here’s a solution in TS* that is marked correct for the small input and hits the memory limit on big input.
*Compiled to JS locally and submitted on JavaScript (Node.js) because their compilation of Typescript is sus.
// Stores flags for whether a machine is in middle of processing or not.
type MachineState = boolean[];
const MACHINE_INDEX = {
IO: 0,
io: 1,
Io: 2,
iO: 3
}
function recurse(index: number, input: string, machineState: MachineState, currCount: number): number[] {
// Base case, no more to process
if (index === input.length) {
return [currCount];
}
const c = input.charAt(index);
let counts = [];
if (c === 'I' || c === 'i') {
const machines = c === 'I' ?
[MACHINE_INDEX.IO, MACHINE_INDEX.Io] : [MACHINE_INDEX.io, MACHINE_INDEX.iO];
machines.forEach((machine_index) => {
// Check machine is not already turned on.
if (!machineState[machine_index]) {
const copy = [...machineState];
copy[machine_index] = true;
counts = counts.concat(recurse(index + 1, input, copy, currCount));
}
})
}
if (c === 'O' || c === 'o') {
const machines = c === 'O' ?
[MACHINE_INDEX.IO, MACHINE_INDEX.iO] : [MACHINE_INDEX.io, MACHINE_INDEX.Io];
machines.forEach((machine_index) => {
// Check machine is turned out.
if (machineState[machine_index]) {
const copy = [...machineState];
copy[machine_index] = false;
let updateCount = machine_index === MACHINE_INDEX.IO ? currCount + 1 : currCount;
counts = counts.concat(recurse(index + 1, input, copy, updateCount));
}
})
}
return counts;
}
function solve(input: string): string {
const machineState = [false, false, false, false]
const counts = recurse(0, input, machineState, 0);
const total = Math.max.apply(null, counts);
return `${total}`;
}
The main idea is we pass along our input string, where we are at processing, and what our machines look like. We return back for each possible valid way of generating the output the value we’re looking for; the number of times the IO machine printed. And then run the max on that. Now let’s look at cleaning this up.
function recurse(index: number, input: string, machineState: MachineState, currCount: number)
input does not change; we could store this in a global variable and be fine.currCount was kind of weird anyways. The only time the count changes is if we completed an “IO” machine print. And then, since we only care about the max, we didn’t need to return an array of possible values, and we can use the max between the possible subcalls.With these changes, our recurse function looks more like this:
// Stores flags for whether a machine is in middle of processing or not.
type MachineState = boolean[];
const MACHINE_INDEX = {
IO: 0,
io: 1,
Io: 2,
iO: 3
}
let input: string;
function recurse(index: number, machineState: MachineState): number {
// Base case, no more to process
if (index === input.length) {
return 0;
}
const c = input.charAt(index);
let counts = [];
if (c === 'I' || c === 'i') {
const machines = c === 'I' ?
[MACHINE_INDEX.IO, MACHINE_INDEX.Io] : [MACHINE_INDEX.io, MACHINE_INDEX.iO];
machines.forEach((machine_index) => {
if (!machineState[machine_index]) {
const copy = [...machineState];
copy[machine_index] = true;
// Removed recurse args and now just insert in count.
counts.push(recurse(index + 1, copy));
}
})
}
if (c === 'O' || c === 'o') {
const machines = c === 'O' ?
[MACHINE_INDEX.IO, MACHINE_INDEX.iO] : [MACHINE_INDEX.io, MACHINE_INDEX.Io];
machines.forEach((machine_index) => {
if (machineState[machine_index]) {
const copy = [...machineState];
copy[machine_index] = false;
// Removed recurse args and add count if an IO machine finished printing.
let updateCount = machine_index === MACHINE_INDEX.IO ? 1 : 0;
counts.push(recurse(index + 1, copy) + updateCount);
}
})
}
return Math.max.apply(null, counts);
}
function solve(s: string): string {
// Set to global
input = s;
const machineState = [false, false, false, false]
const total = recurse(0, machineState);
return `${total}`;
}
Now every parameter we have is limited in space; index by the length of the string, and machineState by the number of possible states (since we only have 4 machines that can be either not processing or waiting for the last character to print, so 2^4 or 16). We could cache on these parameters and call it a day.
// ...
let cache: Record<string, number>[];
function recurse(index: number, machineState: MachineState): number {
// Base case, no more to process
if (index === input.length) {
return 0;
}
const encodedMachineState = machineState.join('');
if (cache[index][encodedMachineState] > -1) {
return cache[index][encodedMachineState];
}
// ...
const result = Math.max.apply(null, counts);
cache[index][encodedMachineState] = result;
return result;
}
function solve(s: string): string {
input = s;
// Initialize with value of -1
cache = new Array(input.length)
.fill(null)
.map(() => ({
'truetruetruetrue': -1,
'truetruetruefalse': -1,
'truetruefalsetrue': -1,
'truefalsetruetrue': -1,
// ...etcetc...
}));
const machineState = [false, false, false, false]
const total = recurse(0, machineState);
return `${total}`;
}
And that’s enough to solve big input! The rest I’ll consider style points. For example, listing out ‘truetruetruetrue’ is pretty janky, we can clearly switch to using 1s and 0s (e.g. 1111) aka binary. Then we can use a regular 2D array instead.
const MACHINE_INDEX = {
IO: 1<<0,
io: 1<<1,
Io: 1<<2,
iO: 1<<3
}
let input: string;
let cache: number[][];
function recurse(index: number, machineState: number): number {
if (index === input.length) {
return 0;
}
if (cache[index][machineState] > -1) {
return cache[index][machineState];
}
const c = input.charAt(index);
let counts = [];
if (c === 'I' || c === 'i') {
const machines = c === 'I' ?
[MACHINE_INDEX.IO, MACHINE_INDEX.Io] : [MACHINE_INDEX.io, MACHINE_INDEX.iO];
machines.forEach((machine_index) => {
if (!(machineState & machine_index)) {
counts.push(recurse(index + 1, machineState | machine_index));
}
})
}
if (c === 'O' || c === 'o') {
const machines = c === 'O' ?
[MACHINE_INDEX.IO, MACHINE_INDEX.iO] : [MACHINE_INDEX.io, MACHINE_INDEX.Io];
machines.forEach((machine_index) => {
if (machineState & machine_index) {
let updateCount = machine_index === MACHINE_INDEX.IO ? 1 : 0;
counts.push(recurse(index + 1, machineState ^ machine_index) + updateCount);
}
})
}
const result = Math.max.apply(null, counts);
cache[index][machineState] = result;
return result;
}
function solve(s: string): string {
input = s;
cache = new Array(input.length)
.fill(null)
.map(() => new Array(16).fill(-1))
const total = recurse(0, 0);
return `${total}`;
}
And that’s that, unless you want to try to flip it to the bottom-up approach. I will not.