Add recursive kolakoski sequence (TheAlgorithms#279)

siriak · web-flow · commit c95d8aa8366e · 2021-12-29T23:10:32.000+02:00
diff --git a/Algorithms.Tests/Numeric/MillerRabinPrimalityTest.cs b/Algorithms.Tests/Numeric/MillerRabinPrimalityTest.cs
@@ -7,13 +7,12 @@ namespace Algorithms.Tests.Numeric
 {
     public static class MillerRabinPrimalityTest
     {
-        [Test]
         [TestCase("7", ExpectedResult = true)]  // true
         [TestCase("47", ExpectedResult = true)] // true
         [TestCase("247894109041876714378152933343208766493", ExpectedResult = true)] // true
         [TestCase("315757551269487563269454472438030700351", ExpectedResult = true)] // true
 
-        [TestCase("2476099", ExpectedResult = false)]       // false 19^5
+        [TestCase("2476099", ExpectedResult = false)] // false 19^5
         // false 247894109041876714378152933343208766493*315757551269487563269454472438030700351
         [TestCase("78274436845194327170519855212507883195883737501141260366253362532531612139043", ExpectedResult = false)]
         public static bool MillerRabinPrimalityWork(String testcase)
@@ -31,7 +30,6 @@ public static bool MillerRabinPrimalityWork(String testcase)
             return result;
         }
 
-        [Test]
         [TestCase("-2")]
         [TestCase("0")]
         [TestCase("3")]
diff --git a/Algorithms.Tests/Sequences/KolakoskiSequenceTests.cs b/Algorithms.Tests/Sequences/KolakoskiSequenceTests.cs
@@ -27,8 +27,10 @@ public void First100ElementsCorrect()
             };
 
             var sequence = new KolakoskiSequence().Sequence.Take(100);
+            var sequence2 = new KolakoskiSequence2().Sequence.Take(100);
 
             sequence.Should().Equal(expected);
+            sequence2.Should().Equal(expected);
         }
     }
 }
diff --git a/Algorithms/Sequences/KolakoskiSequence2.cs b/Algorithms/Sequences/KolakoskiSequence2.cs
@@ -0,0 +1,46 @@
+using System.Collections.Generic;
+using System.Linq;
+using System.Numerics;
+
+namespace Algorithms.Sequences
+{
+    /// <summary>
+    ///     <para>
+    ///         Kolakoski sequence; n-th element is the length of the n-th run in the sequence itself.
+    ///     </para>
+    ///     <para>
+    ///         Wikipedia: https://en.wikipedia.org/wiki/Kolakoski_sequence.
+    ///     </para>
+    ///     <para>
+    ///         OEIS: https://oeis.org/A000002.
+    ///     </para>
+    /// </summary>
+    public class KolakoskiSequence2 : ISequence
+    {
+        /// <summary>
+        /// Gets Kolakoski sequence.
+        /// </summary>
+        public IEnumerable<BigInteger> Sequence
+        {
+            get
+            {
+                yield return 1;
+                yield return 2;
+                yield return 2;
+
+                var inner = new KolakoskiSequence2().Sequence.Skip(2);
+                var nextElement = 1;
+                foreach (var runLength in inner)
+                {
+                    yield return nextElement;
+                    if (runLength > 1)
+                    {
+                        yield return nextElement;
+                    }
+
+                    nextElement = 1 + nextElement % 2;
+                }
+            }
+        }
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -27,8 +27,10 @@ public void First100ElementsCorrect()`
`27`	`27`	`};`
`28`	`28`
`29`	`29`	`var sequence = new KolakoskiSequence().Sequence.Take(100);`
	`30`	`+ var sequence2 = new KolakoskiSequence2().Sequence.Take(100);`
`30`	`31`
`31`	`32`	`sequence.Should().Equal(expected);`
	`33`	`+ sequence2.Should().Equal(expected);`
`32`	`34`	`}`
`33`	`35`	`}`
`34`	`36`	`}`