2
\$\begingroup\$

Take in a natural number n ∈ N, then process and output a(n), with a(n) being the number of quaternary strings (with 0, 1, 2, 3) of length n, where (from left to right) there never follows a character (i + 1) directly after the character i.

For example, n=3 results in a(3) = 42: 000, 002, 003, 020, 021, 022, 030, 031, 032, 033, 100, 102, 103, 110, 111, 113, 130, 131, 132, 133, 200, 202, 203, 210, 211, 213, 220, 221, 222, 300, 302, 303, 310, 311, 313, 320, 321, 322, 330, 331, 332, 333.

How can performance be improved? n = 13 already takes 4 seconds.

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.Scanner;

public class Quaternary {

    public static void start(){
        Scanner reader = new Scanner(System.in).useLocale(Locale.US);
        System.out.print("Enter number n: ");
        int n = Integer.parseInt(reader.nextLine());
        List<String> stringList = new ArrayList<String>();

        long startTime = System.nanoTime();

        for (int k=0; k < 4; k++){
        findString(n, k, "", stringList);
        }

        System.out.println(“Number of strings with n = " + n +  " : "+ stringList.size());

        long estimatedTime = System.nanoTime() - startTime;
        double time = (double)estimatedTime / 1000000000.0;
        System.out.println(time);
    }

    public static void findString(int n, Integer lastNumber, String string, List<String> stringList)
    {
        string += lastNumber.toString();

        if (string.length() == n)
        {
            stringList.add(string);
        }
        else {
            for (int i = 0; i < 4; i++)
            {
                if (i != lastNumber+1)
                {
                    findString(n, i, string, stringList);
                }
            }
        }
    }


    public static void main(String[] args) {
        start();
    }
}
\$\endgroup\$

migrated from programmers.stackexchange.com Oct 17 '16 at 13:39

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • \$\begingroup\$ Have you timed your code in some way to figure out which part of the code is consuming the most time? \$\endgroup\$ – Robert Harvey Oct 7 '16 at 18:31
  • \$\begingroup\$ No I haven't. So placing time outputs at specific lines is the way to go? \$\endgroup\$ – Shlomo Goldstein Oct 7 '16 at 18:32
  • 1
    \$\begingroup\$ That's what I would do. \$\endgroup\$ – Robert Harvey Oct 7 '16 at 18:42
  • \$\begingroup\$ Why is there no 001? \$\endgroup\$ – candied_orange Oct 7 '16 at 19:21
  • \$\begingroup\$ "Take in a natural number n ∈ N, then process and output a(n), with a(n) being the number of quaternary strings (with 0, 1, 2, 3) of length n, where (from left to right) there never follows a character (i + 1) directly after the character i." \$\endgroup\$ – Shlomo Goldstein Oct 7 '16 at 19:50
1
\$\begingroup\$

This isn't something that can be solved by small optimizations to your current algorithm. Your problem is you are iterating through every valid combination, which is O(4n), where your requirements only call for you to count the valid combinations. This requires sometimes tricky analysis to find patterns you can exploit, but can usually be done in O(n log n) or better.

I approach these sorts of problems by drawing a tree, where the first four branches from the root are numbers where the first digit is 0, 1, 2, and 3 respectively, the next layer of branches down is the second digit, and so forth. With the restrictions you gave, an n=2 tree looks like this:

n=2 tree

Now the trick is for any value of n, you want to count how many leaves are on the tree without actually building the entire tree. Here, I take note that the count of each digit on the layer below is dependent on the count of other digits of the previous layer. For example, each 0 on one layer will produce one 0, one 2, and one 3 on the layer below. We don't much care what order those go in. We just want to count them. That can be done in O(n), as below:

depth = num_zeros = num_ones = num_twos = num_threes = 1

while depth < n: 
  num_zeros  = num_zeros + num_ones + num_twos + num_threes
  num_ones   =             num_ones + num_twos + num_threes
  num_twos   = num_zeros +            num_twos + num_threes
  num_threes = num_zeros + num_ones +          + num_threes
  depth = depth + 1

return num_zeros + num_ones + num_twos + num_threes
\$\endgroup\$
1
\$\begingroup\$

I dropped all thoughts of recursion and exploited some java tricks I happen to know to resolve padding issues and string building.

The big ideas were to NOT slurp all this up in memory but dump it out as soon as I could as well as transforming the "(i + 1) never follows i" rule into three simple tests.

Admittedly this hard codes the base but I think this approach is possible to generalize.

public static void main(String[] args) {
    Quaternary quaternary = new Quaternary(3);
    quaternary.generate();
}

class Quaternary{
    int base = 4;
    String zeroes;

    Quaternary(int length) {
        //String of zeros as long as length
        zeroes = new String(new char[length]).replace("\0", "0");
    }

    void generate() {
        for (int i = 0; i < (int)Math.pow(base, zeroes.length()); i++) {
            String s = Integer.toString(i, base);

            // pad with leading zeros if needed
            String result = s.length() < zeroes.length() 
                          ? zeroes.substring(s.length()) + s : s;

            if (!( result.contains("01")
                || result.contains("12")
                || result.contains("23")
            )) {
                System.out.print(", " + result);
            }
        }
    }
}

I called n length.

n=3 outputs

, 000, 002, 003, 020, 021, 022, 030, 031, 032, 033, 100, 102, 103, 110, 111, 113, 130, 131, 132, 133, 200, 202, 203, 210, 211, 213, 220, 221, 222, 300, 302, 303, 310, 311, 313, 320, 321, 322, 330, 331, 332, 333
\$\endgroup\$
1
\$\begingroup\$

We are dealing with a runtime upperbounded by something like 4^n here.

If you are building a list of strings anyway, why not reuse the list of valid strings in the list and append these values to a digit to get a new value?

public static void calculateQuarternary(int n) {

    int startPtr, endPtr;
    startPtr = endPtr = 0;

    ArrayList<String> alTemp = new ArrayList<String>();
    ArrayList<String> alCurrent = new ArrayList<String>();

    alCurrent.add("0");
    alCurrent.add("1");
    alCurrent.add("2");
    alCurrent.add("3");


    for (int i = 1; i < n; ++i) {

        endPtr = alCurrent.size();
        alTemp.clear();

        for (int j = 0; j < endPtr; ++j) {

            for (int k = 0; k < 4; ++k) {
                if (shouldAdd(alCurrent.get(j), k)) {
                    alTemp.add(k + alCurrent.get(j) + "");
                }
            }
        }

        alCurrent = new ArrayList<String>(alTemp);
    }
    System.out.println(alCurrent.size());
}

public static boolean shouldAdd(String s, int k) {

    int firstChar = (int)(s.charAt(0) - 48);
    return k + 1 != firstChar;
}
\$\endgroup\$
  • \$\begingroup\$ I'm not sure I can follow, \$\endgroup\$ – Shlomo Goldstein Oct 7 '16 at 20:06
  • \$\begingroup\$ One second- I will post some code soon. \$\endgroup\$ – Skorpius Oct 7 '16 at 21:20

Your Answer

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