L19 Programming Problem Championship: Round 1 (Recursion)

[Solomon]

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.

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

[Bill Spight]

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".

[Kirby]

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.

[dfan]

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.

[bernds]

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).

[Kirby]

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).

Yes, I think you're correct. So my proposed solution was slow, took lots of memory, *and* incorrect

[Kirby]

I think I can draw parallels with this competition and with how I play go these days (though, it's been awhile back since I played a game).

I rely too heavily on intuition, even when that intuition is incorrect. I've played a lot of games of go, so I often have an idea of the right place to play - whether it's actually right or not. It takes very little effort to have this intuition or feeling, but it takes effort and work to verify that it's correct (or to find that it's wrong).

So often, I'm a bit lazy, and just go with my intuition, and just play the move that I think feels right - even if I haven't thought about it thoroughly to check to see if it's actually correct.

I think I find the same pattern in my programming these days. I've programmed for several years, and have some intuition about how to solve a problem - which may be incorrect, as seems to be the case in the Bishops problem. Instead of verifying or trying to check my intuition, I just trust it, and write up a program. Then when I run into problems, it takes a long time to figure out.

Both in go and in programming, I should doubt my intuition more. This takes effort and work, but is probably the only way to avoid these problems.

[dfan]

I think even more important is acquiring better intuition. To carry over the go analogy, I don't think that it's that you play the vital point without reading and then find out that it doesn't work; it's that you don't have a good intuition of what the vital point is yet. On all of the problems I pretty quickly had a good idea of what the shape of a good solution was going to look like. That comes from experience, not from calculation. To develop that intuition you just have to do a lot of these sorts of problems.

If you have the time, one good exercise might be to come back to some of these problems, armed with the solution outlines that bernds and I gave, and try to implement those solutions. There are plenty of blanks left to be filled in. I am sure that you would learn something.

[Kirby]

I agree that developing better intuition will help. But I do find it a problem that, during a game, I read 1 move deep. Or during a programming problem, I don't do much to verify that my idea is correct, and just get started. I think that this is a fundamental problem.
I plan on doing more of these programming problems to help develop my intuition. But even if my intuition gets very sharp, I think it's still good to do a bit of checking to verify that I'm on the right track.

Maybe it is just a matter of doing more problems. But I'm still concerned that I'm too hasty when I actually play a game or write up a program.

[bernds]

Both in go and in programming, I should doubt my intuition more.

I think the trick is acquiring a better working intuition and then relying on it. Doubting his intuition worked for George Costanza but I don't think he's a good role model.

Do you like mathematics? I don't have as much background there as I might like; while I did briefly try to find some kind of equation to solve Batmanacci, stuff like Bill's solution leaves me befuddled (never mind it would probably be less practical to implement than what everyone actually did). But it's still helpful to familiarize oneself with typical kinds of mathematical puzzles; I believe that does help developing an intuition.

[Kirby]

Both in go and in programming, I should doubt my intuition more.

I think the trick is acquiring a better working intuition and then relying on it. Doubting his intuition worked for George Costanza but I don't think he's a good role model.

Do you like mathematics? I don't have as much background there as I might like; while I did briefly try to find some kind of equation to solve Batmanacci, stuff like Bill's solution leaves me befuddled (never mind it would probably be less practical to implement than what everyone actually did). But it's still helpful to familiarize oneself with typical kinds of mathematical puzzles; I believe that does help developing an intuition.

Well, two people tell me that it's just about working on better intuition. Maybe I'm wrong - maybe it doesn't matter that I rely on intuition during games and programming. I thought I did it too much.

I guess I just need to develop better intuition, and that's that.

[dfan]

Well, two people tell me that it's just about working on better intuition. Maybe I'm wrong - maybe it doesn't matter that I rely on intuition during games and programming. I thought I did it too much.

It's never "just" about anything! I just think that intuition is a very important part, necessary but not sufficient. Of course you have to calculate too. I'm saying that just thinking really hard and carefully, without experience and intuition to back it up, is probably not sufficient to solve all of the problems from the round we just did.

I'm sure you that you have seen Malkovich games where kyu players calculate long lines out that you know right away aren't worth looking at, because they made a clear error on move 3 or because the result is clearly bad for the side considering it. Your dan-level intuition rightly tells you that they shouldn't be wasting time on that calculation. They need to work on their calculation, because they need to work on everything , but to get past those issues they need to develop their intuition.

[Kirby]

Well, two people tell me that it's just about working on better intuition. Maybe I'm wrong - maybe it doesn't matter that I rely on intuition during games and programming. I thought I did it too much.

It's never "just" about anything! I just think that intuition is a very important part, necessary but not sufficient. Of course you have to calculate too. I'm saying that just thinking really hard and carefully, without experience and intuition to back it up, is probably not sufficient to solve all of the problems from the round we just did.

I'm sure you that you have seen Malkovich games where kyu players calculate long lines out that you know right away aren't worth looking at, because they made a clear error on move 3 or because the result is clearly bad for the side considering it. Your dan-level intuition rightly tells you that they shouldn't be wasting time on that calculation. They need to work on their calculation, because they need to work on everything , but to get past those issues they need to develop their intuition.

Can't say I disagree with that.

[Solomon]

Something to add on top of everyone's awesome writeups...

Bishops

Even if you don't happen to "stumble" upon the ideal configuration (which I did in my case, after drawing too many bishops and chessboards on graph paper...), you can utilize the pigeonhole principle to determine the maximum number of bishops that can be placed on the board, i.e., see this PDF for more information.

[Bill Spight]

Both in go and in programming, I should doubt my intuition more.

Well, two people tell me that it's just about working on better intuition. Maybe I'm wrong - maybe it doesn't matter that I rely on intuition during games and programming. I thought I did it too much.

I guess I just need to develop better intuition, and that's that.

Well, then, how to develop your intuition?

There is a popular misconception that I would like to address, and that that you only develop your intuition by relying upon it. I am not against relying upon intuion. Sometimes you take a leap into the unknown. And, as you know, I encourage people to develop seeing, not just reading. But back in my cognitive psyche class we learned that intuition is associated with knowledge. As a rule, the people with the best intuition about certain things also have the greatest knowledge about those things. And in my own life I have found that knowledge increases my intuition. One of your recent tsumego problems has a Golden Cock Stands on One Leg position, another has a double snapback. Each of those chunks of knowledge helps you to see the correct play. Intuition always runs ahead of knowledge, and increasing your knowledge lets it run further.

OC, increasing your knowledge is not the whole story either, but people tend to contrast intuition with knowledge when, in truth, they go together.

As for doubting your intuition, that's healthy, too. In fact, testing your intuition is a way to increase your knowledge. Earlier you said something about reading just one move ahead. If you mean go move (ply), I doubt it. Often you also see your opponent's reply. As you know, when doing an and/or search, to prove that an option leads to a solution, you do not have to examine other options, but you do have to examine all of the replies to it. So in go, it is more important to see your opponent's plays than your own. That way you can test your intuition and in so doing, increase your knowledge.