Any real programmers on BYOND? [Challenge]

Jun 4 2010, 1:08 am
Ulterior Motives	This kind of relates to this, but is mostly off topic and for Airjoe. I'm looking for some type of e-book or website that can help teach me advanced math used for programming. Schnitzelnagler said that you might know of such a thing. If you can point me in the right direction it would be very helpful. =)

Jun 4 2010, 3:16 am
Cbgames	Airjoe wrote: I can't seem to get your "Via File" functionality to work. I load the file and nothing happens. It works for me so I not sure why its not working for you.

Jun 4 2010, 8:46 am
Airjoe	Cbgames: Maybe I'm not doing it correctly. I have a file, input1.txt, in the same folder as your dmb and rsc. I open your dmb, go to the file menu, and open that file. Then, nothing happens. Do I need to put in the number of dogs and then load the file? Maybe it's an OS problem, I'm running on windows 7.

Jun 4 2010, 9:15 am (Edited on Jun 4 2010, 9:35 am)

Cbgames

Airjoe wrote:

Cbgames: Maybe I'm not doing it correctly. I have a file, input1.txt, in the same folder as your dmb and rsc. I open your dmb, go to the file menu, and open that file. Then, nothing happens. Do I need to put in the number of dogs and then load the file? Maybe it's an OS problem, I'm running on windows 7.

Its just the file with the stuff formated in the same way as the sample input.

It runs on Win7 as I made it and tested it on Win7. Send me a copy of the file and I see if its something I am doing wrong with the file handling.

Edit:
Try this one: http://www.byond.com/members/Cbgames/files/DogExhibit_2.zip

Jun 4 2010, 9:40 am
Geldonyetich	I really don't think I'd want to program something with a requirement that it helps Bessie lie about the smartness or funniness of her dogs.

Jun 4 2010, 9:47 am

Airjoe

@Geldonyetch:
It doesn't require Bessie to lie, it requires Bessie to pick the smartest and funniest most well rounded dogs.

@Cbgames:
I am using a file with just the following content:
10
-192 589
-817 407
-733 -950
685 81
-177 -807
-280 -447
-959 28
330 -418
636 825
254 -270

When I run this file, your program says "Please wait..." and has done so for 60 seconds so far, I'll leave it running to see what happens...

Jun 4 2010, 9:54 am
Geldonyetich	I see, so the input is the number of dogs, followed by lines of the smartness of funniness of each dog (separated by a space). After the last dog is output, the sum of smartness/funniness dog is output (so long as neither smartness or funniness for that dog is negative). This being an algorithm test, the goal is to do all this work efficiently. Do I have it right?

Jun 4 2010, 9:56 am
Airjoe	Ah, it seems your program expects the numbers to be separated by two spaces (which is also how my sample input above is formatted, but it shouldn't have been). I'll change my file and check your solution again.

Jun 4 2010, 9:59 am
Cbgames	Was about to say that. http://www.byond.com/members/Cbgames/files/DogExhibit_3.zip should be able to deal with single and double spaces. Answer 2624? It should look something like this if it works: http://www.byond.com/members/Cbgames/files/dog_res1.png

Jun 4 2010, 10:03 am

Airjoe

Geldonyetich:
You are correct about the input. The only thing you output is the largest number T which is the sum of Si and Fi of M dogs. So, for the sample input given:

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

I expect you to output:
8

Of the N (5) dogs, I expect you to find M whose values of S and F will sum to 8. So for this sample, you need to determine what M is and pick those M. We might choose the -5 7 dog and 8 -6 dog for a sum T of 4 and neither ST or FT is negative, but this is not our maximum. So to find our T of 8, which dogs might we pick? We can use the -5 7 dog, the 6 -3 dog and the 2 1 dog to sum to (3 + 5)=8.

Jun 4 2010, 10:22 am (Edited on Jun 4 2010, 10:55 am)

Geldonyetich

My chosen approach is to use an Insert sort, a typecast input proc to make sure the data is of appropriate type, and an interface on an object to assure the data falls into appropriate levels.

[Edit: Small modification added to suit the number of dogs requirement and prevent the code from breaking in the event somebody enters a number of dogs less than 1.]

I'm going a little outside of the project specs in two ways. First, I decided to avoid text operations when we had the more elegant input proc available. Second, I added a whole new data type not in the exercise (Name) and a more comprehensive output due to user friendliness concerns: it doesn't make a lot of sense that Bessie would be able to identify the dog on the sum alone or understand why it is that she's getting "0" back as a reply if there are no suitable candidates.

dog
    var/name 
    var/smartness
    var/funiness
    var/sumOfSmartAndFunny
    
    New (var/newName,var/newSmartness,var/newFuniness)
        
        name = newName
        smartness = newSmartness
        if (smartness > 999) smartness = 999
        if (smartness < -999) smartness = -999
        funiness = newFuniness
        if (funiness > 999) funiness = 999
        if (funiness < -999) funiness = -999
        sumOfSmartAndFunny = smartness + funiness
        
world
    mob = /mob/bessie
            
mob/bessie

    var/list/dog/dogList
    
    Login()     
        usr << "Type \"DogContest\" to begin."
        ..()

    verb/DogContest()
        
        set src = usr
        
        var/numberOfDogsToEnter = input("How many dogs are we considering, Bessie?","Dog Count","2") as num
        
        if (numberOfDogsToEnter < 2 || numberOfDogsToEnter > 99)
            usr << "The number of dogs to enter must be between 2 and 99.")
            return()        

        dogList = new/list()
        
        for (var/dogCount = 1, dogCount <= numberOfDogsToEnter,dogCount++)
            
            var/newDogName = input("Enter dog [dogCount]'s name","Name: dog [dogCount]") as text
            var/newDogSmartness = input("Enter dog [dogCount]'s smartness","Smartness: dog [dogCount]") as num
            var/newDogFuniness = input("Enter dog [dogCount]'s funiness","Funiness: dog [dogCount]") as num
    
            var/dog/newDog = new(newDogName,newDogSmartness,newDogFuniness)
            
            if (newDog.sumOfSmartAndFunny < 1 || newDog.smartness < 0 || newDog.funiness < 0 || dogList.len < 1)
                dogList.Add(newDog)
            else
                
                var/dogAdded = 0
                
                for (var/comparedDogIndex = 1,comparedDogIndex <= dogList.len,comparedDogIndex++)
                    var/dog/comparedDog = dogList[comparedDogIndex]
                                    
                    if (comparedDog.sumOfSmartAndFunny < newDog.sumOfSmartAndFunny)
                        dogList.Insert(comparedDogIndex,newDog)
                        dogAdded = 1
                        break
                
                if (dogAdded == 0)
                    dogList.Add(newDog)
        
        var/dog/idealDog = dogList[1]
        
        if (idealDog.sumOfSmartAndFunny < 1 || idealDog.smartness < 0 || idealDog.funiness < 0)
            usr << "There is no ideal dog to showcase."
        else
            usr << "The ideal dog to showcase is [idealDog.name] with a sum of [idealDog.sumOfSmartAndFunny]."

Jun 4 2010, 11:05 am

Airjoe

Geldonyetich: The reason for the input format is for ease of batch processing. Your input functions may be "elegant", but I'm certainly not going to enter the smartness and funniness of 99 dogs. Secondly, based upon your code, it seems you are choosing a single dog. If you read what I wrote below again, you are not picking a single dog, but M dogs, where M is arbitrary. You are to choose the M dogs and take the sum of their F and S to find the greatest T.

Jun 4 2010, 11:15 am

Geldonyetich

The reason for the input format is for ease of batch processing. Your input functions may be "elegant", but I'm certainly not going to enter the smartness and funniness of 99 dogs.

I thought that likely. The code is designed to allow that: you just replace the three input with the lines to substitute values for newDogName (you could just make that "Dog 1" or whatever), newDogSmartness, and newDogFuniness. It'd be a very easy fix if I had a little more details:

Exactly how are you planning on doing this? Just cutting/pasting directly into the input field probably wouldn't work, unless you were going to do it on a line-by-line basis. Even so, somewhat tricky to do because BYOND needs to route it to an appropriate verb. If you were going to parse a file, you'd need to make modifications anyway, or else provide us the file so we'd know exactly how it needs to be parsed.

If you read what I wrote below again, you are not picking a single dog, but M dogs, where M is arbitrary.

Written where? It's not in your blog post. No wonder we're confused, right?

Again, something I anticipated and so the code is actually built to easily handle that. I just take as many members out of dogList as are needed, because it is always sorted from best-to-worst candidate.

Jun 4 2010, 11:21 am

Airjoe

Geldonyetich wrote:

Exactly how are you planning on doing this? Just cutting/pasting directly into the input field probably wouldn't work, unless you were going to do it on a line-by-line basis. If you were going to parse a file, you'd need to make modifications anyway, or else provide us the file so we'd know exactly how it needs to be parsed.

The blog post contains sample input as it would appear in a file. Earlier I posted a function for reading text line by line.

Written where? It's not in your blog post. No wonder we're confused, right?

Written in the blog post: "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)."

All of the other submissions understood that multiple dogs are to be chosen, you are the only one confused here.

Again, something I anticipated and so the code is actually built to easily handle that. I just take as many members out of dogList as are needed, because it is always sorted from best-to-worst candidate.

And I can guarantee you that this will not work. You can't simply be greedy. Imagine a dog with S=500 and F=-300 amongst a few other dogs with S=range(-10,10) and F=range(-10,10). You would choose the first dog because his sumOfSmartAndFunny is 200, but this leads to the FT being negative.

Jun 4 2010, 11:28 am (Edited on Jun 4 2010, 11:39 am)

Geldonyetich

Airjoe wrote:

Written in the blog post: "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)."

You hopefully can understand why I'd be tripped up when you needed to bold face several words out of separate sentences in order to communicate the idea. "Group" is really ambiguous, "choosing which dogs" makes no sense until a greater context is understoood, and without understanding the idea you don't know what's really being "sum"ed here.

I think I see what you want now... your overall goal is to maximize the Smart and Funiness sum across a range of dogs instead of just isolate a number of dogs with the best sum of Smart and Funiness without allowing either sum to reach a negative number. That's a bit more interesting than what I thought the original problem was.

And I can guarantee you that this will not work. You can't simply be greedy. Imagine a dog with S=500 and F=-300 amongst a few other dogs with S=range(-10,10) and F=range(-10,10). You would choose the first dog because his sumOfSmartAndFunny is 200, but this leads to the FT being negative.

You actually didn't notice where I already wrote the algorithm with that in mind? It doesn't bother to insert-sort these non-candidates, it tosses them in the back of the list and refuses to output them in the end.

Of course, I was operating under the idea that you only needed a single dog, so a different approach is needed.

Jun 4 2010, 11:31 am

Airjoe

Geldonyetich wrote:

You actually didn't notice where I already wrote the algorithm with that in mind? It doesn't bother to insert-sort these non-candidates, it tosses them in the back of the list and refuses to output them in the end.

If you're referring to:

            if (newDog.sumOfSmartAndFunny < 1 || newDog.smartness < 0 || newDog.funiness < 0 || dogList.len < 1)
                dogList.Add(newDog)

That is also wrong, as it is certainly possible to choose a dog that has a negative attribute. Please refer again to my comment #34:
"We can use the -5 7 dog, the 6 -3 dog and the 2 1 dog to sum to (3 + 5)=8."

The only way to get the maximum T from the sample input is to choose dogs that have negative attributes, dogs which you discard.

Jun 4 2010, 11:42 am (Edited on Jun 4 2010, 11:56 am)

Geldonyetich

Airjoe wrote:

If you're referring to:

>             if (newDog.sumOfSmartAndFunny < 1 || newDog.smartness < 0 || newDog.funiness < 0 || dogList.len < 1)
>                 dogList.Add(newDog)
>

That's only the lesser half of it. The better part is where the actual insert sort occurs.

But, again, since we're now looking at a sum of several dogs, and this was coded with a false understanding that what you wanted was a list of single best candidates, clearly a different approach will be needed.

The comprehensive answer involves simply looping through every possible combination of candidates and returning the highest sums (as long as they're positive), but I get a feeling that you're all coiled up to call that answer wrong, because you know of a more efficient way.

Call me a non-real programmer, but knowing you're luring me into what basically amounts to trick question based off of some esoteric algorithm you picked up somewhere, I really don't see why I should bother to try.

Jun 4 2010, 11:54 am
Airjoe	Geldonyetich wrote: The comprehensive answer involves simply looping through every possible combination of candidates and returning a the best answer, but I get a feeling that you're all coiled up to call that answer wrong, because you know of a more efficient way. This is effectively bruteforcing and though it will only work with small sets. A more efficient method does exist.

Jun 4 2010, 12:06 pm (Edited on Jun 4 2010, 1:27 pm)

Geldonyetich

Airjoe wrote:

This is effectively bruteforcing and though it will only work with small sets. A more efficient method does exist.

Well, I guess it is fair enough, not completely a trick question, that you did specifically warn us against "bruteforcing" it.

Clearly, what you'd have to do is isolate the best candidates first, based off of the desired number of results, before the main sort occurs. However, the specifics of what makes a best candidate is likely a mathematical shortcut which isolates an easy set of impossibilities.

Truth to be told, I don't like programming in terms of mathematical shortcuts. I prefer to keep things more flexible to possibilities, even if the program would never use those possibilities and it's not all that efficient.

I'm not sure I'd say this makes me an "unreal" programmer, but it does make me a different type of programmer than one who is more interested in optimal machine resource utilization. A good programming team would have both.

If I had to do this for a job, I'd probably have a reference of answers to look up somewhere. It's likely a specific kind of sorting algorithm.

Jun 4 2010, 1:02 pm
T3h B4tman	BTW Airjoe, I've completed this in Javascript.