khf0.cc

#include "../cekla.h"

// helper function: length(l, len) => length of a list
int length (const list l, const int len) {
  if (l == nil) return len;
  return length(tl(l), len + 1);
}

// length(l) => length of a list
int length (const list l) {
  return length(l, 0);
}

// helper function: revapp(l, l0) => reverse of a list
list revapp (const list l, const list l0) {
  if (l == nil) return l0;
  return revapp(tl(l), cons(hd(l), l0));
}

// reverse(l) => reverse of a list
list reverse(const list l) {
  return revapp(l, nil);
}

// helper function: filter(f, l, i, r) => filters out the elements of a list
// with a given predicate (the predicate has two arguments, value and index)
list filter (const fun2 f, const list l, const int i, const list r) {
  if (l == nil) return r;
  const int h = hd(l);
  if (f(h, i)) return filter(f, tl(l), i + 1, cons(h, r));
  return filter(f, tl(l), i + 1, r);
}

// filter(f, l) => filters out the elements of a list with a given predicate
// (the predicate has two arguments, value and index)
list filter (const fun2 f, const list l) {
  return reverse(filter(f, l, 0, nil));
}

// biggest_power(s, a, p) => determines the biggest power of `a` that can be
// subtracted from `s`
int biggest_power (const int s, const int a, const int p) {
  if ((s - p * a) < 0) return p;
  return biggest_power(s, a, p * a);
}

// biggest_multiplier(s, p, m) => determines the biggest multiplier that can be
// subtracted from `s`
int biggest_multiplier (const int s, const int p, const int m) {
  if ((s - p * m) >= 0) return m;
  return biggest_multiplier(s, p, m - 1);
}

// reduce_number(s, a, p, l) => breaks down `s` to base `a` in a list `l`
list reduce_number (const int s, const int a, const int p, const list l) {
  if (p == 0) return l;
  const int m = biggest_multiplier(s, p, a - 1);
  return reduce_number(s - m * p, a, p / a, cons(m, l));
}

// is_odd(v, i) => determines if index `i` is odd
int is_odd (const int v, const int i) {
  return (i + 1) % 2 != 0;
}

// is_even(v, i) => determines if index `i` is even
int is_even (const int v, const int i) {
  return (i + 1) % 2 == 0;
}

// helper function: merge(a, b, i, r) => merges list `a` and `b` together
// placing `a` elems to odd places, `b` elems to even places
list merge (const list a, const list b, const int i, const list r) {
  if (a == nil) if (b == nil) return r;
  if ((i + 1) % 2 == 0) {
    if (b != nil) return merge(a, tl(b), i + 1, cons(hd(b), r));
    return merge(tl(a), b, i + 1, cons(hd(a), r));
  }
  if (a != nil) return merge(tl(a), b, i + 1, cons(hd(a), r));
  return merge(a, tl(b), i + 1, cons(hd(b), r));
}

// merge(a, b) => merges list `a` and `b` together
// placing `a` elems to odd places, `b` elems to even places
list merge (const list a, const list b) {
  return merge(a, b, 0, nil);
}

// helper function: pow(b, p, r) => calculates b^p in `r`
int pow (const int b, const int p, const int r) {
  if (p == 0) return r;
  return pow(b, p - 1, r * b);
}

// pow(b, p, r) => calculates b^p
int pow (const int b, const int p) {
  return pow(b, p, 1);
}

// helper function: to_number(l, b, a, r) => transforms the elems of list `l`
// into a number in base 10 from base `a`
int to_number (const list l, const int b, const int a, const int r) {
  if (l == nil) return r;
  return to_number(tl(l), b / a, a, hd(l) * b + r);
}

// to_number(l, a) => transforms the elems of list `l` into a number in base 10
// from base `a`
int to_number (const list l, const int a) {
  return to_number(l, pow(a, length(l) - 1), a, 0);
}

// osszekevert(s, a) => transforms `s` into base `a`, then mixes it (reversing
// the numbers in the even positions), then transforms it back to base 10
int osszekevert (const int s, const int a) {
  if (s < a) return s;
  const int bp = biggest_power(s, a, 1);
  const list number = reverse(reduce_number(s, a, bp, nil));
  const list odds = filter(is_odd, number);
  const list evens = reverse(filter(is_even, number));
  const list merged = reverse(merge(odds, evens));
  return to_number(merged, a);
}

int main () {
  return 0;
}