-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathcompetitive-programming-with-swift.html
355 lines (310 loc) · 20.4 KB
/
competitive-programming-with-swift.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
<!DOCTYPE html>
<html lang="en">
<head>
<script src="https://use.fontawesome.com/afd448ce82.js"></script>
<!-- Meta Tag -->
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<!-- SEO -->
<meta name="author" content="Bruno Rocha">
<meta name="keywords" content="Software, Engineering, Blog, Posts, iOS, Xcode, Swift, Articles, Tutorials, OBJ-C, Objective-C, Apple">
<meta name="description" content="Competitive programming is a great way to master a specific programming language. Even if you're not interested in competing in world events like the Facebook Hacker Cup, tackling difficult algorithm problems using nothing but the language's bread and butter will expose you to aspects/shortcuts of the language you would otherwise never see, such as how efficient certain methods/operations are and how to code better alternatives.">
<meta name="title" content="Competitive Programming With Swift">
<meta name="url" content="https://swiftrocks.com/competitive-programming-with-swift">
<meta name="image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4">
<meta name="copyright" content="Bruno Rocha">
<meta name="robots" content="index,follow">
<meta property="og:title" content="Competitive Programming With Swift"/>
<meta property="og:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta property="og:description" content="Competitive programming is a great way to master a specific programming language. Even if you're not interested in competing in world events like the Facebook Hacker Cup, tackling difficult algorithm problems using nothing but the language's bread and butter will expose you to aspects/shortcuts of the language you would otherwise never see, such as how efficient certain methods/operations are and how to code better alternatives."/>
<meta property="og:type" content="website"/>
<meta property="og:url" content="https://swiftrocks.com/competitive-programming-with-swift"/>
<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta name="twitter:image:alt" content="Page Thumbnail"/>
<meta name="twitter:title" content="Competitive Programming With Swift"/>
<meta name="twitter:description" content="Competitive programming is a great way to master a specific programming language. Even if you're not interested in competing in world events like the Facebook Hacker Cup, tackling difficult algorithm problems using nothing but the language's bread and butter will expose you to aspects/shortcuts of the language you would otherwise never see, such as how efficient certain methods/operations are and how to code better alternatives."/>
<meta name="twitter:site" content="@rockbruno_"/>
<!-- Favicon -->
<link rel="icon" type="image/png" href="images/favicon/iconsmall2.png" sizes="32x32" />
<link rel="apple-touch-icon" href="images/favicon/iconsmall2.png">
<link rel="preconnect" href="https://fonts.googleapis.com">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link href="https://fonts.googleapis.com/css2?family=Source+Sans+3:ital,wght@0,200..900;1,200..900&display=swap" rel="stylesheet">
<link rel="canonical" href="https://swiftrocks.com/competitive-programming-with-swift"/>
<!-- Bootstrap CSS Plugins -->
<link rel="stylesheet" type="text/css" href="css/bootstrap.css">
<!-- Prism CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/prism4.css">
<!-- Main CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/style48.css">
<link rel="stylesheet" type="text/css" href="css/sponsor4.css">
<!-- HTML5 shiv and Respond.js support IE8 or Older for HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
<script type="application/ld+json">
{
"@context": "https://schema.org",
"@type": "BlogPosting",
"mainEntityOfPage": {
"@type": "WebPage",
"@id": "https://swiftrocks.com/competitive-programming-with-swift"
},
"image": [
"https://swiftrocks.com/images/thumbs/thumb.jpg"
],
"datePublished": "2018-10-26T13:42:07+00:00",
"dateModified": "2020-04-12T14:00:00+02:00",
"author": {
"@type": "Person",
"name": "Bruno Rocha"
},
"publisher": {
"@type": "Organization",
"name": "SwiftRocks",
"logo": {
"@type": "ImageObject",
"url": "https://swiftrocks.com/images/thumbs/thumb.jpg"
}
},
"headline": "Competitive Programming With Swift",
"abstract": "Competitive programming is a great way to master a specific programming language. Even if you're not interested in competing in world events like the Facebook Hacker Cup, tackling difficult algorithm problems using nothing but the language's bread and butter will expose you to aspects/shortcuts of the language you would otherwise never see, such as how efficient certain methods/operations are and how to code better alternatives."
}
</script>
</head>
<body>
<div id="main">
<!-- Blog Header -->
<!-- Blog Post (Right Sidebar) Start -->
<div class="container">
<div class="col-xs-12">
<div class="page-body">
<div class="row">
<div><a href="https://swiftrocks.com">
<img id="logo" class="logo" alt="SwiftRocks" src="images/bg/logo2light.png">
</a>
<div class="menu-large">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-large">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
<div class="menu-small">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-1">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-2">
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
</div>
<div class="content-page" id="WRITEIT_DYNAMIC_CONTENT">
<!--WRITEIT_POST_NAME=Competitive Programming With Swift-->
<!--WRITEIT_POST_HTML_NAME=competitive-programming-with-swift-->
<!--WRITEIT_POST_SITEMAP_DATE_LAST_MOD=2020-04-12T14:00:00+02:00-->
<!--WRITEIT_POST_SITEMAP_DATE=2018-10-26T13:42:07+00:00-->
<!--Add here the additional properties that you want each page to possess.-->
<!--These properties can be used to change content in the template page or in the page itself as shown here.-->
<!--Properties must start with 'WRITE_IT_POST'.-->
<!--Writeit provides and injects WRITEIT_POST_NAME and WRITEIT_POST_HTML_NAME by default.-->
<!--WRITEIT_POST_SHORT_DESCRIPTION=Competitive programming is a great way to master a specific programming language. Even if you're not interested in competing in world events like the Facebook Hacker Cup, tackling difficult algorithm problems using nothing but the language's bread and butter will expose you to aspects/shortcuts of the language you would otherwise never see, such as how efficient certain methods/operations are and how to code better alternatives.-->
<title>Competitive Programming With Swift</title>
<div class="blog-post">
<div class="post-title-index">
<h1>Competitive Programming With Swift</h1>
</div>
<div class="post-info">
<div class="post-info-text">
Published on 21 May 2018
</div>
</div>
<p>Competitive programming is a great way to master a specific programming language. Even if you're not interested in competing in world events like the <b>Facebook Hacker Cup</b>, tackling difficult algorithm problems using nothing but the language's bread and butter will expose you to aspects/shortcuts of the language you would otherwise never see, such as how efficient certain methods/operations are and how to code better alternatives. This is a cool hobby to have, and as a bonus you'll even be indirectly preparing yourself to the feared Big 4 interviews where you have to solve algorithm problems in a whiteboard!</p>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Even though in a real competition coding in Swift would be a big disavantage (as it's slightly slow compared to other languages and has few native data structures), lots of popular online platforms like <a href="https://leetcode.com/">LeetCode</a>, <a href="https://www.hackerrank.com/">HackerRank</a> and <a href="https://codefights.com/">Codefights</a> support Swift and they are a great way to make yourself a better iOS developer, specially since competitive problems will only accept very fast algorithms as possible solutions. If you've never did this before, I highly recommend giving it a shot.</p>
<p>In this article, I'll give a brief tutorial on how to use Swift to read input data and some tips for tackling competitive problems in Swift.</p>
<h2>Reading Standard Input with Swift</h2>
<p>In competitive programming, the problem's input is usually fed into a command line application which makes some sense of it and prints the desired result.</p>
<p>Platforms like <b>LeetCode</b> and <b>CodeFights</b> will automatically process input data for you and expose an empty Swift method that should return the problem's solution, but other platforms like <b>HackerRank</b> will sometimes have you manually read, parse the standard input and then print the result. Thankfully, that's not as complex as it sounds.</p>
<p>To simulate a competitive programming environment, create a <b>Command Line Tool</b> project in Xcode:</p>
<div class="post-image margin-top-40 margin-bottom-40">
<img src="https://i.imgur.com/MyAl2I0.png" alt="">
</div>
<p>Be aware that a Command Line Tool is not a Cocoa app, so you'll have no access to things like <code>UIKit</code>! The core frameworks like <code>Foundation</code> are all you have here.</p>
<p>In <code>main.swift</code>, type and run the following code:</p>
<pre class="language-swift"><code class="language-swift">let line = readLine()
print("Got something! \(line)")</code></pre>
<p>At this point, the program will be frozen. <code>readLine()</code> is a Standard Library method that synchronously reads the standard input and returns a <code>String?</code> once a full line is retrieved or <code>nil</code> if EOF is reached.</p>
<p>If you type something in Xcode's console, the program's execution will continue and print what you wrote:</p>
<div class="post-image margin-top-40 margin-bottom-40">
<img src="https://i.imgur.com/U5IwGnn.png" alt="">
</div>
<p>However, a competitive programming problem will likely have several hundred lines of input. You can use a <code>while</code> loop to make your code run until the input ends:</p>
<pre class="language-swift"><code class="language-swift">while let line = readLine() {
print("Got something! \(line)")
}</code></pre>
<div class="post-image margin-top-40 margin-bottom-40">
<img src="https://i.imgur.com/KLUwiBK.png" alt="">
</div>
<p>That is all you need to know to get started. From here forward, your skill with pure Swift is the only variable.</p>
<p>Here's an example problem if you've never done this before:</p>
<h2>Example Problem</h2>
<p>Given an array of integers, find the sum of its elements.</p>
<h3>Input Format</h3>
<p>The first line contains an integer, denoting the size of the array.</p>
<p>The second line contains <code>n</code> space-separated integers representing the array's elements.</p>
<h3>Output Format</h3>
<p>Print the sum of the array's elements as a single integer.</p>
<h3>Sample Input</h3>
<pre class="language-swift"><code class="language-swift">6
1 2 3 4 10 11</code></pre>
<h3>Sample Output</h3>
<p><code>31</code></p>
<h2>Solution</h2>
<p>Every problem has multiple possible solutions. For this one, we can harness the power of <code>reduce</code>:</p>
<pre class="language-swift"><code class="language-swift">import Foundation
_ = readLine() //Read and drop the array size line.
//Knowing the size of the array beforehand is needed for some languages
//But as readLine() returns the whole line, Swift doesn't need it!
let array = readLine()!.components(separatedBy: " ").map { Int($0)! }
let result = array.reduce(0, +)
print(result)</code></pre>
<h2>Swift tips for Competitive Programming</h2>
<p>The beauty of competitive programming is that merely solving the problem is not enough - your program must solve it as fast as possible.</p>
<p>There's a lot to talk about <a href="https://pt.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation">runtime complexity</a>, but this section is supposed to cover Swift tips that are useful when things need to be quick.</p>
<p><b>If you have a tip that is not here, feel free to contact me and I'll add it and credit you!</b></p>
<h3>Use Overflow Operators</h3>
<p>Swift naturally protects you from numbers overflowing at the cost of performance. This can cost you some valuable nano-seconds, and some problems might even <b>want</b> you to overflow numbers. Luckily, Swift has special arithmetic operators that ignore overflow checks, making them faster than the regular operators:</p>
<pre class="language-swift"><code class="language-swift">1 &+ 1
1 &- 1
1 &* 1
1 &>> 1</code></pre>
<h3>Printing is slow</h3>
<p>The <code>print(_:)</code> method is very slow, and it can be particularly painful when printing things like <code>Arrays</code>. You can gain some performance if you print everything at once.</p>
<pre class="language-swift"><code class="language-swift">let array = [String](repeating: "A", count: 1000)
for a in array {
print(separated, terminator: " ") // slow
}
/////
let separated = array.joined(separator: " ")
print(separated) // a lot quicker, even though we're processing the array beforehand</code></pre>
<h3>Allocate Array capacities in advance</h3>
<p>Swift's <code>Arrays</code> have dynamic sizes, meaning that the language automatically allocates more memory space for it as it increases in size. Even if this is quite fast, you can make it even faster if you know the array size in advance by using the <code>Array.reserveCapacity(_:)</code> method. This is useful if you have a problem where the solution is an <code>Array</code> with a specific size.</p>
<pre class="language-swift"><code class="language-swift">let arraySize = Int(readLine()!)!
var array = [Int]()
array.reserveCapacity(arraySize) //Runtime is slightly slower without manually setting the array's capacity.
for i in 0..<arraySize {
array.append(solve(for: i))
}</code></pre>
<p>Alternatively, you can use the <code>repeating:count:</code> initializer when you need a pre-filled array:</p>
<pre class="language-swift"><code class="language-swift">let fiveZs = Array(repeating: "Z", count: 5)
print(fiveZs)
// Prints "["Z", "Z", "Z", "Z", "Z"]"</code></pre>
<h3>Abuse Implicitly Unwrapped Optionals</h3>
<p>While the dreaded <code>!</code> should be avoided in real applications, safety is not a concern in competitive programming. Since inputs are guaranteed to always be the same, you can completely skip the overhead of unwrapping optionals.</p>
<h3>Use <code>inout</code> - Dmitry Volevodz</h3>
<p>Using <code>inout</code> arguments can be really useful when passing data around recursive functions, and I was able to confirm that <code>inout</code> arguments are even faster to create than regular ones when passing around value types with inner reference types.</p>
<h3>Subtract Dates to measure performance - Rodrigo Carvalho</h3>
<p>The following snippet will measure how long it takes to run something:</p>
<pre class="language-swift"><code class="language-swift">func measure(function: () -> Void) {
let start = Date()
function()
let end = Date()
print("Elapsed time: \(end.timeIntervalSince(start))")
}
measure {
timeIntensiveTask()
}</code></pre>
<p>This can be useful when you have multiple approaches and is not sure which one is faster. Be sure to run this with optimizations turned on to properly measure things, as most of the Swift compiler's tricks require it.</p>
<h2>Swift Algorithm Club</h2>
<p>Most competitive programming problems will rely on a specific data structure, and since Swift unfortunately has no native support for most of them, that means you'll have to code them yourself.</p>
<p>Fortunately, the <a href="https://github.com/raywenderlich/swift-algorithm-club/">swift-algorithm-club</a> repo has Swift implementations of pretty much everything, making it a great place to learn how to code popular data structures in Swift.</p>
<h2>What else?</h2>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Regardless if you are studying for an interview, wanting to compete at world events or just trying to get better at iOS development, solving competitive programming problems is a very interesting way of increasing your Swift skills. I've personally benefited a lot from it, and would love to know what you think of it.</p>
<p>Follow me on my Twitter - <a href="https://twitter.com/rockbruno_">@rockbruno_</a>, and let me know of any suggestions and corrections you want to share.</p>
<h2>References and Good reads</h2>
<a href="https://pt.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation">Big O Notation</a>
<br>
<a href="http://jordansmith.io/on-performant-arrays-in-swift/">Performant Arrays In Swift</a>
<br>
<a href="https://developer.apple.com/documentation/swift/1641199-readline">Apple Docs: readLine()</a>
</div></div>
<div class="blog-post footer-main">
<div class="footer-logos">
<a href="https://swiftrocks.com/rss.xml"><i class="fa fa-rss"></i></a>
<a href="https://twitter.com/rockbruno_"><i class="fa fa-twitter"></i></a>
<a href="https://github.com/rockbruno"><i class="fa fa-github"></i></a>
</div>
<div class="footer-text">
© 2025 Bruno Rocha
</div>
<div class="footer-text">
<p><a href="https://swiftrocks.com">Home</a> / <a href="blog">See all posts</a></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<!-- Blog Post (Right Sidebar) End -->
</div>
</div>
</div>
<!-- All Javascript Plugins -->
<script type="text/javascript" src="js/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/bootstrap@5.0.2/dist/js/bootstrap.bundle.min.js" integrity="sha384-MrcW6ZMFYlzcLA8Nl+NtUVF0sA7MsXsP1UyJoMp4YLEuNSfAP+JcXn/tWtIaxVXM" crossorigin="anonymous"></script>
<script type="text/javascript" src="js/prism4.js"></script>
<!-- Main Javascript File -->
<script type="text/javascript" src="js/scripts30.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-H8KZTWSQ1R"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-H8KZTWSQ1R');
</script>
</body>
</html>