471–480 of 507 posts
I always push my devs to really study the Bittorrent protocol. The elements of the protocol are all fairly easy to understand, but it's gorgeous to see how elegantly it solved a social problem rather than a computational problem. The tit-for-tat and fast-finish protocols are incredibly graceful ways to create virtuous cycles in a social/technical hybrid, and replaced very real vicious cycles in previous protocols. Va…
Problem: are two points in the same polygon? Solution: a line drawn between those two points has an odd number of intersections with the polygon if they are both in it (or outside of it), and even number if they are not.
Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…
I have a pet implementation of the frequency map that I'm overly fond of, for ascii strings: (1) keep an array of length 127 that you re-use and set to 0 between calls (2) for each character in the first string, increment the array at the character's index (3) for each character in the second string, decrement the array at the character's index If you end up with all 0s, it's an anagram.
This way you only need to check the character values you actually use, and not all 127. It also generalizes trivially to larger character sets.
Binary search. Very simple, incredibly powerful; can search on data or math function. It's the basis for other CS concepts. JS implementation: https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e1...
A cool thing about binary search is you can also use it in real life. It's great for troubleshooting.
Earlier quoted context omitted.
I have a pet implementation of the frequency map that I'm overly fond of, for ascii strings: (1) keep an array of length 127 that you re-use and set to 0 between calls (2) for each character in the first string, increment the array at the character's index (3) for each character in the second string, decrement the array at the character's index If you end up with all 0s, it's an anagram.
Better to use a hash map instead of an array. When iterating the second string, as soon as you see a character without an existing value it's not an anagram. If you finish the second string, check that all values are zero. This way you only need to check the character values you actually use, and not all 127. It also generalizes trivially to larger character sets.
Earlier quoted context omitted.
I was curious how soon overflowing a native integer would come up. The "worst case" would be all "z"s (which map to 103), so how many characters does floor(log_103(2^n-1)) get you? int32 zzzz (4 characters) uint32 zzzz (4 characters) int64 zzzzzzzzz (9 characters) uint64 zzzzzzzzz (9 characters) But that's the worst case, not many real words have several "z"s in them. How often are real words affected? I did some exp…
Hmm, nice result. That makes me want to map letters onto primes in order of frequency. So "e" is 2, "t" is 3, etc., see: http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/...
sequential encoding: 21882 words overflow 2**64 (9.3%)
frequency encoding: 2945 words overflow 2**64 (1.2%)
mean #bits for those words over 64 bits:
seq = 72.0; freq = 69.3
largest #bits:
seq = 115.4; freq = 101.0
word w/ largest #bits:
seq = thyroparathyroidectomize [1]
freq = pathologicopsychological [n/a]
Earlier quoted context omitted.
I have a pet implementation of the frequency map that I'm overly fond of, for ascii strings: (1) keep an array of length 127 that you re-use and set to 0 between calls (2) for each character in the first string, increment the array at the character's index (3) for each character in the second string, decrement the array at the character's index If you end up with all 0s, it's an anagram.
Better to use a hash map instead of an array. When iterating the second string, as soon as you see a character without an existing value it's not an anagram. If you finish the second string, check that all values are zero. This way you only need to check the character values you actually use, and not all 127. It also generalizes trivially to larger character sets.
Earlier quoted context omitted.
Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.
One might also choose not to bring in a BigNum library if you don't need to find every anagram. Here's an exhaustive list of anagrams I found with sorting and comparing that a quick Fundamental Theorem implementation missed: [ 'basiparachromatin', 'Marsipobranchiata' ] [ 'configurationism', 'misconfiguration' ] [ 'constructionism', 'misconstruction' ] [ 'pericardiacophrenic', 'phrenicopericardiac' ] [ 'anatomicophysi…
Here's my code: https://github.com/brlewis/brlewis.github.io/blob/master/201...
On my machine, Fundamental Theorem of Arithmetic finished in 1.703 seconds, sorting letters in 1.954 seconds.