Home > Blockchain >  function complex_decode( string str) that takes a non-simple repeated encoded string, and returns th
function complex_decode( string str) that takes a non-simple repeated encoded string, and returns th

Time:11-04

Im trying to write a function complex_decode( string str) in c sharp that takes a non-simple repeated encoded string, and returns the original un-encoded string. for example, "t11h12e14" would return "ttttttttttthhhhhhhhhhhheeeeeeeeeeeeee". I have been successful in decoding strings where the length is less than 10, but unable to work with length for than 10. I am not allowed to use regex, libraries or loops. Only recursions. This is my code for simple decode which decodes when length less than 10.

public string decode(string str)
    {
        
        if (str.Length < 1)
            return "";
        if(str.Length==2)
            return repeat_char(str[0], char_to_int(str[1]));
        else
            return repeat_char(str[0], char_to_int(str[1])) decode(str.Substring(2));
    }
public int char_to_int(char c)
    {
        return (int)(c-48);
    }
    public string repeat_char(char c, int n)
    {
        if (n < 1)
            return "";
        if (n == 1)
            return "" c;
        else
            return c   repeat_char(c, n - 1);
    }

This works as intended, for example input "a5" returns "aaaaa", "t1h1e1" returns "the"

Any help is appreciated.

CodePudding user response:

I've refactored your code a bit. I've removed 2 unnecessary methods that you don't actually need. So, the logic is simple and it works like this;

Example input: t3h2e4

  1. Get the first digit. (Which is 2 and has index of 1)
  2. Get the first letter comes after that index, which is our next letter. (Which is "h" and has index of 2)
  3. Slice the string. Start from index 1 and end the slicing on index 2 to get repeat count. (Which is 3)
  4. Repeat the first letter of string for repeat count times and combine it with the result you got from step 5.
  5. Slice the starting from the next letter index we got in second step, to the very end of the string and pass this to recursive method.
public static string Decode(string input)
{
    // If the string is empty or has only 1 character, return the string itself to not proceed.
    if (input.Length <= 1)
    {
        return input;
    }
    
    // Convert string into character list.
    var characters = new List<char>();
    characters.AddRange(input);
    
    var firstDigitIndex = characters.FindIndex(c => char.IsDigit(c)); // Get first digit
    var nextLetterIndex = characters.FindIndex(firstDigitIndex, c => char.IsLetter(c)); // Get the next letter after that digit
    if (nextLetterIndex == -1)
    {
        // This has only one reason. Let's say you are in the last recursion and you have c2
        // There is no letter after the digit, so the index will -1, which means "not found"
        // So, it will raise an exception, since we try to use the -1 in slicing part
        // Instead, if it's not found, we set the next letter index to length of the string
        // With doing that, you either get repeatCount correctly (since remaining part is only digits)
        //   or you will get empty string in the next recursion, which will stop the recursion.
        nextLetterIndex = input.Length;
    }
    
    // Let's say first digit's index is 1 and the next letter's index is 2
    // str[2..3] will start to slice the string from index 2 and will stop in index 3
    // So, it will basically return us the repeat count.
    var repeatCount = int.Parse(input[firstDigitIndex..nextLetterIndex]);
    
    // string(character, repeatCount) constructor will repeat the "character" you passed to it for "repeatCount" times
    return new string(input[0], repeatCount)   Decode(input[nextLetterIndex..]);
}

Examples;

Console.WriteLine(Decode("t1h1e1"));   // the
Console.WriteLine(Decode("t2h3e4"));   // tthhheeee
Console.WriteLine(Decode("t3h3e3"));   // ttthhheee
Console.WriteLine(Decode("t2h10e2"));  // tthhhhhhhhhhee
Console.WriteLine(Decode("t2h10e10")); // tthhhhhhhhhheeeeeeeeee

CodePudding user response:

Here is another way of doing this, assuming the repeating string is always one character long and using only recursion (and a StringBuilder object):

private static string decode(string value)
{
    var position = 0;
    var result = decode_char(value, ref position);
    return result;
}

private static string decode_char(string value, ref int position)
{
    var next = value[position  ];
    var countBuilder = new StringBuilder();            
    get_number(value, ref position, countBuilder);
    var result = new string(next, Convert.ToInt32(countBuilder.ToString()));
    if (position < value.Length)
        result  = decode_char(value, ref position);
    return result;
}

private static void get_number(string value, ref int position, StringBuilder countBuilder)
{                        
    if (position < value.Length && char.IsNumber(value[position]))
    {
        countBuilder.Append(value[position  ]);                
        get_number(value, ref position, countBuilder);
    }            
}

CodePudding user response:

First you can simplify your repeat_char function, you have to have a clear stop condition:

public static string repeat_char(char c, int resultLength)
{
    if(resultLength < 1) throw new ArgumentOutOfRangeException("resultLength");     
    if(resultLength == 1) return c.ToString();
    return c   repeat_char(c, resultLength - 1);
}

See the use of the parameter as equivalent of a counter on a loop. So you can have something similar on the main function, a parameter that tells when your substring is not an int anymore.

public static string decode(string str, int repeatNumberLength = 1)
{
    if(repeatNumberLength < 1) throw new ArgumentOutOfRangeException("length");

    //stop condition
    if(string.IsNullOrWhiteSpace(str)) return str;

    if(repeatNumberLength >= str.Length) repeatNumberLength = str.Length; //Some validation, just to be safe
    
    //keep going until str[1...repeatNumberLength] is not an int
    int charLength;
    if(repeatNumberLength < str.Length && int.TryParse(str.Substring(1, repeatNumberLength), out charLength))
    {
        return decode(str, repeatNumberLength   1);
    }
    
    repeatNumberLength--;       
    //Get the repeated Char.
    charLength = int.Parse(str.Substring(1, repeatNumberLength));
    var repeatedChar = repeat_char(str[0], charLength);
    
    //decode the substring
    var decodedSubstring = decode(str.Substring(repeatNumberLength   1));
    return repeatedChar   decodedSubstring;
}

I used a default parameter, but you can easily change it for a more traditonal style. This also assumes that the original str is in a correct format.

An excellent exercise is to change the function so that you can have a word, instead of a char before the number. Then you could, for example, have "the3" as the parameter (resulting in "thethethe").

  • Related