/rewards-system

Primary LanguageClojureEclipse Public License 1.0EPL-1.0

Reward System

Project Organization

The project is divided in the five namespaces below:

  • Adapter

Functions that intermediate input and output with the logic functions.

  • Data

Functions related to insert and manage data.

  • Logic

Functions that compose the main logic of reward system.

  • Handler

Routes of endpoint to receive input and/or show output.

  • Utility

Utility functions that are needed and used in others namespaces.

Principal Algorithm

The main function is bfs that is a recursive function that explore nodes by theirs levels. Is an implementation of the breadth-first search (BFS) algorithm for traversing the graph. Produces a lazy-seq of points for each node visited, it means that only calculate the necessary like (take 2 (bfs args)) only returns the seq of the first two points of nodes visiteds.

Detailed flow of input:

1 2

1 3

3 4

2 4

4 5

4 6

The graph below represents the data structured used in the solution. Note that inviteds and confirmed-inviteds are defined before by using sets in insertion (people that invited someone are confirmed-inviteds).

Graph

The states used are:

  • Levels: A hash-map of levels of each node.

  • Visited: Nodes that are already been visiteds in the tranversing algorithm.

  • Adjacent: Nodes to be visited in a queue.

  • Vertice: Current node.

  • Inviteds: Nodes directly connected to vertice.

  • Confirmed-inviteds: Quantity of inviteds that are confirmed-inviteds.

  • Level: Level of vertice.

  • Points: Intermediate points of vertice calculated by (1/2)^level * number of confirmed inviteds.

Iteration 1

Graph

Iteration 2

Graph

Iteration 3

Graph

Iteration 4

Graph

Iteration 5

Graph

Iteration 6

Graph

Result

Points of 1 = 2 + 0.5 + 0.0 + 0.0 + 0.0 + 0.0 = 2.5

To calcute rewards points of other nodes is necessary to call bfs with the target node being the start-point.

Paralellism With Future

The run function in reward-system.adapter use future to parallelize the count of node reward points. And use deref to wait until all futures are done to show result. Since ranking is an atom (thread safe and retriable), the use of future has no damage to the result consistency.

The old-run function in reward-system.adapter count the node reward points sequentially.

Times of executation using future and doing sequentially

Sample-in (Input located at "resources/sample-in" in the project that have 6 lines)

Parallel

Using Run

Sequential

Using Old-run

In (Input located at "resources/in" in the project that have 200 lines)

Parallel

Using Run

Sequential

Using Old-run

Therefore, the parallelism technique has more performance gain with larger inputs.

Execute

$ lein ring server

Usage Examples

Home page

$ curl http://localhost:3000/

Get Ranking

$ curl http://localhost:3000/ranking

Insert a file containg the input

$ curl -H "Content-Type: application/json" -X POST -d '{"path": "path/to/file"}' http://localhost:3000/insert/file

Example

$ curl -H "Content-Type: application/json" -X POST -d '{"path": "resources/sample-in"}' http://localhost:3000/insert/file

Insert

THe inviter and invited value must be strings representing numbes like "1".

$ curl -H "Content-Type: application/json" -X POST -d '{"inviter": "inviter", "invited": "invited"}' http://localhost:3000/insert

Example

$ curl -H "Content-Type: application/json" -X POST -d '{"inviter": "1", "invited": "2"}' http://localhost:3000/insert

Test

$ lein midje