Help us understand the problem. What is going on with this article?

# オフラインリアルタイムどう書くE27の実装例(ruby,go)

More than 1 year has passed since last update.

オフラインリアルタイムどう書くE27の問題「とあるカードゲーム」の実装例を、まずは Go で。

https://yhpg.doorkeeper.jp/events/81346
を御覧ください。

で。

# Go による順当な実装

```package e27

import (
"fmt"
"math"
"strings"
)

func isContinuous(m map[int]int) bool {
min := math.MaxInt32
max := math.MinInt32
for k, v := range m {
if v != 1 {
return false
}
if k < min {
min = k
}
if max < k {
max = k
}
}
return max-min+1 == len(m)
}

func isStoryOrKind(cards []string) bool {
suits := make(map[int]int)
ranks := make(map[int]int)
for _, c := range cards {
suits[int(c[0])]++
ranks[int(c[1])]++
}
if 1 == len(suits) && isContinuous(ranks) {
return true
}
if 1 == len(ranks) && isContinuous(suits) {
return true
}
return false
}

func eachSplit(cards []string, proc func(hand [][]string)) {
switch len(cards) {
case 0:
proc(make([][]string, 0))
case 1:
// noting to do.
case 2, 3:
if isStoryOrKind(cards) {
proc([][]string{cards})
}
default:
maxbits := 1 << uint(len(cards)-1)
for bits := 1; bits < maxbits; bits++ {
tail := []string{}
for b := uint(0); b < uint(len(cards))-1; b++ {
if 0 != (bits & (1 << b)) {
} else {
tail = append(tail, cards[b+1])
}
}
continue
}
eachSplit(tail, func(hand [][]string) {
proc(h)
})
}
}
}

func scoreOf(hand [][]string) int {
s := 0
for _, c := range hand {
s += (len(c) - 1) * (len(c) - 1)
}
return s
}

func solve(src string) string {
cards := strings.Split(src, ",")
score := 0
eachSplit(cards, func(hand [][]string) {
s := scoreOf(hand)
if score < s {
score = s
}
})
if score == 0 {
return "-"
}
return fmt.Sprintf("%d", score)
}
```
test(go)
```package e27

import "testing"

func Test(t *testing.T) {
var tests = []struct {
name  string
input string
want  string
}{
{"0", "A1,A2,A3,A4,B3,C3,D5,E5", "11"},
{"1", "A1,B2,C3,D4,E5,F6,G7,A8", "-"},
{"2", "A3,A5,A4,A6,A7,A1,A2,A8", "49"},
// 中略
{"70", "A8,D8,D6,D7,C8,B8,E8,C7", "4"},
}
for _, test := range tests {
got := solve(test.input)
if got != test.want {
t.Errorf("%v: solve(%q)=%q, want %q\n", test.name, test.input, got, test.want)
}
}
}
```

もともと ruby で書いていたんだけど、会場で go に移植したもの。

ruby で書くと半分ぐらいの行数になるんだけどね。

# ruby による遅い実装

つづいて ruby による遅いけど書くのが楽な実装。

ruby
```PATTERNS = [
[8],
[6,2],
[5,3],
[4,4], [4,2,2],
[3,3,2], [2,2,2,2],
].freeze

def scoreof(pat)
pat.map{ |x| (x-1)**2 }.sum
end

def split(pat,perm0)
perm = perm0.dup
pat.each.with_object([]) do |u,o|
o.push( Array.new(u){ perm.pop } )
end
end

def story_or_kind?(s,r)
r.sort == [*r.min..r.max] && s.uniq.size==1
end

def out?(pat,perm)
split(pat,perm).all?{ |unit|
suits = unit.map(&:real)
ranks = unit.map(&:imag)
story_or_kind?(suits,ranks) || story_or_kind?(ranks,suits)
}
end

def impl(src)
PATTERNS.each do |pat|
src.permutation(src.size) do |perm|
return scoreof(pat) if out?(pat,perm)
end
end
nil
end

def solve(src)
impl(src.split(",").map{ |x|
s,r = x.chars.map(&:ord)
(s-?A.ord) + (r-?1.ord) * 1i
})&.to_s || "-"
end
```

テストを走らせるコードは省略。

`permutation` で8の階乗通り並べて、それを `PATTERNS` に従って分割。
「あがり」かどうか調べて「あがり」なら得点を計算するというもの
これでも70個走らせて手元のマシンで 2分弱。オフラインリアルタイムどう書くとしては、「勝ち」になるのでこれもアリ。

たぶん解答者側だったらまずこれを書くと思う。遅いけどね。

なお。メソッド名の `out?` は、辞書で「あがり」を引いたもの。

Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away