What are one-line solutions?
Solving an problem from project euler can be a challenge or coding fun. The result of every problem is only one number, calculated by an algorithm. Some algorithms can be written as one expression. You get an one-liner if you can embed it in a function with only one line of code.
What is Project Euler?
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
After solving some project euler problems with python I got some one-line solutions with nice usage of list comprehensions and functional programming. These code examples are not clean code but a challenge to find more one-line solutions. This article include my first 10 solutions for project euler as one-line python function. Dont use it to cheating the project – it should be a motivation to find smart coding solutions and participate to project euler.
Project euler – Problem 1 solution
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
def task1(): return sum(filter(lambda x:x%3==0 or x%5==0, list(range(1,1000))))
The version as list comprehension look similar:
def task1(): return sum([x for x in range(1,1000) if x%3==0 or x%5==0])
I found a ruby one-liner for problem 1 on cslife.wordpress.com.
Project euler – Problem 6 solution
The sum of the squares of the first ten natural numbers is:
12 + 22 + ... + 10^2 = 385
The square of the sum of the first ten natural numbers is:
(1 + 2 + ... + 10)2 = 55^2 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is
3025 - 385 = 2640
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
def task6(): return sum(range(1,101)) ** 2 - sum([x*x for x in range(1,101)])
Project euler – Problem 8 solution
Find the greatest product of five consecutive digits in the given 1000-digit number (given as string).
def task8(n): return max([int(n[i])*int(n[i+1])*int(n[i+2])*int(n[i+3])*int(n[i+4]) for i in range(len(n)-5)])
I generated a list of all products for five consecutive digits and used
to find the greatest number in the list.
Project euler – Problem 9 solution
Pythagorean triplet is a set of three natural numbers,
a < b < c
, for which
a^2 + b^2 = c^2
3^2 + 4^2 = 9 + 16 = 25 = 5^2
There exists exactly one Pythagorean triplet for which
a + b + c = 1000
Find the product
a * b * c
def task9(): return [a*b*c for a in range(1,1000) for b in range(1,1000) for c in [1000-b-a] if a*a+b*b==c*c and a<b and b<c]
Multi-dimension loops can generated by more for-statements in a list comprehension. This can also solved by pen and paper – see the euler project forum after submit the solution. Or read the answers on stackoverflow.com with the correct mathematical solution.
Project euler – Problem 13 solution
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
def task13(listOfNumbers): return str(sum(listOfNumbers))[:10]
There is no limit of the digit-length from an integer in python – problem solved fast. If your language dont support long integer use only the first 12 digits to solve the problem. The same solution found on blog.dreamshire.com and stefanoricciardi.com in F#.
Project euler – Problem 16 solution
2^15 = 32768
and the sum of its digits is
3 + 2 + 7 + 6 + 8 = 26
What is the sum of the digits of the number
def task16(): return sum([int(x) for x in str(2**1000)])
Project euler – Problem 19 solution
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
My first solution was straight-forward:
def task19(): c = 0 for year in range(1901, 2001): for month in range(1, 13): c += datetime.datetime(year,month, 1).weekday()==6 return c
This can be converted in an one-liner, but the truly short solution look like this:
def task19(): return 100*12/7
Project euler – Problem 20 solution
Find the sum of the digits in the number 100! (=
def task20(): return sum([int(x) for x in list(str(math.factorial(100)))])
There is a small cheat – you have to include the math-module. But the stand-alone solution works too:
def task20(): return sum([int(x) for x in str(reduce(lambda a,b:a*b, range(1,101)))])
I found an one-liner on theburningmonk.com in F#.
Project euler – Problem 25 solution
What is the first term in the Fibonacci sequence to contain 1000 digits?
My first solution is the classic non-recursive solution with only three variables.
def task25(self): '''What is the first term in the Fibonacci sequence to contain 1000 digits?''' a1 = 1 a2 = 1 n = 3 while 1: a1 = a1 + a2 if len(str(a1))==1000: return n n += 1 a2 = a1 + a2 if len(str(a2))==1000: return n n += 1
Looks like clean code and performance optimized. The one-line solution have to generate the fibonacci numbers in a list and stop if the 1000-digits member of the fibonacci sequence is reached.
def task25(): return 1+len(reduce(lambda a,b:len(str(a[-1]))==1000 and a or a.append(a[-2]+a[-1]) or a,range(5000),[1,2]))
without reducing is not fine – but a one-line solution. And it’s brute-force – step back to your mathematical knowhow: Fibonacci terms converge to
, where Phi is the Golden Ratio:
– detailed description can found on geekality.net.
def task25(): return int(math.floor( (1000 - 1 + math.log10(math.sqrt(5))) / math.log10((1+math.sqrt(5))/2)))
I found an one-liner on sharp.it in F#.
Project euler – Problem 29 solution
Consider all integer combinations of
for 2 <= a <= 5 and 2 <= b =1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by
a * b
2 <= a <= 100
2 <= b <= 100
I have to generate all combinations for the
and put it into a set to eliminate the duplicates.
def task29(): res = set() for a in range(2, 101): for b in range(2, 101): res.add(a**b) return len(list(res))
I used the same trick like in problem 9. Starting an two-dimensional list-comprehension, converting all products in a python-set to remove the duplicates and counting the elements in the set.
def task29(): return len(set([a**b for a in range(2,101) for b in range(2,101)]))
If you have other one-line solution and/or in other programming languages feel free to comment or link your blogs. Next year I will post the next 10 solutions.
Happy new Year!