Discussion on: Daily Challenge #149 - Fun with Lamps

View post

A Common Lisp implementation 😊.

Correct solution:


;; implementation V
(defun %generate-solutions (for-n)
  (loop repeat for-n
     for i = 0 then (mod (+ 1 i) 2)
     and j = 1 then (mod (+ 1 j) 2)
     collect i into direct
     collect j into alternate
     finally (return (list direct alternate))))

(defun %min-diff-of (lamps-state possible-solutions)
  (loop for solution in possible-solutions
     collect (loop
        for zipped in (mapcar #'list solution lamps-state)
        summing (abs (apply #'- zipped)))
     into steps
     finally (return (apply 'min steps))))

(defun lamps (lamps-state)
  (%min-diff-of lamps-state (%generate-solutions (length lamps-state))))

;; tests V
(defun tests ()
  (assert (= 5 (lamps (list 1 0 0 1 0 1 0 0 1 0 1))))
  ;;;;                (list 1 0 1 0 1 0 1 0 1 0 1) : 5
  ;;;;                (list 0 1 0 1 0 1 0 1 0 1 0) : 6
  (assert (= 6 (lamps (list 1 1 1 1 1 1 1 1 1 1 1 1))))
  ;;;;                (list 1 0 1 0 1 0 1 0 1 0 1 0) : 6
  ;;;;                (list 0 1 0 1 0 1 0 1 0 1 0 1) : 6
  (assert (= 0 (lamps (list 1 0 1))))
  ;;;;                (list 1 0 1) : 0
  (assert (= 0 (lamps (list 1 0 1 0))))
  ;;;;                (list 1 0 1 0) : 0
  (assert (= 0 (lamps (list 0 1 0 1 0))))
  ;;;;                (list 0 1 0 1 0) : 0
  (assert (= 4 (lamps (list 1 0 1 0 0 1 0 1))))
  ;;;;                (list 1 0 1 0 1 0 1 0) : 4
  ;;;;                (list 0 1 0 1 0 1 0 1) : 4
  (assert (= 5 (lamps (list 1 0 0 1 1 0 0 0 0 1 0))))
  ;;;;                (list 1 0 1 0 1 0 1 0 1 0 1) : 5
  ;;;;                (list 0 1 0 1 0 1 0 1 0 1 0) : 5
  t)

This solution is wrong, I'll change it and put the new corrected one of the top. I misunderstood the problem statement the first time.

;; implementation V
(defun %count (number) (if (zerop number) (list 1 0) (list 0 1)))
(defun %sum-tuple (a b) (list (+ (first a) (first b)) (+ (second a) (second b))))

(defun lamps (list)
  (apply 'min (reduce #'%sum-tuple (map 'list #'%count list))))

;; tests V
(defun tests ()
  (assert (= 5 (lamps (list 1 0 0 1 0 1 0 0 1 0 1))))
  (assert (= 0 (lamps (list 1 1 1 1 1 1 1 1 1 1 1 1))))
  (assert (= 1 (lamps (list 1 0 1))))
  (assert (= 2 (lamps (list 1 0 1 0))))
  (assert (= 2 (lamps (list 0 1 0 1 0))))
  (assert (= 4 (lamps (list 1 0 1 0 0 1 0 1))))
  (assert (= 4 (lamps (list 1 0 0 1 1 0 0 0 0 1 0))))
  t)

Rafael Acioly • Dec 30 '19 • Edited

the first test shouldn't be 6?
1 0 0 1 0 1 0 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 (alternated)
x x - - - - - x x x x

Kevin Mas Ruiz • Dec 30 '19 • Edited

What I've understood from the problem statement is that both converting everything to 0s and converting everything to 1s are valid answers, and you need to choose the fastest one (less changes needed).

For the 1 0 0 1 0 1 0 0 1 0 1

Changing all 1s to 0s -> 5 changes
Changing all 0s to 1s -> 6 changes

Maybe I understood it wrong :( Definetely, I understood it wrong. I'll change it :D.

Rafael Acioly • Dec 30 '19 • Edited

I don't know, i think that you understood it right your solution makes sense, the way that i imagine there is no way to get the "less changes needed" because i'll switch everything to see if it it's alternated

Kevin Mas Ruiz • Dec 30 '19

I though the solution was to count the number of changes to light everything on or off. But the idea is to find out the number of changes for alternate lights, so the solution there is wrong :(.

I just changed the original post to add the new solution.

Amin • Dec 30 '19

Now that I read the comments, I think Kevin is right, but I understood it from the point of view of Rafael. But it makes sense since they need to alternate, not to start with 0 (switched off) everytime.