Please solve problems every day at least on problem and upload it that's very helpfull for me and other devoloper in student level and thank you so much 😍
So, as I understand it, we can represent 1024 unique objects(wines) using 10 bits(rats). To solve this programmatically: 1) We should feed each wine to the rats in a unique combination, so that it is possible to identify the wine by seeing which combination of rats died. For example if you fed the wine numbered 10 to the 1st, 4th, 7th, 10th rats it results the string "1001001001" representing which rats were fed the wine based on the rat's position. This combination should never be used for feeding any other wine. 2) We need a Hash-map to store the relation of feeding combination string and the wine number. So in the previous example after feeding a wine we store the feeding combination string in the HashMap called feedingCombinationWineMap in the form like {"1001001001" : 10}. 3) After the feeding of all the wines is done and one hour passed we get to know which rats died. We construct a string called diedRatsString based on ,if a rat died it is 1 if not 0. So for example if 1st, 4th, 7th, 10th rats died it gives the string "1001001001". We query this diedRatsString string in the feedingCombinationWineMap to get which is poisoned wine. In this case it is 10th wine.
Hi, you understood it right! Just 1 improvement, you are able to skip the hashmap part, because you can calculate the index of the wine from the pattern. 1001001001 = 2^0+2^3+2^6+2^9 = 585. So this means the 585th wine is poisoned.
Leonard Loo thanks for the nice insight! I didn’t think this way. So the wine’s number can be converting to binary number to get the feeding pattern. The died rats binary number should be converted to decimal number to get the poisoned wine number. So no storage is required .
@Dhany Damara well instead of thinking about 1000 wines with 10 rats, you can try thinking about it for 4 wines, but only 2 rats. With 2 rats u have 2 bits, meaning u have these combinations 00 01 10 11 On the left column is rat A, on the right column is rat B, and each row represent each wine. If u feed none of the wine to rat A and rat B, and they didnt die, means wine 1 is the poisoned one. If you feed wine 2 to only rat A but not rat B, and only rat A dies, means wine 2 is poisoned. Same goes for wine 3. And if both rats dies, means its gotta be wine 4, cuz u fed both rats.
@Dhany Damara so in the 2 rats and 4 wine example. Wine 1 . Feed to none. Wine 2 : Feed to rat A Wine 3 : Feed to Rat B Wine 4 : Feed to both rats. Within 1 hour, see which rat die or didn't die, gives u the answer as to which wine is poisoned
I know a similar problems with a similar solutions. I'll apply it to this problem, with some license. This is how it works. You take the 1000 wine bottles, and divide them in 2 groups, each of 500 bottles. You choose a group, and take a drop from each bottle of this group, then put them together: this way you get a mix of the wine from half the total wine. Now, you feed the mix to the first rat. After an hour, if he lives, means one of the 500 contains poison; else, the poison is in the other 500. Repeat the procedures using the poisoned wine, dividing it in 2 groups again, mixing and feeding to the next rat. Repeat the procedure 10 times. Each step halvenes the bottles (and possibly kills a mouse). This solution takes 10 hours of waiting, while your solution takes only 1 hour (let's ignore the time to mix to handle wine and feeding mice), so yours is more efficient. An historical note: if memory serves well, the solution involving mixing was used to test a large group of people for blood infection, and was chosen to ease the detection with a small number of tests.
His binary method would take a lot less effort, and it's less wasteful. But they would all face certain death from alcohol poisoning, so I prefer our method lol
Now Joma, let's resolve this if you can: how can you do for have the time to test every combinaison if the poison's effect and the party start 1 hour after (so in the same time)? Let's assume: you can put directly the wine by a syringe in each rat AND you write each combinaison on an Excel sheet in 1s (which is very very fast, as my gf like to says every night), it will takes 16min37s, which is too much (or perfect, it depends the context). So how can you resolve this?
What if you use time identity, I mean, feed ten rats ten different wines every 2-5 mins, then u will use rat + death minute to know which wine is poisonous
This is wrong because if you tested wine number one in no rats so maybe this wine have the poison but its true about bits your right but the question is wrong so instead of the poisen you should ask how many wine we can test it on 10 rats without poison in a wine
Trick question, all the rats die from alcohol poisoning from drinking over 900 wines and not from the poison itself lol
Haha, creative solution ;)
no rat drinks more than 512wines :)
vhraz how come?
Read the question again
Please solve problems every day at least on problem and upload it that's very helpfull for me and other devoloper in student level and thank you so much 😍
So, as I understand it, we can represent 1024 unique objects(wines) using 10 bits(rats).
To solve this programmatically:
1) We should feed each wine to the rats in a unique combination, so that it is possible to identify the wine by seeing which combination of rats died. For example if you fed the wine numbered 10 to the 1st, 4th, 7th, 10th rats it results the string "1001001001" representing which rats were fed the wine based on the rat's position. This combination should never be used for feeding any other wine.
2) We need a Hash-map to store the relation of feeding combination string and the wine number. So in the previous example after feeding a wine we store the feeding combination string in the HashMap called feedingCombinationWineMap in the form like {"1001001001" : 10}.
3) After the feeding of all the wines is done and one hour passed we get to know which rats died. We construct a string called diedRatsString based on ,if a rat died it is 1 if not 0. So for example if 1st, 4th, 7th, 10th rats died it gives the string "1001001001". We query this diedRatsString string in the feedingCombinationWineMap to get which is poisoned wine. In this case it is 10th wine.
Hi, you understood it right! Just 1 improvement, you are able to skip the hashmap part, because you can calculate the index of the wine from the pattern.
1001001001 = 2^0+2^3+2^6+2^9 = 585.
So this means the 585th wine is poisoned.
Leonard Loo thanks for the nice insight! I didn’t think this way. So the wine’s number can be converting to binary number to get the feeding pattern. The died rats binary number should be converted to decimal number to get the poisoned wine number. So no storage is required .
@Dhany Damara well instead of thinking about 1000 wines with 10 rats, you can try thinking about it for 4 wines, but only 2 rats.
With 2 rats u have 2 bits, meaning u have these combinations
00
01
10
11
On the left column is rat A, on the right column is rat B, and each row represent each wine.
If u feed none of the wine to rat A and rat B, and they didnt die, means wine 1 is the poisoned one.
If you feed wine 2 to only rat A but not rat B, and only rat A dies, means wine 2 is poisoned. Same goes for wine 3.
And if both rats dies, means its gotta be wine 4, cuz u fed both rats.
@Dhany Damara so in the 2 rats and 4 wine example.
Wine 1 . Feed to none.
Wine 2 : Feed to rat A
Wine 3 : Feed to Rat B
Wine 4 : Feed to both rats.
Within 1 hour, see which rat die or didn't die, gives u the answer as to which wine is poisoned
@@DivineKage thanks this helped a lot
Wow! That's ingenious. Why couldn't I think of representing rats as bits?
These vids are awesome man!
I am so grateful to have found your channel . You are amazing . thank you so so so much for these videos.
Joma, we appreciate you so much!
This was so good!
5:31
If no rat is given any wine and no rat does, how does it imply that 1st wine is poisoned
Awesome videos bro , upload it every day
Joma, i think i will be awesome if you can show about mathematically prove from coding questions like using induction
I know a similar problems with a similar solutions. I'll apply it to this problem, with some license.
This is how it works. You take the 1000 wine bottles, and divide them in 2 groups, each of 500 bottles. You choose a group, and take a drop from each bottle of this group, then put them together: this way you get a mix of the wine from half the total wine.
Now, you feed the mix to the first rat. After an hour, if he lives, means one of the 500 contains poison; else, the poison is in the other 500.
Repeat the procedures using the poisoned wine, dividing it in 2 groups again, mixing and feeding to the next rat. Repeat the procedure 10 times. Each step halvenes the bottles (and possibly kills a mouse).
This solution takes 10 hours of waiting, while your solution takes only 1 hour (let's ignore the time to mix to handle wine and feeding mice), so yours is more efficient.
An historical note: if memory serves well, the solution involving mixing was used to test a large group of people for blood infection, and was chosen to ease the detection with a small number of tests.
but you only have exactly one hour not more.
@RawPeds your solution is logarthmic approach followed in algos such as binary seach, trees etc. I was also thinking the same lol
His binary method would take a lot less effort, and it's less wasteful. But they would all face certain death from alcohol poisoning, so I prefer our method lol
Nicely explained...
Gr8 video ;)
Pls do make a video on the Pigeonhole principle!
Is 9 or 10 tested bottles not enough for the party?
Now I get my permutations is important in Maths
ohhh I understand it!
Now Joma, let's resolve this if you can: how can you do for have the time to test every combinaison if the poison's effect and the party start 1 hour after (so in the same time)?
Let's assume: you can put directly the wine by a syringe in each rat AND you write each combinaison on an Excel sheet in 1s (which is very very fast, as my gf like to says every night), it will takes 16min37s, which is too much (or perfect, it depends the context).
So how can you resolve this?
Nice trick.. magic of combinations
⚙️⚙️⚙️⚙️⚙️⚙️⚙️⚙️⚙️⚙️
Sir can uh pls provide me the code for this question???? Before 6:45 plss
so remember, bits and bytes = rats and mice
Where is the code
wow he's a good kind of oppa
What if you use time identity, I mean, feed ten rats ten different wines every 2-5 mins, then u will use rat + death minute to know which wine is poisonous
Because the party will start the moment you're 1/10th done with your trials.
This is wrong because if you tested wine number one in no rats so maybe this wine have the poison but its true about bits your right but the question is wrong so instead of the poisen you should ask how many wine we can test it on 10 rats without poison in a wine
Make a video on binary trees. I maintain an open-source project related to them, and would love to display your video on the landing page (:
LInk it.
Niceeeeeeeeeee
More than 1 hour, 7 minutes
thank u for making me realise im dumb:D
I am the first commentor JOMA .😁😁
I'm from INDIA.
no one ask
just cancel the party
U just copy-paste rats pictures...