CI-1322 Tarea #7


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2004

$[\/]$

CI-1322 Autómatas y compiladores

Tarea #7 [solución]

Detector de proyectos copiados

Haga un programa que permita detectar si 2 o más estudiantes han copiado su proyecto programado. Su programa debe recibir archivos C++, a los que aplicará una serie de conversiones para al final obtener lista de números que se usará para detectar programas similares.

Las transformaciones que tiene que aplicar son las siguientes:

ex-00.cpp: ==> Archivo original
ex-01.cpp: ==> Elimine comentarios
ex-02.cpp: ==> Cambie todos los identificadores por "id"
ex-03.cpp: ==> Cambie todas las hileras por "s"
ex-04.cpp: ==> Cambie todos los números por 0
ex-05.cpp: ==> Elimine espacios en blanco múltiples
ex-06.cpp: ==> Elimine renglones en blanco
ex-07.cpp: ==> Ordene todos los renglones
ex-08.cpp: ==> Elimine renglones duplicados

Haga esto para cada archivo de un proyecto, y luego calcule el tamaño del archivo resultantes. Distinga a los archivos que son referenciados en un #include "encabezado.h" de los que no lo son, y ordene los tamaños de los archivos de mayor a menor:

Torres.cpp    Casona.cpp   Isla.cpp     Torres.h   Casona.h   Lista.h   Isla.h
    345          312         215           415       412         233      105

NO es #include    Es #include
(345, 312, 215)  (415, 412, 233, 105)    Estos 2 son similares ==> Seguro son copias
(343, 310, 213)  (415, 412, 233)

(535, 212, 115)  (233, 105,  66,  35)    Nada que ver con los otros.

La entrada para el programa detector de parejas de copia es la ruta a un directorio que contiene todos los proyectos, en donde cada subdirectorio es la solución del proyecto de cada estudiante. No es necesario examinar los sub-sub-directorios que estén más profundos:

Tareas
  |
  |--> A22222
  |--> A33333          Un sub-directorio por cada proyecto
  \--> A44444
          \--> Subdir: No interesa el contenido de sub-sub-directorios

En cada subdirectorio hay que examinar archivos de 2 tipos:

Archivos de encabezado ==> *.h* & *.
Archivos de implementación ==> *.c*

Para encontrar proyectos duplicados se pueden usar al menos estos métodos:

Comparar el tamaño total de todos los archivos.
Comparar el tamaño total de todos los archivos de encabezado y de implementación.
Comparar el tamaño individual de los archivos de encabezado y el tamaño total de los archivos de implementación.
Comparar el tamaño individual de los archivos de implementación y el tamaño total de los archivos de encabezado.
Comparar el tamaño individual de los archivos de encabezado y de implementación.
Incluir los archivos de encabezado dentro de los archivos de implementación, para obtener un única lista de archivos de implementación con la que trabajar.
Asignarle a cada token un valor diferente en cada archivo, para luego calcular un valor que sirva para crear una lista de valores a comparar. Este cálculo se puede hacer por agrupando varios archivos de implementación o de encabezado.
Crear para cada proyecto de cada estudiante una pareja un diccionario que tenga como llave cada uno de los renglones al que se le asocia la cantidad de veces que aparece el renglón. Luego se pueden comparar los diccionarios de cada proyecto para ver cuáles pueden ser similares.
Crear para cada proyecto una matriz que tenga una fila por cada tipo de renglón y una columna para cada tipo de token con el que comienzan las filas. Luego se puede comparar el valor de cada matriz con las demás para detectar posibles copias.
Aplicar cualquiera de los métodos anteriores sólo para archivos que tengan un tamaño "significativo", en donde el umbral de significancia puede empezar enn 128 bytes, por ejemplo.

Una vez que ya se han obtenido las listas de tamaños compactados para cada archivo, el proceso consiste en encontrar parejas de proyectos que aparenten ser similares.

No es necesario urgar en archivos de extensión diferente, pues se debe suponer que si un proyecto parece copiado, pues tienen una estructura extraña, automáticamente quien califica tratará de revisar que ese proyecto no sea copiado.

Como "n ≤ 100" (en donde "n" es el número de proyectos), un algoritmo que sea O(n⁴) o O(n⁵) es perfectamente efectivo, porque hacer 10,000,000 o 100,000,000 de cálculos en una Pentium 4 de 2.0 GigaHerts es suficientemente rápido.

// ex04_18.cpp #include <iostream> using std::cout; using std::endl; int whatIsThis( int [], int ); int main() { const int arraySize = 10; int a[ arraySize ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int result = whatIsThis( a, arraySize ); cout << "Result is " << result << endl; return 0; } int whatIsThis( int b[], int size ) { if ( size == 1 ) return b[ 0 ]; else return b[ size - 1 ] + whatIsThis( b, size - 1 ); } /************************************************************************** * (C) Copyright 2000 by Deitel & Associates, Inc. and Prentice Hall. * * All Rights Reserved. * * * * DISCLAIMER: The authors and publisher of this book have used their * * best efforts in preparing the book. These efforts include the * * development, research, and testing of the theories and programs * * to determine their effectiveness. The authors and publisher make * * no warranty of any kind, expressed or implied, with regard to these * * programs or to the documentation contained in these books. The authors * * and publisher shall not be liable in any event for incidental or * * consequential damages in connection with, or arising out of, the * * furnishing, performance, or use of these programs. * *************************************************************************/

ex-00.cpp: Archivo original

#include <iostream> using std::cout; using std::endl; int whatIsThis( int [], int ); int main() { const int arraySize = 10; int a[ arraySize ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int result = whatIsThis( a, arraySize ); cout << "Result is " << result << endl; return 0; } int whatIsThis( int b[], int size ) { if ( size == 1 ) return b[ 0 ]; else return b[ size - 1 ] + whatIsThis( b, size - 1 ); }

ex-01.cpp: Elimine comentarios

#include <iostream> using id::id; using id::id; id id( id [], id ); id id() { const id id = 10; id id[ id ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; id id = id( id, id ); id << "Result is " << id << id; return 0; } id id( id id[], id id ) { if ( id == 1 ) return id[ 0 ]; else return id[ id - 1 ] + id( id, id - 1 ); }

ex-02.cpp: Cambie todos los identificadores por "id"

#include <iostream> using id::id; using id::id; id id( id [], id ); id id() { const id id = 10; id id[ id ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; id id = id( id, id ); id << "s" << id << id; return 0; } id id( id id[], id id ) { if ( id == 1 ) return id[ 0 ]; else return id[ id - 1 ] + id( id, id - 1 ); }

ex-03.cpp: Cambie todas las hileras por "s"

#include <iostream> using id::id; using id::id; id id( id [], id ); id id() { const id id = 0; id id[ id ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; id id = id( id, id ); id << "s" << id << id; return 0; } id id( id id[], id id ) { if ( id == 0 ) return id[ 0 ]; else return id[ id - 0 ] + id( id, id - 0 ); }

ex-04.cpp: Cambie todos los números por 0

#include <iostream> using id::id; using id::id; id id( id [], id ); id id() { const id id = 10; id id[ id ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; id id = id( id, id ); id << "s" << id << id; return 0; } id id( id id[], id id ) { if ( id == 0 ) return id[ 0 ]; else return id[ id - 0 ] + id( id, id - 0 ); }

ex-05.cpp: Elimine espacios en blanco múltiples

const id id = 10; else id << "s" << id << id; id id = id( id, id ); id id[ id ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; if ( id == 0 ) return 0; return id[ 0 ]; return id[ id - 0 ] + id( id, id - 0 ); #include <iostream> { { } } id id( id [], id ); id id( id id[], id id ) id id() using id::id; using id::id;

ex-07.cpp: Ordene todos los renglones

const id id = 10; else id << "s" << id << id; id id = id( id, id ); id id[ id ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; if ( id == 0 ) return 0; return id[ 0 ]; return id[ id - 0 ] + id( id, id - 0 ); #include <iostream> { } id id( id [], id ); id id( id id[], id id ) id id() using id::id;

ex-08.cpp: Elimine renglones duplicados

Entregue su tarea por correo electrónico, como lo hizo anteriormente.

[mailto:] Entrega de Tareas

Tiempo de entrega:	10 días
Modalidad:	En parejas

Soluciones

$[/\]$