Решение нескольких алгоритмических задачек на 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, по которому можно будет восстановить пути + обновляя максимальное значение глубины каждую итерацию.