Thursday, 29 December 2016

Samu and Vibhu

‘samu’ and ‘vibhu’ are playing a game where there are N integers from 1 to N lying on the table.
In each turn, the player gets to pick one integer to mark as visited from among the previously unvisited ones.
If in a turn, the player picks a number which completes the picking of three consecutive numbers, he wins.
i.e., say at some stage in the game 2 and 4 are already picked(visited) if the player now picks 3, he wins.
Assuming samu starts first and both the players play perfectly optimally, who is the winner.

public class Samu_Vibhu {
private List _inputs = new ArrayList<>();
private Random _random = new Random();
private List _samuPicks;
private List _vibhuPicks;
public Samu_Vibhu(int[] inputs) {
for (int index = 0; index < inputs.length; index++) {
this._inputs.add(inputs[index]);
}
this._samuPicks = new ArrayList<>();
this._vibhuPicks = new ArrayList<>();
}
private int pickOne() {
return this._inputs.remove(this._random.nextInt(this._inputs.size()));
}
private boolean anyOneWon(List inputs, int input) {
return inputs.contains(input -1) && inputs.contains(input + 1);
}
public void play() {
boolean samuTurn = true;
boolean won = false;
int pick;
while(this._inputs.size() > 0 && !won) {
pick = this.pickOne();
System.out.println((samuTurn ? "Samu" : "Vibhu") + " picked " + pick);
if(samuTurn) this._samuPicks.add(pick);
else this._vibhuPicks.add(pick);
won = this.anyOneWon((samuTurn ? this._samuPicks : this._vibhuPicks), pick);
if(!won) samuTurn = !samuTurn;
}
if(won && samuTurn) System.out.println("Samu won");
else if(won) System.out.println("Vibhu won");
else System.out.println("Draw");
}

}

static void demoSamuVibhu() {
      int[] testCase = new int[] {1, 4, 5, 7, 8, 10, 34, 56, 67, 78, 3, 9, 57, 58 };
      Samu_Vibhu samuVibhu = new Samu_Vibhu(testCase);
      samuVibhu.play();
}
Posted by at No comments:
Labels: , ,

Apples to collect

There are N farms in a row, at each farm you either i) collect apples or ii) drink milk(energy). Visiting each farm costs you one unit of energy. This means if energy becomes zero, you cannot visit anymore farms. Given initial energy (even before first farm is visited) as P, find the maximum number of apples which we can collect.
Input
T (the number of test cases)
N P (in each test case the first line has N-the number of farms and P-the initial energy)
m1 m2 m3 m4 … mN (the milk values at each farm)
a1 a2 a3 … aN (the apples available at each farm)
.
.
.
(t such cases)
Output
In each line, output the maximum number of apples which can be collected.
amax1
amax2
.
.
(t such lines)
Test case 0
2
5 1
5 4 3 2 1
5 4 3 2 1
5 1
3 0 0 1 2
4 5 1 10 20
Expected output for Test case 0
10
36
import java.util.ArrayList;

class FarmOutput {
public FarmOutput() {
this._collected = 0;
}
public FarmOutput(int collected) {
this._collected = collected;
}
int _collected;
}

@SuppressWarnings("unused")
public class HowManyApples {
private class Farm {
Farm(String[] data) {
this._currentEnergy = this._initialEnergy = Integer.parseInt(data[0].substring(2));
for(int index = 0; index < Integer.parseInt(data[0].substring(0, 1)); index++) {
this._energyAppleMap.add(new Pair(data[1].split(" ")[index], data[2].split(" ")[index]));
}
}
int _initialEnergy;
int _currentEnergy;
private int _farmPosition = -1;
private class Pair {
Pair(String milk, String apple) {
this._milk = Integer.parseInt(milk);
this._apple = Integer.parseInt(apple);
}
Pair(int milk, int apple) {
this._milk = milk;
this._apple = apple;
}
int _milk;
int _apple;
}
int getApple() {
return this._energyAppleMap.get(this._farmPosition)._apple;
}
int getMilk() {
return this._energyAppleMap.get(this._farmPosition)._milk;
}
int getRemainingApples(int farmToVisit) {
return this.getRemaining(this._farmPosition + 1, farmToVisit)._apple;
}
int getRemainingMilk(int farmToVisit) {
return this.getRemaining(this._farmPosition + 1, farmToVisit)._milk;
}
int getSize() {
return this._energyAppleMap.size();
}

boolean canMove() {
return this._currentEnergy > 0 && this._farmPosition < (this.getSize() - 1);
}
void move() {
if(this.canMove()) {
this._farmPosition++;
this._currentEnergy--;
}
}
int farmsToBeVisited() {
return this.getSize() - this._farmPosition - 1;
}
void consumeEnergy() {
this._currentEnergy += this._energyAppleMap.get(this._farmPosition)._milk;
}
private Pair getRemaining(int start, int end) {
final Pair pair = new Pair(0, 0);
int endPos = (end >= this._energyAppleMap.size() ? this._energyAppleMap.size() - 1 : end);
for(int index = start; index <= endPos; index++) {
pair._apple += this._energyAppleMap.get(index)._apple;
pair._milk += this._energyAppleMap.get(index)._milk;
}

return pair;
}

private ArrayList _energyAppleMap = new ArrayList<>();
}
private Farm[] _farms;
public HowManyApples(String[] testCases, String splitter) {
this._farms = new Farm[testCases.length];
for(int index = 0; index < testCases.length; index++) {
this._farms[index] = new Farm(testCases[index].split(splitter));
}
}
public FarmOutput[] getMaxApplesCollected() {
FarmOutput[] outputs = new FarmOutput[this._farms.length];
for(int index = 0; index < this._farms.length; index++) {
if(!this._farms[index].canMove()) {
outputs[index] = new FarmOutput(0);
} else {
outputs[index] = new FarmOutput(this.getApplesCollected(this._farms[index]));
}
}
return outputs;
}
public void printParsedInput() {
for(int index = 0; index < this._farms.length; index++) {
System.out.println(this._farms[index].getSize() + " " + this._farms[index]._initialEnergy);
this._farms[index]._energyAppleMap.forEach((pair) -> {
System.out.print(pair._milk + " ");
});
System.out.println("");
this._farms[index]._energyAppleMap.forEach((pair) -> {
System.out.print(pair._apple + " ");
});
System.out.println("");
}
}
private int getApplesCollected(Farm farm) {
int collectedApples = 0;
while(farm.canMove()) {
farm.move();
if(farm._currentEnergy >= farm.farmsToBeVisited()) {
collectedApples += farm.getApple();
continue;
}
int consumableEnergy = farm.getMilk();
int applesToBeCollectedWithCurEnergy = farm.getRemainingApples(farm._currentEnergy);
int applesToBeCollectedWithAllEnergy = farm.getRemainingApples(farm._currentEnergy + consumableEnergy);
if(applesToBeCollectedWithAllEnergy > applesToBeCollectedWithCurEnergy) {
farm.consumeEnergy();
} else {
collectedApples += farm.getApple();
}
}
return collectedApples;
}
}

import java.util.Scanner;

public class HelloWorld {
public static void main(String[] args) {
demoApples();
}
static void demoApples() {
final String Splitter = ":";
Scanner scanner = new Scanner(System.in);
System.out.println("Paste the input as per right structure");
int noOfTestCases = Integer.parseInt(scanner.nextLine());
String[] testCases = new String[noOfTestCases];
for(int index = 0; index < noOfTestCases; index++) {
testCases[index] = scanner.nextLine() + Splitter + scanner.nextLine() + Splitter + scanner.nextLine();
}
scanner.close();
HowManyApples demo1 = new HowManyApples(testCases, Splitter);
FarmOutput[] output = demo1.getMaxApplesCollected();
for(int index = 0; index < output.length; index++) {
System.out.println(output[index]._collected);
}
}
}


Posted by at 1 comment:
Labels: , ,

Friday, 18 March 2016

Undirected Weighted Graph

package exercises;

import java.util.*;

/**
 * Undirected Weighted Graph
 */
public class UWGraph {
private final String NA = "NA";
private final String NEIGHBOUR = "NEIGHBOUR";
private HashMap vertexMap = new HashMap<>();
private List vertices = new ArrayList<>();
public Vertex addVertex(String key) {
return this.addVertex(key, null);
}
public synchronized Vertex addVertex(String key, HashMap payload) {
if(vertexMap.containsKey(key)) return this.getVertex(key);
Vertex vertex = new Vertex(this.vertices.size() + 1, key, payload);
this.vertices.add(vertex);
this.vertexMap.put(key, vertex.getId());
return vertex;
}

public void addEdge(Edge e, Vertex start, Vertex end) {
if(this.vertexMap.containsKey(start.getKey()) && this.vertexMap.containsKey(end.getKey())) {
this.getVertex(start.getKey()).addAdjacent(end.getId(), e.getWeight());
this.getVertex(end.getKey()).addAdjacent(start.getId(), e.getWeight());
}
}
public int totalVertices() {
return this.vertices.size();
}
public int degree(String vertex) {
if(!this.hasVertex(vertex)) return 0;
return this.getVertex(vertex).degree();
}
public boolean hasVertex(String key) {
return this.vertexMap.containsKey(key);
}
public boolean hasEdge(String start, String end) {
return this.hasVertex(start) && this.hasVertex(end) && 
this.getVertex(start).hasEdgeTo(this.getVertexId(end));
}
public String getEdges(String vertex) {
return this.getVertex(vertex).toString();
}
public void dfs(String key) {
Vertex v = this.getVertex(key);
Stack<int[]> children = new Stack<>();
List visited = new ArrayList<>();
if(v == null) return;
List<int[]> adjacents = v.getAdjacents();
if(adjacents == null || adjacents.size() <= 0) return;
children.addAll(adjacents);
while(!children.isEmpty()) {
int vertex = children.pop()[0] - 1;
if(visited.contains(vertex)) continue;
visited.add(vertex); System.out.println("Visited : " + vertex);
List<int[]> childs = this.vertices.get(vertex).getAdjacents();
if(childs != null && childs.size() > 0) children.addAll(childs);
}
}
public void bfs(String key) {
Vertex v = this.getVertex(key);
Queue<int[]> children = new LinkedList<>();
List visited = new ArrayList<>();
if(v == null) return;
List<int[]> adjacents = v.getAdjacents();
if(adjacents == null || adjacents.size() <= 0) return;
children.addAll(adjacents);
while(!children.isEmpty()) {
int vertex = children.poll()[0] - 1;
if(visited.contains(vertex)) continue;
visited.add(vertex); System.out.println("Visited : " + vertex);
List<int[]> childs = this.vertices.get(vertex).getAdjacents();
if(childs != null && childs.size() > 0) children.addAll(childs);
}
}
private Vertex getVertex(String key) {
return this.vertices.get(this.vertexMap.get(key) - 1);
}
private int getVertexId(String key) {
return this.getVertex(key).getId();
}
}

class Vertex {
private int id;
private String key;
private HashMap payload;
private List<int[]> adjacents;
Vertex(int id, String key, HashMap payload) {
this.id = id;
this.key = key;
this.payload = payload;
this.adjacents = new ArrayList<int[]>();
}
List<int[]> getAdjacents() {
return this.adjacents;
}
String getKey() {
return key;
}
void setKey(String key) {
this.key = key;
}
int getId() {
return id;
}
void setId(int id) {
this.id = id;
}
HashMap getPayload() {
return payload;
}
void setPayload(HashMap payload) {
this.payload = payload;
}
void addAdjacent(int vertex, int weight) {
if(!this.hasEdgeTo(vertex)) this.adjacents.add(new int[] { vertex, weight });
}
int degree() {
if(this.adjacents == null || this.adjacents.size() <= 0) return 0;
return this.adjacents.size();
}
boolean hasEdgeTo(int vertex) {
/**
* Use Bloomfilter to check for FALSE_POSITIVE and proceed to avoid linear search
*/
if(this.adjacents == null || this.adjacents.size() <= 0) return false;
for(int[] adjacent : this.adjacents) {
if(adjacent[0] == vertex) return true;
}
return false;
}
@Override
public String toString() {
if(this.adjacents == null || this.adjacents.size() <= 0) return super.toString();
StringBuilder output = new StringBuilder();
output.append(this.getKey() + ":" + "{");
for(int[] adjacent : this.adjacents) {
output.append(adjacent[0] - 1 + " ");
}
output.append("}");
return output.toString();
}
}

class Edge {
private String key;
private int weight;
Edge(String key, int weight) {
this.key = key;
this.weight = weight;
}
int getWeight() {
return weight;
}
void setWeight(int weight) {
this.weight = weight;
}
String getKey() {
return key;
}
void setKey(String key) {
this.key = key;
}

}


/**
* [ [1, 6, 8],
[0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] 
]
*/
public static void demoGraph() {
UWGraph graph = new UWGraph();
Vertex v0 = graph.addVertex("0"); Vertex v1 = graph.addVertex("1"); Vertex v2 = graph.addVertex("2");
Vertex v3 = graph.addVertex("3"); Vertex v4 = graph.addVertex("4"); Vertex v5 = graph.addVertex("5");
Vertex v6 = graph.addVertex("6"); Vertex v7 = graph.addVertex("7"); Vertex v8 = graph.addVertex("8");
Vertex v9 = graph.addVertex("9");
graph.addEdge(new Edge("01", 1), v0, v1); graph.addEdge(new Edge("06", 6), v0, v6); graph.addEdge(new Edge("08", 8), v0, v8);
graph.addEdge(new Edge("10", 10), v1, v0); graph.addEdge(new Edge("14", 14), v1, v4); graph.addEdge(new Edge("16", 16), v1, v6);
graph.addEdge(new Edge("19", 19), v1, v9);
graph.addEdge(new Edge("24", 24), v2, v4); graph.addEdge(new Edge("26", 26), v2, v6);
graph.addEdge(new Edge("34", 34), v3, v4); graph.addEdge(new Edge("35", 35), v3, v5); graph.addEdge(new Edge("38", 38), v3, v8);
graph.addEdge(new Edge("41", 41), v4, v1); graph.addEdge(new Edge("42", 42), v4, v2); graph.addEdge(new Edge("43", 43), v4, v3);
graph.addEdge(new Edge("45", 45), v4, v5); graph.addEdge(new Edge("49", 49), v4, v9);
graph.addEdge(new Edge("53", 53), v5, v3); graph.addEdge(new Edge("54", 54), v5, v4);
graph.addEdge(new Edge("60", 60), v6, v0); graph.addEdge(new Edge("61", 61), v6, v1); graph.addEdge(new Edge("62", 62), v6, v2);
graph.addEdge(new Edge("78", 78), v7, v8); graph.addEdge(new Edge("79", 79), v7, v9); 
graph.addEdge(new Edge("80", 80), v8, v0); graph.addEdge(new Edge("83", 83), v8, v3); graph.addEdge(new Edge("87", 87), v8, v7);
graph.addEdge(new Edge("91", 91), v9, v1); graph.addEdge(new Edge("94", 94), v9, v4); graph.addEdge(new Edge("97", 97), v9, v7);
System.out.println("Vertex 0,  Degree :" + graph.degree(v0.getKey()) + ", Edges : " + graph.getEdges(v0.getKey()));
System.out.println("Vertex 1,  Degree :" + graph.degree(v1.getKey()) + ", Edges : " + graph.getEdges(v1.getKey()));
System.out.println("Vertex 2,  Degree :" + graph.degree(v2.getKey()) + ", Edges : " + graph.getEdges(v2.getKey()));
System.out.println("Vertex 3,  Degree :" + graph.degree(v3.getKey()) + ", Edges : " + graph.getEdges(v3.getKey()));
System.out.println("Vertex 4,  Degree :" + graph.degree(v4.getKey()) + ", Edges : " + graph.getEdges(v4.getKey()));
System.out.println("Vertex 5,  Degree :" + graph.degree(v5.getKey()) + ", Edges : " + graph.getEdges(v5.getKey()));
System.out.println("Vertex 6,  Degree :" + graph.degree(v6.getKey()) + ", Edges : " + graph.getEdges(v6.getKey()));
System.out.println("Vertex 7,  Degree :" + graph.degree(v7.getKey()) + ", Edges : " + graph.getEdges(v7.getKey()));
System.out.println("Vertex 8,  Degree :" + graph.degree(v8.getKey()) + ", Edges : " + graph.getEdges(v8.getKey()));
System.out.println("Vertex 9,  Degree :" + graph.degree(v9.getKey()) + ", Edges : " + graph.getEdges(v9.getKey()));
//graph.dfs("0");
graph.bfs("0");
}
Posted by at No comments:
Labels: , , , ,
Subscribe to: Comments (Atom)