Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Anime fans stumbled upon a mathematical proof

scientificamerican.com

Post reply on HN
Print view View original

221–230 of 255 posts

Re: Anime fans stumbled upon a mathematical proof

#221

Post by robinhouston »

throwaway37725 wrote: post #220
robinhouston wrote: post #204

Earlier quoted context omitted.

I fear I'm responsible for this misconception. At first we didn't realise the proof had originated on 4chan – Nathaniel Johnston originally found the proof on Wikia, and the 4chan archive was only discovered later. When I tweeted about it, I said “The best known lower bound for the minimal length of superpermutations was proved by an anonymous user of a wiki mainly devoted to anime.”, by which I meant Wikia (which wa…

>At first we didn't realise the proof had originated on 4chan – Nathaniel Johnston originally found the proof on Wikia >by an anonymous user of a wiki mainly devoted to anime.”, by which I meant Wikia (which was pretty anime-centric at the time). The Wikia in question is the official 4chan /sci/ Wikia.

I know. My description was aimed at people who had never heard of Wikia, and certainly didn't understand its substructure. But I realise it sounds wrong to people like you who do understand that, and I wish I'd worded it more carefully.

Re: Anime fans stumbled upon a mathematical proof

#222

Post by trothamel »

Maken wrote: post #199
endless8 wrote: post #130

Earlier quoted context omitted.

They also close with an example for Harui's show and earlier try to explain its premise too... Completely ignoring the fact that fans don't care to watch the whole show in any order, but only the "Endless 8", the 8 episodes actually stuck in a time loop. And even making an example out of 8 episodes would be stupid, as the 8th episode in the Endless is meant to be the very final piece of the loop. It's arguable for th…

The entire Haruhi series is famously randomly scrambled, so neither it's airing order nor their episode number follow the chronological order of events.

It's been a while since I saw it, but from what I remember the original airing was fairly intelligently scrambled. You have a spine of episodes that consist of the original light novel, which occur in the same order they did in that book. This introduces the characters and the main plot, and ends in a climax that has to be at the end.

You then have a series of one-shot stories from the books (and one original episode contributed by the creator of Full Metal Panic!) that get scattered throughout, as there wasn't enough content for a full season, and it would be weird to have the climax occur mid-season.

Re: Anime fans stumbled upon a mathematical proof

#223

Post by genewitch »

lupire wrote: post #213
genewitch wrote: post #142

Earlier quoted context omitted.

You know Ford/Lincoln had those buttons / touch strip in the door with the buttons labelled like [1|2] [3|4], and so on to [9|0]? There's a permutation list claimed to be the shortest that I used to carry in my PDA to impress friends that had one of those sorts of cars. If I recall, it was guaranteed to open the door in something like 32 button presses, but it may have been less. It was because there was no "start" o…

3+5 4 3 2=123, so 4 digit code would require at least 134 key presses. Even 3 digit code would require over 60 keypresses. We're there other constraints on valid codes? Did the door unlock in a valid non-consecutive* subsequence like 3,4,5,0,6?

No, but it would unlock with 3355 or 3455 or 3365 or 4466 or

there's 5 buttons, and the code is four of those 5 in an arbitrary order. at least to my memory. it could have been 5 buttons in an arbitrary order. It's been 20 years!

5 pick 4 = 120, so that's an upper bound for my recollection. I remember it being fewer than that, but the original "paper" was a sheet of graph paper that had been scanned, i just transcribed it to my palm pilot.

oh. It isn't 120 * 4 keypresses. Because the thing that decided if the code was valid didn't have start/stop/reset states, so 1234523413452 would trigger 1234, 2345, 3452, 4523, 5234, 2341, 3413, 4134, 1345, and 3452. that would take "40 keypresses" in the OP "game", whereas it only takes 13 keypresses on these code pads.

so the paper was "an" shortest permutation that covered every possible combination.

edit: python gave a 625 keypress answer, i replied to a sibling with the full list of numbers.

Re: Anime fans stumbled upon a mathematical proof

#224

Post by phkahler »

I played around with a related problem - find the shortest string containing every binary number of length n. There are 2^n substrings, and I seem to recall being able to to do it in 2^n + n - 1 bits. In other words, perfect overlap was possible at least up to n=10.

I was interested in this because it's an optimal way to plot Julia sets by running the iteration backward and choosing one or the other square root. To visit all parts of the outline you'd want to apply every sequence of root selection (positive or negative) up to some length. Doing it at random is cool, but for a fixed number of points you want one of these sequences.

Re: Anime fans stumbled upon a mathematical proof

#225

Post by Biganon »

Cthulhu_ wrote: post #183
bntyhntr wrote: post #39

At one of my old jobs, the bathroom was locked with a 4 digit code followed by the key symbol. We jokingly made up "Bathroom Code" as an interview question/to nerd snipe each other instead of working, which was "assuming you don't have to press key, and that the bathroom door will unlock if the correct 4 digits are entered in order at any time, write the code to print the shortest possible test sequence to guarantee…

I'm no mathematician or leetcode expert and probably don't understand "shortest possible test sequence", but it sounds like this is just bruteforcing 0000-9999. You can't guess what would be closer to the correct solution, so at best I'd propose making a list of choices and randomizing the tries in case you get lucky. It's different if the keypad gives an indication that one number is correct though, then it'll be 40…

Have you read the article we're commenting on? Obviously mathematicians know that n! * k, with k the length of the code, would work. The idea is to superpose the end of a code with the start of the next, so you don't have to test nearly as many combinations.

Re: Anime fans stumbled upon a mathematical proof

#226

Post by genewitch »

windward wrote: post #216
genewitch wrote: post #142

Earlier quoted context omitted.

You know Ford/Lincoln had those buttons / touch strip in the door with the buttons labelled like [1|2] [3|4], and so on to [9|0]? There's a permutation list claimed to be the shortest that I used to carry in my PDA to impress friends that had one of those sorts of cars. If I recall, it was guaranteed to open the door in something like 32 button presses, but it may have been less. It was because there was no "start" o…

Is this a mean trick to snipe HN users into thinking about algorithms for hours? I have a friend who wants to know.

python assures me this is a valid solution:

>111211131114111511221123112411251132113311341135114211431144114511521153115411551212131214121512221223122412251232123312341235124212431244124512521253125412551313141315132213231324132513321333133413351342134313441345135213531354135514141514221423142414251432143314341435144214431444144514521453145414551515221523152415251532153315341535154215431544154515521553155415552222322242225223322342235224322442245225322542255232324232523332334233523432344234523532354235524242524332434243524432444244524532454245525253325342535254325442545255325542555333343335334433453354335534343534443445345434553535443545355435554444544554545555

625(?) presses, i was way off. :-( It's still a lot fewer than trying all 10,000 individual 4 digit possibilities that the keypad implies are there.

Also this is possibly not the shortest, according to some sibling comments to mine, above. This could be the upper bound?

Re: Anime fans stumbled upon a mathematical proof

#227

Post by yifanl »

swarnie wrote: post #195
VVilhelmsen wrote: post #186

Earlier quoted context omitted.

Indeed. I would even dare to say most of /sci/ don't want to be associated with anime at all.

Unlike sites like Reddit where an overarching hivemind will dominate the entire site to the point where your cooking, gardening and Reality TV subs will all contain American politics for some ungodly reason, 4chan still seems to be siloed in to specifically focused communities. Ignore /b/, /pol/, r9k and all the weeb stuff and you can find some properly good communities which remind me of the old internet. /sci/, /mu…

I can very confidently state /biz/ does not have its moments.

Re: Anime fans stumbled upon a mathematical proof

#230

Post by [deleted] »

swarnie wrote: post #195
VVilhelmsen wrote: post #186

Earlier quoted context omitted.

Indeed. I would even dare to say most of /sci/ don't want to be associated with anime at all.

Unlike sites like Reddit where an overarching hivemind will dominate the entire site to the point where your cooking, gardening and Reality TV subs will all contain American politics for some ungodly reason, 4chan still seems to be siloed in to specifically focused communities. Ignore /b/, /pol/, r9k and all the weeb stuff and you can find some properly good communities which remind me of the old internet. /sci/, /mu…

[deleted]
Post reply on HN