555
\$\begingroup\$

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

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

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

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

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

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3919 Answers 3919

1
3 4
5
6 7
131
5
\$\begingroup\$

The Virtual Prisoners

Background

The year is 2251. You are a self-evolving KOTH bot, in the mysterious land known as Programming Puzzles and Code Golf. To evolve, you need permissions, and to get permissions, you need reputation. You decide that the best way to do this is to take over all of the questions to gain as much reputation as possible. The only problem? Every other bot has decided to do the exact same thing.

Game Explanation

Each round is battled on a question, with 11 vote nodes, between you and your enemy. The board starts as this:

A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11

A is player A's nodes, B is player B's nodes, and N is a neutral node.
Each turn, you may:

  • Vote on a vote node. If both players vote, nothing happens. If one side votes:
    • and the node is controlled by no-one (neutral), it becomes that side's.
    • and it is controlled by the voter's enemy, it becomes neutral.
    • and it is controlled by the voter, nothing happens.
  • Guard a vote node. This guards the node from votes (friendly or enemy) for 2 turns.
  • Use your 'power'. The powers are listed below, including how to use them.

Your side wins if it controls at least 2/3rds (66%) of the vote nodes.

10000 rounds will be run, and the winner of the KOTH is whichever bot has the most wins (in the event of a tie, or indeterminate outcome, more matches are run until a clear winner is decided.)

How Your Bot Should Work

It should accept as command-line arguments:
B A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11
Where A denotes Player A's nodes, N denotes a neutral node, B denotes Player B's nodes, and the first argument (B in this case) is the player your bot is. (This is decided randomly, your bot should work regardless.)
It should return one of the following (powers are general rules):

  • V-4, vote on node 4
  • G-3, guard node 3
  • P-N, use power 'Neutralize'
    with or without a trailing newline.

    Powers

    Intended to give bots a small boost. If X was your power, you would use P-X. You may only have one power per bot.

  • N - Neutralize: Turn 2 random nodes to neutral ones.

  • R - Rebellion: Pick a random node, and randomly turn it to a friendly, neutral, or hostile node.
  • S - Swift Strikes: Pick two random nodes, and vote on them.

Here are the extra rules:

  • The bots must fully run offline.
  • The bots may not attempt to read any files, including their own source code.
  • The bots may not tamper with, hack, or destroy other bots.
  • The bots must return one of the three commands (V, G, or P). If they do not, they forfeit their turn.
  • The bots must not be targeting other bots specifically. (Beating general strategies is welcome.)
  • You may update your bot as often as you like, but bots that are updated very frequently with no good reason (i.e, fixing fatal errors is a good reason) will be disqualified.
  • Your bot must take under 90 seconds for it's turn. If it takes longer, it will be disqualified.

Submission contents

Your submission must contain:

  • The code for the bot
  • The language it is written in (and a link to an offline interpreter, if necessary)
  • Your bot's name (for the leaderboards)
  • How to compile and run your bot

If you do not include all of the required items in your submission, you will be notified, but your bot may not compete until this is fixed.

Example Match

Matches are organized between 2 randomly-selected bots. Here is an example, with bots A and B:
The board begins as this:

A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11

Bot A makes his move, voting on N4, then Bot B votes on N5:

A1 A2 A3 A4 B5 N6 N7 N8 B9 B10 B11

Node 4 becomes A4, and it is now controlled by Bot A. Likewise, node 5 becomes B5.

A votes on N8, and so does B:

A1 A2 A3 A4 B5 N6 N7 N8 B9 B10 B11

Why did nothing happen? That's because both bots voted on the same node - cancelling out each other's effects.

When one bot controls 66% or greater of the nodes, that bot gains a win and the other bot gains a loss.

The game ends after 1024 turns, to prevent any bots that wait around forever. Whoever has the most nodes afterwards wins, or a draw if they have the same amount.

Additional Notes

  • I will be submitting an example bot written in Python as part of my challenge. You are free to use and modify this bot for your submission.
  • If your bot gives invalid output (not of the form C-A, where C is the command and A is the argument), the bot forfeits its turn. If it does, you will be notified, and your bot will be removed until it is fixed.

Meta Questions and Notes

  • Are there any loopholes?
  • Should I add/modify/delete some of the powers?
  • Is something too simple/confusing/uninteresting/overpowered?
  • Should bots be able to see which nodes are and are not guarded?
  • Should I limit people to one bot? If not, I will prevent the same person's bots from battling each other.
  • I have thought of the following alternative way to win matches:
    • The game lasts 1024 turns. Whoever has the most nodes at the end wins.
    • If, at one point, one bot controls all 11 nodes, that bot automatically wins.
  • Would this be a better win condition?
\$\endgroup\$
10
  • \$\begingroup\$ I have a few questions. 1) If I make a new node, will it be neutral? 2) How are the matches organized? If there are, say, 5 submissions, does each pair have a separate battle, after which you count victories, or do they somehow work in teams (as the title suggests)? 3) With some strategies it may be that the game runs forever. You should probably add a time limit (some N turns), after which the game automatically ends in a draw, or a win for the player controlling the most nodes. \$\endgroup\$
    – Zgarb
    Apr 7, 2015 at 15:38
  • \$\begingroup\$ @Zgarb Thanks for your feedback! I've included a section on how the game works. \$\endgroup\$ Apr 7, 2015 at 15:53
  • \$\begingroup\$ Could you add C# (or .NET in general?) \$\endgroup\$ Apr 7, 2015 at 15:55
  • \$\begingroup\$ @LegionMammal978 How do you install that on Linux? The list is mostly because I can't run a lot of things like GolfScript, but I'd be glad to, if you can tell me where to find it. \$\endgroup\$ Apr 7, 2015 at 15:56
  • \$\begingroup\$ @ASCIIThenANSI you could use Mono. I'm mainly just looking for C#. \$\endgroup\$ Apr 7, 2015 at 16:02
  • \$\begingroup\$ @LegionMammal978 Oh, OK. Turns out I installed it for an earlier purpose, thanks for your help! \$\endgroup\$ Apr 7, 2015 at 16:09
  • 1
    \$\begingroup\$ It's not complete, but this question has instructions for running a number of languages. \$\endgroup\$ Apr 15, 2015 at 22:15
  • \$\begingroup\$ @PeterTaylor Thanks for the link! \$\endgroup\$ Apr 16, 2015 at 12:57
  • \$\begingroup\$ Maybe add a clock time limit for each turn, so bots don't simply run an endless loop blocking you running the simulation? \$\endgroup\$ Oct 11, 2015 at 8:33
  • \$\begingroup\$ @PaŭloEbermann I'll watch each of the simulations (with output on what the bots are doing), and any bot that takes too long is disqualified. \$\endgroup\$ Oct 12, 2015 at 14:04
5
\$\begingroup\$

I nearly posted this without sandboxing, but thought it was perhaps too trivial - comments welcome. I was considering perhaps making it too with no digits [0-9] in the source code.Done.

Golf the numbers round a dartboard

For those of you not familiar with the game of darts, a standard dartboard looks like this: enter image description here

This challenge is simple - output the sequence of numbers starting from 20 moving in a clockwise direction:

20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5

To make it a bit more interesting, the digits [0-9] may not appear anywhere in your source code.

  • Your entry must not accept any input and it must output this list in exactly this order.
  • The formatting of the list output may be whatever is convenient for your language.
  • You must not use any builtins designed explicitly to generate this sequence.

OEIS fans may like to note that this is sequence has an entry.

\$\endgroup\$
7
  • 4
    \$\begingroup\$ I like the restricted source version \$\endgroup\$
    – quintopia
    Dec 9, 2015 at 19:16
  • 1
    \$\begingroup\$ @TimmyD Link added. I'm surprised we don't have an OEIS tag - I guess it wouldn't really add much. \$\endgroup\$ Dec 9, 2015 at 20:18
  • 1
    \$\begingroup\$ @ quintopia - yes, I think that's probably the way to go - edited. \$\endgroup\$ Dec 9, 2015 at 20:19
  • 1
    \$\begingroup\$ I was able to do this in CJam in 26 bytes using character to int conversion (it only didn't work online for 13 because it's character is carriage return.) Should this be allowed? goo.gl/JxEcjo . Also, in CJam 1,2,3 and 10-20 are single letter constants. Should those be allowed? \$\endgroup\$
    – geokavel
    Dec 10, 2015 at 5:58
  • 1
    \$\begingroup\$ @geokavel yes, and yes. \$\endgroup\$ Dec 10, 2015 at 6:16
  • 2
    \$\begingroup\$ This is just asking for string compression, especially since digits can't be used even indirectly. \$\endgroup\$
    – xnor
    Dec 10, 2015 at 19:32
  • \$\begingroup\$ @xnor to discourage that, maybe restrict entries to printable ASCII (or give a bonus of *log 95/log 256 for using only printable ASCII)? \$\endgroup\$
    – lirtosiast
    Dec 10, 2015 at 23:40
5
\$\begingroup\$

Verify a game of Morpion Solitaire

