[ВИ] Колоквиумски задачи 2018

Црно - бело Problem 1 (0 / 0)
Предложете соодветна репрезентација и напишете ги потребните функции во Python за да се реши следниот проблем за кој една можна почетна состојба е прикажана на Слика 1:

enter image description here

Слика 1

“Tабла со димензии N x N се состои од бели и црни полиња. Со избор (кликнување) на едно поле се прави промена на бојата на тоа поле и на сите негови непосредни соседи (горе, долу, лево и десно) во спротивната боја, како што е прикажано на Слика 2. Целта е сите полиња на таблата да бидат обоени во бела боја. Потребно е проблемот да се реши во најмал број на потези т.е. со избирање (кликнување) на најмал можен број на полиња.”

enter image description here

Слика 2

За сите тест примери обликот на таблата е ист како на примерот даден на Слика 1. За секој тест пример се менува големината N на таблата, како и распоредот на црни и бели полиња на неа, соодветно.

Во рамки на почетниот код даден за задачата се вчитуваат влезните аргументи за секој тест пример. Во променливата N ја имате големината на таблата (бројот на редици односно колони); во променливата polinja ја имате бојата на сите полиња на таблата (по редослед: одлево - надесно, редица по редица, ако таблата ја гледате како матрица), каде 1 означува дека полето е обоено во црна, а 0 означува дека полето е обоено во бела боја.

Изборот на полиња (потезите) потребно е да ги именувате на следниот начин:

x: redica, y: kolona

каде _redica_ и _kolona_ се редицата и колоната на избраното (кликнатото) поле (ако таблата ја гледате како матрица).

Вашиот код треба да има само еден повик на функција за приказ на стандарден излез (print) со кој ќе ја вратите секвенцата на потези која треба да се направи за да може сите полиња на таблата да бидат обоени во бела боја. Треба да примените неинформирано пребарување. Врз основа на тест примерите треба самите да определите кое пребарување ќе го користите.


Почетен код:

#Vcituvanje na vleznite argumenti za test primerite
N = input()
polinja = map(int, input().split(','))
#Vasiot kod pisuvajte go pod ovoj komentar


=======================================================================================================================================


Црно - бело 2 Problem 2 (0 / 0)
Проблемот во оваа задача е идентичен како проблемот во претходната задача и важат истите ограничувања.

За разлика од Задача 1, овде треба да ја вратите секвенцата на потези која треба да се направи за да може сите полиња на таблата да бидат обоени во бела боја доколку се примени информирано пребарување. Врз основа на тест примерите треба самите да определите растојание за имплементација на евристичката функција.

=======================================================================================================================================

Дрва за одлучување Problem 3 (0 / 0)
Да се промени функцијата за предвидување, така што при изминувањето ќе печати информации за:

со која колона и вредност се споредува
за која е тековната вредност на тест примерокот за бараната колона
нивото на тековниот јазол во дрвото
која е следната гранка што ќе се изминува низ дрвото (True branch или False branch)
преостанатиот дел од дрвото што треба да се измине
празна линија
Потоа да се испечати истренираното дрво, да се вчита непознат тренинг примерок од стандардниот влез и истиот да се класифицира со новата функција за предвидување.

trainingData=[['twitter','USA','yes',18,'None'],
        ['google','France','yes',23,'Premium'],
        ['google','France','no',26,'Basic'],
        ['google','Macedonia','yes',13,'None'],
        ['pinterest','USA','yes',24,'Basic'],
        ['bing','France','yes',23,'Basic'],
        ['google','UK','no',21,'Premium'],
        ['facebook','New Zealand','no',12,'None'],
        ['facebook','UK','no',21,'Basic'],
        ['google','USA','no',24,'Premium'],
        ['twitter','France','yes',19,'None'],
        ['pinterest','USA','no',18,'None'],
        ['google','UK','no',18,'None'],
        ['bing','UK','yes',19,'Premium'],
        ['bing','Macedonia','no',10,'None'],
        ['facebook','Macedonia','no',16,'Basic'],
        ['bing','UK','no',19,'Basic'],
        ['pinterest','Germany','no',2,'None'],
        ['pinterest','USA','yes',12,'Basic'],
        ['twitter','UK','no',21,'None'],
        ['twitter','UK','yes',26,'Premium'],
        ['google','UK','yes',18,'Basic'],
        ['bing','France','yes',19,'Basic']]


# trainingData=[line.split('\t') for line in file('decision_tree_example.txt')]

class decisionnode:
      def __init__(self,col=-1,value=None,results=None,tb=None,fb=None):
         self.col=col
         self.value=value
         self.results=results
         self.tb=tb
         self.fb=fb

def sporedi_broj(row,column,value):
  return row[column]>=value

def sporedi_string(row,column,value):
  return row[column]==value

# Divides a set on a specific column. Can handle numeric
# or nominal values
def divideset(rows,column,value):
    # Make a function that tells us if a row is in
    # the first group (true) or the second group (false)
    split_function=None
    if isinstance(value,int) or isinstance(value,float): # ako vrednosta so koja sporeduvame e od tip int ili float
       #split_function=lambda row:row[column]>=value # togas vrati funkcija cij argument e row i vrakja vrednost true ili false
       split_function=sporedi_broj
    else:
       # split_function=lambda row:row[column]==value # ako vrednosta so koja sporeduvame e od drug tip (string)
       split_function=sporedi_string

    # Divide the rows into two sets and return them
    # set1=[row for row in rows if split_function(row)]  # za sekoj row od rows za koj split_function vrakja true
    # set2=[row for row in rows if not split_function(row)] # za sekoj row od rows za koj split_function vrakja false
    set1=[row for row in rows if split_function(row,column,value)]  # za sekoj row od rows za koj split_function vrakja true
    set2=[row for row in rows if not split_function(row,column,value)] # za sekoj row od rows za koj split_function vrakja false

    return (set1,set2)


# Create counts of possible results (the last column of
# each row is the result)
def uniquecounts(rows):
  results={}
  for row in rows:
     # The result is the last column
     r=row[len(row)-1]
     if r not in results: results[r]=0
     results[r]+=1
  return results


# Entropy is the sum of p(x)log(p(x)) across all
# the different possible results
def entropy(rows):
      from math import log
      log2=lambda x:log(x)/log(2)
      results=uniquecounts(rows)
      # Now calculate the entropy
      ent=0.0
      for r in results.keys():
            p=float(results[r])/len(rows)
            ent=ent-p*log2(p)
      return ent

def buildtree(rows,scoref=entropy):
      if len(rows)==0: return decisionnode()
      current_score=scoref(rows)

      # Set up some variables to track the best criteria
      best_gain=0.0
      best_criteria=None
      best_sets=None

      column_count=len(rows[0])-1
      for col in range(0,column_count):
            # Generate the list of different values in
            # this column
            column_values={}
            for row in rows:
                  column_values[row[col]]=1
                  # print row[col]
            # print
            # print column_values
            # Now try dividing the rows up for each value
            # in this column
            for value in column_values.keys():
                  (set1,set2)=divideset(rows,col,value)

                  # Information gain
                  p=float(len(set1))/len(rows)
                  gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)
                  # print set1, set2, gain
                  if gain>best_gain and len(set1)>0 and len(set2)>0:
                        best_gain=gain
                        best_criteria=(col,value)
                        best_sets=(set1,set2)

      # Create the subbranches
      if best_gain>0:
            trueBranch=buildtree(best_sets[0])
            falseBranch=buildtree(best_sets[1])
            return decisionnode(col=best_criteria[0],value=best_criteria[1],
                            tb=trueBranch, fb=falseBranch)
      else:
            return decisionnode(results=uniquecounts(rows))

def printtree(tree,indent=''):
      #level = 0
      # Is this a leaf node?
      if tree.results!=None:
            print str(tree.results)
      else:
            # Print the criteria
            print str(tree.col)+':'+str(tree.value)+'?'
            # Print the branches
            print indent+'T->',
            printtree(tree.tb,indent+'  ')
            print indent+'F->',
            printtree(tree.fb,indent+'  ')


def classify(observation,tree):
    if tree.results!=None:
        results=[(value,key) for key,value in tree.results.items()]
        results.sort()
        return results[0][1]
    else:
        vrednost=observation[tree.col]
        branch=None

        if isinstance(vrednost,int) or isinstance(vrednost,float):
            if vrednost>=tree.value: branch=tree.tb
            else: branch=tree.fb
        else:
           if vrednost==tree.value: branch=tree.tb
           else: branch=tree.fb

        return classify(observation,branch)


if __name__ == "__main__":
    referrer=input()
    location=input()
    readFAQ=input()
    pagesVisited=input()
    serviceChosen='Unknown'

    testCase=[referrer, location, readFAQ, pagesVisited, serviceChosen]

    # vasiot kod tuka

    drvo = buildtree(trainingData)
    printtree(drvo)
    klasifikacija = classify(testCase,drvo)
    print klasifikacija


=======================================================================================================================================


Патека во граф Problem 4 (0 / 0)
На сликата е даден ненасочен граф со неговите јазли и нивните меѓусебни растојанија.

enter image description here

За јазлите во графот не се познати локациите. Во рамки на вашиот код, јазлите дефинирајте ги точно со имињата дадени на сликата.

Треба да го решите проблемот на наоѓање на должината на најкратката патека помеѓу два јазли од графот, и притоа патеката да поминува низ еден "меѓујазел".

За секој тест пример се менуваат јазлите помеѓу кои треба да се најде најкратката патека и меѓујазелот низ кој треба да се помине. Во рамки на почетниот код даден за задачата се вчитуваат влезните аргументи за секој тест пример. Во променливите Pocetok и Kraj ги имате почетниот и крајниот јазел за најкратката патека која треба да ја најдете, а во Stanica го имате меѓујазелот низ кој треба да се помине.

Вашиот код треба да има само еден повик на функција за приказ на стандарден излез (print) со кој ќе ја вратите должината на најкратката патека помеѓу почетниот и крајниот јазел.