2
\$\begingroup\$

I'm still learning c#, and I need my code to only run less than 2 seconds to be accepted. I have a look and say sequence and after the last number is found, the code sums it all up, and it takes so long if the element in the sequence is big.

Example:

Input: 2

Output: takes less than a second

Input: 50

Output: takes 4 or so seconds.

I have only tried doing is changing foreach loops into for loops. I don't know what else to change. Anyone can point me in the right direction? Thanks all.

namespace SumOfLookAndSaySequence
{
    class Program
    {

        static void Main(string[] args)
        {
            string input = Console.ReadLine();

            if (Int32.TryParse(input, out int nthTerm) && nthTerm > 0)
            {
                string lastSequence = GetSequence(nthTerm).Last();
                char[] digits = lastSequence.ToCharArray();
                int[] itemToSum = new int[digits.Length];
                int result = 0;
                for(int i = 0; i < digits.Length; i++)
                {
                    itemToSum[i] = int.Parse(digits[i].ToString());
                    result = result + itemToSum[i];
                }
                Console.WriteLine(lastSequence);
                Console.WriteLine(result);
            }

        }

        static IEnumerable<string> GetSequence(int nthTerm)
        {
            List<string> sequence = new List<string>() { "1" };

            for(int i = 1; i < nthTerm; i++)
            {
                sequence.Add(GetNextNumberSequence(sequence[i - 1]));
            }

            return sequence;
        }

        static string GetNextNumberSequence(string number)
        {
            StringBuilder stringBuilder = new StringBuilder();

            int count = 1;
            char digit = number[0];

            for(int i = 1; i < number.Length; i++)
            {
                if(number[i] == digit)
                {
                    count++;
                }
                else
                {
                    stringBuilder.Append(string.Concat(count, Char.GetNumericValue(digit)));

                    count = 1;
                    digit = number[i];
                }
            }

            stringBuilder.Append(string.Concat(count, digit));

            return stringBuilder.ToString();
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

I'd have to ask - do you have to Console.WriteLine() the output? Most code testing sites want a return value from a method rather than looking at the console output and clearly, the console output is going to be the vast majority of the time spent in the application.

Secondly, I have a few quick and easy tips for increasing performance:

  1. Ditch the string.Concats - you have the StringBuilder in hand and can just .Append() each of those items in turn:
stringBuilder.Append(count);
stringBuilder.Append(char.GetNumericValue(digit));

in the loop and

stringBuilder.Append(count);
stringBuilder.Append(digit);

after the loop.

  1. Pre-allocate list size: List<string> sequence = new List<string>(nthTerm + 1) { "1" }; This will reduce reallocations as the list grows (it starts at 4 and then increases by twice the size as necessary).

  2. Measure with precision - surround your processing code in Main with var SW = Stopwatch.StartNew(); and Console.WriteLine(sw.Elapsed);. This will show you the time your code actually took.

After I did these all the things listed above, 2 ran in 00:00:00.0006395 and 50 ran in 00:00:00.5806011.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the reply! the Console.WriteLine is only in my code for testing. The final code does'nt have that. I'll try your suggestions and comeback later if it improved or not. \$\endgroup\$ – Jonathan Tapnio Apr 21 '20 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.