Table of Contents

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

náplň cvičení

Úkol 1 Inverzní permutace

Úkol 2: třídění karet

Uvažujme hrací karty .

Napište funkci, který vzestupně třídí karty podle jejich barvy a podle jejich hodnoty. 

cards = [  [3,"A"],  [3,"Q"],  [0,"2"],  [1,"10"]  ]

výsledek pro setřídění: 

[  [0, "2"],  [1, "10"],  [3, "Q"],  [3, "A"]  ]

Seřaďte toto pole: 

cards = [[0, 'Q'], [2, '6'], [1, 'K'], 
         [1, '8'], [2, '10'], [2, '4'], 
         [3, '4'], [0, '4'], [1, '3'], 
         [2, '5'], [0, 'K'], [3, 'A'], 
         [1, 'J'], [0, '3'], [0, '9']]

Úloha 3 Dekódování zprávy

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

Úloha 4 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] ]

domácí práce

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

Souřadnicový systém

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)

board = base.Board(size)
for p in board.board:
   if board.inBoard(p,0):
       board.board[p][0] = 1
board.saveImage("deska.png")

#chci zapsat hodnotu 3 na souradnici p,q
if board.inBoard(p,q):
   board.board[p][q] = 3

stones = base.loadStones("nejaky vstupni soubor")
for si in range(len(stones)):
   board = base.Board(10)  #velikost 10x10
   for i in range(len(stones[si])):
      p,q = stones[si][i]   #i-ta bunka si-teho kamene
      p += 10//3            #posuneme kamen doprosted hraci desky,
      q += 10//2            #abychom ho mohli cely vykreslit
      if board.inBoard(p,q):  #kontrola, ze i-ta bunka kamene je v hraci desce
          board.board[p][q] = 1  #zapiseme
   board.saveImage("kamen-{}.png".format(si))

for p in board.board:    #vsechny sloupce v hraci deske
    for q in board.board[p]:   #vsechny radky, ktere nalezi sloupci p
        print("Hodnota bunky ", p,q, " je ", board.board[p][q] )

Doporučený postup

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 rozmisteni 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()

Soubor base.py

b = base.Board(size)

stones = base.loadStones(soubor-s-kameny)

import copy
import math
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
        """
 
        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="m")
        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