[Guest]

You are the mayor of the new city: Stimland City. Your main objective was to plan your city to reach its highest capacity for the population.

In Stimland there are 25 blocks, arranged typically in 5 rows and 5 columns. Each block fits for one building. You have four choices for the buildings that can be constructed in each block:

Type A

- Maximum capacity: 300.

- Conditions of construction: No conditions, can be built anywhere.

Type B

- Maximum capacity: 600.

- Conditions of construction: When built, it must be built next to a building of Type A.

Type C

- Maximum capacity: 900.

- Conditions of construction: When built, it must be built between a building of Type A and a building of Type B (in the middle).

Type D

- Maximum capacity: 1200.

- Conditions of construction: When built, it must be surrounded (diagonal surroundings excluded) by (at least): a building of Type A, a building of Type B and a building of Type C.

Any building can replace another, but the new one should fulfill its conditions of construction.

Give the number of buildings that can be built of each type, in order to have the maximum capacity in Stimland.

[Guest]

ADBAB

ACBAB

ADBAB

ACBAB

ADBAB

so i guess that'd be:

10 A's

10 B's

2 C's

3 D's

----------

i'm sure theres a more efficient way. took me a minute to come up with that.

[CaptainEd]

ADBAB

ACBAB

ADBAB

ACBAB

ADBAB

so i guess that'd be:

10 A's

10 B's

2 C's

3 D's

----------

i'm sure theres a more efficient way. took me a minute to come up with that.

Mine's not much better

BABAB

DCDCD

ABABA

DCDCD

BABAB

7A, 8B, 4C, 6D

2100+4800+3600+7200=17700

[Guest]

CaptainEd, I find myself agreeing with you a lot

Your solution is also the best one I found (and I didn't look until I had my sol'n)

This seems like an interesting problem for AI (good heuristics and constraints defined).

Cs and Ds cannot go in the corner based on constraints.

Cannot have more than 2 Ds continuous (need 3 sides to each D).

Cannot put 2 Ds continuous along the edge, because it leaves no room for Cs.

When I tried putting 2 Ds together, I got patterns that were more wasteful, but I haven't tried everything.

Edited March 17, 2009 by jb_riddler

[CaptainEd]

CaptainEd, I find myself agreeing with you a lot

Your solution is also the best one I found (and I didn't look until I had my sol'n)

This seems like an interesting problem for AI (good heuristics and constraints defined).

Cs and Ds cannot go in the corner based on constraints.

Cannot have more than 2 Ds continuous (need 3 sides to each D).

Cannot put 2 Ds continuous along the edge, because it leaves no room for Cs.

When I tried putting 2 Ds together, I got patterns that were more wasteful, but I haven't tried everything.

Well, JB, if this is the best you found, I feel better about it

[CaptainEd]

Well, JB, if this is the best you found, I feel better about it

Actually, I fear a hotfoot from HellFire: notice his words about "when built..." and "...can be replaced...". It's as if, we need to go further and gentrify this town. Each new building has to meet its construction requirements, even if the new configuration violates the requirements on legacy buildings. Sigh!

[CaptainEd]

Actually, I fear a hotfoot from HellFire: notice his words about "when built..." and "...can be replaced...". It's as if, we need to go further and gentrify this town. Each new building has to meet its construction requirements, even if the new configuration violates the requirements on legacy buildings. Sigh!

step 1: replace middle row with BAAAB

step 2: replace middle row with BDADB

That's an upgrade of 2 A's to 2 D's, increase of 1800 population, I think.

[CaptainEd]

step 1: replace middle row with BAAAB

step 2: replace middle row with BDADB

That's an upgrade of 2 A's to 2 D's, increase of 1800 population, I think.

History of Stimville City

Archaic period:

in the picture below,

1: build the As

2: build the Bs

3: build the Cs

4: build the Ds

resulting in

BABAB

DCDCD

ABABA

DCDCD

BABAB

Medieval period:

5: replace some As and Bs in top, middle, and bottom, to make

BAAAB

DCDCD

BAAAB

DCDCD

BAAAB

Modern period:

6: upgrade some As to Ds

BDADB

DCDCD

BDADB

DCDCD

BDADB

3A, 6B, 4C, 12D

900+3600+3600+14400=22500

Edited March 17, 2009 by CaptainEd

[Guest]

History of Stimville City

Archaic period:

in the picture below,

1: build the As

2: build the Bs

3: build the Cs

4: build the Ds

resulting in

BABAB

DCDCD

ABABA

DCDCD

BABAB

Medieval period:

5: replace some As and Bs in top, middle, and bottom, to make

BAAAB

DCDCD

BAAAB

DCDCD

BAAAB

Modern period:

6: upgrade some As to Ds

BDADB

DCDCD

BDADB

DCDCD

BDADB

3A, 6B, 4C, 12D

900+3600+3600+14400=22500

One small doubt... are we allowed to place the C such that diagonally placed A and B are permitted... isn't it compulsory to have a C only if you have ACB or BCA in the same line?

[CaptainEd]

One small doubt... are we allowed to place the C such that diagonally placed A and B are permitted... isn't it compulsory to have a C only if you have ACB or BCA in the same line?

Certainly a good question. I'm following the rules that say that "when built", the C must lie between A and B in a straight line (probably not diagonally). However, once they've been placed, I'm building some Ds on top of those As and Bs.

Is this legal? only the OP knows for sure. I expect he'll let us know soon.

[Guest]

Certainly a good question. I'm following the rules that say that "when built", the C must lie between A and B in a straight line (probably not diagonally). However, once they've been placed, I'm building some Ds on top of those As and Bs.

Is this legal? only the OP knows for sure. I expect he'll let us know soon.

Based on the way I read the puzzle, there are no constraints for what has to be around a building the whole time. Just when it's built. Following that logic, the answer you provided is the same that I'm coming up with. There are other ways, but none that reach higher than that population.

[Guest]

Based on the way I read the puzzle, there are no constraints for what has to be around a building the whole time. Just when it's built. Following that logic, the answer you provided is the same that I'm coming up with. There are other ways, but none that reach higher than that population.

u're totallly right in everything, CaptainEd u must have the three building (ABC) in a straight line... and yes, u can replace a building even if it violates the rules of the older buildings (...when built...)... But u're mistaken in one thing, UR answer, u CAN build a city with a higher population than the one u provided in ur answer..

[CaptainEd]

u're totallly right in everything, CaptainEd u must have the three building (ABC) in a straight line... and yes, u can replace a building even if it violates the rules of the older buildings (...when built...)... But u're mistaken in one thing, UR answer, u CAN build a city with a higher population than the one u provided in ur answer..

I feared this might happen

Your observation about corners and Ds on sides is very useful. The "Modern" solution puts Bs on all corners (the highest score that can be achieved from corners), 2 Ds on each side (the largest number of Ds that can be on each side), and even checkerboards the Ds. It's hard to imagine a configuration with more Ds. Also hard to change As or Bs to Cs. But I'm sure HellFire has enough light to see clearly...I can see how to put a D in the middle, after razing the downtown area, but I can't get all 4 Cs back in...Have any idea?

[Guest]

I feared this might happen

Your observation about corners and Ds on sides is very useful. The "Modern" solution puts Bs on all corners (the highest score that can be achieved from corners), 2 Ds on each side (the largest number of Ds that can be on each side), and even checkerboards the Ds. It's hard to imagine a configuration with more Ds. Also hard to change As or Bs to Cs. But I'm sure HellFire has enough light to see clearly...I can see how to put a D in the middle, after razing the downtown area, but I can't get all 4 Cs back in...Have any idea?

From the Modern solution:

BDADB

DCDCD

BDADB

DCDCD

BDADB

If we raze the middle column, and rebuild, we can get:

BDBDB

DCACD

BDADB

DCACD

BDBDB

Then, the two A's located in cells C2 and C4 can become D's again, giving:

BDBDB

DCDCD

BDADB

DCDCD

BDBDB

1 A, 8 B, 4 C, 12 D

300+4800+3600+14400

total population so far = 23100

Increase of 600 over Ed's, but I'm still not positive that there's not a better starting pattern. This is the cap for this set I believe. Anything else would require losing D's to build less in other places. Maybe someone else can destroy what I've built and give more space for people

Oh, and I love the /facepalm smiley.

[CaptainEd]

Oh, and I love the /facepalm smiley.

From the Modern solution:

BDADB

DCDCD

BDADB

DCDCD

BDADB

If we raze the middle column, and rebuild, we can get:

BDBDB

DCACD

BDADB

DCACD

BDBDB

Then, the two A's located in cells C2 and C4 can become D's again, giving:

BDBDB

DCDCD

BDADB

DCDCD

BDBDB

1 A, 8 B, 4 C, 12 D

300+4800+3600+14400

total population so far = 23100

Increase of 600 over Ed's, but I'm still not positive that there's not a better starting pattern. This is the cap for this set I believe. Anything else would require losing D's to build less in other places. Maybe someone else can destroy what I've built and give more space for people

Good job, Inzuri!

What kinds of improvements could be imagined?

1) Ds: this layout has the most Ds imaginable--JB showed we can't have 3 continuous Ds (no, he didn't, he showed you couldn't build them all at once). Hmm. At any rate, unless you put three Ds in the middle row, I think this is the max Ds. The top and bottom can only have 2 because of the corners. we already have 3 in two rows. Only the middle row could be upgraded.

2) C: since Inzuri has awesomely moved As to Bs, all that could wished for (I can't say "imagined") would be to upgrade some to C--a difficult thing requiring lots of temporary As and Bs.

I agree with Inzuri that any better layout probably needs a different starting point.

[Guest]

Good job, Inzuri!

What kinds of improvements could be imagined?

1) Ds: this layout has the most Ds imaginable--JB showed we can't have 3 continuous Ds (no, he didn't, he showed you couldn't build them all at once). Hmm. At any rate, unless you put three Ds in the middle row, I think this is the max Ds. The top and bottom can only have 2 because of the corners. we already have 3 in two rows. Only the middle row could be upgraded.

2) C: since Inzuri has awesomely moved As to Bs, all that could wished for (I can't say "imagined") would be to upgrade some to C--a difficult thing requiring lots of temporary As and Bs.

I agree with Inzuri that any better layout probably needs a different starting point.

Problem is, I don't know if there's a better starting point. Trying out different things, I get through three or four steps, and end up with basically exactly what we already have.

[CaptainEd]

Problem is, I don't know if there's a better starting point. Trying out different things, I get through three or four steps, and end up with basically exactly what we already have.

Me neither.

Can we start with a D in the center, and leave it there? Is it possible to build around it?

[Guest]

OK, great work you two. I admit I hadn't been thinking about replacing... just the best pattern that still fit constraints. I did a bit of tinkering from a blank slate and got a slightly better answer.

Start filling around the outside like this:

AAAAA

AAAAA

AAAAA

AAAAA

BDCDB

Fill all 4 sides of the square like that (note I changed some back to A if necessary):

BDCDB

DAAAD

CAAAC

DAAAD

BDCDB

This leaves it with sort of a sub-problem. Put a C in the middle, then start filling BDBDBD around the outside of that C:

BDCDB

DAABD

CDCDC

DBDBD

BDCDB

Then put the last D in the middle on top:

BDCDB

DADBD

CDCDC

DBDBD

BDCDB

Final: 1A, 7B, 5C, 12D = 23400

I hope that's not too hard to follow, I left a lot out for brevity.

[CaptainEd]

OK, great work you two. I admit I hadn't been thinking about replacing... just the best pattern that still fit constraints. I did a bit of tinkering from a blank slate and got a slightly better answer.

Start filling around the outside like this:

AAAAA

AAAAA

AAAAA

AAAAA

BDCDB

Fill all 4 sides of the square like that (note I changed some back to A if necessary):

BDCDB

DAAAD

CAAAC

DAAAD

BDCDB

This leaves it with sort of a sub-problem. Put a C in the middle, then start filling BDBDBD around the outside of that C:

BDCDB

DAABD

CDCDC

DBDBD

BDCDB

Then put the last D in the middle on top:

BDCDB

DADBD

CDCDC

DBDBD

BDCDB

Final: 1A, 7B, 5C, 12D = 23400

I hope that's not too hard to follow, I left a lot out for brevity.

Most cool! I enjoy the BDBDBD run around the moat; it reminds me of what Abel said of Gauss, "He is like the fox, who effaces his tracks in the sand with his tail"

I'll wait for HellFire to freeze over before I'll put more effort into this one! (Even though most of my effort has been in reading the last two solutions).

[Guest]

Me neither.

Can we start with a D in the center, and leave it there? Is it possible to build around it?

OK, great work you two. I admit I hadn't been thinking about replacing... just the best pattern that still fit constraints. I did a bit of tinkering from a blank slate and got a slightly better answer.

Start filling around the outside like this:

AAAAA

AAAAA

AAAAA

AAAAA

BDCDB

Fill all 4 sides of the square like that (note I changed some back to A if necessary):

BDCDB

DAAAD

CAAAC

DAAAD

BDCDB

This leaves it with sort of a sub-problem. Put a C in the middle, then start filling BDBDBD around the outside of that C:

BDCDB

DAABD

CDCDC

DBDBD

BDCDB

Then put the last D in the middle on top:

BDCDB

DADBD

CDCDC

DBDBD

BDCDB

Final: 1A, 7B, 5C, 12D = 23400

I hope that's not too hard to follow, I left a lot out for brevity.

Good job JB. Ed, I tried starting with a D in the middle, and this is the best I could come up with:

ADBDA

DCDBC

BDDDB

CBDCD

ADBDA

4A 6B 4C 11D

Comes out to 21600. I have all the steps broken down if someone wants to see them to try to get a better grid going. I'm still gonna work it more. Just had another idea for how to counter the A's in the corner problem. I'll repost if I come up with something higher.

[Guest]

OK, great work you two. I admit I hadn't been thinking about replacing... just the best pattern that still fit constraints. I did a bit of tinkering from a blank slate and got a slightly better answer.

Start filling around the outside like this:

AAAAA

AAAAA

AAAAA

AAAAA

BDCDB

Fill all 4 sides of the square like that (note I changed some back to A if necessary):

BDCDB

DAAAD

CAAAC

DAAAD

BDCDB

This leaves it with sort of a sub-problem. Put a C in the middle, then start filling BDBDBD around the outside of that C:

BDCDB

DAABD

CDCDC

DBDBD

BDCDB

Then put the last D in the middle on top:

BDCDB

DADBD

CDCDC

DBDBD

BDCDB

Final: 1A, 7B, 5C, 12D = 23400

I hope that's not too hard to follow, I left a lot out for brevity.

sorry, but still the answer is wrong

[Guest]

sorry, but still the answer is wrong

No hints on what we're doing wrong or anything like that?

[Guest]

Can't believe I didn't see making the center a D instead of C.

Animated! Yay. There is a jump once it shows how to do the outside edges.

1A, 7B, 4C, 13D = 23700.

[Guest]

Can't believe I didn't see making the center a D instead of C.

Animated! Yay. There is a jump once it shows how to do the outside edges.

1A, 7B, 4C, 13D = 23700.

The issue I'm getting from this is you're going from:

ACB

A A

AAA

to

ACB

ADA

AAA

in the middle. There's no B to work off of. Change the right A to a B instead of (or in addition to) the corner one that you did, and your animation works. The idea works as a whole, that's just something I noticed.

[CaptainEd]

Can't believe I didn't see making the center a D instead of C.

Animated! Yay. There is a jump once it shows how to do the outside edges.

1A, 7B, 4C, 13D = 23700.

Hey, HellFire, please look at jb_riddler's answer. Is it the best? (Inzuri has pointed out a minor flaw in the animation that can be easily fixed.)

Edited March 24, 2009 by CaptainEd

[Guest]

Can't believe I didn't see making the center a D instead of C.

Animated! Yay. There is a jump once it shows how to do the outside edges.

1A, 7B, 4C, 13D = 23700.

yes, it is the right answer!!