From 6aa197555af030c2e1390b1f91d24ae23538cf43 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Tue, 2 Oct 2007 22:11:08 +0200
Subject: [PATCH] Lustitko.

---
 morse.c | 185 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 185 insertions(+)
 create mode 100644 morse.c

diff --git a/morse.c b/morse.c
new file mode 100644
index 0000000..50f957b
--- /dev/null
+++ b/morse.c
@@ -0,0 +1,185 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <ctype.h>
+
+#define MAXLEN 256
+
+static unsigned char decode[] = "**etianmsurwdkgohvf*l*p*bxcyzq*";
+static unsigned char encode[256];
+
+static void init(void)
+{
+  for (unsigned i=2; i<sizeof(decode); i++)
+    {
+      int x = i;
+      int y = 1;
+      while (x > 1)
+	{
+	  y = 2*y + x%2;
+	  x /= 2;
+	}
+      encode[decode[i]] = y;
+      encode[toupper(decode[i])] = y;
+    }
+}
+
+static void strencode(unsigned char *dest, unsigned char *src, int spaces)
+{
+  while (*src)
+    {
+      int c = encode[*src++];
+      if (c <= 0)
+	*dest++ = '?';
+      else while (c > 1)
+	{
+	  *dest++ = ".-"[c%2];
+	  c /= 2;
+	}
+      if (spaces && *src)
+	*dest++ = '/';
+    }
+  *dest = 0;
+}
+
+static void strdecode(unsigned char *dest, unsigned char *src)
+{
+  while (*src)
+    {
+      if (*src != '.' && *src != '-')
+	{
+	  src++;
+	  continue;
+	}
+      int c = 1;
+      while (*src == '.' || *src == '-')
+	c = 2*c + (*src++ == '-');
+      *dest++ = decode[c];
+    }
+  *dest = 0;
+}
+
+struct w {
+  struct w *next;
+  char c[1];
+};
+
+struct t {
+  struct t *son[2];
+  struct w *words;
+};
+
+static struct t root;
+
+static void die(char *msg)
+{
+  fprintf(stderr, "%s\n", msg);
+  exit(1);
+}
+
+static void *xmalloc(unsigned int s)
+{
+  void *d = malloc(s);
+  if (!d)
+    die("Out of memory. All memory.");
+  return d;
+}
+
+static void load(char *name)
+{
+  FILE *fi = fopen(name, "r");
+  if (!fi)
+    die("Cannot open dictionary");
+  char buf[256], m[256];
+  int cnt = 0;
+  int treesize = 1;
+  while (fgets(buf, sizeof(buf), fi))
+    {
+      char *c = strchr(buf, '\n');
+      if (c)
+	*c = 0;
+      strencode(m, buf, 0);
+      struct t *t = &root;
+      for (c=m; *c; c++)
+	{
+	  int i = (*c == '-');
+	  if (!t->son[i])
+	    {
+	      t->son[i] = xmalloc(sizeof(struct t));
+	      memset(t->son[i], 0, sizeof(struct t));
+	      treesize++;
+	    }
+	  t = t->son[i];
+	}
+      struct w *w = xmalloc(sizeof(*w) + strlen(buf));
+      w->next = t->words;
+      t->words = w;
+      strcpy(w->c, buf);
+      cnt++;
+    }
+  fclose(fi);
+  printf("Loaded %d words, built %d nodes\n", cnt, treesize);
+}
+
+static char M[MAXLEN+1][MAXLEN+1];	/* M[i][j]==1 if it's possible to cover in[i...N-1] with exactly j words */
+
+static void map(char *in, int N)
+{
+  M[N][0] = 1;
+  for (int i=N-1; i>=0; i--)
+    {
+      struct t *t = &root;
+      int j = i;
+      while (t && j < N)
+	{
+	  t = t->son[in[j++] == '-'];
+	  if (t && t->words)
+	    for (int k=0; k<N; k++)
+	      if (M[j][k])
+		M[i][k+1] = 1;
+	}
+    }
+}
+
+static void print(char *buf, char *p, char *in, int i, int N, int j)	/* cover in[i...N-1] with exactly j words */
+{
+  if (i >= N)
+    {
+      *p = 0;
+      puts(buf);
+      return;
+    }
+
+  struct t *t = &root;
+  *p++ = ' ';
+  while (t && i < N)
+    {
+      t = t->son[in[i++] == '-'];
+      if (t && t->words && M[i][j-1])
+	for (struct w *w = t->words; w; w=w->next)
+	  {
+	    int l = strlen(w->c);
+	    memcpy(p, w->c, l);
+	    print(buf, p+l, in, i, N, j-1);
+	  }
+    }
+}
+
+int main(int argc, char **argv)
+{
+  if (argc != 3)
+    die("Usage: morse <dict> <string>");
+  init();
+  load(argv[1]);
+  int N = strlen(argv[2]);
+  if (N > MAXLEN)
+    die("Oops, too long for my memory!");
+  map(argv[2], N);
+
+  char buf[MAXLEN+1];
+  for (int j=1; j<=N; j++)
+    if (M[0][j])
+      print(buf+1, buf, argv[2], 0, N, j);
+
+  return 0;
+}
-- 
2.39.2