Posts

Showing posts from June, 2020

Rule "Base 10": Be Precise in Your Speech

Image
To a human, 10 is the number of fingers on our hands.  An 8 fingered alien would also number its fingers as 10.  The same can be said for a 16 fingered alien.  The reason is that when we translate to their number system, "10" takes on a new value. Hexadecimal "10" = 16 Decimal "10" = 10 Octal "10" = 8 Binary "10" = 2 In fact "10" is just a universal concept for the base number of your number system.  No matter what number system that may be.  If we were to tell an alien race that we do math in Base 10 they'd either be overjoyed that we use the same system or disappointed that we weren't thoughtful enough to notice that from the user's point of view every number system is Base "10." A better convention would therefore be to name your number system by 10-1, indicating the maximum single-digit value of the system as follows: Hexadecimal F = 15 Decimal 9 = 9 Octal 7 = 7 Binary 1 = 1 Avoiding Miscommunication...

Algorithm as Comedy

Image
  There's a Japanese comedian, 世界のナベアツ, "The World Famous Nabe Atsu," whose entire standup routine is based on variations of the Fizz Buzz algorithm.  You don't have to understand Japanese to get it.  It's mostly physical comedy.  Here's a sample using multiples of 3 and numbers containing 3. Based on his success, there's even a Fizz Buzz idiot calculator. Just for kicks, here are some technology jokes:     Which way did the computer programmer go?      (Data way)      Programming builds character ... arrays .      Why did the computer crash?      (It had a bad driver)     What do programmers do when it gets hot?     (Open Windows)     Where do computers go to dance?     (The disk-o)

Dynamic Programming by Example

Backtracking is a recursive method of performing a depth first search.  Each path is considered until the point it's known not to meet the solution criteria, then the algorithm backtracks to the last branch where the criteria is no longer violated and tries another sub-branch from there.  This proceeds until the solution is found or all possibilities have been exhausted. Dynamic Programming can often provide considerable optimization by reducing pursuit of fruitless branches. Examples: Combination Sum Given a set of positive integer possible values, find all combinations of them that sum to a positive integer target value. Example candidates: [2, 3, 6, 7] target: 7 answer: [[7], [2,2,3]] Backtracking Solution ( casual psuedo-code): We're going to iterate over combinations of the candidate values until we hit one that sums to the target, then add that to the list of answers.  This follows a general pattern for backtracking algorithms.    ...