daily programming 325 Easy

325e.cxx

/* 325 Easy - Color Maze
   Written in 2017 by Taylor C. Richberger
   To the extent possible under law, the author(s) have dedicated all copyright
   and related and neighboring rights to this software to the public domain
   worldwide. This software is distributed without any warranty. 
   You should have received a copy of the CC0 Public Domain Dedication along
   with this software. If not, see
   <http://creativecommons.org/publicdomain/zero/1.0/>. 
*/

#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include <tuple>
#include <set>

using Row = std::vector<char>;
using Maze = std::vector<Row>;

struct Cell {
    unsigned int x;
    unsigned int y;
    unsigned int sequence;

    bool operator<(const Cell &other) const {
        return std::make_tuple(x, y, sequence) < std::make_tuple(other.x, other.y, other.sequence);
    }
};

using History = std::set<Cell>;
using Path = std::vector<Cell>;

Path WalkCell(
    const Row &sequence,
    const Maze &maze,
    const Cell &current,
    History history = History{},
    Path path = Path{}
    ) {

    const unsigned int next_seq = (current.sequence + 1 < sequence.size()) ? current.sequence + 1 : 0;
    const char next = sequence[next_seq];

    path.emplace_back(current);

    if (current.y == 0) {
        return path;
    }

    history.insert(current);

    // In order of precedence, we want to try to move up first if possible and
    // then try left and right before regressing backwards.

    // Need no current.y > 0 check, as that was done already above
    if (maze[current.y - 1][current.x] == next
        && !history.count(Cell{current.x, current.y - 1, next_seq})) {
        const Cell newCell{current.x, current.y - 1, next_seq};

        const Path temp = WalkCell(sequence, maze, newCell, history, path);

        if (!temp.empty()) {
            return temp;
        }
    }

    if (current.x < maze[0].size() - 1
        && maze[current.y][current.x + 1] == next
        && !history.count(Cell{current.x + 1, current.y, next_seq})) {
        const Cell newCell{current.x + 1, current.y, next_seq};

        Path temp = WalkCell(sequence, maze, newCell, history, path);

        if (!temp.empty()) {
            return temp;
        }
    }

    if (current.x > 0
        && maze[current.y][current.x - 1] == next
        && !history.count(Cell{current.x - 1, current.y, next_seq})) {
        const Cell newCell{current.x - 1, current.y, next_seq};

        Path temp = WalkCell(sequence, maze, newCell, history, path);

        if (!temp.empty()) {
            return temp;
        }
    }

    if (current.y < maze.size() - 1
        && maze[current.y + 1][current.x] == next
        && !history.count(Cell{current.x, current.y + 1, next_seq})) {
        const Cell newCell{current.x, current.y + 1, next_seq};

        Path temp = WalkCell(sequence, maze, newCell, history, path);

        if (!temp.empty()) {
            return temp;
        }
    }


    return Path{};
}

Path SolveMaze(
    const Row &sequence,
    const Maze &maze) {

    const Row &lastRow = maze.back();

    for (unsigned int x = 0; x < lastRow.size(); ++x) {
        const char color = lastRow[x];
        if (color == sequence[0]) {
            const Cell current{x, maze.size() - 1, 0};
            const Path temp = WalkCell(sequence, maze, current);
            if (!temp.empty()) {
                return temp;
            }
        }
    }
    return Path{};
}

int main(int argc, char **argv) {
    Row sequence;
    Maze maze;

    char c;
    std::cin >> std::noskipws;
    // Read sequence
    while (std::cin >> c) {
        if (c == '\n') {
            break;
        } else if (c != ' ') {
            sequence.emplace_back(c);
        }
    }
    // Read maze
    maze.emplace_back();
    while (std::cin >> c) {
        if (c == '\n') {
            // Trailing newlines
            while (maze.back().empty()) {
                maze.pop_back();
            }
            if (maze.back().size() != maze.front().size()) {
                throw std::runtime_error("Maze rows aren't evenly sized");
            }
            maze.emplace_back();
        } else if (c != ' ') {
            maze.back().emplace_back(c);
        }
    }
    // Trailing newline
    while (maze.back().empty()) {
        maze.pop_back();
    }
    if (maze.back().size() != maze.front().size()) {
        throw std::runtime_error("Maze rows aren't evenly sized");
    }

    const Path temp = SolveMaze(sequence, maze);
    if (temp.empty()) {
        std::cout << "Could not solve maze!" << std::endl;
        return 1;
    } else {
        for (const auto &step: temp) {
            std::cout << '(' << step.x << ", " << step.y << "): " << sequence[step.sequence] << std::endl;
        }
    }

    return 0;
}