Grid Problems 1 [Programming Competition Problems]

Key Takeaways

welcome back today we're going to be looking at a grid problem from google code jam called rotate this problem is based on a game called connect four in order to win the game connect four you need to have four pieces in a vertical horizontal or diagonal line this problem is a bit more generalized it doesn't necessarily need to be four in a row it's just going to be k in a row where k is an integer so what's going to happen is we're going to be given a board we need to rotate that board and then apply gravity to it and after we've applied gravity we need to figure out if any players have won the game so we have four different cases it's possible that none of the players have one the red player has one the blue player is one or both players have one so we're simply going to be outputting that either red blue neither or both and down below is a sample input and output which we can use to test our solution before submitting it all right so we can start by making our class and the first line of input is going to be giving us an integer which is the number of test cases and we're going to be iterating over these test cases and for each test case they're going to start out by giving us a line containing n and k so we can get these um so we have those two numbers now now we want to read in the grid and the grid is going to be an n by n grid so we can make a new array there okay so we want to read in the grid make a comment here okay so we're going to be reading in line by line so or row by row if you want to think of it that way so into y equals zero y is less than n and for each line i guess we need to read in the line so we can store that as a string see that next line okay now we want to iterate over each character in this line which which will represent a different column so we're gonna use a loop okay now if that um if the character that we're looking at is a period that means it's blank if it's r we're talking about the player red and if it's a b then it's blue so we're going to use a switch statement here maybe the cleanest way so we're going to be switching the character string.jar at x so i'll take the character we're currently looking at and so the first case if it's a period then um this is gonna be a blank so we need some way to represent what a blank is so we can just find some constants up here static final int blank let's just give us a value of zero we need two other constants though we want one for red let's give the value of one and one for blue for the value two okay so that's our first case and our next case is if it's capital r that means that it's the player red so y x equals red and final case is blue okay so now we've read in our grid now the next thing we want to do is rotate this grid but we can simplify this a bit so instead of rotating it and then applying gravity we can actually just apply gravity to the right as opposed to rotating and then playing it downwards so this just saves us a step it wouldn't be too hard to shift around your grid and rotate it but there's no reason why we can't apply gravity to the right so we we're gonna do that so we're gonna need to write a method to do this so shift all r's and b's to the right so we're gonna have some kind of method which uh gravity to gravity to right we're gonna pass in this grid and we'll find it later it'll be convenient to pass in the size of the grid okay so this is gonna give us a new grid where all the pieces have been moved to the right then after that we want to find the winners and then we're gonna want to print the result okay so let's start by filling in that blank so the gravity to the right so how we're going to do that okay so this we have a static method here uh it's going to be returning a new array called gravity to gravity to right um okay and we're going to be taking in a grid and let's take the size of the grid we could find that using length but it's just easier and we're going to be making a new grid at the same dimension okay so we're going to be going row by row so inch y equals zero y is less than n y plus plus so we're going to be shifting them over from right to left so what we're going to do is we're going to be iterating over the old array starting at the right side and every time we find something that's not a blank we're going to be putting it in the new ray starting from the right so we're going to want some kind of counter which starts at the right side and is incremented every time we add something so then things are moving over don't go to the same spot so i'm going to call that shifted x and it's going to start at n minus 1 which is the last cell on the right okay now we're going to be iterating over the old array x 0. okay so we're starting from the right going to the left if it's if grid y x is not equal to blank that means it's red or blue therefore new grid y and this is shifted x but we want to subtract one after we do this so that next time it's in a new spot this is going to be equal to either blue or red depending on what was here before okay and one nice thing with this is we don't need to initialize all the blank spots because we gave blank a value of zero so when you create a new array it's already zero so this is going to work just fine and we can return the new grid okay so now we have the gravity now we're going to need a method to determine if a player has one so we can make this generalized um well first we're going to give it its grid the size of the grid the number of pieces that we need in a row and we're also going to give you the value of the piece so that way we can pass in um we can use the same method for blue and for red so now you need to think about the different ways that a player could win we have the vertical case we have a horizontal case we have diagonal case but there's two different diagonals so we can go from bottom left to top right or we can go another diagonal um sorry top left to bottom right so those are two diagonals now what we want to do is we're going to be making another method called count pieces in row so count pieces in a row what we're going to give is we're going to give it a grid we're going to give it the piece that we're counting we need to give it an x value let's put x for now um a y value so this is where we're starting to check and then we we're going to be giving it is a dx and a dy value so this represents okay which direction are we moving in so in this case we're going vertically so if um so we're going to be okay so in this case we're going vertically so dx well if we go top to bottom then d y would be one and if we're going bottom to top would be negative one so it just represents the direction we're going for a diagonal dx and dy will both be non-zero and we're also going to just pass in n which is the size of the grid now we're going to be doing the same sort of thing for horizontal diagonal and the other diagonal but there's n different verticals we need to check so we're going to be putting this inside of a loop so okay indentation fix there so for this one we're going to be the first value is x so this represents which column we're checking so we can just pass the value of i here since it'll be changing so we're going to be checking a different column each time value of y we can just start at the top so value of 0. so our dx is going to be 0. and we're going to be going downwards so our d y is going to be one okay so if we find k pieces in a row so if this is larger or equal to k then we're going to be returning true because it doesn't matter how many times a player wins as soon as we found a pattern which indicates that they have won we can return true so we're going to be doing the same sort of thing down here for horizontal count pieces in row give it grid piece okay this time the x position is going to be zero let's start from left and the y position is going to be changing each time we go through this loop so this represents the row that we're on so row i and dx is gonna be one we're moving one to the right and d y is going to be zero because we're staying on the same row that's larger equal to k then we return true same sort of logic for the diagonals so this is going bottom left to top right so what that means is we need to be careful here because there's not just n different spots we can check so we're going to be breaking this up into sort of two parts so either we start on the left side of the grid or the bottom of the grid and for each of these we need to go upwards and to the right and see if we can make some kind of line um the way that we're going to be coding in here we're actually going to be counting we're going to be overlapping along the corner so we're going to be checking that twice but just for simplicity of code we can do that as you'll find it our solution isn't the most efficient but it's sufficiently efficient for this problem okay so for the first one we're starting on the left so get a value of zero the row is indicated by i and we're going to be going to the right and upwards this is true but you're in true and if we start along the bottom then our position is i and our vertical position is n minus one so it's just the bottom row and we're going to be going the same direction so one negative one return true i can't spell today all right so our other diagonal so if count pieces grid piece okay so we're going to be starting once again we have to break this up into two parts so the first case we're going to be starting on the top row so this is i and zero and we're going to be heading to the bottom right so dx is one d y is one we're going to return true and the other case is if we start on the left side and head to the bottom right so i that's zero and same direction okay so if we checked all the possibilities and none of them are true then we're gonna returning false so the final method we're going to need is this count pieces in row where does that come from okay so we gave it a grid we're giving it a piece we're giving it the x the y the dx and the dy as well as the n so we have a lot of parameters that's okay so we're going to need a few variables here so we're going to keep track of the most amount of pieces that we counted in a row start at zero and we're going to have like the current counter so every time this counter passes the max we'll update the max and every time we run into a piece that is not the piece we're looking for we can reset the counter to zero and everything that we need to be careful of is that we don't go outside the bounds of the board so that's what this while loop is going to do so we'll make sure that x is larger equal to zero y is larger equal to zero and x is less than n and y is less than n so as soon as we go outside of the board we know that we finished checking that column or row whatever we're checking and we can just break out this loop and return um return the max whatever that was okay so there's two different cases here if the piece that we're currently on matches the piece that we're looking for we can update the counter so counter plus plus and max equals math.max okay so i'll update the counter and the max value otherwise we can just reset the counter to zero because that means we've finished our streak and after we've done that we need to move to the next position so just x plus equals dx y plus equals d y okay so that method is done so now we can return back to the main method so we want to check to see if blue has one and red is one so i'll make some booleans here so red has one equals and we have a method for this um call it is winning and this method is going to take the grid n okay and the piece we're checking so checking for red in this case so i want the same sort of thing for blue okay so now we've checked to see if they have won and now we can print the result so a variable called result if blue is winning if blue is one and red is one then both of the players have won and the problem specified that we need to output this as both otherwise if blue has one if just blue is one because we won't reach this case if red is 1 as well then results equals blue else if red has one result equals red otherwise neither of them won neither okay now we need to print the result format it as they have specified so they want us to put case number sign and then the case number starting at 1 which is our loop value and then whatever string that we just built we'll put in there and of course we want to finish the line so that's our case number this is our string it's called result there we go we should be good so now we're going to run this on the terminal make sure everything compiles right and then test it against the sample input okay so we can start by compiling it drawback rotate.java okay we have an error so we can look back at our code i just made a simple mistake here i reused the same variable name i declared it again also there's no reason that we need to split a line that only has one thing on it so i can just refactor it to that it's a lot better anyway okay so now it compiles now we can run this against the sample input which i put in a file called test.n did not do that right um sorry i didn't pick the okay so that's what our program outputs we can compare that to what it should output and they match so that's good next we can go on to google code jam grab the input files that we actually need to generate and generate our answers i've already downloaded those so uh we can run this now java rotate feed of the file so it's called the a small practice study this is the small one and let's output this into a1.out and do the same thing for the other one a large data set and put an a2.out okay so now we've generated our answers all right so let's select our files okay 1.out and a2.out and we can submit both these first one is correct the second one is correct awesome so thanks for joining us today i had a fun time solving this problem and if you have any suggestions for problems that you would like to see solve not necessarily code jam there's lots of other cool websites that have programming competition problems but yeah if you have any suggestions just comment below and i'll see you next time bye