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

C-ORM: docs, API.

Last 100 entries

Why Information Grows; The Blindness Of The Chilean Elite; Some Victoriagate Links; This Is Why I Left StackOverflow; New TLS Implementation; Maths for Physicists; How I Am 8; 1000 Word Philosophy; Cyberpunk Reading List; Detailed Discussion of Message Dispatch in ParserCombinator Library for Julia; FizzBuzz in Julia w Dependent Types; kokko - Design Shop in Osaka; Summary of Greece, Currently; LLVM and GPUs; See Also; Schoolgirl Groyps (Maths); Japanese Lit; Another Example - Modular Arithmetic; Music from United; Python 2 and 3 compatible alternative.; Read Agatha Christie for the Plot; A Constructive Look at TempleOS; Music Thread w Many Recommendations; Fixed Version; A Useful Julia Macro To Define Equality And Hash; k3b cdrom access, OpenSuse 13.1; Week 2; From outside, the UK looks less than stellar; Huge Fonts in VirtualBox; Keen - Complex Emergencies; The Fallen of World War II; Some Spanish Fiction; Calling C From Fortran 95; Bjork DJ Set; Z3 Example With Python; Week 1; Useful Guide To Starting With IJulia; UK Election + Media; Review: Reinventing Organizations; Inline Assembly With Julia / LLVM; Against the definition of types; Dumb Crypto Paper; The Search For Quasi-Periodicity...; Is There An Alternative To Processing?; CARDIAC (CARDboard Illustrative Aid to Computation); The Bolivian Case Against Chile At The Hague; Clear, Cogent Economic Arguments For Immigration; A Program To Say If I Am Working; Decent Cards For Ill People; New Photo; Luksic And Barrick Gold; President Bachelet's Speech; President Bachelet's Speech; Baltimore Primer; Baltimore Primer; libxml2 Parsing Stream; libxml2 Parsing Stream; configure.ac Recipe For Library Path; configure.ac Recipe For Library Path; The Davalos Affair For Idiots; Not The Onion: Google Fireside Chat w Kissinger; Not The Onion: Google Fireside Chat w Kissinger; Bicycle Wheels, Inertia, and Energy; Bicycle Wheels, Inertia, and Energy; Another Tax Fraud; Google's Borg; Google's Borg; A Verion That Redirects To Local HTTP Server; Spanish Accents For Idiots; Spanish Accents For Idiots; Aluminium Cans; Aluminium Cans; Advice on Spray Painting; Advice on Spray Painting; Female View of Online Chat From a Male; Female View of Online Chat From a Male; UX Reading List; UX Reading List; S4 Subgroups - Geometric Interpretation; S4 Subgroups - Geometric Interpretation; Fucking Email; Fucking Email; The SQM Affair For Idiots; The SQM Affair For Idiots; Using Kolmogorov Complexity; Using Kolmogorov Complexity; Oblique Strategies in bash; Oblique Strategies in bash; Curses Tools; Curses Tools; Markov Chain Monte Carlo Without all the Bullshit; Markov Chain Monte Carlo Without all the Bullshit; Email Para Matias Godoy Mercado; The Penta Affair For Idiots; The Penta Affair For Idiots; Example Code To Create numpy Array in C; Example Code To Create numpy Array in C; Good Article on Bias in Graphic Design (NYTimes); Good Article on Bias in Graphic Design (NYTimes); Do You Backup githb?; Do You Backup github?

© 2006-2015 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