What is this?

I am planning on holding a series of Code Dojos, posting once per month. The style will first introduce the challenge with information needed to solve it and example that can be used. If you want to challenge yourself you stick with the time frame given. After the challenge section there will be a presentation of a solution. The solution will be in basic C++ 14.

The planning with this is to hold them at my work. With that in mind there will be two types of Code Dojos: small, which will be around 1 to 2 hour, and large, which will be 4 hours or more. These will touch all from problem solving, like the first one, to algorithms and computer structures. The idea here is to expand problem solving within coding. In most cases when programming, a new problem could just be a old problem worded differently.

Code Dojo

Category: Problem solving
Restriction: Non
Size: Small

A town have been infested by zombies. To best combat them you need to find out how many groups there are active in the town. A grid will represent a town where a 0 is a human and a 1 is a zombie. Adjacent number, horizontal or vertical, mean they are part of the same group.

Example

10
01

is a town with 4 creatures, 2 humans and 2 zombies. As the 1 are not adjacent we have 2 zombie groups here.

Write a program that will take a grid and calculate how many groups of zombies there are. Solve following grids:

100000
010000
011000
001000
000011

and

101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
111
...
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
111

Above grid should be copied to over 100k rows.

Solution

The solution will be implement with three files: main.cc, util.h and util.cc. For each code snippet that is shown and explained I will write which file the code belong to.

The main implementation will happen in util.cc where the calculation of the groups will happen. Before that, we will setup util.h for util.cc. .h file in c++ are header files and they contains, for the most part, function declaration and definitions.

// util.h
#ifndef UTIL_H
#define UTIL_H

#include <vector>
#include <string>
#include <fstream>
#include <iostream>

std::vector<std::vector<int>> readField(std::string);
void printField(const std::vector<std::vector<int>>&);

#endif

At the start of every source file, .cc, we include libraries which hold definitions and function we want to use in that source file. The header file util.h will hold the reference to function in the source file util.cc. And each other source file that want to use function in util.cc only need to include util.h.

Not to make the compiler compile the header file for each source file that uses it, at the start of each header file we will define a specific tag. What happens is: we check if UTIL_H is define. If it is then don't continue. If it's not then define UTIL_H and continue.

As the source file will include the header file we can use the header file to include the standard libraries that the source file needs. The libraries we are going to use are: vector, string, fstream and iostream. Vector and String we will not get into but fstream is the library that is used for input streams and output streams of files. And iostream is library for input stream and output streams to the console. This is simplified but going forward this is how we will differentiate them.

Next we define the functions with structure:

return name(variable);

readFile function takes a string, the name, of the field we want to read and give it back as a matrix of ints.

printFiled is given a matrix of ints and doesn't return anything. printField have two interest bits: const and &. const at the beginning tells the compiler that the variable that is given will NOT be changed in the function. And & mark that this is a reference. This mean the variable that is given is the variable that is used. Without & it would be a copy of the matrix and if we would modify it it would be modification of the copy and not the original. The & reference means we save memory by not copying the matrix.

We are now going to implement these

// util.cc

#include "util.h"

using namespace std;

vector<vector<int>> readField(string name) {
  ifstream is(name);
  char c;
  vector<vector<int>> field;
  vector<int> row;
  int i;

  while(is.get(c)) {
    i = (int) c - '0';
    if (i == 0 || i == 1)
      row.push_back(i);
    if (c == '\n') {
      field.push_back(row);
      row.clear();
    }
  }
  return field;
}

void printField(const vector<vector<int>>& field) {
  for(int i = 0; i < field.size(); ++i) {
    for(int j = 0; j < field[i].size(); ++j)
      cout << field[i][j];
    cout << endl;
  }
}

First is the inclusion of the header file for util. Next is the decleration of using namespace std. This mean anything from standard libraries, the ones we included in the header, doesn't need a prefix of std:: before them.

Declaration of readFile. It takes a name, as string, as input. It then open a ifstream, input fstream, of the file with given name. A few more variables are decleared. Char c which will be used when we read from the file, matrix field which will hold the town population, vector row which is rows in the matrix (as these need to be added into the matrix) and int i which we will read the char to.

Then starts the loop of the file. As long as there is an input from the file the while-loop will continue. A char is read from the file and get converted to an int. If it is a human, 0, or a zombie, 1, we will add it to the row. If the char is a new line we add the row to the matrix and clear the row, as we will start a new row. When all is done the matrix get returned.

Declaration of printFiled. As mentioned above, a reference of the matrix is given. As the function will only print the content of the matrix it can be declared const, as nothing will be changed. Two for-loop to loop through the matrix and print each spot. At the end of a row we our self start a new row of output.

The main source file:

#include <iostream>
#include <vector>
#include <stdlib.h>

#include "util.h"

int main(int n, char** arg) {
  std::vector<std::vector<int>> field = readField(arg[1]);
  std::vector<std::pair<int,int>> coord_list;

  printField(field);

  int number_of_groups = 0;

  for(int y = 0; y < field.size(); ++y)
    for(int x = 0; x < field[0].size(); ++x) {
      if (field[y][x] == 1) {
        number_of_groups++;
        coord_list.emplace_back(x,y);
        while(coord_list.size() > 0) {
          std::pair<int, int> coord_pair = coord_list.back();
          coord_list.pop_back();
          group(field, coord_pair.first, coord_pair.second, coord_list);
        }
      }
    }
  std::cout << "Number of zombie groups are: " << number_of_groups << std::endl;
}

This is how the complete main will look. The implementation of group, from util, isn't presented yet yet we will talk about it.

The two argument for main file is how many input from the command line and the name, character array, of each input. As we run this program we will give it files where we have defined the field of the town we are observing.

As we have already gone through most of the functions the main method make sense. We first read the file of the field and save it to a matrix. We then create a vector of pairs. This is used as a reference of coordinate for the matrix where we find zombies. Next we print the matrix, to show how the zombie infested town looks like.

We then start looping through the matrix to start calculating how many groups there are. When we find a zombie, a 1, we append 1 to the sum of already found groups of zombies. We then add the coordinate of the zombie we found to the vector. Then we start looping through the coordinate vector. This act as a queue. To get ahead of ourself: when we find a zombie we add it to the coordinate queue. As long as there are zombies in coordinate queue we still working on the same group. When no zombie coordinate is in the vector, the queue, we continue.

Next we get a zombie from the queue and call the function group which takes argument: the matrix, x and y coordinate and the queue.

At the end of the program we print how many groups we found.

Updating header file:

// util.h
void group(std::vector<std::vector<int>>&, int, int, std::vector<std::pair<int,int>>&);

Add this before the #endif in util.h.

Updating source util.h file:

void group(vector<vector<int>>& field, int x, int y, vector<pair<int,int>>& coord_list) {
  if (x < 0 || x > size_x - 1)
    return;
  if (y < 0 || y > size_y - 1)
    return;
  if (field[y][x] == 0)
    return;
  field[y][x] = 0;
  coord_list.emplace_back(x, y - 1);
  coord_list.emplace_back(x, y + 1);
  coord_list.emplace_back(x - 1, y);
  coord_list.emplace_back(x + 1, y);
}

In the main file we talked about the argument of this function. The first two if-statement is to observe that the coordinate isn't outside the matrix. Next we look if the spot is human or zombie. If human we won't do anything. If zombie we continue. We transform the spot to a 0 (or you could use anything representing that a spot have been observed). And we add the coordinates around that spot to the queue. Both horizontal and vertical. This means, when we find a zombie we add to the queue all coordinate around it to observe them.

Conclusion

The output from both fields above:

$ ./run medium.csv
100000
010000
011000
001000
000011
Number of zombie groups are: 3

The program found 3 groups of zombies in the medium town. As can be observed we can confirm this is correct.

$ ./run hard.csv
Number of zombie groups are: 1

The other, 100k row file, have 1 zombie group.

There are many different ways to solve the above problem. You could have, or maybe you did, solved it with using a recursive method. And that would have been fine. But the second field, the 100k large one, is to highlight a problem. Depending on system the main memory of holding the field is around 11MB. Yet a recursive solution would throw a stack overflow. That is as we go down the path of zombie next to each other the number of calls and number pointers needed to store the callback grows. Even with 11MB memory to hold the field a 16GB RAM computer would get stack overflow.

Next Code Dojo in October.