|
I did not bother to check every year in the last 2000+, since it seemed to work for plus or minus 5 years since I started using it.
One of these days I'm going to think of a really clever signature.
|
|
|
|
|
For this sort of question, and many more such, my reference is Dershowitz & Reingold's Calendrical Calculations. I have a first ed dead tree; I think it's now up to 3rd ed. All the code from the book (Lisp!) is available for free download. I think there's also Java available.
Google knows more than me... (but do either of us understand?)
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
A lunar month equals 29 days, 12 hours, 44 minutes; so I'd divide the timespan by that, yielding a pretty good estimate. It might be off by one if either one of the dates is just before/after a full moon.
|
|
|
|
|
I am trying to develop a dynamic pathing algorithm for a game (all text) and running into an issue of finding the shortest path when all the edges(connectors) are the same cost or weight.
The algorithm below will capture all the rooms from start to finish, but the issue is sorting it out to find the shortest distance to the finish, perhaps new algorithm is needed? Thanks in advance for any assistance.
public void findRoute(ROOM_INFO startRoom, ROOM_INFO destinationRoom)
{
Dictionary<ROOM_INFO, bool> visitedStartRooms = new Dictionary<ROOM_INFO, bool>();
Dictionary<ROOM_INFO, bool> visitedStopRooms = new Dictionary<ROOM_INFO, bool>();
List<string> directions = new List<string>();
startQueue.Enqueue(startRoom);
destinationQueue.Enqueue(destinationRoom);
visitedStartRooms.Add(startRoom, true);
visitedStopRooms.Add(destinationRoom, true);
string direction = "";
bool foundRoom = false;
while (startQueue.Count != 0 || destinationQueue.Count != 0)
{
ROOM_INFO currentStartRoom = startQueue.Dequeue();
ROOM_INFO currentDestinationRoom = destinationQueue.Dequeue();
ROOM_INFO startNextRoom = new ROOM_INFO();
ROOM_INFO stopNextRoom = new ROOM_INFO();
if (currentStartRoom.Equals(destinationRoom))
{
foundRoom = true;
break;
}
else
{
foreach (string exit in currentDestinationRoom.exitData)
{
stopNextRoom = extractMapRoom(exit);
if (stopNextRoom.Equals(startRoom))
{
visitedStopRooms.Add(stopNextRoom, true);
foundRoom = true;
break;
}
if (stopNextRoom.mapNumber != 0 && stopNextRoom.roomNumber != 0)
{
if (!visitedStopRooms.ContainsKey(stopNextRoom))
{
if (visitedStartRooms.ContainsKey(stopNextRoom))
{
foundRoom = true;
}
else
{
destinationQueue.Enqueue(stopNextRoom);
visitedStopRooms.Add(stopNextRoom, true);
}
}
}
}
if (foundRoom)
{
break;
}
}
foreach (string exit in currentStartRoom.exitData)
{
startNextRoom = extractMapRoom(exit);
if (startNextRoom.Equals(destinationRoom))
{
visitedStartRooms.Add(startNextRoom, true);
foundRoom = true;
break;
}
if (startNextRoom.mapNumber != 0 && startNextRoom.roomNumber != 0)
{
if (!visitedStartRooms.ContainsKey(startNextRoom))
{
if (visitedStopRooms.ContainsKey(startNextRoom))
{
foundRoom = true;
break;
}
else
{
startQueue.Enqueue(startNextRoom);
visitedStartRooms.Add(startNextRoom, true);
}
}
}
}
if (foundRoom)
{
break;
}
}
}
}
|
|
|
|
|
I did not study your code, and unfortunately you did not describe your algorithm at all, nor did you provide a reference to whatever inspired you.
I do know the normal approach would be something along these lines:
- provide a storage for "distance from starting point" to each node;
- initialize to "infinite" (well, zero would be fine too as long as you read that as infinite!);
- now start walking around from the starting node, using a "breadth first" scheme; this means you go one step away from the starting point in all possible ways, you keep track of all the possible points at this distance (that needs a collection, say a list, it does not need an ordered collection such as a queue), and also set the distance to 1 for all the nodes you can reach in that one step.
- now repeat for all the nodes you collected as having distance 1, then 2, then 3, etc.
- however, for each node N that you can reach from node P in one step, make distance(N) equal to distance(P)+1 only if it does not already have a smaller value.
- now the first time you reach the destination, you are sure to have reached it in the minimal number of steps. And by looking at the distance values, you can trace one way back to the starting point without needing any memory or any trials, just walk the way the distance decreases by one on every step.
To my knowledge there isn't any superior algorithm, so the only thing you can do for performance is come up with a decent implementation!
|
|
|
|
|
Sorry Luc, your right I should have just explained what I was trying to do with the algorithm instead of the code.
I am pretty much doing what your saying except for the keeping track of distance.
Algorithm goes like this:
1. Place Start and End rooms into a start queue and end queue.
2. Enter a while loop with a condition not to leave while there is at least a Start or End Room loaded or that the destination is found.
3. I dequeue the room and iterate through each exit the room has and mark it as visited and load that room into the queue.
4. Repeat step 3 until I reach my destination or run out of rooms.
|
|
|
|
|
That sounds pretty similar, I see it is breadth first; I'm not sure you also are getting the best route, as it seems you don't have permanent storage (the steps taken are being removed from the queues, aren't they?).
|
|
|
|
|
|
Dijkstra's is considering too many possibilities: when all the edge costs are equal, the first solution found is bound to be the cheapest, no need to continue and investigate all the remaining routes.
|
|
|
|
|
Luc Pattyn wrote: when all the edge costs are equal, the first solution found is bound to be the cheapest, no need to continue and investigate all the remaining routes.
The best way might be to implement a generalized algorithm like Dijkstra's algorithm, you never know what might come up  .But for the sake of simplicity it is good to use Breadth First Search (BFS) in such a case as you outlined in your answer. However, in a game application the graph might not always contain edges of equal cost, anyways since the OP wants a specific algorithm for a graph with edges of equal cost then BFS suffices.
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
This is an easy read if you are familiar with set notation.
http://planning.cs.uiuc.edu/node4.html
I have an unfinished project on the shelf which attempts to find the shortest path through a maze by "pressurizing" the maze at the entrance and coloring-in "temperature" or "pressure" at each cell in the maze. The "coolest" or "lowest pressure" (bluest) path is the shortest solution.
Good Luck
Tadeusz Westawic
Sum quid sum.
modified 9-Jul-12 11:19am.
|
|
|
|
|
hi, my question is
if i have 3 basic colors (each made of rgb):
color1 : R:150, B:zero, G:255
color2 : R:255, B:150, G:zero
color3 : R:zero, B:255, G:150
They can be mixed using the formula :
new_color = floor(X*0.9)+floor(Y*0.1)
X and Y can be a basic color or a new color allready created by using the formula.
for example, if i want to mix color1 as main with color3 :
new_color(R,B,G) = (floor(0.9*150)+floor(0.1*0) , floor(0.9*0)+floor(0.1*255) , floor(0.9*255)+floor(0.1*150) ) = (135, 25, 244).
I need to find a way to mix the colors in order to get a desired color, for example : R:187 B:135 G:201
so far i wrote a "brute force" program which go all over the combinations of basic colors (runing for 7 days now got up to 16 mixing steps) and a bit smarter AStar algorithm (got good reults for small sequnces, letting it run for the week end...).
hope there is a smarter and faster way to solve the problem.
Btw, i code with matlab or vb.
Thanks.
|
|
|
|
|
Please do not repost questions in multiple forums. This has already been dealt with here[^].
|
|
|
|
|
sorry, only after posting it there i discovered the algorithm section.
the answer i got there is not correct.
thanks.
|
|
|
|
|
Kobi_Z wrote: new_color = floor(X*0.9)+floor(Y*0.1)
Kobi_Z wrote: new_color(R,B,G) = (floor(0.9*150)+floor(0.1*0) , floor(0.9*0)+floor(0.1*255) , floor(0.9*255)+floor(0.1*150) ) = (135, 25, 244).
Given two color's X,Y, floor(Y*0.9) + floor(X*0.1) and floor(X*0.9) + floor(Y*0.1) give different results,so physically speaking why is that so? The equation has to be commutative, mixing two colors is supposed to be commutative. Please explain why this discrepancy?
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
BupeChombaDerrick wrote: Given two color's X,Y, floor(Y*0.9) + floor(X*0.1) and floor(X*0.9) + floor(Y*0.1) give different results,so physically speaking why is that so? The equation has to be commutative, mixing two colors is supposed to be commutative. Please explain why this discrepancy?
Kobi_Z wrote: for example, if i want to mix color1 as main with color3 :...
the first color you mix is the main one.
It is a riddle some students asked at my university and I try to "solve" it because I find it interesting i dont think you should look on the physical aspect .
hope it explains any discrepancy.
Thanks.
|
|
|
|
|
Okay so in your riddle the colors are mixed in 0.9 and 0.1 proportions where the main color gets 0.9 and the next color gets 0.1?
Perhaps you would have said the formula
new_color = floor(a*X) + floor(b*Y)
where a,b are variable proportions such that a + b = 1. Mathematically correct, in your case a = 0.9 ,b = 0.1. My question is why 0.9 and 0.1,is it how it is? or 0.9 and 0.1 proportions are just for illustration purposes? I want to fully understand the riddle before i think of a solution, i'am not trying to be difficult.
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
it is a fixed formula :
new_color = floor(0.9*x)+floor(0.1*b)
"it is how it is"...
Thanks.
|
|
|
|
|
Okay i googled "color mixing riddle" and your questions here http://www.mymathforum.com/viewtopic.php?f=20&t=31242[^]
is clearer. Okay now I get the question, will see if i can think of a faster solution, will get back to you. 
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
|
mixing two colors in uneven quantities can do almost that, but then I would expect only one floor action, something like
new_color = floor(0.9*X + 0.1*Y)
as the mixing would be a continuous operation, the result may need quantisation.
|
|
|
|
|
its a given question...
i think its like that (the floor) because then mixing same color with itself decreases final most higer value by one.(mix(color1,color1) results in [150,0,254])
|
|
|
|
|
And that, while unnatural, is a clue to an upper bound on the complexity of the solution...
|
|
|
|
|
So the factors 0.9 and 0.1 are just variable proportions, well i thought they were constants as initially illustrated by the OP. Now i get it.
Thanks.
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
0.9 and 0.1 are constants.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
