Ramblings of a techie

23 August 2010

Project Euler : How many Sundays fell on the first of the month during the twentieth century?

Problem 19

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Solution (in Ruby)

This particular solution does not involve any hard calculations, just run through the dates starting from the first sunday step by 7 days and check if the sunday lies on the first day of the month.

require 'date'
d1, d2, total_sundays = [Date::civil(1901, 1, 1), Date::civil(2000, 12, 31), 0]
d1 +=1 while (d1.wday != 0)
d1.step(d2, 7){|date| total_sundays+=1 if date.day == 1}
puts "Total number of Sundays : #{total_sundays}"

Hover here to see the solution

22 August 2010

Project Euler : Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order.

Problem 52

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Solution(in Ruby)

The solution to this problem is simple and straight forward as shown below. Just convert the problem statement into code with tweaks here and there, we should arrive at the solution smoothly. Do not get scared by the catch statement, its just to break nested loops. Moreover, it is enough to inspect numbers that start with 1. The obvious reason being numbers that begin with 2 get more digits when multiplied by 6 which would defeat our purpose.

INFINITY = 1.0 / 0.0
catch (:done) do
  1.upto(INFINITY) do |i|
    ((10**i)...(2*10**i)).each do |x|
      y = x.to_s.split(//)
      if ( y - (x*2).to_s.split(//) ).size == 0 && y.size == (x*2).to_s.split(//).size &&
         ( y - (x*3).to_s.split(//) ).size == 0 && y.size == (x*3).to_s.split(//).size &&
         ( y - (x*4).to_s.split(//) ).size == 0 && y.size == (x*4).to_s.split(//).size &&
         ( y - (x*5).to_s.split(//) ).size == 0 && y.size == (x*5).to_s.split(//).size &&
         ( y - (x*6).to_s.split(//) ).size == 0 && y.size == (x*6).to_s.split(//).size
        puts "The minimum unique number is #{x}"
        throw :done
      end
    end
  end
end

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the minimal path sum from the left column to the right column.

Problem 82
The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

131	673	234	103	18
201	96	342	965	150
630	803	746	422	111
537	699	497	121	956
805	732	524	37	331

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.

Solution(in Ruby)

This problem has to be attacked in the reverse order ie starting from the right to left. Lets take the last but before column. For each cell in that column, find the minimum possible sum for that cell. To find the minimum possible sum, you will have to find all the 'L' paths explored, their sum has be calculated and stored and the minimum sum has to be stored in that cell. After traversing that entire column, replace that particular column value with the minimal sum. Repeat this process for the immediate left column until you exhaust all the columns reaching the left most column. The minimal value of the leftmost column is the minimal sum which is exactly what we look for.

require 'matrix'

input = ''
file = File.new("/matrix.txt","r")
while (line = file.gets) 
  input += line
end

class Cell
  attr_accessor :min_sum, :value
end

x = Matrix.rows(input.lines.map{|each_line| each_line.split(/,/).map{
      |n|
      c = Cell.new
      c.min_sum = c.value = n.to_i
      c
    }})

MAX = x.row_size

(MAX-2).downto(0) do |column|
  0.upto(MAX-1) do |row|
    val_array = []
    aggregate = x[row,column].value
    val_array << aggregate + x[row,column+1].value
    (row+1).upto(MAX-1) do |down_traverse|
      aggregate += x[down_traverse,column].value
      val_array << aggregate + x[down_traverse,column+1].value
    end
    aggregate = x[row,column].value
    (row-1).downto(0) do |up_traverse|
      aggregate += x[up_traverse,column].value
      val_array << aggregate + x[up_traverse,column+1].value
    end
    x[row,column].min_sum = val_array.min
  end
  0.upto(MAX-1) do |each_row|
    x[each_row,column].value = x[each_row,column].min_sum
  end
end
val_array = []
0.upto(MAX-1) do |val|
  val_array << x[val,0].value
end

puts "The minimum sum is #{val_array.min}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

21 August 2010

Project Euler : Find the longest sequence using a starting number under one million.

Problem 14

The following iterative sequence is defined for the set of positive integers:

n --> n/2 (n is even)
n --> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 --> 40 --> 20 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Solution (in Ruby)

In order to solve this problem, we first need to find a pattern by attacking in the reverse order. If you could see if the number gotten is a power of two, it will diminish all the way upto 1. So its wiser to store their frequency (power of 2 numbers) first in the array. The next interesting property is that if you find the chain count for a number you do not want to find that again. Combining these two properties, we can very well get a linear solution for the input count of 1 million solving the problem within seconds.

MAX_NUM = 1000000
n = Array.new(MAX_NUM)
n[0] = 0
n[1] = 1
counter = 1
index = 1
while (counter < MAX_NUM)
  n[counter] = index
  index+=1
  counter*=2
end
(MAX_NUM-1).downto(2) do |num|
  if n[num]
    next
  end
  rolling = num
  sequence = 0
  while !n[rolling]
    if rolling % 2 == 0
      rolling = rolling/2
    else
      rolling = 3*rolling + 1
    end
    sequence+=1
  end
  n[num] = sequence + n[rolling]
end
puts "The maximum chained number is #{n.index(n.max)}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Calculate the sum of all the primes below two million.

Problem 10
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Solution(in Ruby)
The solution to this problem involves the tricky implementation of prime number functionality. Rest is just a matter of programming.

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
sum = 0
2.upto(2000000) do |num|
  x+=num if is_prime(num)
end
puts "Sum is #{sum}"

Hover here to see the solution

Cheers!
Bragaadeesh

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

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution (in Ruby)

The solution to this problem can be solved by just naked eyes. Anyway, I have presented the code in Ruby.

num = '73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450'
f = ''
num.lines{|x| f += x.chop}
y = f.split(//)
arr = []
0.upto(995) do |index|
  arr << y[index].to_i * y[index+1].to_i * y[index+2].to_i * y[index+3].to_i * y[index+4].to_i
end
puts arr.max

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Find the largest palindrome made from the product of two 3-digit numbers.

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.
Find the largest palindrome made from the product of two 3-digit numbers.

Solution (in Ruby)

The solution to this problem is pretty straight forward. All we had to do is run from 101 to 999 and multiply all the combination and push them into an array and find the maximum value.

arr = []
101.upto(999) do |i|
  101.upto(999) do |j|
    prod = i*j
    arr << prod if prod.to_s == prod.to_s.reverse
  end
end
puts "The largest palindromic number is #{arr.max}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Finding maximum prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Solution (in Ruby)

The solution to this problem is simple. But the main problem here is to construct a rock solid method that returns whether a given number is prime or not. A prime number is a number which divisible by itself and 1 only. Example of prime numbers are 2,3,11,4999. The following is the ruby code to find whether or not a number is prime or not. You may see that I have used a square root of the number as the upper bound, the simple reason being, there cannot be a number greater than the square root of that number being prime (you can get it if you think deep)

Now that we have written a method that returns whether or not a number is prime, the rest of the problem is fairly simple. Again, we have to use the square root property. It is enough if we run the prime number validation from the square root of the number. We will have to traverse all the way to 2 for this. The first occurring prime factor is ofcourse the solution to our problem.

Hover here to see the solution.

Cheers!!
Bragaadeesh.

Project Euler : Finding maximum product in a matrix

Problem 11

In the 20 x 20 grid below, four numbers along a diagonal line have been marked in red.

02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 x 63 x 78 x 14 = 1788696.
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 x 20 grid?

Solution (In Ruby)

The solution to this particular problem is simple and by simple naked eye viewing we can get what we want. But then, if the numbers are almost in the same range and if the matrix size is more then it will become real difficult to identify the maximum number. The following ruby code will find the maximum number. All we are doing here is finding the product of the numbers in the fashion we are supposed to. There is no trick shortcut here. We 'will' have to traverse the entire matrix for finding the product.

require 'matrix'
input =
 '08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
  49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
  81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
  52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
  22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
  24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
  32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
  67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
  24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
  21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
  78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
  16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
  86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
  19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
  04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
  88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
  04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
  20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
  20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
  01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'

x =  Matrix.rows(input.lines.map{|line| line.split.map{|n| n.to_i}})
val = []
0.upto(19) do |r|
  0.upto(19) do |c|
    val << x[r,c] * x[r,c+1] * x[r,c+2] * x[r,c+3] if c<=16
    val << x[r,c] * x[r+1,c] * x[r+2,c] * x[r+3,c] if r<=16
    val << x[r,c] * x[r+1,c+1] * x[r+2, c+2] * x[r+3, c+3] if c<=16 && r<=16
    val << x[r,c] * x[r+1,c-1] * x[r+2, c-2] * x[r+3, c-3] if c>=3 && r<=16
  end
end
puts puts "Maximum product is #{val.max}"

Hover here to see the solution

Cheers!!
Bragaadeesh

20 August 2010

Project Euler : Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000).

Problem 48

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.
Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

Solution (In Ruby)

The solution to this problem becomes simple if we just directly implement with the brute force technique. It just costs two lines in Ruby and the source code is given below.

sum = (1..1000).to_a.inject(0) {|b,i| b+= i**i}.to_s
puts sum.to_s[(sum.size-10)..(sum.size)]

Hover here to see the solution.

Cheers!!
Bragaadeesh

Project Euler : Find the sum of the digits in the number 100!

Problem 20
n! means n x (n -1) x ... x 3 x 2 x 1
Find the sum of the digits in the number 100!

Solution (In Ruby)

All we have to do for the above problem is to write a factorial method. Get the value of 100! and split it into characters and simply add them. Source code is given below.

def fact(n)
  return 1 if n == 0
  n * fact(n-1)
end
puts "Result is #{fact(100).to_s.split(//).inject(0){|b,i| b+i.to_i}}"

Hover here to see the result

Cheers!!
Bragaadeesh

Project Euler : What is the sum of both diagonals in a 1001 by 1001 spiral?

Problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

22 23 24 25

 7  8  9 10

 6  1  2 11

 5  4  3 12

16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

The solution (in ruby)

The problem initially looks complex and makes us want to use matrices. For a small input such as the one given, it will be easier to solve. But when the size of the matrix increases, it is almost impossible to do a proper traversal and find the edge values. This problem can be attacked easily if we are able to decipher the pattern. If you could notice the given matrix carefully, you may find that at each square corners, we have a square number on the right top corner, leave the first value (1), we can sum it later.

For the first level, the corner value is 9 = 3²
For the second level, corner value is 25 = 5²

This keeps going. Our job is to find a forumla at each covering square. The forumla that I arrived at each level in terms of n is [4 * (n² - (n-1)*3/2)]. If you apply the above formula for level 3 we will get 24, for level 5, its 76. If you add these two you will get 100. Now add that with 1, you will get the desired answer as 101. Finding that formula is left to the reader as an excercise (it can be found using finite differences)
Now the source code in ruby,

result = 1
(3..1001).step(2) do |n|
  val += (n*n - 3 * (n-1)/2)*4
end
puts "Result is #{result}"

HOVER HERE TO SEE THE ANSWER

Cheers!!
Bragaadeesh.

Project Euler : Find the sum of all the numbers that can be written as the sum of 5th powers of their digits.

Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

The Solution (in Ruby)

This problem is a bit tricky and can be solved with a trial and error method. Best way to attack this problem is to first arrive at a solution for the 4th power as given in the problem, convince ourselves that the solution that we have coded is correct. Then run the same for 5th powers. Of course the upper bound is a mystery, but who cares you have trial and error to know the answer.

final_result = 0
2.upto(200000) do |x|
  sum = x.to_s.split(//).inject(0){|b,i| b+i.to_i**5}
  final_result += sum if sum == x
end
puts "The magic sum is #{final_result}"

HOVER HERE TO SEE THE SOLUTION!!

Cheers!!
Bragaadeesh

08 August 2010

Google CodeJam 2010 : "Rope Intranet" Problem with solution

Problem

A company is located in two very tall buildings. The company intranet connecting the buildings consists of many wires, each connecting a window on the first building to a window on the second building.
You are looking at those buildings from the side, so that one of the buildings is to the left and one is to the right. The windows on the left building are seen as points on its right wall, and the windows on the right building are seen as points on its left wall. Wires are straight segments connecting a window on the left building to a window on the right building.

You've noticed that no two wires share an endpoint (in other words, there's at most one wire going out of each window). However, from your viewpoint, some of the wires intersect midway. You've also noticed that exactly two wires meet at each intersection point.
On the above picture, the intersection points are the black circles, while the windows are the white circles.
How many intersection points do you see?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing an integer N, denoting the number of wires you see.
The next N lines each describe one wire with two integers A_i and B_i. These describe the windows that this wire connects: A_i is the height of the window on the left building, and B_iis the height of the window on the right building.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of intersection points you see.

Limits

1 ≤ T ≤ 15.
1 ≤ A_i ≤ 10⁴.
1 ≤ B_i ≤ 10⁴.
Within each test case, all A_i are different.
Within each test case, all B_i are different.
No three wires intersect at the same point.

Small dataset

1 ≤ N ≤ 2.

Large dataset

1 ≤ N ≤ 1000.

Sample

Input	Output
`2 3 1 10 5 5 7 7 2 1 1 2 2`	`Case #1: 2 Case #2: 0`

Solution

This is one of the simpler problems that I was able to solve in the Codejam round. Following is the source code.

private long solve(int[] a, int[] b) {
  
  PointMesh p = new PointMesh();
  
  for(int i=0;i<a.length;i++){
   p.add(a[i], b[i]);
  }
  
  return p.intersects;
 }

 class PointMesh{
  long intersects;
  List<Line2D> lineList = new ArrayList<Line2D>();
  Line2D line1 = new Line2D.Double();
  Line2D r = new Line2D.Double();  
  
  void add(int a,int b){
   Point2D p1 = new Point2D.Double(0, a);
   Point2D p2 = new Point2D.Double(10, b);
   Line2D newLine = new Line2D.Double(p1,p2);
   
   for(Line2D eachLine:lineList){
    if(eachLine.intersectsLine(newLine))
     intersects++;
   lineList.add(newLine);
  }
 }

Complete source code : here
Practice inputs : here

Cheers!!
Bragaadeesh.

24 July 2010

Google CodeJam 2010 : "File Fix-it" Problem with solution

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.
A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path:

/home/gcj/finals

This refers to the directory with name "finals" in the directory described by "/home/gcj", which in turn refers to the directory with name "gcj" in the directory described by the path "/home". In this path, there is only one part, which means it refers to the directory with the name "home" in the root directory.
To create a directory, you can use the mkdir command. You specify a path, and thenmkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the "/home/gcj/finals" and "/home/gcj/quals" directories from scratch, you would need four commands:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.
The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)
The next M lines each give the path of one directory that you want to create.
Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of mkdir you need.

Limits

1 ≤ T ≤ 100.
No path will have more than 100 characters in it.
No path will appear twice in the list of directories already on your computer, or in the list of directories you wish to create. A path may appear once in both lists however. (See example case #2 below).
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
The input file will be no longer than 100,000 bytes in total.

Small dataset

0 ≤ N ≤ 10.
1 ≤ M ≤ 10.

Large dataset

0 ≤ N ≤ 100.
1 ≤ M ≤ 100.

Sample

Input	Output
`3 0 2 /home/gcj/finals /home/gcj/quals 2 1 /chicken /chicken/egg /chicken 1 3 /a /a/b /a/c /b/b`

Solution

To attack this problem we can use the famous TRIE data structure. We have already seen enough about this data structure in steps and this becomes so handy in this particular problem.
A TRIE data structure simply stores the data that becomes easy for retrieval. But lets not bother about the retrieval part in this particular problem. We will simply increase our counter whenever we add a new folder to the existing directory structure. The place where we optimize this problem involves in its running time. Whenever we see a new directory structure, we simply pass through it in the length times instead which is linear in time jargons. The solution is given below.

private int solve(String[] already, String[] fresh) {
  Trie trieDSA = new Trie();
  
  for(int i=0;i<already.length;i++){
   trieDSA.insert(already[i],false);
  }
  
  for(int i=0;i<fresh.length;i++){
   trieDSA.insert(fresh[i], true);
  }
  
  return trieDSA.counter;
 }

So clean, isnt it? The TRIE and the Node classes are given below. Remember, please go through my TRIE data structure introduction for few minutes, its definitely a knowledgeable one! Trust me :)

class Node {
 String currentPath;
 boolean marker; 
 Collection<Node> child;
 
 public Node(String path){
  child = new HashSet<Node>();
  marker = false;
  currentPath = path;
 }
 
 public Node subNode(String path){
  if(child!=null){
   for(Node eachChild:child){
    if(eachChild.currentPath.equals(path)){
     return eachChild;
    }
   }
  }
  return null;
 }
}

class Trie{
 private Node root;
 
 public int counter = 0;

 public Trie(){
  root = new Node("");
 }

 public void insert(String pathArray, boolean shouldTrack){
  Node current = root; 
  
  String[] paths = pathArray.substring(1).split("\\/");
  
  if(paths.length==0){
   //DO NOTHING
   current.marker=true;
  }
   
   
  for(int i=0;i<paths.length;i++){
   Node child = current.subNode(paths[i]);
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(paths[i]));
    current = current.subNode(paths[i]);
    if(shouldTrack){
     counter++;
    }
   }
   // Set marker to indicate end of the word
   if(i==paths.length-1)
    current.marker = true;
  } 
 }
}

Complete source code : here
Sample Input : here

Cheers!!
Bragaadeesh.