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).
Implementation Notes
- doing it with individual points is a great way to do it, and so is putting the points in a 2d array representing the maps and iterating through it. either should be fast enough
There are a lot of great tricks when you're working with grids like this
- you can encode movement in an array like this. You can also do this moving in any combination of directions based on how you specify x and y delta
//define all 4 possible movements
int x_delta={1,-1,0,0};
int y_delta={0,0,1,-1};
for(int i=0;i<4;i++){//iterate over all 4 possible movements
Point cur_location=vamp_location
while(on_map(cur_location)&¬_blocked){
point.x+=x_delta[i];
point.y+=y_delta[i];
}
// Do something if we have hit a blocking character, whether mirror or person
}
- when you know up front the size of something (in this case, number of vampires and humans) it's a lot easier to allocate the correct size of the array up front rather than an array list. It's less typing and a lot faster executing
- Java has a convenient structure for storing x/y pairs called a Point (import java.awt.point). Sometimes I use it, sometimes i use 2 arrays, one for x and one for y, sometimes i use a 2d array which contains both x and y for each point. Just different options!
Photo Taking:
- whenever we have a relatively small number of points in a problem space (the locations of the people in the whole area), we can often use them to optimize our search. I call the technique "interesting points". In this case we know that in some optimal solution, we can structure the photos such that a human is always on the edge of the photo, limiting our search to only pictures with humans on the edge, rather than all possible picture angles.
- When you can avoid it, don't use slopes. slopes have the "infinity problem" use angles. If you have to translate to slopes, do it as late as possible, and make sure you deal with infinite slopes. Otherwise just use atan2 and get the absolute angle.
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;
}
}