Last active
February 18, 2016 04:17
-
-
Save bdkent/f23818fd97a3ff599df0 to your computer and use it in GitHub Desktop.
base -2 converter
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import scala.collection.mutable.ListBuffer | |
| import scala.annotation.tailrec | |
| object Converter { | |
| type Base = Int | |
| type Bit = Boolean | |
| def toBit(i: Int): Bit = { | |
| i match { | |
| case 0 => false | |
| case _ => true | |
| } | |
| } | |
| def fromBit(bit: Bit): Int = { | |
| bit match { | |
| case true => 1 | |
| case false => 0 | |
| } | |
| } | |
| def toBinary(value: BigInt, base: Base): Seq[Bit] = { | |
| @tailrec | |
| def calc(v: BigDecimal, buffer: ListBuffer[Bit]): ListBuffer[Bit] = { | |
| if (v == 0) { | |
| buffer | |
| } else { | |
| val remainder = v % base | |
| buffer += toBit(remainder.abs.toInt) | |
| val next = (v / base).setScale(0, BigDecimal.RoundingMode.CEILING) | |
| calc(next, buffer) | |
| } | |
| } | |
| calc(BigDecimal(value), new ListBuffer[Bit]()) | |
| } | |
| private val Zero = BigInt(0) | |
| def toInt(bits: Seq[Bit], base: Base): BigInt = { | |
| bits.zipWithIndex.foldLeft(Zero)({ | |
| case (sum, (bit, index)) => | |
| sum + (BigInt(base).pow(index) * fromBit(bit)) | |
| }) | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| object Solution { | |
| def solution(A: Array[Int]): Array[Int] = { | |
| val base = -2 | |
| val bits = A.map(Converter.toBit).toArray | |
| val num = Converter.toInt(bits, base) | |
| Converter.toBinary(-num, base).map(Converter.fromBit).toArray | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| object Tester extends App { | |
| val in = List(1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1).toArray | |
| val out = Solution.solution(in) | |
| val assertion: Array[Int] = Solution.solution(out) | |
| println(in.toList) | |
| println(assertion.toList) | |
| println(in.toList == assertion.toList) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment