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 最低限の設定@CentOS 5

分散型バージョン管理システムgit をCentOS 5上で使ってみた。 まずCe …

no image
VirtualBox 5.0上のUbuntuの時間がずれる@Windows10

Windows 10 上にVirtualBox 5.0をインストールして、Ubu …

no image
管理共有(C$)の使用@Windows 7

Windows XPだと、ファイルの共有を設定しなくても、デフォルトでCドライブ …

GO言語1.12の新機能モジュールを使う

GO 1.12から、公式にmoduleが使えるようになるようなので、一足先に1. …

no image
日本語入力のON/OFFのキーを変更する@Fedora 17

Fedora 17 のデフォルトの日本語入力切り替えのキーは、Ctrl + Sp …

no image
QRコードスキャナーのようなカメラ使うアプリが起動しない@Galaxy S (2.2)

標準のカメラアプリは正常に動作するのに、QRコードスキャナやFxCamera と …

no image
ファイルサーバへのアクセスが異常に遅い@Windows XP or Vista

Windowsからファイルサーバ上のファイルにアクセスしようとすると、異常に遅い …

no image
タイムゾーンの変更方法@RHEL

RHELやCentoSインストール時にタイムゾーン間違ったり、VMwareでクイ …

no image
CodeReadingWiki 改造版でソースコード解読

etherさん作成のCodeReadingWiki が、ソースコードを読むのにす …

no image
Android のセキュリティ確保したけりゃこれ使ってみろ

最近は、Androidもマルウェアやウィルスにさらされてくるようになりました。 …