The Google Hash Code 2015 selection round was yesterday. This post summarizes the problem of the contest, and the approach followed by my team (ENS Ulm 1), providing code for a simplified version of our approach that achieves a score of 388 with less than 100 lines of code.

You can read the problem statements in French and English and the input file. In brief, the task was a knapsack variant where you had to assign servers to positions in a grid, and then assign the servers to groups to maximize a certain function that favors balanced assignments.

The decision problem associated to the task (is it possible to achieve score n given the set of constraints) is NP-complete. It is in NP because one can represent solutions to the problem in polynomial space, and test in polynomial time whether a solution achieves the required score and satisfies the input constraints. Hence, an NP algorithm to solve the problem is to guess a solution, check that it is indeed a solution, and check that it achieves the required score. It is NP-hard by a reduction from the NP-hard partition problem. Consider a multiset of numbers that is the input to the partition problem. Create an instance of the Hash Code problem by making this the multiset of the capacities of servers, with all servers having size one. Now, say you have only two rows, a number of columns that is larger than the number of servers, no forbidden squares, and one single group to create. The maximal possible capacity (half of the total capacity) can be achieved if and only if the original multiset of numbers can be partitioned in two sets with equal sums (the set of servers in the first row, and the set of servers in the second row; clearly it is never useful to not use a server in this case, because all can fit on the grid). This reduction from the partition problem to (a very restricted case of) the Hash Code problem shows that it is NP-hard.

Of course, this hardness proof is not relevant in practice, because the contest task was to solve the problem on one specific instance. Hence, in the four hours or so that the contest lasted, the idea was to try heuristics to reach the best possible solution on that specific instance.

My team (ENS Ulm 1) reached the top position one hour after the start of the contest, and stayed there for almost two hours until other teams caught up with us. So we found a fairly good basic solution quickly but then we didn't optimize it very well. (By contrast, we were beaten by teams that had a worse initial solution but better incremental optimizations.) The goal of this post is to explain the basic strategy that we coded in one hour. I give an explanation of the strategy in English, and then a cleaned-up version of the code for it (less than 100 lines!). As this is a simplification of our solution, its final score is 388 (and not 400 as we finally achieved); we conclude by the additional ideas that are not shown in the code.

Strategy

The solution is entirely greedy, meaning that it never changes its mind about the choices that it makes, and does all choices in sequence, in a certain order, and optimizing certain criteria.

We try to place each server sequentially. However, we consider them according to a smart (greedy) order: we sort them by decreasing capacity per cell. In other words, we try to place first the servers that give the most capacity divided by the number of cells that they use up. In case of ties, we sort servers by decreasing size, because when packing it is more efficient to pack larger items first.

For each server, we greedily assign it to a group by choosing the group with lowest guaranteed capacity. This means that we compute the guaranteed capacity of each group: the capacity that is guaranteed to remain for any row deletion, which is just the total capacity of servers assigned to the group minus the maximum over rows of the capacity of servers of this row assigned to the group. Once the group is chosen, we try to find room for the server on the grid. If we can, we will place it there and assign it to the chosen group.

To place the server, we consider all rows in the following order: we sort them by ascending capacity for the chosen group. The intuition is that we would rather put the server on a row where the existing capacity for this group is as small as possible, to balance the capacity of the group on all rows and minimize the impact of the row deletion. Then, in every row considered in that order, we try to place the server greedily by finding the first sequence of contiguous free cells of sufficient size. We place the server whenever we find a suitable location for it, otherwise we choose not to use the server. We then continue with the next server.

To make this faster, we maintain the following information: the table of used cells (initialized with the forbidden cells and updated as we place servers), the sum of the capacities assigned to each group, and the sum of the capacities assigned to each group on each row.

Code

The code is written in C++ for speed, in the terse and monolithic style of programming contests. It is optimized for programmer time and running time, not at all for readability or reusability. However, I went over the code to clean it up, ensure that variables names were logical (if succinct), and add a few critical comments. This code produces a solution with score 388, runs instantaneously, and is about 100 lines long.

#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

// generous bound on all possible inputs and sizes
#define MAXN 1002

struct Server {
  int id, z, c;
  Server(int id = 0, int z = 0, int c = 0) : id(id), z(z), c(c) {}
  // sort servers by decreasing c/z then decreasing z
  bool operator< (const Server &s) const {
    // a/b < c/d iff da < bc and (e, f) < (g, h) with f,h < N iff eN+f < gN+h
    return z*s.c*MAXN + s.z < s.z*c*MAXN + z;
  }
};

// declaring those globally means we don't have to initialize them
int R, S, U, P, M;
vector<Server> serv;
char grid[MAXN][MAXN]; // filled grid cells, indexed by row, col
int capa[MAXN]; // capa[g]: total capacity allocated to group g
int gcapa[MAXN][MAXN]; // gcapa[r][g]: total capacity for group g in row r
vector<pair<int, pair<int, int> > > out; // group, row, col

