Studoši

Može netko podijelit zadatak i pitanja s blica?

Kod za razvojno okruzenje:

import sys
import array
from typing import Union, List, Iterable


class ArrView:
    """
    Helper class used for indexing the adjacency matrix.
    Serves as a view of a row, column or any part of the adjacency matrix, although
    it can be used for any 1D array/list.
    """
    def __init__(self, arr: array.array, arr_slice: Union[slice, range]):
        self._arr = arr
        if isinstance(arr_slice, slice):
            self._slice_range = range(*arr_slice.indices(len(self._arr)))
        elif isinstance(arr_slice, range):
            self._slice_range = arr_slice
        else:
            raise NotImplementedError("Must provide a slice or range object to the ArrView constructor")
        
    def __len__(self):
        """
        Return the length of the view.
        """
        return len(self._slice_range)
    
    def __getitem__(self, pos: Union[int, slice]):
        """
        Method to override indexing for the view. Fetches the values from the underlying array.
        Args:
            pos (int | slice): Position of the value/values to fetch.
        
        Returns:
            int: Value at the 'pos' if it was an int.
            or
            ArrView: A subview if 'pos' was a slice.
            
        If passed an int, it will return a value at the specified position.
        If passed a slice object, it will return another ArrView object which will be a subview
        into the view, but will still use the underlying array to fetch the values. If passed
        anything else will return NotImplemented.
        """
        if isinstance(pos, int):
            return self._arr[self._slice_range[pos]]
        if isinstance(pos, slice):
            return ArrView(self._arr, self._slice_range[pos])
        return NotImplemented
    
    def __setitem__(self, pos: Union[int, slice], val: Union[int, Iterable[int]]):
        """
        Set the value/values at the specified position/positions.

        Args:
            pos (int | slice): Position(s) of value/values to set.

        Sets the values in the underlying array.
        If passed an int as the position argument, it expects the value argument to be an int as well
        and sets the value at the specified position.
        If passed a slice and iterable of ints as value (i.e. list of ints), sets the values
        indexed by the slice to the values provided in the 'val' argument.
        If passed a slice as position and int as value, sets all of the elements indexed by the
        slice to the specified int value. Otherwise, raises an exception.
        """
        if isinstance(pos, int):
            self._arr[self._slice_range[pos]] = val
        elif isinstance(pos, slice):
            val_range = self._slice_range[pos]
            if isinstance(val, int):
                val = [val] * len(val_range)
            for i, v in zip(val_range, val):
                self._arr[i] = v
        else:
            raise NotImplementedError('ArrView can only be indexed by an "int" or "slice" object.')
    
    def __iter__(self):
        """
        Enables iteration over the view (for-each style).

        Return an iterator over the array view. Enables the view to be used in
        a for-each loop, i.e. "for val in view: ... ".
        """
        for i in self._slice_range:
            yield self._arr[i]
    
    def as_list(self):
        """
        Return the view as a list of integers.
        """
        return [v for v in self]

    def __str__(self):
        """
        Return the string representation of the view, which is the representation
        of the list with the same values.
        """
        return str(self.as_list())

