#include <stdio.h>

const char *FILL_STR  = "- Fill the %d gallon jug\n";
const char *EMPTY_STR = "- Empty the %d gallon jug\n";
const char *TRANS_STR = "- Transfer from the %d gallon jug to the"
                         " %d gallon jug\n";
struct Jug {
    int capacity;
    int volume;
    Jug(int c, int v=0) : capacity(c), volume(v) {}
};

int solveSteps(int, int, int, bool=false);
void solve_visual(int, int, int, bool=false);

int main()
{
    int a = 3;
    int b = 5;
    int x = 4;
    bool empty = true;

    if (solveSteps(a,b,x,empty) < solveSteps(b,a,x,empty))
        solve_visual(a,b,x,empty);
    else
        solve_visual(b,a,x,empty);

    getchar();
    return 0;
}

void operator>>(Jug& lhs, Jug& rhs)
{
    int freeVolume = rhs.capacity - rhs.volume;
    if (lhs.volume > freeVolume)
    {
        lhs.volume -= freeVolume;
        rhs.volume = rhs.capacity;
    }
    else
    {
        rhs.volume += lhs.volume;
        lhs.volume = 0;
    }
}

int solveSteps(int a, int b, int x, bool empty)
{
    Jug jugA(a), jugB(b), jugC(a+b, a+b);
    int count = 0;
    while (jugA.volume != x && jugB.volume != x)
    {
        if (!jugA.volume)
            jugC >> jugA;
        else if (jugB.volume == jugB.capacity)
            jugB >> jugC;
        else
            jugA >> jugB;
        ++count;
    }
    if (empty && jugA.volume && jugB.volume)
        ++count;
    return count;
}

void printColumns(Jug a, Jug b)
{
    int maxHeight = a.capacity > b.capacity ? a.capacity : b.capacity;
    for (int i = maxHeight+1; i > 0; --i)
    {
        printf("    ");
        if (a.volume == i)
        {
            printf("*");
            --a.volume;
        }
        else
            printf(" ");
        printf("              ");
        if (b.volume == i)
        {
            printf("*");
            --b.volume;
        }
        printf("\n");
    }
    printf("%d gal. jug     %d gal. jug\n\n\n", a.capacity, b.capacity);
}

void solve_visual(int a, int b, int x, bool empty)
{
    Jug jugA(a), jugB(b), jugC(a+b, a+b);
    while (jugA.volume != x && jugB.volume != x)
    {
        if (!jugA.volume)
        {
            printf(FILL_STR, a);
            jugC >> jugA;
        }
        else if (jugB.volume == jugB.capacity)
        { 
            printf(EMPTY_STR, b);
            jugB >> jugC;
        }
        else
        { 
            printf(TRANS_STR, a, b, jugA.volume, a, jugB.volume, b);
            jugA >> jugB;
        }
        printColumns(jugA, jugB);
    }
    if (empty && jugA.volume && jugB.volume)
    {
        if (jugA.volume != x)
        {
            printf(EMPTY_STR, a);
            jugA >> jugC;
        }
        else
        {
            printf(EMPTY_STR, b);
            jugB >> jugC;
        }
        printColumns(jugA, jugB);
    }
    printf("Done!\n");
}

- Fill the 5 gallon jug
                   
    *              
    *              
    *              
    *              
    *              
5 gal. jug     3 gal. jug


- Transfer from the 5 gallon jug to the 3 gallon jug
                   
                   
                   
                   *
    *              *
    *              *
5 gal. jug     3 gal. jug


- Empty the 3 gallon jug
                   
                   
                   
                   
    *              
    *              
5 gal. jug     3 gal. jug


- Transfer from the 5 gallon jug to the 3 gallon jug
                   
                   
                   
                   
                   *
                   *
5 gal. jug     3 gal. jug


- Fill the 5 gallon jug
                   
    *              
    *              
    *              
    *              *
    *              *
5 gal. jug     3 gal. jug


- Transfer from the 5 gallon jug to the 3 gallon jug
                   
                   
    *              
    *              *
    *              *
    *              *
5 gal. jug     3 gal. jug


- Empty the 3 gallon jug
                   
                   
    *              
    *              
    *              
    *              
5 gal. jug     3 gal. jug


Done!