#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 86
# Author: David J. Oftedal.
# Find the lowest maximum dimension for which there are more
# than one million cuboids with integer-length shortest paths
# from one corner to the opposite corner along the walls.
class Numeric
def approximate_integer?
(self - self.round).abs < 0.0000000000001
end
end
def count_integer_paths(max_a, max_count)
a = 1
count = 0;
#puts "Max\tCount" if $0 == __FILE__
loop do
asquared = a*a
# We'll be merging b and c later, so we'll generate them together to save time.
(1..2*a).each do |b_plus_c|
# A shortest path is one where the two parts form the hypotenuses of a
# right triangle when the cuboid is flattened so two sides are merged.
# We use Pythagoras to check the smallest of the three possible triangles,
# where the two smallest of the three sides have been merged.
if ((asquared + (b_plus_c)**2)**0.5).approximate_integer?
# Break b and c apart again, to count each cuboid that has an integer solution.
(a).downto(1) do |b|
c = b_plus_c - b
next if c < 1
break if c > b
count += 1
end
end
end
#puts a.to_s << "\t" << count.to_s if $0 == __FILE__
break if (max_a != nil && a >= max_a) || (max_count != nil && count >= max_count)
a += 1
end
return a, count
end
if $0 == __FILE__
a, count = count_integer_paths(nil, 1000000)
puts "The lowest maximum dimension M is " << a.to_s << ", with a count of " << count.to_s << "."
end
require "test/unit"
class Test086 < Test::Unit::TestCase
puts "\n"
def test_653
a, b, c = 6, 5, 3
assert(((a*a + (b+c)**2)**0.5).approximate_integer?)
end
def test_100
assert_equal(2060, count_integer_paths(100, nil)[1])
end
def test_99
assert_equal(1975, count_integer_paths(99, nil)[1])
end
end