Klye @khird@qoto.org
Mod
Joined Sep 2018
Solution (with caveat)
The following _technically_ satisfies your requirements; in that I only replace the stuff in brackets from your example and doesn't use anything but parameter expansion.
However, there's a serious limitation I haven't figured out how to work around - it relies on knowing the name of the variable $TEMP. As stated the problem permits this, but that means I can't save my answer in a variable and reuse it like echo ${TEMP1<foo>}; echo ${TEMP2<foo>} without modifying <foo> in between.
echo ${TEMP#${TEMP%/**/**/**}}
Plot twist: going by the spelling ("kilometre" instead of "kilometer"), I would guess the commenter is not an American.
@Absinthe Great! I have been getting less interested in these without anybody giving me feedback.
Octave solution
Space linear in k, time linear in k*|s|.
function string_size = uniform_substring(alphabet_size, base_string)
string_size = 0;
string_start = 0;
recent_letters = zeros(alphabet_size, 1);
recent_indices = zeros(alphabet_size, 1);
for index = 1:numel(base_string)
cache = find(recent_letters == base_string(index) & recent_indices ~= 0, 1);
if isempty(cache)
cache = find(recent_indices == 0, 1); end;
if isempty(cache)
[~, cache] = min(recent_indices);
string_size = max(string_size, index - string_start - 1);
string_start = recent_indices(cache); end;
recent_letters(cache) = base_string(index);
recent_indices(cache) = index;
end;
string_size = max(string_size, numel(base_string) - string_start); end;
I believe the penultimate line should begin with fact(4) rather than fact(3).
@Absinthe Your approach makes more sense now. Generating that table for an arbitrary combination of numbers and sum is a hard problem: stackoverflow.com/questions/4632322
There happens to be a nice closed-form solution for "ones" and "twos" when X = {1, 2}, so it's convenient for that specific case but I don't think it will generalise nicely.
Yeah I worked it out to about 204 million. To clarify - all 200 million aren't on the stack simultaneously; imagine a binary tree 40 levels deep with 200 million nodes - you're never more than 40 steps away from the root node but visiting all nodes still takes a long time.
I don't understand your uncertainty about the 1,3,5 problem - doesn't NArr() apply the same concept to an arbitrary array of integers? What's left to do after that?
Try to write your program before reading this - it also covers the arbitrary-set case.
The number of solutions can be found inductively.
One stair can be walked in exactly one way: a single one-step.
Two stairs can be walked in exactly two ways: a single two-step, or two consecutive one-steps.
Knowing the solutions for 1, 2, ..., N-1, we can divide the number of ways to walk N stairs into two classes: a one-step followed by any valid way of walking N-1 stairs, or a two-step followed by any valid way of walking N-2 stairs. These are mutually exclusive (no valid walk is a member of both classes) and exhaustive (any valid walk is a member of one of these classes) so we can simply add the number of members of each class: F(N) = F(N-1) + F(N-2).
As it happens, this is the definition of the Fibonacci numbers.
Octave solution
This implementation uses memoization, resulting in a space complexity linear in K and time complexity linear in K*|X| for some K between 1 and N inclusive.
function count = step_orders(distance, permissible_steps = [1, 2])
memos = sparse(distance, 1);
hits = (memos ~= 0);
count = step_orders_stateful(distance);
function sub_count = step_orders_stateful(sub_distance)
sub_count = 0;
for first_step = permissible_steps
remainder = sub_distance - first_step;
if remainder > 0
if ~hits(remainder)
memos(remainder) = step_orders_stateful(remainder);
hits(remainder) = true; end;
sub_count += memos(remainder);
elseif remainder == 0
sub_count += 1; end; end; end; end;
Octave solution
Linear time, constant space
function total = nonadjacent_sum(weight_vector)
total = 0;
alternate_sum = zeros(2, 1);
for i = 1:numel(weight_vector)
parity = mod(i, 2) + 1;
if alternate_sum(3 - parity) > alternate_sum(parity) + weight_vector(i)
total += alternate_sum(3 - parity);
alternate_sum = zeros(2, 1);
elseif weight_vector(i) > 0
alternate_sum(parity) += weight_vector(i); end; end;
total += max(alternate_sum); end;
@mngrif Fedilab (mastalab at the time) would drain my battery like nobody's business; couldn't go a full day with it running in the background. Is the lite version more responsible about power usage?
@TatsuyaIshida In the comic you posted on Tuesday (https://spinster.xyz/@TatsuyaIshida/posts/102888328595345330) the third row looks like Clio, Tessy, someone else, and Clio again - who is in the third panel?
@billstclair @Absinthe @freemo
This solution gives wrong answers in certain cases. E.g. "10" should return one solution, the letter "j', but instead it gives zero. I'm suspicious of the inequalities on line 95 (strictly greater than zero AND strictly less than twenty-six permits the integers 1-25, which looks like a fencepost error given a 26-character alphabet).
My take on it is, "Man-hours cost more than CPU-hours." Say I figure out a more sophisticated algorithm that can save CPU time, but implementing it and debugging the extra complexity costs an hour of my time. It probably doesn't make sense to go that route unless it will save more than about fifty hours of compute time in the long run.
E.g. if on a typical dataset I can save a second per run by getting fancy, we would recoup my invested time after 180,000 executions of the program. If it's a report that gets run daily, that break-even point is about five hundred years in the future.
Octave solution
Linear in time and space by taking advantage of the Fibonacci numbers.
function count = interpretations(string)
ambig = string(1:end-1) == '1' | (string(1:end-1) == '2' & string(2:end) <= '6');
ambig &= string(1:end-1) ~= '0' & string(2:end) ~= '0' & [string(3:end) '1'] ~= '0';
ambig = [false ambig false];
consec = find(ambig(1:end-1) & !ambig(2:end)) - find(!ambig(1:end-1) & ambig(2:end));
fibo = zeros(max(consec), 1);
fibo(1:2) = [2 3];
for i = 3:max(consec)
fibo(i) = fibo(i - 1) + fibo(i - 2); end;
count = prod(arrayfun(@(x)fibo(x), consec)); end;
That doesn't cause a stack overflow anymore, but it still fails to parse, e.g. if you rename the "left.left" node to "0", "sometext|0", "sometext|0|moretext", etc.
Also this is a *weird* language.
@Absinthe @billstclair @namark
I don't think you need any global variables.
Your input string looks something like Node('foo',None,Node('bar',None,None)) based on the ouput of your version of serialize(), right? So you can parse it recursively. The general algorithm could be something like:
1. Check that the string begins with 'Node('.
2. Find the first comma. Everything between 'Node(' until this point is self.val.
3. If the next four characters after the comma are 'None' self.left is None.
4. If self.left is not None, examine the string starting after the comma.
a. Set the nesting level to zero.
b. For every open-paren increment the nesting level by one.
c. For every close-paren decrement the nesting level by one.
d. When you find a comma AND the nesting level is zero, stop.
5. Recursively call deserialize() on everything between the comma you found in step 2 and the comma you found in step 4d. Save the answer as self.left.
6. If the next four characters after the comma are 'None' self.right is None.
7. If self.right is not None, examine the string starting after the comma.
a. Set the nesting level to zero.
b. For every open-paren increment the nesting level by one.
c. For every close-paren decrement the nesting level by one.
d. When you find a close-paren AND the nesting level is zero, stop.
8. Recursively call deserialize() on everything between the comma you found in step 4d and the close-paren you found in step 7d. Save the answer as self.right.
@freemo Looks like you get the most consistent linewidth with 3 but I find the grey ink from 4 most attractive. Have you used oblique pens or only straight ones?
🇳🇱