Как я Sberfight 2022 проходил на Swift

В 2021 году на просторах интернета случайно увидел Sber на geecko.com, тогда компания Sber проводила fight типа "староверы" против "новокодеров". (Простите за неточности, вспоминаю по памяти.)

И когда запустили конкурс Sberfight я уже автоматически попал в рассылку.

Я относительно молод в Swift и тренировка умений или же проверка навыков на скорость очень привлекла. А формат в стиле "Денди" поднимает давно забытое чувство детства. (Моей любимой игрой были "танчики", "контра" и "червяк Джим"- правда у друзей на "Сеге".)

Однако, первый неприятный сюрприз ждал в условиях конкурса - подсчет баллов. Оказывается подсчет баллов теперь осуществляется - 100 баллов за задание(при учете, что все тест кейсы положительные) и + за скорость(по формуле где Swift имеет коэффициент примерно 1.29, как и JS, а вот максимальный С# - 2). Всего 8 заданий - значит минимум 800 баллов без надбавок. А вот сколько за скорость? Ответ был найден быстро - только взглянув на турнирную таблицу (Топ-1 - примерно - 3400 баллов). То есть 2400 надбавка за скорость (предположим C# - значит в общем за Swift при таком же идеальном выполнении я получу - 2477 баллов). Тут-то интерес начал угасать.

А, эскиз победителей уже нарисовался.

Пройдя два задания и поняв, что быстрее отведенного времени я не успеваю, а значит надбавки за скорость нет. Я взглянул на обновленный топ и увидев (Топ-1 - 5500 баллов) моей грусти не было предела.

Так и закрыл я Sberfight до конца февраля, пока мне на почту не упало письмо от рекрутера Sber. (Что это была массовая рассылка - это понятно, но зачем за два задания из 8 для меня осталось вопросом.) Но такая напоминалка заинтриговала меня глянуть на лидеров и каким же было мое удивление, когда Топ 1 - стоял 3400 баллов. Понятно, кто-то нашел баг, накрутил себе баллов, а теперь все пофиксили. Вот тут интерес и разогрелся, увы оставалось два дня.

Однако, пройти все тест кейсы быстрее отведенного времени для меня все равно осталось непреодолимым.

Ради интереса других и комментариев выложу тут свое решение. Увы, из-за спешки забыл скопировать задания и восстанавливаю по памяти.

Тест #1

Задание:

Вывести номера тех чисел, которые будут самыми большими при увеличении их на K

func getResult(cash: [Int], k: Int) -> [Int] {
    var tempArrOfThiefes: [Int] = []
    
    for index in 0..<cash.count {
        print("cash - ", cash[index])
        
        var tempArr: [Int] = []
        for ygrek in 0..<cash.count {
            if (cash[index]+k) > cash[ygrek] {
                tempArr.append(index)
            }
        }
        print("temp arr count - ", tempArr.count)
        if (tempArr.count + 1) >= cash.count {
            print("index appended - ", index)
            tempArrOfThiefes.append(index + 1 )
            tempArr = []
        }
    }
    return tempArrOfThiefes
}

// Test #1
let x = [1,3,4,2]
let k = 2
let res = getResult(cash: x, k: k)
print(res)

Тест #2 (тут задание я так и не вспомнил)

func getResult(nums: [Int], k: Int) -> Int {
    if k == 0 {
        return 0
    }
    var tempInt: Int = 0
    var tempArr = nums
    var tempK = k
    
    repeat {

        for index in 0..<tempArr.count{
            if tempArr[index] <= tempK {
                tempArr[index] = 0
                tempArr.sort()
                tempK += 1
                tempInt += 1
            }
        }

    } while (tempK < tempArr.min()!)
    
    
    return tempInt
}

// Test #1
let x = [1,2,3,4,5]
let k = 1
let res = getResult(nums: x, k: k)
print(res)

Тест #3 (для данного теста на просторах Интернета нашел решение на Python, на которое пытался опираться)

Задание:

Мы знаем количество гостей, ваша задача рассадить всех за стол. Однако, некоторые гости дали вам список неприятелей, с которыми они не сядут. Стулья расставили так, что у стола оказалось два крайних места, у которых только один соседний гость. В остальных случаях соседа два. Определите, можно ли рассадить гостей так, чтобы все оказались довольны.

Ввод:

invited_list - количество приглашённых гостей, 0<invited_list<10

dislike_list - строчный массив неприятелей, ["1-2,3"] - означает, что гость под номером 1 не сядет с гостями 2 и 3

Вывод:

Boolean - возможно ли рассадить гостей так, чтобы они все были довольны

Пример:

invited_list = 4

dislike_list = ["1-2", "3-4"]

get_result(invited_list, dislike_list) = True // [1, 4, 2, 3]

Python (эргономичностью решения я восхитился, источник решения: https://www.cyberforum.ru/python-tasks/thread2943547.html)

def guests_seating( n, dis ):
    lis = list( range(1, n + 1) )
    bad_pairs = set()
    for e in dis:
        L, de, R = e.partition('-')
        not_frends = set( int(x) for x in R.split(',') )
        for nf in not_frends:
            bad_pairs.add( frozenset( [int(L), nf] ) )
    res = [ [x] for x in lis ]
    flag = True
    while flag:
        flag = False
        for x in res:
            for y in lis:
                if frozenset([x[-1],y]) not in bad_pairs and y not in x:
                    x.append(y)
                    flag = True
                    if len(x) == n:
                        #return x
                        return True
    return False
#==============================================================================
n = 10
dis = '1-2,4,6,8 3-5,7,9 4-1,2,3 5-2,4 6-3'.split()
print( guests_seating( n, dis ) )

func getResult(invitedList: Int, dislikeList: [String]) -> Bool {
    if invitedList == 0 {
        return true
    } else if invitedList == 1 {
        return true
    }
    let allGuest = [Int](1...invitedList)
    print("allGuest created - ", allGuest)
    var badPairs:[Int:[Int]] = [:]
    for indexB in 0..<invitedList {
        var tempBadPairs:[Int: [Int]] = [:]
        for indexK in 0..<dislikeList.count {
            let guestArr = dislikeList[indexK].components(separatedBy: "-")
            let keyElement = Int(guestArr.first!)!
            let dislikeElements = guestArr.last!.components(separatedBy: ",")
            let valueElement = dislikeElements.map{Int($0)!}
            tempBadPairs[keyElement] = valueElement
        }
        if tempBadPairs.keys.contains(indexB+1) {
            let newValue = tempBadPairs[indexB+1]
            badPairs[indexB+1] = newValue
        } else {
            badPairs[indexB+1] = [0]
        }
    }
    print("Done well - ", badPairs)
    
    var sortedGuests: [Int] = []
    sortedGuests.append(1)
    var flag = 0
    while flag<invitedList {
        flag += 1
        
        for indexQ in 2...badPairs.count {
            print("x is - ", indexQ)
            if !badPairs[sortedGuests.last!]!.contains(indexQ) {
                if !sortedGuests.contains(indexQ) {
                    sortedGuests.append(indexQ)
                    print("sortedGuests.append(x.key) - ", indexQ)
                }
            }
        }
        
        if sortedGuests.count == invitedList {
            print("sorted guests - ", sortedGuests)
            return true
        }
        print("sorted guests - ", sortedGuests)
    }
    
    return false
}

// Test #1
let invited_list1 = 4
let dislike_list1 = ["1-2,3", "3-4"]
let intT1 = getResult(invitedList: invited_list1, dislikeList: dislike_list1)
print(intT1)
// Test #2
let invited_list2 = 5
let dislike_list2 = ["1-2,3", "3-4,5", "2-3"]
let intT2 = getResult(invitedList: invited_list2, dislikeList: dislike_list2)
print(intT2)

Тест #4 (тут все тест кейсы сильно сопротивлялись :) )

Задание:

Существует массив из N количества 3 видов букв - ["x", "x", "y", "z"]

Если буквы заменить на целые числа, то можно ли получить общую сумму в X число

Пример:

// Test #1

let sub_array = ["x", "x", "x", "y", "y"]

let k = 12

let result = getResult(sub_array, k)

print(result)

// = True

// Можно заменить x на 2, y на 3, тогда получится

//[2, 2, 2, 3, 3]

func getResult(_ subArray: [String], _ k: Int) -> Bool {
    if subArray.count == 1 {
        return true
    }
    if subArray.count > k {
        return false
    }
    if subArray.count == k {
        return true
    }
        
    var tempSetOfTypeLetters: Set<String> = []
    var dictOfCountOfLetters: [String: Int] = [:]
    subArray.forEach { str in
        tempSetOfTypeLetters.insert(str)
        if !dictOfCountOfLetters.keys.contains(str) {
            dictOfCountOfLetters[str] = 1
        } else {
            dictOfCountOfLetters[str]! += 1
        }
    }
    var totalCount: Int = 0
    var tempArray: [Int] = []
    for indexA in dictOfCountOfLetters {
        tempArray.append(indexA.value)
        totalCount = totalCount + indexA.value
    }
    tempArray = tempArray.sorted{$0>$1}
    print("Well done - tempArray is - ", tempArray)

    var tempCounter: Int = 0
    while tempCounter < k {
        tempCounter += 1
        var tempArrOfInt:[Int] = []
        
        for indexE in 0..<tempArray.count-1 {
            tempArrOfInt.append(tempArray[indexE] * tempCounter)
            print("tempArrOfInt.append - ", tempArrOfInt)
            if indexE >= 0 {
                print("<<<---->>>")
                print("indexE is - ", indexE)
                for indexY in 1..<k {
                    var temp:[Int] = []
                    temp.append(tempArray[indexE+1] * (tempCounter + indexY))
                    print("temp appended - ", temp )
                    if tempArray.count == 3 {
                        print("tempArray.count == 3 - ", tempArray.count)
                        for indexK in (indexY+1)..<k {
                            temp.append(tempArray[2] * (tempCounter + indexK))
                            print("temp appended - ", temp)
                            var total = tempArrOfInt.first
                            print("total 2.1 - ", total)
                            temp.forEach{ total = total! + $0 }
                            print("total 2.2 is - ", total as Any)
                            if (k - total!) == 0 {
                                return true
                            }
                        }
                    }

                    print("temp - ", temp)
                    var total = tempArrOfInt.first
                    print("total 1.1 - ", total)
                    temp.forEach{ total = total! + $0 }
                    print("total is 1.2 - ", total as Any)
                    if (k - total!) == 0 {
                        return true
                    }
                }
            }
        }
    }
    return false

}

// Test #1
let sub_array = ["x", "x", "x", "y", "y"]
let k = 12
let result = getResult(sub_array, k)
print(result)
// = True
// Можно заменить x на 2, y на 3, тогда получится
//[2, 2, 2, 3, 3]

// Test #2
let sub_array2 = ["x", "x", "y", "y"]
let k2 = 20
let result2 = getResult(sub_array2, k2)
print(result2)

// Test #3
let sub_array4 = ["x", "x"]
let k4 = 2
let result4 = getResult(sub_array4, k4)
print(result4)

// Test #4
let sub_array5 = ["x", "x", "y"]
let k5 = 4
let result5 = getResult(sub_array5, k5)
print(result5)

// Test #5
let sub_array6 = ["x", "x", "y", "z"]
let k6 = 24
let result6 = getResult(sub_array6, k6)
print(result6)

// Test #6
let sub_array7 = ["x", "x", "y", "z"]
let k7 = 34
let result7 = getResult(sub_array7, k7)
print(result7)

Тест #5 (Тут я упустил, что убирать можно не только первые символы, но и в середине, из-за чего быстрее положенного все тест кейсы не прошел. На том и остановился...)

Задание:

 Дана строка s. Вы можете удалить из нее не более k символов. Определите максимально возможное количество совпадений символов с stringGoal, то есть совпадением считается s[i] = stringGoal[i]. Например, строка "agddb" совпадает с "gdda" только одним символом. Если убрать первый символ, тогда будет уже 3 совпадения - "gddb" "gdda".

Ввод:

 s - строка с символами, 0<length(s)<20

 k - максимальное количество удалений, 0<k<10

 stringGoal - строка для сравнения

 Вывод:

Integer - максимальное количество совпадений s[i] = stringGoal[i]

 Пример:

 s = "agdd"

 k = 1

 stringGoal = "gdd"

 getResult(s, k, stringGoal) = 3

extension String {
    var length: Int {
        return count
    }
    subscript (i: Int) -> String {
        return self[i ..< i + 1]
    }
    func substring(fromIndex: Int) -> String {
        return self[min(fromIndex, length) ..< length]
    }
    func substring(toIndex: Int) -> String {
        return self[0 ..< max(0, toIndex)]
    }
    subscript (r: Range<Int>) -> String {
        let range = Range(uncheckedBounds: (lower: max(0, min(length, r.lowerBound)),
                                            upper: min(length, max(0, r.upperBound))))
        let start = index(startIndex, offsetBy: range.lowerBound)
        let end = index(start, offsetBy: range.upperBound - range.lowerBound)
        return String(self[start ..< end])
    }
}

func getResult(_ s: String, _ k: Int, _ stringGoal: String) -> Int {
    var maxCounterOfMatched: Int = 0
//  Первая попытка
//  проходит Тестов 6 из 10
    var flagFromPrefixToBody: Bool = false
    var whileCounter: Int = 0
    while whileCounter <= k {
        var tempMainString: String = ""

        if flagFromPrefixToBody == false {
            tempMainString = s.substring(fromIndex: whileCounter)
            print("do it 1")
        } else {
            var tempString = s
            if tempString.count > (whileCounter+1) {
                let indexToDelete = tempString.firstIndex(of: Character(tempString[whileCounter+1]))!
                tempString.remove(at: indexToDelete)
                tempMainString = tempString
            }
            print("do it 2")
        }
        print("tempMainString is - ", tempMainString)

        var counterOfMatched: Int = 0
        for indexA in 0..<tempMainString.count {
            if tempMainString[indexA] == stringGoal[indexA] {
                counterOfMatched += 1
            }
        }
        print("compare results")
        if maxCounterOfMatched < counterOfMatched {
            maxCounterOfMatched = counterOfMatched
        }
        if whileCounter == k && flagFromPrefixToBody == false {
            flagFromPrefixToBody = true
            whileCounter = 0
        }
        whileCounter += 1
    }
    print("Part #1 finished, maxCounterOfMatched - ", maxCounterOfMatched)
  
//  Вторая попытка
    print("<<---->>")
    print("Part# 2")
    
    for indexA in 0..<s.count {
        print("do it 1")
        for indexB in 0...k {
            print("do it 3")
            var tempString = s
            let startIndex = tempString.index(tempString.startIndex, offsetBy: indexA)
            //print("startIndex - ", startIndex)
            guard let endIndex = tempString.index(tempString.startIndex, offsetBy: (indexA + indexB)) as? String.Index else {
                break
            }
            //print("endIndex - ", endIndex)
            if startIndex >= endIndex {
                break
            }
            tempString.removeSubrange(startIndex...endIndex)
            print("tempString - ", tempString)
            print("do it 4")
            var counterOfMatched: Int = 0
            for indexC in 0..<tempString.count {
                if tempString[indexC] == stringGoal[indexC] {
                    counterOfMatched += 1
                }
            }
            if maxCounterOfMatched < counterOfMatched {
                maxCounterOfMatched = counterOfMatched
            }
        }
    }
    /*
     вторая часть проходит Тестов 6 из 10
     */

    return maxCounterOfMatched
}
// 1,2,3,6,7,8
// need - 4,5,9,10
// need - 3,7,8,10
// (stringGoal.count - 1,2,3,6,7,8)

// need - 2,6,7,8

let s = "agdd"
let k = 1
let stringGoal = "gdd"
let result = getResult(s, k, stringGoal) //= 3
print(result)

let s2 = "ababcde"
let k2 = 3
let stringGoal2 = "abcde"
let result2 = getResult(s2, k2, stringGoal2) //= 5
print(result2)


let s3 = "aqwerty"
let k3 = 3
let stringGoal3 = "qwerty"
let result3 = getResult(s3, k3, stringGoal3)
print(result3)

// Test that fails
let s4 = "aqawerty"
let k4 = 3
let stringGoal4 = "qwerty"
let result4 = getResult(s4, k4, stringGoal4)
print(result4)