Javaist Blog

Protected: Sudoku Solver in Python

admin — Mon, 07 Dec 2009 23:41:03 +0000

Fruit Counting with Balls and Sticks

admin — Fri, 30 Oct 2009 15:59:59 +0000

Here is a question that may puzzle you initially. But it has a fairly simple solution. Consider you have 3 kinds of fruits Apples, Bananas, and Coconuts. Assume that you have an unlimited source. Then how many ways are there to pick 4 fruits? There are 15 for this case.

4A,4B,4C
3A1B,3A1C,3B1A,3B1C,3C1A,3C1B
2A1B1C,2B1A1C,2C1A1B
2A2B,2B2C,2A2C

Now think about another puzzle. How many ways to arrange 4 balls and 2 sticks? We can see that 4 balls and 2 sticks consume 6 spaces. Within these 6 spaces then we can arrange 4 balls, then the sticks go to empty spaces. So there are
= 15 ways.

A representation looks like this then
OO|O|O
Where O is a ball and | is a stick.

Now, there is a striking similarity between these two puzzles. Observe that the sticks part the balls into 3 groups. In every representation there are three groups of balls. So, balls and sticks question asks the same as the fruit question. There are 3 kinds or groups of fruits to choose from. So the general answer for the fruit problem is

or where r is the number of kinds of fruits and n is the number of fruits to be chosen. The fruit question is the same as n balls r-1 sticks question, since r kinds corresponds to r-1 sticks as r-1 sticks part the n to r groups.

Project Euler Problem 12 in Scheme

admin — Tue, 20 Oct 2009 20:30:29 +0000

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th 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?

Here is the code in Scheme

^?View Code SCHEME

(define (triangular-check no)
  (trian-helper no 1 2))
 
(define (trian-helper no start count)
  (cond ((> count no) start)
        ((> (divisors start) 500) start)
        (else (trian-helper no (+ count start) (+ 1 count)))
        ))
 
(define (divisors no)
  (div-helper no 1 0))
(define (div-helper no start count)
  (cond ((> start (sqrt no)) (* 2 count))
        ((= (remainder no start) 0)
          (div-helper no (+ 1 start) (+ 1 count)))
        (else (div-helper no (+ 1 start) count))
        ))
(triangular-check 15000)

Project Euler Problem 12 in Java

admin — Tue, 20 Oct 2009 19:38:11 +0000

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th 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?

Here is the code in Java

^?View Code JAVA

public class Problem12
{
    private static int numberT = 0;
    private static int divCount = 0;
    public static void main(String args[])
    {
        for(int i= 1; i<30000; i++ )
        {
 
 
          numberT = numberT + i;
          if(check(numberT)>500)
          {
              System.out.println(numberT);
              break;
          }
        }
    }
    public static int check(int x)
    {
        divCount = 0;
        for(int j = 1; j<= Math.sqrt((double) x); j++)
        {
            if(x%j == 0)
                divCount++;
        }
        return 2*divCount;
    }
}

Project Euler Problem 2 in Scheme

admin — Tue, 20 Oct 2009 19:36:05 +0000

^?View Code SCHEME

(define (even-fib limit)
  (even-fib-helper 1 2 limit 0))
 
(define (even-fib-helper first second limit sum)
  (cond ((> first limit) sum)
        ((= (remainder first 2) 0)
              (even-fib-helper second (+ first second)  limit (+ first sum)))
        (else  (even-fib-helper second (+ first second) limit sum))
        ))
 
(even-fib 4000000)

Project Euler Problem 2 in Ruby

admin — Tue, 20 Oct 2009 19:34:43 +0000

^?View Code RUBY

sum = 0
second = 2
first = 1
swap = 0
for test in 1..99
  if first % 2 == 0 and first < 4000000
    sum = sum + first
  end
  swap = first
  first = second
  second = swap + second
end
puts sum
gets

Project Euler Problem 2 in Java

admin — Tue, 20 Oct 2009 19:32:54 +0000

^?View Code JAVA

 
public class Problem2
 
{
 
    private static double sum = 0;
    private static double number[] = new double[2];
    private static double swap;
 
 
    public static void main(String args[])
    {
        number[0]=1;
        number[1]=2;
        for(int i = 2; i< 99; i++)
        {
            swap = number[1];
            number[1] = number[0] + number[1];
            number[0] =swap;
            check(number[0]);
        }
        System.out.print((int) sum);
 
    }
    public static void check(double x)
    {
        if(x% 2 == 0 && x<4000000)
            sum = sum + x;
 
 
    }
 
}

Project Euler Problem 1 in Scheme

admin — Tue, 20 Oct 2009 19:29:13 +0000

^?View Code SCHEME

 
(define (3-or-5 limit)
  (3-or-5-helper limit 0 0))
 
(define (3-or-5-helper limit start sum)
  (cond ((= limit start) sum)
        ((and (= (remainder start 3) 0)
            (> (remainder start 5) 0))
                (3-or-5-helper limit (+ 1 start) (+ start sum)))
        ((and (= (remainder start 5) 0)
            (> (remainder start 3) 0))
                (3-or-5-helper limit (+ 1 start) (+ start sum)))
        ((= (remainder start 15) 0)
            (3-or-5-helper limit (+ 1 start) (+ start sum)))
        (else (3-or-5-helper limit (+ 1 start) sum))
        ))
 
(3-or-5 1000)

Project Euler Problem 1 in Ruby

admin — Tue, 20 Oct 2009 19:27:46 +0000

^?View Code RUBY

sum = 0
for count in 1...1000
  if count % 3 == 0
    sum = sum + count
  elsif count % 5 == 0
    sum = sum + count
  end
end
puts sum
gets

Project Euler Problem 1 in Python

admin — Tue, 20 Oct 2009 19:26:20 +0000

^?View Code PYTHON

sum3 = 0
sum5 = 0
sum15 = 0
for x in range(0,1000,3):
        sum3 = sum3 + x
for x in range(0,1000,5):
        sum5 = sum5 + x
for x in range(0,1000,15):
        sum15 = sum15 + x
result = sum3 + sum5 - sum15
print result
raw_input()