Posts Tagged ‘coding challenge’

h1

Coding challenge

November 2, 2011

Here’s my brute-force clojure solution to Cedric Beust’s latest coding challenge. The code maintains a count of how many weights each combination can measure before iterating through the map and returning the maximum – which of course turns out to be all 40!

(def total 40)

(defn check
  ([a target]
    (if (= a target)
      1
      0))
  ([a b target]
    (if (or (= 1 (check a target)) (= 1 (check b target)) (= (+ a b) target) (= (- a b) target) (= (- b a) target))
      1
      0))
  ([a b c target]
    (if (= 0 (+ (check a b target) (check a c target) (check b c target) (check (+ a b) c target) (check (+ a c) b target) (check (+ b c) a target)))
      0
      1))
  ([a b c d target]
    (if (= 0 (+ (check a b c target) (check a b d target) (check b c d target) (check (+ a b) c d target) (check (+ a c) b d target) (check (+ a d) b c target) (check (+ b c) a d target) (check (+ b d) a c target) (check (+ c d) a b target)))
      0
      1)))

(defn numberOfWeights [combo]
  (loop [x 1 sum 0]
    (if (> x total)
      sum 
      (recur (inc x) (+ sum (check (first combo) (second combo) (nth combo 2) (nth combo 3) x))))))

(defn run 
  ([a b c d result]
    (let [combo [a b c d]] 
      (if (= total (+ a b c d)) 
        (assoc result combo (numberOfWeights combo))
        result)))
  ([a b c result]
    (let [d (- total (+ a b c))]
      (if (< d 0)
        result
        (run a b c d result))))
  ([a b result]
    (loop [c b r result]
      (if (>= (+ a b c) total)
        r
        (recur (inc c) (run a b c r)))))
  ([a result]
    (loop [b a r result]
      (if (>= (+ a b) (- total 1))
        r
        (recur (inc b) (run a b r)))))
  ([]
    (loop [a 1 result {}]
      (if (>= a (- total 2))
        result
        (recur (inc a) (run a result))))))

(def main
  (let [result (run)]
    (loop [resultKeys (keys result) maxKey nil maxValue 0]
      (let [candidate (first resultKeys)]
        (if (nil? candidate)
          {maxKey maxValue}
          (if (or (nil? maxKey) (> (get result candidate) maxValue))
            (recur (next resultKeys) candidate (get result candidate))
            (recur (next resultKeys) maxKey maxValue)))))))

Running it on the clojure console gives me:

user=> (load-file "/home/raghav/spikes/clojure/weights.clj")
#'user/main
user=> main
{[3 9 27 1] 40}

 

Advertisements
h1

Cedric’s Coding Challenge

July 3, 2008

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;
  }
}