K‮ly‬e @khird@qoto.org

@realcaseyrollins

I enjoy it but breaking changes to its Bluetooth support have kept me on an outdated version.

@jeffcliff@niu.moe

Heh, we'll stay put and complain about the cost of gas and let you complain about the cost of housing ;)

@jeffcliff@niu.moe

Have you lived in a city your whole life? I tried to imagine my family being carless until I reached 37, and it just doesn't seem feasible. My K-8 was about 15 minutes by car, and my high school nearly half an hour with a good chunk of that on the freeway. No bus after 8th grade either, so transportation is a self-organised carpool among local families. I really don't think "you can too" applies outside of urban centers.

@Absinthe

Can you provide some test cases? I tried to avoid brute-forcing it but I'm not 100% confident of my algorithm's correctness as the solution being optimal.

function cheapest = paint_optimise(cost_matrix, safe = true)
if size(cost_matrix, 2) == 1
[~, cheapest] = min(cost_matrix);
if ~safe
cheapest = [cheapest; zeros(3, 1)];
cost_matrix(cheapest(1)) = Inf;
[~, cheapest(2)] = min(cost_matrix);
cheapest(3) = cheapest(2);
cost_matrix(cheapest(2)) = Inf;
[~, cheapest(4)] = min(cost_matrix); end;
else
pivot = floor(size(cost_matrix, 2) / 2);
left = paint_optimise(cost_matrix(:, 1:pivot), false);
left_cost = price(left, cost_matrix(:, 1:pivot));
right = paint_optimise(cost_matrix(:, (pivot + 1):end), false);
right_cost = price(right, cost_matrix(:, (pivot + 1):end));
combination = zeros(4);
for left_index = 1:4
for right_index = 1:4
if(left(left_index, end) == right(right_index, 1))
combinations(left_index, right_index) = Inf;
else
combinations(left_index, right_index) = left_cost(left_index) + right_cost(right_index); end; end; end;
[left_index, right_index] = min2d(combinations);
cheapest = [left(left_index, :) right(right_index, :)];
if ~safe
cheapest = [cheapest; zeros(3, size(cost_matrix, 2))];
left_mask = double(left(:, end) == left(left_index, end));
right_mask = double(right(:, 1) == right(right_index, 1));
[right_mask, left_mask] = meshgrid(right_mask, left_mask);
left_mask(logical(left_mask)) = Inf;
right_mask(logical(right_mask)) = Inf;
[left_index, right_index] = min2d(combinations + left_mask);
cheapest(2, :) = [left(left_index, :) right(right_index, :)];
[left_index, right_index] = min2d(combinations + right_mask);
cheapest(3, :) = [left(left_index, :) right(right_index, :)];
[left_index, right_index] = min2d(combinations + left_mask + right_mask);
cheapest(4, :) = [left(left_index, :) right(right_index, :)]; end; end;
function total_cost = price(selections, costs)
total_cost = zeros(size(selections, 1), 1);
for index = 1:size(selections, 1)
for house = 1:size(selections, 2)
total_cost(index) += costs(selections(index, house), house); end; end; end;
function [row_index column_index] = min2d(matrix)
[row_index column_index] = find(matrix == min(min(matrix)), 1); end; end;

@Absinthe

Interesting, that interleaving of the if/else and the while loop is very strange to my eye but it's cool that Python allows it.

The nondestructive one looks solid now; the destructive one still claims to find an intersection in disjoint lists though.

Here is a #toyprogrammingchallenge which corresponds to the general case of a problem I ran up against recently.

Given a positive integer K and a directed graph G with weighted edges, return a new graph H satisfying all the following conditions, if such a graph exists:

1. G and H contain exactly the same set of vertices.
2. H contains only edges in G, but G may contain edges not in H.
3. A path exists in H of length at most K between each pair of vertices in each direction.
4. No edge can be removed from H while still satisfying condition 3.

Where more than one graph exists satsifying these conditions, return the one with the least total weight. You may assume G does not contain edges with negative weights.

Here is an example G, each triplet representing the <start, end, weight> of an edge:
<1, 2, 40>
<1, 3, 12>
<1, 4, 50>
<2, 1, 84>
<2, 3, 19>
<2, 4, 69>
<3, 1, 25>
<3, 2, 78>
<3, 4, 93>
<4, 1, 75>
<4, 2, 36>
<4, 3, 96>

Your program should produce the following H given the above G and K = 2:
<1, 2, 40>
<1, 4, 50>
<2, 1, 84>
<2, 3, 19>
<3, 1, 25>
<4, 2, 36>

@Absinthe

The code isn't that bad, you just have to be careful you don't go down a dead end with your algorithm. It's much easier to add error checking etc. at the end if you designed a versatile solution than it is to try and generalise one of the more brittle ones.

Would you mind if I suggested a challenge? I have one involving graph manipulation, which is kind of up @freemo's alley.

@Absinthe

The 2-pointer solution is mostly good. Three things I see:
1. There's a typo ("heead") on line 76 which causes errors on lists of unequal length.
2. It enters an infinite loop when the intersection is None, i.e. the lists don't actually intersect. This is okay going by the problem statement, but in an interview I'd follow up the question by asking you to extend it to handle this case.
3. You probably want to compare the nodes directly on line 70 rather than their vals - you are only guaranteed that the example is free of nodes with duplicate vals, not that all possible inputs are.

As you note, the other two solutions are destructive, so they can't be implemented where the inputs are const.

The tilde solution has additional problems:
1. You store an extra char per node, so it fails the requirement of constant space.
2. It doesn't generalise well: you can't implement this for val types that don't have a string representation, or for string vals where the input might begin with a literal tilde (Unix filepaths, for instance).

Apart from trashing the input data, the last algorithm can't safely be implemented in a non-garbage-collected language. You can't free each node while traversing the m-list because the intersection node still has to be there when you traverse the n-list, but you leak any nodes you don't free.

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

@Absinthe

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; }

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

@Absinthe

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;

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

@Absinthe

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.

@Absinthe

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%%+([^/])/+([^/])/+([^/])}}

@Absinthe

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%/**/**/**}}

@freemo

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.

@Absinthe

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;

@Absinthe

I believe the penultimate line should begin with fact(4) rather than fact(3).