A little programming chalenge « Next Oldest | Next Newest »

 ▼ Patrice Senior Member Posts: 274 Threads: 23 Joined: Sep 2007 09-15-2010, 07:22 PM 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 Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 09-15-2010, 09:50 PM 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 Senior Member Posts: 320 Threads: 59 Joined: Dec 2006 09-15-2010, 10:50 PM I don't think that would satisfy the "fill as much as possible" rule. ▼ Patrice Senior Member Posts: 274 Threads: 23 Joined: Sep 2007 09-16-2010, 01:40 AM 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 Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 09-16-2010, 06:21 AM Oops! I don't know how I missed that the first time around. Patrice Senior Member Posts: 274 Threads: 23 Joined: Sep 2007 09-24-2010, 01:52 AM Hi all, Just arrived in Fort Collins. Anyone working on the chalenge ? Patrice ▼ David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 09-24-2010, 06:45 AM 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 Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 09-24-2010, 10:34 AM 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 Member Posts: 104 Threads: 0 Joined: Dec 2007 09-24-2010, 05:25 PM 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 Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 09-25-2010, 08:42 PM 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 Senior Member Posts: 274 Threads: 23 Joined: Sep 2007 09-26-2010, 06:50 PM 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

 Possibly Related Threads... Thread Author Replies Views Last Post [OT] engineering student chalenge cyrille de Brébisson 1 957 11-25-2013, 10:06 PM Last Post: FORTIN Pascal was: A little programming chalenge: My solution, the principle Patrice 3 948 10-25-2010, 01:30 PM Last Post: Patrice was: A little programming chalenge Patrice 6 1,373 10-12-2010, 10:24 PM Last Post: Namir Custom Programming vs. Pre-packaged programming Eddie Shore 3 1,082 01-24-2005, 03:42 AM Last Post: Karl Schneider ACO has gone: a new chalenge? Vieira, Luiz C. (Brazil) 38 6,159 11-10-2001, 09:35 AM Last Post: Andrés C. Rodríguez (Argentina)

Forum Jump: