Skip to content

Instantly share code, notes, and snippets.

Avatar

AShelly ashelly

  • San Francisco, CA
View GitHub Profile
View tree_encode.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct Node_t
{
int data;
struct Node_t* left;
struct Node_t* right;
@ashelly
ashelly / permutation.c
Created Feb 1, 2019
Knuth 7.2.1.2: Algorithm L (Lexicographic Permutation Generation) in C.
View permutation.c
static inline void Exchange(int* data, int a, int b) {
int temp = data[a];
data[a]=data[b];
data[b]=temp;
}
//generates all permutations of initially sorted array `a` with `n` elements
//returns 0 when no more permutations exist
int genPermutation(int a[], int n)
{
@ashelly
ashelly / beadsort.c
Created Nov 19, 2018
A 1 dimensional implementation of beadsort. O(MN) where M is maxint.
View beadsort.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
void sort(int A[], int N) {
int i,count;
int *R = calloc(N,sizeof(int));
do {
count=0;
for (i=0;i<N;i++) { if (A[i]) { count++; A[i]--;} }
@ashelly
ashelly / WRS.c
Last active Jun 15, 2020
Fast Weighted Random Sampling from discrete distributions. i.e Selecting items from a weighted list.
View WRS.c
/*
WRS.c
(c) AShelly (github.com/ashelly)
Weighted random sampling with replacement of N items in O(1) time.
(After preparing a O(N) sized buffer in O(N) time.)
The concept is:
Randomly select a buffer index. Each index is selected with probablilty 1/N.
Each index stores the fraction of hits for which this item should be selected,
@ashelly
ashelly / interactive.py
Last active Aug 29, 2015
interactive single-char input in Python (no newline needed)
View interactive.py
import sys,os
import termios
import tty
from contextlib import contextmanager
import signal
""" Allow single-key keyboard input (no <enter> needed)
Sample Usage:
@ashelly
ashelly / jsonvalidate.py
Created Sep 5, 2014
Super simple validator for JSON files. Shows line and column of error, launches editor at that point.
View jsonvalidate.py
#!/usr/bin/python
import sys,json,re,subprocess
try:
file = open(sys.argv[1])
l = file.read()
try:
json.loads(l)
print "OK"
except Exception as e:
@ashelly
ashelly / CompileTimeOptions.h
Last active Aug 29, 2015
Method of easily selecting from multitude of exclusive compile time options.
View CompileTimeOptions.h
//set only one of the following to 1.
#define OPTION_PRIMARY 1
#define OPTION_ALTERNATE 0
#define OPTION_UNLIKELY 0
//Did you follow the rules?
#if ((OPTION_PRIMARY+OPTION_ALTERNATE+OPTION_UNLIKELY)!=1)
#error("Error configuring options")
#endif
@ashelly
ashelly / fake0.sh
Created Apr 21, 2014
emulate a serial device with a terminal
View fake0.sh
socat PTY,link=/dev/ttyFAKE0,raw,echo=0 READLINE
@ashelly
ashelly / getopt.c
Last active Jun 29, 2020
"Port of GNU getopt() to Win32 for anyone who's tired of dealing with getopt() calls in Unix-to-Windows ports." Ported by Pete Wilson. Recovered from the Internet Archive's snapshot of www.pwilson.net/sample.html.
View getopt.c
/* Getopt for GNU.
NOTE: getopt is now part of the C library, so if you don't know what
"Keep this file name-space clean" means, talk to drepper@gnu.org
before changing it!
Copyright (C) 1987,88,89,90,91,92,93,94,95,96,98,99,2000,2001
Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
@ashelly
ashelly / subsequence_k.c
Last active Dec 29, 2015
Tests that string S is a subsequence of T with no gaps greater than k characters
View subsequence_k.c
/*
subsequence_k:
Tests that string S is a subsequence of T with no gaps greater than k characters.
The implementation that uses the idea of a surveyor's chain:
Imagine a series of poles linked by chains of length k.
Place the first pole at the beginning of the string.
Now cary the next pole forward until you find a character match.
Plant that pole. If there is slack, move on to the next character;
else the previous pole has been dragged forward, and you need to go back
You can’t perform that action at this time.