# The "Drunken Walk" Programming Problem

In Tortoises, Teleporting Turtles, and Iterators, we looked at the “Tortoise and Hare” algorithm for detecting a linked list. Like many such algorithms, it “tangles” two different concerns:

1. The mechanism for iterating over a list.
2. The algorithm for detecting a loop in a list.

### functional iterators

We then went on to discuss how to use functional iterators to untangle concerns like this, and used taking the sum of a list as an example. A functional iterator is a stateful function that iterates over a data structure. Every time you call it, it returns the next element from the data structure. If and when it completes its traversal, it returns `undefined`.

For example, here is a function that takes an array and returns a functional iterator over the array:

Iterators allow us to write (or refactor) functions to operate on iterators instead of data structures. That increases reuse. We can also write higher-order functions that operate directly on iterators such as mapping and selecting. That allows us to write lazy algorithms.

### refactoring the tortoise and hare

In the previous post, we refactored other algorithms, but not the Tortoise and Hare. Let’s do that now: We’ll refactor it to use iterators instead of directly operate on linked lists. We’ll add an `.iterator()` method to linked lists, and we’ll rewrite our loop detector function to take an “iterable” instead of a list:

We now have a function that will operate on anything that responds to the `.iterate()` method. It’s classic “Duck Typed” Object-Orientation. So, how shall we put it to work?

### a drunken walk

Consider a finite checkerboard of unknown size. On each square we randomly place an arrow pointing to one of its four sides. For convenience, we shall uniformly label the directions: N, S, E, and W. A chequer is placed randomly on the checkerboard. Each move consists of moving the red chequer one square in the direction of the arrow in the square it occupies. If the arrow should cause the chequer to move off the edge of the board, the game halts.

As a player moves the chequer, he calls out the direction of movement, e.g. “N, E, N, S, N, E…” Write an algorithm that will determine whether the game halts strictly from the called out directions, in constant space.

### hints

You’ll need a “Board” and/or “Game” class that acts as iterable, along with some notion of directions. Here’s one possible implementation:

In Tortoises, Teleporting Turtles, and Iterators, we saw the `fold` function that converts a finite iterator into a value:

There’s a similar function that works with finite or infinite iterators, `accumulate`:

`accumulate` can be very handy for solving this problem. Like `fold`, accumulate takes an iterator, a binary function, and a seed. But instead of returning the final, accumulated value, it returns an iterator over the accumulated values. Compare and contrast:

`accumulate` can be thought of as iterating over the steps of a fold. Accumulate can also be thought of as a stateful map from one iterator to another.

### a solution

One possible solution is posted separately to prevent spoilers. Try at least thinking it through before peeking!

My recent work: