Project Euler – Problem 12

The good lads at Project Euler present to me another brute force challenge! At least this will be easy to solve before I go to bed, albeit poorly and not optimized in the slightest.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Calculating the number of factors in any given number seems like a function that I will be requiring frequently throughout these problems so I decided to write a function for it in my Helper class. At the moment it is very slow and can be improved upon with prime factorization much like I’ve done in Problem 3 but I’m too tired at the moment to wrap my head around the concept again so this will have to do for now!

In my Helper class I added the following function:

The code is mostly straight forward to follow. It is important that we check for the square root of the number in this case instead of the full number however since I originally ran the program without the optimization in place before realizing it’s not going to complete within a reasonable time.

Calculating the triangle numbers in the Problem class was about as simple as it can get and by simply accessing the Helper function and using the following code I was able to process a solution to the problem in less than a second.

Honestly, I just wanted to knock off a problem for the day so I didn’t put too much effort into this like I should have so I may have to come back to this in the future and make it faster! That’s really all I have to say for now since it’s well past my bed time and I need to catch some ZZZzzz’s. Feel free to check out my GitHub for the full code solution and answers to these problems and other cool projects that I’m working on. Until next time good night, and sleep tight.

Project Euler – Problem 11

Like most problems we solve with programming  this could be solved by hand, but thank God we don’t have to do that or we might be sitting here all day!

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

This question is reminiscent of Problem 8 as it is essentially just a more complicated version of the same question. After some internal debating I decided upon not writing a function for this in the Helper class since I don’t believe there’s any part of this problem that can be extracted and repeated for later problems. I’ll just eat my own words if that’s not the case though.

No special math will be required to solve this problem, and upon inspection there doesn’t appear to be a faster method for solving the question other than brute-forcing our way through every possible combination of numbers. With that being said here is some code I threw together to get an answer in less than 2 milliseconds on my machine.

While there is a bit more code here than has been required for previous questions all of the logic is still very simple. Since the creators of the question weren’t kind enough to give me the numbers in a format that can be read from c# straight off the bat I had to write some code to enter the individual numbers into my 2-D array since there was no chance I was manually entering in all of those numbers.

Once I had the numbers in a format that I could easily work with it was just a matter of checking all of the combinations and finding the highest product that we come across. To do this I just created four different for loops to check for all vertically, horizontally, and diagonally adjacent numbers and did some simple math on them.

I honestly don’t know why I keep getting disappointed with these questions considering they are programming based and that obviously entails that they will be doing what computers do best (brute forcing large quantities of numbers), however I do hope to come across some questions that require a strong understanding of data structures and algorithms soon or I may have to supplement these questions with tasks from another website.

As usual you can find the answers to these problems and all the C# code solutions that go with them on my Github which I encourage you to check out for this and other cool projects. Until next time “insert catchphrase here”!

Project Euler – Problem 10

Noticing a trend with these questions that a lot of them involve the use of prime numbers.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

At first glance upon this question I realized it is very similar to Problem 7 which I completed earlier on. I decided to use the same algorithm to solve this problem as the one I used in that question.  In order keep my code organized in this and future questions I created a helper class to contain algorithms / functions that I believe will be required regularly throughout the series of Project Euler questions. At the moment I’ve only added the one function to it for calculating prime numbers up to any given number since it seems to be a reoccurring problem in these questions.

Utilizing this helper class (which will have functionality progressively added to it) will help eliminate redundancies in my problem classes making the complete C# solution much more manageable. Looking at the Problem 10 class below we can see how much tidier it looks by putting the algorithms in a separate class.

If I can find a way to automate the stopwatch that I’ve been putting in every class by taking advantage of the full capabilities of Object Oriented Programming then the classes will be looking a tidy as I can imagine making them. I’ll have see if I can automate the process by extending or inheriting the functionality of these classes in one way or another, but that will be left for another question.

Today marks a milestone as I have completed my 10th question! This of course means that I’m a whopping 1/55th complete as of the current date since more may have been added at the time of reading this. The image below really puts things into perspective of the monumental task that lays ahead so I will have to pick up my game and start completing these things daily I think.

Progress

Anyway nothing new to discuss about this problem as it has all been explained in Problem 7 if you want to get the answers and get the full code solution to these problems feel free to check out my GitHub which I encourage you to check out for some cool projects I am working on. Until next time stay rad, not mad.

Project Euler – Problem 9

After some dwelling on it for some time I was  unable to come up with an elegant solution to the following question:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Basically all I’ve done is brute force my way through every possible combination of numbers until I came across the solution to the problem as you can see in this non-elagant code I’ve written below:

It takes just short of a second to complete on my computer using the aforementioned method which I don’t think can be improved upon in any significant manner. You can of course solve this without using any programming and busting out some abstract algebra. We can use Euclid’s Formula to solve for the equation a2 + b2 = c2 which tells us that

  • a = 2mn
  • b = m2 – n2
  • c = m2 + n2

Since we already know that (a + b + c = 1000) we can use some algebra to solve for the unknowns.

2mn + (m2 -n2) + (m2 + n2) = 1000;
2mn + 2m2 = 1000;
2m(m+n) = 1000;
m(m+n) = 500;

m>n;

m= 20; n= 5;

a= 200; b= 375; c= 425;

This blog is more focused on the programming side of things so I don’t feel too qualified to explain the proof behind this method; I just know that it’s a tool that can be used to solve for Pythagorean triplets. Anyway as usual you can find the full code solutions and answers to all problems I have solved on my GitHub which I encourage you to check out. Sorry that the solution I’ve provided for this problem is very underwhelming, but I’ll be damned if I can think of a more efficient way of solving it! Please let me know whether you know of any improvements that could be made since I’d be very interested to hear them. That’s it for now, until next time stay awesome and get creative.

The Green Marine

aa879f132cdfb8465caffdaf863bdce74a5646e26d70ded8bc5247699d36a85f28ff76bbcd01f110da39a3ee5e6b4b0d3255bfef95601890afd8070965e00e51e463b69ff10ade0917cf04d7

Thought I’d have a go at making a little run and gun game with the popular game development engine Unity where you have to fight off an alien invasion or something of the sort; the story really isn’t important for the scale of game I am planning to make. I busted out my drawing tablet and blew the dust off it to have a go at drawing the graphics by myself for once to try and discover a style I am comfortable with. Lo and behold a simple animation I made in Flash that demonstrates some of the movements the main character will be performing.

IdleRunRoll

After a couple of hours doodling some characters I decided upon this simplistic art style for a number of reasons:

  1. I’m currently not a very good artist and evidently require MUCH more practice
  2. The character is easy to animate. As a one man team I don’t have the resources to spend all my time with the nuances of more complex character animation
  3. The layers are easily interchangeable. I can easily swap the players head, gun, and other limbs in a moments notice

From previous experience I planned ahead and drew all of the characters features individually before placing them together in the Unity Editor. This is important since it allows me to easily access each of the individual components through code which I can then use to create a more dynamic character that for instance rotates his gun to face the cursor as demonstrated here:rotation

There’s a few clipping issues with limbs that I have currently drawn and rotated through code, however I’m not too fussed since the character will be very small on the game-play screen and won’t be noticeable.

I currently have a very basic player movement demo set up using the built in physics engine that’s packaged with Unity, however I am currently working on writing my own physics engine since I can’t get the precise platformer movement I want while using the gimmicky rigid bodies that Unity seems to encourage. Maybe with a lot of tweaking it could be alright, but currently I can’t stop it from feeling really awkward no matter how much I fiddle with the settings. I’m going to have to use some ray-casting in either case as you can see some funny wall jumps happening at the moment with no proper ground collision checks.

Have to use some ray-casting to stop these wall jumps

Have to use some ray-casting to stop these wall jumps

That’s all I have to say for now. I will periodically update this series as I progress through some milestones which I’m yet to set-up. If you would like to help with the project or just to use any of the files for your own games feel free to clone the repository from my GitHub which I will keep updated with new graphics, code, and what not as I progress.

When I’m finished the game will be available to play for free since this isn’t going to be anything too spectacular and is more of a learning exercise if anything. Everything I release for this game will be available under the Creative Commons License which basically just means you can use and edit anything I create for yourself as long as it’s not for profit and I am given credit for the files being used.

