The Abbott's Puzzle

"If 100 bushels of corn were distributed among 100 people in such a manner that each man received three bushels, each woman two, and each child half a bushel, how many men, women, and children were there?"

Reply to wyverex,

> The Abbott's Puzzle
> 
> "If 100 bushels of corn were distributed among 100 people in such a
> manner that each man received three bushels, each woman two, and each
> child half a bushel, how many men, women, and children were there?"
> 

<M, W, C> = <17,5,78> + i*<-3,5,-2>  for i in [0,5]

Wyverex wrote:
> The Abbott's Puzzle
> 
> "If 100 bushels of corn were distributed among 100 people in such a manner that each man received three bushels, each woman two, and each child half a bushel, how many men, women, and children were there?"


T min( T ) (T a, T b) { return (a<b?a:b); }

void main()
{
  int c,w,m;
  for(c = 0; c <= 100; c+=2)
  {
    for(w = 0; w <= min(50, 100-c); w++)
    {
       m = 100 - (c+w);
       if( ((c/2) + (w*2) + (m*3)) == 100 )
         printf("Men:%d Women:%d Children:%d\n", m, w, c);
    }
  }
}


Men:2 Women:30 Children:68
Men:5 Women:25 Children:70
Men:8 Women:20 Children:72
Men:11 Women:15 Children:74
Men:14 Women:10 Children:76
Men:17 Women:5 Children:78
Men:20 Women:0 Children:80

import tango.io.Stdout;

void main()
{
    for(int m = 0; m * 3 <= 100; m++)
        for(int c = 0; c + m <= 100; c+=2)
        {
            int w = 100 - m - c;
            int b = m * 3 + c / 2 + w * 2;
            if(b < 100)
                break;
            if(b == 100)
                Stdout.formatln("men = {}, women = {}, children = {}", m, w,
c);
        }
}


men = 2, women = 30, children = 68
men = 5, women = 25, children = 70
men = 8, women = 20, children = 72
men = 11, women = 15, children = 74
men = 14, women = 10, children = 76
men = 17, women = 5, children = 78
men = 20, women = 0, children = 80

-Steve

"BCS" wrote
> Reply to wyverex,
>
>> The Abbott's Puzzle
>>
>> "If 100 bushels of corn were distributed among 100 people in such a manner that each man received three bushels, each woman two, and each child half a bushel, how many men, women, and children were there?"
>>
>
> <M, W, C> = <17,5,78> + i*<-3,5,-2>  for i in [0,5]
>
>

You missed <20, 0, 80>

Of course, this assumes that it's possible to have 0 women (unlikely :) )

And what's with the non-D code?  It should be a requirement that you have to solve it with D ;)

-Steve

Reply to Steven,

> "BCS" wrote
> 
>> Reply to wyverex,
>> 
>>> The Abbott's Puzzle
>>> 
>>> "If 100 bushels of corn were distributed among 100 people in such a
>>> manner that each man received three bushels, each woman two, and
>>> each child half a bushel, how many men, women, and children were
>>> there?"
>>> 
>> <M, W, C> = <17,5,78> + i*<-3,5,-2>  for i in [0,5]
>> 
> You missed <20, 0, 80>
> 
> Of course, this assumes that it's possible to have 0 women (unlikely
> :) )
> 
> And what's with the non-D code?  It should be a requirement that you
> have to solve it with D ;)
> 
> -Steve
> 

D can't do the closed form solution (and I can't remember how so I used excel)

how about a D vector solution (untested as I'm still running 1.033)

void main()
{
    short[101] ramp;
    foreach(i,ref j;ramp)j=i;

    short[101][101] grain;
    short[101][101] c;

    foreach(short m, ref short[101] row; grain)
        row[] = m*6 - 200 + ramp[]*4 + (100-m-ramp[])*1;

    foreach(short m, ref short[101] row; c)
        row[] = 100-m-ramp[];

    for(int m = 0; m <= 100; m++)
       for(int w = 0; w <= 100; w++)
           if(c[m][w] >= 0 && grain[m][w] == 0)
                writef("M=%d  W=%d  C=%d\n",m,w,c[m][w]);
}

On Mon, 11 Aug 2008 21:25:46 +0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> "BCS" wrote
>> Reply to wyverex,
>>
>>> The Abbott's Puzzle
>>>
>>> "If 100 bushels of corn were distributed among 100 people in such a
>>> manner that each man received three bushels, each woman two, and each
>>> child half a bushel, how many men, women, and children were there?"
>>>
>>
>> <M, W, C> = <17,5,78> + i*<-3,5,-2>  for i in [0,5]
>>
>>
>
> You missed <20, 0, 80>
>
> Of course, this assumes that it's possible to have 0 women (unlikely :) )
>
> And what's with the non-D code?  It should be a requirement that you have to
> solve it with D ;)
>
> -Steve
>
>

