Mavzu: Crossword generator ishlab chiqish

Tahlil qiluvchi xulosa.

import sys

from PIL import Image, ImageDraw, ImageFont

from crossword import *

class CrosswordCreator:

def __init__(self, crossword):

"""

Yangi CSP krossvord yaratish.

"""

self.crossword = crossword

self.domains = {

var: self.crossword.words.copy() for var in self.crossword.variables

}

def letter_grid(self, assignment):

"""

Berilgan topshiriqni ifodalovchi 2D massivni qaytarish.

"""

letters = [

[None for _ in range(self.crossword.width)]

for _ in range(self.crossword.height)

]

for variable, word in assignment.items():

direction = variable.direction

for k in range(len(word)):

i = variable.i + (k if direction == Variable.DOWN else 0)

j = variable.j + (k if direction == Variable.ACROSS else 0)

letters[i][j] = word[k]

return letters

def print(self, assignment):

"""

Terminalga krossvord topshirig'ini chop etish.

"""

letters = self.letter_grid(assignment)

for i in range(self.crossword.height):

for j in range(self.crossword.width):

if self.crossword.structure[i][j]:

print(letters[i][j] or " ", end="")

else:

print("█", end="")

print()

def save(self, assignment, filename):

"""

Krossvord topshirig'ini rasm fayliga saqlash.

"""

cell_size = 100

cell_border = 2

interior_size = cell_size - 2 * cell_border

letters = self.letter_grid(assignment)

# Bo'sh tuval yaratish

img = Image.new(

"RGBA",

(self.crossword.width * cell_size, self.crossword.height * cell_size),

"black",

)

font = ImageFont.truetype("assets/fonts/OpenSans-Regular.ttf", 80)

draw = ImageDraw.Draw(img)

for i in range(self.crossword.height):

for j in range(self.crossword.width):

rect = [

(j * cell_size + cell_border, i * cell_size + cell_border),

(

(j + 1) * cell_size - cell_border,

(i + 1) * cell_size - cell_border,

),

]

if self.crossword.structure[i][j]:

draw.rectangle(rect, fill="white")

if letters[i][j]:

w, h = draw.textsize(letters[i][j], font=font)

draw.text(

(

rect[0][0] + ((interior_size - w) / 2),

rect[0][1] + ((interior_size - h) / 2) - 10,

),

letters[i][j],

fill="black",

font=font,

)

img.save(filename)

def solve(self):

"""

Tugun va yoy izchilligini ta'minlash va keyin CSP ni hal qilish.

"""

self.enforce_node_consistency()

self.ac3()

return self.backtrack(dict())

def enforce_node_consistency(self):

"""

Har bir oʻzgaruvchi tugunga mos keladigan tarzda “self.domains” ni yangilash.

(O'zgaruvchining unaryiga mos kelmaydigan qiymatlarni olib tashlanadi

cheklovlar; bu holda, so'zning uzunligi.)

"""

for variable, words in self.domains.items():

# So'zlarning nusxasini aylantiriladi, chunki to'plam o'zgartiriladi

for word in words.copy():

# Ketma-ket qatorga sig'maydigan so'zlarni olib tashlanadi

if len(word) != variable.length:

self.domains[variable].remove(word)

def revise(self, x, y):

"""

`x` yoyi o`zgaruvchisini `y` o`zgaruvchisiga moslashtiriladi.

Buning uchun “self.domains[x]” dan hech qanday qiymat yoʻq qiymatlarni olib tashlanadi

`self.domains[y]` ichidagi `y` uchun mumkin bo'lgan mos qiymat.

Agar `x` domeniga qayta ko'rib chiqilgan bo'lsa, True qiymatini qaytariladi; qaytish

Agar qayta ko'rib chiqilmagan bo'lsa, noto'g'ri.

"""

# Qayta ko'rib chiqilgan yoki yo'qligini ko'rsatish uchun o'zgaruvchini ishga tushiriladi

revised = False

# Bir-biriga o'xshashlik indeksini olinadi

lapx, lapy = self.crossword.overlaps[x, y]

# X domenidagi har bir so'z uchun

for wordx in self.domains[x].copy():

