DWITE - Programming Contest

[Shanethe13]

The third round of this year's DWITE contest just finished a few hours ago, so I thought I'd see whether any other Facepunchers participated.

For those of you don't know, DWITE is basically a Canadian programming contest run 8 times (previously 4 times) a year, within many Canadian schools. You are given five problems to complete in a three hour period, and your solutions are scored in real-time as you submit them to the website.

Typically, the difficulty of the problems will range from insanely easy ([url]http://dwite.ca/questions/iProfits.html[/url]) to downright impossible ([url]http://dwite.ca/questions/portals_redux.html[/url]) over the course of a single contest. (Okay, maybe not impossible, but that last one was pretty intense)

As you complete a problem, your team is able to upload the solution to the website, where an automated judge will confirm that it works, before awarding points based on execution speed, time remaining in the contest, and whether you were the first team to solve a particular problem. Overall, the contest doesn't actually count for anything, but it is a few hours of fun practice.

Anyways, who else participated, and how did you do? My team ended up in the mid 40s or so out of about 200 teams, but we would have got about 22nd if I hadn't screwed up the uploading process for question two, and uploaded a corrupt file.

If you didn't write the contest, I'd highly recommend talking to a math/computer science teacher at your school, and see if they can get your school registered. There is still five contests planned for the current school year, and its a blast.

[url]www.DWITE.ca[/url]

[ritave]

Downright impossible? I think not... You use dynamic algorithm to see where the rooms are, make the graph out of portals, and then dfs the crap out of it, write it out. Although it's requires some writing, the algorithms for it aren't really that hard, it just needs some time.

Also, why is it needed to read and write to a file? Server should convert standard input/output (with >> in linux) to a file, safer for server and easier for contestants :D

Also also, OH MY GOD! 2 and a half second?! That's outrageously long for such a small limit (20x20) that means there can max be only 400 graph leaves

Also also also, I'm talking about the hardest question.

[b]Edit:[/b] Changed [i]make the graph out of it[/i] to [i]make the graph out of portals[/i]

[nullsquared]

This is VERY interesting!

My school enters a similar competition at a local college, 6 or 7 problems in 2.5 hours. They're not always this impressive (a few are, though), and the competition isn't as large-scale, but it's fun.

I'm going to try the portals problem right now, i really like it.

[editline]03:32PM[/editline]

[QUOTE=Ritave;19010220]You use dynamic algorithm to see where the rooms are, make the graph out of it, and then dfs the crap out of it, write it out.[/QUOTE]

Just a general tip, making a data structure representation out of anything on these type of competition problems is usually the wrong way to do it. It's easiest to work directly with the data as it is.

[ritave]

Yeah, but it often might be faster ;)
And I didn't find a memory limit in this one.

[nullsquared]

[QUOTE=Ritave;19028494]Yeah, but it often might be faster ;)
And I didn't find a memory limit in this one.[/QUOTE]

Not at all; in this case it'd be much *slower*. All you need to do here is flood-fill the grid, best accomplished using the 2D grid of char's itself instead of messing with complex structural versions of it. I'll code up a solution for it in a bit as I've been wanting to do that problem for a while now.

[NukePower]

I'll try and do a functional when I finish up some of my projects. Can't wait :D.

[nullsquared]

Here's my C++ solution I just whipped up for PortalsRedux:
[cpp]
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <map>
#include <utility>
#include <set>

typedef std::vector<char> row_t;
typedef std::vector<row_t> grid_t;
typedef std::pair<int, int> point_t;
typedef std::set<char> result_t;
typedef std::map<char, point_t> portals_t;

void merge(result_t &a, const result_t &b)
{
a.insert(b.begin(), b.end());
}

result_t flood(const point_t &p, const grid_t &grid, portals_t &portals, grid_t &explored)
{
if (p.first < 0 || p.second < 0 || p.first >= grid.size() || p.second >= grid[0].size())
return result_t(); // point out of bounds

if (explored[p.first][p.second])
return result_t(); // already explored

explored[p.first][p.second] = true; // set us to already explored

const char &c = grid[p.first][p.second];

if (c >= 'a' && c <= 'j') // we're a portal entrance, go through
return flood(portals[c], grid, portals, explored);

result_t ret;
if (c >= '1' && c <= '5') ret.insert(c); // found a point of interest

merge(ret, flood(point_t(p.first - 1, p.second), grid, portals, explored));
merge(ret, flood(point_t(p.first + 1, p.second), grid, portals, explored));
merge(ret, flood(point_t(p.first, p.second - 1), grid, portals, explored));
merge(ret, flood(point_t(p.first, p.second + 1), grid, portals, explored));

return ret;
}

int main(int argc, char *argv[])
{
std::ifstream in(argc > 1 ? argv[1] : "PortalsRedux.txt");
int rows, cols; in >> rows >> cols;

portals_t portals;
std::map<char, point_t> interests;

grid_t grid(rows, row_t(cols, '.'));
grid_t explored(rows, row_t(cols, false));
for (int r = 0; r < rows; ++r)
{
for (int c = 0; c < cols; ++c)
{
char &p = grid[r][c];
in >> p;

if (p >= 'A' && p <= 'J') portals[std::tolower(p)] = point_t(r, c); // exit portal
else if (p >= 'a' && p <= 'j'); // entry portal
else if (p >= '1' && p <= '5') interests[p] = point_t(r, c); // point of interest
else if (p == '.'); // open space
else explored[r][c] = true; // everything else is off bounds
}
}

bool addNL = false; // should we add a new line?
for (std::map<char, point_t>::iterator i = interests.begin(); i != interests.end(); ++i)
{
if (addNL) std::cout << "\n"; else addNL = true;
grid_t exploredCopy = explored; // different starting points need a fresh explored map
std::cout << i->first << ":";
result_t r = flood(i->second, grid, portals, exploredCopy);

bool addSpace = false;
for (result_t::iterator j = r.begin(); j != r.end(); ++j)
{
if (*j == i->first) continue; // omit the one we're starting from
if (addSpace) std::cout << " "; else addSpace = true;
std::cout << *j;
}
}
}

[/cpp]

[NukePower]

[QUOTE=nullsquared;19132425]Here's my C++ solution I just whipped up for PortalsRedux:

(Mountain of C=C+1 code)[/QUOTE]

I lose. Haskell isn't the right tool for this job, pointers are just way too useful.

[nullsquared]

[QUOTE=NukePower;19137167]I lose. Haskell isn't the right tool for this job, pointers are just way too useful.[/QUOTE]

Heh, so use C# or something, C++ isn't [i]required[/i] :)

(btw, I didn't use any pointers in there :v:)

[Shanethe13]

[QUOTE=NukePower;19137167]I lose. Haskell isn't the right tool for this job, pointers are just way too useful.[/QUOTE]

Give some of the other problems a try then. Looks great, Nullsqared. Have you ever messed with node graphs? Here's one I'm about to try now;

[url]http://dwite.ca/questions/up_to_four_colours.html[/url]

I didn't get a chance to do it during the actual contest.

[nullsquared]

[QUOTE=Shanethe13;19137451]
[url]http://dwite.ca/questions/up_to_four_colours.html[/url]

I didn't get a chance to do it during the actual contest.[/QUOTE]

Yup I looked at that one but didn't pay much attention to it, I'll get back to you when I try it tomorrow :) It's interesting how both PortalsRedux and UpToFourColors are "Level 5" problems, yet PortalsRedux is so much easier (well, in my opinion, at least).

[Shanethe13]

[QUOTE=nullsquared;19137506]Yup I looked at that one but didn't pay much attention to it, I'll get back to you when I try it tomorrow :) It's interesting how both PortalsRedux and UpToFourColors are "Level 5" problems, yet PortalsRedux is so much easier (well, in my opinion, at least).[/QUOTE]

Honestly, I didn't even finish reading PortalsRedux. I opened the page once, had to go, and never got around to giving it a try. It was just how messy the input looked that made me assume it was hard.

UpToFourColours doesn't seem too bad. I have most of it worked out now, and I'm just putting it into code. I've never worked with node graphs before though, so it took a bit of research before getting started.

[NukePower]

[QUOTE=nullsquared;19137445]Heh, so use C# or something, C++ isn't [i]required[/i] :)

(btw, I didn't use any pointers in there :v:)[/QUOTE]

Accessing members of a stateful array is using pointers, actually. I know that arrays are an interface on top of pointers, but that's the functionality I'm talking about. You can modify state. In haskell I'd have to recursively re-pass the array, which isn't as efficient.

[nullsquared]

[QUOTE=Shanethe13;19138029]Honestly, I didn't even finish reading PortalsRedux. I opened the page once, had to go, and never got around to giving it a try. It was just how messy the input looked that made me assume it was hard.[/QUOTE]

Try it, it's fun.

[editline]09:41PM[/editline]

[QUOTE=NukePower;19138183]Accessing members of a stateful array is using pointers, actually.[/QUOTE]

That's like saying "using loops is using goto's, actually (on the assembly level)"

[NukePower]

[QUOTE=nullsquared;19138383]
That's like saying "using loops is using goto's, actually (on the assembly level)"[/QUOTE]

Sorry if I described a more general idea than you expected. By saying you can use pointers, I was basically implying you can use state + data structure easily and efficiently.

You can say I want cell (3,4) to change to 5. I can't. Just different approaches.

[Shanethe13]

Awesome, the code worked first try. Which is odd, since after running it I realized that I had missed two lines that I thought were crucial. Oh well!

import java.io.*;
import java.util.*;

public class D3_5 {
    public static void main(String[] args) throws IOException {
        Scanner input = new Scanner(new FileReader("D3_5in.txt"));
        PrintWriter output = new PrintWriter(new FileWriter("D3_5out.txt"));
        for(int i = 0; i < 5; i++) {
            Integer graphSize = input.nextInt();
            boolean[][] nodeGraph = new boolean[graphSize][graphSize];
            for(int j = 0; j < graphSize; j++) {
                Integer firstNode = input.nextInt() - 1;
                Integer secondNode = input.nextInt() - 1;
                nodeGraph[firstNode][secondNode] = true; //Undirected graph, so both
                nodeGraph[secondNode][firstNode] = true; //ordered pairs are true
            }
            Integer[] nodeColours = new Integer[graphSize];
            Arrays.fill(nodeColours, 1); //All nodes must be coloured
            for(int j = 0; j < graphSize; j++) {
                for(int k = j + 1; k < graphSize; k++) {
                    if(nodeGraph[j][k]) { //If two nodes are connected
                        if(nodeColours[j] == nodeColours[k]) { //If connected nodes are coloured the same
                            nodeColours[k] += 1;
                        }
                    }
                }
            }
            Integer highestColour = 0; //Pointless comment is pointless
            for(int j = 0; j < graphSize; j++) {
                if(highestColour < nodeColours[j]) { highestColour = nodeColours[j]; }
            }
            if(highestColour > 4) { highestColour = 0; }
            System.out.println(highestColour);
            output.println(highestColour);
        }
        output.close();
        System.exit(0);
    }
}

There's my Java solution for UpToFourColours.

[NukePower]

[QUOTE=Shanethe13;19139337]Awesome, the code worked first try. Which is odd, since after running it I realized that I had missed two lines that I thought were crucial. Oh well!

(Code monkey likes tab and mountain dew)

There's my Java solution for UpToFourColours.[/QUOTE]

That's a unique style lol. Open spaces before and after the class definition and a huge block of text inside? :P

[Shanethe13]

[QUOTE=NukePower;19139897]That's a unique style lol. Open spaces before and after the class definition and a huge block of text inside? :P[/QUOTE]

Every line break I leave out is one byte saved. I'm sure my ISP appreciates it when it comes time upload my solutions.

[NukePower]

[QUOTE=Shanethe13;19140216]Every line break I leave out is one byte saved. I'm sure my ISP appreciates it when it comes time upload my solutions.[/QUOTE]

Why not remove the class def \n's? =P

[Shanethe13]

[QUOTE=NukePower;19140338]Why not remove the class def \n's? =P[/QUOTE]

The space at the end was accidental, I hadn't noticed it until you said something :P As for the liberal use of space for curly braces, I blame OCD.

[HubmaN]

Go to the directory above. Trying to find the other questions gives me the Llama Song.

[nullsquared]

Oh, neat little solution you made there. I don't want to read it quite yet, I want to make my own today :v:

[Shanethe13]

[QUOTE=nullsquared;19145761]Oh, neat little solution you made there. I don't want to read it quite yet, I want to make my own today :v:[/QUOTE]

Thanks, I'll be trying PortalsRedux now, but it looks a lot more difficult than this one, so I'm sure it will take a bit longer.

[Deadollie]

The programming forum should have it's own competition, with something that coders of all languages could enter, this could either be through a challenge that can be done with all different sorts of code, or different challenges for different languages.

Just an idea.

[gparent]

[QUOTE=Deadollie;19149673]The programming forum should have it's own competition, with something that coders of all languages could enter, this could either be through a challenge that can be done with all different sorts of code, or different challenges for different languages.

Just an idea.[/QUOTE]

We've done it (Programming challenges), and it worked for a little bit. Wasn't a competition, though.

[Deadollie]

[QUOTE=gparent;19155313]We've done it (Programming challenges), and it worked for a little bit. Wasn't a competition, though.[/QUOTE]

You should do some more :smug:

[phazmatis]

Judging by the amount of people who are doing programming challenges in this thread, why not bring it back?

[nullsquared]

Because it sucked.

Nothing like the real competitions out there.

[NukePower]

Let's do unique solutions to Project Euler problems. One liners, obscure code, etc. Sound like fun? I have some funny haskell code solutions I did.

[nullsquared]

[QUOTE=NukePower;19175333]Let's do unique solutions to Project Euler problems. One liners, obscure code, etc. Sound like fun? I have some funny haskell code solutions I did.[/QUOTE]

No point, the best solutions are already on the discussion threads available when you solve a problem. The J coders there will beat any one liner of obscure code anyone on here can come up with :v: