URI Online Judge - 2163 - Python 3

Question

I’m having trouble solving the problem The Awakening of the Force of the URI.

A long time ago, in a galaxy far, far away...

After the decline of the Empire, scrappers are scattered throughout the universe looking for a lightsaber lost. Everyone knows that a Lightsaber emits a specific wave pattern: 42 surrounded by 7 in all around. You have a wave sensor that sweeps a terrain with N x M cells. See example below for a 4 x 7 terrain with a saber of light on it (in position (2, 4)).

You should write a program that, given an N x M terrain, seeks by the lightsaber pattern on it. No scan has more than one light saber pattern.

Entree

The first line of the entry has two positive numbers N and M, representing respectively the number of rows and columns swept into the ground (3 N, M 1000). Each of the next N lines has integers M, which describe the values read in each cell of the land (-100 Tij 100, for 1 i N and 1 j M).

Exit

The output is a single line with 2 integers X and Y separated by one space. They represent the coordinate (X,Y) of the lightsaber, case found. If the terrain does not have a light saber pattern, X and Y are both both zero.

I basically solved most of the problem and it works well with small inputs, however are extremely large inputs for example 1000 x 1000 that end up giving me a wrong exit.

Like the first Udebug test case: https://www.udebug.com/URI/2163

I noticed that not all values are being stored within the matrix, but I have no idea how to get around this detail.

Follows my code:

l = input().split()
y, x = int(l[0]), int(l[1])

m=[[0 for i in range(y)]for j in range (x)]

for i in range(y):
    m[i] = input().split()

t = t2 = 0
for i in range(y):
    for j in range(x):
        m[i][j] = int(m[i][j])

for i in range(1, y-1):
    for j in range(1, x-1):
        if m[i][j] == 42:
            if m[i-1][j-1] == 7 and m[i-1][j] == 7 and m[i-1][j+1] == 7:
                if m[i][j-1] == 7 and m[i][j + 1] == 7:
                    if m[i+1][j-1] == 7 and m[i+1][j] == 7 and m[i+1][j+1] == 7:
                        t = i+1
                        t2 = j+1
print(t, t2)

It is very likely that I do not have to store all those values since it would consume a lot of memory (trying to solve the problem in a variety of ways I have locked the pc countless times), I can not imagine any way to deal with it.

Answer 1

I think at the time of copying and pasting the Voce input made some mistake, or your computer gave a bug. Using the 1000x1000 entry from udebug, your program worked and returned the correct output, 480 20. When I solve the problems of any online Judge, I like to test the entries through text files. In linux Voce copies the input to a txt and runs on a terminal the following command:

python3 programa.py < teste.txt

thus, the program runs as if you were typing item by item. URI runs their automated tests in this way.

Now entering your code. It has some inefficient snippets. The first of them, in the "declaration" and matrix fill, you are scanning it many times to do operations that can be summarized in the same loop. Another detail I noticed is that you continue looking for the 42 values even after already found, thing that the problem does not ask (and there is only 1 valid value per input), this way it is interesting you break the loop after finding the saber. As your code is correct and you understood the idea of the problem, knowing where you can look for the saber and in no time you look for a nonexistent Dice, I will post here the program I made with the suggested changes.

l = input().split()
n_linha, n_coluna = int(l[0]), int(l[1])

m = list() 

for i in range(n_linha):                               
    m.append( [int(col_i) for col_i in input().split()] )  

t = t2 = 0
achei = False

for i in range(1, n_linha-1):
    if achei:
        break

    for j in range(1, n_coluna-1):
        if m[i][j] == 42:
            if m[i-1][j-1] == 7 and m[i-1][j] == 7 and m[i-1][j+1] == 7:
                if m[i][j-1] == 7 and m[i][j + 1] == 7:
                    if m[i+1][j-1] == 7 and m[i+1][j] == 7 and m[i+1][j+1] == 7:
                        t = i+1
                        t2 = j+1
                        achei = True
                        break

print("{} {}".format(t, t2))

Note that I also changed the name of some variables to make the program easier to read. I strongly recommend using names that are self-explanatory

I hope I’ve helped, and anything just ask :)