# Lemmo

Published on Tuesday, December 27th, 2016

Wandering around in Wikipedia yesterday, I found this article: *Lemmings*. Though I never play this game before, I have played its open-source clone, *Pingus*, which is really enjoyableI in fact have devised a pretty good strategy for a level several years ago.*Edited on February 25, 2017*: someone broke my record! . This post is written to pay tribute to this wonderful game.

Anyway, the post is not really going to be about the game. *Lemmings* also reminds me of something else too. Several years ago, I attempted to solve a programming puzzle and failed. Then I tried again a year after that, and for this time, I succeeded. It became one of my favorite puzzles because of its trickiness under a seemingly simple problem. This programming puzzle is known as *Lemmo*Here is the original problem statement (in Thai). Indeed, it’s a yet another variant of *Lemmings*.

Lemmo is a simple creature. All it does is merely walking. When hitting a wall, it turns around. When stepping over a space, it fallsLemmo will survive however high it falls. This is not true in the original *Lemmings*.. It is guaranteed that the map that Lemmo is going to be in will have at least a space for every non-first floor. That is, Lemmo will definitely reach the first floor. The game ends when Lemmo steps over either a treasure box or a bottomless sewer drain, located on only the first floor. As you can anticipate, finding a treasure box is a win, while falling into a bottomless sewer drain is a lose. It is also guaranteed that there will be at least one treasure box or one sewer drain, and that there is no space on the first floor. That is, the game will always end.

Let

*Use the following keys to setup the initial configuration: Left to move/face left, Right to move/face right. Then click *

`Start`

to begin the game.__Task 1: Write a program to find how many different initial configurations will lead Lemmo to a treasure box?__

__Task 2: Write a program to find the maximum number of different initial configurations that will lead Lemmo to a treasure box, provided that you are allowed to remove no more than one block from a non-first floor (that is, turning no more than one block into a space)?__

Here’s the constraints:

- Time limit: 1 second
- Memory limit: 32MB
$1 \le r, c \le 1000$

The input will be in the following format:

1 2 3 4 | #####.###.## ###.#####.## #.####.##### @#@$@$###### |

where `@`

indicates a bottomless sewer drain, `#`

indicates a block on a floor, `.`

indicates a space, and `$`

indicates a treasure box.

In the above example, the configurations facing left in the column 6, 7, 8, 9 will lead to the leftmost bottomless sewer drain, while the rest will lead to the rightmost treasure box. However, if we remove the block at row 3, column 4, all configurations will lead to a treasure box. Therefore, the answer should be 20 and 24 respectively.

Following is my solution and explanation. Do not read if you wish not to see a spoiler. I have warned you.

.

.

.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #lang racket (define-syntax-rule (def whatever ...) (define whatever ...)) (define-syntax-rule (def/memo (name arg ...) body ...) (def name (memoize (λ (arg ...) body ...)))) (define-syntax-rule (ie0 condition true-expr ...) (cond [condition true-expr ...] [else 0])) (def (memoize f) (let ([dp (make-hash)]) (λ args (hash-ref! dp args (thunk (apply f args)))))) (define-values (SPACE BLOCK WIN LOSE) (apply values (string->list ".#$@"))) (def (normalize x) (if (equal? x SPACE) 0 1)) (def (lookup t i j) (vector-ref (vector-ref t i) j)) (def (calc ls) (def tab (list->vector (cons (build-vector (string-length (first ls)) (thunk* SPACE)) (map (λ (l) (list->vector (string->list l))) ls)))) (def tab-sum (vector-map (λ (row-vector) (define-values (_ lst) (for/fold ([sum 0] [lst '(0)]) ([e row-vector]) (def next-sum (+ sum (normalize e))) (values next-sum (cons next-sum lst)))) (list->vector (reverse lst))) tab)) (def rows (vector-length tab)) (def cols (vector-length (vector-ref tab 0))) (define-values (next prev) (values + -)) (def (has-all? r i j) (= (+ j (- i) 1) (- (lookup tab-sum r (add1 j)) (lookup tab-sum r i)))) (def (get-hmove c dir change) (def maybe-c (change c dir)) (if (<= 0 maybe-c (sub1 cols)) (values maybe-c dir) (values c (- dir)))) (def/memo (calc1 r c dir) (cond [(zero? r) 1] [else (define-values (p-c p-dir) (get-hmove c dir prev)) (+ (ie0 (equal? SPACE (lookup tab (sub1 r) c)) (calc1 (sub1 r) c dir)) (ie0 (equal? BLOCK (lookup tab r p-c)) (calc1 r p-c p-dir)))])) (def/memo (win? r c dir) (match (lookup tab r c) [(== WIN) #t] [(== LOSE) #f] [(== SPACE) (win? (add1 r) c dir)] [(== BLOCK) (define-values (p-c p-dir) (get-hmove c dir next)) (win? r p-c p-dir)])) (def (delta r c dir) (ie0 (equal? BLOCK (lookup tab r c)) (def proc (cond [(and (win? (add1 r) c dir) (not (win? r c dir))) +] [(and (not (win? (add1 r) c dir)) (win? r c dir)) -] [else #f])) (ie0 proc (def over-calc (ie0 (or (and (= dir -1) (has-all? r c (sub1 cols))) (and (= dir 1) (has-all? r 0 c))) (calc1 r c (- dir)))) (proc (- (calc1 r c dir) over-calc))))) (define-values (first-sol) (for*/fold ([sum 0]) ([c cols]) (values (+ sum (ie0 (equal? WIN (lookup tab (sub1 rows) c)) (+ (calc1 (sub1 rows) c 1) (calc1 (sub1 rows) c -1))))))) (define-values (second-sol) (for*/fold ([sol 0]) ([r (sub1 rows)] [c cols]) ; only non-first floor (values (max sol (+ (delta r c -1) (delta r c 1)))))) (values first-sol (+ first-sol second-sol))) |

Just about 70 lines, in Racket!

Then, to test:

1 2 3 4 5 6 7 8 9 10 11 | (require rackunit) (def (check input sol1 sol2) (define-values (out1 out2) (calc input)) (check-equal? out1 sol1) (check-equal? out2 sol2)) (check '("#####.###.##" "###.#####.##" "#.####.#####" "@#@$@$######") 20 24) |

does not raise any error, indicating that the answers are correct.

## Explanation

### First Task

The naive way to solve the first task is to simulate all possible configurations (in the order of

1 2 3 | #########. .######### #########$ |

would make Lemmo walk over every block (in the order of

This is when dynamic programming comes to rescue. What we want to know is the number of ways that Lemmo will reach any treasure box from all possible configurations. Instead of computing that directly, we will generalize it by computing the number of ways that Lemmo will reach a certain position (facing in a certain direction) from all possible configurations. Then, we notice that the result of this computation relates to the number of ways to reach the previous step. For example, in this map:

1 2 3 4 5 6 7 | +------------ | | #.##.####. | ← | .######### | | #########$ |

To be at `←`

(facing to the left, as suggested by the arrow), Lemmo must come from either the above (the above is a space, so it’s possible that Lemmo will get here by falling from there), or from the right.

To illustrate, the number of initial configurations that could make Lemmo to be at `←`

is 15.

1 2 3 4 5 6 7 8 9 | →→→→→→→→→ ←←←←←← +------------ | | #.##.####. | ← | .######### | | #########$ |

which is merely the number of ways that Lemmo can reach the above (5)

1 2 3 4 5 6 7 8 | ←←←←← +------------ | ← | #.##.####. | | .######### | | #########$ |

plus the number of ways that Lemmo can reach the right (10)

1 2 3 4 5 6 7 8 9 | →→→→→→→→→ ← +------------ | | #.##.####. | ← | .######### | | #########$ |

Let’s now formalize it. Let `calc1`

in line 36.

Base case: to simplify things, let’s add another layer, row 0, to the map where I will refer to as “sky.” Sky, as the name suggested, is all spaces (no block). We will then drop Lemmo from the sky instead. This will not affect the answer, since eventually Lemmo will fall to the original place anyway. However, we now have a clear base case, as there is exactly one way to reach it (which is by dropping it there). Therefore,

$W_{0, j, L} = W_{0, j, R} = 1$ for all$j$ .Adding the sky layer (row 0) corresponds to line 18. The base case corresponds to line 38.

Inductive case: if it’s not the base case, then Lemmo can be at position

$i, j$ facing in the direction$d$ by two ways:- From the space above: therefore, this is only applicable when the above is a space. Note that if Lemmo comes from the above, during the fall, it couldn’t change a direction. Thus, if it is applicable, we know already what is the number of ways to get to the above:
$W_{i - 1, j, d}$ . This corresponds to line 40. From behind (in the same row): this part is a little bit tricky. Suppose the behind position is a space, then Lemmo would fall to the lower floor. It can’t jump to this position. Similarly, if the behind position is a treasure box or a bottomless sewer drain, then the game would have ended already. These are the cases that are not applicable.

But moreover, there is one special case: suppose we are adjacent to a wall (either left or right wall) and facing out of the wall, then the behind position can’t be within the wall. It would instead come from the exactly same position, but facing in the other direction. In the normal case however, the direction would still need to be maintained, as Lemmo will not switch the direction unless it’s the special case.

Thus, if it’s applicable, the number of ways to get to the behind position is

$W_{i, j’, d’}$ where$j’$ is the behind position, and$d’$ is the direction in the behind position ($d’ \ne d$ if it’s a special case, but would be the same otherwise). This corresponds to line 41. Note that the function`get-hmove`

in line 32 is for computing the behind position (and its direction).

Therefore:

$W_{i, j, d} = \begin{cases}

W_{i - 1, j, d} + W_{i, j’, d’} & \text{if both the above case}\\ & \text{and the behind case work}\\

W_{i - 1, j, d} & \text{if only the above case works}\\

W_{i, j’, d’} & \text{if only the behind case works}\\

0 & \text{otherwise}\\

\end{cases}$which corresponds to line 40.

- From the space above: therefore, this is only applicable when the above is a space. Note that if Lemmo comes from the above, during the fall, it couldn’t change a direction. Thus, if it is applicable, we know already what is the number of ways to get to the above:

Regarding the time complexity, for each

To finish the first task, we need to calculate an answer, and this is straightforward: it’s just the sum of number of ways to get to all treasure boxes, from both

### Second Task

The naive way would be to try removing each block at a time in the map, and run the first task’s algorithm to evaluate how many initial configurations that will lead to a treasure box increases after the removal. However, the number of blocks is in order of

One important fact is that Lemmo’s walk is deterministic. Therefore, a position and the direction completely determines Lemmo’s eventual destination. That is, it is possible compute

Note, though, that this is even too detailed. We don’t really want to know where exactly Lemmo will end up. We only want to know whether it will find a treasure box or it will fall into a bottomless sewer drain, as that’s what we need to know to calculate the answer. Thus, we will refine the previous definition: we will compute `win?`

at line 42. Note that it could be the case that the state

What we are going to do will be similar to the naive way. We will try removing each block at a time in the map and evaluate how many initial configurations that will lead to a treasure box changes after the removal. However, we will not call the algorithm in the first task on the modified map. Instead, we will use the exactly same data from the first task that we have already to compute the answer.

Consider removing a block, say

So a removal of a block will have an impact when

But this still doesn’t give us an answer. We want to know the delta of number of ways to reach a treasure box. Let *new* map (after removing block

How do we compute *directly* to

1 2 3 4 5 6 7 8 | +--------------------------- | . . . . . . . | | ###########.#.########### | ← | ...###...##!###...###.... | | . . . . . . . |

So

Note that there is a condition above, which is, Lemmo must walk *directly* to

1 2 3 4 5 6 7 8 | +--------------------------- | . . . . . . . | | #############.########.## | ← | ...###...###########!#### | | . . . . . . . |

Here,

Now we know exactly when will this weird rare case happens: when Lemmo faces out of a wall, and would have just bounced off from the wall. That is, there are contiguous blocks starting from the

How do we detect this special case efficiently?

the naive way would be looping from

$(h,k)$ to the wall and see if they are all blocks. However, number of blocks in a floor is in the order of$O(c)$ . We need to try removing all blocks where the number of all blocks are in the order of$O(rc)$ already, so this would result in$O(rc^2)$ which is too slow.And, you know how this will go: dynamic programming! They are all blocks if the current position is a block and the rest are all blocks. I in fact make it even simpler by observing the following: Let’s say we maps

`#`

to 1 and`.`

to 0.1

##..###..#.####

would then be the following array

$B$ :1

1 1 0 0 1 1 1 0 0 1 0 1 1 1 1

To see if it’s all blocks from the third position from the right to the right wall, we need to see if they are all 1s. That is, if

$B_{13} + B_{14} + B_{15} = 1 + 1 + 1 \stackrel{?}{=} 3$ , and in this case, it does, so it’s all blocks.Let’s try another one. We want to see if the fourth position from the left to the left wall are all blocks or not. That is, if

$B_1 + B_2 + B_3 + B_4 = 1 + 1 + 0 + 0 \stackrel{?}{=} 4$ , and the answer is no, so it’s not all blocks.But we still need to loop over to compute the sum of numbers! How is that gonna make a difference?

Let’s construct a prefix-sum table

$E$ which in this case would be1

1 2 2 2 3 4 5 5 5 6 6 7 8 9 10

That is,

$E_k = \sum_{i = 1}^k B_i$ . And by rewriting it to be in dynamic programming style, we obtain:$E_k = \sum_{i = 1}^{k-1} B_i + B_k = E_{k - 1} + B_k$ , where$E_0 = 0$ .Then,

$B_i + ... + B_j = \left(B_1 + ... + B_{i - 1} + (B_i + ... + B_j)\right) - (B_1 + ... + B_{i - 1})$ . That is,$B_i + ... + B_j = E_j - E_{i - 1}$ .So detecting this special case can be done in

$O(1)$ (provided that the prefix-sum is already constructed)!Building the prefix-sum table corresponds to line 20. Checking if it’s all blocks corresponds to function

`has-all?`

in line 30.How do we cope with it?

Well, if we know that it’s a special case, then we know that

$W_{h,k,d}$ overcounts, because it includes$W_{h,k,d’}$ where$d$ is the direction facing out of the wall, and$d’$ is the direction facing in the wall. Therefore,$N_{h,k,d}$ is just$W_{h,k,d} - W_{h,k,d’}$ . This corresponds to line 60.

The second task only needs to compute the table

With these, we are able to compute the answer to the second task in

FIN