Project Euler #8, I Don't Understand Where I'm Going Wrong

Project Euler #8, I don't understand where I'm going wrong

In fact your solution is too small rather than too big. The answer is what was pointed out in the comments, that there is integer overflow, and the clue is in the fact that your solution is close to the largest possible value for an signed int: 2147483647. You need to use a different type to store the product.

Note that the answer below is still 'correct' in that your code does do this wrong, but it's not what is causing the wrong value. Try taking your (working) code to http://codereview.stackexchange.com if you would like the folks there to tell you what you could improve in your approach and your coding style.

Previous answer

You are checking for a new greatest product inside the inner loop instead of outside. This means that your maximum includes all strings of less or equal ton 13 digits, rather than only exactly 13.

This could make a difference if you are finding a string which has fewer than 13 digits which have a large product, but a 0 at either end. You shouldn't count this as the largest, but your code does. (I haven't checked if this does actually happen.)

for (int i=0; i < num.length() -12; i++)
{
    product = ((int) num[i] - 48);
    for (int j=i+1; j<i+13; j++)
    {
        product = product * ((int) num[j] - 48);
    }
    if (greatestProduct <= product)
    {
        greatestProduct = product;
    }
}

Project Euler #8, I don't understand why I'm going wrong

You are skipping multiplication by 0 in your code. Don't do that; any 13 digit number with a 0 in it is not a valid candidate as multiplication always results in 0.

Simply multiply all the digits in a 13-character slice of the input string:

>>> from operator import mul
>>> from functools import reduce
>>> st = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
>>> size = 4
>>> max(reduce(mul, map(int, st[i:i + size])) for i in range(len(st) - size))
5832
>>> size = 13
>>> max(reduce(mul, map(int, st[i:i + size])) for i in range(len(st) - size))
23514624000

Project Euler 8 - I don't understand it

Reading the data

readFile reads the file "number.txt". If we put a small 16 digit number in a file called number.txt

7316
9698
8586
1254

Runing

euler_8 = do
   str <- readFile "number.txt"
   print $ str

Results in

"7316\n9698\n8586\n1254"

This string has extra newline characters in it. To remove them, the author splits the string into lines.

euler_8 = do
   str <- readFile "number.txt"
   print . lines $ str

The result no longer has any '\n' characters, but is a list of strings.

["7316","9698","8586","1254"]

To turn this into a single string, the strings are concatenated together.

euler_8 = do
   str <- readFile "number.txt"
   print . concat . lines $ str

The concatenated string is a list of characters instead of a list of numbers

"7316969885861254"

Each character is converted into an Int by digitToInt then converted into an Integer by fromInteger. On 32 bit hardware using a full-sized Integer is important since the product of 13 digits could be larger than 2^31-1. This conversion is mapped onto each item in the list.

euler_8 = do
   str <- readFile "number.txt"
   print . map (fromIntegral . digitToInt)
         . concat . lines $ str

The resulting list is full of Integers.

[7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4]

Subsequences

The author's next goal is to find all of the 13 digit runs in this list of integers. tails returns all of the sublists of a list, starting at any position and running till the end of the list.

euler_8 = do
   str <- readFile "number.txt"
   print . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

This results in 17 lists for our 16 digit example. (I've added formatting)

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
    [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
      [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
        [6,9,6,9,8,8,5,8,6,1,2,5,4],
          [9,6,9,8,8,5,8,6,1,2,5,4],
            [6,9,8,8,5,8,6,1,2,5,4],
              [9,8,8,5,8,6,1,2,5,4],
                [8,8,5,8,6,1,2,5,4],
                  [8,5,8,6,1,2,5,4],
                    [5,8,6,1,2,5,4],
                      [8,6,1,2,5,4],
                        [6,1,2,5,4],
                          [1,2,5,4],
                            [2,5,4],
                              [5,4],
                                [4],
                                 []
]

The author is going to pull a trick where we rearrange these lists to read off 13 digit long sub lists. If we look at these lists left-aligned instead of right-aligned we can see the sub sequences running down each column.

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,6,9,8,8,5,8,6,1,2,5,4],
  [9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,8,8,5,8,6,1,2,5,4],
  [9,8,8,5,8,6,1,2,5,4],
  [8,8,5,8,6,1,2,5,4],
  [8,5,8,6,1,2,5,4],
  [5,8,6,1,2,5,4],
  [8,6,1,2,5,4],
  [6,1,2,5,4],
  [1,2,5,4],
  [2,5,4],
  [5,4],
  [4],
  []
]

We only want these columns to be 13 digits long, so we only want to take the first 13 rows.

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,6,9,8,8,5,8,6,1,2,5,4],
  [9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,8,8,5,8,6,1,2,5,4],
  [9,8,8,5,8,6,1,2,5,4],
  [8,8,5,8,6,1,2,5,4],
  [8,5,8,6,1,2,5,4],
  [5,8,6,1,2,5,4],
  [8,6,1,2,5,4],
  [6,1,2,5,4],
  [1,2,5,4]
]

foldr (zipWith (:)) (repeat []) transposes a list of lists (explaining it belongs to perhaps another question). It discards the parts of the rows longer than the shortest row.

euler_8 = do
   str <- readFile "number.txt"
   print . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

We are now reading the sub-sequences across the lists as usual

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1],
  [3,1,6,9,6,9,8,8,5,8,6,1,2],
  [1,6,9,6,9,8,8,5,8,6,1,2,5],
  [6,9,6,9,8,8,5,8,6,1,2,5,4]
]

The problem

We find the product of each of the sub-sequences by mapping product on to them.

euler_8 = do
   str <- readFile "number.txt"
   print . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

This reduces the lists to a single number each

[940584960,268738560,447897600,1791590400]

From which we must find the maximum.

euler_8 = do
   str <- readFile "number.txt"
   print . maximum . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

The answer is

1791590400

Project Euler #8 Wrong answer, explanation needed

    nxt = 13

and

    while nxt < 1000: 
        for i in que[end:nxt]:
                    total *= int(i)
        if total > temp:
            temp = total
        total = 1
        end += 1
        nxt += 1

Project Euler #8, I can't figure out why my code gives absurdly high values

It is because (str[i] - 48) evaluates to an int, not an unsigned long long.

You have to cast the expression

product = (unsigned long long)(str[i] - '0') *(str[i+1] - '0') *(str[i+2] - '0') *(str[i+3] - '0') *(str[i+4] - '0') *(str[i+5] - '0') *(str[i+6] - '0') *(str[i+7] - '0') *(str[i+8] - '0') *(str[i+9] - '0') *(str[i+10] - '0') *(str[i+11] - '0') *(str[i+12] - '0');

Also you should use '0' instead of 48.

Instead of this line you can use another loop

product = 1;
for (int j = 0; j < 13; j++)
{
    if (!isdigit(str[i + j]) || str[i + j] == '0')
    {
        product = 0;
        break;
    }
    product *= str[i + j] - '0';
}

to calculate the product. In this case the cast is not necessary, because product has already the correct type.

---

Related Topics