www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Puzzle 8-10-08

reply 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?"
Aug 11 2008
next sibling parent reply 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]
Aug 11 2008
parent reply "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
Aug 11 2008
next sibling parent 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?"
 


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]); }
Aug 11 2008
prev sibling parent reply 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
Aug 11 2008
parent reply 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() {}
Aug 11 2008
parent reply 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
Aug 11 2008
parent reply "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=


 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=

 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);
Aug 11 2008
parent reply 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
Aug 11 2008
parent reply "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

Aug 12 2008
parent reply 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
Aug 12 2008
parent 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.
Aug 12 2008
prev sibling next sibling parent 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
Aug 11 2008
prev sibling next sibling parent "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 
Aug 11 2008
prev sibling next sibling parent "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)); }
Aug 11 2008
prev sibling parent "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).
Aug 12 2008