Skip to content

Instantly share code, notes, and snippets.

View ibeauregard's full-sized avatar

Ian Beauregard ibeauregard

  • Montréal, Québec
View GitHub Profile
@ibeauregard
ibeauregard / web_crawler.go
Last active June 23, 2022 19:51
A solution for the Web Crawler concurrency exercise in the Tour of Go (https://go.dev/tour/concurrency/10)
package main
import (
"fmt"
"sync"
)
type Fetcher interface {
// Fetch returns the body of URL and
// a slice of URLs found on that page.
@ibeauregard
ibeauregard / k_sum.py
Created March 25, 2022 00:51
Given k integer lists all of equal length, return the number of tuples (index[i] for 0 <= i < k) such that sum(arrays[i][index[i]] for 0 <= i < k) == 0.
from collections import Counter
from itertools import product
class Solution:
def fourSumCount(self, *lists):
k = len(lists)
sum_to_count = Counter(sum(nums) for nums in product(*lists[:k // 2]))
return sum(sum_to_count[-sum(nums)] for nums in product(*lists[k // 2:]))
@ibeauregard
ibeauregard / simple_text_editor.py
Created March 15, 2022 19:16
A simple text editor, along with tests
import functools
class TextEditor:
def __init__(self):
self.text = ''
self.left = 0
self.right = 0
self.clipboard = ''
self.operation_stack = OperationStack()
@ibeauregard
ibeauregard / QueueStack.py
Created March 11, 2022 20:26
A stack implementation using only one queue and whose methods only use standard queue operations (enqueue, dequeue, peek, size)
from collections import deque
from functools import wraps
class QueueStack:
def __init__(self):
self.q = deque()
def __repr__(self):
return f'QueueStack(q={self.q})'
@ibeauregard
ibeauregard / diagonal_matrix_walk.py
Last active November 24, 2022 15:32
An elegant way to walk a matrix along its minor diagonals. Minor diagonal d is made of all elements mat[i][j] such that i + j = d. Minor diagonal d is walked towards row 0 if d is even; if d is odd it is walked towards column 0.
from collections import deque
from itertools import chain
def diagonal_walk(mat):
m, n = len(mat), len(mat[0])
diagonals = [deque() for _ in range(m + n - 1)]
for i in range(m):
for j in range(n):
if (i + j) % 2 == 0:
diagonals[i + j].appendleft(mat[i][j])
else:
@ibeauregard
ibeauregard / char_map.c
Last active April 2, 2021 15:02
Demonstration of dot notation and encapsulation in C
/* char_map.h */
#ifndef CHAR_MAP_H
#define CHAR_MAP_H
typedef struct char_map CharMap;
struct char_map {
char wall;
char corridor;
char path;
char entrance;
from itertools import chain
from collections import namedtuple
from heapq import heappop, heappush
# The heapq module maintains a min-heap invariant, so we have to use
# the negative of the buildings' height because we'd like a max-heap
Building = namedtuple('Building', ['neg_height', 'end'])
Line = namedtuple('Line', ['start', 'height'])
# buildings[i] = [left_i, right_i, height_i]
def get_skyline(buildings):
@ibeauregard
ibeauregard / n_queens.py
Last active May 6, 2022 14:42
The famous N-Queens problem. n_queens(n) returns all the ways in which n queens can be placed on a n x n chessboard so that none of the queens is attacked.
def n_queens(n):
def solve():
i = len(columns)
if i == n:
solutions.append([f"{'.' * col}Q{'.' * (n - col - 1)}" for col in columns])
return
for j in range(n):
if is_legal(i, j):
add_candidate(i, j)
solve()
@ibeauregard
ibeauregard / linkedlistinsertionsort.ipynb
Last active March 5, 2021 13:23
Insertion sort on singly- and doubly-linked list
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@ibeauregard
ibeauregard / spiral_order.py
Created March 3, 2021 21:34
The most elegant way to walk a matrix in spiral order
def spiral_order(matrix):
output = []
if matrix is None:
return output
# Copy the matrix to avoid modifying the input
matrix = [line[:] for line in matrix]
while matrix:
output.extend(matrix[0])
del matrix[0]
# Transpose the matrix, and then reverse its rows