# Fun with Factorions

Also known as Project Euler problem 34:

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

According to Wikipedia, A factorion is a natural number that equals the sum of the factorials of its decimal digits. So now we know what we are looking at. Wikipedia also tells us how many decimal factorians exists, but I wrote some code anyway.

The first part of this is to determine whether a given number is a factorian:

```import math

def is_factorion(integer):
""" Returns True if integer is a factorion, else False
See problem 34 for a more detailed explanation """
digit_sum = 0
for n in str(integer):
digit_sum += math.factorial(int(n))
if digit_sum == integer:
return True
else:
return False```

And then for the reason I found myself googling this: What is the range of numbers I need to check?

It turns out that:

If n is a natural number of d digits that is a factorion, then 10d − 1 ≤ n ≤ 9!d. This fails to hold for d ≥ 8 thus n has at most 7 digits, and the first upper bound is 9,999,999. But the maximum sum of factorials of digits for a 7 digit number is 9!7 = 2,540,160 establishing the second upper bound.

Problem 34 tells us to ignore 1 and 2 so the solution can be derived by simply summing each number between 3 and 2540160 for which is_factorion is True.

# Find the sum of all numbers that can be written as pandigital products.

Also known as Project Euler problem 32. Yes, I am still slowly working my way through these and – in this case – I am quite pleased with myself for having a solution, not least because I had to read the problem twice before I actually understood it.

The problem is this:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

That hint turns out to be useful.

My first thought was that I need a function to identify whether a number is pandigital. This turned out to be easier than I thought and I quickly came up with this:

```def is_pandigital(integer):
""" Returns True if ingeger is pandigital, else false
A pandigital integer of length n is one that contains all
digits from 1 to n exactly once
integer is (obviously) an integer """
text = list(str(integer))
text.sort()
for n in range (0, len(text)):
if str(n + 1) != text[n]:
return False
return True```

Now that I can test for pandigitality (is that a word?) I need to figure out what numbers to test. It was at this point that I realised that I already had a `list_divisors` function, written to solve an earlier problem. Handy, and a bit of trial and error established that I only need to check for four digit products if I want the product and its divisors to total 9 digits in length.

So…

```from euler import is_pandigital, list_divisors

products = []

for n in range(1111, 9999):
divisors = list_divisors(n)
for m1 in divisors:
m2 = n / m1
as_text = str(n) + str(m1) + str(m2)
if len(as_text) == 9:
if is_pandigital(int(as_text)) == True:
products.append(n)
break

print reduce(lambda x, y: x+y, products)```

The hint helps because once I have established that a product and its divisors amount to a pandigital number, I can stop checking (hence the break).

This is probably not the fastest solution available, but it works and it’s very easy to understand.

# Extreme Waiting

Following on from yesterday’s XKCD inspired post, I have now knocked together an extreme waiting application in Python.

You can find the source for XKComplete on GitHub. It’s pretty basic, but it works well enough to provide dates (or years) right back to the beginning of the universe.

# Looptastic

While playing around with Dicetastic earlier this week, I started to feel the need to optionally loop the program so that I didn’t have to repeatedly re-execute the command. This is now implemented and the latest and greatest version has been committed to GitHub.

The changes are documented on the Dicetastic page but the shorter version is that if you start Dicetastic with a `-l` or `--loop`, it will loop until you attempt to roll 0d0.

As part of this, I have added two methods to the Dicelib library, `get_sides` and `get_count`. They are documented, but their usage should be obvious.

# Cleaning up some code

It was in the middle of last year that I implemented what I rather ambitiously referred to as a wallpaper switcher for Gnome 2. What Macsen’s Transitioning Background does is generate an XML file based on the images in a selected folder and then let the Gnome background switcher handle the rest.

With the switch to Gnome 3 this functionality is no longer supported. At least, not as far as I can tell.

I do still like the idea of using an XML file to control the background and have been toying with the idea of knocking together myself. As a first step towards this, I have tidied up some of the code.

The latest version of the source can be found on GitHub. The generated XML can be used to power a transitioning background in Gnome 2 and – if I ever find the time – I will start knocking together something that will work under Gnome 3.

# Dicetastic: Now with convention conforming goodness

I mentioned yesterday that I had been playing around with Pylint and slowly cleaning up my existing code. The first result of this can now be seen online – I have just just committed the cleaned up code for Dicetastic to my GitHub repository.

# Pylint: My new favourite static code analyser for Python

I spent most of yesterday evening playing around with Pylint, a static analysis tool that reads your source code and looks for common mistakes. I found a lot.

You can find Pylint in the Sabayon repositories, so it can be installed with a simple `equo install pylint` and then you’re off.

Running Pylint over a random module, the first thing that surprised me was just how much information the application provides. The first thing it gives you is a line-by-line list of issues – this tells you exactly what problems your code has, and where these problems are. In my case, the vast majority of these were Convention and Warning types, indicating that I really do need to clean up my Python coding style.

It then provides a number of reports which gives you a stack of metrics by which to measure the quality of your code. These were interesting, but would probably be more useful if I was running Pylint over a larger source file.

The approach I found most useful was to go through the list of issues and, for the obvious ones, just fix them. For less obvious issues, I found myself going to the Python documentation to understand why the issue had been raised and what was wrong with my existing approach.

There is a lot of documentation available for Pylint and a goodly set of configuration options. I have looked at neither so far because the reports that it generates are so self-explanatory that it is very easy to jump right in.

This is a tool I can see myself using for a long time to come and, as codebases grow, this is a tool that will become increasingly useful.

# Dicetastic: Now with added documenation

Just a quick note to confirm that a Dicetastic project page has now been added to this site.

I do, at some point, want to put a graphical front end on this but I tend to find GUI programming annoyingly fiddly so I won’t make any promises as to when this might appear.

# Dicetastic: A dice-rolling library with a simple command-line interface

When I started trying to teach myself to program in Python, one of the first applications I wrote (apart from the online and printed exercises I could find) was a simple dice rolling application. For a selected number of dice, it would calculate the rolls and return them as a list.

As time went on I tinkered with this a bit more, separating the guts of the application from the (admittedly simple) terminal interface. I have now cleaned this up a bit and put it on GitHub. Dicetastic consists of a library and a simple program that uses the library.

I’m not convinced that anyone will actually find this useful, but I do know that it isn’t doing anything just sitting on my hard drive.

I will put together a project page on this site for the application (probably tomorrow) but, for now, the code is up and you are welcome to take a look.

# Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Also known as: Project Euler problem 15

Also known as: A week to understand, a minute to implement.

The problem:

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

To start with the simple observation first: Any route through an m x m grid can be expressed as a sequence of Rs and Ds where R is right and D is down (the without backtracking condition ensures that you can’t go left or up – this simplifies things somewhat).

The second observation is that each route must be exactly 2m steps long (m steps to the right and m steps down).

So the problem that needs to be solved is: How many ways can you combine m Rs and m Ds?

It turns out that this is a combination problem which Wikipedia handily defines as a way of selecting several things out of a larger group, where order does not matter. The larger group, in this case, is all 2m steps and the several things you want to select are the k possible combinations of R (or D). The Ds (or Rs) don’t matter because you know that they have to populate the m remaining slots in the path.

A k-combination of a set S is a subset of k distinct elements of S. If the set has n elements the number of k-combinations can be expressed as `n! / k!(n - k)!` as long as k<=n.

Implementing this was a doddle and, for bonus points, my solution should work for any rectangular grid.