10 ms·

Rent-a-coder hilarity (2008)

140 points by cramforce 13y ago

CurtMonash 13y ago
Dear Sir, I kindly propose a two-phase project based on Test-Driven Development methodology, of which we are expert. 1. Specify and develop test harness. 2. Develop program that satisfy tests.
- eliben 13y ago
  (1) is actually perfectly doable w.r.t. to this project, so I must be missing your point.
  - CurtMonash 13y ago
    Any set of tests that fully exercised the desired functionality would be infinite. Any finite approximation would modify the task from an impossibly infinite one to something possible.
    - eliben 13y ago
      Note that for a huge amount of software functionality, the amount of tests required to "exercise full functionality" is infinite, and very rarely can we mathematically prove that a finite set suffices. When code is multi-threaded, for instance, this tends to happen a lot.
      - CurtMonash 13y ago
        Yes. But I stand by adaption of the old sales technique "What does ____ mean to YOU? ... Oh, that won't be a problem."
Lukeas14 13y ago
Here's another asking to solve P vs NP. Hilarity ensues: http://www.getacoder.com/projects/solve%20p%20vs%20np_132036.html http://www.getacoder.com/projects/solve%20p%20vs%20np_132036...
- wrt54g 13y ago
  Ok, so lots of people bid on projects without fully understanding the requirements, some people understand but want to solve it as an engineering rather than a math problem, and others get it. Where's the hilarity in this or OP? HN Sunday night, aiyiyi...
  - kabdib 13y ago
    It's the cautionary tale that you cannot believe the words coming out of a salesman's mouth. I used to work in a startup where the cubicals had sequential phone numbers. From time to time I'd get a call from one of the sales reps in the field. "I'm talking to a customer," the rep would say, "Can our product do X?" Where 'X' was something like, oh I don't know, 'Computational Sushi' or 'License plate recognition,' or anything unrelated to what our real-time messaging middleware did. "No," I would tell them (but using more words). Then I would move to the next cube and instruct the engineer sitting there that the phone was about to ring, and that they should pick it up, listen and say "No" quite firmly. Repeat for the remaining cubicals. Salesmen will say anything to make a sale. It's what they _do_.
    - chiph 13y ago
      We used to have customers who would do that. They'd call every number in the company until they found someone who'd say "That sounds do-able." Upon which they'd demand a price reduction because "Your product doesn't do what you said it does."
- dragonquest 13y ago
  The overlooked bid in this case was by Vinay Deolalikar for $1000000 who simply said "I think I have done this." For background, Vinay was a researcher at HP Labs, Palo Alto who made a serious attempt at solving the problem (independently from this bid :P).
- runeb 13y ago
  I like the guy who guarantees the solution will be "100 % W3C compliant"
Evgeny 13y ago
That looks like another 'FizzBuzz' filter to me, just more elaborate - in this case, KurtG appears to be the one to pass the screen, right?
- jimbokun 13y ago
  I am SO tempted now to add this to our standard interviewing questions list. At least for anyone claiming a CS education.
  - endersshadow 13y ago
    Why? This is a miscommunication issue, not a CS issue. Determining whether or not something runs "infinitely" is typically just, "Does it run longer than an acceptable amount of time?" It may not actually run infinitely, but it may run practically infinitely (which is to say, just very long). You have people responding that are assuming that they're going to test if a process takes too long and bail if it does. Pretty simple, actually, since for all practical purposes, when somebody describes a program as "taking forever," they rarely mean "forever" literally. If you want to ask it, go ahead, but understanding practical limitations and engineering to those is a perfectly acceptable answer for the context of the rent-a-coder site (and an interview for a coding job). The only time it's not is if you're interviewing for some sort of academic position.
niggler 13y ago
Unfortunately, the situation has only gotten worse in 2013
belovedeagle 13y ago
Frankly, I think this shows that the "jokers" don't know what they're talking about either. Yes, the problem is undecidable in general, but one could certainly develop an interesting program that solves the problem sometimes, and can definitively report when it cannot decide the problem [in a given number of steps, for some value of "step"]. The halting problem is not some black hole such that when you dare venture into it, your program will be lost never to "return;".
- belovedeagle 13y ago
  In fact, come to think of it, for any program which 1) uses a bounded amount of memory and 2) has a bounded input (taking "input" as broadly as possible), the halting problem is always decidable in 2^[bits of state] "steps". There are a lot of programs which satisfy (1) so long as (2) is satisfied, and if (2) is not satisfied then the halting problem is not an interesting problem at all.
  - just2n 13y ago
    The approach would be to fix an upper bound on memory and to enumerate all possible state, running the program each time and determining if all cases terminate or if any runs forever? I think the real crux of the problem is that you can't determine in any of those cases whether the program is going to terminate. Consider bogosort or a brute-force algorithm for solving travelling salesman. These can take millions of years to complete even for small input sizes. Do we consider that an "infinite" runtime?
    - belovedeagle 13y ago
      No, the algorithm is to run the program and see if any state is repeated; if it is, the program is in an infinite loop (where "state" means, roughly, all memory and remaining length of input). Of course, this requires 2^[bits of state] bits of memory, and a similar amount of time. Obviously an interesting (read: approximate) solver would use tighter heuristics.
    - sp332 13y ago
absherwin 13y ago
Writing a program to determine if another program will complete, error, or run indefinitely is quite doable given reasonable constraints: Run the program! One need only specify some reasonable length either equivalent to infinity for such a program, use a heuristic of checking whether the program is in the same loop and if so, whether any of the variables involved in determining loop termination are changing. Of course, proper security precautions are required.
- X-Istence 13y ago
  You forgot about the butterfly. Even if it looks like nothing could change, something could due to a bit flipping in memory, which would allow the program to halt.
  - absherwin 13y ago
    Right. Any statement that the program is in an infinite loop will usually be subject to error. Of course, the real question anyone asked to develop such a program would be what runtime is equivalent to an infinite loop. Any real-world program must have a runtime bound that is predictable on invocation or it's useless.
- hobs 13y ago
  It also says it must take "the source code", so that means you would have to be able to build any arbitrary program from source? That would be a huge pain in the ass in general, above and beyond actually doing the things you mention.
- A1kmm 13y ago
  For a certain subset of problems, it is possible to do this. For any finite number of clock cycles N, in a Turing-complete language, I can write you a program which terminates but takes longer than N cycles. There is therefore no value of N which will consistently give the correct results in your program. Turing machines have an infinite tape, so under a Turing machine model, there are infinitely many loop termination conditions, and so it is possible to craft a program which never repeats the same state within N cycles for any N but still terminates. If your machine is finite state (with no inputs) and s possible states, rather than a Turing machine, you can check if the program halts: halts s program initialState = do seenState <- newBooleanArrayOfSize s setBooleanEntry seenState initialState halts' initialState where halts' state0 = if state0 == HaltingState then return True else do seenAlready <- getBooleanEntry seenState state0 if seenAlready then return False else state1 <- nextState program state0 setBooleanEntry seenState state1 halts' state1 In practice, s might be very large (even a 64 bit integer in the state will contribute 2^64 to s) so this algorithm isn't necessarily usable in practice, but it does complete in finite time.
comex 13y ago
Although anyone worth their salt should recognize the halting problem, I'll point out that the vast majority of programs can be proven to terminate or not, and although testing for halting in particular isn't especially useful for real-life programs, it could be used as a benchmark for a more general theorem-proving tool of the sort that would be very useful for avoiding bugs. Of course, a tool that could automatically prove useful properties about programs with no guidance, which would be significantly superior than all existing practical program analysis tools which require quite a lot of guidance, might be beyond the capabilities of the people that post bids for $300. Unless it used Mechanical Turk. :)
- cynicalkane 13y ago
  There exist research programming languages that support 'total functions', that can be proven to always halt. Usually you divide the world into functions and cofunctions, and data and codata, the latter of which may be infinite (such as I/O). I wish this were a more popular thing. When I write a function, I can probably enumerate in my head all the things I want it to do, and not halting usually isn't one of those things. But the instinctive reaction is to worry about Turing-completeness, which is puzzling. When's the last time you wanted a program with fundementally unprovable behavior?
  - Ezku 13y ago
    Programming with such functions is called total functional programming. Here's a nice little introduction to the subject[1], and if you're a fan of code and math you should probably check out the other blog entries as well. [1]: http://blog.sigfpe.com/2007/07/data-and-codata.html http://blog.sigfpe.com/2007/07/data-and-codata.html
  - btilly 13y ago
    When's the last time you wanted a program with fundementally unprovable behavior? I'm working on one today. I'm analyzing a data set for tens of millions of possible statistical anomalies, and I'm putting my "investigate further" threshold to statistically one in billions. Each thing added increases the size of the search space. Knowing that it is extremely unlikely to run forever really is good enough. Proving that it won't is a non-issue for me. (Right now it takes several hours to run.)
kens 13y ago
If you click through to the screendump of the bids there are some pretty obscure jokes besides the obvious KurtG and GeorgeCantor. BusyBeaver is another computability joke, solving "in the most productive manner possible". chn's bid is in infinite-radix numbers. The HaltLib.NET library is claimed to work in PNG and BNF among other languages. J. S. Carberry is a mythical Brown professor started as a practical joke in 1929; the backstory is interesting: http://students.brown.edu/College_Hill_Independent/?p=2127 http://students.brown.edu/College_Hill_Independent/?p=2127
xyzzy123 13y ago
Actually one of my colleagues had the opposite (yet in my opinion equally hilarious) problem with rent-a-coder - the code was much better than he wanted. He wanted sample vulnerable Java code to use for secure development training. None of us enjoyed writing Java web apps, so this seemed like a cunning plan to get sample (yet custom) code with minimal effort. Hopefully, full of bugs. He asked for a "task tracker" (IIRC, might have been phone book), and specified Java with "no framework" as the implementation language. He chose the dodgiest bidder he could who looked like they might finish the job. I think he put a few gotchas in the specifications. Actually, as delivered, the app was solid, and based on JSF2 ;) What I learned about rent-a-coder: * There are corporate refugees who do this on the side to make extra money. * CRUD apps appear to be a sweet spot for rent-a-codering. * Code quality is hit-and-miss if you're looking for disasters ;)
- deleted 13y ago
  [deleted]
- raverbashing 13y ago
  That's funny, how come this person was the dodgiest bid of all? Well, maybe he should have specified he wanted an insecure application (or an "extra secure" application - expected result is having several layers of snake oil and "proprietary solutions" applied)
  - xyzzy123 13y ago
    Bidding was decided based on communication style, low bid, low GDP country and "has feedback on just 1 or 2 projects" (minimal, but not extensive history of delivering). Didn't ask for "extra buggy" or "extra secure" because the ideal was the combination of honest mistakes and laziness that turn up in real code all time. I like the idea though ;) I mean, you'd think that for $100 or whatever all up, they would have half-assed it a bit ;) Probably the mistake was to stop at n=2 and not choosing a harder problem domain.
    - aptwebapps 13y ago
      I love a good anti-anecdote (antidote?) ;) Here's one potential problem with the selection criteria: "low bid, low GDP country". I might have been better to weight the bid with the GDP (I don't mean really crunch the numbers, just put your thumb on the scale). But more to the point, if your friend didn't have a lot of experience with this sort of thing, he probably wasn't that good at picking a bad apple. Or he just got unlucky, maybe.
lifeformed 13y ago
What would happen if you went through with it? I bet it wouldn't be too hard to write a program that does it for 90% of cases. Is there a simple case that would be impossible to determine?
- eru 13y ago
  Oh, the halting problem is easy enough to solve for most cases (people do it informally all the time), just not for the worst cases. For giving a percentage, you need to specify a distribution of programmes first. E.g. programmes created reading from /dev/random, or programmes downloaded at random from the internet, or something more sensible.
- zura 13y ago
  Exactly. The first reason to reply to this kind of request would be to engage with the uneducated client, and make sure that she will pay for that 90%.
- rcfox 13y ago
  Off the top of my head: 1) Assuming rand(x,y) gives a uniform distribution between x and y: for (int a = 0; a < INT_MAX; a += rand(-1,1)); 2) I can't find the source any more, but someone basically implemented a big int library with bit twiddling to allow for an upper bound on a loop that would finish after the heat-death of the universe, assuming generous CPU specs. Not infinite, but also non-terminating. 3) Anything that makes a system call. You might never get scheduled again!
  - StavrosK 13y ago
    #2 isn't any more non-terminating than "for (i=0; i < 100; i++)" is.
  - dagw 13y ago
    As to 1) any rand() implementation that doesn't use an external source of randomness is deterministic and cyclical, thus it is quite possible to determine if 1) halts by analyzing rand()
- 13y ago
barking 13y ago
Is it money up front or c.o.d on those sites? Trying to get my head around why people bid without having a clue what`s entailed
- Evgeny 13y ago
  I believe that if the developer's bid is accepted, the money goes into the 'escrow', which is the main purpose of the site: make sure that the developer does not go unpaid if he did the work. If the customer is not happy, there are some sorts of resolution processes that I don't know much about. What surprises me is that the clueless developers also had high 'reputation' (positive customer feedback), which should be at least some indication about their competence.
  - noptic 13y ago
    They do not really read what the customers want until the bid is accepted. foreach(newProject as project){ new Bid( projeckt.averagePrice * 0.8 ), "We are the best nd have done this many times"); } In the most cases they can really solve the problems and get good ratings. Some clients include a "password" in the project description and ignore all messages without the password.
zura 13y ago
It looks like a recruiter, but the other way around :)
asveikau 13y ago
I don't know about all the rest of you, but I find it really depressing to read these rent-a-coder sites. The first thing that strikes me is that people posting projects don't really understand the value of software engineering. They want someone to do crazy ambitious projects for pretty much no money. As if to say, "I have this idea which is really awesome and valuable, now I just need some monkey to do all the work." $500 should be enough for that, right? Then I'll cash in on my awesome idea... Maybe some projects honestly work out like that. But a lot of the projects I see on these sites fall outside that scope. For big ambitious projects, we all know programmers are not fungible resources, and competent execution matters. But the worst part is that people humor these projects, or more likely take advantage of the gullibility of the people asking for them... "Yes sir, I can solve that impossible problem promptly and under your budget of $500." It's really sad.
- jiggy2011 13y ago
  It's easy enough for us to say that people don't appreciate the value of what we do but really market value is set by supply and demand. Not everyone lives in San Francisco or New York where they feel they must bill $100 p/h just to make rent. A smart person in an emerging economy where $500 per month puts them on a higher part of the local income curve could certainly realize that they can compete in a global marketplace on price. This does not necessarily make them incompetent, in fact it's not a bad way to "hack" oneself out of poverty. Besides, many software applications are alternatives to excel spreadsheets or to handwritten HTML websites and don't necessarily require the hippest programmers who are well studied on the latest technologies. A customized rails scaffold can go a long way to solve a lot of real business problems, and doesn't HN often talk about the value of producing an "MVP"?
  - asveikau 13y ago
    There's truth in the idea that a first world salary might go further elsewhere in the world, and that lots of people get by on less ... But I suggest you look at getacoder.com et al. and see what I was really talking about, because it can't be explained only that way with no other explanation. I once saw a project similar to something that took a former employer 10 years to iterate on and finally get right, with a long tail of bug fixes and crazy corner cases because it is a difficult problem. The rentacoder "cost" was 2 weeks and less than $1000. I did not follow up with that particular guy's project but I'm going to guess that they did not have success with those expectations and that budget.
Luyt 13y ago
I liked this reaction, from KurtG: Dear Mr T., Your problem is very much like I have been considering. Assume that we have a consistent and complete axiomatization of all true first-order logic statements about natural numbers. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm N(n) that, given a natural number n, computes a true first-order logic statement about natural numbers such that, for all the true statements, there is at least one n such that N(n) yields that statement. Now suppose we want to decide if the algorithm with representation a halts on input i. We know that this statement can be expressed with a first-order logic statement, say H(a, i). Since the axiomatization is complete it follows that either there is an n such that N(n) = H(a, i) or there is an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until we either find H(a, i) or its negation, we will always halt. This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false. There is no way your application can be built, and for this advice I am willing to waive any fee. Sincerely, K. Gödel.
- raverbashing 13y ago
  "But the other guy says he can build this in Java in 50 days, I think you're not as smart as he is"
  - pekk 13y ago
    The boss is always right
- deleted 13y ago
  [deleted]
tzaman 13y ago
We had exactly the same frustrations with online outsourcing (being on both sides of the table), and now we have built https://codeable.io https://codeable.io (focused only on WordPress for the time being) - 4 months after launch, we have more than 900 jobs posted, half of them completed, excellent reviews, more than $45k in revenue. I'm very proud of what we achieved so far, because we eliminated the biggest "pains" of online outsourcing; There is no bidding, our (invited and reviewed) contractors form a single estimate which is then presented to the client. And we focus on sub-$500 tasks, because the margin for error is significantly smaller, so if a client comes in with a huge job, we help him break it down into smaller pieces. We also maintain client/contractor ratio, so there is no need for contractors to compete with one another, anyone who wants to work, can work.
- jpdoctor 13y ago
  > so there is no need for contractors to compete with one another Why would buyers desire this?
  - tzaman 13y ago
    Because first and foremost, we want to keep contractors happy. If they are paid well (by well I don't mean ripping clients off), they will come back and perform more work. Our long-term goal is to establish a trusted network of developers that always go that extra mile to satisfy clients - I must admit, so far, this approach has paid off in dividends. We're currently re-designing the landing page, and we will put client testimonials on that prove it.
    - jpdoctor 13y ago
      > and we will put client testimonials on that prove it. I'll be curious to see which client gives you a testimonial that thinks non-competing contractors is a great idea.
      - tzaman 13y ago
        Each and every, in fact. Because they don't come to us to see how (or not) our system works but to get their problems fixed in time, and by a top quality expert. (I'm saying this because we do a lot of research on both sides, and transparency is part of our business, so all involved know how the system works)
ak39 13y ago
Isn't the joke on the guy posting the (impossible) job? I see some have commented on the economic desperation or the salesman attitude of the coders bidding for this impossible job, but when someone asks a large population of salesmen that they have a serious intention to procure a bridge ... well ... there will be a few who'd definitely show up wanting to sell one. Don't see the point of this whole thing really.
- prakashk 13y ago
  > Isn't the joke on the guy posting the (impossible) job? No, considering the poster's name is "AlanT"!
noptic 13y ago
client: I need a software tht can find information about my mp3 files online and it must work 100% correct me: What information do you have and what do you want to look up? client: I have the folder and file names and there are 5 webpages like google where you can search for music. I want the programm to get the right song info from this. BUT IT MUST WORK 100% right no error ever! I had 6 other programmers try it but no one can make it right! (the real clients english was even worse)
DanBC 13y ago
So, what's best current practice for naive clients when trying to hire designers or programmers? Is that advice online anywhere?
dmead 13y ago
what if that program finds bugs in itself? wheres your god now?
th0br0 13y ago
How come that there's a new getacoder project that invites all those users who gave those fabulous comments? http://www.getacoder.com/projects/simple_meteorjs_app_157993.html http://www.getacoder.com/projects/simple_meteorjs_app_157993...
adamrneary 13y ago
To me, the disappointing thing about this spoof is that it treats the engineers on this platform like "code monkies." One of the biggest gripes from top tier engineers is that they hate being treated like animals by jerky business guys, and here we have a group of people mocking these engineers and the platform. It all seems disrespectful to me. describe 'My experience, -> _.map ['amazing','awful'], (quality) -> _.map ['engineers','business guys'], (role) -> _.map ['Brooklyn','online platforms'], (place) -> assert "There are #{quality} #{role} in #{place}."
lnanek2 13y ago
What's funny is that math people know this is impossible and will never attempt it, but it's quite easy to write something practically useful that does the job most of the way. It's possible for static analysis tools to identify many loops that will never end. E.g. in Java if there's no break or return and the guard is a boolean that is never written to and no runtime class loading is used. It can be very valuable to have static analysis tools in an organization, I know my own company has them, and we don't share them. IBM as well puts tons of work into it. Motorola has shared one of their tools. Every bug and issue your tool can find is one much more cheaply solved. Similarly, the client may be doing coding education, or interview, or other software where just a few limited lines and limited operations need to be checked, or it is OK to say if you hit n^4 loops you lose, etc..
- skateinmars 13y ago
  John Carmack also has a lot of praise for static analysis: http://www.altdevblogaday.com/2011/12/24/static-code-analysis/ http://www.altdevblogaday.com/2011/12/24/static-code-analysi...
cognivore 13y ago
The part of rent-a-coder that bothers me is I'm sure it goes like this more than we'd like: - Party A contracts with Party B on a big software contract. - Party B sub-contracts on some of it to Party C, D, & E. - Party E is a bit dodgy and does a bunch of rent-a-coder. - Hey it compiles! It gets passed up the line. - Party B is late and just passes it on. - Party A is late and, "Hey, it works!" and delivers. - Hilarity does not ensue. My personal experience with this kind of thing is that the further away from the actual concerned party you are (in other words, the people who are going to use the software), the more likely it is that the software is going to be wrong.
tlrobinson 13y ago
Project Creator: AlanT Perfect.
rmrfrmrf 13y ago
I don't think it's all that hilarious to waste people's time, especially when the goal is to point out the naïveté of others.
Eva_Peron 13y ago
I have an uncle who is a deposed King of Nigeria who will solve this problem for you for a small deposit and your bank account information. :-)
stcredzero 13y ago
Hmm, the last time I commented on HN on this rent-a-coder hilarity, someone proposed "writing a new scripting language" within a week. I suggested that this was actually doable within a week. One could just concoct some simple language with curly braces that maps 1-to-1 with a procedural subset of Python, then output Python to run it. The result? I was downvoted by some less than informed individuals who thought there was some deep fundamental difference between curly braces languages and whitespace significant ones. What The!?... On HN!? This was before Coffeescript was a widely known thing as it is today. Think what you'd like about Zed Shaw, but his "DB Invasion" idea has some merit.
- nijk 13y ago
  Heh. JavaScript was famously invented in a week.

140 points by cramforce 13y ago

Dear Sir, I kindly propose a two-phase project based on Test-Driven Development methodology, of which we are expert. 1. Specify and develop test harness. 2. Develop program that satisfy tests.

eliben 13y ago
(1) is actually perfectly doable w.r.t. to this project, so I must be missing your point.
- CurtMonash 13y ago
  Any set of tests that fully exercised the desired functionality would be infinite. Any finite approximation would modify the task from an impossibly infinite one to something possible.
  - eliben 13y ago
    Note that for a huge amount of software functionality, the amount of tests required to "exercise full functionality" is infinite, and very rarely can we mathematically prove that a finite set suffices. When code is multi-threaded, for instance, this tends to happen a lot.
    - CurtMonash 13y ago
      Yes. But I stand by adaption of the old sales technique "What does ____ mean to YOU? ... Oh, that won't be a problem."

Lukeas14 13y ago

Here's another asking to solve P vs NP. Hilarity ensues: http://www.getacoder.com/projects/solve%20p%20vs%20np_132036.html http://www.getacoder.com/projects/solve%20p%20vs%20np_132036...

wrt54g 13y ago
Ok, so lots of people bid on projects without fully understanding the requirements, some people understand but want to solve it as an engineering rather than a math problem, and others get it. Where's the hilarity in this or OP? HN Sunday night, aiyiyi...
- kabdib 13y ago
  It's the cautionary tale that you cannot believe the words coming out of a salesman's mouth. I used to work in a startup where the cubicals had sequential phone numbers. From time to time I'd get a call from one of the sales reps in the field. "I'm talking to a customer," the rep would say, "Can our product do X?" Where 'X' was something like, oh I don't know, 'Computational Sushi' or 'License plate recognition,' or anything unrelated to what our real-time messaging middleware did. "No," I would tell them (but using more words). Then I would move to the next cube and instruct the engineer sitting there that the phone was about to ring, and that they should pick it up, listen and say "No" quite firmly. Repeat for the remaining cubicals. Salesmen will say anything to make a sale. It's what they _do_.
  - chiph 13y ago
    We used to have customers who would do that. They'd call every number in the company until they found someone who'd say "That sounds do-able." Upon which they'd demand a price reduction because "Your product doesn't do what you said it does."
dragonquest 13y ago
The overlooked bid in this case was by Vinay Deolalikar for $1000000 who simply said "I think I have done this." For background, Vinay was a researcher at HP Labs, Palo Alto who made a serious attempt at solving the problem (independently from this bid :P).
runeb 13y ago
I like the guy who guarantees the solution will be "100 % W3C compliant"

Evgeny 13y ago

That looks like another 'FizzBuzz' filter to me, just more elaborate - in this case, KurtG appears to be the one to pass the screen, right?

jimbokun 13y ago
I am SO tempted now to add this to our standard interviewing questions list. At least for anyone claiming a CS education.
- endersshadow 13y ago
  Why? This is a miscommunication issue, not a CS issue. Determining whether or not something runs "infinitely" is typically just, "Does it run longer than an acceptable amount of time?" It may not actually run infinitely, but it may run practically infinitely (which is to say, just very long). You have people responding that are assuming that they're going to test if a process takes too long and bail if it does. Pretty simple, actually, since for all practical purposes, when somebody describes a program as "taking forever," they rarely mean "forever" literally. If you want to ask it, go ahead, but understanding practical limitations and engineering to those is a perfectly acceptable answer for the context of the rent-a-coder site (and an interview for a coding job). The only time it's not is if you're interviewing for some sort of academic position.

niggler 13y ago

Unfortunately, the situation has only gotten worse in 2013

belovedeagle 13y ago

Frankly, I think this shows that the "jokers" don't know what they're talking about either. Yes, the problem is undecidable in general, but one could certainly develop an interesting program that solves the problem sometimes, and can definitively report when it cannot decide the problem [in a given number of steps, for some value of "step"]. The halting problem is not some black hole such that when you dare venture into it, your program will be lost never to "return;".

belovedeagle 13y ago
In fact, come to think of it, for any program which 1) uses a bounded amount of memory and 2) has a bounded input (taking "input" as broadly as possible), the halting problem is always decidable in 2^[bits of state] "steps". There are a lot of programs which satisfy (1) so long as (2) is satisfied, and if (2) is not satisfied then the halting problem is not an interesting problem at all.
- just2n 13y ago
  The approach would be to fix an upper bound on memory and to enumerate all possible state, running the program each time and determining if all cases terminate or if any runs forever? I think the real crux of the problem is that you can't determine in any of those cases whether the program is going to terminate. Consider bogosort or a brute-force algorithm for solving travelling salesman. These can take millions of years to complete even for small input sizes. Do we consider that an "infinite" runtime?
  - belovedeagle 13y ago
    No, the algorithm is to run the program and see if any state is repeated; if it is, the program is in an infinite loop (where "state" means, roughly, all memory and remaining length of input). Of course, this requires 2^[bits of state] bits of memory, and a similar amount of time. Obviously an interesting (read: approximate) solver would use tighter heuristics.
  - sp332 13y ago

absherwin 13y ago

Writing a program to determine if another program will complete, error, or run indefinitely is quite doable given reasonable constraints: Run the program! One need only specify some reasonable length either equivalent to infinity for such a program, use a heuristic of checking whether the program is in the same loop and if so, whether any of the variables involved in determining loop termination are changing. Of course, proper security precautions are required.

X-Istence 13y ago
You forgot about the butterfly. Even if it looks like nothing could change, something could due to a bit flipping in memory, which would allow the program to halt.
- absherwin 13y ago
  Right. Any statement that the program is in an infinite loop will usually be subject to error. Of course, the real question anyone asked to develop such a program would be what runtime is equivalent to an infinite loop. Any real-world program must have a runtime bound that is predictable on invocation or it's useless.
hobs 13y ago
It also says it must take "the source code", so that means you would have to be able to build any arbitrary program from source? That would be a huge pain in the ass in general, above and beyond actually doing the things you mention.
A1kmm 13y ago
For a certain subset of problems, it is possible to do this. For any finite number of clock cycles N, in a Turing-complete language, I can write you a program which terminates but takes longer than N cycles. There is therefore no value of N which will consistently give the correct results in your program. Turing machines have an infinite tape, so under a Turing machine model, there are infinitely many loop termination conditions, and so it is possible to craft a program which never repeats the same state within N cycles for any N but still terminates. If your machine is finite state (with no inputs) and s possible states, rather than a Turing machine, you can check if the program halts: halts s program initialState = do seenState <- newBooleanArrayOfSize s setBooleanEntry seenState initialState halts' initialState where halts' state0 = if state0 == HaltingState then return True else do seenAlready <- getBooleanEntry seenState state0 if seenAlready then return False else state1 <- nextState program state0 setBooleanEntry seenState state1 halts' state1 In practice, s might be very large (even a 64 bit integer in the state will contribute 2^64 to s) so this algorithm isn't necessarily usable in practice, but it does complete in finite time.

comex 13y ago

Although anyone worth their salt should recognize the halting problem, I'll point out that the vast majority of programs can be proven to terminate or not, and although testing for halting in particular isn't especially useful for real-life programs, it could be used as a benchmark for a more general theorem-proving tool of the sort that would be very useful for avoiding bugs. Of course, a tool that could automatically prove useful properties about programs with no guidance, which would be significantly superior than all existing practical program analysis tools which require quite a lot of guidance, might be beyond the capabilities of the people that post bids for $300. Unless it used Mechanical Turk. :)

cynicalkane 13y ago
There exist research programming languages that support 'total functions', that can be proven to always halt. Usually you divide the world into functions and cofunctions, and data and codata, the latter of which may be infinite (such as I/O). I wish this were a more popular thing. When I write a function, I can probably enumerate in my head all the things I want it to do, and not halting usually isn't one of those things. But the instinctive reaction is to worry about Turing-completeness, which is puzzling. When's the last time you wanted a program with fundementally unprovable behavior?
- Ezku 13y ago
  Programming with such functions is called total functional programming. Here's a nice little introduction to the subject[1], and if you're a fan of code and math you should probably check out the other blog entries as well. [1]: http://blog.sigfpe.com/2007/07/data-and-codata.html http://blog.sigfpe.com/2007/07/data-and-codata.html
- btilly 13y ago
  When's the last time you wanted a program with fundementally unprovable behavior? I'm working on one today. I'm analyzing a data set for tens of millions of possible statistical anomalies, and I'm putting my "investigate further" threshold to statistically one in billions. Each thing added increases the size of the search space. Knowing that it is extremely unlikely to run forever really is good enough. Proving that it won't is a non-issue for me. (Right now it takes several hours to run.)

kens 13y ago

If you click through to the screendump of the bids there are some pretty obscure jokes besides the obvious KurtG and GeorgeCantor. BusyBeaver is another computability joke, solving "in the most productive manner possible". chn's bid is in infinite-radix numbers. The HaltLib.NET library is claimed to work in PNG and BNF among other languages. J. S. Carberry is a mythical Brown professor started as a practical joke in 1929; the backstory is interesting: http://students.brown.edu/College_Hill_Independent/?p=2127 http://students.brown.edu/College_Hill_Independent/?p=2127

xyzzy123 13y ago

Actually one of my colleagues had the opposite (yet in my opinion equally hilarious) problem with rent-a-coder - the code was much better than he wanted. He wanted sample vulnerable Java code to use for secure development training. None of us enjoyed writing Java web apps, so this seemed like a cunning plan to get sample (yet custom) code with minimal effort. Hopefully, full of bugs. He asked for a "task tracker" (IIRC, might have been phone book), and specified Java with "no framework" as the implementation language. He chose the dodgiest bidder he could who looked like they might finish the job. I think he put a few gotchas in the specifications. Actually, as delivered, the app was solid, and based on JSF2 ;) What I learned about rent-a-coder: * There are corporate refugees who do this on the side to make extra money. * CRUD apps appear to be a sweet spot for rent-a-codering. * Code quality is hit-and-miss if you're looking for disasters ;)

deleted 13y ago
[deleted]
raverbashing 13y ago
That's funny, how come this person was the dodgiest bid of all? Well, maybe he should have specified he wanted an insecure application (or an "extra secure" application - expected result is having several layers of snake oil and "proprietary solutions" applied)
- xyzzy123 13y ago
  Bidding was decided based on communication style, low bid, low GDP country and "has feedback on just 1 or 2 projects" (minimal, but not extensive history of delivering). Didn't ask for "extra buggy" or "extra secure" because the ideal was the combination of honest mistakes and laziness that turn up in real code all time. I like the idea though ;) I mean, you'd think that for $100 or whatever all up, they would have half-assed it a bit ;) Probably the mistake was to stop at n=2 and not choosing a harder problem domain.
  - aptwebapps 13y ago
    I love a good anti-anecdote (antidote?) ;) Here's one potential problem with the selection criteria: "low bid, low GDP country". I might have been better to weight the bid with the GDP (I don't mean really crunch the numbers, just put your thumb on the scale). But more to the point, if your friend didn't have a lot of experience with this sort of thing, he probably wasn't that good at picking a bad apple. Or he just got unlucky, maybe.

lifeformed 13y ago

What would happen if you went through with it? I bet it wouldn't be too hard to write a program that does it for 90% of cases. Is there a simple case that would be impossible to determine?

eru 13y ago
Oh, the halting problem is easy enough to solve for most cases (people do it informally all the time), just not for the worst cases. For giving a percentage, you need to specify a distribution of programmes first. E.g. programmes created reading from /dev/random, or programmes downloaded at random from the internet, or something more sensible.
zura 13y ago
Exactly. The first reason to reply to this kind of request would be to engage with the uneducated client, and make sure that she will pay for that 90%.
rcfox 13y ago
Off the top of my head: 1) Assuming rand(x,y) gives a uniform distribution between x and y: for (int a = 0; a < INT_MAX; a += rand(-1,1)); 2) I can't find the source any more, but someone basically implemented a big int library with bit twiddling to allow for an upper bound on a loop that would finish after the heat-death of the universe, assuming generous CPU specs. Not infinite, but also non-terminating. 3) Anything that makes a system call. You might never get scheduled again!
- StavrosK 13y ago
  #2 isn't any more non-terminating than "for (i=0; i < 100; i++)" is.
- dagw 13y ago
  As to 1) any rand() implementation that doesn't use an external source of randomness is deterministic and cyclical, thus it is quite possible to determine if 1) halts by analyzing rand()
13y ago

barking 13y ago

Is it money up front or c.o.d on those sites? Trying to get my head around why people bid without having a clue what`s entailed

Evgeny 13y ago
I believe that if the developer's bid is accepted, the money goes into the 'escrow', which is the main purpose of the site: make sure that the developer does not go unpaid if he did the work. If the customer is not happy, there are some sorts of resolution processes that I don't know much about. What surprises me is that the clueless developers also had high 'reputation' (positive customer feedback), which should be at least some indication about their competence.
- noptic 13y ago
  They do not really read what the customers want until the bid is accepted. foreach(newProject as project){ new Bid( projeckt.averagePrice * 0.8 ), "We are the best nd have done this many times"); } In the most cases they can really solve the problems and get good ratings. Some clients include a "password" in the project description and ignore all messages without the password.

zura 13y ago

It looks like a recruiter, but the other way around :)

asveikau 13y ago

I don't know about all the rest of you, but I find it really depressing to read these rent-a-coder sites. The first thing that strikes me is that people posting projects don't really understand the value of software engineering. They want someone to do crazy ambitious projects for pretty much no money. As if to say, "I have this idea which is really awesome and valuable, now I just need some monkey to do all the work." $500 should be enough for that, right? Then I'll cash in on my awesome idea... Maybe some projects honestly work out like that. But a lot of the projects I see on these sites fall outside that scope. For big ambitious projects, we all know programmers are not fungible resources, and competent execution matters. But the worst part is that people humor these projects, or more likely take advantage of the gullibility of the people asking for them... "Yes sir, I can solve that impossible problem promptly and under your budget of $500." It's really sad.

jiggy2011 13y ago
It's easy enough for us to say that people don't appreciate the value of what we do but really market value is set by supply and demand. Not everyone lives in San Francisco or New York where they feel they must bill $100 p/h just to make rent. A smart person in an emerging economy where $500 per month puts them on a higher part of the local income curve could certainly realize that they can compete in a global marketplace on price. This does not necessarily make them incompetent, in fact it's not a bad way to "hack" oneself out of poverty. Besides, many software applications are alternatives to excel spreadsheets or to handwritten HTML websites and don't necessarily require the hippest programmers who are well studied on the latest technologies. A customized rails scaffold can go a long way to solve a lot of real business problems, and doesn't HN often talk about the value of producing an "MVP"?
- asveikau 13y ago
  There's truth in the idea that a first world salary might go further elsewhere in the world, and that lots of people get by on less ... But I suggest you look at getacoder.com et al. and see what I was really talking about, because it can't be explained only that way with no other explanation. I once saw a project similar to something that took a former employer 10 years to iterate on and finally get right, with a long tail of bug fixes and crazy corner cases because it is a difficult problem. The rentacoder "cost" was 2 weeks and less than $1000. I did not follow up with that particular guy's project but I'm going to guess that they did not have success with those expectations and that budget.

Luyt 13y ago

