5

This is a basic college puzzle question i have which i though i will nail, but when it comes to implementing it i got stuck right on the get go.

Background: a 4 digit path finding algorithm, so given for example a target number 1001 and target number 1040, find path using BFs,DFs...Etc.

Allowed moves: add or subtract 1 from any of the 4 digits in any order, you cannot add to 9, or subtract from 0. You cannot add or subtract from the same digit twice i.e. to get from 1000 to 3000, you cannot do 2000 ->3000 as you’ll be adding 1 twice to the first digit. So you'll have to do 2000->2100->3100->3000.

Where I am Stuck: I just cannot figure out how i will represent the problem programmatically, never mind the algorithms, but how i will represent 1001 and move towards 1004 .What data structure? How will I identify the neighbours?

Can someone please push me towards the right direction?

Improve this question

5 Answers 5

Reset to default
2

If I understand correctly, you're looking for a way to represent your problem. Perhaps you're having difficulties to find it, because the problem uses a 4 digit number. Try to reduce the dimensions, and consider the same problem with 2 digits numbers (see also this other answer). Suppose you want to move from 10 to 30 using the problem's rules. Now that you have two dimensions, you may easily represent your problem on a 10x10 matrix (each digit can have 10 different values):

matrix representation of the two dimensional problem:

In the picture above S is your source position (10), and T is your target position (30). Now you can apply the rules of the problem. I don't know what you want to find: how many paths? just a path? the shortest path?

Anyway, a sketch of algorithm for handling moves is:

  • if you look at T you see that according to the rules of your problem, the only possible neighbours from which you can reach (30) are (20), (31), and (40).

  • now, let's assume you choose (20), then the only possible neighbour from which you can reach (20) is (21).

  • now, you're forced to choose (21), and the only possible neighbours from which you can reach (21) are (11) and (31).

  • finally, if you choose (11), then the only possible neighbours from which you can reach (11) are (10) and (12) ... and (10) is your source S, so you're done.

