Microproject
Write a prolog rule which determines if a coordinate is within the bounding box of a rectangle. A rectangle will be defined as a list with four components [X, Y, Width, Height] where X and Y specify the upper left point on the rectangle. Coordinates are 1-indexed, so within the rectangle [0, 0, 2, 3] are the squares [1, 1], [2, 1], [1, 2], [2, 2], [1, 3], and [2, 3].
There are two ways to approach this problem: generating the list of squares contained within the rectangle, then checking list membership, or simply doing some math to check the bounds of the rectangle. I recommend the latter, though the former is good recursion practice.
Main Project: Frickin Laser Beams!
You’ve just started a new gig as a physical security penetration tester, and your latest job makes use of a laser tripwire system. Being more on the brains than brawn side of the spectrum, you decide not to risk trying to maneuver through the lasers, and instead to divert them using a clever collection of mirrors you recently acquired so that you can just walk through.
Conveniently, the facility only makes use of lasers which shoot straight across the room horizontally – no funny angles. You therefore set all of your mirrors to 45 degrees and get to work. You will need to create an area free of the laser at least 6 feet tall by 2 feet wide, for example as shown in the image below. The room is 12 feet wide and 10 feet tall. It is convenient to think of the room as a 12×10 grid. There may be obstacles on the ceiling of varying sizes (but always conforming to the grid), making the job a bit more difficult. You also only have 8 mirrors (each of which fits perfectly in, and occupies an entire, 1×1 grid space).
In Prolog you will create a program which automatically figures out where the mirrors should be placed, given a height of laser emitter, and the coordinates of obstacles on the ceiling. You must output where these mirrors will go.
|
1 2 3 4 5 6 7 8 |
% The user-facing version of place_mirrors takes 3 arguments: % 1) how many blocks the laser emitter/dectector is off the ground % 2) coordinates/size of obstacles. The first begins 2 blocks from the left, and has size width = 2, height = 3. % 3) X is the mirror placement. % You may have a version of place-mirrors with more than 3 arguments to make your life easier in writing the program. % Mirrors are expressed as triples, with x and y coordinate and orientation. place_mirrors(3, [[2,2,3],[9,2,4]], X). X = [[2,3,/],[2,7,/],[9,7,\],[9,3,\]] |
Approach
- What do you need to represent about the problem, and how will you represent it?
- What does a state entail, and how will you represent it?
- Given a state, how do you enumerate legal “next” states?
- How do you determine if a state is “safe”?
- Tip: Think of this as a path finding problem for the laser, moving from the emitter to the detector, adding mirrors wherever a direction change is desired.
Constraints
- 12 foot wide, 10 foot high room (grid).
- Emitter at x-coordinate 1, detector at x-coordinate 12.
- Laser exits emitter horizontally (not from above or below).
- Laser enters detector horizontally (not from above or below).
- No mirrors in the emitter / detector squares.
- Between 0 and 12 obstacles (inclusive) are mounted to the ceiling.
- Solutions can be found for a maximum of 8 mirrors (but also should be for 0, 4, or 6 if they are possible).
- Provide an (at least) 6 foot high by 2 foot wide rectangle for the human to walk through.
- Pressing ‘;’ after an answer results in the “next” possible answer, achieved through backtracking. The program should be able to list all possible answers in this way.
- Program should work for any legal locations of obstacles / emitter / detector for which there are solutions for 8 or fewer mirrors.
- No use of assert or retract.
Assumptions
- You only need to divert one laser.
- Mirrors can be assumed to magically float in the air (they have a complex rigging which will “just work” for any situation).
- Mirrors are reflective on both sides, so there are only two orientations (/ or \).
- All mirrors are at 45 degree angles, meaning the laser direction shifts by 90 degrees when hitting a mirror.
- You only have 8 mirrors.
- Obstacles on the ceiling are rectangular, conforming to the grid.