ANyways, so... I was reading The Pragmatic Programmer [1] and it occurred to me that we should probably boil these principles down for the novices amongst us. ITT things you want to carve into your colleagues' faces.
* KEEP IT FUCKING SIMPLE, MOTHERFUCKER!
* You're code is not ``clever'', it is autistic.
* Code is /not/ poetry or art. Go away! Fuck your OCD.
* This shit has been solved a thousand times over.
* You do not need to design with the latest and greatest in gang-of-four approved OOP design patterns, using infinitely scalable NoSQL solutions in hip new languages that compile down to JavaScript (srsly WTF?!), just to create a CRUD application.
* Not everyone gets off on code, some of us just want to make a living doing the least amount of effort that is required to deliver a consistent quality for an extended period of time.
I swear by god if I see one more AbstractControllerFactoryInterface
You do not need to design with the latest and greatest in gang-of-four approved OOP design patterns, using infinitely scalable NoSQL solutions in hip new languages that compile down to JavaScript (srsly WTF?!), just to create a CRUD application.
I don't even know what that means!
This issue largely comes from traditional CS curriculum (SICP included). They start off by saying that complexity and abstraction are good things (only in moderation), "premature optimisation is evil" (it's never premature), and use those as arguments to convince the students that all software needs to be multi-layered elephantine systems broken up into hundreds of classes, packages, design patterns, and other cruft.
Quoting from the first SICP lecture:
"And these techniques for controlling complexity are what
this course is really about. And in some sense that's really
what computer science is about. Now that may seem like a
very strange thing to say, because after all a lot of people
besides computer scientists deal with controlling complexity. A large airliner is an extremely complex system. And the aeronautical engineers who design that air, you know, are dealing with the men's complexity. But there's a difference between that kind of complexity and what we deal with in computer science. And that is that computer science in some sense isn't real. You see, when an engineer is designing a physical system that's made out of real parts, the engineers who worry about that have to address problems of tolerance and approximation and noise in the system. So, for example, as an electrical engineer I can go off and easily build a one-stage amplifier or a two-stage amplifier, and I can imagine cascading a lot of them to build a million-stage amplifier, but it's ridiculous to build such a thing, because by the --- long before the millionth stage the thermal noise in those components way at the beginning is gonna get amplified and make the whole thing meaningless. Computer science deals with idealized components. We know as much as we want about these little programming data pieces that we're fitting things together. So there's... We don't have to worry about tolerance and that means that in building a large program there's not all that much difference between what I can build and what I can imagine. Because the parts of these abstract entities that I know as much as I want. I know about them as precisely as I'd like. So as opposed to other kinds of engineering where the constraints on what you can build are the constraints of physical systems, the constraints of physics and noise and approximation, the constraints imposed... in building large software systems are the limitations of our own minds."
Rubbish. CS is as real as any other science. Computers are physical entities in this universe like any other, and need to obey the laws of physics too. Thinking that abstraction and complexity has no cost is stupid.
(I enjoy some SICP myself but that's just mental masturbation.)
Name:
Anonymous2013-05-09 10:45
>>6 Computers are physical entities in this universe like any other, and need to obey the laws of physics too. Thinking that abstraction and complexity has no cost is stupid.
B-B-But, think of the purity !
Indeed. Programming only feels limited by the mind when your mind stays within the boundary of what's feasible.
Name:
Anonymous2013-05-11 0:33
>>16
When I program, I feel limited by hardware and preexisting software quite often.
For instance, when I program in C, I want for a more natural dynamic array type.
Not to mention primitive types greater than 2^64, easy-to-implement concurrent execution of loops, a sane way to provide syntactically-sweet language extensions (C++ classes/operator overloading are NOT sane), the list goes on...
>>9
The cost of the sequential machine abstraction is far less significant than the flexibility it provides... at least for most tasks. But for everything else... have you heard of FPGAs?
>>17 When I program, I feel limited by hardware and preexisting software quite often.
That's why CS is engineering just like any other type of engineering; you have to work within the constraints of the system you're building. For instance, when I program in C, I want for a more natural dynamic array type.
If you're irritated by that then move to C++ and use std::vector, although then you have not much control over resizing/allocation.
Not to mention primitive types greater than 2^64, easy-to-implement concurrent execution of loops, a sane way to provide syntactically-sweet language extensions (C++ classes/operator overloading are NOT sane), the list goes on...
All those things have additional costs, and making them easier to use encourages overuse where they're absolutely NOT needed. "Let's make all integers arbitrary-precision, then we'll never have to worry about overflow!" >>18 is an example of that. Now your code is a few orders of magnitude larger than it really needs to be, and correspondingly slower. Dynamic arrays are a perfect example of this, and IMHO not having them by default in C makes you think more about whether you actually need them in the first place, possibly making you reconsider and come up with a simpler algorithm (static allocation, in-place streaming) that does not require them.
One of my favourite interview questions is something like this:
"Write a program, in your language of choice, that adds line numbers to a file by prefixing each line with a decimal integer followed by one space. You may assume files have no more than 2^32-1 lines." No hints (you should try this youself) but I can tell you that if you thought of needing an array of some sort, you're not getting the job.
Name:
Anonymous2013-05-11 8:38
>>19
Are you kidding me? That's question requires almost no effort at all. perl -pe 's/^/$. /'
Name:
Anonymous2013-05-11 8:47
>>20
hahhaha cudderfag doesnt know what a regexp is
>>22
Ok so an iterative method is what you want, correct?
I don't see why anyone would use an array for this, unless they're a very inexperienced programmer.
I don't get it. There's got to be a buffer SOMEWHERE to do this, even if it holds only one element/char (a la code]char tmp;[/code]), so how would it be possible without? Or is this what you meant?
Allow me to rephrase >>18.
TURING COMPLETE MACRO SYSTEM TO PROVIDE ANY ABSTRACTION YOU WISH TO HAVE ON TOP OF YOUR MEMORY INSECURE STATICALLY TYPED STACK BOY SCOPED NOOB LANGUAGE
Using a static array is an optimization over using a dynamic array. It can be performed if the compiler is aware of an upper bound to the length of the array. This should be built in to the language: an array with an upper bound provided by the programmer. The upper bound can then be statically verified (to the fullest extent possible), tested dynamically with assertions, and taken for granted in the release.
In place streaming is one way to evaluate a lazy map/reduce. So you're favorite lazy functional language can do this too, although you typically wont have control over the buffer size.
Hint #3: When I gave the "no array" hint, I was thinking more of what you're thinking to do with the array than whether or not there is one. (Memory is a big array. Another hint there...)
>>34 is the closest so far, but screwed up severely at >>39. Recursion is not necessary for this problem either, so even if you didn't have >>39 you wouldn't have passed.
[Why is this reminding me of FizzBuzz? It shouldn't be that much harder, but some of you are providing solutions that would be the equivalent of writing a FizzBuzz that doesn't work for numbers greater than 15 (another hint).]
I'll leave you with a final advice: Read the problem statement carefully, preferably 2 or more times. Does your solution work for all of the problem space? Think about it.
void print(unsigned int x)
{
unsigned int q, z;
for (q = 1000000000; q > 1; q /= 10) {
z = x / q;
if (z) putchar('0' + z % 10);
}
putchar('0' + (x % 10));
}
int main()
{
unsigned int i = 0;
int c;
while (EOF != (c = getchar())) {
print(i++);
putchar(' ');
do {
putchar(c);
} while ((c != '\n') && (EOF != (c = getchar())));
}
return 0;
}
I did not know C but I have tried to do something pausible, and now you are digging requirements out of nowhere. What is it now? I have not got time for that. Adios!
I knew Cudder氏 would not give up for anything but her own (which is impossible for me). I'd better stick to a dumb physics, chemistry or architecture undergrad. ;__;
Name:
Anonymous2013-05-12 13:27
Have some slow as fuck x86 code. But hey, no arrays. Though I don't get the comment about memory being an array, you wouldn't be able to make syscalls without it.
Hello, I'm a beginner programmer so I don't really know how files work. Can you just use the end of the file as a queue? You need to append to the file at one point anyway because of the line numbering increases its size. I'm thinking of something like:
keep line counter i
loop: read character and enqueue it
if the character is '\n' add "i " into the queue and increment i
if the character is EOF organize the queue into an array and we're done
print next character in queue to replace the read one and loop
Please tell me how I'm wrong.
Name:
Anonymous2013-05-12 14:32
#include <stdio.h>
#include <stdlib.h>
int main(void) {
unsigned line = 0;
char c;
while((c = getchar()) != EOF) {
printf("%u ", line++);
do
putchar(c);
while((c = getchar()) != EOF && c != '\n');
putchar(c);
}
return EXIT_SUCCESS;
}
amirite?
Name:
Anonymous2013-05-12 14:58
From Cudder's broad description of an array it sounds like the task is the equivalent of programing a Turing machine without any tape.
>>49
I have not read K&R because I do not have one. But stdio.h says int putchar(int) and int getchar(), that is why they are being pedantic I guess. Anyway I do not know how could char be wrong, since char is signed, ASCII uses only 127 values and EOF == (char)EOF.
>>51
Fuck you copycat, murderer, you tried to be ``clever'' but just introduced a bug and ruined my code.
>>42
Nothing. As I said above, it's more to do with how you use it than whether or not there is one.
So now we have another C solution that's much closer to passing, another broken C solution, Asm that's not much better than what a compiler could do... but not a single remark on why attempts like >>20 and >>30 don't work for all of the problem space! All you did was get hung up on one comment about the use of arrays; I intended that as a hint to get you thinking about the problem in the right direction, not as a "thou shalt not".
Keep on trying. Not trying as in writing more possibly broken code, but as in actually thinking about the problem...
Name:
Anonymous2013-05-13 8:21
You got a pdf brah? All I can find are shitty CHM converts of that book
>>64
So I've read through all of the answers, and it looks like your real problem is files with individual lines stretching beyond 4GiB, or 16EiB, or whatever, which would mean that your catch is `you better not store each line in an array as you read it in.' Okay, fine. That gets rid of >>20.
Another possible issue you're having is that the trivial file '' is not numbered correctly. I.e.
foo
bar
baz
quux
should become
1 foo
2 bar
3 baz
4 quux
5
? I don't agree with this myself for religious reasons, but I think it's something you might do, as it eliminates pretty much everyone and fits with your desire to say `the PROBLEM SPACE!' as you point out, smugly, that an empty sequence of 0 bytes is a valid line. Then the exiting of >>34 would also be caused by the specific (EOF != (c = getchar())) segment, though the problem with it is `it exits too fast' instead of `it uses in-comparison =' or `it assigns char/int wrong' as everyone has been assuming.
It hasn't been you specifically who complains about I/O buffers being arrays, so I'll assume getchar and putchar are fine. That means that if I don't do anything stupid like readline and make sure to number correctly, this should fit your (poorly-communicated) requirements:
#include <stdio.h>
int main(void)
{
unsigned int ln = 2;
int i;
printf("1 ");
i = getchar();
while (i != EOF) {
putchar(i);
if (i == '\n') printf("%u ", ln++);
i = getchar();
}
return 0;
}
As a final note, you should rephrase the question to point out that the line numbers must be correct, as 0 is a perfectly valid decimal integer that can be prepended to all lines. You should also clarify that this need not be done in place, if that is truly your intention.
>>70
No way she is so dumb!
There were TM jokes, maybe she wants these sort of jump tables people use for emulators:
#include <stdio.h>
void print(unsigned int x)
{
unsigned int d = 1000000000;
while (d > 1 && x / d == 0) d /= 10;
while (d > 1) {
putchar('0' + x / d % 10);
d /= 10;
}
putchar('0' + x % 10);
putchar(' ');
}
int main()
{
unsigned int i = 1;
int s = 1, c = getchar();
while (c != EOF) {
switch (s) {
case 1:
print(i++);
putchar(c);
s = 0;
break;
case 0:
putchar(c);
s = (c == '\n');
break;
}
c = getchar();
}
return 0;
}
or with a fall-through:
switch (s) {
case 1:
print(i++);
s = 0;
case 0:
putchar(c);
s = (c == '\n');
}
Name:
722013-05-13 10:53
Oh, I do not even need the s = 0; in the fall-through switch...
So, last submission:
#include <stdio.h>
void print(unsigned int x)
{
unsigned int d = 1000000000;
while (d > 1 && x / d == 0) d /= 10;
while (d > 1) {
putchar('0' + x / d % 10);
d /= 10;
}
putchar('0' + x % 10);
putchar(' ');
}
int main()
{
unsigned int i = 1;
int s = 1, c = getchar();
while (c != EOF) {
switch (s) {
case 1:
print(i++);
case 0:
putchar(c);
s = (c == '\n');
}
c = getchar();
}
return 0;
}
An idea: most of these C solutions don't work for the (231−1)th line number. Maybe Cudder is hinting at something like this, with the whole "problem space" thing:
#include <stdio.h>
int main()
{
unsigned int i = 0;
int c;
while (EOF != (c = getchar())) {
if (i == 0xffffffffUL)
printf("4294967296 ");
else
printf("%u ", ++i);
do {
putchar(c);
} while ((c != '\n') && (EOF != (c = getchar())));
}
return 0;
}
PS: The only reason anyone is having trouble solving this is because you're shit at explaining the problem. There's no reason to act smug about this, and you should really cut it out.
Name:
Anonymous2013-05-13 11:59
>>76
Is it really you? Is it destiny we are coming back to this cesspool. I have also recently started visiting this board again. Check out my ☆★Prog challenge [Physiks]★☆, just like the good ole days except no Physics ;) I actually moved to Physics, after CS degree is complete. How's life treating you old friend.
>>77
Nope, Xarn never posts onymously without a tripcode. I thought my post felt kinda Xarn-y, though, so I figured it'd be a nice homage to put that in the name field.
(If the real Xarn reads this: I hope you appreciate having become a symbol of non-shitposting.)
Name:
Anonymous2013-05-13 12:26
>>78
>Xarn
>non shitposting
guess how many you should pick
Name:
Anonymous2013-05-13 12:38
>>75
I am wrong, okay? As you wish: #include <stdio.h>
int main()
{
unsigned int i = 1;
int s = 1, c = getchar();
while (c != EOF) {
switch (s) {
case 1:
printf("%u ", i++);
case 0:
putchar(c);
s = (c == '\n');
}
c = getchar();
}
return 0;
}
>>76 Fuck you, do you really think I have not tested unsigned int bounds?
Well, 2³²-1 equals UINT_MAX, so as long as the file has no more than 2³²-1 lines (4294967295), the program is right.
Of course, assuming the average x86 desktop and an ANSI compiler.
Name:
Anonymous2013-05-13 12:43
it looks like your real problem is files with individual lines stretching beyond 4GiB, or 16EiB
Then it's a retarded problem to begin with, reading a file that size one byte at a time is going to take ｆ ｏ ｒ ｅ ｖ ｅ ｒ.
Name:
Anonymous2013-05-13 13:31
>>82
Let it never be said that I didn't think this problem was completely retarded to begin with. Especially the smarm of `a decimal integer,' and then not even bothering to say that it must be the correct integer. What, am I going to be a smartass and display the line number in hex, then be considered inferior to the guy who just puts `17' for each line? Because that's how the problem works as written.
Name:
Anonymous2013-05-13 13:51
>>83
And does it have to be an ASCII decimal integer?
>>87
Maybe if you read the problem, preferably the entire problem, and then think about the problem space, after having read the problem, the problem space will allow you to think (preferably twice) about the answer which is, after all, in the space of the space of answers answering the problem space, which you should think of having read, hmm? Also, please see the BIG HINTS at >>88 and >>thinkabouttheproblemspace!
Name:
Anonymous2013-05-13 14:31
Is Cudder-様 telling us to prepend the line numbers to a file that we can't even read, write, touch or think about?
Name:
Anonymous2013-05-13 15:03
Well, this is interesting. Not sure where the newline went, something weird from using null I guess. But it didn't blow up.
$ dd bs=1024 count=4194305 if=/dev/zero of=test
4194305+0 records in
4194305+0 records out
4294968320 bytes transferred in 104.261202 secs (41194310 bytes/sec)
$ gecho -e "\nline2\nline3" >>test
$ perl -pe 's/^/$. /' test
1 2 line2
3 line3
>>85,86
Read the statement again: "You may assume files have no more than 2^32-1 lines".
The maximum line would have number 2³² - 1 = UINT_MAX, and that IS NOT FSCKING ZERO.
I think you'll all just make me facepalm more if I let you continue, so I'll explain it all now.
>>67 was the closest "why". and it looks like your real problem is files with individual lines stretching beyond 4GiB, or 16EiB, or whatever, which would mean that your catch is `you better not store each line in an array as you read it in.'
Not quite. It'll die as soon as you have a line bigger than available memory. which may be several MB. Everything else you say isn't the main issue here. The main issue with the first few solutions is YOU ARE USING O(N) MEMORY WHEN YOU SHOULD ONLY BE USING O(1). That's why I said it doesn't matter whether you buffer or not. You can read in 64K at atime to buffer, no problem. But the moment you think of reading an "entire line" into memory at a time, you've FAILED.
>>70 >>34 is not correct because of getchar's return type. And it uses recursion and reinvents printf%u unnecessarily. Nothing else.
>>80
This is a pass, maybe overly complicated but if this was written on the first try it's a pass.
>>93 if you thought of needing an array of some sort, you're not getting the job.
Based on your initial statement, you should be the one without the job. Attempting to process files with lines of the sort of length you're describing without using an array to handle the data in reasonably sized chunks is ludicrous.
>>98
A "safety vent" to prevent hard crashes. You should never be running a system at that load level, because it'll be unacceptably slow. Some of the systems I work on don't even have secondary storage.
>>104
getchar and putchar will do buffering for you automatically, and they're inlined because they're macros in any good C library, so you're introducing additional overhead by buffering twice. MSVCRT's default buffer is 4K, glibc is also 4K.
>>106
This *might* be faster but you should then turn OFF stdio buffering. Either way I'm not interested in absolute speed with this question, and using 1000x the memory for <1000x speed increase is inefficient (see also: 10KB --- yes, ten thousand bytes --- implementations of memcpy() that achieve maybe a few % speedup in careful benchmarks over rep movsd and probably much less on Nehalem and Sandy Bridge).
Name:
Anonymous2013-05-15 7:47
>>113 stdio includes buffering.
And using it means violating the criteria given for this problem, resulting in horribly inefficient execution.
>>120
Yes, and you originally said to not even think of using an array, while I maintain that if you don't think of using an array then you aren't approaching the problem correctly.
>LELLELELELEEEEEEEEEEEEEEEEEEELL
>LE FAIL FOR DA E/G/IN /G/IN /G/RO
>LELELLE LE EGIN FAIL MEME
>LELELEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE GRO
Name:
Anonymous2013-05-17 4:12
>>121 Don't think, feel, and you will be tanasinn.
>>129
What the fuck are you doing? Go back to whatever shit board you came from. Your not wanted here goyim. I knew Judas should of killed Jesus earlier, so Christian scum like this one could never be born.
Name:
Anonymous2013-05-17 7:08
>>125
Bullshit. Good I/O uses buffers, therefore if I think about using good I/O I think about using arrays. If you want to say "Don't use realloc or critical section malloc" or whatever, say it. Don't pretend arrays are something they aren't.
None of you are fucking welcome here because you keep posting bad programming that keeps making the e/a/in /a/roski imagefaggot post here.
Fucking stop.
Name:
Anonymous2013-05-17 16:44
>>134
LLLLLLLLLLEEEEEEEEEEEEELLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
>LE EGIN BUTTHURT FACE
>>131
Buffers of fixed-length, buffers that you shouldn't need to think about.
Name:
Anonymous2013-05-19 14:01
>>137
Bullshit. Now you're trying to claim that people don't think about buffers when writing I/O. Just admit that your 'no thinking about arrays' statement was poorly worded.