Copyright: Rulez by Peter Luschny
is licensed under aCreative Commons Attribution-Noncommercial-Share Alike 3.0 License.
Please report bugs and comments to: peter (at) luschny (point) de.
1: package de.luschny.math.ruler;
2:
3: import java.io.*;
4: import java.util.*;
5:
6: // Driver class for the generation of perfect rulers.
7:
8: public class Ruler {
9:
10: static String[] help =
11: {
12: " PURPOSE OF THE PROGRAM",
13: " Generating all perfect or optimal rulers of given length.",
14: "",
15: " A ruler with length L is 'perfect' if",
16: " (a) the ruler is complete, i.e. all distances d with",
17: " 1 <= d <= L can be measured with the ruler and",
18: " (b) there is no complete ruler with the same length which",
19: " possesses fewer marks. If, in addition,",
20: " (c) there is no complete ruler with the same number of marks",
21: " which has a greater length, then the ruler is 'optimal'.",
22: "",
23: " SYNTAX: \"function(from, to, options)\" ",
24: " (Like a function call with three arguments.)",
25: "",
26: " function is one out of { perfect, optimal, single }",
27: "",
28: " perfect -> generate all perfect rulers with length L",
29: " constrained by 1 <= from <= L <= to ",
30: " single -> generate only one perfect ruler with length L",
31: " constrained by 1 <= from <= L <= to ",
32: " optimal -> generate all optimal rulers with S segments",
33: " constrained by 1 <= from <= S <= to ",
34: "",
35: " 'options' are any substrings of \"cmdbtf\".",
36: "",
37: " c : count rulers only, don't print them",
38: " for example: Rulers(8,23), Number of rulers: 4",
39: " m : generate and print the marker-representation",
40: " for example: [0,1,4,10,16,18,21,23]",
41: " d : generate and print the difference representation",
42: " for example: <1,3,6,6,2,3,2>",
43: " b : generate and print the binary representation",
44: " for example ||--|-----|-----|-|--|-|",
45: " t : generate and print the type of the ruler",
46: " for example |1^3|2^3|3^3|7^3|14^3|21^3|",
47: " f : generate and print the difference-triangle",
48: "",
49: " All the above options can be combined in a single string.",
50: " The option 'c' overrides all other options.",
51: "",
52: " EXAMPLE USAGE: perfect(23,44,mdb), single(1,80,b)",
53: " optimal(1,20,c), optimal(12,12,mdbtf)",
54: "",
55: " **********************************************************",
56: " Note: If two different rulers are mirror-symmetric both",
57: " will be counted, but only one will be represented.",
58: " For example: [0,1,3] is mirror-symmetric to [0,2,3].",
59: " ***********************************************************",
60: "",
61: " File: Rulers will be saved to the file 'rulers.txt'.",
62: " Info: http://www.luschny.de/math/rulers/index.html"
63: };
64:
65: public static void main(String[] args)
66: {
67: String fileName = "ruler.txt";
68:
69: if(args.length == 1) run(args[0], fileName);
70: else run("noparam", fileName);
71:
72: // ----------------------------------
73: // Some test cases.
74: // Uncomment one line in the next paragraph
75: // ----------------------------------
76: // run("perfect(0,50,d)", fileName);
77: // run("perfect(1,23,mb)", fileName);
78: // run("single(1,80,b)", fileName);
79: // run("optimal(1,16,bd)", fileName);
80: // run("optimal(12,12,mdbtf)", fileName);
81: // ------------------------------------
82: }
83:
84: static void run(String arg, String fileName)
85: {
86: Rulez ruler;
87: boolean validParams = ! arg.equalsIgnoreCase("noparam");
88:
89: if(validParams)
90: {
91: System.out.println("FunctionCall: " + arg);
92: ruler = new Rulez(fileName);
93: validParams = ruler.compute(arg);
94: }
95:
96: if(! validParams)
97: {
98: System.out.println(" *** Missing or invalid arguments ***");
99: System.out.println();
100: for (int i = 0; i < help.length; i++)
101: System.out.println(help[i]);
102: return;
103: }
104:
105: System.out.println("Saved to file: " + fileName);
106: }
107: }
108:
109: class Rulez
110: {
111: static int[] optIndex = new int[]
112: {
113: 1, 1, 3, 6, 9, 13, 17, 23, 29, 36, 43, 50,
114: 58, 68, 79, 90, 101, 112, 123
115: };
116:
117: static int[] lenToSegment = new int[]
118: {
119: 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6,
120: 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9,
121: 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10,
122: 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12,
123: 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13,
124: 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
125: 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
126: 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17,
127: 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
128: 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19,
129: 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19
130: };
131:
132: // ENUM OPTION
133: static final int countOnly = 0, singleOnly = 1, markerRep = 2,
134: diffRep = 3, symbolicRep = 4, tableRep = 5, typeRep = 6;
135:
136: static boolean[] option =
137: {
138: false, false, false, false, false, false, false
139: };
140:
141: // ENUM FUNCTION
142: static int function, From, To;
143: static final int perfect = 0;
144: static final int optimal = 1;
145: static final int single = 2;
146: static String[] functionName =
147: {
148: "perfect", "optimal", "single"
149: };
150:
151: PerfectRuler generator;
152: StopWatch watch, mwatch, mainWatch;
153: PrintWriter rulerReport;
154:
155: static boolean validArgs(String args)
156: {
157: args = args.replace('(', ',');
158: args = args.replace(')', ',');
159:
160: Scanner sc = new Scanner(args).useDelimiter(",");
161:
162: try
163: {
164: String fun = sc.next();
165: int inFrom = sc.nextInt();
166: int inTo = sc.nextInt();
167: String opt = sc.next();
168: sc.close();
169:
170: if (fun.equalsIgnoreCase(functionName[perfect]))
171: {
172: function = perfect;
173: }
174: else if (fun.equalsIgnoreCase(functionName[optimal]))
175: {
176: function = optimal;
177: }
178: else if (fun.equalsIgnoreCase(functionName[single]))
179: {
180: function = single;
181: }
182: else
183: {
184: throw new IllegalArgumentException("Function name invalid!");
185: }
186:
187: option[countOnly] = opt.contains("c");
188: if (!option[countOnly])
189: {
190: boolean optset = false;
191: optset |= option[markerRep] = opt.contains("m");
192: optset |= option[diffRep] = opt.contains("d");
193: optset |= option[symbolicRep] = opt.contains("b");
194: optset |= option[typeRep] = opt.contains("t");
195: optset |= option[tableRep] = opt.contains("f");
196:
197: if (!optset)
198: {
199: throw new IllegalArgumentException("Options missing!");
200: }
201: }
202: option[singleOnly] = function == single;
203:
204: int lmin = 1; // 999 is a pseudo max
205: int lmax = function == optimal ? 999
206: : (function == perfect ? 999 : 999);
207:
208: From = Math.min(Math.max(lmin, inFrom), lmax);
209: To = Math.max(lmin, Math.min(inTo, lmax));
210: }
211: catch (Exception e)
212: {
213: System.out.println(e.toString());
214: return false;
215: }
216:
217: return true;
218: }
219:
220: public Rulez(String fileName)
221: {
222: mainWatch = new StopWatch();
223: watch = new StopWatch();
224: mwatch = new StopWatch();
225:
226: try
227: {
228: rulerReport =
229: new PrintWriter(
230: new BufferedWriter(
231: new FileWriter(fileName, true)));
232: }
233: catch (IOException e)
234: {
235: System.err.println(e.toString());
236: return;
237: }
238:
239: generator = new PerfectRuler(rulerReport, option);
240: }
241:
242: public boolean compute(String args)
243: {
244: if(! validArgs(args)) return false;
245:
246: System.out.println("Computing " + functionName[function] +
247: " rulers from " + From + " to " + To +".");
248:
249: mainWatch.start();
250: int count = handler(function, From, To, option);
251: mainWatch.stop();
252:
253: System.out.println(count + " rulers");
254:
255: if (!option[countOnly])
256: {
257: System.out.println("Generated in " + mainWatch.toString());
258: }
259:
260: rulerReport.flush();
261: return true;
262: }
263:
264: int handler(int fun, int from, int to, boolean[] options)
265: {
266: int allcount = 0,
267: markcount = 0,
268: segment = lenToSegment[from];
269:
270: for (int i = from; i <= to; i++)
271: {
272: int S = fun == optimal ? i : lenToSegment[i];
273: int L = fun == optimal ? optIndex[i] : i;
274:
275: if (segment != S && fun != optimal)
276: {
277: mwatch.stop();
278: System.out.print("* S=" + segment + " -> " +markcount);
279: System.out.println(" in " + mwatch.toString());
280: mwatch.restart();
281:
282: markcount = 0;
283: segment = S;
284: }
285:
286: watch.restart();
287: int count = generator.ruler(S + 1, L);
288: watch.stop();
289:
290: allcount += count;
291: markcount += count;
292:
293: System.out.print("(" + S + "," + L + ") -> " + count);
294: System.out.println(" in " + watch.toString());
295: }
296:
297: if (fun != optimal)
298: {
299: mwatch.stop();
300: System.out.print("* S=" + segment + " -> " + markcount);
301: System.out.println(" in " + mwatch.toString());
302: }
303:
304: return allcount;
305: }
306: }
307:
308: //////////////////////////////////////////////////////
309:
310: class PerfectRuler {
311:
312: // The number of perfect rulers with lenght 1<=L<=123
313: private static int[] perfCount = {
314: 1, 1, 1, 2, 3, 4, 2, 12, 8, 4,
315: 38, 30, 14, 6, 130, 80, 32, 12,500, 326,
316: 150, 66, 18, 4, 944, 460,166, 56, 12, 6,
317: 2036, 890, 304, 120, 20, 10, 2,2678,974, 362,
318: 100, 36, 4, 2,4892,2114,684, 238, 68, 22,
319: 4,16318,6350,2286, 836, 330,108, 24, 12,31980,
320: 12252, 4960,1806, 668, 238, 86, 6, 12, 4,15558,
321: 5906, 2558, 850, 388, 120, 38, 4, 6, 4, 2,
322: 4972, 2234, 798, 332, 106, 48, 4, 6, 2, 2,
323: 2, 3392,1262, 626, 212, 76, 40, 16, 2, 2,
324: 2, 2,3426,1506, 682, 360,138, 70, 28, 8,
325: 2, 2, 2,6578,2984,1458,586, 374, 192, 98,
326: 38, 14, 4, 4
327: };
328:
329: private PrintWriter file;
330: private int[][] rulers;
331: private int[] r;
332: private int L1, count, maxCount, perCount;
333: private boolean[] option;
334:
335: public PerfectRuler(PrintWriter report, boolean[] opt)
336: {
337: file = report;
338: option = opt;
339: rulers = new int [16000][];
340: }
341:
342: public int ruler (int M, int L)
343: {
344: perCount = L < perfCount.length ? perfCount[L] : 32000;
345: maxCount = option[Rulez.singleOnly] ? 1 : perCount;
346:
347: if (option[Rulez.countOnly])
348: {
349: file.println("Number of rulers(" + (M-1) + "," + L
350: + ") = " + maxCount);
351: return maxCount;
352: }
353:
354: maxCount = (maxCount + (maxCount | 1)) >> 1;
355:
356: int S = (M * (M - 1)) / 2;
357: L1 = L + 1;
358:
359: r = new int [M + 1];
360:
361: int[] R = new int [S + 1];
362: int[] K = new int [M + 2];
363:
364: K [2] = L; K [3] = 1;
365: R [1] = 1; R [L] = 1; R [L - 1] = 1;
366:
367: file.println();
368: file.println("Rulers(" + (M-1) + "," + L + ") List of rulers:");
369: file.println();
370: count = 0;
371:
372: try
373: {
374: generator(M, L, K, R, 3, S, 1, false);
375: }
376: catch (java.util.NoSuchElementException e)
377: { // --- do not handle: this is an early-out
378: }
379:
380: if (option[Rulez.singleOnly])
381: {
382: count = 1;
383: }
384: else
385: {
386: count = L < perfCount.length ? perCount : 2 * count;
387: file.print("Rulers(" + (M-1) + "," + L + ") ");
388: file.println("Number of rulers: " + count);
389: }
390:
391: file.flush();
392:
393: return count;
394: }
395:
396: private void generator(int M, int L, int[] K, int[] R,
397: int i, int S, int w, boolean b)
398: {
399: if (i < M)
400: {
401: int k = w;
402:
403: while (R [L - k] > 0)
404: {
405: k++;
406: }
407:
408: int t = L - M + i + 1;
409:
410: if ((t & 1) == 1)
411: {
412: t++;
413: }
414:
415: t >>= 1;
416: if (t < k) k = t;
417:
418: while (k > w)
419: {
420: expander(M, L, K, R, i + 1, S, k, true);
421: expander(M, L, K, R, i + 1, S, k, false);
422: k--;
423: }
424:
425: if (! b)
426: {
427: expander(M, L, K, R, i + 1, S, w, true);
428: }
429: }
430: else
431: {
432: checker(M, K);
433: }
434: }
435:
436: private void expander(int M, int L, int[] K, int[] R,
437: int i, int S, int w, boolean b)
438: {
439: int ka = b ? L - w : w;
440:
441: K [i] = ka;
442:
443: for (int j = 1; j < i; j++)
444: {
445: int len = ka - K [j];
446:
447: if (len < 0)
448: {
449: len = -len;
450: }
451:
452: if (R [len] > 0)
453: {
454: S--;
455: }
456:
457: R [len]++;
458: }
459:
460: if (S >= L)
461: {
462: generator(M, L, K, R, i, S, w, b);
463: }
464:
465: for (int j = 1; j < i; j++)
466: {
467: int len = ka - K [j];
468:
469: if (len < 0)
470: {
471: len = -len;
472: }
473:
474: R [len]--;
475: }
476: }
477:
478: private void checker (int M, int[] K)
479: {
480: int[] a = r;
481:
482: a [1] = K [1];
483: a [M] = K [2];
484:
485: int i, k;
486:
487: for (i = 3; i <= M; i++)
488: {
489: int j = i - 1;
490:
491: while (K [i] < a [j - 1])
492: {
493: a [j] = a [j - 1];
494: j--;
495: }
496:
497: a [j] = K [i];
498: }
499:
500: int[] rul = new int [M - 1];
501:
502: for (k = 1; k < M; k++)
503: {
504: int d = a [k + 1] - a [k];
505: if (d <= 0) return;
506:
507: rul [k - 1] = d;
508: }
509:
510: // equivalent by reflection: choose the smaller ruler
511: int M2 = M - 2;
512:
513: for (k = 0; k < (M - 1); k++)
514: {
515: if (rul [k] < rul [M2 - k])
516: {
517: break;
518: }
519: else
520: {
521: if (rul [k] != rul [M2 - k])
522: {
523: for (int j = (M2 - 1) >> 1; j >= 0; --j)
524: {
525: int temp = rul [j];
526: rul [j] = rul [M2 - j];
527: rul [M2 - j] = temp;
528: }
529: break;
530: }
531: }
532: }
533:
534: for (i = count - 1; i >= 0; i--)
535: {
536: int[] rulI = rulers [i];
537: k = M2;
538:
539: while ((k >= 0) && (rul [k] == rulI [k]))
540: {
541: k--;
542: }
543:
544: if (k < 0) // ruler already found
545: {
546: return;
547: }
548: }
549:
550: // If we reach this point, we have found a new ruler!
551: // -- begin 'visit'
552:
553: rulers [count++] = rul;
554: printer(a);
555:
556: // -- end 'visit'
557:
558: if (maxCount <= count)
559: {
560: // done, early exit
561: throw new java.util.NoSuchElementException();
562: }
563: }
564:
565: //////////////// print - functions //////////////////////
566:
567: private void printer(final int[] a)
568: {
569: int nop = 0;
570: if (option[Rulez.countOnly])
571: {
572: return;
573: }
574: if (option[Rulez.symbolicRep])
575: {
576: nop++;
577: printSymbolic(a);
578: }
579: if (option[Rulez.markerRep])
580: {
581: nop++;
582: printRuler(a);
583: }
584: if (option[Rulez.diffRep])
585: {
586: nop++;
587: printDiffRepresentation(a);
588: }
589: if (option[Rulez.typeRep])
590: {
591: nop++;
592: printTypeOf(a);
593: }
594: if (option[Rulez.tableRep])
595: {
596: nop++;
597: printDiffTable(a);
598: }
599: if (nop > 1)
600: {
601: file.println();
602: }
603: }
604:
605: private void printRuler(final int[] a)
606: {
607: file.print("[0");
608:
609: for (int i = 2; i < a.length; i++)
610: {
611: file.print(",");
612: file.print(a[i]);
613: }
614:
615: file.println("]");
616: }
617:
618: private void printSymbolic(final int[] a)
619: {
620: StringBuilder sr = new StringBuilder(L1);
621: int l = 0;
622:
623: for (int i = 1; i < a.length; i++)
624: {
625: while (l++ < a[i])
626: {
627: sr.append('-');
628: }
629: sr.append('|');
630: }
631: file.println(sr.toString());
632: }
633:
634: private void printDiffRepresentation(final int[] a)
635: {
636: file.print("<" + (a[2] - a[1]));
637:
638: for (int i = 2; i < a.length - 1; i++)
639: {
640: int w = a[i + 1] - a[i];
641: file.print(",");
642: file.print(w);
643: }
644:
645: file.println(">");
646: }
647:
648: private void printDiffTable(final int[] a)
649: {
650: for (int i = a.length - 1; i > 0; i--)
651: {
652: for (int j = 1; j < i; j++)
653: {
654: int w = a[i] - a[i - j];
655: file.print(w);
656: file.print(",");
657: }
658:
659: file.println();
660: }
661: }
662:
663: private int[] typeOf(final int[] a)
664: {
665: int[] t = new int[L1];
666:
667: for (int i = a.length - 1; i > 0; i--)
668: {
669: for (int j = 1; j < i; j++)
670: {
671: int d = a[i] - a[i - j];
672: t[d] = t[d] + 1;
673: }
674: }
675: return t;
676: }
677:
678: private void printTypeOf(final int[] a)
679: {
680: int[] t = typeOf(a);
681:
682: file.print("|");
683:
684: if (t.length < 8)
685: {
686: for (int i = 1; i < t.length; i++)
687: {
688: file.print(i + "^" + t[i] + "|");
689: }
690: }
691: else
692: {
693: for (int i = 1; i < t.length; i++)
694: {
695: if (t[i] > 1)
696: {
697: file.print(i + "^" + t[i] + "|");
698: }
699: }
700: }
701: file.println();
702: }
703: }
704:
705: /**
706: * StopWatch
707: *
708: * @author Peter Luschny
709: * @version 2001-05-12
710: */
711: class StopWatch
712: {
713: private long elapsedCount = 0;
714: private long startCount = 0;
715:
716: /**
717: * Start the time-counter.
718: *
719: */
720: public void start()
721: {
722: startCount = System.currentTimeMillis();
723: }
724:
725: public void restart()
726: {
727: elapsedCount = 0;
728: startCount = System.currentTimeMillis();
729: }
730:
731: /**
732: * Stop the time-counter
733: *
734: */
735: public void stop()
736: {
737: long stopCount = System.currentTimeMillis();
738: elapsedCount += (stopCount - startCount);
739: }
740:
741: /**
742: * Clear the elapsed time-counter.
743: *
744: */
745: public void clear()
746: {
747: elapsedCount = 0;
748: }
749:
750: /**
751: * Get the elapsed time converted to seconds.
752: *
753: */
754: public double getSeconds()
755: {
756: return elapsedCount / 1000.0;
757: }
758:
759: /**
760: * Get the elapsed time as a formatted string.
761: *
762: */
763: @Override
764: public String toString()
765: {
766: return getSeconds() + " sec.";
767: }
768: }
Copyright: Rulez by Peter Luschny
is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 License.
Please report bugs and comments to: peter (at) luschny (point) de.