Cute Little Problem 
Author Message
 Cute Little Problem

Hi!

We recently saw nice solutions to the `nine 9's' problem here.  I was
wondering if anybody have solved the (easier) 1st problem at

  http://www.*-*-*.com/

They ask to make the program as efficient as possible, but I am not
interested in stupid little microoptimizations, but rather whether
there are better, but still simple, algorithms than mine.  That's
also why I am not posting my solution (not yet, at least): I don't
want to influence other solutions if anybody wants to give it a
shot.  To give an idea about orders of magnitude involved, my
solution has about 60 LOC, and runs, with no declarations, no
optimizations turned on, about two minutes.  Note that I changed
the spec for my solution a little: It tries to find /all/ solutions
of maximum length.  IIRC, if it quits when the first solution is
found, it took about 40 secs.  Much fun!

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x42B32FC9



Tue, 13 Jul 2004 03:15:51 GMT  
 Cute Little Problem

Quote:

> optimizations turned on, about two minutes.

Oops, make that three minutes...

Sorry,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x42B32FC9



Tue, 13 Jul 2004 06:35:43 GMT  
 Cute Little Problem

Quote:

> We recently saw nice solutions to the `nine 9's' problem here.  I
> was wondering if anybody have solved the (easier) 1st problem at

>   http://www.itasoftware.com/careers/programmers.php

> They ask to make the program as efficient as possible, but I am not
> interested in stupid little microoptimizations, but rather whether
> there are better, but still simple, algorithms than mine.  That's
> also why I am not posting my solution (not yet, at least): I don't
> want to influence other solutions if anybody wants to give it a
> shot.  To give an idea about orders of magnitude involved, my
> solution has about 60 LOC, and runs, with no declarations, no
> optimizations turned on, about two minutes.  Note that I changed the
> spec for my solution a little: It tries to find /all/ solutions of
> maximum length.  IIRC, if it quits when the first solution is found,
> it took about 40 secs.  Much fun!

I tried my luck and it looks like we're in about the same ball-park. I
arrived at 38 LOC and around 27 seconds for the first solution.
[CMUCL 18c on Linux, PIII 850MHz, 256 MB RAM]

Cheers,
Edi.


("ton" "tone" "tonne" "tonnes" "tension" "sonatine" "nominates" "antinomies"
 "nitrosamine" "terminations" "antimodernist" "determinations"
 "underestimation" "underestimations")
real    0m27.196s
user    0m26.240s
sys     0m0.550s



Tue, 13 Jul 2004 10:12:45 GMT  
 Cute Little Problem

Quote:

> Hi!

> We recently saw nice solutions to the `nine 9's' problem here.  I was
> wondering if anybody have solved the (easier) 1st problem at

>   http://www.itasoftware.com/careers/programmers.php

> They ask to make the program as efficient as possible, but I am not
> interested in stupid little microoptimizations, but rather whether
> there are better, but still simple, algorithms than mine.  That's
> also why I am not posting my solution (not yet, at least): I don't
> want to influence other solutions if anybody wants to give it a
> shot.  To give an idea about orders of magnitude involved, my
> solution has about 60 LOC, and runs, with no declarations, no
> optimizations turned on, about two minutes.  Note that I changed
> the spec for my solution a little: It tries to find /all/ solutions
> of maximum length.  IIRC, if it quits when the first solution is
> found, it took about 40 secs.  Much fun!

Mine is similar in length. It takes about 40 seconds to find
all solutions, where by "find all solutions" I mean "build
a data structure that represents all addagrams in the dictionary,
and output enough information to reconstruct them all trivially".
(I avoid repeating words I've already output; this is quite
effective in avoiding a combinatorial explosion.) It would be
only marginally quicker if I only wanted one solution.

My program conses far too much: about 280Mb. This wouldn't be
very hard to fix. I don't know whether doing so would improve
the speed or make it worse.

Breakdown:

  Reading the dictionary          0.01s   1.75Mb
  Getting it into a usable form   7.75s  75.37Mb
  Finding addagrams              29.52s 203.43Mb
  Reporting the results           0.17s   0.94Mb

All timings are for CMUCL on a 1GHz Athlon running FreeBSD.
No optimization flags and no declarations. I tried adding
a few, but it made no measureble difference.

Writing the code took about 80 minutes, which feels like
approximately a factor of 2 too long. A lot of that time
was spent looking things up in the Hyperspec; not enough
of the spec is swapped into my brain at the moment. (Work
is busy, and CL is almost entirely recreation for me.)

For comparison, I implemented something similar in Python.
It's not identical; one implementation choice seemed to be
more natural one way in CL and another way in Python.
The timings for three of the four stages were very similar;
the other stage ("Finding addagrams") more than twice as
fast in Python. This isn't a major surprise. It would
probably be even faster in Perl.

... So, I tried doing it the "Pythonic" way in CL. It turns
out that it's better in CL as well, though it's still slightly
faster in PYthon. So now the figures look like this:

  Reading the dictionary          0.01s   1.75Mb
  Getting it into a usable form   5.98s  77.45Mb
  Finding addagrams              17.77s 261.40Mb
  Reporting the results           0.13s   1.20Mb

Total: about 24s. The python version takes 23.4s; the
first two stages are slower, the third is quicker. The
Python version is also somewhat shorter. (I also wrote
it more quickly, but that's not interesting because
I'd already written the CL version.)

Like Nils, I'm deliberately not saying more than I
have to about just what the program does, so as not
to spoil the fun for anyone else.

--

.sig under construc



Tue, 13 Jul 2004 10:23:58 GMT  
 Cute Little Problem

Quote:

> Hi!

> We recently saw nice solutions to the `nine 9's' problem here.  I was
> wondering if anybody have solved the (easier) 1st problem at

