Programming with Passion Algorithms, Mobile Development, Robotics

Tuesday, June 28, 2016

LeetCode (Algorithms#2) ‒Add Two Numbers

Problem

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution

The solution requires linear time and space, and is pretty straightforward. We perform simple addition as we were taught in elementary mathematics, starting with the smaller digits and carrying a 1 if necessary. The only trick is to do it in one loop which is easy because the digits are provided in reverse order. What if they weren't? Some backwards recursion could do the trick.

Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode res = new ListNode(0);
    ListNode curs = res;
    ListNode cur1 = l1;
    ListNode cur2 = l2;
    
    int sum;
    boolean carry = false;
    while (true) {
        sum = (cur1 == null ? 0 : cur1.val) + (cur2 == null ? 0 : cur2.val) + (carry ? 1 : 0);
        carry = sum >= 10;
        curs.val = sum % 10;
        
        if ((cur1 == null || cur1.next == null) && 
            (cur2 == null || cur2.next == null)) {
            if (carry) {
                curs.next = new ListNode(1);
            }
            break;
        } else {
            curs.next = new ListNode(0);
            curs = curs.next;
            cur1 = (cur1 == null ? null : cur1.next);
            cur2 = (cur2 == null ? null : cur2.next);
        }
    }
    
    return res;
}

Saturday, June 25, 2016

LeetCode (Algorithms#1) ‒ Two Sums

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

The brute force solution searches for the two indices in O(n^2) time. The problem can be solved in O(n) time and space using a hash table, where you simply look at each number x, and query the table for target - x.

Note: Use a HashMap to store indices as the values, with a unique integer hash function. The default function for Java's Integer is sufficient.

Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public int[] twoSum(int[] nums, int target) {
    int[] res = null;
    Map<Integer,Integer> map = new HashMap<Integer,Integer>(nums.length);
    
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    
    for (int i = 0; i < nums.length; i++) {
        Integer j = map.get(target - nums[i]);
        if (j != null && i != j.intValue()) {
            res = new int[2];
            res[0] = i;
            res[1] = j.intValue();
            break;
        }
    }
    
    return res;
}

Thursday, June 16, 2016

Customizing Xcode: Plugins, Code Snippets, and more

When it come's to Apple development, your pretty much stuck with Xcode. As an IDE, it is comfortable, clean, and does a good job at encapsulating Apple's development environment. Although, like most Apple software, you sacrifice some freedom of control for a "better" user experience. Apple developers usually don't bother to configure Xcode beyond the default. And when using Xcode, it is not immediately evident that you have significant control over its look-and-feel, as well as the overall workflow.

For anyone that is remotely interested in improving their productivity with Xcode, I strongly recommend investing some time into configuring this IDE beyond the Apple comfort zone. Between plugins, code snippets, and keybinds, you can become significantly more efficient and comfortable with this IDE.

Note: As of Xcode 8, Apple has unfortunately removed support for plug-ins. The Plugins section was moved to the bottom of the post. We'll see what Apple does in the future as their decision to kill plugins has riled up many developers.

Code Snippets

Code snippets insert code using a shortcut that you define and select via Xcode's autocompletion. This is especially useful for a language like Objective-C which lacks conciseness. Within a snippet, code tags provide you with parameters that you can tab through to add code (e.g. <#code#>). This way, just a couple keystrokes can produce many commonly used lines of code, where you can then tab through to implement the specifics. It is important to not make your code snippets too specific or too general. You can also select the scope in which the code snippet is available, including: All, Class Implementation, Function or Method, String or Comment, etc. Code snippets are created in the Utilities panel of Xcode.


Ever encounter the absurd task of having to configure a scroll view to move content out from under the keyboard? This is a perfect situation for code snippets, which can generate these 140+ lines of code for you with just a few keystrokes. You will never again have to rumage through Apple Docs to dig out this lengthy solution to such a common problem.

Examples:

#pragma mark -
#pragma mark Table view data source

- (NSInteger)tableView:(UITableView *)tableView numberOfRowsInSection:(NSInteger)section {
    return <#num#>;
}

- (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath *)indexPath {
    UITableViewCell *cell = [tableView dequeueReusableCellWithIdentifier:<#(NSString *)#>];
    
    return cell;
}

#pragma mark -
#pragma mark Table view delegate

- (void)tableView:(UITableView *)tableView didSelectRowAtIndexPath:(NSIndexPath *)indexPath {
    <#code#>
}

Other useful snippets

Key Bindings

With Xcode you can configure key binds for any menu item, including those menu items added by plugins. These keybinds are especially useful with navigating Xcode since things can get a cluttered quite easily, especially when working on a Macbook. I recommend setting keybinds to show and hide the three common panels, as well as control the assistant editor. This allows for you to maximize viewing of the text editor, while keeping functionality within individual panels one keybind away. To accompany this method of navigating, the following default keybinds become exceedingly useful:

  • cmd+shift+o to Quickly Open any file in the bundle (or methods, properties, and variables)
  • enter (or click) to open in primary editor
  • alt+enter (or click) to open in the assistant editor
  • cmd+shift+up and down toggles between .h and .m files. (Adding alt toggles in the un-focused text editor)
  • cmd+shift+left and right navigates back and forth between files in a text editor's history. (Adding alt toggles in the un-focused text editor)

(tabs are also available in Xcode with keybinds)

Plugins

One of the hidden capabilities of Xcode are plugins, of which there is little mention in any documentation. A few developers (like those at the Alcatraz.io team) have done great work to expose the plugin framework that Xcode is built on, and to make it easy to utilize for developers.

Plugins are built as bundles in Xcode where they have access to OS X features through libraries like AppKit and Foundation frameworks. These executables are stored in ~/Library/Application\ Support/Developer/Shared/Xcode/Plug-ins as plug-in bundles (.xcplugin extension) where they are loaded at startup of the IDE. The easiest way to manage these plugins is through Alcatraz, a package manager that maintains repositories of packages on github. Simply install Alcatraz, restart Xcode, and press Cmd+Shift+9 to browse and install packages.

Note that Xcode plugins rely on knowing the UUID of the current Xcode installation. If Xcode is updated, this UUID changes and some plugins may stop working. If this happens, you can simply reinstall the plugin, or follow this.

Here are some features that become available with plugins.

Code Formatting with BBUncrustifyPlugin

In my opinion, the most useful plugin, BBUncrustifyPlugin allows you to standardize your code formatting by specifying a ClangFormat or Uncrustify style, and configuring when formatting occurs (either when saving a file, or using a keybind). LLVM's webpage contains extensive documentation on clang-format here. See example below.

Example

.clang-format: (place this in your home directory where BBUncrustifyPlugin will look by default)

AllowAllParametersOfDeclarationOnNextLine: false
AllowShortBlocksOnASingleLine: false
AllowShortIfStatementsOnASingleLine: true
AllowShortLoopsOnASingleLine: true
AllowShortFunctionsOnASingleLine: false
AlignTrailingComments: true
AlignAfterOpenBracket: true
AlignTrailingComments: true
AlignConsecutiveAssignments: true
BinPackArguments: false
BinPackParameters: true
BreakBeforeBraces: Linux
ColumnLimit: 110
IndentWidth: 4
KeepEmptyLinesAtTheStartOfBlocks: false
ObjCSpaceAfterProperty: true
ObjCSpaceBeforeProtocolList: true
PointerBindsToType: false
SpacesBeforeTrailingComments: 1
TabWidth: 8
UseTab: Never

Customized Logging with XcodeColors + CocoaLumberjack

CocoaLumberjack is a simple logging framework that is optimized to give an order of magnitude increase in performance over NSLog. It offers individually configurable and dynamic log levels, as well as the ability to log to multiple outputs simultaneously. When combined with XcodeColors, you gain the capability of using colors in the Xcode debugging console. You can then create your own formatting for log messages at different levels.

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
@interface MGLogFormatter : NSObject <DDLogFormatter>

@end

@implementation MGLogFormatter

- (NSString *)formatLogMessage:(DDLogMessage *)logMessage
{
    NSString *logLevel;
    switch (logMessage->_flag) {
    case DDLogFlagError:
        logLevel = @"E";
        break;
    case DDLogFlagWarning:
        logLevel = @"W";
        break;
    case DDLogFlagInfo:
        logLevel = @"I";
        break;
    case DDLogFlagDebug:
        logLevel = @"D";
        break;
    default:
        logLevel = @"V";
        break;
    }

    NSDateFormatter *df = [[NSDateFormatter alloc] init];
    df.dateFormat       = @"HH:MM:SS";

    return [NSString stringWithFormat:@"%@ %@ <%@> %@",
                                      [df stringFromDate:logMessage->_timestamp],
                                      logMessage->_function,
                                      logLevel,
                                      logMessage->_message];
}

@end

@interface MGLogger : NSObject

+ (void)initLogger;

@end

@implementation MGLogger

+ (void)initLogger
{
    // Enable XcodeColors
    setenv("XcodeColors", "YES", 0);

    // Standard lumberjack initialization
    [DDLog addLogger:[DDTTYLogger sharedInstance]];

    // Add a custom formatter
    [DDTTYLogger sharedInstance].logFormatter = [[MGLogFormatter alloc] init];

    // And then enable colors
    [[DDTTYLogger sharedInstance] setColorsEnabled:YES];

    [[DDTTYLogger sharedInstance] setForegroundColor:DDMakeColor(100, 100, 100)
                                     backgroundColor:nil
                                             forFlag:DDLogFlagInfo];
    [[DDTTYLogger sharedInstance] setForegroundColor:DDMakeColor(160, 160, 160)
                                     backgroundColor:nil
                                             forFlag:DDLogFlagDebug];
    [[DDTTYLogger sharedInstance] setForegroundColor:DDMakeColor(254, 234, 88)
                                     backgroundColor:nil
                                             forFlag:DDLogFlagWarning];
    [[DDTTYLogger sharedInstance] setForegroundColor:DDMakeColor(254, 81, 81)
                                     backgroundColor:nil
                                             forFlag:DDLogFlagError];
}

@end

Themes

Beautify your Xcode editor with themes. These are nothing new to Xcode preferences, but Alcatraz makes obtaining color presets much easier. Simply install themes through the Package Manager, restart Xcode, and select them in preferences:

BladeRunner

eppz!

Vale

More themes here and in Alcatraz.

Extras

ColorSenseRainbow

Display colors within the editor when interacting with UIColor and NSColor objects.

KSImageNamed

Autocompletion of images in the project bundle for [UIImage imageNamed:].

SCXcodeSwitchExpander

Autocompletion of switch statements that generates cases for all enum values.

BBUDebuggerTuckAway

Auto-hide the Debugging Area upon typing.

DerivedData Exterminator

One-click removal of derived data for those times when you encounter some stubborn errors.

XToDo

Maintains a list of TODO comments (as well as FIXME, ???, !!!!)

I hope this information is as useful to other Apple developers as it has been for me. Most other users of Xcode that I've worked with are not aware of these capabilities, and tend to be slightly stubborn when it comes to customizing it. All I can say is, it is not as difficult a task as it may seem and the payoff is great!