How can you determine how to place coins on a clock?

Question

Say you are given a set of coins such as 4 10¢, 4 5¢, and 4 1¢.

You are asked to place these coins on a 12-hour analog clock face, where the next coin you place must be placed at X hours after the previous coin, where X is the value of the previous coin.

So if you place a 1¢ on 12, the next coin you place goes at 1. If you place a 5¢ on 1, the next coin you place goes at 6. And so on.

How can you maximize the number of coins that can be placed on the clock before the next coin would have to be placed in a slot that is already taken?

This is a problem I came across which I have been unable to solve except via exhaustive search. If the inputs are made to be arbitrary, exhaustive search fails quickly-- say it's an arbitrary number of coins of arbitrary various known denominations, with an arbitrary number of hours on the clock. Then you can't do exhaustive search anymore, because it becomes factorial time and fails on basis of excessive computational time requirements.

Answer 1

As maraca mentioned probably there isn't a much better solution than backtracking without more restrictions. Maybe with a larger number of coins of given denominations space can be covered with 'patterns'. Like coins [5, 10, 10, 5, 10, 10, 5, x] cover first 8 places and next coin is placed in similar location as first one. So the process can be repeated if there are enough coins.

Number of possible coin combinations in this case is not large at all. It is 12! / (4! * 4! * 4!) = 34650. For sure number explodes with larger parameters. Here is simple python code that solves 3 times larger problem which has possible coin combinations 3*10^15.

max_positions = []
max_order = None

def add_coin(coins, position, coin_order, occupied_positions, num_hours):
    global max_positions, max_order
    if position in occupied_positions or not coins:
        # Can't place on that position or there is nothing more to place
        if len(occupied_positions) > len(max_positions):
            max_positions = occupied_positions
            max_order = coin_order
        return not coins  # if all is covered return true to stop search
    #
    for c, num_coins in coins:  # Try each coin
        # Copy coins to new list and remove one used
        c_coins = [x for x in coins if x[0] != c]
        if num_coins > 1:
            c_coins.append((c, num_coins-1))
        # Next iteration
        if add_coin(c_coins,
                 (position + c) % num_hours,
                 coin_order + [c],
                 occupied_positions + [position],
                 num_hours):
            return True

def solve_coins(coins, num_hours):
    global max_positions, max_order
    max_positions = []
    max_order = None
    add_coin(coins, 0, [], [], num_hours)
    print len(max_positions), max_positions, max_order

solve_coins([(1, 4), (5, 4), (10, 4)], 12)
solve_coins([(1, 8), (5, 8), (10, 8)], 24)
solve_coins([(1, 12), (5, 12), (10, 12)], 36)

output:

12 [0, 1, 6, 4, 2, 3, 8, 9, 7, 5, 10, 11] [1, 5, 10, 10, 1, 5, 1, 10, 10, 5, 1, 5]
24 [0, 1, 6, 16, 17, 3, 4, 14, 19, 5, 15, 20, 21, 2, 7, 8, 13, 18, 23, 9, 10, 11, 12, 22] [1, 5, 10, 1, 10, 1, 10, 5, 10, 10, 5, 1, 5, 5, 1, 5, 5, 5, 10, 1, 1, 1, 10, 10]
36 [0, 1, 6, 16, 17, 22, 23, 28, 2, 12, 13, 18, 19, 29, 34, 3, 8, 9, 10, 11, 21, 31, 5, 15, 20, 30, 35, 4, 14, 24, 25, 26, 27, 32, 33, 7] [1, 5, 10, 1, 5, 1, 5, 10, 10, 1, 5, 1, 10, 5, 5, 5, 1, 1, 1, 10, 10, 10, 10, 5, 10, 5, 5, 10, 10, 1, 1, 1, 5, 1, 10, 5]

Answer 2

// Expressing the coins as a list of buckets with the same modulo allows
// you to efficiently find the next coin to test and you don't start to
// calculate with the first penny and then do the same again starting
// with the second penny (or a 13-coin on a 12-clock), it is basically the same.
// Additionally it allows to remove and insert items at the current position in O(1).
// Also reverting is much better than copying whole states on each recursive call.
private class Bucket {
    public int number;
    public LinkedList<Integer> numbers = new LinkedList<>();
    public Bucket(int number, int hours) {
        this.number = number % hours;
        numbers.add(number);
    }
}

private LinkedList<Bucket> coins; // not using interface List as you are supposed to
private LinkedList<Integer> best, current; // because of removeLast()
private boolean[] occupied;
private int hours, limit;

public List<Integer> findBest(int[] coins, int hours) {
    this.hours = hours;
    // create buckets of coins with the same modulo
    Integer[] c = Arrays.stream(coins).boxed().toArray( Integer[]::new );
    // sort descending because a lot of small coins in a row are more likely to create
    // an impassable area on the next pass around the clock
    Arrays.sort(c, new Comparator<Integer>(){
        public int compare(Integer a, Integer b) {
            return Integer.compare(b.intValue() % hours, a.intValue() % hours);
        }
    });
    this.coins = new LinkedList<>();
    Bucket b = new Bucket(c[0].intValue(), hours);
    this.coins.add(b);
    int mod = c[0].intValue() % hours, coinCount = 1;
    for (int i = 1; i < c.length; i++) {
        int m = c[i].intValue() % hours;
        if (m == mod) { // same bucket
            b.numbers.add(c[i]);
        } else { // new bucket
            b = new Bucket(c[i].intValue(), hours);
            this.coins.add(b);
            mod = m;
        }
        coinCount++;
        if (mod == 0) // don't need more than one 0 value
            break;
    }
    best = new LinkedList<>();
    current = new LinkedList<>();
    occupied = new boolean[hours];
    limit = coinCount < hours ? coinCount : hours; // max coins that can be placed
    findBest(0);
    return best;
}

private void findBest(int pos) {
    if (best.size() == limit) // already found optimal solution
        return;
    if (occupied[pos] || current.size() == limit) {
        if (current.size() > best.size())
            best = (LinkedList<Integer>)current.clone();
        return;
    }
    occupied[pos] = true;
    for (int i = 0; i < coins.size(); i++) {
        Bucket b = coins.get(i);
        current.add(b.numbers.removeLast());
        boolean removed = false;
        if (b.numbers.size() == 0) { // bucket empty
            coins.remove(i);
            removed = true;
        }
        findBest((pos + b.number) % hours);
        if (removed)
            coins.add(i, b);
        b.numbers.add(current.removeLast());
    }
    occupied[pos] = false;
}

Output for the given example: 10 10 5 1 1 1 5 10 10 1 5 5

---

Here is a slightly more optimized version in JavaScript where the list is implemented manually, so that you can really see why removing and adding the currend bucket is O(1). Because the list is always read in order it is superior to the array in this case. Whith an array you need to shift many elements or skip a lot of empty ones, depending how you implement it, not with a list of buckets. Should be a little easier to understand than the Java code.

var head, occupied, current, best, h, limit;

document.body.innerHTML = solve([1,1,1,1,5,5,5,5,10,10,10,10], 12);

function solve(coins, hours) {
    h = hours;
    coins.sort(function(a, b) {
        let x = a % hours, y = b % hours;
        if (x > y)
            return -1;
        if (x < y)
            return 1;
        return 0;
    });
    let mod = coins[0] % hours;
    head = {num: mod, vals: [coins[0]], next: null};
    let b = head, coinCount = 1;
    for (let i = 1; i < coins.length && mod != 0; i++) {
        let m = coins[i] % hours;
        if (m == mod) {
            b.vals.push(coins[i]);
        } else {
            b.next = {num: m, vals: [coins[i]], next: null};
            b = b.next;
            mod = m;
        }
        coinCount++;
    }
    limit = coinCount < hours ? coinCount : hours;
    occupied = [];
    for (let i = 0; i < hours; i++)
        occupied.push(false);
    best = [];
    current = [];
    solveRec(0);
    return JSON.stringify(best);
}

function solveRec(pos) {
    occupied[pos] = true;
    let b = head, prev = null;
    while (b !== null) {
        let m = (pos + b.num) % h;
        if (!occupied[m]) {
            current.push(b.vals.pop());
            let rem = false;
            if (b.vals.length == 0) {
                if (prev == null)
                    head = b.next;
                else
                    prev.next = b.next;
                rem = true;
            }
            solveRec(m);
            if (current.length > best.length)
                best = current.slice();
            if (best.length == limit)
                return;
            if (rem) {
                if (prev == null)
                    head = b;
                else
                    prev.next = b;
            }
            b.vals.push(current.pop());
        } else if (current.length + 1 > best.length) {
            best = current.slice();
            best.push(b.vals[b.vals.length - 1]);
        }
        prev = b;
        b = b.next;
    }
    occupied[pos] = false;
}