Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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. CHALLENGE-3: find-compact 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 == true find-compact [1 3x8 40] 7 == true ========== CHALLENGE-4: remove-compact 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 ========== CHALLENGE-5: insert-compact 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 faster ways. 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! Sunanda