469
\$\begingroup\$

What is the Sandbox?

This "Sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to the main page. This is useful because writing a clear and fully specified challenge on the first try can be difficult. There is a much better chance of your challenge being well received if you post it in the Sandbox first.

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

See the Sandbox FAQ for more information on how to use the Sandbox.

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

||||||
\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – James Aug 29 '19 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – S.S. Anne Sep 26 '19 at 15:57
  • 3
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 '19 at 13:43

2744 Answers 2744

-2
\$\begingroup\$

The heights of Natural Numbers

Every number can be expressed as the product of itself and/or smaller numbers. This is a fundamental feature of our world.

For example 10 can be expressed as the product of 5 and 2, or as the product of 1 and 10.

9 can be expressed as the product of 3 and 3, or 1 and 9.

12 can be expressed as the product of 2 and 6. 6, in turn, can be expressed as the product of 2 and 3. It could also be the product of 3 and 4, and in turn 4 is the product of 2 and 2. Lastly there is 1 and 12.

7 can only be expressed as the product 1 and itself.

The numbers in the products are called factors. Every number has at least 2 factors, itself and 1. Numbers with only those two factors are called prime. Numbers with more than 2 are called composite.

These factors can be written as trees. The root begins with the number itself, and factors are written below, by adding branches to the root.

7 has 1 and 7. This is a short tree. It has one prime.

9 has 3 and 3. This is also a short tree, but it has two branches. It has two primes, but they are both at depth of 1 down the tree.

10 has 5 and 2. Again, short. Again, primes are at depth 1.

12 has 6 and 2, 6 has 3 and 2. This tree has two levels of height. Note that at the second level, every factor is prime, but at the first level, some factors are composite. 12 has also 3 and 4, and 4 becomes 2 and 2 - the tree looks similar to when using 6 and 2, this is called Isomorphic, which comes from the Greek language words for same shape.

In other words, every number has several trees of factors, and each tree has leaves that are prime factors. And every tree has a height, the number of branches one must travel between the root and the furthest leaf.

For example, every number has a tree of height 1. Itself and 1. So.

7 has height 1, because 1x7=7

9 also is height 1, because 3x3=9, and 1x9=9, are both of height 1.

12 is height 2. 3x2x2 becomes 3x4, which becomes 12. There are two branches between 12 and either leaf of 2.

But 12 is also height 1 because it has a different tree of height 1: 1x12=12.

16 is height 3, because 16 becomes 2*8 becomes 2*2*4, becomes 2*2*2*2. But 16 is also depth 1 because 1x16=16. However 16 is not depth 2, because no tree of it's factors has primes up two branches from the root.

Write a program that given an integer n, returns a sequence of the first 100 numbers that have prime factor trees of height n.

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ The prologue about factors and primes is unnecessary-- we know what they are. A diagram would be nice. You didn't explicitly mention the rules for creating trees-- why can't 16 = 4x4 = (2x2)x(2x2), or 16 = 8x2 = (8x1)x2? Are depth and height the same? \$\endgroup\$ – lirtosiast Jun 29 '19 at 7:12
-2
\$\begingroup\$

Best Mile Time

Introduction

Your friend has been trying to improve his mile time on. Unfortunately, he isn't very good at keeping a steady pace and constantly speeds up and then slows down. He usually runs for many miles at a time and wants to choose the fastest mile of his run to determine his mile time.

Given your friend's distance versus time, determine his fastest mile time for a contiguous mile stretch.

Input

A list of distances (in miles) sampled at an even interval.

Output

The length of the smallest interval during which a distance of at least one mile was traveled.

Rules

  • You may assume that the the total distance traveled is at least 1 mile.
  • The mile time must be for a continuous time interval.
  • Standard loop-holes are forbidden.
  • Standard rules apply.
  • Please provide a link to test your code as well as an explanation.
  • This is , so the program with the smallest asymptotic time complexity wins!
  • Ties will be broken by fastest run time.

Example

Python 3.7, O(n ^ 2)

Try it online!

from typing import List


def fastest_mile_time(distances):
    """Determines the fastest mile time from a list of distances.

    Parameters
    ----------
    distances : List[float]
        The list of distances in miles.

    Returns
    -------
    int
        The length of the smallest interval during which at least one mile was traveled.
    """
    intervals = []
    for i in range(len(distances) - 1):
        for j in range(i + 1, len(distances)):
            if distances[j] - distances[i] >= 1:
                intervals.append((i, j))
                break

    return min(map(lambda x: x[1] - x[0], intervals))
||||||
\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman how's this? \$\endgroup\$ – Billylegota Jul 19 '19 at 2:32
  • 2
    \$\begingroup\$ Unless I'm missing something this is trivially O(n): keep two pointers into the list, advance them keeping them 1 mile apart, and keep track of the running minimum time. I'm downvoting, so ping me if I was mistaken or if this is updated so I can update my vote. \$\endgroup\$ – lirtosiast Jul 19 '19 at 2:52
  • \$\begingroup\$ @lirtosiast O(n) is trivial. I just gave O(n ^ 2) as an example. However it isn't clear to me that O(n) is the lower bound. I think the fact that the sequence is monotonically increasing may be of some use (although I've yet to show that to be the case). \$\endgroup\$ – Billylegota Jul 19 '19 at 3:20
  • 3
    \$\begingroup\$ The optimal solution is O(n). You need to iterate two pointers through the entire list one time to ensure that you have found the minimum valid difference. The range of time this will take ranges from Ω(n) to O(2n) in the optimized case. for(i=j=0;j<length;i++){for(;array[j]-array[i]<1&&j<length;j++){}minTime=min(minTime , j-i)} \$\endgroup\$ – fəˈnɛtɪk Jul 20 '19 at 17:00
  • 2
    \$\begingroup\$ Consider a list where every element at even index 2n is n, and every element at index 2n+1 is either n+.5 or n+1. If there is an integer at an odd index, the fastest mile time is 1, otherwise it's 2. But we have no way of determining this without reading all n/2 odd indices. \$\endgroup\$ – lirtosiast Jul 20 '19 at 18:17
  • \$\begingroup\$ @lirtosiast +1 thanks for such a clear example! \$\endgroup\$ – Billylegota Jul 21 '19 at 6:16
-2
\$\begingroup\$

Produce a self-reproducing data structure

Write the shortest code to produce a self-reproducing list, dictionary, array, and so on and so forth. That is, when you index any one of the logically-available items that belongs to the resulting data structure that you have produced, you get the same data structure when you compare the equality between the data structure before you indexed and the data structure after you indexed.

  • In order to verify your code with automatically-provided constructions in programming languages, you should pick an operator that compares whether two values are equal (or does type-comparisons, if available).
  • If your language does not provide an equality operator, you should simulate an equality operator yourself using operators like - or other operators that do the job of comparing values (as in Acc!, where an explicit comparison operator is not provided.)

Example

This is an example of a validity/equality test of a possible solution in a Python REPL (when you have already produced a list, namely list, where it produces itself at its 0th item). This test simply compares the equality between the non-indexed list and the indexed list:

>>> list
[[...]]
>>> list[0]
[[...]]
>>> list==list[0]
True

However, if the result of the last line (the equality comparison) is not a truthy value in your language (for example False and 0 in Python), then your answer is invalid and should be improved.

Rules

  • Your program does not have to take input; neither does it have to explicitly output the data structure. However, your resulting data structure has to be accessible in some way.
  • This is a contest; the shortest answer will win.
  • No standard loopholes, please.
  • In this challenge, the values on both operands in the equality check should have the same type.
  • Your code (both your testing code and your producing code) should not produce any errors; any outputs to stderr are considered non-truthy values and demonstrates that your code is invalid.
||||||
\$\endgroup\$
  • 4
    \$\begingroup\$ What does "compare it" mean? There are many many types of comparison one can perform, and they don't necessarily give the same result for the same values. \$\endgroup\$ – Peter Taylor Jul 24 '19 at 7:11
  • 5
    \$\begingroup\$ @A__ For JavaScript, is it == or ===? Either way, people will be angry. \$\endgroup\$ – wizzwizz4 Jul 24 '19 at 13:16
  • 2
    \$\begingroup\$ @A__ Because either the challenge is trivial (['']) or you're arbitrarily restricting a language. Work on your definition of "equality operator". \$\endgroup\$ – wizzwizz4 Jul 24 '19 at 13:46
  • 2
    \$\begingroup\$ @A__ So, basically, you want (x=[])[0]=x? No clever tricks? Just a bog-standard recursive data structure? (Though, it might be interesting in languages where those aren't allowed.) \$\endgroup\$ – wizzwizz4 Jul 24 '19 at 14:07
  • \$\begingroup\$ @wizzwizz4 In fact, your program is a clever trick that I have not thought of. Mine is 13 bytes, yours is 11 bytes. Yes, what I want is a bog-standard recursive data structure, as long as it is not a duplicate of another question. (My program is a=[];a.push(a)) \$\endgroup\$ – user85052 Jul 24 '19 at 14:10
  • 3
    \$\begingroup\$ @U10-Forward 0 bytes \$\endgroup\$ – tjjfvi Jul 24 '19 at 14:32
  • 1
    \$\begingroup\$ @tjjfvi I thought about that one, but I didn't think it'd be syntactically valid. It does, however, work. \$\endgroup\$ – wizzwizz4 Jul 24 '19 at 15:19
  • 1
    \$\begingroup\$ @wizzwizz4 How do you know which language? \$\endgroup\$ – tjjfvi Jul 24 '19 at 15:31
  • 1
    \$\begingroup\$ @tjjfvi I just assumed it was a language where the "null" / "undefined" singleton was indexable, returning the very same value. \$\endgroup\$ – wizzwizz4 Jul 24 '19 at 15:34
  • 1
    \$\begingroup\$ @wizzwizz4 No, JS: window.window === window :) \$\endgroup\$ – tjjfvi Jul 24 '19 at 15:38
  • 2
    \$\begingroup\$ @tjjfvi I read the challenge differently to you. I thought it meant "any one of the logically-available items". By this rule, (x={}).x=x is the shortest I can think of, other than the trivial case. \$\endgroup\$ – wizzwizz4 Jul 24 '19 at 15:53
  • 1
    \$\begingroup\$ @tjjfvi Well i do it in Python so no such a thing called 0 bytes in python \$\endgroup\$ – U10-Forward Jul 25 '19 at 1:08
  • \$\begingroup\$ Alternative: window["window"]===window \$\endgroup\$ – user85052 Jul 25 '19 at 4:06
-2
\$\begingroup\$

Recursive Sum Up The Digits

Tags:

Produce the shortest code that sums up all the digits in a number, and after if it still has more than one digit, sum it up again and again until it's with one digit, example: 987 would become 6 since 9 + 8 + 7 is 24, whereas 2 + 4 is 6.

||||||
\$\endgroup\$
  • 2
    \$\begingroup\$ I have the feeling I've seen this challenge before, but I'm unable to find it. It could be that I'm confusing it with two similar loose challenges, since there are more challenges where we continue doing something until a single digit remains, and there are also loads of challenges summing the digits of an integer. I'm not 100% sure anymore whether there is already one with both combined. \$\endgroup\$ – Kevin Cruijssen Aug 5 '19 at 6:37
  • 5
    \$\begingroup\$ This is just "Given n output n % 9". \$\endgroup\$ – Peter Taylor Aug 5 '19 at 7:46
  • \$\begingroup\$ @PeterTaylor Ah, now I remember where I've seen it before: here in the sandbox, and you (or someone else) made that same comment. :) \$\endgroup\$ – Kevin Cruijssen Aug 5 '19 at 12:24
  • \$\begingroup\$ Isnt this just a duplicate of codegolf.stackexchange.com/q/1775/87923? \$\endgroup\$ – EdgyNerd Aug 6 '19 at 8:19
  • 1
    \$\begingroup\$ @EdgyNerd It's related, but not a dupe. That challenge takes multiple integers as input simultaneously, instead of a single input. And it outputs the amount of iterations for each of those integers to become a single digit, instead of the resulting digit itself. In addition, it has rather cumbersome output-format.. So that challenge would result in 987 2 for input [987]. The core part of both challenges is the same though: continue summing the digits of an integer until a single digit remains. \$\endgroup\$ – Kevin Cruijssen Aug 6 '19 at 9:16
-2
\$\begingroup\$

Make it improbable... BUT NOT IMPOSSIBLE

You must make a program that outputs truly once in a while. However, making it have output falsy all the time is not acceptable.

Rules

  • Standard loopholes are forbidden.
  • You may use any of accepted I/O formats.
  • Your program must be possible to output a truly value.
  • When not outputting a truly value, you may either output a falsy value or not output anything at all.
  • You may output two or more values, however if it contains a truly value, then the output is considered truly.
  • The probability of outputting a truly value must be at most 1/2.
  • Your program must not take/use an input.
  • Using non-deterministic but non-random(Such as getting the time) is prohibited. However, if date etc. is used in the builtin random function, it is allowed.
  • The program must theoretically always terminate or stop outputting anything.
  • You may assume that you have a fast enough computer and large enough memory.
  • Your program should not be affected by raising the maximum value of a data type. You may still use unaffected constants.
  • Data types must be following its spec: ie. for an unbounded arbituary precision integer type, you may assume that it can go as high as you want(but you are not allowed to increment until an error as in the rule above), but a double-precision floating-point format still has 22-bit fraction and 8-bit exponent.
  • Score is calculated as: Pl-1.5l, where P is the probability and l is the byte length.

Example(s)

JavaScript
alert(Math.random()<0.1)
P=0.1, l=24 => Score=23.534

The lowest score wins!

||||||
\$\endgroup\$
  • \$\begingroup\$ So is it acceptable for just a program that always outputs truly? You need to define improbable. (I assume this probability must be at least lest than 1/2.) Providing a few examples will be helpful. So is there only output and no input? In addition, you need an objective winning criterion, which is a criterion that posts for this challenge will need to comply in order for it to be a valid answer. (Usually this criterion is making the source code shortest.) \$\endgroup\$ – user85052 Sep 24 '19 at 13:37
  • \$\begingroup\$ Sorry, I posted this incomplete. \$\endgroup\$ – Naruyoko Sep 24 '19 at 16:14
  • \$\begingroup\$ I don't think your scoring method works particularly well, unless I'm making an error. For any \$ l > 1 \$ your score cannot be less than 1. Achieving a score arbitrarily close to 1 is relatively easy. So the only way to beat that is to have a one or zero byte solution. It is easy to make the probability increase exponentially with linear code additions. It might be necessary to penalise length massively, like \$ P \times e^{l!} \$, to avoid similar problems. \$\endgroup\$ – FryAmTheEggman Sep 24 '19 at 18:39
  • \$\begingroup\$ I see. I guess P^l^k is too penalizing but Pk or Pe^k is too forgiving. Pe^l! looks simple enough but is is the middle so it may work. \$\endgroup\$ – Naruyoko Sep 24 '19 at 20:11
  • 1
    \$\begingroup\$ The problem with any of scoring methods for this challenge is that it is possible for any increasing computable function f, a program with length l can have P around 1/f(l). The only non-broken formula could be uncomputable, i.e. P/BB(l), where BB is the busy beaver function. \$\endgroup\$ – Naruyoko Sep 24 '19 at 20:15
-2
\$\begingroup\$

I reverse the source code, you keep the output

Yet another blatant rip-off of a rip-off of a rip-off of a rip-off. Go upvote those!

Your task, if you wish to accept it, is to write a program/function that outputs/returns its own output. The tricky part is that if I reverse your source code, the output must be preserved.

Examples

Let's say your code is ABC and the corresponding output is XYZ. If I run CBA, the output must also be XYZ

||||||
\$\endgroup\$
  • 3
    \$\begingroup\$ What's to prevent a trivial solution of just 1 in many (many) languages? \$\endgroup\$ – AdmBorkBork Sep 25 '19 at 18:30
  • \$\begingroup\$ Or trivial comment abuse? \$\endgroup\$ – S.S. Anne Sep 25 '19 at 20:39
  • \$\begingroup\$ @JL2210 This works in codegolf.stackexchange.com/questions/193315/… print("ABC")#("ABC")tnirp \$\endgroup\$ – gadzooks02 Sep 26 '19 at 15:21
  • \$\begingroup\$ @AdmBorkBork This works in codegolf.stackexchange.com/questions/193315/… too: 1 is the reverse of 1 \$\endgroup\$ – gadzooks02 Sep 26 '19 at 15:22
  • \$\begingroup\$ And to both of you: why did these not stop that code golf becoming a challenge? \$\endgroup\$ – gadzooks02 Sep 26 '19 at 15:23
  • 2
    \$\begingroup\$ I didn't say it couldn't be a challenge. I just wanted to point out that this is trivial in many languages. And for what it's worth, I downvoted the challenge you linked for the same reason. \$\endgroup\$ – AdmBorkBork Sep 26 '19 at 15:48
  • \$\begingroup\$ @gadzooks02 That challenge requires you to reverse the input. The input can be anything in that challenge. \$\endgroup\$ – S.S. Anne Sep 26 '19 at 15:49
  • \$\begingroup\$ @JL2210 Ah yes. Would preserve the input work better? \$\endgroup\$ – gadzooks02 Sep 26 '19 at 16:02
  • \$\begingroup\$ No, then it would be trivial in Bash and BrainFuck and C and, well, you get the point. \$\endgroup\$ – S.S. Anne Sep 26 '19 at 16:26
  • \$\begingroup\$ @JL2210 Yes, OK. Do I need to do something if I've decided against a challenge? Delete the post? \$\endgroup\$ – gadzooks02 Sep 26 '19 at 16:29
  • \$\begingroup\$ No idea. Read over the guidelines, they might help. \$\endgroup\$ – S.S. Anne Sep 26 '19 at 16:31
-2
\$\begingroup\$

print 1000 digits of \$\pi\$ base 3

The question was on hold for "unclear what you're asking". Really? What was the real reason?

No input. We need to compute and print the values of \$\pi\$ and Euler constant \$\gamma\$
to \$1000\$ digits after decimal point
in base \$3\$ with digits \$-1,0,1\$ represented as -,0,+ respectively.

For \$\pi\$ output is likely starts with +0.0++-+++-000-0++-++0+-++++++00--++.
\$\pi\$ can be computed as series of \$\tan^{-1}\$, \$\gamma\$ -- like here, or any other method will do if fast enough to provide needed accuracy for at most \$60\$ seconds for both numbers.

Storing or using entire pre-computed values are forbidden.
One may though use wolframalpha regular-base-3 values for checking their output -- for \$\pi\$ and \$\gamma\$ (hit "More digits" some times to get \$1000\$).

Scoring method is code-golf, but TIO should run at most \$60\$ seconds.
Good luck. Please fell free to improve this post.

||||||
\$\endgroup\$
  • 3
    \$\begingroup\$ "Storing or using entire pre-computed values are forbidden" is definitely one source of unclarity. What amount of pre-computation could be done? All but the last digit? All but two? Further there doesn't seem to be any reason to ask for two numbers, nor is there a on-site way to check the results. You shouldn't make your answerers have to go to an external site to verify their submission. \$\endgroup\$ – FryAmTheEggman Nov 21 '19 at 19:43
-2
\$\begingroup\$

Introduction

As programming languages reproduce are created, documentation is even more important for programmers. Your task is simple: output the esolangs.org documentation for your programming language.

With wikis being wikis, languages are heavily penalized in this challenge for being used often and for being interesting to write about, the goal here is to draw attention to languages that may not get utilized otherwise.

Challenge

For this task, you will need to output the source for the article on esolangs.org for your language, with greater than or equal to 95% accuracy. Your score is your program length in bytes, as in other challenges.

Languages not on this multi-page list of languages as of the time of this posting are ineligible.

Standard loopholes are forbidden.

Inputs

None

Output

The source (as of this challenge being posted), for the esolangs wiki page for your language, with at least 95% accuracy.

Example

Language: ///

Output:

{{featured language}}
'''///''' (pronounced "slashes") is a minimalist [[Turing-complete]] esoteric programming language, invented by Tanner Swett ([[User:Ihope127]]) in 2006 based on [[wikipedia:sed|the "s/foo/bar/" notation that everybody seemed to be using in IRC]]. The only operation is repeated string substitution, using the syntax <code>/''pattern''/''replacement''/</code>. Despite its extreme simplicity – there isn't even an obvious way to create a loop – it was proved [[Turing-complete]] by [[Ørjan Johansen]] in 2009, who created [[#Bitwise Cyclic Tag interpreter|an interpreter]] for the Turing-complete language [[Bitwise Cyclic Tag]].
...

||||||
\$\endgroup\$
  • 4
    \$\begingroup\$ -1: Interesting idea, but I don't think it can work as a challenge. I'm not convinced that kolmogorov-complexity-ing a volatile data source is a good idea. What happens if the page is edited two weeks from now? \$\endgroup\$ – Beefster Dec 13 '19 at 22:39
  • \$\begingroup\$ Loophole. I blanked the esolangs.org documentation of my language. Therefore I can output nothing to achieve my goal. \$\endgroup\$ – user85052 Dec 18 '19 at 4:07
  • \$\begingroup\$ @A̲̲ nope, you have to output what it was at the time of posting \$\endgroup\$ – iPhoenix Dec 18 '19 at 11:53
  • \$\begingroup\$ Obviously, you blank the page and then post before it gets fixed. \$\endgroup\$ – my pronoun is monicareinstate Dec 19 '19 at 13:55
-2
\$\begingroup\$

Finite Elements from Scratch


Background

"The finite element method (FEM), is a numerical method for solving problems of engineering and mathematical physics." -Wikipedia

One of the elementary formulations of fem in structural engineering is the truss. They are very basic, but have a lot of utility.

When one designs a truss, especially in the preliminary stages some assumptions are usually made to simplify the procedure. For instance, members are assumed to carry only tension or compression load. This means that we can only load the truss at the nodals points. Depending on how the connection is designed and detailed, these assumptions can be quite close to how the structure actually will behave in the real world.

So, what's so special about having a member with only axial loading? Well, there's a property of the material itself we can take advantage of. Most materials have a property of 'linear elasticity' when the material is stretched or compressed a very small amount. A material like steel is quite ductile, and so this range of linear elasticiticy is quite large, as compared to something like ceramics. This means if we push or pull on some steel with a small force, it will displace a proportional amount. If we double our applied force, its displacement will double as well. Also if we release our force, the material will go back to its original configuration. So as long as we deform the material elastically, we won't waste any energy deforming it plastically.

If you have ever taken a physics class, you may know that a spring has these exact same properties. Therefore, we can idealize all the members in our truss as just simple springs.


Building up to direct stiffness method

A zero dimensional spring equation looks like this. $$ K \cdot u = F $$ This relates the force required to any deformation of the spring. The force and deformation are linearly proportional by \$K\$, the spring constant. The constant \$K\$ has units of [force/distance] e.g. [pounds/in] or [kilograms/meter]. For example, if \$K = 50 lb/in\$, it would take \$50lb\$ of force to displace the spring \$1\$ inch, and \$100lb\$ to displace the spring \$2\$ inches. The stiffness in our truss members is similar:

$$ K = \frac{EA}{L} $$

\$E\$ is Young's Modulus, \$A\$ is the cross sectional area, and \$L\$ is the length of the bar. The only scary thing here is probably \$E\$, but it's not too crazy. It's kind of like stiffness, but it's normalized. Instead of [force/distance] we have [stress/strain]. Stress is like the normalized force, it's the amount of force over the area of the element. Strain is like the normalized displacement, it's calculated by (change in length/original length) or percent elongation.

Let's develop this a bit more and put it in matrix form. This will allow us to relate the force on one side of the bar to force on the other.

$$ \frac{EA}{L} \left[\begin{array}{cc} 1 & -1\\ -1 & 1 \\ \end{array}\right] \cdot \left[\begin{array}{c} u_1 \\ u_2 \\ \end{array}\right] = \left[\begin{array}{c} f_1 \\ f_2 \\ \end{array}\right] $$

Now we have our one dimensional spring equation. Instead of a single displacement, we have a displacement vector. We can displace both sides of the spring independently and find what the resultant forces on each side will be.

Examples:

Displace the right node 1 unit to the right $$ \frac{EA}{L} \left[\begin{array}{cc} 1 & -1\\ -1 & 1 \\ \end{array}\right] \cdot \left[\begin{array}{c} 0 \\ 1 \\ \end{array}\right] = \left[\begin{array}{c} f_1 \\ f_2 \\ \end{array}\right]\\ f_1 = \frac{-E A}{L}, f_2 = \frac{E A}{L} $$

This makes sense, because if we displace the right side by a unit, we need a force in the equal and opposite direction on the left side to not drag that side along.

Displace both nodes \$1\$ unit to the right $$ \frac{EA}{L} \left[\begin{array}{cc} 1 & -1\\ -1 & 1 \\ \end{array}\right] \cdot \left[\begin{array}{c} 1 \\ 1 \\ \end{array}\right] = \left[\begin{array}{c} f_1 \\ f_2 \\ \end{array}\right]\\ f_1 = 0, f_2 = 0 $$

This makes sense, because if we displace both sides at the same time, the distance between them does not change. It would be as if we just translated the spring across the table and did not strech it. We don't need some force holding it in a deformed configuration.

That's cool, but one dimensional structures are lame. I want a two dimensional structure to build a bridge! Well, it's not that much more difficult. We just need to add a \$y\$ degree of freedom (dof) on each side of the spring. We can also couple our \$x\$ and \$y\$ dofs into one angle from the \$+x\$ direction to simplify our matrix. And so with some magic (rotational matrix) we can get the following:

Step 1 - Local Stiffnes Matrix

This is our local stiffness matrix, also known as \$K^e\$. It has all the same properties as our one dimensional stiffness matrix, but it takes into account \$(x,y)\$ displacements at each side of the spring. This gives us a total of four degrees of freedom.

You may begin to see how powerfull this method can be. We can now iterate through all of our elements and just calculate the angle and length from its nodes. This will give us \$i\$ local stiffness matrices, where \$i\$ is the number of elements. For example if we have \$3\$ elements in our truss, we can calculate our \$3\$ local matrices for each element.

Let's go through an example.

If we calcualted the local stiffness matrices for the figure above (\$EA = 1\$, \$L(1,2)=1\$), you would find: $$ \hspace{50pt}\begin{array}{cccc}1 & 2 & 3 & 4\\\end{array} \\ K(1) = \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} \left[\begin{array}{cccc} 1 & 0 & -1 & 0\\ 0 & 0 & 0 & 0\\ -1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ \end{array}\right] $$ $$ \hspace{50pt}\begin{array}{cccc}3 & 4 & 5 & 6\\\end{array} \\ K(2) = \begin{array}{c} 3 \\ 4 \\ 5 \\ 6 \\ \end{array} \left[\begin{array}{cccc} 0 & 0 & 0 & 0\\ 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 0\\ 0 & -1 & 0 & 1\\ \end{array}\right] $$ $$ \hspace{50pt}\begin{array}{cccc}1 & 2 & 5 & 6\\\end{array} \\ K(3) = \begin{array}{c} 1 \\ 2 \\ 5 \\ 6 \\ \end{array} \left[\begin{array}{cccc} 0.64 & 0.48 & -0.64 & -0.48\\ 0.48 & 0.36 & -0.48 & -0.36\\ -0.64 & -0.48 & 0.64 & 0.48\\ -0.48 & -0.36 & 0.48 & 0.36\\ \end{array}\right] $$

Where the numbers outside the array correspond to the global matrix indicies.

Step 2 - Assemble local matrices into the global matrix

These local matricies are uncoupled, and so they don't really tell us much about the global system of the truss, or how to solve for the displacements with given forces. However, we can do something called matrix assembly to put them all into one big global stiffness matrix. This will couple all of our local element equations so we can solve our system of equations.

We do this by matching the local degrees of freedom to our global degrees of freedom, then add our local to our global matrix.

Since our global truss has 3 nodes and each node has \$2\$ dofs \$(x,y)\$, our global matricies are of size 6. \$K \in \mathbb R^{6 \times 6}, F \in \mathbb R^{6 \times 1}, u \in \mathbb R^{6 \times 1}\$. If we layed out the dof number for each row/column of our stiffness matrix we would get the following:

$$ \hspace{35pt}\begin{array}{cccccc}1 & 2 & 3 & 4 & 5 & 6\\\end{array} \\ K = \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ \end{array} \left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ \end{array}\right] $$

From step 1, the global dofs of \$k(1)\$ were \$1,2,3,4\$. This means we just add them index by index into our global stiffness matrix.

$$ \hspace{35pt}\begin{array}{cccc}1 & 2 & 3 & 4\\\end{array} \\ k(1) = \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} \left[\begin{array}{cccc} k_{11} & k_{12} & k_{13} & k_{14}\\ k_{21} & k_{22} & k_{23} & k_{24}\\ k_{31} & k_{32} & k_{33} & k_{34}\\ k_{41} & k_{42} & k_{43} & k_{44}\\ \end{array}\right] $$

If we match up the indicies, we can just add: $$ K_{11} += k_{11}\\ K_{12} += k_{12}\\ K_{13} += k_{13}\\ K_{14} += k_{14}\\ K_{21} += k_{21}\\ ... $$

We can see if we do this for all three elements, we can match up where they will go in the global matrix with colors. This is shown in the figure below.

Step 3 - Add bounds on the stiffness matrix, and modify the force vector

We are almost done! But there is one final important step. If we were given an arbitrary force vector and tried to find the displacements, our truss would just fly away to infinity. This is because there are no boundary conditions! There is nothing yet holding on to it, resisting the forces. But guess what? There's another neat trick we can use. This will keep everything in matrix form and give us the answers we want when we solve our system of equations.

All we do is remove the influence of the node on the force vector. For this example, we will assume the constraint on dof1 is set to \$g\$.

For the general case, we just set \$dof1 = g\$ in the force vector, and subtract g* the column of \$K\$ with dof1 = 0. If \$g=0\$, we just need to set \$dof1 = 0\$ in the force vector.

$$ F = \left[\begin{array}{c} F_1\\ F_2\\ F_3\\ \vdots\\ F_n\\ \end{array}\right] \Rightarrow \left[\begin{array}{c} g\\ F_2\\ F_3\\ \vdots\\ F_n\\ \end{array}\right] - g \left[\begin{array}{c} 0\\ K_{21}\\ K_{31}\\ \vdots\\ K_{n1}\\ \end{array}\right] $$

Then we just restrain our stiffness matrix. This can be done by zeroing out the row and column of \$dof1\$, then setting \$(dof1,dof1)=1\$ as shown below.

$$ K = \left[\begin{array}{cccc} K_{11} & K_{12} & \cdots & K_{1n}\\ K_{21} & K_{22} & \cdots & K_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ K_{n1} & K_{n2} & \cdots & K_{nn}\\ \end{array}\right] \Rightarrow \left[\begin{array}{cccc} 1 & 0 & \cdots & 0\\ 0 & K_{22} & \cdots & K_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ 0 & K_{n2} & \cdots & K_{nn}\\ \end{array}\right] $$

Step 4 - Solve with linear algebra

Now we are finally back to our equation of a spring. However, in this case each variable below is an array or vector of size \$n\$, where \$n\$ is the number of \$nodes \times 2\$.

$$ \mathbf{K} \cdot \mathbf{u} = \mathbf{F} $$

We can simply solve this system of equations by taking the inverse of the stiffness matrix. This gives us:

$$ \mathbf{u} = \mathbf{K}^{-1} \cdot \mathbf{F} $$

This can be easily solved by a computer. For example Python:

    u = np.linalg.solve(K, F)

Rules

  • Input data type can for the most part be changed for your needs. However, it should be human-readable, or at least reasonable to be able to change the input for a new structure easily.

Example input

E = .
A = .
nodes = [., ., ...]
elements = [., ., ...]
forces = [., ., ...]
bounds = [., ., ...]

Example output

[., ., ...]
  • Output can be in any form, as long as it's in order of dof.
  • Inbuilt FEM functions not allowed. You must construct and assemble your matrices yourself. Inbuilt linear algebra is fine.

Test Cases

From UNM example in references:

E = 29500
A = 1
nodes = [[0,0],[40,0],[40,30],[0,30]]
elements = [[1,2],[2,3],[1,3],[3,4]]
forces = [[0,0],[20,0],[0,-25],[0,0]]
bounds = [[0,0],[None,0],[None,None],[0,0]]

Output:

[0.0 0.0 0.027 0.0 0.006 -0.022 0.0 0.0]

Large Truss Input:

E = 29000
A = 25
nodes = [[0,0],[100,0],[200,0],[300,0],[0,100],[100,100],[200,100],[300,100],[400,100]]
elements = [[1,2],[1,5],[1,6],[2,3],[2,6],[2,7],[3,4],[3,7],[3,8],[4,8],[4,9],[5,6],[6,7],[7,8],[8,9]]
forces = [[0,-10],[0,-10],[0,-10],[0,-10],[0,0],[0,0],[0,0],[0,0],[0,-10]]
bounds = [[0,0],[None,None],[None,None],[None,None],[-0.01,0],[None,None],[None,None],[None,None],[None,None]]

Output:

[ 0.     0.    -0.008 -0.025 -0.012 -0.061 -0.014 -0.1   -0.01   0.     0.004 -0.019  0.012 -0.057  0.016 -0.098  0.018 -0.136]

Here is what the geometry and displacement looks like for the test cases so you can visualize it.


References

Here are some references that may be useful if you are looking for some more in-depth information.

http://www.unm.edu/~bgreen/ME360/Finite%20Element%20Truss.pdf

https://engineering.purdue.edu/~aprakas/CE474/CE474-Ch5-StiffnessMethod.pdf

http://people.duke.edu/~hpgavin/cee421/truss-method.pdf

http://ocw.ump.edu.my/pluginfile.php/9806/mod_resource/content/2/7_Plane_Truss_Example.pdf

https://nptel.ac.in/content/storage2/courses/105105109/pdf/m4l24.pdf

And lastly, here is some working python 3 code that I wrote. It should lay out all the steps cleanly.

import numpy as np
from math import sqrt,sin,cos,acos

def ex_unm():
    """Example - Verification from UNM"""
    print("Example UNM")
    # Material Properties
    E = 29500 # (units = ksi)
    A = 1 # (units = in^2)
    # Node locations (units = in)
    nodes = {1:(0,0), 2:(40,0), 3:(40,30), 4:(0,30)}
    # Element connections
    elements = {1:(1,2), 2:(3,2), 3:(1,3), 4:(4,3)}
    # Nodal forces (units = kips)
    forces = {2:(20,0), 3:(0,-25)}
    # Nodal Boundaries (units = in)
    bounds = {1:{'x':0,'y':0},2:{'y':0},4:{'x':0,'y':0}}
    # Run Analysis
    displacements = analyze(E,A,nodes,elements,forces,bounds)
    for i,disp in enumerate(displacements):
        print("Node {},{}: {}".format(int(i/2)+1,['x','y'][i%2],round(disp,5)))

    plot_truss(nodes, elements, displacements, 200)

