// Palindromes.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 http://www.gnu.org/licenses/licenses.html#TOCGPL
*/
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();
}
}
|