JASS quicksilver contest Round #1 (winners announced)

10-16-2006, 08:27 PM

Hello, let's see what's the deal here, remember the JASS survival challenge? Why did it fail? I think that it is because It required me to deal with up to 3 contests at the same time and I wasn't even able to deal with 2 of them, then I also had 2 think a lot of problem statements and make sure they had a very fair difficulty classifcation which was, seriously too difficult.

Yet I notice we need contests. So I am introducing you all these ones which are shorter and less fixed to some rules that made it impossible for me to do stuff.

Rules
- I release a problem.
- People try to solve
- Up to 1 week to get results
- Post solutions in pastebin, with a [quicksilver] preffix.
- 3 Fastest (take less time) solutions that solve the problem win.
- If somebody is too good I can classify him as too good for a round that would seem too easy for him, so more people have a chance.

Round one: The polish

There is an strange arithmetic language out there with these symbols:

+ : addition
* : product
! : factorial
(lowercase letter) (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z) : variable

A valid formula is :
- A variable (lowercase letter)
- ! preceding a valid formula
- + preceding 2 valid formulas
- * preceding 2 valid formulas

You have to make a function LargestValidFormula takes string symbols returns string
It takes a string with 1 to 100 characters containing some characters and returns the largest valid formula you can get with the symbols in the input (without repeating any of them)

If there are more like one result, either is a correct answer.

Examples

LargestValidFormula("a") returns "a"

LargestValidFormula("a+b") returns "+ab" or "+ba"

LargestValidFormula("+*!aa") returns "!+aa" or "+!aa" or "+a!a" or "!*aa" or "*!aa" or "*a!a"

LargestValidFormula("abcdefg!") returns "!b" or "!a" or "!c" , etc

LargestValidFormula("+++aaaa") returns "+a+a+aa" or "++aa+aa" or "+++aaaa"

LargestValidFormula("A") returns ""

Edit: The results of the survival challenge will come up eventually and we will have awards there.

Update : October 24th: Results announced

First place: Blu_da_noob (0.037267028 seconds)
Second place: Acehart (0.085897792 seconds)

Disqualified:
- Griffen (wrong answer)
- Mathias (Limit op exceeded)

The answer
It was rather easy, the first thing you could notice is that the only case in which "" is returned is when there are no variables in the input.

Then you can figure out that all the unary operators can be added simply before a variable to get the result.

And that if you unify a binary operator and a variable they can become an unary operator so they follow above's rule.

This is my solution:

JASS:

globals
 string factorialchars = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" 
 string prodchars      = "****************************************************************************************************"
 string pluschars      = "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"
endglobals
function LargestValidFormula takes string s returns string
 local string c
 local string r=""
 local integer i=0
 local integer L =StringLength(s)

 local integer plus=0
 local integer prod=0
 local integer fact=0
 local string  vars=""
 local integer varn
 

    loop
        
        exitwhen i==L
        set c=SubString(s,i,i+1)
        set i=i+1

        if (c=="!") then
            set fact=fact+1
        elseif (c=="+") then
            set plus=plus+1
        elseif (c=="*") then
            set prod=prod+1
        elseif (StringCase(c,true)!=c) then
            set vars=vars+c
        endif
    endloop
    set varn=StringLength(vars)

    if (varn==0) then
        return ""
    endif

    if ( varn > plus+prod) then
        set varn=plus+prod+1
    else
        set i=varn-1
        if (plus>=i) then
            set plus=i
            set prod=0
        elseif (prod>=i) then
            set prod=i
            set plus=0
        else
            set plus=i-prod
        endif
    endif


 return SubString(factorialchars,0,fact)+SubString(pluschars,0,plus)+SubString(prodchars,0,prod)+SubString(vars,0,varn)
endfunction

