# Happy experiments

A few stabs at solving the happy number interview question, and then optimizing it.

## setup

For the c-extended experiments, you'll first need to build and install the extension.

```bash
python setup.py build
python setup.py install
```

All are invoked `python <script name> <n>` where `n` is the max integer for happiness. For easier performance
testing, these just print out the count of happy numbers, rather than the list itself.


## The good experiments

`happy.py` is the basic python solution. It takes about 20s to compute all the happy numbers up to one million.

`c_happy.py` uses a C extension to calculate sums of squares of digits, and computes up to one million in about 3s.

`c_two_stage_happy.py` uses the observation that, up to the limit of a 32-bit long, any starting number will reduce
down to a 4-digit number equal to or less than (1459) (the sum of squared digits for 1999999999999999999). So it computes
all happiness of 1 through 1459 and caches them. Computation of happiness then reduces to finding the first 
sum of squared digits and then looking it up in the cache. This computes happy numbers up to one million in 0.2 seconds.

## An example of a long calculation
Determining the happiness of some numbers can take a large number of computations. Below the above-mentioned threshhold:
766, 121, 6, 36, 45, 41, 17, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58

Here's the general distribution:
steps happy        
1     True        1
2     True        3
3     True       21
4     True       51
5     True       49
6     True       57
7     True       32
8     False       8
9     False      73
10    False      91
11    False     226
12    False     165
13    False     203
14    False     184
15    False     122
16    False      91
17    False      53
18    False      17
19    False      12

Interestingly enough, it looks like all happy numbers converge on 1 faster than unhappy numbers repeat. 

## The first line

The above was the better line, but the first sequence of attempts I made were based around caching all computations. These
got very memory-intensive at large numbers. This wasn't a total waste, because doing these ones led me to the realization
that the number of results to cache should actually be pretty small (see comment about `c_two_stage_happy` above.)

`set_happy.py` caches all happy and unhappy results in a couple of sets. 

`sort_set_happy.py` extends the above by normalizing numbers by sorting their digits, so that combinations 
of the same digits aren't all computed.

`c_ext_happy.py` extends the above by doing the digit sorting in c. This got down to about 1.6 seconds to compute up to 
one million, and then was very hard to find a path to getting any better performance.