[Exercise] Array Sandwiches

Joe

(Adapted from Problem C of the first qualifier of the ACM Programming Contest of 2012/2013)

Presentation
Let's consider a set of Arrays (A1, A2, A3, ... ,An) of variable sizes. All the elements in these arrays are integers. All the arrays are sorted in an ascending order.

A sandwich is a set of indices (i1, i2, i3, ..., in) such as:

A1[i1] <= A2[i2] <= A3[i3] <= .. <= An[in] where "<=" is the inequality sign for "lesser than or equal"

Example
Consider the following arrays:

A1 = [1, 5, 7, 10]
A2 = [2, 6, 6, 8, 12]
A3 = [4, 5, 9]

Here are some examples of valid sandwiches of the above set:

(0, 0, 0) // Because 1 <= 2 <= 4

(1, 3, 2) // Because 5 <= 8 <= 9

Exercise
Given a set of arrays given as input, write a program that will calculate the number of valid sandwiches.
You are free to format your input in any way you want, and use any language you want. If your language of choice has a builtin function that does this (or something close enough), avoid using it.

geek

A brute force approach---for validating future results:
+ Generate the valid lists of indices lexicographically, i.e., {0, 0, ..., 0}, {0, 0, ..., 1}, ..., {0, 0, ..., |A_n|}, {0, 0, ..., 1, 0}, {0, 0, ..., 1, 1}, ..., {|A_0|, |A_1|, ..., |A_n|}, which can be done incrementally, one by one;
+ Filter the generated lists, selecting only the valid sandwiches;
+ Count the number of filtered lists.

L = {{1, 5, 7, 10}, {2, 6, 6, 8, 12}, {4, 5, 9}};

ArrayRange[s__] := Table[L[[i, List[s][[i]]]], {i, Length@L}];
ValidSandwich[s__] := {Ordering[ArrayRange[s]] == Range[Length@L], List[s]};

sandwiches = Flatten[Outer[ValidSandwich, Sequence @@ (Range[#] & /@ Length /@ L)], 2];
sandwiches = #[[2]] & /@ Select[%, #[[1]] &];

Table[L[[i, #[[i]]]], {i, Length@L}] & /@ %
sandwiches - 1
Length@%

{{1, 2, 4}, {1, 2, 5}, {1, 2, 9}, {1, 6, 9}, {1, 6, 9}, {1, 8, 9}, {5, 6, 9}, {5, 6, 9}, {5, 8, 9}, {7, 8, 9}}
{{0, 0, 0}, {0, 0, 1}, {0, 0, 2}, {0, 1, 2}, {0, 2, 2}, {0, 3, 2}, {1, 1, 2}, {1, 2, 2}, {1, 3, 2}, {2, 3, 2}}
10

Joe

@geek I did something similar in (terrible) JavaScript.

Here's the code:

/*
 * A is an array of ints.
 * 
 * Returns true if the input array is sorted in an ascending order.
 * 
 */
function sorted_ascend(A) {
    for (var i=0; i<A.length-1; ++i) {
        if (A[i] > A[i+1]) {
            return false;
        }
    }
    return true;
}

/*
 * A is a set of arrays
 * ind is a list of indices
 * 
 * This function will return true if ind is a sandwich to the set A
 * It does so by verifying that the following list is sorted:
 * 
 * # List comprehension in a Python-fashion
 * [ A[i][ind[i]] for i in range(0, len(A)) ]
 * 
 */
function is_sandwich (A, ind) {
    if (ind.length !== A.length) {
        return false;
    }

    var l = [];

    for (var i=0; i<ind.length; ++i){
        l.push(A[i][ind[i]]);
    }
    
    return sorted_ascend(l);
}


/*
 * face is an object
 * times is an integer
 * 
 * repeat ``face'' on an array, ``times'' times
 * e.g., array.repeat_push("hello", 3) pushes "hello" 3 times.
 * 
 * I use this function to initialize an array with a 0 repeated avariable number of times.
 * Is there a better way to do this?
 * 
 */
function repeat_face (face, times) {
    l = [];
    for (var i=0; i<times; ++i) {
        l.push(face);
    }

    return l;
}

/*
 * ind is an array of indices
 * ref is array holding the max values for each cell
 * 
 * The function returns true if each element of ind is lesser than its equivalent in ref
 * It returns false otherwise
 */
function valid_ind(ind, ref) {

    if (ind === undefined || ind.length !== ref.length) {
        return false;
    }

    for (var i=0; i<ref.length; ++i) {
        if (ind[i] >= ref[i]) {
            return false;
        }
    }
    
    return true;
}

/*
 * ind is an array holding the previous value.
 * ref is a reference array, holding the max value for each cell.
 * 
 * Starting with the rightmost cell, increment the value of ind until reaching the maximum 
 * defined in ref. Once the maximum is reached, reset to 0 and increment the cell on the left.
 * 
 * Do this recursively until all the cells reach their maximum.
 * Then return undefined, to mark the end of the generation process.
 * 
 */
function incr_ind(ind, ref) {
    carry = 1;
    for (var i=ref.length-1; i>=0; --i) {
        ind[i] += carry;
        carry =0;

        if (ind[i] >= ref[i]) {
            ind[i] = 0;
            carry = 1;
        }
    }
    
    return (carry === 0) ? ind : undefined;
}

/*
 * A is a set of arrays
 * 
 * Generate the valid lists of indices lexicographically 
 * i.e., 
 * {{0, 0, ..., 0}, {0, 0, ..., 1}, ..., {0, 0, ..., |An|}, 
 * {0, 0, ..., 1, 0}, {0, 0, ..., 1, 1}, ..., {|A0|, |A1|, ...,  |An|}}
 * 
 * 
 */
function all_indices(A) {
    // replace each array in A by its length
    // this is used to control the max value of each cell 
    // in the indices array.
    lengths_set = A.map(function (x) {
                            return x.length;});

    // initial indice array is [0, 0, 0, ..., 0]
    ind = repeat_face(0, A.length);

    // this array will hold all the valid indices.
    indices = [];

    // as long as the ind list is valid, append it to indices and increment.
    while (valid_ind(ind, lengths_set)) {
        indices.push(ind.slice());
        ind = incr_ind(ind, lengths_set);
    }

    return indices;
}

/*
 * array_set is an array containing all the input arrays.
 * 
 * Bruteforcing: Generate all the possible indices then filtering according
 * to the is_sandwich() test.
 */
function sandwiches(array_set) {
    return all_indices(array_set).filter(function(x) {
                                             return is_sandwich(this, x);
                                         }, array_set);
}

// main function
(function () {
    
     A1 = [1, 5, 7, 10];
     A2 = [2, 6, 6, 8, 12];
     A3 = [4, 5, 9];

     S = sandwiches([A1, A2, A3]);

     console.log(S);
     console.log(S.length);
         
})();

And here's the output I get:

[ [ 0, 0, 0 ],
[ 0, 0, 1 ],
[ 0, 0, 2 ],
[ 0, 1, 2 ],
[ 0, 2, 2 ],
[ 0, 3, 2 ],
[ 1, 1, 2 ],
[ 1, 2, 2 ],
[ 1, 3, 2 ],
[ 2, 3, 2 ] ]
10

Note: I'm very new to JavaScript, so more than ever I am looking for criticism of my code. I commented it to the best of my knowledge, I hope this will make it easier to read.

arithma

The original problem is nice. I think I have a solution:

//
//  main.cpp
//  sandwich
//
//  Created by arithma on 10/24/12.
//  Copyright (c) 2012 napkin. All rights reserved.
//

#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

struct Item{
    int array;
    int index;
    int val;
    
    bool operator<(Item const & item) const{
        return val < item.val;
    }
};

int main(int argc, const char * argv[])
{
    vector<int> A = {10, 20, 30};
    vector<int> B = {1, 2, 3};
    vector<int> C = {4, 5, 9};
    
    vector<vector<int> > arrays;
    arrays.push_back(A);
    arrays.push_back(B);
//    arrays.push_back(C);
    
    vector<Item> items;
    
    for(int i = 0; i < arrays.size(); i++)
        for(int j = 0; j < arrays[i].size(); j++){
            Item item = {i, j, arrays[i][j]};
            items.push_back(item);
        }
    
    sort(items.begin(), items.end());
    
    int minDiff = INT_MAX;
    vector<Item> minSandwich;
    for(int i = 0; i < items.size(); i++){
        cout << "i = " << i << endl;
        vector<Item> sandwich;
        set<int> usedArrays;
        int idx = i;
        while(idx < items.size() && usedArrays.size() < arrays.size()){
            cout << "idx = " << idx << endl;
            while(idx < items.size() && usedArrays.find(items[idx].array) != usedArrays.end()){
                idx++;
            }
            
            if(idx < items.size()){
                cout << items[idx].array << " " << items[idx].index << " " << items[idx].val << ";" << endl;
                sandwich.push_back(items[idx]);
                usedArrays.insert(items[idx].array);
            }
            idx++;
        }
        
        if(usedArrays.size() == arrays.size()){
            cout << "found a sandwich" << endl;
            int diff = sandwich.back().val - sandwich.front().val;
            if(diff < minDiff){
                minDiff = diff;
                minSandwich = sandwich;
            }
        }
    }
    
    cout << minDiff << endl;
    for(int i = 0; i < minSandwich.size(); i++){
        cout << minSandwich[i].array << " " << minSandwich[i].index << " " << minSandwich[i].val << "; ";
    }
    cout << endl;
    
    return 0;
}

arithma

If your language of choice has a builtin function that does this (or something close enough), avoid using it.

I really hate this requirement. It's really hard to define rigorously in mathematical terms. And what's the harm if someone shows that some language can solve a certain problem with a single function call. The burden of requiring genuinity is on the problem maker, and not on the problem solver.

Ayman

Another brute-force solution with Python. Recusively generates all possible permutations and saves those that form a sandwich storing the indexes and respective values of sandwiches in a list of tuples: ([indexes list],[values list]).

def getSand(A,rows,idx):
    if rows == len(matrix):
        vals = [A[i][idx[i]] for i in xrange(0,len(A))]
        
        if(checkSand(vals)):
            sandwiches.append((idx[:],vals))      
    else:
        for i in xrange(0,len(A[rows])):
            idx.append(i)
            getSand(A,rows+1,idx)
            idx.pop()

sandwiches = []

checkSand = lambda l:all(x <= y for x,y in zip(l,l[1:]))

A1 = [1, 5, 7, 10]
A2 = [2, 6, 6, 8, 12]
A3 = [4, 5, 9]

matrix = [A1, A2, A3]

getSand(matrix,0,[])

print sandwiches

print len(sandwiches)

Output

[([0, 0, 0], [1, 2, 4]), ([0, 0, 1], [1, 2, 5]), ([0, 0, 2], [1, 2, 9]), ([0, 1, 2], [1, 6, 9]), ([0, 2, 2], [1, 6, 9]), ([0, 3, 2], [1, 8, 9]), ([1, 1, 2], [5, 6, 9]), ([1, 2, 2], [5, 6, 9]), ([1, 3, 2], [5, 8, 9]), ([2, 3, 2], [7, 8, 9])]

10

I liked this exercise, thinking of possible non brute-force solution, actually having the lists given sorted should be made use of.

ChristianKallas

Hello, I did the exercise in Java, in my code the user can enter the elements of the 3 arrays (and choose how much elements each should contain)!
That's the code:

 import java.util.*;

public class sandwiches {

	public static void main(String[] args) { 
		
		int n1 = 0, n2 = 0 , n3 = 0;
		Scanner scan = new Scanner(System.in);


		System.out.println("Please enter the number of integers in your first array: " );
		n1 = scan.nextInt();	
		System.out.println("Please enter the number of integers in your second array: " );
		n2 = scan.nextInt();
		System.out.println("Please enter the number of integers in your third array: " );
		n3 = scan.nextInt();
		
		int[] arr1 = new int[n1];
		int[] arr2 = new int[n2];
		int[] arr3 = new int[n3];
	
		System.out.println("Now please enter the elements of the first array: ");

		for (int i=0; i<n1; i++){ 
		arr1[i] = scan.nextInt();
		 }

		System.out.println("Now please enter the elements of the second array: ");

		for (int i=0; i<n2; i++){ 
		arr2[i] = scan.nextInt();
		 }

		System.out.println("Now please enter the elements of the third array: ");

		for (int i=0; i<n3; i++){ 
		arr3[i] = scan.nextInt();
		 }
		
		
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		Arrays.sort(arr3);


		for (int a=0; a<arr1.length; a++) 
		for (int b=0; b<arr2.length; b++)  
		for (int c=0; c<arr3.length; c++) 
		if ((arr1[a]<=arr2[b]) && (arr2[b]<=arr3[c])) System.out.println("("+a+","+b+","+c+")");
		
		
		
		

	}

}

raja

This seems like a pretty straightforward DP problem. The essential realisation is that once you hit a particular index in a particular row, the number of sandwiches you can find from that point on is independent of how you got there in the first place. You can take two approaches from there on out, either use memoization(that is, cache the result, keying by <row,index> so you don't recurse on a <row,index> pair more than once given that you'll be getting the same result) or build your answer from bottom row to top(given that each row's answer only depends on the one below it, so there's no need for recursion if that one is already fully calculated).

I'll show both approaches. First, memoization(easier to do because you just write the recursive algorithm and add caching). The brute-force recursive algorithm is:

num_calls = 0
def get_number_of_sandwiches(A, row=0, last_value=None):
    global num_calls
    num_calls += 1
    if row >= len(A):
        return 1

    result = 0
    for e in A[row]:
        if last_value is None or e >= last_value:
            result += get_number_of_sandwiches(A,row+1, e)
    return result

A1 = [1, 5, 7, 10]
A2 = [2, 6, 6, 8, 12]
A3 = [4, 5, 9]

matrix = [A1, A2, A3]
print get_number_of_sandwiches(matrix) # This will output 10 for this case
print num_calls # this will output 23 for this case, we can do better

Then we add caching:


sandwich_cache = {}
num_calls = 0
def get_number_of_sandwiches(A, row=0, last_value=None):
    global num_calls, sandwich_cache
    num_calls += 1
    if row >= len(A):
        return 1

    result = 0
    for i,e in enumerate(A[row]):
        if last_value is None or e >= last_value:
            key = (row,i)
            if key not in sandwich_cache:
                sandwich_cache[key] = get_number_of_sandwiches(A,row+1, e)
            result += sandwich_cache[key]
    return result

This time we get 11 for num_calls. The difference would be extremely bigger for larger arrays. For the matrix:

matrix = [A1, A2, A3,
          A3, A3, A3,
          A3, A3, A3]

I get 23 calls with caching versus 188 without.

As for the build it from the bottom approach. Below is the code:

def get_number_of_sandwiches2(A):
    # B should be a matrix the same size of A with all cells 0 except the last row where they're 1
    # we use B to keep track of intermediate results
    B = [] 
    for i in range(len(A)-1):
        B.append([0]*len(A[i]))
    B.append([1]*len(A[-1]))
        
    for i in range(len(A)-2, -1, -1): # start from the row before last and go up
        for j,e in enumerate(A[i]):
            for k,f in enumerate(A[i+1]):
                if e <= f:
                    B[i][j] += B[i+1][k]
    return sum(B[0])

CodingFreak

Brute-force recursive solution in C++:

#include <iostream>
#include <vector>
using namespace std;

int total;

int sandwich(vector<vector<int> >* arrays, int level, int index_previous, int index_current) {

    if(level != 0 && arrays->at(level).at(index_current) < arrays->at(level-1).at(index_previous))
        return 0;
    
    else if(level == arrays->size()-1)
        return 1;
    
    else
        for (int i = 0; i < arrays->at(level+1).size(); i++)
            total += sandwich(arrays, level+1, index_current, i);
}

int main() {
	
    vector<vector<int> > arrays;
	
    vector<int> A0{-999};
    vector<int> A1{1, 5, 7, 10};
    vector<int> A2{2, 6, 6, 8, 12};
    vector<int> A3{4, 5, 9};

    arrays.push_back(A0);
    arrays.push_back(A1);
    arrays.push_back(A2);
    arrays.push_back(A3);

    sandwich(&arrays, 0, 0, 0);
    cout << total << endl;
}