[REBOL] Re: Algorithm challenge: compacting integers
From: SunandaDH::aol::com at: 26-Jan-2007 7:20
The entries haven't yet dried up on Challenge-1 and Challenge-2, but we are
going to close that part of the challenge at the end of Mon 29-jan-2007 (ie
midnight UTC). So it is not too late to try: you'll have a whole weekend!
If you have entered via Altme or private email, please publish your entries
here before the end of Monday. Otherwise, they are not official.
A couple of people have asked what the other, related, challenges are (as
hinted in the opening message in this thread).
So, without any further delay, here are the other three challenges -- please
feel free to enter these even if you gave the earlier stages a miss.
Write a function, find-compact, that returns true or false depending on
whether a given integer exists in a compacted block. As always you can assume the
compacted block is in ascending order of first elements.
find-compact [1 3x8 40] 20
== false ;; 20 is not in the block
find-compact [1 3x8 40] 40
find-compact [1 3x8 40] 7
Write a function, remove-compact, that returns a copy of the input block
having removed a given integer:
remove-compact [1 3x8 40] 40
== [1 3x8]
remove-compact [1 3x8 40] 10
== [1 3x7 40]
remove-compact [1 3x8 40] 5
== [1 3x2 6x5 50]
remove-compact [1 3x8 40] 99
== [1 3x8 40] ;; 99 not found so the output has the same values as the input
Write a function, insert-compact, that returns a copy of the input block
having inserted (at the right position) a given integer:
insert-compact [1 3x8 40] 25
== [1 3x8 25 40]
insert-compact [1 3x8 40] 11
== [1 3x9 40]
insert-compact [1 3x8 40] 2
== [1x10 40]
insert-compact [1 3x8 40] 7
== [1 3x8 40] ;; 7 already present, so the output values are the same as
the input values
As before, this is not an academic exercise: SKIMP uses my versions of these
functions, and I'd like to use the fastest results from the these challenges
to improve SKIMP.
One way to do these challenges is to use decompact to get a simple list, work
on that, and then recompact. That would make a great one-liner, but there are
The closing date for Challenges 3 through 5 entries is Monday 5-feb-2007. But
please feel free to publish before that. Seeing other people's results may
help you revise your own into a worldbeater.
Thanks to everyone who has taken part so far, and good luck again!