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
Googleの検索に検索ツールが出現

GoogleでWeb検索すると、いつの間にか”検索ツール&#8220 …

no image
bashでの配列操作

あまりbashの配列操作を書くことがないから覚え書き。 定義方法は &#8220 …

no image
Thinkpad USB Trackpoint キーボードでスクロール@Fedora 17

Fedora 17 上で、Thinkpad USB Trackpoint キーボ …

no image
Google IME (mozc) のインストール@Fedora 17

Google製のLinux用IME、Mozc をインストールしてみた。 # yu …

no image
起動時にswaponを実行して、スワップを有効にする @ Android Galaxy S with root

Galaxy S は、Google Map 使うとフリーズしてしまうが、スワップ …

no image
IPアドレスの範囲からサブネットマスクを簡単に計算する@CentOS 5

ちょっとしたアタックがあるIPからあった場合に、whois で IP の情報調べ …

no image
vim-rubyインストール@Debian etch

vim-rubyを使うとrubyのプログラム編集で、補完機能を使うことができるら …

no image
パイプを使ったループの中で使用した変数をループ外で参照できない@bash

bashでパイプを使って以下のような処理をすると、ループ内の変数の値をループ外で …

no image
TCP Wrapper の設定チェック@Linux

昔からあるアクセス制限の方法として、TCP Wrapperがあります。 /etc …

no image
ApacheのNameVirtualHostのデフォルトサイト設定(含SSL)@CentOS 5

CentOS 5 のApacheで、名前ベースのバーチャルホストを構築してみた。 …