Google CodeJam?

Le 27/04/2012 18:28, Alex Wegel a écrit :
> Ian Osgood<iano@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/
>
> I tried another one of the examples for practicing - im still way too
> slow. Fortunately, i wouldn't feel like going on a trip to NY anyway ;-)
>
> The example i tried was "all your base..", the logical sequel to the
> alien example :-)
>
> http://code.google.com/codejam/conte...dashboard#s=p0
>
> It took me about 1:30 hrs to come up with a fully correct solution
> (guess what - it's ugly).
>
> In case someone wants to try too, i don't post my solution or further
> discussions (i.e. any spoilers) yet.
>
> Cheers,
> Alex

hi Alex,
sticked with a bug severals days, here my solution.
curious to see your.
Bruno

\ AllYourBase bruno gauthier
decimal
create in$ maxstring allot create inner1$ maxstring allot
create inner2$ maxstring allot create out$ maxstring allot
create tvals 64 allot create Single-Char-I/O-Buffer 0 C, align
10 constant NL
variable ifh variable ofh variable #ib
0 value T 0 value highestindex 0 value basetested

: Fill-tvals
'1' tvals c! '0' tvals 1+ c!
10 2 do '0' i + tvals i + c! loop
26 0 do 'A' i + tvals i + 10 + c! loop
;
fill-tvals

: CHECKED ( f -- ) ABORT" File Access Error. " ;


: read-char ( file -- char|f )

Single-Char-I/O-Buffer 1 ROT READ-FILE CHECKED

IF Single-Char-I/O-Buffer C@ ELSE -1 THEN
;

: next-word->in$ ( -- )
begin
ifh @ read-char
NL <>
while
Single-Char-I/O-Buffer c@ dup dup
'0' '9' between swap 'a' 'z' between or
if in$ C+place
else drop
then
repeat
;

: parse-headline ( -- ) next-word->in$ in$ count evaluate to T ;
: open-files ( -- )
bl word count r/o open-file throw ifh !
bl word count 2dup file-status nip 0=
if 2dup delete-file drop
then r/w create-file throw ofh !
;
: inits ( -- )
0 to highestindex 0 to basetested
in$ maxstring erase out$ maxstring erase inner1$ maxstring erase
inner2$ maxstring erase
next-word->in$ in$ count 2dup upper inner1$ place
;
: available-chars ( -- )
inner1$ count 2dup bounds
do
2dup i c@ scan drop i = if i c@ inner2$ c+place then
loop
2drop
;
: chars-exchanges ( -- )
in$ count nip 0
do
inner2$ dup 1+ swap
count in$ count drop i + c@ scan drop swap -
dup highestindex max to highestindex
tvals + c@ out$ C+place
loop
;
: .outputs ( i -- )
in$ maxstring erase
cr s" Case #" in$ place
1+ 0 <# #s #> in$ +place s" : " in$ +place
<# #s #> in$ +place in$ count type
crlf$ count in$ +place in$ count ofh @ write-file drop
;

: allyourbase ( -- )
cls open-files parse-headline
T 0
do

inits available-chars chars-exchanges

highestindex 1+ 2 max to basetested
out$ count basetested base-tonum
i .outputs
loop
ofh @ close-file drop
ifh @ close-file drop
;

\ allyourbase A-small-practice.IN A-small-practice.OUT
allyourbase A-large-practice.IN A-large-practice.OUT

Bruno Gauthier <bgauthier@free.fr> wrote:

> Le 27/04/2012 18:28, Alex Wegel a écrit :
> > Ian Osgood<iano@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/
> >
> > I tried another one of the examples for practicing - im still way too
> > slow. Fortunately, i wouldn't feel like going on a trip to NY anyway ;-)
> >
> > The example i tried was "all your base..", the logical sequel to the
> > alien example :-)
> >
> > http://code.google.com/codejam/conte...dashboard#s=p0
> >
> > It took me about 1:30 hrs to come up with a fully correct solution
> > (guess what - it's ugly).
> >
> > In case someone wants to try too, i don't post my solution or further
> > discussions (i.e. any spoilers) yet.
> >
> > Cheers,
> > Alex
>
> hi Alex,
> sticked with a bug severals days, here my solution.
> curious to see your.
> Bruno

As i said, it's another ugly solution - my "philosophy" was to leave
everything out that wasn't really needed for the question. (This way,
there's also less space for bugs to hide.)

I didn't put comments into the code (quel surprise!), but the basic
concept is: The alien digits are already ordered (1,0,2,3,4,5,...), so
it's easy to build a table for translating them. After the table has
been built, the alien number-base is known, and i can feed the
transliterated alien numeral to forth to get the numerical value.

The program uses stdin (run in a pipe), so if your forth doesn't have
that, you just need a replacement for getl, to get a line (e.g. based on
refill).

Here it comes - cheers,
Alex

#! /usr/local/bin/gforth-fast
0 value hi
create d 36 allot
: wipe d 36 erase 0 to hi ;
: +dig d hi + c! 1 hi + to hi ;
: >dig?
hi begin dup while
1 - 2dup d + c@ = if nip true exit then
repeat drop false ;
: twiddle dup >r c@ r@ char+ c@ r@ c! r> char+ c! ;
: pars
bounds do
i c@ >dig? if drop else +dig then
loop d twiddle hi 2 max to hi ;
: dig> dup 9 > if 7 + then [char] 0 + ;
: eval
2dup pars 2dup bounds do i c@ >dig? drop dig> i c! loop
hi base ! s>unumber? drop decimal ;
: getl pad dup 64 stdin read-line throw drop ;
: .. ." Case #" 1 .r ." : " 1 ud.r cr ;
: app getl evaluate 0 do getl eval i 1+ .. wipe loop ;
' noop is bootmessage
app bye

Le 01/05/2012 19:12, Alex Wegel a écrit :

>
> As i said, it's another ugly solution - my "philosophy" was to leave
> everything out that wasn't really needed for the question. (This way,
> there's also less space for bugs to hide.)
>
> I didn't put comments into the code (quel surprise!), but the basic
> concept is: The alien digits are already ordered (1,0,2,3,4,5,...), so
> it's easy to build a table for translating them. After the table has
> been built, the alien number-base is known, and i can feed the
> transliterated alien numeral to forth to get the numerical value.

> The program uses stdin (run in a pipe), so if your forth doesn't have
> that, you just need a replacement for getl, to get a line (e.g. based on
> refill).
>
> Here it comes - cheers,
> Alex
>
> #! /usr/local/bin/gforth-fast
> 0 value hi
> create d 36 allot
> : wipe d 36 erase 0 to hi ;
> : +dig d hi + c! 1 hi + to hi ;
> :>dig?
> hi begin dup while
> 1 - 2dup d + c@ = if nip true exit then
> repeat drop false ;
> : twiddle dup>r c@ r@ char+ c@ r@ c! r> char+ c! ;
> : pars
> bounds do
> i c@>dig? if drop else +dig then
> loop d twiddle hi 2 max to hi ;
> : dig> dup 9> if 7 + then [char] 0 + ;
> : eval
> 2dup pars 2dup bounds do i c@>dig? drop dig> i c! loop
> hi base ! s>unumber? drop decimal ;
> : getl pad dup 64 stdin read-line throw drop ;
> : .. ." Case #" 1 .r ." : " 1 ud.r cr ;
> : app getl evaluate 0 do getl eval i 1+ .. wipe loop ;
> ' noop is bootmessage
> app bye

while have to study it
thanks for your post
bruno

awe..cor.de (Alex Wegel) writes Re: Google CodeJam?

> As i said, it's another ugly solution - my "philosophy" was to leave
> everything out that wasn't really needed for the question. (This way,
> there's also less space for bugs to hide.)

> I didn't put comments into the code (quel surprise!), but the basic
> concept is: The alien digits are already ordered (1,0,2,3,4,5,...), so
> it's easy to build a table for translating them. After the table has
> been built, the alien number-base is known, and i can feed the
> transliterated alien numeral to forth to get the numerical value.

So why not add the above small explanation and some stack comments
to your code? I almost suspect that you deliberately deleted them :-)

