{{announcement.body}}
{{announcement.title}}

# Special Cases Are a Code Smell

DZone 's Guide to

# Special Cases Are a Code Smell

### In this article, we discuss the importance of eliminating special cases in order to write more effective and generalized code.

· Security Zone ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

## A Warning Sign

Los Angeles is famous for its complicated parking signs:

They're totems of rules and exceptions, and exceptions to the exceptions. Often, when we code, we forget a lesson that’s obvious in these preposterous signs: Humans understand simple, consistent rules, but fail on special cases.

## A Trivial Example

Say you’re given an array of integers, and you want to calculate the sum of each element’s neighbors. Try it:

Ruby

`xxxxxxxxxx`
1

1
` [1, 3, 4, 5, 0, 1, 8]`

Before going on, consider how you’d solve this yourself.

A straightforward approach might look like this:

Ruby

`x`

1
`input = [1, 3, 4, 5, 0, 1, 8]`
2

3
`result = input.map.with_index do |_, i|`
4
` if i == 0 # <-- LEFT ENDPOINT `
5
`    input[i+1] `
6
` elsif i == input.size - 1 # <-- RIGHT ENDPOINT`
7
`    input[i-1]`
8
` else`
9
`    input[i-1] + input[i+1] # <-- GENERAL CASE`
10
` end`
11
`end.to_a`

Notice how we treat the endpoints as special cases, complicating the simple rule “sum both neighbors of every element.” A better approach is to first transform the input so the special cases vanish, leaving only the general case. Let’s pad the input with zeros, but loop over the original elements:

Java

`xxxxxxxxxx`
1

1
`     0   1   3   4   5   0   1   8   0`
2
`    ---     ---`
3
`     |       |`
4
`     +-- 3 --+`

Every item now has both a left and right neighbor. The special cases are gone, and the simple algorithm shines through.

Ruby

`xxxxxxxxxx`
1

1
`input = [1, 3, 4, 5, 0, 1, 8]`
2
`padded = [0] + input + [0]`
3

4
`result = (1...padded.size-1).map do |i|`
5
` padded[i-1] + padded[i+1]`
6
`end.to_a`

You may also like: The Benefits of Learning Algorithms.

## Another Simple Example

You start at the bottom (step A) of a 4 step staircase, labeled as follows:

Java

`xxxxxxxxxx`
1

1

2
`                   ____`
3
`                  |  D`
4
`              ____|`
5
`     O       |  C`
6
`     |<  ____|`
7
`    / \ |  B    `
8
`    ____|       `
9
`      A       `

You take `n` steps, turning around at the top and bottom. Where do you end up?

If you took 4 steps, you’d finish on step C – 3 steps to reach the top, turn around, 1 step down. Naively, you could simulate this stair pacing: iterate from `1` to `n`, ping-ponging a current index inside an array.

But, this is inefficient for a large value of `n`. Most programmers notice that every 6 steps you return to step A, so the “`n` answer” must equal the “`n % 6` answer” (the remainder when `n` is divided by `6`).

They might solve it like this:

Ruby

`xxxxxxxxxx`
1
14

1
`STEP_LABELS = 'ABCD'.chars`
2
`STAIRCASE_HEIGHT = STEP_LABELS.size - 1`
3

4
`def final_step(n)`
5
` n = n % (2 * STAIRCASE_HEIGHT)`
6

7
` index = if n <= STAIRCASE_HEIGHT`
8
` n # never turn around`
9
` else`
10
` 2 * STAIRCASE_HEIGHT - n # reach top and turn around`
11
` end`
12

13
` STEP_LABELS[index]`
14
`end`

This solution is fast but still contains a needless special case: reaching the top and turning around. Instead, we can “complete the staircase,” viewing the problem like this:

Java

`xxxxxxxxxx`
1

1
`                   ____`
2
`                  |  D |`
3
`              ____|    |____`
4
`     O       |  C        C  |`
5
`     |<  ____|              |____`
6
`    / \ |  B                  B  |     --> wrap`
7
`    ____|                        |____     around`
8
`      A         `

and walk in a single direction, forever. The “top and bottom” special cases disappear. Once again, the code is simpler:

Ruby

`xxxxxxxxxx`
1

1
`STEP_LABELS = 'ABCD'.chars`
2
`CIRCULAR_LABELS = STEP_LABELS + (STEP_LABELS[1...-1]).reverse`
3

4
`def final_step(n)`
5
` n = n % CIRCULAR_LABELS.size`
6
` CIRCULAR_LABELS[n]`
7
`end`

This example is prototypical: Both modular arithmetic and symmetry completion are common techniques when eliminating special cases.

## Down With Evens!

Say you’re given an array of arrays, and you want to eliminate even-sized arrays by slicing between the first and second element, like so:

Ruby

`xxxxxxxxxx`
1

1
`# odd length, even, slice odd length,`
2
`# unchanged into two unchanged`
3
`# V V V`
4
`input = [ [1], [1, 2, 3, 4], [1, 2, 3] ]`
5

6
`desired_output = [ [1], [1], [2, 3, 4], [1, 2, 3] ]`

A good first instinct is to use `map`:

Ruby

`xxxxxxxxxx`
1

1
`input = [ [1], [1, 2, 3, 4], [1, 2, 3] ]`
2

3
`input.map { |x| x.size.even? ? [[x.first], [x.drop(1)]] : x }`
4
`#=> [[1], [[1], [[2, 3, 4]]], [1, 2, 3]]`

But the nesting isn’t right: we want the split to produce two elements, not an array containing two elements. You might give up here and use `reduce`:

Ruby

`xxxxxxxxxx`
1

1
`input = [ [1], [1, 2, 3, 4], [1, 2, 3] ]`
2

3
`result = input.reduce([]) do |m, x|`
4
` x.size.even? ? (m << [x.first] << x.drop(1)) : m << x`
5
`end`
6
`#=> [[1], [1], [2, 3, 4], [1, 2, 3]] `

This would be a shame because conceptually `map` is a better fit. Our `map` attempt fails because it special cases the even elements, wrapping only those in an array. Instead, let’s wrap odd elements too, and then remove the wrapping from all elements:

Ruby

`xxxxxxxxxx`
1

1
`input = [ [1], [1, 2, 3, 4], [1, 2, 3] ]`
2

3
`result = input.map do |x|`
4
` x.size.even? ? [[x.first], x.drop(1)] : [x]`
5
`end.flatten(1)`
6
`#=> [[1], [1], [2, 3, 4], [1, 2, 3]] `

This trick takes many forms. Ultimately, avoiding special cases is about making things identical. When you can’t make the special case look general, see if you can make the general case look special.

## A Real-World Example

In a system I worked on, merchant hours of operation were stored in a database as bit arrays, and each day was broken into `24 * 12 = 288` 5-minute intervals. Here, for simplicity, we’ll use 24 one hour intervals – it won’t change anything relevant.

If a store was open Monday 8am to 1pm, and then again from 2pm to 7pm, our Monday bit array would be:

Java

`xxxxxxxxxx`
1

1
`12am           8am       1pm         7pm    11pm`
2
`v               v         v           v       v`
3
`0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0`

The goal is to display these bit arrays in a human-friendly form on a web page, the way Yelp does:

Since `01` marks an open time and `10` marks a close time, you might try a solution like this, and think you’re done:

Ruby

`xxxxxxxxxx`
1
17

1
`# NOTE: The utility methods `all_indexes(arr, subarr)`, which returns`
2
`# the indexes of all matches of subarr within arr, and `to_12h(hour)`,`
3
`# which converts 24 hour time to 12 hour time, are defined in the link`
4
`# below, and at the end of the article.`
5
`#`
6

7
`bits = '000000001111101111100000'.chars.map(&:to_i)`
8
`open_times = all_indexes(bits, [0, 1]).map(&:succ).map(&to_12h)`
9
`close_times = all_indexes(bits, [1, 0]).map(&:succ).map(&to_12h)`
10
`hours = open_times.zip(close_times)`
11
`puts hours.map{ |x| x.join(' - ') }.join("\n")`
12

13
`#`
14
`# Output:`
15
`#`
16
`# 8am - 1pm`
17
`# 2pm - 7pm `

But what if a merchant – a club, say – opens at midnight? The `01` will be missing. Likewise, past-midnight closing times force you to look at the next day:

To display Friday’s hours, for example, we must look at Thursday and Saturday, so we can ignore Thursday’s late-night overflow and correctly report Friday’s 2am closing time.

Java

`xxxxxxxxxx`
1

1
`                5pm     1am             5pm     1am             5pm`
2
`                 v       v               v       v               v`
3
`000000000000000001111111110000000000000001111111110000000000000001111111`
4
`\______________________/\______________________/\______________________/`
5
`         Thurs                  Friday                  Saturday`

Again, think about how you’d approach this.

For simplicity, ignore the case where a merchant is open 24 hours straight, but handle all other possibilities. It’s tempting to make special cases for midnight openings and late-night closings. But, can we can avoid them?

Let’s take a full week's schedule and a merchant with both edge cases:

Ruby

`xxxxxxxxxx`
1
12

1
`# A full week of daily hours of operation`
2
`# This is what would be returned by a database query`
3
`#`
4
`hours = [`
5
` '000000000000111000001111', # Mon: 12pm - 3pm, 8pm - 12am`
6
` '000000000000111000001111', # Tue: 12pm - 3pm, 8pm - 12am`
7
` '000000000000111000001111', # Wed: 12pm - 3pm, 8pm - 12am`
8
` '000000000000111000000000', # Thu: 12pm - 3pm`
9
` '111100000000000000000011', # Fri: 12am - 4am, 10pm - 4am`
10
` '111100000000000000000011', # Sat: 10pm - 4am`
11
` '111100000000000000000000' # Sun: Closed`
12
`].map { |h| h.chars.map(&:to_i) }`

The crucial observation — the rule with no exceptions — is this: the time intervals we display on a given day are exactly those whose left endpoint is contained in that day.

Our algorithm, then, will be:

1. Flatten the input so we don’t have to worry about individual days.
2. Pad the input so we don’t have to worry about midnight or overflows.
3. Zip all valid opening times with all valid closing times.
4. Group the results by day, to recover the “day” view.

That’s it — just a couple small adjustments to make our original idea work despite the special cases.

Taking all valid closing times works because ruby’s `zip` method ignores extra items by default:

Ruby

`xxxxxxxxxx`
1

1
`[1, 2].zip([3, 4, 5, 6])`
2

3
`#=> [[1, 3], [2, 4]]`
4
`# NOTE: extras 5 and 6 are ignored`

Using the `hours` we defined above, we’ll combine the tricks we’ve learned so far: modular arithmetic to capture each day’s 24-hour cycle, “padding” the endpoints of the week to make it circular, and modular arithmetic again to handle 24 to 12 hour time conversions.

Ruby

`xxxxxxxxxx`
1
39

1
`# make the hours circular, to avoid special casing Monday`
2
`# at midnight or late night Sunday overlowing into Monday`
3
`circular_hours = hours.last + hours.flatten + hours.first`
4

5
`# this makes two adjustments:`
6
`# 1. adds 1 to found indexes, because searching for '01'`
7
`# or '10' returns the index before the one we want`
8
`# 2. subtracts 24 to remove the extra "circular" Sunday`
9
`# we added to the beginning in "circular_hours"`
10
`def all_adjusted_indexes(arr, subarr)`
11
` all_indexes(arr, subarr).map { |x| x + 1 - 24 }`
12
`end`
13

14
`# all valid open times for a week`
15
`#`
16
`# this filters out our extra "padding" days`
17
`open_times = all_adjusted_indexes(circular_hours, [0,1])`
18
` .select { |x| (0...24*7).cover?(x) }`
19

20
`# all valid close times for a week`
21
`close_times = all_adjusted_indexes(circular_hours, [1,0])`
22
` .select { |x| x > open_times.first }`
23

24
`# the heart of algorithm`
25
`#`
26
`# we zip open and close times, group the "left endpoints"`
27
`# by day of week, and apply human friendly formatting`
28
`hours_by_day = open_times.zip(close_times)`
29
` .group_by { |x| (x[0] / 24).floor }`
30
` .transform_values { |x| x.map(&human_hours).join(', ') }`
31

32
`# all the rest is just printing our results`
33
`days = %w(Mon Tue Wed Thu Fri Sat Sun)`
34

35
`hours_of_operation = days.map.with_index do |day, i|`
36
` "#{day}: #{hours_by_day[i] || 'Closed'}"`
37
`end`
38

39
`puts hours_of_operation.join("\n")`

See the whole thing in action here: Try it online!

Let’s recap what we’ve done. We’ve translated a problem that would require special cases — treating each day’s hours, and the overlaps between them, individually — to one in which all opening and closing times in a week are treated uniformly. In this uniform world, the solution to our problem became trivial: we just zipped together all the opening and closing times.

When we were done, we translated back to our original world of individual days using `group_by`. This trick of translating a problem to a simpler “world,” solving it there, and translating it back is common in mathematics and is related to the concept of duality.

## Take-Aways

Once you start looking for special cases, you’ll see them everywhere. Eliminating them isn’t a minor matter of tidiness, either. It will make your code easier to read, simpler to maintain, and, most crucially, less prone to bugs.

Think of it this way: To make non-trivial code reliable, there are two basic strategies. One is to meticulously enumerate and test all special cases. If you’ve missed any, or if any of your tests are incorrect or incomplete, your code will fail. The other is to recast your problem to make the special cases vanish. There are many fewer ways to fail with the latter strategy. And much less code to maintain.

It’s not always possible to simplify a problem by recasting it. But often it is, if only partially. So, when you find yourself typing `if`… stop, and pause for a moment. Look for another solution. It might be simpler than you were thinking.

Here are the utility functions we used in the final merchant hours example:

Ruby
`xxxxxxxxxx`
1
22

1
`# NOTE: Utility function definitions`
2

3
`# utility to find all indexes of subarr in arr`
4
`def all_indexes(arr, subarr)`
5
` arr.each_cons(subarr.size).map.with_index do |x, i|`
6
` x == subarr ? i : nil`
7
` end.compact`
8
`end`
9

10
`# utility to convert 24 hour time to 12 hour time`
11
`#`
12
`# using odd? generalizes this, so it works for `
13
`# 36 hours, 48 hours, etc`
14
`to_12h = ->(military) do`
15
` pm, h = military.divmod(12)`
16
` "#{h == 0 ? 12 : h}#{pm.odd? ? 'pm' : 'am'}"`
17
`end`
18

19
`# converts an array of 24h [open, close] intervals to:`
20
`# a hyphenated string range in 12h format`
21
`# eg: [12, 16] becomes "12pm - 4pm"`
22
`human_hours = ->(arr) { arr.map(&to_12h).join(' - ') }`

Topics:
security

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.