Skip to content

Instantly share code, notes, and snippets.

View syphh's full-sized avatar

Syphax Ait oubelli syphh

View GitHub Profile
@syphh
syphh / sumSubBruteForce.js
Last active December 22, 2019 21:44
Sum of sub-matrices (Brute force method)
function sumSubmatrices(mat){
// n and m represent dimensions of the matrix
let n = mat.length;
let m = mat[0].length;
// declaring a (n*m) matrix
let sumMat = [...new Array(n)].map(row => [...new Array(m)]);
for(let i = 0; i < n; i++){
for(let j = 0; j < m; j++){
@syphh
syphh / sumSubDynamic.js
Created December 22, 2019 21:24
Sum of sub-matrices (dynamic programming method)
function dynamicSumSubmatrices(mat){
// n and m represent dimensions of the matrix
let n = mat.length;
let m = mat[0].length;
// declaring a (n*m) matrix
let sumMat = [...new Array(n)].map(row => [...new Array(m)]);
// part 1
sumMat[0][0] = mat[0][0];
@syphh
syphh / randMat.js
Created December 22, 2019 21:44
100*100 random matrix
let randomMat = [...new Array(100)].map(row => [...new Array(100)].map(cell => Math.floor(Math.random() * 10)));
@syphh
syphh / addTimer.js
Created December 22, 2019 21:48
Adding timer
function foo(){
console.time();
// function code
console.timeEnd();
}
function isLowerTriangular(mat){
let matSize = mat.length;
for(let i = 0; i < matSize; i++){
for(let j = i+1; j < matSize; j++){
if(mat[i][j] != 0)
return false;
}
}
return true;
}
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def dfs(node, node_map):
clone = Node(node.val)
node_map[node.val] = clone
for neighbor in node.neighbors:
import math
def dist(p1, p2):
x1, y1, x2, y2 = *p1, *p2
return math.sqrt((y2-y1)**2 + (x2-x1)**2)
def polar_angle(p1, p2):
if p1[1] == p2[1]:
return -math.pi
def knapsack(values, weights, k, i=0, lookup=None):
lookup = {} if lookup is None else lookup
if (i, k) in lookup:
return lookup[(i, k)]
if i == len(values):
return 0
elif k < 0:
return float('-inf')
else:
lookup[(i, k)] = max(values[i]+knapsack(values, weights, k-weights[i], i+1, lookup),
def is_safe(board, i, j):
n = len(board)
j_left = j
j_right = j
while i >= 0:
if (j_left >= 0 and board[i][j_left] == 1) or board[i][j] == 1 or (j_right < n and board[i][j_right] == 1):
return False
i -= 1
j_left -= 1
j_right += 1
def is_valid(grid, r, c, k):
not_in_row = k not in grid[r]
not_in_column = k not in [grid[i][c] for i in range(9)]
not_in_box = k not in [grid[i][j] for i in range(r//3*3, r//3*3+3) for j in range(c//3*3, c//3*3+3)]
return not_in_row and not_in_column and not_in_box
def solve(grid, r=0, c=0):
if r == 9:
return True