Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Skyrunner]

I don't know how to dynamic programming D:

How would one go about solving this sort of problem?

A farmer has a row of stalls for housing cows and bulls. She’s already placed each of her cows in a stall so now she has to place her bulls. The bulls need to have a minimum number of stalls between them. The stalls are numbered in increasing order. Write a function can_place_bulls that takes
l, a list of integers. The integer is the number of an empty stall.
n, an integer representing the number of bulls to place.
d, an integer representing the minimum number of stalls that should be between each bull (so if d = 0, you can place bulls in consecutive stalls).
and returns True if it is possible to place all the bulls in the stall as specified above and False otherwise.

While I'm not in comp sci right now, my friend has this as one of her practice problems for the finals; while I've never figured out how to solve dynamic programming-y problems, but I'd like to try.

[karhell]

Code: [Select]

def can_place_bulls(l, n, d):
    return True #Total number of stalls unspecified; assuming infinite row

Or more seriously, you'll need to check that l has enough stalls to place n bulls, then test if there are n stalls in l that are >d distance of other stalls in l.

Not sure whether that clarifies anything... Hope it helps a bit

[Skyrunner]

Technically your joke answer is incorrect.

If L is [] that means the potentially infinite number of stalls are all full, so False is the correct answer.

The problem I'm having is that it seems you would have to test many combinations of bull placement, rather than it being straightforward. :/

Maybe I'm just not thinking of it correctly.

[karhell]

yeah, the joke answer was written before I realised that L is the list of empty stalls >.>

The approach I'd take is to sort the list first, then iterate checking only the two nearest neighbours for a value difference <d (keeping an eye out for IndexErrors, of course )

[Reelya]

Technically your joke answer is incorrect.

If L is [] that means the potentially infinite number of stalls are all full, so False is the correct answer.

The problem I'm having is that it seems you would have to test many combinations of bull placement, rather than it being straightforward. :/

Maybe I'm just not thinking of it correctly.

You would not have to test multiple combinations. Say that # is open, X is used, and minimum distance must be 3:

Code: [Select]

12345
##XX#

You could place your first bull in slot 1 or slot 2. If slot 2 was the correct starting point for maximum bulls, then slot 5 would be the next earliest possible slot. But it would by necessity also be the next possible slot if you placed your first bull in slot 1. So picking slot 2 over slot 1 to start with can never fit more than choosing slot 1. Slot 1 could theoretically fit more in that picking slot 2 however, because slot 4 might be available.

Therefore putting your first bull in the first free slot is guaranteed to be at least equal to the best solution. At this point however we're left with a new "next possible slot", and the same logical argument as above can be applied to show that we should place our next bull in that slot, and so on: always picking the first available slot guarantees you the most bulls fitted in.

[MagmaMcFry]

I don't know how to dynamic programming D:

How would one go about solving this sort of problem?

A farmer has a row of stalls for housing cows and bulls. She’s already placed each of her cows in a stall so now she has to place her bulls. The bulls need to have a minimum number of stalls between them. The stalls are numbered in increasing order. Write a function can_place_bulls that takes
l, a list of integers. The integer is the number of an empty stall.
n, an integer representing the number of bulls to place.
d, an integer representing the minimum number of stalls that should be between each bull (so if d = 0, you can place bulls in consecutive stalls).
and returns True if it is possible to place all the bulls in the stall as specified above and False otherwise.

While I'm not in comp sci right now, my friend has this as one of her practice problems for the finals; while I've never figured out how to solve dynamic programming-y problems, but I'd like to try.

If you find you can't use the method directly for dynamic programming even though it looks like dynamic programming, usually you just need more parameters. In this case add another parameter k, which is the minimum allowed position of a bull.

Code: [Select]

bool canPlaceBulls (vector<int> l, int n, int d) {
   sort(l);
   return canPlaceBulls(l, n, d, l[0]);
}
bool canPlaceBulls (vector<int> l, int n, int d, int k) {
    //<insert something purely recursive here>
}


[miauw62]

Cool, another thing I never heard of. Off to Google I go then. Thanks for the example.

Bounds-checking is just making sure you're not accessing an index 5 when your array size is 4, that sort of stuff.

[Sergarr]

What's the best type of array organization speed-wise, if I have to find the highest one, discard it, add a bunch of new numbers to the array and then repeat?

[MagmaMcFry]

That would be a heap.

[Spehss _]

So what are templates good for? From what I've seen of examples of it online I guess it's good for being able to process a range of variables without needing to be specified, like it can take ints or doubles or chars instead of having to define several functions for each variable type that all do the same thing.

Spoiler (click to show/hide)

Code: [Select]

template <class T> class grid
{
    T *data;
public:
    int sizex, sizey;

    grid(int _sizex, int _sizey) : sizex(_sizex), sizey(_sizey)
    {
        data = new T[sizex * sizey];
    }

    ~grid() { delete [] data; }

    T &operator[](int x, int y) { return data[x + sizex * y]; }
}

// usage:
grid<char> charArray2D(20,20);

grid<mapTile> mapArray2D(80,25);


You can add anything you want to this, e.g. bounds-checking. But I designed this for access speed, so it assumes you've already screened your inputs.

Also Reelya, all I can find of "c++ grid class" is webpages for the Stanford cslib package. So I guess if I wanted to use grid I'd need to download the cslib package and #include the header file? Or am I completely misunderstanding your example with the template and grid?

[MagmaMcFry]

So what are templates good for? From what I've seen of examples of it online I guess it's good for being able to process a range of variables without needing to be specified, like it can take ints or doubles or chars instead of having to define several functions for each variable type that all do the same thing.

That's exactly what they're good for. Without templates, generic programming would be waaaay more annoying.

[alway]

So what are templates good for? From what I've seen of examples of it online I guess it's good for being able to process a range of variables without needing to be specified, like it can take ints or doubles or chars instead of having to define several functions for each variable type that all do the same thing.

That's exactly what they're good for. Without templates, generic programming would be waaaay more annoying.

In short, templates are compiler-level voodoo which automatically generates copies of a function at compile time. So under the hood:

Code: [Select]

template <class T> void foo( T dataIn ) { doStuff; }
char A;
int B;
int C;
foo<char>(A);
foo<int>(B);
foo<int>(C);
is transformed by the compiler into

Code: [Select]

void foo( char dataIn ) { doStuff; }
void foo( int dataIn ) { doStuff; }
char A;
int B;
int C;
foo(A);
foo(B);
foo(C);
So it's sort of a built-in automatic code generation tool that compiles down into regular functions automatically. And if you don't use it at all, it just compiles down to nothing. Or something similar to that IIRC. So it's basically a method to prevent you from needing to rewrite the same code over and over simply because you happen to use both 'short' and 'int' in your calculations, or some similar case.

[i2amroy]

Indeed. And as people have noted, it's also virtually essential if for some reason you need to make your own data structure, since else wise you'd need to do something like make a tree for every single object type in the entire project.

[Spehss _]

So I was making a basic program based off of some example thing I read in a book on artificial intelligence. Long story.

anyway, it keeps crashing, and I'm not sure why. Depending on how I have the for loop in main set, it crashes either immediately after the user inputs the value of total_people or once the for loop int i gets down to 1 person remaining in the vector of people.

Spoiler: c++ code (click to show/hide)

Code: [Select]

#include <iostream>
#include <vector>

using namespace std;

class person    //stores person's name and infection status
{
    public:
        string person_name;
        string target_name; //the person they kiss
        bool infected=false;
};

person get_name(person x)   //gets a person's name
{
    cout<<"What is this person's name? ";
    cin>>x.person_name;
    return x;
}

person get_kiss(person x)
{
    cout<<"Who does this person kiss? ";
    cin>>x.target_name;
    return x;
}

//##############################################
//##############################################
int main()
{
    int total_people=0;
    cout<<"How many people? ";
    cin>>total_people;
    vector<person> people_list(total_people);
    for(int i=total_people; i>=0; i--)
    {
        people_list[i]=get_name(people_list[i]);
        cout<<"This person's name is: "<<people_list[i].person_name<<endl;  //debug
        people_list[i]=get_kiss(people_list[i]);
        cout<<"This person's name is: "<<people_list[i].person_name<<endl;  //debug
        cout<<"This person will kiss: "<<people_list[i].target_name<<endl;  //debug
        if(i>0)
            cout<<"Moving on to the next person. There are "<<i-1<<" people remaining to be defined.\n"<<endl;
        else if(i<=0)
            cout<<"All people have been defined and stored in memory."<<endl;
    }
    return 0;
}


[Reelya]

An array/vector of size "n" is always counted from 0 to n-1. This is because "myArray" is a pointer to the first allocated element, and the index is actually how many places beyond the start to access. if you count down, it must be from n-1 to zero. if you read/write past the end of an array, the results are undefined and may or may not crash unexpectedly.

I'd also suggest making the "getname" methods part of the classes to simplify all the copying/passing values.

"cin" also has usability issues. if you are asked cin>>number and type a non-number then things will go shitty, and cin will no longer work after that. You need to call cin.clear() and cin.ignore() after getting an int from cin. Here's an example:

Code: [Select]

int num1, num2;
cout<<"type a number? ";
cin>>num1;
cout<<"type another number? ";
cin>>num2;
e.g. you'd expect that this would work:

Code: [Select]

int num1=0;
while(num1 < 1 || num1 > 10)
{
    cout<<"Enter a number from 1 to 10? ";
    cin>>num1;
}

And it will work. If you pass an int from 1-10 in, it will leave the loop. if you pass an int that's outside the range it will loop back and ask again. But try typing "foo" and the shit hits the fan with an infinite loop, until you change it to this:

Code: [Select]

int num1=0;
while(num1 < 1 || num1 > 10)
{
    cout<<"Enter a number from 1 to 10? ";
    cin>>num1;
    cin.clear();
    cin.ignore(256, '\n');
}