explain xkcd - User contributions [en]

Talk:1580: Travel Ghost

2015-09-23T18:53:55Z

162.158.92.206:

Racing Ghosts is a refference to Mario Kart [[User:ẞ qwertz|ẞ qwertz]] ([[User talk:ẞ qwertz|talk]]) 12:50, 21 September 2015 (UTC)

: This seems like a bit of a stretch to me. [[Special:Contributions/173.245.55.118|173.245.55.118]] 13:35, 21 September 2015 (UTC)

:: It's not a reference to Mario Kart specifically (lots of racing games have ghosts), but that's basically what this is doing - translating the concept of racing ghosts to the real world.--[[Special:Contributions/108.162.216.70|108.162.216.70]] 13:50, 21 September 2015 (UTC)

::: Well, there are some fitness running apps that support a ghost runner mode, so you run against your best time and get updates if you are in front or behind of your „ghost“. Without actually being able to prove it, I believe (and always assumed) this idea is actually inspired from racing games like Mario Kart. [[Special:Contributions/162.158.115.36|162.158.115.36]] 13:56, 21 September 2015 (UTC)

: Also, see https://en.wikipedia.org/wiki/Time_attack#Video_games [[User:SirKitKat|sirKitKat]] ([[User talk:SirKitKat|talk]]) 14:11, 21 September 2015 (UTC)

So in the title text, is he being replaced with the ghost who always *ahem* comes last? --[[User:SaturNine|SaturNine]] ([[User talk:SaturNine|talk]]) 12:53, 21 September 2015 (UTC)
:I agree. [[Special:Contributions/173.245.50.154|173.245.50.154]] 13:36, 21 September 2015 (UTC)
:: Women prefer men that are stuck in traffic?? [[Special:Contributions/162.158.90.235|162.158.90.235]] 19:17, 21 September 2015 (UTC)
::: Nah - just someone who takes the "scenic" route. [[Special:Contributions/108.162.215.17|108.162.215.17]] 19:50, 21 September 2015 (UTC)
:::: I love that this could be a reference to the move Ghost. Great. -[[User:Jeff|Jeff]] ([[User talk:Jeff|talk]]) 19:51, 21 September 2015 (UTC)

Is this the first time Cueballs children were shown? [[User:ẞ qwertz|ẞ qwertz]] ([[User talk:ẞ qwertz|talk]]) 17:22, 21 September 2015 (UTC)

I don't know if it's worth mentioning that this appears to be a width-first (route-)search algorithm. A memory-heavy but guaranteed 'perfect' solver of best routing, at every point of choice (from the very first, how you start the journey), all possible/practical travel options are explored (including taking a journey in the 'wrong' direction, or waiting for the non-stop train that is not the first to arrive, to take advantage of connections with faster transport links), in parallel according to the total time (or other measure of efficiency) yet taken on each iteration. Unless any 'ghost' arrives at a node that has already been visited by a 'ghost', when it need not continue. Eventually, the most efficient son-of-a-son-of-a-son...-of-a-son-of-a-ghost will reach the destination, indicating the 'correct' answer. At least within the limits of the split-and-propogate algorithm, and the amount of parallelisation available to devote to the problem. (See also the multiple-overlayed 'searches' performed by two-minutes-of-Nicholas Cage, in the near-climactic scene in {{w|Next_(2007_film)|the film 'Next' (beware spoilers!)}}.) [[Special:Contributions/141.101.99.12|141.101.99.12]] 22:38, 21 September 2015 (UTC)
:Are you aware if such an app exists in real life? I'd be interested in trying to program one (albeit with less tangible ghosts). [[User:LowHangingFruit|LowHangingFruit]] 14:19, 22 September 2015 (UTC)
:: This is an extremely easy algorithm to program (I have taught it while teaching AP (high school) computer science), however it isn't an algorithm that will likely be useful to you since it has exponential time complexity. In other words, if there are more than a trivial number of possibilities to be examined, finding the solution through this algorithm would not finish before you were dead. For those of you who are about to say that if we could run a huge bunch of these possibilities in parallel: merging the results, memory management, context switching, and similar things, even if they could be done in constant time would still mean a constant amount of time for each of an exponential set of possibilities. [[Special:Contributions/108.162.219.173|108.162.219.173]] 22:29, 22 September 2015 (UTC)tomb
::: Can anyone give me a (couple) Wikipedia articles to read, so I can understand this comment? I'm really interested. [[Special:Contributions/162.158.92.206|162.158.92.206]] 18:53, 23 September 2015 (UTC)

Will his children have half-siblings that are fathered by the ghost that has replaced him in the bedroom? Or are ghosts infertile?[[Special:Contributions/108.162.215.170|108.162.215.170]] 04:07, 22 September 2015 (UTC)

Doesn't light do this according to some theory, sending out "investigation waves / photons" to determine the quickest way to get anywhere? I'm no expert on this, just some food for thought...
[[Special:Contributions/162.158.90.249|162.158.90.249]] 11:57, 22 September 2015 (UTC)
:Not really - or at least not real. There may be some "potential photons" in some attempts to describe some quantum-based theory ... but there will certainly be no investigation photons after wave collapse. -- [[User:Hkmaly|Hkmaly]] ([[User talk:Hkmaly|talk]]) 12:12, 22 September 2015 (UTC)
::"Everything we call real is made of things that cannot be regarded as real." - Niels Bohr. (Whether or not he's ultimately right, it's an explanation.)[[Special:Contributions/141.101.99.12|141.101.99.12]] 13:48, 22 September 2015 (UTC)

If the simulations explore all travel possibilities, how long will it be until bike ghost gets run off the road by bus ghost? Or flattened by texting driver ghost? [[Special:Contributions/198.41.238.33|198.41.238.33]] 12:30, 22 September 2015 (UTC)
:This reminds me of an Android (and probably iOS) game "Does Not Commute" which takes the classic 'ghost competitor' behaviour (note: 108.162.226.149, below, that it's a common thing) and makes them solid. You run (different) 'missions'/commutes across the playing arena with a succession of new vehicles, each time finding that all your ''previous'' commutes are happening, simultaneously, creating obstacles and hazards. You can collide with (or end up being run into by) another vehicle, replaying the path you set it upon in a previous round, and this causes you to rebound. (But there's no 'kickback' when contact is made with your prior 'self', which sticks solidly to its pre-played path. Thus no need to deal with contradictions and temporal paradoxes by deflecting a past-self thus potentially changing the entire arena (for good or bad) for every other attempt you made, trying to avoid everything else.) Worth a dabble, perhaps, but don't get addicted to it! [[Special:Contributions/141.101.99.12|141.101.99.12]] 13:48, 22 September 2015 (UTC)

There's actually a very similar mechanism in the game Canvas Rider, where the best times on a track (it's a bike racing game with stick figures) can be clicked and a ghost that takes the same path with the same speed as those people appears and moves while you do. In fact, they actually look somewhat similar to the ghost in panel 4. [[Special:Contributions/108.162.226.149|108.162.226.149]] 13:17, 22 September 2015 (UTC)

I strongly suspect this also references the concept of the Oracle machine as it relates to the NP hardness of the traveling salesman problem. TSP is in the complexity class NP Complete, and part of the most common proof that it is NP hard involves showing that it reduces to a polynomial time algorithm (and hence potentially practically computed) if there exists an oracle that can tell you if a route is optimal (the fastest) in constant time. I have never edited here before and don't know all the etiquette, so I leave it to a more experienced editor to consider this in the main article. The "ghost" would then be related to the Oracle because many real world "oracles" (as in fortune tellers or weird tripping priestesses of Apollo) claim to get answers by talking to ghosts. [[Special:Contributions/108.162.219.173|108.162.219.173]] 22:17, 22 September 2015 (UTC) tomb

342: 1337: Part 2

2015-09-16T04:51:26Z

162.158.92.206: /* Explanation */

{{comic
| number = 342
| date = November 13, 2007
| title = 1337: Part 2
| image = 1337 part 2.png
| titletext = Trivia: Elaine is actually her middle name.
}}

==Explanation==
"Like a ring in a bell" appears to be a reference to the {{w|Chuck Berry}} song {{w|Johnny B. Goode}}, in which Berry describes a young boy (like himself) who becomes a guitar-playing prodigy. Apparently, Elaine learned to program as quickly, easily, and skillfully as Johnny (and Chuck) learned to play rock 'n' roll.
{{w|Donald Knuth}} is a computer science Professor Emeritus at {{w|Stanford University}} who is famous for writing {{w|The Art of Computer Programming}} and developing the TeX computerized typesetting system. He may not have a mountain hideaway {{Citation needed}} (a reference to ''{{w|Kill Bill}}'', by the way), but he would be one of the best mentors a budding hacker could have.

The {{w|A* search algorithm}} and {{w|Dijkstra's algorithm}} are {{w|Graph traversal|graph search}} {{w|algorithm}}s. And what study of algorithms would be complete without a healthy study about finding complexities? {{w|Computational complexity theory|Time complexity}} is the amount of time an algorithm takes to execute. Upper and lower bounds for complexity is written in {{w|Big O notation}}. Best possible execution of an algorithm is constant time, or O(1), said in words, for any given data set no matter how large the algorithm will always return the answer in the same time. However, constant time is extremely difficult to achieve; linear time (O(n)) is also very good. For more complex algorithms, [http://www.wolframalpha.com/input/?i=plot+x*log%28x%29 O( n*log(n) )] is good, but [http://www.wolframalpha.com/input/?i=plot+x*log%28log%28x%29%29 O( n*log(log(n)) )] is better. (Note that logarithms in different bases are proportional to each other. So this would hold true for any base >1.)

From the evidence that [[Mrs. Roberts]] has two children, a daughter named [[Elaine Roberts|Elaine]], and a younger son named Bobby (presumably [[Little Bobby Tables|Robert]]'); DROP TABLE students;--), we can assume that she is the same mother from [[327: Exploits of a Mom]]. Of course, the title text here explains that Elaine is only her middle name. In [[327]] we learned her first name is "Help I'm trapped in a driver's license factory". Mrs. Roberts appears to have had fun naming her children.

All comics in "[[:Category:1337|1337]]" series:
*[[341: 1337: Part 1]]
*342: 1337: Part 2 (this one)
*[[343: 1337: Part 3]]
*[[344: 1337: Part 4]]
*[[345: 1337: Part 5]]

This series was released on 5 consecutive days (Monday-Friday) and not over the usual Monday/Wednesday/Friday schedule.

==Transcript==
:[Cueball standing near a friend, who is on the floor near the armchair.]
:Friend: So the greatest hacker of our era is a cookie-baking mom?
:Cueball: Second-greatest.
:Friend: Oh?

:[A young Elaine with a ponytail is laying on the floor looking at the screen of a computer that appears to have been pieced together. A younger Bobby is finger painting at an easel.]
:Mrs. Roberts had two children. Her son, Bobby, was never much for computers, but her daughter Elaine took to them like a ring in the bell.

:[The back of a car is in frame. Mrs. Roberts is waving goodbye to her daughter who is wearing a backpack and is holding a walking stick. She is about to begin climbing a staircase built into a mountain.]
:When Elaine turned 11, her mother sent her to train under Donald Knuth in his mountain hideaway.

:[Donald Knuth is standing with a pointing stick at a chalk board with graph traversal patterns on it.]
:For four years she studied algorithms.
:Knuth: Child—

:[Knuth whips around slashing the stick like a sword. Elaine jumps and lands on the stick.]
:Knuth: Why is A* search wrong in this situation?
:''swish''
:Elaine: Memory usage!
:Knuth: What would you use?
:Elaine: Dijkstra's algorithm!

:[They are outside both working on a chalkboard with a separator down the middle so they cannot look at each other's work. Elaine is no longer wearing her hair in a ponytail.]
:Until one day she bested her master
:Knuth: So our lower bound here is O(n log n)
:Elaine: Nope. Got it in O(n log (log n))
:And left.

==Trivia==
*In this [http://www.youtube.com/watch?v=zJOS0sV2a24#t=21m30s Google-speech] Donald Knuth personally asked [[Randall]] what his ''n*log(log(n))'' algorithm for searching was, and Randall referred him to Elaine.

{{comic discussion}}
[[Category:Comics featuring Cueball]]
[[Category:Comics featuring Elaine Roberts]]
[[Category:Comics featuring Mrs. Roberts]]
[[Category:Comics featuring Little Bobby Tables]]
[[Category:Comics featuring Donald Knuth]]
[[Category:1337|02]]