Optymalne 4 Słowo Umieszczenie Wewnątrz Dowolnie Sized Siatka

Question

oświadczenie

Problem:

Biorąc pod uwagę cztery słowa, umieścić je wewnątrz m x n siatki kwadratów tak, że powierzchnia siatki jest tak mały, jak to możliwe.

Słowa muszą przebiegać od lewej do prawej i od góry do dołu wewnątrz siatki. Litery mogą się nakładać, ale dodatkowych słów nie można uformować. Wszystkie słowa muszą być połączone ze sobą w jeden olbrzymi łańcuch.

Przykładowe siatki, które można utworzyć za pomocą 4 słów "jeden, dwa, trzy i cztery". Uwaga: ostatnia siatka jest najbardziej zoptymalizowana.

Próbuję dowiedzieć się Python i myślałem, że to byłaby dobra aplikacja do cięcia na zęby.

Wszelkie pomysły dotyczące struktury danych i algorytmów w celu rozwiązania problemu takiego jak ten? Nie szukam odpowiedzi bezpośredniej, ale niektóre wskazówki takie jak:

Skorzystaj z tej biblioteki, tej klasy lub tej struktury danych. Lub iteruj tak przez dostępną przestrzeń.

Answer 1

Zastanów się, jaka jest maksymalna wielkość siatki, której potrzebujesz? Jeśli słowa są one, two, three, four, to maksymalna wielkość siatki byłoby

12 x 12. Jest to wielkość siatki, gdzie każde słowo jest umieszczony kres koniec, dzielenie się ostatnią literą poprzedniego słowa.

Teraz mamy przestrzeń. Jak dopasowujesz słowa w przestrzeni? Spróbuj pomyśleć o metodzie brutalnej siły. Co to może oznaczać?

Spróbuj powtórzyć wszystkie możliwe kombinacje wzorów. Możesz umieścić każde słowo na 24 sposoby i są 4 słowa, więc masz ~ 500 000 kombinacji, co nie jest wiele dla współczesnych komputerów. Zobacz, które wzorce faktycznie spełniają kryteria (litery pasują do siebie, itp.).

Po zastosowaniu metody brutalnej siły można ją udoskonalić?

Pod względem struktury danych, naprawdę potrzebujesz siatki, która może przechowywać znaki. Można użyć zagnieżdżonej struktury listy, tablicy numpy, pand lub wielu innych rzeczy. Spróbuj najpierw rozwiązać problem, a następnie dopracuj później.