Stack Implementation in C++ through an array

Stack is one of the important data structures that every computer programmer should be aware of. It follows the simple LIFO (Last In First Out) principle. Implementation of stack can be done in many ways. One of the simplest way is using Arrays. Here an array is initialized to a maximum value first, lets call it capacity. As and when we push elements onto the array, its size will get increased. When the size reaches the capacity, we should ideally double the array size. But in the code given below I am not doing that.

Cheers!!
Bragaadeesh.

Motivation

In his book, 7 Habits of Highly Effective People, Stephen Covey tells the story of a woodcutter who took a new job for a timber merchant. The woodcutter was determined to do his best, so when the employer presented him with an axe he went straight to work. The first day the woodcutter brought 18 trees to the boss. “Congratulations,” the boss said. “Keep it up!” With this motivational encouragement the cutter went out the next day with even more determination. However, at the end of the day he could only bring back 15 trees. The third day he worked harder still, yet try as he might only 10 trees could be felled. So it went; each succeeding day yielded fewer trees. “I must be losing my strength,” the woodcutter thought. He decided to approach his boss to apologize for his unexplained deteriorating output. “When was the last time you sharpened your axe?” the boss asked. The woodcutter stared dumbfounded. “Sharpen my axe! I had no time to sharpen my axe. I have been too busy trying to cut trees!”

It is possible to be too busy to maintain your effectiveness. Whatever your personal situation, this might be the right time to ask yourself if it is time to “sharpen your axe.”

Cheers!!
Bragaadeesh.

Project Euler : Considering natural numbers of the form, ab, finding the maximum digital sum.

Problem 56

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

Solution (in Ruby)

Nothing much to discuss about the solution, I've implemented it directly as given in the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Evaluate the sum of all amicable pairs under 10000.

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.

Solution (in Ruby)

For this problem, it is vital to write an efficient method to find the sum of divisors of a number. The divisor finding logic is same as the one stated in Problem 12. Rest is an as-is implementation of the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many letters would be needed to write all the numbers in words from 1 to 1000?

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.

Solution (in Ruby)

We will have to first try to come out with the unique words that are present in the numbers. We start with the ones which are one, two upto nine. Then the elevens starting from eleven to nineteen. Then the tens, twenties upto nineties. We should also define a hundred and thousand. After that the logic is directly readable from the ruby code given below.


Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Discover all the fractions with an unorthodox cancelling method.

Problem 33

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Solution (in Ruby)

This problem unlike the other problems does not ask us to go to millions and trillions and the scope is such that this can be solved in the least running time. All this problem demands careful inspection of the problem statement itself. Its clear we need to iterate through numbers from 1 to 99. For the outer loop (numerator), its enough we run from 12 since its the first double digit number which does not end with a 0 or their digits being equal. We run upto 97 since the numerator cannot be greater than equal to denominator since the fraction should be less than 1
Same is the case for the inner loop. We should always continue to the next iteration if the last number of either numerator or denominator is 0, or if both digits or equal or if the numerator is greater than or equal to denominator. Rest of the solution is just a language specific implementation of finding whether the two different fractions are indeed equal.

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : What is the value of the first triangle number to have over five hundred divisors?

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?

Solution (in Ruby)

The main aspect about this solution is finding an efficient way to calculate the number of divisors. Lets take a simple example. The number 6 has 4 divisors namely 1,2,3,6. For this number its enough we run upto the Square root of 6 which is integer floored value to be 2. 1 is divisible by 6 by 6 times, so 1 and 6 are divisors. 2 is divisble by 6 3 times, so 2 and 3 are divisors. So totally we have 4 divisors.
There is one more point to be noted here. For a square number such as 16, if we apply this formula, we will end up getting 6 divisors --> 1, 2, 4, 4, 8, 16. You may see we may calculate 4 twice. But it occurs only once for a square number. This special case is handled in the solution given below. The rest is an as-is implementation of the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : How many Lychrel numbers are there below ten-thousand?

Problem 55

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

Solution (in Ruby)

This problem had a higher difficulty rating in project euler problems. But it was one of the straightforward ones that I solved it with Ruby. Nothing to say about the solution, its an as-is implementation of the problem statement.


Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Concealed Square

Problem 206

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

Solution (in Ruby)

Before we look at the optimal solution, lets look at what brute force has to offer us. There are nine slots in the number which leaves us to iterate on 1000000000 times (1 trillion times). This is simply not doable, it will take years to run through this loop. So brute force is out of the equation. We need to find a digit or two to reduce the loop count.

