# Eric Normand Newsletter 468: Choice of abstraction matters

## Reflections ðŸ¤”

*Choice of abstraction matters*

The purpose of abstracting is

notto be vague, but to create a new semantic level in which one can be absolutely precise. -- Edsger Dijkstra

As usual, I've been thinking a lot about abstraction. While my book on the topic would be practical and skill-based, it's useful for me to explore the more abstract, theoretical ideas behind it. I think this is a safe place to do that.

I've rewatched a lecture by Dijkstra where he presents some river-crossing puzzles. One of the puzzles is the Wolf-Goat-Cabbage problem. You have a wolf, a goat, and a cabbage. You're trying to cross the river in a boat. Your boat is only big enough for you and one of your items. If you leave the wolf with the goat, the wolf will eat it. If you leave the goat with the cabbage, the goat will eat it. How do you get all three things across?

While you can easily do a case analysis to figure out the right move for
every case (there are only 16 possible system states), Dijkstra
introduces an abstraction that simplifies the problem. He shows that the
wolf and the cabbage are equivalent in that neither can be alone with
the goat. He calls both objects É‘ (and the two together É‘^2). There are
only 12 possible states with that abstraction since some concrete states
map to the same abstract states. While it doesn't make the problem
*that* much easier to solve, the point is clear: choice of abstraction
does matter.

What Dijkstra doesn't talk about is how it relates to programming. Here's a problem when trying to program to this abstract form: If I know I need to move an É‘, but I have to output my move in terms of "move cabbage" or "move wolf," how do I know which move is correct? I need to map É‘ back down to the concrete object to move. The operation needs to know what is on the current side of the river. It requires the current state. That need makes it much less convenient to write . It may even nullify the benefits of the abstraction.

Choosing an abstraction is only half of the job. The other half is
encoding the abstract form into a convenient construct in your language.
By convenient, I mean it has to be easy to write, read, and show the
correctness of the operations. And it also has to be convenient (read:
*efficient*) for the computer to execute the operations.

If I have `:wolf`

, `:goat`

, and `:cabbage`

, I can easily represent the
state as a set of zero or more of those keywords. If you count them,
you'll see that there are 8 subsets. If I use `:alpha`

and `:goat`

, I
can't keep two alphas in a set. Using a vector is inconvenient because
searching it is hard, and also, order now matters (`[:alpha :goat]`

vs.Â `[:goat :alpha]`

). But I could use a map like `{:alpha 2, :goat 1}`

.
That does encode it, but am I opening up my system to errors where
somehow I get `{:alpha 3}`

? And what's the difference between `{}`

and
`{:goat 0}`

? I need to be able to impose invariants.

I'm not trying to dismiss Dijkstra's abstraction. It's a brilliant example. Even though it's a puzzle, it captures a large part of what we do as programmers when deciding how to program a problem. Instead, I want to discover how to teach the skills this example reveals. How do we invent abstractions? How can we encode those abstract forms in code? How do the operations inform the encodings and influence the abstractions we choose?

## Clojure Challenge ðŸ¤”

### Last challenge

Issue 467 - Unfriendly neighors - Submissions

### This week's challenge

*Maxie and Minnie*

The maxxie of a number `n`

is the largest number you can achieve by
swapping two of its digits (in decimal) (or choosing not to swap if it
is already the largest possible). The minnie is the smallest with one
swap (though you can't swap a zero digit into the most significant
position).

Your task is to write a function that takes an integer and returns a tuple of the maxxie and minnie.

Examples

```
(swapmaxmin 213) ;=> [312, 123]
(swapmaxmin 12345) ;=> [52341, 12345] ;; the number was already the
smallest
(swapmaxmin 100) ;=> [100, 100] ;; no swap possible because of
zeroes
```

Notes

- Swap any two decimal digits
- No leading zeroes
- Don't swap if you can't make it bigger/smaller

Thanks to this site
for the problem idea, where it is rated *Expert* in Ruby. The problem
has been modified.

Please submit your solutions as comments on this gist.

Rock on!

Eric Normand