Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #11177 > unrolled thread

Google CodeJam?

Back to article view | Back to comp.lang.forth

Contents

  Google CodeJam? Ian Osgood <iano@quirkster.com> - 2012-04-11 16:23 -0700
    Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-12 00:43 -0700
      Re: Google CodeJam? hughaguilar96@yahoo.com - 2012-04-21 15:13 -0700
        Re: Google CodeJam? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-22 02:19 +0200
        Re: Google CodeJam? "WJ" <w_a_x_man@yahoo.com> - 2012-04-22 04:03 +0000
          Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-22 23:08 -0700
          Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-22 23:17 -0700
            Re: Google CodeJam? "WJ" <w_a_x_man@yahoo.com> - 2012-04-23 19:27 +0000
              Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-23 22:08 -0700
                Re: Google CodeJam? "WJ" <w_a_x_man@yahoo.com> - 2012-04-24 08:30 +0000
                  Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-24 23:00 -0700
                    Re: Google CodeJam? "WJ" <w_a_x_man@yahoo.com> - 2012-04-26 09:19 +0000
                      Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-26 03:17 -0700
                      Re: Google CodeJam? vandys@vsta.org - 2012-04-26 16:45 +0000
                        Re: Google CodeJam? Paul Rubin <no.email@nospam.invalid> - 2012-04-26 10:47 -0700
                        Re: Google CodeJam? Paul Rubin <no.email@nospam.invalid> - 2012-04-27 02:26 -0700
                          Re: Google CodeJam? vandys@vsta.org - 2012-04-27 16:37 +0000
                            Re: Google CodeJam? Paul Rubin <no.email@nospam.invalid> - 2012-04-27 10:17 -0700
                              Re: Google CodeJam? vandys@vsta.org - 2012-04-27 18:15 +0000
              Re: Google CodeJam? Rugxulo <rugxulo@gmail.com> - 2012-04-26 16:00 -0700
        Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-22 12:12 +0200
          Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-22 14:11 +0200
            Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-22 14:17 +0200
              Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-25 14:25 +0200
          Re: Google CodeJam? mhx@iae.nl (Marcel Hendrix) - 2012-04-22 18:23 +0200
            Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-22 22:24 +0200
              Re: Google CodeJam? mhx@iae.nl (Marcel Hendrix) - 2012-04-23 20:59 +0200
                Re: Google CodeJam? Paul Rubin <no.email@nospam.invalid> - 2012-04-23 13:56 -0700
          Re: Google CodeJam? mhx@iae.nl (Marcel Hendrix) - 2012-04-22 18:29 +0200
            Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-22 21:36 +0200
          Re: Google CodeJam? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-22 23:08 +0200
            Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-22 23:06 -0700
            Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-23 23:19 +0200
              Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-23 22:35 -0700
                Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-25 01:59 +0200
                  Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-24 22:16 -0700
                    Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-25 14:25 +0200
                      Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-25 11:58 -0700
                        Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-26 00:23 +0200
                      Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-25 11:58 -0700
                        Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-26 00:23 +0200
                      Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-25 11:58 -0700
                        Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-26 00:23 +0200
                          Re: Google CodeJam? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-26 12:36 +0000
                    Re: Google CodeJam? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-25 13:39 +0000
                      Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-25 10:05 -0700
                        Re: Google CodeJam? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-26 16:30 +0000
                    Re: Google CodeJam? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-27 15:21 +0200
              Re: Google CodeJam? Paul Rubin <no.email@nospam.invalid> - 2012-04-24 00:51 -0700
                Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-25 01:59 +0200
          Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-25 01:59 +0200
            Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-27 14:15 +0200
              Re: Google CodeJam? hughaguilar96@yahoo.com - 2012-04-30 23:54 -0700
                Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-05-02 01:44 +0200
                  Re: Google CodeJam? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-05-01 20:45 -0700
                    Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-05-02 23:38 +0200
        Re: Google CodeJam? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-04-24 12:50 +0100
          Re: Google CodeJam? Paul Rubin <no.email@nospam.invalid> - 2012-04-24 08:22 -0700
          Re: Google CodeJam? mhx@iae.nl (Marcel Hendrix) - 2012-04-24 22:28 +0200
            Re: Google CodeJam? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-04-25 09:50 +0100
          Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-25 01:59 +0200
            Re: Google CodeJam? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-04-25 09:49 +0100
    Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-04-27 18:28 +0200
      Re: Google CodeJam? Bruno Gauthier <bgauthier@free.fr> - 2012-05-01 17:59 +0200
        Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-05-01 19:12 +0200
          Re: Google CodeJam? Bruno Gauthier <bgauthier@free.fr> - 2012-05-01 20:39 +0200
          Re: Google CodeJam? mhx@iae.nl - 2012-05-01 16:00 -0700
            Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-05-02 02:29 +0200
          Re: Google CodeJam? Paul Rubin <no.email@nospam.invalid> - 2012-05-01 19:18 -0700
            Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-05-02 05:14 +0200
        Re: Google CodeJam? awegel@arcor.de (Alex Wegel) - 2012-05-02 01:44 +0200

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#11521

