Mazn.net

やってみて 調べてみて 苦労しなけりゃ 箱は動かじ

プログラミングコンテストの模擬練習(ババ抜き)を解いてみた

   

以下で紹介されていたプログラミングコンテストの模擬練習問題(ババ抜き)をpythonの勉強がてら解いてみた。使ったpythonのバージョンは、2.7.3です。

http://www.gizmodo.jp/2013/12/recruit_programming_contest.html
http://recruit-programing-contest-practice.contest.atcoder.jp/tasks/recruite_2013_pre_a

ファイル名 : baba.py

#! /usr/bin/python
# -*- coding: utf8 -*-
import copy

class Person():
    def __init__(self,card):
        self.cardList = list(card)
        self.cardList.pop() # remove \n

    def addCardAndCompare(self,card):
        if card in self.cardList:
            self.cardList.remove(card)
            return True
        else:
            self.cardList.append(card)
            return False

    def pickLeftCard(self):
        card = self.cardList.pop(0)
        return card

    def isWin(self):
        if len(self.cardList) == 0:
            return True
        return False

    def __eq__(self, other):
        if len(self.cardList) != len(other.cardList):
            return False
        for i in range(len(self.cardList)):
            if self.cardList[i] != other.cardList[i]:
                return False
        return True

class TestCase():
    def __init__(self, file):
        self.pickCount = 0
        self.picker = 0
        self.target = 1
        self.Fighters = int(file.readline())
        self.personList = []
        self.personListCopy = []
        self.detectLoop = True
        for i in range(self.Fighters):
            self.personList.append(Person(file.readline()))
        self.personListCopy = copy.deepcopy(self.personList)
        self.fight()

    def checkCardList(self, p):
        self.person = self.personList[p]
        if self.person.isWin():
            self.personList.pop(p)
            del(self.person)
            self.Fighters -= 1
            return True
        return False

    def pickCard(self):
        self.pickCount += 1
        self.card = self.personList[self.target].pickLeftCard()

        if self.personList[self.picker].addCardAndCompare(self.card):
            self.detectLoop = False
        if self.checkCardList(self.target):
            self.detectLoop = False
            if self.target < self.picker:
                self.picker -= 1
        if self.checkCardList(self.picker):
            self.detectLoop = False
        if not self.detectLoop:
            self.personListCopy = copy.deepcopy(self.personList)

    def fight(self):
        while True:
            self.pickCard()
            if self.detectLoop:
                if self.personListCopy == self.personList:
                    print "-1"
                    return 0
            self.detectLoop = True
            self.picker = (self.picker + 1) % self.Fighters
            self.target = (self.picker + 1) % self.Fighters
            if self.picker == self.target:
                if len(self.personList) == 0:
                    print self.pickCount
                    return 0
                if self.personList[0].cardList[0] == 'J':
                    print self.pickCount
                    return 0
                print "-1"

inputFile = open("input.txt", "r")
for i in range(int(inputFile.readline())):
    testCase = TestCase(inputFile)
    del testCase
inputFile.close()

実行には以下の入力ファイルを、input.txt というファイル名で同じディレクトリに置いておく必要があります。

3
3
16372
2746J18
348
4
1234
1234
1234
1234J
5
13645
643125
147
5137J
3245

実行結果

$ ./baba.py 
15
29
-1

もっとスマートの解き方はありそうだが、とりあえず動いてます。

 - IT技術, プログラミング

336px

Message

メールアドレスが公開されることはありません。

  関連記事

no image
gitで複数のコミットを一つにしてマージする

自分の開発ブランチではこまめにコミットしたいけど、リリース用のブランチにはもっと …

no image
Windows bash (win-bash)のプロセスのfork性能を測ってみた

Windows上では今までCygwinを使っていたのですが、Cygwinはプロセ …

no image
initrd を展開しファイルを編集する @ Fedora 16

Fedora 16 Live CD の initrd を編集する必要があったので …

no image
vimでBackSpaceが効かない@Cygwin

Cgywin上で、BackSpace が効かず、文字が消せない場合は、~/.vi …

no image
OpenOffice 3のインストール@debian系 Linux

OpenOffice 3がリリースされたので、Linuxにインストールしてみまし …

no image
Windowsのtelnetコマンドの文字コード@Windows XP

限られた環境で、ターミナルのソフトにWindowsのtelnetしかない場合、t …

no image
Googleブック検索

まだβ版ですが、いつの間にかGoogleのブック検索というサービスが動いています …

no image
EJB3 JPAのmapping-type @ JBoss 4.2

JBoss 4.2 でEJB3のJPA (JAVA Persistence AP …

休止状態やハイバネート後のキーボード入力が遅い@Windows10

Windows10を使ってるのですが、休止状態から復帰するとなぜかキーボードのリ …

no image
rubyの文字コードについて考える

rubyでは、1.6以降漢字コードを特別に解釈しなくなったようです。 maznは …