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

• Wyverex (4/4) Aug 11 2008 The Abbott's Puzzle
• BCS (2/8) Aug 11 2008 = <17,5,78> + i*<-3,5,-2> for i in [0,5]
• Steven Schveighoffer (6/14) Aug 11 2008 You missed <20, 0, 80>
• BCS (18/41) Aug 11 2008 D can't do the closed form solution (and I can't remember how so I used ...
• Koroskin Denis (78/97) Aug 11 2008 In D you asked? Here you are: (read from bottom to top)
• bearophile (5/6) Aug 11 2008 But some functions run at compile time too!
• bearophile (61/61) Aug 11 2008 Koroskin Denis, I have modified your code a little trying to use compile...
• bearophile (4/5) Aug 11 2008 Anyway, even using those few small CT functions the compile time decreas...
• Koroskin Denis (78/87) Aug 11 2008 n, =
• bearophile (8/15) Aug 11 2008 Now the compile time is around 0.06 s, way less.
• Koroskin Denis (7/30) Aug 12 2008 Yes, I think it can be asked as an enhancement. As a result this functio...
• bearophile (6/7) Aug 12 2008 I think there can be ways to reduce such complexity (and add a compile-t...
• Koroskin Denis (8/25) Aug 12 2008 Nice idea. IIRC, Walter isn't going to replace its own backend to (or ev...
• Christopher Wright (8/40) Aug 12 2008 There are other issues. If Walter only ever looks at his own code, he's
• Wyverex (22/27) Aug 11 2008 T min( T ) (T a, T b) { return (a
• Steven Schveighoffer (23/23) Aug 11 2008 import tango.io.Stdout;
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
```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
"Steven Schveighoffer" <schveiguy yahoo.com> writes:
```"BCS" 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?"

<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
```Reply to Steven,

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

<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]);
}
```
Aug 11 2008
"Koroskin Denis" <2korden gmail.com> writes:
```On Mon, 11 Aug 2008 21:25:46 +0400, Steven Schveighoffer
<schveiguy yahoo.com> wrote:

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

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