<hughaguilar96@yahoo.com> wrote:

> It seems extremely unlikely that any Forther is going to come up with
> a Forth program to compete against mine.

OK, now that you managed to escape my kill filter, i take the challenge.

After 1 hour and 15 minutes, i got this (ugly but working) solution (with the
sample data coming from the file "alien-sample"):

#! /usr/local/bin/gforth
variable ifh
s" alien-sample" r/o open-file throw ifh !

variable #ib
create ifb 256 allot
: getl ifb 256 ifh @ read-line throw drop #ib ! ;

variable L
variable D
variable N
: parse-headline ifb #ib @ evaluate N ! D ! L ! ;

getl parse-headline

D @ L @ * constant #ad
variable adp
: c>msk 1 swap [char] a - lshift ;
: add-achar c>msk adp @ ! 4 adp +! ;
: add-aword ifb #ib @ bounds do i c@ add-achar loop ;
create adic  #ad 4 * allot
: read-adic adic adp ! D @ 0 do getl add-aword loop ;
read-adic

create pat L @ 4 * allot
variable pp

: ccl 0 swap begin 1+ dup c@ dup [char] ) <> while c>msk rot or swap
  repeat drop swap ;

: make-pat
  pat pp !
  ifb
  L @ 0 do
        dup c@
        dup [char] ( = if
                drop ccl
        else
                c>msk
        then
        pp @ ! 4 pp +!
        1+
  loop drop ;

: chk-1match L @ 4 * 0 do dup i + @ i pat + @ and 0= if unloop drop false exit
then 4 +loop drop true ;
: matches 0 adic #ad 4 * bounds do i chk-1match 1 and + L @ 4 * +loop ; 
: chk-all
  N @ 1+ 1 do getl make-pat  matches ." Case #" i . ." : " . cr loop ;

chk-all

ifh @ close-file throw

[toc] | [prev] | [next] | [standalone]

#11524

Alex Wegel <awegel@arcor.de> wrote:

Small correction: The input buffer must be much larger for the big
example, so change

  create ifb 256 allot
  : getl ifb 256 ifh @ read-line throw drop #ib ! ;

to sth. like

  create ifb 10000 allot
  : getl ifb 10000 ifh @ read-line throw drop #ib ! ;

(and take care that gforth has enough dict-mem available, eg. by using
"gforth -m 4M")

Also, i didn't care to make the output format match the question exactly
(there are 2 superfluous spaces in every line) - well..

[toc] | [prev] | [next] | [standalone]

#11525

Alex Wegel <awegel@arcor.de> wrote:

> Alex Wegel <awegel@arcor.de> wrote:
> 
> Small correction: The input buffer must be much larger for the big
> example, so change
> 
>   create ifb 256 allot
>   : getl ifb 256 ifh @ read-line throw drop #ib ! ;
> 
> to sth. like
> 
>   create ifb 10000 allot
>   : getl ifb 10000 ifh @ read-line throw drop #ib ! ;
> 
> (and take care that gforth has enough dict-mem available, eg. by using
> "gforth -m 4M")
> 
> Also, i didn't care to make the output format match the question exactly
> (there are 2 superfluous spaces in every line) - well..


Another remark: In my even more rusty perl, it was much simpler to do
quick & dirty (by following the suggestion to change the ()'s to []'s):

#!/usr/bin/perl
my ($l, $d, $n) = split " ",<>;

my @d=();
foreach my $i (1..$d) { push @d, scalar <>; }

my @p=();
foreach my $i (1..$n) { push @p, scalar <>; }

map { $_ =~ s/\(/[/g; } @p;
map { $_ =~ s/\)/]/g; } @p;

map { print "".$_."\n"; } @p;

my $c=0;
map {
        my $m=0;
        for ($i=0; $i<$d; ++$i) {
                if ( $d[$i] =~ m($_) ) {++$m;}
        }
        print "Case #".++$c.": $m\n";
} @p;

[toc] | [prev] | [next] | [standalone]

#11605

Alex Wegel <awegel@arcor.de> wrote:

> Another remark: In my even more rusty perl, it was much simpler to do
> quick & dirty (by following the suggestion to change the ()'s to []'s):

I wasn't happy with the clumsy perl code i wrote, so i tried again:

#!/usr/bin/perl
my ($l, $d, $n) = split " ",<>;
while ($d--) { push @d, scalar <>; }
$c=0;
while (<>) {
        ($p = $_) =~ tr/()/[]/;
        $m=0;
        map { $m += m($p) } @d;
        print "Case ".++$c.": $m\n";
}

[toc] | [prev] | [next] | [standalone]

#11531

awegel@arcor.de (Alex Wegel) writes Re: Google CodeJam?
[..]

> After 1 hour and 15 minutes, i got this (ugly but working) solution (with the
> sample data coming from the file "alien-sample"):

It took me somewhat longer because I started on the wrong foot (generating
all possible strings :-) and encountered 'performance problems.' 

-marcel

-- ---------------------------------

'z' 'a' - 1+ =: CMAXI
  #15 =: LMAXI
#5000 =: DMAXI

0 VALUE L
0 VALUE D
0 VALUE N
0 VALUE #matches

CREATE clists   LMAXI CMAXI * CHARS ALLOT 
CREATE dict	LMAXI DMAXI * CHARS ALLOT

: clear-clists	( -- ) clists LMAXI CMAXI * CHARS ERASE ;
: cl-row        ( row# -- addr ) CMAXI * CHARS clists + ;
: dict-row      ( row# -- addr ) LMAXI * CHARS dict + ;
: char!         ( addr char -- ) 'a' - CHARS +  1 SWAP C! ;
: char?         ( addr char -- ) 'a' - CHARS + C@ ;
: next-line     ( -- c-addr u )  REFILL 0= IF  QUIT  ENDIF ;
: GET-L,D,N     ( -- ) next-line 0 WORD COUNT EVALUATE  TO N TO D TO L ;
: create-dictword ( index -- )  next-line  SOURCE  ROT dict-row PACK DROP  SOURCE >IN ! DROP ;
: BUILD-DICT    ( -- )  D 0 ?DO  I create-dictword  LOOP ;

: next-char ( -- char ) 
	SOURCE  >IN @ <= IF  DROP 0 EXIT  ENDIF  
	( addr) >IN @ + C@  1 >IN +! ;

: collect-chars ( addr --  )
	>R BEGIN  next-char DUP ')' <>
	   WHILE  R@ SWAP char!
	   REPEAT DROP R> DROP ;

: create-clists ( -- )
	clear-clists
	L 0 ?DO  I cl-row  next-char DUP '(' = IF  DROP collect-chars  ELSE  char!  ENDIF  LOOP ;

: cl-test?   ( char pos -- TRUE=match ) cl-row SWAP char? ;
: $possible? ( c-addr u -- n ) 0 LOCAL #ok  0 ?DO  C@+  I cl-test? +TO #ok  LOOP DROP  #ok ;
: matches    ( -- ) D 0 ?DO  I dict-row COUNT $possible? L = IF  1 +TO #matches  ENDIF  LOOP ;
: one-case   ( -- ) next-line  create-clists  matches ;
: CASES      ( -- ) N 0 ?DO  CLEAR #matches one-case  CR ." Case #" I 1+ 0 .R SPACE #matches . LOOP ;
: MATCH      ( -- ) GET-L,D,N BUILD-DICT CASES ;

-- Output -----------------------------------------------

	Case #1 1
	Case #2 0
	Case #3 1
	Case #4 6
	Case #5 8
	Case #6 1
	Case #7 8
	Case #8 1
	Case #9 9
	Case #10 0

[toc] | [prev] | [next] | [standalone]

#11534

Marcel Hendrix <mhx@iae.nl> wrote:

> awegel@arcor.de (Alex Wegel) writes Re: Google CodeJam?
> [..]
> 
> > After 1 hour and 15 minutes, i got this (ugly but working) solution
> > (with the sample data coming from the file "alien-sample"):
> 
> It took me somewhat longer because I started on the wrong foot (generating
> all possible strings :-) and encountered 'performance problems.' 

Wouldn't have happened with a quantum computer, i guess ;)

> -- Output -----------------------------------------------
>       Case #1 1
>       Case #2 0
>       Case #3 1
>       Case #4 6
>       Case #5 8
>       Case #6 1
>       Case #7 8
>       Case #8 1
>       Case #9 9
>       Case #10 0

I think the result is wrong (mostly because you were too smart about the
input - see other message. Not sure why your case #9 got 1 more than my
case 10, though).

I got 

Case #1: 0
Case #2: 1
Case #3: 0
Case #4: 1
Case #5: 6
Case #6: 7
Case #7: 1
Case #8: 8
Case #9: 1
Case #10: 8

..and it was accepted as correct.

BTW (Just for boasting):
Runtime (gforth on powerpc mac @1.8GHz) for the large set was 2.0s (with
1.5s utime), or 0.4s (0.3s utime) using gforth-fast :-)

Anyway, my solution is the best, because the aliens would have no chance
to decipher the program :-)

Alex

[toc] | [prev] | [next] | [standalone]

#11547

awegel@arcor.de (Alex Wegel) writes Re: Google CodeJam?

> Marcel Hendrix <mhx@iae.nl> wrote:

>> awegel@arcor.de (Alex Wegel) writes Re: Google CodeJam?
[..]
> I think the result is wrong (mostly because you were too smart about the
> input - see other message. Not sure why your case #9 got 1 more than my
> case 10, though).

Yes, the off-by-one caused the mismatch. However, the large sample exposed
a really shameful bug in my program: it overwrote the dictionary strings 
because I had forgotten the count bytes (size 15 instead of 16).

[..]

> BTW (Just for boasting):
> Runtime (gforth on powerpc mac @1.8GHz) for the large set was 2.0s (with
> 1.5s utime), or 0.4s (0.3s utime) using gforth-fast :-)

Thanks for posting this number, it prompted me to get the bug out 
so I could beat that :-)

Using iForth (64bit) on my old Core i7 920 @2.67 GHz machine, it ran the
large sample in 139 ms.

> Anyway, my solution is the best, because the aliens would have no chance
> to decipher the program :-)

No discussion with that.

-marcel

[toc] | [prev] | [next] | [standalone]

#11549

mhx@iae.nl (Marcel Hendrix) writes:
> Using iForth (64bit) on my old Core i7 920 @2.67 GHz machine, it ran the
> large sample in 139 ms.

Pretty impressive.  I tried a simple Python script using Python's regexp
module and it took about 2.1 sec to do the large sample on my laptop,
2.5 ghz Core 2 Duo using a single core.  Coding time including fixing a
couple of errors was probably in the 8 minute range (I didn't time it).
I got a bit careless by trying to code too fast, which of course slowed
me down.

[toc] | [prev] | [next] | [standalone]

#11532

mhx@iae.nl (Marcel Hendrix) writes Re: Google CodeJam?

> awegel@arcor.de (Alex Wegel) writes Re: Google CodeJam?
> [..]

>> After 1 hour and 15 minutes, i got this (ugly but working) solution (with the
>> sample data coming from the file "alien-sample"):

> It took me somewhat longer because I started on the wrong foot (generating
> all possible strings :-) and encountered 'performance problems.' 

Before I forget, there is an error in the original input file 
A-small-practice.in :

--- 
10 25 10
nwlrbbmqbh
cdarzowkky
...
---

That should be 10 26 10. It may influence the results.

-marcel

[toc] | [prev] | [next] | [standalone]

#11533

Marcel Hendrix <mhx@iae.nl> wrote:

> Before I forget, there is an error in the original input file 
> A-small-practice.in :
> 
> --- 
> 10 25 10
> nwlrbbmqbh
> cdarzowkky
> ...
> ---
> 
> That should be 10 26 10. It may influence the results.

Nope - it just *looks* like it should be ..26.. because the first of the
10 patterns is a plain literal (with no parentheses)!

[toc] | [prev] | [next] | [standalone]

#11535

Alex Wegel wrote:

> <hughaguilar96@yahoo.com> wrote:
> 
>> It seems extremely unlikely that any Forther is going to come up with
>> a Forth program to compete against mine.
> 
> OK, now that you managed to escape my kill filter, i take the
> challenge.
> 
> After 1 hour and 15 minutes, i got this (ugly but working) solution
> (with the sample data coming from the file "alien-sample"):

If you learn how to use CELL, CELL+ and CELLS instead of 4, 4 + and 4 *, 
your program will work on a 64 bit CPU as well.

I like this solution, because it shows that this subset of pattern 
matching can be done without too much hassle (and good performance) in 
plain Forth.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[toc] | [prev] | [next] | [standalone]

#11537

On Apr 22, 3:08 pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:
> Alex Wegel wrote:
> > <hughaguila...@yahoo.com> wrote:
>
> >> It seems extremely unlikely that any Forther is going to come up with
> >> a Forth program to compete against mine.
>
> > OK, now that you managed to escape my kill filter, i take the
> > challenge.
>
> > After 1 hour and 15 minutes, i got this (ugly but working) solution
> > (with the sample data coming from the file "alien-sample"):
>
> If you learn how to use CELL, CELL+ and CELLS instead of 4, 4 + and 4 *,
> your program will work on a 64 bit CPU as well.
>
> I like this solution, because it shows that this subset of pattern
> matching can be done without too much hassle (and good performance) in
> plain Forth.

Mine isn't plain Forth??? What does that term mean?

When I wrote mine, I originally got off on the "wrong foot" by writing
a program that used <SPLIT> to convert the pattern-string into a SEQ
list, and would then interpret that list for every pattern match. This
became complicated, as it involved a lot of nested loops. I think that
it would have been slow too, because it involved doing the same work
redundantly for every pattern match (I don't know what the speed would
have been though, as I never got this version running). Switching over
to generating a pattern-matching function simplified the program
considerably and also made it faster.

So my 3 hour effort actually included writing *two* programs --- one
that didn't work and was badly designed, and a second that you see
above. With better planning, I could have possibly gotten the time
down to 1 hour --- but, of course, you have to still consider the time
required to think up the plan, which would put me back at the 3 hour
figure.

[toc] | [prev] | [next] | [standalone]

#11551

Bernd Paysan <bernd.paysan@gmx.de> wrote:

> If you learn how to use CELL, CELL+ and CELLS instead of 4, 4 + and 4 *,
> your program will work on a 64 bit CPU as well.

That's wrong - i know them already, but didn't use them in this
quick&dirty approach (that's part of what i meant by "ugly"?).

One thing keeping me from using CELLxy words is that the number 4
doesn't really relate to the systems/cpus cell size, but rather to the
size (in AU) of the bit-set representation (26 bits).
So, using CELLxy wouldn't be the right answer for smaller cpus or larger
bit-sets (what if scientists find out that the aliens use 65 characters
on tuesday?).

I think it would be more worthwhile to use a more compact representation
for the alien-dictionary (e.g. by storing the chars themselves instead
of bitsets having exactly one bit set) and thereby getting rid of the 4*
stuff alltogether (at least concerning the dictionary).

> I like this solution, because it shows that this subset of pattern 
> matching can be done without too much hassle (and good performance) in
> plain Forth.

Thanks.
The alien example was perfect for such.

Cheers,
Alex

[toc] | [prev] | [next] | [standalone]

#11555

On Apr 23, 3:19 pm, awe...@arcor.de (Alex Wegel) wrote:
> Bernd Paysan <bernd.pay...@gmx.de> wrote:
> > If you learn how to use CELL, CELL+ and CELLS instead of 4, 4 + and 4 *,
> > your program will work on a 64 bit CPU as well.
>
> That's wrong - i know them already, but didn't use them in this
> quick&dirty approach (that's part of what i meant by "ugly"?).
>
> One thing keeping me from using CELLxy words is that the number 4
> doesn't really relate to the systems/cpus cell size, but rather to the
> size (in AU) of the bit-set representation (26 bits).
> So, using CELLxy wouldn't be the right answer for smaller cpus or larger
> bit-sets (what if scientists find out that the aliens use 65 characters
> on tuesday?).

I understand how your program works. I hadn't thought of this
technique at all. So I've learned something!

Your program is really hard to read. Now that we are no longer speed-
programming on a stop-watch, can you provide a cleaner version with
some comments?

It is possible to use your technique, and to also generate a function
the way that I did.

> I think it would be more worthwhile to use a more compact representation
> for the alien-dictionary (e.g. by storing the chars themselves instead
> of bitsets having exactly one bit set) and thereby getting rid of the 4*
> stuff alltogether (at least concerning the dictionary).

That would only be true if the patterns were mostly absolute chars. If
the patterns contain a lot of () sets, and the () sets typically
contain more than 4 chars, you'll save memory and have a faster
program by sticking with your current technique.

BTW, isn't anybody going to criticize my program because it fails to
work at all on the large input set? This is due to the fact that I
used my SEQ lists from LIST.4TH, and they are limited to 255 char
strings, whereas most of the pattern strings in the large input file
are upwards of 1K in size. This is easy to fix --- all I have to do is
write a new version of SEQ that allows big strings (I'll do this in
the next novice-package upgrade). When I was speed-programming
however, I just used my existing SEQ rather than write all of that low-
level stuff from scratch. I didn't realize this was a problem until
after the program was written and I noticed that it worked fine on the
small input file but not the large input file (I hadn't even visually
inspected the large file at that time, but had just vaguely assumed
that it was the same as the small input file just with more patterns
and more words).

[toc] | [prev] | [next] | [standalone]

#11585

Hugh Aguilar <hughaguilar96@yahoo.com> wrote:

> I understand how your program works. I hadn't thought of this
> technique at all. So I've learned something!
> 
> Your program is really hard to read. Now that we are no longer speed-
> programming on a stop-watch, can you provide a cleaner version with
> some comments?

Yes i can :-)

But i did sth. else instead: Reducing the dict size by a factor of 4,
getting the source to less than 1K (this means: still no comments),
while roughly maintaining execution speed (still at 0.3sec for the large
set).

> It is possible to use your technique, and to also generate a function
> the way that I did.
> 
> > I think it would be more worthwhile to use a more compact representation
> > for the alien-dictionary (e.g. by storing the chars themselves instead
> > of bitsets having exactly one bit set) and thereby getting rid of the 4*
> > stuff alltogether (at least concerning the dictionary).
> 
> That would only be true if the patterns were mostly absolute chars.

I meant the dictionary of words, not the patterns (the 5000 words are
stored real wasteful in my first version, while there's only 1 pattern
stored in memory at any time).
The runtime penalty of the new form is a more or less a "lshift" for
each comparison (about 40.000.000 times), which isn't so very long on a
GHz-class cpu.

> BTW, isn't anybody going to criticize my program because it fails to
> work at all on the large input set?

It didn't work here (on gforth/powerpc) even for the small set, and i
didn't feel like debugging either of these packages (novice, list).

> This is due to the fact that I
> used my SEQ lists from LIST.4TH, and they are limited to 255 char
> strings, whereas most of the pattern strings in the large input file
> are upwards of 1K in size.

The patterns can't be larger than (26+2)*15 = 420 characters,
and actually the longest one has 382 chars.

> This is easy to fix --- all I have to do is
> write a new version of SEQ that allows big strings (I'll do this in
> the next novice-package upgrade). When I was speed-programming
> however, I just used my existing SEQ rather than write all of that low-
> level stuff from scratch. I didn't realize this was a problem until
> after the program was written and I noticed that it worked fine on the
> small input file but not the large input file (I hadn't even visually
> inspected the large file at that time, but had just vaguely assumed
> that it was the same as the small input file just with more patterns
> and more words).

It seems to me that the novice package was more an obstacle, rather than
a helpful tool (at least in this case).

[toc] | [prev] | [next] | [standalone]

#11592

On Apr 24, 5:59 pm, awe...@arcor.de (Alex Wegel) wrote:
> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > BTW, isn't anybody going to criticize my program because it fails to
> > work at all on the large input set?
>
> It didn't work here (on gforth/powerpc) even for the small set, and i
> didn't feel like debugging either of these packages (novice, list).

That is grossly unfair, to say that my novice.4th and list.4th
packages need debugging. They and the alien.4th program all work fine.

When I run alien.4th under SwiftForth I get the correct (according to
Google validation) result:

Case #1: 0
Case #2: 1
Case #3: 0
Case #4: 1
Case #5: 6
Case #6: 7
Case #7: 1
Case #8: 8
Case #9: 1
Case #10: 8

When I run alien.4th under Gforth, Gforth aborts with this message:
gforth: ./main.c.1188 optimize_bb: Assertion `ninsts<128' failed

I have no idea what that means, and I don't really care --- it is not
my job to debug Gforth --- even when Gforth does work, it is too slow
to be useful in any way, so I have no motivation to coax Gforth into
working.

The last time that I had software that didn't work under Gforth, Anton
Ertl criticized me for not knowing that some words don't have an xt
value. WTF??? How was I supposed to know that? Gforth is full of weird
quirks that have to be worked around. This is just a bug in Gforth ---
but no doubt Anton Ertl will blame me for it, just as you have done.

You know, there is a reason why I'm writing Straight Forth --- it is
because Gforth is garbage.

I really believe that Anton Ertl purposely crippled Gforth so that it
wouldn't be competitive against SwiftForth. He is just a stooge of
Forth Inc.. Most likely this bug is part of that effort --- he
crippled Gforth in some way so that it would crash on programs that
SwiftForth handles okay, in order to make SwiftForth look good --- so
that people wouldn't notice how bad SwiftForth is in regard to its
complete lack of optimization.

> It seems to me that the novice package was more an obstacle, rather than
> a helpful tool (at least in this case).

Your program is incredibly ugly. Bernd Paysan calls this "plain Forth"
--- but that really speaks volumes in regard to how bad Forth code
quality has become since the release of ANS-Forth in 1994 --- my
novice package allows me to write beautiful Forth code quickly.

I don't think that it is fair to disparage my novice package because
some of the string stuff is limited to strings < 255 characters in
length --- this has been a common limitation in Forth for decades ---
alien.4th is the first program that I've written in which this
limitation was an issue (the A-large-practice.in file containing
pattern strings longer than 255 chars). Also, as I said, it is easy
enough for me to write a version of SEQ that allows for big strings
--- this is actually trivial --- this has nothing to do with the core
ideas of the novice package.

[toc] | [prev] | [next] | [standalone]

#11606

Hugh Aguilar <hughaguilar96@yahoo.com> wrote:

> On Apr 24, 5:59 pm, awe...@arcor.de (Alex Wegel) wrote:
> > Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > > BTW, isn't anybody going to criticize my program because it fails to
> > > work at all on the large input set?
> >
> > It didn't work here (on gforth/powerpc) even for the small set, and i
> > didn't feel like debugging either of these packages (novice, list).
> 
> That is grossly unfair, to say that my novice.4th and list.4th
> packages need debugging. They and the alien.4th program all work fine.

Well - i now took the time (the lack of which was the main reason i
didn't investigate the failure earlier) to try again (using a different
invocation), and guess what: The small example worked.

> You know, there is a reason why I'm writing Straight Forth --- it is
> because Gforth is garbage.

So you are the god of fairness - LOL!

> I really believe that Anton Ertl purposely crippled Gforth so that it
> wouldn't be competitive against SwiftForth. He is just a stooge of
> Forth Inc..  Most likely this bug is part of that effort --- he
> crippled Gforth in some way so that it would crash on programs that
> SwiftForth handles okay, in order to make SwiftForth look good --- so
> that people wouldn't notice how bad SwiftForth is in regard to its
> complete lack of optimization.

You're obviously paranoid (which is not to say that they're not after
you).

But i know that you're on an agenda (as you repeatedly stated here): To
bring down Forth Inc.

Seriously: The offensive (and untrue) off-topic stuff that you write
here every other day is going on my nerves big time - you're close to
ending up in the filter once again.

> > It seems to me that the novice package was more an obstacle, rather than
> > a helpful tool (at least in this case).
> 
> Your program is incredibly ugly.

Yes, that's what i wrote about it.

> Bernd Paysan calls this "plain Forth"

Because it doesn't have to include anything on top of forth.
Is that so hard to get?

Your code first loads >64KB (!!) of stuff before doing anything.

> --- but that really speaks volumes in regard to how bad Forth code
> quality has become since the release of ANS-Forth in 1994 --- my
> novice package allows me to write beautiful Forth code quickly.

We just saw that. :-)
I still say: It brought you tools that you didn't realls need for the
task, which lead you to writing a program whose source is 5 times as big
as need to be (not including the novice packages source), just in order
to solve problems (eg. complaining about invalid input data and looking
overly neat) that were not part of the task.
Then it even turned out that your SEQ basically was mis-applied in it's
current form, requiring a package update (which might be easy to do for
you and me, but surely not for a novice who would be stuck right there,
waiting for you to come up with the update - and then you pretend that
you're so much better than some company X).

> I don't think that it is fair to disparage my novice package because
> some of the string stuff is limited to strings < 255 characters in
> length --- this has been a common limitation in Forth for decades ---

The fact that you have to rewrite parts of SEQ just means that it's not
very flexible. (Which matters because it obviously pretends to be sth.
to build upon: It even fooled you, the author, and kept you from solving
the large example.)

> alien.4th is the first program that I've written in which this
> limitation was an issue (the A-large-practice.in file containing
> pattern strings longer than 255 chars).

You see: It happens just when you would have to deliver in 8 minutes.

> Also, as I said, it is easy
> enough for me to write a version of SEQ that allows for big strings
> --- this is actually trivial --- 

...So, have you fixed it now?

> this has nothing to do with the core
> ideas of the novice package.

Which are?

Alex

[toc] | [prev] | [next] | [standalone]

#11626

On Apr 25, 6:25 am, awe...@arcor.de (Alex Wegel) wrote:
> But i know that you're on an agenda (as you repeatedly stated here): To
> bring down Forth Inc.

The world is full of sleazy salespeople selling garbage to
unsuspecting customers. I don't interfere with them --- caveat emptor.
Elizabeth Rather has spent her entire career telling everybody about
how she knew Chuck Moore back in the 1970s. That is just name-
dropping. Now she tells us that she personally knows many members of
Barack Obama's family. That is just more name-dropping. If people are
dumb enough to believe this baloney, then they deserve to get ripped
off.

Elizabeth Rather attacked my code. When Passaniti said that it "sucks"
and was "pulled out of my ass," she described this as: "perceptive and
technically sound." She herself said that my novice package was
"written by a novice." She stepped over the line! She can't expect me
to not interfere with her sleazy SwiftForth scam after saying such
things about my code. Of course I'm going to point out the gross
problems with SwiftForth --- she shouldn't have attacked my code ---
people who live in glass houses shouldn't throw stones.

When I'm driving my cab, people often tell me about how they hob-nob
with celebrities, and then when we get to the destination they say
that they have to go inside to get the money (presumably from their
buddy Barack) --- I don't let them get away with this --- I have put
people in jail for this --- and I have given them a beating first,
before handing them over to the police. I can spot phonies a mile away
--- Elizabeth Rather is a complete phony, attaching herself like a
leach to Chuck Moore --- I am amazed that the comp.lang.forth crowd
fails to see this (or, pretends not to see it).

SwiftForth really is a glass house. I paid almost $500 for it, and it
has serious bugs. For example, (LOCAL) doesn't work and will crash the
system. Also, it does essentially no optimization at all --- it just
pastes the code from sub-functions into the calling function --- all
that this saves is the CALL and RET, which isn't much, and it bloats
out the code so that it no longer fits in the cache. In SwiftForth,
ALIGN and ALIGNED are no-ops, so we don't even get aligned data, which
is a very basic optimization that even the most novice assembly-
language programmers know about. SwiftForth gives the Forth community
a bad name --- this is especially true because it comes from Forth
Inc. --- casual observers assume that Forth Inc. defines Forth,
because Forth Inc. owns the name "Forth" (and because Elizabeth Rather
learned Forth directly from Chuck Moore in the 1970s, yada yada).

[toc] | [prev] | [next] | [standalone]

#11635

Hugh Aguilar <hughaguilar96@yahoo.com> wrote:

> On Apr 25, 6:25 am, awe...@arcor.de (Alex Wegel) wrote:
> > But i know that you're on an agenda (as you repeatedly stated here): To
> > bring down Forth Inc.
> 

aha

[toc] | [prev] | [next] | [standalone]

#11627

On Apr 25, 6:25 am, awe...@arcor.de (Alex Wegel) wrote:
> But i know that you're on an agenda (as you repeatedly stated here): To
> bring down Forth Inc.

The world is full of sleazy salespeople selling garbage to
unsuspecting customers. I don't interfere with them --- caveat emptor.
Elizabeth Rather has spent her entire career telling everybody about
how she knew Chuck Moore back in the 1970s. That is just name-
dropping. Now she tells us that she personally knows many members of
Barack Obama's family. That is just more name-dropping. If people are
dumb enough to believe this baloney, then they deserve to get ripped
off.

Elizabeth Rather attacked my code. When Passaniti said that it "sucks"
and was "pulled out of my ass," she described this as: "perceptive and
technically sound." She herself said that my novice package was
"written by a novice." She stepped over the line! She can't expect me
to not interfere with her sleazy SwiftForth scam after saying such
things about my code. Of course I'm going to point out the gross
problems with SwiftForth --- she shouldn't have attacked my code ---
people who live in glass houses shouldn't throw stones.

When I'm driving my cab, people often tell me about how they hob-nob
with celebrities, and then when we get to the destination they say
that they have to go inside to get the money (presumably from their
buddy Barack) --- I don't let them get away with this --- I have put
people in jail for this --- and I have given them a beating first,
before handing them over to the police. I can spot phonies a mile away
--- Elizabeth Rather is a complete phony, attaching herself like a
leach to Chuck Moore --- I am amazed that the comp.lang.forth crowd
fails to see this (or, pretends not to see it).

SwiftForth really is a glass house. I paid almost $500 for it, and it
has serious bugs. For example, (LOCAL) doesn't work and will crash the
system. Also, it does essentially no optimization at all --- it just
pastes the code from sub-functions into the calling function --- all
that this saves is the CALL and RET, which isn't much, and it bloats
out the code so that it no longer fits in the cache. In SwiftForth,
ALIGN and ALIGNED are no-ops, so we don't even get aligned data, which
is a very basic optimization that even the most novice assembly-
language programmers know about. SwiftForth gives the Forth community
a bad name --- this is especially true because it comes from Forth
Inc. --- casual observers assume that Forth Inc. defines Forth,
because Forth Inc. owns the name "Forth" (and because Elizabeth Rather
learned Forth directly from Chuck Moore in the 1970s, yada yada).

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | comp.lang.forth

csiph-web