Some more programming questions
Question 1:
You wish to build a mansion beside a long road. The far side of the road is filled with n houses, each containing a given number of people. Your mansion is as long as w houses combined. Your task is to position the mansion so that as many people as possible live across the road from you.
For instance, consider the road illustrated below, with n = 7 and w = 4. Here the seven houses contain 3, 2, 5, 1, 4, 1 and 3 people respectively. The first diagram places the mansion across from 2 + 5 + 1 + 4 = 12 people, whereas the second diagram places it across from 5 + 1 + 4+ 1 = 11 people. Indeed, of all the possible locations for the mansion, the largest possible number of people living across the road is 12.
Code
import java.util.*;
class Mansion {
public static int maxSum(int arr[], int n, int k)
{
// k must be smaller than n
if (n < k)
{
System.out.println("Invalid");
return -1;
}
// Compute sum of first window of size k
int res = 0;
for (int i=0; i<k; i++)
res += arr[i];
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window.
int curr_sum = res;
for (int i=k; i<n; i++)
{
curr_sum += arr[i] - arr[i-k];
res = Math.max(res, curr_sum);
}
return res;
}
/* Driver program to test above function */
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter no. of house");
int n = sc.nextInt();
System.out.print("Enter no. people in each house");
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
System.out.println("Enter length of mansion");
int k = sc.nextInt();
System.out.println("Largest Possible no. of people in front of mansion = "+maxSum(arr, n, k));
}
}
Question 2:
You are wandering through the desert with a map, whichshows the desert as an (x, y) coordinate plane. You begin your journey at (0, 0) facing north. In your hands are
directions to an oasis, written as a sequence of letters. The possible letters are:
• F, indicating that you should walk forwards one kilometre in the direction you are currently facing;
• L, indicating that you should turn 90◦ to the left;
• R, indicating that you should turn 90◦ to the right.
Alas, the directions contain a critical mistake—one of the right hand turns has been deleted. Fortunately your map also shows the coordinates of the oasis, and so you hope to use this information to work out where the missing right hand turn should be.
For example, suppose the directions are R F L F F F and the oasis is at (2, 2). The first diagram below illustrates this path, which ends at the incorrect location (1, 3).
With some thought it can be seen that the directions should be R F L F F R F. That is, the missing right hand turn takes place just before the final walk forwards, as shown in the second diagram above.
Code:
import java.util.*;
class Lost{
public static void main(String args[]){
Scanner S = new Scanner(System.in);
System.out.print("Enter the Coordinates of destination:\nx: ");
int x = S.nextInt();
System.out.print("y: ");
int y = S.nextInt();
Coordinate des = new Coordinate(x,y);
System.out.print("Enter the Directions: ");
String di = S.next();
System.out.println("Corrected directions are: "+correctDirections(di,des));
}
public static String correctDirections(String dir, Coordinate dest){
String result = "";
for(int i=0;i<dir.length();i++){
String newdir = (dir.substring(0,i)+'R').concat(dir.substring(i,dir.length()));
if(destination(newdir).matchcoordinates(dest)){
result = newdir;
break;
}
}
return result;
}
public static Coordinate destination(String direc, Coordinate start){
char[] dir = direc.toCharArray();
Coordinate result = new Coordinate();
char facing = 'N';
for(int i=0;i<dir.length;i++){
if(dir[i]=='F'){
switch(facing){
case 'N': start.x++;
break;
case 'S': start.x--;
break;
case 'E': start.y++;
break;
case 'W': start.y--;
break;
default:System.out.println("Input Error");
}
}
else
facing = newFacing(facing,dir[i]);
}
result=start;
return result;
}
public static Coordinate destination(String direc){
char[] dir = direc.toCharArray();
Coordinate result = new Coordinate();
Coordinate start = new Coordinate(0,0);
char facing = 'N';
for(int i=0;i<dir.length;i++){
if(dir[i]=='F')
switch(facing){
case 'N': start.y++;
break;
case 'S': start.y--;
break;
case 'E': start.x++;
break;
case 'W': start.x--;
break;
default:System.out.println("Input Error");
}
else
facing = newFacing(facing,dir[i]);
}
result=start;
return result;
}
public static char newFacing(char f, char c){
char result = f;
String directions = "NESW";
int ind = -5;
if(c=='R')
ind = directions.indexOf(f)+1;
if(c=='L')
ind = directions.indexOf(f)-1;
if(ind<0)
ind = directions.length()-1;
if(ind>=directions.length())
ind = 0;
result = directions.charAt(ind);
return result;
}
}
class Coordinate{
int x,y;
Coordinate(){
x=0;
y=0;
}
Coordinate(int x1, int y1){
x=x1;
y=y1;
}
public void setCoordinate(int x1,int y1){
x=x1;
y=y1;
}
public void printCoordinate(){
System.out.println("("+x+","+y+")");
}
public boolean matchcoordinates(Coordinate c){
if(this.x==c.x&&this.y==c.y)
return true;
else
return false;
}
}
Question 3:
A token (marked ‘X’ in the diagram) is in a maze. You may move the token around according to the following rule: in each move the token may travel one cell either horizontally or vertically, but it cannot pass over or stop on a shaded square.
For example, from its starting position the token could travel either one square right, one square down, two squares down or three squares down in a single move. To reach any other square would require more than one move.
What is maximum number of moves required to visit any cell?
Code:
import java.util.*;
class Dungeon
{
static final int[] row = { -1, 0, 0, 1 };
static final int[] col = { 0, -1, 1, 0 };
static Scanner S = new Scanner(System.in);
private static boolean isValid(int[][] maze, boolean[][] visited, int row, int col)
{
if((row >= 0) && (row < maze.length) && (col >= 0) && (col < maze[0].length)&& maze[row][col] == 1 && !visited[row][col])
return true;
else
return false;
}
private static int shortest(int[][] maze, int i, int j, int x, int y)
{
if (maze == null || maze.length == 0 || maze[i][j] == 0 || maze[x][y] == 0) {
return -1;
}
int M = maze.length;
int N = maze[0].length;
boolean[][] visited = new boolean[M][N];
Queue<Cell> q = new ArrayDeque<>();
visited[i][j] = true;
q.add(new Cell(i, j, 0));
int minimum = Integer.MAX_VALUE;
while (!q.isEmpty())
{
Cell Cell = q.poll();
i = Cell.x;
j = Cell.y;
int distance = Cell.distance;
if (i == x && j == y)
{
minimum = distance;
break;
}
for (int k = 0; k < 4; k++)
{
if (isValid(maze, visited, i + row[k], j + col[k]))
{
visited[i + row[k]][j + col[k]] = true;
q.add(new Cell(i + row[k], j + col[k], distance + 1));
}
}
}
if (minimum != Integer.MAX_VALUE) {
return minimum;
}
return -1;
}
public static void main(String[] args)
{
int[][] maze ={
{1,1,1,0,1,1,1,1},
{1,1,0,1,1,0,1,0},
{1,0,1,1,0,1,1,1},
{1,1,1,0,1,1,0,1},
{1,0,1,1,1,0,1,1},
{1,1,1,0,1,0,1,1},
{0,1,0,1,0,1,0,1},
{1,1,1,1,0,1,1,1}
};
int max = 0;
System.out.print("Enter the position of token: \nx: ");
int x = S.nextInt();
System.out.print("y: ");
int y = S.nextInt();
for(int i = 0;i<maze.length;i++)
for(int j = 0; j<maze[0].length;j++){
if(maze[i][j]==1){
int minimum = shortest(maze, x, y, i, j);
if(minimum>max)
max = minimum;
}
}
System.out.println("Maximum number of moves required to visit any cell: " + max);
}
}
class Cell
{
int x, y, distance;
Cell(int x, int y, int distance)
{
this.x = x;
this.y = y;
this.distance = distance;
}
}
Question 4:
To translate an English phrase to leet speek, the following rules are used:
1. Replace any occurrences of two, tu, too or to with the digit 2;
2. Replace any occurrences of four, fore or for with the digit 4;
3. Replace any occurrences of eight, eat or ate with the digit 8;
4. Remove any remaining vowels (letters a, e, i, o or u).
Note that rules 1–3 cannot cross word boundaries. For instance, you can turn foretold into 42ld, but you cannot turn sleigh time into sl8ime.Code:
import java.util.*;
class LeetSpeak{
Scanner S = new Scanner(System.in);
public void main(){
System.out.print("Enter the sentence to be converted to leet: ");
String s = S.nextLine();
System.out.print("Converted Leet Sentence is:");
String[] converted = convertLeet(s);
for(int i=0;i<converted.length;i++){
System.out.print(converted[i]+' ');
}
System.out.println();
}
public String[] convertLeet(String str){
String[] result;
StringTokenizer st = new StringTokenizer(str);
String[] words = Tokenizer_To_Array(st);
for(int i = 0;i<words.length;i++){
//if(words[i].contains("two")||words[i].contains("to")||words[i].contains("too")||words[i].contains("tu")){
//String new_word = words[i].substring(0,words[i].indexOf("two")>-1?words[i].indexOf("two"):words[i].indexOf("too")>-1?
//}
for(int j=0;j<words[i].length()-1;j++){
String temp = "";
for(int k=j;k<words[i].length();k++){
temp+=words[i].charAt(k);
if(temp.equalsIgnoreCase("two")||temp.equalsIgnoreCase("to")||temp.equalsIgnoreCase("tu")||temp.equalsIgnoreCase("too")){
if(temp.equalsIgnoreCase("to")&&k<words[i].length()-1){
if(words[i].charAt(k+1)=='o')
words[i] = (words[i].substring(0,j)+'2').concat(k<words[i].length()-2?words[i].substring(k+2,words[i].length()):"");
else
words[i] = (words[i].substring(0,j)+'2').concat(k<words[i].length()-1?words[i].substring(k+1,words[i].length()):"");
}
else
words[i] = (words[i].substring(0,j)+'2').concat(k<words[i].length()-1?words[i].substring(k+1,words[i].length()):"");
}
if(temp.equalsIgnoreCase("four")||temp.equalsIgnoreCase("fore")||temp.equalsIgnoreCase("for")){
if(temp.equalsIgnoreCase("for")&&k<words[i].length()-1){
if(words[i].charAt(k+1)=='e')
words[i] = (words[i].substring(0,j)+'4').concat(k<words[i].length()-2?words[i].substring(k+2,words[i].length()):"");
else
words[i] = (words[i].substring(0,j)+'4').concat(k<words[i].length()-1?words[i].substring(k+1,words[i].length()):"");
}
else
words[i] = (words[i].substring(0,j)+'4').concat(k<words[i].length()-1?words[i].substring(k+1,words[i].length()):"");
}
if(temp.equalsIgnoreCase("eight")||temp.equalsIgnoreCase("eat")||temp.equalsIgnoreCase("ate")){
words[i] = (words[i].substring(0,j)+'8').concat(k<words[i].length()-1?words[i].substring(k+1,words[i].length()):"");
}
}
}
}
for(int i = 0;i<words.length;i++)
for(int j=0;j<words[i].length();j++)
if(words[i].charAt(j)=='a'||words[i].charAt(j)=='e'||words[i].charAt(j)=='i'||words[i].charAt(j)=='o'||words[i].charAt(j)=='u')
words[i]=(words[i].substring(0,j)).concat(words[i].substring((j--)+1,words[i].length()));
result = words;
return result;
}
public String[] Tokenizer_To_Array(StringTokenizer s1)
{
String result[] = new String[s1.countTokens()];
int n1 = s1.countTokens();
for(int i=0;i<n1;i++)
result[i] = s1.nextToken();
return result;
}
}
Question 5:
As everybody knows, girl spiders are difficult to distinguish from boy spiders. You believe you can do this by using their size. For each spider colony you study, you declare that “all spiders larger than x millimetres are girls, and all spiders smaller than x millimetres are boys.” Of course you will be wrong some of the time; your task is to choose a value for x so that you make as few errors as possible.
Each of the following scenarios describes a colony of spiders, giving the sizes of each boy and girl spider in millimetres. For each scenario, you must choose a value of x that gives you as few errors as possible (that is, the number of girl spiders of size < x plus the number of boy spiders of size > x is as small as possible). This value of x will be your answer to the question.
The size of every spider is even; each of your answers must be an odd number. There will never be more than one best possible answer.
Code:
import java.util.*;
class Spiders{
Scanner S = new Scanner(System.in);
public void main(){
System.out.print("Enter the number of boy spiders: ");
int[] bois = new int[S.nextInt()];
System.out.print("Enter the number of girl spiders: ");
int[] gurlz = new int[S.nextInt()];
System.out.println("Enter the sizes of boy spiders: ");
for(int i=0;i<bois.length;i++){
System.out.print("Enter the size of "+(i+1)+" boy spider: ");
bois[i] = S.nextInt();
}
for(int i=0;i<gurlz.length;i++){
System.out.print("Enter the size of "+(i+1)+" girl spider: ");
gurlz[i] = S.nextInt();
}
System.out.println("The assumed limit should be kept at "+boundary(bois,gurlz)+" to get the least amount of anomalities.");
}
public int boundary(int[] boy, int[] girl){
int result= boy[boy.length-1]+1;
int assumed = boy[boy.length-1]+1;
int diff = difference(boy,girl,assumed);
while(assumed>boy[0]){
assumed-=2;
if(difference(boy,girl,assumed)<difference(boy,girl,result))
result = assumed;
}
return result;
}
public int difference(int[] boy, int[] girl, int bound){
int result = 0;
for(int i=0;i<girl.length;i++)
if(girl[i]<bound)
result++;
for(int i=0;i<boy.length;i++)
if(boy[i]>bound)
result++;
System.out.println(result);
return result;
}
}
