Skip to content

Instantly share code, notes, and snippets.

View ibeauregard's full-sized avatar

Ian Beauregard ibeauregard

22 followers · 2 following
  • Montréal, Québec
View GitHub Profile
@ibeauregard
ibeauregard / exhaustive-ballot.ipynb
Created October 31, 2020 17:27
Exhaustive Ballot.ipynb
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@ibeauregard
ibeauregard / my_printf.c
Last active January 28, 2021 03:42
printf (simple, partial implementation)
#include <stdarg.h>
#include <unistd.h>
#include <stdio.h>
#define CONVERSION_TRIGGER '%'
#define MINUS_SIGN '-'
#define DIGITS "0123456789abcdef"
#define OCTAL 8
#define DECIMAL 10
#define HEXADECIMAL 16
@ibeauregard
ibeauregard / my_readline.c
Last active March 27, 2021 18:14
readline (from a stream)
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdbool.h>
#define READLINE_READ_SIZE 512
#define NEWLINE '\n'
@ibeauregard
ibeauregard / perfect_squares.py
Last active March 7, 2022 16:24
Given an integer 'target', return the least number of perfect square numbers that sum to n.
from math import sqrt
def numSquares(target):
squares = [n ** 2 for n in range(1, int(sqrt(target)) + 1)]
level = 0
remainders = {target}
while True:
level += 1
next_remainders = set()
for remainder in remainders:
for square in squares:
@ibeauregard
ibeauregard / StackQueue.py
Last active March 10, 2022 12:38
A queue implementation using only two stacks and whose methods only use standard stack operations (push, pop, peek, size)
import functools
class StackQueue:
def __init__(self):
self.main = []
self.aux = []
def __repr__(self):
return f'StackQueue(self.main={self.main}, self.aux={self.aux})'
@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
@ibeauregard
ibeauregard / linkedlistinsertionsort.ipynb
Last active March 5, 2021 13:23
Insertion sort on singly- and doubly-linked list
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@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 / skyline.py
Last active May 6, 2022 23:02
The Skyline problem (https://leetcode.com/problems/the-skyline-problem/)
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 / 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;