Just a observation: your program works with iForth when I use the
standard >NUMBER and REFILL words. The runtime for the large example
is dominated by I/O time: 1 ms without output and 120 ms with writing
of the data to file.

-marcel

After adding the following words...

256 constant maxstring
: between 1+ within ;
: C+place ( c saddr) dup >r count dup >r + c! r> 1+ r> c! ;
: upper bounds ?do i c@ toupper i c! loop ;
create crlf$ 1 c, 10 c, align
: cls cr cr cr cr ;
: base-tonum base ! s>unumber? 0= throw decimal ;

....and "0 in$ c!" somewhere before the call to parse-headline (because
allot didn't clear memory, and your inits word is only called later), it
worked:-)

Most of all i like that there's a lot of variety in the style of the
solutions shown in this thread, even though the two CodeJam questions
were of a real simple nature.

Unfortunately, nobody of us could understand the aliens or stop their
attack in time.

Cheers, Alex

<hughaguilar96@yahoo.com> wrote:

> I've never written a plain Forth program in my life.

Now i'm puzzled (though not really surprised by the fact itself) - this
is coming quite a long way from:

> I'm the only Forther on the planet who has any chance at all.

I wish you much fun with or without your package, and good luck with
your copyrights. (iBrows raised..)

Alex

<..x.nl> wrote:

