Project Euler / programming problems

General Chat
245

I’m back with the awful one line solutions.

Problem 8

Though it would probably be alright if I simply made a function for number.slice(iter, iter + window).split('').reduce((prev, curr) => Number(prev) * Number(curr)) instead of copy-pasting it twice.

const _number = `73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450`.split('\n').join('');

const findBiggestProduct = (number, window, maxProduct=0, iter=0) => iter > number.length - window ? maxProduct : maxProduct < number.slice(iter, iter + window).split('').reduce((prev, curr) => Number(prev) * Number(curr)) ? findBiggestProduct(number, window, number.slice(iter, iter + window).split('').reduce((prev, curr) => Number(prev) * Number(curr)), iter + 1) : findBiggestProduct(number, window, maxProduct, iter + 1);

console.log(findBiggestProduct(_number, 13));
2 Likes
246

.replace('\n', '');

2 Likes
247

Seems to work similar to python with \ also.

Summary 
N="73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450"
248

Nah double ticks in js are string templates. Something like print "%s" % myVarAsString except with a more convenient syntax, so this one would be console.log('${mayVar}') (imagine ’ are ticks, it’s incompatible with markdown’s inline code formatting). But they stomach newlines so I used them just for that.

1 Like
249

It seems I’m the only person who convert those .txt files to json format before actually solving :cry:

250

How do you do it actually? Do you download the description in some way, or was it just in this particular case that you saved the number in a txt file?

251

Can we improve on the running time? (That might be the challenging part of this problem)

252

I mean whenever there’s a zero you could probably skip a bunch of terms in the loop maybe, and have the default value return zero in case they gave you a bad number with many zeros?

That’s the only thing I can think of off the top of my head, without analysing the specifics of the given number. Any other ideas?

Edit:

I mean would it be faster to keep track of the first and thirteenth number and then divide and multiply as you shift along? Divide out the term leaving the window, multiply by the new term? (Being careful with zero :slight_smile: )

It’s hard to know, since I don’t know in general what’s the slow part. I guess if you minimise operations it helps a bit.

2 Likes
253

Not sure if this leads to something significant, but here is an idea:

By comparing the i-th digit with the (i + 13)-th digit we can conclude something about whether the maximal subsequence might start / end here. For example if the i-th digit is strictly less than the (i + 13)-th digit, then the sequence cannot start at the i-th digit.

Analogously we could compare the product of digits number i, (i + 1), …, (i + k) and the product of digits with number (i + 13), (i + 14), …, (i + 13 + k) and potentially gain a similar insight.

254

With data like this (1000 chars, 13 numbers to multiply) probably the most effective way to speed up runtime is to switch languages haha

If the length of the string and/or the size of the product is much bigger maybe easier to see where to optimize

1 Like
255

I don’t know either, but I’d guess that multiplying large numbers might be a bit slow and we should try to avoid it if possible.

Maybe, but I’m mainly interested in the runtime from an algorithmic point of view.

256

Some multiplication ideas:

  • zero negates the entire tuple so if the next i is a zero you can immediately skip 13
  • one makes it 12 numbers instead so it’s unlikely that it will be in the winning tuple, but not completely unlikely, for example if on both sides of the tuple there’s a zero and you have to work with this 1
  • for the purposes of this task I think multiplication and addition yield the same result when comparing (the tuple with the highest sum will also be the one with the highest product) if it at all matters (maybe it does to the maths folk) and if I’m correct on this one, with the exception of 1 and 0

Some algorithm ideas:

  • binary search will most likely be faster than a straight loop (logn vs n)
  • using a stack for the tuple and working with that number as a (big)number, extrating the next number by doing mod 10 and modifying the number as / 10 (keeping it integer)

Edit: I think the two algorithm ideas are kind of mutually exclusive though

1 Like
257

I don’t think we can do better than linear since we have to look at all the numbers. But yeah I think we can cut down on looping over each number in the product (say if 13 were instead 5000). I like shinuitos track-first-and-last idea, that at least makes it O(N) instead of O(N×M) where N is the length of string, M length of product

2 Likes
258

How does one binary search if the data is not sorted (or otherwise organized)?

1 Like
259

I was also kind of curious if that idea would work, and or if it would be relevant, but immediately dismissed it because if the number 1 :stuck_out_tongue:

But if you have a reason to skip strings of ones and zeros I can kind of understand it :slight_smile:

1 Like
260

Uhh… (3,2) (5,1)

261

But we have an array of numbers, right? If you decide to go the array way.

Edit: oh I see what you meant now. Scratch that then

At the end of that list item I mentioned that.

262

9 * 2 = 18 < 25 = 5 * 5

9+2 = 11 > 10 = 5+5

This is true for sure. However this algorithm multiplies large numbers, which will take more and more time depending on how many consequent digits we multiply. At some point it stops being a constant-bounded operation, no?

3 Likes
263

Right, should’ve checked that myself before proposing.

2 Likes
264

Oops sorry. Here’s a list of other counter examples:

>>> for i in range(2, 10):
...     for j in range(i, 10):
...         for k in range(2, 10):
...             for h in range(k, 10):
...                 if i + j < k + h and i * j > k * h:
...                     print("(%s, %s), (%s, %s)" % (i, j, k, h))
... 
(3, 5), (2, 7)
(3, 6), (2, 8)
(3, 7), (2, 9)
(4, 4), (2, 7)
(4, 5), (2, 8)
(4, 5), (2, 9)
(4, 6), (2, 9)
(4, 7), (3, 9)
(5, 5), (2, 9)
(5, 5), (3, 8)
(5, 6), (3, 9)
3 Likes