Project Euler Problem 8

[Petr Schreiber]

One of possible solutions for problem #8



' Solution for Eulers Problem #8 as defined here http://projecteuler.net/index.php?section=problems&id=8
' Petr Schreiber, 2008

USES "Console"

dim i as long
dim t1, t2 as quad
dim product, maxProduct as long

printl "Calculating Eulers problem #8"
printl "=> Find the greatest product of five consecutive"+$CRLF+"=> digits in the 1000-digit number."
printl REPEAT$(64, "-")

hiResTimer_init
t1 = hiResTimer_Get

dim sBigNumber as string = "73167176531330624919225119674426574742355349194934"+ _
"96983520312774506326239578318016984801869478851843"+ _
"85861560789112949495459501737958331952853208805511"+ _
"12540698747158523863050715693290963295227443043557"+ _
"66896648950445244523161731856403098711121722383113"+ _
"62229893423380308135336276614282806444486645238749"+ _
"30358907296290491560440772390713810515859307960866"+ _
"70172427121883998797908792274921901699720888093776"+ _
"65727333001053367881220235421809751254540594752243"+ _
"52584907711670556013604839586446706324415722155397"+ _
"53697817977846174064955149290862569321978468622482"+ _
"83972241375657056057490261407972968652414535100474"+ _
"82166370484403199890008895243450658541227588666881"+ _
"16427171479924442928230863465674813919123162824586"+ _
"17866458359124566529476545682848912883142607690042"+ _
"24219022671055626321111109370544217506941658960408"+ _
"07198403850962455444362981230987879927244284909188"+ _
"05886116467109405077541002256983155200055935729725"+ _
"84580156166097919133875499200524063689912560717606"+ _
"71636269561882670428252483600823257530420752963450"

' -- In the string above 1 "letter" correspods to 1 number
' -- By overlaying the byte array over string we get array
' -- of ASCII values. ASCII 0 = 48, ASCII 1 = 49 ... so we
' -- subtract lower boundary to get real numbers
dim BigNumberArray(1000) as byte at strptr(sBigNumber)
for i = 1 to 1000
BigNumberArray(i) -= 48
next

for i = 1 to 996 ' -- Last quintet will be 996 997 998 999 1000

product = BigNumberArray(i) * BigNumberArray(i+1) * BigNumberArray(i+2) * BigNumberArray(i+3) * BigNumberArray(i+4)
maxproduct = max(product, maxproduct)

next

t2 = hiResTimer_Get

printl "Result: "+FORMAT$(maxProduct, "0,")+"; calculation took"+STR$(t2-t1)+" microseconds"
waitkey

[Michael Clease]

this was mine 2 different twist on the same idea but not as fast as yours



'Find the greatest product of five consecutive digits in the 1000-digit number.


uses "Console"

DIM n AS LONG
DIM Counter AS LONG
DIM sProblem AS STRING
DIM Products(1000) AS DWORD
DIM Product AS DWORD
DIM Answer AS DWORD

sProblem = "73167176531330624919225119674426574742355349194934 _
96983520312774506326239578318016984801869478851843 _
85861560789112949495459501737958331952853208805511 _
12540698747158523863050715693290963295227443043557 _
66896648950445244523161731856403098711121722383113 _
62229893423380308135336276614282806444486645238749 _
30358907296290491560440772390713810515859307960866 _
70172427121883998797908792274921901699720888093776 _
65727333001053367881220235421809751254540594752243 _
52584907711670556013604839586446706324415722155397 _
53697817977846174064955149290862569321978468622482 _
83972241375657056057490261407972968652414535100474 _
82166370484403199890008895243450658541227588666881 _
16427171479924442928230863465674813919123162824586 _
17866458359124566529476545682848912883142607690042 _
24219022671055626321111109370544217506941658960408 _
07198403850962455444362981230987879927244284909188 _
84580156166097919133875499200524063689912560717606 _
05886116467109405077541002256983155200055935729725 _
71636269561882670428252483600823257530420752963450"
'...
Dim T1, T2, T3, T4 As QUAD
'---Initialize hi resolution timer
HiResTimer_Init

