Go

package main

import (
    "encoding/json"
    "fmt"
    "io/ioutil"
    "os"
    "strconv"
    "strings"
    "time"
)

func isGuru(b, i int32) bool {
    prev := int32(-1)
    for {
        num := i % b
        if 0 <= prev && prev != num && prev != (num+1)%b {
            return false
        }
        i = (i - num) / b
        if i == 0 {
            return true
        }
        prev = num
    }
}

func impl(b, x, y int32) int32 {
    c := int32(0)
    for i := x; i <= y; i++ {
        if isGuru(b, i) {
            c++
        }
    }
    return c
}

func solveSlow(src string) string {
    vals := strings.Split(src, ",")
    b, e0 := strconv.Atoi(vals[0])
    x, e1 := strconv.ParseInt(vals[1], b, 32)
    y, e2 := strconv.ParseInt(vals[2], b, 32)
    if e0 != nil || e1 != nil || e2 != nil {
        panic(fmt.Sprint(e0, e1, e2))
    }
    count := impl(int32(b), int32(x), int32(y))
    return fmt.Sprint(count)
}

func bytesFromFile(fn string) []byte {
    f, err := os.Open(fn)
    if err != nil {
        panic(err)
    }
    defer f.Close()
    b, err := ioutil.ReadAll(f)
    if err != nil {
        panic(err)
    }
    return b
}

type testDataType struct {
    Number   int    `json:"number"`
    Src      string `json:"src"`
    Expected string `json:"expected"`
}

type dataType struct {
    EventID  string         `json:"event_id"`
    EventURL string         `json:"event_url"`
    TestData []testDataType `json:"test_data"`
}

func runTest(list []testDataType) {
    for _, t := range list {
        start := time.Now()
        actual := solveSlow(t.Src)
        tick := time.Now().Sub(start).Seconds()
        result := func() string {
            if actual == t.Expected {
                return "ok"
            }
            return "***NG***"
        }()
        fmt.Printf("%2d:%s solve(%q)=%q, want %q ( %.3f sec )\n", t.Number, result, t.Src, actual, t.Expected, tick)
    }
}

func main() {
    data := dataType{}
    json.Unmarshal(bytesFromFile(os.Args[1]), &data)
    start := time.Now()
    runTest(data.TestData)
    tick := time.Now().Sub(start).Seconds()
    fmt.Printf("total : %.2f sec\n", tick)
}

実行は go run slow.go data.json みたいな感じで。

随所で int32 と書いているのは、int よりもたぶん速いから。手元の環境では int は 64bit なので、落ちるコードに差が出てくる。

この実装で、手元の環境で 75秒ぐらい。
goルーチンを活用すれば半分ぐらいにはなるはずだけど、何もしていない。

C++

こちらは、cielavenir さんの記事を参考にして、OpenMP を入れてみた。

c++17

// clang++ -O2 -std=c++17 -Wall -Xpreprocessor -fopenmp -lomp  3.cpp

#include <iomanip>
#include <iostream>
#include <numeric>
#include <regex>
#include <sstream>
#include <string>

int is_guru(int b, int i) {
  auto prev{-1};
  for (;;) {
    auto num = i % b;
    if (0 <= prev && prev != num && prev != (num + 1) % b) {
      return 0;
    }
    i = (i - num) / b;
    if (i == 0) {
      return 1;
    }
    prev = num;
  }
}

std::string solve(std::string const &src) {
  auto regex = std::regex(R"(^([^\,]+)\,([^\,]+)\,([^\,]+))");
  std::smatch m;
  std::regex_match(src, m, regex);
  auto b = std::stoi(m[1]);
  auto x = std::strtol(m[2].str().c_str(), nullptr, b);
  auto y = std::strtol(m[3].str().c_str(), nullptr, b);
  int count = 0;
#pragma omp parallel for reduction(+ : count)
  for (int i = x; i <= y; ++i) {
    count += is_guru(b, i);
  }
  return std::to_string(count);
}

void test(std::string const &src, std::string const &expected) {
  auto actual{solve(src)};
  auto okay{actual == expected};
  std::cout << (okay ? "ok" : "**NG**") << " " << src << " " << actual << " "
            << expected << std::endl;
}

int main() {
  /*0*/ test("4,1313,3012", "12");
  /*1*/ test("10,100,110", "0");
  /*2*/ test("36,zoo,zyz", "0");
  /*3*/ test("4,1300000,2222221", "0");
  // 中略
  /*68*/ test("2,101001011010110000110101,110101110001110110110101", "3240321");
}

Go の実装とロジックは同じ。
というか、Go の実装を移植しただけ。
入力のパースで正規表現を使ってみた。std::split とかあると嬉しいんだけどなぁ。
「中略」のところを略さないで実行して、手元のマシンで、10秒弱。OpenMP 様々。

オフラインリアルタイムどう書く E31 の実装例( Go, C++ )

Go

C++