ThoughtWorkshop

Time 2020-11-04 02:03:19

Web Name: ThoughtWorkshop

WebSite: http://timnew.me

ID:104134

Keywords:

ThoughtWorkshop,

Description:

BackgroundCollection must be the most commonly used data model in programming. And there are a number of data structure that represents collection in memory, in which Array and Liked List must be the most well known ones.When dealing with collection, filtering must be one of the most widely used operation being used. Such as find item(s) satisfies specific criteria from the collection. Although filtering is used a lot, but it isn’t actually a simple or easy operation to apply, especially dealing with tremendous data volume.In fact, there are a number of derived topics about collection filtering, which is impossible to cover them all in the article. This article will focus on bit operation, probably a not widely known but really interesting topic to introduce.Problem: Find the missing integerProblemSuppose there is a collection of integers L.Name the collection that contains integers from 1 to N as GThen L contains all the elements of G except one number x.Items in L are in random order.Find x.TIP: This problem be too easy to experienced developers and algorithm hackers. But it is a good opening words to the following 2 problems in this series. Also it reveals the core concept of some other advanced technologies, such as CRC or bloom filter.When got this problem, the very intuitive(means do it manually by human being) idea is to compare the elements in L and G, find each element in L and remove it from G, then the only left item in G is x.Here is the code:12345678910# @param Integer[] L# @param Integer N# @return Integer xdef find_missing_x(L, N) G = [*(1..N)] # Create G with all integers from 1 to N L.each |i| G.delete(i) # Traverse L, and remove each item in L from G return G.last # Return the only rest item from GendWell this is a work but brute algorithm, which is not efficient in both time and space:Instantiate G means it has space complexity NFind and remove i from G means it has time complexity at O(N*Log(N))Yes, the algorithm can be optimized, with bit operation. In fact the problem can be resolved with time complexity O(N) and space complexity O(1).Exclusive-Or OperationExclusive-Or(Or XOR for short, written as ^ in this article) is a basic bit operation, here is an Venn Diagram explains it:XOR is an important bit operation because it has following interesting features:A ^ B = B ^ A (aka Commutativity)(A ^ B) ^ C = A ^ (B ^ C) (aka Associativity)A ^ A = 0A ^ 0 = ACommutativity and Associativity ensure that XOR can be used despite of order. The 3rd and 4th feature establishes a critical position for XOR in cryptology and encoding.Solution: with XORBy making use of XOR, previous problem can ben resolved in a much more graceful way:Given y is the xor result of all items in GAnd z is the xor result of all items in LThen x = y ^ z123456789101112# @param Integer[] L# @param Integer N# @return Integer xdef find_missing_x(L, N) x = 0 # Set x to 0, since A ^ 0 = A (1..N).each |i| x ^= i # Calculate the xor result for G L.each |i| x ^= i # Keep xor all elements in L return x # Return the only rest item from GendLet’s prove it mathematically:1234567Given x'= y ^ zThen x' = (n1 ^ n2 ^ n3 ^ ... ^ x ^ ... ^ nN) ^ (n1 ^ n2 ^ n3 ^ ... ^ nN)Since ^ obeys commutativity and associativityThen = (n1 ^ n1) ^ (n2 ^ n2) ^ ... ^ (nN ^ nN) ^ xAs n ^ n = 0 and n ^ 0 = nThen x'= 0 ^ 0 ^ ... ^ 0 ^ x = xActually the code can be more concise by using reduce, with 2-lines of code12345678# @param Integer[] L# @param Integer N# @return Integer xdef find_missing_x(L, N) x = (1..N).reduce( :^) # Calculate the xor result for G L.reduce(x, :^) # Keep xor all elements in L and returnendOr C version:123456789int find_missing_x(long N, long* L) long x = N; for(long i = 0; i N - 1; i++) // L has size of N-1 x ^= i ^ L[i]; return x; Extending problemsSo far the problem has been gracefully resolved. But it is yet the end, here is a couple of extending questions:If G is collection with random but unique numbers (Not continues integer from 1 to N). How to write the code?Based on 1, if there are 2 numbers are missing? How to find them both?Based on 1, but L contains the members from G except xfor exactly 2 times. That means L might contain 0 or 1 x, but exactly 2 for any other members from G. How to find x?Based on 1, but G isn’t a collection of integer, but a collection of web urls. How to find the one missing url?Based on 4, G is a collection of url, L is subset of G (might contains fewer members other than exactly N - 1). How can we know a randomly picked member from G is absolutely not contained by L. Given the tolerance to mistake on saying a member from G is in L but it doesn’t.These problems will be explained in the following posts. To test the the exception in a rejected promise could be a little bit painful.And Mocha is Promise-friendly, which means it fails the test if exception is not caught.So as a result, here is a simple code example to explain how it is being done:123456789it 'should throw session-expired exception' new Session().generateId().bindUserFromRedis() .then - null .catch (ex) - ex .then (ex) - expect(ex).to.be.instanceof(ResponseError) .and.that.have.property('errorName', 'session-expired')Update: A Chai Plugin can mitigate the pain12345it('should throw session-expired exception', () = return expect(new Session().generateId().bindUserFromRedis()) .to.evetually.rejected .and.that.have.property('errorName', 'session-expired') )Update 2: With async, it can be converted into normal test12345it('should throw session-expired exception', () = return expect(async () = await new Session().generateId().bindUserFromRedis()) .to.throw .and.that.have.property('errorName', 'session-expired') ) EventBus is an special Publish Subscribe Pattern implementation. EventBus enable message to be delivered between components without requiring the components to register itself to others.Comparing EventBus to other Pub Sub implementations, EventBus is:Designed to replace the original event distribution system, which requires the components register itself to each other.Not designed for general use, EventBus adds additional complexity and runtime overhead to the system. So it is not designed to replace normal method calls.Not designed for inter-process communication as some other Pub Sub.EventBus saves Android developers’ lifeWhen developing Android application, I strongly recommend developer to introduce an EventBus library. EventBus from GreenRobot, Otto from Squqre are good solutions. Or even to choose the original EventBus in Guava library from Google.With EventBus, components can communicate with each other without need to hold direct reference of each other. This is very important to avoid app crashes when calling a method on a detached or destroyed component. Usually this kind of issue isn’t that easy to handle due to Android’s over-complicated life cycle management. So even in the worst case that one component is sending message to another component which has been destroyed (which should unregister itself from EventBus on that time), it only triggered a norecipient waring instead of crashing the app.Also with EventBus as intermedia, you can avoid to exposing objects to root activity or application just for registering callbacks on each other. Components are higher cohesion lower coupling.As the result, EventBus saves tons of time to debugging crash, and make your code more readable, maintainble, extensible, and flexible.Abusing EventBus kills your app easily“EventBus is awesome! It is so convenient, so let’s replace everything with event”… This kind of saying is commonly heard from the developers who just realized the benefits from EventBus. Since EventBus is too convenient to use, they tends to replace everything with EventBus.But we mentioned in the introduction of EventBus that EventBus is design to replace traditional event system in Java, and is not designed for general use. Abusing makes your code hard to understand, hard to debug. Long event chain is a common reason that cause of unexpected behavior.Broadcast Event, Command and RequestEventBus is powerful, but can be easily abused. To make a better use of EventBus, I learn a number of EventBus usages, and evaluated the scenario, and summarized out 3 typeical EventBus usage patterns: Broadcast Event, Command and Request.Broadcast EventBroadcast Event is a special kind of event that used by a specific component to broadcast its status updated to other components.DeclarationBroadcast Event should be used when several components cares about the specific component’s status update. So usually Broadcast Event should have more than one recipients or, at least, potential recipients.Broadcast Event should be an immutable data object, so:It is immutable, so once it is created, its status should not changed, which guarantees the equality between recipients.It is data object, so it should not has methods that might change other classes status.It might have methods that helps its consumer to consume the data it contains.It should be declared as a nested static class of publisher.NOTICEIf you thought a Event is “Broadcast Event”, but later you found it has only one recipient, then you might need to consider refact it into a Command or a Request.CommandCommand is a special kind of event that has the ability to update specific object or specific type of objects. In most cases, Command should have only one recipient. In some special cases, it might has a group of recipients with exactly same type.Precisely, the latter case is a variant of Command pattern, Batch Command, which works as same as Command but have multiple recipients so it can update multiple instances in a batch.Command should be a immutable object that able to update specific object, so:It should have 1 execute method with 1 parameter, which represents the target that the command updates.When invoking execute method shouldn’t change its own status, so it does exactly same thing when applying it to multiple targets.It behavior should be stable across time, so its behavior won’t change when it is apply asynchronously.The object that execute method accepts is not necessarily to be the recipient. It could be the object that recipient holds or it has access to.It should be declared as nested static class of the recipient.If recipient accepts multiple events, these events are recommended to derived from the same base class. So The recipient could subscribe to the base class, rather than every command.NOTICECommand can be seen as recipient’s special method that can be invoked without known recipient instance. So its behavior should fully contained in the class. The subscribing method on recipient should contain one line of code to invoke execute method on command.RequestRequest is a special kind of event that has the ability to accept data from another object. If the request has multiple recipients, to avoid ambiguous behavior, there should be only one of Request‘s respond the request.But there is one exception, that is for the request collects data from multiple objects, multiple objects might respond to the request. This special kind of Request is called Collector.Request should be a object that accept data from recipient, so:It should have respond method with 1 parameter, which represents the data the request asks for.Request should contains enough information for the recipients to determine whether to respond the request.The recipients should check request’s status to determine whether it should respond request.The request can update the publisher directly in the respond methodIt should be declared as nested class of publisher. If possible, also declare it as static, which will be helpful to simplify the tests.Request might has methods to help recipient to determine whether to respond the request.NOTICERequest can be seen as a special method that publisher exposes to a specific recipient, so the specific recipient can invoke the method to provide data. For Request, you might need to aware that that sometimes request might not found proper recipient to respond. If the responder is not guaranteed to exist, then the publish to watch out no-recipent warning from EventBus.In android, view hierarchy usually are created via layout xml file. In the file, to instantiate a TextView we write:1234 TextView android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="Sample 1" / Usually, we need to specify the visual of the TextView, so we keep adding attributes to the TextView element:123456789101112 TextView android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="Sample 1" android:background="@drawable/category_indicator_background" android:gravity="center" android:maxLines="1" android:paddingBottom="12dp" android:paddingLeft="22dp" android:paddingRight="22dp" android:paddingTop="12dp" android:textSize="12sp" / Usually to fully customize visual representation of a view needs a lot of attributes and resources. Such as in this example. we added background, gravity, maxLines, padding and textSize, which is a lot of code.And if we want to create another TextView with exactly same visual representation, we need to copy all the values again:12345678910111213141516171819202122232425 TextView android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="Sample 1" android:background="@drawable/category_indicator_background" android:gravity="center" android:maxLines="1" android:paddingBottom="12dp" android:paddingLeft="22dp" android:paddingRight="22dp" android:paddingTop="12dp" android:textSize="12sp" / TextView android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="Sample 2" android:background="@drawable/category_indicator_background" android:gravity="center" android:maxLines="1" android:paddingBottom="12dp" android:paddingLeft="22dp" android:paddingRight="22dp" android:paddingTop="12dp" android:textSize="12sp" / Obviously, in this piece of code, there are a lot of duplications. We need to compare all the values to figure out the 2 TextViews have the same visual. If we want to change the style, we need to update 2 TextViews. And the last, if we want to create the 3rd TextView or even more ones, we need copy the code again and again, which makes the issue become more troublsome.In a short word, the code has bad readability, bad maintainability, bad reusability. In the book Refactor, we know that code redundancy is bad smell. To mitigate the issue, we need to extract the shared code into another “unit”, and replace all the occurrences with the reference.In Android layout xml, the extract “unit”, which represents the shared attributes, are called Style. After introduced Style, we have:1234567891011 TextView android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="Sample 1" / TextView android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="Sample 2" / 12345678910111213 resources style name="TextView.Customized" item name="android:gravity" center /item item name="android:background" @drawable/category_indicator_background /item item name="android:paddingLeft" 22dp /item item name="android:paddingRight" 22dp /item item name="android:paddingTop" 12dp /item item name="android:paddingBottom" 12dp /item item name="android:textAppearance" @style/CategoryIndicator.Text /item item name="android:textSize" 12sp /item item name="android:maxLines" 1 /item /style /resources Well, this is the basics about the Style: why we need it and how it is used. This post is Walkthrough to the game UntrustedThe game introduction is available here: Awesome geek game UntrustedLevel 1: cellBlockAWell, you are trapped in a box. And you need to move yourself to the exit (blue squre).Before you can do anything, you need to pick the computer first, then you will be access to the source code interface.Once you got the computer, you can figure out the code that generates the walls.Remove the code that generate the wall! And press Ctrl+5 to apply it.Level 2: theLongWayOutWell, you have learn the trick from Level 1, but it doesn’t work anylonger this time. You need to figure out a new apporach.Don’t try to find a path in the maze, there is no such solution.You cannot change the maze created, but you can do something to it before it is deployed.You have learn how to create it for specific size. Why not create another smaller one that doesn’t trouble you?!A maze with size (0,0) is not possible, try a more realistic one, such as (3, 3) or (4, 4).Exit is blocked completely. Do think about to break the wall, that is impossible.Who said there can be only 1 exit per level?!Create a new exit at a different location! You can learn the code form existing one.Level 3: validationEngagedWell, again, validateLevel is introduced, which prevents you to replay the old tricks. So you cannot create or remove objects on the fly this time.Since you cannot create or remove objects this time, but you still can move objects.Move one of the wall away to make a gap between the wall.Level 4: multiplicityYou cannot move wall this time, what will you do?Well, this is just a mindset trap. Forget about moving stuff aroud.There is no validateLevel in this level.What you did in level 2.Just create a exit in the box.Level 5: minesweeperRemember the favous game in Windows? Try it here.The issue here is that the mine cannot be distinguished.Mark the mine with a color other than red.You can change block block color by call setSquareColor.Level 6: drones101A killing drone? Keep away from it.Well, check moveToward, the logic is actually very dumb.It always, move up and down if the x offset is larger than y offset.It will not move, it the intented direction is blocked.Move right first, then move down when you at the same col as the drone and block. Then move right, the drone will not follow you.Level 7: colorsA phone to make call? Great idea!Pick up the phone, then press qThe callback will be executed everytime you pressed qRotate your color in the callbackLevel 8: intoTheWoodsGo across the forest from the left to the right!In this level, there is very little code that you can change!Press qThe only code you can change is the callback function nameAll the functions that you can call are in the functionListGenerate a new forest, when you press qMove right as far as you can; Once you are blocked, press q to generate a new forest, the move.Repeat move and generate forest untill you reach the exit.Level 9: fordingTheRiverWell, a self driven raft, the raft comes to pick you up.BTW, I really love the BG music of this level.The raft direction is stored in variable raftDirection.Change the raftDirection to up, will make the raft move up each turn.Find a chance to override the value of raftDirection.Write a function that registerd as phone call back with API setPhoneCallbackGo to the raft, after boarding the raft press q to execute callback, then move up.Level 10: ambushWell, this time, there are a dozen of drones are on your way. You need to figure out a possible to get rid of them as fast as you can.Don’t try to run away as what you did in Level 6. It is a different scenario.Try to change the drone behavior.To apply the same logic to 3 kinds of drones might not be a good idea.Move attak drones away from the row you’re in.Move the Defence Drones away from the row you’re in.Ask Reinforcement Drones to stay at the place.Level 11: robotThis time, there is very little thing about you. It is about the robot.“Hit and turn” should be smart enough for the puzzle.Move forward, when hit something, turn 90 deg.Use me.canMove to test the hit.Since there just 2 states, a boolean should be enough to represent the state.Level 12: robotNavWell this time, it goes a little complicate.“Hit and turn” won’t work here.Path seeking algorithm is way too complicate for this puzzle.Robot should be able to be “programmed”.An instruction system should be enough for the puzzle.Preset the instruction to the robot, and ask robot to execute it step by step.Level 13: robotMazeWell, Well, Well, it upgraded again. More intelligence is needed.Maze is randomly generated, so fixed instruction sequence won’t work any longer.Again, Path seeking algorithm is way too complicate for this puzzle.Don’t waste your intelligence.A lot of robot can be “controlled” remotely.Try to teach the robot how to move by your character’s movement.The robot move down when you’re in last row; the robot move up when you’re in the last 3rd row; the robot try to move to your col when you’re in the last 2nd row.Move into last 2nd row, and the move to most left. Move left and right to control robot move horizontally. Move to last 3rd row or last row when you need to tell robot move up and down.Stay in last row and last 3rd row, and press ‘r’ will move robot up and down continuously.Level 14: crispsContestAgain another maze!The maze is unsolvable, don’t try to solve it.Divide the maze into 5 regions, top left 2 rooms, top right 2 rooms, left 1 room, right 1 room, and bottom 2 rooms.You can hold only one key for each color, or the key will be wastedBecause of restriction(hint.3), left and right regions are meaningless.Region top left, top right, and bottom, enter and exists direction doesn’t matter.Check carefully, a string in the code isn’t locked.The item will be taken away is editable when you pass greenLock.Computer and phone are important items for your further plan.null or undeclared value causes exception.Exception will break the code execution, which blocks you from passing the door.Try to find something exists, but you don’t have yet.The Algorithm ?Level 15: exceptionalCrossingReally a cruel design… Pick how to die? Tricky but interesting!The only thing you can change it the value passed to player.killBy().Try to remember what you encounter in last level.Get some hint from the name of this level.Exception breaks code execution.null is a valid value.Undeclared value causes exception.Level 16: lasersLazer kills different races.NOTICE You might got killed by lazer when you haven’t actually touched it. The reason is that the line isn’t 100% align with the coord is given. And I think it is a BUG than designed by purpose.Lazer representation and collision detection are separated.Remove the drawing logic won’t solve the issue.Lazer only kills the object with different color than itself.Color the lines with the lazer color.Use the phone to update your color.Level 17: pointersThis must be the most problematic level in the game!!!!Since fortune is more important than wisdom in this level!If you’re lucky enough, you might able to clear the level by entering a randomly picked portal.Actually when I play this level for 1st time, I passed without dohing any code work.Well, you can do nothing to the layout, and teleporter links.A path seeking algorithm won’t be helpful for this puzzle.Not all the layout is solvable. That’s why you need some fortune!You’ll be killed immediately if the teleporter is linked to a trap.Try to figure out all the safe links, whose 2 end-points are teleporters.Try to visualize the the safe links.Check API document for new available APIs.Use map.getCanvasCoords to figure out the plot coords for teleporters.Draw lines between safe teleporters.Line drawing code can be found in previous level.Restart the level, if the level is obviously not solvable.The puzzle is unsolvable, if there is no link to the room where exit locatesThe puzzle is unsolvable, if there is no link to the room player is placed.Luck is the key!Level 18: superDrEvalBrosGreat honor to Super Bro.Mario

TAGS:ThoughtWorkshop 

<<< Thank you for your visit >>>

timnew programming code software

Hot Websites