Vampires

Introduction

The big media gimmick these days seems to be vampires. Vampire movies, vampire television shows, vampire books, vampire dolls, vampire cereal, vampire lipstick, vampire bunnies – kids and teenagers and even some adults spend lots of time and money on vampire-related stuff. Surprisingly, nowadays vampires are often the good guys. Obviously, the ACM Programming Contest had better have a vampire problem in order to be considered culturally relevant. As eveyone knows, vampires are allergic to garlic, sunlight, crosses, wooden stakes, and the Internal Revenue Service. But curiously they spend a good part of their time smashing mirrors. Why? Well, mirrors can’t hurt vampires physically, but it’s embarrassing to be unable to cast a reflection. Mirrors hurt vampire’s feelings. This problem is about trying to help them avoid mirrors. In a room full of vampires and ordinary mortals there are a number of mirrors. Each mirror has one of four orientations – north, south, east, or west (the orientation indicates which side of the mirror reflects). A vampire is in danger of embarrassment if he or she is in a direct horizontal or vertical line with the reflecting side of a mirror, unless there are intervening objects (mortals or other mirrors). Your job is to notify each vampire of the directions in which there is danger of experiencing ENR (embarrassing non-reflectivity).

Idea

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;
	}
}