Inverse Fizzbuzz(jasq.org)
jasq.org
Inverse Fizzbuzz
http://www.jasq.org/2/post/2012/05/inverse-fizzbuzz.html
58 comments
So 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.
For those who aren't getting anonymoushn's point - outputting a O(n) bytes will take O(n) time, no matter if your processing per piece of output is fast or slow. In fact, this optimization will only give constant-time speedup from an iterative or functional solution - those do some (very cheap) numerical operations for every number in the range, while this does (even cheaper) array lookup for 7 out of every 15 numbers. A decent-sized constant-factor speedup is still only a constant-factor speedup.
That assumes you're providing the output as a list of elements. Since it's a contiguous sequence, you can uniquely identify a particular output as a tuple (start, length). So you can get a constant-time solution if you're allowed to assume the input is valid (and have a constant-time way of getting the length of the input, I guess).
On the other hand, checking to ensure that the input represents a valid sequence is going to be O(n) in the size of the input no matter what you do...
On the other hand, checking to ensure that the input represents a valid sequence is going to be O(n) in the size of the input no matter what you do...
It'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.
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.
> 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.
Your program might receive bad input, and it's your responsibility to output an error code if so.
[deleted]
[deleted]
I 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.
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.
Or, 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.
I 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).
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).
Indeed, 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.
Cute.
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.
To 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!
i'm not sure what you're working on, but in many enterprise problems, the business complexity is ridiculous: see < http://c2.com/cgi/wiki?WhyIsPayrollHard >. functional programming techniques eliminate several classes of bugs that I see all the time in large codebases, and the quality/correctness benefits make maintenance much less expensive.
There is a difference between dead simple problems and dead simple solutions. You can always come up with complex solutions to dead simple problems. And that's the biggest problem of all.
Also, very often, it's not software that does not scale, it's people working on the software. Clearly, there are relatively few developers in the marketplace who can master the most advanced software development techniques. In practice, "clever" code will be misunderstood sooner or later, its complexity will increase as "lesser" developers patch it down to a level where they can understand it, expand it and correct it. And so you end up with large balls of mud, initially clever code turned into tremendous sources of complexity.
If you look at the pillars of Internet, HTTP, FTP, telnet, IP, TCP, POP, SMTP, etc. There is 1 common factor between them: They are dead simple solutions to specific problems. And that is why they stood the test of time.
Also, very often, it's not software that does not scale, it's people working on the software. Clearly, there are relatively few developers in the marketplace who can master the most advanced software development techniques. In practice, "clever" code will be misunderstood sooner or later, its complexity will increase as "lesser" developers patch it down to a level where they can understand it, expand it and correct it. And so you end up with large balls of mud, initially clever code turned into tremendous sources of complexity.
If you look at the pillars of Internet, HTTP, FTP, telnet, IP, TCP, POP, SMTP, etc. There is 1 common factor between them: They are dead simple solutions to specific problems. And that is why they stood the test of time.
I don't think I would describe most of these protocols as "dead simple". Consider the multitude of attacks that existed/continue to exist against some of these protocols after decades of use. TCP reliable transmission and flow control are pretty tricky. The connection state diagram alone in RFC793 is non-trivial.
Interestingly, 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
Nope, 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.
Got 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.
I 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
<EDIT>
Yes, here's a constant solution: http://codepad.org/Id9eu0Ax
It'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.
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.
"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.
Are you sure? I don't think the challenge said the sequence could not be gappy.
This is resolved in one of the examples given in the introduction where the interviewer agrees that "buzz buzz" is an invalid sequence.
If sequences could be gappy, wouldn't the solution be just mapping fizz to 3, buzz to 5 and fizbuzz to 15? ( or multiples of those numbers, if duplicates aren't allowed )
But in no case would that be the shortest sequence.
For your example a shorter one would be 9,10,15.
For your example a shorter one would be 9,10,15.
If you can assume that you are given a valid fizzbuzz sequence then your solution works. However, look at what it outputs for:
raw_input = ["Fizz","Buzz","Fizz","Fizz","Buzz","Fizz","FizzBuzz","Buzz","Buzz"]
raw_input = ["Fizz","Buzz","Fizz","Fizz","Buzz","Fizz","FizzBuzz","Buzz","Buzz"]
I 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.
Where 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 ?
I 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.
Here is an O(N) functional solution in C# LINQ: http://pastebin.com/fvdmQBFC
Making the solution "functional" was by far the most time-consuming part of the exercise.
Making the solution "functional" was by far the most time-consuming part of the exercise.
Anyone else sick of Shipper?
Memes 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.
To 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.
No, pretty soon we'll see WWSD t-shirts and wrist bands. I think this is a net win for HN!
Not sick of it, but if I were him I'd feel sort of creeped out.
Dude. 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.
"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.
Good to hear! I do also know that I'm not Dan Shipper, I was just offering my 2 cents :)
Not 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.
It'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
I'm now obsessed with finding the Stuff Smith version.
Looks 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/...
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.)
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.)
Great article, very lispy, very fp.
Lead me to question myself about more abstract problems.
Anybody knows other articles of this kind ?
Anybody knows other articles of this kind ?
Not articles, but you'll probably enjoy http://rosettacode.org/
If 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).
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).
Its 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.
This article is missing the point of FizzBuzz.
> 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.
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.
Please read the post! It clearly states this is a futuristic 2016 scenario. (of course it is complete fantasy, but that's not the point)
This 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.
Here's one I wrote that plays around with Clojure. I don't think it is quite O(n) though:
https://gist.github.com/2599321
Ha, 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.
How about I use a simple suffix tree instead?
You mean this isn't a joke? 2016 and interviewers STILL asking dumb, useless questions. Oh well ...
Matching the the sequence of fizz/buzz/fizbuzz disregarding numbers is a repetitive case.
Start with
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:
So you would match against the list [Fizz, Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz].