c# – CodeWars kata Fusc function running too long, but very fast locally

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

Basically, write public static BigInteger Fusc(BigInteger n) given:

  1. fusc(0) = 0
  2. fusc(1) = 1
  3. fusc(2 * n) = fusc(n)
  4. 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));