Rozwiązywanie pogmatwanych zagadek z pytonem?

Question

mam ciekawą zagadkę programowania dla Ciebie:

Będziesz mieć dwie rzeczy:

1. Słowo zawierający listę angielskich słów razem wzięte, np:

   word = "iamtiredareyou" 
   

2. Możliwe podzbiory:

   subsets = [ 
       'i', 'a', 'am', 'amt', 'm', 't', 'ti', 'tire', 'tired', 'i', 
       'ire', 'r', 're', 'red', 'redare', 'e', 'd', 'da', 'dar', 'dare', 
       'a', 'ar', 'are', 'r', 're', 'e', 'ey', 'y', 'yo', 'you', 'o', 'u' 
   ] 
   

wyzwania:

Level-1: muszę pragmatycznie znaleźć członków w subsets które razem w kolejności uczynią "iamtiredareyou" tj ['i', 'am', 'tired', 'are', 'you']

Level-2: Oryginalny ciąg może składać się z kilka dodatkowych znaków w sekwencji, które nie są obecne w podzbiorze. na przykład "iamtired12aareyou". Podany subset jest taki sam jak powyżej, rozwiązanie powinno automatycznie włączyć ten podzbiór we właściwe miejsce w tablicy wyników. tj. ['i', 'am', 'tired', '12a', 'are', 'you']

Jak mogę to zrobić?

Answer 1

Ogólnie rzecz biorąc, zrobiłby to algorytm rekursywny. Zacznij od sprawdzenia wszystkich podzbiorów przed rozpoczęciem danego słowa, jeśli zostanie znaleziony - dodaj (dołącz) do znalezionych wartości i powtórz z pozostałą częścią słowa i bieżącymi znalezionymi wartościami. Lub jeśli jest to koniec ciągu znaków - wydrukuj znalezione wartości.

coś takiego:

all=[] 
def frec(word, values=[]): 
    gobal all 
    if word == "": # got result. 
     all+=[values] 
    for s in subsets: 
     if word.startswith(s): 
      frec(word[len(s):], values+[s]) 

frec(word) 

pamiętać, że istnieje wiele możliwych rozwiązań, ponieważ podzbiory zawierają wiele ciągów jeden znaków. Możesz znaleźć najkrótszy wynik. (13146 rozwiązań ... użyj "all.sort (cmp = lambda x, y: cmp (len (x), len (y)))", aby uzyskać najkrótszy)

Dla poziomu 2 - potrzebujesz kolejnej pętli, jeśli nie ma dopasowań podzbiorów, które dodają coraz więcej symboli do następnej wartości (i powtarza się do tego), dopóki nie zostanie znaleziony odpowiednik.

all=[] 
def frec(word, values=[]): 
    global all 
    if word == "": # got result. 
     all+=[values] 
     return true 
    match = False 
    for s in subsets: 
     if word.startswith(s): 
      match = True 
      frec(word[len(s):], values+[s])  
    if not match:       
     return frec(word[1:], values+[word[0]]) 
frec(word) 

Nie próbuje jednak łączyć wartości innych niż podzestawy w jeden ciąg.

Answer 2

myślę, że należy zrobić własne excercises programowania ....

Answer 3

dla poziomu 1 wyzwanie można to zrobić recursively. Prawdopodobnie nie jest to najbardziej wydajne rozwiązanie, ale najłatwiejsze:

word = "iamtiredareyou" 
subsets = ['i', 'a', 'am', 'amt', 'm', 't', 'ti', 'tire', 'tired', 'i', 'ire', 'r', 're', 'red', 'redare', 'e', 'd', 'da', 'dar', 'dare', 'a', 'ar', 'are', 'r', 're', 'e', 'ey', 'y', 'yo', 'you', 'o', 'u'] 

def findsubset(): 
    global word 

    for subset in subsets: 
     if word.startswith(subset): 
      setlist.append(subset) 
      word = word[len(subset):] 

      if word == "": 
       print setlist 
      else: 
       findsubset() 

      word = subset + word 
      setlist.pop() 

# Remove duplicate entries by making a set 
subsets = set(subsets) 
setlist = [] 
findsubset() 

Twoja lista podzbiorów ma w niej duplikaty - np. 'a' pojawia się dwukrotnie - więc mój kod sprawia, że ​​set usuwa duplikaty przed wyszukiwaniem wyników.

Answer 4

Czy to nie to samo, co znalezienie permutacji, ale z pewnymi warunkami?Podobnie jak przy uruchamianiu algorytmu permutacji (rekursywnego), sprawdzasz, czy ciąg znaków, który już masz, pasuje do pierwszych X znaków twojego słowa, jeśli tak, kontynuuj rekursję, aż znajdziesz całe słowo, w przeciwnym razie wróć.

Poziom 2 jest nieco głupi, jeśli pytasz mnie, ponieważ wtedy mógłbyś napisać cokolwiek jako "słowo, które można znaleźć", ale w zasadzie byłby to jak poziom1 z wyjątkiem tego, że jeśli nie możesz znaleźć podłańcuch na twojej liście po prostu go dodasz (litera po literze, czyli masz "miłość" i listę ["l", "e"] pasujesz do "l", ale brakuje ci "o", więc dodajesz je i sprawdzasz Twoje słowa na liście zaczynają się od "v" i pasują do twojego słowa, ale nie dodają "v" do "o" itp.).

A jeśli jesteś znudzony, możesz zaimplementować algorytm genetyczny, jest naprawdę zabawny, ale niezbyt skuteczny.

Answer 5

Oto rekurencyjny, nieefektywne rozwiązanie Java:

private static void findSolutions(Set<String> fragments, String target, HashSet<String> solution, Collection<Set<String>> solutions) { 
    if (target.isEmpty()) { 
     solutions.add(solution); 
     return; 
    } 

    for (String frag : fragments) { 
     if (target.startsWith(frag)) { 
      HashSet<String> solution2 = new HashSet<String>(solution); 
      solution2.add(frag); 
      findSolutions(fragments, target.substring(frag.length()), solution2, solutions); 
     } 
    }  
} 

public static Collection<Set<String>> findSolutions(Set<String> fragments, String target) { 
    HashSet<String> solution = new HashSet<String>(); 
    Collection<Set<String>> solutions = new ArrayList<Set<String>>(); 
    findSolutions(fragments, target, solution, solutions); 
    return solutions; 
} 

Answer 6

Niestety o braku programowania urywek, ale chciałbym zaproponować programowanie dynamiczne. Atak na poziomie 1 i poziomie 2 w tym samym czasie, nadając każdemu słowu koszt i dodając wszystkie pojedyncze znaki nie występujące jako słowa o wysokim koszcie pojedynczego znaku. Problem polega na znalezieniu sposobu podziału sekwencji na słowa, które dają najmniejszy całkowity koszt.

Pracuj od lewej do prawej wzdłuż sekwencji, w każdym punkcie pracy i zachowując najmniej kosztowne rozwiązanie do bieżącego punktu włącznie, oraz długość słowa, które kończy to rozwiązanie. Aby wypracować odpowiedź na następny punkt w sekwencji, należy rozważyć wszystkie znane słowa będące przyrostkami sekwencji. Dla każdego takiego słowa opracuj najlepszy całkowity koszt, dodając koszt tego słowa do (już wypracowanego) kosztu najlepszego rozwiązania kończącego się tuż przed rozpoczęciem tego słowa. Zwróć uwagę na najmniejszy całkowity koszt i długość słowa, które je produkuje.

Gdy już uzyskasz najlepszy koszt dla całej sekwencji, użyj długości ostatniego słowa w tej sekwencji, aby ustalić, jakie jest ostatnie słowo, a następnie cofnij tę liczbę znaków, aby sprawdzić odpowiedź wypracowaną w tym momencie. wskaż i uzyskaj słowo tuż przed ostatnim słowem, i tak dalej.