Life In 19x19

Posted: **Tue Apr 11, 2017 6:09 pm**

Kirby wrote:2.) Not a huge deal, but the logic I had for reading from and out to files was unnecessary. I like the idea of just using stdin and stdout - it cuts the program down to what's necessary to solve the problem.

I copied the sample code

While deciding what language to use, my greatest fear was having to work with Java's horrible file IO.

Posted: **Wed Apr 12, 2017 12:56 am**

Java IO is awful for competitions, and you must remember to use BufferedReader as Scanner might be too slow for reading the input. Although CodeJam is better in this regard, as they let you download the large file and give you a few minutes.

Posted: **Thu Apr 13, 2017 10:09 am**

I've been practicing a few problems here and there, and I notice that my mind kind of freaks out whenever I encounter a problem that might involve some sort of brute force solution (even if it doesn't). The Pancakes problem from the qualifying round is a good example - it didn't even require brute force, but from the structure of the problem, I didn't catch on to the fact that there's a systematic way to make progress and move forward.

Moving forward is particularly difficult for me in these types of problems. It's easy to setup some sort of enumeration of states so that I can do a breadth first search or depth first search, for example. But then there's the fear of encountering cycles.

An easy example is the classic Towers of Hanoi (https://en.wikipedia.org/wiki/Tower_of_Hanoi) problem. Obviously, I can look at the solution to see what they did, but without doing that, my thought process goes like this:

1.) Think of a couple of examples (using numbers to represent the size of the disk - smaller number is a smaller disk).

1
2
3 _ _

Valid moves? I can move "1" to either of the empty slots. Doesn't matter which, since it's symmetrical.

2
3 1 _

Valid moves?
a.) I could move "1" to the empty spot (silly, though, since it's symmetrical).
b.) I could move "2" to the empty spot.
c.) I could move "1" back to on top of number 2.

Obviously "c" isn't making progress toward a solution, and it's stupid. If I were playing the game myself, I can easily tell that moving "1" back to "2" is not making progress toward finding a solution.

But how do I express this so that the algorithm knows this?

--

So in short, my mind tries to think of a way to iterate through all possible "next states". But I get into trouble when I realize that I might end up going back to a "previous state". Then I get a little flustered about how to proceed.

--
Solution:
Looking at the solution, it says that the key to solving the problem is to realize that it can be "broken down into a collection of smaller sub-problems, to each of which that same general solving procedure that we are seeking applies".

So I guess the procedure is something like:
1.) Realize that, "Hey, if there were n-1 disks already stacked on a different peg, I can move the nth disk to the empty peg. Then I can use that same procedure to move the n-1 disks onto the nth disk."

2.) Then realize that the process will end when n gets low.

---

Looking at the solution, it's a systematic procedure. There's an observation that the problem can be broken up into smaller subproblems that, when combined, form a complete solution.

It's sometimes tricky for me to make this observation. It's sometimes difficult to prove in my mind that the smaller problems do, in fact, form the larger solution. As you can see from my convoluted thought process above, I don't make any observation about breaking the problem into subproblems.

Instead, I start with the big problem, then see what valid "moves" I have at each step. Then I get into trouble when I realize that I'm not systematically moving forward toward a solution.

How can I improve my ability to identify subproblems, and realize properties of the problem that allow for it to be build from these smaller subproblems? I guess the solution is to just do more of these types of problems?

Posted: **Thu Apr 13, 2017 11:58 am**

One way is to work backwards. For example, with Towers of Hanoi, the solution requires you to move the bottom block to a different peg - how do you do that? Well, the rest of the blocks have to be stacked on the third peg, or you can't move the bottom block to the right place. And then you note that this is a smaller version of the same problem.

Posted: **Thu Apr 13, 2017 12:13 pm**

Kirby wrote:
How can I improve my ability to identify subproblems, and realize properties of the problem that allow for it to be build from these smaller subproblems? I guess the solution is to just do more of these types of problems?

Doing many of these types of problems is helpful, but I also think that there are some strategies that can help you make progress more quickly. (There are easy analogies with tsumego here.) I'm not an expert on developing these type of algorithms (hence barely scraping by the qualification round), but I do have a few strategies I apply.

Try to consider the simplest case. Can you find a situation where the problem becomes trivial? In other words, don't start with the "big problem." Start with the simplest possible problem.
Expand a bit upon the simple case. Can you reduce a slightly more complex case to the trivial case with a little manipulation? As you increase the complexity of the case, can you find a pattern that emerges? Familiarity with various mathematical progressions can be helpful here, but I suspect that this is one of the areas where practice is very helpful.
Can you identify a similar problem with a known solution? What kind of algorithms are employed in those problems? (The pancake problem is essentially flipping bits. Does that help solve the problem? While I didn't have time to work on the fashion problem, I did recognize that it involved an n-bishops and an n-rooks problem - that gave me some avenues of research to pursue rather than trying to invent the algorithm from scratch.)

I don't think this really says anything you didn't already know (at least in theory), but it's important to recognize that there are real skills to apply here. In particular, breaking a big problem up into smaller problems is one of the most important techniques in computer science. Experienced developers do it automatically, but it's surprisingly difficult to teach to people new to the field. But I believe that it is a skill that can be mastered independently of your ability to develop complex mathematical algorithms.

Posted: **Thu Apr 13, 2017 12:15 pm**

Hmm, yes. It makes sense after I see the solution. It's not always easy for me to formulate with new problems. I think I just need more practice.

I'm trying a different one right now.

Posted: **Thu Apr 13, 2017 12:20 pm**

jeromie wrote:
Kirby wrote:
How can I improve my ability to identify subproblems, and realize properties of the problem that allow for it to be build from these smaller subproblems? I guess the solution is to just do more of these types of problems?
Doing many of these types of problems is helpful, but I also think that there are some strategies that can help you make progress more quickly. (There are easy analogies with tsumego here.) I'm not an expert on developing these type of algorithms (hence barely scraping by the qualification round), but I do have a few strategies I apply.

Try to consider the simplest case. Can you find a situation where the problem becomes trivial? In other words, don't start with the "big problem." Start with the simplest possible problem.

Expand a bit upon the simple case. Can you reduce a slightly more complex case to the trivial case with a little manipulation? As you increase the complexity of the case, can you find a pattern that emerges? Familiarity with various mathematical progressions can be helpful here, but I suspect that this is one of the areas where practice is very helpful.

Can you identify a similar problem with a known solution? What kind of algorithms are employed in those problems? (The pancake problem is essentially flipping bits. Does that help solve the problem? While I didn't have time to work on the fashion problem, I did recognize that it involved an n-bishops and an n-rooks problem - that gave me some avenues of research to pursue rather than trying to invent the algorithm from scratch.)
I don't think this really says anything you didn't already know (at least in theory), but it's important to recognize that there are real skills to apply here. In particular, breaking a big problem up into smaller problems is one of the most important techniques in computer science. Experienced developers do it automatically, but it's surprisingly difficult to teach to people new to the field. But I believe that it is a skill that can be mastered independently of your ability to develop complex mathematical algorithms.

Well, I wouldn't say I'm new to the field, but I am very rusty. I think I even recall doing the towers of Hanoi as a project in high school, but that was 15 years ago, and I haven't needed this skill much at work. I need to relearn it, and I'm glad to have this opportunity to do so.

Kind of reminds me of proof by induction (also something I haven't done for more than 10 years).

I guess it's just time to get back at it!

Posted: **Thu Apr 13, 2017 1:20 pm**

I didn't mean to imply you were new to the field! I teach Intro to Programming at a community college, and I was thinking of how difficult it is to get some of the students to break a big problem up into smaller chunks.

Posted: **Thu Apr 13, 2017 1:46 pm**

jeromie wrote:I didn't mean to imply you were new to the field! I teach Intro to Programming at a community college, and I was thinking of how difficult it is to get some of the students to break a big problem up into smaller chunks.

Indeed. It's difficult for me, too

I certainly don't mind having a newbie mindset in almost any field. I'm a perpetual novice

Posted: **Thu Apr 13, 2017 2:06 pm**

Kirby wrote:I guess the solution is to just do more of these types of problems?

If it gives you any motivation, there's a fun site called AtCoder that hosts weekly competitions similar to Topcoder, Codeforces, Google Code Jam, etc. However, the thing I like about this site from the others is that they have a ranking system just like Go (I'm 9k there atm, and tourist who could be considered the best in this field is 10d), and the quality of the problems are excellent with interesting problem statements and thorough editorials provided after the contest. It's also cool to see Petr do it live. The only downside is having to wake up at 5am on Saturdays

. Check it out!

Posted: **Thu Apr 13, 2017 2:24 pm**

Solomon wrote:
Kirby wrote:I guess the solution is to just do more of these types of problems?
If it gives you any motivation, there's a fun site called AtCoder that hosts weekly competitions similar to Topcoder, Codeforces, Google Code Jam, etc. However, the thing I like about this site from the others is that they have a ranking system just like Go (I'm 9k there atm, and tourist who could be considered the best in this field is 10d), and the quality of the problems are excellent with interesting problem statements and thorough editorials provided after the contest. It's also cool to see Petr do it live. The only downside is having to wake up at 5am on Saturdays . Check it out!

Awesome. I love it! Not that I can get much more practice in before tomorrow when Round 1 starts, but better late than never

Posted: **Thu Apr 13, 2017 6:54 pm**

Shaddy wrote:One way is to work backwards. For example, with Towers of Hanoi, the solution requires you to move the bottom block to a different peg - how do you do that? Well, the rest of the blocks have to be stacked on the third peg, or you can't move the bottom block to the right place. And then you note that this is a smaller version of the same problem.

Actually, that's working from the middle.

Working backwards from the solution is essentially the same as working forwards from the initial setup.

But yes, the key, middle move is moving the bottom disk to where you want it to go. And that means that you have to have constructed a smaller tower on the other peg.

To me an interesting question is where to play in this position.

_ B(m) T(n)

where T(n) is a tower with n disks, B(m) is the base of a tower with m disks, m > n, and _ is an empty peg.

Now, the more or less obvious way is to check the parity of n, but it is also obvious that you have children who solve the puzzle efficiently without doing that. How do they do so?

Perhaps they remember this position,

Code: Select all

1
n+1 B(m) B(n)

or this position

Code: Select all

     1
n+1 B(m) B(n)

just before they moved disk 1 to the top of B(n), and then moved disk n+1 to the top of B(m), producing _ B(m) T(n).

In the first case they next move disk 1 to the top of the base, which is disk n+1, and in the second case they move it to the empty peg. You can derive this from working backwards. If they just previously moved disk 1 from on top of disk n+1, then they move disk 1 back on top of disk n+1, otherwise not. They may not be able to verbalize how they know where to move disk 1, however.

Anyway, this method requires no arithmetic and only a short stack.

Edits: Edited the last part three times, the first time for stylistic reasons, but in a rush I left it incoherent. So I had to edit again. Sorry for any confusion.

Last edits for spelling and grammar.

Posted: **Thu Apr 13, 2017 8:38 pm**

Kirby wrote:I didn't catch on to the fact that there's a systematic way to make progress and move forward.

Moving forward is particularly difficult for me in these types of problems.

I don't know the problem, but if it is difficult to move forward, you might try moving backward.

It's easy to setup some sort of enumeration of states so that I can do a breadth first search or depth first search, for example. But then there's the fear of encountering cycles.

An easy example is the classic Towers of Hanoi (https://en.wikipedia.org/wiki/Tower_of_Hanoi) problem. Obviously, I can look at the solution to see what they did, but without doing that, my thought process goes like this:

1.) Think of a couple of examples (using numbers to represent the size of the disk - smaller number is a smaller disk).

1
2
3 _ _

Valid moves? I can move "1" to either of the empty slots. Doesn't matter which, since it's symmetrical.

2
3 1 _

Valid moves?
a.) I could move "1" to the empty spot (silly, though, since it's symmetrical).
b.) I could move "2" to the empty spot.
c.) I could move "1" back to on top of number 2.

Obviously "c" isn't making progress toward a solution, and it's stupid. If I were playing the game myself, I can easily tell that moving "1" back to "2" is not making progress toward finding a solution.

But how do I express this so that the algorithm knows this?

In some sense I get the feeling that you make it hard on yourself. You know that in the solution it is wrong to move "1" to the other spot, and you know that it is wrong to move it right back from where it came. Since those are the only options, what conclusion can you draw? It is wrong to move "1" at all. So you tell the program not to move the same disk twice in a row. (In fact, you move the disks in order until you cannot, as a little reflection will show.)

All it takes to think of that is a little generalization and a little logic.

So in short, my mind tries to think of a way to iterate through all possible "next states". But I get into trouble when I realize that I might end up going back to a "previous state". Then I get a little flustered about how to proceed.

Why iterate? You are starting from brute force trial and error, which may be easy to program, but is terribly inefficient and, in a graph, may cycle, as you say. There are better problem solving approaches. You don't play go that way. Nor do you solve tsumego that way, do you? If you have to resort to brute force, the problem is too hard for you.

Looking at the solution, it's a systematic procedure. There's an observation that the problem can be broken up into smaller subproblems that, when combined, form a complete solution.

It's sometimes tricky for me to make this observation.

Breaking a problem into subproblems is a bread and butter problem solving technique, as is working backwards.

As you can see from my convoluted thought process above, I don't make any observation about breaking the problem into subproblems.

Right. You grab the rough end of the stick, as I think Thomas Jefferson used to say. There is a problem solving literature, that you might find helpful -- and interesting, as well.

Edit: Another thing, which may or may not help. When I was learning to program, way back when, one idea was to start with data structures before devising algorithms. In the case of the Towers of Hanoi, smaller towers are obvious data structures. That might point to a recursive algorithm.

Posted: **Fri Apr 14, 2017 12:28 am**

In general, for all kinds of search problems/methods (BFS/DFS/UCS/A*, etc.) we can always draw a state space tree like this:
http://slidewiki.org/upload/media/images/25/4183.PNG

And in any case we need to avoid visiting the same state twice, which could be done by comparing e.g. the values or the hash of two states. Once you define the state representation, initial state and goal state, you can just search the tree/graph using existing algorithms.

(EDIT: But yes, if the problem can be broken down into a collection of smaller sub-problems, it might be solved in polynomial time with dynamic programming instead of searching with non-polynomial time.)

Posted: **Fri Apr 14, 2017 9:25 am**

Yeah, I think I have a tendency to go directly to brute force if the solution isn't immediately obvious to me. I think it's worth trying to think of the "right way" to do the problem efficiently. I've been practicing this a bit recently.

I actually hope to see some problems that require this kind of systematic breakdown into sub problems tonight.

I need some practice and this is a great way to get it.

Life In 19x19

Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam

Re: Google Code Jam