태그 보관물: projecteuler

[Python] 018/067 Maximum Path Sum

밤에 잠이 안와서 시작한 문제 풀이가 어느덧 3시간이 지났다.
그래서 풀어서 기분은 좋다..^^

문제를 보고 잘못 생각해서 위에서 아래로 큰 수를 찾아가는 거로 계산을 하고 제출을 했는데 오답 표시.

문제를 다시 읽어보니 어떻게 풀어야 할지 조금 막막하다.. 구글신의 도움을 받아 다른 사람이 어떻게 풀었는지를 찾아보았다.

http://www.mathblog.dk/project-euler-18/

위의 링크에 보면 Dynamic Programming 이라는 섹션에 어떤식으로 풀어야 되는지 표시가 되어 있다.

풀이과정

[초기값]

8 5 9 3
2 4 6
7 4
3

[가공값]

  1. 8+2 와 5+2 를 비교하여 큰값을 2행 1열(2)위치에 입력
  2. 5+4 와 9+4 를 비교하여 큰값을 2행 2열(4)위치에 입력
  3. 9+6 과 3+6 을 비교하여 큰값을 2행 3열(6)위치에 입력
  4. 1~3의 스텝을 반복한다.

[소스코드]

import unittest


class TestMaximumPathSumClass(unittest.TestCase):

    def testExample(self):
        input_str = '''
                    3
                    7 4
                    2 4 6
                    8 5 9 3'''
        value = self.maximum_path_sum(input_str)
        self.assertEqual(value, 23)

    def testPE67(self):
        f = open("/Users/p/Downloads/p067_triangle.txt")
        lines = f.readlines()
        value = self.maximum_path_sum(''.join(lines))
        print(value)
        f.close()

    def testPE18(self):
        input_str = '''
                    75
                    95 64
                    17 47 82
                    18 35 87 10
                    20 04 82 47 65
                    19 01 23 75 03 34
                    88 02 77 73 07 63 67
                    99 65 04 28 06 16 70 92
                    41 41 26 56 83 40 80 70 33
                    41 48 72 33 47 32 37 16 94 29
                    53 71 44 65 25 43 91 52 97 51 14
                    70 11 33 28 77 73 17 78 39 68 17 57
                    91 71 52 38 17 14 91 43 58 50 27 29 48
                    63 66 04 68 89 53 67 30 73 16 69 87 40 31
                    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''
        value = self.maximum_path_sum(input_str)
        print("Maximum path sum = ", value)

    def maximum_path_sum(self, input_str):
        input_str = input_str.strip()
        lines = input_str.split('n')
        array = []
        for line in lines:
            if len(line) == 0:
                continue
            nums_array = line.strip().split(" ")
            array.insert(0, nums_array)

        for i in range(0, len(array) - 1):
            nums_array = array[i]
            changed_array = []
            for j in range(0, len(nums_array)-1):
                v1 = int(array[i][j]) + int(array[i+1][j])
                v2 = int(array[i][j+1]) + int(array[i+1][j])
                changed_array.append(max(v1, v2))
            array[i+1] = changed_array
            print(changed_array)

        return array[len(array)-1][0]

if __name__ == '__main__':
    suite = unittest.TestLoader().loadTestsFromTestCase(TestMaximumPathSumClass)
    unittest.TextTestRunner(verbosity=2).run(suite)

[Python] 53_combinatoric_selections

문제링크

문제풀이

  1. 조합을 구하는 함수를 정의한다
  2. 팩토리얼을 구하는 함수를 정의한다. (팩토리얼을 lambda를 이용한다)
  3. 조합의 공식에 따라 구해진 값이 1,000,000이 넘는 값을 카운팅 한다.
import unittest
import functools


class TestCombination(unittest.TestCase):

    def testCombination(self):
        value = self.combination(5, 3)
        self.assertEqual(value, 10)

        value = self.combination(23, 10)
        self.assertEqual(value, 1144066)

    def combination(self, a, b):
        v1 = self.fact(a)
        v2 = (a == b and 1 or (self.fact(b) * (self.fact(a - b))))
        return v1 / v2

    def fact(self, a):
        if a == 0:
            return 0
        fact_value = functools.reduce(lambda x, y: x * y, range(1, a + 1))
        return fact_value

    def testOverMillionCount(self):
        count = 0
        for i in range(1, 101):
            for j in range(1, i):
                combi_value = self.combination(i, j)
                if combi_value > 1000000:
                    # print("%d, %d, combi_value=%d" % (i, j, combi_value))
                    count += 1
        print("Over 1million counts = ", count)

if __name__ == '__main__':
    suite = unittest.TestLoader().loadTestsFromTestCase(TestCombination)
    unittest.TextTestRunner(verbosity=2).run(suite)

[Python] 54-Poker hands

링크

결과

답은 적지 않지만 풀면서 중복된 값을 찾고 정렬해서 스트레이트 카드인지 여부를 판별하는데 어려움이 있었던것 같다.

소스 코드는 많이 지저분 하지만 나름대로 한번에 풀이한 성과가 있는거 같다.

문제 풀이

  1. CARD 인덱싱할 수 있는 배열을 선언
  2. 승리 여부를 판별할 수 있는 배열 선언
  3. 각 카드를 승리 여부를 판별 할 수 있는 문자로 변환
  4. 플레이어 2명의 카드가 동일한 경우 두번째로 높은 카드를 판별

** collections.Counter 클래스를 이용 **

collections.Counter 클래스는 배열의 중복되는 값을 찾아 Key-Value 형태로 리턴해주기 때문에 One-Pair, Two-Pairs, Full House, Four Card 등과 같은 값을 판별하기 적합하다.

[풀이코드]

import collections
import logging

CARD_INDEX = ['A', 'T','J','Q','K']
WIN_ORDER = ['None', 'HIGH', 'ONE_PAIR', 'TWO_PAIR', 'THREE_OF_KIND'
             , 'STRAIGHT', 'FLUSH', 'FULL_HOUSE', 'FOUR_OF_A_KIND', 'S_FLUSH', 'R_FLUSH']
for i in range(2, 10):
  CARD_INDEX.insert(i-1, str(i))

logging.basicConfig(filename='D:/result.log',level=logging.DEBUG)



def flushCheck(nums):
  nums = sorted(nums)
  R_FLUSH_CARDS = [CARD_INDEX.index('A'), CARD_INDEX.index('T'), CARD_INDEX.index('J'), CARD_INDEX.index('Q'), CARD_INDEX.index('K')]
  if (len(set(nums).intersection(R_FLUSH_CARDS)) == 5):
    return 'R_FLUSH', nums

  if not isStraight(nums):
    return 'FLUSH', nums  
  return 'S_FLUSH', nums


def isStraight(nums):
  nums = sorted(nums)
  for i in range(0, len(nums)-1):    
    if (nums[i]+1 != nums[i+1]):      
      return False
  return True


def getResult(nums, suits):   

  if (len(set(suits)) == 1):
    return flushCheck(nums)

  cardCounters = collections.Counter(nums).values()  
  if 4 in cardCounters:
    return 'FOUR_OF_A_KIND', nums

  if len(cardCounters) == 2 and (3 in cardCounters) and (2 in cardCounters):
    return 'FULL_HOUSE', nums

  if isStraight(nums):
    return 'STRAIGHT', nums

  if len(cardCounters) == 3 and 3 in cardCounters:
    return 'THREE_OF_KIND', nums

  if len(cardCounters) == 3 and 2 in collections.Counter(cardCounters).values():
    return 'TWO_PAIR', nums

  if len(cardCounters) == 4 and 2 in cardCounters:
    return "ONE_PAIR", nums

  return "None", 'None'


def sperateNumSuit(s):  
  cards = s.split(" ")
  nums = []
  suits = []
  for c in cards:
    num = c[:1]
    suit = c[1:]    
    nums.append(CARD_INDEX.index(num))
    suits.append(suit)
  return nums, suits


def getHighestNum(num1, num2):
  # Ace is highest number
  while True:
    if 0 not in num1:
      break
    num1[num1.index(0)] = 14  

  while True:
    if 0 not in num2:
      break
    num2[num2.index(0)] = 14  

  collectNum1 = collections.Counter(num1)
  collectNum2 = collections.Counter(num2)

  if (len(collectNum1) == 5):
    if 0 in num1:
      return "PLAYER#1 WIN"
    elif 0 in num2:
      return "PLAYER#2 WIN"    
    return (max(num1) > max(num2)) and "PLAYER#1 WIN" or "PLAYER#2 WIN"

  for i in range(1, len(collectNum1)):
    p1Max = max(collectNum1, key=collectNum1.get)
    p2Max = max(collectNum2, key=collectNum2.get)

    if (collectNum1[p1Max] == 1 and collectNum2[p2Max] == 1):
      return max(collectNum1) > max(collectNum2) and "PLAYER#1 WIN" or "PLAYER#2 WIN"            

    if (p1Max == p2Max):
      print collectNum1, collectNum2
      del collectNum1[p1Max]
      del collectNum2[p2Max]      
      print 'DELETE %s' % CARD_INDEX[p1Max]

    else:      
      if (p1Max > p2Max):
        return "PLAYER#1 WIN"
      else: 
        return "PLAYER#2 WIN"


if __name__ == '__main__':
  f = open("C:/Users/coozplz/Downloads/p054_poker.txt")
  lines = f.readlines()  
  p1WinCount = 0
  for s in lines:      
    p1, p2 = s[:14], s[15:len(s)-1]
    logging.info("P1=%s, P2=%s" % (p1, p2))
    nums1, suits1 = sperateNumSuit(p1)    
    pr1, n1 = getResult(nums1, suits1)  
    nums2, suits2 = sperateNumSuit(p2)    
    pr2, n2 = getResult(nums2, suits2)
    if pr1 == None:
      pr1 = 'None'
    if pr2 == None:
      pr2 = 'None'

    logging.info("%s,%s / %s, %s" % (pr1, str(n1), pr2, str(n2)))
    if pr1 == pr2:      
      result = getHighestNum(nums1, nums2)
    else:
      if (WIN_ORDER.index(pr1) > WIN_ORDER.index(pr2)):
        result = "PLAYER#1 WIN"
      else:
        result = "PLAYER#2 WIN"
    if (result == "PLAYER#1 WIN"):
      p1WinCount += 1
      logging.info("Player1 Won!!")
    else:
      logging.info("Player2 Won!!")    
    logging.info( "-" * 80)
  logging.info("Total Win Count=%d" % p1WinCount)    

[Python] 5-SmallestMultiple

알고리즘은 생각하지 않고 하루에 한 문제씩 풀면서 파이썬이란 언어와 친해지려고 합니다..
혹시 보시고 잘못된 부분이나 지적하실 부분이 있으면 댓글로 남겨주세요..

[문제 링크]
http://projecteuler.net/problem=5

[문제 요약]
1에서 20으로 모두 나눠지는 가장 작은 수를 구하시오..

[풀이 리뷰]
알고보면 간단한 문젠데 이해가 안되서 고민을 좀 했습니다.
프로젝트오일러에 나온 문제들은 대부분 1분내외로 풀어야 한다고 합니다.
제가 풀려고 했던 방법은 2의 배수중 20 보다 작은 가장 큰 수, 3의 배수중 20보다 작은 가장 큰수…. + 20이하의 모든 소수로 나눠지는 수를 계산하려고 했습니다.

나름 머리를 쓴다고 쓴게 반복을 최소화해서 속도를 높여보자였는데 간단한 방법이 있었습니다.

최소공배수(Least Common Multiple)를 이용하는 방법입니다.

lcm(lcm(lcm(lcm(1,2),3),4)…., 20)
위와 같은 방법으로 하면 연산을 많이 하지 않고도 답을 구할 수 있습니다.

[소스 코드]

"""
# 5_SmallestMultipl.py
# Date: 2014. 08. 04
# Author: coozplz@gmail.com
"""
import time

sTime = time.clock()
def gcd(a,b):
   """
   최대 공약수를 구하는 함수
   :param a: 숫자 입력값 1
   :param b: 숫자 입력값 2
   :return:최대 공약수
   """
   m = max(a,b)
   n = min(a,b)
   while n != 0:
       t = m % n
       (m,n)=(n,t)
   return abs(m)


"""
# 1. 숫자 1과 숫자 2의 최소공배수를 구한다.
# 2. 1의 결과와 3의 최소공배수를 구한다.
# ....
# 이전의 결과와 20의 최소공배수를 구한다.
"""

gcdValue = 1
for j in range(1, 21):
    # 최소 공배수를 구한다
    gcdValue = int(gcdValue * j / gcd(gcdValue, j))
    i = j
print(gcdValue, "최소공배수 이용=", (time.clock() - sTime) * 100)

"""
# 단순 무식하게 반복문으로 1씩 증가하면서 모두 해본다.
"""
sTime = time.clock()
num = 1
while True:
    found = True
    for i in range(1, 21):
        if num % i != 0:
            found = False
            break
    if found:
        break
    num += 1
print(num, "반복문만 사용=", (time.clock() - sTime) * 100)

[풀이 시간]
최소공배수 이용= 0.0030000000000000512
반복문만 사용= 14033.343700000001

[Python] 22 – Name Scores

[문제 링크]
http://projecteuler.net/problem=22

[문제 요약]
“names.txt” 정렬이 안된 텍스트 파일을 읽어 모든 이름을 아래의 룰에 따라 연산한 합의 결과를 출력
COLIN 은 알파벳 순서로 정렬시 938번째에 존재한다.
C = 3
O = 15
L = 12
I = 9
N = 14
========
SUM = 53

nameScore = 938 * 53 = 49714

그렇다면 텍스트 파일에 포함된 모든 숫자의 nameScore의 합은?

[문제 풀이]
1. 파일을 읽는다.
2. 파일을 쉼표(,) 를 기준으로 split() 한다.
3. split() 된 파일을 정렬한다.
4. split() 의 결과를 반복하며 알파벳의 순서를 합산한다.

[소스코드]

"""
# 22_Names_scores.py
# Date: 2014. 08. 01
# Author: coozplz@gmail.com
# 학습내용
    1. 파일 읽기
    2. 리스트 정렬
    3. Character 를 ASCII 코드값으로 출력
"""

#이름 정보를 저장할 파일명
nameList = []

f = open("names.txt", "r")
# 파일을 읽는다.
line = f.read()

# 라인을 , 를 구분으로 자른다.
aStr = line.split(",")

for n in aStr:
    nameList.append(n)

print("Size =", len(nameList))

#이름을 정렬한다.
nameList.sort()

# 합산 점수를 저장
sumOfScores = 0

# 이름의 위치한 행의 번호
rowCount = 1


for name in nameList:
    nameCount = 0
    '''
    # 이름에 따옴표가 포함된 경우 제거
    '''
    name = name.replace("\"", "")
    for ch in name:
        '''
        # 이름을 한자씩 잘라서 ASCII 값으로 알파벳의 덧셈을 처리한다.
        # Ex) A = 1, B = 2
        '''
        nameCount += (ord(ch) - (ord('A')-1))

    sumOfScores += (nameCount * rowCount)
    rowCount += 1
print(sumOfScores)

[Python] 21 – Amicable Numbers

[문제 링크]
http://projecteuler.net/problem=21

[문제 원본]
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

[문제 풀이]

  • 반복문에서 수를 감소시키며 숫자의 약수의 합을 구한다.
  • 1에서 구해진 약수의 합의 수의 약수의 합을 구한다.
  • 2에서 구해진 값과 진행 중인 숫자가 일치하면 Amicable Number로 인식한다.단, 1에서 구해진 약수의 합과 진행 중인 숫자가 같은 경우는 제외한다.

[소스 코드]

"""
# 19_Amicable_Numbers.py
# Date: 2014. 07. 31
# Author: coozplz@gmail.com
"""
num = 10000
sumOfAmicable = 0

while(num > 0) :
    sumOfDivisor = 0
    for i in range(1, num):
        if(num % i == 0):
            # 약수의 합을 구한다.
            sumOfDivisor = sumOfDivisor + i

    sumOfDivisor2 = 0
    for i in range(1, sumOfDivisor):
        if(sumOfDivisor % i == 0):
            # 약수의 합을 구한다.
            sumOfDivisor2 = sumOfDivisor2 + i


    """
    # 약수의 합과 수가 일치하지만 두수가 동일한 경우는 제외한다.
    # 예) 28 // 28
    #      6 // 6
    """
    if(sumOfDivisor2 == num and num != sumOfDivisor) :
        print("AmicableNumber=", num, sumOfDivisor)
        sumOfAmicable = sumOfAmicable + num
    num = num - 1
print(sumOfAmicable)

[Python] 19 – Counting Sundays

문제 이해를 잘못해서 시간이 엄청 걸렸습니다.

제출을 하면 어디가 잘못되었는지가 나오지 않기 때문에 문제를 정확하게 파악해야 됩니다.

이번에 실수는 1901~2000까지 일요일의 수를 카운팅 하는건줄 알았는데 알고보니 월의 처음 시작일이 일요일인 것만 찾는 문제였습니다.

소스코드에 불필요한 부분이 많이 있더라도 파이썬에 익숙해보고자 하는 일이기 때문에 … 이해 부탁드립니다.

[문제 링크]
http://projecteuler.net/problem=19

[문제 원본]
You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

[풀이 방법]
1. 1900~1901년까지 월의 시작요일이 일요일인 개수를 구한다.
2. 1900~2000년까지 월의 시작요일이 일요일인 개수를 구한다.
3. 2의 결과에서 1의 결과를 제거한다.

위와 같이 한 이유는 문제에서 주어진 처음 시작 요일이 1900년 1월 1일 이기 때문입니다.
[소스 코드]

#
#19_Counting_Sundays.py
#
months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
days = ["MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"]

'''
#### 함수 정의 부분 ####
'''
def countingSundays(sYear, eYear):
    """ 주어진 기간 동안에 월의 시작요일이 일요일인 항목은 구한다.
    :param sYear: 시작 월
    :param eYear: 마지막 월
    :return:       월의 시작 요일이 일요일인 개수
    """

    count = 0
    sumOfDays = 0

    while(sYear <= eYear) :
        if((sYear % 4 == 0 and sYear%100 != 0) or (sYear % 400 == 0)) :
            months[1] = 29
        else :
            months[1] = 28
        for i in months :
            if(days[sumOfDays % 7] == 'SUN'):
                count = count+1
            sumOfDays = sumOfDays + i
        sYear = sYear + 1

    return count

'''
#### 메인 실행 부분 ####
'''
sumUtil1901 = countingSundays(1900, 1900)
print("Sundays fell on the first of the month until 1901 =", sumUtil1901)
print("Sundays fell on the first of the month = ", countingSundays(1900, 2000) - sumUtil1901)