>   http://www.itasoftware.com/careers/programmers.php

> They ask to make the program as efficient as possible, but I am not
> interested in stupid little microoptimizations, but rather whether
> there are better, but still simple, algorithms than mine.

Well, I'd cut down the size of the search space by lumping together
words that are anagrams of one another because I know I'm not going to
have more success adding a letter to "spat" than to "taps".  And I'd
treat this problem as a graph search problem.

The "word lumps" are the nodes in the graph and the edges are the
letters added to form longer words.  I'd use a breadth first and weed
out nodes that are either already enqueued or nodes that don't
represent words in the dictionary.

I think that's about as optimal as one can get, no?

-dj



Tue, 13 Jul 2004 12:12:02 GMT  
 Cute Little Problem

Quote:

> ... So, I tried doing it the "Pythonic" way in CL. It turns
> out that it's better in CL as well, though it's still slightly
> faster in PYthon. So now the figures look like this:

>   Reading the dictionary          0.01s   1.75Mb
>   Getting it into a usable form   5.98s  77.45Mb
>   Finding addagrams              17.77s 261.40Mb
>   Reporting the results           0.13s   1.20Mb

> Total: about 24s. The Python version takes 23.4s; the
> first two stages are slower, the third is quicker. The
> Python version is also somewhat shorter. (I also wrote
> it more quickly, but that's not interesting because
> I'd already written the CL version.)

I just did a Dylan version.  It's 33 lines and takes 16.5 seconds on my
700 MHz Athlon on linux using Gwydion 2.3.6.

Reading the dictionary and building data structure: 13.5s
Finding longest add-a-gram:                          3.0s

Final heap size is 29 MB.  I don't know the GC stats.
I could double the speed with another ten lines of code, mostly by
doing my own parsing of the input file instead of using sucky library
routines.

-- Bruce



Tue, 13 Jul 2004 14:38:51 GMT  
 Cute Little Problem

On my AMD K6-3 400, my solution in cmucl:

Evaluation took:
  8.64 seconds of real time
  6.06 seconds of user run time
  0.87 seconds of system run time
  [Run times include 1.47 seconds GC run time]
  0 page faults and
  40242400 bytes consed.

The insane amount of consing is due to my choice of data-structure,
which really should be changed, but I don't feel like bothering at
this point. The code is quite long, partly because it uses lots of
small wrapper functions to abstract over some of the details of the
data-structure used and partly because I have commented out code using
LOOP alongside the code that's acutally run which uses SERIES. The
performance difference of the LOOP and SERIES solutions is essentially
nothing.

--
-> -/-                       - Rahul Jain -                       -\- <-

-> -/- "I never could get the hang of Thursdays." - HHGTTG by DNA -\- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   Version 11.423.999.221020101.23.50110101.042
   (c)1996-2002, All rights reserved. Disclaimer available upon request.



Tue, 13 Jul 2004 15:30:19 GMT  
 Cute Little Problem

Quote:

> I just did a Dylan version.  It's 33 lines and takes 16.5 seconds on my
> 700 MHz Athlon on linux using Gwydion 2.3.6.

> Reading the dictionary and building data structure: 13.5s
> Finding longest add-a-gram:                          3.0s

> Final heap size is 29 MB.  I don't know the GC stats.

Now I have some internal instrumentation:

$ time ./add-a-gram <WORD.LST
16: #("indeterminations", "intermediations", "determinations",
"antimodernist", "terminations", "nitrosamine", "antinomies",
"nominates", "mentions", "tension", "nitons", "niton", "into", "ton")

reading file: 13.27d0 sec, 172.029688d0 MB
searching: 3.24d0 sec, 5.387312d0 MB

real    0m16.531s
user    0m16.430s
sys     0m0.100s



Tue, 13 Jul 2004 19:25:14 GMT  
 Cute Little Problem

Quote:
> I tried my luck and it looks like we're in about the same
> ball-park. I arrived at 38 LOC and around 27 seconds for the first
> solution.
> [CMUCL 18c on Linux, PIII 850MHz, 256 MB RAM]

I changed the algorithm a little bit and I'm now at 10 seconds
(including load time which is less than 1 second) - again without
declarations, same platform. LOC have increased to about 55.

Edi.

Evaluation took:
  0.9 seconds of real time
  0.82 seconds of user run time
  0.08 seconds of system run time
  [Run times include 0.52 seconds GC run time]
  410 page faults and
  17980360 bytes consed.

