Detective Pikaptcha

pika.cpp

// https://www.codingame.com/ide/puzzle/detective-pikaptcha-ep2

#include <iostream>
#include <vector>
#include <optional>

enum class Direction {
    TOP, BOT, LEFT, RIGHT
};

char DirToChar(Direction d) {
    switch (d) {
        case Direction::TOP: return '^';
        case Direction::BOT: return 'v';
        case Direction::LEFT: return '<';
        case Direction::RIGHT: return '>';
    }
}

Direction turnLeft(Direction d) {
    switch (d) {
        case Direction::TOP: return Direction::LEFT;
        case Direction::BOT: return Direction::RIGHT;
        case Direction::LEFT: return Direction::BOT;
        case Direction::RIGHT: return Direction::TOP;
    }
}

Direction turnRight(Direction d) {
    switch (d) {
        case Direction::TOP: return Direction::RIGHT;
        case Direction::BOT: return Direction::LEFT;
        case Direction::LEFT: return Direction::TOP;
        case Direction::RIGHT: return Direction::BOT;
    }
}

struct Grid;

struct Pos {
    size_t x;
    size_t y;

    bool Advance(Direction d, Grid & grid);
};


struct Pikachu {
    Pos pos;
    bool wallOnLeft;
    Direction direction;

    void Turn(bool toWallOnLeft) {
        if (toWallOnLeft) {
            direction = turnLeft(direction);
        } else {
            direction = turnRight(direction);
        }
    }
};

struct Grid {
    size_t m_width;
    size_t m_height;
    std::vector<std::optional<unsigned int>> m_passage;
    Pikachu m_pikachu;

    size_t startingX;
    size_t startingY;
    bool alreadyGone = false;

    Grid(size_t width, size_t height) : m_width(width), m_height(height) {
        m_passage.reserve(width * height);
    }

    void input(char c) {
        switch (c) {
            case '#':
                m_passage.push_back(std::nullopt);
                break;
            case '0':
                m_passage.push_back(0);
                break;
            default:
                {
                    Direction d;
                    switch(c) {
                        case '<': d = Direction::LEFT; break;
                        case 'v': d = Direction::BOT; break;
                        case '^': d = Direction::TOP; break;
                        case '>': d = Direction::RIGHT; break;
                        default: std::cerr << c << " unrecognized\n"; exit(1);
                    }
                    m_pikachu.direction = d;
                    m_pikachu.pos.x = m_passage.size() % m_width;
                    m_pikachu.pos.y = m_passage.size() / m_width;
                    m_passage.push_back(0);

                    startingX = m_pikachu.pos.x;
                    startingY = m_pikachu.pos.y;
                }
                break;
        }
    }

    void PikachuFollows(char c) {
        if (c == 'L') {
            m_pikachu.wallOnLeft = true;
        } else if (c == 'R') {
            m_pikachu.wallOnLeft = false;
        } else {
            std::cerr << "Pikachu must follow L or R, not " << c << "\n";
            exit(2);
        }
    }

    template<typename T>
    void AddCharOf(size_t x, size_t y, T & channel) {
        auto opt = m_passage[x + m_width * y];

        if (opt) {
            channel << opt.value();
        } else {
            channel << '#';
        }
    }

    void DisplayGrid(bool withPikachu = false) {
        if (withPikachu)
            std::cerr << "\n";

        for (size_t y = 0 ; y != m_height ; ++y) {
            for (size_t x = 0 ; x != m_width ; ++x) {
                if (withPikachu && m_pikachu.pos.x == x && m_pikachu.pos.y == y) {
                    std::cerr << DirToChar(m_pikachu.direction);
                } else {
                    if (withPikachu)
                        AddCharOf(x, y, std::cerr);
                    else
                        AddCharOf(x, y, std::cout);
                }
            }

            if (withPikachu)
                std::cerr << "\n";
            else
                std::cout << "\n";
        }

        if (withPikachu)
            std::cerr << "\n";
    }

    bool IsWall(size_t x, size_t y) const {
        return !m_passage[x + y * m_width].has_value();
    }

    bool PikachuIsNexttoWall() {
        Pos p = m_pikachu.pos;
        Direction d = m_pikachu.direction;
        if (m_pikachu.wallOnLeft) {
            d = turnLeft(d);
        } else {
            d = turnRight(d);
        }
        return !p.Advance(d, *this);
    }

    bool AdvancePikachu() {
        if (m_pikachu.pos.x == startingX && m_pikachu.pos.y == startingY && alreadyGone) {
            return false;
        }

        alreadyGone = true;

        if (!PikachuIsNexttoWall()) {
            //std::cerr << "No wall :pika:" << "\n";
            m_pikachu.Turn(m_pikachu.wallOnLeft);
            m_pikachu.pos.Advance(m_pikachu.direction, *this);
        } else {
            //std::cerr << "MY hand is on a wall" << "\n";
            while (!m_pikachu.pos.Advance(m_pikachu.direction, *this)) {
                //std::cerr << "tuuuut" << "\n";
                m_pikachu.Turn(!m_pikachu.wallOnLeft);
            }
        }

        m_passage[m_pikachu.pos.x + m_pikachu.pos.y * m_width].value() += 1;

        return true;
    }

    bool IsTrapped() {
        Pos p = m_pikachu.pos;

        for (Direction d : { Direction::BOT, Direction::TOP, Direction::LEFT, Direction::RIGHT }) {
            if (p.Advance(d, *this)) {
                return false;
            }
        }

        return true;
    }

};


bool Pos::Advance(Direction d, Grid & grid) {
    switch (d) {
        case Direction::LEFT:
            if (x == 0) return false;
            if (grid.IsWall(x - 1, y)) return false;
            x -= 1;
            return true;
        case Direction::TOP:
            if (y == 0) return false;
            if (grid.IsWall(x, y - 1)) return false;
            y -= 1;
            return true;
        case Direction::RIGHT:
            if (x == grid.m_width - 1) return false;
            if (grid.IsWall(x + 1, y)) return false;
            x += 1;
            return true;
        case Direction::BOT:
            if (y == grid.m_height - 1) return false;
            if (grid.IsWall(x, y + 1)) return false;
            y += 1;
            return true;
    }

    return false;
}

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/

int main()
{
    int width;
    int height;
    std::cin >> width >> height; std::cin.ignore();

    Grid grid(width, height);

    for (int i = 0; i < height; i++) {
        std::string line;
        std::cin >> line; std::cin.ignore();

        for (size_t x = 0 ; x != line.length(); ++x) {
            grid.input(line[x]);
        }
    }
    std::string side;
    std::cin >> side; std::cin.ignore();

    std::cerr << grid.m_passage.size();
    std::cerr << side << "\n";

    grid.PikachuFollows(side[0]);

    grid.DisplayGrid(true);


    if (!grid.IsTrapped()) {
        while (grid.AdvancePikachu()) {
            //grid.DisplayGrid(true);
        }
    }

    grid.DisplayGrid(false);
}