How exactly can they contain nulls?
fopen() takes a null-terminated filename, so if there is a null byte in the middle it would just truncate the filename.
421 karma · joined September 6, 2017
fopen() takes a null-terminated filename, so if there is a null byte in the middle it would just truncate the filename.
[1]: https://github.com/gwsw/less/commit/6a070fc53799fb86e0fe3880...
A more portable solution is to use `chmod` right after unzipping the binary. The `COPY` command will then preserve the executable permission.
With Debian, there are snapshot images[3] which seem like a better approach for making apt-get reproducible. You'd simply have to change the "FROM" line in the Dockerfile to something like "FROM debian/snapshot:stable-20220316" (where 20220316 is the date of the image you are trying to reproduce, helpfully given in /etc/apt/sources.list).
With the approach you describe, you would have to carefully manage the base images: tag them, record which one was used to create each application image, and keep them around in order to reproduce older application images.
I'm sure there are situations where the approach you describe is useful (e.g. with other package managers, especially ones that don't have a notion of lockfiles), but it adds complexity and I don't think it's necessarily justified in the case of apt-get (at least on Debian).
[1]: https://docs.docker.com/engine/reference/builder/#exec-form-...
[2]: https://docs.docker.com/develop/develop-images/dockerfile_be...
(A less sneaky version is to explicitly define new predicates: `is_green2(i) := (i == left - 1) || is_green(i)` and `is_red2(i) := (i == right) || is_red(i)`, where `left` and `right` refer to the function's original parameters (inclusive-exclusive). These predicates can be used as the invariants, and are sufficient for showing that at the end of the loop the result is either the first red, or one-past-the-end if everything is green.)
An alternative is to tweak the invariants:
Let `left` and `right` be the function's original parameters (inclusive-exclusive), and let `l` (that's a lowercase L) and `r` be the variables used in the loop (exclusive-exclusive).
The original invariants are `is_green(l)` and `is_red(r)`, which require sneaky definitions when `l = left - 1` and `r = right`.
The tweaked invariants are `is_green(i) for all i where left <= i <= l` and `is_red(i) for all i where r <= i < right`. In other words, everything up to and including `l` is green, and everything from `r` onward is red.
These invariants are vacuously true when `l = left - 1` and `r = right`, so they hold before the loop (without having to define `left - 1` to be green and `right` to be red).
def binary_search(left, right, is_green):
left -= 1
while left + 1 < right:
middle = (left + right) // 2
if is_green(middle):
left = middle
else:
right = middle
return right
# Usage.
binary_search(0, len(array), lambda i: array[i] < 6)
*Equivalent except for the rounding in the division.
def binary_search(array, target):
left, right = 0, len(array)
while left < right:
middle = (left + right) // 2
if array[middle] < target:
left = middle + 1
else:
right = middle
return right
(Explanation: when `left` and `right` differ by 1, `(left + right) // 2` will return `left` and the search will not make any progress.)
- When the target appears multiple times, the search will find the last occurrence rather than the first.
- If you return `right`, then you get the behaviour of C++'s std::upper_bound and Python's bisect.bisect_right: The return value is the index of the first element strictly greater than the target, or `len(array)` if all the elements are less than or equal to the target.
- If you return `left`, you get a somewhat unusual beast: The return value is the index of the last element less than or equal to the target. If all the elements are greater than the target, the return value should be -1 (because returning 0 would incorrectly suggest that `array[0] <= target`).
Initialising `right` to `len(array)` removes one of the special cases (which is nice and can be done regardless of the invariant), but if `left` remains initialised to 0 then a special case would still be necessary to distinguish between "the first element is equal to the target" and "all the elements are greater than the target" (this special case can be eliminated by initialising `left` to -1; see my top-level comment).
Inclusive-exclusive intervals are a great in many cases, but a little pragmatism can make life easier.
P.S. I also write `while right - left > 1`.
Implementations that terminate early might seem faster at fist glance, but they can actually be slower: they only save 1 iteration on average*, and they require up to 2 branches in each iteration instead of 1. The cost of doubling the number of branches can outweigh the savings (1 iteration out of log2(n)). A possible exception is if the comparison function is expensive and returns a rich comparison (less/equal/greater), in which case it might make sense to perform the 2 branches.
But a much more significant disadvantage of terminating early is that when the target element appears multiple times, there is no guarantee which occurrence will be found.
*Incomplete proof that the saving is only 1 iteration on average: n/2 cases will not terminate early, n/4 will terminate 1 iteration early, n/8 will terminate 2 iterations early, n/16 will terminate 3 iterations early, etc. So the total saving is n/4*1 + n/8*2 + n/16*3 + ... which is at most n (the proof is the same as for the time complexity of the "heapify" operation).
But the three if-statements for the base cases are horrible and completely unnecessary!
We can't initialise `left` to 0 because that might violate the invariant (it is possible that `is_green(arr[0])` will return False). However, we can initialise `left` to -1 (!) if we define `is_green(arr[-1])` to be True, and make sure to never actually compute `is_green(arr[-1])`. (Note when I say `arr[-1]` I am referring to the fictional element before the first element, not the element specified by Python's negative index rules.)
Similarly, we can initialise `right` to `len(arr)` if we define `is_green(arr[len(arr)])` to be False.
So the first line becomes
left, right = -1, len(array)
This uses an exclusive-exclusive range, which can be a little unsettling for people used to inclusive-exclusive ranges. But I think the elegance of the invariants totally justifies it.
Another reason I prefer exclusive-exclusive over inclusive-exclusive for this is that it makes the rounding in `(left + right) // 2` consistent with the "uniqueness" of the middle. An array with 3 items has a unique middle (index 1), while an array with 4 items has two "middles" (index 1 and index 2). With an inclusive-exclusive range, the rounding does not reflect this: when the size is 3, `(0 + 3) / 2` gives 1.5 (which must be truncated to give the correct index); when the size is 4, `(0 + 4) / 2` gives 2.0 (which arbitrarily picks index 2). It bothers me that the case with a unique middle involves rounding (which must be done in the correct direction!) and the case with no unique middle returns a misleadingly exact result. With an exclusive-exclusive range on the other hand, it all works nicely: when the size is 3, `(-1 + 3) / 2` gives 1.0 (which is the unique middle); and when the size is 4, `(-1 + 4) / 2` gives 1.5 (which can be rounded up or down to get the two "middles").
The link posted by @rossy (with "id_") works fine though.
("id_" stands for "identity" and means to return the original resource without rewriting the content, see https://pywb.readthedocs.io/en/latest/manual/rewriter.html#i...)
remaining="" output=""
for ((i = 0; i < ${#actual}; i++)); do
if [[ "${actual:$i:1}" != "${guess:$i:1}" ]]; then
remaining+=${actual:$i:1}
fi
done
for ((i = 0; i < ${#actual}; i++)); do
if [[ "${actual:$i:1}" != "${guess:$i:1}" ]]; then
if [[ "$remaining" == *"${guess:$i:1}"* ]]; then
output+="\033[30;103m ${guess:$i:1} \033[0m"
remaining=${remaining/"${guess:$i:1}"/}
else
output+="\033[30;107m ${guess:$i:1} \033[0m"
fi
else
output+="\033[30;102m ${guess:$i:1} \033[0m"
fi
done
printf "$output\n"
The variable `remaining` tracks the letters of `actual` that can contribute toward yellows.
The best score on https://botfights.io/game/wordle is currently 4.044 (4044/1000).
*Spoiler: The score of the entropy strategy can be improved to 4.086 (53007/12972) by tweaking the entropy formula as follows: Let n be the number of possible solutions and let ki be the size of the i-th partition after the current guess. The usual entropy formula is sum{pi * -log(pi)} where pi = ki / n. The improved formula is sum{pi * -log((ki+1) / n)}. This formula aligns more closely with the expected number of guesses required to solve small partitions.
Another comment mentioned https://botfights.io/game/wordle, if you evaluate your solver on their word list you could compare scores.
I have a counter example for a simplified version the game with the following rule changes:
1. The player is only told which letters in the guess are correct (i.e. they are not told about letters that are present but in a different location).
2. If the player knows there is only one possible solution, the player wins immediately (without having to explicitly guess that word).
3. The set of words that the player is allowed to guess may be disjoint from the set of possible solutions.
Here is the list of possible solutions:
aaaa
aaab
aaba
babb
abaa
bbab
bbba
bbbb
Here is the dictionary of words the player is allowed go guess:
axxx
xaxx
xxax
xxxa
The information gain for each possible initial guess is identical (all guesses result in a 4-4 split), so a strategy based on information gain would have to make an arbitrary choice.
If the initial guess is axxx (the "red herring"), the expected number of guesses is 3.25.
But a better strategy is to guess xaxx (then guess xxax and xxxa). The expected number of guesses is then 3.
(In this example information gain was tied, but I have a larger example where the information gain for the "red herring" is greater than the information gain for the optimal first guess.)
I realise that this blog post is about a strategy for humans to use rather than for an ideal solver, so a degree of inexactness is to be expected. Still, I dislike the way the words "best" and "optimal" are thrown around. The guesses presented in the blog post are "best" in the sense that they maximise some heuristic (namely covering the most frequent letters), but the blog post doesn't explain why that heuristic is good.
Regarding an ideal solver, to prove that a strategy is optimal (in terms of the worst-case number of guesses) one would need to show two things:
- That the worst-case number of guesses of the strategy is N, and
- That there is no strategy whose worst-case number of guesses is less than N.
The first is quite easy to do (for an automated strategy): simply run the strategy against each possible secret "wordle" and keep track of the maximum number of guesses. The second is much harder.
(Since the worst-case number of guesses is likely to be small, this is not a fine-grained way to compare strategies. One could also look at the distribution of the number of guesses to get more information; for example a strategy that takes 6 guesses half the time and 5 guesses the other half is clearly better than a strategy that always takes 6 guesses. Still, it would be really nice if people who published automated strategies also published their worst-case number of guesses.)
Knuth's strategy is optimal (in terms of the worst-case number of guesses) for Mastermind, but it might not be optimal for Wordle. Knuth showed that his strategy takes at most 5 guesses for Mastermind, and presumably there is no strategy that takes at most 4 guesses. But his strategy is not optimal in terms of the distribution of the number of guesses; there are strategies with a lower average number of guesses (and the same worst-case number of guesses; see https://mathworld.wolfram.com/Mastermind.html). Reducing the set of possibilities as much as possible is a very sensible strategy, but it might not be optimal because the number of guesses required to solve a set depends on the nature of its elements, not just on the size of the set. In the case of Mastermind, this inefficiency does not affect the worst-case number of guesses; but in the case of Wordle it might.
One strategy which is obviously optimal is to use minimax (recursively, not like Knuth's Mastermind strategy which was mentioned by @christiangenco), however this strategy is not computationally feasible.
---
Aside: There is something broken with this site's history manipulation. When I open the blog post it creates two entries in the history list, and clicking the browser's back button takes me to a page with the same URL as the blog post that displays "Error Page Not Found".
x = (1,2,3)
#print("the value of x is %s" % x) # breaks if x is a tuple
print("the value of x is %s" % (x,)) # works even if x is a tuple
tuple(["hello"])
def tup(*args):
return tuple(args)
I am reminded of a somewhat similar issue with empty set literals: {1,2} is a set, {1} is a set, but {} is a dict. The way to create empty sets is using set().