Base 6 conversion as fold?

Question
1

I have a suspicion that I can more elegantly express the function longToCube as some type of fold operation. I’m basically dividing and moding by 6, 24 times. Each time I perform the mod 6, I use that to grab a character by index out of the array cubeColors. My function accumulates these into a list by successive consing, using tail call, and finally reverses the list and calls mkString

I’d appreciate suggestions.

  type Cube = String

  val cubeColors = Array('W', 'G', 'Y', 'B', 'O', 'R')

  def cubeToLong(cube:Cube):Long = {
    // convert from string to base 6
    cube.foldLeft(0L)((acc:Long,ch:Char)=>(acc * 6 + cubeColors.indexOf(ch)))
  }

  def longToCube(n:Long):Cube = {
    def recur(residue:Long,digit:Int, acc:List[Char]):Cube = {
      if ( digit == 0)
        acc.mkString
      else {
        recur(residue / 6, digit - 1, cubeColors((residue % 6).toInt)::acc)
      }
    }
    recur(n, 24, List())
  }
3

Folds are done on collections, so you would need to create an artifical collection beforehand. Is it worth it?

In your case you can have succint code without folds:

  type Cube = String

  val cubeColors = Array('W', 'G', 'Y', 'B', 'O', 'R')

  val colorToDigit: Array[Char] = {
    Array.tabulate[Char](128) { digitAscii =>
      (cubeColors.indexOf(digitAscii.toChar) + '0').toChar
    }
  }

  val pad: String = "0" * 24

  def cubeToLong(cube: Cube): Long =
    java.lang.Long.parseLong(cube.map(color => colorToDigit(color)), 6)

  def longToCube(n: Long): Cube = {
    val digits = (pad + java.lang.Long.toString(n, 6)).takeRight(24)
    digits.map(digit => cubeColors(digit - '0'))
  }

or in more object oriented form:

  class Cube(val raw: Long) extends AnyVal {
    def toDigits: String =
      (Cube.pad + java.lang.Long.toString(raw, 6)).takeRight(24)

    def toColors: String =
      toDigits.map(digit => Cube.cubeColors(digit - '0'))

    override def toString: String =
      toColors
  }

  object Cube {
    val cubeColors = Array('W', 'G', 'Y', 'B', 'O', 'R')

    val colorToDigit: Array[Char] = {
      Array.tabulate[Char](128) { digitAscii =>
        (cubeColors.indexOf(digitAscii.toChar) + '0').toChar
      }
    }

    val pad: String = "0" * 24

    def fromColors(colors: String): Cube =
      fromDigitsBase6(colors.map(color => colorToDigit(color)))

    def fromDigitsBase6(digits: String): Cube =
      new Cube(java.lang.Long.parseLong(digits, 6))
  }
4

@tarsa, I think what you’re suggesting is that my tail recursive function implementation is not so bad. right?

5

BTW, I could implement a function similar to foldRight/foldLeft on Long so that I can treat a long like a sequence of digits of a given base? That would have the benefit of making the function cubeToLong look much more similar to is inverse function, longToCube.

6

Well, your tail recursive function definitely does the job.

If you first convert Long to series of digits (base 6) then you don’t need fold anymore - simple map suffices (like in my version).

1 Like
7

Not sure if it is more readable, but here is what I get when I try to make a fold-like function which maps across the digits of a number from right to left, in a specified base.

  def foldRightDigits[T](num:Long, digits:Int, base:Int)(initial:T,f:(T,Int)=>T):T = {
    def recur(digits:Int,acc:T,num:Long):T = {
      if (digits == 0)
        acc
      else
        recur(digits-1, f(acc, (num % base).toInt), num / base)
    }
    recur(digits, initial, num)
  }
  def cubeToLong(cube:Cube):Long = {
    // convert from string to base 6
    cube.foldLeft(0L)((acc:Long,ch:Char)=>(acc * 6 + cubeColors.indexOf(ch)))
  }

  def longToCube(n:Long):Cube = {
    foldRightDigits(n, 24, 6)(List(),(acc:List[Char],digit:Int) => cubeColors(digit)::acc).mkString
  }