A train line has two stations on it, A and B. Trains can take trips
from A to B or from B to A multiple times during a day. When a train
arrives at B from A (or arrives at A from B), it needs a certain amount
of time before it is ready to take the return journey - this is the turnaround time. For example, if a train arrives at 12:00 and the turnaround time is 0 minutes, it can leave immediately, at 12:00.
A train timetable specifies departure and arrival time of all trips between A and B. The train company needs to know how many
trains have to start the day at A and B in order to make the timetable work:
whenever a train is supposed to leave A or B, there must actually be one there
ready to go. There are passing sections on the track, so trains don't
necessarily arrive in the same order that they leave. Trains may not travel on trips that do not appear on the schedule.
Input
The first line of input gives the number of cases, N. N test
cases follow.
Each case contains a number of lines. The first line is the
turnaround time, T, in minutes. The next line has two numbers on it,
NA and NB. NA is the number of trips from A to B,
and NB is the number of trips from B to A. Then there are
NA lines giving the details of the trips from A to B.
Each line contains two fields, giving the HH:MM departure and arrival
time for that trip. The departure time for each trip will be earlier
than the arrival time. All arrivals and departures occur on the same
day. The trips may appear in any order - they are not necessarily
sorted by time. The hour and minute values are both two digits,
zero-padded, and are on a 24-hour clock (00:00 through 23:59).
After these NA lines,
there are NB lines giving the departure and arrival times for the
trips from B to A.
Output
For each test case, output one line containing "Case #x: " followed
by the number of trains that must start at A and the number of trains that
must start at B.
C:\CodeJam\2008Qualification\TrainT imetable>c:\Python25\python.exe run.py B-small-practice.in the number of tc : 20 Case #1: 0 2 Case #2: 1 0 Case #3: 2 0 Case #4: 4 2 Case #5: 3 1 Case #6: 3 2 Case #7: 3 5 Case #8: 1 10 Case #9: 8 7 Case #10: 7 7 Case #11: 7 11 Case #12: 1 1 Case #13: 2 0 Case #14: 3 6 Case #15: 13 0 Case #16: 0 8 Case #17: 6 8 Case #18: 2 2 Case #19: 6 3 Case #20: 8 4
C:\CodeJam\2008Qualification\TrainT imetable>c:\Python25\python.exe run.py B-large-practice.in the number of tc : 100 Case #1: 0 2 Case #2: 1 0 Case #3: 3 2 Case #4: 1 1 Case #5: 4 1 Case #6: 2 2 Case #7: 3 3 Case #8: 5 6 Case #9: 2 10 Case #10: 0 44 Case #11: 10 35 Case #12: 8 29 Case #13: 84 5 Case #14: 2 11 Case #15: 21 0 Case #16: 6 10 Case #17: 14 0 Case #18: 0 11 Case #19: 6 10 Case #20: 4 2 Case #21: 4 6 Case #22: 7 5 Case #23: 50 50 Case #24: 40 35 Case #25: 27 31 Case #26: 25 26 Case #27: 16 29 Case #28: 10 32 Case #29: 14 20 Case #30: 10 26 Case #31: 5 26 Case #32: 8 26 Case #33: 8 26 Case #34: 9 27 Case #35: 9 28 Case #36: 6 33 Case #37: 7 35 Case #38: 5 35 Case #39: 4 37 Case #40: 4 38 Case #41: 6 41 Case #42: 4 42 Case #43: 12 34 Case #44: 5 42 Case #45: 9 38 Case #46: 8 39 Case #47: 6 43 Case #48: 6 42 Case #49: 5 45 Case #50: 6 46 Case #51: 4 51 Case #52: 9 55 Case #53: 11 56 Case #54: 7 54 Case #55: 10 59 Case #56: 7 62 Case #57: 9 66 Case #58: 9 65 Case #59: 8 74 Case #60: 13 74 Case #61: 8 82 Case #62: 17 78 Case #63: 50 49 Case #64: 26 25 Case #65: 21 17 Case #66: 21 10 Case #67: 17 10 Case #68: 16 9 Case #69: 16 7 Case #70: 11 11 Case #71: 12 6 Case #72: 12 9 Case #73: 10 8 Case #74: 9 9 Case #75: 11 9 Case #76: 9 7 Case #77: 8 10 Case #78: 9 8 Case #79: 10 6 Case #80: 10 5 Case #81: 9 7 Case #82: 7 6 Case #83: 2 1 Case #84: 2 1 Case #85: 2 1 Case #86: 1 2 Case #87: 2 1 Case #88: 2 1 Case #89: 3 2 Case #90: 3 2 Case #91: 1 2 Case #92: 1 2 Case #93: 2 1 Case #94: 4 1 Case #95: 3 1 Case #96: 1 2 Case #97: 4 2 Case #98: 2 2 Case #99: 2 2 Case #100: 10 9
요즘 기분이 꿀꿀해서 CodeJam 2008 Qualification Round 문제 중 하나인, 'Saving the Universe'를 풀어봤습니다.
1번 문제(Saving the Universe)는 다음과 같습니다.
Problem
The urban legend goes that if you go to the Google homepage and search
for "Google", the universe will implode. We have a secret to share...
It is true! Please don't try it, or tell anyone. All right, maybe not.
We are just kidding.
The same is not true for a universe far far away. In that universe,
if you search on any search engine for that search engine's name, the
universe does implode!
To combat this, people came up with an interesting solution. All
queries are pooled together. They are passed to a central system that
decides which query goes to which search engine. The central system
sends a series of queries to one search engine, and can switch to
another at any time. Queries must be processed in the order they're
received. The central system must never send a query to a search engine
whose name matches the query. In order to reduce costs, the number of
switches should be minimized.
Your task is to tell us how many times the central system will have
to switch between search engines, assuming that we program it
optimally.
Input
The first line of the input file contains the number of cases, N. N test cases follow.
Each case starts with the number S -- the number of search engines. The next S
lines each contain the name of a search engine. Each search engine name
is no more than one hundred characters long and contains only uppercase
letters, lowercase letters, spaces, and numbers. There will not be two
search engines with the same name.
The following line contains a number Q -- the number of incoming queries. The next Q lines will each contain a query. Each query will be the name of a search engine in the case.
Output
For each input case, you should output:
Case #X: Y
where X is the number of the test case and Y is the number of search engine switches.
Do not count the initial choice of a search engine as a switch.
C:\CodeJam\2008Qualification\Saving Universe>c:\Python25\python.exe savinguniverse.py A-small-practice.in the number of tc : 20 Case #1: 0 Case #2: 0 Case #3: 1 Case #4: 1 Case #5: 3 Case #6: 3 Case #7: 99 Case #8: 48 Case #9: 10 Case #10: 3 Case #11: 0 Case #12: 1 Case #13: 5 Case #14: 2 Case #15: 0 Case #16: 1 Case #17: 2 Case #18: 3 Case #19: 1 Case #20: 2
C:\CodeJam\2008Qualification\Saving Universe>c:\Python25\python.exe savinguniverse.py A-large-practice.in the number of tc : 20 Case #1: 0 Case #2: 0 Case #3: 1 Case #4: 1 Case #5: 3 Case #6: 3 Case #7: 999 Case #8: 498 Case #9: 12 Case #10: 1 Case #11: 4 Case #12: 1 Case #13: 6 Case #14: 0 Case #15: 1 Case #16: 11 Case #17: 1 Case #18: 3 Case #19: 3 Case #20: 2
요즘 뜨는 SNS인 트위터를 회사에서 모니터링하기에는 너무 눈치가 보여서, 브라우저 플러그인이나 독립어플이 아닌 커멘트라인으로 어떻게 바꿀 수 있을까 생각 중이었는데요. 트위터는 open api가 잘 되어있고, python-twitter 모듈이 쉽게 정리되어 있어서 구현이 정말 쉽더군요.
특히 왜 이렇게 스팸들이 많은지 이해할 수 있었습니다. 모니터링하면서 following하고 스팸 뿌리기가 너무 쉽네요 --;
yes24 판매지수의 로그가 남지 않아서, 판매량의 변화를 알고 싶어서 간단하게 짰습니다.
예약작업이나 시작프로그램에 넣으시거나, crontab 등에 등록해서 돌리면 됩니다. 하루에 한번만 실행되며, 레코드가 이미 존재하는 경우에는 다시 쓰지 않습니다. sqlite3를 사용하므로, 데이터확인은 직접 콘솔로 확인하셔도 되고, db 클래스의 확인용 함수를 사용하셔도 됩니다. 저는 아래 그림과 같이 firefox용 sqlite manager를 써서 확인합니다.
소스코드는 다음과 같습니다. 수집대상을 바꾸려면 초반의 books 사전정보를 변경하시면 됩니다.
import urllib2, time, traceback from BeautifulSoup import BeautifulSoup import sqlite3
class DB: "SQLITE3 wrapper class" def __init__(self): self.conn = sqlite3.connect('bookDB') self.cursor = self.conn.cursor() for title in books.keys(): self.cursor.execute('CREATE TABLE IF NOT EXISTS %s(date text, sale int)'%title) self.cursor.execute('CREATE UNIQUE INDEX IF NOT EXISTS IDX001 ON %s(date)'%title)
def printPythonResult(self, title): self.cursor.execute('SELECT * FROM %s ORDER BY date ASC'%title) for row in self.cursor.fetchall(): print row[0],'\t', row[1]
def printPythonResult(self, title, num): self.cursor.execute('SELECT * FROM %s ORDER BY date DESC LIMIT %d'%(title,num)) for row in self.cursor.fetchall(): print row[0],'\t', row[1]
db = DB()
if __name__ == "__main__": curtime = time.localtime() curday = "%d/%02d/%02d"%(curtime[0],curtime[1],curtime[2])
for title,url in books.items(): content = getContent( url ) soup = BeautifulSoup( content )
a = soup('dt', {'class':'saleNum'}) salenum = -1 if len(a)>0: try: text = str( a[0].contents[0] ).split('|')[1] #print text splited = text.split(' ') for s in splited: if s.isdigit(): salenum = int(s) break except: traceback.print_exc()
t = os.path.getctime('/var/www/war3/info') pubdate = time.asctime( time.gmtime(t) )
body ="""<?xml version="1.0" encoding="UTF-8"?> <rss version="2.0"> <channel> <title>Frozen Throne - Kalimdor Tracer</title> <link>http://cybershin.x-y.net/tt/</link> <description>누가누가 달렸나 모니터링 시스템</description> <language>ko</language> <pubDate>%s</pubDate> <generator>dsp generator</generator>""" %pubdate footer = """ </channel> </rss>""" info = getInfo() for i in info: user, level, date = i date = conv(date) level = level.replace('l','l ') link = url_head + user body += """ <item> <title>%s</title> <link>%s</link> <description>%s, Last Ladder Game : %s</description> <author>(%s)</author> <guid>%s#%s</guid> <pubDate>%s</pubDate> </item>"""%(user, link, level, date, user, link, re.sub(' ','',date), date ) # Sat, 18 Apr 2009 00:15:00 +0900 body += footer req.write( body ) return apache.OK
5. 성공적으로 실행되면 브라우저상에서 다음과 같이 잘 출력되는 것을 볼 수 있으며, hanrss, outlook 등으로 연결해서도 잘 되는 것을 확인할 수 있습니다.
Frozen Throne - Kalimdor Tracer 누가누가 달렸나 모니터링 시스템
alpakook Level 12, Last Ladder Game : Sat, 09 May 2009 1:54 AM dspshin Level 6, Last Ladder Game : Fri, 08 May 2009 12:40 AM soudz Level 22, Last Ladder Game : Thu, 23 Apr 2009 12:58 AM milkelf Level 9, Last Ladder Game : Sun, 03 May 2009 8:20 PM sacrea Level 2, Last Ladder Game : Sun, 12 Apr 2009 8:31 PM again4you Level 1, Last Ladder Game : Tue, 05 May 2009 6:49 PM
2. 이 예제는 특정 사이트를 모니터링하며 해당 정보가 업데이트되면 RSS로 알려주는 예제입니다. 고로 Request가 올때마다 특정 사이트를 읽어서 답하면 너무 늦으므로 프로세스를 2개로 나눠서 실행합니다. 즉, 정보 수집을 맡는 Crawl.py 와 RSS결과를 반환해 주는 rss.py로 분리.
3. Crawl.py는 다음과 같습니다. crontab 등으로 하루에 몇번만 실행시키면 됩니다.
#!/usr/bin/python # -*- coding: utf-8 -*-
import urllib2, re, pickle, sys, time from BeautifulSoup import BeautifulSoup
def getInfo( user ): url = url_head + user contents = urllib2.urlopen(url).read() soup = BeautifulSoup( contents ) B = soup('b', {'class':'small'}) date = '' for b in B: if str(b).find(':')>-1: date = b.contents[0].strip().encode('ascii')