ProjectEuler 51-60.py

# -*- coding: utf-8 -*-
"""
Created on Fri May  7 11:48:10 2021

@author: catal
"""

import math
from itertools import count, islice


"""
problem 51
By replacing the 1st digit of the 2-digit number *3,
it turns out that six of the nine possible values:
13, 23, 43, 53, 73, and 83, are all prime

By replacing the 3rd and 4th digits of 56**3 with the same digit,
it is the first example having seven primes among the ten generated numbers,
yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993.
Consequently 56003, being the first member of this family,
is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number
(not necessarily adjacent digits)
with the same digit, is part of an eight prime value family.
"""


def isPrime(n):
    """assumes n is an integer
    returns a boolean,
    true if n is a prime number,
    false if n is not a prime number
    """
    return n > 1 and all(n % i for i in islice(count(2), int(math.sqrt(n)-1)))


def primeDigitReplacement():
    """returns an int, the smallest elements of a family of eight primes,
    generated by replacing two digits of a number
    and replacing both digits by the digits 0-9"""
    for num in range(1000, 10000000000):  # arbitrarily large end point, self terminates
        base = str(num)
        for i in range(0, len(base)-3):
            for j in range(i+1, len(base)-2):
                for k in range(j+1, len(base)-1):
                    # sub digits 0-9 for each of 3 spaces, and test for primeness
                    prime_list = []
                    for digit in range(1, 10):
                        test_base = int(base[:i] + str(digit) + base[i+1:j] + str(digit) +
                                        base[j+1:k] + str(digit) + base[k+1:])
                        if isPrime(test_base):
                            prime_list.append(test_base)
                        # test for eight prime families
                        if len(prime_list) == 8:
                            return min(prime_list)
    print("error, did not find any such set in range")


# print(primeDigitReplacement())


"""
problem 52

It can be seen that the number, 125874, and its double, 251748,
contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x,
contain the same digits.

"""


def isSameDigits(num1, num2):
    """assumes num1 and num2 are ints
    returns a boolean, True if num1 and num2are pumations of each other
    (they use all the same digits, in any order)
    else returns False
    """
    num1_list = sorted([int(x) for x in str(num1)])
    num2_list = sorted([int(x) for x in str(num2)])
    return num1_list == num2_list


# print(isSameDigits(125874, 251748))
# print(isSameDigits(125872, 251744))


def permutatedMultiples():
    """returns an int, the smallest positive integer x,
    such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in any order
    """
    for num in range(125873, 100000000000):  # arbitrarily large range, self terminates
        permutation_counter = 0
        for m in range(2, 7):
            multiple = m*num
            if not isSameDigits(num, multiple):
                break
            else:
                permutation_counter += 1
            if permutation_counter == 5:
                return(num)


# print(permutatedMultiples())


"""
problem 53

There are exactly ten ways of selecting three from five, 12345:
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, (5 3) = 10

In general, (n r) = (n!) / (r!(n-r)!)
where , r <=n, and .0!=1

It is not until n=23, that a value exceeds one-million: (23 10) = 1144066.

How many, not necessarily distinct, (n r)  values of
for 1 <= n <= 100 are greater than one-million?
"""


def calcCombinatoric(n, r):
    """assumes n is an int, r is an int <=n
    returns an int, the number of combinatorics of (n r)
    where(n r) = (n!) / (r!(n-r)!), and 0!=1
    (does NOT return the combinations)
    """
    numerator = math.factorial(n)
    denum = math.factorial(r) * math.factorial(n-r)
    return int(numerator / denum)


# print(calcCombinatoric(5,3))


def combinatoricSelection(n):
    """assumes n is an int
    returns an int, the number of (n r) combinatorics  greater than 1 million
    where (n r) = (n!) / (r!(n-r)!), r<=n, 0!=1
    """
    combinatorics_count = 0
    for n in range(1, 101):
        for r in range(1, n):
            if calcCombinatoric(n, r) > 1000000:
                combinatorics_count += 1
    return combinatorics_count


# print(combinatoricSelection(100))


"""
problem 54

In the card game poker, a hand consists of five cards and are ranked,
from lowest to highest, in the following way:

High Card: Highest value card.
One Pair: Two cards of the same value.
Two Pairs: Two different pairs.
Three of a Kind: Three cards of the same value.
Straight: All cards are consecutive values.
Flush: All cards of the same suit.
Full House: Three of a kind and a pair.
Four of a Kind: Four cards of the same value.
Straight Flush: All cards are consecutive values of same suit.
Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.
The cards are valued in the order:
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the highest value wins;
for example, a pair of eights beats a pair of fives (see example 1 below).
But if two ranks tie, for example, both players have a pair of queens,
then highest cards in each hand are compared (see example 4 below);
if the highest cards tie then the next highest cards are compared, and so on.

The file, poker.txt, contains one-thousand random hands dealt to two players.
Each line of the file contains ten cards (separated by a single space):
    the first five are Player 1's cards and the last five are Player 2's cards.
    You can assume that all hands are valid (no invalid characters or repeated cards),
    each player's hand is in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?
"""


class playingCard(object):
    def __init__(self, value, suite):
        """assumes value is a char: 2, 3, 4, 5, 6, 7, 8, 9, T(Ten),
        J(Jack), Q(Queen), K(King), A(Ace)
        assumes suite is a char: C(clubs), S(spades), H(hearts), D(diamonds)
        """
        good_suite = suite in ["C", "S", "H", "D"]
        good_value = value in ["2", "3", "4", "5", "6", "7", "8", "9", "T", "J",
                               "Q", "K", "A"]
        if good_suite and good_value:
            self.value = value
            self.suite = suite
        else:
            raise ValueError

    def __repr__(self):
        return self.value + self.suite

    def __eq__(self, other):
        return self.value == other.value and self.suite == other.suite

    def __lt__(self, other):
        ordered_values = "23456789TJQKA"
        self_index = ordered_values.find(self.value)
        other_index = ordered_values.find(other.value)
        return self_index < other_index

    def __gt__(self, other):
        ordered_values = "23456789TJQKA"
        self_index = ordered_values.find(self.value)
        other_index = ordered_values.find(other.value)
        return self_index > other_index

    def same_value(self, other):
        return self.value == other.value

    def same_suite(self, other):
        return self.suite == other.suite


# badcard1 = playingCard("22","D")
# badcard2 = playingCard("2","V")
# badcard3 = playingCard("22","O")
# acard1 = playingCard("7","D")
# acard2 = playingCard("7","D")
# acard3 = playingCard("7","H")
# acard4 = playingCard("6","D")
# acard5 = playingCard("K", "D")
# acard6 = playingCard("A", "D")
# print(acard1==acard2)
# print(acard1==acard3)
# print(acard1.same_value(acard2))
# print(acard2.same_value(acard1))
# print(acard1.same_value(acard3))
# print(acard1.same_value(acard4))
# print(acard4.same_value(acard1))
# print(acard1.same_suite(acard2))
# print(acard1.same_suite(acard3))
# print(acard1.same_suite(acard4))
# print(acard3.same_suite(acard1))
# print(acard4.same_suite(acard1))
# print(acard1)
# print(acard6 < acard5)
# print(playingCard("K", "D") > playingCard("T", "D"))
# print(playingCard("A", "D") > playingCard("Q", "D"))


class pokerHand(object):
    def __init__(self, hand_string):
        """assumes hand is a string representing a hand of poker
        of format "7D 2S 5D 3S AC"
        """
        cards = hand_string.split()
        cards.sort(key=lambda x: x)
        self.card1 = playingCard(cards[0][0], cards[0][1])
        self.card2 = playingCard(cards[1][0], cards[1][1])
        self.card3 = playingCard(cards[2][0], cards[2][1])
        self.card4 = playingCard(cards[3][0], cards[3][1])
        self.card5 = playingCard(cards[4][0], cards[4][1])
        cards_list = [self.card1, self.card2, self.card3, self.card4, self.card5]
        sort_order = ["2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K", "A"]
        self.cards_list = [card for x in sort_order for card in cards_list
                           if card.value == x]
        self.i = -1

    def __repr__(self):
        card_rep = ""
        for card in self.cards_list:
            card_rep += card.__repr__() + ", "
        return card_rep[:-2]

    def __iter__(self):
        return self

    def __next__(self):
        self.i += 1
        if self.i < len(self.cards_list):
            return self.cards_list[self.i]
        self.i = -1
        raise StopIteration

    def __eq__(self, other):
        """returns a boolean,
        True if both pokerHand objects contain the same playingCard objects in any order,
        else False
        """
        for i in range(5):
            if self.cards_list[i] != other.cards_list[i]:
                return False
        return True

    def getHandValues(self):
        """returns a list of strings, the values of the cards in the hand"""
        hand_values = []
        for card in self:
            hand_values.append(card.value)
        return hand_values

    def getHandSuites(self):
        """returns a list of strings, the suits of the cards in the hand"""
        hand_suites = []
        for card in self:
            hand_suites.append(card.suite)
        return hand_suites

    def valuesDict(self):
        """returns a dictionary, whose keys are card values,
        and whose values are a count of how many time the key appears in the hand
        """
        count = {}
        for value in self.getHandValues():
            if value not in count:
                count[value] = 1
            else:
                count[value] += 1
        return count

    def determineRank(self):
        """returns an int 1 to 10 inclusive, representing the rank of the poker hand
        10 royal flush
        9 straight flush
        8 four of a kind
        7 full house
        6 flush
        5 straight
        4 tree of a kind
        3 two pair
        2 one pair
        1 high card
        """
        hand_values = self.getHandValues()
        hand_suites = self.getHandSuites()
        hand_dict = self.valuesDict()
        if hand_values == ['A', 'J', 'K', 'Q', 'T'] and len(set(hand_suites)) == 1:
            rank = 10  # royal flush
        elif len(set(hand_suites)) == 1 and (''.join(hand_values)) in "23456789TJQK":
            rank = 9  # straight flush
        elif 4 in (hand_dict).values():
            rank = 8  # four of a kind
        elif (3 in (hand_dict).values()) and (2 in (hand_dict).values()):
            rank = 7  # Full House
        elif len(set(hand_suites)) == 1:
            rank = 6  # Flush
        elif (''.join(hand_values)) in "23456789TJQK":
            rank = 5  # Straight
        elif (3 in (hand_dict).values()):
            rank = 4  # Three of a Kind
        elif len(((hand_dict).values())) == 3:
            rank = 3  # Two Pairs
        elif len(((hand_dict).values())) == 4:
            rank = 2  # One Pair
        else:
            rank = 1  # High Card
        return rank

    def compareHighCards(self, other):
        """assumes self and other are pokerHand objects, sorted by increasing value
        returns a boolean, True if self has the highest card, else False"""
        for i in range(1, len(self.cards_list)+1):
            self_card = self.cards_list[-i]
            other_card = other.cards_list[-i]
            if self_card > other_card:
                return True
            elif self_card < other_card:
                return False
        raise RuntimeError("perfect tie")

    def compareTwoPokerHands(self, other):
        """returns a boolean,
        True if self wins the round of Texas Hold 'Em,
        else False
        """
        self_hand_dict = self.valuesDict()
        other_hand_dict = other.valuesDict()
        # determine ranks
        self_rank = self.determineRank()
        other_rank = other.determineRank()
        # compare ranks
        if self_rank > other_rank:
            return True
        elif self_rank < other_rank:
            return False
        else:  # compare values making up rank
            if self_rank == 1:
                return self.compareHighCards(other)
            elif self_rank == 2:
                self_pair_card = playingCard(max(self_hand_dict, key=lambda
                                                 key: self_hand_dict[key]), "C")
                other_pair_card = playingCard(max(other_hand_dict, key=lambda
                                                  key: other_hand_dict[key]), "C")
                if self_pair_card > other_pair_card:
                    return True
                elif self_pair_card < other_pair_card:
                    return False
                else:
                    return self.compareHighCards(other)
            elif self_rank == 3:
                self_keys = list(self_hand_dict.keys())
                self_keys.remove(min(self_hand_dict, key=lambda key: self_hand_dict[key]))
                other_keys = list(other_hand_dict.keys())
                other_keys.remove(min(other_hand_dict, key=lambda key: other_hand_dict[key]))
                self_cards = [playingCard(str(x), "C") for x in self_keys]
                other_cards = [playingCard(str(x), "C") for x in other_keys]
                if max(self_cards) > max(other_cards):
                    return True
                elif max(self_cards) < max(other_cards):
                    return False
                if min(self_cards) > min(other_cards):
                    return True
                elif min(self_cards) < min(other_cards):
                    return False
                else:
                    return self.compareHighCards(other)
            elif self_rank == 4:
                self_three_card = playingCard(max(self_hand_dict, key=lambda
                                                  key: self_hand_dict[key]), "C")
                other_three_card = playingCard(max(other_hand_dict, key=lambda
                                                   key: other_hand_dict[key]), "C")
                if self_three_card > other_three_card:
                    return True
                elif self_pair_card < other_pair_card:
                    return False
                else:
                    return self.compareHighCards(other)
            elif self_rank == 5:
                return self.compareHighCards(other)
            elif self_rank == 6:
                return self.compareHighCards(other)
            elif self_rank == 7:
                # compare three of a kind values
                self_three_card = playingCard(max(self_hand_dict, key=lambda
                                                  key: self_hand_dict[key]), "C")
                other_three_card = playingCard(max(other_hand_dict, key=lambda
                                                   key: other_hand_dict[key]), "C")
                if self_three_card > other_three_card:
                    return True
                elif self_pair_card < other_pair_card:
                    return False
                else:
                    self_pair_card = playingCard(min(self_hand_dict, key=lambda
                                                     key: self_hand_dict[key]), "C")
                    other_pair_card = playingCard(min(other_hand_dict, key=lambda
                                                      key: other_hand_dict[key]), "C")
                    if self_pair_card > other_pair_card:
                        return True
                    elif self_pair_card < other_pair_card:
                        return False
                    else:
                        return self.compareHighCards(other)
            elif self_rank == 8:
                self_four_card = playingCard(max(self_hand_dict, key=lambda
                                                 key: self_hand_dict[key]), "C")
                other_four_card = playingCard(max(other_hand_dict, key=lambda
                                                  key: other_hand_dict[key]), "C")
                if self_four_card > other_four_card:
                    return True
                elif self_pair_card < other_pair_card:
                    return False
                else:
                    return self.compareHighCards(other)
            elif self_rank == 9:
                return self.compareHighCards(other)
            elif self_rank == 10:
                raise RuntimeError("perfect tie")


