001package net.n1da.dev.euler;
002
003import net.n1da.dev.euler.core.*;
004import net.n1da.dev.euler.helper.*;
005
006/**
007 * Solution for problem 8
008 * "<strong>Largest product in a series</strong>"
009 * completed on Fri, 10 Apr 2015, 09:07.
010 * 
011 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
012 * @since 09.04.2015 23:42:06
013 * 
014 * @see <a href="https://projecteuler.net/problem=8" target="_blank">Problem @ Project Euler</a>
015 * @see <a href="http://n1da.net/specials/projekt-euler/problem-8-groesstes-produkt-in-einer-serie/" target="_top">Solution @ Ni-Da-Net</a>
016 */
017public class PE0008 extends Problem {
018
019        /**
020         * The 1000 digits.
021         */
022        private short[] digits;
023        
024        /**
025         * The number of adjacent digits to find.
026         */
027        private int window;
028        
029        /**
030         * The storage for the different step counts.
031         */
032        private int[] counts;
033        
034        /**
035         * The storage for the different products.
036         */
037        private long[] products;
038        
039        /**
040         * A simple constructor to set {@link Problem#number number}
041         * and {@link Problem#title title}.
042         */     
043        public PE0008() {
044                super( 8, "Largest product in a series" );
045        }
046
047        /**
048         * Prepares the solving process by setting the wanted window size (13),
049         * initializing the storages and reading the 1000 digits from a file.
050         * 
051         * @see IO#readDigits(String, int)
052         */
053        @Override
054        public void prepare() {
055                super.prepare();                
056                window = 13;
057                counts = new int[ window ];
058                products = new long[ window ];
059                digits = IO.readDigits( "data-files/1000digits.txt", 1000 );
060                resetStorages();
061        }
062        
063        /**
064         * Solves this problem by running over every of the 1000 digits and
065         * multiplying it into the {@link #products} array. If the {@link #counts}
066         * array at the same place is incremented and equal to the {@link #window}
067         * size, a candidate to the maximum is found.
068         * 
069         * If a zero is found both local storages are {@link #resetStorages() reseted}.
070         * 
071         * @return the largest product of adjacent digits
072         * @see #resetStorages()
073         */
074        @Override
075        public String solve() {
076                long max = 0;
077                for( int i=0; i<digits.length; i++ ) {
078                        int cur = digits[ i ];
079                        
080                        if( cur == 0 ) {
081                                resetStorages();
082                        } else {
083                        
084                                for( int j=0; j<window; j++ ) {
085                                        counts[ j ]++;
086                                        
087                                        if( counts[ j ] > 0 ) {
088                                                products[ j ] *= cur;
089                                        }
090                                        
091                                        if( counts[ j ] == window ) {
092                                                if( max < products[ j ] ) {
093                                                        max = products[ j ];
094                                                        IO.debugln( "found new max = " + max );
095                                                }
096                                                
097                                                products[ j ] = 1;
098                                                counts[ j ] = 0;
099                                        }
100                                }
101                        }
102                }
103                
104                return IO.l2s( max );
105        }
106        
107        /**
108         * Resets the local storages {@link #counts} and {@link #products} by
109         * setting all their values back to standard.
110         */
111        private void resetStorages() {
112                for( int i=0; i<window; i++ ) {
113                        counts[ i ] = -i;
114                        products[ i ] = 1;
115                }
116        }
117}