459
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43
  • \$\begingroup\$ I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . \$\endgroup\$ – AZTECCO Oct 5 at 19:39

2566 Answers 2566

2
\$\begingroup\$

Pirates!

Introduction

Arrr mateys!

All hands on deck! Tharr be a ship o' other pirates comin' starboard up t' us on t' starboard! Man t' six pounders! We'll show these guys what we're made of!

...

What? They have t' exact same ship, and t' exact same six pounders as us? That don't matter, we've got better cannon strategy! As long as we reinforce points o' our ship that they fire upon, and fire upon unreinforced parts o' their ship, we're aye t' win! Now, where's that techno thingamabob that said what t' do...?"

Game Description

In this King of the Hill challenge, you write a program to command a pirate crew in a naval war. The other pirate crews are controlled by other players' programs. By carefully choosing where and when to fire, you can defeat the other pirate crews and claim the golden treasure -- the green checkmark of legend.

A battle occurs between two ships. Each ship is mounted with 7 cannons in a row, labelled 1 to 7. Each cannon is directly opposite to the cannon on the other side. Ships all start with 0 damage. If a ship reaches 10 damage, it sinks, and the crew of the other ship win the battle. If both ships sink at the same time, the battle is a draw.

Each battle consists of several turns. On each turn your crew can do any of the following actions:

L:n

Load a cannonball into cannon n. All the cannons start with cannonballs in them, and naturally firing a cannon without a cannonball doesn't do anything.

You can only load one cannonball into a cannon at a time.

R:n

Reinforce a cannon n. Reinforcements will nullify a single attack on that cannon. However, reinforcements are but a transient defence -- they will wear off two turns after they have been applied.

[Todo: Clarification on "two turns"]

F:n

Fire a cannon n, which will hit cannon n on the opposing side. If the cannon is not reinforced, the opposing ship's damage will increase by 1. If the cannon is reinforced, the ship will not take damage, but the reinforcement will be destroyed.

Input Description

The controller will call your program from the command line like this:

<command> <history> <enemy_history> <damage> <your_damage>

where:

  • command is the command needed to run your program. For instance, if your program's source code was in the file arrr.rb, the command is ruby arrr.rb.
  • history is a comma separated list of moves that you have made. For instance, L:1,F:1,L:2,F:2 would mean that you loaded and fired cannon 1, and loaded and fired cannon 2.
  • enemy_history is a comma separated list of moves the enemy has made.
  • damage is your ship's damage (from 0 to 9, since 10 means you've sunk)
  • enemy_damage is the enemy ship's damage

Output Description

Output to STDOUT in the form:

A:N

where A is either L, R, or F, and N is an integer from 1 to 7. This indicates the move that you want the pirates to do.

[Todo: The rest of the spec. I'm tired and I'm posting it here to save it. Will come back some time to finish it. Maybe. Honestly I'm not too fond of the idea but it might have some potential.]

\$\endgroup\$
  • 1
    \$\begingroup\$ Your specification was very well written until the Game Description; please consider rewriting the whole thing in Pirate. \$\endgroup\$ – Faraz Masroor Jun 2 '15 at 21:45
  • 2
    \$\begingroup\$ @FarazMasroor I'll consider it. I want to be careful that I don't go overboard on the pirate speech though since I don't want to make the spec difficult to read. \$\endgroup\$ – absinthe Jun 2 '15 at 22:05
  • \$\begingroup\$ Haha how about adding a translation at the bottom. \$\endgroup\$ – Faraz Masroor Jun 2 '15 at 22:08
  • \$\begingroup\$ >Implying Pirate is hard to read but English isn't \$\endgroup\$ – Faraz Masroor Jun 2 '15 at 22:14
2
\$\begingroup\$

Chinese Checkers

I'm considering writing a challenge that will have people write Chinese Checkers players.

Image courtesy of Wikipedia

Image courtesy of Wikipedia

The game is quite simple: In clockwise turns, players try to move their 'pegs' across the board. They may only move one peg each turn. Valid moves are either moving to an adjacent empty space, or hopping over any number of pegs (friend or foe). These moves cannot be combined. The game is won when somebody has all their pegs in the triangle opposite of where they started.

I will write a controller, that will match up all players against each other in a sufficiently large number of matches. Each match, there will be points for the first, second and third place. Winner is the one with the most points.

Players must have a time limit on each move. This limit will be checked by the controller, and penalties will be applied accordingly. There will also be a limit on total number of moves, to prevent my poor laptop from calculating Chinese Checkers until the heat death of the universe because some idiot decided that random walks would be the way to go.

Since I've never written a controller before, I'd first like to see whether you guys are interested at all in this challenge. Furthermore, which language is generally preferred for these kind of challenges: Java or C++?

\$\endgroup\$
  • \$\begingroup\$ Sounds like it could be good. You'll certainly get more participation if the controller is in Java. Ideally you'd also provide a wrapper that allows communication via STDIN/STDOUT, such that any language can participate. \$\endgroup\$ – Martin Ender Jun 8 '15 at 10:32
  • \$\begingroup\$ @MartinBüttner Thanks for the feedback! How should I do that? Ask people to upload their binaries? Or compile everything on my laptop, and limit the languages to compilers I can easily obtain with apt-get? \$\endgroup\$ – Sanchises Jun 8 '15 at 10:55
  • \$\begingroup\$ The latter. You'll usually want to compile things yourself. \$\endgroup\$ – Martin Ender Jun 8 '15 at 10:55
  • 1
    \$\begingroup\$ You should keep in mind that Chinese Checkers AI programs already exist, and much of the challenge may be adapting them to fit the time constraints, special rules, etc. \$\endgroup\$ – lirtosiast Jun 8 '15 at 20:50
  • \$\begingroup\$ @ThomasKwa I think (hope?) that for these kind of games, there is no 'best' AI (yet), so it all depends on what heuristics you choose to implement with what parameters. What do you think? \$\endgroup\$ – Sanchises Jun 10 '15 at 13:04
  • \$\begingroup\$ Although our members do impressive things, I'm not sure that there will be multiple people skilled enough to write their own state-of-the-art Chinese Checkers AI. One thing you may be able to do is have an extremely tight time constraint for each move (in the single-digit ms), because that may be a niche that mainstream AIs haven't filled yet. Don't trust me though, because I know nothing about board game AIs. \$\endgroup\$ – lirtosiast Jun 10 '15 at 15:17
2
\$\begingroup\$

Captcha cops-and-robbers

Cops develop a captcha algorithm in minimum bytes. Robbers tries to implement a recognizer that recognizes 90 of 100 generated captchas.

\$\endgroup\$
  • \$\begingroup\$ I'm sure there will need to be more details, but that seems to summarise what would be needed already so +1 \$\endgroup\$ – trichoplax Jun 9 '15 at 18:15
  • \$\begingroup\$ @trichoplax, I'll edit into a fully fledged question if the idea gains some support. The main problem that the captcha needs to be solvable by humans, which is a bit subjective. \$\endgroup\$ – Vi. Jun 9 '15 at 19:12
  • \$\begingroup\$ Yes, I guess you'd need a population of unwitting humans for testing \$\endgroup\$ – trichoplax Jun 9 '15 at 19:38
  • \$\begingroup\$ @trichoplax, I and other users can test and vouch for validity of posts. \$\endgroup\$ – Vi. Jun 9 '15 at 21:15
  • 1
    \$\begingroup\$ I guess it's the borderline cases that would be harder to judge. If 95% of humans agree on the solution it's OK. If only 50% of humans agree on any one solution then it's probably not OK. But what if 75% of us agree on a given solution? Does it count as a valid cop? \$\endgroup\$ – trichoplax Jun 9 '15 at 21:47
  • 1
    \$\begingroup\$ @trichoplax, Maybe it needs some online service that that users can test in more or less controlled way? \$\endgroup\$ – Vi. Jun 10 '15 at 0:35
  • \$\begingroup\$ I think some companies use humans completing captchas as a way of determining what the "correct" human answers should be. We don't have a large pool of humans we can force to complete captchas though. \$\endgroup\$ – trichoplax Jun 10 '15 at 0:48
  • \$\begingroup\$ I'd like to see this work if there's another way of verifying what is readable to a human. If nothing better comes up you can simply say that you as the question poster will be the designated subjective human. So the challenge should go ahead one way or another. \$\endgroup\$ – trichoplax Jun 10 '15 at 0:49
2
\$\begingroup\$

Merging Words

Input

Two strings, and two numbers: "hlwl", "elo_ord!", 1 2

These may be function parameters, STDIN or language equivalents.

Output

The second string merged into the first string. The numbers specify how many characters to add when merging.

This is what happens:

h  l  w  l        //notice there is only 1 char per group (first number)
 el o_ or d!      //2 chars per group here (second number)
-------------
hello_world!

More formal-ish procedure:

  • start with the first string
  • Remove the first n chars from the first string and append it to r, where n is the first numerical input and r is the output string
  • Remove the first k chars from the second string and append it to r, where k is the second numerical input
  • Repeat the last 2 steps until both the first and the second string are empty. You may assume that first_string.length / second_string.length == n / k

Test Cases

input: aaaa bbbb 1 1
output: abababab

input: abcd iiiiiiii 1 2
output: aiibiiciidii

input: chmeeo aln 2 1
output: chameleon

input: emblem ezzent 3 3
output: embezzlement

This is code-golf, so shortest code wins!

\$\endgroup\$
  • \$\begingroup\$ Does the order of the input parameters matter? Can be input be formatted as something parsable (e.g., "aaaa" "bbbb" 1 1)? \$\endgroup\$ – Dennis Jun 23 '15 at 4:47
  • \$\begingroup\$ @Dennis The order does matter - start with the first string, and the input can be pretty much anything - I'll clarify that. \$\endgroup\$ – Stretch Maniac Jun 23 '15 at 11:20
  • 3
    \$\begingroup\$ FWIW this is 4 characters plus a couple for stack manipulation in certain golfing languages. \$\endgroup\$ – Peter Taylor Jun 23 '15 at 13:29
  • 1
    \$\begingroup\$ What I meant was if the input could be read as "hlwl" 1 "elo_ord!" 2 or 1 "hlwl" 2 "elo_ord!" or even 1 "hlwl" "elo_ord!" 2, for example. \$\endgroup\$ – Dennis Jun 23 '15 at 14:28
2
\$\begingroup\$

Can you lose from this chess position?

Introduction

You are an arbiter who supervises a very large number of chess tournaments. Thus, you frequently rule on whether a player who runs out of time may claim a draw based on Article 6.9 of the FIDE Laws of Chess:

[...] If a player does not complete the prescribed number of moves in the allotted time, the game is lost by the player. However, the game is drawn, if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves.

In order to be able to perform your job more efficiently, you decide to create a computer program that determines whether it is possible for a player to be checkmated from a given position.

Regulations

The input will be a position with White to move, with at least one legal move available. You may assume that in the initial position, neither player will retain castling rights and no en passant capture will be available. Additionally, you may assume that the existence of en passant is irrelevant to the correct output. Your program must determine whether, starting from the input position, there exists any sequence of legal moves that ends in Black checkmating White's king.

Either a program utilizing standard input and output, or a function accepting a string and returning a number is acceptable.

Input will be given in FEN notation, but excluding the last 4 tokens – only the locations of the pieces on the board are described.

The program shall output 1 if it is possible for white to be checkmated, or 0 if it is not.

Restrictions

  • Your source code must fit inside a post on this site.
  • If the program exceeds 1 minute of thinking about a position, it is equivalent to an incorrect output.

The winner is the first competitor to submit a correct program. A program shall be considered correct if no one provides an input that causes the program to fail to produce correct output in time for three days after the program is posted.

Examples

Input

kb6/8/8/8/8/8/8/KB6

Output

1

Input

1kb5/8/8/8/8/8/8/KB6

Output

0

Input

3k4/8/1p1p1p1p/pPpPpPpP/P1P1P1P1/8/8/3K4

Output

0

---------------------------

Feedback

Suggestions for improvement are welcome. I would most like to have some input on the victory condition. Is it too difficult to achieve? Should I score it on a fixed set of positions instead?

\$\endgroup\$
  • 4
    \$\begingroup\$ The three day rule is a bad one. If an answer is incorrect, it's incorrect, and the possibility that no-one paid it much attention in the first 72 hours after posting shouldn't change that. \$\endgroup\$ – Peter Taylor Sep 19 '14 at 19:45
  • \$\begingroup\$ This is interesting. Here's two slightly tricky test cases: 8/8/p1p1p1pk/P1P1P1q1/5P1K/6B1/8/5b2 and 7k/2PPRPRP/p3P1PP/8/8/8/P7/K7. \$\endgroup\$ – Lopsy Sep 20 '14 at 15:58
  • \$\begingroup\$ Hmm so maybe there should be a new rule that you are losing again, if someone provides a counterexample to your program at any date? @Lopsy nice example requiring a bishop promotion :) \$\endgroup\$ – feersum Sep 20 '14 at 16:18
2
\$\begingroup\$

Am I offering a bite that's more than people are willing to chew?


Truth Table Solver

Goal

This code golf challenge is to display a rule that is valid for a given truth table.

Input

The input into the program is a boolean array, though you may choose how this is formatted (array, string, etc.) Each value in the array is true or false (or 1 or 0 or any other boolean pair). The index of the value represents the truth table inputs and the value itself is the result of applying the unknown rule to these inputs.

For the truth table inputs, A is the least significant bit of the index. B is the second-least significant bit, and so on. The number of indices in the table determines the number of inputs: log2(n).

For example:

index c b a value
  0   0 0 0   0
  1   0 0 1   0
  2   0 1 0   0
  3   0 1 1   1
  4   1 0 0   1
  5   1 0 1   1
  6   1 1 0   1
  7   1 1 1   1

Output

Given this truth table, your program must determine the rule is, in this case, (a&b)|c and output it. The variables may be in any order and printing redundant brackets is fine.

Requirements

Rules may include any of the following operations NOT (~), AND (&), OR (|), XOR (^) and identify priority with brackets.

Test Cases

Here are some test cases, expressed as a string of boolean results:

0100              (~a)&b
00011111          (a&b)|c
01101000          a^b^c
0000011101110111  (a|b)&(c|d)
0100010100010000  a&(((~b)|c)^d)

Scoring

The shortest code after two weeks wins the contest.

\$\endgroup\$
  • \$\begingroup\$ The requirement to "support the operation... XOR" doesn't make sense to me. The obvious way to get the shortest program is to output in DNF, and XOR is unnecessary for that. The requirement to "identify priority with brackets" seems to contradict the example output ~a&b. \$\endgroup\$ – Peter Taylor Jul 3 '15 at 6:24
  • \$\begingroup\$ What happens if a boolean array can be expressed in multiple ways? Do we output all possible options or just one? \$\endgroup\$ – Beta Decay Jul 3 '15 at 10:06
  • \$\begingroup\$ If you want to include a specific range of operators without having answers never use some of them (due to DNF as mentioned by Peter Taylor), you could require the shortest rule, instead of just any rule that works. \$\endgroup\$ – trichoplax Jul 3 '15 at 16:01
  • 1
    \$\begingroup\$ Thanks for the feedback! After reading about DNF, I see now the easiest solution is to simply output every "true" row of the truth table which makes this purely an exercise in data transforming, not problem solving, eg. (a&b&~c)|(~a&~b&c)|(a&~b&c)|(~a&b&c)|(a&b&c) \$\endgroup\$ – Hand-E-Food Jul 5 '15 at 23:32
  • \$\begingroup\$ I want to take this one. \$\endgroup\$ – Akangka Jan 1 '16 at 0:01
2
\$\begingroup\$

Translate Treehugger to BrainF**k

(?)

Overview

This problem deals with two esoteric programming languages that I will briefly describe for completeness.

Brainfuck is a language that has only 8 commands. Imagine a tape of values (generally 0-255) stretching infinitely to the right, initialized to zero, and an instruction pointer P pointing to the first element:

|-----|-----|-----|-----|-----...
|  0  |  0  |  0  |  0  |  ...
|-----|-----|-----|-----|-----...
   ^
   P

The eight commands effect the pointer and tape in the following way:

+ ===== increment the value that `P` currently points to
- ===== decrement the value that `P` currently points to
, ===== read a byte from stdin into the location that `P` points to
. ===== output the value that `P` points to as an ASCII character
> ===== move `P` one cell to the right
< ===== move `P` one cell to the left
[ ===== if the value pointed to by `P` is zero, jump past the matching ] ( while(*P){ )
] ===== if the value pointed to by `P` is non-zero, jump to the preceding [ ( } )

Some finer points, for the purposes of this question:

  • Adding one to 255 yields 0, and decrementing 0 yields 255.
  • Moving left off of the tape causes the program to abruptly halt.
  • All [ must be matched with a single ]. They may be nested.

Treehugger is a language derived from Brainfuck, but differs greatly in how memory is stored. Instead of viewing memory as a tape, view memory as a binary tree that expands infinitely downward:

       P
       v
       0
  0---/ \---0
 / \       / \
0   0     0   0
.   .     .   .
.   .     .   .
.   .     .   .

P begins at the top of the tree, and again all values are initialized as 0. Most of the commands are exactly the same as corresponding Brainfuck commands, but there are two differences:

< ===== move P down the left branch of the tree once
> ===== move P down the right branch of the tree once

There is also one new command:

^ ===== move P one node up the tree

It is simple to translate Brainfuck to Treehugger by replacing every < with a ^. Translating Treehugger to Brainfuck, however, is far more difficult.

Input

Your program or function will take in a list of characters from +-<>^,.[], representing a complete Treehugger program.

  • You may assume that the input ends in some terminating character, like a newline or EOF.
  • You may assume that, other than the optional terminating character, every character is one of the 9 commands.
  • The Treehugger program will have balanced [ and ].
  • The Treehugger program will not attempt to move up one node from the top of the tree at any point.
  • The Treehugger program will never contain a , character inside of a [] loop. The program will always take a finite, known number of input bytes.
  • The Treehugger program will terminate for all inputs.

Input must be taken as a string of characters through stdin or a function argument.

Output

Your output should be a functioning Brainfuck program that takes the same number of inputs and provides the same output as the corresponding Treehugger program. Brackets must be balanced, and the code must never move left off of the tape. Your Brainfuck program must terminate.

Rules and Scoring

Your score for this challenge is:

Length of your code + 0.1 * the length of each test case's output

Lowest score wins!

Standard Loopholes are disallowed.

Test cases

Coming soon to a challenge near you...


Is this interesting?

Too easy/hard?

Is the scoring system appropriate?

\$\endgroup\$
  • \$\begingroup\$ I do not think this is possibly. And lol "Soon" \$\endgroup\$ – Rohan Jhunjhunwala Aug 9 '16 at 1:01
2
\$\begingroup\$

Proposed King-of-the-Hill: Synchronous Bughouse Chess960

I have an idea for what I think could be a fun and somewhat different KOTH contest. However, before I put in the work writing explicitly detailed instructions and writing/deploying a test server, I want to make sure that (a) there will be sufficient interest to go through this effort and (b) the best way to design the contest and restrictions if people would like to play.

Chess960 is a chess variant in which the starting positions of the back-rank pieces are randomized with constraints such that there are 960 possible starting positions. Bughouse chess is a team-based chess variant played asynchronously on two boards in which teammates hand the pieces they capture to their teammates to potentially drop on the board.

Synchronous Bughouse Chess960 (SBC960) is a chess variant I developed to combine these two variants and to impose some synchronization rules to make it suitable for a tournament. Each of the two boards is set up independently using the rules of chess960 of the other (thus making for 921,600 overall starting positions). Game play is organized into orderly rounds during which each player takes his turn in the following order: team 1 white, team 2 white, team 1 black, team 2 black. On a player's turn, he may move a piece according to chess960's rules, drop a captured piece according to bughouse chess's rules, or delay.

Each player starts the game with five delays. When a player uses a delay, his opponent's next turn is skipped (at no cost to the opponent other than perhaps momentum). Delays are legal moves. Play continues until a player has no legal actions when his turn in the round comes up (no legal moves, no legal drops, and no remaining delays). When that condition comes, the outcome of the game is determined by whether that player is in check. If so, the team who has checked the player wins. If not, the game ends in a draw. For convenience, a position is only considered "checkmate" if a player is in check and has no legal moves left.

My KOTH tournament idea is to have players design AIs to play SBC960. I think this game has some interesting possibilities because of the team-based play. For example, rushing for the win on one's board might be a losing strategy for a player if the other team can checkmate his teammate faster. It might also be viable for a player to allow himself to be checked toward checkmate if one's teammate can achieve checkmate before that player runs out of delays. Also, the many starting positions makes it impractical for anyone to write an entry that uses opening libraries.

So, the first question is:

1) Would anyone be interested in participating in an SBC960 tournament? If at least four people would compete, I am willing to put in the work to get this together

If people are willing to play, then I need to know the best way to structure the rules for the entries. This entails the server-client interface (STDIN/STDOUT? sockets with TCP/IP?), whether to permit people from designing AIs that think when it is not their turn, and whether I should have an official "pre-play" round so that AIs can learn how the other entries play. I see the opportunity to make a KOTH that is different than most of the KOTHs on the site, but I want to know:

2) What are people's recommendations for the best way to design the entry rules?

I would appreciate any feedback.

\$\endgroup\$
  • \$\begingroup\$ Team KotH is tricky. The only way that I think you really get to assess each answer's strength is to play with homogeneous teams: i.e. two of Alice's bot (one white, one black) vs two of Bob's bot (one white, one black). \$\endgroup\$ – Peter Taylor Jul 21 '15 at 17:32
  • \$\begingroup\$ @PeterTaylor I had intended to use homogenous teams for at least some of the games to act at least as a tie-breaker. I think it might be possible to use ANOVA to determine how much an AI's results correlate to its abilities. Of course, I'd have to relearn ANOVA to determine whether this thought is correct. \$\endgroup\$ – sadakatsu Jul 21 '15 at 18:45
2
\$\begingroup\$

Vowel-Consonant Imbalance

Sandbox question: Is it too easy/too close to an existing question? Related ones I found: Find words containing every vowel and Finding the most 'unique' word

You should write a program or function which receives a list of space-separated words as input and outputs or returns one of the words with the greatest difference between its vowel and consonant counts.

E.g.

"cars" has 1 vowel and 3 consonant so the difference is 2
"queue" has 4 vowels and 1 consonant so the difference is 3

If multiple words have the same maximal difference, exactly one (any of them) should be returned.

Input

todo

Output

todo

Examples

todo

This is code golf so the shortest entry wins.

\$\endgroup\$
  • \$\begingroup\$ IMO this is too easy, but if you decide to post it then it needs an unambiguous working definition of "vowel". I assume that input can be mixed case, but e.g. is y a vowel or a consonant? (If you want to be realistic then the answer is "It depends", but I'm not sure I could write a clear and accurate spec for when it's a vowel). What about accented letters? \$\endgroup\$ – Peter Taylor Jul 22 '15 at 6:01
  • \$\begingroup\$ @PeterTaylor Thanks, if I post it, I will clarify these. Input will be only lowercase letters and spaces. Vowels will be aeiouy. But it is really easy. Maybe I'll post it on a very slow day once... \$\endgroup\$ – randomra Jul 22 '15 at 10:48
2
\$\begingroup\$

CJam Expander

Input: a program written in CJam. You can accept input however you'd like.

Output: the same program ready to be put into a PPCG answer. You must:

  • Not change the horizontal position of any token in the program.
  • Put each token one line below the previous one except } which must appear on the same line as the corresponding {. The token immediately following a } will be one line below the }.
    • For this challenge, every letter is considered a token except literal strings and numbers which count as one token regardless of character length.
  • Add e# to the end of every line. The e#s must line up vertically two spaces to the right of the last character in the program.
  • Either prefix each line with four spaces or surround your output with <pre> and </pre>.

Example:

Adapted from Martin Büttner♦'s answer.

Input: 4,{"Happy Birthday "\2="Dear CJam""to You"?N}%

Output:

    4                                               e#
     ,                                              e#
      {                                         }   e#
       "Happy Birthday "                         %  e#
                        \                           e#
                         2                          e#
                          =                         e#
                           "Dear CJam"              e#
                                      "to You"      e#
                                              ?     e#
                                               N    e#

Bonus:

If you output a header and footer like the one below, multiply your score by 0.8. Using the same input, here is an output that qualifies for the bonus:

#CJam, 46 bytes


    4,{"Happy Birthday "\2="Dear CJam""to You"?N}%

Explanation:

    4                                               e#
     ,                                              e#
      {                                         }   e#
       "Happy Birthday "                         %  e#
                        \                           e#
                         2                          e#
                          =                         e#
                           "Dear CJam"              e#
                                      "to You"      e#
                                              ?     e#
                                               N    e#

[Try it online.][1]

[1]: link

Of course, you have to adjust the byte count to match the input. You are not required to make a working link for the online demo (although that would be cool).

\$\endgroup\$
  • 2
    \$\begingroup\$ Similar, but with different I/O format and language specificity. \$\endgroup\$ – Geobits Jul 21 '15 at 17:19
2
\$\begingroup\$

Sort a CSV list by key...imperfectly.

Tags:

Anything I missed and/or overlooked here? I'm pretty sure I closed up most of the holes here. Also, what is there that could use some improvement?

Another question: would this be better tagged as ?


Introduction

You are working for some company you can't stand, two-week notice already turned in, and you've just been tasked with sorting all the CSVs the company has gathered over the years. This doesn't sound like much, except your boss, whom you also don't like, has demanded you implement your own sort. He doesn't care about Big-O whatever (he has never even heard of the term), but he just wants it done. You want to get back at him for making you do this, so you want to make that sort imperfect. At least you know he won't have time to check it until you're gone.

Objective

Your task is to write a program that sorts a CSV table (incorrectly), by key.

A correct program for purposes of this challenge:

  • doesn't use one of the tried-and-false, unfunny techniques.
  • takes two arguments (in order): the key to sort by, and optionally a separator, defaulting to a comma (,).
  • takes the CSV via standard input, in the following format:
    • Each row is separated by a Unix-style line feed.
    • Each entry within each row is delimited by the separator.
    • Each entry is unquoted/etc. It is solely delimited by the separator.
    • Each entry may be assumed to not contain an instance of the separator or a newline.
    • The first row indicates the key names. The successive rows are the data that needs sorted, by key
  • emits the sorted CSV via standard output.
    • The emitted data must also adhere to the above format, including the separator. It must be syntactically correct.
  • looks completely innocent, despite being completely and totally wrong. That's the underhanded spirit.
    • Please don't use Unicode lookalikes. It's not funny nor original, especially after seeing it multiple times on a single question.

In this case, the values for the key key are 1, 2, and 3.

foo,key,value
spammer,1,32nefr2u34
ball,2,304u23rne2
blarger,3,32o4u3jnk4

Invariants

  • The input CSV is assumed to be correct, including each row having the same number of entries. At least they weren't made by such air-headed people.
  • The entries may have varying lengths.
  • The associated values for the key is assumed to be a float (decimal not required) in textual form, base 10.
  • The list may vary in length.

Requirements

  • At least 1% of the list must vary from the "correct" output every single time. This may mean entries that are out of order, lost, or corrupted. This may also include entire columns going missing (in which 100% is "incorrect").
    • This is only required when there are at least 4 entries in the input.
    • The keys themselves are not counted as part of the list, but they don't necessarily have to remain intact.
  • It must print at least 50% of the data it took in, but more than 100% of the original is permitted.
    • As a special case, empty stdin allows empty stdout, and input just consisting of the headers may simply print just headers coming out.
  • The program must have no other external side effects other than what is required to do the above.

Other information

  • The sorting algorithm is up to the implementation. It doesn't matter, as long as it sorts, the sort is stable, and the algorithm's complexity is bounded (i.e. no Bogosort, infinite loops, etc.).
  • No other features may be added, including a help message.

Example

Input:

foo,key,value
ball,5.2,304u23rne2
spammer,1,32nefr2u34
blarger,3.1,32o4u3jnk4

Output (correct):

foo,key,value
spammer,1,32nefr2u34
blarger,3.1,32o4u3jnk4
ball,5.2,304u23rne2

Output (passes this challenge):

foo,key,value
spammer,1,32nefr2u34
ball,5.2,304u23rne2
blarger,3.1,32o4u3jnk4

The person with the highest number of votes wins!

\$\endgroup\$
  • \$\begingroup\$ The spec as written seems to allow emitting the empty string as the only output. \$\endgroup\$ – Peter Taylor Jul 20 '15 at 13:21
  • \$\begingroup\$ @PeterTaylor Good catch... \$\endgroup\$ – Isiah Meadows Jul 20 '15 at 13:24
  • \$\begingroup\$ Most underhanded questions are tagged as both underhanded and popularity-contest. Since the winner is determined by the number of votes, I'd use both tags, and drop code-challenge. \$\endgroup\$ – es1024 Jul 21 '15 at 6:46
  • \$\begingroup\$ @es1024 Done. <filler text> \$\endgroup\$ – Isiah Meadows Jul 22 '15 at 4:10
2
\$\begingroup\$

Save the bunny!

This King of the Hill competition is about a 2D flawn populated with bouncing balls and bunnies. The balls will collide with each other and the boundaries. If a bunny gets hit by a ball, it´s dead teleported away (for cuteness sake).
Your task is to write a AI for the bunnies, such that they live as long as possible.

The AI:

The AI shall be a C++ Class with a constructor that takes a pointer to the array of balls and a function that returns the direction the bunny should go as a angle. Of course AIs that modify the game will not be accepted. @ Meta: Will be more specific once the framework is finished.

Scoring:

Competitions will be run on several dates based on the valid submissions, after that the video will be posted on Youtube.
The time your bunny survives is your score.
To minimize randomness, there will be several runs and a 3 second spawn protection.

Meta

I will do the framework in the next few weeks and enhance this post with pictures, source code and more specific stuff. Is the basic idea clear?

\$\endgroup\$
  • 1
    \$\begingroup\$ Say two bunnies are really good at dodging and just plain don't get hit. Is there a time limit (to tie), or how do you ensure there is just one winner? \$\endgroup\$ – Geobits Jul 24 '15 at 12:39
  • 2
    \$\begingroup\$ I will increase the number of balls, until they die \$\endgroup\$ – Moartem Jul 25 '15 at 9:36
  • 2
    \$\begingroup\$ I was hoping (hopping...?) it would be something like that :) \$\endgroup\$ – Geobits Jul 25 '15 at 14:20
2
\$\begingroup\$

Weight Configuration

Introduction

Gyms have machines that contain a stack of weights and a pin. You insert the pin into the hole that matches the amount of resistance you want, and then you work out. However, the machines often have an additional set of smaller weights at the top that are pinned onto a fixed piece of the machine; you can unpin these weight and slide them down to sit on top of the big stack to add a few more options for your workout. In ASCII form, these weight stacks look something like this (this one is annotated):

-----------   }- top of stack, always required
___|___|___   \
|____5____|   |
___|___|___   |
|____5____|   |
   |   |      }- "neck" section
   |   |      |
   |   |      |
 __|___|__    /
_|_____o_|_   \
|_20___o__|   |
|_30___o__|   |
|_40___o__|   }- weight stack
|_50___o__|   |
|_60___o__|   /

...and so on. Notice that there is a smaller block on top of the big stack that has no number; putting the pin in this block means there is no extra resistance beyond the base amount the machine provides. If you wanted to exercise with only 5 or 10 resistance on this machine, you would put the pin in this block and then unpin one of the extra weights.

Challenge

Given the number of small weights on the machine, the configuration of the large weights, and the level of resistance someone wants to work out at, you must output a picture of the correct configuration of weights so that the given resistance is met. The small weights always have a value of 5 (pounds, kilos, stones, whatever). For example:

Input:

3 [20,30,40,50,65,80,100] 45

Output:

-----------
___|___|___   
|____5____|
___|___|___   
|____5____|
   |   |
   |   |
   |   |
   |   |
___|___|___   
|____5____|
_|_____o_|_
|_20___o__|
|_30___o__|
|_40___O__|
|_50___o__|
|_60___o__|
|_70___o__|
|_80___o__|
|_90___o__|
|_100__o__|

One of the 5 weights has been unpinned and now sits on the stack; the 40 weight has the pin in it (as denoted by the capital O). Another valid solution would be to put the pin in the 30 weight and slide all of the extra weights down onto the stack, as both would achieve 45. That would look like this:

-----------
   |   |
   |   |
   |   |
   |   |
   |   |
   |   |    
___|___|___   
|____5____|  
|____5____|   
|____5____|
_|_____o_|_
|_20___o__|
|_30___O__|
|_40___o__|
|_50___o__|
|_60___o__|
|_70___o__|
|_80___o__|
|_90___o__|
|_100__o__|

Notice the length of the "neck" in both cases of the machine; the number of rows in the neck section must be exactly 2*(number of extra weights)+4. In this case, since there are 3 extra weights, that number is 10. No matter how the extra weights are positioned, there must be 10 rows (because when you slide a weight down the neck, part of the neck doesn't disappear!), and extra weights that are pinned at the top must have a row of neck between them (as in the examples). Since the weights slide down, the lowest weight must be used first, then the next, and so on. All the 5s are centered, and all of the numbers on the large weights are left-aligned to the third column.

Input specifications:

The three pieces may be inputted in any format you like (newline separated, space separated, list in any format of your choosing, etc), subject to the following restrictions: The number of extra weights is always the first piece of input and will be between 0 and 4. The list of weights is the next input; each element will be between 15 and 200 and a multiple of 5; the whole list may be assumed to be sorted. The target resistance is last and will be between 0 and 220; it will also be a multiple of 5.

Output specifications:

Output a weight stack as specified above, with the pin in the appropriate place and the appropriate extra weights slid down onto the stack such that the target resistance is met. If the target resistance can't be met with the given configuration, you may either output an unmodified stack (with all extra weights pinned at the top, and no pin inserted), an error message, or nothing. Some resistances have multiple configurations that achieve it; you are only required to output one of them, and your program need not output the same one every time.

Whitespace:

  • Trailing whitespace on lines is okay and need not be uniform.
  • Leading whitespace on lines is acceptable as long as the leading whitespace on each line is the same (this doesn't include the whitespace required to draw the neck section or zero-weight pin block).
  • Leading and trailing newlines are acceptable.

Scoring

This is , so lowest byte count wins. Multiply your byte-count by 0.9 if instead of only outputting one configuration when there are multiple solutions, you output all of them (either side-by-side with at least one empty column between them, or one after the other with at least one blank line between them).

Tags:

Suggestions? I think the neck bit is a little confusing and there may be too much going on.

\$\endgroup\$
  • \$\begingroup\$ I think it might be good to show the 30 possibility too, because I'm not sure how the output is supposed to look when you have small weights stacking. \$\endgroup\$ – Sp3000 Aug 13 '15 at 2:56
  • \$\begingroup\$ @Sp3000 I edited it to show both versions and I tried to clarify the thing about the neck height. \$\endgroup\$ – Alex Van Liew Aug 13 '15 at 3:07
  • \$\begingroup\$ It's a bit clearer, but I'm still a little confused - does the neck height depend on the number of extra weights (2*(number of extra weights)+4 I'm assuming) or is it always 10? Because "for this reason the extra weights will always be between 0 and 4" seems to suggest the latter to me \$\endgroup\$ – Sp3000 Aug 13 '15 at 3:11
  • \$\begingroup\$ (also, as with most ASCII art challenges - are there any rules on leading/trailing whitespace either before/after the entire output or before/after each line?) \$\endgroup\$ – Sp3000 Aug 13 '15 at 3:11
  • \$\begingroup\$ @Sp3000 Let me tweak the requirements a bit. \$\endgroup\$ – Alex Van Liew Aug 13 '15 at 3:30
  • \$\begingroup\$ @Sp3000 Okay, I added stuff about whitespace and removed the thing about "for this reason the weights..."; it doesn't really matter why I chose 4 as the maximum, I just thought it might help the reader understand the specifications about the neck. I've personally never seen machines with any number other than 2, but I assume they must exist (and it seems like there wouldn't be any with more than 3 or 4). \$\endgroup\$ – Alex Van Liew Aug 13 '15 at 3:46
2
\$\begingroup\$

Theoretical Analysis of Pulley System

(I think it is gonna be a code golf challenge?)

Introduction

In rope access and rescue, as well as sometimes in climbing, caving and rock climbing you need to build pulley systems for hauling equipment or rescuing injured people. Here we will look at them from a more abstract perspective. As those systems can get arbitrarily complex we will limit ourselves to a certain class of pulley systems: They are one dimensional (only two opposing directions) and there is only one fixed anchor. Further we assume that there is one piece of load on one end of the rope and unit of force pulling at the other end of the rope.

Challenge

Write a program that accepts a pulley system encoded as a string (see below) that returns the actual mechanical advantage (AMA) - polynomial.

Introduction of symbols

  • Rope rope There is one continuous piece of rope, beginning at the load and ending where the force is applied. The rope is not cut, always just one piece.

  • Attachment points:

    • Anchor: anchor In each example we consider here, there is exactly one anchor (you can imagine it as the ceiling). Other than that, the anchor behaves the same way as a knot (see below):

    • Knot: knot You can attach an unlimited number of pulleys to each knot. Those connections will also be shown as black lines in the following graphics, but do not count as rope.

    • Pulley: pulley A pulley can be attached to a knot (or the anchor), (indicated by the black lines from center of the pulleys to the knots). When the rope is passing a pulley (the lines that are tangent to the circle), it acts as a redirection (rope coming in in the opposite direction of the rope going out).

  • Load: load In each example we consider here there is exactly one piece of load. It is connected to one end of the rope.

  • Pulling force: pulling end In each example we consider here there is exactly one point where external force is applied, this is the other end of the rope.

Theory: The T-Method

(You can skip this if you are already familiar with how to calculate the mechanical advantage of pulley systems assuming a friction coefficient.)

Theoretical mechanical advantage (only an intermediate step, we do not use this for the challenge)

With the so called T-Method we can calculate the theoretical mechanical advantage (TMA) of a pulley system. Here we use the assumption that a rope going through a pulley has the same tension on both sides of the pulley. We define the applied force (tension) to be one unit and follow along the rope in order to successively figure out the force/tension on each piece of rope, pulley or knot and eventually the load. The force on the load is the TMA of the whole pulley system. (The TMA is only considered for teaching how to calculate the AMA and usually has no practical application.)

age description here

Actual mechanical advantage (AMA)

Each redirection of the rope (=pulley) creates some friction so the assumption of having the same amount of tension on both sides of the pulley can lead to way too optimistic results. We can improve this model by assuming that each pulley has an efficiency 0<=X<=1. This means that if we apply and amount of force F to the rope on one side of the pulley, the rope on the other side of the pulley will only experience a force of X*F. Here an example with X=0.9 (90% efficiency):

enter image description here

(The AMA with known efficiencies is a great tool for estimating the real mechanical advantage of a pulley system especially if you have to rely on low efficiency pulleys/redirections, as most have an efficiency of <<95%. But there are only a few pulley systems that are actually used in the mentioned applications.)

Assuming that every pulley has the same efficiency X we can now use the same procedure as with the TMA in order to find the AMA. If we do not know the efficiency X we have to use X as a variable. When calculating the AMA of a certain pulley system with an unknown efficiency we get a polynomial in X for the AMA. This is what your program has to do for a given pulley system.

enter image description here


Input format

The input consists of a string of lower- and uppercase letters (a-z and A-Z). For a given pulley system, we start at the load and follow along the rope. Each time we encounter an attachment point (a pulley, a knot or the anchor) we write down the corresponding letter. We use uppercase letters if the rope is attached via knot to that attachment point or a lower case letter when the rope goes through a pulley. The attachment points are labeled alphabetically in the order of first occurrence during the rope traversal. Each time you find a knot, you can assume that the rope will go on in the same direction. Each time you find a pulley, you can assume that the rope gets redirected by 180°. The anchor point always gets the letter Z.

enter image description here

Output format

The output should comprise a list that encodes the polynomial coefficients. E.g. the polynomial a_0 + a_1 * x + a_2 * x^2 + a_3 * x^3 + …+ a_n * x^n will be encoded like so: [a_0, a_1, a_2, a_3, …, a_n]

Other Examples:

11:1

enter image description here

META: Is this ok/clear enough so far? Are there any mistakes? Can you understand it? I would of course add more examples.

\$\endgroup\$
  • \$\begingroup\$ Go for code golf. I can't think of any other challenge type which would fit \$\endgroup\$ – Beta Decay Aug 19 '15 at 8:46
  • \$\begingroup\$ Thanks for the input! Do you think the challenge is clear enough/did you understand the stuff I've written down? \$\endgroup\$ – flawr Aug 19 '15 at 18:43
  • \$\begingroup\$ I'm not 100% on the maths involved, but I got most of it \$\endgroup\$ – Beta Decay Aug 19 '15 at 18:53
  • \$\begingroup\$ It would be more readable if you trimmed a lot of whitespace off the images. And I don't find the diagrams at all intuitive: I can't work out which parts of the system are rigid and which are rope, or what's going on with the three-way joins. \$\endgroup\$ – Peter Taylor Aug 20 '15 at 17:27
  • \$\begingroup\$ @PeterTaylor Thank you for pointing this out! I indeed forgot to add some specs. I now updated the section where the symbols are explained, is it better now? \$\endgroup\$ – flawr Aug 20 '15 at 20:52
2
\$\begingroup\$

Write a Foo-immune program

In The Programming Language Quiz, Foo has quickly become one of the most annoying languages. Ever. Various people have started to "immunize" their code to avoid it being valid Foo.

Now, here's the challenge. You need to write a polyglot. A polyglot that appears to work in Foo but does something totally different versus the intended language. For instance:

a=(1)
print "Hello, World!"

would appear to work in Foo, but it actually loops indefinitely (the (1)). In Python (the intended language), it prints Hello, World! (if that wasn't already obvious :).

Rules:

  • You may not just rely on just Foo's printing of string literals, which means snippets like print "HHello, World!"[1:] are invalid. You have to put something else, too.
  • Your program may not print any error messages when run in Foo.
  • Try not to be boring. This is a popularity contest, after all!
\$\endgroup\$
  • 4
    \$\begingroup\$ I don't understand the first rule. Also you might want to explain a bit how Foo works, why many codes would unexpectedly work in Foo (i.e. that it prints strings literally) and what counts as "appears to work in Foo", because otherwise the challenge really only makes sense to people who have participated actively in the quiz. \$\endgroup\$ – Martin Ender Aug 27 '15 at 16:15
  • \$\begingroup\$ I was thinking about this as well. It's a tricky sort of challenge. I was leaning towards a set of three or four specific (reasonably simple) tasks written in different languages that also work in Foo. It would have to have some rules around code embedded in comments and other loopholes I suppose. If you can make this question work, may I suggest !foobar as a title :) \$\endgroup\$ – MickyT Aug 27 '15 at 20:49
  • 2
    \$\begingroup\$ "Write a polyglot which does two different things" is definitely Too Broad. \$\endgroup\$ – Peter Taylor Aug 29 '15 at 19:30
2
\$\begingroup\$

Invert the Fundamental Transformation on permutations

A permutation like

[3, 5, 1, 2, 4, 6]
1->3, 2->5, 3->1, 4->2, 5->4, 6->6

can be decomposed into cycles

(3, 1) (5, 4, 2) (6)

There's many ways to write these cycles, but we can fix a canonical form by requiring that:

  • In each cycle, the greatest element is written first.
  • The cycles are sorted in increasing order of greatest element.

In this form, we don't even need parentheses to demarcate the cycles. Just from the list of numbers

3, 1, 5, 4, 2, 6

we can infer that the cycles starts at the numbers that are greater than any to their left.

 3, 1, 5, 4, 2, 6
 *     *        *
(3, 1)(5, 4, 2)(6)

From here, the original permutation [3, 5, 1, 2, 4, 6] can be uniquely recovered, and your task is to write code that performs this recovery.

Input: A list of n distinct numbers 1 through n. Optionally, the value n itself.

Output: The permutation f that produces that canonical form cycle list, listed or printed as [f(1), f(2), ..., f(n)]. Format is up to you.

You may optionally work with 0-indexed values 0 ... n-1 instead of 1 ... n.

\$\endgroup\$
2
\$\begingroup\$

3-Hole Golf Course: Text Formatter

This is a series of three code golf challenges. The over-arching idea is that in each of them, you write a program that processes text in some way, and if you pipe an input text through all three solutions (with a small amount of glue code), it spits out a nicely formatted paragraph.

Hole 1: Hyphenation

Hole 2: Line Wrap

You are given as input a hyphenated piece of text, and the maximum width n ≥ 2 of a line. The output shall be a newline-delimited string, obtained by greedily splitting the input into lines of length at most n characters. Lines can be broken between words (replacing a space with a newline), after a tilde (replacing it with a hyphen), or after a hyphen (inserting a newline after it; this is needed with words like well-known). All tildes which are not replaced by hyphens should be removed, and this should be taken into account when computing the lengths of the lines. The correct output for Hy~phen~ate this sen~tence! and 20 would be

Hyphenate this sen-
tence!

A syllable that's at least n characters long and not the last syllable of a word shall be cut after the n-1st character, and a hyphen shall be inserted there before the line break. The same applies to the last syllable of a word that's over n characters long.

Hole 3: Justification

You are given as input one line of text, and the desired width n of a line, which is at least the length of the input. Your output is that line, but with extra spaces added between the words to make its length exactly n. The extra space should be added in an aesthetically pleasing way, so we require the following.

  • The lengths of any two runs of spaces differ by at most 1. This means that for some number k, every run of spaces between two words shall be of length k or k+1. For example, we could have runs of only 5 or 6 spaces between the words.
  • The list of lengths of these runs shall be balanced, in the following sense. For any two contiguous sublists of the same length, the number of ks in them differs by at most 1. For example, the list of lengths 5, 6, 5, 5, 6, 6, 5 is not balanced, since the length-2 sublist 5, 5 and 6, 6 contain 2 and 0 occurrences of 5, respectively. The list 5, 6, 5, 5, 6, 5, 6, on the other hand, is balanced.

These constraints do not uniquely specify the output. For example, for the inputs Hyphenate this sen- and 20, the two acceptable outputs are

Hyphenate  this sen-

and

Hyphenate this  sen-

If the input contains only one word, it should be left unchanged.


Sandbox notes

In all of the above holes, we can add some constraints to the input, if the challenge would otherwise be too complex (all hyphens and spaces occur between letters, all punctuation occurs at the end of words etc). However, I'm a little concerned that the holes may still be too complex. In the first hole, I can relax the case-insensitivity of the hyphenation list, and in the last hole, the second requirement can be dropped, but I feel that the second hole is already about as simple as I can make it.

\$\endgroup\$
  • \$\begingroup\$ I'm confused about the first hole: if hyphens are a known problem, why does the hyphenated word input use hyphens rather than tildes? In the second hole, for consistency I think you should replace "at a tilde" with "after a tilde". The cut at the n-1st character doesn't seem complex to me: it's just a case of how the "where should the cut be?" variable is initialised. \$\endgroup\$ – Peter Taylor Aug 25 '15 at 20:19
  • \$\begingroup\$ Also, I think the given definition of balanced in the third hole doesn't say what it's intended to say. In particular, subsequence is almost certainly not the word you want to use. \$\endgroup\$ – Peter Taylor Aug 25 '15 at 20:26
  • \$\begingroup\$ @PeterTaylor Thanks for the input! I tried to clarify the balance condition; I think it says what I want it to say, but it's hard to write clearly. \$\endgroup\$ – Zgarb Aug 25 '15 at 21:17
  • \$\begingroup\$ The point is that 2, 2 is a subsequence of 1, 1, 2, 1, 1, 2. Perhaps you could use the word sublist? \$\endgroup\$ – Peter Taylor Aug 26 '15 at 5:19
  • \$\begingroup\$ @PeterTaylor Oh, I see what you mean. Edited. \$\endgroup\$ – Zgarb Aug 26 '15 at 14:04
2
\$\begingroup\$

Enough jQuery?

As a general rule of thumb, jQuery is a vital part of any program. It is really great and does all things. Your job, as a quality-control expert, is to ensure that a given program meets industry standards. Only programs that use jQuery are eligible for your seal of approval.

The Task

Write a program which takes an HTML file as input, and returns a High-Quality (TM) HTML file as output. An existing HTML file is deemed as high-quality if it contains a script tag with the word jquery in it. Examples include the following:

<script src="jquery.js"></script>
<script src="//code.jquery.com/jquery-1.11.1.min.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

This condition is satisfied whenever there is the string <script src=", followed by "></script>, with the string jquery located somewhere in the middle.

(I'm not sure if I should make this condition more precise. It's probably good enough.)

If the given file meets quality standards, simply output it as-is. If there is no enough jQuery, however, output the file with the string <script src="jquery.js"></script> at the very top, so that everyone can see that it's a fixed, bug-free program.

\$\endgroup\$
  • 1
    \$\begingroup\$ <script type="text/javascript" src="..."></script>? \$\endgroup\$ – Peter Taylor Sep 6 '15 at 19:42
2
\$\begingroup\$

Blastoff

Your goal is the create the following text output:

10 9 8 7 6 5 4 3 2 1 Blastoff!

The "10 " will be generated by the following C program:

#include <stdio.h>
int main(){printf("10 ");}

The "9 " will then be generated by a function in a different language of your choice; the "8 " by a function in a different language; and so on until the last function generates "Blastoff!". Each function will take as input the complete source code of the previous step in the form of a string and output the next number in the sequence and a space (or the string "Blastoff!").

Each function must "do something meaningful" with the input. Doing something meaningful is defined to mean that the output will vary based on the input. That is, ignoring the input or trivially using it (e.g. making it evaluate as 0 no matter what comes in and then adding the needed number) fails to meet the challenge.

Scoring

A contestants base score will be the sub-total of the byte-length of all 10 functions. To encourage creativity, the base score will then be divided by the number of different techniques used to generate the output. For example, "string splitting", "character count", "bitwise and", etc. The technique of each function is defined as first thing done to the input string other than assignment to a variable.

Example

The following Perl code illustrates how a "9 " can be generated:

nine('#include <stdio.h>
int main(){printf("10 ");}');

sub nine{
 @a=split(/"/,$_[0]);
 print $a[1]-1 ." ";
}

Here, the function nine() takes the source code of the C program and manipulates it to get the number 9, then adds a space to the printed output. For scoring purposes, only the subroutine counts - the additional code was added for illustration purposes only and need not be listed on an entry in general. The input string for the next function will start with the "s" in "sub" and go through the final "}"

The score for this function is thus 54 (including the actually unnecessary CRs and spaces). The technique used here is string splitting. An entry that included this code would thus look like this:

9: Perl

sub nine{
 @a=split(/"/,$_[0]);
 print $a[1]-1 ." ";
}

Score: 54

Technique: String split

8: Ruby

...

Total

Base score: (54 + ... ) = 512

Unique techniques: 8

Final score: (512 / 8) = 64


Meta comments:

  • The goal of the rules is to 1) avoid trivial solutions and 2) encourage thinking about the next step while writing the current one. If the rules need to be added to enhance either aim, let me know.
  • Is ten functions too many? I could start the count at 5 if that seems better
\$\endgroup\$
  • \$\begingroup\$ I think 10 is good, as it encourages users to be ever more creative with each function. \$\endgroup\$ – mbomb007 Sep 10 '15 at 20:44
  • 2
    \$\begingroup\$ "Doing something meaningful" is very hard to make precise. \$\endgroup\$ – Peter Taylor Sep 10 '15 at 20:54
  • \$\begingroup\$ @Peter I defined it as having variable output based on the input. While something as simple as an if statement will cause that to happen, I think it might be OK when combined with the incentive for different techniques - 10 trivial "if input >=< something" routines won't be a very good score anyway as all techniques will be "comparison". Of course I'm open to better wording suggestions. :) \$\endgroup\$ – ThaddeusB Sep 10 '15 at 21:29
  • \$\begingroup\$ @ThaddeusB Great idea. +1 \$\endgroup\$ – mınxomaτ Sep 16 '15 at 3:21
2
\$\begingroup\$

The Algebra of Reflecting Points

This is a challenge based on manipulating points with a specific set of operations, each dealing with the reflection of some points over others.

Warning: There's not actually a challenge here yet, just the basis for a challenge that could be to "simplify the given expression" or something.

(I'll add more diagrams later)

Lists of Points

The fundamental object is an ordered list of points, like (A,B,C) or ([2,3],[5,8],[6,8]).

Reflection

A r B represents the reflection of point A across point B, resulting in a new point C so that B is the midpoint of AC.

A r (B,C,D) represents the reflection over a series of points, and is equivalent to A r B r C r D.

(A,B,C) r (D,E) represents (Ar(D,E),Br(D,E),Cr(D,E)), with either list being of any positive length.

The result of the reflection operator is a list of points that is the same length as the first operand. (If the first operand is a single point, then the output is a single point.)

A list with a single point is that same as that single point. (B) == B

Lists can be arbitrary grouped inside of other lists. (A,B,C,D) == (A,(B,C),D) == ((A,B,C),D)

Simplification

A point reflected over itself is an identity, CrC is the same as C. Any point reflected over the same point twice is an identity, rCrC can be removed.

(A,B,C) equals (C,B,A)

For any three points ABC there exists a unique fourth point D=C-B+A such that anything r (A,B,C) = anything r D. This means that any long chain of ArBrCrDrErF... can be reduced to have fewer than three rs.

((A,...,B)r(C,...,D)) == ((D,...,C),(A,...,B),(C,...,D)) and (ArB) == (B,A,B)

Examples

Show that `Cr(CrA)rB == Cr(BrArC)`

Cr(CrA)rB         #original
Cr(A,C,A)rB       #expanding 4th simplification rule
CrArCrArB         #the list is equivalent to a series of `r`s
CrAr(C,A,B)       #grouping to form a list
CrAr(B,A,C)       #swapping, the 2nd simplification rule
CrArBrArC         #expanding list
CrCrArBrArC       #Identity operation of C=CrC
Cr(C,A,B,A,C)     #listifying
Cr((C,A),B,(A,C)) #further grouping
Cr(Br(A,C))       #using the 4th simplification rule
Cr(BrArC)         #expanding parenthesis

Here is this proof visualized geometrically.

enter image description here

\$\endgroup\$
2
\$\begingroup\$

Whose Llama is it anyways?

BetaDecay posted a legit looking movie poster in chat, which got me into thinking that this could be a very nice challenge!

Your task is to overlay a nifty llama poster on top of a movie poster in a way that it still looks a legitimate movie poster. The image posted by Beta Decay is:

a http://pictures.boxxspring.com/pictures/960x0/100588

Your program will be provided with an input of fixed size (TBD) movie poster of any popular movie and a fixed llama cutout to overlay that poster as arguments. You may scale (proportionally), rotate or translate the llama cutout anywhere on the movie poster to make it look like a llama is photobombing the poster. At the same time, the output image should still look like a legitimate movie poster in a way the above poster feels real. You cannot perform any operations on the movie poster and no other operations on the cutout other than scaling, rotation and translation.

This is a popularity contest, so the answer with the most net votes wins. Voters are encouraged to judge answers by:

  • The correct placement of the cutout such that it does not outright look like a cutout
  • The scaling of the cutout to match with people/objects in the movie poster
  • The placement of the cutout with respect to the movie text. i.e. The cutout should not hide the movie title in a way that its no longer understandable.

Input

Two images in any common image format. The input can come as paths to the images or the images themselves (if your language support image input) either as function arguments, ARGV, STDIN or equivalent.

The first image (movie poster) will be of fixed resolution and the second image (the llama cutout) will be of enough resolution in order to have good quality even after scaling or rotation.

Output

A single image of the same resolution as the movie poster image in any favorable image format.

Llama Cutout

Please use this cutout as the second argument in your program:

[TBD]

Test Images

Here are a few images to test your algorithm on. Click on the images to get the actual resolution.

TBD

Please include some examples for these test images (along with other examples if needed) in your submission. Its also a good practice to briefly explain your algorithm as well.

\$\endgroup\$
2
\$\begingroup\$

Help Agent Zigzag with his secret messages

The WW2 double agent Eddie Chapman — aka "Agent Zigzag" — used an unusual cipher to communicate with his German controllers. It is described in the appendix of Ben Macintyre's book about Chapman and can also be viewed at the National Archives, apparently.

Read the following description and write a program to encrypt and decrypt messages using this system.

Your program should accept three inputs via stdin and/or command line switches:

  1. A keyword
  2. A flag to select either encryption or decryption
  3. A message to be encrypted or decrypted

The output should be the corresponding ciphertext/plaintext, arranged into groups of 5 letters separated by single spaces. You may assume that the keyword consists entirely of uppercase letters, but should accept plaintexts and ciphertexts containing mixed case characters, punctuation and spaces. Non-alphabet characters should be stripped from the input and should not appear in the output (which may only contain groups of 5 uppercase characters separated by spaces, with an optional line break at the end). The date value used for keyword processing should be obtained from the system clock using the local time zone.

This is a code-golf challenge. The shortest code (measured in bytes) will win.


1. Keyword processing

Write out the keyword, and below each letter write the position in which this letter would appear if the letters were all sorted alphabetically. If the same letter appears more than once, number them from left to right. For example, the 14-letter keyword CONSTANTINOPLE would be processed as follows:

C   O   N   S   T   A   N   T   I   N   O   P   L   E
2   9   6   12  13  1   7   14  4   8   10  11  5   3

(Notice how the three Ns are numbered 6, 7 and 8.) Combine this sequence of digits into a single number, and multiply by the current date (from 1 to 31). For example, if the transmission is being made on the 8th of the month:

2961213171448101153 x 8 = 23689705371584809224

2. Encryption

Pad the secret message to a multiple of five characters in length by appending the null character X as many times as necessary, then encrypt Vigenere-style by cycling each letter through the alphabet by offsets corresponding to successive digits of the number calculated at step 1. For example, the message

Have arrived safely and in good health. Awaiting further instructions.

is encrypted as follows:

havearrivedsafelyandingoodhealthawaitingfurtherinstructionsx << Plaintext
236897053715848092242368970537158480922423689705371584809224 << Key (repeated)
JDBMJYRNYLEXIJMLHCPHKQMWXKHJDSUMIAIICKPKHXXBQLRNQZUWCGBIXPUB << Ciphertext

because 'H'+2='J', 'A'+3='D', 'V'+6='B', etc.

Finally, read off the encrypted message in groups of five characters:

JDBMJ YRNYL EXIJM LHCPH KQMWX KHJDS UMIAI ICKPK HXXBQ LRNQZ UWCGB IXPUB

\$\endgroup\$
  • 1
    \$\begingroup\$ For languages that don't have system clock access, is it acceptable to take the date/time as an additional input? \$\endgroup\$ – Geobits Sep 23 '15 at 14:09
  • \$\begingroup\$ @Geobits Would you mind if I said no? We have so many code-golf questions that are dominated by esolangs, I thought it would make a change to have one that favours higher-level languages. (Although it looks like Pyth can do dates...) \$\endgroup\$ – squeamish ossifrage Sep 23 '15 at 14:55
  • \$\begingroup\$ I don't personally mind since I don't tend to use them. Some might, so I figured it was better to ask/clarify while it was sandboxed rather than on main. \$\endgroup\$ – Geobits Sep 23 '15 at 14:57
  • \$\begingroup\$ It's not just about esolangs: removing the direct coupling with the system clock allows test cases which work consistently. \$\endgroup\$ – Peter Taylor Sep 23 '15 at 20:19
  • \$\begingroup\$ @PeterTaylor But only 31 test cases are needed. \$\endgroup\$ – squeamish ossifrage Sep 23 '15 at 22:02
2
\$\begingroup\$

Well hello there, fellow golfers. The time has come for us to take part in the game. Time for the official Illuminati Confirmation!

Illuminati Confirmed?

Nah, just joking. We actually want to hide even better - by making conspiracy theorists look ridiculous.

For that, you need to create code in whatever language you want to. Your task is to print the Eye of Providence, as an ascii art. The program may take input, but it shouldn't rely on it.

However, there's a catch. You need to hide as many non-obvious references to Illuminati in source code as you can. One particular requirement is that your code must have an "Illuminati confirmed" sentence hidden somewhere(although it doesn't have to be plain string - in fact, it shouldn't; you can have it hidden by placing it as a first letter to every line, etc. - be creative!)

And because it's , the most upvoted and creative code wins!


Confirmed.


Now I want feedback before posting it - what else should I have in here? What is not clear? And if you come up with better "lore chit-chat"(I actually had no afflatus) - feel free to help me.

\$\endgroup\$
  • 7
    \$\begingroup\$ You need to hide as many non-obvious references to Illuminati in source code as you can: One problem you may run into is that I think it's been proven by the internet at large that you can make anything an Illuminati reference if you twist it enough. \$\endgroup\$ – Geobits Sep 24 '15 at 17:22
  • 2
    \$\begingroup\$ Also, pretty sure the Illuminati has already been confirmed since it was a real and historical secret society. \$\endgroup\$ – mbomb007 Sep 24 '15 at 17:56
  • 1
    \$\begingroup\$ @mbomb007 Nonsense! \$\endgroup\$ – MatthewRock Sep 24 '15 at 18:59
  • \$\begingroup\$ @Geobits What is your suggestion then? I am honestly counting on community, so some stupid answers like "Well, I have a word 'rock' rock is four characters, and four - 1 = 3, triangle also has 3 sides - Illuminati Confirmed" will be downvoted, and some clever ideas will get attention. \$\endgroup\$ – MatthewRock Sep 24 '15 at 19:05
  • \$\begingroup\$ This is an art / wordgame contest, not a programming contest. I'm not as strongly against this sort of thing as some, but there's a fair chance this will get closed. \$\endgroup\$ – Level River St Sep 24 '15 at 21:08
  • \$\begingroup\$ @steveverrill what I had in mind wasn't "Print the prettiest and funniest image and code, but rather to get people creative. This post is one of my inspirations - Perl and Brainfuck are bottles; C makes heavy use of macros to call the function in a funny manner, and while there are many other "plain" programs, the most creative are the most upvoted. This is similar to mine. There is more of that, buut looks like this shouldn't be closed. \$\endgroup\$ – MatthewRock Sep 24 '15 at 22:07
  • \$\begingroup\$ The 99 bottles of beer question is 4 years old and things were different back then. Nevertheless the issue was raised in the top comment on that question. There was a big attitude change just after the christmas tree challenge, in my opinion probably caused partially by Code Trolling. I'm not saying don't do it, just be aware of the issue. James Webster's recent cake question did quite well, though it did attract some close votes. The recent Back To The Future question was closed immeditately. \$\endgroup\$ – Level River St Sep 24 '15 at 22:35
  • \$\begingroup\$ @steveverrill I'm sorry, I have no idea what you're talking about. Could you please introduce me to the issue of Code Trolling, and provide some examples? \$\endgroup\$ – MatthewRock Sep 25 '15 at 8:29
  • \$\begingroup\$ Code Trolling was a particular class of open ended questions. The tag description is here. codegolf.stackexchange.com/tags/code-trolling/info It got out of hand. The history is too long and emotive to discuss in a comment, but it seems the challenges have been deleted. There are many meta questions on the subject. I've picked this one for you. meta.codegolf.stackexchange.com/q/760/15599 \$\endgroup\$ – Level River St Sep 25 '15 at 8:56
  • \$\begingroup\$ @steveverrill Okay, thanks for your insight. I will think about what you guys said, and maybe post the question - the worst that will happen is that iit will get closed - but hopefully it will spawn some clever and funny answers. \$\endgroup\$ – MatthewRock Sep 25 '15 at 9:21
  • \$\begingroup\$ Will an ASCII art version of the Eye of Providence be added in the question, or will we have to make one ourselves? \$\endgroup\$ – ASCIIThenANSI Sep 25 '15 at 15:52
  • \$\begingroup\$ @ASCIIThenANSI That's what I asked in other topic(well, I did it badly). I'm afraid to lock it to one particular output, because this way they can only get creative with code. What do you think? \$\endgroup\$ – MatthewRock Sep 25 '15 at 19:11
  • \$\begingroup\$ If you designed the exact Eye of Providence that we had to produce, it would go better as codegolf than popularitycontest. A good codegolf would require a fair amount of repetition in the pattern (compressing completely random strings is boring.) I guess it's fair to assume your design would be symmetrical. But since you want a popularity contest, just go for a popularity contest, and see if it flies high or if it gets shot down in flames. There's only one way to find out for sure, and you won't do it with meta posts. That said, Geobits makes a good point, that you need to address. \$\endgroup\$ – Level River St Sep 26 '15 at 9:39
2
\$\begingroup\$

1,2,3,4,...n-2,n,n-1


Your goal is, with an input "n", to print the numbers 1-n BUT the last two values are flipped. The numbers must be CSV (Comma separated values)

n must be >= 3 (And an integer)

For example, with an input n="10", your output should be as follows: 1,2,3,4,5,6,7,8,10,9.

An input with n="3", your output should be as follows: 1,3,2.

\$\endgroup\$
  • 3
    \$\begingroup\$ Get rid of the requirement that you can't just embed a string, please. How about printing 1,2,3,...,n-2,n,n-1 for a given input n? \$\endgroup\$ – Lynn Oct 3 '15 at 11:16
  • \$\begingroup\$ @Mauris Added this in, thanks for your input :) \$\endgroup\$ – Albert Renshaw Oct 3 '15 at 20:52
  • \$\begingroup\$ Shouldn't it be "last two values" instead of "last two digits"? In the example, the swapped items are 9 and 10, and 10 is not a digit. \$\endgroup\$ – Reto Koradi Oct 5 '15 at 5:14
  • \$\begingroup\$ @RetoKoradi Ahah good catch, edited it thanks! \$\endgroup\$ – Albert Renshaw Oct 5 '15 at 7:12
  • \$\begingroup\$ @FryAmTheEggman Got it in, thanks! \$\endgroup\$ – Albert Renshaw Oct 6 '15 at 20:21
2
\$\begingroup\$

Categorical logic [on hold]

Inspired by this question:

Task

The point of this challenge is to create a function or program that takes 3 short phrases and returns the logical assessment of the phrases.

Input

Each of the three phrases will be in the form: [All|Some] [A|B|C] are [A|B|C]., where the two A|B|C elements are different. The string Therefore,{space}, where {space} is a single space character, precedes the third phrase and reduces the initial capital of the third phrase to a lower case letter.

You may choose the input source and the separation of the strings. For example, STDIN with three concatenated phrases, text file, phrases separated by newlines, and taking the phrases as command-line arguments in quotes are all acceptable.

Sample input

With three concatenated phrases as example format.

  • Some tees are moos. All moos are yees. Therefore, all tees are yees. (output: falsy)
  • All A are B. All A are C. Therefore, some B are C. (output: ????)
  • All submissions are answers. Some submissions are winners. Therefore, some answers are winners. (output: truthy)

Output

  • Output for a logically correct combination of phrases must be a truthy value.
  • Output for a logically incorrect combination must be a falsy value. This is also the case if the input is logically unsound e.g. All A are B. No A are B. ...
  • Output for a logically uncertain combination must be the following string: ????

The output may be followed by a single newline.

Clarifications for finicky logic

  • Some is a subset of All. The following statement is badly written, but truthy: All A are B. All A are B. Therefore, Some A are B.
  • The following statement is also truthy: All A are B. All B are C. Therefore, some C are A.

Scoring

This is , so shortest code in bytes wins.

You may reduce your score by 10% if your values for A|B|C can contain spaces. You may assume that the value for A|B|C will not contain the word {space}are{space}).

You may reduce your score by a further 20% if your function or program also correctly handles No as input as well as All|Some.

Leaderboard

Standard leaderboard code goes here. Tag suggestions are welcome!

\$\endgroup\$
  • \$\begingroup\$ You should add what the expected output is for the sample imputs you give, so that one does not have to find if a sample is logically sound (and possibly be mistaken) \$\endgroup\$ – Fatalize Oct 13 '15 at 9:23
  • \$\begingroup\$ Working on a table of expected output. It's bigger than I had expected, and I haven't yet included 'No' as an option... \$\endgroup\$ – pbeentje Oct 13 '15 at 9:42
  • \$\begingroup\$ What is logically unsound about All A are B. Some A are B.? That's just equivalent to All A are B. There is at least one A. \$\endgroup\$ – Peter Taylor Oct 13 '15 at 13:27
  • \$\begingroup\$ @Peter Taylor, You're right. A couple of prods at the table has turned up logical differences for the same statement in different places. I don't have enough time to fix this right now, so am putting the question on hold until I can make a clear definition of required behaviour for different cases. \$\endgroup\$ – pbeentje Oct 13 '15 at 13:58
  • 2
    \$\begingroup\$ "All answers are submissions. Some submissions are winners. Therefore, some answers are winners." This doesn't seem truthy to me. A simple substitution: All cats are animals. Some animals are birds. Therefore, some cats are birds. \$\endgroup\$ – Geobits Oct 13 '15 at 17:08
  • \$\begingroup\$ In the few minutes at a time I'm spending on this, I'm struggling to be logically consistent. I feel that All A are B. Therefore, all B are A is false because of the presence of Therefore in the statement. My gut wants me to categorise All A are B. Therefore, all A are C as logically uncertain, yet applying the same logic this should actually be false (as should all logically uncertain combinations). I'll have a search but would appreciate it if anyone already knows of a definitive source. @Geobits: thank you, I've corrected that example. \$\endgroup\$ – pbeentje Oct 14 '15 at 14:08
2
\$\begingroup\$

An Assortment of Sorting

Sorting an array of integers in ascending order is one of the most fundamental tasks in programming. Indeed, there are many algorithms which exist to accomplish this. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages. So let's sort some integers!

Rosetta code features lists by sorting algorithm and language of idiomatic approaches to array sorting. However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to "Hello, World!", Is this number a prime?, and Golf you a quine for great good!.

Task

Write a full program that, when given an array of strictly positive integers, will print the ascending sorted version of the input array using one particular algorithm that is guaranteed to terminate.

The sorting algorithm used must be specified in the post. Note that bogosort is not allowed as it is not guaranteed to terminate.

Input

To ensure that the focus of submissions is on the mechanics of the algorithm rather than parsing input, a variable (with a name of your choosing) must be hard-coded in the program. However, the hard-coded value must be easily exchangeable; it may appear in only a single place in the entire program. For scoring purposes, submit the program that corresponds to the one-element array 1.

The elements of the array may be in their decimal representations, unary representations (using a character of your choice), as byte arrays (big or little endian), or as single bytes (if this is your languages largest data type).

All elements of the array can be assumed to be in the range 1 to 255, inclusive. Your program must be able to handle an array of any size from 1 to 255, inclusive.

Output

Output has to be written to STDOUT or closest alternative.

If possible, the output should consist solely of the sorted array with an optional trailing newline. The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

The output array can be formatted in any reasonable way. For example, [3,2,1] and 3 2 1 would both be fine.

Additional Rules

  • There should be only one language and algorithm combination per answer. Please submit separate algorithms in the same language or separate languages with the same algorithm as separate posts.

  • All submissions are required to feature some kind of explanation of the code.

  • Unless entirely unpreventable in your language, nothing should be output to STDERR.

  • This is not about finding the language with the shortest approach for sorting, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

  • Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

    The language Piet, for example, will be scored in codels, which is the natural choice for this language.

    Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

  • Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program sorts an array, then congratulations for paving the way for a very boring answer.

    Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

  • If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

  • Built-in functions for sorting with a particular algorithm are allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it. However, you must provide a link that proves that the built-in uses whichever algorithm you claim.

  • The input cannot be assumed to already be sorted.

  • Unless they have been overruled earlier, all standard rules apply, including the Loopholes that are forbidden by default.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers as a list of the shortest solutions per language and algorithm, as well as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language, Algorithm, N bytes

where N is the size in bytes of your submission. If you improve your score, you can keep old scores in the headline by striking them through. For instance:

# Ruby, Bubble Sort, <s>101</s> <s>96</s> 90 bytes

If you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, Insertion Sort, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

# [><>](http://esolangs.org/wiki/Fish), Heapsort, 121 bytes

Insert a super awesome snippet here



Meta questions:

  • Should this be restricted to specific set of sorting algorithms or is it okay to allow any deterministic algorithm?

  • Is the title okay? The catalog challenges tend to have straightforward, descriptive, searchable titles (with the notable exception of Golf you a quine for great good!). I figured this title is clear enough while still being interesting, but perhaps it's better to opt for something more straightforward.

  • At Peter's suggestion I've modified the input method. Arrays are now to be hard-code rather than being taken as input. This eliminates the need for parsing input. If I were to allow a variable to already exist, submissions would be snippets rather than full programs, which I don't want for this.

  • Is the closed interval [1, 255] appropriate for bounds on the integer values in the array as well as the length of the array? Is it better to make the array an arbitrary size?

\$\endgroup\$
  • 1
    \$\begingroup\$ If you require people to label their answers with the algorithm name, I guarantee you will have at least one argument in comments about the difference between bubble sort, insertion sort, and selection sort. \$\endgroup\$ – Peter Taylor Oct 21 '15 at 6:31
  • \$\begingroup\$ Are extremely inefficient solutions like "Check every possible permutation of the list" allowed, if they are guaranteed to terminate? I don't mind them but they almost don't seem like sorting algorithms :p \$\endgroup\$ – Fatalize Oct 21 '15 at 13:44
  • \$\begingroup\$ @PeterTaylor Do you think it would be best to scrap the entire part about choosing a specific algorithm? \$\endgroup\$ – Alex A. Oct 21 '15 at 16:19
  • \$\begingroup\$ @Fatalize I don't see why not. I'm sure that's already a documented sorting algorithm, however inefficient. \$\endgroup\$ – Alex A. Oct 21 '15 at 16:19
  • 1
    \$\begingroup\$ To be honest, I think this question is on such thin ice with respect to dupe votes (e.g. 49935, 40744, 26947, 36447, 12028, 20478, ...) that I'm not sure it's worth dedicating effort to. But if you are going to post it, I would make two big changes: 1. Make it per-language, ask people to explain their code (giving algorithm name and complexity where possible), and allow them to give alternative algorithms in the same answer. 2. Ditch the I/O. The point of the "catalogue" questions is to showcase basic computational building blocks, not I/O. \$\endgroup\$ – Peter Taylor Oct 21 '15 at 17:51
  • \$\begingroup\$ @PeterTaylor Is that per language, not per language/algorithm? And by ditching I/O do you mean allowing a variable to be defined containing the array (for example)? \$\endgroup\$ – Alex A. Oct 21 '15 at 17:58
  • \$\begingroup\$ Yes, and exactly. \$\endgroup\$ – Peter Taylor Oct 21 '15 at 18:36
  • \$\begingroup\$ @PeterTaylor Okay. I think I'm on board with the latter, especially since it's been difficult trying to come up with a truly convenient means of getting an array as input. Having it already defined scoots it a little closer to being a dupe of 49935 though. :/ But I think separating algorithms makes this more unique than the others. \$\endgroup\$ – Alex A. Oct 21 '15 at 18:49
  • \$\begingroup\$ @PeterTaylor I changed the I/O. Any better? \$\endgroup\$ – Alex A. Oct 21 '15 at 20:07
  • \$\begingroup\$ @PeterTaylor "and allow them to give alternative algorithms in the same answer." I think this is problematic because you'd still get multiple answers for each language, and if each language contains a few implementations they are spread out over the answers quite weirdly. That's why I suggested putting each algorithm in a separate answer and labelling it - then at least you know where to find each implementation (although I agree that the definitions of the different sorting algorithms aren't really applicable in some esolangs). \$\endgroup\$ – Martin Ender Oct 22 '15 at 7:37
  • \$\begingroup\$ @MartinBüttner, I don't see the problem. Maybe because I see it as a catalogue of sorting, and you see it as a merger of many separate catalogues for bubble-sort, insertion-sort, quicksort, etc? \$\endgroup\$ – Peter Taylor Oct 22 '15 at 7:47
  • \$\begingroup\$ @PeterTaylor I guess I'm just generally not a fan of multiple solutions in a single answer (even for a normal code golf, I'd rather just post two answers if the approaches are significantly different). \$\endgroup\$ – Martin Ender Oct 22 '15 at 7:51
  • \$\begingroup\$ @MartinBüttner, but if the question is presented as a catalogue of the shortest way to sort in every language then e.g. any answer in GolfScript other than $ would deserve to be voted to about -5. \$\endgroup\$ – Peter Taylor Oct 22 '15 at 18:35
  • \$\begingroup\$ @PeterTaylor It doesn't need to be presented like that. All I'm saying is that separate approaches should be kept in separate answers. Whether the leaderboard reads the algorithm from the header or not is a different matter. \$\endgroup\$ – Martin Ender Oct 22 '15 at 19:15
  • \$\begingroup\$ Regarding build-in functions: few language specifications clearly state which sorting algorithm has to be used, so all depends on the either the compiler/interpreter or the std library. The used algorithm may change over time, for example Cs (g)libc used to use quickersort (hence the name qsort) but switched to a mixture of algorithms depending on input size - the name remained. Therefore a C answer using qsort should also name the library version to be verifiable ... \$\endgroup\$ – nimi Oct 23 '15 at 15:01
2
\$\begingroup\$

Two mountain hikers want to meet, but must stay at the same altitude

This question is totally inspired by this question on Puzzling SE. For ease, I have reproduced the original question here:

Two hikers are separated by a two-dimensional mountain range, like the one shown below. The mountain range alternates between peaks and valleys, connected by straight lines.

enter image description here

Both hikers are at sea level, and the mountain range never dips below sea level.

The two hikers want to meet up with each other. Prove that they can do this while staying at the same altitude as each other for their entire journey. They are allowed to backtrack.

Source: http://www.cs.cmu.edu/puzzle/puzzle12.html

Input/Output

Meta: what input/output format would be better?

Continuous:

  • Input: a list of ordered pairs (x,y) that represent the peaks and valleys.
  • Output: a sequence of positions where one hiker or both changes direction, formatted like so:
(x1 y1) (u1 v1)
(x2 y2) (u2 v2)
(x3 y3) (u3 v3)
...

Discrete:

  • Input: a sequence of heights that represent the height of the terrain (with no flat portions). (I.e., 0 1 2 3 4 5 4 3 4 5 6 7 6 5 6 5 4 3 2 3 2 1 0, maybe with steps larger than 1?)
  • Output: the left/right moves each hiker has to make, outputted like
L R
L L
L L
R L
...

Scoring

  • Scoring is in bytes.
  • Bonus: -5% if your program produces optimal solutions.

Meta:

  • I'm pretty sure this is not a duplicate, but still, is it?
  • I'd like a better title. Would "Mountain Hikers" be good enough?
  • Any other feedback?
\$\endgroup\$
  • \$\begingroup\$ Is the input sorted? Also, I don't understand the first output format. \$\endgroup\$ – feersum Oct 29 '15 at 16:15
  • \$\begingroup\$ @feersum: Sorted in the x-direction, yes. The rationale behind the first output format is that as the hikers are moving, they're both moving in one direction (not necessarily together). However, when one reaches a peak or valley, the other will stop and change direction. The output should have the positions of the hikers at these moments. \$\endgroup\$ – El'endia Starman Oct 29 '15 at 19:25
  • 1
    \$\begingroup\$ I think that allowing the input to have deltas of more than 1 would potentially require the hikers to make fractional steps, which would certainly complicate the spec. I don't think the bonus has any point: if you look at the many many existing questions about reachability in a graph (which is what this is), I think you'll find that most of the answers do breadth-first search and thus produce optimal solutions. \$\endgroup\$ – Peter Taylor Oct 29 '15 at 22:21
  • \$\begingroup\$ @PeterTaylor: Yeah, I realized last night that delta > 1 is a problem in the discrete case (if I want hikers to always be at integer steps). You're probably right about the bonus being pretty much useless. \$\endgroup\$ – El'endia Starman Oct 29 '15 at 22:24
2
\$\begingroup\$

Bridge Flowers


One of the example inputs for this challenge is a really minor puzzle in Undertale, and the example output is the solution. You have been warned.

In the Underground, there is a mysterious plant known as the Bridge Flower. They always come in groups of four Bridge Seeds, and have some interesting properties:

  • When dropped in water, a Bridge Seed floats away from you in the direction you were facing when you dropped it. It floats until it hits a wall or another Bridge Seed, at which point it stops moving.
  • If four Bridge Seeds are touching, forming a straight line, and none of them are moving, they will bloom into Bridge Flowers. Bridge Flowers can support a monster's weight (or a human, but when will that ever happen?), hence the name.
  • Another mysterious plant, the Bell Blossom, has a special interaction with Bridge Flowers. The Bell Blossom can be rung to turn all Bridge Flowers back into Bridge Seeds and return them to their original spot.

Consider this map, where . is ground, is water, and X is a Bridge Seed. You'll always be on the part of the map where the Bridge Seeds are. The gap is only four tiles wide, so it's quite easy to make a bridge of Bridge Flowers.

........    ........  |  ........    ........
..X.....    ........  |  ........    ........
.X.X....    ........  |  ........XXXX........
..X.....    ........  |  ........    ........
........    ........  |  ........    ........

Here's a slightly more difficult gap to cross. Even though the straight-line distance is longer than four tiles, you can make it across with a little bit of thought.

........       ........  |  ........       ........
..X.....       ........  |  ........       ........
.X.X....       ........  |  ........       ........
..X.....       ........  |  ........       ........
........       ........  |  ........       ........
..         ............  |  ..     XXXX............
..         ............  |  ..         ............

Here's one that's even trickier than the last two. Most of this river is three tiles wide or fewer, so you can't simply make a straight-line bridge across! Thinking outside the box, though, you'll arrive at the solution.

....   ............  |  .... X ............
...   .............  |  ...  X.............
....   ............  |  .... X ............
.....  ............  |  .....X ............
....   ...X.X......  |  ....   ............
....   ...X.X......  |  ....   ............
     ..............  |       ..............
       ............  |         ............

For this challenge, write a program or function that takes a map like the ones here and outputs the same map, but with the puzzle solved (the Bridge Seeds moved to the final position of the Bridge Flowers). If there's more than one possible answer, any of them will do. You may assume there will be exactly two areas of land separated by water, with the one that you start on denoted by the presence of exactly four Bridge Seeds.

If the program can't find an answer... well, just because it's impossible doesn't mean you should give up! Don't lose your Determination! Output Ding to sound the Bell Blossom, reset the Bridge Seeds and try again!

\$\endgroup\$
  • \$\begingroup\$ It took me quite a while to understand the examples. At the very least I think you need to explain that you can pick up bridge seeds from the ground, and clarify "floats until it hits a wall or another Bridge Seed" to define hits. (I think it must include being adjacent to in directions perpendicular to the direction in which it's floating - or am I missing something?) It might also be worth stating explicitly that you don't have to drop them all from the same point. \$\endgroup\$ – Peter Taylor Nov 5 '15 at 22:07
2
\$\begingroup\$

Based on this question in the Puzzling SE. Not 100% sure on the scoring, and this is my first time posting a PPCG challenge, so I'd appreciate any suggestions on improving it.


Unicode Box Drawing

Write a program which outputs a diagram using all of the standard Unicode box drawing characters:

─ │ ┌ ┐ └ ┘ ├ ┤ ┬ ┴ ┼
═ ║ ╔ ╗ ╚ ╝ ╠ ╣ ╦ ╩ ╬
    ╒ ╕ ╘ ╛ ╞ ╡ ╤ ╧ ╪
    ╓ ╖ ╙ ╜ ╟ ╢ ╥ ╨ ╫

The diagram should have no loose ends, so:

┌┐ <-Allowed  ┌┐ <-Not allowed  ┌┐┌┐ <-Allowed
└┘            └┴                └┴┴┘

Also, single lines should line up with other single lines, and double with double:

├─, ╟─, ╠═, ╞═ <-Allowed  ├═, ╟═, ╠─, ╞─ <-Not allowed

The diagram must use each of the 40 characters at least once, and must form one contiguous, connected shape. Because the characters might look different depending on your browser font, do not consider the space between double lines to be an actual separation. Separations can only be between two characters. In other words:

┌╖ <-Allowed  ┌┐┌┐ <-Not allowed
└╜            └┘└┘

Your code must compute the diagram from scratch. You may not create an already existing diagram and just print it out. A bonus of 20% will be awarded if your program outputs a different valid diagram based on a random seed. (This seed may be provided as input, or you may use system time, read the seed from a file, or any other means you choose.) Note that a random seed may be provided externally, but the diagram itself may not. If you implement this bonus, please provide multiple examples showing different output.

This is code-golf, so scoring will be based on the number of bytes in the source code. In addition, the length of the output will also be counted. You get 40 characters free to account for the required characters. Any additional characters will come at a 10% penalty. This includes spaces/tabs, and any duplicate graph pieces. Newlines are free (to be fair to the differences between OSs).

If your program produces multiple outputs of different lengths (due to randomness), you may use the shortest output produced, but you must provide a seed that results in that output so it can be verified. Since this might be difficult if you used system time as a seed, entries using system time must somehow prove that they are capable of producing the smallest claimed output. (For instance, if they produce the same length output every time, or produce the minimum claimed output at least 50% of the time.)

So in summary:

  • Take length of source code in bytes.
  • Add 10% for each whitespace character (not counting newlines) or duplicated character in the output.
  • Subtract 20% if you implement the random seed input.

Standard loopholes apply.

\$\endgroup\$
  • 2
    \$\begingroup\$ "You may not create an already existing diagram and just print it out." This is probably too fuzzy. There many shades of hardcoding. Starting from including the string plainly in the code, over decoding a Base64-string which magically happens to give the correct result, all the way to "cleverly" pruning the possible diagrams your code tries to find, because you know there is a valid one in the search space. You can work around all of that by requiring programs to take some input: e.g. the actual set of characters that need to be accounted for. \$\endgroup\$ – Martin Ender Nov 4 '15 at 15:22
  • \$\begingroup\$ Additionally, this might make an interesting code challenge instead of code golf. \$\endgroup\$ – Martin Ender Nov 4 '15 at 15:22
  • \$\begingroup\$ You should probably also define contiguous, because some of the answers on the Puzzling.SE question have shapes which don't look contiguous (but are considered contiguous) because they have gaps inside the double-line characters (e.g. the "separate" box in the top left corner in the second example of the accepted answer). \$\endgroup\$ – Martin Ender Nov 4 '15 at 15:24
  • \$\begingroup\$ @MartinBüttner This problem is caused by different rendering of the unicode characters. Here is how it looks in the SE Android app: i.stack.imgur.com/PlQWI.jpg \$\endgroup\$ – Sleafar Nov 4 '15 at 16:05
  • \$\begingroup\$ @Sleafar Oh, interesting. Might be worth mentioning anyway if some fonts display it differently. \$\endgroup\$ – Martin Ender Nov 4 '15 at 16:07
  • \$\begingroup\$ Yeah, most fonts I've seen they look like they do in Sleafar's image. For whatever reason, the one used on SE does not. I think it would probably be much harder if you considered those double lines to be actual separations. As for the hardcoding, I didn't want this to be just another "Print out <blah>" challenge, there's tons of those. It's much more interesting if you have to derive such a graph in code. (Which is why I added the bonus for using a random seed, because then you KNOW it's being generated on the fly.) \$\endgroup\$ – Darrel Hoffman Nov 4 '15 at 17:56
  • \$\begingroup\$ To avoid the hardcoding issue, I'd suggest generalizing the puzzle in some way, perhaps by giving a multiset of components to use. \$\endgroup\$ – xnor Nov 4 '15 at 21:51
  • \$\begingroup\$ Problem with using a multiset of input is you'd now have to validate said input to make sure that it's even possible to create a graph with no loose ends using the given inputs. I think the idea of using an input parameter which is just a random seed should be sufficient to ensure the results were not hard-coded in some way. Also, there's nothing stopping you from hard-coding it and printing the same thing every time, you just won't be eligible for the 20% bonus that way. (Is 20% enough? I feel like generating a valid graph is orders of magnitude more difficult than just printing one...) \$\endgroup\$ – Darrel Hoffman Nov 4 '15 at 22:52
  • \$\begingroup\$ You could take the multiset as input and require that at least the characters in it have to be used, possibly others. The scoring could combine source code size and output size for a set of test cases. \$\endgroup\$ – Zgarb Nov 5 '15 at 2:16
  • 1
    \$\begingroup\$ I don't like the idea of using preset test-cases except as examples. For one, it makes it possible to hardcode valid graphs for just the test-cases, which is contrary to the spirit of the challenge. Also it limits the challenge to a few already-solved cases instead of making it more general. As Sleafar found in his answer in puzzling, there are many perfect solutions for a given set, and I wouldn't want everyone to just use the same algorithm and thus produce the same graph. I could see providing some examples, but I don't want to use only the example input for scoring purposes. \$\endgroup\$ – Darrel Hoffman Nov 6 '15 at 14:21
2
\$\begingroup\$

Find pattern in pixel carpet

[insert story why this needs to be as short as possible]

Given an image the goal is finding the biggest* connected* pattern of pixels, that occurs more than once. If there is more than one distinct pattern of maximum size, find the one that occurs more.

The output should consist of mask (bw image) of the size of the input, that is black where the copies of the pattern were on the original image, and white otherwise.

* Specs

  • Biggest as in number of pixels
  • connected means four connected

Two instances of the pattern must not overlap.

Example

enter image description here

enter image description here

Meta

  • consider rotations / mirroring of the patter too, or only translations?
  • runntime requirement?
\$\endgroup\$
  • 3
    \$\begingroup\$ "You are a carpet salesman who is looking for stains in a carpet to maintain your reputation. However, since you are locally known as the 'guy who sells dirty carpets', you don't have the money to buy new hardware, and you only have a tiny hard drive and a terrible camera to try to find them with. Therefore, you're going to need a really small program in order to try to find these stains." \$\endgroup\$ – Addison Crump Nov 7 '15 at 18:53
  • \$\begingroup\$ @VoteToClose Then it must be runnable in embedded system? A Raspberry Pi, maybe. \$\endgroup\$ – Akangka Nov 16 '15 at 15:18
  • \$\begingroup\$ @ChristianIrwan Let's say it is an arduino=) \$\endgroup\$ – flawr Nov 16 '15 at 20:32

You must log in to answer this question.

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