Number of ways to have breakfast

Problem:
Find the number of ways you can have breakfast in ‘n’ days, given Bread-butter can be eaten every day, Pizza can be eaten every alternate day and Burger can be eaten every two days. Only one item can be eaten on a given day.

Solution:
Let us call the sequence of breakfast item on the days as timetable. And the condition of whether a particular item can be consumed on a given day as constraint.

Approach 1:
Create the timetable while checking that the constraints are met.

Approach 2:
Generate all possible timetables and eliminate the timetables that do not meet the constraints.

Java Program:

package com.sourabh.practice;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Breakfast {
    public static void main(String[] args) {
        String[] menu = new String[]{"Bread-butter", "Pizza", "Burger"};
        int[] constraint = new int[]{1, 2, 3};
        List<List<String>> timeTableList = new ArrayList<>();
        List<String> timeTable = new ArrayList<>();
        int n = 3;
        Breakfast breakfast = new Breakfast();
        breakfast.countNumberOfWaysEvaluationApproach(menu, constraint, timeTableList, timeTable, n);
        System.out.println(timeTableList.size());
    }
    
    public void countNumberOfWaysEvaluationApproach(String[] menu, int[] constraint, List<List<String>> timeTableList, List<String> timeTable, int n) {
        if(timeTable.size() == n) {
            // For unit-testing purpose
            List<String> output = new ArrayList<>();
            for(String food : timeTable) {
                System.out.print(food + " ");
                output.add(food);
            }
            System.out.println();
            timeTableList.add(output);
        } else {
            List<String> possibilities = new ArrayList<>();
            boolean found = false;
            for(int i=0; i<constraint.length; i++) {
                for(int j=1; j<constraint[i]; j++) {
                    if(timeTable.size() - j >=0 && timeTable.get(timeTable.size() - j).equals(menu[i])) {
                        found = true;
                    }
                }
                if(!found) {
                    possibilities.add(menu[i]);
                } else {
                    found = false;
                }
            }
            for(String possibility : possibilities) {
                timeTable.add(possibility);
                countNumberOfWaysEvaluationApproach(menu, constraint, timeTableList, timeTable, n);
                timeTable.remove(timeTable.size() - 1);
            }
        }
    }
    
    public void countNumberOfWaysExhaustiveApproach(String[] menu, int[] constraint, List<List<String>> timeTableList, List<String> timeTable, int n) {
        generatePermutation(menu, timeTableList, timeTable, n);
        Iterator<List<String>> iterator = timeTableList.iterator();
        while(iterator.hasNext()) {
            List<String> output = iterator.next();
            boolean passed = true;
            for(int i=0; i<menu.length; i++) {
                int occ1 = -1;
                int occ2 = -1;
                for(int j = 0; j < output.size(); j++) {
                    if(output.get(j).equals(menu[i])) {
                        if(occ1 < 0) {
                            occ1 = j;
                        } else {
                            occ2 = occ1;
                            occ1 = j;
                        }
                    }
                    if(occ1 >= 0 && occ2 >= 0 && occ1 > occ2 && occ1 - occ2 < constraint[i]) {
                        passed = false;
                    }
                }
            }
            if(!passed) {
                iterator.remove();
            }
        }
        for(List<String> output : timeTableList) {
            for(String food : output) {
                System.out.print(food + " ");
            }
            System.out.println();
        }
        System.out.println(timeTableList.size());
    }
    
    public void generatePermutation(String[] menu, List<List<String>> timeTableList, List<String> timeTable, int n) {
        if(timeTable.size() == n) {
            // For unit-testing purpose
            List<String> output = new ArrayList<>();
            for(String food : timeTable) {
                output.add(food);
            }
            timeTableList.add(output);
        } else {
            for(int i=0; i<menu.length; i++) {
                timeTable.add(menu[i]);
                generatePermutation(menu, timeTableList, timeTable, n);
                timeTable.remove(timeTable.size() - 1);
            }
        }
    }
} 

Sample Output:

Bread-butter Bread-butter Bread-butter 
Bread-butter Bread-butter Pizza 
Bread-butter Bread-butter Burger 
Bread-butter Pizza Bread-butter 
Bread-butter Pizza Burger 
Bread-butter Burger Bread-butter 
Bread-butter Burger Pizza 
Pizza Bread-butter Bread-butter 
Pizza Bread-butter Pizza 
Pizza Bread-butter Burger 
Pizza Burger Bread-butter 
Pizza Burger Pizza 
Burger Bread-butter Bread-butter 
Burger Bread-butter Pizza 
Burger Pizza Bread-butter 
15

Unit Tests:

package com.sourabh.practice;

import static org.junit.Assert.*;

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

import org.junit.Assert;
import org.junit.Test;

public class BreakfastTests {
    Breakfast breakfast = new Breakfast();
    @Test
    public void testCountNumberOfWaysInTermsOfFrequency() {
        String[] menu = new String[]{"Bread-butter", "Pizza", "Burger"};
        int[] constraint = new int[]{1, 2, 3};
        List<List<String>> timeTableList = new ArrayList<>();
        List<String> timeTable = new ArrayList<>();
        int n = 3;
        Breakfast breakfast = new Breakfast();
        breakfast.countNumberOfWaysEvaluationApproach(menu, constraint, timeTableList, timeTable, n);
        boolean passed = true;
        for(List<String> output : timeTableList) {
            for(int i=0; i<menu.length; i++) {
                int occ1 = -1;
                int occ2 = -1;
                for(int j = 0; j < output.size(); j++) {
                    if(output.get(j).equals(menu[i])) {
                        if(occ1 < 0) {
                            occ1 = j;
                        } else {
                            occ2 = occ1;
                            occ1 = j;
                        }
                    }
                    if(occ1 >= 0 && occ2 >= 0 && occ1 > occ2 && occ1 - occ2 < constraint[i]) {
                        passed = false;
                    }
                }
            }
        }
        Assert.assertTrue(passed);
    }
    
    @Test
    public void testCountNumberOfWaysInTermsOfExhaustiveness() {
        String[] menu = new String[]{"Bread-butter", "Pizza", "Burger"};
        int[] constraint = new int[]{1, 2, 3};
        List<List<String>> timeTableList = new ArrayList<>();
        List<String> timeTable = new ArrayList<>();
        int n = 3;
        Breakfast breakfast = new Breakfast();
        breakfast.countNumberOfWaysExhaustiveApproach(menu, constraint, timeTableList, timeTable, n);
        boolean passed = true;
        for(List<String> output : timeTableList) {
            for(int i=0; i<menu.length; i++) {
                int occ1 = -1;
                int occ2 = -1;
                for(int j = 0; j < output.size(); j++) {
                    if(output.get(j).equals(menu[i])) {
                        if(occ1 < 0) {
                            occ1 = j;
                        } else {
                            occ2 = occ1;
                            occ1 = j;
                        }
                    }
                    if(occ1 >= 0 && occ2 >= 0 && occ1 > occ2 && occ1 - occ2 < constraint[i]) {
                        passed = false;
                    }
                }
            }
        }
        Assert.assertTrue(passed);
    }
    
    @Test
    public void testCountNumberOfWaysInTermsOfAccuracy() {
        String[] menu = new String[]{"Bread-butter", "Pizza", "Burger"};
        int[] constraint = new int[]{1, 2, 3};
        List<List<String>> timeTableList = new ArrayList<>();
        List<String> timeTable = new ArrayList<>();
        int n = 3;
        Breakfast breakfast = new Breakfast();
        Long start1 = System.currentTimeMillis();
        breakfast.countNumberOfWaysEvaluationApproach(menu, constraint, timeTableList, timeTable, n);
        Long end1 = System.currentTimeMillis();
        int size1 = timeTableList.size();
        timeTableList = new ArrayList<>();
        timeTable = new ArrayList<>();
        Long start2 = System.currentTimeMillis();
        breakfast.countNumberOfWaysExhaustiveApproach(menu, constraint, timeTableList, timeTable, n);
        Long end2 = System.currentTimeMillis();
        int size2 = timeTableList.size();
        Assert.assertEquals(size1, size2);
        System.out.println(end1 - start1);
        System.out.println(end2 - start2);;
    }
}