🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of hyphenrf

hyphenrf's solution

to All Your Base in the OCaml Track

Published at May 04 2020 · 0 comments
Instructions
Test suite
Solution

Convert a number, represented as a sequence of digits in one base, to any other base.

Implement general base conversion. Given a number in base a, represented as a sequence of digits, convert it to base b.

Note

  • Try to implement the conversion yourself. Do not use something else to perform the conversion for you.

About Positional Notation

In positional notation, a number in base b can be understood as a linear combination of powers of b.

The number 42, in base 10, means:

(4 * 10^1) + (2 * 10^0)

The number 101010, in base 2, means:

(1 * 2^5) + (0 * 2^4) + (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (0 * 2^0)

The number 1120, in base 3, means:

(1 * 3^3) + (1 * 3^2) + (2 * 3^1) + (0 * 3^0)

I think you got the idea!

Yes. Those three numbers above are exactly the same. Congratulations!

Getting Started

  1. Install the Exercism CLI.

  2. Install OCaml.

  3. For library documentation, follow Useful OCaml resources.

Running Tests

A Makefile is provided with a default target to compile your solution and run the tests. At the command line, type:

make

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

Feedback, Issues, Pull Requests

The exercism/ocaml repository on GitHub is the home for all of the Ocaml exercises.

If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue or submit a PR. We welcome new contributors!

test.ml

(* all-your-base - 2.3.0 *)
open OUnit2
open All_your_base

let option_printer = function
  | None -> "None"
  | Some xs -> "Some [" ^ String.concat ";" (List.map string_of_int xs) ^ "]"

let ae exp got _test_ctxt =
  assert_equal exp got ~printer:option_printer

let tests = [
  "single bit one to decimal" >::
  ae (Some [1]) (convert_bases ~from:2 ~digits:[1] ~target:10);
  "binary to single decimal" >::
  ae (Some [5]) (convert_bases ~from:2 ~digits:[1; 0; 1] ~target:10);
  "single decimal to binary" >::
  ae (Some [1; 0; 1]) (convert_bases ~from:10 ~digits:[5] ~target:2);
  "binary to multiple decimal" >::
  ae (Some [4; 2]) (convert_bases ~from:2 ~digits:[1; 0; 1; 0; 1; 0] ~target:10);
  "decimal to binary" >::
  ae (Some [1; 0; 1; 0; 1; 0]) (convert_bases ~from:10 ~digits:[4; 2] ~target:2);
  "trinary to hexadecimal" >::
  ae (Some [2; 10]) (convert_bases ~from:3 ~digits:[1; 1; 2; 0] ~target:16);
  "hexadecimal to trinary" >::
  ae (Some [1; 1; 2; 0]) (convert_bases ~from:16 ~digits:[2; 10] ~target:3);
  "15-bit integer" >::
  ae (Some [6; 10; 45]) (convert_bases ~from:97 ~digits:[3; 46; 60] ~target:73);
  "empty list" >::
  ae (Some [0]) (convert_bases ~from:2 ~digits:[] ~target:10);
  "single zero" >::
  ae (Some [0]) (convert_bases ~from:10 ~digits:[0] ~target:2);
  "multiple zeros" >::
  ae (Some [0]) (convert_bases ~from:10 ~digits:[0; 0; 0] ~target:2);
  "leading zeros" >::
  ae (Some [4; 2]) (convert_bases ~from:7 ~digits:[0; 6; 0] ~target:10);
  "input base is one" >::
  ae None (convert_bases ~from:1 ~digits:[0] ~target:10);
  "input base is zero" >::
  ae None (convert_bases ~from:0 ~digits:[] ~target:10);
  "input base is negative" >::
  ae None (convert_bases ~from:(-2) ~digits:[1] ~target:10);
  "negative digit" >::
  ae None (convert_bases ~from:2 ~digits:[1; -1; 1; 0; 1; 0] ~target:10);
  "invalid positive digit" >::
  ae None (convert_bases ~from:2 ~digits:[1; 2; 1; 0; 1; 0] ~target:10);
  "output base is one" >::
  ae None (convert_bases ~from:2 ~digits:[1; 0; 1; 0; 1; 0] ~target:1);
  "output base is zero" >::
  ae None (convert_bases ~from:10 ~digits:[7] ~target:0);
  "output base is negative" >::
  ae None (convert_bases ~from:2 ~digits:[1] ~target:(-7));
  "both bases are negative" >::
  ae None (convert_bases ~from:(-2) ~digits:[1] ~target:(-7));
]

let () =
  run_test_tt_main ("all-your-bases tests" >::: tests)
type base = int

let convert_bases ~from ~digits ~target =
  if from < 2 || target < 2 then None
  else if not @@List.for_all (fun x -> x >= 0 && x < from) digits then None
  else
    let rec to_base_list = function
      | n when n = 0 -> []
      | n -> let (d, m) = (n / target), (n mod target) in
             (to_base_list d) @ [m]
    in
    let places = List.length digits in
    let powers = List.init places (fun x -> places - x - 1) in
    let ( ** ) a b = int_of_float (float a ** float b) in
    let out = List.fold_left2 
              (fun acc digit place -> acc + digit * (from ** place)) 
              0 digits powers
    |> to_base_list
    in if out = [] then Some [0] else Some out

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?