DEV Community: Justin Chan

Back-Tracking N-queen challenge

Justin Chan — Mon, 26 Jul 2021 03:58:09 +0000

What is backtracking?

Backtracking is a brute-force approach that finds all possible solution. What is brute-force? Brute-force exhaustively analyze the input and constraints to find a specific solution. Basically, backtracking is find the way of your way through a cornfield maze.

How does it relate to a maze in 4 steps?

Enter the cornfield
Take a path. Ex. Left, right
if Dead end, trace back aka "backtrack" to the intersection and explore another path.
Repeat steps 2 and 3 until you find exit.

Explanation

The maze in essence is related to backtracking because we traced back one step and made a different turn to find another possible solution.

More notes about backtracking

Represented in a State-Space Tree
Bounding function is used to add constraints to find the desired solutions. Note: We can have more than one solution in backtracking.
DFS!!!! [DFS = forms a root to child "path" by "path"]

More notes about brute-force

DP is a brute-force approach that finds the maximum or minimum optimal solution.
Branch and Bound is also a brute-force approach that is BFS[form the tree level by level].

Challenge: Solve the n-queen problem

Background

Queen is most valuable piece on the board...actually, the king is most valuable because if you don't have a king, you lose. The queen is the 2nd most valuable piece on the chess board. This piece is able to move diagonally, horizontally, and vertically. Your job is to place 7 queens on a chess board where each queen does not pose any threat to each other.
I have solved this challenge in 10 minutes. Can you beat it?

Steps

Navigate to the link below and have fun: Click on me [https://www.chess.com/analysis]
Click on 'Setup' and 'Trashcan' icon
Have fun!

My Solution

Reference:
Introduction to Backtracking [https://www.youtube.com/watch?v=DKCbsiDBN6c]

Day 2-4: My Driver's Test

Justin Chan — Wed, 07 Jul 2021 00:11:02 +0000

I have been preparing for my driver's test for the past few days. I have practiced more than 50 hours on various maneuvers such as 3-point turns and parking. However, as you would later find out, it would not be enough.

On the exam day, my mother woke me up 1 hour before the big test. She said that we would have to report to the test site early since there were already other vehicles lining up. I hurried to brush my teeth, get dressed, grab my breakfast. Within 5 minutes, my mother and I were heading out of the door.

When we arrived at the test site, other people were waiting for their turn. Based on my view, approximately six cars were waiting at the location. My mother parked the car behind the last queued car. We switched seats since I would be taking the road test.

As time passed by, each vehicle left with the examiner. We slowly inched closer to the starting point. At some point, I was tired of starting my car and moving 3 feet closer for every car that leaves the test site. That was a big mistake on my part. I should have moved closer no matter what the circumstances.

A lady was walking on the sidewalk and speaking on the phone simultaneously. On top of that, she glared at me. In my mind, I was like, "Why are you looking at me like that?" I was completely confused since I didn't know her. It looked like I did something which she would never forgive me. She slowly walked on the empty parking spot in front of me and walk back on the sidewalk. Then a car drove by and intended to park in that spot. In my mind, I had to inch closer to prevent this unforgivable action. Everybody is waiting patiently and these people have to cut the line. The following steps were the actions that I have taken:

Turned on the car
I thought I had the car in drive and pushed on the gas pedal, but the car engine just revved.
Placed the car in Drive and moved forward to prevent the female driver from parking.
The funny thing is these two ladies went out their way to coordinate, but she had to drive to the back of the line.🤣🤣🤣

Back to the story.....
When we were the first one on the line and the examiner approached the car, we gave the name[Justin] and time[8:30 AM]. I thought it was my turn to take the test; only in your dreams! The examiner told us to wait for the next batch of examiners.

So we waited and waited.....

And waited...

A lady examiner approached our car and told us to move closer to the curb. Note that if the car hits the curb, I would fail. As a result, I mumbled to my mother, "Tell me when!" As I was moving closer to the curb, my mother was like "More, more." That gave the examiner a bad impression from the start. She also asked us to wipe everything because of COVID. She stated her script and I stated without thinking, "Can I start?" That probably angered her even more! I feel like she intended to fail me from the start by instructing me to take the most difficult route[Note that no other driver took that route].

My route

All-way stop
A left turn to the narrow street
Right turn at an intersection
Drive through the curvy road
Parking
Right turn
Right turn
3-point turn
3 Right turns
All-way stop
Pull up to the curb
Done

I received the envelope and scored a 70% on the road test. I passed! 🍾🥂 This day was an emotional roaster!

What did I learn?

First Impression Counts!!
Speed up to not impede traffic. I drive at 10 mph when the speed limit is 25 mph.
Check all mirrors before any maneuvers. Ex. Parallel Parking

Day 1: My Leetcode Adventure[2]

Justin Chan — Sun, 04 Jul 2021 10:10:32 +0000

How many problems have I solved? Uno
Leetcode 1920: Build Array from Permutation

*Return same-length zero-based permutation nums array[array of distinct integers from 0 to nums.length-1] in which ans[i] = nums[nums[i]] where 0<=i< nums.length. *

My Answer
This is the first problem I had for the Weekly Contest 248. On top of that, it has been a while since I visited this website. I am starting the grind to secure a job after graduation.

newArr=[]
        for i in range(len(nums)):
            # Calculate the new val
            temp=nums[nums[i]]
            newArr.append(temp)
        return newArr

Better Solution

 return [nums[nums[i]] for i in range(len(nums))]

Even BetterSolution

 return [nums[i] for i in nums]

What I learned?

List comprehensions can reduce code snippets
Sometimes I am extra like finding the same element[Ex. nums[i]] Instead of... newArr=[] for i in range(len(nums)): # Calculate the new val temp=nums[nums[i]] newArr.append(temp) return newArr Do...

return [nums[i] for i in nums]

Leetcode 1921: Build Array from Permutation

*Given monsters arr and speed arr where monster i travels at speed j. You are allowed to kill any monsters starting from minute 0. Keep in mind that monsters are not allowed to be killed in the middle of a minute and only one monster can be killed at the start of the minute. If monster reaches city == start of the minute, you still lose. Return the max numbers of monsters you can kill before the monster reach your city. *

Answer
I had trouble with this question because I was not able to solve it completely with 3 attempts. Every attempt got me closer to the answer.

Attempt 1 = 53/150 Cases passed
Attempt 2 = 105/150 Cases
Attempt 3 = 116/130 Cases

Attempt 1

killed=0
        while dist or sum(1 for d in dist if d<0)>0:
            killed +=1 
            #Remove 1st monster
            dist.pop(0)
            speed.pop(0)
            # Subtract dist and speed 
            for i in range(len(dist)):
                dist[i]-=speed[i]
        return killed

My first approach was to kill the first monster, but it is flawed because the other monsters could be faster. In addition, the second condition[sum(1 for d in dist if d<0)>0] doesn't make sense. It should stop iterating if monster reached the city.
Attempt 2

killed=0
        # print(sum(1 for d in dist if d<=0))
        while dist and sum(1 for d in dist if d<=0)==0:
            print(dist)
            print(speed)
            # print("Killing...")
            for i in range(len(dist)):
                dist[i]-=speed[i]
            print(dist)
            # Remove a monster 
            delMon=[ind for ind,elem in enumerate(dist) if elem <=0]
            delMonInd= delMon[0] if delMon else dist.index(min(dist))
            print("Killed #", killed,", Index:",delMonInd, ", Value:",dist[delMonInd] )
            dist.pop(delMonInd)
            speed.pop(delMonInd)

            killed +=1 
        return killed

2nd approach was to dist-speed and then find all monster that have entered the city and remove 1st occurence. The problem is for the else condition where some monster can advance to the city faster so I can't just remove the monster with the shortest distance.
Attempt 3

killed=0
        while dist and sum(1 for d in dist if d<=0)==0:
            for i in range(len(dist)):
                dist[i]-=speed[i]
            # Remove a monster 
            delMon=[ind for ind,elem in enumerate(dist) if elem <=0]
            special=[]
            for i in range(len(dist)):
                special.append(int(dist[i]/speed[i]))
            # delMonInd= delMon[0] if delMon else self.turnsLeft(dist,speed)
            delMonInd= delMon[0] if delMon else special.index(min(special))
            dist.pop(delMonInd)
            speed.pop(delMonInd)
            killed +=1 

            # print("Killed #", killed,", Index:",delMonInd )
        return killed

3rd approach was to take current result and perform division between distance and speed. This helps resolve the closest monster problem and this is the right approach. However, time exceeded for this approach.
Better Solution

arr=[]
            #Store the minute time for each monster
            for i in range(len(dist)):
                minute=math.ceil(dist[i]/speed[i] )
                arr.append(minute)
            arr.sort()
            killed=0
            #Count number of monster killed
            for m in range(len(arr)):
                if(arr[m]<=m):
                    return killed
             killed+=1
            return killed

This sorting approach is O(nlogn) which is simple and fast. First, it converts to comparable units. Then it sorts to decide which monster to remove during minute m. Remove monsters until monster has reached the city. *
**What I learned?*

How to check array for emptiness? if arr: T else F
How to write a ternary operator in Python? "Y" if T else 'N'
How to move elements from array? .pop()!!!
Condition should be better
math.ceil() vs math.floor()
Reassigning func list has no effect on outside
Include code to main flow--> Transfer to a function
zip(lst1,lst2)--> Create a zip object of tuple pairs from both list