Puzzles & Programming Problems (Think Like a Programmer)

hello the Anton sprawl here again talking about how you can learn to think like a programmer in this video I'm going to talk about a classic brain teaser and explain how the thought process needed to solve this puzzle is like the thought process needed to solve a programming problem you see once you understand the syntax of a programming language reasonably well the difficulty in programming is all in the problem-solving part and the approaches needed to solve problems are similar no matter what kind of problem we're trying to solve this is something I talked about in the first couple of chapters of my book and it's really the key to becoming a good problem solver and therefore a good programmer but here's an example I didn't use in the book now let me say that this is an old old puzzle and you may already know the answer to it that's fine you just have to think back to how it was when you first heard the puzzle because the important thing is not the answer but how the answer is found so here's the puzzle you're following a recipe that requires exactly two ounces of water unfortunately you don't have anything with the measure for exactly two ounces or even just one ounce which of course would also work what you've got is one cup that holds five ounces and another that holds three ounces so how can you get the exact measure that you need again you may remember the answer to this if you don't though try to figure it out pause the video and give yourself a couple of minutes to think about it all right did you figure it out if you didn't don't feel bad very few people do I know I didn't see the answer the first time I heard one of these problems so here is the answer to get a measurement of two ounces we first need to fill the five ounce cup then filled the three ounce cup from the five ounce cup now there will be exactly two ounces left in the five ounce cup so that's the answer but here's another question why is that puzzle so hard it's because it involves pouring from one measuring cup to another and that's something that most people don't even consider think about it what if I had described the problem like this you've got two cups one that holds five ounces and one that holds three by pouring water into the cups from a faucet and by pouring water from one cup into another how can you measure exactly two ounces describing the puzzle that way removes much of the difficulty so the lesson from this puzzle is that restating the problem another way often makes finding the solution much easier how does this apply to programming the sample programming problem I'm going to discuss deals with permutations so we need to discuss that concept first to understand what a permutation is think of a three digit lock like you might see on a bike lock or a suitcase how many different ways are there to set the digits with three digits each of which can be set one of 10 different ways there are 10 times 10 times 10 or 1,000 permutations it's a little confusing that in official terminology we call these permutations and not combinations but in math a combination is a situation in which the order doesn't matter like if you're trying to figure out how many different sandwiches you can make out of the stuff in your refrigerator a ham and Swiss sandwich is the same as a Swiss and ham sandwich that's combinations but if you set the lock to 4 - 7 - 2 then you can't open it with 2 - 4 - 7 because the order the digits matters that's permutations to get started let me show you some basic code for displaying all the possible permutations of digits on our three-digit lock this is in C++ so let me walk through it quickly in case some of you aren't completely comfortable with C++ yet in C++ counting loops are normally written using for inside the parentheses the section before the first semicolon is where we initialize our looping variable the next section limits the looping in this case we are looping as long as our variable is less than 10 the last section is executed at the end of each pass through the loop in this case we are incrementing or adding one to our loop variable so each of these loops runs a different variable from 0 up to 9 the loops are nested or placed one inside each other so that each time the outer loop executes once the loop in the middle executes ten times and each time the loop in the middle executes once the loop inside it executes ten times so these things run sort of like an odometer inside the innermost loop we have an output statement here's a look at the first part of the output from this program as you can see it displays all the possible permutations of the lock okay all of that was just the setup here's the actual problem and it's similar to ones you will often see at programming contests there is a highly organized city that has decided to assign a number to each of three major departments fire police and sanitation each of these departments is going to get a number from one to seven as you might expect you can't give the same number to two departments furthermore for some reason is required that the sum of all the numbers equals 12 oh and the chief of police has an irrational fear of odd numbers and requires that the police department gets an even number so the problem is to write a program that outputs all the possible valid permutations of department numbers if you're the sort of programmer that is still struggling with problem solving this is the kind of problem that can start you sweating I remembered the trouble I had when I first saw this problem I recognized that it was a permutation problem and I was comfortable writing the sort of permutation code I just showed you so I thought about how I could modify that basic nested loop to get the results I needed but I kept running down dead ends my first thought was well I could run the loops from 1 to 7 so I did that as you can see it's basically the same code only I've changed the variable names and the loops now go from 1 to 7 instead of 0 to 9 but then I remembered that no two Dept numbers could be the same so I thought what if I started each loop on the digit after the current value of the previous loops variable that seemed like it would run through all the possible permutations without ever having the same value for any two variables I realized I'd be skipping some permutations that way because it meant that the fire department would always have the lowest number for example but maybe I could worry about that later but then I remembered that the police chief needed an even number for the police department so I thought I could modify that loop to start it 2 and increment by 2 instead of by 1 but wait how am I going to keep the idea of starting each loop one after the position of the previous loop and I haven't even started thinking about how I was going to get all the numbers to equal 12 I had a vague idea that maybe after computing the numbers for the first two departments I could just add those together and then subtract that sum from 12 and get the number needed for the Sanitation Department but what if the sum of the first two departments was already 12 or greater I needed some way to stop the middle loop before it went too far I was in trouble no doubt about it it wasn't that I didn't think I could get it to work eventually but I was looking at a lot of tricky coding and it was the sort of thing where I worried that even if I managed it it would take a lot of testing and I was never going to be 100% confident that my program generated only valid permutations then came the Eureka moment if you want pause the video and try to think your way through to a simple solution here's what I realized nothing in the question actually requires that the program generate only valid permutations for the different departments it just requires that the program outputs only the valid permutations in other words what I realized is I could just stick with my original code and generate every permutation of the digits one through seven and then before printing out a particular permutation check to see if it follows all the rules that program looks like this as you can see we generate every permutation of three numbers one through seven but then check to see if the numbers are different and the sum of the numbers is 12 and the police department number is even another advantage of this approach is that we could turn the checking into a function dividing our labor and making the program a lot easier to read now it looks like this again the lesson is when you are stuck on a problem ask yourself what are the things I know how to do what is the question really asking for don't ever assume that the direction that initially seems most obvious is the correct one and give yourself every opportunity to experiment with other approaches alright thanks for listening and I hope this helps some of you out there if you'd like to see more videos like this please subscribe and if you have ideas for topics or questions head over to my website for my contact information

Channel: V. Anton Spraul

Views: 266,397

Rating: 4.9043827 out of 5

Keywords: programming, C++, problem solving, beginning programming, how to think like a programmer, Programmer (Occupation), Programmer (Profession), Computer Science (Field Of Study)

Id: 2bkfA2fHVwg

Length: 11min 30sec (690 seconds)

Published: Fri May 17 2013