The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

A little programming chalenge
Message #1 Posted by Patrice on 15 Sept 2010, 7:22 p.m.

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

      
Re: A little programming chalenge
Message #2 Posted by David Hayden on 15 Sept 2010, 9:50 p.m.,
in response to message #1 by Patrice

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

            
Re: A little programming chalenge
Message #3 Posted by Chuck on 15 Sept 2010, 10:50 p.m.,
in response to message #2 by David Hayden

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

                  
Re: A little programming chalenge
Message #4 Posted by Patrice on 16 Sept 2010, 1:40 a.m.,
in response to message #3 by Chuck

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

                        
Re: A little programming chalenge
Message #5 Posted by David Hayden on 16 Sept 2010, 6:21 a.m.,
in response to message #4 by Patrice

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

      
Re: A little programming chalenge
Message #6 Posted by Patrice on 24 Sept 2010, 1:52 a.m.,
in response to message #1 by Patrice

Hi all,

Just arrived in Fort Collins.

Anyone working on the chalenge ?

Patrice

            
Re: A little programming chalenge
Message #7 Posted by David Hayden on 24 Sept 2010, 6:45 a.m.,
in response to message #6 by Patrice

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.

            
Re: A little programming chalenge
Message #8 Posted by Egan Ford on 24 Sept 2010, 10:34 a.m.,
in response to message #6 by Patrice

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

            
Re: A little programming chalenge
Message #9 Posted by Steve Perkins on 24 Sept 2010, 5:25 p.m.,
in response to message #6 by Patrice

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.

      
Re: A little programming chalenge
Message #10 Posted by Egan Ford on 25 Sept 2010, 8:42 p.m.,
in response to message #1 by Patrice

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.

            
Re: A little programming chalenge
Message #11 Posted by Patrice on 26 Sept 2010, 6:50 p.m.,
in response to message #10 by Egan Ford

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

[ Return to Index | Top of Index ]

Go back to the main exhibit hall