Magic squares in clojure

I’d never looked into the logic underlying magics squares… until now.

Behold, the gist.

Command-line Freecell written in Clojure

Tags

clojure, freecell

This rather lengthy post describes my latest project: a highly annotated, command-line freecell clone. It spins off into thoughts on what it was like to develop in clojure, and finishes with some tips and tricks for how to setup your clojure/vim environment.

You can view the source on github.

The Concept

I am an on-again off-again freecell addict. Over the years I’ve found myself mentally dividing the game-playing experience into two parts:

1. Surveying. Searching the board for possible moves, or possible problems in the future.
2. Deciding. Based on those possible moves, making a strategic decision about what to do next.

Of the two parts, I find the second to be far and away the more interesting. So I thought, why not make a freecell clone that will automate the boring work?

My solution, the theory

My solution was to attempt to throw annotations at the board that would answer at a glance common questions such as:

• Which cards are already connected into runs?
• Which cards, if uncovered, could be moved to the foundation piles right now, or to another cascade?
• Which cards are out-of-order in their cascade, or duplicates (same rank and color)?

My solution, technical details

Since I was primarily interested in testing the mechanics of my annotations theory, I decided to go with a minimal front-end. Thus, a CLI. It would be fair to say that I was more than a little inspired by Dwarf Fortress.

My solution, the result

I haven’t played that many games yet, so I don’t have any fully-formed opinions. Some observations:

The command-line interface isn’t as much of a problem as I’d expected. You start seeing past the symbols after a game or two, and the Do What I Mean button means I don’t often have to think about the coordinates.

The games seems to go faster, but shallower. Faster in that I just bang on the DWIM button, and shallower in that I have a less clear understanding of what moves I’m making. My win rate doesn’t seem to be affected, though, so maybe more of the game was about searching for possible moves than I’d realized.

I seem to get stuck more often. I’m not sure whether that means I’m breezing through the easy parts more quickly, or whether I’m getting myself into more difficult binds through abuse of the DWIM button. If the latter, maybe the problem will resolve itself with discipline.

Clojure

I decided to take this project as an opportunity to try a not-completely-trivial clojure project. Some observations.

No state

There is no state in the program. Not a single a = 4 line. No atoms, refs, or agents.

And it was no big deal. Better, it was easy.

I was determined to write in a pure(ish) functional style, but I was concerned about the main game loop. I needn’t have worried. It turned out to be an elegant recursive function, with the state of the world passed from one iteration to the next. Because the state of the world was something I was passing around anyway, it was easy to modify it during a pass to revert to an earlier state or a new game entirely.

Warning, pure opinion and speculation ahead: I have little evidence to support this claim, but I suspect that writing in a functional style provides many of the same benefits as Test Driven Development. It seemed to me that the code naturally divided itself into separate concerns, with few dependencies between the sections. Certainly there was a feeling that once a function was done it was done forever. And why not? All it was doing was making slight tweaks to a common, immutable data structure¹.

Ah, the ()

I love the parentheses in clojure.

On the one hand, they’re super easy to work with (see next section). On the other hand, they get completely out of the way. They’re so ubiquitous and consistent, you just stop seeing them. You use them for automatic code-formatting feature, and otherwise just read the indentation. It’s like python, but with automatic indentation, less ambiguity, more consistency, and better editing tools.

My development environment (vim)

As mentioned, because clojure’s syntax is so regular, it’s extremely simple to create quick shortcuts to manipulate the text. Some quick recommendations for vim users.

• Use tslime to communicate with the REPL
• Use paredit, as extracted from slimv, to automatically balance your parentheses (plus other functions)
• Use surround for additional swashbuckling-() goodness

I created a quick script that provides the following functions:

• Show documentation for word under cursor (or an entered word)
• Rename variable in function, or globally
• Load current file
• Evaluate current expression
• Surround current expression with additional ()

And I’m sure I’ll add more over time. Also, vim’s built-in support for treating ()s as text objects makes moving, copying, deleting and generally manipulating s-expressions an absolute joy. The consistency of the language lets you stop thinking about syntax or how to edit it, and instead get down to thinking only about the logic.

Live out of the REPL

I’ve used languages that had REPLs before, but I’d never grokked the full power of the idea until this project. The power in the ability to introduce or modify functions in the project as it’s running cannot be overstated.

Several times as I was debugging a troublesome function I redefined the function feeding it input to be more regular or to test some edge case — essentially stubbing it out on the fly. There was no recompile cycle, there was no hassle. The code reshaped itself at the speed of thought. It’s seriously a religious experience: super powerful and eye opening to the person who experienced it, but it makes you sound crazy to those who haven’t been through it.

Conclusions on clojure

Clojure is a joy to work with.

Its stateless, functional style makes programs very easy to reason about, test, debug, and breakdown into logical, by-concern-separated chunks.

Its regular syntax is easy on the eyes, and even easier on your text editor. I’ve never found any other language so easy to manipulate — not even java with its enormous, specialized IDEs.

I’d been concerned about clojure’s relatively long startup time. That turned out to be a non-issue, as I spent all my development time in a single REPL session anyway. Working with the REPL itself was an incredibly organic experience, with a natural flow between source code, quick throw-away examples, and the running program.

---

1. Along those same lines, I certainly found that old saw to be true: once I got the central data structures right, the program basically wrote itself. ↩

Awk is awesome

If you don’t know awk, take 5-10 minutes right now and go read the wikipedia page. You’ll probably find that it saves you at least that much time in the next week or two.

