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:  }

Creative Commons License   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.