Project Euler problem 58

Problem 58:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

This problem has some similarities to problem 28. In that case the spiral went clockwise; this one it goes anti-clockwise. For our purposes that’s a red herring.

We want to loop round, calculating the value for the corners of our spiral.
For each value, work out if it is prime (re-using the IsPrime function I first used back in problem 3).
Keep count of how many primes there are.
Also keep track of how long the side of our spiral is.
At each loop round the spiral, check if the ratio of primes / length is less than 10%.

<cfset numPrimes = 0>
<cfset length = 1>
<cfset number = 1>
<cfset increment = 2>
<cfset ratio = 100>

<cfloop condition="ratio GT 10">
	<cfset length += 2>

	<!--- add our increment 4 times, calculating each time if it's prime --->
	<cfloop index="i" from="1" to="4">
		<cfset number += increment>

		<!--- the 4th corner is never prime --->
		<cfif i LT 4 AND IsPrime(number)>
			<cfset numPrimes++>
		</cfif>
	</cfloop>

	<cfset ratio = numPrimes / ((2*length)-1) * 100>

	<cfset increment += 2>
</cfloop>

<cfoutput>#length#</cfoutput>

<cfscript>
function isPrime(x)
{
	var isPrime = true;
	var i = 0; 

	if (x LT 2)
	{
		return false;
	}

	if ((NOT x MOD 2) AND (x GT 2))
	{	// a multiple of 2, but not 2 itself
		return false;
	}

	for (i = 3; i LTE SQR(x); i = i + 2)
	{
		if (NOT x MOD i)
		{	// found a factor of x
			return false;
		}
	}

	return isPrime;
}
</cfscript>

Like in problem 28, we can see the corner values go:
3, 5, 7, 9, [increment: 2]
13, 17, 21, 25, [increment: 4]
31, 37, 43, 49 [increment: 6]
etc.

So we can work out the corner values by starting at 1, adding 2 to our increment each time round the spiral, then adding the increment four times to calculate the corners.

We don’t need to work out if the 4th corner is prime; it will always be a square number. e.g. on spiral with length 3, the 4th corner is 3² = 9. On length 5, the 4th corner is 5² = 25, and so on. So the if statement <cfif i LT 4 AND IsPrime(number)> will only execute the IsPrime() function if i LT 4 evaluates to true.

Project Euler problem 44

Problem 44:

Pentagonal numbers are generated by the formula, P_n=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference is pentagonal and D = |P_k − P_j| is minimised; what is the value of D?

I’d originally made a start on this in Python, then gave up on it. Came back to it much later and tried doing it in ColdFusion. My solution there took too long to run, so I went back to my Python version and finished it off.

Here’s the code:

import math

def pentagonal(x):
	return x * (3 * x - 1) / 2

def isPentagonal(x):
        n = (math.sqrt((24 * x) + 1) + 1) / 6

        if n == int(n) and n > 0:
                return 1
        else:
                return 0

i = 0
pentagonals = []
solution = 0

while 1:
        i += 1
        p = pentagonal(i)

        for j in pentagonals:
                diff = abs(p - j)

                if isPentagonal(diff) == 1:
                        intSum = p + j

                        if isPentagonal(intSum) == 1:
                            print("solution:", int(diff))
                            solution = 1
                            break

        if solution:
                break

        pentagonals.append(p)

The formula for calculating the pentagonal numbers is given to us. I already had a formula for the reverse, checking if a number is pentagonal, from problem 45.
To calculate the square root, I needed to import the math library.

Basically I loop until I find a solution. I calculate the pentagonal value of i. Then I subtract each pentagonal number smaller from it (but use the abs() function to get the absolute value).
If that difference is pentagonal, then I do a sum as well.
If that is also pentagonal, then our solution is the difference.
As I go along I append each pentagonal number into the array.
This solution runs in about 12 seconds for me.

Project Euler problem 55

Problem 55:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

Yet another problem which was easy to code in ColdFusion, but it couldn’t deal with the large numbers generated. So rewrote it in Python.

Just for interest, here’s what I did in CFML. NB: there’s a logic error here, which I fixed once I moved to Python:

<cfscript>
function isPalindrome(x)
{
	if (x EQ Reverse(x))
		return true;
	else
		return false;
}
</cfscript>

<cfset Lychrel = ArrayNew(1)>

<cfloop index="i" from="1" to="9999">
	<cfset k = i>

	<cfloop index="j" from="1" to="50">

		<cfset temp = k + Reverse(k)>

		<cfif IsPalindrome(temp)>
			<cfoutput>#k# + #Reverse(k)# = #temp#</cfoutput><br>
			<cfset ArrayAppend(Lychrel, i)>
			<cfbreak>
		</cfif>

		<cfset k = temp>
	</cfloop>
</cfloop>

<cfoutput><strong>#ArrayLen(Lychrel)#</strong></cfoutput>

Running this it quickly throws an error:
‘The value 210+E11200002108.1 cannot be converted to a number.’

Python doesn’t seem to have a built-in Reverse function like ColdFusion, so you have to write your own.

def Reverse(x):
        num = str(x)
        newnum = ''

        for i in range(len(num)-1, 0, -1):
                newnum += num[i]

        newnum += num[0]

        return newnum

Lychrel = []
limit = 10000

for i in range(1, limit):
	k = i

	for j in range(50):
		temp = k + int(Reverse(k))

		if str(temp) == str(Reverse(temp)):
			break

		k = temp

	if j == 49:
	      Lychrel.append(i)

print(len(Lychrel))

This code is pretty fast, but it could be better. For instance I’m casting everything to a string or an int as required, but that could maybe be tidied up somehow.
Also in my Reverse function, I somehow couldn’t work out how to properly loop backwards through the string, so ended up having to add on the first character outside of the loop.

Initially I was appending to my Lychrel array at the point where I break out of the loop. However on reading the question again I realised the Lychrel numbers are the numbers which aren’t solved within 50 iterations, not the other way around. I don’t even need an array, I could just have a counter that I increment. But having it in the array gives us the advantage of being able to output the array contents to make sure we’re on the right track.

Coldfusion and XML – an introduction

I was doing a bit of investigation into XML in ColdFusion. This is pretty simple stuff, but I didn’t really see any good information about this on the web, so thought it would be worth blogging, as much for my future reference as anyone else’s.

<CFSaveContent> versus <CFXML>

There are various ways of creating XML in ColdFusion. The two simplest ways are cfsavecontent and cfxml.
Method 1 – CFSaveContent:

<cfsavecontent variable="myXML_1">
<country>
	<name>United Kingdom</name>
	<population>61,113,205</population>
	<capital>London</capital>
</country>
</cfsavecontent>

Method 2 – CFXML:

<cfxml variable="myXML_2">
<country>
	<name>United States</name>
	<population>307,212,123</population>
	<capital>Washington, DC</capital>
</country>
</cfxml>

Look almost identical, right? There’s a difference though. CFSaveContent returns a string. CFXML returns a ColdFusion XML object. What’s the difference? Firstly, try outputting both variables.

Variable 1:

<cfoutput>
#HTMLEditFormat(myXML_1)#
</cfoutput>

<country> <name>United Kingdom</name> <population>61,113,205</population> <capital>London</capital> </country>

Variable 2:

<cfoutput>
#HTMLEditFormat(myXML_2)#
</cfoutput>

<?xml version=”1.0″ encoding=”UTF-8″?> <country> <name>United States</name> <population>307,212,123</population> <capital>Washington, DC</capital> </country>

As you can see, the CFXML example has got an XML declaration prepended onto it ( <?xml version=”1.0″ encoding=”UTF-8″?> ). If you were using CFSaveContent you’d usually have to add this in yourself. But that’s not the only difference. This time try dumping out the variables:

<cfdump var="#myXML_1#">

<country> <name>United Kingdom</name> <population>61,113,205</population> <capital>London</capital> </country>

Dumping the first variable is identical to outputting it, because all you have is a string.

<cfdump var="#myXML_2#">

Dumping out the variable created with CFXML displays a bit like a structure. [If you click the part that says "xml document" it changes to the 'long version'. Clicking it again hides the cfdump content.]

So we’ve established the difference, but what advantage does one method have over the other? Because the first variable is just a string, you can put anything you like in there, including invalid XML. However if you try doing that with CFXML, it’ll throw an error (which is a good thing, as you don’t want to accidentally be using something invalid, right?)

XMLParse()

Any time you’re working with XML in ColdFusion, you’ll probably come across the XMLParse function. This takes a block of XML and turns it into an XML object. If you used CFSaveContent, then passed it into XMLParse, you’d get back an object identical to what you’d get if you’d just used CFXML.

You can also pass in an XML object to XMLParse, and it won’t change it. In other words, regardless of if your variable came from CFSaveContent or CFXML, calling XMLParse on it will return the same object.

If you’re getting some XML from anywhere other than CFXML, you probably always want to call XMLParse() on it to turn it into an XML object. If the XML is invalid, it’ll throw an error. You can also pass in a path to a DTD or XML Schema to validate it further.

Functions

When you declare a function in ColdFusion, you can specify an optional returntype attribute. This determines what type of variable is returned from your function (or ‘void‘ if nothing is returned).

When your function is returning XML, you can set returntype=”string” or returntype=”XML” (or returntype=”any”, but that’s a whole other discussion).
If your function is using XMLParse or CFXML to create an XML object, it doesn’t matter if you specify string or XML, it will always return as an XML object.
If you’re using CFSaveContent to create your XML as a string, you can still specify either string or XML, and it will return your XML as a string.
So in other words, regardless of which returntype you use, the variable that’s returned is of a type that matches how it’s created (a string if using CFSaveContent; an XML object if using CFXML).

However if you specify returntype=”XML”, it has to be valid XML, or it will throw an error.

If your function is returning XML to anything other than ColdFusion, e.g. as a webservice, then you want to return it as a string, not an XML object. I’d recommend still using returntype=”XML”, and CFXML to create it (therefore forcing you to create valid XML), but then call ToString() on it when returning.

You probably also want to specify output=”false” (which is good practice most of the time anyway) to avoid getting any extra whitespace appearing at the start of your XML object.

Arguments

Similarly, if you are passing in some XML as a function argument, you can specify type=”string” or type=”XML”. Again, regardless of whether your XML came from CFSaveContent (or elsewhere) as a string, or CFXML / XMLParse() as an XML object, either type=”string” or type=”XML” will be fine. However if you specify type=”XML”, the argument must be valid XML.

If you specify type=”XML”, but it’s an optional argument, I’d recommend doing it like so:

<cfargument name="myXML" type="XML" required="false">

Typically you often see in code default=”" on non-required cfarguments. However it’s not best practice, and if using type=”XML” will thrown an error. If you really need to specify the default attribute, put in a valid bit of XML, e.g.

<cfargument name="myXML" type="XML" required="false" default="<foo>bar</foo>">

Summary

• Use CFXML instead of CFSaveContent; you won’t have to specify an XML declaration, and it will only work with a valid XML packet
• CFSaveContent is just a string, so it doesn’t have to be valid XML
• Use type=”xml” on the argument, even if the value you pass in is a string. It will only accept a valid XML packet
• If the value could come from anywhere other than CFXML, use XMLParse() to turn what will be a string into a ColdFusion XML object
• You can use XMLParse() even on a valid XML object (it won’t change it)
• Even with returntype=”string” if you use CFXML it will return a ColdFusion XML object
• If you might be returning data to something other than ColdFusion, you would need to turn it into a string first using ToString()

2009 goal review – summer

I decided this year to publish some personal goals and then review them quarterly. I didn’t manage to do my summer review when I’d originally intended, due to the complication involved in moving from Scotland to London. So here it is now, better late than never.

Experts Exchange : get one more Master ranking, and improve both Coldfusion Markup Language and ColdFusion Application Server to Guru level.
Half-done; I managed to get those two CF zones up to Guru, but don’t have another Master ranking yet. Haven’t been active on Experts Exchange since I decided I was moving to London and realised I’d be too busy over the coming weeks. Might get back into it now though.

Join the gym.
When I moved down here I thought I’d do this, and had a one day trial at a local gym. However I’ve decided not to bother for now. I have been doing a bit of running though, and my goal is to try and average two runs a week.

Start using some kind of source control.
When I set myself this goal, I’d originally thought I’d have to do this for my personal projects, due to little chance of seeing it being implemented at work. However at my new company I use Subversion every day.

Complete 40 of the Project Euler problems.
I completed my original goal to do 25 of these, and revised it to complete 40. At the time I’d done 33, and I haven’t made any progress since then.

Blog at least once a week on average. I’d also like to do more Coldfusion-related blog posts.
When I moved to London I was offline for about six weeks, so I’ve fallen behind on this, but hope to get back on schedule.

Get involved in something open source.
No progress.

Install and start using Railo.
No progress.

Start using MySQL.
No progress.

Police considering Chinese-style spying measures for 2012 Olympics

Worrying article in the Sunday Times: “Spy bugs may be deployed for 2012 Olympics“.

The police have looked at how the Chinese conducted their surveillance for the last Olympics, and are considering re-using some of their ideas. Such as:

• bugging taxis to listen in to any incriminating conversations
• using microchips on tickets and passes to track the movements of athletes, journalists and spectators
• facial recognition CCTV

What I find most frightening is the final line:
“Alan Campbell, the Home Office minister, has revealed that the Home Office is investigating technology that would allow police to halt a vehicle remotely“

Does anyone seriously consider that might be a good idea? Especially in the hands of the Metropolitan Police, or any other police force in this country.

Thanks to OurWorld OurSay for tweeting this originally.

---

Photo from surfstyle’s Flickr stream. Creative Commons license.

How not to do input validation

Here’s a screenshot from a form I was filling in on the TV Licensing website. I’d just entered the date as 9/6/2009 instead of 09/06/2009. Obviously it’s too tricky for them to work out how to pad 1-digit numbers with a leading zero.

This falls into the same category as sites that insist you enter your username in either lower or upper case. Or that you enter your credit card without spaces or hyphens. Or that you format your phone number in a particular way.

It’s all putting extra work on the user for something that could be done automatically server-side with just a few lines of code at most. Not good practice!

Fife Council publishes councillors’ expenses

Fife Council recently published “Councillors expenses for 2008/09″ [sic]. Although this is never going to be as exciting as recent revelations about MPs’ expenses, or even MSPs’ expenses, it is maybe still worth analysing a bit. If you download the Excel file of expenses, you’ll see it’s been formatted for print, with the page header repeated about half-way down, presumably where the page break occurs. For some reason, in Open Office, the council logo is reversed.

Anyway, rather than try and read through a spreadsheet of numbers, I’ve tried graphing some of the data.  Please click on the graphs to see each fullsize.

Salary
Since the last local authority elections in 2007, councillors have received a salary and not just expenses. Heads of committees, the provost, etc. receive a higher salary.

For some reason Margaret Kennedy received a marginally smaller salary than her colleagues; £15,445.24 instead of £15,785.73.

Travel Expenses
This first graph shows all councillors. You can see the long tail effect, with several councillors claiming zero travel expenses. These travel expenses do not include rail, air or taxi fares. The mileage rate is 40p per mile, reduced from 49.3p.

Unfortunately Google Docs saves the image without all names visible. So this second graph shows just the top 30 names.

Gerald McMullan and Tim Brett clearly have higher claims than anyone else, at least £1000 more than the third highest.

For Councillor McMullan to claim £6993.64 in travel expenses, at 40p per mile, he must have driven 17,484.1 miles in a year. I’ve no idea if that is reasonable. He lives in Crossford, approximately 24 miles from Glenrothes. If we divide 17,484.1 by 48, we get 364.252083. In other words, if he was only doing the return drive from his council ward to the council headquarters, he’d have to make that journey every day for a year to justify his travel expense claim. However he must do lots of other mileage besides, e.g. driving round to various locations in his ward. I’d still be interested to find out more about exactly what mileage he claimed for. For example if we could see his daily mileage claims instead of just an annual total.

ICT Expenses
Only 8 out of 78 councillors claimed any ICT expenses. The spreadsheet says “Communication and IT Costs, Mobile Phone Costs and Provision of Council Cars borne by Fife Council is not generally a cost incurred directly by individual Councillors.” I’m therefore unsure what William Walker managed to claim £670 pounds for. If full receipts were published this would clear things up.