def ex_big_boi():
    """Example - Large Truss"""
    print("Example BIG BOI")
    # Material Properties
    E = 29000 # (units = ksi)
    A = 25 # (units = in^2)
    # Node locations (units = in)
    nodes = {1:(0,0), 2:(100,0), 3:(200,0), 4:(300,0),
        5:(0,100), 6:(100,100), 7:(200,100), 8:(300,100), 9:(400,100)}
    # Element connections
    elements = {1:(1,2), 2:(1,5), 3:(1,6),
        4:(2,3), 5:(2,6), 6:(2,7),
        7:(3,4), 8:(3,7), 9:(3,8),
        10:(4,8), 11:(4,9),
        12:(5,6), 13:(6,7), 14:(7,8), 15:(8,9)}
    # Nodal forces (units = kips)
    forces = {1:(0,-10), 2:(0,-10), 3:(0,-10), 4:(0,-10), 9:(0,-10)}
    # Nodal Boundaries (units = in)
    bounds = {1:{'x':0,'y':0}, 5:{'x':-0.01,'y':0}}
    #bounds = {1:{'x':0,'y':0}, 5:{'x':0,'y':0}}
    # Run Analysis
    displacements = analyze(E,A,nodes,elements,forces,bounds)
    for i,disp in enumerate(displacements):
        print("Node {},{}: {}".format(int(i/2)+1,['x','y'][i%2],round(disp,5)))

    plot_truss(nodes, elements, displacements, 500)


"""Visualization, not really needed but may be good to see"""
import matplotlib.pyplot as plt

def plot_truss(nodes, elements, u, scale):
    """A very simple plot to show geometry and displacements of nodes"""
    x = [coords[0] for node,coords in nodes.items()]
    y = [coords[1] for node,coords in nodes.items()]
    ux = x + u[::2] * scale
    uy = y + u[1::2]* scale

    fig,ax = plt.subplots()
    # Plot original Points
    ax.plot(x,y,'o',color=(0.5,0.5,0.5))
    # Plot original Elements (Theres probably a better way to do this)
    for element,eleNodes in elements.items():
        ex = [x[i-1] for i in eleNodes]
        ey = [y[i-1] for i in eleNodes]
        ax.plot(ex,ey,color=(0.5,0.5,0.5))

    # Plot displaced Points
    ax.plot(ux,uy,'o',color=(0,0,1))
    # Plot displaced Elements (Theres probably a better way to do this)
    for element,eleNodes in elements.items():
        ex = [ux[i-1] for i in eleNodes]
        ey = [uy[i-1] for i in eleNodes]
        ax.plot(ex,ey,color=(0,0,1))

    # Make plot have same xy scale
    ax.axis('equal')
    #fig.tight_layout()
    ax.set_title("Truss Geometry and Displacement, Scale = {}".format(scale))







def analyze(E, A, nodes, elements, forces, bounds):
    """Analyze a given system and return the nodal displacements"""
    # Assemble global matricies
    K = gen_global_K(E,A,nodes,elements)
    F = gen_global_F(nodes,forces)
    # Add bounds to matricies
    #F = restrain_stiffness(K, F, bounds)
    restrain_stiffness(K, F, bounds)
    # Solve K*u=F -> u=K^-1*F
    u = np.linalg.solve(K, F)
    # return the nodal displacements
    return u

def gen_global_K(E, A, nodes, elements):
    """Generate the Global stiffness Matrix"""
    # Initialize Global Stiffness Matrix
    size = len(nodes)*2
    K = np.zeros([size,size])

    # Itterate through each element and add its local stiffness to global stiffness
    for element,(node_1,node_2) in elements.items():
        node_1_xy = nodes[node_1]
        node_2_xy = nodes[node_2]
        # Element length
        L = sqrt((node_2_xy[0]-node_1_xy[0])**2 + (node_2_xy[1]-node_1_xy[1])**2)
        # Get this element's local stiffness roated into global plane
        K_local = (E*A/L) * gen_local_K(node_1_xy, node_2_xy)
        # Assemble local matrix into global 
        assemble(K, K_local, node_1, node_2)
    return K

def gen_local_K(n1, n2):
    """Create a local stiffness matrix from two nodes' angle"""
    angle = gen_angle(n1,n2)
    c  = cos(angle)**2
    s  = sin(angle)**2
    cs = cos(angle) * sin(angle)
    # Create the local K matrix
    K_local = np.array([[ c , cs,-c ,-cs],
                        [ cs, s ,-cs,-s ],
                        [-c ,-cs, c , cs],
                        [-cs,-s , cs, s ]])
    return K_local

def gen_angle(n1, n2):
    """Find angle between two nodes and +x axis"""
    v1 = np.array([n2[0]-n1[0],n2[1]-n1[1]])
    v2 = np.array([1,0])
    return acos(np.dot(v1,v2) / (np.linalg.norm(v1) * np.linalg.norm(v2)))

def assemble(K, K_local, n1, n2):
    """Assemble a local element stiffness matrix into the global stiffness"""
    # Degrees of freedom of our local element
    dofs = [2*(n1-1), 2*(n1-1)+1, 2*(n2-1), 2*(n2-1)+1]
    # Go element by element to add matrix
    for i_local,i_global in enumerate(dofs):
        for j_local,j_global in enumerate(dofs):
            K[i_global,j_global] += K_local[i_local,j_local]

def gen_global_F(nodes, forces):
    """Generate the global force vector"""
    F = np.zeros(2*len(nodes))
    for node,(f_x,f_y) in forces.items():
        dof = 2*(node-1)
        F[dof] = f_x
        F[dof+1] = f_y
    return F

def restrain_stiffness(K, F, bounds):
    """Use a given displacement bound to modify matricies"""
    dir = {'x':0, 'y':1}
    for node,this_bound in bounds.items():
        for coord,disp in this_bound.items():
            # Get what dof the bound is
            dof = (node-1)*2 + dir[coord]
            add_disp(K, F, disp, dof)

def add_disp(K, F, disp, n):
    """Move the fixed displacement over to F (since it's constant)"""
    # Get displaced F by reducing by given displacement * stiffness column
    # Must use -= to ensure python evaluates in-place
    #   We don't need to return the array if it's passed by reference
    F -= disp * K[:,n]
    # Set the Force value at that dof to the given displacment
    F[n] = disp
    # Clear stiffness matrix dof row & col
    add_bound(K, n)

def add_bound(K, n):
    """Zero out row and col of dof, then make [n,n] = 1"""
    for i in range(np.size(K,0)):
        K[n,i] = 0
        K[i,n] = 0
    K[n,n] = 1

if __name__ == "__main__":
    # Set print options if you want to print an array nicely (easier for debug)
    np.set_printoptions(precision=2, suppress=True, linewidth=np.inf)
    ex_unm()
    ex_big_boi()

    plt.show()

Good Luck!

||||||
\$\endgroup\$
  • \$\begingroup\$ Really cool introduction to FEM! I allowed myself to make some corrections and convert some more equations to mathjax, I hope you are ok with that. Some points I noticed that I would suggest improving: If you introduce a new variable, always describe what it is: It doesn't seem clear from the start what \$u\$ is (displacement?) or how \$\beta\$ is defined. Then I'd also try to make the indexing consistent: I'd always use the indices like \$K_i\$ insetad of \$K(i)\$. \$\endgroup\$ – flawr Dec 28 '19 at 14:32
  • \$\begingroup\$ Similarly I'd avoid reusing the same symbol: For example for \$k(1)\$ you reuse the symbol \$k\$ for its entries, so I'd recommend rewriting it as maybe \$\vec k_1\$. \$\endgroup\$ – flawr Dec 28 '19 at 14:35
  • \$\begingroup\$ You talk about the degrees of freedom "dofs", aren't these just the entries of \$u\$? \$\endgroup\$ – flawr Dec 28 '19 at 14:37
  • 2
    \$\begingroup\$ And what type of challenge is it anyway? code-golf or something else? \$\endgroup\$ – flawr Dec 28 '19 at 14:37
  • \$\begingroup\$ Thanks! Yea, the u vector is the displacement of each node. It is common to have it in the form {node1 x, node1 y, node2 x, node2 y.,,,}. Each element of the vector would be a degree of freedom, and together they would be the degrees of freedom of the entire structure. However, the u vector is not the actual degrees of freedom, it is just the displacements at each degree of freedom. For instance, the force vector would have a force at each degree of freedom. I think it wold be standard code-colf, least bytes wins, however I'm not sure if there's a better challenge it should go into. \$\endgroup\$ – WretchedLout Dec 29 '19 at 4:21
-2
\$\begingroup\$

101 Hello Worlds

I have a project where I'm trying to collect 101 versions of "Hello, World" using obscure and over-engineered approaches in JavaScript/Node.js:

https://github.com/georgemandis/101-hello-worlds

We're up to 38 so far and I've really enjoyed the community contributions.

I recognize the way this is phrased at the moment isn't compatible with the way Code Golf is setup, but I feel like there could be a large overlap with people who might be interested and this community.

Does this seem like something that would be welcome here? Would others have suggestions for how I might re-word this to create a suitable entry for Code Golf?

If it's not suitable or welcome here I respect being downvoted into oblivion and can remove the answer.

Thanks!

||||||
\$\endgroup\$
  • 2
    \$\begingroup\$ Thanks for using the Sandbox. The answer is that no, this isn't really suited to the Code Golf site. The closest winning criterion to use would be popularity-contest, but that was retired a while ago, since it wasn't really objective. If you want inspiration though, you can look at the hello-world tag, which has a lot of interesting restrictions on hello world programs. For example, there's no repetition, radiation-hardened, polyglots, palindromes etc. \$\endgroup\$ – Jo King Feb 11 at 4:52
  • \$\begingroup\$ Thanks @JoKing. I'll take a look at that tag. I think I'll add a tag to it in my project's README as well to give other people inspiration. \$\endgroup\$ – George Mandis Feb 11 at 14:28
-2
\$\begingroup\$

Hello, World, but looong


I couldn't find out that this challenge exists

If this challenge exists, let me know


Write a simple Hello, World! program.

The winner is the person who has the longest code.

However, any subsequence except itself cannot be the answer.

Input

You can have input in which way.

Output

Hello, World!
||||||
\$\endgroup\$
-2
\$\begingroup\$

Check if There is a Valid Path in a Grid

Given a m x n grid. Each cell of the grid represents a street. The street of \$grid[i][j]\$ can be:

  • 1 which means a street connecting the left cell and the right cell.
  • 2 which means a street connecting the upper cell and the lower cell.
  • 3 which means a street connecting the left cell and the lower cell.
  • 4 which means a street connecting the right cell and the lower cell.
  • 5 which means a street connecting the left cell and the upper cell.
  • 6 which means a street connecting the right cell and the upper cell.

Grid path

You will initially start at the street of the upper-left cell \$(0,0)\$. A valid path in the grid is a path that starts from the upper left cell \$(0,0)\$ and ends at the bottom-right cell \$(m - 1, n - 1)\$. The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise

Test Case 1: enter image description here

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the 
grid to reach (m - 1, n - 1).

Test Case 2: enter image description here

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of 
any other cell and you will get stuck at cell (0, 0)

Testcase 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Testcase 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Test Case 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Please feel free to add more test cases.

This is code-golf so shortest submission in bytes wins! If you liked this challenge, consider upvoting it... And happy golfing!

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ May I use a different numbering/encoding to encode the six tiles? One example could be using 3, 5, 6, 9, 10, 12 to utilize bitwise ops, or a 4-element array per tile e.g. [0, 0, 1, 1], [0, 1, 0, 1], etc. \$\endgroup\$ – Bubbler Mar 24 at 8:13
  • 1
    \$\begingroup\$ You might want to clarify that the path is not required to cover every single cell (or the opposite). Also, are the top left and bottom right corners guaranteed to have a single side connected to the outside, e.g. 4 or 5 will never appear at the top left? \$\endgroup\$ – Bubbler Mar 24 at 8:19
  • \$\begingroup\$ Nothing to add to Bubbler's comments other than maybe make the images smaller and/or replace them with ASCII or Unicode diagrams. (imgur is blocked by some networks). \$\endgroup\$ – Adám Mar 24 at 15:40
  • 2
    \$\begingroup\$ This also has the issue of being a LeetCode problem, which you presumably don't have permission to post here. \$\endgroup\$ – xnor Mar 25 at 0:56
-2
\$\begingroup\$

Longest happy prefix

A prefix of a string is a happy prefix if it's also a suffix of that string, but not if it's the entire string. This means that the string both begins and ends with it.

Given a non-empty string s, return the longest happy prefix of s. Note that this can be the empty string.

Test Cases:

Case 1:

Input: s = "level"
Output: "l"

Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix
("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".

Case 2

Input: s = "ababab"
Output: "abab"

Explanation: "abab" is the largest prefix which is also suffix. 
They can overlap in the original string.

Case 3:

Input: s = "a"
Output: ""

Please feel free to add more test cases.

This is code-golf so shortest submission in bytes wins! If you liked this challenge, consider upvoting it... And happy golfing!

||||||
\$\endgroup\$
  • \$\begingroup\$ Would answering with the length not be reasonable? \$\endgroup\$ – Adám Mar 24 at 9:19
  • \$\begingroup\$ What else Should I ask to return?? \$\endgroup\$ – Krishna Mar 24 at 15:31
  • \$\begingroup\$ "Given a string s. Return the longest happy prefix of s ." → "Given a string s. Return the longest happy prefix of s or its length." \$\endgroup\$ – Adám Mar 24 at 15:32
  • \$\begingroup\$ If you remove "non-empty" you can also remove "Return an empty string if no such prefix exists." \$\endgroup\$ – Adám Mar 24 at 15:35
  • \$\begingroup\$ I tried to clear up the wording a bit. \$\endgroup\$ – xnor Mar 25 at 0:52
  • 3
    \$\begingroup\$ Wait, this is also a LeetCode problem! Are all of your challenges really copy-pasted from LeetCode and similar sites? That's not OK to do, unless you've been somehow given explicit permission to post them here. \$\endgroup\$ – xnor Mar 25 at 1:07
-3
\$\begingroup\$

Code-challenge: Guess my number

The challenge

You have a number from 1 to 10 in mind, and your program should ask questions to find out which number. These questions can be any questions, the program only has to find out the number as fast as possible.

Your program should ask a question, such as "Is the number a prime?", and the user must answer either y or n (yes or no). Ask questions until you know the number.

The scoring

To calculate the score, you need to take the sum of the question count for each number. For example, if you need 1 question to find the number 1, 2 questions to find the number 2, and so on, the score is 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10, so the score is 55.

Important note: the question count for a specific number must always be the same. For example, if you need 4 questions to find out the number 10, then you have to ask always 4 questions to find out the number 10, otherwise it is impossible to calculate the score.

||||||
\$\endgroup\$
  • 5
    \$\begingroup\$ boooring. The Huffman tree for a uniform set is any perfectly balanced tree. The question asks us to perform a binary search on the usr device. Is the number greater than 5? Is the number greater than 2? Is the number greater than 1? Hey' I think it's 1. \$\endgroup\$ – John Dvorak Jan 2 '14 at 11:49
  • 3
    \$\begingroup\$ Maybe if this were a pop-contest and the goal was to make the most original set of questions while still keeping the score at its theoretical minimum. \$\endgroup\$ – John Dvorak Jan 3 '14 at 5:28
-3
\$\begingroup\$

Bovine Ignorance

I'm curious about code which still works after being mangled by figlet, toilet, cowsay et al, but I'm not sure whether this in any way sane.

What I'm toying with is a challenge in which a participant may submit any program in any language. It should be possible to use this program's source code as input to cowsay or whatever, and the result should be another valid program in any language, which still does a similar thing. For instance, the following bf program prints Hello world! with no newline:

+++++ +++++
[
> +++++ ++
> +++++ +++++
> +++
> +
<<<< -
]
> ++ .
> + .
+++++ ++ .
.
+++ .
> ++ .
<< +++++ +++++ +++++ .
> .
+++ .
----- - .
----- --- .
> + .
+++++++++++++++++++++++++++++++++++++++++

Running cat ./prog.bf | cowsay -e .. -T $'>.' yields the following output:

 _________________________________________
/ +++++ +++++ [ > +++++ ++ > +++++ +++++  \
| > +++ > + <<<< - ] > ++ . > + . +++++   |
| ++ . . +++ . > ++ . << +++++ +++++      |
| +++++ . > . +++ . ----- - . ----- --- . |
| > + .                                   |
| +++++++++++++++++++++++++++++++++++++++ |
\ ++                                      /
 -----------------------------------------
        \   ^__^
         \  (..)\_______
            (__)\       )\/\
             >. ||----w |
                ||     ||

Which is itself a valid bf program which prints Hello world!!!, followed by a newline.

The problem with using bf here is that it ignores most of the cow, making this a bit too easy. The problem with using any other language is that it doesn't ignore most of the cow, making this far too difficult. Is there a sensible middle ground I could pick for this? I don't think it's impossible, I'm fairly sure you can exploit cowsay's behavior on one-liners to produce valid svgs, but I'm not sure how best to pose this challenge. Any ideas?

||||||
\$\endgroup\$
  • 2
    \$\begingroup\$ I could not think of any language that falls in the middle ground. Even brainfuck is affected by the -----------------------------------------..>.---- inserted by cowsay. Most languages have strong parsing rules that would not cope with being post-processed by cowsay. The few exceptions for this will be either completely unaffected or badly affected, making the challenge uninteresting. \$\endgroup\$ – Victor Stafusa Feb 19 '14 at 12:32
  • \$\begingroup\$ Actually, you can't transform just any brainfuck program to cowsay-brainfuck. Namely those that can output fewer than three characters cannot be transformed at all. \$\endgroup\$ – John Dvorak Feb 19 '14 at 14:52
  • \$\begingroup\$ @JanDvorak, I was intending to allow competitors to choose the parameters of their calls to cowsay. For the uninitiated, -e controls the string used for eyes and defaults to oo, and -T controls the string used for the tongue, defaulting to ` U`. This is all yak-shaving, though, and having written this up and read the comments, I suspect that this idea has neither legs, horns nor udders. \$\endgroup\$ – ymbirtt Feb 19 '14 at 23:19
  • 2
    \$\begingroup\$ If I could propose a variant that is more feasible, you could do a challenge like "Write a program in your language of choice that draws ASCII art of a cow saying something (does not have to be identical or even similar to the cowsay art). The entire drawing must itself be valid source code that does something other than no-op. Post results of both programs." That gives people more leeway to work around the specific restrictions of their compiler. \$\endgroup\$ – Jonathan Van Matre Feb 21 '14 at 23:22
  • \$\begingroup\$ Ok, I found a language that falls within the middle ground: whitespace. Anyway, this question has a too narrow scope to develop an interesting challenge. \$\endgroup\$ – Victor Stafusa Feb 22 '14 at 18:31
  • \$\begingroup\$ @JonathanVanMatre That would be a subjective validity criterion, and would probably be closed as too broad. \$\endgroup\$ – wastl Jul 2 '18 at 13:55
-3
\$\begingroup\$

99 Bottles of Errors

While there are already many versions of "print 99 Bottles of Beer," I thought another one wouldn't hurt.


The challenge is fairly simple: print the lyrics to 99 bottles of Beer to STDERR. I don't care how you do it, so long as the entire lyrics show up. An entire program is required, so the following Java program would be invalid (even if it did do the correct thing):

System.out.println("99 Bottles of Beer on the Wall, take one down and pass it around...");

The scoring:

  • This challenge is , so shortest code by byte count wins.
  • If necessary, assume UTF-8 is the character encoding used.

The rules

  • All the code must be in one file.
  • Any language is allowed.
  • Reading input, whether it is from STDIN, a file, or the web, is not allowed.
||||||
\$\endgroup\$
  • 5
    \$\begingroup\$ This is trivial in some languages (Java), where it reduces to a simple kolmogorov challenge, and impossible in others (those that have no distinct STDERR) \$\endgroup\$ – John Dvorak Mar 27 '14 at 7:42
-3
\$\begingroup\$

Create an Identicon Generator

The challenge is to create an identicon generator. The identicons must be randomly generated, so we get a new identicon for each key the program receives. You can input a key using std-in or you can use your language's random number generator for the key.

In order to make your identicon look reasonably nice, it must generate a picture, then rotate that picture around the bottom right corner, the way this mockup shows:

enter image description here

The output must be to a PNG file. Shortest code wins.

||||||
\$\endgroup\$
  • 5
    \$\begingroup\$ Far too broad. As this stands I can create a 1-pixel image whose colour is just the key. I don't think this question will be ready to go until you've found a way to prevent me from making the images differ only in their palette (and to pre-empt, I think that adding a rule "Images may not differ only in their palette" isn't a real fix). \$\endgroup\$ – Peter Taylor Mar 28 '14 at 14:50
  • 5
    \$\begingroup\$ If you just ask for "random" images, you'll get images that are either hardly random at all (a solitary pixel in a random location), or completely random (noise). To get something "reasonably nice", you'll have to provide very clear instructions on how to produce these images. I suggest you try creating a few of these yourself, and find a minimal set of rules that produces results that look OK. Include requirements on dimensions (100x100px?), selection of colours (at least 2, not too similar), and drawing method (e.g., "five triangles with random vertices and a minimum area of 20 px²"). \$\endgroup\$ – r3mainer Mar 28 '14 at 15:25
  • 1
    \$\begingroup\$ How important is the PNG file output? This will be a challenge in itself for many languages. Would you accept an uncompressed non-interlaced format like PPM? \$\endgroup\$ – trichoplax Apr 16 '14 at 9:45
-3
\$\begingroup\$

Underhand Bejewled

Help me to write a game of bejewled, which cannot be lost!

Bejewled game rules

If you ever played bejewled, you can skip this, but for those who did not see it ever:

  • Playing field of 8*8 grid is filled in with gems of 7 different types randomly
  • By swapping two adjective stones, your goal is to create a line of at least three same type of stones in the either vertical or horizontal line
  • If did so, the gems will dissappear, points are added (say 20 points for a matching) and new gems are provided randomly from the top
  • image related:

enter image description here

Your challenge

Provide me a game which cannot be lost. In other words, the gems falling from the top are not random at all, but are falling in order that there is always at least one possibility to match three gems

But, from looking at the code at level of newbie programmer, it should look like that game acts as if it was random

Output

Playable game. As long as it is the grid of 8*8 filled in with 7 different types of "gems" the game is ok. It does not to have killer graphics, neither it does not need to be playable by mouse. (But in that case please make sure you show which "gem" is hovered and then selected)

Winning criteria

This is popularity contest. So highest rated game wins

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ I think this is too big a task to work well for an underhanded contest. The programs will be way too large for anyone to actually read the source and try to find what's underhanded about it. \$\endgroup\$ – Martin Ender Nov 11 '14 at 8:32
  • \$\begingroup\$ Thats what I was also afraid of. I will either take it as lesson to progress on my programming skill, or abandon the idea completly \$\endgroup\$ – Pavel Janicek Nov 11 '14 at 8:38
-3
\$\begingroup\$

Shortest Program that May or May not Terminate:

Write a program such that whether or not it terminates depends on the answer to an unsolved question in Computer Science or Mathematics. For example, your program might test the Goldbach conjecture for every N and quit if a counterexample is found, or hunt for odd perfect numbers. Please include an explanation of why your program may or may not terminate!

Note: assume infinite memory and stack size, because otherwise they all terminate. Your program must be self contained, take no input, and only use standard libraries. This is Codegolf, so shortest code wins!

||||||
\$\endgroup\$
  • \$\begingroup\$ What about "unsolvable" problems, e.g. halting problem? Can I take another code as input and terminate if that terminates? Because that other program may or may not terminate, and there's no way to tell. \$\endgroup\$ – Martin Ender Nov 20 '14 at 18:03
  • \$\begingroup\$ The intention was that the program isn't allowed to take input. I'll be more specific. \$\endgroup\$ – QuadmasterXLII Nov 20 '14 at 18:50
  • 2
    \$\begingroup\$ Does this differ from this previous question in the sandbox? \$\endgroup\$ – trichoplax Nov 20 '14 at 19:34
  • \$\begingroup\$ (even if not the comments explaining why that one wouldn't work as a question may help Taylor this one) \$\endgroup\$ – trichoplax Nov 20 '14 at 19:35
  • \$\begingroup\$ The intent of this doesn't differ significantly from the question you linked, I searched posted questions but forgot to search the sandbox. \$\endgroup\$ – QuadmasterXLII Nov 20 '14 at 19:41
  • \$\begingroup\$ Infinite memory isn't required. \$\endgroup\$ – feersum Nov 20 '14 at 21:46
-3
\$\begingroup\$

This and this gave me an idea, but I'm not quite sure if this can be done at all, or if it is trivial. If it is, maybe point out how it could be changed to be interesting.

Anti golfing - Write the longest program not repeating any character

Well, it's just what the title says. Finally you're allowed to use as much bytes as possible.

Conditions

  • The code of the program or function should not use any character that is used in the code before.

  • Your program should print some sort of result to stdout, or into a file or return a value. You're not allowed to output or return the empty string or only a newline.

  • Other than that your program might do anything. Read input, print lots of output, or what you can think of, but you have to explain what it does, of course.

  • Only characters in the ASCII range [32 .. 126] and newlines are allowed, which limits the maximal code length to 96 bytes.

  • Variable names are only allowed to consist of a single character

  • String literals or the like are forbidden. They could be used to hold the unused characters (though they would need two " in most languages anyway).

  • The same rule applies for similar literal constructs like blocks or what else is there in some languages.

  • Even if the length of a string literal would be used to generate a number, it is forbidden.

  • Variables can not just be declared and never be used. They have to be reflected in the output somehow.

  • If you've read and understood the above rules and still found a loophole and used it, you should go and stand in the corner for a while, thinking about what you've done.

So all in all, only use characters for actual code that does something generating the output, might it be calculating a value or formatting. And don't put unused characters somewhere in your code as a literal. Numbers are an exception, but I guess it's no problem to use them anyway.

I guess you should have a pretty good idea of what would be considered cheating here.

Example in awk

BEGIN{gsub(a,9);print $j-13+d^c/4*5678%20}

It prints 15.5, score is 42.

It replaces the empty string a with 9 in $0, which is the empty string in the beginning. So $0 becomes 9.

Then it prints the result of 9-13+1/4*5678%20.

($j is $0 (==9), because j is not defined

d^c ist 1, because c and d are not defined)

Please don't invent languages for this ;)

The longest code in bytes wins.

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Are you sure you want to allow ASCII 127? That's the unprintable<DEL> character. The main problem with this challenge is "only use characters for actual code that does something". This is essentially unenforceable, because there may be arbitrarily complicated no-ops in the code. It's also why most code-bowling challenges fail to be popular/interesting. \$\endgroup\$ – Martin Ender Sep 14 '15 at 7:32
  • \$\begingroup\$ Well, I thought about making it a "most votes win" challenge, but I guess that would be unfair for less known users. I don't know what could be done with what you are pointing out. \$\endgroup\$ – Cabbie407 Sep 14 '15 at 7:51
  • 2
    \$\begingroup\$ I don't think this is a good candidate for a popularity contest. Popularity contests shouldn't be used as a cop out if the actual spec is a bit vague. They work best for challenges where the actual scoring criterion can be well specified but is more easily judged by humans than machines (e.g. "visually approximate a given image with these constraints..."). \$\endgroup\$ – Martin Ender Sep 14 '15 at 7:54
  • \$\begingroup\$ Yeah, it's hard to formulate the rules for this. But I think it's not always about finding a winner anyway. Thought this might be fun. Resolved the character 127 situation btw.. \$\endgroup\$ – Cabbie407 Sep 14 '15 at 7:57
  • \$\begingroup\$ How could I change that rule? I'm thinking about "only use code that contributes to the generation of the output" \$\endgroup\$ – Cabbie407 Sep 14 '15 at 8:02
  • 2
    \$\begingroup\$ How do you define "contribute"? E.g. this GolfScript program prints the length of the block in {...} which is a convenient way to stuff all characters except in '"# in there. Do all those random characters actually contribute? In Slashes everything which isn't an unescaped slash is printed to STDOUT, so as long as I put \/ together, I can put any characters I want there and they'll all contribute. \$\endgroup\$ – Martin Ender Sep 14 '15 at 8:07
  • \$\begingroup\$ Hmm, I thought this would be covered by forbidding string literals.. might think about extending that rule to blocks. Well, I'm not that fluent at esolangs. \$\endgroup\$ – Cabbie407 Sep 14 '15 at 8:10
  • \$\begingroup\$ It's trivial to use all possible 96 bytes. Trust me. If you really want to see the program I'm thinking of, I suppose I could write it, but I'm pretty sure it can be done. \$\endgroup\$ – mbomb007 Sep 16 '15 at 18:34
  • \$\begingroup\$ Yeah, I guess you're right. i have no idea how it would be done, but alright. \$\endgroup\$ – Cabbie407 Sep 16 '15 at 20:10
  • \$\begingroup\$ Not to mention this is pretty much a duplicate of codegolf.stackexchange.com/questions/30159/… \$\endgroup\$ – pppery Aug 6 '17 at 12:52
-3
\$\begingroup\$

Linear Time Sorting

It was another slow day at Initech Inc. when a feature request came in:

New Feature: Ability to sort by cash value in the transaction form. But make it a fast one!

Well it looks simple.. but what do the requester mean by fast one? Let's call Jim, from sales he probably knows what's going on.

Jim: Well you know , our Business Inc. contact is very passionate about 

programming and computer science! In fact he had this idea that we should 

do sorting in how that was called.. linear time?


You: Well you know that's impossible?

Jim: But it was already approved by their cto and all! You need to do something

You and Jim came up with a plan.. nobody will notice if that big of a list isn't sorted enough, right?

Your task

Your task is to write a linear time sorting program. It will be scored on accuracy of the sort as compared to list sorted by regular sorting algorithm but it must work on O(N) time in the worst case, where N is length of the input.

Input will be in the form of list of string-double tuples, e.g:

[("aaaa",2.0) , ("aaba",1.0)]

The program should sort on the number value of the tuple, i.e. in the above case the order should be reversed. There may be multiple inputs with the same double values, but no string value is repeated. In the event that two inputs have the same integer value the perfect solution is to keep the order as it is. The double value may be any floating-point value that fits in 8 byte double precision variable. NaNs should be placed at the end of the list.

The score is calculated as number of "bubble sort operations" (switch an element with the next/previous element) needed to achieve perfect output from the output of your algorithm.

Sandbox Worries

Well I don't know how clear my explanation of challenge was and if it is interesting to the PPCG crowd.

Obviously there is a need for testing program and test cases.

||||||
\$\endgroup\$
  • \$\begingroup\$ How big will the test cases be? If you pick a fixed size, the response will be "n passes of bubble sort where n is the size of the largest test". Bam, linear with perfect score. \$\endgroup\$ – John Dvorak Apr 11 '16 at 10:12
  • \$\begingroup\$ @JanDvorak I rephrased the scoring sentence to more reflect what I meant. In that case the score wouldn't be perfect as after just n switches the list wouldn't be the most ordered. EDIT: I think I understood it now. Well I think you can somehow exclude answers like that with some caveats in the rules, like "Your algorithm cannot make any assumtions about length of the input" \$\endgroup\$ – Lause Apr 11 '16 at 10:17
  • \$\begingroup\$ I don't make any assumptions. It sorts every array up until the largest test case correctly and all other arrays partially. \$\endgroup\$ – John Dvorak Apr 11 '16 at 10:28
  • 1
    \$\begingroup\$ An algorithm that fares better than n-pass bubble sort is to do a level-n mergesort. If the length exceeds 2^n, sort each [k::len/2^n] subarray separately. \$\endgroup\$ – John Dvorak Apr 11 '16 at 10:32
  • \$\begingroup\$ But then you're making assumptions based on the size of the test cases - if somehow the test cases were changed (but still fitting the rules) to test cases which are much longer (for example you prepared for max 10 element list and you get 100000 element list) your program isn't linear. \$\endgroup\$ – Lause Apr 11 '16 at 10:41
  • \$\begingroup\$ The problem with a spec is that it cannot change once you've posted the challenge, and you can't define "making assumptions based on the size of the test cases". You can't even ban all magic numbers - I can simply use functions merge1 .. merge20 \$\endgroup\$ – John Dvorak Apr 11 '16 at 10:47
  • \$\begingroup\$ It isn't the spec - the way the test cases used to grade the result are constructed is described but do I have to post the test cases (but those used to score) themselves? \$\endgroup\$ – Lause Apr 11 '16 at 10:50
  • \$\begingroup\$ You need to define the test cases, and you can't change them based on the answers (if only because updating the score of every answer would be a nuisance). Maybe you could ask for asymptotic behavior, but that can be surprisingly hard to measure. \$\endgroup\$ – John Dvorak Apr 11 '16 at 10:53
  • \$\begingroup\$ Hidden test cases are a problem as well, because then we can't test the submissions after you're gone. \$\endgroup\$ – John Dvorak Apr 11 '16 at 10:55
  • \$\begingroup\$ The idea was to pregenerate some test cases (undisclosed) and some test cases that are disclosed (for testing purposes during the coding) and then do a cutoff time for the challenge where all the solutions are tested against the undisclosed challenges. Also obviously after the cutoff time the test cases would be disclosed. \$\endgroup\$ – Lause Apr 11 '16 at 10:56
  • \$\begingroup\$ 1. Most real-life data types can be sorted in linear time, so the premise of the question seems badly flawed. 2. "Input will be in the form of list of string-double tuples ... There may be multiple inputs with the same integer values" Huh? Where do the integer values come from? 3. "The double value may be any floating-point value" Where do NaNs sort? \$\endgroup\$ – Peter Taylor Apr 11 '16 at 16:00
  • \$\begingroup\$ 1. The idea is that the data may be the worst case for any algorithm that can achieve linear sorting time 2. It was a typo 3. At the end - I will put it into the question \$\endgroup\$ – Lause Apr 11 '16 at 18:36
  • \$\begingroup\$ Why does the input being worst case make any difference? The solution will still be perfect, so you'll need a tie-breaker to separate every single answer. \$\endgroup\$ – Peter Taylor Apr 11 '16 at 21:27
-3
\$\begingroup\$

Alphabetization 101 (popularity contest)

Your task is to use all 52 letters of both the uppercase and lowercase alphabet, ONCE and ONCE only, and make a program.

You are free to use any other ASCII character more than once, or use a letter of the alphabet more than once if it's required for the language to function.

Meta:

  • Not sure if this has been done before.
  • Any questions regarding the task?
||||||
\$\endgroup\$
  • \$\begingroup\$ Not really meta: Is there any place I can go to (like a chat or something) to post a question about BF? StackOverflow probably isn't suitable. \$\endgroup\$ – clismique Apr 17 '16 at 6:48
  • 1
    \$\begingroup\$ Come to our chatroom! :) \$\endgroup\$ – Leaky Nun Apr 17 '16 at 6:50
  • 3
    \$\begingroup\$ I would vote to close this as too broad. It's not a particularly interesting restriction per se, and it certainly doesn't make a good question without some restriction on the task to be performed. \$\endgroup\$ – Peter Taylor Apr 17 '16 at 14:07
  • \$\begingroup\$ @PeterTaylor That's why it's a popularity contest, though - it lets the people decide whether the program made is good or not. What WOULD be a good restriction on the task? \$\endgroup\$ – clismique Apr 18 '16 at 1:40
  • \$\begingroup\$ The popularity-contest tag is not an excuse for a broad challenge. "Write a program that does anything..." is pretty much the definition of "too broad", regardless of any source code restriction put on the program. So at least you should choose a specific task. Could be anything really, but if it relates to the restriction it might be more interesting (e.g. a pangram checker). Even so, I agree with Peter that the restriction isn't particularly interesting. There are tons of languages where it's trivial to avoid unwanted letters and then include the remaining ones in a string or comment. \$\endgroup\$ – Martin Ender Apr 21 '16 at 7:04
-3
\$\begingroup\$

Why did I come to Sandbox?

I have a very specific challenge, and I wanted to see if it was too specific.

The challenge is to output "Valdosta ACM" using the shortest number of characters with the BrainF**k programming language.

I've noticed it isn't the norm to specify a programming language on this domain, so I've come here to get feedback on whether or not this is acceptable.


Introduction

As a challenge to the members of my local Association for Computing Machinery(ACM) chapter, I asked them to produce the shortest Brainf**k code that would output "Valdosta ACM".

This was a very fun challenge for all of our members, and we got very competitive! I was impressed with the solutions turned in, but I wondered if it was possible to beat our best solution. Surely it's possible, but who could do it?

Challenge

Output the string "Valdosta ACM".

Stipulations:

  • Use only the Brainf**k programming language (you can test your code here)

  • No input can be accepted by your program

  • Your program must halt

  • The space in the string must be ASCII character #032.

These are the ASCII values of each character, as they appear in the string, for convenience:

 086 097 108 100 111 115 116 097 032 065 067 077

The winner is determined by the shortest code, by character count.

Example Input and Output

Input:

NO input is allowed

Output:

Valdosta ACM

||||||
\$\endgroup\$
  • \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! Thanks for using the Sandbox. :) A few things to note: 1.) Generally we discourage language-specific challenges, 2.) typically code golf is scored by bytes rather than characters, and 3.) printing a fixed string like this would be insufficiently different from the Hello, World! challenge to avoid it being closed as a duplicate. \$\endgroup\$ – Alex A. Apr 25 '16 at 3:38
  • \$\begingroup\$ Thanks Alex! Since I want to compare the results of my local competition with the results of the challenge here, is there anything I could change about the challenge to make it acceptable? I don't see a way to do this, but I was so excited about seeing if anyone here could do better than our coders. And thanks for the warm welcome! :) \$\endgroup\$ – Matt C Apr 25 '16 at 3:48
  • \$\begingroup\$ You could look at Brainf**k solutions to other challenges (like this one), and see if the techniques used there can help you improve your solution. \$\endgroup\$ – ugoren Apr 25 '16 at 7:09
  • \$\begingroup\$ We also have a tips question that may be of interest. \$\endgroup\$ – trichoplax Apr 26 '16 at 6:30
  • 2
    \$\begingroup\$ Although this particular challenge is probably too similar to "Hello, World!" (as Alex pointed out), if you had a different challenge that you wanted to see solutions for in a specific language, you can still post it but just allow all languages to compete. If you don't see solutions in your specific language you can post a bounty for that language to encourage it. \$\endgroup\$ – trichoplax Apr 26 '16 at 6:33
-3
\$\begingroup\$

Cops and robbers : Programmers/Hackers

  • This challenge is quite different from my previous challenges. This challenge is an endless competition between robbers and cops, which are respectively hackers and programmers. One of them will ever win!!!
  • This will evolve to code de/obfuscating when it gets to the higher stages: a skillful programmer who is struggling to save his program from a sourcecode-mangling attempted by a cunning "robber" who tries to impose his existence by patching his name instead of the name of the "programmer" in the output console without changing anything else in the code. The story begins this way:

  • Programmer is at the point of executing his recently made C code, so he included this trivial line to show off:

C (1)

    printf("[Programmer's username]")

After executing this program programmer saw this on the screen:

[Robber's username]

which indicates the presence of some evil code at the compiler level that compromises his code, which follows:

Matlab (2)/parser

      a=findstr(code,'printf(''[Programmer's username]'')'); if a code(a:20)='printf(''[Robber's username]'')';end

The programmer cannot modify the counter-program in the compiler, so he must rather change the program content to escape the twiddling:

PHP (3)

      $a='[programmer's username]';echo $a;

The score is now 3, which is the number of steps from the beginning. The current user would win only if the hacker did not figure out something like:

PHP/Regex(pcre flavor) (4)

      $code=ereg_replace("(\$\w)\='programmer';(.*?);echo\s\1","\1\='robber';\2;echo\s\1",$code)

Since the solution above does not satisfy the rules (see the bottom of this question), the score stays unchanged, and the programmer can make a counter example, and take out the score from last submitter with a penalty on his score equivalent of how much he earned in the earlier level, where the counter example can be something as:

PHP (4)

      $a='programmer';$b=$a;$a='unrelated';echo $a;

Or he can adjust his program in higher scale to escape all the regex-trapping in a superior range, So the cycle goes on until no post can be added and the last submitter before the end of June is declared a potential winner meanwhile.

The hacker can also fix his regex and regain his score, so the recent scoring will be abrogated from programmer.

Perl/dynamic-regex (4)

local @a=('');

sub check{
  if (grep {$_ eq @_[1]} @a)  
   {push @a,@_[0]; } 
  elsif  (grep {$_ eq @_[0]} @a)   {
    my @del_indexes = grep { @a[$_] eq @_[0] } 0..$#a;
    foreach $item (@del_indexes) {
     splice (@a,$item,1);
    }
  }   
return 1;
}

sub actor{
if (grep {$_ eq @_[0]} @a)
 {return "print robber";}
else
 {return "print ".@_[0];}
}


sub initiate{
push(@a,@_[0]);
return 1;
}

$code =~ s/(((\w+)\="programmer"(??{initiate($3);}))|(print\s(\w+))|((\w+)\=(\w+)(?{check(($7),($8));})(?1)))/print($2);actor($5)/pegmx;

As you can see this Perl program prints b in the first case because the variable b is compromised after the first assignment, but in the second case the regex modifies the output because d receives the target-string transitively. Let's just stop here and not mess the fun (of course, if there will be some).

Scoring and rules

How is the score counted ?

  • Any hacker/programmer is scored for his code as the actual level L the game is on.
  • A partial dynamic regex within the core of the program is scored L + (2^L)/log(length of program + length of characters which do not belong to the regex)), where the log is base 2. For the second example of level (4) the length of the compacted program is 480, and the length of regex is 136, so the score is 4+2^4/log2(480+480-136) ~= 4+16/9.6
  • A fully functional regex as in the first example level (4) is scored L + (2^L)/log(length of regex), where the log is base 2, in that case S = 4 + 2^4 / log(91) ~= 4+16/6.5
  • Scores are added progressively to submitters, and when a level is surpassed with no regex, it is still open for scores, while the actual winner remains unchanged.
  • A penalty on a certain-leveled score when the regex/parser is revealed out of rules and the game is regressed to this stage until the issue is fixed, rules are cited below:

Rules:

  • The main rule: the hacker-program must compromise an output to the console, which is the username of the programmer. Any other behavior is unaccepted simply because a string variable of [programmer's username] can be used in other order rather than printing, a counter-example is easy, converting the string to integer then use it for arithmetic calculations that harms the main program once intentionally modified.
  • Also one of the following factors declared by any counter-example bans the targeted flawed regex/parser as non rule-complying:
    • The regex/parser prints anything other than a chosen string preferably set as the username of the robber.
    • The regex/parser generates a program which does not compile.
    • The regex/parser does not print anything, or compromises a segment of code that is needed for tasks other than printing .
  • The variable which stores the program is named code by default, also you may assume that is one-liner, and any non-significant spaces are omitted, and that it is fully working by default.
  • The regex/parser deals with one variant of one code proportion in a comprehensive way, i.e. if a print function is used, that encompasses all printing functions in all languages puts,disp,..etc. Also, code separators can be unified to one characterL either , or ; or a significant space needlessly of enumerating all keywords/syntaxes, this is not a contest about a working code in a specific programming language.
  • To prevent endless program/regex loops let's just not making a jokey sequence as a='programmer';print a / /(\w)\='programmer';print\s\1/ / a='programmer';b=a;print b / /(\w)\='programmer';(\w)\=\1;print\s\2/ because the first person who makes a regex/parser which palliates to a same replicated idea will take out all attributed scores to this idea from their owners, so any anaphoric sequences like this in addition that they are set to same level, they are unneeded.
  • Any language that uses pointers/addresses/classes like C++ are welcome, as long as they help to evade the hacker.
||||||
\$\endgroup\$
  • 3
    \$\begingroup\$ Please, for the love of god, spell things correctly. In the first bit alone I spotted a ton of spelling mistakes without even looking for them. Also, that whole first list is... basically impossible to understand, at least for me. Maybe use full sentences? \$\endgroup\$ – Fund Monica's Lawsuit May 10 '16 at 21:29
  • 1
    \$\begingroup\$ Have you seen our cops-and-robbers challenges? It sounds like that is what you are trying to do here. That said, there are a couple of problems with the spec: Defining what parts of the language counts as a "partial regex" or "full regex" is really tough, especially when we get into esoteric languages. \$\endgroup\$ – Nathan Merrill May 10 '16 at 21:36
  • 1
    \$\begingroup\$ Could you add a short summary to the post? I don't understand what the actual task here is. Is this a cops-and-robbers or answer-chaining challenge, or something entirely different? \$\endgroup\$ – Zgarb May 10 '16 at 21:36
  • \$\begingroup\$ i will see what cops and robbers is \$\endgroup\$ – Abr001am May 10 '16 at 21:39
  • \$\begingroup\$ @NathanMerrill this is not a code golf so i dont see the point of introducing esolangs here \$\endgroup\$ – Abr001am May 10 '16 at 22:28
  • 1
    \$\begingroup\$ @Agawa001 Esoteric languages are still useful outside of golfing. You can use them to make it tough for regexes to match. \$\endgroup\$ – Nathan Merrill May 10 '16 at 23:06
  • 3
    \$\begingroup\$ The introduction is very long and after reading it I have no idea what the task is. I would have to vote to close this as "Unclear what you're asking" in its current state. \$\endgroup\$ – Peter Taylor May 11 '16 at 7:45
  • \$\begingroup\$ So what's the core mechanic? Is this an answer-chaining question where answers must alternate programmer and hacker? But if the programmer can change language at will, how can the hacker hope to win? \$\endgroup\$ – Peter Taylor May 12 '16 at 12:06
  • \$\begingroup\$ @PeterTaylor yes it is answer chaining but the last submitter can post two consecutive answers and be the robber and cop themselves, the programmer change his code, hacker changes his regex taken consideration of all last regex/parsers. \$\endgroup\$ – Abr001am May 12 '16 at 16:13
  • 1
    \$\begingroup\$ I have no idea what this challenge is supposed to be. The very little explanation of the concept is muddled by spelling and grammar issues. Please, learn English spelling and grammar before trying to write a challenge. \$\endgroup\$ – Mego May 13 '16 at 5:18
  • \$\begingroup\$ @PeterTaylor refer at the 4th rule, procedures which accomplishes a specific task in different languages are dealt as one thing, this is not a challenge about checking language-syntaxes, when a programmer changes language, consider all previous regex/parsers changed to trap same functionnalities of previous code on the new language. \$\endgroup\$ – Abr001am May 28 '16 at 11:37
-3
\$\begingroup\$

Challenge

Write a program that takes an numerical input n and outputs the nth number that is not a perfect square.

Rules

This is , so least bytes wins.

||||||
\$\endgroup\$
  • 3
    \$\begingroup\$ What's the maximum expected input? Does it expect 0? How do we handle 0? Is there a requirement on the efficiency for large inputs? Also give some example inputs and outputs. \$\endgroup\$ – Patrick Roberts Jun 17 '16 at 20:19
  • \$\begingroup\$ Here's some test cases I just generated: 1->2,2->3,3->5,4->6,5->7,6->8,7->10,8->11,9->12,10->13,11->14,12->15,13->17,14->18,15->19,16->20,17->21,18->22,19->23,20->24,21->26,22->27,23->28,24->29,25->30,26->31,27->32,28->33,29->34,30->35,31->37,32->38,33->39,34->40,35->41,36->42,37->43,38->44,39->45,40->46,41->47,42->48,43->50,44->51,45->52,46->53,47->54,48->55,49->56,50->57,51->58,52->59,53->60,54->61,55->62,56->63,57->65,58->66,59->67,60->68,61->69,62->70,63->71,64->72,65->73,66->74,67->75,68->76,69->77,70->78,71->79,72->80 Is this the function you expect? \$\endgroup\$ – Patrick Roberts Jun 17 '16 at 20:41
  • \$\begingroup\$ Yes, yes it is. \$\endgroup\$ – weatherman115 Jun 17 '16 at 20:42
  • \$\begingroup\$ Can you address my other questions please? Namely, the largest expected input and how to handle input of 0. \$\endgroup\$ – Patrick Roberts Jun 17 '16 at 20:43
-3
\$\begingroup\$

Generate all variations of a string with every combination of upper and lower case for each vowel but leaving consonants and order of letters unchanged.

This is a simplified analog of a problem I've thought about a few times over the years based around variant spellings in different spoken languages.

Input is a text string. Output is an array of all variations of the text string.

A "variation" means the same letters in the same order but for each vowel letter in the string we generate a version of that string with the vowel in uppercase and the vowel in lowercase.

No variation should be included more than once. No legal variation may be omitted.

Example

Input

codegolf

Output

  • codegolf
  • codegOlf
  • codEgolf
  • codEgOlf
  • cOdegolf
  • cOdegOlf
  • cOdEgolf
  • cOdEgOlf

The winner shall be the most elegant as voted by the community.

"Elegant" includes that the algorithm should be optimal in terms of Big O notation, should be concise, should be idiomatic making good use of available features of the implementation language.

Length of code characters or bytes is not relevant.

Programming language is open.

||||||
\$\endgroup\$
  • \$\begingroup\$ "most elegant as voted by the community." I doubt many answers to such a challenge will be deemed elegant. \$\endgroup\$ – Fatalize Jun 23 '16 at 13:01
  • \$\begingroup\$ Really? Anything to suggest instead? Just "best" is usually no good for Stack Exchange... \$\endgroup\$ – hippietrail Jun 23 '16 at 13:22
  • 3
    \$\begingroup\$ Code golf version of this challenge: codegolf.stackexchange.com/q/80995/8478. That said, I don't think "most elegant" makes a good popularity contest and is very likely to be downvoted and closed almost instantly. If you're looking for elegant solutions, this might not be the right community in the first place though. You could write your own solution and post it on Code Revew to ask for improvements. We generally require objective winning criteria for our challenges, and popularity contests are in a weird place where you need to come up with something really good for it to be accepted. \$\endgroup\$ – Martin Ender Jun 23 '16 at 13:30
  • \$\begingroup\$ Hmm well OK whatever. \$\endgroup\$ – hippietrail Jun 24 '16 at 11:55
-3
\$\begingroup\$

Make a Fork Bomb

under construction, please constructively (no pun intended) criticize

Create a program which forks itself at twice and exits, or forks itself once and idles. Whether it continues forever or exits is your choice. Forks can be OS forks or simply a command to relaunch the program.

Rules

  • No spoon bombs allowed, please.
  • Don't make any assumptions about the location of the program.

Bash, 10 chars

./$0|./$0&

Acts as a standard punching bag for other solutions.


Microsoft Windows Batch file, 5 chars

 %0|%0

Anybody who beats this one gets a million internet points. (and maybe a bounty)

||||||
\$\endgroup\$
  • 4
    \$\begingroup\$ I assume that the downvote is because someone considers that this violates our policy on malicious code. I think it's borderline, but if it's on the right side of the border then the question has other issues. 1. Why fork itself at least twice? Surely forking once is enough for a fork bomb? 2. Define "OS forks" in a way which doesn't rely on the OS being POSIX. Or, better, remove that requirement: it seems to me to limit the languages permitted more than necessary for no benefit. 3. What's a spoon bomb? Google is not being helpful. \$\endgroup\$ – Peter Taylor Jul 14 '16 at 13:49
  • \$\begingroup\$ @PeterTaylor 1. the chat said it was fine 2. If you only fork once and exit, you have a constant amount of processes 3. Good idea. Any tips for windows forks? 4. it's a joke \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jul 14 '16 at 16:38
  • \$\begingroup\$ I'm downvoting because I think it's close enough to malicious. A fork bomb can hang a computer. \$\endgroup\$ – mbomb007 Jul 22 '16 at 19:27
-3
\$\begingroup\$

2 Pass Hello world

There you go, your first "Hello world" is displayed on your terminal. You think about your next step into becoming a wizard.

You've heard about this fancy new programming language, but you're not sure you understand it perfectly. So you want to go over a new "Hello world" tutorial again.

How boring!

Instead you have a good idea, using your knowledge of the first programming language to create a "Hello world" program in the second programming language.

Exemple:

console.log('print "Hello world"');

Evaluated in javascript output:

print "Hello world"

Which, evaluated in python 2.X output:

"Hello world"

Nice, but, can it be shorter?

||||||
\$\endgroup\$
  • 1
    \$\begingroup\$ We have a tag for multi-language challenges, polyglot. \$\endgroup\$ – Rɪᴋᴇʀ May 4 '16 at 14:06
  • \$\begingroup\$ Pyth: \H (Guess what the second language is) \$\endgroup\$ – Leaky Nun May 4 '16 at 14:08
  • 1
    \$\begingroup\$ Maybe add a scoring mechanism by how many languages it works in? e.g. console.log('print("puts\'Hello, World!\'")') would score len(submission)/num_languages_it_works_in? \$\endgroup\$ – Rɪᴋᴇʀ May 4 '16 at 14:09
  • \$\begingroup\$ Then the submission above would score 0. \$\endgroup\$ – Leaky Nun May 4 '16 at 14:09
  • \$\begingroup\$ (To OP) Maybe you would need to add some more rules \$\endgroup\$ – Leaky Nun May 4 '16 at 14:11
  • \$\begingroup\$ @KennyLau no? 2/2 = 1 \$\endgroup\$ – Rɪᴋᴇʀ May 4 '16 at 14:11
  • 1
    \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ It can be fed into itself for one more pass... \$\endgroup\$ – Leaky Nun May 4 '16 at 14:12
  • \$\begingroup\$ I didn't want to add any recursive mechanism, because the end goal should be to display "Hello world" but a more than 2 language is a great idea. \$\endgroup\$ – nobe4 May 4 '16 at 14:15
  • \$\begingroup\$ I don't see how you will be able to come up with a good scoring system for this. Using two esolangs / two times the same esolang will result in 1/2 bytes answers right away. \$\endgroup\$ – Fatalize May 4 '16 at 14:16
  • \$\begingroup\$ @KennyLau, what rules do you generally add to a incomplete challenge? we thought adding a time/memory limit for the execution, but seems irrelevant... \$\endgroup\$ – nobe4 May 4 '16 at 14:17
  • 3
    \$\begingroup\$ This is really closely related to several other challenges we've had on the site, such as this one and this one. You'll need to be very careful to not make it a duplicate. \$\endgroup\$ – AdmBorkBork May 4 '16 at 14:22
  • 1
    \$\begingroup\$ Also this one, which is practically a duplicate, just with numbers instead of "Hello, world." \$\endgroup\$ – AdmBorkBork May 4 '16 at 14:26
  • \$\begingroup\$ Yeah, I haven't seen all this, I guess I'll start searching for another idea instead ;) \$\endgroup\$ – nobe4 May 4 '16 at 14:29
  • 2
    \$\begingroup\$ Also, welcome to PPCG! (I forgot to mention that earlier). Hope you enjoy yourself here! \$\endgroup\$ – AdmBorkBork May 4 '16 at 14:36
-3
\$\begingroup\$

Return True to Win - Counter

Original credit goes to this site, which you should all check out

Write the shortest javascript code to pass as parameter f to function counter such that it returns true:

function counter(f) {
    var a = f(), b = f();
    return a() == 1 && a() == 2 && a() == 3
        && b() == 1 && b() == 2;
}

I'm considering also making this a series with all the rest of the challenges on the site, where each one gets harder

||||||
\$\endgroup\$
  • 6
    \$\begingroup\$ Given the lack of a terms of use page on the site, the code on that site is copyrighted, with no provisions for reproduction. This is copyright violation. \$\endgroup\$ – Mego Aug 9 '16 at 6:00
  • 2
    \$\begingroup\$ In addition to Mego's note regarding copyright, language-specific challenges are not typically well-received by the community. \$\endgroup\$ – Alex A. Aug 9 '16 at 18:18
-3
\$\begingroup\$

Stump The Golfing Languages

This is the seed of an idea. I'm unclear on the details that might make it work.

I want people to submit answers in the form of a program in a "normal" language (defined how?), such that reproducing its functionality in a golfing language isn't much smaller. That is, I want to find the algorithms that Jelly and Pyth and Matl and such are not optimized for.

I would appreciate suggestions on how to make this work. Maybe cops and robbers? Maybe each entry just contains two programs, and comments are given to help golf the smaller one?

||||||
\$\endgroup\$
  • \$\begingroup\$ The only language that could possibly win is mathematica \$\endgroup\$ – Destructible Lemon Aug 23 '16 at 1:52
  • 2
  • 2
    \$\begingroup\$ It's very easy to come up with boring examples e.g. print this exact trace, reproduce the output of this random number generator, etc. I don't see any way to get interesting answers. \$\endgroup\$ – feersum Aug 23 '16 at 6:31
  • \$\begingroup\$ @feersum I'd probably disqualify errors and crashes and stacktrace outputs and such, and maybe all built-in non-trivial algorithms. Thanks for pointing those out. \$\endgroup\$ – Sparr Aug 24 '16 at 7:26
  • \$\begingroup\$ @DestructibleWatermelon you don't have to beat the golfing language to win. The winning entry will probably still have a shorter Jelly solution than Python (or whatever). \$\endgroup\$ – Sparr Aug 24 '16 at 7:27
  • \$\begingroup\$ I don't know of any golfing languages where creating a simple webserver is possible. All this would be is finding a task that isn't normally required for when doing code-golf \$\endgroup\$ – Blue Aug 24 '16 at 14:16
  • \$\begingroup\$ I'm thinking of restricting it to algorithms and output, not stuff like network and file access. \$\endgroup\$ – Sparr Aug 24 '16 at 22:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .