Home ›

10 one-line solutions for project euler

Christian Harms's picture
by Christian Harms on Tue, 12/28/2010 - 14:00
in

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.

  1. def task1():
  2.     return sum(filter(lambda x:x%3==0 or x%5==0, list(range(1,1000))))

The version as list comprehension look similar:

  1. def task1():
  2.     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 + ... + 102 = 385.
The square of the sum of the first ten natural numbers is: (1 + 2 + ... + 10)2 = 552 = 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.

  1. def task6():
  2.     return sum(range(1,101)) ** 2 - sum([x*x for x in range(1,101)])

I found a groovy one-liner on jared.cacurak.com and the correct O(1) solution on basildoncoder.com (as comment ) and shaunabram.com.

Project euler - Problem 8 solution

Find the greatest product of five consecutive digits in the given 1000-digit number (given as string).

  1. def task8(n):
  2.     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 max to find the greatest number in the list.

On scrollingtext.org are many comments with different solutions and on codesnippt.com is my brute-force solution.

Project euler - Problem 9 solution

Pythagorean triplet is a set of three natural numbers, a < b < c, for which a2 + b2 = c2.

For example: 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product a * b * c.

  1. def task9():
  2.     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][0]

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.

  1. def task13(listOfNumbers):
  2.     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

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

  1. def task16():
  2.     return sum([int(x) for x in str(2**1000)])

My solution in python (but commented) found at realultimateprogramming.blogspot.com or stackoverflow.com.

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:

  1. def task19():
  2.     c = 0
  3.     for year in range(1901, 2001):
  4.         for month in range(1, 13):
  5.             c += datetime.datetime(year,month, 1).weekday()==6
  6.     return c

This can be converted in an one-liner, but the truly short solution look like this:
  1. def task19():
  2.     return 100*12/7

Project euler - Problem 20 solution

Find the sum of the digits in the number 100! (=factorial(100)).

  1. def task20():
  2.     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:
  1. def task20():
  2.     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.

  1. def task25(self):
  2.     '''What is the first term in the Fibonacci sequence to contain 1000 digits?'''
  3.     a1 = 1
  4.     a2 = 1
  5.     n = 3
  6.     while 1:
  7.         a1 = a1 + a2
  8.         if len(str(a1))==1000:
  9.             return n
  10.         n += 1
  11.  
  12.         a2 = a1 + a2
  13.         if len(str(a2))==1000:
  14.             return n
  15.         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.
  1. def task25():
  2.     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]))

Using reduce 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 (n)*Phi=(n+1), where Phi is the Golden Ratio: (1+sqrt(5))/2 - detailed description can found on geekality.net.
  1. def task25():
  2.     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 a*b for 2 <= a <= 5 and 2 <= b <= 5:
22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=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 for 2 <= a <= 100 and 2 <= b <= 100?

I have to generate all combinations for the ab and put it into a set to eliminate the duplicates.

  1. def task29():
  2.         res = set()
  3.         for a in range(2, 101):
  4.             for b in range(2, 101):
  5.                 res.add(a**b)
  6.         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.

  1. def task29():
  2.     return len(set([a**b for a in range(2,101) for b in range(2,101)]))

other solutions

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!

Comments

Marcos Toledo's picture
"of 3 or 5 below 1000."
Marcos Toledo (not verified) - Wed, 12/29/2010 - 01:31

"of 3 or 5 below 1000." means 1000 exclusive, so range should be up to 999 no?
The example's 'below 10' doesn't list 10 itself as a multiple of 5

Christian Harms's picture
python range-iterator
Christian Harms - Wed, 12/29/2010 - 07:35

the python range iterator produce a sequence of integer exclusive the stop value, from python docu: "... range(i, j) returns [i, i+1, i+2, ..., j-1];". That is a little bit unconventional.

  1. range(1,10) -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

Twitter Trackbacks for 10 one-line solutions for project eu's picture
Pingback
Twitter Trackbacks for 10 one-line solutions for project eu (not verified) - Wed, 12/29/2010 - 12:55

[...] 10 one-line solutions for project euler | united-coders.com united-coders.com/christian-harms/10-one-line-solutions-for-project-euler – view page – cached 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. [...]

Mike's picture
Very clever and inventive solutions
Mike (not verified) - Fri, 12/31/2010 - 09:11

Really like what you're doing here. I am new to Python and learning some neat tricks about the language through your solutions. Thanks - keep up the great work!

Christian Harms's picture
euler project solutions
Christian Harms - Fri, 12/31/2010 - 14:23

Thanx for the comment. Like in your blog there are many project euler solutions out there - but I dont found a source for tricky one-line solutions for the project euler problems.

Iftah's picture
no need for the list in your solutions
Iftah (not verified) - Tue, 01/18/2011 - 10:19

Overall good job, nothing extr
You generate lists of items (using list comprehension, and/or using range instead of xrange) and then feed it to functions such as sum, len, set, max.

You could just pass the functions the generator (without the "[" "]") and it will work a little faster, use much less memory and the code will look better.

For example problem 1 you wrote:
sum([x for x in range(1,1000) if x%3==0 or x%5==0])

But better (IMHO) would be (note no [] brackets)
sum(x for x in xrange(1,1000) if x%3==0 or x%5==0)

jhe's picture
#1 Divisions aren't cheap
jhe (not verified) - Tue, 03/01/2011 - 12:57

  1. >>> sum(set(xrange(3,1000,3)) | set(xrange(5,1000,5)))
  2. 233168

Duh. :)

Christian's picture
Fine set functionality
Christian (not verified) - Tue, 03/01/2011 - 15:27

I have to check out all the set tricks in python - never give up learning ;-)

Salvage Trucks's picture
I'm targeting scripting
Salvage Trucks (not verified) - Thu, 06/09/2011 - 16:40

I'm targeting scripting languages with grammar similar to the English language, mainly Python and it seems that I am bit happy with their performance.