PDA

View Full Version : Would this logic algorithm be possible to implement?


josephdinatale
02-09-2011, 09:40 AM
Consider this hypothetical logic I want to implement:

Let's say I know the following ridiculous facts:
Dogs > cats
Dogs > fish
Dogs > monkeys
Dogs > lions

cats > turkeys
cats > zebras
cats > mice
cats > ducks

mice > dragons
mice > crocodiles
mice > elephants
mice > chickens

Ok, now let's say I want to show how dogs > dragons.
Well logically, that's:
dogs > cats > mice > dragons, thus dogs > dragons

How would I implement this logic into computer programming, so that I could show that dogs > chickens, or dogs > crocodiles, for any possible combination? (Assume I had the logic chart for every possible combination)

Achillies
02-09-2011, 09:44 AM
I am thoroughly confused.

notavirus.exe
02-09-2011, 09:47 AM
Make each name a variable and assign it a value in ascending order.

chickens = 1
elephants = 2
crocodiles = 3
dragons = 4
mice = 5
...
cats = 9
...
Dogs = 13

Then using booleans I'm sure you can rig something up.

The key is to make sure that Mice have the highest value of their group, cats have the highest in their group, and dogs have the highest in theirs.

Thats how I might try to go about it.

bluz74
02-09-2011, 09:50 AM
...
cats = 9
...


9 lives? Very clever sir!

sad_ism
02-09-2011, 09:57 AM
With your example (data and query), I'd just put the data in a multi-dimensional array and trace the relationship backwards (or upwards):

dogs[cats[turkeys[...],zebras[...],mice[dragons,crocodiles,elephants,chickens],ducks],fish[...],monkeys[...],lions[...]]

However, plotting the relationship between turkeys and dragons will be problematic.

kill4pie
02-09-2011, 10:02 AM
What language are we looking at here? I'll see if I can whip somthing up.

ypertatos
02-09-2011, 10:38 AM
My suggestion ( I'll use java )

* Make a general class animal

* Subclass every animal or make different instances of the said class.
Set enough variables in the class. For example a

private string name = "Dog";

would suffice in your example for the

animal dog = new animal();

* In that class add an array that contains the animals that are lower than him.

for example your dog would be like

private animal[] lower = new animal[4];

//In the constructor the following lines
lower[0] = cat;
lower[1] = fish;
lower[2] = monkey;
lower[3] = lion;

*Add a function in the the general class that will run through the lower array to look for the animal you are looking for. If the search fails it should search the lower array for each animal in the first lower array. Unless you assign the animals in a circle, it will eventually end and return with the result.

public boolean searchLower(animal a){
for( int i=0; i<lower.size(); i++ ){
if(lower[i] == a) return true;
}
for(int i=0; i<lower.size(); i++){
if( lower[i].searchLower(a) ) return true;
}

return false;
}


The code above may not be particulary right. I've not given it much thought. That's the general guideline though.

Hope I helped.

Rechar
02-09-2011, 11:16 AM
Have no idea if this would work either (or how competant it is from a coding perspective) but i enjoy coding stuff so thought i'd give it a go in Lua.

Animal_table = {
["Dog"] = {"Cat", "Mouse"},
["Mouse"] = {"Dragon"}
}

function superior_search(animal, below)
for k, v in pairs(Animal_table[animal]) do
if string.match(v, below) then
return true
else
superior_search(v, below)
end

end

return false
end

Pebr
02-09-2011, 11:19 AM
I'd suggest something similar to notavrius.

Assign each animal a variable - This variable is a certain level of power.

Dogs = 3;
Cats = 2;
Mice = 1;
All Others = 0;

This will simplify your process.

IcarusNine
02-09-2011, 12:47 PM
http://en.wikipedia.org/wiki/Binary_tree

josephdinatale
02-09-2011, 04:32 PM
I am thoroughly confused.

Imagine I had a ton of relationships. Cats > Fish, Dogs > cats, Dragons > Turkeys, Chickens > Salmon, Turkeys > Bears, Fish > dragons.

I want a user to be able to select two animals, and have the "logic path" between them shown.

For example, lets say the user picks bears and dogs.

Well, Dogs > Bears because Dogs > cats > fish > dragons > turkeys > bears

Make each name a variable and assign it a value in ascending order.

chickens = 1
elephants = 2
crocodiles = 3
dragons = 4
mice = 5
...
cats = 9
...
Dogs = 13

Then using booleans I'm sure you can rig something up.

The key is to make sure that Mice have the highest value of their group, cats have the highest in their group, and dogs have the highest in theirs.

Thats how I might try to go about it.


I'm not following your idea. Read my example above and see if your idea fits that example.

With your example (data and query), I'd just put the data in a multi-dimensional array and trace the relationship backwards (or upwards):

dogs[cats[turkeys[...],zebras[...],mice[dragons,crocodiles,elephants,chickens],ducks],fish[...],monkeys[...],lions[...]]

However, plotting the relationship between turkeys and dragons will be problematic.

Yeah, I want to be able to show the relationship between any two possible animals (assume there is SOME path between every two animals)

What language are we looking at here? I'll see if I can whip somthing up.

My suggestion ( I'll use java )

* Make a general class animal

* Subclass every animal or make different instances of the said class.
Set enough variables in the class. For example a

private string name = "Dog";

would suffice in your example for the

animal dog = new animal();

* In that class add an array that contains the animals that are lower than him.

for example your dog would be like

private animal[] lower = new animal[4];

//In the constructor the following lines
lower[0] = cat;
lower[1] = fish;
lower[2] = monkey;
lower[3] = lion;

*Add a function in the the general class that will run through the lower array to look for the animal you are looking for. If the search fails it should search the lower array for each animal in the first lower array. Unless you assign the animals in a circle, it will eventually end and return with the result.

public boolean searchLower(animal a){
for( int i=0; i<lower.size(); i++ ){
if(lower[i] == a) return true;
}
for(int i=0; i<lower.size(); i++){
if( lower[i].searchLower(a) ) return true;
}

return false;
}


The code above may not be particulary right. I've not given it much thought. That's the general guideline though.

Hope I helped.

That could possibly work. So I would have to create an object for each animal in the animal path, and an array of each animal that the particular animal "is greater than"?

Have no idea if this would work either (or how competant it is from a coding perspective) but i enjoy coding stuff so thought i'd give it a go in Lua.

Animal_table = {
["Dog"] = {"Cat", "Mouse"},
["Mouse"] = {"Dragon"}
}

function superior_search(animal, below)
for k, v in pairs(Animal_table[animal]) do
if string.match(v, below) then
return true
else
superior_search(v, below)
end

end

return false
end

I want to make this in Java

I'd suggest something similar to notavrius.

Assign each animal a variable - This variable is a certain level of power.

Dogs = 3;
Cats = 2;
Mice = 1;
All Others = 0;

This will simplify your process.

But each animal has a different level of power over another animal.

Dogs might be > cats, and cats might be > mouse,

http://en.wikipedia.org/wiki/Binary_tree

I've only had one and a half semesters of Java, I'm really not sure how to apply an advanced data structure like that.

Levi
02-09-2011, 04:49 PM
There is a computing language called prolog (http://www.swi-prolog.org/) that is specifically geared towards these sorts of problems.

I've long since forgotten how to program in this language though. :)

spacebug
02-09-2011, 04:52 PM
That sounds like the kind of thing that prolog is designed for.

Logic trees and all that stuff.

I can't give you an example, because it's been absolutely years, but in prolog you're supposed to be able to enter the problem in the right syntax and the program will tell you the answer. You don't need to tell it how to work out the answer, you just need to ask it the question in the right way.

I was absolutely rubbish at prolog, but I think you might find it an interesting avenue to research.

Edit: Bah, ninja'd!

But definitely look into it! Your question put me in mind of the kinds of example problems we were given in our Prolog tutorials!

Pebr
02-09-2011, 04:57 PM
But each animal has a different level of power over another animal.

Dogs might be > cats, and cats might be > mouse,

I know...

Dogs 3
Cats 2
Mice 1
Other 0

Dogs have a 2 power difference over a mouse
Cats have a 1 power difference over a mouse
Dogs have a 1 power difference over cats

Does that matter? All you required was that you needed to show that something was > than something else.

Using the above logic you just look for the bigger number.

W-
02-09-2011, 05:19 PM
This is easy enough to do with a directed graph. It almost fits perfectly.
Just use the greater than relationship as a edge from one element to the other, then use many of the graph algorithms to do path finding. If a path from one node to the other node exists, the starting node is better.

numbering order won't work since you will artificially generate some comparisons that don't exist.

for example, given these facts:
a > b
a > c
b > d
c > e
e > g
d > h
g > g
You can generate this directed graph:
All edges pointing to the right

b - d ---
a < > h
c - e - g

Given the facts you can't tell if b > c or if b < c. It gets worse when you try to compare d with e and g. Therefore, any numbering system would introduce some artificial differences between d, e, and g. Really, with the given facts, you should return "unknown" to a query between d and e, but the numbering system would return a false positive or negative.

Assuming no cycles (i.e. a > b; b > c; c >a)
Define: y is connected to x if you can get to y from x by following edges on the directed graph.
For your query on whether a is bigger than b
if(b connected to a) result = true;
else
if(a connected to b) result = false;
else
result = unknown;

Just google about graphs and path finding if you need to do an implementation.

notavirus.exe
02-09-2011, 05:29 PM
assign integer values to each one like i said and just do a comparison of the numbers, the greater one will be the victor.

josephdinatale
02-09-2011, 06:48 PM
This is easy enough to do with a directed graph. It almost fits perfectly.
Just use the greater than relationship as a edge from one element to the other, then use many of the graph algorithms to do path finding. If a path from one node to the other node exists, the starting node is better.

numbering order won't work since you will artificially generate some comparisons that don't exist.

for example, given these facts:
a > b
a > c
b > d
c > e
e > g
d > h
g > g
You can generate this directed graph:
All edges pointing to the right

b - d ---
a < > h
c - e - g

Given the facts you can't tell if b > c or if b < c. It gets worse when you try to compare d with e and g. Therefore, any numbering system would introduce some artificial differences between d, e, and g. Really, with the given facts, you should return "unknown" to a query between d and e, but the numbering system would return a false positive or negative.

Assuming no cycles (i.e. a > b; b > c; c >a)
Define: y is connected to x if you can get to y from x by following edges on the directed graph.
For your query on whether a is bigger than b
if(b connected to a) result = true;
else
if(a connected to b) result = false;
else
result = unknown;

Just google about graphs and path finding if you need to do an implementation.

Wow, that seems to be what I want to do. In your example, I would want the user to be able to say "a and h" and the program will find a path from a to h and then present the route it took!

The problem is, I've only had one and a half semesters of java programming. What would I need to look up to implement this?

W-
02-09-2011, 07:08 PM
Just google some information and read the wiki article on directed graphs/ graphs

http://en.wikipedia.org/wiki/Directed_graph
http://en.wikipedia.org/wiki/Graph_(data_structure)
and if you want to figure out connectivity
http://en.wikipedia.org/wiki/Breadth-first_search

for directed graphs, any search algorithm should be modified to only follow edges that point in the correct direction.

and if you are not interested in looking at the implementation of the algorithms, then there are certainly libraries that you can use.
Google-ing around found this library http://jgrapht.sourceforge.net/
But the appropriateness of using external code, of course, depends on what you are doing with it.

bdmason
02-09-2011, 07:09 PM
This is easy enough to do with a directed graph. It almost fits perfectly.
Just use the greater than relationship as a edge from one element to the other, then use many of the graph algorithms to do path finding. If a path from one node to the other node exists, the starting node is better.

numbering order won't work since you will artificially generate some comparisons that don't exist.

for example, given these facts:
a > b
a > c
b > d
c > e
e > g
d > h
g > g
You can generate this directed graph:
All edges pointing to the right

b - d ---
a < > h
c - e - g

Given the facts you can't tell if b > c or if b < c. It gets worse when you try to compare d with e and g. Therefore, any numbering system would introduce some artificial differences between d, e, and g. Really, with the given facts, you should return "unknown" to a query between d and e, but the numbering system would return a false positive or negative.

Assuming no cycles (i.e. a > b; b > c; c >a)
Define: y is connected to x if you can get to y from x by following edges on the directed graph.
For your query on whether a is bigger than b
if(b connected to a) result = true;
else
if(a connected to b) result = false;
else
result = unknown;

Just google about graphs and path finding if you need to do an implementation.

This. I hope my nightmares from Algorithms class don't pop up again after reading this thread. :o

Levi
02-09-2011, 07:48 PM
There is a computing language called prolog (http://www.swi-prolog.org/) that is specifically geared towards these sorts of problems.

I've long since forgotten how to program in this language though. :)

Okay, I got curious and decided to remember how to do this. :)

code.pl:

gr(dog, cat).
gr(dog, fish).
gr(dog, monkey).
gr(dog, lion).

gr(cat, turkey).
gr(cat, zebra).
gr(cat, mouse).
gr(cat, duck).

gr(mouse, crocodile).
gr(mouse, elephant).
gr(mouse, dragon).
gr(mouse, chicken).

greater(X, Y) :- gr(X, Y).
greater(X, Y) :- gr(X, Z),greater(Z,Y).

Now if in the prolog interpreter you ask:

greater(dog,dragon).

It says true. :) Apart from the definitions the problem is solved in 2 lines of code.

If I ask what dogs are better than:

27 ?- greater(dog,X).
X = cat ;
X = fish ;
X = monkey ;
X = lion ;
X = turkey ;
X = zebra ;
X = mouse ;
X = duck ;
X = crocodile ;
X = elephant ;
X = dragon ;
X = chicken ;
false.

If I ask what mice are better than:

31 ?- greater(mouse,X).
X = crocodile ;
X = elephant ;
X = dragon ;
X = chicken ;
false.

bdmason
02-09-2011, 07:51 PM
Okay, I got curious and decided to remember how to do this. :)

code.pl:

gr(dog, cat).
gr(dog, fish).
gr(dog, monkey).
gr(dog, lion).

gr(cat, turkey).
gr(cat, zebra).
gr(cat, mouse).
gr(cat, duck).

gr(mouse, crocodile).
gr(mouse, elephant).
gr(mouse, dragon).
gr(mouse, chicken).

greater(X, Y) :- gr(X, Y).
greater(X, Y) :- gr(X, Z),greater(Z,Y).


Now if in the prolog interpreter you ask:

greater(dog,dragon).

It says true. :)

And if I ask:
27 ?- greater(dog,X).
X = cat ;
X = fish ;
X = monkey ;
X = lion ;
X = turkey ;
X = zebra ;
X = mouse ;
X = duck ;
X = crocodile ;
X = elephant ;
X = dragon ;
X = chicken ;
false.

I get a list of all the things that dogs are better than.

What happens when you put in waffles (http://www.youtube.com/watch?v=2KyRCQp32p8)?

Levi
02-09-2011, 07:54 PM
What happens when you put in waffles (http://www.youtube.com/watch?v=2KyRCQp32p8)?

32 ?- greater(toaster, X).
false.

I was hoping for a blueberry muffin. :(

bdmason
02-09-2011, 08:09 PM
32 ?- greater(toaster, X).
false.

I was hoping for a blueberry muffin. :(

:(

5char

lucid enigma
02-09-2011, 08:26 PM
typedef enum {chickens, elephants, crocodiles, dragons, mice,..., Dogs} AnimalsEnum;

AnimalsEnum Animals1 = elephants, Animals2 = Dogs;
if (Animals1 > Animals2) ShowMessage("Animals1 wins!");
else if (Animals2 > Animals1) ShowMessage("Animals2 wins!");
else ShowMessage("Animal equilibrium!");

This sort of thing would kind of work. It would of course say "Animals2 wins!" since Dogs rule!
I'm not sure if we could really say that Dogs > chickens + chickens though?
(although a stone would kill both birds so I reckon a dog could take them)

Levi
02-09-2011, 09:01 PM
Oh, and if you are doing this in java, I found a java based prolog interpreter (http://www.ugosweb.com/jiprolog/index.aspx) that looks like it can be used to process prolog directly from your java code.

ypertatos
02-10-2011, 12:30 AM
That could possibly work. So I would have to create an object for each animal in the animal path, and an array of each animal that the particular animal "is greater than"?

Yes.

It's just an extra parameter in each animal's class.

And then add a function to search through it.




I've only had one and a half semesters of Java, I'm really not sure how to apply an advanced data structure like that.

Where do you study java?

One and a half semester and you consider binary trees advanced data structure?

What I proposed is basically a ( not a binary ) tree.

It's not that complicated.

bessent
02-10-2011, 07:07 AM
1. Create a one-dimensional String array of animal names. (animal)
2. Create a two-dimensional boolean array illustrating the relationships between animals. (isGreaterThan)
3. Create a method to return the array index of an animal name. (findAnimalIndex)
4. Use it! (relationship)

(One could easily add code to expand upon this and to handle animal names that are not pre-defined.)

String animal[] = new String[] { "dog", "cat", "mouse" };
boolean isGreaterThan[][] = new boolean[][] { { false, true, true },
{ false, false, true }, { false, false, false } };

private int findAnimalIndex(String animalName) {
int i = 0;
while (i < animal.length && !animal[i].equals(animalName)) {
i++;
}

return i;
}

boolean relationship = isGreaterThan[findAnimalIndex(animal1)][findAnimalIndex(animal2)];
Example: relationship = isGreaterThan[findAnimalIndex("dog")][findAnimalIndex("cat")];
i.e. relationship = true;

(Not actually tested!)