int main(int argc, char **argv) {
  scanf("%d%d%d%d%d", &R, &S, &U, &P, &M);
  for (int i = 0; i < U; i++) {
    int r, s;
    scanf("%d%d", &r, &s);
    grid[r][s] = 1; // grid cell is occupied
  }
  for (int i = 0; i < M; i++) {
    int z, c;
    scanf("%d%d", &z, &c);
    serv.push_back(Server(i, z, c));
    out.push_back(make_pair(-1, make_pair(-1, -1))); // server is unused
  }

  sort(serv.begin(), serv.end());

  for (int s = 0; s < M; s++) {
    // place server s
    int guar[MAXN]; // guar[g]: guaranteed capa for group g
    for (int g = 0; g < P; g++)
      guar[g] = capa[g];
    for (int r = 0; r < R; r++)
      for (int g = 0; g < P; g++)
        guar[g] = min(guar[g], capa[g] - gcapa[r][g]); // capa if killing row r
    int mguar = guar[0], mg = 0; // min and argmin of guar over all groups
    for (int g = 0; g < P; g++)
      if (guar[g] < mguar) {
        mguar = guar[g];
        mg = g;
      }
    // mg is the group with lowest guar, assign s to mg if we can place it
    vector<pair<int, int> > rows;
    for (int r = 0; r < R; r++)
      rows.push_back(make_pair<int, int>(gcapa[r][mg], r));
    sort(rows.begin(), rows.end()); // sort rows by inc capa for group mg
    int fr = -1, fc = -1; // row and col to place s
    for (int rr = 0; rr < R; rr++) {
      int contig = 0; // count contiguous free cells
      fr = rows[rr].second;
      for (int c = 0; c < S; c++) {
        if (!grid[fr][c])
          contig++;
        else
          contig = 0;
        if (contig == serv[s].z) {
          fc = c - (serv[s].z - 1); // we can place s at (fr, fc)
          rr = R; // break out of both loops
          break;
        }
      }
    }
    if (fc >= 0) {
      // assign s to mg and place it at (fr, fc)
      capa[mg] += serv[s].c;
      gcapa[fr][mg] += serv[s].c;
      for (int d = 0; d < serv[s].z; d++)
        grid[fr][fc+d] = 1; // squares occupied by s
      out[serv[s].id] = make_pair(mg, make_pair(fr, fc));
    }
  }

  for (int i= 0 ; i < M; i++)
    if (out[i].first >= 0)
      printf("%d %d %d\n", out[i].first,
          out[i].second.first, out[i].second.second);
    else
      printf("x\n");

  return 0;
}

Extensions

To improve the performance of our solution by 12 points, we changed a few additional things:

• Once the list of servers was sorted, we kept the top of that list with the servers whose total size filled all the free space in the grid, and, assuming optimistically that we would be able to place those servers, we sorted them by decreasing size to help the packing.
• When considering the rows when choosing where to place a server, we broke ties on the assigned capacity by examining first the rows with the most free space left.
• We did random unprincipled tweaks which happened to make our solution better by one or two points.
• The last point (from 399 to 400) was gained by a brute-force incremental optimization that tried to perform random swaps.

Our brute-force incremental optimization was not very effective. I think that teams that beat us had a much more efficient approach.

There was a recent rumor about Dropbox accessing all files of your machine, and while it turns out that it was probably not true this time, I remembered getting a sinking feeling when reading this and worrying about whether my files were safe. Dropbox is one of the few pieces of proprietary software that I run, and this story reminded me that I was just blindly trusting it to not act wrong, as I was not restricting its interaction with the rest of my data in any way.

I had to change this. Hence this post, which can probably also serve as a more general description of how to properly restrict any kind of untrusted or possibly insecure programs. I should point out that I am using a Debian system, so this may vary for other Linux distros.

I want to stress that this post is not an endorsement of Dropbox, even though it may have the unintended effect of encouraging privacy-conscious users to run Dropbox because they can more easily tame it. Dropbox is software I'd really rather not run: it is a proprietary client, for a proprietary protocol, for a centralized cloud service, with no suitable privacy guarantees, it fosters network effects by rewarding users if they can attract more users, it encourages collaboration within the ecosystem and does not facilitate it across ecosystems, and forkability is low (you can have your files, but unlike, e.g., git, I'm not sure it's easy to export the history). The problem is that I need to collaborate with other people who use Dropbox, and I don't know what to suggest to them instead if they won't use a real VCS (I have complained before about this). If you're one of the few people whom I have to use Dropbox to work with, I invite you to feel guilty about all the work that I have to do for you. ;)

So this post describes how to sandbox Dropbox if you have to use it, but keep in mind that the right solution is not to use it altogether.

I took the most part from an existing guide but deviated from it in quite many respects, that I will point out. There is another more paranoid guide about running Dropbox in a chroot, but this is a bit more heavy and the guide relies on Gentoo-specific tools, so I preferred to stick with the simpler approach of running Dropbox as its own user. (There would also be the even stronger approach of running Dropbox in a virtual machine, e.g., using KVM.)¹ Of course, the crucial parts below are those where you run Dropbox as a separate user with no access to your files or the X server, plus the necessary bindfs trick to access its files as your real user. The rest is icing on the cake.

Preliminary precautions

First, of course, for what we are doing to make sense, you should make sure that the permissions of your own files with your real user are properly set up, so that the restricted dropbox user that we will create is indeed unable to access them. This probably includes setting up a suitable umask and going over your files to set the right permissions. (If you haven't done this before, you should be prepared for some problems later. For instance, when first updating this blog with my new umask, I temporarily broke it because the permissions of the compiled files were not right.)

Second, you should ensure that access to your X server is suitably restricted. Verify that xhost is returning only SI:localuser:youruser, where youruser is your user name. Otherwise, set it up. To do so automatically, I use the following script when starting my X session (I wonder if there is a cleaner way):

xhost +si:localuser:`whoami`
xhost | sed 1d | grep -v `whoami` | while read l; do
  xhost "-$l"
done

Contrary to the other guide, we will not be setting up any form of access to the X server by the dropbox user. Indeed, from my attempts, Dropbox works fine on an entirely headless system. This simplifies things a bit.

It may the case that, no matter what xhost says, local connections to the X server are still allowed, so that the dropbox user will be able to connect to it in the next step. If this happens, you need to use xauth instead. This may already have been setup for you by your graphical display manager; otherwise, you can rely on startx to do it for you. However, beware: xinit will not do it for you.

Creating the user

We create a separate dropbox user to run Dropbox, with disabled password (i.e., password authentication is not permitted) and no login shell.

sudo adduser --disabled-password dropbox
sudo chsh -s /bin/false dropbox

Contrary to the other guide, everything Dropbox-related will run as that user and live within that user's home directory. In particular, we will not be installing Dropbox in /usr/bin.

Now, open a shell as the dropbox user by issuing:

sudo su -s /bin/bash dropbox

Try to go around the home directory of your real user and check that your precious files cannot be opened. Check that, even with the DISPLAY variable correctly set, you cannot run graphical applications (e.g., xeyes).

Disk usage

I like the idea of restricting quotas so I recap it from the other guide. Edit /etc/fstab to add usrjquota=aquota.user,jqfmt=vfsv0 as mount options to the partition where the home of the dropbox user is (let's say it's /home), and do the following, adapting for your Dropbox quota (4GB here):

sudo apt-get install quota quotatool
sudo mount -o remount /home
sudo quotacheck -cavm
sudo quotaon /home
sudo quotatool -bu dropbox -l 4000MB /home

By contrast with the original guide, this is using journaled quotas, which are supposed to be more resilient; and I only set up user quotas because group quotas do not seem needed here.

Test the setup as the dropbox user by issuing, e.g.:

dd if=/dev/zero of=test bs=1M count=5000

Check that this fails with a Disk quota exceeded error. As for persisting across reboots, with my config the quotas were automatically enforced at boot (you can check this with quotaon -p /home).

Memory usage

This section restricts the overall RAM usage of the dropbox user, so that the system would not malfunction if Dropbox started allocating too much memory. It generalizes to other restrictions that can be enforced using cgroups, e.g., IO and CPU priorities, etc., but I won't go into this here.

You need to install the cgroup-tools package. Check if memory support is enabled by issuing:

cat /proc/cgroups | grep memory | awk '{print $4}'

If this returns 0, as it seems to do by default in Debian, add cgroup_enable=memory to your GRUB_CMDLINE_LINUX in /etc/default/grub, run sudo update-grub2 and reboot. (Yes, it sucks having to reboot, but I don't know a different way.)

Now a confusing thing is that for cgroups to be created and tasks to be allocated to the right cgroup, you have to edit /etc/cgconfig.conf and /etc/cgrules.conf, but for this to do anything you need to arrange for cgconfigparser and cgrulesengd to be started at boot time, and there is apparently no init script to do it in Debian (see /usr/share/doc/cgroup-tools/TODO.Debian). As a crappy hack I added to /etc/rc.local:

cgconfigparser -l /etc/cgconfig.conf
cgrulesengd

Now we can setup the cgroup for dropbox, by adding the following to /etc/cgconfig.conf to define the group (adjust 256 MB to what you think is acceptable). (This is where additional restrictions (CPU shares, IO shares, etc.) would go if you wanted to add them.)

group dropbox {
    memory {
        memory.limit_in_bytes = 256000000;
    }
}

Now, add the following to /etc/cgrules.conf to assign tasks by the dropbox user to the right group. The first dropbox is the user, the second is the cgroup. (Note that memory would need to be changed to * if you added different kinds of restrictions.)

dropbox memory dropbox/

Now reload the groups and tell the cgrulesengd daemon to reload the rules (assuming you have started that daemon, at boot or otherwise):

sudo cgconfigparser -l /etc/cgconfig.conf
sudo pkill -SIGUSR2 cgrulesengd

To check that this works, open a shell as the dropbox user. Check that the shell is indeed in the dropbox cgroup, by issuing:

cat /proc/$$/cgroup | grep dropbox

To control that being in that cgroup prevents you from allocating too much memory, you can use the stress program (packaged as stress in Debian); note that it will also use CPU. Check that you cannot allocate 500M of memory:

stress -m 1 --vm-keep --vm-bytes 500M

This should fail (the process should get a signal). You can check that the memory limit is cumulative for all processes of the dropbox user: running stress to allocate 200 MB will work, but trying to run an additional such process will fail.

Network access

Unlike the other guide, I will not try to restrict Dropbox traffic to use Tor. However the official documentation says that Dropbox is using only the HTTP and HTTPS ports, so I will prevent it from connecting to anything else (except DNS, of course). I don't think I need the "Open button" or "LAN sync" features mentioned in the doc, so I didn't allow them. We have to configure rules both for IPv4 and IPv6.

for cmd in iptables ip6tables
do
  sudo $cmd -A OUTPUT -m owner --uid-owner dropbox -p tcp --dport 80 -j ACCEPT
  sudo $cmd -A OUTPUT -m owner --uid-owner dropbox -p tcp --dport 443 -j ACCEPT
  sudo $cmd -A OUTPUT -m owner --uid-owner dropbox -p udp --dport 53 -j ACCEPT
  sudo $cmd -A OUTPUT -m owner --uid-owner dropbox -j REJECT
done

You can make those rules persistent by installing the iptables-persistent package in Debian and saying that you want to save the current rules.

Installing Dropbox

Do as follows, as the dropbox user of course:

# required because Dropbox tries to access the display and crashes otherwise
export DISPLAY=""
cd
wget -O dropbox.py "https://linux.dropbox.com/packages/dropbox.py"
chmod 755 dropbox.py
./dropbox.py start -i
# required because you won't get the auth URL if the daemon is backgrounded
./dropbox.py stop
~/.dropbox-dist/dropboxd start

Say yes when asked to download the proprietary daemon. You should obtain an authentication URL. Open it in a web browser and authenticate. Then it should magically work and your files should synchronize in ~dropbox/Dropbox. You can ^C the daemon and run ./dropbox.py start to start it in background.

Whenever you need to interact directly with the Dropbox daemon as your real user, do, e.g.:

sudo su dropbox -s /bin/bash -c 'DISPLAY="" ~/dropbox.py status'

There's just one slight glitch left: how to access your Dropbox files as your real user?

Accessing the files

The original guide uses SMB as a hack to mount the Dropbox folder of the dropbox user to access it as your real user. I use a dedicated tool instead, bindfs, which I feel is slightly less hacky and more flexible, even though the resulting invocation is quite verbose. The following should be run as your regular user, not the dropbox user.

sudo apt-get install bindfs
sudo mkdir -p ~/mnt/dropbox
sudo bindfs --create-for-user=$(id -u dropbox) \
  --create-for-group=$(id -g dropbox) \
  --create-with-perms='f-x' \
  --chown-deny --chgrp-deny \
  --chmod-filter='of-x,gf-x,uf-x' -p 'f-x' \
  -u $(id -u) -g $(id -g) \
  ~dropbox/Dropbox ~/mnt/dropbox

This means that you can interact with your Dropbox files in ~/mnt/dropbox, with all existing files and new files appearing to be owned by your real user and its group, but they are actually owned by dropbox and its group in the home of the dropbox user. All chmod and chown operations in the mount from your real user will fail (which is right, as they make no sense), and files will never appear there as executable nor can be set to be executable (this approximates the noexec option and makes it harder to execute code from the Dropbox files, which is useful if you're paranoid about Dropbox smuggling harmful executables there).

I use a little script to pass commands to Dropbox and do the bindfs invocation if necessary, checking beforehand that Dropbox is suitably restricted. Again, the script should be run as your regular user, not the dropbox user. I think those tests are important: as the system is insecure by default, you want to test explicitly if the restrictions are still there; otherwise, if they break and Dropbox can start doing unpleasant things like connect to your X server, you will never find out about it (except the hard way).

Limitations

In comparison with the original guide I am not covering the use of AppArmor to restrict the dropbox program. (I don't feel this is that useful as my setup installs Dropbox locally to the dropbox user and not as /usr/bin, although it would be nice, e.g., to limit Dropbox's ability to investigate /proc.) I do not cover the question of starting Dropbox automatically (I run it manually and stop it when I'm done), only the question of maintaining the restrictions across boots.

I do not cover the question of encrypting files in Dropbox (as my use case is to collaborate with people who would not use encryption). I do not cover the question of having a GUI, status icons, nautilus plugins, etc. (I do not use those.)

Concluding remarks

All of this makes the installation of Dropbox on a new machine a bit more tedious. However, it's important to understand that the privacy-conscious user has no alternative: the Dropbox client is a proprietary program that they have no reason to trust, especially given that Dropbox is US-based, and the US have been known for massive privacy violations. Dropbox is a tool designed to upload your data to untrusted third parties, so it is very important that your computer enforces the necessary checks to ensure that it shares only the data that you want it to share.

There is a general principle at play here: whereas the general public is happy to install random apps and toys with little regard to which harm they could cause, the privacy-conscious user will always need more effort to integrate anything new into their computing infrastructure, because it needs to be done in a controlled and secure way.

I have a lot of files and I'm not fond of sorting them intelligently, so I usually give them long and descriptive file names and rely on locate to find them quickly. I was always a bit annoyed to see that locate was not instantaneous even though intuition suggested that it should be, but I was shocked to find out that locate is actually an antique, and that reimplementing a better version of it seems trivial. So I thought I had to investigate more, to replace locate with something that worked better.

Current setup

I am currently using locate, by which I mean mlocate, not slocate which is not packaged for Debian, and not the old locate from findutils.

My database in /var/lib/mlocate/mlocate.db takes 300 MB, and indexes about 10M files. Indexing is run every night, I don't know how much time it takes, mlocate is maybe smart about which files to examine, but I don't really care about that. (To be honest, I am a bit concerned about power consumption and hard drive and SSD wear, but that's rather hard to estimate.) Hence, I will focus on the performance of query evaluation only, not indexing. To estimate performance for typical use cases I grepped from my history file to find the latest locate commands that I ran:

grep ';locate' ~/.history |
  cut -d'|' -f1 | cut -d';' -f2 | grep -v '^grep' |
  cut -d ' ' -f2- > workload

That's 650 invocations (over a bit over 100k lines of history). I filtered them to remove those that did not run, and to remove the very rare cases where I used a locate-specific feature (there was one -0 and a few cases where I was searching simultaneously on multiple patterns, otherwise the only flag was -i), so that's exactly 646 queries (of which 527 are unique). Let's time all those commands, running it 3 times to avoid outliers, with no outstanding IO or CPU activity:

for a in 1 2 3; do
  time sed 's/^/locate /' workload | sh > /dev/null;
done

This takes around 1 hour, so about 5.5 seconds per query.¹ In terms of hardware, I should point out that the machine that I am using has an SSD, most specifically a 120 GB Samsung SSD 840, which hosts the system (plus some of the data, the rest is on hard drives), and of course I'm always storing indexes on the SSD. The CPU is an Intel Core i5-4570 at 3.20 Ghz with 4 cores, there is 8 GB of RAM.

For completeness I also timed locate.findutils (so locate from the GNU findutils) and it is marginally faster, taking about 50 minutes. The database is much more compact, however, and takes only 75 MB. I did not bother benchmarking slocate as Debian does not package it.

Making it faster

Let's try to replace locate by the simplest possible approach to optimize for pure speed.

sudo find / > files

This takes some time, but I don't care. The result is about 900 MB. Let's time the workload on it:

for a in 1 2 3; do
  time sed 's/^/grep /;s/$/ files/' workload | sh > /dev/null;
done

This takes about 19 minutes, so it's already about 2.5 to 3 times faster than locate. (Yes, ideally, I should have checked that it returns exactly the same results, or quantify the differences, but I didn't bother. I just verified for some example queries that the result made sense.)

It turns out one easy way to make grep faster is to set LC_ALL=C. This is unsafe with respect to multibyte characters, but I don't use those very often in file names and never in queries, and my understanding is in this case this option can only add false positives with low probability, which is OK for me.

for a in 1 2 3; do
  time sed 's/^/LC_ALL=C grep /;s/$/ files/' workload | sh > /dev/null;
done

This takes about 7 and a half minutes, so faster than the vanilla grep solution by a factor of 2.5 to 3.

How to make this even faster? It turns out that grep is CPU-bound in this case, so with a multicore CPU it is tempting to parallelize it. This is easy to do: we can clearly split the indexed files in buckets that we index and query separately, merging the results. I use 8 buckets here.

split files files. -nr/8

This splits files in files.aa, ..., files.ah, in a round-robin fashion.²

Let's now create a script grep.sh to grep the files in parallel, using the parallel command from GNU parallel. It is slightly confusing but we must re-quote the arguments to the grep.sh script in this strange way so that we can pass them to the command invoked by parallel:

ARGS=$(printf " %q" "$@")
ls files.* | parallel 'bash -c "LC_ALL=C grep '$ARGS' {}"'

The parallel command will spawn as many parallel jobs as there are CPUs (i.e., cores, so should be 4 in my case). Note that it would not be safe to use xargs or parallel from moreutils they could garble output by two parallel processes if they tried to write at the same moment; GNU parallel, by contrast, prevents this (with --group, which is implied by default). Now let's time this:

for a in 1 2 3; do
  time sed 's/^/.\/grep.sh /' workload | sh > /dev/null;
done

This takes around 3 minutes 30, so around 2 times faster than the non-parallel version. This amounts to 1/3 second per request (plus the overhead of displaying the results, which is not accounted for here), which I think is good enough for my needs.

Compressing the index

One respect in which this grep-based approaches is worse than locate is that its index is three times larger than that of locate. The original post about locate conjectured that this explained why locate's performance is worse than naive grep. However, as we will see, it is easy to compress the index and still be much faster than locate. First, let's simply compress the files with gzip:

split --additional-suffix=.gzip \
  --filter="bash -c 'gzip > \$FILE'" files files. -nr/8

The resulting index is 105 MB in size in total, so 10 times smaller than the uncompressed index, and still 3 times smaller than that of locate. We can then decompress these files when querying them, by replacing our search script with:

ARGS=$(printf " %q" "$@")
parallel -i bash -c "gunzip -dc {} | LC_ALL=C grep $ARGS" -- files.*.gz

The timing of this is 14 minutes, which is 4 times slower than the uncompressed version, but still 4 times faster than locate.

In fact, we can still make this much more efficient. One easy way is to use the pigz command to decompress, which spawns additional threads and is faster. Replacing gunzip by pigz in the above (which is packaged for Debian), we get a timing of 11 minutes for the same index size.

Of course, if we want to achieve different tradeoffs between file size and speed, we can look at different compression and decompression algorithms, optimized for speed. One possibility is lz4, packaged as liblz4-tool in Debian. The index is 160 MB in total, which is 50% more than with gzip but half of the size of the locate index, and replacing gzip by lz4 and timing, we get 8 minutes. So this last solution that assembles off-the-shelf tools with around 5 lines of bash is about 7.5 times faster than locate while using an index which is twice smaller.

Result summary

Concluding

I am considering replacing locate by the fastest of these approaches (the one with parallelization and no compression) for my own needs, but I just intend to do it as a personal hack; doing it in a reusable way would be much harder.

Of course, this post is just scratching the surface; the list of file names is not preprocessed in any way to make grep faster, whereas in principle it could. However, I could not find any standard Unix utility that could do index file > file.idx and search --index=file.idx pattern file, such that file.idx is not too large compared to file and the search operation is much faster than a grep (at least for patterns that are fixed strings).³ It would be fun to implement such a tool, based, e.g., on a suffix tree, but I probably won't bother as the grep approach is fast enough.

In addition to choosing the best algorithms, a good replacement of locate should also implement the various options of locate, so as to be a drop-in replacement for it. In fact, it would probably be relevant to index more metadata in addition to file names, to optimize searches, e.g., for recently modified files, etc. I am quite surprised that such a tool does not seem to exist. To be precise, it does exist in a stronger form in all the graphical desktop search tools, so this could alternatively be implemented as a usable CLI interface to such tools, intended as a locate replacement.⁴

Submitting a research paper to a conference or journal can be a stressful process; there are many things to remember, and you want to avoid mistakes. Here is my attempt to summarize all the steps and my experience about some points, because it's easier to follow a checklist than to remember every time what you have to do. Note that I'm making some implicit assumptions, e.g., that you are using a revision control system, that you are using LaTeX, etc.; also, this list may not be sensible or exhaustive in all fields (I'm talking from the perspective of theoretical computer science).

TODO flushing.

There should be no tasks left before you start finalizing the submission. Of course, it's fine to remove a TODO because you decided to not do it because you did not have the time, the energy, it wasn't worth the effort, etc.; but the status of all TODOs must have been cleared, so you won't realize after proofreading that there were some changes left that you intended to do. Possible sources of TODOs to process:

• In the main text: those should be the most obvious.
• In LaTeX comments: I don't use those but some people do, consider grepping for "TODO" or such keywords (for this reason, TODOs that you gave up on should probably be moved to a separate file, not just commented out)
• In a separate TODO file: did you start jotting down things to do in separate files ("TODO", "ideas", "meeting_notes")?
• In your mailbox: if you have any mail in your inbox about the submission, you probably intend to get rid of it once submitted, so go through it before you start finalizing, and ensure nothing is left to do.
• In the reviews of a previous unsuccessful submission of the paper.

Once the only task left is "proofread the submission", you can continue.

Proofreading.

Go over the submission once, linearly, from start to end. You may want to do it on screen, or on paper (annotating the paper copy and then implementing any changes). If using a WYSIWYM editor such as LaTeX, when editing anything during proofreading, it is crucial to recompile and read again what you just changed, preferably the whole paragraph: fixing errors can easily introduce other errors, and you won't be proofreading again what you are currently changing.

Hopefully, at this point, the scientific content of the submission should not change. If it turns out you have to make significant fixes when proofreading, consider doing a second proofreading pass.

Check that you proofread the following, which are easily forgotten:

• Paper title, author information: especially affiliations, which are often filled in casually early on and may not be sensible.
• Section titles in the paper: go once through the paper looking just at section titles, to check that they make sense and match the "Paper structure" paragraph if you have one.
• Footnotes.
• Floats, figures, algorithms, etc.
• Formal statements: it's easy to focus on the prose, but you should double-check that the precise wording of theorems makes sense, no matter how they are framed.
• Bibliography: Do all references follow the same format? Are you consistent when abbreviating venue names? when including or discarding page numbers, addresses, publishers? Are all author names sensible? Are all acronyms and proper names correctly capitalized in titles (e.g., no "Designing an xml language for hadoop")?

Once you are done proofreading, you have a known good version. It may make sense, when doing further changes, to check their diff against that version to spot any errors that you would be introducing.

Spellchecking.

Use any spellchecking tool. Also check for notations and terms and other things that shouldn't be there anymore:

• Remove the definitions of macros that should no longer be used (for old macros, for TODO notes, etc.)
• If you introduced a macro to replace a notation and changed the notation, check for hardcoded instances of the notation or of previous notations.
• If a name has multiple variants and you have been using them inconsistently, standardize to one name (e.g., "foo bar" to "foo-bar"). When looking for occurrences of multi-word names, don't forget that there may be a line break in the middle (i.e., check for "foo" at end of line).

Typography.

Check for the following:

• Math identifiers at the beginning of lines: if "of x" is split, make the space between the words non-breaking.
• Overfull \hboxes: check for them in the LaTeX log and fix them by rewording, or tweaking hyphenation for technical terms that LaTeX does not know.
• General page layout: widows and orphans, spacing around environments and floats, positioning of section titles (not at the bottom of a column!), placement and numbering of floats, etc.

Sanity checks.

Verify the following one last time:

• Go through the call for papers and formatting instructions:
  • Did you get the page limit right? Including or excluding title page, references?
  • Are you using the correct style file? Are the font size and paper size correct?
  • Should you be including author information? (depends if the venue is double-blind or not)
• Search a last time in the PDF and grep in the source folder for bad strings like "TODO", "FIXME", and other such stuff.
• Check the LaTeX log for bad errors like broken references or multiply-defined labels. Search for "??" in the PDF to double-check that there are no broken references.
• Will you be submitting your LaTeX source? If yes (e.g., on arXiv), make sure there are no embarrassing comments left in the LaTeX. See for instance the script in this arXiv FAQ entry. In addition to comments, do you have block comments with iffalse, the comment environment, or custom commands? Are some of the LaTeX files unused, i.e., not included in the compilation?
• Are all your changes committed to the revision control system? Check this on all the machines where you have been editing the document (to make sure that there aren't uncommitted changes on a different machine).

Submitting.

Submit the paper. Check the following:

• Are the title, author information, track, keywords, etc., correct on the submission interface?
• If you had to indicate conflicts of interest, did you do it?
• Are you supposed to submit additional things, like uploading an appendix elsewhere? If yes, don't forget them.
• Update the abstract on the submission interface.

Double-checking.

Re-download the file that you submitted from the submission interface and go through it to check that it looks good.

• Are all pages there?
• What is the last change that you did? Is it there?
• Did you submit the right file, for the right paper? This may sound stupid, but silly mistakes can happen, especially if you have multiple submissions for the same deadline.

It's normal to find mistakes at the last minute when going over the PDF after submitting. Of course, when fixing them, be extra careful; at this stage you should probably be double-checking the changes that you make, and checking them again by proofreading the diff before you commit.

Concluding.

Decide you are done.

Let your coauthors know. Thank them for their hard work.

Then, celebrate as you see fit. :)

Aftermath.

The following are things that you should probably do, but there's no firm deadline for them, so the safest way to avoid doing them multiple times because of last-minute fixes is to wait for the submission deadline to have passed.

• Ensure that your version control system knows what was the final submitted version.
• If applicable and not double-blind, upload your preprint on your website and/or a preprint repository such as arXiv.

A French translation of this post is available. — Une traduction de ce billet en français est disponible.

In April 2014, Google Paris organized an onsite programming contest, the Google Hash Code. The task to solve was quite fun. This post describes the problem, and some of the strategies to solve it that were used by the ENS teams. The reason why this gets published now is because the 2015 edition is currently being organized, which for some reason gave us the impetus to document our work.

ENS scored pretty well in the contest (ENS students were in teams ranked 1st, 2nd, 3rd, 4th, 7th, 10th; mine was "ENS Ulm 1" which ranked 7th), and substantially improved on their solutions afterwards during the Extended Contest, which lasted for some time after the contest.

Problem description

The full task assignment by Google is available.

We are given a map of Paris (from OpenStreetMap data) that includes¹ all intersections and streets. As in real life, some of the streets are one-way. The segments are labeled by their length in meters and the time it takes to traverse them. We have 8 Street View cars that start from the Google office and want to photograph as many street meters as possible in a limited amount of time (15 hours). You can traverse the same street as many times as you want, but it only counts once towards your total meters.

The goal is to choose a route for the 8 cars which allows you to traverse as many unique meters of the streets of Paris as possible, within the allotted time.

The brute-force method

Of course, in principle we can solve the problem by enumerating all of the possible routes for the 8 cars, and picking the best one. There are finitely many routes, so this approach is guaranteed to find the optimal solution. This is good enough for a mathematician, but not for a computer scientist: the paths are too numerous and you will never be able to enumerate them in practice.

Imagine there is a single car that reaches every minute an intersection with at least two possible streets, during 10 hours. The number of paths is $2^{10\times 60}$, which is about ${10}^{180}$. Even if every atom in the Solar System were an impossibly powerful supercomputer, you wouldn't be able to reach this number before the Sun goes bust.

The greedy method

At the opposite end of the spectrum, the simplest possible approach (beyond purely random approaches) is to choose every street to take, one after the other, based on some greedy optimization criterion.

Basic greedy

For instance, plan a route for each car, one after the other. Whenever the car reaches an intersection that allows it to reach streets that haven't been traversed yet, choose one of them. Maybe pick the one with most meters, or the one with most meters per second. Otherwise, if all reachable streets have been visited, choose one of them at random. Repeat while there is time, then do the same for all cars.

The greedy strategy will yield reasonable results. There are, of course, tweaks to make, for instance planning the route for all cars simultaneously instead of sequentially... Or sending the cars at the beginning to hardcoded start positions which are far apart, to increase coverage.

However, the key drawback of greedy solutions is that they cannot plan things in advance. When choosing among already visited streets, for instance, you are not trying to get closer to unvisited streets. If visiting a new street will trap you in a maze of already visited streets, you will still fall in the trap.

Greedy with lookahead

A simple solution to this problem is to improve the greedy strategy with brute-force that looks ahead for a few steps. Whenever you need to take a decision, don't take it based on what it will bring you now. Rather, consider all possible paths of length, say, 10, that you can do from this point, and see which one is bringing you the best results. Choose your next move to be the first move of the best path. Do the routing for cars in parallel following this idea. The path length that you use is tweakable, and in general using higher path lengths will improve the result: I think we used something like 17 in practice.

This simple idea is easy to implement and yields pretty good results. My team used it with a few tweaks, and to my knowledge many of the top-ranking teams also did.

The clever method

Of course, the point of this post is to describe the clever solution, the one that was implemented after the contest, for the extended round.

Rephrasing the problem as Eulerian paths

The key insight is to notice the similarity between our problem and the Eulerian path problem: computing a path in a graph which visits each edge exactly once. The map of Paris is seen as a graph, where the intersections are the vertices, and the streets are the edges. If we could find an Eulerian path in this graph, then it would be the ideal solution, going through all segments without wasting any time in already visited segments.

Of course, you need to squint a bit to see the reduction. First, we have 8 cars; but for now we will assume that we have only one, and will split the path between the various cars later. Second, we have a time limit, and edges have a value in terms of their number of meters; but we will disregard this. We will pretend that we will be able to visit all edges in the allotted time (which isn't so unrealistic, as we will see ;)), so that we ignore the time limit and the lengths of the streets in meters (we only care about the time needed to traverse them).

Third, and more importantly, our graph is a bit weird, because some edges are undirected, and others (the one-way streets) are directed. Because of the one-way streets, we cannot rely on undirected Eulerian paths, and will be forced to reduce to directed Eulerian path. We will thus need to choose an orientation for the undirected edges.

Fourth: well, obviously, we won't be able to find an Eulerian path. There is a well-known characterization of directed graphs that have Eulerian paths (I call them Eulerian graphs), which is not hard to prove: the in-degree of each vertex (the number of edges that go towards it) must be equal to its out-degree². Does the input graph satisfy this condition? Not a chance. However, in our case it isn't really forbidden to traverse edges multiple times; we just want to avoid doing it as it is wasteful.

Hence, there will be two steps to our process to make the graph Eulerian. First, we will choose a direction for all undirected edges, in a way that makes the graph "more Eulerian". Second, we will add edges to make it really Eulerian, which materialize the (wasteful) choice of going through edges which are otherwise visited (that is, that have been visited or will be visited at another point in the solution).

Orienting undirected edges

In order to reduce to a directed Eulerian path, we have to assign a direction to all undirected edges. To make the Eulerian path problem easier to solve on the resulting graph, we will try to minimize the sum, across all vertices, of the difference between in-degree and the out-degree: intuitively, the smaller this quantity, the less edges we have to add to make the graph Eulerian.

To introduce some terminology, I will say that a vertex is overloaded (in the original graph, or in a directed graph obtained from it by edge orientation) if its in-degree (counting only directed edges) is more than its out-degree; it is underloaded if it is less, and balanced if both are equal. The load of the vertex is the difference between in-degree and out-degree (which is $>0$ for overloaded vertices and $<0$ for underloaded vertices).

How can we choose the best orientation of the edges? Our choice of terminology gives some insight: we would like edge orientations that allow originally overloaded vertices to "transfer" some of their load to the underloaded vertices, following directed paths, which have to be disjoint to avoid double-counting the intermediate edges. It turns out that this can actually be phrased neatly as a flow problem.

Overloaded and underloaded vertices are respectively represented as sources and sinks, with capacity equal to their load. Each undirected edge is represented as a pair of edges going in both directions, with capacity 1. Edges that are already oriented are ignored.

We solve this flow problem using any flow algorithm. By the integral flow theorem, the flow along each edge in the result is either 0 or 1. Hence, the result describes a way to orient some (but not all) of the undirected edges, depending on the direction of the flow going through them.

We still have the problem that some edges in the result are still undirected, namely those which were not used at all in the optimal flow. To take care of this, we simply orient all of the remaining edges at random. Of course, this may make the final sum worse, and to alleviate this we enforce manually the property that the flow algorithm had enforced for us before: for any path of our newly oriented edges, if reversing the direction of the path makes the sum better (because the path origin was underloaded and the path target was overloaded), we do the reversal, which increases the load of the origin by one, decreases the load of the target by one, and does not change the other degrees. To perform this last step efficiently, observe that it suffices to consider all pairs of vertices. Whenever we find a pair of an underloaded vertex and an overloaded vertex, we can search for a path from one to the other, and reverse it if it exists.

Hence, at the end of this process, we have a directed graph where we have tried to minimize the sum of differences between in-degree and out-degree, to make it as Eulerian as possible. We now make it Eulerian for real, by adding edges so that all vertices are balanced.

Adding edges

Intuitively, the edges that we add to make the graph Eulerian correspond to the possibility of adding already traversed edges to the path.

In other words, if we add an edge from vertex $i$ to vertex $j$, it means that we will be going from $i$ to $j$ through a path of edges that will be visited anyway. All the time that we spend doing such traversals is wasted, and does not contribute towards our objective. Hence, the cost of adding an edge from $i$ to $j$ should be the time needed to go from $i$ to $j$ following any edge path. In fact, we may follow a path that violates our chosen orientation for the edges that used to be undirected, and it does not matter; so we are really talking about following a shortest path in the original graph.

Hence, we start by precomputing the shortest path time between all pairs of vertices in the input graph, using the Floyd-Warshall algorithm.

Now, we model the problem of adding more edges as a minimum weight matching in a weighted bipartite graph. On one part of the bipartite graph, we put all vertices that are overloaded in the result of the previous phase, duplicated as many times as their load. We analogously create the other part³ of the graph with the underloaded vertices. We add edges in the bipartite graph between any two vertices in the two parts, weighted by the time of the shortest path from one to the other.

Now, a perfect matching in this graph represents a way to add the right number of edges to ensure that all vertices are balanced, and if its weight is minimal then it wastes little total time as possible traversing edges that are otherwise visited. We use the Hungarian algorithm to solve this problem, and to complete the oriented graph.

Constructing the Eulerian path

The resulting graph is now directed, and each vertex is balanced, so it has an Eulerian path. To compute it, it is well-known that a simple greedy approach works. (Maybe there would be possible improvements with respect to the later steps, but we didn't look into this.)

From the Eulerian path, expanding the edges that were added in the previous phase to the shortest paths to which they correspond, we obtain an itinerary, which is a fairly good solution for a single car to traverse all the streets of Paris in as little time as possible.

Splitting the path among cars

We now remember that we have 8 cars rather than a single one, so that our route must be split among them.

Here is our approach: we take the first car, and have it run the beginning of the route for one quarter of the allotted time. Then, we look at the rest of the route until the end of the allotted time, and search for the traversed vertex that is the easiest to reach (in terms of shortest path time) from the starting vertex (the Google office). We continue the route of the first car until it reaches this vertex, at which point we end it. Then, the next car starts at the starting vertex, goes to the cut vertex following the shortest path, follows the rest of the route again for one quarter of the allotted time, and continues until the closest point to the starting vertex. We repeat until the last car, which takes care of all the rest of the route.

Of course, the reason why we cut when each car goes close to the starting vertex is to minimize the effort spent by the next car to reach the position where they can resume the route. The solution will still give too much work to the last car, but we will see later how to balance the duration of the routes of all cars. The reason why we ensured that each car ran for at least one quarter of the time is to make this balancing operation easier, by ensuring that the car paths are sufficiently long to intersect many times.

We use this as our initial solution, and now optimize it further.

Optimizations

We now iterate a bunch of optimizations to tweak the paths and make them better, until we get something which we judge is good enough.

Of course, not all optimizations yield the same savings; and the order in which they are applied can make a large difference. That said, I don't remember in which order, or how many times, they were applied; there probably wasn't much logic to it. :)

Pruning

For any subpath of the path of any car that consists only of otherwise visited edges, we replace it by a shortest path between its endpoints (courtesy of the precomputed Floyd-Warshall).

Loop swapping

Assume some car's path includes a move from vertex $i$ to vertex $j$, then a cycle $C$, then a move from vertex $j$ to vertex $i$; and that the edge from $i$ to $j$ is otherwise visited. If we can find any other car that passes through an intersection of $C$, we can have that other car take care of the edges of $C$ on the way, so that the first car doesn't need to do $C$ and doesn't need to do the steps from $i$ to $j$ and back (so we save twice the time of the $i$—$j$ edge).

Of course, this can lead to a situation where some cars have a longer path than others, but this will be dealt with later.

Trimming

If the last edge of a car's path is already visited by someone else, just remove it.

Brute-force

For every subpath of every car's path, up to certain length, if the path can be replaced by any shorter path that leaves no street unvisited, then do so. This differs from the pruning optimization in that the subpaths are allowed to contain edges that are not otherwise visited; of course, the replacement subpath will also need to traverse these edges (possibly in a different order).

Balancing

The time limit of 15 hours has been ignored until now, but it has to be obeyed by all cars, so we shouldn't return a solution where one car does all the work and the others do not do much. Further, in case we do manage to traverse all edges (which we did!), the quality of a solution is judged according to its remaining time, which is $T-{max}_{c\in \{1,\dots ,8\}}{t}_c$ where $T$ is the time limit and $t_c$ the time of car $c$.

Hence, we would ideally want all the cars to follow routes that take the same time. This implies that the busiest cars should try to swap longer parts of their paths with shorter parts of less busy cars.

In practice, look for any two vertices $x$ and $y$ and two cars such that both cars will pass through $x$ before passing through $y$. Now, in general the paths followed by the two cars between $x$ and $y$ will take a different amount of time; if swapping the paths will decrease the time difference between the two cars' routes, then swap them.

This is a simple greedy scheme that can be iterated as long as we want. In fact, as the paths of cars will tend to intersect very often, it works very well and quickly converges to a state where all cars take the same time to do their routes, no matter the initial routes.

Results

The clever strategy described here managed to traverse all streets on Paris in the allotted time (in fact, in 9 minutes less than the allotted time). It's a pity that this didn't happen during the contest proper, but still, it is nice. :)

Related work

We developed all of this on our own, and we didn't look seriously into the related work of people who already tried to solve similar problems. It turns out that our problem is known as the postman problem, because of course it is also useful to optimize mail delivery.

More specifically, our version is known as the "$k$-mixed postman problem", because we have multiple cars (here, $k=8$), and because the graph is mixed: some of the edges are directed while others are undirected. Surprisingly, the directed postman problem and the undirected postman problem (for $k=1$) can be optimally solved in polynomial time⁴, whereas the mixed postman problem is NP-hard⁵.

It would be nice to compare the results of our method to state-of-the-art approaches. We did a preliminary comparison to existing datasets and we have no reason to believe that our algorithms are competitive. But, still, we had fun. :)

Credits

The ideas in this post are not mine: essentially everything was done by other ENS students. All steps of the clever solution except for the post-processing were conceived and implemented by gnomnain (code). The optimizations were implemented by elarnon (code), and Mc and mehdi (code). (All code is purely write-only and there is no documentation of any kind, so don't try to use it.)

This post was re-written from an earlier version authored by Mc. Thanks to Jill-Jênn, elarnon, Armavica and gprano for proofreading drafts and offering feedback. There is another write-up about the topic, in French, by Jill-Jênn.