nested/nested_vanb.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to Nested Palindromes
  8  * 
  9  *  Here are some observations. Because of the no-adjacent-digits constraint, 
 10  *  no palindrome or sub-palindrome can be of even length. There must always 
 11  *  be a 'middle' digit. Thus, the only legitimate numbers must be 2^n-1 in length, 
 12  *  same as the number of moves in a towers of hanoi puzzle with n disks. 
 13  *  In fact, if you letters the digits by first occurrence, you get a string like this: 
 14  *      abacabadabacaba 
 15  *  which is the same as the disk moves in ToH. Every digit past 'a' is only adjacent to 'a'.
 16  *  So, for any digits you don't know, there are 9 possibilities: 
 17  *      'a' can be anything but 0 (since the number cannot have a leading zero), 
 18  *      and everything else can be anything but whatever you chose for 'a'. 
 19  * 
 20  * @author vanb
 21  */
 22 public class nested_vanb
 23 {
 24     public Scanner sc;
 25     public PrintStream ps;
 26 
 27     public int maxlevel = 0;
 28     public char generators[] = new char[15];
 29     
 30     public String generate( int level )
 31     {
 32         String result = "";
 33         
 34         if( level>0 )
 35         {
 36             --level;
 37             result = generate(level) + generators[level] + generate(level);
 38         }
 39                 
 40         return result;
 41     }
 42     
 43     /**
 44      * Driver.
 45      * @throws Exception
 46      */
 47     public void doit() throws Exception
 48     {
 49         sc = new Scanner( new File( "nested.judge" ) );
 50         ps = new PrintStream( new FileOutputStream( "nested.solution" ) );
 51         
 52         // These are legitimate lengths.
 53         // They are powers of 2 minus 1
 54         int legit[] = new int[20];
 55         for( int i=0; i<20; i++ )
 56         {
 57             legit[i] = (1<<i)-1;
 58         }
 59         
 60         // See which of the ten digits are available for the first place
 61         boolean avail[] = new boolean[10];
 62 
 63         for(;;)
 64         {           
 65             // There are a number of ways we can fail.
 66             // We'll use this variable to see if any of the happens.
 67             boolean fail = true;
 68             
 69             long n = sc.nextLong();
 70             if( n==0L ) break;
 71 
 72             char digits[] = sc.next().trim().toCharArray();
 73             
 74             // We fail if the digit string isn't of the right length.
 75             for( int i=0; i<20 && fail; i++ )
 76             {
 77                 if( digits.length == legit[i] ) fail = false;
 78             }
 79                        
 80             if( !fail )
 81             {
 82                 Arrays.fill( generators, '-' );
 83                 maxlevel = 0;
 84                 for( int i=0; i<digits.length; i++ )
 85                 {
 86                     int level = 1;
 87                     int k = i+1;
 88                     while( (k&1)==0 )
 89                     {
 90                         k >>= 1;
 91                         level++;
 92                     }
 93                     if( level>maxlevel ) maxlevel = level;
 94                     --level;
 95                     
 96                     if( generators[level]=='-' || generators[level]=='?' ) generators[level] = digits[i];
 97                     if( generators[level]!=digits[i] ) fail = true;
 98                 }
 99                 
100                 if( generators[0]=='0' ) fail = true;
101                 if( Character.isDigit( generators[0] )) for( int i=1; i<maxlevel; i++ )
102                 {
103                     if( generators[i]==generators[0] ) fail = true;
104                 }
105             }
106             
107             String base9str = Long.toString( n-1, 9 );
108             System.err.println( base9str );
109             int need = 0;
110             for( int i=0; i<maxlevel; i++ )
111             {
112                 if( generators[i]=='?' ) ++need;
113             }
114             
115             if( need==0 && n!=1 ) fail=true;
116             if( need>0 && need<base9str.length() )fail = true;
117             String pad = "00000000000000000000" + base9str;
118             char base9[] = pad.substring( pad.length()-need, pad.length() ).toCharArray();          
119             
120             int p=0;
121             
122             // The first digit is special.
123             if( digits[0]=='?' )
124             {
125                 // This array will show which digits are available for digit 1
126                 Arrays.fill( avail, true );
127                 avail[0] = false;
128                 
129                 // If any digit has been used anywhere else in the number,
130                 // then it's not available for the 1st digit
131                 for( int i=0; i<maxlevel; i++ )
132                 {
133                     if( generators[i]!='?' ) avail[(int)(generators[i]-'0')] = false;
134                 }
135                 
136                 int count = (int)(base9[p++]-'0');
137                 int digit = 1;
138                 while( digit<10 && !avail[digit] ) ++digit;
139                 for( int i=0; i<count; i++ )
140                 {
141                     ++digit;
142                     while( digit<10 && !avail[digit] ) ++digit;
143                 }
144                 
145                 if( digit<10 ) digits[0] = generators[0] = (char)(digit+'0'); 
146                 else fail = true;
147             }
148             
149             if( !fail ) for( int i=1; i<digits.length; i++ ) if( digits[i]=='?' )
150             {
151                 int j = i+1;
152                 int g = 0;
153                 while( (j&1)==0 )
154                 {
155                     ++g;
156                     j>>=1;
157                 }
158                 
159                 if( generators[g]=='?' )
160                 {
161                     char ch = base9[p++];
162                     if( generators[0]<=ch ) ++ch;
163                     generators[g] = digits[i] = ch;
164                 }
165                 else
166                 {
167                     digits[i] = generators[g];
168                 }
169             }            
170             ps.println( fail ? "-1" : new String( digits ) );
171         }
172     }
173     
174     /**
175      * @param args
176      */
177     public static void main( String[] args ) throws Exception
178     {
179         new nested_vanb().doit();
180     }   
181 }