3
\$\begingroup\$

In following of this question, I would like to have a second review.

The exercise is to write a recursive method that takes a String and a char parameter and returns a String with each occurrence of the char doubled. Additionally, the number of doubling operations should be added at the end of the string. No "extern" variables outside the method are allowed to use. The String parameter can contain any valid char, including numbers.

It's not allowed to use other (recursive) helper methods. The method signature and parameters must not to be change.

My code is working correctly now (I hope), but how to replace the "pre-"calculated map from line 7 to 25 with a simple formula/term? Thanks in advance.

import java.util.HashMap;

public class Redouble {
    public static String redouble(final String s, final char c) {
        if (s.length() > 0) {
            if (s.charAt(0) == c) {
                HashMap<Integer, Integer> map = new HashMap<>();
                map.put(2, 1);
                for (int j = 1; j <= 4; j++) {
                    int n0 = (int) Math.pow(10, j - 1);
                    int n1 = (int) Math.pow(10, j);
                    int i = n0;
                    for (; i < n0 + j; i++) {
                        int x = ((int) Math.log10(i) + i * 2 + 3 - j) / 2;
                        if (!map.containsKey(x)) {
                            map.put(x, j - 1);
                        }
                    }
                    for (; i < n1; i++) {
                        int x = ((int) Math.log10(i) + i * 2 + 3 - j) / 2;
                        if (!map.containsKey(x)) {
                            map.put(x, j);
                        }
                    }
                }
                //System.out.println("map = " + map);

                int len1 = s.length();
                String s1 = "" + c + c + redouble(s.substring(1), c);
                int len2 = s1.length();
                int lenDiff = len2 - len1;
                if (lenDiff > 0) {
                    int x = map.get(lenDiff);
                    //System.out.println(lenDiff + " " + x);
                    int n = Integer.parseInt(s1.substring(s1.length() - x));
                    return s1.substring(0, s1.length() - x) + (n + 1);
                }
                return s1;
            }
            return "" + s.charAt(0) + redouble(s.substring(1), c);
        }
        return "0";
    }

    public static void main(final String[] args) {
        // Some tests...
        String s = "0cac1c01";
        for (int i = 2; i <= 1010; i++) {
            s += "a";
            String s2 = redouble(s, 'a');
            System.out.println("Expected: " + i + ", actual: " + s2.substring(s2.length() - (int) Math.log10(i) - 1));
            if (!String.valueOf(i).equals(s2.substring(s2.length() - (int) Math.log10(i) - 1))) {
                System.out.println("ERROR");
                return;
            }
        }
    }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Could you please copy the problem statement from the other question, so we don't have to switch between two different ones? And is it a requirement that you recursively call the "method that takes a String and a char" recursively? Or is it allowed to use recursion in a helper method with additional parameters, as that would allow for a much simpler solution. \$\endgroup\$ Commented Dec 5, 2023 at 8:29
  • \$\begingroup\$ Thanks, I have edited my question with additional details. \$\endgroup\$ Commented Dec 5, 2023 at 13:35

3 Answers 3

1
+150
\$\begingroup\$

You can calculate the number of doublings instead of looking it up in a map. The code below is otherwise copied from @Roman's answer.

public static String redouble(final String s, final char c) {
    if (s.length() <= 0) {
        return "0";
    }

    if (s.charAt(0) != c) {
        return "" + s.charAt(0) + redouble(s.substring(1), c);
    }
    
    String original = s.substring(1);
    String doubled = redouble(original, c);
    // 1st estimate overestimates n because it includes its own string representation
    // 2nd estimate is correct or underestimates by one, as the length difference between
    // (n + n.toString().length()).toString() and n.toString() is 0 or 1 (prove it yourself)
    // 3rd estimate is definitely correct
    int n = doubled.length() - original.length();
    n -= ("" + n).length();
    if ((original + n).length() + n != doubled.length()) {
        n += 1;
    }

    return "" + c + c + doubled.substring(0, original.length() + n) + (n + 1);
}

The most complicated part is proving the assertion mentioned in the comment. The table illustrates what you have to prove for all n (the length difference is always 0 or 1):

 n        len(n)    n + len(n)   len(n + len(n))   difference
  0         1            1              1             0
  1         1            2              1             0
  2         1            3              1             0
  3         1            4              1             0
  4         1            5              1             0
 ...   
  8         1            9              1             0
  9         1           10              2             1
 10         2           12              2             0
 11         2           13              2             0
 ...
 97         2           99              2             0
 98         2          100              3             1
 99         2          101              3             1
100         3          103              3             0
 ...
\$\endgroup\$
1
  • \$\begingroup\$ Thanks, solved. :) I have an edit suggestion for determine the int length... \$\endgroup\$ Commented Dec 6, 2023 at 17:34
1
\$\begingroup\$

Nested If-Statements

You can simplify the code and improve the readability as a result. It is achievable by using the Guard Pattern which in short can break off nested if-statements by inverting the condition:

public static String redouble(final String s, final char c) {
    if (s.length() <= 0) {
        return "0";
    }

    if (s.charAt(0) != c) {
        return "" + s.charAt(0) + redouble(s.substring(1), c);
    }
    
    HashMap<Integer, Integer> map = /* creating the map */;

    int len1 = s.length();
    String s1 = "" + c + c + redouble(s.substring(1), c);
    int len2 = s1.length();
    int lenDiff = len2 - len1;
    
    if (lenDiff <= 0) {
        return s1;
    }
    
    int x = map.get(lenDiff);
    int n = Integer.parseInt(s1.substring(s1.length() - x));

    return s1.substring(0, s1.length() - x) + (n + 1);
}

The code readability is improved by eliminating the nested if-statements. Now the code is understandable by reading from top to bottom without thinking about the nested conditions.

Good Names for Variables are important

Without really knowing you problem statement it is hard to understand the code because the naming of the variables is poor.

If you don't have a good name: Don't give it a name. Variables like len1 are useless. First it is an abbreviation for length which is really just three characters longer. Second when I see len1 I know, that there will be by minimum a len2. But as a reader I'm not interested in the enumeration; I'm interested in the difference (for example of the origin) of those lengths.

As I already said: Don't give them a name if the name is poor. s.length() gives me more context as len1:

int len1 = s.length();
String s1 = "" + c + c + redouble(s.substring(1), c);
int len2 = s1.length();
int lenDiff = len2 - len1;

if (lenDiff <= 0) {
   return s1;
}

The name s1 is somehow useless. Maybe doubled fits better? And len1 and len2 are only used to calculate the lenDiff, thus we can omit them. And the same for lenDiff. Additionally, original could be a better name for s1:

String doubled = "" + c + c + redouble(original.substring(1), c);
if (doubled.length() - original.length() <= 0) {
    return doubled;
}

Further Simplification

s.length() <= 0 can be expressed as s.isEmpty():

if (s.isEmpty()) {
    return "0";
}

How to simplify the Map?

There are two ways. The first one is by simplifying the creation of the map and the second one is by don't use a map at all.

Simplify the Creation of the Map

If I am right, the map will always look the same. This means you could write your map by hand without to calculate all the keys and values. But… the map has maaaany keys.

How does the map look like?

{2=1, /*...*/ , 12=1, 13=2, /*...*/, 103=2, 104=3, /*...*/, 1004=3, 1005=4, /*...*/, 10000=4}

And the map will always look like this, because there is no variable that will make it dynamic.

So actually you could simplify the creation of the map to:

HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < 13) {
    map.put(i, 1);
}

for(int i = 13; i < 104) {
    map.put(i, 2);
}

for(int i = 104; i < 1005) {
    map.put(i, 3);
}

for(int i = 1005; i < 10000) {
    map.put(i, 4);
}

Don't use a Map at all

The map is used in this statement: int x = map.get(lenDiff);.

Instead of storing 10000 values inside a map to only query one value you could calculate the value: int x = /* some math to caluclate the value of x */;.

I don't know enough about the problem and the math behind the precalculation of the map, to know how a calculation of x could look like.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks. Can you tell something about creating or simplifying (avoiding) the map? \$\endgroup\$ Commented Dec 6, 2023 at 8:28
  • \$\begingroup\$ Tobias, I edited my post to simplify and also to avoid the map. I hope it will help you. \$\endgroup\$
    – Roman
    Commented Dec 6, 2023 at 9:19
0
\$\begingroup\$

You can simplify the calculation of the number of doubling operations using a mathematical formula instead of the pre-calculated map.

public class Redouble {
public static String redouble(final String s, final char c) {
    if (!s.isEmpty()) {
        if (s.charAt(0) == c) {
            int len1 = s.length();
            String s1 = "" + c + c + redouble(s.substring(1), c);
            int len2 = s1.length();
            int lenDiff = len2 - len1;
            if (lenDiff > 0) {
                // Extract the numeric part from the end of the string
                String numericPart = "";
                int index = s1.length() - 1;
                while (index >= 0 && Character.isDigit(s1.charAt(index))) {
                    numericPart = s1.charAt(index) + numericPart;
                    index--;
                }

                // Parse the numeric part as an integer
                int x = Integer.parseInt(numericPart);

                return s1.substring(0, s1.length() - numericPart.length()) + (x + 1);
            }
            return s1;
        }
        return "" + s.charAt(0) + redouble(s.substring(1), c);
    }
    return "0";
}

public static void main(final String[] args) {
    // Some tests...
    String s = "0cac1c01";
    for (int i = 2; i <= 1010; i++) {
        s += "a";
        String s2 = redouble(s, 'a');
        System.out.println("Expected: " + i + ", actual: " + s2.substring(s2.length() - (int) Math.log10(i) - 1));
        if (!String.valueOf(i).equals(s2.substring(s2.length() - (int) Math.log10(i) - 1))) {
            System.out.println("ERROR");
            return;
        }
    }
  }
}

Hope this helps

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think this will fail if the original string (before adding the number) ends with a digit. Your code will interpret that digit as part of the trailing number, which it isn't. \$\endgroup\$
    – Rainer P.
    Commented Dec 6, 2023 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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