This solution was provided by Bonny Biswas.
int size;
size = Integer.parseInt(stdin.readLine());
if (size > 0)
Student[] student_list = new Student[size];
else {
System.out.println("Array size must be positive");
exit(0);
}
for (int i = 0; i < size; i++)
{
// read in data for student
String name = stdin.readLine();
int mark = Integer.parseInt(stdin.readLine());
// constructor call
student_list[i] = new Student(name,mark);
}
void printMulti(int num, char item)
{
// prints out a string of num items
String str;
for (int i = 0; i < num; i++)
{
str += item;
}
System.out.println(str);
}
void printBars(int[] count)
{
for (int i = 0; i < count.length; i++)
{
printMulti(count[i],'*');
}
}
This is a first inefficient way of solving the problem..
boolean valid_position(boolean[][] board, int row, int column)
{
if (board[i][j])
return false;
else {
int i,j;
// check each square in the column
j = column;
for (i = 0; i < board.length; i++) {
if (board[i][j])
return false;
}
// check each square in the row
i = row;
for (j = 0; j < board[i].length; j++) {
if (board[i][j])
return false;
}
//check diagonals
int incr_i, incr_j;
// left half of diagonal of negative slope
incr_i = -1;
incr_j = -1;
i = row + incr_i;
j = column + incr_j;
while ( i < board.length && j < board[i].length && i>=0 && j>=0)
{
if (board[i][j]) return false;
i += incr_i;
j += incr_j;
}
// left half of diagonal of positive slope
incr_i = 1;
i = row + incr_i;
j = column + incr_j;
while ( i < board.length && j < board[i].length && i>=0 && j>=0)
{
if (board[i][j]) return false;
i += incr_i;
j += incr_j;
}
// right half of diagonal of negative slope
incr_j = 1;
i = row + incr_i;
j = column + incr_j;
while ( i < board.length && j < board[i].length && i>=0 && j>=0)
{
if (board[i][j]) return false;
i += incr_i;
j += incr_j;
}
// right half of diagonal of positive slope
incr_i = -1;
i = row + incr_i;
j = column + incr_j;
while ( i < board.length && j < board[i].length && i>=0 && j>=0)
{
if (board[i][j]) return false;
i += incr_i;
j += incr_j;
}
}// end else
} // end valid_position
Notice how the i & j assignments as well as the while loop are repeated throughout the method in order to check all halves of all diagonals.. This is very redundant. See the solution below for a better implementation.
This a more efficient implementation of Question 2.
boolean valid_position(boolean[][] board, int row, int column)
{
if (board[i][j])
return false;
else {
int i,j;
// check each square in the column
j = column;
for (i = 0; i < board.length; i++) {
if (board[i][j])
return false;
}
// check each square in the row
i = row;
for (j = 0; j < board[i].length; j++) {
if (board[i][j])
return false;
}
//check diagonals
int incr_i, incr_j;
return
(diagonal(-1,-1,board,row,column) && diagonal(1,-1,board,row,column)
&& diagonal(1,1,board,row,column) && diagonal(-1,1,board,row,column));
}
}
boolean diagonal(int incr_i, int incr_j, boolean[][] board, int row,
int column)
{
int i = row + incr_i;
int j = column + incr_j;
while ( i < board.length && j < board[i].length && i>=0 && j>=0)
{
if (board[i][j]) return false;
i += incr_i;
j += incr_j;
}
}
final String TERMINATOR = "QUIT";
final int MAX_RUNNER = 1000;
Runner[] runners = new Runner[MAX_RUNNER];
int rnum = 0;
boolean notdone = true;
while (notdone)
{
String name = stdin.readline();
if (name.equals(TERMINATOR))
notdone = false;
else
{
int time = Integer.parseInt(stdin.readLine());
runners[rnum] = new Runner(name, time);
rnum++;
}
}
// first find fastest runner
int fastest = 1000000; // a big number
for (int i = 0; i < rnum; i++)
{
if (runners[i].time <= fastest)
fastest = runners[i].time;
}
// print out all runner's names with time <= fastest + 10%
float close = fastest + (fastest*0.10);
// go through the runners
for (int i = 0; i < rnum; i++)
{
if (runners[i].time <= close)
System.out.println(runners[i].name);
}
void printFastest(Runner[] runners, int rnum)
{
final float fraction = 0.10;
int fastnum = (int)rnum*fraction;
Runner[] fastest = new Runner[fastnum];
int current = 0;
// read in first five runners as the fastest so far
for (int i = 0; i < fastnum; i++)
{
fastest[i] = runners[i];
current++;
}
// loop to read in the rest of the runners
for (int i = current; i <= rnum; i++)
{
Runner nextrunner = runners[i];
// 1) find the slowest runner in "fastest"
// 2) if nextrunner is faster than than the slowest runner in fastest:
// - shift all runners in "fastest" after "slowest" up by one
// (effectively removing "slowest")
// - insert "nextrunner" at the end of "fastest"
int slowest = 0;
// loop to find the slowest runner in array "fastest"
for (int j = 1; j < fastnum; j++)
{
if (fastest[j].time >= fastest[slowest].time)
slowest = j;
}
if (nextrunner.time <= fastest[slowest].time)
{
// shift the remaining runners in fastest up
// (thereby removing slowest)
for (int k = slowest+1; k < fastnum; k++)
{
fastest[k-1] = fastest[k];
}
// insert the current runner in the last position
fastest[fastnum-1] = nextrunner;
} // end if (nextrunner.time <= fastest[slowest].time)
} // end for (int i = current; i <= rnum; i++)
// print out all the runners in the array
for (int i = 0; i < fastnum; i++)
{
System.out.println(fastest[i].name);
}
} // end printFastest
10 Mary St. price: 250000.0, taxes: 3000.0 4 Parkdale Ave. price: 180000.0, taxes: 2100.0 99 Ellesmere Road rent: 700.0 12 Amelia Court not found Houses: 10 Mary St. 2 Yonge St. 4 Parkdale Ave. Apartments: 147 Peter St. 99 Ellesmere Road 3987 Finch Ave.
10 Mary St. -- once 4 Parkdale Ave. -- 6 times 99 Ellesmere Road -- 3 times 12 Amelia Court -- 6 times