Wishful Coding

Last night my brother told me about this puzzle where you have a square of 3x3 that you have to fill with 1-9 in a way that all columns and rows sum up to 15.(this is not a real magic square, but anyway)

After discussig our strategies for a bit, we went on to think about generalising the problem to bigger squares.

The next morning we tested our theory in excel and produced a 4x4 square. The method we used was to fill in numbers at random, then switching them around horizontally until all collumns equalled 34 and finally switching them around vertically to make the rows work out.

Once we started thinking about doing the 5x5 grid, I suggested I might do it faster using core.logic. I was wrong.

user=> (time (test/magic 3))
(1 5 9)
(6 7 2)
(8 3 4)
"Elapsed time: 451.880413 msecs"
nil
user=> (time (test/magic 4))
(1 2 15 16)
(7 8 9 10)
(12 11 6 5)
(14 13 4 3)
"Elapsed time: 6386.272944 msecs"
nil
user=> (time (test/magic 5))
OutOfMemoryError GC overhead limit exceeded

The code simply generates N² logic variables in the 1-9 domain that are distinct. These are then sliced up in rows and collumns and constrained to sum up to the “magic number”.

(ns test
  (:refer-clojure :exclude [==])
  (:use clojure.core.logic
        clojure.pprint)
  (:require [clojure.core.logic.fd :as fd]))

(defn grid [n] (repeatedly (* n n) lvar))

(def rows partition)

(defn cols [n grid] (apply map list (rows n grid)))

(defn sum [ls res]
  (conde
    ((== ls []) (== res 0))
    ((== ls [res]))
    ((fresh [h t inter]
       (conso h t ls)
       (fd/+ h inter res)
       (sum t inter)))))

(defn magic [n]
  (let [g (grid n)
        nums (range 1 (inc (* n n)))
        ndom (apply fd/domain nums)
        lsum (/ (apply + nums) n)
        lines (concat (rows n g) (cols n g))]
    (->> (run 1 [q]
           (everyg #(fd/dom % ndom) g)
           (fd/distinct g)
           (everyg #(sum % lsum) lines)
           (== q g))
      first
      (rows n)
      (map println)
      dorun)))

I suspect I can still beat my brother to 6x6 by implementing one of the techniques outlined on wikipedia in a good old imperative style, especially since he’s not even trying.

I’m playing with Pallet to setup an IRC server and bouncer. Pallet uses vmfest to deploy to VirtualBox.

While vmfest comes with some prepared images, I found that my laptop would not run them, so I made my own, with a lot of help from Antoni Batchelli.

• Create an image in VirtualBox with a NAT and host-only network.
• Install your favourite distro.
• Install an SSH server.
• Setup passwordless sudo

• Make sure /etc/network/interfaces contains both eth0 and eth1.

    auto eth0
    iface eth0 inet dhcp
    auto eth1
    iface eth1 inet dhcp
  

• Update and upgrade all packages.
• Install the guest additions
• On some Debian based distros, remove persistent-net.rules.

This should give you a working machine, but we’re not done yet. You still need to make the hard disk multi-attachable.

If you where to use this image in Pallet, you could only use it once. Multiattach means that every time a machine is made, a new copy-on-write image is created so the original stays intact.

To do this, delete the VM, but not the vdi file, and run the following command:

VBoxManage modifyhd the/disk.vdi --type multiattach

Finally, you need to create a meta file with the same name as the disk image, but with the .meta extension. As an example:

 {:os-type-id "Ubuntu_64",
  :sudo-password "vmfest",
  :no-sudo false,
  :username "vmfest",
  :os-family :ubuntu,
  :os-version "12.04",
  :os-64-bit true,
  :password "vmfest",
  :description "Ubuntu 12.04 (64bit)"
  :packager :apt}

brain dump alert

I had read this article on core.logic a few days back, and while making myself a dinner, I came up with this analogy.

At first, I was confused about disjunction and conjunction, so let’s start with the Prolog cook.

The prolog cook cooks depth-first. The cook has several recipes and steps to produce them. The first recipe on the list is an egg with ham and cheese.

The cook bakes the egg on top of the ham, adds some salt, finds out there is no cheese, throws everything away and moves on to the next recipe.

The next recipe is is a simple pasta. The cook checks if there is pasta, herbs, tomato, and finally checks to see how much water is in the tap.

Next up is the miniKanren cook. This cook has fair disjunction, but unfair conjunction.

So the cook looks at her recipes, picks the egg recipe, checks if there is an egg. Then, picks another recipe, like a pasta, checks if there is any pasta.

The cook keeps going over the recipes, discarding ones that can’t be made. But at some point this cook will also check how much water is in the tap. And keep checking until there is no more water.

Finally, the fair cook, with fair conjunction.

This cook goes over his recipes the same way the miniKanren cook does, but upon checking for water, this cook opens the tap and continues cooking while keeping an eye on the tap.

Maybe the recipe can be adjusted not to check for all the water. Even the fair cook is wasting a lot of water while doing other stuff, but at least she does other stuff in the meantime.

There have been very successful Prolog cooks, but not all recipes can be adjusted to work for the Prolog cook.