View Single Post
Old 10-26-2006, 01:13 PM   #1
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,898

Submissions (37)

Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)

Hero Contest #3 - 2nd Place

Default Quicksilver #2: Sequence (Results)

Rules
  • One week to solve.
  • Submit solutions to the pastebin, make sure to have a [quicksilver] prefix.
  • I will test each submission against a big set of test cases.
  • 3 fastest solutions (those which take the least time) win. (It is not a solution if it doesn't show the correct result for any test case)
    • 1st place: 20 rep
    • 2nd place: 15 rep
    • 3rd place: 10 rep
  • If you use global variables in your submission include them in a globals block.
  • Your submission should not get into the op limit in any case, in order to override the limit, you cannot use TriggerSleepAction nor PolledWait, you have to use ExecuteFunc/TriggerExecute. It CAN get into the op limit if you call the function twice, but an instance of the function should never get into the limit.

Problem #2: Sequence
I have a global integer array udg_input and udg_count , udg_input contains udg_count elements, if udg_count is 7 then udg_input has the indexes 0..6 assigned.

udg_count is a number between 2 and 200
udg_input contains postive integer numbers not greater than 10000000 . No element appears in the list more than once. (no repetitions)

The objective is to make a function:
function Consecutive takes nothing returns boolean
It returns true if and only if the elements of the array can form a sequence of consecutive numbers.

Examples

To make the examples, I will use [i0 i1 i2 ...] notation to abbreviate the array.

Then Consecutive([4 5 6]) means:
Collapse JASS:
    set udg_count=3
    set udg_input[0]=4
    set udg_input[1]=5
    set udg_input[2]=6
    set b=Consecutive()

All right:

Consecutive( [1 2 3 4 5 6] ) : returns true
Consecutive( [1 2 3 4 5 7] ) : returns false

Consecutive( [6 2 5 4 3 1] ) : returns true
Consecutive( [3 2 4 5 6 1] ) : returns true

Consecutive( [3 2 4 5 6 1] ) : returns true

Consecutive( [102 103 104 105 106 107 108 109 110 111 112 113] ) : returns true


Consecutive( [100013 100002 100003 100004 100005 100006 100007 100008 100009 100010 100011 100012] ) : returns true

Consecutive( [100013 100002 12 100004 100005 100006 100007 100008 100009 100010 100011 100012] ) : returns false





The results
  • 1st: CaptainGriffen : 0.032236452s
  • 2nd: SeasonsOfLove : 0.048517480s
  • 2nd: Blu_da_noob : 0.048734676s
(the difference was way too small, so I decided to declare a tie, (each gets 17 rep)

Other submissions:
  • Anitarf: 0.053227096s
  • Daelin: 0.053475628
  • Acehart : 0.054932712s
  • emjrl3 : 2.485663648s

disqualified:
  • INfraNe : Wrong output
  • BertTheJasser: Op Limit exceeded
  • ChuckleBrother: Op Limit exceeded

The solution
It was really easy, there are no repetitions, then you can just get min and max values of the array and check if their substraction matches (count-1)

There was an alternative solution in which you only get the minimum and the sum then check with Gauss' formula for sum of consecutive numbers.

Both solutions ended up being as efficient, but the min/max version has an advantage and it is that with little changes you can make it stop the iteration when you can be sure it is wrong.

Otherwise, when 2 persons submitted the same algorithm, little details in the implementation decided who wins.

emjrl3 is the only person who used a different, heavier algorithm that didn't get to the op limit/had issues.

Extra Kudos go to anitarf for being the first person to submit a O(n) algorithm, the rest eventually updated theirs later.

So here is a solution:
Collapse JASS:
function Consecutive takes nothing returns boolean
 local integer c = udg_count
 local integer i = c-2
 local integer t
 local integer l = udg_input[c-1]
 local integer m = l

    loop
        set t = udg_input[i]
        if l > t then
            if t + c > m then
                set l = t
            else
                return false
            endif
        elseif m < t then
            if l + c > t then
                set m = t
            else
                return false
            endif
        endif
        set i = i - 1
        exitwhen i == -1
    endloop

    return true
endfunction
Attached Files
File Type: w3x quicksilver.w3x (230.2 KB, 19 views)
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Sponsored Links - Login to hide this ad!