10 ms·
Hello, World
- tempodox 11y ago... Obama [...] became the first president to write a line of code ... Wasn't the Dictator of Singapore earlier with his Sudoku? This is a ridiculous stunt, and it sets the wrong accents. Coding is being hyped while the people who actually keep us alive and in good condition work 3 jobs and can't afford health insurance. Meantime, Obama destroys the Constitution and betrays the People of the U.S. to the NSA and their ilk like none did before. I think I'm getting sick.
- eru 11y agoYou mean the PM of Singapore? Anyway, they are obviously referring to POTUS's only. (You can bet eg Dr Angela Merkel wrote some code in her time as well.)
- alexashka 11y agoIf the answer is 'at least one of them always write down "heads or tails"', then lol
- alexashka 11y agoI had assumed there was no real solution and figured it being a clever semantic play. I stand corrected, very nice puzzle :)
- SMackinnon 11y agoSpoiler: Bob always chooses the same as his flip, Alice always chooses the opposite of her flip. B A H H - Bob chooses heads, Win H T - Alice chooses heads, Win T H - Alice chooses tails, Win T T - Bob chooses tails, Win
- sdab 11y agoYep, its a nice problem. Reformulating it such that there are two possibilites (the coins are either different or the same) rather than four (permutations of two coins) is the way to solve the problem. I was going to post a hint rather than the solution, but you beat me to the punch.
- SMackinnon 11y agoYeah, added a little spoiler tag.
- placeybordeaux 11y agoI liked showing the four possibilities and thinking about it in the way that one of them has to be responsible for winning in each case.
- furyofantares 11y agoMy experience arriving at this solution made me a bit curious as to how others solved it. Was there reasoning involved before you arrived at a strategy and verified it, or did the strategy just come to you? Did you try multiple strategies, and if so, was there a method to generating/iterating on them, or were they just coming to you and you tried them?
- callahad 11y agoMy thought process: It seemed obvious that fixed-guess strategies couldn't work, both from the proof in the article and from intuition that the inverse of your fixed guesses will always represent a failure case. If a fixed strategy can't work, then the guesses must be decided dynamically. At the time the guess is made, only one bit of information (their own flip) is available to each participant, so each guess has to be based on that. With one bit of information, you could only choose two things: do the same, or do the inverse. The correct, asymmetric pair of strategies popped into my head at this point, and a quick truth table check confirmed it.
- bsaul 11y agoExact same here. Thanks for analysing this though, because i had trouble rethinking my own process. I more had the feeling to try things a bit randomly and eliminate ranges of similar choices. But in fact it wasn't random, it did follow the exact train of thoughts you described, in that order.
- Rangi42 11y agoI made a table of all four possibilities: A_coin B_coin A_guess B_guess H H ? ? H T ? ? T H ? ? T T ? ? Then I tried to fill in the guesses, given that A_guess has to be based on B_coin and vice-versa. After making Alice guess the same as her coin flip, since that's a simple thing to try first, it was clear that Bob had to guess the opposite of his coin flip for each row to have exactly one correct match.
- SMackinnon 11y ago
- deleted 11y ago[deleted]
- kolodny 11y agoAnother way to look at it is either they can both get the same result or they can get different results, if it's the same then Bob will be correct, if it's different then Alice will be correct
- JoshTriplett 11y agoAnd to show how to logically work out this answer (same spoiler warning applies): I started with a truth table as well. It's pretty easy to show that if Alice (or without loss of generality Bob) uses a fixed "always guess H" or "always guess T" strategy, that wins in two cases, but in the other two cases Bob has no way to reliably win. For instance, if Alice always guesses H, then two cases become wins: A B H H W H T ? T H W T T ? But in the other two cases, Bob has the same T each time, so he doesn't have enough information to distinguish those cases, and thus he can't reliably guess correctly. So Alice needs to use a strategy that depends on her flip. There are only two such strategies that don't trivially reduce to a constant guess: guess what you flip or guess the opposite of what you flip. Going with the former, where Alice guesses what she flips: A B H H W H T ? T H ? T T W From this, clearly if Bob guesses the opposite of what he flips, someone wins in all four cases. The only other solution is to reverse the two: Alice guesses the opposite of what she flips, and Bob guesses what he flips. This seems like a nice warm-up for other protocols that depend on agreed-upon strategy but not a secure channel for direct communication, such as Diffie Hellman or the Socialist Millionare Problem.
- gamekathu 11y agohowever, if the puzzle is changed from 'either one or both their guesses are correct they win' to 'both their guesses should be correct to win', then the solution becomes tough!
- ColinDabritz 11y agoIt helped me to think of it this way: Alice is guessing that their coins are different (one possibility) and Bob is guessing that their coins are the same (the other possibility), so from either direction they are covered.
- yukinon 11y agoThanks. I think this was the reply that actually helped me understand this.
- imdsm 11y agoYeah it still took a minute. The way I realised it was Bob is covering them for the same flips, so if he flips H, he covers if Alice flips a H too. But if she flips a T, Bob is no longer covering her, but she knows when Bob isn't covering her, if she guesses for the opposite, she'll cover them. 100%. The next level is: Eve joins the game, and the coin gets another side.
- TheSoftwareGuy 11y agoYes, the intuitive way to think of it could be that the coins will either be the same (bob gets it right) or they will be different (alice gets it right)
- lucio 11y agoJust a comment: They'll had always a win, by sacrificing the possibility of both of them guessing right.
- Toenex 11y agoThank you Professor Falkener. Now how about Alice and Bob play Global Thermonuclear War?
- deleted 11y ago[deleted]
- yorkyorkyork 11y agoEasier explenation There are 16 possibilities A Alice's coin Ac Alice's choice B Ben's coin Bc Ben's choice They win if A's and Bc's OR B's and Ac's are the same A Ac B Bc T T T T W H T T T W T H T T W H H T T L T T H T W H T H T L T H H T W H H H T W T T T H W H T T H W T H T H L H H T H W T T H H L H T H H W T H H H W H H H H W It's easier to check for when they are losing: A Ac B Bc H H T T |they both stick to their choices H T H T |they both flip T H T H |they both flip T T H H |they stick So the winning strategy is if one of them sticks to his choice and other flips it's choice.
- darkonmist 11y agoWow, that is way better explanation to check on where they may lose. Thanks!
- JadeNB 11y agoDownvoted because I don't think this should be at the top of the discussion. I always read comments first, especially with a title like "Hello, World" that doesn't give any clue about the content; and now I don't get a chance to think about this puzzle because the spoiler was the first thing I saw. EDIT: To be clear, I am not downvoting because I think that this comment is unconstructive; clearly it is a useful contribution. At least as good as, and probably better than, having it appear later would be having more whitespace between the spoiler warning and the actual spoiler.
- est 11y agoThis is off topic, but when the next president takes office, all of current whitehouse.gov content will be gone and replaced, no?
- trvr 11y agoI'm guessing they will do something similar to when Obama took office: http://georgewbush-whitehouse.archives.gov/ http://georgewbush-whitehouse.archives.gov/
- chx 11y agoI am not sure what will happen to https://petitions.whitehouse.gov/ https://petitions.whitehouse.gov/ -- can you imagine that just wiped off?
- pipermerriam 11y agofun. https://gist.github.com/pipermerriam/d1b5a24230f2f9ec4446 https://gist.github.com/pipermerriam/d1b5a24230f2f9ec4446
- deleted 11y ago[deleted]
- anishathalye 11y agoslightly less verbose: https://gist.github.com/1751cebe44d88dc7db15 https://gist.github.com/1751cebe44d88dc7db15
- chronial 11y agoslightly less Haskell :) https://gist.github.com/Chronial/e091dc5deb9234a2a7a1 https://gist.github.com/Chronial/e091dc5deb9234a2a7a1
- markcerqueira 11y agoBut slightly more Haskell... ;)
- tmhedberg 11y ago`zip toss toss` only produces 2 of the possible outcomes. Try `liftA2 (,) toss toss` instead.
- Veedrac 11y agoThere's always [(a, b) | a <- toss, b <- toss]. It's not as Haskell-y, but it's simpler.
- startupfounder 11y ago> The puzzle is this: Can you think of a strategy Alice and Bob can use that is guaranteed to win every time? Raise campaign finance from the wealthy so that they can make it past the lesterland election[0]. Now that you have a war chest and are in the general election you just need to raise more capital from the 0.1%, buy more advertising, hire the best staff in Washington and bam! I know this is not the coding question at hand, but a more important question on how unequal our political system is and I couldn't forgo the opportunity to ever so gently show the obvious reality - once you past the lesterland wealthy elite and get their backing, winning is only a matter of time. [0] http://lesterland.lessig.org/ http://lesterland.lessig.org/
- happyscrappy 11y agoIf Lessig's theory is correct then how in the world is pot being legalized?
- rjtobin 11y agoSome discrete mathematicians are interested in this sort of problem, which they call "simultaneous hat guessing". There are quite a few papers, in case anyone is interested and unfamiliar with this sort of thing. Another fun problem, probably better known, is sequential hat guessing: take 100 people in a line, arranged so that each person can see everyone in front of them, but no-one can see any of the people behind them. Everyone is given either a red or black hat to wear, but no one can see the color of their own hat, or the hat of anyone behind them. So the person at the back of the line can see everyone's hat but their own, the next person can see everyone's hat except the first person and their own, etc. Now starting with the back of the line, each person is asked to publicly guess the color of their hat. The participants are allowed to agree upon a strategy, how many people can they guarantee guess correctly? Things get crazy if you allow an infinite countable line of people, and put ear-muffs on anyone so that no one gets to hear anyone else's guess. Surprisingly, you can still save almost everyone (if you allow the axiom of choice).
- d0m 11y agoYes, this is a great one. Unless I'm mistaken, the best strategy has potentially one error, but all the rest would get it right, yes?
- rjtobin 11y agothat's exactly it
- judk 11y agoThe solution requires infinite memory (not just arbitrary finite memory, but an actual, non-compressible infinite value) which is of course impossible in reality. Usually problems on "countable" structures need only finite memory (to process infinite streaming input), so this problem is rather misleading.
- praptak 11y agoAn actual fun problem: 100 prisoners are each assigned a black or white hat, at random. As always, they cannot communicate after the hats are assigned. Then they are shown each other. None sees own hat, everyone sees everyone elses hat. Then they are led into separate rooms and each guesses their own hat color. They win only if everybody guesses correctly. What strategy maximizes the probability of that event?
- gigias 11y agoIt seems too simple to be right, but can Bob just say heads all the time, and Alice say tails all the time?
- lobe 11y agoNo, there are two different coins. So if Bob flipped heads (which Alice guessed tails for) then they lose.
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- bandrami 11y agoFrom the first link: I find it difficult to believe that in the entirity of Jimmy Carter's Navy career, he wrote zero lines of code.
- waterlesscloud 11y agoConsidering he left the Navy in 1953, I find it easy to believe. I wouldn't be shocked if W had written some excel macros, though. Even less so if Romney had.
- protomyth 11y agoMight be close, 1953 was the year of his discharge, so he might not have written anything.
- cheapsteak 11y agoJimmy Carter aside, what kind of code do navy people write?
- jebblue 11y agoDuring Carter's era or today. In 90 I was trained for a year in computer engineering for our sonar computer mainframe including Assembly. The idea was that if we were on deployment and a bug caused a problem we could potentially figure it out and maybe fix it without stopping the mission. I was programming on my own for 8 years prior to that as a hobby so was actually correcting the instructor on a couple of occasions. There is also the rate DT which does programming all the time I think. I wanted to get into that rate but the wait was a year and I was impatient.
- __z 11y agohttp://en.wikipedia.org/wiki/Grace_Hopper#World_War_II http://en.wikipedia.org/wiki/Grace_Hopper#World_War_II
- JacobEdelman 11y agoBonus points: What if only one of them gets a coin to flip and then they must both come to an agreement on what the result was. They can talk but the NSA overhears everything they say and can crack every cipher they use. Can you maximize the chance that the NSA can't guess who got that coin AND Alice and Bob agree on the correct result? Note: An open problem. You can look up cryptogenography for current results.
- pokstad 11y agoReminds me of Dr Ebert's hat problem: http://web.csulb.edu/~tebert/hatProblem/nyTimes.htm http://web.csulb.edu/~tebert/hatProblem/nyTimes.htm
- javert 11y agoI have zero respect for someone who would take a role like that.
- hkmurakami 11y agoSo you have no respect for a researcher who took rhe stand against Microsoft in the Microsoft antitrust case?
- javert 11y agoAbsolutely. That makes him even worse. "Antitrust" is a bogus concept. It is never and was never in the public interest. It is also a massive violation of the rights of companies and their shareholders. Consider that if Windows/IE were really that bad, people would have just switched more readily to a Microsoft competitor. Desktop-quality Linux would have come about/come about sooner, or something equivalent. This is an example of the point that there is no such thing as a monopoly unless it's created through legal channels (i.e. is granted by the government). There is no business that can't be competed against with sufficient capital. And the global economy accumulates spare capital over time (because in the net, the species produces more than it consumes). Even "natural monopolies" are a function of a mistaken way to implement property rights, as opposed to being "natural." Because you can always build underneath or around whatever is already there. edit: This is a serious intellectual comment that deserves to be read. It also matters a lot for our industry. Consider Google in Europe right now.
- mappu 11y agoMost "free" markets don't have perfect competition, nor perfect information, nor rational actors. It's possible for Microsoft to provide a terrible service and for no better competitors to emerge. Consider last-mile telephone lines. It's wasteful to have ten companies each spend billions of dollars digging up the same roads to lay the same cables - and it's a nearly-impossible barrier to entry for new competitors. Sure, anything is possible with "sufficient capital", but fundamentally it's an inefficient waste of time and investor money to recreate a service that already exists, and the investors will be correspondingly scarce. Most countries have enacted legislation enforcing fairly shared use of such lines (breaking up monopolies in the process) because cooperation is fundamentally more efficient than competition as effort is not wasted in duplication. As a result, the ISP/telco market in civilized countries has since escaped from that stagnant local maxima with its high barrier-of-entry, to a more agile, more competitive state where smaller players have a fair chance of competing. I'm not sure if this includes the USA though (c.f. Comcast/TWC merger complaints, single-ISP areas, the "Worst company in america" award, unending complaints on /r/technology &c).
- idohealth 11y agoCan't Alice just always pick heads, and Bob always pick tales?
- halter73 11y agoThis fails if Alice flips heads and Bob flips tails.
- namelezz 11y agoOne writes down what s/he sees. The other writes down what s/he does not see.
- JacobEdelman 11y agoSo, "a paper" and "a gigantic ostrich juggling American Space Kangaroo"?
- namelezz 11y agoLOL. Good one!
- pelario 11y ago"Coding is exciting: you can decide what is supposed to happen, and the computer will do it…the only limit is your skill and imagination!" Someone didn't learn about the halting problem :-)
- noreasonw 11y agoI solved (believe) the puzzle in 3 minutes. A says B result is the same as A result. B says A result is different from B result, so that A covers (H,H) and (T,T), B covers (H,T) and (T, H), so always A or B is true, so they always win.
- thewarrior 11y agoI haven't looked at any of the solutions. Or any of the other comments.So at the risk of posting a redundant comment : Alice guesses that Bob's coin is the same as hers. Bob guesses that Alice's coin is the opposite to hers. It's fairly straightforward. I'd like to know the computer science angle to this though. EDIT: From the computer science that I know : We need to find an invariant that all permutations of coin flips always satisify. Intuition tells us that Alice's coin might be the same as Bob or vice versa : If you construct a truth table : Alice Bob Alice's Coin same as bob Bob's opposite to Alice H H YES NO T T YES NO H T NO YES T H NO YES The expression : Alice's coin same as Bob || Bob's opposite to Alice Always evaluates to true. So Alice can guess her flip and Bob can guess the opposite. But what if we had Alice , Bob and George and atleast one of them had to get the other two right ? Is there a general pattern ? Alice Bob George H H H H H T H T H H T T T H H T H T T T H T T T Will try and figure it out over dinner :D .
- giltleaf 11y agoI think I was slow coming up with this, but basically I wrote a lot of tables out and came up with...SPOILER... Alice always guessing the same as what she flips and Bob always guessing different. But - my question is this: Are there any other possible solutions to this puzzle? Either way, I'm pretty sure this is just an Illuminati code plot from the White House to find the world's top coders and recruit them into some CIA program.
- mmcclellan 11y agoJust adding the Python test I used: https://gist.github.com/mmcclellan/4b01bf781393395526e3 https://gist.github.com/mmcclellan/4b01bf781393395526e3
- titanomachy 11y agoOK, we get it, most HN readers were able to solve the puzzle in a minute or two. Most of us have done interview problems much more difficult. I'm more interested to know what people think about Obama's proselytizing of computer science. It seems like a great move to me. Is he going about this in a smart way? Do you think he'll get the results that he's looking for?