Discrete : wip-worktree-statedescrete

11 files changed, 947 insertions, 0 deletions

diff --git a/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch b/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch
new file mode 100644
index 0000000..bb4a6e1
--- /dev/null
+++ b/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch
@@ -0,0 +1,38 @@
+diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c
+index 7830651..106328b 100644
+--- a/01-knapsack/ks_dp-ng.c
++++ b/01-knapsack/ks_dp-ng.c
+@@ -120,20 +120,32 @@ static void solve(Solver* solver)
+ 
+         // this computes the top-left bottom-right diagonal,
+         // values above this don't need to be computed
++        j = k;
+         min_c -= w;
+         lower_bound = (k - min_c);
+         if (lower_bound < w)
+           lower_bound = w;
+-        for (j = k; j >= lower_bound; j--, data--, up_left--)
++
++        while (j >= lower_bound)
+           {
+              counter++;
++               /* printf("  % 4d\n", j); */
+ 
+              if (data->v < (v + up_left->v))
+                {
+                   data->i = i;
+                   data->v = v + up_left->v;
+                   data->w = w + up_left->w;
++                  if (j == k) {
++                       j -= w;
++                       data -= w;
++                       up_left -= w;
++                       continue;
++                  }
+                }
++             j--;
++             data--;
++             up_left--;
+           }
+ 
+         if (debug > 2)
diff --git a/01-knapsack/1-relaxation-what-to-do-with.patch b/01-knapsack/1-relaxation-what-to-do-with.patch
new file mode 100644
index 0000000..cbc59e3
--- /dev/null
+++ b/01-knapsack/1-relaxation-what-to-do-with.patch
@@ -0,0 +1,143 @@
+diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c
+index 7830651..ddb0d04 100644
+--- a/01-knapsack/ks_dp-ng.c
++++ b/01-knapsack/ks_dp-ng.c
+@@ -7,12 +7,14 @@
+ 
+ #define NONE -1
+ 
++enum { RELAX = 0, NO_RELAX };
+ enum { SORT_DESC = 0, SORT_ASC };
+ enum { UNSORTED = 0, SORT_WR, SORT_VR, SORT_RW, SORT_RV};
+ 
+ static int debug;
+ static int sort;
+ static int sort_order;
++static int relax;
+ 
+ typedef struct _InputItem
+ {
+@@ -25,6 +27,7 @@ typedef struct _SolverItem {
+      int i;             /* index of the selected item */
+      int v;             /* cumulated value */
+      int w;             /* cumulated weight */
++     float r;           /* linear relaxation best value */
+ } SolverItem;
+ 
+ typedef struct _Solver
+@@ -87,11 +90,39 @@ item_cmp(const void *p1, const void *p2)
+    return 0;
+ }
+ 
++static inline float relax_item(Solver* solver, SolverItem* data, int start)
++{
++   int w;
++   int i;
++   float relax;
++   const InputItem *item;
++
++   w = data->w;
++   relax= data->v;
++   item = &solver->items[start];
++   for (i = start; i < solver->n; i++, item++)
++     {
++        if ((w + item->w) <= solver->k)
++          {
++             w += item->w;
++             relax += item->v;
++          }
++        else
++          {
++             relax += (item->v * ((solver->k - w) / (float)item->w));
++             break;
++          }
++     }
++
++   return relax;
++}
++
+ static void solve(Solver* solver)
+ {
+    int n, k;
+    int v, w;
+    int i, j;
++   float r;
+    int min_c, lower_bound;
+    const InputItem *item;
+    SolverItem *data;
+@@ -105,7 +136,16 @@ static void solve(Solver* solver)
+ 
+    if (debug > 2)
+      {
+-        printf("\nformat V(i,W)\n");
++        printf("\nformat V(i,W,r)\n");
++     }
++
++   /* RELAXATION */
++   if (relax == RELAX)
++     {
++        data = solver->column;
++        r = relax_item(solver, data, 0);
++        for (j = 0; j <= k; j++, data++)
++          data->r = r;
+      }
+ 
+    /* SOLVE */
+@@ -134,6 +174,12 @@ static void solve(Solver* solver)
+                   data->v = v + up_left->v;
+                   data->w = w + up_left->w;
+                }
++
++             /* RELAXTION must be cached */
++             if (relax == RELAX)
++               {
++                  data->r = relax_item(solver, data, (i + 1));
++               }
+           }
+ 
+         if (debug > 2)
+@@ -141,8 +187,8 @@ static void solve(Solver* solver)
+              printf("i=%d; j=k; j<=%d:\n", i, lower_bound);
+              data = solver->column;
+              for (j = 0; j <= k; j++, data++)
+-               printf("  %d : % 4d(% 2d % 2d)\n",
+-                      j, data->v, data->i, data->w);
++               printf("  %d : % 4d(% 2d % 2d %.1f)\n",
++                      j, data->v, data->i, data->w, data->r);
+              printf("\n");
+           }
+      }
+@@ -152,8 +198,8 @@ static void solve(Solver* solver)
+         printf("i=%d:\n", solver->n - 1);
+         data = solver->column;
+         for (j = 0; j <= k; j++, data++)
+-          printf("  % 4d(% 2d % 2d)\n",
+-                 data->v, data->i, data->w);
++          printf("  % 4d(% 2d % 2d %.1f)\n",
++                 data->v, data->i, data->w, data->r);
+      }
+ 
+    if (debug > 0)
+@@ -194,10 +240,11 @@ int main(int argc, char** argv, char** env)
+    InputItem *item;
+ 
+    debug = 0;
++   relax = NO_RELAX;
+    sort = UNSORTED;
+    sort_order = SORT_DESC;
+    excpected_value = NONE;
+-   while ((opt = getopt(argc, argv, "d:e:s:S")) != -1) {
++   while ((opt = getopt(argc, argv, "d:e:s:SR")) != -1) {
+         switch (opt) {
+            case 'd':
+               debug = atoi(optarg);
+@@ -211,6 +258,9 @@ int main(int argc, char** argv, char** env)
+            case 'S':
+               sort_order = SORT_ASC;
+               break;
++           case 'R':
++              relax = RELAX;
++              break;
+            default: /* '?' */
+               fprintf(stderr, "Usage: %s [falgs] input\n",
+                       argv[0]);
diff --git a/01-knapsack/ks_dp b/01-knapsack/ks_dp
new file mode 100755
index 0000000..0267f00
--- /dev/null
+++ b/01-knapsack/ks_dp
diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c
index 7830651..282cecf 100644
--- a/01-knapsack/ks_dp-ng.c
+++ b/01-knapsack/ks_dp-ng.c
@@ -160,6 +160,75 @@ static void solve(Solver* solver)
      printf("loops count: %u\n", counter);
 }
 
+static void reset_output(char *output, int bits)
+{
+   char *ch;
+   char *end;
+
+   end = output + bits;
+   for (ch = output; ch < end; )
+     {
+        (*ch++) = '0';
+        (*ch++) = ' ';
+     }
+   ch--;
+   *ch = '\0';
+}
+
+static int print(Solver* solver)
+{
+   int ret;
+   int v, w;
+   char *output;
+   const Item *item;
+   const SolverData *data;
+
+   output = calloc((solver->n * 2), sizeof(char));
+   if (!output)
+     {
+        fprintf(stderr, "ERROR: output calloc\n");
+        return EXIT_FAILURE;
+     }
+   reset_output(output, (solver->n * 2));
+
+   data = solver->column + solver->k;
+   printf("%d %d\n", data->v, 0);
+
+   v = 0;
+   w = 0;
+   /* for (data = solver->column + solver->k; data->i != -1 ; data -= item->w) */
+   for (data = solver->column + solver->k; data->s != -1 ; data -= item->w)
+     {
+        /* item = &solver->items[data->i]; */
+        item = &solver->items[data->s];
+        output[(item->i) * 2] = '1';
+        if (debug > 1)
+          printf("  from % 6d  - take % 4d (% 4d % 4d)\n",
+                 data->v, item->i, item->v, item->w);
+        v += item->v;
+        w += item->w;
+     }
+   printf("%s\n", output);
+
+   free(output);
+
+   ret = EXIT_SUCCESS;
+   data = solver->column + solver->k;
+   if (v != data->v)
+     {
+        fprintf(stderr, "ERROR: value %d != %d\n", v, data->v);
+        ret = EXIT_FAILURE;
+     }
+   if (w > solver->k)
+     {
+        fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k);
+        ret = EXIT_FAILURE;
+     }
+
+   return ret;
+
+}
+
 static int check(Solver *solver, int excpected_value)
 {
    const SolverItem *data;
diff --git a/01-knapsack/ks_dp2.c b/01-knapsack/ks_dp2.c
new file mode 100644
index 0000000..a776f24
--- /dev/null
+++ b/01-knapsack/ks_dp2.c
@@ -0,0 +1,436 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+#include <time.h>
+#include <unistd.h>
+
+enum { UNSORTED = 0, SORT_WR, SORT_VR, SORT_RW, SORT_RV};
+enum { DESC = 0, ASC };
+enum { NO_RELAX = 0, RELAX };
+
+static int debug;
+static int sort;
+static int sort_order;
+static int relax;
+
+typedef struct _Item
+{
+   int i;
+   int v;
+   int w;
+} Item;
+
+typedef struct _SolverData {
+     int v;    /* cumulated value */
+     int w;    /* cumulated weight */
+     float r;  /* relaxed max value */
+     int i;    /* index of the selected item */
+} SolverData;
+
+typedef struct _Solver
+{
+   int k;               /* capacity */
+   int n;               /* items # */
+   int sum_w;           /* sum of weight of all items */
+   Item *items;         /* items */
+   SolverData *column;  /* solver column */
+} Solver;
+
+static int
+item_cmp(const void *p1, const void *p2)
+{
+   int ret;
+   float r1, r2;
+   const Item *i1, *i2;
+
+   i1 = (const Item *) p1;
+   i2 = (const Item *) p2;
+
+   ret = ((sort_order == ASC) ? 1 : -1);
+
+   if (sort == SORT_WR)
+     {
+        if (i1->w > i2->w) return  ret;
+        if (i1->w < i2->w) return -ret;
+     }
+   else if (sort == SORT_VR)
+     {
+        if (i1->v > i2->v) return  ret;
+        if (i1->v < i2->v) return -ret;
+     }
+   else  // SORT_RW | SORT_RV
+     {
+        r1 = i1->v / (float)i1->w;
+        r2 = i2->v / (float)i2->w;
+        if (r1 > r2) return  ret;
+        if (r1 < r2) return -ret;
+     }
+
+   if (sort == SORT_RW)
+     {
+        if (i1->w > i2->w) return  ret;
+        if (i1->w < i2->w) return -ret;
+     }
+   else if (sort == SORT_RV)
+     {
+        if (i1->v > i2->v) return  ret;
+        if (i1->v < i2->v) return -ret;
+     }
+   else  // SORT_WR | SORT_VR
+     {
+        r1 = i1->v / (float)i1->w;
+        r2 = i2->v / (float)i2->w;
+        if (r1 > r2) return  ret;
+        if (r1 < r2) return -ret;
+     }
+
+   return 0;
+}
+
+static void reset_output(char *output, int bits)
+{
+   char *ch;
+   char *end;
+
+   end = output + bits;
+   for (ch = output; ch < end; )
+     {
+        (*ch++) = '0';
+        (*ch++) = ' ';
+     }
+   ch--;
+   *ch = '\0';
+}
+
+static int print(Solver* solver)
+{
+   int ret;
+   int v, w;
+   char *output;
+   const Item *item;
+   const SolverData *data;
+
+   output = calloc((solver->n * 2), sizeof(char));
+   if (!output)
+     {
+        fprintf(stderr, "ERROR: output calloc\n");
+        return EXIT_FAILURE;
+     }
+   reset_output(output, (solver->n * 2));
+
+   data = solver->column + solver->k;
+   printf("%d %d\n", data->v, 0);
+
+   v = 0;
+   w = 0;
+   for (data = solver->column + solver->k; data->i != -1 ; data -= item->w)
+     {
+        item = &solver->items[data->i];
+        output[(item->i) * 2] = '1';
+        if (debug > 1)
+          printf("  from % 6d  - take % 4d (% 4d % 4d)\n",
+                 data->v, item->i, item->v, item->w);
+        v += item->v;
+        w += item->w;
+     }
+   printf("%s\n", output);
+
+   free(output);
+
+   ret = EXIT_SUCCESS;
+   data = solver->column + solver->k;
+   if (v != data->v)
+     {
+        fprintf(stderr, "ERROR: value %d != %d\n", v, data->v);
+        ret = EXIT_FAILURE;
+     }
+   if (w > solver->k)
+     {
+        fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k);
+        ret = EXIT_FAILURE;
+     }
+
+   return ret;
+
+}
+
+static inline void relax_item(Solver* solver, SolverData* data, int start)
+{
+   int w;
+   int i;
+   const Item *item;
+
+   w = data->w;
+   data->r = data->v;
+   item = &solver->items[start];
+   for (i = start; i < solver->n; i++, item++)
+     {
+        if ((w + item->w) <= solver->k)
+          {
+             w += item->w;
+             data->r += item->v;
+          }
+        else
+          {
+             data->r += (item->v * ((solver->k - w) / (float)item->w));
+             break;
+          }
+     }
+}
+
+static void solve(Solver* solver)
+{
+   int n, k;
+   int v, w;
+   int i, j;
+   int max_c, upper_bound;
+   const Item *item;
+   SolverData *data;
+   const SolverData *up_left;
+
+   unsigned int counter;
+
+   n = solver->n;
+   k = solver->k;
+   max_c = solver->sum_w;
+
+   /* RELAXATION */
+   if (relax == RELAX)
+     {
+        data = solver->column;
+        for (j = 0; j <= k; j++, data++)
+          relax_item(solver, data, 0);
+     }
+
+   if (debug > 2)
+     {
+        printf("\ncurrent V(i,s,W,r)\n");
+     }
+
+   /* SOLVE */
+   counter = 0;
+   item = solver->items;
+   for (i = 0; i < n; i++, item++)
+     {
+        v = item->v;
+        w = item->w;
+        data = NULL;
+        data = solver->column + solver->k;
+        up_left = solver->column + (solver->k - w);
+
+        // this computes the top-left bottom-right diagonal,
+        // values above this don't need to be computed
+        max_c -= w;
+        upper_bound = (((k - max_c) > w) ? (k - max_c) : w );
+        for (j = k; j >= upper_bound; j--, data--, up_left--)
+          {
+             // FIXME
+             /* if ((relax == RELAX) && (data->v == (int)data->r)) */
+             /* if ((relax == RELAX) && (data->v <= (int)data->r)) */
+             /* if ((relax == RELAX) && (data->v < (int)data->r)) */
+             /*   { */
+             /*      /1* fprintf(stderr,"RELAX\n"); *1/ */
+             /*      continue; */
+             /*   } */
+
+             counter++;
+
+             if (data->v < (v + up_left->v))
+               {
+                  data->i = i;
+                  data->v = v + up_left->v;
+                  data->w = w + up_left->w;
+                  /* if (j == k) */
+                  /*   { */
+                  /*      for (critical = data; critical->i != -1 ; */
+                  /*           critical -= solver->items[data->i].w) */
+                  /*        { */
+                  /*           critical->c = critical->i; */
+                  /*        } */
+                  /*      print_vector(solver, i + 1, 0); */
+                  /*      print_vector(solver, i + 1, 1); */
+                  /*   } */
+               }
+
+             /* RELAXTION must be cached */
+             if (relax == RELAX)
+               {
+                  relax_item(solver, data, (i + 1));
+               }
+          }
+
+        if (debug > 2)
+          {
+             printf("i=%d; j=k; j<=%d:\n", i, upper_bound);
+             data = solver->column;
+             for (j = 0; j <= k; j++, data++)
+               printf("  % 4d(% 2d % 2d %.1f)\n",
+                      data->v, data->i, data->w, data->r);
+             printf("\n");
+          }
+     }
+
+   if (debug > 0)
+     printf("loops count: %u\n", counter);
+
+   if (debug == 2)
+     {
+        printf("i=%d:\n", solver->n - 1);
+        data = solver->column;
+        for (j = 0; j <= k; j++, data++)
+          printf("  % 4d(% 2d % 2d %.1f)\n",
+                 data->v, data->i, data->w, data->r);
+     }
+}
+
+int main(int argc, char** argv, char** env)
+{
+   FILE *fp;
+
+   int opt;
+   int ret;
+   int i;
+   uint64_t dt;
+   struct timespec t0;
+   struct timespec t1;
+
+   Solver solver;
+   Item *item;
+
+   sort = UNSORTED;
+   sort_order = DESC;
+   relax = NO_RELAX;
+   debug = 0;
+   while ((opt = getopt(argc, argv, "d:s:SR")) != -1) {
+        switch (opt) {
+           case 's':
+              sort = atoi(optarg);
+              break;
+           case 'd':
+              debug = atoi(optarg);
+              break;
+           case 'S':
+              sort_order = ASC;
+              break;
+           case 'R':
+              relax = RELAX;
+              break;
+           default: /* '?' */
+              fprintf(stderr, "Usage: %s [-d level] [-s 0|1] [-S] [-R]input\n",
+                      argv[0]);
+              return EXIT_FAILURE;
+        }
+   }
+
+   if (sort > SORT_RV) sort = UNSORTED;
+   if (sort_order > ASC) sort = DESC;
+
+   if (optind >= argc) {
+        fprintf(stderr,"input file missing\n");
+        return EXIT_FAILURE;
+   }
+
+   if (debug > 0) printf("%s\n", argv[optind]);
+   fp = fopen(argv[optind], "r");
+   if (fp == NULL)
+     {
+        fprintf(stderr, "I couldn't open results.dat for reading.\n");
+        return EXIT_FAILURE;
+     }
+
+   /* read k and n */
+   if (fscanf(fp, "%d %d\n", &solver.n, &solver.k) != 2)
+     {
+        fprintf(stderr, "ERROR: read first line\n");
+        return EXIT_FAILURE;
+     }
+   if (debug > 0) printf("  K:%d N:%d\n", solver.k, solver.n);
+
+   /* allocate */
+   solver.items = calloc(solver.n, sizeof(Item));
+   if (!solver.items)
+     {
+        fprintf(stderr, "ERROR: items calloc\n");
+        return EXIT_FAILURE;
+     }
+
+   solver.column = calloc((solver.k + 1), sizeof(SolverData));
+   if (!solver.column)
+     {
+        free(solver.items);
+        fprintf(stderr, "ERROR: column calloc\n");
+        return EXIT_FAILURE;
+     }
+   for (i = 0; i < (solver.k + 1); i++)
+     solver.column[i].i = -1;
+
+   /* read items */
+   solver.sum_w = 0;
+   item = solver.items;
+   for (i = 0; i < solver.n; i++, item++)
+     {
+        item->i = i;
+        fscanf(fp, "%d %d\n", &item->v, &item->w);
+        solver.sum_w += item->w;
+     }
+   fclose(fp);
+
+   if (sort != UNSORTED)
+     qsort(solver.items, solver.n, sizeof(Item), item_cmp);
+
+   if (debug > 1)
+     {
+        printf("  Items ");
+        if (sort == UNSORTED)
+          {
+              printf("unsorted\n");
+          }
+        else
+          {
+             printf("sorted ");
+             switch(sort){
+                  case SORT_VR:
+                     printf("Value,ratio(V/W)");
+                     break;
+                  case SORT_WR:
+                     printf("Weight,ratio(V/W)");
+                     break;
+                  case SORT_RW:
+                     printf("ratio(V/W),Weight");
+                     break;
+                  case SORT_RV:
+                     printf("ratio(V/W),Value");
+                     break;
+                  default:
+                     break;
+             }
+            if (sort_order == ASC)
+              printf(" asc\n");
+            else
+              printf(" desc\n");
+          }
+        item = solver.items;
+        printf("     index    Value   Weight\n");
+        for (i = 0; i < solver.n; i++, item++)
+          printf("  % 8d % 8d % 8d\n", item->i, item->v, item->w);
+     }
+
+   clock_gettime(CLOCK_MONOTONIC, &t0);
+   solve(&solver);
+   clock_gettime(CLOCK_MONOTONIC, &t1);
+   ret = print(&solver);
+
+   if (debug > 0)
+     {
+        dt = ((t1.tv_sec * 1000000000) + t1.tv_nsec) -
+           ((t0.tv_sec * 1000000000) + t0.tv_nsec);
+        printf(" time %7u [ms]\n", (unsigned int)(dt/1000000));
+     }
+
+   free(solver.items);
+   free(solver.column);
+
+   return ret;
+}
+
diff --git a/02-graph-coloring/CP-solver.rb b/02-graph-coloring/CP-solver.rb
new file mode 100755
index 0000000..c157c07
--- /dev/null
+++ b/02-graph-coloring/CP-solver.rb
@@ -0,0 +1,229 @@
+#! /usr/bin/ruby
+
+class Node
+   #
+   def initialize i, a
+      @i = i      # index
+      @a = [a]    # adjacents
+      @c = nil    # colour
+      @f = 0      # finished adjacents
+      @l = nil
+   end
+   #
+   attr_reader :i, :a
+   attr_accessor :c, :f
+   #
+   def add a
+      @a << a
+   end
+   #
+   def to_s
+      "#{@i} #{@c.to_s} " + @a.to_s
+   end
+   #
+   def l
+      return @l if not @l.nil?
+      @l = @a.length
+   end
+   #
+   def blocked?
+      (l == @f)
+   end
+   #
+end
+
+class Step
+   #
+   def initialize n, c
+      @n = n   # nodes
+      @c = c   # max color
+      @k = nil # current
+      @f = []  # failed
+      @p = n.select { |n| n.c.nil? } # possible
+      # puts @p.inspect
+      # @p[0].c = 666
+      # puts @p[0].to_s
+   end
+   attr_reader :c, :n
+   def done?
+      @p.empty?
+   end
+   #
+   def sort ar
+      ar.sort { |a,b|
+         r = b.l <=> a.l
+         if r == 0
+            b.f <=> a.f
+         else
+            r
+         end
+      }
+   end
+   #
+   def chose_node
+      b = @p.select { |n| n.blocked? }
+      if not b.empty?
+         return sort(b).shift
+      end
+      sort(@p).shift
+   end
+   #
+   def test c
+      @k.a.each do |i|
+         if @n[i].c == c
+            return false
+         end
+      end
+      true
+   end
+   #
+   def set_color c
+      @k.c = c
+      @k.a.each do |i|
+         @n[i].f += 1
+      end
+   end
+   #
+   def try
+      while not @p.empty?
+         if @k.nil?
+            @k = chose_node
+            @p.delete @k
+         end
+         # puts "try #{@k.to_s}"
+         co = nil
+         cs = (@k.c.nil? ? 0 : @k.c )
+         (cs..@c).each do |c|
+            if test c
+               co = c
+               break
+            end
+         end
+         if co.nil?
+            @f << @k
+            @k = nil
+         else
+            set_color co
+            break
+         end
+      end
+      # @n.each do |n| puts n.inspect end
+      # puts @k.inspect
+      # puts 'OK'
+      true
+   end
+   #
+   def next
+      # TODO @k might be nil !!
+      Step.new(@n.inject([]) {|a,n| a << n.clone}, ( (@k.c < @c) ? @c: @c+1))
+   end
+   #
+end
+
+class Graph
+   #
+   def initialize p, n, e
+      @path = p
+      @n = n
+      @e = e
+      @nodes = {}
+      @edges = []
+      @steps = []
+      @c = 0
+   end
+   #
+   def add e
+      @edges << e
+
+      a, b = *e
+      a = a.to_i
+      b = b.to_i
+
+      n = @nodes[a]
+      if n.nil?
+         @nodes[a] = Node.new a, b
+      else
+         n.add b
+      end
+
+      n = @nodes[b.to_i]
+      if n.nil?
+         @nodes[b] = Node.new b, a
+      else
+         n.add a
+      end
+   end
+   #
+   def solve
+      s = Step.new(@nodes.values.inject([]) {|a,n| a << n.clone}, @c)
+      @steps << s
+      while true
+         if @steps.empty?
+            puts 'unsolvable'
+            return
+         end
+         if @steps[-1].try
+            @steps << @steps[-1].next
+            if @steps[-1].done?
+               puts 'success'
+               return
+            end
+         else
+            @steps.pop
+         end
+      end
+   end
+   #
+   def to_s
+      r = "#{@p}: N:#{@n} E:#{@e}\n"
+      @nodes.sort_by { |k,v| k } .each do |k,v|
+         r += " #{v.to_s}\n"
+      end
+      r
+   end
+   #
+   def draw
+      puts "colors : #{@steps[-1].c}"
+      require 'paleta'
+      color = Paleta::Color.new(:hex, "0000ff")
+      colors = Paleta::Palette.generate(:type => :complementary, :from => :color, :color => color, :size => @steps[-1].c).to_array(:rgb)
+      df = @path+'.dot'
+      pf = @path+'.png'
+      open(df,'w') do |f|
+         f << "graph {\n"
+         f << "node [style=filled];\n"
+         @steps[-1].n.each do |n|
+            f << " #{n.i} [color=\"#{"#%02X%02X%02X" % colors[n.c]}\"]\n"
+         end
+         @edges.each do |a,b|
+            f << " #{a} -- #{b}\n"
+         end
+         f << "}\n"
+      end
+      system "dot -Tpng -o '#{pf}' '#{df}'"
+   end
+   #
+end
+
+def read_graph path
+   puts "read #{path}…"
+   g = nil
+   open(path).read.each_line do |line|
+      if g.nil?
+         g = Graph.new path, *line.split
+         next
+      end
+      g.add line.split
+   end
+   puts "done."
+   g
+end
+
+ARGV.each do |path|
+
+   g = read_graph path
+   g.solve
+   puts g
+   g.draw
+end
+
diff --git a/02-graph-coloring/README b/02-graph-coloring/README
new file mode 100644
index 0000000..76ff5f0
--- /dev/null
+++ b/02-graph-coloring/README
@@ -0,0 +1,15 @@
+
+break symetries (colours are interchangeable);
+   - max colour + 1
+
+try first where you fail:
+   - nodes with bigger degree && less possible colour
+
+think about distinct graphs:
+   - ??
+
+a step is:
+   - possible nodes
+   - failed nodes
+   - chosen node
+
diff --git a/02-graph-coloring/data/gc_4_1.dot b/02-graph-coloring/data/gc_4_1.dot
new file mode 100644
index 0000000..32b343b
--- /dev/null
+++ b/02-graph-coloring/data/gc_4_1.dot
@@ -0,0 +1,10 @@
+graph {
+node [style=filled];
+ 0 [color="#FFFF00"]
+ 1 [color="#0000FF"]
+ 2 [color="#FFFF00"]
+ 3 [color="#FFFF00"]
+ 0 -- 1
+ 1 -- 2
+ 1 -- 3
+}
diff --git a/02-graph-coloring/data/gc_4_1.png b/02-graph-coloring/data/gc_4_1.png
new file mode 100644
index 0000000..b783995
--- /dev/null
+++ b/02-graph-coloring/data/gc_4_1.png
diff --git a/02-graph-coloring/draw b/02-graph-coloring/draw
new file mode 100755
index 0000000..656c60b
--- /dev/null
+++ b/02-graph-coloring/draw
@@ -0,0 +1,7 @@
+#! /bin/bash
+
+for data in ./data/*; do
+   echo "draw $data …"
+   cat $data | sed -e '1agraph G {' -e '1d; s/ / -- /; s/$/;/' -e '$a}' | dot -Tpng -o ${data}.png
+done
+
diff --git a/02-graph-coloring/gc_20_1.png b/02-graph-coloring/gc_20_1.png
new file mode 100644
index 0000000..20eac27
--- /dev/null
+++ b/02-graph-coloring/gc_20_1.png