Find Palindromes in Java


/** Palindromes, another nice program by Augustin Vidovic
Try it with the --help option to have a usage message. @author A. Vidovic @version 20031023-18
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
Alternatively, you may consult it on the web at */ import java.util.*; public class Palindromes { public static String OPT_RADIX="--radix"; public static String OPT_N="--N"; public static void printUsage() { System.out.println("Usage: Palindromes [options]"); System.out.println("\tThis program looks for palindromes and outputs them,\n\tthe number of palindromes of the same length,\n\tthe average distance between two palindromes of the same length.\nMore fun : you can adjust the radix and the maximum length (N)."); System.out.println("Options:"); System.out.println("\t--help\tDisplays this help message"); System.out.println("\t"+OPT_RADIX+" <n>\tradix (max "+MAX_RADIX+", default "+DEFAULT_RADIX+")"); System.out.println("\t"+OPT_N+" <n>\tmax number of digits (default "+DEFAULT_M+")"); System.out.println("\t--display-all\tTo output all results"); System.out.println("\t--display-recap\tTo output recapitulation only (default)"); System.out.println("\t--display-nothing\tTo suppress all output"); } public static void main(String[] args) throws Exception { int l=args.length; int radix=DEFAULT_RADIX; int n=DEFAULT_M; int display=DEFAULT_DISPLAY; for (int i=0; i<l; i++) { if (args[i].equals("--help")) { printUsage(); System.exit(0); } else if (args[i].equals(OPT_RADIX)) { int r=Integer.parseInt(args[i+1]); if (r>=2&&r<=MAX_RADIX) radix=r; } else if (args[i].equals(OPT_N)) { n=Integer.parseInt(args[i+1]); } else if (args[i].equals("--display-all")) { display=2; } else if (args[i].equals("--display-recap")) { display=1; } else if (args[i].equals("--display-nothing")) { display=0; } } Palindromes p=new Palindromes(); p.init(radix,n,display); p.start(); } public Palindromes() { } public static int DEFAULT_RADIX=10; public static int MAX_RADIX=36; public static int DEFAULT_M=9; public static int DEFAULT_DISPLAY=1; public static char[] digit = new char[] { '0','1','2','3','4','5','6','7','8','9', 'A','B','C','D','E','F','G','H','I','J', 'K','L','M','N','O','P','Q','R','S','T', 'U','V','W','X','Y','Z' }; public int radix; public int[] bench; public int m,n,display; public int[] nbPalindromes; public int[] avgDistance; public long[] totalDistance; public long[] lastPalindrome; public void init() { init(DEFAULT_RADIX,DEFAULT_M,DEFAULT_DISPLAY); } public void init(int radix,int n,int display) { this.radix=radix; bench=new int[n]; m=0; this.n=n; this.display=display; nbPalindromes=new int[n]; avgDistance=new int[n]; totalDistance=new long[n]; lastPalindrome=new long[n]; initStats(); if (display>0) System.out.println("Display mode "+display+", radix="+radix+", N="+n); } public void initStats() { int l=lastPalindrome.length; for (int i=0; i<l; i++) { totalDistance[i]=lastPalindrome[i]=-1; } } public String toString() { StringBuffer sb=new StringBuffer(); for (int i=m;i>=0;i--) { sb.append(digit[bench[i]]); } return sb.toString(); } public long longValue() { long l=0; int c=1; for (int i=0;i<n;i++) { l+=(long)(bench[i])*c; c*=radix; } return l; } public int incBench() { boolean r=true; int i=0; for (;i<n&&r;i++) { int x=bench[i]+=r?1:0; r=x>=radix; if (r) bench[i]-=radix; } i--; return r?-1:(i>m?i:m); } public boolean isPalindrome(){ boolean z=true; int l=m>>1; int j=m; for (int i=0; z&&i<=l; i++,j--) z=bench[i]==bench[j]; return z; } public void doPalindrome() { if (display>=2) System.out.println(this); long l=longValue(); long lp=lastPalindrome[m]; long t=totalDistance[m]; totalDistance[m]=(t>=0)?t+l-lp:0; lastPalindrome[m]=l; nbPalindromes[m]++; } public void doStats(boolean decorate,int p) { try { avgDistance[p]=(int)(totalDistance[p]/((long)nbPalindromes[p]-1)); } catch (ArithmeticException e) { } if (display>=2) System.out.println((decorate?"*** STATS : ":"\t")+"M="+(p+1)+"\tnb="+nbPalindromes[p]+"\tavg="+avgDistance[p]); } public void recapitulate() { System.out.println("========== Recapitulation ==========="); System.out.println("\tRadix="+radix+"\tN="+n); display=2; for (int i=0;i<n;i++) { doStats(false,i); } } public void start() { for (;m>=0;) { if (isPalindrome()) doPalindrome(); int p=m; m=incBench(); if (p<m||m<0) doStats(true,p); } if (display>=1) recapitulate(); } }

$ java Palindromes --help                        
Usage: Palindromes [options]
        This program looks for palindromes and outputs them,
        the number of palindromes of the same length,
        the average distance between two palindromes of the same length.
More fun : you can adjust the radix and the maximum length (N).
        --help  Displays this help message
        --radix <n>     radix (max 36, default 10)
        --N <n> max number of digits (default 9)
        --display-all   To output all results
        --display-recap To output recapitulation only (default)
        --display-nothing       To suppress all output

$ java Palindromes --radix 10 --N 9 --display-recap
Display mode 1, radix=10, N=9
========== Recapitulation ===========
        Radix=10        N=9
        M=1     nb=10   avg=1
        M=2     nb=9    avg=11
        M=3     nb=90   avg=10
        M=4     nb=90   avg=101
        M=5     nb=900  avg=100
        M=6     nb=900  avg=1001
        M=7     nb=9000 avg=1000
        M=8     nb=9000 avg=10001
        M=9     nb=90000        avg=10000

$ java Palindromes --radix 2 --N 16 --display-recap
Display mode 1, radix=2, N=16
========== Recapitulation ===========
        Radix=2 N=16
        M=1     nb=2    avg=1
        M=2     nb=1    avg=0
        M=3     nb=2    avg=2
        M=4     nb=2    avg=6
        M=5     nb=4    avg=4
        M=6     nb=4    avg=10
        M=7     nb=8    avg=8
        M=8     nb=8    avg=18
        M=9     nb=16   avg=16
        M=10    nb=16   avg=34
        M=11    nb=32   avg=32
        M=12    nb=32   avg=66
        M=13    nb=64   avg=64
        M=14    nb=64   avg=130
        M=15    nb=128  avg=128
        M=16    nb=128  avg=258

$ java Palindromes --radix 36 --N 6 --display-recap
Display mode 1, radix=36, N=6
========== Recapitulation ===========
        Radix=36        N=6
        M=1     nb=36   avg=1
        M=2     nb=35   avg=37
        M=3     nb=1260 avg=36
        M=4     nb=1260 avg=1297
        M=5     nb=45360        avg=1296
        M=6     nb=45360        avg=46657