Cedric’s Coding Challenge

I thought I would take an attempt at the coding challenge presented by Cedric. Most of the solutions presented in the comments to the post seemed to involve brute force using regex manipulations, with people complaining that the implementations were quite slow. I thought I would try a different implementation, a highly customised one for the specific problem stated, but one which runs in 734ms on my not-so-fast development machine.

One interesting sidenote to add. I was never good at combinatorics and I am probably quite wrong at this, but I figure that the number of combinations I have to worry about as the number of digits increase probably increases quite alarmingly. When dealing with 2 digit numbers, I had only C(2,2) = 1 combination to worry about. With 3 digit numbers, C(3,2) = 3 and with 4 digit numbers, C(4,2) = 6. So the next increase would give me C(5,2) = 10 different variations to worry about. This isn’t critical for this particular challenge, but for a real-world problem, I would have to generalise the solution!

public class CedricCodingChallenge {
  public static void main(String[] args) {
    CedricCodingChallenge codingChallenge =
      new CedricCodingChallenge();

    long startTime = System.currentTimeMillis();
    List<String> list = codingChallenge.populateList(1, 10000);
    long endTime = System.currentTimeMillis();

    System.out.println(Arrays.toString(list.toArray()));
    System.out.println(String.format(
      "Size of list: %d", list.size()));
    System.out.println(String.format("Biggest jump: %d",
      codingChallenge.getBiggestJump(list, 10000)));
    System.out.println(String.format(
      "Total time: %d", endTime - startTime));
  }

  private List<String> populateList(int start, int end) {
    List<String> whiteList = new ArrayList<String>();
    for (int i=start; i<end; i++)
      whiteList.add(String.format("%d", i));

    for (int i=0; i<=9; i++)
      removeDuplicatesFromWhiteList(whiteList, i);

    return whiteList;
  }

  private void removeDuplicatesFromWhiteList(
    List<String> list, int digitToRemove) {

    // Remove 2 digit numbers
    if (digitToRemove > 0) {
      String numberToRemove =
        String.format("%s%s", digitToRemove, digitToRemove);
      list.remove(numberToRemove);
    }

    for (int i=0; i<=9; i++) {
      if (i > 0) {
        // Remove 3 digit numbers where digit is the last 2
        String numberToRemove = String.format(
          "%s%s%s", i, digitToRemove, digitToRemove);
        list.remove(numberToRemove);
      }

      if (digitToRemove > 0) {
        // Remove 3 digit numbers where digit is the first 2
        String numberToRemove = String.format(
          "%s%s%s", digitToRemove, digitToRemove, i);
        list.remove(numberToRemove);

        // Remove 3 digit numbers where digit is the first and the last
        numberToRemove = String.format(
          "%s%s%s", digitToRemove, i, digitToRemove);
        list.remove(numberToRemove);
      }
    }

    for (int i=0; i<=9; i++)
      for (int j=0; j<=9; j++) {
        if (i > 0) {
          // Remove 4 digit numbers where digit is the last 2
          String numberToRemove = String.format(
            "%s%s%s%s", i, j, digitToRemove, digitToRemove);
          list.remove(numberToRemove);

          // Remove 4 digit numbers where digit is the middle 2
          numberToRemove = String.format(
            "%s%s%s%s", i, digitToRemove, digitToRemove, j);
          list.remove(numberToRemove);

          // Remove 4 digit numbers where digit is 2nd and 4th
          numberToRemove = String.format(
            "%s%s%s%s", i, digitToRemove, j, digitToRemove);
          list.remove(numberToRemove);
        }

        if (digitToRemove > 0) {
          // Remove 4 digit numbers where digit is the first 2
          String numberToRemove = String.format(
            "%s%s%s%s", digitToRemove, digitToRemove, i, j);
          list.remove(numberToRemove);

          // Remove 4 digit numbers where digit is 1st and 3rd
          numberToRemove = String.format(
            "%s%s%s%s", digitToRemove, i, digitToRemove, j);
          list.remove(numberToRemove);

          // Remove 4 digit numbers where digit is 1st and 4th
          numberToRemove = String.format(
            "%s%s%s%s", digitToRemove, i, j, digitToRemove);
          list.remove(numberToRemove);
        }
      }
  }

  private int getBiggestJump(List<String> list, int max) {
    int biggestJump = 1;
    int previous = 0, next = 0;
    ListIterator<String> iterator = list.listIterator();
    while (iterator.hasNext() || previous < max) {
      if (iterator.hasNext())
        next = Integer.parseInt(iterator.next());
      else
        next = max;
      int difference = next - previous;
      biggestJump =
        biggestJump >= difference? biggestJump : difference;
      previous = next;
    }
    return biggestJump;
  }
}