Hark, to forge algorithms of simple guise,

Skip to content

This doth be a machine-wrought text which may contain errors!

Quote

“Algorithm”, a terme by coders ycleped, when they desire not to unfold what deeds they have wrought.

Algoritme?

What manner of thing is an algoritme?

An algoritme doth be a logical function which performeth a given operation. Thus, one might technically call a function which addeth two numbers together an “algoritme”, yet oft times an algoritme is somewhat more complex than so. Oft are algoritmes employed to make operations which take much time, swifter.

Algorithm Meme

Must I employ Python in these tasks?

Nay! Thou mayest use whatsoever tongue of programming doth please thee in these endeavours.

Innebygde biblioteker?

The conceit in these tasks doth lie in eschewing the use of built-in libraries or special Python functions. Forsooth, there existeth a simple “one-liner” to reverse text: text[::-1], yet here we desire thee to attempt to solve such tasks without employing the same. It may be that we mention a built-in function should the solution prove somewhat difficult to divine. This shall be marked with ❗.

In practice, ‘tis fully possible to resolve all these tasks with if, for, while and common list operations.

How to “Design” an Algorithm?

Most oft are algorithms designed iteratively. What doth this signify?

1. ✅ Break first the problem into lesser parts.
  • Think ye first upon that which is most vital for the algorithm to function
    • Shall it return a value? A boolean? A list?
    • Do I require any helping functions?

2. ❓ Doth any “edge-cases” exist?
  • What doth befall shouldst thou cast in an empty list or text?

3. ✅ Begin, perchance, but to assay a solution.

4. ✅ Prithee, Examine if the Algorithm Doth Function Aptly in its Running
  • Essay with larger input, doth it consume much time?

5. ❓ Ponder upon thy solution, doth thou require all the steps thou hast employed?
  • Are all if-checks needful?
  • Shouldst thou possess more than one for-loop, exist there any clear ways to make this one for-loop?
    • This doth differ shouldst thou have nested loops or loops one after another. One after another is oft times avoidable.

6. ✅ Consider Extreme Scenarios with Inputs:
  • Example with numbers: great numbers, small numbers, negative numbers
  • Text example: much text, many small words, extra spaces, large and small letters.

7. ❓ Doth it avail to employ pseudo-code to wit the logic more fully?

Easy Task 1 - To Discern if a List Doth Contain a Given Number

Compose ye an algorithm (a function, if thou wilt) which shall discern if a list doth contain a given number. It shall return True or False based upon whether the number doth exist within the list or doth not.

Herein lieth a list with test-data:

Test-data for algoritme:
Test-Data Sjekk Svar
[1, 2, 3, 4, 5, 6, 7, 8, 9] 5 True
[1, 2, 3, 4, 5, 6, 7, 8, 9] 10 False
[2, 3, 5, 7, 11, 13, 17, 19, 23] 2 True
[2, 3, 5, 7, 11, 13, 17, 19, 23] 10 False
[-1, 0, 1, -34, 321, 22, 98, -214] -214 True
[-1, 0, 1, -34, 321, 22, 98, -214] 0 True
[-1, 0, 1, -34, 321, 22, 98, -214] 2 False

Tips til framgangsmåte
  1. Take in a list and a list-value into a function. In this task, ‘tis numbers, yet may be text.
  2. Employ a for-loop to traverse the list.
  3. Should the number be like unto the check-number, return True.
  4. If the for-loop doth conclude and thou hast not found it, return False.

Svaret (i python) 
def exists_in_list(the_list, check):
    for number in the_list:
        if number == check:
            return True
    return False

Verily, the answer (in the tongue of Python) doth present itself thus:

def exists_in_list(the_list, check):
    for number in the_list:
        if number == check:
            return True
    return False

Easy A Task – Summation

Devise an algorithm that doth sum a list of numbers together.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], doth yield the answer 21.
  • [5, 1, 23, 68, 22, 13, 4], doth yield the answer 136
  • [3, 3, -3, -3, 3] doth yield the answer 3. Perchance thou mayest disregard the numbers of ill omen and give the answer 9.

Tips til framgangsmåte
  1. Do take a list within a function’s hold,
  2. And store a temporary sum as 0 of old.
  3. Employ a for-loop to traverse the list, I say.
  4. return the sum of the list without delay.

