How to solve ‘trapRooms’ in CodeFights

The Problem:

A zoological museum can be represented as a matrix in which each cell is a room. The alarm system in the museum allows visitors to go from each room only in one direction, specific to that room.

One night the exhibits went mad and messed the alarm system up. Now there are traps in the museum. A room is considered to be a trap if it’s impossible to leave the museum starting from it. A person leaves the building once he leaves the rectangle that represents it.

Given the museum’s configuration, find the number of traps in it.

Example

For

museum = [['U', 'L'],
          ['R', 'L']]

the output should be
trapRooms(museum) = 2.

There is no exit if you start from either of the bottom rooms.

Check out the image below for better understanding:

Input/Output

• [time limit] 4000ms (py)

• [input] array.array.char museum

  A non-empty rectangular matrix. The possible values of museum[i] are:

  • 'L' if it’s possible to move to the left;
  • 'R' if it’s possible to move to the right;
  • 'U' if it’s possible to move up;
  • 'D' if it’s possible to move down.

  Guaranteed constraints:
  1 ≤ museum.length ≤ 10,
  1 ≤ museum[0].length ≤ 10.

• [output] integer

  The number of traps.

The Solution:

def trapRooms(museum):
    x=[[0]*len(museum[0]) for x in range(len(museum))]
    def rec(a,b,x):
        if not(a<len(museum) and a>=0 and b<len(museum[0]) and b>=0):
            return 0
        if x[a][b]:
            return 1
        s=0
        x[a][b]=1
        if museum[a][b]=='U':
            s+=rec(a-1,b,x)
        if museum[a][b]=='D':
            s+=rec(a+1,b,x)
        if museum[a][b]=='L':
            s+=rec(a,b-1,x)
        if museum[a][b]=='R':
            s+=rec(a,b+1,x)
        x[a][b]=0
        return s
    p=0
    for a in range(len(museum)):
        for b in range(len(museum[0])):
            p +=rec(a,b,x)
            print p
    return p

The Explanation:

We need to traverse the maze starting from each o the rooms and see if we can go outside, or go back to one of the rooms we have already passed. If we see any rooms we have already passed, that means we are stuck in the maze because the same room will always cause us to go back to same route.

 

 

How to solve ‘bijectiveBase10’ in CodeFights

The Problem:

Consider a numeral system similar to base-10 numeral system with the only difference that it does not use a digit to represent zero; instead it has a digit to represent ten, such as A. It is called bijective base-10 system. For example, numbers that do not contain zeros in base-10 system remain the same when converted to bijective base-10 system.

Given a positive integer in base-10 system, return its representation in bijective base-10 system.

Example

• For a = 12345, the output should be
  bijectiveBase10(a) = "12345";
• For a = 10, the output should be
  bijectiveBase10(a) = "A";
• For a = 100, the output should be
  bijectiveBase10(a) = "9A".

  100 = 10 * 9 + 10 -> "9A".

• For a = 2010, the output should be
  bijectiveBase10(a) = "19AA".

  2010 = 1 * 103 + 9 * 102 + 10 * 10 + 10 -> "19AA".

Input/Output

• [time limit] 4000ms (py)

• [input] integer a

  A positive integer.

  Guaranteed constraints:
  10 ≤ a ≤ 6 · 108.

• [output] string

  The string representation of a in bijective base-10 system.

 

The Solution:

def bijectiveBase10(a):
    if '0' not in `a`:
        return `a`
    r=""
    while a>0:
        if a%10==0:
            a-=10
            r+="A"
        else:
            r+=str(a%10)
        a/=10
    return r[::-1]

The Explanation:

We need to understand the arithmetic behind this. For every 0 digit we see, we replace it with an ‘A’, which is 10. So, we decrease 10 from our number, because it is not zero anymore, but a ten. Then, we continue doing this just as if we are converting the number to another base. At the end, we have the reverse of the number, so, we return reverse.

The first if statement is actually unnecessary, it would work exactly the same without that if block.

How to solve ‘studentsAge’ in CodeFights

The Problem:

My friend Albi is a teacher. At the beginning of each lesson, her students form a line and enter the class one by one. As they enter, each student shakes her hand. Albi enters the students’ names in a list in the order in which they enter the classroom. After work, she analyzes the list to get a hint of the connections and relationships in the class.

Albi has a hunch that the ages of the students can tell her a lot. She has a list of the ages of her students in the order they entered the classroom, and she wants to calculate the number of pairs of students such that their age difference is exactly 1, and the youngest student in the pair entered before the oldest. Please help my friend!

Example

• For students = [2, 4, 3, 4, 6], the output should be
  studentsAge(students) = 2.

  There are two pairs of students Albi would be interested in: (2, 3) and (3, 4).

• For students = [5, 4, 9, 10], the output should be
  studentsAge(students) = 1.

  The only interesting pair of students in (9, 10).

Input/Output

• [time limit] 4000ms (py)

• [input] array.integer students

  The ages of the students in the order they entered the classroom.

  Guaranteed constraints:
  1 ≤ students.length ≤ 105,
  0 ≤ students[i] ≤ 105.

• [output] integer

  An integer with the answer for Albi.

The Solution:

def studentsAge(s):
    m=[0]*5**9
    c=0
    for x in s:
        c+=m[x-1]
        m[x]+=1
    return c

The Explanation:

There are multiple ways to solve this problem. Smarter way is to use a dictionary and store how many times each element is seen. However, to achieve the shortest solution (62 character in Python), we need a less efficient approach. Instead of a dictionary, create an array of size 10^5 and use this array to count each element.

For each element x in array, we need how many times x-1 is seen before that. So, for each element, we sum up this number and return it. The reason the array is initialized with length 5^9 is to decrease 1 character from 10^6.

How to Solve ‘Chemicals’ in CodeFights

The Problem:

Abby is a researcher at a company that makes chemical solutions. Her boss left her with a difficult task late Friday afternoon, and waltzed off into the weekend.

Abby has a hazardous liquid that reacts with oxygen by exploding. Her task is to distribute the liquid between special containers. The company buys containers of specific sizes in bulk, so she has access to a lot of containers of each size.

Since the liquid is explosive, Abby needs to fill the containers full to the exact capacity. Preparing the containers is tricky, so Abby wants to use as few containers as possible. Given the totalAmount of liquid and the set of container sizes containers, find the total number of containers she will need.

If there’s no way to distribute the liquid as described above, return -1 instead.

Example

• For totalAmount = 18 and containers = [1, 2, 5, 10],
  the output should be
  Chemicals(totalAmount, containers) = 4.Abby has access to containers with sizes 10, 5, 2, and 1, and will use one container of each size.
• For totalAmount = 9 and containers = [1, 4, 6],
  the output should be
  Chemicals(totalAmount, containers) = 3.Abby can use two containers of size 4 and one container of size 1.

Input/Output

• [time limit] 4000ms (py)

• [input] integer totalAmountThe amount of chemicals.Guaranteed constraints:
  0 ≤ totalAmount < 5 · 104.
• [input] array.integer containersA sorted array of distinct integers, denoting the container sizes.Guaranteed constraints:
  1 ≤ containers.length ≤ 15,
  0 ≤ containers[i] ≤ 1000.
• [output] integerThe minimum number of containers needed to distribute the liquid. Return -1 if there’s no way to distribute the liquid.

The Solution:

def Chemicals(totalAmount, containers):
    totalAmount+=1
    d=[999999]*totalAmount
    d[0]=0
    for x in containers:
        if x <totalAmount:
            d[x]= 1
    for x in range(totalAmount):
        for y in containers:
            if x-y>0:
                d[x]= min(d[x],d[x-y]+1)
    if d[-1]==999999:
        return -1
    return d[-1]

The Explanation:

Knapsack Problem, you can search for this term and learn more about it. In essence, create an array d. Each element of d shows the best solution up to that index. The idea follows this:

If I can get maximum value of 90 at 10 weight, and I have an item with weight 2 and value 10, then, at the best case, I can have 100 value at 92.

Reversing this, we want to minimize our weight at a given value. And slightly modifying the problem, we want to minimize number of containers at a given value.

If I can use minimum 5 containers to store 90, and I have containers of size 5, then I can have minimum 6 containers for size 95.

 

How to Solve ‘minSubstringWithAllChars’ in CodeFights

The Problem:

You have two strings, s and t. The string t contains only unique elements. Find and return the minimum consecutive substring of s that contains all of the elements from t.

It’s guaranteed that the answer exists. If there are several answers, return the one which starts from the smallest index.

Example

For s = "adobecodebanc" and t = "abc", the output should be
minSubstringWithAllChars(s, t) = "banc".

Input/Output

• [time limit] 4000ms (py)

• [input] string sA string consisting only of lowercase English letters.Guaranteed constraints:
  0 ≤ s.length ≤ 100.
• [input] string tA string consisting only of unique lowercase English letters.Guaranteed constraints:
  0 ≤ t.length ≤ min(26, s.length).
• [output] string

The Solution:

def minSubstringWithAllChars(s, t):
    for x in range(len(s)+1):
        for p in range(len(s)-x+1):
            c = filter(lambda x: x in t,s[p:p+x])
            if len(set(c))==len(t):
                return s[p:p+x]
    return ""

The Explanation:

How to Solve ‘isCryptSolution’ in CodeFights

The Problem:

A cryptarithm is a mathematical puzzle for which the goal is to find the correspondence between letters and digits, such that the given arithmetic equation consisting of letters holds true when the letters are converted to digits.

You have an array of strings crypt, the cryptarithm, and an an array containing the mapping of letters and digits, solution. The array crypt will contain three non-empty strings that follow the structure: [word1, word2, word3], which should be interpreted as the word1 + word2 = word3 cryptarithm.

If crypt, when it is decoded by replacing all of the letters in the cryptarithm with digits using the mapping in solution, becomes a valid arithmetic equation containing no numbers with leading zeroes, the answer is true. If it does not become a valid arithmetic solution, the answer is false.

Example

For crypt = ["SEND", "MORE", "MONEY"] and

solution = [['O', '0'],
            ['M', '1'],
            ['Y', '2'],
            ['E', '5'],
            ['N', '6'],
            ['D', '7'],
            ['R', '8'],
            ['S', '9']]

the output should be
isCryptSolution(crypt, solution) = true

When you decrypt "SEND", "MORE", and "MONEY" using the mapping given in crypt, you get 9567 + 1085 = 10652 which is correct and a valid arithmetic equation.

For crypt = ["TEN", "TWO", "ONE"] and

solution = [['O', '1'],
            ['T', '0'],
            ['W', '9'],
            ['E', '5'],
            ['N', '4']]

the output should be
isCryptSolution(crypt, solution) = false

Even though 054 + 091 = 145, 054 and 091 both contain leading zeroes, meaning that this is not a valid solution.

Input/Output

• [time limit] 4000ms (py)

• [input] array.string crypt

  An array of three non-empty strings containing only uppercase English letters.

  Constraints:
  crypt.length = 3,
  1 ≤ crypt[i].length ≤ 14.

• [input] array.array.char solution

  An array consisting of pairs of characters that represent the correspondence between letters and numbers in the cryptarithm. The first character in the pair is an uppercase English letter, and the second one is a digit in the range from 0to 9.

  Constraints:
  solution[i].length = 2,
  'A' ≤ solution[i][0] ≤ 'Z',
  '0' ≤ solution[i][1] ≤ '9',
  solution[i][0] ≠ solution[j][0], i ≠ j,
  solution[i][1] ≠ solution[j][1], i ≠ j.

  It is guaranteed that solution only contains entries for the letters present in crypt and that different letters have different values.

• [output] boolean

  Return true if the solution represents the correct solution to the cryptarithm crypt, otherwise return false.

The Solution:

The Explanation:

Map the letters to the given numbers.

Generate corresponding numbers,

if first + second = third, check if they have leading zeros by comparing the length of numbers and the words, if not, return 1

f they have leading zeros or the sum is not equal, return 0

How to Solve ‘containsCloseNums’ in CodeFights

The Problem:

Given an array of integers nums and an integer k, determine whether there are two distinct indices i and j in the array wherenums[i] = nums[j] and the absolute difference between i and j is less than or equal to k.

Example

• For nums = [0, 1, 2, 3, 5, 2] and k = 3, the output should be
  containsCloseNums(nums, k) = true.

  There are two 2s in nums, and the absolute difference between their positions is exactly 3.

• For nums = [0, 1, 2, 3, 5, 2] and k = 2, the output should be

  containsCloseNums(nums, k) = false.

  The absolute difference between the positions of the two 2s is 3, which is more than k.

Input/Output

• [time limit] 4000ms (py)

• [input] array.integer nums

  Constraints:
  0 ≤ nums.length ≤ 55000,
  -231 - 1 ≤ nums[i] ≤ 231 - 1.

• [input] integer k

  Constraints:
  0 ≤ k ≤ 35000.

• [output] boolean

The Solution:

The Explanation:

First of all, we can solve this by running two loops, one is i from 1 to k and the other j from 0 to len(nums)-i and compare nums[j] and nums[i+j]. If we find an equality, return 1. If none found, return 0.

However, we would receive Time Limit Exceeded Error. So, we need a better solution. We know that when we sort numbers, the same numbers will be consecutive in sorted order. So, if we store the original locations of all elements, we will have the same elements together and also know their original location. All we have to do now is to check if any consecutive equal numbers have a smaller distance than k+1.

This reduces our complexity from, let’s say len(nums) = n. Then, O(n*k) to O( n*log(n) )

limit of n is 55000 so, logn is approximately 16. Where k could be 35000. So, our worst case scenario becomes 55000*35000 to 55000*16.

How we do this is simple. First,generate a new array with numbers and their original addressses. Then, sort them using their values. Then, for each element, check if the previous element has the same value, if so, check their original location distances. If smaller than k+1, return 1

Otherwise, return 0

How to Solve ‘SimplifyPath’ in CodeFights

The Problem:

Given an absolute file path (Unix-style), shorten it to the format /<dir1>/<dir2>/<dir3>/....

Here is some info on Unix file system paths:

• / is the root directory; the path should always start with it even if it isn’t there in the given path;
• / is also used as a directory separator; for example, /code/fights denotes a fights subfolder in the code folder in the root directory;
  • this also means that // stands for “change the current directory to the current directory”
• . is used to mark the current directory;
• .. is used to mark the parent directory; if the current directory is root already, .. does nothing.

Example

For path = "/home/a/./x/../b//c/", the output should be
simplifyPath(path) = "/home/a/b/c".

Here is how this path was simplified:
* /./ means “move to the current directory” and can be replaced with a single /;
* /x/../ means “move into directory x and then return back to the parent directory”, so it can replaced with a single /;
* // means “move to the current directory” and can be replaced with a single /.

Input/Output

• [time limit] 4000ms (py)

• [input] string pathA line containing a path presented in Unix style format. All directories in the path are guaranteed to consist only of English letters.

  Constraints:
  1 ≤ path.length ≤ 5 · 104.

• [output] stringThe simplified path.

The Solution:

The Explanation:

How to Solve ‘treeLevelSum’ in CodeFights

The Problem

Given a binary tree and a number k, your task is to find the sum of tree nodes at level k. The binary tree is represented by a string tree with the format: (<node-value>(<left subtree>)(<right subtree>)).

Example

For tree = "(0(5(6()())(14()(9()())))(7(1()())(23()())))" and k = 2, the output should be

treeLevelSum(tree, k) = 44.

Explanation: The nodes at level 2 are 6, 14, 1, and 23, so the answer is 6 + 14 + 1 + 23 = 44.

Input/Output

• [time limit] 4000ms (py)

• [input] string tree

  A valid string representing a tree.

  Constraints:

  2 ≤ tree.length ≤ 105.

  All the values in a given tree are guaranteed to be integers.

• [input] integer k

  Constraints:

  0 ≤ k ≤ 105.

• [output] integer

  The total sum of all the values at level k in a tree.

The Solution

How to Solve ‘numberof1Bits’ in CodeFights

The Problem

Note: Avoid using built-in functions that convert integers to their binary representations. Write the solution that uses O(k)operations per test, where k is the number of bits set to 1.

Write a function that takes an unsigned (positive) integer and returns the number of 1 bits its binary representation contains. This value is also known as the integer’s Hamming weight.

Example

For n = 13, the output should be
numberOf1Bits(n) = 3.

13 is represented in binary as 1101, so the function should return 3.

Input/Output

• [time limit] 4000ms (py)

• [input] integer n

  Constraints:
  0 ≤ n ≤ 231 - 1.

• [output] integer

The Solution