オフラインリアルタイムどう書くE04 をビット演算で解いた・その２

解説はそのうち…。

• 問題はこちら: http://mtsmfm.github.io/2016/06/04/doukaku-e04.html
• Ruby のコードはこちら: http://qiita.com/emattsan/items/cb65001e2b4b76faf6cd
• 各人の実装へのリンク集はこちら: http://qiita.com/mtsmfm/items/6d9112fcc568908caaba

C++

orde04.cpp

#include <iostream>
#include <string>
#include <numeric>

struct Roll
{
    unsigned int rock;

    Roll(unsigned int rock) : rock(rock) {}

    unsigned int operator () (unsigned int death_route, char b)
    {
        const unsigned int branch      = (0x181u >> (8 - (b - '0'))) & 0xff;

        if(rock & branch)
        {
            rock ^= branch;
            return death_route | branch;
        }

        if(((death_route ^ branch) & branch) * (death_route & branch))
        {
            return death_route ^ branch;
        }

        return death_route;
    }
};

std::string solve(const std::string& input)
{
    auto i = std::find(input.begin(), input.end(), ':');
    std::string branches(input.begin(), i);
    unsigned int rock = 1u << (*++i - 'A');

    unsigned int death_route = std::accumulate(branches.begin(), branches.end(), rock, Roll(rock));

    std::string actual;

    for(int i = 0; i < 8; ++i)
    {
        if(((death_route >> i) & 1) == 0)
        {
            actual += ('A' + i);
        }
    }

    return actual;
}

void test(const std::string& input, const std::string& expected)
{
    std::string actual = solve(input);
    if(actual == expected)
    {
        std::cout << "\x1b[32m.\x1b[0m" << std::flush;
    }
    else
    {
        std::cout
          << "\x1b[31m\n"
          << "input:    " << input << "\n"
          << "expected: " << expected << "\n"
          << "actual:   " << actual << "\x1b[0m\n"
          << std::flush;
    }
}

int main(int, char* argv[])
{
    test("2512:C", "DEFGH");
    test("1:A", "CDEFGH");
    test(":C", "ABDEFGH");
    test("2345:B", "AGH");
    test("1256:E", "ABCDH");
    test("1228:A", "ADEFG");
    test("5623:B", "AEFGH");
    test("8157:C", "ABDEFGH");
    test("74767:E", "ABCFGH");
    test("88717:D", "ABCEFGH");
    test("148647:A", "ACDEFH");
    test("374258:H", "BCDEFH");
    test("6647768:F", "ABCDEH");
    test("4786317:E", "ABFGH");
    test("3456781:C", "");
    test("225721686547123:C", "CEF");
    test("2765356148824666:F", "ABCDEH");
    test("42318287535641783:F", "BDE");
    test("584423584751745261:D", "FGH");
    test("8811873415472513884:D", "CFG");
    test("74817442725737422451:H", "BCDEF");
    test("223188865746766511566:C", "ABGH");
    test("2763666483242552567747:F", "ABCG");
    test("76724442325377753577138:E", "EG");
    test("327328486656448784712618:B", "");
    test("4884637666662548114774288:D", "DGH");
    test("84226765313786654637511248:H", "DEF");
    test("486142154163288126476238756:A", "CDF");
    test("1836275732415226326155464567:F", "BCD");
    test("62544434452376661746517374245:G", "G");
    test("381352782758218463842725673473:B", "A");

    std::cout << std::endl;

    return 0;
}

Haskell

orde04.hs

import Data.Bits
import Data.Char
import Data.List
import Data.Word

roll :: (Word, Word) -> Word -> (Word, Word)
roll (rock, death_route) branch
  | rock .&. branch /= 0 = (rock `xor` branch, death_route .|. branch)
  | ((death_route `xor` branch) .&. branch) * (death_route .&. branch) /= 0 = (rock, death_route `xor` branch)
  | otherwise = (rock, death_route)

runOver = map fst.filter (\(c, b) -> b == 0).zip ['A'..'H'].unfoldr (\n -> Just (n .&. 1, shiftR n 1))

solve input =
  runOver $ snd $ foldl' roll (rock, rock) branches
  where
    (branches, rock) = (\(bs, [':', r]) -> (map (\b -> (shiftR 0x181 (8 - (ord b - ord '0'))) .&. 0xff::Word) bs, shiftL (1::Word) (ord r - ord 'A'))) $ break (== ':') input

test input expected =
  if actual == expected
  then
    putStr "\x1b[32m.\x1b[0m"
  else do
    putStrLn "\x1b[31m"
    putStr "input:    "
    putStrLn $ input
    putStr "expected: "
    putStrLn $ expected
    putStr "actual:   "
    putStrLn $ actual
    putStr "\x1b[0m"
  where
    actual = solve input

main = do
  test "2512:C" "DEFGH"
  test "1:A" "CDEFGH"
  test ":C" "ABDEFGH"
  test "2345:B" "AGH"
  test "1256:E" "ABCDH"
  test "1228:A" "ADEFG"
  test "5623:B" "AEFGH"
  test "8157:C" "ABDEFGH"
  test "74767:E" "ABCFGH"
  test "88717:D" "ABCEFGH"
  test "148647:A" "ACDEFH"
  test "374258:H" "BCDEFH"
  test "6647768:F" "ABCDEH"
  test "4786317:E" "ABFGH"
  test "3456781:C" ""
  test "225721686547123:C" "CEF"
  test "2765356148824666:F" "ABCDEH"
  test "42318287535641783:F" "BDE"
  test "584423584751745261:D" "FGH"
  test "8811873415472513884:D" "CFG"
  test "74817442725737422451:H" "BCDEF"
  test "223188865746766511566:C" "ABGH"
  test "2763666483242552567747:F" "ABCG"
  test "76724442325377753577138:E" "EG"
  test "327328486656448784712618:B" ""
  test "4884637666662548114774288:D" "DGH"
  test "84226765313786654637511248:H" "DEF"
  test "486142154163288126476238756:A" "CDF"
  test "1836275732415226326155464567:F" "BCD"
  test "62544434452376661746517374245:G" "G"
  test "381352782758218463842725673473:B" "A"
  putStrLn ""