001package net.n1da.dev.euler;
002
003import java.util.*;
004
005import net.n1da.dev.euler.core.*;
006import net.n1da.dev.euler.helper.*;
007
008/**
009 * Solution for problem 51
010 * "<strong>Prime digit replacements</strong>"
011 * completed on Sun, 14 Aug 2016, 18:09.
012 * 
013 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
014 * @since 14.08.2016 16:34:27
015 * 
016 * @see <a href="https://projecteuler.net/problem=51" target="_blank">Problem @ Project Euler</a>
017 * @see <a href="http://n1da.net/specials/projekt-euler/problem-51-ziffern-ersetzen-in-primzahlen" target="_top">Solution @ Ni-Da-Net</a>
018 */
019public class PE0051 extends Problem {
020
021        /**
022         * Internal memory for all primes referenced by their length
023         */
024        private Hashtable< Integer, ArrayList< LargeNumber > > mem;
025        
026        /**
027         * A simple constructor to set {@link Problem#number number}
028         * and {@link Problem#title title}.
029         */
030        public PE0051() {
031                super( 51, "Prime digit replacements" );
032        }
033
034        /**
035         * Prepares this problem by loading the {@link #mem memory} with
036         * primes between 100 and 1.000.000 sorted by their number of
037         * digits.
038         * 
039         * @see Sieve
040         */
041        @Override
042        public void prepare() {
043                super.prepare();
044                
045                mem = new Hashtable< Integer, ArrayList< LargeNumber > >();
046                Sieve sieve = new Sieve( 1000000 );
047                
048                for( int prim : sieve ) {
049                        if( prim > 100 ) {
050                                LargeNumber num = new LargeNumber( prim );
051                                int key = num.getLength();
052                                if( !mem.containsKey( key ) ) {
053                                        mem.put( key, new ArrayList< LargeNumber >() );
054                                }
055                                mem.get( key ).add( num );
056                        }
057                }
058        }
059        
060        /**
061         * This method solves the problem by replacing every digit in a prime
062         * searching for other primes in this way.
063         * 
064         * @return the first prime that leads to a eight prime long series
065         */
066        @Override
067        public String solve() {
068                
069                Enumeration< Integer > keys = mem.keys();
070                while( keys.hasMoreElements() ) {
071                        int key = keys.nextElement();
072                        IO.debugln( "key = " + key );
073                        for( LargeNumber prim : mem.get( key ) ) {
074                                for( int i = 1; i < prim.getLength(); i++ ) {
075                                        int count = 1;
076                                        String result = prim.toString();
077                                        for( int x = 0; x < 11; x++ ) {
078                                                if( x != prim.getDigit( i ) ) {
079                                                        LargeNumber num = prim.replaceDigit( prim.getDigit( i ), x );
080                                                        if( mem.get( key ).contains( num ) ) {
081                                                                count++;
082                                                                result += " > " + num;
083                                                        }
084                                                }
085                                        }
086                                        
087                                        if( count >= 6 ) {
088                                                IO.infoln( "found series: " + result );
089                                        }
090                                        if( count == 8 ) {
091                                                return prim.toString();
092                                        }
093                                }
094                        }
095                }
096                
097                return null;
098        }
099}