Duncan's blog

November 3, 2008

Project Euler: problem 42

After completing problem 22, I spotted this one that looked quite similar.

Problem 42:

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

So, reusing most of the code from problem 22, the only new bit of functionality we need to worry about is how to determine if a number is a triangular number. The Wikipedia gave me the formula needed. An alternative way would have been to just calculate a list or array of all the triangular numbers up to some limit, then check if each word’s value is in that list.

<cffile	action="read" 
	file="#GetDirectoryFromPath(GetCurrentTemplatePath())#words.txt" 
	variable="wordsFile">

<cfset words = ArrayNew(1)>
<cfset total = 0>

<!--- transfer names into an array --->
<cfloop index="i" list="#wordsFile#">
	<cfset ArrayAppend(words, ReplaceNoCase(i, '"', '', 'ALL'))>
</cfloop>

<cfscript>
function isTriangle(x)
{
	var n = (SQR((8 * x) + 1) - 1) / 2;
	
	if (n EQ Round(n))
	// it's an integer
		return true;
	else
	// it's not an integer, therefore not a triangle number
		return false;
}
</cfscript>

<cfloop index="i" from="1" to="#ArrayLen(words)#">
	<cfset sum = 0>
	
	<cfloop index="j" from="1" to="#Len(words[i])#">
		<cfset sum = sum + Asc(Mid(words[i], j, 1)) - 64>
	</cfloop>
	
	<cfif isTriangle(sum)>
		<cfset total = total + 1>
	</cfif>
</cfloop>

<cfoutput>#total#</cfoutput>

Again, I’m making the assumption that all letters are uppercase, so I can simply subtract 64 from each letter’s ASCII value to get it transformed into a 1-26 range.

1 Comment »

  1. […] numbers, mathematics, maths, pentagonal numbers, Project Euler, triangle numbers After completing problem 42, which required checking if a number was a triangular number, this problem was a natural […]

    Pingback by Project Euler: problem 45 « Duncan’s blog — November 4, 2008 @ 7:16 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: