AllTom.com

Daily Crap 2008-04-14

2008-04-14T14:04:39-04:00

Want/need to find an apartment in northwest Columbus for the summer. 2-bedroom. Hoping to bike to the EdgeCase office.
Just started using Instapaper. Very handy, but still looking for a system that will "forget" stuff so it's not clouding my psyche with such negativity as a long list of things I "should read."

Daily Crap 2008-04-23

2008-04-23T15:17:15-04:00

I almost want to start working with video just so I can use this handy video resolution guide.
I know, lame post. I'm approaching finals period, jerk.
I got a position at MIT this summer, as a TA/tutor/RA for the Digital Design course at the MITES summer camp. I'll be coaching high school juniors on how to make web sites, because clearly I'm an expert.

Daily Crap 2008-05-02

2008-05-02T01:11:29-04:00

I like video games, but at the same time, I feel that life is too short to play them. Down-time from thinking is incredibly important for me, of course, but I find sleep works just as well. I've been feeling pretty mortal lately.
I wish I could finish one thought before being irreversibly driven to the next. I have quite a lot of things I've moved on from that I know could still excite me, but it would take a huge amount of energy to get myself back on that track. Old ideas just seem so used up.

Programming Manifesto

2008-05-04T16:49:21-04:00

This is an open letter I wrote for a professor who rejected a proposal I gave for a semester-long research project in creating a programming language I'm designing. It became a personal programming manifesto and as such was inappropriate for actually sending to said professor, so I merely publish it here.

If you are the originally-intended recipient, hello! I'm flattered that you would read my blog.

Dear Professor,

I just realized that I misrepresented myself when I last came to propose my independent research project for next semester. I unintentionally revealed my foolishness with such a crazy project idea. The problem is that I am a perpetual student. I have no intention of pushing forward the field of computer science, because I've decided that I just don't know enough yet. Thus, all I can do for now is study.

I have the philosophy that if we can only learn by doing, and we learn from our mistakes, that the greatest way to learn is by throwing oneself headlong into projects that have every opportunity for failure. So I do this on a daily basis.

In Operating Systems class, I eschewed the recommendations to create a disk-based filesystem based on i-nodes; instead I ported an old, naive implementation of malloc. It took several times longer and I thought I could smell failure around the corner several times, but in the end I had a system that was faster, supported files and directories the size of the disk, and added a few items to my list of things to never do again.

What it came down to was the fact that I didn't want to take the safe bet. Everyone could see the flaws of such a simple system, so there was no element of exploration. Trudging down that road would have been mindless busy-work. As I'm blissfully ignorant of most CS literature, my own approach was surely just as primitive, but even if I had read that it was the least effective filesystem possible to design, I likely would have tried it if only to see whether it was true. A big part of my self-education is digging back through time and testing our base assumptions for myself.

I maintain a blog that used to be written in PHP. After a while I discovered Ruby on Rails and re-wrote it. Running on Ruby, it became slow, and I decided to figure out whether all the beauty Ruby gave me was worth it — so I rewrote the site in C. I certainly got further than I expected — recognizing URLs and serving several different pages — but when it came time to use library calls for managing things like database connections or file handles, I took some good looks at the documentation for the C API calls and decided that it was time to move on.

I had rediscovered something I had been told many times over: C is inappropriate for designing web sites. Now I know exactly how, which means the wheel I'm reinventing is about as good as those we had a decade ago. One day I hope to catch up and invent cutting-edge wheels of my own, but just as motivating is understanding what drove the development of wheels from the mess that preluded them.

So pardon my affection for the tried-and-failed. I won't be coming by your office again for quite some time — enough for me to prototype the system on my own to examine its merit, in fact. I was never any good at finding problems for my solutions, but perhaps one will show up before classes begin again.

Sincerely,

Tom Lieber

In case you were wondering, the language I proposed was a real doozy. Remember when self-modifying code was all the rage? Combine that with an in-memory code layout I'm having trouble finding a textual representation for, and an interpreter which is never meant to lose state, and you've got a really scary system on your hands. If this project doesn't put some hair on my chest, I don't know what will. Wish me all the best!

Daily Crap 2008-05-12

2008-05-12T12:27:27-04:00

Oh, no, it's bears! … That's all I got.

Daily Crap 2008-05-14

2008-05-14T10:24:24-04:00

Finally, a non-"Elements" copy of Photoshop appears on my hard drive. It feels so great to be able to make images again without a trip to that tiny building on the opposite end of the campus between the hours of 1pm and 7pm.

ChucK Tricks

2008-05-14T10:34:33-04:00

Updated May 14, 2008, in the morning: Tried to better describe what the code was doing

ChucK is the audio software powering most of PLOrk (the PRinceton Laptop Orchestra), and pretty much anything I've made recently requiring real-time audio. It's a flaky scripting language that's strongly-timed, meaning that it makes guarantees about where samples you create will appear in the output stream (even if the stream doesn't make it to the speaker on time because your script is slow).

But if you don't already know ChucK, I'll have to point you toward his wonderful documentation before you read much further.

Generic Polyphonic

In creating the various ChucK instruments I have over the semester, I've often needed a way to combine many sounds with interleaved start and end times. There are two major stumbling blocks to doing this well:

ChucK gets slow and has trouble keeping up with your requested timing when there are too many generators sending audio to the output. Voices should only be connected to the dac when they are playing audio for efficiency.
You should be able to kill a voice while it is still "warming up." That is, if a voice is not quite through its initial "attack," you should still be able to cancel it so that the closing envelope can be applied.

After many, many trials, I believe I'm finally getting close to something usable, even though I have reservations. Take a look:

Gain mix => dac;

9 => int numVoices;
Envelope outs[numVoices];
Shred managers[numVoices];
for(0 => int i; i < numVoices; i++) {
    Envelope e @=> outs[i];
    null => managers[i];
}

fun void open(int voice) { outs[voice] => mix; }
fun void close(int voice) { outs[voice] =< mix; }

fun void rampTo(int voice, float gain, dur len) {
    gain => outs[voice].target;
    len => outs[voice].duration;
    outs[voice].keyOn();
    len => now;
}

// spork this
fun void on(int voice, float gain) {
    if(managers[voice] != null) Machine.remove(managers[voice].id());
    me @=> managers[voice];

    open(voice);
    rampTo(voice, gain * 2.0, 50::ms); // attack
    rampTo(voice, gain, 50::ms); // sustain

    null => managers[voice];
}

// spork this
fun void off(int voice) {
    if(managers[voice] != null) Machine.remove(managers[voice].id());
    me @=> managers[voice];

    rampTo(voice, 0.0, 500::ms);
    close(voice);

    null => managers[voice];
}

Each voice is an Envelope you chuck audio to. Think of it as an organ; you chuck sounds to the different pipes, which you on() and off() to open or close.

Each voice also has a reference to the "shred" which is currently managing its envelope. If you should on() a voice while it is still fading out, the shred doing the fading is killed and the new, fade-in shred takes over.

That the shreds go around killing each other really bothers me. What happens when a voice is told to on and off at the same ChucK time? Who knows? However, I cannot argue with the results: this is my first implementation that works well enough that I don't feel like my system for handling voices is getting in the way when I banging out notes. It's hard to argue with results, even when race conditions lurk behind every corner.

The code I'm using this for requires a special MIDI device that I've been working with recently, but here is some pseudo-code that should work just as well as a demonstration.

for(0 => int i; i < numVoices; i++) {
    SinOsc s => outs[i];
    0.4 => s.gain; Std.mtof(60 + i) => s.freq;
}

spork ~ on(0, 1.0);
500::ms => now;
spork ~ on(1, 1.0);
300::ms => now;
spork ~ off(0);
spork ~ on(2, 1.0);
500::ms => now;
spork ~ off(1);
spork ~ off(2);
1::second => now;

'Course if there are better solutions out there, I'd love to hear them.

Copter Music

2008-05-14T11:00:58-04:00

Tentatively-titled "Copter Music" is a music piece for PLOrk (the Princeton Laptop Orchestra) performed by playing a 3D-ified version of a game with which you may be familiar, and which I re-made in C# to use Wiimote controls a last summer.

It's back! This time, built using openFrameworks (a C++ application holster for installations with graphics and sound) and ChucK. Oh, and you control it by tipping your (Mac) laptop.

I can't share much now because it's not quite finished, but one person was quoted saying, "This is fun enough that I would play it on its own!"

GLApp

2008-05-17T02:29:54-04:00

Updated May 16, 2008, in the late, late night: Moved project to GitHub

I had to get this out of my system so that I could get back to focusing on exams. You don't understand; this has nothing to do with any of the finals or projects I have coming up in the next two days. Oh god, why did this bug have to bite today.

It's a Ruby mini-framework for OpenGL/GLUT applications. It's a raw, unconfigurable, toy, and it's small enough to understand in one sitting so that you can get over that initial hump of starting a GLUT application and just start coding already.

You could say it's Processing-inspired, but that would be an insult to Processing. I don't wrap anything good (yet), so you still need to know how to use the drawing calls wrapped by ruby-opengl, and deal with popping pushed matrices, and all the good stuff you can learn at NeHe's OpenGL tutorial pages, like everyone else on the Internet.

Why do this? Handling OpenGL initialization is already enough to almost make 3D fun. You get to jump right in and start drawing!

Getting GLApp

I've published the source code in a GLApp GitHub repository, which isn't meant to be scary. If you know how to use git, then great, but if not, just click the "Download" link at the top of the project page there.

Or click here: download GLApp from GitHub.

Using GLApp

It's really easy; all you need are the ruby-opengl gem and the gl_app.rb file. Check out triangles.rb in the examples/ directory of the download for a fairly simple example (the one I used to generate the graphic at the top of this page). Here is an excerpt from the README:

It's simple:

  1) require "gl_app"
  2) include GLApp
  3) override as many of the callbacks as you need:
     - setup
     - draw
     - update(seconds)
     - special_keyboard(key, modifiers)
     - mouse_click(button, state, x, y)
     - mouse_active_motion(x, y)
     - mouse_passive_motion(x, y)
     - keyboard(key, modifiers)
  4) call go_windowed(width, height)

Look at the scripts in the examples/ directory.
In fact, here's one:

  require "gl_app"
  include GLApp

  def draw
    glTranslate 0, 0, -5
    glutSolidCube 2
  end

  go_windowed 800, 600

Daily Crap 2008-05-30

2008-05-30T00:34:36-04:00

Consider my mind blown:

struct vtable *Vector_vt = 0;

int Vector_length(struct Vector *vector) {
  return vector->length;
}

void initialise(void) {
  ...
  Vector.vt = send(vtable, s.allocate, sizeof(struct vtable));
  send(Vector_vt, s.addMethod, s_length, Vector_length);
  ...
}

int length(struct object *object) {
  return send(object, s_length);
}

Hopefully I'll have read and understood enough soon to be able to write about and use their system. From the papers I've read already, I'm blown away. Regardless of how old the ideas are, they're new to me!

Daily Crap 2008-06-07

2008-06-07T21:46:48-04:00

My boss' programming history. It's funny thinking back on how I was so psyched about programming, then Visual Basic came out and trying to move into GUI programming was like banging my head against a brick wall. The complexity was so much greater that it took forever to get the hang of it. It's a wonder people learn to program at all today.

Go

2008-06-09T16:02:04-04:00

Updated Jun 09, 2008, in the afternoon: Game vs Nick

I'm training myself to be a Go master. It's my way of trying to make up for my apparent lack of strategy, subtlety, and strategic subtlety.

The "Go" Facebook application [1] has been my best friend because it only requires a Facebook account (which most people seem to have) and can be used for real-time or play-by-mail–speed games.

I also have a friend who's both better than me, and willing to play several turns a day on average, which is sweet! Here is my current play log (with links you can use to check on the game, if you have a Facebook account):

Me (black) vs Min [2]. 19x19, 2-stone handicap. Black wins by ~82 (IIRC).
Me (black) vs Min [3]. 19x19, no handicap. Ongoing.
Me (white) vs William [4]. 13x13, 4-stone handicap (he pretended to be less experienced than he was ;p). Ongoing.
Me (white) vs Jon [5]. 19x19, 2-stone handicap. Ongoing.
Me (black) vs Nick. 19x19, 3-stone handicap. I won by 0.5 points! Played on his (real) board!

References

Awful Markov Chains

2008-06-25T09:35:25-04:00

As an exercise in writing inefficient Ruby code, I created these scripts for creating a Markov model [1] of bodies of text, then using it to generate realistic-looking quotations based on it! If you follow me on Twitter, you've unfortunately been subject to the results for the past day.

Creating a Model

I used the clearest, most space-inefficient method I could imagine:

Store each word in a giant hash, keyed by each word in the text, with values being arrays of succeeding words (once per occurrence)
Save the hash to disk

The hash looks like this one, generated from the sentence "save the store from the storm":

db = { "" => ["save"],
       "save" => ["the"],
       "the" => ["store", "storm"],
       "store" => ["from"],
       "from" => ["the"]
       }

When this hash is saved to disk (using Marshal), it ends up being bigger than the original text, but the format is incredibly easy to use to produce text, so it was worth it to me as a quick hack. This is the code for generating it:

# usage: ruby learn.rb db-file-name

file = ARGV[0]

# load the existing model from disk
db = Marshal.load(File.read(file)) rescue {}

# read words from $stdin; yield each with the one before
def get_words
  while $stdin.gets do
    preceding = ""
    $_.split.each do |word|
      yield preceding, word
      preceding = word
    end
  end
end

# add words to the model
get_words do |preceding, word|
  db[preceding] ||= []
  db[preceding] << word
end

# save back to disk
File.open(file, "w") { |f| f.write Marshal.dump(db) }

One important thing to note: the word at the beginning of each line is stored as occurring after "", the empty string. These are the possible starting points for generated chains…

Generating Text

Generating text is easy! I may as well show you the code first:

# usage: ruby produce.rb db-file-name max-characters

file = ARGV[0]
count = ARGV[1].to_i

# load the model
db = Marshal.load(File.read(file)) rescue {}

# define convenience method for getting a random element of an array
class Array
  def rand
    self[Kernel.rand(length)]
  end
end

words = []
last = ""
loop do
  last = db[last].rand rescue nil
  break if last.nil?
  break if (words + [last]).join(" ").length >= count
  words << last
  # break if last[/[\.\?\!]$/] # stop at an end-of-sentence marker
end

puts words.join(" ")

It's easy to explain:

Choose a first word from among those that had no preceding words during training (those at the beginning of lines)
Randomly choose a word to come next from the pool of words that came after the previous one in the training text
Continue until a word is chosen that has no successors, or the maximum number of characters is reached.

Using the training sentence from before ("save the store from the storm"), you can produce such glorious sentences as: "save the storm," "save the store from the storm," and, "save the store from the store from the store from the store from the storm."

Applications

The first thing I did of course, was train it with my plain text copy of the book of Genesis. Perhaps you do not have this text available. Why not try it with your own copy of the whole bible [2]? I've gotten choice "quotations" like:

"And in the valleys, to him, he railed on the captains of Israel, hast put their father's brothers' sons: so is in the Egyptians, so I will"
"Then delivered unto thee, that shall carry forth fruit, as for a trance"
"For God hath ought to profit, but the ground and to wife. Then said the LORD, for ye not find no light."

Then I trained it on a database dump of a forum I frequent full of h4x0rz, g4m3rz, and nubc4k3z:

"now I thought as old T20 and is my post n64 games?/??"
"Marvel Ultimate and she just some holy Francisc, work a test server when a dirty commies."
"Your MOM looks like to appear!"

Get creative.

Kicking it up a notch: Twitter

Using this power, you can become nearly as annoying a tweeter as I am! This script downloads a user's Twitter RSS feed, parses it with Hpricot [3] (so you need the gem), then outputs new tweets to stdout (old tweets are cached). This output is meant to be piped into the learn.rb script … for generating tweets that are not entirely unlike those the poor victim wrote themselves.

The example code has _why [4]'s Twitter feed information hard-coded near the top, for ultimate randomness. The ID number is taken from the URL for his RSS feed on Twitter -- feel free to change this to the ID number for any user you'd like to mimic.

# usage: ruby getwhy.rb | ruby learn.rb why

require "rubygems"
require "hpricot"
require "open-uri"

@id = "3573501"
@file = "_why_tweets"

rss = Hpricot(open("http://twitter.com/statuses/user_timeline/#{@id}.rss"))
new_statuses = (rss/"item title").map { |i| i.inner_html }.map { |i| i.split(" ", 2).last }
saved_statuses = Marshal.load(File.read(@file)) rescue []

never_before_seen = new_statuses - saved_statuses
statuses = new_statuses | saved_statuses
File.open(@file, "w") { |f| f.write Marshal.dump(statuses) }
puts never_before_seen.join("\n")

Daily Crap 2008-06-27

2008-06-27T10:46:18-04:00

I found a nice present in my inbox this morning: "a port of Plan 9 to FreeBSD, Linux, and OS X, using the vx32 sandboxing library" (which has been used for some other nifty applications as well). 9vx pegs my CPU on OS X 10.5. Kind of wish I had the skills to help with it.

Solving Sudoku in OCaml

2008-07-18T23:25:18-04:00

I wrote a modest sudoku solver in OCaml to keep my mind sharp by learning a programming language. OCaml comments are surrounded by (* and *) so you should be able to copy everything beneath this rule directly into a .ml file and execute it with OCaml.

(* sudoku.ml *)

(* Range helper: (1--3) -> [1; 2; 3] *)
let (--) a b = Array.to_list (Array.init (b - a + 1) ((+) a));;

(* The data structure I use for a sudoku grid is a map from (col, row) coordinates to sets of integers. A grid will have all the coordinates (1, 1), (1, 2), … (9, 9) present; each square is a set of the integers which are candidates for the actual value of the square. For a solved puzzle, each set will have exactly one integer. *)

(* Map from (x, y) -> Set *)
let coord_compare (x1, y1) (x2, y2) =
  compare (x1 + y1 * 9) (x2 + y2 * 9);;
module CoordMap = Map.Make(struct type t = (int * int) let compare = coord_compare end);;

(* set of ints *)
module IntSet = Set.Make(struct type t = int let compare = compare end);;

(* There is basic visualization support while the puzzle is being solved. A 9x9 grid is shown, each square containing up to 9 filled circles (one for each candidate for that square) with the exception of squares with only one number — in those the number itself is displayed. This way a solved puzzle looks as it would on paper. *)

(* graphics *)
open Graphics;;
let box_width = 40;;
let box_x col = col * box_width + (15 * ((col - 1) / 3));;
let box_y row = (9 - row + 1) * box_width + (15 * ((9 - row) / 3));;
let display_possibility (col, row) num =
  let props n = (((n * 2) + 1) * box_width) / 6 in
  let xoff = props ((num - 1) mod 3) in
  let yoff = box_width - (props ((num - 1) / 3)) in
  set_color (rgb 0 0 128) ;
  fill_circle ((box_x col) + xoff) ((box_y row) + yoff) (box_width / 8);;
let display_box (col, row) possibilities =
  set_color black ;
  draw_rect (box_x col) (box_y row) box_width box_width ;
  if IntSet.cardinal possibilities = 1 then (
    moveto ((box_x col) + box_width / 2) ((box_y row) + box_width / 2) ;
    draw_string (string_of_int (IntSet.choose possibilities))
  ) else IntSet.iter (display_possibility (col, row)) possibilities;;
let display_grid grid = clear_graph () ; CoordMap.iter display_box grid;;

(* creating a grid (map of coordinates to sets of possible numbers) *)
(* grid coordinates are 1-indexed *)
let init_box () = List.fold_right IntSet.add (1--9) IntSet.empty;;
let coord_seq = List.concat (List.map (fun x -> List.map (fun y -> (x, y)) (1--9)) (1--9));;
let grid = List.fold_right (fun x -> CoordMap.add x (init_box ())) coord_seq CoordMap.empty;;

(* grid displaying functions *)
let string_of_coords (x, y) =
  "(" ^ (string_of_int x) ^ ", " ^ (string_of_int y) ^ ")";;
let string_of_possibilities possibilities =
  IntSet.fold (fun x -> (^) (string_of_int x ^ " ")) possibilities "";;
let string_of_box coords possibilities =
  (string_of_coords coords) ^ ": " ^ (string_of_possibilities possibilities);;
let print_grid grid =
  for y = 1 to 9 do
    for x = 1 to 9 do
      print_endline (string_of_box (x, y) (CoordMap.find (x, y) grid))
    done
  done;;

(* solved? *)
let is_inconsistent grid =
  let any_empty k v m = m || (IntSet.cardinal v = 0) in
  CoordMap.fold any_empty grid false;;
let is_complete grid =
  let all_done k v m = m && (IntSet.cardinal v = 1) in
  CoordMap.fold all_done grid true;;
let is_done grid =
  is_inconsistent grid || is_complete grid;;

(* eliminate_box num coords grid returns a grid with the box at the given coordinates having the given number removed from its set. eliminate_all_but num coords grid removes every number except the one given. These are the basis for the other functions which do the same for rows, columns, and sectors (one of the 3x3 sub-sections of the grid).

select num (col, row) grid is the function actually used for manipulating a game grid. It is the equivalent of writing in a number as "for sure" and crossing out the ones in its column, row, and sector which it makes impossible. It also 'cascades' once so that if more "for sures" are found, the same selection process is performed on them. )*

(* elimination *)
(* sectors are 0-indexed *)
let sector_coords col row = (col - 1) / 3, (row - 1) / 3;;
let rec eliminate_box num coords grid =
  CoordMap.add coords (IntSet.remove num (CoordMap.find coords grid)) grid
and eliminate_all_but num coords grid =
  CoordMap.add coords
    (IntSet.inter
      (CoordMap.find coords grid)
      (IntSet.add num IntSet.empty))
     grid
and eliminate_in_row num except_coords row grid =
  let doit grid col =
    if (col, row) = except_coords then grid
    else eliminate_box num (col, row) grid
  in
  List.fold_left doit grid (1--9)
and eliminate_in_col num except_coords col grid =
  let doit grid row =
    if (col, row) = except_coords then grid
    else eliminate_box num (col, row) grid
  in
  List.fold_left doit grid (1--9)
and eliminate_in_sector num except_coords (sector_x, sector_y) grid =
  let doit grid (col, row) =
    if (col, row) = except_coords then grid
    else eliminate_box num (col, row) grid
  in
  let coords = [sector_x * 3 + 1, sector_y * 3 + 1;
                sector_x * 3 + 2, sector_y * 3 + 1;
                sector_x * 3 + 3, sector_y * 3 + 1;
                sector_x * 3 + 1, sector_y * 3 + 2;
                sector_x * 3 + 2, sector_y * 3 + 2;
                sector_x * 3 + 3, sector_y * 3 + 2;
                sector_x * 3 + 1, sector_y * 3 + 3;
                sector_x * 3 + 2, sector_y * 3 + 3;
                sector_x * 3 + 3, sector_y * 3 + 3;] in
  List.fold_left doit grid coords
