Friday 4 July 2008

Cedric's coding challenge

So, the latest little problem buzzing around is Cedric's coding challenge. I took Raghav's solution as a base, and just simplified it somewhat I think:



package com.bt.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

int max = 10000;

long startTime = System.currentTimeMillis();
List<String> list = codingChallenge.populateList(1, max);
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, max)));
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++)
whiteList = removeDuplicatesFromWhiteList(whiteList, i);

return whiteList;
}

private List<String> removeDuplicatesFromWhiteList(List<String> whiteList, int i) {
List<String> result = new ArrayList<String>(whiteList.size());
for (String item: whiteList) {
String c = String.format("%d", i);
int f = item.indexOf(c);
if (f < 0) {
result.add(item);
continue;
}
int l = item.lastIndexOf(c);
if (f == l) {
result.add(item);
continue;
}
}
return result;
}

private int getBiggestJump(List<String> list, int max) {
int result = 0;
int last = 0;
for (String item: list){
int i = Integer.parseInt(item);
int jump = i - last;
if (jump > result)
result = jump;
last = i;
}
if ((max - last) > result)
result = max - last;
return result;
}
}

My solution took 722ms.