# Geometry

## HackerRank: Minimum Height Triangle

It is always fun to work with triangles in any kind of setting not least problem solving in HackerRank. The problem Minimum Height Triangle is no exception. The problem reads

Given integers b  and a, find the smallest integer h, such that there exists a triangle of height h, base b, having an area of at least a.

In case we should have forgotten the primary school mathematics. The area of a triangle is given by

This can be isolated such that we get the height of the triangle instead as

Since we want the minimum integer size we then need to ceil that such that we get

This can be implemented in Python as

def lowestTriangle(base, area):
return math.ceil(2 * area / base)


I usually write somewhat longer posts. But to be honest, I don’t know what to add to this problem.

Posted by Kristian in HackerRank, 0 comments

## HackerRank: Find the Point

I finally found the math problems on HackerRank which makes me so happy. So let’s getting cracking on the first one called Find the Point. It asks us to

Consider two points,  and . We consider the inversion or point reflection, of point  across point   to be a  rotation of point  around .

Given  sets of points  and , find  for each pair of points and print two space-separated integers denoting the respective values of  and  on a new line.

## Project Euler 144: Investigating multiple reflections of a laser beam.

Problem 144 of Project Euler is once again a geometry problem, just like the previous. However, it is completely different. The problem reads

In laser physics, a “white cell” is a mirror system that acts as a delay line for the laser beam. The beam enters the cell, bounces around on the mirrors, and eventually works its way back out.

The specific white cell we will be considering is an ellipse with the equation 4x2 + y2 = 100

The section corresponding to -0.01  x  +0.01 at the top is missing, allowing the light to enter and exit through the hole.

The light beam in this problem starts at the point (0.0,10.1) just outside the white cell, and the beam first impacts the mirror at (1.4,-9.6).

Each time the laser beam hits the surface of the ellipse, it follows the usual law of reflection “angle of incidence equals angle of reflection.” That is, both the incident and reflected beams make the same angle with the normal line at the point of incidence.

In the figure on the left, the red line shows the first two points of contact between the laser beam and the wall of the white cell; the blue line shows the line tangent to the ellipse at the point of incidence of the first bounce.

The slope m of the tangent line at any point (x,y) of the given ellipse is: m = -4x/y

The normal line is perpendicular to this tangent line at the point of incidence.

The animation on the right shows the first 10 reflections of the beam.

How many times does the beam hit the internal surface of the white cell before exiting?

Posted by Kristian in Project Euler, 12 comments

## Project Euler 143: Investigating the Torricelli point of a triangle

Problem 143 of Project Euler is a notorious problem. Notorious for having the fewest correct answers per time it has been released. If you sort by number of solvers, you will see a pretty good correlation between problem number and place on that list. However, this problem is moved quite a bit down that list. The problem reads

Let ABC be a triangle with all interior angles being less than 120 degrees. Let X be any point inside the triangle and let XA = p, XB = q, and XC = r.

Fermat challenged Torricelli to find the position of X such that p + q + r was minimised.

Torricelli was able to prove that if equilateral triangles AOB, BNC and AMC are constructed on each side of triangle ABC, the circumscribed circles of AOB, BNC, and AMC will intersect at a single point, T, inside the triangle. Moreover he proved that T, called the Torricelli/Fermat point, minimises p + q + r. Even more remarkable, it can be shown that when the sum is minimised, AN = BM = CO = p + q + r and that AN, BM and CO also intersect at T.

If the sum is minimised and a, b, c, p, q and r are all positive integers we shall call triangle ABC a Torricelli triangle. For example, a = 399, b = 455, c = 511 is an example of a Torricelli triangle, with p + q + r = 784.

Find the sum of all distinct values of p + q + r ≤ 120000 for Torricelli triangles.

Posted by Kristian in Project Euler, 4 comments

## Project Euler 126: Exploring the number of cubes required to cover every visible face on a cuboid.

Problem 126 of Project Euler is a really awesome geometric challenge. It reads

The minimum number of cubes to cover every visible face on a cuboid measuring 3 x 2 x 1 is twenty-two.

If we then add a second layer to this solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.

However, the first layer on a cuboid measuring 5 x 1 x 1 also requires twenty-two cubes; similarly the first layer on cuboids measuring 5 x 3 x 1, 7 x 2 x 1, and 11 x 1 x 1 all contain forty-six cubes.

We shall define C(n) to represent the number of cuboids that contain n cubes in one of its layers. So C(22) = 2, C(46) = 4, C(78) = 5, and C(118) = 8.

It turns out that 154 is the least value of n for which C(n) = 10.

Find the least value of n for which C(n) = 1000.

Posted by Kristian in Project Euler, 9 comments

## Project Euler 102: For how many triangles in the text file does the interior contain the origin?

Problem 102 of Project Euler asks us the following question

Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ xy ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

Using triangles.txt  a 27K text file containing the co-ordinates of one thousand “random” triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.

Posted by Kristian in Project Euler, 15 comments

## Project Euler 94: Investigating almost equilateral triangles with integral sides and area.

I can realy feel that the problems become harder and harder. Problem 94 of Project Euler took me a good while to figure out. The problem is easy to understand and reads

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the
5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

Posted by Kristian in Project Euler, 25 comments

## Project Euler 86: Exploring the shortest path from one corner of a cuboid to another.

Problem 86 of Project Euler is more of a geometric problem than most of what I have seen here. It requires one insight and then it is fairly straight forward to solve. An insight I am just about  to give you, but let’s start with the problem formulation

A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest “straight line” distance from S to F is 10 and the path is shown on the diagram.

However, there are up to three “shortest” path candidates for any given cuboid and the shortest route is not always integer.

By considering all cuboid rooms with integer dimensions, up to a maximum size of M by M by M, there are exactly 2060 cuboids for which the shortest distance is integer when M=100, and this is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions is 1975 when M=99.

Find the least value of M such that the number of solutions first exceeds one million.

The insight we need in order to proceed is how to calculate the shortest path. Once we figure that out the rest should be pretty forward. Continue reading →

Posted by Kristian in Project Euler, 20 comments

## Project Euler 85: Investigating the number of rectangles in a rectangular grid

And now for something completely different.. or maybe as we will see later Problem 85 of Project Euler offers us a new problem where we can use the same ideas as for the solution to a previous problem. To lets start out with the problem text:

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.

A nice and short problem text. I have found two possible solutions for the problem, one using brute force and the other applying some combinatorics to find an analytical solution to the number of rectangles that we have for a given size. Continue reading →

Posted by Kristian in Project Euler, 16 comments

## GeoGebra – a cool geometric tool

At work I use many fairly advanced tools that can do a lot of things such as Matlab, which in all it’s glory is a very nice tool. However, for things such as Project Euler which does contain small problems, where I try to get a feeling for the problem in a whole other sense than I usually do Matlab is not very good, let alone that I could never afford it for private use.

I have been pointed towards a tool called GeoGebra which is a free tool written in Java, where you can manipulate lots of different geometric objects such as functions, points and lines. You can also use tools such as intersection and getting the slope shown. You can even define your own tools if you like.

I think it has been made as a teaching tool for high school students, but I have been playing around with it for a short while now and I can definitely see some useful things in it when I try to grasp a problem. It wont work on abstract problems, but small geometric problems will be a thrill to work with from now on.

It promotes it self as

GeoGebra is free and multi-platform dynamic mathematics software for all levels of education that joins geometry, algebra, tables, graphing, statistics and calculus in one easy-to-use package. It has received several educational software awards in Europe and the USA.

The best thing about the tool is the readily available material. There are a tutorial and manual right at the GeoGebra help site, there are tons of You tube videos from GeoGebra let alone the ton of user made videos and there is the user forum.

Math and Multimedia has a list of the 10 best tutorials for the tool to get you started. and GeoGebra Applet Central has some applets which shows the use of different parts of GeoGebra and I especially like the applet showing how to approximate Pi by increasing the number of sides in a polygon inscribed in a circle.

I am very impressed so go ahead and take a look at it at GeoGebra. You will definitely see some illustrations from me using this tool in the future, since it is so easy to illustrate the functions and so on.

Posted by Kristian in Math, 7 comments