Notices by La Fée Verte (absinthe@qoto.org), page 2

#toyprogrammingchallenge

Second Freebie!!! This one is marked as "easy"

This problem was asked by Google.

Given two singly linked lists that intersect at some point, find the intersecting node. The lists are non-cyclical.

For example, given A = 3 -> 7 -> 8 -> 10 and B = 99 -> 1 -> 8 -> 10, return the node with value 8.

In this example, assume nodes with the same value are the exact same node objects.

Do this in O(M + N) time (where M and N are the lengths of the lists) and constant space.

#toyprogrammingchallenge

Freebie!! Here you go!
This problem was asked by Facebook.

A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighboring houses are of the same color.

Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color, return the minimum cost which achieves this goal.

#toyprogrammingchallenge

Here's a freebie. They labeled it as "Hard"

This problem was asked by Google.

Suppose we represent our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
subdir1
subdir2
file.ext
The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Note:

The name of a file contains at least a period and an extension.

The name of a directory or sub-directory will not contain a period.

@khird @freemo

Okay, so with all that, here is the actual longhand using the permutations, but I am not sure how to handle this if I passed an array of numbers like in the 1,3,5 example

def NFact(x):
def fact(x):
_fact = 1
for i in range(1, x+1):
_fact = _fact * i
return _fact

def r_NFact(num):
twos = x - num
ones = x - (2 * twos)
if ones < 0:
return 0
return r_NFact(num - 1) + ( fact(num) // (fact(ones) * fact(twos)))
return r_NFact(x)

@khird @freemo

How's this look?
def N(x):
if (x < 0):
return 0
if (x == 0 or x == 1):
return 1
return N(x-1) + N(x-2)

def N135(x):
if (x < 0):
return 0
if (x == 0):
return 1
return (N135(x-1) + N135(x-3) + N135(x-5))

def NArr(x, arr):
if (x < 0):
return 0
if (x == 0):
return 1
return sum([NArr(x - i, arr) for i in arr])

def main():
for n in range(10):
print(n, N(n))

for n in range(10):
print(n, N135(n))

for n in range(10):
print(n, NArr(n, [1,3,5]))

if __name__ == "__main__":
main()

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

#toyprogrammingchallenge #python #lisp #c #c++ #cpp #coding #programming

Ready for the next challenge?

"5 Guys and a Bunch of Coconuts"

Here is a link to the text description of the problem.

https://git.qoto.org/Absinthe/coconuts/blob/master/coconuts.txt

That link is to the repo, and my solution is in it as well.

care to play with some programming languages:

Here is a web page that lets you have a compillation environment for a whole bunch of them without having to install anything. Pick your language from the drop down.

https://rextester.com/

#toyprogrammingchallenge

I want to propose a programming challenge. This could be fun for beginners and experienced programmers as well. It is language agnostic. It might even be more about community than the programming part itself. The challenge itself should not take more than an hour. But it shouldn't be so simple that you don't have to put in a little effort. I will propose the first one, and those who participate are welcome to propose the next and as we can agree on it we can go off and knock it out.

Once you see other people's results you can modify your own, or even propose something to make someone else's better or faster or fix a bug that you find.

These can become toy programs for you to have around for testing concepts, and helping to try out other languages.

If you are interested or know someone else who might want to play too share this with them.

I guess we can use this thread to get started, and I guess i am supposed to use a hashtag for something like this so how about #toyprogrammingchallenge

I will try to work in Python at least in the beginning but you are welcome to work in whatever you are comfortable with.

#toyprogrammingchallenge
First challenge:

"Ninety-nine bottles of beer on the wall"

Generate the whole song from "Ninety-nine" to "No". The output should look like :

Ninety-nine bottles of beer on the wall.
Ninety-nine bottles of beer. Take one down,
pass it around... Ninety-eight bottles of beer.

(You know what the middle looks like)

Two bottles of beer on the wall.
Two bottles of beer. Take one down,
pass it around... one bottle of beer.

One bottle of beer on the wall.
One bottle of beer. Take one down,
pass it around... No bottles of beer.

I won't put too many specifics on how you get there, but the output should be words, not numerals :) Try to write clean, maintainable and visually understandable code.

Let see if I am alone or anyone wants to play along. :)

Here is my first attempt total time 48 minutes.

https://git.qoto.org/Absinthe/ninety_nine_bottles

@freemo Dead colony.

When a queen is raised and she hatches she will go around and tear apart any other queen cells and kill any other virgin queens she can find. Then she goes away and has her mating flight where she will have sex with as many drones (from other colonies) as possible. Likely about 20 of them. They mate in flight. The drones break off their penis inside the queen and she stores all their sperm in her spermatheca. When she returns to the hive her pheromone will start the proper behaviors. However, if after that point the workers detect any problems with the queen they will begin making queen cells (they can make a queen cell with any fertilized egg under 3 days old.) In preparation for her demise. However, if she fails and they haven't created queen cells, or whatever, this is when you can get a laying worker. If they have a laying worker they will no longer try to make a queen cell, and the laying worker's eggs are not of any use to make females anyway, and she lays a whole bunch of them in a cell not just one.

Once they have no viable egg to make into a queen, the colony will die (unless the keeper introduces a new queen)

English is such an odd lanugage sometimes. Because I am a beekeeper my daughter bought me a wood (Or linoleum) cut print of a bee and the quote "The keeping of bees is like the direction of sunbeams." - HDT

I had to read it over and over again, out loud to finally get the meaning. I guess I just don't use "direction" to mean "act of directing" ...

Hello Qoto! Is this the instance I am looking for? Can I discuss controversial topics on either side of the argument? Is anything off topic? Can I criticize things or are there some golden calves I need to avoid?