-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
808 lines (504 loc) · 37.9 KB
/
index.html
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
<meta charset="utf-8">
<title>Carter's Octopress Blog</title>
<meta name="author" content="Carter">
<meta name="description" content="Container View Controllers I was working on a project recently where I had only one screen which was responsible for performing several different …">
<!-- http://t.co/dKP3o1e -->
<meta name="HandheldFriendly" content="True">
<meta name="MobileOptimized" content="320">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="canonical" href="http://clevin95.github.io">
<link href="/favicon.png" rel="icon">
<link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
<link href="/atom.xml" rel="alternate" title="Carter's Octopress Blog" type="application/atom+xml">
<script src="/javascripts/modernizr-2.0.js"></script>
<script src="//ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<script>!window.jQuery && document.write(unescape('%3Cscript src="./javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
<script src="/javascripts/octopress.js" type="text/javascript"></script>
<!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.googleapis.com/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.googleapis.com/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
</head>
<body >
<header role="banner"><hgroup>
<h1><a href="/">Carter's Octopress Blog</a></h1>
<h2>A blogging framework for hackers.</h2>
</hgroup>
</header>
<nav role="navigation"><ul class="subscription" data-subscription="rss">
<li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
</ul>
<form action="https://www.google.com/search" method="get">
<fieldset role="search">
<input type="hidden" name="q" value="site:clevin95.github.io" />
<input class="search" type="text" name="q" results="0" placeholder="Search"/>
</fieldset>
</form>
<ul class="main-navigation">
<li><a href="/">Blog</a></li>
<li><a href="/blog/archives">Archives</a></li>
</ul>
</nav>
<div id="main">
<div id="content">
<div class="blog-index">
<article>
<header>
<h1 class="entry-title"><a href="/blog/2014/07/28/container-controllers/">Container Controllers</a></h1>
<p class="meta">
<time datetime="2014-07-28T09:04:16-04:00" pubdate data-updated="true">Jul 28<span>th</span>, 2014</time>
</p>
</header>
<div class="entry-content"><p>Container View Controllers</p>
<ul>
<li>I was working on a project recently where I had only one screen which was responsible for performing several different tasks. As I programmed, this screen’s view controller file quickly became massive and hard to read. Looking for a solution to this problem I came across container view controllers. Container view controllers allow you to separate the logic of a view controller and smaller more modular chunks. As of iOS 6 you can now drag out a container view object onto your storyboard. The container will effectively create a window to another view controller. You will then be able to create another view controller subclass where you can put all the logic for that separate view. A view controller can have any number of container view’s inside of it. Each of these nested view controllers are considered children of the the parent view controller.</li>
</ul>
<p>Important features:</p>
<ul>
<li><p>Parent and child controllers connected by embedded segue:
The segue connecting the parent and children view controllers are called “embedded segues.” Embedded segues are fired immediately when the app starts so if you need to pass information from the parent controller to a child controller you can ether call the childviewcontrollers property on the parent controller, or you could also make the child view controller a property of the parent view controller and assign it in the prepare for segue method.</p></li>
<li><p>View did load of child view controllers runs before view did load of parent
Another important feature of child view controllers is that their view did load methods are called before the view did load of the parent view controller. This means that if you want to access the parent view controller inside the view did load method of a child controller by calling the “parent viewcontroller” property it will return null. If you need to access the parent view controller you will have to do so after the lifecycle has completed.</p></li>
<li><p>Must change background color to “clear color” for transparency
Another helpful tip that gave me some trouble while working with container view controllers was making the view see through to the background of the parent view. For this I realized that change the alpha of the container view would make every thing in the child view transparent. What I realized is that you need to make both the background color of the container view and the child view “clear color”</p>
<p> Overall container view controllers are great for making seamless transitions while still retaining the same background view and logic. I was able to make my app much more modular and easy to read by breaking up each individual function into a distinct controller. Here is a picture of my storyboard before and after I broke it up:</p></li>
</ul>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2014/07/13/the-magic-of-parse/">The Magic of Parse</a></h1>
<p class="meta">
<time datetime="2014-07-13T20:06:31-04:00" pubdate data-updated="true">Jul 13<span>th</span>, 2014</time>
</p>
</header>
<div class="entry-content"><p>Recently I ran into a pretty common road block for most begginer iOS developers; I wanted to share information between a comunity of users but only knew how to save information using core data. After doing some reading I discovered that what I would need was some kind of cloud database to which I could push data and then pull back down later. Luckly I came across a great service called parse, which essentially abstracted all the complexities away from cloud based storage and turned it into a few lines of easy to read objective C code. With parse I was able to easily save oobjects to cloud and then pull them back down with simply one line query requests. Using parse I was able to create user acounts with distinct information and have users make posts that could then be view by other users remotely. While parse is great and free up untill your getting 3 requests per second (which is a ton) I didnt feal comfortable with having so much ‘magic’ in my app. I decided to dig deaper to get a better understanding of what was going on behind parse.</p>
<p>After diging deaper into cloud based storage I was able to break down the procces of creating your own cloud backend into three distinct phases. The first step is to build a web app which you can hit remotely with an api. To do this you’ll need to learn the basics of a web framework such as ruby on rails or node.js. This app will have to be set up to receive POST requests contaiing the data you would like to save and also handle GET requests which will return the information specified in the url. After you’ve set up your app you can push it to a cloud hosting platform such as Heroku or Engine Yard. Next, you’ll need to set up a web database. When it comes to the details of what makes certain batabases preferable to others I have very litle insight. I’ve looked around an found a few blogs with highlight the different features of the major databases. Here is one verry good resourse I came accross:
<a href="http://kkovacs.eu/cassandra-vs-mongodb-vs-couchdb-vs-redis">http://kkovacs.eu/cassandra-vs-mongodb-vs-couchdb-vs-redis</a>
once you’ve got your app entirely hooked up to the database your all ready to start hitting the web app’s api from within your iOS app</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2014/07/06/making-a-drop-down-menu-with-uidynamics/">Making a Drop Down Menu With UIDynamics</a></h1>
<p class="meta">
<time datetime="2014-07-06T22:01:19-04:00" pubdate data-updated="true">Jul 6<span>th</span>, 2014</time>
</p>
</header>
<div class="entry-content"><p>Making a slide down menu</p>
<p>This weekend I spent a lot of time playing around with core dynamics. Core dynamics is a physics engine which comes with ios7, enabling you to do things like add gravity and mass to your views. To start using uidynamics all you need to do is add a uidynamicanimator property to your view controller. You’ll then need to aloc init the animator with the following line:
self.animator = [[UIDynamicAnimator alloc]initWithReferenceView:self.view];
In this customized initializer the reference view represents the frame which all animations will take place in relation to. Thus if the reference view were moving, all animation would move in relation. Once the animator has been alloc inited the syntax for adding forces is fairly straightforward. If you wanted to add a push force to a view for instance you would write:</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>UIPushBehavior *push = [[UIPushBehavior alloc]initWithItems:@[self.moveView] mode:UIPushBehaviorModeContinuous];
</span><span class='line'>push.pushDirection = CGVectorMake(1, 0);
</span><span class='line'>[self.animator addBehavior:self.push];
</span></code></pre></td></tr></table></div></figure>
<p>In this particular example the self.moveView would be pushed off the screen. Because the mode was set to UIPushBehaviorModeContinuous the speed of the view will increase. This is becuase a constant force results in a constant acceloration. If you wanted a constant velocity you could set the mode to UIPushBehaviorModeInstantaneous or use the following snippet:</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>UIDynamicItemBehavior *velocityBehavior = [[UIDynamicItemBehavior alloc]initWithItems:@[self.menuView]];
</span><span class='line'>[velocityBehavior addLinearVelocity:velocity forItem:self.menuView];
</span><span class='line'>[self.animator addBehavior:velocityBehavior];</span></code></pre></td></tr></table></div></figure>
<p>After aquainting myself with the basics of uidynamic animator I set out to create a dragable drop down menu similar to the controll panel in iOS7. To begin I created a uiview to which I added a pangesturerecogniser which delegated to the method handlePan:. In my handlePan method i wrote the following</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
<span class='line-number'>8</span>
<span class='line-number'>9</span>
<span class='line-number'>10</span>
<span class='line-number'>11</span>
<span class='line-number'>12</span>
<span class='line-number'>13</span>
<span class='line-number'>14</span>
<span class='line-number'>15</span>
<span class='line-number'>16</span>
<span class='line-number'>17</span>
<span class='line-number'>18</span>
<span class='line-number'>19</span>
<span class='line-number'>20</span>
<span class='line-number'>21</span>
<span class='line-number'>22</span>
<span class='line-number'>23</span>
<span class='line-number'>24</span>
<span class='line-number'>25</span>
<span class='line-number'>26</span>
<span class='line-number'>27</span>
<span class='line-number'>28</span>
<span class='line-number'>29</span>
<span class='line-number'>30</span>
<span class='line-number'>31</span>
<span class='line-number'>32</span>
<span class='line-number'>33</span>
<span class='line-number'>34</span>
<span class='line-number'>35</span>
<span class='line-number'>36</span>
<span class='line-number'>37</span>
<span class='line-number'>38</span>
<span class='line-number'>39</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>- (void)handlePan:(UIPanGestureRecognizer *)gesture
</span><span class='line'>{
</span><span class='line'> CGPoint currentTouchPosition = [gesture locationInView:self.view];
</span><span class='line'> CGPoint velocity = [gesture velocityInView:gesture.view.superview];
</span><span class='line'> velocity.x = 0;
</span><span class='line'> if (gesture.state == UIGestureRecognizerStateBegan){
</span><span class='line'> [self.animator removeAllBehaviors];
</span><span class='line'> }else if (gesture.state == UIGestureRecognizerStateChanged)
</span><span class='line'> {
</span><span class='line'> if (self.menuView.frame.origin.y + (currentTouchPosition.y - self.previousMenuPosition.y) <= 0){
</span><span class='line'> [self updateMenuAndSearchAlpha];
</span><span class='line'> CGRect newMenuPosition = CGRectOffset(self.menuView.frame, 0, (currentTouchPosition.y - self.previousMenuPosition.y));
</span><span class='line'> self.menuView.frame = newMenuPosition;
</span><span class='line'> }
</span><span class='line'> }
</span><span class='line'> else if (gesture.state == UIGestureRecognizerStateEnded) {
</span><span class='line'> UIDynamicItemBehavior *velocityBehavior = [[UIDynamicItemBehavior alloc]initWithItems:@[self.menuView]];
</span><span class='line'> [velocityBehavior addLinearVelocity:velocity forItem:self.menuView];
</span><span class='line'> [self.animator addBehavior:velocityBehavior];
</span><span class='line'> if (velocity.y > 0 ){
</span><span class='line'> [self fadeOutViews:@[self.searchAndFilterBar]];
</span><span class='line'> }else{
</span><span class='line'> [self fadeInViews:@[self.searchAndFilterBar]];
</span><span class='line'> }
</span><span class='line'> [self.topBoundry addBoundaryWithIdentifier:@"topBarrier"
</span><span class='line'> fromPoint:self.topLeft
</span><span class='line'> toPoint:self.topRight];
</span><span class='line'> [self.topBoundry addBoundaryWithIdentifier:@"bottomBarrier"
</span><span class='line'> fromPoint:self.bottomLeft
</span><span class='line'> toPoint:self.bottomRight];
</span><span class='line'> [self.animator addBehavior:self.topBoundry];
</span><span class='line'> self.push.pushDirection = CGVectorMake(velocity.x, velocity.y);
</span><span class='line'> [self.animator addBehavior:self.push];
</span><span class='line'> velocityBehavior.action = ^{
</span><span class='line'> [self updateMenuAlpha];
</span><span class='line'> };
</span><span class='line'> }
</span><span class='line'> self.previousMenuPosition = currentTouchPosition;
</span><span class='line'>}</span></code></pre></td></tr></table></div></figure>
<p>Essentially the method works by attaching the movement of the view along the Y axis to the movement of the pan gesture. Then once the gesture has stopped the view is given an initial velocity equal to the velocity of gesture as the touch ended and a force in the same direction. It is necessary to give the view a velocity as well as a push so that the view moves in one continuous motion.</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2014/06/29/using-map-view/">Using Map View</a></h1>
<p class="meta">
<time datetime="2014-06-29T21:26:06-04:00" pubdate data-updated="true">Jun 29<span>th</span>, 2014</time>
</p>
</header>
<div class="entry-content"><p>Intro to MKMapKit</p>
<p>If you have a smart phone it’s likely that you’ve interacted with apps which employ a map as part of their UI. While the maps are impressive and appear complicated to implement, apple has made adding maps incredibly easy by dealing with most of the functionality, such as scrolling and zooming, themselves. The first step when adding a map object to your project is to add the MapKit framework to your binary libraries. The way to do this is by going to your main project selecting the build phases tab and pressing the plus button in the Link Binary With Libraries drop down. You’ll then want to search for MapKit.framework and add it. You’ll now be able to import <MapKit/MapKit.h> to all the view controller’s you wish to add a map.</p>
<p>The next step is to add a map view object. You can ether do this by dragging the map view object into your story board or by alloc initing it in the view did load. You now should have a scrollable and zoomable map in your view. Now that you have a map in your project you can do such things as track the user’s location and drop pins.</p>
<p>To track location you will need to import the CoreLoaction framework in the same way in which you imported MapKit. You then can track the users movement using the following code:</p>
<ul>
<li><p>(void)locationManager:(CLLocationManager <em>)manager didFailWithError:(NSError </em>)error
{
NSLog(@“didFailWithError: %@”, error);
UIAlertView *errorAlert = [[UIAlertView alloc]
initWithTitle:@“Error” message:@“Failed to Get Your Location” delegate:nil cancelButtonTitle:@“OK” otherButtonTitles:nil];
[errorAlert show];
}</p></li>
<li><p>(void)locationManager:(CLLocationManager <em>)manager didUpdateToLocation:(CLLocation </em>)newLocation fromLocation:(CLLocation *)oldLocation
{</p></li>
</ul>
<p>}</p>
<p>Now that you have the users location tracked you’ll want to be able to drop a pin. To drop a pin at the users current location you can use the following code</p>
<p>MKPointAnnotation *point = [[MKPointAnnotation alloc] init];
point.coordinate = currentLocation.coordinate;
[self.currentLocationMap addAnnotation:point];</p>
<p>You can also remove pins by writing:
NSMutableArray *pins = [[NSMutableArray alloc] initWithArray:[self.currentLocationMap annotations]];
[self.currentLocationMap removeAnnotations:pins];</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2014/06/23/making-custom-ios-keyboards/">Making Custom iOS Keyboards</a></h1>
<p class="meta">
<time datetime="2014-06-23T15:28:56-04:00" pubdate data-updated="true">Jun 23<span>rd</span>, 2014</time>
</p>
</header>
<div class="entry-content"><p>At WWDC, 2014, apple unveiled iOS 8 and Xcode 6. For developers the big news out of the conference was apples new programming language, “swift.” However the new language may have overshadowed some even more groundbreaking changes introduced in the new operating system. Among the biggest changes, likely to greatly effect the way in which apps are developed and used, was apple’s introduction of “extensibility.” Essentially extensibility means that apps will now be able to communicate and build off of existing UI’s. This new stance on allowing apps to build off each other takes a sharp turn from the previously used technique of “Sandboxing.” Sandboxing was a security measure which prevented programs from interacting by giving each app a confined area in memory and CPU. The ultimate goal of Sanboxing was to prevent untrusted third party apps from interacting with and harming the host software. This security, however, won’t all be lost with apples introduction of extensibility. Apps still must ask for the users permission when doing such things as accessing the internet. Furthermore there still are many more restrictions put on iPhone development than there are for most other mobile operating systems, like Android.</p>
<p>One of the most obvious new capabilities introduced to developers with extensibility is the ability to create custom global keyboards. This past weekend I spent some time trying to figure out how I could make my own custom keyboard. The first few steps were very straightforwardly build into Xcode. The first thing I did was create a new target for my project (File –> New –> Target). After selecting new target I navigated to the extensions tab where I found an option for “custom keyboard.” Other extensions available were “Action Extension”, “Document Picker”, “Photo Editing Extension”, “Share Extension”, and “Today Extension.” Next I went to the .plist for my new custom keyboard, its important to note that you both your main project and new keyboard extension now have plists and it is important to select the keyboard extension’s property list. In order to access properties such as language and text alignment for your new keyboard you need to right click on the plist file and select the “source code” option. The plist will now be a markdown file in which you can set the settings of your keyboard.</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2014/06/15/the-words/">The Words</a></h1>
<p class="meta">
<time datetime="2014-06-15T21:43:20-04:00" pubdate data-updated="true">Jun 15<span>th</span>, 2014</time>
</p>
</header>
<div class="entry-content"><p>This past week I spent a lot of time developing and perfecting an algorithm to find all english dictionary words that can be formed from a given set of letters. I started out using a simple recursive algorithm which found each permutation for a set of letters and checked them against a dictionary. This solution was slow and caused a stack overflow for sets of letters over 20. Eventually I was able to develope a permutation generating algorithm which worked allongside the dictionary look up algorithm. This more sopisitcated aproach was able to procces every letter of the alphabet times 65 (16,900 letters) in 8.5 minutes with only using a max of 500mb of live memory. I’ve outlined my process in detail bellow.</p>
<p>My first function focussed entirely on generating permutations and checking each permutation against the dictionary:
//function returns an array of words that can be created using the letters inputed to “letters to add”
//newWord and newWordList both start out empty when you call the function</p>
<p>func allPermutations(lettersToAdd:Character[], newWord:Character[], inout newWordList:String[]) –> String[] {</p>
<pre><code>var lettersCopy = lettersToAdd
var newWordCopy = newWord
let newWordString:String = convertToString(newWord)
if (self.isRealWord(newWordString)) {
newWordList.append(newWordString)
}
for i in 0..lettersCopy.count{
var addLetter = lettersCopy[i]
lettersCopy.removeAtIndex(i)
newWordCopy.append(addLetter)
allPermutations(lettersCopy, newWord: newWordCopy, newWordList: &newWordList)
lettersCopy = lettersToAdd
newWordCopy = newWord
}
return newWordList
</code></pre>
<p>}</p>
<p>The function works by removing each letter from the lettersToAdd array and adding it to the newWord array and running the function recursively on each one of these newWords and reduced sets of lettersToAdd. This is demonstrated best by a simple depiction of the recursive tree. In this image the arrays on the left are the “lettersToAdd”, and the arrays on the right are the “newWord” arrays. As you can see the new words contain all the possible combinations of abc and each subset.</p>
<pre><code> [a, b, c] []
/ | \
/ | \
/ | \
/ | \
[b, c] [a] [a, c] [b] [a,b] [c]
/ | /\ | \
/ | / \ | \
/ | / \ | \
/ | / \ | \
/ | / \ | \
/ | / \ | \
</code></pre>
<p>[c] [a, b] [b] [a, c] [c] [b, a] [a] [b, c] [b] [c,a] [a] [c,b]</p>
<pre><code>| | | | | |
</code></pre>
<p>[] [a,b,c] [] [a,c,b] [] [b,a,c] [] [b, c, a] [] [c,a,b] [] [c,b,a]</p>
<p>This algorithm is nice because it is straight forward and doesn’t create any duplicates (if there is only one of each letter). However it is also incredibly slow for long sets of letters. The run time is N! + (N – 1)! + (N – 2)! + … (N – N)!) * logbase2(lengthOfDictionary). You have to multiply by log2(lengthOfDictionary) because there is a dictionary look up for every new word.</p>
<p>My first attempt to make this algorithm faster lead me down an incorrect path. Because I wanted to find the longest word that could be formed from a given set of letters I concluded that a solution that built from the top down as apposed to the button up would be more efficient. So instead of adding letters to newWord array I created an algorithm which was based on swapping letters. This algorithm is effective in creating all permutations of a set of letters without duplicates but does not find subset permutations. It also takes the same number of steps to create the full length permutations as my first algorithm so effectively it doesn’t really build solutions from the top down as I had hoped.</p>
<p>//Solution by swapping
//Failed attempt at making algorithm faster</p>
<p>–(NSString <em>)largestRealWord:(NSMutableArray </em>)lettersToAdd</p>
<pre><code> withCount:(NSInteger)count {
NSMutableArray *allSwapsForCount = [self allEllemensIn:lettersToAdd moveToIndex:count];
if (count == [lettersToAdd count] + 1){
NSString *arrayAsString = [self convertArrayToString:lettersToAdd];
if ([self isDictionaryWord:arrayAsString]){
NSLog(@"%@",arrayAsString);
return arrayAsString;
}else{
return nil;
}
}
for (NSMutableArray *newSwap in allSwapsForCount){
[self largestRealWord:newSwap withCount:count + 1];
}
return nil;
</code></pre>
<p>}</p>
<p>–(NSMutableArray <em>)allEllemensIn:(NSMutableArray </em>)letterArray</p>
<pre><code> moveToIndex:(NSInteger)index {
NSMutableArray *outputArray = [[NSMutableArray alloc]init];
for (NSInteger i = index + 1; i < [letterArray count]; i++){
NSMutableArray *newCombination = [letterArray mutableCopy];
[newCombination exchangeObjectAtIndex:index withObjectAtIndex:i];
[outputArray addObject:newCombination];
}
[outputArray addObject:letterArray];
return outputArray;
</code></pre>
<p>}</p>
<h6>#</h6>
<p>THE VERY LONG BUT VERY FAST SOLUTION:</p>
<h6>#</h6>
<p>After attempting to make my first algorithm more efficient I realized that there was probably no significantly faster way to create all permutations for a given set of letters. However I also had the realization that I was not trying to create all permutations, I was trying to create all permutations that were dictionary words. This important distinction lead me to the realization that instead of having the dictionary look up process and the permutation generation algorithm work independent of each other I should have each process inform the other. I eventually realized that if I looked up the permutations being created in the newWord arrays in the dictionary and couldn’t find any words starting with the combination I would be able to stop recursing down that branch. If I did find a word starting with the generated sequence using binary search I could then use the range in which this sequence was found to narrow down the section of the dictionary that needed to be searched for each newly generated word down the respective path. Thus as the newWord array gets longer the range of the dictionary that needs to be searched gets smaller and smaller.</p>
<p>The great thing about this approach is that it is nearly impossible to get a stack overflow no matter how many letters you input. To test this I ran it on every letter in the alphabet times 65 (that’s 16,900 letters). It takes a little while to run (about 8.5 minutes) simply because it has to run through and generate all of the words in the dictionary (the dictionary i’m using has 80368 words). This means that it is generating and checking 157 dictionary words per second (80,368words/(8.5 * 60)s = 157.56words/s). Also, because the recursive branches are pruned as soon as there are no dictionary words starting with the generated letter combination the recursion does not go too deep. For this test of 16,900 letters the live memory consumption reached a peak of only 500mb. Seeing as it only recurses to a depth where a dictionary word can still be formed the run time of the algorithm grows linearly with the number of words that can be found as apposed to an exponential relationship with the number of letters input.</p>
<p>This is my implementation:</p>
<p>//Very quick solution for generating all possible words for a given set of letters
–(BOOL)binarySearchForItem:(NSString *)item</p>
<pre><code> From:(NSInteger)start
To:(NSInteger)finish
inArray:(NSArray *)array {
NSInteger middle = ((finish - start) / 2) + start;
NSString *middleItem = array[middle];
NSComparisonResult compare = [item compare:middleItem];
if (ABS(start - finish) < 2){
if ([item isEqualToString:array[start]]){
return YES;
}else if ([item isEqualToString:array[finish]]){
return YES;
}
else{
return NO;
}
}
if (compare == NSOrderedSame){
return YES;
}else if (compare == NSOrderedAscending){
return [self binarySearchForItem:item From:start To:middle inArray:array];
}else{
return [self binarySearchForItem:item From:middle To:finish inArray:array];
}
</code></pre>
<p>}</p>
<p>//This function uses binary search
//returns a range where all the words beginning with the letters in item can be found
//If no words begging with item are found it returns a range of (-1,-1)
–(NSRange)searchForStartingSequence:(NSString *)item</p>
<pre><code> inDictionary:(NSArray *)array
start:(NSInteger)start
finish:(NSInteger)finish {
NSInteger middle = ((finish - start) / 2) + start;
NSString *middleItem = array[middle];
if ([middleItem length] > [item length]){
middleItem = [middleItem substringToIndex:([item length])];
}
NSComparisonResult compare = [item compare:middleItem];
if (ABS(start - finish) < 2){
if ([item isEqualToString:array[start]] || [item isEqualToString:array[start]]){
return NSMakeRange(start, (finish - start));
}
else{
return NSMakeRange(-1, -1); //returns -1 -1 if starting sequence does not exist in dictionary
}
}
if (compare == NSOrderedSame){
return NSMakeRange(start, (finish - start));
}else if (compare == NSOrderedAscending){
return [self searchForStartingSequence:item inDictionary:array start:start finish:middle];
}else{
return [self searchForStartingSequence:item inDictionary:array start:middle finish:finish];
}
</code></pre>
<p>}</p>
<p>//Searches makes all permutations from lettersToAdd
//Adds each letter from letters to add as the next letter in newWord and runs recursively on each combination
//remove the letter added to newWord from lettersToAdd for that path
//Function also checks the dictionary for each newWord to see if there are any words that start with newWord
//if not the recursive branch is pruned.
//If a word is found starting with newWord the range is updated to contain the range of words in the dictionary
//containing all the words starting with newWord. This narrows down the section of the dictionary
//needed to search to determine if the word is in the dictionary.</p>
<p>–(NSString <em>)allPermutationsFromLetters:(NSMutableArray </em>)lettersToAdd</p>
<pre><code> toNewWord:(NSMutableArray *)newWord
runningLongest:(NSString *)runningLongest
withDictionaryRange:(NSRange)range
englishDictionary:(NSArray *)dictionary
</code></pre>
<p>{</p>
<pre><code>NSRange newRange = range;
if ([newWord count] > 0){
NSRange newRange = [self searchForStartingSequence:[self convertArrayToString:newWord] inDictionary:dictionary start:range.location finish:(range.location + range.length)];
if (newRange.length == -1){
return @""; // returns empty string if the no words begin with the letters in newWord
}else{
NSString *wordAsString = [self convertArrayToString:newWord];
if ([self binarySearchForItem:wordAsString From:newRange.location To:(newRange.location + newRange.length) inArray:dictionary]){
NSLog(@"%@",wordAsString);
}
}
}
NSArray *distinctLetters = [self allDistinctFrom:lettersToAdd];
for (NSInteger i = 0; i < [distinctLetters count]; i++){
NSMutableArray *lettersToAddCopy = [lettersToAdd mutableCopy];
NSMutableArray *newWordCopy = [newWord mutableCopy];
NSString *letterToTransfer = distinctLetters[i];
[lettersToAdd removeObjectAtIndex:[lettersToAdd indexOfObject:letterToTransfer]];
[newWord addObject:letterToTransfer];
[self allPermutationsFromLetters:lettersToAdd toNewWord:newWord runningLongest:runningLongest withDictionaryRange:newRange englishDictionary:dictionary];
newWord = newWordCopy;
lettersToAdd = lettersToAddCopy;
}
return runningLongest;
</code></pre>
<p>}</p>
<p>//returns an array of all the distinct items in the input array
–(NSArray <em>)allDistinctFrom:(NSMutableArray </em>)arrayWithDuplicates {</p>
<pre><code>NSMutableArray *distinctArray = [[NSMutableArray alloc]init];
for (NSString *item in arrayWithDuplicates){
if (![distinctArray containsObject:item]){
[distinctArray addObject:item];
}
}
return distinctArray;
</code></pre>
<p>}</p>
<p>//main function which the user would pass the letters to.
–(NSString <em>)makeLargestFormLetters:(NSString </em>)letters {</p>
<pre><code>NSMutableArray *lettersArray = [self convertWordToLetterArray:letters];
AppDelegate *appD = (AppDelegate *)[[UIApplication sharedApplication] delegate];
NSRange fullRange = NSMakeRange(0, ([appD.allWords count] - 1));
NSString *runningLongest = @"";
[self allPermutationsFromLetters:lettersArray toNewWord:[@[] mutableCopy] runningLongest:runningLongest withDictionaryRange:fullRange englishDictionary:appD.allWords];
return runningLongest;
</code></pre>
<p>}</p>
<p>–(NSString <em>)makeLargestFormArray:(NSMutableArray </em>)lettersArray {</p>
<pre><code>AppDelegate *appD = (AppDelegate *)[[UIApplication sharedApplication] delegate];
NSRange fullRange = NSMakeRange(0, ([appD.allWords count] - 1));
NSString *runningLongest = @"";
[self allPermutationsFromLetters:lettersArray toNewWord:[@[] mutableCopy] runningLongest:runningLongest withDictionaryRange:fullRange englishDictionary:appD.allWords];
return runningLongest;
</code></pre>
<p>}</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2014/06/04/first-post/">First Post</a></h1>
<p class="meta">
<time datetime="2014-06-04T13:15:10-04:00" pubdate data-updated="true">Jun 4<span>th</span>, 2014</time>
</p>
</header>
<div class="entry-content">
</div>
</article>
<div class="pagination">
<a href="/blog/archives">Blog Archives</a>
</div>
</div>
<aside class="sidebar">
<section>
<h1>Recent Posts</h1>
<ul id="recent_posts">
<li class="post">
<a href="/blog/2014/07/28/container-controllers/">Container Controllers</a>
</li>
<li class="post">
<a href="/blog/2014/07/13/the-magic-of-parse/">The Magic of Parse</a>
</li>
<li class="post">
<a href="/blog/2014/07/06/making-a-drop-down-menu-with-uidynamics/">Making a Drop Down Menu With UIDynamics</a>
</li>
<li class="post">
<a href="/blog/2014/06/29/using-map-view/">Using Map View</a>
</li>
<li class="post">
<a href="/blog/2014/06/23/making-custom-ios-keyboards/">Making Custom iOS Keyboards</a>
</li>
</ul>
</section>
</aside>
</div>
</div>
<footer role="contentinfo"><p>
Copyright © 2014 - Carter -
<span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
</footer>
<script type="text/javascript">
(function(){
var twitterWidgets = document.createElement('script');
twitterWidgets.type = 'text/javascript';
twitterWidgets.async = true;
twitterWidgets.src = '//platform.twitter.com/widgets.js';
document.getElementsByTagName('head')[0].appendChild(twitterWidgets);
})();
</script>
</body>
</html>