4 ms·

I'm a non-coding lurker here, but the only thing that ever motivated me to write my own program was to solve the newspaper anagram puzzle, "Jumble", faster than

I'm a non-coding lurker here, but the only thing that ever motivated me to write my own program was to solve the newspaper anagram puzzle, "Jumble", faster than my wife. I wrote it in Basic, then re-wrote it in assembly language, I forget when. Then in Fortran while home bound during the first summer of the pandemic - to atone for my past sin of neglecting to learn Fortran when I had a chance in the late 1960's.

mock-possum 3y ago
I dunno man, I’ve never heard of a “non-coder” rewriting the same program in three languages, including one round ‘just because’
lurquer 3y ago
I did the same thing! I stumbled upon an old ‘Al Zimmerman’ programming contest that involved creating wordsearch grids with the most words possible. I had a technique in mind, wrote it in BASIC. Then realized that was too slow. So I tried it in Java (which I’d heard was easy… it wasn’t… st least not to me). And then finally wrote it in C++, a language I found perfect in all respects. I actually ranked near the top in that contest, and I’ve been programming ever since. Ironically, I write programs to make puzzle books and I even have a Jumble knock-off on Amazon (sans cartoons… can’t draw worth a damn.)
mxuribe 3y ago
With respect, the moment you mentioned "re-wrote it in assembly language"...you stopped being a non-coder! :-) By the way, very cool use of technolgoy for somewhat everyday things (solving puzzles).
jodrellblank 3y ago
I did similar for a newspaper puzzle unscrambler, pushing to rewrite it in lower level languages (PowerShell then C# then Rust) and changing algorithm (from sort letters, to precompute lookup hashtable of sorted letters, to multiply prime numbers one for each alphabet letter to drop the overhead of sorting, to lookup hash of those, to sorting the integer results into an array to do a binary search through and jump to the matching offset in an answers array and inlining those in the code) until it was near enough instant. ... and I don't use it, because unjumbling the word myself is satisfying, but typing the letters into a computer and getting the answer isn't.
- _a_a_a_ 3y ago
  > to multiply prime numbers one for each alphabet letter to drop the overhead of sorting how does that work?
  - deleted 3y ago
    [deleted]
  - jodrellblank 3y ago
    Not sure if you're asking about the technique, or the math, or the comparison with sorting, so here's a long answer of all of them - start like the secret codes from childhood by giving numbers to letters so A=1, B=2, C=3, D=4, etc. Then go through a word and find the values for each letter and multiply them together, e.g. "tab" is 20 x 1 x 2 = 40 and hopefully an anagram that just rearranges the letters gets the same answer because multiplication doesn't change if you shuffle the numbers around, e.g. "bat" is 2 x 1 x 20 = 40 which is the same, "bat" and "tab" are anagrams... but with the integers it doesn't always work and different words can clash e.g. "fab" 6 x 1 x 2 = 12 and "cad" 3 x 1 x 4 = 12 have the same answer but are not anagrams. Prime numbers help because the Fundamental Theorem of Arithmetic[1][2] says that there can't be any clashes when you multiply Primes, every number breaks down into a unique product of Primes (I can't prove that myself, but it is apparently true). So give the letters Prime numbers A=2, B=3, C=5, D=7, E=11, F=13, etc. and now "fab" 13 x 2 x 3 = 78 and "cad" 5 x 2 x 7 = 70 no longer clash. The only way to get the same answer is to have the same primes (in any order), so anagrams will have the same answer and non-anagrams will not. Why it drops the overhead of sorting is that the time for sorting any collection requires looking at each item and comparing at least some of them, and swapping positions of at least some of them, generally O(N items x log(N)). Lookup the letter in a Prime value array and multiplication once per letter doesn't need any comparisons or any swapping positions, so it is O(N items) time, that gives this approach less work to do for each word, so it can finish faster. It looks like (Python, assuming lowercase ASCII letters where 'a' starts at code 97): primes = [2,3,5,7,...] ascii_a = 97 product = 1 for c in word: product *= primes[ord(c) - ascii_a] Do that for the incoming word, and for every word in the wordlist, and see which have matching products, those are the anagrams. Or pre-compute for all the words in the wordlist and only do it for the incoming word and then lookup the matching ones. [1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme... [2] https://www.varsitytutors.com/hotmath/hotmath_help/topics/prime-factorization https://www.varsitytutors.com/hotmath/hotmath_help/topics/pr...
