Coding Comp

TheCheeseDemon

Pimped.
EnigmaClusive
Jr. Member

Online

Posts: 80

Respect: 0

Coding Comp

« on: February 02, 2012, 12:14:26 PM »

If you make the first working solution to the previous problem then you set the next and so on - try to make them more logical challenges rather then app type things.

I shall start -
Write a program which reverses all the individual words in a sentence i.e. Hello thar, wtf you suck. becomes olleH raht, ftw uoy kcus.
In doing this the only functions you can use(or the equivalent tools in whatever language your using) for any s are s.equals(""), s.charAt(0), s.substring(1). To build a string you can use concatenation of two strings s1+s2, the empty string "" and concatenation of a character and a string (s+c) or (c+s). You may also write other functions and use them (for example, if you write the reverse function, you can then use it in other functions), but clearly these functions should only use the "essential" functions themselves.
No ints(etc) allowed!

Enjoy n' ting.


	Logged

* PackagedGeek404 is now known as CockVein
* CockVein is now known as SmallCockVein
---------------------------------------------
<TheCheese> mrgragons i'll diss yo boogie as much I want, ain't got shit on mine!
<TheCheese> *mrdragons
<st3alth> TheCheese: You are a self admitted fag
<TheCheese> So anyway, whats everyone up to?
<st3alth> FUCK YOU I KNOW YOU CAN READ THIS
<mrdragons> nm, just chillin
<st3alth> STOP SHUNNING ME

Rik

asshat
Full Member

Online

Posts: 150

Respect: +2

Re: Coding Comp

« Reply #1 on: February 02, 2012, 04:38:35 PM »

Does the end result require me to actually have the reversed string stored somewhere ? or do I just have to output it?


	Logged

TheCheeseDemon

Pimped.
EnigmaClusive
Jr. Member

Online

Posts: 80

Respect: 0

Re: Coding Comp

« Reply #2 on: February 03, 2012, 12:40:27 PM »

Yeah - have it stored.


	Logged

Rik

asshat
Full Member

Online

Posts: 150

Respect: +2

Re: Coding Comp

« Reply #3 on: February 04, 2012, 12:49:01 PM »

Code: [Select]

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

int main( int argc, char *argv[] )
{
 if( argc != 2 ) { printf("%s \"<string>\"\n\n",argv[0]); return 1; }
 
 char *end = argv[1];
 while( *end ) ++end;

 char temp, *word_start, *word_end, *next_word = argv[1];
 
 while( next_word != end )
 {
   while( *next_word == ' ' ) ++next_word;
   if( *next_word == '\0' ) break;
   
   word_start = word_end = next_word;
   while( (word_end < end) && (*word_end != ' ') ) ++word_end;
   next_word = word_end;
   --word_end;
   
   while( word_start <= word_end ) 
    {
      temp = *word_start;
      *word_start++ = *word_end;
      *word_end-- = temp;
    }
 }
 
 printf("Output: %s\n\n",argv[1]);
 
 return 0;   
}


« Last Edit: February 04, 2012, 12:50:58 PM by Rik »	Logged

TheCheeseDemon

Pimped.
EnigmaClusive
Jr. Member

Online

Posts: 80

Respect: 0

Re: Coding Comp

« Reply #4 on: February 04, 2012, 12:56:32 PM »

Rik wins - set the next problem

Heres how I originally did it -

Code: [Select]

public static String splitReverse(String in){
	String out= "", word="";
	while(true){
		if(in.equals("")){
			out+=reverse(word);
			return out;
		}
		else if((in.charAt(0)>=65 && in.charAt(0)<=89) || (in.charAt(0) >=97 && in.charAt(0) <= 122) )
			word+=in.charAt(0);
		else{
			out += reverse(word) + in.charAt(0);
			word="";
		}
		in = in.substring(1);
		
	}
}
public static String reverse(String s){
	String out= "";
	return reverse2(s,out);
}
public static String reverse2(String s, String out){
		if(s.equals("")) return out;
		out = s.charAt(0) + out;
		s = s.substring(1);
		return reverse2(s,out);
}

}


	Logged

Rik

asshat
Full Member

Online

Posts: 150

Respect: +2

Re: Coding Comp

« Reply #5 on: February 04, 2012, 01:29:13 PM »

Next challenge.

You have two integer arrays. It doesn't matter whether you enter them from standard input, or read them from a file, or get them from the command line. The one important thing is that the integer arrays can be of variable length. The goal is to merge these two integer arrays into one new array. However, in the new array, the integers must be sorted in ascending order and there can be no duplicates.

Array 1: 1 0 5 8 4
Array 2: 3 7 2 5 6

Merged: 0 1 2 3 4 5 6 7 8


	Logged

psychomarine

Owner, Creator
Administrator
Veteran

Online

Posts: 1185

Respect: +1339

Re: Coding Comp

« Reply #6 on: February 04, 2012, 03:15:38 PM »

apparently my submission was too small, and reminded rik of his pecker.

even though it worked, it was not big enough to be impressive.

It has now been removed.

thanks,
psychomarine


« Last Edit: February 04, 2012, 08:55:36 PM by psychomarine »	Logged

DrOptix

Veteran Member
Jr. Member

Offline

Posts: 52

Respect: 0

Re: Coding Comp

« Reply #7 on: February 05, 2012, 12:12:53 PM »

Code: [Select]

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int main(int argc, char** argv) {
	int i, j, k, n, m;
	int x[50], y[50], z[100];

	// read some data
	ifstream fin("nr.in");
	fin >> n;
	for (i = 0; i < n; ++i) {
		fin >> x[i];
	}
	fin >> m;
	for(j = 0; j < m; ++j) {
		fin >> y[j];
	}
	fin.close();

	// sort input arrays (i assume the input arrays are not sorted)
	sort(x, x + n);
	sort(y, y + m);

	// do the merge
	i = j = 0; k = -1;
	while ((i < n) && (j < m)) {
		if (x[i] < y[j]) {
			z[++k]=x[i++];
		} else {
			z[++k]=y[j++];
		}
	}
		
	if (i < n) {
		for (j = i; j < n; ++j) {
			z[k++] = x[j];
		}
	} else {
		for (i = j; i < m; ++i) {
			z[k++] = y[i];
		}
	}
	
	
	// Output the result
	cout << endl << "New array \"z\":" << endl;
	for (i = 0; i < k; ++i) {
		cout << z[i] << " ";
	}
	
	return 0;
}


« Last Edit: February 05, 2012, 12:14:41 PM by DrOptix »	Logged

TheCheeseDemon

Pimped.
EnigmaClusive
Jr. Member

Online

Posts: 80

Respect: 0

Re: Coding Comp

« Reply #8 on: February 07, 2012, 11:58:43 AM »

DrOptix solution is a go - set the next problem

(posted because rik is a lazy ho)


	Logged

DrOptix

Veteran Member
Jr. Member

Offline

Posts: 52

Respect: 0

Re: Coding Comp

« Reply #9 on: February 07, 2012, 02:35:09 PM »

I want to propose two things. The first one is easier but the second one is a little bit tricky but fun too Here we go:

First problem:

Quote

Find the minimum spanning tree (aka MST) in a graph with N nodes and E edges.

The input has this format:

Quote

N E
Each edge definition has this form: X Y C. Interpret it like this: There is an edge from node X to node Y with a cost C.

The output has this format:

Quote

The total cost of the MST
Number of edges in the MST
Edge 1 from MST
Edge 2 from MST
and so on

Input example:

Quote

9 14
1 2 10
1 3 -11
2 4 11
2 5 11
5 6 13
3 4 10
4 6 12
4 7 5
3 7 4
3 8 5
8 7 5
8 9 4
9 7 3
6 7 11

Output example:

Quote

37
8
3 1
7 9
7 3
9 8
7 4
2 1
5 2
7 6

The second problem:

Quote

Implement a function that take a real (float, better double) number as parameter and returns the binary logarithm of that number. You are allowed to use only this mathematical operations: +, -, *, /, sqrt.

This problem is not my creation. It is inspired from a job interview example I found on InfoArena, one of the main training sites for Computer Science Olympiad here in Romania.

As a side note I'm a person that hate math when it is too abstract but this little problem made me to take another look at logarithms operations and it has a really good practical importance: implementation of logarithms related functions from math module of C lib.

README:

I'm also working at a solution for the 2nd problem
Please try to find an optim algorithm. For example if you need to sort something use something that runs in O(n log n) not O(n²)
If you find a solution please explain it in a few words. Comment your code or write a little README when you post the solution.

Thank you for your attention and happy hacking!


« Last Edit: February 08, 2012, 02:29:05 PM by DrOptix »	Logged

DrOptix

Veteran Member
Jr. Member

Offline

Posts: 52

Respect: 0

Re: Coding Comp

« Reply #10 on: February 08, 2012, 02:31:03 PM »

UPDATE 1 - New post because updates don't bump it on the timeline
I have an idea for Problem 2. Let's assume we want to compute binary logarithm from 321.
I plan to compute it recursively like this:

Quote

log2(321) = log2(2 * [321/2]) = = 1 + log2(160) = 1 + log2(2 * [160/2]) = 2 + log2(80) = 2 + log2(2 * [80/2]) = 3 + log2(40) = 4 + log2(20) = 5 + log2(10) = 6 + log2(5) = 7 + log2(2) = 8 + log2(1).

Even if I have a mistake above I hope you got the idea. WolframAlpha says Log2(321) = 8.3264. This means that my idea is good at least for the integer part of the result.

As you can see I'm using the fact that log_bb = 1. But it bugs me when it comes to compute the decimal part of a logarithm also I'm not really sure how this idea will behave for negative numbers.

I'll play a little more on the paper and I'll come with an update.


	Logged

DrOptix

Veteran Member
Jr. Member

Offline

Posts: 52

Respect: 0

Re: Coding Comp

« Reply #11 on: February 13, 2012, 11:42:15 AM »

I see no one try to do this. Here is my solution for the MST problem. It uses Kruskal's algorithm and disjoint set data structure:

Code: [Select]

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

struct Node {
	int rank;
	int father;
};

struct Edge {
	int cost;
	int x;
	int y;
};

void init_forest(int node, Node* forest) {
	forest[node].rank = 0;
	forest[node].father = node;
}

int find_root(int node, Node* forest) {
	if (forest[node].father != node) {
		forest[node].father = find_root(forest[node].father, forest);
	}
	return forest[node].father;		
}

void union_trees(int node_a, int node_b, Node* forest) {
	int x_root = find_root(node_a, forest);
	int y_root = find_root(node_b, forest);
	
	if (x_root == y_root) {
		return;
	}
	
	if (forest[x_root].rank < forest[y_root].rank) {
		forest[x_root].father = y_root;
	} else if (forest[x_root].rank > forest[y_root].rank) {
		forest[y_root].father = x_root;
	} else {
		forest[y_root].father = x_root;
		forest[y_root].rank += 1;
	}
}

int edge_cmp_func(Edge x, Edge y) {
	return x.cost < y.cost;
}

#define MAXN 400100

int main(int argc, char** argv) {
	int n, e;
	Node forest[MAXN];
	Edge edges[MAXN];
	
	FILE* fin = fopen("apm.in", "r");
	FILE* fout = fopen("apm.out","w");
	
	fscanf(fin, "%d%d", &n, &e);
	for (int i = 0; i < e; ++i) {
		fscanf(fin, "%d %d %d", &edges[i].x, &edges[i].y, &edges[i].cost);
	}
	fclose(fin);
	
	for (int i = 0; i < n; ++i) {
		init_forest(i, forest);
	}
	
	sort(edges, edges + e, edge_cmp_func);
	
	int answear = 0;
	vector<int> answear_edges_index;
	
	for (int i = 0; i < e; ++i) {
		if (find_root(edges[i].x, forest) != find_root(edges[i].y, forest)) {
			union_trees(edges[i].x, edges[i].y, forest);
			answear += edges[i].cost;
			answear_edges_index.push_back(i);
		}
	}

	fprintf(fout, "%d\n%d\n", answear, answear_edges_index.size());
	for (int i = 0; i < answear_edges_index.size(); ++i) {
		fprintf(fout, "%d %d\n", edges[answear_edges_index[i]].x, edges[answear_edges_index[i]].y);
	}
	fclose(fout);
	
	return 0;
}