Notices by Kyle (khird@qoto.org)

@codesections @freemo

I prefer "resign" because it can actually be ambiguous in sentences, while "cleave" can be disambiguated by the presence or absence of a direct object. Suppose you see a headline "Star Player Resigns" - it can mean either that he quit (ri-ZINE) or that he signed a contract extension to continue playing (REE-sine).

@freemo

The case where a is an integer but not a natural number can be excluded because primes are a subset of the natural numbers. If a < 1, then p = a³ - 1 < 0 which contradicts p's primality.

@freemo

Assume the opposite: some cube a³ = p + 1 for some natural number a ≠ 2 and prime p.

The difference of cubes formula shows that:
p = a³ - 1 = (a² + a + 1)(a - 1)

Both terms (a² + a + 1) and (a - 1) are integers. Since p is prime, it follows that exactly one of the two must be equal to unity.

The first possibility can be ruled out because a² + a + 1 = 1 has no solution in the natural numbers.

The second is impossible because a - 1 = 1 contradicts the assumption a ≠ 2.

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

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;

@QOTO Keep in mind the inherent sampling bias when you rely on user engagement (responses to this poll) to evaluate attitudes toward engagement as a criterion for benefits.

@freemo Nice. Not that I'll block either - I'm just in favour of techniques like this that give users more control over what content they want to see. Played a big role in me choosing this instance in the first place.