Re: A programming exercise
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.
--
Ben Pfaff
http://benpfaff.org
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.
>
> 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
Temp file. :)
Alan Curry
Stefan Ram <r...@zedat.fu-berlin.de> wrote:
| 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:
|
| 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.
|
| 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[i] = 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.
--
Alan Curry
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>
// 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
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
Michael Tsang
Hash: SHA1
Stefan Ram wrote:
> 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
gets(buf) ? Looks unsafe.
--
Michael Tsang
Hash: SHA1
Phil Carmody wrote:
> #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:
<snip a solution>
> 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>
--
Ben.
Phred Phungus
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
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.
--
Ben.
Phil Carmody
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 Carmody
> Phil Carmody wrote:
>
>> #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);}
santosh
[ ... ]
> 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.
--
Flash Gordon
Phred Phungus
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
// 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?
--
froederick
Phred Phungus
>> I will post my own solution not before 2010-02-08T05:05:29+01:00,
>
> 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.
>
$ gcc -D_GNU_SOURCE -Wall -Wextra ad3.c -o out
$ ./out
4
5
6
0
4
5
6
$ cat ad3.c
#include <stdio.h>
#include <stdlib.h>
struct list {
struct list *next;
int n;
};
int count;
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;
++ count;
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[i] = p->n;
return ret;
}
int main(void)
{
int i;
int *numbers,*p;
count=0;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
p=numbers;
for (i=0; i<count; ++i) printf("%d\n",*p++);
return 0;
}
// gcc -D_GNU_SOURCE -Wall -Wextra ad3.c -o out
$
Since no one else wants it, I'll lay claim to the Stefan Ram Ramstein.
--
fred