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

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

問題 : http://nabetani.sakura.ne.jp/hena/orde27cardgame/
実装リンク集 : https://qiita.com/Nabetani/items/cdc102d186faaf542574
イベント : https://yhpg.doorkeeper.jp/events/79705

次回のイベントは 11/3。
詳しくは
https://yhpg.doorkeeper.jp/events/81346
を御覧ください。

で。

Go による順当な実装

実装(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++ {
			head := []string{cards[0]}
			tail := []string{}
			for b := uint(0); b < uint(len(cards))-1; b++ {
				if 0 != (bits & (1 << b)) {
					head = append(head, cards[b+1])
				} else {
					tail = append(tail, cards[b+1])
				}
			}
			if !isStoryOrKind(head) {
				continue
			}
			eachSplit(tail, func(hand [][]string) {
				h := append(hand, head)
				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 で書くと半分ぐらいの行数になるんだけどね。

書いてて辛かったのは、 int 用の min, max がないとか、その辺り。

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? は、辞書で「あがり」を引いたもの。