DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #149 - Fun with Lamps

#challenge

Setup

A number (n) of lamps are placed in a line, some are switched on and some are off. Write a function that will return the smallest number of lamps that need to be switched on or off so that the line of lamps alternate.

You are given an array of 0s and 1s as input. 1 means on, 0 means off. Return the minimum number of switches needed.

Example

For a = [1, 0, 0, 1, 1, 1, 0], the result should be 3.
1 0 0 1 1 1 0 --> 0 1 0 1 0 1 0

Tests 

lamps([1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1])

lamps( [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

lamps([1, 0, 1])

lamps([1, 0, 1, 0])

lamps([0, 1, 0, 1, 0])

lamps([1, 0, 1, 0, 0, 1, 0, 1])

lamps([1,0,0,1,1,0,0,0,0,1,0])

Good luck, have fun!

This challenge comes from myjinxin2015 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (12)

Collapse
 
kmruiz profile image
Kevin Mas Ruiz • • Edited

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)
Collapse
 
rafaacioly profile image
Rafael Acioly • • 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

Collapse
 
kmruiz profile image
Kevin Mas Ruiz • • 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.

Thread Thread
 
rafaacioly profile image
Rafael Acioly • • 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

Thread Thread
 
kmruiz profile image
Kevin Mas Ruiz •

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.

Thread Thread
 
aminnairi profile image
Amin •

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.

Collapse
 
idanarye profile image
Idan Arye •

Rust:

fn lamps(current_states: &[usize]) -> usize {
    let result_for = |offset: usize| {
        current_states.iter().enumerate().filter(|(index, &state)| {
            let desired_state = (index + offset) % 2;
            desired_state == state
        }).count()
    };
    std::cmp::min(result_for(0), result_for(1))
}

fn main() {
    assert_eq!(lamps(&[1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1]), 5);
    assert_eq!(lamps(&[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 6);
    assert_eq!(lamps(&[1, 0, 1]), 0);
    assert_eq!(lamps(&[1, 0, 1, 0]), 0);
    assert_eq!(lamps(&[0, 1, 0, 1, 0]), 0);
    assert_eq!(lamps(&[1, 0, 1, 0, 0, 1, 0, 1]), 4);
    assert_eq!(lamps(&[1,0,0,1,1,0,0,0,0,1,0]), 5);
}
Collapse
 
sabbin profile image
Sabin Pandelovitch • • Edited

Javascript

const getResults = lamps => {
  const results = lamps.reduce(
    (acc, val, i) =>
      i % 2 === 0
        ? {
            a: val === 0 ? acc.a + 1 : acc.a,
            b: val === 1 ? acc.b + 1 : acc.b
          }
        : {
            a: val === 1 ? acc.a + 1 : acc.a,
            b: val === 0 ? acc.b + 1 : acc.b
          },
    { a: 0, b: 0 }
  );

  return results.a <= results.b ? results.a : results.b;
};

console.log(getResults([1, 0, 0, 1, 1, 1, 0]));
Collapse
 
leonardoalonso profile image
Leonardo Alonso • • Edited

Python:

def lamps(lamps_list):
    steps = 0
    for idx in range(0, len(lamps_list) - 1):
        if lamps_list[idx + 1] == lamps_list[idx]:
            steps += 1
            lamps_list[idx + 1] = 1 if lamps_list[idx] == 0 else 0
    return steps
if __name__ == "__main__":
    assert lamps([1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1]) == 5
    assert lamps([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) == 6
    assert lamps([1, 0, 1]) == 0
    assert lamps([1, 0, 1, 0]) == 0
    assert lamps([0, 1, 0, 1, 0]) == 0
    assert lamps([1, 0, 1, 0, 0, 1, 0, 1]) == 4
    assert lamps([1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0]) == 6
Collapse
 
elvezpablo profile image
Paul •

A variation on the javascript solution. Opted for a bit more verbosity for ease of understanding. Would love feedback as I get my coding skills back into shape.

const lamps = ary => {
  return ary.reduce((acc, curr, idx) => {
    const startsWithZero = ary[0] === 0;
    const isEven = idx % 2 === 0;
    const correctValue =
      (startsWithZero && !isEven) || (!startsWithZero && isEven) ? 1 : 0;

    return correctValue !== curr ? (acc += 1) : acc;
  }, 0);
};
Collapse
 
aminnairi profile image
Amin • • Edited

Elm

import List exposing (filter, head, indexedMap, length)
import Maybe exposing (withDefault)
import Tuple exposing (pair)


switchNeeded : List Int -> ( Int, Int ) -> Bool
switchNeeded line ( index, lamp ) =
    if (line |> head |> withDefault 0) == 0 then
        modBy 2 index /= lamp
    else
        modBy 2 index == lamp


lamps : List Int -> Int
lamps line =
    line
        |> indexedMap pair
        |> filter (switchNeeded line)
        |> length

Demo.

Collapse
 
bamartindev profile image
Brett Martin •

Standard ML of New Jersey

fun gen_alt (starting, next, len) = List.tabulate(len, fn x => if x mod 2 = 0 then starting else next)

fun diff ([], []) = 0
  | diff (x::xs, y::ys) = (if x = y then 0 else 1) + diff(xs, ys)
  | diff (_, _) = ~1 (* List lengths don't match for some reason *)

fun lamps [] = 0
  | lamps i = Int.min(diff(i, gen_alt(0, 1, length i)), diff(i, gen_alt(1, 0, length i)))
View full discussion (12 comments)

Read next

tanvir_ahamed profile image

Exploring the Core of true value vs false value in JavaScript...

Tanvir Ahmed -

ehab7osam profile image

LeetCode in Golang: Parsing A Boolean Expression

Ehab Hosam -

i_am_vesh profile image

Understanding Microsoft Entra ID (Formerly Azure Active Directory) for the Azure Administration Certification Exam-Az 104

Avesh -

end3r profile image

Judging the first DEV Web Game Challenge

Andrzej Mazur -