Svaret (i python) 
def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Lo, the answer (in the tongue of Python) doth lie thus:

def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Medium Task 3a - The Greatest Value in a List

Devise an algorithm that doth discover the largest value within a list.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], doth yield the answer 6.
  • [6, 17, 227, 1, 23, 42, 12], doth yield the answer 227
  • [2, -2, 2, -2, -2, 2] doth yield the answer 2.

Tips til framgangsmåte
  1. Take ye a list into a function.
  2. Set a temporary value unto the first element of the list.
  3. Employ a for-loop to traverse the list and compare it with the value thou didst set in 2.
  4. If the value be greater, set the temporary value unto the new value.
  5. return this temporary value.

Svaret (i python) 
def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Verily, the answer (in the tongue of Python) doth lie thus:

def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Easy Task 3b - Should the List be Void?

Add a check which doth assay if the list doth contain any elements. Should it be empty, return None.

Svaret (i python) 
def find_max(numbers):
    if len(numbers) == 0:
        return None

    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Verily, the answer (in the tongue of Python) doth lie thus:

def find_max(numbers):
    if len(numbers) == 0:
        return None

    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Easy Task the Fourth – To Count the Number of a Given Element Within a List

Devise an algorithm which doth tally the number of a given element within a list.

Test-data for algoritme:
  • ["apple", "banana", "orange", "apple", "apple", "banana"] with apple doth yield the answer 3.
  • [1, 4, 5, 2, 4, -3, -4, 4, 2, 4, 221, 3, 1, 1, 4, 1, 12, 33, 4, 4, 2, -4, 1, 4] with 4 doth yield the answer 8.
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] with dog doth yield the answer 3.
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] with 7 doth yield the answer 5.
  • ["red", "blue", "green", "red", "yellow", "red"] with red doth yield the answer 3.
  • [10, -2, -2, -2, 5, 10, 10, -2] with -2 doth yield the answer 4.

Tips til framgangsmåte
  1. Take in a list and a check-value into a function
  2. Begin with a temporary count-value set to 0.
  3. Traverse the list with a for-loop.
  4. If the element is like unto the check, increase the count-value by 1.
  5. Return the count-value.

Svaret (i python) 
def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

Lo, the answer (in the tongue of Python) doth present itself thus:

def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

Medium Task the Fifth – To Reverse a String, Sayeth the Text

Devise an algorithm that doth reverse a given string.

Test-data for algoritme:
  • Hello there! doth become !ereht olleH.
  • heisann alle sammen doth become nemmas ella nnasieh
  • Python doth become nohtyP
  • racecar doth become racecar
  • 12345abc doth become cba54321
  • god morgen doth become negrom dog

Tips til framgangsmåte
  1. Take in a string into a function
  2. Create a temporary value to store an empty string.
  3. Go through the texts with a for-loop with range. Here thou mayest traverse the list backwards, but ‘tis possible to solve this by proceeding forwards in the list.
  4. Add each character to the temporary value in order.
  5. Return the temporary text.

Svaret (i python) 
def reverse(text):
    result = ""
    # This line is somewhat complex, yet it doth begin
    # at the end, proceeding (inclusive) to 0 (by writing
    # -1 as the end), and counting downwards by 1 each time
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Perchance thou mayest employ an algorithm that addeth to the beginning instead:

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # add to the beginning instead
       result = text[i] + result
   return result

Medium Task the Sixth - An Algorithm for Palindromes

Devise ye an algorithm that doth assay whether a given word be a palindrome. Examples of such palindromes are abba, racecar, regninger.

Tips til framgangsmåte
  1. Create a function that doth receive text to examine.
  2. Employ a for-loop to ascertain if the letters on either side of the text be alike.
  3. Return False should a letter not correspond; if all do match (for-loop doth complete), return True.

Ekstra:
Dost thou perceive how thou mightest render the algorithm twice as swift?

Hint

Du trenger bare å sjekke halvparten!

Svaret (i python) 
def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True
Raskere algoritme

def palindrome(text):
for i in range(0, int(len(text) / 2)):
if text[i] != text[len(text) - i - 1]:
return False
return True

Lo, the answer (in the tongue of Python)

def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True
Raskere algoritme

def palindrome(text):
for i in range(0, int(len(text) / 2)):
if text[i] != text[len(text) - i - 1]:
return False
return True

Medium Task the Seventh – To Discern if a List Be Sorted

Compose an algorithm that doth examine if a list be sorted. The most facile manner to assay this is to commence from the beginning, comparing if the next element be “greater.” Should an element not be “greater,” then is the list not sorted.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], doth yield the answer True.
  • [6, 17, 227, 1, 23, 42, 12], doth yield the answer False
  • [2, -2, 2, -2, -2, 2] doth yield the answer False.
  • [2, 2, 3, 4, 4, 6], doth yield the answer True.
  • [12, 23, 34, 45, 56, 67], doth yield the answer True.

Tips til framgangsmåte
  1. Create a function that doth receive a list.
  2. Employ a for-loop to traverse the whole list (use range to the length of the list, less one len(list) - 1).
  3. Compare element \(n\) with \(n + 1\), that is, the current element with the next element.
  4. If \(n\) be less than \(n + 1\), proceed to the next comparison.
  5. If it be not less, but greater, then is the list not sorted. Return False here.
  6. If thou dost reach the end, then is the list sorted, return True.

Svaret (i Python) 
def is_sorted(the_list):
    for i in range(len(the_list) - 1):
        if the_list[i] > the_list[i + 1]:
            return False
    return True

Verily, the answer (in the tongue of Python) doth lie thus:

def is_sorted(the_list):
    for i in range(len(the_list) - 1):
        if the_list[i] > the_list[i + 1]:
            return False
    return True

Medium Task the Eighth - To Shuffle

Devise an algorithm that doth mingle a list of things. There be many ways to accomplish this, yet a goodly method is that which is called a Fisher-Yates shuffle algorithm. More upon this matter mayst thou find here Wikipedia.

Test Data
  • ["a", "b", "c", "d", "e"] → can become, forsooth, ["c", "e", "a", "d", "b"]
  • [1, 2, 3, 4, 5, 6] → can become, forsooth, [4, 1, 6, 3, 2, 5]
  • ["apple", "banana", "orange"] → can become, forsooth, ["orange", "apple", "banana"]
  • ["x"] → doth remain as ["x"]
  • [] → doth remain as []

Hark, how it doth operate:

Algoritmen
  1. Create a function that doth receive the list of numbers.
  2. Create a new, empty list which shall hold the mingled result.
  3. Employ a random to choose a chance index within the list.
  4. Add this element unto the empty list and delete it from the old.
  5. Return the new list from the function.

Svaret (i Python) 
import random

def shuffle(the_list):
    shuffled = []

    while len(the_list) > 0:
        i = random.randrange(0, len(the_list))
        shuffled.append(the_list[i])
        the_list.pop(i)

    return shuffled

Medium Task 9 - Bogo-sort

In this task, thou shalt craft a (for all intents and purposes) dreadful, yet most simple sorting algorithm. ‘Tis exceedingly poor when it cometh to large lists (it shall take an age with more than 12-13 items). In Level 2, we shall devise a better sorting algorithm, bubble-sort.

Test Data
  • [3, 1, 2] → [1, 2, 3]
  • [5, 4, 3, 2, 1] → [1, 2, 3, 4, 5]
  • [10, 7, 8, 2] → [2, 7, 8, 10]
  • [1, 1, 1] → [1, 1, 1]
  • [9, 3, 6, 3, 9] → [3, 3, 6, 9, 9]
  • [0, -1, 4, -2] → [-2, -1, 0, 4]

The Algorithm doth function thus:

Algoritmen
  1. Create a function that doth receive the list of unsorted numbers.
  2. Shuffle the list by chance (use the shuffle from task 8).
  3. Check if the list is sorted (use the check thou didst make in task 7).
  4. If the list be not sorted, repeat steps 2 and 3.
  5. Repeat until the list is sorted, then return.

Simply explained: bogo-sort doth mix the whole list and hopeth that it is sorted.

Gru bogo sort meme
Prithee, read of Big O notation in Level 2.

Hark! Perchance employ shuffle from task eight to fashion an unsorted list for thine algorithm.

