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])
Ludvig Learns Python is about me, Ludvig, who got interested in Python programming after being introduced to Quantopian (algorithm trading) which is built on Python programming. The scope of this blog is to document my learning process and see if it becomes more effective when I need to explain what I'm doing instead of just clicking around.
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!
Labels:
problem 67,
project euler
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])
Labels:
problem 18,
project euler
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:
Program code:
/Ludvig
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
Labels:
problem 17,
project euler
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.
A slimmer version of the same code:
/Ludvig
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
Labels:
problem 16,
project euler
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.
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.
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
So I'm also going to give try-except a shot.
Aaaaand it works!
/Ludvig
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
Labels:
problem 15,
project euler
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
Labels:
problem 14,
project euler
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
Labels:
problem 13,
project euler
Subscribe to:
Posts (Atom)