# Agar uning indekslangan harfi y dagi indekslangan harfga mos kelmasa, so'zni olib tashlanadi

if wordx[lapx] not in [wordy[lapy] for wordy in self.domains[y]]:

revised = True

self.domains[x].remove(wordx)

return revised

def ac3(self, arcs=None):

"""

“Self.domains” ni har bir oʻzgaruvchi yoyga mos keladigan tarzda yangilanadi.

Agar “yoylar” Yo‘q bo‘lsa, muammodagi barcha yoylarning dastlabki ro‘yxatidan boshlanadi.

Aks holda, izchil qilish uchun yoylarning dastlabki roʻyxati sifatida “arcs” dan foydalaniladi.

Agar yoy izchilligi bajarilsa va domenlar bo'sh bo'lmasa, True qiymatini qaytariladi;

Agar bir yoki bir nechta domenlar bo'sh bo'lsa, False qiymatini qaytariladi.

"""

if arcs:

queue = set(arcs)

else:

# Navbat bir-biriga o'xshash bo'lgan o'zgaruvchan misollar majmuasiga teng bo'ladi

queue = {

varz for varz, overlap in self.crossword.overlaps.items() if overlap

}

while queue:

x, y = queue.pop()

if self.revise(x, y):

# Agar biz x ning barcha so'zlarini olib tashlagan bo'lsak, unda hech qanday yechim yo'q

if len(self.domains[x]) == 0:

return False

# X qayta ko'rib chiqilganligi sababli, biz barcha qo'shnilarni qayta ko'rib chiqish uchun qo'shamiz

for z in self.crossword.neighbors(x) - {y}:

queue.add((z, x))

# Yechim mavjudligini ko'rsatish uchun

return True

def assignment_complete(self, assignment):

"""

Agar "topshiriq" tugallangan bo'lsa, "True" qiymatini qaytariladi (ya'ni, har biriga qiymat beradi

krossvord o'zgaruvchisi); aks holda False ni qaytariladi.

"""

if len(self.domains) == len(assignment):

return True

return False

def consistent(self, assignment):

"""

Agar “topshiriq” izchil boʻlsa (yaʼni, soʻzlar krossvordga toʻgʻri kelsa) “True” qiymatini qaytariladi

qarama-qarshi belgilarsiz boshqotirma); aks holda False ni qaytariladi.

"""

# Har bir o'zgaruvchida noyob so'z borligini tekshiriladi

if len(assignment) != len(set(assignment.values())):

return False

# Har bir bir-biriga o'xshash o'zgaruvchilar bir xil o'xshash belgilarga ega ekanligini tekshirish

for varz, overlap in self.crossword.overlaps.items():

if overlap:

x, y = varz

if x in assignment.keys() and y in assignment.keys():

# so'zlar uzunligi ketma-ketlik ketma-ketligiga mos kelishini tekshiriladi

if len(assignment[x]) != x.length or len(assignment[y]) != y.length:

return False

lapx, lapy = overlap

if assignment[x][lapx] != assignment[y][lapy]:

return False

return True

def order_domain_values(self, var, assignment):

"""

`var` domenidagi qiymatlar roʻyxatini quyidagi tartibda qaytariladi

qo'shni o'zgaruvchilar uchun ular istisno qiladigan qiymatlar soni.

Ro'yxatdagi birinchi qiymat, masalan, bitta bo'lishi kerak

bu "var" ning qo'shnilari orasida eng kam qiymatlarni istisno qiladi.

"""

counts = {value: 0 for value in self.domains[var]}

# Eng kam cheklovchi qiymatlar evristik

for word in self.domains[var]:

for neighbor in self.crossword.neighbors(var):

if neighbor in assignment.keys():

continue

lapv, lapn = self.crossword.overlaps[var, neighbor]

for wordn in self.domains[neighbor]:

# Agar so'z qo'shni o'zgaruvchining chiqarilishiga sabab bo'lsa, 1 ga takrorlang

if word[lapv] != wordn[lapn]:

counts[word] += 1

return sorted(self.domains[var], key=lambda word: counts[word])

def select_unassigned_variable(self, assignment):

"""

Tayinlanmagan oʻzgaruvchini “topshiriq” tarkibiga kirmagan holda qaytariladi.

Qolgan qiymatlarning minimal soniga ega o'zgaruvchini tanlanadi

uning domenida. Agar tenglik bo'lsa, eng yuqori o'zgaruvchini tanlanadi

daraja. Agar tenglik mavjud bo'lsa, bog'langan o'zgaruvchilarning har biri qabul qilinadi

qiymatlarni qaytarish.

"""

# Minimal qolgan qiymatlar (MQQ)

# Barcha tayinlanmagan o'zgaruvchilarni domen uzunligi bo'yicha tartiblanadi

unassigned = sorted(

self.domains.keys() - assignment.keys(),

key=lambda var: len(self.domains[var]),

)

# Bog'lanishlarni tekshirish

same = []

for var in unassigned:

if len(self.domains[var]) == len(self.domains[unassigned[0]]):

same.append(var)

# Ro'yxat tartiblanganligi sababli, biz bog'lanmagan ro'yxatni topsak, biz uni buzishimiz mumkin

else:

break

# Evristik daraja

# Bog'langan taqdirda, eng katta qo'shnilari bo'lganini tanlanadi

highest_degree = unassigned[0]

for var in same:

if len(self.crossword.neighbors(var)) > len(

self.crossword.neighbors(highest_degree)

):

highest_degree = var

return highest_degree

def inference(self, assignment):

arcs = set()

for varz, overlap in self.crossword.overlaps.items():

if overlap:

x, y = varz

if x not in assignment:

arcs.add((x, y))

self.ac3(arcs)

for var, domain in self.domains.items():

if var not in assignment.keys():

if len(domain) == 1:

assignment[var] = domain[0]

return assignment

def backtrack(self, assignment):

"""

Backtracking Search-dan foydalanib, qisman topshiriqni kiritiladi

krossvord va agar iloji bo'lsa, to'liq topshiriqni qaytariladi.

`tayinlash` - o'zgaruvchilardan (kalitlar) so'zlarga (qiymatlarga) xaritalash.

Agar topshiriq bo'lmasa, None ni qaytariladi.

"""

# Asosiy holat

if self.assignment_complete(assignment):

return assignment

# Rekursiv holat

var = self.select_unassigned_variable(assignment)

for value in self.order_domain_values(var, assignment):

copy_assignment = assignment.copy()

copy_assignment[var] = value

# qiymat qo'shish nomuvofiqlikka olib kelmaydi

if self.consistent(copy_assignment):

#Sekinroq

# copy_assignment = self.inference(copy_assignment)

result = self.backtrack(copy_assignment)

if result:

return result

def main():

# Foydalanishni tekshirish

if len(sys.argv) not in [3, 4]:

sys.exit("Usage: python generate.py structure words [output]")

# Buyruqlar qatori argumentlarini tahlil qilish

structure = sys.argv[1]

words = sys.argv[2]

output = sys.argv[3] if len(sys.argv) == 4 else None

# Generate crossword

crossword = Crossword(structure, words)

creator = CrosswordCreator(crossword)

assignment = creator.solve()

# Natijani chop etish

if assignment is None:

print("No solution.")

else:

creator.print(assignment)

if output:

creator.save(assignment, output)

if __name__ == "__main__":

main()

NATIJA:




Xulosa.
Ko'pchilik uchun foydali hobbi yoki shunchaki katta rivojlanayotgan faoliyat bu krossvordlarni echishdir. U xotirani tarbiyalaydi, miya faoliyatini yaxshilaydi va so'z boyligini kengaytiradi. Krossvord insonlar vaqtini qiziqarli o’tkazish bilan miya faoliyatini zivojlantirishga yordam beradi. Chet tilida tuzilga krossvordlar esa insonlarga chet tili so’zlarini iboralarini tezroq yodlashga ulardan foydalanishga yordam beradi. Shuningdek yosh bolalar uchun ham krossvordlar rasmlar orqli so’zlarmi yodlashga ulardan foydalanishga yordam beradi.

Foydalanilgan adabiyotlar.

1. 
   www.google.com
   
2. 
   https://en.wikipedia.org/wiki/Crossword#Cipher_crosswords
   
3. 
   https://uz.wikipedia.org/wiki/Python
   
4. 
   www.github.com