Skip to content

Instantly share code, notes, and snippets.

View danong's full-sized avatar

Daniel Ong danong

View GitHub Profile
# coding=utf-8
"""Sudoku solver using constraint propogation + search"""
from collections import defaultdict
from itertools import chain, product
from pprint import pprint
from typing import List
CELLS = None
UNITS = None
PEERS = None
class Solution:
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
row_0 = col_0 = False
# step 1: iterate through matrix and set 0 markers in 1st row and col (except top left)
for row_idx, row in enumerate(matrix):
for col_idx, val in enumerate(row):
@danong
danong / detect_cycle.py
Last active March 27, 2020 01:01
Directed graph: detect cycles and topological sort
def detect_cycles(graph: dict) -> bool:
"""Return whether or not graph has any cycles."""
visited = set()
path = set()
def visit(node):
"""Return True if node is in a cycle"""
if node in visited:
return False
visited.add(node)
@danong
danong / check_bst.py
Created October 5, 2018 21:48
Given the head node of a binary tree, check if the tree is a binary search tree.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_bst_rec(node: Node, min_v: object = None, max_v: object = None) -> bool: # todo should use float('inf') and float('-inf')
if (min_v and node.val < min_v) or (max_v and node.val > max_v):
return False
"""
EXAMPLES
Puzzle 1:
[0, 1, 4]
[2, 3, 5]
[8, 7, 6]
Longest chain is [4, 5, 6, 7, 8] with length 5.
Puzzle 2:
[0, 2]
import random
if __name__ == "__main__":
# define and initialize queue variables
lambd_in = 0.5
lambd_out = 0.4
closing_time = 100
t = 0
num_arrivals = 0
num_departures = 0
@danong
danong / queue.py
Last active February 26, 2016 01:14
Single server queue simulation
import random
import numpy as np
# for graphing
from mpl_toolkits.mplot3d.axes3d import Axes3D
import matplotlib.pyplot as plt
if __name__ == "__main__":
# setting up scatterplot
Xa = []
Ya = []
@danong
danong / npuzzle.py
Last active September 21, 2023 14:24
# 8 Tile Solver
# Written by Daniel Ong for COEN 166: Artificial Intelligence
#
# A comparison of the real time taken to solve an n tile puzzle using:
# 1. Iterative deepening depth-first search
# 2. Depth-first search
# 3. Breadth-first search
# Tested on the 8 tile puzzle
# Some code adapted from Edd Mann's blog post: http://eddmann.com/posts/using-iterative-deepening-depth-first-search-in-python/
@danong
danong / HW1.pro
Created January 24, 2014 10:25
Polygon Class
TEMPLATE = app
CONFIG += console
CONFIG -= app_bundle
CONFIG -= qt
SOURCES += main.cpp \
polygon.cpp
HEADERS += \
vertex.h \