class AdjMatrix:
    """
    Helper class which implements a weighted adjacency matrix.
    Should hold zeros if there is no edge between nodes at an index
    or the weight of the edge if there is one.

    n_nodes (int): Number of nodes in the graph.

    Indexing with regular integers returns ArrView of rows (matrix[0] -> 0-th row).
    Indexing with tuples returns the values at the position in the matrix
    (matrix[0, 1] -> weight of the edge at position (0, 1)).
    """

    def __init__(self, n_nodes: int):
        self._data = array.array('i', [0] * (n_nodes * n_nodes))
        self.n_nodes = n_nodes
        
    def __len__(self):
        """
        Get the total number of elements in the matrix.
        """
        return self.n_nodes * self.n_nodes
    
    def getColumn(self, col_ind: int):
        """
        Get a column as a view.

        Args:
            col_ind (int): Index of the column.
        
        Returns:
            ArrView: View of the column.
        """
        return ArrView(self._data, slice(col_ind, None, self.n_nodes))
    
    def getRow(self, row_ind: int):
        """
        Get a row as a view.
        Same as A[row_ind].

        Args:
            row_ind (int): Index of the row.
        
        Returns:
            ArrView: View of the row.
        """
        n = self.n_nodes
        return ArrView(self._data, slice(row_ind * n, (row_ind + 1) * n))

    def getEdgeWeight(self, row_ind: int, col_ind: int) -> int:
        """
        Get the weight of the edge between the row_ind and col_ind nodes.
        Weight of the edge row_ind->col_ind.

        Args:
            row_ind (int): Row index (source node).
            col_ind (int): Column index (target node).
        """
        return self._data[row_ind * self.n_nodes + col_ind]
    
    def __getitem__(self, pos: Union[int, tuple]):
        """
        Enables indexing into the matrix with integers, tuples or slices.

        Args:
            pos (int | tuple): Position of the value/values to fetch.
        
        Returns:
            int | ArrView: Value/values at the specified position/s.
        
        If the argument is an int, fetches pos-th row, equivalent to getRow(pos).
        If the arugmnet is a tuple, fetches the weight of the edge between pos[0] and pos[1].
        Otherwise returns NotImplemented.
        """
        if isinstance(pos, int):
            return self.getRow(pos)
        if isinstance(pos, tuple):
            i, j = pos
            return self.getEdgeWeight(i, j)
        return NotImplemented
    
    def __setitem__(self, pos: Union[int, tuple], val: Union[int, Iterable[int]]) -> None:
        """
        Enables setting values by index.

        Args:
            pos (int, tuple): Position/s to set in the underlying array.
            val (int, Iterable[int]): Value/s to set.
        
        If the pos argument is a tuple, then the val should be an int and
        the method will set the value at the specified position in the matrix
        (weight of the edge pos[0]->pos[1]).
        If the pos is an int then sets the whole row, with ArrView
        handling the logic of setting the values.
        Otherwise, raises a NotImplemented error.
        """
        if isinstance(pos, tuple):
            i, j = pos
            self._data[i * self.n_nodes + j] = val
        elif isinstance(pos, int):
            self.getRow(pos)[:] = val
        else:
            raise NotImplementedError('AdjMatrix can only be indexed by an int, tuple or slice object.')
    
    def columns(self):
        """
        Fetches an iterator over the columns of the matrix.
        Enables "for col in A.columns(): ...".
        """
        for i in range(self.n_nodes):
            yield self.getColumn(i)
    
    def rows(self):
        """
        Fetches an iterator over the rows of the matrix.
        Enables "for row in A.rows(): ...".
        """
        for i in range(self.n_nodes):
            yield self.getRow(i)
    
    def __iter__(self):
        """
        Delegates to the 'rows' method.
        """
        return self.rows()

    def __str__(self) -> str:
        """
        Fetch the string representation of the matrix as a list of lists.
        """
        return str([row.as_list() for row in self])

class BellmanFordNode:
    """
    Helper class for solving problems with the BellmanFordAlgorithm.

    d (int): The current distance to a node.
    prev (BellmanFordNode): The previous node in the solution graph.
    """

    def __init__(self, d_value=sys.maxsize, prev_node=None):
        self.d = d_value
        self.prev = prev_node

class NegativeCycleError(Exception):
    """Class used to raise an error when a negative cycle is present in a graph"""
    pass

Kod koji treba nadopuniti:

class BellmanFord:
    """
    Class implementing static methods for solving graph problems
    using the Bellman-Ford algorithm.
    """

    @staticmethod
    def edges(W: AdjMatrix):
        """
        Fetch a iterable over the edges of the graph from its weighted adjacency matrix.

        Args:
            W (AdjMatrix): weighted adjacency matrix.
        
        Returns:
            Iterable[...] | Iterator: An iterable of any representation of an edge or an iterator.
        """
        ####################
        ## YOUR CODE HERE ##
        ####################
        # HINT: Koristite 'yield' operator ili izradite listu
        # bridova i nju vratite. Na Vama je da odaberete.
    
    @staticmethod
    def createInitialSolution(n_nodes: int) -> List[BellmanFordNode]:
        """
        Create the list which will hold the final solution to the problem
        we are solving with the Bellman-Ford algorithm and populate it with initial values.

        Args:
            n_nodes (int): Number of nodes in the graph for which we are solving.
        
        Returns:
            List[BellmanFordNode]: The starting point of the algorithm.
        """
        return [BellmanFordNode() for _ in range(n_nodes)]
    
    @staticmethod
    def solve(W: AdjMatrix, start: int) -> List[BellmanFordNode]:
        """
        Solve the specified problem using the Bellman-Ford algorithm.

        Args:
            W (AdjMatrix): The weighted adjacency matrix of the graph for which we are solving.
            start (int)  : The starting node.
        
        Returns:
            List[BellmanFordNode]: Solution to the problem, i.e. the list of
                                   distances to the nodes from the starting point
                                   and which nodes are chosen as predecessors for each node.

        Throws:
            NegativeCycleError: If there is a negative cycle in the graph.
        """
        D = BellmanFord.createInitialSolution(W.n_nodes)
        ####################
        ## YOUR CODE HERE ##
        ####################
        
        # HINT: Iteracija po bridovima se mora moci pozivati na sljedeci nacin:
        #     "for ... in BellmanFord.edges(W):"
        # Gdje "..." ovisi o tome kako implementirate staticku metodu edges i kako
        # zelite da Vam se varijabla/e zove/u.

Kod za testni primjer:

def revPath(solution: List[BellmanFordNode], to_node: int) -> List[int]:
    curr = to_node
    path = []
    while curr is not None:
        path.append(curr)
        node = solution[curr]
        curr = node.prev
    return path
    

W = AdjMatrix(9)
W[0] = [0, 1, 0, 0, 0, 0, 0, 0, 0]
W[1] = [0, 0, 0, 0, -5, 0, 0, 0, 0]
W[2] = [0, 0, 0, 1, 0, 0, 1, 1, 0]
W[3] = [2, 0, 0, 0, 4, 0, 0, 0, 1]
W[4] = [0, 0, 0, 0, 0, 4, 0, 0, 0]
W[5] = [0, 0, 0, 0, 0, 0, 0, 0, 0]
W[6] = [0, 0, 0, -1, 0, 0, 0, 0, 0]
W[7] = [0, 0, 0, 0, 0, 0, -1, 0, 0]
W[8] = [0, 0, 0, 0, 0, 1, 0, 0, 0]
D = BellmanFord.solve(W, 2)
assert revPath(D, 5) == [5, 8, 3, 6, 7, 2]

Marko218 def revPath(solution: List[BellmanFordNode], to_node: int) -> List[int]:
curr = to_node
path = []
while curr is not None:
path.append(curr)
node = solution[curr]
curr = node.prev
return path

Kako je ovo moguce? curr je malo int pa malo BellmanFordNode?

Marko218 ima netko mozda rjesenje?

W={‘a’:{‘a’:0, ‘b’:2, ‘c’:0, ‘d’:0},
‘b’:{‘a’:0, ‘b’:0, ‘c’:3, ‘d’:-1},
‘c’:{‘a’:-1, ‘b’:0, ‘c’:0, ‘d’:7},
‘d’:{‘a’:3, ‘b’:0, ‘c’:0, ‘d’:0}}
Poziv funkcije WFI(W,‘a’,‘d’) mora vratiti:

Zadatak WFI i pitalice iste kao kolega Marko218.

import random
from math import ceil, floor, log
from typing import List


class SkipList:
    """Class for skip list
    """

    def __init__(self, n: int = 10000, p: float = 0.5):
        """Creates skip list and initializes all the necessary
        parameters

        Args:
            n (int, optional): expected capacity. Defaults to 10000.
            p (float, optional): probability of jumping up by one level. Defaults to 0.5.
        """
        self.p = p
        self.n = n
        self.max_level = # TODO: fix calculation for max_level
        self.head = SkipNode(None)
        self.head.pointers = [None]*self.max_level
        self.histogram = self._createHistogram()

    def _createHistogram(self) -> List:
        """Creates histogram of degrees.

        Returns:
            List: histogram according to the third method from the lecture
        """
        H = [0]*(self.max_level+1)
        for i in range(1, self.max_level+1):
            H[i] = # TODO: fix value for the histogram
        return H
    
    def sampleLevel(self) -> int:
        """Randomly decides the height of the node,
        according to the histogram, using only one sample!

        Returns:
            int: returns valid randomly selected height
        """
        ctoss = random.randint(1, self.n)
        i = 1
        while # TODO: fix the condition for sampling!
            i += 1
        return i

    def insert(self, value: int) -> None:
        """Inserts an element into the skip list if it has not already existed.
        Duplicates are not allowed.

        Args:
            value (int): key to insert into the skip list
        """
        level = self.sampleLevel()

        pred_node = self._search(value)
        if pred_node.value == value:
            return
        succ_node = pred_node.pointers[0]

        new_node = SkipNode(value, pred_node=pred_node)
        new_node.pointers = [None]*level
        new_node.pointers[0] = succ_node

        #TODO: update all the pointers on necessary levels. 
        # Hint: Also use pred_node for backsearch over the levels to update. Or, use alternative way!


    def _search(self, value: int) -> SkipNode:
        """Searches for the element in a list

        Args:
            value (int): search key

        Returns:
            SkipNode: skiplist node containing the search key, if it exists.
            Otherwise it returns the last element of the skip list.
        """
        node = self.head
        curr_height = len(node.pointers)-1
        while curr_height >= 0:
            next_node = node.pointers[curr_height]
            if next_node is None or #TODO: add the missing condition here
                curr_height = curr_height-1
            else:
                node = next_node
        return node
    
    def search(self, value: int) -> SkipNode:
        """tidy wrapper around _search

        Args:
            value (int): search key to find

        Returns:
            SkipNode: Returns the found node or None.
        """
        node = self._search(value)
        if node.value == value:
            return node
        else:
            return None


    def __str__(self) -> str:
        """string representation of skip list - useful for debugging

        Returns:
            str: string representation
        """
        curr_node = self.head.pointers[0]
        str = ''
        while curr_node is not None:
            str = str + \
                f"(Node {curr_node.value},level={len(curr_node.pointers)}),"
            curr_node = curr_node.pointers[0]
        return str
    
class SkipNode:
    """Class for a node in skip list
    
    predecessor - pointer to predecessor node on THE lowest level.
    
    pointers - pointers to successors (over full height of the node)
    value - value stored in the node 
    """
    pointers, value, predecessor = None, None, None

    def __init__(self, value: int, pred_node: 'SkipNode' = None, succ_node: 'SkipNode' = None):
        """Creates skip node for skip list.
        
        Args:
            value (int): value to be stored
            pred_node (SkipNode, optional): predecessor node on the lowest level. Defaults to None.
            succ_node (SkipNode, optional): successor node on the lowest level. Defaults to None.
        """
        self.value = value
        self.pointers = [None]
        if pred_node is not None:
            pred_node.pointers[0] = self
            self.predecessor = pred_node
        if succ_node is not None:
            self.pointers[0] = succ_node
            succ_node.predecessor = self

njihov kod za testni primjer

random.seed(22)

a = SkipList(18, 0.6)
print(f'histogram={a.histogram}, max level={a.max_level}')
a.insert(12)
a.insert(18)
a.insert(16)
a.insert(18)
a.insert(281)
a.insert(-1)
a.insert(0)

print(a)

"""ispisuje:
histogram=[0, 8, 12, 15, 16, 17, 18], max level=6
(Node -1,level=1),(Node 0,level=2),(Node 12,level=1),(Node 16,level=1),(Node 18,level=1),(Node 281,level=1),
"""

random.seed(23)

a = SkipList(12, 0.5)
print(f'histogram={a.histogram}, max level={a.max_level}')
a.insert(12)
a.insert(18)
a.insert(16)
a.insert(18)
a.insert(281)
a.insert(-1)
a.insert(0)

print(a)

"""ispisuje:
histogram=[0, 6, 9, 11, 12], max level=4
(Node -1,level=2),(Node 0,level=2),(Node 12,level=1),(Node 16,level=1),(Node 18,level=1),(Node 281,level=1),
"""

izvinite što se sjebano kopiralo, ugl puno pomaže što uopće ne morate raditi ovaj TODO u insertu tak da ukupno morate cca 5 linija koda napisat, riješi se za 10 min ko zna gradivo, ko ne zna ko ja onda malčice duže

aerius Zašto ne treba TODO u insertu?

kod od preskocnih listi

gdje je TODO to treba napravit

MOD EDIT: isto kao aerius

Maddy Valjda ovisi o tome kako si implementirala metodu solve. Oni su ju zadali kao def solve(W: AdjMatrix, start: int) -> List[BellmanFordNode] što znači da vraća listu BellmanFordNode-ova. Kad pošaljem takvu listu revPath-u dobijem TypeError: list indices must be integers or slices, not BellmanFordNode error…

…zato što prilikom curr = node.prev bude tipa BellmanFordNode i u sljedećoj iteraciji node = solution[curr] više nema smisla.

# njihov revPath
def revPath(solution: List[BellmanFordNode], to_node: int) -> List[int]:
    curr = to_node
    path = []
    while curr is not None:
        path.append(curr)
        node = solution[curr]
        curr = node.prev
    return path

Možda nešto krivo gledam…Kolega je napisao istu napomenu DrEtva

edit: ako će sutra na Edgaru padati testovi onda ću returnati indexe umjesto Node-ova pa bi sve trebalo biti ok

Još nekom?

Sulejman
I meni isto, taman krenula pisati mail nekome

jer radi i bez toga

aerius da skuzio sam to al mislio sam da ima razlog neki

aerius ziher pa ti je radilo.. meni konsntantno daje 5 errora kak vrijednosti pokazivača nisu iste

Ima netko problem s WFI da mu je sve tocno ali postoje 2 razlicita najkraca puta sa istom udaljenošću i da u nihovom rješenju uzimaju onaj drugi pa je moje rješenje netočno iako ima istu udaljenost?

Može li se na vježbi uživo odustati od rješavanja zadatka/usmenog ispitivanja?

monte može

Popravljena verzija revPath-a za Bellman-Ford:

def revPath(solution: List[BellmanFordNode], to_node: int) -> List[int]:
    curr = solution[to_node]
    path = []
    while curr is not None:
        index = solution.index(curr)
        path.append(index)
        curr = curr.prev
    return path

Matt Je li to nova verzija u edgaru ili? Ispadao mi je tocno zad s prvom, a ovako baca error.

kako isključiti pahuljice?

Je li kome bilo pitanje za veličinu grafa? Google kaže da je broj bridova, a za točan su stavili da je broj vrhova.

Mauricius u pravu si, ali svejedno probaj koristiti bolji izvor od samo googla.

Komu da pišem mail?

viliml možeš kolegi asistentu