Silly Pop-11 Programming Challenge 2003 
Author Message
 Silly Pop-11 Programming Challenge 2003

Dear fellow programmers,

Excellent - a whole New Year to spend on silly programming
challenges!  What's this, I hear you say?  You've run out of daft
crackpot problems and you need to get back to your real work!
Already?!?

Perhaps you have time for just one potty little problem?  An easy
one.  No honest.  This one's *really* easy.  Unless you want style
points ...

       --- Steve's Very Silly Pop-11 Programming Challenge 2003 ---

Implement a PERMUTATION REPEATER.  Given a data structure of your
choice (string, list, vector, all of the previous), return a
procedure that when called repeatedly returns permutations of the
original.  Although the order of the permutations returned there
should be no repeats and every possible permutation should be
returned, eventually.

Points will be awarded by me for
     1.  Correctness, because this is not a C programming challenge.
     2.  Beauty.
     3.  Efficiency - in both time and space.
     4.  Generality.  Super bonus points for handling dynamic lists.
     5.  Showing off, rule bending, cheating, etc.

Post your solutions to popforum _or_, if you don't want to share you
cunning plan with your rivals, email them direct to me.  I do
solemnly promise not to steal your ideas for my own answer.  Well,
not before announcing any results, anyway.  The scoring system will
be announced after I have seen the entries and decided on the winner.
Lastly, rival judgements to my own are naturally welcome.

--
Steve



Tue, 21 Jun 2005 00:25:38 GMT  
 Silly Pop-11 Programming Challenge 2003

Quote:

>       --- Steve's Very Silly Pop-11 Programming Challenge 2003 ---

>Implement a PERMUTATION REPEATER.  Given a data structure of your
>choice (string, list, vector, all of the previous), return a
>procedure that when called repeatedly returns permutations of the
>original.  Although the order of the permutations returned there
>should be no repeats and every possible permutation should be
>returned, eventually.

Aha!

Quote:
>Points will be awarded by me for
>     1.  Correctness, because this is not a C programming challenge.
>     2.  Beauty.
>     3.  Efficiency - in both time and space.
>     4.  Generality.  Super bonus points for handling dynamic lists.
>     5.  Showing off, rule bending, cheating, etc.

What about:
      0.  Amount of time spent coding your solution.

This is relevant, because I suspect I can find several examples in
my library, so coding time would be zero ... ;-).

I think 3 should be split into 3a time and 3b space - we are not all
Einsteins, you know!

Jonathan

--
Use jlc instead of netspam to e-mail me, please.



Tue, 21 Jun 2005 07:57:58 GMT  
 Silly Pop-11 Programming Challenge 2003
Hi,

[For readers who aren't following this thread, this is YOUR SILLY WARNING.]

Quote:
>What about:
>       0.  Amount of time spent coding your solution.

This is (5) Showing off, and clearly merits points.

Quote:
>I think 3 should be split into 3a time and 3b space - we are not all
>Einsteins, you know!

Although that would simplify email addresses considerably.
Efficiency extremes will be awarded points for showing off, naturally
enough.

                                     ---*---

For example, one might consider the permutation repeater for
references.  Since references contain one and only one item, the set
of permutations is computationally tractable.  Here is an
implementation which does the job.

;;; Example of reasonably efficient solution to permutation problem.
;;; Known Limitation: only handles objects containing a single element
;;; such as refs.  Can also handle lists, vectors and strings of length 1.
define permutations_of_ref( ref );
     listtopd( [ ^ref ] )
enddefine;

Now, I daresay some (insufficiently silly) people will complain that
"listtopd" needs definition.  Fusspots.

;;; OK, OK here it is.
;;; Converts lists to repeaters.  The repeaters are pushable.
define listtopd( L ) -> R;
     lvars seen_termin = false;
     procedure();
         if null( L ) then
             if seen_termin then
                 mishap( 'listtopd: repeater exhausted', [] )
             else
                 true -> seen_termin;
                 termin;
             endif
         else
             fast_destpair( L ) -> L
         endif
     endprocedure -> R;
     procedure( /* item */ ) with_nargs 1;
         conspair( /* item */, L ) -> L
     endprocedure -> updater( R );
enddefine;

--
Steve



Wed, 22 Jun 2005 08:10:28 GMT  
 Silly Pop-11 Programming Challenge 2003
Hi -

I guess it is incumbent on me to waste some of my own precious time
on this "easy" challenge.  Did I really suggest this was easy?  I
must have been out of my mind.  Well, I am now.  Certainly after
reading David's marvellous entry which illustrates a remarkable
approach to the problem.  Wow!

My own (first) entry is included below.  I decided to write a core
procedure that takes N items from the stack and deliver a
quasi-repeater.  I say quasi repeater because either it returns
termin or a permutation of the original N items - as such it fails to
meet the contract of a repeater.  However, this allows it to make
good use of the stack rather than the heap.

Similar to David's entry, the core procedure is fronted by a more
friendly version that handles a variety of data types and performs
the conversion to the core.

At this point I will observe that both David's solution and my own
have two defects.  (1) Neither supports any store sharing between
solutions - although this can be constructed as an advantage.  (2)
Neither can deal with potentially infinite dynamic lists.  I wonder
if anyone can repair these problems?

                             ---oooOOOooo---

compile_mode :pop11 +strict;

section;

;;; We want to use fast integer arithmetic, so we need to establish
;;; safe limits.
uses int_parameters;

define permutations_n( n );
     lvars procedure constructor;

     define exhausted_pd();
         mishap( 0, 'Calling an exhausted repeater' )
     enddefine;

     define singleton_to_pd( x );
         lvars done = false;
         procedure();
             if done then
                 exhausted_pd()
             else
                 x;
                 x == termin -> done;
                 termin -> x;
             endif
         endprocedure
     enddefine;

     ;;; Verify that it is safe to add 1 to n.  We need this to
     ;;; support idx : integer AND idx ranges from 1 to n + 1.
     fi_check( n, 0, pop_max_int fi_- 1 ) -> _;

     if n == 0 then
         singleton_to_pd( 0 )
     else
         ;;; Pick up the top n-1 items.  We'll extract the permutations
         ;;; of these items one by one.  Each of these P(n-1) will
         ;;; be used to generate n permutations from P(n) by transposition.
         lvars procedure gen = permutations_n( n fi_- 1 );

         lvars item = ();
         lvars vector = initv( n );              ;;; This may also
establish n < pop_max_int.
         lvars idx = n fi_+ 1;                   ;;; 1 <= idx : integer <= n + 1

         ;;; Generator calls itself recursively so it needs to be named.
         define generator();
             if idx fi_<= n then
                 ;;; Invariant: the elements 1 to n - 1 are a permutation of
                 ;;; the n-1 items captured by gen.  The nth element is, in
                 ;;; principle item, BUT in practice we allow it to become
                 ;;; junk for a small efficiency gain.
                 lvars ith = fast_subscrv( idx, vector );
                 ith -> fast_subscrv( n, vector );       ;;; Transposition.
                 item -> fast_subscrv( idx, vector );
                 destvector( vector );                   ;;; PUSH THE ANSWER.
                 ith -> fast_subscrv( idx, vector );     ;;; restore
the invariant.
                 idx fi_+ 1 -> idx;
             else
                 ;;; We set up a new sub-permutation to create the
                 ;;; next batch of permutations from.
                 lvars k = gen();                        ;;;  k is
termin OR n - 1.
                 if k == termin then
                     termin;
                     exhausted_pd -> gen;
                     ;;; The vector is now garbage, too.
                 else
                     ;;; Set up the invariant described about.  The nth
                     ;;; value does not matter.  I use -item- here, since
                     ;;; that is the 'natural' value.  However, the nth
                     ;;; slot gets zapped every time.
                     fill( item, vector ) -> _;
                     1 -> idx;
                     ;;; Having set up the invariant we call the generator
                     ;;; again to get out the values.
                     generator();
                 endif
             endif
         enddefine;

         generator

     endif;
enddefine;

define permutations( obj );
     lvars ( destructor, constructor ) = (
         if obj.isvectorclass then
             lvars key = obj.datakey;
             key.class_dest, key.class_cons
         elseif obj.islist then
             destlist, conslist
         else
             mishap( obj, 1, 'List or vectorclass object expected' )
         endif
     );
     lvars procedure gen = permutations_n( obj.destructor );
     procedure();
         lvars k = gen();
         if k == termin then
             termin
         else
             constructor( k )
         endif
     endprocedure
enddefine;

endsection;

--
Steve



Mon, 27 Jun 2005 20:40:16 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Silly Pop-11 Programming Challenge 2003 - Result!

2. Forwarded: Re: Silly Pop-11 Programming Challenge 2003

3. Forwarded: Re: Silly Pop-11 Programming Challenge 2003

4. Forwarded from David Young: Re: Silly Pop-11 Programming Challenge 2003

5. looking for file processing programs written in Pop-11

6. Pop-11 programs for MIF scripting

7. POP-11 as a first programming language

8. Constraint Logic Programming in Pop-11

9. Constraint Logic Programming in Pop-11

10. Clarion Magazine Weekly Summary For May 11-17, 2003

11. final day for Python 11 - OSCON 2003 early bird registration

12. less than two weeks left for Python 11 - OSCON 2003 early bird registration

 

 
Powered by phpBB® Forum Software