#🔒 Help with path finding for a coding problem

13 messages · Page 1 of 1 (latest)

silk meteor
#

I'm currently doing some programming exercises on my free time that are provided by adventofcode.com, I'm currently on day 17 there. To the problem at hand:

I have 2d map of integers ranging from [1-9] representing a cost of traveling through that slot, for example:

1234
2345
1831

The task is to find the least costly path, the problem is that there is a limitation on how you are allowed to move; you can only move straight forward 3 blocks.

I really don't want to be spoon-fed a solution to this, but, does anyone have a recommendation on path finding algorithms that finds this path in a fast way?

dense oysterBOT
#

@silk meteor

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
left sentinel
#

(well, actually only 75s total for both parts, it seems)

silk meteor
#

Okay, I will look that up!

left sentinel
#

The main idea for such tasks is to figure out what will be the space of all possible states that you'll be doing BFS on. In this case, just the current position won't be enough - it also matters ||what direction you're currently travelling in||, and ||how many tiles consequtive tiles you've travelled that way||.

silk meteor
#

Okay, I think I have an algorithm in mind now, thanks for the advice. (I was trying something similar to the A* Pathfinding Algorithm, but I think the amount of possible paths became too long or something, or I messed up somewhere, because it's taking ages to compute)

left sentinel
#

A* will probably work faster than a BFS, yeah

silk meteor
#

Hmm, then I'm just messing up somewhere...

silk meteor
#

I will close this for now, thanks for the hints!

!close

#

!close

dense oysterBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.