Liberation through Computer Literacy

[ejolson]

Kira the Koding Kitty (as he insists he be called) says he's only including words containing the 26 English lower-case letters, though he can be purr-suaded to allow hyphens which will be ignored and possibly upper-case which will be treated as lower-case, but only if I give him some turkey. And it will have to wait until he's been fishing!

It looks like Fido may have some furry four-footed company. I hope they get along.

I've added a heap data structure to the insane line-numbered Basic anagram program. The revised program reads as follows:

Code: Select all

1000 REM hanagram.bas -- Find anagrams
1010 REM Written July 24, 2019 by Eric Olson
1020 REM
1030 REM This program demonstrates using letter counts and a heap to
1040 REM find anagrams in the insane British dictionary.
1050 REM
2000 F$="/usr/share/dict/british-english-insane"
2001 REM F$="tail.dat"
2010 M0=0:OPEN F$ FOR INPUT AS #1
2015 IF EOF(1)<>0 THEN 2030
2020 INPUT #1,A$:M0=M0+1:GOTO 2015
2030 DIM L$(M0),K$(M0),H(M0),V0(26)
2040 CLOSE #1:OPEN F$ FOR INPUT AS #1
2050 A1=ASC("a")-1:A2=ASC("0"):N0=0:H0=0
2060 FOR I=1 TO M0:INPUT #1,A$
2063 FOR J=1 TO 26:V0(J)=0:NEXT J:J=0
2065 IF J>=LEN(A$) THEN 2075
2068 J=J+1:C=ASC(MID$(A$,J,1))-A1
2070 IF (C<1) OR (C>26) THEN 2130
2071 V0(C)=V0(C)+1:GOTO 2065
2075 V$="":FOR J=1 TO 26
2080 V$=V$+CHR$(V0(J)+A2):NEXT J
2120 N0=N0+1:L$(N0)=A$:K$(N0)=V$:GOSUB 4000
2130 NEXT I:CLOSE #1
2140 IF H0=0 THEN 9000
2150 GOSUB 4500
2160 J0=J:L$(J0)=L$(J0)+":"
2170 IF H0=0 THEN 2400 
2180 GOSUB 4500
2190 IF K$(J)<>K$(J0) THEN 2160
2200 L$(J0)=L$(J0)+" "+L$(J)+",":GOTO 2170
2400 FOR I=1 TO N0:A$=L$(I)
2410 IF RIGHT$(A$,1)<>"," THEN 2430
2420 PRINT LEFT$(A$,LEN(A$)-1)
2430 NEXT I
2900 GOTO 9000
4000 REM Insert a key into the heap
4010 REM  inputs: N0 the key to insert
4020 H0=H0+1:R=H0:H(R)=N0
4030 S=INT(R/2):IF S=0 THEN RETURN
4035 B0$=K$(H(R))+L$(H(R))
4036 B1$=K$(H(S))+L$(H(S))
4040 IF B0$>=B1$ THEN RETURN
4060 T=H(S):H(S)=H(R):H(R)=T:R=S:GOTO 4030
4500 REM Remove a key from the heap
4510 REM  output: J the key removed
4520 J=H(1):H(1)=H(H0):H0=H0-1:S=1
4530 R0=2*S:R1=R0+1:IF R0>H0 THEN RETURN
4535 B0$=K$(H(R0))+L$(H(R0)):IF R1>H0 THEN 4550
4536 B1$=K$(H(R1))+L$(H(R1))
4540 IF B0$>=B1$ THEN 4600
4550 IF B0$>=K$(H(S))+L$(H(S)) THEN RETURN
4560 T=H(R0):H(R0)=H(S):H(S)=T:S=R0:GOTO 4530
4600 IF B1$>=K$(H(S))+L$(H(S)) THEN RETURN
4660 T=H(R1):H(R1)=H(S):H(S)=T:S=R1:GOTO 4530
9000 END

Since this is an O(nlogn) algorithm, it is now reasonable from a certain point of view to process the insane British dictionary. The results are

Code: Select all

$ time ./gplbasic hanagram.bas >hanagram-gpl.insane 

real    14m1.851s
user    14m0.341s
sys 0m0.131s
$ fbc -lang qb hanagram.bas
$ time ./hanagram >hanagram-fbc.insane

real    0m46.614s
user    0m45.546s
sys 0m1.000s
$ time ./anagram.perl >perl.insane

real    0m13.547s
user    0m13.349s
sys 0m0.182s
$ md5sum *.insane
bec74aa3b31577edbb291aeb7269a4d5  hanagram-fbc.insane
bec74aa3b31577edbb291aeb7269a4d5  hanagram-gpl.insane
bec74aa3b31577edbb291aeb7269a4d5  perl.insane

[Heater]

John Spikowski,

This challenge seems to favor languages with built in functions like sort , islower, ...

Please tell me you are not serious there.

How can there be favoritism when writing sort and character checking functions for oneself is not exactly difficult if ones language of choice does not provide them? See posts above.

The same bias was shown with fibo and languages with BIGINT support.

Clearly not. As I have told you before there are solutions to the fibo challenge in all manner of languages, with and without BIGINT support, and that if you want to compare speed, some of the ones without it came top of the heap.

Seems I should remind, again, that sheer performance was never the primary goal of the fibo challenge. Neither this one I gather. As ejolson said back in 1978: "If you get the result, you win".

Let's rename this thread "Obscure challenges with the goal to define Infinity".

I'm not sure they are "obscure". I have seen such challenges, especially anagrams, circulating for decades. Only now we have more languages easily available.

Now, do not blame us if you cannot get ScriptBasic to do what budding programmers have been practicing since ever there were computers.

We look forward to your ScriptBasic solution.

[John Spikowski]

We look forward to your ScriptBasic solution.

I was hoping @ejolson was going to use ScriptBasic for his example due to his associative array comment.

[Heater]

Bah! Cat could not nap...

Code: Select all

//
// insane-british-anagram.cpp - Find words that have valid anagrams
//                              Words sourced from Debian's british-english-insane dictionary
//
// heater - 2019-07-25
// 
#include <fstream>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <unordered_map> 
#include <vector> 

std::string getFileContents(const char *filename) {
    std::ifstream in(filename, std::ios::in | std::ios::binary);
    if (in) {
        std::string contents;
        in.seekg(0, std::ios::end);
        contents.resize(in.tellg());
        in.seekg(0, std::ios::beg);
        in.read(&contents[0], contents.size());
        in.close();
        return(contents);
    }
    throw(std::runtime_error("Shit happened!"));
}

char* sortString (const char* s) {
    char* string = (char*)malloc(strlen(s) + 1); 
    strcpy (string, s); 
    char temp;
    int i, j;
    int n = strlen(string);

    for (i = 0; i < n-1; i++) {
        for (j = i+1; j < n; j++) {
            if (string[i] > string[j]) {
            temp = string[i];
            string[i] = string[j];
            string[j] = temp;
            }
        }
    }
    return string;
}

int main (int argc, char* argv[]) {
    // Map container for sets of anagrams 
    // An anagram set is simply a string of format like: "whiter: wither, wrihte, writhe"
    std::unordered_map<std::string, std::string> anagramMap;
    std::unordered_map<std::string, std::string>::iterator it;

    // An ordered index of anagram set keys 
    // Key for the anagram sets in the map are the ordered characters of the words.
    std::vector<std::string> index;

    auto dictionary = getFileContents("/usr/share/dict/british-english-insane");
    char* dictionaryPtr = (char*)dictionary.c_str();
    char* wordPtr = dictionaryPtr;
    char* charPtr = wordPtr;
    bool reject = false;
    while (1) {
        if (islower(*charPtr)) {
            // We are scanning a valid word
            charPtr++;
        } else if ((*charPtr) == '\n') {
            // We have hit the end of a word, use the word if it's valid
            *charPtr = 0;
            if (!reject) {
                // Do we have a word with this key (potential anagram)?
                char* key = sortString(wordPtr);
                it = anagramMap.find(key);
                if (it == anagramMap.end()) {
                    // No: Add it to the map as start of new anagram set.
                    anagramMap[key] = std::string(wordPtr);
                    index.push_back(key);
                } else {
                    // Yes: Append it to the existing anagram set.
                    it->second.append(", ").append(wordPtr); 
                }
            }
            charPtr++;
            wordPtr = charPtr;
            reject = false;
        } else if ((*charPtr) != 0) {
            // Invalid character
            reject = true;
            charPtr++;
        } else {
            // End of dictionary
            break;
        }
    }

    // Iterate over the collected anagram sets in order of the index.
    for(auto const& key: index) {
        it = anagramMap.find(key);
        // Sets with a "," contain more than one word, the anagrams!
        size_t found = it->second.find(',');
        if (found != std::string::npos) {
            std::string fart = it->second;
            fart.replace(found, 1, ":");
            std::cout << fart << std::endl ;
        }
    }
    return (0);
}

With results:

Code: Select all

$ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m2.290s
user    0m1.954s
sys     0m0.329s
pi@pi3-buster-1:~ $ time node ./insane-british-anagram.js > insane-british-anagram-js.txt
rss 117.82 MB
heapTotal 83.57 MB
heapUsed 77.37 MB
external 0.64 MB

real    0m11.848s
user    0m13.771s
sys     0m0.301s
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt

Down to only 5 times faster.

I'm not sure the code is any more readable than ejolson's master piece above.

[ejolson]

Code: Select all

pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt

It's nice to have a C++ anagram finder and a speedy one at that. Note that when comparing output, I would prefer if you computed the md5 sum of both files rather than the same one twice.

There seems to be a bubble sort in the middle of the code. Were the standard C++ sorting templates slower or unfathomable? What happened to the idea of using vectors of letter counts? That's what the Basic code does. I think it would be very interesting to hear how the algorithm for sortString was chosen.

[Heater]

ejolson,

I would prefer if you computed the md5 sum of both files rather than the same one twice.

Bummer. Good point:

Code: Select all

$ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m2.253s
user    0m1.873s
sys     0m0.378s
pi@pi3-buster-1:~ $ time node ./insane-british-anagram.js > insane-british-anagram-js.txt
rss 119.55 MB
heapTotal 83.82 MB
heapUsed 77.32 MB
external 0.64 MB

real    0m11.948s
user    0m13.788s
sys     0m0.289s
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt insane-british-anagram-js.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-js.txt

That's what happens when the cat does not get a nap.

There seems to be a bubble sort in the middle of the code. Were the standard C++ sorting templates slower or unfathomable?

Yeah, I have no idea. Just put the thing I could find quickest in there that would get me a result.

What happened to the idea of using vectors of letter counts?

That is the thing I had in the back of my mind. That bubble sort is not really there to do sorting of characters in strings. It's there to make a unique key that is invariant for all anagrams of the the given string.

I should rename it to makeKey(...) and have it return a string of letter frequencies instead.

Aside: It often amazes me how naming a function/method/class after what you want it to do rather than how it actually does it totally changes ones view of a program and leads to all kind of simplifications. Naming is the hardest thing to get right in software engineering.

I think it would be very interesting to hear how the algorithm for sortString was chosen.

It was the first thing I found on a google search

Like I say, enough to get a correct result before thinking about tweaking this and that.

Also: The map thing I am using there uses a std::string for keys and values. Where the value string holds all the anagrams of a word concatenated. That must be a lot of new string allocation going on. I would rather it used an array of pointers into the originally loaded dictionary string.

To be continued...

[John Spikowski]

Here is the ScriptBasic modified @ejolson anagram. (tail -n 10000)

Code: Select all

flen = FILELEN("tail.dat")
OPEN "tail.dat" FOR INPUT AS #1
fraw = INPUT(flen, 1)
SPLITA fraw BY "\n" TO wa
CLOSE(1)

a1 = ASC("a") - 1
a2 = ASC("0")
n0 = 0

FOR i = 0 TO UBOUND(wa)
  SPLITA STRING(27, "0") BY "" TO v0
  j = 0
2065:
  IF j >= LEN(wa[i]) THEN GOTO 2075
  j += 1
  c = ASC(MID(wa[i], j, 1)) - a1
  IF c < 1 OR c > 26 THEN GOTO 2130
  v0[c] = v0[c] + 1
  GOTO 2065
2075:
  v = ""
  FOR j = 1 TO 26
    v &= CHR(v0[j] + a2)
  NEXT
  j = 0
2090:
  IF j >= n0 THEN GOTO 2120
  j = j + 1
  IF k[j] <> v THEN GOTO 2090
  l[j] &= " " & wa[i] & ","
  GOTO 2130
2120:
  n0 += 1
  l[n0] = wa[i] & ":"
  k[n0] = v
2130:
NEXT

FOR i = 1 TO n0
  a = l[i]
  IF RIGHT(a, 1) = ":" THEN GOTO 2430
  PRINT LEFT(a, LEN(a) - 1),"\n"
2430:
NEXT


jrs@jrs-laptop:~/sb/ejolson$ time scriba anagram.sb > anagram.out

real	1m35.671s
user	1m35.584s
sys	0m0.017s
jrs@jrs-laptop:~/sb/ejolson$ 


wheedle: wheeled
wheer: where
whein: whine
whemmel: whemmle
whenso: whosen
whereat: wreathe
whereer: wherere
wherrit: whirret, writher
whilend: whindle
whilter: whirtle
whipray: yarwhip
whips: whisp
whirliest: wiltshire
whirrets: writhers
whirtles: whistler
whissing: wishings
whist: whits, wisht, withs
whister: withers, writhes
whisting: whitings
whistling: whitlings
whit: with
white: withe
whited: withed
whiten: withen
whitepot: whitetop
whiter: wither, wrihte, writhe
whites: withes
whitest: withset
whitewares: wreathwise
whitewood: withewood
whitier: withier
whities: withies
whitiest: withiest
whitin: within
whiting: withing
whitret: whitter
whitrets: whitster, whitters
whity: withy
whomsoever: whosomever
whoopies: whoopsie
whooses: wooshes
whort: worth, wroth
whorts: worths
whoso: woosh
wicht: witch
wickeder: wickered
widdle: wilded
wide: wied
widely: wieldy
widen: wined
wider: wierd, wired, wride, wried
wides: wised
widest: wisted
widgeon: wongied
wiel: wile
wield: wiled
wiels: wiles
wigeons: wongies
wiggler: wriggle
wigglers: wriggles
wildflower: wildfowler
wildflowers: wildfowlers
wildness: windless
willest: willets
wilroun: wournil
wilting: witling
wimpler: wrimple
windel: windle
windocks: windsock
windores: windrose
windroses: wordiness
wines: wisen
winkel: winkle
winkler: wrinkle
winklers: wrinkles
winklot: wotlink
winnel: winnle
winster: winters
winzes: wizens
wipings: wisping
wips: wisp
wirble: wrible
wirer: wrier
wirerooms: worrisome
wires: wiser, wries
wisents: witness
wises: wisse
wisest: witess
wisewoman: womanwise
wishes: wisshe
wishmay: yahwism
wissel: wissle
wist: wits
wiste: wites
wister: wriest, writes
withdrawers: witherwards
withering: wrightine
witherso: worthies
wiver: wrive
woeful: woulfe
woiwodes: woodwise
wolfkins: wolfskin
wolof: woolf
wolter: wortle
wonnot: wonton
wooden: wooned
woodlark: workload
woodlarks: workloads
woodnote: woodtone
woodnotes: woodstone, woodtones
woodworm: wormwood
woodworms: wormwoods
wordier: worried
workyard: yardwork
worst: worts
worthful: wrothful
worthily: wrothily
worthiness: wrothiness
worthy: wrothy
wost: wots
woy: yow
wraitly: wrytail
wrate: wreat
wrist: writs
wrister: writers
wristing: writings
wye: yew
wyes: yews
xanthein: xanthine
xantheins: xanthines
xiv: xvi
xix: xxi
xxiv: xxvi
xylidin: xylinid
xylitone: xylonite
xylomas: xylosma
yachan: yancha
yachtmanships: yachtsmanship
yade: yead
yager: yerga
yamun: yuman
yander: yarned
yare: year
yarely: yearly
yarta: yatra
yartas: yatras
yate: yeat, yeta
yates: yeast, yeats
yearend: yearned
yede: yeed
yedes: yeeds
yedo: yode
yees: yese
yelk: ylke
yelks: ylkes
yelm: ylem
yelms: ylems
yeo: yoe
yeti: yite
yetis: yites
yeuk: yuke
yeuks: yukes
yirm: ymir
yodel: yodle
yodels: yodles
youk: yuko
youks: yukos
yuckel: yuckle
zambo: zomba
zaminder: zemindar
zaniest: zeatins
zanze: zazen
zanzes: zazens
zapus: zupas
zari: zira
zedonk: zonked
zein: zine
zeins: zines
zemmi: zimme
zendic: zinced
zendik: zinked
zendo: zoned
zenick: zincke
zeno: zone
zinciest: zincites
zinco: zonic
zolotink: zolotnik
zoography: zoogrpahy

[Heater]

ejolson,

What happened to the idea of using vectors of letter counts?

Not looking good.

If I replace that letter sorting function with a letter frequency counting function it slows things down by about 15%.

Code: Select all

char* makeAnagramKey (const char* s) {
    char* key = (char*)malloc(27);
    memset(key, 'a', 27);
    key[26] = 0;

    for (size_t i = 0; i < strlen(s); i++) {
        size_t x = s[i] - 'a';
        key[x]++;
    }
    return key;
}

Interestingly if I replace that malloc() with a simple pointer moving up a big memory space it saves no time at all

[ejolson]

Interestingly if I replace that malloc() with a simple pointer moving up a big memory space it saves no time at all

Does it save any memory to move the malloc up?

The note from the zombies about replacing strings of letter counts with dogarithms and prime numbers sounds interesting. As Fido won't tell me anything more, I'm tempted to let them in so I can see the code. However, to avoid the apocalypse that may not be such a good idea.

[Heater]

ejolson,

Code: Select all

Does it save any memory to move the malloc up?

No idea, I backed out the change, didn't much like the aesthetics of it anyway.

It probably uses a lot less memory now that I free all the original keys after they have been plugged into the map and index.

I changed to using vectors of pointers into the dictionary, instead of std::strings, for the anagram collections. Not sure it made much difference.

Then I remembered that somebody, could have been me, once said C++ output streams were really slow. So I changed it to use fputs(), for a useful saving of over 30% in execution time!

The new insane cpp anagram finder:

Code: Select all

//
// insane-british-anagram.cpp - Find words that have valid anagrams
//                              Words sourced from Debian's british-english-insane dictionary
//
// heater - 2019-07-25
// 
#include <fstream>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <unordered_map> 
#include <vector> 

std::string getFileContents(const char *filename) {
    std::ifstream in(filename, std::ios::in | std::ios::binary);
    if (in) {
        std::string contents;
        in.seekg(0, std::ios::end);
        contents.resize(in.tellg());
        in.seekg(0, std::ios::beg);
        in.read(&contents[0], contents.size());
        in.close();
        return(contents);
    }
    throw(std::runtime_error("Shit happened!"));
}

char* sortString (const char* s) {
    int n = strlen(s);
    char* string = (char*)malloc(n + 1); 
    strcpy (string, s); 
    char temp;
    int i, j;

    for (i = 0; i < n-1; i++) {
        for (j = i+1; j < n; j++) {
            if (string[i] > string[j]) {
            temp = string[i];
            string[i] = string[j];
            string[j] = temp;
            }
        }
    }
    return string;
}

int main (int argc, char* argv[]) {
    // Map container for sets of anagrams 
    // An anagram set is simply a vector of pointers to words in the dictionary
    // Keys for the anagram sets in the map are the ordered characters of the words.
    std::unordered_map<std::string, std::vector<char*> >anagramMap;
    std::unordered_map<std::string, std::vector<char*>>::iterator it;

    // An ordered index of anagram set keys 
    std::vector<std::string> index;

    auto dictionary = getFileContents("/usr/share/dict/british-english-insane");
    char* dictionaryPtr = (char*)dictionary.c_str();
    char* wordPtr = dictionaryPtr;
    char* charPtr = wordPtr;
    bool reject = false;
    while (1) {
        if (islower(*charPtr)) {
            // We are scanning a valid word
            charPtr++;
        } else if ((*charPtr) == '\n') {
            // We have hit the end of a word, use the word if it's valid
            *charPtr = 0;
            if (!reject) {
                // Do we have a word with this key (potential anagram)?
                char* key = sortString(wordPtr);
                it = anagramMap.find(key);
                if (it == anagramMap.end()) {
                    // No: Add it to the map as start of new anagram set.
                    anagramMap[key].push_back(wordPtr);

                    // And add the new anagram set to index
                    index.push_back(key);
                } else {
                    // Yes: Append it to the existing anagram set.
                    it->second.push_back(wordPtr); 
                }
                free(key);
            }
            charPtr++;
            wordPtr = charPtr;
            reject = false;
        } else if ((*charPtr) != 0) {
            // Invalid character
            reject = true;
            charPtr++;
        } else {
            // End of dictionary
            break;
        }
    }

    // Iterate over the collected anagram sets in order of the index.
    for(auto const& key: index) {
        it = anagramMap.find(key);
        if (it->second.size() > 1) {
            int count = 0;
            for(const auto& value: it->second) {
                if (count == 1) {
                    fputs(": ", stdout);                
                } else if (count > 1) {
                    fputs(", ", stdout);                
                }
                fputs(value, stdout);                
                count++;
            }
            fputs("\n", stdout);                
        }
    }
    return (0);
}

Using std::cout:

Code: Select all

$ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m3.167s
user    0m2.608s
sys     0m0.380s

pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt

Using fputs:

Code: Select all

pi@pi3-buster-1:~ $ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m2.026s
user    0m1.865s
sys     0m0.160s
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
pi@pi3-buster-1:~ $

I think that is as far as this is going to go.

[ejolson]

I think that is as far as this is going to go.

The new code seems to be a big improvement over the old one. It clearly generates fewer greenhouse gases and even smells better. For the record, did the fart variable in the previous code have any mnemonic meaning other than the obvious one?

Those zombies are tempting me. I just received another note which read

Having no brain means we're not insane. Our dogarithmic anagram program runs faster on the Raspberry Pi than any other. Let us in now.

The reference to brains worries me, though, because of the previous experience I had with plants and zombies.

[Heater]

ejolson,

The note from the zombies about replacing strings of letter counts with dogarithms and prime numbers sounds interesting.

It does. And oddly enough I started thinking about that when we first discussed using letter frequencies as an index.

If you really want to unleash the awesome power of the Prime Directive of Arithmetic: https://en.wikipedia.org/wiki/Fundament ... arithmetic do not let the zombies in, just continue reading:

A quick experiment in Javascript yields a sweet algorithm to hash words into numbers by multiplying the prime number we assign to each lower case letter of the alphabet:

Code: Select all

const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

function primeHash (word) {
    let hash = 1
    for (var i = 0; i < word.length; i++) {
        let index = word.charCodeAt(i) -  97  
        hash = (hash * primes[index])
    }
    return(hash)
}

Sadly when plugged into the JS anagram finder it gets faster but produces the wrong result.

Undeterred, here is the primeHash in C:

Code: Select all

// One prime number for each lower case letter of the alphabet
int primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

uint64_t primeHash (char* word) {
    uint64_t hash = 1;
    for (size_t i = 0; i < strlen(word); i++) {
        int index = word[i] -  97;  
        hash = hash * primes[index];
    }
    return hash;
}

Plugging that into the CPP anagram finder reduces execution time from 2 seconds to 1.5. A 25% speed up and the correct results. Yay!

Code: Select all

$ g++ -std=c++17 -Wall -O3 -o insane-british-anagram insane-british-anagram.cpp
pi@pi3-buster-1:~ $ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m1.460s
user    0m1.359s
sys     0m0.100s
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt selfgrams_pl.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  selfgrams_pl.txt

Now, that primeHash() has to overflow at some point, apparently not for any word in English lower case, or at least if it does there was no hash collision. I suspect the JS version is running out of digits somewhere as it's using the mantissa bits of 64 bit floats.

The insane anagram finder in CPP using primeHash() :

Code: Select all

//
// insane-british-anagram.cpp - Find words that have valid anagrams
//                              Words sourced from Debian's british-english-insane dictionary
//
// heater - 2019-07-25
// 
#include <fstream>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <unordered_map> 
#include <vector> 

std::string getFileContents(const char *filename) {
    std::ifstream in(filename, std::ios::in | std::ios::binary);
    if (in) {
        std::string contents;
        in.seekg(0, std::ios::end);
        contents.resize(in.tellg());
        in.seekg(0, std::ios::beg);
        in.read(&contents[0], contents.size());
        in.close();
        return(contents);
    }
    throw(std::runtime_error("Shit happened!"));
}

// One prime number for each lower case letter of the alphabet
int primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

uint64_t primeHash (char* word) {
    uint64_t hash = 1;
    for (size_t i = 0; i < strlen(word); i++) {
        int index = word[i] -  97;  
        hash = hash * primes[index];
    }
    return hash;
}

int main (int argc, char* argv[]) {
    // Map container for sets of anagrams 
    // An anagram set is simply a vector of pointers to words in the dictionary
    // Keys for the anagram sets in the map are the ordered characters of the words.
//    std::unordered_map<std::string, std::vector<char*> >anagramMap;
//    std::unordered_map<std::string, std::vector<char*>>::iterator it;
    std::unordered_map<uint64_t, std::vector<char*> >anagramMap;
    std::unordered_map<uint64_t, std::vector<char*>>::iterator it;

    // An ordered index of anagram set keys 
    std::vector<uint64_t> index;

    auto dictionary = getFileContents("/usr/share/dict/british-english-insane");
    char* dictionaryPtr = (char*)dictionary.c_str();
    char* wordPtr = dictionaryPtr;
    char* charPtr = wordPtr;
    bool reject = false;
    while (1) {
        if (islower(*charPtr)) {
            // We are scanning a valid word
            charPtr++;
        } else if ((*charPtr) == '\n') {
            // We have hit the end of a word, use the word if it's valid
            *charPtr = 0;
            if (!reject) {
                // Do we have a word with this key (potential anagram)?
                uint64_t key = primeHash(wordPtr);

                it = anagramMap.find(key);
                if (it == anagramMap.end()) {
                    // No: Add it to the map as start of new anagram set.
                    anagramMap[key].push_back(wordPtr);

                    // And add the new anagram set to index
                    index.push_back(key);
                } else {
                    // Yes: Append it to the existing anagram set.
                    it->second.push_back(wordPtr); 
                }
            }
            charPtr++;
            wordPtr = charPtr;
            reject = false;
        } else if ((*charPtr) != 0) {
            // Invalid character
            reject = true;
            charPtr++;
        } else {
            // End of dictionary
            break;
        }
    }

    // Iterate over the collected anagram sets in order of the index.
    for(auto const& key: index) {
        it = anagramMap.find(key);
        if (it->second.size() > 1) {
            int count = 0;
            for(const auto& value: it->second) {
                if (count == 1) {
                    fputs(": ", stdout);                
                } else if (count > 1) {
                    fputs(", ", stdout);                
                }
                fputs(value, stdout);                
                count++;
            }
            fputs("\n", stdout);                
        }
    }
    return (0);
}

Amazingly this code is only 3 times slower on a Pi 3 than my x86 PC!

[jahboater]

Undeterred, here is the primeHash in C:

Code: Select all

// One prime number for each lower case letter of the alphabet
int primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

uint64_t primeHash (char* word) {
    uint64_t hash = 1;
    for (size_t i = 0; i < strlen(word); i++) {
        int index = word[i] -  97;  
        hash = hash * primes[index];
    }
    return hash;
}

Does it help any if you hoist the strlen() out of the loop?
Or declare "word" const so the compiler can do so.
As in ....

Code: Select all

static uint64_t 
primeHash( char const * const word ) {
      // One prime number for each lower case letter of the alphabet
    static const int primes[26] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };
    uint64_t hash = 1;
    const size_t len = strlen(word);
    size_t i = 0;
     
    do
      hash *= primes[ word[i] - 97 ];
    while( ++i < len );
    
    return hash;
}

[Heater]

I wondered about that as I wrote it. I made most of the changes you suggest:

Code: Select all

uint64_t primeHash (const char* const word) {
    // One prime number for each lower case letter of the alphabet
    static const uint64_t primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    uint64_t hash = 1;
    const size_t len = strlen(word);
    for (size_t i = 0; i < len; i++) {
        int index = word[i] -  97;
        bool overflow = __builtin_umull_overflow (hash, primes[index], &hash);
        //assert (!overflow);
    }
    return hash;
}

If it makes any difference in execution time it's lost in the noise on my PC.

If I uncomment that assert we find there are tons of overflows going on in that hash. Amazingly none of then for the anagrams. Or at least not in a way that has an effect.

Should I put our big integer arithmetic in there?

[ejolson]

Should I put our big integer arithmetic in there?

I was surprised JavaScript didn't switch to big-number arithmetic and get the right answer.

Can you reorder the primes to avoid an overflow? I asked the lead developer of FidoBasic but all I heard was some whining about dogarithms not logarithms. I think Fido wants some of Napier's bones to chew on. I wonder if it would be better to use only odd primes.

[Heater]

Sadly JS does not automatically "switch" to using big int maths like Python. JS has a separate BigInt type.

Oddly I can't get it to work properly using that either.

[Heater]

OK, got the JS version of insane anagram working with the primeHash function and BigInts

Turns out it was generating the right anagrams but outputting them in the wrong order. Why? Because of that unspecified behavior I mentioned earlier. Namely, that anagramSets object is not guaranteed to return members in the order they were inserted. It just happened to do so earlier, presumably because the keys were sorted. Now that the keys are randomized it breaks.

So I introduced an index array to keep an order list of anagram keys.

Using the primeHash the JS anagram finder gets a 25% speed boost. Handily beating the Perl solution.

Code: Select all

$ time node insane-british-anagram.js > insane-british-anagram-js.txt
rss 111.11 MB
heapTotal 80.61 MB
heapUsed 77.35 MB
external 0.6 MB

real    0m8.471s
user    0m9.405s
sys     0m0.272s
pi@pi3-buster-1:~ $ time ./selfgrams.pl > selfgrams_pl.txt

