clusters: A really bad 1D clustering program.

The idea is to help with guessing expected track lengths.

diff --git a/clusters b/clusters
new file mode 100755 (executable)
index 0000000..f3b20aa
--- /dev/null
+++ b/clusters
@@ -0,0 +1,59 @@
+#! /usr/bin/python3
+
+import math as M
+import sys as SYS
+
+data = []
+for line in SYS.stdin: data.append(float(line))
+data.sort()
+data = [data]
+
+def cover(lo, hi):
+  mid = (lo + hi)/2
+  return mid, 1.0 - lo/mid
+
+def metric(vv):
+  print(";; measuring...")
+  tot = 0
+  for v in vv:
+    spread = M.pow(v[-1] - v[0], 0.5)
+    print(";;\t%g .. %g -> %g" % (v[0], v[-1], spread))
+    tot += spread
+  return tot
+
+def largest_gap(vv):
+  #print(";; finding gap...")
+  best, bestwd = None, None
+  for i, v in enumerate(vv):
+    lo = v[0]
+    for j in range(1, len(v)):
+      hi = v[j]
+      _, spread = cover(lo, hi)
+      #print(";;\t%d/%d: %g .. %g -> %g" % (i, j, lo, hi, spread))
+      if bestwd is None or spread > bestwd:
+        best, bestwd = (i, j), spread
+      lo = hi
+  #if best is None: print(";; already atomized")
+  #else: print(";; best gap %d/%d; %g" % (best[0], best[1], bestwd))
+  return best
+
+lastmetric = metric(data)
+while True:
+  best = largest_gap(data)
+  if best is None: break
+  i, j = best
+  newdata = data[:i] + [data[i][:j], data[i][j:]] + data[i + 1:]
+  newmetric = metric(newdata)
+  if newmetric > lastmetric: break
+  lastmetric, data = newmetric, newdata
+
+def format_duration(t):
+  f, t = M.modf(t)
+  frac = ("%g" % f)[1:]
+  if t >= 3600: return "%d:%02d:%02d%s" % (t//3600, (t//60)%60, t%60, frac)
+  elif t >= 60: return "%d:%02d%s" % (t//60, t%60, frac)
+  else: return "%d%s s" % (t, frac)
+
+for v in data:
+  mid, spread = cover(v[0], v[-1])
+  print("%s ± %g%%" % (format_duration(mid), 100.0*spread))