Awk had been intimidating me for years because it seemed complicated. Complicated it may be, but it doesn’t take much knowledge to get great benefits.

For example, I was doing some spreadsheet-y work in vim, and I needed to total the 2nd column. Solution: select the table and pipe it through

awk '{s+=$2}END{print s}'

I have no other method for solving this problem so quickly or easily.

Summing columns is such a common operation for me, I created these vim shortcut keys. Enjoy.

" sum column in selection
vmap \s1 !awk '{s+=$1}END{print s}'<CR>
vmap \s2 !awk '{s+=$2}END{print s}'<CR>
vmap \s3 !awk '{s+=$3}END{print s}'<CR>
vmap \s4 !awk '{s+=$4}END{print s}'<CR>
vmap \s5 !awk '{s+=$5}END{print s}'<CR>

Vim Budget-er

Tags

vi

An example of not going overboard solving a problem.

Use Case

Track my monthly spending in my master notes file. Should be able to keep track of amount spent, date, and on what. Should be able to quickly find amount spent, so I know if I’ve gone over my budget yet.

Bad Solution

First thought: write some script to parse some format I make up, and print the result somewhere.

Better/More Lazy Solution

Use the unix tool dc to do the summing. Simple case for simple addition:

1 2 + 3 + 4 + p  # p is to print result

Rearrange to make the "+"s look like bullets

1 2
+ 3
+ 4
+ p

Put in leading fillers for consistency.

0 0
+ 1
+ 2
+ 3
+ 4
+ p

A full example

0 0
+ 2.40  # [04 Jun 2011] kmart
+ 8.20  # [03 Jun 2011] walmart
+ 6.40  # [02 Jun 2011] 7-11
+ p

In vim, create mapping that quickly pipes block through dc, and prints the solution below.

nmap \rd yip}O<Esc>pvip!dc<CR>

Conclusion

It may not be the most general solution in the world, but I didn’t lose a day to putting together a custom, perfectly general script, either.

7-11 Problem

Tags

python

My full solution is on github.

7-11 problem: find 4 numbers whose sum and product are exactly 7.11

Method: use algebra to reduce the search space from 711^4 to 711^2. Then
iterate only over factors of 711,000,000, up to 711, instead of one-by-one.

Result: finds the single exact answer is 0.02 seconds on my machine. Implemented in python.

Indent lines not containing links

Tags

vi

"When all you have is a hammer, everything looks like a nail."

Ordinarily this is an aspect of human nature to avoid, but somtimes it makes an interesting nail easier to find.

I had a pile of reference URLs buried in an even larger pile of prose, and needed some way of visually offsetting the links. So I entered this into vim:

:v/http/norm >>

Which instantly indented each line that didn’t contain http, and for my purposes highlighted the data I wanted just fine.

Quick, simple solution — which wouldn’t have been at all possible if I hadn’t taken the time to pound vim into my bones.

Project Euler problems in dc

Tags

dc

I’m often drawn to ancient, terse, obscure, essentially useless technologies. What this means is that, yes, I’ve started solving Project Euler problems with dc. You can check it out on github.

Swap control and alt keys

Most of the commonly used keyboard shortcuts use the control key: copy, cut, paste, save, close, find, … The alt key is hardly used.

Yet on most keyboards control is relegated to the far corners, while alt sits immediately next to the space bar — trivially accessible to the thumbs.

My humble suggestion: remap your keyboard to swap control and alt. I’ve been living with this arrangement for a week, and I’m loving it. My hands contort less frequently, and I spend more time in home position.

If your own experience is anything like mine, you’ll never switch back.

Bash: temp pipe trick

Tags

terminal

I am easily impressed by awesome bash tricks.

The problem was how to compare two directories. I needed to know what files they didn’t have in common.

The solution:

diff <(ls dir-a) <(ls dir-b)

As described here, wrapping the ls commands in <() causes them to be executed, and the results stuffed through a pipe back to the diff command at the start.

Mergesort in Scheme (with vim)

Tags

lisp, vi

Not having really ever understood mergesort, I decided to implement it in scheme. You can see the result here.

The code is over 100 lines. This is largely because I’m working only with the most primitive functions — what most languages would call “operators”. Including (and restricted to): <=, =, and, car, cdr, cond, cons, define, if, let, list, not, null?, or, and quote. I’m pretty sure that’s it. Notably absent, of course, would be assignment and looping constructs. Also any kind of indexing function, a length, and any means of comparing lists.

I’ve discovered an unexpected benefit of the regularity of scheme’s syntax: it’s really easy to work with the code. Some vim highlights:

• I mapped ) to move to the next ), and ( to move to the previous (. This allows me to hop the cursor exactly to logical pieces of code, uniformly, throughout the program. It’s always ( and ) to move to the relevant bit, then w (for one word forward) until I reach the argument I want. You can’t do that in a language where the delimiters keep changing.

• % in vim moves the cursor to the matching ( or ). This makes it insanely simple to cut/copy/delete/paste-over a logical piece of code. Taken with the previous point: to delete the body of a function I might ))) to move to the right spot, then d% to delete it. There’s no messing around with “one space this way or that” at all.

• I have a vim plugin which lets me write the code in one pane, then execute it in other with the press of a button. After a quick remapping trick, all I have to do to execute a piece of code is move the cursor to an opening or closing brace ((((), then F5 to execute the code in the middle. Works the same if I’m executing a function, an expression, or an expression in a function.

Vim makes writing code feel like a video game. Writing lisp, that feeling is only enhanced.