chatGPT Grades Ripero's Pet Detective Solver (Hint: It Needs Work😊)


This would be a nice one to solve. There's nothing online that lets you submit a picture of the puzzle and get the steps you need to take.

Now, see what Ripero says:

Just run the binary from the directory that contains the five files described above.

$ ls
car.dat  lengths.dat  missing_links.dat  missing_points.dat  pets.dat
$ ../src/pd
 1--- 2--- 3--- 4
 |    |         |
 5--- 6--- 7--- 8
 |    |    |     
 9---10   11---12
 |    |         |
13---14---15---16
 |    |    |    |
17   18---19---20
 |    |         |
21   22---23---24
Computing distances between nodes...... done
Number of calls to DFS: 54655
SOLUTION FOUND:
14  15  16  24  23  22  13  17  9  10  18  19  20  11  7  6  5  1  2  4  3

The output starts with a sketch of the grid, with all its nodes and existing links. Each node is given a number. If a solution is found, the sequence of nodes that forms the solution will be provided in the last line.

Isn't that sweet. But, if you've ever approached such a problem, you know that the algorithm needs to scale. Else, you could wait years!

So, I asked the oracle:

Are you good with Fortran? Can you explain what this program does?

Yes, I'm comfortable with Fortran, and this is a pretty interesting program! Let me give you a breakdown of what it does:

🧠 Purpose of the Program (pd)

This program simulates and solves a delivery routing problem on a 2D grid (lattice), where a car needs to:

  1. Pick up pets from given positions,

  2. Deliver them to their corresponding homes,

  3. Respect a distance constraint (the car can't travel more than a specified number of steps),

  4. Only carry up to 4 pets at a time.

It's essentially a constrained depth-first search (DFS) pathfinding algorithm for logistics on a lattice-like graph.

...

Notes

  • This is a nice example of a grid-based search with physical constraints.

  • Could be used in simulations of robot delivery, game AI, or resource logistics.

  • DFS is exhaustive, so performance might degrade with large grids or more pets.

And then:

Is the approach computationally efficient?

Great question — and very relevant given that this program uses a recursive depth-first search (DFS) for a combinatorial routing problem.

🚨 TL;DR:

The approach is not computationally efficient for large input sizes — it’s exponential in complexity due to DFS trying all possible sequences of pickups and deliveries. It’s fine for small cases (e.g. 2–4 pets), but will struggle as the problem scales.

--------

What's the holy grail? User hits a keyboard shortcut, AHK script takes over - detects if the browser has lumosity, pet detective, is maximized, maximizes it if necessary, takes a snip of the screen, passes it through the solver, takes the solution and implements it with simulated mouse-clicks. Dig?

Who is Duane Loren Mattern?

Duane Loren Mattern is an Embedded Systems Engineer works at Sampled Systems who currently resides in Westlake, Ohio. Duane is 67 years old and was born in June 1957. Duane attended Purdue University. Duane went on to The Ohio State University. Beyond the current title, Duane's employment history includes the following: an embedded systems engineer at Sampled Systems, Llc, and an embedded systems engineer at Crosspoint Solutions, Llc.

Comments

Post a Comment