Factor Fun (Part 1) Edited

I have recently become quite active in the Factor community, and thought I should write my first blog post which includes actual Factor code . It will be very basic. I see a lot of technical blogging about Factor from the core developers, and I thought I should write a post about something fun.

After talking with Daniel Ehrenberg (littledan), I noticed how terrible the first version of the code actually is .

So I have edited this post to include the better code and merge the 2 posts into a single, coherent post.

So, I will use my basic Factor-fu to judo-chop the following puzzle:
(original text at http://www.streamtech.nl/problemset/100.html)

The Problem

Consider the following algorithm:

#1 input tn

#2 print tn

#3 if n = 1 then STOP

#4    if n is odd then n <= 3n + 1

#5    else n <= n/2

#6 GOTO #2

Given the input 22, the following sequence of numbers will be printed
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input nn. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

The SOLUTION (1st version)

SYMBOL: len

: getCycleLength ( x -- y )
    dup 1 =
    [ drop len get 1 len set ]
    [ len get 1 + len set dup even?
        [ 2 / getCycleLength ]
        [ 3 * 1 + getCycleLength ] if
    ] if ;
    
: getCycleLengths ( x y -- z )
   1 + 2dup =
   [ ]
   [ dup r> swap getCycleLength add >r
     getCycleLengths ] if ;

SYMBOL: maxLength

: getMaxCycleLength ( seq -- x )
    0 maxLength set
    [
        dup maxLength get >
        [ maxLength set ]
        [ drop ] if
    ] each
    maxLength get ;

: calculateMaxCycleLength ( x y -- z )
    1 len set swap
    V{ } clone >r
    getCycleLengths
    r>
    getMaxCycleLength ;

There are 4 steps to implementing the algorithm:

1. Push the number range to work with onto the data stack
2. For each number in the range:
3. => Calculate the cycle length of that number
4. Then find the largest cycle length number and display it.

The first thing was to calculate the sequence length of a single integer value. This is done using the getCycleLength word. getCycleLength takes the integer from the top of the stack and calculates the cycle length of the integer value. For each recursion, we increment the len variable's value by 1. At the end of the recursions, we drop the top integer value, put the cycle length for the integer on the stack and reset the len variable's value to 1.

So if I want the cycle length of the value 22, I use getCycleLength as follows:

22 getCycleLength
  => 16

getCycleLength consumes the value 22 and places the value 16 (the cycle length) onto the stack.

The next step is to get the cycle lengths for a range of integer values. This is done using the getCycleLengths word. This word iterates through the range pushed onto the stack, and for each number in the range, it calculates the cycle length for the number and then stores the cycle length in a vector which is on the retain stack. So after getCycleLengths has executed, we have a vector on the data stack containing the cycle lengths for each number in the specified range.

Now that we have a vector of all the cycle lengths for the number range, we can iterate through the sequence, and get the largest integer value in the sequence. This is done by the getMaxCycleLength word. getMaxCycleLength takes a sequence and extracts the largest integer value from it. After this word has executed, we have our answer.

The calculateMaxCycleLength word sets up the environment with the needed data structures and arranges the elements on the stack in a specific way and then calls the getMaxCycleLength which performs the actual calculation.

So that concludes the overview of the code.

In Retrospect - A Better Solution

After talking to Daniel, I have learned a whole lot of new stuff. The code above is an example of how NOT to write Factor code.

So the following code is a (much) better example of how to implement the algorithm (thanks littledan):

: find-natural* ( num quot -- integer )
    [ call ] 2keep rot
    [ drop ] [ >r 1+ r> find-natural* ] if ;

: cycle-length ( x -- length )
    1
    [ drop dup 1 = dup
      [ >r dup even? [ 2 / ] [ 3 * 1 + ] if r> ]
      unless
    ] find-natural* nip ;

USE: math.ranges

: max-cycle-length ( x y -- z )
    [a,b] [ cycle-length ] map supremum ;

This is a much better implementation. I have also learned the following:

• Factor has a good library and before you try to write something yourself, check the library to see if a similar word does not already exist.
• Don't use variables unless their use would make the code cleaner and easier to understand.
• Word names should be kept short, with hyphens (dashes) between the different words in the word-name, and word names should be all lower-case.