hoosieree 3y ago
We regret to inform you that you are now a former non-coder.
mjd 3y ago
About thirty years ago I had an account on a computer system that had a Boggle game, and I got tired of losing to it. So I wrote a program (in C!) which, when run, would search the grid and print out a list of all the words it found. Since I was using a bigger dictionary than the Boggle game itself, I found a lot more words. Ha ha, take that! I proudly boasted to a friend about my winning Boggle solver and they said it was the pettiest thing they had ever heard of.

mock-possum 3y ago

I dunno man, I’ve never heard of a “non-coder” rewriting the same program in three languages, including one round ‘just because’

lurquer 3y ago

I did the same thing! I stumbled upon an old ‘Al Zimmerman’ programming contest that involved creating wordsearch grids with the most words possible. I had a technique in mind, wrote it in BASIC. Then realized that was too slow. So I tried it in Java (which I’d heard was easy… it wasn’t… st least not to me). And then finally wrote it in C++, a language I found perfect in all respects. I actually ranked near the top in that contest, and I’ve been programming ever since. Ironically, I write programs to make puzzle books and I even have a Jumble knock-off on Amazon (sans cartoons… can’t draw worth a damn.)

mxuribe 3y ago

With respect, the moment you mentioned "re-wrote it in assembly language"...you stopped being a non-coder! :-) By the way, very cool use of technolgoy for somewhat everyday things (solving puzzles).

jodrellblank 3y ago

I did similar for a newspaper puzzle unscrambler, pushing to rewrite it in lower level languages (PowerShell then C# then Rust) and changing algorithm (from sort letters, to precompute lookup hashtable of sorted letters, to multiply prime numbers one for each alphabet letter to drop the overhead of sorting, to lookup hash of those, to sorting the integer results into an array to do a binary search through and jump to the matching offset in an answers array and inlining those in the code) until it was near enough instant. ... and I don't use it, because unjumbling the word myself is satisfying, but typing the letters into a computer and getting the answer isn't.

_a_a_a_ 3y ago
> to multiply prime numbers one for each alphabet letter to drop the overhead of sorting how does that work?
- deleted 3y ago
  [deleted]
- jodrellblank 3y ago
  Not sure if you're asking about the technique, or the math, or the comparison with sorting, so here's a long answer of all of them - start like the secret codes from childhood by giving numbers to letters so A=1, B=2, C=3, D=4, etc. Then go through a word and find the values for each letter and multiply them together, e.g. "tab" is 20 x 1 x 2 = 40 and hopefully an anagram that just rearranges the letters gets the same answer because multiplication doesn't change if you shuffle the numbers around, e.g. "bat" is 2 x 1 x 20 = 40 which is the same, "bat" and "tab" are anagrams... but with the integers it doesn't always work and different words can clash e.g. "fab" 6 x 1 x 2 = 12 and "cad" 3 x 1 x 4 = 12 have the same answer but are not anagrams. Prime numbers help because the Fundamental Theorem of Arithmetic[1][2] says that there can't be any clashes when you multiply Primes, every number breaks down into a unique product of Primes (I can't prove that myself, but it is apparently true). So give the letters Prime numbers A=2, B=3, C=5, D=7, E=11, F=13, etc. and now "fab" 13 x 2 x 3 = 78 and "cad" 5 x 2 x 7 = 70 no longer clash. The only way to get the same answer is to have the same primes (in any order), so anagrams will have the same answer and non-anagrams will not. Why it drops the overhead of sorting is that the time for sorting any collection requires looking at each item and comparing at least some of them, and swapping positions of at least some of them, generally O(N items x log(N)). Lookup the letter in a Prime value array and multiplication once per letter doesn't need any comparisons or any swapping positions, so it is O(N items) time, that gives this approach less work to do for each word, so it can finish faster. It looks like (Python, assuming lowercase ASCII letters where 'a' starts at code 97): primes = [2,3,5,7,...] ascii_a = 97 product = 1 for c in word: product *= primes[ord(c) - ascii_a] Do that for the incoming word, and for every word in the wordlist, and see which have matching products, those are the anagrams. Or pre-compute for all the words in the wordlist and only do it for the incoming word and then lookup the matching ones. [1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme... [2] https://www.varsitytutors.com/hotmath/hotmath_help/topics/prime-factorization https://www.varsitytutors.com/hotmath/hotmath_help/topics/pr...

hoosieree 3y ago

We regret to inform you that you are now a former non-coder.

mjd 3y ago

About thirty years ago I had an account on a computer system that had a Boggle game, and I got tired of losing to it. So I wrote a program (in C!) which, when run, would search the grid and print out a list of all the words it found. Since I was using a bigger dictionary than the Boggle game itself, I found a lot more words. Ha ha, take that! I proudly boasted to a friend about my winning Boggle solver and they said it was the pettiest thing they had ever heard of.