Skip to content

Instantly share code, notes, and snippets.

View chain_tree.py
# Here's a probably-not-new data structure I discovered after implementing weight-balanced trees with
# amortized subtree rebuilds (e.g. http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-scapegoat-splay.pdf)
# and realizing it was silly to turn a subtree into a sorted array with an in-order traversal only as an
# aid in constructing a balanced subtree in linear time. Why not replace the subtree by the sorted array and
# use binary search when hitting that leaf array? Then you'd defer any splitting of the array until inserts and
# deletes hit that leaf array. Only in hindsight did I realize this is similar to the rope data structure for strings.
# Unlike ropes, it's a key-value search tree for arbitrary ordered keys.
#
# The main attraction of this data structure is its simplicity (on par with a standard weight-balanced tree) and that it
# coalesces subtrees into contiguous arrays, which reduces memory overhead and boosts the performance of in-order traversals
View nodeiter.c
typedef struct {
// These fields are internal state and not considered part of the public interface.
Node *parent;
int next_index;
// This field is public and valid to read after a call to next that returns true.
Node *child;
} Iter;
Iter iter_children(Node *node) {
View line_server.py
buffer = b'' # This is the partial line buffer.
while 1:
buffer += socket.recv(1024) # Read up to 1024 bytes and append it to the buffer.
lines = buffer.split(b'\n') # Split the buffer by newlines.
buffer = lines[-1] # The last piece is a partial line.
for line in lines[:-1]: # Every other piece is a complete line.
process(line)
View rpn_serialize.c
typedef enum {
CMD_INT = NODE_INT,
CMD_NEG = NODE_NEG,
CMD_NOT = NODE_NOT,
CMD_ADD = NODE_ADD,
CMD_SUB = NODE_SUB,
CMD_RET = 128,
CMD_SETREF,
CMD_GETREF,
} Cmd;
View print_reverse.ras
func bisect(begin: Node*, end: Node*): Node*
return nth(begin, end, len(begin, end) / 2)
func print_reverse(begin: Node*, end: Node*)
if begin == end
return
mid := bisect(begin, end)
if mid != end
print_reverse(next(mid), end)
print_node(mid)
View per-cl.baf
IF
Heard([ANYONE], 251182)
THEN
RESPONSE #100
ReallyForceSpell(Player1, CLERIC_BLESS)
ReallyForceSpell(Player1, CLERIC_AID)
ReallyForceSpell(Player1, CLERIC_DEFENSIVE_HARMONY)
ReallyForceSpell(Player1, CLERIC_PROTECTION_FROM_EVIL_10_FOOT)
ReallyForceSpell(Myself, CLERIC_DRAW_UPON_HOLY_MIGHT)
ReallyForceSpell(Myself, CLERIC_HOLY_POWER)
View pre_cps.md

Partial redundancy elimination (PRE) is an optimization where you eliminate computations that are redundant on some but not all control flow paths.

Example:

if (...) {
    // ...
    int a = x + y;
    // ...
} else {
    // ...
View hejlsberg_fp.asm
; Math48 Floating Point Package
; Version 1.1 Revision 1
; by Anders Hejlsberg
; 2532 Bytes
;HOPTABEL
JP FPADD
JP FPSUB
JP FPMUL
View tp3.asm
; https://web.archive.org/web/20190701203222/https://www.pcengines.ch/tp3.htm
; The disassembler was applied to a copy of TP 3.01A downloaded from WinWorld.
; I postprocessed the disassembly with a script to clean up spacing and column alignment.
; *** TURBO PASCAL version 3.01 A source code
; ***
; *** commented by Pascal Dornier
; *** all rights reserved
; "***
cseg $100 ; "COM file...
View vec.c
// A sketch of persistent vectors with the in-place v2 trick.
typedef struct Leaf Leaf;
typedef struct Node Node;
typedef struct Vec Vec;
typedef uint32_t Ver;
typedef uint64_t Val;
typedef int32_t RelPtr;
You can’t perform that action at this time.