This project is part of the official curriculum at School 42.
At School 42, almost every project must be written to comply with a coding standard (also known as the "Norm"). As a result, the implementation of certain parts may appear strange.
- Official instructions
- Code documentation
- Algorithm explanation
- This project practices the following algorithmic topics
- minimum cost maximum flow (Ford-Fulkerson, Suurballe)
- path search in directed graphs (BFS, Dijkstra, Bellman-Ford)
- sorts (quick sort, insertion sort)
- efficient data representation (priority queues, graphs, arrays, queues, linked lists)
To compile, run
git clone https://github.com/almayor/lem-in
cd lem-in
git submodule --init --recursive
make
Then try some example maps
./lem-in < example-maps/flow-thousand.txt
or generate your own
./generator-osx --flow-thousand | ./lem-in
(NOTE you could use generator-linux
to run the generator on Linux.)
Your can check that a generated solution is correct using the provided Python script check-solution
./lem-in < {your-map} | ./check-solution
Alternatively, you can run the whole batch of included tests with
make test
I have written a detailed PDF to outline my thought process when designing the algorithm. Please have a look if you're interested.
- https://courses.csail.mit.edu/6.854/06/scribe/s12-minCostFlowAlg.pdf
- http://www.macfreek.nl/memory/Disjoint_Path_Finding
- https://en.wikipedia.org/wiki/Suurballe%27s_algorithm
We are grateful to the entire team behind School 42 and its Moscow branch, as well as to my fellow students for help and support. Some ideas for tests found in example-maps
are borrowed from a similar project by davhojt.
If you have any questions, please contact me on Github.