Fork of sources (C++) from book "Grokking Algorithms (2016) by Aditya Bhargava" created while study. Author of original sources - Aditya Bhargava @egonSchiele, https://adit.io/

ch01_binary_search.cpp

/*
 * Fork of sources (C++) from "Grokking Algorithms (2016) by Aditya Bhargava"
 * created while study.
 * Author of original sources - @egonSchiele, https://adit.io/
 */

#include <ctime>
#include <random>
#include <cstdint>
#include <cstdlib>
#include <iostream>

uint8_t my_value()
{
	std::random_device rd;
	std::mt19937 gen(rd());
	std::uniform_int_distribution<> dis(0, 100);
	return static_cast<uint8_t>(dis(gen));
}

//static const auto value = my_value();
int8_t value;

int8_t is_value_found(uint8_t expected_value)
{
	if (expected_value < value)
	{
		return 1;
	}
	else if (value < expected_value)
	{
		return -1;
	}

	return 0;
}

bool binary_search(uint8_t start, uint8_t finish, uint8_t& out)
{
	if (start == finish)
	{
		return false;
	}

	const auto length = static_cast<uint8_t>(finish - start);
	const auto expected_value = static_cast<uint8_t>(start + length / 2);
	const auto direction = is_value_found(expected_value);

	if (direction < 0)
	{
		if (finish == expected_value)
		{
			return false;
		}

		return binary_search(start, expected_value, out);
	}
	else if (0 < direction)
	{
		if (start == expected_value)
		{
			return false;
		}

		return binary_search(expected_value, finish, out);
	}

	out = expected_value;
	return true;
}

int main()
{
	uint8_t out;

	for (value = INT8_MIN / 2; value < INT8_MAX; ++value)
	{
		std::cout << "Input value = " << static_cast<int>(value) << std::endl;

		if (binary_search(0, 100, out))
		{
			std::cout << "Value = " << static_cast<int>(out) << std::endl;
		}
		else
		{
			std::cout << "Value not found." << std::endl;
		}
	}

	return EXIT_SUCCESS;
}

ch06_Breadth-first_search.cpp

/*
 * Fork of sources (C++) from "Grokking Algorithms (2016) by Aditya Bhargava"
 * created while study.
 * Author of original sources - @egonSchiele, https://adit.io/
 */

#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstdlib>
#include <iostream>

void assing_queue(
	const std::map<std::string, std::set<std::string>>& graph,
	const std::string& name, std::queue<std::string>& queue)
{
	if (0 == graph.count(name))
	{
		return;
	}

	const auto& friends = graph.at(name);

	for (const auto& f : friends)
	{
		queue.push(f);
	}
}

bool is_person_a_seller(const std::string& name)
{
	return !name.empty() && 'm' == name[name.size() - 1];
}

int main()
{
	std::map<std::string, std::set<std::string>> graph;
	
	graph["You"].insert({ "Alice", "Bob", "Claire" });
	graph["Bob"].insert({ "Anuj", "Peggy" });
	graph["Alice"].insert({ "Peggy" });
	graph["Claire"].insert({ "Thom", "Jonny" });
	graph["Anuj"];
	graph["Peggy"];
	graph["Thom"];
	graph["Jonny"];

	std::queue<std::string> search_queue;
	assing_queue(graph, "You", search_queue);

	while (!search_queue.empty())
	{
		const auto& person = search_queue.front();

		if (is_person_a_seller(person))
		{
			std::cout << person << std::endl;
			return EXIT_SUCCESS;
		}

		assing_queue(graph, person, search_queue);
		search_queue.pop();
	}

	std::cout << "Not found" << std::endl;
	return EXIT_SUCCESS;
}

ch07_algorithm_of_Dijkstra.cpp

/*
 * Fork of sources (C++) from "Grokking Algorithms (2016) by Aditya Bhargava"
 * created while study.
 * Author of original sources - @egonSchiele, https://adit.io/
 */

#include <map>
#include <set>
#include <cstdlib>
#include <iostream>

void init_graph_A(std::map<char, std::map<char, int>>& graph)
{
	graph.clear();

	graph['S']['A'] = 5;
	graph['S']['B'] = 2;

	graph['A']['C'] = 4;
	graph['A']['D'] = 2;

	graph['B']['A'] = 8;
	graph['B']['D'] = 7;

	graph['C']['D'] = 6;
	graph['C']['F'] = 3;

	graph['D']['F'] = 1;

	graph['F'];
}

void init_graph_B(std::map<char, std::map<char, int>>& graph)
{
	graph.clear();

	graph['S']['A'] = 10;
	
	graph['A']['C'] = 20;
	
	graph['C']['B'] = 1;
	graph['C']['F'] = 30;
	
	graph['B']['A'] = 1;

	graph['F'];
}

void init_graph(std::map<char, std::map<char, int>>& graph)
{
	graph.clear();

	graph['S']['A'] = 2;
	graph['S']['B'] = 2;

	graph['A']['B'] = 2;

	graph['B']['C'] = 2;
	graph['B']['F'] = 2;

	graph['C']['A'] = -1;
	graph['C']['F'] = 2;

	graph['F'];
}

void init(char start_node, const std::map<char, std::map<char, int>>& graph, std::map<char, int>& costs, std::map<char, char>& p)
{
	if (0 == graph.count(start_node))
	{
		return;
	}

	costs[start_node] = 0;
	const auto& neighbors = graph.at(start_node);

	for (const auto& n : neighbors)
	{
		costs[n.first] = n.second;
		p[n.first] = start_node;
	}

	for (const auto& n : graph)
	{
		if (costs.count(n.first))
		{
			continue;
		}

		costs[n.first] = INT32_MAX;
	}
}

bool find_lowest_cost_node(const std::map<char, int>& costs, const std::set<char>& processed, char& node)
{
	auto length = INT32_MAX;

	for (const auto& node_ : costs)
	{
		if (0 < processed.count(node_.first))
		{
			continue;
		}

		if (node_.second < length)
		{
			node = node_.first;
			length = node_.second;
		}
	}

	return INT32_MAX != length;
}

void process(std::map<char, std::map<char, int>>& graph, std::map<char, int>& costs, std::map<char, char>& p)
{
	char node;
	std::set<char> processed;

	while (find_lowest_cost_node(costs, processed, node))
	{
		const auto cost = costs[node];
		const auto& neighbors = graph[node];

		for (const auto& n : neighbors)
		{
			auto new_cost = cost + n.second;

			if (new_cost < costs[n.first])
			{
				costs[n.first] = new_cost;
				p[n.first] = node;
			}
		}

		processed.insert(node);
	}
}

int main()
{
	std::map<char, std::map<char, int>> graph;
	init_graph(graph);
	//
	std::map<char, int> costs;
	std::map<char, char> p;
	init('S', graph, costs, p);
	//
	process(graph, costs, p);
	std::cout << "S -> F " << costs['F'] << std::endl;
	char n = 'F';

	while (0 < p.count(n))
	{
		std::cout << n << " ";
		n = p.at(n);
	}
	
	std::cout << n << std::endl;
	return EXIT_SUCCESS;
}

ch08_find_best_station.cpp

/*
 * Fork of sources (C++) from "Grokking Algorithms (2016) by Aditya Bhargava"
 * created while study.
 * Author of original sources - @egonSchiele, https://adit.io/
 */

#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <iostream>

template<class T>
void association(const T& a, const T& b, T& c)
{
	c.clear();
	c.insert(a.cbegin(), a.cend());
	c.insert(b.cbegin(), b.cend());
}

template<class T>
void intersection(const T& a, const T& b, T& c)
{
	c.clear();

	for (const auto& a_ : a)
	{
		if (0 < b.count(a_))
		{
			c.insert(a_);
		}
	}
}

template<class T>
void difference(const T& a, const T& b, T& c)
{
	c.clear();

	for (const auto& a_ : a)
	{
		if (0 == b.count(a_))
		{
			c.insert(a_);
		}
	}
}

int main()
{
	std::set<std::string> states_needed
	({
		"mt", "wa", "or", "id", "nv", "ut", "ca", "az"
	});

	std::map<std::string, std::set<std::string>> stations;
	stations["kone"].insert({ "id", "nv", "ut" });
	stations["ktwo"].insert({ "wa", "id", "mt" });
	stations["kthree"].insert({ "or", "nv", "ca" });
	stations["kfour"].insert({ "nv", "ut" });
	stations["kfive"].insert({ "ca", "az" });

	std::set<std::string> final_stations;

	while (states_needed.size())
	{
		std::string best_station;
		std::set<std::string> states_covered;

		for (const auto& station_and_states_for_station : stations)
		{
			std::set<std::string> covered;
			intersection(states_needed, station_and_states_for_station.second, covered);

			if (covered.size() > states_covered.size())
			{
				best_station = station_and_states_for_station.first;
				states_covered = covered;
			}
		}

		std::set<std::string> states_still_needed;
		difference(states_needed, states_covered, states_still_needed);
		final_stations.insert(best_station);

		if (states_needed.size() == states_still_needed.size())
		{
			break;
		}

		states_needed = states_still_needed;
	}

	for (const auto& station : final_stations)
	{
		std::cout << station << " ";
	}

	return EXIT_SUCCESS;
}

ch09_maximum_at_storage.cpp

/*
 * Fork of sources (C++) from "Grokking Algorithms (2016) by Aditya Bhargava"
 * created while study.
 * Author of original sources - @egonSchiele, https://adit.io/
 */

#include <map>
#include <list>
#include <string>
#include <cstdint>
#include <cstdlib>
#include <utility>
#include <iostream>

void fill_table(
	const std::pair<int, int>& index, uint32_t storage,
	const std::tuple<std::string, uint32_t, uint32_t>& current_item,
	std::map<std::pair<int, int>, std::pair<uint32_t, std::list<std::string>>>& table)
{
	if (storage < std::get<2>(current_item))
	{
		const auto key = std::make_pair(std::get<0>(index) - 1, std::get<1>(index));

		if (0 < table.count(key))
		{
			const auto& previous_items = table[key];
			std::get<0>(table[index]) = std::get<0>(previous_items);
			std::get<1>(table[index]).assign(
				std::get<1>(previous_items).cbegin(), std::get<1>(previous_items).cend());
		}
		else
		{
			table[index] = std::make_pair(0, std::list<std::string>());
		}
	}
	else
	{
		table[index] = std::make_pair(
			std::get<1>(current_item), std::list<std::string>({ std::get<0>(current_item) }));
		const auto key = std::make_pair(
			std::get<0>(index) - 1, std::get<1>(index) - std::get<2>(current_item));

		if (0 < table.count(key))
		{
			const auto& previous_items = table[key];
			std::get<0>(table[index]) += std::get<0>(previous_items);
			std::get<1>(table[index]).insert(
				std::get<1>(table[index]).cbegin(),
				std::get<1>(previous_items).cbegin(), std::get<1>(previous_items).cend());
		}
	}
}

int main()
{
	std::list<std::tuple<std::string, uint32_t, uint32_t>> items;
	items.push_back(std::make_tuple("Player", 3000, 4));
	items.push_back(std::make_tuple("Laptop", 2000, 3));
	items.push_back(std::make_tuple("Guitar", 1500, 1));

	const uint32_t max_storage = 4;

	std::map<std::pair<int, int>, std::pair<uint32_t, std::list<std::string>>> table;

	for (uint32_t storage = 1, i = 0, j = 0; i < max_storage; ++storage, ++i, j = 0)
	{
		for (const auto& current_item : items)
		{
			fill_table(std::make_pair(i, j++), storage, current_item, table);
		}
	}

	if (!items.empty() && 0 < max_storage)
	{
		const auto key = std::make_pair(
			static_cast<int>(max_storage - 1), static_cast<int>(items.size() - 1));

		if (0 < table.count(key))
		{
			const auto& answer = table[key];
			std::cout << "Total cost will be " << std::get<0>(answer);
			std::cout << " from collection of next items:" << std::endl;

			for (const auto& item_ : std::get<1>(answer))
			{
				std::cout << "\t" << item_ << std::endl;
			}

			std::cout << "." << std::endl;
		}
	}

	return EXIT_SUCCESS;
}

ch09_similar_words.cpp

/*
 * Fork of sources (C++) from "Grokking Algorithms (2016) by Aditya Bhargava"
 * created while study.
 * Author of original sources - @egonSchiele, https://adit.io/
 */

#include <map>
#include <string>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>

void fill_table(const std::string& word_a, const std::string& word_b, std::map<std::pair<int, int>, uint32_t>& table)
{
	for (int i = 0; i < word_a.size(); ++i)
	{
		for (int j = 0; j < word_b.size(); ++j)
		{
			if (word_a[i] == word_b[j])
			{
				const auto index = std::make_pair(i, j - 1);
				table[std::make_pair(i, j)] =
					0 < table.count(index) ? table[index] + 1 : 1;
			}
			else
			{
				const auto index_1 = std::make_pair(i - 1, j);
				const auto index_2 = std::make_pair(i, j - 1);
				table[std::make_pair(i, j)] = std::max(
					0 < table.count(index_1) ? table[index_1] : 0,
					0 < table.count(index_2) ? table[index_2] : 0);
			}			
		}
	}
}

int main()
{
	/*const std::string word("hish");
	const std::string candidates[]{ "fish", "vista" };*/
	/*const std::string word("fosh");
	const std::string candidates[]{ "fish", "fort" };*/
	const std::string word("blue");
	const std::string candidates[]{ "clues" };

	const std::string* answer = nullptr;
	uint32_t length = 0;

	for (const auto& candidate : candidates)
	{
		std::map<std::pair<int, int>, uint32_t> table;
		fill_table(word, candidate, table);

		for (const auto& cell : table)
		{
			if (length < std::get<1>(cell))
			{
				answer = &candidate;
				length = std::get<1>(cell);
			}
		}
	}

	if (nullptr != answer)
	{
		std::cout << *answer << std::endl;
	}
	else
	{
		std::cerr << "Not found." << std::endl;
	}

	return EXIT_SUCCESS;
}

cmake.yml

# .github/workflows/cmake.yml

name: CMake

on: [push, pull_request]

jobs:
  build:
    name: >-
      ${{ github.ref_name }}
      ${{ matrix.os }}
      ${{ matrix.compiler }}
      ${{ matrix.optimized && 'release' || 'debug' }}
      ${{ matrix.target_platform }}

    strategy:
      fail-fast: false
      matrix:
        compiler: [clang, gcc, msvc15, msvc16, msvc17, mingw]
        os: [ubuntu-latest, macos-latest, windows-2016, windows-2019, windows-2022]
        optimized: [true, false]
        target_platform: [x64, Win32]
        exclude:

        - os: ubuntu-latest
          compiler: clang
        - os: windows-2016
          compiler: clang
        - os: windows-2019
          compiler: clang
        - os: windows-2022
          compiler: clang

        - os: macos-latest
          compiler: gcc
        - os: windows-2016
          compiler: gcc
        - os: windows-2019
          compiler: gcc
        - os: windows-2022
          compiler: gcc

        - os: ubuntu-latest
          compiler: msvc14
        - os: macos-latest
          compiler: msvc14
        - os: windows-2019
          compiler: msvc14
        - os: windows-2022
          compiler: msvc14

        - os: ubuntu-latest
          compiler: msvc15
        - os: macos-latest
          compiler: msvc15
        - os: windows-2019
          compiler: msvc15
        - os: windows-2022
          compiler: msvc15

        - os: ubuntu-latest
          compiler: msvc16
        - os: macos-latest
          compiler: msvc16
        - os: windows-2016
          compiler: msvc16
        - os: windows-2022
          compiler: msvc16

        - os: ubuntu-latest
          compiler: msvc17
        - os: macos-latest
          compiler: msvc17
        - os: windows-2016
          compiler: msvc17
        - os: windows-2019
          compiler: msvc17

        - os: ubuntu-latest
          compiler: mingw
        - os: ubuntu-latest
          target_platform: Win32

        - os: macos-latest
          compiler: mingw
        - os: macos-latest
          target_platform: Win32

        - compiler: mingw
          target_platform: Win32
        - compiler: mingw
          os: windows-2016
        - compiler: mingw
          os: windows-2019

    env:
      CMAKE_SOURCE_DIR: ${{ github.workspace }}
      CMAKE_BUILD_DIR: >-
        ${{ format(
            startsWith(matrix.os, 'windows') && '{0}\build' || '{0}/build',
            github.workspace) }}
      CMAKE_GENERATOR: ${{ 'mingw' == matrix.compiler && '-G "MinGW Makefiles"' || '' }}
      CMAKE_BUILD_TYPE: >-
        ${{ format(
            'msvc' == matrix.compiler && '' || '-DCMAKE_BUILD_TYPE={0}',
            (matrix.optimized && 'Release' || 'Debug')) }}
      CMAKE_CONFIG_TYPE: ${{ matrix.optimized && 'Release' || 'Debug' }}
      CMAKE_TARGET_PLATFORM: >-
        ${{ format(
            startsWith(matrix.compiler, 'msvc') && '-A {0}' || '',
            matrix.target_platform) }}
      EXECUTABLE_EXTENSION: ${{ startsWith(matrix.os, 'windows') && '.exe' || '' }}
      BINARY_PATH: >-
        ${{ format(
            startsWith(matrix.compiler, 'msvc') && '{0}\build\{1}\' || '{0}/build/',
            github.workspace,
            matrix.optimized && 'Release' || 'Debug') }}

    runs-on: ${{ matrix.os }}

    steps:
    - name: Checkout
      uses: actions/checkout@v2

    - name: Create project files
      run: >-
        cmake ${{ env.CMAKE_TARGET_PLATFORM }}
        ${{ env.CMAKE_GENERATOR }} ${{ env.CMAKE_BUILD_TYPE }}
        -S ${{ env.CMAKE_SOURCE_DIR }} -B ${{ env.CMAKE_BUILD_DIR }}

    - name: Get number of CPU cores
      uses: SimenB/github-actions-cpu-cores@v1

    - name: Build
      run: >-
        cmake --build ${{ env.CMAKE_BUILD_DIR }}
        --config ${{ env.CMAKE_CONFIG_TYPE }}
        --parallel ${{ steps.cpu-cores.outputs.count }}

    - name: Run ch01_binary_search
      run: ${{ env.BINARY_PATH }}ch01_binary_search${{ env.EXECUTABLE_EXTENSION }}

    - name: Run ch06_Breadth-first_search
      run: ${{ env.BINARY_PATH }}ch06_Breadth-first_search${{ env.EXECUTABLE_EXTENSION }}

    - name: Run ch07_algorithm_of_Dijkstra
      run: ${{ env.BINARY_PATH }}ch07_algorithm_of_Dijkstra${{ env.EXECUTABLE_EXTENSION }}

    - name: Run ch08_find_best_station
      run: ${{ env.BINARY_PATH }}ch08_find_best_station${{ env.EXECUTABLE_EXTENSION }}

    - name: Run ch09_maximum_at_storage
      run: ${{ env.BINARY_PATH }}ch09_maximum_at_storage${{ env.EXECUTABLE_EXTENSION }}

    - name: Run ch09_similar_words
      run: ${{ env.BINARY_PATH }}ch09_similar_words${{ env.EXECUTABLE_EXTENSION }}

CMakeLists.txt

cmake_minimum_required(VERSION 2.8.12)

if(CMAKE_SOURCE_DIR STREQUAL CMAKE_BINARY_DIR)
  message(FATAL_ERROR "Configuration process cannot start from project source directory.")
endif()

project("Aditya Bhargava - Grokking Algorithms(2016)")

add_executable(ch01_binary_search "${CMAKE_SOURCE_DIR}/ch01_binary_search.cpp")
add_executable(ch06_Breadth-first_search "${CMAKE_SOURCE_DIR}/ch06_Breadth-first_search.cpp")
add_executable(ch07_algorithm_of_Dijkstra "${CMAKE_SOURCE_DIR}/ch07_algorithm_of_Dijkstra.cpp")
add_executable(ch08_find_best_station "${CMAKE_SOURCE_DIR}/ch08_find_best_station.cpp")
add_executable(ch09_maximum_at_storage "${CMAKE_SOURCE_DIR}/ch09_maximum_at_storage.cpp")
add_executable(ch09_similar_words "${CMAKE_SOURCE_DIR}/ch09_similar_words.cpp")

if(NOT MSVC)
  if(CMAKE_VERSION VERSION_LESS 3.1 OR ";${CMAKE_CXX_COMPILE_FEATURES};" MATCHES ";cxx_std_11;")
    target_compile_features(ch01_binary_search PRIVATE cxx_std_11)
    target_compile_features(ch06_Breadth-first_search PRIVATE cxx_std_11)
    target_compile_features(ch07_algorithm_of_Dijkstra PRIVATE cxx_std_11)
    target_compile_features(ch08_find_best_station PRIVATE cxx_std_11)
    target_compile_features(ch09_maximum_at_storage PRIVATE cxx_std_11)
    target_compile_features(ch09_similar_words PRIVATE cxx_std_11)
  else()
    set_property(TARGET ch01_binary_search PROPERTY CXX_STANDARD 11)
    set_property(TARGET ch06_Breadth-first_search PROPERTY CXX_STANDARD 11)
    set_property(TARGET ch07_algorithm_of_Dijkstra PROPERTY CXX_STANDARD 11)
    set_property(TARGET ch08_find_best_station PROPERTY CXX_STANDARD 11)
    set_property(TARGET ch09_maximum_at_storage PROPERTY CXX_STANDARD 11)
    set_property(TARGET ch09_similar_words PROPERTY CXX_STANDARD 11)
  endif()
endif()