memoization

A funky stack that is lazy but fast.

Scenario

We have to implement 3 operations on a stack-like list structure: push [value], pop, and an increment operation, inc [i] [value], that adds [value] to the bottom [i] elements of the stack ([value] can be negative). For example, inc 3 10 changes the bottom 3 data points in a stack as such:

| 5|      | 5| (top)
| 4|      | 4|
| 2|  =>  |12|
| 2|      |12|
| 3|      |13| (bottom)

At first read, this is simple, but there’s a way to make run it faster than you might’ve considered…

Scenario

Determine number of possible ways to decode a given Caeser cipher encoded message that maps:
‘A’ -> ‘1’
‘B’ -> ‘2’
…
‘Z’ -> ‘26’
The input is a string of n numbers and the output is a number counting all the possible ways a message could be decoded…