Flip the bits, find the path

Arrays
Data Types
Heaps
Trees
Data Structures

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])``````

Decimal numbers to Roman numerals

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``````
• def convert_decimal_roman(numero):
• num_romanos_dic = {
• 1: 'I',
• 5: 'V',
• 10: 'X',
• 50: 'L',
• 100: 'C',
• 500: 'D',
• 1000: 'M'
• }
• list_num_rom = [{'key': x, 'value': y} for x, y in num_romanos_dic.items()]
• size_num = len(numero)
• output = []
• for i in range(size_num):
• num = numero[i:]
• num_unit = int(num)
• numextre_izq = int(num[0])
• pref = []
• for i in range(1, len(list_num_rom), 2):
• if num_unit >= list_num_rom[i-1]['key'] and num_unit < list_num_rom[i+1]['key']:
• pref.append(list_num_rom[i-1]['value'])
• pref.append(list_num_rom[i]['value'])
• pref.append(list_num_rom[i+1]['value'])
• if numextre_izq < 4 and numextre_izq > 0:
• output.append(pref[0]*numextre_izq)
• if numextre_izq == 4:
• output.extend(pref[0:2])
• if numextre_izq == 5:
• output.append(pref[1])
• if numextre_izq > 5 and numextre_izq < 9:
• output.append(pref[1] + pref[0]*(numextre_izq-5))
• if numextre_izq == 9:
• output.extend(pref[::2])
• output = ''.join(output)
• 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

Find n-th term in sequence 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ….

Code
Diff
• ``````function solution(num){
const k = Math.floor(Math.sqrt(2*num)-0.5);
return num - k*(k+1)/2;
}
``````
• function solution(num){
• let times = 1;
• let count = 0;
• while(num > 0){
• count = num
• num -= times;
• times++;
• }
• return count;
• }
• const k = Math.floor(Math.sqrt(2*num)-0.5);
• return num - k*(k+1)/2;
• }