# hand1 = pokerHand("7D 2S 5D 3S AC")
# hand2 = pokerHand("8C JS KC 9H 4S")
# hand3 = pokerHand("3S 7D 2S 5D AC")
# hand4 = pokerHand("5H 5C 6S 7S KD")
# hand5 = pokerHand("2C 3S 8S 8D TD")
# hand6 = pokerHand("TC JC QC KC AC") #royal flush
# hand7 = pokerHand("TC JC QC KH AC") #not royal flush due to suite, flush
# hand8 = pokerHand("2D 2C 2H 2S 6S") #four of a kind
# hand9 = pokerHand("3D 3C 3S 7H 7D") #full house
# hand10 = pokerHand("2D 3D 4D 5D 6D") #straight flush
# hand11 = pokerHand("3D 6D 7D TD QD") #flush
# hand12 = pokerHand("2D 3S 4D 5H 6D") #straight
# hand13 = pokerHand("2D 9C AS AH AC") #3 of a kind
# hand14 = pokerHand("2S 2D 7D 7C 8C") #2pairs
# hand15 = pokerHand("2S 2D 3C 8C TH") #1pair
# hand16 = pokerHand("2S 4C 6C 7H KD") #high card K
# hand17 = pokerHand("AC AH 2H 2D 8D") #two pair A 2
# hand18 = pokerHand("KC KD 4H 4D 3D") #two pair K 4
# hand19 = pokerHand("AC AH KH KD 8D") #two pair A K
# hand20 = pokerHand("AC AH AD AS 3D") #4 kind A
# hand21 = pokerHand("4C 4H 4D 4S AS") #4 kind 4

# print(hand1)
# print(hand2)
# for acard in hand1:
#     print(acard)
# print(hand1 == hand1)
# print(hand1 == hand2)
# print(hand1 == hand3)
# print(hand2 == hand1)
# print(hand3 == hand1)
# print(hand4.getHandValues())
# print(hand4.compareTwoPokerHands(hand5))
# print(set(hand6.getHandSuites()))
# print(hand6.valuesDict())
# print(hand16.determineRank())
# print(hand6.compareTwoPokerHands(hand5))

# player1hand1 = pokerHand("5H 5C 6S 7S KD")
# player2hand1 = pokerHand("2C 3S 8S 8D TD")
# player1hand2 = pokerHand("5D 8C 9S JS AC")
# player2hand2 = pokerHand("2C 5C 7D 8S QH")
# player1hand3 = pokerHand("2D 9C AS AH AC")
# player2hand3 = pokerHand("3D 6D 7D TD QD")
# player1hand4 = pokerHand("4D 6S 9H QH QC")
# player2hand4 = pokerHand("3D 6D 7H QD QS")
# player1hand5 = pokerHand("2H 2D 4C 4D 4S")
# player2hand5 = pokerHand("3C 3D 3S 9S 9D")
# hands_list= [player1hand1, player2hand1, player1hand2, player2hand2,
# player1hand3, player2hand3, player1hand4, player2hand4, player1hand5, player2hand5]
# for hand in hands_list:
    # print(hand.determineRank())
# print(player1hand1.determineRank())
# print(player1hand1.compareHighCards(player2hand1)) #false
# print(hand16.compareHighCards(hand14)) #true
# pdb.set_trace()
# print(player1hand5.compareTwoPokerHands(player2hand5))

def loadHands(file_name):
    """assumes file_name is an accessible .txt file composed of alphanumeric,
    spaces, and line breaks
    returns a list of strings, each string being a line from the input file
    """
    file = open(file_name)
    file_holder = file.readlines()
    file.close()
    return file_holder


# loadHands("p054_poker.txt")


def doesPlayer1WinPokerHand(two_poker_hands):
    """assumes two_poker_hands is a string of format "8C TS KC 9H 4S 7D 2S 5D 3S AC"
    representing two poker hands "8C TS KC 9H 4S" and " 7D 2S 5D 3S AC"
    returns a boolean, True if player 1 wins the hand, else False
    """
    player1_hand = pokerHand(two_poker_hands[:int((0.5*len(two_poker_hands)))])
    player2_hand = pokerHand(two_poker_hands[int((0.5*len(two_poker_hands))):])
    return player1_hand.compareTwoPokerHands(player2_hand)

# two_hands1 = "8C TS KC 9H 4S 7D 2S 5D 3S AC"
# two_hands2 = loadHands("p054_poker.txt")[0]
# print(doesPlayer1WinPokerHand(two_hands))
# print(doesPlayer1WinPokerHand(two_hands2))


def pokerGameWinner(file_name):
    """assumes assumes file_name is an accessible .txt file composed lines,
    each of format "8C TS KC 9H 4S 7D 2S 5D 3S AC"
    returns a boolean, True if player 1 wins the set of rounds
    else False"""
    pass
    player1_wins = 0
    poker_hands = loadHands(file_name)
    for two_hands in poker_hands:
        if doesPlayer1WinPokerHand(two_hands):
            player1_wins += 1
    return player1_wins


# print(pokerGameWinner("p054_poker.txt"))


"""
problem 55
Lychrel numbers
If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.


A number that never forms a palindrome through the reverse and add process
is called a Lychrel number.
Due to the theoretical nature of these numbers,
and for the purpose of this problem,
we shall assume that a number is Lychrel until proven otherwise.
In addition you are given that for every number below ten-thousand,
it will either (i) become a palindrome in less than fifty iterations, or,
(ii) no one, with all the computing power that exists, has managed so far to
map it to a palindrome.

In fact, 10677 is the first number to be shown to require over fifty iterations
before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers;
the first example is 4994.

How many Lychrel numbers are there below ten-thousand?
"""


def addAndReverse(num):
    """assumes num is an int
    returns an int, the sum of int and it's reverse
    e.g. for 47, 47 + 74 = 121, returns 21
    """
    reverse = int(str(num)[::-1])
    return num + reverse


# print(addAndReverse(4213))


def isPalindrome(input_string):
    """assumes input_string is a string
    returns a boolean, true if input_string is a palindrome, else false
    """
    original_string = (input_string[:])
    reversed_string = (input_string[::-1])
    return (original_string == reversed_string)


def isLychrel(num):
    """assumes num is an int
    returns a boolean, True if num is not shown to not be a Lychrel number
    in 50 iterations or less,
    else False
    """
    considered = num
    for iteration in range(50):
        considered = addAndReverse(considered)
        if isPalindrome(str(considered)):
            return False
    return True


# print(isLychrel(22))
# print(isLychrel(10677))


def countLychrelNumbers(upper_limit):
    """assumes upper_limit is an int, the number up to which to look for Lychrel numbers
    returns an int, the number of Luchrel numbers under upeer_limit
    """
    lychrel_count = 0
    for num in range(upper_limit):
        if isLychrel(num):
            lychrel_count += 1
    return lychrel_count


# print(countLychrelNumbers(10000))

"""
problem 56
powerful digit sums

A googol (10**100) is a massive number: one followed by one-hundred zeros;
100**100 is almost unimaginably large: one followed by two-hundred zeros.
Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, a**b, where a, b < 100,
what is the maximum digital sum?
"""


def powerfulDigitSumMaximizer(upper_limit):
    """assumes upper_limit is an int, the limit on a and b
    returns an int, the maximal digit sum of a**b,
    for values of a and b less than upper_limit
    e.g if a=10, b=100 --> 1
    """
    max_digit_sum = 0
    for a in range(2, upper_limit):
        for b in range(2, upper_limit):
            print(a, b)
            a_digit_sum = 0
            for digit in str(a**b):
                a_digit_sum += int(digit)
            if a_digit_sum > max_digit_sum:
                max_digit_sum = a_digit_sum
    return max_digit_sum

# print(powerfulDigitSumMaximizer(100))


"""
problem 57
Square root convergents

It is possible to show that the square root of two can be expressed as
an infinite continued fraction.

(2)**.5 = 1 +(1/(2+...))
where each iteration has form 1/(2+iter)

1st iter = 1+1/2 = 3/2 = 1.5
2nd iter = 1+ 1/(2+1/2)) = 7/5 = 1.4
3erd iter = 1 + 1/(2+(1/(2+1/2))) = 17/12 = 1.416...
4th iter = 1 + (1/(2+(1/(2+(1/(2+1/2)))))) = 41/29 = 1.41379...
5th iter = 99/70
6th iter = 239/169
7th iter = 577/408
8th iter = 1393/985

the eighth expansion ,is the first example where the number of digits in the
numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, ]
how many fractions contain a numerator with more digits than the denominator?
"""
# a_fraction = f.Fraction(1,2)
# print(f.Fraction(1,2))
# print(a_fraction)
# print(type(a_fraction))
# print(a_fraction.numerator)
# print(a_fraction.denominator)
# print(a_fraction.numerator/a_fraction.denominator)


def squareRootLargeNumFractionDigits(limit):
    """ assumes interations is an int, the number of iterations of
    the square root expansion to survey
    returns an int, the number of square root expansion fractions under iterations
    that have numerator with more digits than the denominator
    """
    big_num_count = 0
    numerator = 3
    denominator = 2
    for i in range(1, limit):
        numerator += 2*denominator
        denominator = numerator - denominator
        if len(str(numerator)) > len(str(denominator)):
            big_num_count += 1
    return big_num_count

# print(squareRootLargeNumFractionDigits(1000))


"""
problem 58
spiral primes

Starting with 1 and spiralling anticlockwise in the following way,
a square spiral with side length 7 is formed.

It is interesting to note that the odd squares lie along the bottom right diagonal,
but what is more interesting is that 8 out of the 13 numbers lying along both diagonals
are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above,
a square spiral with side length 9 will be formed.
If this process is continued, what is the side length of the square spiral
for which the ratio of primes along both diagonals first falls below 10%?
"""


def buildGrid(grid_size):
    """assumes grid_size is an odd int representing
    how many rows or columns a square the grid has
    returns a list of lists of ints, representing a square grid,
    where the external list has the same lenght as each of the internal lists,
    where the int values are filled in from the center in counterclockwise spiral
    """
    # initialize empty grid
    grid = []
    row = []
    for size in range(grid_size):
        row.append([])
        size += 1
    for size in range(grid_size):
        grid.append(row.copy())
        size += 1
    # fill grid with values
    x = grid_size//2
    y = grid_size//2
    value = 1
    step = 1
    grid[x][y] = value
    value += 1
    while step < grid_size:
        for i in range(step):
            y += 1
            grid[x][y] = value
            value += 1
        for i in range(step):
            x -= 1
            grid[x][y] = value
            value += 1
        step += 1
        for i in range(step):
            y -= 1
            grid[x][y] = value
            value += 1
        for i in range(step):
            x += 1
            grid[x][y] = value
            value += 1
        step += 1
    # fill in last row
    for i in range(step-1):
        y += 1
        grid[x][y] = value
        value += 1
    return grid

# print(buildGrid(7))


def calcGridDiagonalPrimeRations(prime_ratio):
    """assumes prime_ratio is a float, the ratio of primes:composites desired
    uses a_grid represents a square grid, it is a list of lists of ints
    where the external list has the same lenght as each of the internal lists
    returns an int, the size of the grid, filled counterclockwise,
    where the ratio of primes to composites on both diagonal of the grid falls
    bellow prime_ratio
    is extremely slow"""
    # innitialize basic grid
    grid = buildGrid(9)
    diagonal_nums = []
    j = 9-1
    for i in range(9):
        # take left diagonal
        diagonal_nums.append(grid[i][i])
        # take right diagonal
        diagonal_nums.append(grid[i][j])
        j -= 1
    # remove double counting of center tile
    diagonal_nums.remove(diagonal_nums[int(len(diagonal_nums)/2)])
    # innitialize prime ratio
    prime_count = 0
    for num in diagonal_nums:
        if isPrime(num):
            prime_count += 1
    # iterate over larger grids until diagonals fall under prime_ratio
    for grid_size in range(11, 1000000, 2):
        print(grid_size)
        new_grid = buildGrid(grid_size)
        new_diagonal_points = [new_grid[0][0],
                               new_grid[0][grid_size-1],
                               new_grid[grid_size-1][0],
                               new_grid[grid_size-1][grid_size-1]]
        for new_point in new_diagonal_points:
            if isPrime(new_point):
                prime_count += 1
        # calc prime ratio
        if prime_count/len(diagonal_nums) < prime_ratio:
            return grid_size

# calcGridDiagonalPrimeRations(0.1)


def generateCornerNumbers(prime_ratio):
    """assumes prime_ratio is a float, the ratio of primes:composites desired
    returns an int, the size of the grid, filled counterclockwise,
    where the ratio of primes to composites on both diagonal of the grid falls
    bellow prime_ratio
    """
    # initialize values for 3x3 grid
    prime_count = 3
    grid_size = 2
    corner_value = 9
    # loop increasing grid_size until fall bellow prime_ration
    while prime_count/((2*grid_size)+1) > prime_ratio:
        grid_size += 2
        # test corner values for primacy
        for i in range(4):
            corner_value += grid_size
            if isPrime(corner_value):
                prime_count += 1
    return grid_size + 1


# print(generateCornerNumbers(0.1))

"""
problem 59
XOR decryption

Each character on a computer is assigned a unique code
and the preferred standard is ASCII (American Standard Code for Information Interchange).
For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII,
then XOR each byte with a given value, taken from a secret key.
The advantage with the XOR function is that using the same encryption key
on the cipher text, restores the plain text;
for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message,
and the key is made up of random bytes.
The user would keep the encrypted message and the encryption key in different locations,
and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, 4
so the modified method is to use a password as a key.
If the password is shorter than the message, which is likely,
the key is repeated cyclically throughout the message.
The balance for this method is using a sufficiently long password key for security,
but short enough to be memorable.

the encryption key consists of three lower case characters.
 Using p059_cipher.txt (right click and 'Save Link/Target As...'),
 a file containing the encrypted ASCII codes,
 and the knowledge that the plain text must contain common English words,
 decrypt the message and find the sum of the ASCII values in the original text.
"""

# subgoals:
#     import text of p059_cipher.txt
#         # is series of CSV encoded ASCII
#     iterate over guess decryption key (three lowercase characters)
#         # if repeated not allowed = 26*25*24 = 15600
#         # if repeated allowed 26*26*26 = 17576:
#         # (not 26 choose 3 because order matters)
#         test "decrypt" the message by applying guessed key
#         convert "decrypted" message from ASCII values to plaintext
#         measure real-word character of plaintext
#         keep best decryption key and score
#     convert best decrypted message to ASCII values
#     take the sum of the ASCII values in the best decrypted text.


def loadASCIIFile(file_name):
    """assumes file_name is an accessible .txt file composed of
    ints seperated by commas
    returns a list of ints from the input file
    """
    file = open(file_name)
    file_holder = file.readlines()
    file.close()
    ASCII_list = file_holder[0].split(",")
    ASCII_list = [int(x) for x in ASCII_list]
    return ASCII_list

# print(loadASCIIFile("p059_cipher.txt"))


def load_words(file_name):
    '''
    Assumes file_name is a string: the name of the file containing
    the list of words to load
    Returns: a list of strings: lowercase valid words
    Depending on the size of the word list, this function may take a while to finish.
    '''
    # inFile: file
    inFile = open(file_name, 'r')
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.extend([word.lower() for word in line.split(' ')])
    return wordlist


def is_word(word_list, word):
    '''
    Determines if word is a valid word, ignoring capitalization and punctuation
    assumes word_list is a list of string:  words in a dictionary.
    assumes word is a string: a possible word.
    Returns: True if word is in word_list, False otherwise
    '''
    word = word.lower()
    word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")
    return word in word_list


# word_list = load_words(
#     r"C:\Users\catal\OneDrive\Desktop\Learning_to_Code\6.0001\6.0001 PS4\words.txt")
# print(is_word(word_list, "cat"))

def nextElemCyclicGenerator(a_list):
    """assumes a_list is a last
    returns the next element of a_list, cycling infinitely
    """
    while True:
        for elem in a_list:
            yield elem


# keys = nextElemCyclicGenerator(["A", "B", "C"])


def decryptASCIIValues(encrypted_ASCII_list, decryption_key):
    """assumes encrypted_ASCII_list is a list of ints representing ASCII values
    assumes decryption_key is a list of ints
    returns a list of int repressenting decrypted ASCII values
    """
    decrypted_ASCII_list = []
    # innitialize generator for decryption key parts
    keys = nextElemCyclicGenerator((decryption_key))
    # apply decryption key to all values
    for value in encrypted_ASCII_list:
        decrypted_ASCII_list.append(next(keys) - value)
    return decrypted_ASCII_list


# print(decryptASCIIValues([65], [42]))  # expected result = 107


def guessDecryptionKey3Char(encrypted_ASCII_list):
    """assumes encrypted_ASCII_list is a list of ASCII values
    encrypted with a key of 3 lowercase characters
    returns a string of lenght 3, the decryption key
    note: will take O(len(encrypted_ASCII_list)*3).
    if encrypted_ASCII_list is long, consider running on partial list
    """
    # initialize variable to track best decryption key
    best_decryption_key = []
    best_word_count = 0
    word_list = load_words(
    r"C:\Users\catal\OneDrive\Desktop\Learning_to_Code\6.0001\6.0001 PS4\words.txt")
    # guess all potential 3char keys and make generator
    # ASCIII 97-123 represents a-z
    for letter1 in range(97, 123):
        for letter2 in range(97, 123):
            for letter3 in range(97, 123):
                decryption_key_guess = [letter1, letter2, letter3]
                decryption_key_guess_generator = \
                    nextElemCyclicGenerator(decryption_key_guess)
                # decrypt ASCII and create list of " " seperated words
                decrypted_char_list = [
                    chr(x+next(decryption_key_guess_generator))
                    for x in encrypted_ASCII_list]
                decrypted_string = ''.join(decrypted_char_list)
                decrypted_string_list = decrypted_string.split("")
                # count real words in decrypted_string_list
                word_count = 0
                for elem in decrypted_string_list:
                    if is_word(word_list, elem):
                        word_count += 1
                if word_count > best_word_count:
                    best_word_count = word_count
                    best_decryption_key = decryption_key_guess
    return best_decryption_key


