Programming challenges

[Jplus]

I couldn't be bothered to put a sorting algorithm together for the first round, I'm not sure you could make it quicker without losing the... challenge aspect of the challenge.

I was thinking along lines of (for example):

• a challenge for which a single line of code would suffice (that is still challenging to come up with);
• a challenge for which a (poor) solution is already given, so you only need to edit an existing program instead of writing a new one.

At the most extreme, there might be a way to organize a challenge such that you can reply directly in a PM or even publicly in the thread, without ever opening an editor or running a compiler/interpreter. Would that lower the barrier enough?

i'm not quite sure how you would evaluate a maze generation algorithm, what you would give badges for. maybe number of dead ends?

Or maybe the host writes a maze solving program, and the solution that generates the hardest mazes for that program (that are still possible) wins? Or the total length of, or number of bends in, the shortest path?

That said, if I were to host a maze challenge, I would probably be more inclined to have the participants write maze solvers. I was thinking to maybe include increasingy difficult dynamic elements in the mazes and let the solution win that reached the highest "level". Not quite sure how to shoehorn such a challenge in a low-barrier format, though.

"I am easy" (colloq. "I don't care.") Coulda been clearer.

Ah, thanks for that new nugget of knowledge! As you may have guessed, I'm not a native speaker of English.

[phillip1882]

i have a maze generation and solver in mind, so either is fine by me.

[phillip1882]

so, i'll write a maze generator and solver. your task is to write a solver and/or generator.
i'll give a badge for the fastest time to solve my maze, and a badge that maze takes the longest time for me to solve.
the maze will be in a format of a dictionary where every cell connected to every open adjacent cell is listed.

Code: Select all

  ___ ____
6| |_____ |
5| | _____|
4| |___ | |
3| _____| |
2| |  ___ |
1|___| ___|
  12345678

{[1,1]:[1,2,2,1], [2,1]:[1,1,3,1], [3,1]:[2,1,3,2],
[5:1]:[5,0,6,1], [6,1]:[5,1,7,1], [7,1]:[6,1,8,1],
[8,1]:[7,1,8,2], [1,2]:[1,1,1,3], [3,2]:[3,1,4,2],
[4,2]:[3,2,5,2], [5,2]:[4,2,6,2], [7,2]:[6,2,8,2],
[8,2]:[8,1,8,3,7,2], [1,3]:[1,2,1,4,2,3], [2,3]:[1,3,3,3],
[3,3]:[2,3,4,3], [4,3]:[3,3,5,3], [6,3]:[5,3,6,4],
[8,3]:[8,4,8,2], [1,4]:[1,5,1,3], [3,4]:[3,5,4,4],
[4,4]:[3,4,5,4], [6,4]:[6,3,5,4], [8,4]:[8,3],
[1,5]:[1,6,1,4], [3,5]:[3,4,4,5], [4,5]:[3,5,5,5],
[5,5]:[4,5,6,5], [6,5]:[5,5,7,5], [7,5]:[8,5,6,5],
[8,5]:[8,6,7,5], [1,6]:[1,5], [3,6]:[4,6],
[4,6]:[4,7,3,6,5,6], [5,6]:[4,6,6,6], [6,6]:[5,6,7,6],
[7,6]:[6,6,8,6], [8,6]:[7,6,8,5]}

note that walls shouldn't take up a cell, this is just demonstration.

[phillip1882]

mazes should be able to be 25x25 to 100x100
deadline is july 30th

[Jplus]

So if I understand correctly, the walls are "infinitely thin". And there should be an entrance and an exit, which I guess must be connected. Is there any rule about where the entrance and the exit should be? Also, did you mean that mazes must/cannot be smaller than 25x25?

I don't understand how the dictionary format works, could you explain it?

You can also represent a maze with a two-dimensional array. Suppose I have this 2x2 maze, with each cell being between four grid points and the grid points represented by the + signs:

Code: Select all

+-+-+
|   |
+ + +
| |  
+ +-+

Then I could use the coordinates of the grid points as indices into a two-dimensional array. In each element, I store 0 if there is a wall neither right of the grid point nor below it, 1 if there is only a wall right of it, 2 if there is only a wall below it, or 3 if there are walls right of it and below it. That would look like this for my extremely simple 2x2 maze:

Code: Select all

[[3, 1, 2],
[2, 2, 0],
[0, 1, 0]]

[Jplus]

By the way, how will you determine which solver is fastest? A very efficient program in Python might be slower than a very inefficient program in C++.

[Jplus]

Sorry, another question. Is the solver looking at the maze from a birds-eye perspective and computing a path, or is it an agent that walks through the maze and that can only see whether there are walls directly around it? In the first case, should it be the shortest path? In the second case, can the solver still use knowledge of where the exit is relative to the entrance?

Also, should solvers output anything in order to prove that they found a valid solution?

[phillip1882]

So if I understand correctly, the walls are "infinitely thin". And there should be an entrance and an exit, which I guess must be connected. Is there any rule about where the entrance and the exit should be? Also, did you mean that mazes must/cannot be smaller than 25x25?

yes walls are "thin", yes, entrance at the bottom, exit it the top. the solver can also go from top to bottom. yes not smaller than 25x25.

I don't understand how the dictionary format works, could you explain it?

so to the left of the : symbol is coordinate of the cell horizontal first the vertical. to the right are all cells that are adjacent and connected.

Sorry, another question. Is the solver looking at the maze from a birds-eye perspective and computing a path, or is it an agent that walks through the maze and that can only see whether there are walls directly around it?

the solver sees the whole dictionary at every point.

In the first case, should it be the shortest path? In the second case, can the solver still use knowledge of where the exit is relative to the entrance?

it doesn't have to be the shortest path, just a valid one. but there is only 1 path from the entrance to the exit. the solver should give me the list of cells traversed to get from entrance to exit.

[phillip1882]

By the way, how will you determine which solver is fastest? A very efficient program in Python might be slower than a very inefficient program in C++.

hmm good question. i was thinking based on time to solve, but maybe total squares traversed?

[Jplus]

so to the left of the : symbol is coordinate of the cell horizontal first the vertical. to the right are all cells that are adjacent and connected.

Oh, I think I understand. It is [x1, y1, x2, y2, x3, y3]. Two issues, though:

• How do you indicate entrance and exit? Your example dictionary does not encode them in any way. Are they always in the middle of the top and bottom sides? What if the maze has an even width?
• Dictionaries with pairs as keys are difficult to represent in some programming languages. The two-dimensional array notation that I suggested is probably easier to implement.

(...) there is only 1 path from the entrance to the exit. the solver should give me the list of cells traversed to get from entrance to exit.

Ah, so cycles are not allowed?

Are mazes required to be fully connected?

how will you determine which solver is fastest?

(...) maybe total squares traversed?

Yes, that seems like it might be a good way to determine the efficiency of a solver!

[phillip1882]

How do you indicate entrance and exit? Your example dictionary does not encode them in any way. Are they always in the middle of the top and bottom sides? What if the maze has an even width?

the cell with adjacent cell 0 for start, 7 for end. the horizontal position is random.

Dictionaries with pairs as keys are difficult to represent in some programming languages. The two-dimensional array notation that I suggested is probably easier to implement.

hmm. ok, we'll try yours.

Ah, so cycles are not allowed?

correct.

Are mazes required to be fully connected?

no you can have cells that can never be reached, but why you would want that i don't know. it's legal though.

[phillip1882]

you still haven't posted the evaluation of my sorts!

[Jplus]

I have!

Edit to add: I updated the results and I meant to mention that in a new post, but it seems I forgot.

[phillip1882]

so how many are interested in this? i dont want to go through the trouble of writing the code for only 1 participant

[phillip1882]

i hate to say it, but i think this contest is bunk. no one is participating it seems. other than myself and jplus.

[Jplus]

commodorejohn said he was interested. Let's allow others the time to collect the courage to open this thread again and make up their minds. There is still a lot of time until the deadline.

[phillip1882]

just wanted to revive this one more time, hope to get more interest.

[Jplus]

I'm still interested. I sent a PM to commodorejohn and added round 3 to the opening post, which apparently I forgot before.