Month: February 2015

Problem 052


Project Euler

Permuted multiples

Problem 52

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.


Unbelievably, I was able to do this by hand in less than 30 minutes.

First, the number has to be at least 6 digits to be able to satisfy the criteria because each of the multiples are a permutation of the original number. Since we are looking for the smallest, I start with 6 digits and thinking that I will have to worry about 7 digits later. Turn out the answer is a 6 digits integer.

Next, the first digit must be 1 or it will become 7 digits at 5x if it is greater than 1.

 x: 1 _ _ _ _ _

Now, if we have only 6 digits, and the first digit is 1, the last digit must be 7 because 2,4,5,6,8 will give us a zero at some point for the unit digit which is impossible for a 6 digits integer to start with zero as one of the permutation, and the multiple of 3 or 9 will never produce 1 as the last digit in any of the multiples.

 x: 1 _ _ _ _ 7

In fact, since we know the last digit is 7, we also know that 1,2,4,5,7, and 8 are the digits we must work with because those are the unit digit produced by 7’s multiples. The order of those last digits from 1x to 6x are 7, 4, 1, 8, 5, and 2. We also know that the order of the first digits must be 1, 2, 4, 5, 7, 8 because the first digit must grow in sequence.

 x: 1 _ _ _ _ 7
2x: 2 _ _ _ _ 4
3x: 4 _ _ _ _ 1
4x: 5 _ _ _ _ 8
5x: 7 _ _ _ _ 5
6x: 8 _ _ _ _ 2

Now, working from 1x to 2x, we know that the 2nd digit must not carry because 1st digit must be 2 at 2x. Therefore, 2 or 4 must be the 2nd digit in the original number. We also know that 4 can not be in front of 5, 7, and 8 because 4×2+1 = 9, which is not one of the digit we are working with. In another word, 4 must be in front of 2. Therefore

 x: 1 4 2 _ _ 7
2x: 2 8 5 _ _ 4

Both combination of 5, 8 work from 1x to 2x. However, if the original 5th digit place is 8 and last digit is 7, then it will produce 3×8+2 = 6 at 3x, which is not one of the digit we are working with again. Therefore,

 x: 1 4 2 8 5 7

Continue to multiply x up to 6x will find that this number works and it is the smallest positive integer that works.

Advertisements

Episode 10 – Open-Closed Principle

Clean Code

Episode 10

Episode ten talks about the Open-Closed principle where it is possible for source code to be open for extension but closed for modification.

  • Open and Closed
    • Software module should be open for extension but closed for modification
    • Open for extension means it should be very easy to change the behavior of the module
    • Closed for modification means the source code should not be change
    • Use abstraction and inversion by inserting abstract interface between the high level module and the low level module so that both modules are depend on the abstract interface.
    • Whenever there is a module whose behind you like to extend without modifying it, you separate the extendable behavior behind an abstract interface, and turn the dependency around.
  • Point of Sale Example
  • Implications
    • If a module is open for extension but closed for modification, then each new feature will only need additional new code and not modifying the exiting code.
  • Is this possible?
    • It is hard to be able to completely adhere to open-closed principle
    • The difficulty of conforming to open-closed principle is due to size. Small function, classes and small component are easy to conform but not with larger component.
  • A Smelly Design
  • De-Oderizing the Design
  • The Lie
    • Only protect you from changes if you can predict what they are
  • Two Solutions
  • Big Design Up-Front (BDUF)
    • Think of all possible extension before hand and build the system assuming these extension may be happening.
    • Problem with BDUF is that a major part of the system is unnecessary.
    • Abstraction create indirection and make it hard to follow the call.
  • Agile Design
    • Get a simple design out and then let the customer tell you what need to change and change that. Thus, it is an iterative process with lots of feedback.
    • By understanding what type of change is likely base on the pass changes, we can use the knowledge to predict future changes.
  • Agile Design in Practice
    • In real life, establish basis shape of the system but not over think that implement unnecessary abstraction.
  • Example
  • Reprise
  • References
    • Bertand Meyer, Object-oriented software construction

Episode 09 – Single Responsibility Principle

Clean Code

Episode 09

The ninth episode talks about the Single Responsibility principle.

  • Responsibility
    • Function and module.
    • Best module has only one responsibility
  • It’s about user
    • Responsibility that classes and function has to the user, who will request changes.
    • Responsibility can be view as the sources of change.
    • e.g. Employee class with method calculatePay, save, empolyeeInfo.
      • user for calculatePay maybe from accountants.
      • user for save maybe from DBA if the data is save in the database.
      • user for employeeInfo maybe from people who request the report.
  • It’s about role
    • Avoid coupling software, separate the user of the software from the role they play.
    • When user play a certain role, they are call actor. Responsibility is tied to actor and not to individual.
  • Reprise
    • Responsibility is a family of function serve one particular actors.
  • The two values of software
    • Secondary value is its behavior (no bug, no crashes).  Achieve by meeting the user’s need.
    • Primary value is the ability to change.
  • Friction
  • CM Collision
    • When a software with multiple responsibility is being changed by multiple users, changes would collide.
  • Fan out
    • Multiple responsibility will force the class to use multiple API. Thus, a large fan out is sensitive to changes in large array of API and cause the software its stability.
  • Collocation is coupling
    • When a software with multiple responsibility, changes from one of the users may force all other users calling this module to have to recompile and re-deploy when the changes has nothing to do with them.
  • Encroaching Fragility
    • Changes come from one user in module with multiple responsibility can affect another user when the two users initially share the usage of the same function.
  • SRP
    • Gather things that changes for the same reason and separate things that are not change for the same reason.
  • Invert Dependency
    • Separate the employee class into implementation and interface but the actors are still coupling
  • Extract Class
    • Separate the employee into three classes for each actors. However, its hard to find the right function for an employee class since it is now three different classes.
  • Facade
    • All users are using the facade class which delegate the implementation to different classes (like previously). However, actors still coupled.
  • Interface Segregation
    • Create 3 interface classes but one implementation class (see Invert dependency). Each actor is entirely decouple from the other because each actor uses its own interface. But developer need to hunt for the interface they need (see Extract Class) and implement still coupled because they are in the same implementation class.
  • Welcome to Engineering
    • No one solution fit all, balance the tradeoff.
  • Faking it
    • The episode follows a waterfall development cycle but in fact, it was done using TDD.
  • References

Episode 08 – SOLID Principle

Clean Code

Episode 08

The eighth episode talks about the SOLID principle.

  • The source code is the design
    • The cost of design is expensive for software vs building a software
  •  Design smell
    • Rigidity, Fragility Immobility
  • Rigidity
    • System is hard to change.
    • Reduce build and test time
    • Long build time is a function of coupling
  • Fragility
    • Small change in one module affect another module
    • Manage the dependency in the module and isolate them from each other
  • Immobility
    • Internal component cannot be easily extracted and re-use in new environment
    • Immobility is due to coupling and dependency between the module of the system.
    • Decouple the central abstract in the application from database, UI and framework… etc.
  • Viscosity
    • Necessary operation like build and test, check-in, check-out, merge are difficult to perform and take a long time to execute
    • Exist due to irresponsible tolerance
    • Cause by tight coupling
    • decoupling module and manage remaining dependency
  • Needless Complexity
    • Coding additional needless complexity because anticipating change for the future that are not required
    • Use TDD so code changes in the future can be trusted with tests and no need for needless complexity now. Focus on current requirement.
    • Needless complexity related to tight coupling because we anticipate relationship of modules which currently are not related.
  • Code Rot
  • Dependency Inversion
    • Avoid having the dependency pointing to the same direction of the flow of control
    • Having dependency oppose the flow of control, prevent code rot by preventing application fan out from growing and coupling with low level.
    • Example, C++ v-table for virtual function, polymorphic dispatch mechanism in Java, C# and Ruby.
    • Inverse key dependency by using dynamic polymorphism.
  • What is OO?
    • Dependency inversion
    • Protecting high level policy from low level detail
  • Dependency Management
    • SOLID principle (Dependency related)
      • Single Responsibility Principle
      • Open Closed Principle
      • Liskov Substitution Principle
      • Interface Segregation Principle
      • Dependency Inversion Principle
    • Component Cohesion Principles
      • Release-Reuse Equivalency Principle
      • Common Closure Principle
      • Common Reuse Principle
    • Component Coupling Principle
      • Acyclic Dependencies Principle
      • Stable Dependencies Principle
      • Stable Abstraction Principle
  • References