Arrays
Heaps
Trees
Data Structures

Task

Given an matrix of bits (0 or 1), return the minimum number of bits that you need to flip to draw a path of 0s from the top left corner to the bottom right corner.

Two cells can be contiguous in a path only orthogonally (not diagonally). That means that you can move on the path in four directions: top, bottom, left, right.

To flip a bit b means change its value to 0 if b === 1 else 1.

Examples

to_be_flipped([[1, 0, 1, 0],
               [0, 1, 0, 1],
               [1, 0, 1, 0],
               [0, 1, 0, 1]])
# returns: 4

One of the best paths goes through the top right corner (the flipped bits are bold):

(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3)

to_be_flipped([[0, 1, 0, 0],
               [1, 0, 1, 0],
               [1, 1, 0, 1],
               [0, 0, 1, 0]])
# returns: 2

(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3)

Constraints

  • 0 < len(matrix) < 200
  • 0 < len(matrix[0]) < 200
  • n == 0 or n == 1 for each number n in the matrix

Tests

9 fixed tests and 80 random tests

from heapq import heapify, heappop, heappush

def to_be_flipped(mat):
    ori = [[n for n in r] for r in mat]
    mat = [[n and 10001 for n in r] for r in mat]
    mat[0][0] = 1
    queue = [(1, 0, 0)]
    heapify(queue)
    directions = ((1, 0), (0, 1), (0, -1), (-1, 0))
    while not mat[-1][-1] or mat[-1][-1]>queue[0][0]:
        _, x, y = heappop(queue)
        for i, j in directions:
            xi, yj = x+i, y+j
            if 0<=xi<len(mat) and 0<=yj<len(mat[0]):
                if not mat[xi][yj] or mat[x][y]+ori[xi][yj]<mat[xi][yj]:
                    mat[xi][yj] = mat[x][y]+ori[xi][yj]
                    heappush(queue, (mat[xi][yj], xi, yj))
    return mat[-1][-1] - (not ori[0][0])
Basic Language Features
Fundamentals
Control Flow
Code
Diff
  • def convert_decimal_roman(numero):
        num_romanos = ['', 'M', 'D', 'C', 'L', 'X', 'V', 'I']
        numero = numero.zfill(4)
        output = ''
        for i, num_unit in enumerate(numero):
            q, r = divmod(int(num_unit), 5)
            if r == 4:
                output += num_romanos[2 * i + 1] + num_romanos[2 * i - q]
            else:
                output += num_romanos[2 * i] * q + num_romanos[2 * i + 1] * r
        return output
  • 11 def convert_decimal_roman(numero):
    2 num_romanos_dic = {
    3 1: 'I',
    4 5: 'V',
    5 10: 'X',
    6 50: 'L',
    7 100: 'C',
    8 500: 'D',
    9 1000: 'M'
    10 }
    11 list_num_rom = [{'key': x, 'value': y} for x, y in num_romanos_dic.items()]
    12 size_num = len(numero)
    13 output = []
    14 for i in range(size_num):
    15 num = numero[i:]
    16 num_unit = int(num)
    17 numextre_izq = int(num[0])
    18 pref = []
    19 for i in range(1, len(list_num_rom), 2):
    20 if num_unit >= list_num_rom[i-1]['key'] and num_unit < list_num_rom[i+1]['key']:
    21 pref.append(list_num_rom[i-1]['value'])
    22 pref.append(list_num_rom[i]['value'])
    23 pref.append(list_num_rom[i+1]['value'])
    24
    25 if numextre_izq < 4 and numextre_izq > 0:
    26 output.append(pref[0]*numextre_izq)
    27 if numextre_izq == 4:
    28 output.extend(pref[0:2])
    29 if numextre_izq == 5:
    30 output.append(pref[1])
    31 if numextre_izq > 5 and numextre_izq < 9:
    32 output.append(pref[1] + pref[0]*(numextre_izq-5))
    33 if numextre_izq == 9:
    34 output.extend(pref[::2])
    35
    36 output = ''.join(output)
    2+ num_romanos = ['', 'M', 'D', 'C', 'L', 'X', 'V', 'I']
    3+ numero = numero.zfill(4)
    4+ output = ''
    5+ for i, num_unit in enumerate(numero):
    6+ q, r = divmod(int(num_unit), 5)
    7+ if r == 4:
    8+ output += num_romanos[2 * i + 1] + num_romanos[2 * i - q]
    9+ else:
    10+ output += num_romanos[2 * i] * q + num_romanos[2 * i + 1] * r
    3737 return output
Code
Diff
  • function solution(num){
      const k = Math.floor(Math.sqrt(2*num)-0.5);
      return num - k*(k+1)/2;
    }
    
  • 11 function solution(num){
    2 let times = 1;
    3 let count = 0;
    4 while(num > 0){
    5 count = num
    6 num -= times;
    7 times++;
    8 }
    9 return count;
    2+ const k = Math.floor(Math.sqrt(2*num)-0.5);
    3+ return num - k*(k+1)/2;
    1010 }