11
\$\begingroup\$

Related but noticeably different

You are the leader of the guard in the dungeon of an ancient castle.
There are N doors in the dungeon and N guards with keys.
Guard with index i may operates with doors that have multiple indexes:
i, 2 * i, 3 * i, ...

The way he operates is very dumb: he just toggles state of the door: "open" → "close", "close" → "open".
Every morning you are given two lists:

  • the list of doors that are open now (criminally or legally)
  • the list of doors that must be open after your shift

Your goal is to select the minimum number of guards to accomplish the task.

Each guard from your selected team passes through all his doors (scan and opens/closes them), but only once and only one way, starting from the first guard in the list.

Examples

Number of doors: 1001
Doors are opened: [ ]
Doors must be opened: [ ]
Answer: [ ]

Number of doors: 10
Doors are opened: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Doors must be opened: [ ]
Answer: [1] (First guard closes all doors)

Number of doors: 5
Doors are opened: [1, 2, 3]
Doors must be opened: [3, 4, 5]
Answer: [1, 3] (After guard #1 doors [4, 5] are opened, and guard #3 just open door #3)

Input

  • Number of doors N
  • List of doors are opened now
  • List of doors must be opened

Every list is valid: no negative or > N numbers, duplicates etc.
Also you may suppose that lists are sorted as you need: by ascending or descending.

Output

Any of teams of guards (that resolves the task) with minimal number of members.

About solution

I remember that there should be considerations from the number theory that either solve the problem in a closed form or greatly optimize searching. But I can’t formulate them yet.

Test cases

6, [2, 3, 4], [3, 4, 5] → [2, 4, 5, 6]  
8, [1, 8], [4] → [1, 2, 3, 4, 5, 6, 7]  
100, [12], [13] → [12, 13, 24, 26, 36, 39, 60, 65, 72, 78, 84, 91 ]  
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I suspect that guard \$k\$ should be included if and only if you need to toggle an odd number of doors of the form \$k/d\$ with \$d\$ square-free. \$\endgroup\$
    – Nitrodon
    Apr 4, 2023 at 18:08
  • \$\begingroup\$ @Nitrodon It's interesting, but what about even number of doors? Could it help to get closed form solution? \$\endgroup\$
    – lesobrod
    Apr 4, 2023 at 18:43

4 Answers 4

5
\$\begingroup\$

JavaScript (ES6), 83 bytes

Expects (source, target)(N), where the first two arguments are sets. Returns an array.

(a,b,o=q=[])=>g=n=>++q>n?o:g(n,o.map(v=>p^=q%v<1,p=a.has(q)^b.has(q))|p&&o.push(q))

Try it online!

Commented

(                  // outer function taking:
  a,               //   a   = set of currently open doors
  b,               //   b   = target set of opened doors
  o =              //   o[] = output list
  q = []           //   q   = counter, initially zero'ish
) =>               //
g = n =>           // inner recursive function taking n
++q > n ?          // increment q; if it's greater than n:
  o                //   stop and return o[]
:                  // else:
  g(               //   do a recursive call:
    n,             //     pass n unchanged
    o.map(v =>     //     for each entry v in o[]:
      p ^=         //       toggle p if:
        q % v < 1, //         v is a divisor of q
      p =          //       start with p set to:
        a.has(q) ^ //         the presence of q in a
        b.has(q)   //         XOR the presence of q in b
    ) |            //     end of map()
    p &&           //     if p is truthy:
      o.push(q)    //       append q to o[]
  )                //   end of recursive call
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 31 bytes

≔⁺⁻ηζ⁻ζηηW⌊η«≔Φ…·¹θ⁻¬﹪κι№ηκη⟦Iι

Try it online! Link is to verbose version of code. Explanation:

≔⁺⁻ηζ⁻ζηη

Get the list of doors that need to be toggled.

W⌊η«

While there are doors remaining, get the next guard needed.

≔Φ…·¹θ⁻¬﹪κι№ηκη

Calculate the new list of doors that need to be toggled.

⟦Iι

Output the guard.

\$\endgroup\$
1
  • \$\begingroup\$ Cool! 1000 doors just for 1.7 s! \$\endgroup\$
    – lesobrod
    Apr 4, 2023 at 9:36
3
\$\begingroup\$

05AB1E, 21 20 bytes

«Ð¢Ï[W,©g!#Lʒ®ßÖ®yå^

Port of @Neil's Charcoal answer, so make sure to upvote him as well!

Inputs in the order \$[openDoors], [doorsToBeOpened], numberOfDoors\$; outputs the results on separated lines to STDOUT.

Try it online or verify all test cases.

Explanation:

«      # Merge the first two (implicit) input-lists together
 Ð     # Triplicate this list
  ¢    # Pop two copies, and get the counts of each item
   Ï   # Only leave the items where the count is 1
       # (we now have an unordered list of unique items of the merged input-lists)
[      # Start an infinite loop:
 W     #  Push the minimum of the list (without popping the list itself)
  ,    #  Pop and print this minimum with trailing newline
 ©     #  Store the list in variable `®` (without popping)
  g    #  Pop and push the length of the list
   !   #  Faculty (edge case for an empty input-lists)
    #  #  If this length! equals 1 (aka length is 0 or 1): stop the infinite loop
 L     #  Push a list in the range [1, third (implicit) input-integer]
  ʒ    #  Filter it by:
   ®ß  #   Push the minimum of list `®` again
     Ö #   Check if the current item is divisible by this minimum
   ®   #   Push list `®` again
    yå #   Check if the current item is in list `®`
   ^   #   Bitwise-XOR to check either of the two is truthy (but not both!)
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for detailed explanation! \$\endgroup\$
    – lesobrod
    Apr 4, 2023 at 18:48
0
\$\begingroup\$

Python3, 311 bytes

R=range
V=lambda i,o:{j for j in o if 0==j%i}
def f(n,o,O):
 q=[(o:={*o},{*R(1,n+1)}-o,[])]
 for o,c,p in q:
  if[*o]==O:return p
  for i in R(min({*o,*O}),n+1):
   if i>max(p+[0])and(C:=V(i,{*o,*O})):
    U=V(i,c);Q={*(o-C),*U}
    if not(t:={j for j in Q if j not in O})or i<=min(t):q+=[(Q,{*(c-U),*C},p+[i])]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.