Skip to content

Instantly share code, notes, and snippets.

Avatar

Kenneth Chung kentor

View GitHub Profile
View dirtybit-deno.js
addEventListener("fetch", (event) => {
event.respondWith(
new Response("Dirtybit.dev", {
status: 200,
headers: { "content-type": "text/plain" },
}),
);
});
@kentor
kentor / prep.txt
Last active Jul 30, 2020
Corrupted guauntlet prep
View prep.txt
Goal is to get
* 7 of each resource
* 20 fish
* 2 tier 3 weapons
* 3 potions
* 520 shards
Try to do this in two passes with minimal item juggling.
First pass:
@kentor
kentor / kth-smallest-element-in-union-of-two-sorted-arrays.md
Last active Jan 23, 2019
kth smallest element in the union of two sorted arrays
View kth-smallest-element-in-union-of-two-sorted-arrays.md

Given two sorted arrays, A of length N where N in [0, inf), and B of length M in [0, inf), find the kth smallest element in the union U = A u B in sub O(k) time.

Most of the solutions that I have googled do not consider the case where N and M can be as small as 0, but this solution does.

The strategy to this problem is to chop off part of the arrays that we know can't be the kth element. In doing so, when we recurse on the smaller arrays, the number 'k' will change to reflect tossing out elements smaller than the kth element. The base case is when either one of the arrays is empty, the kth smallest element is the the non-empty array at index k-1:

def kth_smallest(k, a, b)
  return b[k-1] if a.empty?
  return a[k-1] if b.empty?
View keybase.md

Keybase proof

I hereby claim:

  • I am kentor on github.
  • I am kentor (https://keybase.io/kentor) on keybase.
  • I have a public key whose fingerprint is EBFF 6E66 1EB6 E094 AD5E EC64 F0F2 8A0A 7AB8 63FD

To claim this, I am signing this object:

@kentor
kentor / boggle.rb
Last active Oct 10, 2016
Ruby Boggle Solver
View boggle.rb
class Point < Complex
class << self
alias :new :rectangular
end
end
class Boggle
require 'set'
attr_reader :words
@kentor
kentor / quicksort.rb
Created Feb 27, 2012
Ruby Quicksort Implementation (In-Place)
View quicksort.rb
class Array
def qsort!(low = 0, high = self.size - 1)
return self if high <= low
pivot_idx = rand(low..high)
pivot = self[pivot_idx]
self[pivot_idx], self[high] = self[high], pivot
i, j = low - 1, high
begin
@kentor
kentor / convert-number-to-excel-column.md
Created Jun 7, 2014
convert-number-to-excel-column.md
View convert-number-to-excel-column.md

This (interview) question is to create a function that maps integers to excel columns. For example:

1 => A, 2 => B, ..., 26 => Z, 27 => AA, 28 => AB, ..., 52 => AZ, 53 => BA, ..., 703 => AAA

The problem is tricky because once you start thinking in terms of base 26, you're going to find out it doesn't do the mapping correctly (I've been there). You're tempted to think okay if I let

0 => A, 1 => B, ..., 25 => Z

like in base 26, then I'd just have to subtract the input number by 1 and use this mapping to get the output. But that doesn't work for the input 27 since that would map to BA (26 = 1*26 + 0). Indeed, you can't even get AA using this scheme in a sane manner. This is because the conversion isn't really base 26. Perhaps rewriting the input numbers makes it clearer: