<jupyter_start><jupyter_text>Exercise 1 One hundred ways to get to one hundred (more or less)Write a program that outputs all possibilities to generate the number 100 from the digits $1,2,3,4,5,6,7,8,9$ (in that order) either by putting a $+$, $-$, $*$, $/$, or nothing between the digits, e.g.\ $1+2+3-4+5+6+78+9=100$ or $1+23*4+56/7+8-9=100$.Usual arithmetic rules apply.How many possibilities exist?<jupyter_code>from pprint import  pprint
import doctest
operator=['','+','-','*','/']

eight='12345678'

from itertools import product

ct=0
# Iterate over all combinations of operators (5**8)
for eight_ops in product(operator,repeat=8):
    # Construct expression by mixing digits and operators
    c=[]
    for d,i in zip(eight,eight_ops):
        c.append(d+i)
    c.append('9')
    c=''.join(c)
    if (eval(c)==100):
        print("{:25}".format(c),end=" ")
        ct+=1
        if ct%4==0:
            print()
print()
print('total number of solutions:',ct)
# Constructing all expressions using generators and recursion

def iter_expressions(final_digit):
    # Generate all expressions constructed from 1,...,final_digit
    # and operators '','+','-','*','/'
    str_digit = str(final_digit)
    if final_digit==1:
        yield str_digit
    else:
        for expr in iter_expressions(final_digit-1):
            yield expr+str_digit
            for oper in "+-*/":
                yield expr +  oper + str_digit

all1=[]
for expr in iter_expressions(9):
    if eval(expr)==100:
        all1.append(expr)
print('total number of solutions:',len(all1))
#pprint(all1)
# Constructing all expressions using queues without recursion

from collections import deque

next_digit=dict(zip('123456789','234567890'))

def all_expressions(final_digit):
    final_digit = str(final_digit)
    expressions = []
    queue = deque("1")
    while queue:
        expr = queue.popleft()
        digit = expr[-1]
        if digit==final_digit:
            expressions.append(expr)
        else:
            digit = next_digit[digit]
            queue.append(expr+digit)
            for oper in '+-*/':
                queue.append(expr+oper+digit)
    return expressions
               
count = 0
all_2=[]
expressions = all_expressions(9)
for expr in expressions:
    if eval(expr)==100:
        all_2.append(expr)
        count += 1
