571
\$\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".

\$\endgroup\$
0

4629 Answers 4629

1
53 54
55
56 57
155
1
\$\begingroup\$

Format a list of words

Your challenge is to format a list of words across multiple lines that are no longer than a given number of characters, so that each line contains as many words as possible and no words are unnecessarily cut off.

Input

The input will be a space-separated list of words and then a number that is at least 4.

Output

The output should be the input words grouped into lines so that none of the lines contains more characters than the input number. The lines should be output in the order they were input. The words should be comma-separated, and each line except the last should end with a comma. If a word is too long to fit on a line, it should be cut off as little as possible while following the other rules, and "..." should be added to the end.

Test cases

Input:
foo bar baz qux 12

Output:
foo, bar,
baz, qux


Input:
foo bar baz qux 5

Output:
foo,
bar,
baz,
qux


Input:
strength dexterity constitution intelligence wisdom charisma 10

Output:
strength,
dexterity,
consti...,
intell...,
wisdom,
charisma


Input:
quas wex exort 4
...,
wex,
e...

Sandbox questions

  • Has this been done before?
\$\endgroup\$
1
\$\begingroup\$

Smallest Turing Complete Interpreter

Sandbox Notes

  • Has anything like this ever been done before?
  • Do you think this will be well received?
  • In my research I couldn't find a simple definition of what makes a language "Turing complete". What alterations or additions should I make to the language rules? I would prefer that the language in every answer was not exactly the same, but at the same time I want to keep the complexity as low as possible (while still being Turing complete) so that ideally one of the answers would become the world's smallest (non-eval) interpreter.
  • Are there any other loopholes I missed?

Let me know in the comments!


Your challenge is to make the smallest possible interpreter for a programming language.

What is the language we are interpreting?

