Largest Remainder

Largest Possible Remainder problem in racket:

;;lr = largest remainder so far lrd = divisor with largest remainder
(define (largest-remainder n d (lr 0) (lrd 0)) 
  (cond
    [(= d 0) (values lr lrd)] ;;catch cases like n = 6, d = 3
    [(> lr d) (values lr lrd)] ;;stop when d is < largest remainder
    [(> (modulo n d) lr)
     (largest-remainder n (sub1 d) (modulo n d) d)] ;;save new largest remainder
    [else 
     (largest-remainder n (sub1 d) lr lrd)])) ;;iterate with d-1

Common Lisp translation:

(defun largest-remainder (n d &optional (lr 0) (lrd 0))
  (cond
    ((<= d 0) (values lr lrd))
    ((< d lr) (values lr lrd))
    (t (let ((r (rem n d)))
	 (if (> r lr)
	     (largest-remainder n (1- d) r d)
	     (largest-remainder n (1- d) lr lrd))))))

Iterative in python.


def largest_remainder(n,d):
    lr = 0
    lrd = 0
    while (d >= lr) and (d > 0):
        if (n % d > lr):
            lr = n % d
            lrd = d
        d -= 1
    return (lr,lrd)

print largest_remainder(20,10)
print largest_remainder(6,3)

Limited Median Problem

Another Programming Praxis problem. The problem is nicely constrained by limiting it to 8-bit numbers.

#lang racket

(define (limited-median xs)
  (define xsv (make-vector 256 0))
  (for ([x xs])
    (vector-set! xsv x (+ 1 (vector-ref xsv x))))
  (define half-limit (/ (length xs) 2))
  (define (median low high low-count high-count)
    (cond
      [(< low-count half-limit) 
       (median (add1 low) high (+ low-count (vector-ref xsv low)) high-count)]
      [(< high-count half-limit)
       (median low (sub1 high) low-count (+ high-count (vector-ref xsv high)))]
      [else
       (/ (+ low high) 2)]))
  (median 0 255 0 0))

Edit: C++

#include <iostream>
#include <array>
#include <vector>
//#include <cstdio>
//#include <cmath>
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */

//linux: clang++ -std=c++11 -g -Wall limited_median.cpp -o limited_median

float limited_median (std::vector<int> numbers){
  std::array<int,256> counting_array;
  counting_array.fill(0);
  int count = numbers.size();
  for (int const& i : numbers) { counting_array[i]++; }
  int right = 255;
  int right_count = 0;
  int left = 0;
  int left_count = 0;
  int half_limit = count / 2;
  while (left_count < half_limit)
    {
      left_count += counting_array[left];
      left ++;
    }
  while (right_count < half_limit)
    {
      right_count += counting_array[right];
      right --;
    }
  return (left + right)/ 2.0;
  
}



int main(int argc, char* argv[]){
  std::vector<int> test1 {2,4,5,7,3,6,1};
  std::vector<int> test2 {5,2,1,6,3,4};
  
  std::cout << limited_median(test1) << "\n";
  std::cout << limited_median(test2) << "\n";

  
  //test with 5000 random numbers  
  srand(time(NULL));
  std::vector<int> test3;
  for (int i = 0; i < 5000; i++)
    {
      test3.push_back((rand() % 256));
    }
  std::cout << limited_median(test3) << "\n";
  return 0;
}