| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

Last 100 entries

Interesting (But Largely Illegible) Typeface; Retiring Essentialism; Poorest in UK, Poorest in N Europe; I Want To Be A Redneck!; Reverse Racism; The Lost Art Of Nomography; IBM Data Center (Photo); Interesting Account Of Gamma Hack; The Most Interesting Audiophile In The World; How did the first world war actually end?; Ky - Restaurant Santiago; The Black Dork Lives!; The UN Requires Unaninmous Decisions; LPIR - Steganography in Practice; How I Am 6; Clear Explanation of Verizon / Level 3 / Netflix; Teenage Girls; Formalising NSA Attacks; Switching Brakes (Tektro Hydraulic); Naim NAP 100 (Power Amp); AKG 550 First Impressions; Facebook manipulates emotions (no really); Map Reduce "No Longer Used" At Google; Removing RAID metadata; New Bike (Good Bike Shop, Santiago Chile); Removing APE Tags in Linux; Compiling Python 3.0 With GCC 4.8; Maven is Amazing; Generating Docs from a GitHub Wiki; Modular Shelves; Bash Best Practices; Good Emergency Gasfiter (Santiago, Chile); Readings in Recent Architecture; Roger Casement; Integrated Information Theory (Or Not); Possibly undefined macro AC_ENABLE_SHARED; Update on Charges; Sunburst Visualisation; Spectral Embeddings (Distances -> Coordinates); Introduction to Causality; Filtering To Help Colour-Blindness; ASUS 1015E-DS02 Too; Ready Player One; Writing Clear, Fast Julia Code; List of LatAm Novels; Running (for women); Building a Jenkins Plugin and a Jar (for Command Line use); Headphone Test Recordings; Causal Consistency; The Quest for Randomness; Chat Wars; Real-life Financial Co Without ACID Database...; Flexible Muscle-Based Locomotion for Bipedal Creatures; SQL Performance Explained; The Little Manual of API Design; Multiple Word Sizes; CRC - Next Steps; FizzBuzz; Update on CRCs; Decent Links / Discussion Community; Automated Reasoning About LLVM Optimizations and Undefined Behavior; A Painless Guide To CRC Error Detection Algorithms; Tests in Julia; Dave Eggers: what's so funny about peace, love and Starship?; Cello - High Level C Programming; autoreconf needs tar; Will Self Goes To Heathrow; Top 5 BioInformatics Papers; Vasovagal Response; Good Food in Vina; Chilean Drug Criminals Use Subsitution Cipher; Adrenaline; Stiglitz on the Impact of Technology; Why Not; How I Am 5; Lenovo X240 OpenSuse 13.1; NSA and GCHQ - Psychological Trolls; Finite Fields in Julia (Defining Your Own Number Type); Julian Assange; Starting Qemu on OpenSuse; Noisy GAs/TMs; Venezuela; Reinstalling GRUB with EFI; Instructions For Disabling KDE Indexing; Evolving Speakers; Changing Salt Size in Simple Crypt 3.0.0; Logarithmic Map (Moved); More Info; Words Found in Voynich Manuscript; An Inventory Of 3D Space-Filling Curves; Foxes Using Magnetic Fields To Hunt; 5 Rounds RC5 No Rotation; JP Morgan and Madoff; Ori - Secure, Distributed File System; Physical Unclonable Functions (PUFs); Prejudice on Reddit; Recursion OK; Optimizing Julia Code; Cash Handouts in Brazil; Couple Nice Music Videos; It Also Works!

© 2006-2013 Andrew Cooke (site) / post authors (content).

Installing Gecode/J (Opensuse)

From: "andrew cooke" <andrew@...>

Date: Sat, 13 Sep 2008 20:29:23 -0400 (CLT)

First, you need the C library - http://www.gecode.org/download.html

This is just the usual ./configure --prefix=... ; make; make install

Next, the Java library - http://www.gecode.org/gecodej/download.html

This needs to find the C libs installed previously, so if they weren't in
a standard location you'll need to do something like:

export PKG_CONFIG_PATH=".../gecode-2.2.0/lib/pkgconfig"

before the ./configure --prefix=... ; make; make install

(You also need a JDK, ant, etc).

The documentation can be built with "make doc", but it's doxygen,not
javadoc, which is no doubt much cooler, but is also frustrating if you're
a seasoned Java coder (I suspect this is written by a bunch of academics
who are only touching Java in a bid to be popular...).  You can build
javadoc using

javadoc -d javadoc -subpackages org -sourcepath .

(assuming you're in the main gecodej dir) but it has doxygen markup all
over the place.

And the docs suck big time.  There's a general intro to constraints at
http://kti.mff.cuni.cz/~bartak/constraints/ but it's completely separate
from Gecode (so it's not clear how things tie in) and the english isn't
that great .

There's also a Ruby interface Gecode/R - http://gecoder.rubyforge.org/ -
which as a few more examples.

Ah well.  Onwards...

Andrew

Programming Constraint Services

From: "andrew cooke" <andrew@...>

Date: Sat, 13 Sep 2008 23:49:27 -0400 (CLT)

Just found a good reference for all this - Christian Schulte's thesis -
http://www.mozart-oz.org/papers/abstracts/ProgrammingConstraintServices.html
+
http://www.ps.uni-sb.de/PapersOz/ProgrammingSysLab/ProgrammingConstraintServices.pdf

I am not sure it describes Gecode - I think it's describing the Oz
precursor - but in the first couple of chapters it's already a answered a
whole pile of questions I had (probably worth reading the article I linked
to earlier first since as general background).  If understanding the
implementation details (at some limited ;evel) will help you understand
the system, this is for you.

Will continue reading tomorrow.

Andrew

Commented GecodeJ Example

From: "andrew cooke" <andrew@...>

Date: Sun, 14 Sep 2008 11:33:22 -0400 (CLT)

This is Queens (again), but with a bit more explanation that in the
GecodeJ docs.  The output looks like:

....
Copy constructor for:
Q.......
..Q.....
????????
????????
????????
????????
????????
????????
Result:
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....


package org.acooke.jbv.example;

import static org.gecode.Gecode.branch;
import static org.gecode.Gecode.distinct;

import java.util.Iterator;

import org.gecode.DFSIterator;
import org.gecode.IntValBranch;
import org.gecode.IntVar;
import org.gecode.IntVarBranch;
import org.gecode.Options;
import org.gecode.Space;
import org.gecode.VarArray;

/**
 * A space is a node in the search tree - it does the same work as a
 * stack frame might in a recursive search.
 */
public class Queens extends Space {

  public static final int BOARD_SIZE = 8;

  /**
   * We force there to be one queen per row by the way we store the
   * data (we store only a column for each row, rather than a [row,
   * column] pair).  This is a good thing - it gives us a constraint
   * for free and reduces the search space.
   */
  VarArray<IntVar> columnForRow;

  /**
   * This is used to create the initial space, so we define the
   * starting conditions.
   */
  public Queens() {
    super("Queens");
    // the VarArray needs a reference to the space and a size
    columnForRow = new VarArray<IntVar>(this, BOARD_SIZE,
        // the next args construct the contents by calling
        // the constructor of the given class with the args
        // (which in this case will be min and max values -
        // the domain limits are inclusive(!), hence the "-1")
        IntVar.class, 0, BOARD_SIZE-1);
    // (note - this is a static import from Gecode which provides a
    // selection of pre-packaged constraints)
    // add the constraint that every value is distinct
    distinct(this, columnForRow);
    // another constraint saying that
    // x[i] + delta[i] != x[j] + delta[j]
    // gives us one constraint along diagonals
    distinct(this, diagonals(1), columnForRow);
    // and this gives the other
    distinct(this, diagonals(-1), columnForRow);
    // once all constraints have been applied we may still need to
    // search.  so here we describe how to partition the remaining
    // space with an additional constraint
    // http://kti.mff.cuni.cz/~bartak/constraints/ordering.html
    // (again this is a static import from Gecode)
    // so we need to give the space and variables
    branch(this, columnForRow,
        // @see IntVarBranch - this describes which variable to pick
        IntVarBranch.INT_VAR_NONE, // anything!
        // @see IntValBranch - what to do with the values
        IntValBranch.INT_VAL_SPLIT_MAX); // split in half
  }

  /**
   * Offsets for constraints on diagonals.
   * @param scale 1 or -1, to give the two directions.
   * @return
   */
  private static int[] diagonals(int scale) {
    int[] delta = new int[BOARD_SIZE];
    for (int i = 0; i < BOARD_SIZE; ++i) {
      delta[i] = i * scale;
    }
    return delta;
  }

  /**
   * This is used to clone the space for child nodes.
   * @param share If true, data can be shared (basically, if share is
   * false you've got to expect that different instances will be accessed
   * by different threads).
   * @param s Another instance of this class to copy (not sure why Space
   * doesn't have the signature Space<S extends Space>).
   */
  protected Queens(Boolean share, Queens q) {
    super(share, q);
    System.err.print("Copy constructor for:\n" + q.toString());
    // there's a constructor that does all the work for us
    columnForRow = new VarArray<IntVar>(this, share, q.columnForRow);
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    for (IntVar queen: columnForRow) {
      for (int column = 0; column < BOARD_SIZE; ++column) {
        // we need to be careful here - we can't access values if
        // they haven't been assigned.
        if (! queen.assigned()) {
          builder.append("?");
        } else if (queen.val() == column) {
          builder.append("Q");
        } else {
          builder.append(".");
        }
      }
      builder.append("\n");
    }
    return builder.toString();
  }

  public static void main(String[] args) {
    Queens space = new Queens();
    // let's use depth first search with whatever the defaults are
    // (there doesn't seem to be an interface that exposes Iterable)
    Iterator<Queens> results =
      new DFSIterator<Queens>(space, new Options());
    while (results.hasNext()) {
      System.out.println("Result:\n" + results.next().toString());
    }
  }

}

Not to be popular...

From: "andrew cooke" <andrew@...>

Date: Mon, 15 Sep 2008 08:54:37 -0400 (CLT)

---------------------------- Original Message ----------------------------
From:    "Mikael Zayenz Lagerkvist" <zayenz@...>
Date:    Mon, September 15, 2008 5:42 am
--------------------------------------------------------------------------

"I suspect this is written by a bunch of academics
who are only touching Java in a bid to be popular..."

Well, we might be academics, but the Java interface was done out of
neccessity, not to be popular.

Cheers,
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/

GecodeJ Not for "Real Use"

From: "andrew cooke" <andrew@...>

Date: Mon, 15 Sep 2008 08:56:41 -0400 (CLT)

Turns out GecodeJ is only intended for teaching; for decent efficiency you
apparently need to use the C++ library.

http://www.ps.uni-sb.de/pipermail/gecode-users/2008-September/002464.html

Big pity...

Andrew

Choco?

From: "andrew cooke" <andrew@...>

Date: Mon, 15 Sep 2008 09:08:24 -0400 (CLT)

I missed this earlier.  At first glance it seems to have some of the same
annoyances as GecodeJ (eg ranges are inclusive instead of half open), but
the documentation is hugely better: there's a readable guide at
http://choco-solver.net/index.php?title=User_guide and javadocs at
http://choco.sourceforge.net/api/

Also, it seems to be a pure Java implementation, so hopefully extending it
won't be so tricky.

Andrew

Comment on this post