Grind Report 18

Alright! I am now officially above the average for the number of problems completed on Project Euler. The current average is 17.3. You can see the statistics here.

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 5
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

[number triangle]

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

*WARNING: This contains the solution!*

As soon as I read "clever method" my heart jumped for joy for it knows what a challenge looks like. I immediately began seeking to discover this oh so clever method.

My initial thought was that I could possibly use some type of algorithm like A* (A-star) and find the best path using that. In order for A* to work I would need each point, every number, to know what its value is to reach the bottom - or at least this is what I was thinking. When I did look at the bottom and see if I could actually come up with this value for each number, I saw that I could get this if I started with the second to last row and considered each number. For each number I would take the largest out of the two choices that number had below it and add it to the number. Like so...

//consider the first number
63 66
04 62 98

//add 62 to 63
125 66
04 62 98

//consider the secon number
125 66
04 62 98

//add 98 to 66
63 164
04 62 98

...and so on. Move up the rows as you complete them to get the best value so we can perform the A*... wait. When we get to the top it is going to have the largest number we can get right? Isn't that we are going for?

Yes!

And this is how I stumbled upon the "clever method". It was around this point that I concluded that A* is not the algorithm you'd want to use for this type of problem. It was worth a shot though and amazing it did lead to the correct answer.

Here is my implementation of the method explained above.

#include <iostream>
#include <vector>
#include <fstream>
#include <string>

using std::string;
using std::ifstream;
using std::vector;

//changes a string to an int
int stoi(string str)
{
int val;
val = 0;
for (int i = 0; i < str.length(); ++i)
val = 10 * val + (str[i] - '0');
return val;
}

int main()
{
vector<vector<int>> triangle;

//read in the triangle from file
string line;
int lineCount = 0;
ifstream file ("triangle.txt");
if (file.is_open())
{
while (!file.eof())
{
 std::getline(file, line);
 triangle.push_back(vector<int>());
 for (int i = 0; i * 3 + 1 < line.length(); ++i)
 {
  int number = stoi(line.substr(i * 3, 2));
  triangle[lineCount].push_back(number);
 }
 ++lineCount;
}
//take back the extra line
--lineCount;
}

//go through every row, starting from the second to the bottom,
//and calculate the row's optimal values based off of the row below
for (int i = lineCount - 1; i >= 0; --i)
//go through every number
for (int j = 0; j < triangle[i].size(); ++j)
 //add the best possible value to the current index
 triangle[i][j] += triangle[i + 1][j] > triangle[i + 1][j + 1] ? triangle[i + 1][j] : triangle[i + 1][j + 1];
//the top will house the maximum value at the end of the algorithm
std::cout << triangle[0][0] << std::endl;
}

*saved game*

Grind Report 17

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

*WARNING: This contains the solution!*

There are many approaches to this. I think that this is a pretty simply problem overall. My approach to this problem was fairly straightfoward. Basically I made a map that consisted of keys that represented the number and the values were the number of letters the number was made up of. Such as 7 mapped to 5 (seven). 20 -> 6 (twenty).

I did not have to include all of the numbers because there is so much overlap and I could split up the number into its different components. An example of this would be 192 one comes from 1 -> 3. 100 -> 7. 90 -> 6. 2 -> 3 and then since the number is greater than 100 and not evenly divisible by 100 we need to include the 'and' so add 3. 192 = 22

I used recursion for this since I like recursion so much :)

#include <string>
#include <iostream>
#include <map>

using std::map;
using std::string;
using std::cout;

map<int, int> dictionary;
const int MAX = 1000;

int CountLetters(int number)
{
 if (!number)
  return 0;
 if (number < 20)
  return dictionary[number];
 if (number / 1000)
  return CountLetters(number / 1000) + dictionary[1000] + CountLetters(number % 1000);
 if (number / 100)
 {
  int temp = CountLetters(number / 100);
  temp += dictionary[100];
  temp += CountLetters(number % 100);
  return  temp;
 }
 if (number / 10)
 {
  int temp = dictionary[(number / 10) * 10];
  temp += CountLetters(number % 10);
  return temp;
 }
}

int main()
{
 dictionary[0] = 3; //and
 dictionary[1] = 3; //one
 dictionary[2] = 3; //two
 dictionary[3] = 5; //three
 dictionary[4] = 4; //four
 dictionary[5] = 4; //five
 dictionary[6] = 3; //six
 dictionary[7] = 5; //seven
 dictionary[8] = 5; //eight
 dictionary[9] = 4; //nine
 dictionary[10] = 3; //ten
 dictionary[11] = 6; //eleven
 dictionary[12] = 6; //twelve
 dictionary[13] = 8; //thirteen
 dictionary[14] = 8; //fourteen
 dictionary[15] = 7; //fifteen
 dictionary[16] = 7; //sixteen
 dictionary[17] = 9; //seventeen
 dictionary[18] = 8; //eighteen
 dictionary[19] = 8; //nineteen
 dictionary[20] = 6; //twenty
 dictionary[30] = 6; //thirty
 dictionary[40] = 5; //forty
 dictionary[50] = 5; //fifty
 dictionary[60] = 5; //sixty
 dictionary[70] = 7; //seventy
 dictionary[80] = 6; //eighty
 dictionary[90] = 6; //ninety
 dictionary[100] = 7; //hundred
 dictionary[1000] = 8; //thousand


 int temp = CountLetters(201);


 int letterCount = 0;
 for (int i = 1; i <= MAX; ++i)
 {
  letterCount += CountLetters(i);
  if (i > 100 && i % 100 != 0)
   letterCount += dictionary[0];
 }

 cout << letterCount << std::endl;
}

*saved game*

Grind Report 16

Problem 16

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

*WARNING: This contains the Solution!*

What is your first thought when looking at this problem? Mine was that the largest number that C++ can represent is 2^64 (long long). So obviously we cannot just calculate this by any traditional means.

What I decided to do is go back to grade school and implement some basic arithmetic to solve the problem. I did this by creating a large array that would house the solution. The array was initialized with 1 in the first index and I then preceded to continuously multiply the contents of the array by the base value, 2 in this case. Carrying was of course necessary.

I feel like this was a pretty basic and fairly obvious approach to solving this problem. I know that some of the scripting languages such as Ruby or Python were able to solve this problem in one line - good for them. Here is my code.

#include <iostream>

using std::cout;
using std::endl;

//2^1000 (This solution works for BASE 1-10 & POWER 0+)
const int BASE = 2;
const int POWER = 1000;

int main()
{
 //this array size needs to be adjusted according to the BASE and POWER
 int number[310];
 //BASE^0
 number[0] = 1;
 int size = 1;
 int remainder = 0;
 //for each power...
 for (int i = 1; i <= POWER; ++i)
 {
  //raise each value by the base, keep the remainder and use the previous remainder
  for (int j = 0; j < size; ++j)
  {
   //calculate the new remainder
   int newRemainder = BASE * number[j] / 10;
   //the new value of this digit
   number[j] = ((BASE * number[j]) % 10) + remainder;

   //check to see if the remainder caused overflow
   if (number[j] / 10)
   {
    newRemainder += number[j] / 10;
    number[j] = number[j] % 10;
   }
   //set the remainder
   remainder = newRemainder;
  }
  //if there is a remainder left then add it and increase the size
  if (remainder)
  {
   number[size] = remainder;
   ++size;
  }
  remainder = 0;
 }

 int sum = 0;
 //sum of the digits of the number
 for (int i = 0; i < size; ++i)
  sum += number[i];

 cout << sum << endl;
}

*saved game*

Grind Report 15

Problem 15

Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.

[2x2 grid routes]

How many routes are there through a 20x20 grid?

*WARNING: This contains the solution!*

This was an interesting and challenging problem! That is if you don't have any background with this type of problem. To be completely honest, this was the first problem thus far that actually had me stumped. I enjoyed it!

My initial intuition was that there must be some type of equation that represents the answer. The grounding for this thought was based on the fact that the number of routes grows with the size of the grid. But how? This question daunted me for nearly an hour before I came to the conclusion that I would not be able to derive this algorithm and there must be another way. Before I move on though, I would like to share some of my attempts.

For some reason, along with my initial intuition came the factorial sign (!) and so I played around with that some. I saw that for the 2x2 grid 3! = 6 which is (2 + 1)!. I needed more samples to work with so I figured out that 1x1 = 2 and 3x3 = 20. (1 + 1)! = 2. I was really onto something! (3 + 1)! = 24 ...or not >.<.

My next attempt was nxn = (2n)! / 2n. 2x2 = 4! / 4 = 6. Good... 6! / 6 = 120...not quite. I played around with some other numbers but soon moved onto my next method.

This other method consisted of me staring at all the possible 3x3 routes and trying to come up with some sort of elegant way to calculate the number of paths for any nxn grid. I tried many things like sorting the routes by the number of turns they took, breaking the 3x3 into a 2x2 and seeing if I could build off of the previous nxn grid...ect. Some of these ideas where definitely better than others, but in the end I had come up with nothing. I was for once actually stumped.

So I turned to my good friend, Google, and asked him what he knew about this problem. I was looking for some type of hint - a push towards the solution. Well, he told me exactly what I was asking for...and way more. Unfortunately, while I was attempting to find a hint, I found a HUGE hint that led to the solution in about...3 seconds...

What I found was that this problem is strongly connected with pascal's triangle and by drawing the triangle inside the grid (with the outside 1's on the outside of the grid) you can actual find the number of possible routes every time by looking at the largest number (it will be in the corner). If you do this starting from the bottom corner of the grid up to the start corner each number inside of the grid represents the possible number of routes from that corner. You have no idea how close I was to figuring this out. I went ahead and programmed something along these lines to get the solution.

#include <string>
#include <iostream>

using namespace std;

const int diminsion = 20;

int main()
{
int total;
//this grid will be a pascals triangle
long long grid[diminsion + 1][diminsion + 1];
//fill in the sides with 1
for (int i = 0; i < diminsion + 1; ++i)
{
 grid[0][i] = 1;
 grid[i][0] = 1;
}
//fill in the middle
for (int i = 1; i < diminsion + 1; ++i)
{
 for (int j = 1; j < diminsion + 1; ++j)
 {
  grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
 }
}
cout << grid[20][20];
}

After getting the solution I was able to read the forums for this question and see what the different solutions people had come up with. Apparently there is another way to solve this problem. This other method deals with combinatorics, which I almost took last semester but didn't because I wanted to take Linear Programming. I don't know all of the details that go into finding this solution but I do know what the solution looks like.

(40!) / (20! * 20!)
((2n)!) / (n! * n!)

...seriously!? >.>;

*saved game*

Grind Report 14

Problem 14

The following iterative sequence is defined for the set of positive integers:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

*WARNING: This contains the solution!*

As you can guess this could be a lot of calculations. But all of the numbers eventually cross at some point (4 -> 2 -> 1). So my first thought was to use memoization but before I did this I implemented a fairly straightforward method (for the most part brute force). I got this to work almost immediately so I decided to attempt the memoization.

Along side the memoization, I used a recursive method. Basically I had a map that stored the number as a key and the value was the number of terms in the chain the key would produce. Overall I think this was a good direction to come from; however, there was two things I did not take into consideration.

One thing is that the overhead for each function call in the recursion added up thus slowing the program. The other problem is that mapping each value to a key took a toll on the speed as well. I ended up scrapping this attempt because the brute force method was pretty fast (1.5~ seconds to solve this problem). In retrospec, I think I could have fixed up this memoization method and gotten it to be faster than 1.5~ seconds.

First, if I inlined the function *I think* that would take out some? most? of the overhead for calling the function. The other thing I could have done is been smarter with mapping the numbers. Such as only mapping the more common numbers; however, I am not sure how to distinguish the common numbers from the other numbers. Even numbers would be a guess of mine, but that is something I'd have to consider more for a good answer.

So I reverted back to my first attempt. Two things I used to make this attempt more effecient were: only consider odd numbers, only consider numbers 500,000-999,999. The reason for the first one is somewhat obvious. Odd numbers make it become larger; even numbers make it become smaller. The reason for the second one is because all numbers 1-499,999 can be multiplied by 2 and be found within the range I was considering - therefore adding an extra number to the chain. :)

Here is my brute force method.

#include <string>
#include <iostream>

using std::string;
using std::cout;

const int MAX = 999999;

int main()
{
int answer = 0;
int highestCount = 0;
for (int i = (MAX + 1) / 2; i < MAX; i += 2)
{
 long long number = i;
 int count = 1;
 while (number != 1)
 {
  if (number % 2 == 0)
   number /= 2;
  else
   number = number * 3 + 1;
  ++count;
 }
 if (count > highestCount)
 {
  highestCount = count;
  answer = i;
 }
}
cout << "Highest Number is " << highestNumber << std::endl;
cout << answer << " with count of " << highestCount << std::endl;
}

*saved game*

Grind Report 13

After a two day hiatus, I am back and ready for action.

Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

