coins.rkt

#lang racket

; Coin Flips!
; http://fivethirtyeight.com/features/can-you-survive-this-deadly-board-game/
;
; You place 100 coins heads up in a row and number them by position, with the coin all the way on the left No. 1 and the one on the rightmost edge No. 100. Next, for every number N, from 1 to 100, you flip over every coin whose position is a multiple of N. For example, first you’ll flip over all the coins, because every number is a multiple of 1. Then you’ll flip over all the even-numbered coins, because they’re multiples of 2. Then you’ll flip coins No.  over all the coins, because every number is a multiple of 1. Then you’ll flip over all the even-numbered coins, because they’re multiples of 2. Then you’ll flip coins No. 3, 6, 9, 12 ... And so on.
;
; What do the coins look like when you’re done? Specifically, which coins are heads down?

; Heads is true, tails is false
(define heads #t)
(define tails #f)

; Flip is therefore the `not` unary operator
(define flip not)

; heads? is the same as just asking for the value (since true is heads!)
(define heads? values)
; tails? is a not
(define tails? not)

; Start off with 100 coins
(define coins
  (build-list 100 (lambda (n) heads)))

; Let's define a function that will flip every n coins
(define (flip-every coins n)
  ; Inner helper function to recurse
  (define (inner coins index)
          ; Base case
    (cond ((empty? coins) '())
          ; Flip this coin!
          ((= index n)
           ; Specifically, flip the first coin and recurse on the remaining coins
           ; Resetting our index to 1
           (cons (flip (car coins))
                 (inner (cdr coins) 1)))
          (else
           ; Otherwise keep the first coin and flip the others
           (cons (car coins)
                 (inner (cdr coins) (+ index 1))))))
  (inner coins 1))

; Let's flip every other coin and show the first 10
(take (flip-every coins 2)
      10)
; => '(#t #f #t #f #t #f #t #f #t #f)

; Sweet, now let's invoke flip-every from n to 100
(define flip-from-1-to-100
         ; Reduce `flip-every`
  (foldl (lambda (n memo)
           (flip-every memo n))
         ; Using `coins`
         coins
         ; Over the numbers 1 to 100
         (range 1 101)))

; What do the first 10 results look like?
(take flip-from-1-to-100 10)

; Let's extract the indices for all the heads and tails
;
; First, we'll define a general `extract-indices` that takes in an array and procedure that tests the first value of the list and returns the index if the result is true
(define (extract-indices arr proc)
  (define (inner arr index)
    (cond ((empty? arr) '())
          ((proc (car arr))
           (cons index
                 (inner (cdr arr) (+ index 1))))
          (else
           (inner (cdr arr) (+ index 1)))))
  (inner arr 1))

(define heads-indices (extract-indices flip-from-1-to-100 heads?))
(define tails-indicies (extract-indices flip-from-1-to-100 tails?))

; So, which coins are tails?
tails-indicies
; => '(1 4 9 16 25 36 49 64 81 100)
; The squares!
;
; Why is this?
; Coins are flipped once for each factor. For example, coin #12 will be flipped when n=[1,2,3,4,6,12], or 6 times. These factors come in pairs, that is, 1*12 = 2*6 = 3*4.
; Getting a particular coin to show `tails` requires an _odd_ number of flips. Meaning that the only coins to show tails must have an odd number of factors.
;
; Factors travel in pairs, and the squares are unique in that the square root is paired with itself! So a number like 16 = [1,2,4,8,16] has an odd number of pairs.
;
; Therefore, the coins showing tails will be those with square indices.