Skip to content

Instantly share code, notes, and snippets.

View sebinsua's full-sized avatar
🐚

Seb Insua sebinsua

🐚
View GitHub Profile
@sebinsua
sebinsua / smooth-with-array.ts
Last active November 28, 2023 15:49
Smooth a stream of LLM tokens into a stream of characters while reducing jitter by stabilising output timing. Explorations of different approaches.
View smooth-with-array.ts
function sleep(ms: number) {
return new Promise((resolve) => setTimeout(resolve, ms));
}
class AsyncQueue<T> {
queuedItems: (T | Error)[];
queuedProcessors: [(item: T) => void, (error: Error) => void][];
constructor() {
// Note: The FIFO `shift` operations we do on these arrays are `O(n)`.
View search-in-rotated-sorted-array.py
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Special case for lists with only one or two elements.
if len(nums) <= 2:
try:
return nums.index(target)
except:
return -1
# As the array has been sorted and then rotated, it's not actually
View valueEquality.ts
import stringify from "fast-json-stable-stringify";
type ImmutablePrimitive =
| undefined
| null
| boolean
| string
| number
| Function;
@sebinsua
sebinsua / follow.py
Last active August 23, 2023 21:37
An implementation of a sequential generator called `follow` for traversing linked lists and other data structures in a fixed manner.
View follow.py
from operator import eq, attrgetter as attr
from typing import TypeVar, Callable, Iterator, Optional
eq_or_none = lambda x, y: y is None or eq(x, y)
T = TypeVar('T')
def follow(start: T, next_fn: Callable[[T], T], stop: Callable[[T, T], bool] = eq_or_none) -> Iterator[Optional[T]]:
yield start
@sebinsua
sebinsua / compactRanges.js
Last active August 22, 2023 17:04
Collapse a set of ranges to the minimal set of equivalent ranges. https://twitter.com/buildsghost/status/1298054783828291585 (See also: https://leetcode.com/problems/merge-intervals)
View compactRanges.js
// Here's a difficult coding challenge for you. Given (arbitrary, unsorted, inclusive) ranges such as:
//
// 1...2, 4...6, 7...9, 2...4
//
// Reduce them to the minimal set of equivalent ranges:
//
// 1...6, 7...9
//
// See: https://twitter.com/buildsghost/status/1298054783828291585
function compactRanges(ranges) {
View typesafe-zip-2.ts
type Zipped<A extends readonly (readonly any[])[]> = {
[RowIndex in keyof A[0]]: RowIndex extends "length" ? number : {
[ArrayIndex in keyof A]: A[ArrayIndex] extends readonly any[] ? A[ArrayIndex][RowIndex] : never;
};
};
type NumericRange<TotalLength extends number, TempRange extends any[] = []> =
TempRange['length'] extends TotalLength ? TempRange : NumericRange<TotalLength, [...TempRange, TempRange['length']]>;
type TupleFromKeys<T, K extends readonly (keyof T)[]> = {
View in-place-iterative-quicksort.ts
type Slice = [lowIndex: number, highIndex: number];
function getRandomIntegerInRange([low, high]: Slice): number {
return Math.floor(Math.random() * (high - low + 1)) + low;
}
function createPartitionForSlice([lowIndex, highIndex]: Slice) {
return function partition(pivotIndex: number, items: number[]): number {
// Partitioning a slice works like so:
// - We get the pivot value from the pivot index (in our case, a random index
View quickSort.js
#!/usr/bin/env node
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
// Choosing the first item as the pivot causes worst-case
// performance if an array is already sorted.
let randomIdx = Math.floor(Math.random() * arr.length);
View sqrtUsingBinarySearch.js
#!/usr/bin/env node
const THRESHOLD = 0.00000000000001;
function sqrt(N) {
let left = 0;
// The square root of a number between 0 and 1 is greater than the number but <= 1.
// Therefore, for such numbers, we set the upper boundary to 1, and to N otherwise.
let right = Math.max(1, N);
@sebinsua
sebinsua / interesting-trie.ts
Last active August 9, 2023 16:27
I experimented a little bit with tries.
View interesting-trie.ts
export class TrieNode {
public children: Record<string, TrieNode> = {};
public isEndOfWord = false;
}
export class Trie {
private root: TrieNode;
constructor() {
this.root = new TrieNode();