real    0m11.308s
user    0m11.137s
sys     0m0.162s
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-js.txt selfgrams_pl.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-js.txt
addeda36a4631afc983f3bff13742e36  selfgrams_pl.txt

The new JS insane anagram finder using primeHash:

Code: Select all

//
// insane-british-anagram.js - Find words that have valid anagrams
//                             Words sourced from Debian's british-english-insane dictionary
//
// heater       - 2019-07-26
// 
const fs = require('fs')

const primes = [
    2n,   3n,  5n,  7n, 11n, 13n, 17n, 19n, 23n,
    29n, 31n, 37n, 41n, 43n, 47n, 53n, 59n, 61n,
    67n, 71n, 73n, 79n, 83n, 89n, 97n, 101n
]

function primeHash (word) {
    let hash = 1n
    for (var i = 0; i < word.length; i++) {
        let index = word.charCodeAt(i) -  97  
        hash = hash * primes[index]
    }
    return(hash)
}

const allLowerCasePattern = /^[a-z]+$/
const anagramSets = {}
const index = []

const file = fs.readFileSync('/usr/share/dict/british-english-insane', 'utf-8');

const dictionary = file.split('\n')

for (let i = 0; i < dictionary.length; i++) {
    const word = dictionary[i]
    if (allLowerCasePattern.test(word)) {
        let key = primeHash(word).toString()

        if (anagramSets[key]) {
            anagramSets[key].push(word)
        } else {
            anagramSets[key] = [word]
            index.push(key)
        }
    }
}

let output = ""
for (let i = 0; i < index.length; i++) {
    let anagramSet = anagramSets[index[i]]
    if (anagramSet.length > 1) {
        output += anagramSet.join(", ").replace(',', ':') + '\n'
    }
}

const used = process.memoryUsage();
for (let key in used) {
    process.stderr.write(`${key} ${Math.round(used[key] / 1024 / 1024 * 100) / 100} MB\n`);
}

process.stdout.write(output)

[Paeryn]

I was testing Kira's code yesterday whilst he was out, he was using an approach of counting letter distributions making a 96-bit key that identifies anagrams (though not all bits are used and a few are only for relatively few cases). When I asked him whether he could get it down to 64-bits he mumbled about the Pharaoh's knowing not to meddle in the arcane arts of Kitty magic (and that the overheads of reducing it would probably take longer than what would be saved).

Unfortunately his map had a few bugs (words weren't always getting added and causing segfaults when it tried to link anagrams to them) and when I offered to fix it for him he took offence, swatted the mouse a few times before laying out on the keyboard saying that it was his Komputer and that I should concern myself with more pressing matters like how to keep him cool in this overbearing heat. Then he promptly fell asleep leaving me to figure out how to shut the PC down whilst new windows kept opening because of the keys he was laid on...

[Heater]

Something weird is going on. I ran the Perl, JS and CPP anagram generators on a Pi 3 running the 64 bit Pi64 operating system. All the md5sums come out different. Well, all the same but different to the Pi 3 with Buster:

On the 64 bit OS:

Code: Select all

$ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m1.359s
user    0m1.234s
sys     0m0.119s
pi@pi64-aalto:~$ time node insane-british-anagram.js > insane-british-anagram-js.txt
rss 164.86 MB
heapTotal 122.77 MB
heapUsed 116.05 MB
external 0.58 MB

real    0m7.600s
user    0m9.436s
sys     0m0.496s
pi@pi64-aalto:~$ time ./selfgrams.pl > selfgrams-pl.txt

real    0m11.459s
user    0m11.172s
sys     0m0.285s
pi@pi64-aalto:~$ md5sum insane-british-anagram-cpp.txt insane-british-anagram-js.txt selfgrams-pl.txt 
bec74aa3b31577edbb291aeb7269a4d5  insane-british-anagram-cpp.txt
bec74aa3b31577edbb291aeb7269a4d5  insane-british-anagram-js.txt
bec74aa3b31577edbb291aeb7269a4d5  selfgrams-pl.txt

On the 32 bit OS:

Code: Select all

 $ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m1.434s
user    0m1.342s
sys     0m0.092s
pi@pi3-buster-1:~ $ time node insane-british-anagram.js > insane-british-anagram-js.txt
rss 107.84 MB
heapTotal 76.87 MB
heapUsed 73.51 MB
external 0.6 MB

real    0m8.465s
user    0m9.568s
sys     0m0.271s
pi@pi3-buster-1:~ $ time ./selfgrams.pl > selfgrams-pl.txt

real    0m11.398s
user    0m11.187s
sys     0m0.180s
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt insane-british-anagram-js.txt selfgrams-pl.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-js.txt
addeda36a4631afc983f3bff13742e36  selfgrams-pl.txt

On my x86-64 PC:

Code: Select all

$ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m0.381s
user    0m0.203s
sys     0m0.156s
$ time node insane-british-anagram.js > insane-british-anagram-js.txt
rss 170.07 MB
heapTotal 144.39 MB
heapUsed 121.55 MB
external 0.59 MB

real    0m1.681s
user    0m1.266s
sys     0m0.672s
$ time ./selfgrams.pl > selfgrams-pl.txt

real    0m2.051s
user    0m1.484s
sys     0m0.531s
$ md5sum insane-british-anagram-cpp.txt insane-british-anagram-js.txt selfgrams-pl.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-js.txt
addeda36a4631afc983f3bff13742e36  selfgrams-pl.txt

[gkreidl]

Something weird is going on. I ran the Perl, JS and CPP anagram generators on a Pi 3 running the 64 bit Pi64 operating system. All the md5sums come out different. Well, all the same but different to the Pi 3 with Buster:

On the 64 bit OS:

Code: Select all

$ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m1.359s
user    0m1.234s
sys     0m0.119s
pi@pi64-aalto:~$ time node insane-british-anagram.js > insane-british-anagram-js.txt
rss 164.86 MB
heapTotal 122.77 MB
heapUsed 116.05 MB
external 0.58 MB

real    0m7.600s
user    0m9.436s
sys     0m0.496s
pi@pi64-aalto:~$ time ./selfgrams.pl > selfgrams-pl.txt

real    0m11.459s
user    0m11.172s
sys     0m0.285s
pi@pi64-aalto:~$ md5sum insane-british-anagram-cpp.txt insane-british-anagram-js.txt selfgrams-pl.txt 
bec74aa3b31577edbb291aeb7269a4d5  insane-british-anagram-cpp.txt
bec74aa3b31577edbb291aeb7269a4d5  insane-british-anagram-js.txt
bec74aa3b31577edbb291aeb7269a4d5  selfgrams-pl.txt

On the 32 bit OS:

Code: Select all

 $ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m1.434s
user    0m1.342s
sys     0m0.092s
pi@pi3-buster-1:~ $ time node insane-british-anagram.js > insane-british-anagram-js.txt
rss 107.84 MB
heapTotal 76.87 MB
heapUsed 73.51 MB
external 0.6 MB

real    0m8.465s
user    0m9.568s
sys     0m0.271s
pi@pi3-buster-1:~ $ time ./selfgrams.pl > selfgrams-pl.txt

real    0m11.398s
user    0m11.187s
sys     0m0.180s
pi@pi3-buster-1:~ $ md5sum insane-british-anagram-cpp.txt insane-british-anagram-js.txt selfgrams-pl.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-js.txt
addeda36a4631afc983f3bff13742e36  selfgrams-pl.txt

On my x86-64 PC:

Code: Select all

$ time ./insane-british-anagram > insane-british-anagram-cpp.txt

real    0m0.381s
user    0m0.203s
sys     0m0.156s
$ time node insane-british-anagram.js > insane-british-anagram-js.txt
rss 170.07 MB
heapTotal 144.39 MB
heapUsed 121.55 MB
external 0.59 MB

real    0m1.681s
user    0m1.266s
sys     0m0.672s
$ time ./selfgrams.pl > selfgrams-pl.txt

real    0m2.051s
user    0m1.484s
sys     0m0.531s
$ md5sum insane-british-anagram-cpp.txt insane-british-anagram-js.txt selfgrams-pl.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-cpp.txt
addeda36a4631afc983f3bff13742e36  insane-british-anagram-js.txt
addeda36a4631afc983f3bff13742e36  selfgrams-pl.txt

The insane dictionary versions on Buster and Stretch seem to be different.

[Heater]

Ah, silly me, was getting so tired after a busy, long, and very hot day, that the obvious did not occur to me.

You know how sometimes you can be so concentrated on one part of a problem, in this case prime number hashes and overflows, as to totally miss other things going on.

Or, I blame all those people running Perl, Python and BASIC and all the global warming they are causing

Climate change, the true Digital Apocalypse. Think I'm joking, consider the following:

a) Bitcoin mining
https://www.theverge.com/2019/7/4/20682 ... comparison

b) People complaining that power consumption is limiting super computer progress:
https://cacm.acm.org/news/192296-superc ... m/fulltext

c) People finding that expanding AI is an ecological disaster:
https://www.newscientist.com/article/22 ... han-a-car/

d) The ScriptBasic anagram finder, using the insane British dictionary on my x86 PC is still running after 24 hours!

[ejolson]

d) The ScriptBasic anagram finder, using the insane British dictionary on my x86 PC is still running after 24 hours!

If that is the same code as posted here, then it does not include the heap data structure and is consequently an O(n^2) algorithm. Note that ScriptBasic reportedly processed n=10000 words in 1 minute 35 seconds. Since the insane British dictionary is about 60 times larger, then it should theoretically take about 60^2 times longer to process. Assuming your computer is similar in speed, that comes to about 3.75 days. Unless you run out of electricity first, I would suggest waiting at least 5 days before concluding something is wrong.

It will be interesting to see how long it really runs.

[Heater]

OK. Bet's are on.

Still humming along at full throttle, 100% usage of one of my precious cores. Only 2% memory down.

Hope Win 10 does not jump in an reboot itself after an update...

[John_Spikowski]

Another array abuse challenge.

[Heater]

John_Spikowski,

Another array abuse challenge.

What an absurd statement. I don't know if I should laugh or cry.

How is it "abuse" to use arrays like, well, arrays. As we have been doing in computer programs since ever there were such things?

Of course if you mean to say that particular code does not make use of ScriptBasic in an optimal way I could understand better. If so we look forward to your seeing improved solution.