It is currently Thu Mar 28, 2024 9:47 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 37 posts ]  Go to page 1, 2  Next
Author Message
Offline
 Post subject: L19 Programming Problem Championship: Round 1 (Recursion)
Post #1 Posted: Wed Apr 26, 2017 3:42 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Following Kirby's idea for a weekly tsumego contest, I wanted to do something similar with programming problems after it looked like there was some interest in the Google Code Jam thread.

I'll be hosting the problems on Kattis, and every week I can either have the problems set to a certain "theme" (e.g., this Friday will be recursion / DP, next week could be strings, another week on graph problems, etc.), or just pick problems at random (but at various levels of difficulty) as a fun way to get the people in the venn diagram of Go and programming (which is a rather large intersection it seems) keep their programming sharp.

On a personal note, this year's GCJ has motivated me to try and do well in competitive programming. Specifically, like how in Go I set a goal to reach 1d, I've set a goal in the competitive programming space to reach purple on Codeforces and get into Div. 1, so it'll be motivating for me to participate myself in these (and I'd be cheating myself if I put in problems I've already done before, so don't worry about that).

Anyways, I already set up the first contest here, feel free to sign up and join (the problems on Kattis are quite good on their own):
https://open.kattis.com/contests/nhx45f

Time start: 2017-04-29 02:00:00 UTC (Fri Apr 28 2017 7pm PST)
Duration: 50 hours
Problems: 7
Theme: Recursion, DP

We can use this thread to discuss solutions after a contest, keep track of the overall leaderboard, and discuss other ideas for themes and contests. Hope to code with you this Friday!


This post by Solomon was liked by 4 people: Bill Spight, dfan, gamesorry, Kirby
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #2 Posted: Sat Apr 29, 2017 10:52 am 
Gosei

Posts: 1590
Liked others: 886
Was liked: 527
Rank: AGA 3k Fox 3d
GD Posts: 61
KGS: dfan
That was fun, thanks! I will have more detailed comments after it's over.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #3 Posted: Sat Apr 29, 2017 6:23 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
My parents are over, and we went hiking today, but I should have time to take a look tonight. Thanks for making the time limit long enough to have good enough time to participate :-)

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #4 Posted: Sat Apr 29, 2017 8:05 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
I don't quite get it. Do I just submit my source file? Is there a specific input filename I should read?

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #5 Posted: Sat Apr 29, 2017 8:10 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
Looks like it's stdin:
https://open.kattis.com/contests/nhx45f/help/judgements

I'll give it a shot.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #6 Posted: Sat Apr 29, 2017 9:22 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
Nice problems :-)

I'm having memory issues for larger inputs on the few I've tried so far. Maybe my approaches are too simplistic.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #7 Posted: Sat Apr 29, 2017 10:09 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Kirby wrote:
Nice problems :-)

I'm having memory issues for larger inputs on the few I've tried so far. Maybe my approaches are too simplistic.

Thanks! I hit MLE on problem C, but it was well deserved when I realized I'm dealing with input as large as 10^18. Hit TLE on B, but unfortunately it seems like it was just a language issue. When I rewrote the algorithm from Python 3 to C++, I got the AC.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #8 Posted: Sat Apr 29, 2017 11:03 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
Solomon wrote:
...but it was well deserved when I realized I'm dealing with input as large as 10^18. ...


I've really got to improve on this front. I've been practicing problems recently, and I can usually come up with an algorithm pretty quickly, but it seems I'm still pretty weak with large inputs.

I'll hide the following comments since I'm discussing some problem details.

1st Problem: Apparently easy based on what everyone else did - I must be missing an easier way to solve the problem. What I suspect may be the problem is that I maintain the board state on each recursive call (or maybe it's something else - this is just all that I could think of). This appeared to work for smaller inputs, but as soon as things got large, I immediately ran into OOM when trying to allocate an array to store everything. I tried to improve on this by using a bunch of bits to represent board state, and this resolved the OOM problems. But then I get a stack overflow for large inputs since I recur every time.

2nd Problem: Seemed similar to first, so I skipped it, suspecting I'd encounter similar problems.

3rd Problem: I just wrote up the program as the problem defined, and maintained a map of solutions I'd already done. When I came up with a new string, I added it to the map. I used a string builder to avoid many string copies. But the map was still too big to fit into memory for large input. Not using the map resulted in slow running time. Maybe there's some pattern I'm missing?

4th Problem: Didn't get a chance to read it.

5th Problem: Writing up directly how to get the sum was really straight forward and easy. But it's too slow for large input. I realized that I can probably take advantage of multiplication by the digits. But I ran out of time to work on this tonight.


I'm going to have to call it a night, and stop here for the problems this week (I'll be busy tomorrow). I realize I'm pretty weak at this, but I'll try to do better for Round 2.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #9 Posted: Sun Apr 30, 2017 7:03 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
I'll be asleep when the contest is finished in a few hours, but when I wake up I'll post the scores. Since I'm also working on these problems and I haven't gotten around to solving all of the problems, I'll just post my thoughts at a high level of how I approached the ones I did manage to get. It would also be cool if dfan and others who got all problems correct post their thought process for solving some of the more difficult problems. Also, was 7 a bit too many problems? I'm thinking for next round to drop it to 5 problems (1 easy, 2 medium, 2 hard). Let me know what you guys think, and congrats to everyone who did get all 7 in.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #10 Posted: Sun Apr 30, 2017 11:59 pm 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
Solomon wrote:
I'll be asleep when the contest is finished in a few hours, but when I wake up I'll post the scores. Since I'm also working on these problems and I haven't gotten around to solving all of the problems, I'll just post my thoughts at a high level of how I approached the ones I did manage to get. It would also be cool if dfan and others who got all problems correct post their thought process for solving some of the more difficult problems. Also, was 7 a bit too many problems? I'm thinking for next round to drop it to 5 problems (1 easy, 2 medium, 2 hard). Let me know what you guys think, and congrats to everyone who did get all 7 in.


I think 7 problems was fine, I had fun, and also it gives more choice if something seems like too big an obstacle.

When I saw the earlier Google Code Jam discussions I already thought this could be fun but I'd apparently missed the deadline, and the later rounds of that seem to have been unreasonably short. Can we see each other's solutions somehow on the Kattis site?

Bishops: quite trivial once you think about how to arrange them. How many diagonals are there, and can we fit one on each diagonal? Google also confirms the solution immediately. Got some failures trying to deal with EOF from gets. What can I say, that doesn't come up too often...

