Any real programmers on BYOND? [Challenge]

Page: 1 2 3 4 5 6
ID:96360
 
Jun 3 2010, 12:08 pm (Edited on Jun 3 2010, 12:55 pm)
How many of you can solve the problem below? This is a personal challenge, but prizes (i.e. hosting) may be awarded at my discretion.

 
Problem 2:  Dog Exhibit

The dogs want to prove to the public that they are both smart and funny.  In
order to do this, Bessie has organized an exhibition that will be put on by the
dogs. She has given each of the N (1 < N < 100) dogs a thorough interview and
determined two values for each dogs: the smartness Si ( -1000 < Si < 1000) of
the dog and the funniness Fi ( -1000 < Fi < 1000) of the dog.
Bessie must choose which dogs she wants to bring to her exhibition.  She
believes that the total smartness ST of the group is the sum of the Si and,
likewise, the total funniness FT of the group is the sum of the Fi. Bessie wants
to maximize the sum of ST and FT , but she also wants both of these values
to be non-negative (since she must also show that the dogs are well-rounded; a
negative ST or FT would ruin this).  Help Bessie maximize the sum of ST and
FT without letting either of these values become negative.

Problem name:  exhibit

Input Format
* Line 1: A single integer: N.
* Line 2..1+N: Two space-separated numbers: Si and Fi

Sample Input
5
-5  7
8  -6
6  -3
2  1
-8  -5

Input Details:
You can expect input to be valid (i.e. there will be a valid solution with non-negative ST and FT).

Output Format
* Line 1:  A single integer represented the maximum sum of ST and FT such
that neither is negative (ST >= 0 and FT >= 0).

Sample Output
8

Output Details
The optimal sum of smartness and funniness for the given set of dogs is 8.



Feel free to publicly post your solutions here, on your own blog, or e-mail them to [email protected]

Bruteforcing is allowed but code will be tested against a corner case (i.e. N=100) which means there are 1.2676506e30 possibilities, so good luck with that ;]
Jun 3 2010, 12:14 pm
It's fine on my screen (1680x1050 with firefox 3.6.3) but I just decreased the font size- still happening for you?
Jun 3 2010, 12:19 pm
Just dropped the text size some more, hopefully that's better.
Jun 3 2010, 12:22 pm
I'm using Opera on a 1024x768, it looks fine.
Jun 3 2010, 12:24 pm
It was going off the screen because I enclosed the text in <pre> tags because I copied it out of my PDF.

This question comes from a programming competition I was in a few months back and is likely the easiest of the six. If this is solved, we'll go on to another.
Jun 3 2010, 12:29 pm
Grrr, I thought I was done with school for the summer. Some of what the problem wants from me, I really don't even understand (specifically everything past the actual word problem). Guess I'm not a "real" programmer, not that I ever thought I was. I've never done anything outside of BYOND.
Jun 3 2010, 12:30 pm
Maybe I'll write something later, but for now, clarify:

1) The input looks needlessly complicated; why not use a list for the dogs?
2) What about cases where a negative value is inevitable? Such as when N=1 and only dog is (-1,-1).
Jun 3 2010, 12:33 pm (Edited on Jun 3 2010, 12:47 pm)
@Fugsnarf:
Effectively there are N dogs and each dog has two attributes, S and F. You want to pick M dogs that will provide the largest T, where T is the sum of each dog's S (ST=sum(Si)) and F (FT=sum(Fi)); that is, T=ST+FT. However, neither ST nor FT may be negative (if they could, the solution would be trivial).

@Toadfish:
Welcome to the real world, where data is often given in CSV (or similar) files. There is no such thing as a "list" in a plaintext file.

@Neblim:
Yes, funness, but Firefox told me it was not a word so I guess I changed it in one place- my bad. F is always the same thing, there is no "funny" and "fun" as seperate variable, I will correct this.
Jun 3 2010, 12:34 pm
That's nonsense Airjoe, the problem here is finding the optimal algorithm; not handling inputs.
Jun 3 2010, 12:36 pm
If you can't read in a plaintext file you have much bigger problems. This is about following specifications and providing a solution. If you don't like it, don't participate.
Jun 3 2010, 12:37 pm
You seem to be missing the point. But okay, I won't.
Jun 3 2010, 1:11 pm
I'm bruteforcing it no matter how much you try and discourage the use of it!
Jun 3 2010, 1:33 pm
So wait, how do you want this done? In a certain language? As psuedo-code? Also, must input really be handled (it's more of an annoyance rather than an issue, but still). If input must be handled, is each dog's info in a separate file, or the same file?
Jun 3 2010, 1:35 pm
Preferably BYOND, but it's really up to you (again, personal challenge). I'm just curious to see how many people on BYOND are capable of solving a simple algorithm design problem like this. Crashed has written a bruteforcer in Python, though it can't handle sets larger than about 15 right now. My original solution was in C++ and could easily handle the N=100 corner case. I'm porting my solution to DM now. Pseudo-code would be acceptable, but could you test it?

Input should be handled as given, though I'm not sure why this is tripping anyone up. The input is in a single file, as per the Input Format described above. The first line is the number of lines ("dogs") in the input file, and each following line contains two values, separated by one space, as S and F respectively.
Jun 3 2010, 1:52 pm
Is there a time limit for this challenge, or will it run as long as you feel like running it?
Jun 3 2010, 1:54 pm
No time limit at all. First person to solve it gets kudos, though! ;p
Jun 3 2010, 2:04 pm
For anyone having trouble reading in lines one by one, here's a simple function to get you on track:
proc{
    getLines(T){
        var/pos=1;
        while(findtext(T,"\n",pos)){
            world<<copytext(T,pos,findtext(T,"\n",pos));
            pos=findtext(T,"\n",pos)+1;
        }
    }
}


I had forgotten how poor BYOND's file-io is.
Jun 3 2010, 4:54 pm
Test this out:

http://www.byond.com/members/cbgames/files/DogExhibit.zip

You can use a text file via the file menu.

I am aware that the tab on the inputs and buttons are not working right.

It did manage to give the right answer for the example but thats as far as I got with testing.
Jun 3 2010, 5:17 pm
I can't seem to get your "Via File" functionality to work. I load the file and nothing happens.
Jun 3 2010, 10:50 pm
Not sure I completely understand, but here we go..

mob/verb/SortDogs()
    var/list/Si = new/list
    var/list/Fi = new/list
    for(var/n=1,n<100,n++)
        Si["Dog#[n]"] += rand(-100,100)
        Fi["Dog#[n]"] += rand(-100,100)
    var/list/ListOrder = new/list
    var/list/NCut = new/list
    for(var/n = 1 to length(Si))
        var/Dog = Si[n]
        var/tempSi = Si[Dog]
        var/tempFi = Fi[Dog]
        if(tempSi >= 0 && tempFi >= 0)
            var/N = (tempSi+tempFi)-abs(tempSi-tempFi)
            var/nm = 1
            while(nm <= length(ListOrder))
                if(NCut[ListOrder[nm]] <= N)
                    break
                nm += 1
            NCut[Dog] = N
            ListOrder.Insert(nm,Dog)
    var/TX = ""
    for(var/n = 1 to length(ListOrder))
        var/Dog = ListOrder[n]
        var/tempSi = Si[Dog]
        var/tempFi = Fi[Dog]
        var/tempN = NCut[Dog]
        TX += "[n == 1 ? "":"<br>"][Dog] (Si:[tempSi]; Fi:[tempFi]; N:[tempN] )"
    src << browse(TX,"window=Dogs")


First, it generates ya a list of 100 dogs with random Si and Fi. Then it goes through that random list and uses N which is the dogs Si pluss it's Ni then minus it's Si and Fi difference(absolute Si - Fi). I think that's what you were asking for >.<?

Then it just adds the ordered list to a text so it can be displayed in a browser all fancy like.

*edit* I just noticed something about double spacing format? If you want I can redo it in that format although that just seems a pain =)?
Page: 1 2 3 4 5 6