How many ways to place n DNA chains

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}

-1

The problem is to find how many complete structures can be formed using the DNA chains. The rule is that the first letter of the new part has to be the same as the last letter of the previous chain.

On the first row you are given an integer: the number of chains. On the next n rows are strings: the chains.

Example:

ACGA

ACAC

CCCC

CTAC

Output:
4

I tried a recursive backtracking solution, but I am sometimes getting wrong answers. I can't seem to figure out what is wrong.

ans = 0

used = {}



def place(howmanyplaced, allowedletter):

    global ans

    if howmanyplaced == num:

        ans += 1

        return ans



    for i in range(0, len(mylist)):

        if mylist[i][0] == allowedletter and used[i] == False:

            allowedletter = mylist[i][-1]

            used[i] = True

            place(howmanyplaced+1, allowedletter)

            used[i] = False





num = int(input())

mylist = 

for l in range(0, num):

    i = input()

    used[l] = False

    mylist.append(i)



for k in range(0, len(mylist)):

    used[k] = True

    place(1, mylist[k][-1])

    used[k] = False  

print(ans)

edited Jan 3 at 12:22

asked Jan 3 at 12:07

Quiti

777

2

Meaning sometimes with the same input? Or with different inputs? If different then provide the input and expected output as well as what you get. Otherwise is the code properly indented since it doesn’t look like it

– Sami Kuhmonen
Jan 3 at 12:11

Same input allowed. I re-intended the code-

– Quiti
Jan 3 at 12:20

Can you use numpy in your application?

– dubbbdan
Jan 3 at 18:51

add a comment |

-1

The problem is to find how many complete structures can be formed using the DNA chains. The rule is that the first letter of the new part has to be the same as the last letter of the previous chain.

On the first row you are given an integer: the number of chains. On the next n rows are strings: the chains.

Example:

ACGA

ACAC

CCCC

CTAC

Output:
4

I tried a recursive backtracking solution, but I am sometimes getting wrong answers. I can't seem to figure out what is wrong.

ans = 0

used = {}



def place(howmanyplaced, allowedletter):

    global ans

    if howmanyplaced == num:

        ans += 1

        return ans



    for i in range(0, len(mylist)):

        if mylist[i][0] == allowedletter and used[i] == False:

            allowedletter = mylist[i][-1]

            used[i] = True

            place(howmanyplaced+1, allowedletter)

            used[i] = False





num = int(input())

mylist = 

for l in range(0, num):

    i = input()

    used[l] = False

    mylist.append(i)



for k in range(0, len(mylist)):

    used[k] = True

    place(1, mylist[k][-1])

    used[k] = False  

print(ans)

edited Jan 3 at 12:22

asked Jan 3 at 12:07

Quiti

777

2

Meaning sometimes with the same input? Or with different inputs? If different then provide the input and expected output as well as what you get. Otherwise is the code properly indented since it doesn’t look like it

– Sami Kuhmonen
Jan 3 at 12:11

Same input allowed. I re-intended the code-

– Quiti
Jan 3 at 12:20

Can you use numpy in your application?

– dubbbdan
Jan 3 at 18:51

add a comment |

-1

The problem is to find how many complete structures can be formed using the DNA chains. The rule is that the first letter of the new part has to be the same as the last letter of the previous chain.

On the first row you are given an integer: the number of chains. On the next n rows are strings: the chains.

Example:

ACGA

ACAC

CCCC

CTAC

Output:
4

I tried a recursive backtracking solution, but I am sometimes getting wrong answers. I can't seem to figure out what is wrong.

ans = 0

used = {}



def place(howmanyplaced, allowedletter):

    global ans

    if howmanyplaced == num:

        ans += 1

        return ans



    for i in range(0, len(mylist)):

        if mylist[i][0] == allowedletter and used[i] == False:

            allowedletter = mylist[i][-1]

            used[i] = True

            place(howmanyplaced+1, allowedletter)

            used[i] = False





num = int(input())

mylist = 

for l in range(0, num):

    i = input()

    used[l] = False

    mylist.append(i)



for k in range(0, len(mylist)):

    used[k] = True

    place(1, mylist[k][-1])

    used[k] = False  

print(ans)

edited Jan 3 at 12:22

asked Jan 3 at 12:07

Quiti

777

The problem is to find how many complete structures can be formed using the DNA chains. The rule is that the first letter of the new part has to be the same as the last letter of the previous chain.

On the first row you are given an integer: the number of chains. On the next n rows are strings: the chains.

Example:

ACGA

ACAC

CCCC

CTAC

Output:
4

I tried a recursive backtracking solution, but I am sometimes getting wrong answers. I can't seem to figure out what is wrong.

ans = 0

used = {}



def place(howmanyplaced, allowedletter):

    global ans

    if howmanyplaced == num:

        ans += 1

        return ans



    for i in range(0, len(mylist)):

        if mylist[i][0] == allowedletter and used[i] == False:

            allowedletter = mylist[i][-1]

            used[i] = True

            place(howmanyplaced+1, allowedletter)

            used[i] = False





num = int(input())

mylist = 

for l in range(0, num):

    i = input()

    used[l] = False

    mylist.append(i)



for k in range(0, len(mylist)):

    used[k] = True

    place(1, mylist[k][-1])

    used[k] = False  

print(ans)

python recursion backtracking

edited Jan 3 at 12:22

asked Jan 3 at 12:07

Quiti

777

edited Jan 3 at 12:22

asked Jan 3 at 12:07

Quiti

777

edited Jan 3 at 12:22

asked Jan 3 at 12:07

Quiti

777

asked Jan 3 at 12:07

Quiti

777

asked Jan 3 at 12:07

Quiti

777

2

Meaning sometimes with the same input? Or with different inputs? If different then provide the input and expected output as well as what you get. Otherwise is the code properly indented since it doesn’t look like it

– Sami Kuhmonen
Jan 3 at 12:11

Same input allowed. I re-intended the code-

– Quiti
Jan 3 at 12:20

Can you use numpy in your application?

– dubbbdan
Jan 3 at 18:51

add a comment |

2

Meaning sometimes with the same input? Or with different inputs? If different then provide the input and expected output as well as what you get. Otherwise is the code properly indented since it doesn’t look like it

– Sami Kuhmonen
Jan 3 at 12:11

Same input allowed. I re-intended the code-

– Quiti
Jan 3 at 12:20

Can you use numpy in your application?

– dubbbdan
Jan 3 at 18:51

Meaning sometimes with the same input? Or with different inputs? If different then provide the input and expected output as well as what you get. Otherwise is the code properly indented since it doesn’t look like it

– Sami Kuhmonen
Jan 3 at 12:11

Same input allowed. I re-intended the code-

– Quiti
Jan 3 at 12:20

Can you use numpy in your application?

– dubbbdan
Jan 3 at 18:51

add a comment |

2 Answers
2

active

oldest

votes

My major concern with your code is how allowedletter is modified in this loop:

    if mylist[i][0] == allowedletter and used[i] == False:

        allowedletter = mylist[i][-1]

        used[i] = True

        place(howmanyplaced+1, allowedletter)

Since you're chaining sequences via recursion, not iteration, allowedletter should not be modified during this loop. Use a different variable. Below is my rework of your program fixing this issue and rethinking the code style:

def place(how_many_placed=0, allowed_letter=None):



    if how_many_placed == number:

        return 1



    answer = 0



    for i, sequence in enumerate(sequences):

        if not used[i] and (allowed_letter is None or sequence[0] == allowed_letter):

            used[i] = True

            answer += place(how_many_placed + 1, sequence[-1])

            used[i] = False



    return answer



number = int(input())



sequences = 



used = 



for _ in range(number):

    sequences.append(input())

    used.append(False)



print(place())

See if this works any better for you.

edited Jan 3 at 18:38

answered Jan 3 at 18:13

cdlane

19.9k21245

Great answer, thanks. One last question: why is it wrong to edit allowedletter inside the recursion?

– Quiti
Jan 4 at 10:47

@Quiti, you were using allowedletter in the if statement to determine which sequences were suitable, but then also used it in the body as a temporary to hold the last character of the chosen sequence. By the time the if comes around again, we're testing for a different letter! In an iterative approach we'd do this at some level as we chained sequeces together. But in your recursive approach, we want to continue filtering on the same letter as before as the recursion will deal with the next link in our chain.

– cdlane
Jan 4 at 17:51

add a comment |

If you can use numpy, here is a vectorized solution. np.roll shifts the list so you can compare the first letter of the next element to the last letter of the previous row.

import numpy as np



l = ['ACGA', 'ACGA', 'ACAC', 'CCCC', 'CTAC']    

a = np.array(l)    

last_letter= np.roll(a,1)[1:].view('<U1')[::len(a[-1])]

first_letter = a.view('<U1')[::len(a[0])][:-1]

sum(last_letter==first_letter)

#returns 4

answered Jan 3 at 20:16

dubbbdan

974922

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54021989%2fhow-many-ways-to-place-n-dna-chains%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

My major concern with your code is how allowedletter is modified in this loop:

    if mylist[i][0] == allowedletter and used[i] == False:

        allowedletter = mylist[i][-1]

        used[i] = True

        place(howmanyplaced+1, allowedletter)

def place(how_many_placed=0, allowed_letter=None):



    if how_many_placed == number:

        return 1



    answer = 0



    for i, sequence in enumerate(sequences):

        if not used[i] and (allowed_letter is None or sequence[0] == allowed_letter):

            used[i] = True

            answer += place(how_many_placed + 1, sequence[-1])

            used[i] = False



    return answer



number = int(input())



sequences = 



used = 



for _ in range(number):

    sequences.append(input())

    used.append(False)



print(place())

See if this works any better for you.

edited Jan 3 at 18:38

answered Jan 3 at 18:13

cdlane

19.9k21245

Great answer, thanks. One last question: why is it wrong to edit allowedletter inside the recursion?

– Quiti
Jan 4 at 10:47

@Quiti, you were using allowedletter in the if statement to determine which sequences were suitable, but then also used it in the body as a temporary to hold the last character of the chosen sequence. By the time the if comes around again, we're testing for a different letter! In an iterative approach we'd do this at some level as we chained sequeces together. But in your recursive approach, we want to continue filtering on the same letter as before as the recursion will deal with the next link in our chain.

– cdlane
Jan 4 at 17:51

add a comment |

My major concern with your code is how allowedletter is modified in this loop:

    if mylist[i][0] == allowedletter and used[i] == False:

        allowedletter = mylist[i][-1]

        used[i] = True

        place(howmanyplaced+1, allowedletter)

def place(how_many_placed=0, allowed_letter=None):



    if how_many_placed == number:

        return 1



    answer = 0



    for i, sequence in enumerate(sequences):

        if not used[i] and (allowed_letter is None or sequence[0] == allowed_letter):

            used[i] = True

            answer += place(how_many_placed + 1, sequence[-1])

            used[i] = False



    return answer



number = int(input())



sequences = 



used = 



for _ in range(number):

    sequences.append(input())

    used.append(False)



print(place())

See if this works any better for you.

edited Jan 3 at 18:38

answered Jan 3 at 18:13

cdlane

19.9k21245

Great answer, thanks. One last question: why is it wrong to edit allowedletter inside the recursion?

– Quiti
Jan 4 at 10:47

@Quiti, you were using allowedletter in the if statement to determine which sequences were suitable, but then also used it in the body as a temporary to hold the last character of the chosen sequence. By the time the if comes around again, we're testing for a different letter! In an iterative approach we'd do this at some level as we chained sequeces together. But in your recursive approach, we want to continue filtering on the same letter as before as the recursion will deal with the next link in our chain.

– cdlane
Jan 4 at 17:51

add a comment |

My major concern with your code is how allowedletter is modified in this loop:

    if mylist[i][0] == allowedletter and used[i] == False:

        allowedletter = mylist[i][-1]

        used[i] = True

        place(howmanyplaced+1, allowedletter)

def place(how_many_placed=0, allowed_letter=None):



    if how_many_placed == number:

        return 1



    answer = 0



    for i, sequence in enumerate(sequences):

        if not used[i] and (allowed_letter is None or sequence[0] == allowed_letter):

            used[i] = True

            answer += place(how_many_placed + 1, sequence[-1])

            used[i] = False



    return answer



number = int(input())



sequences = 



used = 



for _ in range(number):

    sequences.append(input())

    used.append(False)



print(place())

See if this works any better for you.

edited Jan 3 at 18:38

answered Jan 3 at 18:13

cdlane

19.9k21245

My major concern with your code is how allowedletter is modified in this loop:

    if mylist[i][0] == allowedletter and used[i] == False:

        allowedletter = mylist[i][-1]

        used[i] = True

        place(howmanyplaced+1, allowedletter)

def place(how_many_placed=0, allowed_letter=None):



    if how_many_placed == number:

        return 1



    answer = 0



    for i, sequence in enumerate(sequences):

        if not used[i] and (allowed_letter is None or sequence[0] == allowed_letter):

            used[i] = True

            answer += place(how_many_placed + 1, sequence[-1])

            used[i] = False



    return answer



number = int(input())



sequences = 



used = 



for _ in range(number):

    sequences.append(input())

    used.append(False)



print(place())

See if this works any better for you.

edited Jan 3 at 18:38

answered Jan 3 at 18:13

cdlane

19.9k21245

edited Jan 3 at 18:38

answered Jan 3 at 18:13

cdlane

19.9k21245

answered Jan 3 at 18:13

cdlane

19.9k21245

answered Jan 3 at 18:13

cdlane

19.9k21245

Great answer, thanks. One last question: why is it wrong to edit allowedletter inside the recursion?

– Quiti
Jan 4 at 10:47

@Quiti, you were using allowedletter in the if statement to determine which sequences were suitable, but then also used it in the body as a temporary to hold the last character of the chosen sequence. By the time the if comes around again, we're testing for a different letter! In an iterative approach we'd do this at some level as we chained sequeces together. But in your recursive approach, we want to continue filtering on the same letter as before as the recursion will deal with the next link in our chain.

– cdlane
Jan 4 at 17:51

add a comment |

Great answer, thanks. One last question: why is it wrong to edit allowedletter inside the recursion?

– Quiti
Jan 4 at 10:47

@Quiti, you were using allowedletter in the if statement to determine which sequences were suitable, but then also used it in the body as a temporary to hold the last character of the chosen sequence. By the time the if comes around again, we're testing for a different letter! In an iterative approach we'd do this at some level as we chained sequeces together. But in your recursive approach, we want to continue filtering on the same letter as before as the recursion will deal with the next link in our chain.

– cdlane
Jan 4 at 17:51

Great answer, thanks. One last question: why is it wrong to edit allowedletter inside the recursion?

– Quiti
Jan 4 at 10:47

@Quiti, you were using allowedletter in the if statement to determine which sequences were suitable, but then also used it in the body as a temporary to hold the last character of the chosen sequence. By the time the if comes around again, we're testing for a different letter! In an iterative approach we'd do this at some level as we chained sequeces together. But in your recursive approach, we want to continue filtering on the same letter as before as the recursion will deal with the next link in our chain.

– cdlane
Jan 4 at 17:51

add a comment |

If you can use numpy, here is a vectorized solution. np.roll shifts the list so you can compare the first letter of the next element to the last letter of the previous row.

import numpy as np



l = ['ACGA', 'ACGA', 'ACAC', 'CCCC', 'CTAC']    

a = np.array(l)    

last_letter= np.roll(a,1)[1:].view('<U1')[::len(a[-1])]

first_letter = a.view('<U1')[::len(a[0])][:-1]

sum(last_letter==first_letter)

#returns 4

answered Jan 3 at 20:16

dubbbdan

974922

add a comment |

If you can use numpy, here is a vectorized solution. np.roll shifts the list so you can compare the first letter of the next element to the last letter of the previous row.

import numpy as np



l = ['ACGA', 'ACGA', 'ACAC', 'CCCC', 'CTAC']    

a = np.array(l)    

last_letter= np.roll(a,1)[1:].view('<U1')[::len(a[-1])]

first_letter = a.view('<U1')[::len(a[0])][:-1]

sum(last_letter==first_letter)

#returns 4

answered Jan 3 at 20:16

dubbbdan

974922

add a comment |

If you can use numpy, here is a vectorized solution. np.roll shifts the list so you can compare the first letter of the next element to the last letter of the previous row.

import numpy as np



l = ['ACGA', 'ACGA', 'ACAC', 'CCCC', 'CTAC']    

a = np.array(l)    

last_letter= np.roll(a,1)[1:].view('<U1')[::len(a[-1])]

first_letter = a.view('<U1')[::len(a[0])][:-1]

sum(last_letter==first_letter)

#returns 4

answered Jan 3 at 20:16

dubbbdan

974922

If you can use numpy, here is a vectorized solution. np.roll shifts the list so you can compare the first letter of the next element to the last letter of the previous row.

import numpy as np



l = ['ACGA', 'ACGA', 'ACAC', 'CCCC', 'CTAC']    

a = np.array(l)    

last_letter= np.roll(a,1)[1:].view('<U1')[::len(a[-1])]

first_letter = a.view('<U1')[::len(a[0])][:-1]

sum(last_letter==first_letter)

#returns 4

answered Jan 3 at 20:16

dubbbdan

974922

answered Jan 3 at 20:16

dubbbdan

974922

answered Jan 3 at 20:16

dubbbdan

974922

answered Jan 3 at 20:16

dubbbdan

974922

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu