It is currently Thu Mar 28, 2024 11:27 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 37 posts ]  Go to page Previous  1, 2
Author Message
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #21 Posted: Mon May 01, 2017 8:02 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
bernds wrote:
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).


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

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #22 Posted: Mon May 01, 2017 8:25 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #23 Posted: Mon May 01, 2017 8:35 am 
Gosei

Posts: 1590
Liked others: 886
Was liked: 527
Rank: AGA 3k Fox 3d
GD Posts: 61
KGS: 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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #24 Posted: Mon May 01, 2017 8:40 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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.

_________________
be immersed

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

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
Kirby wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #26 Posted: Mon May 01, 2017 8:46 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
bernds wrote:
Kirby wrote:
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.

_________________
be immersed

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

Posts: 1590
Liked others: 886
Was liked: 527
Rank: AGA 3k Fox 3d
GD Posts: 61
KGS: dfan
Kirby wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #28 Posted: Mon May 01, 2017 9:33 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
dfan wrote:
Kirby wrote:
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.

_________________
be immersed

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

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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.


This post by Solomon was liked by: Bill Spight
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #30 Posted: Mon May 01, 2017 11:40 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
Kirby wrote:
Both in go and in programming, I should doubt my intuition more.

Kirby wrote:
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. :)

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #31 Posted: Mon May 01, 2017 2:27 pm 
Lives in gote

Posts: 319
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
the bishops problem is also trivially simple, its
[spoiler]
x +x-2
with the exception of a 1x1 board.

place a row of bishops on one edge, the a row on the opposite edge minus the corners.

[/spoiler]
i have no idea how to program an efficient solution to the holey chessboard problem however.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #32 Posted: Mon May 01, 2017 4:00 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Next round's theme will be strings. Just giving a heads up in case anyone wanted to refresh on string algorithms during the week, contest link here. I'll post a new thread when it starts (Friday 7pm PDT) with the link and other details.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #33 Posted: Mon May 01, 2017 8:43 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
Bill Spight wrote:
Kirby wrote:
Both in go and in programming, I should doubt my intuition more.

Kirby wrote:
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. :)


Agree with what you say. Also, in this case, the topic of the competition was recursion, so I might have focused too much on trying to find a recursive definition of the problem, and not enough about trying to solve the problem itself.

As soon as I read the problem, I was thinking, "OK, if I want to solve for board size N, how do I get this from board size N-1?"

I may have been to eager to use a technique, rather than really solving the problem at hand.

That being said, I'm pretty confident with the upcoming string competition - recursion and DP are weak points of mine. Though, given that I received 0 points this round, we'll see whether that confidence is founded :-)

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #34 Posted: Tue May 02, 2017 9:28 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
bernds wrote:
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).


This may make it clearer. (Not that it was obvious to me. It took a while to get there. Intuitively, I felt that there should be a straight line fit to the distribution of "N"s, but I had to guarantee that the maximum error was contained.)

Consider the sequence of these points:

1.5, 4.118, 6.736, 9.354, 11.972, 14.590. 17.208, 19.826, 22.444, ...

The difference between two consecutive points is Φ+1 = 2.1680... They represent the ideal positions of "N". OC, "N"s occur only at integer positions, so let's round the numbers. The first number could round either way, to 1 or 2, but that is true of our actual sequences. After rounding we get this sequence for the rest:

4, 7, 9, 12, 15, 17, 20, 22, ...

Which is the actual sequence of positions for "N". :D

Instead of rounding a floating point number I added 0.5 and used INT.

The proportion of "N"s is approximately 1/(Φ+1) = 0.382... Because, for positions greater than 2, all Fibonacci positions are "A"s, the proportion of "N"s in the next two positions after a Fibonacci number is 0.5. That is where the maximum deviations occur. You can already see that the fractional parts of 14.590 (after 13) and 22.444 (after 21) are near 0.5. The maximum deviations approach 0.5 in the limit as the positions approach ∞, but they remain bounded. :)

In a contest I probably would have just built bitstrings as necessary. Knowing that the string positions are identical after 2 meant that you could confine yourself to strings with a length of the next Fibonacci number after K. For instance, for 777 you just have to look at a string of length 987. :) But if I had found my solution quickly enough, I would probably have tried it without checking for the maximum deviations, just to be different. ;)

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #35 Posted: Tue May 02, 2017 12:25 pm 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 12
Rank: KGS 5 kyu
This is interesting. I just found this. I'll join for round 2. Though is this a programming challenge or is it mathematics challenge?

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #36 Posted: Tue May 02, 2017 12:44 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
peti29 wrote:
Though is this a programming challenge or is it mathematics challenge?
More programming than mathematics, but if mathematics is involved, it's usually in combinatorics or {number, graph, probability} theory at an elementary level.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 1
Post #37 Posted: Thu May 04, 2017 2:49 pm 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 12
Rank: KGS 5 kyu
Warmup ;-)

Hmm has anyone been able to solve
https://open.kattis.com/problems/rationalsequence2
in c#?

I keep getting a timeout limit and it's killing me...

Edit: never mind. I've had enough, cheated, googled the answer and meh, that's what I call a more mathematical than programming challenge...

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

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