Project Euler Solutions Thread

0xDEAD10CC · 05-06-2014, 05:05 AM

Might as well start something fun.

A few starting solutions I've written for Project Euler problems. I may add some more later. Feel free to post your solutions if you want. Smile

I've solved over 70 problems so far, but some others may not be as far so keep in mind to use spoilers, and provide explanations for the more difficult problems if the code seems cryptic.

Problem 1: C++

Spoiler:Code:
#include <iostream>

int main()
{
  const int max_n = 1000;
  int j = 0, count = 0;
  for (int i = 3; i < max_n; i += 3)
  {
    if (i > j && (j += 5) < max_n) count += j;
    if (i != j) count += i;
  }
  std::cout << count << std::endl;
}

Problem 2: C++

Spoiler:Code:
#include <iostream>

int main()
{
  int sum = 0, i = 1;
  const int max_n = 4000000;
  int fib[2] = {1, 2};
  do
  {
    sum += fib[i] & 1 ? 0 : fib[i];
    fib[i ^= 1] = fib[0] + fib[1];
  } while (fib[i] < max_n);
  std::cout << sum << std::endl;
}

Problem 3: C++

Spoiler:Code:
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

/*
 * What is the largest prime factor
 * of the number 600851475143?
*/

void prime_atkin(const int max_n, std::vector<int> &primes)
{
  std::vector<bool> p(max_n, false);
  int sqrt_limit(static_cast<int>(std::sqrt(max_n)));
  for (int x(1); x <= sqrt_limit; x++)
  {
    const int x2(x * x);
    for (int y(1); y <= sqrt_limit; y++)
    {
      const int y2(y * y);
      int n = (4 * x2) + (y2);
      if (n <= max_n && (n % 12 == 1 || n % 12 == 5))
        p[n] = p[n] ^ true;
      n = (3 * x2) + (y2);
      if (n <= max_n && n % 12 == 7)
        p[n] = p[n] ^ true;
      n = (3 * x2) - (y2);
      if (x > y && n <= max_n && n % 12 == 11)
        p[n] = p[n] ^ true;
    }
  }
  primes.push_back(2);
  primes.push_back(3);
  int a(5);
  for (; a <= sqrt_limit; a += 2)
  {
    if (p[a])
    {
      const int a2(a * a);
      for (int i(a2); i < max_n; i += a2) p[i] = false;
      primes.push_back(a);
    }
  }
  for (; a < max_n; a += 2) if (p[a]) primes.push_back(a);
}

template <class C>
class reverse_wrapper
{
  C &container;
public:
  reverse_wrapper(C &c) : container(c) { }
  decltype(container.rbegin()) begin() { return container.rbegin(); }
  decltype(container.rend()) end() { return container.rend(); }
};

int main()
{
  uint64_t target = 600851475143L;
  int x = (int)sqrt(target);
  std::vector<int> primes; prime_atkin(x, primes);
  for (const auto &it : reverse_wrapper<std::vector<int>>(primes))
  {
    if (target % it == 0)
    {
      std::cout << it << std::endl;
      return 0;
    }
  }
}

Problem 4: C++

Spoiler:Code:
#include <iostream>
#include <set>

#define P 100000

bool is_palindrome(int n)
{
  int i = n;
  int num = 0;
  int p = P;
  do
  {
    num += (i % 10) * p;
    i /= 10; p /= 10;
  }
  while (i > 0);
  return num == n;
}

int main()
{
  std::set<int> palindromes;
  int product;
  for (int i = 999; i > 100; --i)
    for (int j = i - 1; j > 100; --j)
      if (is_palindrome(product = i * j))
        palindromes.insert(palindromes.begin(), product);

  auto it = palindromes.end(); --it;
  std::cout << *it << std::endl;
}

Problem 5: C++

Spoiler:Code:
#include <iostream>
#include <algorithm>

int main()
{
  const int div_test[] = { 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 9 };
  size_t len = sizeof(div_test) / sizeof(div_test[0]);
  for (int i = 2520; ; i += 20)
  {
    if (std::all_of(div_test, div_test + len,
    [&i](int n) { return i % n == 0; }))
    {
      std::cout << i << std::endl;
      return 0;
    }
  }
}

Problem 6: C

Spoiler:Code:
#include <stdio.h>

#define SUM_SQUARES 0
#define SUM_SQUARED 1

int main()
{
  const int max_n = 100;
  int sum[2] = {0, 0};
  for (int i = 1; i <= max_n; ++i)
  {
    sum[SUM_SQUARES] += i * i;
    sum[SUM_SQUARED] += i;
  }
  sum[SUM_SQUARED] *= sum[SUM_SQUARED];
  printf("%d\n", sum[SUM_SQUARED] - sum[SUM_SQUARES]);
}

xornull · 05-06-2014, 05:50 AM

I'm gonna try to do problem 470

EDIT: did half of it, but fuck it

0xDEAD10CC · 05-06-2014, 06:51 PM

I'll try 470 when I'm home

0xDEAD10CC · 05-07-2014, 04:32 AM

Here's a start anyways:

Code:
#include <iostream>
#include <map>

/*
 | Consider a single game of Ramvok:
 |
 | Let t represent the maximum number of turns the game lasts.
 | If t = 0, then the game ends immediately. Otherwise, on each
 | turn i, the player rolls a die. After rolling, if i < t the
 | player can either stop the game and receive a prize equal to
 | the value of the current roll, or discard the roll and try again
 | next turn. If i = t, then the roll cannot be discarded and
 | the prize must be accepted. Before the game begins, t is chosen
 | by the player, who must then pay an up-front cost ct for
 | some constant c. For c = 0, t can be chosen to be infinite
 | (with an up-front cost of 0). Let R(d, c) be the expected
 | profit (i.e. net gain) that the player receives from a single
 | game of optimally-played Ramvok, given a fair d-sided die and
 | cost constant c. For example, R(4, 0.2) = 2.65. Assume that
 | the player has sufficient funds for paying any/all up-front costs.
 |
 | Now consider a game of Super Ramvok:
 |
 | In Super Ramvok, the game of Ramvok is played repeatedly, but with a slight
 | modification. After each game, the die is altered. The alteration process
 | is as follows: The die is rolled once, and if the resulting face has its
 | pips visible, then that face is altered to be blank instead. If the face
 | is already blank, then it is changed back to its original value. After the
 | alteration is made, another game of Ramvok can begin (and during such a ga
 | me,
 | at each turn, the die is rolled until a face with a value on it appears).
 | The player knows which faces are blank and which are not at all times. The
 | game of Super Ramvok ends once all faces of the die are blank.
 |
 | Let S(d, c) be the expected profit that the player receives from an
 | optimally-played game of Super Ramvok, given a fair d-sided die to start
 | (with all sides visible), and cost constant c.
 |
 | For example, S(6, 1) = 208.3.|
 |
 | Let F(n) = ∑(4 <= d <= n) ∑(0 <= c <= n) S(d, c)
 | Calculate F(20), rounded to the nearest integer.
 |
*/

struct Pips
{
  enum e
  {
    Blank = 0,
    Visible
  };
} Pips;

class die_t : public std::map<int, Pips::e>
{
public:
  die_t(unsigned faces) : faces(faces)
  {
    for (unsigned i = 1; i <= faces; ++i)
    {
      m.insert(std::make_pair(i, Pips.Visible));
    }
  }
  /* return die value if not blanked, otherwise Pips.Blank (-1).
   * note: flips current face state on die.
  */
  int operator [](size_t value)
  {
    bool currently_visible = m[value] == Pips.Visible;
    m[value] = (Pips::e)(m[value] ^ Pips.Visible);
    return currently_visible ? value : (int)Pips.Blank;
  }
  int get_faces() const { return faces; }
protected:
  unsigned faces; // number of faces current die has
  std::map<int, Pips::e> m; // face <value, state> map
};

/* retrieve the expected profit from a game of
 * optimally-played game of super ramvok.
 * [example: S(6, 1) = 208.3]
 */
double S(int d, int c)
{
  die_t die(d);
  // TODO
  // determine t
  // find total gain
  // return total gain - (t * c)
  return -1;
}

/* functional sum of expected profits for n-range */
int F(int n)
{
  int result = 0;
  for (int d = 4; d <= n; ++d)
    for (int c = 0; c <= n; ++n)
      result += S(d, c);
  return result;
}

int main()
{
  using namespace std;
  cout << S(6, 1) << endl; // 208.3
}

