Skip to content

Instantly share code, notes, and snippets.

@zoeisnowooze
Last active Jun 7, 2022
Embed
What would you like to do?
C Coin Combo
#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;
}
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment