Project Euler – Problem 85

Yan Cui

I help clients go faster for less using serverless technologies.

Problem

By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

Solution

	open System
	let target = 2000000
	// function to work out the number of rects in a grid of x by y
	let getRectCount x y = (x * x + x) * (y * y + y) / 4
	// try x and y dimensions up to 100
	let answer =
	seq {
	for x in 2..100 do
	for y in 2..100 do
	// get the grid area and the difference to the target count in a tuple
	yield (x * y, Math.Abs(getRectCount x y - target))
	}
	|> Seq.minBy (fun (area, diff) -> diff)

view raw gistfile1.fs hosted with by GitHub

This problem looks more difficult than it is, I’m not going to go into the details here but basically the number of rectangles inside a x by y grid can be calculated as:

The rest is fairly easy, just pick a range of x and y values you want to try and brute force it!