Arrays
Data Types
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])import codewars_test as test
from solution import to_be_flipped
from heapq import heapify, heappop, heappush
from random import randint, randrange, shuffle
@test.describe("Example tests")
def _():
@test.it("Fixed tests")
def _():
test.assert_equals(to_be_flipped([[0]]), 0)
test.assert_equals(to_be_flipped([[1]]), 1)
test.assert_equals(to_be_flipped([[0, 1]]), 1)
test.assert_equals(to_be_flipped([[1, 1], [1, 1]]), 3)
test.assert_equals(to_be_flipped([[0, 0, 1], [0, 1, 0], [1, 0, 0]]), 1)
test.assert_equals(to_be_flipped([[1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]]), 4)
test.assert_equals(to_be_flipped([[0, 1, 0, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0]]), 2)
test.assert_equals(to_be_flipped([[1, 1, 1, 1], [1, 0, 0, 1], [1, 0, 0, 1], [1, 1, 1, 1]]), 4)
test.assert_equals(to_be_flipped([[0, 0, 0, 0], [1, 1, 1, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]]), 0)
@test.describe("Random tests")
def _():
def check(input):
expected = to_be_flipped_check(input)
actual = to_be_flipped(input)
test.assert_equals(actual, expected)
def to_be_flipped_check(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])
X = 60
def random_mat(l, h, p=1/2):
rows, cols = randint(l, h), randint(l, h)
k = int(p*X)
return [[int(randrange(X)<k) for _ in range(cols)] for _ in range(rows)]
def snakes(l, h):
rows, cols = randint(l, h), randint(l, h)
mat = [[1 for _ in range(cols)] for _ in range(rows)]
s = (rows+cols)//2 or 1
n = rows*cols//(2*s)
dir = ((1, 0), (0, 1), (0, -1), (-1, 0))
for _ in range(n):
x, y = randrange(cols), randrange(rows)
for _ in range(s):
mat[y][x] = 0
i, j = dir[randrange(4)]
x, y = x+i, y+j
if not(0<=x<len(mat[0]) and 0<=y<len(mat)):
x, y = x-i, y-j
return mat
def checkers(l, h):
rows, cols = randint(l, h), randint(l, h)
k = 9*X//10
return [[int(randrange(X)<k)^((i+j)%2) for i in range(cols)] for j in range(rows)]
@test.it("Easy tests")
def _():
tests = []
n = 10
l, h = 1, 9
tests.extend(random_mat(l, h, i/X) for i in range(X-1, 0, -X//n))
tests.extend(snakes(l, h) for _ in range(n//2))
tests.extend(checkers(l, h) for _ in range(n//2))
shuffle(tests)
for matrix in tests:
check(matrix)
@test.it("Medium tests")
def _():
tests = []
n = 10
l, h = 19, 29
tests.extend(random_mat(l, h, i/X) for i in range(X-1, 0, -X//n))
tests.extend(snakes(l, h) for _ in range(n//2))
tests.extend(checkers(l, h) for _ in range(n//2))
shuffle(tests)
for matrix in tests:
check(matrix)
@test.it("Heavy tests")
def _():
tests = []
n = 10
l, h = 89, 99
tests.extend(random_mat(l, h, i/X) for i in range(X-1, 0, -X//n))
tests.extend(snakes(l, h) for _ in range(n//2))
tests.extend(checkers(l, h) for _ in range(n//2))
shuffle(tests)
for matrix in tests:
check(matrix)
@test.it("Heavier tests")
def _():
tests = []
n = 10
l, h = 189, 199
tests.extend(random_mat(l, h, i/X) for i in range(X-1, 0, -X//n))
tests.extend(snakes(l, h) for _ in range(n//2))
tests.extend(checkers(l, h) for _ in range(n//2))
shuffle(tests)
for matrix in tests:
check(matrix)Basic Language Features
Fundamentals
Control Flow
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
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 = numnum -= times;times++;}return count;}- const k = Math.floor(Math.sqrt(2*num)-0.5);
- return num - k*(k+1)/2;
- }
const { assert } = require("chai") function test(n, expected) { let actual = solution(n) it(`Expected ${expected}, got ${actual}`, () => { assert.strictEqual(actual, expected) }) } describe("basic tests", function(){ test(3,2); test(55,10); test(4,1); test(1,1); test(12,2); test(54,9); })- const { assert } = require("chai")
- function test(n, expected) {
- let actual = solution(n)
- it(`Expected ${expected}, got ${actual}`, () => {
- assert.strictEqual(actual, expected)
- })
- }
- describe("basic tests", function(){
- test(3,2);
- test(55,10);
- test(4,1);
- test(1,1);
- test(12,2);
- test(54,9);
- })