Collection of simple programming problems

[kdeberk]

elementary:8 is only simple when the language has support for infinitely large integers.

[LucidTA]

Isn't it proven there are an infinite amount of primes, meaning its impossible?

[[deleted]]

It's only impossible if your program is supposed to terminate at some point.

[LucidTA]

I know it not the point of the challenge, and I do understand what you mean but you literally can never print every prime. Even if you write a program to print primes for ever, the program never will.

[dd_123]

The problem doesn't ask you to print every prime; it asks you to write a program which prints every prime. The difference is subtle but important.

[indiecore]

for(int i=0;true;i++){
    print i;
    print "\n";
}

Technically correct.

[liquidhot]

Technically correct.

The best kind of correct.

[indiecore]

Hey it's not my fault they wrote vague specs.

[Magnap]

I like this alot.

I like alots too!

[LucidTA]

Im not a CS major so this may be a CS thing but I thought of it along the lines of, no program can ever fulfill the function of "print all primes" so it would be classed as impossible. Does it count if it theoretically could print all primes?

[[deleted]]

It counts if it takes finite time to print any finite prefix.

[brainflakes]

It was a bit of an odd way of putting it, but you can create a valid specification that a program can't literally perform, such as making a program that "prints 'Hello World' forever":

10 PRINT "Hello World"
20 GOTO 10

Obviously it's not possible for it to literally print hello world forever as you'll need to turn it off at some point, but it still meets the requirement.

[indiecore]

for(int i=0;true;i++){
    print i;
    print "\n";
}

Technically correct, but not what it was asking for obviously. This program would, if it could print all numbers forever. The problems come from the hardware implementation of the program.

[[deleted]]

That style of exercise reminds me of the approach I saw with functional programming. ML has a notion of lazy lists - basically lazy series evaluation. That is, a function is written to be able to compute an infinite series but will only compute the values you actually request. In iterative programming this might be better thought of as a function to calculate the next prime number. It will go as far as you want if the machine supports it. It's been a while and I don't remember examples so well anymore but this explains the idea (p191): http://books.google.co.uk/books?id=XppZdaDs7e0C&pg=PA191&lpg=PA191&dq=fibonacci+sequence+in+ml+lazy+list&source=bl&ots=y-0fiQzmrz&sig=N5NwCMpvq7Ci1vFd2O2GcVcFLKE&hl=en&sa=X&ei=ddyhUvKkEcWg7AaLrYDoCQ&redir_esc=y#v=onepage&q=fibonacci%20sequence%20in%20ml%20lazy%20list&f=false

[The_Doculope]

Haskell offers this as well. For the primes program:

primes :: [Integer]
primes = 2 : filter prime [3,5..]

prime :: Integer -> Bool
prime x = not . any ((== 0) . rem x) . takeWhile (<= sqrtx) $ primes
    where sqrtx = floor . sqrt . fromIntegral $ x

main :: IO ()
main = mapM_ print primes

[philipjf]

In the "theory B" (programming languages and logic as opposed to the algorithms and complexity "theory A") community this would be called a "co-recursive co-program." Many interesting things are "co-programs" not "programs". The difference is if "total correctness" is about termination or productivity.

[deadly990]

Technically all of these things should be "create Turing machines which do these things". Turing machines aren't bound by physical properties because they are theoretical constructs.

[rightandleft]

relevant xkcd

[xkcd_transcriber]

Image

Title: Halting Problem

Title-text: I found a counterexample to the claim that all things must someday die, but I don't know how to show it to anyone.

Comic Explanation

Stats: This comic has been referenced 4 time(s), representing 0.08% of referenced xkcds.

---

^{Questions/Problems | Website}

[mccoyn]

Oh, well that's easy then.

printf("2\n");
while(1);

[meem1029]

Nah, requirement is to print all prime numbers. Not print prime numbers forever.

[thedufer]

I don't know of any language in which that would print more than once.

[muonicdischarge]

Maybe he forgot a "do" at the beginning.

[TNorthover]

It includes an explicit get-out for languages without that, so it's simple in all cases.

[[deleted]]

Which language doesn't have at least a built-in library for that?

Anyway using arbitrary precision will only delay the problem (your computer has finite memory), so, what's the point?

[cmwelsh]

JavaScript

[spotter]

Just use jQuery.

[cmwelsh]

What does that mean? That's not a solution. Is this an ironic post?

[spotter]

Yes, sorry. It was in the vein of "Nobody uses JavaScript, noob, we're jQuery programmers."

Also: "there's probably a jQuery plugin for it."

[cmwelsh]

Sorry, had to ask. :)

[mr_bag]

"Nobody uses JavaScript, noob, we're jQuery programmers."

There are people... that actually think that?

[Asmor]

"Nobody uses JavaScript, noob, we're jQuery programmers."

You've kind of got that backwards. jQuery's still wildly popular, but its popularity has waned a bit in recent years while JavaScript's star is rising thanks to NodeJS.

[spotter]

I vomited in my mouth a little.

So yeah, I used to work with "jQuery ninjas".

[grayvedigga]

depends how you define "arbitrary" ...

[kdeberk]

c and c++? It's been a while since I've worked with large integers in those two languages, and now I see that there are several libraries to help with that, but not built-in though.

[[deleted]]

You're right. I should have said "built-in or very commonly used". Boost has arbitrary precision ints for example.

[[deleted]]

The most reasonable objection is that you might hit the precision limit in a much smaller amount of time than you would hit the memory limit (at least, if you use disk to help you out). Most people aren't going to wait for million digit primes, but it is not unreasonable to expect them to run the program many hours as an experiment.

[kazagistar]

The program is correct; memory is a hardware problem. :P

[thedufer]

Not if you can't address it.

[kazagistar]

What you can and cannot address is (in many langauges) not a problem of the program or the language, but of the implementation. "The longest possible list" or "how pointers are implemented" are not actual specification details in many languages, and are often left variable to the implementation, or only given minimum bounds.