Cycle detection: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Scala contribution added.) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 166:
Start index = 2
Cycle = [101, 2, 5, 26, 167, 95]</pre>
=={{header|C#|C_sharp}}==
Line 306 ⟶ 267:
</lang>
=={{header|C++}}==
<lang cpp>struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* Solution::detectCycle(ListNode* A) {
ListNode* slow = A;
ListNode* fast = A;
ListNode* cycleNode = 0;
while (slow && fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
cycleNode = slow;
break;
}
}
if (cycleNode == 0)
{
return 0;
}
std::set<ListNode*> setPerimeter;
setPerimeter.insert(cycleNode);
for (ListNode* pNode = cycleNode->next; pNode != cycleNode; pNode = pNode->next)
setPerimeter.insert(pNode);
for (ListNode* pNode = A; true; pNode = pNode->next)
{
std::set<ListNode*>::iterator iter = setPerimeter.find(pNode);
if (iter != setPerimeter.end())
{
return pNode;
}
}
}</lang>
=={{header|D}}==
Line 719:
Nothing
</pre>
=={{header|J}}==
Line 1,113 ⟶ 1,112:
Cycle start index 2
101 2 5 26 167 95</pre>
=={{header|Phix}}==
Line 1,943 ⟶ 1,898:
Start Index = 2
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2016-01}}
Pretty much a line for line translation of the Python code on the Wikipedia page.
<lang perl6>sub cyclical-function (\x) { (x * x + 1) % 255 };
my ( $l, $s ) = brent( &cyclical-function, 3 );
put join ', ', (3, -> \x { cyclical-function(x) } ... *)[^20], '...';
say "Cycle length $l.";
say "Cycle start index $s.";
say (3, -> \x { cyclical-function(x) } ... *)[$s .. $s + $l - 1];
sub brent (&f, $x0) {
my $power = my $λ = 1;
my $tortoise = $x0;
my $hare = f($x0);
while ($tortoise != $hare) {
if $power == $λ {
$tortoise = $hare;
$power *= 2;
$λ = 0;
}
$hare = f($hare);
$λ += 1;
}
my $μ = 0;
$tortoise = $hare = $x0;
$hare = f($hare) for ^$λ;
while ($tortoise != $hare) {
$tortoise = f($tortoise);
$hare = f($hare);
$μ += 1;
}
return $λ, $μ;
}</lang>
{{out}}
<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ...
Cycle length 6.
Cycle start index 2.
(101 2 5 26 167 95)</pre>
=={{header|REXX}}==
Line 2,217:
}</lang>
=={{header|Sidef}}==
{{trans|Perl 6}}
| |||