From b1adf14f542e7a48f0ac9cd92069d6930665a4bd Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sun, 10 Mar 2013 01:02:34 +0100
Subject: [PATCH] MPC knapsack solver

---
 ucw/Makefile   |   2 +-
 ucw/songsack.c | 104 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 105 insertions(+), 1 deletion(-)
 create mode 100644 ucw/songsack.c

diff --git a/ucw/Makefile b/ucw/Makefile
index b5b0684..a4145d5 100644
--- a/ucw/Makefile
+++ b/ucw/Makefile
@@ -7,7 +7,7 @@ LD=gcc
 CFLAGS=-O2 -Wall -W -Wno-parentheses -Wstrict-prototypes -Wmissing-prototypes -Wundef -Wredundant-decls -std=gnu99 $(UCWCF) -ggdb
 LDLIBS+=$(UCWLF)
 
-all: fit digit
+all: songsack
 
 clean:
 	rm -f `find . -name "*~" -or -name "*.[oa]" -or -name "\#*\#" -or -name TAGS -or -name core -or -name .depend -or -name .#*`
diff --git a/ucw/songsack.c b/ucw/songsack.c
new file mode 100644
index 0000000..42e55a7
--- /dev/null
+++ b/ucw/songsack.c
@@ -0,0 +1,104 @@
+/* A knapsack full of songs */
+
+#undef LOCAL_DEBUG
+
+#include <ucw/lib.h>
+#include <ucw/fastbuf.h>
+#include <ucw/mempool.h>
+#include <ucw/gary.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include <unistd.h>
+
+struct song {
+  char *name;
+  int duration;
+};
+
+static struct song *songs;
+static struct mempool *mp;
+
+int main(int argc, char **argv)
+{
+  if (argc != 2)
+    die("Usage: songsack <minutes>");
+  int goal = atoi(argv[1]) * 60;
+  int size = goal + 61;
+
+  GARY_INIT(songs, 0);
+  mp = mp_new(65536);
+
+  struct fastbuf *f = bopen_fd(0, NULL);
+  char line[1024];
+  while (bgets(f, line, sizeof(line)))
+    {
+      char *c = strchr(line, ' ');
+      if (!c)
+	continue;
+      *c++ = 0;
+      int m, s;
+      if (sscanf(line, "%d:%d", &m, &s) != 2)
+	continue;
+      int d = 60*m + s;
+      if (d > size)
+	continue;
+      if (d < 60)	// Ignore bogus tracks
+	continue;
+
+      DBG("<< %d <%s>", d, c);
+      struct song *g = GARY_PUSH(songs, 1);
+      g->name = mp_strdup(mp, c);
+      g->duration = d;
+    }
+  bclose(f);
+  int n = GARY_SIZE(songs);
+  fprintf(stderr, "Considering %d songs\n", n);
+
+  srand(time(NULL) ^ getpid());
+  for (int i=0; i<n; i++)
+    {
+      int j = i + random_max(n-i);
+      struct song t = songs[i];
+      songs[i] = songs[j];
+      songs[j] = t;
+    }
+
+  int *best = xmalloc_zero(size * sizeof(int));
+  int *used = xmalloc_zero(size * sizeof(int));
+  best[0] = 1;
+  for (int i=0; i<n; i++)
+    {
+      int d = songs[i].duration;
+      for (int j=size-1; j>=d; j--)
+	if (!best[j] && best[j-d])
+	  {
+	    best[j] = 1;
+	    used[j] = i;
+	  }
+    }
+
+  int opt=10*size, opti=-1;
+  for (int i=size-1; i>=0; i--)
+    if (best[i])
+      {
+	int score = (i > goal) ? 3*(i-goal) : goal-i;
+	score += random_max(20) - 10;
+	if (score < opt)
+	  opt = score, opti = i;
+      }
+  if (opti < 0)
+    die("No solution");
+
+  fprintf(stderr, "Duration: %02d:%02d\n", opti/60, opti%60);
+  while (opti)
+    {
+      int j = used[opti];
+      int d = songs[j].duration;
+      fprintf(stderr, "%02d:%02d %s\n", d/60, d%60, songs[j].name);
+      printf("%s\n", songs[j].name);
+      opti -= d;
+    }
+
+  return 0;
+}
-- 
2.39.2