0
\$\begingroup\$

I'm trying to solve Pylons from the 2019's round 1A.

Problem

Our Battlestarcraft Algorithmica ship is being chased through space by persistent robots called Pylons! We have just teleported to a new galaxy to try to shake them off of our tail, and we want to stay here for as long as possible so we can buy time to plan our next move... but we do not want to get caught!

This galaxy is a flat grid of R rows and C columns; the rows are numbered from 1 to R from top to bottom, and the columns are numbered from 1 to C from left to right. We can choose which cell to start in, and we must continue to jump between cells until we have visited each cell in the galaxy exactly once. That is, we can never revisit a cell, including our starting cell.

We do not want to make it too easy for the Pylons to guess where we will go next. Each time we jump from our current cell, we must choose a destination cell that does not share a row, column, or diagonal with that current cell. Let (i, j) denote the cell in the i-th row and j-th column; then a jump from a current cell (r, c) to a destination cell (r', c') is invalid if and only if any of these is true:

r = r'
c = c'
r - c = r' - c'
r + c = r' + c'

Can you help us find an order in which to visit each of the R × C cells, such that the move between any pair of consecutive cells in the sequence is valid? Or is it impossible for us to escape from the Pylons? Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing two integers R and C: the numbers of rows and columns in this galaxy. Output

For each test case, output one line containing Case #x: y, where y is a string of uppercase letters: either POSSIBLE or IMPOSSIBLE, according to whether it is possible to fulfill the conditions in the problem statement. Then, if it is possible, output R × C more lines. The i-th of these lines represents the i-th cell you will visit (counting starting from 1), and should contain two integers ri and ci: the row and column of that cell. Note that the first of these lines represents your chosen starting cell. Limits

Time limit: 20 seconds per test set. Memory limit: 1GB. Test set 1 (Visible)

T = 16. 2 ≤ R ≤ 5. 2 ≤ C ≤ 5. Test set 2 (Hidden)

1 ≤ T ≤ 100. 2 ≤ R ≤ 20. 2 ≤ C ≤ 20.

The analysis suggests that a brute force approach should work. However, my Python 3 solution doesn't pass the 2nd test case. Can I make it faster without complicating the algorithm?

from itertools import product, repeat


def main():
    T = int(input())  # the number of test cases

    for case in range(1, T+1):
        R, C = map(int, input().split())  # the numbers of rows and columns

        stack = []

        for r, c in product(range(R), range(C)):
            grid = [[False]*C for _ in repeat(None, R)]
            grid[r][c] = True
            stack.append((((r, c),), grid))

        while stack:
            moves, grid = stack.pop()
            if len(moves) == R*C:
                print('Case #{}: POSSIBLE'.format(case))
                for r, c in moves:
                    print(r+1, c+1)
                break

            for r, c in product(range(R), range(C)):
                if (not grid[r][c] and r != moves[-1][0] and c != moves[-1][1]
                        and moves[-1][0] - moves[-1][1] != r - c
                        and moves[-1][0] + moves[-1][1] != r + c):
                    g = [r.copy() for r in grid]
                    g[r][c] = True
                    stack.append((moves+((r, c),), g))
        else:
            print('Case #{}: IMPOSSIBLE'.format(case))


main()
\$\endgroup\$
  • \$\begingroup\$ Can you share a link to the analysis you've mentioned? I have a strong doubts that the brute force may work. Meanwhile, the problem looks like a knight tour variation with an ability to make non-knight moves. Use Warnsdorff's rule, and break the dead ends with non-knight moves. \$\endgroup\$ – vnp Apr 13 at 18:36
  • \$\begingroup\$ Just follow the link and open the 'ANALYSIS' tab. \$\endgroup\$ – Eugene Yarmash Apr 13 at 19:18
  • \$\begingroup\$ There is nothing about the brute force there. The do however mention the knight tour (I honestly didn't read that tab when making the above comment). \$\endgroup\$ – vnp Apr 13 at 19:21
  • 1
    \$\begingroup\$ Can you add a title that explains what the task is? This way reviewers can get some context. \$\endgroup\$ – bhathiya-perera Apr 13 at 21:56
  • \$\begingroup\$ @vnp: Did you read it to the end? :) This suggests that there are many possible solutions, and we might expect even more as the grid's dimensions get larger. {...} So, our intuition might suggest at this point that the best approach is some kind of brute force. \$\endgroup\$ – Eugene Yarmash Apr 14 at 7:32
1
\$\begingroup\$

A simple randomized brute-force works for this problem. From the analysis:

We can try these solutions anyway, or we can rely on our occasional friend, randomness! We can pick a random starting cell, repeatedly choose valid moves uniformly at random from the space of all allowed moves from our current cell, and, if we run out of available moves, give up and start over. For any case except for the impossible ones mentioned above, this approach finds a solution very quickly.

Python code:

from itertools import product, repeat
from random import choice


def main():
    T = int(input())  # the number of test cases

    for case in range(1, T+1):
        R, C = map(int, input().split())  # the numbers of rows and columns

        if R < 2 or C < 2 or R + C < 7:
            print('Case #{}: IMPOSSIBLE'.format(case))
        else:
            print('Case #{}: POSSIBLE'.format(case))

            while True:
                grid = [[False]*C for _ in repeat(None, R)]
                moves = []
                last = None
                for _ in repeat(None, R*C):
                    candidates = ([(r, c) for r, c in product(range(R), range(C)) if not grid[r][c]
                                   and r != last[0] and c != last[1] and last[0] - last[1] != r - c
                                   and last[0] + last[1] != r + c]
                                  if last is not None else list(product(range(R), range(C))))
                    if not candidates:
                        break
                    cell = choice(candidates)
                    moves.append(cell)
                    grid[cell[0]][cell[1]] = True
                    last = cell
                else:
                    for r, c in moves:
                        print(r+1, c+1)
                    break


main()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.