Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I found the best anagram in English (2017)

blog.plover.com

Post reply on HN
Print view View original

141–150 of 236 posts

Re: I found the best anagram in English (2017)

#141

Post by jodrellblank »

_a_a_a_ wrote: post #135
jodrellblank wrote: post #128

Earlier quoted context omitted.

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…

> to multiply prime numbers one for each alphabet letter to drop the overhead of sorting how does that work?

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_arithme...

[2] https://www.varsitytutors.com/hotmath/hotmath_help/topics/pr...

Re: I found the best anagram in English (2017)

#142

Post by [deleted] »

_a_a_a_ wrote: post #135
jodrellblank wrote: post #128

Earlier quoted context omitted.

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…

> to multiply prime numbers one for each alphabet letter to drop the overhead of sorting how does that work?

[deleted]

Re: I found the best anagram in English (2017)

#143

Post by kmoser »

jstimpfle wrote: post #75
kmoser wrote: post #6

That was pretty good for a one-word anagram. Back in the 1990s I wrote a program that generated anagrams for longer phrases and I was surprised to find these prescient ones: Saddam Hussein = He damns Saudis Charles Manson = Slasher con man David Letterman = Dead mitral vent Mary Jo Kopechne = My joke chaperon * Benito Mussolini = So, I bout Leninism Lee Harvey Oswald = Oe, why ever Dallas? * * "Chaperon" is a valid a…

How many generated anagrams do you have to skim through to find these gems? Was the program written in a way that limits the output to phrases that make at least some sense?

It had features for things like limiting output to anagrams that contain a maximum number of words, or words with a minimum length, so you wouldn't have to slog through every permutation. Usually the most interesting ones had the fewest words. But "interesting" is subjective so if you really wanted to find juicy ones you would have to spend more time combing through the results by hand.

You can find the documentation, a Win32 executable, and the source code here: https://www.kmoser.com/anagrams/

Re: I found the best anagram in English (2017)

#144

Post by kazinator »

abecedarius wrote: post #90
kazinator wrote: post #60

This is the TXR Lisp interactive listener of TXR 285. Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet. TXR's sound system features 120 dB separation between quarreling audiophiles. 1> (flow "/usr/share/dict/words" file-get-lines (group-by sort) hash-values (keep-if cdr) (sort @1 : [chain car len])) (("ho" "oh") ("am" "ma") ("em" "me") ("no" "on") ("ah" "ha") ("it" "ti") ("mu" "um") ("eh" "he") ("a…

Can you explain that last line (sort @1 : [chain car len])?

