🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of ross-schlie

ross-schlie's solution

to Largest Series Product in the PHP Track

Published at Feb 04 2021 · 0 comments
Instructions
Test suite
Solution

Given a string of digits, calculate the largest product for a contiguous substring of digits of length n.

For example, for the input '1027839564', the largest product for a series of 3 digits is 270 (9 * 5 * 6), and the largest product for a series of 5 digits is 7560 (7 * 8 * 3 * 9 * 5).

Note that these series are only required to occupy adjacent positions in the input; the digits need not be numerically consecutive.

For the input '73167176531330624919225119674426574742355349194934', the largest product for a series of 6 digits is 23520.

Running the tests

  1. Go to the root of your PHP exercise directory, which is <EXERCISM_WORKSPACE>/php. To find the Exercism workspace run

     % exercism debug | grep Workspace
    
  2. Get PHPUnit if you don't have it already.

     % wget --no-check-certificate https://phar.phpunit.de/phpunit.phar
     % chmod +x phpunit.phar
    
  3. Execute the tests:

     % ./phpunit.phar largest-series-product/largest-series-product_test.php
    

Source

A variation on Problem 8 at Project Euler http://projecteuler.net/problem=8

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

largest-series-product_test.php

<?php

class SeriesTest extends PHPUnit\Framework\TestCase
{
    public static function setUpBeforeClass() : void
    {
        require_once 'largest-series-product.php';
    }

    /**
     * Since PHP can only support Integers between +/- 9223372036854775807
     * We will deal with the series of digits as strings to avoid having them cast to floats.
     */

    public function testCanFindTheLargestProductOf2WithNumbersInOrder() : void
    {
        // The number starts with a 0, qualifying it to be an octal
        // So it needs to be a string so PHP doesn't complain
        $series = new Series("0123456789");
        $this->assertEquals(72, $series->largestProduct(2));
    }

    public function testCanFindTheLargestProductOf2() : void
    {
        $series = new Series(576802143);
        $this->assertEquals(48, $series->largestProduct(2));
    }

    public function testFindsTheLargestProductIfSpanEqualsLength() : void
    {
        $series = new Series(29);
        $this->assertEquals(18, $series->largestProduct(2));
    }

    public function testCanFindTheLargestProductOf3WithNumbersInOrder() : void
    {
        $series = new Series(123456789);
        $this->assertEquals(504, $series->largestProduct(3));
    }

    public function testCanFindTheLargestProductOf3() : void
    {
        $series = new Series(1027839564);
        $this->assertEquals(270, $series->largestProduct(3));
    }

    public function testCanFindTheLargestProductOf5WithNumbersInOrder() : void
    {
        $series = new Series("0123456789");
        $this->assertEquals(15120, $series->largestProduct(5));
    }

    public function testCanGetTheLargestProductOfABigNumber() : void
    {
        $series = new Series("73167176531330624919225119674426574742355349194934");
        $this->assertEquals(23520, $series->largestProduct(6));
    }

    public function testCanGetTheLargestProductOfABigNumberProjectEuler() : void
    {
        $digits = "731671765313306249192251196744265747423553491949349698352031277450632623957831801698480186947"
            . "8851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096"
            . "3295227443043557668966489504452445231617318564030987111217223831136222989342338030813533627"
            . "6614282806444486645238749303589072962904915604407723907138105158593079608667017242712188399"
            . "8797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490"
            . "7711670556013604839586446706324415722155397536978179778461740649551492908625693219784686224"
            . "8283972241375657056057490261407972968652414535100474821663704844031998900088952434506585412"
            . "2758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828"
            . "4891288314260769004224219022671055626321111109370544217506941658960408071984038509624554443"
            . "6298123098787992724428490918884580156166097919133875499200524063689912560717606058861164671"
            . "0940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

        $series = new Series($digits);
        $this->assertEquals(23514624000, $series->largestProduct(13));
    }

    public function testReportsZeroIfTheOnlyDigitsAreZero() : void
    {
        $series = new Series("0000");
        $this->assertEquals(0, $series->largestProduct(2));
    }

    public function testReportsZeroIfAllSpansIncludeZero() : void
    {
        $series = new Series(99099);
        $this->assertEquals(0, $series->largestProduct(3));
    }

    public function testRejectsSpanLongerThanStringLength() : void
    {
        $this->expectException(InvalidArgumentException::class);

        $series = new Series(123);
        $series->largestProduct(4);
    }

    /**
     * There may be some confusion about whether this should be 1 or error.
     * The reasoning for it being 1 is this:
     * There is one 0-character string contained in the empty string.
     * That's the empty string itself.
     * The empty product is 1 (the identity for multiplication).
     * Therefore LSP('', 0) is 1.
     * It's NOT the case that LSP('', 0) takes max of an empty list.
     * So there is no error.
     * Compare against LSP('123', 4):
     * There are zero 4-character strings in '123'.
     * So LSP('123', 4) really DOES take the max of an empty list.
     * So LSP('123', 4) errors and LSP('', 0) does NOT
     *
     */
    public function testReports1ForEmptyStringAndEmptyProduct0Span() : void
    {
        $series = new Series("");
        $this->assertEquals(1, $series->largestProduct(0));
    }

    /**
     * As above, there is one 0-character string in '123'.
     * So again no error. It's the empty product, 1.
     */
    public function testReports1ForNonemptyStringAndEmptyProduct0Span() : void
    {
        $series = new Series("123");
        $this->assertEquals(1, $series->largestProduct(0));
    }

    public function testRejectsEmptyStringAndNonzeroSpan() : void
    {
        $this->expectException(InvalidArgumentException::class);

        $series = new Series("");
        $series->largestProduct(1);
    }

    public function testRejectsInvalidCharacterInDigits() : void
    {
        $this->expectException(InvalidArgumentException::class);

        $series = new Series("1234a5");
        $series->largestProduct(2);
    }

    public function testRejectsNegativeSpan() : void
    {
        $this->expectException(InvalidArgumentException::class);

        $series = new Series("12345");
        $series->largestProduct(-1);
    }
}
<?php

/**
 * Given a series of numbers, can find the Largest Series Product
 * @see largestProduct
 */
class Series {

    private $numberSeries;

    /**
     * @param String - String containing numbers
     */
    function __construct($numberSeries) {
        $this->numberSeries = $numberSeries;
    }

    /**
     * Validate input and throw InvalidArgumentException when invalid
     * @param Integer $number - the length of digists to get a product for
     * @param Integer $seriesLen - the length of number series
     * @throws InvalidArgumentException
     */
    private function validate($number, $seriesLen) {
        if ($number < 0) {
            throw new InvalidArgumentException("Number is less than 0.");
        }

        if ($number > $seriesLen) {
            throw new InvalidArgumentException("Number is longer than series.");
        }

        if ($number > 0 && !is_numeric($this->numberSeries)) {
            throw new InvalidArgumentException("Can't get a product for a non-numeric series.");
        }
    }

    /**
     * Find the largest product for a series of $number digits from the number series
     * @param Integer $number 
     * @return Integer highest product of numbers m in a series 
     */
    public function largestProduct($number) {
        $seriesLen = strlen($this->numberSeries);
        $this->validate($number, $seriesLen);

        //?
        if ($number < 1) {
            return 1;
        }

        $highestProduct = 0;
        //Note that we don't want to go "out of bounds", so check up to and including
        //the lenght of number series - the number in a sequence
        //Time complexity of N for this loop, where N is the length of the number series
        for ($n = 0; $n <= $seriesLen - $number; $n++) {
            //all prior combinations should include the number, so no need to lookback
            //convert the numbers in the sequence to numbers and record the product
            //if it's the largest so far.
            $sequence = substr($this->numberSeries, $n, $number);
            
            //the length of $sequence SHOULD equal $number
            $currentProduct = 1;
            //Time complexity of N (above) * M for $number which is the length of the sequence
            for ($m = 0; $m < $number; $m++) {
                $currentProduct *= $sequence[$m];
            }

            
            if ($currentProduct > $highestProduct) {
                $highestProduct = $currentProduct;
            }
        }
      
        return $highestProduct;
    }
}

?>

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?