summaryrefslogtreecommitdiff
path: root/macros/generic/knst/knd.c
blob: a099bb25adf46d05a9369501a55bfe040b1467da (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
/*
  AUTHOR: Jordi Saludes <saludes@grec.upc.es>
  DATE:   12/9/1996
  FILE:   knd.c

	kndecode - Decoder of knapsack tests answers.
	
	SYNOPSIS
	
		kndecode [-i] [-apSGI] filename1 [filename2]
		
	DESCRIPTION

	kndecode decodes page totals for knapsack tests. kndecode
        reads first the exam description, then the students identifiers and
        answers and returns grades, decoded answers and other information.
	When filename2 is given, filename1 contains the exam
	description (usually a .ans file) and filename2 contains
	the students data and answers. When only one file name is given,
        filename1 contains first the exam description and then, after a blank
	line, the students data.
        filename2 can be `-', namely the standard input.
	Exam description
	 The exam description is usally written by the TeX run of
         exam file into a .ans file. Lines of such desciption are
           \opts  q p r:   Question number q has p options. Option number r
                           is the right one.
           \pagebot q:     Question q is the last one in current page.
           \Key k d:       k is the key for the test and  d is the
                           detection factor.
	Data lines
         Each line contains identifier, page totals (and possibly version
         number) of a student.
         Fields are separated by spaces. First field must be the
         identifier (long int) of student, next ones are
         the consecutive page totals. However if one of these fields
         f is negative, it is assumed that it represents a new
         version number instead of a page total. Version number is -f 
         from now on.
         
         If no options are given the student identifier is not expected.
		
	OPTIONS
	  
		i      Read incidences. Second field must be an octal
		       number standing for incidences ocurred in the
                       pre-processing of the exam data file.
		a      Return answers of exam, separated by tabs.
		p      Return plain (decoded) page totals,
                       for archiving purposes.
		S      Return the number of right, wrong and null answers.
		G      Return grade. Right answer means +1, null answer
                       means 0, value of wrong answers are adjusted 
		       to have 0 expectation when questions are answered
                       picking answers randomly.
                       Modify routine "qualifica" to change grading.
		I      Output incidences. Input incidences from
                       pre-processing  (when i option is given) are
                       OR-ed with incidences generated by kndecode and
                       returned.
		None   All information returned by the a, p, S or G
                       options is displayed in more human-readable form.
		       No student identifier is expected as first field.

        EXAMPLES

	 kndecode foo.ans -
         -38353  17942344
(Version number) (Page 1 total)

        kndecode -G foo.ans -  (Only grade)
        1001 -38353  17942344  674532
(IDentifier)   (V)     (P1)    (P2)

        kndecode -i -GI foo.ans - (Grade and output incidences)
        1001 2      -38353  17942344  674532
       (ID) (Incid.) (V)      (P1)     (P2)

*/

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

#define NSDF     1      /* Page total is  not a multiple of df */
#define BVER     2      /* Bad version number: Not inversible */
#define BCNT     4      /* Bad control number. From pre-processing */
#define DUPR     8      /* Duplicated record. From pre-processing */
#define BDEC    16      /* Bad decoding */

#define MQNS 100	/* Max number of questions */
#define MPAGS 10	/* Max number of pages in a test */

#define GRADE 1
#define PLAIN 2
#define STAT  4
#define ANSW  8
#define IIND 16
#define OIND 32

#define NSDF_str "%s: %ld is not a multiple of %hd\n"
#define BVER_str "%s: %ld has no inverse\n"
#define BDEC_str "%s: Bad decoding for %ld\n"
#define BFMT_str "%s: Bad format file\n"
#define UNKO_str "%s: Unknown  option\n"


typedef struct {short int nopt,marca,ref; long int w;} question;

question qn[MQNS];
short int	npag,df,nq;
short int	pb[MPAGS];
/* ref[MQNS],nopt[MQNS],marca[MQNS],pb[MPAGS]; */
long  int	key;
/* w[MQNS]; */

int    	getOptions(int argc, char *argv[], FILE **dataF, short *opts);
int	aplana(long *pla, long a, long s, long modul);
int	inverteix(long *in, long b, long key);
int     deco(long v, long s, question r[],short n,long *pla);
float   qualifica(short *n,short *b, short *m);

int     main(argc, argv)
int     argc;
char    *argv[];
{       FILE    	*dataF;
	int 		errs;
	short int       i,j,incid,opts;
	short int	bons,mals,nuls;
	long int	dni,suma,versio=1L,spla;
	float		nota;
	int		c;
	
	if(getOptions(argc,argv,&dataF,&opts)==0)
	  return(1);
	while(1) {
	  incid=0;
	  bons=mals=nuls=0;
	  nota=0.0;
	 if(opts) {
	    if(fscanf(dataF,"%ld",&dni)==EOF) break;
	    if (opts&IIND && fscanf(dataF,"%ho",&incid)==EOF) break;
	    printf("%ld",dni);
	}
	for(i=0;i<npag;) {
	    if (fscanf(dataF,"%ld",&suma)==EOF) goto sortir;
	    if (suma<0) {
	      inverteix(&versio,-suma,key);
	      continue;
	    }
	    if (suma%df!=0) {
	      fprintf(stderr,NSDF_str,argv[0],suma,df);
	      incid|=NSDF;
	      goto aborta;
	    }
	    i++;
	    if(deco(versio, suma/df,qn+pb[i-1],pb[i]-pb[i-1],&spla)) {
	      fprintf(stderr,BDEC_str,argv[0],suma/df);
	      incid|=BDEC;
	      goto aborta;
	    }
	if(!opts) {
#define LOOP for (j=pb[i-1];j<pb[i];j++)
	  printf("\n\nPg. %d\t",i); LOOP printf("%2d ",j+1);
	  printf("\n\t"); LOOP printf("---");
	  printf("\n\t"); LOOP printf("%2hd ",qn[j].ref);
	  printf("\n\t"); LOOP printf("%2hd ",qn[j].marca);
	  printf("\n\t"); LOOP
	   printf(" %c ", qn[j].marca==0? ' ':(qn[j].marca==qn[j].ref? 'B':'M'));
	}
	    if(opts&PLAIN)
	      printf("\t%ld",spla);
	    if (opts&ANSW)
	      LOOP printf("\t%hd",qn[j].marca);
	  }
 /* Now summaries */
	nota=qualifica(&nuls,&bons,&mals);
	if(!opts) {
	  printf("\n\nRight\tWrong\tNo answ\t\tGrade");
	  printf("\n%d\t%d\t%d\t\t%4.2f\n\n\n",bons,mals,nuls,nota);
	}
  	if (opts&GRADE)
	    printf("\t%4.2f", nota);
	  if(opts&STAT)
	    printf("\t%hd\t%hd\t%hd", bons,mals,nuls);
aborta:	if (opts&OIND) printf("\t%ho",incid);
	  printf("\n");
	}
sortir:
	fclose(dataF);
	return 0;
}


/** Get the multiplicative inverse of b modulo key
 ** Return in in.
 ** Uses algorith Y in Knuth
 **
 **/
int	inverteix(long *in, long b, long key)
{ 	long 	u1=1,u2=0,u3,v1,v2,v3,t1,t2,t3;
	long    u=b,v=key;
	int	k;
	if (b<=0) return 1;
	for (k=0; (u&1)==0 && (v&1)==0; k++) {u/=2; v/=2;}
	u3=u; v1=v; v2=1-u; v3=v;
	if ((u&1)==1) {
		t1=0; t2= -1; t3= -v;
		goto y4;
	} else {
		t1=1; t2=0; t3=u;
	}
y3:	if( (t1&1)==0 && (t2&1)==0) {
		t1/=2; t2/=2; t3/=2;
	} else {
		t1=(t1+v)/2; t2=(t2-u)/2; t3/=2;
	}
y4:	if((t3&1)==0) goto y3;
	if(t3>0) {
		u1=t1; u2=t2; u3=t3;
	} else {
		v1= v-t1; v2= -u-t2; v3= -t3;
	}
	t1=u1-v1; t2=u2-v2; t3=u3-v3;
	if (t1<0) { t1+=v; t2-=u;}
	if (t3!=0) goto y3;
	*in= u1;
	return 0;
}




/** Return grade. Give also the nuwer of
 ** right, wrong and null answers.
 **/
float   qualifica(short *n,short *b,short *m)
{       short int i;
		float nota=0.0;
	(*n)= (*b)= (*m)= 0;
	for(i=0; i<nq; i++) {
		if(qn[i].marca==0)
			(*n)++;
		else
			if(qn[i].marca==qn[i].ref) {
				(*b)++; nota++;
			} else {
				(*m)++; nota-=1.0/(qn[i].nopt-1);
			}
	}
	return (nota*10.0)/nq;
}




/** Given the plain total sp, obtain n answers in res
 **
 **/
int	deco(long int v, long int s, question res[], short n,long *pla)
{       long int    	sp;
	short int       i;

	if(s<0) return(1);
	s= s%key;
	for (sp=0;v;s=(s+s)%key,v>>=1)
	  if(v&1) sp=(sp+s)%key;
	*pla=sp;
	for (i=n-1; i>=0; i--) {
		if ((res[i].marca=sp/res[i].w)>res[i].nopt) return(1);
		sp= sp%res[i].w;
	}
	return(0);
}




/** Get the options in the command line
 **
 **/
int	getOptions(int argc, char *argv[], FILE **dataF, short int *opts)
{       short int	k,i,j,na,cref;
	long  int	m=1;
	int	errs, rcs;
	char opt, rec[50];
	*dataF=NULL;

	if (argc<=1) return(0);
	*opts=0;
	for (k=1;k<argc;k++) {
	  if (argv[k][0]!='-') break; /* File names */
	  switch(argv[k][1]) {
	  case 'i': (*opts)|=IIND;
	    break; /* No incidences */
	  default:
	    for(i=1;(opt=argv[k][i])!=0;i++)
	      switch(opt) {
	      case 'G': /* Give grade */
		(*opts)|=GRADE; break;
	      case 'p': /* Give plain total */
		(*opts)|=PLAIN; break;
	      case 'S': /* statistics */
		(*opts)|=STAT; break;
	      case 'a': /* Give answers */
		(*opts)|=ANSW; break;
	      case 'I': /* Output incidences */
	       (*opts)|=OIND; break;
	      default:
		fprintf(stderr, UNKO_str,argv[0]);
		return(0);
	      }
	  }
	}
	*dataF= fopen(argv[k++],"r");
	if(!(*dataF)) return(0);
	/* Read the file header*/
	nq=0; pb[0]=0; npag=0;
	do {
	 	if(!fgets(rec,50,*dataF)) break;
		rcs=sscanf(rec, "\\Key %ld %hd\n",&key, &df);
       if(sscanf(rec, "\\opts %hd %hd %hd",&i, &na,&cref)) {
	       rcs++;
	       qn[i-1].ref=cref;
	       qn[i-1].nopt=na;
       }
       if(sscanf(rec, "\\pagebot %hd\n",&i)) {
       	rcs++;
       	pb[++npag]=i;
       	nq= nq<i? i: nq;
       }
    } while (rcs>0);
    for(j=0,i=1; i<=npag; i++)
	for(m=1; j<pb[i]; j++) {
		qn[j].w= m;  /* printf("%ld ",m); */
		m*=(qn[j].nopt+1);
	}
	fprintf(stderr,
		"\nReading header\nkey= %ld, df= %hd, nq=%hd\n",key,df,nq);
	if(argc<=k) return(1); /* Use the same file */
	fclose(*dataF);
	if(argv[k][0]=='-')
	  *dataF= stdin;
	else {
	  *dataF= fopen(argv[k],"r");
	  if(!(*dataF)) return(0);
	}
	return(1);
}