/    Sign up×
Community /Pin to ProfileBookmark

Algorithm issue

Copy linkTweet thisAlerts:
Feb 27.2010

Imagine I have a timeline starting at an arbitrary time in the past and continuing up to the present. On that timeline are two sets of events, say [I]a[/I] and [I]b[/I]. These sets of events are independent, but within each set the events occur at regular intervals. For example, [I]a[/I] may occur every 30 seconds and [I]b[/I] may occur every 40 seconds (though these values are arbitrary).

What I need is to end up with an array containing either ‘a’ or ‘b’, in the order the events occur on the timeline. Where [I]a[/I] and [I]b[/I] occur at the same time, [I]a[/I] should always take precedence.

An illustrative example in case that made no sense:

[code]
 a a a a a a a a
||||||||||||||||||||||||–> etc
b b b b b b
[/code]

From the above I’d like an array like this:

[code=php]
array(‘a’, ‘b’, ‘a’, ‘b’, ‘a’, ‘a’, ‘b’, ‘a’, ‘b’, ‘a’, ‘b’, ‘a’, ‘a’, ‘b’);
[/code]

Anyone got any ideas on an efficient way of doing this? The best I’ve come up with so far is looping through the timeline but that could get pretty impractical for longer periods.

EDIT: In fact the most ideal thing would be getting an array just up to the point where the pattern repeats rather than actually containing the repeating pattern x number of times.

to post a comment
PHP

2 Comments(s) ↴

Copy linkTweet thisAlerts:
@NogDogFeb 27.2010 — I don't have any "eureka" ideas, but if you know the intervals for each event, if you calculate the least common multiple for those two numbers, you'll know how many of the basic time unit you need to cycle through before the pattern will start repeating.
Copy linkTweet thisAlerts:
@MindzaiauthorFeb 27.2010 — Thanks NogDog, that works for me ?

Here's what I came up with in case anyone else has a similar issue.[COLOR="White"]%[/COLOR]

[code=php]
function least_common_multiple($a, $b) {
if ($b > $a) {
list($a, $b) = array($b, $a);
}
return $a * $b / greatest_common_divisor($a, $b);
}

function greatest_common_divisor($a, $b) {
if ($b == 0) {
return $a;
}
return greatest_common_divisor($b, $a % $b);
}

$a = 30;
$b = 40;
$lcm = least_common_multiple($a, $b);
$results = array();
for ($i = 0; $i < $lcm; $i++) {
if ($i % $a == 0) {
$results[] = 'a';
}
if ($i % $b == 0) {
$results[] = 'b';
}
}

print_r($results);
[/code]

<i>
</i>Array
(
[0] =&gt; a
[1] =&gt; b
[2] =&gt; a
[3] =&gt; b
[4] =&gt; a
[5] =&gt; a
[6] =&gt; b
)
×

Success!

Help @Mindzai spread the word by sharing this article on Twitter...

Tweet This
Sign in
Forgot password?
Sign in with TwitchSign in with GithubCreate Account
about: ({
version: 0.1.9 — BETA 6.17,
whats_new: community page,
up_next: more Davinci•003 tasks,
coming_soon: events calendar,
social: @webDeveloperHQ
});

legal: ({
terms: of use,
privacy: policy
});
changelog: (
version: 0.1.9,
notes: added community page

version: 0.1.8,
notes: added Davinci•003

version: 0.1.7,
notes: upvote answers to bounties

version: 0.1.6,
notes: article editor refresh
)...
recent_tips: (
tipper: @nearjob,
tipped: article
amount: 1000 SATS,

tipper: @meenaratha,
tipped: article
amount: 1000 SATS,

tipper: @meenaratha,
tipped: article
amount: 1000 SATS,
)...