001package net.n1da.dev.euler;
002
003import net.n1da.dev.euler.core.*;
004import net.n1da.dev.euler.helper.*;
005
006/**
007 * Solution for problem 31
008 * "<strong>Coin sums</strong>"
009 * completed on Sat, 19 Dec 2015, 22:30.
010 * 
011 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
012 * @since 12.12.2015 00:23:18
013 * 
014 * @see <a href="https://projecteuler.net/problem=31" target="_blank">Problem @ Project Euler</a>
015 * @see <a href="http://n1da.net/specials/projekt-euler/problem-31-summen-von-muenzen" target="_top">Solution @ Ni-Da-Net</a>
016 */
017public class PE0031 extends Problem {
018
019        /**
020         * Stores for every coin the count to fill 200 pence.
021         */
022        private int[] coins;
023        
024        /**
025         * Stores for every coin how many are used in a combination.
026         */
027        private int[] used;
028        
029        /**
030         * Counts the number of found combinations.
031         */
032        private int count;
033        
034        /**
035         * A simple constructor to set {@link Problem#number number}
036         * and {@link Problem#title title}.
037         */
038        public PE0031() {
039                super( 31, "Coin sums" );
040        }
041
042        /**
043         * Initializes the {@link #coins} and {@link #used} arrays, and the {@link #count}
044         * with 0. 
045         */
046        @Override
047        public void prepare() {
048                super.prepare();
049                coins = new int[]{ 200, 100, 50, 20, 10, 5, 2, 1 };
050                used  = new int[]{   0,   0,  0,  0,  0, 0, 0, 0 };
051                count = 0;
052        }
053        
054        /**
055         * This problem is solved by a recursive call of the {@link #check(int)} method.
056         * Here this method is called and the final {@link #count} is returned.
057         * 
058         * @return the count of all found combinations
059         */
060        @Override
061        public String solve() {
062                
063                check( 0 );
064
065                return IO.i2s( count );
066        }
067
068        /**
069         * Here the algorithm is implemented by checking every combination of coins.
070         * If the {@link #getSum() sum} of the current combination is less than 200
071         * this method is called recursively for the next smaller coin.
072         * 
073         * @param level the position in {@link #coins} array
074         */
075        private void check( int level ) {
076                int div = 200 / coins[ level ];
077                for( int i=0; i<=div; i++ ) {
078                        used[ level ] = i;
079                        int sum = getSum();
080                        if( sum == 200 ) {
081                                count++;
082                                IO.debugln( "found [ " + IO.join( used, ", " ) + " ]" );
083                                i = div;
084                                used[ level ] = 0;
085                        } else if( sum > 200 ) {
086                                i = div;
087                                used[ level ] = 0;
088                        } else {
089                                if( level == 6 ) {
090                                        count++;
091                                        used[ 7 ] = 200 - sum;
092                                        IO.debugln( "found [ " + IO.join( used, ", " ) + " ]" );
093                                        used[ 7 ] = 0;
094                                } else {
095                                        check( level+1 );
096                                }
097                        }
098                }
099        }
100        
101        /**
102         * Calculates the sum of the combination in {@link #used} array.
103         * 
104         * @return the sum of all products of elements in {@link #used} and #coins array
105         */
106        private int getSum() {
107                int res = 0;
108                
109                for( int i=0; i<coins.length; i++ ) {
110                        res += coins[ i ] * used[ i ];
111                }
112                
113                return res;
114        }
115}