Rail / Air / Taxis / Hotels
Less than a third of councillors claimed for this.

You would expect the council Leader Peter Grant to have the highest claim, on the assumption he’s representing the council at national and international events. Second highest is Mike Rumney (listed as Robert Rumney on the spreadsheet), with a claim of £1,241.31. Again, without more information, it’s impossible to tell how this money was spent.

Total expenses
Again, Google Docs produces an image without all names visible:

And here’s the top 30 names. Gerry McMullan clearly with the highest expense claims due almost entirely to his high travel expenses.

Kirkcaldy swimming pool opening hours

Update: I just discovered that Kirkcaldy Swimming Pool actually publish another leaflet with contradictory times to their Opening Times leaflet: Activity Programme 2009 (PDF). I’ve emailed them for clarification. Until I get it, assume the information below is possibly incorrect.

I was trying to work out the times I could go for a swim at Kirkcaldy Swimming Pool. They publish the opening times (PDF) but it’s not immediately clear when is normal swimming and when does that clash with lessons / aquaerobics / family fun / lane swimming.

So I’ve attempted to re-publish them in a different format, so you can hopefully see what’s on at any time. This information will probably get out of date within a few months, especially when they start building the new pool.

Key:

	Normal swimming
	Adult lane swimming
	Swimming lessons
	Aquaerobics
	Family fun session (last Sunday of the month)

	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday	Sunday
8.00
8.15
8.30
8.45
9.00
9.15
9.30
9.45
10.00
10.15
10.30
10.45
11.00
11.15
11.30
11.45
12.00
12.15
12.30
12.45
13.00
13.15
13.30
13.45
14.00
14.15
14.30
14.45
15.00
15.15
15.30
15.45
16.00
16.15
16.30
16.45
17.00
17.15
17.30
17.45
18.00
18.15
18.30
18.45
19.00
19.15
19.30
19.45

The worst thing in the world

I don’t know what your opinion is of torture, but personally I’m against it. The US Government has published some secret memos detailing the legal justification for their torture enhanced interrogation techniques used by the CIA in the ‘war on terror‘. Mostly these are just self-serving legalistic jargon explaining why the end justifies the means.

The techniques range from relatively mild (slaps to the face or abdomen, shoving captives against a wall) to the extreme (sleep deprivation, prolonged stress positions, water boarding).

The first of these memos (PDF) has the following section:

In addition to using the confinement boxes alone, you also would like to introduce an insect into one of the boxes with Zubaydah. As we understand it, you plan to inform Zubaydah that you are going to place a stinging insect into the box, but you will actually place a harmless insect in the box, such as a caterpillar. If you do so, to ensure that you are outside the predicate act requirement, you must inform him that the insects will not have a sting that would produce death or severe pain. If, however, you were to place the insect in the box without informing him that you are doing so, then, in order to not commit a predicate act, you should not affirmatively lead him to believe that any insect is present which has a sting that could produce severe pain or suffering or even cause his death. [censored] so long as you take either of the approaches we have described, the insect’s placement in the box would not constitute a threat of severe physical pain or suffering to a reasonable person in his position. An individual placed in a box, even an individual with a fear of insects, would not reasonably feel threatened with severe physical pain or suffering if a caterpillar was placed in the box.

Does that remind you of anything? The following excerpts are from George Orwell’s Nineteen Eighty-Four:

‘The worst thing in the world,’ said O’Brien, ‘varies from individual to individual. It may be burial alive, or death by fire, or by drowning, or by impalement, or fifty other deaths. There are cases where it is some quite trivial thing, not even fatal.’
…
‘In your case,’ said O’Brien, ‘the worst thing in the world happens to be rats.’
…
‘By itself,’ he said, ‘pain is not always enough. There are occasions when a human being will stand out against pain, even to the point of death. But for everyone there is something unendurable–something that cannot be contemplated. Courage and cowardice are not involved. If you are falling from a height it is not cowardly to clutch at a rope. If you have come up from deep water it is not cowardly to fill your lungs with air. It is merely an instinct which cannot be destroyed. It is the same with the rats. For you, they are unendurable. They are a form of pressure that you cannot withstand, even if you wished to. You will do what is required of you.’