Suppose, you are the owner of a bank that operates in a strange way. Customers can lend money from your bank (just like a normal bank) and they can also deposit money in your bank. A register is maintained to track the daily transactions. However, being the strange owner of a strange bank, you have a fascination with finding out whether a portion of your daily transactions (in/out) balance out to zero. For example, suppose your daily transaction register looks like this: 1 Lend 100 2 Deposit 150 3 Lend 400 4 Lend 500 5 Deposit 1000 6 Lend 460 7 Deposit 160 8 Deposit 200 9 Lend 500 10 Depost 100 In this case, there is a portion of the transactions that would balance itself out. (6th, 7th, 8th, and 10th transactions would amount to 0). Your task is to use a genetic algorithm to solve this strange bank problem. Task Breakdown: Model the transaction register in a way suitable for the problem. Write a fitness function. Hint: It is the sum of the non-zero elements of a register. Write the crossover function. Write the mutation function. Create a population of randomly generated registers. Run genetic algorithms on the population until highest fitness has been reached and/or number of maximum iterations has been reached. Input The first line has a number N denoting the number of daily transactions followed by N lines each starting with either l or d and a number S denoting the amount of transaction. Here: N ( 1 N 102 ) S ( 1 S 105 ) Output The output would be a binary string denoting the specific transactions that balance themselves to zero or -1 if such a string cannot be formed. String consisting of all zeros won’t be accepted. Example: Sample Input 1 7 l 120 l 289 d 475 l 195 d 6482 l 160 d 935 Sample Output 1 1011010 Sample Input 2 5 l 100 l 450 d 500 l 7923 d 9055 Sample Output 2 -1

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

Suppose, you are the owner of a bank that operates in a strange way. Customers can lend money from your bank (just like a normal bank) and they can also deposit money in your bank. A register is maintained to track the daily transactions. However, being the strange owner of a strange bank, you have a fascination with finding out whether a portion of your daily transactions (in/out) balance out to zero. For example, suppose your daily transaction register looks like this:

1	Lend	100
2	Deposit	150
3	Lend	400
4	Lend	500
5	Deposit	1000
6	Lend	460
7	Deposit	160
8	Deposit	200
9	Lend	500
10	Depost	100

In this case, there is a portion of the transactions that would balance itself out. (6th, 7th, 8th, and 10th transactions would amount to 0).

Your task is to use a genetic algorithm to solve this strange bank problem.

Task Breakdown:

Model the transaction register in a way suitable for the problem.
Write a fitness function. Hint: It is the sum of the non-zero elements of a register.
Write the crossover function.
Write the mutation function.
Create a population of randomly generated registers.
Run genetic algorithms on the population until highest fitness has been reached and/or number of maximum iterations has been reached.

Input

The first line has a number N denoting the number of daily transactions followed by N lines each starting with either l or d and a number S denoting the amount of transaction. Here:

N ( 1 N 102 )

S ( 1 S 105 )

Output

The output would be a binary string denoting the specific transactions that balance themselves to zero or -1 if such a string cannot be formed. String consisting of all zeros won’t be accepted.

Example:

Sample Input 1

l 120

l 289

d 475

l 195

d 6482

l 160

d 935

Sample Output 1

1011010

Sample Input 2