Return to homepage.

JUNTO Club Page


Python Practice - Project Euler Problem 23

Problem Statement

Solution - John
import math

abundant = set()

for n in range(1, 28_123):
    sqrt_n = math.sqrt(n)
    
    divisor_sum = 1
    for m in range(2, int(sqrt_n) + 1):
        if n % m == 0:
            divisor_sum += m + (n / m)
    
    if sqrt_n.is_integer():
        divisor_sum -= sqrt_n
    
    if divisor_sum > n:
        abundant.add(n)

nonabundant_sum = 0
for i in range(1, 28_123):
    sum_of_abundants = False
    
    for k in sorted(abundant):
        if k > i / 2:
            break

        if i - k in abundant:
            sum_of_abundants = True
            break

    if not sum_of_abundants:
        nonabundant_sum += i

print(nonabundant_sum)
Solution - Oscar
Not Submitted
Solution - Daniel
Not Submitted

Python Practice - Solutions

2019-02-18

Project Euler Problem 102

Solution - Daniel
"""Project Euler 102"""

_author_ = "Daniel Bassett"

import math

total = 0

for i, line in enumerate(open("p102_triangles.txt", "r")):
    xa, ya, xb, yb, xc, yc = map(int, line.split(","))
    point_a = xa * yb - ya * xb > 0
    point_b = xb * yc - yb * xc > 0
    point_c = xc * ya - yc * xa > 0

    total += point_a == point_b == point_c

print(total)
Solution - John
"""Project Euler 102"""

__author__ = "John Lekberg"

count = 0

with open("p102_triangles.txt", "r") as triangle_file:
    for line in triangle_file:
        x1, y1, x2, y2, x3, y3 = map(int, line.split(","))
        whole_area = abs(
            (x1 - x3) * (y2 - y1) - (x1 - x2) * (y3 - y1)
        )
        fragment_area = (
            abs(x1 * y2 - x2 * y1)
            + abs(x1 * y3 - x3 * y1)
            + abs(x2 * y3 - x3 * y2)
        )
        if whole_area == fragment_area:
            count += 1

print(count)
Solution - Oscar
import numpy as np


def has_origin(coord_arr):
    v1 = coord_arr[:2]
    v2 = coord_arr[2:4]
    v3 = coord_arr[4:]

    try:
        alpha = (
            ((v2[1] - v3[1]) * (0 - v3[0]))
            + ((v3[0] - v2[0]) * (0 - v3[1]))
        ) / (
            ((v2[1] - v3[1]) * (v1[0] - v3[0]))
            + ((v3[0] - v2[0]) * (v1[1] - v3[1]))
        )

        beta = (
            ((v3[1] - v1[1]) * (0 - v3[0]))
            + ((v1[0] - v3[0]) * (0 - v3[1]))
        ) / (
            ((v2[1] - v3[1]) * (v1[0] - v3[0]))
            + ((v3[0] - v2[0]) * (v1[1] - v3[1]))
        )

        gamma = 1 - alpha - beta

    except ZeroDivisionError:
        return print("Not a triangle")

    return (
        False
        if True
        in [not (0 <= i <= 1) for i in [alpha, beta, gamma]]
        else True
    )


triangles = np.loadtxt(
    "p102_triangles.txt", dtype=np.int32, delimiter=","
)
origin_triangles = 0

for i in range(1000):
    if has_origin(triangles[i]):
        origin_triangles += 1
print(origin_triangles)
2019-01-21

Project Euler Problem 99

Solution - Daniel
#!/usr/bin/env python

"""Find greatest base-exponent pair (Euler Problem 99)."""

_author_ = "Daniel Bassett"

import math
from math import log10

"""Sought guidance. See https://zach.se/project-euler-solutions/99/"""

greatest = [0, 0]

for i, line in enumerate(open("p099_base_exp.txt", "r")):
    y, x = list(map(int, line.split(",")))
    if x * log10(y) > greatest[0]:
        greatest = [x * log10(y), i + 1]
print(greatest[1])
Solution - John
#!/usr/bin/env python3

"""Solution to Project Euler Problem 99."""

import numpy as np

__author__ = "John Lekberg"

with open("p099_base_exp.txt", "r") as infile:
    pairs = np.loadtxt(infile, delimiter=",")
    log_values = np.log(pairs[:, 0]) * pairs[:, 1]
    print(1 + np.argmax(log_values))
Solution - Oscar
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jan  3 11:33:37 2019

@author: oscarmartinez
"""

# %% General implementation
import numpy as np

arr = np.loadtxt(
    "p099_base_exp.txt", dtype=np.float64, delimiter=","
)
print(np.argmax(np.log2(arr[:, 0]) * arr[:, 1]) + 1)
2019-01-02

Project Euler Problem 35

Solution - John
#!/usr/bin/env python3

"""Solution to Project Euler Problem 35 - Circular Primes."""

import numpy
import collections
import typing

__author__ = "John Lekberg"


def circular_primes_under(n: int) -> int:
    primes = primes_up_to(1_000_000)
    count = 0
    prime_set = set(primes)
    for p in prime_set:
        if all(r in prime_set for r in rotations(str(p))):
            count += 1
    return count


def rotations(s):
    for i in range(len(s)):
        yield int(s[i:] + s[:i])


def primes_up_to(n: int):
    """Primes for 2 up to n.
    See primesfrom2to at https://stackoverflow.com/questions/2068372.
    """
    assert n >= 6
    sieve = numpy.ones(n // 3 + (n % 6 == 2), dtype=numpy.bool)
    for i in range(1, int(n ** 0.5) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3 :: 2 * k] = False
            sieve[k * (k - 2 * (i & 1) + 4) // 3 :: 2 * k] = False
    return numpy.r_[
        2, 3, ((3 * numpy.nonzero(sieve)[0][1:] + 1) | 1)
    ]


print(circular_primes_under(1_000_000))
Solution - Oscar
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Dec 25 23:17:02 2018

@author: oscarmartinez
"""

import math as m


def hasDigit1(n):
    while n > 0:
        if n % 10 in {2, 4, 6, 8, 5, 0}:
            return False
            break
        n = n // 10
    return True


def sievePrime(maxN):
    primes = [True for i in range(maxN + 1)]
    p = 2
    while p * p <= maxN:
        if primes[p] == True:
            for i in range(p * 2, maxN + 1, p):
                primes[i] = False
        p += 1

    return {
        j for j in range(3, maxN, 2) if primes[j] and hasDigit1(j)
    }


def rot(n, base):
    l_b = 10 ** base
    return 10 * (n % (l_b)) + (n // l_b)


def getRots(n):
    base = m.floor(m.log10(n))
    rot_lst = []
    rot_lst.append(n)
    for _ in range(base):
        rot_lst.append(rot(rot_lst[len(rot_lst) - 1], base))
    return rot_lst[1:]


def CircularPrimes(n):
    c = False
    cnt = 0
    prime_set = sievePrime(n)
    prime_set.add(2)
    seen_set = set()
    for pr in prime_set:
        if pr in seen_set:
            continue
        seen_set.add(pr)
        rots = getRots(pr)
        for rp in rots:
            seen_set.add(rp)

            if not rp in prime_set:
                c = True
        if not c:
            cnt += len(rots) + 1
        else:
            c = False

    print(cnt)


CircularPrimes(1000000)
2018-12-19

Project Euler Problem 48

Solution - John
#!/usr/bin/env python3

"""pe48.py: Solution to project Euler Problem 48."""

__author__ = "John Lekberg"


def last_n_digits(x: int, n: int):
    """The last 'n' digits of 'x'."""
    assert x >= 0
    assert n >= 1
    return x % 10 ** n


result = sum(i ** i for i in range(1, 1001))

print(last_n_digits(result, n=10))
Solution - Oscar
import itertools as it
import cProfile as cp


def EU48():
    print(str(sum(i ** i for i in range(1, 1001)))[-10:])


cp.run("EU48")
2018-11-28

Project Euler Problem 44

Solution - John
import itertools


class Pentagonal:
    def __init__(self):
        self._generator = (
            n * (3 * n - 1) // 2 for n in itertools.count(1)
        )
        self._max = None
        self._seen = set()
        self._seen_ordered = list()

    def check_pentagonal(self, n):
        while self._max is None or self._max < n:
            item = next(self._generator)
            self._max = item
            self._seen.add(item)
            self._seen_ordered.append(item)

        return n in self._seen

    def get_pentagonal(self, n):
        while len(self._seen_ordered) < n:
            item = next(self._generator)
            self._max = item
            self._seen.add(item)
            self._seen_ordered.append(item)

        return self._seen_ordered[n - 1]


def candidate_indices():
    for i in itertools.count(1):
        for j in range(1, i):
            yield (i, j)


db = Pentagonal()

for (i, j) in candidate_indices():
    p_i = db.get_pentagonal(i)
    p_j = db.get_pentagonal(j)

    sum_pentagonal = db.check_pentagonal(p_i + p_j)
    diff_pentagonal = db.check_pentagonal(abs(p_i - p_j))

    if sum_pentagonal and diff_pentagonal:
        print(f"The answer is {abs(p_i - p_j)}")
        break
Solution - Oscar
#!/usr/bin/env python3

import itertools as it


class Pents:
    def __init__(self):
        self.new_set()

    def new_set(self):
        self.pset = self.gen_pents()

    def gen_pents(self):
        return map(self.pent, it.count(start=1))

    def pent(self, integer):
        return int((integer * (3 * integer - 1)) / 2)

    def is_pent(self, integer):
        self.new_set()
        for p in self.pset:
            if p > integer:
                return False
            elif p == integer:
                return True


def min_d():
    p_i = Pents()
    trail_p = []
    for i in p_i.pset:
        trail_p.append(i)
        # print(i)
        if len(trail_p) > 1:
            for j in range(len(trail_p) - 2, -1, -1):
                if (
                    (i - trail_p[j]) in trail_p
                ) and Pents().is_pent(i + trail_p[j]):
                    # print('Got it')
                    return (abs(i - trail_p[j]), i, trail_p[j])


d, _, _ = min_d()
print(d)
2018-11-08

Project Euler Problem 25

Solution - John
import math

from decimal import Decimal


def way1():
    def fibonacci():
        a, b = 1, 1
        while True:
            yield a
            a, b = b, a + b

    threshold = 10 ** (1000 - 1)

    fib_above = (
        (i, n)
        for i, n in enumerate(fibonacci(), start=1)
        if n >= threshold
    )

    i, _ = next(fib_above)

    return i


def way2():
    phi = (1 + Decimal(5).sqrt()) / 2

    # Binet’s Formula
    estimate = (999 + Decimal(5).sqrt().log10()) / phi.log10()

    return math.ceil(estimate)


print(way1())
print(way2())
Solution - Oscar
# This code runs into the maxiumum recursion depth and so cannot reliably be used.

import sys

sys.setrecursionlimit(5000)


def fib(n_prime=1):
    n_prime += n_prime
    if len(str(n_prime)) <= 1000:
        return fib(n_prime)
    else:
        return n_prime


print(fib())

# %%

# This yields the answer

ind = 0
i = 1
while len(str(i)) < 1000:
    i += i
    ind += 1
len(str(i))
print(f"The index of the fibonacci number {i} is {ind}.")
2018-10-16

Project Euler Problem 11

Solution - John
import itertools

import numpy as np

grid_str = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
"""

grid = np.fromiter(grid_str.split(), dtype=np.uint64)
grid.shape = 20, 20


def candidates():
    global grid

    for (r, c) in itertools.product(range(20), repeat=2):
        can_vertical = r <= 16
        can_horizontal = c <= 16

        if can_horizontal:
            yield grid[r, c : c + 4]

        if can_vertical:
            yield grid[r : r + 4, c]

        if can_horizontal and can_vertical:
            sub_grid = grid[r : r + 4, c : c + 4]
            yield np.diagonal(sub_grid)
            yield np.diagonal(np.fliplr(sub_grid))


solution = max(np.prod(c) for c in candidates())

print(solution)
Solution - Oscar
import numpy as np

with open("p11.txt") as gridfl:
    grid = gridfl.readlines()

for i, row in enumerate(grid):
    grid[i] = row.replace("\n", "").split(" ")


def best_quad():
    temp_max = 0
    max_val = 0
    for index in range(0, 17):
        temp_max = (
            g_arr[0:20, index : (index + 4)].prod(axis=1).max()
        )
        if max_val < temp_max:
            max_val = temp_max
        temp_max = (
            g_arr[index : (index + 4), 0:20].prod(axis=0).max()
        )
        if max_val < temp_max:
            max_val = temp_max
    rdiag = 1
    for row in range(0, 17):
        for column in range(0, 17):
            if max_val < rdiag:
                max_val = rdiag
            rdiag = 1
            for shift in range(0, 4):
                rdiag *= g_arr[row + shift, column + shift]
    ldiag = 1
    for row in range(19, 2, -1):
        for column in range(0, 17):
            if max_val < ldiag:
                max_val = ldiag
            ldiag = 1
            for shift in range(0, 4):
                ldiag *= g_arr[row - shift, column + shift]

    return max_val


print(best_quad())
2018-10-01

Project Euler Problem 4

Solution - John
import itertools

palindrome = lambda n: str(n) == str(n)[::-1]

three_digit_num = range(100, 1000)

squares = (n ** 2 for n in three_digit_num)

products = (
    n * m for n, m in itertools.combinations(three_digit_num, 2)
)

max_palindrome = max(
    p for p in itertools.chain(squares, products) if palindrome(p)
)

print(max_palindrome)
Solution - Oscar
def euler4():
    sMaxPalin = 0
    iFactor = 999

    def isPalin(iNumber):
        return "".join(reversed(str(iNumber))) == str(iNumber)

    while iFactor > 99:
        for i in range(999, 99, -1):
            iTempMult = iFactor * i
            if isPalin(iTempMult) and iTempMult > sMaxPalin:
                sMaxPalin = iTempMult

        iFactor -= 1

    return sMaxPalin


import cProfile

cProfile.run("euler4()")
2018-09-18

Project Euler Problem 1

Solution - Daniel
sum({*range(3, 1000, 3)} | {*range(5, 1000, 5)})
Solution - John
sum(i for i in range(1000) if not (i % 5 and i % 3))
Solution - Oscar
# -*- coding: utf-8 -*-
"""
Created on Thu Sep  6 12:16:50 2018

@author: omartinez
"""

#%% JUNTO Practice Problem 3
# We want to find the sum of the multiples of 3 or 5 in a range, [1,N)
# In this case N is 1000, range is [1,1000)

# We opt to store the values in an array and then sum them,
# in case we wanted to list the numbers
# Start with empty array
arr_multiples = []

# Loop through [1,1000)
# Check if remainder is 0, the number is a multiple and we store it
for i in range(1, 1000):
    if i % 3 == 0 or i % 5 == 0:
        arr_multiples.append(i)

arr_multiples
sum(arr_multiples)
2018-09-04

Rosalind, Complementing a Strand of DNA

Solution - John
#!/usr/bin/env python3
#
# Read a string of DNA from standard input and output
# its reverse complement on standard output.
#

import sys

# Guanine, Adenine, Cytosine, Thymine.
#
bases = {"G", "A", "T", "C"}

# Complements of above bases.
#
complement_table = {"G": "C", "A": "T", "T": "A", "C": "G"}

# Function that applies `complement_table` to complement a base.
# Ex. complement('G') == 'C'
#
complement = complement_table.get

# Read string of characters from standard input and only keep characters
# corresponding to one of the bases.
#
dna_string = list(filter(lambda c: c in bases, sys.stdin.read()))

# Reverse and then complement `dna_string`.
#
rc_string = map(complement, reversed(dna_string))

# Print the result to standard output as a string.
#
print("".join(rc_string))
Solution - Oscar
def reverse_complement(s):
    original = "ATCG"
    complement = "TAGC"
    nucl_compl = "".maketrans(original, complement)
    return "".join(reversed(s)).translate(nucl_compl)


print(reverse_complement(reverse_complement("ATCGATTCAAATTT")))
2018-08-20

Project Euler Problem 22

Solution - John
#!/usr/bin/env python3

with open("names.txt", "r") as namefile:
    content = namefile.read().replace('"', "")
    names = sorted(content.split(","))
    total = 0

    for i, name in enumerate(names, start=1):
        alpha_val = sum(
            map(lambda c: 1 + ord(c) - ord("A"), name)
        )
        total += i * alpha_val

    print(total)
Solution - Oscar
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 18:50:36 2018

@author: oscarmartinez
"""

#%%

"""Set Working Directory, change to your needs."""

import os

os.getcwd()
os.chdir("/Users/oscarmartinez/Master Files/JUNTO")

#%%

"""Read off the names, remove the quotation marks and split on commas"""
"""Sort the list in place as specified by problem"""

strNamesList = open("p022_names.txt").read().replace('"', "")
lstNames = strNamesList.split(sep=",")
lstNames.sort()

#%%

"""create Dict to map strings"""
"""NOTE: could use method .maketrans() and then str.translate() instead
in order to create a way to map name scores"""

import string

dictCharScore = {}
for i, char in enumerate(string.ascii_uppercase):
    dictCharScore[char] = i + 1

#%%

"""manual sum over the list, could also use a list of numbers and then
sum over the list"""

fltTotalScore = 0.0
for row, name in enumerate(lstNames):
    iBaseScore = 0
    for char in name:
        iBaseScore += dictCharScore[char]

    iScore = iBaseScore * (row + 1)
    fltTotalScore += iScore

print(fltTotalScore)

Meeting Attendance


Marketwatch Games

Game From To Winners Notes
JUNTO 5 2019-03-08 2019-03-19 John Only shorting allowed.
JUNTO 4 2019-02-19 2019-03-04 John No constraints.
JUNTO 3 2019-02-05 2019-02-18 John No constraints.
JUNTO 2 2019-01-23 2019-02-04 Daniel No constraints.
JUNTO 2018-08-29 2019-01-01 Daniel No constraints.