("ton" "tone" "tonne" "tonnes" "tension" "sonatine" "nominates" "antinomies"
 "nitrosamine" "terminations" "antimodernist" "determinations"
 "underestimation" "underestimations")
Evaluation took:
  9.05 seconds of real time
  8.73 seconds of user run time
  0.26 seconds of system run time
  [Run times include 0.99 seconds GC run time]
  9 page faults and
  41866368 bytes consed.



Tue, 13 Jul 2004 20:37:00 GMT  
 Cute Little Problem

Quote:

> On my AMD K6-3 400, my solution in cmucl:

> Evaluation took:
>   8.64 seconds of real time
>   6.06 seconds of user run time
>   0.87 seconds of system run time
>   [Run times include 1.47 seconds GC run time]
>   0 page faults and
>   40242400 bytes consed.

Some people apparently found great solutions :-)  Maybe we should all
exchange solutions by email...

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x42B32FC9



Wed, 14 Jul 2004 00:06:43 GMT  
 Cute Little Problem

Quote:

> Some people apparently found great solutions :-) Maybe we should all
> exchange solutions by email...

I'd be interested to see the other solutions as well. As you started
this thread - would you mind assembling them and sending them out to
the other participants (if they agree)? [I already sent you a link to
my solution (updated this morning).]

Thanks in advance,
Edi.



Wed, 14 Jul 2004 00:17:48 GMT  
 Cute Little Problem



Quote:

> > Some people apparently found great solutions :-) Maybe we should all
> > exchange solutions by email...

> I'd be interested to see the other solutions as well. As you started
> this thread - would you mind assembling them and sending them out to
> the other participants (if they agree)? [I already sent you a link to
> my solution (updated this morning).]

> Thanks in advance,
> Edi.

I've got a couple of solutions, but the one that's competitive in time
is substantially longer than some of the others.  It's hard to benchmark,
since I'm using a different compiler on a different machine running
a different OS: about 50 secs on a 500 mHz P-III Vaio running
Windows-98 (don't ask) using FunO Dylan.

I think my datastructure is over-engineered (but you can do other
cool things with it), so I'm slashing down a version now to see what
a minimal solution might do.



Wed, 14 Jul 2004 00:27:27 GMT  
 Cute Little Problem

Since so many people are writing up solutions to ITA's problems I thought
it would be interesting to do a little informal followup to
http://www.flownet.com/gat/papers/lisp-java.pdf

Anyone who has written up an ITA problem in any language who would like to
be a data point in a new study please email me a copy of your code.  If I
get enough submissions I'll run a set of benchmarks on some standardized
environments and compile the results.

Please put [ITA] in the subject line of your submission email to make it
easier for me to sort them out.  Also, please include the following
information:

1.  How long you spent writing the code (to the best of your recollection)
2.  How long you've been programming
3.  How long you've been programming in the language your code is written in.

Multiple submissions from the same person are fine.

Thanks!

Erann



Wed, 14 Jul 2004 00:10:12 GMT  
 Cute Little Problem

Quote:


>> Some people apparently found great solutions :-) Maybe we should all
>> exchange solutions by email...

> I'd be interested to see the other solutions as well. As you started
> this thread - would you mind assembling them and sending them out to
> the other participants (if they agree)? [I already sent you a link to
> my solution (updated this morning).]

I'll mail you and anybody else who ask me a tar file with all solutions
I got so far.  I hope everybody who mailed one to me agrees with that;
if not, post soon or sue me ;-)

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x42B32FC9



Wed, 14 Jul 2004 02:37:31 GMT  
 Cute Little Problem

Quote:

> Since so many people are writing up solutions to ITA's problems I thought
> it would be interesting to do a little informal followup to
> http://www.flownet.com/gat/papers/lisp-java.pdf

> Anyone who has written up an ITA problem in any language who would like to
> be a data point in a new study please email me a copy of your code.  If I
> get enough submissions I'll run a set of benchmarks on some standardized
> environments and compile the results.

To make things easier for you, we should first clarify the problem
a bit: ITA asks for ``the'' solution, but there is actually more than
one.  Should the programs find /all/ solutions or stop when they have
found one?  I think searching for /all/ solutions makes more sense,
so that's what's my version does.

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x42B32FC9



Wed, 14 Jul 2004 02:49:06 GMT  
 
 [ 48 post ]  Go to page: [1] [2] [3] [4]

 Relevant Pages 

1. 1 little, 2 little, 3 little endians...

2. a cute hack -- delegation after doesNotUnderstand

3. Unrelated but cute...

4. a cute hack -- delegation after doesNotUnderstand

5. a cute hack -- delegation after doesNotUnderstand

6. Cute Laila

7. limited test-less loop-less call-full repetition

8. a cute way to reduce a fraction?

9. Cute toy or start of something?

10. Here's a cute one...

11. Ada to C/C++ -- no cute answers, please.

12. TO: Colin and Bob - cute stories but economically insignificant

 

 
Powered by phpBB® Forum Software