Programeer opdrachtenOpdracht : opdr5_marvin.txt

Terug naar de inzendingen
Opdracht 5,Marvin Raaimakers
24 April 2005
 Zo mijne is klaar: http://www.linux-box.nl/~marvin/src/route.tar.gz
 
 Zoals gevraagt, geeft mij programma aan of je naar links of naar rechts moet.
 Hij zegt dit echter niet, omdat het mij niet lukt om de festival C API
 hiervoor te gebruiken.
 
 De invoer
 Het programma maakt gebruikt van het invoerbestand 'map.in' om de kaart van te
 lezen. Op de eerste regel van dit bestand staat het getal N. vervolgens komen
 er N regels met de coordinaten van de steden. Deze regels bestaan uit een x en
 een y (integer) waarde gescheiden door een komma. De eerste stad is stad 'A',
 de tweede 'B', enz. Vervolgens volgen regels die de verbindingen tussen de
 steden aangeven. Zo'n regel begint met de letter van de ene stad, daarna volgt
 er een '-' en daarna de letter van de andere stad. Dat stad X met dat Y
 verbonden is betekend dat er van X naar Y en van Y naar X gereist kan worden.
 Het invoerbestand 'map.in' wat in de opdracht wordt beschreven, zal er dus zo
 uit zien:
 Code:
 6
 1,0
 4,0
 1,2
 2,2
 0,3
 4,4
 A-C
 A-E
 D-B
 C-D
 D-F
 F-E
 
 
 De uitvoer
 Als uitvoer wordt de begin- en eind bestemming weergeven, de lengte van de
 route en de route beschrijving.
 De route beschrijvinging bestaat uit delen, gescheiden door een '>', met de
 volgende syntaxis:
 Code:
 [X](richting,Y)
 
 Hierin is X de stad waar je je op dat moment bevindt en is Y de stad waar je
 naar toe moet rijden. 'richting' is de richting waarnaartoe je moet veranderen
 wanneer je van X naar Y gaat.
 
 Richting bepalen
 We reizen van punt F naar A naar T en willen weten naar welke kant (links of
 rechts) we onze richting moeten veranderen wanneer we op punt A zijn
 aangekomen. De coordinaten van de punten F, A en T zijn alle drie bekend.
 We gaan als volgt te werk:
 - Stel punt F gelijk aan (0,0)
 - Trek een lijn van F naar A
 - Trek een lijn door T de parallel loopt aan FA.
 Wanneer de x-coordinaat van A (Xa) groter is dan 0 dan kunnen we het volgende
 zeggen:
 - Wanneer lijn door T parallel aan FA, boven FA ligt is de richting links.
 - Wanneer lijn door T parallel aan FA, onder FA ligt is de richting rechts.
 Wanneer Xa kleiner is dan 0 geldt het omgekeerde.
 Wanneer lijn door T parallel aan FA, gelijk is aan FA, veranderen we niet van
 richting.
 De lijn door T parallel aan FA ligt boven FA wanneer het snijpunt met de y-as
 groter is dan 0 en ligt er onder wanneer deze kleiner is dan 0.
 We stellen een formule op voor de lijn FA:
 Code:
 f(x) = x * Ya/Xa
 
 en voor de lijn door T parallel aan FA:
 Code:
 g(x) = x * Ya/Xa + b
 
 'b' is hierin het snijpunt met de y-as en kunnen we berekenen:
 Code:
 Yt = Xt * Ya/Xa + b
 b = Yt - Xt * Ya/Xa
 
 We kunnen hiermee de volgende code schrijven:
 Code:
 if ((b > 0 && Xa > 0) || (b < 0 && Xa < 0))
 {
  richting = links;
 }
 else if ((b < 0 && Xa > 0) || (b > 0 && Xa < 0))
 {
  rigthing = rechts;
 }
 else
 {
  riching = verandert_niet;
 }
 
 We kunnen
 Code:
 (b > 0 && Xa > 0) || (b < 0 && Xa < 0)
 
 herschrijven als
 Code:
 b * Xa > 0
 
 en
 Code:
 (b < 0 && Xa > 0) || (b > 0 && Xa < 0)
 
 als
 Code:
 b * Xa < 0
 
 
 En zo bepalen we de richting. We zijn echter nog niet klaar, want het
 bovenstaande verhaaltje gaat niet op wanneer Xa = 0. Hiervoor schrijven we de
 volgende code:
 Code:
 if (Xto*Yat < 0)
 {
  richting = links;
 }
 else if (Xto*Yat > 0)
 {
  richting = rechts;
 }
 else
 {
  richting = verandert_niet;
 }
 1 
*****Makefile*****
  
 2TARGET = route
 3SOURCES = \
 4 route.c \
 5 clever.c
 6
 7CFLAGS=-I. -O2 -Wall
 8LINKFLAGS=-lm
 9CC=gcc
 10
 11OBJECTS=$(SOURCES:.c=.o)
 12
 13all: $(TARGET)
 14
 15cc:
 16 $(MAKE) CC=cc \
 17  all
 18
 19$(TARGET): $(OBJECTS)
 20 $(CC) $(LINKFLAGS) -o  $@ $(OBJECTS)
 21
 22clean:
 23 $(RM) $(TARGET) $(OBJECTS)
 1 
*****map.in*****
  
 26
 31,0
 44,0
 51,2
 62,2
 70,3
 84,4
 9A-C
 10A-E
 11D-B
 12C-D
 13D-F
 14F-E
 1 
*****map2.in*****
  
 25
 31,5
 40,1
 53,6
 65,2
 74,0
 8A-B
 9A-E
 10B-D
 11C-D
 12C-E
 13D-E
 1 
*****route.h*****
  
 2/*-------------------------------------------------------------------------------
 3Name               : route.h
 4Author             : Marvin Raaijmakers
 5Description        : The header file for route
 6Date of last change: 24-April-2005
 7
 8    Copyright (C) 2005 Marvin Raaijmakers
 9
 10    This program is free software; you can redistribute it and/or modify
 11    it under the terms of the GNU General Public License as published by
 12    the Free Software Foundation; either version 2 of the License, or
 13    any later version.
 14
 15    This program is distributed in the hope that it will be useful,
 16    but WITHOUT ANY WARRANTY; without even the implied warranty of
 17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 18    GNU General Public License for more details.
 19
 20    You should have received a copy of the GNU General Public License
 21    along with this program; if not, write to the Free Software
 22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 23
 24    You can contact me at: marvin_raaijmakers(at)linux-box(dot)nl
 25    (replace (at) by @ and (dot) by .)
 26---------------------------------------------------------------------------------*/
 27#define MAX_NUM_CITIES (26)
 28
 29#define UNKNOWN  (-1)
 30#define INFINITE (INT_MAX)
 31
 32#define MAP_FILE ("map.in")
 33
 34#define TRUE (1)
 35#define FALSE (0)
 36
 37#define city_to_char(_city) ((char)('A'+_city))
 38#define char_to_city(_city) ((char)(_city-'A'))
 39
 40typedef int Boolean;
 41typedef int CITY;
 42typedef int MAP[MAX_NUM_CITIES][MAX_NUM_CITIES];
 43
 44typedef struct {
 45 Boolean final;
 46 int distance;
 47 CITY previous_city;
 48} ROUTE_ELEMENT;
 49
 50typedef ROUTE_ELEMENT ROUTE[MAX_NUM_CITIES];
 51
 52typedef struct {
 53 int x,
 54  y;
 55} COORD;
 56
 57typedef enum {
 58 LEFT,
 59 NO_CHANGE,
 60 RIGHT
 61} DIRECTION;
 62
 63
 64extern void solve_route (int num_cities, CITY begin, CITY end, ROUTE *route, MAP map);
 65extern DIRECTION direction (COORD from, COORD at, COORD to);
 1 
*****route.c*****
  
 2/*-------------------------------------------------------------------------------
 3Name               : route.c
 4Author             : Marvin Raaijmakers
 5Description        : Program that calculates the routes
 6Date of last change: 24-April-2005
 7
 8    Copyright (C) 2005 Marvin Raaijmakers
 9
 10    This program is free software; you can redistribute it and/or modify
 11    it under the terms of the GNU General Public License as published by
 12    the Free Software Foundation; either version 2 of the License, or
 13    any later version.
 14
 15    This program is distributed in the hope that it will be useful,
 16    but WITHOUT ANY WARRANTY; without even the implied warranty of
 17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 18    GNU General Public License for more details.
 19
 20    You should have received a copy of the GNU General Public License
 21    along with this program; if not, write to the Free Software
 22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 23
 24    You can contact me at: marvin_raaijmakers(at)linux-box(dot)nl
 25    (replace (at) by @ and (dot) by .)
 26---------------------------------------------------------------------------------*/
 27#include 
 28#include 
 29#include 
 30#include 
 31
 32#include 
 33
 34/*                                   sqrt( dX^2 + dY^2 )                                         */
 35#define calc_dist(_from, _to) ((int) sqrt( pow((_from).x-(_to).x, 2) + pow((_from).y-(_to).y, 2) ))
 36
 37
 38static void get_locations (int num_cities, CITY *from, CITY *to);
 39static CITY get_city (int num_cities);
 40static void init_map (MAP *map);
 41static void read_map (MAP *map, COORD coord[MAX_NUM_CITIES], int *num_cities);
 42static void handle_invalid_map (FILE *file);
 43static void print_route (int num_cities, CITY begin, CITY end, ROUTE route, COORD coord[MAX_NUM_CITIES]);
 44
 45
 46void
 47init_map (MAP *map)
 48/*
 49Input:
 50 -
 51Output:
 52 map - The initialized map
 53Returns:
 54 -
 55Description:
 56 This function initializes map to be empty.
 57*/
 58{
 59 int from, to;
 60 
 61 for (from = 0; from < MAX_NUM_CITIES; from++)
 62 {
 63  for (to = 0; to < MAX_NUM_CITIES; to++)
 64  {
 65   (*map)[from][to] = 0;
 66  }
 67 }
 68}
 69
 70
 71void
 72handle_invalid_map (FILE *file)
 73{
 74 printf ("ERROR: The map file is invalid.\n");
 75 exit (1);
 76}
 77
 78
 79void
 80read_map ( MAP *map,
 81  COORD coord[MAX_NUM_CITIES],
 82  int *num_cities              )
 83/*
 84Input:
 85 -
 86Output:
 87 map  - The map read from the intput file.
 88 num_cities - The number of cities the map contains.
 89Returns:
 90 -
 91Description:
 92 This function reads the map from an input file.
 93*/
 94{
 95 int from, to,
 96  count;
 97 char char_from, char_to;
 98 FILE *file;
 99 
 100 file = fopen(MAP_FILE, "r");
 101 if (file == NULL)
 102 {
 103  printf ("ERROR: Could not open '%s'.\n", MAP_FILE);
 104  exit (1);
 105 }
 106 
 107 if (fscanf(file, "%d", num_cities) != 1)
 108 {
 109  handle_invalid_map (file);
 110 }
 111 else if (*num_cities > MAX_NUM_CITIES)
 112 {
 113  printf ("ERROR: The map '%s' contains more than %d cities, which is not allowed.\n",
 114   MAP_FILE, MAX_NUM_CITIES);
 115  exit (1);
 116 }
 117 else if (*num_cities <= 0)
 118 {
 119  printf ("ERROR: The map '%s' contains less than one city, which is not allowed.\n",
 120   MAP_FILE);
 121  exit (1);
 122 }
 123 else
 124 {
 125  for (count = 0; count < *num_cities && !feof(file); count++)
 126  {
 127   if (fscanf(file, "%d,%d\n", &(coord[count].x), &(coord[count].y)) != 2)
 128   {
 129    handle_invalid_map (file);
 130   }
 131  }
 132  if (count != *num_cities)
 133  {
 134   handle_invalid_map (file);
 135  }
 136  else
 137  {
 138   while (!feof(file))
 139   {
 140    if (fscanf(file, "%c-%c\n", &char_from, &char_to) != 2)
 141    {
 142     handle_invalid_map (file);
 143    }
 144    else
 145    {
 146     from = char_to_city(char_from);
 147     to = char_to_city(char_to);
 148     if (from < 0 || from >= *num_cities || to < 0 || from >= *num_cities || to == from)
 149     {
 150      handle_invalid_map (file);
 151     }
 152     else
 153     {
 154      (*map)[from][to] = calc_dist(coord[from], coord[to]);
 155      (*map)[to][from] = (*map)[from][to];
 156     }
 157    }
 158   }
 159  }
 160 }
 161}
 162
 163
 164void
 165print_route ( int num_cities,
 166  CITY begin,
 167  CITY end,
 168  ROUTE route,
 169  COORD coord[MAX_NUM_CITIES]  )
 170/*
 171Input:
 172 num_cities - The number of cities the map contains
 173 begin  - The city the route begins at
 174 end  - The city the route ends at
 175 route  - The route
 176 coord  - The coordinates of the cities
 177Output:
 178 -
 179Returns:
 180 -
 181Description:
 182 This function prints the route information to the stdout.
 183*/
 184{
 185 CITY city_stack[MAX_NUM_CITIES],
 186  city;
 187 int stack_size, count;
 188 
 189 if (route[end].distance == INFINITE)
 190 {
 191  printf ("There is no route from %c to %c.\n", city_to_char(begin), city_to_char(end));
 192 }
 193 else
 194 {
 195  city = end;
 196  for (stack_size = 0; route[city].previous_city != city; stack_size++)
 197  {
 198   city_stack[stack_size] = city;
 199   city = route[city].previous_city;
 200  }
 201  city_stack[stack_size] = city;
 202  
 203  printf ("            Start: %c\n"
 204   "              End: %c\n"
 205   "   Route distance: %d\n"
 206   "Route description: [%c](%c) > ",
 207   city_to_char(begin), city_to_char(end), route[end].distance,
 208   city_to_char(city_stack[stack_size]), city_to_char(city_stack[stack_size-1]));
 209  for (count = stack_size; count-1; count--)
 210  {
 211   printf ("[%c](", city_to_char(city_stack[count-1]));
 212   /*                 from                      at                          to                         */
 213   switch ( direction(coord[city_stack[count]], coord[city_stack[count-1]], coord[city_stack[count-2]]) )
 214   {
 215    case LEFT:
 216     printf ("left,");
 217     break;
 218    case RIGHT:
 219     printf ("right,");
 220     break;
 221    default:
 222     break;
 223   }
 224   printf ("%c) > ", city_to_char(city_stack[count-2]));
 225  }
 226  printf ("[%c]\n", city_to_char(end));
 227 }
 228}
 229
 230
 231CITY
 232get_city (int num_cities)
 233/*
 234Input:
 235 num_cities - The number of cities
 236Output:
 237 -
 238Returns:
 239 The city entered by the user.
 240Description:
 241 This function asks the user for a city in a range of num_cities cities.
 242*/
 243{
 244 char char_city;
 245 CITY city;
 246 
 247 printf ("Please enter a city in the range from %c to %c: ", city_to_char(0), city_to_char(num_cities-1));
 248 while (scanf("%c", &char_city) != 1 || (city = char_to_city(char_city)) < 0 || city >= num_cities)
 249 {
 250  printf ("The city you entered does not exist. Please reenter: ");
 251  getchar();
 252  city = -1;
 253 }
 254 getchar();
 255 return (city);
 256}
 257
 258
 259void
 260get_locations ( int num_cities,
 261  CITY *from,
 262  CITY *to         )
 263/*
 264Input:
 265 num_cities - The number of cities the map contains
 266Output:
 267 from  - The city to start
 268 to  - The city to ends
 269Returns:
 270 -
 271Description:
 272 This function asks the user to enter the city to start en the city to end.
 273*/
 274{
 275 do
 276 {
 277  printf ("FROM:\n  ");
 278  *from = get_city(num_cities);
 279  printf ("TO:\n  ");
 280  *to = get_city(num_cities);
 281  if (*from == *to)
 282  {
 283   printf ("\nPlease reenter seriously: \n");
 284  }
 285 } while (*from == *to);
 286}
 287
 288
 289int
 290main (void)
 291{
 292 MAP map;
 293 COORD coord[MAX_NUM_CITIES];
 294 ROUTE route;
 295 int num_cities;
 296 CITY from, to;
 297 
 298 init_map (&map);
 299 read_map (&map, coord, &num_cities);
 300 
 301 get_locations (num_cities, &from, &to);
 302 solve_route (num_cities, from, to, &route, map);
 303 print_route (num_cities, from, to, route, coord);
 304 
 305 return (0);
 306}
 1 
*****clever.c*****
  
 2/*-------------------------------------------------------------------------------
 3Name               : Clever.c
 4Author             : Marvin Raaijmakers
 5Description        : The clever functions for route
 6Date of last change: 24-April-2005
 7
 8    Copyright (C) 2005 Marvin Raaijmakers
 9
 10    This program is free software; you can redistribute it and/or modify
 11    it under the terms of the GNU General Public License as published by
 12    the Free Software Foundation; either version 2 of the License, or
 13    any later version.
 14
 15    This program is distributed in the hope that it will be useful,
 16    but WITHOUT ANY WARRANTY; without even the implied warranty of
 17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 18    GNU General Public License for more details.
 19
 20    You should have received a copy of the GNU General Public License
 21    along with this program; if not, write to the Free Software
 22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 23
 24    You can contact me at: marvin_raaijmakers(at)linux-box(dot)nl
 25    (replace (at) by @ and (dot) by .)
 26---------------------------------------------------------------------------------*/
 27#include 
 28
 29#include 
 30
 31void
 32solve_route ( int num_cities,
 33  CITY begin,
 34  CITY end,
 35  ROUTE *route,
 36  MAP map      )
 37/*
 38Input:
 39 num_cities - The number of cities on the map
 40 begin  - The city to begin
 41 end  - The city to end
 42 map  - The map containing information about the connections between the
 43     (num_cities) cities
 44Output:
 45 route  - The shortest route found from 'begin' to 'end'
 46Returns:
 47 -
 48Description:
 49 This function finds the shortest route from 'begin' to 'end' using information of 'map'.
 50*/
 51{
 52 int from, to,
 53  count,
 54  smallest_distance,
 55  nearest_city;
 56 
 57 /* Initialize route */
 58 for (to = 0; to < num_cities; to++)
 59 {
 60  (*route)[to].distance = INFINITE;
 61  (*route)[to].final = FALSE;
 62  (*route)[to].previous_city = UNKNOWN;
 63 }
 64 (*route)[begin].distance = 0;
 65 (*route)[begin].previous_city = begin; /* To identify that this is the city to start */
 66 
 67 for (count = 0; count < num_cities; count++)
 68 {
 69  smallest_distance = INFINITE;
 70  for (to = 0; to < num_cities; to++)
 71  {
 72   if ((*route)[to].distance != INFINITE &&
 73       !(*route)[to].final &&
 74       (*route)[to].distance < smallest_distance)
 75   {
 76    smallest_distance = (*route)[to].distance;
 77    nearest_city = to;
 78   }
 79  }
 80  (*route)[nearest_city].final = TRUE;
 81  from = nearest_city;
 82  /* Update all the distances (if needed) of the cities connected to nearest_city */
 83  for (to = 0; to < num_cities; to++)
 84  {
 85   /* If city 'to' is connected to nearest_city and the distance to 'to'
 86    * plus the distance from begin to nearest_city is smaller than the
 87    * (until now) found distance from begin to 'to'.
 88    */
 89   if (map[from][to] &&
 90       (map[from][to]+(*route)[from].distance < (*route)[to].distance ||
 91        (*route)[to].distance == INFINITE) &&
 92       !(*route)[to].final)
 93   {
 94    (*route)[to].distance = map[from][to]+(*route)[from].distance;
 95    (*route)[to].previous_city = nearest_city; /* To identify were we come from */
 96   }
 97  }
 98 }
 99}
 100
 101
 102DIRECTION
 103direction ( COORD from,
 104  COORD at,
 105  COORD to     )
 106/*
 107Input:
 108 from - The coordinates of the city we came from
 109 at - The coordinates of the city where we are now
 110 to - The coordinates of the city where we go to
 111Output:
 112 -
 113Returns:
 114 The direction (RIGHT, LEFT or NO_CHANGE) when we move from 'from' to 'at' and once
 115 arrived at 'at' change direction to 'to'.
 116Description:
 117 See above.
 118*/
 119{
 120 int Xat, Yat,
 121  Xto, Yto;
 122 DIRECTION direction;
 123 
 124 /* Correct the coordinates such that 'from' is at (0,0) */
 125 Xat = at.x - from.x;
 126 Xto = to.x - from.x;
 127 Yat = at.y - from.y;
 128 Yto = to.y - from.y;
 129 
 130 if (Xat == 0)
 131 {
 132  if (Xto*Yat < 0)
 133  {
 134   direction = LEFT;
 135  }
 136  else if (Xto*Yat > 0)
 137  {
 138   direction = RIGHT;
 139  }
 140  else
 141  {
 142   direction = NO_CHANGE;
 143  }
 144 }
 145 else if (Yto*Xat-Xto*Yat > 0)
 146 {
 147  direction = LEFT;
 148 }
 149 else if (Yto*Xat-Xto*Yat < 0)
 150 {
 151  direction = RIGHT;
 152 }
 153 else
 154 {
 155  direction = NO_CHANGE;
 156 }
 157 return (direction);
 158}
 
 
Mijn commentaar
 
 Marvin,
 Zoals we inmiddels van je gewend zijn een mooi stukje werk waarbij goede
 documentatie onontbeerlijk is.
 Eigenlijk heb ik verder heel weinig te vertellen, behalve dan dat ik vrees dat
 je welhaast dezelfde bijdrage kunt insturen voor opdracht 6.
 Zoals ik uit je werkwijze begrijp loop je gewoon de route af en kijkt dan
 hoever het is (zo zou ik het zelf ook doen).
 Ik had er graag meer over willen zeggen Marvin,
 maar je bijdrage is gewoon goed uitgewerkt en AF.
 Wat moet ik daar dan nog aan toevoegen ?