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 30
010 * "<strong>Digit fifth powers</strong>"
011 * completed on Fri, 11 Dec 2015, 23:34
012 * 
013 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
014 * @since 15.10.2015 19:33:27
015 * 
016 * @see <a href="https://projecteuler.net/problem=30" target="_blank">Problem @ Project Euler</a>
017 * @see <a href="http://n1da.net/specials/projekt-euler/problem-30-ziffern-hoch-fuenf" target="_top">Solution @ Ni-Da-Net</a>
018 */
019public class PE0030 extends Problem {
020        
021        /**
022         * Stores the sums of the powered digits. As keys the sorted digits are used.
023         */
024        protected Hashtable< LargeNumber, LargeNumber > cache;
025
026        /**
027         * A simple constructor to set {@link Problem#number number}
028         * and {@link Problem#title title}.
029         */
030        public PE0030() {
031                super( 30, "Digit fifth powers" );
032        }
033
034        /**
035         * A simple base constructor to set the given {@link #number}
036         * and {@link #title}. In this special case it's needed for
037         * inheritance to {@link PE0034}.
038         * 
039         * @param num - the number of this problem
040         * @param tit - the title of this problem
041         */
042        protected PE0030( int num, String tit ) {
043                super( num, tit );
044        }
045
046        /**
047         * Just the {@link #cache} is initialized.
048         */
049        @Override
050        public void prepare() {
051                super.prepare();
052                cache = new Hashtable< LargeNumber, LargeNumber >();
053        }
054        
055        /**
056         * Beginning with 10 all numbers to 500.000 are tested, if the sum of
057         * its powered digits are equal to the number itself. To speed up the
058         * search, the {@link #cache} is used to reduce the power calculations.
059         * 
060         * @return the sum of all found numbers that are equals to their powered digit sum
061         */
062        @Override
063        public String solve() {
064                
065                int i = 0;
066                LargeNumber one = new LargeNumber( 1 );
067                LargeNumber num = new LargeNumber( 9 );
068                LargeNumber sum = new LargeNumber();
069                LargeNumber tmp, key;
070                
071                while( i < 500000 ) {
072                        num = num.add( one );
073                        key = num.getWithSortedDigits();
074                        
075                        if( cache.containsKey( key ) ) {
076                                tmp = cache.get( key );
077                        } else {
078                                tmp = getDigitSum( num );
079                                cache.put( key, tmp );
080                        }
081                        
082                        if( num.equals( tmp ) ) {
083                                IO.debugln( tmp + " <-> " + tmp );
084                                sum = sum.add( num );
085                        }
086
087                        i++;
088                }               
089                
090                return sum.toString();
091        }
092        
093        /**
094         * Calculates the sum of all digits of the given number. Therefore every digit is powered by 5.
095         * 
096         * @param num a {@link LargeNumber} to calculate the sum of its digits
097         * @return the sum of the power 5 digits as new {@link LargeNumber}
098         * @see LargeNumber#sumOfDigitPowers(int)
099         */
100        protected LargeNumber getDigitSum( LargeNumber num ) {
101                return num.sumOfDigitPowers( 5 );
102        }
103}