In D you asked? Here you are: (read from bottom to top)

template doCheckMen(int men)
{
    const int doCheckMen = CheckWomen!(men, 0, 100-men);
}

template numChildren(int men, int women)
{
    const int numChildren = 100 - men - women;
}

template isEven(int number)
{
    const bool isEven = (number & 1) == 0;
}

template getValue(int men, int women, int children)
{
    const int getValue = 3 * men + 2 * women + children / 2;
}

template checkSolution(int men, int women, int children)
{
    static if ( isEven!(children) && getValue!(men,women,children) == 100) {
        pragma(msg, "Solution found: " ~ itoa!(men) ~ " " ~ itoa!(women) ~ " " ~ itoa!(children));
        const int checkSolution = 1;
    } else {
        const int checkSolution = 0;
    }
}

template isOverflow(int men, int women = 0)
{
    const int isOverflow = getValue!(men, women, 0) > 100;
}

template doCheckWomen(int men, int women)
{
    const int doCheckWomen = checkSolution!(men, women, numChildren!(men, women));
}

template CheckWomen(int men, int first, int last)
{
    static if (first == last) {
        const int CheckWomen = doCheckWomen!(men, first);
    } else static if (first < last) {
        // an optimization
        static if (isOverflow!(men, first)) {
            const int CheckWomen = 0;
        } else {
            const int CheckWomen = CheckWomen!(men, first, first) + CheckWomen!(men, first+1, last);
        }
    } else {
        static assert(false);
    }
}

template CheckMen(int first, int last) {
    static if (first == last) {
        const int CheckMen = doCheckMen!(first);
    } else static if (first < last) {
        // an optimization
        static if (isOverflow!(first)) {
            const int CheckMen = 0;
        } else {
            const int CheckMen = CheckMen!(first, first) + CheckMen!(first+1, last);
        }
    } else {
        static assert(false);
    }
}

int solve() {
    return CheckMen!(0, 100);
}

void main()
{
    const int numSolutios = solve();
    pragma(msg, "Number of solutions: " ~ itoa!(numSolutios));
}

Koroskin Denis:
> In D you asked? Here you are: (read from bottom to top)

But some functions run at compile time too!

Thank you for reminding me why CLisp macros aren't that bad ;-)

Bye,
bearophile

Koroskin Denis, I have modified your code a little trying to use compile time functions.

But I don't understand why for example getValue() can be a CT function, while DoCheckMen() can't.

/*
The Abbott's Puzzle:

"If 100 bushels of corn were distributed among 100 people in such a manner that each man received three bushels, each woman two, and each child half a bushel, how many men, women, and children were there?" */

import std.metastrings: Format;

int numChildren(int men, int women) {
    return 100 - men - women;
}

bool isEven(int number) {
    return !(number & 1);
}

int getValue(int men, int women, int children) {
    return 3 * men + 2 * women + children / 2;
}

bool isOverflow(int men, int women = 0) {
    return getValue(men, women, 0) > 100;
}

template DoCheckMen(int men) {
    const DoCheckMen = CheckWomen!(men, 0, 100 - men);
}

template CheckSolution(int men, int women, int children) {
    static if (isEven(children) && getValue(men,women,children) == 100) {
        pragma(msg, Format!("Solution found: %s %s %s", men, women, children));
        const CheckSolution = 1;
    } else
        const CheckSolution = 0;
}

template DoCheckWomen(int men, int women) {
    const DoCheckWomen = CheckSolution!(men, women, numChildren(men, women));
}

template CheckWomen(int men, int first, int last) {
    static if (first == last) {
        const CheckWomen = DoCheckWomen!(men, first);
    } else static if (first < last) {
        // an optimization
        static if (isOverflow(men, first))
           const CheckWomen = 0;
        else
           const CheckWomen = CheckWomen!(men, first, first) + CheckWomen!(men, first+1, last);
    } else
        static assert(false);
}

template CheckMen(int first, int last) {
    static if (first == last) {
        const CheckMen = DoCheckMen!(first);
    } else static if (first < last) {
        // an optimization
        static if (isOverflow(first))
            const CheckMen = 0;
        else
            const CheckMen = CheckMen!(first, first) + CheckMen!(first+1, last);
    } else
        static assert(false);
}

const int numSolutios = CheckMen!(0, 100);

pragma(msg, Format!("Number of solutions: %s\n", numSolutios));

//void main() {}

bearophile:
> But I don't understand why for example getValue() can be a CT function, while DoCheckMen() can't.

Anyway, even using those few small CT functions the compile time decreases from 1.81 s to about 0.91 s on my PC, and the memory used from about 42 MB to 32 MB, I don't know why.

Bye,
bearophile