Object-oriented Programming in C++

By using a bash command, find your home directory. Try to also find it in the (graphical) file explorer of your operating system (e.g. windows explorer, finder).

Create a directory named cse201 in your home directory. Check with a graphical file explorer that the directory exists.

In theory, you should already have an account. To check that it is the case, try to log in on https://gitlab.binets.fr. If that’s not the case, you need to activate your account by clicking on “ma première connexion” on the Sigma server (https://sigma.binets.fr/app/login).

Once you have your account, you have to create a project named cse201 by clicking on the New project button. For the project group, pick your own name, and for the project “name”, use “cse201”. Let the visibility as private, and unselect "Initialize repository with README". Finally, click on "Create repository". You should now see your beautiful project. Since the project is empty, you should see some instructions explaining how to start.

What you have created on GitLab is named a "repository". A repository is like a directory where you store your source files. It's not so far from dropbox, but tailored for development. GitLab manages the repository with the git tool. git is a "distributed version control system". It means that git keeps an history of the files stored in the repository. It's very useful if you make mistakes when you modify your code, and want to retrieve an older version of a file.

Now, you have to add your professors in your project through the web interface. For that, click on "Manage", then "Members", and finally "Invite member". Type "gael.thomas" and selects the user. Modify the role to Developper, otherwise, we will not see your code. Finally, click on invite. Do the same with the user "julien.tierny".

For the moment, your source files are stored in the servers of GitLab. To work with them, you have to copy them locally on your machine. For that, you have first to create what we name a ssh keypair, which is used as an authentication token to load and store the files in your repository. Technically, a ssh keypair contains a public and a private key. You give the public key to someone (in our case GitLab), and you use the private key to generate an authentication token. Since only the owner of the private key can create a token that matches the public key, anyone can verify that you are actually the owner of a public key, which authenticates you.

To create this keypair, you have to use the ssh-keygen tool. Then you have to display the public key and to record it in GitLab. For that, you have to launch a terminal (by launching the terminal application for the Mac users, or by starting WSL for the Windows user). In the terminal, type the following commands:

At this step, you should see your public key in the terminal. Through the GitLab web interface, click on your profile, then preferences, then SSH Keys and then add new key. In the Key field, copy paste copy-paste the public key that you see in the terminal, and then click on "Add key".

With git, when you write code, other developers must be able to identify you. To do this, they need your name and an email address to contact you in case of a problem. For this reason, you need to configure your git developer name and email on your local machine by copying and pasting into a terminal the two lines starting with git config --global that are displayed on the GitLab web page.

Now that you have the cse201 repository hosted on GitLab, we will connect your local cse201 to this project.

Under the hood, git works by considering repositories, and by connecting them. Technically, a repository is a normal directory enriched with meta-data that, at a high level, contains the full history of modifications you brought to your project. Additionally, a repository may have what we call an origin. The origin of a repository is a kind of master copy. To work locally, you thus need a local repository configured so that it uses the repository hosted on the GitLab server as its origin. Such a local repository is what we call a clone of an origin. You can, of course, have clones of a git repository on different machines, which means that you can end up with an architecture similar to this one:

Internally, a Git repository considers two different elements:

• The working tree: this is the directory tree that you see in cse201. At the moment, in your working tree, you have a lab1 subdirectory that contains your hello.c file.
• The commits: a commit is an internal snapshot of your files that you can send (we say push) to the origin server, or restore locally if you want to retrieve an older version.

This means that, locally, you have a set of commits (which we call the history) and your working tree, which is not yet committed. For example, as you work, you will end up with a history similar to this one:

Here, imagine that you created commits 0, 1, and 2, and then modified the sierpinski.c file. In this state, you can, for example, revert your working copy to commit 0, push commit 2 to origin, or create commit 3 from your working directory.

To illustrate, we will create commit 0 from your current version of the lab1/hello.c file. To do that, you need to know that, inside your working directory, Git considers different kinds of files:

• Untracked: Git totally ignores the file. Any new file is initially in this state.
• Tracked: Git tracks this file and can include it in a commit:
  • Unmodified: the file has not been modified. In the next commit, the version from the previous commit will be used.
  • Modified: the file has been modified:
    • Staged: the new version will be included in the commit.
    • Unstaged: the new version will be ignored, meaning Git will use the last committed version of the file in the next commit while ignoring the current state in the working directory.

You can see the state of your files at any moment with the following command:

If you type this command, you will see that the directory lab1 is untracked: it means that the whole directory and its files are untracked. We will thus tell Git to track the file lab1/hello.c (this also marks the lab1 directory as tracked) with this command:

If you type git status again, Git will tell you that lab1/hello.c will be committed in the next commit. It should also tell you that lab1/hello is untracked. You can thus create your first commit by typing:

The -a flag stands for "consider all modified tracked files as staged", and the -m flag allows you to add a message describing the modifications you made to your code.

Adding a generated executable to a commit is not a good idea, as we can always regenerate it from the source files. For this reason, we will never track a generated binary like cse201/hello. However, the file appears as untracked when you type git status, which can be annoying as it pollutes the output. If you want to hide these files, you can tell Git to totally ignore them by using the lab1/.gitignore file in the cse201 directory. In detail, you have to add the ignored files, each on its own line, to lab1/.gitignore:

lab1/.gitignore is itself a file. It is thus a good idea to add it to your repository so that if you clone your project on a different machine you don't lose it. For that, you just have to create a new commit:

You should see your two commits: the one that adds lab1/hello.c and the one that adds lab1/.gitignore.

If you go to the GitLab server, you will see that your repository is still empty. This is because when you commit to a local repository, it does not propagate the commit to origin. To propagate the commits, you have to use the command:

Once entered, if you go to the GitLab server, you will see your files. Congratulations, it means that the professors can see your work and grade you. Regularly checking that your work is visible is a good idea to avoid disappointment: if your work is not pushed to GitLab, your professors will think that you did not work...

Now that everything is set up properly, working with Git is relatively straightforward. During a lab, you will work on your working tree, and then commit and push your work. We will simulate such a process. For that, we will create a new file Readme.md in the cse201 directory with the following content:

And type exactly the code of your Readme in the terminal. Once done, on the GitLab server, you should see the Readme.md file. You can also see that the content of this file is displayed directly on the server, which is great to explain users how to install or configure your project.

In the second part of the course, you will have to work with teammates on a project. To collaborate, you will use git. It means that you will have several clones of your project, and you will have to synchronize them. We will simulate such a process. For that, we will create a second clone of your project. In the terminal, go to your home directory by typing cd. Then, copy the URL of the project by clicking on the Code icon on the GitLab server (use the URL that starts with git), and type

If you explore the directory my-teammate with ls, you will see a full copy of the last commit.

In my-teammate, create a new commit. For that, modify the Readme.md file by adding some random content, and type:

Go into your cse201 directory. At this step, you do not yet see the modifications of your teammate. To include them in your local repository, you simply have to type:

If git asks you how you want to handle potential conflicts, use the rebase method.

You can check that you now see the modifications of your teammate.

While you work with your teammates, you will face conflicts. A conflict appears when two repositories diverge: one contains a commit that is not yet included in the other, and the other repository has also been modified (either only the working tree, or because it contains other commits).

We will simulate such a conflict. For that:

• In the my-teammate directory, edit Readme.md and remove your random content, then commit and push your modifications
• In the cse201 directory, edit lab1/hello.c to print Git is easy! instead of Hello, world!!!. Compile and execute your new hello program. Commit your modifications, but without pushing them
• In the cse201 directory, modify lab1/hello.c a second time to print Git is easy! Heu.... maybe not so much?. Do not commit, push, or pull anything.

At this step, we have two conflicting repositories.

Here, the history of the repository located on the server and on your laptop matches up to commit1, but then totally diverges. If you type git pull in your cse201, git will first refuse because of the modifications in your working tree, which have not been committed and may be overridden if you pull the history from the server. To solve this problem, we will remove the problem of the pending modifications in the working tree from the equation. For that, you have to type:

This command "hides" your local changes. Technically, it sets them aside so that you can apply them later once the other conflicts are resolved. It means that now, you have two different commit histories that conflict, but at least, your working tree is clean, which makes the conflict easier to solve.

To solve the history conflict, you just have to type:

If git asks you how you want to handle the conflict, select the rebase method.

Under the hood, what git did is that it:

• canceled commit3 to revert to commit1 in your local repository (the history is commit0
• pulled commit2 (the history is commit0
• reapplied the modifications of commit3 on top of commit2, and then re-committed commit3 (the history is commit0

Here, we are lucky: git solves the conflicts on a line-by-line basis, and since commit2 and commit3 modified different lines (in different files), git is able to merge the commits automatically. It may happen that you and your teammate modified the exact same line. In this case, you will have a message from git saying that you have to solve the conflict manually before continuing. At a high level, you have to:

• Edit the file where you have a conflict that git cannot solve, and find the lines that start with <<<. Here you can see both your version and the one pulled from origin. You have to remove the <<< lines, and select one of the versions (or adapt the content)
• Type git add the-file-in-conflict and commit with git commit -a -m "Merge conflict",
• Continue to merge the conflict with git pull --continue.

At this step, the conflict between the histories is solved, but your local modification to print "not so easy" is not yet reintegrated. You can reintegrate it by typing:

This command will re-apply your stashed modifications to your local tree. If git is unable to merge the stashed modifications, it will add lines that start with <<< to your file, and as in the case of a merge issue during a git pull, you will have to manually merge the conflict.

At this time, your life is beautiful again, all the conflicts are merged, and you have this clean history:

Since the history prefix on the GitLab server and in your clone matches, you can commit your last modifications, and push your work so that commits 2 and 3 become visible to your teammates.

In order to test your application, you first need some sudoku grids. For that, you have to go to the directory cse201/lab1, and then to execute the following commands in the terminal:

Depending on your configuration, you may have to use wget instead of curl:

If everything went well, you should now have a sub-directory named grids, which contains some sub-directories that start with the name grid. Among the grids, they all have a solution except grid02, which cannot be solved. You can use this one to check if your sudoku solver can also handle unsolvable properly.

Write a sudoku.c file that:

• quits with a message if the program does not exactly receive one argument,
• and prints this argument in the terminal.

For example, running ./sudoku grids/grid01/grid.bin should output grids/grid01/grid.bin.

To manage the arguments, you have to know that:

• The signature of the main function is int main(int argc, char* argv[]),
• argc gives the number of arguments, knowing that the name of the program itself account for one argument,
• argv[i] is the i^th argument (argv[0] is the name of the program).

The argument provided to the program is a path to a binary file that contains a grid. In details, the binary file contains 81 integers (4 bytes each). Write a function int read_sudoku(const char* path, int grid[]) that reads the content of the file path into the grid grid. The function has to return -1 if an error occurred and 0 otherwise. In the main function, instead of writing the argument of the program, you have to call read_sudoku with the argument.

In order to read a file, you need these functions:

• int open(const char* path, int oflags) (provided by fcntl.h): open the file path and returns a file descriptor that can be used to access the file. oflags indicates how you want to open the file (read, write, create etc...). In our case, we want to read from the file, so we will use the flag O_RDONLY.
• ssize_t read(int fd, void* buf, size_t nbytes) (provided by unistd.h): read nbytes in buf from the file descriptor fd. You will better understand what is void* in the next labs. For the moment, imagine that void* means "any array". As a result, to read the content of the file identified by the file descriptor fd, you have to insert this code:
  read(fd, grid, 81 * sizeof(int));
  Thanks to that, read will read 81 times the size of a int from the file identified by fd, and put these bytes into the grid.

To use the open and read functions, you may need to add this line at the top of your source file:

In order to test your program, you have to run ./sudoku grids/grid01/grid.bin.

Note that you can find a lot of useful information about the open and read by typing the command man 2 open or man 2 read in the terminal.

Write a void print_sudoku(int grid[]) function that prints the sudoku grid in the terminal.

In order to test your program, you have to run ./sudoku grids/grid01/grid.bin.

We propose that you solve your grid using a backtracking method. This method involves trying out values and, if they lead to an inconsistent grid, going back to try a different value. Modify your program so that it solves the sudoku using this method.