print("Total number of expressions:",len(expressions))
print("Total number of solutions:",count)
pprint(all_2)<jupyter_output>Total number of expressions: 390625
Total number of solutions: 101
['123+45-67+8-9',
 '123+4-5+67-89',
 '123+4*5-6*7+8-9',
 '123-45-67+89',
 '123-4-5-6-7+8-9',
 '12+34+5*6+7+8+9',
 '12+34-5+6*7+8+9',
 '12+34-5-6+7*8+9',
 '12+34-5-6-7+8*9',
 '12+3+4+5-6-7+89',
 '12+3+4-56/7+89',
 '12+3-4+5+67+8+9',
 '12+3*45+6*7-89',
 '12+3*4+5+6+7*8+9',
 '12+3*4+5+6-7+8*9',
 '12+3*4-5-6+78+9',
 '12-3+4*5+6+7*8+9',
 '12-3+4*5+6-7+8*9',
 '12-3-4+5-6+7+89',
 '12-3-4+5*6+7*8+9',
 '12-3-4+5*6-7+8*9',
 '12*3-4+5-6+78-9',
 '12*3-4-5-6+7+8*9',
 '12*3-4*5+67+8+9',
 '12/3+4*5-6-7+89',
 '12/3+4*5*6-7-8-9',
 '12/3+4*5*6*7/8-9',
 '12/3/4+5*6+78-9',
 '1+234-56-7-8*9',
 '1+234*5*6/78+9',
 '1+234*5/6-7-89',
 '1+23-4+56+7+8+9',
 '1+23-4+56/7+8*9',
 '1+23-4+5+6+78-9',
 '1+23-4-5+6+7+8*9',
 '1+23*4+56/7+8-9',
 '1+23*4+5-6+7-8+9',
 '1+23*4-5+6+7+8-9',
 '1+2+34-5+67-8+9',
 '1+2+34*5+6-7-8*9',
 '1+2+3+4+5+6+7+8*9',
 '1+2+3-45+67+8*9',
 '1+2+3-4+5+6+78+9',
 '1+2+3-4*5+6*7+8*9',
 '1+2+3*4-5-6+7+89',
 '1+2+3*4*56/7-8+9',
 '1+2[...]<jupyter_text>Exercise 2 Eight queensThe game of chess is played on a checkered board consisting of 64 squares arranged on an 8 by 8 grid. Different types of pieces are placed on the board, each of which is allowed different types of moves. A piece can capture another piece (which is subsequently removed from the board) if it can move to the square occupied by the other piece in a single turn. Here, we are not really interested in the rules of the game, instead, we are only interested in the movements of the piece called  *queen*. The queen is the most powerfull piece in chess, it can move along the board in any direction, horizontally, vertically one or more squares. Thus any other piece placed in a straight horizontal, vertical, or diagonal line (with no intervening pieces) can be captured by the queen.The *eight queens* problem asks you to place as many queens as possible on a chessboard so that no queen can capture any other queen. (Note, that there cannot be more than 8 queens on an 8 by 8 chessboard, as this requires at least one row and column to contain more than one queen, each of which would be able to capture the other.)1. Write a program that finds and prints a solution for the eight queens problem, placing eight queens on the board in such a way that no queen can capture any other. (In chess, columns are labeled **a** to **h** (left to right) and rows **1** to **8** (bottom to top). You can print the positions as **a1**, **b5**, **c3** ... for the eight queens.)2. Make sure your program is able to  also solve the more general problem of placing $n$ queens on an $n\times n$ board.3. Modify your program to find *the total number of possible solutions* to the $n$ queens problem instead of a single solution. (You do not need to print all the solutions, just determine the number of possible solutions!) What is the smallest $n$, for which at least one solution exists? (For this exercise you do not need to print the individual solutions4. Depending on your approach and implementation, you can determine the {\em number of possible solutions} for the $n$ queens problems also for larger $n>8$ in a reasonable time. How large is $n$ allowed to be so that your algorithm finds the number of possible solution within a few seconds?*Hint:* Note, that there has to be exactly one queen in each of the columns. Thus, you can represent the positions of $n$ queens by a list/tuple of $n$ numbers. The first number indicates the row for the queen in column {\bf a}, the second indicates the row for the queen in column **b**, and so on.<jupyter_code>def show_board(positions):
    """ Display a chess board with queens
    >>> show_board([1,3,0,2])
    . Q . .
    . . . Q
    Q . . .
    . . Q .
    """
    n = len(positions)
    for col_idx in positions:
        row = ['.']*n
        row[col_idx] = 'Q'
        print(' '.join(row))

def show_positions(positions):
    """ show positions of pieces
    >>> show_positions([1,3,0,2])
    a2, b4, c1, d3
    """
    abc = 'abcdefghijklmnopqrstuvwxyz'
    s = ", ".join("{}{}".format(abc[c],r+1) for c,r in enumerate(positions))
    print(s)
doctest.run_docstring_examples(show_board,globals(),verbose=True)
doctest.run_docstring_examples(show_positions,globals(),verbose=True)
import itertools


def queens_conflict(positions):
    """ Determine whether queens on a chess board are in conflict
    >>> queens_conflict([1,3,0,2])
    False
    >>> queens_conflict([0,2,1,3])
    True
    """
    for c,r in enumerate(positions):
        for c0,r0 in enumerate(positions):
            if c0 == c:
                break
            if abs(c-c0) == abs(r-r0) or r==r0:
                return True
    return False
doctest.run_docstring_examples(queens_conflict,globals(),verbose=True)
# N queens solution using itertools.permutations

def n_queens_iter(n):
    number_of_solutions = 0
    for positions in itertools.permutations(range(n)):
        if not queens_conflict(positions):
            if number_of_solutions == 0:
                show_board(positions)
                show_positions(positions)
            number_of_solutions += 1
    return number_of_solutions

n_queens_iter(8)

import time
n = 9
p = time.perf_counter()
nos = n_queens_iter(n)
elapsed_time = time.perf_counter() - p
print("{} solutions found in {:2} seconds.".format(nos,elapsed_time))
# N queens solution using recursion - single solution

def n_queens_rec(positions,n):
    current_col = len(positions)
    if current_col == n:
        return positions
    for current_row in range(n):
        okay = True
        for col,row in enumerate(positions):
            if current_row == row or abs(row-current_row)==abs(col-current_col):
                okay = False
                break
        if okay:
            pos = n_queens_rec(positions+[current_row],n)
            if pos:
                return pos
    return None

positions = n_queens_rec([],18)
show_board(positions)
show_positions(positions)
 
# N queens solution using recursion - all solutions
  
def n_queens_rec_all(positions,n,all_solutions):
    current_col = len(positions)
    if current_col == n:
        all_solutions.append(positions)
        return 1
    else:
        number_of_solutions = 0
        for current_row in range(n):
            okay = True
            for col,row in enumerate(positions):
                if current_row == row or abs(row-current_row)==abs(col-current_col):
                    okay = False
                    break
            if okay:
                number_of_solutions += n_queens_rec_all(positions+[current_row],n,all_solutions)
        return number_of_solutions

all_solutions = []
nos = n_queens_rec_all([],8,all_solutions)
show_board(all_solutions[-1])
show_positions(all_solutions[-1])
print("Number of solutions:",nos)
import time
n = 10
p = time.perf_counter()
all_solutions = []
nos = n_queens_rec_all([],n,all_solutions)
show_board(all_solutions[-1])
show_positions(all_solutions[-1])
elapsed_time = time.perf_counter() - p
print("{} solutions found in {:2} seconds.".format(nos,elapsed_time))
# Optimized solution using flags to indicate availability of each row/column
# (Note, that a nxn chess board has 2n-1 diagonals and 2n-1 anti-diagonals!)
import random
MAX_SOLUTIONS = 10000
def n_queens(n):
    diagonal_available = [True]*(2*n-1)
    anti_diagonal_available = [True]*(2*n-1)
    row_available = [True]*n
    position = [0]*n
    solutions = []
    def fill_column(c):
        if c >= n:
            if len(solutions)<MAX_SOLUTIONS:
                solutions.append(tuple(position))
            return 1
        else:
            number_of_solutions = 0
            for r in range(n):
                if row_available[r] and diagonal_available[r-c+n-1] and anti_diagonal_available[r+c]:
                    row_available[r] = diagonal_available[r-c+n-1] = anti_diagonal_available[r+c] = False
                    position[c] = r
                    number_of_solutions += fill_column(c+1)
                    row_available[r] = diagonal_available[r-c+n-1] = anti_diagonal_available[r+c] = True
            return number_of_solutions
    
    number_of_solutions = fill_column(0)
    return number_of_solutions,solutions
    
import time
n = 13
p = time.perf_counter()
nos,solutions = n_queens(n)
show_board(solutions[-1])
show_positions(solutions[-1])
elapsed_time = time.perf_counter() - p
print("{} solutions found in {:2} seconds.".format(nos,elapsed_time))<jupyter_output>. . Q . . . . . . . . . .
. . . . . . . . Q . . . .
. . . . . . . . . . . Q .
. . . . . . . . . Q . . .
. Q . . . . . . . . . . .
. . . Q . . . . . . . . .
. . . . . Q . . . . . . .
. . . . . . . Q . . . . .
. . . . . . . . . . . . Q
. . . . . . . . . . Q . .
Q . . . . . . . . . . . .
. . . . Q . . . . . . . .
. . . . . . Q . . . . . .
a3, b9, c12, d10, e2, f4, g6, h8, i13, j11, k1, l5, m7
73712 solutions found in 7.863204099999999 seconds.<jupyter_text>Exercise 3 Forbidden lettersWrite a function named ``avoids``that takes a word and a string of forbidden letters, andthat returns ``True`` if the word doesn't use any of the forbiddenletters and ``False`` otherwise.Write some Python code to identify a combination of 6 forbidden letters that aims toexclude the smallest number of words from the file ``words.txt``?<jupyter_code>def avoids(word,letters):
    for char in word:
        if char in letters:
            return False
    return True
   
from collections import Counter

def readWords(fn):
    return [line.strip() for line in open(fn)]

def words_per_letter(all_words):
    word_count=Counter()
    for word in all_words:
        word_count.update(set(word))
    return word_count

def select_letters_greedy(word_file,how_many_letters):
    selected = []
    all_words = readWords(word_file)
    for _ in range(how_many_letters):
        word_count = words_per_letter(all_words)
        letter = min(word_count,key=word_count.get)
        selected.append(letter)
        before = len(all_words)
        all_words = list(filter(lambda word: avoids(word,letter),all_words))
        # Alternative without using avoids:
        # all_words = list(filter(lambda word: letter not in word,all_words))
        after = len(all_words)
        print("Selecting {} eliminated {} words".format(letter,before-after))
    selected = "".join(selected)
    remaining = sum(1 for w in readWords("words.txt") if avoids(w,selected))
    return selected,remaining
        
    
selection,remaining = select_letters_greedy("words.txt",6)
print("Final selection:",selection)
print("Remaining words:",remaining)
from itertools import combinations
def select_letters_combinatorial(word_file,how_many_letters,search_limit=None):
    if search_limit is None:
        search_limit = how_many_letters
    selected = []
    all_words = readWords(word_file)
    word_count = words_per_letter(all_words)
    rare_letters = sorted(word_count,key=word_count.get)[:search_limit]
    best_letters = None
    best_remaining = 0
    for letters in combinations(rare_letters,how_many_letters):
        remaining = len(list(filter(lambda w: avoids(w,letters),all_words)))
        if remaining > best_remaining:
            best_remaining = remaining
            best_letters = letters
    return "".join(best_letters),best_remaining
letters,remain= select_letters_combinatorial("words.txt",6,9)
print("Avoiding letters '{}' {} words remain in the dictionary".format(letters,remain))<jupyter_output>Avoiding letters 'qjxzwk' 88759 words remain in the dictionary<jupyter_text>Exercise 4 A nice word puzzle and an even better programming exercise}    What is the longest English word, that remains a valid English word,	as you remove its letters one at a time?		Now, letters can be removed from either end, or the middle, but you	can't rearrange any of the letters. Every time you drop a letter, you	wind up with another English word. If you do that, you're eventually	going to wind up with one letter and that too is going to be an	English word---one that's found in the dictionary. We want to know	what's the longest word and how many letters does it	have?		Here is a  little modest example: Sprite. You start	off with sprite, you take a letter off, one from the interior of the	word, take the r away, and we're left with the word spite, then we	take the e off the end, we're left with spit, we take the s off, we're	left with pit, it, and I.     Write a program to find all words that can be reduced in this way,and then find the longest one. Use the file `words.txt` as a dictionary of valid words for this exercise.This exercise is a little more challenging. When trying this exercise please note that the provided list of words `words.txt` does not contain the one letter words "a"  and "i", you might want to add them to your list of words. (Depending on your approach you might also want to add the empty word  "".)<jupyter_code># Recursive solution using memoization

def readWords(fn):
    return [line.strip() for line in open(fn)]

words = set(readWords('words.txt'))
words.update(["","a","i"])

def children_list(word):
    result = []
    for i in range(len(word)):
        result.append(word[:i]+word[i+1:])
    return result

def children_yield(word):
    for i in range(len(word)):
        yield word[:i]+word[i+1:]
        
children = children_yield

def reducible_simple(word):
    if word not in words:
        return False
    if word=="":
        return True
    for child in children(word):
        if reducible_simple(child):
            return True
    return False

# Remember if a word is reducible or not
reducibleMemo={"":True}

def reducible_memo(word):
    if word not in words:
        return False
    if word not in reducibleMemo:
        rd = False
        for child in children(word):
            if reducible(child):
                rd = True
                break
        reducibleMemo[word] = rd
    return reducibleMemo[word]

reducible = reducible_memo

def all_reducible():
    t = []
    for word in words:
        if reducible(word):
            t.append(word)
    t.sort(key = len,reverse=True)
    return t

def show_reduction(word):
    if reducible(word):
        print(word)
        for child in children(word):
            if show_reduction(child):
                break
        return True
    else:
        return False

result = all_reducible()
for x in result[:5]:
    show_reduction(x)

# Non-recursive solution
# Starting from shorter to longer words

def readWords(fn):
    return [line.strip() for line in open(fn)]

def children_yield(word):
    for i in range(len(word)):
        yield word[:i]+word[i+1:]

def show_reduction(word):
    if word:
        print(word)
        show_reduction(reduce_dict[word])

word_list = list(readWords("words.txt"))
word_list.extend(["a","i"])
# or words.extend("ai")
word_list.sort(key=len)

reduce_dict = {"":""}

for word in word_list:
    for child in children_yield(word):
        if child in reduce_dict:
            reduce_dict[word] = child
            break
            
longest = max(reduce_dict.keys(),key=len)

show_reduction(longest)<jupyter_output>complecting
completing
competing
compting
comping
coping
oping
ping
pig
pi
i
{'fraction_non_alphanumeric': 0.1228936170212766, 'fraction_numerical': 0.037843971631205675, 'mean_word_length': 3.07631822386679, 'pattern_counts': {'":': 4, '<': 14, '<?xml version=': 0, '>': 28, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '430151', 'license': 'MIT', 'n_tokens_mistral': 6189, 'n_tokens_neox': 5797, 'n_words': 1755, 'path': 'sample solutions/Handout 2.ipynb', 'repo_name': 'RSRamKumar/Programming_Lab_1', 'size': '17625'}