Jump to content
Vorticon

Programming Challenge Competition

Recommended Posts

Posted (edited)

I was watching the other day some YouTube videos about tiny robotic "mice" learning how to navigate a maze and coming up with an optimized path, and I thought it would be fun to recreate that competition virtually on the TI. Challengers will provide me with a program meeting the specifications outlined below and I will merge it with a custom program which will generate a maze on the screen. The idea is to have 2 runs at a maze, the first one being a discovery run and the second an optimized path run.

 

So here are the rules:

  • TI BASIC only. DSK1 access allowed for data storage and retrieval. No support cartridges of any kind.
  • Program must start at line 100
  • Entry to the maze will be at screen position X=16 and Y=23 and the first open position will start at X=16 and Y=22
  • The walls of the maze will be represented by ASCII character 42 [*]
  • Empty spaces in the maze will be represented by ASCII character 32 [space]
  • After each mouse move, you must
    • Place ASCII character 35 [#] at its current position
    • Update the variable MX with your current X position
    • Update the variable MY with your current Y position
    • Perform a GOSUB 10000. I will provide the contents of that subroutine which will check if the move is valid, track the number of steps taken and verify if the mouse has exited the maze. A step is defined as ANY mouse movement of 1 space. The maximum number of steps allowed is 350. 
    • Upon return from subroutine 10000, you MUST read MX and MY and use these values as the CURRENT mouse coordinates
    • Upon return from the subroutine at 10000, check if the variable ME has changed status from zero. If ME = 1 (end of the first run), perform a GOSUB 15000. If ME = 2 (end of the second run), perform a GOSUB 20000. If ME = 0, resume your mouse activities.
    • Please remember: DO NOT provide content for the subroutines at 10000 and 15000 or 20000. Just execute a simple GOSUB.
  • Only the number of steps needed to exit the maze on the SECOND RUN will count. 
  • Obviously the main challenge here is to come up with an optimized path the second time around based on your discovery path on the first run. 
  • The winner will be the programmer who manages the smallest number of steps on the second run. The same maze will be used for all entries.

 

Important: no prescanning of the maze will be allowed in the code. The mouse will have "visual" access to only the 4 squares surrounding it.

 

Below is a flow chart of the program process. Any boxes in orange are code provided by me, whereas the blue ones are your own code.

 

914695832_MouseChallenge.thumb.png.8797fb187eaa79b3e83b56ab33a24749.png

 

 

*** The prize will be a brand new Logitech G300s gaming mouse (no pun intended 😁) ***

20210704_203704.thumb.jpg.6123d8028ae1e575c7a96820cfa9bb82.jpg

The contest will run from July 17, 2021 at 00:00 GMT and will end on August 4, 2021 00:00 GMT. The winner will be announced on Sunday August 8, 2021 along with a reveal of the competition maze and a video of the winner's run.

Please do NOT post your entries here. PM me your entries instead in order to avoid code "cross-pollination". You may submit as many entries as you like, but only one entry per participant will be considered (your choice).

GOOD LUCK!

Edited by Vorticon
  • Like 3

Share this post


Link to post
Share on other sites

If MX and MY represent an invalid location, how does the caller know? What is the feedback contract?

Share this post


Link to post
Share on other sites
Posted (edited)
11 minutes ago, jedimatt42 said:

If MX and MY represent an invalid location, how does the caller know? What is the feedback contract?

The subroutine at 10000 will use these values to check positional validity against the maze layout and exit condition. However, the programmer should use a CALL GCHAR to check for walls ahead of any movement regardless. The mouse will be disqualified if it performs an invalid move.

Edited by Vorticon

Share this post


Link to post
Share on other sites
Posted (edited)

Spoiler here...  Does the maze have any restrictions?  Aka - only one exit path, no loops, etc?  If so, it seems like 2nd run is just a simple stack from the first run and everyone should have similar answers... 

Edited by unhuman

Share this post


Link to post
Share on other sites
6 hours ago, Vorticon said:

 A maximum of 200 steps will be allowed before disqualification. 

 

So in the first run through, only 200 steps are allowed? That may not be enough - how complex will the maze be?

You might offer a silver medal for the most compact program that can complete the maze.

Share this post


Link to post
Share on other sites
6 hours ago, unhuman said:

Spoiler here...  Does the maze have any restrictions?  Aka - only one exit path, no loops, etc?  If so, it seems like 2nd run is just a simple stack from the first run and everyone should have similar answers... 

There will be one exit somewhere. Loops are possible.

Can you elaborate on what you mean by simple stack?

Share this post


Link to post
Share on other sites
3 hours ago, senior_falcon said:

So in the first run through, only 200 steps are allowed? That may not be enough - how complex will the maze be?

You might offer a silver medal for the most compact program that can complete the maze.

The maze will be limited by the screen real estate and character resolution, so I would think 200 steps should be sufficient. Compactness can be rather subjective though 😊

Share this post


Link to post
Share on other sites
Posted (edited)
11 hours ago, Vorticon said:

There will be one exit somewhere. Loops are possible.

Can you elaborate on what you mean by simple stack?

If loops are possible, then a stack won't work...  :)  Definitely makes it more interesting.

 

Stack will work...  Just gotta be careful with it.  This could be fun.

Edited by unhuman

Share this post


Link to post
Share on other sites

Sounds mice ... I mean nice. I would prefer XB though.

 

When do you provide the two subroutines and a test-maze for training? I might play around and see where it gets me ... 

 

I wonder if 200 steps are always sufficient if you don't know where to look for the exit. There are 768 character positions on the sceen. Assuming there is a solid wall around your maze there are 660 positions left.

Share this post


Link to post
Share on other sites
44 minutes ago, SteveB said:

Sounds mice ... I mean nice. I would prefer XB though.

 

When do you provide the two subroutines and a test-maze for training? I might play around and see where it gets me ... 

 

I wonder if 200 steps are always sufficient if you don't know where to look for the exit. There are 768 character positions on the sceen. Assuming there is a solid wall around your maze there are 660 positions left.

Yes but as much as half, and possibly more, might be taken up by internal walls. But you might be right and perhaps 350 steps may be more achievable. 

I will not provide the subroutines or a test maze ahead of time. The subroutines only perform routine housekeeping though and do not contribute to the challenge and it will be up to you to create your own testing environment 🙂

Share this post


Link to post
Share on other sites
17 hours ago, unhuman said:

If loops are possible, then a stack won't work...  :)  Definitely makes it more interesting.

 

Stack will work...  Just gotta be careful with it.  This could be fun.

Go for it 🙂

  • Like 1

Share this post


Link to post
Share on other sites

I went ahead and changed the max number of steps to 350.

I'll open up a poll to see how many programmers, if any, are interested in this. 

Share this post


Link to post
Share on other sites

Will the openings in the maze be only 1 char wide?  I guess it doesn't fundamentally matter, but it could make for a lot of excessive processing.

Share this post


Link to post
Share on other sites

The more I think about it, it gets a little bit tricky.  Looks like you can only exit once in round 1...  With loops possible, seems like there could be luck in finding the optimal path with no chance to find alternate...  Huh.

Share this post


Link to post
Share on other sites
7 hours ago, unhuman said:

Will the openings in the maze be only 1 char wide?  I guess it doesn't fundamentally matter, but it could make for a lot of excessive processing.

Yes, which is the width of the paths.

Share this post


Link to post
Share on other sites

To make sure I don't miss this... Once you find the exit of the maze, you're done, right?  Can't continue to find other paths other than what you know?

Is the exit known to be on the edge or could it be anywhere?

Share this post


Link to post
Share on other sites
11 hours ago, unhuman said:

To make sure I don't miss this... Once you find the exit of the maze, you're done, right?  Can't continue to find other paths other than what you know?

Is the exit known to be on the edge or could it be anywhere?

Yes. And the exit is on one of the edges. 

Unfortunately, it does not look like there is ravenous interest in this so far...

Share this post


Link to post
Share on other sites

I am mildly interested. I suspect this could be done in just a few lines. Of course, in TI BASIC there would have to be some extra lines. Still, I would be surprised if it took more than 20 lines.

Share this post


Link to post
Share on other sites
1 hour ago, senior_falcon said:

I am mildly interested. I suspect this could be done in just a few lines. Of course, in TI BASIC there would have to be some extra lines. Still, I would be surprised if it took more than 20 lines.

I'm thinking it's probably more than that, but I haven't programmed anything in TI in a while...  But...  I'm just kind of thinking the exit detection is actually going to make it more a game of chance than deterministic...

Share this post


Link to post
Share on other sites
Posted (edited)
1 hour ago, unhuman said:

I'm thinking it's probably more than that, but I haven't programmed anything in TI in a while...  But...  I'm just kind of thinking the exit detection is actually going to make it more a game of chance than deterministic...

Sounds like a competition!! (edit - for compactness of coding)  I do think it is a game of chance. Whether you start looking up, down, right or left will make a difference.

 

"Only the number of steps needed to exit the maze on the SECOND RUN will count"

 

Programming steps or actual steps of the mouse?

Edited by senior_falcon

Share this post


Link to post
Share on other sites

I'd be interested if the programming language was free to choose, especially since performance does not play a factor in determining the winner.

Share this post


Link to post
Share on other sites
1 hour ago, senior_falcon said:

Sounds like a competition!! (edit - for compactness of coding)  I do think it is a game of chance. Whether you start looking up, down, right or left will make a difference.

 

"Only the number of steps needed to exit the maze on the SECOND RUN will count"

 

Programming steps or actual steps of the mouse?

Mouse steps

Share this post


Link to post
Share on other sites
1 hour ago, TheMole said:

I'd be interested if the programming language was free to choose, especially since performance does not play a factor in determining the winner.

I would have to create a testing program for each language used except XB which would not be practical. Settling on the lowest possible denominator creates a uniform space for all.

Share this post


Link to post
Share on other sites

Those of you interested in competing should state so in the poll. I would say we need at least 4 entries to keep things interesting 🙂

Share this post


Link to post
Share on other sites

Does anything in the rules prevent you from scanning the entire maze before making your move?

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...