c -- 519
(or 137 if you credit me for the framework...)
Rather than solving just this one operation, I decided to produce a framework for solving all persistence problems.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char*(*O)(char*);
char*b(char*s){long long int v=0,i,l=0;char*t=0;l=strlen(s);t=malloc(l+2);
for(i=0;i<l;i++)v+=s[i]-'0';snprintf(t,l+2,"%lld",v);return t;}
int a(char**s,O o){int r;char*n;n=o(*s);r=!strcmp(*s,n);free(*s);
*s=n;return r;}
int main(int c, char**v){size_t l, m=0;char *d,*n=0;O o=b;FILE*f=stdin;
while(((l=getline(&n,&m,f))>1)&&!feof(f)){int i=0;n=strsep(&n,"\n");
d=strdup(n);while(!a(&n,o))i++;printf("%s %d\n",d,i);free(d);free(n);n=0;m=0;}}
Only the two lines starting from char*b
are unique to this problem.
It treats the input as strings, meaning that leading "0"s are not strip before the output stage.
The above has had comments, error checking and reporting, and file reading (input must come from the standard input) striped out of:
/* persistence.c
*
* A general framework for finding the "persistence" of input strings
* on opperations.
*
* Persistence is defined as the number of times we must apply
*
* value_n+1 <-- Opperation(value_n)
*
* before we first reach a fixed point.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../getline.h"
/* A function pointer type for operations */
typedef char*(op_func)(char*);
typedef op_func* op_ptr;
/* Op functions must
* + Accept the signature above
* + return a point to a newly allocated buffer containing the updated str
*/
char* addop(char*s){
int i,l=0;
long long int v=0;
char *t=NULL;
/* protect against bad input */
if (NULL==s) return s;
/* allocate the new buffer */
l = strlen(s);
t = malloc(l+2);
if (NULL==t) return t;
/* walk the characters of the original adding as we go */
for (i=0; i<l; i++) v += s[i]-'0';
//fprintf(stderr," '%s' (%d) yields %lld\n",s,l,v);
snprintf(t,l+2,"%lld",v);
//fprintf(stderr," %lld is converted to '%s'\n",v,t);
return t;
}
/* Apply op(str), return true if the argument is a fixed point fo
* falsse otherwise,
*/
int apply(char**str, op_ptr op){
int r;
char*nstr;
/* protect against bad input */
if ( NULL==op ) exit(1);
if ( NULL==*str ) exit(4);
/* apply */
nstr = op(*str);
/* test for bad output */
if ( NULL==nstr ) exit(2);
r = !strcmp(*str,nstr);
/* free previous buffer, and reasign the new one */
free(*str);
*str = nstr;
return r;
}
int main(int argc, char**argv){
size_t len, llen=0;
char *c,*line=NULL;
op_ptr op=addop;
FILE *f=stdin;
if (argc > 1) f = fopen(argv[1],"r");
while( ((len=getline(&line,&llen,f))>1) && line!=NULL && !feof(f) ){
int i=0;
line=strsep(&line,"\n"); // Strip the ending newline
/* keep a copy for later */
c = strdup(line);
/* count necessary applications */
while(!apply(&line,op)) i++;
printf("%s %d\n",c,i);
/* memory management */
free(c);
free(line);
line=NULL;
llen=0;
}
}
A little more could be saved if we were willing to leak memory like a sieve. Likewise by #define
ing return and the like, but at this point I don't care to make it any uglier.
1Your test cases include some values which are over 2^64, and your spec says that the program only has to handle values up to 2^32. Might be worth clearing that up. – Peter Taylor – 2011-03-25T23:40:22.240
@Peter Taylor, forgot to remove those limits. If a program can handle the input I have provided, it shouldn't have an issue with limits. – Kevin Brown – 2011-03-25T23:49:16.497
5Isn't 999999999999's persistence 2 instead of 3? – Eelvex – 2011-03-26T02:13:19.727
@Evelex, that was an incorrect last minute change I guess. Fixed. – Kevin Brown – 2011-03-26T21:45:41.493
Several answers here aren't doing output on stdout but rather use J's "interactive" output by returning results after taking command line input. (This includes 2 other J answers and, I'm guessing, the K answer.) Is this considered legit? Because I can shed 18-ish characters if so. – Jesse Millikan – 2011-03-27T01:29:55.447
@Jesse Millikan, the problem doesn't state it must output to stdout. – Kevin Brown – 2011-03-27T01:42:18.293
It does state "followed by a single space," and, "on it's own line", which seems to imply at least some kind of string output. Also, interactive J doesn't format them as stated if there are inputs of different lengths. – Jesse Millikan – 2011-03-27T01:47:05.610
"Also, interactive J doesn't format them as stated if there are inputs of different lengths." What do you mean by that? – Kevin Brown – 2011-03-27T02:01:21.253
I meant outputs of different lenghts, though it's irrelevant... I was hallucinating or something. Both of the J answers are doing the output as given. – Jesse Millikan – 2011-03-27T02:21:51.523
@Jesse Millikan, The K answer outputs a formatted string to stdout and not to the interactive prompt. – isawdrones – 2011-03-27T06:31:43.150