557
\$\begingroup\$

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page 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, though you can optionally add a title at the top. 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, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3992 Answers 3992

1
13 14
15
16 17
134
3
\$\begingroup\$

Primitive Pythagorean triples

Introduction

A Pythagorean triple is a tuple of three positive integers a, b and c so that a² + b² = c². One example of that is (3, 4, 5).
One subset of those are primitive Pythagorean triples which require a, b and c to also be coprimes, so their only common divisior is 1. One example is (5, 12, 13)

The Challenge

Given three numbers representing a triple, output a truthy value if there is a triple representation of them that form a primitive Pythagorean triple and a falsy value if not.

Test cases

Truthy

Coming Soon

Falsy

Coming soon

tags:

TODO

  • What about zero as input?
  • Test cases
  • Example for the different triple configurations?
  • What about builtins?
  • More descriptive title
\$\endgroup\$
6
  • \$\begingroup\$ Unless I'm bad at maths, can't you check for these two conditions totally separately? Since if gcd(a,b,c) = G then we could instead write (Gx)^2 + (Gy)^2 = (Gz)^2 where x,y,z are a,b,c divided by G. Since that doesn't change the equality, wouldn't you just have to check for it being a triple and that they are all coprimes? It's fine if that's what you want (I also may have misunderstood) but it feels... disconnected? \$\endgroup\$ Jun 15, 2016 at 14:11
  • \$\begingroup\$ @FryAmTheEggman, no need to check them all. If a and b have a common factor, it's also a factor of c. So it's a GCD test and a Pythagorean test. @DenkerAffe, "if there is a triple representation of them that form" would be much easier to understand as "if they are". Zero as input is fine: (0, 1, 1) is a (degenerate) primitive Pythagorean triple. I wouldn't worry about built-ins: GCD has been asked before, and a built-in for "Is this a Pythagorean triple" is rather too specific to exist except as a 30-character Mathematica function. \$\endgroup\$ Jun 15, 2016 at 14:25
  • 1
    \$\begingroup\$ @PeterTaylor You're right, but what I was trying to get at was that the challenge felt like two different tests with an and slapped in the middle. While this isn't exactly a problem (particularly because the primitive triples are actually studied) I was trying to suggest the challenge might be better if it felt more like they were connected. However, I have no idea how to accomplish that... \$\endgroup\$ Jun 15, 2016 at 14:55
  • \$\begingroup\$ Also, here is a test script I wrote, if it helps. It only works on sorted inputs, currently. \$\endgroup\$ Jun 15, 2016 at 14:55
  • \$\begingroup\$ @FryAmTheEggman I definetly see you point. Just read about it and wanted to make a challenge about it ^^. It should be fine, since it not just two random things with an AND between them, but I will think about it. \$\endgroup\$
    – Denker
    Jun 15, 2016 at 17:24
  • \$\begingroup\$ @PeterTaylor I agree the wording is a bit off. Will clarify later. Thanks for your other thoughts as well! \$\endgroup\$
    – Denker
    Jun 15, 2016 at 17:26
3
\$\begingroup\$

Join the dots without crossing the line


Given a collection of distinct points in the unit square, output the points in order. This can be any order such that a closed polygon formed by straight line segments joining each point to the next (and the last back to the first) has no two lines crossing.

Input

  1. There will be between 4 and 255 points.

  2. Each one is represented by an ordered pair (x, y)

  3. The coordinates will have entries in the range [0, 1), that is 0 <= x < 1

  4. Each entry may have up to 8 decimal places, so the range is 0 to 0.99999999.

  5. You may choose to accept integers instead, in which case the range will be 0 to 99999999.

  6. You may take input in any reasonable format. For example:

    • (0.1, 0.2), (0.3, 0.4), (0.5, 0.7)
    • 10000000 20000000 30000000 40000000 50000000 70000000

Output

The output format need not match the input format as long as both are unambiguous.

Impossible cases

The code does not need to work for impossible cases, such as all points being colinear. Neither does it need to report such cases - it can simply not work. Behaviour is undefined.

Random algorithms

Your code must be deterministic. That is, it must always give the same output for the same input. For this purpose, the same points in a different order will be counted as distinct inputs and need not have the same output.

You may use pseudo random number generators provided the output is still consistent. If this requires setting a seed, that seed must be zero.

Time limit

Your code does not have to be particularly efficient, but it must finish for the 255 point test case in under 5 minutes.

The requirement for the code to be deterministic is so that this time limit can be checked with a single run. If your random number generator of choice cannot give consistent behaviour by default, then you will need to seed it with zero. If a random number generator does not allow for seeding and does not give consistent behaviour then you may not use that generator.

Test cases

[ TO BE ADDED ]

Output verification snippet

[ TO BE ADDED ]

Scoring

This is code golf. Shortest code in bytes wins.


Note that this is not a Traveling Salesman Problem. There is no requirement for the tour to be short, only for it to be non-intersecting.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It would be good to be explicit about whether non-deterministic solutions are accepted, and if so then what that means for the time limit. \$\endgroup\$ Jun 30, 2016 at 9:47
  • 1
    \$\begingroup\$ I think that it would be reasonable to say that RNGs which seed automatically and can't be reseeded with value 0 may not be used. This would mean that e.g. CJam answers have to be deterministic, but there's a perfectly good deterministic approach anyway. (The obvious approach IMO is to find the convex hull, then remove those points and recurse). \$\endgroup\$ Jul 1, 2016 at 21:04
3
\$\begingroup\$

The Fast and The Fourier

Implement the Discrete Fourier Transform (DFT) for a sequence of any length using a Fast Fourier Transform algorithm (FFT). This may implemented as either a function or a program and the sequence can be given as either an argument or using standard input. A DFT has time complexity of O(n2) whereas a FFT has time complexity of O(n log n).

The algorithm will compute a result based on standard DFT in the forward direction. The input sequence has length n and consists of the complex values {x0, x1, ..., xn-1}. The output sequence will have the same length and consists of {y0, y1, ..., yn-1} is defined by the relation below.

DFT

Bluestein's algorithm

One algorithm that meets these requirements Bluestein's algorithm. It is a special case of the Chirp-Z transform and is able to compute the FFT for a sequence of any length n by transforming it in order to solve it as a cyclic convolution which can be solved with a time complexity of O(n log n).

Keep in mind that it is not required that you only use this algorithm in your implementation. If you know a better way, feel free to use it.

First, an identity is used to rewrite the initial DFT in a form where a convolution can easily be recognized.

Chirp transform

You can obtain two sequences from this new form

Chirp sequences

which allow you to write the DFT as a convolution of two sequences.

Chirp convolve

Sample

Get the input
    x = [1, 2, 3, 4, 5]

Get the length of the input
    n = 5

Compute the 'a' sequence
    a = [1, 1.618 - 1.176j, -2.427 - 1.763j, 3.236 + 2.351j, -4.045 + 2.939j]

Compute the 'b' sequence
    b = [1, 0.809 + 0.588j, -0.809 + 0.588j, 0.809 - 0.588j, -0.809 - 0.588j]

Compute the convolution of 'a' and 'b' (using summation)
    y[0] = (a[0]*b[0] + a[1]*b[1] + a[2]*b[2] + a[3]*b[3] + a[4]*b[4]) / b[0]
         = 15 / 1 = 15

    y[1] = (a[1]*b[0] + a[0]*b[1] + a[2]*b[1] + a[3]*b[2] + a[4]*b[3]) / b[1]
         = (-4.045 + 1.314j) / (0.809 + 0.588j) = -2.5 + 3.441j

    y[2] = (a[2]*b[0] + a[1]*b[1] + a[3]*b[1] + a[0]*b[2] + a[4]*b[2]) / b[2]
         = (1.545 - 2.127j) / (-0.809 + 0.588j) = -2.5 + 0.813j

    y[3] = (a[3]*b[0] + a[2]*b[1] + a[4]*b[1] + a[1]*b[2] + a[0]*b[3]) / b[3]
         = (-2.5 + 0.813j) / (0.809 - 0.588j) = -2.5 - 0.813j

    y[4] = (a[4]*b[1] + a[3]*b[1] + a[2]*b[2] + a[1]*b[3] + a[0]*b[4]) / b[4]
         = 4.253j / (-0.809 - 0.588j) = -2.5 - 3.441j

The Fourier tranform of x
    y = [15, -2.5 + 3.441j, -2.5 + 0.813j, -2.5 - 0.813j, -2.5 - 3.441j]

Rules

  • This is so the shortest solution wins.
  • Builtins that compute FFT in forward or backward (also known as inverse) directions are not allowed.
  • Builtins that compute the convolution are not allowed. (Most will have not been allowed by the previous rule as they use FFT internally.)
  • Your solution must have time complexity of O(n log n) where n is the length of the input sequence.
  • Floating-point inaccuracies will not be counted against you.

Test Cases

FFT([1, 1, 1, 1]) = [4, 0, 0, 0]
FFT([1, 0, 2, 0, 3, 0, 4, 0]) = [10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j]
FFT([1, 2, 3, 4, 5]) = [15, -2.5+3.44j, -2.5+0.81j, -2.5-0.81j, -2.5-3.44j]
FFT([5-3.28571j, -0.816474-0.837162j, 0.523306-0.303902j, 0.806172-3.69346j, -4.41953+2.59494j, -0.360252+2.59411j, 1.26678+2.93119j] = [2, -3j, 5, -7j, 11, -13j, 17]

Related

  • Compute the Discrete Fourier Transform - This contains some implementations for the standard DFT algorithm which has time complexity O(n2). You'll want to understand how to implement this before trying FFT.
  • Too Fast, Too Fourier: FFT Code Golf - This previous challenge is the precursor to the current challenge here. Before, you only had to consider sequences where the length n was a power of 2 which allowed for simpler recursive implementations. The difference here is that you now have to implement an FFT algorithm that will work for sequences with any length.
\$\endgroup\$
8
  • \$\begingroup\$ nice choice for the title \$\endgroup\$
    – Abr001am
    May 7, 2016 at 20:47
  • \$\begingroup\$ Duplicate? \$\endgroup\$
    – Luis Mendo
    Jun 16, 2016 at 7:43
  • \$\begingroup\$ @LuisMendo That challenge is for sequences where the length is a power of two, but this is for sequences of any length. \$\endgroup\$
    – miles
    Jun 16, 2016 at 7:48
  • \$\begingroup\$ Oh, sorry then. I suggest you add a link in your challenge explaining the difference. I think many people may get confused as I did. Apart from this, if length is not a power of 2 there's another potential problem: what algorithms count as a FFT? \$\endgroup\$
    – Luis Mendo
    Jun 16, 2016 at 7:52
  • \$\begingroup\$ @LuisMendo I had a short snippet stating the difference but I deleted it in my previous edit for some reason. I want it to be so that any FFT algorithm that has a time complexity better than the naive DFT - O(n^2) - will be accepted. It would probably be best to explain an algorithm, ie Cooley-Tukey FFT, that has time complexity O(n log n), and work through a specific example using it. Applying other algorithms would be left to the solver. \$\endgroup\$
    – miles
    Jun 16, 2016 at 8:02
  • \$\begingroup\$ I think the sentence your solution must have time complexity of O(n log n) covers that. Sorry, I missed that again! \$\endgroup\$
    – Luis Mendo
    Jun 16, 2016 at 8:04
  • \$\begingroup\$ @LuisMendo Nevertheless, it'd probably be a good idea to explain one approach for solving this. I'll try to add one later. \$\endgroup\$
    – miles
    Jun 16, 2016 at 8:14
  • \$\begingroup\$ Is there such a thing as a slow Fourier Transform? \$\endgroup\$ Jun 24, 2016 at 3:18
3
\$\begingroup\$

Language succession

Given two words (two strings of lowercase-only letters separated by a space) as input to a program PX written in language X, output two programs in languages Y and Z such that program PY outputs the first word and program PZ outputs the second word. You may output or return these results. These programs may be returned in any fashion as long as it is evident that there are two distinct programs, e.g. double newline, or an array containing the result, or even a fancy box.

Here's the catch: the next answer's language X must be either language Y or Z from a past answer that has not as of the answer been used as a language X. The resulting nodes Y and Z cannot be a language that has appeared yet.

For example, say the first answer is a program written in Java that outputs a programs in Python 2 and Whitespace. Then, the next answer would write a program in either Python 2 or Whitespace that outputs programs in languages different than Java, Whitespace, and Python 2. Let's say it outputs answers in Foo and C++. Then, the next answer must be written in Whitespace, Foo, or C++.

The same user, however, may not extend their own nodes. That is, the person who posted the Java answer in the above example may not extend in Python 2 or Whitespace. Also, no person can extend two nodes of the same answer. So, someone couldn't extend both the Python 2 answer and the Whitespace one.

Here are languages I consider the "same":

  • Different versions of the same language. So, Python 2 is Python 3.
  • Trivial derivatives of a language. Brainfuck syntax substitutions are not valid, say.

However, this does not mean that Python 2 can be exchanged for Python 3.

The next solution in the chain must use the same character set as the previous program PX, adding or removing only 5 characters from that set. There is no restriction on the length of the set. Any characters may be added or removed from the set. Even if characters are not used in a submission, they still remain in the characters set until forcibly removed. (You may optionally substitute the characters with characters in another code page at the same place.) If you need an example, look below.

The winner of this challenge is the one with the last answer. I define "last answer" as the most recently posted answer on this challenge where after a period of seven days after the answer was posted, no new nodes have been extended. Feel free to continue extending nodes after the challenge has ended, but I will not revise the accepted answer. You may use languages made/updated after this challenge and still compete, but only if that language was not made/updated specifically for this challenge.

First post

(this will not be part of the resulting question)

I will start it off. Here's the answer markdown:

# J, initial answer

    split =: 3 : 0
     w1 =. > 0 { ;: y
     w2 =. > 1 { ;: y
     ('alert("' , w1, '")') ; ('print("', w2, ')"')
    )

Languages used:
 1. JavaScript
 2. Python 3

Character set used: `"'(),.0123:;=>aeilnprstwy{`, space, `\r`, and `\n`.

Code points used: `10 13 32 34 39 40 41 44 46 48 49 50 51 58 59 61 62 97 101 105 108 110 112 114 115 116 119 121 123`.

No differences, is initial answer.

Call it like `split 'multiple words'`. Output looks like this:

    +-----------------+--------------+
    |alert("multiple")|print("words")|
    +-----------------+--------------+

Answer format

Here's an example of the answer format to be used.

# Language, extends [language](link to post)

    program

Languages used:
  1. lang 1
  2. lang 2

Character set used: `characters`.

Code points used: `code points`.

Differences:
 * added "c"
 * removed " "

<extra info>

Also, please edit posts saying that one of your languages has been used, like so:

Languages used:
  1. lang 1 ([used](link to post))
  2. lang 2

Language Availability Snippet:

/* Configuration */

var QUESTION_ID = 47338; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 8478; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var LANG_REG = /<h\d>\s*([^\n,]*[^\s,]),[^]*?Languages used:\n\s*1. ([^\n]*)\n\s*2. ([^\n]*)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var used = [];
  var available = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(LANG_REG);
    if (match)
      used.push({
        language: match[1],
        user: getAuthorName(a),
        link: a.share_link
      });
      available.push({
        language: match[2],
        link: a.share_link
      });
      available.push({
        language: match[3],
        link: a.share_link
      });
      
  });
  
  available.filter(function (a) {
      return used.map(function (b) {return b.language}).indexOf(a.language) + 1
  });
  
  used.sort(function (a, b) {
    if (a.language > b.language) return 1;
    if (a.language < b.language) return -1;
    return 0
  });
  available.sort(function (a, b) {
    if (a.language > b.language) return 1;
    if (a.language < b.language) return -1;
    return 0
  });

  used.forEach(function (a) {
    
    var used_lang = jQuery("#used-template").html();
    used_lang = used_lang.replace("{{LANGUAGE}}", a.language)
                   .replace("{{NAME}}", a.user)
                   .replace("{{LINK}}", a.link);
    used_lang = jQuery(used_lang);
    jQuery("#used").append(used_lang);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
  });
  
  available.forEach(function (a) {
    
    var avail_lang = jQuery("#available-template").html();
    avail_lang = avail_lang.replace("{{LANGUAGE}}", a.language)
                   .replace("{{LINK}}", a.link);
    avail_lang = jQuery(avail_lang);
    jQuery("#available").append(avail_lang);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
  });

}
body { text-align: left !important}

#used-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#available-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="avail-list">
  <h2>Available</h2>
  <table class="avail-list">
    <thead>
      <tr><td>Language</td><td>Link</td></tr>
    </thead>
    <tbody id="available">

    </tbody>
  </table>
</div>
<div id="used-list">
  <h2>Used</h2>
  <table class="used-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Link</td></tr>
    </thead>
    <tbody id="used">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="available-template">
    <tr><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="used-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
3
  • \$\begingroup\$ I thought about it a bit, and I think you will run into trouble with the challenge being too easy to extend. I think your second options is better, particularly in that the different branches could have different character sets, which would be cool. Also I think last answer is a better winning criterion, but all of that is just my opinion. Also, probably would be a good idea to ban people from adding children to their own posts (unless you have it and I missed it...) \$\endgroup\$ Jun 17, 2016 at 17:48
  • \$\begingroup\$ @FryAmTheEggman Thanks a lot! I'll hold off on deciding wining criterion until more feedback comes (if any). I will ban people from adding children to their own post, that's a good idea. \$\endgroup\$ Jun 17, 2016 at 17:53
  • \$\begingroup\$ @FryAmTheEggman Oh, nice catch! \$\endgroup\$ Jun 17, 2016 at 18:09
3
\$\begingroup\$

Xor A Rational Number

Background

Consider the fraction 3/5 in base 2:

0.10011001100110011001100110011...
\___/\__/
 (a)  (b)

It has a "regular" or non-repeating part (a) and a repeated part (b). Let's go ahead and shift it right by one bit and xor it with the original:

 x           = 0.10011001100110011001100110011...
(x >> 1)     = 0.01001100110011001100110011001...
(x >> a) ^ x = 0.11010101010101010101010101010...
               \__/\/
               (a) (b)

By examining the regular (a) and repeating (b) parts, we find that (x >> 1) ^ x = 5/6.

Input

  • Two whole numbers 0 < x, y < 256 such that 0 < x/y < 1 and gcd(x, y) = 1
  • Input can be through STDIN or function arguments
  • Input passed in any simple format for two decimals is acceptable, e.g. x y, x\ny, (x,y), [x, y], x/y, x%y (Haskell)
  • Input must be in base 10

Output

  • The numerator and denominator of ((x/y) >> 1) ^ (x/y), in base 10, in any clear output format.

Rules

  • The submission may be a function or full program
  • The output fraction does not have to be in its most reduced form
  • Builtins for rational number xor are not allowed
  • Infinite precision rational number types are allowed
  • This is code golf so shortest answer in bytes wins! (Tie break by first submission)

Test cases

More tests upon request or when this question is posted.

3/5 -> 5/6
1/2 -> 3/4
1/3 -> 4/6

Note:

I'm not entirely sure whether this has a more or less trivial solution...

This is code golf so shortest answer is bytes wins!

\$\endgroup\$
10
  • \$\begingroup\$ Great idea. :) Are rational types allowed for I/O? Or at all? \$\endgroup\$ Aug 1, 2016 at 14:31
  • \$\begingroup\$ Great point. No, I believe that builtins for exact rational numbers should be disallowed. Do you think it's clear that the error should be 0, i.e. exact answers only? \$\endgroup\$ Aug 1, 2016 at 14:33
  • \$\begingroup\$ You've disallowed the use of built-ins for xoring rational numbers. Can we use rational types otherwise as long as we don't xor them? If so, it would probably be good to include that in the valid I/O formats as a useful example. \$\endgroup\$ Aug 1, 2016 at 14:42
  • \$\begingroup\$ "Consider a fraction 2/5:" ok, 0.4. I think you should mention either "base 2" or "binary" somewhere in that first sentence. \$\endgroup\$ Aug 1, 2016 at 14:55
  • \$\begingroup\$ @MartinEnder Yes, that is allowed. I've added that and a couple more valid I/O formats \$\endgroup\$ Aug 1, 2016 at 15:23
  • \$\begingroup\$ I don't think your binary representation of 2/5 is correct. 0.1 in binary is 0.5 in decimal, which is already more than 0.4. 0.01100110... seems to be the correct value. \$\endgroup\$
    – beaker
    Aug 1, 2016 at 16:50
  • 1
    \$\begingroup\$ @beaker You're totally right. I meant to write 3/5 but typo'd it. Thanks for catching that \$\endgroup\$ Aug 1, 2016 at 16:53
  • \$\begingroup\$ That makes more sense \$\endgroup\$
    – beaker
    Aug 1, 2016 at 16:53
  • 1
    \$\begingroup\$ You might be interested that the xor of rationals gives the Sierpinski Gasket as a 3D graph. \$\endgroup\$
    – xnor
    Aug 2, 2016 at 9:38
  • 1
    \$\begingroup\$ I disagree with your third test case. 1/3 = 0.0101010101... so 1/3 ^ 1/6 = 0.011111111... = 1/2. \$\endgroup\$ Aug 2, 2016 at 15:35
3
\$\begingroup\$

The Hanoi KoTH

The KoTH is like this:

Two stacks of height-8 towers are on either side of a total of 11 pegs, and are coloured red and blue.

(Like this: [["R8", "R7", "R6", "R5", "R4", "R3", "R2", "R1"], [], [], [], [], [], [], [], [], [], ["B8", "B7", "B6", "B5", "B4", "B3", "B2", "B1"]] - each array is a peg.)

The objective is to move your entire tower to the opposite side before your opponent does, Tower of Hanoi-style. Red has to move all of their blocks to where Blue's blocks are, and vice versa.

Rules:

  • You may not place a block on top of a block that is of an equal or smaller size.
  • You are only allowed to place a block on your "end tower" once your opponent has cleared away all their blocks.
  • If there are no more "moves" for either side, then the game is a draw.
  • There is a limit of 10,000 moves. If neither side completes their tower, then the game is a draw.
  • If you complete your tower before your opponent does and before the 10,000 moves is over, then you have won.
  • Invalid moves include:
    • Moving a block that is covered by other blocks
    • Moving a block onto a peg that contains smaller or equal-sized blocks than it
    • Doing "null" moves (moves that don't do anything).

Input:

Your input will consist of two numbers separated by a space.

The first number will be the starting peg. Pegs are zero-indexed (so the first peg is 0, and the last peg is 10).

The first number is valid only if the associated peg is not empty, and the block that's on the top of the peg is yours. Any other input is invalid, and your bot will be notified.

The second number will be the peg that your block is moving to. If the stack that the block is moving to is either:

  • Empty, or
  • Contains only larger blocks than the moving block

then the block can move. Otherwise, your bot will be notified that this is an invalid move.

Valid inputs (based on the starting position) would be:

  • 0 4 (Moving the block on peg 0, which is R1, to peg 4)
  • 0 3 (Moving the block on peg 0, which is R1, to peg 3)

Invalid inputs (again, based on the starting position) would be:

  • 1 3 (Invalid because there are no blocks on peg 1)
  • 10 3 (Invalid because the top block on peg 5, B1, is not yours)
  • 0 0 (Invalid because that is a null move)

If 5 invalid inputs are committed by the bot in a row, that counts as an automatic loss.

Output

The program will output to the bot what the current situation is - it will output the eleven arrays, each separated with the / symbol.

So, the starting position is like this:

R8R7R6R5R4R3R2R1//////////B8B7B6B5B4B3B2B1 (the middle nine stacks are empty).

Point System:

  • Win: 5 points
  • Draw: -1 point (to discourage drawing)
  • Loss: -5 points

I've made a small controller here.

META STUFF

  • Is this challenge a dupe?
  • Is there anything I can clarify?
  • Can anyone help with the controller (i.e. fix it up, optimise the code)?
    • Issues with the code:
      • Doesn't work with external files.
\$\endgroup\$
11
  • 1
    \$\begingroup\$ Have you done a game-theoretic analysis to work out the value of the game? (I.e. without the turn limit, is it a win for player 1 or a draw?) \$\endgroup\$ Aug 20, 2016 at 12:27
  • \$\begingroup\$ @PeterTaylor See 2nd rule and 2nd bit of last rule (TBH, those were implemented just for this cause). I did a small analysis, and most of the rules put in place were to counter draws (because frankly, those aren't interesting). Is it possible that you could suggest any improvements to the game via the rules? This is the sandbox, after all. \$\endgroup\$
    – clismique
    Aug 20, 2016 at 12:30
  • \$\begingroup\$ Cabt I trivially move back and forth, to be a nuisance to the other team? \$\endgroup\$ Aug 21, 2016 at 0:22
  • \$\begingroup\$ Oh never mind just saw the last rule \$\endgroup\$ Aug 21, 2016 at 0:57
  • \$\begingroup\$ It does seem like the game space is a bit small though \$\endgroup\$ Aug 21, 2016 at 0:57
  • \$\begingroup\$ @RohanJhunjhunwala Ummm... the rules don't exactly cover the "moving back and forth" thing, but it would be easy to find a counter to that. The game space is adequate enough - I can increase the size if needed. \$\endgroup\$
    – clismique
    Aug 21, 2016 at 1:08
  • \$\begingroup\$ By game space I mean the complexity space as in the game tree complexity en.wikipedia.org/wiki/Game_complexity \$\endgroup\$ Aug 21, 2016 at 1:11
  • \$\begingroup\$ @trichoplax Fixed! \$\endgroup\$
    – clismique
    Aug 21, 2016 at 7:22
  • \$\begingroup\$ @trichoplax Yeah, that's true... I wanted to make it so that multiple bots can play Hanoi at the same time (with multiple towers), but I'm mainly not bothered to improve on the bot in that way. I'm fairly sure that this will be fine in order to finish in a reasonable time. \$\endgroup\$
    – clismique
    Aug 21, 2016 at 7:49
  • \$\begingroup\$ @trichoplax Fixed, again... also, implemented a controller. Can you help with it (if possible)? \$\endgroup\$
    – clismique
    Aug 21, 2016 at 8:09
  • \$\begingroup\$ Now that there's a link to the controller others will be able to give you feedback on it. I won't be able to review it myself at the moment. \$\endgroup\$
    – trichoplax
    Aug 21, 2016 at 8:12
3
\$\begingroup\$

Repetition

In a language called Repetition (something I just made up), there consists an infinite string of 12345678901234567890..., with 1234567890 repeating forever.

The following syntax is available to output numbers:

  • +-*/: This inserts the operator into the string of repeating digits.
    • Examples:
      • + -> 1+2 = 3 (The + inserts a + between 1 and 2)
      • +* -> 1+2*3 = 1+6 = 7 (Same as above, except two operators are used now)
      • / -> 1/2 = 0 (Repetition uses integer division)
    • Each operator is inserted so that it has one digit to its left, unless there are ~'s (see below).
  • c: Concatenates with the next digit in the string.
    • Examples:
      • c+ -> 12+3 = 15 (The c "continues" the 1 and concatenates it with the next digit, 2, to form 12)
      • +c -> 1+23 = 24
  • (): Brackets for processing numbers.
    • Examples:
      • (c+)* -> (12+3)*4 = 15*4 = 60 (Repetition uses the order of operations)
      • (c+)/c -> (12+3)/45 = 15/45 = 0
  • s: Skip a number.
    • s+ -> 2+3 = 5 (s skips 1)
    • csc -> 124 (s skips 3, and c concatenates 12 with 4)

In the examples above, only a finite amount of digits in the infinite string are used. The number of digits used is equivalent to number of operators, concats and skips + 1.

Your task is, when given a string of Repetition code, output the result.

Examples of input and output are:

++ -> 6
- -> -1
(-)* -> -3
cscc -> 1245

This is code golf, so shortest code in bytes wins!

Meta:

  • Is this explained remotely well? Anything I need to clear up?
  • Should this be a code golf or a metagolf challenge? I'm thinking of something like my previous challenge, There can be only 1!.
\$\endgroup\$
10
  • \$\begingroup\$ I'd definitely like it to be a calculator implementation challenge \$\endgroup\$ Sep 16, 2016 at 8:32
  • \$\begingroup\$ @DestructibleWatermelon Calculator implementation challenge? \$\endgroup\$
    – clismique
    Sep 16, 2016 at 8:47
  • \$\begingroup\$ like this one \$\endgroup\$ Sep 16, 2016 at 9:02
  • \$\begingroup\$ @DestructibleWatermelon So, a code-golf, then? \$\endgroup\$
    – clismique
    Sep 16, 2016 at 9:07
  • \$\begingroup\$ I'd definitely love both a code-golf and a metagolf. \$\endgroup\$
    – user48538
    Sep 16, 2016 at 11:17
  • \$\begingroup\$ So, two separate challenges? \$\endgroup\$
    – clismique
    Sep 16, 2016 at 11:19
  • \$\begingroup\$ Shouldn't the number of digits used be number of operators etc. + 1 \$\endgroup\$
    – Riley
    Sep 16, 2016 at 19:14
  • \$\begingroup\$ @Riley Yeah, it should be. Thanks for catching that! \$\endgroup\$
    – clismique
    Sep 16, 2016 at 23:38
  • \$\begingroup\$ I guess its tirvially possible to prove that all numbers can be generated like this, by adding a corresponding series of ones lol... negative numbers can start with ones and subtract (-n + 1) ones \$\endgroup\$ Sep 17, 2016 at 0:03
  • \$\begingroup\$ @RohanJhunjhunwala Yeah, that's true - which is where the metagolfing part comes in, and you have to golf down the output. The code golf doesn't really matter to that either, since you have to process input and return an output. \$\endgroup\$
    – clismique
    Sep 17, 2016 at 0:05
3
\$\begingroup\$

Make an un-polyglot-able language!

The cops' task is to create a language that is as hard to polyglot as possible. However, when making a language, you must follow these rules:

  • ASCII characters only.
  • The language must fit our definition of programming language, i.e. it must be able to add two numbers together, and check, when given a numerical input, if a number is prime or not.
    • You must post the adder and prime checker (the full program) into your answer, and they must be at most 1kb in size.
  • You must post your full interpreter into the answer as well.
  • Also, give a run-down of what each command in your language is and how your language works in general.
  • You must complete the robbers' task, which is to create a polyglot of your language and a language from this list that outputs "Hello, World!". It must not exceed 5kb.
    • If your language doesn't support ASCII output, you can write a program that outputs the ASCII character codes of each character of "Hello, World!".
  • All four of the things above (interpreter, adder, prime checker and "Hello, World!" polyglot) MUST fit into your answer.
  • After your challenge is Cracked, you must post your answer to the robbers' task.
  • If your language has not been Cracked for over 7 days, then your language is Safe. You must put Safe in your header, and post your solution.
  • Your language answer should look like this:

    # {language name}, {cracked/safe} (<- the "cracked/safe" is only to be used 
                                       when your lang is either cracked or safe)
    
    {language description}
    
    {full interpreter}
    
    {adder} (max 1kb)
    
    {primality checker} (max 1kb)
    
    {Hello World polyglot} (<- only posted if your lang is cracked or safe, max 5kb)
    

The robbers' task is to create a polyglot using any cops' language that outputs "Hello, World!".

  • You must output the exact string "Hello, World!", nothing more and nothing less (except for leading and trailing linefeeds).
    • If the cop's language doesn't support ASCII output, you may output the ASCII character codes of "Hello, World!".
  • You only need to support two languages: the cops' one and one from this list of common languages.
  • The final polyglot must not exceed 5kb.
  • Your answer should look like this:

    # {language name}, {original author}, {bytecount}
    
        {insert code here}
    
    {description of code}
    
  • Post a comment on the (in the cops' thread) language that you Cracked, linking them to your answer.

The winner will be:

  • (Cops) the safe language that has the lowest byte-count for the "Hello, World!" polyglot. It will be declared after 1 month.
  • (Robbers) the person who has cracked the most languages.

In case the language list changes, the languages are:

Java, Python, PHP, C#, Javascript, C++, C, Objective C, R, Swift, Matlab,
Ruby, VBA, Visual Basic, Scala, Perl, Lua, Delphi, Go, Haskell, Rust

Meta:

  • Is this challenge a dupe?
  • Anything I can improve on?
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Interesting concept, but this needs some additional work. 1. I couldn't find the winning criterion for the robbers' challenge. 2. You'd somehow have to avoid languages that only compile if the source code has a specific hash. 3. The language list you link to changes every month(?); the challenge spec should be static. \$\endgroup\$
    – Dennis
    Oct 7, 2016 at 4:20
  • \$\begingroup\$ Nothing seems to rule out a language where the program 'a' prints Hello world, 'b' adds numbers, 'c' checks primality, and any other programs do nothing. \$\endgroup\$
    – xnor
    Oct 7, 2016 at 4:43
  • \$\begingroup\$ @xnor That problem is removed by the author having to make his/her own "Hello, World!" polyglot. \$\endgroup\$
    – clismique
    Oct 7, 2016 at 4:53
  • 1
    \$\begingroup\$ Where you allow answers to print the character codes of Hello World, it's not clear whether in that case the mainstream language should also print character codes or still Hello, World!. \$\endgroup\$ Oct 7, 2016 at 21:04
  • \$\begingroup\$ Could you specify tie breakers for both winning criteria (cops and robbers)? I guess first to post would work well for the cops, but for the robbers the tie breaker needs to be chosen carefully. If one person cracks 9 languages that are easy to crack, and another person later cracks 9 languages that are hard to crack, being earlier doesn't seem the ideal way to choose a winner. I can't think of a better way though. \$\endgroup\$
    – trichoplax
    Oct 16, 2016 at 9:13
  • \$\begingroup\$ Is it worth specifying that the crack answer should link to the answer it is cracking? \$\endgroup\$
    – trichoplax
    Oct 16, 2016 at 9:18
3
\$\begingroup\$

The challenge is to write the fastest code possible for computing the permanent of a matrix.

The permanent of an n-by-n matrix A = (ai,j) is defined as

enter image description here

Here S_n represents the set of all permutations of [1, n].

As an example (from the wiki):

enter image description here

In this question matrices are all square and will only have the values -1 and 1 in them.

Examples

Input:

[[ 1 -1 -1  1]
 [-1 -1 -1  1]
 [-1  1 -1  1]
 [ 1 -1 -1  1]]

Permanent:

-4

Input:

[[-1 -1 -1 -1]
 [-1  1 -1 -1]
 [ 1 -1 -1 -1]
 [ 1 -1  1 -1]]

Permanent:

0

Input:

[[ 1 -1  1 -1 -1 -1 -1 -1]
 [-1 -1  1  1 -1  1  1 -1]
 [ 1 -1 -1 -1 -1  1  1  1]
 [-1 -1 -1  1 -1  1  1  1]
 [ 1 -1 -1  1  1  1  1 -1]
 [-1  1 -1  1 -1  1  1 -1]
 [ 1 -1  1 -1  1 -1  1 -1]
 [-1 -1  1 -1  1  1  1  1]]

Permanent:

192

The task

You should write code that, given an n by n matrix, outputs its permanent.

As I will need to test your code it would be helpful if you could give a simple way for me to give matrix as input to your code.

Be warned that the permanent can be large (the all 1s matrix is the extreme case).

Scores and ties

I will test your code on random +-1 matrices of increasing size and stop the first time your code takes more than 1 minute on my computer.

If two people get the same score then the winner is the one which is fastest for that value of n. If those are within 1 second of each other then it is the one posted first.

Languages and libraries

You can use any available language and libraries you like but no pre-existing function to compute the permanent. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.`

Reference implementations

There is already a codegolf question question with lots of code in different languages for computing the permanent. Mathematica and Maple also both have permanent implementations if you can access those.

My Machine The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250. This also means I need to be able to run your code.

\$\endgroup\$
4
  • \$\begingroup\$ Is your system 64-bit? How much memory/disk space can we use? Could you add a reference implementation so that we might have something to initially compare against. \$\endgroup\$
    – miles
    Oct 21, 2016 at 5:28
  • \$\begingroup\$ @miles Yes and I added some details to the question. \$\endgroup\$
    – user9206
    Oct 21, 2016 at 7:45
  • \$\begingroup\$ Thanks. Also I meant a reference implementation that strives to be efficient without using builtins. Most of the submissions from that challenge are very inefficient since the requirement was only up to 6x6 matrices. \$\endgroup\$
    – miles
    Oct 21, 2016 at 8:06
  • \$\begingroup\$ @miles I see. I found this online bpaste.net/show/c346e05415f9 . I don't know if I am allowed to include it. \$\endgroup\$
    – user9206
    Oct 21, 2016 at 10:34
3
\$\begingroup\$

This has been donated to the Secret Santa Sandbox if anyone wants to take up the mantle.

Crazy Librarian's Interesting Numbers Game

Phew, you just managed to finish your code for the Arithmetic Sequence of Primes, and everything went swimmingly for your Crazy Librarian boss. Indeed, the math teacher taught the librarian a new card game as thanks for the prime sequences. However, the librarian wants to beat the math teacher at their own game, and so you're enlisted (again) to assist.

The card game was described as a two-player variation of a trick-taking game called California Jack. Each player is dealt a particular suit of cards from a standard US 52-card deck, and this forms their hand. A third suit of the cards is randomly shuffled and placed face-down between the players as the trophy deck. The fourth suit is unused. Each round, the top of the trophy deck is flipped face-up, and the two players select a card (in secret) from their hand to be their bid for that round, and places it face-down in front of them. The players reveal their bid card, and the higher card (aces low) wins the trophy card. The trophy card goes into the winner's trophy pile, and the two bid cards are discarded. If the players both bid the same card, neither gets the trophy card, and it is discarded along with both bid cards. The winner after all 13 rounds is whoever has the most points in their trophy pile, with Jack=11, Queen=12, and King=13. Note that it is possible for the game to end in a draw (including a zero-point draw).

Since you really want to impress the Crazy Librarian, you've ... enlisted ... the help of some of your friends, and you're going to create a bracket royale to find the best playing algorithm, and use that so the librarian can show up the math teacher.


Questions for Meta

  • Program I/O? I'm envisioning a stateful program that keeps track of its own cards, where each execution is a run of the game against an outside opponent -- e.g., each input is [W/L] T# that says whether the program Won or Lost the previous round, and what the current-round's Trophy card is. Then, the output would be what card it chooses to bid. Repeat 13 times. Could also do an interactive version, scraping STDOUT and setting STDIN?
  • Example of a really simplistic algorithm (in pseudocode) -- return argv[1] -- this just bids the same as whatever the trophy card is.
  • The programs could keep track of their opponent's total and their total, but the controller would have final say (obviously).
  • I'm envisioning a double-bracket style, where each program is randomly seeded into the bracket. Best 3-of-5 games moves it to the next round, while the loser gets re-seeded into the loser's bracket and can re-win a chance for the final four.
  • What am I missing?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think input could be expanded a bit. For instance, there doesn't seem to be any way to track your opponent's cards right now (just whether it won/lost the last), even though in an actual game they would be revealed (and would be part of any decent strategy I'd think). \$\endgroup\$
    – Geobits
    Oct 9, 2015 at 14:03
3
\$\begingroup\$

Planting Sugarcane

In the game Minecraft the crop sugarcane can only be planted on a block that has water along one of its edges..

Task

Given a area what is the most efficient way to place water such that every tile in the area is next to (does not include diagonals) a water block. That is how do you place water to maximize the amount of sugarcane that can be grown in that area.

For example if you had a small plus:

http://www.clipartkid.com/images/656/black-and-white-square-clip-art-8lblvX-clipart.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://www.clipartkid.com/images/656/black-and-white-square-clip-art-8lblvX-clipart.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg

You could grow the most sugarcane if you put the water in the middle:

http://www.clipartkid.com/images/656/black-and-white-square-clip-art-8lblvX-clipart.jpg

http://www.clipartkid.com/images/656/black-and-white-square-clip-art-8lblvX-clipart.jpg

Or If you had a three by three square:

http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg

You could place six sugarcane:




Sometimes the best answer will still leave dirt patches.

For example:

http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg

Is best tiled as:


http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg

I/O

Standard I/O applies.

You may take in an area as either an ASCII diagram with two distinct characters, one representing a block that is in the space and one representing a block that is not or a two dimensional data structure of truthy and falsy values representing the space.

You may output either output a ASCII diagrams with two distinct characters one representing water, and one representing everything else or a two dimensional data structure with truthy and falsy values with the truthy values representing the location of water.

You must also output the number of sugarcanes that can be planted with the scheme described.

Scoring

This is you will be scored accordingly.

\$\endgroup\$
5
  • \$\begingroup\$ You want to tighten up the spec a little bit. It's lind of vague as it stands \$\endgroup\$ Aug 23, 2016 at 23:00
  • \$\begingroup\$ 1. Define "next to". 2. The closest dupe that I can think of is codegolf.stackexchange.com/q/17096/194 . They're both examples of (non-exact) set cover using a square lattice, but with different neighbourhoods. I would say it's just on the right side of the borderline, but others may disagree. \$\endgroup\$ Aug 24, 2016 at 10:24
  • \$\begingroup\$ In the second example, what makes it not be [[S,W,S],[W,S,S],[S,S,W]]? \$\endgroup\$ Nov 1, 2016 at 18:17
  • \$\begingroup\$ @carusocomputing That is also a valid answer \$\endgroup\$
    – Wheat Wizard Mod
    Nov 1, 2016 at 18:18
  • 5
    \$\begingroup\$ Maybe instead of requiring them to output the explicit combination, have them calculate the maximum number of sugar cane possible. \$\endgroup\$ Nov 1, 2016 at 18:19
3
\$\begingroup\$

Will the snake bump into itself?

Given a string containing NESW characters, check if a snake will bump into itself if it moves like this:

The snake starts out with length 2.

For every character in the string:

  • If the character is N, move the head of the snake up one.
  • If the character is E, move the head of the snake right one.
  • If the character is S, move the head of the snake down one.
  • If the character is W, move the head of the snake left one.

The rest of the snake follows the path of the head of the snake.

The snake grows 1 unit longer every 2 moves.

Your task is to determine if the snake will bump into itself, and give a truthy or falsey value accordingly.

Truthy Inputs

NS
NWSSENW

Falsey Inputs

NNN
SS
NWNNNWWWSSS
NWNNEEEESSS

More test cases coming soon.

\$\endgroup\$
1
  • \$\begingroup\$ Does the snake move between inputs? \$\endgroup\$ Nov 23, 2016 at 22:04
3
\$\begingroup\$

Implement the sin function.

For those unfamiliar with trignometry. The sin function is a mathematical wave function, it can be defined a number of ways, but the canonical definition, is that it is sin(x) gives the ratio of the opposite side of an angle of measure (X) to the hypotenuse of a right triangle


Your job is to implement a program or function, that receives an angle (x) in degrees or radians, and outputs sin(x) to an accuracy of +/- .001 for at least the 360 degree values on a circle (or their radian equivalents). You may also specify a range that has width of a minimum of 360 degrees (or 2 pi radians) and require inputs to be converted to an equivalent angle to fit within that range. See the following table for outputs (multiples of 15 degrees are provided). You may not rely on any inbuilt library for trig functions. (i.e return Math.sin(x) is forbidden, or cos(90-x) or something similar 1/sqrt(tan(x-pi/2)^2+1)).
(Degrees|Radians|Sin)

0|0.0|0.0
15|0.2617993877991494|0.25881904510252074
30|0.5235987755982988|0.49999999999999994
45|0.7853981633974483|0.7071067811865475
60|1.0471975511965976|0.8660254037844386
75|1.3089969389957472|0.9659258262890683
90|1.5707963267948966|1.0
105|1.8325957145940461|0.9659258262890683
120|2.0943951023931953|0.8660254037844387
135|2.356194490192345|0.7071067811865476
150|2.6179938779914944|0.49999999999999994
165|2.8797932657906435|0.258819045102521
180|3.141592653589793|1.2246467991473532E-16
195|3.4033920413889422|-0.25881904510252035
210|3.6651914291880923|-0.5000000000000001
225|3.9269908169872414|-0.7071067811865475
240|4.1887902047863905|-0.8660254037844385
255|4.4505895925855405|-0.9659258262890683
270|4.71238898038469|-1.0
285|4.974188368183839|-0.9659258262890684
300|5.235987755982989|-0.8660254037844386
315|5.497787143782138|-0.7071067811865477
330|5.759586531581287|-0.5000000000000004
345|6.021385919380437|-0.2588190451025207
360|6.283185307179586|-2.4492935982947064E-16


This is , but it aims to be a canonical list of trig function implementation in esolangs, especially those without a sin function built in. No answer may rely on a built in method.

\$\endgroup\$
10
  • \$\begingroup\$ So you can just use a sin(x) builtin in your program? \$\endgroup\$
    – user41805
    Nov 24, 2016 at 16:27
  • \$\begingroup\$ @KritixiLithos sadly, yes. \$\endgroup\$ Nov 24, 2016 at 16:40
  • \$\begingroup\$ @KritixiLithos I believe it is frowned upon to outright ban certain built ins. \$\endgroup\$ Nov 24, 2016 at 16:41
  • \$\begingroup\$ @RohanJhunjhunwala I don't think it would be frowned upon to ban sin(x)-built-ins when the task is to implement exactly such built-ins. \$\endgroup\$
    – Laikoni
    Nov 24, 2016 at 17:49
  • \$\begingroup\$ @Laikoni fixed. \$\endgroup\$ Nov 24, 2016 at 19:03
  • 2
    \$\begingroup\$ @KritixiLithos I banned built ins now. \$\endgroup\$ Nov 24, 2016 at 19:04
  • \$\begingroup\$ Related but not duplicate as the scoring is different. codegolf.stackexchange.com/q/30160/15599 @RohanJhunjhunwala what is frowned upon is "do x without y" challenges, which are often rather unimaginative "print this phrase without using the necessary letters." This is a "do x without x" challenge which is fine. You should ban all trig functions (otherwise I will just do cos x-90) and also complex numbers (I would do i**(x/90) and take the imaginary part.) \$\endgroup\$ Nov 25, 2016 at 0:21
  • \$\begingroup\$ @LevelRiverSt I did ban all trig functions \$\endgroup\$ Nov 25, 2016 at 4:37
  • \$\begingroup\$ What about complex exponentiation builtins? Those have a very easy way to implement sin, but can be hard to ban as it's just basic arithmetic. \$\endgroup\$
    – user62131
    Jan 1, 2017 at 10:08
  • \$\begingroup\$ @ais523 that seems moderately more involved, and not agains tthe spirit of the challenge. I think I'll allow it. \$\endgroup\$ Jan 1, 2017 at 13:14
3
\$\begingroup\$

Happy New Year, 2017

Your task is to write a complete program, that if started today (December 16th, 2016), will produce no output until it is New Year's Day in 2017 (January 1st, 2017, 12:00am). At this exact moment (in your computer's local time), it will inform the user "Happy New Year!". After this, it can either keep running forever (producing no output ever again), or exit. Starting the program after this time will produce no output ever. Informing the user can be done in any manner EXCEPT for printing to stdout, such as a GUI, spoken through the speakers, sending an email or a text to you, or any other reasonable way of informing the user that they are now in 2017.

(Note for sandbox reviewers: the "today December 16th" part will be updated for whatever day it is when I post the challenge for real.)

\$\endgroup\$
6
  • 1
    \$\begingroup\$ I think this would be more suited as a code-golf. It might also be a duplicate \$\endgroup\$
    – Blue
    Dec 16, 2016 at 17:05
  • \$\begingroup\$ I thought it was a duplicate too, but I couldn't find one quite like it. \$\endgroup\$
    – Cody
    Dec 16, 2016 at 17:06
  • \$\begingroup\$ you are probably thinking about this question that was closed as dupe of this one \$\endgroup\$
    – Rod
    Dec 16, 2016 at 18:11
  • \$\begingroup\$ The second linked question is different, that challenge applies to a specific day on any year, whereas mine applies to one day ever. It is similar to the first one, but that one was closed as a dupe (even though they are different). Mine is more flexible, however, in that it allows outputs via formats other than stdout. \$\endgroup\$
    – Cody
    Dec 16, 2016 at 18:18
  • \$\begingroup\$ It is definitely a dupe of the second one that @Rod posted. Hardcoding the number 2017 instead of getting it from current system time is pretty irrelevant, especially as it's somewhat common to allow languages that don't have a built-in date function to accept the current datetime as an input. \$\endgroup\$ Dec 16, 2016 at 18:40
  • \$\begingroup\$ I modified the challenge to be distinct from the linked question. \$\endgroup\$
    – Cody
    Dec 16, 2016 at 18:46
3
\$\begingroup\$

Dot matrix number visualization

Your task is to make a program that takes a number as input and outputs it as a wall of characters with spaces. The digits should be written like this:

  1    222   333     4  55555  666  77777  888   999   000 
 11   2   2 3   3   44  5     6   6     7 8   8 9   9 0   0
1 1       2     3  4 4  5555  6        7  8   8 9   9 0  00
  1      2    33  4  4      5 6666    7    888   9999 0 0 0
  1     2       3 44444     5 6   6  7    8   8     9 00  0
  1    2    3   3    4  5   5 6   6  7    8   8 9   9 0   0
11111 22222  333     4   555   666   7     888   999   000  

Each digit is represented as a grid of 5x7 characters consisting of spaces and the digit itself. The number should be written like above with a vertical line of spaces separating the different digits.

The preformatted text above should be the output of a 1234567890 number input. If you guys like this challenge, I'll post an image that better visualizes how each number should be printed.

Lowest size program wins.

Edit: Added a picture to better illustrate the digits. Dotmatrix digit grid

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's pretty clear what you're giving as the task, but an image would help, as the pre-formatted text is rather hard to read \$\endgroup\$ Jan 17, 2017 at 11:59
  • \$\begingroup\$ @TrojanByAccident: It is pretty obvious what result the author wanted even without the image. \$\endgroup\$
    – sergiol
    Jan 24, 2017 at 17:34
3
\$\begingroup\$

Powerful numbers

Look at the number 81 expressed as the sum of distinct powers of the same base:

  • 81 = 81 (well, duh)
  • 81 = 80 + 1 (easy)
  • 81 = 9*9
  • 81 = 4*4*4 + 4*4 + 1
  • 81 = 3*3*3*3
  • 81 = 2*2*2*2*2*2 + 2*2*2*2 + 1 (if you thought that was obvious...)
  • 81 = 1 + 1 + ... + 1 (yeah, yeah...)

As you can see, for N > 4, there are always 4 trivial bases: 1, 2, N-1 and N. Powerful numbers are those numbers which have at least one nontrivial base. Please write a program or function that, given a number N > 4, outputs a truthy or falsy value for whether a nontrivial base exists. The results for N up to 30 should be as follows:

(1  F)  16  T
(2  F)  17  T
(3  F)  18  F
(4  F)  19  F
 5  F   20  T
 6  F   21  T
 7  F   22  F
 8  F   23  F
 9  T   24  F
10  T   25  T
11  F   26  T
12  T   27  T
13  T   28  T
14  F   29  F
15  F   30  T

This is , so the shortest solution wins!

\$\endgroup\$
17
  • 2
    \$\begingroup\$ "Your challenge is, given a number N, to return the Nth Powerful number." I doubt that there's any way to generate the Nth number other than counting up from 1 and stopping once you've encountered N of them. So why not reduce it to "given a number, determine whether it's powerful"? \$\endgroup\$ Jan 19, 2017 at 12:13
  • 2
    \$\begingroup\$ Simplified definition: "a powerful number is a number which can be written using only the digits 0 and 1 in any base other than 1, 2, n, or n-1." \$\endgroup\$
    – user62131
    Jan 19, 2017 at 15:37
  • 1
    \$\begingroup\$ I believe a (very golfed) reference implementation in ES6 to determine whether a number is powerful would be a=>(g=b=>b>1&&(f=c=>c&&c%b|f(c/b|0),f(a)<2)+g(b-1))(a)>3. This gives these first 1000 powerful numbers. The sequence doesn't seem to be on OEIS though. \$\endgroup\$ Jan 19, 2017 at 17:36
  • \$\begingroup\$ @MartinEnder I was under the impression that it was more common to ask for the Nth or first N terms rather than just verifying a particular term. Perhaps if I ask for all Powerful numbers up to N? \$\endgroup\$
    – Neil
    Jan 19, 2017 at 21:01
  • 2
    \$\begingroup\$ @Neil I think that's even worse. That way you make 100% sure that there's no way to avoid wrapping the entire program in a boring loop. \$\endgroup\$ Jan 19, 2017 at 21:10
  • \$\begingroup\$ I like challenges like this better as a decision-problem, since that's what it comes down to. Outputting the Nth such number or the first N just adds extra code around the real meat of the challenge. \$\endgroup\$ Jan 19, 2017 at 22:03
  • \$\begingroup\$ Example for first N terms: codegolf.stackexchange.com/questions/107420/… \$\endgroup\$
    – Neil
    Jan 20, 2017 at 9:45
  • \$\begingroup\$ @MartinEnder OK, how about if, given an integer N greater than 1, the result should be the number of representations? \$\endgroup\$
    – Neil
    Jan 20, 2017 at 19:18
  • \$\begingroup\$ @Neil That's fine, but I'm curious why you're so strongly opposed to making it a simple decision problem. :) \$\endgroup\$ Jan 21, 2017 at 14:38
  • \$\begingroup\$ @MartinEnder You want people to add extra code to compare the result to 4 around the real meat of the challenge? (Sorry I couldn't resist!) \$\endgroup\$
    – Neil
    Jan 21, 2017 at 15:48
  • \$\begingroup\$ Quoting me now, are you? :P But you don't actually have to count all of them since 4 are already given: 1, 2, n-1, and n. So all you really have to do in a decision-problem is check if there are any between 3 and n-2, inclusive. \$\endgroup\$ Jan 21, 2017 at 22:40
  • \$\begingroup\$ That said, I'm not sure which path would be shorter in most langs. My attempts in JS for both versions of the problem turned out the same length. \$\endgroup\$ Jan 21, 2017 at 23:37
  • \$\begingroup\$ @ETHproductions OK I'm convinced now. \$\endgroup\$
    – Neil
    Jan 22, 2017 at 1:08
  • \$\begingroup\$ Related OEIS sequence \$\endgroup\$ Jan 22, 2017 at 22:23
  • \$\begingroup\$ I actually don't know whether decision-problem would be better than just counting how many bases it's powerful in. There are arguments for and against each. My solutions turned out the same length in JS, but in Jelly the decision-problem solution came out as just 2 extra bytes added to an 8-byte counting solution. I guess it just comes down to what you want to see in the challenge. \$\endgroup\$ Jan 23, 2017 at 16:48
3
\$\begingroup\$

Does Mathematica Have a Builtin?

Mathematica has a lot of builtins.

Your task is to take in a question names and its tags; and to guess whether or not Mathematica has a builtin that solves that question.

Rules

  • Your code must be less than 100 bytes long.

  • You may use internet to access the Mathematica reference guide you may also use the internet to access the tag wikis. Standard loopholes apply to internet access.

  • For this challenge we will consider a valid builtin to be a builtin that does most of the computation for the challenge. Extra bytes spent on trivialities like IO formatting will be ignored.

  • You must output a truthy value if Mathematica has a builtin to solve that challenge and a falsy value otherwise.

  • If Mathematica has a builtin and for some reason the challenge does not allow Mathematica to compete or bans builtins your program must still output truthy.

Scoring

This is a so you will be scored on the percentage questions here (This is currently a work in progress there will be more cases in the final question) that your program gets the correct answer on.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ As always with builtins, you'll want to outline exactly what counts as "built-in". For example, if a challenge is about printing hexagonal numbers, does using PolygonalNumber with fixing r = 6 count? (not sure if that's an accurate example, but you get the point). The test battery would make things 100% indisputable, but it's something you might want to think about when making the test battery. \$\endgroup\$
    – Sp3000
    Jan 26, 2017 at 1:55
  • \$\begingroup\$ On a side note, is a hardcoded approach okay, e.g. regex golfing the pass vs fail set? \$\endgroup\$
    – Sp3000
    Jan 26, 2017 at 1:55
  • \$\begingroup\$ @ETHproductions I meant the later, a function that does most of the work. I am not sure if I am going to write a super strict definition of builtin but I will be writing at least a loose one. \$\endgroup\$
    – Wheat Wizard Mod
    Jan 26, 2017 at 1:57
  • \$\begingroup\$ @Sp3000 Hardcoded is fine. I would like to see all sorts of approaches to this problem including regex. \$\endgroup\$
    – Wheat Wizard Mod
    Jan 26, 2017 at 1:58
  • \$\begingroup\$ My question codegolf.stackexchange.com/questions/107181/… was solved in Mathematica with a built-in that I wasn't expecting. That might be useful for your tests \$\endgroup\$
    – Gareth
    Jan 26, 2017 at 9:22
  • \$\begingroup\$ Can you read the Mathematica answer off the page if it exists, or is the idea to only read the question? \$\endgroup\$
    – xnor
    Jan 26, 2017 at 9:40
  • \$\begingroup\$ @Gareth Thanks I am in need of more test cases. \$\endgroup\$
    – Wheat Wizard Mod
    Jan 26, 2017 at 12:52
  • \$\begingroup\$ Answer: Hardcode truthy because Mathematica ALWAYS has a builtin :P \$\endgroup\$
    – user42649
    Apr 10, 2017 at 13:05
3
\$\begingroup\$

Minimal QWERTY

The task -- to output the layout of a QWERTY keyboard:

QWERTYUIOP
ASDFGHJKL
ZXCVBNM

But, you will be scored based on the length of your code, and on the number of distinct characters in it.

Rules

1) The code must output the three lines of text above (or the text above with optional trailing newline)

2) Standard loophole restrictions apply

3) If the language contains predefined information about the QWERTY layout, you are not allowed to use that information.

Scoring

The score will be defined as [Length of the program in bytes]*[# of distinct characters in the program], with lowest score winning.

For example, the code

ABAB1212

would have score 8*4=32 since it has length 8, but only 4 distinct characters: AB12

And the code:

ABC!!!{{{

Would have score 9*5=45, since it has length 9, and 5 distinct characters: ABC!{

\$\endgroup\$
11
  • 3
    \$\begingroup\$ I really like this scoring system; it strikes a great balance between cutting down chars and cutting down the number of distinct chars you're using. I was going to say that this might not be the best way to use this scoring system, but anything other than "output this exact string" would likely be solvable in 10 bytes in golfing languages, or not solvable in 100 in non-golfing langs. (Perhaps a string with more repetition would work better though, but we won't know until the challenge is posted.) \$\endgroup\$ May 6, 2017 at 20:31
  • 1
    \$\begingroup\$ About "If the language contains predefined information about the QWERTY layout, you are not allowed to use it.": does this mean you're not allowed to use the language, or just the QWERTY built-in? \$\endgroup\$ May 6, 2017 at 20:33
  • 1
    \$\begingroup\$ @ETHproductions Thanks for the input! The reason I thought thought the QWERTY task would work well with this scoring system is that the output consists almost entirely of a large number of distinct characters (meaning any substantial use of string literals for the output would be very bad for the score), and those characters are fairly disordered, meaning a simple loop won't solve it. Do you have thoughts on other possible tasks for this scoring system? \$\endgroup\$
    – Maria
    May 7, 2017 at 1:54
  • \$\begingroup\$ Regarding your second question -- the language would be allowed; they just wouldn't be allowed to use the predefined information. I've changed the wording to make that clear (I see that it was ambiguous before - thanks for catching that) \$\endgroup\$
    – Maria
    May 7, 2017 at 1:58
  • \$\begingroup\$ May be too close to this challenge. It's not quite the same, but the basic task is similar (golf down a large set of distinct characters into a set of mostly repeated characters). This challenge is even closer, requesting printing a constant string with many distinct characters, and using the same scoring method; that's almost certainly a duplicate at this point. \$\endgroup\$
    – user62131
    May 7, 2017 at 2:23
  • \$\begingroup\$ @ComradeSparklePony I think this is covered by the condition to exclude this? \$\endgroup\$ May 7, 2017 at 21:02
  • \$\begingroup\$ @PaŭloEbermann Oops, I missed that. \$\endgroup\$
    – sporklpony
    May 7, 2017 at 21:05
  • \$\begingroup\$ +1, when are you going to post this? \$\endgroup\$
    – MD XF
    May 10, 2017 at 1:22
  • \$\begingroup\$ I kinda agree with @ETHproductions first comment regarding a string with more repetition and non-golfing languages. For example, to solve this in fewest bytes in Java 7 (I know, Java 7 is verbose as F.. xD), it will be: String r(){return"QWERTYUIOP\nASDFGHJKL\nZXCVBNM";} (score of 51 bytes * 41 unique characters = 2091). With fewest characters possible you'll abuse unicodes and it becomes pastebin.com/unrn6xj2 (too long for comment..), with a score of 343 bytes * 18 unique characters = 6174.. But of course, you're free to post it nonetheless as is. Java won't ever compete anyway ;) \$\endgroup\$ May 10, 2017 at 9:07
  • \$\begingroup\$ But I like the scoring mechanism, and it's also a fairly easy challenge for most golfing languages, where the size vs unique characters really matters, which is of course the focus of code-golfing languages. So perhaps just post it, and I'll just score 2091 with my Java 7 answer. ;) \$\endgroup\$ May 10, 2017 at 9:10
  • \$\begingroup\$ Japt, 4 points ;D :D \$\endgroup\$ May 19, 2017 at 20:13
3
\$\begingroup\$

Exiting Vim — Cops & Robbers

In honour of the recent milestone, let's turn escaping Vim into a game!

Rules for Cops

Starting from launching vim with no arguments (i.e. no initial file open), provide a sequence of keys to be typed in to the editor.

Rules for Robbers

Starting from the state described by the cop, provide a sequence of keys to exit Vim.

Scoring

Cops are scored by the difference between key counts <robber_key_count> - <cop_key_count>, and robbers are scored by the ratio of key counts <cop_key_count> / <robber_key_count>. Higher scores are better.

Keys are counted as one per key-down event (e.g. a sequence of Ctrl+X, Ctrl+Y, Ctrl+Z only need count the Ctrl once, unless it must be released during the sequence). Note that this is not the same as the golf-rules scoring for Vim.

Plugins are not permitted.

Example 1

Cop (1 key): i

Robber (4 keys): Esc : q Enter

Score for cop = 4 - 1 = 3, score for robber = 1 / 4 = 0.25

Example 2

Cop (2 keys): i i

Robber (5 keys): Esc : q ! Enter

Score for cop = 5 - 2 = 3, score for robber = 2 / 5 = 0.4

Example 3

Cop (3 keys): i Ctrl+V

Robber (6 keys): Return Esc : q ! Enter

Score for cop = 6 - 3 = 3, score for robber = 3 / 6 = 0.5

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm not sure that the scoring here rewards cops enough for ingenuity (all the examples score 3 after all!), so ideas on that would be great. Also I'm considering banning Esc & Ctrl+[ to make this more interesting, but I suspect even with Esc permitted there are ways to get seriously tied-up. \$\endgroup\$
    – Dave
    May 23, 2017 at 20:13
  • \$\begingroup\$ I'm worried that there may not be much scope for the cops to improve; it'd be something of a design flaw in the challenge if there's a hard limit to how well a cop can do. Also, what about key sequences that depend on the environment within which vim is running? (For example, Ctrl-Z will suspend vim and require the use of the shell to either exit or restart it, but how you do that depends on which shell is running; or on Linux, Ctrl-Alt-F1 will probably switch to a different virtual terminal altogether, and what assumptions can you make about its state?) \$\endgroup\$
    – user62131
    May 31, 2017 at 21:35
  • \$\begingroup\$ Another potential problem: exit sequences which have side effects. In particular, I'm thinking about Alt-SysRq-K, which is guaranteed to exit vim, in addition to everything else, on Linux systems which have it enabled. That compares favourably to basically all the exit strings you have right now, and there's no way, short of reconfiguring the OS, to block it. \$\endgroup\$
    – user62131
    May 31, 2017 at 21:36
  • \$\begingroup\$ @ais523 I'm thinking it could easily be restricted to "vim-only" commands, so anything which is intercepted by the shell can be forbidden. But I agree that it feels like there's a hard-limit on the cop (though I don't know vim nearly well enough to be sure, and I've seen some hints around the internet that it's possible to get exceedingly stuck, but perhaps only because some modes need obscure non-esc keys, rather than needing more keys). Any ideas for better scoring? \$\endgroup\$
    – Dave
    Jun 5, 2017 at 20:36
3
\$\begingroup\$

Mark Duplicates

Given a list of non-negative integers, find the values which are duplicates and mark their positions.

For example, given [1, 2, 3, 2, 1], the output could be [1, 1, 0, 1, 1] where each 1 signifies that the value at that position is duplicated elsewhere in the array and each 0 signifies that the value at that position is unique.

Your output may use either 0 and 1, boolean values for false and true, or any other two distinct values as long as you remain consistent.

This is so minimize the length of your code.

Test Cases

[] -> []
[5] -> [0]
[0, 1] -> [0, 0]
[2, 2] -> [1, 1]
[1, 2, 3, 2, 1] -> [1, 1, 0, 1, 1]
[6, 3, 6, 3, 5, 2, 3] -> [1, 1, 1, 1, 0, 0, 1]
\$\endgroup\$
12
  • 2
    \$\begingroup\$ Ironically, I feel this is a duplicate of (or at least closely related to) and existing challenge but I can't find it at the moment. \$\endgroup\$
    – Shaggy
    May 24, 2017 at 10:43
  • \$\begingroup\$ Would we have to use 0 & 1 or could we use any 2 distinct & consistent values? \$\endgroup\$
    – Shaggy
    May 24, 2017 at 11:06
  • \$\begingroup\$ I.e Nub Sieve? \$\endgroup\$
    – Adám
    May 24, 2017 at 11:27
  • \$\begingroup\$ @Adám I previously made a challenge for nub sieve. This is slightly different since we aren't choosing positions to filter for only the unique values. \$\endgroup\$
    – miles
    May 24, 2017 at 18:43
  • 1
    \$\begingroup\$ @Shaggy Yes, any choice of output values is fine as long as its two distinct values that you use consistently. \$\endgroup\$
    – miles
    May 24, 2017 at 18:45
  • \$\begingroup\$ Isn't this just NOT nub sieve? \$\endgroup\$
    – Adám
    May 24, 2017 at 18:47
  • \$\begingroup\$ @Adám For the [1, 2, 3, 2, 1], nub sieve could be [1, 1, 1, 0, 0], [0, 1, 1, 0, 1], [0, 0, 1, 1, 1], [1, 0, 1, 1, 0], and the not of each is [0, 0, 0, 1, 1], [1, 0, 0, 1, 0], [1, 1, 0 ,0, 0], [0, 1, 0, 0, 1]. \$\endgroup\$
    – miles
    May 24, 2017 at 19:21
  • \$\begingroup\$ I think this would be interesting if the first time an entry appears it's not counted as a duplicate. \$\endgroup\$
    – xnor
    May 24, 2017 at 19:37
  • \$\begingroup\$ @xnor Wouldn't that be not( nub-sieve( x ) )? \$\endgroup\$
    – miles
    May 24, 2017 at 20:23
  • \$\begingroup\$ How does nub-sieve work? My suggestion is because it means the position of the item matters rather than just its value, so it's not just mapping each entry x to l.count(x)>1. \$\endgroup\$
    – xnor
    May 24, 2017 at 20:26
  • \$\begingroup\$ The first occurrence of a value is marked true and all subsequent occurrences of the same value are marked false. Nub-sieve. My previous challenge for distinct sieves is a relaxed variant to nub-sieve. For [1, 2, 3, 2, 1], a proper nub-sieve would be [1, 1, 1, 0, 0], and not of that would be [0, 0, 0, 1, 1]. I do agree with that last sentence about how most solutions in golfing languages would probably just count occurrences. \$\endgroup\$
    – miles
    May 24, 2017 at 20:44
  • \$\begingroup\$ @miles can I adopt and post this abandoned proposal? \$\endgroup\$
    – user58826
    Jun 9, 2017 at 1:34
3
\$\begingroup\$

This message is open for anyone to adopt and post to main. For more details, see the chat room or meta post.

Nonogram it

Nonograms are one of my favorite types of puzzles, but sometimes there are not enough of them to solve!

The challenge here is to write a program that would take an image and output the values for the columns and rows of the puzzle.

INPUT: black and white PNG on STDIN

OUTPUT: two lines with the values to create the puzzle. First line is the columns, second the rows. The format of both lines is: [a,b,c...],[d,...],... (lists of integers separated with commas delimited with [], with each list separated by commas, ending in a newline. No dangling commas allowed inside the lists or at line end)

The squares on the image should be of 5x5px. The thereshold for determining if a square is filled is if it has at least 30% black inside it.

(3 sample images will be added later)


I'm not sure about the scoring for this challenge, most likely it should be a .

Additional scoring criteria I can think of:

  • allowing to enter square size or cols*rows of the puzzle.
  • accepting non black and white images
  • reading other image types
  • providing a solver
\$\endgroup\$
12
  • 1
    \$\begingroup\$ wait, is the PNG itself in the STDIN, or a file path to it? I assume the latter, but it's currently formulated as if it's the former. Also, the threshold needs to be clarified. Also, why is the image scaled up in the first place? \$\endgroup\$ Mar 26, 2014 at 19:59
  • 2
    \$\begingroup\$ Also, I'd prefer an ascii-art input (a grid of hashes and spaces) than having the challenge complicated by looking up and interfacing an image manipulation API. \$\endgroup\$ Mar 26, 2014 at 20:02
  • \$\begingroup\$ It could be a file path if that's more accesible. I didn't say the image was scaled, the 5*5 squares are for the grid to create the nonogram, just to avoid another required parameter(number of cols*rows desired). About the ascii-art, that would have no challenge, just a count() \$\endgroup\$
    – Einacio
    Mar 27, 2014 at 15:42
  • 1
    \$\begingroup\$ I don't think a PNG library showoff is a good challenge for this site. There's no thinking present, just having to learn an API and hope it has short enough names. \$\endgroup\$ Mar 27, 2014 at 15:45
  • 1
    \$\begingroup\$ I don't understand the 5x5 rule. Is it that there are 5x5 pixels in the image, and 5x5 pixels in the grid? 5x5s are no puzzles. \$\endgroup\$ Mar 27, 2014 at 15:46
  • \$\begingroup\$ It wouldn't be the first challenge using PNG, so I see no problem there. About the grid, I'll prepare the example images later, I hope that'll be clearer to understand \$\endgroup\$
    – Einacio
    Mar 27, 2014 at 16:02
  • 1
    \$\begingroup\$ Seeing that you prescribe exactly how black and white cells are to be determined, unique solubility of the resulting nonogram is no criterion? \$\endgroup\$ Mar 31, 2014 at 11:28
  • \$\begingroup\$ @m.buettner I proposed the fixed grid and cell criterion with the idea of being able to check results against others. I forgot about ambiguous solutions, and I don't know how difficult is to test for it, specially if it ends as a code-golf. Maybe I should rule it out explicitly to keep answers simpler? \$\endgroup\$
    – Einacio
    Mar 31, 2014 at 14:18
  • 1
    \$\begingroup\$ @Einacio well, uniqueness could be checked with a solver (there might be easier ways). I suppose you just have to decide whether you want soluble or comparable answers. If you are going for soluble, you can make this a "code challenge" and determine the score based on both code length and similarity to input image. \$\endgroup\$ Mar 31, 2014 at 14:58
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 16:29
  • \$\begingroup\$ @programmer5000 Hi, I totally forgot about this challenge, I haven't had much free time in those 3 years to give it some love. I would be delighted to see someone pull it through, do I have to do something more than post it in the chat? \$\endgroup\$
    – Einacio
    Jun 9, 2017 at 19:40
  • \$\begingroup\$ @Einacio just post a link to this answer and nothing else in that chat room. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 19:55
3
\$\begingroup\$

Irreducible Polynomials over a Finite Field

Given a polynomial whose coefficients are in a finite field, deduce whether or not it is irreducible, without using any related built-ins (you can use a built-in that represents polynomials, but you cannot use built-ins for factoring or otherwise finding information about the polynomial).

A polynomial in F[x] (where F is a field) is considered irreducible if it cannot be factored into the product of non-constant polynomials.

I/O:

Your program/function will take two inputs:

  • a prime number for the order of the Finite Field
  • some representation for the polynomial

Output a truthy value if the polynomial is irreducible, and a falsy value otherwise.

Test Cases

Your program must run in a reasonable time for this (i.e. 1 hour is definitely too long):

>>> F = 2, f(x) = x^3 + x^2 + x + 1
false
>>> F = 5, f(x) = x^4 + 4x^3 + 4x^2 + x
false
>>> F = 2, f(x) = x^4 + x + 1
true
>>> F = 5, f(x) = x^3 + x + 1
true
>>> F = 5, f(x) = x^6 + 2x^4 + 2x^3 + x^2 + 2x + 1
false
>>> F = 2, f(x) = x^6 + x^2 + 1
false
>>> F = 5, f(x) = 4x^4
false

Meta Note:

These are all really related:

The first especially. This challenge is very similar to the first, except that the first is for irreducible polynomials over Z (the integers), whereas this is for irreducible polynomials over finite fields. Although the challenges are similar, I feel this is different enough to warrant a new challenge

\$\endgroup\$
5
  • \$\begingroup\$ Is the polynomial guaranteed to be monic? Is the zero polynomial irreducible? Also, are you OK with brute-force solutions that take huge amounts of time? \$\endgroup\$
    – xnor
    Oct 18, 2014 at 5:20
  • \$\begingroup\$ @xnor No, the polynomial is not guaranteed to be monic, yes brute-force is okay if it runs in reasonable time for the test cases - I wrote a program that took <20 min for all but the 2nd last test case, which would take 2 days. Regarding zero polynomial, I need to do a bit of research first. \$\endgroup\$
    – Justin
    Oct 27, 2014 at 5:56
  • 1
    \$\begingroup\$ Now that I almost have an answer to the polynomial factoring question I can say that the test cases can be handled by brute force in a slow language in a few seconds. It's the case over Z that allows tough performance requirements with simple test cases. \$\endgroup\$ Oct 28, 2014 at 7:54
  • \$\begingroup\$ @programmer5000 No, I would still like to use this. I had forgotten about it, and I will improve it and post it to main. Thank you for reminding me about this post \$\endgroup\$
    – Justin
    Jun 11, 2017 at 6:59
  • \$\begingroup\$ I feel like many people will not know what a finite field is. I think you should explain it in the post to allow people to answer without google. \$\endgroup\$ Jun 11, 2017 at 19:19
3
\$\begingroup\$

ASKEY robbers

You are a robber in the ASCII world. ASCII lock-key work in similar fashion as the real-world: matching ridges. Your objective is to write a program which generates a duplicate key for the ASCII locks.

Example:

A Lock is given as:

   |\    |\         
 __| \___| \____             
|               | 
|_______________| 

Its key shall be something like:

 _______________
|   __     __   |
|  |  \   |  \  |  
|__|   \__|   \_|

The fit being something like:

 _______________
|   __     __   |
|  ||\\   ||\\  |
|__|| \\__|| \\_|
|               |
|_______________| 

SandBox

I think the fit is weird. It didn't go as I had imagined when I finished typing in the ASCII drawing.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ This has potential, but it needs a clear specification as to what a fit is, and what constitutes a lock (i.e. some constraint on the input). \$\endgroup\$ Jun 14, 2017 at 17:47
  • \$\begingroup\$ Yes. This is very incomplete/unclear as of yet. \$\endgroup\$ Jun 15, 2017 at 3:27
3
\$\begingroup\$

When did I need to be born to celebrate a magic birthday?

I was born in 1984 and in 2016 I became 32 years old, which is 20 in base 16, what a coincidence!

Your task is, given the year of interest -say 2016- , to calculate the year I had to be born to be able to say In 2016 I have celebrated/I will celebrate my 20th birthday (in base 16).

  1. take n-digit decimal number - the year xy.
  2. Split it in half, if n is odd, the digit the middle is appended to number side.
  3. Calculate the year I had to be born to be x base ys old in the year of xy.

Your code shall return Not-a-Number or error message if the decomposition cannot be resolved.

Walkthough:

>  foo(2016)
1: '2016' -> '20' '16'
2: 20 base 16 = 32
3: 2016-32 = 1984
>> 1984

> foo(445)
1: '445' ->'44' '5'
2: 44 base 5 = 24
3: 445-24 = 421
>> 421

>foo(7)
1: '7' -> '7' ''
Error, base not defined
>> nan

>foo(10)
1: '10' -> '1' '0'
Error, base 0 don't exist
>> nan

>foo(1805)
1: '1805'->'18' '5'
Syntax error
>> nan

Test cases:

 7    : nan/error
10    : nan/error
78    : 71
445   : 421 
1024  : 1000
1805  : nan/error
1936  : 1891
1984  : 1891
1999  : 1891
2016  : 1984
2015  : 1985
10002 : 9998
10912 : 10759
116015: 115769

Shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Boo-urns to input validation! Can you add a full example? \$\endgroup\$
    – Shaggy
    Jun 21, 2017 at 16:14
  • \$\begingroup\$ Do you mean full ungolfed code or full path from, say 445 to 421? \$\endgroup\$
    – Crowley
    Jun 21, 2017 at 16:25
  • \$\begingroup\$ Just a walkthrough of how to get from input to output. \$\endgroup\$
    – Shaggy
    Jun 21, 2017 at 16:26
  • \$\begingroup\$ @Shaggy Thanks for sugegstion. Is it better now? \$\endgroup\$
    – Crowley
    Jun 21, 2017 at 17:16
  • \$\begingroup\$ Shouldn't 1999 result in 1891? \$\endgroup\$
    – Emigna
    Jun 22, 2017 at 8:49
  • \$\begingroup\$ @Emigna Correct. Updated. \$\endgroup\$
    – Crowley
    Jun 22, 2017 at 13:36
3
\$\begingroup\$

Is there a total ordering?

TL;DR:

Given a set of strings, determine whether the characters expose a total ordering based on location in the strings.


In this challenge, strings are used as a predicate to determine the order in which characters should appear in this set. For example, the string

"ONE"

Says:

  • All instances of "N" should appear only after instances of "O"

  • All instances of "E" should appear only after instances of "N"

By this reasoning, the string "FOOOONZAi.EE" follows this ordering, but "NEEEE3#?EAO" does not (there is an "O" after an "N").


Your challenge is to take a set of strings and determine whether these strings define a total ordering without any logical flaws. This would occur as a cycle of any length, such as:

  • "N" must follow "P"

  • "P" must follow "N"

...or such as:

  • "A" must follow "B"

  • "B" must follow "C"

  • "C" must follow "A"

etc.


Rather than strings, you may take in lists of characters or integers if you wish.

Since this is a , you may output any two consistent values for yes or no, such as true and false, zero and non-zero, exception and no exception, etc. Just specify your output format in your answer.


Test Cases

["ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX"] -> true (one possible ordering is "TWFOUIVXNHRE")
["SEVEN"] -> false ("E" must follow "V" which must follow "E")
["ZERO", "FOUR"] -> false ("R" must follow "O", but "O" must follow "U" which must follow "R")
["", ".", "forty", "this->~why();", " -y."] -> true
["AB", "BC", "CD", "DE", "AC", "BD", "CE", "EA"] -> false

(more can be written if needed)

Scoring

This is , so the shortest answer in each language wins.

Sandbox

How can I make this more clear? Any suggestions?

\$\endgroup\$
6
  • \$\begingroup\$ This could be more general if you allow lists as input rather than strings. \$\endgroup\$
    – lirtosiast
    Jul 13, 2017 at 22:18
  • \$\begingroup\$ @lirtosiast So a list of lists of characters? \$\endgroup\$ Jul 14, 2017 at 0:52
  • \$\begingroup\$ I would recommend lists of integers instead of strings. I feel the challenge would be "cleaner" that way, but that's up to you. Also, you should have a test case where where each pair is consistent but the whole set isn't. \$\endgroup\$
    – Zgarb
    Jul 15, 2017 at 7:17
  • \$\begingroup\$ Is this not effectively the same as your previous challenge of whether a directed graph has a cycle? \$\endgroup\$
    – xnor
    Jul 16, 2017 at 1:19
  • \$\begingroup\$ @xnor I suppose it is, though I think the challenging part is collecting the edges by vertex. How about this: I rewrite the challenge to be "Give a valid ordering for a set of strings, guaranteed that one exists"? \$\endgroup\$ Jul 16, 2017 at 3:49
  • \$\begingroup\$ @musicman523 I remember a DAG sorting challenge, I think that would be a dupe of it. \$\endgroup\$
    – xnor
    Jul 16, 2017 at 3:52
3
\$\begingroup\$

Make a Minecraft Crafting Table

\$\endgroup\$
3
  • \$\begingroup\$ +1 This seems like a really fun challenge! I think you should clarify what counts as a recipe. For instance, are gold chestplates and iron chestplates counted as 2 working recipes, or do you need to implement all chestplates to count for 1 recipe? Similarly, for unshaped crafting, does each valid combination (ie ----G---- and -G------- for gold nuggets) count seperately? \$\endgroup\$ Jul 15, 2017 at 0:03
  • \$\begingroup\$ Unfortunately, you were ninja'd by Minecraft 1.12, which adds recipe hints ;) \$\endgroup\$
    – hyper-neutrino Mod
    Jul 15, 2017 at 20:24
  • 1
    \$\begingroup\$ @HyperNeutrino I posted this first (MC 1.12 came out June 7th) so I ninja'd Minecraft \$\endgroup\$ Jul 15, 2017 at 20:25
3
\$\begingroup\$

Self-Improvement

Your Task

You must create a self-mutable program that, when run, outputs a non-zero integer and also overwrites the file with a program that outputs double the number.

For example, if I run the program self-improvement and it outputs 10, it must output 20 when I run it the second time, output 40 the next time, and so on.

Additional Notes

  • You must not rely on any file on the computer other than your program.
  • Said program must consist of only one file.
  • Of course, no loopholes that are banned from the entire site.
  • You can assume that your program won't go tested beyond the range -2^16 to 2^16-1.
\$\endgroup\$
6
  • 1
    \$\begingroup\$ no loopholes banned -> no loopholes that are banned, overwrite -> overwrites. Also, something on how far this needs to go might be important - does it have to work infinitely, or only to INT_MAX for the language in question? If you choose the second option, keep in mind language with very small numeric caps. Otherwise, welcome to PPCG, I really like this question, and I'm glad you Sandbox'd it :) \$\endgroup\$
    – Stephen
    Jul 17, 2017 at 21:33
  • \$\begingroup\$ @StepHen Thanks; I decided that they can assume that the parameters won't go beyond INT_MAX. \$\endgroup\$ Jul 17, 2017 at 21:38
  • 2
    \$\begingroup\$ In case anyone needs to find it at some point, don't forget about this standard loophole. \$\endgroup\$
    – Stephen
    Jul 17, 2017 at 22:24
  • \$\begingroup\$ @Artyer I stated "any nonzero integer". That excludes 0. \$\endgroup\$ Jul 17, 2017 at 22:55
  • \$\begingroup\$ @LawfulLazy I didn't read that too well. \$\endgroup\$
    – Artyer
    Jul 17, 2017 at 22:58
  • \$\begingroup\$ @Artyer I'll make sure to embolden it. I've also set a minimum integer range for StepHen. \$\endgroup\$ Jul 17, 2017 at 22:59
3
\$\begingroup\$

How high can you count in English?

Challenge

In 500 bytes (or fewer) write a program that outputs a list of the English word forms of as many consecutive integers greater than zero as you can.

For example, score 6:

one two three four five six

Example submission (hopefully you can do better than this):


Python 3, score 43 (488 bytes)

print(["one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen", "sixteen","seventeen","eighteen","nineteen","twenty","twenty-one","twenty-two","twenty-three","twenty-four","twenty-five","twenty-six","twenty-seven","twenty-eight","twenty-nine","thirty","thirty-one","thirty-two","thirty-three","thirty-four","thirty-five","thirty-six","thirty-seven","thirty-eight","thirty-nine","forty","forty-one","forty-two","forty-three"])

Try it online!


Scoring and rules

For each language, the person whose code counts the highest wins. In case of a tie, the person who submitted first wins.

  • No modules, libraries, builtins that convert from numeric to word form are allowed.
  • You must output all integers from 1 (one) to n (your score) without missing any. If you want to output 0 (zero) as well, that's fine.
  • You are allowed up to 500 bytes of code. Your code may be a full program or function.
  • Number format: for consistency, all numbers must match the output of this site.
  • Standard loopholes apply (of course)
  • Standard output rules apply
\$\endgroup\$
10
  • 2
    \$\begingroup\$ Come on, you could at least make your example better by just using a single space-separated string ;) but nice challenge! :) \$\endgroup\$
    – hyper-neutrino Mod
    Jul 18, 2017 at 18:00
  • 1
    \$\begingroup\$ Alternate title: How high can you count in English? \$\endgroup\$
    – Stephen
    Jul 18, 2017 at 18:06
  • \$\begingroup\$ You may, however, omit "and" if you'd like. do we have to omit and or not? Personally, I'd say you wouldn't as it 'sounds more correct'. \$\endgroup\$
    – Okx
    Jul 18, 2017 at 18:11
  • \$\begingroup\$ @StepHen changed, thanks. \$\endgroup\$
    – wrymug
    Jul 18, 2017 at 18:15
  • \$\begingroup\$ Your edit doesn't answer my question. Do we have to omit and or not? \$\endgroup\$
    – Okx
    Jul 18, 2017 at 18:15
  • \$\begingroup\$ @Okx I take your point. Removed. \$\endgroup\$
    – wrymug
    Jul 18, 2017 at 18:28
  • 1
    \$\begingroup\$ I'm not sure this adds to existing number-to-english challenges like this or this. Past getting the same basic pattern of digits down, the question seems to be how many prefixes for powers of 1000 one can compress into the remaining bytes. \$\endgroup\$
    – xnor
    Jul 18, 2017 at 18:33
  • 1
    \$\begingroup\$ Off the jokes, what if I can count to infinity? \$\endgroup\$ Jul 20, 2017 at 13:40
  • \$\begingroup\$ @courtois I don't see how that would be possible, but I guess you'd win \$\endgroup\$
    – wrymug
    Jul 20, 2017 at 13:42
  • \$\begingroup\$ @rosslh yeah you're right, I just saw the sentence Number format: for consistency, all numbers must match the output of [this](https://lingojam.com/NumbersToWords) site. And for my method, it would have been with million of billion of billion of ... though the site stops at one hundred novenonagintanongentillion, something like 3002 zeros. \$\endgroup\$ Jul 20, 2017 at 13:43
3
\$\begingroup\$

ASCII addition

Objective

Given two strings, your job is to:

  1. Convert each character to their respective ASCII decimal value
  2. Concatenate the numbers into one large number
  3. Add these values together
  4. Get the ASCII characters represented of each pair of numbers starting from the right (or if there are not enough numbers, take a number alone)
  5. Leave unprintables (ie not in the range 32 - 126), and output the rest

An example for HELLO and WORLD

"HELLO"    + "WORLD"
H E L L O  + W O R L D
7269767679 + 8779827668
1 60 49 59 53 47    (separated to show ASCII conversion easily)
   <  1  ;  5  /    convert to ASCII by converting pairs to their respective characters (note: you start from the last pair)
<1;5/               output (note there is no 0x01) 

Notes

  • Each string will be a maximum of 6 characters long
  • Input will always contain readable ASCII characters
  • You have to take pairs of numbers from the end of the sum and convert each one of them to ASCII
  • You must not print unreadable characters if their values appear and instead skip them

Examples

ABC + XYZ  //input
656667 + 888990
1 54 56 57
   6  8  9       //again 0x01 is left out
689      //output

Rules

  • Your submission can be either a program or a function

This is so the program with the shortest bytecount wins!

Sandbox Questions

  • Are the specs clear enough?
  • Will this question give me hats?
  • Any better title suggestions?
\$\endgroup\$
12
  • \$\begingroup\$ What range of ASCII characters do we need to be able to handle in the input? Only printable characters or any? \$\endgroup\$ Dec 20, 2016 at 20:07
  • 1
    \$\begingroup\$ I swear we've had this challenge, but I can't seem to find it ... \$\endgroup\$ Dec 20, 2016 at 20:21
  • \$\begingroup\$ Edited that into the specs \$\endgroup\$
    – user41805
    Dec 20, 2016 at 20:22
  • \$\begingroup\$ @TimmyD How's this now? \$\endgroup\$
    – user41805
    Dec 21, 2016 at 7:28
  • \$\begingroup\$ what if a character is unprintable? do we still need to output it then? \$\endgroup\$ Dec 21, 2016 at 7:46
  • \$\begingroup\$ @DestructibleWatermelon Yes \$\endgroup\$
    – user41805
    Dec 21, 2016 at 7:56
  • \$\begingroup\$ Better wording. Given that a bunch of control codes are possible, some test cases that demonstrate expected behavior when (e.g.) 11 or 13 occur in the output would be of good value. \$\endgroup\$ Dec 21, 2016 at 13:49
  • \$\begingroup\$ @TimmyD Do you think it would be a good idea if I restrict the output to displaying only characters if their values are between 32 and 126 because outputting other values might be difficult in some languages? \$\endgroup\$
    – user41805
    Dec 21, 2016 at 13:54
  • \$\begingroup\$ That may be a better way to go, but you'll need to be very careful with the wording. For example, suppose that the output number is ...226... and the 26 is slated to be the pair of digits that get converted to ASCII. Obviously, that's outside the printable range, so let's look at the next digit, but now 226 is also outside. Does that mean just the 6 is skipped? The 26 is skipped? The 226 is skipped? \$\endgroup\$ Dec 21, 2016 at 13:58
  • \$\begingroup\$ @Cowsquack You don't say precisely (but we see it in the test case) how many digits we need to parse at a time, before outputting. \$\endgroup\$ Jul 18, 2017 at 14:06
  • \$\begingroup\$ @V.Courtois Is this clearer now? \$\endgroup\$
    – user41805
    Jul 19, 2017 at 12:48
  • \$\begingroup\$ @Cowsquack This is! In fact you could see, in the comments some were wondering too if we had to print things like 125 -> }. \$\endgroup\$ Jul 19, 2017 at 12:55
3
\$\begingroup\$

Deduplicate equivalent expressions

Suppose we wanted to generate all expressions containing at most 2 of + and −. We might have a list like this:

a + b + c         b + c + a
a + b - c         b + c - a
a - b + c         b - c + a
a - b - c         b - c - a
a + c + b         c + a + b
a + c - b         c + a - b
a - c + b         c - a + b
a - c - b         c - a - b
b + a + c         c + b + a
b + a - c         c + b - a
b - a + c         c - b + a
b - a - c         c - b - a

There is a lot of repetition here. It surely isn't necessary to include all of a + b + c, a + c + b, b + a + c, b + c + a, c + a + b, and c + b + a, since they all mean the same thing. This can be deduced from knowing that, for any x and y, x + y is the same as y + x.

Similarly, b + a - c and a - c + b are equivalent. To deduce this, one must know that, for any x and y, x - y is the same as x + (-y).

Let's assume the following:

[1]: a + b == b + a
[2]: a - b == a + -b

Then, we can deduce that b + a - c and a - c + b are equivalent:

start:  b + a - c
        b + a + -c        by 2
        a + b + -c        by 1
        a + -c + b        by 1
end:    a - c + b         by 2

Therefore, they are the same. After performing similar proofs, we are left with the list:

a + b + c
a + b - c
a - b + c
a - b - c
b - a + c
b - c - a
c - b - a

Definition of an expression

An expression can be described as:

variable   = "a" | "b" | "c" | ... | "y" | "z";
digit      = "0" | "1" | "2" | ... | "8" | "9";
number     = digit . digit*;
operator   = "!" | "#" | "$" | "%" | "&" | "*" | "+"
           | "~" | "-" | "." | "/" | ":" | ";" | "<"
           | "=" | ">" | "?" | "@" | "^" | "_" | "`"
           | "|";
data       = number | variable;
subexpr    = data | operator* . data;
expression = subexpr
           | subexpr . operator . expression;

Where | suggests alternatives, . suggests concatenation (with potential whitespace around each operand), * suggests "0 or more times", and " is a string literal.

x + y, j * i - 3, u & 4 * 2 < ~4, q % ~*^t and r are all expressions.

You should assume all operators are left-associative.

Definition of assumptions

An assumption is a pair of expressions said to be equivalent. This means one can be transformed into the other. When performing a transformation using an assumption, one replaces all the appropriate variables and maintains the numbers as they are. (These "variables" can also be sub-expressions, which is any expression not using an operator in the assumption.)

For example, if the assumption is !a == a + 5, then one can transform t + 5 into !t and 3 + 5 into !3.

Another example: if the assumption is a + b == a * b @ b, then 5 + 2 can become 5 * 2 @ 2 and z * 3 @ 3 can become z + 3, but z * 4 @ a cannot be reduced further using this rule.

One last example: if the assumption is a < b == a, then 1 + 3 & 5 < 2 * 3 + 6 would become 1 + 3 & 5, and 1 + 2 < x + y < 7 $ q would become 1 + 2, since it would be equivalent to (1 + 2) < (x + y) < (7 $ q), which is thus 1 + 2.

If either side of the assumption is a single variable, numbers are excluded from this assumption. E.g., the assumption a == 3 would only apply to variables.

Expression equality

Two expressions are equal if they can be proven to be the same. Variables must be the same for each expression; for example, a + b is not by default the same as b + c.

Challenge

Your task is to remove "duplicate" expressions given some assumptions. You can use any unambiguous symbol or method, including taking a pair of strings, to represent an expression. The expressions remaining in the result do not necessarily have to be in the set, but must be equivalent by the given assumptions. E.g., if you have a + b - c and b - c + a in the input, you can have -c + b + a represent these in the resultant set. You should try each equation in the order that it's given to you (to simulate "precedence").

The input consists of a list of assumptions and a list of input expressions. The input expressions can be an array or container of strings or string pointers, or in any way standard to your language. (E.g., for C, one should expect null-terminated strings.) The input format must be consistent for all runs.

The output can be a list representation (as is standard to your language), can be separated by newlines (\r, \n, and \r\n are acceptable), or separated by commas. The output format must be consistent between runs.

This is a , so the shortest program in bytes wins.

Test cases

Every output is merely an example, and is not the only valid output.

Assumptions: { e1 == e2, e3 == e4, ... eN-1 == eN }
Input: { expr1, expr2, ... exprN }
Output: { expr1, expr2, ..., exprK }

Assumptions: { "a + b" == "b + a" }
Input: { "3 + 4", "4 + 3", "5 * a", "a + 2", "2 * a", "a * 5", "a + b", "2 + a" }
Output: { "3 + 4", "5 * a", "a + 2", "2 * a", "a * 5", "a + b" }

Assumptions: { "a + 0" == "a", "a * 1" == "a", "a * b" == "b * a", "a + b" == "b + a" }
Input: { "1 * 2 * 3", "3 * 2 + 0", "1 + 2 + 3" }
Output: { "1 * 2 * 3", "1 + 2 + 3" }
    OR: { "2 * 3", "1 + 2 + 3" }

Assumptions: { "~a" == "a ~ a" }
Input: { "~z", "z ~ z", "~a", "~~a", "a ~ a ~ a ~ a" }
Output: { "~a", "~z", "~~a" }

Assumptions: { "a + b" == "0" }
Input: { "x + y", "0", "3 + y + a + v + k", "75", "4 + 2" }
Output: { "0", "75" }

Assumptions: { }
Input: { "x + y", "x + y", "y + x", "3", "3 ! 3" }
Output: { "x + y", "y + x", "3", "3 ! 3" }

Assumptions: { "j" == "3" }
Input: { "v + t", "z", "q", "q + r + t", "4 + 2" }
Output: { "v + t", "z", "q + r + t", "4 + 2" }

Assumptions: { "a" == "b" }
Input: { "a", "b + c", "e % t", "q & t", "!3", "z" }
Output: { "a", "b + c", "e % t", "q & t", "!3" }

Assumptions: { "1 & 0" == "0", "1 & 1" == "1", "0 & 0" == "0", "a & b" == "b & a", "0 ? a : b" == "b", "1 ? a : b" == "a" }
Input: { "1 & 1 & 0", "j & k", "y & z", "z & y", "1 & 0 ? k & j : 0" }
Output: { "0", "j & k", "y & z" }
\$\endgroup\$
9
  • \$\begingroup\$ Several of your expressions are inconsistently quoted. I also think you should explain what should happen when the assumption is something like 3 == a. Would I remove one of: 5, 7? It seems if you had a == b as the assumption you would, but the other one is counter-intuitive to me. Also, a == b is rather odd on its own, perhaps that is also a good test case. Also, the empty assumption if you intend to allow it. \$\endgroup\$ Jul 17, 2017 at 3:18
  • \$\begingroup\$ @FryAmTheEggman Could you clarify your first question? Are you asking what should happen if 5, 7 is the input given the assumption a == 3? \$\endgroup\$ Jul 17, 2017 at 4:00
  • \$\begingroup\$ Yes, that's what I meant. \$\endgroup\$ Jul 17, 2017 at 4:08
  • \$\begingroup\$ 1. subexpr = data | operator* . data; is surely equivalent to just subexpr = operator* . data;? 2. For the second test case it would be more illustrative to include an example output like { "0 * 2 + 3", "1 + 2 + 3" }. 3. I'm not sure what you mean by "If either side of the assumption is a single variable, numbers are excluded from this assumption". Is it that an assumption a == 3 with input {"b == 2", "c == 2", "4 == 2"} should give output e.g. {"3 == 2", "4 == 2"} rather than {"3 == 2"}? \$\endgroup\$ Jul 17, 2017 at 7:43
  • \$\begingroup\$ @PeterTaylor 1. yeah, I original had * mean "1 or more"; will fix. 2. good idea. 3. Well, the way that input would be parsed is b = = 2, with a binary = followed by a unary =. Could you perhaps use a different symbol? I don't quite understand your confusion. \$\endgroup\$ Jul 17, 2017 at 16:53
  • \$\begingroup\$ Sure: assumptions: { "a" == "3" }; input: {"b + 2", "c + 2", "4 + 2"}. Is {"3 + 2", "4 + 2"} the correct output? \$\endgroup\$ Jul 17, 2017 at 18:03
  • \$\begingroup\$ @PeterTaylor Yes, it is. \$\endgroup\$ Jul 17, 2017 at 18:34
  • \$\begingroup\$ The definition of assumptions includes an assumption with more than one operator, but none of the test cases do. I would think that's an important thing to test. \$\endgroup\$ Jul 26, 2017 at 11:06
  • \$\begingroup\$ @PeterTaylor Added. \$\endgroup\$ Jul 26, 2017 at 19:32
1
13 14
15
16 17
134

You must log in to answer this question.

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