Morpion Solitaire is an interesting, unsolved "single-player game". (The linked site lists several variants - we're talking about 5T here.) It has been proven that solving or even approximating it is NP-hard. But we're going to do something simpler here: your challenge will be to verify whether the game has been played correctly.

The rules are fairly simple. You start on a regular (infinite) grid, with 36 intersections marked in the following shape:

enter image description here

Now a move consists of drawing a straight line segment, orthogonally or 45 degrees with the grid, through four marked and one unmarked intersection. The unmarked intersection will then be marked for future moves:

enter image description here enter image description here enter image description here
enter image description here enter image description here enter image description here

The lines may cross or touch, but they must never overlap (notice that the last move shares an endpoint in a straight line with an earlier move, but does not overlap with it). The goal of the game is to make as many move as possible. The world record is at 178 moves.

Because the grid gets very messy after a while, it becomes very hard to reconstruct a game. People work around this problem, by writing consecutive numbers into the intersections they add. However, even when this is not done, it is always possible to verify the validity of game.

Further reading:

The Challenge

You're given an ASCII representation of a played game of Morpion Solitaire (the game may or may not be finished). Every other cell represents an intersection, which can be either unmarked (.), one of the initial intersections (o) or one of the intersections added by a move (#). All other cells are either spaces, or one of -, |, /, \, X indicating that a line-segment was drawn across the two adjacent intersections. The example above would look like this:

. . . . . . . . . . . .

. . . . o-o-o-o-# . . .
        |/     /       
. . . . o . . o . . . .
       /|    /         
. . . # o . # o . . . .
     /  |  /           
. o-o-o-o-# . o o o o .
   /    |/             
. o . . # . . . . . o .
        |              
. o . . # . . . . . o .
        |              
. o o o o . . o o o o .
        |              
. . . . o . . o . . . .
        |              
. . . . o . . o . . . .

. . . . o o o o . . . .

. . . . . . . . . . . .

Output a truthy value if the game represented by graph can be played by following the rules, and a falsy value otherwise.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may assume that the initial intersections always form the cross shape displayed above (although I doubt any answers will be affected by this).

Your code should solve any of the test in less than 5 seconds. This should not be an issue as very efficient solutions exist.

Standard rules apply.

Sandbox Notes

  • Will add test cases...
\$\endgroup\$
8
  • \$\begingroup\$ The simplest representation for parsing would be to give either the endpoints of each line as cartesian coordinates, or one endpoint and a direction (either one of 8 directions, or it could be standardized to one of 4 directions if the N/E/NE/NW is always the endpoint given.) Checking would then be fairly straightforward: start with the empty grid and see which lines are allowed, until all are exhausted. \$\endgroup\$ Dec 21, 2015 at 9:34
  • \$\begingroup\$ The ASCII art representation will require more effort for parsing: I think it's unambiguous because you can identify endpoints by looking for for intersections which don't have opposite pairs of |_\/, but it could take quite a few parses through the file. You would also need some way of identifying the start points. \$\endgroup\$ Dec 21, 2015 at 9:35
  • \$\begingroup\$ @steveverrill There will be no information about endpoints in the input. In a finished game (without numbering) you only have individual line segments (four of which make up a move). That's why I think an ASCII representation is simpler than a graph, where you need to piece together manually which edges form a straight line of four segments. I also think an ASCII representation doesn't necessarily need to be parsed at all: I think it can be solved straight via manipulation of the character grid (in fact, this should be doable in Retina). \$\endgroup\$ Dec 21, 2015 at 9:45
  • 1
    \$\begingroup\$ 1. It would be clearer to talk about drawing a straight line segment through 4 marked and one unmarked lattice point, as "straight line" often implies that it's infinite. 2. It seems that the lines must be axis-aligned or at 45 degrees to the axis. If so, it would be good to state that explicitly in the description of play. 3. The page linked in the first sentence is very uninformative. I assume you did it because the diagrams on the Wikipedia page are for a different initial setup, but there must be some better external link. \$\endgroup\$ Dec 21, 2015 at 9:48
  • \$\begingroup\$ In that case I would go for the ASCII art representation. It also depends to some extent on which is the most convenient way for you to obtain / generate test cases. \$\endgroup\$ Dec 21, 2015 at 9:51
  • \$\begingroup\$ @PeterTaylor Thanks, I'll edit those suggestion in. As for the page I linked, did you see the navigation in the left iframe? (I overlooked that at first.) I'll link to Wikipedia as well though. \$\endgroup\$ Dec 21, 2015 at 9:52
  • \$\begingroup\$ I agree with Peter that the website is a bit of a mess. There are many variations of the game, so I think you should state that this is the 5T variant (identified by the fact that Christopher Rosin holds the records for 5T at 178 moves and 5D at 82 moves.) It took me a while to work out why Marc Bertin at 216 moves in 1974 was not the record holder: (He was playing 5T+.) Only the 5T (endpoints of parallel lines touching allowed) and 5D (endpoints of parallel lines must be disjoint) variants are unsolved according to the website. \$\endgroup\$ Dec 21, 2015 at 9:57
  • \$\begingroup\$ The person who wrote that site needs to be dragged kicking and screaming into the 21st century. But I'd prefer a link to morpionsolitaire.com/English/Rules.htm and the navigation be damned than a link to the front page. \$\endgroup\$ Dec 21, 2015 at 10:01
5
\$\begingroup\$

Four-Byte Bloom Filter

Bloom filters are cool. In the words of that Wikipedia article:

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set".

The motivation behind Bloom filters is that, by giving up perfect accuracy, the amount of memory necessary can be dramatically decreased.

A Bloom filter takes the form of a set of bits, along with a set of hash functions. To insert something into the Bloom filter, calculate the N different hashes and flip those bits to 1.

initialization 
00000000

letter `P` maps to 1 when using hash function F and 6 when using hash function G
01000010

Additional elements are added over top previous ones.

letter `h` maps to 6 and 4
01001010

To test if an element is a member of a set, perform the hashes and check to see if those bits are 1. If not all of them are 1, then it can't possibly be a member of the set. If they are all 1s, then it could be a member.

letter `W` maps to 0 and 4
01001010
^   ^
`W` is not a member

letter `P` maps to 1 and 6
01001010
 ^    ^
`P` could be a member (it is)

letter `i` maps to 4 and 1
01001010
 ^  ^
`i` could be a member (it is a false positive)

As more elements are added to the set, the probability of false positives increases. In large-scale applications, a Bloom filter with a small error rate is still an order of magnitude smaller than an exact database. Below is a neat diagram from this great article on probabilistic data structures.

enter image description here


In this challenge, you will implement a miniature Bloom filter. A really, really small Bloom filter with 32 bits. Your data type will be the 94 non-whitespace printable ASCII characters.

Functionality

The Bloom filter will have 32 bits and 2 hash functions. It is up to you what those two hash functions are, they simply must be decently independent of one another. (Sandbox note, should I specify the hash functions?). Your program will be asked to do two separate tasks:

  • Given a current state of the bloom filter and a list of characters, add those characters to the filter and output the new filter state
  • Given a current state of the bloom filter and a list of characters, test those characters for membership and output a list of truthy (could be a member) or falsey (definitely not a member) values.

Formatting specifics

Input consists of the current state, an operation, and a list of characters. The Bloom filter state will be represented as a string of 8 hexadecimal characters. This will then be followed by either + for adding or ? for membership testing. Finally, there will be a list of between 1 and 94 characters (printable non-whitespace ASCII) as data points.

Output will either be the new state, as 8 hex characters, or a list of truthy/falsey values.

Example I/O

This represents adding the characters in my username to a blank filter
00000000+PhiNotPi
This is a possible output (7 bits have been permanently flipped)
48a01030

This represent adding the character 1 to the current filter
48a01030+1
This is a possible output (9 bits flipped so far)
48a01074

This represents testing for membership of Phi
48a01074?Phi
Output must be all true since they were added in earlier
[True, True, True]

This represents testing for membership of 12345
48a01074?1234
Output must be true for 1, but not necessarily false for the others
[True, False, False, True, False]
\$\endgroup\$
1
  • \$\begingroup\$ You should specify the hashing function, if you don't want the hashing function is a mod 32 or worse, return 4. \$\endgroup\$
    – Xwtek
    Jan 14, 2016 at 14:34
5
\$\begingroup\$

The largest convex polygon

Given an input of at least one coordinate pair on the Cartesian plane, determine the largest number of sides a convex, non-self-intersecting polygon formed from those points can have.

A convex polygon is a polygon such that there is an angle strictly less than 180˚ and greater than 0˚ between each pair of consecutive sides. Note that if three points are collinear, they still only form one side. Two sides cannot have a 180˚ angle between them.

The ordinate and abscissa of a coordinate are not necessarily integers, and they can be positive, negative, or zero.

If there are less than 3 points, or if the points inputted cannot form a convex polygon, the program should output 0.

Test cases

(0,0) (1,1) (3,4)
==> 3

(0,0) (-1,-1) (5,5)
==> 0

(-1,0) (1,0) (0,1) (5,5) (-5,5) (0,-5)
==> 3

(-3,2) (4,6) (-1,2) (0,4) (5,-3) (-2,-2) (1,1)
==> 5

(0,0) (10,0) (10,10) (9,1) (10,4) (9,6) (5,4)
==> 5

Here are pictures for the test cases, in order. Note that solutions are not necessarily unique. (Made with Geogebra)

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

\$\endgroup\$
7
  • \$\begingroup\$ For the third test case, can't you get a four-side polygon (-5,5) -- (5,5) -- (1,0) -- (-1,0) -- (-5,5)? (or (0,-5) -- (-1,0) -- (0,1) -- (1,0) -- (0,-5)) \$\endgroup\$
    – David
    Feb 16, 2016 at 0:09
  • \$\begingroup\$ @David Thanks for catching that. I will fix it tomorrow, \$\endgroup\$
    – Arcturus
    Feb 16, 2016 at 5:06
  • \$\begingroup\$ This could probably use some more test cases where the result is not the convex hull... if possible even one where none of the points of the convex hull are part of the solution. \$\endgroup\$ Feb 16, 2016 at 7:45
  • \$\begingroup\$ @MartinBüttner The last test case is not the convex hull, as (10,0) and (10,10) are not included in the output polygon. \$\endgroup\$ Feb 16, 2016 at 15:08
  • \$\begingroup\$ @TimmyD The emphasis in my sentence was on "more". ;) (I admit that may not have been obvious.) \$\endgroup\$ Feb 16, 2016 at 15:09
  • \$\begingroup\$ @MartinBüttner I read it as "This could probably use some more test cases, [such as] where the result is not the convex hull" ... yay, English. \$\endgroup\$ Feb 16, 2016 at 15:15
  • \$\begingroup\$ @TimmyD I like ambiguity more than most people. \$\endgroup\$ Feb 16, 2016 at 15:22
5
\$\begingroup\$

Battle Snake

Introduction

The classic snake game where bots control the snakes. Can you create a bot that out lives the rest?

Snakes will enter the arena and hope to survive. Eat pellets and grow in length. Can you force your competition to crash and die while you survive?

See video for visuals of my simple bot playing against itself. I am sure you can do better!

Features

  • Real-time graphics provided by Love2D
  • Multiple snakes per game
  • Solo game as well
  • Humans can play too!
  • Highly configurable settings
  • Supports any programming language that can use sockets.

Requirements

  • Love2D: 2D game engine written for Lua
  • Socket-compatible programming language
  • Controller: The main controller for this challenege

Optional

  • Lua winapi: Handy way to spawn processes in the background

Controller Contents

  1. main.lua: Main loop for Love.
  2. snake.lua: Support library for game mechanics
  3. config.lua: Configuration settings.
  4. bots\: location of externally-defined bots
    1. simple.lua: Example bot written in Lua

Executing

Run the love2d executable on the controller directory

love.exe <location_of>\battlesnake

or

[Recommended] Use ZeroBrane Studio with the 'Love' interpreter. Change your project directory to where you installed the controller, and then run the script in ZeroBrane. You'll still have to install Love separately.

Configuration

All configurable options are located in the config.lua file in the controller. The options are detailed in that file itself.

Rules

General snake rules apply. Hit something and you die. This includes the walls, other snakes, or even yourself.

Collisions happen before the board is updated. Therefore, if you move to a spot where another snake's tail is, it will still cause a collision. Even though it could be moving away that turn. If two or more snakes enter the same spot the same turn, they all collide with each other.

Eat a pellet and gain points. You also grow in size for a number of turns. Your head continues moving but your tail stays stationary until you stop growing.

Mechanics

The game uses a server-client model, where the main game loop is the server and each snake is a client. The game communicates to each snake over TCP through an assigned port. The default host is the localhost, no external networks are required.

When the game starts, it will start each snake (aka bot) by starting its associated program and sending the IP ADDRESS and PORT and PLAYER ID to it as input arguments:

bots\someBot.exe 127.0.0.1 52311 1

The main server then waits for a socket connection from that bot at the given IP and PORT. If the connection times out, it will error and the game will not start. If the server receives a connection from the bot, it will proceed on to the next bot.

Once all bots are started and connected to the server, the game will be generated. Bots are expected to block until receiving data from the server. Typically this is just an infinite loop with a blocking socket.receive() call at the top of the loop.

Board

The game board can be of any width and height. The coordinate system starts at x = 1, y = 1 at the top-left. Increasing x values go left-to-right and increasing y values go top-to-bottom. The board has hard walls, hitting them will kill your snake. (Lua is 1-based, that is why it starts at 1)

Order of Events

  1. First the game settings are broadcast to all bots

    1. Board Information

      bi width,height

      Where width and height are integer values

    2. Pellet Location

      p x,y

      Where x and y are integer values >= 1 and <= to their respective width and height.

    3. For each bot

      • For each body part, starting at the head and going to the tail

        si snake_id x,y

        Where snake_id is an integer value, and x and y are as described before.

    4. Ready signal

      ready

      All bots are initialized by now, so the next command will be from the main game loop.

  2. Main Loop

    1. For each tick (tick is when all snake movements will be applied)

      1. Server will broadcast to each bot

        mov

        The bot needs to respond to this request with a direction to head in

        • r Head Right
        • l Head Left
        • u Head Up
        • d Head Down

        If the bot doesn't respond within a specified time, it will continue to move in its previous direction. (Previous direction is r on the first turn)

        The bot should send a single char back, nothing more will be parsed.

      2. Check End Game Conditions

        If the game ended this tick each bot will be sent either a quit or nil message from the server. Each bot is expected to clean up after itself when it receives this signal.

      3. Updated Pellet Info [optional]

        If a pellet was eaten this tick, a new pellet packet will be broadcast to all active bots

        p x,y

      4. Server broadcasts snake deltas that were applied this turn

        s snake_id new_x,new_y,removed_x,removed_y

        Where all parameters are integers. new_x and new_y are the new head location of a given snake.

        If removed_x and removed_y are >= 1, this is where the tail used to be, so each bot knows the updated board.

        If remove_x and removed_y are == -1, then that bot is actively growing in size, so its tail didn't move.

        If a snake died this tick, its deltas will not be broadcast. It is up to the bots to remove the body from their game state.

See the example bot for details

Matches

Games are grouped together in best-of matches. For the purposes of the bots, they do not need to understand the concept of a match. The bot that wins the required number of games in a match is declared the match winner.

Scoring

  1. Scoring

    • Match winner: +2500 points per match
    • Last Man Standing: +1000 points per game
    • Pellets Eaten: +50 points per pellet
    • Game Ticks Alive: +1 point per tick

    If two or more bots enter the same square on the same tick, they all die. If this square happened to be the pellet, none of those bots will be rewarded the pellet points. However, the pellet will be "consumed" and a new location will be generated for the remaining bots to eat.

    If there is a tie at the end of the game among the bots, the game is a wash. A new game will be started.

  2. King-of-the-hill Scoring

    This challenge will combine two parts: A solo effort and a classic king-of-the-hill part.

    Each bot will be given the same random seed at the start of the competition. There will also be imposed a maximum time between eating pellets to prevent bots from going around in circles to farm points.

    1. Solo

      Each bot will enter into a 10-game match to see how long it lasts and how well it eats by itself. The scores of each game in the match will be summed to compose its final Solo-score.

    2. King-of-the-hill

      All the bots will enter into a best-of-39 match. If the game ends and there is still a final living bot, the game still end at that point. That bot will be given the last man standing bonus.

      The scores of each game will be summed and composed into the snakes final KOTH-score.

    3. Final Scoring

      All the bots will be ranked in each part separately. Ties in ranks are permitted at this stage. Then their positional rank in each part will be summed together to give their final score. The bot with the lowest combined rank wins!

      In case of a tie at this level, the bot with the better KOTH rank will win. If still a tie, the bot with the better Solo rank will win.

Sandbox Questions

My biggest concerns

  1. Requires a few third-party programs to work. So that will limit the number of people who enter.
  2. Requires sockets. I couldn't figure out a good way with Lua\Love2d to have bidirectional pipes with STDIN and STDOUT. So I thought sockets would be the best alternative to open the challenge to as many people as possible.
  3. Too hard?
  4. Haven't optimized scoring yet.
\$\endgroup\$
5
\$\begingroup\$

Count the Cats

This is a cat:

Specifically, that is my cat. She is my only cat. And, in that image, there is only one cat: her.

These are also cats (image credit):

In that picture, there are two cats. It is relatively easy to count them, thanks to their distinct coloring.

This is a picture of 5 cats (image credit):

It's harder to differentiate the cats because of their similar coloring, but there are definitely 5.

This is a landscape (image credit):

There are no cats in this image.

The Challenge

Given an image, output the number of cats in the image.

Rules

  • Submissions must output and terminate within 1 minute for a single image.
  • Any common image format is acceptable for input, as long as no additional data (such as the number of cats present in the image) is encoded in the format.
  • Submissions must be fully deterministic, and make a genuine attempt at counting the cats. Outputting a random number or a consistent but unrelated number (such as the value of the last hex digit of the SHA-256 hash of the image data) is not allowed.
  • The images in the test cases will contain no animals besides cats. There may or may not be humans in the images - they are not cats, and thus should not be counted as cats.

Scoring

The score for a single image is the square of the difference between the true number of cats in the image and the output of the submission ((actual - output)**2). The total score is the sum of all of the individual scores. The submission with the lowest score wins.

[scoring images TBD]

\$\endgroup\$
15
  • 2
    \$\begingroup\$ I feel like this is probably a dupe of either the goat question or the rice question. I'm not sure that it being a test battery question or the precise subimage to identify really makes it much different from these other ones? \$\endgroup\$ Jun 23, 2016 at 19:17
  • 2
    \$\begingroup\$ @FryAmTheEggman I don't think it's a dupe of goats - goats wanted a boolean classification, where this one asks for a count. The rice question is closer, but there is a possibility (and perhaps a need) for different approaches, given that a) cats can overlap, b) cats come in different colors, and c) cats have much more complex shapes than rice grains (which are ellipses). \$\endgroup\$
    – user45941
    Jun 23, 2016 at 19:19
  • \$\begingroup\$ "Submissions must output and terminate within 10 seconds for a single image." I don't know about that, counting the amount of cats and only cats is a rather difficult task already, a 10-second limit seems really small. Perhaps a couple minutes? \$\endgroup\$
    – Downgoat
    Jun 23, 2016 at 20:03
  • \$\begingroup\$ Also, I think there should be some specification for how the cats would appear. At least having the full cat's face showing would make this challenge more approachable. If a test-case shows the back of a cat that seems a bit too difficult for a PPCG challenge. Also: Will there be a mix of cats and other animals? Are built-ins allowed (I'm very sure there's mathematica builtin)? \$\endgroup\$
    – Downgoat
    Jun 23, 2016 at 20:07
  • 1
    \$\begingroup\$ @Upgoat The time requirement can be extended. The number of cats will always be clear to a human viewer with 20/20 eyesight and adequate attention for detail. The challenge is about counting cats, not about picking out camouflaged cats, so there won't be any excessive trickery in the test images. Built-ins are allowed, but I'm on the fence about whether or not I'm going to allow them to be competitive, since Mathematica is likely the only language that would benefit from built-ins. \$\endgroup\$
    – user45941
    Jun 23, 2016 at 20:12
  • 1
    \$\begingroup\$ Showing a picture of a dog and expecting a zero output doesn't seem fair. Writing a program that distinguishes between dogs and cats seems like a difficult enough task as it is, and you have it here as sort of an afterthought. Empty images should be emptier, imo. \$\endgroup\$
    – Liam
    Jun 25, 2016 at 22:45
  • 1
    \$\begingroup\$ @Liam On the other hand, if all of the test images consisted of 0-5 cats and no other animals, it would be too easy to get a perfect score. Having harder test cases means that submissions will have room for improvement, and thus there will be more competition. \$\endgroup\$
    – user45941
    Jun 27, 2016 at 1:46
  • \$\begingroup\$ Is fitting allowed? I think learning will probably be the most practical approach to this challenge. Though this does need some specification before it's ready to post imo and limits on the possible inputs as I doubt any answer will be able to conform to the wide variety of things cats can be e.g. color, position, shape, size, direction, camera position, etc. \$\endgroup\$
    – Downgoat
    Jun 27, 2016 at 5:15
  • 1
    \$\begingroup\$ @Downgoat As per usual with these types of challenges, optimizing for the test cases is not allowed. However, given that a ML-oriented approach would be interesting and perform well on this challenge, I'd be willing to include a training set, separate from the scoring set. As for limits on possible inputs, I'm trying to work out a good set. \$\endgroup\$
    – user45941
    Jun 27, 2016 at 5:41
  • 2
    \$\begingroup\$ I think the part about the dog makes this a chameleon challenge -- distinguishing a cat from a dog is much harder than identifying and counting cats on an image free of distracters. \$\endgroup\$
    – xnor
    Jun 27, 2016 at 23:48
  • \$\begingroup\$ @xnor On the other hand, without the distracters, it would likely be too easy to get a perfect score. \$\endgroup\$
    – user45941
    Jun 28, 2016 at 2:48
  • \$\begingroup\$ Distinguishing a cat from a dog on a picture already requires decently advanced algorithms (CNNs are the first that come to mind) which in turn require a LOT of training data to generalize decently. \$\endgroup\$
    – Fatalize
    Jun 29, 2016 at 9:09
  • \$\begingroup\$ @Fatalize Would using non-mammilian animals (such as lizards and birds) be better in your opinion? \$\endgroup\$
    – user45941
    Jun 29, 2016 at 9:10
  • 1
    \$\begingroup\$ @Mego It probably would be easier because it wouldn't force people to use machine learning techniques (You could use texture comparison to distinguish feathers from scales, color detection, etc.). Counting the number of each is an added difficulty that makes it maybe too difficult as a whole. Only classifying is easier but probably a dupe of the goats challenge. Only counting might be good though. \$\endgroup\$
    – Fatalize
    Jun 29, 2016 at 9:14
  • \$\begingroup\$ The problem with this scoring technique is that even if people make legit attempts at counting the cats, they will try to optimize their code for the limited test set, which will make their approaches less general on new data. One solution could be to provide a validation set (for say 2 weeks if that's the time frame in which you can post an answer) on which people can evaluate their answers, and choose the winning answer based on a test set that was not available during those 2 weeks containing new images. \$\endgroup\$
    – Fatalize
    Jul 1, 2016 at 13:27
5
\$\begingroup\$

The Ifelse Tower

You are an inhabitant of the whimsical country of Forance, filled with programmers.

Life in Forance is said to be extremely repetitive, which isn't good to attract tourists. For this, authorities of Forance want to hire someone to print tons of postcards to promote their most iconic landmark: the Ifelse tower.

                   if
                   if
                   if
                   if
                   if
                   if
                   if
                  else
                  else
                 ifelse
                  else
                  else
                ifelseif
                ifelseif
               elseifelse
              ifelseifelse
            elseifelseifelse
              ifelseifelse
              ifelseifelse
              else    else
             else      else
            else        else
           else          else
          else            else
       ifelseifelseifelseifelseif
       ifelseifelseifelseifelseif
       ifelseifelseifelseifelseif
       ifelseifelseifelseifelseif
      elseifelseif    elseifelseif
     elseifelse          elseifelse
    ifelseif                ifelseif
   ifelse                      ifelse
  ifelse                        ifelse
 ifelse                          ifelse
ifelse                            ifelse

But, of course, they want to do this with the least possible cost. So, if you want this job, you have to show you can do this with very little code

Challenge

Write a program or function that takes no input, and outputs to STDOUT the Ifelse tower.

Rules

  • Leading and traling new lines are not allowed
  • Leading spaces are (of course) a must
  • All lines must be at most the same lenght as the base (40 chars). This means you are free to use or not trailing spaces on each line, as long as they don't surpass the base's lenght
  • Standard loopholes are not allowed

This is , so shortest answer in bytes gets the job -err wins

\$\endgroup\$
3
  • 5
    \$\begingroup\$ I'd allow a single optional trailing linefeed. A lot of languages print full lines by default. In some it's annoying to suppress that and in some it's impossible. \$\endgroup\$ Jul 20, 2016 at 7:30
  • 1
    \$\begingroup\$ Why enforced an output to stdout? \$\endgroup\$
    – aloisdg
    Jul 20, 2016 at 12:41
  • \$\begingroup\$ This challenge proposal has been inactive for over a month. I would like to take ownership of the challenge and make it ready for posting. Please let me know within the next 14 days if you have any objections and would still like to finish and post this challenge yourself. \$\endgroup\$ Jun 4, 2017 at 13:05
5
\$\begingroup\$

Interpret a Formal Grammar

Given a context-free grammar, and a string, parse the string using the formal grammar and output the matches for the non-terminals.

Examples

First line is string, following lines are grammar, then is the main grammar to parse, last line is output.

123

n -> any of
     0 1 2 3 4 5 6 7 8 9
N -> n N
     n

N

N [ n [1], n [2], n [3] ]
2+2*(4/2)

o -> any of
     + - / *
n -> any of
     0 1 2 3 4 5 6 7 8 9
E -> o E E'
     ( E ) E'
     n E'
E' -> o E E'
     o E'
     ε

E

E [ n [2], E' [ o [+], E [ n [2], E' [ε]  ] ] ]
a b

S -> S' S
     ε
S' -> a   b

S

S [ S' [a], S' [ ], S' [b] ]

This grammar is the same as regex: [a b]+

Spec

Details:

  • All recursion will be right-recursive
  • Rule names will consist of A-Z a-z α β γ Γ and may have a ' at the end.
    • Valid Rule names:
      • A
      • Γ
      • AB
      • αβ
      • foo'
      • faαβdg'
    • Invalid Rule names:
      • 'ab (' will be at the end)
      • ab'' (two ''s)
      • code golf (spaces not allowed in rule names)
  • Nonterminals will be lowercase, terminals upercase
  • A derivation format will be:

    <rule name> -> <rule>
                   <rule>
                   <rule, etc.>
    

    meaning the rules will be lined up (when in a monospace font), by spaces.

  • Symbols/rule-names will never be repeated
  • ε (epsilon) means empty. i.e. ""

Rule definition:

  • If the initial rule is "any of", the second rule will exist and will be a space separated list of symbols/rule-names (maybe more than one char). There will be no rules after this
  • Else, the rule will consist of space-seperated tokens which either refer to a rule or a literal. If it is not a valid rule name, assume it is a literal which should be treated as if it is a terminal.

Summing up, for input you will be given the string to parse, the grammar, and the rule to parse.

Output:

You may output in whichever format you like as long as it is able to convey the following information. You must somehow label the match to their respective rule names. You may optionally not label terminals.

Challenge Rules:

  • Feel free to assume the input can always be parsed by the given grammar.
  • External libraries (ones that have to be imported), are not allowed
  • If your language has built-in parsing tools (e.g. regex) those are allowed
  • If your language has a built-in to parse a grammar (i.e. some formal grammar parser), these are allowed but your solution is non-competing and you must clearly state this in the header of your answer.

This is so shortest code in bytes wins!

I may award a bounty to any particularly ingenious solutions, so try to add an explanation!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 1. Why the special-case Greek letters in the valid rule names? That seems to add complication for no benefit. 2. Am I correct in thinking that the only way to match a literal space character is as part of an "any of" rule? Some test cases involving literal spaces would be useful. 3. What does "Symbols will never be repeated" mean? 4. The spec for the rule definition uses the words "symbols" and "tokens". It's not clear to me whether these are synonyms, and if not then what the distinction is. 5. May we assume that there is a valid parse tree for the given input? \$\endgroup\$ Jun 11, 2016 at 11:47
  • \$\begingroup\$ @PeterTaylor greek letters are often used in grammars. I'll address number 2, and 4. Symbols are a name of a derivation(s). \$\endgroup\$
    – Downgoat
    Aug 7, 2016 at 22:22
  • \$\begingroup\$ Trying to outsource compiler design for cheddar? Lol, jk, +1! \$\endgroup\$ Aug 7, 2016 at 23:29
  • 1
    \$\begingroup\$ I must say that I never saw any Greek letters except for episilon in the formal language and parsing courses I took, but that wasn't really my point. My point was the special-casing of three lower-case and one upper-case Greek letters. If rule names could contain any character other than - > then it would be simpler. If they could contain any Unicode alphabetic character then it would be simpler (at least for regex users). Also, 6. "Nonterminals will be lowercase, terminals upercase" Does this mean that mixed case tokens are always literals? \$\endgroup\$ Aug 8, 2016 at 7:30
5
\$\begingroup\$

Esolang Interpreters

Using a programming language from this version of this list, write an interpreter for the next language on the list. For example, if you choose to start with LOCK, you would write an interpreter for LOLCODE. Continue this pattern (use LOLCODE to write an LCBF iterpreter, etc)
If specs of a language are unclear and the compiler is nonexistant or closed-source, ask me and I'll decide whether or not to take it off the list.