Anyway I hope to see you all again some time soon with a bunch of progress. Until next time stay awesome and get creative!

Project Euler – Problem 8

Unfortunately I misinterpreted this question at first thinking it was about a 2-D array of numbers instead of a 1 dimensional array so I got excited about a potentially complex challenge that is actually a very simple question.

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Since the numbers aren’t in a matrix, but are instead just a single line string the solution is very easy to obtain. By creating two for loops that check every possible segment of 13 adjacent digits we can easily obtain the product of each segment and store the largest one we find in a variable to be displayed at the end of the loops. I think the code is more or less self explanatory as I have created below:

The program completes in 2 milliseconds on my computer and I believe the general code/algorithm cannot be improved upon in this case since the problem requires that we do examine every 13 digit segment in the number and that’s basically all we do. This question was actually pretty lame, but at least the next question looks like it will require a little bit of thought. All answers and code solutions can be found on my GitHub if you’re interested in running the program on your own machine. As usual stay awesome and try to learn something every day!

Project Euler – Problem 7

Prime numbers again? AWESOME!

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

I decided to tackle this problem using an ancient mathematical algorithm dating back to the times of Ancient Greece called the Sieve of Eratosthenes which is aptly named after its discover Eratosthenes. This algorithm is used to discover all of the prime numbers up to any given number, although it does progressively become less efficient as we check for primes in larger scopes.

Sourced from https://commons.wikimedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif under the creative commons license.

Sourced from https://commons.wikimedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif under the creative commons license.

The algorithm as visually represented above works by following this set of instructions:

  1. Create array of numbers marking them all as prime by default
  2. Find the first prime number in the array (“2” in this scenario)
  3. Mark all multiples of the found prime number as not prime
  4. Find the next prime number (“3” in this scenario)
  5. Repeat steps 3 and 4

This algorithm is effective when translated into computer code since even though we are forced to iterate through the array multiple times we do so in increasingly larger jumps of prime numbers 2, 3, 5, 7, 11 etc…

Converting the algorithm into code is very simple too. Breaking the code into the steps I’ve created above I created the following.

Step 1:

Steps 2-5

And putting it all together with the timer and what not I created the full class

On my machine this completed in 5 milliseconds which I think is more than acceptable given the current problem. Although there is an even more effective algorithm/sieve for calculating prime numbers known as The Sieve of AtkinIt is however much more modern and therefore complicated to understand and implement, and being the lazy person I am will only use it when I am forced to perhaps in a later challenge. Come to think of it my Grandfathers surname is Atkins… maybe I come from a bloodline that invented that sieve since we’re both of British heritage? I guess I’ll have to pay my respects and use it at a later date then. If only knowledge was hereditary. Anyway as usual you can find the full code solutions and answers on my GitHub along with some other projects I plan on uploading soon. See you in the next problem which actually looks pretty cool!

Project Euler – Problem 6

There is only one way to solve a problem like this unless you are aware of some mathematical hocus-pocus that can solve these with a funny looking equation. I suppose it would help if you saw it first before I ramble so have a look below

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

As you may have already guessed most people will come to the solution by simply looping through the numbers 1-100 and adding the values to some assigned variables before finding the difference between them. For example my code shown below works just by doing that:

This of course works fine and solves the problem is about 2 milliseconds, but (there’s always a but) if we wanted to calculate for numbers up to and beyond 1 trillion or whatever it’s not going to complete within our lifetimes with this code. Thankfully some math people who are much smarter than me discovered some equations to solve for the sum of squares and the square of sums. So if you’re a real nerd for this stuff you can find that:

  • The square of sums is (1 + 2 + … + n)^2 = n^2 * (n+1)^2 * 1/4
  • The sum of squares is 1^2 + 2^2 + … + n^2 = n * (n+1) * (2n+1) * 1/6

These equations will work for any value of n. The reason I have not implemented these in my code is because it seems redundant to solve the problem with these equations when you could just as easily solve it with pen and paper.

Sorry this question was kind of lame; hopefully things will start getting interesting soon as I progress further with the questions. As usual the full code and answers to all problems can be found on my GitHubUntil next time as my home boy Finn would say “Stay mathematical!”

Project Euler – Problem 5

Jumping straight into this one the problem comes with the following example and query:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I went through two iterations trying to solve this problem within a reasonable time. Both solutions are very similar but have a critical change to increase the solve time by a factor of over 20.

The Stupid Way

As most people could probably figure out on their own to solve this problem we have to test whether numbers starting from 20 –  ? are evenly divisible by numbers 1 through 20. The first thought that comes to mind is to create a while or for loop based on the conditions above that increments the number being checked by one per iteration by doing something along the lines of this:

On my machine this completes in a time of about 8 seconds as you can see below. YES THE GREEN TEXT ON A BLACK CONSOLE IS IMPORTANT FOR THAT 1337 |-|4X0|* CRED!

Problem-5-Slow

The smarter way

The above code works fine, however if we analyze the problem for a few seconds we can see a few inefficiencies to get rid of.

  • Firstly there is no reason to have the counter increment in values of 1 since the highest factor we are testing for is 20 making 19/20 checks pointless.
  • Secondly there is no reason to check whether the number is divisible by numbers 1-10 since if it is divisible by numbers 11-20 we already know it is divisible by the lower half. For instance if we were checking all numbers from 1-30 we would only need to check half way through that too 16-30 since they’re also twice the value of their lower half making it redundant to check them as well.

By making the simple changes that we just noted in our code we can expect a dramatic increase in performance. Pasted below is the full class I used to solve this problem the efficient way:

Using this code I get an average performance of less than 0.2 seconds. This makes sense since we reduced the number of iterations by a factor of 20 bringing the average down to 0.4 seconds. Following this we reduced the number of checks needed to be performed by half meaning we should then roughly halve the remaining time of the value we are getting now as shown on my machine here:

Problem-5-Fast

This problem demonstrates very well how imperative it is to look over your code for minor and/or simple improvements that can drastically increase the programs performance times. There are even much faster ways to solve this problem using a completely different method than I’ve shown here using prime factorization of the numbers 11 through 20, although I don’t want to get into that right now since I feel it’s more important to emphasize the importance of your code with the knowledge you currently have. By all means feel free to research the best way to tackle a certain problem, but always remember to look over the method you have implemented for improvements much like I’ve shown here.

I should note that if you wish to run my code samples as individual files rather than downloading the whole project from my GitHub just copy the code I provide here into your IDE of choice and change the run() function into the entry function public static void main(string[] args). Anyway that’s all I have to say about this problem for now so until next time have fun and prosper!

Project Euler – Problem 4

Not a great deal of thought had to go into this one since it mainly just involved some basic string observations/manipulation or whatever you want to call it. The problem goes like this:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Basically all that I had to do was create two for loops with one being nested inside the other one. Starting with the highest triple digit numbers (999 * 999) I followed these steps:

  1. If product is higher than current highest palindrome
  2. If product is a palindrome
  3. The product is now the new highest palindrome!
  4. Skip to the next set of integers since every other value will be lower than the current palindrome for this current value of j
  5. Rinse and repeat until we run out of triple digit numbers to multiply!

The main thing I have to insist people do on this problem is break out of the loops early when you can. When checking every single product for palindromes it took my machine on average ~182 ms to complete since I was checking for just under 800,000 different products, however when breaking out of the loops at appropriate times I got this down to ~3 ms on average or in other words made it %6000 faster! These were the speeds I was clocking before and after the modification.

Time to Complete

Here is the class that I created to solve the problem. Nothing too special to look at in this one since all of the logic is pretty straight forward. Feel free to comment/contact me if there is any confusion though and I’ll be glad to help.

Unfortunately the largest palindrome isn’t a prime 🙁 Obviously the question made it impossible for that to be the case though since it was asking for a palindrome from a product. As usual the full solutions and answers can be found on my GitHub which I encourage you to check out. I’ll start explaining myself a little more as I progress and the questions require more complex thought maybe by writing some pseudo-code or something? Anyway that’s it for now so until next time have a blast with whatever you’re doing.