Microproject
Read the below project description. Then, given a list of obstacles, produce the list of blocks which are occupied by those obstacles. Using the example given below, the following is output:
|
1 2 |
?- obstacle_spaces([[2,2,3],[9,2,4]],X). X = [[3,10],[3,9],[3,8],[4,10],[4,9],[4,8],[10,10],[10,9],[10,8],[10,7],[11,10],[11,9],[11,8],[11,7]] |
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, located 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 9 10 11 12 |
% 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. % 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,\]] |
Summary Constraints and Assumptions
- You will only need to divert one laser.
- The laser must exit the emitter and enter the detector horizontally.
- You may assume the emitter is on the left (in X coordinate 1) and the detector is on the right (in X coordinate 12).
- You may not place mirrors in the same squares as the emitters, detectors, obstacles, or walking path.
- 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 \).
- Since the mirrors are at 45 degree angles, the laser direction shifts by 90 degrees.
- You have only 8 mirrors (but realize you will need either 0, 4, 6, or 8 to solve any configuration).
- Obstacles on the ceiling are rectangular, conforming to the grid.
- The human requires a rectangle at least 6 blocks high by 2 blocks wide to walk through.
- Pressing ‘;’ after an answer should result in the ‘next’ possible answer, achieved through backtracking.
Tips
Be thinking about:
– the state space – mirrors should only go in blocks which the laser passes through.
– what makes a position “unsafe” for the laser to pass through?
– how do you ensure you have enough room for the human?
I also recommend avoiding the use of assert and retract.