5th Serbian Open Optimizing Puzzle Championship

Information and discussion on Puzzle Competitions
Post Reply
NikolaZ
Posts: 20
Joined: Mon 01 Nov, 2010 12:21 pm

5th Serbian Open Optimizing Puzzle Championship

Post by NikolaZ » Sat 17 Nov, 2012 10:03 pm

Dear optimizing puzzle lovers,

I would like to invite you to participate in the fifth Serbian Open Championship in solving optimizer puzzles. Competition will start on Monday, November 26th. The puzzles will be available for download on website http://puzzleserbia.rs/vesti0.htm where you can read propositions.

Nikola

NikolaZ
Posts: 20
Joined: Mon 01 Nov, 2010 12:21 pm

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by NikolaZ » Mon 26 Nov, 2012 8:31 am

The fifth Serbian Open Championship in solving optimizing puzzles has started.

I wish you a good fun and best luck!

Nikola

kiwijam
Posts: 697
Joined: Wed 01 Jun, 2011 10:03 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by kiwijam » Fri 30 Nov, 2012 2:02 am

There are three puzzles here, which are rather nice optimizers.
If you haven't tried optimizing before, I suggest you at least look at the instructions. It's a very different style of puzzling I think, instead of being guided to a solution by the creator you decide yourself when you've reached your solution (but sometimes you'll know that you've found the best one possible!)
And if you feel inspired by them, you have until Monday to send your 3 solutions in... which is when the second half will start.

Janix
Posts: 381
Joined: Tue 22 Jun, 2010 11:59 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by Janix » Fri 30 Nov, 2012 8:46 pm

I've been having a go at these this week. Be good to compare notes after each section is over as to how you know "you've found the best one possible", from the initial 'assumption' or starting point onwards - and if your strategy changed as a result of the initial investigations. Without, hopefully, giving anything away, I would say that for one puzzle, then there *seems* to be a two stage process where the optimisation only takes place after you've found the optimal solution...?!

Generally, the more time you spend on these puzzles, the more interesting they get. And, I'm sure that you could write code to solve the first one - is this allowed?!

kiwijam
Posts: 697
Joined: Wed 01 Jun, 2011 10:03 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by kiwijam » Fri 30 Nov, 2012 9:47 pm

Janix wrote:I've been having a go at these this week. Be good to compare notes after each section is over as to how you know "you've found the best one possible", from the initial 'assumption' or starting point onwards - and if your strategy changed as a result of the initial investigations. Without, hopefully, giving anything away, I would say that for one puzzle, then there *seems* to be a two stage process where the optimisation only takes place after you've found the optimal solution...?!
Generally, the more time you spend on these puzzles, the more interesting they get. And, I'm sure that you could write code to solve the first one - is this allowed?!
I know what you mean for that one puzzle, I think it's fun not being sure if you're even optimizing the right thing, but as you continue the process you find out...
Hmm, it is hard to discuss now! Happy to chat further after Monday. Glad you're enjoying them too.
Technically any puzzle (opt or normal) could be solved by a computer program, and #1 would be easier than most. There are some optimizing competitions (the Germans have a monthly one) where you can use a computer as long as you declare it (effectively giving two highscore tables), but this is not one of those. Gotta use your brain!

kiwijam
Posts: 697
Joined: Wed 01 Jun, 2011 10:03 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by kiwijam » Sun 02 Dec, 2012 11:47 am

Hmm, seems each round is only 6.5 days, not 7, so my earlier comment was incorrect (well, for UK it was), submissions are due Sunday night 9pm.

Janix
Posts: 381
Joined: Tue 22 Jun, 2010 11:59 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by Janix » Sun 02 Dec, 2012 10:04 pm

I've just posted my answers. I have unexpectedly had to go away this weekend (week early to fetch daughter's stuff from Uni) which took out yesterday afternoon onwards until this afternoon, then delayed shopping trip with the better half, etc.

Therefore, I hope they accept them - I notified them by 9pm that I was writing them up and would send as soon as done - but annoyed that I couldn't put the icing on my cakes - I only hope that I baked them correctly!

Enjoy this week's challenges!

kiwijam
Posts: 697
Joined: Wed 01 Jun, 2011 10:03 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by kiwijam » Sun 02 Dec, 2012 10:21 pm

OK, I'll assume Round 1 has finished now...

Here's some basic thoughts.

Q1. Constellations.
For this I started with the six unplanned routes. I want them to be short, so I want AGHI to be near each other, and CDE, and BF.
And it turns out (coincidentally) that all the planned (long routes) go between these three groups, never within them.
And it also turns out (coincidentally) that there is an intersection star (call it Z) in the middle of the grid that divides the 11 spaces into three groups of 4 and 4 and 3. Any path through this central star Z is generally going to be longer than any path not through it.
All the long routes can be broken into two pieces at this star. e.g. Distance from A to B = distance from A to Z + distance from B to Z.
So the three different groups can be optimized separately, then added up at the end.
Then it's a matter of deciding which of the groups AGHI, CDE, BF, match each of the three 'regions': northeast, west, and south.
Just work out how many points they can earn in each place. e.g. AGHI can be 69 points in the south (3xAZ,3xGZ,3xHZ,3xIZ,-HA-AG-GI), and 68 points in the west, and can't fit in the northeast.
Throw in an L when finished.
Using this I got my best scores of 147 with HAGI or IGAH in the south, ECD or DCE in the west, and LBF or LFB in the northeast.

kiwijam
Posts: 697
Joined: Wed 01 Jun, 2011 10:03 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by kiwijam » Sun 02 Dec, 2012 11:03 pm

Q2. Pentomino XTV

When optimizing the sum of six numbers, the priority is to optimize the first digits of those six numbers.
So however you set up the X,T,V, you'll have 6 important cells and in each of the three grids you'll want the 3x2s and 3x3s to be in those six cells. This would give a maximum of 3x1500=4500 (plus a little bit for the other digits).
However if you rotate the V so that the corner is to the top-left then its two numbers will share their first cell. There are only five important cells now, with one counting double. Put a 3 in there in the grid can be worth up to 1600, for a total maximum of 4800 (plus).
Although having the V in that orientation makes it a little harder, it's worth starting here because if you can find any solution worth 4600+ then you know that it is better than any solution with a differently-oriented-V, so they can all be ignored.

I found there were four places where a V can go that might get grids of 1600+.
One of these cases even had two grids of 1600+ using six different pentominoes, but the remaining three pentominoes only gave me 1243 points, which was disappointing.
So next I went through all the ways of getting 1500 point grids for these four cases. This took a few hours, but it was helpful to use a spreadsheet to copy/paste all the different options.
Every time I found a 1600 or 1500 grid I would write down the three pentominoes used. And eventually I found three grids for one case that used all nine different pentominoes (worth 1600+1500+1500). In fact there were a few ways to do this, so I scored them up (and worked out the tens and units digits too now) and got a score of 4714.
See the XLS file for my working, hopefully it vaguely makes sense!
SerbOptPentominoesWorking.xls
5thSerbOptChamps round1 working
(132.19 KiB) Downloaded 377 times

kiwijam
Posts: 697
Joined: Wed 01 Jun, 2011 10:03 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by kiwijam » Sun 02 Dec, 2012 11:31 pm

Q3. Doppelblock

This one I had less idea about. I just kept building grids and hope that my best one is not too awful!

But I did learn some interesting facts about Doppelblock.
In all the 8 rows, a maximum of half of the digits can be between black squares. That's 24 of the 48 digits.
And you get 24 digits if and only if each row has one black in the left four cells, and one black in the right four cells. Doesn't matter where the black squares are, they can even be touching (if they're in the middle two columns).
The same rule applies to the columns obviously too.
So the row and column sums will include 48 digits (some count twice) if each of the four 4x4 quarters has one black in each row and column. So this seems a good thing to do, to get more digits into our final sum.
Some digits might be summed twice (try to make these bigger), some not summed at all (make them smaller).

Of course I'm assuming that all the row sums and column sums will be different, which is most of the challenge.
Next put the blacks into a grid. You only want one row with all 6 white cells between the blacks, because it will always sum to 21. Any sum of 20 or 19 will need 5 whites between the blacks, and so on.
I ended up preferring grids which had the white-cell-lengths of 6,5,5,4,4,4,3,3,3,3,2,2,2,1,1,0, then I'd start filling the large sums first (e.g. put a 1 and a 2 at the ends of the 5-length rows), trying to get as many as I could of 21,20,19,18,17,... . By squeezing lots of digits into the big numbers it gave me more chance that the small numbers would all be unique. But it wouldn't surprise me if there's a better way to do this.

I'm also unsure how much to optimize the 'red' numbers. 4s, 5s and 6s seem not worth it because they don't occur in most grids. But 2s and 3s are everywhere, and worth something. 1s seem less valuable. So typically I'd start (before doing the stuff mentioned above) by throwing as many red 3s in as I could in. Then I'd put a few red 2s in, preferably outside the blacks so they don't get summed. Then I'd start fitting my big sums in. And finally I'd hope that a 5 appears in a corner!

The XLS also includes a little of my working, when I made a guess I'd copy the grid across to the side, then if it didn't work I could go to a previous grid and try something else. I mainly used paper though.

My score was 213 (I like that the digits in the grid start and finish with "213" also). Even my worst score was only 204, very close, whenever I tried to make more points from a new strategy I'd lose them somewhere else. I should probably wait to see what the best answer looks like, but anyway that's how I did them.

NikolaZ
Posts: 20
Joined: Mon 01 Nov, 2010 12:21 pm

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by NikolaZ » Mon 03 Dec, 2012 8:41 am

Thank you, James! Interesting thoughts. I hope you will enjoy this week too, because the second round has started just now.

Nikola

Janix
Posts: 381
Joined: Tue 22 Jun, 2010 11:59 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by Janix » Tue 04 Dec, 2012 12:45 pm

Question 1

I didn't have time to optimise this, but I got as far as recognising the different constraints of the planned routes vs the unplanned routes and the 4,3,4 scenario. My worst score - submitted just to enter - only 104

Question 2

Lots of degrees of freedom on this one. Did the min-max constraints, and was moving towards a structured submission, however, there were lots of permutations. I populated the bottoms of the grids first as most scores are taken from the top / middle of the grid. Submitted 3467. Would like to have had the hours to move them pentominoes around...

Question 3

My best effort - and here I spent time on the first constraint - where do the black blocks go. I came up with a diamond structure with 45 on the top row, 36 second, 27 third, and 18 fourth and fifth, then back to the centre on the eighth row.

This achieved the 24 counting squares, and provides symmetry - which is always pleasing.

I did not have time to optimise the score, however, I achieved 2x100 = 200 plus 12 from 6x 2, giving 212 (my submission - one less than yours!). Looking at my solution, I feel that there must be a way of getting at least one 3 in the correct position so I reckon the optimum score should be at least 215...

Janix
Posts: 381
Joined: Tue 22 Jun, 2010 11:59 am

Re: 5th Serbian Open Optimizing Puzzle Championship

Post by Janix » Sun 09 Dec, 2012 9:42 pm

Oops - in respect of last week. Totally overlooked the BOLDED requirement for only unique scores to count somewhere in the course of the week, and didn't even pick it up on submission...

Didn't submit this week, but spent a good few hours playing around with Eight Equations. A beautiful problem where you can stuff all the symbols in, bar one. And I didn't get close to choosing the optimum numbers for the optimum layout - is this another double optimisation?!

On Word Search Improvement, I found the sheer number of changes possible too large a commitment, even though I tried to simplify it. For example, I grouped all the W,D,V,F,J,K and Q letter in words together and tackled the grid this way for minimal substitutions and word crosses, but very few countries popped out, before eliminating these letters from the grid. Then I looked at C, O, M and ran out of time.

From all these the best result was ZAMB(h)IA(c)/MALI(w) - from bottom rhc diagonally up scoring 12 for three substitutions - value score of 4 (12/3) per replacement letter, things went downhill fast in getting anywhere near this score elsewhere on the grid.

The Sudoku with Perfect Squares appears to involve putting as many pairs of squares as possible throughout the grid, however, I couldn't see an obvious strategy to do this, and I did not spend much time here.

Post Reply