Description
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,\]] |
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. Your program should be able to list all possible answers in this way.
-
You may not use assert or retract.
Tips
Be thinking about:
– what state you need to keep track of.
– 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?
