tags:

views:

125

answers:

4

I've got a 2-dimensional array like this (it represents a timetable):

alt text

Orange cells are lectures and whites are free time. How could I calculate number of free hours between lectures in the same day? (columns are days and rows are hours)

For example, in this table the result should be:
2 for first column
0 for second colum
--> The function returns 2 (because 2+0=2)

A: 

Hi, i am not familiar with java.

Just telling the concept of this,

1. Merge the two array as provide the result as a single.
2. Count the array values.
Karthik
I don't understand your idea. Could you explain it a little more?
genesiss
A: 

Something like this

public int countHoles(boolean[][] timetable){
     int count=0;
     for (int days=0;days<timetable.length;days++){
          for (int i =1;i<timetable[days].length-1;i++){
              if (!timetable[days][i]){
                   int j=i-1; boolean before=false;
                   while(j>=0 || before) {if (timetable[days][j]) before=true; j--;}
                   j=i+1; boolean after=false;
                   while(j<timetables[days].length || after) {if (timetable[days][j]) after=true; j++;}
                   if (before && after) count++;
          }
     }

}

Don't know if the first for works.. but that's the stupid way you can do it.

Fabio F.
That inner if statement fails if you have a two hour gap between lectures.
Paolo
... thank you. Now SHOULD works.
Fabio F.
I think it doesn't work, because there are hours in first dimension of the array, so timetable.lengths returns number of hours, nut number of days.
genesiss
A: 
  1. Use a two dimensional boolean array (true if there is a lecture and false if free.. or something like that)
  2. Traverse the array
  3. If there is a free element, check if the element above and below the current (if value available) is true. If yes, increment a counter
  4. After traversal, the counter gives you the result.

Try to implement yourself and let us know if you face any issue.

bdhar
As per Fabio's original attempt, point 3 fails if there is more than a one hour gap between lectures
Paolo
+5  A: 
schedule = ['11010100','01100000'] #original schedule
freehours = [day.strip('0').count('0') for day in schedule]

Algorithm: convert to a string like '11010100', strip 0 chars from start and end ('110101') and count the 0 chars (2) that remain. Descriptively, all periods between the first and last filled period which are not filled are your free periods.

Extra geekery: More efficiently, if working in C++ with an array of booleans: get an iterator for the array, run it through any 0 vals at the beginnning. Declare another and iterate backward from the end over any 0 vals. Then iterate the start iterator forward, counting any zeroes until you reach the end iterator.

However, if you had a very long list, it might be more efficient to only iterate forward, storing the position of the last 1 and adding the size of each space to a counter when encountering the next 1. This way the memory is read in contiguous blocks and the summation could be performed on a streaming input, even writing running totals to a socket.

Phil H