; MIT License
; Copyright (C) 2022 Shintaro Mukai.
; https://mukai.systems/articles/c1mra8acn43i8k5pytofabwy3vsfvckd/

; xor.

(import :rand)

(macro test (x y)
  `(if (!= ,x ,y) (raise Error (str "assert failed " (list :expr ',x :evaluated ,x :expected ',y)))))

(function bits (b0 b1)
  (if (every? zero? (list b0 b1)) nil
      (zero? b1) (cons 0 (bits (-- b0) b1))
      (cons 1 (bits b0 (-- b1)))))

(function rand-bits (b0 b1)
  (rand.shuffle! (bits b0 b1)))

(function xor (x y)
  (if (= x y) 0 1))

(function simulate (n m)
  ; loop version.
  (let (lis (rand-bits n m))
    (while (cdr lis)
      (<- lis (rand.shuffle! lis))
      (push! (xor (pop! lis) (pop! lis)) lis))
    (car lis)))

(function! simulate (n m)
  ; recursion version.
  (let (rec (f (bag)
              (if (nil? (cdr bag)) (car bag)
                  (simulate-rec (rand.shuffle! (cons (xor (car bag) (cadr bag)) (cddr bag)))))))
    (simulate-rec (rand-bits n m))))

(function! simulate (n m)
  ; xor is commutative and associative.
  (reduce xor (bits n m)))

(function! main (args)
  (test (sort! (bits 0 0)) nil)
  (test (sort! (bits 5 0)) '(0 0 0 0 0))
  (test (sort! (bits 0 5)) '(1 1 1 1 1))
  (test (sort! (rand-bits 3 2)) '(0 0 0 1 1))
  (test (sort! (rand-bits 2 3)) '(0 0 1 1 1))
  (test (xor 0 0) 0)
  (test (xor 1 0) 1)
  (test (xor 0 1) 1)
  (test (xor 1 1) 0)
  (dotimes (n 10)
    (dotimes (m 10)
      (test (simulate (++ n) (++ m)) (% (++ m) 2)))))