Oxaric’s Blog

A compendium of amazing things…

Posts Tagged ‘answer’

« Previous Entries

Euler Project Problem #104 Solution

Posted by oxaric on November 24, 2008

It uses C.

Click to directly download euler-solution-104.c
// filename 'euler-solution-104.c'
// By: Louis Casillas, oxaric@gmail.com

// Euler Problem #104
// Find the Fibonacci sequence for which the first nine digits and the last nine digits are 1-9 pandigital

#include <stdio.h>
#include <gmp.h>

char number_string[100000];

char isPandigital( unsigned long int num )
{
   if ( num < 123456789 )
   {
      return 0;
   }

   char num_of_unique_digits = 0;

   char number_array[9];

   unsigned long int temp = num;

   int i;
   int j;

   for ( i = 0; i < 9; i++ )
   {
      number_array[i] = temp - ((temp / 10) * 10);
      if ( number_array[i] == 0 )
      {
         return 0;
      }

      temp /= 10;
   }   

   char is_unique = 1;
   
   for ( i = 0; i < 9; i++ )
   {
      for ( j = 0; j < 9; j++ )
      {
         if ( i != j )
         {
            if ( number_array[i] == number_array[j] )
            {
               is_unique = 0;
            }
         }
      }
      
      if ( is_unique )
      {
         num_of_unique_digits++;
      }

      is_unique = 1;
   }   

   if ( num_of_unique_digits == 9 )
   {
      return 1;
   }
   else
   {
      return 0;
   }
}

int numOfDigits( mpz_t num )
{
   int num_of_digits = 0;
   
   char *number_pointer;
   mpz_get_str( number_string, 10, num );
   
   number_pointer = number_string;

   while( *number_pointer != '' )
   {
      num_of_digits++;
      number_pointer++;
   }

   return num_of_digits;
}

char areBothSidesPandigital( mpz_t num )
{
   mpz_t mod;
   mpz_init_set_str( mod, "1000000000", 10 );

   mpz_t temp;
   mpz_init( temp );

   unsigned long int number_group = 0;

   mpz_mod( temp, num, mod );

   number_group = mpz_get_ui( temp );

   if ( isPandigital( number_group ) )
   {
      mpz_ui_pow_ui( temp, 10, (numOfDigits( num ) - 9) );

      mpz_tdiv_q( temp, num, temp );

      number_group = mpz_get_ui( temp );

      if ( isPandigital( number_group ) )
      {
         mpz_clear( temp );
         mpz_clear( mod );

         return 1;
      }
   }
   
   mpz_clear( temp );
   mpz_clear( mod );

   return 0;
}

int main()
{
   mpz_t num1;
   mpz_init_set_str( num1, "1", 10 );

   mpz_t num2;
   mpz_init_set_str( num2, "1", 10 );

   char add_to_first = 1;
   char are_we_up_to_ten_digits = 0;
   int current_sequence = 2;

   while( 1 )
   {
      current_sequence++;

      if ( add_to_first )
      {
         mpz_add( num1, num1, num2 );
         add_to_first = 0;
      }
      else
      {
         mpz_add( num2, num1, num2 );
         add_to_first = 1;
      }

      if ( add_to_first )
      {
   //      printf( "\nNumber of digits: %d\n", numOfDigits( num2 ) );
         if ( areBothSidesPandigital( num2 ) )
         {
            printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
            return 0;
         }
      }
      else
      {
         //printf( "\nNumber of digits: %d\n", numOfDigits( num1 ) );
         if ( areBothSidesPandigital( num1 ) )
         {
            printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
            return 0;
         }
      }      
   }

   //mpz_ui_pow_ui( temp, base, exp );

   //mpz_out_str( out_file, 10, temp );

   //printf("\n");
   //mpz_out_str( stdout, 10, temp );
   //printf("\n\n");

   printf("\n\n");

   return 0;
}

Posted in C/C++, Programming, Project Euler | Tagged: , , , , , , | 2 Comments »

Euler Project Problem #102 Solution

Posted by oxaric on November 24, 2008

It uses C.


Click to directly download euler-solution-102.c
Right click to save the needed data file triangles.txt

// filename 'euler-solution-102.c'
// By: Louis Casillas, oxaric@gmail.com

// Euler Problem #102
// Determine which triangles encompass the origin.
// The file is 'triangles.txt'

#include <stdio.h>

char doesLineCrossXAxis( x1, x2 )
{
   if ( ((x1 < 0) && (x2 > 0)) || ((x1 > 0) && (x2 < 0)) )
   {
      return 1;
   }
   
   return 0;
}

char doesLineCrossYAxis( y1, y2 )
{
   if ( ((y1 < 0) && (y2 > 0)) || ((y1 > 0) && (y2 < 0)) )
   {
      return 1;
   }
   
   return 0;
}

char doesTriangleContainOrigin( x1, y1, x2, y2, x3, y3 )
{
   char does_line1_cross_x_axis = 0;
   char does_line2_cross_x_axis = 0;
   char does_line3_cross_x_axis = 0;

   char num_lines_cross_x_axis = 0;

   // line1
   if ( doesLineCrossXAxis( x1, x2 ) )
   {
      does_line1_cross_x_axis = 1;
      num_lines_cross_x_axis++;
   }

   // line2
   if ( doesLineCrossXAxis( x2, x3 ) )
   {
      does_line2_cross_x_axis = 1;
      num_lines_cross_x_axis++;
   }

   // line3
   if ( doesLineCrossXAxis( x1, x3 ) )
   {
      does_line3_cross_x_axis = 1;
      num_lines_cross_x_axis++;
   }

   // two of the lines must cross the x-axis to make it possible to contain the origin
   if ( num_lines_cross_x_axis < 2 )
   {
      return 0;
   }

   float line1_slope = 0;
   float line2_slope = 0;
   float line3_slope = 0;

   float line1_x_intercept = 0;
   float line2_x_intercept = 0;
   float line3_x_intercept = 0;

   if ( does_line1_cross_x_axis )
   {
      line1_slope = (1.0 * y1 - y2) / (x1 - x2);
      line1_x_intercept = y1 - ( 1.0 * line1_slope * x1 );      
   }

   if ( does_line2_cross_x_axis )
   {
      line2_slope = (1.0 * y2 - y3) / (x2 - x3);
      line2_x_intercept = y2 - ( 1.0 * line2_slope * x2 );
   }

   if ( does_line3_cross_x_axis )
   {
      line3_slope = (1.0 * y1 - y3) / (x1 - x3);
      line3_x_intercept = y3 - ( 1.0 * line3_slope * x3 );
   }

   if ( ((line1_x_intercept > 0) && (line2_x_intercept < 0)) ||
             ((line2_x_intercept > 0) && (line3_x_intercept < 0)) ||
             ((line1_x_intercept > 0) && (line3_x_intercept < 0)) ||
        ((line1_x_intercept < 0) && (line2_x_intercept > 0)) ||
             ((line2_x_intercept < 0) && (line3_x_intercept > 0)) ||
             ((line1_x_intercept < 0) && (line3_x_intercept > 0))

           )
   {
      return 1;
   }

   return 0;
}

int main()
{
   int number_holder = 0;
   char current_point = 1;
   char current_char;
   char is_negative_number = 0;
   int num_that_contain_origin = 0;

   int x1 = 0;
   int y1 = 0;
   int x2 = 0;
   int y2 = 0;
   int x3 = 0;
   int y3 = 0;

//printf( "\n\n%d\n\n", (int)doesTriangleContainOrigin( -340, 495, -153, -910, 835, -947 ) );

   FILE *in_file = fopen("triangles.txt", "rt");

   while( (current_char = fgetc( in_file )) != EOF )
   {   
      if ( current_char == '\r' )
      {
      }
      else if ( current_char == '\n' )
      {
         if ( is_negative_number )
         {
            number_holder *= -1;
         }
         y3 = number_holder;
         number_holder = 0;
         is_negative_number = 0;
         
//         printf( "\n\n%d\t%d\t%d\t%d\t%d\t%d", x1, y1, x2, y2, x3, y3 );
//getchar();

         if ( doesTriangleContainOrigin( x1, y1, x2, y2, x3, y3 ) )
         {
            num_that_contain_origin++;
         }

         current_point = 1;

         x1 = 0;
         y1 = 0;
         x2 = 0;
         y2 = 0;
         x3 = 0;
         y3 = 0;
      }
      else if ( current_char == ',' )
      {
         if ( is_negative_number )
         {
            number_holder *= -1;
         }

         switch( current_point )
         {
            case 1:
               x1 = number_holder;
            break;

            case 2:
               y1 = number_holder;
            break;

            case 3:
               x2 = number_holder;
            break;

            case 4:
               y2 = number_holder;
            break;

            case 5:
               x3 = number_holder;
            break;
         }

         current_point++;

         number_holder = 0;
         is_negative_number = 0;
      }
      else
      {
         // ascii value of '-' is 45, base 10
         
         if ( (int)current_char == 45 )
         {
            is_negative_number = 1;
         }
         else
         {
            number_holder *= 10;
            number_holder += (current_char - '0');
         }
      }
   }

   printf( "\n\nThe number of triangles that contain the origin is: %lu\n\n", num_that_contain_origin );
   
   fclose( in_file );

   printf("\n\n");

   return 0;
}

Posted in C/C++, Programming, Project Euler | Tagged: , , , , , , | Leave a Comment »

Euler Project Problem #99 Solution

Posted by oxaric on November 24, 2008

It uses C.


Click to directly download euler-solution-99.c
Right click to save the needed data file base_exp.txt

// filename 'euler-solution-99.c'
// By: Louis Casillas, oxaric@gmail.com

// Euler Problem #99
// Determine which line number that has the greatest numerical value.
// Calculate by: first number ^ second number
// The file is 'base_exp.txt'

#include <stdio.h>
#include <gmp.h>

int main()
{
   mpz_t temp_result;
   mpz_init( temp_result );

   mpz_t max_result;
   mpz_init( max_result );
   mpz_set_ui( max_result, 0 );

   unsigned long int base;
   unsigned long int exp;
   unsigned long int number_holder = 0;
   
   unsigned int line_number = 0;
   unsigned int max_line_number = 1;

   char current_char;

   FILE *in_file = fopen("base_exp.txt", "rt");

   while( (current_char = fgetc( in_file )) != EOF )
   {   
      if ( current_char == '\r' )
      {
      }
      else if ( current_char == '\n' )
      {
         exp = number_holder;
         number_holder = 0;
         line_number++;

         mpz_ui_pow_ui( temp_result, base, exp );
         
         if ( mpz_cmp( temp_result, max_result ) > 0 )
         {
            mpz_set( max_result, temp_result );
            max_line_number = line_number;
         }
         
         printf( "\nline number: %d\n", line_number );

         base = 0;
         exp = 0;
      }
      else if ( current_char == ',' )
      {
         base = number_holder;
         number_holder = 0;
      }
      else
      {
         number_holder *= 10;
         number_holder += (current_char - '0');
      }
   }

   printf( "\n\nThe max line number is: %lu\n\n", max_line_number );

   //mpz_ui_pow_ui( temp, base, exp );

   //mpz_out_str( out_file, 10, temp );

   //printf("\n");
   //mpz_out_str( stdout, 10, temp );
   //printf("\n\n");
   
   fclose( in_file );

   printf("\n\n");

   return 0;
}

Posted in C/C++, Programming, Project Euler | Tagged: , , , , , , | Leave a Comment »

Euler Project Problem #97 Solution

Posted by oxaric on November 24, 2008

It uses Scheme.


Click to directly download euler-solution-97.sc

; filename 'euler-solution-97.sc'
; By: Louis Casillas, oxaric@gmail.com

; Euler Problem #97
; Find the last ten digits of the non-Mersenne prime: 28433 \u00d7 27830457 + 1.

(define (ToTheSecondPower n) 
        (* n n)
)

(define (Power x n)
        (if (= n 0)
            1
            (if (= (modulo n 2) 0)
                (ToTheSecondPower (Power x (/ n 2)))
                (* x (Power x (- n 1)))
            )
        )
)

(+ (* (Power 2 7830457) 28433) 1)

Posted in Programming, Project Euler, Scheme | Tagged: , , , , , , | Leave a Comment »

Euler Project Problem #92 Solution

Posted by oxaric on November 24, 2008

It uses Ruby.


Click to directly download euler-solution-92.rb

# filename 'euler-solution-92.rb'
# By: Louis Casillas, oxaric@gmail.com

# Euler Problem #92
# A number chain is created by continuously adding the square of the
# digits in a number to form a new number until it has been seen before.
# Any chain that arrives at 1 or 89 will become stuck.
# How many starting numbers below ten million will arrive at 89?

def whatDoesTheChainLoopAt?( num )
   new_number = num

   while( (new_number != 1) && (new_number != 89) )
      temp_s = new_number.to_s
      new_number = 0

      for i in (0...temp_s.size)
         new_number += (temp_s[ i, 1 ].to_i ** 2)
      end
   end

   new_number
end

total = 0

for i in (1...10000000)
   if ( whatDoesTheChainLoopAt?( i ) == 89 )
      total += 1
   end
end

puts "The number of starting numbers that loop with 89 is: " + total.to_s

Posted in Programming, Project Euler, Ruby | Tagged: , , , , , , | Leave a Comment »

Euler Project Problem #84 Solution

Posted by oxaric on November 24, 2008

It uses Ruby.


Click to directly download euler-solution-84.rb

# filename 'euler-solution-84.rb'
# By: Louis Casillas, oxaric@gmail.com

# Euler Problem #84
# In the game, Monopoly, find the three most popular squares when using two 4-sided dice.

def take_community_chess_card()
   
   case @community_chess_card_position

      when 3
         @player_position = 0
   
      when 9
         @player_position = 10
   end
   
   @community_chess_card_position += 1

   if ( @community_chess_card_position == 12)
      @community_chess_card_position = 0
   end

   nil
end

def take_chance_card()
   case @chance_card_position

      when 0
         @player_position = 0
   
      when 1
         @player_position = 10
      
      when 2
         @player_position = 11

      when 3
         @player_position = 24

      when 4
         @player_position = 39

      when 5
         @player_position = 5

      when 6, 7
         if (@player_position < 5)
            @player_position = 5
         else
            if (@player_position < 15)
               @player_position = 15
            else
               if (@player_position < 25)
                  @player_position = 25
               else
                  if (@player_position < 35)
                     @player_position = 35
                  else
                     @player_position = 5
                  end
               end
            end
         end

      when 8
         if (@player_position < 12)
            @player_position = 12
         else
            if (@player_position < 28)
               @player_position = 28
            else
               @player_position = 12
            end
         end

      when 9         
         @player_position = @player_position - 3

         if (@player_position == 33)
            take_community_chess_card()
         end
   end
   
   @chance_card_position += 1

   if ( @chance_card_position == 12)
      @chance_card_position = 0
   end

   nil

end

board = Array.new(40)

for i in (0..39)
   board[ i ] = 0
end

@player_position = 0
@community_chess_card_position = 0
@chance_card_position = 0

number_of_doubles = 0
size_of_dice = 4

NUMBER_OF_MOVES = 100000000

for i in (1..NUMBER_OF_MOVES)
   dice1 = rand(size_of_dice) + 1
   dice2 = rand(size_of_dice) + 1

   if (dice1 == dice2)
      number_of_doubles += 1
   end

   if (number_of_doubles == 3)
      @player_position = 10
   else
      @player_position += (dice1 + dice2)

      if (@player_position > 39)
         @player_position = @player_position - 40
      end

      case @player_position
         when 2, 17, 33
            take_community_chess_card()

         when 7, 22, 36
            take_chance_card()

         when 30
            @player_position = 10
      end
   end
   

   board[ @player_position ] = board[ @player_position ] + 1   
end

for i in (0..39)
   puts "Square: " + i.to_s + " --- Probability: " + ((board[ i ] / (NUMBER_OF_MOVES * 1.0)) * 100).to_s
end

puts "---"
puts

max = 0
max_i = 0
for i in (0..39)
   if (board[i] > max)
      max = board[i]
      max_i = i
   end
end

puts "The biggest percentage is at square: " + max_i.to_s

board[ max_i ] = 0

max = 0
max_i = 0
for i in (0..39)
   if (board[i] > max)
      max = board[i]
      max_i = i
   end
end

puts "The second biggest percentage is at square: " + max_i.to_s

board[ max_i ] = 0

max = 0
max_i = 0
for i in (0..39)
   if (board[i] > max)
      max = board[i]
      max_i = i
   end
end

puts "The third biggest percentage is at square: " + max_i.to_s

Posted in Programming, Project Euler, Ruby | Tagged: , , , , , , | Leave a Comment »

« Previous Entries