Craft simple algorithms, aye!

Skip to content

Avast ye, this be a machine-translated text an’ may contain errors, aye!

Quote

“Algorithm”, a word used by programmers when they be wishin’ to keep mum ‘bout what they’ve done.

Algoritme?

What be a algorithm, aye?

An algorithm be a logical function that performs a given operation. So, ye can technically call a function that adds two numbers together an “algorithm”, but more often than not, an algorithm be somethin’ a bit more complicated than that. Oftentimes, algorithms be used to make operations that take a long time, faster.

Algorithm Meme

Must I be usin’ Python for these tasks, aye?

Nay! Ye can be usin’ any programm’n language ye fancy for these tasks.

Built-in libraries?

The idea in these tasks is to avoid using built-in libraries or special Python functions. For example, there’s a simple “one-liner” to reverse text: text[::-1], but here we want ye to try and solve such tasks without usin’ that. It may be that we mention a built-in function if the solution be a bit tricky to figure out. This will be marked with ❗.

In practice, it should be fully possible to solve all these tasks with if, for, while and common list operations.

How to “Design” an Algorithm?

Most times, algorithms be designed iteratively. What does this mean, aye?

1. ✅ Shiver me timbers, break the problem into smaller pieces, ye scurvy dogs!
  • First, think on what be most vital for the algorithm to function, aye.
    • Will it return a treasure? A boolean, perhaps? Or a list o’ booty?
    • Do ye need any helper functions, me hearties?

2. ❓ Be there any ‘edge-cases’, aye?
  • What happens if ye be tossin’ in an empty list or text, savvy?

3. ✅ Aye, start by just tryin’ to craft a solution

4. ✅ Aye, Check if the Algorithm Be Runnin’ Smoothly
  • Try a larger haul o’ input, does it take a long time, savvy?

5. ❓ Weigh anchor an’ consider yer solution, do ye need all the steps ye’ve taken?
  • Be all them if checks truly necessary, aye?
  • If ye be havin’ more than one for-loop, be there any clear ways to make this into one for-loop?
    • This be different if ye be havin’ nested loops or loops one after t’other. One after t’other be often avoidable, savvy?

6. ✅ Consider extreme scenarios with inputs:
  • Example with numbers: large numbers, small numbers, negative numbers
  • Text example: much text, many small words, extra spaces, large and small letters.

7. ❓ Be it o’ use mock code to grasp the logic better, aye?

Easy Task 1 - Discoverin’ if a List Holds a Given Number

Craft an algorithm (function) that finds out if a list be holdin’ a given number. It shall return True or False based on if the number exists within the list or not, aye.

Here be a list o’ 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. Bring in a list and a list value into a function. For this task, ‘tis numbers, but could be text as well.
  2. Use a for-loop to sail through the list.
  3. If the number be equal to the check number, return True.
  4. Should the for-loop be done and ye haven’t 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

Easy A Task - Summin’ the Booty

Craft a scheme t’ add up a list o’ numbers, aye.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], yields the answer 21.
  • [5, 1, 23, 68, 22, 13, 4], yields the answer 136.
  • [3, 3, -3, -3, 3] yields the answer 3. Perhaps ye can ignore the negative numbers and give the answer 9.

Tips til framgangsmåte
  1. Haul a list into a function, aye.
  2. Stash a temporary sum as 0.
  3. Use a for-loop to sail through the list.
  4. return the sum o’ the list, savvy?

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

Medium Task 3a - Highest Value in a List

Craft an algorithm that finds the largest value in a list, aye.

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

Tips til framgangsmåte
  1. Haul a list into a function, ye scurvy dog!
  2. Set a temporary value to the first item on the list.
  3. Use a for-loop to sail through the list and compare it to the value ye set in 2.
  4. If the value be larger, set the temporary value to the new value.
  5. return this temporary value, aye!

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

    return largest

Easy Task 3b - If the list be empty, aye?

Add a check to test if the list holds any treasures. If ‘tis empty, return None, savvy?

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

Easy Task 4 - Countin’ the Number o’ a Given Item in a List

Craft an algorithm that counts the number o’ a given item within a list, aye.

Test-data for algoritme:
  • ["apple", "banana", "orange", "apple", "apple", "banana"] with apple gives 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 gives the answer 8.
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] with dog gives the answer 3.
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] with 7 gives the answer 5.
  • ["red", "blue", "green", "red", "yellow", "red"] with red gives the answer 3.
  • [10, -2, -2, -2, 5, 10, 10, -2] with -2 gives the answer 4.

