DEVTOME.COM HOSTING COSTS HAVE BEGUN TO EXCEED 115$ MONTHLY. THE ADMINISTRATION IS NO LONGER ABLE TO HANDLE THE COST WITHOUT ASSISTANCE DUE TO THE RISING COST. THIS HAS BEEN OCCURRING FOR ALMOST A YEAR, BUT WE HAVE BEEN HANDLING IT FROM OUR OWN POCKETS. HOWEVER, WITH LITERALLY NO DONATIONS FOR THE PAST 2+ YEARS IT HAS DEPLETED THE BUDGET IN SHORT ORDER WITH THE INCREASE IN ACTIVITY ON THE SITE IN THE PAST 6 MONTHS. OUR CPU USAGE HAS BECOME TOO HIGH TO REMAIN ON A REASONABLE COSTING PLAN THAT WE COULD MAINTAIN. IF YOU WOULD LIKE TO SUPPORT THE DEVTOME PROJECT AND KEEP THE SITE UP/ALIVE PLEASE DONATE (EVEN IF ITS A SATOSHI) TO OUR DEVCOIN 1M4PCuMXvpWX6LHPkBEf3LJ2z1boZv4EQa OR OUR BTC WALLET 16eqEcqfw4zHUh2znvMcmRzGVwCn7CJLxR TO ALLOW US TO AFFORD THE HOSTING.

THE DEVCOIN AND DEVTOME PROJECTS ARE BOTH VERY IMPORTANT TO THE COMMUNITY. PLEASE CONTRIBUTE TO ITS FURTHER SUCCESS FOR ANOTHER 5 OR MORE YEARS!

Goat in a Field Problem

Many years ago, while I was at university, I was introduced to the “Goat in a Field” problem. This is a problem of intersecting circles. The farmer has a circular field (evenly covered in grass) and he is going to tether his goat to some point on the perimeter of the field. The problem is to work out how long the tether should be to allow the goat to eat exactly half the grass in the field.

goat1.jpg

Seemingly, this should not be a very difficult problem to solve. Or at least so I thought. However, despite being in the middle of doing a Physics degree at the time, I was entirely unable to solve it. For those that may be interested, the mathematical solution to this is available (like so many other things these days) on the internet at http://mathforum.org/dr.math/faq/faq.grazing.html or http://mathworld.wolfram.com/GoatProblem.html. If you take a look at these articles, you will see that the solution is insanely complicated. Looking at these I don’t feel so bad now for having being unable to solve the problem myself.

At the time (my university days) if I had had access to the articles I have referenced above, I would have eagerly attempted to understand the solutions being presented. I have to say that for me, those days are long gone. However, I do know how to program a computer, and in this article I am going to show you an easy way to solve the Goat in a Field problem using nothing more complicated that Pythagorus’ Theorem 1) (and a bit of computing power). We also have to use a sorting technique, so this article will be useful for anyone wanting to learn how to sort a set of data (in UNIX/C).

Computer Solution

The way we can work out the answer is really very simple. First we have to fill the field with a set of evenly spaced points (think of them as blades of grass). Then we have to work out the distance of each blade of grass away from the point on the perimeter of the field to which the goat is tethered (Pythagorus’ Theorem can do that). We then sort our blades of grass according to their distance from the goat. The distance of the blade of grass in the middle of our sorted list will be the answer!

For the purposes of the calculation we will define the field as having radius 1 unit. The centre of the field has grid reference 0,0 (x=0, y=0). The goat can be tethered at any point on the perimeter of the field, so for our calculation we will choose position x = -1, y = 0. Now let’s examine the steps in detail.

Filling the field with blades of grass

The question arises how to fill the field with evenly spaced blades of grass. My first thought was to work my way from 0 to 360 degrees (a fraction of a degree at a time) and choose a number of different distances between 0 and 1 for each angle. However, with a moments consideration I realized that this would not generate an even spread of points – they would be more clustered towards the centre of the circle.

I briefly considered just placing the blades of grass at random on the basis that if there are enough of them their positions will be near enough evenly spread. But I quickly realized there is a much simpler way – using a grid. If we draw a square around the field (this will be a 2 by 2 unit square) then all we have to do is use a nested loop to lay down points in the x and y directions. Obviously some of these points will not lie within the field. We can check this using Pythagorus’ Theorem – which as everyone has learned at school states that “the square on the hypotenuse is equal to the sum of the squares on the other 2 sides”. In this case the hypotenuse is the distance from the centre of the field, so we can simply discard points where the hypotenuse is greater than 1.

goat2.jpg

Calculate the distance of each blade from the goat

Here we are performing exactly the same sort of Pythagorus calculation that we made to check the blade of grass is inside the field, but instead of working out the distance from the centre of the field (coordinate 0,0) we instead work out the distance from the goat (coordinate -1, 0). We store the distance of each and every blade of grass away from the goat in a very large array.

Sort the array by distance

We now need to sort the distances we have collected into ascending numerical order. Fortunately the C library on a UNIX system has a built in function qsort to do this for you. All you have to do is write a function which qsort can use to compare 2 slots in your array. Thus depending on how you write your sort function you can sort in ascending order, descending order or in some other way if you have a special requirement. In our case we just want to sort in ascending order for which the sort function looks like this.

int distanceSort (double *first, double *second)
{
        if (*first < *second)
                return (-1) ;
        else
                return (1) ;

        return (0) ;
}

The qsort function then does all the hard work of worrying about which elements of the array to compare with which other elements, in an efficient way, until it has all the array elements sorted according to the rules laid down by the distanceSort function you provide it with.

Full program

For those that may be interested and would like to try this for themselves, here is the full program. As you can see, it is really quite a small program.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#include <unistd.h>

// now for a big array
static double distancePerimeter[4000000] ;

double getDistanceFromPosition(double x, double y, double px, double py)
{
        // all we need is a bit of pythagoras
        // px, py is our position and x,y is the position of the blade of grass

        double xSquared = (x - px) * (x - px) ;
        double ySquared = (y - py) * (y - py) ;
        double distance = sqrt (xSquared + ySquared) ;
        return (distance) ;
}
int distanceSort (double *first, double *second)
{
        if (*first < *second)
                return (-1) ;
        else
                return (1) ;

        return (0) ;
}


main (int argc, char **argv)
{
        int i = 0 ;
        int j = 0 ;
        int numPoints = 0 ;

        // generate points

        double percent = atof (argv[1]) ;

        for (i=0;i<2000;i++)
        {
                for (j=0;j<2000;j++)
                {
                        // Each coordinate is somewhere from -1.0 to + 1.0

                        double x = (double) i * 0.001 - 1.0 ;
                        double y = (double) j * 0.001 - 1.0 ;

                        // get distance from the centre of the field (position 0,0)

                        double distanceCentre = getDistanceFromPosition(x, y, 0.0, 0.0);
                        if (distanceCentre > 1.0)
                        {
                                // this blade of grass is not in the field
                                continue;
                        }

                        // Now get the distance from the edge of the field. We can
                        // choose any coordinate on the edge of the field (so long
                        // as we always choose the same point!)


                        double distPerimeter = getDistanceFromPosition(x, y, -1.0, 0.0) ;

                        distancePerimeter[numPoints++] = getDistanceFromPosition(x, y, -1.0, 0.0) ;
                }
        }

        // sort the blades of grass

        int (*sortfn)() = distanceSort ;
        qsort (distancePerimeter, numPoints, sizeof(double), sortfn) ;

        int percentPos = (double) numPoints / (100.0 / percent) ;
        printf ("Length of Tether = %f \n", distancePerimeter[percentPos]) ;
}

Results

For the goat to be able to eat half the grass in the field, we have to look at the middle (or 50%) value of our sorted array.

% time ./goat 50
Length of Tether = 1.158734
[2]    15795 exit 29    ./goat 50
./goat 50  0.72s user 0.11s system 97% cpu 0.845 total

Notice it does not take much time to come up with the answer. Runtime is less than a second. This is running on my approx 12 year old laptop installed with Centos 5, so hardly a powerful system.

If we compare this to the solution provided in http://mathworld.wolfram.com/GoatProblem.html which calculates the answer as 1.15872847, you can see we have a correct answer to 4 decimal places.

Answers to supplementary questions

Our computer solution to the problem also enables us to answer other related questions that could be asked about this sort of scenario, as follows.

Length of Tether to eat different proportions of the grass in the field

Because we have a sorted array we can now also investigate the required length of tether to be able to eat different proportions of the grass in the field. For the length of tether to be able to eat 25% of the grass we would look a quarter of the way along the array, for 75% we would look three quarters of the way along the array.

% ./goat 25
Length of Tether = 0.774741
[1]    15792 exit 29    ./goat 25
% ./goat 75
Length of Tether = 1.512060
[1]    15793 exit 29    ./goat 75

Proportion of grass that can be eaten if Tether is 1.0 long

You have to run the program a few times to find it, but after a bit of trial and error we can find out what percentage of the grass can be eaten if the tether is the radius of the field. It turns out to be 39.1% of the grass.

 % ./goat 39.1
 Length of Tether = 0.999998
 [1]    15794 exit 29    ./goat 39.1

Tether point somewhere else in the field

We can also investigate the length of tether needed if the goat is tethered not to the perimeter, but to some other point within the field. It is the work of a moment to change our program to enable this. All we have to do is allow the x,y coordinate at which the goat resides to be provided as arguments to the program

    double goatX = -1.0 ;
    double goatY = 0.0 ;

    if (argc == 4)
    {
        goatX = atof (argv[2]) ;
        goatY = atof (argv[3]) ;
    }

Then, in the call to the getDistanceFromPosition function where we are calculating the distance of the goat from the blade of grass, we pass in these coordinates

            distancePerimeter[numPoints++] = getDistanceFromPosition(x, y, goatX, goatY) ;

Let’s predict what the answer should be if the goat is tethered to the centre of the field. This is of course a very simple scenario, where there are no intersecting circles and so our program is not needed. But it is a good way of checking that the program is working correctly. The area of a circle is proportional to the square of the radius 2) , so if the goat is going to eat half the grass of a field radius 1, I would expect the length of tether to be the square root of a half which is 0.70710678…

Now let’s run the program and see what that comes up with

% ./goat 50 0.0 0.0
Length of Tether = 0.707102
[1]    15833 exit 29    ./goat 50 0.0 0.0

Good. The program is doing what I would expect. In fact if any position near the centre of the field is selected, I would expect the same result, because until the goat is a bit nearer the edge of the field we don’t have an intersecting circles scenario.

% ./goat 50 0.1 0.15
Length of Tether = 0.707102
[1]    15837 exit 29    ./goat 50 0.1 0.15

Now we can calculate any scenario we need to. Let’s work out how long the tether need be to let the goat eat 60% of the grass when tethered 75% of the distance from the centre of the field to the edge.

% ./goat 60 0.75 0.0
Length of Tether = 1.087090
[1]    15836 exit 29    ./goat 60 0.75 0.0

Precision of the answer

There is a problem with the above solutions to any of these scenarios, if great precision in the answer is required. The more precision needed, the greater the number of blades of grass that need to be simulated. For each additional decimal place you need to increase the number of blades of grass tenfold, and very soon you will end up with an unmanageably large array of points. Either you will exceed the allowable addressable space on your system, or you will have so much data that the program takes an unreasonably long time to run.

However, it is possible to get more accuracy by changing the solution slightly. We have to increase the number of points but we no longer keep an array which needs to be sorted. I will describe the mechanism in the following section.

Method without Sorting

This method can be used to gain greater accuracy than the sorting method, by using more points. The downside is that you have to use interpolation to get to the answer. In other words you have to guess the answer in the first place, and then refine your estimate based on the results of running the program. I will show the program first and then describe how it works.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#include <unistd.h>

static int numOutside[11] ;
static int numInside[11] ;

double getDistanceFromPosition(double x, double y, double px, double py)
{
        // all we need is a bit of pythagoras
        // px, py is our position and x,y is the position of the blade of grass

        double xSquared = (x - px) * (x - px) ;
        double ySquared = (y - py) * (y - py) ;
        double distance = sqrt (xSquared + ySquared) ;
        return (distance) ;
}

main (int argc, char **argv)
{
        if (argc != 3)
        {
                printf ("Usage: goat <minTether> <maxTether>\n") ;
                exit (0) ;
        }

        int i = 0 ;
        int j = 0 ;
        int pos = 0 ;
        int numPoints = 0 ;

        double minTether = atof (argv[1]) ;
        double maxTether = atof (argv[2]) ;
        double tether = 0.0 ;
        double increment = (maxTether - minTether) / 10.0 ;

        // generate points

        for (i=0;i<20000;i++)
        {
                for (j=0;j<20000;j++)
                {
                        // Each coordinate is somewhere from -1.0 to + 1.0

                        double x = (double) i * 0.0001 - 1.0 ;
                        double y = (double) j * 0.0001 - 1.0 ;

                        // get distance from the centre of the field (position 0,0)

                        double distanceCentre = getDistanceFromPosition(x, y, 0.0, 0.0);
                        if (distanceCentre > 1.0)
                        {
                                // this blade of grass is not in the field
                                continue;
                        }

                        // Now get the distance from the edge of the field. We can
                        // choose any coordinate on the edge of the field (so long
                        // as we alwyas choose the same point!)

                        double distancePerimeter = getDistanceFromPosition(x, y, -1.0, 0.0) ;

                        for (tether=minTether, pos=0; tether <= maxTether; tether += increment, pos++)
                        {
                                if (distancePerimeter > tether)
                                        numOutside[pos]++ ;
                                else
                                        numInside[pos]++ ;
                        }
                }
        }

        int first = 1;

        for (tether=minTether, pos=0; tether <= maxTether; tether += increment, pos++)
        {
                if (first && (numInside[pos] > numOutside[pos]))
                {
                        first = 0 ;
                        printf ("--------------------------\n") ;
                }
                printf ("%.10f %d  %d\n", tether, numInside[pos], numOutside[pos]) ;
        }
}