This is just a sketch for the algorithm (it doesn't say anything on how to choose from the list of possible neighbours), but I hope it gives you an idea.

Finally, when you've solved the problem in the two-dimensional space, you can extend it to a three-dimensional space, and to a four-dimensional space (your original problem), where you have a 10x10x10x10 matrix. Each dimension has always 10 slots/positions.

I hope this helps.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

I would start with a directed graph where each node represents your number plus an additional degree of freedom (because of the constraint). E.g. you can think of this as another digit added to your number which represents the "digit changed last". E.g. you start with 1001[0] and this node connects to

1001[0] -> 2001[1]
1001[0] -> 0001[1]
1001[0] -> 1101[2]
1001[0] -> 1011[3]
1001[0] -> 1002[4]
1001[0] -> 0000[4]

or 2001[1] to

2001[1] -> 2101[2]
2001[1] -> 2011[3]
2001[1] -> 2002[4]
2001[1] -> 2000[4]

Please note: the ????[0] nodes are only allowed as starting nodes. And each edge always connects numbers with different last digit.

So for each number xyzw[d] the outgoing edges are given by

xyzw[d] -> (x+1)yzw[1]   if x<9 && d!=1
xyzw[d] -> (x-1)yzw[1]   if x>0 && d!=1
xyzw[d] -> x(y+1)zw[2]   if y<9 && d!=2
xyzw[d] -> x(y-1)zw[2]   if y>0 && d!=2
xyzw[d] -> xy(z+1)w[3]   if z<9 && d!=3
xyzw[d] -> xy(z-1)w[3]   if z>0 && d!=3
xyzw[d] -> xyz(w+1)[4]   if w<9 && d!=4
xyzw[d] -> xyz(w-1)[4]   if w>0 && d!=4

Your targets are now the four nodes 1004[1] .. 1004[4]. If your algorithm requires a single target node you may add an artificial edge ????[?] -> ????[0] for each number and then have 1004[0] as final.

Improve this answer

10 Comments

@Howard I found this incredibly useful, thank you. The last part you mention "If you algorithm requires a single target you may add an artificial edge.....". I don't quit understand this part. Also in terms of containers would it be beneficial to use something like a linkedlist or should i stick to a 4 dimensional array.
Ok ignore the last comment, Reading it carefully i got what you mean by the artificial edge.
I'm not confident that i know what I'm doing with implementing of the above detail. So if i have 1000 and target is 3000. Firstly i would have 4 possible nodes of 2000,1100,1010,1001 as edges to 1000. Then given 3000 is not in there same has to be done for each of the edges. so for 2000 i would have 3000,2100,2010,2001. Do i stop here and not worry about filling the edges of 1100,1010,1001 or should i fill the graph completely? Note at this stage I am not implementing the algorithms but just getting the data ready to be traversed based on different algorithm. I'm lost in translation :(
@keren you have to build the complete graph. Beforehand you do not know if there is a path from 2000 to 3000 and thus you have to take all edges into account. Regarding your last comment: in this case you can simply put everyting into an one-dimensional array [00000] to [99994] (using my notation of above with an additional digit). Each element represents a node and the edges you do not have to persist at all since they can easily be calculated on the fly (see the eight lines in my answer).
Hrm i find myself starring at the screen hoping i'll see what you are seeing @howard. Now i have the visualization in my head right and what's required. But in terms of Directed Graph, if i understand correctly , if i have a start 1000 and target 3000 Then i have 4 possible children 2000,1100,1010,1001, I don't know how to represent the children. IF i use a graph i can only have two children under any one node !
|
1

The first thing that came to my mind is that this is just a point with extra dimensions. That is, rather than [x,y] to represent a point on a 2-D grid, you have [w,x,y,z] to represent a point in a 4-D space.

The one thing I'm not sure in your problem is what happens when you add a 1 to a 9. Is there a remainder that get's carried over, or does the number just get rolled over to zero? Or does this represent an edge that can't be crossed?

In any case, I'd start with thinking of this as a type of point with extra dimensionality, and apply your algorithms appropriately.

Improve this answer

1 Comment

No you cannot add to 9 or subtract from 0 , nor can you add twice to a digit in two moves.
1

You can represent each state as an integer array of length 4. Then have a graph structure to connect the states (I would not advice on building the graph fully, as this alone will require O(10^4) memory).

Then use A* algorithm for traversing the graph and reaching the destination node.

Or simply use a BFS traversal routine where you generate the neighbouring states as you process a state. You'll have to keep a track of the states already visited (some sort of a set like data structure).

Improve this answer

Comments

0

When visit a node you need to iterate through all children of the node and visit some of them, so you should only implement children generator function getting one parameter - current number like 1001. It's the "core" of the algorithm, then you need to use recoursion to traverse a tree. The following is code that DOES NOT WORK and goes into infinite recoursion, but is a sketch explaining my idea:

from random import random

def shouldVisit(digits):
    #very smart function defining search strategy
    return random() > 0.5

def traverse(source, target, prev):
    if source == target:
        print 'wow!'
        return
    for i in range(len(source)):
        if i == prev:
            continue
        d = source[i]
        if d > 0:
            res = list(source)
            res[i] = d - 1
            if shouldVisit(res):
                traverse(res, target, i)
        if d < 9:
            res = list(source)
            res[i] = d + 1
            if shouldVisit(res):
                traverse(res, target, i)

def traverse0(source, target):
    def tolist(num):
        digits = []
        while num:
            digits.append(num % 10)
            num /= 10
        return digits
    traverse(tolist(source), tolist(target), -1)

traverse0(1001, 1040)

very smart stub function shouldVisit may check for example if given node has been already visited

Improve this answer

1 Comment

so if i have 4 dimensional array, say with a given digit [1][0][0][1] and target is [2][0][0][0] i need to populate all the possible neighbors between 1001 and 2000 to be able to implement say for example the BFS algorithm. what approach do i take in building the population. In other words in my head i'm thinking i need to build a graph with all the possible moves given and starting and ending point but i don't know how. can you please be little more detailed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.