Created
August 8, 2017 17:09
-
-
Save Taywee/e1d3c605cfa86bd7952fc1593f58e077 to your computer and use it in GitHub Desktop.
Same 325 Easy solution, but with an extra-fancy ncurses mode
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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 <chrono> | |
#include <vector> | |
#include <thread> | |
#include <tuple> | |
#include <set> | |
#include <curses.h> | |
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>; | |
inline unsigned int GetColor(const char letter) { | |
switch (letter) { | |
case 'R': | |
return 1; | |
case 'O': | |
return 2; | |
case 'Y': | |
return 3; | |
case 'G': | |
return 4; | |
case 'B': | |
return 5; | |
case 'P': | |
return 6; | |
default: | |
return 7; | |
} | |
} | |
Path WalkCell( | |
const Row &sequence, | |
const Maze &maze, | |
const Cell ¤t, | |
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') { | |
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); | |
} | |
} | |
// There could easily have been 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"); | |
} | |
const Path temp = SolveMaze(sequence, maze); | |
if (temp.empty()) { | |
std::cout << "Could not solve maze!" << std::endl; | |
return 1; | |
} else { | |
initscr(); | |
cbreak(); | |
noecho(); | |
curs_set(0); | |
start_color(); | |
move(0, 0); | |
init_pair(GetColor('R'), COLOR_BLACK, COLOR_RED); | |
init_pair(GetColor('O'), COLOR_BLACK, COLOR_CYAN); | |
init_pair(GetColor('Y'), COLOR_BLACK, COLOR_YELLOW); | |
init_pair(GetColor('G'), COLOR_BLACK, COLOR_GREEN); | |
init_pair(GetColor('B'), COLOR_BLACK, COLOR_BLUE); | |
init_pair(GetColor('P'), COLOR_BLACK, COLOR_MAGENTA); | |
for (const auto &cell: sequence) { | |
attron(COLOR_PAIR(GetColor(cell))); | |
addch(' '); | |
addch(' '); | |
} | |
for (unsigned int y = 0; y < maze.size(); ++y) { | |
const auto &row = maze[y]; | |
move(2 + y, 0); | |
for (const auto &cell: row) { | |
attron(COLOR_PAIR(GetColor(cell))); | |
addch(' '); | |
addch(' '); | |
} | |
} | |
wrefresh(stdscr); | |
for (const auto &step: temp) { | |
const auto seqcolor = COLOR_PAIR(GetColor(sequence[step.sequence])); | |
const auto mazecolor = COLOR_PAIR(GetColor(maze[step.y][step.x])); | |
attron(seqcolor); | |
mvaddch(0, step.sequence * 2, ACS_BLOCK); | |
addch(ACS_BLOCK); | |
attron(mazecolor); | |
mvaddch(step.y + 2, step.x * 2, ACS_BLOCK); | |
addch(ACS_BLOCK); | |
wrefresh(stdscr); | |
std::this_thread::sleep_for(std::chrono::duration<double>(0.25)); | |
attron(seqcolor); | |
mvaddch(0, step.sequence * 2, ' '); | |
addch(' '); | |
attron(mazecolor); | |
mvaddch(step.y + 2, step.x * 2, ' '); | |
addch(' '); | |
} | |
endwin(); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment