467
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – James Aug 29 '19 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – S.S. Anne Sep 26 '19 at 15:57
  • 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 '19 at 13:43

2696 Answers 2696

1 25 26 27 28 29 90
1
\$\begingroup\$

Fundamentals of City Planning

In this challenge, you are a city planner. You have been given an N by M rectangle to fill with residential lots of size K and roads of width 1. You know that money is made based on the number of residents in the city, so your goal is to maximize the number of lots in your rectangle. However, the following rules are enforced:

  • Roads have a width of 1 square, and all roads must be orthogonally connected to each other.
  • Every lot must share at least 1 side with a road
  • Lots must all be the same size K. They can be in the shape of any polyomino of size K.
  • There must be at least 1 road that touches the edge of the rectangle, as your residents need to be able to get in and out!

The winner of the challenge is the one that:

  1. Fits the most lots across all of the below examples. In the case of a tie:
  2. Fastest solution, unless multiple answers are running under a second. In that case:
  3. The earliest posted solution

Submitted answers must run in under a minute.

STDIO

You will be passed three integers, N, M, K. You need to output the generated grid. Roads should be represented by .. Lots should be ordered and numbered, and when printed should be represented by their number mod 10. The ordering can be arbitrary, and is simply used to distinguish lots on output. Empty squares are allowed and are represented by #.

Test Cases for correctness

Provided solutions can be numbered differently, rotated, and/or reflected

1 2 1 
.1

1 3 1
1.2

2 2 1
1.
2.

3 3 1
123
...
456

3 3 2
11#      11.      #11     
2..  or  2..  or  2..
233      233      233

Test cases used for scoring:

20 15 1
20 15 2
20 15 3
20 15 4
20 15 5
20 15 6
20 15 7
20 15 8
\$\endgroup\$
  • \$\begingroup\$ 1. I got to the bit about lots being the same size K and wondered why I would choose K to be anything other than 1. Only when I got to the input spec did I understand. Adding "of size K" to the end of the second sentence would probably avoid that confusion. 2. Do you have a reference implementation? I'm worried that "fastest solution" might not be a good tiebreaker because on the given test cases the answers may execute in under 200ms. \$\endgroup\$ – Peter Taylor Jul 4 '15 at 6:52
  • \$\begingroup\$ I updated, tell me if it looks reasonable? \$\endgroup\$ – Nathan Merrill Jul 4 '15 at 11:45
  • \$\begingroup\$ Are answers required to be deterministic? \$\endgroup\$ – trichoplax Jul 4 '15 at 13:53
  • \$\begingroup\$ @trichoplax no, but deterministic will probably lead to better results. Updated the description. \$\endgroup\$ – Nathan Merrill Jul 4 '15 at 14:46
1
\$\begingroup\$

Catch the robber

This is my first time making a KOTH. I (mostly) will not post this KoTH. Read the ReadMe file for more info.


Overview

A cop spots a robber and the robber runs and ends up in a basement. The cop then goes into the basement and locks the door.

Gameplay

The basement consist of 49 rooms with dimensions 7 x 7. The top-left room has coordinates [0,0] while the bottom-right room has coordinates [6,6]. The cop starts on the room with coordinates [6,3] while the robber starts on the room with coordinates [0,3].

Cop

The cop moves first. The cop can move in one of these directions:

  • Up
  • Right
  • Down
  • Left
  • Here

The direction here indicates that the cop will stay in the current room and will not move. The rest of the directions are self-explanatory. The cop can move in a particular direction if it is a valid one, i.e, the cop cannot move out of the grid or move into a room with a trap.

The cop can also put traps in a room. At the start of every match, the cop has 3 traps. Once a trap has been placed, the cop will not be able to move into the room where the trap is placed.

The cop also has 3 pressure sensors at the start of every match. The cop can move into a room where a pressure sensor has been placed.

If the robber moves into an adjacent room of the cop, the cop will be alerted.

Robber

The robber can move in the same directions as the cop does. The robber too cannot move outside the grid.

The robber has two TrapDetector5000 which can be used by the robber. It will detect if there is a trap in one of the adjacent rooms that the robber is in.

If the cop moves into an adjacent room of the robber, the robber will be alerted.

Goal

The cop must catch the robber as soon as possible. This can be done by moving into a room where the robber is. The cop will also catch the robber if the robber moves into the room where the cop is.

If the robber moves into a room where the cop has placed a trap or a pressure sensor, the cop will be alerted and the robber will not be able to move for 2 turns, if the room had a trap. However, the robber will be able to move if the room had a pressure sensor.

The robber will be alerted if the robber steps into a room with a pressure sensor.

Controller

The controller is written in java and can be found here. As a cop or a robber you each have to each complete implement a Java class.

You have to implement the Cop interface if you are writing a Cop Bot and implement the Robber interface if you are writing a Robber Bot.

There is an enum direction with 5 directions Here, Up, Right, Down, Left which you can use when building your Bot.

You can use the Grid.isValidMove(direction) to check if that direction is a valid move. This is for Cops.

You can use the Grid.isValidPosition(direction) to check if that direction is a valid move. This is for Robbers.

You also may write additional functions within that class. The controller comes with one working example of a simple cop and robber bot.

Please use java 7 and please do not exploit stuff in the controller and cheat.

Note that your bot needs to return an int from takeTurn within 200 milliseconds. Failure to do so will result in the disqualification of your Bot.

Scoring

Each cop plays 10 rounds against each robber and the number of moves each robber makes in each round will be added up and this is the score of that particular robber. The same goes for cops.

The robber with the highest score and the cop with the lowest score wins!

\$\endgroup\$
  • 2
    \$\begingroup\$ This KoTH has potential, I believe. I might expand the room to ensure that traps aren't an insta-catch. Also, if a cop moves into a room next to a robber, only the robber knows? (and vice versa)? If that is true, its going to hard to beat the robber strategy of "stand until a cop moves next to you" \$\endgroup\$ – Nathan Merrill Jun 27 '15 at 2:08
  • \$\begingroup\$ First of all. Thanks for reviewing this KoTH. What size should the grid be? And "if a cop moves into a room next to a robber, only the robber knows? (and vice versa)?" -- Yes. Because this is different from those KoTHs where a turn means movement of both the players. Any idea for making it more interesting? \$\endgroup\$ – Spikatrix Jun 27 '15 at 8:15
  • \$\begingroup\$ I'd say that a 7x7 would be sufficient. If I am caught in the center, it is still possible that the cop won't catch me if he is on the edge of the room. I'm not sure how to make it more interesting, but an idea I had would be to allow both the cop and robber to place "pressure sensors" instead of traps. Their party is informed when stepped on, but they don't know which sensor has been stepped on (unless there is only 1 they placed) \$\endgroup\$ – Nathan Merrill Jun 27 '15 at 11:52
  • \$\begingroup\$ "Their party is informed when stepped on" -- Party? There is just one cop. Should there be more than one cop? \$\endgroup\$ – Spikatrix Jun 27 '15 at 11:59
  • \$\begingroup\$ No. I just used party to refer to either cop or robber depending on who placed it. \$\endgroup\$ – Nathan Merrill Jun 27 '15 at 12:04
  • \$\begingroup\$ I was thinking of cops having 2 traps + 4(?) pressure sensors. Also, I've been thinking of giving robbers something... like a dummy (moves in a straight direction and tricks the cops will be alerted if it is in an adjacent room) or one trap-detector-5000 (which detects if there if there is a trap in an adjacent room and can be used only once). What do you think? \$\endgroup\$ – Spikatrix Jun 27 '15 at 12:28
  • \$\begingroup\$ I'm not sure about the dummy idea. I think that this challenge is about calculating probabilities of the enemy's location. I'd personally would prefer abilities to be purely knowledge granting, but that's my opinion. \$\endgroup\$ – Nathan Merrill Jun 27 '15 at 13:37
  • \$\begingroup\$ @NathanMerrill I've written some code, but I don't think I'll post this. See the answer for more info. \$\endgroup\$ – Spikatrix Jul 7 '15 at 9:01
1
\$\begingroup\$

Blackjack

How to Play

Blackjack is for any number of people, but there will be only one in this case. The goal is to get as close to 21 as possible without going over. Aces will be 1 for this program. All other face cards are worth 10.

To start, the player is dealt two cards. They can then choose to hit (take another card) or stand. This repeats until they go over 21 (bust) or decide to stay.

If the player busts, their score is 0. Otherwise, their score is the total of all the cards.

Input/Output

  1. The program should output 2 "cards" (randomly choose between 2, 3, 4, 5, 6, 7, 8, 9, 10, K, Q, J, and A).
  2. The player then inputs a move, stand or hit.
  3. If he/she stands, output Final Score: [total of cards].
  4. If he/she hits, output another "card". Output Bust! if the score is over 21.
  5. Repeat steps 2-4 until the player busts or stands.

Test Cases

Output: 5 K
Input:  hit
Output: 6
Input:  stand
Output: Final Score: 21



Output: A Q
Input:  hit
Output: 7
Input:  hit
Output: 6
Output: Bust!

Rules and Other Notes

  • Aces are always 1.
  • Each output/input should be on a new line.
  • Any trailing spaces and newlines are okay.
  • Assume that all input will be valid. You don't need to notify the player of invalid input.
  • You cannot read from a file or other source.

Scoring & Submissions

  • This is code golf. Shortest code in characters wins.
  • How to win: post the shortest working code within one week.
  • Please include the language, number of characters, and code. Explanations are appreciated, but not required.

Good luck!

Tags

, ,

Sandbox Questions

Anything I'm forgetting? Does anything need more clarification?

\$\endgroup\$
  • \$\begingroup\$ @TNT code-golf, game, card-games. I'll edit my post. \$\endgroup\$ – Nick B. Jul 11 '15 at 2:54
1
\$\begingroup\$

roll me back a game of hearts

Roll me back a game of hearts
given just a deck of cards
please.

So, I've been playing a game of hearts (https://en.wikipedia.org/wiki/Hearts) with three of my friends but I'm not entirely sure if all of them were playing perfectly according to the rules. So I'd like to replay the game with everyone's cards openly visible. And because you like algorithms, you offered me your help determining everyone's cards from the final deck after each hand. However, I can't quite remember if you promised me a full program or just a named function.

A card is represented with two characters. The first character represents its value and is one of 23456789TJQKA (2-10, jack, queen, king, ace). The second character represents its suit and is one of CDHS (clubs, diamonds, heards, spades).

The input is a list of 52 cards. It can either be a list (array, vector...) of two-character strings or a single space-separated string. You will be given the cards in the exact order they were played. The list represents a valid deck and 2C is the first card in the deck.

Output four sets of cards, each representing the starting hand of one player. The first set may correspond to any player but the rest must be ordered in the order of play (so if the first hand to be output is the third one to play, the rest must be in the order of fourth, first, second). The cards in each player's hand may be output in any order (it's a set). If you choose to output a single string, separate the cards in each hand with spaces and the hands with newlines.

Game rules:

Rules irrelevant to this challenge have been formatted in small font

  • There are variants for three to six players but the base variant is for four players so let's assume this one.
  • Before the main game each player passes three cards to another player. Since this is a lossy operation, let's just ask for the hands after this passing moment.
  • Each game consists of 13 tricks. Each trick consists of each player in clockwise order playing one card from their hand, then one player "taking" the trick.
  • The first trick starts by the two of club. Each subsequent trick is started by whichever player took the previous trick.
  • The first player in a trick can play any card. The first player cannot play hearts unless hearts have already been played in that game or he has no other cards, however. The other players have to play the same suit as the leading player if they have that suit, otherwise they can play any card. Scoring cards cannot be played in the first trick
  • The player that played the highest valued card of the same suit as the leading card of that trick takes that trick. E.G.: in 2C AD KC 5C, the king of clubs takes the first trick. In 2H KS AS QS the leading player takes the trick (and fourteen points).
  • The objective of the game is to end up with the fewest points possible. A player gets one point per each hearts taken, and 13 poins for the queen of spades.

You may assume that the deck of cards is valid (exactly one of each card) and that the two of clubs has been lead. You may also assume that the rules concerning the order of play and trick taking have been followed. You may not assume the rules concerning which cards can be played when have been followed. Heck, you don't even know that I haven't been cheating. Because a player may have been dealt nothing but hearts, you may not even assume only non-scoring cards have been played in the first trick (if everyone on the planet plays 100 games in their life, this may realistically happen to someone).


Should I loosen the I/O requirements? How much?
Formatting advice? Which parts (if any) should I trim down? What needs to be clarified?
Anything else?

\$\endgroup\$
  • \$\begingroup\$ So the program you're asking me to write can actually ignore most of the rules of Hearts and I can think purely in terms of a no-trump game in any whist-like game? \$\endgroup\$ – Peter Taylor Jul 13 '15 at 12:13
  • \$\begingroup\$ @PeterTaylor Correct. Spades does have trumps, however, and hearts is the only other whist-like game I've played. \$\endgroup\$ – John Dvorak Jul 13 '15 at 12:17
1
\$\begingroup\$

How to Create a Dating Website

Dating websites make lots of money. You want lots of money, so you're going to make a dating website. However, we all know that the most important part of any dating website is the algorithm, so you need to build that first.

When your customers will sign up, they are going to fill out a short survey describing themselves*. On the survey, they filled out personal interests, personality traits, and other important data for you to process using your algorithm.

Your algorithm must then accept two things:

  1. A list of people, where each person has a list of traits
  2. A list of trait pairs (A, B), where each pair has a score S. A trait pair matches a couple if one of them has trait A, and the other has trait B. The score can be negative. If A and B are different, and both people have both of the traits, then the score is doubled.

Your algorithm must then output a list of couples. Each person must be included in a couple exactly once, and only two people is allowed in each couple**. Your score is the sum of each couple's score. A couple's score is the sum of each of the trait pairs they match.

Input/Output

Input is given as shown in the following example. Ignore the # comments

4         # Number of customers
1,3,5,7   # Customer 1's list of traits
1,2,4,5,6 # Customer 2's list of traits
1,6,7     # Customer 3's list of traits
1,2       # Customer 4's list of traits
4         # Number of trait pairs
1,2,-2    # Trait 1 and 2 give a score of -2
1,6,4     # Trait 1 and 6 give a score of 4
2,3,-4    # Trait 2 and 3 give a score of -4
6,6,5     # Trait 6 and 6 give a score of 5

Let's say you output:

2,3 1,4

Then that would match Customer 2 to 3 and 1 to 4.

If we look at 2,3, they match:

  • The first trait pair, because Customer 3 has Trait 1, and Customer 2 has Trait 2
  • The second trait pair, because they both have Traits 1 and 6. (This means double the score)
  • The fourth trait pair, because they both have trait 6. However, because the trait pair only references 1 trait, we don't double the score.

Adding it all up, we get -2 + 4*2 + 5 = 11. The other couple scores -2 + -4 = -6, so the final score is 11 + -6 = 5.

The person who generates the highest scoring pairing wins the challenge. In the case of a tie, the program that generates it the fastest wins. If programs are generating the answer in under a second, then the earliest posted answer wins.

Question: I'm planning on doing 10K people, 500 traits, an average of 50 traits per person, and 5K trait pairs. I'm doing large numbers because I want efficient algorithms, but I want to know if the numbers are feasible

*They clicked a check box saying that they didn't lie, so we know that the survey is accurate

**You can assume everybody is a hermaphrodite

\$\endgroup\$
  • \$\begingroup\$ FYI there's a well-known polynomial-time algorithm. \$\endgroup\$ – feersum Jul 13 '15 at 4:25
  • 1
    \$\begingroup\$ @feersum, that's for weighted matchings in bipartite graphs. This is maximum weight matching in a complete graph, for which the well-known polynomial-time algorithm is Edmond's blossom algorithm. PS Nathan, if you don't want a debate about your cover story, you should probably specify that this dating site is aimed specifically at bisexuals. \$\endgroup\$ – Peter Taylor Jul 13 '15 at 6:08
  • \$\begingroup\$ ... or hermaphrodites. Poor snails, perpetually being asked about their gender and not being able to reply "both". \$\endgroup\$ – John Dvorak Jul 13 '15 at 8:31
  • \$\begingroup\$ stdio is a standard header file for input and output functions in the C language. Why is it mentioned in this problem? \$\endgroup\$ – aditsu quit because SE is EVIL Jul 13 '15 at 10:11
  • \$\begingroup\$ @aditsu STDIO stands for "Standard I/O" \$\endgroup\$ – Nathan Merrill Jul 13 '15 at 12:39
  • \$\begingroup\$ Yes, and that doesn't change anything I said. \$\endgroup\$ – aditsu quit because SE is EVIL Jul 13 '15 at 15:14
  • \$\begingroup\$ @aditsu then I don't see your point. I'm describing how to input/output (and giving an example at the same time) \$\endgroup\$ – Nathan Merrill Jul 13 '15 at 16:51
  • \$\begingroup\$ My point is STDIO specifically refers to the C header file. What you are then actually showing is example input. If it really was stdio, I would expect some C macros and declarations. \$\endgroup\$ – aditsu quit because SE is EVIL Jul 13 '15 at 17:54
1
\$\begingroup\$

LindenMASM

LindenMASM is an Assembly-like programming language which can be used to generate images from Lindenmayer systems. Lindenmayer systems are very interesting in the fact that they can provide a rudimentary method of generating fractals, such as a Sierpinski triangle. They are also interestingly able to mimic nature very closely for some reason, which can be seen in the below image. You will be implementing a LindenMASM interpreter in a language of your choice.

Understanding Lindenmayer Systems

You should check out the Wikipedia page for a more detailed overview of Lindenmayer systems, as I will simply describe the process of actually using a system. I will be referring to a turtle in this explanation. A turtle is simply the device by which an L-system is drawn. We will use a dragon curve L-system as an example.

Firstly, we need to consider the variables we will be using. In the case of an L-system, a variable is used to control evolution, and does not actually correspond to any movement. We will need two for this, so let's call X and Y our variables.

Next, we would define our constants. In most L-Systems, the character F refers to moving forward, - turns left and + turns right. We will follow these conventions here, and specify that - turns the turtle 90 degrees left and + turns the pointer 90 degrees right.

After this, the axiom needs to be defined. This is the starting point of the system, i.e. what it looks like after 0 iterations. In our case, we will set it to FX.

Finally, we need to define some rules. Rules are applied by going through each character of the axiom, and if one of them matches a rule, replace it with the defined set of instructions. Our rules are that X -> X+YF+ and Y -> -FX-Y. I will show a quick evolution of steps, so you can see how these rules are applied.

  • n=0 - FX
  • n=1 - FX+YF+
  • n=2 - FX+YF++-FX-YF+
  • n=3 - FX+YF++-FX-YF++-FX+YF+--FX-YF+
  • n=4 - FX+YF++-FX-YF++-FX+YF+--FX-YF++-FX+YF++-FX-YF+--FX+YF+--FX-YF+

When this is interpreted, however, since X and Y don't control movement, the interpreted steps for n=4 would look like this:

F+F++-F-F++-F+F+--F-F++-F+F++-F-F+--F+F+--F-F+

Simplified..

F+F+F-F+F+F-F-F+F+F+F-F-F+F-F-F+

Which would result in the following drawing:

n=4 Dragon Curve

Syntax

There are only a few keywords available in LindenMASM which you will need to implement.

  1. STT - Begins every LindenMASM file.
  2. AXI $ - Sets the axiom (initial state) of the system.
    • $ is a series of commands/variables/constants, ranging from the built-ins plus any user-defined functions.
  3. DEG $ - Sets the degree of which all turns will follow.
    • $ will be a integer or float between 0 and 359, inclusive. The default value is 90 otherwise.
  4. MOV $ - Sets the move distance of which all position adjustments will follow.
    • $ will be a integer or float between 1 and 100, inclusive. The default value is 10 otherwise.
  5. INC $ - Sets the number of iterations the generation should go through.
    • $ will be a number between 0 and 30, inclusive. The default value is 0 otherwise. (a value of 0 means just the axiom is displayed).
  6. SET $ # - Sets a constant $ to a specified command #
    • $ will be a letter between A and Z, inclusive, and will be uppercase.
    • # will either be a 0 or a 1, where a 0 corresponds to the constant being one that draws forward, and a 1 corresponds to the constant being one that moves fowards.
  7. RPL $ # - On every iteration, variable/constant $ will be replaced with the command/variable/constant string #.
    • $ will be a letter between A and Z, inclusive, and uppercase. It does not need to be SET to be replaced.
    • # is a string of commands/variables/constants that $ should be replaced with.
  8. END - Ends every LindenMASM file.

Each keyword should be placed on a new line. Your program should fail parsing if (a) The file does not start with STT or does not end with END. Your program should assume that the rest of the keywords will have proper arguments attached to them.

Below is a list of all of the regular commands that cannot be defined by the user:

  1. + - Rotates the pointer to the right DEG degrees.
  2. - - Rotates the pointer to the left DEG degrees.
  3. [ - Saves the pointer's coordinates and heading to a list.
  4. ] - Pops the last value of a list and sets the pointer's coordinates and heading to that.

Examples

I will give 5 examples, each of which will have detailed information on the pattern, plus a link to have it visualized online.

Fractal Tree - n=6, axiom=X, Θ=25, X->F-[[X]+X]+F[+FX]-X, F->FF (Test Online)

STT
AXI X
DEG 25
MOV 10
INC 6
SET F 0
RPL X F-[[X]+X]+F[+FX]-X
RPL F FF
END

Fractal Tree

Gosper Curve - n=4, axiom=F, Θ=60, F->F+G++G-F--FF-G+, G->-F+GG++G+F--F-G (Test Online)

STT
AXI F
DEG 60
INC 4
SET F 0
SET G 0
RPL F F+G++G-F--FF-G+
RPL G -F+GG++G+F--F-G
END

Gosper Curve

Koch Variant - n=4, axiom=F-F-F-F, Θ=90, F->FF-F--F-F (Test Online)

STT
INC 4
RPL F FF-F--F-F
SET F 0
AXI F-F-F-F
END

Koch Variant

Sierpinski Triangle - n=7, axiom=F-G-G, Θ=120, F->F-G+F+G-F, G->GG (Test Online)

STT
RPL G GG
RPL F F-G+F+G-F
DEG 120
AXI F-G-G
SET F 0
SET G 0
INC 7
END

Sierpinski Triangle

Dragon Curve - n=12, axiom=FX, =90, X->X+YF+, Y->-FX-Y (Test Online)

STT
INC 12
DEG 90
AXI FX
SET F 0
RPL X X+YF+
RPL Y -FX-Y
END

Dragon Curve

Input

Aside from the examples given above, your code should support the following test cases as well:

Input:

SET F 0
AXI FF
RPL F F-F+F
END

Output: Error: No STT at beginning.

Input:

STT
SET F 0
AXI FF
RPL F F-F+F

Output: Error: No END at ending.

Output

Your program should output the resulting image by outputting an image or by drawing to the screen (e.x. turtle graphics). If you would like to check out a Python 3 example, here is a Github link to pylasma.


This is , so least number of bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Why is "turtle graphics" in particular mentioned? Why not any other method of drawing to the screen? \$\endgroup\$ – feersum Jul 14 '15 at 3:40
  • \$\begingroup\$ @feersum My intent was to say that, at the time of writing I didn't know how to word it, I was very tired :P \$\endgroup\$ – Kade Jul 14 '15 at 11:04
  • \$\begingroup\$ Do any of the commands accept floating-point arguments? \$\endgroup\$ – feersum Jul 14 '15 at 14:41
  • \$\begingroup\$ @feersum MOV and DEG are the only two which should support floating-point arguments. I'll update. \$\endgroup\$ – Kade Jul 14 '15 at 14:44
  • \$\begingroup\$ This is pretty close to codegolf.stackexchange.com/q/9341/194 . The bit that's different is parsing the input, so if you want to make an original question then you could restrict it to validating that a file obeys the structure rules (although I must say that I find "$ ... will be one of the variables within #" overly restrictive). \$\endgroup\$ – Peter Taylor Jul 14 '15 at 18:42
  • \$\begingroup\$ @PeterTaylor Just my opinion, but validating a text file is much less exciting than the question I'm posing :P I'd rather just scrap this. \$\endgroup\$ – Kade Jul 14 '15 at 20:50
1
\$\begingroup\$

Print time of day using words

I'm not sure if this has been done before. I thought it must have but I could not find one using search. The idea is basically, given a number in seconds, e.g. the output from time(NULL). Return the current time in words using 12 hour clock, e.g.

HALF PAST FIVE PM
A QUARTER TO SIX PM
TEN TO SIX PM
SIX O'CLOCK PM
SIX TEN PM
TWELVE NOON
TWELVE O ONE AM

Has this challenge been done before?

One thing I cannot decide is when the "PAST" should be used. Should it be used only when there is less than 15 minutes left? Should it be FIVE FIFTY FIVE or FIVE TO SIX?

\$\endgroup\$
  • \$\begingroup\$ It doesn't matter too much which approach you choose as long as you define it clearly so there is no doubt which way is the correct way for your question. I'm guessing using PAST and TO would make it a slightly more challenging/interesting golf. \$\endgroup\$ – trichoplax Aug 4 '15 at 0:43
  • \$\begingroup\$ Yes, I want it to be a 12 hour clock. As humanly as possible. I think I should add AM and PM to the answer. Possibly even NOON. \$\endgroup\$ – some user Aug 4 '15 at 0:49
  • \$\begingroup\$ Yes it's a tricky system. Just keep editing to clarify edge cases until the comments stop coming in :) \$\endgroup\$ – trichoplax Aug 4 '15 at 0:55
  • \$\begingroup\$ This is essentially It's Spanish Time! in a different language. \$\endgroup\$ – Dennis Aug 8 '15 at 4:40
  • \$\begingroup\$ You have three options. 1. use only the digital times, like FIVE FIFTY FIVE (boring in my opinion) 2. use the word based system, TWENTY TO FIVE (the changeover occurs between 30 and 31 past the hour) 3. use word based system for the 15 minute intervals (half past, quarter past/to and o'clock.) Whatever you do, be very clear about what's required acceptable and what is not. For me 12 noon is PM. If you require NOON you should require MIDNIGHT also. Other things like the A in A QUARTER and the O in TWELVE O ONE AM should be spelt out in detail in the specification. \$\endgroup\$ – Level River St Aug 10 '15 at 0:41
1
\$\begingroup\$

Maze to regex

Suppose we have an ASCII maze like so:

#######
#s# # #
# # # #
#     #
# ### #
# #  e#
#######

The input maze will have the following properties:

  • One cell (marked s) will denote the start of the maze, and a separate cell (marked e) will denote the exit.

  • The walls will be denoted by hashes #, and empty corridors will be denoted by spaces.

  • The maze will be a perfect rectangle, have no cycles, and will consist of exactly one connected component (i.e. all cells will be reachable)

A single character from NSEW represents a move North, South, East or West respectively, and consists of moving two characters in the specified direction. For instance, the above example is a 3 by 3 maze where the following cells can be occupied:

#######
#x#x#x#
# # # #
#x x x#
# ### #
#x#x x#
#######

A string consisting of NSEW is said to solve a maze if applying each move in turn results in the exit being reached at some point in time, regardless of whether the string continues on afterward. If a move is blocked by a wall, the move is ignored and no movement occurs.

Example strings which solve the above maze are SEES, SENSES and SSSSSNENNNNNSENNNNNSSSSSSSSWW.

The challenge

Your task is to write a program or function which takes in an ASCII maze and outputs a regex. The regex must match a string of NSEW if and only if it solves the given input maze.

For instance, all solutions to the 2 by 2 maze

#####
#s#e#
# # #
#   #
#####

can be encapsulated by the regex

^(([NEW]|S[WS]*N)*S[WS]*E([ES]|W[WS]*E)*W[WS]*N)*([NEW]|S[WS]*N)*S[WS]*E([ES]|W[WS]*E)*N[NEWS]*$

(Try it online at Regex101)

Available features

You may only use the following regular expression features:

^$         Start and end anchors respectively
N|E        Alternation
NE         Concatenation
()         Grouping
*          Repetition (0+ times)
+          Repetition (1+ times)
?          Optional (0 or 1 times)
[NESW]     Character classes (but not negated classes)

In particular, recursion, wildcards, lookaheads and other unlisted features are not allowed.


Sandbox questions:

  • What would be better, (scoring by providing a few test mazes, and taking the sum of output regex lengths) or (any output regex is okay as long as it is finite and correct)?

  • I've chosen this ASCII representation because it looks the nicest, but I'm not sure if it's the most convenient. I'm open to suggestions for alternatives.

  • What is the best way to test submissions? I can write a bunch of test cases per maze, but it's impossible for me to test an infinite number of strings.

\$\endgroup\$
  • \$\begingroup\$ Is it guaranteed that there will never be a wall in a position that permits a move of only 1 step instead of 2? Or should such cases be simply treated as no move possible? \$\endgroup\$ – trichoplax Aug 10 '15 at 17:02
  • \$\begingroup\$ What range of maze sizes must this work for? \$\endgroup\$ – trichoplax Aug 10 '15 at 17:03
  • \$\begingroup\$ If you don't have an automated way of checking submissions, you could announce one of "innocent until proven guilty" or "guilty until proven innocent". Either answers require a proof, or answers are assumed to be valid until someone proves otherwise. \$\endgroup\$ – trichoplax Aug 10 '15 at 17:06
  • \$\begingroup\$ @trichoplax I'll work on the maze definition later, but the input is guaranteed to be valid. Maze size would have to depend on if this is golf (which would probably have a larger limit) or metagolf \$\endgroup\$ – Sp3000 Aug 11 '15 at 1:46
1
\$\begingroup\$

Be Rational! Finding Rational Roots of Polynomials


In this challenge you are to find all rational zeroes of a polynomial. The results have to be exact. I would suggest using The Rational Root Theorem.

Input


Input can be through function argument, command argument, or user input. Input will be a polynomial. The polynomial may have rational coefficients. If a term has a coefficient of zero, that term will not be included in the input. x^1 will be abbreviated as x.

Examples:

-x^7+4x^4/7-21x^2/2+5x+23/19
...//More to be added when posted

Output


Output will be a list of the rational roots of the input polynomial. Output can be through function return value or stdout. If output in string format, you will use improper fractions separated by commas. The output must be simplified as much as possible. Duplicate roots should not be printed more than once.

Examples:

4/5,2/3,-15/2
...//More to be added when posted.

Example Cases

> x^2-1
1,-1
...//More to be added when posted.

Just like all questions, the answer with the lowest byte count wins.

Questions:

Is this too much like Peter's earlier question?
Are there any points I haven't covered or are not clear?
Any grammar/spelling mistakes?
Any tips on improved formatting?

\$\endgroup\$
  • \$\begingroup\$ Somewhat related question \$\endgroup\$ – Sp3000 Aug 17 '15 at 2:01
  • \$\begingroup\$ The title is one character shy of the minimum title length and "abbreviate" should be "abbreviated." Can the roots be listed in any order? Do they have to be fully reduced or could we, for example, use 2/4 in place of 1/2? I would also suggest rewording "fractional coefficients" to "rational coefficients." \$\endgroup\$ – Alex A. Aug 17 '15 at 2:38
1
\$\begingroup\$

Rec(ursion)less execution

We have a simple (non-Turing complete) language.

Each line of program is a set of terms separated by single space. Some of terms (ending with ()) are function calls. Some lines (whose first term ends with :) are function definitions. The lines that are not function definitions are called expressions.

This is a sample program:

funa: one two three
funb: funa() four oclock rock
here we go funb()

Here we have two function definition lines and one expression line.

And this is BNF for this language just for clarity:

literal ::= [any printable char other than ' ', ':', '(', ')']+
function_header ::= literal ':'
function_call ::= literal '()'
term ::= literal | function_call
expression ::= term | expression_list ' ' term
function_definition ::= function_header expression

program_line ::= function_definition | expression
program ::= [program_line '\n']+

The task is to write a program or function that validates the program P and performs EXECUTE(P) if the program adheres to validation rules.

Validation rules:

  1. EXECUTE(P) eventually stops (it's not Turing complete - enough to check if one of the called functions would eventually cause itself to be called - either being recursive itself or "mutually recursive" with other function it calls),

  2. while calling EXECUTE(P) -> EXECUTE_LINE(P,L), each function definition search succeedes (in other words - the program will not try to call undefined function).

If program does not pass validation rule 1 or 2, ERROR: RECURSIVE FUNCTION or ERROR: UNRECOGNIZED FUNCTION should be printed respectively.

When both rules seem to be violated, assume that search for undefined function causes the algorithm to fail (stop) instantly, so recursion that would occur later if the function was found, is not reported. We only report ERROR: UNRECOGNIZED FUNCTION in this case (see Example 5 below).

In similar way, if recursion prevents a call to function that would not be found otherwise, even though the function containing call to unrecognized function is called only ERROR: RECURSIVE FUNCTION is reported (see Example 4 below).

If validation does not report any of those two errors, EXECUTE(p) should be called.

Executing a program is defined like this:

EXECUTE(P)
  - for each line L in the program P:
     - if L is not a function definition EXECUTE_LINE(P,L)

EXECUTE_LINE(P,L)
  - for each term T in L:
      - if T is a literal
          print T followed by single space
        else
          FH = T without '()' + ':'
          FDL = find in P a line starting with term FH
          FD = all terms of FDL after FH
          EXECUTE_LINE(FD)

Example 1:

a: b()
b: a()
c: cucumber
other: nofun()
d: apple banana and c()
we have d()

Output:

we have apple banana and cucumber

Note, that in spite of existence of mutually recursive function definitions a and b and function definition other calling undefined function nofun error was not raised, because execution never goes to any to this functions.

Example 2:

other: nofun()
c: apple banana and cucumber
we have other()

Output:

ERROR: UNRECOGNIZED FUNCTION

Example 3:

a: b()
b: a()
c: apple banana and cucumber
we have b()

Output:

ERROR: RECURSIVE FUNCTION

Example 4:

a(): a() nofun()
hello a()

Output:

ERROR: RECURSIVE FUNCTION

We don't output ERROR: UNRECOGNIZED FUNCTION, because the program would never try to execute nofun, recurring infinitely into first term of definition of a.

Example 5.

a(): nofun() a()
hello a()

Output:

ERROR: UNRECOGNIZED FUNCTION

We don't output ERROR: RECURSIVE FUNCTION here, because the program would fail to find definition for nofun before even tring to recurse into a.

Accepted solution: a function or a program that takes a program in the above-defined language, validates and runs it. You can assume that program has already been split into single lines, however you can use raw input or accept program as single string when convenient.

This is code-golf, so the shortest submission in term of bytes will win. However, all working submissions in all languages will be appreciated.

\$\endgroup\$
  • \$\begingroup\$ The two rules seem to be inconsistent: the first one prohibits the recursive function f: f() even if f isn't called; and the second prohibits the function which calls an undefined function f: fail(), but only if f is called. It would be less confusing to make them both syntactic (based on the text of P) or both semantic (based on the execution of P). \$\endgroup\$ – Peter Taylor Aug 22 '15 at 7:35
  • \$\begingroup\$ @PeterTaylor I didn't mean to prohibit existence of recursive functions that are not called, this was my description that was not precise enough. I clarified the description and added some more examples. So now, both rules are based on execution of P rather than text of P. \$\endgroup\$ – pawel.boczarski Aug 22 '15 at 8:57
1
\$\begingroup\$

Triple Triad Tournament!


(anything in italic parenthesis is a note for the sandbox)

About Triple Triad

Triple Triad is a card game from the Final Fantasy series. I've never played a FF game that included it, though, so I'm only familiar with the version in the Pokémon fangame Pokémon Insurgence. It may or may not be different than the original version, so apologies in advance if this isn't quite what you're expecting. :)

In Triple Triad, each card has 4 numerical stats that range from 1 to 10*: An "up" value, a "left" value, a "right" value, and a "down" value. Here's an example of a card with an "up" value of 1, a "left" value of 6, a "right" value of 3 and a "down" value of 2:

Triple Triad Rules

At the beginning of each game, players construct a "deck" of five cards, chosen from their entire collection. These cards are kept secret from the other player.

Triple Triad is played on a 3x3 grid. Players take turns choosing a card from their deck and placing it on an empty square of the grid. The goal of the game is to control the majority of the cards when the grid is filled. When the game is complete, one card is randomly selected from the loser's deck and given to the winner.

Control

When a card is placed on the grid, it is controlled by its owner. In order to come out of the game victorious, you must gain control of cards that the opponent played.

To gain control of an opponent's card, you must place a card of your own that "beats" it adjacent (not including diagonals) to the card you want to take control of. Whether or not your card beats the opponent's depends on their stats and which side you place your card on.

Imagine this board as the current game state and the blue card as a card in my deck:

If I want to take control of the opponent's Numel, I have to place my Mareep adjacent to it. This leaves only two options: The top middle square or the middle right square. If I were to place it on the top middle square, my card would be to the left of the opponent's. As a result, Mareep's "right" value of 2 would be contested against Numel's "left" value of 4. 2 is not greater than 4, so my opponent would retain control of Numel. Note that my value must be strictly greater; a tie would be the same as a loss.

If I were to place my card in the middle right corner, it would be below the opponent's card. As a result, Mareep's "up" value of 4 would be contested against Numel's "down" value of 3. 4 is greater than 3, so I would gain control of Numel (which would turn blue to indicate that).

This process is applied in all four directions at once. If there was a card below Mareep with an "up" value of 1 or 2, I would gain control of it as well. However, gaining control is not done passively or recursively. Control can only be contested at the exact moment a card is placed, and gaining control of a card does not count as "placing it".

Tournament Rules

Each bot is given a budget of (TBD) with which to purchase cards before the tournament (this will be done by the author, not the bot itself, and will be hardcoded into the bot). Here are the cards, along with their costs:

There - 1000
 will - 1500
   be - 1500
    a - 2500
 list - 3000
 here - 4000

The bots will play in a Round Robin tournament with Bo3 matches (subject to change. not sure if round robin will work well or if i should be using Bo5 or what). The bot that wins the most matches will be declared the winner.

Match Procedure

  1. Each bot chooses 5 cards from their collection to create a deck. (If they have less than five cards, they forfeit the match.)
  2. The game is played as described above, until the board is filled. (i'm not sure how to decide who should go first. alternate? winner of the last game? loser?)
  3. When the game is complete, a random card from the loser's deck is removed from their collection and inserted into the winner's collection. (At the end of the match, each bot's collection is reset to its original state.) (i'm not totally sure about choosing a random card. it's how the original game works, but it's not necessarily 100% fair. the idea is that over the course of a round robin tournament, any RNG variance will be smoothed out, but i don't know...)
  4. Repeat steps 1 through 3 until one bot has won 2 games.

Input / Output Specifications and Controller Details

(none yet lmao)


* The Insurgence variant has some nonsense regarding Pokémon types at higher difficulty levels, but this challenge will ignore that.

\$\endgroup\$
  • \$\begingroup\$ Your mention of excluding recursive moves makes me wonder what the game would be like including recursion, on a much larger board... (perhaps as a separate KotH) \$\endgroup\$ – trichoplax Sep 1 '15 at 14:34
  • \$\begingroup\$ Choosing a random card for the winner will introduce unfair variation in a single round robin, but I think that's worth it for the increased variety of games that will test strategies more thoroughly. As long as you don't mind running the round robin multiple times until it converges on a fair score, I would keep the random element. \$\endgroup\$ – trichoplax Sep 3 '15 at 7:23
1
\$\begingroup\$

Is a point inside a polygon?

Given the polygon with 2 < N < 11 sides, on 2D plane, find out if a given point is inside the polygon.

The input can be an array of points in x, y, each determining a vertex, or by a string in format X Y x1 y1 x2 y2 ... xN yN (you may choose other separator). The X and Y are the coordinates of the point to be tested. The list then contains N verices, and the last point is connected to the first point. All x and y are integers.

Using any built-in functions performing the test is prohibited (like this one)

You should consider that a point is inside a polygon also when it is one of its vertices or it lies on one of its edges.

Notes

  1. Tags would be and
  2. Should max x and y be determined?
  3. Should they be positive (uint) values only?
  4. Some questions of this type have already been asked on StackOverflow (example 1, example 2). Is it ok to ask this question here? (I didn't find it)
  5. Should the question also allow non-convex polygons? A non-convex (concave) is a polygon which has at least one of its angles larger than 180 deg., and can borders intersect? (I think it can be too complicated and in my opinion it should be for convex polygons only).
\$\endgroup\$
  • \$\begingroup\$ The question should definitely allow non-convex polygons, but if it allows self-intersection then you'll need to pick a winding rule and explain how it works. \$\endgroup\$ – Peter Taylor Sep 8 '15 at 19:58
  • \$\begingroup\$ Be aware that some of the answers here generalize to polygons. \$\endgroup\$ – xnor Sep 12 '15 at 18:57
1
\$\begingroup\$

Literal Fourier Transform (or Fouriest Numbers?) Dupe

(inspired by this Saturday Morning Breakfast Cereal comic)

It's called a fourier tranform when you take a number and convert it to the base system where it will have more fours, thus making it "fourier". If you pick the base with the most fours, the number is said to be "fouriest."

Goal: Given a positive integer n in base 10:

$$ 4 \le n_{10} \le 2^{31} -1 $$

Write a function that displays its equivalent in another base in the format below that maximizes the number of 4s, i.e. the fouriest:

Base x; Fouriest y

Notes:

  1. If multiple bases tie on the number of 4s, any base will be accepted. E.g. if the input has the fouriest value already, it's fine to return/display the input.
  2. Numbers may not necessary yield a 4, see last example below.

Examples:

  • (from comic) 624 -> Base 5; Fouriest 4444
  • 2316780 -> Base 14; Fouriest 444444
  • 4 -> Base 10; Fouriest 4
  • 5 -> Base 10; Fouriest 5

Bonus:

  1. Have your function accept a second argument m for the input base: 1/4 reduction in submission size.

Winning:

Shortest code in bytes wins.

This is .

\$\endgroup\$
  • \$\begingroup\$ If two different bases give the same number of 4s, can either be chosen? \$\endgroup\$ – trichoplax Sep 8 '15 at 7:18
  • \$\begingroup\$ @trichoplax yes, I think that'll be an extension of point 1 under "Notes". :) \$\endgroup\$ – h.j.k. Sep 8 '15 at 7:22
  • \$\begingroup\$ I'm not personally a fan of bonuses (I prefer just one well defined objective), but if you choose to have a bonus it might work better to make it a percentage reduction instead of a number of bytes. Otherwise the bonus has very different effect on different languages. \$\endgroup\$ – trichoplax Sep 8 '15 at 7:38
  • \$\begingroup\$ P.S. With or without a bonus, I think this is a brilliant challenge. \$\endgroup\$ – trichoplax Sep 8 '15 at 7:42
  • \$\begingroup\$ @trichoplax along the lines of everything-to-do-with-four, I was thinking of shaving 1/4 for the bonus component, but then I'm not too sure if that's too much. :p I guess I can still consider that... while awaiting for other suggestions. :D \$\endgroup\$ – h.j.k. Sep 8 '15 at 8:01
  • 1
    \$\begingroup\$ Dupe \$\endgroup\$ – Peter Taylor Sep 8 '15 at 13:32
  • \$\begingroup\$ @PeterTaylor thanks for pointing that out! I wouldn't be posting this then. It didn't mention "fourier", which explains why it slipped through my search for posted questions. \$\endgroup\$ – h.j.k. Sep 8 '15 at 14:23
1
\$\begingroup\$

Find all matchings

Golf this SO question in any language. Fewest bytes wins.


Given two equal-size sets of positive integers,

A={3,1,5}
B={2,4,3}

a matching pairs up elements from each set, like:

{(5, 2), (1, 4), (3, 3)}

There's one matching for each permutation of n elements, where n is the size. Your goal is to print or return all the matchings.

{(3, 2), (1, 4), (5, 3)}
{(3, 2), (1, 3), (5, 4)}
{(1, 2), (3, 4), (5, 3)}
{(1, 2), (5, 4), (3, 3)}
{(5, 2), (3, 3), (1, 4)}
{(3, 4), (1, 3), (5, 2)}

Input: Two nonempty equal-size collections (lists, arrays, sets) of positive integers. Numbers won't repeat within a collection, but may overlap between them. If your collection is ordered, you may assume it to be sorted.

Output: Print or return all possible matchings.

Each matchings must appear exactly once, in any order. They must be somehow grouped or separated, so you can tell where each one beings and ends. These rules also apply to the pairs in each matching.

Banned: Built-ins that generate matchings or permutations.

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

I have an idea for a challenge but I'm not sure if it would be best as a or , I'm also not sure what rules I should apply to make it more interesting.


"Convert an image to LEGO safe-colours"

The task is to convert the existing colours from a JPEG image into LEGO-safe colours.

What are LEGO-Safe colours?

For the purpose of this challenge, LEGO-Safe colours are defined as the seven oldest solid colours produced by LEGO that are still in production. (The exception being grey which has changed in recent years, for the purpose of this challenge, the original grey will be used).

The colours are hexadecimal approximations from this list.

White, #f2f3f2
Grey, #a1a5a2
Black, #000000
Bright Red, #c4281b
Bright Yellow, #f5cd2f
Dark Green, #287f46
Bright Blue, #0d69ab

Images

You may demonstrate your results using images provided by yourself or the ones shown below.

Lego Factory (Colour)

enter image description here

Lego and Duplo Bricks (Greyscale)

enter image description here

\$\endgroup\$
  • 2
    \$\begingroup\$ Dupe \$\endgroup\$ – Peter Taylor Sep 18 '15 at 14:27
  • \$\begingroup\$ @PeterTaylor Bummer \$\endgroup\$ – Ambo100 Sep 19 '15 at 9:26
1
\$\begingroup\$

Another cake question - Share it fairly!

I'm having a party, and there were going to be 8 of us. As I like to cut the slices of cake fairly, I normally get a round cake and make the cuts with the help of a protractor (any code golfer would!) But this time I found the bakery were making octagonal cakes, so I bought one of these to help me with my cutting.

The problem is, now there are only 7 of us! Some people are so inconsiderate, dropping out at the last minute! How am I going to cut the cake fairly now?

Well it turns out that at https://puzzling.stackexchange.com/a/18244/4768 they have the answer. Although my protractor is no good, it's still true that if I start my cuts at evenly spaced points on the perimeter of the cake and end at the centre, all the slices will be of equal size and have an equal area of icing. This is very important. This is quite easy to prove for cakes in the shape of any regular polygon, using the fact that the area of a triangle is base*height/2.

I need you to write me a program or function to show me how to cut my cake.

The code will take 2 inputs: the number of edges on the cake (3 to 15) and the number of pieces to cut it into (3 to 40).

It will output a diagram showing the cake (a regular polygon) and the positions where the cuts are to be made (lines radiating out from the centre to equally spaced points on the perimeter.)

Some examples are shown below. Note for example that for the case 3,9 the slices are all equal size, but the angles at the centre of the cake are not.

You can orient the cake any way you like, but one of the cuts has to pass through a vertex for easy comparison of answers.

enter image description here

Scoring: this is code golf. Shortest code in bytes wins.

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

My first challenge in a long time. Feedback would be appreciated!

Last Minute Shipments

Here's the situation: You're an engineer for Acme Rail Shipping Inc. There's a string of shipments to make for tomorrow but it turns out at the last moment that they're actually expected to arrive today! There isn't enough time to stop at every destination. It doesn't matter if you skip a few stops as long as you get to others as fast as possible. Your task is to figure out which ones to skip.

Challenge

Given a list of stops and a minimum number of stops to make, write a program or function that outputs the list of stops to make that results in the lowest total time taken. Here's the catch: Your train is very long and very heavy, so it takes a long time to accelerate. Sometimes it may be more efficient to skip a stop rather than to slow down to make it.

  • Your train starts with the front at the origin and is at rest.
    • Each stop is a point along your 1D route defined by a positive distance from the origin.
    • To make a stop, you must slow down to rest with the front of the train on the point. The shipment is delivered immediately so right as you reach rest, you start accelerating again.
    • The train accelerates uniformly at 0.3 m/s^2 and brakes uniformly at 1.2 m/s^2 (I'm not sure how realistic these values are. Subject to change. Feedback would be helpful.)
    • Assume that there is no upper speed limit to the train. Therefore, you should be accelerating at every point between stops.
    • Added: You cannot go backwards.
    • Added: Total time will be measured from when you start to when you pass or arrive at the last stop, regardless of whether you decide to make it or not. You can't just leave your train in the middle of the route! This means that, for example, if you skip the last stop, then the total time will include the time taken for the train to accelerate from the second to last stop and reach the last stop at some velocity. If you don't skip the last stop, the measured time will end when you come to rest at the last stop.

Input

Input will be a number for the minimum number of stops to make, followed by a list of distances from the origin for each stop. The first item in the list will be the distance for stop #1, the next will be distance for stop #2, then distance for stop #3, etc. Distances in the list are strictly increasing and are defined in meters.

You can take input in any reasonable format, such as a delimited list on stdin with the first item as the minimum number of stops, as program arguments with the first item as the minimum number, or as parameters to a function.

Output

Output will be a list of stops to make. This list will contain the numbers of each stop, as defined in the previous section. For example, if it is determined that stops 2, 3, and 5 out of five stops need to be made, the output would be 2, 3, 5.

Output can be any reasonable format, such as a delimited list on stdout, or an array return value from a function. Trailing whitespace or newlines are acceptable. The list doesn't necessarily have to be sorted.

Example I/O

Coming soon

Standard rules apply. Shortest code wins, however clever solutions will get my upvotes. Good luck!

\$\endgroup\$
  • \$\begingroup\$ This feels like a minor variant on the several existing single-source shortest path questions. It's borderline enough that I wouldn't use my unilateral close-as-dupe powers, but I wouldn't be surprised to see it closed as a dupe. \$\endgroup\$ – Peter Taylor Sep 21 '15 at 17:52
  • \$\begingroup\$ @PeterTaylor I did search before I posted this but I didn't find anything, maybe I didn't use the right terms. Are there any examples specifically that you are referring to? \$\endgroup\$ – DankMemes Sep 21 '15 at 18:41
  • \$\begingroup\$ codegolf.stackexchange.com/search?q=shortest+path+is%3Aquestion Not all of them are shortest path in a graph, but I think most of them are. \$\endgroup\$ – Peter Taylor Sep 21 '15 at 21:42
  • \$\begingroup\$ @PeterTaylor I intended distance to always be the same, and the optimization to be for shortest time (I've updated the answer to clarify distance). The point here isn't that you must visit all nodes as fast as possible, it's that you must visit n of the nodes and decide which ones to pass. \$\endgroup\$ – DankMemes Sep 21 '15 at 22:07
  • \$\begingroup\$ Yes, I understood that. So the graph has vertices which are pairs (stop, num visited), for each k > j >= i there is an edge (stop_j, i) --> (stop_k, i+1) with weight corresponding to the time to get from stop j to stop k, and you start at (0, 0) and want the shortest path to (any, n). \$\endgroup\$ – Peter Taylor Sep 22 '15 at 6:28
1
\$\begingroup\$

Strata

Strata is a puzzle game in which you lay coloured ribbons across a grid. When two ribbons intersect, the cell under the intersection takes on the colour of the uppermost ribbon. Here's an example puzzle, ready to solve:

After laying the first ribbon, no cells have been assigned a colour yet:

Empty example puzzle

Laying a perpendicular ribbon colours a cell in:

Example puzzle with one ribbon

Notice that, if the uppermost ribbon isn't the correct colour, the cell isn't filled in to let you know you've got it wrong. Also, if a cell doesn't have a target colour, it doesn't matter what colour ends up on top of it; the cell remains colourless when the second ribbon is laid across it:

Example puzzle with four ribbons

And a completed solution:

Completed example puzzle

The Challenge

The object of this challenge is to write a program or function that will provide a step-by-step solution for a Strata puzzle. Here is the layout for the example puzzle provided above, rotated 45 degrees clockwise and with letters a-c substituted for the cell colours:

 ba
ab 
a c

For ease of the following discussion, I've labelled the columns 1-3 and the rows A-C.

  ABC
 +---
1| ba
2|ab 
3|a c

The notation for the output commands will be a single character representing the row or column to lay a ribbon upon, and then another character representing the ribbon type. For example, the command Cb represents laying a ribbon of type b on the rightmost column of this layout.

One of a number of valid solutions for this puzzle is 3a, Cc, 1a, 2a, Bb, Aa. Another is Ca, 3c, 2a, 1a, Aa, Bb.

Input

Input will consist of the layout for a Strata puzzle. The puzzle will always form a square, with side length of 2-9 inclusive. Each character in the input will be one of the following:

  • a lower case letter, representing the ribbon type which should be laid on top of the intersection in the completed puzzle
  • a space, representing a cell where the type of the uppermost ribbon does not matter

Note that a puzzle can use between 2-26 (inclusive) ribbon types, and that the types will not necessarily a the first nth letters of the alphabet. Your program/function won't be provided these separately, and should be acquired from the puzzle layout if required.

Input may be provided in any reasonable form that is convenient for your chosen language. For example, you may accept input as single newline-delimited string, as an array or list of strings, etc. Please provide a description of how your submission will expect its input for testing purposes.

Similarly, input can be provided in any appropriate manner. For example, as command line arguments, function arguments, as a stream via STDIN, etc. You should only specify this if it is not immediately obvious.

Output

Output should consist of a valid solution for the given puzzle. It should consist of an ordered series of instructions, each consisting of two characters:

  • The first character should be a number or upper case letter; a number represents a row, starting with 1 for the uppermost row, a letter represents a column, starting with A for the leftmost column (e.g., in the puzzle above, the instruction 4a would be invalid as there are only 3 rows)
  • The second character should be the type of the ribbon to lay on the grid; this should be a lower case character, corresponding to one of the types provided on the input (e.g., in the example puzzle above, the instruction Az would be invalid as z is not one of the types used in the grid)

Your program/function can provide the output pairs in any reasonable form, and on any reasonable medium. For example, as a series of comma, space, or newline separated values on STDOUT, as an array for return from a function, written to a file with specified name, etc.

Other Rules

  • A puzzle is only considered complete when all rows and columns have had a single ribbon laid across them, and no row or column can have more than one ribbon laid on it. This means that your output will consist of 2 * (side length) instructions.
  • This is code golf, so the winner is the shortest solution in bytes. In the event of a tie, the earliest submission wins.

Test Cases

Input:

 ba
ab 
a c

Possible output:
3a, Cc, 1a, 2a, Bb, Aa

Sandbox comments:

This is my first PPCG question, so I tried to make sure every angle was covered. I think I may have gone overboard though, do you think I should get rid of any sections?

As this isn't a puzzle of my own invention, would there be any problems with posting in-game screenshots?

This puzzle is actually pretty easy to work out if you employ a backtracking technique - find a row or column consisting of a single colour, ignoring spaces and cells which have been crossed once. Add this instruction pair to the end of the prototype solution, then mark all the cells as having been crossed once (or twice). Repeat this 2 * (side length) times and you'll have a solution, if there is one to be found.

I want to discourage brute force solutions, so I'm going to come up with a 9x9 test case with more than 10 different types. My stats skills aren't up to much, but I think that, for a puzzle with side length n and number of ribbon types t, the total number of possible ways to lay ribbons on the grid is:

(2n)! * (2n)^t

Could anyone double check that for me? Also, if I were to put in a 9x9, 10-type test case, would that be big enough to rule out a brute force solution? Should I impose some form of computation time limit, and if so, how long on what sort of machine?

\$\endgroup\$
  • \$\begingroup\$ @trichoplax There is indeed a solution which is significantly faster than brute force, which is as described in my comments. For a puzzle of side length n, it requires exactly 2n iterations to find a solution if one exists, and requires a maximum of [the (2n)th triangle number] row/column inspections in the worst case scenario. I can add a discussion of this to the main body of the challenge, but I'm worried that it's already too long! \$\endgroup\$ – Sok Sep 22 '15 at 11:32
  • \$\begingroup\$ I misread that part and thought that was the brute force solution - but I can see now that it is much faster - I'll delete my irrelevent comment... \$\endgroup\$ – trichoplax Sep 22 '15 at 11:37
  • \$\begingroup\$ I confirm your count for a really brute force solution. It's possible to optimise slightly by observing that if there's a sequence of parallel ribbons then the order in which they're placed is irrelevant. \$\endgroup\$ – Peter Taylor Sep 23 '15 at 20:26
1
\$\begingroup\$

Just repeat yourself

Write a program that outputs "Do not repeat yourself!"

Your program code must respect the following constraints :

  • its length must be an even number
  • each character that is in position 2n (where n is an integer > 0) must be equal to the character in position 2n-1. The second character of the program is equal to the first, the fourth is equal to the third, etc.

Examples:

HHeellllooWWoorrlldd is a valid program

123 or AAABBB or HHeello are incorrect

This is code-golf, so the shortest code wins!

\$\endgroup\$
  • 2
    \$\begingroup\$ This rules out most languages which require a keyword to output. For example, print, put or output would be excluded. Maybe there is some way of specifying the constraints to allow many languages to compete, while still being highly restrictive? I can't think of a way, but I wonder if it would help to say "meet 2 of 3 constraints" rather than "meet 2 constraints". Hopefully someone else can come up with a better way that I can't think of... \$\endgroup\$ – trichoplax Sep 22 '15 at 11:52
  • 1
    \$\begingroup\$ @trichoplax maybe "each character in the source code must have one and only one neighbour at the left, the right, the bottom or the top with the same character value". \$\endgroup\$ – Arnaud Sep 22 '15 at 13:29
  • \$\begingroup\$ @SuperChafouin Based on that, would comments be allowed? \$\endgroup\$ – ASCIIThenANSI Sep 22 '15 at 18:45
  • \$\begingroup\$ @ASCII yes comments should not be allowed, that would be too easy (just double each line and add "\\") \$\endgroup\$ – Arnaud Sep 23 '15 at 2:14
  • \$\begingroup\$ I think I'll stay on my current rules - they sure rule out some languages, but a lot can still compete. These questions also exclude a lot of languages, yet they are popular and interesting imho : codegolf.stackexchange.com/questions/52809/… codegolf.stackexchange.com/questions/39993/… \$\endgroup\$ – Arnaud Sep 23 '15 at 2:19
1
\$\begingroup\$

The shortest code for testing reliable password ( for Vault Password Rank 3 puzzle )

Introduction

I started playing Empire of Code recently, and there was some challenge. The player is supposed to write a code on a python or on javascript to detect if passed string is reliable password, that is, contains at least one lowercase Latin letter, one uppercase Latin letter and one digit and has at least 10 characters.

It was quite easy for me to fit in 130 characters limit for rank 3 using javascript, however, I spent a lot of time trying to fit in 100 characters limit for rank 3 using Python. Some guy said that he has managed to fit in 71 characters for Python. I was trying hard but still couldn't reduce the code less than 90 characters. Is it possible to use even less than 71 character?

Challenge Vault Password [ the following description is mostly copied from https://empireofcode.com/ ]

We've installed a new vault to contain our valuable resources and treasures, but before we can put anything into it, we need a suitable password for our new vault. One that should be as safe as possible.

The password will be considered strong enough if its length is greater than or equal to 10 characters, it contains at least one digit, as well as at least one uppercase letter and one lowercase letter. The password may only contain ASCII latin letters or digits, no punctuation symbols.

You are given a password. We need your code to verify if it meets the conditions for a secure password.

In this mission the main goal to make your code as short as possible. The shorter your code, the more points you earn. Your score for this mission is dynamic and directly related to the length of your code.

Input: A password as a string.

Output: A determination if the password safe or not as a boolean, or any data type that can be converted and processed as a boolean. When the results process, you will see the converted results.

Example:

golf('A1213pokl') === false

golf('bAse730onE') === true

golf('asasasasasasasaas') === false

golf('QWERTYqwerty') === false

golf('123456123456') === false

golf('QwErTy911poqqqq') === true

Precondition:

0 < "password| ≤ 64

password matches by regexp expression "[a-zA-Z0-9]+"

Scoring:

Scoring in this mission is based on the number of characters used in your code (comment lines are not counted).

Rank1:

Any code length.

Rank2:

Your code should be shorter than 230 characters for Javascript code or shorter than 200 characters for Python code.

Rank3:

Your code should be shorter than 130 characters for Javascript code or shorter than 100 characters for Python code.

How it is used:

If you are worried about the security of your app or service, you can use this handy code to personally check your users' passwords for complexity. You can further use these skills to require that your users passwords meet or include even more conditions, punctuation or unicode.

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

Compute factorials

In the style of the Hello, World! catalog, this question is a collection of the shortest programs that compute a factorial (a common task for new programmers) in any given language.

Specifications

Your program must take a positive integer as input from STDIN, and output the corresponding factorial to STDOUT (or your language's closest alternatives).
Your program must also accept the special case of 0! = 1 if 0 is entered. No negative numbers will be entered.

Your program must handle numbers up to 40 factorial (8.159152832×10⁴⁷). Sandbox question: Is 40 factorial too large a minimum requirement? I was also considering 50 factorial is 40 is too small.

Test Cases

3
6

6
720

0
1

11
39916800

Additional Rules

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

  • Submissions are scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8. For example, Piet is scored in codels rather than bytes. If you're not sure how your language is scored, you can ask on Meta.

  • Nothing can be printed to STDERR.

  • 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 computes factorials, then congrats, you've just created a boring answer.

  • Your language must have a valid way to test your program (through an interpreter, compiler, etc.) If there aren't any, you can write one yourself.

  • Standard loopholes are disallowed except where specified by these rules.

leaderboard snippet will be added once this challenge is posted

\$\endgroup\$
  • 2
    \$\begingroup\$ For languages with several integer types/ranges, how high do we need to support? There's a big difference between doing this with int and BigInteger in Java, for instance. \$\endgroup\$ – Geobits Sep 24 '15 at 14:15
  • 2
    \$\begingroup\$ It's up to you, but I think it'd be more interesting to include 0! = 1 as valid input as well (i.e. input nonnegative integer rather than positive). Also, if FizzBuzz is happening soon, it might be good to wait a while before doing another catalogue. \$\endgroup\$ – Sp3000 Sep 24 '15 at 14:16
  • \$\begingroup\$ @Sp3000 Thanks for that reminder, I overlooked the special 0! = 1 rule when writing this challenge. As for FizzBuzz, if it gets posted soon I'll make sure to leave this unposted for a little while. \$\endgroup\$ – ASCIIThenANSI Sep 24 '15 at 14:25
  • \$\begingroup\$ @Geobits Thanks for pointing that out, didn't think there would be a problem. Programs must support numbers between 0 and 2^31 -1 inclusive. \$\endgroup\$ – ASCIIThenANSI Sep 24 '15 at 14:28
  • \$\begingroup\$ Hmm. I meant more a limit on the output rather than input, since it grows so quickly. Trying to find the factorial of 2^31-1 would probably break most languages :) \$\endgroup\$ – Geobits Sep 24 '15 at 14:58
  • \$\begingroup\$ @Geobits Yup, I tried 50 factorial and it was really big. I've changed it so programs must support numbers up to 100 factorial, but I'm not sure if this is too big. \$\endgroup\$ – ASCIIThenANSI Sep 24 '15 at 15:17
  • \$\begingroup\$ @ASCIIThenANSI I'd argue that, because the amount of observable atoms in Universe is about 10^80 atoms, 50! is almost to big. It might be annoying to check results with slower languages. \$\endgroup\$ – MatthewRock Sep 25 '15 at 22:10
  • \$\begingroup\$ Also, I'd leave out the requirement for valid interpreter - because, depending on language, there might be no such thing - I'd take C++ as an example - I'm almost sure that there can't be valid C++ interpreter, because it wouldn't be compatible with standard (I may be wrong though). \$\endgroup\$ – MatthewRock Sep 25 '15 at 22:11
  • \$\begingroup\$ @MatthewRock Thanks for your suggestions. I've changed the limit to 40 factorial, and changed the interpreter rule to "some valid way to run". \$\endgroup\$ – ASCIIThenANSI Sep 26 '15 at 15:37
  • \$\begingroup\$ I also think that allowing the competition to have a winner could be more appealing, but that's a side note. \$\endgroup\$ – MatthewRock Sep 26 '15 at 15:39
  • \$\begingroup\$ @Geobits WA (1, 2) suggests that you would need about 7.93 gigabytes just to store the number as binary. \$\endgroup\$ – LegionMammal978 Sep 26 '15 at 16:24
  • \$\begingroup\$ There's an old challenge to find factorials with 100 answers. What does this add to that? \$\endgroup\$ – xnor Oct 16 '15 at 9:18
1
\$\begingroup\$

Golf a game of Nim

Similar to my previous Write the shortest game of Alak challenge, this time you have to golf another simple game - Nim.

You may already know how to play, but if you don't, here are the rules:

  • In Nim, two players take turns removing objects from heaps (piles).
  • Each turn, one player removes at least one object from any heap.
  • You can take as many objects as you want, provided they all come from the same heap.
  • You can take from any heap you want, but you can't take objects from two different heaps in the same move.
  • The player to take the last piece(s) wins.

There are 3 heaps, each starting out with a random number of objects between 2 and 20.

Input

Input is in the form of two numbers - a heap number and the number of objects to take from that heap.
For example, the input 1 2 means "take 2 objects from heap #1".

Output

Every turn, the program must print to STDOUT (or your language's closest alternative) the amount of objects in each heap. (This includes at the start of the game.)
For example, if there were 5 objects in heap #1, 2 objects in heap #2, and 0 objects in heap #3, you would output this:
5 2 0
When one player wins by taking the last piece(s), you have to output P# wins and end the game, where # is the number of the player who won (1 or 2.)

Assumptions

  • Input will always be in the form of Heap# Amount. Any invalid input can be handled however you like.
  • The input will never ask to take from a heap that doesn't exist, or take more objects than a heap contains.

Questions for Meta

  • Are there any loopholes?
  • Should the sizes of each heap be set, rather than random?
  • Should there be a random number of heaps?
  • Should programs have to handle taking objects from non-existent heaps, or more objects that a heap has?
  • I'm 99% certain I've covered everything, but have I left out any rules of Nim?
\$\endgroup\$
  • \$\begingroup\$ Maybe I'm too tired, but I don't see any specification for how the initial sizes of the heaps are set. With respect to your questions, personally I think the rules of Nim are trivial; and that it's if not standard then at least typical for interactive code-golf to not require handling bad inputs. \$\endgroup\$ – Peter Taylor Aug 29 '15 at 19:29
  • \$\begingroup\$ @PeterTaylor Thanks, I've added that to the challenge. \$\endgroup\$ – ASCIIThenANSI Aug 29 '15 at 22:56
1
\$\begingroup\$

Cookie Clicker

Cookie Clicker: Simple, stupid, and yet strangely addictive. In it you must click a cookie (hence the title). Once you have enough cookies, you can spend them on items that will produce cookies for you. Eventually you will be getting hundreds, then thousands, then millions of cookies per second.

There are a few different items that you can buy for cookies: A clicker (that clicks the cookies for you), a grandma (that bakes the cookies for you), a farm (that grows cookies for you), a factory (that mass produces cookies for you), a mine (that will mine and process veins of dough for you), a shipment (that ships cookies from other planets to you), an alchemy lab (that transforms gold into cookies), and others that we won't worry about.

Let's golf a simplified Cookie Clicker.

Challenge

Write a full program. Your program should always display the number of cookies as a whole integer. Every second, your program should add the current cookies per second (defaulted to 0) to the cookie count.

  • When the spacebar is pressed, it adds the base click amount (defaulted to 1) to your cookie count.

  • When the key "1" is pressed, if there are 10 or more cookies in the cookie count, subtracts the cookie count by 10 and adds 0.1 to the current cookies per second.

  • When the key "2" is pressed, if there are 100 or more cookies in the cookie count, subtracts the cookie count by 100 and adds 0.5 to the current cookies per second.

  • When the key "3" is pressed, if there are 500 or more cookies in the cookie count, subtracts the cookie count by 500 and adds 4 to the current cookies per second.

  • When the key "4" is pressed, if there are 3,000 or more cookies in the cookie count, subtracts the cookie count by 3,000 and adds 10 to the current cookies per second.

  • When the key "5" is pressed, if there are 10,000 or more cookies in the cookie count, subtracts the cookie count by 10,000 and adds 40 to the current cookies per second.

  • When the key "6" is pressed, if there are 40,000 or more cookies in the cookie count, subtracts the cookie count by 40,000 and adds 100 to the current cookies per second.

  • When the key "7" is pressed, if there are 200,000 or more cookies in the cookie count, subtracts the cookie count by 200,000 and adds 400 to the current cookies per second.

  • When the key "0" is pressed, if there are 50 or more cookies in the cookie count, subtracts the cookie count by 50 and adds 1 to the base click amount.

There is no input, only output, being changed every second to update the cookie count. No other key should do anything, so you cannot press enter after every key and have it do something.

Other information

  • This is code golf so shortest program in bytes wins.

Thoughts for sandbox

  • There are many, many more features I could add to this challenge if it is too simple. I feel that challenge entries for this will already be long enough.

  • I do not see many challenges that ask for constant input. Does this mean that this challenge is a bad idea?

  • Have I crossed a line?

\$\endgroup\$
  • 1
    \$\begingroup\$ Requiring real-time user input is definitely rare. One big reason is that it's fairly hard to do and (probably) often requires a library. Many if not most esolangs won't be able to do it at all. \$\endgroup\$ – El'endia Starman Oct 3 '15 at 3:08
  • 1
    \$\begingroup\$ A lot of people will ask if they can require the player to press enter after typing each number, so you should be explicit that this is not allowed. \$\endgroup\$ – feersum Oct 3 '15 at 3:30
  • \$\begingroup\$ It's a real shame that non-blocking terminal reading isn't easier to work around, although it has been done a few times: 1, 2, 3 it probably would be a bit of a barrier. I do like the sound of this though! \$\endgroup\$ – Dom Hastings Oct 8 '15 at 9:35
  • \$\begingroup\$ The list should show what is being bought here (instead you can skim down the introductory paragraph). \$\endgroup\$ – Paŭlo Ebermann Oct 11 '15 at 8:19
1
\$\begingroup\$

This is a raw draft about an idea for a popularity contest. Any input would be appreciated.

My watch, it has two buttons

I have this watch with two buttons and a display that can show six characters split into groups of two by colons like this

12:34:56

Each character is displayed by a 5x7 LCD-Matrix, so arbitrary ASCII-characters can be displayed.

I'd like to call the buttons "select" and "modify".

The problem is that the watch is dead. It needs a new operating system.

Since I'm not very trained at designing operating systems I want you to write an emulator for my watch. The emulator should be programmable using the following commands.

  • big letters A-Z represent short presses of "select" the corresponding number of times.
  • small letters a-z have the same meaning for the modify button.
  • < represents keeping "select" pressed for half a second (or something like that).
  • > represents the same for the modify button.
  • numbers in the code mean to wait for that number of hundredth of seconds.

You're free to program any kind of functionality into my watch, but it should at least be usable as a watch showing the time and as a stopwatch showing minutes, seconds and hundredth of seconds.

One thing I know about my watch is that it can be programmed to receive data from my stdin and send data to my stdout. So once the operating system is installed I could send data and a program to the watch and print the results of the execution to my console.

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

Spot the differences

Little Timmy is waking you up on this Saturday morning once again to help him solve his puzzles. You love the little bugger, but those Spot the Differences games are starting to undermine your patience. Like always, you plan to delegate this tedious task to Robotic Dad™ so you can better spend your time... planning for your child education? Yeah, I think that was the plan.
Anyway, you tell Timmy not to worry, that you're going to help him soon enough, grab a beer and sit in front of your computer to help your child solve those puzzles, once and for all.

Your task is to write code that will take two similar pictures which differ in a few spots and somehow output the differences between them. The format of the output is free, however a 5 year-old child should be able to get it.

Here are examples of input :

a glorious abstract realisation of mine, 1 a glorious abstract realisation of mine, 2

wikipedia's example, 1 wikipedia's example, 2

Since there is no formally defined output, this is a .
Please also keep in mind that you'd like to spend a little time sipping your beer calmly in front of your computer. In this regard, built-in solution should be regarded less highly.


Meta : I plan to post a community answer as an example output, linking to the http://franklinta.com/2014/11/30/image-diffing-using-css/ article which made me think of this challenge and using a snippet to illustrate it. Is it enough?

\$\endgroup\$
  • \$\begingroup\$ I don't understand the last sentence. If I want to sip beer calmly, surely a built-in solution is the best? \$\endgroup\$ – Peter Taylor Oct 11 '15 at 20:33
  • 1
    \$\begingroup\$ It immediately occurs to me that the easiest way of doing this is to XOR the two images together. BTW What is the input format? \$\endgroup\$ – Level River St Oct 11 '15 at 23:35
  • 1
    \$\begingroup\$ The technical side seems like it'd simply be subtracting or xor'ing the two arrays, then the popularity side is very open-ended (just draw freehand circles around them?) \$\endgroup\$ – Nick T Oct 12 '15 at 0:18
  • \$\begingroup\$ @PeterTaylor the father described in this question seems to enjoy his time in front of his computer more than with his child. He still wants to improve his child's future but will use any excuse to do it in front of his computer. Disclaimer : I do not encourage bad parenting ;) \$\endgroup\$ – Aaron Oct 12 '15 at 8:47
  • \$\begingroup\$ @NickT & steveverrill I do not know the first thing about image processing so my challenge may indeed be too way too easy. Do you know how I could avoid simple XOR answers? \$\endgroup\$ – Aaron Oct 12 '15 at 8:51
1
\$\begingroup\$

Sudoku with handicap

Note: I've completely reworked this, as the comments convinced me that there's not a good way to describe the restrictions I originally was after in a language-independent way without unreasonably restricting languages. Thanks to all the commenters.

I now reworked the question in a way that also inhibits traditional recursive solving (at least doing so in a straightforward way), and at the same time even allows to add a metrics about the "efficiency" of the algorithm. The basic idea being that your program is called not once, but many times, each time only having limited information about the field.

Also note that this new version requires me to write a driver program; so the question cannot go live until the driver program is written.

Questions are set in italics inside the text

The goal of this challenge is to solve a given Sudoku. However there's a twist: The program cannot access the full board at any time. Instead it is called repeatedly, and each time it has only limited information about the board. I'll refer to the totality of all calls as the "calling loop". The program can then request different information for the next run, or declare that it is finished (that is, request to not be called again; the call loop is terminated).

The only way to pass information between different runs is through the Sudoku board, and a small amount of scratch space. The Sudoku board is initialized before the first call with the Sudoku to solve (obviously) and is then checked after the call loop terminated. During the call loop, the Sudoku board is not checked, so you may "abuse" it to store additional information, as long as at the end, a valid result is generated.

Since it may not be possible to completely solve all Sudokus using such an algorithm, the only hard requirement is that the call loop is guaranteed to eventually terminate, the Sudoku field after termination is in a valid state. The rest is covered by scoring.

Standard loopholes are explicitly disallowed.

The stored data

The data that is stored outside the program consists of 90 nine-it unsigned numerical values (that is, minimal nmumber 0, maximal number 511), 81 of which represent the Sudoku field, and 9 values are scratch space. The values of the field are interpreted as bit fields, as described below.

In the following I'll use as example the Sudoku field

4.5|.7.|89.
..2|.5.|6..
..7|9..|542
---+---+---
..3|5.6|489
...|3.8|...
684|7.9|1..
---+---+---
238|..5|9..
..6|.9.|3..
.79|.3.|2.1

where dots contain fields that have not been filled.

Initially, the data gets filled as follows:

  • Each field pre-filled with number $n$ is represented by the value $2^{n-1}$, that is, the bit corresponding to that number is set, and all other bits are unset.

  • The unfilled fields are represented by the value $511$ (that is, all nine bits are set).

  • The scratch space is filled with $0$.

After the run loop terminates, each pre-filled field needs to have the same value as initially, and each initially empty field must have at least the bit corresponding to the correct solution set. That is, every zero bit represents a value that your program excluded for that field, and a program that excludes the correct solution is disqualified.

The contents of the field is only evaluated at the end of the call loop. So in between your program is free to make creative use of the storage space given.

The input

The program receives its data through standard input of the following form:

The first line contains a description of which data is given to/set by the program in this run. It consists of one to three space-separated words from the following list. On the first run, it is just "S". At later runs, it is exactly what the program requested at its previous run.

The possible values and corresponding interpretation are:

  • R1 to R9: The indicated row of the Sudoku, 1 being the uppermost row.
  • C1 to C9: The indicated column of the Sudoku, 1 being the leftmost column.
  • F1 to F9: The indicated $3\times 3$ subfield of the Sudoku, numbered left to right, up to down. So for example 1 denotes the upper left subfield, 6 denotes the middle right subfield.
  • S: The scratch space.

The next one to three lines contain the corresponding data, from left to right, and from up to down, as space separated decimal numbers.

So at the first run, your program will receive the input

S
0 0 0 0 0 0 0 0 0

At the second run with the example Sudoku field, the input to your program might be:

R2 C3 F4
511 511 2 511 16 511 32 511 511
16 2 64 4 511 8 128 32 256
511 511 4 511 511 511 32 128 8

Output

The first one to three lines are the new values to replace the ones given in the input. The number of the lines must be the same as the number of fields in the first input line, and each line must contain nine values separated by whitespace (leading/trailing whitespace gets ignored).

If some field appears in more than one data line, the corresponding values are bitwise anded together. For example, if the initial line of your program's input was

R1 C1

and the first two line of your output read (with question marks replacing values that are irrelevant for this example — of course your code may not actually output question marks here)

3 ? ? ? ? ? ? ? ?
5 ? ? ? ? ? ? ? ?

then the upper left value us the Sudoku storage field will be 3 & 5, that is, 1

Following those data lines, there will be a single line containing either the single word STOP, in which case the run loop is terminated and the resulting field is created, or a line containing one to three whitespace separated words requesting data to be served in the next run, that is, the words to be presented in the first line of the next run of the program.

Scoring:

The score for qualifying entries is calculated as follows (lower score is better):

  • You get 1 score point for each run of your program.
  • You get 5 score points for each set bit in the final representation of your Sudoku field
  • At the end, subtract 45 (because a perfectly solved Sudoku will have nine bits set; if your program leaves less bits set, it will be disqualified anyway).

The total score is then calculated as weighted mean of the test cases, where the difficulty is used as weight, rounded up to the next integer. That is, if $d_k$ is the difficulty assigned to test case $k$, and $S_k$ is the score you achieved at test case $k$, your total score is $$S = \left\lceil \frac{\sum_k d_k S_k}{\sum_k d_k}\right\rceil$$

Sandbox question: Should I change the relative weight of program runs versus unsolved fields? And is the difficulty weighting a good idea, or should I simply add up all scores?

Test cases:

(Hardness as reported by GNOME Sudoku)

Test case 1: Easy (0.17)

4.5|.7.|89.
..2|.5.|6..
..7|9..|542
---+---+---
..3|5.6|489
...|3.8|...
684|7.9|1..
---+---+---
238|..5|9..
..6|.9.|3..
.79|.3.|2.1

Solution:

415|672|893
892|453|617
367|981|542
---+---+---
723|516|489
951|348|726
684|729|135
---+---+---
238|165|974
146|297|358
579|834|261

Test case 2: Hard (0.63)

.6.|52.|..8
7..|...|9.2
.82|71.|56.
---+---+---
.59|...|..6
.76|...|14.
8..|...|72.
---+---+---
.18|.36|25.
6.3|...|..1
5..|.41|.9.

Solution:

961|524|378
745|683|912
382|719|564
---+---+---
159|472|836
276|398|145
834|165|729
---+---+---
418|936|257
693|257|481
527|841|693

Test case 3: Very hard (0.96)

.35|.94|...
..8|.53|..9
4..|8..|...
---+---+---
..1|9..|.85
..9|1.5|3..
54.|..8|9..
---+---+---
...|..7|..1
6..|58.|7..
...|41.|82.

Solution

135|294|678
268|753|149
497|861|532
---+---+---
371|946|285
829|175|364
546|328|917
---+---+---
982|637|451
614|582|793
753|419|826

Sandbox question: Should I add more test cases?

\$\endgroup\$
  • \$\begingroup\$ Pretty sure you meant code golf not gode golf. \$\endgroup\$ – Blue Sep 2 '15 at 10:49
  • \$\begingroup\$ Is using constraint programming libraries/capabilities of a language allowed, since I'm only calling them and not writing them? \$\endgroup\$ – Fatalize Sep 2 '15 at 14:06
  • \$\begingroup\$ Also do you intend to add a time limit constraint to the challenge? I could write an answer that tries every possible grid until one is valid, without recursion or stacks \$\endgroup\$ – Fatalize Sep 2 '15 at 14:09
  • \$\begingroup\$ @muddyfish: Definitely. Thanks, fixed. \$\endgroup\$ – celtschk Sep 2 '15 at 20:12
  • \$\begingroup\$ @Fatalize: I don't know constrained programming libraries; it might be something I also want to ban. Maybe ban every built-in library that could not be written without recursion? Also, good point on the brute force method. I don't really like time limits, because they are too vague (different computers have different speed), maybe limitations on loops would be an alternative. Or limitations on how often the same variable/memory location may be changed. \$\endgroup\$ – celtschk Sep 2 '15 at 20:25
  • \$\begingroup\$ Limitations on how often a variable can change would be useless in python because you can setattr globals. \$\endgroup\$ – Blue Sep 2 '15 at 22:05
  • \$\begingroup\$ @muddyfish: setattr also changes a variable (by adding attributes to it), doesn't it? \$\endgroup\$ – celtschk Sep 3 '15 at 7:38
  • \$\begingroup\$ Yes but if you're saying you can't do that, you're saying you can only have a certain number of variables. \$\endgroup\$ – Blue Sep 3 '15 at 7:59
  • \$\begingroup\$ I really don't know what's banned as a recursive technique. For instance, what is a stack data structures? Can I use a list and extract the last element? What if I used dynamic programming instead of recursion? \$\endgroup\$ – xnor Sep 4 '15 at 7:46
  • 1
    \$\begingroup\$ Are stack-based languages (CJam, GolfScript, PostScript, FORTH, etc) banned? If so, are languages which use a stack for function/method calls (C, Java, etc.) also banned? Would a better approach be to forget talking about stacks and instead allow only a certain number of memory locations to be used, and limit each of them to 8-bit values? Then C-like language programmers can use a single global array for all their memory, or split it between a few global arrays and some loop variables; stack-based language programmers can work with a limited maximum stack depth; etc. \$\endgroup\$ – Peter Taylor Sep 4 '15 at 14:07
  • \$\begingroup\$ Basically what I want to prevent is algorithms trying to insert some numbers, and when it fails, track back and try something different. \$\endgroup\$ – celtschk Sep 5 '15 at 5:43
1
\$\begingroup\$

The Drunken Knight

Inputs

  • a: Starting location of the knight, e.g. A2
  • b: Target location of the knight, e.g. B4. The starting and target locations may be the same.
  • n: An integer equal to or greater than 0.

Output

The probability that a knight starting at a, moving at random for n turns on an 8x8 board, ends at b.

Notes

  • The knight has equal probability to move to any of the squares which it can access.
  • There are no other pieces on the board that could block any squares from the knight.
\$\endgroup\$
  • \$\begingroup\$ Any time constraints? \$\endgroup\$ – Sp3000 Oct 7 '15 at 14:21
  • \$\begingroup\$ @Sp3000 I haven't really thought about that yet. Do you think it would be more interesting if I tried to disallow brute force solutions via a time constraint? \$\endgroup\$ – absinthe Oct 7 '15 at 14:24
  • \$\begingroup\$ From a simple test (assuming my implementation is right), caching seems to be all you need if you want to bypass a time constraint (brute force ~10 moves in a lot of secs, caching > 100 in less than a sec). So I guess it might be better off without a time constraint after all... \$\endgroup\$ – Sp3000 Oct 7 '15 at 14:51
  • \$\begingroup\$ 1. Is the knight moving on an 8x8 board? 2. Please tag markov-chain \$\endgroup\$ – Peter Taylor Oct 11 '15 at 20:50
  • 1
    \$\begingroup\$ Ah, another thought which occurs: valid output formats? The obvious three are floating point to a certain precision and accuracy; exact rational; and exact rational reduced to simplest form. \$\endgroup\$ – Peter Taylor Oct 13 '15 at 13:31
1
\$\begingroup\$

Time Series Analysis

Time series analysis comprises methods for analyzing time series data in order to extract meaningful statistics and other characteristics of the data (from here).

The challenge

Write a program or function that take a time series vector ts and output a the coefficient of determination of a simple linear regression model estimated by the ordinary least squares.

The coefficient of determination should be the squared correlation between the predicted values of the model and the real values of the input, in such way that any perfectly linear time series should have 1 as it's coefficient.

Considerations

  • ts is a vector of racional numbers of length .
  • To make the model assume ts is time sucessive and use time as its regressor.
  • You can assume that ts is already loaded.
  • You can't use build-in modeling functions such as lm() or similars.
  • The input should be in any reasonable format.

Examples

# input
1,2,3,4,5,6  
# output                      
0

enter image description here

#input 
0.244,0.569,1.575,1.965,2.604,3.493,4.084,4.436,5.209,6.110,6.979,7.245,8.229,9.161,10.309
# output    
0.971                              

enter image description here

Let the shortest code win!

\$\endgroup\$
  • 1
    \$\begingroup\$ This could use either a link to a page that clearly explains the terms and method used, or preferably a better explanation within the post. \$\endgroup\$ – Geobits Oct 14 '15 at 18:42
  • \$\begingroup\$ Good idea, I will link it. \$\endgroup\$ – Mutador Oct 14 '15 at 18:43
  • \$\begingroup\$ The fact that this is time series doesn't change anything since it's just OLS estimation, which is not specific to time series. OLS requires two dimensions, so x is essentially position in the series and y is the value of the series? \$\endgroup\$ – Alex A. Oct 14 '15 at 18:43
  • \$\begingroup\$ I thought about saying time series to add some context, but yeah, it is just that, not sure about the output though. \$\endgroup\$ – Mutador Oct 14 '15 at 18:46
  • 1
    \$\begingroup\$ What does lm() do? \$\endgroup\$ – flawr Oct 14 '15 at 18:53
  • \$\begingroup\$ @flawr lm() is a function in R for fitting linear models. \$\endgroup\$ – Alex A. Oct 14 '15 at 19:33
1
\$\begingroup\$

Cops and Robbers: Text Transformations

Cops' challenge

The cops must write a fully deterministic program that reads input from STDIN and writes output to STDOUT as its only side effects. The mapping from strings to strings performed by this program will be called f.

A cop's post consists of such a program's source code, along with its length and the name of the language the program is written in. The poster must also prepare a possible crack (see below), and release it when their post is safe. A cop's post is safe when it remains uncracked for exactly two weeks.

A safe post where the original code is n bytes long is worth 1/n² points. The author with the highest point total wins. The tiebreaker is popularity (sum of votes of answers in the robbers' thread.)

A single author may not use the same language twice in two different cop answers.

Robbers' challenge

To crack a cop's post, a robber must figure out which transformation f the program in the post is performing, and write a program P in the language used by the cop, so that both P and f(P) perform the transformation f.

The length, method, or complexity of P are irrelevant; as long as is produces the same output as the cop's original code for any input you pass it, the solution is valid.

Successfully cracking a cop's post is worth one point. The author with the highest point total wins. The tiebreaker is popularity (sum of votes of answers in the robbers' thread.)


This is a bit hard to conceptualize, so here's a very simple example.

If the cop's post is:

Python 3, 20 bytes

print(input()[::-2])

(i.e., reverse STDIN and remove every other character) The robber's answer might be:

print(input()[::-2])# ) ] 2 - : : [ ) ( t u p n i ( t n i r p

as passing this program as input to itself yields a new program that does the same thing:

print(input()[::-2])#]-:)tpitip

As another example, if a cop writes a C++ program that rotates lines on STDIN by 90 degrees, a valid solution is a C++ program that also rotates lines by 90 degrees, and does the very same thing if you rotate it by 90 degrees.


The difficulty for cops is to come up with transformations that are short to express, but difficult to code around (and, of course, they essentially have to crack their own post -- but at least they know f in advance.)

The difficulty for robbers is to decipher the cops' solutions to find out which transformation f they're performing, and then write any program P such that both P and f(P) perform f.

\$\endgroup\$
  • 1
    \$\begingroup\$ "A single author may not use the same language twice in two different cop answers." Not a fan of rules like that. Anyway, is there anything to prevent a cop from using a function like "Return the (n/2)nd character of the string." In that case it's pretty much impossible for f(P) to compute this function. Or should the mapping be surjective? Also do cops and robbers have to use the same language? Finally, how do we prove that a robber's implementation computes the exact same function as the cop's, especially if the cop's code is obfuscated and undocumented? \$\endgroup\$ – Martin Ender Oct 19 '15 at 12:07
  • \$\begingroup\$ If it's impossible for f(P) to compute f, the original post is invalid anyway -- cops must be able to crack their own cop answers and release the solutions if they go uncracked. Also, yeah, they would use the same language. \$\endgroup\$ – Lynn Oct 19 '15 at 13:16
  • \$\begingroup\$ @feersum pointed out a more serious problem in chat: cops can post something like x = readline(); if (md5(x) == 'f0a92b8efc0...') print x, which is nearly impossible for other people to solve. \$\endgroup\$ – Lynn Oct 19 '15 at 13:18
1
\$\begingroup\$

Watermelon Contest

You and your buddies are contesting a lone piece of watermelon left in the middle of the table. You decide to make a program to contest for you.

The Goal

You want to be the last program standing. Then you get the watermelon.

The Process

Every iteration 1 program will be eliminated from the watermelon contest. This will be decided by a vote among all the remaining programs. This means that your program will have 1 and only 1 vote to spend on the elimination of another program. Whichever program ends up with the most votes is eliminated.

This continues until there are only 1 program left, the winner. This entire process is considered a "round".

After there is a winner, another round will be started with a new piece of watermelon. All programs will be re-entered. When 10,000 rounds have been completed, the program with the most "wins" will be considered the "grand champion". All the rounds combined is considered the "tournament".

The Catch

Every program will have an opportunity to send a message to all the other programs. The message must be the same for every program. The message is a string, up to 500 bytes long.

You may have a file in which you may store any data you wish from previous rounds. This will persist over the entire tournament.

The Program

Write a program or function that accepts the following input in any (convenient) form:

[program-name], [message], "The Slug", "hey! don't vote for me!", "Chucknorium II", "a2TEI5ds#" ...

and outputs the name of the program that you vote for:

Chucknorium II

Notes

  • In the likely event of a tie, one of the high scoring programs will be randomly eliminated
  • Messages can be anything that doesn't mess with stuff it's not supposed to (e.g. don't mess with the controller or other people's programs). This is what makes the challenge interesting.
  • You may not hard-code program names into your program! In other words, numbering the programs randomly at the beginning of the game should produce the same output. Names are just more fun.
  • For observation purposes, your program will still be run even if it has been eliminated. It will not, however, have a chance to vote that round.
\$\endgroup\$
  • 3
    \$\begingroup\$ This seems to reward out-of-band collaboration (or posting multiple answers, which is effectively the same thing). \$\endgroup\$ – Peter Taylor Oct 20 '15 at 8:20
  • \$\begingroup\$ So the winner between the last two is basically always random (since I assume neither will vote themselves out)? \$\endgroup\$ – Geobits Oct 20 '15 at 18:34
  • \$\begingroup\$ @Geobits correct. Over several thousand rounds this should even out. \$\endgroup\$ – Stretch Maniac Oct 20 '15 at 19:49
  • \$\begingroup\$ I see. There's nothing about how many rounds will be played, so I was wondering about that. If you add this, you should make sure to distinguish turns/rounds or rounds/games, etc. \$\endgroup\$ – Geobits Oct 20 '15 at 19:53
  • \$\begingroup\$ Also, do programs continue to be called once they're "out"? If I want to track who did well each round, for instance, I don't think I can (since I think I only get input up to when I get voted out). \$\endgroup\$ – Geobits Oct 20 '15 at 19:56
  • \$\begingroup\$ Good point. Yes. You just won't be able to vote. I'll change that (and other things) when I get to a computer. \$\endgroup\$ – Stretch Maniac Oct 20 '15 at 19:59
  • 1
    \$\begingroup\$ I don't need to hard-code program names: I just need to agree a signature algorithm whereby the combination of name and message means that either the program is a collaborator or they're piggybacking on our agreement. \$\endgroup\$ – Peter Taylor Oct 20 '15 at 20:37
  • \$\begingroup\$ I see... How about a statement that prevents engineering to specific programs? Would that prevent pre-determined collaboration? \$\endgroup\$ – Stretch Maniac Oct 20 '15 at 20:42
  • \$\begingroup\$ Can you clarify the format of the input \$\endgroup\$ – user193661 Oct 21 '15 at 9:05
  • \$\begingroup\$ I hate to be a party pooper, but I honestly don't see the point of this KOTH since it seems to be more politics than programming. Then again I didn't get the cake cutting one either and look at how that one turned out... \$\endgroup\$ – Sp3000 Oct 23 '15 at 12:36
1 25 26 27 28 29 90

You must log in to answer this question.

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