Duncan's blog

October 31, 2008

Project Euler: problem 17

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

After completing the first eleven problems, I’ve started to cherry-pick the ones I think I can tackle. I jumped ahead a bit to problem 17.

Problem 17:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

So this is kind of a fun problem that I think is actually a useful thing to know as a web developer. You might not have a practical application where you need to convert digits to words, however there are similar applications. For instance you might want to output a date or time difference in words rather than numbers, e.g. ‘you last logged in four days / three weeks / two months / one year ago’. The principles are similar.

<cfset numbers = ArrayNew(1)>
<cfset words = ArrayNew(1)>
<cfset sum = 0>

<cfset numbers[1] = "one">
<cfset numbers[2] = "two">
<cfset numbers[3] = "three">
<cfset numbers[4] = "four">
<cfset numbers[5] = "five">
<cfset numbers[6] = "six">
<cfset numbers[7] = "seven">
<cfset numbers[8] = "eight">
<cfset numbers[9] = "nine">
<cfset numbers[10] = "ten">
<cfset numbers[11] = "eleven">
<cfset numbers[12] = "twelve">
<cfset numbers[13] = "thirteen">
<cfset numbers[14] = "fourteen">
<cfset numbers[15] = "fifteen">
<cfset numbers[16] = "sixteen">
<cfset numbers[17] = "seventeen">
<cfset numbers[18] = "eighteen">
<cfset numbers[19] = "nineteen">
<cfset numbers[20] = "twenty">
<cfset numbers[30] = "thirty">
<cfset numbers[40] = "forty">
<cfset numbers[50] = "fifty">
<cfset numbers[60] = "sixty">
<cfset numbers[70] = "seventy">
<cfset numbers[80] = "eighty">
<cfset numbers[90] = "ninety">

<cfloop index="i" from="1" to="1000">
	<cfset numberAsString = "">
	
	<!--- how many thousands? --->
	<cfset thousands = i \ 1000>
	<cfset hundreds = i \ 100>	<!--- DIV 100 --->
	<cfset tens = (i \ 10) MOD 10>	<!--- DIV 10 MOD 10 --->
	<cfset units = i MOD 10>
	
	<cfif thousands GT 0>
		<cfset numberAsString = numberAsString & numbers[thousands] & " thousand">
	</cfif>
	
	<cfif hundreds GT 0 AND hundreds LT 10>
		<cfset numberAsString = numberAsString & numbers[hundreds] & " hundred">
		
		<cfif (tens GT 0 AND tens LT 10) OR units GT 0>
			<cfset numberAsString = numberAsString & " and ">
		</cfif>
	</cfif>
	
	<cfif tens EQ 1>
		<cfset numberAsString = numberAsString & numbers[(tens*10) + units]>
	</cfif>
	
	<cfif tens GT 1 AND tens LT 10>
		<cfset numberAsString = numberAsString & numbers[tens*10] & " ">
	</cfif>
	
	<cfif units GT 0 AND tens NEQ 1>
		<cfset numberAsString = numberAsString & numbers[units]>
	</cfif>
	
	<cfoutput>#numberAsString#</cfoutput><br>
	
	<!--- strip out the spaces --->
	<cfset ArrayAppend(words, REReplace(numberAsString, "[[:space:]]", "", "ALL"))>
</cfloop>

<cfloop index="i" from="1" to="#ArrayLen(words)#">
	<cfset sum = sum + Len(words[i])>
</cfloop>

<cfoutput><strong>#sum#</strong></cfoutput>

This code’s not as lean as it could be. However I hope it’s easy to understand, which is perhaps more important!

Firstly I create an array for the words we’ll need to use to build up our string. I set the array index equal to whatever that number is. This means our array has lots of empty elements; we’ll be fine so long as we don’t try and loop through the array from 1 to the end.

Then I loop up to 1000. At each iteration, do some DIV and MOD calculations on the loop counter. In Coldfusion, the DIV operation is represented by a \ instead of the normal / used for floating point division. Just to clarify for anyone who doesn’t know what I mean by DIV: divide a by b. MOD gives you just the remainder, DIV gives you the integer part before the remainder (aka the ‘quotient‘). So 12 DIV 10 = 1. Or in CFML:
<cfset x = 12 \ 10>

Then gradually build up the string based on what number we have for each of the thousands, hundreds, tens and units. We need to make a special exception for the numbers between eleven and nineteen, because we don’t write them as ‘ten one’, ‘ten two’ etc.

Then I strip out the spaces, store this in a separate array, loop through that array and add up the lengths. This last step could be done in a variety of simple ways. There’s no real advantage to me using the array, I could just have easily ditched that array and second loop, and just made the last line inside my main loop
<cfset sum = sum + Len(REReplace(numberAsString, “[[:space:]]”, “”, “ALL”))>

1 Comment »

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

    Pingback by Project Euler: problem 17 (PHP) | Duncan's blog — October 2, 2014 @ 8:01 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

Create a free website or blog at WordPress.com.

%d bloggers like this: