Day 3 Week 7 on JFLAP

  1. minimize DFA

    check for partition completeness fixed: the program no longer alerts the partition is not completed when it is.

    variable minimizedEdges changed to 2D array with node(FAState) as parameters. minimizedEdges[i][j] is an array of characters on the edge from node i to node j

    add trap states before everything so the program can run on incomplete DFAs

  2. Regular Expression

    no unnecessary parentheses are added

  3. FA.js

    right click menu no longer disables dragging

    dragging no longer unhighlights nodes that are originally highlighted

  4. FAEditor

    notify the user about current action: toRE

    regular expression now shows as the title of the page

 

Demo of FA – RE – NFA – DFA – minimize DFA:

Progress on Duke-CSA-iOS

Today I’m gonna take some time to write down my progress for Duke-CSA iOS app development.

This new feature is temporarily named “Q&A”. Duke Chinese students, especially class of 2020 freshmen, can post their questions about Duke student lives, classes, and other stuff on here. Upperclassmen are then able to answer them on the app. Both questions and answers can be voted on, just like Stack Overflow. Users can also comment on answers.

Most of the code for data transfer between the online database and the app was copied from Jay’s earlier work on the app. I also refactored a little bit to make the code cleaner.

Below are some screenshots of the app for now.

Main View: all questions ordered

Detail of a question with all its answers

Detail of an answer with all its comments

compose a new question

The voting buttons are functional but cannot be highlighted for now. I already know the reason is with updating TableViewCell – the button will only update its image when the TableViewCell is reloaded. I will probably be able to fix this tomorrow.

The reply function is used in three places of the app – Event, Rendezvous, and QA, so I made a new file ReplyController and extended this classes in these individual controllers, which made the code much shorter and easier to debug. However, the code structure for Event is a little different so I’ll work on that later.

The other function that Jay and I would like to implement is showing the class database collected by CSA. A search feature would be awesome, too.

Day 2 Week 7 on JFLAP

  1. NFA -> DFA nodes layout bounds fixed
  2. FAtoRE dragging helper lines disappear after adding edges now
  3. in FAEditor clicking on ‘toRE’ will scroll up to jsav msg
  4. FATester, FAFixer scroll down for test results
  5. does not alert to export as soon as the user completes
  6. add check done button for NFAtoDFA
  7. add description feature to exercise generator
  8. make createDFAexercise prettier

pretty create exercise pagePretty create exercise page

Day 1 Week 7 on JFLAP

Today I added a NFA to DFA tool. Before we had this file in exercise format, but now I created a new file with only the converting functions so that FAEditor can use it to convert NFA to DFA. Then I worked on the export of graphs between these files. Now you can start from FAEditor, create an FA, use the FAtoRE button to convert it to regular expression, and export to REtoFA.html, from where you can convert back to NFA and export to FAEditor, and further convert it to DFA and export back toFAEditor, so it’s an ecosystem now, just like JFLAP. I will work on the minimizing proof tomorrow.

LeetCode 274. H-Index

Problem:

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

  1. An easy approach is to sort the array first.
  2. What are the possible values of h-index?
  3. A faster approach is to use extra space.

Solution:

public class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = citations.length;
        for (int i = 0; i < citations.length; i++) {
            if (citations[i] >= h) return h;
            h--;
        }
        return 0;
    }
}

LeetCode 125. Valid Palindrome

Problem:

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Solution:

Reading the question statement thoroughly is so important. I forgot about numeric values.

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null){
            return false;
        }
        if (s.length() <= 1) {
            return true;
        }
        s = s.toLowerCase();
        int low = 0;
        int high = s.length() - 1;
        while (low < high){
            char c1 = s.charAt(low);
            char c2 = s.charAt(high);
            boolean v1 = ('a' <= c1 && c1 <= 'z') || (48 <= c1 && c1 <= 57);
            boolean v2 = ('a' <= c2 && c2 <= 'z') || (48 <= c2 && c2 <= 57);
            if (!v1) {
                low++;
                continue;
            }
            if (!v2) {
                high--;
                continue;
            }
            if (c1 != c2) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
}public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null){
            return false;
        }
        if (s.length() <= 1) {
            return true;
        }
        s = s.toLowerCase();
        int low = 0;
        int high = s.length() - 1;
        while (low < high){
            char c1 = s.charAt(low);
            char c2 = s.charAt(high);
            boolean v1 = ('a' <= c1 && c1 <= 'z') || (48 <= c1 && c1 <= 57);
            boolean v2 = ('a' <= c2 && c2 <= 'z') || (48 <= c2 && c2 <= 57);
            if (!v1) {
                low++;
                continue;
            }
            if (!v2) {
                high--;
                continue;
            }
            if (c1 != c2) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
}

Day 5 Week 6 on JFLAP

Today is the day I give up refactoring grammar. I changed the files back to its state and deleted the files I added. The functions and variables are hopeless. I don’t understand how one could continue adding code to this already relentless and magically working code. From next week I will focus on creating exercises models and exercises question generators instead of refactoring. I read some book chapters about refactoring methodologies and a paper about algorithm visualization softwares in the afternoon. The book is very useful and provided me some insights about refactoring. Sadly I’m not doing it again.

LeetCode 123. Best Time to Buy and Sell Stock III

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Do it DP front and back.

public class Solution {
    int[] pre;
    int[] post;
    
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        pre = new int[prices.length];
        post = new int[prices.length];
        
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            pre[i] = prices[i] - min > pre[i-1] ? prices[i] - min : pre[i-1];
        }
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            if (prices[i] > max) max = prices[i];
            post[i] = max - prices[i] > post[i+1] ? max - prices[i] : post[i+1];
        }
        
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            int p = pre[i] + post[i];
            if (p > profit) profit = p;
        }
        return profit;
    }
}

LeetCode 53. Maximum Subarray

Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Solution:

DP

public class Solution {
    int[] end;
    public int maxSubArray(int[] nums) {
        end = new int[nums.length];
        if (nums.length < 2) return nums[0];
        end[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int connect = end[i-1] + nums[i];
            int alone = nums[i];
            end[i] = connect > alone ? connect : alone;
        }
        int max = end[0];
        for (int i = 1; i < nums.length; i++) {
            if (end[i] > max) max = end[i];
        }
        return max;
    }
}

LeetCode 121. Best Time to Buy and Sell Stock

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Solution:

Simple DP. Save the current min.

public class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            max = prices[i] - min > max ? prices[i] - min : max;
        }
        return max;
    }
}