# Contest Solution: Hailstones

The Problem

In the January 1984 issue of Scientific American, an interesting sequence of numbers known as a hailstone series was described. The series is formed by generating the next number based on the number just prior to it. If the previous number was even, the next number in the series is half of it. If the previous number was odd, the next number is three times it plus one. Although the series goes up and down, it eventually settles into a steady state of 4, 2, 1, 4, 2, 1, … For example, starting at 21, the hailstone series is: 21, 64, 32, 16, 8, 4, 2, 1, 4, 2, 1, … For 21, it required five steps before the steady state was reached.

Write a program that computes how many steps will be necessary before the steady state is reached in the hailstone series beginning at a given number.

Sample Input

Your program must take its input from the ASCII text file hail.in. The file contains a sequence of one or more integer values, one per line. Sample contents of the file could appear as:

21
10


Sample Output

Your program must direct its output to the screen and must tell the number of steps required to reach the hailstone steady state for each integer recorded in the input file. Your program must format its output exactly as that shown below which is the output corresponding to the sample input above.

5 steps were necessary for 21.
4 steps were necessary for 10.


hail.py

with open('hail.in') as f:
while l:
n, a, b, i = int(l[:-1]), [], { 4, 2, 1 }, 0
while set(a) & b != b:
if i == 0:
a.append(n)
else:
a.append(a[i-1]/2 if a[i-1] % 2 == 0 else a[i-1]*3+1)
i += 1
print(i - len(b), 'steps were necessary for', str(n) + '.')


Any advice on performance enhancement and solution simplification or that is topical is appreciated!

with open('hail.in') as f:
while l:
…


… should be more idiomatically written as:

with open('hail.in') as f:
for l in f:
…


Also, the inner counting loop, with i += 1, would be more idiomatically written using for i in itertools.count(): ….

This code looks like you are code-golfing:

while l:
n, a, b, i = int(l[:-1]), [], { 4, 2, 1 }, 0


While n and i are acceptable, the other one-letter names are too cryptic. Renaming lline, aseq, and bsteady would make the code much easier to understand.

Why do you write l[:-1]? Is the -1 to strip the trailing newline? You don't need to do that: int() automatically disregards trailing whitespace.

The code for counting the steps for each n should be extracted into a separate function, since it is a deterministic function of n.

You don't need to build the list a to determine how long the sequence is.

Use the // operator for integer division. Floating-point division is wasteful.

Instead of calling print() with multiple arguments, use one of the string-formatting mechanisms in Python (e.g. str.format() or f-strings).

## Suggested solution

from itertools import count

def steps(n):
"""
Count the number of steps for the hailstone sequence starting at n to
reach a steady state of 4, 2, 1, 4, 2, 1, ...
"""
for i in count():
if n in { 4, 2, 1 }:
return i
n = n // 2 if n % 2 == 0 else 3 * n + 1

with open('hail.in') as f:
for line in f:
n = int(line)
print('{0} steps were necessary for {1}.'.format(steps(n), n))


If your hail.in input contains many lines, it would likely pay off to use memoization to avoid repeating computations.

steps_memo = {4: 0, 2: 0, 1: 0}

def steps(n):
"""
Count the number of steps for the hailstone sequence starting at n to
reach a steady state of 4, 2, 1, 4, 2, 1, ...
"""
seq = [n]
while n not in steps_memo:
n = n // 2 if n % 2 == 0 else 3 * n + 1
seq.append(n)
for i, n in enumerate(reversed(seq), steps_memo[seq[-1]]):
steps_memo[n] = i
return steps_memo[n]