Math factors game - who can write the most elegant solution?

Question

Here's a fun exercise.

http://www.hughchou.org/hugh/grid_game.cgi?CLEAR

Who can write the most elegant yet performant code to win this game? My solution is in C/C++.

#include<vector>
#include<iostream>
#include<fstream>

#define N 64

std::vector<int> numbers(N+1);

void init()
{
    for(int i = 0; i < N+1; ++i)
     numbers[i] = 1;
}

int getbest()
{
    int max_difference = -9999999;
    int best_number = -1;

    for(int i = 1; i <= N; ++i)
    {
     // if the number is available for choosing, check how many points it's worth
     if(numbers[i])
     {
      int sum_factors = 0;

      for(int j = 1; j < i; ++j)
      {
       if(numbers[j] && i%j == 0)
        sum_factors += j;
      }

      // if we found any factors
      if(sum_factors != 0 && (i - sum_factors) > max_difference)
      {
       max_difference = i - sum_factors;
       best_number = i;
      }
     }
    }

    std::cout<<"max difference: "<<max_difference<<"\n";
    std::cout<<"best choice: "<<best_number<<"\n";

    for(int i = 1; i < best_number; ++i)
    {
     if(best_number % i == 0)
      numbers[i] = 0;
    }

    return best_number;
}

int main()
{
    init();

    int n;
    do
    {
     n = getbest();
    } while(n != -1);
}

Answer 1

Your code will be more efficient if you start from the biggest number, and also zero out the numbers picked, not just their factors.

Also, I'm not convinced that picking the optimum number in a turn will result in optimum gameplay.

Answer 2

A quick Common Lisp version:

;;; helpers                                                                                                          

(defun list-range (start end &optional (step 1))
  "Makes a list from start (inclusive) to end (exclusive)."
  (labels ((lr-h (z acc)
             (if (>= z end)
                 (nreverse acc)
                 (lr-h (+ z step) (cons z acc)))))
    (lr-h start ())))

(defun remove-list (r-liste liste)
  "Returns a list where all elements in r-liste are removed from liste."
  (if r-liste
      (remove-list (cdr r-liste) (remove (car r-liste) liste))
      liste))

;;; calculations

(defun faktoren (zahl verfuegbare-tests)
  "Returns the list of zahl's factors that are in verfuegbare-tests."
  (labels ((f-h (tests max acc)
             (cond ((or (not (car tests))
                        (> (car tests) max))
                    acc)
                   ((integerp (/ zahl (car tests)))
                    (f-h (cdr tests) max (cons (car tests) acc)))
                   (t
                    (f-h (cdr tests) max acc)))))
    (f-h verfuegbare-tests (/ zahl 2) ())))

(defun faktoren-summe (zahl verfuegbare-tests)
  (reduce #'+ (faktoren zahl verfuegbare-tests)))

(defun beste-zahl (liste)
  (let ((v-liste (remove-if #'(lambda (x) (zerop (faktoren-summe x liste))) liste)))
    (if v-liste
        (reduce #'(lambda (a b)
                    (if (> (- a (faktoren-summe a liste))
                           (- b (faktoren-summe b liste)))
                        a
                        b))
                v-liste)
        nil)))

;;; main loop                                                                                                        

(defun hugh ()
  (labels ((h-h (liste)
             (when liste
               (let ((b (beste-zahl liste)))
                 (format t "Best: ~a~%" b)
                 (if b
                     (h-h (remove-list (cons b (faktoren b liste))
                                       liste))
                     t)))))
    (h-h (list-range 1 65))))

Answer 3

Every move clears at least two numbers, more like 3-4 including then-invalidated choices (a first move of "61" seems ideal, and reduces the number of available valid moves by 18). I expect the entire state space to be smaller than 10^15, significantly smaller with even simple pruning. This game can be Solved in reasonably small run time, so the optimal-performing solution would probably just be a state table with responses to the <10^7 possible branches of the the tree. Not very elegant, though.