Show more

Recursion is almost never the correct solution for any problem in a language that doesn't support tail call optimization.

Octave solution 

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

Octave solution 

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

Octave solution 

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

Basic non regex solution 

@Absinthe@qoto.org I just did, pretty interesting.

Python-ish solution 

I am not happy with the pythonicallity of this, but it solves the problem...

git.qoto.org/Absinthe/justify

Show thread

Okay, here's one. I just finished helping someone worth through this. So it's pretty fun.

Write a program in Python, that can accept a paragraph string and and page
width and return an array of left AND right justified strings. NOTE: No words
should be broken, the beginning and end of the line should be characters).

You should provide instructions on how to execute your program and provide a
sample output.

Example:

Sample input:

Paragraph = "This is a sample text but a complicated problem to be solved, so
we are adding more text to see that it actually works."

Page Width = 20

Output should look like this:

Array [1] = "This is a sample"
Array [2] = "text but a"
Array [3] = "complicated problem"
Array [4] = "to be solved, so we"
Array [5] = "are adding more text"
Array [6] = "to see that it"
Array [7] = "actually works.”

Okay, here's one. I just finished helping someone worth through this. So it's pretty fun.

Write a program in Python, that can accept a paragraph string and and page
width and return an array of left AND right justified strings. NOTE: No words
should be broken, the beginning and end of the line should be characters).

You should provide instructions on how to execute your program and provide a
sample output.

Example:

Sample input:

Paragraph = "This is a sample text but a complicated problem to be solved, so
we are adding more text to see that it actually works."

Page Width = 20

Output should look like this:

Array [1] = "This is a sample"
Array [2] = "text but a"
Array [3] = "complicated problem"
Array [4] = "to be solved, so we"
Array [5] = "are adding more text"
Array [6] = "to see that it"
Array [7] = "actually works.”

Another Python Using Generators 

"""Example using generators for run length encode/decode."""

def rleunits(str1):
"""Generate run length encoded units."""
current = None
count = 0

for letter in str1:
if letter == current:
count += 1
else:
if current:
yield str(count)+current
count = 1
current = letter

def rldunits(str1):
"""Generate run length decoded units."""
count = None

for c in str1:
if c.isdigit():
if not count:
count = c
else:
count += c
else:
yield(c * int(count))
count = None

def main():
"""Drive the example."""
str1 = "AAAABBBBCDDEEFFFFFFFFFFF"

encoded = ''.join(rleunits(str1))
print(encoded)

unencoded = ''.join(rldunits(encoded))
print(unencoded)

main()

Show thread

Basic non regex solution 

@Absinthe@qoto.org
def encode(input):
out = ""

let = input[0]
num = 1

for i in range(1, len(input)):
if input[i] == input[i-1]:
num = num + 1
else:
out = out + str(num) + input[i-1]
let = input[i]
num = 1

out = out + str(num) + input[len(input)-1]

return out

def decode(input):
out = ""

i = 0

while i != (len(input)):
for p in range(0, int(input[i])):
out = out + input[i+1]
i = i + 2

return out

Here is a 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>

SPOILER ONE-LINER SOLUTIONS IN PYTHON 

import re

encooded = "14A3B2C1D2A"
decoded = ""

# first attempt at decoding
list1 = re.findall('\d+\D', encooded)
for l in list1:
count, char = int(l[0:-1]) , l[-1]
decoded += ''.join(count * char)
print(decoded)

# one-liner using regex for decoding!
print(''.join([ int(l[0:-1]) * l[-1] for l in re.findall('\d+\D', encooded) ]))

# one liner using regex for encoding
print( ''.join([ str(len(match[1])+1) + match[0] for match in re.findall(r"(.)(\1*)", decoded)]))

Show thread

Wow, lots of followers today!

If you are interested in any of my coding challenges they should all be tagged with :

If you put that in your search and scroll to to bottom you will see my original proposal. Here is a link with the explanation of where my head is at. The ones I post that I call freebies, are from a subscription to Job Interview problems, and they should be a little tricky, but are usually rated as easy, medium or hard.

qoto.org/@Absinthe/10280565958

Today's Freebie. It's marked as easy.

This problem was asked by Amazon.

Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as a single count and character. For example, the string "AAAABBBCCDAA" would be encoded as "4A3B2C1D2A".

Implement run-length encoding and decoding. You can assume the string to be encoded have no digits and consists solely of alphabetic characters. You can assume the string to be decoded is valid.

while ps -p 5637 >/dev/null; do sleep 5;done; echo "done"| mail -s foo 8125551234@vtext.com # Notification when pid 5637 done

Here's a Freebie, it is marked as "Easy"

This problem was asked by Facebook.

Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).

For example, given the string "([])[]({})", you should return true.

Given the string "([)]" or "((()", you should return false.


Here's a freebie!

This problem was asked by Snapchat.

Given an array of time intervals (start, end) for classroom lectures (possibly overlapping), find the minimum number of rooms required.

For example, given [(30, 75), (0, 50), (60, 150)], you should return 2.

Show more
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.