Klye @khird@qoto.org
Mod
Joined Sep 2018
@Absinthe Are you sure you interpreted the problem correctly? It seems your solution only works with non-intersecting lists that just happen to have the same numbers at the end.
For instance your solution breaks if I change the beginning of main() to the following:
common = Node(8,Node(10));
mlist = LList(Node(3,Node(7,common)))
nlist = LList(Node(99,Node(1,common)))
C solution
I got it with one integer and two pointers.
#include <stdlib.h>
typedef struct node {
struct node * next;
int val; } node;
node * list_intersection(node * head_a, node * head_b) {
int diff = 0;
node * this_a = head_a, * this_b = head_b;
while(this_a != NULL) {
this_a = this_a->next;
diff++; }
while(this_b != NULL) {
this_b = this_b->next;
diff--; }
this_a = head_a;
this_b = head_b;
while(this_a != this_b) {
if(diff >= 0) {
this_a = this_a->next;
diff--; }
if(diff < 0) {
this_b = this_b->next;
diff++; }}
return this_a; }
Solution (with caveat)
@Absinthe Perhaps you have a bug in your version of Bash? That statetment involves two parameter manipulations - the inner removing a suffix and the outer removing a prefix. Neither of them should perform a character-replacement to print ' ' instead of '/'.
It works perfectly in Bash 4.3.11.
Octave solution
Worst-case space is linear in the number of control characters (newlines plus tabs). I'm not entirely sure on time requirements of the regex but the rest of it is linear in total characters.
function path_length = max_path_length(stringfs)
indent = char(9);
newline = char(10);
if stringfs(1) ~= indent
indent_level = 0;
else
indent_level = find(stringfs ~= indent, 1) - 1; end
path_length = 0;
children_delims = regexp(stringfs, ['\n' repmat('\t', 1, indent_level) '[^\t]']);
for bounds = [1 children_delims + 1; children_delims - 1 numel(stringfs)]
if any(stringfs(bounds(1):bounds(2)) == newline)
cutoff = find(stringfs(bounds(1):bounds(2)) == newline, 1);
this_path_length = cutoff - indent_level + max_path_length(stringfs((bounds(1) + cutoff):bounds(2)));
elseif any(stringfs(bounds(1):bounds(2)) == '.')
this_path_length = bounds(2) - bounds(1) - indent_level + 1;
else
this_path_length = -Inf; end;
path_length = max(path_length, this_path_length); end; end;
Solution (with caveat)
@Absinthe Given your example where $TEMP="/head/shoulders/knees/and/toes/eyes/ears/mouth", it returns exactly "eyes/ears/mouth". Do you have a test case where it doesn't work?
Solution (with caveat)
In that context, you know the name of the variable. A solution where you don't need to know the name of the variable would be more useful in other circumstances, however.
For example, let's say I am allowed to execute but not modify a script which reads the pattern from a file or environment variable or something. If the permissions of that file or variable are insufficiently restrictive, I can manipulate the effect of the script by overwriting that pattern with my own. But if the script is going to make multiple calls like do_something_with ${TEMP1<foo>}; do_something_with ${TEMP2<foo>}; then I would need a version of <foo> that is independent of the name of the variable.
Solution (with caveat)
For some reason I had the idea the spec wanted the leading slash. This gets it without, but has the same caveat as the above.
echo ${TEMP#${TEMP%%+([^/])/+([^/])/+([^/])}}
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?
🇳🇱