# guessDecryptionKey3Char([1, 2, 3, 4, 5])
# print(guessDecryptionKey3Char((loadASCIIFile("p059_cipher.txt"))))


def sumOfASCIIValues(ASCII_list):
    """assumes ASCII_list is a list of ints representing ASCII values
    returns an int, the sum of the ASCII values"""
    pass
    return sum(ASCII_list)


# encrypted_ASCII_list = loadASCIIFile("p059_cipher.txt")
# decryption_key = guessDecryptionKey3Char((loadASCIIFile("p059_cipher.txt")))
# # decryption_key = [101, 120, 112]
# decrypted_ASCII_values_list = decryptASCIIValues(encrypted_ASCII_list, decryption_key)
# decrypted_readable_list = [chr(x) for x in decrypted_ASCII_values_list]
# decrypted_readable_string = ''.join(decrypted_readable_list)
# print(sumOfASCIIValues(decrypted_ASCII_values_list))


"""
problem 60

The primes 3, 7, 109, and 673, are quite remarkable.
By taking any two primes and concatenating them in any order
the result will always be prime.
For example, taking 7 and 109, both 7109 and 1097 are prime.
The sum of these four primes, 792,
represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes
for which any two primes concatenate to produce another prime.
"""

# goal: sum of set of 5 prime nums
# where any 2 items concat to a prime
# (check all 16 combos)

# options 1: brute force, minor optimizing:
#     generate prime numbers as list
#     pick first 5 nums
#         concat each 16 combos
#         if combo fails:
#             remove both component primes as posibilities
#     test list until find 5 that fully combine
#     return sum of 5 primes


def concatNums(num1, num2):
    """assumes num1 and num2 are integers
    returns an int, the concatenation of num1 then num2
    (not num 2 then num1)
    """
    return int(str(num1)+str(num2))


def makePairs(num1, prime_lenght):
    """assumes num1 is a prime number
    assumes prime_lenght is an int, the amount of primes being considered
    returns a list of sets of ints,
    representing the primes that can be concatenated to the ith prime
    to make a new prime
    """
    pairs_set = set({})
    for num2 in range(num1+1, prime_lenght):
        if isPrime(concatNums(num1, num2)) and isPrime(concatNums(num2, num1)):
            pairs_set.add(num2)
    return pairs_set


def primePairSetOf5():
    """returns an int, the sum of a set of 5 prime numbers,
    any two of which can be concatenated in any order with each other
    to make another prime number
    """
    # initialize empty variables
    pairs_sets_list = []
    # generate list of primes
    primes_list = []
    for i in range(10000):
        if isPrime(i):
            primes_list.append(i)
            pairs_sets_list.append(None)
    prime_sum = sum(primes_list[-1:-5:-1])  # arbitrary high limit
    # iterate over all primes
    for a in range(0, len(primes_list)):
        if primes_list[a] * 5 >= prime_sum:
            break
        if pairs_sets_list[a] is None:
            pairs_sets_list[a] = makePairs(a, len(primes_list))
        for b in range(a+1, len(primes_list)):
            if ((primes_list[a] + primes_list[b]) * 4) >= prime_sum:
                break
            if pairs_sets_list[b] is None:
                pairs_sets_list[b] = makePairs(b, len(primes_list))
            for c in range(b+1, len(primes_list)):
                if (primes_list[a] + primes_list[b] + primes_list[c])*3 >= prime_sum:
                    break
                if pairs_sets_list[c] is None:
                    pairs_sets_list[c] = makePairs(c, len(primes_list))
                for d in range(c+1, len(primes_list)):
                    if (primes_list[a] + primes_list[b] + primes_list[c] + primes_list[d])*2 >= prime_sum:
                        break
                    if pairs_sets_list[d] is None:
                        pairs_sets_list[d] = makePairs(d, len(primes_list))
                    for e in range(d+1, len(primes_list)):
                        if (primes_list[a] + primes_list[b] + primes_list[c] + primes_list[d]) + primes_list[e] >= prime_sum:
                            break
                        if pairs_sets_list[e] is None:
                            pairs_sets_list[e] = makePairs(e, len(primes_list))
                        if prime_sum > primes_list[a] + primes_list[b] + primes_list[c] + primes_list[d]:
                            prime_sum = primes_list[a] + primes_list[b] + primes_list[c] + primes_list[d]
    return prime_sum


# icecream.ic(primePairSetOf5())