> awe..cor.de (Alex Wegel) writes Re: Google CodeJam?
>
> > As i said, it's another ugly solution - my "philosophy" was to leave
> > everything out that wasn't really needed for the question. (This way,
> > there's also less space for bugs to hide.)
>
> > I didn't put comments into the code (quel surprise!), but the basic
> > concept is: The alien digits are already ordered (1,0,2,3,4,5,...), so
> > it's easy to build a table for translating them. After the table has
> > been built, the alien number-base is known, and i can feed the
> > transliterated alien numeral to forth to get the numerical value.
>
> So why not add the above small explanation and some stack comments
> to your code? I almost suspect that you deliberately deleted them :-)

Actually i think i had 2 of them at some point in time, but that was
about it, and then they went stale. They not so interesting anyway :-)
See:

#! /usr/local/bin/gforth-fast
0 value hi \ highest digit-value found so far
create d 36 allot \ digit string containing all alien digits
: wipe ( ) d 36 erase 0 to hi ; \ housekeeping
: +dig ( c) d hi + c! 1 hi + to hi ; \ add newly learned digit to d
: >dig? ( c -- +n true|c false) \ lookup alien digit
hi begin dup while
1 - 2dup d + c@ = if nip true exit then
repeat drop false ;
: twiddle ( ca) dup >r c@ r@ char+ c@ r@ c! r> char+ c! ; \ exch 2 bytes
: pars ( ca u) \ read alien numeral to determine digits & number base
bounds do
i c@ >dig? if drop else +dig then
loop d twiddle hi 2 max to hi ;
: dig> (+n--c) dup 9 > if 7 + then [char] 0 + ; \ convert 1 dig to text
: eval ( ca u) \ evaluate alien number string
2dup pars 2dup bounds do i c@ >dig? drop dig> i c! loop
hi base ! s>unumber? drop decimal ;
: getl pad dup 64 stdin read-line throw drop ;
: .. ." Case #" 1 .r ." : " 1 ud.r cr ;
: app getl evaluate 0 do getl eval i 1+ .. wipe loop ;
' noop is bootmessage
app bye

Main thing to remember when reading the source is that in bottom up
programming, the top is down.

> Just a observation: your program works with iForth when I use the
> standard >NUMBER

Yes, i should have used that one.

> and REFILL words.

Also yes, this time there were no overlong input lines, so this would do
the job too.
My defense is that what i posted is the original - the first working
version, so changing these would be part of some clean-up to come.
(I fathom that using SCAN in >dig? and maybe getting rid of hi as a
value could also get on the todo-list).

> The runtime for the large example
> is dominated by I/O time: 1 ms without output and 120 ms with writing
> of the data to file.

Well - strictly speaking, the 4 minutes(?) granted by the codejam rules
are way too much time, considering some of the attack-dates ;-)

Cheers,
Alex

awegel@arcor.de (Alex Wegel) writes:
> I didn't put comments into the code (quel surprise!), but the basic
> concept is: The alien digits are already ordered (1,0,2,3,4,5,...), so

It was a pretty easy problem (I used Python) and my test output
looks ok to me, but the upload says my answer was incorrect.
Did you get 290762935202 for case #35 and 10^18 for case #36?

Did they really expect people to complete this task in 4 minutes? I
guess that's doable if absolutely nothing goes wrong. Make a small
mistake or two and you're sunk. I didn't time myself but I probably
took between 5 and 10 minutes.

I should try doing some of these in C, which should be more directly
comparable to Forth. I had trouble attempting using Forth because of
the complexity of doing anything with strings or files. In languages
like Python, this stuff is too easy because the built-in libraries do
all the work.

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

> awegel@arcor.de (Alex Wegel) writes:
> > I didn't put comments into the code (quel surprise!), but the basic
> > concept is: The alien digits are already ordered (1,0,2,3,4,5,...), so
>
> It was a pretty easy problem (I used Python) and my test output
> looks ok to me, but the upload says my answer was incorrect.
> Did you get 290762935202 for case #35 and 10^18 for case #36?

Case #1: 201
Case #2: 75
Case #3: 11
Case #4: 17419143
Case #5: 1801622
Case #6: 47225
Case #7: 17273
Case #8: 866022
Case #9: 2
Case #10: 42
Case #11: 44317196
Case #12: 511
Case #13: 1
Case #14: 44317196
Case #15: 1023456789
Case #16: 29480883458974409
Case #17: 26432593615
Case #18: 35180798355218
Case #19: 102334506713879
Case #20: 398821148
Case #21: 102345156378290
Case #22: 1002342562744892
Case #23: 674293938766347782
Case #24: 4256386811230819
Case #25: 515096463571317029
Case #26: 3589692911
Case #27: 102034056733893387
Case #28: 187812613000849559
Case #29: 108686242308947
Case #30: 2616885866937
Case #31: 35181782102483
Case #32: 674303048939557361
Case #33: 102345678950
Case #34: 64897047
Case #35: 290762935202
Case #36: 1000000000000000000
Case #37: 575985757797280145
Case #38: 319635304277606399
Case #39: 316555023193359374
Case #40: 921615989741647091
Case #41: 23219822358886405
Case #42: 11986027137890515
Case #43: 153855365171289881
Case #44: 262144
Case #45: 244593359538403
Case #46: 3005211782346
Case #47: 1859030134286095
Case #48: 211967741386084
Case #49: 4256889290508007
Case #50: 23551152047651
Case #51: 23551946083611
Case #52: 102343256672849
Case #53: 23550744836764
Case #54: 14018075135
Case #55: 10234456789102345
Case #56: 29480883458974409
Case #57: 50069
Case #58: 4
Case #59: 1244777988
Case #60: 64881574
Case #61: 3
Case #62: 107
Case #63: 398819
Case #64: 1145122416
Case #65: 1342284513
Case #66: 287
Case #67: 12194234
Case #68: 60589237
Case #69: 1177315138
Case #70: 83
Case #71: 115
Case #72: 2430248
Case #73: 5
Case #74: 10843881
Case #75: 53409068
Case #76: 302
Case #77: 431345
Case #78: 29
Case #79: 3
Case #80: 22094
Case #81: 637
Case #82: 4825
Case #83: 1315
Case #84: 64776197
Case #85: 4297977
Case #86: 17194
Case #87: 11
Case #88: 2163798
Case #89: 1802680
Case #90: 1664354412
Case #91: 62874659
Case #92: 290313057
Case #93: 13
Case #94: 427257653
Case #95: 138
Case #96: 893251
Case #97: 301
Case #98: 1
Case #99: 17349
Case #100: 1924398475

> Did they really expect people to complete this task in 4 minutes? I
> guess that's doable if absolutely nothing goes wrong. Make a small
> mistake or two and you're sunk. I didn't time myself but I probably
> took between 5 and 10 minutes.

I would have failed there too (both times), but with re-reading, and
properly understanding the given limits *before* trying with the real
data (i.e. before the 4- or 8-min timer would have started), i would
have had a better chance (because that's what i stumbled over twice:
first buffer size, then number precision).

> I should try doing some of these in C, which should be more directly
> comparable to Forth. I had trouble attempting using Forth because of
> the complexity of doing anything with strings or files. In languages
> like Python, this stuff is too easy because the built-in libraries do
> all the work.

Well - the first example almost being a regexp was an especially fitting
case for string-heavy languages, but even there, i'd say that forth had
it's strengths, and if it's just by encouraging to not regard the input
as strings, but as something a little bit simpler, in the limits of the
posed question.

Cheers,
Alex

On May 1, 5:44*pm, awe...@arcor.de (Alex Wegel) wrote:
> <hughaguila...@yahoo.com> wrote:
> > I've never written a plain Forth program in my life.
>
> Now i'm puzzled (though not really surprised by the fact itself) - this
> is coming quite a long way from:
>
> > I'm the only Forther on the planet who has any chance at all.

Your "plain Forth" would more accurately be called "obfuscated Forth"
--- I've never written that in my life --- and I never will.

I don't think that I could write a Forth program without stack-picture
comments, as I would confuse myself. I think that you used stack-
picture comments just like everybody else when you wrote your program,
but then removed them afterward to obfuscate your code.

We've been quoting poetry in this thread --- here is what another
German said on the subject:
"Nor are poets clean enough for me --- they muddy the water to make it
appear deep."

> I wish you much fun with or without your package, and good luck with
> your copyrights. (iBrows raised..)

I stick that copyright notice on the top of all my stuff. I don't
think there is a market for alien-alphabet software. This will go into
the next novice package upgrade as yet another example program --- all
of that stuff is BSD license --- anybody can use it freely.

Actually, there isn't any market for any kind of Forth. That was the
point that I was making. It is mildly amusing to write a string
pattern-matching program from scratch in Forth, but the rest of the
world just uses the myriad scripting languages available for this kind
of stuff --- they are trivial. It took me about 3 hours (and I screwed
it up by not supporting pattern strings longer than 255 chars) --- no
employer in the world is going to pay for 3 hours of work to write a
program that even the office intern working for free could knock out
in 30 minutes.

You don't really want an answer to that crap?