Liberation through Computer Literacy

[Heater]

It's odd. I put a screen and keyboard on the rusty Pi and it booted and ran just fine. It spent a couple of hours trying it's best to cause global warming by compiling the project for debug, for release and again for the cargo bench. Which all worked but I noticed I was getting low voltage warnings occasionally. Then running the actual benchmark crashed out and I gave up with that.

With the screen back on my PC I find I can reach the Pi over ssh but it never responds after entering the password.

BUT, I can log into it over ssh from another PC running Debian natively. Grrr...

Oh wait....now I find I can't log into that Debian machine from Win 10 anymore either. Is Win 10 playing silly buggers with me. Time for a reboot...

Sure enough, now ssh works again, bloody Windows. Grrrr...

[davidcoton]

Deepest Mandelbrot Set Zoom Animation ever - a New Record! 10^275 (2.1E275 or 2^915)

That's a fun video; however, after the Fibonacci sequence, I'm not sure I could bear another big-number arithmetic challenge.

What do you think about something fun like a graphical network version of the classic star trader game?

How about a challenge to honour the work of Fido and Kira?

We all know what the command "cat" does; so create a command "dog". It can do anything you like, but it must be as useful as "cat". Write it in any language or script. Marks for usefulness, elegance, and efficiency. Judging solely by Fido and Kira. No zombies allowed.

[Heater]

A doggerel generator?

[ejolson]

A doggerel generator?

Fido's tail has been wagging in excitement at the idea of a doggerel generator. After the usual

Code: Select all

$ sudo ln cat dog
$ sudo rm cat

solution, the dog developer has been working all day on an option that converts standard input to verse before writing to standard output. When I asked how it worked, I was told

• Every paragraph is broken into lines of 5 to 10 words.
• In cases where the last word ends with punctuation, lines of 4 to 11 words are allowed.
• The lines which rhyme are determined using cyclotomic doggynomials over a prime field, user selectable.
• At least one of the rhyming words in each couplet must be a synonym selected from the dict-moby-thesaurus for the corresponding input word.
• The quality of a rhyme is scored as follows:
  • Translate both words to the international phonetic alphabet using the open-source eSpeak speech synthesis project.
  • Count how many trailing vowel phonemes match.
  • If both words end in punctuation, give that the weight of an additional phoneme match.
• All possible synonyms and line breaks are considered.
• The output line length and synonyms are chosen to maximise the rhyme.

Although paradise was lost long ago, there is nothing that can't be made worse by a dogital apocalypse. Therefore, I tried Fido's program on the freely available text of Paradise Lost. However, the only output was "core dumped."

As poetic as that sounds, the output wasn't correct according to the doggerel algorithm described above. When I pointed that out, the canine coder growled, it doesn't matter. My program wins anyway, because "sudo rm cat" has left me as the only judge.

Is it possible Fido used the Rust benchmarking harness for the doggerel generator?

I wonder where that insane Haskell anagram program has got to.

[davidcoton]

Code: Select all

$ sudo rm cat

Alas, poor Kira, I knew her not.

At least one of the rhyming words in each couplet must be a synonym selected from the dict-moby-thesaurus for the corresponding input word.

May I suggest a dict-moggie-thesaurus?

Please remind Fido that, even if cat cannot be retrieved from a backup, the judges' role involves implementing the rules. It would be very unsatisfying for one of the judges to win the challenge with an entry scoring null points.

[Paeryn]

Code: Select all

$ sudo rm cat

Alas, poor Kira, I knew her not.
...
Please remind Fido that, even if cat cannot be retrieved from a backup, the judges' role involves implementing the rules. It would be very unsatisfying for one of the judges to win the challenge with an entry scoring null points.

Thankfully cats are well backed up - they do have 9 lives! Oh, and just to confuse people, Kira is male. Don't ask, he already had that name before he decided to move in with me.

I wonder where that insane Haskell anagram program has got to.

I've scrapped my first attempt and I'm partway through trying a different approach but another of my feline gang is demanding some play time.

[John_Spikowski]

I hope new challenge suggestions haven't ended.

[ejolson]

I hope new challenge suggestions haven't ended.

How is the anagram finder using the hash extension for Script Basic?

Is there a memory leak?

What's not working?

[John_Spikowski]

The HASH extension module doesn't seem to detect the end of the hash and seg faults calling next hash. It may be as simple as I don't know what I'm doing but I'm really busy with real life to investigate. I've ask AIR to have a peek but he seems busy as well.

Feel free to give it a try. Maybe you will have better luck. It seems a lot faster.

[John_Spikowski]

This doesn't seg fault so I'm getting closer. The issue seems to be what I'm doing with updating the hash value.

FYI: This HASH library is used internally by ScriptBasic's lexer.

ScriptBasic HASH Extension Module Docs

Code: Select all

INCLUDE hash.bas

hh = HASH::New()

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

FOR lstidx = 0 TO UBOUND(wordlist)
  SPLITA wordlist[lstidx] BY "" TO wordarray
  FOR wrdidx = 0 TO UBOUND(wordarray)
    IF wordarray[wrdidx] < "a" OR wordarray[wrdidx] > "z" THEN GOTO NextWord
  NEXT
  SPLITA wordlist[lstidx] BY "" TO thisword

  FOR i = 0 TO UBOUND(thisword)
    FOR j = i + 1 TO UBOUND(thisword)
      IF thisword[i] > thisword[j] THEN
        temp = thisword[i]
        thisword[i] = thisword[j]
        thisword[j] = temp
      END IF
    NEXT
  NEXT
  FOR x = 0 TO UBOUND(thisword)
    sortword &= thisword[x]
  NEXT
' IF HASH::Exists(hh, sortword) = FALSE THEN
' IF anagram{sortword} = undef THEN
'   anagram{sortword} = wordlist[lstidx] & ":"
'   HASH::SetValue hh, sortword, wordlist[lstidx] & ":"
' ELSE
'   anagram{sortword} &= " " & wordlist[lstidx] & ","
'   strdta = HASH::Value(hh, sortword)
'   HASH::SetValue(hh, sortword, strdta & " " & wordlist[lstidx] & ",")
' END IF
HASH::SetValue(hh, sortword, wordlist[lstidx])
  sortword = ""
NextWord:
NEXT

HASH::Start hh
WHILE HASH::Exists(hh)
'   IF RIGHT(thisana, 1) = "," THEN
'   PRINT LEFT(thisana, LEN(thisana) - 1), "\n"
'   PRINT HASH::ThisValue(hh),"\n"
'   END IF
  PRINT HASH::ThisKey(hh)," - ",HASH::ThisValue(hh), "\n"
  HASH::Next(hh)

WEND
HASH::Release hh

[ejolson]

This doesn't seg fault so I'm getting closer. The issue seems to be what I'm doing with updating the hash value.

FYI: This HASH library is used internally by ScriptBasic's lexer.

ScriptBasic HASH Extension Module Docs

Code: Select all

INCLUDE hash.bas

hh = HASH::New()

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

FOR lstidx = 0 TO UBOUND(wordlist)
  SPLITA wordlist[lstidx] BY "" TO wordarray
  FOR wrdidx = 0 TO UBOUND(wordarray)
    IF wordarray[wrdidx] < "a" OR wordarray[wrdidx] > "z" THEN GOTO NextWord
  NEXT
  SPLITA wordlist[lstidx] BY "" TO thisword

  FOR i = 0 TO UBOUND(thisword)
    FOR j = i + 1 TO UBOUND(thisword)
      IF thisword[i] > thisword[j] THEN
        temp = thisword[i]
        thisword[i] = thisword[j]
        thisword[j] = temp
      END IF
    NEXT
  NEXT
  FOR x = 0 TO UBOUND(thisword)
    sortword &= thisword[x]
  NEXT
' IF HASH::Exists(hh, sortword) = FALSE THEN
' IF anagram{sortword} = undef THEN
'   anagram{sortword} = wordlist[lstidx] & ":"
'   HASH::SetValue hh, sortword, wordlist[lstidx] & ":"
' ELSE
'   anagram{sortword} &= " " & wordlist[lstidx] & ","
'   strdta = HASH::Value(hh, sortword)
'   HASH::SetValue(hh, sortword, strdta & " " & wordlist[lstidx] & ",")
' END IF
HASH::SetValue(hh, sortword, wordlist[lstidx])
  sortword = ""
NextWord:
NEXT

HASH::Start hh
WHILE HASH::Exists(hh)
'   IF RIGHT(thisana, 1) = "," THEN
'   PRINT LEFT(thisana, LEN(thisana) - 1), "\n"
'   PRINT HASH::ThisValue(hh),"\n"
'   END IF
  PRINT HASH::ThisKey(hh)," - ",HASH::ThisValue(hh), "\n"
  HASH::Next(hh)

WEND
HASH::Release hh

The documentation says "import hash.bas" but you have written "include hash.bas" instead. Would that make any difference?

[John_Spikowski]

IMPORT only INCLUDEs the file once. Other than that, they are the same.

What needs to be done is create a control word list with 10 or so entries and step through the routines validating what's happenong.

Thinking about this a bit, the SPLITA may have created a null element at the end and that is what one of the HASH functions is choking on.

I hope to have some time next week to have another look at this. I don't think the HASH extension module has an issue and it's just me.

Free copy of ScriptBasic to the first person to resolve it.

I'll check this thread to see if anyone has a question about ScriptBasic or the HASH extension module.

[Heater]

The Digital Apocalypse is nigh!

I've just spent some days, non-stop, reimplementing one of our "micro-services" in Rust. Formerly in C#. Which was not just slow but a tangled mess of inter dependent classes/objects with no discernible rhyme or reason as to why any particular functionality was put into any particular class. Clearly written by someone who had never heard the phrase "separation of concerns".

There is just time for a break before the digital apocalypse so it's either beer or...

Did I miss a new challenge this last week.... ?

[Paeryn]

Sorry for taking so long getting the Haskell version of the anagrams done, I've not been too well and got fed up trying to write an efficient version so I've done it by sorting the letters of each word and using that directly to sort the list of words and group identical entries.

I've not run it on my RPi, well I did try, but it hits the swap hard (it uses nearly 2GB of memory) so I've only run it on my PC - I suggest only running it on a 4GB RPi4 (the best I've got is an RPi3 currently).

Code: Select all

paeryn@hobbiton:~/Programming/banagrams$ cat haskell_anagrams.hs
import qualified Data.List
import qualified Data.ByteString.Char8 as Char8
import Data.Char (isLower)
import Data.Function (on)

printRest :: [Char8.ByteString] -> IO ()
printRest [x] = Char8.putStrLn x
printRest (x:xs) = do
  Char8.putStr x
  putStr ", "
  printRest xs

printAnagram :: [Char8.ByteString] -> IO ()
printAnagram (x:xs) = do
  Char8.putStr x
  putStr ": "
  printRest xs


main :: IO ()
main = do
  f <- Char8.readFile "/usr/share/dict/british-english-insane"
  let hashWords = (Char8.sort >>= (,)) <$> (filter (Char8.all isLower) (Char8.lines f))
  let sortedHashWords = Data.List.sortOn fst hashWords
  let groupedWords = Data.List.groupBy (on (==) fst) sortedHashWords
  let nonUniqueWords = filter ((> 1) . length) groupedWords
  let hashlessWords = map (map snd) nonUniqueWords
  let sortedWords = Data.List.sort hashlessWords
  mapM_ printAnagram sortedWords

-- As above, but with the whole anagram generator condensed into one
-- long line (although split up over several for readability).
--
--main = do
--  f <- Char8.readFile "/usr/share/dict/british-english-insane"
--  mapM_ printAnagram $ Data.List.sort 
--          [wl | ws <- (Data.List.groupBy (on (==) fst) $
--                       Data.List.sortOn fst $
--                       (Char8.sort >>= (,)) <$> (filter (Char8.all isLower) $
--                                              Char8.lines f)),
--                length ws > 1,
--                let wl = map snd ws]

The commented main does the same thing but without variables to hold each list. The only difference is that it uses list comprehension to filter out words with no anagrams at the same time as discarding the hash string (filter followed by map (map snd) in the long version).

Code: Select all

paeryn@hobbiton:~/Programming/banagrams$ ghc haskell_anagrams.hs -O2 -rtsopts
[1 of 1] Compiling Main             ( haskell_anagrams.hs, haskell_anagrams.o )
Linking haskell_anagrams ...
paeryn@hobbiton:~/Programming/banagrams$ time ./haskell_anagrams +RTS -s >insane-h
   1,944,451,792 bytes allocated in the heap
     559,384,504 bytes copied during GC
     543,598,344 bytes maximum residency (10 sample(s))
     852,710,104 bytes maximum slop
            1997 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      5343 colls,     0 par    1.183s   1.183s     0.0002s    0.0029s
  Gen  1        10 colls,     0 par    0.387s   0.388s     0.0388s    0.1322s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    2.351s  (  2.353s elapsed)
  GC      time    1.570s  (  1.571s elapsed)
  EXIT    time    0.082s  (  0.082s elapsed)
  Total   time    4.004s  (  4.006s elapsed)

  %GC     time      39.2%  (39.2% elapsed)

  Alloc rate    827,127,227 bytes per MUT second

  Productivity  60.8% of total user, 60.8% of total elapsed


real	0m4.074s
user	0m3.424s
sys	0m0.648s
paeryn@hobbiton:~/Programming/banagrams$ !md
md5sum insane-?
eda1c97aacecc83b23ac568bde0cd384  insane-h
eda1c97aacecc83b23ac568bde0cd384  insane-q

insane-h is the output of the Haskell version,
insane-q is the output of Kira's C version.

[ejolson]

I've not run it on my RPi, well I did try, but it hits the swap hard (it uses nearly 2GB of memory) so I've only run it on my PC - I suggest only running it on a 4GB RPi4 (the best I've got is an RPi3 currently).

I hadn't anticipated running up against memory limitations so quickly with the 2GB Pi 4B that I bought earlier this month.

Along different lines I've just downloaded the 64-bit Gentoo image from

https://github.com/sakaki-/gentoo-on-rpi-64bit

for the Pi 4, but Fido won't log in using the demouser account. The canine coder said with a growl, de-mouser is just a clever way of saying cat and I'm not logging in as a cat. Consequently, there have been some delays with the 64-bit testing.

As the phase of the moon has changed, so the title of this thread. Just in time, too, because the zombies had just noticed someone ran over most of the wild pea plants in my yard with a lawn mower.

[Heater]

How on Earth can juggling 650,000 words, only 6.6M bytes, manage to consume 2 giga bytes?!

[Paeryn]

How on Earth can juggling 650,000 words, only 6.6M bytes, manage to consume 2 giga bytes?!

The sort function is a merge sort, it generates a huge number of temporary lists. Sorting lists is expensive when you have such long lists.

[Heater]

Hmm.. I see...

But, but, the input data is already sorted, it's a dictionary after all, so there is no need to do any sorting to get the anagrams out (except for sorting letters in words perhaps).

[Paeryn]

Hmm.. I see...

But, but, the input data is already sorted, it's a dictionary after all, so there is no need to do any sorting to get the anagrams out (except for sorting letters in words perhaps).

To group entries together it needs the lists sorted by the ordered letters, this list is no longer in alphabetical order of the words e.g. coat (acot) will be before and (adn).
So the whole list needs sorting by ordered letters to group them together, then the list of groups need to be sorted to put them back into alphabetical order of the first word in each group. Within each group of words (the anagrams) the words stay in alphabetical order so don't need sorting.

[Heater]

Paeryn,

I have no idea what you are up to there but I have to dispute your use of the word "need".

1) The input is sorted, so if we scan the input words no sorting is needed.

2) For every new word create hash (by sorting the letters or whatever) then:

a) If there is no anagram list existing for that hash then create one. It will contain one entry, the new word.

b) If there is an anagram list existing for that hash then append the new word to it. No sorting needed as only "lesser" words can be in the anagram list so far.

c) If this is a new anagram list append it to some output list. A list of anagram lists. No sorting needed there as we have created the anagram lists in order as we proceed.

3) Repeat from 2) until no more words.

4) For output scan the list of anagram lists and output the words each one contains. No sorting needed as we created the whole thing in order.

Now, this is straightforward if your anagram detection depends on sorting the letters of words. In my solution I used the prime hash function which is essentially random and blows the ordering. So I keep an index of hashes as they get created so that I can output anagram lists in order at the end.

[Paeryn]

The "need" is down to how it's implemented, it just uses sorted lists, it doesn't search for matching hashes rather it relies on sorting them all which puts all matching hashes next to each other. Using a proper tree to store and search the list of anagrams would be better (like Kira did in C) but I was making mistakes, my Haskell being a bit rusty and me not able to concentrate properly, so I did it with simple list sorting.

Lists are immutable so changing an element means creating a brand new new list (which is why the sort uses up so much memory), when I feel up to it I'll look into how to use mutable arrays and re-write it to use a tree/hashmap.

Example, dictionary containing 4 words: ask, bad, bed & dab

• Words are read into a list as a tuple containing the sorted letters and the word.
  [("aks", "ask"), ("abd", "bad"), ("bde","bed"), ("abd", "dab")]
• This list is sorted on the first item so that anagrams are next to each other
  [("abd", "bad"), ("abd", "dab"), ("aks", "ask"), ("bde", "bed")]
• This list is used to make a list of lists where each list is the list of consecutive tuples with matching first elements
  [[("abd", "bad"), ("abd", "dab")], [("aks", "ask")], [("bde", "bed")]
• The first elements of the tuples can now be thrown away and we have a list where each element is a list of words that are anagrams (here I'll keep the anagrams with only one word, the code throws those away)
  [["bad", "dab"], ["ask"], ["bed"]]
• As you can see, ask isn't first since the sorting was done on the ordered letters so we need to sort this outer list based on the first word of the inner list.

[John_Spikowski]

The word list is already sorted. If you use a hash method properly the only sorting going on is the dictionary word to build the hash key.

I think the ScriptBasic approach is the most efficient but using associative arrays rather than the hash extension module is its downfall.

[hippy]

"A Second Age of Personal Computing"
"A Final Fibonacci Challenge"
"Project Digital Apocalypse Not Now"
"Liberation through Computer Literacy"

Can I suggest the next change of thread title is to "Best Troll. Ever"

[scruss]

Lor' lummy, are youse all still at this? Perl is Fast Enough for me, so I've not given it much more thought, except for:

• it may be quicker to find anagrams of words all the same length, since by definition two words can only be anagrams of each other if they're the same length. Reading and classifying strings by length is a bit slow under the Unix paradigm as we don't have fixed-length records baked into the filesystem. Either way, you only have to hash far fewer words against one another even if you still need a master array for the final output order.
• each of those comparisons of words of the same length might work quite well as separate threads.

Here's how that insane word list stacks up by word length:

Code: Select all

Length	Count	% of total
1	26	0%
2	240	0%
3	1910	0%
4	7349	2%
5	17257	4%
6	32498	8%
7	46596	11%
8	57535	13%
9	59453	14%
10	54659	13%
11	45499	11%
12	35410	8%
13	25569	6%
14	17592	4%
15	11264	3%
16	6855	2%
17	3939	1%
	… (longer words aren't significant as there are so few)

[ejolson]

I have no idea what you are up to there but I have to dispute your use of the word "need".

Make the keys, sort the keys and then identify the anagrams is the technique used by managram.c and zanagram.c, neither of which use undue amounts of memory or time when running.

A merge sort generally uses twice the memory needed to hold the items being sorted. That's the main reason why quick sort is so popular. On the other hand, the work-span analysis of merge sort is much more favourable from a parallel algorithms point of view. That's why the zombies used a parallel merge sort while my original anagram finder simply leveraged qsort from the standard library.

In the case when merge sort allocates new memory to store another copy of the list being sorted at each level of the recursion, the memory use should scale with log(n) where n is the number of items being sorted. That seems to put the Haskell program into 4GB Pi 4 territory.

One of the standard complaints about Haskell and functional programming is that it is much more difficult to reason about how much memory will be used. Do you think some sort of eager processing of the lists would reduce the memory use?