Svaret (i Python) 
def bogo_sort(the_list):
    while not is_sorted(the_list):
        the_list = shuffle(the_list)
    return the_list

Verily, the answer (in the tongue of Python) doth present itself thus:

def bogo_sort(the_list):
    while not is_sorted(the_list):
        the_list = shuffle(the_list)
    return the_list

Hard Task the Tenth, Part A - To Seek for Text - “Substring” (Most Difficult!)

Devise ye an algorithm that may discover a keyword within text. That is to say, shouldst thou possess a sentence such as hello there, thou shalt return True with the keyword hello, and False with a keyword like hahah. This algorithm shall function withal, regardless of input and output.

Employ the text-data hereunder to assay if thine algorithm doth function aright.

Test-data for algoritme:
  • hello there everyone with there = True
  • hello there everyone with ever = True
  • hello there everyone with then = False
  • qwecvyufavsjekkftyergwcery with sjekk = True

Tips til framgangsmåte
  1. Create a function that doth receive two strings, data and søkeord.
  2. Employ a for-loop with range to traverse the text.
  3. Here ‘tis most vital to consider how far the loop shall proceed.
  4. Create a temporary variable which doth declare if the søkeord hath been found, set it to True by default.
  5. Use yet another for-loop with range to compare where thou art in the text with the søkeord.
  6. If aught in the søkeord doth not match where thou dost check now, set the temporary variable to True and break out of the inner loop.
  7. If thou dost reach the end of the text without finding any match, return False.

Svaret (i Python) 
def search(data, word): 
    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Verily, the answer (in the tongue of Python) doth lie thus:

def search(data, word): 
    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True
        
    return False

Easy Task 10b

Add, I pray thee, yet another check to ensure the keyword doth not exceed the length of the sentence itself.

Tips til framgangsmåte
  • Add this check ere the for-loop doth begin.

Svaret (i python) 
def search(data, word): 
    if len(word) > len(data):
        return False

    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Lo, the answer (in the tongue of Python)

def search(data, word): 
    if len(word) > len(data):
        return False

    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True
        
    return False

Hard Task Eleven – Reversing of Words in Sentence (Difficult)

Recall ye back unto Task Five concerning the reversing of a sentence. Amend (or begin anew), to craft an algorithm that doth reverse each single word within a sentence, and then joineth them once more.

Test-data for algoritme:
  • hello there everyone doth become olleh ereht enoyreve
  • This is the way it goes! doth become sihT si eht yaw ti !seog
  • does this racecar go? of course! doth become seod siht racecar ?og fo !esruoc

Tips til framgangsmåte
  1. Create a function that doth receive a string.
  2. ❗Divide the text by employing .split(" ").
  3. Create a temporary variable to store the final value.
  4. Use a for-loop to traverse each word.
  5. Employ the same method for reversal as in Task 5
  6. Use the result and add it to the variable thou didst create in step 2.
  7. Return the final value

Svaret (i Python) 
def reverse_words(words):
    sentence = words.split(" ")
    output = ""

    for word in sentence:
        reversed_word = ""
        for i in range(0, len(word)):
            reversed_word = word[i] + reversed_word
        output += reversed_word + " "

    return output

Lo, the answer (in the tongue of Python)

def reverse_words(words):
    sentence = words.split(" ")
    output = ""

    for word in sentence:
        reversed_word = ""
        for i in range(0, len(word)):
            reversed_word = word[i] + reversed_word
        output += reversed_word + " "
    
    return output

➕ An Addendum:

Cracked Task E1 - To Expunge Duplicates from a List

Say thou hast a list which doth contain numbers, or text, yet we would expunge the duplicates. Forge an algorithm which shall expunge all duplicates from a list, and contain only the first of each unique element which doth exist within the said list.

Tips til framgangsmåte
  1. Begin with a function that doth receive a list
  2. Here shall we employ while-loops instead of for. ‘Tis made easier in Python, in other tongues for with counting variables doth function well.
  3. Create a counting variable idx (for index, or i)
  4. Use a while loop which shall proceed to the length of the list
  5. We shall compare the element at idx with all other elements
  6. Create a counting variable to jdx (or j) which doth begin at idx + 1
  7. Compare element at idx with element at jdx, if they be alike, delete jdx by using pop(jdx).
  8. HUSK! If thou dost delete the element, then the list doth become smaller, therefore must we step back a pace at jdx -= 1.
  9. Increase jdx by 1 and test the next element
  10. After the inner while-loop increase idx by 1 and the outer while-loop shall continue
  11. Return at length the list with deleted duplicates

Test Data
  • [1, 2, 2, 3, 1, 4, 3] → blir [1, 2, 3, 4]
  • ["a", "b", "a", "c", "b", "d"] → blir ["a", "b", "c", "d"]
  • [5, 5, 5, 5] → blir [5]
  • ["x", "y", "z", "x", "y", "x"] → blir ["x", "y", "z"]
  • [10, -1, 10, -1, 0, 0, 10] → blir [10, -1, 0]
  • ["apple", "apple', "banana", "orange", "apple", "orange", "pear", "apple"]
    • Shall yield: ["apple", "banana", "orange", "pear"]

Svaret (i Python) 
def delete_duplicates(the_list):
    idx = 0

    while idx < len(the_list):
        jdx = idx + 1

        while jdx < len(the_list):
            if the_list[idx] == the_list[jdx]:
                the_list.pop(jdx)
                jdx -= 1
            jdx += 1
        idx += 1

    return the_list

Lo, the answer (in the tongue of Python)

def delete_duplicates(the_list):
    idx = 0

    while idx < len(the_list):
        jdx = idx + 1

        while jdx < len(the_list):
            if the_list[idx] == the_list[jdx]:
                the_list.pop(jdx)
                jdx -= 1
            jdx += 1
        idx += 1
    
    return the_list

Cracked Task E2 - Counting Sort

Counting sort is one of the few sorting algorithms which doth function in what we call \(O(n)\) time. That is to say, it taketh not so very much longer than the number of elements in the list. Read more of Big O notation in Level 2.

It doth depend somewhat upon how great the span of elements is. If the least be 0 and the greatest be 100000 it may take a little time, so this may be used if the span of values is small. It worketh not for negative numbers, but one may modify the algorithm to work with negative numbers.

The algorithm worketh thus:

  • Find out how great the greatest element is, store the value of this element as \(k\).
  • Create a list which containeth \(k + 1\) elements, count.
  • Go through the unsorted list and use the value of the number as index. That is to say, if the element hath the value 47, then go to count[47] and increase it by 1.
  • Go through count the list and place the number of numbers as the index is. Example: There standeth 3 at index 1, so add three 1 numbers.

Testdata
Unsorted Data Sorted Data
[7, 3, 9, 1, 4, 3, 0, 6, 8, 6, 2, 1, 9, 0, 5, 4] [0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9]
[12, 13, 15, 0, 8, 15, 8, 5, 16, 8, 0, 20, 4, 9, 17, 16, 1, 3, 6, 15, 5, 2, 3, 1, 19, 13, 17, 5, 3, 10] [0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 8, 8, 8, 9, 10, 12, 13, 13, 15, 15, 15, 16, 16, 17, 17, 19, 20]

Tips til framgangsmåte
  1. Begin with the crafting of a function, taking a list as its input.
  2. Create an empty output list.
  3. Employ a for-loop to traverse the entirety of the list.
  4. Keep track of the highest value within a variable ere the for-loop.
  5. Update the highest value shouldst thou discover a greater.
  6. Create a list containing this number of zeroes, plus one. For example: should the greatest value be forty-seven, then create a list with forty-eight zeroes. This canst thou do with [0] * (maks + 1), or a for loop. Call it count.
  7. Traverse the list once more with a for-loop.
  8. Use the value of the element as index and increase by one. count[value] += 1
  9. Employ a for-loop to traverse the count list.
  10. Use the value that is at each index to add that number of numbers.
  11. Return the sorted list.

Svaret (i Python) 
def counting_sort(input_list):
    output = []

    max_val = input_list[0]

    for n in input_list:
        if n > max_val:
            max_val = n

    # dette vil lage en haug med nuller
    count = [0] * (max_val + 1)

    for n in input_list:
        count[n] += 1

    for i in range(len(count)):
        # bruk _ for å ignorere en verdi
        for _ in range(count[i]):
            output.append(i)

    return output