Got home late from work, I'll continue with this tomorrow. I haven't written anything for the summation, but I'd have to figure out the optimized profit calculation.

Eclipse · 02-15-2015, 10:11 AM

Wow, I forgot all about this thread.

Problem 1: Python

Spoiler:Code:
count = 0
for number in range(1, 1000):
    if number % 3 == 0 or number % 5 == 0:
        count += number
        print(str(number) + " Yes")
    else:
        print(str(number) + " No")
print("Count: " + str(count))

Problem 2: Python

Spoiler:Code:
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
i = 1
count = 0
while fib(i) <= 4000000:
    if fib(i) % 2 == 0:
        count += fib(i)
    i += 1
    print("Total: " + str(count))

Problem 3: Python

Spoiler:Code:
number = 600851475143
i = 2
while i * i < number:
     while number % i == 0:
         number = number / i
     i = i + 1
print(str(int(number)))

Problem 4: Python

Spoiler:Code:
n = 0
s = 100
l = 999
for x in range(l, s, -1):
     for y in range(x, s, -1):
          z = x * y
          if z > n:
               if str(x * y) == str(x * y)[::-1]:
                    n = x * y
print("Largest: " + str(n))

Problem 5: Python

Spoiler:Code:
check = [11, 13, 14, 16, 17, 18, 19, 20] #Remove un-needed numbers

working = True
n = 2520
while working == True: #Find LCM of values in list to get start and step
     if all(n % x == 0 and n != 0 for x in check):
          working = False
          print("Done: " + str(n))
          break
     n += 2520
     print(n)

input()

Problem 6: Python

Spoiler:Code:
theRange = range(1, 101)
total = sum(theRange)
print((total * total) - sum(x * x for x in theRange))

input()

Problem 7: Python

Spoiler:Code:
def primeCheck(x):
    return x > 1 and all(x % y for y in range(2, x))
def main():
    nth = 0
    final = 0
    for x in range(1, 999999999):
        if primeCheck(x) == True and nth <= 10000:
            final = x
            nth += 1
            print("nth: " + str(nth))
        elif nth > 10000:
            break
        print(final)
    print("Final: " + str(final))
main()

input()

Problem 9: Python

Spoiler:Code:
for a in range(1, 1000, 1):
    for b in range(1, 1000 - a, 1):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print("final: " + str(a * b * c))
input()

Problem 10: Python

Spoiler:Code:
def is_prime(n):
    if n <= 3:
        return n >= 2
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(n ** 0.5) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

total = 0

for i in range(1, 2000000):
    if is_prime(i) == True:
        total += i

print(total)
input()

Yeah, I know. I've done some pretty gay shit in these programs.

0xDEAD10CC · 02-22-2015, 03:48 AM

Problem #1 [ Rust ]:

Code:
fn main()
{
  let mut sum = 0;
  let max = 1000;

  let mut x = 3;
  while x < max
  {
    if x % 5 != 0 { sum += x; }
    x += 3;
  }

  x = 5;
  while x < max
  {
    sum += x;
    x += 5;
  }
  println!("Answer: {}", sum);
}

0xDEAD10CC · 03-30-2015, 05:07 AM

I rewrote a solution in C++ for #2:

Code:
#include "stdafx.h"
#include <iostream>

const int &next_fib(int &low, int &high)
{
  int sum = low + high;
  low = high;
  high = sum;
  return high;
}

int _tmain(int argc, _TCHAR *argv[])
{
  int sum = 0, n = 0, fib[] = { 0, 1 };
  while (n < 4000000) if (!((n = next_fib(fib[0], fib[1])) & 1)) sum += n;
  std::cout << sum << std::endl;
  std::cin.get();
}

It's pretty compact, and efficient.

Inori · 03-31-2015, 12:44 PM

Not sure why this is in C/C++ when the problems can be solved with pretty much every language.

Eclipse · 03-31-2015, 01:38 PM

(03-31-2015, 12:44 PM)Nightc||ed Wrote: Not sure why this is in C/C++ when the problems can be solved with pretty much every language.

So why not C/C++? It's fast, low-level, and simple. (Relatively)

Inori · 03-31-2015, 03:06 PM

(03-31-2015, 01:38 PM)Eclipse Wrote: So why not C/C++? It's fast, low-level, and simple. (Relatively)

What about the general coding sub?

Project Euler Solutions Thread
Author Message