Wyverex <wyverex.cypher gmail.com> writes:

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?"

BCS <ao pathlink.com> writes:

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]

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

"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 

BCS <ao pathlink.com> writes:

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]);
}

"Koroskin Denis" <2korden gmail.com> writes:

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));
}

bearophile <bearophileHUGS lycos.com> writes:

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

bearophile <bearophileHUGS lycos.com> writes:

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 <bearophileHUGS lycos.com> writes:

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

"Koroskin Denis" <2korden gmail.com> writes:

On Tue, 12 Aug 2008 04:23:55 +0400, bearophile <bearophileHUGS lycos.com=
  =

wrote:

 bearophile:
 But I don't understand why for example getValue() can be a CT functio=


n,  =

 while DoCheckMen() can't.


because the following code is wrong due to mixing of compile time and  =

run-time constants:

template square(int a)
{
    const int foo =3D a * a;
}

int getSquare(int a)
{
     return square!(a); // you can't instantiate a template
     // with a variable (unless it is an alias, which is not a case)
}

 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 fr=

om  =

 about 42 MB to 32 MB, I don't know why.

 Bye,
 bearophile

That's because compiler doesn't have to instantiate all those hundreds o=
f  =

templates (and hold them in memory until exit).

I took a step forward and eliminated all the templates. Note that now th=
e  =

result is returned as a string due to a lack of compile time text output=
  =

(it will be output once per template/fuction instance).

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 =3D 0) {
     return getValue(men, women, 0) > 100;
}

char[] DoCheckMen(int men) {
     return CheckWomen(men, 0, 100 - men);
}

char[] itoa(int i)
{
     if (i < 10) {
         return "0123456789"[i..i+1];
     } else {
         return itoa(i / 10) ~ itoa(i % 10);
     }
}

char[] CheckSolution(int men, int women, int children) {
     if (isEven(children) && getValue(men,women,children) =3D=3D 100) {
         return  =

"Men:\t"~itoa(men)~"\tWomen:\t"~itoa(women)~"\tChildren:\t"~itoa(childre=
n)~"\n";
     } else {
         return "";
     }
}

char[] DoCheckWomen(int men, int women) {
     return CheckSolution(men, women, numChildren(men, women));
}

char[] CheckWomen(int men, int first, int last) {
     if (first =3D=3D last) {
         return DoCheckWomen(men, first);
     }

     if (isOverflow(men, first)) {
         return "";
     }

     return DoCheckWomen(men, first) ~ CheckWomen(men, first+1, last);
}

char[] CheckMen(int first, int last) {
     if (first =3D=3D last) {
         return DoCheckMen(first);
     }
     if (isOverflow(first)) {
         return "";
     }

     return DoCheckMen(first) ~ CheckMen(first+1, last);
}

const char[] solutios =3D CheckMen(0, 100);
pragma(msg, solutios);

bearophile <bearophileHUGS lycos.com> writes:

Koroskin Denis:
      return square!(a); // you can't instantiate a template
      // with a variable (unless it is an alias, which is not a case)

Uhm... I think there can be ways to modify DMD to allow a better mixing of CT
functions and templates.


 That's because compiler doesn't have to instantiate all those hundreds of  
 templates (and hold them in memory until exit).

Now the compile time is around 0.06 s, way less.
Such difference is very interesting. A functional language (even an interpreted
one) can probably execute the code relative to those templates in way less than
the original 1.8 seconds (it amounts to almost 4 billion clock ticks, it's a
lot of computations!).
I presume DMD somehow contains an almost complete interpreter of D language
(with GC) plus a functional language interpreter for the templates that can
probably be improved, plus the compiler itself, it sounds like a lot of
complexity/stuff :-)


 Note that now the  
 result is returned as a string due to a lack of compile time text output  
 (it will be output once per template/fuction instance).

Good idea, I'll remember it.

Bye,
bearophile

"Koroskin Denis" <2korden gmail.com> writes:

On Tue, 12 Aug 2008 05:15:09 +0400, bearophile <bearophileHUGS lycos.com>  
wrote:

 Koroskin Denis:
      return square!(a); // you can't instantiate a template
      // with a variable (unless it is an alias, which is not a case)

 Uhm... I think there can be ways to modify DMD to allow a better mixing  
 of CT functions and templates.

Yes, I think it can be asked as an enhancement. As a result this function  
becomes Compile-Time evalualable only, so it will yield "Can not evaluate  
at run-time" if used with non-constant parameters. I like that bridge  
between functions and templates and it would reduce code complexity.

 That's because compiler doesn't have to instantiate all those hundreds  
 of
 templates (and hold them in memory until exit).

 Now the compile time is around 0.06 s, way less.
 Such difference is very interesting. A functional language (even an  
 interpreted one) can probably execute the code relative to those  
 templates in way less than the original 1.8 seconds (it amounts to  
 almost 4 billion clock ticks, it's a lot of computations!).
 I presume DMD somehow contains an almost complete interpreter of D  
 language (with GC) plus a functional language interpreter for the  
 templates that can probably be improved, plus the compiler itself, it  
 sounds like a lot of complexity/stuff :-)

Yes, it is. And Walter writes it on his own :(

 Note that now the
 result is returned as a string due to a lack of compile time text output
 (it will be output once per template/fuction instance).

 Good idea, I'll remember it.

 Bye,
 bearophile

bearophile <bearophileHUGS lycos.com> writes:

Koroskin Denis:
 Yes, it is. And Walter writes it on his own :(

I think there can be ways to reduce such complexity (and add a compile-time GC).

I think in a short time LLVM will become good enough as backend for D (what are
the practical problems left that make this adoption possible? In my benchmarks
(all the Shootout C benchmarks) LLMV isn't efficient as GCC yet, but it's
probably already more efficient than the backend of DMD so that's not a
problem, and it's open source), what I mean it can become the backend for the
official D compiler developed by Walter (and the D community). (side question:
can the front-end for LLMV be written in D? I hope so).

Does Walter oppose moving to develop with this back-end? I think it will lead
to solve some of the main current problems in the D development process (such
switch can be aligned to a switch to phobos+tango too).

Bye,
bearophile

"Koroskin Denis" <2korden gmail.com> writes:

On Tue, 12 Aug 2008 15:45:15 +0400, bearophile <bearophileHUGS lycos.com>  
wrote:

 Koroskin Denis:
 Yes, it is. And Walter writes it on his own :(

 I think there can be ways to reduce such complexity (and add a  
 compile-time GC).

 I think in a short time LLVM will become good enough as backend for D  
 (what are the practical problems left that make this adoption possible?  
 In my benchmarks (all the Shootout C benchmarks) LLMV isn't efficient as  
 GCC yet, but it's probably already more efficient than the backend of  
 DMD so that's not a problem, and it's open source), what I mean it can  
 become the backend for the official D compiler developed by Walter (and  
 the D community). (side question: can the front-end for LLMV be written  
 in D? I hope so).

 Does Walter oppose moving to develop with this back-end? I think it will  
 lead to solve some of the main current problems in the D development  
 process (such switch can be aligned to a switch to phobos+tango too).

 Bye,
 bearophile

Nice idea. IIRC, Walter isn't going to replace its own backend to (or even  
look at) GCC because of the GPL license. However, LLVM has a BSD-like  
license and that could be an option.

It still lacks some features, but it evolves *daily* unlike DMD backend.  
For example, chances are we won't ever get a native x86_64 codegen from DM  
backend, but we will get it with LLVM eventually (very soon, hopefully).

Christopher Wright <dhasenan gmail.com> writes:

Koroskin Denis wrote:
 On Tue, 12 Aug 2008 15:45:15 +0400, bearophile 
 <bearophileHUGS lycos.com> wrote:
 
 Koroskin Denis:
 Yes, it is. And Walter writes it on his own :(

 I think there can be ways to reduce such complexity (and add a 
 compile-time GC).

 I think in a short time LLVM will become good enough as backend for D 
 (what are the practical problems left that make this adoption 
 possible? In my benchmarks (all the Shootout C benchmarks) LLMV isn't 
 efficient as GCC yet, but it's probably already more efficient than 
 the backend of DMD so that's not a problem, and it's open source), 
 what I mean it can become the backend for the official D compiler 
 developed by Walter (and the D community). (side question: can the 
 front-end for LLMV be written in D? I hope so).

 Does Walter oppose moving to develop with this back-end? I think it 
 will lead to solve some of the main current problems in the D 
 development process (such switch can be aligned to a switch to 
 phobos+tango too).

 Bye,
 bearophile

 
 Nice idea. IIRC, Walter isn't going to replace its own backend to (or 
 even look at) GCC because of the GPL license. However, LLVM has a 
 BSD-like license and that could be an option.

There are other issues. If Walter only ever looks at his own code, he's 
safe from any infringement issues (at least reasonably so). Of course, 
just using the internal representation from LLVM, and its public APIs, 
won't have any real affect.

Also, moving dmd to llvm would kill dmc.

 It still lacks some features, but it evolves *daily* unlike DMD backend. 
 For example, chances are we won't ever get a native x86_64 codegen from 
 DM backend, but we will get it with LLVM eventually (very soon, hopefully).

I agree completely with this. I'd rather be using llvmdc right now, but 
I couldn't get it to work.

Wyverex <wyverex.cypher gmail.com> writes:

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

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

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