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 で。

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

Nabetani
横浜へなちょこプログラミング勉強会をやっていました。 / CodeIQ の出題者でした。 / 日経 WinPC に連載を持っていました(名義が違うけど) / Yokohama rb に半分ぐらい参加しています。 / twitter : http://twitter.com/Nabetani
https://nabetani.hatenadiary.com/
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