Exercise 9 | RACSO

Exercise _‹9_›:

Flight simulation

Solve the following exercise by means of a reduction to SAT:

Determine if two planes can fly simultaneously through a cave filled with obstacles without crashing and, furthermore, crossing at some point of the flight, i.e., such that the plane that started higher ends lower than the other. The cave is a two-dimensional space discretized in squares. It has height $h$ and length $l$ . Each square can either be free or an obstacle. For instance, the cave
```
        ##########################·········
        ·······###·········#########·······
        ········#···············#########··
        ········#······###···········######
        ······#········#·#····###··········
        ·····###·······###····########·····
        ···######··························
        ###################################
```
has height $8$ and length $35$ , obstacles being indicated with a #.

A plane occupies a square. At each unit of time, planes move forward (one square to the right). At the same time, they can ascend (increasing their height by one square), keep the same height, or descend (decreasing their height by one square). We start with two planes, A and B, at the beginning of the cave (in the first column of squares), the plane A starting somewhere above plane B. We want to find how can they fly safely to the end of the cave (the last column), without crashing against obstacles or against each other. Moreover, we want to find a route in which the planes cross, i.e., such that the plane A reaches the end of the cave somewhere below the plane B. For instance, given the starting positions A and B, the paths marked with a and b are a valid solution for the previous cave:
```
        ##########################
        Aaa    ###         #########
           aaaa #  aaaaaaaa     #########
            bbba# a    ### aaaaaaa   ######
          bb  #baa     # #    ### aaaaa  bb
        Bb   ###bbbbb  ###    ######## ab
           ######    bbbbbbbbbbbbbbbbbbbaaa
        ###################################
```

The input of the exercise and the output with the solution (when the input is solvable) are as follows:

```
h: int
l: int
A: int
B: int
cave: array of array of int
```
The input contains the numbers $h$ and $l$ with the height and length of the cave. The variable cave is an $h\times l$ matrix with the shape of the cave, cell $(0,0)$ corresponding to the top-left corner of the cave, and cell $(h-1,l-1)$ to the bottom-right corner (note that height increases opposite to row indexes, maximum height being at row $0$ ). A cell of cave contains a $0$ to denote a free square, and a $1$ to denote an obstacle. The planes start at the free positions $($ A $,0)$ and $($ B $,0)$ . Note that A $<$ B since plane A starts higher than plane B.
```
planeA: array of int
planeB: array of int
```
The output consists of two arrays with length $l$ . The array planeA contains the row of each positions throughout the path of the plane A (in particular, planeA[0] must be A). The array planeB is the analogous for the plane B.

Note: this problem can be solved in asymptotic polynomial time without reducing to SAT.

Authors: Nil Mamano / Documentation:

Exercise ‹9›:

Exercise _‹9_›: