Table of Contents

Cvičení 8: Fronta, zásobník, objekty

Dekódování zprávy

TE*A*QYS***SEU****NI*O**

Flood fill

m=[
[0,0,1,0,0,1,0,0,0,0],
[0,0,1,0,0,1,0,0,0,0],
[0,0,1,1,0,1,0,0,0,1],
[0,0,1,0,0,0,1,0,1,0],
[0,0,1,0,0,0,0,1,0,0],
[0,0,1,1,0,1,0,0,0,0],
[0,0,1,0,1,1,1,1,0,0],
[0,0,1,0,0,1,0,1,1,1],
[0,0,1,0,0,1,0,0,0,0],
[0,0,1,0,0,1,0,0,0,0] ]

Fronta

Objekt komlexní číslo

Třídy pro komplexní čísla: 

class Complex:
    def __init__(self, real=0, imag=0):
        self.real = real
        self.imag = imag
 
    def amplitude(self):
        return (self.real*self.real + self.imag*self.imag)**(1/2)
 
    def add(self, rhs):
        self.real += rhs.real
        self.imag += rhs.imag
 
    def sub(self, rhs):
        self.real -= rhs.real
        self.imag -= rhs.imag
 
    def __repr__(self):
        sign = "+";
        if (self.imag < 0):
            sign = "-";
        return str(self.real) + sign + str(abs(self.imag)) + "i"
 
    def mul(self, rhs):
        r = self.real*rhs.real - self.imag*rhs.imag;
        i = self.real*rhs.imag + self.imag*rhs.real;
        self.real = r
        self.imag = i 
 
a = Complex()
print("a=",a)
 
b = Complex(1,-1)
print("b=",b)
 
a.add(b)
print("a=",a)
 
a.mul(b)
print("a=",a)
 
print("|a|=",a.amplitude())
print("|b|=",b.amplitude())

Témata k procvičení

Inverzní permutace

Domácí úkol

Lehká varianta

Příklad 1: vstupní kameny

Úkolem je vyplnit hrací desku o velikosti 4×4 (4-řádky, každý řádek 4 pole). Všechna řešení jsou:

Nápověda a pomocný program

Ukázka programu

python3 tile_easy.py 3 stones.txt solution.txt

2 0 
1 2 1 1 0 2 
0 0 1 0 0 1 -1 2 
2 1

0 0 3
0 1 3
0 2 1
1 0 3
1 1 2
1 2 4
2 0 2
2 1 2
-1 2 3

Kameny

stones = base.loadStones(filename)

for si in range(len(stones)):
   print("Stone ", si, " has ", len(stones[si]), " cells ") 
   stoneColor = si + 1    #toto je barva kamene, kterou zapisujeme do hraci desku
   for i in range(len(stones[si])):
      p,q = stones[si][i]
      print("Cell[",i,"] of stone ",si, " is ",p,q)

Takto bude vypadat typický program pro HW08: 

import base
import sys
 
#nacteni vstupnich parametru z prikazove radky do promennych size, inputFile, outputFile
size = int(sys.argv[1])
board = base.Board(size)
stones = base.loadStones(sys.argv[2])
 
#program hledajici rozmísteni kamenu, ktery svuj vysledek zapisuje do board.board
 
#vytvoreni, ci otevreni vystupniho souboru do handleru f
f=open(sys.argv[3], "w")
if reseni_exist:
  for p in board.board:
   for q in board.board[p]:
      f.write("{} {} {}\n".format(p,q,board.board[p][q]))
else:
  f.write("NOSOLUTION")
f.close()

base.py

Následující program si uložte do stejného adresáře jako program pro tuto úlohu. Uložte jej pod názvem base.py 

 
import copy
import math
#import random
from PIL import Image, ImageDraw
 
 
def loadStones(filename):
    f = open(filename,"r")
    stones = []
    for line in f:
        coords = list(map(int, line.rstrip().split()))
        if len(coords) > 0:
            stones.append( [] )
            for i in range(len(coords)//2):
                x = coords[2*i]
                y = coords[2*i+1]
                stones[-1].append([ x,y ] )
    return stones;
 
 
class Board:
    def __init__(self, size):
        self.size = size
        self.board = {}
 
        #create empty board as a dictionary
        self.b2 = {}
        for p in range(-self.size,self.size):
            for q in range(-self.size, self.size):
                if self.inBoard(p,q):
                    if not p in self.board:
                        self.board[p] = {}
                    self.board[p][q] = 0
 
                    if not q in self.b2:
                        self.b2[q] = {}
                    self.b2[q][p] = 0
 
        #this is for visualization and to synchronize colors between png/js
        self._colors = {}
        self._colors[-1] = "#fdca40" #sunglow
        self._colors[0] = "#ffffff" #white
        self._colors[1] = "#947bd3" #medium purple
        self._colors[2] = "#ff0000" #red
        self._colors[3] = "#00ff00" #green
        self._colors[4] = "#0000ff" #blue
        self._colors[5] = "#566246" #ebony
        self._colors[6] = "#a7c4c2" #opan
        self._colors[7] = "#ADACB5" #silver metalic
        self._colors[8] = "#8C705F" #liver chestnut
        self._colors[9] = "#FA7921" #pumpkin
        self._colors[10] = "#566E3D" #dark olive green
 
 
 
    def inBoard(self,p,q):
        """ return True if (p,q) is valid coordinate """
        return (q>= 0) and (q < self.size) and (p >= -(q//2)) and (p < (self.size - q//2))
 
 
    def rotateRight(self,p,q):
        pp = -q
        qq = p+q
        return pp,qq
 
    def rotateLeft(self, p,q):
        pp = p+q
        qq = -p
        return pp, qq
 
 
 
    def saveImage(self, filename):
        """ draw actual board to png. Empty cells are white, -1 = red, 1 = green, other values according to
            this list 
            -1 red, 0 = white, 1 = green 
        """
 
        cellRadius = 25
        cellWidth = int(cellRadius*(3**0.5))
        cellHeight = 2*cellRadius
 
        width = cellWidth*self.size + cellRadius*3
        height = cellHeight*self.size
 
        img = Image.new('RGB',(width,height),"white")
 
        draw = ImageDraw.Draw(img)
 
        lineColor = (50,50,50)
 
 
        for p in self.board:
            for q in self.board[p]:
                cx = cellRadius*(math.sqrt(3)*p + math.sqrt(3)/2*q) + cellRadius
                cy = cellRadius*(0*p + 3/2*q) + cellRadius
 
                pts = []
                for a in [30,90,150,210,270,330]:
                    nx = cx + cellRadius * math.cos(a*math.pi/180)
                    ny = cy + cellRadius * math.sin(a*math.pi/180)
                    pts.append(nx)
                    pts.append(ny)
                color = "#ff00ff" #pink is for values out of range -1,..10
                if self.board[p][q] in self._colors:
                    color = self._colors[self.board[p][q]]
 
                draw.polygon(pts,fill=color)
                pts.append(pts[0])
                pts.append(pts[1])
                draw.line(pts,fill="black", width=1)
                draw.text([cx-3,cy-3], "{} {}".format(p,q), fill="black", anchor="mm")
        img.save(filename)

Těžká varianta

newp, newq = board.rotateLeft(p,q)

newp, newq = board.rotateRight(p,q)

Ukázka rotace

Základní pozice kamene

1. rotace

2. rotace

3. rotace

4. rotace

5. rotace