OpenEuphoria

Algo for Patrick Barnes

• Posted by Alan Oxley <fizzpop at icon.co.za> Jun 30, 2004
• 452 views

--
-- 30th June 2004, AJ Oxley
-- uses Euphoria 2.4 licenced, see
-- www.rapideuphoria.com
--
-- Algo for Mr Trick, requested 29th June 16:23
--
with    type_check
with    trace
without profile
with    warning
--
include machine.e -- needed for set_rand
--
sequence numbers, numbers_copy, result, result_copy
atom element -- actual number does not have to be an integer
integer sequence_length, seed_value
--
sequence_length = 900 -- max is 1073741823, see rand() doc
seed_value = 76325661 -- max is 1073741823, see set_rand()
numbers = {}
result = {}
result_copy = {}
--
procedure fill_sequence()
     -- fill the sequence with easy-to-check numbers.
     -- In this case, the position number in the sequence.
     integer i1
     i1 = 0
     while i1 < sequence_length do
         i1 = i1 + 1
         element = i1 -- make the integer an atom
         numbers = append(numbers,element)
     end while
     numbers_copy = numbers -- backup for later comparison
end procedure

procedure main_algo1()
     -- select an element of the sequence, and
     -- then remove that element from the sequence.
     -- this ensures you cannot select the same element twice.
     -- It is also faster than hit-and-miss, especially when
     -- you are nearly finished the loop
     --
     integer i1, i2
     sequence s1, s2
     i1 = sequence_length + 1
     set_rand(seed_value) -- ensure repeatable pseudo random
     while 1 < i1 do
         i1 = i1 - 1
         if i1 = 1 then  -- last remaining element ?
            result = append(result,numbers[1])
            exit
         end if
         i2 = rand(i1)
         element = numbers[i2]
         result = append(result,element)
         if i2 != 1 then
            if i2 != i1 then
               s1 = numbers[1..i2-1]
               s2 = numbers[i2+1..i1]
               numbers = s1 & s2
            else
               numbers = numbers[1..i1-1]
            end if
         else
            numbers = numbers[2..i1]
         end if
      end while
end procedure

procedure main_algo2()
     -- repeat of main_algo1 procedure, using
     -- numbers_copy and result_copy
     integer i1, i2
     sequence s1, s2
     i1 = sequence_length + 1
     set_rand(seed_value) -- ensure repeatable pseudo random
     while 1 < i1 do
         i1 = i1 - 1
         if i1 = 1 then  -- last remaining element ?
            result_copy = append(result_copy,numbers_copy[1])
            exit
         end if
         i2 = rand(i1)
         element = numbers_copy[i2]
         result_copy = append(result_copy,element)
         if i2 != 1 then
            if i2 != i1 then
               s1 = numbers_copy[1..i2-1]
               s2 = numbers_copy[i2+1..i1]
               numbers_copy = s1 & s2
            else
               numbers_copy = numbers_copy[1..i1-1]
            end if
         else
            numbers_copy = numbers_copy[2..i1]
         end if
      end while
end procedure

procedure main()
      fill_sequence()
      main_algo1()
      main_algo2()
      if compare(result,result_copy) = 0 then
         puts(1,"\nSequences are identical!\n")
      end if
end procedure

main()

HTH,
Regards
Alan