Thread: dogs chasing cats up trees

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    10

    dogs chasing cats up trees

    I have an assignment until next week and i don't know hot to complete it

    In the program in c we have to help a cat escape from a dog which has double speed. The program works as follows :
    the data of the program are read from the file CatAndDog.dat (the first line has the cat's coordinates, the second has the dog's ones, the third has the number of the trees that the cat can climbs on (max 1000) and the next n lines has the coordinates of the trees)
    For example :
    2.0 2.0
    1.0 1.0
    4
    0.0 1.0
    1.5 1.5
    2.5 2.9
    0.0 0.5

    After doing this we have to check if the cat can escape by climbing on any tree. But this is the difficult for me because if there are two or more trees we should prefer the tree that is closer to initial position of the cat. Otherwise The cat cannot esacape.

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    This is the C# board, not C.
    We also don't answer homework assignments. We comment on code examples, so try to solve it and you'll get help finish it or ironing out any errors.

    Hint: if you subtract the cat location from a tree location, you get a good idea which trees are closest and which ones are furthest.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Use the distance formula: distance = sqrt( (x1-x2)^2 + (y1-y2)^2) )

    Good old Pythagoras!

    Using your sample data I was able to whip up a quick program that spit this out:
    Code:
    Cat is at: (2,2)
    Dog is at: (1,1)
    There are 4 trees: (0,1) (1.5,1.5) (2.5,2.9) (0,0.5)
    The closest tree to the cat is: (1.5,1.5)
    The dog is 1.4142135623731 units from the cat.
    The cat is 0.707106781186548 units from the closest tree.
    The cat will not escape from the dog.
    Since I wrote it in C# because this is the C# forum, but you need to write it in C, I guess there's no harm in posting the code to see how I did it:
    Code:
        class Program
        {
            struct Point
            {
                double X;
                double Y;
    
                public Point(double x, double y)
                    : this()
                {
                    X = x;
                    Y = y;
                }
    
                public double DistanceFrom(Point other)
                {
                    return Math.Sqrt(Math.Pow(X - other.X, 2) + Math.Pow(Y - other.Y, 2));
                }
    
                public static Point FromLine(string line)
                {
                    string[] parts = line.Split(' ');
                    return new Point(double.Parse(parts[0]), double.Parse(parts[1]));
                }
    
                public override string ToString()
                {
                    return "(" + X + "," + Y + ")";
                }
            }
    
            static void Main(string[] args)
            {
                TextReader reader = new StreamReader("..\\CatAndDog.dat");
    
                Point cat = Point.FromLine(reader.ReadLine());
                Point dog = Point.FromLine(reader.ReadLine());
    
                int numTrees = int.Parse(reader.ReadLine());
                Point[] trees = new Point[numTrees];
                for (int i = 0; i < numTrees; ++i)
                    trees[i] = Point.FromLine(reader.ReadLine());
                reader.Close();
    
                Console.WriteLine("Cat is at: {0}", cat);
                Console.WriteLine("Dog is at: {0}", dog);
                Console.Write("There are {0} trees:", trees.Length);
                foreach (Point tree in trees)
                    Console.Write(" {0}", tree);
                Console.WriteLine();
    
                Point closestTree = trees.OrderBy(t => t.DistanceFrom(cat)).First();
                Console.WriteLine("The closest tree to the cat is: {0}", closestTree);
                Console.WriteLine("The dog is {0} units from the cat.", dog.DistanceFrom(cat));
                Console.WriteLine("The cat is {0} units from the closest tree.", cat.DistanceFrom(closestTree));
                Console.WriteLine("The cat will{0} escape from the dog.", (cat.DistanceFrom(closestTree) * 2 < dog.DistanceFrom(cat)) ? "" : " not");
            }
        }
    Last edited by itsme86; 03-23-2011 at 12:58 PM.
    If you understand what you're doing, you're not learning anything.

  4. #4
    Registered User
    Join Date
    Mar 2011
    Posts
    10
    itsme86 i really appreciate your work, but how to write all this in C ?

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    214
    Quote Originally Posted by sadam View Post
    itsme86 i really appreciate your work, but how to write all this in C ?
    Thats why you're taking a C class... to figure that out.

  6. #6
    Registered User
    Join Date
    Mar 2011
    Posts
    10
    FILE *fp;

    if((fp = fopen("CatAndDog.dat","r")) == NULL)
    printf("File could not be opened\n")

    fscanf(fp, "%d %d", &a, &b);
    fscanf(fp, "%d %d", &c, &d);
    fscanf(fp, "%d", &e);
    }

    What i don't know is how to read the coordinations of the tree and how to find if the cat can escape or not

  7. #7
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    I would use an array that's num_trees elements big, personally.
    If you understand what you're doing, you're not learning anything.

  8. #8
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    A few things:

    1) In your fscanf statements you are reading in integers, but from the data file it seems that both the coordinates for the cat and the dog are floats. You want
    Code:
    fscanf(fp, "%f %f", &cat_X_coord, &cat_Y_coord);
    fscanf(fp, "%f %f", &dog_X_coord, &dog_Y_coord);
    fscanf(fp, "%d", &number_of_trees);
    The %f tells fscanf to look for a floating point number rather than an integer

    2) See how I've given my variables meaningful names? Do that.

    3) Next you want arrays to store the coordinates of the trees and a loop to read in the coordinates from the file and store them in the arrays. Have you covered how arrays and loops work in your class?

  9. #9
    Registered User
    Join Date
    Mar 2011
    Posts
    10
    Well we have done them but i would appreciate any help because i am very confused

  10. #10
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by sadam View Post
    Well we have done them but i would appreciate any help because i am very confused
    No we are not going to hand you code...

    Work the problem, use the advice given... show the initiative and post your code when you get stuck ... really stuck, not lazy stuck.

  11. #11
    Registered User
    Join Date
    Mar 2011
    Posts
    10
    please don't be the smart one, if you don't want to help me just don't help me. i'm stuck and i don't care if you believe it or not. but don't tell me to work if you don't know what i do...

  12. #12
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by sadam View Post
    please don't be the smart one, if you don't want to help me just don't help me. i'm stuck and i don't care if you believe it or not. but don't tell me to work if you don't know what i do...
    1) OK, then I won't help you.
    2) I do know what you're NOT doing... and that's applying yourself to the problem.

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Take it step by step:

    1)For holding the data, using an array of struct of points (prototyped above main() ), with int x and int y as it's only members.

    That array is declared (created) in main().

    2) write a function or block of code, to read in the data. Number of tree's is the length of good data that your array of points[] will use. Points[] could be sized to 500 or some other very large number, to avoid the need for dynamic memory allocation (which is not a part of the assignment I believe).

    You also have two other points - one for the dog, one for the cat.

    3) now compute the distance between point dog and point cat, using the distance formula, shown here (reposted from Itsme's post):

    Use the distance formula: distance = sqrt( (x1-x2)^2 + (y1-y2)^2) )

    You can use the sample data with your program, to see if it agrees with his program:

    Cat is at: (2,2)
    Dog is at: (1,1)
    There are 4 trees: (0,1) (1.5,1.5) (2.5,2.9) (0,0.5)
    The closest tree to the cat is: (1.5,1.5)
    The dog is 1.4142135623731 units from the cat.
    The cat is 0.707106781186548 units from the closest tree.
    The cat will not escape from the dog.
    In the same way that you calculated the distance between the dog and cat, you now need a loop to calculate the distance from the cat to each of the trees. Obviously, the cat needs the closest tree, but you can't be sure which one that is without some (at least preliminary), calculating for all of them

    Politicians worry endlessly about the distance from the dog to the tree's, but they are stuck with no common sense, worrying about things like "what the definition of is, is". ;/

    So, show what you've got for a start on code, and let us know what you're stuck on, and we'll work it through.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by sadam View Post
    Well we have done them but i would appreciate any help because i am very confused
    Normally I would take such a line to mean "I don't know how to tackle this problem" however the C# code someone posted should largely be sufficient even for someone not familiar with C# to understand how to tackle the problem.
    If it's that you don't know how to do it with C syntax, well then that's what reference material is for, whether online or books. Do you need some material suggestions?

    The hardest part is starting. It involves coming to terms with the fact that this assignment will actually take you some time to complete, possibly a few days at your experience level. You either accept that and jump in and proceed one step at a time, or you'll decide that you can't be bothered learning to program.

    If you ask questions, then ask specific smart questions.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Strategy might be as simple as:
    Calculate distance from initial cat position to all the trees. Find closest one. Is it 2x distance from dog to cat?

    But while the cat is heading off to any particular tree, should the dog aim for the same tree? Or aim for the cat at its anticipated position of intercept dynamically? Or travel in some curve? Now the problem starts to get all differential equationy. What if cat heads for tree #1, then takes a quick turn and goes for tree #2? Dog has to alter his path. I think this is too hard to solve.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Can you Microwave Regular Hot dogs?
    By Kleid-0 in forum A Brief History of Cprogramming.com
    Replies: 38
    Last Post: 01-11-2005, 01:53 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. A Miracle has occurred in the realm of Hot Dogs
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 05-08-2004, 03:18 PM
  4. Cats vs. Dogs
    By LouDu in forum A Brief History of Cprogramming.com
    Replies: 44
    Last Post: 03-14-2003, 09:22 PM

Tags for this Thread