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

Question

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));

• aepot: First i can see that you check if it 0 or 1 each iteration before calculations. Maybe reorder checks e.g. 3-4-1-2? Also you can use DivRem because you need both at once, also IsEven, IsZero, IsOne properties may help.
• Rick Davin: The link you provided suggests using tail recursion, which C# does not support natively.

Answer 1

The direct answer to my question of "why is it timing out on submission" turns out to be that it's running 10k super-large values. I suspect that this approach is a dead end

Some stats that may be of interest about the last test case:

• runs through the while loop 1992 times
• performs work in Normalize 331 times across all MediumInt instances
• bumping MediumInt's scratch values up to longs and setting the thresholds to +-4_500_000_000_000_000_000 only drops that count to 286

My initial reading of the problem (and some poking to get a couple of random known-correct super-large expected/actual pairs) suggested that the test included only a few of those super-large values, to prevent the naïve recursive solution from working. But, looping over that last test case 10k times runs in just over 28 seconds (twice the 12-second limit).

Answer 2

I don't understand your rationale for introducing the MediumInt class. You have written:

// the "MediumInt" is an attempt to reduce the number of BigInteger allocations, since
// they're immutable

The System.Numerics.BigInteger is a struct so there's no heap allocation anyway. I haven't profiled your code so it may be faster but maybe not for the reason you think. Sometimes it can be helpful to have a wrapper to avoid having to key into a dictionary twice:

public class Counter
{
 public BigInteger Current { get; set; }
}
// One example of using it:
if (!someDictionary.TryGetValue(someKey, out Counter c)
{
 someDictionary[someKey] = c = new Counter();
}
c.Current++;

This also shows something else you want to be doing, using TryGetValue. If you're looking up in your dictionary as much as I expect, it will yield a good gain. Applying it to your Enqueue local function, using the simplified Counter class and fixing the brace style:

void Enqueue(BigInteger toAdd, BigInteger parent)
{
 if (queue.TryGetValue(toAdd, out var counter))
 {
 counter.Value++;
 } 
 else
 {
 queue[toAdd] = counter = new Counter { Value = new BigInteger(1) };
 }
 if (parent != null && queue.TryGetValue(parent, out var parentCounter)) 
 {
 counter.Value += parentCounter.Value;
 }
}

All of this comes with the caveat that I have neither compiled nor run any of it. I can give it a test tomorrow and update if you don't try it before then. Have you attempted to work through the tail call recursion as the question suggests?

• minnmass: While BigInts are structs, my understanding is that they're immutable; thus, small operations (like incrementing/decrementing, like in Enqueue and Dequeue) get expensive because they instantiate a new instance. ... I've started looking at the tail call recursion, but I don't have enough math readily at hand to do it, alas.