# 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 LemmoHere 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 $r, c$ be the number of rows and columns of the map respectively. Initially, Lemmo will start on the highest floor, which could be in $c$ different positions. It can either face to the left or to the right. Therefore, there are $2c$ initial configurations.

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

The naive way to solve the first task is to simulate all possible configurations (in the order of $O(c)$). Simulation is feasible because any initial configurations will lead to either a treasure box or a bottomless sewer drain eventually, so the simulation will terminate. However, a map like this:

 1 2 3 #########. .######### #########$ would make Lemmo walk over every block (in the order of $O(rc)$). Thus, it would run in $O(rc^2)$. This would be too slow to finish in one second. 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)

FIN