Programming Problem #2 - Magic Squares (Novice/Intermediate)

Key Takeaways

hey guys and welcome back to the second video in my programming problem-solving series and in today's video we're moving into a bit more of a complex problem so the last video I did we had a decent problem it wasn't too hard it wasn't too difficult is fairly straightforward and fairly simple if you guys are new to programming and you're new to solving problems I'd recommend you go watch that one first I'll leave a card up in the top right hand corner and I kind of give a little intro and go over what the series is about if you're wondering about that so let's just get right into this problem today this one is called magic squares now pretty much what this is is we all just read it out to you the introduction of magic squares a 2d matrix composed of n to the power of 2 or n squared integers where n is the length of one row or one column and in a Magic Square each row each column and two and the two diagonals must sum to the same value so we'll look at the example below here and you can see we have a square we have two nine four seven five three six one eight and all of them some to 15 so the diagonals here and so they'll sum to 15 so how can we figure out if a square is a Magic Square and that's what the problem says here so it says given a 2d matrix which is the same thing as this right here in the same form as shown and as mentioned above your program must determine if the square is magic or not magic it will output magic or not magic accordingly so your program will first take an input n representing the length of one row of the matrix it will then take n lines with input containing n integers separated by spaces and then if we look below I have my sample input and output that I've written here for you guys obviously this first one is pretty straightforward just to show you the obvious Nastase if all of the numbers are the same then obviously the square is going to be magic because no matter where you add where you sum all the things they're all going to equal four so what am i saying six in this case and you can see if you didn't quite understand input line here what's first gonna happen is your program is gonna take one line here which is gonna tell you how long one row is and how many rows there are so it tells you three three rows and then in each row you have three elements right so this next one is a more complex case you can see we have a length of four so this square is indeed magic it might not look like it and it's hard to tell and that's why we write programs to determine this so when you guys are testing out your program make sure you test out different all these different test cases so I have these two that are magic I also have another one here that's not magic I just made these numbers up and wrote them in here so if you guys just make up your own numbers and type them in then you can also test if those are not magic squares so yeah I'll give me a second here to pause the video if you guys want the actual sheet here that I have then I have actually shared a Google tribe with you in the description down below I forgot to mention this in my last video but if you go to the description it'll say my solutions or my answers or whatever click on the link there it should bring you to a Google Drive and then on that Google Drive you can see the the folder I have go to the according problem so it'll say magic squares and then you'll be able to see this and my python file is with the solution as well so I'll scroll through it here so you guys can have a look pause the video when you feel like it and go ahead and try the problem again this is slightly more advanced so I'd say this is probably about a novice problem and it should take you about 15 to 20 minutes to complete may be a bit long okay so I hope you guys have had a chance now to complete the the program hopefully you were able to get it working if you've noticed it's not too difficult to actually code this it just is slightly tedious and it takes a few steps so let's get into the solution now okay so the solution so I have already here in Python my solution so the first part of the problem is understanding how it works so this one wasn't too complicated we have a square and we just have to figure out all the numbers do they add to the same thing so the first part actually after we figure out so I guess the second part is now taking the input and you'll notice as I introduce more problems the input for them is gonna become a little slightly more complex and even just taking the input for the Perl is going to be something that you have to figure out yourself so here we said n is equal to the int of input so I'll just show you when I run the program all I have here I don't have any prompts it just all you do is you type a number and then you're prompted to type the next row of numbers accordingly like so I'm and yeah and then it will output whatever they obviously that didn't work so I didn't type the right amount anyways we then set up a new array where I guess the list in Python I'm calling this a matrix and then I'm saying four rows in range n so we take however many rows or is gonna be and then for all those rows were then gonna take all those numbers on each line so we say nums are equal to that input of that line again this can happen say if we had four rows this will happen four times and then we append all those numbers into a list into a two-dimensional list so we actually end up having a matrix of matrix that looks something like this and it has a bunch of lists inside of it and that's called a two-dimensional array or two-dimensional list and that's the way that I like to set up the problem just so that I can kind of visualize it as well and that's each one of these would represent one one row so if we had one one one one one one one one one this would be a Magic Square with three rows and three elements in each row all right so three columns and you can see that if we were add all these together then we would get three for all of them and it would all work out like that okay so I'm gonna get rid of this now but that was just an example to show you so that's what that that's what this line is doing here it's just pretty much setting it up into a two-dimensional array and then I've just written a comment here saying we can take a three step approach so there are three things that the square has to satisfy right so the rows must add to each other the columns must add to each other and the diagonals must add as well so let's check all three of those things individually you can do them all in one big step but I prefer just to do them individually it keeps the program cleaner and it's easier to read especially for you guys so I first just start off by setting a variable called magic now what this is going to do is we're just gonna set this to false the second we find that the square is no is no longer magic because once we find that it's not magic there's no point in continuing we can just set it to false right away so now what I'm doing here is I'm creating a new matrix and this is called C matrix so this might seem a little confusing at this point but pretty much we have a two dimensional list up here which I'm calling matrix that has all of our rows and columns it looks exactly like this if you were to print it out onto the screen that's what it would look like your Magic Square and then here I'm setting up a column matrix now what I'm doing is I'm just adding a new level into the array a new dimension into the list according how many rows we have how many columns we have and then after this I'm just grabbing the value that we want to check so because we know that all of the columns and all the rows need to add up to the same value we can just pick any column any row that we want and just get the sum of it and say well we need to make sure that everything equals that value so that's why I've just picked to the sum of matrix 0 so this is Rho 0 that's the sum of it and then we start by checking the rows so here I have a new for loop say for X row in enumerate matrix if you don't know what enumerate does it pretty much allows you to have a counter variable and a variable that has the actual value in the matrix so it's really useful to use that so we say if the sum of our row which is going to be equal to obviously the row it is not equal to value which is 1 we've checked up here then we're just gonna instantly say magic equal to false that's it we're done we don't need to do anything else and we know the square is no longer a magic so we check all of the rows now say that they are they do all add to the same thing well now what we need to end up to do is we need to set up our column matrix so the first matrix I set up has the rows in it now we want ones with the columns in it so that we're able to add all of the columns up together so we're going across adding not and now we want to add down so I just do this in the same step as I'm checking the rows because it makes sense to do it in the same for loop rather than setting up a new one again I'm saying for a common element in a numerate row so for every element in our row I'm going to add that element into the corresponding matrix for the column so into so for each row I'm gonna have a different dimension that each element goes into so for example this is this one if we're on zero zero right now we're gonna go into the first first column and this is the first element in the first column and then we continue on and then the second element well that's gonna be in the second column the third element in the row that's gonna be in the third column and then once we go down to the second row so now we're on row two then we put this this is the second element in the first column and so on and so forth okay so now that we've set up our column matrix we go ahead and we can check our columns so now that we have them we can do the exact same thing we did up here except instead of using rows we're using columns and we're using the other matrix and we're just gonna say well if these columns if they don't sum up to the value that we've set at the beginning here then we know it's not magic so we'll set magic equal to false okay so this that part was fairly straightforward I know I went kind of fast through it but what we do here now is a little more complicated and this is with diagonals so I'm just setting up two variables to start here I and J now I equals zero Jake this is gonna correspond this is row and this is column okay so I've just set up now a little diagonal two-dimensional list as well and this is gonna have the diagonal on the left side and the diagonal on the right side and the reason I can do this rather than having to set it up variable wise like I have up here is because I know that no matter how big the square is we're only gonna have two diagonals corner to corner so it's fine to do it like this now I'm saying for X in range and so for the amount of elements or the amount of rows so on we're gonna say a diagonal zeros to the left side and we're gonna add matrix I and matrix J now what this does is since we're starting at 0 0 it's gonna add 0 0 and I'm just gonna pull up this actually because it's gonna make it a bit easier to understand so we're gonna have 0 0 here which gonna be 2 and and from the right side we're gonna say n minus 1 minus I now what this does is it we're on the same row so if I get back here we're on the same rail we're still here in the same Jake J value but we need to go we need to go back because right now we're here we want to get to 6 so how do we do that the way we do that is we say well we know that there's 3 elements in here if we're currently at 0 then we need to first subtract 1 because obviously there's not a third what do you call them here it's only it only goes up to 2 if we're counting like programmers which we are so we say n minus 1 now we're at 2 & 2 minus I since I zero that plops this over to here where 6 is so we can get the other diagonal value now after we do that we're gonna add 1 to both of these values so you can see that over here we add 1 to both of them so that means we're now moving down and we're moving to the right so I've started at 0 0 I'm now going down 1 to the right where I get 5 and same thing from this side I'm here starting at that so now that our values gone up by 1 and we've subtracted 1 from it mine is from a done or whatever and now we're back in the middle as well and then we moved down one more time so for here we move down and then we move to the right for this one here and then here we're moving to the left so we're moving down or moving to the left so we can get that value and we just stored them in this diagonals two-dimensional list here and then we're just checking with a simple if statement here if diagonal 0 does not equal value or the sum of diagonals 1 does not equal value magic equals false and finally the conclusion if magic after all of this checking still equals true we haven't found any contradictions in the sums then we print magic otherwise we print not magic and yes that is my solution now I know this is a little little bit harder but these are good problems to start thinking about this one is just more tedious than it is difficult and in the next video we're gonna get into one that's maybe not as long but it's gonna require a bit more thinking so I'm gonna go ahead and run my program now prove to you guys that it does indeed work so first we'll start with the very basic case like that tu-tu-tu-tu-tu-tu like that we get a magic square run the program again I'm gonna put some random numbers in here this time dude 3 4 5 3 2 4 5 3 4 5 not magic now if I pull up my output here this 4 1 the one that you guys should be checking as well pull it up again how can I get this oh it's on the screen and I have to push it all the way over okay and let's make this a bit smaller there we are I'm gonna start by typing 4 and then 60 1 2 3 13 5 11 10 8 9 7 6 12 and 4 14 15 1 and we get magic so we can confirm that this program is indeed working and if you guys again have any other better way of doing this you found a more efficient solution make sure you either send me a link in the comments below or just post your code down there I'll have a look at it and if it is indeed faster than mine that I'll be sure to show you guys out in the next video so that's been it for this video if you guys enjoyed please make sure you leave a like on the video and subscribe to the channel and make sure you're around every Thursday for new programming problems [Music]