MaterialesTareaImplementacion.tar

Makefile0000444000175200017520000000654413367641504011136 0ustar  fefefefe
# --------------------------------------------------------------------
#  Makefile de tarea .

#  Laboratorio de Programación 3.
#  InCo-FIng-UDELAR

# Define un conjunto de reglas.
# Cada regla tiene un objetivo, dependencias y comandos.
#objetivo: dependencia1 dependencia2...
#	comando1
#	comando2
#	comando3
# (antes de cada comando hay un tabulador, no espacios en blanco).
# Se invoca con
#make objetivo
# para que se ejecuten los comandos.
#
# Si `objetivo' es un archivo los comandos se ejecutan solo si no está
# actualizado (esto es, si su fecha de actualización es anterior a la de alguna
# de sus dependencias.
# Previamente se aplica la regla de cada dependencia.


# --------------------------------------------------------------------

# Objetivo predeterminado (no se necesita especificarlo al invocar `make').
all: principal

# Objetivos que no son archivos.
.PHONY: all clean_bin clean_test clean testing

TESTDIR = test
EJECUTABLE = principal

# compilador
CC = g++
# opciones de compilación
CCFLAGS = -Wall -Werror -I$include -g -DNDEBUG
# -DNDEBUG
# si se mantiene esta opción las llamadas a assert no hacen nada.

# $^ se expande en todas las dependencias
$(EJECUTABLE):principal.cpp intervalos.cpp
	$(CC) $(CCFLAGS) $^ -o $@


# casos de prueba
CASOS = 00 01 02 03 04 05

# cadena de archivos, con directorio y extensión
INS=$(CASOS:%=$(TESTDIR)/%.in)
OUTS=$(CASOS:%=$(TESTDIR)/%.out)
SALS=$(CASOS:%=$(TESTDIR)/%.sal)
DIFFS=$(CASOS:%=$(TESTDIR)/%.diff)

$(SALS):$(EJECUTABLE)
# el guión antes del comando es para que si hay error no se detenga la
# ejecución de los otros casos
$(TESTDIR)/%.sal:$(TESTDIR)/%.in
	-timeout 6 valgrind -q --leak-check=full ./$(EJECUTABLE) < $< > $@ 2>&1
	@if [ $$(stat -L -c %s $@) -ge 10000 ]; then \
		echo "tamaño excedido" > $@;\
	fi

# prueba de tiempo
$(TESTDIR)/05.sal:$(TESTDIR)/05.in
	./$(EJECUTABLE) < $< > $@



# cada .diff depende de su .out y de su .sal
%.diff: %.out %.sal
	@diff $^ > $@;                                            \
	if [ $$? -ne 0 ];                                         \
	then                                                      \
		echo ---- ERROR en caso $@ ----;                  \
	fi
# Con $$? se obtiene el estado de salida del comando anterior.
# En el caso de `diff', si los dos archivos comparados no son iguales,
# el estado de la salida no es 0 y en ese caso se imprime el mensaje.



# Test general. Las dependencias son los .diff.
# Con `find` se encuentran los .diff de tamaño > 0 que están en el directorio
# $(TESTDIR) y lo asigna a $(LST_ERR).
# Si el tamaño de $(LST_ERR) no es cero imprime los casos con error.
# Con `sed` se elimina el nombre de directorio y la extensión.
testing:$(DIFFS)
	@LST_ERR=$$(find $(TESTDIR) -name *.diff* -size +0c -print);            \
	if [ -n "$${LST_ERR}" ];                                                \
	then                                                                    \
		echo -- CASOS CON ERRORES --;                                   \
		echo "$${LST_ERR}" | sed -e 's/$(TESTDIR)\///g' -e 's/.diff//g';\
	fi

# borra binarios
clean_bin:
	rm -f $(EJECUTABLE) 

# borra resultados de ejecución y comparación
clean_test:
	@rm -f $(TESTDIR)/*.sal $(TESTDIR)/*.diff $(TESTDIR)/*~

# borra binarios, resultados de ejecución y comparación, y copias de respaldo
clean:clean_test clean_bin
	@rm -f *~ $(HDIR)/*~ 


check-syntax:
	gcc -o nul -S ${CHK_SOURCES}
principal.cpp0000444000175200017520000002002313367641504012147 0ustar  fefefefe/*
  Programa principal.
  Intérprete de comandos.

  Lee comandos desde la entrada estándar, invoca a funciones e imprime en la
  salida estándar.

  Con el comando de nombre "Fin" termian la ejecución.

  Los comandos de nombres "max_cantidad_intervalos" y "max_volumen_intervalos"
  invocan a las funciones 'max_cantidad' y 'max_volumen' respectivamente.
  Ambos leen los atributos de los intervalos desde la entrada estándar y tras
  obtener la solución imprime es la salida estándar o bien el valor que
  corresponde a la solución o bien el mensaje "ERROR: hay solapamiento."

  El comando de nombre "test_tiempo" prueba la eficiencia en el tiempo de
  ejecucion de la función 'max_cantidad'. Lee desde la entrada la cantidad de
  intervalos que se van a generar, el posible rango de duración de cada ellos
  y el tiempo máximo que se acepta en la ejecución de la función.
  Si no se cumple el tiempo se imprime en la salida estándar el mensaje
  "ERROR: Limite de tiempo excedido." y el tiempo que llevó la ejecución.
  En otro caso se imprime "TEST TIEMPO OK" y se procede a controlar si hay
  solapamiento y a obtener al valor que corresponde a la solución.


  Laboratorio de Programación 3.
  InCo-FIng-UDELAR
 */

#include "include/intervalos.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <climits>
#include <time.h>

#define MAX_LONG_TXT 80

/*
  Devuelve un numero entero seudoaleatorio entre a y b
 */
uint rand(uint a, uint b) { return rand() % (b - a + 1) + a; }

/*
  Lee desde la entrada estándar 'cant_intervalos' con el formato
  inicio-fin-volumen
  Devuelve un arreglo con los intervalos leídos.
 */
intervalo_t *leer_intervalos(uint cant_intervalos) {
  intervalo_t *intervalos = new intervalo_t[cant_intervalos];
  for (uint i = 0; i < cant_intervalos; i++) {
    int res = scanf("%i - %i -%i", &intervalos[i].inicio, &intervalos[i].fin,
                    &intervalos[i].volumen);
    assert(res == 3);
    assert(intervalos[i].inicio < intervalos[i].fin);
    (void)res; // para evitar el warning al eliminar el assert
  }
  return intervalos;
}

/*
  Devuelve una copia de 'intervalos'.
 */
intervalo_t *copia_intervalos(intervalo_t *intervalos, uint cant_intervalos) {
  intervalo_t *copia = new intervalo_t[cant_intervalos];
  for (uint i = 0; i < cant_intervalos; i++)
    copia[i] = intervalos[i];
  return copia;
}

/*
  Reorganiza aleatoriamente los elementos de 'A', que tiene 'n' elementos.
 */
void shuffle(intervalo_t *A, uint n) {
  for (uint i = 0; i < n; i++) {
    uint j = i + rand(0, n - i - 1);
    intervalo_t tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
  }
}

/*
  Pre: 'cant_total' >= 'cant_sin_solapar' > 0.
  Pre: 'duracion_max' >= 'duracion_min' >= 1.
  Post: Devuelve un arreglo con 'cant_total' intervalos.
  La maxima cantidad de intervalos sin solapar es 'cant_sin_solapar'.
  La duracion de los intervalos devueltos esta entre 'duracion_min' y
  'duracion_max'.
 */
intervalo_t *generar_entrada(uint cant_total, uint cant_sin_solapar,
                             uint duracion_min, uint duracion_max) {
  intervalo_t *intervalos = new intervalo_t[cant_total];
  uint inicio = duracion_max;                   // defasaje inicial
  for (uint i = 0; i < cant_sin_solapar; i++) { // intervalos solucion
    int duracion = rand(duracion_min, duracion_max);
    intervalos[i].inicio = inicio;
    intervalos[i].fin = inicio + duracion;
    inicio = intervalos[i].fin;
  }
  for (uint i = cant_sin_solapar; i < cant_total; i++) { // intervalos solapados
    uint j = rand(0, cant_sin_solapar - 1);
    uint duracion = rand(duracion_min, duracion_max);
    uint fin = rand(intervalos[j].fin, intervalos[j].fin + duracion - 1);
    intervalos[i].inicio = fin - duracion;
    intervalos[i].fin = fin;
  }
  shuffle(intervalos, cant_total);
  return intervalos;
}

/*
  Devuelve 'true' si y solo si cada para de posiciones de 'solucion' cuyos
  valores son 'true' corresponden a identificadores en 'intervalos' que no se
  solapan. El chequeo se realiza en O(n*log(n))
 */
bool hay_solapamiento(bool *solucion, intervalo_t *intervalos, uint n) {
  int *seleccionados = new int[n];
  int cant_seleccionados = 0;
  for (uint i = 0; i < n; i++) {
    if (solucion[i]) {
      seleccionados[cant_seleccionados] = i;
      cant_seleccionados++;
    }
  }
  bool solapa = false;
  for (int i = 0; ((i < cant_seleccionados - 1) && (!solapa)); i++)
    for (int j = i + 1; ((j < cant_seleccionados) && (!solapa)); j++)
      if ((intervalos[seleccionados[i]].fin >
           intervalos[seleccionados[j]].inicio) &&
          (intervalos[seleccionados[j]].fin >
           intervalos[seleccionados[i]].inicio))
        solapa = true;

  delete[] seleccionados;
  return solapa;
}

int main() {

  srand(12345678);
  uint cont_comandos = 0;
  char nom_comando[MAX_LONG_TXT];
  bool salir = false;
  while (!salir) {
    // mostrar el prompt
    cont_comandos++;
    printf("%u>", cont_comandos);

    // leer el comando
    scanf("%s", nom_comando);

    // procesar el comando
    if (!strcmp(nom_comando, "Fin")) {
      salir = true;
      printf("Fin.\n");

    } else if (!strcmp(nom_comando, "#")) {
      char resto_linea[MAX_LONG_TXT];
      scanf("%[^\n]", resto_linea);
      printf("#%s.\n", resto_linea);

    } else if (!strcmp(nom_comando, "max_cantidad_intervalos")) {
      uint cant_intervalos;
      scanf("%i", &cant_intervalos);
      intervalo_t *intervalos = leer_intervalos(cant_intervalos);
      intervalo_t *copia = copia_intervalos(intervalos, cant_intervalos);
      bool *solucion = max_cantidad(copia, cant_intervalos);
      bool hay = hay_solapamiento(solucion, intervalos, cant_intervalos);
      if (hay)
        printf("ERROR: hay solapamiento. \n");
      else {
        uint cant = 0;
        for (uint i = 0; i < cant_intervalos; i++)
          if (solucion[i])
            cant++;
        printf("Cantidad: %i\n", cant);
      }

      delete[] copia;
      delete[] intervalos;
      delete[] solucion;

    } else if (!strcmp(nom_comando, "max_volumen_intervalos")) {
      uint cant_intervalos;
      scanf("%i", &cant_intervalos);
      intervalo_t *intervalos = leer_intervalos(cant_intervalos);
      intervalo_t *copia = copia_intervalos(intervalos, cant_intervalos);
      bool *solucion = max_volumen(copia, cant_intervalos);
      bool hay = hay_solapamiento(solucion, intervalos, cant_intervalos);
      if (hay)
        printf("ERROR: hay solapamiento. \n");
      else {
        uint vol = 0;
        for (uint i = 0; i < cant_intervalos; i++)
          if (solucion[i])
            vol += intervalos[i].volumen;
        printf("Volumen: %i\n", vol);
      }

      delete[] copia;
      delete[] intervalos;
      delete[] solucion;

    } else if (!strcmp(nom_comando, "test_tiempo")) {
      uint cant_total, cant_solucion, duracion_min, duracion_max, timeout;
      scanf("%i - %i -%i -%i -%i", &cant_total, &cant_solucion, &duracion_min,
            &duracion_max, &timeout);
      intervalo_t *intervalos = generar_entrada(cant_total, cant_solucion,
                                                duracion_min, duracion_max);
      intervalo_t *copia = copia_intervalos(intervalos, cant_total);
      clock_t t;
      t = clock();
      bool *solucion = max_cantidad(copia, cant_total);
      t = clock() - t;
      float tiempo_transcurrido = ((float)t) / CLOCKS_PER_SEC;
      if (tiempo_transcurrido > timeout)
        fprintf(stderr, "ERROR: Limite de tiempo excedido. (%.1f segundos)\n",
                tiempo_transcurrido);
      else {
        fprintf(stderr, "TEST TIEMPO OK\n");
        uint cant = 0;
        for (uint i = 0; i < cant_total; i++)
          if (solucion[i])
            cant++;
        bool hay = hay_solapamiento(solucion, intervalos, cant_total);
        if (hay)
          printf("ERROR: hay solapamiento. \n");
        else {
          printf("Cantidad: %i\n", cant);
        }
      }

      delete[] copia;
      delete[] intervalos;
      delete[] solucion;

    } else {
      printf("Comando no reconocido.\n");
    }
    // lee el resto de la línea
    fgets(nom_comando, MAX_LONG_TXT, stdin);

  } // while
}
include/intervalos.h0000444000175200017520000000166113367641504013453 0ustar  fefefefe/*
  Módulo de definición de `intervalos'.


  Laboratorio de Programación 3.
  InCo-FIng-UDELAR
 */

#ifndef _INTERVALOS_HPP
#define _INTERVALOS_HPP