and select_without_cascade num (col, row) grid =
  let grid = eliminate_in_row num (col, row) row grid in
  let grid = eliminate_in_col num (col, row) col grid in
  let grid = eliminate_in_sector num (col, row) (sector_coords col row) grid in
  let grid = eliminate_all_but num (col, row) grid in
  grid
and cascaded_select grid =
  let f coords possibilities grid =
    if IntSet.cardinal possibilities = 1 then
      select_without_cascade (IntSet.choose possibilities) coords grid
    else
      grid
  in
  CoordMap.fold f grid grid
and select num (col, row) grid =
  let grid = select_without_cascade num (col, row) grid in
  cascaded_select grid;; (* TODO: repeat until cascading has no effect *)

(* For some puzzles, you just have to start guessing. solve_by_guessing grid does it in a fairly naïve way: at each level of recursion, a list of all the possible guess is made, then each is made and the resulting grid is again passed to solve_by_guessing grid. This is a depth-first search of all the possible ways to solve the puzzle – basically brute-force – and is far too inefficient to ever solve problems that require more than a few numbers to be guessed. *)

(* Warning: just pretend that this code doesn't exist. *)

(* still too many choices? guess! *)
let possible_moves grid =
  let possibility_list coords possibilities =
    let f p arr = (coords, p) :: arr in
    if IntSet.cardinal possibilities > 1 then
      IntSet.fold f possibilities []
    else []
  in
  let f coords possibilities arr =
    (possibility_list coords possibilities) :: arr
  in
  let lcompare a b = compare (List.length a) (List.length b) in
  let p = List.sort lcompare (CoordMap.fold f grid []) in
  List.concat p;;
let solve_by_guessing grid =
  let rec recurse grid =
    display_grid grid ;
    (* wait_next_event [Key_pressed] ; *)
    if is_complete grid then (grid, "solved")
    else if is_inconsistent grid then (grid, "inconsistent")
    else try_possibilities grid
  and try_possibilities grid =
    let rec loop moves =
      (* print_moves moves ; *)
      match moves with 
        [] -> (grid, "no solution")
      | (coords, num) :: rest ->
          (* print_endline ("trying " ^ (string_of_int num) ^ " at " ^ (string_of_coords coords)) ; *)
          let new_grid, state = recurse (select num coords grid) in
          if state = "solved" then (new_grid, "solved")
          else loop rest
    in
    loop (possible_moves grid)
  in
  recurse grid;;

(* ask the user for the numbers already on the grid *)
let rec ask_loop grid =
  try
    print_string "Num: " ;
    let num = read_int () in
    print_string "Col: " ;
    let col = read_int () in
    print_string "Row: " ;
    let row = read_int () in
    print_endline ("Selecting " ^ (string_of_int num) ^
      " @ (" ^ (string_of_int col) ^ ", " ^ (string_of_int row) ^ ")") ;
    display_grid grid ;
    (* wait_next_event [Key_pressed] ; *)
    let new_grid = select num (col, row) grid in
    if is_done new_grid then new_grid
    else ask_loop new_grid
  with
      Failure "int_of_string" -> grid
    | End_of_file -> grid;;

(* begin *)
open_graph " 470x470";;
let grid = ask_loop grid;;
let grid = if is_done grid then grid else (
  print_endline "** TIME FOR GUESSING **" ;
  let grid, solved = solve_by_guessing grid in
  print_endline solved ;
  grid
);;
print_endline "** FINISHED **";;

display_grid grid ;;
wait_next_event [Key_pressed] ;;