LUMS | LUMS CS Dept.
Home |

the Thinking Code Monkey

ProjectEuler.net

I love this site!! Anybody who wants to think over mathematical problems and solve them by code, this site was made for you. Or if you are too good, you can compute these problems on paper 'n' pencil, but then God will only help you when you try to compute the 10001st prime! Many, many such challenging problems, can addict you for hours on stretch. These problems are also quite different from what you would find, on lets say, acm.uva.es, as all problems just give you a mission statement from any area of mathematics and the answer is just meant to be filled down in a textbox. No code submission! No time spent on thinking about strange boundary cases. I'll be now and then writing about problems I found really hard on ProjectEuler, in hope you'll get hooked on too :)

Problems solved: 58 / 187 .... 31% genius :( . Haven't found time to waste lately in order to think on a problem :(

Top

ProjectEuler.net - Problem 163 - Cross-hatched triangles

Somewhere back in December of 2007, I wanted to solve the hardest problem in ProjectEuler's arsenal. There is a very objective way to make that choice: ProjectEuler offers statistics of how many people have solved a certain problem. So sorting that row, I picked the one solved by the least number of people....and at that time it turned out to Problem 163. Only around 80 odd people had solved it at that time. At first go, it looked quite daunting (read the problem statement), but there is an easy way to solve it. Read on for learning the method I used.

The biggest difficulty in solving this problem is that you can't make all possible triangle shapes in the figure given. You'll need to look at a bigger set of triangles, where all triangles become more evident. But first things first. You need to identify how many unique corners are there where an apex of a triangle can fall. For finding this, of course, you will need to look at two adjacent triangles. So the lower figure gives you all the possible 6 points. Note that there are 5 other points in the figure, but they are simply repeats from the set of chosen 6:

Problem 164 - Points of consideration

After identifying these 6 points, you will need to grab a big sheet of paper, and draw rows upon rows of these cross-hatched triangles. Then draw all possible triangle shapes that can occur. But before you do this its important to follow some sequence, otherwise you will end up missing one triangle or the other. Remember, we are looking for possible triangle shapes, and not the total set of triangles themselves (doing that will drive you mad!). Secondly, every time you think you have a new triangle shape, look at the triangles chosen before and check if you are not re-choosing a triangle before you make your decision.

There is a certain sequence I followed. First I choose any apex point among the 6 decided on. Then we choose the width of the triangle from the apex, given by the number of lines that fall between the two connecting sides of the apex. Third, we choose a direction of spread of the triangle (we'll eventually mark all similar triangles to the triangle shape chosen). For example, apex point 1 has a total of 12 direction spreads, if you consider a width of one for it (a width of 1 in my terminology, doesn't contain any lines in-between the apex edges). Last, but not the least, we see how many different triangles can come out from that apex, with the chosen width and the chosen direction. Look at the two figures below (click on them to enlarge). They contain all the possible smallest triangle shapes that can occur in cross-hatched triangles (apart from those occurring in a single unit of equilateral triangle and those occurring across an intersection of 2 triangles). The numbering I follow is [<Apex Point no.><Width from Apex><Direction from Apex><the Triangle No.>] :

Possible Triangles 1 Possible Triangles 2

You should note that I skipped about half of the triangle shapes! This is simply because I considered just half of the directions from the apex, since all triangles have a reflection along the y-axis (un-less the triangle is an isosceles across the y-axis), and we simply solve this by multiplying the number of triangles by 2 where-ever required.

Firstly we'll count all the 16 triangles for a each unit of equilateral triangle. After that we'll mark all triangles that are between two triangles' intersection, with one inverted one in-between (ignore the triangles in a single unit equilateral triangle since we have already counted them). Look at the diagram below to which depicts this intersection. The triangles occurring here turn out to be 21 (look at the figure below). Counting all the intersections on all the Levels, we'll multiply it by 21 triangles (by Level, I mean just a row of triangles, which are denoted by different coloring in the diagram)

Two trianlge intersections

After that we need to see which triangle shapes spans across more than a row Level of triangles (like11aa, 11ab, 11ac, among many others) and which can still inherently fit in a single level (like 11ea, 11db, and so on). We'll call them Type A, and Type B respectively. Remember these are the smallest shape of the triangles. In our code we'll count all the similar triangle for a certain shape of triangle. So first at the lowest base row Level, we'll count just Type B triangles. Once we have counted at the base Level, at all the above Levels we'll count both Type A and Type B triangles, until we reach the top Level. One last thing to note: the smallest form of 41aa and 61aa shouldn't be counted as they have been already accounted for while counting the triangles in the intersections.

C code for Problem 163

Top

Thinnest Mountain Problem

I came across the problem while refining our motion tracker algorithm in AVRiL. This in no way compares to the amount of brain I consumed for the Cross-hatch problem :). But nonetheless, its still an important problem. Before I even dig into the problem statement, tune your mind to think about bars on a graph, cause this problem exactly deals with that. Of course bars on a graph can be simply denoted by the So this is the exact problem statement:

The thinnest mountain problem states that given an array of numbers (think of it as a bar graph), where is the shortest span in the array where the sum of values reach at least a given sum. A span in an array is simply a contiguous set of values.

Now that I have stated the problem, look at the graph below showing possible values for an array. The problem is to find the contiguous part in the graph where the sum of the values of the bars are at least a given value:

Thinnest Mountain Graph

The first step is to put a marker at both ends of the graph, and then decrease the rightmost marker until it stops fulfilling the minimum sum criteria. Then we need to move the leftmost / stating marker forward until it too stops fulfilling the minimum sum criteria. This will give us the leftmost minimum span mountain:

Thinnest Mountain Step1

The second step is extremely crucial. In fact this is the iterative step which will eventually give you the thinnest mountain having a minimum sum. Here, in every step, you move the spanning blue window forward to check if the sum criteria is met. If it is, then you attempt to thin the mountain further by moving the starting left marker forward as long as the sum criteria keeps being met. Every time you thin the mountain, that becomes your possible answer. In all further steps you'll try to find the sum criteria in the thinnest span you have found. This will ensure that you don't look at spans fulfilling the sum criteria which are too wide to be the thinnest. In case at a certain step the sum criteria is not met, we simply move forward, by advancing the starting and ending markers:

Thinnest Mountain Step 2

As said before, you'll finally arrive at a contiguous span where your mountain is the thinnest. This will eventually form your final answer, but you can't be sure until you have traversed the whole array. Note that our span is now of 5 bars/values:

Thinnest Mountain Step 3

Moving till the end with a 5 bar span, we try to search for any areas having an even thinner mountain. If not, then the last thinnest span found forms the solution.

Thinnest Mountain Final Step

There are 2 more things to note. 1. The highest value is not necessarily in your solution (like in the example above). 2. there can be multiple solutions to the problem....look at the code to adjust if you either want the first or the last occurring thinnest mountain:

C++ code for the Thinnest Mountain Problem
Adjust the CRITERIA_FRACTION to set the minimum sum criteria (here it is taken as a fraction of the sum of all values)

Top

Primes Generator

C code for dealing with Prime Numbers

The functions in this code are ones I use for solving problems in ProjectEuler.net. There are a number of functions in it which are helpful when dealing with primes. One is the simplePrimesGenerator(). In the first argument given you simply tell it the limit till where the prime numbers should be generated. This function internally first creates prime sieve (a prime sieve is a data-structure which contains a list of numbers, where each prime is marked with a flag) which it uses to populate the primes array returned.

The second function simpleNoOfPrimesGenerator() is a bit involved in the sense, that it returns you at least (close to) the number of primes specified. This is not simple to do, since you somehow have to estimate the limit number till where you will at least have the number of primes you want. Lets say you tell this function that you need 5 primes. The function will need to somehow estimate that the prime sieve that needs to be generated, should at least contain numbers till 11 (which is the 5th prime). This function is used when you require a given number of primes, although it will usually return you more primes, due to estimation errors. This technique is proved through the Prime Number Theorem (PNT). Here is my approximation between the Prime-Counting Function and its estimation by x / ln(x). The fractional difference between the two just tapers off below 1.26

Differences Prime-counting Function and its Estimation

The function simpleSieveGenerator() is the fastest function amongst all (other functions usually use it). It uses techniques illustrated by John Moyer, where you embed the first few hundred primes in your code, and then use them to generate primes further. John Moyer's code is more efficient (faster and less-memory hogging) than mine, since he has hard-coded more primes in his implementation. If you use this function, the sieve array returned has to be used in conjunction with sieveIsPrime() to find if a given number is a prime.

And finally we have the dirty old rudimentaryIsPrime() which just computes if a number is a prime by brute-force.

Top

 
mail: ahmad.humyn@gmail.com | skype: ahmad.humayun | voice: +92 321 4457315