@Absinthe This is amazing! I had a feeling he would basically snob Mastodon, so happy I was wrong! 😃

Have you had a look at today's puzzle? 😁 Part 1 seems easy, I fear for part 2...

#toyprogrammingchallenge

This one is super free! It is not a programming problem so much as a BASH problem.

Using bash parameter expansion only gnu.org/software/bash/manual/h

Given an arbitrarily long path, such as "/head/shoulders/knees/and/toes/eyes/ears/mouth" stored in a variable $TEMP construct a parameter expansion to render only the last two subdirectory and filename like "eyes/ears/mouth" such that you can simply offer the command "echo ${TEMP<stuff goes in here>}"

And yes I do know how much easier it is to do with grep, sed, python, perl, awk <insert your favorite alternate solution here> can do it better and easier. This is a real world problem, and someone on Reddit pointed me in the right direction.

#toyprogrammingchallenge

Okay, this is a big one (description-wise) but basically the idea is to build a Monte Carlo simulation craps simulator to observe strategic differences between "Pass", "Don't Pass", with and without odds.

Here is a description of the necessary craps rules. Ask whatever questions that I haven't made clear.
git.qoto.org/Absinthe/crapssim

@Absinthe I have hardly any experience with Python but I think you ought to write your own parser that reports an error on input that can't represent an actual tree (this is what I did in my solution, anyway). The other issue is making sure you escape any special characters in Node.val so your parser doesn't treat them as control characters.

@Absinthe got a new challenge soon, been a bit busy but ready for the next!

#toyprogrammingchallenge
Another Freebie...

This problem was asked by Facebook.

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.

You can assume that the messages are decodable. For example, '001' is not allowed.

This was a really fun programming challenge originally proposed by @Absinthe I want to paste it here, along with my solution, so everyone who is interested can check it out.

Here is the link to his original post: qoto.org/@Absinthe/10289580109

#toyprogrammingchallenge
Another Freebie...

This problem was asked by Facebook.

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.

You can assume that the messages are decodable. For example, '001' is not allowed.

Here is the link to my solution: qoto.org/@freemo/1028986298217

My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.

git.qoto.org/snippets/4

If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.

But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.

It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.

For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.

Incomplete paths can also be trimmed to further reduce the space. But since incomplete paths each add only a single leaf node to the tree, and might be useful for various use cases I decided to keep it.

#ruby #programming

Octave solution 

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

#toyprogrammingchallenge

This is not a programming question per-se. It, was however, quite interesting and fun to figure out. I am still looking for a new program for this weekend. Unfortunately, no one seemed too interested in last weekend's one, so I may let it float. But I am still looking for one anyway.

An evil warden holds you prisoner, but offers you a chance to escape. There are 3 doors A, B, and C. Two of the doors lead to freedom and the third door leads to lifetime imprisonment, but you do not which door is what type. You are allowed to point to a door and ask a single yes-no question to the warden. If you point to a door that leads to freedom, the warden does answer your question truthfully. But if you point to the door that leads to imprisonment, the warden answers your question randomly, either saying "yes" or "no" by chance. Can you think of a question and figure out a way to escape for sure?

#toyprogrammingchallenge

Okay, maybe you can help me come up with a problem. I can feel it coming on, so here is where I am going:

A trick for pricing things for negotiation is to hide the price encoded. One of the ways of doing this is using a 10 letter isogram such as "upholstery" to convert 0=u, 1=p, 2=h...9=y. So then you could mark a tag or sticker with Tly for $6.49 (with the capitols for dollars and the lower case for cents) Alternatively, you could have an asking price and hide a lowest taking price TlyLuu Meaning that you could ask 6.49 but settle for 4.00. This way someone else could negotiate with the customers, from the person that set the prices.

So writing a program should be unnecessary, the reason for using the isogram is to make it easy to remember and figure it out simply.

So how hard would a program to do this be? Ideas?

#toyprogrammingchallenge

Here's a freebie,

This problem was asked by Airbnb.

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Follow-up: Can you do this in O(N) time and constant space?

@Absinthe #toyprogrammingchallenge I did this with recursion (plus caching). Will create a repo tomorrow, but the lru_cache in Python is pretty awesome. The recursive solution starts to slow down significantly as the input strong gets longer, but caching the intermediate results keeps it super fast.

@Absinthe
I think I understand this discussion, I'm admittedly out of my element though so specific implementation ideas aren't coming to mind (which is exciting for me!). Let me see if I have some basic problem constraints:

a n-letter word W is used for encoding pricesbase(s) are open field, ideally base 10 with a 10-letter word
an anagram of W can be used for decoding to deterministically apply a specific markup or discount

Am I following?

@freemo

c++ solution 

@Absinthe C++ is clearly not the appropriate tool, but I need to refamiliarize myself with it, so thanks for the excercise. Solution: gitlab.com/tymorl/warmups/blob .

Python solution 

@Absinthe #toyprogrammingchallenge

git.qoto.org/zingbretsen/nonad

This solution modifies the list as we loop over it. It ensures that at each step, we have the maximum possible sum at each step.

The possibility of having negative numbers necessitates checking at each step.

O(N) time, and repurposes the original list for calculations, so adds no space overhead. This could also be done with a separate 2-item register if the original list should not be modified. This would also be constant space.

#toyprogrammingchallenge

Okay, here is another freebie.

This problem was asked by Amazon.

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.

discussion of solution 

@freemo I understand that the solution is the nth fib for any n when the choice is 1 or two at a time. And my guess is that it goes with a similar function for other numbers of stairs. I also know that for n stairs there is a summation of each number of permutations with repetition n , 1, 0 + n-1, 2,8 8 + n-2 , 3, 4 and so forth. But I don't understand why the fib() works?

Show thread

#toyprogrammingchallenge

Here's another freebie:

This problem was asked by Amazon.

Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.

For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".

#toyprogrammingchallenge

Here's a fun freebie! Only because I just recently saw a problem similar :)

This problem was asked by Facebook.

Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.

Show older
Mastodon

Server run by the main developers of the project 🐘 It is not focused on any particular niche interest - everyone is welcome as long as you follow our code of conduct!