Duncan's blog

February 3, 2009

Project Euler problem 40

Filed under: Coldfusion,Project Euler,Python — duncan @ 12:00 am
Tags: , , , ,

Problem 40:

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021…

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000

Firstly I completed this in Coldfusion. I got the correct answer by brute-forcing it, but the solution was slow. This took about 11 minutes on a CF 5 server; it would undoubtedly be a lot quicker on any CFMX server. I then rewrote it in Python, which spits out the correct answer within a couple of seconds.

I thought it might be interesting to do a code comparison between the two languages.
CFML:

<cfset fraction = "">
<cfset total = 1>

<cfloop index="i" from="1" to="1000000">
<!--- we're going to break out of the loop sooner than that --->
	<cfset fraction = fraction & i>
	
	<cfif Len(fraction) GTE 1000000>
		<cfbreak>
	</cfif>
</cfloop>

<cfset total = total *	Mid(fraction, 1, 1) * 
	Mid(fraction, 10, 1) * 
	Mid(fraction, 100, 1) * 
	Mid(fraction, 1000, 1) * 
	Mid(fraction, 10000, 1) * 
	Mid(fraction, 100000, 1) * 
	Mid(fraction, 1000000, 1)>

<cfoutput>#total#</cfoutput>

Python:

fraction = ""
total = 1

for i in range(1,1000000):
    fraction = fraction + str(i)

    if len(fraction) >= 1000000:
        break

total = total * \
        int(fraction[0]) * \
        int(fraction[9]) * \
        int(fraction[99]) * \
        int(fraction[999]) * \
        int(fraction[9999]) * \
        int(fraction[99999]) * \
        int(fraction[999999])

print(total)

Almost identical code. I’m still not anywhere near writing pythonic code, but it’s early days.

Basically I loop from 1 to 1000000 (not really that far, because I break out of the loop once our string has length of 1000000). As I go I append each loop counter to the string.

Then I just multiply together the 1st, 10th, 100th etc values from the string. That part could also have been done in a loop to simplify the code slightly. The whole thing’s not particularly clever, but it works.

If you’re coming to this from a Coldfusion background, you’re maybe wondering why I’m doing a DIV between each of the values before multiplying them. Because whitespace is important in Python, the \ can be used to join two lines together where the line length gets too long.

3 Comments »

  1. Nice solution! Here’s one in Perl: Problem 40

    Comment by grandcanyontours — May 25, 2009 @ 8:08 pm | Reply

  2. I used Haskell and it solved in instant.

    let f x = (show x) ++ f (x + 1) in product $ map (read . (:[]) . (f 1 !!)) [0,9,99,999,9999,99999,999999]

    Explanation:
    let f x = …: Generates a infinite sequence of digits like 123456789101112…
    That does not generate an infinite loop, because Haskell has lazy evaluation
    map (read . (:[]) . (f 1 !!)): Shorthand of map (\x -> read([f 1 !! x])). (:[]) x === x:[] === [x]
    It basically means: Get the nth digit as a character, make it a string, then make it an integer

    Comment by SHiNKiROU — November 14, 2010 @ 9:48 pm | Reply

  3. […] previously blogged about this Project Euler puzzle nearly 6 years ago, using both ColdFusion and Python.  This is my approach using PHP as a simple practical exercise […]

    Pingback by Project Euler: problem 40 (PHP) | Duncan's blog — October 12, 2014 @ 8:07 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: