User avatar
bensimmo
Posts: 4157
Joined: Sun Dec 28, 2014 3:02 pm
Location: East Yorkshire

Re: Project Digital Apocalypse Not Now

Tue Jul 16, 2019 9:42 am

I have no idea what popular fictional characters those might be. Perhaps we can find something.
You mean, like if the teletubbies was still popular?

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: Project Digital Apocalypse Not Now

Tue Jul 16, 2019 10:28 am

BINGO!

Teletubies, all grown up and gigantically huge and slow.

Meanwhile Zebedee is still bouncing around and helping people out when they have a difficult problem.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: Project Digital Apocalypse Not Now

Tue Jul 16, 2019 6:05 pm

bensimmo wrote:
Tue Jul 16, 2019 9:42 am
I have no idea what popular fictional characters those might be. Perhaps we can find something.
You mean, like if the teletubbies was still popular?
I'm looking forward to the new picture. I suspect it will be even more popular than the first.

To think, it's all because of the digital apocalypse which started that fateful year in 1976.

timrowledge
Posts: 1275
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: A Final Fibonacci Challenge

Fri Jul 19, 2019 5:12 am

gkreidl wrote:
Wed Jun 26, 2019 6:09 pm
Taking out the check for 0 is a good idea. My Python function now looks like this:
{snip}
Nice! That gets the calculation time for Squeak on my Pi3b+ to ~4.5sec. A clear and simple improvement from the ~6secs of the prior version.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: Project Digital Apocalypse Not Now

Fri Jul 19, 2019 5:33 am

timrowledge,

What, do you have a new improved version of your fibo 4784969 solution?

If so I should check it out and up date the Fibo Challenge repository.

I don't follow your mentioning speeds of 4 to 6 seconds on a Pi3b+. When I ran your fibo.cs on an Intel PC it took half a minute.

Or are you talking about some other calculation there?

timrowledge
Posts: 1275
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: Project Digital Apocalypse Not Now

Sat Jul 20, 2019 3:40 pm

I just took advantage of the nice tweak gkriedel spotted and was pleased to see that it improved the calculation time for the big fib from circa 6secs to circa 4.8. Printing time, obviously, wasn’t changed.
Your 30 second experience was not when using Squeak on an intel machine unless it is a 486 era model. My8 year old i7 iMac does the calculation in less than half a second. Are you perhaps remembering bad experiences with GST?
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: Project Digital Apocalypse Not Now

Sat Jul 20, 2019 3:51 pm

timrowledge wrote:
Sat Jul 20, 2019 3:40 pm
I just took advantage of the nice tweak gkriedel spotted and was pleased to see that it improved the calculation time for the big fib from circa 6secs to circa 4.8. Printing time, obviously, wasn’t changed.
Your 30 second experience was not when using Squeak on an intel machine unless it is a 486 era model. My8 year old i7 iMac does the calculation in less than half a second. Are you perhaps remembering bad experiences with GST?
The times that have been reported here generally include writing the output to a file. Otherwise the trade-off in doing the calculation more slowly in base 10 to obtain an O(N) print routine that avoids the base conversion doesn't make sense.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: Project Digital Apocalypse Not Now

Sat Jul 20, 2019 4:30 pm

timrowledge,
Your 30 second experience was not when using Squeak on an intel machine unless it is a 486 era model. My8 year old i7 iMac does the calculation in less than half a second. Are you perhaps remembering bad experiences with GST?
It certainly was.

Sadly I no longer have my 486 era machine. Which was a sweet 100MHz AMD K6.

Nope, my "30 second experience" was on an Intel(R) Core(TM) i5-3610ME CPU @ 2.70GHz.

Code: Select all

$ time ./bin/squeak -vm-display-null -headless -nosound shared/Squeak5.2-18229-64bit.image  /home/heater/Squeak5.2-18229-64bit-201810190412-Linux/fibo.cs 2>/dev/null | head -c 32
10727395641800477229364813596225
real    0m31.213s
user    0m31.168s
sys     0m0.132s
$ time ./bin/squeak -vm-display-null -headless -nosound shared/Squeak5.2-18229-64bit.image  /home/heater/Squeak5.2-18229-64bit-201810190412-Linux/fibo.cs 2>/dev/null | tail -c 32
4856539211500699706378405156269

real    0m31.279s
user    0m31.208s
sys     0m0.140s
$
As ejolson notes above, actually producing the decimal output is required to satisfy the challenge. It's kind of pointless otherwise, is it not?

It is interesting that some languages with support for big integer calculation have turned in quite reasonable results for their actual calculation time but fallen down so badly when it comes to actually printing the result. Smalltalk is in good company there with Python and Javascript there.
Are you perhaps remembering bad experiences with GST?
Gack, don't remind me of that nightmare.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: Project Digital Apocalypse Not Now

Sat Jul 20, 2019 6:20 pm

Heater wrote:
Sat Jul 20, 2019 4:30 pm
It is interesting that some languages with support for big integer calculation have turned in quite reasonable results for their actual calculation time but fallen down so badly when it comes to actually printing the result.
I suspect the software engineers designing those big number libraries were thinking rather specifically about providing just enough functionality for a textbook implementation of RSA public-key encryption. While that algorithm is running, there is never a need to print out any numbers in base 10 and keys are almost always stored using some sort of base-64 encoding. From a teaching point of view, deriving the doubling formulas necessary to quickly compute large Fibonacci numbers may be a better starting point than trying to understand the dual-base number systems used in the RSA algorithm.

Speaking of encryption, I recently installed WireGuard and found it much easier to use than either IPsec or ssh tunnels. It consists of a kernel module that provides a virtual network device, for example wg0, that participates in a VPN defined using public key pairs. I wonder how easy it would be to network boot a Raspberry Pi over WireGuard?

Unfortunately, unlike the Fibonacci sequence, encryption is not an effective way to prevent the digital apocalypse. Fortunately, those who wish to avoid arithmetic involving rather large numbers but are not similarly scared of anagrams now have something to do.

There has been an separate discussion focusing on whether the C programming language is suitable as a first programming language in this thread. As in the present thread, that discussion has been informed by actual working code in C, Perl, Python, bash and 8th to find all anagrams in the insane British dictionary. Since no example code was given in Basic, I've been wondering whether the onset of the digital apocalypse might be related to bananagrams and the inability of Basic to help with them.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 1:02 am

ejolson,
I suspect the software engineers designing those big number libraries were thinking rather specifically about providing just enough functionality for a textbook implementation of RSA public-key encryption. While that algorithm is running, there is never a need to print out any numbers...
I have been wondering about this...

Given the ridiculously slowness of these languages to actually produce big integer results one wonders why they even bothered adding the feature to the languages. Python, Javascript, Smalltalk for example. I can offer a couple of suggestions...

1) It's cool that ones calculations won't overflow some arbitrary limit imposed by the machines word size that you have forgotten to cater for at some point. A common source of bugs that need not be bugs in languages like C that are happy to produce wrong results and continue for you rather than point out your mistake.

2) I guess that when people do actually want to work with absurdly huge integers often it is not actually required to produce a human readable result, as in your encryption example, so no one worried about the speed of printing results.

But still, things like GMP show that producing the big integer outputs speedily is possible, so why don't these language use those algorithms?

Speaking of Wireguard, I was was recently thinking about checking that out for use in a project. I'd love to hear what your experiences are with it. Perhaps in thread dedicated to it.

I don't see such a secure network boot system making it into the bootloader soon.

jalih
Posts: 76
Joined: Mon Apr 15, 2019 3:54 pm

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 6:58 am

Heater wrote:
Sun Jul 21, 2019 1:02 am
ejolson,
Given the ridiculously slowness of these languages to actually produce big integer results one wonders why they even bothered adding the feature to the languages. Python, Javascript, Smalltalk for example. I can offer a couple of suggestions...

1) It's cool that ones calculations won't overflow some arbitrary limit imposed by the machines word size that you have forgotten to cater for at some point. A common source of bugs that need not be bugs in languages like C that are happy to produce wrong results and continue for you rather than point out your mistake.

2) I guess that when people do actually want to work with absurdly huge integers often it is not actually required to produce a human readable result, as in your encryption example, so no one worried about the speed of printing results.

But still, things like GMP show that producing the big integer outputs speedily is possible, so why don't these language use those algorithms?
I think big numbers should be properly integrated into programming language.

With 8th I can print the stack contents and it properly shows:

Code: Select all

1    n: 0000000002ddf7e0 1  F 21438616965787467196949606254029645878617458393600018361005357582097219031844287...
8th Converts fibo(47849699) result bfloat to 9999996 digit result 'int' string and outputs into file in just 3984 msecs.

If you include fibo(47849699) calculation time, the result is: 12572 msec

User avatar
Zebedeee
Posts: 5
Joined: Tue Jul 16, 2019 12:19 pm

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 11:43 am

Heater wrote:
Tue Jul 16, 2019 10:28 am
Meanwhile Zebedee is still bouncing around and helping people out when they have a difficult problem.
Who, me?
Boing. Boing.
Time for bed.

(Sorry this reply is late. Blame the mods, but not too much.)

User avatar
scruss
Posts: 2419
Joined: Sat Jun 09, 2012 12:25 pm
Location: Toronto, ON
Contact: Website

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 4:35 pm

ejolson wrote:
Sat Jul 20, 2019 6:20 pm

Since no example code was given in Basic, I've been wondering whether the onset of the digital apocalypse might be related to bananagrams and the inability of Basic to help with them.
If only the BASIC interpreters I use (and want to keep using) had hash tables, this would be right easy. But they don't, so it's not.
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.

User avatar
John Spikowski
Posts: 41
Joined: Sat Jul 20, 2019 5:34 pm
Location: Anacortes, WA USA
Contact: Website

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 5:06 pm

ScriptBasic has a hash extension module but I use associative arrays for the same purpose.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 6:57 pm

John Spikowski wrote:
Sun Jul 21, 2019 5:06 pm
ScriptBasic has a hash extension module but I use associative arrays for the same purpose.
Associative arrays make Script Basic a natural choice for the

Insane British Anagram Challenge.

This challenge is based on the problem originally proposed here.

From my point of view, the anagram challenge is for anyone interested in avoiding the Fibonacci challenge as well as avoiding the digital apocalypse through an increased ability to read and write computer programs. As the present thread is under the "General programming chat and advice for beginners" topic, beginners are especially encouraged to enter as well as the usual crowd and all other forum members.

Specifically, the challenge is
  • Install the insane British dictionary on your Pi using

    Code: Select all

    $ sudo apt-get install wbritish-insane
    
  • Choose any suitable or possibly unsuitable programming language.
  • Write a program that
    • Selects only the words consisting of all lower-case characters from the file
      /usr/share/dict/british-english-insane.
    • Outputs those words which are anagrams of each other in the format

    Code: Select all

    aah: aha
    aahed: ahead
    aahs: ahas
    aal: ala, laa
    aaliis: sialia
    aals: alas, laas, lasa, sala
    ...
    zinco: zonic
    zolotink: zolotnik
    zoography: zoogrpahy
    
    • Note that each word is printed only once. The lines are in alphabetical order and the anagrams on each line are listed in alphabetical order. Note also that zoogrpahy is actually in the dictionary, otherwise it wouldn't be insane.
  • Time how long it takes your program to run on a Raspberry Pi using the command

    Code: Select all

    # sudo echo performance >/sys/devices/system/cpu/cpufreq/policy0/scaling_governor
    $ time ./myprogram >myoutput.insane
    $ time ./myprogram >myoutput.insane
    $ time ./myprogram >myoutput.insane
    # sudo echo ondemand >/sys/devices/system/cpu/cpufreq/policy0/scaling_governor
    
  • Compare your output to the output given by the original Perl implementation.
  • After everything matches report the best total time, the md5sum of the output and what model of Pi.
  • Further post code, tell jokes and ask for help if necessary.
For reference the Perl code is

Code: Select all

#!/usr/bin/env perl
# selfgrams.pl - find words that have valid anagrams
# scruss - 2019-07 - may need wcanadian/wbritish/wamerican package
# modified to use the insane British dictionary by ejolson
use v5.20;
my (@words, %grams, @elem, %output, $key, $fh);

# create source word list from system file
open( $fh, '<', '/usr/share/dict/british-english-insane' ) or die "$!\n";
chomp( @words = grep { /^[a-z]+$/ } <$fh> );
close($fh);

# process source word list into hash of anagrams
foreach (@words) {
    # sort word's letters to generate key - eg: 'maps' => 'amps'
    $key = join( '', sort( split( '', $_ ) ) );
    # append word to existing hash match or create if word is new
    @elem =
        ( exists( $grams{$key} ) )
      ? ( @{ $grams{$key} }, $_ )
      : ($_);
    $grams{$key} = [@elem];
}

# generate output hash of anagrams where key matched > 1 word
foreach ( grep { scalar( @{$_} ) > 1 } values(%grams) ) {
    @elem = @{ $_ };
    $key = shift(@elem);
    $output{$key} = join( ', ', @elem );
}

foreach ( sort( keys(%output) ) ) {
    say join( ': ', $_, $output{$_} );
}
exit;
Last edited by ejolson on Mon Jul 22, 2019 5:30 pm, edited 3 times in total.

User avatar
scruss
Posts: 2419
Joined: Sat Jun 09, 2012 12:25 pm
Location: Toronto, ON
Contact: Website

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 7:32 pm

while I'm touched that this has been taken up as a challenge, installing wbritish-insane is considered harmful. It's chock full of typos, so if you use it as your system spelling dictionary, expect troulbe
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 7:33 pm

scruss wrote:
Sun Jul 21, 2019 4:35 pm
ejolson wrote:
Sat Jul 20, 2019 6:20 pm

Since no example code was given in Basic, I've been wondering whether the onset of the digital apocalypse might be related to bananagrams and the inability of Basic to help with them.
If only the BASIC interpreters I use (and want to keep using) had hash tables, this would be right easy. But they don't, so it's not.
I'm presently working on a version in classic line-numbered Basic that organizes all the anagrams into a heap data structure.
Last edited by ejolson on Sun Jul 21, 2019 7:39 pm, edited 1 time in total.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: Project Digital Apocalypse Not Now

Sun Jul 21, 2019 7:38 pm

scruss wrote:
Sun Jul 21, 2019 7:32 pm
while I'm touched that this has been taken up as a challenge, installing wbritish-insane is considered harmful. It's chock full of typos, so if you use it as your system spelling dictionary, expect troulbe
Note that

Code: Select all

$ grep troulbe british-english-insane
shows your troulbe came from someplace else.

From what I understand, as long as you don't also install ibritish-insane there is no danger. It would also be sane to check the default dictionary links in /etc/dictionaries-common to make sure none of them point to anything with insane in the filename.

They've apparently removed zoogrpahy from the dictionary. I wonder if that update made it into the Buster version of Raspbian.

jalih
Posts: 76
Joined: Mon Apr 15, 2019 3:54 pm

Re: Project Digital Apocalypse Not Now

Mon Jul 22, 2019 10:05 am

ejolson wrote:
Sun Jul 21, 2019 7:33 pm
I'm presently working on a version in classic line-numbered Basic that organizes all the anagrams into a heap data structure.
I got a version of s:sort word used to sort keys in my 8th program that uses heap from Ron Aaron (8th developer).

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: Project Digital Apocalypse Not Now

Mon Jul 22, 2019 10:07 am

ejolson,

As this seems to be a challenge for anyone who is both British and insane of course I had to step up to the plate. For King and Country and all that. Tally-ho.

Damn you, ejolson, you have just laid waste my entire morning :)

Anyway here is my solution in Javascript:

Code: Select all

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

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

const dictionary = readline.createInterface({
    input: fs.createReadStream('/usr/share/dict/british-english-insane'),
})

dictionary.on('line', function(word) {
    if (allLowerCasePattern.test(word)) {
        let key = word.split('').sort().join('')
        if (anagramSets[key]) {
            anagramSets[key].push(word)
        } else {
            anagramSets[key] = []
            anagramSets[key].push(word)
        }
    }
})

dictionary.on('close', function(line) {
    for (let [key, value] of Object.entries(anagramSets)) {
        if (value.length > 1) {
            process.stdout.write(value[0] + ': ' + value[1])
            for (let i = 2; i < value.length; i++) {
                process.stdout.write(', ' + value[i])
            }
            process.stdout.write('\n')
        }
    }
})
No timings on a Pi yet but this is how it compares to the perl solution on my Debian PC:

Code: Select all

$ time node ./selfgrams.js > selfgrams_js.txt

real    0m3.816s
user    0m3.031s
sys     0m1.984s
[email protected]:/mnt/c/Users/michael/conveqs$ time ./selfgrams.pl > selfgrams_pl.txt

real    0m2.531s
user    0m2.078s
sys     0m0.453s
Hmm... 50% slower.

But not so slow that I feel I might have to learn the insanity of a language that is perl thank God.

Technically there is an undefined behavior in that JS. Can anyone spot it?

"zoogrpahy" is still in Buster.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: Project Digital Apocalypse Not Now

Mon Jul 22, 2019 12:51 pm

After a little tweeking JS can handily match Perl at this:

Code: Select all

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

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

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 = word.split('').sort().join('')
        if (anagramSets[key]) {
            anagramSets[key].push(word)
        } else {
            anagramSets[key] = [word]
        }
    }
}

let output = ""
for (let [key, value] of Object.entries(anagramSets)) {
    if (value.length > 1) {
        output += value[0] + ': ' + value[1]
        for (let i = 2; i < value.length; i++) {
            output += ', ' + value[i]
        }
        output += '\n'
    }
}
process.stdout.write(output)

Code: Select all

$ time node selfgrams.js > selfgrams_js.txt

real    0m2.470s
user    0m2.063s
sys     0m0.781s

$ time ./selfgrams.pl > selfgrams_pl.txt

real    0m2.531s
user    0m2.078s
sys     0m0.453s

User avatar
scruss
Posts: 2419
Joined: Sat Jun 09, 2012 12:25 pm
Location: Toronto, ON
Contact: Website

Re: Project Digital Apocalypse Not Now

Mon Jul 22, 2019 3:09 pm

ejolson wrote:
Sun Jul 21, 2019 6:57 pm
… After everything matches report the best total time, the md5sum of the output and what model of Pi.
I believe that the young 'uns do call this “refactoring”

Time: 43.077s (original Perl was 54.713s, so 21% faster)

md5sum: bec74aa3b31577edbb291aeb7269a4d5 (same)

Raspberry Pi Zero, Perl 5 again:

Code: Select all

#!/usr/bin/perl -l
# selfgrams4.pl - find words that have valid anagrams
# scruss - 2019-07
my ( %grams, $key, $fh, @out, $k );

open( $fh, '<', '/usr/share/dict/british-english-insane' ) or die "$!\n";
foreach ( grep { /^[a-z]+$/ && chomp; } <$fh> ) {
    $key = join( '', sort( split( '', $_ ) ) );
    if ( exists( $grams{$key} ) ) {
        $out[ $grams{$key} ] .= ', ' . $_;
    }
    else {
        $grams{$key} = $k;
        $out[$k] = $_;
        $k++;
    }
}
close($fh);

print join( "\n", grep { index( $_, ',' ) >= 0 && s/,/:/; } @out );
exit;
Note complete lack of sorting (except for the anagram key) and maintaining the words list's intrinsic sort order by using a keyed array. Perl's hashes are returned in random order while arrays/lists stay sorted. The grep { pattern && effect } @list construct is a gleeful way of subverting the rather pure list processing of the grep function that just came to me. It gives you the list you want and changes it via side effects at the same time!

Let's try Heater's js on the same machine, shall we?

Code: Select all

$ time node selfgrams.js > /dev/null
FATAL ERROR: Committing semi space failed. Allocation failed - process out of memory
Aborted

real	2m37.916s
user	1m0.165s
sys	0m2.398s
I am using the ancient Raspbian version of node, but still ...
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: Project Digital Apocalypse Not Now

Mon Jul 22, 2019 5:12 pm

scruss wrote:
Mon Jul 22, 2019 3:09 pm
Let's try Heater's js on the same machine, shall we?

Code: Select all

$ time node selfgrams.js > /dev/null
FATAL ERROR: Committing semi space failed. Allocation failed - process out of memory
Aborted

real	2m37.916s
user	1m0.165s
sys	0m2.398s
I am using the ancient Raspbian version of node, but still ...
The JavaScript timings look promising. I wonder what needs to be done so that code runs on the Raspberry Pi. The incompatibility reminds me of Basic.

Speaking of Basic, I've almost finished optimizing my classic-line numbered program. The first version took less than an hour to write and verify with a short test dictionary. Unfortunately, the insane O(n^2) algorithm has been processing the British dictionary for the last two days. The digital apocalypse (if not severe global warming) will surely be upon us before it finishes.

While further optimization involving a heap has resulted in an O(n log n) algorithm, it appears the strings have caused the garbage collector to go on strike for disability compensation due to a work-related stutter. Details forthcoming may shed light on whether the same Basic which started the golden age of personal computing was also responsible for its collapse.

With that in mind, it is notable that Raspbian was made possible by Linux. Linux would not exist had there not been Unix, and Unix would not have been successful if not for the efficient portability of C. In this way, one can see that the second age of personal computing initiated by the Raspberry Pi would not have been possible without C.

As with Basic and the golden age this naturally brings up the question, will the C programming language itself ultimately lead to the collapse of the second age of personal computing and an ensuing digital apocalypse?
Last edited by ejolson on Mon Jul 22, 2019 5:34 pm, edited 6 times in total.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: Project Digital Apocalypse Not Now

Mon Jul 22, 2019 5:13 pm

scruss,
Let's try Heater's js on the same machine, shall we?
...FATAL ERROR...
Ouch! What happened there?

Time to dig out a Pi. Give me two ticks...

jalih
Posts: 76
Joined: Mon Apr 15, 2019 3:54 pm

Re: Project Digital Apocalypse Not Now

Mon Jul 22, 2019 6:15 pm

Here is a 8th version of the anagram challenge program using heap to sort keys:

Code: Select all


m:new var, anamap
a:new var, anakeys

' n:cmp h:new constant strheap

: s:sort \ s -- s
  s:len >r
  strheap  swap ' h:push s:each!
  "" swap
  (
    h:pop
    rot swap s:+ swap
  ) r> times drop ;

: process-words \ word --
  /^[a-z]+$/ r:match if
    r:str nip dup >r
    s:sort
    anamap @
    over
    m:exists? if
      over m:@ r> a:push 2drop
    else
      swap a:new r> a:push m:!
    then
  then drop ;

: read-and-check-words  \ fname --
  f:slurp ' process-words s:eachline ;

: len>=  \ key --
  anakeys @ swap a:push drop ;

: fetch-ana-list \ key array --
  a:len 2 n:cmp
  1 n:+
  nip
  [ ' drop , ' len>= , ' len>= ]
  swap
  caseof ;

: key-val-cmp          \ key1 key2
  anamap @ swap m:@    \ key1 anamap key2val
  0 a:@ nip            \ key1 anamap val2
  swap rot             \ val2 anamap key1
  m:@ nip              \ val2 key1val
  0 a:@ nip            \ val2 val1
  swap                 \ val1 val2
  s:cmp ;

: sort-keys-by-first-word
  anakeys @ ' key-val-cmp a:sort drop ;

: list-words \ value --
  " " a:join . cr ;

: app:main
  0 args "/usr/share/dict/british-english-insane" ?:
  read-and-check-words
  anamap @ ' fetch-ana-list m:each drop
  sort-keys-by-first-word
  anamap @ anakeys @ m:@@ nip ' list-words a:each! drop
  anakeys @ a:len nip "\nAnagrams: %d\n" s:strfmt .
  bye ;
Last edited by jalih on Mon Jul 22, 2019 6:26 pm, edited 2 times in total.

Return to “General programming discussion”