In order to save the game some time, I avoid creating strings during the process so I only use counters, the variables part must use strings though.
In this case the binary + variable becomes unary is still latent, but I just have it work as (binary)(exp)(variable) instead of (binary)(variable)(exp) it works the same.
Then the result is always: (All the unary operators)( (x - 1) binary operatos )( x variables ) , where x depends on the input. Unless, there are no variables in the input then the result is ""
Calculating x is the last problem, if there are more variables than binary operators, then x is (number of binary operators)+1 , else it is the number of variables present in the input and the number of binary operators in the output should change to x-1.

- Mathias, used a brute force approach, although it is not the fastest solution it is a good idea to check it in order to see how brute force works.

- Griffen's submission would have been the fastest if it wasn't for the error.

I am including a map with the test environment and all the submissions.

Attached Files

quicksilver.w3x (56.6 KB)

10-16-2006, 09:32 PM	#2
Captain Griffen	confused

10-16-2006, 10:07 PM	#3
UnMi	... ... ... Unlike the last two Problems you used to post, I do not understand a single bit of this one.

10-16-2006, 11:28 PM

SeasonsOfLove

I understand the problem.
You're given a string with a bunch of symbols, all of which are either a variable (lowercase letter), an !, a *, or a +. You have to find the longest valid formula, which involves:
A variable (a)
A ! preceding one valid formula (!a, !+ab, !*ab)
A * or + preceding two valid formulas (*ab, +ab, *!a!b, +*!a!b*!a!b)

The hardest part for this is figuring out what he means by the question. Once you get that, it should become easier to figure out.

10-16-2006, 11:45 PM	#5
Naakaloh	It's not to hard to understand; there's just one issue I'd like to confirm. Could the example "abcdefg!" return "!a", "!b", "!c", etc.?

10-17-2006, 01:14 AM

Chuckle_Brother

Yeah its pretty easy to understand, but implementation may be a bit more difficult.

Edit: Something I don't get though are what would be considered valid formulas, I am gonna have to write this all out based on your little priority table.

@Vex: You state "without repeating any of them", does this mean that if you have 3 ! in a symbol line for example you can use ! 3 times as Seasons seems to believe? Or can you use only one ! in the final product?

10-17-2006, 02:14 AM

Vexorian

Quote:

It's not to hard to understand; there's just one issue I'd like to confirm. Could the example "abcdefg!" return "!a", "!b", "!c", etc.?

Yes.

Quote:

@Vex: You state "without repeating any of them", does this mean that if you have 3 ! in a symbol line for example you can use ! 3 times as Seasons seems to believe? Or can you use only one ! in the final product?

You can use up to 3 "!" in that case

10-17-2006, 02:41 AM	#8
Chuckle_Brother	Ahh excellent. Many thanks for the clearup.

10-17-2006, 11:50 AM

DotA_DR

Quote:

- Post solutions in pastebin, with a [quicksilver] preffix.

pastebin - what it is?

10-17-2006, 12:09 PM	#10
Thunder_Eye	http://www.wc3campaigns.net/pastebin.php

10-17-2006, 03:41 PM

#11

Rising_Dusk

Quote:

Originally Posted by Vexorian

Yet I notice we need contests.

So why did noone start the next spell contest?
Sheesh. :/

10-17-2006, 03:57 PM	#12
moyack	YEAHHH, Spell contest!!! I need to make spells now!!

10-17-2006, 04:06 PM

#13

Fulla

Quote:

Originally Posted by Rising_Dusk

So why did noone start the next spell contest?
Sheesh. :/

Agreed

Was hoping to enter a jass spell :D

10-17-2006, 04:16 PM	#14
Rising_Dusk	I mean seriously, if people are too busy to start the spell sessions up again... I'll sacrifice my ability to partake in it and run it myself. Seriously though, we need spell sessions. They're always very popular and fun to participate in.

10-17-2006, 04:30 PM

#15

moyack

Quote:

Originally Posted by Rising_Dusk

I mean seriously, if people are too busy to start the spell sessions up again...
I'll sacrifice my ability to partake in it and run it myself.

Seriously though, we need spell sessions.
They're always very popular and fun to participate in.

I'm with Rising, besides I think that one of JASS objectives is to make custom spell, and the best way to make some honour to this language is with a spell contest.