Yes. @1 indicates where the first argument of the implicit function is inserted. (It's like _ in some partial application syntaxes, but more general because there can be multiple implicit arguments.) The previous steps produced a list of word lists, so we indicate that this giant list, which is the implicit first argument of this function of the pipeline, is going into the first argument position of sort.

The : symbol causes argument 2 of sort to be defaulted, as if it were omitted. That's the comparison function, which defaults to less. In TXR Lisp, you can explicitly default optional arguments with : which enables you to give arguments to later optional arguments to the right of those.

We then specify argument 3, the function for selecting the key to sort by for each element. Each element is a list of words (anagrams fo equal length). We pick the first one with car, and take its length: chain will compose those functions for us.

We use square brackets because the function names are in the function namespace: square brackets provide a function application language in which variables and functions are in one namespace.

Re: I found the best anagram in English (2017)

#145

Post by kazinator »

pavlov wrote: post #120
zirkonit wrote: post #107

Earlier quoted context omitted.

According to GPT-4, an equivalent APL one-liner is: (⊢⌷⍨∘⍋∘≢¨)↑1<≢¨⊢⌸(⍋⊢)¨⎕NGET'/usr/share/dict/words'1

AI-assisted APL could totally be a thing. Why shouldn’t my programs be intense neutron stars of weird symbols, if there’s a superhuman intelligence always at hand to explain and improve the code?

Assembly language generation by symbolic AI (compilers) has been here for 60 years. The "prompts" are very precise and predictably behaved, but requiring the users to learn a specialized language. (Most such languages tend to be concerned with the "how" rather than "what".)

With the new AI, you just specify the "how". Then you get a buggy program, in one of the above specialized languages for the old AI, and the rest of the prompts in the chat are edit instructions on how the AI should fix the code to make it work.

Re: I found the best anagram in English (2017)

#146

Post by jodrellblank »

rak1507 wrote: post #134
jodrellblank wrote: post #124

Earlier quoted context omitted.

That doesn't work in Dyalog APL, comes back with RANK ERROR. It's idiomatic to pick ⊃ the first result of ⎕NGET to get just the lines to work on, and not the other things like file encoding. Then grade-up-right-train-each (⍋⊢)¨ is redunant, it's the same as grade-up-each ⍋¨ The grade is an array of which indices to take to put the argument in sorted order and I don't think it makes sense to group ⌸ by that since the…

(⊢⊢⍤/⍨1<≢¨)({⍵[⍋⍵]}¨⊢∘⊂⌸⊢)words or something like that maybe

Ah!

(That expands to {⍵[⍋⍵]}¨words to sort each word, then use that on the left of Key ⌸ with words on the right, and Key feeds the count and indices into the custom function which is ⊢∘⊂ that takes the indicies with right-tack ⊢ and throws away the count, and encloses them with ⊂. That gives nested arrays of words which sort the same, including invididual words that sort like nothing else. Then (⊢⊢⍤/⍨1<≢¨) added to the left is counting the words in each nesting and filtering out the single ones, and I think ⊢⍤/ is a bodge to use compress in a train without it being misread as reduce when both use the same symbol / ?)

Re: I found the best anagram in English (2017)

#147

Post by justinlloyd »

jodrellblank wrote: post #141
_a_a_a_ wrote: post #135

Earlier quoted context omitted.

> to multiply prime numbers one for each alphabet letter to drop the overhead of sorting how does that work?

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 sam…

Prime combinatorics - I think every programmer independently discovers the technique. You can also determine if a shorter word can be made from a longer word, e.g. "cat" from "catch", by looking for modulo results.

And the technique of Prime Combinatorics for an "alphabet" can be used to solve Poker hands, Blackjack hands, Match 3 puzzle games, slot machine reel positions, and a slew of other similar problems where you would ordinarily have to build a very complex logic table/switch-case/if-then-else decision tree.

Re: I found the best anagram in English (2017)

#148

Post by abecedarius »

kazinator wrote: post #144
abecedarius wrote: post #90

Earlier quoted context omitted.

Can you explain that last line (sort @1 : [chain car len])?

Yes. @1 indicates where the first argument of the implicit function is inserted. (It's like _ in some partial application syntaxes, but more general because there can be multiple implicit arguments.) The previous steps produced a list of word lists, so we indicate that this giant list, which is the implicit first argument of this function of the pipeline, is going into the first argument position of sort. The : symbo…

Thanks! It's interesting to see some ideas from other Lisp dialects. Maybe I'll learn a bit more TXR.

Re: I found the best anagram in English (2017)

#150

Post by kadoban »

jodrellblank wrote: post #141
_a_a_a_ wrote: post #135

Earlier quoted context omitted.

> to multiply prime numbers one for each alphabet letter to drop the overhead of sorting how does that work?

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 sam…

Is it actually faster?

You could just do counting sort if the big-O is important, but I'm a bit suspicious about that big-O anyway. A model where multiplying arbitrarily big numbers is constant time is a bit unrealistic, kind of feels like it's getting off the hook for a log factor for free.

It's also all such small values that I'm not sure the big-O matters either, I'm not confident which would win without just trying it. I'd _guess_ that usual sort probably just wins though, or counting sort if you really went out of the way to optimize it.

Post reply on HN