DEV Community: HHMathewChan

Leetcode 2. Add Two Numbers - my solution

HHMathewChan — Mon, 03 Jul 2023 17:36:22 +0000

Description

You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order,
- and each of their nodes contains a single digit.
Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Input:** l1 = [2,4,3], l2 = [5,6,4]
**Output:** [7,0,8]
**Explanation:** 342 + 465 = 807.

Constraints:
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Problem definition

Function:add two numbers
Input: list1, a linked list, list2, a linked list
Precondition: 0<|list1| < 100, |list 2| > 0, 0 ≤ node.value ≤ 9, 0< list1[0] ≤ 9, 0< list2[0] ≤ 9
Output: sum, a linked list
Postcondition: $\times 10^0 + sum[1] x 10^1 ... + sum[| sum | - 1] \times 10^{| list1 | - 1} = list1[0] x 10^0 + list1[1] \times 10^1 ... + list1[| list1 | - 1] \times 10^{| list1 | - 1} + list2[0] \times 10^0 + list2[1] \times 10^1 ... + list2[| list2 | - 1] x 10^{| list2 | - 1}$

The outline of the algorithm

This question can be divided into two parts: 1. calculate the sum of the two linked lists and 2. convert the sum into a linked list.
I solve this in a recursive style

The first part

Function: sum of a list
Input: list1, a linked list, degree, an integer
Precondition: 0 < |list1| < 100, 0 ≤ node.value ≤ 9, 0< list1[0] ≤ 9
Output: sum, an integer
Postcondition: $\times 10^{degree} + list1[1] \times 10^{degree + 1} ... + list1[| list1 | - 1] \times 10^{degree + | list1 |}$

Let's think about the base case: The lowest possible input is there is only one node in the linked list, which means its next value is None. In this case, we multiply the value of the current pointing node by 10 to the power of nodes we travel
What about other cases: we multiply the value of the current pointing node by 10 to the power of nodes we travel, I use degree to denote it and + call the function on the next node

The recursive definition is:
- if n is the last node: node.value x $10^{degree}$
- otherwise: node.value x $10^{degree}$ + sum of a list(node.value, degree + 1).

For the complexity, in each recursive call, we calculate the node.value x 10^{degree} which has a complexity of O(\log degree)
number of recursive call x complexity of each call = $∣list1∣ \times O(\log degree)) = O ( | list1 | \times \log degree)$ . Since the degree is increased by 1 for everyone more linked list, so it is also $O(log⁡∣list1∣)O(\log |list1|)$ .
The code

def sum_of_a_list(node, degree = 0):
        if node.next == None:
            return node.val * 10 ** degree
        else:
            return node.val * 10 ** degree + sum_of_a_list(node.next, degree + 1)

The second part

this part is to create a linked list from the sum of the two linked list
Function: new linked list
Input: sum, an integer
Precondition: an int ≥ 0
Output: list3, a linked list
Postcondition: $\times 10^{0} + list3[1] \times 10^{1} ... + list3[| list3 | - 1] \times 10^{| list3 |}$

The outline of the algorithm

I would assign one digit to one node starting from the last digit of the sum, the last digit can be found by the remainder sum divided by 10. Every time I assign a digit, I will shift the end pointer to the left by shortening the sum using floor division by 10. Since in this implementation, there is no head pointer to the first node of the linked list, I have to explicitly create a first node variable to assign the last digit of the sum and pass the rest of sum to the recursive function.

The base case of the reclusive approach would be the sum becoming 0. The sum will only become 0 when both linked lists have only a 0 value node or after the floor division a single digit, which means the last digit of the sum. The former situation is handled by the creation of the first node variable. In the latter situation, since there is no leading 0 in the sum, so we don't need to assign this 0, so we will assign the value of this node to be None.
In other cases: we assign the last digit of the sum and then cut the last digit of the sum and assign the node.next value to the next node
The recursive definition is:
- if sum = 0: node.val = none
- if sum > 0:
  - current node.val = sum % 10
  - sum = sum // 10
  - current node.next = new linked list(sum)

The complexity is basically affected by the number of digits of sum, i.e. $O((\log_{10} sum) + 1) = O (\log sum)$ . Since sum is larger when the two linked list given in the first place is longer, so this also mean it has a complexity of O(log l list1|).
The code

def new_linked_list(sum:int):
  def in_new_linked_list(an_int2:int):
            if an_int2 == 0:
                return None
            else:
                current_node = ListNode()
                current_node.val = an_int2 % 10
                an_int2 = an_int2 // 10
                current_node.next = in_new_linked_list(an_int2)
                return current_node

        first_node = ListNode(sum % 10)
        sum = sum // 10
        first_node.next = in_new_linked_list(sum)
        return first_node

Combined algorithm

let sum be the sum of list1 and the sum of list 2
convert sum to a linked list
let first node be the linked list of sum

The overall complexity is $\times \log | list1 |) + \log | list1 | )$ = O (( | list1 | x \log | list1 |). Since we are concerned only with the fastest growing term. This means the overall complexity is a log-linear complexity.
The Code

def addTwoNumbers(l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """
    def sum_of_a_list(node, degree = 0):
        if node.next == None:
            return node.val * 10 ** degree
        else:
            return node.val * 10 ** degree + sum_of_a_list(node.next, degree + 1)

    # degree = 0
    sum = sum_of_a_list(l1,0) + sum_of_a_list(l2, 0)

    def new_linked_list(sum:int):
        def in_new_linked_list(an_int2:int):
            if an_int2 == 0:
                return None
            else:
                current_node = ListNode()
                current_node.val = an_int2 % 10
                an_int2 = an_int2 // 10
                current_node.next = in_new_linked_list(an_int2)
                return current_node

        first_node = ListNode(sum % 10)
        sum = sum // 10
        first_node.next = in_new_linked_list(sum)
        return first_node   

    return new_linked_list(sum)

Feeling

- Actually, I am quite happy to finish this challenge, although this is a slow algorithm. This is the first time, I successfully write a recursive algorithm outside of the course material. This give me more confidence and experience to write recursive algorithms which I am a bit confused about before.

Reference:

Add Two Numbers - LeetCode

My Solution to Delimiter Soup from kattis

HHMathewChan — Mon, 19 Jun 2023 16:45:32 +0000

Problem

Whenever a programmer starts to learn a Lisp,
- they think that there are too many parentheses in it.
Sophia thinks there are too few,
- so she is making a programming language with only parentheses.
To spice it up a bit, she is also adding square brackets (‘[]’) and curly braces (‘{}’) to the language.
Right now, she is struggling to make people use it for production code.
Obviously, it has to be because of the bad error messages you get when you mess up the delimiters!
Right now, you only get the error message ‘syntax error’ when you mess them up.
Any opening delimiter must be closed by the same type of delimiter: ‘(’ is closed with ‘)’, [ is closed by ] etc.
Sophia wants to improve the error message so that you at least get some help finding out where it all went wrong.

Input

The input consists of two lines.
- The first line contains an integer |L|, the length of the next line.
- The next line contains L, the program you want to validate.

Output

Output
- the character and the 0-indexed location
- of the first closing delimiter
  - that does not match with the opening delimiter.
If there are no errors, or there are more opening delimiters than closing delimiters,
- print ‘ok so far’ instead.

Limits

$1 ≤ L ≤ 200$
L contains only the characters ()[]{} and spaces
L does not start with a space character

My solution

problem definition

Function: validate program
Inputs: length, an integer that is the length of the L
- L, a string contain the program to validate
Precondition:
- $1 ≤ length ≤ 200$
- L contains only the characters ()[]{} and spaces
- L does not start with a space character
Output:
- message, a string
Postcondition:
- if there is a closing delimiter that does not match with the opening delimiter:
  - message contain the the first closing delimiter and its index
- If there are no errors, or there are more opening delimiters than closing delimiters:
  - message contain 'ok so far’ .

Test table

The test table

validate_program_tests = [
    # case,            length,  L,                           expected
    ['ok for length 1',     1,  '[',                          'ok so far'],
    ['] at 0',              1,  ']',                          '] 0'],
    ['] at 7',              8,  '([] [] ]',                    '] 7'],
    ['ok for length is 13', 13, '(([] [[]] ())',               'ok so far'],
    ['] at 20',             21, '[ { { () () () () } ]',       '] 20'],
    ['ok for length is 27', 27, '[ { [[()]] (({})) } ] () {}', 'ok so far'],
    [') at 8',              19, '[[]] () ) [] {{}} {',          ') 8'],
]

Outline of the algorithm

create a empty stack for the delimiters opened so far and not yet matched. Iterate over L for length times and process each character. If it's an open delimiter, push it on the stack. If it's a closing delimiter and the stack is empty or the top item isn't a matching opening delimiter, print that character and the index of the character, and stop. Otherwise, the delimiters match, so pop the opening delimiter from stack. If the end of L is reached, print "ok so far".

Algorithm

let opened be an empty stack
for each index from 0 to length - 1:
1. let character be L[index]
2. if character = '(' or character = '[' or character = '{':
  1. push character on opened
3. otherwise if character = ')':
  1. if │opened│ > 0 and top of opened = '(':
    1. pop opened
  2. otherwise:
    1. let message be the character and the index of the character
    2. stop
4. otherwise if character = ']':
  1. if │opened│ > 0 and top of opened = '[':
    1. pop opened
  2. otherwise:
    1. let message be the character and the index of the character
    2. stop
5. otherwise if character = '}':
  1. if │opened│ > 0 and top of opened = '{':
    1. pop opened
  2. otherwise:
    1. let message be the character and the index of the character
    2. stop
6. otherwise:
  1. do nothing
let message be 'ok so far'

Complexity

The stack is implemented using the list data type in python
Step 1. Θ(1)
Step 2, the loop has different case, state later
- Step 2.1 Θ(1)
- Step 2.2 Θ(1)
  - Step 2.2.1 Θ(1)
- Step 2.3 Θ(1)
  - Step 2.3.1
  - get the length of stack is Θ(1) as Python's list implementation stores the length of the list as a separate attribute
  - so the complexity of step 2.3.1 would be Θ(1 + 1 + 1) = Θ(1)
    - Step 2.3.1.1 Θ(1)
  - Step 2.3.2
    - Step 2.3.2.1 Θ(1)
    - Step 2.3.2.2 Θ(1)
- The overall complexity of step 2.3 is Θ(1)
- The complexity of Step 2.4 , Step 2.5 and Step 2.6 is the same as step 2.3 = Θ(1)
Step 3 Θ(1)
The best case for step 2 is the first character is a closing delimiter, the loop will execute 1 time, so the complexity would be Θ(1)
The worst case for step 2 is it need to loop through the whole L , so the complexity would be Θ(|L|)
Since the largest factor that contribute to the complexity is step 2, and the best case of step 2 is a small input that can be ignore so the complexity of the whole program would be Θ(|L|)

The code

The code

def delimiter_soup(length, L):
    opened = []
    for index in range(length):
        char = L[index]
        if char in '([{':
            opened.append(char)
        elif char == ')':
            if len(opened) > 0 and opened[-1] == '(':
                opened.pop()
            else:
                return char + ' ' + str(index)
        elif char == ']':
            if len(opened) > 0 and opened[-1] == '[':
                opened.pop()
            else:
                return char + ' ' + str(index)
        elif char == '}':
            if len(opened) > 0 and opened[-1] == '{':
                opened.pop()
            else:
                return char + ' ' + str(index)
        else:
            pass
    return 'ok so far'

The extra part add to answer in Kattis

length = int(input())
L = input()
print(delimiter_soup(length, L))

Additional

some alternation

char + ' ' + str(index)
# can be replace as follow using f-string
f'{char}{index}'

Source

Delimiter Soup – Kattis, Kattis

Python challenge: Leetcode 3. Longest Substring Without Repeating Characters

HHMathewChan — Sun, 24 Jul 2022 17:06:43 +0000

Question

Given a string s, find the length of the longest substring without repeating characters.

Example

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

My attempt

Attempt 1 (fail at last two case, exceed time limit)

algorithm

>Find the length of the longest substring without repeating characters.
initialise the length_of_s equals to length of s
initialise the length_list_of_sub_string to the empty string

define a find_and_record_substring program:
    initialise seen_string as an empty string
    initialise seen_dictionary as an empty dictionary
    initialise the length equals to 0
    for each character in s:
       if the charcter do not found in seen_string:
           add the character to seen_string
        otherwise:
            initialise the length equals to length of seen_string
            update seen_dictionary with length as key, seen_string as value
            set seen_string to empty string
            add the character to seen_string
    return the maximum of the key of the dictionary

>>find and record each substring without repeating characters in the string s

repeat the find_and_record_substring program for the length of s times:
    add the result of find_and_record_substring program to length_list_of_sub_string
    set s to a s that remove the first character

>>return the longest substring without repeating characters
return longest length equals to the maximum of length_list_of_sub_string

code

class Solution:  
    def lengthOfLongestSubstring(self, s: str) -> int:  
        length_of_s = len(s)  
        length_list_of_sub_string = []  
        # program to find each substring without repeating characters in the string
        def find_and_record_substring(str1: str):  
            seen_string = ""  
            seen_dict = {}  
            for char in str1:  
                if char not in seen_string:  
                    seen_string += char  
                # if char found in seen_string
                else:
                    # add the current seen_string to dict first  
                    length_of_seen_string = len(seen_string)  
                    seen_dict.update({length_of_seen_string: seen_string})
                    # clear the seen_string and continue to build seen_string  
                    seen_string = ""  
                    seen_string += char
            # should add the current seen_string to dict
            length_of_seen_string = len(seen_string)  
            seen_dict.update({length_of_seen_string: seen_string})  
            longest_length = max(seen_dict.keys())  
            return longest_length  
        if s == "":  
            return 0  
        while length_of_s != 0:  
            length_list_of_sub_string.append(find_and_record_substring(s))
            # remove the first charcter of s  
            s = s[1::]
            # update the length of s  
            length_of_s = len(s)  
        return max(length_list_of_sub_string)

Attempt 2 (success)

basically the same way as the above , but add a function to find the upper limit of a substring that is equal to the number of unique character in the string s.
and when any substring reach the upper limit, the function will not go any forward and return the substring length instead
code

class Solution:  
    def lengthOfLongestSubstring(self, s: str) -> int:  
        length_of_s = len(s)  
        length_list_of_sub_string = []  
        temp_max = 0  

        def longest(str1):  
            set1 = set(str1)  
            return len(set1)  

        max_limit = longest(s)  

        def find_and_record_substring(str1: str):  
            seen_string = ""  
            seen_dict = {}  
            for char in str1:  
                if char not in seen_string:  
                    seen_string += char  
                else:  
                    length_of_seen_string = len(seen_string)  
                    seen_dict.update({length_of_seen_string: seen_string})  
                    seen_string = ""  
                    seen_string += char  
            length_of_seen_string = len(seen_string)  
            seen_dict.update({length_of_seen_string: seen_string})  
            longest_length = max(seen_dict.keys())  
            return longest_length  

        if s == "":  
            return 0  
        while length_of_s != 0 and temp_max < length_of_s and temp_max < max_limit:  
            length_list_of_sub_string.append(find_and_record_substring(s))  
            s = s[1::]  
            length_of_s = len(s)  
            temp_max = max(length_list_of_sub_string)  
        return max(length_list_of_sub_string)

My reflection

so I learn a new algorithm today called Sliding Window Algorithm.

Credit

leetcode3

Instruction to install pygraphviz package in Pycharm in MacOs

HHMathewChan — Fri, 22 Jul 2022 14:47:00 +0000

Since I spend a lot of time to solve this problem, so make a rocord for future reuse.

Environment

Mao os 12.4
Macbook air(M1,2020)
PyCharm 2022.1.4 (Community Edition)
- Runtime version: 11.0.15+10-b2043.56 aarch64
graphviz: stable 5.0.0
pygraphviz: 1.9

Problem

The problem is encounter after install graphviz
- as to install pygraphviz you need
  - Python (version 3.8, 3.9, or 3.10)
  - Graphviz (version 2.42 or later)
  - C/C++ Compiler
if you use normal command pip install graphviz to install graphviz first
- then use pip install pygraphviz to install pygraphviz
- you would encounter a fatal error

fatal error: 'graphviz/cgraph.h' file not found

the file cgraph.h cannot be found
even you may find the file in graphviz package file

Why this problem happen

the installation wizard of pygraphviz cannot find cgraph.h in his default searching path
So, you need to provide searching path when install pygraphviz

Solution that work for me

Step 1. use Homebrew to `graphviz` package first

Install Homebrew from its official website
type following command in Pycharm terminal

brew install graphviz

it takes a long time to install
- then you should be able to find graphviz file in the following path :(/opt/homebrew/Cellar/graphviz)

Some explanation

Homebrew is a kind of package manager for MacOS (or Linux)
and all package installed via Homebrew is stored its Homebrew file which is under an opt file
the opt file is a directory for installing unbundled packages
i.e. Homebrew in this case help you to install graphviz and provide an searching path for further installation for pygraphviz

Step 2. Provide searching path when install pygraphviz

type following command in Pycharm terminal

pip3 install --global-option=build_ext --global-option="-I$(brew --prefix graphviz)/include" --global-option="-L$(brew --prefix graphviz)/lib" pygraphviz

pip3 is just to make sure package is install for python 3
the -I and -L flags tell the linker where to look for the required Graphviz libraries at build time and run time
--prefix will let you specific where the directory to go for

Credit

Python Exercise 23: Two sum

HHMathewChan — Sat, 16 Jul 2022 08:35:58 +0000

Question

Given an array of integers nums and an integer target,
- return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution,
- and you may not use the same element twice.
You can return the answer in any order.

Example

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

My attempt

First attempt

The algorithm is work theoretical but too slow, run out of time if last two test case
algorithm

> find the indices of the two number such that they add up to target
>>find two number if they add up to the target
  for index1, num1 in the nums:
      for index2,num2 in the nums:
          if num2 is not the same number as num1:
              if value1 + value 2 == target:
                  return a list consist of index1 and index2

code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        final_list = [[index1,index2] for index1,value1 in enumerate(nums) for index2,value2 in enumerate(nums) if index2 > index1 if value1+value2 ==target]
        return final_list[0]

Second attempt (success pass all test)

algorithm

> find the indices of the two number such that they add up to target
>>find two number if they add up to the target
  for index1,value1 in nums:
      calculate a second_number that have a sum with value equals to target
      if second is in nums:
          find the indices of the second_number
          if the second_number is not the same number as value1:
              return a list consist of index1 and index2

code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for index1, value1 in enumerate(nums):
            second_number = target - value1
            if second_number in nums:
                second_number_index = nums.index(second_number)
                if second_number_index != index1:
                    return [index1, second_number_index]

My reflection

This is a good challenge to make me think a method that not just rely on for loop completely. And I learn a new pattern form others to use a dictionary to reduce searching time.

Credit

challenge on leetcode 1
solution on code recipe

Python exercise 22: ransomnote

HHMathewChan — Wed, 13 Jul 2022 15:25:36 +0000

Question

Given two strings ransomNote and magazine,
- return true
  - if ransomNote_can be constructed
  - by using the letters from_ magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.

Example

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

Constraints:
1 <= ransomNote.length, magazine.length <= 105
ransomNote and magazine consist of lowercase English letters.

My Solution

algorithm

>>determine if ransomNote can be constructed from magzine
  set lengthr to length of ransomNote
  set lengthm to length of magzine
  if lengthr>lengthm:
      return false
  else:
      for each char in ransomnote:
          if char appear in magazine:
              remove char in ransomenote
              remove char in magazine
              if lengthr equal to 0:
                  return True
      else:
        return False

key point
- need to split the question into case in terms of the difference between two string
- if length of ransomNote greater than length of magzine
  - there is no way magzine have enough word to construct to the ransomNote
code

class Solution:  
    def canConstruct(self,ransomNote: str, magazine: str) -> bool:  
        lenngthr = len(ransomNote)  
        lenngthm = len(magazine)  
        if lenngthr>lenngthm:  
            return  False
        # lenngthr<=lenngthm  
        else:  
            for char in ransomNote:  
                if char in magazine:
                    # remove that char from both string  
                    magazine=magazine.replace(char,"",1)  
                    ransomNote=ransomNote.replace(char,"",1)
                    # This mean the whole string can be found on magzine  
                    if len(ransomNote) == 0:  
                        return True  
            # if ransomNote has not reduce to an empty string
            else:  
                return False

My reflection

I learn from others that when checking one group is belong to other group, use dictionary is faster.
I do not understand why the solution should construct within a class but not a separate function.

Credit

challenge find on leet code 383

Python Exercise 21: list comprehensions

HHMathewChan — Tue, 05 Jul 2022 16:36:31 +0000

Question

You are given three integers (x,y,z) representing the dimensions of a cuboid along with an integer n .

Print a list of all possible coordinates
- given by (i, j , k) in a 3D grid
- where the sum of i+j+k is not equal to n.
- i.e. can be greater than or smaller than n
Here 0<=i<=x; 0<=j<=y; 0<=k<=z
Please use list comprehensions
Print the list in lexicographic increasing order.

Example

x = 1
y = 1
z = 2
n = 3

All permutations of (i, j, k) are:

[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], [0, 1, 2], [1, 0, 0], [1, 0, 1], [1, 0, 2], [1, 1, 0], [1, 1, 1], [1, 1, 2]]

Print an array of the elements that sum of i, j, k does not equal to n (The required output)

[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 2]]

My solution

code

    # make list of all x,y and z possible number
    x = int(input())
    y = int(input())
    z = int(input())
    n = int(input())
    x = [i for i in range(x+1)]
    y = [i for i in range(y+1)]
    z = [i for i in range(z+1)]
    # for each combination of i,j,k will form a sublist in the final_list, and sum of i,j,k will not equal to n
    final_list = [[i,j,k]for i in x for j in y for k in z if (i+j+k)!=n]
    print(final_list)

My reflection

The first time to try problem need to obtain variable form standard input
good exercise.
The first time to use multiple for loop in list comprehension.

Credit

challenge on hackerrank

Python Exercise 20:Find the pattern

HHMathewChan — Mon, 04 Jul 2022 08:26:09 +0000

Question

Given a dictionary containing up to six phrases,
- return a list containing the matching phrases according to the given string (p).
Ignore any digit that is placed after or before the given string.
Whether the first letter is capitalized or not,
- if all letters of the word match the given string (p), it is valid.
If it does not match the given string (p) then None.

Example

example 1

find_pattern({
  "Phrase1": "COVID-19 is no good",
  "Phrase2": "COVID-18 is no good",
  "Phrase3": "COVID-17 is no good"
}, "COVID-19")

➞ ["Phrase1 = COVID-19", "Phrase2 = None", "Phrase3 = None"]

example 2

find_pattern({
  "Phrase1": "Edabit is great",
  "Phrase2": "Edabit is very great",
  "Phrase3": "Edabit is really great"
}, "really")

➞ ["Phrase1 = None", "Phrase2 = None", "Phrase3 = really"]

My solution

algorithm

>>get the value of each Phrase
>>separate the the value into a list by white space 
>>store each separated value into list
  the list name from phase1_list to phase6_list
>>check if the given string (p) appear in the each phrase
  for phrase1 to phrase 6:
      if the given string (p) appear in the phrase value
      add that phrase and value into one string
      add that string to the final list
>>return a final list

code

def find_pattern(dictionary: dict, string_p: str) -> list:  
    prefix = "Phrase"  
    counter = 1  
    final_list = []  
    for sentence in dictionary.values():  
        if string_p in sentence:  
            final_list.append(f"{prefix}{counter} = {string_p}")  
        else:  
            final_list.append(f"{prefix}{counter} = None")  
        counter += 1  
    return final_list

Python Exercise 19:advanced list sort

HHMathewChan — Sun, 03 Jul 2022 10:58:53 +0000

Question

Create a function that
- takes a list of numbers or strings
- and returns a list with the items from the original list stored into sublists.
- Items of the same value should be in the same sublist.
The sublists should be returned in the order of each element's first appearance in the given list.

Example

advanced_sort([1,2,1,2]) -> [[1,1],[2,2]]
advanced_sort([2,1,2,1]) ->  [[2,2],[1,1]]
advanced_sort([3,2,1,3,2,1]) -> [[3,3],[2,2],[1,1]]
advanced_sort([5,5,4,3,4,4]) ->  [[5,5],[4,4,4],[3]]
advanced_sort([80,80,4,60,60,3])-> [[80,80],[4],[60,60],[3]]
advanced_sort(['c','c','b','c','b',1,1])-> [['c','c','c'],['b','b'],[1,1]]
advanced_sort([1234, 1235, 1234, 1235, 1236, 1235])-> [[1234, 1234],[1235, 1235, 1235],[1236]]
advanced_sort(['1234', '1235', '1234', '1235', '1236', '1235'])-> [['1234', '1234'],['1235', '1235', '1235'],['1236']]

My solution

algorithm

>>separate the original list to different sublist
  initialist a empty list: new_list 
  add the first number of orginal list into new_list
  for each number in the original list:
    if number equals to the first element of any sublist:
        add number to that sublist
    else:
        add number to an new empty sublist

code

def advanced_sort(original_list: list) -> list:  
    # create a list with the first element of the original_list  
    new_list = [[original_list[0]]]  
    for index, item in enumerate(original_list):  
        if index == 0:  
            continue  
        not_added = True
        # To iterate over every sublist in the new_list
        for sublist_index, sublist in enumerate(new_list):  
            # try:  
            # if item is the same with first element of the sublist of new list and not already added            
            if item == sublist[0] and not_added:  
                # add item to that sublist  
                sublist.append(item)  
                not_added = False  
            # if no same item appear after checking the whole new list and not already added  
            if item != sublist[0] and sublist_index == len(new_list) - 1 and not_added:  
                # add the item the end of the new_list  
                new_list.append([item])  
                not_added = False  
    return new_list

My reflection

about while loop
- the loop will not instantly end when the boolean condition is changed to false
- need to use if condition to control the execution of code
Just admire people can write short code in elegant way

Credit

challenge on edabit

Python exercise 18:Sales Season

HHMathewChan — Mon, 27 Jun 2022 08:02:48 +0000

Question

A retailer is having a store-wide "buy 2, get 1 free" sale.
For legal reasons, they can't charge their customers $0 for an article
- so a discount is applied to all products instead. - --
Create a function that takes in a list of prices for a customer's shopping cart
- and returns the prices with the discount applied.
- Round all prices to the cent.

Example

For example, if a customer gets three products a, b and c:

Product A	Product B	Product C
$15.99	$23.50	$23.50

She gets the cheapest one for free, so she ends up paying $15.99 + $23.50 = $39.49, but what her receipt says is:
Product A: $15.99 − Special Discount = $12.57
Product B: $23.50 − Special Discount = $18.47
Product C: $10.75 − Special Discount = $8.45
Total: $39.49

My solution

algorithm

>>calculate the original price of all the products
  initialise a variable called original_total
  original_total = sum of the shopping cart
>>calculate the discount given in percentage
>>>determine how many product should be free
   free_product_number  = length of shopping cart // 3
>>>calculate the total price of the free product
>>>>find the lowest (numbers_of_free_product) price in the shopping cart
    initialise a free_product list
    while length of free_product list is not equal to free_product_number:
        for product in shopping cart:
            lowest_product = min(shopping cart)
            add the lowest_product to free_product list
            delete the lowest_product
   initialise a variable called discount_given
   discount_given = sum of the free_product list
>>>calculate the discount percentage
   discount percentage = 1-(discount_given / original_total)
>>return the list of all product price with discounted applied
  initialise a discounted_list
  for each product in the shopping cart:
      new_price = product * discount percentage
      then round the new_price to 2 decimal place
      store the new_price to the discounted list
  return the new_list

code

def discount(shopping_cart: list):  
    copy_of_shopping_cart = shopping_cart.copy()  
    # >>calculate the original price of all the products  
    original_total = sum(shopping_cart)  
    free_product_number = len(shopping_cart) // 3 
    # >>>calculate the total price of the free product  
    #    find the lowest (numbers_of_free_product) product in the shopping cart    free_product_list = list()  
    #  set up a loop for free_product_number times:  
    while len(free_product_list) < free_product_number:  
        free_product = min(copy_of_shopping_cart)  
        free_product_list.append(free_product)  
        # remove the lowest product in the shopping cart, so the next lowest product can be found  
        copy_of_shopping_cart.remove(free_product)  
    # calculate the total prise of the free item  
    discount_given = sum(free_product_list)  
    discount_percentage = 1 - (discount_given / original_total)  
    # >>return the list of all product price with discounted applied  
    discounted_list = list()  
    # applied discount to each product in the original list , round to 2 decimal place and add to discounted_list  
    for product in shopping_cart:  
        discounted_product = product * discount_percentage  
        discounted_list.append(round(discounted_product, 2))  
    return discounted_list

My reflection

I have learned a new way to solve the find lowest item in the list by using sorted()function and slicing method
seem like my code are very long compare to other, need to practice more the shorten code.

Credit

challenge find on edabit

Python exercise 17: convert number to english word

HHMathewChan — Sun, 26 Jun 2022 10:19:19 +0000

Question

Write a function that accepts a positive integer between 0 and 999 inclusive and returns a string representation of that integer written in English.

Example

num_to_eng(0) ➞ "zero"

num_to_eng(18) ➞ "eighteen"

num_to_eng(126) ➞ "one hundred twenty six"

num_to_eng(909) ➞ "nine hundred nine"

My attempt

algorithm


  initialise a dictionary with number as key and zero to nine as value
  initialise a dictionary with number as key and ten to ninety as value
 >>determine the value of the number
>>>if number is betwen 0 and 9 inclusive
    return the equivalent word
>>>if number is betwen 10 and 20 inclusive
    return the equivalent word
>>>if number is between 21 and 99 inclusive:
   find the remainder of number divide by 10
>>>>if remainder is zero
    return the equivalent word
>>>>if remainder is not zero
    return the equivalent prefix for the first digit
    return the equivalent word for the second digit
    concatenate them to a string
>>>if number is between 100 to 999 inclusive:
   find the remainder of number divide by 100
>>>>if remainder is zero
    return the equivalent word
   return the equivalent prefix for the first digit
   return the equivalent prefix for the second digit
   return the equivalent word for the third digit
   concatenate them to a string

code(has modified a lot from the above algorithm)

def num_to_eng(number: int):  
    def convert_0_to_20(number_0_to_20: int):  
        direct_convert = {0: "zero",  
                          1: "one",  
                          2: "two",  
                          3: "three",  
                          4: "four",  
                          5: "five",  
                          6: 'six',  
                          7: "seven",  
                          8: "eight",  
                          9: "nine",  
                          10: "ten",  
                          11: "eleven",  
                          12: "twelve",  
                          13: "thirteen",  
                          14: "fourteen",  
                          15: 'fifteen',  
                          16: "sixteen",  
                          17: "seventeen",  
                          18: "eighteen",  
                          19: "nineteen",  
                          20: "twenty"}  
        return direct_convert[number_0_to_20]  

    def convert_21_to_99(number_21_to_99: int):  
        two_digits_prefix = {20: "twenty",  
                             30: "thirty",  
                             40: "forty",  
                             50: "fifty",  
                             60: 'sixty',  
                             70: "seventy",  
                             80: "eighty",  
                             90: "ninety"}  
        # find the remainder divided 10  
        remainder = number_21_to_99 % 10  
        if remainder == 0:  
            return two_digits_prefix[number_21_to_99]  
        if remainder != 0:  
            return two_digits_prefix[number_21_to_99 - remainder] + " " + convert_0_to_20(remainder)  

    def convert_100_to_999(number_100_to_999: int):  
        two_digit_part = number_100_to_999 % 100  
        first_digit = number_100_to_999 // 100  
        if two_digit_part == 0:  
            return convert_0_to_20(first_digit) + " hundred "  
        if two_digit_part != 0:  
            # if two_digit_part <20 , there will be error  
            try:  
                return convert_0_to_20(first_digit) + " hundred " + convert_21_to_99(two_digit_part)  
            except:  
                # for two_digit_part <20 , call another function at the end  
                return convert_0_to_20(first_digit) + " hundred " + convert_0_to_20(two_digit_part)  

    if number < 21:  
        return convert_0_to_20(number)  
    if 20 < number < 100:  
        return convert_21_to_99(number)  
    if 99 < number < 1000:  
        return convert_100_to_999(number)

My reflection

It turns out that my solution has a lot different from what i coded, as i feel it would be too much similar code if I stick to the original algorithm. However, i am quite happy for what I code, I have applied some knowledge that I just learned: define function inside function, call function inside function, error handling. This is a good exercise.

Credit

challenge on edabit

Python Exercise 16: find the highest index alphabet

HHMathewChan — Sat, 25 Jun 2022 09:29:20 +0000

Question

Given a name, return the letter with the highest index in alphabetical order,
- with its corresponding index,
- in the form of a string.
You are prohibited to use max() nor is reassigning a value to the alphabet list allowed.

Example

alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]


alphabet_index(alphabet, "Flavio") ➞ "22v"

alphabet_index(alphabet, "Andrey") ➞ "25y"

alphabet_index(alphabet, "Oscar") ➞ "19s"

My attempt

algorithm

>find the letter with the highest index in alphabetical order
 initialise highest_index to 0
 initialise highest_index_character to empty string
>>Find the highest index of the character and the relevant character in the name
  initialise highest_index to 0
  initialise highest_index_character to empty string
  for each character in the name:
      if character's index in alphabet is higher than in highest_index
      set highest_index to character's index
      set highest_index_character to character
  return string of highest_index and highest_index_character

code

alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u",  
            "v", "w", "x", "y", "z"]  


def alphabet_index(alphabet: list, name: str):
    # The name are in upper case, but alphabet is in lower case
    name = name.lower()  
    # initialise highest_index to 0  
    highest_index = 0  
    # initialise highest_index_character to empty string  
    highest_index_character = str()  
    # for each character in the name:  
    for character in name:  
        #  if character's index in alphabet is higher than in highest_index  
        if alphabet.index(character) + 1 > highest_index:  
            # set highest_index to character's index  
            highest_index = alphabet.index(character) + 1  
            #   set highest_index_character to character  
            highest_index_character = character  
    # return string of highest_index and highest_index_character  
    return str(str(highest_index) + highest_index_character)

My reflection

This takes me long time to write out the algorithm in appropriate formate, need to practice more

Credit

challenge find on edabit

DEV Community: HHMathewChan

Leetcode 2. Add Two Numbers - my solution

Description

Problem definition

The outline of the algorithm

The first part

The second part

The outline of the algorithm

Combined algorithm

Feeling

Reference:

My Solution to Delimiter Soup from kattis

Problem

Input

Output

Limits

My solution

problem definition

Test table

Outline of the algorithm

Algorithm

Complexity

The code

Additional

Source

Python challenge: Leetcode 3. Longest Substring Without Repeating Characters

Question

Example

Constraints:

My attempt

Attempt 1 (fail at last two case, exceed time limit)

Attempt 2 (success)

Other solution

My reflection

Credit

Instruction to install pygraphviz package in Pycharm in MacOs

Environment

Problem

Why this problem happen

Solution that work for me

Step 1. use Homebrew to graphviz package first

Some explanation

Step 2. Provide searching path when install pygraphviz

Credit

Python Exercise 23: Two sum

Question

Example

Constraints:

My attempt

First attempt

Second attempt (success pass all test)

Other solution

Claim to be the fastest algorithm with 0(n) complexity

My reflection

Credit

Python exercise 22: ransomnote

Question

Example

My Solution

Other solution

My reflection

Credit

Python Exercise 21: list comprehensions

Question

Example

My solution

Other solution

My reflection

Credit

Python Exercise 20:Find the pattern

Question

Example

My solution

Other solution

Credit

Python Exercise 19:advanced list sort

Question

Example

My solution

Other solution

Step 1. use Homebrew to `graphviz` package first