Prime factors coding kata using transformations.

Inspired by Uncle Bob's Transformation Priority Premise, Glennn and I tried a Groovy kata.

  @Test
  void shouldReturnPrimeFactors(){
    assertThat getPrimeFactors(1), equalTo([])
    assertThat getPrimeFactors(2), equalTo([2])
    assertThat getPrimeFactors(3), equalTo([3])
    assertThat getPrimeFactors(4), equalTo([2,2])
    assertThat getPrimeFactors(5), equalTo([5])
    assertThat getPrimeFactors(6), equalTo([2,3])
    assertThat getPrimeFactors(7), equalTo([7])
    assertThat getPrimeFactors(8), equalTo([2,2,2])
    assertThat getPrimeFactors(9), equalTo([3,3])
    assertThat getPrimeFactors(10), equalTo([2,5])
    assertThat getPrimeFactors(11), equalTo([11])
    assertThat getPrimeFactors(12), equalTo([2,2,3])
    assertThat getPrimeFactors(13), equalTo([13])
    assertThat getPrimeFactors(14), equalTo([2,7])
    assertThat getPrimeFactors(15), equalTo([3,5])
    assertThat getPrimeFactors(16), equalTo([2,2,2,2])
    assertThat getPrimeFactors(17), equalTo([17])
    assertThat getPrimeFactors(18), equalTo([2,3,3])

    assertThat getPrimeFactors(25), equalTo([5,5])

    assertThat getPrimeFactors(64), equalTo([2,2,2,2,2,2])

    assertThat getPrimeFactors(74), equalTo([2,37])
}


We didn't record everything as we went. It would have been good to look back at our mistakes. But here's the steps I took when re-doing it later.

Step 1. "{} -> nil" transformation. Suceeds for 1, fails at 2.
  static def getPrimeFactors(int number) {
    return []
  }


Step 2. "unconditional -> if" transformation. Succeeds up to 3, fails at 4.
  static def getPrimeFactors(int number) {
    if (number == 1) return []
    return [number]
  }


Step 3. "unconditional -> if" transformation and "statement-> recursion" transformation. Fails at 9.
  static def getPrimeFactors(int number) {
    if (number == 1) return []
    if (number%2 == 0) {
      return [2]+getPrimeFactors(number.intdiv(2))
    }
    return [number]
  }


Step 4. "unconditional -> if" transformation. Fails at 25.
  static def getPrimeFactors(int number) {
    if (number == 1) return []
    if (number%2 == 0) {
      return [2]+getPrimeFactors(number.intdiv(2))
    }
    if (number%3 == 0) {
      return [3]+getPrimeFactors(number.intdiv(3))
    }
    return [number]
  }


Step 5. Refactor to remove duplication. No change to behaviour.
  static def getPrimeFactors(int number) {
    if (number == 1) return []
    for (int divisor=2; divisor<=3; divisor++) {
      if (number % divisor == 0) {
        return [divisor] + getPrimeFactors(number.intdiv(divisor))
      }
    }
    return [number]
  }


Step 6. "constant -> scalar" transformation. Success for all cases.
  static def getPrimeFactors(int number) {
    if (number == 1) return []
    for (int divisor=2; divisor*divisor<=number; divisor++) {
      if (number % divisor == 0) {
        return [divisor] + getPrimeFactors(number.intdiv(divisor))
      }
    }
    return [number]
  }

One slightly undesirable characteristic is that this method attempts to use composite divisors, although these can never succeed. Some may consider it better to construct a list of primes as potential divisors. I'll look into this another time, but I suspect that the additional work to construct the list of primes will add complexity, and not improve performance too much (unless the primes are calculated just once, and there are many calls to getPrimeFactors).