2017-06-22

Project Euler Problem 67

Since problem 67 was just a "harder" version of problem 18, I figured I'd try my problem 18 solution on it, and voila, it worked!


with open('pe67.txt', 'r') as file:
    numbers = [[int(num) for num in line.split()] for line in file]

numbersRev = reversed(numbers)


for line in numbersRev:
    for item in range(0, len(line)):
        if item < len(line) - 1:
            a = line[item]
            b = line[item + 1]
            c = max(a, b)
            numbers[numbers.index(line) - 1][item] += c

print(numbers[0][0])

2017-06-21

Project Euler Problem 18

with open('pe18.txt', 'r') as file:
    numbers = [[int(num) for num in line.split()] for line in file]

numbersRev = reversed(numbers)


for line in numbersRev:
    for item in range(0, len(line)):
        if item < len(line) - 1:
            a = line[item]
            b = line[item + 1]
            c = max(a, b)
            numbers[numbers.index(line) - 1][item] += c

print(numbers[0][0])

2017-06-19

Project Euler Problem 17

For this problem I want to use a dictionary

This problem took me way too long time to solve. All because of a mistake I made caused by naming my dictionaries too similarly. When I thought I was adding "hundred_and_text", I really was adding "hundreds_text". What made it really annoying is that I made my code output all the thousand numbers in words, which worked great. For troubleshooting I copied the output into excel and counted the letters in the cells which gave the correct answer, but when I used my code for counting, I missed ~300 letters. Next time I'm planning on doing something like this, I'm going to give dictionaries more distinguishable names.


In this program I also worked in multiple files, i.e. I had my dictionaries in a file called "dicts.py" and my main program in "main.py" (mostly because I could).

Dictionary code:

singulars_text = {  # 36    1: 'one',    2: 'two',    3: 'three',    4: 'four',    5: 'five',    6: 'six',    7: 'seven',    8: 'eight',    9: 'nine',}

ten_to_nineteen_text = {  # 70    1: 'ten',    2: 'eleven',    3: 'twelve',    4: 'thirteen',    5: 'fourteen',    6: 'fifteen',    7: 'sixteen',    8: 'seventeen',    9: 'eighteen',    10: 'nineteen'}

tens_text = {  # 46    2: 'twenty',    3: 'thirty',    4: 'forty',    5: 'fifty',    6: 'sixty',    7: 'seventy',    8: 'eighty',    9: 'ninety'}

hundreds_text = {  # 107    1: 'onehundred',  # onehundred    2: 'twohundred',  # twohundred    3: 'threehundred',  # threehundred    4: 'fourhundred',    5: 'fivehundred',    6: 'sixhundred',    7: 'sevenhundred',    8: 'eighthundred',  # eighthundred    9: 'ninehundred',  # ninehundred}

hundred_and_text = {  # 126    1: 'onehundredand',  # onehundredand    2: 'twohundredand',  # twohundredand    3: 'threehundredand',  # threehundredand    4: 'fourhundredand',  # fourhundredand    5: 'fivehundredand',    6: 'sixhundredand',    7: 'sevenhundredand',    8: 'eighthundredand',    9: 'ninehundredand',}

Program code:

import dicts


def number_counter_text():

    tot = 0
    for k, v in dicts.singulars_text.items():
        # print(dicts.singulars_text[k])        tot += len(dicts.singulars_text[k])

    for k, v in dicts.ten_to_nineteen_text.items():
        # print(dicts.ten_to_nineteen_text[k])        tot += len(dicts.ten_to_nineteen_text[k])

    for k, v in dicts.tens_text.items():
        # print(dicts.tens_text[k])        tot += len(dicts.tens_text[k])
        for a, b in dicts.singulars_text.items():
            # print(dicts.tens_text[k], end="")            # print(dicts.singulars_text[a])            tot += len(dicts.tens_text[k]) + len(dicts.singulars_text[a])

    for k, v in dicts.hundred_and_text.items():
        # print(dicts.hundreds_text[k])        tot += len(dicts.hundreds_text[k])
        for x, y in dicts.hundreds_text.items():
            # print(dicts.hundred_and_text[k], end="")            # print(dicts.singulars_text[x])            tot += len(dicts.hundred_and_text[k]) + len(dicts.singulars_text[x])
        for a, b in dicts.ten_to_nineteen_text.items():
            # print(dicts.hundred_and_text[k], end="")            # print(dicts.ten_to_nineteen_text[a])            tot += len(dicts.hundred_and_text[k]) + len(dicts.ten_to_nineteen_text[a])
        for c, d in dicts.tens_text.items():
            # print(dicts.hundred_and_text[k], end="")            # print(dicts.tens_text[c])            tot += len(dicts.hundred_and_text[k]) + len(dicts.tens_text[c])
            for e, f in dicts.singulars_text.items():
                # print(dicts.hundred_and_text[k], end="")                # print(dicts.tens_text[c], end="")                # print(dicts.singulars_text[e])                tot += len(dicts.hundred_and_text[k]) + len(dicts.tens_text[c]) + len(dicts.singulars_text[e])
    # print("onethousand")    tot += len("onethousand")

    print("----- result -----")
    print(tot)

    pass
number_counter_text()

/Ludvig

2017-06-18

Project Euler Problem 16

Easiest to far. I take the number, make it into a string, during for-loop through the characters in the string, I make them into integers and add them to tot.








number = 2 ** 1000tot = 0
for x in range(0, len(str(number))):
    digit = str(number)[x:x + 1]
    tot += int(digit)

print("tot:", tot)


A slimmer version of the same code:


tot = 0
for x in range(0, len(str(2 ** 1000))): tot += int(str(2 ** 1000)[x:x + 1])

print("tot:", tot)


/Ludvig

2017-06-17

Project Euler Problem 15

I think this problem is about combinatorics, i.e. finding out in how many ways a series of discrete values can be combined. For this problem I'm going to use factorials, mathematically expressed as "!".

2x2 has 3! combinations: 3x2x1=6
3x3 has 4! combinations: 4x3x2x1=24
4x4 has 5! combinations: 5x4x3x2x1=120

etc.

What I want to do is to write a code that calculated factorials and tells me what 21! is.


def calculate_factorial(val):
    result = 1    for x in range(1, val + 1):
        result *= x
    return result

print(calculate_factorial(21))
  
Outputs: 51090942171709440000 which is WRONG. I'm guessing that it's because this way of doing it includes duplicates of routes. Another approach is to write all routes as directions. I chose R for right and D for down. On a 2x2 grid, going from upper left corner to lower right corner, it takes four directions: RRDD. As long as these four directions are included in the route, it will make the route complete. So I want to make a program that checks all the combinations of the directions and removes all duplicates. When I google for help on these problems I try to avoid websites that addresses the very problems that I'm working on (there's a lot of help to get on Project Euler problems already).

I found a video about this type of problem and I was on the way to finding the solution, what I missed though was that I need to divide the factorial with the number of directions that I'll take (20xR and 20xD). So I get: c(40,(20,20)) which is 40!/(20!20!). Voila, I got it to work. This code works for any grid sized ROW*COLUMN.








def factorial(val):
    result = 1    for x in range(1, val + 1):
        result *= x
    return result


def routes(down, right):
    result = factorial(down + right) / (factorial(down) * factorial(right))
    return int(result)

print("Routes: ", routes(20, 20))

To make this problem a little bit more interesting I'm going to let the user input values in the console instead of having it hard coded. By the way, when googling around, I found an interesting quote:

"The classical Python mentality, though, is that it's easier to ask forgiveness than permission. In other words, don't check whether x is an integer; assume that it is and catch the exception results if it isn't:
try:
    x += 1
except TypeError:
    ..."


So I'm also going to give try-except a shot.


def factorial(val):
    result = 1
    for x in range(1, val + 1):
        result *= x
    return result


def routes(down, right):
    result = factorial(down + right) / (factorial(down) * factorial(right))
    return int(result)

rowInput = input("Rows:")
colInput = input("Columns:")
try:
    print("Routes: ", routes(int(rowInput), int(colInput)))
except:
    print("Invalid input")

Aaaaand it works!

/Ludvig

2017-06-16

Project Euler Problem 14



I first ran a code that went through all the 1M starting values, and when it was finished, it printed the chain length instead of what starting number the chain had -.-. When I modified the code to solve the problem I made it stop at that chain length instead of continuing searching.

chain = []
newChain = []
val = 0

def odd_val(val):
    odd = 3 * val + 1    return int(odd)


def even_val(val):
    even = val / 2    return int(even)


for value in range(10 ** 6, 1, -1):
    print(value, len(chain))
    while value != 1:
        if value % 2 == 0:
            value = even_val(value)
            newChain.append(value)
        else:
            value = odd_val(value)
            newChain.append(value)
    if len(newChain) > len(chain):
        chain = newChain
        print("New chain!")
    if len(chain) == 524:
        break    newChain = []

print(len(chain), val)

Hmmm now that I look through the print out there seems to be something weird in the code. I'm going to make it look nicer before heading on to the next problem.

I ran out of energy for fixing it. Hopefully I'll turn back sometime in the future.


/Ludvig

2017-06-15

Project Euler Problem 13


tot = 0
with open('pe13.txt') as file:
    lines = file.readlines()

lines = [x.strip() for x in lines]

for x in range(0, len(lines)):
    line = lines[x]
    tot += int(line)


tot = str(tot)
tot = tot[:10]
print(tot)

Above is what I first did to solve the problem. Below is how I refined my solution:

tot = 0lines = []

with open('pe13.txt') as file:
    lines = file.readlines()

lines = [x.strip() for x in lines]

lines = list(map(int, lines))

tot = str(sum(lines))
tot = tot[:10]
print(tot)

and even more:

with open('pe13.txt') as file:
    lines = file.readlines()

lines = [x.strip() for x in lines]
lines = list(map(int, lines))

print(str(sum(lines))[:10])

Quite compact if I may say so.

/Ludvig