K‮ly‬e @khird@qoto.org

@Absinthe

Should be fairly easy to modify for other bracket types, just add them to the lists at the top and bottom (using the same index for an open bracket and its corresponding close bracket).

function valid = is_balanced(string)
open_brackets = '({[';
close_brackets = ')}]';
expecting = false(size(string));
valid = true;
expected_bracket = [];
for index = 1:numel(string)
if ismember(string(index), open_brackets)
expecting(index) = true;
expected_bracket = strchr(open_brackets, string(index));
elseif ismember(string(index), close_brackets)
if expected_bracket == strchr(close_brackets, string(index))
expecting(find(expecting, 1, 'last')) = false;
expected_bracket = strchr(open_brackets, string(find(expecting, 1, 'last')));
else
valid = false; end; end; end;
if any(expecting)
valid = false; end; end;

@Absinthe

Why did you choose to specify the language for this one? For the freebies that's not so much of an issue but this is the sort of problem that is kind of a pain if you're working in a language where you're not familiar with its features.

@Absinthe

Pictured are G and H from the example

@Absinthe

Think of edges in a directed graph as arrows, which you can follow in the direction they point but not in the opposite direction. The edge <1, 2, 40> allows you to go *from* node 1 *to* node 2, while <2, 1, 84> allows you to go *to* node 1 *from* node 2. So if you exclude the edge you suggested, the graph no longer satisfies the third condition (k-hop rule) because it's no longer possible to get from node 4 to node 1 in two hops (shortest path is 4->2->3->1, which is three hops).

Canada just had a parliamentary election yesterday. Seat breakdown is as follows, per the CBC:

Liberal 157
Conservative 121
Bloc Quebecois 32
New Democrat 24
Green 3
Independent 1

There will almost certainly be a minority government, led by the centre-left Liberals and supported by one or more of the further-left Bloc, NDP, and Greens.

The Liberal party achieved this result despite winning zero seats in the less populous western provinces outside of the Vancouver and Winnipeg metropolitan areas, and I'm starting to see people repeat the claim that a US-style electoral college would stop city voters from "ruling over" rural voters. I'm skeptical of this argument when Americans cite it as a Divine wisdom encapsulated in the Constitution, so I got the preliminary data from Elections Canada and simulated an electoral college.

First, I supposed each province and territory had a number of electors equal to the number of seats it currently gets in the House of Commons, and awarded all its electors to the winner of the popular vote within its boundaries (the Liberals came away with NL, PE, NS, NB, QC, ON, YT, and NT, while the Conservatives prevailed in MB, SK, AB, and BC; the New Democrats won only NU). The seat totals end up as follows:

Liberal 233
Conservative 104
New Democrat 1

Essentially, what happens is that the Liberals get a massive boost from narrow wins in very populous provinces, while the Conservatives already own most of the seats in the western provinces, so coming away with *all* of them doesn't come close to balancing things out. The Bloc came a close second in Quebec but end up with nothing to show for it and the NDP's scattered support doesn't pay off.

Canada, however, has a complicated formula for allocating seats to each province, which no longer matches up well with population distribution because some regions have grown faster than others. So I simulated it again with US-style rules where electors are distributed among provinces according to current population, while territories get zero (Canada doesn't have elected senators, so I set each province's minimum at one elector rather than three as in the States). Turns out not to make a big difference:

Liberal 230
Conservative 108

This masks some interesting stuff going on behind the scenes - Atlantic Canada is overrepresented, losing eleven electors across four provinces, while Ontario is underrepresented and picks up ten when this is corrected. Because these are all Liberal victories anyway, the net effect is only a loss of one (the other two correspond to the territories no longer being eligible for electors, which are mainly redistributed to western provinces).

This should be evidence against the idea that importing electoral features from the US will make Canada's political landscape more like that of America. Using either scheme, allocating a whole province at a time really changes things, but not in a way that helps strengthen rural Canada's voice. Every other party loses seats to the Liberals, which pushes them from a minority government to a very lopsided majority.

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