 Nationwide Competition - Territory Tester [Part 1]

(The C# Dude) #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 .
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;

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))
{
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.ToString());
int y = int.Parse(p.ToString());

if(x < int.Parse(terr.ToString()) && x > int.Parse(terr.ToString()))
{
if (y < int.Parse(terr.ToString()) && y > int.Parse(terr.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.ToString());
int y = int.Parse(territory.ToString());
int xMax = int.Parse(territory.ToString());
int yMax = int.Parse(territory.ToString());

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

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

y += 1;
}
x += 1;
y = int.Parse(territory.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);
}
}
}
``````

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

(CTRLtheALTofDELETE) #2

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. 1 Like

(Jakub) #3

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 `CTerritoryChecker.c` file:

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

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

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

while (1) {
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;
}

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

#4

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

3 Likes

(oaktree) #5

@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

(oaktree) #6

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) - 48,
int(input) - 48,
int(input) - 48,
int(input) - 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

(Jakub) #7

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

(oaktree) #8

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++.

0 Likes

(system) closed #9

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

0 Likes