Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #11177 > unrolled thread
| Started by | Ian Osgood <iano@quirkster.com> |
|---|---|
| First post | 2012-04-11 16:23 -0700 |
| Last post | 2012-05-02 01:44 +0200 |
| Articles | 20 on this page of 71 — 15 participants |
Back to article view | Back to comp.lang.forth
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 1 of 4 [1] 2 3 4 Next page →
| From | Ian Osgood <iano@quirkster.com> |
|---|---|
| Date | 2012-04-11 16:23 -0700 |
| Subject | Google CodeJam? |
| Message-ID | <97af1620-3418-40b0-8c6f-b4ef828227c2@iu9g2000pbc.googlegroups.com> |
Four years, and never a Forth entry. Anyone want to put Forth on the scoreboard this year? Registration is open and the qualification round is on Friday. http://code.google.com/codejam/
[toc] | [next] | [standalone]
| From | Hugh Aguilar <hughaguilar96@yahoo.com> |
|---|---|
| Date | 2012-04-12 00:43 -0700 |
| Message-ID | <ef8dcfcf-f7b6-474f-a20d-197d269575cd@f37g2000yqc.googlegroups.com> |
| In reply to | #11177 |
On Apr 11, 5:23 pm, Ian Osgood <i...@quirkster.com> wrote: > Four years, and never a Forth entry. Anyone want to put Forth on the > scoreboard this year? Registration is open and the qualification round > is on Friday. > > http://code.google.com/codejam/ Armed with my novice package, I'm the only Forther on the planet who has any chance at all. All of the problems seem to involve reading in a data file, processing it, and writing out a solution file. My LIST. 4TH would work very well (especially the SEQ lists). I also have ordered associative arrays, which could come in handy. I've got a lot of code in there --- no Forther is even close to me. http://www.forth.org/novice.html Without regular expressions though, I don't have a very good chance --- that was something I meant to add to the novice package, but never got around to doing --- the only CodeJam example problem I looked at closely was "alien language," and having regular expressions would have helped with it. Of course, it is possible to write code manually to do string pattern-matching, but with the tight time limits that wouldn't be competitive against the myriad scripting languages in use nowadays. I'm hesitant to take Friday off, as Friday is my big money day driving the cab --- so I won't enter. Just for fun, lets have our own comp.lang.forth contest to write the best Forth solution to the "alien language" problem. http://code.google.com/codejam/contest/90101/dashboard#s=p0 This will be a loser's consolation contest, as none of us have any chance at the real contest.
[toc] | [prev] | [next] | [standalone]
| From | hughaguilar96@yahoo.com |
|---|---|
| Date | 2012-04-21 15:13 -0700 |
| Message-ID | <13201023.2427.1335046423871.JavaMail.geo-discussion-forums@ynbi17> |
| In reply to | #11189 |
On Thursday, April 12, 2012 1:43:19 AM UTC-6, Hugh Aguilar wrote:
> Just for fun, lets have our own comp.lang.forth contest to write the
> best Forth solution to the "alien language" problem.
> http://code.google.com/codejam/contest/90101/dashboard#s=p0
> This will be a loser's consolation contest, as none of us have any
> chance at the real contest.
I've waited and waited, but nobody has come forward. To qualify for the CodeJam contest, the program had to be written in under 8 minutes. That is very fast programming; I think that a typical programmer using a modern language would take about 1/2 hour. My own Forth program took me about 3 hours, so I am 6 times slower than pretty much everybody. This is a big part of why Forth is not used in the work world. No employer is going to pay anybody to program in Forth when it takes 6 times longer to write a program than it does in any other language. Also, I had the advantage of having my novice package available. Without the novice package, I think most Forth programmers would take maybe 3 days to write a program like this (that is why nobody responded to my challenge).
It seems extremely unlikely that any Forther is going to come up with a Forth program to compete against mine. I would like to see programmers of other languages, such as Lisp and Ruby and so forth, present their own programs along with a mention of how much time was required. It is okay to post non-Forth code on comp.lang.forth --- nobody is posting Forth code --- if we are going to get any code posted, it will have to be in other languages.
Here is my own Forth code:
\ This is the solution to the "alien language" example problem from Google CodeJam.
\ http://code.google.com/codejam/contest/90101/dashboard#s=p0
\ Written by Hugh Aguilar --- copyright (c) 2012 --- BSD license
\ requires novice.4th and list.4th
marker alien.4th
\ ******
\ ****** input and output
\ ******
variable #letters
variable #words
variable #patterns
: seqs ( name-str -- word-seq pattern-seq )
read-seq
dup .line @ count evaluate
#patterns ! #words ! #letters !
.fore @ \ -- word-seq
dup #words @ nth \ -- word-seq pattern-seq
delink
dup #patterns @ nth \ -- word-seq pattern-seq extraneous-seq
delink kill-seq \ -- word-seq pattern-seq
\ error checking
over length #words @ <> abort" *** bad word-seq ***"
dup length #patterns @ <> abort" *** bad pattern-seq ***"
over each[ .line @ c@ #letters @ <> abort" *** string in word-seq is wrong length ***" ]each ;
: dump-result ( pattern-list name-str -- )
<cstr +cstr c" .result" +cstr cstr> write-seq ;
\ ******
\ ****** convert pattern string into any-seq list
\ ****** each node in the list represents one char in the target string
\ ****** the .LINE string of each node contains all of the character that would match
\ ******
: check-any-str { pattern-str head -- }
head length #letters @ <> if
cr ." *** any-seq is the wrong length ***"
cr pattern-str count type
cr true abort" *** aborting ***
then ;
\ If CHECK-ANY-STR fails, this is usually because the pattern-str is longer than 255 characters and it got truncated.
\ This happens in the file: A-large-practice.in
\ I could upgrade the program to deal with this problem, but doing so would involve rewriting the SEQ code in LIST.4TH.
: <make-any-seq> ( head str -- head )
dup c@ if new-seq link \ str has characters in it
else drop then ;
: make-any-seq { pattern-str | group? -- any-seq }
nil <cstr
pattern-str count bounds ?do \ -- head
group? if \ if inside of ( ) group
I c@ [char] ) = if false to group? cstr> <make-any-seq> <cstr
else I c@ char+cstr then
else \ else outside of ( ) group
I c@ [char] ( = if true to group?
else I c@ char+cstr cstr> <make-any-seq> <cstr then
then
loop
cstr> <make-any-seq>
pattern-str over check-any-str ;
\ ******
\ ****** generate pattern matcher
\ ******
char & comment \ this is an example of what will get generated
:noname ( char-adr -- match? ) \ this is for: a(bc)
false \ -- char-adr any?
over c@ 97 = if true or then
0= if drop false exit then
1+ \ -- new-char-adr
false \ -- char-adr any?
over c@ 98 = if true or then
over c@ 99 = if true or then
0= if drop false exit then
1+ \ -- new-char-adr
drop true ;
&
: <generate-pattern> { node -- }
s" false " evaluate
node .line @ count bounds do
s" over c@ " evaluate
I c@ lit,
s" = if true or then " evaluate
loop
s" 0= if drop false exit then 1+ " evaluate ;
: generate-pattern ( any-seq -- xt )
>r
s" :noname ( char-adr -- match? ) " evaluate
r> ['] <generate-pattern> each
s" drop true ; " evaluate ;
\ ******
\ ****** upgrade pattern-seq
\ ******
seq \ .LINE starts out as pattern-str, later gets changed to result-str
w field .any \ pointer to any-seq
w field .xt \ xt of generated pattern matcher
w field .matches \ count of matches for this pattern
constant pattern
: <kill-pattern> ( node -- )
dup .any @ kill-seq
<kill-seq> ;
: kill-pattern ( head -- )
each[ <kill-pattern> ]each ;
: init-pattern ( pattern-str node -- node )
init-seq >r
r@ .line @ make-any-seq r@ .any !
r@ .any @ generate-pattern r@ .xt !
0 r@ .matches !
r> ;
: new-pattern ( str -- node )
pattern alloc
init-pattern ;
: upgrade-pattern ( pattern-seq -- pattern-list ) \ create a PATTERN list given a SEQ list
nil swap \ -- pattern-list pattern-seq
each[ .line @ new-pattern link ]each ;
\ ******
\ ****** pattern-match
\ ******
: <check-word> ( pattern-list-node word-seq-node -- )
.line @ count drop \ -- pattern-list-node char-adr \ assume str size is correct
over .xt @ execute \ -- pattern-list-node match?
if 1 over .matches +! then ; \ -- pattern-list-node
: <check-pattern> ( word-seq pattern-list-node -- word-seq )
over ['] <check-word> each \ -- word-seq pattern-list-node
drop ;
: check-pattern ( word-seq pattern-list -- )
['] <check-pattern> each \ -- word-seq
drop ;
\ ******
\ ****** make result strings
\ ******
: u>str ( u -- adr cnt )
u>d <# #s #> ;
: <fill-result> ( pattern# pattern-list-node -- new-pattern# )
dup .line @ dealloc \ get rid of pattern-str in .LINE
<cstr
c" Case #" +cstr
over u>str <+cstr>
c" : " +cstr
dup .matches @ u>str <+cstr>
cstr> hstr swap .line ! \ -- pattern# \ set result-str to .LINE
1+ ; \ -- new-pattern#
: fill-result ( pattern-list -- )
1 swap ['] <fill-result> each \ -- pattern#
drop ;
\ ******
\ ****** main program
\ ******
: alien ( name-str -- )
dup seqs { name-str word-seq pattern-seq | pattern-list -- }
s" marker upgrade-pattern-stuff " evaluate \ so we can get rid of the UPGRADE-PATTERN words
pattern-seq upgrade-pattern to pattern-list
word-seq pattern-list check-pattern
pattern-list fill-result
pattern-list name-str dump-result
\ clean up
word-seq kill-seq
pattern-seq kill-seq
pattern-list kill-pattern
s" upgrade-pattern-stuff " evaluate ;
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-04-22 02:19 +0200 |
| Message-ID | <jmvirb$qdo$1@online.de> |
| In reply to | #11508 |
hughaguilar96@yahoo.com wrote: > It seems extremely unlikely that any Forther is going to come up with > a Forth program to compete against mine. Probably. This is a task screaming for a language where regexps are already implemented in a very similar form used in the quest data. I.e. you replace the ( with a [ and then use the regexp comparison operation, and be almost done. It *is* an 8 minute task. I wouldn't use Forth for that. And I even have a regexp package for my Forths, which makes it actually easier than using your novice package, but still not as easy as with awk or Perl or Python or whatever regexp- based language of the year you want to use for that (you could do it with the shell and grep and tr). Well, maybe I really should invest the time to add a Perl- or Python-compatible regexp compiler as frontend, because *then*, it is just as easy as with the competition. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | "WJ" <w_a_x_man@yahoo.com> |
|---|---|
| Date | 2012-04-22 04:03 +0000 |
| Message-ID | <jmvvul02moh@enews4.newsguy.com> |
| In reply to | #11508 |
hughaguilar96@yahoo.com wrote:
> On Thursday, April 12, 2012 1:43:19 AM UTC-6, Hugh Aguilar wrote:
> > Just for fun, lets have our own comp.lang.forth contest to write the
> > best Forth solution to the "alien language" problem.
> > http://code.google.com/codejam/contest/90101/dashboard#s=p0
> > This will be a loser's consolation contest, as none of us have any
> > chance at the real contest.
>
> I've waited and waited, but nobody has come forward. To qualify for the CodeJam contest, the program had to be written in under 8 minutes. That is very fast programming; I think that a typical programmer using a modern language would take about 1/2 hour. My own Forth program took me about 3 hours, so I am 6 times slower than pretty much everybody. This is a big part of why Forth is not used in the work world. No employer is going to pay anybody to program in Forth when it takes 6 times longer to write a program than it does in any other language. Also, I had the advantage of having my novice package available. Without the novice package, I think most Forth programmers would take maybe 3 days to write a program like this (that is why nobody responded to my challenge).
>
> It seems extremely unlikely that any Forther is going to come up with a Forth program to compete against mine. I would like to see programmers of other languages, such as Lisp and Ruby and so forth, present their own programs along with a mention of how much time was required. It is okay to post non-Forth code on comp.lang.forth --- nobody is posting Forth code --- if we are going to get any code posted, it will have to be in other languages.
>
> Here is my own Forth code:
>
> \ This is the solution to the "alien language" example problem from Google CodeJam.
> \ http://code.google.com/codejam/contest/90101/dashboard#s=p0
>
> \ Written by Hugh Aguilar --- copyright (c) 2012 --- BSD license
>
> \ requires novice.4th and list.4th
>
> marker alien.4th
>
>
> \ ******
> \ ****** input and output
> \ ******
>
> variable #letters
> variable #words
> variable #patterns
>
> : seqs ( name-str -- word-seq pattern-seq )
> read-seq
> dup .line @ count evaluate
> #patterns ! #words ! #letters !
> .fore @ \ -- word-seq
> dup #words @ nth \ -- word-seq pattern-seq
> delink
> dup #patterns @ nth \ -- word-seq pattern-seq extraneous-seq
> delink kill-seq \ -- word-seq pattern-seq
> \ error checking
> over length #words @ <> abort" *** bad word-seq ***"
> dup length #patterns @ <> abort" *** bad pattern-seq ***"
> over each[ .line @ c@ #letters @ <> abort" *** string in word-seq is wrong length ***" ]each ;
>
> : dump-result ( pattern-list name-str -- )
> <cstr +cstr c" .result" +cstr cstr> write-seq ;
>
>
> \ ******
> \ ****** convert pattern string into any-seq list
> \ ****** each node in the list represents one char in the target string
> \ ****** the .LINE string of each node contains all of the character that would match
> \ ******
>
> : check-any-str { pattern-str head -- }
> head length #letters @ <> if
> cr ." *** any-seq is the wrong length ***"
> cr pattern-str count type
> cr true abort" *** aborting ***
> then ;
>
> \ If CHECK-ANY-STR fails, this is usually because the pattern-str is longer than 255 characters and it got truncated.
> \ This happens in the file: A-large-practice.in
> \ I could upgrade the program to deal with this problem, but doing so would involve rewriting the SEQ code in LIST.4TH.
>
> : <make-any-seq> ( head str -- head )
> dup c@ if new-seq link \ str has characters in it
> else drop then ;
>
> : make-any-seq { pattern-str | group? -- any-seq }
> nil <cstr
> pattern-str count bounds ?do \ -- head
> group? if \ if inside of ( ) group
> I c@ [char] ) = if false to group? cstr> <make-any-seq> <cstr
> else I c@ char+cstr then
> else \ else outside of ( ) group
> I c@ [char] ( = if true to group?
> else I c@ char+cstr cstr> <make-any-seq> <cstr then
> then
> loop
> cstr> <make-any-seq>
> pattern-str over check-any-str ;
>
>
> \ ******
> \ ****** generate pattern matcher
> \ ******
>
> char & comment \ this is an example of what will get generated
>
> :noname ( char-adr -- match? ) \ this is for: a(bc)
>
> false \ -- char-adr any?
> over c@ 97 = if true or then
> 0= if drop false exit then
> 1+ \ -- new-char-adr
>
> false \ -- char-adr any?
> over c@ 98 = if true or then
> over c@ 99 = if true or then
> 0= if drop false exit then
> 1+ \ -- new-char-adr
>
> drop true ;
>
> &
>
> : <generate-pattern> { node -- }
> s" false " evaluate
> node .line @ count bounds do
> s" over c@ " evaluate
> I c@ lit,
> s" = if true or then " evaluate
> loop
> s" 0= if drop false exit then 1+ " evaluate ;
>
> : generate-pattern ( any-seq -- xt )
> >r
> s" :noname ( char-adr -- match? ) " evaluate
> r> ['] <generate-pattern> each
> s" drop true ; " evaluate ;
>
>
> \ ******
> \ ****** upgrade pattern-seq
> \ ******
>
> seq \ .LINE starts out as pattern-str, later gets changed to result-str
> w field .any \ pointer to any-seq
> w field .xt \ xt of generated pattern matcher
> w field .matches \ count of matches for this pattern
> constant pattern
>
> : <kill-pattern> ( node -- )
> dup .any @ kill-seq
> <kill-seq> ;
>
> : kill-pattern ( head -- )
> each[ <kill-pattern> ]each ;
>
> : init-pattern ( pattern-str node -- node )
> init-seq >r
> r@ .line @ make-any-seq r@ .any !
> r@ .any @ generate-pattern r@ .xt !
> 0 r@ .matches !
> r> ;
>
> : new-pattern ( str -- node )
> pattern alloc
> init-pattern ;
>
> : upgrade-pattern ( pattern-seq -- pattern-list ) \ create a PATTERN list given a SEQ list
> nil swap \ -- pattern-list pattern-seq
> each[ .line @ new-pattern link ]each ;
>
>
> \ ******
> \ ****** pattern-match
> \ ******
>
> : <check-word> ( pattern-list-node word-seq-node -- )
> .line @ count drop \ -- pattern-list-node char-adr \ assume str size is correct
> over .xt @ execute \ -- pattern-list-node match?
> if 1 over .matches +! then ; \ -- pattern-list-node
>
> : <check-pattern> ( word-seq pattern-list-node -- word-seq )
> over ['] <check-word> each \ -- word-seq pattern-list-node
> drop ;
>
> : check-pattern ( word-seq pattern-list -- )
> ['] <check-pattern> each \ -- word-seq
> drop ;
>
>
> \ ******
> \ ****** make result strings
> \ ******
>
> : u>str ( u -- adr cnt )
> u>d <# #s #> ;
>
> : <fill-result> ( pattern# pattern-list-node -- new-pattern# )
> dup .line @ dealloc \ get rid of pattern-str in .LINE
> <cstr
> c" Case #" +cstr
> over u>str <+cstr>
> c" : " +cstr
> dup .matches @ u>str <+cstr>
> cstr> hstr swap .line ! \ -- pattern# \ set result-str to .LINE
> 1+ ; \ -- new-pattern#
>
> : fill-result ( pattern-list -- )
> 1 swap ['] <fill-result> each \ -- pattern#
> drop ;
>
>
> \ ******
> \ ****** main program
> \ ******
>
> : alien ( name-str -- )
> dup seqs { name-str word-seq pattern-seq | pattern-list -- }
> s" marker upgrade-pattern-stuff " evaluate \ so we can get rid of the UPGRADE-PATTERN words
> pattern-seq upgrade-pattern to pattern-list
> word-seq pattern-list check-pattern
> pattern-list fill-result
> pattern-list name-str dump-result
> \ clean up
> word-seq kill-seq
> pattern-seq kill-seq
> pattern-list kill-pattern
> s" upgrade-pattern-stuff " evaluate ;
>
Ruby:
_, numwords, numpatterns = gets().split.map{|s| s.to_i}
words = (1 .. numwords).map{ gets().strip }
patterns = (1 .. numpatterns).map{ gets().strip }
patterns.each_with_index{|pat,i|
regex = Regexp.new( pat.gsub("(", "[").gsub(")", "]") )
printf "Case #%d: %d\n", i, words.grep( regex ).size
}
[toc] | [prev] | [next] | [standalone]
| From | Hugh Aguilar <hughaguilar96@yahoo.com> |
|---|---|
| Date | 2012-04-22 23:08 -0700 |
| Message-ID | <ba86554e-753f-492b-bf6d-4b78bd92a6df@f27g2000yqc.googlegroups.com> |
| In reply to | #11518 |
On Apr 21, 10:03 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> hughaguila...@yahoo.com wrote:
> > On Thursday, April 12, 2012 1:43:19 AM UTC-6, Hugh Aguilar wrote:
> > > Just for fun, lets have our own comp.lang.forth contest to write the
> > > best Forth solution to the "alien language" problem.
> > >http://code.google.com/codejam/contest/90101/dashboard#s=p0
> > > This will be a loser's consolation contest, as none of us have any
> > > chance at the real contest.
>
> > I've waited and waited, but nobody has come forward. To qualify for the CodeJam contest, the program had to be written in under 8 minutes. That is very fast programming; I think that a typical programmer using a modern language would take about 1/2 hour. My own Forth program took me about 3 hours, so I am 6 times slower than pretty much everybody. This is a big part of why Forth is not used in the work world. No employer is going to pay anybody to program in Forth when it takes 6 times longer to write a program than it does in any other language. Also, I had the advantage of having my novice package available. Without the novice package, I think most Forth programmers would take maybe 3 days to write a program like this (that is why nobody responded to my challenge).
>
> > It seems extremely unlikely that any Forther is going to come up with a Forth program to compete against mine. I would like to see programmers of other languages, such as Lisp and Ruby and so forth, present their own programs along with a mention of how much time was required. It is okay to post non-Forth code on comp.lang.forth --- nobody is posting Forth code --- if we are going to get any code posted, it will have to be in other languages.
>
> > Here is my own Forth code:
>
> > \ This is the solution to the "alien language" example problem from Google CodeJam.
> > \http://code.google.com/codejam/contest/90101/dashboard#s=p0
>
> > \ Written by Hugh Aguilar --- copyright (c) 2012 --- BSD license
>
> > \ requires novice.4th and list.4th
>
> > marker alien.4th
>
> > \ ******
> > \ ****** input and output
> > \ ******
>
> > variable #letters
> > variable #words
> > variable #patterns
>
> > : seqs ( name-str -- word-seq pattern-seq )
> > read-seq
> > dup .line @ count evaluate
> > #patterns ! #words ! #letters !
> > .fore @ \ -- word-seq
> > dup #words @ nth \ -- word-seq pattern-seq
> > delink
> > dup #patterns @ nth \ -- word-seq pattern-seq extraneous-seq
> > delink kill-seq \ -- word-seq pattern-seq
> > \ error checking
> > over length #words @ <> abort" *** bad word-seq ***"
> > dup length #patterns @ <> abort" *** bad pattern-seq ***"
> > over each[ .line @ c@ #letters @ <> abort" *** string in word-seq is wrong length ***" ]each ;
>
> > : dump-result ( pattern-list name-str -- )
> > <cstr +cstr c" .result" +cstr cstr> write-seq ;
>
> > \ ******
> > \ ****** convert pattern string into any-seq list
> > \ ****** each node in the list represents one char in the target string
> > \ ****** the .LINE string of each node contains all of the character that would match
> > \ ******
>
> > : check-any-str { pattern-str head -- }
> > head length #letters @ <> if
> > cr ." *** any-seq is the wrong length ***"
> > cr pattern-str count type
> > cr true abort" *** aborting ***
> > then ;
>
> > \ If CHECK-ANY-STR fails, this is usually because the pattern-str is longer than 255 characters and it got truncated.
> > \ This happens in the file: A-large-practice.in
> > \ I could upgrade the program to deal with this problem, but doing so would involve rewriting the SEQ code in LIST.4TH.
>
> > : <make-any-seq> ( head str -- head )
> > dup c@ if new-seq link \ str has characters in it
> > else drop then ;
>
> > : make-any-seq { pattern-str | group? -- any-seq }
> > nil <cstr
> > pattern-str count bounds ?do \ -- head
> > group? if \ if inside of ( ) group
> > I c@ [char] ) = if false to group? cstr> <make-any-seq> <cstr
> > else I c@ char+cstr then
> > else \ else outside of ( ) group
> > I c@ [char] ( = if true to group?
> > else I c@ char+cstr cstr> <make-any-seq> <cstr then
> > then
> > loop
> > cstr> <make-any-seq>
> > pattern-str over check-any-str ;
>
> > \ ******
> > \ ****** generate pattern matcher
> > \ ******
>
> > char & comment \ this is an example of what will get generated
>
> > :noname ( char-adr -- match? ) \ this is for: a(bc)
>
> > false \ -- char-adr any?
> > over c@ 97 = if true or then
> > 0= if drop false exit then
> > 1+ \ -- new-char-adr
>
> > false \ -- char-adr any?
> > over c@ 98 = if true or then
> > over c@ 99 = if true or then
> > 0= if drop false exit then
> > 1+ \ -- new-char-adr
>
> > drop true ;
>
> > &
>
> > : <generate-pattern> { node -- }
> > s" false " evaluate
> > node .line @ count bounds do
> > s" over c@ " evaluate
> > I c@ lit,
> > s" = if true or then " evaluate
> > loop
> > s" 0= if drop false exit then 1+ " evaluate ;
>
> > : generate-pattern ( any-seq -- xt )
> > >r
> > s" :noname ( char-adr -- match? ) " evaluate
> > r> ['] <generate-pattern> each
> > s" drop true ; " evaluate ;
>
> > \ ******
> > \ ****** upgrade pattern-seq
> > \ ******
>
> > seq \ .LINE starts out as pattern-str, later gets changed to result-str
> > w field .any \ pointer to any-seq
> > w field .xt \ xt of generated pattern matcher
> > w field .matches \ count of matches for this pattern
> > constant pattern
>
> > : <kill-pattern> ( node -- )
> > dup .any @ kill-seq
> > <kill-seq> ;
>
> > : kill-pattern ( head -- )
> > each[ <kill-pattern> ]each ;
>
> > : init-pattern ( pattern-str node -- node )
> > init-seq >r
> > r@ .line @ make-any-seq r@ .any !
> > r@ .any @ generate-pattern r@ .xt !
> > 0 r@ .matches !
> > r> ;
>
> > : new-pattern ( str -- node )
> > pattern alloc
> > init-pattern ;
>
> > : upgrade-pattern ( pattern-seq -- pattern-list ) \ create a PATTERN list given a SEQ list
> > nil swap \ -- pattern-list pattern-seq
> > each[ .line @ new-pattern link ]each ;
>
> > \ ******
> > \ ****** pattern-match
> > \ ******
>
> > : <check-word> ( pattern-list-node word-seq-node -- )
> > .line @ count drop \ -- pattern-list-node char-adr \ assume str size is correct
> > over .xt @ execute \ -- pattern-list-node match?
> > if 1 over .matches +! then ; \ -- pattern-list-node
>
> > : <check-pattern> ( word-seq pattern-list-node -- word-seq )
> > over ['] <check-word> each \ -- word-seq pattern-list-node
> > drop ;
>
> > : check-pattern ( word-seq pattern-list -- )
> > ['] <check-pattern> each \ -- word-seq
> > drop ;
>
> > \ ******
> > \ ****** make result strings
> > \ ******
>
> > : u>str ( u -- adr cnt )
> > u>d <# #s #> ;
>
> > : <fill-result> ( pattern# pattern-list-node -- new-pattern# )
> > dup .line @ dealloc \ get rid of pattern-str in .LINE
> > <cstr
> > c" Case #" +cstr
> > over u>str <+cstr>
> > c" : " +cstr
> > dup .matches @ u>str <+cstr>
> > cstr> hstr swap .line ! \ -- pattern# \ set result-str to .LINE
> > 1+ ; \ -- new-pattern#
>
> > : fill-result ( pattern-list -- )
> > 1 swap ['] <fill-result> each \ -- pattern#
> > drop ;
>
> > \ ******
> > \ ****** main program
> > \ ******
>
> > : alien ( name-str -- )
> > dup seqs { name-str word-seq pattern-seq | pattern-list -- }
> > s" marker upgrade-pattern-stuff " evaluate \ so we can get rid of the UPGRADE-PATTERN words
> > pattern-seq upgrade-pattern to pattern-list
> > word-seq pattern-list check-pattern
> > pattern-list fill-result
> > pattern-list name-str dump-result
> > \ clean up
> > word-seq kill-seq
> > pattern-seq kill-seq
> > pattern-list kill-pattern
> > s" upgrade-pattern-stuff " evaluate ;
>
> Ruby:
>
> _, numwords, numpatterns = gets().split.map{|s| s.to_i}
>
> words = (1 .. numwords).map{ gets().strip }
> patterns = (1 .. numpatterns).map{ gets().strip }
>
> patterns.each_with_index{|pat,i|
> regex = Regexp.new( pat.gsub("(", "[").gsub(")", "]") )
> printf "Case #%d: %d\n", i, words.grep(...
>
> read more »
I don't know anything about Ruby, but I can certainly admire the
conciseness of your program. How does it compare in speed to mine?
[toc] | [prev] | [next] | [standalone]
| From | Hugh Aguilar <hughaguilar96@yahoo.com> |
|---|---|
| Date | 2012-04-22 23:17 -0700 |
| Message-ID | <526a220d-3748-486b-85cd-664a59b96748@p6g2000yqi.googlegroups.com> |
| In reply to | #11518 |
On Apr 21, 10:03 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> Ruby:
>
> _, numwords, numpatterns = gets().split.map{|s| s.to_i}
>
> words = (1 .. numwords).map{ gets().strip }
> patterns = (1 .. numpatterns).map{ gets().strip }
>
> patterns.each_with_index{|pat,i|
> regex = Regexp.new( pat.gsub("(", "[").gsub(")", "]") )
> printf "Case #%d: %d\n", i, words.grep(...
>
I don't know anything about Ruby, but I can certainly admire the
conciseness of your program. How does it compare in speed to mine?
[toc] | [prev] | [next] | [standalone]
| From | "WJ" <w_a_x_man@yahoo.com> |
|---|---|
| Date | 2012-04-23 19:27 +0000 |
| Message-ID | <jn4afr0pil@enews1.newsguy.com> |
| In reply to | #11540 |
Hugh Aguilar wrote:
> On Apr 21, 10:03 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> > Ruby:
> >
> > _, numwords, numpatterns = gets().split.map{|s| s.to_i}
> >
> > words = (1 .. numwords).map{ gets().strip }
> > patterns = (1 .. numpatterns).map{ gets().strip }
> >
> > patterns.each_with_index{|pat,i|
> > regex = Regexp.new( pat.gsub("(", "[").gsub(")", "]") )
> > printf "Case #%d: %d\n", i, words.grep(...
> >
>
> I don't know anything about Ruby, but I can certainly admire the
> conciseness of your program. How does it compare in speed to mine?
It takes 6.5 seconds for the large input file on my laptop.
The program is run this way:
ruby code-jam.rb Code-jam.in
I'll explain a few things.
_, numwords, numpatterns = gets().split.map{|s| s.to_i}
gets() reads a line from stdin or the file given on the
command-line; .split splits that string on whitespace,
yielding an array or list of strings;
.map works as in Lisp, in this case converting each string
in the array or list into an integer.
words = (1 .. numwords).map{ gets().strip }
(1 .. numwords) is a range; some examples of ranges
(the .to_a expands the range into an array or list):
(1 .. 5).to_a
==>[1, 2, 3, 4, 5]
("b" .. "f").to_a
==>["b", "c", "d", "e", "f"]
Here I'm simply using the range to read numwords lines
from the file. I could have done something like
words = []
numwords.times{ words << gets().strip }
.strip removes all whitespace from beginning and end
of the string.
patterns.each_with_index{|pat,i|
Iterating through the patterns; pat, of course, is
the pattern. i is assigned the index of the current
item, starting with 0 (which means my output has an
off-by-1 error).
printf "Case #%d: %d\n", i, words.grep( regex ).size
.grep works on an array or list of strings, selecting
only the items that match the regular expression.
[toc] | [prev] | [next] | [standalone]
| From | Hugh Aguilar <hughaguilar96@yahoo.com> |
|---|---|
| Date | 2012-04-23 22:08 -0700 |
| Message-ID | <ac31f7de-92be-4cd0-a902-ce5ecb2a4092@2g2000yqp.googlegroups.com> |
| In reply to | #11548 |
On Apr 23, 1:27 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> Hugh Aguilar wrote:
> > On Apr 21, 10:03 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> > > Ruby:
>
> > > _, numwords, numpatterns = gets().split.map{|s| s.to_i}
>
> > > words = (1 .. numwords).map{ gets().strip }
> > > patterns = (1 .. numpatterns).map{ gets().strip }
>
> > > patterns.each_with_index{|pat,i|
> > > regex = Regexp.new( pat.gsub("(", "[").gsub(")", "]") )
> > > printf "Case #%d: %d\n", i, words.grep(...
>
> > I don't know anything about Ruby, but I can certainly admire the
> > conciseness of your program. How does it compare in speed to mine?
>
> It takes 6.5 seconds for the large input file on my laptop.
>
> The program is run this way:
>
> ruby code-jam.rb Code-jam.in
>
> I'll explain a few things.
>
> _, numwords, numpatterns = gets().split.map{|s| s.to_i}
>
> gets() reads a line from stdin or the file given on the
> command-line; .split splits that string on whitespace,
> yielding an array or list of strings;
> .map works as in Lisp, in this case converting each string
> in the array or list into an integer.
>
> words = (1 .. numwords).map{ gets().strip }
>
> (1 .. numwords) is a range; some examples of ranges
> (the .to_a expands the range into an array or list):
> (1 .. 5).to_a
> ==>[1, 2, 3, 4, 5]
> ("b" .. "f").to_a
> ==>["b", "c", "d", "e", "f"]
> Here I'm simply using the range to read numwords lines
> from the file. I could have done something like
> words = []
> numwords.times{ words << gets().strip }
> .strip removes all whitespace from beginning and end
> of the string.
>
> patterns.each_with_index{|pat,i|
>
> Iterating through the patterns; pat, of course, is
> the pattern. i is assigned the index of the current
> item, starting with 0 (which means my output has an
> off-by-1 error).
>
> printf "Case #%d: %d\n", i, words.grep( regex ).size
>
> .grep works on an array or list of strings, selecting
> only the items that match the regular expression.
Ruby is pretty impressive; I should learn more about it. BTW, do you
know Icon?
As I've said before, my Straight Forth will only be for micro-
controllers. I will have a "sister language" that will be used for
desktop-computer programs that are related in some way to the micro-
controller programs. I had been planning on Racket, but maybe I should
consider Ruby instead. Ruby is a lot more popular, although I think
that Racket has more novice-oriented documentation (a good thing, as
most micro-controller enthusiasts are more interested in hardware than
in software; they don't want to learn something complicated even if it
is more powerful, especially for desktop-computer programming which is
only peripherally related to micro-controllers).
Over on comp.lang.lisp, I've heard Ruby described as "Matz-Lisp" ---
meaning that Ruby is just Lisp with a more friendly syntax (for people
accustomed to infix). Would you consider that to be an accurate
description of Ruby?
[toc] | [prev] | [next] | [standalone]
| From | "WJ" <w_a_x_man@yahoo.com> |
|---|---|
| Date | 2012-04-24 08:30 +0000 |
| Message-ID | <jn5obq01o0m@enews1.newsguy.com> |
| In reply to | #11554 |
Hugh Aguilar wrote:
> On Apr 23, 1:27 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> > Hugh Aguilar wrote:
> > > On Apr 21, 10:03 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> > > > Ruby:
> >
> > > > _, numwords, numpatterns = gets().split.map{|s| s.to_i}
> >
> > > > words = (1 .. numwords).map{ gets().strip }
> > > > patterns = (1 .. numpatterns).map{ gets().strip }
> >
> > > > patterns.each_with_index{|pat,i|
> > > > regex = Regexp.new( pat.gsub("(", "[").gsub(")", "]") )
> > > > printf "Case #%d: %d\n", i, words.grep(...
> >
> > > I don't know anything about Ruby, but I can certainly admire the
> > > conciseness of your program. How does it compare in speed to mine?
> >
> > It takes 6.5 seconds for the large input file on my laptop.
> >
> > The program is run this way:
> >
> > ruby code-jam.rb Code-jam.in
> >
> > I'll explain a few things.
> >
> > _, numwords, numpatterns = gets().split.map{|s| s.to_i}
> >
> > gets() reads a line from stdin or the file given on the
> > command-line; .split splits that string on whitespace,
> > yielding an array or list of strings;
> > .map works as in Lisp, in this case converting each string
> > in the array or list into an integer.
> >
> > words = (1 .. numwords).map{ gets().strip }
> >
> > (1 .. numwords) is a range; some examples of ranges
> > (the .to_a expands the range into an array or list):
> > (1 .. 5).to_a
> > ==>[1, 2, 3, 4, 5]
> > ("b" .. "f").to_a
> > ==>["b", "c", "d", "e", "f"]
> > Here I'm simply using the range to read numwords lines
> > from the file. I could have done something like
> > words = []
> > numwords.times{ words << gets().strip }
> > .strip removes all whitespace from beginning and end
> > of the string.
> >
> > patterns.each_with_index{|pat,i|
> >
> > Iterating through the patterns; pat, of course, is
> > the pattern. i is assigned the index of the current
> > item, starting with 0 (which means my output has an
> > off-by-1 error).
> >
> > printf "Case #%d: %d\n", i, words.grep( regex ).size
> >
> > .grep works on an array or list of strings, selecting
> > only the items that match the regular expression.
>
> Ruby is pretty impressive; I should learn more about it. BTW, do you
> know Icon?
Years ago, Icon was my favorite language. (I have the book by Griswold
& Griswold.) Then I switched to Ruby.
>
> As I've said before, my Straight Forth will only be for micro-
> controllers. I will have a "sister language" that will be used for
> desktop-computer programs that are related in some way to the micro-
> controller programs. I had been planning on Racket, but maybe I should
> consider Ruby instead.
I'm trying to learn some Racket, too.
Ruby lacks 2 things (compared to Racket):
1. High-speed looping. (Don't try to generate the Mandelbrot Set
with it.) Most of the other "scripting" languages are faster
than Ruby, I believe.
2. Macros.
> Ruby is a lot more popular,
I wonder which language would have more users if one didn't count
those who just use Ruby to power web sites (Ruby on Rails, etc.).
> although I think
> that Racket has more novice-oriented documentation (a good thing, as
> most micro-controller enthusiasts are more interested in hardware than
> in software; they don't want to learn something complicated even if it
> is more powerful, especially for desktop-computer programming which is
> only peripherally related to micro-controllers).
When people like that learn Ruby, they should skip the advanced
object-oriented features, as I did. I basically use Ruby as one
would use Perl, Awk, Lua, Python, or Scheme. I very seldom create
a new class; I just write some functions. Ruby on Rails is Greek
to me.
>
> Over on comp.lang.lisp, I've heard Ruby described as "Matz-Lisp" ---
> meaning that Ruby is just Lisp with a more friendly syntax (for people
> accustomed to infix). Would you consider that to be an accurate
> description of Ruby?
Perhaps. The creator of Ruby wrote this:
* Ruby is a language designed in the following steps:
* take a simple lisp language (like one prior to CL).
* remove macros, s-expression.
* add simple object system (much simpler than CLOS).
* add blocks, inspired by higher order functions.
* add methods found in Smalltalk.
* add functionality found in Perl (in OO way).
So, Ruby was a Lisp originally, in theory.
Let's call it MatzLisp from now on. ;-)
matz.
Paul Graham, the Lisp guru, has advised those who cannot
use Lisp at work to see if they can use Ruby, which he
considers somewhat Lisp-like.
No matter how many other languages I dabble in, I'll probably
keep using Ruby for many things. It often makes programming
so easy that it's almost boring.
[toc] | [prev] | [next] | [standalone]
| From | Hugh Aguilar <hughaguilar96@yahoo.com> |
|---|---|
| Date | 2012-04-24 23:00 -0700 |
| Message-ID | <beaac66f-092f-4e0e-abe0-36c4b40656e1@f37g2000yqc.googlegroups.com> |
| In reply to | #11561 |
On Apr 24, 2:30 am, "WJ" <w_a_x_...@yahoo.com> wrote: > No matter how many other languages I dabble in, I'll probably > keep using Ruby for many things. It often makes programming > so easy that it's almost boring. That sounds like a good thing to me. This alien.4th program was fun, but it was also a lot more complicated and time-consuming than it would have been in any other language. I'd rather have a language in which programming is boring --- this is especially true in a workplace --- it is too stressful to risk getting fired every day, because every program assigned to me is a challenge that I may or may not succeed at. Now I discover that my alien.4th program crashes Gforth --- I wouldn't want to have to deal with a mess like that in a workplace with my boss breathing down my neck. I would rather have a language that never crashed and that allowed me to write programs in a matter of minutes --- then my only worry would be that the boss wouldn't catch me goofing off on the internet during work hours. ;-) BTW, have you tried Python? What do you think of it as compared to Ruby? Rails is Ruby's killer app. There are some web frameworks in Python, but they aren't nearly as popular as Rails. Python doesn't have any killer app, but Python is more popular for general-purpose scripting than Ruby is. Python is what Qbasic used to be --- the easy language that everybody learns, but which isn't taken very seriously among professionals. That is my impression anyway.
[toc] | [prev] | [next] | [standalone]
| From | "WJ" <w_a_x_man@yahoo.com> |
|---|---|
| Date | 2012-04-26 09:19 +0000 |
| Message-ID | <jnb3u701rmd@enews4.newsguy.com> |
| In reply to | #11595 |
Hugh Aguilar wrote: > On Apr 24, 2:30 am, "WJ" <w_a_x_...@yahoo.com> wrote: > > No matter how many other languages I dabble in, I'll probably > > keep using Ruby for many things. It often makes programming > > so easy that it's almost boring. > > That sounds like a good thing to me. This alien.4th program was fun, > but it was also a lot more complicated and time-consuming than it > would have been in any other language. I'd rather have a language in > which programming is boring --- this is especially true in a workplace > --- it is too stressful to risk getting fired every day, because every > program assigned to me is a challenge that I may or may not succeed > at. Now I discover that my alien.4th program crashes Gforth --- I > wouldn't want to have to deal with a mess like that in a workplace > with my boss breathing down my neck. I would rather have a language > that never crashed and that allowed me to write programs in a matter > of minutes --- then my only worry would be that the boss wouldn't > catch me goofing off on the internet during work hours. ;-) > > BTW, have you tried Python? What do you think of it as compared to > Ruby? I have barely looked at Python. The significance of indentation doesn't appeal to me. Also repellent is the fact that the language tries to allow you to do a thing only one way: Guido's way. His tyrannical attitude inspired this revision of Stephen Crane's poem "Think as I Think": Code as I Code "Code as I code," said Guido, "Or you are abominably wicked; "You are a toad." And after I had thought of it, I said: "I will, then, be a toad." (Off topic) Another Crane poem that has never been more apropos than it is today: The wayfarer Perceiving the pathway to truth Was struck with astonishment. It was thickly grown with weeds. ``Ha,'' he said, ``I see that none has passed here In a long time.'' Later he saw that each weed Was a singular knife. ``Well,'' he mumbled at last, ``Doubtless there are other roads.''
[toc] | [prev] | [next] | [standalone]
| From | Hugh Aguilar <hughaguilar96@yahoo.com> |
|---|---|
| Date | 2012-04-26 03:17 -0700 |
| Message-ID | <0a232bee-ef7c-43b3-8de6-c924ae9e4495@v22g2000yqm.googlegroups.com> |
| In reply to | #11644 |
On Apr 26, 3:19 am, "WJ" <w_a_x_...@yahoo.com> wrote: > Hugh Aguilar wrote: > > On Apr 24, 2:30 am, "WJ" <w_a_x_...@yahoo.com> wrote: > > > No matter how many other languages I dabble in, I'll probably > > > keep using Ruby for many things. It often makes programming > > > so easy that it's almost boring. > > > That sounds like a good thing to me. This alien.4th program was fun, > > but it was also a lot more complicated and time-consuming than it > > would have been in any other language. I'd rather have a language in > > which programming is boring --- this is especially true in a workplace > > --- it is too stressful to risk getting fired every day, because every > > program assigned to me is a challenge that I may or may not succeed > > at. Now I discover that my alien.4th program crashes Gforth --- I > > wouldn't want to have to deal with a mess like that in a workplace > > with my boss breathing down my neck. I would rather have a language > > that never crashed and that allowed me to write programs in a matter > > of minutes --- then my only worry would be that the boss wouldn't > > catch me goofing off on the internet during work hours. ;-) > > > BTW, have you tried Python? What do you think of it as compared to > > Ruby? > > I have barely looked at Python. The significance of indentation > doesn't appeal to me. Also repellent is the fact that the language > tries to allow you to do a thing only one way: Guido's way. > His tyrannical attitude inspired this revision of Stephen Crane's > poem "Think as I Think": > > Code as I Code > > "Code as I code," said Guido, > "Or you are abominably wicked; > "You are a toad." > > And after I had thought of it, > I said: "I will, then, be a toad." > > (Off topic) > Another Crane poem that has never been more apropos than it is > today: > > The wayfarer > Perceiving the pathway to truth > Was struck with astonishment. > It was thickly grown with weeds. > ``Ha,'' he said, > ``I see that none has passed here > In a long time.'' > Later he saw that each weed > Was a singular knife. > ``Well,'' he mumbled at last, > ``Doubtless there are other roads.'' I agree that being Pythonic isn't a much of a goal to aspire to. On the other hand though, Python has become so common that it is worth being familiar with. What do you think of Lua? I never heard of Stephen Crane and had to google him. His poems were pretty good from what I read. I'm a fan of Alexander Pope myself. This is one of my favorites, and very apropos for comp.lang.forth: The coxcomb bird, so talkative and grave, That from his cage, cries Cuckold, Whore and Knave, Though many a passenger he rightly call, You hold him no philosopher at all.
[toc] | [prev] | [next] | [standalone]
| From | vandys@vsta.org |
|---|---|
| Date | 2012-04-26 16:45 +0000 |
| Message-ID | <9vtcdeFd1rU1@mid.individual.net> |
| In reply to | #11644 |
WJ <w_a_x_man@yahoo.com> wrote:
> I have barely looked at Python. The significance of indentation
> doesn't appeal to me. Also repellent is the fact that the language
> tries to allow you to do a thing only one way: Guido's way.
Having coded heavily in C, Forth, and Python, I can say that the indentation
approach has not turned out to be a big deal. And although Guido is, in
fact, "Benevolent Dictator for Life", his guidance has evolved Python into a
very effective language. I suggest you move beyond "barely looking" before
reaching a conclusion on the language.
One of my most recent "aha" moments was this code for doing breadth traversal
of collections:
def breadthfirst(tree, children=iter):
yield tree
last = tree
for node in breadthfirst(tree, children):
for child in children(node):
yield child
last = child
if last == node:
return
It's used as:
for member in breadthfirst(aCollection):
...
And "member" gets first the things at the top, then things one level down,
and so forth. It works generically across any collection.
Although the language does not have, as such, lazy evaluation semantics, this
function uses generators to get that effect. I'm not sure I've seen a more
elegant breadth-first traversal in any language, and I don't know that
there's any other language which could use this implementation technique.
I really hope that, some day, a next generation Forth will marry its elegance
to semantics as powerful as these.
--
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-04-26 10:47 -0700 |
| Message-ID | <7xlilitmg8.fsf@ruckus.brouhaha.com> |
| In reply to | #11657 |
vandys@vsta.org writes: > Having coded heavily in C, Forth, and Python, I can say that the indentation > approach has not turned out to be a big deal. I agree with this. "One and only one way" just means Python tries to avoid creating multiple syntaxes or libraries to do the same thing. The general feeling of programming Python is sort of like Lisp. There are still lots of styles you can use. I haven't used Ruby in part because from what I can tell, it's similar enough to Python that I wouldn't really gain anything new from it. > def breadthfirst(tree, children=iter): > yield tree > last = tree ... > Although the language does not have, as such, lazy evaluation semantics, this > function uses generators to get that effect. I'm not sure I've seen a more > elegant breadth-first traversal in any language, and I don't know that > there's any other language which could use this implementation technique. I actually find that code pretty confusing, and I can't tell quite what it's supposed to do. I suspect it would be simpler in Haskell. You could also look at Lua coroutines. > I really hope that, some day, a next generation Forth will marry its > elegance to semantics as powerful as these. Perhaps: http://factorcode.org/ But, I think Forth itself is intended to be quite low-level.
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-04-27 02:26 -0700 |
| Message-ID | <7xmx5xttjj.fsf@ruckus.brouhaha.com> |
| In reply to | #11657 |
vandys@vsta.org writes:
> def breadthfirst(tree, children=iter):
> yield tree
> last = tree
> for node in breadthfirst(tree, children):
> for child in children(node):
> yield child
> last = child
> if last == node:
> return
Maybe that could be written something like (untested):
from itertools import chain
def breadthfirst(tree, children=iter):
def t(fifo):
n1 = list(islice(fifo,1))
return chain(n1,fifo,children(n1) if n1 else [])
return t([tree])
That's the more traditional way to do it. It's prettier in Haskell, IMO:
data Tree a = Tree {value :: a, children :: [Tree a] }
breadthFirst t = bf1 [t] where
bf1 [] = []
bf1 (x:xs) = value x : bf1 (xs ++ children x)
[toc] | [prev] | [next] | [standalone]
| From | vandys@vsta.org |
|---|---|
| Date | 2012-04-27 16:37 +0000 |
| Message-ID | <a000alF8vsU1@mid.individual.net> |
| In reply to | #11673 |
Paul Rubin <no.email@nospam.invalid> wrote:
> Maybe that could be written something like (untested):
> from itertools import chain
> def breadthfirst(tree, children=iter):
> def t(fifo):
> n1 = list(islice(fifo,1))
> return chain(n1,fifo,children(n1) if n1 else [])
> return t([tree])
No, even fixing errors (islice is also from itertools) it's not right.
I don't think itertools.chain is giving you the semantics you want.
> That's the more traditional way to do it. It's prettier in Haskell, IMO:
>
> data Tree a = Tree {value :: a, children :: [Tree a] }
>
> breadthFirst t = bf1 [t] where
> bf1 [] = []
> bf1 (x:xs) = value x : bf1 (xs ++ children x)
My (uninformed--I don't know Haskell) reading sees this as a depth-first
traversal. How does it achieve breadth-first semantics?
--
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-04-27 10:17 -0700 |
| Message-ID | <7x4ns55c1t.fsf@ruckus.brouhaha.com> |
| In reply to | #11691 |
vandys@vsta.org writes:
>> data Tree a = Tree {value :: a, children :: [Tree a] }
>>
>> breadthFirst t = bf1 [t] where
>> bf1 [] = []
>> bf1 (x:xs) = value x : bf1 (xs ++ children x)
>
> My (uninformed--I don't know Haskell) reading sees this as a depth-first
> traversal. How does it achieve breadth-first semantics?
The data declaration says that a tree has a value and a list of
subtrees. I'm not sure if that's what your original Python code did,
but I'll assume it is.
The usual way to do breadth-first traversal of a tree is:
1. Put the tree onto a FIFO queue (so the queue starts with one element)
2. Iterate over the queue like this:
while (queue is not empty):
t <- pop first tree from queue
yield (value associated with root of t)
append all children of root of t to the queue
Maybe I got too clever with itertools.chain in my python example, and
should have used collections.deque instead. Anyway, the code
breadthFirst t = bf1 [t] where
bf1 [] = []
bf1 (x:xs) = value x : bf1 (xs ++ children x)
says "breadthFirst t" calls a helper function bf1 on a list [t], i.e. a
one-element list containing t, like in Python. bf1 is defined
internally to breadthFirst with the "where" clause, but it could have
been written as a separate top-level function.
bf1 returns immediately if given an empty list. If given a nonempty
list, it splits it into the first element (x), and the rest (xs). It
then returns a new list containing the value from x, followed by what
comes from recursively calling bf1 on the result of appending x's
children to the original fifo. ++ concatenates two lists together.
This is all done with lazy evaluation (Haskell uses lazy evaluation for
everything), and the recursive call to bf1 is in tail position so you
shouldn't get a lot of list bloat or stack buildup if you're going to
just iterate through the traversal and do something with each element.
Also, ++ is lazy (like itertools.chain) so it doesn't go and traverse
the two lists and allocate storage for a new one each time you call it.
For depth-first, you just process in LIFO instead of FIFO order:
depthFirst t = df1 [t] where
df1 [] = []
df1 (x:xs) = value x : df1 (children x ++ xs)
Example (*Main> is ghci's interactive prompt):
*Main> let x = Tree 1 [Tree 2 [Tree 3 []], Tree 4 []]
*Main> breadthFirst x
[1,2,4,3]
*Main> depthFirst x
[1,2,3,4]
It is of course possible that I missed something and am doing stuff in
the wrong order, or that the code has some efficiency problem that could
be avoided some simple way. I'm nowhere near Haskell guru level.
[toc] | [prev] | [next] | [standalone]
| From | vandys@vsta.org |
|---|---|
| Date | 2012-04-27 18:15 +0000 |
| Message-ID | <a00615FordU1@mid.individual.net> |
| In reply to | #11693 |
Paul Rubin <no.email@nospam.invalid> wrote: > ... > It is of course possible that I missed something and am doing stuff in > the wrong order, or that the code has some efficiency problem that could > be avoided some simple way. I'm nowhere near Haskell guru level. Thank you! -- Andy Valencia Home page: http://www.vsta.org/andy/ To contact me: http://www.vsta.org/contact/andy.html
[toc] | [prev] | [next] | [standalone]
| From | Rugxulo <rugxulo@gmail.com> |
|---|---|
| Date | 2012-04-26 16:00 -0700 |
| Message-ID | <3312229f-a93a-4d46-b7a2-ebb13a32b4db@c4g2000yqj.googlegroups.com> |
| In reply to | #11548 |
Hi,
On Apr 23, 2:27 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> Hugh Aguilar wrote:
> > On Apr 21, 10:03 pm, "WJ" <w_a_x_...@yahoo.com> wrote:
> > > Ruby:
>
> > > _, numwords, numpatterns = gets().split.map{|s| s.to_i}
>
> > > words = (1 .. numwords).map{ gets().strip }
> > > patterns = (1 .. numpatterns).map{ gets().strip }
>
> > > patterns.each_with_index{|pat,i|
> > > regex = Regexp.new( pat.gsub("(", "[").gsub(")", "]") )
> > > printf "Case #%d: %d\n", i, words.grep(...
>
> > I don't know anything about Ruby, but I can certainly admire the
> > conciseness of your program. How does it compare in speed to mine?
>
> It takes 6.5 seconds for the large input file on my laptop.
>
> The program is run this way:
>
> ruby code-jam.rb Code-jam.in
This may or may not be interesting to you (Ruby 1.8.7 pl352), just
comparing to itself on this one x86 machine:
= Lucid Puppy Linux: time ruby code-jam.rb Code-jam.in > linux.out
(3.7 s.)
= DJGPP build atop DOSEMU: redir -t ruby code-jam.rb Code-jam.in >
djgpp-a.out (4.2 s.)
= DJGPP build atop DOSEMU: redir -t miniruby code-jam.rb Code-jam.in >
djgpp-b.out (2.8 s.)
So timings for one version of Ruby (or any language) depend on various
things, even on the same exact machine, so take such measurements with
a big grain of salt.
[toc] | [prev] | [next] | [standalone]
Page 1 of 4 [1] 2 3 4 Next page →
Back to top | Article view | comp.lang.forth
csiph-web