Spiiin's blogРешение нескольких алгоритмических задачек на daScript.
Задачки со старого собеса Nokia на C++ программиста (уже закрыли офис в России), разбор
Вычислить первые N простых чисел#
.. и вернуть результат в качестве массива.
def calc_primes(n: int; var a:array<int>)
a |> clear
a |> reserve(n)
a |> push(2)
if n == 1
return
a |> push(3)
let gen <- generator<int>() <| $()
var t = 6
while true
yield t-1
yield t+1
t += 6
return false
var iterVal: int
while length(a) < n
next(gen, iterVal)
var simple = true
for prim in a
if iterVal % prim == 0
simple = false
break
if prim * prim > iterVal
break
if simple
a |> push(iterVal)
[export]
def main
var a: array<int>
calc_primes(1000000, a)
print("{a[length(a)-1]}\n")https://github.com/spiiin/dascript_trivial_examples/blob/main/primes/primes.das
Тривиальная версия:
- чуть более улучшенная формула перебора чисел-кандидатов (вместо всех нечётных — t*6+/-1) + проверка границы не корнем, а квадратом.
- не совсем понял, как хочет применить решето Эратосфена в варианте на C++ сама st_1ena, если нужны первые N простых чисел, а не “все числа меньшие N”, то возникает подзадача оценить минимальное натуральное число, меньше которого точно окажутся N простых чисел, что также нетривиально, или построить ленивых фильтров, что совсем нетривиально на C++, и требует оценки памяти под эти фильтры.
- вместо этого, версия решения, которая может вычислить первые N чисел в compile-time — в предположении, что у нас есть некоторое количество памяти, для сохранения решета эратосфена, эффективнее тогда потратить всю эту память на хранение предпросчитанных первых значений, и начинать рассчёт только сверх этих предпросчитанных чисел. На языках с макросами — предпросчёт в compile-time выполняется той же функцией, что в run-time, т.е. не требует написания дополнительного кода.
Версия, которая сохраняет первый числа в кеш (макрос [cached_primes (count=200)] - с параметром, сколько чисел будет предпросчитано заранее)
Посчитать статистику слов в тексте по длине слова#
Задача на то, чтобы найти в стандартной библиотеке языка нужные функциии
require fio
require strings
require daslib/strings_boost
[export]
def main()
var strings : array<string>
fopen("eng_to_rus.txt","rt") <| $(f)
if f != null
while !feof(f)
strings |> push <| fgets(f)
var counter : table<int; int>
for str in strings
var words <- str |> split_by_chars(" .,:-\n\t()%\"'")
for word in words
if word != ""
counter[length(word)] += 1 //word length
//counter[word] += 1 //word
var freq_pairs : array<tuple<int;int>>
for k, v in keys(counter), values(counter)
freq_pairs |> push <| [[ tuple<int;int> k, v]]
freq_pairs |> sort($(a,b) => !(a._1 < b._1))
for pair in freq_pairs
print("{pair._0} : {pair._1}\n")Решение в лоб - прочитать файл построчно, разбить на символы split_by_chars, обновляя в словаре значения количество слов. Дальше переложить значение в список пар, который отсортировать по первому элементу, и вывести на экран.
- Можно упороться по тому, чтобы выяснять у интервьюера, какие допустимы кодировки, разделители или что есть слова, как кажется подразумевали авторы задачи, которые потом расстроились, что ни один кандидат не учёл все возможные кейсы.
- Можно сохранять данные не в словаре, а сразу в списке пар
(длина слова, частота), не так то и много возможных длин слов. Сортировка такого списка пар в daScript - либо с помощью явной передачи функции сортировки, либо определением оператора < для своего типа.
Удалить из односвязного списка каждый пятый элемент#
Интересно посмотреть на разницу в работе с памятью между C++ и daScript
struct ListItem
value: int
[[do_not_delete]] next: ListItem?
def makeDemoList
var head = new [[ListItem value=1]]
var current = head
for i in range(2, 21)
current.next = new [[ListItem value=i]]
current = current.next
return head
[sideeffects]
def deleteEveryFifth(lst: ListItem?)
var counter = 1
var current = lst
while current != null
if counter++ % 4 == 0
var toDelete = current.next
current.next = current.next?.next
unsafe { delete toDelete; }
current = current.next
def printList(lst: ListItem?)
if lst != null
print("{lst.value} ")
printList(lst.next)
else
print("\n")
[export]
def main
var list = makeDemoList()
printList(list)
deleteEveryFifth(list)
printList(list)
//freeList //or just kill context
//Output:
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
// 1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 19- Раз мы “играем в C++”, то попробуем при удалении элемента из списка сразу же звать финализатор для него. Финализатор по умолчанию рекурсивно зовёт финализаторы для всех полей структуры. Это поведение можно изменить, если переопределить функцию
finalize, или если пометить поле атрибутом[[do_not_delete]](так как мы вручную измененяем указатели при удалении элемента, то элемент списка не отвечает за удаление следующего элемента по ссылке next). - С помощью
options persistent_heap = true, можно настроить также освобождение памяти после вызова финализатора (иначе за освобождение памяти отвечает хост-программа, один из паттернов быстрой работы с памятью — грохнуть всю выделенную в цикле работы скрипта память разом).
Вывести максимальное число, составленное из единиц двоичного представления заданного числа#
def popcount(x)
var temp = x
var count = 0
while temp != 0
temp &= temp - 1
count++
return count
def maxFrom1s(x)
let count1s = popcount(x)
var res = 0
for i in range(count1s)
res++
res<<=1
for i in range(31 - count1s) //assume 32 bits
res<<=1
return res
[export]
def main
print("{uint(maxFrom1s(256-1))}\n") //'0xff000000'Тоже без заморочек, в лоб.
В продакшен-варианте, если нужно действительно быстро, решение прокидывается в C++, где задействуются всевозможные интринсики компилятора для того, чтобы получать кол-во битов так, как умеет процессор, или другие трюки для минимизации количества инструкций (развернуть циклы, и наложить кучу масок — Hamming weight).
Вывести список всех самых длинных путей в дереве#
require daslib/functional
struct Tree
data : int
left, right : Tree?
var tree = new [[ Tree data = 5,
left = new [[Tree data = 1,
right = new [[Tree data = 2]]
]],
right = new [[Tree data = 7,
right = new [[Tree data = 10]]
]]
]]
//TODO: optimize
def clone_array(a: array<int>; newData:int)
unsafe
var newArr <- to_array(each(a))
newArr |> push <| newData
return <- newArr
def each_element(var tree:Tree?; path: array<int>; depth:int; blk:lambda<(what: int; path: array<int>; depth: int):void>)
if tree.left != null
each_element(tree.left, clone_array(path, tree.data), depth+1, blk)
invoke(blk, tree.data, path, depth)
if tree.right != null
each_element(tree.right, clone_array(path, tree.data), depth+1, blk)
[export]
def main
let startPath: array<int>
var globalResult : table<int; array<array<int>>>
unsafe
tree |> each_element(startPath, 0) <| @[[&globalResult]](value: int; path: array<int>; depth: int)
globalResult[depth] |> push_clone <| clone_array(path, value)
//find max depth
let maxDepth = reduce(keys(globalResult)) <| $(left, right : int)
return left > right ? left : right
//print all pathes
print("All pathes with longest depth:\n")
for path in globalResult[maxDepth]
print("{path}\n")
//All pathes with longest depth:
//[[ 5; 1; 2]]
//[[ 5; 7; 10]]Туповатое решение, с кучей лишних копирований путей.
Можно оптимайзить. Либо по памяти, разделив обход на 2 — сначала найти максимальную глубину, затем собрать только самые длинные пути. Либо в один проход, но сохраняя не полные копии путей, а альтернативное дерево с записью глубины каждой ветви рядом с указателем на оригинальные ноды left и right, по которому можно будет восстановить пути + обновляя максимальное значение глубины каждую итерацию.