Problem #14

Här kommer min lösning till problem 14. Här stötte jag på problem då mina 32-bit int's inte räckte till på min plattform. Därav uint64_t, då talet växte till ganska stora tal (dvs större än 4294967296).

#include <iostream>
#include <utility>

template <typename T>
inline T next_seq(T n)
{
  return n & 1 ? (n * 3) + 1 : n / 2;
}

template <typename T>
inline T chain_length(T n)
{
  T i;
  for (i = 1; n != 1; ++i)
    n = next_seq(n);
  return i;
}

int main(int argc, char *argv[])
{
  std::pair<int64_t, uint64_t> chain_pair;
  for (uint64_t i = 2; i < 1000000; ++i)
  {
    uint64_t len = chain_length(i);
    if (len > chain_pair.first)
      chain_pair = std::make_pair(len, i);
  }

  std::cout << "Answer is "
            << chain_pair.first
            << " for n = "
            << chain_pair.second
            << std::endl;

  return 0;
}

Det finns en ganska bra optimering att göra in chain_length() genom att ha en hashtabell med n som nyckel och längden som värde för att inte göra onödigt jobb. Men med brute force på min MacBook går det <1s så det känns ganska onödigt.

Godnatt! Snart dags för en ny arbetsvecka.

Unix timestamp 1234567890

... har precis inträffat! Det är ett stort ögonblick. :D

Problem #8

Find the greatest product of five consecutive digits in the 1000-digit number.

Nästan för enkel:

#include <iostream>

char nums[] = {
  "73167176531330624919225119674426574742355349194934"
  "96983520312774506326239578318016984801869478851843"
  "85861560789112949495459501737958331952853208805511"
  "12540698747158523863050715693290963295227443043557"
  "66896648950445244523161731856403098711121722383113"
  "62229893423380308135336276614282806444486645238749"
  "30358907296290491560440772390713810515859307960866"
  "70172427121883998797908792274921901699720888093776"
  "65727333001053367881220235421809751254540594752243"
  "52584907711670556013604839586446706324415722155397"
  "53697817977846174064955149290862569321978468622482"
  "83972241375657056057490261407972968652414535100474"
  "82166370484403199890008895243450658541227588666881"
  "16427171479924442928230863465674813919123162824586"
  "17866458359124566529476545682848912883142607690042"
  "24219022671055626321111109370544217506941658960408"
  "07198403850962455444362981230987879927244284909188"
  "84580156166097919133875499200524063689912560717606"
  "05886116467109405077541002256983155200055935729725"
  "71636269561882670428252483600823257530420752963450"
};

int main(int argc, char *argv[])
{
  for (size_t i = 0; i < sizeof(nums); ++i)
    nums[i] -= '0'; // Just convenience

  int largest_product = 0;
  for (size_t i = 0; i < sizeof(nums) - 5; ++i)
  {
    int p = nums[i]*nums[i+1]*nums[i+2]*nums[i+3]*nums[i+4];
    largest_product = std::max(p, largest_product);
  }

  std::cout << "Answer is " << largest_product << std::endl;
  return 0;
}

Problem 7: Find the 10001st prime.

Problem #7 var lite tråkigt. Min is_prime() är inte optimal direkt. Följande fakta borde ha implementerats också:

• 1 är inte ett primtal.


• Alla primtal utom 2 är udda.


• Givet n kan bara ha en primtalsfaktor större än sqrt(n).

Min lösning:

#include <iostream>

template <typename T>
inline bool is_prime(T p)
{
  for (T i = 2; i < p; ++i)
    if (!(p % i))
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  int n = 10001; 
  for (int pnum = 0, i = 2;; ++i)
  {
    if (is_prime(i))
    {
      pnum++;
      if (pnum == n)
      {
        std::cout << "Answer is " << i << std::endl;
        return 0;
      }
    }
  }
}

Godnatt!

Problem #6

Hade redan öppnat sidan för problem #6 i browsern...

#include <iostream>

template <typename T>
T sum_square(T n)
{
  T result = 0;
  for (T i = 1; i <= n; ++i)
    result += i * i;
  return result;
}

template <typename T>
T square_sum(T n)
{
  T result = 0;
  for (T i = 1; i <= n; ++i)
    result += i;
  return result * result;
}

int main(int argc, char *argv[])
{
  int n = 100;
  std::cout << "Answer is "
            << square_sum(n) - sum_square(n)
            << std::endl;
  return 0;
}

Nej, nu stänger jag av datorn för ikväll!

Problem #4

Okej, vi tar problem #4 också. Här är utmaningen att hitta det största talet som är ett palindrom genom produkten av två heltal på minst tre siffror.

#include <iostream>

template <typename T>
bool is_palindrome(T candidate)
{
  T n = candidate, rev = 0;
  while (n > 0)
  {
    rev = rev * 10 + n % 10;
    n /= 10;
  }
  return candidate == rev;
}

int main(int argc, char *argv[])
{
  int largest_palindrome = 0, cx, cy;
  int max = 1000, min = 100;
  for (int x = min; x < max; ++x)
  {
    for (int y = min; y < max; ++y)
    {
      if (is_palindrome(x * y))
      {
        int product = x * y;
        if (product > largest_palindrome)
        {
          cx = x; cy = y;
          largest_palindrome = product;
        }
      }
    }
  }
 
  std::cout << "Answer is "
            << largest_palindrome
            << " (" << cx << " * " << cy << ")"
            << std::endl;
  return 0;
}

Godnatt (på riktigt)!

Problem #3

Och här en quick'n'dirty lösning till problem #3. Här kom primtalsfaktoriseringen till användning.

#include <iostream>
#include <cmath>

template <typename T>
bool is_prime(T p)
{
  for (T i = 2; i < (p / 2.0); ++i)
    if (fmod(p, i) == 0.0)
      return false;
  return true;
}

template <typename T>
T trial_division_prime_only(T n)
{
  T max = sqrt(n), result = 0.0;
  for (T i = 2; i <= max; ++i)
    if (fmod(n, i) == 0.0 && is_prime(i))
      result = i;
  return result;
}

int main(int argc, char *argv[])
{
  long double n = 600851475143;
  std::cout << "Answer is " << trial_division_prime_only(n) << std::endl;
  return 0;
}

Godnatt!

Problem #5

En möjlig lösning till problem #5. Den här snurran tar någon sekund att beta genom på min maskin, men det går att gena genom primtalsfaktorisering fick jag lära mig.

#include <iostream>

bool f(int n)
{
  for (int i = 1; i <= 20; ++i)
    if (n % i)
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  int n = 1;
  while (!f(n))
    ++n;

  std::cout << "Answer is " << n << std::endl;
  return 0;
}

Problem #2

Och här kommer lösning till problem #2:

#include <iostream>

int main(int argc, char *argv[])
{
  int sum = 0;
  for (int t, c = 2, p = 1; sum < 4000000; )
  {
    if (!(c & 1))
      sum += c;
    t = c; c += p; p = t;
  }

  std::cout << "Answer is " << sum << std::endl;

  return 0;
}

Gjorde den rekursiv först; men stacken tog lite för mycket stryk :P

Nya tidsfördriv, Project Euler

Har hittat ett nytt tidsfördriv. Project Euler.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Löste igår tre av 231 problem, svårighetsgraden ökar ganska snabbt, så det kommer bli en otroligt lärorik resa.

Här min lösning på Problem #1:

#include <iostream>

int f(int n)
{
  if (!n)
    return 0;
  else
    return (!(n % 3) || !(n % 5)) ? n + f(n - 1) : 0 + f(n - 1);
}

int main(int argc, char *argv[])
{
  int n = 1000 - 1;
  std::cout << "Answer is " << f(n) << std::endl;
  return 0;
}

Känner jag mig själv rätt kommer många problem lösas av hård brute force ;)