Nationwide Competition - Territory Tester [Part 1]

Hey Mates,
I have much to do at the moment, so I can’t publish that often, but I try to do as much as I can :slight_smile:.
However, I am currently studying for the “Bundeswettbewerb für Informatik” in germany which takes place in September (In english: Nationwide competition for informatics) and I thought these exercises could be interesting for you too! Whenever I’m finished with the next one I post the exercise description here and my solution, which will be probably in C#.


Description

This time you have to build a simple program which takes a territoy as input and prints out if it overlaps with other territories. The territories are given like this: 3385. The first two numbers are the x and y coordinate of the corner on the bottom left of the rectangle. The last two numbers represent the x and y coordinate of the top right point.
See the coordinate system below:

Here you can see 3 territories. The black and red one can get allowed, but the blue one overlaps, so it has to get disallowed!
Ok, I hope you understood the system.


My Solution

Here you can find a simple program in C# which takes the territories one by one and always prints out if they can get allowed or not.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Territory_Tester
{
    class Program
    {
        static void Main(string[] args)
        {
            List<String> areas = new List<String>();

            while (true)
            {
                //Get territory and validates
                String territory = input("\nYour territory (e.g. 3385): ");
                if (!validate(territory))
                    continue;

                //Build a list of all points in the rectangle
                List<String> points = getAllPoints(territory);

                //Tests if the rectangle can be allowed
                if(testTerritory(areas, points))
                {
                    areas.Add(territory);
                    Console.WriteLine("[*] This territory can get allowed!");
                }
                else
                {
                    Console.WriteLine("[!] This territory can't get allowed!");
                }
            }
        }

        /// <summary>
        /// Tests if the territory overlaps
        /// </summary>
        /// <param name="areas"></param>
        /// <param name="points"></param>
        /// <returns></returns>
        static bool testTerritory(List<String> areas, List<String> points)
        {
            foreach(String terr in areas)
            {
                foreach(String p in points)
                {
                    int x = int.Parse(p[0].ToString());
                    int y = int.Parse(p[1].ToString());

                    if(x < int.Parse(terr[2].ToString()) && x > int.Parse(terr[0].ToString()))
                    {
                        if (y < int.Parse(terr[3].ToString()) && y > int.Parse(terr[1].ToString()))
                            return false;
                    }
                }
            }

            return true;
        }

        /// <summary>
        /// This function builds a list with all points in the rectangle
        /// </summary>
        /// <param name="territory"></param>
        /// <returns></returns>
        static List<String> getAllPoints(String territory)
        {
            int x = int.Parse(territory[0].ToString());
            int y = int.Parse(territory[1].ToString());
            int xMax = int.Parse(territory[2].ToString());
            int yMax = int.Parse(territory[3].ToString());

            List<String> points = new List<String>();

            while (x <= xMax)
            {
                while(y <= yMax)
                {
                    String p = x.ToString() + y.ToString();
                    points.Add(p);

                    y += 1;
                }
                x += 1;
                y = int.Parse(territory[1].ToString());
            }

            return points;
        }

        /// <summary>
        /// Tests whether it's a valid territory
        /// </summary>
        /// <param name="territory"></param>
        /// <returns></returns>
        static bool validate(String territory)
        {
            //Tests the length
            if (territory.Length != 4)
            {
                Console.WriteLine("\n[!] Not a valid territory!");
                return false;
            }

            //Tests whether the input is a number
            try
            {
                int.Parse(territory);
            }
            catch
            {
                Console.WriteLine("\n[!] Not a valid territory!");
                return false;
            }

            return true;
        }

        /// <summary>
        /// Just a small input with given text function. It's like input() in Python.
        /// </summary>
        /// <param name="text"></param>
        /// <returns>User input</returns>
        static String input(String text)
        {
            Console.Write(text);
            return Console.ReadLine();
        }
    }
}

Conclusion

This can be seen as a good programming challenge. I think it’s good for learning to build up a strategy first and then work on accomplishing it. As always I hope you have fun with trying to solve this easy challenge.

|-TheDoctor-|

1 Like

You might be looking for the word “vertices”, “corners”, or simply “points”.
I didn’t finish reading it yet but wanted to help you out with that. :slight_smile:

1 Like

After my introducing I decide to learn C/C++ and I’m started about 1 week ago. So, look at my first solution written with C :slight_smile:

CTerritoryChecker.c file:

#include <stdio.h>
#include <stdlib.h>
#include "Rect.h"

int checkAllIntersections(Rect*, DynamicRectArray *);
int checkintersection(Rect *, Rect *);
int readnextrect(Rect *);
int isint(char *);
int chartoint(char *);

int main(void) {
	DynamicRectArray array;
	initializeRectArray(&array);
	Rect *currentRect = getNewRect(&array);

	while (1) {
		readnextrect(currentRect);
		if (checkAllIntersections(currentRect, &array)) {
			printf("[*] This territory can get allowed!\n");
			currentRect = getNewRect(&array);
		} else {
			printf("[!] This territory can't get allowed!\n");
		}
	}
	return EXIT_SUCCESS;
}

int checkAllIntersections(Rect * currentRect, DynamicRectArray *rects) {
	int i, j;
	for (i = 0; i < rects->used; i++) {
		Rect *r0 = &rects->elements[i];
		if (r0 != currentRect && checkintersection(r0, currentRect)) {
			return 0;
		}
	}
	return 1;
}

int checkintersection(Rect * r0, Rect * r1) {
	if ((r0->left < r1->right) && (r0->right > r1->left)
			&& (r0->top > r1->bottom) && (r0->bottom < r1->top)) {
		return 1;
	}
	return 0;
}

int readnextrect(Rect* rect) {
	printf("Enter territory (e.x. 3385):");
	int done = 0;
	int parsedCount = 0;
	while (!done) {
		char c = getchar();
		if (c == '\0' || c == '\n') {
			continue;
		} else {
			if (isint(&c)) {
				int val = chartoint(&c);
				switch (parsedCount) {
				case 0:
					rect->left = val;
					break;
				case 1:
					rect->bottom = val;
					break;
				case 2:
					rect->right = val;
					break;
				case 3:
					rect->top = val;
					done = 1;
					break;
				}
				parsedCount++;
			}
		}
	}
}

int isint(char *c) {
	return *c >= '0' && *c <= '9';
}

int chartoint(char *c) {
	return *c - '0';
}

Rect.h header file:

typedef struct {
	int left;
	int right;
	int top;
	int bottom;
} Rect;

typedef struct {
	Rect * elements;
	size_t used;
	size_t size;
} DynamicRectArray;

void initializeRectArray(DynamicRectArray * arr) {
	arr->used = 0;
	arr->size = sizeof(Rect) * 2;
	arr->elements = (Rect*) malloc(arr->size);
}

Rect* getNewRect(DynamicRectArray * arr) {
	if (arr->used == arr->size) {
		arr->size += 1;
		arr->elements = (Rect*) realloc(arr->elements, arr->size);
	}

	Rect * r = &arr->elements[arr->used++];
	r->left = r->right = r->top = r->bottom = 0;
	return r;
}
1 Like

Yeah and I’m studying C for about 1 week and a half and just got done coding the Linux Kernel.

3 Likes

@JaCube you shouldn’t use raw pointers in C++… I’m not one to talk, though…

EDIT: Crap, I saw the “C/C++” and assumed C++. Oh, well…

But then again: C and C++ are not the same. Good C code makes for awful C++ code. So, don’t think you’re learning C/C++, understand you are learning C or C++.

1 Like

Alright. Here’s my solution in the beautiful C++ Programming Language:

#include <iostream>
#include <vector>
 
struct rectangle {
    int bottom_left_x,
        bottom_left_y,
        top_right_x,
        top_right_y;
};
 
bool check_territory(const std::vector<rectangle>& graph, const rectangle& to_check);
bool are_ints(const std::string& str);
 
int main() {
    std::vector<rectangle> graph;
    std::string input;
    rectangle new_rect;
    while(true) {
        std::cout << "[!] Input graph coords. ";
        std::cin >> input;
 
        if (input.size() != 4 || !are_ints(input)) {
            std::cout << "[!] ERROR: Invalid Input. Try again..." << std::endl;
            continue;
        }
 
        new_rect = {
            int(input[0]) - 48,
            int(input[1]) - 48,
            int(input[2]) - 48,
            int(input[3]) - 48
        };
 
        if (check_territory(graph,new_rect)) {
            graph.push_back(new_rect);
            std::cout << "[!] This rectangle will fit. "
                << "Adding to graph... Ctrl+C to finish. "
                << std::endl;
        } else {
            std::cout << "[!] This rectangle does not fit. Try again."
                << std::endl;
        }
    }
    return 0;
}
 
bool check_territory(const std::vector<rectangle>& graph, const rectangle& to_check) {
    if (graph.size() == 0) return true;
 
    for (auto& rect : graph) {
        if ( !( to_check.bottom_left_x < rect.bottom_left_x
                || to_check.bottom_left_y < rect.bottom_left_y )
            || !( to_check.top_right_x > rect.top_right_x
                || to_check.top_right_y > rect.top_right_y )
            || !( to_check.bottom_left_x < rect.top_right_x
                || to_check.bottom_left_y < rect.top_right_y )
            || !( to_check.top_right_x > rect.bottom_left_x
                || to_check.top_right_y > rect.bottom_left_y )
            || !( to_check.bottom_left_x > rect.top_right_x
                || to_check.top_right_y < rect.bottom_left_y )
            || !( to_check.top_right_x < rect.bottom_left_x
                || to_check.bottom_left_y > rect.top_right_y )
            )
        {
            return false;
        }
    }
 
    return true;
}
 
bool are_ints(const std::string& str) {
    for (auto& c : str)
        if (c < '0' || c > '9')
            return false;
 
    return true;
}

Line Count: 78

Here is an alternative pastebin link.

I’ll gladly explain this code if someone doesn’t “get it.”

1 Like

Sure, I’m just told C/C++ because I’m planned to learn C++ too (after C). In the next time, I’ll be more attentive to things like this.

1 Like

Well, when you start to learn C++, there will be a few things you’ll have to rethink. Again: good C code makes for bad C++.

This topic was automatically closed after 30 days. New replies are no longer allowed.