Dice
(utilities/dice.hpp)

View this file on GitHub
Last update: 2026-06-21 11:15:18+09:00
Include: #include "utilities/dice.hpp"

Overview

Dice<T> stores values on the six faces of a die and updates their positions when the die rolls. It is intended for grid simulation, orientation queries, face matching, and testing whether two labeled dice are equivalent up to rotation.

#include "utilities/dice.hpp"

All names are in m1une::utilities.

Face convention

The constructor takes faces in the following order:

Dice(
    top,
    bottom,
    north,
    south,
    east,
    west
)

Directions describe the die’s movement. After roll_north(), for example, the old south face is on top and the old top face points north.

DiceFace has the values top, bottom, north, south, east, and west. DiceDirection has the four horizontal directions. The free function opposite(face) returns the opposite face position.

Operations

Operation	Description	Complexity
`operator[](face)`	Accesses the value currently at `face`.	$O(1)$
`top()`, `bottom()`	Returns the current vertical face value.	$O(1)$
`north()`, `south()`, `east()`, `west()`	Returns a current side-face value.	$O(1)$
`faces()`	Returns all six current values in `DiceFace` order.	$O(1)$
`roll_north()`, `roll_south()`	Rolls the die one step in that direction.	$O(1)$
`roll_east()`, `roll_west()`	Rolls the die one step in that direction.	$O(1)$
`roll(direction)`	Rolls using a `DiceDirection`.	$O(1)$
`rotate_clockwise()`	Rotates the die clockwise as viewed from above.	$O(1)$
`rotate_counterclockwise()`	Rotates it counterclockwise as viewed from above.	$O(1)$
`orientations()`	Returns the 24 spatial orientations.	$O(1)$
`orientation(top, south)`	Finds an orientation with the requested top and south values.	$O(1)$
`equivalent(other)`	Tests equality under an arbitrary spatial rotation.	$O(1)$

Rolling and rotation operations mutate the die and return *this, allowing calls such as die.roll_north().roll_east(). Ordinary operator== compares the values at the same six positions; use equivalent when rotation is allowed.

If face values are repeated, orientation(top, south) returns the first matching orientation. It returns std::nullopt if no match exists.

Simulating commands

#include "utilities/dice.hpp"

#include <iostream>
#include <string>

int main() {
    m1une::utilities::Dice<int> die(
        1, 6, 5, 2, 3, 4
    );

    std::string commands = "SENW";
    for (char command : commands) {
        if (command == 'N') die.roll_north();
        if (command == 'S') die.roll_south();
        if (command == 'E') die.roll_east();
        if (command == 'W') die.roll_west();
    }
    std::cout << die.top() << "\n";
}

The values in this example use the common AOJ input order top, south, east, west, north, bottom, rearranged for the constructor.

Finding a side face

When the top and front faces are specified, orient the die and inspect the right-hand face. If “front” means south and “right” means east:

auto oriented = die.orientation(top_value, front_value);
if (oriented.has_value()) {
    std::cout << oriented->east() << "\n";
}

Comparing dice up to rotation

if (first.equivalent(second)) {
    std::cout << "the same die\n";
}

orientations() always represents all 24 rotations, even when repeated face values make some resulting value arrangements equal.

Arrows and other oriented face decorations

Dice<T> moves face values but does not rotate the values themselves. This is correct for numbers, colors, and labels. A decoration such as an arrow also has an orientation within its face, so it needs the separate ArrowDice class.

ArrowDice represents each arrow by the world-space DiceFace direction in which it points. Its roll and rotation operations update both the occupied face and the arrow direction.

Direction convention

The six DiceFace values name fixed world directions:

top and bottom are vertically upward and downward.
north, south, east, and west are the four horizontal directions.

These names do not change when the cube is viewed from another side. For example, arrow(DiceFace::south) == DiceFace::east means that the arrow painted on the south face points toward world east. It does not mean “right on the screen,” because that would depend on the viewer.

World-space direction convention for arrows on dice faces

In the diagram, the arrow on the top face points north, the arrow on the west face points south, and the arrow on the south face points upward (top). Each arrow direction must be tangent to its face:

Face containing the arrow	Possible arrow directions
`top` or `bottom`	`north`, `south`, `east`, `west`
`north` or `south`	`top`, `bottom`, `east`, `west`
`east` or `west`	`top`, `bottom`, `north`, `south`

from_net converts the viewer-relative characters ^, v, <, and > in the flat input grid into these world-space directions while folding the net. After that conversion, viewing direction is irrelevant.

Operation	Description	Complexity
`arrow(face)`	Returns the direction of the arrow on `face`.	$O(1)$
`roll...()` / `rotate...()`	Rotates the die and all face arrows together.	$O(1)$
`orientations()`	Returns all 24 decorated orientations.	$O(1)$
`difference(other)`	Counts differing arrows with the current alignments.	$O(1)$
`distance(other)`	Returns the minimum difference under arbitrary rotation.	$O(1)$
`from_net(grid, empty)`	Folds a character grid into an arrow die.	$O(HW)$

rotate_direction, rotate_direction_clockwise, and rotate_direction_counterclockwise are also available when a solution needs to rotate a standalone world-space direction.

Folding a cube net

ArrowDice::from_net accepts a rectangular grid containing exactly six non-empty cells. The characters ^, v, <, and > describe arrows in the grid before folding. Adjacent cells are folded along their common edge.

The method rejects disconnected, inconsistent, overlapping, and malformed nets with std::invalid_argument.

std::vector<std::string> net{
    "..^..",
    ".<v>.",
    "..>..",
    "..<..",
    "....."
};

m1une::utilities::ArrowDice die =
    m1une::utilities::ArrowDice::from_net(net);

The starting orientation chosen while folding is arbitrary, which does not affect distance.

Minimum difference between arrow dice

This directly supports problems such as AOJ 3206, where two arrow dice may be rotated before corresponding faces are compared:

int answer = first.distance(second);

Internally, this checks six faces in each of the 24 cube orientations. Comparing all pairs among $N$ dice therefore takes $O(24 \cdot 6 \cdot N^2)$ time, which is effectively $O(N^2)$.

Verified with

Code

#ifndef M1UNE_DICE_HPP
#define M1UNE_DICE_HPP 1

#include <array>
#include <cstddef>
#include <optional>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

namespace m1une {
namespace utilities {

enum class DiceFace : std::size_t {
    top,
    bottom,
    north,
    south,
    east,
    west
};

enum class DiceDirection {
    north,
    south,
    east,
    west
};

constexpr DiceFace opposite(DiceFace face) noexcept {
    switch (face) {
        case DiceFace::top:
            return DiceFace::bottom;
        case DiceFace::bottom:
            return DiceFace::top;
        case DiceFace::north:
            return DiceFace::south;
        case DiceFace::south:
            return DiceFace::north;
        case DiceFace::east:
            return DiceFace::west;
        case DiceFace::west:
            return DiceFace::east;
    }
    return DiceFace::top;
}

constexpr DiceFace rotate_direction(
    DiceFace direction,
    DiceDirection rotation
) noexcept {
    switch (rotation) {
        case DiceDirection::north:
            switch (direction) {
                case DiceFace::top:
                    return DiceFace::north;
                case DiceFace::north:
                    return DiceFace::bottom;
                case DiceFace::bottom:
                    return DiceFace::south;
                case DiceFace::south:
                    return DiceFace::top;
                default:
                    return direction;
            }
        case DiceDirection::south:
            switch (direction) {
                case DiceFace::top:
                    return DiceFace::south;
                case DiceFace::south:
                    return DiceFace::bottom;
                case DiceFace::bottom:
                    return DiceFace::north;
                case DiceFace::north:
                    return DiceFace::top;
                default:
                    return direction;
            }
        case DiceDirection::east:
            switch (direction) {
                case DiceFace::top:
                    return DiceFace::east;
                case DiceFace::east:
                    return DiceFace::bottom;
                case DiceFace::bottom:
                    return DiceFace::west;
                case DiceFace::west:
                    return DiceFace::top;
                default:
                    return direction;
            }
        case DiceDirection::west:
            switch (direction) {
                case DiceFace::top:
                    return DiceFace::west;
                case DiceFace::west:
                    return DiceFace::bottom;
                case DiceFace::bottom:
                    return DiceFace::east;
                case DiceFace::east:
                    return DiceFace::top;
                default:
                    return direction;
            }
    }
    return direction;
}

constexpr DiceFace rotate_direction_clockwise(DiceFace direction) noexcept {
    switch (direction) {
        case DiceFace::north:
            return DiceFace::east;
        case DiceFace::east:
            return DiceFace::south;
        case DiceFace::south:
            return DiceFace::west;
        case DiceFace::west:
            return DiceFace::north;
        default:
            return direction;
    }
}

constexpr DiceFace rotate_direction_counterclockwise(DiceFace direction) noexcept {
    switch (direction) {
        case DiceFace::north:
            return DiceFace::west;
        case DiceFace::west:
            return DiceFace::south;
        case DiceFace::south:
            return DiceFace::east;
        case DiceFace::east:
            return DiceFace::north;
        default:
            return direction;
    }
}

template <typename T>
class Dice {
private:
    static constexpr std::size_t face_count = 6;
    std::array<T, face_count> faces_;

    static constexpr std::size_t index(DiceFace face) noexcept {
        return static_cast<std::size_t>(face);
    }

public:
    constexpr Dice(
        T top,
        T bottom,
        T north,
        T south,
        T east,
        T west
    )
        : faces_{
              std::move(top),
              std::move(bottom),
              std::move(north),
              std::move(south),
              std::move(east),
              std::move(west)
          } {}

    explicit constexpr Dice(std::array<T, face_count> faces)
        : faces_(std::move(faces)) {}

    [[nodiscard]] constexpr const T& operator[](DiceFace face) const noexcept {
        return faces_[index(face)];
    }

    [[nodiscard]] constexpr T& operator[](DiceFace face) noexcept {
        return faces_[index(face)];
    }

    [[nodiscard]] constexpr const T& top() const noexcept {
        return (*this)[DiceFace::top];
    }

    [[nodiscard]] constexpr const T& bottom() const noexcept {
        return (*this)[DiceFace::bottom];
    }

    [[nodiscard]] constexpr const T& north() const noexcept {
        return (*this)[DiceFace::north];
    }

    [[nodiscard]] constexpr const T& south() const noexcept {
        return (*this)[DiceFace::south];
    }

    [[nodiscard]] constexpr const T& east() const noexcept {
        return (*this)[DiceFace::east];
    }

    [[nodiscard]] constexpr const T& west() const noexcept {
        return (*this)[DiceFace::west];
    }

    [[nodiscard]] constexpr const std::array<T, face_count>& faces() const noexcept {
        return faces_;
    }

    constexpr Dice& roll_north() {
        T old_top = std::move((*this)[DiceFace::top]);
        (*this)[DiceFace::top] = std::move((*this)[DiceFace::south]);
        (*this)[DiceFace::south] = std::move((*this)[DiceFace::bottom]);
        (*this)[DiceFace::bottom] = std::move((*this)[DiceFace::north]);
        (*this)[DiceFace::north] = std::move(old_top);
        return *this;
    }

    constexpr Dice& roll_south() {
        T old_top = std::move((*this)[DiceFace::top]);
        (*this)[DiceFace::top] = std::move((*this)[DiceFace::north]);
        (*this)[DiceFace::north] = std::move((*this)[DiceFace::bottom]);
        (*this)[DiceFace::bottom] = std::move((*this)[DiceFace::south]);
        (*this)[DiceFace::south] = std::move(old_top);
        return *this;
    }

    constexpr Dice& roll_east() {
        T old_top = std::move((*this)[DiceFace::top]);
        (*this)[DiceFace::top] = std::move((*this)[DiceFace::west]);
        (*this)[DiceFace::west] = std::move((*this)[DiceFace::bottom]);
        (*this)[DiceFace::bottom] = std::move((*this)[DiceFace::east]);
        (*this)[DiceFace::east] = std::move(old_top);
        return *this;
    }

    constexpr Dice& roll_west() {
        T old_top = std::move((*this)[DiceFace::top]);
        (*this)[DiceFace::top] = std::move((*this)[DiceFace::east]);
        (*this)[DiceFace::east] = std::move((*this)[DiceFace::bottom]);
        (*this)[DiceFace::bottom] = std::move((*this)[DiceFace::west]);
        (*this)[DiceFace::west] = std::move(old_top);
        return *this;
    }

    constexpr Dice& roll(DiceDirection direction) {
        switch (direction) {
            case DiceDirection::north:
                return roll_north();
            case DiceDirection::south:
                return roll_south();
            case DiceDirection::east:
                return roll_east();
            case DiceDirection::west:
                return roll_west();
        }
        return *this;
    }

    constexpr Dice& rotate_clockwise() {
        T old_north = std::move((*this)[DiceFace::north]);
        (*this)[DiceFace::north] = std::move((*this)[DiceFace::west]);
        (*this)[DiceFace::west] = std::move((*this)[DiceFace::south]);
        (*this)[DiceFace::south] = std::move((*this)[DiceFace::east]);
        (*this)[DiceFace::east] = std::move(old_north);
        return *this;
    }

    constexpr Dice& rotate_counterclockwise() {
        T old_north = std::move((*this)[DiceFace::north]);
        (*this)[DiceFace::north] = std::move((*this)[DiceFace::east]);
        (*this)[DiceFace::east] = std::move((*this)[DiceFace::south]);
        (*this)[DiceFace::south] = std::move((*this)[DiceFace::west]);
        (*this)[DiceFace::west] = std::move(old_north);
        return *this;
    }

    [[nodiscard]] constexpr std::array<Dice, 24> orientations() const {
        Dice top_top = *this;
        Dice north_top = *this;
        north_top.roll_south();
        Dice south_top = *this;
        south_top.roll_north();
        Dice east_top = *this;
        east_top.roll_west();
        Dice west_top = *this;
        west_top.roll_east();
        Dice bottom_top = *this;
        bottom_top.roll_north().roll_north();

        std::array<Dice, 6> top_orientations{
            std::move(top_top),
            std::move(north_top),
            std::move(south_top),
            std::move(east_top),
            std::move(west_top),
            std::move(bottom_top)
        };

        std::array<Dice, 24> result{
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this
        };
        std::size_t result_index = 0;
        for (Dice oriented : top_orientations) {
            for (int rotation = 0; rotation < 4; ++rotation) {
                result[result_index++] = oriented;
                oriented.rotate_clockwise();
            }
        }
        return result;
    }

    [[nodiscard]] constexpr std::optional<Dice> orientation(
        const T& top_value,
        const T& south_value
    ) const {
        for (const Dice& oriented : orientations()) {
            if (oriented.top() == top_value && oriented.south() == south_value) {
                return oriented;
            }
        }
        return std::nullopt;
    }

    [[nodiscard]] constexpr bool equivalent(const Dice& other) const {
        for (const Dice& oriented : orientations()) {
            if (oriented == other) {
                return true;
            }
        }
        return false;
    }

    friend constexpr bool operator==(const Dice&, const Dice&) = default;
};

class ArrowDice {
private:
    struct Vector {
        int x;
        int y;
        int z;

        friend constexpr bool operator==(const Vector&, const Vector&) = default;
    };

    struct Frame {
        Vector normal;
        Vector up;
        Vector right;

        friend constexpr bool operator==(const Frame&, const Frame&) = default;
    };

    Dice<DiceFace> arrows_;

    static constexpr Vector negate(Vector vector) noexcept {
        return Vector{-vector.x, -vector.y, -vector.z};
    }

    static constexpr DiceFace vector_to_face(Vector vector) {
        if (vector == Vector{0, 0, 1}) return DiceFace::top;
        if (vector == Vector{0, 0, -1}) return DiceFace::bottom;
        if (vector == Vector{0, 1, 0}) return DiceFace::north;
        if (vector == Vector{0, -1, 0}) return DiceFace::south;
        if (vector == Vector{1, 0, 0}) return DiceFace::east;
        if (vector == Vector{-1, 0, 0}) return DiceFace::west;
        throw std::invalid_argument("vector is not a cube direction");
    }

    static constexpr Frame adjacent_frame(
        const Frame& frame,
        DiceDirection direction
    ) noexcept {
        switch (direction) {
            case DiceDirection::north:
                return Frame{frame.up, negate(frame.normal), frame.right};
            case DiceDirection::south:
                return Frame{negate(frame.up), frame.normal, frame.right};
            case DiceDirection::east:
                return Frame{frame.right, frame.up, negate(frame.normal)};
            case DiceDirection::west:
                return Frame{negate(frame.right), frame.up, frame.normal};
        }
        return frame;
    }

    static constexpr DiceFace arrow_from_character(
        char arrow,
        const Frame& frame
    ) {
        if (arrow == '^') return vector_to_face(frame.up);
        if (arrow == 'v') return vector_to_face(negate(frame.up));
        if (arrow == '>') return vector_to_face(frame.right);
        if (arrow == '<') return vector_to_face(negate(frame.right));
        throw std::invalid_argument("arrow dice net contains an invalid character");
    }

    constexpr void rotate_arrows(DiceDirection direction) noexcept {
        for (DiceFace face : all_faces()) {
            arrows_[face] = rotate_direction(arrows_[face], direction);
        }
    }

    static constexpr std::array<DiceFace, 6> all_faces() noexcept {
        return std::array<DiceFace, 6>{
            DiceFace::top,
            DiceFace::bottom,
            DiceFace::north,
            DiceFace::south,
            DiceFace::east,
            DiceFace::west
        };
    }

public:
    constexpr ArrowDice(
        DiceFace top,
        DiceFace bottom,
        DiceFace north,
        DiceFace south,
        DiceFace east,
        DiceFace west
    )
        : arrows_(top, bottom, north, south, east, west) {}

    explicit constexpr ArrowDice(Dice<DiceFace> arrows)
        : arrows_(std::move(arrows)) {}

    [[nodiscard]] constexpr DiceFace arrow(DiceFace face) const noexcept {
        return arrows_[face];
    }

    [[nodiscard]] constexpr const Dice<DiceFace>& arrows() const noexcept {
        return arrows_;
    }

    constexpr ArrowDice& roll(DiceDirection direction) {
        arrows_.roll(direction);
        rotate_arrows(direction);
        return *this;
    }

    constexpr ArrowDice& roll_north() {
        return roll(DiceDirection::north);
    }

    constexpr ArrowDice& roll_south() {
        return roll(DiceDirection::south);
    }

    constexpr ArrowDice& roll_east() {
        return roll(DiceDirection::east);
    }

    constexpr ArrowDice& roll_west() {
        return roll(DiceDirection::west);
    }

    constexpr ArrowDice& rotate_clockwise() {
        arrows_.rotate_clockwise();
        for (DiceFace face : all_faces()) {
            arrows_[face] = rotate_direction_clockwise(arrows_[face]);
        }
        return *this;
    }

    constexpr ArrowDice& rotate_counterclockwise() {
        arrows_.rotate_counterclockwise();
        for (DiceFace face : all_faces()) {
            arrows_[face] = rotate_direction_counterclockwise(arrows_[face]);
        }
        return *this;
    }

    [[nodiscard]] constexpr std::array<ArrowDice, 24> orientations() const {
        ArrowDice top_top = *this;
        ArrowDice north_top = *this;
        north_top.roll_south();
        ArrowDice south_top = *this;
        south_top.roll_north();
        ArrowDice east_top = *this;
        east_top.roll_west();
        ArrowDice west_top = *this;
        west_top.roll_east();
        ArrowDice bottom_top = *this;
        bottom_top.roll_north().roll_north();

        std::array<ArrowDice, 6> top_orientations{
            top_top,
            north_top,
            south_top,
            east_top,
            west_top,
            bottom_top
        };
        std::array<ArrowDice, 24> result{
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this
        };

        std::size_t result_index = 0;
        for (ArrowDice oriented : top_orientations) {
            for (int rotation = 0; rotation < 4; ++rotation) {
                result[result_index++] = oriented;
                oriented.rotate_clockwise();
            }
        }
        return result;
    }

    [[nodiscard]] constexpr int difference(const ArrowDice& other) const noexcept {
        int result = 0;
        for (DiceFace face : all_faces()) {
            result += arrow(face) != other.arrow(face);
        }
        return result;
    }

    [[nodiscard]] constexpr int distance(const ArrowDice& other) const {
        int result = 6;
        for (const ArrowDice& oriented : orientations()) {
            int current = oriented.difference(other);
            if (current < result) result = current;
        }
        return result;
    }

    [[nodiscard]] static ArrowDice from_net(
        const std::vector<std::string>& net,
        char empty = '.'
    ) {
        if (net.empty()) {
            throw std::invalid_argument("arrow dice net is empty");
        }
        std::size_t width = net.front().size();
        if (width == 0) {
            throw std::invalid_argument("arrow dice net is empty");
        }
        for (const std::string& row : net) {
            if (row.size() != width) {
                throw std::invalid_argument("arrow dice net must be rectangular");
            }
        }

        int height = static_cast<int>(net.size());
        int integer_width = static_cast<int>(width);
        std::vector<std::vector<std::optional<Frame>>> frames(
            net.size(),
            std::vector<std::optional<Frame>>(width)
        );
        auto character_at = [&](int row, int column) -> char {
            return net[static_cast<std::size_t>(row)]
                      [static_cast<std::size_t>(column)];
        };
        auto frame_at = [&](int row, int column) -> std::optional<Frame>& {
            return frames[static_cast<std::size_t>(row)]
                         [static_cast<std::size_t>(column)];
        };
        std::vector<std::pair<int, int>> queue;
        int face_count = 0;
        for (int row = 0; row < height; ++row) {
            for (int column = 0; column < integer_width; ++column) {
                if (character_at(row, column) != empty) {
                    ++face_count;
                    if (queue.empty()) queue.emplace_back(row, column);
                }
            }
        }
        if (face_count != 6) {
            throw std::invalid_argument("arrow dice net must contain six faces");
        }

        Frame initial{
            Vector{0, 0, 1},
            Vector{0, 1, 0},
            Vector{1, 0, 0}
        };
        frame_at(queue.front().first, queue.front().second) = initial;

        constexpr std::array<int, 4> row_delta{-1, 1, 0, 0};
        constexpr std::array<int, 4> column_delta{0, 0, 1, -1};
        constexpr std::array<DiceDirection, 4> directions{
            DiceDirection::north,
            DiceDirection::south,
            DiceDirection::east,
            DiceDirection::west
        };
        for (std::size_t head = 0; head < queue.size(); ++head) {
            int row = queue[head].first;
            int column = queue[head].second;
            Frame frame = *frame_at(row, column);
            for (std::size_t edge = 0; edge < directions.size(); ++edge) {
                int next_row = row + row_delta[edge];
                int next_column = column + column_delta[edge];
                if (
                    next_row < 0 || next_row >= height ||
                    next_column < 0 || next_column >= integer_width ||
                    character_at(next_row, next_column) == empty
                ) {
                    continue;
                }

                Frame next_frame = adjacent_frame(frame, directions[edge]);
                std::optional<Frame>& known = frame_at(next_row, next_column);
                if (!known.has_value()) {
                    known = next_frame;
                    queue.emplace_back(next_row, next_column);
                } else if (*known != next_frame) {
                    throw std::invalid_argument("arrow dice net folds inconsistently");
                }
            }
        }
        if (queue.size() != 6) {
            throw std::invalid_argument("arrow dice net is disconnected");
        }

        std::array<std::optional<DiceFace>, 6> arrows;
        for (const std::pair<int, int>& cell : queue) {
            int row = cell.first;
            int column = cell.second;
            Frame frame = *frame_at(row, column);
            DiceFace face = vector_to_face(frame.normal);
            std::optional<DiceFace>& slot =
                arrows[static_cast<std::size_t>(face)];
            if (slot.has_value()) {
                throw std::invalid_argument("arrow dice net overlaps when folded");
            }
            slot = arrow_from_character(character_at(row, column), frame);
        }
        for (const std::optional<DiceFace>& arrow : arrows) {
            if (!arrow.has_value()) {
                throw std::invalid_argument("arrow dice net does not form a cube");
            }
        }

        return ArrowDice(
            *arrows[static_cast<std::size_t>(DiceFace::top)],
            *arrows[static_cast<std::size_t>(DiceFace::bottom)],
            *arrows[static_cast<std::size_t>(DiceFace::north)],
            *arrows[static_cast<std::size_t>(DiceFace::south)],
            *arrows[static_cast<std::size_t>(DiceFace::east)],
            *arrows[static_cast<std::size_t>(DiceFace::west)]
        );
    }

    friend constexpr bool operator==(const ArrowDice&, const ArrowDice&) = default;
};

}  // namespace utilities
}  // namespace m1une

#endif  // M1UNE_DICE_HPP

#line 1 "utilities/dice.hpp"



#include <array>
#include <cstddef>
#include <optional>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

namespace m1une {
namespace utilities {

enum class DiceFace : std::size_t {
    top,
    bottom,
    north,
    south,
    east,
    west
};

enum class DiceDirection {
    north,
    south,
    east,
    west
};

constexpr DiceFace opposite(DiceFace face) noexcept {
    switch (face) {
        case DiceFace::top:
            return DiceFace::bottom;
        case DiceFace::bottom:
            return DiceFace::top;
        case DiceFace::north:
            return DiceFace::south;
        case DiceFace::south:
            return DiceFace::north;
        case DiceFace::east:
            return DiceFace::west;
        case DiceFace::west:
            return DiceFace::east;
    }
    return DiceFace::top;
}

constexpr DiceFace rotate_direction(
    DiceFace direction,
    DiceDirection rotation
) noexcept {
    switch (rotation) {
        case DiceDirection::north:
            switch (direction) {
                case DiceFace::top:
                    return DiceFace::north;
                case DiceFace::north:
                    return DiceFace::bottom;
                case DiceFace::bottom:
                    return DiceFace::south;
                case DiceFace::south:
                    return DiceFace::top;
                default:
                    return direction;
            }
        case DiceDirection::south:
            switch (direction) {
                case DiceFace::top:
                    return DiceFace::south;
                case DiceFace::south:
                    return DiceFace::bottom;
                case DiceFace::bottom:
                    return DiceFace::north;
                case DiceFace::north:
                    return DiceFace::top;
                default:
                    return direction;
            }
        case DiceDirection::east:
            switch (direction) {
                case DiceFace::top:
                    return DiceFace::east;
                case DiceFace::east:
                    return DiceFace::bottom;
                case DiceFace::bottom:
                    return DiceFace::west;
                case DiceFace::west:
                    return DiceFace::top;
                default:
                    return direction;
            }
        case DiceDirection::west:
            switch (direction) {
                case DiceFace::top:
                    return DiceFace::west;
                case DiceFace::west:
                    return DiceFace::bottom;
                case DiceFace::bottom:
                    return DiceFace::east;
                case DiceFace::east:
                    return DiceFace::top;
                default:
                    return direction;
            }
    }
    return direction;
}

constexpr DiceFace rotate_direction_clockwise(DiceFace direction) noexcept {
    switch (direction) {
        case DiceFace::north:
            return DiceFace::east;
        case DiceFace::east:
            return DiceFace::south;
        case DiceFace::south:
            return DiceFace::west;
        case DiceFace::west:
            return DiceFace::north;
        default:
            return direction;
    }
}

constexpr DiceFace rotate_direction_counterclockwise(DiceFace direction) noexcept {
    switch (direction) {
        case DiceFace::north:
            return DiceFace::west;
        case DiceFace::west:
            return DiceFace::south;
        case DiceFace::south:
            return DiceFace::east;
        case DiceFace::east:
            return DiceFace::north;
        default:
            return direction;
    }
}

template <typename T>
class Dice {
private:
    static constexpr std::size_t face_count = 6;
    std::array<T, face_count> faces_;

    static constexpr std::size_t index(DiceFace face) noexcept {
        return static_cast<std::size_t>(face);
    }

public:
    constexpr Dice(
        T top,
        T bottom,
        T north,
        T south,
        T east,
        T west
    )
        : faces_{
              std::move(top),
              std::move(bottom),
              std::move(north),
              std::move(south),
              std::move(east),
              std::move(west)
          } {}

    explicit constexpr Dice(std::array<T, face_count> faces)
        : faces_(std::move(faces)) {}

    [[nodiscard]] constexpr const T& operator[](DiceFace face) const noexcept {
        return faces_[index(face)];
    }

    [[nodiscard]] constexpr T& operator[](DiceFace face) noexcept {
        return faces_[index(face)];
    }

    [[nodiscard]] constexpr const T& top() const noexcept {
        return (*this)[DiceFace::top];
    }

    [[nodiscard]] constexpr const T& bottom() const noexcept {
        return (*this)[DiceFace::bottom];
    }

    [[nodiscard]] constexpr const T& north() const noexcept {
        return (*this)[DiceFace::north];
    }

    [[nodiscard]] constexpr const T& south() const noexcept {
        return (*this)[DiceFace::south];
    }

    [[nodiscard]] constexpr const T& east() const noexcept {
        return (*this)[DiceFace::east];
    }

    [[nodiscard]] constexpr const T& west() const noexcept {
        return (*this)[DiceFace::west];
    }

    [[nodiscard]] constexpr const std::array<T, face_count>& faces() const noexcept {
        return faces_;
    }

    constexpr Dice& roll_north() {
        T old_top = std::move((*this)[DiceFace::top]);
        (*this)[DiceFace::top] = std::move((*this)[DiceFace::south]);
        (*this)[DiceFace::south] = std::move((*this)[DiceFace::bottom]);
        (*this)[DiceFace::bottom] = std::move((*this)[DiceFace::north]);
        (*this)[DiceFace::north] = std::move(old_top);
        return *this;
    }

    constexpr Dice& roll_south() {
        T old_top = std::move((*this)[DiceFace::top]);
        (*this)[DiceFace::top] = std::move((*this)[DiceFace::north]);
        (*this)[DiceFace::north] = std::move((*this)[DiceFace::bottom]);
        (*this)[DiceFace::bottom] = std::move((*this)[DiceFace::south]);
        (*this)[DiceFace::south] = std::move(old_top);
        return *this;
    }

    constexpr Dice& roll_east() {
        T old_top = std::move((*this)[DiceFace::top]);
        (*this)[DiceFace::top] = std::move((*this)[DiceFace::west]);
        (*this)[DiceFace::west] = std::move((*this)[DiceFace::bottom]);
        (*this)[DiceFace::bottom] = std::move((*this)[DiceFace::east]);
        (*this)[DiceFace::east] = std::move(old_top);
        return *this;
    }

    constexpr Dice& roll_west() {
        T old_top = std::move((*this)[DiceFace::top]);
        (*this)[DiceFace::top] = std::move((*this)[DiceFace::east]);
        (*this)[DiceFace::east] = std::move((*this)[DiceFace::bottom]);
        (*this)[DiceFace::bottom] = std::move((*this)[DiceFace::west]);
        (*this)[DiceFace::west] = std::move(old_top);
        return *this;
    }

    constexpr Dice& roll(DiceDirection direction) {
        switch (direction) {
            case DiceDirection::north:
                return roll_north();
            case DiceDirection::south:
                return roll_south();
            case DiceDirection::east:
                return roll_east();
            case DiceDirection::west:
                return roll_west();
        }
        return *this;
    }

    constexpr Dice& rotate_clockwise() {
        T old_north = std::move((*this)[DiceFace::north]);
        (*this)[DiceFace::north] = std::move((*this)[DiceFace::west]);
        (*this)[DiceFace::west] = std::move((*this)[DiceFace::south]);
        (*this)[DiceFace::south] = std::move((*this)[DiceFace::east]);
        (*this)[DiceFace::east] = std::move(old_north);
        return *this;
    }

    constexpr Dice& rotate_counterclockwise() {
        T old_north = std::move((*this)[DiceFace::north]);
        (*this)[DiceFace::north] = std::move((*this)[DiceFace::east]);
        (*this)[DiceFace::east] = std::move((*this)[DiceFace::south]);
        (*this)[DiceFace::south] = std::move((*this)[DiceFace::west]);
        (*this)[DiceFace::west] = std::move(old_north);
        return *this;
    }

    [[nodiscard]] constexpr std::array<Dice, 24> orientations() const {
        Dice top_top = *this;
        Dice north_top = *this;
        north_top.roll_south();
        Dice south_top = *this;
        south_top.roll_north();
        Dice east_top = *this;
        east_top.roll_west();
        Dice west_top = *this;
        west_top.roll_east();
        Dice bottom_top = *this;
        bottom_top.roll_north().roll_north();

        std::array<Dice, 6> top_orientations{
            std::move(top_top),
            std::move(north_top),
            std::move(south_top),
            std::move(east_top),
            std::move(west_top),
            std::move(bottom_top)
        };

        std::array<Dice, 24> result{
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this
        };
        std::size_t result_index = 0;
        for (Dice oriented : top_orientations) {
            for (int rotation = 0; rotation < 4; ++rotation) {
                result[result_index++] = oriented;
                oriented.rotate_clockwise();
            }
        }
        return result;
    }

    [[nodiscard]] constexpr std::optional<Dice> orientation(
        const T& top_value,
        const T& south_value
    ) const {
        for (const Dice& oriented : orientations()) {
            if (oriented.top() == top_value && oriented.south() == south_value) {
                return oriented;
            }
        }
        return std::nullopt;
    }

    [[nodiscard]] constexpr bool equivalent(const Dice& other) const {
        for (const Dice& oriented : orientations()) {
            if (oriented == other) {
                return true;
            }
        }
        return false;
    }

    friend constexpr bool operator==(const Dice&, const Dice&) = default;
};

class ArrowDice {
private:
    struct Vector {
        int x;
        int y;
        int z;

        friend constexpr bool operator==(const Vector&, const Vector&) = default;
    };

    struct Frame {
        Vector normal;
        Vector up;
        Vector right;

        friend constexpr bool operator==(const Frame&, const Frame&) = default;
    };

    Dice<DiceFace> arrows_;

    static constexpr Vector negate(Vector vector) noexcept {
        return Vector{-vector.x, -vector.y, -vector.z};
    }

    static constexpr DiceFace vector_to_face(Vector vector) {
        if (vector == Vector{0, 0, 1}) return DiceFace::top;
        if (vector == Vector{0, 0, -1}) return DiceFace::bottom;
        if (vector == Vector{0, 1, 0}) return DiceFace::north;
        if (vector == Vector{0, -1, 0}) return DiceFace::south;
        if (vector == Vector{1, 0, 0}) return DiceFace::east;
        if (vector == Vector{-1, 0, 0}) return DiceFace::west;
        throw std::invalid_argument("vector is not a cube direction");
    }

    static constexpr Frame adjacent_frame(
        const Frame& frame,
        DiceDirection direction
    ) noexcept {
        switch (direction) {
            case DiceDirection::north:
                return Frame{frame.up, negate(frame.normal), frame.right};
            case DiceDirection::south:
                return Frame{negate(frame.up), frame.normal, frame.right};
            case DiceDirection::east:
                return Frame{frame.right, frame.up, negate(frame.normal)};
            case DiceDirection::west:
                return Frame{negate(frame.right), frame.up, frame.normal};
        }
        return frame;
    }

    static constexpr DiceFace arrow_from_character(
        char arrow,
        const Frame& frame
    ) {
        if (arrow == '^') return vector_to_face(frame.up);
        if (arrow == 'v') return vector_to_face(negate(frame.up));
        if (arrow == '>') return vector_to_face(frame.right);
        if (arrow == '<') return vector_to_face(negate(frame.right));
        throw std::invalid_argument("arrow dice net contains an invalid character");
    }

    constexpr void rotate_arrows(DiceDirection direction) noexcept {
        for (DiceFace face : all_faces()) {
            arrows_[face] = rotate_direction(arrows_[face], direction);
        }
    }

    static constexpr std::array<DiceFace, 6> all_faces() noexcept {
        return std::array<DiceFace, 6>{
            DiceFace::top,
            DiceFace::bottom,
            DiceFace::north,
            DiceFace::south,
            DiceFace::east,
            DiceFace::west
        };
    }

public:
    constexpr ArrowDice(
        DiceFace top,
        DiceFace bottom,
        DiceFace north,
        DiceFace south,
        DiceFace east,
        DiceFace west
    )
        : arrows_(top, bottom, north, south, east, west) {}

    explicit constexpr ArrowDice(Dice<DiceFace> arrows)
        : arrows_(std::move(arrows)) {}

    [[nodiscard]] constexpr DiceFace arrow(DiceFace face) const noexcept {
        return arrows_[face];
    }

    [[nodiscard]] constexpr const Dice<DiceFace>& arrows() const noexcept {
        return arrows_;
    }

    constexpr ArrowDice& roll(DiceDirection direction) {
        arrows_.roll(direction);
        rotate_arrows(direction);
        return *this;
    }

    constexpr ArrowDice& roll_north() {
        return roll(DiceDirection::north);
    }

    constexpr ArrowDice& roll_south() {
        return roll(DiceDirection::south);
    }

    constexpr ArrowDice& roll_east() {
        return roll(DiceDirection::east);
    }

    constexpr ArrowDice& roll_west() {
        return roll(DiceDirection::west);
    }

    constexpr ArrowDice& rotate_clockwise() {
        arrows_.rotate_clockwise();
        for (DiceFace face : all_faces()) {
            arrows_[face] = rotate_direction_clockwise(arrows_[face]);
        }
        return *this;
    }

    constexpr ArrowDice& rotate_counterclockwise() {
        arrows_.rotate_counterclockwise();
        for (DiceFace face : all_faces()) {
            arrows_[face] = rotate_direction_counterclockwise(arrows_[face]);
        }
        return *this;
    }

    [[nodiscard]] constexpr std::array<ArrowDice, 24> orientations() const {
        ArrowDice top_top = *this;
        ArrowDice north_top = *this;
        north_top.roll_south();
        ArrowDice south_top = *this;
        south_top.roll_north();
        ArrowDice east_top = *this;
        east_top.roll_west();
        ArrowDice west_top = *this;
        west_top.roll_east();
        ArrowDice bottom_top = *this;
        bottom_top.roll_north().roll_north();

        std::array<ArrowDice, 6> top_orientations{
            top_top,
            north_top,
            south_top,
            east_top,
            west_top,
            bottom_top
        };
        std::array<ArrowDice, 24> result{
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this,
            *this, *this, *this, *this, *this, *this
        };

        std::size_t result_index = 0;
        for (ArrowDice oriented : top_orientations) {
            for (int rotation = 0; rotation < 4; ++rotation) {
                result[result_index++] = oriented;
                oriented.rotate_clockwise();
            }
        }
        return result;
    }

    [[nodiscard]] constexpr int difference(const ArrowDice& other) const noexcept {
        int result = 0;
        for (DiceFace face : all_faces()) {
            result += arrow(face) != other.arrow(face);
        }
        return result;
    }

    [[nodiscard]] constexpr int distance(const ArrowDice& other) const {
        int result = 6;
        for (const ArrowDice& oriented : orientations()) {
            int current = oriented.difference(other);
            if (current < result) result = current;
        }
        return result;
    }

    [[nodiscard]] static ArrowDice from_net(
        const std::vector<std::string>& net,
        char empty = '.'
    ) {
        if (net.empty()) {
            throw std::invalid_argument("arrow dice net is empty");
        }
        std::size_t width = net.front().size();
        if (width == 0) {
            throw std::invalid_argument("arrow dice net is empty");
        }
        for (const std::string& row : net) {
            if (row.size() != width) {
                throw std::invalid_argument("arrow dice net must be rectangular");
            }
        }

        int height = static_cast<int>(net.size());
        int integer_width = static_cast<int>(width);
        std::vector<std::vector<std::optional<Frame>>> frames(
            net.size(),
            std::vector<std::optional<Frame>>(width)
        );
        auto character_at = [&](int row, int column) -> char {
            return net[static_cast<std::size_t>(row)]
                      [static_cast<std::size_t>(column)];
        };
        auto frame_at = [&](int row, int column) -> std::optional<Frame>& {
            return frames[static_cast<std::size_t>(row)]
                         [static_cast<std::size_t>(column)];
        };
        std::vector<std::pair<int, int>> queue;
        int face_count = 0;
        for (int row = 0; row < height; ++row) {
            for (int column = 0; column < integer_width; ++column) {
                if (character_at(row, column) != empty) {
                    ++face_count;
                    if (queue.empty()) queue.emplace_back(row, column);
                }
            }
        }
        if (face_count != 6) {
            throw std::invalid_argument("arrow dice net must contain six faces");
        }

        Frame initial{
            Vector{0, 0, 1},
            Vector{0, 1, 0},
            Vector{1, 0, 0}
        };
        frame_at(queue.front().first, queue.front().second) = initial;

        constexpr std::array<int, 4> row_delta{-1, 1, 0, 0};
        constexpr std::array<int, 4> column_delta{0, 0, 1, -1};
        constexpr std::array<DiceDirection, 4> directions{
            DiceDirection::north,
            DiceDirection::south,
            DiceDirection::east,
            DiceDirection::west
        };
        for (std::size_t head = 0; head < queue.size(); ++head) {
            int row = queue[head].first;
            int column = queue[head].second;
            Frame frame = *frame_at(row, column);
            for (std::size_t edge = 0; edge < directions.size(); ++edge) {
                int next_row = row + row_delta[edge];
                int next_column = column + column_delta[edge];
                if (
                    next_row < 0 || next_row >= height ||
                    next_column < 0 || next_column >= integer_width ||
                    character_at(next_row, next_column) == empty
                ) {
                    continue;
                }

                Frame next_frame = adjacent_frame(frame, directions[edge]);
                std::optional<Frame>& known = frame_at(next_row, next_column);
                if (!known.has_value()) {
                    known = next_frame;
                    queue.emplace_back(next_row, next_column);
                } else if (*known != next_frame) {
                    throw std::invalid_argument("arrow dice net folds inconsistently");
                }
            }
        }
        if (queue.size() != 6) {
            throw std::invalid_argument("arrow dice net is disconnected");
        }

        std::array<std::optional<DiceFace>, 6> arrows;
        for (const std::pair<int, int>& cell : queue) {
            int row = cell.first;
            int column = cell.second;
            Frame frame = *frame_at(row, column);
            DiceFace face = vector_to_face(frame.normal);
            std::optional<DiceFace>& slot =
                arrows[static_cast<std::size_t>(face)];
            if (slot.has_value()) {
                throw std::invalid_argument("arrow dice net overlaps when folded");
            }
            slot = arrow_from_character(character_at(row, column), frame);
        }
        for (const std::optional<DiceFace>& arrow : arrows) {
            if (!arrow.has_value()) {
                throw std::invalid_argument("arrow dice net does not form a cube");
            }
        }

        return ArrowDice(
            *arrows[static_cast<std::size_t>(DiceFace::top)],
            *arrows[static_cast<std::size_t>(DiceFace::bottom)],
            *arrows[static_cast<std::size_t>(DiceFace::north)],
            *arrows[static_cast<std::size_t>(DiceFace::south)],
            *arrows[static_cast<std::size_t>(DiceFace::east)],
            *arrows[static_cast<std::size_t>(DiceFace::west)]
        );
    }

    friend constexpr bool operator==(const ArrowDice&, const ArrowDice&) = default;
};

}  // namespace utilities
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Dice
(utilities/dice.hpp)

Overview

Face convention

Operations

Simulating commands

Finding a side face

Comparing dice up to rotation

Arrows and other oriented face decorations

Direction convention

Folding a cube net

Minimum difference between arrow dice

Verified with

Code

Dice (utilities/dice.hpp)

Overview

Face convention

Operations

Simulating commands

Finding a side face

Comparing dice up to rotation

Arrows and other oriented face decorations

Direction convention

Folding a cube net

Minimum difference between arrow dice

Verified with

Code

Dice
(utilities/dice.hpp)