5
$\begingroup$

Leuks is the land of light bulbs, where the bulbs are leading a peaceful life, with no humans at all. Presently there are 100 residents . (Of course, they all are light bulbs!).

Let $a_{1}, a_{2}, . . .,a_{100}$ be the 100 residents.

The relationships that exist among the residents are quite complicated to understand.

For example, say, if $a_{1} $ is ON , then $a_{2}$ and $a_{3}$ are OFF, $a_{7}$ is ON.

If $a_{12}$ is ON and $a_{25}$ is OFF , then $a_{20}$ $a_{92}$ $a_{45}$ are ON.

These are just some examples and there are a lot more relationships like this that exist within the community.

Yearly, the community invites some citizens from Earth (of course Humans like you!) to solve this puzzle:

all the 100 bulbs go and hide in boxes numbered $b_{1}, b_{2}, . . .,b_{100} $ sequentially, i.e., a1 goes to b1 and so on.

They tell you ALL relationship possibilities that exist within the community as I gave in the examples.

Your aim is to figure out all the bulbs which are ON, by opening and looking up the ON/OFF status of minimum number of bulbs.

How will you do it? Can you win the prize!

Notes:

  1. The human who finds all active bulbs with minimum number of lookups win
  2. There is no guarantee that every bulb will be in some relationship. But note that the list of all possible relationships are given to you (For example as a collection of if... then...statements)

  3. I am looking for a general algorithmic approach. For example, to start with, if a bulb is not in any relationship, you have to open the corresponding box for sure.

$\endgroup$
  • 1
    $\begingroup$ How many relationships are there? Is each resident part of at least one relationship? Who wins the prize? The human with the lowest amount of lookups? $\endgroup$ – npkllr Oct 20 at 17:13
  • 1
    $\begingroup$ @npkllr I added notes to the puzzle. $\endgroup$ – Jyotish Robin Oct 20 at 17:29
  • 1
    $\begingroup$ If you are looking for a general algorithm, then the number of lookups for a given algorithm will depend on the state of the bulbs (the input configuration). Are you looking for an algorithm with the fewest number of lookups in the worst case (i.e. among all possible valid configurations, what is the maximum number of lookups that your algorithm has to make), or do you want the best best-case solution, or the best average-case solution? $\endgroup$ – hdsdv Oct 20 at 19:15
  • $\begingroup$ Does the converse also hold true? For the given example, if 𝑎1 is OFF , then 𝑎2 and 𝑎3 are ON, 𝑎7 is OFF. $\endgroup$ – rahuljain1311 Oct 21 at 16:19
  • 1
    $\begingroup$ Finally, the OP doesn't specify whether this is a puzzle that he knows a smart answer (as is most puzzles posted on this site) or he's just asking for ideas. I would be very interested to know the answer if it is the first case, but still the question needs a bit clarification. In the second case, I'd say the question is too broad. $\endgroup$ – WhatsUp Oct 21 at 18:57
3
$\begingroup$

Since we are looking for a generic approach without knowing the exact 'rules', I would suggest the following:

1. First, assign each rule the properties $r_{cw}$ and $r_{ct}$ for the number of bulbs in the when and then clauses and then find the rule with the highest ratio $r_{ct}\over 2^{r_{cw}}$, i.e. the rule potentially giving you the most new knowledge with the fewest number of lookups taking into consideration that the chance for the when clause to be fulfilled is only $2^{r_{cw}}$. As long as we don't know anything about the bulbs, we must assume a 50/50 chance for a bulb to be on or off and the probability for $n$ bulbs to match a given condition is $1\over{2^n}$. Order the bulbs in the when clause in descending order depending on how often they occur in the other when clauses. Open the boxes for the bulbs in the when clause in this order (most used bulb first), stop as soon as a revealed bulb does not match the when clause and if all bulbs match the when clause, note the knowledge you have now gained about the bulbs in the then clause.

2. Throw away all rules, for which we based on the known bulbs can surely say that the when clause is not fulfilled. E.g. if a rule says 'If $a_1$ is on and ..., then ...' and we know that $a_1$ is off, we can ignore the rule.

3. After doing this, reevaluate the properties $r_{cw}$ and $r_{ct}$ for each remaining rule, so that only the number of unknown bulbs in each of the clauses are counted. Now, either find any rule with $r_{cw}=0$ and check if you can gain any new knowledge without opening new boxes or if no such rule exists, find yet again the rule with the highest ratio $r_{ct}\over 2^{r_{cw}}$, open the boxes in the same way as described in step 1. Repeat from step 2 until all rules have been evaluated or ignored.

4. At last, open the boxes of the still unknown bulbs to check their state.

$\endgroup$
  • 1
    $\begingroup$ That probably will not always give the most knowledge. For example, if a relationship states "if $a_1$ is on, then all 99 others are off", so the ratio will be 99 (highest possible), but if we open the $b_1$ box and discover that $a_1$ is indeed off, then we only know that at least one of 99 other bulbs is on, which rules out only 1 possibility out of $2^{99}$ (i.e. we've gained very little knowledge). $\endgroup$ – trolley813 Oct 21 at 7:34
  • $\begingroup$ @trolley813 You are at least partially right. I have changed the priority calculation to lower the priority of rules with many unknown bulbs in the when clause. Your example is however slightly off. The rules, at least the examples, are not saying "if $a_1$ is on, and only then, all 99 others are off", so if you with a rule as stated by yourself in the comment open $a_1$ and it is off, you still have no knowledge about the other 99 bulbs. They could also be all off, without violating the rule. $\endgroup$ – jarnbjo Oct 21 at 10:17
  • $\begingroup$ Sorry, it was my fault. But without "and only" (i.e. using implication instead of equivalence) this statement will be even stronger (since in the other case we would gain no knowledge at all). $\endgroup$ – trolley813 Oct 21 at 10:29
  • $\begingroup$ @trolley813 No, but it simplifies the rest of the algorithm not having to consider 'partial' knowledge. $\endgroup$ – jarnbjo Oct 21 at 10:44
  • $\begingroup$ Would it not be better to gives scores to the lights themselves? A light that occurs in several "when" clauses is much more valuable to know than a light that is used in just one. Maybe it is as simple as adding up the scores for the rules it takes part in, I don't know. $\endgroup$ – Jaap Scherphuis Oct 21 at 11:06
1
$\begingroup$

Another approach (probably somewhat different of @jarnbjo's one):

1. Open the boxes of the bulbs which are not involved in any relationship, if they are those (since you have to open them anyway).
2. For the remaining ones, build a set $S$ consisting of all possible states ($2^N$ rows, where $N$ is a number of unopened boxes, so up to $2^{100}=1267650600228229401496703205376$ rows - it's large but forget about the physical restrictions for a while, these don't matter here).
3. For each relationship, exclude from $S$ the rows for which it's false. E.g. "if $A$ then $B$" excludes rows, for which $A$ holds but not $B$.
4. Now, we end up with $S$ being the set of possible states (considering it as a table with rows being the states, and columns being numbers of bulbs/boxes).
5. Pick up the box $b_i$ which has the most balanced number of 1's and 0's in its column in $S$, e.g. $\arg\min_i{|\#_1(i, S)-\#_0(i, S)|}$, where $\#_1(i, S)$ and $\#_0(i, S)$ is the number of ones (ONs) and zeroes (OFFs) in the $i$-th column of the $S$ table, respectively, and open the box. Exclude from $S$ the non-matching states (so the rationale about this step is to exclude the largest number of possibilities even in the worst case).
6. Repeat step 5 while $|S|>1$ (cardinality of $S$ is greater then 1, i.e. until we have only one possibility).

$\endgroup$
  • $\begingroup$ If the goal is for a human to win the price, I would very much assume that the anticipated length of a human life must be considered as a 'physical restriction', which can't be ignored. $\endgroup$ – jarnbjo Oct 21 at 10:47
  • $\begingroup$ @jarnbjo Well, the puzzle is obviously set in the fantasy world, so we cannot assume that the humans is this world cannot live for millions of years and/or have computers (there is no no-computers tag in the question) which perform such computations in seconds. $\endgroup$ – trolley813 Oct 22 at 7:01
  • $\begingroup$ If your computer can check a billion sets per second, which is by several magnitudes more than realistic, a brute force approach will still take more than 40,000,000,000,000 years. No computer can do this 'in seconds'. $\endgroup$ – jarnbjo Oct 23 at 14:06
  • $\begingroup$ @jarnbjo Again, it's true only in our (real) world, since it's due to some laws of physics which limit the computation speed and efficiency, involving fundamental physical constants. In the fantasy world of the puzzle, these constants can have significantly different values (or maybe, some laws of "our" physics do not hold there at all). $\endgroup$ – trolley813 Oct 24 at 6:13
0
$\begingroup$

This seems like a relationship problem to me. I think we can try to use

(DSU) DISJOINT SET UNION here. Reference

Assumptions:

  1. There are no conflicting relationships
  2. Represent all the bulbs with 2 states. a11 means a1 bulb which is ON. Similarly a10 means a1 bulb which is OFF
  3. Converse also hold true. For the given example, if 𝑎1 is OFF , then 𝑎2 and 𝑎3 are ON, 𝑎7 is OFF
  4. Input example for going over steps:
    1. a61 -> a70, a90 -> a81
    2. a11 -> a20, a30 -> a41, a51, a61
    3. a131 -> a120 (if 13th bulb is ON, 12th would be OFF)

Steps:

  1. Let us initially create 2*100 independent sets. This would represent 2 states for each bulb, i.e. ON and OFF. So we would initialize our structure with a10, a11, .... a1001, a1000 (100th bulb)
  2. Now let us go over the relationships one by one:
    1. In the first one, we put a61, a70, a90 and a 81 in the same set. Basically we will call Union(a61, a70), Union(a61, a90), Union(a61, a81). Note that we don't need to call Union(a90, a71) or Union(a70, a81), etc. because of the DSU structure. (Think of them as putting the same set!)
    2. We need to add the opposite bulb states to our data structure as well. E.g. add to set Union(a10, a21), Union(a10, a31), Union(a10, a40), Union(a10, a50), Union(a10, a60)
    3. Continue to iterate over all the relationships and perform steps 1 and 2
  3. After processing all the relationships we would be left with a bunch of disjoint sets. Each independent of one another. If any bulb has not appeared in the relationship, say a20 then we would have 2 sets belonging to it namely, a200, a201.
  4. Now that we have all the disjoint sets, we count them. For the given example we would get 8 disjoint sets, namely:
    1. a11, a20, a30, a41, a51, a61, a70, a81, a90
    2. a10, a21, a31, a40, a50, a60, a71, a80, a91
    3. a101
    4. a100
    5. a111
    6. a110
    7. a131, a120
    8. a130, a121
  5. We only need to count one possibility out of ON and OFF for each set's state. Take for e.g. a111 and a110 . We we take in turn to check if bulb a11 is ON or OFF. So we divide the count by 2. This should be the minimum number of bulbs which we need to check.
  6. To find out which bulbs are on, we need to check one bulb from each set. That one bulb will tell us the status of the whole set.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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