# 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.

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

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

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

Theme: Rubric. Blog at WordPress.com.