You get to create the language! You can implement any instructions you like, however the language must be Turing complete. For the purposes of this challenge, your "Turing complete" language must be able to:

  • Store and retrieve an arbitrary amount of data in memory The amount must be theoretically infinite, but your interpreter only needs to handle a minimum of 64 kilobytes (256 ^ 0xffff distinct values). The format could be an array of numbers, a string, a very large integer (if the language of your interpreter supports 524288-bit integers :P ) or any other format that provides the same number of distinct values.
  • Loop conditionally The loop must also be able to alter the execution flow (if you implement a while loop that can only have one instruction in the body, it won't be able to affect anything outside of the while loop). This can be one command (eg: while A do { B C D }) or two (eg: if A then B and goto C) or any number that produces the same effect.
  • Print any ASCII character This includes code points 32 to 126 inclusive. Newline is not required but being able to print characters outside of this range is fine.

It does not need to take input. Any extra features are fine as long as it meets these requirements. The language does not have to be pleasant to use, but each of these requirements must be usable in the real world.

See the languages here for some inspiration...

Input

  • Your interpreter must take a single string containing the source code of a program in your language.
  • The input will always be a valid program. You do not need to handle endless loops, impossible instructions, etc.

Output

  • A single string containing the output of the program.
  • A single trailing newline is allowed, any other leading or trailing whitespace is not.

Rules

  • The only rule is that you cannot use eval (or equivalent) in your interpreter.
  • Your interpreter must be a full program, not just a function. Input and output must be from STDIN, STDOUT or their equivalents.
  • The interpreter and the specifications of your language must be posted in your answer. Make sure you include all details that prove the language is Turing complete!
  • Your language can be identical to an existing language or a language from another answer.

Remember...

This is . Your score is the number of bytes in the source code of your interpreter, so design your language to minimise this score.

Good luck!


Sample Answer

JavaScript (ES6), 148 bytes

s=prompt();o="";m=[];for(p=i=0;c=s[i];i++)v=m[p],+c?c-1?c-2?c-3?c-4?o+=String.fromCharCode(v):p++:p--:m[p]=~~v+1:m[p]=~~v-1:m[p]?i=m[p+1]:0;alert(o)

Language Specification

Memory is stored on an infinite tape. The pointer variable points to a position within this tape. The index variable holds the index of the current instruction in the source code being executed. Each instruction is a single-digit number. The numbers do the following:

  • 5 = print character ASCII code at pointer
  • 4 = increment pointer
  • 3 = decrement pointer
  • 2 = increment value at pointer
  • 1 = decrement value at pointer
  • 0 = if the value at pointer is non-zero, set index to the value at pointer + 1

Explanation

Using numbers instead of letters for the instructions means I can check with c-3 instead of c=="x".

s=prompt();
o="";
m=[];
for(p=i=0;c=s[i];i++)
  v=m[p],
  +c?
    c-1?
      c-2?
        c-3?
          c-4?
            o+=String.fromCharCode(v)
          :p++
        :p--
      :m[p]=~~v+1
    :m[p]=~~v-1
  :m[p]?i=m[p+1]:0;
alert(o)

Test

prompt = () => input.value;
alert = (output) => result.textContent = output;
var solution = _=>{ s=prompt();o="";m=[];for(p=i=0;c=s[i];i++)v=m[p],+c?c-1?c-2?c-3?c-4?o+=String.fromCharCode(v):p++:p--:m[p]=~~v+1:m[p]=~~v-1:m[p]?i=m[p+1]:0;alert(o) };
<textarea id="input" rows="5" cols="70">222222222222222222222222222222222222222222222222222222222222222222222222522222222222222222222222222222522222225522254222222222222222222222222222222222222222222225111111111111531111111111111111111111115222222222222222222222222522251111115111111115425</textarea><br />
<button onclick="solution()">Go</button>
<pre id="result"></pre>


Tags:

\$\endgroup\$
7
  • \$\begingroup\$ You ought to add that all submissions include a proof of TC-ness \$\endgroup\$
    – quintopia
    Jan 9, 2016 at 6:49
  • \$\begingroup\$ @quintopia Yes. I've been contemplating what the simplest way to prove turing-completeness is. At the moment the only way to check is by looking at their language specs and comparing them to the checklist in my question, but maybe there's a simple program that uses all these rules that I could require (or at least recommend) to be made and run in their language which proves Turing completeness... \$\endgroup\$
    – user81655
    Jan 9, 2016 at 8:03
  • \$\begingroup\$ The only way to prove TC-ness that I know is to reduce a universal language to it. But you can let the submitter decide which language they want to reduce to it. \$\endgroup\$
    – quintopia
    Jan 9, 2016 at 8:07
  • 1
    \$\begingroup\$ 1. I would vote to close this as too broad. It essentially duplicates half of the interpreter tag. See in particular codegolf.stackexchange.com/q/40300/194 . 2. What makes a language TC is the ability to emulate a universal TM. This is often proven by proving ability to emulate another known-TC system and applying transitivity. 3. In "a minimum of 64 kilobytes (256 ^ 0xffff distinct values)", what is ^ and how does 256 ^ 0xffff relate to 64 kB? 4. Not all TC systems have an explicit concept of loop. \$\endgroup\$ Jan 9, 2016 at 17:04
  • 1
    \$\begingroup\$ 5. Output in ASCII seems to directly contradict your stated intention to "keep the complexity as low as possible" and inspire "the world's smallest (non-eval) interpreter". 6. The restriction against eval seriously constrains some languages' ability to process input. \$\endgroup\$ Jan 9, 2016 at 17:05
  • \$\begingroup\$ @PeterTaylor Yeah, the broadness of the challenge is my main concern. I'm not sure there is a way to fix this without changing the purpose of the challenge as well. Addressing your other points: 3. There are 256 to-the-power-of 0xffff different ways you can arrange the bits of a 64 kilobyte block of bits. I just worded it like this to illustrate that the memory can be stored in any way that produces the same effect (rather than enforcing a 16384 length array of 32-bit integers, etc). The wording could be improved. \$\endgroup\$
    – user81655
    Jan 10, 2016 at 2:47
  • \$\begingroup\$ @PeterTaylor 4. I assumed that would be necessary. How would it compute a recursive algorithm without the execution jumping back to the start of the algorithm repeatedly? 5. True. It's purpose was to unify the output of the languages and simplify testing but it would probably be more work for some interpreter languages. 6. That was to prevent trivial answers like eval(input). I could make an exception for using eval to parse the input as a literal. \$\endgroup\$
    – user81655
    Jan 10, 2016 at 2:47
1
\$\begingroup\$

"Compress" text into Zalgo

Zalgo, the Nezperdian hivemind of chaos, is a type of text that uses combining characters to make very tall and noisy text. If you don't know what I'm talking about, maybe this will jog your memory:

<zalgo>




H̡̢̢̡̡̧̢̡͎̟͚̮͓͇̦̮̙̗̜̱̱͔̲̹̣̱̠̀̀͐̑̾̓̃́̃̍̀͆̇͆̽̔̒̚̕͘̚͜͝͠͠ͅE̢̧͓̺͉̟͙͇̳̰͉͖̺̻͕̰̱̝̳̙̰̟̠̯̘̰̲̎̑͋͂͑́͛̎͋̇̍̾̊̈́̂̽̿͆͛͑̽̒̊́͠͝͠͝͝ͅ ̨̢̟̳̥̖̺̼͎̩̘̰̣̼͇̰̫̞̜̲̰͔̗̠͔̩̻̳͇̾͌̆̑̍̄̊͗̓̃̆̊̄̽̐̂͛̏͑̒̓̆͝͝͝Ç̛̬̩͙̱̥̦̪̮̖͚͚͔̼̱̺̳̳̬̭͍̣͍̙̹̜̫̟̳͌̓͗͊̐̈̄́̏̀͂̎̃̈́̈́̎͋̀̒̊̀̈́͒̽͘̕͝Ȏ̡̡̨̡̝̬̠͚̠̯͖̹̟͓̮̻̲͙̖̪̯͇̍̅̂̌̌̒͗̈́̉͆̇̑͒̉̂̾̃̌̽͛͘͝͝ͅM̡̢̢̘͉̤͍̫̺̻͕̱̤̤̞̟̞̹͉͓̥̳͖̹̤̆̋̓͂̂͑̃̌͛͂̋̂̓̏́̀̾̋̈́̅̐̅̎̇̐̽͜͝Ȩ̨̛̭̥̹̳̫͎͖͈̳̠͍͙͉̻̼͍̞̜̺̝̻̝̗̳̏̈̓͋̐́̋͆͋̓̿͐͆̾̾̃͌͌̾̊́̚͘͘͜S̡̢̡̡̛̯̪̬̹̲̙̮̲̲̤͖͖̞̲̞̼̪͓͇̤̼͇͆͋̊̈̑̆̿̐̎͑̾̅̀̒̓̎̐̍̽̈́̋̽̓̔̍͜͝





</zalgo>

As a new twist on the age-old Zalgo generation problem, your goal is to take a string and "compress" it into a single Zalgo character. You will write two programs, one which takes in a string of printable ASCII and outputs a single Zalgo character, and a second which takes in a single Zalgo character and outputs the original ASCII string.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ I think the most golfable solution will be to encode the input in unary and use a single combining mark. Is that what you're looking for? \$\endgroup\$ Jan 9, 2016 at 22:11
  • 1
    \$\begingroup\$ Maybe require the zalgo output to be shorter in some sense? \$\endgroup\$
    – xnor
    Jan 9, 2016 at 22:38
1
\$\begingroup\$

Sorting trains

This problem is based off of a solitaire card game called Calculation. You can play it here (highly recommended).

You are in charge of designing a train yard. At your junction, you have an In/Out track (queues) and Storage (stack). Train cars come in a random order; your job is to arrange them into 4 different ordered trains. Land is expensive, so we need you to minimize the amount of storage tracks we need.

Your rail car mover can only handle 1 train at a time, and move a car:

  1. In track -> Out track
  2. In track -> Storage track
  3. Storage track -> Out track.

Each Out Track needs the same 25 cars, each in a different order:

Track 1: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,0
Track 2: 2,4,6,8,10,12,14,16,18,20,22,24,1,3,5,7,9,11,13,15,17,19,21,23,0
Track 3: 3,6,9,12,15,18,21,24,2,5,8,11,14,17,20,23,1,4,7,10,13,16,19,22,0
Track 4: 4,8,12,16,20,24,3,7,11,15,19,23,2,6,10,14,18,22,1,5,9,13,17,21,0

We can use (nx+n) mod 25 to calculate ID of the xth car of the nth track.

Important notes:

  • Storage tracks can store as many cars as you want, but you can only remove the most recently placed car
  • Cars cannot be moved from one storage track to another
  • Your algorithm must be deterministic (it must do the same thing given the same input queue and the same number of storage stacks)
  • You may get into an impossible situation, where you end up not being able to order the trains. If that happens, try again with additional storage tracks.

Input:

Your input is a list of integers, where each integer is the ID of the train car.

Output:

You need to return a list of moves that sorts the cars into the Out tracks. A move looks like I->S1 or S1->O2, where I is the input track, S# is a storage track, and O# is an output track.

Scoring:

Your score is the total number of tracks you need for of all test cases (you can use a different number of tracks for each test case). Lowest score wins.

Test cases:

4,13,20,23,22,21,0,18,8,17,16,6,18,22,15,19,21,8,6,24,7,21,9,4,24,19,0,20,12,1,3,10,5,6,19,23,17,9,14,24,13,5,10,15,2,14,7,8,6,10,3,18,22,16,2,4,10,14,1,21,11,9,22,18,20,16,1,4,12,0,12,11,20,11,19,12,0,13,9,11,23,24,15,3,14,5,2,5,8,7,7,3,16,13,15,23,17,1,2,17
1,8,7,5,6,7,21,9,15,5,7,6,21,13,13,18,16,12,22,10,18,14,13,14,10,0,8,24,13,23,2,9,3,4,19,11,24,16,15,10,8,22,3,2,16,17,1,2,12,18,19,2,19,22,0,23,12,24,11,23,23,3,21,15,0,16,14,5,17,10,20,20,0,15,6,7,20,11,17,22,6,17,5,9,1,8,14,21,4,4,3,11,12,4,20,19,1,18,9,24
21,2,14,11,12,21,15,21,16,23,2,19,8,14,23,0,16,4,7,9,24,10,0,11,17,5,4,8,10,0,20,6,5,18,18,6,9,10,22,10,9,1,16,22,1,22,6,17,19,7,2,1,7,18,3,18,11,2,11,7,23,17,6,3,19,13,21,4,20,14,24,20,15,15,15,13,13,12,22,5,13,20,24,3,24,23,4,0,9,8,5,17,16,8,14,12,3,19,1,12
2,7,10,22,15,3,16,7,3,6,4,17,2,20,6,21,13,5,1,7,16,18,24,17,8,14,5,23,17,18,13,0,9,14,24,21,19,23,0,20,15,1,12,24,3,18,11,5,15,7,4,4,9,8,17,12,0,23,6,8,14,12,1,22,9,11,14,20,19,3,12,23,11,19,16,11,22,16,9,4,13,19,1,22,15,2,8,10,0,13,10,18,24,10,21,6,5,2,21,20
14,20,18,21,19,10,7,16,2,22,14,15,17,24,8,10,13,0,11,5,11,11,7,13,19,9,22,10,7,0,3,16,2,8,21,8,4,14,2,19,24,16,12,1,0,0,17,15,1,21,6,5,4,6,12,23,3,15,21,2,12,23,14,23,5,1,10,1,17,13,7,22,4,5,18,6,18,12,16,11,9,13,6,19,23,15,17,22,4,20,8,3,18,20,24,20,9,24,3,9
0,23,4,4,14,17,14,0,8,21,8,9,8,5,16,20,15,9,24,23,12,11,24,2,14,17,3,21,1,19,5,17,15,16,7,2,22,20,6,1,24,16,7,22,21,19,6,13,23,11,4,11,15,19,20,19,18,5,1,18,10,22,16,6,18,20,10,9,6,2,12,23,7,12,3,9,10,7,5,10,13,3,17,12,13,2,1,0,15,4,22,18,11,14,3,24,21,8,0,13
8,19,19,0,23,7,10,21,2,22,13,20,2,10,16,21,3,17,20,18,5,9,14,19,22,0,7,6,3,10,18,6,6,5,24,2,11,24,7,1,11,17,8,9,24,5,15,18,16,24,11,5,14,1,0,13,16,0,13,17,8,12,4,1,21,20,11,10,14,16,8,21,4,7,17,9,13,4,1,3,15,6,22,23,9,23,15,12,15,19,3,20,2,23,12,12,4,18,22,14
17,3,8,24,18,5,7,2,13,2,9,19,21,6,8,8,21,16,17,3,11,20,24,24,12,11,18,11,16,15,24,9,14,10,18,4,22,20,0,10,7,14,6,1,15,6,13,7,3,12,7,23,4,21,0,23,2,10,12,22,9,17,0,4,4,3,22,16,23,20,15,18,10,8,23,1,14,11,5,19,16,1,2,22,9,12,1,5,13,19,14,20,19,5,13,0,15,6,21,17
\$\endgroup\$
0
1
\$\begingroup\$

Let's play Ticket to Ride!

(Note, this challenge was inspired by the board game Ticket to Ride, but is massively simplified to a graph-searching problem).

For this challenge, you have a list of cities (nodes), connections (edges), and tickets ([City, City, Point] tuple). You also have a limited number of trains, where each connection takes exactly 1 train to fill. For each ticket you complete (there is a filled-in path between the two cities), you get the ticket's point value.

Your goal is to maximize the number of points you get. For example, given the following graph:

A-B-C-D

and two tickets [(A,B)=>1, (B,D)=>2], and 2 trains, then you should output (B,C), (C,D) as that gives you a total of 2 points, because you have created a path from B to D, which matches the second ticket.

Everybody will be working on the same large graph and set of tickets, so your score is the score of your solution. Your solution is a list of filled connections (not the code that generated them, although your code should be included).

\$\endgroup\$
9
  • \$\begingroup\$ This is very unclear. "tickets (point value to make a path between two cities)" sounds like you need to have that many points in order to create an edge, then you say "Your goal is to maximize the number of points you get"... but you don't describe how you get points. And then "you should output (B,C), (C,D) as that gives you a total of 2 points": how does (B,C), (C,D) give you points? \$\endgroup\$
    – msh210
    Jan 15, 2016 at 18:17
  • \$\begingroup\$ @msh210 is that better? \$\endgroup\$ Jan 15, 2016 at 18:52
  • \$\begingroup\$ 1. To check I've understood: there's a sense in which what we have isn't a list of edges but a list of potential edges, and we have to choose n edges from those listed to create an actual graph on which reachability analysis will be performed? 2. Is there any reason to think that the answers won't all be optimal? \$\endgroup\$ Jan 15, 2016 at 19:35
  • \$\begingroup\$ @PeterTaylor 1. correct. I'll make that clearer. 2. I believe that the optimal solution requires a massive big O, but I may be wrong. \$\endgroup\$ Jan 15, 2016 at 19:39
  • \$\begingroup\$ @NathanMerrill, yep! \$\endgroup\$
    – msh210
    Jan 15, 2016 at 19:42
  • \$\begingroup\$ At the moment there's no runtime restriction preventing people from using an algorithm which considers every n-element subset of the edges. \$\endgroup\$ Jan 15, 2016 at 19:44
  • \$\begingroup\$ @PeterTaylor When I post the challenge, I'm going to be including a single, large test case. A submission will simply be a list of connections, not the program that generated them (although the program would certainly be nice) \$\endgroup\$ Jan 15, 2016 at 19:48
  • 1
    \$\begingroup\$ If answers don't have to include code (or at least pseudo-code), the question is off-topic on this site. \$\endgroup\$ Jan 15, 2016 at 20:00
  • \$\begingroup\$ What about this challenge: codegolf.stackexchange.com/questions/52496/… \$\endgroup\$ Jan 15, 2016 at 20:05
1
\$\begingroup\$

Risk dice battle

Risk is a board game in which you attempt to conquer the world by attacking your opponents' countries. As the game progresses the number of armies involved in attack gets higher and higher, which can lead to a lot of dice rolling. I want you to make this easier for me. It's possible that my favourite answer will actually get used when playing Risk.

Rules of Risk battles

Each country in Risk must have at least one army on it. Therefore a battle can only take place if the attacker has more than one army (in case he loses.) The defender obviously has at least one army.

The attacker rolls 3 dice (only 2 if he has only 2 armies) while the defender rolls 2 dice (only 1 if he has only 1 army.) Once the dice are rolled, the highest dice of each player are compared, then the next highest. (If one player rolled more dice than the other, his lowest dice are discarded.)

For each dice comparison, the player with the lower score loses an army. If the dice are the same, the defender wins and the attacker loses an army. Note that this does not necessarily put the attacker at the disadvantage, as he frequently has more dice to roll than the defender.

Example:

               Attacker 6 3 2
               Defender 5 4
                        ^ ^
                        | |
 Defender loses 1 army -+ +-Attacker loses 1 army

For interest the probabilities are as follows:

                        Defender rolls 2 dice       Defender rolls 1 die
                        --------------------------------------------------- 
Attacker rolls 3 dice   Attacker loses 2 29.26%     Attacker loses 1 34.03%
                        Both lose 1      33.58%     Defender loses 1 65.97%
                        Defender loses 2 37.17%

Attacker rolls 2 dice   Attacker loses 2 44.83%     Attacker loses 1 42.13%
                        Both lose 1      32.41%     Defender loses 1 57.87%
                        Defender loses 2 22.76%

Task

A full program is required which will accept from stdin or commandline, a number of attacking armies and a number of defending armies. There will be at least 1 army of each. Your code will display the number of armies as follows

1.If there is only 1 attacking army, your program shall immediately terminate with the message Insufficient force.

2.The code shall now accept a user input from stdin. If the user now enters anything other than an empty string, the code shall terminate. If the user enters an empty string, you must simulate the roll of the appropriate number of dice, sort each player's dice in descending order, and report the result and the updated number of armies per example below. 2 trailing newlines are required after the output.

Attacker dice: 5 3 1
Defender dice: 5 4

Attacker: p armies (where p is the number of attacking armies)
Defender: q armies (where q is the number of defending armies)
(2 trailing newlines)

3.If either player now has 0 armies, display the message Defender defeated! or Attacker defeated! as appropriate and terminate the program. Similarly, if the attacker now has only 1 army, terminate with the message Insufficient force.

The program shall now loop back to step 2 and continue until either one player's armies are depleted or the user enters a non-empty string.

Rules

The distribution of the dice throws shall be exactly as with real dice (up to the limits of uniformity both the dice and the random number generator used.) It is expected that most submissions will generate the numbers for each die and then sort them. Clever submissions that generate the output in other ways avoiding the sorting step are acceptable, but the theoretical probability distribution of the output must be identical to the real dice throws. (For example it is permissible to precalculate and presort all 216 possible throws of 3 dice and select one of these at random.)

Due to the real time nature of the application a full program is required, with input from stdin (enabling the user to run quick fire battles by reviewing the output and pressing the return key.)

Formatting of output strings and newlines shall be exactly as described above. Up to 2 additional symbols (but not alphanumerics) are acceptable between and around numbers. For example [3,2,1] is an acceptable way of displaying the roll of 3 dice.

Scoring

This is code golf. Shortest code in bytes wins.

(example output to be added)

\$\endgroup\$
4
  • \$\begingroup\$ I don't see the point of requiring termination on a nonempty string. \$\endgroup\$
    – lirtosiast
    Jan 18, 2016 at 3:18
  • \$\begingroup\$ @ThomasKwa An attacker doesn't always want to fight to the death, especially if he has a run of bad luck with the dice. The user experience is designed to make attacking as easy as possible but there has to be a way to terminate. The alternative would be ctrl z or ctrl c which is ugly. If you mean you don't see the point of termination on the first iteration, well that is partly to enable implementation with a while loop but mainly to enable the attacker to change his mind right up to the last minute. \$\endgroup\$ Jan 18, 2016 at 8:21
  • \$\begingroup\$ Oh, okay. I wasn't used to seeing practical concerns on code golf questions. \$\endgroup\$
    – lirtosiast
    Jan 18, 2016 at 17:51
  • \$\begingroup\$ Your description of the number of dice rolled by the attacker doesn't seem to match the official rules. You say "The attacker rolls 3 dice (only 2 if he has only 2 armies)", but the rules say "You, the attacker, will roll 1,2 or 3 red dice: You must have at least one more army in your territory than the number of dice you roll". (There's also the subtle issue of choosing to roll fewer dice than the maximum because you want to keep more than one army behind). \$\endgroup\$ Jan 23, 2016 at 19:16
1
\$\begingroup\$

Help find Mersenne primes!

There has recently been a discovery of a new prime number: 2^74207281-1. This is the biggest prime number to date and broke the previous 3-year record holder by over 4 million digits!

