Android Programming Course - Kotlin, Jetpack Compose UI, Graph Data Structures & Algorithms

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments
Captions
In this course, you will learn to create an Android app using the jetpack compose UI library. Along the way, you will learn about graph algorithms and data structures. Ryan MK teaches this course. He is a very experienced developer and instructor. What's up everybody? This is Ryan here, and I would like to welcome you to my tutorial series on the graph Sudoku application. This is an application I wrote primarily to refine my understanding of graph data structures and algorithms, and the new UI library on Android jetpack compose. In this part of the series, I will Overview The main goals and topics of the series and discuss a few design decisions which may come as a surprise to you. I will try to keep the public version of the project source code up to date. And it will be your responsibility to look at that source code if something becomes deprecated or stops working. The format of this series is a code along style, which implies that the best way to learn is to write the code with me as I explain it. For advanced developers, the full source is available for direct learning, but you can watch the videos to clear up any holes in your knowledge. I use some fairly advanced features of the kotlin language and the timeless principles of software architecture, so you might learn a thing or two. For beginners, it is very important that you follow along with me in code but at your own pace. You might not feel like you're making progress at first, but understand that you will be practicing the skill of writing code even if you don't yet understand what you're writing. I will also secretly be teaching you how to write code which is easy to write, read, fix, improve and test. But instead of asking you to memorize the timeless principles of software design, you will learn and use them in practice as we build this application. There are four general topics that This tutorial will demonstrate graph data structures and algorithms jetpack compose clean UI architectures, and kotlin language features. We will explore the topic of directed colored graphs and my experiments in writing algorithms to generate solve and unsolved n sized Sudoku puzzles. We will build the entire user interface using jetpack compose, which allows us to create our UI entirely in kotlin. As opposed to XML views and styles. I will show you how to wire up a simple app using principles commonly expounded in solid and clean architectures. However, I teach these topics in my own way, so do not expect a bunch of jargon or over engineering. I will also demonstrate how and when to use basic and advanced features of this beautiful programming language. This part of the video is intended more for intermediate and advanced developers. Understanding this design decision is not required to complete the tutorial. Throughout this tutorial, you will notice that apart from compose and proto data store, I use almost no libraries from Android jetpack In fact, very few third party libraries in general, by relying on kotlin and Java standard libraries and the Android SDK, my code becomes more resistant to deprecations and changes in libraries. This is because the Android SDK, and the standard libraries tend to change less frequently than third party libraries, such as those you see an Android jetpack. It also means that some things which libraries like jetpack viewmodel, jetpack, navigation or help might handle must be hand written by us. I actually like that, but you might have a different value system. And my goal here is not to discourage you from learning these tools if you're interested in them. With that being said, you might be surprised at how easy it is to write your own viewmodel navigation or dependency injection code without them in a small app like this one. This application uses Model View whatever architecture, which is my way of saying that I don't follow anyone else's style. Having studied this topic for many years, I let the project requirements in my understanding of the principles of good software design guide my architecture. In this case, I find that compose is made for an MVVM based approach, but I added a presentation logic class for a specific reason. This reason is called passive view or humble object. Instead of having the view or the view model manage the control flow of each screen, I pulled that logic into a separate class. This class is super easy to write and test because it has no third party dependencies. And it prevents my view model from becoming an ugly God object. You should try it sometime. I designed this architecture simply by applying the single most important principle of software architecture, separation of concerns. That's it for this part of the series. Now we begin coding. The domain package represents two things, the most general pieces of information, such as data classes, constants, and enough Which the program must virtually represent. Also, the most general things this program must do, which the program represents using functions and interfaces. In essence, it is the foundation of any new program I rate and I use a repeatable process to design my domain package or module. For a clear and simple introduction to that process. Check out this video on my channel, how to design information systems and applications. That video is a recording of a talk I gave to some software engineers in Egypt about that particular topic. Anyways, most of the code in this package is simple, but it does include a design pattern, which I will introduce now. This package contains several interfaces, which are used to employ the repository design pattern. This pattern is also known as the facade pattern. And the general goal of the pattern is simpler than its technical definition. The technical definition of the facade or repository pattern is to hide the details of a subsystem, in this case, data storage mechanisms behind an abstraction, in this case, an interface. Let's look at a practical example. To make sense out of that definition, our presentation logic classes will hold references to these repository interfaces, instead of the classes which implement the interfaces. This gives several benefits to our presentation logic classes. They can be built independently of each other without causing a compiler error, they can be tested with a fake implementation of the interface without requiring us to change any code within the presentation logic class. Also, if we decide to use a different implementation of the interface, such as switching from file storage to a room database, we can also do that without requiring any changes to the presentation logic class. These benefits are a result of building software systems, which are loosely coupled. And the repository or facade pattern is an easy way to promote loose coupling. In fact, interfaces in general tend to promote loose coupling. Now don't feel the need to use this pattern everywhere. A good general rule is to use them in significant architectural boundaries. In this case, I'm using them as a boundary between the front end and the back end of this application. To start things off, right click on the domain package, go to New kotlin file and create a file called difficulty. And that's going to be an enum class. enum classes in kotlin, and Java and various other languages are useful for creating a restricted set of values. As we'll see later on, you can use sealed classes in kotlin to create a restricted set of types. In any case, the main benefit outside of just creating that set of restricted values is that enums can greatly improve the legibility of your program. As we'll see in a moment, let's add in our enum entries. quite obviously, this enum will represent the difficulty of a given Sudoku puzzle. However, we need to add one more thing before moving on, we will actually be using some values for each of these entries in the algorithms to basically dictate the difficulty of the Sudoku puzzle. So in order to add a value to an enum in kotlin, we need to give it a property or some properties. As you can see, our entries are now read, so obviously, we need to give them some doubles. And that's everything we need to do here. Right click on the main package, go to New kotlin file for class. And we're going to create a data class called settings. settings is our first data model, as I like to call it or a plain old kotlin object. And as we'll see in a moment, it will contain both the difficulty and the boundary, which is the size of the Sudoku puzzle. So a four by four Sudoku puzzle will have a boundary of four, a nine by nine will have a boundary of nine. The data keyword when put ahead of a class keyword basically adds or generates a couple of helper methods, such as equals hash code or copy. We'll definitely be making use of copy later on maybe not in this class, but in some of them and others. certain point, we will also make use of the generated hash code function. Anyways, this is a really simple class, we're just going to add two properties to it. And that's it. Right click on the domain package, go to New kotlin class or file. And this time, we're going to create a class called user statistics. And that's going to be a data class. Now, the purpose of this class is to represent the user's shortest slash best times for solving any particular difficulty or size of Sudoku puzzle. So we're basically just going to add a whole bunch of properties that are pretty much the same. Now, one thing you can do in IntelliJ IDEA, or Android Studio is you can just click there and then hit Ctrl D, however many times you need and that will copy to a new line. That's basically it for this class. Now, you might be wondering, why are we using long here, we're actually storing the time it takes for the user to complete a particular game in milliseconds. So that's why we want the long integer value. Again, right click on the domain package, go to New kotlin filer class, and this is going to be a data class named Sudoku note. Now, this is where things start to get a little more complicated and interesting with our data models. So what I'm doing here is I'm representing an individual node in a graph data structure, we're going to talk a lot more about graph data structures later on when we get to the part of the tutorial dedicated to it. But just to give you an idea, so we are actually going to be building a directed colored graph. And an important thing here to note is that in this particular case, this term color really just refers to a number, it's just a value we associate in some kind of node. And again, to give you a preview ahead, when I say graph data structure, a better name for it would be a network data structure, because that's essentially what it is. It's a collection of nodes, and edges, which are essentially like lines between the nodes relationships between the nodes. Anyways, this particular node structure in our data structure is going to have a color or a value, which is just an integer from one through nine or one to four, also, including 00 represents like an empty Sudoku tile, but that's more concern of the front end. These notes will also include an X and Y coordinate, so the top left will be x zero y zero, the bottom right will be x eight, y eight, and we're going to be using Zero Based indexing. So instead of starting from x one to x nine, we just basically subtract that by one. So that's it for that preamble, let's get started writing the code. So we'll start with the x and y values. Next, we will add the color which will be a variable because it can change throughout the course of execution. Then we will add a Boolean called read only and I'll explain what that is after we write it. Now, the purpose of the read only Boolean here is quite simple. When we essentially generate and then unsolved a Sudoku puzzle, which is another way of saying we create a new Sudoku puzzle then remove a certain number of clues to make the game actually playable and fun. Some of those numbers on the Sudoku board or in the Sudoku graph data structure will be read only those are like the given clues that the user is not supposed to be able to change themselves. As we'll see later on. This will also affect the user interface because we will draw the read only Sudoku nodes or tiles differently than the ones which the user can edit. Now, we're not quite done yet, we need to override the hash code function which was provided by the data class keyword as I discussed earlier, and then we also need to add a function to get a hash code. Okay, so hash code will have a default implementation, which is based on the values provided up here in the different properties, we're actually just going to do something different. So we're going to type get hash, like that. And this is actually a function that we are going to create also, we'll add in two parameters here for x and y. Okay, we're now going to add the get hash function, and it's going to be top level, which means it sits outside the brackets of our Sudoku node class. Okay, let's just implement this function, and then I'll explain what we're doing here. Okay, so let me start by explaining what exactly a hash code or hash value is. So it's essentially some kind of generated key or unique identifier based on some kind of algorithm. In this case, I have a very simple algorithm, all I do is multiply the x value by 100. And I leave the y value alone. And I basically just combine those two values together into an integer. Now, the reason why I multiply x by 100, is if I didn't do that in a nine by nine Sudoku puzzle, there would be certain edge cases where the even though the X and Y value are technically different, the resulting hash code would not be unique for several different nodes. Simply put, I'm multiplying by 100 to make the hash codes unique for every individual tile in the Sudoku puzzle. As for why we're using hash code, in general, I'll try and keep it fairly straightforward. Basically, we're going to be storing each node in the graph in a linked hash map. So the hash values will represent the key for that hash map. A hash map has key value pairs, in case you're not aware it, we'll be seeing that in a moment. But this turns out to be really useful because our user interface as well will be representing things in that kind of X and Y coordinate style. So just take my word for it. Hash codes are pretty handy in situations where you have a large number of elements, and you don't necessarily want to have to maintain a reference for every individual element. Instead, we can just retrieve a reference by getting a hash code. Oh, and before we go, we need to add one more thing here, we're going to make this thing implement serializable. Now essentially, what this does is it allows us to read and write our Sudoku nodes and also the whole puzzle to a file. Since we're only going to be storing one puzzle at a time, I didn't really want to use something like a database, it kind of just made more sense to use the file system, and serializable and makes it easier to do that essentially. Okay, we have one final data model to create in this particular package again, right click New kotlin file our class, this one's going to be called Sudoku puzzle. And again, it's going to be a data class. A good way to think of data models, as I like to call them is that they are virtual representations of a real world object, in this case, a Sudoku puzzle. The way that I initially designed this class is by asking critical questions about what constitutes a Sudoku puzzle. Things like the boundaries, so are there four tiles per row or column or are there nine tiles for example, we have the difficulty. And most importantly, we have the graph data structure itself. There's also the elapsed time which the user has taken to solve a particular puzzle. So let's go ahead and add those properties in and then I'll explain some of them the ones that need to be explained afterwards. Also, before I forget, let's add in the serializable implementation here. Okay, so you're probably wondering what build new Sudoku is. So what we'll be doing is we're actually going to be calling a large series of top level functions, which will form all of our different algorithms, which are necessary to build and generate a new Sudoku puzzle, based on a given size, which is what boundary represents and a given difficulty. Also, if you're wondering about what's going on with the linked hash map, which is full of linked lists, that's kind of a way of representing an adjacency list. Again, I'm going to go into those details on graph data structures and different ways you can represent them, or at least how I represent them in this particular application later when we get to that particular package and topic. But for the time being understand this represents our virtual Sudoku puzzle, the last thing we're going to do is just add in a small little method, which just makes it a little more obvious and legible how to get ahold of the graph itself, at least in my opinion. And we're going to use single expression syntax. So I'm just going to type equals graph. Let's create a new interface called I game repository. I like to use this naming convention of putting a capital I in front of the interfaces. And then as we'll see later on, in the persistence package, I will add a suffix of I MPL, which stands for implementation to naturally the classes which implement this interface. When designing a small to medium scale application, one thing you can do is you can actually conceptually think of the functions in your repository interfaces. As use cases themselves, the things we're going to be writing here are going to be called like save game update game update node, which is very similar if you're doing like a user stories in the use cases type application design. So I just wanted to throw that in there. In a more complicated application, where I needed to do more coordination of multiple different data sources and repositories, I probably would have like an interactor, or a use case, as it's commonly talked about, between Martin Fowler or Robert Martin, Uncle Bob. But in this particular case, in simpler applications, generally speaking, the use case as a class itself, is typically an unnecessary extra layer of abstraction. So with here, we're just going with our presenter, or view model or whatever, talking directly to a repository. And that is a sufficient amount of abstraction for an application of this size. Now, how an interface works is that it's very similar to a class except as we'll see, in a moment, we're not actually allowed to implement or give a body to the functions that we'll be writing, we just write what are commonly called either abstract functions or functions stubs. Now there's two important points here. Firstly, the suspend keyword is applied there, because these functions will actually be called from co routine scopes, which exists in the logic class or the presenter that will be referencing this particular interface. So that's all we need to do to establish concurrency for now. Now, in case you're not familiar, what I'm using here is what's known as a function type. And so what we'll do is we will be actually passing in a reference to two functions which exist in the logic class the presentation logic will pass those functions in. And then in the repository implementations the things which implement this particular interface, that is how they will call back with some kind of result, either a successful result or a failure. Now you might be wondering, why do we have unit and then it returns unit which is what that arrow means, in this particular case? This is something we kind of have to do in order for the kotlin compiler to understand exactly what we're telling it to do. So this would be kind of equivalent to passing in void or like basically nothing into this particular function, and then returning nothing from that particular function. But what it will do is it will signal something like an oncomplete if you have any experience with RX Java, where basically we just want to resume the application successfully when this function is called. But this particular function does not actually need to return anything. Later on, we'll see some examples of when we actually need to return a value through our on success function type. Again, you might be wondering what is the difference between saving a game and updating a game? Well, essentially, in the update game function, we're going to be wholesale writing an entire Sudoku puzzle, which includes an elapsed time, although there are some situations where all we really need to do is simply update the elapsed time of the game, such as when the user navigates away from the application. So what I'm doing here is I'm creating sort of specialized functions depending on what we want to achieve from the user's point of view. Now I'm going to demonstrate when we actually want to return a value from these particular function types. Okay, so for onsuccess, what we're effectively saying here is that this particular function must be called with some kind of Boolean value, obviously, either true or false when it's called in the implementation of this particular suspending function. Now, basically, what we're doing here is when the user updates a single node or tile in a Sudoku puzzle, there's a possibility that that might be the final tile in the puzzle. And in that particular case, assuming the puzzle is correct, and the user has inputted, the final tile, that would signal that the gain is complete. So it might be a little bit confusing here. But onsuccess does not necessarily mean that the game itself has been completed. So that's why I'm differentiating there. Okay, now, in this particular case, what we're doing is when the user returns to an active game, we obviously want to get a current game. And there is actually an edge case where the user completes the game, navigates away from the application, and then restarts the application. And so that's why we're still passing in that is complete flag. Here we're going to return obviously, a settings object. Let's create another interface. And it's going to be called I gain, data storage. And that's obviously an interface. Now, before we write the interface itself, we're going to do something a little bit different. We are going to create a result wrapper or Well, let's just say it's inspired by an either mon ad from functional programmers, but no one really cares what functional programmers think or talk about anyways. Seal classes are truly one of my favorite simple features of the kotlin programming language. It allows us to create In a restricted set of types, and those types can contain particular values, and visca. What this will do And as we'll see in a moment is it allows us to return an object from a particular function have I gained data storage, and this particular object is capable of representing multiple different states. So like I showed you before in AI game repository, here, we're representing an error state and a success state as two separate function references. In this example, we're going to be representing both of those states through a single object. Now, one final point, before we move on, if you have, for example, some kind of situation where you want to represent just a success case, so equivalent to just returning unit in onsuccess, what you can do is you can actually just use an object so you could say like object on complete, etc. But we don't actually do the that in this application. So you don't need to add that in. Now, let's finish off the interface. Create another interface called I settings storage. Now, we're also going to use result wrappers here. So I'm actually going to just copy and paste this over. And we're just going to rename a few things. Okay, and now we can write the interface. One more interface to go for this package. This one is going to be called pi statistics if I can spell it repository, and obviously, it's going to be an interface. Now one final point, again, is record is going to actually affect something in the user interface based on whether or not a statistic that gets updated is a record ie the shortest possible time of completion for a particular boundary or size of Sudoku puzzle, and a particular difficulty. The common package contains code which is reused in a variety of different classes and functions. In this part of the tutorial, we will learn about many different kotlin language features, which are designed for sharing code in an intelligent and efficient way. Topics covered include extension functions and problem These abstract classes, the open closed principle, object, Singleton, and co routine dispatchers. Before we write the code, let's talk about the open closed principle. The OCP is a relatively confusing concept, but I will try to explain it in the clearest way i can to give you my own verbal definition, which we'll break down later. Any commonly reused software entity, which is expected to change should have a fixed public interface, and a way to change its implementation. In order for that particular definition to make sense, there's a couple things that I need to unpack. Firstly, when I say software entity, I'm generally speaking about a class or a function, but it could be a few other things. So let's examine what I mean by public interface and why I argue that it should be fixed if it's commonly reused. By public interface, I am not speaking of a Java or kotlin interface specifically, instead, I mean any publicly visible aspect of a class or a function. Since this is an Android tutorial, let us take the example of the activity class. An activity fits my requirement of being commonly reused and expected to change over time. So it is a perfect case to think about the OCP. Every subclass of activity must include the onCreate function, which is a part of the public interface, which it makes available to classes which reference it. The reason why we want this public interface not to change is very simple. Suppose that the Android platform developers suddenly decided to deprecate and remove saved instance, state bundles from all lifecycle functions. Because this public interface is used by pretty much every Android program around this platform update would break everyone's code. What I mean specifically is that all activity subclasses in all code bases, which have not removed this parameter would not be able to compile. So this is why I'm talking specifically about commonly reused software entities like activity, and why it is important that their public interfaces change as little as possible. Since we've established why fixed public interfaces are really important. The next question is simple. How do we then provide a mechanism or way for the implementation of the public interface to change? Well, it turns out the kotlin gives you many options to solve this problem. Rather than explain them all, verbally, I will teach you how to use them in code. As we build this application, right click on the common package, and go to new Colin filer class. And this is actually going to be an abstract class which they don't give an option for here. So what we're going to do is type in base logic, we will add in the abstract keyword. Unfortunately, I don't have the time to explain the difference between an abstract class and interface in plain old inheritance. In this particular course, this is something I go into and explained very clearly in my other video courses. But what I will do is explain why we're using an abstract class here instead of an interface. The reason why we would want to use an abstract class is for situations when we want to share behavior. So for example, we'll be writing a function stub or abstract function, which I want to be shared across any class, which inherits from base logic. And I also want to share a variable, but this particular variable will have to be protected as opposed to public. And if we were to try and do this using an interface, then necessarily that particular value would be public, we're also going to use a generic type. So I'll show you how to do that. So the syntax for a generic type is to just use angle brackets. And then you could take quite literally whatever you wanted between those angle brackets. But my suggestion to you is to not use something which is already used, hence why I'm using this all capitals event. Now, if it doesn't make sense what we're doing here, it will make more sense when we write the classes which inherit from base logic. Let's go ahead and finish this off. To briefly explain the intent of this abstract class. Basically, I'm saying that I want a set of classes, the ones which will inherit from base logic, all of which will have this function on event. In other words, these classes will handle events from the user interface. And then as we'll see, we're going to use this job object which comes from the coroutines API as a way to Cancel child co routines. And also to make each of these logic classes as its own co routine scope. I'll explain that when we get to that particular part of the tutorial, right click on the common package and create a new kotlin file, which is just going to be a plain old file, and it's going to be called extensions. gotlands extension functions and extension properties are among my favorite features of the language as a whole. Without getting too technical here, extensions allow you to employ the open closed principle, which states that software entities should be open for extension, but closed for modification. If that doesn't make sense, don't worry about it is kind of a confusing definition. But it allows us to add new functionality to existing source code without having to modify the original source code. Now, this particular file extensions.kt is kind of like a replacement for static utilities that we might have used in Java or something like that. It's really just a place where you stick utility code which is used across the application. Let's write our first extension function to see how this works. The purpose of this particular extension function, obviously it will be used within activities is really just syntactic sugar, its way to make it so that I don't have to type out toast dot make text and supply this message toast dot length long and dot show. Instead, in the activity where we'll be using activities, I should say where we'll be using this particular extension function, we can just type make toast, give it whatever string we want to display, and it's handled like that. By making it an extension function of the activity class, I can use it seamlessly in any activity. Let's write another much uglier utility extension function. The purpose of this ugly little function here is to take the elapsed time of the given puzzle which the user is currently working on, and to attempt to convert it into a value based on minutes and seconds or a string to display based on minutes and seconds. Now, if it takes the user longer than an hour, then we end up just displaying like a generic more than 5959. Now if you think this code is ugly, in kotlin, I challenge you to write it in Java. Now for beginners, this might not make sense intuitively, but it's important to understand what this is referring to. This is actually referring to the long object, which we will be calling dot two time on. That might make a little bit more sense when we actually get to using this particular extension function. There's only one more extension, we need to add, and it's actually going to be an extension property this time. So what I'm doing here is I'm hitting alt, enter on this particular red thing, and then I'm going to hit Add remaining branches. going to hit alt enter, again, to import our, these are obviously string resources. That's one thing, we're not going to be writing by hand. So hopefully, what you've done is you've gone and grabbed the source code for the starting point, which includes things like string resources, right click on the common package again, and we're going to create a new kotlin interface, which is going to be called dispatcher provider. This interface is very small, what we'll do is we'll write the code and then I'll briefly explain what it does. Now, unfortunately, I can't briefly explain what a co routine context is. But I can't explain the purpose of this particular class and how we're going to be using these co routine contexts. So in most situations, most of the work that we're going to be doing within co routines land is going to take place on the main thread or the UI thread. Now, with that being said, there are a few operations like writing to a file, which we don't actually want to occur on the main thread. And that would be a situation where we're going to provide the IO context. Now, the actual purpose of this particular interface is really key here. What we're going to be doing is that if we wanted to hypothetically test any class, which needs to use these co routine contexts, in a JVM environment, so not an actual running application, then what we could do is we could return a particular kind of CO routine context, which allows us to test in that particular environment. I know that's a lot of technical detail, but I can't really make it a whole lot simpler than that. However, by using this interface here, when we want to use our co routines in the production environment, we can provide the real UI main thread context for the front end, and then we can provide a real dispatcher for the IO thread. To make that even simpler, we're really just making the code easier to test. Right click on the common package, go to New kotlin file or class, this time, it's going to be an object. And hopefully I can spell this right production dispatcher provider. Again, what we'll do is we'll write the code here and then I'll explain how it works afterwards. I'm going to hit alt Enter again. And this is where we will return the actual dispatchers that we'll be using in production as per the name of this particular object. Now there's a number of reasons why I'm using the object keyword here. So basically objects in kotlin are in this particular case Singleton's. So that basically means that we will only ever have one of these production dispatcher, a provider software thingies floating around in memory space at one particular time. They're also thread safe, which is important because although co routine is not necessarily a thread, our dispatchers dot main and dispatchers.io has something to do with threading. And the other thing that an object can do is it can actually inherit from an interface. Now we're not actually going to be writing any unit tests in this particular application, which require the dispatchers but just to show you What you would do if you wanted to unit test some class which needs to use these co routine context, what you can do is you can just instead return dispatchers dot unconfined, and then you would return that for both the IO context and the UI context. And then that is what you would use in like a JVM j unit test environment. The persistence package contains classes and functions, which have the role of persisting or storing data beyond the lifecycle of an Android process. If you don't know what a process is, it simply means a program which is running on a device. Practically speaking, we will store the progress which the user has made in the current Sudoku game, as well as the settings for that game, and the user's personal records or statistics, as I call them. Here's a quick look at the architecture of the persistence package. The game repository in this situation functions as a back end decision maker for the two data sources, which coordinates the data sources themselves. Just try to carry out CRUD operations, create, read, update, delete, and either report with a success or a failure if an exception is thrown. The general principle here is to keep things together, which makes sense to be kept together to separate what doesn't need to be kept together, and to also use an abstraction or an interface. In any place where the implementation might change, I might decide to stop using the local file storage or proto data store. So hiding these details from the repository is not over engineering, but rather a calculated decision. Speaking of data sources or storage mechanisms, we will use two different mechanisms for storing our data. Firstly, we will store the user's preferred Game Settings and their personal statistics in protro data store data store provides a lightweight and efficient way to store this kind of data using protocol buffers. Protocol Buffers is a serialization language similar to JSON. However, I find it easier to read than JSON. And fortunately, the library we will use also comes with its own protobuf compiler that will generate some of the boilerplate code which we would otherwise need to write ourselves. We also use the device's file storage to store the progress of the user in the currently active game. Every Android app is given some memory space to store files, which is what we will use. This is done by making all of the domain models implement serializable. And using Java as input and output streams to read and write objects from kotlin language. So in case you aren't following along with the tutorial, and you haven't downloaded the starting point repository, what you're going to want to do is you're going to want to add a directory called pro tau in the main source set, the starting point repository should already have that directory. So just go ahead and right click on it, and go to new file. And this file is going to be called gain underscore settings, dot proto, and make sure it's all lowercase. Go ahead and type this in the top of the file. So protocol buffers are essentially like a serialization language. It's very similar to JSON. If you want to look more into it, you can about what the benefits and the pros and cons of using something like JSON. But personally, this being the only project that I've used Protocol Buffers in so far, I'm quite happy with it. Okay, so let's just add two more lines. And I'll explain some more from there. Okay, so we'll talk a little bit more about this in a moment. But basically, what's going to happen here is, we're going to define this protocol buffer message, as it's called, which is kind of like a data type for lack of a better term. And what we can do is, so this file will be consumed by something called the protocol buffer compiler. And in this case, what we're basically telling it is that we're going to be generating Java files. Now in the generated class files. The protocol buffer compiler is going to basically add whatever we put in the Java package as the package for the generated Java class file. It's just useful to not mix up your namespaces and stuff like that. And as for the second option, here, Java, multiple files. If you don't have that turned on, then what can happen is that basically, the generated Java files will all be in one single file. We don't really want that, although I'm not sure if it's absolutely integral to getting this application to work. Like I say, we're going to go through this pretty practically and I'm not an expert in protocol buffers. Okay, now, we're going to do Line a message which is kind of like one of the main data types for lack of a better term in this particular language. Okay, so let's talk about what we just did here. So we've defined a message, which in Protocol Buffers is kind of like a data type or a collection of fields. And we've done two things. So within the game settings message, we have a 32 bit integers, like a kind of a smaller integer to represent the boundary of a Sudoku puzzle. So when I say boundary, I mean like a four by four Sudoku puzzle will have a boundary of four, a nine by nine Sudoku puzzle will have a boundary of nine, obviously. And the other thing we did here is we defined an enum in protocol buffers. Now when you're creating these enums, you'll need like a default value unknown. And then you've got the other values that the enum can potentially be. Also notice how in boundary and difficulty the fields above the enum I'm giving it default values, naturally, those will be like the values that the protocol buffer gets pre loaded with, like the first time you access it. Now, the important thing to understand here is that assuming you've added the support for Protocol Buffers into your build Gradle configuration, the proto buffer compiler is going to actually generate some Java files or classes out of this particular message. Okay, so what I'm doing here is I've opened up the completed project, and I'm just having a look at the file which was generated by the protocol buffer compiler. And all I really want you to notice here is that when you're using proto data store, what's going to happen is it's actually going to generate a Java class for you. Obviously, you can see we have our gain settings in camel case, which is what we defined as our message. And then we also have that enum defined below. So what does this actually do for us, basically, this is going to allow us to serialize or basically translate from Java into the protocol buffer language and vice versa. And it also means that we don't actually have to create our own plain old Java object in order to do that. The library is going to generate that for us. But we can still use it in our code, which we'll do in a moment, we're going to add one more proto file. So go ahead and open up the protobuf directory, right click again, go to file. And this one's going to be called user statistics dot Proto. Alright, so I've just copied and pasted the first three lines from the other protocol because we'll be reusing them. And we are going to create another message here. Now when I say statistics, this is kind of like my way of talking about the user's personal records. So what are the shortest times to completion that a user has made in solving a particular size and difficulty in a particular Sudoku puzzle? It's pretty straightforward. So let's just write it out. And there you have it. Now, you might be wondering why I'm using 64 bit integers here. So these actual values are going to be stored in milliseconds, which is why I do want the 64 bit integer storage there instead of the 32 bit integer. I'm not actually 100% sure if that's necessary, but I did that just to be safe, and realistically, it's not really going to eat up that much extra memory. Okay, so that's it for our protocol buffer files. Now, we're going to have to create some protocol buffer data stores, which is how we're actually going to create and access our protocol buffers. Go ahead and right click on the persistence package, go to New kotlin file or class and this is just going to be a file called data stores. Okay, so before proceeding, you're going to want to go to build and make project. Now the build will probably fail, but all we really wanted to do is to generate the appropriate Java class out of the protocol buffer. But if for some reason that doesn't work for you, just follow along, and eventually it will work. Okay, so for each protocol buffer based data source, we're going to need to provide a way to get ahold of it or create it from context, then the other thing we'll need is a serializer. Go ahead and import everything. And there's two things we need to add into the delegate here. Okay, so don't worry that it's showing up red will actually write this serializer. Next, so I just wanted to explain what's going on here. So we're creating a data store object, and it takes the protocol buffer generated Java class, which is called Game Settings. And essentially, what this does is it creates a reference which which we can use to either store or retrieve our protocol buffer. Now, you might be wondering what game underscore setting.pb is, and why it has a different file extension than our proto files, to the best of my understanding game underscore settings. PB is something that's generated after the fact by the compiler, whereas the profile is something we write for the compiler to consume. But in case I'm wrong on that, then feel free to flame me on Twitter. The other thing we'll need is a serializer, which takes care of serialization quite obviously. After that, you can just click here, hit alt insert, override methods, and we only need the methods from the serializer interface. So again, let's read the code and then I'll explain what I need to explain after the fact. Okay, so I'm going to keep the details here pretty light. So obviously, when we create our data store, it's given the game setting serializer here. And what the serializer does is it helps us to read and write from input streams. So in other words, we're going to be obviously reading from a protocol buffer file, and then that's going to be serialized, or rather D serialized into Java, and vice versa. So basically, what the Android team has done for us here is they've made it a lot easier to handle things like error handling and dealing with input streams. Because if you've ever worked with input streams in Java, then you can tell there's, you know, you're probably familiar with a lot of boilerplate code to do with that. So basically, we do a little bit of boilerplate work here. And it translates to a very simple API, when we actually want to read and write with this particular tool in the back end, which we'll be doing in a moment. Okay, now, obviously, we need to write another data store and also serializer for the other data type. So this is going to be one of those rare scenarios where I do actually just copy and paste because there's absolutely nothing new, we're just going to change a couple of the words. So this would be one of the points where I encourage you to have the complete source code open on the side and then that way, you can do a little bit of copy paste action, like I'm going to do now. And that is our data stores file complete. Now obviously, if you had a whole bunch of these, you'd probably want to use separate files, but since I only have Have the two I just decided to stick them in the same file, right click on the persistence package and go to New kotlin class. This one's going to be called local game storage ample. So firstly, we're going to make a constant which will represent the name of the text file that we will be reading and writing the game data to. Next, we'll create the constructor. So you might be wondering where file storage directory comes from. When we create the build logic of this application, which is kind of like my inversion of control dependency injection type stuff, what's going to happen is we're going to call this one function to the Android system, which will return us the specific directory from the system where we can read and write things like files. Let's go ahead and implement the interface. Now, I'm going to try to get through this relatively quickly. But one thing I want to explain is that you'll notice I'm making fairly extensive usage of helper functions. The reason for that is just to avoid writing redundant code. Also, as with the other implementations, we're going to be using the width context co routine builder to do this kind of IO work off of the main thread. So what we'll do is we'll call a helper function called update game data, and we'll pass it in the game data. And if that operation happens to be successful, then we'll actually just return the same game object that was passed in because it should be consistent. Okay, now we can create the helper. So here, we're going to throw the exception so that it'll actually get picked up by the catch block in the functions that we'll be calling this helper. Now, we're going to be using input and output streams, which are part of the Java standard library in order to rate our data to and from the file. If you're wondering kind of what this word stream means, ultimately, what we're actually doing kind of at the low level, is we're going to take our game or Sudoku puzzle object, and we're going to serialize it into basically a stream or a very long sequence of textual characters. And that's what we'll actually be reading and writing from the file. Okay, so two points, you always want to close your streams. Also, you might be wondering, how is it that we can say dot write object and pass in our Sudoku puzzle, but let's just check the parameters here. So I'm going to hit Ctrl p within the parameter brackets, and as you can see, it accepts any type. Now the important thing is that if our different classes like Sudoku puzzle and Sudoku node did not extend serializable than we wouldn't be able to do this without errors. So for update node, it's a little bit different, we're just updating one individual node. So how this is going to work is we're going to get the old data and then we're just going to update that individual node. And then we will rewrite the result back to storage. So get game will be another helper, we write, and what I'm going to do is I'm actually going to write that one right away. Otherwise, the autocomplete and error handling stuff will be all over the place. Okay, that's what we need to do there. Now, just a quick reminder here, when we say color, and really, whenever anyone talks about a color in a graph data structure, they're really just talking about a number. So in this case, the number represents the actual value placed in a particular Sudoku square. So it'll be like something from one through nine, or one through four, depending on the boundary of the Sudoku will also update the elapsed time. After it's updated, we will write that result to storage hopefully. And just to keep the front end synchronized with everything else, then we will return that same game object. Now it has just come to my attention that I have forgotten to add a particular integer called color to this particular function when I wrote it, so let's just go ahead and fix that now. There we go. And I managed to save the easiest for last. And that's it for this file. Right click on the persistence package, go to New kotlin class, this one's going to be called game repository info. So in case you jumped ahead, and you aren't actually familiar with the repository pattern, I actually already explained that in part two of this series where I built the domain package. In any case, let me just reiterate, reiterate what the purpose of this particular classes, it's basically like a bridge and decision maker for the backend. Now sometimes you'll have multiple different repositories or datasets. In the back end, and it might be a good idea to keep them separate. The reason why I didn't in this particular case is because the game storage and the settings storage are actually inextricably linked. They are by nature closely related. So based on that, and the fact that this isn't actually a very large application, I chose to put them together within this repository. And then how it will work is that the repository will coordinate these two different data sources. Let's start with the constructor and the repository interface. Okay, so as you can see, we have our work cut out for us. So what I'm going to do is I'm going to try to write the code relatively quickly. And after it's written, I'll explain what it does. So there shouldn't be anything new in this particular function, except for the fact that we're making an assignment statement within a control statement, Val current game result equals etc. We're allowed to do that because kotlin is a beautiful and idiomatic language. This one's actually pretty simple. You know, for the life of me, I don't understand why it keeps putting on air on top. I'll explain this function in a moment. So puzzle is complete is actually a function which exists in the computation logic package, which we'll be writing later on, of course, and all it does is exactly what it says. But it will return either a true or a false based on whether the puzzle is complete or not. Hence is complete. Okay, so what I've done here is I've copied and pasted in the plain language use case which describes this particular function. Now, as you can see, it's pretty complicated to give a basic explanation of what's going on. And why did this when we request the current game, ie when the application starts up, there's a number of different things that could happen. So for starters, the user could have a currently active game and they just want to retrieve it. It could be the first run of the application, so no game currently exists in storage. And then there are different situations where errors could occur along the way. This is something that happens when you're coordinating multiple different data sources. Now I have my own system of tracking these different event streams, I use basically letters and numbers to denote steps and different potential event streams. But whatever you do, my suggestion to you is to write this down in plain language first and then go ahead writing the code. That's what I did this comment above you see here, I wrote that before I wrote the code. Anyways, let's get started. Okay, so for our first Event Stream, we attempt to retrieve the current game, and that returned successfully. And then we also want to know whether the current game is complete or not. We can just get rid of oncomplete. And here we go again. So this is obviously the case where the user has first loaded the application and we want to create a brand new game. And Looks like I'll have to do this manually this time. The autocomplete is not helping me here. But in fairness, we haven't written that function yet. Okay, I'm just gonna double check that I wrote that correctly. Now, before I want to move on, I want to explain one thing about my perspective on software architecture. While sometimes in a simpler application, we can do something like have the presenter coordinate different repositories or back end data sources. In this particular case, there was enough complicated back end logic that I wanted to have also a decision maker class, which happened to be this game repository imple on the back end, and part of the purpose of this class is to take care of the logic of coordinating these different back end data sources, so that I can keep the presentation logic class doing what it's supposed to do, managing presentation logic, and then I have this class dealing with this messy kind of almost business logic type stuff here. Anyways, we're not done yet. Okay, so it just occurred to me that I have missed a function in the interface of a game repository. So let's just go ahead and add that in. So what I'm going to do is I'm just going to copy update game, paste it down below. And what we're going to call this is create new game. And it's going to take in a settings object and that's it. So that's actually a helper function that I created mostly for legibility, let's just go ahead and add that in right now. Just another quick note here, you'll notice that I like incredibly long and descriptive names of everything that's going on. This is largely because I don't have a great memory for fine details. So by making these things super long and descriptive, I don't actually have to remember them, I can just read my code and pretty much understand what it does. Even in these complicated situations where we have all these different event streams and interactions occurring, okay, only two more short functions to go. And that's it for our back end. In the top level of the UI package, we have four small files, which we will use to create and apply styles, colors, fonts, and so on. One of those files is the global theme for our application. And I will show you how to create both a light and dark theme for the app in only a few extra lines of code. Stay tuned for the end of this section, as I will do a live demo of the different themes. Right click on the UI package and create a new kotlin file, which is going to be called color dot Katie. This file will essentially be a replacement for colors dot XML, if you're used to working with the old resources system, which was based in XML, let's create a color object. Make sure you import the Compose color class. Okay, so before we proceed, the most important thing to understand here is how to read these particular values. So the first two characters here 0x. This basically tells the compiler, which is the program that will be reading this code that this is in fact a hexadecimal number. The second two digits here indicates the alpha value as a percentage. Alpha is another way of saying transparency or how opaque something is. The remaining three pairs are the red, blue, and green or RGB values, again in a hexadecimal percentage, and that's pretty much all there is to know about these different color values. I've copied and pasted over the rest of the values because there's absolutely no point in either was typing all this out. But also keep in mind that they have some predefined values such as flack, for example, which you can also make use of right click on the UI package, and we're going to create another new kotlin file. And this one's going to be called shape. So in the old view system, when you wanted to do something like creating a background with rounded corners, or a button or widget or something like that, you had to create usually something inside of the drawable folder, which was XML based. Again, since this is compose, we can just go ahead and do that in kotlin instead. And we'll just use some default parameters. Now, this might be your first time seeing the.dp extension, let's just take a quick look at the source code. So as you can see, you can basically just append it to an integer double and various kinds of numbers. The important thing to understand here is that this basically tells the Compose framework that we want to use density independent pixels. If you want a more profound explanation of what exactly those are, I strongly suggest you look into it because it's a little bit complicated. Suffice it to say that the idea here is to allow the framework to create values for heights and widths and things like that would work across a variety of different screen sizes and form factors. Right click on the UI package, and we're going to create another kotlin file, this one is going to be called type. Now in case you're wondering, when we say type, we're not really talking about a type system, or anything to do with type theory, it has to do with type Pog, Rafi or text and how this text is styled or presented. So again, this is very much the kind of thing that we used to do and styles dot XML, we're basically going to create a bunch of different text styles, which will use throughout the application. And then we'll kind of see how to wrap those up in a typography object. And then we'll see how to add that typography object to our sort of global compose theme. First, let's create a text style. Sometimes we have a situation where we want to keep a bunch of default values, but we might want one or two values, which are actually passed in as a parameter to create the text style object. So I'll show you another way to create these text styles using function. Just gonna do some quick copy paste here. And then we can override the color. So again, what I'm going to do for the rest of these textiles now that we've seen everything there is to see here is I'm going to copy and paste them over. But there is one more thing that's new that we need to create in this particular file. Okay, as you can see, we've got a couple different textiles here. So the last thing we need to do is create a typography object. So basically, what that's going to mean is that we're going to assign some of the text styles that we've created below, which are used in common things like the body text of a particular feature of the application, buttons, titles, that kind of thing. If that doesn't make sense. Let's just write the code. Make sure you select compose dot material, not kotlin dot txt. Okay, we're just gonna do To more. All right, and the only other thing we need to do is set up our graph Sudoku theme. Right click on the UI package, and we've got, you guessed it another kotlin file. And it's going to be called graph Sudoku themed. So one of the handy little features of jetpack compose is that it is incredibly easy to create a theme for light and dark modes. As someone who uses generally speaking, dark mode almost always actually really appreciate this particular feature of compose. The first step in that process is to create two different color palettes. Let's start with the light color palette. So some of these properties should probably be familiar to most Android developers like having a color primary. That's how we used to do it also in the old XML system with colors, or at least that was a common naming convention. Now, one thing I want to point out here is that there's a degree to which some of these more obscure ones like primary variant surface on primary and so forth, I'm really just using those because it's convenient, they don't necessarily have to mean anything in particular. But the important thing to understand here is that if there's any different color between a light theme and a dark theme, we do want to define it somewhere in here, and then use it appropriate in the composable, which we'll be learning to do later on. Okay, that was actually supposed to be uppercase there by convention. And also notice that I've copy pasted over the dark color palette, because again, there's nothing new going on there. The next step, however, is very important, we're going to create our theme, and it's actually going to be really, really easy. Here's a little shortcut I learned from a friend, if you want to create a composable function really quickly start typing comp, and then hit enter, just saves you a little bit of time. Now this theme is going to have two parameters here. So before we write the body of this function, I just wanted to discuss these two parameters. So as you can see, we're actually making a function call is system in dark theme, what's going to happen is this system call will return a Boolean, which will tell us whether the user has specified if the app is supposed to be in dark mode or light mode. And then the content represents everything that will be wrapped inside of this theme. What's important to understand here is that everything that we put inside of this composable, ie the content will have access to all these different colors, styles and typography information from within the theme itself. The actual utility of this will make a lot more sense when we actually write the composable. Just to finish things off, we're going to create a material theme composable. And we won't need the lambda expression. So there you have it, it only took a few minutes to create like the color resources and styles and typography information necessary to render both a dark color palette and a light color palette for different modes. What I'm going to do is show you a quick demo of what this actually looks like in an application. Here I'm going to be starting the application in the light theme. Then I'm going to navigate to the operating system settings and set it to a preferred dark mode. And upon returning we see immediately that the application now is using the dark theme. We're now ready to start building our user interface. The UI components package contains reusable elements of the user interface. Since this is a very small app, the only two such elements are a toolbar, and a loading screen. One of the great features of compose is that we can make our components reusable in different ways. Firstly, if a component needs to be positioned according to where it fits in different parent composable, or parent screens, we can pass in a modifier instead of creating a modifier within the child composable. This is worth experimenting with in case you haven't already. Secondly, it is possible to pass in composable as arguments, which also allows reuse and extension of functionality. In this app, we want different toolbar icons for the two different UI screens. And we can achieve this by passing in the icon compostables. From those parent UI screens, you'll see later on how we can specify and handle different icons and different click events. Using the same toolbar will also create this reusable loading screen and later, I will show you how to animate it, right click on the UI package and go to new package. And this one's going to be called components. Just a brief explanation here, I've adopted this particular convention from the composed samples repository. So what will go into this particular folder are composable, which will end up being reusable across a variety of different UI elements and different screens. In this case, we're going to be creating a reusable toolbar, and also a reusable loading screen, right click on the components folder, and go to New kotlin file, and this one's going to be called app toolbar. Let's create our functions stub, what I'm going to do is I'm going to type co MP and then the autocomplete will create a composable function. This one's going to be called app toolbar. First, let's write the parameter list and I'll explain it a little bit. Make sure you select the compose.ui modifier. Let's start by talking a little bit about modifiers. So modifiers are basically how you can create most of these styles size and position kind of data for a particular composable. Now there's kind of two different main ways to do this. We could of course, create this modifier and use it within this widget. But that would be for a situation when the widget itself is going to be deciding that kind of information. Since we're using a reusable component here, an app toolbar, which we plan to use in multiple different places. In this particular situation, we're going to pass the modifier into this function, which is a way of basically saying that the parent composable will actually decide where to position and how to size this particular UI element. The title is pretty self explanatory, but what is a little more complicated is the icon. And again, that will be dictated by something in the parent composable. That's how I actually make this thing reusable and allow it to handle different icons or different actions when it's clicked. After we finish off this particular composable, I'll show you a quick preview of the actual icon that we'll be using. So hopefully that will make a little bit more sense. The first thing we want to do is override the top app bar composable. Let's just pause a moment and talk about different colors. So one way to solve this problem would be to hard code some kind of color in here. But in the previous section of this tutorial, we went through the trouble of setting up both a light and dark theme. So what we're doing here is we're actually going to be using a color which is based on the theme. Remember in the graph Sudoku theme composable, there was a call to a function which was his system and dark theme or something like that. And that's actually going to dictate which color palette we select. So by using material theme colors dot primary, it will automatically inherit the appropriate color based on whether we're in light and dark mode. And that would be one reason to avoid hard coding something in here. In this case, we have a color which will be the same regardless of whether it's light or dark mode. So we're just going to add in a text composable which is effectively eight Extra view. But if you wanted to add something like a logo for the application in front or after the title text, and what you could do is you could add in a row here and then just add in both the icon and then the text composable. And then you'd be ready to go. Go ahead and import that. This is probably pretty self explanatory. But when we want to inherit style data for particular fonts and stuff like that, then this is how we can do it. Again, this is something super handy. And you only see this in kotlin, certainly not Java. So what we're doing here is we're explicitly asking is the application currently in light mode, and then we're picking a text color based on that. This is really just an alternative way of handing this conditional UI logic without having to assign something to a theme specifically. Next, we'll deal with alignment. And that's it for the texts composable in our toolbar. So action bar is probably something that will be more familiar to the older Android developers. But basically think of this is like the icons within the toolbar. Generally, they're used for very important actions in the user interface, like navigating to a new feature, indicating that you're done doing something. And note importantly, that this particular lambda function is of type row scope. So basically, what that means is, if you have several action buttons, you can place them within these two brackets here, and they will automatically be lined up like a row. Now all we need to do is just type icon and then add in the parentheses here. And this is because we're actually going to be passing this icon in from the parent composable. As I said, moments ago, I just wanted to give you a sneak preview of the icon itself. We're not going to be writing it yet, but we will do so later on. The important thing to understand here is that we're deciding about how to handle on click and what this thing actually looks like in the parent composable, we're not actually doing it within the toolbar. And by pulling that responsibility out of the toolbar, that's how we get the reusability that we want. Right click on the components package, go to New kotlin file, and this one's going to be called loading screen. Let's create our loading screen composable. The first thing we'll need is a surface. So you might be wondering, why are we using a surface here in particular, in this case, I really just want like a space surface of the UI, which has a particular color and specific dimensions. Here I've set Phil max height to a fraction of point eight F, which is basically saying I want it to take up most of the width, or sorry, most of the height of the user interface. But I might want some space for something like a an ad banner or something of that nature. Anyways, I basically want an icon or an image which is stacked on top of a progress bar which will be stacked on top of some kind of like text. So for that kind of situation, obviously we're going to want to use a column. Obviously, we'll be centering things. Go ahead and import that. Now I'm noticing it's not improperly importing our I think there's something within the Compose libraries, which basically mimics our so let me just fix those imports before we proceed. As you can see here, I've just copy and pasted it in the our import. And now we're good to go. That's our logo. Here's your progress bar. Okay, so you might be wondering about this painter thing. So basically, in the alpha version of compose, we had to specify whether it was a vector asset or a bitmap asset and stuff like that. So we can just use this generic painter resource thing and point it to basically anything in our drawable. And it will actually figure out whether it's a bitmap or a vector asset. Also, I wanted to point out the copy function here. Suppose you have a color and you want to slightly change the alpha value or you have one of these textile objects and you want to make some kind of change to it. The copy function is super handy for doing that. In this part of the tutorial, we will create the event sealed class view model and presenter for the act of game feature. Before we do that, let us look at a few design decisions involved in this architecture. The purpose of our presentation logic class, which I call logic, for short, is exactly as the name implies, it handles the work of coordinating the container view model and backend repositories. If notified of a non stop event, it will also cancel all co routines, it does not possess any Android platform code, which makes it loosely coupled and very easy to test. I might also consider reusing it for a desktop version of this app. But we'll see. The purpose of the view model is also to do exactly what the name implies, it is a virtual representation of the user interface, which the view observes. In simpler terms, it is a model of the view, it exposes function types, which is a very simple and easy standing for the observer pattern. In situations where we don't require multiple observers. Each time our logic class updates the view model, the view model will automatically publish the new data to the view. Another design decision with this view model is that it does not extend jetpack view model. There are several reasons for this decision, some of them simple, and some of them quite technical. The simple reason is that using jetpack view model creates tight coupling with the Android platform. And it has its own set of boilerplate code and dependencies, which I'm not a huge fan of. In short, it doesn't solve more problems than it creates in this particular application. And I wanted to practice creating view models which might be usable for kotlin desktop or kotlin. j s. The technical reason why is that in this application, we simply don't need to persist the data across activity instances or process death in order to have a good user experience. Instead, we just make a fairly cheap call to the Android file system and reload the data from there if such events occur. Now, before you apply that reasoning in every situation, understand that reloading data from a file system works fine in this application, but should not be considered a suitable replacement for unsaved instance state in every application you write. If you like the models in save state handle, go right ahead and use it. We also employ the strategy pattern to clean up the interface which our logic class exposes to the container in the view. Each subclass of the sealed class represents an action that can occur in the view or container. Rather than having a function for every UI event. We have one function that accepts a single object that can represent multiple different paths of execution. That's the strategy pattern. Right click On the UI package, and go to new package called active game, right click on this new package, go to New kotlin file or class, and we're going to create an interface, and it's going to be called active game container. This word container is a technical term. The way I'm using it here is to kind of signify something which contains a large portion of an application or an entire application. In my opinion, a container doesn't usually deal much with the business kind of logic of the application. It basically just wires things together and builds things and kind of serves as an entry point. In the next part of this tutorial, I'll explain what we'll actually be using as a container. But by using an interface here, I'm basically stating quite explicitly that I might change my mind about what we use as a container. Anyways, it only contains two abstract functions. Right click on the active game package again, and we're going to create a sealed class this time. And it's going to be called active game event. So as I explained in the above comment, the active game event sealed class represents every kind of user interaction of a given feature, in this case, the active game feature. This is a very common pattern that I use and we'll see how it works with our base logic abstract class which we created in the common package. Okay, we are now going to create our view model. Firstly, let's create a small little class here which will be like a virtual representation of a single tile in a Sudoku puzzle. So obviously, x&y represent the x&y coordinates of the particular Sudoku tile value will represent what we talked about in graph data structures as the color again, it's literally just a number, I don't know why we need to call it a color. Now it has focused indicates that the user has clicked on a particular tile, after which they can click on one of the input buttons to change that particular number. And finally, a read only tile you can think of as a tile, which is like a given clue in the puzzle. So therefore, the user is not allowed to actually change any read only tiles. So before we start reading this view model, I just wanted to mention a couple of things here. As discussed in the introduction for this particular section, I didn't actually want to use any of the jetpack libraries to achieve a publisher subscriber relationship between the view model and the view. Now, it turns out that that publisher, subscriber relationship or pattern is actually quite easy to implement. But in this case, I actually found it simpler to just use kotlin function types to achieve what I would call a poor person's publisher, subscriber pattern or observer pattern. So this really means something simple in practice, although it might look kind of complicated for those who aren't really familiar with working with function types. Our view model will possess these nullable function type references. As we'll see in a moment, what we can do is each time we update the view model from the presentation logic class, we can then update the view by extension by invoking these function types from within the view model. Now, the reason why we're using notables here is from within the view model. I can never be 100% certain if there is actually anything listening. But with that being said, I feel like if I played around with this particular class for a couple of hours, I could probably streamline a little bit and maybe make some of these internal variables private or something like that. So really what I'm saying here is Feel free to take this general idea of having a view model, which isn't tightly coupled to Android jetpack, but also feel free to experiment with it and see if you can optimize it. So with that out of the way, let's create some function types. So all of these function types will be prefixed with sub to ensure good legibility. Active game screen state is actually something we will create in the next part of this tutorial. So just go ahead and leave it glowing red here. Okay, let me just briefly explain these different function types. So the board state is basically a virtual representation of the Sudoku board. Obviously, the content state basically just means three different states. So either we're loading the data, the user has a currently active game that they're solving, or the user has completed a particular game, we will use this to animate between different states in the user interface. Now, timer state has to do with the count up timer, which basically records how long it takes for the user to complete a given Sudoku game. So just to hopefully clear up any confusion here, timer state will be the actual long value in milliseconds representing the time and then sub timer state is the way that we actually update the user interface after we update the new timer state. Let's finish off the rest of these variables. These are quite obviously default values. Next, we'll write a function to initialize this view model. Okay, so let's just pause for a moment. What we're doing here is we're taking the state of the data as it existed in storage, we're giving it to the view model, and then what we're doing is we're building the view models own virtual representation of that state. Now, the view models internal representations will have things like has focus, which are concerned specifically of the user interface and not necessarily something that I would include in the original domain model. Also, in case you're wondering, the key value is basically created from hashing the x value and the y value. This is something that we covered very early on in this tutorial, in case you've jumped ahead. Again, active gain screen state is something that we will create in the Compose part of the tutorial. Here, we're binding that data to the view model. And then we will invoke our function types to update the view assuming it's listening. And that's it for our init function. Now, we just have a few more functions, which will be called by our presenter to do various things with the state of the view model. So here, we're just updating an individual tile. So what we're doing here is when the user hits a particular tile, that's going to send a message into the presenter, which will have a particular x and y coordinate, and then the presenter will call this particular function. And so what it will do is it will look for the tile which the user clicked on based on that X and Y value, and set that one to has focus equals true. And then for every other tile, we want to set it to false. Otherwise, we could have a situation where the user has selected multiple different tiles, which is not something our application is supposed to be allowed to Do and this would be the situation where our back end has determined that the current puzzle is complete. Right click on the active game package. And let's create a new kotlin class, which is going to be called active game logic. Okay, so before we proceed, this is definitely one of those situations where I strongly suggest having the complete source code open on the side while you follow along here. Obviously, I'm going to do my best not to make any mistakes, but it's possible that I will make a mistake. Active game logic represents the presentation logic of this particular feature of the application. As we'll see, it coordinates between the container the view model, and then by extension, the view, as well as the back end of the application. Let's start with the constructor. Okay, so just a bit of review before we move on, for the time being the container will actually be an activity. But there's a possibility in the future, I might move to using fragments as containers instead, at this point, I don't really want to, but we'll just see if that makes sense in the future. But this is the entire reason why I have included an interface here so that I can change what's behind the interface very easily. The view model is pretty clear, we just wrote it. Game repo is where we store the game data. So that includes the game settings as well as the current progress of the users game stats. repple is where we store the records for the shortest times to completion of each different difficulty and size of puzzle. And if you're wondering what the dispatcher is go back and watch the common package when we created that we created this dispatcher provider and I basically explained what the purpose of it is there. Base logic is also something that we created in the common package. And we'll see the function that we inherit from that class in a moment. Okay, let's start for a moment about co routines. So one way to think about scopes, whether we're talking about co routine scope, or dagger or whatever, is to really just consider that it's about a life cycle. Now, you're probably wondering, why are we not making something like a view model or a fragment or an activity, our life cycle class? Well, in case you haven't noticed by now, I don't like any kind of tight coupling to the Android platform, if I can avoid it. There's a number of other reasons. But one of the main ones is that because this class contains all of the presentation logic, in a sense, it's the head decision maker for this feature of the application, then, in my opinion, it makes sense to make it responsible for cancellation of any co routines, which happened to be currently running as far as this on event function, which we inherit from base logic. Well, basically, this is an implementation of the strategy pattern. I won't give you a long and technical explanation here. It's actually a very simple pattern. But basically, it provides sort of like a singular entry point into this particular class. So instead of having like a single function, for every event, we have one function, which takes in an argument, our active game event, which is capable of representing all the different events, and I just find that really cleans up the interfaces between different classes, interfaces is used in the general sense in that statement. Okay, first, let's implement our co routine context. Remember, jobtracker exists in base logic, but we also need to initialize it Okay, now before we proceed, there's something really important we need to implement which is a ko routine timer. As I mentioned before, the active game Screen does have a count up timer. Now some of you are probably going to be wondering, why didn't I use the Java timer class or the androids count up timer or whatever it's called. Basically, I did try using those things. And they presented different application breaking problems. And it turned out to be easiest just to create this kind of CO routine timer. Okay, so this requires a little bit of explanation, obviously. So we'll notice two different keywords here, which might be unfamiliar to some of you, we have the inline and cross inline keywords. So whenever you see the inline keyword, the easiest way to understand that is to understand that it just means copy, paste. And if you want to know what that means in code, then I suggest you decompile some of your kotlin code, which uses the inline modifier, and you'll see how the inline function is actually copy and pasted into the call site. Now we have something else going on here, which is a cross inline function type. So before I explain what the cross inline action is, let's talk about what this function actually does. So here we have a pretty standard spin lock, while true. So it's a loop that's going to just endlessly execute, it's going to invoke that function type, and then it's going to delay for 1000 milliseconds. Now, there's a couple different things going on here. Number one, you have to understand that we will be delaying this ko routine, but it's not actually going to block the thread that it's on, which is of course a big win. Now the other thing that's going on here is action is going to be a lambda expression that we will pass into this particular function. Really the only thing crossing line does is it basically makes it so that in the lambda function, which we will pass into this function here, we're not allowed to write a return statement in that function. So in the most general sense here, what we're doing is we're taking a preventative step, to avoid a situation where we might accidentally return from within the lamda that we pass in here causing unexpected behavior. Now, you're probably wondering, since we have this endless loop going on, how do we actually stop this particular core routine? Well, what we're going to do is we're going to create a job. Let's just do that now. And what we'll do soon is we will actually assign this job variable to our start co routine timer, and that will allow us to cancel it. Let's just write another quick extension function to do with this timer business and then I'll explain what it does. In experimenting with the user interface, how to make the timer the least janky or most accurate that it could be it turned out that subtracting one from the value each time we write it to the back end created a more consistent timer. But one particular edge case is if the value equals zero, then obviously we don't want to subtract one from it. Otherwise the timer will say negative one at first and that just doesn't look very good. Okay, so with all that done, we can get to implementing the rest of the presentation logic Okay, so when the user hits an input button, we can have two different situations that could occur. In one situation, the user has already selected a tile, which would become the focus tile. Or it might be that they just hit an input button without actually focusing a tile, in which case, we don't really want to do anything. Okay, so if you're wondering about the details of game repo, you can go back to the part of the tutorial where we actually build it. Basically, we're going to be creating a lambda to represent the success case, and then another lambda to represent like an error exception case, to make that a little bit more legible. I'll just add in a comment here. Okay, so if you're again, wondering how we actually cancel the timer, this is exactly how we do it, we cancel the job object. Now we'll write this other function in a moment. Basically, if it's a new record, then we want to render the user interface slightly differently than if it wasn't a record. But before we do that, let's finish off the error case. So in order to actually know if it's record, we actually need to pass the value back into the stats repo just to check on that. So I'm going to be honest, the error handling in this application is not the best, neither is it really the worst show error Well, for the time being just actually show a toast message explaining that some error occur. Okay, just a quick fix. This is actually supposed to be elapsed time not timer state. Next, we have on new game clicked. You'll notice a recurring theme here, which is at any time we want to perform concurrent operations. So anytime we're working with the back end, we're going to wrap that into a launch co routine. There's a lot of different ways to work with CO routines. This is just one of the most simple straightforward ways to do it. In my opinion. Okay, so what we're doing here is first we're asking the view model has the user completed the current game, if they haven't, we actually want to store the progress the user has made in their current game, when they hit on new game clicked, because maybe they hit it by accident, or they want to be able to go back and finish the game or some reason like that. That's right The update with time function. Again, we have success and error cases. Hopefully, that's pretty clear at this point. Next, we'll implement that function. Next, we'll write the cancel stuff function. So basically, the cancel stuff function essentially cancels every ko routine. Next, we'll write on start. I forgot to mention earlier, the reason why we had an underscore in one of the functions for is complete. It's just kind of a convention for a lambda argument or parameter, which doesn't actually end up getting used. In this case, we're going to use it. Okay, so obviously, this is where we start the coroutine timer, and we only want to do that when on start is called. Now, again, I feel like I could have handled this a little bit better, it kind of goes against my rules to consider standard flow the application as an exception. But basically, what we're going to do here is in the event that we ask the storage for a current game, and it doesn't actually retrieve anything, generally speaking, this situation is going to occur when the user has run the application for the first time, and hence, there wouldn't actually be any data stored. So in that particular case, we would want to do this. Now, we could also end up here because of some kind of legitimate exception, but in that particular case, I still think navigating to the new game feature is still actually a good way to handle that good but maybe not the best. Next we have on stop. Okay, so onstop is actually tied to the lifecycle of the Android activity or fragment that it's bound to. So when this function is called, that basically means that we want to save the user's current progress and then kind of shut everything down. Finally, we have on tile focus. So this would be when a user actually selects a particular Sudoku tile. Now this function is incredibly complicated, so brace yourself. Okay, I lied. That's actually everything we need to do. In this part of the tutorial, we will create the user interface for the active game feature. Before proceeding I strongly suggest you watch my video entitled How to Understand jetpack compose a beginner's guide to composable and read composition. We will be writing many composable and setting up re composition as well. But that video is made for people who are just getting started with compose. It explains what a composable is, what read composition is and how to avoid doing read composition the wrong way. And believe me, it is fairly easy to screw up read composition if you aren't aware of how it works. I will link to this video in the pinned comment below. This video is full of a ton of information, so please take a look at the timestamps in the description box below. Topics include basic widgets, such as text, text, button, image, icon, spacer, and divider layouts, such as box column row box with constraints and my favorite constraint layout. Simple transition animations to animate between a loading screen, active game and a complete game. I also show you how to communicate with our presentation logic and our view model using function types and lambda expressions. Before we write the composed code, though, I show you how to set up an activity as a container for composable. The process for doing this is almost identical for fragments if you prefer them, I also show you how to write a very simple dependency injection extension function, which hides the backend details from the front end. Right click on the active game package and go to new activity and choose an empty activity. And make sure you uncheck generate a layout file. And this activity will be called active game activity. It will be the launcher activity. Now in case you're wondering why we're using this wizard instead of just creating a class file. The reason is simply that by using the wizard it will add an entry into the manifest so we don't have to do that. Just to briefly recap the purpose of this activity here is as a feature specific container. Let's start by creating a reference to our active game logic class. Next, let's implement the active game container interface. Click on the red and hit alt enter. For show error, we will use the extension function that we created way earlier on in this tutorial. Go ahead and import. Also in case you're wondering, this is single expression syntax here it basically just replaces the brackets and return statement with just an equal sign. Next one implement on new game click. Now obviously we haven't created new game activity yet so that will show up as red until we do. We also need to override two more lifecycle methods. Here will tell the logic class that everything is ready to go And then we'll also override on stop. And that will obviously signal the logic class that it's time to cancel things and tear stuff down. Finally, we just need to add a few lines to on create. First of all, create the view model. Now, this is a really important part, what we're going to do next is we're basically going to anchor our composable that we'll be creating in the next part of this tutorial, to the activity here. This is also something you can call inside of a fragment. Go ahead and import that. Naturally, we're gonna wrap everything in our compose theme. Now, this is a very critically important thing to understand and a very important pattern. So when we create active game screen, we're going to pass in a function type, which will serve as our event handler, which is basically my way of saying that is the way in which we will forward the events, the onClick events and stuff like that, that occur in the composable to our presentation logic class. So make sure you pay attention to what I'm saying here, because this is a really important part, even if you don't use presenters wood, or whatever. Function types are an excellent way to handle on click events, especially if you combine them with the strategy pattern, which we discussed in the previous section. Okay, now, if you've never seen a function reference, I believe it's called basically what we're doing here is we are pointing to the on event function of the logic class. This really is a function reference. So hopefully, you can understand what I'm talking about here. We'll also pass in the view model. Now lastly, we actually need to build our logic class. So what we'll do is we will write that code in an extension function, but what we can do first is just read it here. And that's everything we need to do in our activity. Right click on active game, go to new package, and this package will be called build logic. Right click on that package and go to New kotlin file or classes is going to be a file. And it's going to be called build active game logic. If you've been watching my channel, or live streams for some time, you'll know that I talk a lot about dependency injection service locators. And one of the things I say all the time is that in a small application, you really don't need to use di container, like hilt, dagger, whatever, you can use it. But what I always advise for beginners is to write the code that these things generate for you, yourself first, so that you understand what these frameworks are doing for you. So that's exactly what we're going to do. We're going to write the kind of thing that these frameworks generate for you. And in a small application, it's actually very simple code to write. And, of course, it's going to return active game logic. Okay, let's pause for just one moment here. So in case you're wondering how we get the path to the storage directory that we can use for this application, you can call context dot files dir dot path. Finally, our dispatcher. And that's all we need to do. Right click on the active game feature, and create new kotlin file called active game screen. First, let's create an enum. This enum represents different states, which this feature of the user interface can possess. The actual state is held in the view model, but we will see how we can update our composable UI by binding to the view models function types we created in the previous part of this tutorial. Active game screen represents the root composable. In this hierarchy of composable, it has the responsibility of setting up the core elements of the UI, and also animating between them. event handler function type reference is how we call back to the presentation logic. When the user interacts with the application, it must be passed down to any composable, which has such interactions, we also pass in the view model, which is how we actually give the data to our UI. In very simple language, whenever we have some kind of data or state, which may change at runtime, we want to wrap that data in a remember delegate. This tells the Compose library under the hood, to watch for changes and to redraw the UI if a change occurs. Now mutable transition state is used specifically for animations here, so don't use this everywhere. We will see a more general purpose example of a remembered state later on. Remember, delegate prepares compose for updates, but we also need a way to actually update the value. We do this by binding a lambda expression to one of the function types which our view model possesses. When one of those functions is invoked in the view model, the program automatically jumps to and executes this code within our composable. This is what actually triggers the re composition. We have a remembered transition state and a way to update that state from the view model. Now we need to set up the transition animations themselves. This is where you can get as creative as you like. In this app. Each content state has its own composable associated with it. We animate between them simply by changing the alpha value or transparency. Now it was truly up as red a moment ago, the way I fixed that was to manually import the Compose runtime. So the transition spec tells compose details about what the animation should look like. Essentially, this means we don't have to write our own mathematical instructions, which is great for someone like me who sucks at arithmetic. One option for compose is to use the scaffold composable as a skeleton for your UI. I personally prefer to do this myself, since it's not really that difficult, and it doesn't hide anything from me. First, we have our app toolbar. Let's go ahead and create that new game icon. These icons come from the Compose material library, I highly recommend you use it. This is how we actually trigger an on click event. As explained in a previous part of the tutorial, by creating our toolbar icon here and passing it into the app toolbar composable, we make the app toolbar reusable. Below the toolbar we have the main content of this screen, which can have three different states. Each time a re composition occurs, this one statement will be executed again. The act of alpha value will change when the transition animation occurs, thus fading out the previous content state and fading in the new one. Obviously, we will create these in a moment. And that's it for our route composable the most complex part of our UI comes from an active Sudoku game. A nine by nine puzzle has 81 different texts composable, which is a large number of widgets. The way I went about writing this composable was to think of each part of the Sudoku game as a particular layer or element. Be sure to avoid writing God composable by making usage of helper functions, which break down the UI into the smallest reasonable parts. box with constraints is kind of like a composable wrapper, which gives us information about the height, width and other measurements, we can use that information within its lambda expression. We need to know the screen width in order to determine how wide and tall the Sudoku board should be. Here we asked for the max width of this constraint layout. Here we ask for the max width of this layout composable. But we need that value to be in density independent pixels, and it needs to be relative to the density of the current screen as well. That's where the two dp extension function comes in. And it uses the local density to determine that value. The margin of the board also needs to change based on the screen density. I arrived at these values simply by testing the app on various densities using the emulator. Next, we will write a constraint layout, which is a totally awesome way to manage dynamic layouts. Now in order to constrain composable to each other, we need a way for them to reference each other. This is equivalent to setting IDs for XML views. First, we create these references and you will see how to bind them later on. Let's create a layout container for the puzzle board. Okay, so this is really important see how we're passing in that reference in the constrain as parameter there. This is how we actually associate a particular composable with a particular reference. This box composable will be associated with the name board. Next we'll create the Sudoku board itself. Again, the boundary is like the size of the puzzle. So it's either a four by four puzzle or a nine by nine puzzle. So boundary would either be four or nine. This is supposed to say size. So the offset here is used to evenly distribute the screen real estate for each Sudoku, tile and grid line. Here's a way to make a mutable state which is not associated with some kind of transition animation. So this is the more general purpose approach. So the first argument here view model dot board state can be thought of as the initial value, never equal policy ensures that even minor changes in the state like has focus actually triggers a re composition. Again, this is how we actually update the value once the view model is updated. As you can see, here, again, I'm making usage of lots of helper functions to break things down. Here we render the text fields which represent tiles in the puzzle, they can either be read only or mutable, thus, meaning that we need to render them slightly differently. So here, we're saying if the user sets a particular tile to a value of zero, we actually just want to render it as an empty tile. The main idea here is that we're using the x and y values of each individual tile along with the offset in order to evenly position each tile So when the user selects a tile, it's going to become focused and we want to render that tile obviously a little bit different than an unfocused tile. Now we'll render the read only squares. Next we'll create the board grid. So Sq RT is an extension, which is actually defined in the computation logic. In retrospect, I probably should have defined that in the common package, but it's pretty obvious what it does. So this function here, we'll draw the grid lines that separate the Sudoku puzzles. To make it more obvious to the user which sub grids are which we draw different borders to separate the four by four or nine by nine sub grids. This is why we're using modulo here. So this will draw both the vertical and the horizontal lines. Okay, so we're jumping back into the game content composable to finish it off. below our Sudoku board, we have some different icons to indicate the difficulty of the puzzle. Next we need a layout container for the count up timer that's great, the timer texts composable. Now the default value, it's just empty. Okay, we're back in the game content composable. The last thing we need to do is just add a layout container for the input buttons. Now we're about to hard code some values in here and that is kind of bad practice. But the reason is that the Compose team deprecated flow row, which I'm still upset about, and it worked perfectly for this situation, and I've been too lazy to implement flow myself. Hey, at least I'm being honest. In case you're wondering, 0.4 and five dot dot nine will emit a range inclusive of those values. Let's create that composable a spacer is pretty self explanatory, it just takes up some space in the layout. Next we have the buttons themselves. This text button wrapper allows us to style a nice looking button instead of just adding on click on a text composable. Alright, that's it for gain content. Now we need to do the game complete content screen, which is obviously when a user finishes a game. So this is basically just two images stacked on top of each other, but we're only going to render one of them if it is actually a new record that the user made. So since we don't actually create the emoji events icon, we can change the color of it using this color filter thing. Pretty handy. Next, we have to text composable. And that's it. Congratulations. In this part of the tutorial, we will examine the topic of graph data structures, mostly with respect to solving Sudoku. Unlike the rest of this tutorial, which is presented in a code along format, This lesson will be different. Instead of rewriting all the code, we will look at the basics of a graph data structure. How I modeled a Sudoku puzzle as a graph data structure, how I created, tested and improved my algorithms to the point where they could generate 100 puzzles in roughly 400 milliseconds. before I proceed, I suggest you read my article on Free Code Camp, which explains the fundamentals of software engineering in a clear and accessible way. That article explains these topics assuming only that you have some basic coding skills. Let's start by asking a question, what are graph data structures? The simplest verbal explanation I can think of is that they are a family of data structures, which are useful for modeling a bunch of things which are connected in some way. To connect that definition with something visual, you can imagine that the bunch of things are a series of nodes or points, and the connections between them are a series of edges, which you can think of as lines connecting the points. So whenever I say the phrase graph data structure, a better term for most people to understand this topic is a network data structure. In fact, that is exactly how they are used in apps like Facebook to represent users and friends. Google Maps to represent city addresses in the roads connecting them or Sudoku puzzles to represent tiles which have relationships to each other. According to the game's rules. Pictures and words are fine, but the code is more important. How do we tell a computer system to virtually represent a Sudoku puzzle? This process is more concrete than you might think, though, it helps to be an expert in the programming language you're using. In principle, the process is to take all of the information you know about the problem you're solving, ie the problem domain, and start writing code which describes it. First, we represent a single tile in a Sudoku puzzle with the class Sudoku node. It has a value x and y coordinates and a Boolean to establish whether it can be edited or not by the user. Read Only true would indicate a node which is a given clue at the start of a new Sudoku game. Now this term color really just means a value from zero to the boundary of the puzzle. So a nine by nine puzzle would have the colors zero to nine. To be honest, I don't like using the term color as it confused my hyper literal brain. But please understand that it really is just a number value. And the term color is actually irrelevant in this problem domain. Where the word came from is that this kind of data structure was used to solve a problem that involved coloring different countries on a map using a fixed set of colors. We could have just as easily associated these numbers with different kinds of sandwiches, but to the computer, it is the same thing. In any case, if you hear me say color, just remember it's a value, it's a number, not literally a color. Now the data structure itself must include every element, as well as the connections or relationships between every element. There is no single way to do this, but I arrived at using a linked hash map datatype from the kotlin standard library. This data type preserves the ordering of its elements, and allows me to find a specific element based on a hash code. The hash code itself comes from this simple hashing function which generates a unique key based on the x and y values of a node. The linked lists themselves represent both the root node at a given x&y location as well as any other node which happens to be in the same row column or sub grid of that root node. The root node will always be the first node in the list known as the head element. But other than that, we don't care about the ordering of the rest of the So after I figured out how to model a Sudoku game in this way, the next step was to start writing the algorithms to manipulate my chosen data structure. The first algorithm I wrote was called build nodes. Its job was to build the skeleton of our data structure. By adding an element for every tile in the puzzle. A square size in Sudoku will have n squared tiles or elements. So the first thing I did was write a unit test to check for that condition. Here we see the first example of the process I used to write these algorithms. I tried to solve the problem one step at a time and to verify the correctness of each step as I went. Next, I knew that I needed to create the edges or relationships between different tiles based on the rules of the game, nodes would share a column may not have the same value or color nodes would share a row may not have the same value, nodes would share the same sub grid may not have the same value. Now, we haven't actually added any values yet, but we can still build the edges of the graph using these rules. After looking at a picture of a four by four, nine by nine in 16. By 16 Sudoku puzzle, I was able to determine that every tile will have the same number of edges as any other tile, and those numbers happened to be 821 and 40, respectively. At first, the test was failing. But I figured out that a node can be for example, in the same column and subgrid. So I needed in my algorithm to be smarter about avoiding those kinds of repeats. The previous two algorithms were childsplay. Whereas now we get into some more difficult problems. The seed colors algorithm caused me huge problems and took many days to get working properly. The purpose of this algorithm was to provide some initial values, ie seed values to make the next step in the algorithm easier. At first, I tried to do this by distributing the values diagonally, which is a relatively safe way to avoid breaking the rules. But this approach led me to an uneven distribution of initial values. I thought this was a problem and eventually came up with a new algorithm that would make horizontal and vertical passes of the entire puzzle, allocating numbers in such a way that was guaranteed not to break the rules and provide an even distribution. While I'm proud of this algorithm in a certain way, on a certain level, it's also disgustingly complicated and proved pretty difficult to test, I settled on ensuring that it wasn't creating an invalid puzzle, and it was allocating a number of values roughly equal to A quarter of the total number of tiles. If I allocated too many tiles, it would cause problems though, so I had to include some hard coded edge cases, which I didn't really like. Perhaps most important algorithm in this series of algorithms is the solver algorithm. The solver algorithm takes in our seated graph and attempts to solve the puzzle from there. Now I had already written a few other solver algorithms that didn't use graph data structures. So I was curious to see if using a graph would actually make this process easier. In some ways it did, but it was still overall quite difficult to write a high performance solver for n sized Sudoku puzzles. Every algorithm for generating a Sudoku puzzle that I'm aware of makes usage of three things. brute force random number assignment, checking if these new assignments create an invalid puzzle. backtracking when an invalid puzzle is created, or the algorithm is simply not able to allocate any new values without actually breaking the rules of the game. The problem with brute force random number assignment is that it scales very poorly as the size of the puzzle grows, randomly generating a four by four Sudoku puzzle is quite easy that way. But even a nine by nine puzzle can take a long time if you just use random numbers and backtracking. There's no way the app would be any good if the user had to sit and wait for five minutes just for the app to generate a new puzzle. As is often the case, the solution to this problem came from figuring out the right question to ask, How do I tell the computer to make smart decisions about assigning values instead of just purely random decisions. In the end, I settled on giving the algorithm a nice value, which is inspired by nice values in CPU scheduling. In principle, the algorithm will select an empty tile and look at the number of possible values we can assign to that tile with respect to the rules of the game. This is done by looking at the rest of the elements in the linked list for that tile, and seeing how many of them are already colored that is given a value in a nine by nine puzzle if eight other tiles in the list already have a unique value than the tile we have currently selected, can only have one possible correct value. If seven tiles are already colored, we have a 50% chance of guessing the correct number which is still pretty good odds. So the nice value represents how picky the algorithm is in deciding whether or not to assign a value. The nice value itself is adjusted constantly with the basic idea being two things. If the algorithm has looked at many elements and could not find a sufficiently safe guess, we increment the nice value, thus allowing the algorithm to make riskier guesses. If the algorithm assigns a value, it becomes pickier again by decrementing the nice value. The other important part of this algorithm is the multistage backtracking. This part was very difficult to figure out, and it required trying a lot of different approaches. In order to work smoothly for four, nine and 16 boundary puzzles, I settled on using three stages of backtracking. In the first stage, when the algorithm gets stuck, we remove half of the values we have allocated to the puzzle. In the second stage, we remove all values we have allocated to the puzzle, but we keep the same seated values. In the final stage, we remove all values and generate a new seed then reset the algorithm to start from scratch. After playing around with both the nice values and the conditions for each stage of backtracking, something magical happened, I made one small change to the nice value adjustment. And suddenly, as you can see from my benchmark tests, the algorithm was generating 101 nine by nine Sudoku puzzles in roughly 400 milliseconds instead of over four minutes. At first, I didn't trust what I was seeing. But after removing the change I had just made, we were right back two minutes instead of milliseconds. The key takeaway is that every time I made a small change to the algorithm, I rerun the benchmarks to see what changed. Tests are absolutely critical when you are writing new algorithms, as they tell you both the correctness and efficiency of your code. I was super excited to have a working Sudoku solver that was crushing my benchmarks, but there was still one more algorithmic dragon to slay. As you can guess a solved Sudoku puzzle is not actually useful to a person looking to solve a Sudoku game, which happens to be our entire user base. Having generated a complete and valid puzzle, the next thing to do was to remove a certain amount of values to make the game playable again. At first, I thought the difficulty of a Sudoku puzzle was largely dependent on how many initial clues are given to the user. That idea is true at the extremes of a complete puzzle or an empty puzzle, but not so true in the middle. What I mean is that you can definitely have a Sudoku puzzle with 33 given clues that is easy to solve without guessing and have a puzzle with 38 given clues that is impossible to solve without guessing. So I suddenly realized that I was going to need to invent some way of establishing the difficulty of a Sudoku puzzle in a consistent way. Now, I knew that there must be some way to do this mathematically. But the truth is that mathematics is not a natural way for me to solve problems. I was great at calculus, but only for the reason that I could visualize the graphs which the equations described. Instead of trying to model this problem in mathematical terms, I visualize the things that I actually do in order to solve various difficulties of Sudoku puzzles. I then figured out how to tell the computer to employ these different strategies to attempt to solve a puzzle without making any random guesses. This led to creating three kinds of strategies which dictate the difficulty of a given puzzle. In the basic solving strategy, a puzzle can be solved simply by going through each square and asking if there is only one possible value that can be placed in that square based on the rules of the game. In the advanced strategy, we still use the basic strategy, but we also look for a situation where a node has two possible values, we then look for another empty node, which has an edge to the original node that also has the same possible two values. Finally, we test assigning both values to both nodes. Three things can occur when this happens if both result in a valid Sudoku puzzle. This doesn't actually help much because it's possible to make valid assignments that still result in an invalid puzzle later on. If both result in an invalid puzzle, this is obviously not a good situation. Finally, if one configuration is valid, but the other isn't, then logically, the valid configuration is correct. The final solving strategy basically means that the puzzle cannot be solved in a purely logical way, ie you must make guesses to solve it, or it requires some kind of advanced strategy, which I'm not aware of. I'm not an expert in Sudoku, but I'm better than the average player. So either way, I would consider that to be a hard puzzle.
Info
Channel: freeCodeCamp.org
Views: 69,794
Rating: 4.9616346 out of 5
Keywords:
Id: bo_LP6QOUio
Channel Id: undefined
Length: 209min 44sec (12584 seconds)
Published: Wed Aug 25 2021
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.