' this is outside the loop because of how the data is presented
sProblem = REMOVE$(sProblem, ANY $CRLF+$TAB+" ") 'msgbox 0, STR$(LEN(sProblem))

T1 = hirestimer_get
For n = 1 to 1000-4 '(Len(sProblem))
INCR Counter
Products(Counter) = VAL(Mid$(sProblem, n,1))
Products(Counter) *= VAL(Mid$(sProblem,1+n,1))
Products(Counter) *= VAL(Mid$(sProblem,2+n,1))
Products(Counter) *= VAL(Mid$(sProblem,3+n,1))
Products(Counter) *= VAL(Mid$(sProblem,4+n,1))
NEXT
ARRAY SORT Products, DESCEND
T2 = hirestimer_get

console_printat ("Answer: " + STR$(Products(1)), 1, 1)
console_printat ("Elapsed time in microseconds: " & FORMAT$(T2-T1),1,2)

T3 = hirestimer_get
For n = 1 to 1000-4 '(Len(sProblem))
Product = VAL(Mid$(sProblem, n,1)) * VAL(Mid$(sProblem,1+n,1)) * VAL(Mid$(sProblem,2+n,1)) * VAL(Mid$(sProblem,3+n,1)) * VAL(Mid$(sProblem,4+n,1))
Answer = MAX(Answer,Product)
NEXT
' ARRAY SORT Products, DESCEND
T4 = hirestimer_get

console_printat ("Answer: " + STR$(Answer), 1, 4)
console_printat ("Elapsed time in microseconds: " & FORMAT$(T4-T3),1,5)
console_waitkey

[Petr Schreiber]

Hi Michael,

my first idea was exactly the same as yours!

Your code is more easy to read and not much more than just 2x slower on my PC.
It seems string cutting is still very fast in ThinBasic, and my pre-calculation of string2numbers did not had such a impact. Maybe with longer number it would be more different :)

[ErosOlmi]

A little note:

in multi-line strings it is not necessary to terminate the line with line continuation char _
thinBasic automatically will detect the end of line

Ciao
Eros

PS: those problems are very fascinating and very useful because, apart the math problems they pose, they show very different ways of doing the same things.

[ErosOlmi]

This is my try in which I've used pointers and multiplied ASC values of single byte numbers.

Seems quite fast but I suppose that in this particular Euler problem Oxygen module would give a lot of speed.



'Find the greatest product of five consecutive digits in the 1000-digit number.

uses "Console"

DIM n AS LONG
DIM sProblem AS STRING
DIM Product AS DWORD
DIM Answer AS DWORD

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

' this is outside the loop because of how the data is presented
sProblem = REMOVE$(sProblem, ANY $CRLF+$TAB+$SPC) 'msgbox 0, STR$(LEN(sProblem))

'...
Dim T1, T2 As QUAD
'---Initialize hi resolution timer
HiResTimer_Init

dim pStr as long
dim lBase as long

T1 = hirestimer_get
pStr = strptr(sProblem)
lBase = asc("0")

For n = 1 to 1000-4
Product = (peek(byte, pStr ) - lBase) * _
(peek(byte, pStr + 1) - lBase) * _
(peek(byte, pStr + 2) - lBase) * _
(peek(byte, pStr + 3) - lBase) * _
(peek(byte, pStr + 4) - lBase)
Answer = MAX(Answer, Product)
incr pStr
NEXT

T2 = hirestimer_get

printl "Answer: " + STR$(Answer)
printl "Elapsed time in microseconds: " & FORMAT$(T2-T1)
waitkey

[Michael Clease]

on my main pc when I run Eros's version it produces exactly the same time as my second one.