summaryrefslogtreecommitdiff
path: root/macros/generic/knst
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/generic/knst
Initial commit
Diffstat (limited to 'macros/generic/knst')
-rw-r--r--macros/generic/knst/README15
-rw-r--r--macros/generic/knst/foo.tex44
-rw-r--r--macros/generic/knst/knd.c352
-rw-r--r--macros/generic/knst/knst.tex256
4 files changed, 667 insertions, 0 deletions
diff --git a/macros/generic/knst/README b/macros/generic/knst/README
new file mode 100644
index 0000000000..7620a4ffd8
--- /dev/null
+++ b/macros/generic/knst/README
@@ -0,0 +1,15 @@
+This is the package supporting generation and correction of
+multiple option tests, as will appear in TUGBoat 17#3:
+"Fast and secure multiple option tests".
+
+The package includes:
+ - knst.tex: Macro TeX package and style to typeset the tests;
+ - knd.c: C code for an utility which grades these tests as described in
+ the paper;
+ - README: this file;
+ - foo.tex: Example test file. Uncomment \plainversion to run the
+ plain version, then run again with the comments in place
+ to get a test.
+
+ --Jordi Saludes
+ saludes@grec.upc.es
diff --git a/macros/generic/knst/foo.tex b/macros/generic/knst/foo.tex
new file mode 100644
index 0000000000..96ae42c25f
--- /dev/null
+++ b/macros/generic/knst/foo.tex
@@ -0,0 +1,44 @@
+\input knst.tex
+\date{April 1995}
+\title{A test}
+%%\plainversion
+\test{1234531}
+\qtn Example question with
+a displayed equation
+$$\int_{\partial S}\omega=
+ \int_S d\omega.$$
+ \anw Option a;
+ \Anw Option b (and right);
+ \anw Option c;
+ \anw Option d;
+ \anw Option e;
+ \anw Option f;
+ \anw Option g;
+\endqtn
+
+\qtn This question has
+a `fixed' option at the end.
+ \Anw This is the right option;
+ \anw Not so well;
+ \anw Clearly wrong;
+ \fix\anw None of the above.
+\endqtn
+
+\qtn Boolean question
+ \anw True;
+ \Anw False
+\endqtn
+
+\qtn Fuzzy question
+ \Anw Quite true;
+ \anw Quite false;
+\endqtn
+
+\qtn Is this the last one?
+ \anw Who knows;
+ \anw Choose me;
+ \fix\Anw None of the above;
+ \anw All of the above.
+\endqtn
+\stepversion{1243}
+\endtest
diff --git a/macros/generic/knst/knd.c b/macros/generic/knst/knd.c
new file mode 100644
index 0000000000..a099bb25ad
--- /dev/null
+++ b/macros/generic/knst/knd.c
@@ -0,0 +1,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);
+}
+
+
+
diff --git a/macros/generic/knst/knst.tex b/macros/generic/knst/knst.tex
new file mode 100644
index 0000000000..7038f45883
--- /dev/null
+++ b/macros/generic/knst/knst.tex
@@ -0,0 +1,256 @@
+%%% AUTHOR: Jordi Saludes <saludes@grec.upc.es>
+%%% DATE: 12/9/1996
+%%% FILE: knst.tex
+%%% knapsack test macros.
+\catcode`@=11
+%% Shift Register
+%% from H. van der Meer, TUB 15, 1
+\newcount\@SR
+\def\@SRconst{2097152}
+\def\SRset#1{\global\@SR#1\relax}%
+\def\@SRadvance{\bgroup
+ \ifnum\@SR<\@SRconst\relax
+ \@A=0
+ \else\@A=1\fi
+ \ifodd\@SR
+ \advance\@A by1 \fi
+ \global\divide\@SR by2
+ \ifodd\@A
+ \global\advance\@SR\@SRconst\relax\fi
+ \egroup}
+%% Arithmetic
+\newcount\@A
+\newcount\@B
+\newcount\@C
+\newcount\@x \@x=0\relax
+\newcount\@y \@y=0\relax
+\newcount\@w
+\newcount\key
+\newcount\df \df=1\relax
+\def\qtnno{\the\@x\relax}
+\def\inc@#1{\advance#1 by1\relax}
+\def\mod@A#1{\@B=\@A \divide\@B by#1
+ \multiply\@B by#1
+ \advance\@A by-\@B\relax}
+\def\gcd#1#2{{\@A=#1 \@C=#2
+ \loop\mod@A\@C
+ \ifnum\@A>0
+ \@B=\@C \@C=\@A \@A=\@B
+ \repeat
+ \ifnum\@C=1\else
+ \errmessage{Invalid stepper/version
+number "#1"}\fi}}
+\def\adv@w{{\inc@\@y
+ \global\multiply\@w by \@y}}
+\def\labelno{{\@A=\@B
+ \mod@A\key\multiply\@A by\df \the\@A}}
+%% Boxing and unboxing
+\newtoks\pfootline
+\newtoks\pheadline
+\newbox\lqtn@bx
+\newbox\lanw@bx
+\newbox\canw@bx
+\newbox\cqtn@bx
+\def\new@page{\unvbox\lqtn@bx
+ \vfill\penalty-10000
+ \global\@w=\verno \adv@w}
+\def\append@bx#1#2{%
+ \setbox#1=\vbox{\unvbox#1 #2}}
+\def\prepend@bx#1#2{%
+ \setbox#1=\vbox{#2\unvbox#1}}
+\def\add@anw{\@SRadvance
+ \iffix@anw
+ \global\append@bx{\lanw@bx}{\theanw}%
+ \else
+ \ifodd\@SR
+ \global\prepend@bx{\lanw@bx}{\theanw}%
+ \else
+ \global\append@bx{\lanw@bx}{\theanw}%
+ \fi\fi}%
+\def\add@qtn{\@SRadvance
+ \iffix@qtn
+ \global
+ \append@bx{\lqtn@bx}{\unvbox
+ \cqtn@bx}%
+ \else
+ \ifodd\@SR
+ \global
+ \prepend@bx{\lqtn@bx}{\unvbox
+ \cqtn@bx}%
+ \else
+ \global
+ \append@bx{\lqtn@bx}{\unvbox
+ \cqtn@bx}%
+ \fi\fi}
+\def\fix{\global\fix@anwtrue\relax}%
+\def\fixqtn{\global\fix@qtntrue\relax}%
+\def\qtn{\global\inc@\@x
+ \@y=0 \@B=0
+ \ifplain\else
+ \ifnum\@x>\botqtn
+ \new@page\@next\fi\fi
+ \rightanw=0
+ \global\fix@anwfalse
+ \setbox\cqtn@bx=\vbox\bgroup
+ \noindent\qtn@pr}
+\def\endqtn{\egroup\add@anw
+ \ifplain\ifnum\rightanw=0
+ \immediate\write16{There is no
+ option marked in question
+ \the\@x}\fi\fi
+ \setbox\cqtn@bx=\vbox{\box\cqtn@bx
+ \preanwskip\box\lanw@bx
+ \qtnskip}%
+ \adv@w\wr@anw
+ \ifplain
+ \ifnum\@w>\key
+ \message{*}\new@page\fi
+ \else
+ {\@A=\@w \mod@A\key \global\@w=\@A}\fi
+ \mark{\noexpand
+ \themark{\the\@x}{\the\@w}}
+ \message{.}\add@qtn}
+\def\Anw{\ifnum\rightanw>0
+ \errmessage{There are several
+ options marked in question
+ \the\@x}\fi
+ \global\rightanw=\@y
+ \global\inc@\rightanw
+ \anw}
+\def\anw{\egroup
+ \ifnum\@y=0\else
+ \add@anw\fi
+ \advance\@B by\@w\relax\inc@\@y
+ \setbox\canw@bx=\vtop\bgroup
+ \relax\noindent}
+\newif\ifplain
+\plainfalse
+\newcount\verno \verno=0
+\newcount\rightanw
+\newif\iffix@anw
+\newif\iffix@qtn
+\fix@qtnfalse
+\let\read@line=\relax
+\let\@read=\relax
+\def\theanw{\hbox{\vrule
+ height10pt width\z@\relax
+ \anwprompt\ \box\canw@bx\hfill}}
+\newcount\verno
+\newwrite\anwfile
+\newwrite\auxfile
+\newdimen\labelw
+\def\test#1{\key=#1
+ \setbox3=\hbox{\multiply\key by\df
+ \the\key}%
+ \labelw=\wd3\relax
+ \ifnum\verno<1\relax
+ \immediate
+ \openin\auxfile=\jobname.aux\relax
+ \read\auxfile to\@read \@read
+ \immediate\closein\auxfile\relax\fi
+ \gcd{\the\verno}{\the\key}
+ \@SRadvance
+ \global\@w=\verno
+ \header
+ \setbox\lqtn@bx=\vbox{}
+ \ifplain
+ \message{Plain version}\SRset{0}%
+ \global\@w=1
+ \else
+ \message{Version \the\verno}
+ \immediate
+ \openin\anwfile=\jobname.ans\relax
+ \fi\@next}
+\def\endtest{
+ \ifplain
+ \write\anwfile{\string
+ \Key\space\the\key\space
+ \the\df\space}%
+ \closeout\anwfile
+ \else
+ \closein\anwfile\fi
+ \unvbox\lqtn@bx\vfill\supereject\end}
+\def\stepversion#1{\gcd{#1}{\the\key}%
+ \immediate
+ \openout\auxfile=\jobname.aux\relax
+ {\ifnum\@SR=0
+ \@SR=\@SRconst
+ \divide\@SR by3\fi
+ \@SRadvance
+ \@A=\verno
+ \multiply\@A by#1\relax
+ \mod@A\key\relax
+ \immediate\write\auxfile{\string
+ \verno=\the\@A\space
+ \string\SRset{\the\@SR}}}%
+ \immediate\closeout\auxfile}
+\def\plainversion{\plaintrue\verno=1
+ \let\newpage=\new@page
+ \def\wr@anw{\immediate
+ \write\anwfile{\string\opts
+ \space\the\@x\space\the\@y\space
+ \the\rightanw\space\the\@w\space}}
+ \immediate
+ \openout\anwfile=\jobname.ans\relax
+ \def\qtn@pr{\llap{\qtnprompt}}
+\def\anwprompt{\hbox to\labelw{\hss
+ \ifnum\rightanw=\@y
+ $\bullet$\ \fi}}
+\footline=\pfootline
+\headline=\pheadline
+\let\@next=\relax
+\output={\botmark\plainoutput}
+\def\add@qtn{\unvbox\cqtn@bx\penalty-50}}
+\def\themark#1#2{\immediate
+ \write\anwfile{\string\pagebot
+ \space #1\space}%
+ \global\divide\@w by#2\relax}
+\let\wr@anw=\relax
+\let\qtn@pr=\relax
+\def\@next{\read\anwfile to\@read
+ \@read}
+\def\Key #1 #2 {\@next}
+\def\opts #1 #2 #3 #4 {\@next}
+\def\pagebot #1 {\def\botqtn{#1}}
+\def\botqtn{1000}
+\let\newpage=\relax
+%% Style commands
+\def\qtnprompt{\bf\qtnno.\ }
+\pfootline={\hss
+ Plain version $\dots$\hss}
+\pheadline={\ifnum\folio>1
+ \thetitle\hss\folio\else\hss\fi}
+\footline={Page \folio. Version
+ {\tt\the\verno}.
+ $\Sigma=$\hskip7em
+ $\Sigma/\the\df=$\hfill}
+\def\date#1{\def\thedate{#1}}
+\def\title#1{\def\thetitle{#1}}
+\def\header{
+ \line{\bf\thetitle\hfill\thedate}%
+ \smallskip
+ \line{Name:\ \dotfill}%
+ \medskip
+{\baselineskip=9pt
+ \noindent\small
+ Each question has
+ only one right answer.
+ For each page, add the numbers at
+ the left side of
+ your answers and write the total by
+ the $\Sigma$. Divide the total
+ by~\the\df. If your addition is right,
+ the quotient must be integer
+ (But this does not mean
+ that your choices were correct).
+ Do not forget to write down your name,
+ but do not write anything else in the
+ exam sheet.\par}
+ \medskip}
+\df=7
+\def\anwprompt{\hbox to\labelw{\it
+ \hss\labelno\ $\diamond$}}
+\def\qtnskip{\vskip 20pt plus25pt }
+\let\preanwskip=\smallskip
+\font\small=cmr8
+