The blades of grass are generated and placed on the grid (and discarded if outside the field) in exactly the same way as previously. We then guess the tether length, and then for each guess we work out the number of blades of grass that the goat can and cannot eat. The program takes an assumed range in which the answer must lie, and splits it into 10 equally spaced guesses for the tether length. The answer must lie somewhere between the guess that gives less points available to the goat than not, and the next guess which gives more points available to the goat than not. The program outputs a line ——————- to mark this point for ease of reference.

Since we are choosing 10 possibilities per run, the idea is to increase the accuracy of the answer by 1 decimal place with each run.

Results

As a starting point we know that tether length must be greater than the radius of the field, so we will provide the range 1.0 to 2.0 for the first run.

% ./goat2 1.0 2.0
1.0000000000 122836896  191322151
1.1000000000 144204929  169954118
--------------------------
1.2000000000 166230597  147928450
1.3000000000 188608105  125550942
1.4000000000 210997439  103161608
1.5000000000 233011700  81147347
1.6000000000 254195086  59963961
1.7000000000 273984129  40174918
1.8000000000 291626074  22532973
1.9000000000 305958778  8200269

The line ——————— shows us that the answer is between 1.1 and 1.2, so this is what we provide on the next run.

% ./goat2 1.1 1.2
1.1000000000 144204929  169954118
1.1100000000 146382683  167776364
1.1200000000 148566767  165592280
1.1300000000 150756929  163402118
1.1400000000 152952689  161206358
1.1500000000 155153909  159005138
--------------------------
1.1600000000 157360309  156798738
1.1700000000 159571449  154587598
1.1800000000 161787067  152371980
1.1900000000 164006919  150152128

Now we know the answer lies between 1.15 and 1.16. By the way, our loops for filling the grid are going from 1 to 20000 in each direction. Compare that with the 1 to 2000 we had previously for the sorting solution. So we have 100 times more blades of grass in the field. As a consequence each run takes a bit longer.

% time ./goat2 1.15 1.16
1.1500000000 155153902  159005145
1.1510000000 155374332  158784715
1.1520000000 155594804  158564243
1.1530000000 155815220  158343827
1.1540000000 156035876  158123171
1.1550000000 156256574  157902473
1.1560000000 156477146  157681901
1.1570000000 156697958  157461089
1.1580000000 156918676  157240371
--------------------------
1.1590000000 157139412  157019635
1.1600000000 157360290  156798757
./goat2 1.15 1.16  25.45s user 0.00s system 98% cpu 25.769 total

About 26 seconds run time. We can carry on with this mechanism, getting an extra decimal place of accuracy at each run until we get to the following point

% ./goat2 1.158728 1.158729
1.1587280000 157079454  157079593
1.1587281000 157079470  157079577
1.1587282000 157079478  157079569
1.1587283000 157079510  157079537
--------------------------
1.1587284000 157079540  157079507
1.1587285000 157079562  157079485
1.1587286000 157079578  157079469
1.1587287000 157079618  157079429
1.1587288000 157079638  157079409
1.1587289000 157079658  157079389

It is at this point that we have insufficient points in the grid to get more accuracy. We have with this method the first 6 decimal places correct (1.158728) but we are now showing the next digit as 3 when in fact it should be 2. These iterations were taking about 25 seconds each. For each additional decimal place the time taken would increased by a factor of 10, so to get another 2 decimal places would require 2 further runs of about 2500 seconds each.

Although I have only described how to find the answer to the original question (half the grass when tethered on the perimeter) with this non-sorting method, it would also be possible to adapt the program to find the answers to any of the supplementary questions I discussed earlier in the article. This I will leave as an exercise for the reader.


Computing | Math


QR Code
QR Code goat_in_a_field_problem (generated for current page)
 

Advertise with Anonymous Ads