A programming exercise

[Stefan Ram]

I have an idea for a program, yet I have not yet written and
tested it.

Here is an exercise that might be solved by this program:

Write a C program to read positive int numbers from a
user (a single int number is entered by its decimal
digits and the enter key) which are terminated by entry
of the digit 0 and the enter key, then allocate an array
of exactly the required size and then store the numbers
into this array (not including the terminating number 0).

The program may only once allocate memory with allocated
storage duration (malloc, calloc or so) (that is, for
the array mentioned above), and it shall not contain any
arbitrary limit for the number of numbers a user might
enter, although limitations of the C implementation used
might indeed impose a limitation on this number.

I will post my own solution not before 2010-02-08T05:05:29+01:00,
so feel free to post your own solution as a reply to this post.

 

[Ben Pfaff]

Write a C program to read positive int numbers from a
user (a single int number is entered by its decimal
digits and the enter key) which are terminated by entry
of the digit 0 and the enter key, then allocate an array
of exactly the required size and then store the numbers
into this array (not including the terminating number 0).

The program may only once allocate memory with allocated
storage duration (malloc, calloc or so) (that is, for
the array mentioned above), and it shall not contain any
arbitrary limit for the number of numbers a user might
enter, although limitations of the C implementation used
might indeed impose a limitation on this number.

Recursion.

 

[Ersek, Laszlo]

I have an idea for a program, yet I have not yet written and
tested it.

Here is an exercise that might be solved by this program:

Write a C program to read positive int numbers from a
user (a single int number is entered by its decimal
digits and the enter key) which are terminated by entry
of the digit 0 and the enter key, then allocate an array
of exactly the required size and then store the numbers
into this array (not including the terminating number 0).

The program may only once allocate memory with allocated
storage duration (malloc, calloc or so) (that is, for
the array mentioned above), and it shall not contain any
arbitrary limit for the number of numbers a user might
enter, although limitations of the C implementation used
might indeed impose a limitation on this number.

I will post my own solution not before 2010-02-08T05:05:29+01:00,
so feel free to post your own solution as a reply to this post.

Are you building a list on the stack via recursion?

Cheers,
lacos

 

[Kaz Kylheku]

Recursion.

Temp file.

 

[Alan Curry]

| I have an idea for a program, yet I have not yet written and
| tested it.
|
| Here is an exercise that might be solved by this program:
|
| Write a C program to read positive int numbers from a
| user (a single int number is entered by its decimal
| digits and the enter key) which are terminated by entry
| of the digit 0 and the enter key, then allocate an array
| of exactly the required size and then store the numbers
| into this array (not including the terminating number 0).
|
| The program may only once allocate memory with allocated
| storage duration (malloc, calloc or so) (that is, for
| the array mentioned above), and it shall not contain any
| arbitrary limit for the number of numbers a user might
| enter, although limitations of the C implementation used
| might indeed impose a limitation on this number.
|
| I will post my own solution not before 2010-02-08T05:05:29+01:00,
| so feel free to post your own solution as a reply to this post.
|

#include <stdio.h>
#include <stdlib.h>

struct list {
struct list *next;
int n;
};

static int *read_numbers(struct list *list)
{
char buf[100];
int val, i, *ret;
struct list node, *p;
if(fgets(buf, sizeof buf, stdin)) {
if(sscanf(buf, "%d", &val)!=1) {
fprintf(stderr, "That's not a number\n");
exit(EXIT_FAILURE);
}
if(val!=0) {
node.n = val;
node.next = list;
return read_numbers(&node);
}
} else {
if(ferror(stdin)) {
perror("standard input");
exit(EXIT_FAILURE);
}
/* Naughty user sent EOF; pretend it was a 0 but with a warning */
fprintf(stderr, "Didn't get 0 terminator. List may be incomplete\n");
}

for(i=0,p=list;p;++i,p=p->next)
/*nothing*/;
ret = malloc(i * sizeof *ret);
if(!ret) {
perror("malloc");
exit(EXIT_FAILURE);
}
for(--i,p=list;p;--i,p=p->next)
ret = p->n;
return ret;
}

int main(void)
{
int *numbers;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
return 0;
}

Another option would be to pass the count as another parameter to the
recursive function. And it should probably also return the final count so you
can know how many numbers there are (the obvious solution of including the 0
terminator in the array was forbidden for some reason).

This is inferior to a realloc loop in at least 3 ways: the malloc overhead is
probably much less than the extra space taken up by saved registers in all
those stack frames, the total available stack space is probably smaller than
the total available malloc space, and there's no chance to do any cleanup
when the stack allocation finally fails, causing sudden death.

 

[Ersek, Laszlo]

Are you building a list on the stack via recursion?

I mean a list represented by stack frames, not an explicitly linked
list.

----v----
#include <stdio.h>
#include <stdlib.h>

static long *
f(const size_t num)
{
long val, *arr;

scanf("%ld", &val);
arr = val ? f(num + 1u) : malloc(sizeof *arr * (num + 1u));
arr[num] = val;
return arr;
}


int
main(void)
{
long *p = f(0u),
val;

while ((val = *p++)) {
printf("%ld\n", val);
}
return 0;
}
----^----

(No error checking at all.)

Cheers,
lacos

 

[Phred Phungus]

Another option would be to pass the count as another parameter to the
recursive function. And it should probably also return the final count so you
can know how many numbers there are (the obvious solution of including the 0
terminator in the array was forbidden for some reason).

This is inferior to a realloc loop in at least 3 ways: the malloc overhead is
probably much less than the extra space taken up by saved registers in all
those stack frames, the total available stack space is probably smaller than
the total available malloc space, and there's no chance to do any cleanup
when the stack allocation finally fails, causing sudden death.

I don't really understand the finer points there, but I did give source
a whirl:



dan@dan-desktop:~/source/unleashed/ch11$ gcc -D_GNU_SOURCE -Wall
-Wextra ac1.c -o out
dan@dan-desktop:~/source/unleashed/ch11$ ./out
^C
dan@dan-desktop:~/source/unleashed/ch11$ ./out
3 4 5

That's not a number
dan@dan-desktop:~/source/unleashed/ch11$
dan@dan-desktop:~/source/unleashed/ch11$ ./out
345

That's not a number
dan@dan-desktop:~/source/unleashed/ch11$ cat ac1.c
#include <stdio.h>
#include <stdlib.h>

struct list {
struct list *next;
int n;
};

static int *read_numbers(struct list *list)
{
char buf[100];
int val, i, *ret;
struct list node, *p;
if(fgets(buf, sizeof buf, stdin)) {
if(sscanf(buf, "%d", &val)!=1) {
fprintf(stderr, "That's not a number\n");
exit(EXIT_FAILURE);
}
if(val!=0) {
node.n = val;
node.next = list;
return read_numbers(&node);
}
} else {
if(ferror(stdin)) {
perror("standard input");
exit(EXIT_FAILURE);
}
/* Naughty user sent EOF; pretend it was a 0 but with a warning */
fprintf(stderr, "Didn't get 0 terminator. List may be incomplete\n");
}

for(i=0,p=list;p;++i,p=p->next)
/*nothing*/;
ret = malloc(i * sizeof *ret);
if(!ret) {
perror("malloc");
exit(EXIT_FAILURE);
}
for(--i,p=list;p;--i,p=p->next)
ret = p->n;
return ret;
}

int main(void)
{
int *numbers;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
return 0;
}


// gcc -D_GNU_SOURCE -Wall -Wextra ac1.c -o out
dan@dan-desktop:~/source/unleashed/ch11$

I don't mind saying that I want to win the Stefen Ram Ramstein. Maybe
we could collude in small groups. Gruss,
--

 

[Phil Carmody]

I have an idea for a program, yet I have not yet written and
tested it.

Here is an exercise that might be solved by this program:

Write a C program to read positive int numbers from a
user (a single int number is entered by its decimal
digits and the enter key) which are terminated by entry
of the digit 0 and the enter key, then allocate an array
of exactly the required size and then store the numbers
into this array (not including the terminating number 0).

The program may only once allocate memory with allocated
storage duration (malloc, calloc or so) (that is, for
the array mentioned above), and it shall not contain any
arbitrary limit for the number of numbers a user might
enter, although limitations of the C implementation used
might indeed impose a limitation on this number.

I will post my own solution not before 2010-02-08T05:05:29+01:00,
so feel free to post your own solution as a reply to this post.

Acording to the as-if rule, the following should be allowed:

int main() { return 0; }

However, I suspect you're more looking for something like this:

#include <stdio.h>
#include <stdlib.h>
static int n,l;
static int*r;

void rn(void)
{
int i;
scanf("%d",&i)&&i?n++,l++,rn(),r&&(r[--n]=i):l?!(r=malloc(l*sizeof(*r))):0;
}
int main()
{
rn();
/* This bit not actually asked for */
if(r) for(n=0; n<l; ++n) printf("%i\n",r[n]);
return !l;
}

I've minimised local variable usage to the absolute minimum, in order
to try and keep the recursive part as wastefree as possible, and thus
permit deeper recursion and a larger array given a limited quantity of
RAM. Of course, just the housekeeping of doing the rest of the task
imposes a lower limit on how tight that can be.

For even tighter RAM use on a typical architecture, replace
scanf("%d",&i)&&i
with
gets(buf)&&(i=atoi(buf))

Phil

 

[Michael Tsang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I have an idea for a program, yet I have not yet written and
tested it.

Here is an exercise that might be solved by this program:

Write a C program to read positive int numbers from a
user (a single int number is entered by its decimal
digits and the enter key) which are terminated by entry
of the digit 0 and the enter key, then allocate an array
of exactly the required size and then store the numbers
into this array (not including the terminating number 0).

The program may only once allocate memory with allocated
storage duration (malloc, calloc or so) (that is, for
the array mentioned above), and it shall not contain any
arbitrary limit for the number of numbers a user might
enter, although limitations of the C implementation used
might indeed impose a limitation on this number.

I will post my own solution not before 2010-02-08T05:05:29+01:00,
so feel free to post your own solution as a reply to this post.

#include <stdio.h>
#include <stdlib.h>

//! Read a list of unsigned integers from the standard input and return an
// array of them.
/*! @param[out] size A pointer to a size_t object to put the size of the
* allocated array in. If it is a null pointer, the size is discarded.
* @return The dynamically allocated array containing the numbers read.
*/
unsigned *get_numbers(size_t *size) {
static size_t level;
unsigned number;
scanf("%u", &number);
if(!number) {
if(size) {
*size = level;
}
return malloc(level * sizeof (unsigned));
} else {
++level;
unsigned *array = get_numbers(size);
--level;
array[level] = number;
return array;
}
}

int main(void) {
size_t size;
unsigned *array = get_numbers(&size);
for(unsigned *p = array; p != array + size; ++p) {
printf("%u\n", *p);
}
}
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAktr0C0ACgkQm4klUUKw07Cr7gCfbspoJ4/2UIaCS0gS8vHUSQXj
VcQAnRg0omQys/sYLh6v8N2RQeB1Fdrk
=lLr0
-----END PGP SIGNATURE-----

 

[frank]

I have an idea for a program, yet I have not yet written and
tested it.

Here is an exercise that might be solved by this program:

Write a C program to read positive int numbers from a
user (a single int number is entered by its decimal
digits and the enter key) which are terminated by entry
of the digit 0 and the enter key, then allocate an array
of exactly the required size and then store the numbers
into this array (not including the terminating number 0).

The program may only once allocate memory with allocated
storage duration (malloc, calloc or so) (that is, for
the array mentioned above), and it shall not contain any
arbitrary limit for the number of numbers a user might
enter, although limitations of the C implementation used
might indeed impose a limitation on this number.

I will post my own solution not before 2010-02-08T05:05:29+01:00,
so feel free to post your own solution as a reply to this post.

Acording to the as-if rule, the following should be allowed:

int main() { return 0; }

However, I suspect you're more looking for something like this:

#include <stdio.h>
#include <stdlib.h>
static int n,l;
static int*r;

void rn(void)
{
int i;
scanf("%d",&i)&&i?n++,l++,rn(),r&&(r[--n]=i):l?!(r=malloc(l*sizeof(*r))):0;
}
int main()
{
rn();
/* This bit not actually asked for */
if(r) for(n=0; n<l; ++n) printf("%i\n",r[n]);
return !l;
}

I've minimised local variable usage to the absolute minimum, in order
to try and keep the recursive part as wastefree as possible, and thus
permit deeper recursion and a larger array given a limited quantity of
RAM. Of course, just the housekeeping of doing the rest of the task
imposes a lower limit on how tight that can be.

For even tighter RAM use on a typical architecture, replace
scanf("%d",&i)&&i
with
gets(buf)&&(i=atoi(buf))

Phil

gets(buf) ? Looks unsafe.
--

 

[Michael Tsang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

#include <stdio.h>
#include <stdlib.h>
static int n,l;
static int*r;

void rn(void)
{
int i;
scanf("%d",&i)&&i?n++,l++,rn(),r&&(r[--n]=i):l?! (r=malloc(l*sizeof(*r))):0;
}
int main()
{
rn();
/* This bit not actually asked for */
if(r) for(n=0; n<l; ++n) printf("%i\n",r[n]);
return !l;
}

IOCCC entry?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAktr6K4ACgkQm4klUUKw07DzegCdH72aOUuTPD+54T9iaG1mh3Cu
5zgAn2u5DZD+e+55K/rxmcJRW3PfrKfX
=e2kj
-----END PGP SIGNATURE-----

 

[Ben Bacarisse]

Alan Curry wrote:

I don't really understand the finer points there, but I did give
source a whirl:

dan@dan-desktop:~/source/unleashed/ch11$ gcc -D_GNU_SOURCE -Wall
-Wextra ac1.c -o out
dan@dan-desktop:~/source/unleashed/ch11$ ./out
^C
dan@dan-desktop:~/source/unleashed/ch11$ ./out
3 4 5

That's not a number
dan@dan-desktop:~/source/unleashed/ch11$
dan@dan-desktop:~/source/unleashed/ch11$ ./out
345

That's not a number

What is your point? It would be clearer if you asked a question. For
example "why does the program do this?"; "how can I change the program
so that it ignores blank lines?"; "what forms of input does this
program accept?".

<snip>

 

[Phred Phungus]

What is your point? It would be clearer if you asked a question. For
example "why does the program do this?"; "how can I change the program
so that it ignores blank lines?"; "what forms of input does this
program accept?".

<snip>

My point is that the first user did not get output. I'm usually pretty
good at guessing on such matters.

I know that I'm not the most-knowledgeable guy about C around here, but
I'm not shy about trying source that others write so as to be a sounding
board.

The question I wanted to ask you was a different one. Pretty trivial.
If I rm a file, is it gone?
--

 

[Ben Bacarisse]

My point is that the first user did not get output. I'm usually
pretty good at guessing on such matters.

Eh? They did get output.

I know that I'm not the most-knowledgeable guy about C around here,
but I'm not shy about trying source that others write so as to be a
sounding board.

The question I wanted to ask you was a different one. Pretty
trivial. If I rm a file, is it gone?

The short answer is no, but it is not a C question so a long answer is
inappropriate here. I am not sure what the right group is to ask
about core *nix commands, sorry.

 

[Phil Carmody]

I have an idea for a program, yet I have not yet written and
tested it.

Here is an exercise that might be solved by this program:

Write a C program to read positive int numbers from a
user (a single int number is entered by its decimal
digits and the enter key) which are terminated by entry
of the digit 0 and the enter key, then allocate an array
of exactly the required size and then store the numbers
into this array (not including the terminating number 0).

The program may only once allocate memory with allocated
storage duration (malloc, calloc or so) (that is, for
the array mentioned above), and it shall not contain any
arbitrary limit for the number of numbers a user might
enter, although limitations of the C implementation used
might indeed impose a limitation on this number.

I will post my own solution not before 2010-02-08T05:05:29+01:00,
so feel free to post your own solution as a reply to this post.

Acording to the as-if rule, the following should be allowed:

int main() { return 0; }

However, I suspect you're more looking for something like this:

#include <stdio.h>
#include <stdlib.h>
static int n,l;
static int*r;

void rn(void)
{
int i;
scanf("%d",&i)&&i?n++,l++,rn(),r&&(r[--n]=i):l?!(r=malloc(l*sizeof(*r))):0;
}
int main()
{
rn();
/* This bit not actually asked for */
if(r) for(n=0; n<l; ++n) printf("%i\n",r[n]);
return !l;
}

I've minimised local variable usage to the absolute minimum, in
order to try and keep the recursive part as wastefree as possible,
and thus
permit deeper recursion and a larger array given a limited quantity
of RAM. Of course, just the housekeeping of doing the rest of the
task
imposes a lower limit on how tight that can be.

For even tighter RAM use on a typical architecture, replace
scanf("%d",&i)&&i
with
gets(buf)&&(i=atoi(buf))

Phil

gets(buf) ? Looks unsafe.

The code copes with well-formed input perfectly, assuming buf is a sensible
size. The specification of the input was quite clear. No behaviour was
specified for when the input is malformed, and so I've not violated anything
by crashing horribly and electrocuting your children if you feed it garbage.

Anyway - stop whining, and fix it. However, you must do that without
increasing the stack frame usage on any of the three architectures I
tested on.

Phil

 

[Phil Carmody]

#include <stdio.h>
#include <stdlib.h>
static int n,l;
static int*r;

void rn(void)
{
int i;
scanf("%d",&i)&&i?n++,l++,rn(),r&&(r[--n]=i):l?! (r=malloc(l*sizeof(*r))):0;
}
int main()
{
rn();
/* This bit not actually asked for */
if(r) for(n=0; n<l; ++n) printf("%i\n",r[n]);
return !l;
}

IOCCC entry?

Not really - that flowed quite naturally, and worked first time.
Then again, I've written recursive stuff IOCCC-stylee so often
that perhaps that perversion has rubbed of on 'normal' code too.

Ahhh, memories of:

main(int O,char**l){O-1&&main((O++<0?putchar(O%4?*1[l]++:",\n"[!O]):1[l][O-2])?O:2-4*O/3,l);}

Phil

 

[santosh]

Phred Phungus wrote:
[ ... ]

The question I wanted to ask you was a different one. Pretty trivial.
If I rm a file, is it gone?

If you remove() a file, the file as a file is gone, but in many cases
the data on the storage device that was represented by the file still
persists, but for how long and in what manner and if and how it could
be recovered are all very system specific questions. So you might have
better responses in a more specific group for your system.

 

[Flash Gordon]

Phred Phungus wrote:
[ ... ]

The question I wanted to ask you was a different one. Pretty trivial.
If I rm a file, is it gone?

If you remove() a file, the file as a file is gone,

Unless it isn't. The remove() function can fail.

but in many cases
the data on the storage device that was represented by the file still
persists, but for how long and in what manner and if and how it could
be recovered are all very system specific questions.

Even without those complications it isn't that simple.

So you might have
better responses in a more specific group for your system.

That is true, especially as the OP was not asking about the C function
but something else.

 

[Phred Phungus]

Phred Phungus wrote:
[ ... ]

The question I wanted to ask you was a different one. Pretty trivial.
If I rm a file, is it gone?

If you remove() a file, the file as a file is gone,

Unless it isn't. The remove() function can fail.

but in many cases
the data on the storage device that was represented by the file still
persists, but for how long and in what manner and if and how it could
be recovered are all very system specific questions.

Even without those complications it isn't that simple.

So you might have
better responses in a more specific group for your system.

That is true, especially as the OP was not asking about the C function
but something else.

He was soliciting this:


dan@dan-desktop:~/source/unleashed/ch11$ gcc -D_GNU_SOURCE -Wall
-Wextra ac1.c -o out
dan@dan-desktop:~/source/unleashed/ch11$ ./out
7
345
23
0
dan@dan-desktop:~/source/unleashed/ch11$ cat ac1.c
#include <stdio.h>
#include <stdlib.h>

struct list {
struct list *next;
int n;
};

static int *read_numbers(struct list *list)
{
char buf[100];
int val, i, *ret;
struct list node, *p;
if(fgets(buf, sizeof buf, stdin)) {
if(sscanf(buf, "%d", &val)!=1) {
fprintf(stderr, "That's not a number\n");
exit(EXIT_FAILURE);
}
if(val!=0) {
node.n = val;
node.next = list;
return read_numbers(&node);
}
} else {
if(ferror(stdin)) {
perror("standard input");
exit(EXIT_FAILURE);
}
/* Naughty user sent EOF; pretend it was a 0 but with a warning */
fprintf(stderr, "Didn't get 0 terminator. List may be incomplete\n");
}

for(i=0,p=list;p;++i,p=p->next)
/*nothing*/;
ret = malloc(i * sizeof *ret);
if(!ret) {
perror("malloc");
exit(EXIT_FAILURE);
}
for(--i,p=list;p;--i,p=p->next)
ret = p->n;
return ret;
}

int main(void)
{
int *numbers;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
return 0;
}


// gcc -D_GNU_SOURCE -Wall -Wextra ac1.c -o out
dan@dan-desktop:~/source/unleashed/ch11$

Without objection I'll call this the program of subthread one. Of
course Alan wrote it, but if santosh hadn't commented on rm, then I
wouldn't have tested successfully. And I wouldn't have thought that
Alan's code worked unless Ben told me it did.

It's close to noon on Feb 8 in Deutschland.

Die Zeit, wo treibt sie Dich?

 

[Stefan Ram]

Write a C program to read positive int numbers from a (...)
I will post my own solution not before 2010-02-08T05:05:29+01:00,

This exercise was solved faster than I expected, and,
indeed, I had recursion in mind - similar to the solutions
posted already, so I will not post another version of mine.

While recursion might not be the most efficient solution,
it still is useful as a programming exercise for those who
have not yet grasped the concepts of recursion, automatic
and allocated storage duration in C.