I have a tricky problem I'm not sure how to solve: Given a DAG, topologically sort it in such a way that when the graph is embedded by mapping the nodes to the number line at their position in the sorted list, the total length of all edges is minimized.
@El'endiaStarman what to do with those degrees? Of more importance here is the sizes of cuts in the embedding I should think. The solution which minimizes the average cut size is probably the one we want.
Well, yes, as I said, we want to minimize their total length. So their weight is that distance. (But when I said cut size a moment ago, I meant the number of edges in the cut)
Well, I've been awake a long time, with little sleep, and I've had only a little formal training in graph theory. I can't really think of the solution to your problem.
Plus, I'm working on the Variations of Life thing, so...
Countries own a series of territories on a 1D world. Each country is uniquely identified by a number. Ownership of the territories can be represented by a list as follows:
1 1 2 2 1 3 3 2 4
We define a country's edgemost territories as the two territories closest to either edge. If the above l...
Create a CleverBot!
Tags: code-golf string natural-language
CleverBot is a conversational AI that fundamentally works by repeating responses from real humans it has heard previously. It starts off pretty dumb, but once the database becomes (a lot) larger it begins sounding more like an actual p...
Though since I'm making this a golfing challenge, I don't want to force these things to be hardcoded. If there was some symmetry I might, but I'm leaning towards allowing all combinations
i've heard of people who just hit keys at random and copy it into the "confirm" box, and every time they wanted to use the site they clicked "forgot password"
i was thinking there might be an approach with a list comp, like lambda l:[sorted(l,key=l[::-b].index)[::-b]for b in-1,1], if you can say the elts are unequal within 8 chars
Mini-challenge: Given an nonnegative integer with only even digits (0 2 4 6 8), halve it without using any division or multiplication operators anywhere in the code. Addition and subtraction are allowed, so are string operations. 242886 -> 121443, 4 -> 2, 0 -> 0
The Koch snowflake (also known as the Koch star and Koch island) is a mathematical curve and one of the earliest fractal curves to have been described. It is based on the Koch curve, which appeared in a 1904 paper titled "On a continuous curve without tangents, constructible from elementary geome...
Generate a Koch Snowflake
A Koch snowflake is a triangle that for each n, another equilateral point is added in the middle of each side: http://en.wikipedia.org/wiki/Koch_snowflake#Properties
We already had a kolmogrov-complexity Koch Snowflake challenge for n=4. The new challenge is to draw ...
In Salesforce CRM, every object has 15-character alphanumeric ID, which is case-sensitive. If anyone's curious, actually it's base-62 number.
However, tools used for data migration and integration may or may not support case sensitivity. To overcome that, IDs can be safely converted to 18-charact...
Surrounding Countries
code-golfkolmogorov-complexity
Ever wonder what countries surround another? I do too, sometimes, and, well, here's the challenge for it.
Here is a list of countries that you must recognize (look in the lefthandmost corner). You need to create a full program that outputs (...
@FlagAsSpam Yes, but the challenge can seem trivial as you can just remove the checksum if the starting case and the target case match. However, we need to convert IDs which have a starting case that differs from the target case.
For example, if we need id00330000000xEft, cs00330000000xEftMGH can be shortened to id00330000000xEft, which is just fine.
But for the same target, cs00330000000xeftMGH won't work in the same way as it corresponds to id00330000000xeft, which is not what we want.
We only have cs00330000000xeftMGH, which must be converted in a special way.
Count the ones!
code-golf [Sandbox-note: Is this really still code-golf?]
my-descriptive-tags [Sandbox note: Need to find descriptive tags]
Void Corp needs you!
Thanks to extreme advancements in a technology called null-space we are able to compress any number of 0-bits into just one memory b...
> The graph (up to n = 100000) appears to have a fractal structure. The dense areas are not random but seem to repeat, approximately doubling in width and height each time. - Daniel Forgues, Jan 21 2014
import time
file = open('A229037.txt','w')
start = time.time();
A229037_list = []
for n in range(100000):
i, j, b = 1, 1, set()
while n-2*i >= 0:
b.add(2*A229037_list[n-i]-A229037_list[n-2*i])
i += 1
while j in b:
b.remove(j)
j += 1
A229037_list.append(j)
print(time.time()-start)
for item in A229037_list:
file.write("%s\n" % item)