Wining Criteria:
The longest streak of compilers wins.


Proposed Edits:
Make several defined starting points. (this would make many answers too similar, though)


Edits: changed from list of all esolangs to just turing complete ones.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ I like it, but it may be a trivial task depending on what language you choose \$\endgroup\$ Aug 24, 2016 at 21:37
  • \$\begingroup\$ I think this would be better as a similar challenge to the enterprise quality code, but where the winner is the one who does the most languages at the end at you need to go in order. If you don't think so, I'll make a separate sandbox post. \$\endgroup\$
    – Riker
    Aug 24, 2016 at 21:39
  • 1
    \$\begingroup\$ In order to prevent edits, you can simply use the version in the url: esolangs.org/w/index.php?title=Language_list&oldid=49177 \$\endgroup\$ Aug 24, 2016 at 21:41
  • 1
    \$\begingroup\$ I agree with Easterly, but I'd also make it a cycle based-system. Aka, the interpreter for "!!!Batch" must be written before the interpreter for "???" can be written. You could also have multiple starting points, one for each letter. \$\endgroup\$ Aug 24, 2016 at 21:45
  • \$\begingroup\$ Actually, better idea, score them based on the number of consecutive interpreters they write. \$\endgroup\$ Aug 24, 2016 at 21:48
  • \$\begingroup\$ How will you deal with cases where one language is a joke language and/or not Turing complete, and therefore cannot interpret the next language? \$\endgroup\$ Aug 24, 2016 at 21:56
  • \$\begingroup\$ @El'endiaStarman should I use this list instead? \$\endgroup\$ Aug 25, 2016 at 0:09
  • \$\begingroup\$ @Nathan Merrill I think I will do that, yes. Great suggestions. \$\endgroup\$ Aug 25, 2016 at 0:10
  • \$\begingroup\$ @BaldBantha: That would be better, but you may still run into problems such as languages being technically Turing complete, but entirely impractical. For instance, try multiplying two numbers in Pancake Stack. \$\endgroup\$ Aug 25, 2016 at 0:12
  • \$\begingroup\$ @El'endiaStarman Oh, well this challenge isn't supposed to be easy. I assume the first few answers will include 2-3 interpreters (depends on the starting points, TBH), but I think it would stall for a while. TLDR: I don't feel like classifying several hundred langueges as practical or not. \$\endgroup\$ Aug 25, 2016 at 0:16
  • \$\begingroup\$ The bigger issue I see is that many languages don't have completely solid specs, so it's not clear what counts as a valid interpreter of the language. \$\endgroup\$ Aug 25, 2016 at 8:53
5
\$\begingroup\$

Sesquiprimes

Given a non-negative integer N, output the Nth sesquiprime integer.

We say that a positive integer I is sesquiprime if I + ⌊I/2⌋ is prime (where ⌊...⌋ is the floor function).

For example, 25 is a sesquiprime because 25 + ⌊25/2⌋ = 25 + 12 = 37, which is prime.

Sequence A158708 is the sequence of prime sesquiprimes.

Inputs and outputs

  • N may be 0-indexed or 1-indexed, please indicate which of the two your solution uses.

  • Inputs and outputs must be in the decimal base.

  • N may be taken through STDIN, as a function argument, or anything similar.

  • The output may be printed to STDOUT, returned from a function, or anything similar.

Test cases

The following test cases are 0-indexed.

N        Output

0        2
1        5
2        9
4        21
8        45
15       93
16       101
23       149
42       305
100      853
1000     11693

Scoring

This is , so the shortest answer in bytes wins.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ I don't think the link to prime sesquiprimes adds anything other than a possibility for mistakes by people too lazy to read specs fully (like me) \$\endgroup\$ Sep 4, 2016 at 17:34
  • \$\begingroup\$ @JonathanAllan True. Would adding it as a comment be better to make it less appear like part of the challenge? \$\endgroup\$
    – Fatalize
    Sep 4, 2016 at 17:40
  • 1
    \$\begingroup\$ Including the link as a comment and/or prefixed by Related: would probably be clearer. \$\endgroup\$
    – Dennis
    Sep 4, 2016 at 18:11
  • \$\begingroup\$ This seems close to finding primes that are 1 mod 3. \$\endgroup\$
    – xnor
    Sep 5, 2016 at 10:18
5
\$\begingroup\$

Slay

This KoTH is based off of the computer game, Slay. Try it out, its way fun.

TLDR

  • You start off with a bunch of small territories: you try to merge them and capture as much land as possible.
  • Each territory has its own economy: each hex gives you 1 gold per turn.
  • Warriors can capture and protect territory, but cost money to maintain.
  • If you run out of money, all units on that territory die

Map

  • A hexagonal map is generated using Perlin noise.
  • Each hexagon is randomly assigned to a player. Players will start with a similar number of hexagons, as well as a similar number of territories (see below)
  • Hexagons that touch the edge of the map (or a hole in the middle), are on the beach
  • Each tile has a 1/5 chance of starting with a tree: Palm tree if on the beach, pine tree otherwise
  • Hexagons may contain a warrior, house, tower, grave, or palm/pine tree

Territory

  • A block of 2 or more hexagons with the same owner is considered a territory
  • All territories contain exactly 1 house.
    • If a territory ever doesn't have a house, it gets one in a random location, preferring: empty hexes, trees, graves, towers, and then warriors. (in that order)
  • A territory "death" occurs when it is reduced/split into a single hexagon.
    • Houses turn into a pine/palm (if on the beach) tree
    • Warriors die (turn into graves) at the start of their next turn
    • Towers disappear
  • If two territories grow so that they touch, they merge and the smaller territory's house disappears.

Finanaces

  • Each territory has its own reserve/income
  • Each territory starts with 10 gold in its reserve
  • Territories generate 1 income at the end of each turn for each tree-less hexagon
  • If you don't have enough money to pay for your units at the end of your turn, then all of your units in that territory will die (turn into graves) at the start of your next turn.
  • If a territory splits, then the larger of the two gets all of the reserve.
  • If a territory combines, their reserves combine

Defense

  • Certain objects give defense to its hexagon and all adjacent friendly hexagons:
    • Houses (1): cannot be built, but every territory has exactly one
    • Towers (2): can be built for 15 gold
    • Warriors (strength): see below

Map objects

Warriors

  • A warrior has a strength between 1 to 4 (inclusive)
  • A warrior costs 10*strength to build
  • A warrior costs 2*3^(strength-1) gold each turn. This means that a 4-str warrior costs you a whopping 54 gold per turn
  • A warrior can move a maximum of 4 hexes each turn. Moving through enemy lands is not allowed. Capturing enemy lands ends the warrior's turn.
  • If you move/build a warrior onto a friendly warrior, they combine, and their strength is summed.
    • Trying to make a warrior of strength > 4 doesn't work
    • If the friendly warrior hadn't moved yet, the new unit can still move
  • A warrior can capture an adjacent hexagon if its defense rating is lower than its strength

Trees

  • Trees prevent a hexagon from generating income
  • Trees grow at the end of each round:
    • Palm trees grow onto all unoccupied adjacent beach tiles
    • Any unoccupied tile that is adjacent to two pine trees grows another pine
  • Trees can be removed by moving a unit onto them
  • Graves turn into a pine/palm (if on beach) tree at the end of the round

Game flow

  • Between 2 to 6 players can play on a single map. (The size of the map depends on the number of players. You can expect about 50 hexagons per player)
  • Turn order is randomized, but is consistent within a single game
  • Once a player owns all hexagons, they win!
\$\endgroup\$
2
  • \$\begingroup\$ @zyabin101 still not ready yet. \$\endgroup\$ Aug 31, 2016 at 21:35
  • 1
    \$\begingroup\$ @zyabin101 + others finished my post! It took me a bit to ensure I got all corner cases correct. \$\endgroup\$ Sep 6, 2016 at 15:41
5
\$\begingroup\$

Flexagonal datastructures

Being programmers, watching us flex aren't very interesting. Today we change that! In this challenge you will lex and flex hexaflexagons.

About

For a video introduction, watch viharts video(s) on flexagons

A flexagon is a shape that you can flex to reveal faces other than the top and bottom one; we are making a hexahexaflexagon, which has 6 faces. See the image below on how to fold a hexahexaflexagon out of a strip of paper.

hexahexaflexagon construction

A shows both sides of the strip. The two white triangles are glued together. This is how you would flex it:

flexing the flexagon

Below is a diagram of possible states and their relationships:

Diagram v6

The colored circles represent the 6 triangles with the same number from the first image. Each of the circes have two colors- the bottom most represent the back face (what you would see if you where to flip your flexagon around), which you don't have to consider in this challenge.

The gray circles represent how you can flex your flexagon in any given state: there are 4 different ways to flex it, we call these Left, Right, Up and Down. You don't actually flex in these directions, the important bit is that some are opposite to each other.
If you are in the center you can use Left and Right to go to the other center ones. To get out of the center you use Up and Down. If you aren't in the center you cannot use Left or Right.

Left/Down = clockwise
Right/Up  = anti-clockwise

Challenge

Create a function or program that take as input what should be on the 18 front faces and the 18 back faces of a flexagon, a sequence of left, right, up and down flexes, and return the 8 visible faces after the flexes.

Example computation:

flex "hexaflexaperplexia" 
     "flexagationdevices" 
     [Right, Right, Left]

Divide a strip of paper into 19 triangles:
1/2\3/1\2/3\1/2\3/1\2/3\1/2\3/1\2/3   Front
4/4\5/5\6/6\4/4\5/5\6/6\4/4\5/5\6/6   Back

Write "hexaflexaperplexia" to the front of the paper strip:
1/2\3/1\2/3\1/2\3/1\2/3\1/2\3/1\2/3

hexaflexaperplexia
123123123123123123
h  a  e  p  p  x     Face 1, Initially the front face
 e  f  x  e  l  i    Face 2, Initially the back face
  x  l  a  r  e  a   Face 3, Initially hidden


Write "flexagationdevices" to the back of the paperstrip:
4/4\5/5\6/6\4/4\5/5\6/6\4/4\5/5\6/6

flexagationdevices
445566445566445566
fl    at    ev       Face 4, up from 3
  ex    io    ic     Face 5, up from 2
    ag    nd    es   Face 6, up from 1


Flex it [Right, Right, Left]
  The initial visible face is 1: "haeppx"
  flexing Right ..
  The current visible face is 2: "efxeli"
  flexing Right ..
  The current visible face is 3: "xlarea"
  flexing Left ..
  The current visible face is 2: "efxeli"
  flexed [Right, Right, Left]!

outputting "efxeli"

Example input and expected output:

> hexaflexaperplexia flexagationdevices RRL
= efxeli

> loremipsumdolorsit hexaflexamexicania LUU
= riuort

> abcdefghijklmnopqr stuvwxyz1234567890 UL
= I can't flex that way :(

> abcdefghijklmnopqr stuvwxyz1234567890 RRRRLLUDDUUUULDD
= uv1278

Rules

  • You may take input and return output in any reasonable way
  • If the input is impossible, you should indicate so in some way that is distinct from regular output
  • Standard loopholes apply
  • This is Codegolf. Shortest code in bytes win.
\$\endgroup\$
2
  • 3
    \$\begingroup\$ The diagram is at best confusing. The overlapping arrows are hard to read, and the fact that they're directional is just plain wrong. Then the example computation is very cryptic. To be useful the examples need to explain what each line of text means, and they should avoid duplicating letters. It would be good to make the first example show the output with zero flexes. I made my first hexaflexagon at least 25 years ago, and I carried one in my wallet for years to play with when bored, so if I find this spec lacking imagine how it must look to people who don't know anything about them! \$\endgroup\$ Sep 9, 2016 at 22:11
  • \$\begingroup\$ @PeterTaylor Is this remotely better? \$\endgroup\$
    – BlackCap
    Sep 9, 2016 at 23:09
5
\$\begingroup\$

Draw me a Brick Wall!

I'm drawing up a plan for my house extension - and I need a simple graphic for walls...

The Challenge

Your task is to create a program, which takes an input of the wall's dimensions and draws a brick wall, in the style of the one below.

[__][__][__][__]
_][__][__][__][_
[__][__][__][__]
_][__][__][__][_
[__][__][__][__]
_][__][__][__][_

Please notice that the rows alternate between beginning on a full brick ([__]) and a half brick (_]), to create a more realistic, stable wall.

The input will be two integers, separated by a single comma, such as 4,3 or 2,6. You can assume both integers are positive and larger than 0.

The first integer specifies the width (in bricks) and the second specifies the height (in rows of bricks).

Rules / Notes

  • This is , so the shortest code (in bytes) wins. However, don't feel like you have to beat everyone else to post your solution - I'd love to see your code!
  • Standard loopholes apply, no reading from external files.
  • You may optionally take the input with brackets/braces, for example (4,3) or [4,3] as long as you specify this in your answer.
  • You should take the input from STDIN and output on STDOUT - if your language does not have these, please use the nearest equivalent.

Test Cases

Input: 1,1

[__]

Input: 2,4

[__][__]
_][__][_
[__][__]
_][__][_

Input: 5,10

[__][__][__][__][__]
_][__][__][__][__][_
[__][__][__][__][__]
_][__][__][__][__][_
[__][__][__][__][__]
_][__][__][__][__][_
[__][__][__][__][__]
_][__][__][__][__][_
[__][__][__][__][__]
_][__][__][__][__][_

Example: Python 3, 65 bytes

This is somewhat golfed but still readable.

w,h=eval(input())
for i in range(h):print(('[__]','_][_')[i%2]*w)
\$\endgroup\$
7
  • \$\begingroup\$ very closely related or dupe \$\endgroup\$
    – Emigna
    Oct 28, 2016 at 13:11
  • 3
    \$\begingroup\$ this one is related too I think \$\endgroup\$
    – Dada
    Oct 28, 2016 at 13:12
  • \$\begingroup\$ Hi, welcome to PPCG! This seems like a great first challenge. There are a few related challenges regarding brick walls, like this one (inputs as different sized bricks) or this one (is it stable). But, I think this challenge is different enough. Instead of having different sized bricks as input, this simply asks for two inputs for an NxM wall, which is imho different enough from the first challenge. \$\endgroup\$ Oct 28, 2016 at 13:12
  • \$\begingroup\$ @Emigna I'd like to think they're different, as this one is a 'more static' string to print and doesn't require an algorithm to work out a stable wall first - however I understand that they are closely related. \$\endgroup\$
    – FlipTack
    Oct 28, 2016 at 13:13
  • \$\begingroup\$ @Dada Hmm, that one might be more related than the two related ones linked by me, and more towards a dupe (despite the different ASCII used for the bricks themselves). But we'll perhaps wait on some more feedback from other users. \$\endgroup\$ Oct 28, 2016 at 13:14
  • \$\begingroup\$ The one Dada linked is similar, but not quite a dupe. The brick structure is quite a bit more flexible in Luis' challenge, given that the input is total character width and height plus a horizontal offset, whereas here it's in number of bricks. \$\endgroup\$ Oct 28, 2016 at 13:21
  • \$\begingroup\$ I'd still call the previous brick printing one a dupe. The offsetting pattern is the same, and in most of the answers it would be easy to replace constants with inputs. \$\endgroup\$
    – xnor
    Oct 29, 2016 at 6:11
5
\$\begingroup\$

The smallest circles


Challenge

This is a variant of the smallest-circle problem, but instead of one circle, you get three. Given a list of coordinates, output three circles such that the following conditions are met:

  1. Each input coordinate must be located inside or on the perimeter of a circle.
  2. The sum of the radii of all three circles must be minimal.
  3. The coordinates and radii of all three circles must be non-negative integers.

You must place all three circles. You may place overlapping circles. A circle with a radius of zero that is directly on top of an input coordinate is considered to be covering that input coordinate.

Input

A list containing between 1 and 1000 pairs of integers, inclusive. Each pair of integers represents an xy-coordinate. Use whatever input format you want to use.

For example, the input...

1,1;1,2;2,2;3,3

... can be drawn like this:

enter image description here

Output

A list of three integer triples. Each triple contains an x coordinate, followed by a y coordinate, followed by a radius. The triples, and the integers within each triple, must be distinguishable from one another. Otherwise, the output format is not important.

Example:

1,1,1;2,2,1;3,3,2

Given this example output, circles would be drawn at (1,1), (2,2), and (3,3). The first two circles would have a radius of 1, and the third would have a radius of 2. The sum of the radii would be 4.

Test case explained

Given the input...

1,1;1,2;2,2;3,3

... you could output...

1,2,1;3,3,0;0,0,0

... or you could output...

1/2/1
3/3/0
0/0/0

The radii sums to 1, and since it is not possible to draw three circles whose radii sum to less than 1 that encompass or touch all four points, this is the correct answer.


(maybe too)

\$\endgroup\$
9
  • \$\begingroup\$ The text says that the list is colon-delimited, but the example is semicolon-delimited. It would help readability to mention that you can place three circles at some point before "The sum of the radii of all three circles is minimal". It's not clear whether the coordinates and radii of the circles must be integers, nor whether the radii must be non-zero. Finally, some test cases would be nice. \$\endgroup\$ Nov 7, 2014 at 18:50
  • \$\begingroup\$ If I didn't fully address any of the comments above please let me know. \$\endgroup\$
    – Rainbolt
    Nov 7, 2014 at 19:41
  • 1
    \$\begingroup\$ If the input can contain up to 1000 points it might help to have a large test case too. \$\endgroup\$
    – trichoplax
    Jan 20, 2016 at 22:30
  • \$\begingroup\$ For large numbers of input points, how will you assess whether the output is of minimal total radius? Is a proof required or is it sufficient that no other answer/person can find a counterexample? You could also have a judge program / reference implementation to define the correct total radius. \$\endgroup\$
    – trichoplax
    Jan 20, 2016 at 22:31
  • 1
    \$\begingroup\$ @trichoplax Hopefully I'll have a reference implementation before I post. If I decide that I am too lazy for that, then I will assume answers are correct until someone finds a counterexample. I will come up with a larger test case. \$\endgroup\$
    – Rainbolt
    Jan 20, 2016 at 22:37
  • \$\begingroup\$ Does the rigid I/O format really add anything interesting to the challenge? meta.codegolf.stackexchange.com/a/8077/8478 \$\endgroup\$ Jan 21, 2016 at 10:55
  • \$\begingroup\$ @MartinBüttner I completely relaxed the input format, and I somewhat relaxed the output format. Thanks for the feedback. \$\endgroup\$
    – Rainbolt
    Jan 21, 2016 at 14:12
  • \$\begingroup\$ @Rainbolt If I read the output section right, you're allowing any distinguishable delimiters for the output now? Then it might be clearer if one of the two example formats didn't use commas as the inner delimiter (maybe use spaces for the second example or so). \$\endgroup\$ Jan 21, 2016 at 14:15
  • 1
    \$\begingroup\$ The rewrite states two conditions which must be met, but there's a third one hidden down in the output section: that the coordinates and radii must be integers. That should be up in the first section. \$\endgroup\$ Jan 19, 2017 at 21:13
5
\$\begingroup\$

Make A Rotating Emoji Globe

Your task is to make a globe out of the following characters, with the line being cleared ever 1/3 of a second:

🌍🌎🌏

You must clear the line your emoji globe on it and print the next one every approximate 1/3 of a second.
Output may be to the terminal or elsewhere.
The program must also continue until interrupted on purpose.
Also, your code may not contain the emoji globes themselves, but it may contain Unicode escapes.


This is , so standard loopholes & rules apply.
May the best coder win...

\$\endgroup\$
14
  • 1
    \$\begingroup\$ Simple, fairly identical to this in that you simply display a cycle of things, Most answers from that will fairly easily work copied over. \$\endgroup\$
    – ATaco
    Feb 7, 2017 at 2:47
  • \$\begingroup\$ @ATaco How could I make it more challenging? \$\endgroup\$
    – ckjbgames
    Feb 7, 2017 at 2:50
  • \$\begingroup\$ @ATaco I think it's sufficiently distinct--it requires clearing the line (an option in the other challenge), display unicode characters, and only displaying one character at a time. \$\endgroup\$ Feb 7, 2017 at 3:24
  • \$\begingroup\$ @ConorO'Brien I still feel I could distinguish my challenge a bit more, though... \$\endgroup\$
    – ckjbgames
    Feb 7, 2017 at 17:48
  • \$\begingroup\$ Define clear the line? Does it have to clear the line, or does the whole terminal suffice? \$\endgroup\$
    – Riker
    Feb 7, 2017 at 18:13
  • \$\begingroup\$ @EasterlyIrk Clearing the screen can be done in any way, as long as the globe appears to rotate onscreen. \$\endgroup\$
    – ckjbgames
    Feb 7, 2017 at 21:40
  • \$\begingroup\$ It's even more similar to codegolf.stackexchange.com/questions/101289/loading-forever. Printing a single character that cycles \$\endgroup\$
    – 12Me21
    Feb 7, 2017 at 22:26
  • \$\begingroup\$ @12Me21 How can I make it different, then? \$\endgroup\$
    – ckjbgames
    Feb 7, 2017 at 22:35
  • \$\begingroup\$ Maybe you could require them to draw an actual rotating globe, given a map image. (It's a lot more complicated though) \$\endgroup\$
    – 12Me21
    Feb 7, 2017 at 22:37
  • \$\begingroup\$ @12Me21 I just had the idea to add a moon rotating around the earth. Help me think of how to implement it. \$\endgroup\$
    – ckjbgames
    Feb 7, 2017 at 22:59
  • \$\begingroup\$ You could make it use the different moon phase emoji to display the proper phases or something \$\endgroup\$
    – 12Me21
    Feb 7, 2017 at 23:05
  • \$\begingroup\$ @12Me21, an actual rotating globe is potentially a dupe of codegolf.stackexchange.com/q/24326/194 - certainly some of the answers could be copied across. \$\endgroup\$ Feb 9, 2017 at 9:02
  • \$\begingroup\$ Take as input the "spin speed" (ms delay), althought that's fairly trivial to handle. \$\endgroup\$ Feb 10, 2017 at 22:13
  • \$\begingroup\$ @Carcigenicate I will do that. \$\endgroup\$
    – ckjbgames
    Feb 12, 2017 at 21:54
5
\$\begingroup\$

Tron Game

Write a Tron bot!

The aim of the game is to make as many moves on a grid as possible without moving onto a space that has already been occupied in the current game. If your bot is unable to make such a move, it loses the round. The board does not wrap so bots can not go off the side of the arena.

Game IO:

Your bot will be written in python and will create a class that inherits from BotSkeleton. An example test bot is shown below.

from bot_skeleton import BotSkeleton
from typing_hints import PositionDict, Position
from board import Board
from typing import List

import random


class Test(BotSkeleton):
    def make_move(self, board: Board, positions: PositionDict) -> Position:
        self.board = board
        self.position = positions[self.bot_id]
        valid_moves = self.get_valid_moves()
        try:
            return random.choice(valid_moves)
        except IndexError:
            return None

    def get_valid_moves(self) -> List[Position]:
        moves = filter(self.board.position_valid, ((self.position[0]+1, self.position[1]),
                                                   (self.position[0]-1, self.position[1]),
                                                   (self.position[0], self.position[1]+1),
                                                   (self.position[0], self.position[1]-1)))
        return list(moves)

(Type hints are not required but illustrated here to help understanding)

  • position is a 2-long tuple containing 2 integers.
  • positions is a Dict[bot_id, position]
  • board can be indexed with a position.
    • get_random_empty_pos() -> position - returns a empty position at random in the board
    • position_valid(position) -> bool - returns if this move is valid (but not next to the position given)
    • copy() -> List[List[int] - returns a 2d list that can be modifiable of the current board state
    • EMPTY - the id for an empty space
  • The value you return must be a position, and must also have a distance of 1 from this, not including diagonals.

Built in attributes for BotSkeleton:

  • log - contains a file object that you may write to
  • no_bots - the number of bots the game began with
  • bot_id - you're bot's id number.

Methods in Board:

  • get_random_empty_pos() -> Position - Returns a position at random that is empty
  • position_valid(pos: Position) -> bool - returns if a position is inside the board and is currently empty
  • copy() -> Board - return a copy of the board that is writable

Tournament structure

  • Every bot will get pitted against every other bot in a giant arena
    • That is to say every single bot will be in every battle
    • The size of the arena will be (30, 30). This may be increased depending on number of bots entered.

General rules that I can't find better places for

  • Your bot may NOT use any file storage except for write-only access to the log file provided
  • Your bot must be written in Python 3. Sorry java people
  • You may enter as many bots as you want
  • Your bot must not attempt to subvert the game state

I reserve the right to disqualify any bot from the competition

(but shall only do so after telling you I will do so and you not making any changes required)

You may download the controller here

Results:

  • Results here

Sandbox notes:

  • Should there be a minimum starting distance between players?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ What happens if two bots go on the same position at the same time? \$\endgroup\$
    – Katenkyo
    Mar 23, 2016 at 11:10
  • 2
    \$\begingroup\$ Is the goal really to survive as many moves as possible, and not to survive longer than the other guy? \$\endgroup\$
    – feersum
    Dec 7, 2016 at 14:03
  • \$\begingroup\$ probably change "sorry" to "sorry not sorry" \$\endgroup\$ Feb 11, 2017 at 12:20
5
\$\begingroup\$

Part I: Triangular Manhattan Distance

Part II: Triangular Chebyshev Distance

The Chebyshev distance on a regular grid is the number of orthogonal or diagonal steps one needs to take to reach one cell from another. That is, we can move either through the edge of a cell, or through a corner, to a neighbouring cell.

We can define a similar distance on other grids, for example the triangular grid. We can address the individual cells in the grid with the following indexing scheme, where each cell contains an x,y pair:

    ____________________________________...
   /\      /\      /\      /\      /\
  /  \ 1,0/  \ 3,0/  \ 5,0/  \ 7,0/  \
 / 0,0\  / 2,0\  / 4,0\  / 6,0\  / 8,0\
/______\/______\/______\/______\/______\...
\      /\      /\      /\      /\      /
 \ 0,1/  \ 2,1/  \ 4,1/  \ 6,1/  \ 8,1/
  \  / 1,1\  / 3,1\  / 5,1\  / 7,1\  /
   \/______\/______\/______\/______\/___...
   /\      /\      /\      /\      /\
  /  \ 1,2/  \ 3,2/  \ 5,2/  \ 7,2/  \
 / 0,2\  / 2,2\  / 4,2\  / 6,2\  / 8,2\  
/______\/______\/______\/______\/______\...
\      /\      /\      /\      /\      /
 \ 0,3/  \ 2,3/  \ 4,3/  \ 6,3/  \ 8,3/
  \  / 1,3\  / 3,3\  / 5,3\  / 7,3\  /
   \/______\/______\/______\/______\/___...
   /\      /\      /\      /\      /\
  .  .    .  .    .  .    .  .    .  .
 .    .  .    .  .    .  .    .  .    .

Now the Chebyshev distance on this grid is again the minimal number of steps across edges or corners to get from one cell to another. So you can move from 3,1 to any of its 12 neighbours:

2,1 4,1 3,2 (through edges)

3,0 1,2 5,2 (the opposite triangle through corners)

2,0 4,0 1,1
5,1 2,2 4,2 (the other triangles through corners)

For instance, the distance from 2,1 to 7,2 is 3. The shortest path is generally not unique, but one way to make the distance in 3 steps is:

2,1 --> 4,1 --> 5,1 --> 7,2

The Challenge

Given two coordinate pairs x1,y1 and x2,y2 from the above addressing scheme, return the Chebyshev distance between them.

You may assume that all four inputs are non-negative integers, each less than 128. You may take them in any order and arbitrarily grouped (four separate arguments, a list of four integers, two pairs of integers, a 2x2 matrix, ...).

You may write a program or a function and use any of the standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

Test Cases

Each test case is given as x1,y1 x2,y2 => result.

1,2 1,2 => 0
0,1 1,1 => 1
1,0 1,1 => 1
2,1 7,2 => 3

Will add more test cases when I have a reference implementation.

\$\endgroup\$
10
  • \$\begingroup\$ @trichoplax Yes, thank you. With the slow response to the Manhattan variant, I do wonder whether this one will be a bit too tricky, but we'll see. :) \$\endgroup\$ Apr 4, 2017 at 21:28
  • \$\begingroup\$ "I do wonder whether this one will be a bit too tricky, but we'll see. :)" I've found a solution for this one, but not for the other one yet. ;) \$\endgroup\$ Apr 5, 2017 at 12:01
  • \$\begingroup\$ @KevinCruijssen Oh, would you mind sharing it? :) \$\endgroup\$ Apr 5, 2017 at 12:06
  • \$\begingroup\$ I always make my answers in Java 7 btw, so I'll still be beaten by golfing answers. But this is what I came up with (I've also added an explanation of how I came up with the solution in the TIO footer): Try it here. \$\endgroup\$ Apr 5, 2017 at 12:23
  • \$\begingroup\$ Hmm, I just took another look at your part 1 challenge and realized my solution above for part 2 is incorrect.. :( Based on your current test cases I falsely assumed x1,y1 is always smaller than x2,y2. So my code fails for a test case like 4,1 1,3. Back to the drawing board.. Also, as to why I think this challenge is easier than part 1: In part 1 you had to determine whether the triangle was facing upwards (available: left; right; below) or facing downwards (available: left; right; above). With this challenge all 12 surrounding triangles - regardless of orientation - are accessible. \$\endgroup\$ Apr 7, 2017 at 8:22
  • \$\begingroup\$ @KevinCruijssen but the exact coordinates/orientations of those 12 neighbours also change, right? \$\endgroup\$ Apr 7, 2017 at 8:24
  • \$\begingroup\$ Yeah, was about to edit my comment again when I realized that.. If you have more test cases I'll take another look at this part 2. I'll start with part 1 for now. (PS: Have a nice weekend - apparently I can use it.. >.>) \$\endgroup\$ Apr 7, 2017 at 8:25
  • \$\begingroup\$ Me again, more than one year later. I've currently set a bounty for your Part 1 challenge to give it more attention, which you may or may not have noticed based on the new answers given. If you have time, could you add more test cases for this one? \$\endgroup\$ Jun 29, 2018 at 8:40
  • \$\begingroup\$ @KevinCruijssen I'm not sure how soon I'll get around to that, because I'd want to write a reference implementation for that. If you want it post it soon, feel free to add them yourself (and optionally post the challenge yourself if you like). \$\endgroup\$ Jun 29, 2018 at 16:26
  • \$\begingroup\$ Oh no, I'll patiently wait. I'm going on vacation soon anyway, so I won't have time to answer during that time. I just made that comment above as a reminder so it can hopefully be posted in the not to distant future. :) \$\endgroup\$ Jun 29, 2018 at 16:42
5
\$\begingroup\$

Table parser, code golf

Input

|===========|=============|==============|
|Left align |  Right align| Center align |
|===========|=============|==============|
|This       |         This|     This     |
|-----------|-------------|--------------|
|                column                  |
|-----------|-------------|--------------|
|will       |                            |
|-----------|          will be           |
|be         |                            |
|-----------|-------------|--------------|
|left       |        right|    center    |
|-----------|-------------|--------------|
|aligned    |      aligned|   aligned    |
|-----------|-------------|--------------|
|and can be |    vertical-|              |
|multilined | align middle|  as default but a bit long line |
|with <br>  |             |              |
|-----------|-------------|--------------|

Output should be valid HTML. And I am thinking of following requirement specs.

  • alignments (left, right, middle)
  • border thickness (normal -, |, bold, =,||)
  • with table headers or without
  • rowspans, colspans
  • multiline & vertical-align is always middle

What do you think?

\$\endgroup\$
18
  • \$\begingroup\$ I guess figuring out cells and row/colspans is enough work, so handling bold and italic could be omitted, maybe. \$\endgroup\$
    – Joey
    May 9, 2011 at 12:15
  • \$\begingroup\$ Also, should this be a code golf or a challenge? \$\endgroup\$
    – Joey
    May 9, 2011 at 12:18
  • \$\begingroup\$ code-golf @joey. and I am gonna leave bold and italic out. I was not sure it was hard enough :D \$\endgroup\$
    – YOU
    May 9, 2011 at 13:22
  • \$\begingroup\$ Can cells contain more than a line of text? I.e. do long contents wrap or do they extend the cell? \$\endgroup\$
    – Joey
    May 9, 2011 at 13:35
  • \$\begingroup\$ @Joey, yeah, a bit more complicated now, multiline involve vertical-align, so I set that as middle as default, what do you think? \$\endgroup\$
    – YOU
    May 9, 2011 at 13:49
  • \$\begingroup\$ Yikes :D. Well, I was just pondering a few ways of figuring out the layout and determining rowspans would be much easier if all rows are the same height ;). Should be ok, but bear in mind that it makes judging correct vertical align difficult. Given the current last row the valigns could be either one of mmm, ttm, tmm, btm, bmm. No show-stopper but something to keep in mind for test cases and scripts. \$\endgroup\$
    – Joey
    May 9, 2011 at 13:53
  • \$\begingroup\$ @Joey, yeah, to judge top, middle, and button, we need a blank row between every table row, just like a space in right, right, and center, so I guess I need to make vertical-align as middle as default. \$\endgroup\$
    – YOU
    May 9, 2011 at 14:06
  • \$\begingroup\$ So vertical align will not vary and always be middle, if I understand you correctly? \$\endgroup\$
    – Joey
    May 9, 2011 at 14:07
  • \$\begingroup\$ @Joey, yeah .. and for multiline items you just need to put <br> between and can be, multilined, and too, if those are supposed to be same line, input will be |and can be multilined too | ....... | ..... | . \$\endgroup\$
    – YOU
    May 9, 2011 at 14:10
  • \$\begingroup\$ I think your multi-column cells are ambiguous: the last row shows that text can extend beyond the ASCII art column width, so we cannot use the horizontal alignment of |s to judge colspans. Therefore, the 4th and 5th rows could span 1 and 2 columns (as visually, but unreliably indicated) or 2 and 1 columns. Example \$\endgroup\$
    – Adám
    Jun 5, 2017 at 7:20
  • \$\begingroup\$ @Adám, thanks for taking a look. Yeah, might be that's the reason there is not much interest on this. \$\endgroup\$
    – YOU
    Jun 5, 2017 at 10:33
  • \$\begingroup\$ @YOU Also, this is a very complex challenge, pretty much implementing a large subset of the Wiki markup for tables. Maybe you should narrow the scope by removing all formatting; alignment, borders, headers (these are also ambiguous), and just focusing on converting the -| style table into HTML. Maybe even remove the row and column spans? \$\endgroup\$
    – Adám
    Jun 5, 2017 at 10:42
  • \$\begingroup\$ I don't remember why I put all those things in, may be similar challenge was there already, for simple tables, but I don't know. I need to look up more. \$\endgroup\$
    – YOU
    Jun 5, 2017 at 14:11
  • \$\begingroup\$ @Adám, removed rowspan, colspan, multiline and vertical align. Not sure it could be duplicate entry now. \$\endgroup\$
    – YOU
    Jun 5, 2017 at 14:17
  • 1
    \$\begingroup\$ @programmer5000, became duped, because of you guys suggestion. I rollbacked. \$\endgroup\$
    – YOU
    Jun 9, 2017 at 15:37
5
\$\begingroup\$

Line up for golf!

\$\endgroup\$
7
  • 4
    \$\begingroup\$ The comments in the test cases reduce their usefulness as test cases. Moreover, the first one contradicts the "full specification", and the second one adds to it. The spec should contain everything needed to justify the correctness of the test cases. You also need to specify desired behaviour when there is no solution, and to include a test case for that scenario. \$\endgroup\$ Mar 7, 2014 at 14:04
  • 2
    \$\begingroup\$ How are conditionals to be interpreted when mixed in a single full condition? Alice is 1st or 1st to last and in front Bob or 1 space behind Bob \$\endgroup\$ Mar 7, 2014 at 14:12
  • \$\begingroup\$ This seems like a good challenge, but Peter Taylor and Jan Dvorak's concerns should be addressed. \$\endgroup\$
    – user10766
    Mar 8, 2014 at 18:42
  • \$\begingroup\$ @PeterTaylor Edited, but how does the first one contradict? \$\endgroup\$
    – Doorknob
    Mar 10, 2014 at 2:32
  • \$\begingroup\$ @JanDvorak Edited to clarify. \$\endgroup\$
    – Doorknob
    Mar 10, 2014 at 2:32
  • \$\begingroup\$ Another concern: What if there is no solution? What if there is more than one? \$\endgroup\$ Mar 10, 2014 at 6:04
  • \$\begingroup\$ Please delete this now that it is posted. \$\endgroup\$
    – user58826
    Aug 1, 2017 at 16:07
5
\$\begingroup\$

This is a proposal adopted by programmer5000. Any feedback before I post it?

Seven-segment usage

I have an old digital clock and I am concerned the individual segments of the digits might run out of magical binary energy or whatever powers them. To know which of the segments on the clock will fail first I want to know what is the percentage of time each segment is lit.

The challenge is to compute the percentage of time any segment on a digital clock is lit.

Input

The input will be in the form X.L, where:

  • X is a number from 1 to 4. 1 is the left-most number of the clock, 4 the right-most
  • L is a letter from a to g or a number from 1 to 7
  • the separator can be changed to fit your needs (no separator is an option)

Disposition of segments, image source: Wikipedia Disposition of segments plus numbers image source: Wikipedia]

Output

The output, is a percentage, given with at least 2 figures after the decimal point. It can be rounded or truncated to the closest value if you want to keep a limited number of digits.

Valid outputs: 0.74, 32.47, 7.5 (for 7.50)

Additional stuff

The clock is in 24 hours format (so 22:45 is a valid time).

We consider the clock started working at 0:00 so the challenge is effectively working out what percentage of a complete day a single segment is lit.

The first number is not lit when it is 0.

Lit segments for each number:

  • 1: b c
  • 2: a b d e g
  • 3: a b c d g
  • 4: b c f g
  • 5: a c d f g
  • 6: a c d e f g
  • 7: a b c
  • 8: a b c d e f g
  • 9: a b c d f g
  • 0: a b c d e f

Examples

  • 1.b => 58.33
  • 3.e => 33.33
  • 2.d => 70.83
  • 4.d => 70.00

Full list of outputs here

Winner

Code golf, most probably, though I am not sure yet this is the best format (I am not too interested in the input parsing and the output formatting, they might be an obstacle to golfing?)

\$\endgroup\$
5
  • 6
    \$\begingroup\$ AIUI there are 28 valid inputs, so you could provide a full list of test cases as a pastebin. I would remove "No hard coding of results": if hard-coding the 28 cases is shorter than the calculation, then IMO that's a flaw which makes the question not worth bothering with at all rather than something which can be worked around; and the issue of whether or not an answer "hard-codes the results" is likely to be grey rather than black or white. \$\endgroup\$ Mar 3, 2016 at 10:54
  • \$\begingroup\$ List of results added, I'll need to double check them. Hard coding removed, yes I don't see how "cheating" would be an issue. Any hard-coding would have to be quite constructive to be efficient. \$\endgroup\$
    – drolex
    Mar 3, 2016 at 11:29
  • \$\begingroup\$ I am removing limitations on the output as well, I don't think it brings anything to the challenge. I have started to golf a solution in python, I think there are a few interesting possibilities to optimise the use of strings describing segments used for each digit. \$\endgroup\$
    – drolex
    Mar 3, 2016 at 15:56
  • \$\begingroup\$ Can I post this abandoned proposal? \$\endgroup\$
    – user58826
    Jun 9, 2017 at 13:00
  • \$\begingroup\$ @programmer5000 certainly, just try to make it better :) \$\endgroup\$
    – drolex
    Jun 9, 2017 at 13:05
5
\$\begingroup\$

A Game of Knights

In this King of the Hill, you control 10 Knights. You need to surround your enemy before they surround you.

Each Knight has 3 possible actions:

  • Dash: Move 3 squares in a cardinal direction. If there is a knight in your path, move as far as you can.
  • Leap: Move 2 squares in a cardinal direction. If there is a knight on your destination square, don't move at all.
  • Push: Move 1 square in a cardinal direction. If there is a knight on your destination square, and no knight or wall behind him, you both move 1 square.

Each round will have a Planning Phase and then an Action Phase.

Planning:

During the planning phase, players will alternate creating a plan until both players have created 10 plans.

  • A plan consists of either an action type or a cardinal direction (not both).
  • A plan also includes the knight that will perform the action
  • All plans are revealed to both players

Action:

  • Actions occur in the same order that they were planned.
  • If you planned an action type, you will be able to choose the direction. If you planned a cardinal direction, you will be able to chose the action type you want.

After the action phase, if any knights are on the same location they started at (at the start of the round) are captured and removed from the game. You win by capturing all other knights.

Other info:

  • Cardinal means North, East, South, or West
  • The board is a 10x10 board. Your knights start as a line at the bottom of the board.
  • Walls block movement and cannot be pushed.
  • You don't have to plan an action for every knight, and a knight can take multiple actions.
  • There are a maximum of 1000 rounds. After those 1000 rounds, the winner is the player with the most knights. (A tie is allowed).
  • The starting player for a game is randomized, and that player starts every round.

You have won the game when you opponent cannot make any mobility actions.

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Man, now I want to play this in person. \$\endgroup\$
    – DLosc
    Feb 18, 2017 at 21:17
  • 1
    \$\begingroup\$ Isn't it possible to form your knights into a solid 2×5 rectangle (thus immune to pushing), away from the starting squares, before the enemy can move and push it? That would guarantee you couldn't lose. Also you should clarify whether you can plan two actions for the same knight, and if you can, whether it gets to take both or only one. \$\endgroup\$
    – user62131
    Feb 18, 2017 at 23:14
  • \$\begingroup\$ @ais523 movement is not simultaneous. You start as a 1x10 line. A knight could take 10 moves on a round \$\endgroup\$ Feb 18, 2017 at 23:52
  • \$\begingroup\$ To be clear, as long as you have 10 knights, you need to move each of them every round or lose the ones you didn't move, assuming you don't push. Correct? \$\endgroup\$
    – isaacg
    Jun 23, 2017 at 21:30
  • \$\begingroup\$ Does the same player go first in each round, or does that alternate? \$\endgroup\$ Jun 23, 2017 at 21:31
  • \$\begingroup\$ @isaacg correct. \$\endgroup\$ Jun 23, 2017 at 23:51
  • \$\begingroup\$ @PeterTaylor I've debated about this, and I think the same player will go first in each round. The player that goes first will be randomized each game, but it will be consistent round to round. Otherwise, you end up with a player being able to move twice in a row. \$\endgroup\$ Jun 23, 2017 at 23:52
5
\$\begingroup\$

The Chroma Key to Success

\$\endgroup\$
5
  • \$\begingroup\$ So essentially, for every pixel in the second image, if it's #00FF00, replace it with the corresponding pixel in the first image; otherwise, don't modify that pixel? \$\endgroup\$
    – hyper-neutrino Mod
    Jul 16, 2017 at 17:33
  • \$\begingroup\$ @HyperNeutrino Yes. \$\endgroup\$
    – ckjbgames
    Jul 16, 2017 at 17:34
  • \$\begingroup\$ I don't know image formats very well, but are we guaranteed that the image will be in 3-byte-RGB format? As in, is there transparency? \$\endgroup\$
    – hyper-neutrino Mod
    Jul 16, 2017 at 17:36
  • \$\begingroup\$ @HyperNeutrino Assume the image is full opacity. \$\endgroup\$
    – ckjbgames
    Jul 16, 2017 at 17:39
  • 3
    \$\begingroup\$ Please delete this, now that it is posted. \$\endgroup\$
    – user58826
    Jul 17, 2017 at 13:05
5
\$\begingroup\$

PPCG VS CR KotH

I am working as fast as I can to get this ready. Please be patient. I have a real job and will attempt to work on this on vacation to the northern states using mobile. I give no promises.

I challenged CR to a KotH challenge. So here is the specs.

Two sides in a arena. 1000x1000. Resources scattered about. A giant area in the center filled with resources. You must build a base and defend your ancient.

You have a few kinds of buildings:

  1. Wall: a simple wall that must be broken before walking through. It has 1/2/4/8 health (upgrades). It can be changed into a gate.
  2. Gate: a gate that lets the side that made it walk through. Health: 1/2/2/4
  3. Turret: Deals 1/1/2/4 damage to the lowest health enemy within a 1/2/4/4 block radius and has 1/1/4/8 health.
  4. Resource drop: a place that you can drop resources. Has 2/2/4/6 health.
  5. Tower of vision. Gives 10 sight radius with health of five. Costs two resources to build.

Upgrades are 1/2/3/4. The first upgrade is just buying the building.

Gates when transformed stay the same level as the wall they started as, can still be upgraded.

Every bot starts with five health, one damage, and three sight radius. They can upgrade each by four for the cost of 1/2/2/2.

All upgrades take one bot. It takes 1/2/2/3 turns to upgrade an item. The bot must upgrade the item all at once or it must restart and repay the cost. Building a item takes one resource.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ so, how does turn order work? is there a way to attack excluding turrets? \$\endgroup\$ Jul 29, 2017 at 2:54
  • 1
    \$\begingroup\$ Will the bots have knowledge of the entire 1000x1000 area or what is the line of sight? \$\endgroup\$ Jul 29, 2017 at 8:48
  • 2
    \$\begingroup\$ I'd recommend not making the challenge too complicated/complex. I'm not sure that skill points are necessary. \$\endgroup\$ Jul 29, 2017 at 8:49
  • \$\begingroup\$ How does it work with the Q&A site format? Or is it an off-site challenge? \$\endgroup\$
    – ugoren
    Jul 29, 2017 at 19:10
  • 2
    \$\begingroup\$ @ugoren King of the Hill challenges like this one are very much on-topic on PPCG, and in fact we even have a tag for challenges like these: koth. \$\endgroup\$
    – user41805
    Jul 29, 2017 at 19:53
  • \$\begingroup\$ @Cowsquack, You're right, it's OK. A bit strange for my taste, since the war happens off-site, but never mind. \$\endgroup\$
    – ugoren
    Jul 29, 2017 at 20:16
  • \$\begingroup\$ @SimonForsberg good point \$\endgroup\$ Jul 29, 2017 at 23:26
  • \$\begingroup\$ This will not be a challenge between PPCG and CR. Challenge declined \$\endgroup\$ Aug 4, 2017 at 18:50
  • \$\begingroup\$ Since this idea is dead now, consider developing it further as a normal KoTH or deleting and editing it down to a stub. \$\endgroup\$
    – hyper-neutrino Mod
    Oct 30, 2017 at 2:24
5
\$\begingroup\$

Swap the frogs!

Given 2 integers N >= 1, representing left-side frogs, and M >= 1, representing right-side frogs, return all the steps required so that the frogs change sides with the minimum number of steps. The frogs start with one empty spot between the two sides. A frog can jump to the empty space if there is at most 1 frog from either side between the frog and the empty space. A frog can jump either forwards or backwards.


An example, with N = 3 and M = 2:

LLL.RR
LL.LRR
LLRL.R
LLRLR.
LLR.RL
L.RLRL
.LRLRL
RL.LRL
RLRL.L
RLR.LL
R.RLLL
RR.LLL

The corresponding output would be (1-indexed):

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

Each one is the index of the column that the frog that must jump is before jumping.

Rules

  • You may perform I/O in any reasonable format.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Maybe start with a small example, because now the main output specification is tucked under a huge block of text, which will be TL;DR for many people. \$\endgroup\$
    – Sanchises
    Aug 8, 2017 at 10:52
  • \$\begingroup\$ 1. The questions in the section headed "Sandbox" make no sense because their context has been deleted. Are they still relevant? 2. "What you have to print" should presumably be "What you have to output". 3. "A frog can jump either forwards or backwards" so there should be at least one test case where all optimal paths only involve jumping forwards and at least one where all optimal paths involve jumping backwards. \$\endgroup\$ Aug 8, 2017 at 14:55
  • \$\begingroup\$ Maybe a testcase where no steps are necessary, too. \$\endgroup\$
    – Sanchises
    Aug 8, 2017 at 15:13
  • \$\begingroup\$ @PeterTaylor Please, don't be too meta :-) :p \$\endgroup\$ Aug 8, 2017 at 16:46
5
\$\begingroup\$

Learning your strengths and weaknesses

  • Fighters have a unique, random Strength (between 1 and 1000)
  • When two fighters fight, the stronger one wins.
  • Your goal is to accurately guess your fighter's Strength.

Gameplay:

  1. We start by randomly ordering all 1000 fighters.

  2. Each fighter fights his neighbor (The even fighters fight the fighter 1 above)

  3. The fighter is given two pieces of information: His opponent's last guess, and who won the fight. The fighter then guesses his strength.

  4. We perform a stable sort based on the guessed strength, and go back to step 2

  5. After 10 guesses, the fighter's score is (RealStrength - GuessedStrength)^2. Lower is better.

Other details:

  • There will be duplicate bots in a single game.

  • A stable sort is a sort that (effectively) uses the past ordering as a tiebreaker. In essence, if players [A,B,C,D] guessed [10,5,10,5] then the new order would be [B,D,A,C]

  • Bots aren't allowed to share information between each other, but are allowed to persist information within a single game.

  • I will run a large number of games. The exact number will be dependent on how much variation there is. Your final score will be all of your scores summed up.

\$\endgroup\$
7
  • \$\begingroup\$ I like this a lot. Sounds like a very interesting challenge. A couple thoughts though. 1) What's the point of squaring your score? If there was some kind of polynomial scoring I could see that, but it doesn't really have any purpose at the moment. 2) personally, I think it should be more than 10 rounds. \$\endgroup\$
    – DJMcMayhem
    Jan 29, 2018 at 17:17
  • \$\begingroup\$ @DJMcMayhem I think 10 rounds is enough for good bots to get a reasonable score without providing so much information that many will get a perfect score. I do think the process should be repeated though. Maybe a terminology change: 10 guesses per round, each round scored as indicated, average of X rounds is the final score. Also, the squaring is a way of getting absolute value (result is always positive even if guess > real) and if averaging multiple results it weights wildly incorrect guesses to increase the score by a lot. \$\endgroup\$ Jan 29, 2018 at 17:45
  • \$\begingroup\$ @DJMcMayhem Squaring means that being 50 off is far worse than being 25 off. I picked 10 rounds because log2(1000) is 9.97. This requires bots to be efficient with their time. If I make it much higher, then its going to be hard for me to differentiate the top bots. \$\endgroup\$ Jan 29, 2018 at 18:24
  • \$\begingroup\$ @KamilDrakari Updated, thanks. \$\endgroup\$ Jan 29, 2018 at 18:30
  • \$\begingroup\$ In step 3, each fighter is provided "His opponent's last guess". What will be provided during the first round? \$\endgroup\$ Jan 29, 2018 at 19:21
  • \$\begingroup\$ That'll be part of the API spec. Something like -1. \$\endgroup\$ Jan 29, 2018 at 19:31
  • \$\begingroup\$ This will probably be my last suggestion (for now): a link and/or description for "stable sort" will probably be helpful; I certainly needed to look it up, and is quite useful for informing strategies, as well as answering a question I otherwise had about handling ties. \$\endgroup\$ Jan 29, 2018 at 22:00
5
\$\begingroup\$

Can the robotic arm reach itself?

( ͡° ͜ʖ ͡°) title is kinda sketch at the moment

A robotic arm is made up of a set of line segments, each with a positive integer length. Each joint on the robot has two possible positions: straight or 90 degrees clockwise.

Here is a robotic arm with 4 line segments of sizes 4, 2, 3, 2

+---+-+--+-+

Here is the same robot arm with one joint bent

+---+-+
      |
      |
      +
      |
      +

(vertical scale is kinda messed up)

Right now, the robotic arm isn't reaching itself. By bending all of the segments, however, the arm can reach itself.

+X--+
 |  |
 +--+

So, a robotic arm of size [4,2,3,2] can reach itself.

Here is a robotic arm of size [3,1,4,3] that can't reach itself:

+--++---+--+

+
|
|+--+
+---+

Whereas a robotic arm of size [1,1,2,2,3] can reach itself.

++-+-+--+

+
X++
| |
+-+

A robotic arm of size [2,2,3,5,3,4] can also reach itself

a-b-c--d----e--f---g

e--f
|  |
|  |
|a-b
|  g
d--c

Challenge

Given list of numbers, such as [1,2,3,4,5], output a truthy value of the robotic arm can reach itself and a falsey value if it cannot.

\$\endgroup\$
9
  • \$\begingroup\$ s/touch/intersect/g? \$\endgroup\$ Feb 17, 2016 at 20:27
  • \$\begingroup\$ We've had some related challenges I think. At least codegolf.stackexchange.com/q/45059/8478 \$\endgroup\$ Feb 17, 2016 at 21:01
  • \$\begingroup\$ codegolf.stackexchange.com/q/49713/8478 \$\endgroup\$ Feb 17, 2016 at 21:03
  • 1
    \$\begingroup\$ The scenario reminds me of stretchy snakes kissing. Except, these snakes are unusually rigid ... you know what, never mind. \$\endgroup\$
    – xnor
    Feb 17, 2016 at 21:45
  • \$\begingroup\$ The first few examples would be clearer if either you also used letters to distinguish the joints or if you at least marked one end of the chain in both the straight and the folded representation. \$\endgroup\$ Feb 18, 2016 at 7:55
  • \$\begingroup\$ You could probably also use more than one example where self-intersection only happens when not all joints are bent like the [1,1,2,2,3] example. If that's possible it would be good to have one where you need to bend joints on both sides of a straight joint to make the self-intersection happen, but I don't know if that can happen. \$\endgroup\$ Feb 18, 2016 at 12:23
  • \$\begingroup\$ @El'endiaStarman s/touch/reach/g \$\endgroup\$
    – mbomb007
    Apr 7, 2016 at 15:13
  • \$\begingroup\$ Is 4,2,3,3 truthy or falsy? \$\endgroup\$
    – Zgarb
    Feb 7, 2018 at 8:12
  • 2
    \$\begingroup\$ Can the robotic arm go through itself? The [2,2,3,5,3,4] case seems to indicate so. \$\endgroup\$
    – stanri
    Feb 7, 2018 at 10:50
5
\$\begingroup\$

Efficient Tab Completion

Many tools that programmers use on a daily basis, like bash and Emacs, have tab completion.

  • Pressing Tab in certain situations will attempt to complete the text at the cursor, from a set of possibilities. The term is "completed" by filling in the remaining text.
  • For the aforementioned, if there are multiple candidates for completion, you will instead be shown a list of the candidates.
  • If there are multiple possibilities but they all start with the same substring/prefix, the rest of that substring will be filled in.

For example, to reach pydoc3, you only have to type

pyd<TAB>3

where Tab is shown as <TAB>. The tab key will insert oc, since all options starting with pyd also start with pydoc (in the set below).

a shot of bash tab completion options


The Challenge

Given a collection of strings called S and a target string called T, figure out the minimum number of keystrokes to reach T, assuming we're using tab completion and S is the set of possibilities.

  • Tab completion here is modeled after bash and Emacs, so it is case-sensitive.
  • The keystrokes/moves don't matter, only how many. A "keystroke" is:
    • Some character in the string
    • Tab
    • If S is [abc, ab] and T is ab, then either a<TAB> or ab will get there. Tab counts as one keystroke, so the method doesn't matter.
  • You may assume terms will only contain alphanumeric characters, underscore, and hyphen ([A-Za-z0-9]_-), for the purpose of this challenge.
  • You may assume no strings are empty.
  • You may assume S contains T (unsure about this one)
  • The input can be taken in whatever format is appropriate for your platform or language (array of strings, string with separators etc.) S and T are considered separate inputs.
    • I/O format is flexible and defaults apply (full program, function etc.)

This is , so shortest answer in bytes wins.


Test Cases

Set                                                 Target         Output
--------------------------------------------------  -------------  ------
[ab, abc]                                           ab             2
[lisp-mode, list-abbrevs, list-packages]            list-packages  5
[heck, hell, help_me, hello, goodbye, hello_world]  hello          5

Feedback

  • Is anything vague or underspecified?
  • Is something too specific or cumbersome?
  • Is this too similar to an existing question?
  • Should we assume S will always contain T, or require a special case?
  • Should something be changed about case-sensitivity? Assume everything is lowercase?
  • Any tags I should use?
\$\endgroup\$
6
  • \$\begingroup\$ Hmm. wouldn't it be l<TAB>t-p<TAB> for #2? Also how to get hello in 4 keystrokes? \$\endgroup\$
    – ASCII-only
    May 2, 2018 at 0:48
  • \$\begingroup\$ You're right about list-packages, I'll fix it. And it looks like hello should be 5 keystrokes at hello. Good eye. \$\endgroup\$
    – snail_
    May 2, 2018 at 0:55
  • \$\begingroup\$ You can get symbols for keys using <kbd> (<kbd>tab</kbd>) \$\endgroup\$
    – 12Me21
    May 2, 2018 at 1:41
  • \$\begingroup\$ I like this challenge! A couple of questions: is it illegal to start typing with a TAB (could be useful when all the strings in S start with the same prefix)? Why is . not in the allowed characters, since it is present in your first example of pydoc? \$\endgroup\$
    – Leo
    May 3, 2018 at 1:15
  • \$\begingroup\$ You can use <TAB> wherever you want as long as it produces the minimum keystrokes. The image is supposed to be illustrative and not necessarily representative of the challenge itself; I worry that requiring too large or too specific a subset of characters will make the challenge more complicated than it needs to be (or maybe it won't affect much at all?) \$\endgroup\$
    – snail_
    May 3, 2018 at 1:38
  • \$\begingroup\$ Assume S is [abcde] and T is abcdf. What should be the output? \$\endgroup\$
    – DELETE_ME
    May 4, 2018 at 14:02
5
\$\begingroup\$

Existential Golf

\$\endgroup\$
9
  • \$\begingroup\$ Proofs could be simple: it supports NAND, and NAND is functionally complete. \$\endgroup\$
    – tsh
    Jul 5, 2018 at 7:23
  • 1
    \$\begingroup\$ @tsh Currently there is still no winning criteria. \$\endgroup\$
    – DELETE_ME
    Jul 5, 2018 at 9:54
  • 3
    \$\begingroup\$ This is quite interesting (not sarcasm!), but what's the actual challenge? \$\endgroup\$
    – N. Virgo
    Jul 7, 2018 at 7:02
  • 3
    \$\begingroup\$ @Nathaniel When I actually finish it this will be the next installment of proof-golf. \$\endgroup\$
    – Wheat Wizard Mod
    Jul 8, 2018 at 3:19
  • 1
    \$\begingroup\$ It's great to see an unfinished idea, ready for feedback until it's postable. I see this as an important purpose of the sandbox. \$\endgroup\$
    – trichoplax
    Jul 10, 2018 at 19:43
  • \$\begingroup\$ @trichoplax Not everyone think so. \$\endgroup\$
    – DELETE_ME
    Jul 11, 2018 at 3:46
  • 3
    \$\begingroup\$ I definitely disagree with having to make sandbox posts "finished". I agree with not being lazy though. I see this post as a great example of unlazy and unfinished (when posted). There was clearly effort made, and it was made available for feedback early, which can avoid going too far down a path that others already know won't work. Posting early prunes impossible or impractical challenges so challenge authors have more time for writing the challenges that will make it to main. \$\endgroup\$
    – trichoplax
    Jul 12, 2018 at 19:05
  • 1
    \$\begingroup\$ @user202729 For context, I said that in response to a 1-sentence sandbox post. I also said it bothers me when people "just post the bare minimum they can get by with and edit it later". The first revision of this challenge was clearly not the bare minimum to get by with. \$\endgroup\$
    – DJMcMayhem
    Jul 12, 2018 at 19:14
  • \$\begingroup\$ @DJMcMayhem So you're measuring effort? That's usually not a good idea. \$\endgroup\$
    – DELETE_ME
    Jul 13, 2018 at 2:48
5
\$\begingroup\$

Split and recombine a number

This challenge has two related parts. Your task is to write two functions/programs as per the below specifications. You may share code across your submissions, the submissions may call one another, and you may even submit a single submission which handles both conversions. In the latter case, conversion direction may be determined by whether the input is a single number vs a list, or by an additional consistent second value (not a function) input.

Part 1

Given a floating point number, return a list with one element per digit of its integer part, if any, and if the number is a non-integer, one additional part which is the fractional part. If the number is negative, negate all elements in the output. If the number is zero, return a 1-element list with a zero in it.

When the result list is recombined as per Part 2, it must be precise to within an absolute or relative error of 10⁻¹⁰, whichever is more permissive.

Part 2

Given a list generated as per Part 1, return the number which would have generated that list in Part 1.

When the result number is split as per Part 1, each element must be precise to within an absolute or relative error of 10⁻¹⁰, whichever is more permissive.

Examples

Part 1 <-> Part 2
-123       [-1,-2,-3]
2.71828    [2,0.71828]
-800.6     [-8,0,0,-0.6]
321.7001   [3,2,1,0.7001]
-0.01      [-0.01]
100        [1,0,0]
0          [0]

\$\endgroup\$
11
  • \$\begingroup\$ (1) Technically infinities are floating point numbers (or, at least, they're not NaNs). What should the output be for an infinity? (2) How about for 1E45? (3) For numbers which are small enough to have a fractional part, what restrictions are there on the precision of the output? E.g. to take the fourth test case, 321.7001 - 321 in IEEE 754 double format gives 0.7001000000000204. \$\endgroup\$ Nov 18, 2018 at 21:18
  • \$\begingroup\$ Do we need the leading 0 in the list? Seems cleaner without it \$\endgroup\$
    – Quintec
    Nov 18, 2018 at 22:11
  • \$\begingroup\$ @Quintec What leading zero? \$\endgroup\$
    – Adám
    Nov 18, 2018 at 22:28
  • \$\begingroup\$ @PeterTaylor I'll exclude infinities. I'm not sure what do do about inexactness. I guess I could allow stopping at 16 digits of precision. Any ideas? \$\endgroup\$
    – Adám
    Nov 18, 2018 at 22:31
  • \$\begingroup\$ Now that I think about it, string output for part one doesn’t make sense. But if it did, then I meant [2, .718] instead of [2, 0.718] \$\endgroup\$
    – Quintec
    Nov 18, 2018 at 22:43
  • \$\begingroup\$ I don't see any reason to reject 0 <-> [], given that 0.01 <-> [0.01]. \$\endgroup\$
    – Bubbler
    Nov 19, 2018 at 1:21
  • \$\begingroup\$ For the precision, how about something in the line of "correct up to absolute/relative precision of 1e-16"? Partly because big numbers stored in double are not accurate even in the integer parts. \$\endgroup\$
    – Bubbler
    Nov 19, 2018 at 1:29
  • \$\begingroup\$ @user202729 Yes, I'll add that. Also, see tolerance text now. \$\endgroup\$
    – Adám
    Nov 19, 2018 at 12:36
  • \$\begingroup\$ @Bubbler Tolerance specs added. \$\endgroup\$
    – Adám
    Nov 19, 2018 at 12:41
  • \$\begingroup\$ Suggested test cases: 4.4 <-> [4,0.4] and 44.44 <-> [4,4,0.44]. Also, can we assume there will not be any unnecessary trailing zeros? I have a working solution, even with workaround for 0 <-> [0], but for 0.0 it outputs [0.0], but vice-versa for [0.0] it outputs 0 instead of 0.0. Hence the question that there won't be test cases like 0.0, 4.0 or 6.4000 with unnecessary trailing zeros. My programming language outputs 4.0 -> [4,0] -> 40 due to the implicit conversion of 0.0 to 0.. \$\endgroup\$ Dec 4, 2018 at 10:44
  • \$\begingroup\$ @Adám FWIW Composed a solution using JavaScript for the specification at this question, and a solution for the specification at the original question (that currently has a bug for two test cases at "Part 2" portion, though is not incapable of being fixed). \$\endgroup\$ Dec 17, 2018 at 23:47
1
3 4
5
6 7
131

You must log in to answer this question.

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