Tips til framgangsmåte
  1. Take in a list and a check-value in a function
  2. Begin with a temporary count value set to 0.
  3. Go through the list with a for-loop.
  4. If the element be equal to 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

Medium Task 5 - Reversin’ a string, text

Craft an algorithm that reverses a given string.

Test-data for algoritme:
  • Hello there! be comin’ ‘round as !ereht olleH.
  • heisann alle sammen be comin’ ‘round as nemmas ella nnasieh
  • Python be comin’ ‘round as nohtyP
  • racecar be comin’ ‘round as racecar
  • 12345abc be comin’ ‘round as cba54321
  • god morgen be comin’ ‘round as 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 text with a for-loop with range. Here ye can go through the list backwards, but ‘tis possible to solve this by goin’ forward 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 be a bit tricky, but it starts
    # at the end, goes (includin') to 0 (by writin'
    # -1 as the end), and counts down by 1 each time
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Should ye be so inclined, ye can use an algorithm that adds to the beginnin’ instead:

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

Medium Task 6 - Palindrome Algorithm

Craft an algorithm that checks if a given word be a palindrome, aye. Examples o’ palindromes be abba, racecar, regninger.

Tips til framgangsmåte
  1. Craft a function that takes text to check.
  2. Use a for-loop to check if the letters on each side of the text be matchin’.
  3. Return False if a letter doesn’t match, if all match (for-loop completes), return True.

Extra:
Be seein’ how ye can make the algorithm twice as swift?

Hint

Du trenger bare å sjekke halvparten!

The answer (in python) 
def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True
Faster algorithm

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 7 - Checkin’ if a List be Sorted

Craft an algorithm that checks if a list be sorted, aye. The easiest way to check this be to start from the beginnin’ and compare if the next item be “larger”. If an item ain’t “larger”, then the list be not sorted, savvy?

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

Tips til framgangsmåte
  1. Craft a function that takes in a list, aye.
  2. Use a for-loop to sail through the whole list (use range to the length o’ the list, minus 1 len(list) - 1).
  3. Compare element \(n\) with \(n + 1\), that be the current element with the next one.
  4. If \(n\) be less than \(n + 1\), move on to the next comparison, ye scurvy dog.
  5. If it ain’t less, but greater, then the list ain’t sorted. Return False here, savvy?
  6. If ye reach the end, then the list be sorted. Return True, arr!

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

Medium Task 8 - Shuffle

Craft a scheme to mix up a list o’ items, aye. There be many ways to do this, but a good ‘un be what they call a Fisher-Yates shuffle algorithm. Ye can read more ‘bout this here Wikipedia.

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

Aye, ‘tis how ‘er works:

Algoritmen
  1. Craft a function that takes in the list o’ numbers
  2. Craft a new empty list to hold the mixed result.
  3. Use a random to choose a random index in the list.
  4. Add this element to the empty list and delete it from the old one
  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, ye shall create a (practically) dreadful, but exceedingly simple sortin’ algorithm. ‘Tis a fearsome beast when it comes to large lists (it’ll take an eternity with more than 12-13 items). In Level 2, we shall craft a better sortin’ 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 be workin’ like so:

Algoritmen
  1. Craft a function that takes in the list o’ unsorted numbers.
  2. Shuffle the list at random (use the shuffle from task 8, ye scallywag).
  3. Check if the list be sorted (use the check ye made in task 7).
  4. If the list ain’t sorted, repeat steps 2 and 3.
  5. Repeat ‘til the list be sorted, then return.

Simply put: bogo-sort mixes the whole list and hopes it be sorted.

Gru bogo sort meme
Read about Big O notation in Level 2.

Aye, be usin’ shuffle from task 8 to craft a disordered list for yer algorithm, savvy?

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

Hard Task 10a - Seekin’ Text - “substring” (Shiver me timbers!)

Craft a scheme to find a keyword within text, aye. That be, if ye have a sentence like hello there, ye’ll return True with the keyword hello, and False with a keyword like hahah. This scheme shall work no matter the input or output, savvy?

Use the text-data below to test if yer scheme be workin’ proper.

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

Tips til framgangsmåte
  1. Craft a function that takes two strings, data and keyword.
  2. Use a for-loop with range to sail through the text.
  3. Here ‘tis important to ponder how far the loop shall go.
  4. Create a temporary variable that says whether the keyword has been found, set it to True by default.
  5. Use yet another for-loop with range to compare where ye be in the text with the keyword.
  6. If somethin’ in the keyword don’t match where ye check now, set the temporary variable to True and break out o’ the inner loop.
  7. If ye reach the end o’ the text without findin’ anythin’, 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

Easy Task 10b

Add also an extra check to be sure the keyword ain’t longer than the sentence, aye.

Tips til framgangsmåte
  • Add this check before the for loop, aye.

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

Hard Task 11 - Reversin’ o’ Words in a Sentence (Difficult)

Recall back to Task 5 ‘bout reversin’ a sentence. Alter (or start anew), and craft an algorithm that reverses each single word in a sentence, then stitches ‘em back together.

Test-data for algoritme:
  • hello there everyone be comin’ ‘round as olleh ereht enoyreve
  • This is the way it goes! be turnin’ into sihT si eht yaw ti !seog
  • does this racecar go? of course! be shapin’ up as seod siht racecar ?og fo !esruoc

Tips til framgangsmåte
  1. Create a function that takes a string as input.
  2. ❗Split the text using .split(" ").
  3. Create a temporary variable to store the final value.
  4. Use a for-loop to go through each word.
  5. Use the same method for reversing as in Task 5
  6. Use the result and add it to the variable you created 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

➕ Avast Ye:

Cracked Task E1 - Be Ridin’ o’ Duplicates from a List

Avast, say ye have a list containin’ numbers, or text, but we be wantin’ to be rid o’ the duplicates. Craft an algorithm that be scrubbin’ all duplicates from a list, leavin’ only the first o’ each unique element that exists within the list.

Tips til framgangsmåte
  1. Begin with a function that takes in a list
  2. Here we shall use while-loops instead of for. It makes it easier in Python, in other languages for with counter variables works fine.
  3. Create a counter variable idx (for index, or i)
  4. Use a while loop that shall go to the length of the list
  5. We will compare the element at idx with all other elements
  6. Create a counter variable to jdx (or j) that starts at idx + 1
  7. Compare element at idx with element at jdx, if they be the same, delete jdx by using pop(jdx).
  8. REMEMBER! If ye be deletin’ the element, the list gets smaller, therefore we must step back one by 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 will continue
  11. Return in the end the list with deleted duplicates

Test Data
  • [1, 2, 2, 3, 1, 4, 3] → becomes [1, 2, 3, 4]
  • ["a", "b", "a", "c", "b", "d"] → becomes ["a", "b", "c", "d"]
  • [5, 5, 5, 5] → becomes [5]
  • ["x", "y", "z", "x", "y", "x"] → becomes ["x", "y", "z"]
  • [10, -1, 10, -1, 0, 0, 10] → becomes [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

Cracked Task E2 - Counting Sort

Counting sort be one o’ the few sortin’ algorithms that works in what we call \(O(n)\) time. Aye, it don’t take much longer than the number o’ items in the list. Read more ‘bout Big O notation in Level 2.

It depends a bit on how large the range o’ items be. If the smallest be 0 and the largest be 100000, it can take a bit o’ time, so this can be used if the range o’ values be small. It don’t work for negative numbers neither, but ye can modify the algorithm to work with negative numbers.

The algorithm works like this:

  • Find out how large the largest item be, store the value o’ this item as \(k\).
  • Create a list that contains \(k + 1\) items, count.
  • Go through the unsorted list and use the value o’ the number as the index. Aye, if the item has the value 47, ye go to count[47] and increase it by 1.
  • Go through the count list and place the number o’ numbers as the index be. Example: There be 3 at index 1, so ye 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 by craftin’ a function with a list as input, aye.
  2. Forge an empty output list.
  3. Use a for-loop to sail through the whole list.
  4. Keep track o’ the highest value in a variable before the for-loop, savvy?
  5. Update the highest value if ye find somethin’ larger.
  6. Forge a list containin’ this many zeros + 1. Example: highest value be 47, then ye forge a list with 48 zeros. Ye can do this with [0] * (maks + 1), or a for loop. Call it count.
  7. Sail through the list once more with a for-loop.
  8. Use the value o’ the element as index and increase by 1. count[value] += 1
  9. Use a for-loop to sail through the count list.
  10. Use the value that be on each index to add that many 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

    # this'll create a pile o' nothin's
    count = [0] * (max_val + 1)

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

    for i in range(len(count)):
        # use _ to ignore a value
        for _ in range(count[i]):
            output.append(i)

    return output