Skip to content

Instantly share code, notes, and snippets.

View rotate.c
#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 / bs.c
Created May 4, 2019
Indirect bucket/radix sort
View bs.c
#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) {
View gcsort.c
#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)
View dlss.c
/* A classical Dancing Links Sudoku solver. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>
// Dancing links Algorithm X exactly from Knuth's paper.
typedef struct data {
struct data *l, *r, *u, *d;
@gene-ressler
gene-ressler / diagwalk.c
Last active Dec 11, 2017
Diagonal array walker
View diagwalk.c
#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 / isqrt.c
Last active May 1, 2017
Integer square root with shift and add
View isqrt.c
// 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 / life.java
Last active Aug 29, 2015
Simple Life in Java Swing
View life.java
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 / levenshtein.java
Last active Jan 4, 2016
Levenshtein distance algorithm implemented in Java with some attention to minimizing storage.
View levenshtein.java
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 / game.htm
Last active Jan 2, 2016
My first HTML 5 graphics program.
View game.htm
<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 / compiler.java
Last active Jan 2, 2016
An experiment in the workings of DAGs for common subexpression elimination.
View compiler.java
/**
* An experiment in how DAGs work for common subexpression elimination.
*/
package compiler;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;