All possible permutations and related data OR other solutions

[leorob88]

I would make a program to calculate a sequence, taken from a game i played.
Basically you have a sequence of numbers, it is like a clock really, meaning they're disposed in a circle. These numbers are 1 digits only, from 1 to a max of 6, but there can be duplicates of numbers along the circle, meaning the sequence can be for example 2, 2, 3, 2, 2 (starting from top/north position and following the circumference clockwise).
The purpose of this kind of game is "selecting" ALL the numbers in the sequence but selecting them all just ONCE. You can choose where to start from. When you select a number, you can choose next only the two other numbers distancing by the number you selected. By two numbers I mean you can choose distancing forward or backwards. For examples, you select a 3, you can next select only the two numbers which have a distance of 3 from the 3. So, in the example case, the selectable values would both be 2, but in different positions. If per chance one of the two positions is unselectable, since you already selected it earlier, you cannot select it again, you can only select the others. If both are unavailable, you lose (as you indeed failed to create a sequence of selecting all numbers not selecting the same multiple times).
In the example case that I could sample like this:
2
2
3
2
2
the solution could be this (there is more than one solution in this example but this is one possible solution)
2 1st select
2 4th select
3 2nd select
2 5th select
2 3rd select
As you see, after the 3 you move backwards and so you choose the last in the list as 3rd selection. Then you move forward again restarting from the top of the list.
So, my goal would be to create a program which calculates a possible solution for this game, given a starting sequence of values. Only, the list of values can be up to 13 values. I thought also about calculating permutations but it would be 13 factorial... Once the solution is found, i need to write (messagebox, textbox, label, whatever you want) the sequence of the numbers selected and the positions in the original list (as there can be duplicate values so I need to know exactly what position that number is). How would you advice to handle this thing?

 

[Skydiver]

What's wrong with just a basic depth first tree search?

 

[leorob88]

What's wrong with just a basic depth first tree search?

Basically that I don't know what you are talking about, sorry. But I'm curious to learn!

 

[Skydiver]

See:

Depth-first search - Wikipedia

en.m.wikipedia.org

Depth-First Search (DFS)

Understand Depth-First Search (DFS) with key concepts, pseudocode, and Python examples. Explore its applications in pathfinding and puzzle-solving.

celerdata.com

 

[leorob88]

See:

Depth-first search - Wikipedia

en.m.wikipedia.org

Depth-First Search (DFS)

Understand Depth-First Search (DFS) with key concepts, pseudocode, and Python examples. Explore its applications in pathfinding and puzzle-solving.

celerdata.com

lol at first you made it sound like it should be obvious! So, I tried reading. The general concept on wikipedia i kinda get. Only I don't understand properly the code and how to apply it, even more because my case is some sort of ring/circle structure and not a tree graph, so I don't really understand how to apply this difference too. In the second one there is not even a line of code so I found it more of a conceptual explanation. The third link actually shows more comprehensible code, kinda, and the recursive code seems more useful than the iterative, only i don't know Python and

def dfs_recursive(graph, node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

visited = set()
dfs_recursive(graph, 'A', visited)

Is set() supposed to be like an Array or List? Also, in the case of this code example each node in graph has assigned related data (like, A -> B, C). For the purpose of my program, I suppose these 2 should be the numbers you can select next, when you select a number? I have this doubt just because I see in this example D and F have no related nodes.

 

[leorob88]

Also, I tried to assume it's like that and i tried it in C# but it doesn't actually work. Meaning, there's an issue. What my program should do is "if you can't progress any further, restart and try a different path" but what it does instead is "if you can't progress, go backwards to unexplored other branches and write down those remaining as well". I tried to check the iterative method but actually since I don't know Python and I see there are no variables types I have a doubt.

stack : [start]

This calls the parameter..... but what is [start] supposed to be? In theory, it is a string but maybe it is handling it as a string array...? I don't understand... So, briefly, to at least understand what this code actually does, it would be nice to have it translated to C#...

 

[Skydiver]

You have a fun little problem, and I'm trying not to just spoonfeed you the answer because you seem to enjoy learning, and I don't want to deprive you of the joy of that "A-ha!" moment.

Perhaps this might help a bit more since it a little more visual. Sorry, it's Python again, but the concepts should be a lot clearer.

Morse Code using a Binary Tree - 101 Computing

The Morse Code was designed to quickly transfer messages using a series of "dots (.)" and "dashes (-)". Morse code was named after Samuel Morse, one of the inventors of the telegraph. The International Morse Code includes the 26 letters of the alphabet (there is no distinction between lowercase...

www.101computing.net

As for the circular array that you have: the modulus operator % is your friend. Let's you you have an array of length 5, and you are currentyl at index 4:

2 2 3 2 2 -- value
        ^
0 1 2 3 4 -- index

So given the value of 2 in your array, you are can go back 2 or advance by 2. To handle the advance case, if you add do (4 + 2) % 5, you get the result of 1:

2 2 3 2 2 -- value
  ^
0 1 2 3 4 -- index

(Alas, the C# modulus operator trick won't work on the go back case. For that you'll need to do bounds check.)

 

[leorob88]

You have a fun little problem, and I'm trying not to just spoonfeed you the answer because you seem to enjoy learning, and I don't want to deprive you of the joy of that "A-ha!" moment.

Perhaps this might help a bit more since it a little more visual. Sorry, it's Python again, but the concepts should be a lot clearer.

Morse Code using a Binary Tree - 101 Computing

The Morse Code was designed to quickly transfer messages using a series of "dots (.)" and "dashes (-)". Morse code was named after Samuel Morse, one of the inventors of the telegraph. The International Morse Code includes the 26 letters of the alphabet (there is no distinction between lowercase...

www.101computing.net

As for the circular array that you have: the modulus operator % is your friend. Let's you you have an array of length 5, and you are currentyl at index 4:

2 2 3 2 2 -- value
        ^
0 1 2 3 4 -- index

So given the value of 2 in your array, you are can go back 2 or advance by 2. To handle the advance case, if you add do (4 + 2) % 5, you get the result of 1:

2 2 3 2 2 -- value
  ^
0 1 2 3 4 -- index

(Alas, the C# modulus operator trick won't work on the go back case. For that you'll need to do bounds check.)

Well actually my priority would be a working code, making my own idea is not a priority, I can just be fine with a working code and understanding how it works by just reading it. I mean, I want to do this thing but it doesn't have to be "my conceptual idea that I made up by my notions", it can be just something someone else did and I just use for my personal use, understanding and learning are not the priority to me. The priority is to realize something that works and doesn't take a day to understand the code lol I'll try later to read that page though and see what's there! For now I realized a first step. Meaning, when I solve these puzzles I go with trial and error but first I found out a useful method. By knowing how many points can lead to a specific point, I can cut down some waste of time. For example, if one point is unreachable from any other point of the ring, it means that one is the starting point. If one is reachable from only 1 point, it is most probably a connection you're going to do somewhere half way. Not always though, for example I had one with 12 points. 2 of these were reachable by only 1 point and it was the same one. Fact was one of the 2 was the starting point, the other instead was reached during the sequence. So, I made a function to calculate from how many points every point in the ring is reachable. That can give me a lead on which one/s can be the starting point or where there are forced selections.

 

[leorob88]

Before wasting 20 minutes with a video, I must say/ask this..... I don't think a morse translator has much to do with my purpose...? Or at least I don't see how they can be completely related. Morse is more defining/searching which letter/symbol corresponds. My case could relate to morse in two ways: one is we already know a letter and so we must search for the path leading to that letter but that has little to do with what I need to do, the other way is we already know which number we want to reach and we search for the number leading to that one, but that's not my problem at all, since I don't need to reach a number, I need to define a sequence leading to ALL numbers. In a morse perspective, we can sample this as: we know there's a phrase made of a defined number of letters, we have to reach all those letters to form a consistent phrase and not just random nonsense text. That's quite a different matter than a morse translator.
Also, I asked something in the previous comment. I don't understand if you didn't reply because you don't know Python or because you forgot...