Obtained: Job (Internship)

As most NPCs know by now, I recently began a new chapter in the story; my story. This chapter focuses on my recently obtained internship at MokaFive. To be completely honest when I first heard about MokaFive from a good friend that works there I was highly hesitant. My primary concern was that it was not a video game company. Sad news.

However, my interest in the position grew as I learned more about the company and the technologies I would be working with. As the interview process proceded I found myself more and more hopeful of being offered the job. This was all weeks ago.

Now, a week into the job, I am very pleased to say that it is a great place to work and for several reasons. The people are really friendly and are exceptionally intellegent with a large portion having a masters (or Ph.D.) from Stanford. One of the founders is even a CS professor from Stanford. The overall environment is relaxed and fairly casual but at the same time there is always something that needs to be done and it's seemingly crunch time often.

I am not clear on exactly all of the cool technologies that I am going to work with but to give you an idea. Last week I played around with a MSI file using Orca.exe and learned a great deal about the MokaFive product. This next week I am going to learn Python and SCons to help work on the build tools and I am also going to implement a Windows service into the product which is going to undoubted require me to use about five different things that I have never used before. Exciting!

The only downside to this internship is that I consequently have much less time. Project Euler problems are going to probably be fairly infrequent for now as well as my blog posts. I do want to continue to write about what I am doing at work as well as a juicy side project that I have yet to mention in this blog. Stay tuned!

*saved game*

Grind Report 30

Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

*WARNING: This contains the solution!*

This was a fairly simple problem. My approach was extreme brute force using some recursion. I first consider every possible number with one digit, then two digits and so on. Every number I consider I check to see if the number matches the criteria for being a special number.

As I look back at my solution I think that recursion was probably not the best method but I'll let it stay as it is.

One important thing to do in this problem is precalculate the digits to the 5th power and store them in an array. This is somewhat obvious but still helps cut down the cost.

#include <iostream>
#include <vector>
#include <math.h>

using std::vector;
using std::cout;

const double N = 5;
const int MAXDIGITS = 6;

vector<int> nthpow;
int solution;

void CheckDigitCombinations(int digitCount, int digitTotal, int num, int sumOfDigits);

int main()
{
 //precalculate the nth power of all single digits [0-9]
 for (double i = 0; i < 10; ++i)
  nthpow.push_back((int)pow(i, N));

 for (int digitCount = 1; digitCount <= MAXDIGITS; ++digitCount)
  CheckDigitCombinations(digitCount, digitCount, 0, 0);

 cout << solution;
}

void CheckDigitCombinations(int digitCount, int digitTotal, int num, int sumOfDigits)
{
 
 for (int digit = 0; digit < 10; ++digit)
 {
  int number = num;
  int sum = sumOfDigits;
  if (digitCount == digitTotal && !digit)
   continue;
  //add on the extra digit (doesn't change anything for digit #1)
  number *= 10;
  number += digit;
  sum += nthpow[digit];
  if (digitCount > 1)
   CheckDigitCombinations(digitCount - 1, digitTotal, number, sum);
  if (sum == number && sum != 1 && digitCount == 1)
   solution += number;
 }
}

*saved game*

Grind Report 29

Problem 29

Consider all integer combinations of a^b for 2 <= a <= 5 and 2 <= b <= 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 <= a <= 100 and 2 <= b <= 100?

*WARNING: This contains the solution!*

While attempting this problem I came up with two solutions - but only one actually completely worked... As usual, using C++ runs into some problems here because of the limitation on integer size.

My first solution (the semifunctional one) placed the focus on the repeated terms. I used the fact that an exponent can be broken up such as

2^32 = (2^4)^8 = 16^8

With this it is possible to find which terms are repeated without ever actually calculating the value of a^b. So with this it is easy to simply keep a boolean collection of the different combinations and if one has been encountered before. Such as in the example above when 2^32 (a = 2, b = 32) is run it will see that this is equal to 4^16 and 16^8. Consequently [4][16] and [16][8] both need to be marked as repeats. At the end it is as easy as counting the repeats and subtracting them from the max number of possible terms (99x99).

Here is the code but keep in mind that this code does not return the correct answer. While attempting to debug the solution I came across another, much simplier, solution. That I'll discuss after this.

#include <iostream>
#include <vector>

using std::vector;
using std::cout;

int PowerWithinMAX(int a, int b);

int main()
{
vector<vector<bool>> encountered;
 //create the list of encountered combinations - vector<vector<bool>>
 for (int i = 0; i < MAX + 1; ++i)
  encountered.push_back(vector<bool>(MAX + 1, false));
 
 int repeatCount = 0;
 for (int a = MIN; a <= MAX; ++a)
 {
  for (int b = MIN; b <= MAX; ++b)
  {
   //if a^b has previously been encountered before
   //then increment repeat count and continue
   if (encountered[a][b])
   {
    ++repeatCount;
    continue;
   }
   //check to see if b can be broken up into pieces
   //ie. 2^32 = (2^4)^8 = 16^8
   //if so then mark that as being encountered ([16][8])
   for (int i = 2; i < b / 2; ++i)
   {
    //if i is a divisor of b
    if (b % i == 0)
    {
     //check to see if the power is within the max
     int c = PowerWithinMAX(a, i);
     if (c)
      encountered[c][b / i] = true;
    }
   }
  }
 }
 int ans = 0;
 for (int i = 0; i <= MAX; ++i)
  for (int j = 0; j <= MAX; ++j)
   if (encountered[i][j])
    ++ans;
 
 int answer = (MAX - MIN + 1) * (MAX - MIN + 1) - ans;
 cout << answer;
}

int PowerWithinMAX(int a, int b)
{
 int solution = 1;
 //calculates a^b until solution is > 100
 while (solution <= MAX && b > 0)
 {
  solution *= a;
  b--;
 }
 //if b > 0 (true) then the solution is greater than MAX
 if (solution > MAX)
  return 0;
 else
  return solution;
}

The working method using some more standard library goodness to take care of mostly everything. Every possible combination of a^b is calculated using pow(a, b) and then stored into a set. Once done the set.size() is the unique number of terms. The reason why this works is that when using double it is true that it is not precise enough to give the correct term, but it is precise enough that all terms are unique unless they are actually a repeated term.

Because this is so simple the code is pretty small.

#include <iostream>
#include <set>
#include <math.h>

using std::set;
using std::cout;

const int MIN = 2;
const int MAX = 100;

int main()
{
 set<double> answer;
 for (double a = MIN; a <= MAX; ++a)
  for (double b = MIN; b <= MAX; ++b)
   answer.insert(pow(a, b));
 cout << answer.size();
}

I will probably go back and fix up the first solution and get it working eventually. I am curious what the problem with the algorithm is. In the meantime I'll continue to move onward.

*saved game*