K‮ly‬e @khird@qoto.org

Here's a #toyprogrammingchallenge requiring a bit of algebra.

For any four non-collinear points A, B, C, and D in three-dimensional space, there is a unique hyperbolic paraboloid H containing the lines AB, BC, CD, and AD (that is, every point on any of these lines is also on the surface of H). Write a program that accepts Cartesian coordinate triplets representing A, B, C, and D and prints an equation in x, y, and z that is satisfied if and only if <x, y, z> is a point on H.

Your program's output may differ from the examples but should be optimised for human readability. Combine like terms, omit terms equal to zero and avoid unnecessary factors (e.g. prefer "x = y" to "2x + 0 = 4y - 2y" even though both describe the same surface).

Example 1 input:
<0, 1, -1>; <1, 0, 1>; <0, -1, -1>; <-1, 0, 1>
Example 1 output:
z = x² - y²

Example 2 input:
<1, 1, 1>; <1, 0, -1>; <-1, 1, -1>; <-1, 0, 1>
Example 2 output:
2y = xz + 1

Example 3 input:
<0, 1, 1>; <0, 1, -1>; <0, -1, -1>; <0, -1, 1>
Example 3 output:
x = 0

@freemo So I can clear my notifications all at once. But I can't figure out how to dismiss a given notification (for example, the notification that you replied to me) without clearing all the rest. Going by the documentation here[1] it seems like it should be possible.

1: https://docs.joinmastodon.org/api/rest/notifications/#post-api-v1-notifications-dismiss

@freemo

I see in Mastodon's API there is a call to dismiss a specific notification. Is there a way to do this from the web frontend?

@mngrif

I see things like this all over the place, is there something else you meant?

https://ebay.com/i/264429918604

@Absinthe

This was super straightforward. Linear in time and space, plus whatever the sort algorithm needs (by default it's nlogn in Octave but you can implement other ones).

function room_count = min_rooms(class_times)
[~, indices] = sort(class_times'(1:numel(class_times)));
current = 0;
room_count = 0;
for index = indices
if mod(index, 2)
current++;
room_count = max(room_count, current);
else
current--; end; end; end;

Call with two arguments, both mandatory: a string to justify and a linewidth to justify to. Returns a 2D array of chars. Where it can, the words touch both sides simultaneously. Sometimes it's not possible to fit more than one word on a line, in which case it is left justified, padded with spaces.

> justify_text('I walked until midnight in the storm, then I went home and took a sauna for an hour and a half. It was all clear. I listened to my heart and saw if there were any signs of my destiny in the sky, and there were none - there were just snowflakes.', 16)
ans =

I walked until
midnight in the
storm, then I
went home and
took a sauna for
an hour and a
half. It was all
clear. I
listened to my
heart and saw if
there were any
signs of my
destiny in the
sky, and there
were none -
there were just
snowflakes.

@Absinthe

Matlab normally represents strings as 1D arrays of chars. It's not usual to put chars in an 2D array because all the rows would have to be the same length, and that's pretty inflexible. Octave is happy to make such an array just as it would with any other type, though, and here that's exactly what we want.

function array = justify_text(string, width)
words = strtrunc(strsplit(string), width);
array = zeros(0, width);
line_length = 0;
start_index = 1;
for word_index = 1:numel(words)
this_word = words{word_index};
if line_length + numel(this_word) > width
array = [array; render_words(start_index, word_index - 1)];
start_index = word_index;
line_length = numel(this_word) + 1;
else
line_length += numel(this_word) + 1; end; end;
array = [array; render_words(start_index, numel(words))];
function this_line = render_words(start_index, end_index)
chars_raw = cellfun(@numel, words(start_index:end_index));
total_padding = width - sum(chars_raw);
if start_index == end_index
this_line = [words{start_index} repmat(' ', 1, total_padding)];
else
base_padding = floor(total_padding / (end_index - start_index));
extra_padding = rem(total_padding, end_index - start_index);
next_char = 1;
for index = start_index:end_index
this_padding = 0;
if index < end_index
this_padding = base_padding;
if index - start_index < extra_padding
this_padding++; end; end;
this_line(next_char:(next_char + chars_raw(index - start_index + 1) - 1)) = words{index};
next_char += chars_raw(index - start_index + 1);
this_line(next_char:(next_char + this_padding - 1)) = repmat(' ', 1, this_padding);
next_char += this_padding; end; end; end; end;

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