# Eric Normand Newsletter 468: Choice of abstraction matters

Sign up for weekly Clojure tips, software design, and a Clojure coding challenge.

## 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