a3nm's blog

Configuring screens with xrandr

There are various GUI tools on Linux to change the screen resolution and configure the various screens of your machine, which is useful to do, e.g., when plugging in a video projector to give talks. From my experience, however, the right tool, the one that does not hide anything from you and allows you to get the job done, is the CLI utility xrandr.

This post is a quick guide to perform common tasks with xrandr. I'm certainly not an X guru, but maybe this can serve as an introduction about how to perform common display configuration tasks with it.

The starting point is always to see the current state with:

xrandr -q

This will print out information about all screens and outputs known to the system. For instance:

Screen 0: minimum 320 x 200, current 3360 x 1080, maximum 16384 x 16384
LVDS connected 1920x1080+1440+0 (normal left inverted right x axis y axis) 382mm x 215mm
   1920x1080     60.01*+
   1680x1050     59.95  
   1400x1050     59.98  
   1280x1024     59.89  
   1440x900      59.89  
   1280x960      59.94  
   1280x854      59.89  
   1280x800      59.81  
   1280x720      59.86  
   1152x768      59.78  
   1024x768      59.92  
   800x600       59.86  
   848x480       59.66  
   720x480       59.71  
   640x480       59.38  
DisplayPort-0 disconnected (normal left inverted right x axis y axis)
DisplayPort-1 disconnected (normal left inverted right x axis y axis)
DisplayPort-2 disconnected (normal left inverted right x axis y axis)
VGA-0 connected 1440x900+0+0 (normal left inverted right x axis y axis) 408mm x 255mm
   1440x900      59.89*+  74.98  
   1280x1024     75.02    60.02  
   1280x800      59.81  
   1152x864      75.00  
   1024x768      75.08    70.07    60.00  
   832x624       74.55  
   800x600       72.19    75.00    60.32    56.25  
   640x480       75.00    72.81    66.67    60.00  
   720x400       70.08

The first thing is to figure out which output corresponds to which of the screens you have in front of you. You can usually determine it from the output names: VGA, HDMI, and DVI usually correspond to the connector type on the motherboard. On the example output above from my work computer, VGA-0 is indeed an external screen plugged in my computer's VGA port. LVDS is usually a laptop's internal screen, which is the case in the example. Sometimes the names are off, e.g., on my home computer, a DVI port is mistakenly labeled as an HDMI port. Alternatively, you can identify screens by their modes if you know which resolutions they support. For instance, above, I know that my main screen supports 1920x1080, so it is necessarily the LVDS one. (If you don't know what a screen resolution is, read on, I'll explain it.)

If you're trying to configure an external screen or video projector, and it doesn't show up in the output of xrandr -q, then you have a problem that's deeper than just persuading X to use the output properly. You should probably investigate whether the kernel or X server can see anything (in case your output is not listed) or check the cable (in case the output is listed but indicated as disconnected). When debugging things, know that all external screen standards that I know of (VGA, DVI, HDMI) are perfectly plug-and-play, meaning that it is safe to play with the cables. However, in some cases (e.g., laptops), it could be the case that an output will not work unless the system has booted with a usable screen on that output, or unless some magic key combination is pressed to enable the output.

If all outputs that you want to use seem to be listed and have a screen connected to them, congrats! You can now configure them. The two simplest commands are the following. The first one enables one output that has a connected screen and sets it to its preferred resolution, which is usually what you want to do. The second one disables one output (any screen connected to it will usually go in power-save mode).

# enable output VGA1 and set its screen to its preferred mode
xrandr --output VGA1 --auto
# disable output VGA1
xrandr --output VGA1 --off

Now, how to decide what to put on each screen? The first possibility is to tile the display across multiple screens. This makes sense when you have a laptop and an external screen, or multiple screens on one machine, and want to show different windows on them. If you are trying to use a video projector, this is reasonable if you are using a fancy presentation tool like pdfpc that can show the slides on one screen and use your laptop screen to show the next slide, notes, etc. Here is an example to illustrate how this is configured1:

# my home setup is as follows, from left to right:
# one VGA screen, one DVI screen, one HDMI screen
xrandr --output VGA1 --left-of DVI1
xrandr --output DVI1 --left-of HDMI1

The second thing that you could want to do is to have two screens that show the same thing. For instance, for presentations using a non-fancy PDF reader, you usually want both your screen and the video projector to show your slides. This is achieved very simply:

# set VGA1 (the projector) to show the same thing as LVDS1 (laptop screen)
xrandr --output VGA1 --same-as LVDS1

However, if your projector is not set to the same resolution as your screen, your presentation will be clipped or mis-centered on one of the displays. Let me explain a bit about this. What a screen displays is made of atomic dots, aka pixels2, and the resolution of a screen is the number of pixels it displays, given as the width times the height, for instance 1024x768 (with the letter 'x' commonly used for the times symbol instead of the Unicode character '×'). Screen resolutions also have names, such as "VGA" (for 640x480), or "FHD" (for Full HD, that is3, 1920x1080). Screen resolution tells you nothing about the actual size of the display, which depends on the size of the physical pixels on the screen, aka pixel density4.

Screens can support multiple resolutions. In the vast majority of cases, the screen is designed to be used at its highest possible resolution, and lower resolutions look a bit ugly because they crudely scale up the lower resolution to the screen's physical resolution (the number of physical pixels it has). Screens can be set at a lower resolution as a poor man's version of zooming, although it is usually far prettier to do the resizing at the software level, e.g., use larger fonts, so that fonts are large but remain crisp. However, lower resolutions are also useful to show the same thing (e.g., your presentation) on two screens with different characteristics.

Doing xrandr -q indicates which modes are supported by the screen connected to each output, with a '+' next to the preferred mode (the one the screen is "designed" to be used in) and a '*' next to the currently used mode. Each mode consists of a screen resolution, given at the left, and a refresh rate5.

Thus, to fix the problem with --same-as, you should find in the list what is the highest resolution supported by both outputs. (With some luck, it will be the projector's preferred resolution, so only your laptop screen will look a bit blurry; but this is not always the case, especially when aspects ratios do not match.) You should then set the outputs to that resolution; for instance:

xrandr --output VGA1 --mode 1024x768
xrandr --output LVDS1 --mode 1024x768

Once you are done giving your presentation, you will probably want to revert your laptop's screen to its preferred resolution using --auto, as previously explained.

You can do a bunch of other things with xrandr, such as rotating displays, applying transformation matrices to them, software brightness and gamma correction, zooming, etc., see man xrandr to know more. Playing with these options should be safe (although it's true that, in ancient days, there were stories about software ways to destroy CRT screens...). A real risk, however, is that if you make all your screens unusable (e.g., turn them off with --off, make them display garbage with bogus scales, flip them, etc.,), xrandr has no way to allow you to revert to sane settings automatically after a time, as GUI tools often do. You will have to undo your mistake in the blind. If you can't do this, one possible option is to switch to a TTY with Ctrl-Alt-F1, and use xrandr from there; you will probably have to pass it an environment variable so that it can talk to your X server, for instance:

DISPLAY=":0" xrandr --output LDVS1 --auto

Worst comes, of course, you can always restart the machine, as these settings do not persist across reboots.

  1. Experts will note that you can combine this in one invocation to the xrandr command, but for simplicity I will not address this here. 

  2. Pixel is the abbreviation of "picture element" and is supposed to be the smallest displayable unit. However, in fact, on LCD screens, individual pixels are further split in red, green, and blue subpixels, as you can easily see with a magnifying glass (or, e.g., a drop of rain on your smartphone's screen). This fact is commonly used to improve the quality of the display to something finer than what the resolution would suggest, especially for text; this is known as subpixel rendering

  3. It is typically quite annoying to see screens advertised as "Full HD" as if it were some magical statement about the quality of the screen, whereas it is nothing more than a technical statement about the number of pixels it can display. 

  4. In particular, what Apple brands as "retina displays" are displays with a certain high pixel density, which supposedly exceeds the human eye's own density for a certain typical viewing distance. Nothing magical here either. 

  5. The refresh rate is the number of times per second the screen should update, in Hertz. You can select it using --rate. I will not talk about it further, because it usually does not matter. 

Google Hash Code 2015

Today was the onsite final of the Google Hash Code contest organized by Google Paris. The task was to route loons to optimize Internet delivery on target cells by adjusting the loons' altitude and taking advantage from winds: see the problem statement in English and French and the input file, which I will not summarize further here.

With Théotime Grohens, Marc Jeanmougin, and Auguste Olivry, I was part of the "ENS Ulm 1" team who got the first place. This post presents our strategy to solve the problem. It is comparatively simpler than the 2014 contest strategies used during the extended round. We also provide cleaned-up code for our approach; it is about 200 lines long, which is twice more than what I published for the selection round; however, unlike the selection round, this code would have sufficed to reach the first place of the contest (like we did), beating the second best score (698678 by the hackEns team).


The basic idea of the strategy is to compute the route of the loons one after the other, considering the route of the other loons as fixed, and starting with the default routes of not moving the loons at all.

To route each loon, we use a dynamic programming approach, which computes the optimal route for this loon given the other routes. We maintain (in covered in the code below) which target cells are already covered at which time by the other loons (whose routes are fixed), to focus at each point in time on the target cells which are not covered. We optimize the total number of covered cells (summed over all time units) for the loon that we are routing: we call this the score. We use the following recursive definition to compute the optimal route:

  • once the time is over, the score for a loon is 0 no matter its position
  • at a time \(0 \leq t < T\), the possible options for a loon at row \(r\), column \(c\), altitude \(a\) are to adjust altitude by -1, 0, or 1 (within acceptable bounds), and the score is the sum of the following quantities:
    • the number of cells that we cover at time \(t+1\) in the cell where the wind has taken us after our move, counting only those that are not otherwise covered
    • the score at time \(t+1\) for the position where the wind has taken us after our move (or 0 if the loon was lost), which we compute recursively

To make this more palatable, we have precomputed overall, for each cell, the cell where the wind leads us (in dest). We also precompute which target cells are covered by a loon in each cell (in cov; and then in left at each iteration for speed). To implement the recursive definition and compute the optimal path (in function route), we then just need to compute a big table for our loon with each possible row, cell, altitude and time unit, filling it from the end of time to the beginning of time. We store in each cell of the table the optimal score (in best), computed according to the above, and the altitude adjustment (in dir) that achieves the best score.

Will this have a reasonable running time? The bounds of the input were the following: 300 rows, 75 columns, 9 altitudes (counting the ground), and 400 time units. We need two tables, each containing one int for each possibility (so 8 bytes total). The total is 648 MB, which just fits. On my workstation (with Intel Core i5-4570 @ 3.20GHz), this computation takes about one second per loon.

Doing this for all loons in sequence gives a score of 680953 with my implementation, which would have sufficed to reach the 7th place. To improve the solution further, we follow a very simple scheme. As we have computed the optimal route for each loon in isolation, once all routes have been computed, we just recompute the routes for each loon in sequence, given the previous routes. This cannot make the solution worse (the loon can always follow its previous route, which the dynamic programming approach cannot miss), and may improve it, if the loon can follow a better route given the new routes of the other loons. As just one additional tweak, to make this optimization more efficient, when two altitude adjustments are tied in the dynamic algorithm, we choose one of them at random rather than deterministically: this means that the dynamic algorithm still returns the optimal route for its loon, but it adds more opportunities to change the route and makes the iterative optimization more effective.


The following C++ code is under 200 lines in total, and produces solutions with increasingly better score, in a file called "output". On my workstation, it takes a bit under 20 minutes to produce a solution with a score that would have sufficed to reach the first place in the contest.

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

using namespace std;

#define MAXR 77
#define MAXC 302
#define MAXL 2252
#define MAXA 11
#define MAXT 402
#define MAXB 54

int R, C, A, L, V, B, T, rs, cs;

struct Pt {
  int r, c;
  Pt(int r=0, int c=0) : r(r), c(c) {}

// global variables: auto-initalized, can be larger than what fits in stack
vector<int> cov[MAXR][MAXC]; // which targets are covered by a loon at (r, c)
Pt dest[MAXA][MAXR][MAXC]; // where a loon at (a, r, c) flies; (-1, -1) = out
Pt target[MAXL]; // position of target cells
bool covered[MAXT][MAXL]; // at time t, is target cell l covered yet?
// dynamic programming: best score at (t, a, r, c) and best direction
int left[MAXT][MAXR][MAXC]; // how many new cells covered at (r, c) at time t
// solution: at time t, altitude adjustment for loon b 
int solution[MAXT][MAXB];

// given by problem statement
int columndist(int c1, int c2) { return min(abs(c1 - c2), C - abs(c1 - c2)); }
// does a loon at (r, c) cover target cell l?
int iscovered(int l, int r, int c) {
  int u = target[l].r, v = target[l].c;
  return ((r - u) * (r - u) + columndist(c, v) * columndist(c, v) <= V*V);

// return next move for loon b at time t when at position (a, r, c)...
// ... using the results of dynamic programming
int decide_dyn(int b, int t, int a, int r, int c) { return dir[t][a][r][c]; }
// ... using the computed solution
int decide_sol(int b, int t, int a, int r, int c) { return solution[t][b]; }

int simulate(int b, int (*decide)(int, int, int, int, int)) {
  // compute the run of loon b using decision function decide
  // return the score improvement
  int score = 0;
  int r = rs, c = cs, a = 0;
  for (int t = 0; t < T; t++) {
    int bestda = (*decide)(b, t, a, r, c);
    // store the move
    solution[t][b] = bestda;
    // apply it
    a += bestda;
    Pt next = dest[a][r][c];
    r = next.r;
    c = next.c;
    if (r < 0)
      break; // loon exited
    if (a > 0) {
      // update covered target cells
      for (unsigned int i = 0; i < cov[r][c].size(); i++) {
        int l = cov[r][c][i];
        // score improved if target cell not already covered
        score += covered[t+1][l] ? 0 : 1;
        covered[t+1][l] = true;
  return score;

void route(int b) {
  // route loon b given the already covered targets (in covered)

  // save a factor A: pre-count the uncovered targets for each cell
  for (int t = 0; t <= T; t++)
    for (int r = 0; r < R; r++)
      for (int c = 0; c < C; c++) {
        int score = 0;
        for (unsigned int i = 0; i < cov[r][c].size(); i++) {
          int l = cov[r][c][i];
          score += covered[t][l] ? 0 : 1;
        left[t][r][c] = score;

  // dynamic programming, t == T is a sentinel value
  for (int t = T-1; t >= 0; t--)
    for (int a = 0; a <= A; a++)
      for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) {
          int bestda = 0, bestv = 0; // best altitude adjustment, best value
          for (int da = -1; da <= 1; da++) {
            if (a <= 1 && da == -1)
              continue; // can't go down when on ground, or back on ground
            if (a + da > A)
              continue; // can't go above max altitude
            // pretend we moved b by da at time t
            Pt next = dest[a + da][r][c];
            if (next.r < 0)
              break; // loon exited, so score remains 0
            // score if going at these new coordinates, computed dynamically
            int rscore = best[t+1][a+da][next.r][next.c];
            // if above ground, score increased by number of covered targets
            if ((a + da) > 0)
              rscore += left[t+1][next.r][next.c];
            // break ties at random
            if (rscore > bestv || (rscore == bestv && (rand() % 2))) {
              // da is the best altitude adjustment
              bestv = rscore;
              bestda = da;
          // store best altitude adjustment, best value
          best[t][a][r][c] = bestv;
          dir[t][a][r][c] = bestda;

void print_sol() {
  FILE *f = fopen("output", "w");
  for (int t = 0; t < T; t++) {
    for (int b = 0; b < B; b++)
      fprintf(f, "%d ", solution[t][b]);
    fprintf(f, "\n");

int main(int argc, char **argv) {
  srand(42); // make it deterministic
  scanf("%d%d%d", &R, &C, &A);
  scanf("%d%d%d%d", &L, &V, &B, &T);
  scanf("%d%d", &rs, &cs);
  for (int l = 0; l < L; l++) {
    int r, c;
    scanf("%d%d", &r, &c);
    target[l] = Pt(r, c);
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++) {
  for (int a = 0; a <= A; a++)
    for (int r = 0; r < R; r++)
      for (int c = 0; c < C; c++)
        if (!a) {
          // wind at altitude 0 does not move loons
          dest[a][r][c] = Pt(r, c);
        } else {
          int dr, dc;
          scanf("%d%d", &dr, &dc);
          // populate dest with the coordinates where the wind takes the loon
          int destr, destc;
          destr = r + dr;
          destc = (c + dc + C) % C;
          if (destr < 0 || destr >= R)
            destr = destc = -1; // loon goes out
          dest[a][r][c] = Pt(destr, destc);

  // compute for each cell the list of targets covered by a loon at this cell
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
      for (int l = 0; l < L; l++)
        if (iscovered(l, r, c))

  int orig_score = 0;
  // iteratively compute a route for each loon given other routes
  while (true) {
    for (int br = 0; br < B; br++) {
      // route br given the routes of the other loons
      // first, forget about which cells are covered
      for (int t = 0; t <= T; t++)
        for (int l = 0; l < L; l++)
          covered[t][l] = false;
      // then, simulate the other loons (default routes are 0 ... 0)
      int score = 0;
      for (int b = 0; b < B; b++)
        if (b != br)
          score += simulate(b, &decide_sol);
      // now, compute the route of br with dynamic programming
      score += simulate(br, &decide_dyn);
      fprintf(stderr, "route %d\n", br);
      if (score > orig_score) {
        fprintf(stderr, "score was %d is %d\n", orig_score, score);
        orig_score = score;

  return 0;


The above code gets stuck fairly quickly. After reaching 698684 in about 17 minutes on my machine, it painfully and progressively goes up to 698734 in about 30 more minutes, and then stalls and does not seem to improve further (I left it running for about 30 additional minutes). Of course, this may vary given your choice of RNG seed (I hardcoded one in the code for reproducibility), and indeed for some unlucky seeds (one out of 5 that I tested) it seems that the code fails to reach a winning score. In any case, our final score of 700913 was achieved with a slightly more elaborate approach. If anyone is brave enough to want to have a look at our actual code, it is here.

We used the following additional improvement: whenever iterating over loons no longer makes progress, start trying to reroute two loons (or more than two) instead of just one. When doing this, unlike when rerouting only one loon, the solution score may decrease, so the code must rollback to the previous solution if the solution got worse. (If the score is still the same but the solution is different, however, it is good to keep the change, so that further optimizations with just one loon can be more effective.) We alternated in parallel optimization attempts with a single loon and attempts with two or three loons that did not make things worse. To be precise, we also tweaked solutions twice, by moving as many as 4 loons, at the expense of a slight drop in quality, to escape local optima and reach better solutions.

All of this was very hacky and we did not have a clean way to run many explorations in parallel on multiple machines, passing improved solutions to other running instances as they were found, some being more adventurous and others more conservative, and hopefully following what is known about metaheuristics. I trust that such approaches will be explored to unimaginable depths during the extended online contest. ;) I don't know if a more clever approach could yield substantial score improvements (rather than incremental ones); this may also turn up during the extended contest.

In any case, we had lots of fun during the contest, and we are very grateful to the organizers for making it happen. :)

Noms et verbes français qui n'existent qu'avec des préfixes

This post is about French, so I only write it in French.

Un problème amusant (merci, Valentine !) : quels sont les verbes et noms français qui existent avec différents préfixes, mais n'existent pas sans le préfixe ?

Par exemple, on peut déférer, référer, préférer, conférer, inférer, proférer, et même transférer, mais on ne peut jamais férer. On peut déduire, réduire, enduire, conduire, induire, et produire, mais pas duire. On peut révoquer, évoquer, convoquer, invoquer, et provoquer, mais pas voquer. Si on sait ce qu'est une déjection, une injection, une surjection, une projection, une bijection, et une interjection, qu'est-ce qu'une jection ? Une révolution, une dévolution, une involution, une convolution ; mais une volution ?

Ce billet cherche à trouver de façon automatique d'autres exemples de ce phénomène. Si seuls les résultats finaux vous intéressent, voici les 100 premières formes nominales et verbales trouvées, assorties des formes préfixées qui existent réellement. Bien sûr, il y a des choses inintéressantes et incorrectes dedans, parce que c'est généré automatiquement.

Voici les verbes :

férer:       déférer       référer       préférer      conférer      inférer    proférer  transférer
duire:       déduire       réduire       enduire       conduire      induire    produire
crire:       décrire       récrire       écrire        transcrire    redécrire
voquer:      révoquer      évoquer       convoquer     invoquer      provoquer
noncer:      dénoncer      renoncer      énoncer       prononcer
sister:      désister      résister      consister     insister
ouler:       rouler        couler        bouler        fouler        remouler
ter:         enter         conter        coter         rater         acter
puter:       députer       réputer       computer      disputer
spirer:      respirer      aspirer       conspirer     inspirer
osser:       désosser      rosser        cosser        bosser
stituer:     restituer     constituer    instituer     prostituer
clure:       reclure       conclure      inclure       exclure
cevoir:      décevoir      recevoir      concevoir
gresser:     régresser     agresser      progresser    transgresser
treindre:    retreindre    rétreindre    étreindre
iser:        riser         coniser       biser         remiser
gurgiter:    dégurgiter    régurgiter    ingurgiter
charner:     décharner     écharner      acharner
purer:       dépurer       épurer        apurer
vier:        dévier        envier        convier
voyer:       dévoyer       envoyer       convoyer
baucher:     débaucher     ébaucher      embaucher
iller:       ailler        ciller        piller        railler
arder:       darder        carder        barder        farder
tamer:       rétamer       entamer       étamer
soler:       désoler       consoler      insoler
iler:        piler         biler         filer         exiler
valer:       dévaler       avaler        ravaler
onder:       inonder       bonder        fonder        exonder
iger:        piger         figer         transiger     exiger
gir:         régir         surgir        agir
mailloter:   démailloter   emmailloter   remmailloter
mancher:     démancher     emmancher     remmancher
boîter:      déboîter      emboîter      remboîter
poter:       dépoter       empoter       rempoter
barquer:     débarquer     embarquer     rembarquer
paqueter:    dépaqueter    empaqueter    rempaqueter
créter:      décréter      concréter     excréter
ssortir:     ressortir     assortir      rassortir
ssembler:    ressembler    assembler     rassembler
sumer:       résumer       présumer      consumer
server:      réserver      préserver     conserver
specter:     respecter     inspecter     prospecter
irer:        désirer       airer         cirer
sulter:      résulter      consulter     insulter
membrer:     démembrer     remembrer
oter:        roter         doter         coter
amer:        ramer         damer         camer
tribuer:     rétribuer     contribuer    distribuer
ocher:       rocher        cocher        pocher
outer:       router        douter        bouter
aguer:       raguer        daguer        baguer
aliser:      réaliser      coaliser      baliser
criminer:    récriminer    incriminer    discriminer
ire:         rire          dire          raire
incer:       rincer        pincer        coincer
aser:        raser         caser         baser
pliquer:     répliquer     compliquer    expliquer
ister:       désister      pister        exister
ayer:        rayer         payer         bayer
endre:       rendre        pendre        fendre
uer:         ruer          puer          remuer
coler:       récoler       racoler       accoler
cuser:       récuser       excuser       accuser
ifier:       déifier       réifier
vertir:      avertir       convertir     invertir
piner:       épiner        copiner       rapiner
pier:        épier         copier        expier
iner:        suriner       biner         rainer
volvériser:  revolvériser  révolvériser
champir:     rechampir     réchampir
fréner:      refréner      réfréner
véler:       revéler       révéler
oucher:      doucher       coucher       boucher
ciser:       préciser      inciser       exciser
courager:    décourager    encourager
caisser:     décaisser     encaisser
visager:     dévisager     envisager
tourer:      détourer      entourer
dommager:    dédommager    endommager
grosser:     dégrosser     engrosser
crasser:     décrasser     encrasser
clencher:    déclencher    enclencher
velopper:    développer    envelopper
fourner:     défourner     enfourner
verguer:     déverguer     enverguer
tartrer:     détartrer     entartrer
gourdir:     dégourdir     engourdir
gluer:       dégluer       engluer
asser:       casser        passer        coasser
cimer:       décimer       écimer
pouiller:    dépouiller    épouiller
valuer:      dévaluer      évaluer
ller:        aller         coller        raller
anner:       canner        panner        banner
aver:        caver         paver         baver
aner:        caner         paner         faner
eindre:      ceindre       peindre       feindre
uver:        cuver         couver        prouver

Et les noms :

duction:      déduction      réduction      induction       enduction       conduction     production    diduction     transduction
quet:         coquet         caquet         biquet          baquet          paquet         triquet       parquet       taquet        piquet
jection:      déjection      rejection      injection       surjection      projection     bijection     interjection
férence:      déférence      référence      inférence       conférence      préférence     interférence
ception:      déception      réception      conception      interception    exception      perception
chet:         déchet         cochet         cachet          parchet         archet         pichet
tention:      détention      rétention      intention       contention      prétention
fection:      défection      réfection      infection       confection      perfection
cision:       décision       incision       concision       précision       excision
putation:     députation     réputation     imputation      computation     disputation
céphale:      encéphale      bicéphale      polycéphale     tricéphale      microcéphale   hydrocéphale
quette:       coquette       raquette       biquette        maquette        disquette      piquette
quetage:      coquetage      caquetage      baquetage       paquetage       parquetage     piquetage
ille:         caille         baille         paille          maille          taille         arille
ssement:      cassement      passement      massement       trissement      tassement      pissement
ducteur:      réducteur      inducteur      conducteur      producteur      transducteur
sseur:        casseur        masseur        passeur         tasseur         pisseur        chasseur
ssage:        cassage        massage        passage         tassage         pissage        chassage
posant:       déposant       proposant      composant       disposant       exposant
gression:     régression     ingression     progression     digression      transgression
venance:      survenance     convenance     prévenance      provenance      contrevenance
cepteur:      récepteur      concepteur     précepteur      intercepteur    percepteur
volution:     dévolution     révolution     involution      convolution
tage:         cotage         contage        ratage          matage          partage
lation:       délation       relation       dilation        translation
clamation:    déclamation    réclamation    proclamation    exclamation
scrit:        rescrit        inscrit        conscrit        proscrit
stitution:    restitution    institution    constitution    prostitution
scription:    rescription    inscription    conscription    proscription
chage:        cochage        cachage        trichage        tachage         perchage
sque:         casque         bisque         disque          basque          masque
logue:        prologue       autologue      radiologue      trilogue        hydrologue
nche:         canche         ranche         banche          manche          tanche
illage:       caillage       maillage       paillage        entreillage     taillage
métrie:       télémétrie     radiométrie    micrométrie     photométrie     hydrométrie
spiration:    respiration    inspiration    conspiration    perspiration
quage:        caquage        parquage       taquage         arquage         piquage
clusion:      réclusion      inclusion      conclusion      exclusion
sistance:     résistance     insistance     consistance     persistance
potement:     dépotement     empotement     tripotement     tapotement
portation:    déportation    importation    exportation     transportation
ction:        rection        coction        diction         paction
posante:      déposante      composante     disposante      exposante
vention:      invention      convention     prévention      intervention
hibition:     inhibition     cohibition     prohibition     exhibition
clinaison:    déclinaison    reclinaison    inclinaison
plication:    réplication    implication    complication    explication
collement:    décollement    recollement    encollement
tine:         rétine         ratine         patine          matine
gurgitation:  dégurgitation  régurgitation  ingurgitation
noncement:    dénoncement    renoncement    prononcement
nonciation:   dénonciation   renonciation   prononciation
ture:         enture         rature         biture          triture
posé:         imposé         préposé        composé         exposé
niement:      déniement      reniement      maniement
calement:     décalement     recalement     intercalement
sane:         insane         basane         persane         pisane
posement:     déposement     reposement     entreposement
solation:     désolation     insolation     consolation
bordement:    débordement    rebordement    transbordement
rdon:         cordon         cardon         pardon          chardon
bine:         cabine         bibine         combine         babine
vage:         cavage         ravage         bavage          pavage
llage:        collage        billage        tallage         pillage
sultante:     resultante     résultante     consultante
ngue:         cangue         dingue         mangue          tangue
illeuse:      railleuse      bailleuse      pailleuse       tailleuse
illeur:       railleur       bailleur       pailleur        tailleur
spirateur:    respirateur    inspirateur    conspirateur
tiste:        protiste       batiste        artiste         altiste
crément:      décrément      incrément      excrément
testation:    détestation    contestation   protestation
èdre:         polyèdre       trièdre        parèdre         exèdre
ssette:       cassette       massette       tassette        pissette
pier:         papier         polypier       tripier         pipier
lèvement:     relèvement     enlèvement     prélèvement
lier:         calier         palier         perlier         pilier
logie:        trilogie       radiologie     électrologie    hydrologie
sseuse:       casseuse       masseuse       pisseuse        chasseuse
nière:        panière        manière        tanière         pinière
lage:         calage         parlage        perlage         pilage
vasement:     dévasement     envasement     transvasement
primé:        déprimé        imprimé        comprimé
pette:        tripette       tapette        arpette         pipette
pilation:     dépilation     empilation     compilation
cernement:    décernement    concernement   discernement
pense:        dépense        impense        dispense
ploration:    déploration    imploration    exploration
hérence:      inhérence      déshérence     cohérence
valement:     dévalement     cavalement     ravalement
quillage:     requillage     coquillage     maquillage
crimination:  récrimination  incrimination  discrimination
quin:         requin         coquin         taquin
servation:    réservation    conservation   préservation
quisition:    réquisition    inquisition    perquisition
formé:        réformé        informé        transformé
sonance:      résonance      consonance     dissonance
tribution:    rétribution    contribution   distribution
sonnance:     résonnance     consonnance    dissonnance
paration:     réparation     préparation    disparation

Des détails, pour ceux que ça amuse. La liste de mots utilisée est Lefff, d'où je ne garde, soit que les verbes à l'infinitif, soit que les noms communs au singulier. Il y a 7817 infinitifs et 41680 noms.

La première question qu'il faut élucider, c'est de déterminer ce qu'est un préfixe. Pour cela, j'utilise la méthode suivante : pour chaque mot de la liste, pour chaque façon de le couper en un préfixe et un radical (c'est-à-dire toutes les longueurs possibles de préfixe) qui soit non-triviale (c'est-à-dire que radical et préfixe ne sont pas vides), si le radical est également un mot de la liste, alors cela compte comme une preuve que le préfixe considéré est effectivement un préfixe. Je trie les préfixes par nombre décroissant d'occurrences en ce sens, et je garde les meilleurs avec leur score.

Le code est ici. Pour les verbes, je garde les 30 meilleurs ; pour les noms, les 60 meilleurs, mais j'exclus ensuite ceux qui font une seule lettre, car il y a trop de bruit sinon. Voici les préfixes obtenus et leur nombre d'occurrences, pour les verbes :

dé     542
re     387
ré     166
dés    139
r      120
en     97
sur    97
é      87
auto   60
pré    58
a      49
d      44
em     43
con    39
c      37
p      32
in     30
co     28
com    26
b      23
f      22
pro    21
dis    20
ra     20
entre  20
trans  19
ex     19
redé   19
ac     18
rem    18

Et pour les noms :

dé       651
re       394
ré       223
in       195
dés      166
sur      150
en       147
co       105
con      91
im       90
pré      88
pro      81
em       81
télé     77
sous-    63
contre-  61
ca       59
anti     56
ra       55
auto     53
bi       52
com      52
di       50
ba       49
ma       48
pa       48
poly     47
radio    46
demi-    46
inter    46
tri      46
dis      44
contre   43
par      42
entre    41
électro  40
micro    40
ex       39
ta       38
ar       37
photo    36
hydro    35
trans    34
per      34
pi       32
cha      31
al       31

Ensuite, étant donnée cette liste pondérée de préfixes, je regarde chaque mot du dictionnaire et chaque préfixe. Si on peut retirer ce préfixe au mot, et que le résultat n'existe pas, alors c'est une forme manquante : son poids est la somme du poids de tous les préfixes tels quel la forme avec préfixe existe, mais que j'élève à un exposant (0.2, arbitrairement choisi) pour donner un meilleur score aux situations où de nombreux préfixes sont possibles.

Le code est ici. Pour les noms, j'élimine les propositions de longueur 3 ou moins. L'espacement final est réalisé avec column -t. Le fichier principal qui fait tout est duire.sh ; vous pouvez l'utiliser pour calculer davantage de formes que celles que j'inclus ici. Certains des fichiers intermédiaires sont également inclus dans le dépôt, par commodité.

Comme améliorations supplémentaires possibles, on pourrait appliquer des filtres plus sérieux pour identifier les propositions intéressantes : exiger notamment que le début du mot, par exemple les trois premières lettres, existe déjà dans un mot français ; peut-être filtrer les formes attestées avec préfixe pour vérifier que la prononciation correspond bien. On pourrait aussi imaginer de faire le même travail en tenant compte de la fréquence des mots : pour l'identification des préfixes et des formes manquantes, le vote de tous les mots se valent, mais ce n'est pas réaliste vu que certains mots sont beaucoup plus fréquents que d'autres ; et une forme sans préfixe qui existe mais est beaucoup plus rare que les formes avec préfixe qui existent, cela pourrait aussi être une réponse intéressante.

Google Hash Code 2014

This post is a French translation of this previous post. — Ce billet est une traduction française du billet original en anglais, réalisée avec Mc et Jill-Jênn.

En avril 2014, Google Paris a organisé un concours de programmation dans ses locaux à Paris : le Google Hash Code. Le problème à résoudre était plutôt amusant. Nous le présentons dans cet article, en précisant certaines stratégies adoptées par les équipes des Écoles normales supérieures. L'édition 2015 du concours est en cours, l'épreuve de qualification a eu lieu jeudi 12 mars (les inscriptions sont closes) ; c'est la nouvelle édition de l'épreuve qui nous a motivés pour rédiger notre solution pour l'épreuve de l'an dernier.

Les Écoles normales supérieures se sont particulièrement bien défendues lors de l'édition 2014, en décrochant les rangs 1, 2, 3, 4, 5, 7, 10 (les auteurs de cet article ont obtenu les rangs 5 et 7) et ont amélioré leurs résultats significativement dans les jours qui suivaient l'épreuve, l'échéance ayant été repoussée afin de pouvoir accueillir de nouvelles solutions.

Description du problème

L'énoncé complet est disponible sur le site officiel du concours.

On dispose d'une carte de Paris (à partir de données OpenStreetMap) qui décrit toutes les intersections et rues de la ville1. Comme dans la vraie vie, certaines rues sont à sens unique. Les segments sont étiquetés par leur longueur (en mètres) et leur durée de parcours (en secondes). Le problème est le suivant : à partir de 8 voitures Street View qui partent des locaux de Google Paris (rue de Londres), combien de mètres de rues est-il possible de parcourir au maximum en un temps limité de 15 heures ? On peut choisir d'emprunter certaines rues plusieurs fois, mais leur longueur ne sera comptée qu'une seule fois dans le total des mètres parcourus.

Le but est donc de déterminer un itinéraire pour les 8 voitures afin de parcourir un maximum de mètres différents de rues de Paris dans le temps imparti.

La méthode exhaustive

Naturellement, on peut en principe résoudre le problème en énumérant toutes les routes possibles pour les 8 voitures et en choisissant la meilleure. Il y a un nombre fini de telles routes, donc cette approche identifiera nécessairement la solution optimale. Ceci peut suffire pour un mathématicien, mais pas pour un informaticien : les chemins sont trop nombreux, ainsi il serait impossible de tout les explorer en pratique. (Le concours lui aussi est en temps limité…)

À titre de comparaison, s'il s'agissait de n'énumérer que les routes possibles en 10 heures pour une voiture atteignant à chaque minute une nouvelle intersection d'où partent au moins deux routes, il y aurait déjà \(2^{10 \times 60}\) chemins possibles, soit environ \(10^{180}\). Même si chaque atome du système solaire était un supercalculateur, on ne parviendrait pas à explorer toutes ces routes avant l'extinction du Soleil.

L'algorithme glouton

À l'inverse, une des approches les plus simples (outre les méthodes purement aléatoires) consiste utiliser un critère d'optimisation glouton : par exemple, choisir la rue la plus longue, la rue la plus rapide à parcourir, etc.). On planifie le parcours des voitures rue par rue, et on utilise le critère à chaque intersection pour choisir simplement la rue dans laquelle on se dirige ensuite.

Glouton basique

On considère pour commencer une unique voiture. Adoptons l'approche suivante : lorsque la voiture aboutit à une intersection qui lui permet de traverser des rues qu'elle n'a pas encore explorées, on choisit l'une d'entre elles : la plus longue, ou bien celle où l'on pourra visiter le plus de mètres par seconde. En revanche, si toutes les rues accessibles ont été visitées, on en choisit une au hasard. On réitère ce procédé tant qu'il reste du temps, et on fait de même pour les autres voitures.

Cette méthode gloutonne aura une performance correcte. Cela dit, de nombreux ajustements sont possibles, par exemple : planifier l'itinéraire de toutes les voitures simultanément plutôt que l'une après l'autre, ou bien commencer par envoyer les voitures à des intersections bien réparties dans Paris pour que chacune n'empiète pas sur le territoire des autres.

Cependant, l'inconvénient principal des solutions gloutonnes est qu'elles sont incapables d'anticiper. Par exemple, lorsqu'on choisit une rue au hasard parmi celles déjà visitées, on ne tente pas de se rapprocher d'un gisement de rues non visitées. Ainsi, une réflexion hâtive (c'est de là que vient le mot « glouton ») à partir d'informations partielles risque d'entraîner les voitures dans un dédale de rues déjà visitées.

Méthode gloutonne avec anticipation

On peut combiner la méthode gloutonne avec une recherche exhaustive qui se limite aux quelques prochains choix à faire. En d'autres termes, pour choisir la prochaine rue à suivre à chaque intersection, on ne le fera pas uniquement sur la base des mètres que cela permet de visiter en une étape. À la place, on peut par exemple considérer tous les chemins possibles de longueur 10 et choisir de traverser la première rue de celui qui donne les meilleurs résultats en dix étapes. On peut ensuite planifier le trajet de toutes les voitures en parallèle suivant cette idée. La longueur des chemins à considérer (dans cet exemple, "10") est bien entendu paramétrable ; en général, plus elle est longue, meilleurs seront les résultats, mais plus il sera difficile de les calculer.

Cette idée simple est facile à implémenter et donne des résultats plutôt satisfaisants. Une de nos équipes l'a essayée avec des chemins de longueur 17, sauf erreur, et il semble que plusieurs des dix meilleures équipes l'ont également suivie.

La méthode intelligente

Bien sûr, l'objet de ce billet est de décrire la solution intelligente, celle que l'on a implémentée au terme de l'épreuve, pour le concours étendu.

Voir le problème comme une recherche de chemin eulérien

Pour avoir la bonne intuition, il faut remarquer le lien entre le problème étudié et celui de la recherche d'un chemin eulérien dans un graphe, c'est-à-dire un chemin qui passe par chaque arête une et une seule fois (ou, autrement dit, parcourt le graphe "sans lever le crayon"). En effet, si l'on voit le plan de Paris comme un graphe, où les intersections sont les sommets et les rues sont les arêtes, un chemin eulérien dans ce graphe serait la solution idéale, qui parcourt chaque rue une unique fois sans perdre de temps dans des rues déjà visitées.

Bien sûr, il faut un peu se forcer pour faire ce rapprochement. Déjà, il y a huit voitures ; mais pour l'instant on supposera qu'il n'y en a qu'une seule, et on partagera le parcours entre les huit voitures plus tard. Ensuite, il y a une limite de temps, et toutes les rues n'ont pas la même valeur en termes de nombre de mètres photographiés ; mais on négligera cela et on prétendra être capable de visiter toutes les arêtes dans le temps imparti (on verra que ce n'est pas une supposition si irréaliste ;)). Ainsi, on ignore complètement la valeur en mètres des rues, et on ne s'intéresse qu'au temps nécessaire pour les parcourir.

Enfin, et c'est là la principale difficulté, le graphe d'entrée est un peu inhabituel, car certaines arêtes ne sont pas orientées, mais d'autres le sont, à savoir les rues à sens unique. À cause des sens uniques, il va falloir s'intéresser au problème du graphe eulérien orienté, et il va donc falloir choisir une orientation pour les arêtes non-orientées.

Soyons précis : à proprement parler, il sera impossible de trouver un chemin eulérien. Il est facile de démontrer la célèbre caractérisation suivante des graphes qui ont un chemin eulérien (appelons-les les graphes eulériens) : le degré entrant de chaque nœud (le nombre d'arêtes qui pointent vers lui) doit être égal à son degré sortant2. Bien sûr, le graphe d'entrée n'a aucune raison de remplir cette condition. Cependant, pour le problème du Hash Code, il n'est pas vraiment interdit de parcourir la même arête plusieurs fois ; c'est juste qu'on préfère éviter de le faire parce que ça fait perdre du temps.

Ainsi, on tente de rendre le graphe eulérien, en deux étapes. Premièrement, on choisira une direction pour orienter toutes les arêtes qui ne le sont pas, et ce d'une manière qui aide à rendre le graphe "plus eulérien". Ensuite, on ajoutera des arêtes pour le rendre réellement eulérien, afin de matérialiser la possibilité (dispendieuse) de parcourir une deuxième fois des arêtes visitées par ailleurs (c'est-à-dire des arêtes déjà visitées ou qui seront visitées de toute manière à un point ultérieur de la solution).

Orienter les arêtes non-orientées

Pour se ramener au problème du calcul d'un chemin eulérien orienté, il faut choisir une orientation pour toutes les arêtes non-orientées du graphe. Pour que ce problème de recherche de chemin eulérien soit plus facile à résoudre sur le graphe ainsi obtenu, on tentera d'orienter les arêtes d'une façon qui minimise la somme, sur tous les sommets, de la différence entre degré entrant et degré sortant. Intuitivement, plus cette valeur est petite, moins il faudra ajouter d'arêtes pour rendre le graphe eulérien.

Introduisons un peu de terminologie. Un sommet est dit surchargé (dans le graphe original, ou dans un graphe orienté obtenu à partir de ce dernier pour un certain choix d'orientation d'arêtes) si son degré entrant, en ne comptant que les arêtes orientées, est plus petit que son degré sortant. Il est dit sous-chargé dans le cas contraire, et équilibré si les deux degrés sont égaux. La charge d'un sommet est la différence entre son degré entrant et son degré sortant (elle est strictement positive pour un sommet surchargé, et strictement négative pour un sommet sous-chargé).

Comment choisir à présent la meilleure orientation pour les arêtes ? Le choix terminologique donnent déjà des indices : on voudrait orienter les arêtes de sorte à permettre aux sommets initialement surchargés de "transférer" une partie de leur charge aux sommets sous-chargés, suivant des chemins orientés, qui doivent être disjoint pour éviter de compter deux fois les arêtes intermédiaires. Il se trouve que l'on peut formuler cela proprement comme un problème de flot maximum.

Les sommets surchargés et sous-chargés sont respectivement représentés comme des sources et des puits dont la capacité est égale à leur charge. Chaque arête non-orientée est représentée comme une paire d'arêtes orientées allant dans chaque direction, leur capacité étant fixée à 1. Les arêtes déjà orientées sont ignorées.

Le problème de flot correspondant peut être résolu à l'aide de n'importe quel algorithme de flot. Par le théorème des flots entiers, le flot suivant chaque arête est de 0 ou de 1. Ainsi, le résultat du problème de flot décrit une façon d'orienter certaines des arêtes non-orientées (mais pas toutes), suivant la direction du flot qui passe par elles.

Il reste le problème que certaines arêtes du résultat n'ont pas d'orientation spécifiée, à savoir celles qui n'étaient pas utilisées du tout dans le flot optimal. Pour régler ce problème, il suffit d'orienter toutes les arêtes restantes au hasard. Bien sûr, ceci peut faire croître la somme que l'on cherche à minimiser, et pour remédier à cela on effectue ensuite l'amélioration suivante, que l'algorithme de flot avait déjà vérifiée avant la phase d'orientation aléatoire : pour tout chemin orienté qui utilise exclusivement les arêtes nouvellement orientées, si l'on peut diminuer la somme à optimiser en inversant la direction du chemin (c'est-à-dire que l'origine du chemin était sous-chargée et sa destination était surchargée), alors on inverse l'orientation de cette manière. Ceci incrémente la charge de l'origine, décrémente la charge de la destination, et ne change rien aux autres charges, donc c'est une amélioration. Pour effectuer cela de façon efficace, notez qu'il suffit de considérer toutes les paires de sommets. Dès que l'on trouve une paire d'un sommet sous-chargé et d'un sommet surchargé¸ on peut rechercher un chemin allant de l'un à l'autre, et l'inverser si on en trouve un.

Ainsi, à la fin de ce processus, on obtient un graphe orienté où l'on a tenté de minimiser la somme des différences entre le degré entrant et le degré sortant, sur tous les nœuds, pour rendre le graphe aussi eulérien que possible. Il reste à le rendre véritablement eulérien en ajoutant des arêtes pour que tous les sommets soient équilibrés.

Ajouter des arêtes

Intuitivement, les arêtes que l'on veut ajouter pour rendre le graphe eulérien correspondent à la possibilité d'ajouter au chemin des arêtes parcourues par ailleurs.

En d'autres termes, si on ajoute une arête du sommet \(i\) au sommet \(j\), cela signifie que l'on va aller du sommet \(i\) au sommet \(j\) suivant un chemin d'arêtes qui seront visitées par ailleurs. Tout le temps passé dans de tels chemins est perdu, et ne contribue en rien à l'objectif. Ainsi, le coût d'ajouter une arête de \(i\) à \(j\) devrait être la durée nécessaire pour aller de \(i\) à \(j\) suivant n'importe quel chemin dans le graphe. Pour être plus précis, on peut dans ce cadre suivre un chemin qui viole l'orientation que nous avions choisie pour les arêtes non-orientées, et cela ne pose pas problème ; donc on parle vraiment de la durée d'un plus court chemin dans le graphe original.

Ainsi, on commence par précalculer la durée du plus court chemin entre toutes les paires de sommets du graphe original, à l'aide de l'algorithme de Floyd-Warshall.

Ensuite, on représente le problème de choisir les arêtes à ajouter comme un problème de couplage de poids minimal dans un graphe biparti pondéré. D'un côté du graphe biparti, on place les sommets qui sont surchargés dans le graphe obtenu à l'issue de la phase précédente, copiés en un nombre d'exemplaires égal à leur charge. On crée de la même manière l'autre côté du graphe biparti avec les sommets sous-chargés3. Le graphe biparti dispose également d'une arête entre chaque paire de sommets de chaque partie, dont le poids est le temps du plus court chemin du premier au second.

À présent, un couplage parfait dans ce graphe biparti représente une façon d'ajouter le bon nombre d'arêtes d'une manière qui équilibre tous les sommets, et imposer que le poids d'un tel couplage soit minimal signifie que l'on veut minimiser le temps perdu à suivre des arêtes qui sont visitées par ailleurs. On utilise ainsi l'algorithme hongrois pour résoudre ce problème, et pour compléter le graphe orienté obtenu à l'issue de la phase précédente pour le rendre eulérien.

Construction du chemin eulérien

Le graphe obtenu est maintenant orienté, et chaque sommet est équilibré, donc on peut y construire un chemin eulérien. Pour le calculer, une simple approche gloutonne suffit. (Il y a peut-être des améliorations possibles pour optimiser par rapport aux étapes suivantes, mais nous n'en avons pas cherché.)

Depuis le chemin eulérien, en remplaçant les arêtes qui ont été ajoutées dans la phase précédente par les plus courts chemins auxquels elles correspondent, nous obtenons un itinéraire qui est une assez bonne solution pour le parcours de toutes les rues de Paris par une unique voiture en le moins de temps possible.

Partage du chemin entre voitures

On se rappelle à présent que l'on a huit voitures et non une seule, et qu'il faut donc découper la route obtenue entre les voitures.

Voici la méthode suivie. Prenons la première voiture, et faisons-lui suivre le début du chemin jusqu'à un quart du temps alloué. Ensuite, en considérant le reste du chemin qu'elle peut parcourir jusqu'à la fin de son temps, on cherche le sommet qu'elle traverse qui est le plus rapide à atteindre depuis le point de départ (dont on rappelle qu'il s'agit des bureaux de Google). La première voiture va jusqu'à ce point, et s'arrête. La voiture suivante prend le plus court chemin jusqu'à ce point, poursuit sa route suivant la suite de l'itinéraire pendant un quart du temps alloué, puis continue jusqu'au point le plus proche du point de départ obtenu de la même manière. On répète cela jusqu'à la dernière voiture, qui s'occupe de tout le reste de l'itinéraire.

Bien entendu, si l'on coupe le chemin à un point proche du point de départ, c'est pour minimiser le temps perdu par la voiture suivante pour reprendre l'itinéraire. Cette solution donnera toujours trop de travail à la dernière voiture, mais on verra plus tard comment équilibrer la durée des trajets des voitures. Si on force les voitures à parcourir l'itinéraire pendant au moins un quart du temps alloué, c'est pour rendre cet équilibrage plus facile, en garantissant que les parcours de toutes les voitures sont suffisamment longs pour se rencontrer de nombreuses fois.

Le trajet obtenu constitue la solution initiale pour huit voitures. Il reste à l'optimiser.


On itère maintenant un certain nombre d'optimisations destinées à modifier légèrement le chemin en l'améliorant, jusqu'à ce que l'on juge que la qualité du résultat est suffisante.

Bien entendu, toutes les optimisations ne sont pas aussi efficaces, et l'ordre dans lequel elles sont appliquées peut engendrer des différences significatives. Il est difficile de retrouver exactement l'ordre dans lequel elles ont été appliquées pendant le concours, ni le nombre d'itérations, mais il n'y avait de toute manière pas beaucoup de logique pour justifier ces choix.


Pour tout sous-chemin d'un chemin d'une voiture, qui consiste uniquement d'arêtes déjà visitées par ailleurs, on peut le remplacer par un plus court chemin entre les extrémités du sous-chemin, calculé à l'aide du Floyd-Warshall précédemment évoqué.

Échange de boucles

Supposons qu'une voiture se déplace d'un sommet \(i\) à un sommet \(j\), puis effectue un cycle \(C\), puis se déplace à nouveau de \(j\) à \(i\), et l'arête entre \(i\) et \(j\) est déjà visitée par ailleurs. Si on peut trouver une voiture qui passe par n'importe lequel des sommets de \(C\), alors cette voiture peut s'occuper de tout le cycle \(C\) sur son chemin, et la première voiture peut économiser \(C\) et l'aller-retour entre \(i\) et \(j\) (l'économie totale est donc de deux fois la longueur de l'arête \(i\)\(j\)).

Bien entendu, ceci peut contribuer à déséquilibrer la longueur du trajet des voitures, mais on s'occupera de ces situations plus tard.


Si une voiture termine son chemin par un sous-chemin déjà visité par une autre voiture, on peut simplement le supprimer.

Exploration exhaustive

Pour tout sous-chemin de chaque chemin de chaque voiture, jusqu'à une certaine longueur, on vérifie si le sous-chemin peut être remplacé par un chemin plus court, qui visite tout de même toutes les rues du chemin qui ne sont pas visitées par ailleurs. Dans ce cas, on remplace le sous-chemin par le chemin trouvé. Ceci diffère de l'écrémage en ce sens que les sous-chemins peuvent inclure des arêtes qui ne sont pas visitées par ailleurs ; dans ce cas, le remplacement devra également passer par ces arêtes, possiblement dans un ordre différent.


Jusqu'ici, on n'a pas tenu compte de la contrainte de temps maximal (15 heures). Celle-ci a besoin d'être satisfaite par toutes les voitures ; on ne peut donc pas se contenter d'une solution où une voiture a un trajet beaucoup plus long que les autres. Du reste, si on parvient à trouver une solution qui passe par toutes les arêtes (et ce fut le cas !), la qualité d'une solution est jugée selon son temps restant, c'est-à-dire \(T - \max_{c \in \{1, \ldots, 8\}} t_c\)\(T\) est la limite de temps, et \(t_c\) le temps pris par la voiture \(c\).

Idéalement, on voudrait donc que toutes les voitures effectuent des trajets qui prennent le même temps. Ceci signifie qu'il est souhaitable d'échanger des portions longues du trajet des voitures les plus occupées avec des portions plus courtes du trajet des voitures moins occupées.

En pratique, on recherche des paires de sommets \(x\) et \(y\) telles que deux voitures passent par \(x\) puis par \(y\). En général, les chemins des deux voitures entre \(x\) et \(y\) auront une longueur différente. Ainsi, si échanger les chemins permet de diminuer la différence de durée entre l'itinéraire des deux voitures, alors on procède à l'échange.

Cette méthode gloutonne peut être itérée aussi longtemps que nécessaire. En fait, comme les chemins des voitures ont tendance à se croiser très souvent, la méthode fonctionne très bien et converge rapidement vers un état où toutes les voitures suivent des itinéraires dont la durée est la même, à la seconde près, peu importe les itinéraires initiaux.


La stratégie intelligente décrite ici parvient à parcourir toutes les rues de Paris dans le temps alloué (et même en 9 minutes de moins). Dommage de ne pas l'avoir réussi pendant le concours lui-même (plutôt que pendant l'extension), mais c'est déjà ça ! :)

État de l'art

Nous avons développé toutes ces méthodes par nous-mêmes, et n'avons pas regardé sérieusement l'état de l'art des méthodes utilisées par des gens qui ont déjà essayé de résoudre des problèmes similaires. En fait, notre problème est connu comme le problème du postier chinois, car il est également utile pour optimiser les distributions postales (et a été étudié par un mathématicien chinois).

Plus spécifiquement, notre version est le "\(k\)-mixed postman problem", car on a plusieurs voitures (\(k\)=8), et car le graphe est mixte : certaines des arêtes sont orientées, d'autres non. De manière assez surprenante, la solution optimale peut être calculée en temps polynomial pour les versions orientées et non-orientées4, mais la version mixte est NP-difficile5.

Il serait intéressant de comparer le résultat de notre méthode à l'état de l'art. Nous nous sommes rapidement comparés à des résultats de référence sur des jeux de données existants et nous n'avons pas de raison de penser que nos algorithmes sont meilleurs. Mais peu importe, nous nous sommes bien amusés. :)


Les idées de ce billet ne sont pas les miennes : à peu près tout a été fait par d'autres élèves de l'ENS. Les étapes de la solution intelligente, hormis les optimisations subséquentes, ont été conçues et implémentées par gnomnain (code). Et les optimisations par elarnon (code), and Mc and mehdi (code). (Tout le code est "en écriture seule" (write-only) et ne contient aucune documentation d'aucune sorte, je déconseille de tenter de l'utiliser.)

Ce billet a été écrit à partir d'une version préliminaire de Mc. Merci à Jill-Jênn, elarnon, Armavica et gprano pour leur relecture et remarques sur la version originale.

  1. Les coordonnées géographiques des intersections étaient également fournies, mais on n'en fera pas usage. Ceci étant dit, au risque d'anticiper sur la suite, certaines équipes ont eu des résultats intéressants en utilisant simplement l'heuristique gloutonne consistant à toujours choisir à chaque intersection la rue la plus à gauche parmi celles qui n'ont pas encore été visitées, ceci afin de faire des trajets en forme de spirale. 

  2. Pour être précis, le critère énoncé ici est celui de l'existence d'un cycle eulérien, et non un chemin. Ceci étant dit, comme il faudrait imposer aux chemins de commencer au sommet de départ, il est plus simple de rechercher un cycle, ce qui n'est qu'un cas particulier de chemin. 

  3. On peut vérifier que les deux côtés ont bien la même taille, car le total des degrés entrants des sommets est égal au total des degrés sortants ; c'est en fait le nombre d'arêtes dirigées dans le graphe obtenu à l'issue de la phase précédente. 

  4. J. Edmonds, E.L. Johnson. Matching Euler tours and the Chinese postman, Mathematical Programming 5 (1973) 88–124. 

  5. C.H. Papadimitriou. On the complexity of edge traversing, Journal of the ACM 23 (1976) 544–554. 

Hash Code 2015 selection round

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.


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.


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 = 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
    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);

  return 0;


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.