all and sundry: July 2011

Tuesday, July 26, 2011

"n" slots - continued..

A different java implementation, closer to being a good functional implementation, but not quite there:

public List<String> fillNSlots(int n){
        return fillNSlotsWithPrefix(0, n, "");
         
    }
     
    private List<String> fillNSlotsWithPrefix(int counter, int  n, String prefix){
        if (counter==n-1){
            return new ArrayList<String>(Arrays.asList(new String[]{prefix + "0", prefix + "1"})); 
        }else{
            List<String> result1 = fillNSlotsWithPrefix(counter+1, n , prefix + "0");
            result1.addAll(fillNSlotsWithPrefix(counter+1, n , prefix + "1"));
            return result1;
        }
    }

It is not quite there, as there is still a need to hold an intermediate state with a temporary variable, result1 above, which could have been avoided had List supported an API which adds an element and returns itself or returns a new list.

The following is an equivalent implementation in scala:

def fillNSlots(n:Int):List[String] = {
        fillNSlotsWithPrefix(0,n,"")
    }
 
    def fillNSlotsWithPrefix(counter:Int, n: Int, prefix:String): List[String] = {
        if (counter==(n-1))
            (prefix+"0")::(prefix+"1")::List()
        else
            fillNSlotsWithPrefix(counter+1, n, prefix+"0"):::fillNSlotsWithPrefix(counter+1, n, prefix+"1")
    }

Sunday, July 24, 2011

"n" slots - different ways of filling it

The problem is simple - Given "n" slots, find all possible different configurations to fill the slots:
For "2" slots, the possible configurations are - [00, 01, 10, 11]
For "3" slots, the possible configurations are - [000, 001, 010, 011, 100, 101, 110, 111]

Here is a test for any solution:

@Test
    public void test2Slots() {
        String[] slotsAnswer = {"00","01", "10", "11"};
        assertThat(fillNSlots(2), hasItems(slotsAnswer));
    }
 
    @Test
    public void test3Slots() {
        String[] slotsAnswer = {"000", "001", "010", "011", "100", "101", "110", "111"};
        assertThat(fillNSlots(3), hasItems(slotsAnswer));
    }
 
    @Test
    public void test5Slots() {
        String[] slotsAnswer = {"00000", "00001", "00010", "00011", "00100", "00101", "00110", "00111", "01000", "01001", "01010", "01011", "01100", "01101", "01110", "01111", "10000", "10001", "10010", "10011", "10100", "10101", "10110", "10111", "11000", "11001", "11010", "11011", "11100", "11101", "11110", "11111"};
        assertThat(fillNSlots(5), hasItems(slotsAnswer));
    }

I have a naive solution to start with:

public List<String> fillNSlots(int n){
        List<String> result = new ArrayList<String>();
        fillNSlotsWithPrefix(result, n, "");
        return result;
    }
     
    private void fillNSlotsWithPrefix(List<String> result, int n, String prefix){
        if (n==0){
            result.add(prefix);
        }else{
            fillNSlotsWithPrefix(result, n-1, prefix + "0");
            fillNSlotsWithPrefix(result, n-1, prefix + "1");
        }
    }

This solution works, however state is being passed(an arraylist of result) with each of the "fillNSlotsWithPrefix" methods recursive calls. A pure functional method, however would not have had this side effect. I will fix this implementation to be more functional over the course of next week.