Take a 2D list of any even dimensions and return a list holding the count of thing for each 2 X 2 grid (Python)

user_3687547 0
Viewed 421

I am trying to make a function that will take a list such as:

l = [["A", 1, 2, 3, 4, 5],
     ["A", "A", 2, 3, 4, 5],
     [1, 2, 3, 4, 5, 5],
     ["A", "A", "A", "A", "A", "A"],
     ["A", 3, "A", 4, "A", "A"],
     [1, 3, 5, "A", 5, "A"]
     ]

and a key, for example "A". And will give a list containing an int based on how many times KEY appears in the 2D list in every 2x2 cell. So for example a function

def count_in_grids(l, key):

will return

[3, 0, 0, 2, 2, 2, 1, 2, 3]

So far I have really bad code that I wrote. I am generally having trouble manipulating 2D lists. Since this is actually an assignment I am not allowed to use any library. If anyone can help me comprehend and write this, I will deeply appreciate it.

My crappy code that I wrote so far:

def countInGrids(l, thing):
new_list = []  # created a final list that will be returned
count = 0
for line in range(0, len(l), 2):  # Access lines
    for el in range(0, line, 2):  # Access elements
        #count + count() of all elements in line[el] to line[el+1], 
        move 2 lines down and repeat.
        count += line[line[el]:line[el]+1].count(thing) 
        count += line+1[line[el]:line[el]+1].count(thing)

        new_list.append(count)
print(new_list)
return new_list

OUTPUT: line 63, in countInGrids count += line[line[el]:line[el]+1].count(thing) TypeError: 'int' object is not subscriptable

P.S: If anyone is wondering, this is my 1st semester CS Lab

matrix list arrays python
2 Answers

It's probably a bit clunky, but list comprehensions are always an option.

def countInGrid(grid, key):
    return [sum([v[i:i+2].count(key) for v in grid[j:j+2]])
            for j in range(0, len(grid), 2) for i in range(0, len(grid[0]), 2)]

Going through this, what it's using to come up with the 2x2 grids is [v[i:i+2] for v in grid[j:j+2]. This isn't a super efficient operation if you're doing it to the entire list of lists a bunch of times, but it's fast to write.

To count the key, it first counts in each row with .count(key), and then it adds it up for each of the 2 rows in your 2x2 grid using sum().

The last line is how you're selecting which 2x2 grid you want to look at. It specifies where you'll start and where you'll end. The order of i and j is important if you don't want to iterate through columns and then through rows.

The list comprehension basically has all of the following small components wrapped up into a tighter syntax.

def count_row(v, key):
    return v.count(key)

def count_grid(grid, key):
    return sum(count_row(v, key) for v in grid)

def get_nxn(grid, i, j, n=2):
    return [v[i:i+n] for v in grid[j:j+n]]

def iter_block_row(grid, j):
    for i in range(0, len(grid[0]), 2):
        yield get_nxn(grid, i, j)

def iter_grid(grid):
    for j in range(0, len(grid), 2):
        # In Python 3.3+, use
        # yield from iter_block_row(grid, j)
        for g in iter_block_row(grid, j):
            yield g

def count_in_grid(grid, key):
    return [count_grid(g, key) for g in iter_grid(grid)]

Thinking about big problems as being composed of small parts helps to make them manageable with any amount of experience. It's also helpful to see that you don't need any of the extra syntactic sugar and language tricks to accomplish the same goal in a clean way.

Note the slices in get_nxn() are super inefficient. This is one way to decompose the problem (and I think the easiest way to think about conceptually), but it is NOT the most efficient.

Update I was wrong about the get_nxn() inefficiency. It looks like list slices in Python don't copy data, even as far back as Python 2.7+. The get_nxn() operation runs in constant time with respect to the size of grid, and it's a fast constant time at that.

user_37988970

It's tempting to try for a solution with slicing and comprehensions right off the bat, but I think the risk of confusion is sufficiently high that it's OK to start with a naive solution.

The first step is to locate all corners of the sub-squares:

1 . 2 . 3 .
. . . . . .
4 . 5 . 6 .
. . . . . .
7 . 8 . 9 .
. . . . . .

This is a nested loop counting by 2 where a corner cell is located at (row, col).

Given a sub-square, traversing its cells is another pair of nested loops with a step of 1:

1 2 x . x .
3 4 . . . .
x . x . x .
. . . . . .
x . x . x .
. . . . . .

Here, each element is located at (row + i, col + j) where i and j are inner loop steps.

After that, it's a matter of writing a conditional test and appending a counter for each sub-square to the result list.

Lastly, add the step size as a default parameter to increase reusability.

Putting it together:

def count_in_grids(l, key, size=2):
    result = []

    for row in range(0, len(l), size):
        for col in range(0, len(l[row]), size):
            result.append(0)

            for i in range(size):
                for j in range(size):
                    if key == l[row+i][col+j]:
                        result[-1] += 1

    return result

print(count_in_grids(l, "A"))
user_62433520
Related