[SOLVED] EEE472-CSE422 Lab 2 -Strange Bank Problem

EEE472/CSE422 Strange Bank Problem

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:

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:

1. Model the transaction register in a way suitable for the problem.
2. Write a fitness function. Hint: It is the sum of the non-zero elements of

   a register.

3. Write the crossover function.
4. Write the mutation function.
5. Create a population of randomly generated registers.
6. 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 𝑁 denoting the number of daily transactions followed by 𝑁 lines each starting with either l or d and a number 𝑆 denoting the amount of transaction. Here:

𝑁 ( 1 ≤ 𝑁 ≤ 10 2 )

𝑆 ( 1 ≤ 𝑆 ≤ 10 5 )

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:

1011010