I liked this reaction, from KurtG: Dear Mr T., Your problem is very much like I have been considering. Assume that we have a consistent and complete axiomatization of all true first-order logic statements about natural numbers. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm N(n) that, given a natural number n, computes a true first-order logic statement about natural numbers such that, for all the true statements, there is at least one n such that N(n) yields that statement. Now suppose we want to decide if the algorithm with representation a halts on input i. We know that this statement can be expressed with a first-order logic statement, say H(a, i). Since the axiomatization is complete it follows that either there is an n such that N(n) = H(a, i) or there is an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until we either find H(a, i) or its negation, we will always halt. This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false. There is no way your application can be built, and for this advice I am willing to waive any fee. Sincerely, K. Gödel.

raverbashing 13y ago
"But the other guy says he can build this in Java in 50 days, I think you're not as smart as he is"
- pekk 13y ago
  The boss is always right
deleted 13y ago
[deleted]

tzaman 13y ago

We had exactly the same frustrations with online outsourcing (being on both sides of the table), and now we have built https://codeable.io https://codeable.io (focused only on WordPress for the time being) - 4 months after launch, we have more than 900 jobs posted, half of them completed, excellent reviews, more than $45k in revenue. I'm very proud of what we achieved so far, because we eliminated the biggest "pains" of online outsourcing; There is no bidding, our (invited and reviewed) contractors form a single estimate which is then presented to the client. And we focus on sub-$500 tasks, because the margin for error is significantly smaller, so if a client comes in with a huge job, we help him break it down into smaller pieces. We also maintain client/contractor ratio, so there is no need for contractors to compete with one another, anyone who wants to work, can work.

jpdoctor 13y ago
> so there is no need for contractors to compete with one another Why would buyers desire this?
- tzaman 13y ago
  Because first and foremost, we want to keep contractors happy. If they are paid well (by well I don't mean ripping clients off), they will come back and perform more work. Our long-term goal is to establish a trusted network of developers that always go that extra mile to satisfy clients - I must admit, so far, this approach has paid off in dividends. We're currently re-designing the landing page, and we will put client testimonials on that prove it.
  - jpdoctor 13y ago
    > and we will put client testimonials on that prove it. I'll be curious to see which client gives you a testimonial that thinks non-competing contractors is a great idea.
    - tzaman 13y ago
      Each and every, in fact. Because they don't come to us to see how (or not) our system works but to get their problems fixed in time, and by a top quality expert. (I'm saying this because we do a lot of research on both sides, and transparency is part of our business, so all involved know how the system works)

ak39 13y ago

Isn't the joke on the guy posting the (impossible) job? I see some have commented on the economic desperation or the salesman attitude of the coders bidding for this impossible job, but when someone asks a large population of salesmen that they have a serious intention to procure a bridge ... well ... there will be a few who'd definitely show up wanting to sell one. Don't see the point of this whole thing really.

prakashk 13y ago
> Isn't the joke on the guy posting the (impossible) job? No, considering the poster's name is "AlanT"!

noptic 13y ago

client: I need a software tht can find information about my mp3 files online and it must work 100% correct me: What information do you have and what do you want to look up? client: I have the folder and file names and there are 5 webpages like google where you can search for music. I want the programm to get the right song info from this. BUT IT MUST WORK 100% right no error ever! I had 6 other programmers try it but no one can make it right! (the real clients english was even worse)

DanBC 13y ago

So, what's best current practice for naive clients when trying to hire designers or programmers? Is that advice online anywhere?

dmead 13y ago

what if that program finds bugs in itself? wheres your god now?

th0br0 13y ago

How come that there's a new getacoder project that invites all those users who gave those fabulous comments? http://www.getacoder.com/projects/simple_meteorjs_app_157993.html http://www.getacoder.com/projects/simple_meteorjs_app_157993...

adamrneary 13y ago

To me, the disappointing thing about this spoof is that it treats the engineers on this platform like "code monkies." One of the biggest gripes from top tier engineers is that they hate being treated like animals by jerky business guys, and here we have a group of people mocking these engineers and the platform. It all seems disrespectful to me. describe 'My experience, -> _.map ['amazing','awful'], (quality) -> _.map ['engineers','business guys'], (role) -> _.map ['Brooklyn','online platforms'], (place) -> assert "There are #{quality} #{role} in #{place}."

lnanek2 13y ago

What's funny is that math people know this is impossible and will never attempt it, but it's quite easy to write something practically useful that does the job most of the way. It's possible for static analysis tools to identify many loops that will never end. E.g. in Java if there's no break or return and the guard is a boolean that is never written to and no runtime class loading is used. It can be very valuable to have static analysis tools in an organization, I know my own company has them, and we don't share them. IBM as well puts tons of work into it. Motorola has shared one of their tools. Every bug and issue your tool can find is one much more cheaply solved. Similarly, the client may be doing coding education, or interview, or other software where just a few limited lines and limited operations need to be checked, or it is OK to say if you hit n^4 loops you lose, etc..

skateinmars 13y ago
John Carmack also has a lot of praise for static analysis: http://www.altdevblogaday.com/2011/12/24/static-code-analysis/ http://www.altdevblogaday.com/2011/12/24/static-code-analysi...

cognivore 13y ago

The part of rent-a-coder that bothers me is I'm sure it goes like this more than we'd like: - Party A contracts with Party B on a big software contract. - Party B sub-contracts on some of it to Party C, D, & E. - Party E is a bit dodgy and does a bunch of rent-a-coder. - Hey it compiles! It gets passed up the line. - Party B is late and just passes it on. - Party A is late and, "Hey, it works!" and delivers. - Hilarity does not ensue. My personal experience with this kind of thing is that the further away from the actual concerned party you are (in other words, the people who are going to use the software), the more likely it is that the software is going to be wrong.

tlrobinson 13y ago

Project Creator: AlanT Perfect.

rmrfrmrf 13y ago

I don't think it's all that hilarious to waste people's time, especially when the goal is to point out the naïveté of others.

Eva_Peron 13y ago

I have an uncle who is a deposed King of Nigeria who will solve this problem for you for a small deposit and your bank account information. :-)

stcredzero 13y ago

Hmm, the last time I commented on HN on this rent-a-coder hilarity, someone proposed "writing a new scripting language" within a week. I suggested that this was actually doable within a week. One could just concoct some simple language with curly braces that maps 1-to-1 with a procedural subset of Python, then output Python to run it. The result? I was downvoted by some less than informed individuals who thought there was some deep fundamental difference between curly braces languages and whitespace significant ones. What The!?... On HN!? This was before Coffeescript was a widely known thing as it is today. Think what you'd like about Zed Shaw, but his "DB Invasion" idea has some merit.

nijk 13y ago
Heh. JavaScript was famously invented in a week.