I have a solution to this CodeWars challenge that’s being rejected as “too slow”.

Basically, write `public static BigInteger Fusc(BigInteger n)`

given:

- fusc(0) = 0
- fusc(1) = 1
- fusc(2 * n) = fusc(n)
- fusc(2 * n + 1) = fusc(n) + fusc(n + 1)

— CodeWars description (from part 1, which is formatted slightly nicer IMO)

I have the class below. `FuscInner`

is a literal, naïve implementation, to offer a “known good” answer if needed; it’s slow, but that’s fine. The trouble that I’m running into is that `FuscInnerTest`

runs against my test driver in a quarter second, but times out on CodeWars.

While I’m open to any suggestionst for cleaning up `FuscInnerTest`

or `MediumInt`

, my primary goal is to ascertain why it’s running so poorly when I submit to CodeWars (of course, I don’t know how many test cases it runs…).

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
public class FuscSolution {
public static BigInteger Fusc(BigInteger n) {
//var timer = System.Diagnostics.Stopwatch.StartNew();
var answer = FuscInnerTest(n);
//timer.Stop();
//Console.WriteLine($"{n} {answer} : {timer.Elapsed}");
//timer.Restart();
//answer = FuscInner(n);
//timer.Stop();
//Console.WriteLine($"{n} {answer} : {timer.Elapsed}");
return answer;
}
private static BigInteger FuscInner(BigInteger n) {
if (n == BigInteger.Zero) {
return BigInteger.Zero;
}
if (n == BigInteger.One) {
return BigInteger.One;
}
if (n % 2 == BigInteger.Zero) {
return FuscInner(n / 2);
}
var half = n / 2;
return FuscInner(half) + FuscInner(half + 1);
}
private static readonly Dictionary<BigInteger, BigInteger> _dict = new Dictionary<BigInteger, BigInteger> {
{ BigInteger.Zero, BigInteger.Zero },
{ BigInteger.One, BigInteger.One },
{ new BigInteger(3), new BigInteger(2) },
{ new BigInteger(5), new BigInteger(3) },
};
private static BigInteger FuscInnerTest(BigInteger n) {
// note: making this a Dictionary<BigInteger, BigInteger> worked quickly locally, too
// the "MediumInt" is an attempt to reduce the number of BigInteger allocations, since
// they're immutable
var queue = new Dictionary<BigInteger, MediumInt> {
{ n, new MediumInt(1) },
};
BigInteger answer = BigInteger.Zero;
while (queue.Any()) {
var current = queue.Keys.Max();
if (_dict.ContainsKey(current)) {
answer += _dict(current) * queue(current).ToBigInt();
queue.Remove(current);
} else {
Dequeue(current);
var half = current / 2;
Enqueue(half, current);
if (!current.IsEven) {
Enqueue(half + 1, current);
}
queue.Remove(current);
}
}
return answer;
void Dequeue(BigInteger toRemove) {
if (queue.ContainsKey(toRemove)) {
if (queue(toRemove).IsPositive()) {
queue(toRemove).Decriment();
} else {
queue.Remove(toRemove);
}
}
}
void Enqueue(BigInteger toAdd, BigInteger parent) {
if (queue.ContainsKey(toAdd)) {
queue(toAdd).Incriment();
} else {
queue(toAdd) = new MediumInt(1);
}
if (parent != null) {
if (queue.ContainsKey(parent)) {
queue(toAdd).Add(queue(parent));
}
}
}
}
private class MediumInt {
private const int max = 2_000_000;
private const int min = -2_000_000;
private BigInteger big = BigInteger.Zero;
private int current = 0;
public MediumInt(int initialValue) {
current = initialValue;
Normalize();
}
public bool IsZero() {
return big == BigInteger.Zero && current == 0;
}
public bool IsPositive() {
if (IsZero()) {
return false;
}
if (current == 0 && big <= 0) {
return false;
}
if (big == BigInteger.Zero && current <= 0) {
return false;
}
if (big == BigInteger.Zero) {
return current > 0;
}
if (big > BigInteger.Zero && big > Math.Abs(current)) {
return true;
}
if (big < BigInteger.Zero && big < Math.Abs(current)) {
return true;
}
throw new Exception("IsPositive unknown state");
}
public void Incriment() {
++current;
Normalize();
}
public void Decriment() {
--current;
Normalize();
}
public void Add(MediumInt value) {
current += value.current;
big += value.big;
Normalize();
}
public BigInteger ToBigInt() {
return big + current; ;
}
private void Normalize() {
if (current > max || current < min) {
big += current;
current = 0;
}
}
}
}
```

Driver code:

```
Assert.AreEqual(BigInteger.Zero, FuscSolution.Fusc(BigInteger.Zero));
Assert.AreEqual(BigInteger.One, FuscSolution.Fusc(BigInteger.One));
Assert.AreEqual(BigInteger.One, FuscSolution.Fusc(new BigInteger(4)));
Assert.AreEqual(new BigInteger(2), FuscSolution.Fusc(new BigInteger(3)));
Assert.AreEqual(new BigInteger(3), FuscSolution.Fusc(new BigInteger(10)));
Assert.AreEqual(new BigInteger(3), FuscSolution.Fusc(5));
Assert.AreEqual(new BigInteger(3), FuscSolution.Fusc(20));
Assert.AreEqual(new BigInteger(8), FuscSolution.Fusc(21));
Assert.AreEqual(new BigInteger(53), FuscSolution.Fusc(9007199254740991L));
// You need to pass these tests very quickly
BigInteger twoPThous = BigInteger.Pow(2, 1000);
Assert.AreEqual(new BigInteger(1001), FuscSolution.Fusc(twoPThous + BigInteger.One));
Assert.AreEqual(new BigInteger(1000), FuscSolution.Fusc(twoPThous - BigInteger.One));
Assert.AreEqual(new BigInteger(2996), FuscSolution.Fusc(twoPThous + 5));
Assert.AreEqual(new BigInteger(7973), FuscSolution.Fusc(twoPThous + 21));
Assert.AreEqual(new BigInteger(50245), FuscSolution.Fusc(twoPThous + 9007199254740991L));
var e = BigInteger.Parse("40441312560834288620677930197198699407914760287917495887121626854370117030034851815445037809554113527157810884542426113562558179684997500659084090344407986124994461497183");
var a = BigInteger.Parse("4496047232746033439866332574607641115185289828815659836877207557974698638551430698226403383854431074455323285812344476437334109742500243442945967768558521790671067401423809250553312923996658420643391496408098163895264498830090255970293513331630261702288646149000136895514918279039816543329290294321200");
Assert.AreEqual(e, FuscSolution.Fusc(a));
```