Re: algorithmic approach to calculating number of full moon since a certain date ? - Algorithms Discussion Boards

i'm not trying to predict future prices only based on past chart patterns (i never thought technical analysis would work). What im trying to do is finding the causes for those patterns. If a message is released exactly at the turning point of a chart and if similar chart/message patterns (i know, this is the second big difficulty: how do you define Text-Similarity?) often occur, i'd guess the probability of a similar message causing a similar chart pattern is high.

Newbie18 wrote:
If a message is released exactly at the turning point of a chart and if similar chart/message patterns (i know, this is the second big difficulty: how do you define Text-Similarity?) often occur, i'd guess the probability of a similar message causing a similar chart pattern is high.

Computing text-similarity is easy. Teaching the computer to do what you want, is impossible.

Aight, say you focus on determining the "cause" of a certain change in the graph; let's say there's a turning-point that can be easily identified. You'd then have to search all the news, and find a message that first relates to the change (most news will not, obviously).

Say you found all the messages relating Microsoft, just an hour before the big change in stock-price; how would you have the program differentiate between a rant on Windows and a statement from it's CEO? Given the way financials talk, how do you think your app would interpret a sentence like

"We have managed to stop the decline in growth."

You and I would have trouble interpreting that line, a bot would have even more trouble. No, we haven't even looked at the fact that some news takes more than an hour to reach investors, or that it may take longer to realize what's going on.

To make things worse, most of those turning-points will not be attributable to a single headline.

Bastard Programmer from Hell Suspicious | :suss:

if you can't read my code, try converting it here[^]

Eddy Vluggen wrote:
Computing text-similarity is easy.

Now i'm curious. How would you do that?

The program doesn't have to interpret any information in the text, that's of course too difficult. If it can find a "class" of messages, that are similiar to each other and all released several hours before a rise of the price (it doesnt have to be a rise over a few hours, it could also be over a week or even a month) of the company mentioned in it, the relation should be obvious.

Eddy Vluggen wrote:
To make things worse, most of those turning-points will not be attributable to a single headline.

If enough messages are processed, maybe i can find some, which have enough relevance of their own.

I know, it's not likely that my ideas are realizable, and if they are, most probably some Bank or Hedge Fund has already done it and i can't earn anything at all with my application. But i just have to try.

Newbie18 wrote:
Now i'm curious. How would you do that?

There are multiple algorithms that can be used to determine whether two words 'sound alike' (like metaphone and soundex), what their "edit distance" is (Levenshtein[^]) - you could even download and abuse the wiktionary to find synonyms and validate against their soundex.

Newbie18 wrote:
If it can find a "class" of messages, that are similiar to each other

Without interpreting the message, it's nigh impossible to determine whether you're dealing with "good" or "bad" news. Since you can't make that simple classification, I'd have my doubts about the validity on complexer classes.

Newbie18 wrote:
I know, it's not likely that my ideas are realizable, and if they are, most probably some Bank or Hedge Fund has already done it

Not in this way.

They're most likely scanning for keywords, and have a human validating the most promising headlines. You could perhaps "train" some artificial network to recognize "positive" news, but again you'd hit new trouble - your bot might start to buy/sell based on false rumours.

Say you do find a correlation between trades (somewhat simpeler than correlation between price and news); say you notice the move in the price of copper before the price in silver moves - that might imply a connection, but it might also be a coincidence. In practice, silver often follows, but at some days it simply moves in a contrary direction due to "other factors" (like the discovery of a huge deposit of silver).

If trading were that easy, we would have replaced wall street completely with computers and gotten rid of the human influence a long time ago.

Bastard Programmer from Hell Suspicious | :suss:

if you can't read my code, try converting it here[^]

Klaman filters are not bad at that: Kalman filtering demo[^]

Edit: the location of this database of full moons: "Full Moon Dates Between (1900 - 2100)"[^] ... has eliminated my need to find an algorithm. But, I'll leave this "up," in case the link the database is useful to someone else.

No, I am not "into" astrology, but a friend asked me if I could write a calculator that given year, month, day, would indicate the number of full moons between that date, and the current date.

So, this is a question more of "curiosity," rather than one aimed at any practical result.

Here's a text-file dataset (times shown: GMT +1) of full moons from 1943-1953.[^]. Also see:[^].

What interests me is whether, given the variance between solar year time (in the "western" calendar, given "leap years," etc.) and lunar cycles, one can algorithmicly compute the number of years between the full moon falling on a certain day of the week in a specific week and month, and the next full moon falling on the same day of the month and week in the future.

Other potential complexities, of lunar cycle duration, and systems of lunation numbering, are well-described here:[^], and here:[^].

Now, if one had an algorithm that would compute the number of years with 13, rather than 12, moons per year, based on a starting year, month, date, I suppose that would make it easier.

Appreciate any thoughts, thanks, Bill

The glyphs you are reading now: are place-holders signifying the total absence of a signature.

modified 1-Jul-12 10:31am.

I have some code that calculates the date of Easter for any year, based on the first full moon after March 21st. I do not fully understand it but I know it works; I guess it could be adapted to what you are looking for.

speaking as ...

Richard MacCutchan wrote:
date of Easter for any year, based on the first full moon after March 21st.

Note that the date of Easter (western, not Greek Orthodox or Russian Orthodox) relies on a specific definition of what is a Full Moon - it is 'as seen from Rome', and it is after the first Sunday after the 21st March which makes an unsubtle variation in the actual date (up to +/- 7 days) as seen from the observer's position because it may be Sunday earlier or later locally than it is in Rome. Gauss's algorithm does not work 100% of the time (IIRC there was at least one date in the 1800s that his algorithm got wrong).

This is the formula that I have been using for the last 35 years (changed language several times but same method):

C#

Date.prototype.Easter   =   // Date of Easter Sunday for the year that the date object represents or for a given year
    function(optYear)   // Optionally can override year that the date is for
        // optYear can be a Date object or a numeric year
    {
        var year    = optYear
            ?   (   optYear.constructor == Date
                ?   optYear.getFullYear()
                :   ( optYear < 1900 ? optYear + 1900 : optYear )   // Assume number
                )
            :   this.getFullYear();

        // Algorithm optimised from 'Puzzles and Paradoxes' by T H O'Beirne
        // (Oxford University Press, London (c) 1965)
        var a   = year % 19;
        var b   = Math.floor(year / 100);
        var c   = year % 100;
        var d   = Math.floor(b / 4);
        var h   = (19 * a + b - d - Math.floor((8 * b + 13) / 25) + 15) % 30;
        var mu  = Math.floor((a + 11 * h) / 319) - h;
        var lambda  = (2 * (b - d * 4) + Math.floor(c / 4) * 6 - c + mu + 32) % 7 - mu;
        var month   = Math.floor((lambda + 90) / 25);

        return  new Date(year, month - 1, (lambda + month + 19) % 32);
    };  // Date.prototype.Easter

The variable names are based on the names in the original article cited in the comments but I have optimised the calculations (used to be 10 steps, now only 8 steps).

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.

Smile | :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

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.

C#

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); // Queue up the initial room
            destinationQueue.Enqueue(destinationRoom);

            visitedStartRooms.Add(startRoom, true);// say we have been there, done that
            visitedStopRooms.Add(destinationRoom, true);

            string direction = "";
            bool foundRoom = false;

            while (startQueue.Count != 0 || destinationQueue.Count != 0)
            {

                ROOM_INFO currentStartRoom = startQueue.Dequeue(); // remove room from queue to check out.
                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
                {
                    // Start from destination and work to Start Point.
                    foreach (string exit in currentDestinationRoom.exitData)
                    {

                        stopNextRoom = extractMapRoom(exit); // get adjacent room
                        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;
                    }
                }

                // start from the start and work way to destination point
                foreach (string exit in currentStartRoom.exitData)
                {

                    startNextRoom = extractMapRoom(exit); // get adjacent room
                    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;
                }
            }

        }
        //// ''determinePath(visitedStartRooms);
        //// return directions;



    


        }

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!

Smile | :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

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?).

Smile | :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

This looks like you have to implement Dijkstra's algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm[^] Smile | :)

.

“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”

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.

Smile | :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

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 Laugh | :laugh:

.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[^].

speaking as ...

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? Smile | :)

I want to fully understand the riddle before i think of a solution, i'am not trying to be difficult. Laugh | :laugh:

“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”