I have a problem and I already solved it, but I am searching for enhancement.

pythonatSheriff

Full Stack Web Developer
Joined
Dec 15, 2021
Messages
25
Location
Egypt
Programming Experience
1-3
Twitter
shiccorama
The problem is :

((Have the function MathChallenge(str) take the str parameter being passed and determine if there is some substring K that can be repeated N > 1 times to produce the input string exactly as it appears. Your program should return the longest substring K, and if there is none it should return the string -1.

For example: if str is "abcababcababcab" then your program should return abcab because that is the longest substring that is repeated 3 times to create the final string. Another example: if str is "abababababab" then your program should return ababab because it is the longest substring. If the input string contains only a single character, your program should return the string -1. ))

My solutions is :
my solution to math problem:
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;


class MainClass
{

  public static void Main(string[] arg1)
  {
        //abcababcababcab
        string str = "abababababab";

        int count = 0;
        for(var i=0; i<str.Length; i++)
        {
            count = count + 1;
        }
        Console.WriteLine(count);

        int division = 0;
        if(count%2 == 0)
        {
            //Console.WriteLine("can divide on 2");
            division = 2;
            
        }
        else if(count%3 == 0)
        {
            //Console.WriteLine("can divide on 3");
            division = 3;
        }


        char[] LooseLetters = str.ToCharArray();
        int LettersCount = (LooseLetters.Length)/(division);
        StringBuilder part1 = new StringBuilder(str);
        if(division == 2)
        {
            part1.Insert(LettersCount, ",");
            Console.WriteLine(part1);
        }
        else if(division == 3)
        {
            part1.Insert(LettersCount, ",");
            part1.Insert((2*LettersCount)+1, ",");
            Console.WriteLine(part1);
        }

        string strConverter = part1.ToString();

        List<string> DuplicateString = strConverter.Split(",").ToList();
        // foreach(var item in DuplicateString)
        // {
        //     Console.WriteLine(item);
        // }

        string result = "";

        if(division == 2)
        {
            if(DuplicateString[0] == DuplicateString[1])
            result = DuplicateString[0];
            else
            result = "-1";
        }
        else if(division == 3)
        {
            if(DuplicateString[0] == DuplicateString[1] && DuplicateString[0] == DuplicateString[2])
            result = DuplicateString[0];
            else
            result = "-1";
        }

        Console.WriteLine(result);

  }

}


Now, I feel like it can be done using (Linq) methods, although I read most of the methods, or there is a simpler solution, so I would like to know to increase my knowledge.
Thanks in advance.
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,085
Location
Chesapeake, VA
Programming Experience
10+
The original brute force substring matcher seems to be the best in terms of simplicity and speed.
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,085
Location
Chesapeake, VA
Programming Experience
10+
Interesting to see ModuloMatcher vs OffsetMatcher, the % operation obviously adds more computation than multiply index.
My gut feel is that the ModuloMatcher is not as cache or predictor friendly as OffsetMatcher. The OffsetMatcher is always looking forward in memory, while the ModuloMatcher has to peek back into the beginning of the memory block.
 

JohnH

C# Forum Moderator
Staff member
Joined
Apr 23, 2011
Messages
1,415
Location
Norway
Programming Experience
10+
The original brute force substring matcher seems to be the best in terms of simplicity and speed.
Unfortunately that one has serious bug, it is cheating by starting the loop at index 2 (the third part), if there is only two parts in input it skip the test and just return true 😮 So the for loop in SubstringMatcher must start with 1. (I updated post 3 now also for this)

Further there is a couple of big bugs in your RegexMatcher and LinqMatcher, neither runs in a loop, they match input in one go by "repeat tricks", their AllPartsEqual overrides must be changed to:
RegexMatcher:
var partsCount = input.Length / part.Length;
return Regex.IsMatch(input, $"({part}){{{partsCount}}}");
LinqMatcher:
var partsCount = input.Length / part.Length;
return string.Concat(Enumerable.Repeat(part, partsCount)) == input;
Actually the partCount here is recalculated, the i suggested in post 6 was the i from outer loop (in SubstringPartsMatcher).

Then the results change considerably for RegexMatcher and LinqMatcher, and almost no change for SubstringMatcher:
C#:
|           Method |        Mean |    Error |   StdDev |    Gen 0 |    Gen 1 |    Gen 2 | Allocated |
|----------------- |------------:|---------:|---------:|---------:|---------:|---------:|----------:|
| SubstringMatcher |    133.2 us |  1.17 us |  0.91 us |  16.3574 |        - |        - | 138,824 B |
|     SplitMatcher |    267.8 us |  3.65 us |  3.41 us |  41.5039 |  41.5039 |  41.5039 | 134,956 B |
|     RegexMatcher |    170.8 us |  0.81 us |  0.76 us |   0.2441 |        - |        - |   2,176 B |
|      LinqMatcher |    239.6 us |  1.57 us |  1.31 us |  83.0078 |  83.0078 |  83.0078 | 265,420 B |
| PureRegexMatcher | 10,900.7 us | 95.01 us | 84.22 us |        - |        - |        - |     504 B |
|    OffsetMatcher |    162.6 us |  0.95 us |  0.89 us |        - |        - |        - |     536 B |
|    ModuloMatcher |    375.5 us |  1.23 us |  1.15 us |        - |        - |        - |     536 B |
|       KmpMatcher |    265.8 us |  0.95 us |  0.80 us | 166.5039 | 166.5039 | 166.5039 | 529,040 B |
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,085
Location
Chesapeake, VA
Programming Experience
10+
I have a pending speed boost for the KMP matcher but using stackalloc instead of the heap. Code is currently in:

 
Top Bottom