Vampires

Vampire Notes

There are a few methods of solving this problem. The simplest way is to create a 2D grid where each point can be a wall, a vampire, a mortal, or a mirror. These 'points' can either be their own objects or can be mapped to a single integer. Then, we simply iterate through every vampire and go in each cardinal direction and see if any mirrors reflect back to it (ignoring all the irrelevant objects).

Code

Solution - Java

package Completed;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author Jiawei
 * Completed
 */
public class Vampires {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int counter = 0;
		while (sc.hasNext()) {
			counter++;
			int numVamp = sc.nextInt();
			int numOrd = sc.nextInt();
			int numMir = sc.nextInt();
			
			if (numVamp==0 && numOrd ==0 && numMir==0) {
				break;
			}
			
			boolean none = true;

			ArrayList<Integer> xVamp = new ArrayList<Integer>();
			ArrayList<Integer> yVamp = new ArrayList<Integer>();
			ArrayList<Integer> nVamp = new ArrayList<Integer>();
			for (int i = 0; i < numVamp; i++) {
				xVamp.add(sc.nextInt());
				yVamp.add(sc.nextInt());
				nVamp.add(i+1);
			}

			ArrayList<Integer> xOrd = new ArrayList<Integer>();
			ArrayList<Integer> yOrd = new ArrayList<Integer>();
			for (int i = 0; i < numOrd; i++) {
				xOrd.add(sc.nextInt());
				yOrd.add(sc.nextInt());
			}

			ArrayList<Integer> xMir = new ArrayList<Integer>();
			ArrayList<Integer> yMir = new ArrayList<Integer>();
			ArrayList<String> dMir = new ArrayList<String>();
			for (int i = 0; i < numMir; i++) {
				String direction = sc.next();
				int x1 = sc.nextInt();
				int y1 = sc.nextInt();
				int x2 = sc.nextInt();
				int y2 = sc.nextInt();
				int mirrorTiles = 0;
				if (x1 == x2) {
					// North-South wall or one tile
					mirrorTiles = Math.abs(y2 - y1) + 1;
					if (y2 >= y1) {
						for (int j = y1; j <= y2; j++) {
							xMir.add(x1);
							yMir.add(j);
							dMir.add(direction);
						}
					} else if (y2 < y1) {
						for (int j = y2; j <= y1; j++) {
							xMir.add(x1);
							yMir.add(j);
							dMir.add(direction);
						}
					}
				} else if (y1 == y2) {
					// East-West wall
					mirrorTiles = Math.abs(x2 - x1) + 1;
					if (x2 >= x1) {
						for (int j = x1; j <= x2; j++) {
							xMir.add(j);
							yMir.add(y1);
							dMir.add(direction);
						}
					} else if (x2 < x1) {
						for (int j = x2; j <= x1; j++) {
							xMir.add(j);
							yMir.add(y1);
							dMir.add(direction);
						}
					}
				}

			}

			// for each vampire, find closest mirror in each of four directions
			// facing toward it
			
			System.out.printf("Case %d:\n", counter);
			
			for (int i=0; i<xVamp.size(); i++) {
				boolean eastTrue = false;
				boolean southTrue = false;
				boolean northTrue = false;
				boolean westTrue = false;
				int[] all4 = findMirrors(xVamp.get(i),yVamp.get(i),xMir,yMir,dMir);
				int[] block4 = findBlocks(xVamp.get(i),yVamp.get(i),xMir,yMir,dMir,xOrd,yOrd);
				if (all4[0]!=Integer.MAX_VALUE && all4[0]<block4[0]) {
					northTrue = true;
				}
				if (all4[1]!=Integer.MAX_VALUE && all4[1]<block4[1]) {
					eastTrue = true;
				}
				if (all4[2]!=Integer.MAX_VALUE && all4[2]<block4[2]) {
					southTrue = true;
				}
				if (all4[3]!=Integer.MAX_VALUE && all4[3]<block4[3]) {
					westTrue = true;
				}
				
				
				if (westTrue || southTrue || eastTrue||northTrue) {
					none = false;
					System.out.printf("vampire %d",nVamp.get(i));
					if (eastTrue) {
						System.out.print(" east");
					}
					if (northTrue) {
						System.out.print(" north");
					}
					if (southTrue) {
						System.out.print(" south");
					}
					if (westTrue) {
						System.out.print(" west");
					}
					System.out.println();
				}
				//System.out.printf("Vamp: %d %d; North: %d; East: %d; South: %d; West: %d\n",xVamp.get(i), yVamp.get(i),all4[0],all4[1],all4[2],all4[3]);
			}
			if (none) {
				System.out.println("none");
			}
		}

	}

	public static int[] findMirrors(int vampX, int vampY,
			ArrayList<Integer> mirrorX, ArrayList<Integer> mirrorY,
			ArrayList<String> mirrorD) {
		int closestNorth = Integer.MAX_VALUE;
		int closestEast = Integer.MAX_VALUE;
		int closestSouth = Integer.MAX_VALUE;
		int closestWest = Integer.MAX_VALUE;
		int[] output = new int[4];

		ArrayList<Integer> mirrorsNS = indexOfAll(vampX, mirrorX);
		ArrayList<Integer> mirrorsEW = indexOfAll(vampY, mirrorY);

		// find all south-facing mirrors north of vampire
		for (int i = 0; i < mirrorsNS.size(); i++) {
			int index = mirrorsNS.get(i);
			if (mirrorD.get(index).equals("S") && mirrorY.get(index)>vampY) {
				if (Math.abs(mirrorY.get(index) - vampY) < closestNorth) {
					closestNorth = Math.abs(mirrorY.get(index) - vampY);
				}
			}
		}

		// find all north-facing mirrors south of vampire
		for (int i = 0; i < mirrorsNS.size(); i++) {
			int index = mirrorsNS.get(i);
			if (mirrorD.get(index).equals("N") && mirrorY.get(index)<vampY) {
				if (Math.abs(mirrorY.get(index) - vampY) < closestSouth) {
					closestSouth = Math.abs(mirrorY.get(index) - vampY);
				}
			}
		}

		// find all west-facing mirrors east of vampire
		for (int i = 0; i < mirrorsEW.size(); i++) {
			int index = mirrorsEW.get(i);
			if (mirrorD.get(index).equals("W") && mirrorX.get(index)>vampX) {
				if (Math.abs(mirrorX.get(index) - vampX) < closestEast) {
					closestEast = Math.abs(mirrorX.get(index) - vampX);
				}
			}
		}

		// find all east-facing mirrors west of vampire
		for (int i = 0; i < mirrorsEW.size(); i++) {
			int index = mirrorsEW.get(i);
			if (mirrorD.get(index).equals("E") && mirrorX.get(index)<vampX) {
				if (Math.abs(mirrorX.get(index) - vampX) < closestWest) {
					closestWest = Math.abs(mirrorX.get(index) - vampX);
				}
			}
		}
		output[0] = closestNorth;
		output[1] = closestEast;
		output[2] = closestSouth;
		output[3] = closestWest;
		return output;
	}
	
	public static int[] findBlocks(int vampX, int vampY,
			ArrayList<Integer> mirrorX, ArrayList<Integer> mirrorY,
			ArrayList<String> mirrorD, ArrayList<Integer> mortalX, ArrayList<Integer> mortalY) {
		int closestNorth = Integer.MAX_VALUE;
		int closestEast = Integer.MAX_VALUE;
		int closestSouth = Integer.MAX_VALUE;
		int closestWest = Integer.MAX_VALUE;
		int[] output = new int[4];

		ArrayList<Integer> mirrorsNS = indexOfAll(vampX, mirrorX);
		ArrayList<Integer> mirrorsEW = indexOfAll(vampY, mirrorY);
		ArrayList<Integer> mortalsNS = indexOfAll(vampX, mortalX);
		ArrayList<Integer> mortalsEW = indexOfAll(vampY, mortalY);

		// find all south-facing blocks north of vampire
		for (int i = 0; i < mirrorsNS.size(); i++) {
			int index = mirrorsNS.get(i);
			if (!mirrorD.get(index).equals("S") && mirrorY.get(index)>vampY) {
				if (Math.abs(mirrorY.get(index) - vampY) < closestNorth) {
					closestNorth = Math.abs(mirrorY.get(index) - vampY);
				}
			}
		}
		for (int i = 0; i < mortalsNS.size(); i++) {
			int index = mortalsNS.get(i);
			if (mortalY.get(index)>vampY) {
				if (Math.abs(mortalY.get(index) - vampY) < closestNorth) {
					closestNorth = Math.abs(mortalY.get(index) - vampY);
				}
			}
		}

		// find all north-facing mirrors south of vampire
		for (int i = 0; i < mirrorsNS.size(); i++) {
			int index = mirrorsNS.get(i);
			if (!mirrorD.get(index).equals("N") && mirrorY.get(index)<vampY) {
				if (Math.abs(mirrorY.get(index) - vampY) < closestSouth) {
					closestSouth = Math.abs(mirrorY.get(index) - vampY);
				}
			}
		}
		for (int i = 0; i < mortalsNS.size(); i++) {
			int index = mortalsNS.get(i);
			if (mortalY.get(index)<vampY) {
				if (Math.abs(mortalY.get(index) - vampY) < closestSouth) {
					closestSouth = Math.abs(mortalY.get(index) - vampY);
				}
			}
		}

		// find all west-facing mirrors east of vampire
		for (int i = 0; i < mirrorsEW.size(); i++) {
			int index = mirrorsEW.get(i);
			if (!mirrorD.get(index).equals("W") && mirrorX.get(index)>vampX) {
				if (Math.abs(mirrorX.get(index) - vampX) < closestEast) {
					closestEast = Math.abs(mirrorX.get(index) - vampX);
				}
			}
		}
		for (int i = 0; i < mortalsEW.size(); i++) {
			int index = mortalsEW.get(i);
			if (mortalX.get(index)>vampX) {
				if (Math.abs(mortalX.get(index) - vampX) < closestEast) {
					closestEast = Math.abs(mortalX.get(index) - vampX);
				}
			}
		}

		// find all east-facing mirrors west of vampire
		for (int i = 0; i < mirrorsEW.size(); i++) {
			int index = mirrorsEW.get(i);
			if (!mirrorD.get(index).equals("E") && mirrorX.get(index)<vampX) {
				if (Math.abs(mirrorX.get(index) - vampX) < closestWest) {
					closestWest = Math.abs(mirrorX.get(index) - vampX);
				}
			}
		}
		for (int i = 0; i < mortalsEW.size(); i++) {
			int index = mortalsEW.get(i);
			if (mortalX.get(index)<vampX) {
				if (Math.abs(mortalX.get(index) - vampX) < closestWest) {
					closestWest = Math.abs(mortalX.get(index) - vampX);
				}
			}
		}
		
		output[0] = closestNorth;
		output[1] = closestEast;
		output[2] = closestSouth;
		output[3] = closestWest;
		return output;
	}

	public static ArrayList<Integer> indexOfAll(Object obj, ArrayList list) {
		// from stackoverflow
		ArrayList<Integer> indexList = new ArrayList<Integer>();
		for (int i = 0; i < list.size(); i++)
			if (obj.equals(list.get(i)))
				indexList.add(i);
		return indexList;
	}
}