Your job will be to help mathematicians find some prime numbers (not really). You must take in an integer N and output the Nth Mersenne prime (OEIS A000668). You may assume that the Nth Mersenne prime is under your languages maximum integer number and/or will not cause an overflow (but your code should work for higher numbers if your language allowed it. You may not use any built ins for primality testing and cannot hard-code any values.

You can find a list of most of these numbers over here.

Test Cases

2 -> 7
5 -> 8191
8 -> 2147483647

This is , shotest code in bytes wins.

\$\endgroup\$
4
  • \$\begingroup\$ Please don't call it GIMPS XD. \$\endgroup\$ Jan 21, 2016 at 4:51
  • 1
    \$\begingroup\$ 1. Yes, that's the wrong sequence. It's actually A000668. 2. The current wording of the overflow assumption seems to allow hard-coding 4 values if your language operates purely on bytes. I also see no restriction on built-in primality testing. \$\endgroup\$ Jan 21, 2016 at 9:15
  • \$\begingroup\$ I've been thinking about "code-golf or fastest-code". As code-golf it's a loop with multiplication by two and a primality test, and primality testing has been done to death. As fastest-code, it would pretty much be a case of simplifying the GIMPS client to something which could be posted. I suggest that you make it a compromise: code-golf, but with a speed constraint which rules out naïve primality testing. Maybe write a Lucas-Lehmer test in a slow language, take the highest value it can do in 6 seconds, and require answers to reach that value in 1 minute. \$\endgroup\$ Jan 21, 2016 at 21:15
  • \$\begingroup\$ Somehow failed to find it when I searched before, but this question is related. \$\endgroup\$ Jan 24, 2016 at 23:08
1
\$\begingroup\$

Parse an "Efficient" Encoding

Let us define a fictitious encoding "ENCWID", that follows this general form: there are three bits that denote the length of the following character, for each character. This looks something like this:

WWWN..N
   ^^^^--- the actual character
^^^------- width bits; from 000 to 111

Perhaps this is a little vague. To understand this better, let us encode the string "Hello!" into ENCWID. Observe:

H   72   1001000
e   101  1100101
l   108  1101100
o   111  1101111
!   33   100001

This diagrams the binary ASCII codes of each character in the string. Let us put these values into an array that represents "Hello!": [1001000,1100101,1100101,1100101,1101111,100001]. The widths for each of these strings are 7, 7, 7, 7, 7, and 6 respectively. To binary, this makes 7 111 and 6 110. Now, we put the binary length of each binary ASCII code before the actual ASCII code, and combine them all into a single string, as such:

111-1001000 111-1100101 111-1101100 111-1101100 111-1101111 110-100001
(7)-(  H  ) (7)-(  e  ) (7)-(  l  ) (7)-(  l  ) (7)-(  ᴏ  ) (6)-(  !  )

(Spaces, hyphens, and parentheses added for visual clarity.)

And thus, the encoding of "Hello!" is 11110010001111100101111110110011111011001111101111110100001.

Decoding the string form is perhaps rather easy, using the following steps:

  1. Read three characters; call this N.
  2. Set N to the decimal number represented by N, from binary.
  3. Read the next N charcters; call this S.
  4. Parse S as a binary number, and append this character to the result.
  5. If there are still unread characters, go to step 1. Otherwise, continue.
  6. Return the result.

Objective Your objective is to write two programs; one that encodes and one the decodes the described encoding. Your score is the sum of the program's byte count.


Implications

Suppose that we can actually implement this in mainstream use; then, an encoding can be used that utilizes the lower-width codepoints for the most common letters in a given language. This would allow for a lesser amount of bits to convey the same message.

Say we did this for English, and that this

earniol1t.9h0s,dC()u2Scmy8gBJDW7HvM6RbkA435wfLPGpTKEFNYO
zI'Vq/Ux-[]jZ"  ;:QX&!

is the approximate frequency at which english letters occur, this could be our (partial) encoding:

   0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
0     e  a  r  n  i  o  l  1  t  .  9  h  0  s  ,
1  d  C  (  )  u  2  S  c  m  y  8  g  B  J  D  W
2  7  H  v  M  6  R  b  k  A  4  3  5  w  f  L  P
3  G  p  T  K  E  F  N  Y  O  \n z  I  '  V  q  /
4  U  x  -  [  ]  j  Z  "  \t ;  :  Q  X  &  !  \

Thus, "Hello!" would be encoded as:

H   12   18   10010     (5 => 101)
e   01   01   1         (1 => 001)
l   07   07   111       (3 => 011)
o   06   06   110       (3 => 011)
!   4E   78   1001110   (7 => 111)

101-10010 001-1  011-111 011-111 011-110 111-1001110
(5)-( H ) (1)(e) (3)-(l) (3)-(l) (3)-(o) (7)-(  !  )

=> 1011001000110111110111110111101111001110
(²7ß{Î, under ISO-8859-7 encoding)

And, "Hello!" fits into a clean 5 bytes under this encoding, as opposed to 6-byte standard encoding. This would equate to a lot more bytes saved for a higher sample size.



Meta

Suggestions?

\$\endgroup\$
2
  • \$\begingroup\$ 1. The introduction talks in terms of bits, but the description of decoding talks in terms of characters. Which is it? 2. If it's bits, how is padding to an exact multiple of 8 bits handled? (Or to an exact multiple of some other word size, if the storage/transmission model isn't based on octets). 3. With respect to the implications, see Huffman encoding and arithmetic encoding, which do the same thing better. \$\endgroup\$ Jan 23, 2016 at 18:56
  • \$\begingroup\$ @PeterTaylor 1. Bits, I will revise. 2. I don't know much about this stuff; this really isn't an implementation as it is an interpretation. 3. I didn't claim that this was the best way. >_<. I know of both mentioned. \$\endgroup\$ Jan 23, 2016 at 19:02
1
\$\begingroup\$

Language Guessing

(Inspired by What's the Language?)

According to the first Google result, the most popular programming languages are:

  1. Java
  2. C++
  3. C#
  4. Python
  5. PHP

(For our purposes, C and C++ will both be treated as C++, though the test cases may include C source code and header files)

Your Task

Write a function that accepts a String, determines what programming language the String is, and returns its result.

Rules

  • The input String will be in one of the five languages listed above.
  • Your method should return a String with the name of the programming language exactly as written above.
  • Your code must be under 150 bytes.
  • No compiling, running, or otherwise evaluating the test cases to determine their language.
  • No standard loopholes.

Scoring

  • The code with the highest match percentage wins
  • For every 15 bytes under the 150 byte limit, you get an extra percentage point (a 61-75 byte program would get 5% extra on top of the match percentage.
  • The method or function header does not count toward the total byte count. Return statements do count, however.
  • The code used to load the test cases and feed them into your method does not count either.
  • You get one import for "free". Any other imports count toward the byte limit.

Test Cases and Testing Code

Here is sample java code used for testing submissions. If you write in a language besides java, your tester must only accept one parameter, and cannot access any variables that are stored between iterations of the function. The entire code, including the tester, must be included in your answer.

import java.util.*;
import java.io.*;

public class Tester{

    static int right = 0;//How many are right
    static int total = 0;//How many tested in all

    public static void main(String[] args){

        //Opens up test cases
        File rootFolder = new File("./Test Cases");
        File[] subFolders = rootFolder.listFiles();

        HashMap<File, String> fileList = new HashMap<>();

        //Add all files in a subfolder to a HashMap and associate them with the language
        for(File currentFolder : subFolders){
            if(currentFolder.isDirectory()){
                for(File currentFile : currentFolder.listFiles()){
                    fileList.put(currentFile, currentFolder.getName());
                }
            }
        }

        //Iterate through files
        fileList.forEach((File f,String lang)->{
            System.out.print("Testing " + f.getName()+"\t");

            try{
                //Get contents of file
                BufferedInputStream input = new BufferedInputStream( new FileInputStream(f));
                Scanner sc = new Scanner(input);
                sc.useDelimiter("\\Z");
                String contents = sc.next();

                //Call compute method and store result
                String result = compute(contents);

                //Increment counters
                if(result.equals(lang))
                    right++;
                total++;

                System.out.println("Guess: " + result +"\tActual: " + lang);
            } catch(IOException e){
                System.out.println("There was an error when reading the file");
            }
        });

        //Print out final results
        System.out.println("Right: " + right);
        System.out.println("Total: " + total);
        System.out.println("Percent: " + (double)right * 100.0 / total + "%");
    }

    public static String compute(String c){
        //YOUR CODE HERE
    }
}

The test cases consist of 500 code samples (100 from each language) from around the internet (mostly github). Specific locations can be found in Credit.txt in the Test Cases folder.

The test cases can be downloaded here.

\$\endgroup\$
8
  • \$\begingroup\$ If you don't want to limit it to Java, don't enforce the submission tester. Most languages aren't too hard to test, with the exception of TinyMUSH. \$\endgroup\$
    – Riker
    Jan 24, 2016 at 1:16
  • \$\begingroup\$ @RikerW I made the wording a bit more language neutral. \$\endgroup\$
    – Daniel M.
    Jan 24, 2016 at 1:27
  • \$\begingroup\$ Why do we need a tester at all? Can't we just test it manually? \$\endgroup\$
    – Riker
    Jan 24, 2016 at 1:30
  • \$\begingroup\$ How else would you run through a few hundred test cases \$\endgroup\$
    – Daniel M.
    Jan 24, 2016 at 1:32
  • \$\begingroup\$ @Downgoat's was a special case, normally there aren't that many test cases. There should only be like 10 different cases, and that should cover most of it. \$\endgroup\$
    – Riker
    Jan 24, 2016 at 1:33
  • \$\begingroup\$ The number of test cases will vary widely with the challenge. Depending on the length of the code samples in this challenge, I can imagine a fairly large number of test cases being used to give a demanding challenge. \$\endgroup\$ Jan 28, 2016 at 18:52
  • \$\begingroup\$ If the test cases are provided as a list of inputs and a list of outputs, would that allow for easy testing in any language? Simply automate the running of the candidate answer against every input, giving a list of outputs, and then compare that with the target list of outputs. \$\endgroup\$ Jan 28, 2016 at 18:54
  • \$\begingroup\$ The test cases are a bunch of files of each programming language. They are sorted into subfolders with the name of the language the example is written in. The tester loads each file, gets the language based on the subfolder's name, puts the whole file into a string, and feeds it to the method. It compares the returned value to the subfolder's name. This way, to add or change test cases, it's a matter of dropping additional files into a folder, or dropping in a folder to add a new language. \$\endgroup\$
    – Daniel M.
    Jan 28, 2016 at 19:03
1
\$\begingroup\$

Semaphore Decoder

You are to write a program which can decode ASCII semaphores. Each semaphore fits in a 3x2 grid, with the flagger's head represented by a o (which is always in the upper middle square), and his flags represented by _ | / \. Each block is separated by one blank column. Text may continue onto additional lines if it gets too long. The letters look like the following format:

[Space]  o   A  o  B _o  C \o  D |o  E o/  F o_  G o   H _o  I \o  J |o_
        | |    /|     |     |     |    |     |     |\    /      /       

K  o|  L  o/  M  o_  N  o   O _o\  P _o|  Q _o/  R _o_  S _o   T \o|
  /      /      /      / \                                  \

U \o/   V |o   W /o_  X o/  Y \o_  Z o_
            \           \             \

To keep your messages from being observed by spies, your code must be as short as possible.

Example:

Input

_o| _o_ _o\  o   o   o_  o_ \o   o   o   o  _o| \o/  o_  o_  o/  o/ _o   o
             |\ /|  /   /    /  / \  |\ | |           \   \ /    |    \ | |
 o   o  |o   o  \o  _o\ |o   o/  o   o   o/ _o\  o/  o_
/|  / \  |  | |  |       |   |  | |  |\ /       /    |

Output

PROGRAMMING PUZZLES AND CODE GOLF
\$\endgroup\$
8
  • \$\begingroup\$ Essentially the opposite of this encoder -- codegolf.stackexchange.com/q/3628/42963 \$\endgroup\$ Jan 25, 2016 at 21:06
  • \$\begingroup\$ @TimmyD - I saw that. In fact I deliberately chose a different format (3x2 instead of 3x3) so that you couldn't just use the same code in reverse. I think the bonuses will also make this a bit more interesting, since some signals have multiple meanings, and you need to keep a stack to handle the Error code. \$\endgroup\$ Jan 25, 2016 at 21:14
  • 2
    \$\begingroup\$ -1 for bonuses \$\endgroup\$
    – user45941
    Jan 26, 2016 at 8:42
  • \$\begingroup\$ @Mego - Is it the idea of bonuses that offends you? Or is the scoring just not balanced? I think the bonuses are what make this challenge the most interesting. Would it help if I were to make them requirements instead? \$\endgroup\$ Jan 26, 2016 at 14:35
  • 1
    \$\begingroup\$ @DarrelHoffman The linked post explains fairly well why I am strongly against bonuses. The biggest issue I have is that n bonuses require people to solve the problem 2^n different ways, and look for the best score. The bonuses add unneede complexity, and detract from the actual challenge. \$\endgroup\$
    – user45941
    Jan 26, 2016 at 20:31
  • 3
    \$\begingroup\$ If you think the bonuses make it more interesting, make them requirements. \$\endgroup\$ Jan 26, 2016 at 21:37
  • \$\begingroup\$ What I don't get is - I've seen dozens of challenges that had one or more bonuses, and I've never seen a complaint about them until now. I guess I could see how it affects some languages more than others, but it's not like there's actual prize-money going out for these things. It's more just a matter of having fun and practicing code-fu. I'm just afraid that having those bonuses as a requirement might scare off some people from even trying. But without them - is this even much of a challenge for the veterans out there? \$\endgroup\$ Jan 26, 2016 at 21:56
  • 1
    \$\begingroup\$ @DarrelHoffman Bonuses on challenges used to be rarer. Then people started putting bonuses on everything, with severely detracted from challenge quality. So, in response, the community decided (in the post I linked) that bonuses shouldn't be used unless you have a really strong justification for including them. 9 times out of 10, the challenge would be vastly improved by making them requirements or discarding them outright. \$\endgroup\$
    – user45941
    Jan 27, 2016 at 1:53
1
\$\begingroup\$

Pixel "Density"

In this challenge, we will be viewing each pixel in an image as a particle with two properties:

(1) vertical density (vd)

(2) horizontal density (hd)

These two properties are determined by the RGB values of the pixel in the following manner:

vd = Red - Blue

hd = 128 - Green

We call a sorted image an image that satisfies the following conditions:

For each pixel:

  1. no pixel to the right has a lower hd

  2. no pixel to the left has a higher hd

  3. no pixel above has a higher vd

  4. no pixel below has a lower hd

The challenge is to produce such sorted images.

Input

An image in any "common, recognizable" format, via file or stdin.

Output

A sorted image in a "common, recognizable" format (not necessarily the same format as input) containing exactly the pixels of the original , via file or stdout.

Relevant Details:

  • This is .

  • alpha values (if they exist) are ignored.

  • Libraries may be used, but size must be added to your score

  • "common, recognizable" formats will be determined by the community. I don't expect this to be an issue, but if you feel the the loose wording is being exploited, downvote the answer (or even better, help me fix it before the challenge goes live. I don't really want to enumerate the allowed formats, but maybe that is a better option?).

If there is interest in the question, I will create a reference implementation as well as test cases.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ I don't think this specific task is a dupe - the closest that comes to mind involves doing the same transformation but on colours represented as hex strings rather than on the actual bytes. However, this is pretty much "Look up one value i in an array; then loop applying A[i++]^=255 until the end of the array. Adding alpha makes it slightly less boring, but not much. \$\endgroup\$ Jan 23, 2016 at 13:29
  • \$\begingroup\$ @PeterTaylor You were right about it being extremely boring, I've reworked the challenge considerably. I hope this is more interesting. \$\endgroup\$
    – Liam
    Jan 23, 2016 at 23:28
  • \$\begingroup\$ There seem to be 2 separate tasks here: 1. the pixel sorting. 2. processing bmp files. Do you want the file processing to be part of the same challenge? Otherwise you could allow any recognised freely available image format. For example, I would expect code to process a ppm file to be considerably shorter than code to process a bmp file. \$\endgroup\$ Jan 28, 2016 at 18:35
  • \$\begingroup\$ Relevant meta answer \$\endgroup\$ Jan 28, 2016 at 18:45
  • 1
    \$\begingroup\$ @trichoplax good point. My original thinking was to discourage the use of libraries so I wanted to use the simplest format I could think of, which is bmp. I'll make changes. \$\endgroup\$
    – Liam
    Jan 28, 2016 at 18:48
  • \$\begingroup\$ changes made (for future readers of these comments) \$\endgroup\$
    – Liam
    Jan 28, 2016 at 23:52
1
\$\begingroup\$

Windows batch polyglot/hybrids challenge with any language possible /* I need some help to refine my challenge */

As the batch scripts are pretty limited, hybrid files that embed a code from another language into a batch file are used a lot lately.

Though usually there are some requirements for a good hybrid script:

  1. The embedded code should be usable as-it-is - without any ugly batch escaping sequences.
  2. There should not be redundant output. E.g. a lot of languages use /* */ for multi-line comments. If the batch script executes a line that starts with / * it will print an error message an will continue to the next line .Though it will allow you to hybridize C/C++/C#/Java/... with a batch file the error message cannot be surpassed so this will not count as a good hybrid.
  3. No temp files.It's easy to output a lot of code into a temp file that will be later executed , the IO operations will slow the script and on of the main advantages of batch scripting (the speed) will be lost. And more over is a challenging constraint. But this will be not possible for compiling languages and for extension sensitive languages.

Some examples will follow:

JScript (good for example as it comes with every windows installation) technique invented somewhere in the link by Tom Lavedas :

@if (true == false) @end /*
@echo off
cscript //nologo //e:javascript "%~dpnx0" %*
echo Output from the batch.
goto :EOF */

WScript.Echo('Output from the jscript.');

The output will be:

Output from the jscript.

Output from the batch.

The technique uses the JScript (javascript has no such thing) specific @ directives to make the code valid (or silent) both for both languages.

Another example (again with JScript) invented by Ryan Biesemeyer:

0</* :
@echo off
echo Output from the batch.
cscript /nologo /E:jscript %~f0 %*
exit /b %errorlevel%
*/0;

WScript.Echo('Output from the jscript.');

This time is used the redirection priority in batch scripts and 0</* : will be parsed as 0:</* .

Here are some info that can help you:

  • every line that starts with @ will be silent - even the invalid commands.
  • every line that starts with : will be taken as label in batch and will be not executed
  • every line that starts with something like <someWord : someWord will be silent because of redirection priority
  • every line that starts with something like digit<someWord : someWord will be silent because of redirection priority (this time the output will be redirected to a stream).In this case will be best to use 0
  • you can use <space><tab> ; , = at the beginning of every line - these will be ignored as standard delimiters in batch.Can be useful if some language use some of these as comment.
  • if you start a line with %not_existing_variable% it will be replaced with nothing.Could be useful if in some language comments start with percent.
  • If you finish a line with a caret ^ the next line will be appended at the end.With the caret in batch you can escape the new line.

here's a little bit more inspiration

And here's the challenge. Your script should be with .bat or .cmd extension . It should contain a code from another language - the code should be used by the second language as it is (no escapes symbols) .REPL tools are accepted with the condition of no escape symbols - except in the line where the REPL tool is invoked. There should not be redundant output. There should be not temp files (with the exception of compiling languages , and file extension sensitive languages - then the file should copy itself in the %TEMP% folder).

Each script should accept one command line argument which will be printed 5 (five) times . Both from the batch part of the code and from the second language prefixed by the language name (for the batch case it should be BATCH: for example.If the second language is Ruby it should be RUBY:)

For sure this will be not possible with every language , but for many it is achievable.

The winner should propose the most solutions with different languages (or if the language is the same a different kind of techniques should be used like in the two examples above).In case of equal number of solutions the first one wins.

\$\endgroup\$
1
\$\begingroup\$

Weekly Physics Golf #{TBD}: Wavelength of a Sound Wave

META NOTE: I believe, and others in the comments, that this challenge is quite trivial. So, I will be working on making this challenge harder in the next few days.

Introduction to the Series

Every week I will be posting a physics challenge. My goal here is to design challenges that in the end, teach some people some physics. Overall, the challenges will be very basic with little information. All of these challenges will have the minimal information necessary to solve them, and the goal is for users like you to do some research, watch some videos, and understand how these concepts work to teach you how to approach these types of physics problems and explain how they work. Of course, I will also give two optional hints per challenge, which are there if you do not have the time or determination to do the research, or you cannot figure out how to do the problem after researching. The two hints will be "necessary equations for this challenge" and "process to solve the problem". The hints are completely optional to use and it is encourages to not use them, but as stated above to learn the information for yourself. The series will have one main leaderboard. Whoever has the least combined byte count for all of the challenges gets a to be determined prize. Each challenge will range in difficulty, with an upwards trend of difficulty. I wish you all luck and I hope you learn a thing or two!

Challenge #{TBD}: Wavelength of a Sound Wave (Difficulty: EASY)

Many people may not know that sound is actually a wave, which would explain why it can go through objects and bend around corners. But it has some really interesting properties. For example, the speed of the sound wave changes from a few factors, all relating to the medium it travels through. In this challenge, you will have to figure out the wavelength of a sound wave through a given medium.

But first, lets define a medium. A medium is any liquid, solid, or gas that a wave can travel through. Mediums can affect the speed of a sound wave in two ways: the density of the medium, and the bulk modulus elasticity of the medium. But what are these two things? Well lets first consider the density of an object. Density is defined to be the mass divided volume of the object, or in simple terms, amount of mass in a given space. This is important, as waves travel differently through mediums of different densities. The reason behind this is that a medium with a higher density has more inertia (the resistance to change in motion). An object with a higher inertia will be more difficult to move with a wave (which displaces particles to move). Therefore, INCREASED DENSITY corresponds to DECREASED WAVE SPEED.

Now lets define bulk modulus elasticity. This is really just a fancy name for stiffness of an object. But what does this have to do with anything? Well, when an object is stiffer, each molecule is more interconnected to other molecules. And because a wave displaces particles to "move", it will move through a stiff medium faster because it can move larger molecules, hence moving more distance in a shorter time, a.k.a. moving faster. Therefore, INCREASED BULK MODULUS ELASTICITY corresponds to INCREASED WAVE SPEED.

So in this challenge, I will give you the density and the BME (bulk modulus elasticity) of the medium, and also the frequency of the sound wave. Your job is to use this information and output the wavelength. Here are the full specs:

  • Input will be three numbers (not necessarily integers). They correspond to density in kg/m^3, bulk modulus elasticity in Pascals, and sound wave frequency in hertz.
  • Input can be in any order, in any convenient format (so 12.3 45.6 78.9, [12.3 45.6 78.9], and 78.9,[12.3,45.6] are all acceptable).
  • You may assume that input will never cause any sort of error during execution.
  • Output will be the calculated frequency of the sound wave in meters, precise to three decimal places, omitting leading and trailing zeros. For example, inputs of 6, 27, and 3 would given an output of 0.707 after rounding from 0.70710678118654752440084436210485.
  • Shortest code in bytes wins!

Test cases

META NOTE: Test cases to come, I am working on them right now.

Hints

These hints are for those who do not want to put in the time and effort of research, or those who could not find a solution. So, here are the two hints:

Hint 1: Equations

You need the following equations for this challenge:

enter image description here

Hint 2: Sample Solution Process:

Using the two equations above, we can set them equal to each other to get:

enter image description here

Solving for wavelength gets us this equation:

enter image description here

From here you can just plug in values.

This is , so shortest code in bytes wins. Good luck!

Leaderboard

Meta note: blah blah blah, working leaderboard will eventually go here! This leaderboard will contain and combine scores for all of the weekly challenges. It will only be visible on this question, though.

\$\endgroup\$
5
  • \$\begingroup\$ Please tell me of any suggestions, I'll be happy to hear them. More importantly, please alert me of any mathematical inaccuracies and/or inaccurate explanations. \$\endgroup\$
    – GamrCorps
    Feb 2, 2016 at 2:25
  • \$\begingroup\$ +1 for the idea. I love learning new things! \$\endgroup\$
    – user81655
    Feb 2, 2016 at 12:20
  • \$\begingroup\$ But my concern with this challenge is that it's too simple and straight-forward. The shortest answer in every language would be something like (a,b,c)=>(b/a)**.5/c (except for Mathematica, it proabably has a built-in :P ). \$\endgroup\$
    – user81655
    Feb 2, 2016 at 12:20
  • \$\begingroup\$ I concur with @user81655, but I'm excited to see what you can come up with. \$\endgroup\$
    – lirtosiast
    Feb 2, 2016 at 18:05
  • \$\begingroup\$ @user81655 Yes, after further analysis I have realized how simple the problem is. I am currently working on an alternative challenge while I make this one more difficult. \$\endgroup\$
    – GamrCorps
    Feb 2, 2016 at 21:55
1
\$\begingroup\$

I've posted two well-received (by my standards: 10+ no downvotes) questions in the past; however, I've always missed a bit of information, so I welcome all feedback to this challenge!

Introduction

A palindrome is a word or string of words that is the same forwards as it is backwards, e.g. taco cat, kayak, madam im adam. I'm sure by now you're all familiar with .

An anagram is a word or group of words that when the letters are rearranged, forms a different word or string of words. If you haven't already, Google for anagram or define anagram (not part of the puzzle, obviously).

Task

Your task is to write a program which will take a string of lowercase characters and blank space, and return truthy/falsey if the string can be anagrammed into (or is) a palindrome (even if it doesn't form a legit word). This is so shortest answer wins. Standard loopholes apply.

Input

  • A string of at least 1 character containing a mixture of lowercase alphanumeric characters and blank space
  • Whitespace can be ignored when determining whether a word or phrase can be anagrammed.

Output

Examples:

Truthy
kayak = kayak / akyka
maam = maam / amma
her taco cat hero = hertacoocatreh
boob = obbo
boobs = bosob
ooh = oho
lol = lol (already a palindrome)
zzz = zzz (already a palindrome)
i = i
00010001 = 10000001
0xd00000d = 0d00x00d0
sevens 7even = seven7neves
Falsey
glum glow worm
maam im adam
book
banana
nana ant
jquery

\$\endgroup\$
5
  • 1
    \$\begingroup\$ What whitespace characters can appear in the input? And the rule that "anagrammed into a palindrome" requires the palindrome to be distinct from the original string, even if that were itself a palindrome, should be mentioned in the task description, not hidden in the examples. \$\endgroup\$ Feb 3, 2016 at 14:26
  • \$\begingroup\$ Thanks for your feedback: I removed the unnecessary "palindrome must be unique from original" requirement, and clarified whitespace. \$\endgroup\$
    – Tas
    Feb 3, 2016 at 21:12
  • \$\begingroup\$ I actually thought that the requirement to be different to the original string, while needing to be stated clearly because it was unexpected, made the question more interesting. Without that requirement the test is just that there's at most one non-whitespace character which occurs an odd number of times. Although I suppose that with a permutation operator the difference isn't that big. \$\endgroup\$ Feb 3, 2016 at 21:24
  • \$\begingroup\$ Not quite: na na na na can be anagrammed into the palindrome nanaanan and it only contains characters with even counts. \$\endgroup\$
    – Tas
    Feb 3, 2016 at 21:47
  • 1
    \$\begingroup\$ I said "at most one", not "exactly one". \$\endgroup\$ Feb 3, 2016 at 22:27
1
\$\begingroup\$

Maximum cover time ratio

Given an undirected graph and a start node, there is an expected number of steps to reach all possible nodes if you walk at random. This expected number of steps will depend on which node you start from. For a given graph and starting node, let us call the number of steps to visit all nodes in the graph the cover time. We can estimate the cover time by just setting off 1000 walks and taking the average.

You can also set off two independent random walks from the same node at once and see how many steps it takes for every node to be visited by at least one of the walks. Clearly you can do this with more than two as well. Let us call the expected number of steps to reach each node with at least one of k random walks starting from the same node, the k-cover time. We can see that cover time = 1-cover time.

Task

Write code that explores different undirected graphs, starting nodes and values of k and computes both the cover time and the k-cover time for each. You should use at least 1000 random walks to estimate the time to reach all nodes. The goal is to maximize the expected cover time ratio explained below.

Output

Your code should output a single graph in any sensible format you choose, the value k, the identity of a starting node, the cover time and the k-cover time.

Score

Your score will be cover time from your given starting node divided by k times k-cover time starting from the same node.

Languages and libraries

You can use any language or library you like (that wasn't designed for this challenge). However, for the purposes of scoring I will run your code on my machine so please provide clear instructions for how to run it on Ubuntu.

My Machine The timings will be run on my machine. This is a standard Ubuntu install on an 8GB AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code.

Details

  • I will kill your code after 2 minutes unless it starts to run out of memory before then. Your code should therefore output something before 2 minutes is up.

Any help with finishing this question would be gratefully received. I think it just needs examples and test cases and maybe a picture or two.

\$\endgroup\$
8
  • \$\begingroup\$ Shouldn't the k-cover time be the same as the cover time by the central limit theorem? \$\endgroup\$ Feb 4, 2016 at 16:26
  • \$\begingroup\$ @PeterTaylor Maybe my definition is confusing but you can explore a city more quickly with two people rather than one. Similarly, you would expect to explore a graph more quickly with two random walks rather than one. The number of steps is measured until every node has been visited by at least one random walk. \$\endgroup\$
    – user9206
    Feb 4, 2016 at 16:39
  • \$\begingroup\$ Aha. I think the at least one belongs in the definitional statement: "expected number of steps to reach each node with at least one of k random walks starting from the same node". Have you done any testing on small cases to see whether there are easy unbounded solutions or easy bounds? \$\endgroup\$ Feb 4, 2016 at 19:57
  • \$\begingroup\$ What's the input to the program going to be? \$\endgroup\$
    – feersum
    Feb 5, 2016 at 3:14
  • \$\begingroup\$ @feersum There wasn't going to be any input in a similar fashion to codegolf.stackexchange.com/questions/65876/… . \$\endgroup\$
    – user9206
    Feb 5, 2016 at 6:17
  • \$\begingroup\$ I'm pretty sure you can actually solve this problem analytically as questions like those are known under the name Markov Chains. You can e.g. calculate the expected number of steps from A to B by making B absorbing, and calculate the expected number of steps to absorbtion. \$\endgroup\$
    – flawr
    Feb 5, 2016 at 21:45
  • \$\begingroup\$ @flawr That would be very interesting. As I can't I hope an expert can comment on this. \$\endgroup\$
    – user9206
    Feb 5, 2016 at 21:47
  • 1
    \$\begingroup\$ I'm not very fluent anymore but I'm going to reread some of this which I found very helpful in the past. \$\endgroup\$
    – flawr
    Feb 5, 2016 at 22:22
1
\$\begingroup\$

Show me your OOP

Your task is to implement OOP that have this feature:

  1. Inheritance (Single dispatch)
  2. Class

Your submission have to translate this pseudo-code into your languages:

class Animal{
    Animal(string name){
        printLn("An animal has summoned " + name);
    }
    public void sound();
}
class Sheep extends Animal{
    bool woolstate;
    Sheep(bool state){
        woolstate = state;
    }
    public void sound(){
        printLn("Mbaaaa\n");
    }
    public void growWool(){
        woolstate = true;
    }
    public void getWool(){
        if(woolstate == true){
            printLn("Mbaaaa\nget " + (new Math.Random()).getInt(0, 10).toString() + " bags of wool");
            woolstate = false;
        }
    }
}
class Worm(){
    Worm tails;
    public int numbers;
    public Worm(int number, int length){
        if(length != 0){
            tails = new Worm(number, length-1);
        }
        numbers = number;
        if(number == length){
            this.privateMethod
        }
    }
    public Worm getTails(){
        return this.tails;
    }
    public Worm setTails(Worm tail){
        this.tails = tail
    }
    public Worm getNumbers(){
        return this.numbers;
    }
    public Worm setNumbers(int number){
        this.numbers = number
    }
    public void sound(){
        printLn("Doesn't sound");
    }
    private void privateMethod(){
        printLn("This is a private method");
    }
}
int main(){
    Sheep a = new Sheep(true);
    Animal b = new Sheep(false);
    Worm c = new Worm(5, 5);
    b.sound();
    a.sound();
    b.getWool(); //Error
    a.getWool();
    if(c.getNumbers()==5){
        c.setNumbers(6);
    }
    b=c.getTails();
    b.setNumber(7); //Error
    b.sound();
}

If the random function is not available, you can deterministically return anything from 0 into 10.

The submission should be scored based on:

  1. Difficulty of implementation (i.e. how far is the language from OOP?)
  2. Ease of usage of implemetation
  3. Efficiency of implementation
  4. The pleasantness of syntax
\$\endgroup\$
2
  • \$\begingroup\$ This could be a potential challenge! However, it could use more objective criteria, as popularity-contests are now generally frowned upon here. For example, what prevents me from posting a 0-byte C#/Java/C++/etc. answer, and claiming that it implements OOP? (Also, some languages don't have a random feature for the Sheep.getWool() function.) Also, we apparently need an interface feature as well, for Animal.sound(), and is the Sheep constructor supposed to call the Animal constructor? If so, you forgot to call it with a name. \$\endgroup\$ Feb 7, 2016 at 12:42
  • \$\begingroup\$ @LegionMammal978 What is your suggestion \$\endgroup\$
    – Xwtek
    Feb 8, 2016 at 11:58
1
\$\begingroup\$

Prove that this program terminates or run forever

Introduction:

Halting problem has been shown to have no complete algorithm. Yet it is important to understand what the program does and verifying the program if the program matches with its specification

Challenger

Challenges

Your challenge is to write program that takes no input in given language (so no obscure language is used) and a formal proof that the program is halting or run forever. Output will be ignored.

Rules

  1. Proof must be written formally.
  2. No computer aided proof. (i.e. running the program, or convert it into Coq, Idris, or another dependent-typed language)
  3. This is not challenge, so do not obscure the program.
  4. If your program is not cracked after 6 days, then you must give the proof whether your program halts or not. It is then verified.
  5. Your program should not depend on unsolved problems.
  6. Cracking your own submission is not allowed.
  7. Score for submission:
    • Cracked : -5
    • Verified : 10
    • Flawed : -15

Prover

Challenges

Your challenge is to proof that the program that is posted in Challenger thread is halting or run forever.

Rules

  1. Proof must be written formally.
  2. No computer aided proof. (i.e. running the program, or convert it into Coq, Idris, or another dependent-typed language)
  3. Score for submission:
    • Verified (With no proof from owner) : 8
    • Verified (With flawed proof from owner) : 12
    • Flawed : -8

Sandbox Question

What language should I use? The requirement is:

  1. Turing Complete
  2. Imperative
  3. Easy to understand, even to noncoder
  4. Easy to write

Also, I need help with the leaderboard

\$\endgroup\$
6
  • \$\begingroup\$ Why is the downvote? \$\endgroup\$
    – Xwtek
    Feb 8, 2016 at 13:41
  • \$\begingroup\$ as i understand it, the robber doesn't actually write any code, huh? \$\endgroup\$ Feb 8, 2016 at 15:09
  • \$\begingroup\$ @undergroundmonorail I don't know which from Prover and Challenge is the robber? \$\endgroup\$
    – Xwtek
    Feb 9, 2016 at 3:55
  • 1
    \$\begingroup\$ This is unfeasible. If I write a program that stops when it disproves the Goldbach conjecture, no one here (including me) is going to know if it stops or loops forever (without becoming instantly world famous). \$\endgroup\$ Feb 9, 2016 at 13:15
  • \$\begingroup\$ @Calvin'sHobbies You have to provide proof after 6 days. If not, the submission will not be safe and you will not get score at all. \$\endgroup\$
    – Xwtek
    Feb 9, 2016 at 13:19
  • 1
    \$\begingroup\$ It becomes really a question of who can find the most obscure mathematical result which can be translated into code rather than a programming contest per se. \$\endgroup\$ Feb 9, 2016 at 14:34
1
\$\begingroup\$

Continue the sequence

As we all know, there are a lot of integer sequences in the world. What if we could create one program to figure out the next few items in any given sequence? That would be pretty cool, right? Well, I'm pretty sure we can't create a program that does every sequence, but we can at least do most of the simple ones.

Challenge

Your challenge is to create a program or function that takes in 5 integers in any reasonable format (array, string, separate arguments, etc.), and returns/outputs the next 5 integers in the sequence.

Rules

  • Your submission must be deterministic; that is, the output should be the same every time for the same input.
  • You may not use a built-in for determining the next items. (cough Mathematica cough)

Scoring

To score a submission:

  1. Take the value of each single output integer minus the expected output.
  2. Take the square root of the absolute value of each of these.
  3. Take the average of the result and add one.
  4. Multiply your byte count by this number.

For example, if the only test case were 1,2,3,4,5 => 6,7,8,9,10, and your 15-byte submission outputs 6,7,8,10,6, your score would be:

1,2. abs(6 - 6) = 0, sqrt(0) = 0
     abs(7 - 7) = 0, sqrt(0) = 0
     abs(8 - 8) = 0, sqrt(0) = 0
     abs(10 - 9) = 1, sqrt(1) = 1
     abs(7 - 10) = 4, sqrt(4) = 2
3.   0 + 0 + 0 + 1 + 2 = 3
     3 / 5 = 0.6; 0.6 + 1 = 1.6
4.   15 bytes * 1.6 = 24

Thus, your score would be 24.

Lowest score wins.

Test cases

2,2,2,2,2 => 2,2,2,2,2
1,2,3,4,5 => 6,7,8,9,10
109,117,125,133,141 => 149,157,165,173,181
1,2,4,8,16 => 32,64,128,256,512
1,10,100,1000,10000 => 100000,1000000,10000000,100000000,1000000000
1,2,3,5,8 => 13,21,34,55,89
2,1,3,4,7 => 11,18,29,47,76
1,3,6,10,15 => 21,28,36,45,55
1,4,9,16,25 => 36,49,64,81,100
8,7,6,5,4 => 3,2,1,0,-1
1,0,1,0,1 => 0,1,0,1,0
1,2,3,2,1 => 2,3,2,1,2
512,256,128,64,32 => 16,8,4,2,1
1,11,111,1111,11111 => 111111,1111111,11111111,111111111,1111111111
1,21,321,4321,54321 => 654321,7654321,87654321,987654321,10987654321
1,2,6,24,120 => 720,5040,40320,362880,3628800

I will create a GitHub Gist with all of the test cases before posting.

Sandbox questions

Currently, I'm looking for suggestions for:

  • a better name
  • more tags
  • more sequences

Feel free to post any other questions/notes you have.

1 This will be replaced with the actual number of test cases when this is posted.

\$\endgroup\$
15
  • \$\begingroup\$ Why the 100 byte limit? \$\endgroup\$
    – nimi
    Feb 10, 2016 at 20:45
  • \$\begingroup\$ @nimi The goal is to correctly predict as many sequences as possible while keeping the code fairly short. Does 100 bytes sound too short? \$\endgroup\$ Feb 10, 2016 at 20:47
  • 2
    \$\begingroup\$ ... well, 100 bytes of Pyth aren't 100 bytes of Java. Wordy languages will be quite handicapped. \$\endgroup\$
    – nimi
    Feb 10, 2016 at 20:51
  • \$\begingroup\$ @nimi True. How might I be able to fix this? \$\endgroup\$ Feb 10, 2016 at 20:51
  • \$\begingroup\$ Classical bonuses (although discouraged now) work better when relative compared to absolute. Maybe something like byte count * (2 - percentage solved), i.e. 2x bytes if 0%, 1x bytes if 100%, lowest score wins. But somehow we must prevent trivial answers like outputting the constant string 0 0 0 0 0 for 2x9 = 18 bytes. \$\endgroup\$
    – nimi
    Feb 10, 2016 at 21:00
  • 5
    \$\begingroup\$ Sequences are pretty arbitrary, so I'm having trouble seeing how this could go well. I get the feeling most submissions will just end up hardcoding in a set number of patterns, eg geometric progression, polynomial interpolation, and ignore ones which are too complex, eg Golomb. Also, standard loophole, but it might be worth mentioning explicitly that looking up things on, eg OEIS, is not okay. \$\endgroup\$
    – Sp3000
    Feb 10, 2016 at 21:48
  • \$\begingroup\$ @Sp3000 You have a good point there. What would you think about A) choosing a select number of sequence types, B) choosing a select number of types and making it code-golf, or C) just choosing a single type to focus on? \$\endgroup\$ Feb 11, 2016 at 16:11
  • \$\begingroup\$ I had a think about this, and I think what this challenge might need is 1) A fairly large test-battery covering a large variety of sequence types (e.g. OEIS), and 2) A tweak to the scoring system which takes into account how far off a number is (since getting 0 points for a guess that's just off by 1 seems a bit harsh). Just a thought though. \$\endgroup\$
    – Sp3000
    Feb 14, 2016 at 4:11
  • \$\begingroup\$ Regarding your options, I'm not a great fan of C since it changes the challenge completely, and might need dupe checking. There's no real need to limit the number of sequence types I think, as long as there's an incentive to be close with the guess rather than dead on. \$\endgroup\$
    – Sp3000
    Feb 14, 2016 at 4:12
  • \$\begingroup\$ Perhaps make it a [test-battery] with lots of test cases. That seems like the best way to score these types of languages. You may also want to disallow built-ins as I know Mathematica has a built-in to do this \$\endgroup\$
    – Downgoat
    Feb 15, 2016 at 17:09
  • \$\begingroup\$ @Sp3000 Yes, those are some very good thoughts. This is now a test-battery challenge, and the new scoring algorithm takes into account both the byte-count and the average of the sqrt-distances of the outputs. Does this seem like a decent way to score this challenge? \$\endgroup\$ Feb 15, 2016 at 18:02
  • \$\begingroup\$ @Downgoat This is now a test-battery challenge, and built-ins have been banned. Thanks! \$\endgroup\$ Feb 15, 2016 at 18:02
  • \$\begingroup\$ @nimi The scoring system has been completely rewritten. \$\endgroup\$ Feb 15, 2016 at 18:06
  • \$\begingroup\$ With respect to limiting the types of sequence, you need to be careful not to turn it into a dupe of codegolf.stackexchange.com/q/3485/194 \$\endgroup\$ Feb 15, 2016 at 19:09
  • \$\begingroup\$ @PeterTaylor Thanks, I'll keep that in mind. \$\endgroup\$ Feb 15, 2016 at 19:48
1
\$\begingroup\$

Compress by Replacement

You are to take an input string, and then turn it into another string with a list of replacements which would turn this new string into the input string. The catch is that you must output the smallest such alternate string + list of replacements you can.

The input string will be restricted to the following characters (Please note there is a space at the end and that semicolons are not allowed):

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:<=>?@[]^_`{|}~ 

The way the output is formatted is

CompressedString;tofind;toreplace;tofind;toreplace;...

An example output is 111222;1;abcd;2;efgh which outputs abcdabcdabcdefghefghefgh

The replacement rules are applied in the order they are shown in the output to avoid ambiguity.

Therefore, if one were to input abcdabcdabcdefghefghefgh (which has a length of 24). Then the output would be 111222;1;abcd;2;efgh with a length of 20 which is the shortest possible output for this input

Some other notes:

  • The replacement rules are restricted to the same character set that the input has. This means that if the input contained every possible letter except for the character h, then your replacement rule would only work if the tofind part of the rule is h
  • There may be situations where the input string is the shortest possible output, this is fine
  • The program doesn't have to be computationally efficient, as long as it does calculate the correct answer when it finishes, then it is valid
  • There are also occasionally multiple correct answers, any solution which has the smallest possible count is valid and you only need to output one solution, not all the valid solutions
  • The semicolons are included in the character count for the output

Some test cases:

'abcdabcdabcdabcdefghefghefghefgh' -> '11110000;1;abcd;0;efgh' or '00001111;1;efgh;0;abcd'
'this is a test. this is a test.' -> '0 0;0;this is a test.'
'there is no shortening in this one' -> 'there is no shortening in this one'
'01001001010100101010110101010101010110101010' -> '202030321332130;3;222;2;01' or '22331131210113;3;212;2;010' or '22212233230132;3;121;2;010' or '223233133301132;3;21;2;010' or '222323133310133;3;12;2;010' or '020203031332132;3;222;2;10'

This is codegolf, so shortest answer in bytes wins

Sandbox notes:

  • This takes a long time to brute force for anything longer than 40 characters with repeated substrings, so it may take a while for brute forced solutions to verify they are correct. Because of this, I was thinking this question might be better proposed as a "best algorithm" kind of puzzle to see who can make the best algorithm. What do you think?
  • Should I allow people to choose what delimiter is used to separate the output? Ideally what would happen is that they would just say 'I am assuming that , is not used and it is my delimeter for the output'.
  • Am I being too strict on the output? The aim was that you are trying to compress it only via replacements, and as a result want to output those replacements as short as you can, which this format is the smallest you can make.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 1. I don't understand what you mean by "The replacement rules are restricted to the same character set that the input has", even with the explanation. 2. A simplified version of this problem is NP-complete, so I'm not sure what "best algorithm" winning criterion you could use. 3. It would be good to have a test case where all optimal answers have a tofind which is more than one character (ensuring that answers solve the problem stated, not just that simplified version). \$\endgroup\$ Feb 17, 2016 at 16:40
  • \$\begingroup\$ Seems possible if you limited to a couple replacements. Otherwise, maybe a code challenge/fastest code version? \$\endgroup\$ Feb 17, 2016 at 18:44
  • \$\begingroup\$ 1. What i mean is, that the rules: 1;abcd;2;efgh for example, must only contain characters which were allowed in the input. So you can't use weird unicode characters or things to replace 2. I'd not heard of the simplified version of this problem. In fact I think that this may be more efficient, because some rules which may be valid in that problem would not be valid due to having to factor in the additional length of the semicolons, and 3. I don't believe I have such a solution available, maybe none exist like that? \$\endgroup\$ Feb 18, 2016 at 4:17
  • \$\begingroup\$ I think algorithm is a no-go from Peter's response since it does seem to be NP complete, maybe I could restrict it to be at most 3 replacements as per Michael Klein's suggestion \$\endgroup\$ Feb 18, 2016 at 4:20
1
\$\begingroup\$

Wring the changes

I want to ring Stedman Doubles, but I'm lazy so I want to get to a particular change and back as quickly as possible.

Change-ringing is essentially an enumeration of permutations of a set of small integers. To make the enumeration ringable, no bell can move more than one step in each permutation. A change therefore consists of some or all of the bells swapping places with adjacent bells.

Consider the case of five bells. Before changes start, the bells are rung in ascending numerical order, known as Rounds, which would be 12345. A typical change would then consist of leaving one bell in the same place while a double swap occurs between the remaining four bells, thus the name "Doubles". The bell that remains in the same place serves to notate the change. Note that this refers to the bell currently in that position, rather than the bell with that number.

In the case of Stedman the full notation is 3.1.5.3.1.3.1.3.5.1.3.1. If you repeat those 12 changes five times you will enumerate 60 changes before returning to Rounds. The first few changes are as follows:

[12345 Rounds]
 21354 (1,2 and 4,5 swap)
 23145 (1,3 and 5,4 swap; 2 was 1st so doesn't move)
 32415 (2,3 and 1,4 swap)
 23451 (3,2 and 1,5 swap; 4 was 3rd so doesn't move)

There are of course 120 permutations of five bells, so in order to access the other 60 changes, or simply for variety, Stedman allows for every sixth change to be altered by a call known as a Single, which causes the two bells currently in position 4 and 5 to stay in the same place instead of exchanging as they would normally do.

A touch is described by a sequence of letters describing whether each sixth change is Plain or a Single. It ends when it returns to Rounds, which need not be after a multiple of six changes, but it may not repeat any change, so 120 is the longest possible length of a touch of Stedman Doubles. For instance, a complete extent of all 120 changes could be rung using the touch PPPPPPPPPSPPPPPPPPPS.

Your challenge is to write a program or function that will calculate the shortest touch that includes a given change. Your input should be the change (you can expect it to be a valid change) as a string, and your output should be (in either order) the touch description (as a string of P and S characters) and also the number of changes (including the final rounds, so up to 120).

The score for this challenge shall be the length of your program, plus the lengths of the touches it finds for the following inputs:

13524
14235
14253
43215
53124

The Batch script @echo 120 PPPPPPPPPSPPPPPPPPPS would therefore score 630.

\$\endgroup\$
3
  • \$\begingroup\$ This could use a little background information. Ideally, the challenge should be self-contained and understandable by somebody who does not know what Stedman Doubles or change ringing is (such as myself). \$\endgroup\$
    – Dennis
    Feb 17, 2016 at 17:04
  • \$\begingroup\$ So in essence, we have a highly structured digraph of 60 vertices (corresponding to the order-60 group generated by P and S, which I assume is A5 but haven't checked); each of the 120 edges is labelled with 12 permutations (and each permutation therefore occurs on 12 edges, but symmetry), and we need to find the shortest cycle from 12345 which includes an edge labelled with the input permutation \$\endgroup\$ Feb 18, 2016 at 12:34
  • \$\begingroup\$ @PeterTaylor Close. You don't need a cycle as long as you reach the input permutation before you reach an edge labelled 12345 (or 12345 is labelled after the input on the same edge), and there are 4 generators as the meaning of P alternates between 42351 and 43152 and S between 42315 and 43125, so the group is generated by P1P2, P1S2, S1P2 and S1S2 (but I don't know what the group looks like, except that (P1P2)^5==I). \$\endgroup\$
    – Neil
    Feb 18, 2016 at 13:14
1
\$\begingroup\$

Implement floating-point square-root with integer addition, subtraction and bit-shifts only

Someone has broken your favourite language! Almost all arithmetic functions are now unusable. You've been left with integer addition, subtraction, bit-shifts (both left and right) and bitwise operators (AND, XOR, OR, NOT) only. If your language doesn't have bit-shifts you may substitute *2^i or /2^i for a cost of i each time. You need to write an efficient square-root function because it's been proven[citation needed] that every useful program uses square-root[dubious-discuss].

Your function will take one number (see format below), calculate its square-root and return the result. The last binary digit may either be consistently rounded down, or rounded to closest.

Rounding down:

...0(0)  ...0
...0(1)  ...0
...1(0)  ...1
...1(1)  ...1

Rounding to closest:

...0(0)  ...0
...0(1)  ...1
...1(0)  ...1
..01(1)  ..10, etc.

Scoring:

  • 1: Copy an integer (any length)
  • 2: Add or Increment
  • 2: Subtract or Decrement
  • 1: Greater-than, Less-than, Equal-to, etc.
  • 1: Check a bit
  • 1: Write a bit
  • 1: Bit-shift (left or right) by 1
  • 2: Bitwise operator (AND, XOR, OR, NOT)
  • n x (code + condition): Do-While
  • n x condition + (n - 1) x code: While (For can be implemented as While)
  • 0 (free): Jump to start or end of loop
  • 0 (free): Jump to start of function
  • 0 (free): Return from function

Since different languages use different number formats, the format used for scoring this challenge is as follows: 8 bits for the exponent, 32 bits for the mantissa. You don't have to use these lengths internally, just assume this is what it is for scoring purposes.

There will be no negative numbers or zero in the input, nor will you have to store a value of 0.0. Since the square root function always produces a number closer to 1, you don't need to worry about overflow or underflow. The Most Significant Bit of the mantissa will always be 1.

  • All floating point numbers will be stored and passed around as two unsigned integers, m and e
  • Bm and Be are the number of bits in m and e respectively
  • The value of the number is given by 2(e-Bm-2Be-1)m or 2^(e-Bm-2^(Be-1))*m
  • In your code Bm must be ≥ 32 and Be must be ≥ 8

The code will be scored assuming that Bm = 32 and Be = 8, so no penalty will be given if your code uses larger values.

 exponent   MSB          mantissa           LSB    decimal
[01111110] [10000000 00000000 00000000 00000000]   0.125
[01111111] [10000000 00000000 00000000 00000000]   0.25
[10000000] [10000000 00000000 00000000 00000000]   0.5
[10000001] [10000000 00000000 00000000 00000000]   1
[10000001] [10100000 00000000 00000000 00000000]   1.25
[10000010] [10000000 00000000 00000000 00000000]   2
[10000010] [11000000 00000000 00000000 00000000]   3
[10000011] [11100000 00000000 00000000 00000000]   7
[10000100] [10000000 00000000 00000000 00000000]   8
[10000100] [10010000 00000000 00000000 00000000]   9

Please include a version number for ease of reference. If you know the name of your method, please include it too, e.g. "Brute force", "Trial and error", etc. Increase the major number if your score changes, otherwise increase the minor number if your score is the same, e.g:

v1.0: Perl, Brute force - 108
v1.1: Perl, Brute force - 108
v1.2: Perl, Brute force - 108
v2.0: Perl, Brute force - 95
v2.1: Perl, Brute force - 95
v3.0: Perl, Brute force - 93

This is not , so you will be scored on the efficiency of your algorithm. If more than one answer is equally efficient, the oldest one will be in the lead. If editing your answer reduces your score, it also resets your time. The time is taken from your last minor version 0.


I'll probably need some fair test values that don't allow tuning for specific numbers.

Thoughts?

\$\endgroup\$
13
  • \$\begingroup\$ The nested superscript/subscript is hard to read. Can you pull out the offset? \$\endgroup\$ Feb 16, 2016 at 13:07
  • \$\begingroup\$ Someone has broken your favourite language \$\endgroup\$
    – wizzwizz4
    Feb 16, 2016 at 15:03
  • \$\begingroup\$ @wizzwizz4 Cute! The difference is that now your job is to fix it afterwards! \$\endgroup\$
    – CJ Dennis
    Feb 17, 2016 at 1:57
  • \$\begingroup\$ Thanks @PeterTaylor. Do you have any other suggestions? Does my scoring seem balanced? Have I forgotten any operations that might be needed? I've never done a fastest-algorithm challenge before so I want to make sure it is good. \$\endgroup\$
    – CJ Dennis
    Feb 17, 2016 at 2:12
  • \$\begingroup\$ Do X without Y challenges are generally frowned upon \$\endgroup\$
    – user45941
    Feb 17, 2016 at 4:01
  • \$\begingroup\$ @Mego This isn't always bad, "Do X without Y" can be good questions. Do you think this challenge isn't "meaty" enough? Please don't pigeon-hole it with a broad generality if you don't have specific gripes. If you think the entire concept is flawed, please clearly explain why. \$\endgroup\$
    – CJ Dennis
    Feb 17, 2016 at 4:22
  • \$\begingroup\$ @CJDennis I never said that I thought the challenge was flawed. I just wanted to point out that challenges of this type are generally frowned upon, and thus you may face some resistance/downvotes with this one. \$\endgroup\$
    – user45941
    Feb 17, 2016 at 4:24
  • \$\begingroup\$ @Mego OK. Understood. This is why I've posted it to the Sandbox first. I've had an upvote and no downvotes so far, and while no-one's said "This is brilliant!" no-one's panned it either. Any suggestions you have for improving it/making it more user friendly are welcome! \$\endgroup\$
    – CJ Dennis
    Feb 17, 2016 at 4:31
  • \$\begingroup\$ Is the unusual exponent bias intentional? What rounding is permitted? It's probably worth explicitly stating that since sqrt is always nearer to one, there's no need to worry about underflow or overflow in the output. \$\endgroup\$ Feb 17, 2016 at 6:53
  • \$\begingroup\$ That floating-point format looks suspiciously like that on the ZX81, which is convenient, as I actually wrote a fast floating point square root for it. If only I could remember it. \$\endgroup\$
    – Neil
    Feb 18, 2016 at 13:29
  • \$\begingroup\$ @PeterTaylor Are you saying the bias is strange because it doesn't have a -1? This is intentional as I believe it will make some methods easier without penalising others. \$\endgroup\$
    – CJ Dennis
    Feb 19, 2016 at 0:48
  • \$\begingroup\$ @Neil The format is based on the Amstrad CPC (but not identical), so I wouldn't be at all surprised if the format was similar or identical to the ZX81 (both using Z80 CPUs). As I remember a lot of software was easily ported between them. \$\endgroup\$
    – CJ Dennis
    Feb 19, 2016 at 0:51
  • \$\begingroup\$ I wasn't thinking it through enough. The -Bm is because of the implicit binary point in the explanation I'm more used to seeing. Ignore that point. \$\endgroup\$ Feb 19, 2016 at 6:39
1
\$\begingroup\$

xkcd's Fast Bogosort

This xkcd comic presents pseudocode for four very bad sorting algorithms: halfhearted merge sort, fast bogosort, job interview quicksort, and panic sort. Because the other three are too easy, impossible to decipher, or a danger to users, you'll be implementing fast bogosort.

Your code will take an array of positive integers in any convenient format, and will return or output the result of fast bogosort as defined below.

Let N be the binary logarithm of the length of the list, rounded to the nearest non-negative integer. Shuffle the list randomly N times. After each shuffle, if the list is fully sorted, return the result.

If no value has yet been returned, return the exact string Kernel Page Fault (Error Code: 2).

The output of your code must match the expected probabilities of this algorithm exactly, but does not need to follow the explicit steps stated.

Test cases

In the format Input -> Output (Probability)

[] -> Kernel Page Fault (Error Code: 2) (1)
[1] -> Kernel Page Fault (Error Code: 2) (1)
[1, 1] -> [1, 1] (1)
[1, 2] -> [1, 2] (1/2)
[1, 2] -> Kernel Page Fault (Error Code: 2) (1/2)
[1, 1, 1] -> [1, 1, 1] (1)
[1, 1, 2] -> [1, 1, 2] (5/9)
[1, 1, 2] -> Kernel Page Fault (Error Code: 2) (4/9)
[3, 2, 1] -> [1, 2, 3] (11/36)
[3, 2, 1] -> Kernel Page Fault (Error Code: 2) (25/36)
[8, 4, 2, 1] -> [1, 2, 4, 8] (47/576)
[8, 4, 2, 1] -> Kernel Page Fault (Error Code: 2) (529/576)
[7, 7, 7, 7, 7, 7, 7, 7] -> [7, 7, 7, 7, 7, 7, 7, 7] (1)

Meta

Any bad math in here? Any other good test cases I should add?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 1. The requirement to "match the expected probabilities of this algorithm exactly" needs to be relaxed slightly because most systems don't have perfect RNGs. 2. If you're allowing built-in sorts, the only interesting part is rounding the logarithm. And that's really the only difference to the bogosort question, so it's quite likely to be closed as a dupe. \$\endgroup\$ Feb 20, 2016 at 10:28
1
\$\begingroup\$

Remove Vowel

There is a word puzzle called Enter Vowel which looks a little like a crossword but the clues are simply the answers with all the vowels removed.

Your task will be to take a solved crossword and turn it back into the Enter Vowel clues. You can assume that the crossword consists of upper case letters, octothorpes and newlines. You can also assume that the crossword will be rectangular and that only octothorpes will appear on its borders.

The first step is of course to obscure the letters. Each letter should be replaced by a space, except those letters that begin a word, which should be replaced by an underline. Each underline is notionally numbered starting from 1.

To the right of the obscured grid you must then provide separate columns of across and down clues, but both sets of clues share the underline numbering, so that the numbers are not consecutive within each list of clues. The clues are simply the original words with the vowels removed.

Example:

###############
###PROGRAMMING#
###U####N######
###Z##CODE#####
###Z###########
#GOLF##########
###E###########
###S###########
###############

becomes

############### ACROSS      DOWN
###_    _     # 1. PRGRMMNG 1. PZZLS
### #### ###### 3. CD       2. ND
### ##_   ##### 4. GLF
### ###########
#_   ##########
### ###########
### ###########
###############

Extra whitespace is permissible as long as the general formatting is adhered to.

This is , so you need to remove as much code as you can.

\$\endgroup\$
4
  • \$\begingroup\$ The example given includes a full border of one line of #s. Can answers assume that this border will always be included? \$\endgroup\$ Feb 22, 2016 at 11:05
  • \$\begingroup\$ @PeterTaylor Unless you can suggest nicer ASCII or Unicode art to represent a crossword, then yes, I think the input should always have the border. \$\endgroup\$
    – Neil
    Feb 22, 2016 at 11:12
  • \$\begingroup\$ Then please make that explicit in the question, because it simplifies the answers. \$\endgroup\$ Feb 22, 2016 at 12:06
  • \$\begingroup\$ @PeterTaylor I also added that it will always be rectangular, because I wasn't sure that was sufficiently obvious. \$\endgroup\$
    – Neil
    Feb 22, 2016 at 13:35
1
\$\begingroup\$

Untangle the footnote labyrinths

enter image description here

Challenge

Your challenge is to create a program or function that untangles footnote labyrinths.

Input

The input will be made up of two parts:

  • A "main" string
  • A list of footnotes in the format (1. Footnote text)

Output

The output should be the "main" string with each footnote mark (represented with superscript tags <sup>1</sup>) replaced with its corresponding footnote. Examples:

This is some sample text.<sup>1</sup>
1. This is a sample footnote.

The "main" string has one footnote <sup>1</sup>; the 1 is replaced with the text of the footnote:

This is some sample text.<sup>This is a sample footnote.</sup>

Here's another one:

This is some sample text.<sup>1</sup>
1. This is a footnote.<sup>2</sup>
2. This is a nested footnote.

This time, the footnote has a footnote mark in it, which should be replaced as well:

This is some sample text.<sup>This is a footnote.<sup>This is a nested footnote.</sup></sup>

One more example:

Welcome to my lair!<sup>8</sup><sup><sup>3</sup></sup>
3. This footnote is not inserted.

Footnote 3 is inserted, but footnote 8 does not exist, so it's not modified:

Welcome to my lair!<sup>8</sup><sup><sup>This footnote is not inserted.</sup></sup>

You may assume:

  • Nested footnotes are not represented as <sup>1<sup>2</sup></sup>; rather as <sup>1</sup><sup><sup>2</sup></sup>.
  • There will be no circular references, i.e. 1. Abc<sup>1</sup> or 1. Abc<sup>2</sup> 2. Xyz<sup>1</sup>
  • The footnote numbers will only be 1 through 9.

You may not assume:

  • The footnote numbers will be consecutive, or in order. 2. Abc 1. Xyz and 9. Qwerty 4. Asdf are both valid.

Test cases

(One or more lines of input, empty line, output. Feel free to suggest a better format.)

This is some sample text.<sup>1</sup>
1. This is a sample footnote.

This is some sample text.<sup>This is a sample footnote.</sup>

_____________________________________________________________________

This is some sample text.<sup>1</sup>
1. This is a footnote.<sup>2</sup>
2. This is a nested footnote.

This is some sample text.<sup>This is a footnote.<sup>This is a nested footnote.</sup></sup>

_____________________________________________________________________

Studies have shown<sup>1</sup> that PPCG users are more likely to accept typos<sup>3</sup> than the correct spelling<sup>4<sup>5</sup></sup>.
1. Studies by an individual research group, not affiliated with PPCG in any way.
3. https://github.com/vihanb/PPCG-Design/pull/50
4. http://strawpoll.me/6847681/r
5. Very comprehensive studies.<sup>1</sup>

Studies have shown<sup>Studies by an individual research group, not affiliated with PPCG in any way.</sup> that PPCG users are more likely to accept typos<sup>https://github.com/vihanb/PPCG-Design/pull/50</sup> than the correct spelling<sup>http://strawpoll.me/6847681/r<sup>Very comprehensive studies.<sup>Studies by an individual research group, not affiliated with PPCG in any way.</sup></sup></sup>.

_____________________________________________________________________

Welcome to my lair!<sup>It's very cozy.</sup>
1. This footnote is not inserted.

Welcome to my lair!<sup>It's very cozy.</sup>

_____________________________________________________________________

Welcome to my lair!<sup>8</sup><sup><sup>3</sup></sup>
3. This footnote is not inserted.

Welcome to my lair!<sup>8</sup><sup><sup>This footnote is not inserted.</sup></sup>

This is code-golf, so shortest code in bytes wins.

\$\endgroup\$
4
  • \$\begingroup\$ Zgarb had a challenge that was either this or the exact opposite transformation. I'll try to look it up later. \$\endgroup\$ Feb 22, 2016 at 17:43
  • \$\begingroup\$ Ah yeah, the opposite. \$\endgroup\$ Feb 22, 2016 at 18:48
  • \$\begingroup\$ @Martin Interesting. Would that have any bearing on this challenge being a duplicate? \$\endgroup\$ Feb 23, 2016 at 2:24
  • \$\begingroup\$ No, it wouldn't. \$\endgroup\$ Feb 23, 2016 at 7:45
1
\$\begingroup\$

How long until a five-card-stud poker winning hand?

Background:

Five card stud is a variant of poker where the player is dealt a hand of five cards from a shoe of multiple standard 52-card decks. This hand is then used for play/scoring, following the table listed below.

{insert chart of poker hands}

We're going to play a variation of this as follows: The dealer selects five cards out of the shoe as the Hand to Beat. The dealer then shuffles all the remaining cards, and deals the player five cards. If the player wins, the game is over, else the player's cards are shuffled back into the shoe and the process repeats. We want to determine the expected number of hands that will need to be dealt before the player has a hand that will beat the dealer.

Challenge:

Given an input of the dealer's full five-card hand, and the number of decks in the original shoe, output the expected number of games before the player will have a hand that beats the dealer's.

Input:

  • A positive integer, 0 < n < 6 representing how many decks are in the shoe.
  • A numerical or string representation of the dealer's full five-card hand. You're allowed to choose the representative encoding, and the input format, but please specify that in your answer. Examples could be 3H 2C KC QH JD for a card-value/suit combination, or assign each card a numerical value from 1 to 52 (such as Ace of Spades = 1, Two of Spades = 2, ... King of Hearts = 52). Your choice.

Output:

  • A single numeric value representing the expected number of hands that need to be dealt before the player is dealt a winning hand.

Examples:

to be expanded

1 "2H 3C 4S 5C 7H" >
5 "22 33 45 17 8" >

Meta Discussion:

Related (abandoned) challenge - Generate random 7-carded poker hand for a given hand type

Since the related challenge isn't exactly a duplicate, I don't think the below apply, but I'll link them here for discussion purposes:
Duplicates with different restrictions or no restrictions
Is it OK to copy a question if the old one is long dead?
Can we make use of abandoned sandbox posts?
Closing old question as duplicate of a new one

\$\endgroup\$
1
\$\begingroup\$

Traffic Light Simulator 2016

In this challenge, you are in charge of all of the traffic lights in a busy city. It is your goal to move the traffic as efficiently as possible.

Definitions:

City: Everything you control. Contains a 10x10 square grid of intersections. All adjacent intersections are connected via roads, and intersections on an edge have 1 outside connection (2 on corners)

Tick: Measures time. For the first 10,000 ticks, 10 cars will span. The simulation ends after all cars have left the city.

Road: Moves cars from one intersection to another (or an outside connection). Roads have a length (in ticks).

Intersection: 12-way intersection. Connects 4 roads together, and allows cars to move from one road to one of the other 3. Only 1 car per direction can travel through at a time.

Traffic Light: Allows/Prevents cars from crossing an intersection. There are 12 lights (one for each direction) at each intersection. Lights can only be green (allows traffic) or red (prevents traffic). If a light is green, then any intersecting paths must have been red for at least 3 ticks.

Intersecting paths: Paths that cross or meet assuming right-side traffic. The following graph indicates when two paths intersect given your direction and the other lanes' directions.

Your        Left  Right Across
Direction  |L|R|A|L|R|A|L|R|A 
------------------------------
Left       |X   X|X   X|  X X
Straight   |X   X|X X X|X    
Right      |    X|     |X    

Car: Starts at a random outside connection, and travels the shortest path to another random outside connection. After reaching its destination, adds 1.05^(TravelDuration) to your score.

Outside connection: Has a Busyness, and spawns cars. The chance of an outside connection being randomly chosen is Busyness/Sum(Busyness of every connection)

Your goal:

I have provided a controller that will simulate the cars and the cities. You need to provide a function that returns a list of [x,y,Direction] tuples that indicates which lights you would like to toggle. Attempting to turn a green light with intersecting green lights will turn the intersecting lights red, and turn the light green after 3 turns.

After the simulation has run, your score is the sum of all cars' scores, lowest score wins.

\$\endgroup\$
2
  • \$\begingroup\$ Did anything ever come from this? This seems like it could be a fun challenge. \$\endgroup\$
    – nedla2004
    Feb 25, 2018 at 17:18
  • \$\begingroup\$ No. I'm not convinced that there are actually interesting solutions to be had, and the controller isn't trivial to write. If you want to take this challenge, feel free :) \$\endgroup\$ Feb 26, 2018 at 2:16
1
\$\begingroup\$

How Many Laps?

I was at my taekwondo training last night and the first thing we do when we start is a ~5 min jog around the gym to get warmed up. The problem is as follows. We run around the edge of the gym, everyone starting from wherever they like, and everyone jogs at a slightly different speed, so there is a lot of awkward passing as no one wants to have to ruin their flow by changing speed. So i started wondering, how many times will each person be overtaken?

The Question

Given a square of side lengths 15m, and a person starting at each corner of the square, running at speed n (m/s) how many times will each person be passed by someone else during a 5 min jog?

Input/Output

  • Input should take the form of 4 values that represent each persons average running speed( Assume their speed remains constant) accurate to 3 decimal places. The range of the input may be (0,5]. Input may be seperated by commas or spaces i.e 4.123,2.122,3.145,1.445
  • Output should be printed as 4 integers representing the number of times each person was overtaken by someone else, given in the same order as the input was supplied.

Test Cases

The input 1.3334 2.5334 1.1344 2.8531 can be visually represented as follows

1.3334 ------------ 2.5334
   |                   |
   |                   |
   |                   |
   |                   |
   |                   |
 2.8531 ------------ 1.1344 

Each of the numbers in the corner of the square represents a jogger and their speed running in a clockwise direction(Clockwise because of the order of the input). After 5 mins of jogging, how many times will each jogger have been overtaken by everyone else?

The output for this case would be 13 1 14 0 This basically means the first person( top left corner) will be overtaken 13 times. The second person(top right) will be overtaken once. third person(bottom right, and the slowest jogger) will be overtaken 14 times. The fourth person( bottom left, and the fastest) will not be overtaken by anyone, as they are the fastest. Here are some more test cases

  • Input: 5.3334 1.5334 1.5334 0.8531 Output: 0 19 19 28
  • Input: 0.1334 1.5334 2.5334 3.8531 Output: 37 16 6 0

Rules

  • This is code golf, shortest working program in bytes wins
  • Must be a fully working program
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You should really add an example, since this is very hard to imagine in your mind. Also don't forget testcases! \$\endgroup\$
    – Denker
    Feb 25, 2016 at 7:48
  • \$\begingroup\$ Haha yeah i thought someone would say that! I'm currently trying a few ideas as im not sure how to solve this myself yet! Once i have a way, ill ad some test cases \$\endgroup\$
    – SoloKix
    Feb 25, 2016 at 8:16
1
\$\begingroup\$

The broken minus parser

Sam is trying to create a new programming language, but is having a lot of trouble getting the parser right. For example,

4--5

evaluates correctly to 4 - (-5) = 9, but

4-5

is giving a result of -20!

After doing some digging around, Sam realises that their parser's grammar is ambiguous. In fact, it's actually interpreting 4-5 as 4 (-5), multiplication (by juxtaposition) between two numbers!

Here's some example inputs and outputs, to get a feel for what the parser's doing woeful wrong:

Input             Calculation                 Output
7                 7                           7
-7                (-7)                        -7
8-3               8 (-3)                      -24
8--3              8 - (-3)                    11
-8-3              (-8) (-3)                   24
-8--3             (-8) - (-3)                 -5
-4-5-2            (-4) (-5) (-2)              -40
-4--5-2           ((-4) - (-5)) (-2)          -2
-4-5--2           (-4) ((-5) - (-2))          12
-4--5--2          (-4) - (-5) - (-2)          3
1-4-5-9           1 (-4) (-5) (-9)            -180
1-4--5-9          1 ((-4) - (-5)) (-9)        -9
1--4-5--9         (1 - (-4)) ((-5) - (-9))    20
1--4--5--9        1 - (-4) - (-5) - (-9)      19

To be a bit more explicit, here's the rules followed by the parser, in order:

  1. Multiplication by juxtaposition: If possible, split the input into two valid parts a, b such that a is as short as possible. Return evaluate(a) * evaluate(b).

  2. Subtraction: If the input is of the form a-b where a, b are two valid parts, return evaluate(a) - evaluate(b), taking the - such that b is as short as possible.

  3. Unary negation: If the input is of the form -a where a is valid and does not start with a -, return -evaluate(a). In other words, unary negation can only be applied once.

  4. Digit: If the input consists of a single digit, return the corresponding integer.

If an input string fails to satisfy any of the above conditions, it is invalid. For example, the following strings are invalid:

(empty)
-
7-
--7
8---3

The task

Given a valid string consisting of 0123456789-, output the result as interpreted by Sam's broken parser. Invalid input is undefined behaviour. You may assume the usual code golf defaults for input and output, e.g. programs and functions are both okay.

Sandbox notes:

  • I'll work on the algorithm description a bit later so it doesn't sound so much like "just implement this".
  • Will add more test cases later.
  • Should eval-like functions be allowed? I'm not sure how much they'd help here
  • With the current rules, 42 would evaluate to 4*2=8. Would it be preferable to state that input will never have two or more digits in a row?
\$\endgroup\$
3
  • \$\begingroup\$ Doesn't rule 1 already cause 42 to be evaluated as 4*2=8 by having precedence above rule 4? \$\endgroup\$
    – xnor
    Feb 26, 2016 at 5:25
  • \$\begingroup\$ @xnor Ah true, yes it does (updated). I'm still tossing up whether 42 should be a valid test case - I'm wondering if it might be more interesting golfing-wise if you only ever had single digits... \$\endgroup\$
    – Sp3000
    Feb 26, 2016 at 5:34
  • \$\begingroup\$ I think eval-like functions should be allowed because it disallowing doesn't add much to the challenge \$\endgroup\$
    – Downgoat
    Feb 28, 2016 at 2:17
1
\$\begingroup\$

What can I buy in Catan?

Catan is a board game where players collect 5 commodities: brick, lumber, wool, grain and ore.

You can trade commodities in the following ways:

  • you can always sell 4 of one kind to buy 1 of any other kind
  • if you have 3-for-1 trading possibility you can sell 3 of one kind to buy 1 of any other kind
  • if you have a given commodity trading possibility you can sell 2 of the given commodity to buy 1 of any other kind

You can use your commodities to buy 4 things:

  • road costs 1 brick and 1 lumber
  • settlement costs 1 brick, 1 lumber, 1 wool and 1 grain
  • city costs 2 grain and 3 ore
  • development card costs 1 wool, 1 grain and 1 ore

The same costs in matrix form:

 |blwgo
-+-----
r|11
s|1111
c|   23
d|  111

Your task is to find out which of the four things a player could buy given his/her commodities and trading possibilities.

Input

Output

Examples

This is code golf so the shortest entry wins.

\$\endgroup\$
1
\$\begingroup\$

Transpose a paragraph

For some odd reason I want to transpose paragraphs. The basic idea of a transpose is that this:

a b
c d

Is changed to:

a c
b d

[more on the rules here]

Examples

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer suscipit, arcu
ut facilisis blandit, neque tellus consequat urna, in semper mi purus vel magna.
Nam placerat mauris ac varius dictum. Nunc placerat ipsum et lectus iaculis
feugiat. Aenean eget felis ac purus fermentum dapibus ac nec leo. Vestibulum
convallis euismod metus a gravida. In eu nisl facilisis, accumsan urna a,
consectetur mauris. Integer vitae lectus et justo vestibulum lobortis. Donec
quis erat est. Curabitur pellentesque mi purus, vel posuere nunc volutpat quis.
Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia
Curae; Maecenas ultrices, elit sed finibus euismod, lacus tortor hendrerit
libero, quis auctor risus mi in tortor. Vivamus finibus consectetur est, quis
ultricies metus congue sit amet. Ut non elit libero. Fusce efficitur nec ante ut
tempor. Proin vitae commodo tortor. In aliquam massa a nulla eleifend commodo. 

Lorem      ut         Nam        feugiat.   convallis  consectetu quis       Vestibulum Curae;     libero,    ultricies  tempor.   
ipsum      facilisis  placerat   Aenean     euismod    mauris.    erat       ante       Maecenas   quis       metus      Proin     
dolor      blandit,   mauris     eget       metus      Integer    est.       ipsum      ultrices,  auctor     congue     vitae     
sit        neque      ac         felis      a          vitae      Curabitur  primis     elit       risus      sit        commodo   
amet,      tellus     varius     ac         gravida.   lectus     pellentesq in         sed        mi         amet.      tortor.   
consectetu consequat  dictum.    purus      In         et         mi         faucibus   finibus    in         Ut         In        
adipiscing urna,      Nunc       fermentum  eu         justo      purus,     orci       euismod,   tortor.    non        aliquam   
elit.      in         placerat   dapibus    nisl       vestibulum vel        luctus     lacus      Vivamus    elit       massa     
Integer    semper     ipsum      ac         facilisis, lobortis.  posuere    et         tortor     finibus    libero.    a         
suscipit,  mi         et         nec        accumsan   Donec      nunc       ultrices   hendrerit  consectetu Fusce      nulla     
arcu       purus      lectus     leo.       urna       volutpat   posuere    est,       efficitur  eleifend  
vel        iaculis    Vestibulum a,         quis.      cubilia    quis       nec        commodo.  
\$\endgroup\$
2
  • \$\begingroup\$ Where did "vel" (at the bottom of column 1 in your output) come from? \$\endgroup\$
    – msh210
    Feb 29, 2016 at 6:47
  • \$\begingroup\$ I'm not exactly sure, but I don't (and won't) have time to fix it for a while. 1-2 months min. \$\endgroup\$
    – J Atkin
    Feb 29, 2016 at 21:08
1
53 54
55
56 57
155

You must log in to answer this question.

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