Airport max lanes length task

[AxelWasTaken]

Hello, i have a task that i am really struggling with for 5 days straight and i would preferably need it done by Monday (tomorrow)

The task reads:

Byteasar is currently developing a plan for a new airport to be built in the center of Byteotia.
Airport occupies a square of n × n bytemeters and on the plan it is divided into n2 fields of dimensions 1 × 1
bytemeters. Some of the fields are already occupied by the planned buildings (departures and arrivals hall, control tower
flights, hangars). Byteasar's task is to plan a place for m (m ≤ 2) runways of the same
length.
Each runway of length k must consist of k adjacent free fields, forming a rectangle
with dimensions of 1 × k or k × 1 bytemeters. Runways must be disjoint (in the case of m = 2) and not
may contain occupied fields. Byteasar wonders what the maximum length of the runways is
they will fit at the airport.

Entry
The first line of the input contains two integers n and m (1 ≤ n ≤ 1500, 1 ≤ m ≤ 2), meaning
the length of the side of the airport and the number of runways to be built.
The next n lines contain the airport description; each of them contains an n-letter word composed of X characters (field
busy) or . (empty field).
Exit
In the only line of the output, one integer k should be written, denoting the maximum length of the strips
startups that can be scheduled.

Example:
For input:

Output:
5 2
.X...
.XXXX
XX...
.....
.X.X.

the correct result is:

Output:
3
Explanation of the example: The figure below shows the possible arrangement of runways of length 3:
.X...
.XXXX
XX..2
111.2
.X.X2

With some mild help from r/learnpython i have managed to put together this piece of code:[/b]

from itertools import product

n, m = map(int, input().split())
airport = [input() for _ in range(n)]

def check(k):
    """Helper function to check if k-length runways can be built."""
    for i in range(n):
        for j in range(n - k + 1):
            if all(c == '.' for c in airport[i][j:j+k]):
                if m == 1:
                    return True
                for l in range(i+1, n):
                    if all(c == '.' for c in airport[l][j:j+k]):
                        return True
                break
    return False

lo, hi = 1, n
while lo < hi:
    mid = (lo + hi + 1) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid - 1

print(lo)

The problem is, the person that was helping me understand this task, has been straight up ghosting me for the past 3 days, and I'm stuck at this point because no matter what i try, it eighter breaks as a whole some other part of the code, or just doesn't work at all.

I would be very thankful if any of you could help me write working code for this task

Also, some more test cases for this task here:

Output:
1rating: n = 2, m = 1, all fields are empty; the answer is 2.

2ratings: n = 2, m = 2, one field is occupied; the answer is 1. 

3ratings: n = 10, m = 2, all fields are occupied except line 5; the answer is 5. 

4ratings: n = 10, m = 2, all fields are occupied except columns 2 and 8; the answer is 10. 

5ratings: n = 1500, m = 2, all fields are occupied except column 31, which has only 2 fields occupied; the answer is 531

My code work only up to the 2nd test.

Larz60+ write Nov-05-2023, 11:35 AM:
Please post all code, output and errors (it it's entirety) between their respective tags. Refer to BBCode help topic on how to post. Use the "Preview Post" button to make sure the code is presented as you expect before hitting the "Post Reply/Thread" button.
Code was modified for you this time (best as I can). Please use BBCode tags on future posts.

[deanhystad]

I think your entire approach is wrong.

If you want to build 3 runways of length 3, the first thing you need to do is find a place to build the first runway. The runway might run north/south or east/west. After finding a place to put the first runway you update the runway map to show the location of the runway.

If this is our map:

Output:
.X...
.XXXX
XX...
.....
.X.X.

we try [0, 0] and check if we can build a east/west runway. We cannot because [0, 1] has a building, so we try a north/south runway. Here we are blocked by a building in [2, 0]. We move to the next square, [0, 1]. This contains a building, so we move on to [0, 2]. This square is open and there is room for a east/west runway. We modify the airport map to show the new runway.

Output:
.X111
.XXXX
XX...
.....
.X.X.

Now we try to find a place for the second runway. We don't need to check if [0, 0] is open, because we already checked that square for runway 1. We check if [0, 3] is open, but it is being used by runway 1, so we move on to [0, 4] which is also used by runway 1. [1, 0] is open, but there is not enough room to place a east/west or north/south runway so we check squares [1, 1], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1] all of which have buildings. [2, 2] is open, and there is room for an east/west runway. We modify the airport map to show the new runway.

Output:
.X111
.XXXX
XX222
.....
.X.X.

Now we find a place for the third runway. We already checked all the squares up to [2, 2], so we start our search at [2, 3]. [2, 3] is being used by runway 2, as is [2, 4], so we cannot place a runway there. We move on to [3, 0] which is open, and there is enough space for an east/west runway. We modify the airport map to show the new runway.

Output:
.X111
.XXXX
XX222
333..
.X.X.

We found a place for 3 runways of length 3. Notice that the problem was solved the same way for each runway? First we found a place for runway 1, creating a new airport map that contains the runway. We took this map and found a location for runway 2. We then updated the airport map to show runway 2 and found a location for runway 3.

Locate runway for empty airport
Locate runway for airport with 1 runway
Locate runway for airport with 2 runways.

That seemed pretty straight forward. You place runway 1, then 2 and then finally 3 and you are done. Easy! But it is not always easy. Look at this map.

Output:
.xx.x
...x.
.x...
.x..x
..xx.

We would start by placing a north/south airport in [0. 0]

Output:
1xx.x
1..x.
1x...
.x..x
..xx.

Then we would put an east/west runway in [2, 2].

Output:
1xx.x
1..x.
1x222
.x..x
..xx.

There is no room for runway 3, but that doesn't mean there is no room for three runways. I remove runway 2 and try to find another place for it. There are no other places where runway 2 fits, so I remove runway 1 and try a different location.

What if instead of placing runway 1 north/south at [0, 0] we instead place it as an east/west runway at [0, 1].

Output:
.xx.x
111x.
.x...
.x..x
..xx.

Next we would place runway 2 north/south at [2, 0]

Output:
.xx.x
111x.
2x...
2x..x
.2xx.

And now we have room for an east/west runway at [2, 2]

Output:
.xx.x
111x.
2x333
2x..x
.2xx.

You remember what you tried, and if you fail, instead of giving up you undo the last thing your tried and try a different approach. In this example there was no place for runway 3, so I removed runway 2 and looked for alternative locations. This failed, so we removed runway 1 and looked for an alternative location.

To implement this kind of search your program will need a way to remember all the airport maps, remember what square you were last searching, and remember if you tried to build an east/west or a north/south runway. Problems like this are often solved using recursion.

[AxelWasTaken]

I think your entire approach is wrong.

If you want to build 3 runways of length 3, the first thing you need to do is find a place to build the first runway. The runway might run north/south or east/west. After finding a place to put the first runway you update the runway map to show the location of the runway.

If this is our map:

Output:
.X...
.XXXX
XX...
.....
.X.X.

we try [0, 0] and check if we can build a east/west runway. We cannot because [0, 1] has a building, so we try a north/south runway. Here we are blocked by a building in [2, 0]. We move to the next square, [0, 1]. This contains a building, so we move on to [0, 2]. This square is open and there is room for a east/west runway. We modify the airport map to show the new runway.

Output:
.X111
.XXXX
XX...
.....
.X.X.

Now we try to find a place for the second runway. We don't need to check if [0, 0] is open, because we already checked that square for runway 1. We check if [0, 3] is open, but it is being used by runway 1, so we move on to [0, 4] which is also used by runway 1. [1, 0] is open, but there is not enough room to place a east/west or north/south runway so we check squares [1, 1], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1] all of which have buildings. [2, 2] is open, and there is room for an east/west runway. We modify the airport map to show the new runway.

Output:
.X111
.XXXX
XX222
.....
.X.X.

Now we find a place for the third runway. We already checked all the squares up to [2, 2], so we start our search at [2, 3]. [2, 3] is being used by runway 2, as is [2, 4], so we cannot place a runway there. We move on to [3, 0] which is open, and there is enough space for an east/west runway. We modify the airport map to show the new runway.

Output:
.X111
.XXXX
XX222
333..
.X.X.

We found a place for 3 runways of length 3. Notice that the problem was solved the same way for each runway? First we found a place for runway 1, creating a new airport map that contains the runway. We took this map and found a location for runway 2. We then updated the airport map to show runway 2 and found a location for runway 3.

Locate runway for empty airport
Locate runway for airport with 1 runway
Locate runway for airport with 2 runways.

That seemed pretty straight forward. You place runway 1, then 2 and then finally 3 and you are done. Easy! But it is not always easy. Look at this map.

Output:
.xx.x
...x.
.x...
.x..x
..xx.

We would start by placing a north/south airport in [0. 0]

Output:
1xx.x
1..x.
1x...
.x..x
..xx.

Then we would put an east/west runway in [2, 2].

Output:
1xx.x
1..x.
1x222
.x..x
..xx.

There is no room for runway 3, but that doesn't mean there is no room for three runways. I remove runway 2 and try to find another place for it. There are no other places where runway 2 fits, so I remove runway 1 and try a different location.

What if instead of placing runway 1 north/south at [0, 0] we instead place it as an east/west runway at [0, 1].

Output:
.xx.x
111x.
.x...
.x..x
..xx.

Next we would place runway 2 north/south at [2, 0]

Output:
.xx.x
111x.
2x...
2x..x
.2xx.

And now we have room for an east/west runway at [2, 2]

Output:
.xx.x
111x.
2x333
2x..x
.2xx.

You remember what you tried, and if you fail, instead of giving up you undo the last thing your tried and try a different approach. In this example there was no place for runway 3, so I removed runway 2 and looked for alternative locations. This failed, so we removed runway 1 and looked for an alternative location.

To implement this kind of search your program will need a way to remember all the airport maps, remember what square you were last searching, and remember if you tried to build an east/west or a north/south runway. Problems like this are often solved using recursion.

I have managed to scrape together a piece of code that does almost as you say, but i cant seem to figure out why its not working properly.

def place_runway(airport, runway_num, runways):
    if runway_num > runways:
        return airport, runways

    for i in range(len(airport)):
        for j in range(len(airport[0])):
            for orientation in ['E', 'N']:
                if can_place_runway(airport, i, j, runway_num, orientation):
                    new_airport = [row[:] for row in airport]
                    place(new_airport, i, j, runway_num, orientation)
                    result, length = place_runway(new_airport, runway_num + 1, runways)
                    if result is not None:
                        return result, length
    return None, 0


def can_place_runway(airport, i, j, runway_num, orientation):
    for k in range(runway_num):
        ni, nj = (i + k, j) if orientation == 'N' else (i, j + k)
        if ni >= len(airport) or nj >= len(airport[0]) or airport[ni][nj] != '.':
            return False
    return True

def place(airport, i, j, runway_num, orientation):
    for k in range(runway_num):
        ni, nj = (i + k, j) if orientation == 'N' else (i, j + k)
        airport[ni][nj] = str(runway_num)

n, m = map(int, input().split())
airport = [list(input()) for _ in range(n)]
result, length = place_runway(airport, 1, m)
if result is None:
    print("No solution found")
else:
    print( length)

where for input

Output:
2 2
..
..

The output is

Output:
2

Which is correct, but for something like

Output:
5 2
.X...
.XXXX
XX...
.....
.X.X.

It's also

Output:
2

Instead of the correct

Output:
3

I would appreciate any help with that, i personally think its due to the fact that my runways overwrite each other somehow, but i can't really seem to figure it out.

[deanhystad]

You need to mark the entire runway on the map, not just the start of the runway.

I don't see anywhere in your code where you remove an airport. There will be times when you can place a runway in a square only to find out it blocks other runways from being built. When this happens you unwind and try a different solution. Unwinding involves removing the last runway from the map. Unwinding so you can try alternative solutions is essential.

I would use recursion for a problem like this. Recursion makes it easy to do "unwind and try again". Below is a pythony pseudo-code version of a recursive solution.

def add_runway(airport, length, row, col, direction, runway_marker):
    """Try adding a runway of starting at row, col and running in direction.
    If the runway fits, add to the airport map and return True, else return
    False.
    """


def remove_runway(airport, length, runway_marker):
    """Remove runway from map."""


def build_runways(airport, length, best, start=0, count=1):
    """Build runways at airport.
    airport : Map of airport showing buildings and runways
    length  : length of runways to build
    best    : Most runways (count, map) found so far.
    start   : Start trying to build runways here.
    count   : Current number of runways in airport.
    """
    rows = len(airport)
    cols = len(airport[0])
    squares = rows * cols

    # Find a place to build a runway.
    for square in range(start, squares):
        row = square // cols
        col = square % cols
        for direction in "NE":
            if add_runway(airport, length, row, col, direction, str(count)):
                if count > best count:
                      save best count and airport map
                build_runways(airport, length, best, square+1, count+1)  # Build the next runway starting at the next square.
                remove_runway(airport, str(count))  # This is the undo so we can try the next square part
    # After trying locations for this runway, return so different locations can be tried for the previous runway.

The recursion part is where build_runways() calls itself with a modified airport map and different starting position. Recursion results in a compact solution because the recursive function only has to build one runway and then call itself to build the next runway.

You might wonder "Why loop over squares instead looping over rows and columns?" The reason is that I don't want to waste time looking at starting locations that have already been checked for previous runways. By looping through "squares" it is easier to keep track of what runway locations have already been tried. Exhaustive search algorithms are inefficient enough without retracing already trodden paths.