A codificação run-length é uma técnica para compactar conjuntos de dados esparsos com corridas longas (sequências do mesmo valor). Neste problema, tomaremos como entrada um array 2D (lista de listas) representando uma imagem e o compactaremos usando esta técnica.
Trabalharemos da parte superior esquerda da imagem, compactando sequências de $n$ cópias do mesmo número $c$ em uma única tupla $(n,c)$.
Por exemplo, considere a seguinte pequena matriz 2-D:
[[0, 0, 0],
[2, 2, 1],
[1, 1, 1]]
Em forma compactada, isso seria uma lista [(3, 0), (2, 2), (4, 1)]
(representando o fato de que, lendo da esquerda para a direita e de cima para baixo, nós primeiro veja uma sequência de 3 0
's, depois uma sequência de 2 2
's e depois uma sequência de 4 1
's).
Como outro exemplo, a seguinte imagem:
é representada por esta matriz:
[[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]]
Na forma comprimida, seria [(8, 1), (5, 0), (2, 1), (1, 0), (1, 1), (1, 0), (1, 1), (1, 0), (2, 1), (5, 0), (2, 1), (1, 0), (3, 1), (1, 0), (2, 1), (5 , 0), (8, 1)]
.
Defina uma função run_length_encode_2d(array)
que recebe um array 2D (lista de listas) como entrada e retorna uma lista de tuplas que representam a versão codificada run-length. Sua função deve ser capaz de lidar com qualquer array 2D de inteiros (não apenas zeros e uns).
Nota:
Quando estiver pronto (depois de ter simulado manualmente e testado em sua própria máquina e estiver convencido de que seu programa fará a coisa certa), faça upload do seu arquivo Python no Problema 3.1 no Gradescope. Lembre de nomear seu arquivo p3_1.py
.