13
\$\begingroup\$

Today's XKCD is a sports-tournament style bracket, where the contestants are well-known names, put into groups of possibly confusing names.

Give the probability that a given contestant will win the entire tournament, based on each contestant in a given round having an equal chance of winning that round.

Input

The name of a contestant.

  • XKCD likes to use all upper case, but you may use whatever case makes sense for you or make your input case insensitive.
  • You may assume all input names are valid.
  • Jeff Gordan is probably a misspelling of Jeff Gordon. You may choose to accept either or both of these.
  • Some names include punctuation, e.g. H. G. Wells and Joseph Gordon-Levitt. You may choose to accept names with or without punctuation (or both). The above without punctuation would be H G Wells and Joseph Gordon Levitt
  • Similarly, you may choose to accept either Beyoncé or Beyonce or both
  • The Mister/Fred Astaire/Rogers line is a bit odd. For this one, you must accept all of the following: Fred Rogers, Mister Rogers and Fred Astaire

Output

The probability of the given contestant winning the whole tournament, in rational form (e.g. 1/64)

Examples

  • Louis Armstrong will potentially play in 6 rounds, each with two contestants, so he has a 1/64 chance of winning.
  • Alan Rickman will potentially play in 7 rounds, the first with 3 contestants and the rest with 2 contestants, so he has a 1/192 chance of winning.

To save you the effort of typing in all the names from the image, explainXKCD already has them tabulated. I've also dumped them to this pastebin.

Note the winning probabilities in the explainXKCD are wrong - they are twice as big as they should be because they are presumably forgetting the final round. Thanks for pointing this out @Geobits.

\$\endgroup\$
  • \$\begingroup\$ so we have to first convert the image into text and then hardcode probability buckets .. ughh \$\endgroup\$ – Optimizer May 26 '15 at 16:34
  • 2
    \$\begingroup\$ @Optimizer explainxkcd can help you with that \$\endgroup\$ – Martin Ender May 26 '15 at 16:47
  • \$\begingroup\$ @MartinBüttner That's dope \$\endgroup\$ – Optimizer May 26 '15 at 16:48
  • \$\begingroup\$ @Optimizer no image conversion required :) \$\endgroup\$ – Digital Trauma May 26 '15 at 16:51
  • 4
    \$\begingroup\$ explainxkcd is a wiki; why fix it with a note in the spec when you could fix it for everyone? :P \$\endgroup\$ – undergroundmonorail May 26 '15 at 20:07
6
\$\begingroup\$

CJam, 161 bytes

1'/l_"FRE"#\_'É#)\2b626%536%"òazíF­.?§·»ùßóÿ÷ýÿÿ»×ï_ÿÿ¿ß÷ä¿ûïÿÏÅÿ¿ÿÿ~ÿþÿýó½ïÿþþ/ïþÿ®þü¾ùÿ®÷/"256b2b2*<1-,"ãÍÕý*ÔÞ)ð^sV? Ìöî²\ÅlÕáS{Á"260b5b=5,Z6t=2+1\?4?32*

This is a full program that expects uppercase input, with punctuation and accents exactly as shown in the pastebin.

Try it online in the CJam interpreter.

How it works

1'/      e# Push a 1 and a slash.
l        e# Read a line of input from STDIN.
_"FRE"#  e# Push 0 if the input starts with "FRE" and a truthy value otherwise.
\_'É#)   e# Push 1 if the input doesn't contain "É" and a falsy value otherwise.

         e# Now we hash the input:
\2b      e#     Apply base 2 conversion to turn the input into an integer.
626%536% e#     Take that integer modulo 626, then modulo 536.

"òazíF­.?§·»ùßóÿ÷ýÿÿ»×ï_ÿÿ¿ß÷ä¿ûïÿÏÅÿ¿ÿÿ~ÿþÿýó½ïÿþþ/ïþÿ®þü¾ùÿ®÷/"256b2b2*

         e# Convert the string from base 256 to base 2 and repeat it.
         e# The resulting array, [1 1 1 1 0 0 1 0 0 ...], contains a 0 at index X
         e# if and only if there is a possible input with hash X.

<        e# Keep the binary values before the index of the input hash.
<1-,     e# Count the number of zeroes.

"ãÍÕý*ÔÞ)ð^sV?  Ìöî²\ÅlÕáS{Á"260b5b

         e# Convert the string from base 260 to base 5.
         e# The resulting array, [2 2 2 2 2 0 4 4 0 0 ...], contains a diffrent
         e# integer for every different probability. The input with the lowest hash
         e# corresponds to the first index, the one with the highest to the last.

=        e# Retrieve the integer corresponding to the input.
5,Z6t=   e# Retrieve the corresponding element from [0 1 2 6 4].
2+       e# Add two.
1\?      e# Select the result from above or 1 for BEYONCÉ.
4?       e# Select the result from above or 4 for and FRED.
32*      e# Multiply by 32.
\$\endgroup\$
  • \$\begingroup\$ I've taken the probabilities from explainxkcd (multiplied by 2) and filled in the gaps. Hopefully, everything is correct. Fixing any probability should not have an impact on the byte count. \$\endgroup\$ – Dennis May 27 '15 at 4:09

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.