Holey n-Queens: also not too hard. You recurse, placing new queens wherever it's valid to do so. Keep track of which row, column, and each of the two diagonals already have a queen; you don't really need a board at all unless you want to print it (and since it came up in this thread: you don't need to allocate new boards or other information, just modify a global one before a recursive call, and undo your changes afterwards). Since you know you have to place n queens you can limit the possibilities a little, on recursion depth N you place a queen only on row N. I was worried we'd have to consider symmetries, but the examples showed we didn't. On the internet you can find correct outputs for the "N 0" case to verify your algorithm.

Batmanacci: I started with this one, I thought it sounded neat. Obviously you can't store all the strings: K can be too big. There's two tricks you have to realize: once you know fibN-1 and fibN-2, then for string sN you can tell which character comes from which predecessor sequence. If K is smaller than fibN-2, then you reduce N by 2, otherwise, reduce N by 1 and K by fibN-1. The other trick is to realize that even with 64 bit numbers you'll start getting overflow, but the limit for K is chosen such that at some point you will always be in the first half of the string, and only need to reduce N by 2 until you reach a magic number (92 or so) where you can correctly compute the fib numbers.

Pebble Solitaire: another problem where I didn't see anything obvious other than to recurse. The trick is making it go fast: subdividing the problem whenever you can prove that two subparts cannot influence each other. I think you can't cross two empty spaces from any given direction, so if you can show that there's a point you can't cross from either side, you can split your search into independent parts there. Also, black&white pebbles make nice binary numbers, and you can make a big lookup table where you store results up to a certain length. I was never quite clear on the memory limit: does it only apply to malloc, can I make really big static tables? Tried some pruning as well (if there are more isolated pebbles than in the best solution we've found at any level, we can stop), but it didn't seem that helpful.

Digit Sum: I was guessing a trivial implementation would be too slow. The idea was to find a way to increment by entire blocks of 10/100/1000 whereever possible, and to do it in two stages. If you want to go to 34567, you can do it from a starting point of 30000 by doing 4x1000, 5x100, etc. If you're coming from 23456, you then need to first get to 30000, starting from the low digits and working your way up. So, one step where your additions have carries, and one where they don't. After that it's just fiddly getting all the calculations right, and remembering to use unsigned long long everywhere.

Walrus Weights: Obvious steps: read in the weights, sort them, then compact the table to merge ones of equal weight. Had some mental block trying to decide what to do next; I think more practice with these sorts of problems would make it more obvious. A recursive algorithm works but fails runtime length requirements on one of the hidden problems. Finally got the algorithms book out to look at the knapsack problem, and that got me past it. I had been thinking the whole time I needed to build up a table of solutions iteratively but it would be too big, but then I realized I don't need to store combinations, I just needed to store weights achievable by the combinations of weights 0..N, iterating over N. I guess in hindsight it was obvious to me that this would be the solution, I just tried the recursive one first because the details eluded me. Doing these problems instead of sleeping might have had something to do with it.

Buying Coke: The main problem here was thinking it was fairly trivial and not realizing I sometimes had to insert 10+1+1+1 to get an extra fiver for later. I'm actually not convinced that my solution does the right thing in all cases (how about not having enough ones and therefore having to do some 5+5 combinations where you otherwise wouldn't), but the site accepted it. I liked this one least; if there is some important approach it teaches, it went over my head.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #11 Posted: Mon May 01, 2017 4:14 am 
Gosei

Posts: 1590
Liked others: 886
Was liked: 527
Rank: AGA 3k Fox 3d
GD Posts: 61
KGS: dfan
General comments:

The problems were good. Pretty much all of the were of the form "There's a straightforward algorithm that is far too inefficient for the size of the actual test inputs, so you need a clever trick," except for maybe Holey N-Queens, which I pretty much brute-forced.

It's too bad that the time constraints meant that Python was often not a good choice. (They even say so in the FAQ.) I started with Python but mostly switched to C++ after I had to spend a lot of time doing stupid Python optimization tricks to get my Holey N-Queens time low enough. Doing the rest in C++ reminded me of why Python is so much more pleasant to program in. :)

It was really tough not getting any more detail than "wrong answer" for code that produced the wrong answer on some input. I understand the reasoning, but it can be a real pain. This is the main reason that Buying Coke took me 19 tries (yikes).

I am out of practice when it comes to these sorts of problems but I am probably dan level when it comes to algorithms and programming puzzles. So it was nice to have a subject here that I could excel at for once. :)

Comments on the individual problems (I'm happy to go into more detail on any of them if desired):

A. Bishops
Right away I assumed that you'd just put bishops all the way down two adjacent sides of the board, and it was easy to confirm that this produces the maximum number (imagine putting them on the west and south sides, then look at at all the NE-SW diagonals; we fill them all, so there are no more bishops to place). I made a couple of careless mistakes (forgetting about the n=1 case, not noticing that I have to leave out one corner) so it took me three tries.

B. Holey N-Queens
I couldn't think of a better way than a standard recursive solution, going column by column and picking a valid row, and that was sufficient, though I needed to put in a fair number of optimizations to get my Python solution to be fast enough.

C. Batmanacci
Clearly you are not supposed to construct the actual strings. Ah, the ith letter in the nth string comes from either the n-1th string or the n-2nd string, and it's easy to find the correct index into that string (you just may have to subtract off the length of the n-2nd string), so once you compute all the Fibonacci numbers you may need it's a straightforward recursive algorithm. I did stick with Python for this one because it handles arbitrarily long integers and it was clear that my algorithm was going to be fast enough.

D. Pebble Solitaire
There are only 223 possible boards, which we can index by the integer corresponding to the binary representation of the board. Then it's perfect for dynamic programming. This is the only one I got in one try.

E. Digit Sum
The brute-force solution is clearly far too slow. My first idea was to have checkpoints (say, at 10, 100, 1000...) and precompute digit sums up to that point, then do some tricky differences. Then I realized that
  • It's much easier to just compute the full digit sum from 1 to a and from 1 to b, and just subtract one from the other.
  • The full digit sum is actually straightforward to compute in a recursive way.
I made two helper tables:
  • The digit sum from 0 to 10n for each n in 0..15
  • The digit sum from 0 to n for each n in 0..9
which I used in a slightly complicated but not-too-bad recursive formula.

F. Walrus Weights
It seemed like the key must be to phrase things in terms of the 1001 possible total weights, rather than the 21000 combinations of individual weights. So I kept a 1001-element boolean array of whether each total weight from 0 to 1000 was achievable in any way with the first n weights, then kept updating that as I ran through n. You do also have to keep track of your best over-1000 result, but that's just one number.

G. Buying Coke
I'm still not sure why this took me 19 tries. I think I kept fixing something and breaking something else in the process. The final issue was that I had a array for number of Cokes to buy that ran from 0 to 149 instead of to 150. Whee, C++ (yeah, I know, C++ has bounds-checking, but "for speed" I was just using a raw C multidimensional array).

In the end, it really was "just" a dynamic programming problem, but the fact that I kept failing kept making me think that there was something more subtle going on. One thing that tripped me up for a while was that my dynamic programming table was only indexed by number of Cokes left to buy, number of five-value coins, and number of ten-value coins, but I didn't clear it out between problems so it could have bogus data (the number of one-value coins is implicit from the other values, but only if you know how many you had to start with).

Thanks again to Solomon for setting this up! If you're going to do this on a regular basis I would definitely suggest reducing the number of problems. You proposed 5 but I think you could even go down to 3.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #12 Posted: Mon May 01, 2017 5:12 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
dfan wrote:
I started with Python but mostly switched to C++ after I had to spend a lot of time doing stupid Python optimization tricks to get my Holey N-Queens time low enough. Doing the rest in C++ reminded me of why Python is so much more pleasant to program in. :)
Really? I did everything in C and never felt that language choice would matter much for these kinds of problems, except maybe briefly when I thought I might need more than 64 bits of precision for Batmanacci. I tend to find I'm not enjoying myself much whenever I have to use Python - what was the problem with C++?

Quote:
There are only 223 possible boards, which we can index by the integer corresponding to the binary representation of the board. Then it's perfect for dynamic programming.
Quite. I think the strategy of starting to do problems instead of going to sleep and staying up all night caught me out here too; I think the whole time I fantasized I was under a stricter memory limit than I actually was. so I didn't even consider that even when I started building lookup tables...

Quote:
G. Buying Coke
In the end, it really was "just" a dynamic programming problem, but the fact that I kept failing kept making me think that there was something more subtle going on.
I wasn't even that subtle about it. If I'd been asked to solve a more general problem with arbitrary sets of coins I'd probably have found a better solution, but somehow I ended up thinking this was a trivial one like Bishops.

Quote:
Thanks again to Solomon for setting this up! If you're going to do this on a regular basis I would definitely suggest reducing the number of problems. You proposed 5 but I think you could even go down to 3.
I kind of liked the variety. It's not like one actually has to solve all of the problems since there's no prize or anything.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #13 Posted: Mon May 01, 2017 5:25 am 
Lives in sente
User avatar

