7 ms·
Inverse Fizzbuzz
- jgmmo 14y agoAnyone else sick of Shipper?
- noahc 14y agoNo, pretty soon we'll see WWSD t-shirts and wrist bands. I think this is a net win for HN!
- JoachimSchipper 14y agoTo the best of my knowledge, he's just popular - I certainly haven't seem him put his name everywhere. Let's be nice to him.
- dxbydt 14y agoMemes are fun. I have a whole series of posts planned around Shipper if this one takes off. Shipper takes on contravariance. A Ship in a Minkowski space. Shipper and the options monster. A suboptimal algorithm to Ship Shipper around the seven bridges of Konisgberg. All in legit Scala, with just a trace of math to throw you off the scent.
- peter_l_downs 14y agoNot sick of it, but if I were him I'd feel sort of creeped out.
- dxbydt 14y agoDude. I cleared it with him before I posted it. "Very funny (and an interesting post). Go ahead! also definitely let me know when it's "public" i'd like to tweet it out" - Dan Shipper.
- peter_l_downs 14y agoGood to hear! I do also know that I'm not Dan Shipper, I was just offering my 2 cents :)
- jmyc 14y agoNot necessarily of Shipper but I'm sick of these "long conversation" ways of explaining things that don't need to be simplified. This is an almost boringly simple problem (I'm not trying to be condescending, but this is freshman CS stuff), we don't need to be eased into the complex situation at hand.
- dastbe 14y agoI think it is a cute problem which turns a "can you program" question into a can you think question, but I don't see why it has to have a such a long introduction.
- novalis 14y agoWhere else would the uncalled for dead on hate for OOP be placed in that piece without throwing other ranting parts in there, it would look extra crazy right ?
- bandy 14y agoIt's a newer version of the old "Ise A Muggin" magical musical numbers song, originally recorded in the 30s by Stuff Smith with 7 and 10. Here's a more recent recording ('60) using 4 and 10: http://www.youtube.com/watch?v=7n4AGv6HWLs http://www.youtube.com/watch?v=7n4AGv6HWLs
- polynomial 14y agoI'm now obsessed with finding the Stuff Smith version.
- bandy 14y agoLooks as if one of the three versions on this disc would likely be the "Ise a Muggin (Magical Musical Numbers Game)": http://www.amazon.com/Complete-1936-37-Sessions-Stuff-Smith/dp/B000N60HAE http://www.amazon.com/Complete-1936-37-Sessions-Stuff-Smith/... The other Stuff Smith version of "Ise a Muggin" has resulted in a question I ask older Railroad workers (and fans): What exactly did a "Black Cap" or a "Blue Cap" do? (It also speaks of Red Caps, but we still have that profession here in the USA.)
- jholdn 14y agoHow about I use a simple suffix tree instead?
- EternalFury 14y agoCute. Now, back to reality, where 99% of the code is dead simple stuff that sticks around for years. I am really starting to believe it is a fault to be too clever in software development. Granted, the easier your code is to understand, the better it is for business.
- neeleshs 14y agoInterestingly, this fizzbuzz (not the inverse) is used in several contexts in my current project. But you are right, 99% is probably a very good estimate of dead simple stuff
- eitally 14y agoNope, not even close. Yes, CRUD apps and simple parsers/middleware are dead simple in theory, but when you have scores of execs fighting over quirky business rules, combine that with attrition and years of technical debt and even simple things become complex, crufty codebases. Pile on regulatory compliance and other external factors and it gets unmanageable quickly. Dealing with this is one of the biggest reasons type A programmers leave the enterprise space -- if you are frustrated easily by politics and nonsensical requests, AND you are confident enough or empowered enough to say not, the odds are high you will be unhappy.
- raganwald 14y agoTo me, the notion that 99% of a code base is dead simple is like the notion that Human DNA is 99% similar to Chimpanzee DNA. There’s only 1% difference, but oh what a difference that 1% makes!
- xsmasher 14y agoAgreed - but making too-clever solutions for the easy 99% parts is a disease. I'm sure you've met arsonist developers that light buildings on fire just to see if they can escape them.
- 14y ago
- ww520 14y agoI found that clearly defining and specifying a question is half way to the answer. More often than not, the questions are asked poorly and the desired goal is obscured confusingly. For example the first question, "How do you map the list on the left to the list on the right?" Huh? What do you mean by "map"? Do you want a data structure to link the two? Are the list infinite? Or just upto 100? Do you want to derive the algorithm to produce the next number? Or do you want a function that given the left list produce the right list? Or do you want a function that given a number from the left list, produce the corresponding item on the right. On and on.
- neeleshs 14y agoOr, in the context of an interview, thats also a skill on the part of interviewee, to ask these/similar questions that will help her/him get to the solution.
- sophacles 14y agoI find that slightly vague questions are actually helpful in interviews. In the real world, finding requirements and interpreting specs require these skills. So I will ask questions that can be understood a few ways to gauge the prospective hire's requirements gathering. This can backfire, and requires a bit of fluidity in the interviewer's part -- no cargo cult questions, just open problem solving. In a really good case, me being open to what the interviewee was saying about ambiguity led to a fascinating attempt to solve a different problem than I had originally structured, but we found out we work well together and solved a fun problem. At the same time he showed me his skills, and I showed him my skills. Result: both of us decided working together would be beneficial -- the best possible outcome of an interview (although just as good would be mutually deciding we wouldn't work well together and amicably parting ways).
- neeleshs 14y agoIndeed, though not as collaborative as your case, I've been intrigued by the variations of the original problem that evolved because of how both of us(candidate & me) probed the problem.
- MaxGabriel 14y agoI think these long allegories are rarely justified vis-a-vis a direct explanation that can 'break character' to reference other works and use more varied supporting examples. This also avoids wrapping up individuals and their reputations into the much more important question of what the truth is.
- igoros 14y agoHere is an O(N) functional solution in C# LINQ: http://pastebin.com/fvdmQBFC http://pastebin.com/fvdmQBFC Making the solution "functional" was by far the most time-consuming part of the exercise.
- agumonkey 14y agoGreat article, very lispy, very fp. Lead me to question myself about more abstract problems. Anybody knows other articles of this kind ?
- ricardobeat 14y agoNot articles, but you'll probably enjoy http://rosettacode.org/ http://rosettacode.org/
- p0ckets 14y agoIf the bounds are specified, just run the forward problem once to get two lists (3,5,6) and (fizz,buzz,fizz), then find the "substring" you want in the second list. Edit: you don't even need to specify the bounds, just run the forward algorithm for a large enough range (length of input list x 15 will be more than sufficient).
- dxbydt 14y agoIts called a "slice", not "substring" - but your solution is the simplest to understand and the shortest to code up in Scala (using slice on lit and List.tabulate). The multiplier is much smaller than 15. If input list is n, I think 30+15*ceil(n/15) will suffice, because that'll cover n on both sides. I'll hold off on posting my solution to give others a chance.
- harpastum 14y agoTLDR: Here's a constant-time solution: http://codepad.org/Id9eu0Ax http://codepad.org/Id9eu0Ax Matching the the sequence of fizz/buzz/fizbuzz disregarding numbers is a repetitive case. Start with 3 Fizz 5 Buzz 6 Fizz 9 Fizz 10 Buzz 12 Fizz 15 FizzBuzz 18 Fizz 20 Buzz 21 Fizz 24 Fizz 25 Buzz 27 Fizz 30 FizzBuzz [repeats] Just split the input list as a prefix of a few, and then a repeat. The goal of the shortest total distance between them is constant. You just need to measure the number of ints between each of the 8 repeating distances. For example: 3 -> Fizz +2 -> Buzz +1 -> Fizz +3 -> Fizz +1 -> Buzz +2 -> Fizz +3 -> FizzBuzz +3 -> Fizz +2 -> Buzz +1 -> Fizz +3 -> Fizz +1 -> Buzz +2 -> Fizz +3 -> FizzBuzz So you would match against the list [Fizz, Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz].
- deleted 14y ago[deleted]
- anonymoushn 14y agoSo the runtime of the solution is bounded by a constant for arbitrarily large input? There must be some great cleverness at play to produce an output with size linear in the input size without taking time proportional to the size of the output.
- bdonlan 14y agoIt's just modular math. The output is fizz if the output is orthogonal to 0 mod 3, and buzz if it is orthogonal to 0 mod 5. It's fizzbuzz when it's 0 mod 15. Now, since 15 is divisible by 3, it's easy to see that x = 0 mod 3 iff x = {0, 3, 6, 12} mod 15, and similarly x = 0 mod 5 iff x = {0, 5, 10} mod 15. So you can see now that you can determine the output for a given index based on the remainder after dividing by 15, so the sequence must repeat every 15 elements.
- dspeyer 14y ago> Shipper: Hmmm. I don't think that list is valid... > Google: Good. So your program will have to detect that. Your program might receive bad input, and it's your responsibility to output an error code if so.
- dxbydt 14y agoGot a dozen solutions to inverse fizzbuzz so far, atleast two of which are O(n). Got some disturbing emails - a recruiter plans to use inverse fizzbuzz at his next interview! Dear God what monster have I unleashed...programmer community, pls forgive me. And a CS prof is going to assign inverse fizzbuzz to his cs 101 students as extra-credit.
- harpastum 14y agoI believe a constant solution exists, because Fizzbuzz repeats after 8 items. Still working on it... <EDIT> Yes, here's a constant solution: http://codepad.org/Id9eu0Ax http://codepad.org/Id9eu0Ax
- qiemem 14y agoIt's pretty simple actually (spoiler): For any sequence containing fizzbuzz, match up the fizzbuzz with 15 and you're done. Any sequence of length >=7, fizzbuzz will be present. Thus, we only need to think about sequences length <7 that don't contain fizzbuzz. Solving this by brute force is constant time, since you only have finite possible inputs.
- harpastum 14y agoYup. I updated my comment with working code. Just figure out the small case, and extrapolate once you find a match.
- igoros 14y agoNice approach! It's O(1) to find a candidate solution, but of course it will still be O(N) to verify that the solution really works.
- Danieru 14y ago"Any sequence of length >=7, fizzbuzz will be present." Are you sure? I don't think the challenge said the sequence could not be gappy.
- jchonphoenix 14y agoHa, I actually use a similar question in phone screens. Its surprising how many people can tell you how to do fibonacci and can't invert it.
- mleonhard 14y agoThis article is missing the point of FizzBuzz.
- lucian303 14y agoYou mean this isn't a joke? 2016 and interviewers STILL asking dumb, useless questions. Oh well ...
- zackzackzack 14y agoHere's one I wrote that plays around with Clojure. I don't think it is quite O(n) though: https://gist.github.com/2599321 https://gist.github.com/2599321
- appleaintbad 14y ago> After a series of embarassing public disasters involving OOP & mutable state, the world has finally realized the wisdom of John Hughes and switched to functional programming. Which world do you speak of? Most of the jobs I'm aware of (for example, java, .net, php, etc.) are still a mix of OOP and procedural.
- sold 14y agoPlease read the post! It clearly states this is a futuristic 2016 scenario. (of course it is complete fantasy, but that's not the point)
- roryokane 14y agoThis blog's theme, unfortunately, makes the first paragraph, which is entirely a link, look like just another part of the header for the blog post. It blends in with the post title, date, and separator line. I only looked up and saw the "2016" introduction after I started reading about Apple requiring Haskell for apps and was confused.