wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Warcraft III Modding > Developer's Corner > Triggers & Scripts
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 10-26-2006, 02: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)

NOTE: You have been redirected in order for our attachments to be made available to you. This will only last two minutes; these measures where taken to avoid hotlinking and bandwidth theft.
To avoid these restrictions Log in or Register

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!
Old 10-26-2006, 02:41 PM   #2
Chuckle_Brother
Oh for the sake of fudge
 
Chuckle_Brother's Avatar


Respected User
 
Join Date: Dec 2005
Posts: 782

Submissions (2)

Chuckle_Brother will become famous soon enough (53)Chuckle_Brother will become famous soon enough (53)

Send a message via ICQ to Chuckle_Brother Send a message via AIM to Chuckle_Brother Send a message via MSN to Chuckle_Brother Send a message via Yahoo to Chuckle_Brother
Default

Heh, looks like fun.

Are use lazy types who didn't bother with contest #1 allowed in?
__________________
"...you play a mean banjo"
Chuckle_Brother is offline   Reply With Quote
Old 10-26-2006, 02:47 PM   #3
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

Each quicksilver round is independent of the others.
__________________
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
Old 10-26-2006, 02:48 PM   #4
The)TideHunter(
SpeakerGames.com
 
The)TideHunter('s Avatar
 
Join Date: Mar 2006
Posts: 1,328

Submissions (1)

The)TideHunter( is a jewel in the rough (160)The)TideHunter( is a jewel in the rough (160)

Send a message via MSN to The)TideHunter(
Default

Quote:
Originally Posted by Vexorian
Consecutive( [3 2 4 5 6 1] ) : returns true

Thats a sequence?
How'd you get that?
__________________
Big plans...
The)TideHunter( is offline   Reply With Quote
Old 10-26-2006, 02:51 PM   #5
Chuckle_Brother
Oh for the sake of fudge
 
Chuckle_Brother's Avatar


Respected User
 
Join Date: Dec 2005
Posts: 782

Submissions (2)

Chuckle_Brother will become famous soon enough (53)Chuckle_Brother will become famous soon enough (53)

Send a message via ICQ to Chuckle_Brother Send a message via AIM to Chuckle_Brother Send a message via MSN to Chuckle_Brother Send a message via Yahoo to Chuckle_Brother
Default

Rearrange it: 1,2,3,4,5,6

Edit: Good, this one looks like fun(by which I mean easy:)) so I think I will do it.
__________________
"...you play a mean banjo"

Last edited by Chuckle_Brother : 10-27-2006 at 01:40 AM.
Chuckle_Brother is offline   Reply With Quote
Old 10-26-2006, 06:55 PM   #6
BertTheJasser
xyzi - our universe
 
BertTheJasser's Avatar
 
Join Date: May 2005
Posts: 742

Submissions (2)

BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)

Default

No big deal, took me some minutes.
__________________
Note: Bye... I had a lot of fun here!
Special thanks to Vexorian who helped me learn jass, the real jass and always helped me when problems occured, I would call him somehow my mentor. Pipedream, who made amazing Grimoire and helped me acclerating my map (currently at 99% finished, no developement atm).

Vote for Linux Ports in general of Blizzard products: http://www.PetitionOnline.com/ibpfl/
BertTheJasser is offline   Reply With Quote
Old 10-26-2006, 06:58 PM   #7
Chuckle_Brother
Oh for the sake of fudge
 
Chuckle_Brother's Avatar


Respected User
 
Join Date: Dec 2005
Posts: 782

Submissions (2)

Chuckle_Brother will become famous soon enough (53)Chuckle_Brother will become famous soon enough (53)

Send a message via ICQ to Chuckle_Brother Send a message via AIM to Chuckle_Brother Send a message via MSN to Chuckle_Brother Send a message via Yahoo to Chuckle_Brother
Default

Yeah, same. I think Vex is losing it. It being his edge.

Edit: Where be your entry? Even if this is an easy problem you may as well scoop up some rep while you can.
__________________
"...you play a mean banjo"

Last edited by Chuckle_Brother : 10-26-2006 at 07:05 PM.
Chuckle_Brother is offline   Reply With Quote
Old 10-26-2006, 07:16 PM   #8
BertTheJasser
xyzi - our universe
 
BertTheJasser's Avatar
 
Join Date: May 2005
Posts: 742

Submissions (2)

BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)

Default

Quote:
Originally Posted by Chuckle_Brother
Edit: Where be your entry? Even if this is an easy problem you may as well scoop up some rep while you can.
What?
__________________
Note: Bye... I had a lot of fun here!
Special thanks to Vexorian who helped me learn jass, the real jass and always helped me when problems occured, I would call him somehow my mentor. Pipedream, who made amazing Grimoire and helped me acclerating my map (currently at 99% finished, no developement atm).

Vote for Linux Ports in general of Blizzard products: http://www.PetitionOnline.com/ibpfl/
BertTheJasser is offline   Reply With Quote
Old 10-26-2006, 07:28 PM   #9
blu_da_noob
Nonchalant
 
blu_da_noob's Avatar


Respected User
 
Join Date: Mar 2006
Posts: 1,933

Submissions (2)

blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)

[Quicksilver #2] - 2nd Place[Quicksilver#1] 1st place

Send a message via MSN to blu_da_noob
Default

Note: The challenge may not be simply solving the problem, but doing so in the fastest possible time. Algorithm efficiency is important.

Chuckle: Check your link, it has a message. The whole point isn't to post your solution for everyone to see, which was an absolutely marvelous idea there, because it's a competition. Everyone is supposed to submit a solution alone, without any help from other people so that it can be judged as a representation of your abilities.
__________________
blu_da_noob is offline   Reply With Quote
Old 10-26-2006, 07:29 PM
Vexorian
This message has been deleted by Vexorian. Reason: bah, blu
Old 10-26-2006, 07:33 PM
blu_da_noob
This message has been deleted by blu_da_noob. Reason: bah, vex
Old 10-26-2006, 07:35 PM   #10
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

yes?
Vexorian is offline   Reply With Quote
Old 10-26-2006, 07:36 PM   #11
blu_da_noob
Nonchalant
 
blu_da_noob's Avatar


Respected User
 
Join Date: Mar 2006
Posts: 1,933

Submissions (2)

blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)

[Quicksilver #2] - 2nd Place[Quicksilver#1] 1st place

Send a message via MSN to blu_da_noob
Default

We keep doing stuff at the same time which confuses the others' action >.<

So thanks for the 'apparently' psychic answer :P

(Question was: can we modify the data in udg_input in our function)
__________________

Last edited by blu_da_noob : 10-26-2006 at 07:38 PM.
blu_da_noob is offline   Reply With Quote
Old 10-26-2006, 08:25 PM   #12
Captain Griffen
Dread Lord of the Cookies
 
Captain Griffen's Avatar


Content Director
 
Join Date: Sep 2003
Posts: 5,375

Submissions (2)

Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)

Approved Map: Warlords[Quicksilver #2] - 1st Place

Default

Submitted.

Handy Tip

Bubble sort is by far the most effective for this.

__________________
Quote:
Originally Posted by Earth-Fury
Griffen is correct, you are not.
Quote:
[13:32] <Akolyt0r> hmm.. stil i want to have some unused women
Captain Griffen is offline   Reply With Quote
Old 10-26-2006, 09:53 PM   #13
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,177

Submissions (19)

Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default

Submitted.

I had to edit it just a few minutes afterwards, serves me right for not testing it. I hope Vex has the latest version.

Anyway, this one was almost absurdly simple.
__________________
Anitarf is offline   Reply With Quote
Old 10-27-2006, 01:38 AM   #14
Chuckle_Brother
Oh for the sake of fudge
 
Chuckle_Brother's Avatar


Respected User
 
Join Date: Dec 2005
Posts: 782

Submissions (2)

Chuckle_Brother will become famous soon enough (53)Chuckle_Brother will become famous soon enough (53)

Send a message via ICQ to Chuckle_Brother Send a message via AIM to Chuckle_Brother Send a message via MSN to Chuckle_Brother Send a message via Yahoo to Chuckle_Brother
Default

I thought we were supposed to put it in the pastebin, no?

Quote:
because it's a competition
Oh well, it was simple so unless someone is REALLY bad, they would know how to do this.
__________________
"...you play a mean banjo"

Last edited by Chuckle_Brother : 10-27-2006 at 01:39 AM.
Chuckle_Brother is offline   Reply With Quote
Old 10-27-2006, 02:28 AM   #15
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

Yes, you were supposed to put it in the pastebin, but not link it.
__________________
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
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 06:19 PM.


Affiliates
The Hubb The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2017, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services