Google CodeJam?

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?

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

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.

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.

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

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?

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).

awegel@arcor.de (Alex Wegel) writes:
> 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).

I think the Forth spirit is "solve the problem you have". The 32-bit
representation is just fine for the problem as stated.

> 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?).

And if there were a million patterns to check instead of 500, you would
have wanted a totally different structure such as a decision tree, if
you cared about speed. Similarly the aliens might skip over 65 chars
and go directly to Unicode (Aliencode?) so again you'd need a totally
different approach. That's ok too.

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.

On 21/04/2012 23:13, yahoo.com">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/conte...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.
>

Yet another solution using simple character comparisons. Not a robust
solution as it expects perfectly formatted data, which is OK for the two
test files. Just stick the word alien as the first line of a test file
and include it.

0 value L 0 value D 0 value N
variable awords

: next-line ( -- ) refill 0= if cr ." Finished" cr quit then ;
: get-LDN ( -- ) next-line source evaluate to N to D to L ;
: load-words ( -- )
here awords !
D 0 do next-line source here over chars allot swap cmove loop
;

\ Match alternatives inside parentheses, ca points to a ( character
\ Returns ca2 which points to a ) character

: match-alts ( ch ca -- ca2 f ) \ f is true for a match
begin
char+ 2dup c@ dup [char] ) <> ( -- ch ca' ch ch2 f )
while
=
until
nip 1000 s" )" search nip \ match, skip to closing )
else
2drop nip 0 \ no match
then
;

\ ca1 is test case, ca2 is word of length L
\ returns 1 for a match else 0
: match-word ( ca1 ca2 -- 0|1 )
L chars over + swap
do ( -- ca1 )
dup c@ dup [char] ( <>
if
i c@ <> if 0= leave then
else
drop i c@ swap match-alts 0= if 0= leave then
then
char+ 1 chars
+loop
0<> negate
;

: match-all-words ( ca -- n )
0 awords @ D L chars * over + swap
do ( -- ca n )
over i match-word + ( -- ca n' )
L chars
+loop nip
;

: .case ( n i -- ) cr ." Case #" 0 .r ." : " . ;

: match-all-cases ( -- n )
N 1+ 1
do next-line source drop match-all-words i .case loop
;

: alien
cr get-LDN
load-words
match-all-cases
next-line
;

Results for the large file - do others agree?
\ -----------------
Case #1: 0
Case #2: 1
Case #3: 0
Case #4: 1
Case #5: 577
Case #6: 577
Case #7: 1
Case #8: 384
Case #9: 1
Case #10: 375
Case #11: 0
Case #12: 1
Case #13: 0
Case #14: 1
Case #15: 264
Case #16: 457
Case #17: 1
Case #18: 378
Case #19: 1
Case #20: 478
Case #21: 0
Case #22: 1
Case #23: 0
Case #24: 1
Case #25: 537
Case #26: 419
Case #27: 1
Case #28: 499
Case #29: 1
Case #30: 483
Case #31: 0
Case #32: 1
Case #33: 0
Case #34: 1
Case #35: 388
Case #36: 720
Case #37: 1
Case #38: 280
Case #39: 1
Case #40: 546
Case #41: 0
Case #42: 1
Case #43: 0
Case #44: 1
Case #45: 561
Case #46: 666
Case #47: 1
Case #48: 501
Case #49: 1
Case #50: 533
Case #51: 0
Case #52: 1
Case #53: 0
Case #54: 1
Case #55: 522
Case #56: 517
Case #57: 1
Case #58: 690
Case #59: 1
Case #60: 494
Case #61: 0
Case #62: 1
Case #63: 0
Case #64: 1
Case #65: 548
Case #66: 533
Case #67: 1
Case #68: 555
Case #69: 1
Case #70: 643
Case #71: 0
Case #72: 1
Case #73: 0
Case #74: 1
Case #75: 763
Case #76: 637
Case #77: 1
Case #78: 367
Case #79: 1
Case #80: 801
Case #81: 0
Case #82: 1
Case #83: 0
Case #84: 1
Case #85: 534
Case #86: 769
Case #87: 1
Case #88: 627
Case #89: 1
Case #90: 594
Case #91: 0
Case #92: 1
Case #93: 0
Case #94: 1
Case #95: 900
Case #96: 346
Case #97: 1
Case #98: 398
Case #99: 1
Case #100: 423
Case #101: 0
Case #102: 1
Case #103: 0
Case #104: 1
Case #105: 414
Case #106: 441
Case #107: 1
Case #108: 759
Case #109: 1
Case #110: 473
Case #111: 0
Case #112: 1
Case #113: 0
Case #114: 1
Case #115: 502
Case #116: 678
Case #117: 1
Case #118: 572
Case #119: 1
Case #120: 441
Case #121: 0
Case #122: 1
Case #123: 0
Case #124: 1
Case #125: 389
Case #126: 430
Case #127: 1
Case #128: 665
Case #129: 1
Case #130: 397
Case #131: 0
Case #132: 1
Case #133: 0
Case #134: 1
Case #135: 646
Case #136: 324
Case #137: 1
Case #138: 636
Case #139: 1
Case #140: 623
Case #141: 0
Case #142: 1
Case #143: 0
Case #144: 1
Case #145: 529
Case #146: 526
Case #147: 1
Case #148: 531
Case #149: 1
Case #150: 496
Case #151: 0
Case #152: 1
Case #153: 0
Case #154: 1
Case #155: 336
Case #156: 421
Case #157: 1
Case #158: 456
Case #159: 1
Case #160: 336
Case #161: 0
Case #162: 1
Case #163: 0
Case #164: 1
Case #165: 473
Case #166: 563
Case #167: 1
Case #168: 323
Case #169: 1
Case #170: 327
Case #171: 0
Case #172: 1
Case #173: 0
Case #174: 1
Case #175: 650
Case #176: 528
Case #177: 1
Case #178: 427
Case #179: 1
Case #180: 459
Case #181: 0
Case #182: 1
Case #183: 0
Case #184: 1
Case #185: 525
Case #186: 579
Case #187: 1
Case #188: 533
Case #189: 1
Case #190: 833
Case #191: 0
Case #192: 1
Case #193: 0
Case #194: 1
Case #195: 472
Case #196: 400
Case #197: 1
Case #198: 604
Case #199: 1
Case #200: 529
Case #201: 0
Case #202: 1
Case #203: 0
Case #204: 1
Case #205: 708
Case #206: 337
Case #207: 1
Case #208: 519
Case #209: 1
Case #210: 596
Case #211: 0
Case #212: 1
Case #213: 0
Case #214: 1
Case #215: 416
Case #216: 599
Case #217: 1
Case #218: 663
Case #219: 1
Case #220: 420
Case #221: 0
Case #222: 1
Case #223: 0
Case #224: 1
Case #225: 467
Case #226: 649
Case #227: 1
Case #228: 571
Case #229: 1
Case #230: 417
Case #231: 0
Case #232: 1
Case #233: 0
Case #234: 1
Case #235: 751
Case #236: 381
Case #237: 1
Case #238: 460
Case #239: 1
Case #240: 278
Case #241: 0
Case #242: 1
Case #243: 0
Case #244: 1
Case #245: 409
Case #246: 636
Case #247: 1
Case #248: 320
Case #249: 1
Case #250: 644
Case #251: 0
Case #252: 1
Case #253: 0
Case #254: 1
Case #255: 603
Case #256: 289
Case #257: 1
Case #258: 461
Case #259: 1
Case #260: 322
Case #261: 0
Case #262: 1
Case #263: 0
Case #264: 1
Case #265: 747
Case #266: 417
Case #267: 1
Case #268: 676
Case #269: 1
Case #270: 393
Case #271: 0
Case #272: 1
Case #273: 0
Case #274: 1
Case #275: 414
Case #276: 450
Case #277: 1
Case #278: 432
Case #279: 1
Case #280: 481
Case #281: 0
Case #282: 1
Case #283: 0
Case #284: 1
Case #285: 676
Case #286: 581
Case #287: 1
Case #288: 464
Case #289: 1
Case #290: 530
Case #291: 0
Case #292: 1
Case #293: 0
Case #294: 1
Case #295: 425
Case #296: 483
Case #297: 1
Case #298: 433
Case #299: 1
Case #300: 416
Case #301: 0
Case #302: 1
Case #303: 0
Case #304: 1
Case #305: 514
Case #306: 434
Case #307: 1
Case #308: 480
Case #309: 1
Case #310: 396
Case #311: 0
Case #312: 1
Case #313: 0
Case #314: 1
Case #315: 462
Case #316: 623
Case #317: 1
Case #318: 426
Case #319: 1
Case #320: 356
Case #321: 0
Case #322: 1
Case #323: 0
Case #324: 1
Case #325: 543
Case #326: 507
Case #327: 1
Case #328: 433
Case #329: 1
Case #330: 602
Case #331: 0
Case #332: 1
Case #333: 0
Case #334: 1
Case #335: 459
Case #336: 248
Case #337: 1
Case #338: 650
Case #339: 1
Case #340: 357
Case #341: 0
Case #342: 1
Case #343: 0
Case #344: 1
Case #345: 489
Case #346: 520
Case #347: 1
Case #348: 481
Case #349: 1
Case #350: 313
Case #351: 0
Case #352: 1
Case #353: 0
Case #354: 1
Case #355: 359
Case #356: 440
Case #357: 1
Case #358: 475
Case #359: 1
Case #360: 642
Case #361: 0
Case #362: 1
Case #363: 0
Case #364: 1
Case #365: 434
Case #366: 470
Case #367: 1
Case #368: 322
Case #369: 1
Case #370: 498
Case #371: 0
Case #372: 1
Case #373: 0
Case #374: 1
Case #375: 385
Case #376: 744
Case #377: 1
Case #378: 465
Case #379: 1
Case #380: 382
Case #381: 0
Case #382: 1
Case #383: 0
Case #384: 1
Case #385: 784
Case #386: 654
Case #387: 1
Case #388: 671
Case #389: 1
Case #390: 481
Case #391: 0
Case #392: 1
Case #393: 0
Case #394: 1
Case #395: 357
Case #396: 422
Case #397: 1
Case #398: 526
Case #399: 1
Case #400: 418
Case #401: 0
Case #402: 1
Case #403: 0
Case #404: 1
Case #405: 371
Case #406: 526
Case #407: 1
Case #408: 606
Case #409: 1
Case #410: 1045
Case #411: 0
Case #412: 1
Case #413: 0
Case #414: 1
Case #415: 495
Case #416: 496
Case #417: 1
Case #418: 540
Case #419: 1
Case #420: 506
Case #421: 0
Case #422: 1
Case #423: 0
Case #424: 1
Case #425: 372
Case #426: 601
Case #427: 1
Case #428: 575
Case #429: 1
Case #430: 450
Case #431: 0
Case #432: 1
Case #433: 0
Case #434: 1
Case #435: 450
Case #436: 507
Case #437: 1
Case #438: 589
Case #439: 1
Case #440: 390
Case #441: 0
Case #442: 1
Case #443: 0
Case #444: 1
Case #445: 441
Case #446: 447
Case #447: 1
Case #448: 397
Case #449: 1
Case #450: 296
Case #451: 0
Case #452: 1
Case #453: 0
Case #454: 1
Case #455: 226
Case #456: 407
Case #457: 1
Case #458: 509
Case #459: 1
Case #460: 619
Case #461: 0
Case #462: 1
Case #463: 0
Case #464: 1
Case #465: 517
Case #466: 467
Case #467: 1
Case #468: 483
Case #469: 1
Case #470: 569
Case #471: 0
Case #472: 1
Case #473: 0
Case #474: 1
Case #475: 481
Case #476: 509
Case #477: 1
Case #478: 451
Case #479: 1
Case #480: 348
Case #481: 0
Case #482: 1
Case #483: 0
Case #484: 1
Case #485: 713
Case #486: 424
Case #487: 1
Case #488: 391
Case #489: 1
Case #490: 640
Case #491: 0
Case #492: 1
Case #493: 0
Case #494: 1
Case #495: 650
Case #496: 479
Case #497: 1
Case #498: 470
Case #499: 1
Case #500: 826

--
Gerry

Gerry Jackson <gerry@jackson9000.fsnet.co.uk> writes:
> Yet another solution using simple character comparisons.

Very nice and compact.

> Results for the large file - do others agree?

I did a quick eyeball check of a dozen or so values and didn't spot any
discrepancies with my own output.

Gerry Jackson <gerry@jackson9000.fsnet.co.uk> writes Re: Google CodeJam?
[..]
> Yet another solution using simple character comparisons. Not a robust
> solution as it expects perfectly formatted data, which is OK for the two
> test files. Just stick the word alien as the first line of a test file
> and include it.
[..]
Results for the large file - do others agree?
[..]

The results match mine, modulo spaces, tabs, and eol characters.
Google has a checker that you could have used.

-marcel

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).

Paul Rubin <no.email@nospam.invalid> wrote:

> I think the Forth spirit is "solve the problem you have". The 32-bit
> representation is just fine for the problem as stated.

After some more thinking, i tend to agree. :-)

Gerry Jackson <gerry@jackson9000.fsnet.co.uk> wrote:

> Results for the large file - do others agree?

I ran it myself, and checked the output - it was correct (after deleting
the input which had got echoed into the output).

So - you won on program size, memory usage and probably on
clarity/simplicity/straightforwardness.

It took >10 sec utime to process the large example, though ;-)

Cheers,
Alex