tag:blogger.com,1999:blog-4115025577315673827.post534609903851979791..comments2021-01-26T19:30:37.111+05:30Comments on CSE Blog - quant, math, computer science puzzles: Gold Links PuzzlePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-4115025577315673827.post-16453816718536429692019-03-29T11:02:27.790+05:302019-03-29T11:02:27.790+05:30I somehow stumbled upon the code I wrote years ago...I somehow stumbled upon the code I wrote years ago so here they are:<br />https://github.com/jiningq/AOC/blob/master/goldlinks.jlAnonymoushttps://www.blogger.com/profile/13938038410059149506noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-32487351725585683362019-03-15T05:53:21.343+05:302019-03-15T05:53:21.343+05:30Doesn't seem like anyone has proved that 4 cut...Doesn't seem like anyone has proved that 4 cuts (or 5 pieces) is the minimum that can be achieved (although the proof isn't that hard). Suppose that it is possible to get all numbers from 1 to 23 with just four pieces. That means we get an encoding of all 23 numbers with just 4 bits (each piece corresponds to a bit and it's 0 or 1 depending on whether you give that piece to the landlady or not), which is a contradiction.Vinayakhttps://www.blogger.com/profile/10879814454563618581noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-18798880315902025482018-12-24T07:51:33.766+05:302018-12-24T07:51:33.766+05:30So, even with this case, we are making 4 cuts (not...So, even with this case, we are making 4 cuts (not 2 as you wrote). Hence, both the options below require exactly 4 cuts<br /><br />option-1) 1,2,4,8,8<br />option-2) 1,1,3,6,12Unknownhttps://www.blogger.com/profile/07937856920912235413noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-92233430692283987242018-05-26T13:57:00.796+05:302018-05-26T13:57:00.796+05:30The blog description says that this blog contains ...The blog description says that this blog contains both questions and the answers. Where are the answers?Anonymoushttps://www.blogger.com/profile/11078069660065080793noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-3344214409051401242017-03-21T09:25:13.257+05:302017-03-21T09:25:13.257+05:304 cuts need to be made, of lenght 1,2,4,8 and the ...4 cuts need to be made, of lenght 1,2,4,8 and the last peice whic will remian will be of 8 link. So he can pay for all 23 days.<br />1 - 1<br />2 - 2<br />3 - 1+2<br />4 - 4<br />5 - 1+4<br />6 - 4+2<br />7 - 4+1+2<br />8 - 8<br />9 - 8+1<br />10 - 8+2 .. and so onnehahttps://www.blogger.com/profile/07448110670840335345noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-26010240902299197242016-11-28T10:12:55.384+05:302016-11-28T10:12:55.384+05:30I think I have deleted the file already. But here&...I think I have deleted the file already. But here's the rough idea: each 'solution' is represented by a list of numbers adding up to 23. There is a function testing whether it is a legal solution, by exhausting all possible subset of this list and see if they add up to every possible number between 1 and 23. Then there is another function which exhausts all possible ways of picking two numbers and merge them into one (or intuitively, cutting the link into 23 separate pieces is a trivial solution, we are looking to see how to merge the links and get longer ones). After each proposed merge you test whether the solution is still legal and you give up the merge step if it isn't. Repeat this enough times and you will see a lot of solutions. Anonymoushttps://www.blogger.com/profile/13938038410059149506noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-36241480478688304702016-09-30T17:29:42.517+05:302016-09-30T17:29:42.517+05:30according to the question, how many links needed t...according to the question, how many links needed to be cut?<br />Its 4 as when we cut 4 links at 1,2,4 & 8 intervals from the begining we have finally 5 small chains of 1, 2, 4, 8 & 8 links in them but cut made is only 4 (i.e 4 individual links are cut down).Anonymoushttps://www.blogger.com/profile/12742827937773450846noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-52443167422711105112016-08-23T03:53:15.286+05:302016-08-23T03:53:15.286+05:30There are two cuts, each of which passes through a...There are two cuts, each of which passes through a single link. Before the cut, the link will look the letter O. After the cut, it looks like the letter C. The adjacent links can now be passed through the broken one.Anonymoushttps://www.blogger.com/profile/07389596093529234481noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-54183053166198839312016-07-31T16:32:59.309+05:302016-07-31T16:32:59.309+05:30Can you share the code for the same ?Can you share the code for the same ?Shailesh Sharmahttps://www.blogger.com/profile/02403663345421673239noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-19844932333517627812016-07-26T22:42:14.104+05:302016-07-26T22:42:14.104+05:30I wrote sort of an evolutionary algorithm to explo...I wrote sort of an evolutionary algorithm to explore more possibilities. Basically you cannot get there using 4 links since 4 digits in binary representation only get you up to 15. But 5 digits get you to 31, and that leaves some room for 23.<br />Possible 5-link solutions I found:<br />[1,2,3,5,12]<br />[1,1,3,6,12]<br />[1,2,4,7,9]<br />[1,2,2,6,12]<br />[1,2,4,5,11]<br />[1,2,3,7,10]<br />[1,2,4,8,8]<br />[1,2,3,6,11]<br />[1,2,4,4,12]<br />[1,2,4,6,10]Anonymoushttps://www.blogger.com/profile/13938038410059149506noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-35897184931815437982016-07-26T05:19:21.513+05:302016-07-26T05:19:21.513+05:30This comment has been removed by the author.Anonymoushttps://www.blogger.com/profile/13938038410059149506noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-80051867386014650352016-07-18T18:45:58.459+05:302016-07-18T18:45:58.459+05:30Didn't really understand how you are breaking ...Didn't really understand how you are breaking the chain. How are you getting "two broken links"?Alankar Jainhttps://www.blogger.com/profile/12925017021863139123noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-37332890858318803082016-07-01T20:33:24.931+05:302016-07-01T20:33:24.931+05:30You only need to cut 2 links. Specifically, if the...You only need to cut 2 links. Specifically, if the links are numbered 1,2,...,23, then cut the links numbered 4 and 11. This gives you three chains of lengths 3, 6, and 12, plus the two broken links. This is optimal, since cutting a single link does not suffice.<br /><br />Here's how this works.<br /><br />Day 1: give her a broken link. <br />Day 2: give her the second broken link. <br />Day 3: give her the 3 chain, and take back the broken links as change. <br />Days 4-5: repeat days 1 and 2. <br />Day 6: give her the 6 chain, taking back the 3 chain and two broken links as change. <br />Days 7-11: repeat days 1-5 <br />Day 12: give her the 12 chain, take back all previous pieces as change. <br />Days 13-23: repeat days 1-11.Anonymoushttps://www.blogger.com/profile/07389596093529234481noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-10448501852967084542016-06-30T14:32:20.454+05:302016-06-30T14:32:20.454+05:30Minimum links - 5. Length of each link - 1, 2, 4, ...Minimum links - 5. Length of each link - 1, 2, 4, 8, 8Saket Mishrahttps://www.blogger.com/profile/13963418777520937697noreply@blogger.com