Letter Coverage - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:35:46Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:35, 9 October 2019
Line 56:		Line 56:
	===Code===		===Code===

	Link to code: https://charlesreid1.com~~:3000~~/cs/five-letter-words/src/master/letter_coverage.py		Link to code: https://git.charlesreid1.com/cs/five-letter-words/src/master/letter_coverage.py

	word2bitvector method:		word2bitvector method:

Admin: /* Simple Manual Example */

2017-09-19T21:27:03Z

Simple Manual Example

← Older revision		Revision as of 21:27, 19 September 2017
Line 232:		Line 232:
	</pre>		</pre>

	Now, we wish to write a dynamic program that will find the smallest set of words such that taking the union of each bit vector gives 11111. At each step, we seek the words that will maximize the length of the sequence of 1s in the union of the bit vectors, for the minimum number of words. We take the union of the "~~longest~~ sequence of 1s" bit vector from the prior step, plus the bit vector for the current step.		Now, we wish to write a dynamic program that will find the smallest set of words such that taking the union of each bit vector gives 11111. At each step, we seek the words that will maximize the length of the sequence of 1s in the union of the bit vectors, for the minimum number of words. We take the union of the "largest sequence of 1s" bit vector from the prior step, plus the bit vector for the current step.

	'''W1:'''		'''W1:'''

	Start with word W1: this is the only bit vector, so it sets the starting "~~longest~~ sequence of 1s" bit vector. We wish to maximize "~~longest~~ sequence of 1s" and minimize number of words.		Start with word W1: this is the only bit vector, so it sets the starting "largest sequence of 1s" bit vector. We wish to maximize "largest sequence of 1s" and minimize number of words.
	* W1 solution is therefore <math>11000</math>. The number of 1s is 1. The number of words is 1. (W1 SOLUTION)		* W1 solution is therefore <math>11000</math>. The number of 1s is 1. The number of words is 1. (W1 SOLUTION)

	'''W2:'''		'''W2:'''

	Next is word W2: the "~~longest~~ sequence of 1s" bit vector is the union of the prior step's "~~longest~~ sequence of 1s" bit vector and the current word's bit vector. One option:		Next is word W2: the "largest sequence of 1s" bit vector is the union of the prior step's "largest sequence of 1s" bit vector and the current word's bit vector. One option:
	* union of W1 solution and W2 <math>11000 \bigcup 01100 = 11100</math>. The number of 1s is 3. The number of words is 2. (W2 SOLUTION)		* union of W1 solution and W2 <math>11000 \bigcup 01100 = 11100</math>. The number of 1s is 3. The number of words is 2. (W2 SOLUTION)

	'''W3:'''		'''W3:'''

	Next is word W3: the "~~longest~~ sequence of 1s" bit vector is the union that maximizes the number of 1s and minimizes the number of words. Two options:		Next is word W3: the "largest sequence of 1s" bit vector is the union that maximizes the number of 1s and minimizes the number of words. Two options:
	* union of W1 solution and W3 <math>11000 \bigcup 10000 = 11000</math>. The number of 1s is 2. The number of words is 2.		* union of W1 solution and W3 <math>11000 \bigcup 10000 = 11000</math>. The number of 1s is 2. The number of words is 2.
	* union of W2 solution and W3 <math>11100 \bigcup 10000 = 11100</math>. The number of 1s is 3. The number of words is 3. (W3 SOLUTION)		* union of W2 solution and W3 <math>11100 \bigcup 10000 = 11100</math>. The number of 1s is 3. The number of words is 3. (W3 SOLUTION)
Line 252:		Line 252:
	'''W4:'''		'''W4:'''

	Next is word W4: the "~~longest~~ sequence of 1s" bit vector is the union that maximizes the number of 1s and minimizes the number of words. Three options:		Next is word W4: the "largest sequence of 1s" bit vector is the union that maximizes the number of 1s and minimizes the number of words. Three options:
	* union of W1 solution and W4 <math>11000 \bigcup 00010 = 11010</math>. The number of 1s is 3. The number of words is 2.		* union of W1 solution and W4 <math>11000 \bigcup 00010 = 11010</math>. The number of 1s is 3. The number of words is 2.
	* union of W2 solution and W4 <math>11100 \bigcup 00010 = 11110</math>. The number of 1s is 4. The number of words is 3. (W4 SOLUTION)		* union of W2 solution and W4 <math>11100 \bigcup 00010 = 11110</math>. The number of 1s is 4. The number of words is 3. (W4 SOLUTION)
Line 259:		Line 259:
	'''W5:'''		'''W5:'''

	Next is word W5: the "~~longest~~ sequence of 1s" bit vector is the union maximizing number of 1s and minimizing number of words. Four options:		Next is word W5: the "largest sequence of 1s" bit vector is the union maximizing number of 1s and minimizing number of words. Four options:
	* union of W1 solution and W5 <math>11000 \bigcup 00011 = 11011</math>. The number of 1s is 4. The number of words is 2.		* union of W1 solution and W5 <math>11000 \bigcup 00011 = 11011</math>. The number of 1s is 4. The number of words is 2.
	* union of W2 solution and W5 <math>11100 \bigcup 00011 = 11111</math>. The number of 1s is 5. The number of words is 3. (W5 SOLUTION)		* union of W2 solution and W5 <math>11100 \bigcup 00011 = 11111</math>. The number of 1s is 5. The number of words is 3. (W5 SOLUTION)
Line 267:		Line 267:
	'''W6:'''		'''W6:'''

	Next is word W6: the "~~longest~~ sequence of 1s" bit vector is the union maximizing number of 1s and minimizing number of words. Five options:		Next is word W6: the "largest sequence of 1s" bit vector is the union maximizing number of 1s and minimizing number of words. Five options:
	* union of W1 solution and W6 <math>11000 \bigcup 01000 = 11000</math>. The number of 1s is 2. The number of words is 2.		* union of W1 solution and W6 <math>11000 \bigcup 01000 = 11000</math>. The number of 1s is 2. The number of words is 2.
	* union of W2 solution and W6 <math>11100 \bigcup 01000 = 11100</math>. The number of 1s is 3. The number of words is 3.		* union of W2 solution and W6 <math>11100 \bigcup 01000 = 11100</math>. The number of 1s is 3. The number of words is 3.

Admin: /* Code */

2017-08-17T13:42:33Z

Code

← Older revision		Revision as of 13:42, 17 August 2017
Line 56:		Line 56:
	===Code===		===Code===

	Link to code: https://charlesreid1.com:3000/cs/five-letter-words/src/master/~~word_coverage~~.py		Link to code: https://charlesreid1.com:3000/cs/five-letter-words/src/master/letter_coverage.py

	word2bitvector method:		word2bitvector method:

Admin: /* Code */

2017-08-17T13:30:57Z

Code

← Older revision		Revision as of 13:30, 17 August 2017
Line 55:		Line 55:

	===Code===		===Code===

			Link to code: https://charlesreid1.com:3000/cs/five-letter-words/src/master/word_coverage.py

	word2bitvector method:		word2bitvector method:

Admin: /* Code */

2017-08-17T13:29:47Z

Code

← Older revision		Revision as of 13:29, 17 August 2017
Line 55:		Line 55:

	===Code===		===Code===

			word2bitvector method:

	<pre>		<pre>
	~~"""~~
	~~word_coverage.py~~

	~~Compute the minimum number of words from five-letter-words~~
	~~needed to cover N letters from the alphabet.~~

	~~This can be done in O(N^2) time with a dynamic program.~~
	~~For each word that we choose, we have to look at all other words~~
	~~to see how many letters those two cover, combined.~~

	~~https://charlesreid1.com/wiki/Five_Letter_Words~~
	~~https://charlesreid1.com/wiki/Letter_Coverage~~
	~~"""~~
	~~from get_words import get_words~~
	~~import numpy as np~~
	~~from pprint import pprint~~

	def word2bitvector(word,N):		def word2bitvector(word,N):
	"""		"""
Line 87:		Line 72:
	pass		pass
	return np.array(bit_vector)		return np.array(bit_vector)
			</pre>

			The main method:

			<pre>
	~~if __name__=="__main__":~~

	~~# Searching for words covering first N letters~~
	~~N = 13~~

	~~words = get_words()~~
	~~words = words[:1000]~~



	# Initialization:		# Initialization:
	# ----------------		# ----------------
Line 114:		Line 91:
	# Store prior word for backtracking		# Store prior word for backtracking
	bt = [-1]*len(words)		bt = [-1]*len(words)
			</pre>

			Fencepost initialization step:

			<pre>
	# Fencepost: Initial Step		# Fencepost: Initial Step
	# Word 0		# Word 0
Line 135:		Line 114:
	# Backtracking: first word has no prior word		# Backtracking: first word has no prior word
	bt[0] = 0		bt[0] = 0
			</pre>

			Loop over words i:

			<pre>
	for i in range(1,len(words)):		for i in range(1,len(words)):
	wi = words[i]		wi = words[i]
Line 166:		Line 149:
	# Backtracking		# Backtracking
	bt[i] = i-1		bt[i] = i-1
			</pre>

			Loop over words j < i:

			<pre>
	# Now loop over the rest of the words,		# Now loop over the rest of the words,
	# and look for a better solution.		# and look for a better solution.
Line 199:		Line 186:
	# but what if we find the perfect		# but what if we find the perfect
	# solution right at the end?!?		# solution right at the end?!?
			</pre>

			Construct the actual solution:

			<pre>
	# Okay, now actually get the solution.		# Okay, now actually get the solution.
	# The solution is the maximum of ones_bv and the minimum of ws		# The solution is the maximum of ones_bv and the minimum of ws

Admin: /* Pseudocode */

2017-08-17T13:18:30Z

Pseudocode

Show changes

Admin: /* Solution */

2017-08-17T13:17:50Z

Solution

@@ Line 10: / Line 10: @@
 ==Solution==
 This dynamic programming problem requires us to both maximize and minimize two different quantities. Our top priority is to maximize the number of letters covered; our second priority is to minimize the number of words used. Thus, we are always trying to be greedy and cover more letters; but if we have two solutions that both cover the same number of letters, we break the tie by comparing the number of words used.
@@ Line 27: / Line 29: @@
 * Search the solutions for every word, and pick out the one that maximizes the number of 1s and minimizes the number of words.
 * To get the actual sequence of words, we also need to save the prior word that leads to the maximum number of 1s and minimum number of words, for each word. Then at the end we can backtrack through the words that compose the solution.
 ==Example==

Admin: /* Solution */

2017-08-17T12:33:22Z

Solution

← Older revision		Revision as of 12:33, 17 August 2017
Line 26:		Line 26:
	Once you've gone through all words, you're ready to find the minimum:		Once you've gone through all words, you're ready to find the minimum:
	* Search the solutions for every word, and pick out the one that maximizes the number of 1s and minimizes the number of words.		* Search the solutions for every word, and pick out the one that maximizes the number of 1s and minimizes the number of words.
			* To get the actual sequence of words, we also need to save the prior word that leads to the maximum number of 1s and minimum number of words, for each word. Then at the end we can backtrack through the words that compose the solution.

	==Example==		==Example==

Admin: /* Simple Manual Example */

2017-08-17T10:24:19Z

Simple Manual Example

← Older revision		Revision as of 10:24, 17 August 2017
Line 86:		Line 86:
	* union of W3 solution and W6 <math>11100 \bigcup 01000 = 11100</math>. The number of 1s is 3. The number of words is 4.		* union of W3 solution and W6 <math>11100 \bigcup 01000 = 11100</math>. The number of 1s is 3. The number of words is 4.
	* union of W4 solution and W6 <math>11110 \bigcup 01000 = 11110</math>. The number of 1s is 4. The number of words is 4.		* union of W4 solution and W6 <math>11110 \bigcup 01000 = 11110</math>. The number of 1s is 4. The number of words is 4.
	* union of W5 solution and W6 <math>11111 \bigcup 01000 = 11111</math>. The number of 1s is 5. The number of words is 4.		* union of W5 solution and W6 <math>11111 \bigcup 01000 = 11111</math>. The number of 1s is 5. The number of words is 4. (W6 SOLUTION)

	(NOTE: We don't need to consider every possible combination of W1, W2, W3, W4, W5, and W6; we only need to consider each word once, because each word's current solution can be written in terms of the prior word's solution, so we only need to consider solutions for each word. We've already considered the non-solutions and can therefore ignore them because they don't maximize number of 1s and minimize number of words.)		(NOTE: We don't need to consider every possible combination of W1, W2, W3, W4, W5, and W6; we only need to consider each word once, because each word's current solution can be written in terms of the prior word's solution, so we only need to consider solutions for each word. We've already considered the non-solutions and can therefore ignore them because they don't maximize number of 1s and minimize number of words.)

Admin: /* Solution */

2017-08-17T00:52:18Z

Solution

← Older revision		Revision as of 00:52, 17 August 2017
Line 13:		Line 13:
	This dynamic programming problem requires us to both maximize and minimize two different quantities. Our top priority is to maximize the number of letters covered; our second priority is to minimize the number of words used. Thus, we are always trying to be greedy and cover more letters; but if we have two solutions that both cover the same number of letters, we break the tie by comparing the number of words used.		This dynamic programming problem requires us to both maximize and minimize two different quantities. Our top priority is to maximize the number of letters covered; our second priority is to minimize the number of words used. Thus, we are always trying to be greedy and cover more letters; but if we have two solutions that both cover the same number of letters, we break the tie by comparing the number of words used.

			The procedure is as follows:
			* For each word (word_i), we must examine all prior words (word_j, where j < i)
			* For each pair of words, we need to take the union (OR) of the character coverage for word_i and the solution bit vector for word_j (that is, the best-covered solution so far for word_j)
			* (Note: for word_i we need to store one of these unions as the best-covered solution so far for word_i, but we aren't sure which one yet.)
			* For the given pair of words, word_i and word_j, we are looking at word_j and the possibility of extending that with word_i
			* Compute the number of 1s in the union with, e.g., sum(bit_vector)
			* Compute the number of words in the solution for word_j and add 1 to it (add word_i to the solution)
			* Searching for the prior solution word_j that leads to the maximum number of 1s
			* Break ties by picking the word_j that will minimize number of words
			* Once you find the best word_j, save the union bit vector for word_i and word_j under word_i combined solution bit vector; save the length of 1s in the combined solution bit vector; save the number of words so far in the solution

			Once you've gone through all words, you're ready to find the minimum:
			* Search the solutions for every word, and pick out the one that maximizes the number of 1s and minimizes the number of words.

	==Example==		==Example==