-1
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.
Could you give an example? Or, more precisely, what would be the expected output for the input your program fails, and what output your program is broadcasting? For "very large entries", I believe this makes little difference. After all, the problem is a finite automaton, will not spend more than a fixed amount of memory.
– Anderson Torres
So, you can not paste the entry here because it would exceed the number of characters, but you can see in the Udebug site of the problem https://www.udebug.com/URI/2163 the first entry for example posted by bitfreeze, asks to enter with a thousand values per thousand values, my pc hangs just trying to copy that input to paste into the pycharm terminal. There also shows the expected output.
– Mr. Potato
In this case, it would really be insane to insert such values. One thousand per thousand, one million numbers, each of say four bytes (two for digits, one for signal and one for space), would give 4 megabytes, a really huge value for insertion. .......................................... Why not do a routine to read these values from a TXT file? That at least helps you keep cheating and cheating.
– Anderson Torres
On the other hand, I believe that even manipulating so much data in memory is not necessarily a good strategy. Okay, now 4 gigs of ram is the basics for a PC, but it always seems to me a bad programming strategy to assume that one is working on a hypermachine when the problem is not too demanding. But then I think I’m interfering too much in the "discovery process". Anyway, I’ll give my idea: read a buffer three-line matrix, looking for the standard lightsaber; and re-filling this buffer according to the observed pattern. !
– Anderson Torres
Thanks for replying again. Assuming I don’t know this topic in python, it’s a good opportunity to study about. Soon I return to give the outcome of the resolution. Thanks!
– Mr. Potato