Recently when traveling I had several free hours at an airport I decided to dabble in Apple’s forgotten scripting language called AppleScript.

Instinctively I figured that the best way to learn the language was to write some simple loops and conditionals. Consequently I wrote some simple algorithms.

I chose Applescript because I had never dabbled in the built-in scripting language Apple provides in OS X. Learning AppleScript is pretty simple. It only has 2 data structures it appears.

Scenario for the algorithm

A typical problem that I’ve used in junior level interviews is around finding the max sum of an integer subarray¹. The key rule is that the sub-array must be consecutive indices and an input to the function is the integer size of the sub-array.

1

{9, 1, 7, 6, 4, 5}

For instance the above array input should return 17 for an input size of 3.

If you notice we have a special case where the frequency of the max sub array is greater than 1.

1

{9, 1, 7}

Sums to 17.

1

{7, 6, 4}

Also sums to 17.

To make things simple we will ignore the frequency for now.

What are some possible solutions?

There are several ways to solve this problem but the most efficient would yield a linear O(n) in Big O notation. We must scan the array once at least once in order to evaluate all the sums.

The trick is to maintain a sliding window and keep track of the maximum sum that has been solved. An additional integer variable can keep track of the current sum for clarity.

The Naive Approach

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

on maxSubList(theList, length)
  
  #boundary checking
  if length > (count of theList) then return -1
  if length ≤ 0 then return -1
  
  set maxEndingHere to 0
  set maxSoFar to 0
  set refCount to 0
  repeat with i from 1 to count of theList
      --log "Outer Loop i: " & i
      repeat with j from i to i + length - 1
          set refCount to refCount + 1
          --log "j: " & j
          set currentValue to item j of theList
          --log "currentValue: " & currentValue
          set maxEndingHere to maxEndingHere + currentValue
          --log "maxEndingHere: " & maxEndingHere
          if j - i + length ≥ 1 then set maxSoFar to max(maxSoFar, maxEndingHere)
      end repeat
      set maxEndingHere to 0
      --log "maxSoFar: " & maxSoFar
      
      if j = (count of theList) then log "refCount:  " & refCount
      if j = (count of theList) then return maxSoFar
  end repeat
  --return maxSoFar
end maxSubList

In my attempt at getting something working I wrote the above after several trial and error compile/runs in the AppleScript Editor.

The name of the function on line 1 is maxSubList. It accepts two parameters which I called theList (array or collection) and length (window size).

At this point the signature of the function looks similar to Javascript and other scripting languages. I found it curious that the way to declare a function is with the keyword on.

Lines 4 & 5 cover some simple boundary and cases on the length and theList input variables. Notice that AppleScript doesn’t declare types in a function signature, similar to Javascript.

Lines 7 through 9 declare some variable I thought we might need. Lines 10 through 26 describe an iteration on our collection of integers. I like the use of the keyword repeat as a FOR loop descriptor. Maybe not as great as “ForEach” (in .NET/C#) but better than “For”. that AppleScript

The memento pattern’s undo/redo behaviors the MaxSum increment and decrement is the keeping things simple².

I timed this Naive approach on a large array…it took a whopping 11.1 seconds!

The Iterated Approach

The only way to get better at algorithms is to practice the problems. I prefer pen and paper. After a couple minutes of thought the solution was obvious.

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

on maxContiguousSubListSum(theList, subListLength)
  
  if subListLength > (count of theList) then return -1
  if subListLength ≤ 0 then return -1
  
  set valueQueue to {}
  set currentMaxSum to 0
  set overallMaxSum to 0
  
  repeat with i from 1 to count of theList
      set currentValue to item i of theList
      
      set end of valueQueue to currentValue
      set currentMaxSum to currentMaxSum + currentValue
      
      if (count of valueQueue) > subListLength then
          set poppedOffItem to item 1 of valueQueue
          set currentMaxSum to currentMaxSum - poppedOffItem
          set valueQueue to rest of valueQueue
      end if
      
      if currentMaxSum > overallMaxSum then
          set overallMaxSum to currentMaxSum
      end if
  end repeat
  
  return overallMaxSum
end maxContiguousSubListSum

Off the bat I’ll just tell you that this implement ran in 0.88 seconds at O(n) complexity. Much better than 11 seconds.

In the end AppleScript is a bit cumbersome to seriously consider as a 1st or even 2nd choice language to develop with on the Mac. Any script that is longer that 50 lines can probably be don’t in another language. I’m sure that the intention of AppleScript isn’t to make super speedy algorithms. But you don’t have to take my word for it, try for yourself. I’ll see you next time.