Programming challenges

Sit back, relax, and enjoy some forum-based games.
User avatar
Jplus
Posts: 6
Joined: Sun Sep 18, 2022 10:58 pm

Re: Programming challenges

Post by Jplus »

somitomi wrote: Fri Mar 03, 2023 6:25 pm 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?
phillip1882 wrote: Fri Mar 03, 2023 6:46 pm 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.
commodorejohn wrote: Fri Mar 03, 2023 7:07 pm "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.
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by phillip1882 »

i have a maze generation and solver in mind, so either is fine by me.
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by 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.
Last edited by phillip1882 on Sat Mar 04, 2023 5:15 pm, edited 1 time in total.
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by phillip1882 »

mazes should be able to be 25x25 to 100x100
deadline is july 30th
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
Jplus
Posts: 6
Joined: Sun Sep 18, 2022 10:58 pm

Re: Programming challenges

Post by 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]]
Last edited by Jplus on Sat Mar 04, 2023 6:27 pm, edited 1 time in total.
User avatar
Jplus
Posts: 6
Joined: Sun Sep 18, 2022 10:58 pm

Re: Programming challenges

Post by 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++.
User avatar
Jplus
Posts: 6
Joined: Sun Sep 18, 2022 10:58 pm

Re: Programming challenges

Post by 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?
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by 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.
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by 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?
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
Jplus
Posts: 6
Joined: Sun Sep 18, 2022 10:58 pm

Re: Programming challenges

Post by Jplus »

phillip1882 wrote: Sat Mar 04, 2023 7:05 pm 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?
phillip1882 wrote: Sat Mar 04, 2023 7:15 pm
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!
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by 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.
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by phillip1882 »

you still haven't posted the evaluation of my sorts! :-)
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
Jplus
Posts: 6
Joined: Sun Sep 18, 2022 10:58 pm

Re: Programming challenges

Post by 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.
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by phillip1882 »

so how many are interested in this? i dont want to go through the trouble of writing the code for only 1 participant
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by phillip1882 »

i hate to say it, but i think this contest is bunk. no one is participating it seems. other than myself and jplus.
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
Jplus
Posts: 6
Joined: Sun Sep 18, 2022 10:58 pm

Re: Programming challenges

Post by 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.
User avatar
phillip1882
Posts: 4
Joined: Sat Jan 29, 2022 10:54 pm

Re: Programming challenges

Post by phillip1882 »

just wanted to revive this one more time, hope to get more interest.
lover of chess, baduk, and civ 4.
capable of eating sin, removing negative energy, and healing while sleeping.
User avatar
Jplus
Posts: 6
Joined: Sun Sep 18, 2022 10:58 pm

Re: Programming challenges

Post by Jplus »

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