Skip to content

Instantly share code, notes, and snippets.

View gene-ressler's full-sized avatar

gene-ressler

3 followers · 0 following
View GitHub Profile
@gene-ressler
gene-ressler / game.htm
Last active January 2, 2016 11:19
My first HTML 5 graphics program.
<html><head>
<script>
function run(elt) { (function(ctx) {
var render = {
clear: function() {
ctx.fillStyle = 'white'
ctx.clearRect(0, 0, elt.width, elt.height)
@gene-ressler
gene-ressler / levenshtein.java
Last active January 4, 2016 13:29
Levenshtein distance algorithm implemented in Java with some attention to minimizing storage.
package levenshtein;
public class Levenshtein {
// Levenshtein distance using O(min |a|, |b|) space.
static int distance(String a, String b) {
// Use minimum buffer size.
if (a.length() < b.length())
return distance(b, a);
a = a.toLowerCase();
@gene-ressler
gene-ressler / isqrt.c
Last active May 1, 2017 04:52
Integer square root with shift and add
// assumes unsigned is 32 bits
unsigned isqrt1(unsigned x) {
unsigned r = 0, r2 = 0;
for (int p = 15; p >= 0; --p) {
unsigned tr2 = r2 + (r << (p + 1)) + (1u << (p << 1));
if (tr2 <= x) {
r2 = tr2;
r |= (1u << p);
}
}
@gene-ressler
gene-ressler / diagwalk.c
Last active December 11, 2017 02:27
Diagonal array walker
#include <stdlib.h>
int* getDiagonalOrder(int** matrix, int m, int n) {
int *r = malloc(m * n * sizeof(int));
int dir = 1, i = 0, j = 0;
for (int k = 0; k < m * n; ++k) {
r[k] = matrix[i][j];
if (dir > 0) {
if (j == n - 1) {
dir = -1;
@gene-ressler
gene-ressler / gcsort.c
Created June 7, 2018 02:13
#include <stdio.h>
#include <stdlib.h>
// An radix 2 sort with nice properties.
void sort(unsigned *a, int len)
{
unsigned *s = a, *d = malloc(len * sizeof *d), *t, bit, is, id0, id1;
for (bit = 1; bit; bit <<= 1, t = s, s = d, d = t)
for (is = id0 = 0, id1 = len; is < len; ++is)
@gene-ressler
gene-ressler / bs.c
Created May 4, 2019 04:15
Indirect bucket/radix sort
#define N_CHUNKS (16)
#define CHUNK_SIZE (2)
#define CHUNK_MASK (~(~0u << CHUNK_SIZE))
#define SHIFT(C) (CHUNK_SIZE * (C))
#define N_BUCKETS (1 << CHUNK_SIZE)
// Return an integer s and array p that comprise a list of
// indices of array a that put it in ascending sorted order:
// a[s] <= a[next[s]] <= a[next[next[s]]]] <= ...
void ibs(unsigned *a, int n, int *s, int *next) {
@gene-ressler
gene-ressler / rotate.c
Created October 17, 2019 06:15
#include <stdio.h>
#include <inttypes.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
// Rotate a monochrome bitmap in Microsoft BMP format by pi/2.
//
// Monochrome BMP format:
// * Pixels in big-endian order: Bit 7 of byte 0 is bottom-left-most.
@gene-ressler
gene-ressler / life.java
Last active November 26, 2021 00:13
Simple Life in Java Swing
package life;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;
import java.util.Timer;
@gene-ressler
gene-ressler / maze.c
Created January 7, 2022 04:33
Rectangular grid maze generation by random DFS
/*
* A parameterized rectangular grid maze generator.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Maze data bits.
#define VISITED 1
#define RIGHT 2
@gene-ressler
gene-ressler / dijkstra.java
Last active August 17, 2022 03:31
Simple Shortest Paths in Java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.NavigableSet;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.IntStream;
import static java.util.Comparator.comparing;
public class Dijkstra {