How can I solve this?

Using Swift
1

Recently I was given a problem to solve and I don't even know where to start. It's related to a project I'm working on but I'm failing to wrap my head around the logic.


let input: [(Int, Int)] = [(1, 3), (1, 4), (2, 7), (1, 8), (3, 4), (2, 5)]
let expectedOutput: [Int: [Int]] = [1: [3, 4, 8], 2: [7, 5], 3: [4]]
var actualOutput: [Int: [Int]] = [:]

/* Print "Success" by using 'input' to fill 'actualOutput' 
and checking 'expectedOutput' == 'actualOutput' */

if expectedOutput == actualOutput { print("Success") } else { print("Failure") }


/* My Feeble Attempts */
/* Feeble Attempt 1 */
for x in input {
    print(x)
    print((x.0, x.1))
    
    if [x.1] != actualOutput[x.0, default: [x.1]] {
        
        actualOutput[x.0, default: [x.1]] += [x.1]
        
    } else if [x.1] == actualOutput[x.0, default: [x.1]] { continue }
    
    print("INSIDE", actualOutput)
}
print("OUTSIDE", actualOutput)


/* Feeble Attempt 2 */
for x in input {
    if x.1 == expectedOutput.keys.0 {
        
    }
}

My hint was "dictionary subscripting" but I clearly don't know how to take it. Would someone be able to point me in the right direction please?

Thanks

  • L33t-HAXXOR
2

"Dictionary subscripting" is the practice of using a "subscript", dict[key] with [ and ], in order to get or update the value associated with a key in a dictionary:

// Get the optional value, if any (maybe there is no value associated with the key)
let value = dict[key]

// Process the value, if any
if let value = dict[key] {
    print(value)
} else {
    print("no value")
}

// Set the value
dict[key] = ...

In your case, the code snippets below show you how "dictionary subscripting" helps solving your problem.

First version: iterate input pairs, and update the output dictionary with subscripting as described above

var actualOutput: [Int: [Int]] = [:]
for (left, right) in input {
    if let elements = actualOutput[left] {
        actualOutput[left] = elements + [right]
    } else {
        actualOutput[left] = [right]
    }
}
print("OUTSIDE", actualOutput)

Second version: modify accumulated elements in place, with append(_:).

var actualOutput: [Int: [Int]] = [:]
for (left, right) in input {
    if var elements = actualOutput[left] {
        elements.append(right)
        actualOutput[left] = elements
    } else {
        actualOutput[left] = [right]
    }
}
print("OUTSIDE", actualOutput)

Third version: modify accumulated elements right inside the output dictionary, with subscript(_:default:).

This third version is my favorite. It is very readable, and will please both beginners and experienced programmers:

var actualOutput: [Int: [Int]] = [:]
for (left, right) in input {
    actualOutput[left, default: []].append(right)
}
print("OUTSIDE", actualOutput)

Fourth version: replace the for loop with the reduce standard library method. One advantage is that the actualOutput variable is no longer mutable (we can declare it as let).

let actualOutput: [Int: [Int]] = input.reduce(into: [:]) { output, tuple in
    output[tuple.0, default: []].append(tuple.1)
}
print("OUTSIDE", actualOutput)

Some other readers will surely come up with other versions as well :-)

1 Like
3

Wow!

That is extensive! Thank you.
In the subscript example here they used:

let message = "Hello, Elle!"
var letterCounts: [Character: Int] = [:]
for letter in message {
    letterCounts[letter, defaultValue: 0] += 1
}

as an example
I didn't think to read 0 as 'empty Int literal' like [] is an empty array literal!
That certainly demistifies things

Those first two versions are very confusing and my brain is twisting trying to figure out what this is saying:

    if let elements = actualOutput[left] {
        actualOutput[left] = elements + [right]
    }

I mean I get that it works but I can't imagine how one would come up with that

4

You can do this way more easily using existing building blocks:

let result = Dictionary(grouping: input, by: \.0)
	.mapValues { tuples in tuples.map { $0.1 } }
3 Likes
5

Yet, it is Swift code that uses more common techniques than dict[key, default: ...], which is known by less people, and is a more... "rich" feature of the stdlib. It's good that you know it, of course.

// `left` is the left element of the input tuples.
// In (1, 3), it is 1. And `right` would then be 3.
//
// This reads: if there is already an array `elements`
// associated with key `left`... 
if let elements = actualOutput[left] {
    // ... then replace, in the dictionary, those elements with
    // a new array made of those elements
    // plus the new one, `right`.
    actualOutput[left] = elements + [right]
} else {
    // ... otherwise, create a new array with the
    // `right` number, and store it in the dictionary.
    actualOutput[left] = [right]
}

I suggested this version first, because:

  • It starts from your own initial code, in hope you would "grasp" the technique (I was partially wrong :wink:)
  • It exposes, step after step, an algorithm used to build the final result.
  • It can be translated, almost without any modification, in almost all other programming languages that are said to be "imperative" (which means that you instruct all steps that the program should perform, in order).

All other versions introduce, one after the other, Swift syntaxes and functional idioms, that may not always be translatable in other programming languages.

In your journey with Swift and other programming language, you will see all versions. Being able to recognize they are almost equivalent is useful. Being able to learn about their differences is important as well. But this is another story :-)

6

Thank you so much!
I'll have to learn more about those blocks first!

7

Thank you for presenting them in the order you did!
I'm probably going to want to build this type of algorithm for other languages in the future