So its wiser to look at some of the property of square numbers. Square number ending with zero, has to have the previous digit also 0, which leaves us with only 8 slots now. One more property is that the square root for this particular number has to start with 1. The reason is in finding the square root, we need pair numbers from the back and need to find the square root of the first hanging digit/pair. In this case its 1. Square root 1 is 1 and its enough to inspect only one digit. This leaves us 1 more slot less in our problem. And one final property is the ending digit. Here its 9. Only numbers that end with 3 and 7 produces 9. This leaves our permutation reduce by one more digit (since its enough for us to step 10 times every time in the loop). We need to find the lower bound of the number which is 10203040506070809. The square root of this number is 101010101. We shall end with either 3 or 7. And start with the maximum digit in that sequence which is 199999999. Thats it!! Now we've shortened the problem to be solved within seconds!!


Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many circular primes are there below one million?

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?

Solution (in Ruby)

The solution to this problem invovles one performance enhancement in finding the prime numbers. If you want to check whether the same number is prime more than once in your program, it is highly important to have a look on the running time. That is why I am using an array to store the number as the index itself. This would make sure that the number given is found to be prime or not in O(1) time. Rest of the solution did what the problem statement demands


Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

Problem 36

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Solution (in Ruby)

The solution is one the simplest and straightforward when implemented in Ruby.

sum = 0
1.upto(1000000) do |num|
  sum+=num if num.to_s == num.to_s.reverse && num.to_s(base=2) == num.to_s(base=2).reverse
end
puts "Sum is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many triangle words does the list of common English words contain?

Problem 42

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Solution (in Ruby)

The main place where we need to attack this problem involves in finding the roots of the quadratic equation. We know the roots of the quadratic equation

If you apply this equation to the simple formula to find the triangle numbers, we will find out that a = 1 and b = 1 and c will be twice the triangle number. There will be two roots possible, one will be positive and other will be negative. It is enough to find the positive root. If that root is a whole number, then that will be a proper triangle number.

names = File.new("/words.txt","r").gets.split(/,/)
count = 0
names.each do |n|
  value = n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64}
  positive_root = (-1+Math.sqrt(1+8*value))/2
  count+=1 if positive_root == positive_root.ceil
end
puts "The total number of words is #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Using an efficient algorithm find the maximal sum in the triangle?

Problem 67

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 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

Solution (in Ruby)

To attack this problem, we should think in the reverse order as exploring all the possible routes would take 20 billion years to solve this problem!! We should start at the bottom but before level. For each number in that level, replace with the sum of that number and the maximum of the below two numbers. Do this for each level and bingo! we will arrive at the solution. So easy now isnt it? :) Thats 'after' you know it. Ruby code is presented below. There is another problem (Problem 18) (the minor input version) which also is the same one like the one above.

input = ''

f = File.new("/triangle.txt","r")
while (line = f.gets)
  input += line
end

class Row
  attr_accessor :index, :data
end

index = 0
triangle =  input.lines.map{|each_line| r = Row.new; r.index = index; r.data=[]; index+=1; sub_index = 0
  each_line.split.map{|n| r.data[sub_index] = n.to_i; sub_index+=1}; r}

(triangle.size - 2).downto(0) do |n|
  0.upto(triangle[n].data.size-1) do |sub_index|
    triangle[n].data[sub_index] += [ triangle[n+1].data[sub_index+1] , triangle[n+1].data[sub_index] ].max
  end
end

puts "The maximum value is #{triangle[0].data}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

Problem 27

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
Using computers, the incredible formula  n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.
Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

Solution (in Ruby)

Normally we would want to run through 1000 numbers in the outer loop and 1000 numbers in the inner loop to attack this problem. But we can significantly reduce that by just running 168 x 168 times by calculating the number of primes below 1000 first. This would reduce our running time. The rest of the solution is an as-is implementation of the problem statement.

def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end

max_primes = []; a_s = []; b_s = []
INFINITY = 1.0/0.0

primes_upto_1000 = []
1.upto(999) do |each_num|
  primes_upto_1000 << each_num if is_prime(each_num)
end

primes_upto_1000.each do |a|
  primes_upto_1000.each do |b|
    each_prime = 0
    0.upto(INFINITY) do |n|
      break unless is_prime(n**2 - a*n + b)
      each_prime+=1 
    end
    max_primes<<< -a ; b_s << b
  end
end

puts "Product of a and b is #{a_s[max_primes.index(max_primes.max)] * b_s[max_primes.index(max_primes.max)]}" 

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : What is the total of all the name scores in the file of first names?

Problem 22

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 53 = 49714.
What is the total of all the name scores in the file?

Solution (in Ruby)

All we had to do is read the file convert all the values into an array and sort it. Then for each word we need to apply the rule as stated in the problem. If you could look at the code inside the loop, i would be ripping the starting and trailing quotes '"' and then converting them to index numbers. ie A for 1, B for 2 upto Z for 26. Rest is self explanatory.

names = File.new("/names.txt","r").gets.split(/,/).sort
sum = 0
index = 1
names.each do |n|
  sum += n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64} * index
  index+=1
end
puts "The total of all the name scores is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh.