DEV Community: Chris

Code Dojo #4 Christmas Special: Reindeer race

Chris — Wed, 11 Dec 2019 22:45:56 +0000

Intro

The code for this monthly challenge is at git repository. On this month challenge there will be a complete server and a template client to communicate with the server. Unfortunately there won't be any new C++ code for this challenge.
I won't be presenting any solution for this.

Code Dojo

This Code Dojo is a Christmas special. It's a reindeer race, who is the fastest reindeer to help Santa to deliver present to all the children. But unfortunately there is a snowstorm and the reindeer is blind.

The code is divided into two parts: Server and Client.

The Server which holds the obstacle course for the reindeer that want to compete to be on the Santa team. Client is each reindeer that want to compete. One Client will register with the Server and get a UUID that identify that reindeer.

The Server have five endpoints

@RequestMapping(method = RequestMethod.POST, value = "/{id}/drawMap/{map}")
public ResponseEntity drawMap(@PathVariable(value = "id") UUID id, @PathVariable(value = "map") String map);

@RequestMapping(method = RequestMethod.POST, value = "/{id}/clear")
public ResponseEntity clearMap(@PathVariable(value = "id") UUID id);

@RequestMapping(method = RequestMethod.POST, value = "/{id}/startRace")
public ResponseEntity startRace(@PathVariable(value = "id") UUID id);

@RequestMapping(method = RequestMethod.POST, value = "/createBlindeer/{color}")
public ResponseEntity<CreateDeerDto> createBlindeer(@PathVariable(value = "color") String color);

@RequestMapping(method = RequestMethod.POST, value = "/{id}/move/{move}")
public ResponseEntity<MovedDeerDto> moveRaindeer(@PathVariable(value = "id") UUID id, @PathVariable(value = "move") Move move);

The master ID for the Server is: 0ef506e8-5f6b-45ed-a81a-53eab6d7eb6b.
Use this when communicating with the endpoints a Client shouldn't touch. There are three maps already implemented with two types of obstacle and one type of environment, but you are more than welcome to add as many as you like. Ice environment make the reindeer move faster in the direction it is going.

The clear endpoint is to wipe the screen.

startRace endpoint let the reindeer out of their boxes and they can start going down the course.

createBlindeer take a color as path variable. It can be any of the standard colors. And the response will be the ID that identify the reindeer.

move endpoint has two path variable: one that identify the reindeer and a move variable. Four moves are implemented: Up, Down, Left and Right. A reindeer can't move until the race have started. The response will be 200 with a body. The body will have a SUCCESS, if the movement succeeded, or a FAIL, if the reindeer bump into something. The body will also tell the coordinates where the reindeer is.

To run the program, follow these steps:

Start the server - Server side
Draw the map - Server side
Create reindeer - Client side
Start the race - Server side
Move the reindeer - Client side

Set up a Server, gather some friends that each implement a Client with a pathing algorithm and see who can race down the track fastest.

Code Dojo #3: Low latency

Chris — Thu, 21 Nov 2019 21:04:15 +0000

Update

I have added a git repository where solutions to the different dojos will be. On the repository will also be what is needed for each challenge.
For this Code Dojo I will unfortunately not use C++ but Java instead. That is because this will be a microservice Code Dojo that will have some minimum CS in it. And right now I'm working on creating microservices in C++ I haven't gotten to the point where I run it with working requests.

Code Dojo

Category: Software Engineering and Computer science
Restriction: Non
Time: Small

You have a large set of data, represented by range.csv. The dataset has over 1 million rows. And data is stored in a database. The challenge is to retrieve the data with low latency as possible when a request comes in.

I had this problem at work. We had 500k rows of data in a database and the latency couldn't be slower than 500ms.

Solution

In the repository is a template Spring Boot microservice. Before diving into the code we need to discuss how to solve the problem.

Jeff Dean from Google visualize latency

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

This chart can give us some help how to minimize the latency for this problem. Comparing storing the data in a database to memory (or cache) we see a great increase in performance. But even if we can access the data from memory, it becomes a question how to get it fast. With that we need to look at algorithms. The one I shall implement is Binary Search which have a Big O notation of O(log(n)). And to Binary Search for us to use Binary Search, the data must be sorted which I will implement quicksort that has Big O notation of O(n log(n)).

There are many guides out there on how Spring Boot works, and how to get a service up-and-running so I will not go into that here.

To start with, a new Service will be created.

import ...

@Service
public class RangeService {

    private final List<RangeEntity> rangeList = new ArrayList<>();

    private final RangeRepository rangeRepo;

    private static final int BATCH_SIZE = 4000;

    private final Comparator<RangeEntity> compareRange = 
        Comparator.comparing(RangeEntity::getLowerBin);

    public RangeService(RangeRepository rangeRepo) {
        this.rangeRepo = rangeRepo;
    }

}

The important pieces of the service have been included here. The list will be our cache and contain the rows from the database. The RangeRepository will be the communication where the reading will happen. Not to read whole data at one go, it will be done in batches of 4000. And for later use when doing the binary search,

We can't start the loading from the database until it's up-and-running and we can't be sure that will happen when this constructor is called. We will use EventListener from Spring Framework to wait until the whole application is up before initiating the loading.

@EventListener(ApplicationReadyEvent.class)
public void handleApplicationStarup() {        
    initializeCache();
}

We can now implement initializeCache().

private void initializeCache() {
    Slice<RangeEntity> rangeOnPage;

    Pageable page = new PageRequest(0, BATCH_SIZE);
    while ( true ) {
        rangeOnPage = rangeRepo.findAll(page);
        rangeList.addAll(rangeOnPage.getContent());
        if (!rangeOnPage.hasNext() )
            break;
        page = page.next();
    }

    sortRange(rangeList, 0, rangeList.size());
}

A few bits here. Using pageable on findAll to get pages from the database. This means we get small batches, as we defined above the size, from the db without getting all of it and also keeping track of which data we have already retrieved and which data we have left. Slice works with pageable by saying if there is more data left or if we have reached the end. The while-loop will then request 4000 entries from the db each iteration and store them into our list. When there is no more data left to retrieve we break the loop and start sorting our list.

private void sortRange(List<RangeEntity> list, int start, int end) {
    if (start < end) {
        int pivot = pivot(list, start, end);
        sortRange(list, start, P - 1);
        sortRange(list, P + 1, end);
    }
}

Quicksort as we will implement it is a Divide and Conquer algorithm. It will pick a element from the list as a pivot, place the pivot in the middle while having all the element smaller as the pivot come earlier in the list and all the element larger being come later. Then it runs the algorithms on these two parts and continue until it's sorted.

There are different ways to choose the pivot element from the list. It could be the first, it could be the last or a random element. Or median from the list. I usually go for the last element on the list.

private int pivot(List<RangeEntity> list, int start, int end) {
    int pivot = list[end].getLow();
    int temp, p = start;

    for (int i = start; i < end; i++)
        if (v[i].getLow() <= pivot) {
            temp = v[i].getLow();
            v[i].setLow(v[p].getLow());
            v[p].setLow(temp);
            p++;
        }
    temp = v[end].getLow();
    v[end].setLow(v[p]);
    v[p].setLow(temp);
    return p;
}

As stated, I choose the last element as pivot here. As we need to keep track of where we are on moving element, we initiate p as our pointer where we are on the list. We then start a for-loop through the list. Each element we compare with our pivot. If they are larger we don't do anything about them. If they are smaller than the pivot we switch the value to the value our pointer is looking at. When we are done with this section of the list, section start to end, we switch the pivot value to the value we are currently looking at and return that value.

We have now implemented our quickSort for our list.

Next is the implementation if a request comes in and ask for the data in a specific range.

public RangeEntity findRange(int range) {
        return binarySearchRange(0, list.size(), range);
}

private RangeEntity binarySearchRange(int start, int end, int range) {
    if (end >= start) {
        int mid = start + (end - start) / 2;

        if (list[mid].getLow() < range && list[mid].getHigh() > range)
            return list[mid];

        if (list[mid].getLow() > range)
            return binarySearchRange(start, mid - 1, range);
        return binarySearchRange(mid + 1, end, range);
    }
    return null;
}

And here is the implementation of the binary search for our list. Binary search works that we compare our value with the element in the middle of the list. If our value is larger than the value in the middle, we search in the upper part. We do another call with the middle value as our starting point, the largest as our end and again compare our value with the value in this range.
If our value is smaller than the middle, we search for it in the lower part. As we can see, the binary search needs a sorted list to work.

Conclusion

We have now implemented all the parts needed for this microservice to be in use. We can have a large set of data in our db and have a minimum of latency for each request to retrieve the data. We have learned to implement two good algorithms that every engineers should know: quick sort and binary search. And we have worked with a microservice.

Next Code Dojo in December.

Code Dojo #2: Sudoku

Chris — Thu, 24 Oct 2019 21:52:53 +0000

Code Dojo

Category: Problem solving
Restriction: Non
Time: Small

Write a sudoku solver that can solve following sudokus:

Bench mark each run for the solver.

Solution

Hope all went well. 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 algorithm will be implemented in main.cc with helper methods in util.cc. 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 <fstream>
#include <iostream>
#include <string>
#include <vector>

std::vector<std::vector<int>> readFile(const std::string);
void printSudoku(const std::vector<std::vector<int>>&);
bool canPlace(const std::vector<std::vector<int>>&,int,int,int);

#endif

Unlike previous Code Dojo solution, these are the methods we need to use. One method to read the file that contain the sudoku, one method to print the sudoku and one method that indicate if we can place a number at a spot.

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_type);

readFile function takes a string, the name, of the field we want to read and give it back the sudoku as a matrix of ints. const in front of the string indicate that we are only going to read the value and the method won't change anything.

printFiled is given a matrix of ints and doesn't return anything. printField have one interest bit: &. & 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

#include "util.h"

using namespace std;

#define SIZE  9

vector<vector<int>> readFile(const string name) {
  ifstream in(name);
  char c;

  vector<vector<int>> file(SIZE, vector<int>(SIZE,1));
  int x = 0, y = 0;
  while(in.get(c)) {
    if (c == '\n') {
      file[++y];
      x = 0;
      continue;
    } 
    file[y][x++] = (int) c - '0';
  }
  return file;
}

void printSudoku(const vector<vector<int>>& sudoku) {
  for (int i = 0; i < SIZE; ++i) {
    if (i % 3 == 0 && i > 0)
      cout << endl;
    for (int j = 0; j < SIZE; ++j) {
      if (j % 3 == 0 && j > 0)
    cout << " ";
      cout << sudoku[i][j];
    }
    cout << endl;
  }
}

we will implement the method 'canPlace' later as that have some private methods.

First is the inclusion of the header file for util. Next is the declaration 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. Then we define SIZE to be 9 as that the size of a sudoku. This mean, when we use SIZE in our program we will reference 9.

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 declared. The while-loop will read character from the file and populate char c until there is nothing else to read. Then there is a check to see if there is a new line (not something we will populate our matrix with). There is an update to the matrix, to start a new row. Other wise the program cast the character to an integer and add it to the matrix, that hold our sudoku. The method end with returning the sudoku in the matrix.

Declaration of printSudoku. It will not modify the sudoku and only need a reference to it. By printing we want gaps after 3 numbers. And after 3 rows we want an empty row so better visualize the sudoku.

The main source file:

// main.cc
#include <iostream>
#include <vector>

#include "util.h"

#define SIZE 9

bool backTrack(std::vector<std::vector<int>>&);

int main(int argn, char** argv) {
  if (argn < 2) {
    std::cout << "Wrong number of arguments\n";
    return 1;
  }
  std::vector<std::vector<int>> sudoku = readFile(argv[1]);
  printSudoku(sudoku);
  std::cout << "--------------------------\n";
  backTrack(sudoku);
  printSudoku(sudoku);
  return 0;
}

bool backTrack(std::vector<std::vector<int>>& sudoku) {

  for(int j = 0; j < SIZE; ++j) {
    for(int i = 0; i < SIZE; ++i) {
      if (sudoku[j][i] == 0) {
    for (int n = 1; n <= 9; ++n) {
      if (canPlace(sudoku, n, i, j)) {
        sudoku[j][i] = n;
        if (!backTrack(sudoku))
          continue;
        else
          return true;
      }
    }
    sudoku[j][i] = 0;
    return false;
      }
    }
  }
  return true;
}

This is how the complete main will look. backTrack method is our algorithm to solve the sudoku.

Start by including libraries that will be in use. The include our own creation, util. As sudoku is square with size 9 we define SIZE to be 9. We then define method backTrack, like util.h define methods for util.cc.

Declaration of main. The two arguments are number of inputs to the program and what they are, representing as char*. To simplify think char* as string. The program expect the given file that contain a sudoku. If there is less than 2 arguments to the the program wasn't given a sudoku to solve and will quit.
We then read the file and get a sudoku from it in matrix format. We print the sudoku to the terminal to show the unsolved sudoku. Next we print a line of dashes to separate the unsolved sudoku to the solved sudoku.
A call to backTrack algorithm and print the solved sudoku.

Declaration of backTrack. This is the main algorithm to solve sudokus. Is a basic, brute force, simple solution. It will basically try a number on a spot until it find one that fit then continue to the next spot. If a spot can't be represented by any number it will go back and change a previous number until all spot has a number.
To break it down as it is written: loop through the sudoku. When a spot is reached that is represented by 0, that spot need to be filled in. Start with 1 throughout 9 to see which number can fit. Now we call the method in util canPlace(). This will check if the number interfere either along the horizontal or vertical line or inside the box. If returned true, the number can the placed in the spot. We do a recursive call to backTrack after the spot is represented by that number.

The backTrack have returned type bool. If the algorithm return false, it means that a spot can't be represented by any number between 1-9. This mean it will go "up" in the recur call which, looking at the if-statement, the algorithm will test another number. IF the backtrack have solved it, it will return true and go back up until it is in the main method again. Before we go "up" in the recur line, if a spot can't be represented, we need to revert the spot to 0 if we had change the number.

This is the algorithm. Time to look at the helper methods.

// util.cc
bool placeLine(const vector<vector<int>>& sudoku, int n, int x, int y) {
  for (int i = 0; i < SIZE; ++i) {
    if (sudoku[y][i] == n)
      return false;
  }
  for (int i = 0; i < SIZE; ++i) {
    if (sudoku[i][x] == n)
      return false;
  }
  return true;
}

bool placeBox(const vector<vector<int>>& sudoku, int n, int x, int y) {
  int lowX = x - x%3;
  int lowY = y - y%3;

  for (int i = lowY; i < lowY + 3; ++i)
    for (int j = lowX; j < lowX + 3; ++j)
      if (sudoku[i][j] == n)
    return false;
  return true;
}

bool canPlace(const vector<vector<int>>& sudoku, int n, int x, int y) {
  return placeBox(sudoku, n, x, y) && placeLine(sudoku, n, x, y);
}

Declaration of canPlace. The arguments is reference to the sudoku, method won't change it thus const. Number n we want to test on the given spot. The coordinate x and y where we observing in the sudoku. The method until does two things: call placeBox and placeLine. Basically checking "can this number be placed in the box we currently in and does any number interfere with it on the line?"

Declaration of placeBox. Same arguments of canPlace. We build lowX and lowY out of the spot we are looking at. A box is 3x3 in a sudoku and we need to be in the correct box while comparing numbers. It loops through all the spot in the box and see if any number is the same to the number that we want to place. If it finds, return false. If so such number interfere we return true.

Declaration of placeLine. Same arguments as canPlace. All that is done here is loop horizontal and compare number with the number we want to place then loop vertical and compare. Return false as soon we see a number that is equal to the number we want to place. Return true if we can place.

Conclusion

The output from medium and challenge above:

$ time ./run medium
812 437 596
439 658 217
657 912 843

174 265 938
398 174 625
526 893 174

245 381 769
761 549 382
983 726 451

real    0m0.060s
user    0m0.026s
sys 0m0.004s

and

$ time ./run hard
987 654 321
246 173 985
351 928 746

128 537 694
634 892 157
795 461 832

519 286 473
472 319 568
863 745 219

real    1m4.001s
user    0m55.984s

As can be seen, the first sudoku is quite straightforward to solve with the backTracking algorithm. It take around 60 ms to solve it. The second one is constructed to be complicated. A brute force algorithm like backTracking took around 1 min to solve it. I did implement annealing algorithm which is to randomize number and place on empty spot, calculate number of errors and change number (those that were place) to minimize number of errors until it is solved. But because of the complexity of the sudoku it could never solve it. I tried solution other people made but even them couldn't solve the challenge. This make it a good challenge, as it need a good algorithm to solve it or tricks with brute forcing to save seconds here and there.

Next Code Dojo in November

Code Dojo #1: Zombie town

Chris — Sun, 29 Sep 2019 09:50:15 +0000

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:

and

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

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.

Creating REST API with CRNK, Part 2

Chris — Thu, 26 Sep 2019 08:17:07 +0000

In Part 1 we created a basic REST application with Spring Framework and CRNK. We had a basic model how our data is representative in the database that external user can GET, POST or PUT.

External facing data

In previous article we only worked with one model, knowing that every information that is externally requested should be given in full. But if you construct an API where the model may hold information that an external user should not see, say you use some data to base filters on, there is a way to hide this. Two models are created, one for the external use and one for the repository. Then a mapper will be created that link between the external model and the internal model.

This is done with implementing JpaModuleConfigurator and overriding configure. The parameter is JpaModuleConfig which let you configure the CRNK application. Here below we add a repository where we bind the two models, external and internal, with a mapper.


package com.test.store.configuration;

import com.test.store.model.ModelMapper;
import com.test.store.model.ModelExternal;
import com.test.store.model.ModelEntity;
import io.crnk.jpa.JpaModuleConfig;
import io.crnk.jpa.JpaRepositoryConfig;
import io.crnk.spring.setup.boot.jpa.JpaModuleConfigurer;
import org.springframework.stereotype.Component;

@Component
public class JpaModuleConfigurator implements JpaModuleConfigurer {

  @Override
  public void configure(JpaModuleConfig jpaModuleConfig) {
       jpaModuleConfig.addRepository(JpaRepositoryConfig.builder(
                                     ModelEntity.class,
                                     ModelExternal.class, new ModelMapper())
                      .build());
    }
}

And for JpaModuleConfigurator to use the mapper it needs to implement JpaMapper where you specify the two models and override method to jump between them.


package com.test.store.model;

import com.test.store.model.ModelExternal;
import com.test.store.model.ModelEntity;
import io.crnk.jpa.mapping.JpaMapper;
import io.crnk.jpa.query.Tuple;
import org.springframework.stereotype.Component;
import javax.persistence.EntityManager;
import javax.persistence.PersistenceContext;

@Component
public class ModelMapper implements JpaMapper<ModelEntity, ModelExternal> {

  @PersistenceContext
  private EntityManager entityManager;@Override
  public ModelExternal map(Tuple tuple) {
    ModelExternal dto = new ModelExternal();

    ModelEntity entity = tuple.get(0, ModelEntity.class);
    dto.setData(entity.getData());
    return dto;
  }

  @Override
  public ModelEntity unmap(ModelExternal dto) {
    ModelEntity entity;
    if (dto.getId() == null) {
      entity = new ModelEntity();
    } else {
      entity = entityManager.find(ModelEntity.class, dto.getId());
      if (entity == null) {
        throw new RuntimeException("Couldn't find entity");
      }
    }
    return translateToEntity(dto, entity);
  }

  private ModelEntity translateToEntity(ModelExternal dto, ModelEntity entity) {
    entity.setData(dto.getData);
    return entity;
  }
}

The external user can still use CRNK default search query for the model but you can control what will be seen. If you have data that you want to hide it can be controlled in the mapper and in the external model you don’t have that data.

Modifying repository data

Above gives an opportunity to hide data from external user which may be present in the database. A question and a problem may be if information is going to be presented to the user which is not present in the database. What if, based on query to the API, we want to change the response back?

For this we can’t connect the two models with JpaModuleConfigurator. Both models need to have their own repositories where the internal facing one is the one connecting to the database. The external facing repository will hold the internal facing one as an attribute to be used in the different calls.

For this example, we are assuming a query has been made to the API with a age and we want to give back the every person and their age difference to the query. The new attribute to our ModelExternal is

private int ageDifference;

In previous article we hold the data in memory. This time we are going to create a repository which is connected to a database where data is persisted. As previous, we state which model the repository is using and what attribute is the identifier.


package com.test.store.repository;

import com.test.store.model.ModelEntity;
import org.springframework.data.jpa.repository.Query;
import org.springframework.data.repository.CrudRepository;
import org.springframework.data.repository.query.Param;
import org.springframework.stereotype.Service;import java.util.List;
import java.util.UUID;

@Service
public interface ModelEntityCrudRepository extends CrudRepository<ModelEntity, UUID> {
}

This repository doesn’t need to hold much compare to ResourceRepositoryBase as CrudRepository is the communicator with database and we’re not interested into changing anything here. If you want to make specific calls inside your API to the database you can always create specific queries to the database, for example

@Query("select s from model s where partner_id = :partnerId")  
List<StoreEntity> findByPartnerId(@Param("partnerId") String partnerId);

The external facing repository will be a bit trickier to set up. We need to define it as a CRNK repository but also connect it with our ModelEntity above. First we create an interface extending ResourceRepositoryV2 , for us to use CRNK default queries.


package com.test.store.repository;

import com.test.store.model.store.Store;
import io.crnk.core.repository.ResourceRepositoryV2;
import java.util.UUID;

public interface ModelExternalRepository extends 
                             ResourceRepositoryV2<ModelExternal, UUID> {}

Next comes the main repository.


package com.test.store.repository;

import com.test.store.model.ModelExternal;
import com.test.store.model.ModelEntity;
import com.test.store.translator.ModelTranslator;
import io.crnk.core.boot.CrnkBoot;
import io.crnk.core.exception.BadRequestException;
import io.crnk.core.exception.RepositoryNotFoundException;
import io.crnk.core.queryspec.QuerySpec;
import io.crnk.core.repository.ResourceRepositoryBase;
import io.crnk.jpa.JpaEntityRepository;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.context.ApplicationContext;
import org.springframework.stereotype.Component;
import java.util.Comparator;
import java.util.List;
import java.util.UUID;
import java.util.stream.Collectors;

@Component
public class ModelExternalRepositoryImpl extends 
                               ResourceRepositoryBase<ModelExternal, UUID> implements ModelExternalRepository {

  private JpaEntityRepository modelEntityJpaRepository;@Autowired
  ApplicationContext appContext;

  public ModelExternalRepositoryImpl() {
    super(ModelExternal.class);
    modelEntityJpaRepository = null;
  }

  @Override
  public ModelExternal findOne(UUID id, QuerySpec querySpec) {
    if (modelEntityJpaRepository == null) {
      initJpaRepositoryEntity();
    }
    return ModelTranslator.map((ModelEntity)  modelEntityJpaRepository.findOne(id, querySpec));
  }

  @Override
  public ModelExternalResourceList findAll(QuerySpec querySpec) {
    if (modelEntityJpaRepository == null) {
      initJpaRepositoryEntity();
    }
    ResourceList<ModelEntity> modelEntityResourceList = modelEntityJpaRepository.findAll(querySpec);
    ...

modelResourceList.addAll(ModelTranslator.translate(modelEntityResourceList));
    ...

    return modelResourceList;
  }

  /**
   * Initialize the JpaRepository.
  */
  private void initJpaRepositoryEntity() {
    CrnkBoot crnkBoot = appContext.getBean(CrnkBoot.class);
    modelEntityJpaRepository = crnkBoot.getModuleRegistry()
                                           .getRepositories()
                                           .stream()
                                           .filter(repository -> repository instanceof JpaEntityRepository)
                                           .map(repository -> (JpaEntityRepository) repository)
                                           .filter(repository -> repository.getEntityClass().equals(ModelEntity.class)
                                                           && repository.getResourceClass().equals(ModelEntity.class))
                                           .findFirst()
                                           .orElseThrow(() -> new RepositoryNotFoundException("ModelEntity JpaRepository not found"));
    }

  public static class ModelResourceList extends ResourceListBase<ModelExternal, MetaInformation, LinksInformation> {}
}

We will break this up in importance.

One of the more important bit here is initJpaRepositoryEntity. This is because it can’t be controlled when repositories are initialised and to autowired the internal repository could throw error saying it’s not there yet. To circumvent this with a hack the first call to the data will the two repositories. What happens is that it will search for our ModelEntity repository that is connected to the database and load into this repository.

Breaking in steps:

First we search for our CrnkBoot bean which will hold all our repositories.
Load all the modules register with CrnkBoot and get all of the repositories
Start by going through them and look for each repository which is a JpaRepository
For each JpaRepository look for the one that is connected to our ModelEntity class

After all of these steps we have our database repository loaded in our external facing repository.

A external call will hit our external facing repository which is connected to our database repository. It will get the information from it with the query (and if needed you can always modify the query by creating a new and send that into the internal repository). We get some data out of it and translate that into external facing data. With the translation we can add data that we want the external user to see.

Above is just two ways to separate data from external users and internal user. And we still keep the default CRNK behaviour, with filtering and sorting. A last tip with using two repository and sorting is to modify the query to the repository then get more data than you need. Sort this data in your external repository and give only a set of data back.

Add new filtering

In part 1 we talked about filtering and what the standard filtering CRNK will give you. But later you may want to add filtering for the specific data your repository hold.

To add a filter you need to extend filterOperator


package com.test.store.filter;

import io.crnk.core.queryspec.FilterOperator;

public class PersonFilterOperator extends FilterOperator {

  public PersonFilterOperator(String id) {
    super(id);
  }

  /**
   * Handle new filterOperator. Should in default pass if value2 (value given by request) is given.
   * @param value1 value from DB
   * @param value2 value from request
   * @return true if value from request isn't null
  */
  @Override
  public boolean matches(Object value1, Object value2) {
    /*
     This class and this method is only used for new FilterOperators. FilterOperators are used in making a request and using crnk filtering.
     Value 1 is the data from the DB and Value 2 is from the request. FilterOperator.LIKE may first check if value2 exist then later on
     check value1 == value2. As we don't want to check values on that level we are only interested to check if the user provided a value.
     */
    return value2 != null;
  }
}

The filter above doesn’t do anything more than checking the value that is passed with the request holds data. But you can modify method matches to fit what you want your filtering to do. Now just adding this class won’t add the filtering to your application but you need to add it to the Url mapper.


package com.test.store.configuration;

import com.test.store.filter.StoreFilterOperator;
import io.crnk.core.queryspec.FilterOperator;
import io.crnk.core.queryspec.mapper.DefaultQuerySpecUrlMapper;
import org.springframework.stereotype.Component;

@Component
public class PersonQuerySpec extends DefaultQuerySpecUrlMapper {

  public static final FilterOperator WITHIN= new PersonFilterOperator("WITHIN");
  public static final FilterOperator NEAR = new PersonFilterOperator("NEAR");
  public ModelQuerySpec() {
    super.addSupportedOperator(WITHN);
    super.addSupportedOperator(NEAR);
  }
}

We add a new filterOperator to DefaultQuerySpecUrlMapper so when a call comes in with the new filter CRNK knows what to do with it instead. The above example uses the same class as above which doesn’t do anything but a filter call now with

/person?filter[NEAR][age]=25

works. What is important when using your own filterOperator is, as mentioned in Part 1, that filter work both between the request to your API and the query from the repository to the underlying data structure. This mean that if using specific filterOperator you will have to implement a repository class to unpack your querySpec and modify the request.

Summary

Doing more specific things with CRNK can prove to be a problem as this article point out. CRNK give help with connecting two models, external and internal, to help hide data but if data is needed in the response it get trickier. There isn’t, what we have seen, a way to control how the repositories are loaded. This means that to have different repositories talking to each other hacks need to be put in place.

CRNK is relative new for now so hopefully some of these things can be simplified and the community grow around it.

Creating REST with CRNK

Chris — Mon, 23 Sep 2019 17:28:21 +0000

Note: This article was written, and suppose to publish, winter 2018

Microservices are more than common these days, and at Travelex we use them in various parts of the business. For many of the services we have been using Spring framework to make it easy to get a service up and running fast. As all the microservices are communicating with each other we adopted JSON:API standard. A library which builds upon JSON:API standard is the CRNK library.

Crnk is a native resource-oriented rest library where resources, their relationships and repositories are the main building blocks.

Combining Crnk and the Spring framework, we have got services up and running fast. Spring Boot creates a runnable service and CRNK helps to handle REST APIs communications. This article, and the next, will go through how to set up a service using CRNK. We will handle a more general sense of what CRNK is and later we going to talk about some challenges we faced when we wanted to do more advanced thing with CRNK.

CRNK

The minimum requirement to use this library is JAVA 8. We will only look at gradle and maven for this setup. For maven you add in your pom.xml the following packages:

<dependency>
  <groupId>io.crnk</groupId>
  <artifactId>crnk-setup-spring-boot2</artifactId>
  <version>${crnk.version}</version>
</dependency>
<dependency>
   <groupId>io.crnk</groupId>
   <artifactId>crnk-client</artifactId>
   <version>${crnk.version}</version>
</dependency>
<dependency>
   <groupId>io.crnk</groupId>
   <artifactId>crnk-validation</artifactId>
   <version>${crnk.version}</version>
</dependency>
<dependency>
   <groupId>io.crnk</groupId>
   <artifactId>crnk-security</artifactId>
   <version>${crnk.version}</version>
</dependency>
<dependency>
   <groupId>io.crnk</groupId>
   <artifactId>crnk-jpa</artifactId>
   <version>${crnk.version}</version>
</dependency>
<dependency>
   <groupId>io.crnk</groupId>
   <artifactId>crnk-monitor-brave4</artifactId>
   <version>${crnk.version}</version>
</dependency>

And for gradle you build.gradle looks as followed:

compile project(':crnk-setup:crnk-setup-spring-boot2')
compile project(':crnk-jpa')
compile project(':crnk-validation')
compile project(':crnk-home')
compile project(':crnk-ui')
compile project(':crnk-operations')
compile project(':crnk-security')
compile project(':crnk-data:crnk-data-facet')

With any of this the project is ready to use CRNK. And to use CRNK is quite easy. As a minimum it only need an annotation on a model class and a repository connected with that model class. A repository will handle the data for said model. It could either store it in itself as a hashmap or it could store the data in a data structure, e.g database.

Model and data

The model is the representation of the data the application have. The data needs to be stored in a repository which either hold the data in memory or can be connected to a database.

// Copyright (c) 2018 Travelex Ltd
package com.travelex.store.model;
import io.crnk.jpa.annotations.JpaResource;
import lombok.Data;
import javax.persistence.Entity;
@Data
@JpaResource(type = "person")
@Entity
public class Person {
  private String name;
  private int age;
}

In the above example the JpaResource will be the external connection to this resource when making POST, PUT or GET request. The annotation entity will connect us straight to the database we have as our underlying structure to hold data. We don't need to construct a repository class if we configure with using Entity.

Lombok

The Lombok package is what we use throughout our services which help us greatly to reduce code. The way lombok work is generating code for our class so we don't have to write about getters and setters and all those method a class is suppose to have. The annotation of Data bundles together different annotation to create getter, setters, toString, constructors and more so we only have to define the attributes of our model.

Repository

We now need to connect our resource to its data, and we'll do this by creating a repository. For simplicity, our repository will store our data in memory within a hashmap.

A resource, which the model is, need to connect to its data. This is usually done with a repository. The repository will either hold the data in memory, as hashmap, or it can be connected to a data structure, e.g database. A normal repository can look like:

// Copyright (c) 2018 Travelex Ltd
package com.travelex.store.model;
import io.crnk.core.queryspec.QuerySpec;
import io.crnk.core.repository.ResourceRepositoryBase;
import io.crnk.core.resource.list.ResourceList;
import org.springframework.stereotype.Component;
import java.util.HashMap;
import java.util.Map;
@Component
public class PersonRepository extends ResourceRepositoryBase<Person, int> {
  private Map<int, String> list = new HashMap<>();
  public PersonRepository() {
    super(Person.class);
  }

  @Override
  public void delete(int age) {
    list.remove(age);
  }

  @Override
  public <S extends Person> S save(S person) {
    list.put(person.getAge(), person.getName());
  }

  @Override
  public ResourceList<Person> findAll(QuerySpec querySpec) {
    return querySpec.apply(list.values());
  }
  ...
}

Filtering and CRNK

The JpaResource gives us features from CRNK how to query the data. Default options is filtering and sorting resources. With filtering you can have: EQ for equal values, LIKE for patterns, LT for lower than, LE for lower and equal, GT for greater than and GE for greater and equal. A typical filter call

/person?filter[EQ][age]=25

will look through the database for every entity where the data for age is equal to 25.

You can add your own filter operator as long as you handle the query in the repository correctly. Meaning that filterOperators are both on the request going into your server and the query request to the database. This will be handle in later.

Summary

With CRNK library you can create the REST APIs with minimum effort. It helps construct REST API for the service and the only thing we have to worry about is the data we need said service to handle. If you are using the Spring framework as we did with our test service here at minimum you would need less than 5 classes: the main class that start the SpringBoot application, the model class which represent our data and a configuration class that connect with a database.

CRNK is good to create simple REST APIs services that can hold data. It easy to use with SpringBoot and as developers we don't need to focus on the code to connect to our service. But as with CRNK being simple to connect with SpringBoot and setting up a service, if you need to configure something which is not standard in CRNK there will be a need to hack around this.