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

/* Copyright (C) 1992,2000 Bisqwit (http://iki.fi/bisqwit/)
 * No warranty. You are free to modify this source, and to
 * distribute modified sources, as long as you keep the
 * existing copyright messages intact and as long as you
 * remember to add your own copyright markings.
 */

static struct {int m,h; const char *n;} kerroin[] =
{
    /* an optimal count to give before next currency matter,
     * value per one,
     * name
     */

    {1,50000, "mithril"},
    {5,10000, "batium"},
    {2,5000, "anipium"},
    {5,1000, "platinum"},
    {10,100, "gold"},
    {5,60, "silver"},
    {3,40, "bronze"},
    {5,20, "copper"},
    {10,10, "tin"},
    {2,5, "zinc"},
    {10,1, "mowgles"}
};

#define ainemaara ((sizeof kerroin) / (sizeof kerroin[0]))

static void InvNow(const char *hdr, int *aine)
{
    int a, c=0;
    printf("*** %s: ", hdr);
    for(a=0; a<(int)ainemaara; ++a)
        if(aine[a])
        {
            printf("%d %s, ", aine[a], kerroin[a].n);
            c += kerroin[a].h * aine[a];
        }
    printf("that is %d.%02d...\n", c/100, c%100);
}

static int debug=1;

/* The brute force -routine */
/* Chooses often the best choice in less than ten loops... */
static int Calcul(int *aine, int *sums, int start, int hinta)
{
    int a;
    for(a=start; a<(int)ainemaara; ++a)
    {
        int f = kerroin[a].h, arvo = aine[a] * f, max, e, c;
        if(arvo > hinta)arvo = hinta;
        max = arvo / kerroin[a].h;
        if(!max)
        {
            sums[a] = 0;
            continue;
        }
/*      printf("Testing %s(have %d -> %d) for %d.%02d...\n",
            kerroin[a].n, aine[a], max, hinta/100, hinta%100);
*/      for(c=max, e=c*f; c>0; --c, e-=f)
        {
            if(e == hinta)
            {
                sums[a] = c;
                while(++a < (int)ainemaara)sums[a] = 0;
                return 1;
            }
            if(Calcul(aine, sums, a+1, hinta-e))
            {
                sums[a] = c;
                return 1;
            }
        }
/*      printf("blah\n");
*/      break;
    }
    return 0;
}

static void maksa(const char *nick, unsigned pay, int *aine, int Isot1)
{
    int kayt[ainemaara];
    int a, b=0, hinta=pay;

    for(a=0; a<(int)ainemaara; ++a)kayt[a] = 0;

/*  This is not a good idea to put yet here. Would make this too slow.
    Let's do some simple fixing first.

    if(!Calcul(aine, kayt, 0, hinta))goto diu;
*/
    if(debug)InvNow("Inv at start", aine);

    for(a=Isot1?0:ainemaara; Isot1?a<(int)ainemaara:a>0; Isot1?++a:0)
    {
        unsigned e;
        if(!Isot1)--a;
        for(e=0; aine[a] && kerroin[a].h <= hinta; ++e)
        {
            --aine[a];
            ++kayt[a];
            hinta -= kerroin[a].h;
            b += kerroin[a].h;
        }
        if(e && debug)
        {
            printf("*** first: gave %u %s... so I've %d.%02d left to pay.\n",
                e, kerroin[a].n, hinta/100, hinta%100);
        }
    }

    for(; hinta != 0; )
    {
        int kulu[ainemaara];
        const char *gave = "";

        if(debug)
        {
            InvNow("Inv now", aine);
            InvNow("Have gave", kayt);
        }
        for(a=ainemaara; --a>=0; )
        {
            if(aine[a])break;
            if(!a && hinta>0)
            {
                printf("say [batmoney] I don't have enough money to pay with.\n");
                return;
            }
        uusi:;
        }
        if(a >= 0)
        {
            int maara = kerroin[a].m, arvo;
            if(maara > aine[a])maara = aine[a];
            aine[a] -= maara;
            kayt[a] += maara;
            arvo = kerroin[a].h * maara;
            hinta -= arvo;
            b += arvo;
            if(debug)
                printf("*** exchange: gave %d %s%s (%d.%02d), now I want %d.%02d back...\n",
                    maara, kerroin[a].n, gave,
                    arvo/100, arvo%100,
                    (-hinta)/100, (-hinta)%100);
        }
        if(!Calcul(kayt, kulu, 0, -hinta))
        {
            if(a>0)
            {
                gave = " more";
                goto uusi;
            }
            if(debug)
                printf("*** exchange: didn't help... getting cash back.\n");
            break;
        }

        for(a=0; a < (int)ainemaara; ++a)
        {
            int c = kulu[a]*kerroin[a].h;
            if(kulu[a])
            {
                if(debug)
                    printf("*** exchange: took back %u %s (%d.%02d)...\n",
                        kulu[a], kerroin[a].n,
                        c/100, c%100);
                kayt[a] -= kulu[a];
                aine[a] += kulu[a];
                hinta += c;
                b -= c;
            }
        }
    }

    for(a=0; a < (int)ainemaara; ++a)
    {
        unsigned e;
        for(e=0; kayt[a] && kerroin[a].h <= -hinta; ++e)
        {
            ++aine[a];
            --kayt[a];
            hinta += kerroin[a].h;
            b -= kerroin[a].h;
        }
        if(e && debug)
            printf("*** last: took %u %s... I still need to reget %d.%02d.\n",
                e, kerroin[a].n,
                (-hinta)/100, (-hinta)%100);
    }
/*
diu:*/
    if(debug)
    {
        printf("-----------\n");

        InvNow("Inv now", aine);
        InvNow("Have gave", kayt);

        printf("-----------\n");
    }

    for(a=0; a<(int)ainemaara; ++a)
        if(kayt[a])
        {
            if(nick)
                printf("give %d %s to %s\n", kayt[a], kerroin[a].n, nick);
            else
                printf("drop %d %s\n", kayt[a], kerroin[a].n);
        }

    printf("say [batmoney] %s worth of %d.%02d.\n", nick?"Paid":"Dropped", b/100, b%100);

    if(hinta < 0)
    {
        hinta = -hinta;
        printf("say [batmoney] I ran out of small coins, I want %d.%02d back.\n", hinta/100, hinta%100);
    }

    if(debug)
        printf("-----------\n");
}

static void ParseInventory(char *inv, int *aine)
{
    int a, b=ainemaara, l=0;
    for(a=0; a<b; ++a)aine[a]=0;
    while(*inv && *inv!=')')
    {
        int n = strtol(inv, &inv, 10);
        while(*inv==' ')++inv;
        for(a=0; a<b; ++a)
        {
            l = strlen(kerroin[a].n);
            if(!strncmp(inv, kerroin[a].n, l))break;
        }
        if(a==b)
        {
            printf("say [batmoney] Money inventory parse error at '%s'\n", inv);
            exit(-1);
        }
        aine[a] = n;
        inv += l;
        if(*inv == ',')++inv;
        if(!strncmp(inv, " and", 4))inv += 4;
        while(*inv==' ')++inv;
    }
}

int main(int argc, const char *const *argv)
{
    char Buf[512];
    char Money[2048];

    int aine[ainemaara];

    const char *nick = NULL;
    int amount = -1;
    int isot = 0;
    int a;

    while(--argc)
    {
        const char *s = *++argv;

        if(*s=='-')
        {
            while(*++s)
            {
                switch(*s)
                {
                    case 'd':
                        debug=1;
                        break;
                    case 'q':
                        debug=0;
                        break;
                    case 'b':
                        isot=1;
                        break;
                    default:
                    usage:
                        printf(
                            "Pay calculator for the unique BatMUD's monetary system.\n\n"
                            "Usage: pay [-q] [-d] [-b] [<nick>] <amount>\n"
                            "    -d  Debug info (for algorithm investigators) (default)\n"
                            "    -q  Disables -d (makes quiet)\n"
                            "    -b  Pay using biggest coins ""(default: smallest coins)\n"
                            "Example: pay bisqwit 10000\n"
                            "\n"
                            "Copyright (C) 1992,2000 Bisqwit (http://iki.fi/bisqwit/)\n"
                        );
                        return 0;
                }
            }
        }
        else if(!nick)
            nick = s;
        else
        {
            if(amount >= 0)
                goto usage;
            amount = strtod(s, (char **)&s) * 100 + 0.5;
            if(*s || amount < 0)goto usage;
        }
    }
    if(amount == -1 && nick)
    {
        const char *s;
        amount = strtod(nick, (char **)&s) * 100 + 0.5;
        if(*s)goto usage;
        nick = NULL;
    }
    if(amount < 0)goto usage;

    if(debug)
        printf("*** Now paste your inventory here (the lines saying what coins do you have):\n");

    for(a=0; fgets(Buf,511,stdin); )
    {
        char *s;
        strtok(Buf, "\n");
        strtok(Buf, "\r");
         /* so that this source can be used as input */
        if(!a && strstr(Buf, "coi""ns ("))
        {
            a=1;
            strcpy(Money, strchr(Buf, '(')+1);
        }
        if(a)
        {
            s = strchr(Buf, ')');
            if(s)a += 2;
            if(a==1)
                a=2;
            else
            {
                if(a==2 || a==4)strcat(Money, Buf);
                if(a >= 3)
                {
                    if(debug)
                        printf("*** Thank you\n");
                    a=0;
                    break;
                }
            }
        }
    }
    if(a)
        printf("say [batmoney] Unexpected end of input.\n");

    ParseInventory(Money, aine);

    maksa(nick, amount, aine, isot);

    return 0;
}

/*

You are carrying 20.9 kg of equipment:
20917 coins (93 mithril, 40 batium, 16 anipium, 13 platinum, 16187 gold, 386
 silver, 378 bronze, 64 copper, 511 tin, 1123 zinc and 2106 mowgles) [Cash:
 68140  Bank: 1  Total: 68141]
No items.

From: Bisqwit
Subject: A product of creativity
Date: Sun Mar 26 11:13:15 2000 (postedited)
Reply-Code: 24le
Lines: 17
Like if I had nothing better to do, I coded a bit.

http://iki.fi/bisqwit/src/batmoney.c is the sourcecode
of a program, which you can use to calculate money sums
in BatMUD. Complete description is found at
http://iki.fi/bisqwit/notes.shtml?algomoney .

Shortly:
If you want to pay a sum of cash and you have a various
collection of coins, you can use this program to calculate
what coins do you give. It creates a list of commands for
giving the coins away. You can either give the smallest
coins or the biggest coins you have.

It even handles the cases when you don't have enough money
(no it does not go to bank), or you have no suitable coins.

*/