exercism

Exercism solutions.
git clone git://code.dwrz.net/exercism
Log | Files | Refs

grains.el (2895B)


      1 ;;; grains.el --- Grains exercise (exercism)
      2 
      3 ;;; Commentary:
      4 ;;; I solved this problem on the C track. There, the solution was
      5 ;;; simpler: simply shift an unsigned long long to get the number of
      6 ;;; grains at square n.
      7 ;;;
      8 ;;; In Emacs, that approach doesn't seem to work. Only 61 bits are used
      9 ;;; for integers, resulting in overflows above square 60.
     10 ;;;
     11 ;;; The solution, if one wants to calculate it, seems to be to rely on
     12 ;;; the calc package to calculate bigger numbers. The functions
     13 ;;; calculate-square and calculate-total rely on that approach.
     14 ;;;
     15 ;;; However, it also occurred to me that the values here are known,
     16 ;;; limited, and not likely to change anytime soon. By using contants,
     17 ;;; we can get constant time determination of the number of grains for
     18 ;;; a square. The functions used by the tests, square and total, return
     19 ;;; these constant values.
     20 ;;;
     21 ;;; Emacs itself was useful in effectuating this solution. I used a
     22 ;;; macro to evaluate calculate-square for n, and then insert the
     23 ;;; results in this buffer. There's probably a more elegant way to do
     24 ;;; this, but the approach was adequate for this task.
     25 ;;;
     26 ;;; Sometimes, making the programmer's life easier can lead to more
     27 ;;; efficient code.
     28 
     29 ;;; Code:
     30 
     31 (require 'calc)
     32 
     33 (defvar grains
     34   [0 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072
     35      262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864
     36      134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592
     37      17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
     38      1099511627776 2199023255552 4398046511104 8796093022208 17592186044416
     39      35184372088832 70368744177664 140737488355328 281474976710656
     40      562949953421312 1125899906842624 2251799813685248 4503599627370496
     41      9007199254740992  18014398509481984 36028797018963968 72057594037927936
     42      144115188075855872 288230376151711744 576460752303423488
     43      1152921504606846976 2305843009213693952 4611686018427387904
     44      9223372036854775808]
     45   "Vector containing the number of grains for a square with the corresponding index.")
     46 
     47 (defun square(n)
     48   "Return the number of grans at square n; 0 for negative numbers and numbers above 64."
     49   (cond ((< n 0) 0)
     50 	((> n 64) 0)
     51 	(t (aref grains n))))
     52 
     53 (defun total()
     54   "Return the total number of grains on a chessboard with 64 squares."
     55   18446744073709551616)
     56 
     57 (defun calculate-square(n) ;; Not used, for reference only.
     58   "Return the number of grains at square N. Use left shifts when n is equal to or below 60, and calc for numbers up to 65."
     59   (cond ((< n 0) 0)
     60 	((> n 65) 0)
     61 	((<= n 60) (lsh 1 (- n 1)))
     62 	(t (string-to-number (calc-eval (format "2^%d" (1- n)))))))
     63 
     64 (defun calculate-total() ;; Not used, for reference only.
     65   "Return the total number of grains on a chessboard with 64 squares."
     66   (1- (square 65)))
     67 
     68 (provide 'grains)
     69 ;;; grains.el ends here