Posts: 842
Liked others: 180
Was liked: 151
Rank: 3d
GD Posts: 422
KGS: komi
Unfortunately I was busy this weekend, so didn't really have any time to look at this (apart from a few minutes to do the bishops problem, which didn't really require any coding). Please do it again.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #14 Posted: Mon May 01, 2017 5:36 am 
Gosei

Posts: 1590
Liked others: 886
Was liked: 527
Rank: AGA 3k Fox 3d
GD Posts: 61
KGS: dfan
bernds wrote:
dfan wrote:
I started with Python but mostly switched to C++ after I had to spend a lot of time doing stupid Python optimization tricks to get my Holey N-Queens time low enough. Doing the rest in C++ reminded me of why Python is so much more pleasant to program in. :)
Really? I did everything in C and never felt that language choice would matter much for these kinds of problems, except maybe briefly when I thought I might need more than 64 bits of precision for Batmanacci. I tend to find I'm not enjoying myself much whenever I have to use Python - what was the problem with C++?

It really is just a matter of opinion. To me Python is the closest thing to "executable pseudocode", so it offers the least resistance on the path from envisioning an algorithm to obtaining a solution. The arbitrary-length integers were certainly nice in a couple of problems. Parsing is more convenient (though that wasn't much of an issue in this set). Automatic bounds-checking would have saved me from a stupid bug in the Cokes problem. Stuff like that. If you find C more pleasant I will not try to convince you. :)

Quote:
Quote:
There are only 223 possible boards, which we can index by the integer corresponding to the binary representation of the board. Then it's perfect for dynamic programming.
Quite. I think the strategy of starting to do problems instead of going to sleep and staying up all night caught me out here too; I think the whole time I fantasized I was under a stricter memory limit than I actually was. so I didn't even consider that even when I started building lookup tables...

Yeah, pretty much the first question I asked myself for every problem was "How much memory can I get away with using for my lookup tables / dynamic programming?"

Quote:
Quote:
Thanks again to Solomon for setting this up! If you're going to do this on a regular basis I would definitely suggest reducing the number of problems. You proposed 5 but I think you could even go down to 3.
I kind of liked the variety. It's not like one actually has to solve all of the problems since there's no prize or anything.

True, but some of us have a hard time not cleaning our plate. :)

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #15 Posted: Mon May 01, 2017 6:38 am 
Dies in gote
User avatar

Posts: 63
Liked others: 0
Was liked: 40
Thanks for setting up the contest, I also enjoyed it.

I used Python throughout, but for the walrus weights I did not manage to build a solution which ran within the acceptable time limit. (And in all test cases I set up, the run time was a lot shorter than the allowed 2 seconds, so that was a bit puzzling.) However, from the others' comments I see that my choice of algorithm was too naive.

It would be interesting to look at the solutions of the other contestants, but I suppose they are not available via the Kattis website, right?

Best regards,

Ulrich

_________________
u-go.net

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #16 Posted: Mon May 01, 2017 6:40 am 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Leaderboard

  1. dfan - 7
  2. bernds - 7
  3. ugoertz - 6
  4. Solomon - 4
  5. quantumf - 1

(if I'm missing your L19 handle, let me know!). I'll tinker with the number of problems and the difficulty levels until we find a good balance. Huge thank you to dfan and bernds for their detailed write-ups! I don't think I'd be contributing much with my own writeups since they covered everything I also did for the ones I did manage to solve, but I will be referencing them as I try to upsolve the problems I haven't managed to do, so it's very much appreciated.

ugoertz wrote:
It would be interesting to look at the solutions of the other contestants, but I suppose they are not available via the Kattis website, right?
Unfortunately no :(.

Also, for those curious, here were the difficulty ratings (higher = harder) for the problems in this round:

  1. Bishops - 2.0
  2. Holy N-Queens (Batman) - 2.8
  3. Batmanacci - 4.0
  4. Pebble Solitaire - 3.7
  5. Digit Sum - 5.6
  6. Walrus Weights - 4.0
  7. Buying Coke - 5.3

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #17 Posted: Mon May 01, 2017 6:55 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
Solomon, I think that this is a great idea. :)

I did not submit anything, but I did take an interest in the Batmanacci problem. Fibonacci numbers be very good to me. ;)

