Project 12 — Collatz Sequence

27

ek9 collatz.ek9 < input.txt

Collatz Sequence, or, the 3n + 1 Problem
By Al Sweigart al@inventwithpython.com

The Collatz sequence is a sequence of numbers produced from a starting
number n, following three rules:

1) If n is even, the next number n is n / 2.
2) If n is odd, the next number n is n * 3 + 1.
3) If n is 1, stop. Otherwise, repeat.

It is generally thought, but so far not mathematically proven, that
every starting number eventually terminates at 1.

Enter a starting number (greater than 0) or QUIT:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

#!ek9
defines module bigbook.collatz

  defines class

    //THE input idiom of this book, copied unchanged from lib/LineInput.ek9 (the reasons are
    //there): read with next(), and every input loop also stops when ended() is true.
    LineInput
      stdin as Stdin: Stdin()
      inputEnded as Boolean: false

      next()
        <- rtn as String: stdin.next()
        if not rtn?
          inputEnded: true

      ended() as pure
        <- rtn as Boolean: Boolean(inputEnded)

      override operator ? as pure
        <- rtn as Boolean: true

    //THE INPUT AND OUTPUT: everything the player sees or types goes through here, worded by Say.
    Console
      stdout as Stdout: Stdout()
      input as LineInput: LineInput()
      say as Say: Say("en")

      Console()
        -> words as Say
        say: words

      showIntroduction()
        stdout.println(say.introduction())

      //Asks once, as the book does; unset when the entry is not a starting number.
      nextStart()
        <- rtn as BigInteger: BigInteger()
        stdout.println(say.askStart())
        if entry <- input.next()
          rtn: startingNumber(entry)

      //The terms are numbers the program works out, not words: they are printed as they are.
      showSequence()
        -> terms as List of BigInteger
        cat terms | map with asText | join with withComma > stdout

      showNotAStart()
        stdout.println(say.notAStart())

      override operator ? as pure
        <- rtn as Boolean: true

  defines function

    //THE GAME: the rules of the sequence, with no input or output.

    //BigInteger(text) is unset for QUIT and for anything else that is not a number, so one
    //test covers what the book checks with isdecimal() and its check for '0'.
    startingNumber() as pure
      -> entry as String
      <- rtn as BigInteger: BigInteger()
      if start <- BigInteger(entry.trim()) then start > BigInteger(0)
        rtn: start

    //The three rules: n / 2 when n is even, 3n + 1 when it is odd. The caller stops at 1.
    //BigInteger, because 3n + 1 can pass the 64-bit limit: an Integer then becomes UNSET
    //and the sequence would end early, where Python's integers just keep growing.
    nextTerm() as pure
      -> n as BigInteger
      <- rtn as BigInteger: BigInteger()
      two <- BigInteger(2)
      three <- BigInteger(3)
      rtn: (n rem two) == 0 <- n / two : (three * n) + BigInteger(1)

    //Each step gives 'term' a NEW BigInteger, so the terms already in the list do not change.
    collatzSequence()
      -> start as BigInteger
      <- rtn as List of BigInteger: List() of BigInteger
      finish <- BigInteger(1)
      term <- start
      rtn += term
      while term <> finish
        term: nextTerm(term)
        rtn += term

  defines function

    asText() as pure
      -> n as BigInteger
      <- rtn as String: $n

    withComma() as pure
      ->
        left as String
        right as String
      <- rtn as String: `${left}, ${right}`

    //THE language of the words, copied unchanged from lib/Language.ek9: BIGBOOK_LANG when it
    //is set (fr, zh, ...), otherwise en.
    language()
      <- rtn as String: EnvVars().get("BIGBOOK_LANG") ?: "en"

  //THE WORDS: every word the player sees.
  defines text for "en"

    Say

      introduction()
        `Collatz Sequence, or, the 3n + 1 Problem
By Al Sweigart al@inventwithpython.com

The Collatz sequence is a sequence of numbers produced from a starting
number n, following three rules:

1) If n is even, the next number n is n / 2.
2) If n is odd, the next number n is n * 3 + 1.
3) If n is 1, stop. Otherwise, repeat.

It is generally thought, but so far not mathematically proven, that
every starting number eventually terminates at 1.
`

      askStart()
        "Enter a starting number (greater than 0) or QUIT:"

      notAStart()
        "You must enter an integer greater than 0."

  defines program

    //Collatz Sequence (Big Book project 12). Reads a starting number and prints its whole 3n + 1
    //sequence, comma-separated. The game decides; the Console asks and tells, in the player's
    //words.
    Collatz()
      //A language with no words of its own is unset: ?: falls back to English.
      console <- Console(Say(language()) ?: Say("en"))

      console.showIntroduction()
      if start <- console.nextStart()
        console.showSequence(collatzSequence(start))
      else
        console.showNotAStart()