SBTB 2023: Stewart Stewart, Puzzles and Problem Solving with Scala Tooling.

SBTB 2023: Stewart Stewart, Puzzles and Problem Solving with Scala Tooling.

Recording: SBTB 2023: Stewart Stewart, Puzzles and Problem Solving with Scala Tooling.

[Music] um yeah good morning everyone it's it's good to be back here in person again finally I I've been really excited for this um yeah and uh there's a there's an ongoing theme here with my talk so last two times I spoke here I I I did speak about puzzles about logic puzzles and about solving rubby cubes so those are using relational programming and group Theory um respectively uh so we're continuing with that sort of theme and and talking more about uh problem solving like the thought process behind problem solving and specifically in a live coding um kind of a context uh so so for some background context to this uh during the pandemic I started doing more experimenting with live streaming uh live streaming live code as as I solved uh some problems um and you know that that was for for various reasons um but the uh the long and short of it is you know I want to I want to practice you know practice communicating code as as I as I do it right so this this helps with pair programming with any kind of tech demonstration you're doing perhaps in interview and of course a situation like this a talk which you know might sometimes include live coding um so I'm just going to get started right away with uh the Highlights today this is what I'm going to try and convince you of and one is that you should be embracing worksheets for more exp exploratory problem solving so I I think they're kind of um underrated perhaps maybe on the data science side maybe people are using Jupiter more often and then and know the benefits of that um but I think they really should be used in in a lot of context and even you know perhaps attached to your to your library that you're developing or or your production codebase um and you should be pair programming more often uh that that will be self-explanatory here in a bit um you should try recording yourself this this was a this was a really interesting exercise for me over the pandemic you know not so it wasn't just uh you know live streaming but when I when I stream I I have all these recordings on myself that I can review right so I have I have a couple hundred hours of footage to review of myself solving problems and I was able to take out a lot of uh a lot of insights from that uh and of course that you know scolar 3 is an excellent medium um for this kind of interactive problem solving uh and for like communicating your uh problem solving process and we'll go more into all those points later okay um I already mentioned this a little bit uh this is my context for you know why why I went to into uh into live programming live coding um and one thing I didn't mention here is it is fun to share and discuss puzzles or problem that you're you're solving like I I do very much enjoy uh pair programming with people and doing this collaborative um problem solving kind of a thing you know I also enjoy puzzle hunts that kind of a thing and it was it was a nice thing to do during the pandemic um and yeah you know here I've listed some of the some of the benefits but I'll move through these slides pretty quickly because I I do want we're going to end this with a a bit of a live coding demonstration um but yes i' I've touched on recording yourself and being able to watch that footage I've been able to catalog so this I I've made a lot of mistakes and this is this is not going to be in this talk like this will have to be like a followup blog post on all the mistakes I've made um um but you know I've been able to catalog a lot of uh common coding and reasoning errors that sort of cut the flow of your um of your process here um and you know I've I've been forced to try and find ways to like maintain Clarity of thought and explain these ideas you know explain what I'm working on as I'm working on it which is important for collaboration not not just when you're demonstration but when you're working with a coworker um you know on a colleague doing whiteboarding or whatnot okay so in this context where you're life coding you're trying to explain this to an audience you're trying to make sure they understand and they're keeping along with you there are a few things you want right so you want the ability to prototype rapidly get your ideas down on paper start start something start those uh uh start getting those ideas on paper and then once you have a start there you want to be able to expand it um expand upon those ideas maybe maybe change those ideas and you want to be able to do this fluently and and while maintaining you know the the correctness of your code maintaining the understand you know making sure it's still understandable and since problem solving is not always like a a linear process you know you want be able to like backtrack think about new ideas change your ideas go back to what your ideas were previously Etc right there's there's kind of a tree traversal as your as you're searching for a solution um and you know built-in testing also facilitates that and that comes alongside the this ability to demonstrate what you're thinking as as you're going right so if you're able to test things kind of in line as as you're going then you're able to demonstrate what it is you're trying to do um and that's beneficial for your audience of course but it's also beneficial for yourself and in in the same way that robber ducking can be um and of course we want to minimize debugging right it's not fun to it's not fun for either party if you're kind of stuck there scratching your head at a problem right it it's it's awkward and comfortable for you know the person who's who's doing it and it's it's awkward it can be awkward for the audience as well right and we we don't want that we want a a fluid a fluent you know Lucid problem solving process uh so these are the goals are driving me um when I think about my environment and my tooling and why I I use what I use here um of course I can touch briefly on this on on Scola as a medium of thought um this is this has probably been covered plenty by by other people in other talks but you know it's the same old you know you have type safety that that lets you offload some of the thinking to the compiler it lets you kind of encode your ideas uh in into into the source code um which which makes it easier for the for the environment to assist you but also easier for you to see where your train of thought was because you don't you don't want to be kind of thinking about what you were thinking earlier when you're trying to think of new ideas and problem solving right so these it communicates the ideas to you know whoever you're talking to and and to uh yourself you know a note for self for later and of course you know the tool is uh is great the interactive environments I'll get into that and um of course schar 3 as a as a language is very kind of flexible to uh to play with you know you can scale from different um constructs as as you're changing your approach to solving a problem and of course that's been gone over plenty so that's what not what this talk is about today um so I mentioned in the last slide here mentioned these interactive environments um and what I'm going to be focusing on today is the Scola 3 worksheets and there are a few ideas I I want to bring in here because I I I feel like this combines the the benefits of of some of these older ideas uh so test driven development um when Kent Beck wrote his original book on test driven development he'd mentioned an idea that uh he he sees he sees tdd as a way of giving programmers the benefit of the the small talk environment or you know of the environment and the uh the the interactive nature of it right it it's so when you when he was going from a dynamic language to a you know compiled language he was he was missing some of that benefit of being able to go into the r and you know explore explore these ideas as you go and just test things out you write a line of code you see what it does and then you keep you keep iterating on that and that was one of the reasons why he he um he recommended test driven development was that you know the the unit test being able to run on each compilation uh kind of replicates that right but now um with worksheets we we kind of get that we we kind of get a reppel Plus+ right so um the SC of reppel is all very nice and of course like a natural evolution of that was ammonite with like the multi-line editing and whatnot um and of course like now ammonite in like Metals worksheets uh so it's uh it's it's still interactive you you get you get the uh results of all the all the code that you're writing right there in line but now you have more flexibility to to edit it and you have your you have your editor and and all the tools that come along with that um so this kind of gives you like a a lightweight way to test as you go right uh and then there's this idea of uh rubber duck debugging where all familiar um you might see how that comes naturally when you're uh when you're rubber duct programming or or to say you know you're speaking to someone as as your live coding right and um that that that same kind of idea so when you're when you're writing all of this into kind of a worksheet from scratch and then going very iteratively and explaining as you go the worksheet makes it easy for you to be uh very iterative here and you pick up some of the benefits of of rubber ducking where like you would um you would catch on hopefully I mean there's some there are some cases where where you don't it ites takes a little bit of like thoughtfulness as well but you you catch you if you're explaining what you're doing to yourself or anyone all you're catching on to these problems um and and then of course there's the idea of of literate programming uh from from Donald k um which is that uh you know this is this programs interpers with text uh you know sort programs as literature something you would read and it would be uh a lot more instructive um but you know what canth found is also that the process of of of writing this helps understand and now you you can certainly you worksheets are great for literate programming you could do that um in the context of of like a live coding demonstration the the the literate part is is is your speech uh so um so you know this this whole idea of like programming with a worksheet or you know live coding with a worksheet reminded me of all these ideas and seeing some of some of these all same benefits um yeah I I had this idea of a of a whiteboard it's you know it's it's kind of like an a ideal whiteboard here in that you know you you have you have an ability to use it for demonstrations but also um write ideas down um okay so we're going to do a little bit of a demonstration and and show how these uh how you know these these worksheets work and let's see I didn't have it pulled up uh 2022 day what is this 12 okay so I'm I pulled up a problem here let me make it a little bit bigger and there there's a lot of flavor text in here but but the basic idea is that you're you're given you're given a map and you're given um a a height so this is a grid map with a height elevations of um various points on the map and you have you have a start prision and you have an end goal and your goal is to hike up to this peak here that this e in as few steps as possible but now there are some rules here you can't you can't climb very vertically so you can only go um up one level so for example here from s you have a b then you can go down to C because C is you know one level above B but you couldn't go up to Q you or are here right so this is a this is a simple simple enough problem and I'll say this this this could be done with a with a much larger problem what what I would like to do if if I had more time is to to lay out a much larger problem and then and show how each of these kind of um mistakes or debugging ideas can come into play but this we'll have to serve for today as as kind of like a a demonstration of the idea so here on the left we have um on on the right we have the the data set so you can see rough idea like it a lot of it's actually fairly flat and then over here we have what looks to be some sort of a mountain where we have a larger much larger letters here and you know different gradations um so let's start working on this so we have a grid so we we probably want points um so I mean first we could you know we could check that we've in the worksheet we check that we've um parsed that text file properly so now we have a vector of strings and we're just going to use that as a 2d grid of our of our map right um so if you have grids where we're traversing through this we we'll probably want points so we'll we'll make a case class here um and we we want a way to like check into this grid like so if we we have a point what we're doing with these points is like traversing through so we want a way to get um other adjacent points to it so we can just add that as as a definition in here so you know let's say um we had an up and that would be uh that would be a new point so we could just use a copy Constructor so um we give x and y = y + 1 um and because we're in a worksheet here we can do some sort of uh testing so point0 0 again this is like a trivial example but you know this this kind of thing you can do is as you're writing this you immediately you immediately test it so that U and you get the 01 okay um so we'll want that for like left and right so this becomes a mass here and then we have left and right and in this case these just become uh X's left would be minus one X would be plus one and again we could do like some sort of aent of of of a test here so like Point uh Z 0. u.r and you um and look so that looks like a bug uh so we can look into Maybe why that's wrong maybe let's just look at R see if we move to the right and it we're actually moving up here so the error here is that we copied copy pasted the Y's and we have X is here and you know of of course like there's a benefit of like testing testing early and often you catch this before it kind of is more confusing in the context later on right so we have those tests in there we we can just leave that and continue on um so we want to be able to find what we have like uh we have a starting spot and then we have um so we have to be able to find that we have to be able to compare the the elevation of of certain places so let's do that right now so def elevation given a point um and then we could just index into the grid so grid uh p.y and then p.x so let's let's look at our test data here and 0 here should be a point one one should be this B right over here let's make that oh we can't make it all bigger so so let's give that test and this test Point we've done so much just let's just give it a name um Val origin and then we can test on it repeatedly so elevation of origin is a and origin do down and again we have another error here so what's wrong this is probably let's read it it's it's an index out of bounds um so our our conception of down is kind of different from what we're expecting here um so what we could do is is uh invert all this right plus plus minus uh right actually we'll we'll keep that there and now we'll just use y as as you know positive indexes go down like in in uh graphic programming or like a canvas right um a do down is B great and if we go to the right we get B if we go to the right again we get C um and there I'm pretty confident that elevation works and I am using so what I'm returning here is just a character right so I I don't even need to translate this to a number I can do kind of this I can do a check like this so let's look at that a um um and let's look at the one to the right of it so this B and let's look at the elevation difference so um minus elevation uh origin dot or wait we we want we actually just want the origin or here we want the point to the right we want the point to the right minus the origin that should be one because that point is one higher than this so we know we can use this function here um okay so now let's look specifically at the the problem statement was a fewest possible STS required to move from your current position to the location that should get you the best signal okay so what I want to do with this how I want to approach this problem here is um kind of a a flood fill approach right so we'll we'll look at our starting point or starting set of points and we'll expand um from you adjacent pieces around there uh to places that are legal to go and and we we'll just keep doing that and it's a small problem that that should be an efficient enough approach uh it's at least worth a shot um okay so we have a we have a starting point um actually before before we do that I think we want uh we want ajent points so we want the the set of points that are adjacent to any given point and we probably want to filter for if they are inbounds so before you do that let's do an inbounds um I like to do that this way so let's make an X range so we have grid we'll just take the first element that head do indices and then we have a y range and that would just be the grid. indices and we can we can double check that so this is 0 until 81 on the X and you know we can see here in my editor that we are going to column 81 so I I'm I'm feeling comfortable uh comfortable about that and to check if a point is in bounds def in bounds um we can just say uh X range contains X and Y range that contains Y and again as as we're doing this we can we can add more mini tests in here right like you might be doing this because you're explaining it to explaining it to a friend or just trying to convince yourself that you know there there isn't an error here so again we can do um origin uh do inbounds uh we're getting an error here the return value of origin is uh null because actually origin we should Define up higher okay okay if we go origin and then we go up which should not be legal that should be out of bounds so so we have a test there okay so now we can get our adjacent um and we'll say uh set udl do filter inbounds uh do inbounds there we go and again we can test that so uh origin. adjacent and we get those two points and and that makes perfect sense because it's in the corner okay um so now we're searching for path and what we're going to do here let's have some sort of um next function so given given a set points So Def next um this is the set points we uh we just visited and then and we have kind of a current set of points so this might be like a an approach you might be familiar with um and in fact maybe maybe we don't do this right now I'm I'm jumping ahead because I know I'll probably go into this kind of a solution but let's just say this goes from a set points to a set of adjacent points um how am I on time 25 I have five minutes here there's a possibility that I skip to the completed version of this file uh but that's okay we're we're getting the idea here um so we would just take uh you know we take the visit points and then we map to adjacent and since this is a set of points this will get your your your set of adjacent points and now we want to prevent going into uh an endless endless loop right so we're going to rename these actually so this is now our current we're going to have a previous so we have another set points um and we'll just call it current filter not previous okay so this gets us everything in like an expanding ring around us um and now of course we want to test that this is a this is okay so let's let's say we had you know just one one over there um and maybe we call next on it twice or you know let's take a set of two points um so let's call next um let's actually start at the origin so previous is the set of just the origin and then next next would be um all the current points would be just the ones adjacent to origin or that add and again here this is actually a method and here uh we'll just do a dip against previous um not quite so if we map this it should still be uh oh this is a flat map we want we still want a single set right and then we see you know we're we're expanding here we have this line of three and of course those are all valid because we we don't have any High Cliffs here yet um and at this point I'm going to just go to sort of what this will look like here at the end and you know what you might do in in testing this along the way uh so what what I hadn't added here yet is an additional filter again using that elevation function um again this whole next thing can be its own function that we were writing and and you can test that separately right and then um if you're familiar with an unfold then this unfold here um Can can use that recursive function to to continuously like grow a set right and then it it it will return this lazy list a set of points that are the uh expending floodfill and our answer would just be to like search this lazy list of points until we get to the end here um anyway that is uh that is my time for today and I'll move on to questions thank you for [Applause] coming