typedef unsigned int uint;

struct intervalo_t {
  // fin > inicio
  uint inicio;
  uint fin;
  uint volumen;
};

/* Devuelve un arreglo de booleanos de 'n' con TRUE en los intervalos asignados,
   los cuales no se superponen.
   La cantidad de intervalos asignados debe ser la máxima posible.
   'intervalos' es un arreglo con 'n' intervalo_t.
   El tiempo de ejecucion de peor caso debe ser O(n*log(n)).
*/
bool *max_cantidad(const intervalo_t *intervalos, uint n);

/* Devuelve un arreglo de booleanos de 'n' con TRUE en los intervalos asignados,
   los cuales no se superponen.
   La suma de los volumenes de los intervalos asignados debe ser la máxima
   posible.
   'intervalos' es un arreglo con 'n' intervalo_t.
*/
bool *max_volumen(const intervalo_t *intervalos, uint n);

#endif
test/00.in0000444000175200017520000000052313367641504011213 0ustar  fefefefemax_cantidad_intervalos 
1
1-15-1
max_cantidad_intervalos 
2
1-15-1
15-30-1
max_cantidad_intervalos 
2
1-15-1
3-10-1
max_cantidad_intervalos 
3
1-15-1
3-20-1
15-30-1
max_volumen_intervalos
1
1-15-10
max_volumen_intervalos 
2
1-15-30
15-30-20
max_volumen_intervalos 
2
1-15-20
3-10-50
max_volumen_intervalos 
3
1-15-10
3-20-40
15-30-20
Fin
test/00.out0000444000175200017520000000016713367641504011420 0ustar  fefefefe1>Cantidad: 1
2>Cantidad: 2
3>Cantidad: 1
4>Cantidad: 2
5>Volumen: 10
6>Volumen: 50
7>Volumen: 50
8>Volumen: 40
9>Fin.
test/01.in0000444000175200017520000000027213367641504011215 0ustar  fefefefemax_cantidad_intervalos 
17
1-15-1
3-10-1
15-16-1
30-35-1
20-30-1
35-45-1
50-52-1
49-52-1
50-53-1
46-51-1
52-55-1
57-62-1
55-58-1
61-64-1
62-65-1
59-63-1
63-70-1
Fin
test/01.out0000444000175200017520000000002613367641504011413 0ustar  fefefefe1>Cantidad: 10
2>Fin.
test/02.in0000444000175200017520000000030713367641504011215 0ustar  fefefefemax_volumen_intervalos
17
3-10-30
1-15-10
15-16-13
20-30-1
30-35-1
35-45-1
46-51-10
50-52-5
49-52-30
50-53-50
52-55-10
55-58-20
57-62-50
59-63-50
61-64-80
62-65-70
63-70-40
Fin

test/02.out0000444000175200017520000000002613367641504011414 0ustar  fefefefe1>Volumen: 216
2>Fin.
test/03.in0000444000175200017520000000041213367641504011213 0ustar  fefefefemax_cantidad_intervalos 
30
1-15-1
2-8-1
15-30-1
27-35-1
20-33-1
9-15-1
10-22-1
25-40-1
45-63-1
50-57-1
4-35-1
10-42-1
30-58-1
61-64-1
63-75-1
59-63-1
63-70-1
43-75-1
60-78-1
67-70-1
8-15-1
30-33-1
39-55-1
25-43-1
38-40-1
48-77-1
65-77-1
74-78-1
34-42-1
50-68-1
Fin
test/03.out0000444000175200017520000000002513367641504011414 0ustar  fefefefe1>Cantidad: 9
2>Fin.
test/04.in0000444000175200017520000000044513367641504011222 0ustar  fefefefemax_volumen_intervalos 
30
1-15-18
2-8-35
15-30-46
27-35-57
20-33-12
9-15-10
10-22-98
25-40-24
45-63-1
50-57-37
4-35-88
10-42-54
30-58-23
61-64-19
63-75-15
59-63-70
63-70-1
43-75-86
60-78-72
67-70-65
8-15-43
30-33-16
39-55-80
25-43-78
38-40-75
48-77-28
65-77-45
74-78-47
34-42-50
50-68-21
Fin
test/04.out0000444000175200017520000000002613367641504011416 0ustar  fefefefe1>Volumen: 484
2>Fin.
test/05.in0000444000175200017520000000004713367641504011221 0ustar  fefefefetest_tiempo
10000000-45435-1-20-10
Fin
test/05.out0000444000175200017520000000003113367641504011413 0ustar  fefefefe1>Cantidad: 45435
2>Fin.