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