ucw/songsack.c

   1 /* A knapsack full of songs */
   2
   3 #undef LOCAL_DEBUG
   4
   5 #include <ucw/lib.h>
   6 #include <ucw/fastbuf.h>
   7 #include <ucw/mempool.h>
   8 #include <ucw/gary.h>
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <time.h>
  12 #include <unistd.h>
  13
  14 struct song {
  15   char *name;
  16   int duration;
  17 };
  18
  19 static struct song *songs;
  20 static struct mempool *mp;
  21
  22 int main(int argc, char **argv)
  23 {
  24   if (argc != 2)
  25     die("Usage: songsack <minutes>");
  26   int goal = atoi(argv[1]) * 60;
  27   int size = goal + 61;
  28
  29   GARY_INIT(songs, 0);
  30   mp = mp_new(65536);
  31
  32   struct fastbuf *f = bopen_fd(0, NULL);
  33   char line[1024];
  34   while (bgets(f, line, sizeof(line)))
  35     {
  36       char *c = strchr(line, ' ');
  37       if (!c)
  38         continue;
  39       *c++ = 0;
  40       int m, s;
  41       if (sscanf(line, "%d:%d", &m, &s) != 2)
  42         continue;
  43       int d = 60*m + s;
  44       if (d > size)
  45         continue;
  46       if (d < 60)       // Ignore bogus tracks
  47         continue;
  48
  49       DBG("<< %d <%s>", d, c);
  50       struct song *g = GARY_PUSH(songs, 1);
  51       g->name = mp_strdup(mp, c);
  52       g->duration = d;
  53     }
  54   bclose(f);
  55   int n = GARY_SIZE(songs);
  56   fprintf(stderr, "Considering %d songs\n", n);
  57
  58   srand(time(NULL) ^ getpid());
  59   for (int i=0; i<n; i++)
  60     {
  61       int j = i + random_max(n-i);
  62       struct song t = songs[i];
  63       songs[i] = songs[j];
  64       songs[j] = t;
  65     }
  66
  67   int *best = xmalloc_zero(size * sizeof(int));
  68   int *used = xmalloc_zero(size * sizeof(int));
  69   best[0] = 1;
  70   for (int i=0; i<n; i++)
  71     {
  72       int d = songs[i].duration;
  73       for (int j=size-1; j>=d; j--)
  74         if (!best[j] && best[j-d])
  75           {
  76             best[j] = 1;
  77             used[j] = i;
  78           }
  79     }
  80
  81   int opt=10*size, opti=-1;
  82   for (int i=size-1; i>=0; i--)
  83     if (best[i])
  84       {
  85         int score = (i > goal) ? 3*(i-goal) : goal-i;
  86         score += random_max(20) - 10;
  87         if (score < opt)
  88           opt = score, opti = i;
  89       }
  90   if (opti < 0)
  91     die("No solution");
  92
  93   fprintf(stderr, "Duration: %02d:%02d\n", opti/60, opti%60);
  94   while (opti)
  95     {
  96       int j = used[opti];
  97       int d = songs[j].duration;
  98       fprintf(stderr, "%02d:%02d %s\n", d/60, d%60, songs[j].name);
  99       printf("%s\n", songs[j].name);
 100       opti -= d;
 101     }
 102
 103   return 0;
 104 }