A little programming chalenge

[Patrice]

Hello all,

Here is a little programming chalenge (no prices). I will present my solution at HHC 2010.

It is all about optimization: be as fast as possible.

The goal is to fill as much as possible places in a figure while respecting the rule.

The figure is a square or a rectangle.

The rule is that there must be no more than 3 consecutive places filled in a row, a colomn or a diagonal.

Here is a 4*4 square :

. * * *

* * . *

* . * *

* * * .

Since the amount of calculus grows quickly, the programming can be done on a PC.

If you are under a minute of runtime, just make the figure bigger:
4*4, 4*5, 5*5, 5*6, 6*6, 6*7, 7*7 and so on.

To compare the results, give the size of your figure, the number of time you have try to fill a place, the timing in seconds, and the language for advice :

4 4 12 0 D

Be smart guys :-)

Patrice

Edited: 16 Sept 2010, 1:30 a.m. after one or more responses were posted

[David Hayden]

Thanks for posting this Patrice. I always like programming challenges.

I think there may be more to the problem than you're stating. For example, if I leave all of the places on the board unfilled, that would meet the rules that you've stated. So are we trying to fill in as many places as possible?

Thanks. See you at HHC2010!

Dave

[Chuck]

I don't think that would satisfy the "fill as much as possible" rule.

[Patrice]

You right, Chuck !

Quote:

---

The goal is to fill as much as possible places in a figure while respecting the rule.

---

This sentence is not clear enough ?

well ! I don't know when I will this forum again, I take plane in 6 hours.

Patrice

[David Hayden]

Oops! I don't know how I missed that the first time around.

[Patrice]

Hi all,

Just arrived in Fort Collins.

Anyone working on the chalenge ?

Patrice

[David Hayden]

I thought about it a little and tried playing with it on paper, but didn't get much beyond that. One problem I found was figuring out when I had an optimum answer.

[Egan Ford]

I cannot make HHC this year (too much work), I just canceled yesterday, so I may have time this weekend to work on it.

[Steve Perkins]

I thought about it for a while.

It's a worthy challenge.

I thought it was pretty easy, then I read it again and noticed the "diagonal" requirement.

I'm interested to see the results folks get.

[Egan Ford]

Quote:

---

Be smart guys :-)

---

My first not-so-smart pass (quick and dirty):

4 4 12 0 C

* * * . 

. * * * 

* * . * 

* . * * 

4 5 15 0 C

. * * * 

* * * . 

* . * * 

* * . * 

. * * * 

5 5 18 0 C

* * * . * 

. * * * . 

* * . . * 

* . * * * 

* * . * * 

5 6 22 1 C

* * * . * 

* . * * * 

. * . * * 

* * . * . 

* * * . * 

* . * * * 

6 6 26 14 C

* * . * * * 

* * * . * * 

* . * . * * 

. * * . . . 

* * . * * * 

* * * . * * 

6 7 31 234 C

* * * . * * 

* * . * * * 

* * * . * * 

. . * . . . 

* * * . * * 

* * . * * * 

* * * . * * 

7 7 36 0 Just thought about it.

* * * . * * *

* * * . * * *

* * * . * * *

. . . . . . .

* * * . * * *

* * * . * * *

* * * . * * *

I have a rather large project due. So, I'll try for a smart solution next weekend.

Edited: 25 Sept 2010, 9:22 p.m.

[Patrice]

Nice beginning Egan,

Brute force attack ?

Too bad you were not at HHC.

I have not presented my solution to the problem at the conference because schedule was too tight. I have done it only on reduced comity after the end of the conference.

I will post my solution in another treat on the forum, so that, you can continue your search and device a solution on your own.

Patrice