It is currently Sun Jul 23, 2017 3:49 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 98 posts ]  Go to page Previous  1, 2, 3, 4, 5  Next
Author Message
Offline
 Post subject: Re: Google Code Jam
Post #61 Posted: Tue Apr 11, 2017 6:09 pm 
Oza

Posts: 3990
Location: North Carolina
Liked others: 395
Was liked: 657
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
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 :lol: While deciding what language to use, my greatest fear was having to work with Java's horrible file IO.

_________________
Occupy Babel!

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #62 Posted: Wed Apr 12, 2017 12:56 am 
Lives with ko

Posts: 199
Liked others: 6
Was liked: 55
Rank: KGS 3 kyu
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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #63 Posted: Thu Apr 13, 2017 10:09 am 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
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?

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #64 Posted: Thu Apr 13, 2017 11:58 am 
Lives in sente
User avatar

Posts: 1153
Liked others: 51
Was liked: 165
Rank: KGS 5d
KGS: Str1fe, Midorisuke
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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #65 Posted: Thu Apr 13, 2017 12:13 pm 
Lives in gote

Posts: 635
Location: Littleton, CO
Liked others: 227
Was liked: 187
Rank: KGS 4k
Universal go server handle: jeromie
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.


This post by jeromie was liked by: Kirby
Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #66 Posted: Thu Apr 13, 2017 12:15 pm 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
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.

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #67 Posted: Thu Apr 13, 2017 12:20 pm 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
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!

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #68 Posted: Thu Apr 13, 2017 1:20 pm 
Lives in gote

Posts: 635
Location: Littleton, CO
Liked others: 227
Was liked: 187
Rank: KGS 4k
Universal go server handle: jeromie
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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #69 Posted: Thu Apr 13, 2017 1:46 pm 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
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 :-)

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #70 Posted: Thu Apr 13, 2017 2:06 pm 
Gosei
User avatar

Posts: 1820
Location: Bellevue, WA
Liked others: 89
Was liked: 814
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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 :P. Check it out!


This post by Solomon was liked by 2 people: ez4u, Kirby
Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #71 Posted: Thu Apr 13, 2017 2:24 pm 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
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 :P. 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 :-)

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #72 Posted: Thu Apr 13, 2017 6:54 pm 
Judan

Posts: 6208
Liked others: 1465
Was liked: 2367
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. :D

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:
1
n+1 B(m) B(n)

or this position
Code:
     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.

_________________
"Drooling Banjos"


Last edited by Bill Spight on Fri Apr 14, 2017 8:29 am, edited 5 times in total.
Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #73 Posted: Thu Apr 13, 2017 8:38 pm 
Judan

Posts: 6208
Liked others: 1465
Was liked: 2367
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.

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

Quote:
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.

Quote:
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.

Quote:
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. :D

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

_________________
"Drooling Banjos"

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #74 Posted: Fri Apr 14, 2017 12:28 am 
Dies with sente

Posts: 124
Liked others: 157
Was liked: 41
Rank: Chinese 3d
KGS: 3d
DGS: 3d
OGS: 3d
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.)

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #75 Posted: Fri Apr 14, 2017 9:25 am 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
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.

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #76 Posted: Fri Apr 14, 2017 5:30 pm 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
Thirty minutes to liftoff... Good luck, everyone :salute:

_________________
Discipline is remembering what you want. -David Campbell


This post by Kirby was liked by: Bill Spight
Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #77 Posted: Fri Apr 14, 2017 8:31 pm 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
Whew. Not fast enough, I guess. I worked on problems 1 and 2. Conceptually, they didn't seem very difficult. I ran into a couple of hiccups with getting the correct input for problem 2, and didn't get something submitted in time.

I guess I need to work on my speed.

I got problem 1 correct.

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #78 Posted: Fri Apr 14, 2017 8:45 pm 
Gosei
User avatar

Posts: 1820
Location: Bellevue, WA
Liked others: 89
Was liked: 814
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Couldn't get to my home in time to do it (was teaching Go at Sakura-con since I had the day off today). I did read the problems on the bus though, and thought Problem C was pretty awesome (and it looked incredibly difficult, which judging from the stats looked like it was). See you guys at 1B!

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #79 Posted: Fri Apr 14, 2017 8:54 pm 
Dies with sente

Posts: 124
Liked others: 157
Was liked: 41
Rank: Chinese 3d
KGS: 3d
DGS: 3d
OGS: 3d
Kirby wrote:
Whew. Not fast enough, I guess. I worked on problems 1 and 2. Conceptually, they didn't seem very difficult. I ran into a couple of hiccups with getting the correct input for problem 2, and didn't get something submitted in time.

I guess I need to work on my speed.

I got problem 1 correct.


Almost same here :cry: I got a couple of hiccups for problem 1 due to some infinite loops, and then it took me too long to understand problem 2. Definitely need to work on my speed!

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #80 Posted: Fri Apr 14, 2017 9:21 pm 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
KGS: Kirby
Tygem: 커비라고해
Yeah, the wording on Problem 2 sucked. I spent several minutes thinking, "what in the world are you asking?"

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 98 posts ]  Go to page Previous  1, 2, 3, 4, 5  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: Google [Bot] and 4 guests


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