Subscribed unsubscribe Subscribe Subscribe

Empty

2013年4月から社会人になりました。

気分転換に競技プログラミング: Google Code Jam Qualification Round 2012: Problem A. Speaking in Tongues

Google Code Jam 2012 の Qualification Round Problem A. Speaking in Tonguesを解いたので、書いたコードを晒してみる。

solve.py

#!/usr/bin/env python
# coding: utf-8

"""
Google Code Jam 2012: Problem A. Speaking in Tongues
http://code.google.com/codejam/contest/1460488/dashboard

$ solve.py < input.in
"""

import sys
import string

sample_set = [
    "ejp mysljylc kd kxveddknmc re jsicpdrysi",
    "rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd",
    "de kr kd eoya kw aej tysr re ujdr lkgc jv",
]

answer_set = [
    "our language is impossible to understand",
    "there are twenty six factorial possibilities",
    "so it is okay if you want to just give up",
]

def understand_sample():
    replace_set = {}
    for i, text in enumerate(sample_set):
        answer_text = list(answer_set[i])
        if not len(text) == len(answer_text): sys.exit("Error sample")
        for j, char in enumerate(list(text)):
            replace_set[char] = answer_text[j]
    if len(replace_set) - 1 == len(string.lowercase):
        pass
    elif len(replace_set) == len(string.lowercase):
        for char in list(string.lowercase):
            if not char in replace_set.keys(): key_char = char
            if not char in replace_set.values(): value_char = char
        replace_set[key_char] = value_char
    elif len(replace_set) + 1 == len(string.lowercase):
        key_chars = []
        value_chars = []
        for char in list(string.lowercase):
            if not char in replace_set.keys():
                key_chars.append(char)
            if not char in replace_set.values():
                value_chars.append(char)
        value_chars.sort()
        key_chars.sort()
        if value_chars == key_chars:
            replace_set[key_chars[0]] = value_chars[1]
            replace_set[key_chars[1]] = value_chars[0]
    return replace_set

def read():
    f = sys.stdin
    num = int(f.next().strip())
    return [f.next().strip() for i in range(num)]

def main(replace_set):
    for i, text in enumerate(read()):
        try:
            replaced_text = "".join([replace_set.get(char)\
                                    for char in list(text)])
        except TypeError:
            raise
        print "Case #%d: %s" % ( i+1, replaced_text )

if __name__ == "__main__":
    replace_set = understand_sample()
    main(replace_set)

A-small-practice.in

30
ejp mysljylc kd kxveddknmc re jsicpdrysi
rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd
de kr kd eoya kw aej tysr re ujdr lkgc jv
hello i am the google code jam test data
how are you
aynny iynny aynny iynny aynny iynny aynny iynny aynny iynny aynny iynny aynny iynny aynny ieeeeeeeee
y n f i c w l b k u o m x s e v z p d r j g a t h a q set k oset xa ynfd
schr rkxc tesr aej dksl tkrb xc
wep rbedc tbe dvcyo ks y resljc ie ser dvcyo re erbcp vcevmc
seneia jsicpdrysid rbcx dksfc rbca ypc dvcyoksl xadrcpkcd ks rbc dvkpkr
rbkd kd de chfkrksl k bygc re le rbc nyrbpeex
kr tyd rbc ncdr ew rkxcd kr tyd rbc nmjpdr ew rkxcd
mcr mkvd ie tbyr bysid ie
rbkd bcpc kd ljsveticp yfrkgyrci rtcsra dcgcs fymkncp wjmm yjre se okfonyfo sykmrbpetksl xyabcx
k bygc ncdrci wpjkr dvkoc ysi xees set k dbymm ncdr aej rbc lja
eb byk kx ks jp fexvjrcp cyrksl aejp fbccqnjplcpd ysi leelmcpcdksl aejp rchrq
ys cac wep ys cac ysi y vklces wep y vklces
ymm aejp nydc ypc ncmesl re cppep rbc dveesa nypi
aej vkddci eww rbc fbkfocs myia
set kd rbc djxxcp ew ejp myfo ew ikdfesrcsr
na rbc vpkfoksl ew xa rbjxnd dexcrbksl tkfoci rbkd tya fexcd
ks y tepmi ew ikpctemgcd ysi mkesd dexcrkxcd rbc pypcdr fpcyrjpc kd y wpkcsi
lpccrksld fbccdc vevdkfmc rbc sjxncp aej bygc ikymci kd fjppcsrma ejr ew vepofbevd
tba ie vpelpyxxcpd ymtyad xkh jv bymmetccs ysi fbpkdrxyd
kx fexxysicp dbcvypi ysi rbkd kd xa wygepkrc vpenmcx es rbc leelmc feic uyx
w ew rte czjymd w ew esc czjymd esc
wep k ncrtccs rbpcc ysi s w ew k czjymd w ew k xksjd esc vmjd w ew k xksjd rte
bet ypc aej bemiksl jv ncfyjdc kx y veryre
ip qykjd ip qykjd ip qykjd ip qykjd eeeeeeeeeeeeb ip qykjd
tbeeeeeeeeeeeeeeeeeeeyyyyyyyyy k oset f vmjd vmjd

output

Case #1: our language is impossible to understand
Case #2: there are twenty six factorial possibilities
Case #3: so it is okay if you want to just give up
Case #4: xoggk d yl wxo vkkvgo ekso uyl wonw sywy
Case #5: xkf yto akj
Case #6: yabba dabba yabba dabba yabba dabba yabba dabba yabba dabba yabba dabba yabba dabba yabba dooooooooo
Case #7: a b c d e f g h i j k l m n o p q r s t u v y w x y z now i know my abcs
Case #8: next time wont you sing with me
Case #9: for those who speak in a tongue do not speak to other people
Case #10: nobody understands them since they are speaking mysteries in the spirit
Case #11: this is so exciting i have to go the bathroom
Case #12: it was the best of times it was the blurst of times
Case #13: let lips do what hands do
Case #14: this here is gunpowder activated twenty seven caliber full auto no kickback nailthrowing mayhem
Case #15: i have bested fruit spike and moon now i shall best you the guy
Case #16: oh hai im in ur computer eating your cheezburgers and googleresing your textz
Case #17: an eye for an eye and a pigeon for a pigeon
Case #18: all your base are belong to error the spoony bard
Case #19: you pissed off the chicken lady
Case #20: now is the summer of our lack of discontent
Case #21: by the pricking of my thumbs something wicked this way comes
Case #22: in a world of direwolves and lions sometimes the rarest creature is a friend
Case #23: greetings cheese popsicle the number you have dialed is currently out of porkchops
Case #24: why do programmers always mix up halloween and christmas
Case #25: im commander shepard and this is my favorite problem on the google code jam
Case #26: f of two equals f of one equals one
Case #27: for i between three and n f of i equals f of i minus one plus f of i minus two
Case #28: how are you holding up because im a potato
Case #29: dr zaius dr zaius dr zaius dr zaius ooooooooooooh dr zaius
Case #30: whoooooooooooooooooooaaaaaaaaa i know c plus plus

ながーいコードになってしまい悔しいです。久々に競技プログラミングすると楽しいですね。また気分転換にやりたいと思います。