Years ago I worked out an estimation of the miai values of approach kos using Fibonacci numbers. Let S be the swing. Then for a 0 move approach ko (simple, direct ko), the miai value is S/3, for a 1 move approach ko the miai value is S/5, for a 2 move approach ko the value is S/8, for a 3 move approach ko the miai value is S/13, etc. I published the results, but somehow that has not become general go knowledge. {shrug}

Further comments hidden for courtesy. :)

Except for the first two letters, the rest of the letters are fixed, as this lineup illustrates.

N
A
NA
ANA
NAANA
ANANAANA
NAANAANANAANA

If you are looking for the Kth letter, as long as K > 2 it is arithmetically computable from K alone. :) OC, if K < 3 then which letter it is depends upon the parity of N.

Let Φ be the Golden Ratio = (1 + sqrt(5))/2 = 1.618...

If K > 2 AND K = int((Φ+1)*int(K/(Φ+1))) + 2
Then the Kth letter is "N"
Else the Kth letter is "A"

:)

If K = 7, then (Φ+1)*int(K/(Φ+1)) + 2 = 7.236... and the Kth letter is "N".
If K = 777, then (Φ+1)*int(K/(Φ+1)) + 2 = 776.938... and the Kth letter is "A".
If K = 777777, then (Φ+1)*int(K/(Φ+1)) + 2 = 777778.009... and the Kth letter is "A".

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.


This post by Bill Spight was liked by: dfan
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #18 Posted: Mon May 01, 2017 7:33 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
The bishops problem is a good example of how I should think more before I start coding.

I failed to make any observation about the properties of the board, noting that N=1 should be a single bishop, and for N>1, I could take a board solution for N-1, and check every open spot for placing new pieces.

Obviously that takes a lot of time and memory, though, it appears to "work".

Checking here: http://mathworld.wolfram.com/BishopsProblem.html

I see that the answer is just 2n-2 for N>1. Had I thought a bit more, maybe programming this would have been trivial.


Similar issue with Batmanocci.

I guess I should be less eager to write something up, and think a bit more.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #19 Posted: Mon May 01, 2017 7:47 am 
Gosei

Posts: 1590
Liked others: 886
Was liked: 527
Rank: AGA 3k Fox 3d
GD Posts: 61
KGS: dfan
Kirby wrote:
I failed to make any observation about the properties of the board, noting that N=1 should be a single bishop, and for N>1, I could take a board solution for N-1, and check every open spot for placing new pieces.

Obviously that takes a lot of time and memory, though, it appears to "work".

Checking here: http://mathworld.wolfram.com/BishopsProblem.html

I see that the answer is just 2n-2 for N>1. Had I thought a bit more, maybe programming this would have been trivial.

It helps to be lucky! As I said in my writeup, I thought I could just place bishops on all the squares of two adjacent sides. Obviously in retrospect you end up with lots of mutually attacking pairs. Luckily for me you can rearrange them and the solution remains the same. I didn't realize until I followed your link that my proposed arrangement was completely invalid. :oops:

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #20 Posted: Mon May 01, 2017 7:50 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
Kirby wrote:
I failed to make any observation about the properties of the board, noting that N=1 should be a single bishop, and for N>1, I could take a board solution for N-1, and check every open spot for placing new pieces.


Reducing a problem to a smaller one is often a good strategy, but you'd also have to prove (to your own satisfaction at least) that an optimal bishop arrangement for board N necessarily includes an N-1 board solution on a subboard. This isn't entirely obvious to me in this case, and it does not hold for the obvious arrangement of bishops (two almost filled rows, one at the bottom and one at the top column).

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 37 posts ]  Go to page 1, 2  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group