C Coin Combo

coin_combo.c

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEBUG 0
#define IMPOSSIBLE (INT_MAX >> 1)

int main(int argc, char **argv) {
    int num_coins, amount;
    int *coins;
    int *m;

    if (argc < 2) {
        fprintf(stderr, "Usage: %s NUM_COINS [COINS ...]\n", argv[0]);
        return 1;
    }

    amount = atoi(argv[1]);

    num_coins = argc - 2;
    coins = malloc(num_coins * sizeof(int));
    for (int i = 0; i < num_coins; i++) {
        coins[i] = atoi(argv[i + 2]);
    }

    m = calloc((num_coins + 1) * (amount + 1), sizeof(int));
    for (int j = 1; j < amount + 1; j++) {
        m[j * (num_coins + 1)] = IMPOSSIBLE;
    }

    for (int i = 1; i < num_coins + 1; i++) {
        int coin = coins[i - 1];
        for (int r = 1; r < amount + 1; r++) {
            if (coin == r) {
                m[r * (num_coins + 1) + i] = 1;
            } else if (coin > r) {
                m[r * (num_coins + 1) + i] = m[r * (num_coins + 1) + i - 1];
            } else {
                int solution_a = m[r * (num_coins + 1) + i - 1];
                int solution_b = 1 + m[(r - coin) * (num_coins + 1) + i];
                if (solution_a < solution_b) {
                    m[r * (num_coins + 1) + i] = solution_a;
                } else {
                    m[r * (num_coins + 1) + i] = solution_b;
                }
            }
        }
    }

    if (DEBUG) {
        for (int i = 1; i < num_coins + 1; i++) {
            for (int j = 0; j < amount + 1; j++) {
                if (m[j * (num_coins + 1) + i] == IMPOSSIBLE) {
                    printf("---- ");
                } else {
                    printf("%4d ", m[j * (num_coins + 1) + i]);
                }
            }
            printf("\n");
        }
    }

    int i = num_coins;
    int j = amount;
    char output[256] = "";
    char *cur = output, *const end = output + sizeof(output);

    while (j != 0) {
        int coin = coins[i - 1];
        if (j >= coin && m[(j - coin) * (num_coins + 1) + i] == m[j * (num_coins + 1) + i] - 1) {
            if (j == coin) {
                printf("%s%d\n", output, coin);
            } else {
                cur += snprintf(cur, end - cur, "%d, ", coin);
            }
            j -= coin;
        } else if (i > 0) {
            i--;
        } else {
            break;
        }
    }

    free(m);
    free(coins);

    return 0;
}

coin_combo.f90

PROGRAM coin_combo
    IMPLICIT NONE
    CHARACTER(len=10) :: arg
    INTEGER :: i, j, num_coins, amount, coin, r
    INTEGER, DIMENSION (:), ALLOCATABLE :: coins
    INTEGER, DIMENSION (:,:), ALLOCATABLE :: m

    num_coins = command_argument_count() - 1
    ALLOCATE (coins(num_coins))

    CALL get_command_argument(1, arg)
    READ (arg, '(I10)') amount

    ALLOCATE (m(num_coins + 1, amount + 1))
    m(:,:) = 0
    m(1, 2:) = 999

    DO i = 2, num_coins + 1
        CALL get_command_argument(i, arg)
        READ (arg, '(I10)') coins(i - 1)
    END DO

    DO i = 2, num_coins + 1
        coin = coins(i - 1)
        DO j = 2, amount + 1
            r = j - 1
            IF (coin == r) THEN
                m(i, j) = 1
            ELSE IF (coin > r) THEN
                m(i, j) = m(i - 1, j)
            ELSE
                m(i, j) = MIN(m(i - 1, j), 1 + m(i, j - coin))
            END IF
        END DO
    END DO

    i = num_coins + 1
    r = amount

    DO WHILE (r /= 0)
        coin = coins(i - 1)
        j = r + 1
        IF (r >= coin .AND. m(i, j - coin) == m(i, j) - 1) THEN
            IF (r == coin) THEN
                WRITE (*, '(i3)') coin
            ELSE
                WRITE (*, '(i3)', advance='no') coin
            END IF
            r = r - coin
        ELSE IF (i > 2) THEN
            i = i - 1
        ELSE
            EXIT
        END IF
    END DO

    DEALLOCATE(coins)
    DEALLOCATE(m)
END PROGRAM coin_combo