[list of 100 50-digit numbers]

With one of the earlier problems I had to deal with some large numbers and know that the largest integer type provided by C++ is unsigned long long, which ranges from 0 to 18446744073709551615. That is not 50-digits long. So having a long long array of the 100 numbers is out of the question.

One of the keys to solving this is that only the first 10 digits of the sum needs to be found. So my first thought was that I only needed to sum up around the first 15~ digits of each number. This gives plenty of room for the number to be correct and also fit inside of a long long.

Another thought I had was to just simply read from a file one line at a time. Each line has a number so I take the substring of the first 15 digits and then convert it into a long long and add it to the total. Once the file reaches its end all that needs to be done is return the answer.

This is very straight forward, took about 15 minutes to solve completely, and returned the correct answer my first run. :)

#include <iostream>
#include <fstream>
#include <string>

using std::string;
using std::ifstream;


long long atoll(string str)
{
 long long val;
 val = 0;
 //goes through each digit and adds it to the value
 for (int i = 0; i < str.length(); ++i)
   val = 10 * val + (str[i] - '0');
 return val;
}

int main()
{
   long long answer = 0;
   string line;
   ifstream file ("numbers.txt");
   if (file.is_open())
   {
       while (!file.eof())
       {
           std::getline(file, line);
           line = line.substr(0, 15);
           answer += atoll(line);
       }
   }
   std::cout << answer << std::endl;
}

*saved game*

Grind Report 12

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th 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?

*WARNING: This contains the solution!*

I believe there are a few different approaches for this problem. One is a complete brute force solution of checking each number that divides into the triangle number. This would be kind of slow and I actually did not even really consider it.

The approach I used was much more direct. Determining a triangle number was essentially given since we always had the previous triangle number. The tricky part of this problem was determining how many divisors a number has.

How many divisors a number has? With this approach to the question it is very easy to get the number of divisors. But you have to know prime numbers... those things sound familiar... In problem 7, Grind Report 8, an algorithm was created to make a list of prime numbers - just what we need!

With a list of prime numbers we can run through them and factor the number. Meanwhile, we add up each prime number exponent and multiply them all together to come up with the solution. Here is the code.

#include <iostream>
#include <math.h>
using namespace std;

const int TARGET = 200;
int primes[TARGET];

int calculateDivisorCount(int number)
{
 //setup
 int total = 1;
 int count = 0;
 int max = number / 2;
 for (int i = 0; i < TARGET; ++i)
 {
  //if the number is done being factored then break;
  //if a the prime number currently being considered (primes[i] is greather
  //than the number / 2 then that means the number is prime
  if ((number == 1 && count == 0) || primes[i] > max)
   break;
  //check to see if the current prime number is a factor
  if (number % primes[i] == 0)
  {
   //lessen the number to continue the factor tree
   number /= primes[i];
   //increase the exponent of the current prime number
   count++;
   //repeat the current prime number
   --i;
  }
  else if (count != 0)
  {
   //update the total divisors by multiplying it by the number of exponents of this prime number
   total *= (count + 1);
   count = 0;
  }
 }
 //if total is 1 that means the number is a prime and thus it has 2 divisors (1 and itself)
 if (total == 1)
  return 2;
 return total;
}

int main()
{
 primes[0] = 2;
 primes[TARGET - 1] = -1;
 int number = 3;
 int foundCount = 1;
 bool isPrime = false;
 while (primes[TARGET - 1] == -1)
 {
  double max = sqrt((float)number);
  //assume a number is prime until proven guilty
  isPrime = true;
  for (int i = 0; i < foundCount; ++i)
  {
   //break if the number is divisible by an already found prime number (guilty)
   if (number % primes[i] == 0)
   {
    isPrime = false;
    break;
   }
   //check to see if the square root of the number is less than or equal to the current prime number.
   //if so then break. This means the number is a prime.
   if (primes[i] >= max)
    break;
  }
  //add the prime number
  if (isPrime)
   primes[foundCount++] = number;
  //increment the number by 2 (to stay odd)
  number += 2;
 }

 //sum is the triangle number
 int sum = 0;
 int i = 1;
 while (true)
 {
  sum += i;
  ++i;
  if (calculateDivisorCount(sum) > 500)
   break;
 }
 int answer = sum;
 cout << "Answer: " << answer << endl;
}

I was pretty happy with this solution. It is very fast and I think the method I used to calculate the divisor count is kind of neat :)

*saved game*