527
\$\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 needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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

3420 Answers 3420

1
21 22
23
24 25
114
2
\$\begingroup\$

Fence Matrix

Given a positive integer n, output the 2n+1 x 2n+1 "fence"-matrix

0  1  0  1  ...  0 
1  2  1  2  ...  1
0  1  0  1  ...  0 
1  2  1  2  ...  1 
⋮   ⋮  ⋮   ⋮       ⋮  
0  1  0  1  ...  0 

Alternatively you can also return a nested array or print a string (even with other entry delimiters than spaces or none at all) or output a raster image where each entry is represented by one pixel.

Examples

n = 1
0  1  0
1  2  1
0  1  0

n = 2
0  1  0  1  0
1  2  1  2  1
0  1  0  1  0
1  2  1  2  1
0  1  0  1  0
\$\endgroup\$
4
  • \$\begingroup\$ related, but not at all close to a dupe \$\endgroup\$ – Destructible Lemon Jun 7 '17 at 23:13
  • 2
    \$\begingroup\$ 1. The challenge should specify better about what constitutes a fence matrix. I suggest stating "A fence matrix is a representation of a square matrix where the 0-indexed element at index a of 0-indexed line b has the value a%2+b%2`" \$\endgroup\$ – fireflame241 Jun 7 '17 at 23:25
  • \$\begingroup\$ @fireflame241 This suggests using your particular solution, but there are many more to achieve that. \$\endgroup\$ – flawr Jun 8 '17 at 8:54
  • \$\begingroup\$ @DestructibleLemon Ha, I would never have seen the connection if you did not point it out :) \$\endgroup\$ – flawr Jun 8 '17 at 8:54
2
\$\begingroup\$

Anyone who would like may post this challenge to main. Just give credit to @Lordofdark.

How long will I sleep

You need to go to bed, but what you need more is to know how long you will sleep until your alarm rings.

Your task

Write a program or function that takes a time (hours and minutes) as input, and outputs the number of hours and minutes until the next occurence of this time.

Rules

  • In this challenge every clock in 24h format.
  • You must always get the current time for the same timezone; you can assume the input is in this timezone

Input

The input time must be in hours and minutes in any convenient 24h format for your language.
Hours and minutes must always be separated by at least one character

Valid inputs for 8h30:
"8h30"
8H30M
8,30
8 30
[8,30]
...

Invalid inputs for 8h30:
8.5
830
510min

Ouptut

The output is the difference between current time and the next occurrence of the input time (it can only be today or tomorrow).

The same formatting rules apply : hours and minutes separated by at least one character an in 24h format.

Note that the output will always be between 0h00 and 23h59

Examples :

If it is currently 20h10 :

7h30 -> 11h20m
20h -> 23h50m
21h -> 0h50m

Challenge

This is , so the shortest answer in bytes wins. Standard loopholes are prohibited

\$\endgroup\$
9
  • \$\begingroup\$ This is my first challenge so I'm not sure about the I/O rules \$\endgroup\$ – Fabich Jan 31 '17 at 14:51
  • \$\begingroup\$ Hello and welcome to PPCG! :) Your challenge seems fine, though I recommend specifying that you should use a 24h clock earlier in the post. Aside from that, the "minutes are always two figures" part is a bit odd. Does that mean that if I used the format [8, 30] I would then have to return [8, 05]? Personally I would recommend just saying that hours and minutes have to be separate, as it is simpler and would require less space to show. \$\endgroup\$ – FryAmTheEggman Jan 31 '17 at 17:07
  • \$\begingroup\$ What timezone is the input and the current time? Do we assume UTC? What happens if a language can't get the current time? \$\endgroup\$ – Artyer Jan 31 '17 at 22:16
  • \$\begingroup\$ @FryAmTheEggman You are right I removed the 2 figures condition, and I specified at the beginning the 24h format. \$\endgroup\$ – Fabich Jan 31 '17 at 22:58
  • \$\begingroup\$ @Artyer I guess I should add a condition about input and current being in the same timezone. Something like "You must always get the current time for the same timezone; you can assume the input is in this timezone". What do you think I could do for language without access to current time ? \$\endgroup\$ – Fabich Jan 31 '17 at 23:02
  • \$\begingroup\$ @Lordofdark in general, it's good to not exclude challenges for arbitrary reasons, but in this case there's a very good reason for certain languages to not be allowed. If it can't get the time, it can't compete. \$\endgroup\$ – Pavel Feb 1 '17 at 0:37
  • \$\begingroup\$ Are multi-character separators allowed in the input format (e.g. 8 hours 30 minutes)? They probably shouldn't be, or people may well figure out a way to put their entire program in the separators and thus get a score of 0 (or however many bytes eval is in their language). \$\endgroup\$ – user62131 Feb 8 '17 at 5:36
  • \$\begingroup\$ @Lordofdark can I adopt this abandoned challenge? \$\endgroup\$ – user58826 Jun 9 '17 at 12:03
  • \$\begingroup\$ @programmer5000 yes you can. Sorry I totally forgot about this \$\endgroup\$ – Fabich Jun 9 '17 at 13:27
2
\$\begingroup\$

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

Visualized Tree of 3n+1 Conjecture

Originally by @KeyuGan. Thanks for letting me use this!

Introduction

Probably you are already familiar with 3n+1 conjecture (aka Collatz conjecture). As is stated in this golfing problem:

  • Start with an integer n > 1.
  • Repeat the following steps:
    • If n is even, divide it by 2.
    • If n is odd, multiply it by 3 and add 1.

And it is proven that for all positive integers up to 5 * 260, or about 5764000000000000000, n will eventually reach 1.

It is easy to draw a chain of the whole process for an integer (e.g. for 5, the chain is 1<-2<-4<-8<-16<-5).

Task Description

You are asked to print a string of a visualized 3n+1 tree of all chains resulting from positive integers from 2 to n, containing new lines if necessary.

Input and Output

There is only one input n, which can be read from stdin, be a function parameter or from any external sources.

You can safely assume input is valid and does not exceed your language's processing ability. However, your code should be able to deal with inputs of 2 - 446. Under such circumstances, the biggest number involved is 13120.

[Sandbox note: Is 446 a proper minimum ? It turns out to be the largest number in which the biggest number involves is less than 32767]

The output is flexible, as long as:

  • It is a textfile, or a string, or an array of characters, or an array of lines.
  • It contains only 0-9, -, |, <, >, ^, v, spaces or new lines, where <, >, ^, v are for arrows, -, | are for lines.
  • Not hardcoded
  • Correctly visualized and in proper directions (for instance, 1->2->4->8->16->5 and 1-2-4-8-16-5 are not accepted.)
  • All numbers included in the output occur exactly once.
  • All leaves of the visualized tree should lie in the range of 2 ~ n, that is, all numbers in the output must be necessary for the result.
  • the destination of every chain is 1

Besides, the output should meet the following formatting criterion:

  • A number should be arranged horizontally and connected.
  • There should not be horizontally-adjancent digits from different numbers. For instance, in the following example, 17<34 23<46 is OK, while 17<3423<46 is not. Space(s) should be put between the two numbers under this circumstance.
  • There should not be vertically-adjancent digits as well.
  • There should not be zero(es) before a number (such as 0016).
  • There should be only one arrow for a line.
  • The line between two numbers must be straight.
  • As is demonstrated in output, - and | can be omitted if not neccessary.
  • Lines should not be crossed. A solution without crossed lines is proved to be available. A simple explaination is: Thinking in reverse, you can start from integer x, and draw 2x and (x-1)/3 (if result is odd) following x, and repeat the process for every new number. Stop when you have all required integers from 2 ~ n in the graph and erase all unneccessary numbers.
  • You can only draw a line onto and from a number directly, that is, the arrow of the line must be pointing at a digit. e.g. |<--, ^<--, |-- and ^-- are not accepted.
  • The direction of arrows and lines must be correct. e.g. ^- and <| are not accepted.
  • There should not be spaces between arrow and number.
  • There should not be spaces between arrows and lines, neither in lines.

[Sandbox note: Tell me plz if you come up with other loopholes.]

Output is assumed to be printed in a monospaced font (all characters have same width).

Sample

Input

15

Possible Output 1

1<2<4<8<16
         ^
         5<10<20<40<80<160
           ^     ^     ^
           3<6<12|     53<106
                 |        ^
                 13<26<52 35<70
                       ^     ^
                       17<34 23<46
                          ^     ^
                          11<22 15
                             ^
                             7<14<28
                                  ^
                                  9

Possible Output 2

                   15
                   v
                   46
                   v
                   23
                   v
                   70
                   v
                   35
                   v
                   106
                   v
                   53
                   v
                   160
                   v
                   80
                   v
1<2<4<8<16<5<10<20<40<13<26<52<17<34<11<22<7<14<28<9
             ^
             3
             ^
             6
             ^
             12

Possible Output 3

1<2<4<8<16<5     80<160<53<106<35<70<23<46<15
           ^     v
    12>6>3>10<20<40<13<26<52<17<34<11<22<7<14<28<9

Scoring

Your answer should include verifiable output of input 42, without a violation to output requirements. And you should verify your answers with different answers on this page: TBD

[Sandbox note: I will provide a js checker on my site to validate an output.]

Among all accepted codes, shortest code wins.

\$\endgroup\$
8
  • \$\begingroup\$ Smallest output can be a useful winning criterion in some cases, where there is the possibility of continuously finding smaller outputs with little chance of finding an optimal solution. However, in this case the sequence will always be the same, so the winning criterion is how short an output format can be made before being judged unreadable. This has two problems: 1. This will force output formats towards the subjective boundary between readable and unreadable, making judging validity difficult. 2. An output format does not require programming skill. \$\endgroup\$ – trichoplax Oct 22 '16 at 19:47
  • \$\begingroup\$ You might want to consider taking out the "readable" requirement and just keeping the objective description about adjacent numbers and spacing, as that cannot lead to ambiguity. Then you can use a different winning criterion (such as code golf), and people can be flexible in the output format they choose depending on what allows for the shortest code in their language. \$\endgroup\$ – trichoplax Oct 22 '16 at 19:56
  • \$\begingroup\$ Looks like I was commenting on the version before your edit - apologies if some of this no longer applies... \$\endgroup\$ – trichoplax Oct 22 '16 at 19:57
  • 1
    \$\begingroup\$ @trichoplax thanks. I believe your words have convinced me that subjective 'readable' judgement is not that good for this challenge. \$\endgroup\$ – Keyu Gan Oct 22 '16 at 20:04
  • \$\begingroup\$ @trichoplax I have modified the problem a little bit to take out that requirement \$\endgroup\$ – Keyu Gan Oct 22 '16 at 20:15
  • 1
    \$\begingroup\$ One way to test that your requirements are objective is to write a validator program that takes the output of a submission as input and indicates whether it is valid. If you can write this program then the requirements are objective, and it will also ensure everyone is working with the same definition. Any problems you run into while writing it will also help to identify any ambiguities in the requirements. \$\endgroup\$ – trichoplax Oct 23 '16 at 10:51
  • \$\begingroup\$ Can I post this abandoned proposal? \$\endgroup\$ – user58826 Jun 9 '17 at 12:50
  • \$\begingroup\$ @programmer5000 Sure. Mention me if it doesn't bother you. XD \$\endgroup\$ – Keyu Gan Jun 9 '17 at 13:26
2
\$\begingroup\$

Perfect Hash Generator

Given N words you are to generate a perfect hash function (ala gperf). A perfect hash function for a set of strings is a hash function with no collisions. An additional condition is that the range of the generated hash function must be [0...O(N)] (i.e. at most a constant times larger than N). You can use any language for the generated function.

Can we get some feedback on this old post? I'm wondering if it is possible to avoid the obvious loophole of a cat program.

\$\endgroup\$
2
  • \$\begingroup\$ Sounds good at first blush. Do you foresee this as a [code-golf] or some more extensive challenge? If the later what metric would be used to judge it? I think that evaluation of results for compliance is easy enough if the resulting hashes are composed into programs---in unix: entry < testfile > hash_program && hash_program < testfile | sort -u | wc -l and compare to wc -l testfile---but less obvious if the submitters don't provide a scaffold (and if they do should it be counted toward length in the event that this is a [code-golf]?). \$\endgroup\$ – dmckee --- ex-moderator kitten Jun 22 '11 at 1:24
  • \$\begingroup\$ Perl solution, 2 bytes (1, plus 1 for -pE instead of -E): ; Or, wait, did you mean that our program has to print another program that generates a hash? Then say";" I suppose, at 6 bytes. \$\endgroup\$ – msh210 Jun 16 '16 at 14:52
2
\$\begingroup\$

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

Find the mines!

Tags:

You are a mine remover. Your job is to find all mines on a field, without a mine explodes. So, you write an application that can find the mines carefully.

The input

The input can either be provided through command line arguments or through STDIN (tell what you use in your submission). The input items are separated by commas.

The input looks like this:

<current step (zero-based)>,<mine count>,<field width>,<field height>,<field data>

The field data is like a Minesweeper field. Rows in the field data are separated by semicolons, columns are separated by nothing, as each column is just one character. Here are the characters you can get:

  • X This means that you don't yet know what's there, the real data is still hidden. At the start, you get a field full of Xs.
  • / This means that there is nothing on that location.
  • <number> Specifies the count of mines around the location of the number.
  • F This is marked by a flag by you.
  • ? This got a question mark from you. There might be a mine on it, but you are not sure. This is just used as a reminder for you, it doesn't mean something specific to the controller.

Example input:

2,1,3,3,XX1;X1X;XXX

That input means that it's currently your third step, there is one mine, the field is 3x3, and the field looks like:

X X 1
X 1 X
X X X

The output

The output consists of 4 parts: the X of which you want to see the data (like a click in Minesweeper), the location on which you want to put a flag mark, the location on which you want to put a question mark and a sign, used to let the controller know whether you are finished or not (0 for not finished, 1 for finished). Locations are written as X;Y, zero-based. If there is something you don't want to do, output -1. You can also remove flags/question marks using the same way.

Example output:

4;3,-1,3;3

Specifications

  • If your first output data is the location of a mine, you hit the mine and you die, but you'll still get a score.
  • If you select a X which hides an empty location (/), all adjacent empty fields (and their borders, which are numbers) will be revealed.
  • For every step, your program is executed again with the updated arguments.
  • When looking for mines, you are allowed to have more flags than the amount of mines. Only if you finish, the amount of flags must not be more than the amount of mines. If the amount of flags is greater than the amount of mines, your submission is disqualified (for every test!) and excluded from the scoreboard.

Testing

When I test your submission, I'll run 100 tests on every submission, with randomly generated fields, which I created using a program that I'll write after I got some feedback. Every submission gets the same test fields, so it's fair. Test fields look like this:

  • 10 tests with a 10x10 field and 10 mines.
  • 10 tests with a 10x10 field and 12 mines.
  • 10 tests with a 12x12 field and 14 mines.
  • 10 tests with a 15x10 field and 16 mines.
  • 10 tests with a 15x15 field and 35 mines.
  • 10 tests with a 20x20 field and 40 mines.
  • 10 tests with a 25x25 field and 50 mines.
  • 10 tests with a 25x25 field and 60 mines.
  • 10 tests with a 50x50 field and 100 mines.
  • 10 tests with a 50x50 field and 125 mines.

Scoring

You get 10 points for every mine you find, you lose 5 points if you think there is a mine somewhere when there is none and you lose 2 points for every mine you missed. The scoring is always the same, it doesn't matter whether you finish or die. The highest score wins.

In case of a tie, the count of steps is a tie breaker.

Controller

I'll start working on this after I got some feedback.

\$\endgroup\$
15
  • 1
    \$\begingroup\$ You say "like Minesweeper" a couple of times, but on a cursory read I didn't see anything which differentiates it from Minesweeper. Why is this not a dupe of codegolf.stackexchange.com/q/24118/194 ? \$\endgroup\$ – Peter Taylor Jul 24 '14 at 14:58
  • \$\begingroup\$ @PeterTaylor You are right, only the winning criterion is different. As there is many discussion going on about these dupes with only a different winning criterion, I'll wait for some more opinions about whether it is different enough or not. \$\endgroup\$ – ProgramFOX Jul 24 '14 at 15:08
  • \$\begingroup\$ Maybe you could distinguish it by more than just the winning criterion. How about something crazy like a 3d grid of cubes where you can only access cubes that can be reached from the outside, so you slowly clear it from the outside in. \$\endgroup\$ – trichoplax Jul 28 '14 at 22:36
  • \$\begingroup\$ @githubphagocyte I'm not sure what you mean by "where you can only access cubes that can be reached from the outside". \$\endgroup\$ – ProgramFOX Jul 29 '14 at 6:49
  • \$\begingroup\$ That bit isn't essential - a 3d grid would work without that restriction. What I mean is restricting the cubes that can be uncovered or marked to just those on the outside of the big cube at first. Imagine it like breaking blocks to get through to blocks behind them. \$\endgroup\$ – trichoplax Jul 29 '14 at 8:58
  • \$\begingroup\$ The equivalent in the 2d minefield would be treating the 2d playing area as an actual field which you have to walk across, so you can't walk to a square you want to test without testing the squares on a path to it first. \$\endgroup\$ – trichoplax Jul 29 '14 at 9:00
  • \$\begingroup\$ 3d was just my 1st idea - but you could make it different in other ways. You could stick with the integer grid of squares to uncover, but let the mines beneath the grid take on floating point positions. The number in an uncovered square would be floating point because each of the eight squares adjacent to it may contain only part of a mine (which would explode if any of the squares it is overlapping were uncovered). If mines are squares the same size as the grid squares, then it may take 1, 2 or 4 flagged squares per mine, and each flagged square may contain overlap with 1, 2 or 4 mines. \$\endgroup\$ – trichoplax Jul 29 '14 at 9:03
  • \$\begingroup\$ A simpler change would be to keep everything integer but let the mines be 2x2 squares. \$\endgroup\$ – trichoplax Jul 29 '14 at 9:09
  • \$\begingroup\$ @githubphagocyte Thanks for your comments! What about just changing it into a 3d grid, but keep the 'normal' rules? Doing what you said about only accessing blocks if you broke the block that hides it looks complicated to implement. Unfortunately, there will still be one problem left: if everyone would post an optimal solution, then the scoreboard will boil down to luck. \$\endgroup\$ – ProgramFOX Jul 29 '14 at 9:33
  • \$\begingroup\$ Yes I think with the normal rules there will be a clear optimal solution. I guess even working in from the outside there would still be only one objectively best move at each step. \$\endgroup\$ – trichoplax Jul 29 '14 at 10:03
  • \$\begingroup\$ If you want to avoid the possibility of an optimal solution, there are 2 possibilities. 1.Make it a king of the hill and somehow have bots competing against each other in the same minefield. That way an optimal solution against one bot will be sub-optimal against another. 2.Make a change to the game that makes the search space too large for an optimal solution to be found. Then answers will consist of interesting heuristics and there will be the possibility of continually finding better solutions over a long period of time. \$\endgroup\$ – trichoplax Jul 29 '14 at 10:05
  • \$\begingroup\$ @githubphagocyte Your KotH suggestion is a good idea, thanks! I'll think of a good way to do this. \$\endgroup\$ – ProgramFOX Jul 29 '14 at 10:13
  • \$\begingroup\$ I guess just taking turns would work. You'd just need to decide the winning criteria: survivor when the opponent hits a mine / player who identifies the most mine / player who uncovers the most safe squares / ... \$\endgroup\$ – trichoplax Jul 29 '14 at 10:54
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – user58826 Jun 9 '17 at 16:54
  • \$\begingroup\$ Hey @programmer5000, feel free to adopt it. \$\endgroup\$ – ProgramFOX Jun 9 '17 at 16:55
2
\$\begingroup\$

Inspired by lifecompetes.com

Multiplayer Game of Life (GOL)

There are n players that play the Game of Life (standard rules) on an 50 x 50 grid. (Size, border conditions? Toroidal, Absorbing, Mirroring?)

Before first GOL-Step

When the game starts, each player has 12 cells that he can place anywhere he want as long as they do not overlap. Before the first GOL-step occures every player has to place 6 cells. If two players place their cell on the same spot no cell wil be placed an thei cells will remain in each players bank.

During game

In each GOL-Step, each player can place as many new cell on the grid as he has in his bank. If two or more players want to place a cell on the same spot, no cell will be placed there (the cells will remain in each players bank). Every six GOL-steps all the players who have less that 12 cells in their bank will get a new cell in their bank.

Goal

The goal is achieving the maximum number of cells on the grid during 1000 GOL-steps.

How to participate

Each participant has to write a javascript function of the following form (multiple return statements allowed.)

function my_bots_name(field, bank, golstep){
  /* your code */
  return p;
}

Where p is a 2d array of points [[x1,y1],[x2,y2],[x3,y3],...] that the player wants to set. field contains a 2d array of the GOL grid, bank indicates the number of cells in the player's bank, and golstep is the index of the current GOL step (golstep == 0 before the first GOL-step occurs). The function may not the global variables and cannot access Math.random() or Date(). In field the empty cells will be set to 0, the own cells will be set to 2 and the other player's cells will be set to 1. (You will not be able to distinguish between various other players.)

The winner will be determined with a game that contains all valid submissions after one week after the first submission.

TODO

The exact environment will be provided so everyone can test the own function before the official runs.

  • What size of the grid is appropriate? (dependent on number of players?)
  • How many steps should be computed?
  • What border conditions should be chosen?
  • Is the restriction of Math.random() and Date() apropriate? (The idea was that the games will be the same no matter of who/when they will be run. (Deterministic) )
\$\endgroup\$
14
  • \$\begingroup\$ relevant. also relevant. \$\endgroup\$ – Martin Ender Aug 6 '14 at 12:20
  • \$\begingroup\$ It looks like it was abandoned, since the user has not been here for more than a month. I was not able to read everything yet - is there something important that should be considered or is it a challenge that shouln't even be started? \$\endgroup\$ – flawr Aug 6 '14 at 13:03
  • \$\begingroup\$ I just thought you might want to have a look to get some inspiration from a previous spec. \$\endgroup\$ – Martin Ender Aug 6 '14 at 13:09
  • \$\begingroup\$ Ok thank you, I wil read them later. \$\endgroup\$ – flawr Aug 6 '14 at 13:21
  • \$\begingroup\$ What do you mean by "standard rules"? The standard rules for Life have binary cells, and this doesn't. \$\endgroup\$ – Peter Taylor Aug 7 '14 at 22:07
  • \$\begingroup\$ Well each cell of the grid can have two states: occupied by a live cell or not. For executing a GOL-Step it does not matter which cell is of which player, they are all treated the same. (As it is in lifecompetes.com) \$\endgroup\$ – flawr Aug 7 '14 at 22:15
  • \$\begingroup\$ What happens to an empty cell that has 3 neighbours of different players? Are new cells only born if they have 3 neighbours of the same player? \$\endgroup\$ – trichoplax Aug 10 '14 at 20:23
  • \$\begingroup\$ Thank you for pointing this out, I did never think about this special case but I just checked livecompetes and they handle this as follows: A new cell is born if two or three of the neighbours are from the same player. If there are three different players invovled the space remains empty. \$\endgroup\$ – flawr Aug 10 '14 at 20:40
  • \$\begingroup\$ why n players instead of 2 players? \$\endgroup\$ – Sparr Aug 18 '14 at 4:31
  • 1
    \$\begingroup\$ Can you provide some thoughts why only two players would make a better game? If you could start it with n players at once you can let all submissions compete against each other as you do in the original lifecompetes.com \$\endgroup\$ – flawr Aug 18 '14 at 8:11
  • \$\begingroup\$ @programmer5000 Yes, feel free to adopt! Just make sure work out the details in the sandbox before posting. If you want me to help in one way or another, just ping me! \$\endgroup\$ – flawr Jun 9 '17 at 17:43
  • \$\begingroup\$ Can you add support for other languages? \$\endgroup\$ – CalculatorFeline Jun 9 '17 at 18:46
  • \$\begingroup\$ @programmer5000 I thought you wanted to adopt it?!? \$\endgroup\$ – flawr Jun 9 '17 at 19:32
  • \$\begingroup\$ Please next time say that you want to list it for adoption rather than adopting it yourself! \$\endgroup\$ – flawr Jun 9 '17 at 19:39
2
\$\begingroup\$

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

Edit: I'll have to clarify the optional features and there may be more. Essential I want to have the basic features covered, and if anything beyond gets implemented because it saves characters that is okay, but not required.

Edit: Updated but still working on it. Will definitely include edge cases and more examples as test cases.

Edit: It might be cool to have this implemented as a function, and then have some follow up questions where you are allowed to call the function created here while only counting the function call as characters, and not the contents.

Still working on the specifics, but getting it the idea out there.


2-Dimensional Regex

Given a 2-Dimensional regex and a block of text, do a match, a single search and replace or a global search and replace depending on the input.

Implement this as a function. The input should be two arguments to the function. The first is the regex, and the second argument is the string to match. The output should be a truthy or falsey value when doing a match, or the string when doing a search and replace.


Match

Input:

/aaa/
/bbb/
/ccc/

and

aaaab
dbbba
ecccc

Output:

A truthy value

Single Search and Replace

Replace the first instance of the match. The search order is the match that includes the top most character. If multiple matches end up with the top-most character on the same line, then include the left-most match.

Input:

s/bb/cc/
 /bb/cc/

and

abbaabba
bbbaabba
bbbaaaaa

Output:

accaabba
bccaabba
bbbaaaaa

Global Search and Replace

Replace all occurrences of the match. Matches do not overlap, and you use the same search order as the single search and replace.

Input:

s/bb/cc/
 /bb/cc/

and

abbaabba
bbbaabba
bbbaaaaa

Output:

accaacca
bccaacca
bbbaaaaa

Another example:

Input:

s/aba/bbb/
 /aba/aba/
 /aba/bbb/g

and

aaaabaaaa
  aabaababa
aababaababa
aabaaabbaba
 aba

Output:

aaabbbaaa
  aabaabbbb
aabbbbababa
aabaaabbbbb
 aba

Rules

  • Only ASCII characters 32 through 126 are valid.
  • Character classes are valid, [a-c4-6] would match an a,b, c, 4, 5, or 6. And [b?7] matches one b, one ?, or one 7.
  • . matches any character.
  • Use \ to escape there special characters to match their literal character instead of their special meaning: {}[]/\.?*.
  • a? matches 0 or 1 a's.
  • b+ matches 1 or more b's.
  • c* matches 0 or more c's.
  • b{2} matches 2 b's. Ranges such as {2,5} to match 2 to 5 b's is optional.
  • g flag replaces all of the occurrences, without it only the first occurrence would be replaced. This flag is optional.

Optional features:

  • Capture groups are optional. Please specify whether to use () or \(\) to match literal parenthesis.
  • Grouping such as (ab)+ matching all of abababab.
\$\endgroup\$
11
  • \$\begingroup\$ Sounds interesting, but apart from the character-class and . addition it's very similar to codegolf.stackexchange.com/questions/37867/programmers-garden. Some specifics you should clarify (I know you're still working on it, but before I forget it...): Is the regex always rectangular? Are regex and replacement equal in shape? And make sure to specify that matches found with g never overlap. \$\endgroup\$ – Martin Ender Sep 17 '14 at 17:04
  • \$\begingroup\$ First occurrence with which search order? What about all the other things which make up a regex (in particular, full alternation and repetition)? \$\endgroup\$ – Peter Taylor Sep 17 '14 at 17:13
  • \$\begingroup\$ @MartinBüttner I got the inspiration for it while working on the garden one since 2-D regexes would help a lot with that problem! I think it would be cool to implement a lot of regex features and that would be a different problem. /i for case insensitive, maybe even capture groups. The replacement could be a different size than the match (I'll have to define how that affects making a previous match now invalid while using /g). \$\endgroup\$ – hmatt1 Sep 17 '14 at 17:58
  • \$\begingroup\$ @PeterTaylor I'd love to define and add other regex features, but I don't want to make the challenge too hard. I'll think about how to implement repetition and non-rectangular searches. Definitely interested in hearing ideas about making this interesting and feasible! \$\endgroup\$ – hmatt1 Sep 17 '14 at 18:00
  • \$\begingroup\$ As far as overlapping matches goes, it might be okay to have that in the input, but then have the one that would get replaced would be the first in whatever search order we end up choosing. \$\endgroup\$ – hmatt1 Sep 17 '14 at 18:02
  • \$\begingroup\$ If the only regex features you have are a small subset of character classes, it's potentially misleading to call it a regex problem at all. It might be less confusing to talk about 2D pattern matching instead. \$\endgroup\$ – Peter Taylor Sep 17 '14 at 21:11
  • \$\begingroup\$ @PeterTaylor I'm planning on adding more regex features. Good point though! Thanks! \$\endgroup\$ – hmatt1 Sep 17 '14 at 21:16
  • \$\begingroup\$ Having implemented a large part of the ECMAScript regex flavour before, let me tell you that a) getting the spec right and b) implementing regular expressions is a lot of work. Starting with your spec: is repetition greedy? You've got character classes with ranges - what about invalid ranges? What about - at the beginning or end of the string? What about character class negation? What about []? Likewise, what about invalid {m,n} quantifiers? Also, I'd definitely leave out grouping and capturing - that complicates things significantly. \$\endgroup\$ – Martin Ender Sep 24 '14 at 22:17
  • \$\begingroup\$ Added to that are the difficulties from the fact that your regex is 2D. How do I specify that the stuff in two lines is repeated the same amount of times? E.g. if I want to match an n x 2 block of as, I couldn't just write a+ in two lines, right? Because the +s are technically independent. What if there's a + in one line and no + in another? etc... \$\endgroup\$ – Martin Ender Sep 24 '14 at 22:19
  • \$\begingroup\$ @programmer5000 you are welcome to adopt this! \$\endgroup\$ – hmatt1 Jun 9 '17 at 19:36
  • \$\begingroup\$ The second and third examples are the same. \$\endgroup\$ – CalculatorFeline Jun 11 '17 at 4:38
2
\$\begingroup\$

Sandbox

This will be my first kolmogorov-complexity submission, does this question fall under that category?

Is the question clear enough?

Is it too trivial?

Problem

Given no input write a program or a function that outputs or returns the following string:

(<(<>(<>.(<>.<(<>.<>(<>.<>)<>.<>)>.<>).<>)<>)>)

Rules

  • Shortest program wins.
  • Trailing whitespace allowed.
  • Trailing newlines allowed.
  • Unused parameters for functions allowed.
\$\endgroup\$
4
  • \$\begingroup\$ Can you give more context to the string you're outputting, its significance etc? \$\endgroup\$ – Pureferret Jun 15 '17 at 11:24
  • \$\begingroup\$ It's a poor ASCII representation of a crowd of blank stares a single person being (<>.<>) \$\endgroup\$ – LiefdeWen Jun 15 '17 at 11:25
  • \$\begingroup\$ a more common representation being (-_(-_(-_(-_(-_-)_-)_-)_-)_-) \$\endgroup\$ – Skidsdev Jun 15 '17 at 11:28
  • \$\begingroup\$ @Mayube Yes, I just used a broader face so the outputted string is longer \$\endgroup\$ – LiefdeWen Jun 15 '17 at 11:29
2
\$\begingroup\$

Implement Nopfunge

Background

Nopfunge is a very simple Befunge derivative, with no stack and no real form of data storage; all it has is an instruction pointer and five commands ("turn north", "turn south", "turn east", "turn west", "continue in same direction"). However, what it does have is a program that repeats forever in two dimensions, which turns out to be enough to make it Turing complete.

The task

Your program must take, as input, four 2D arrays of characters, a, b, c, and d, via any reasonable means. Each of these will have the same dimensions, and they will be rectangular (although not necessarily square). (Note: This is a simplification from the actual syntax of Nopfunge, but is still just as Turing-complete.)

The program will then conceptually work on an infinite array formed out of sub-arrays identical to the inputs, formed by placing a in the top left corner, b along the top edge, c along the left edge, and d everywhere else, like this:

abbbbbbb …
cddddddd …
cddddddd …
cddddddd …

⫶⫶⫶⫶⫶⫶⫶

(Note that because you can't assume your language can do infinite work in finite time, you won't be able to actually represent the compressed array in memory, so you won't be able to calculate the value at a particular coordinate pair in advance; rather, you'll have to calculate it lazily and/or every time it's needed.)

Then simulate the progress of a Nopfunge program on this array. Specifically, there's an instruction pointer that has a position on the array, and a direction; it starts at the top-left corner, going to the right. Repeatedly, run the command specified by the character at the instruction pointer:

  • >: Move the instruction pointer one position to the right; it now points right
  • <: Move the instruction pointer one position to the left; it now points left
  • ^: Move the instruction pointer one position upwards; it now points up
  • v: Move the instruction pointer one position downwards; it now points down
  • (space): Move the instruction pointer one position in its current direction

Should the instruction pointer ever attempt to move outside its infinite array (by moving above the top edge or to the left of the left edge), your program should exit. If the instruction pointer never attempts to move outside its infinite array, the program should never exit. (Or in other words, the task is to halt if and only if the Nopfunge program does.)

Clarifications

  • You can input the arrays as arrays of character codes (i.e. integers) rather than characters if you wish, but if you do, they must use the ASCII/Unicode encodings, 62 60 94 118 32 for > < ^ v .
  • Your program can do anything if the input arrays aren't all the same size or aren't rectangular.
  • You may take additional inputs for the dimensions (width and height) of the input arrays, if you wish.
  • It doesn't matter what (if anything) your program outputs; all that matters is whether or not it halts.

Victory condition

This is , so shorter programs (in bytes) are considered to have a better score.

Sandbox questions

  • Is the specification easy to understand and unambiguous?

  • Is this the best possible input format? I wanted to avoid the secondary task of having to parse Nopfunge's input format (which uses = and ; to split one array into the four given here), but am not sure whether this format or that one is more convenient for solving the task.

\$\endgroup\$
1
  • \$\begingroup\$ Note so I don't forget: it was pointed out in chat that test cases will be helpful. \$\endgroup\$ – user62131 Jun 21 '17 at 10:15
2
\$\begingroup\$

Reindent Java/C/C++/etc. code

Write a program that adds or removes whitespace to format code nicely. Rules for what the code should look like when you're done:

  • No line should contain more than one of { and }.
  • A { should always be the last thing on a line.
  • A } should always be the only thing on a line (besides whitespace that comes before it).
  • The amount of whitespace in front of each line should be a fixed multiple of the current nesting count. (You can use any amount of indentation you want, as long as it doesn't change.)
  • No whitespace should be inserted or removed that doesn't contribute to satisfying one of these rules.

The nesting count for the first line is 0. The nesting count of any other line is the nesting count of the previous line, plus one if the previous line contains a {, minus one if the current line contains a }.

{ and } inside string literals and comments don't count in the above rules. A string literal is text enclosed in single or double quotes, where single or double quotes with a backslash before them aren't interpreted as the end of the string literal. A comment is text enclosed in /* and */, or text going from // to the end of the line. /* */ comments can be nested.

For example, it should reformat this:

    main() {printf("Hello!"); // I don't care about the world...
        }

into this:

main() {
    printf("Hello!"); // I don't care about the world...
}

\$\endgroup\$
7
  • \$\begingroup\$ Strictly interpreted, the current rules don't allow any legal output for input "{}". You probably need to define rules for string literals and comments. I also note that you don't require the indentation to be consistent (different lines can use different multiples of the nesting count), and that inputs with badly indented lines which aren't adjacent to { or } can't be fixed by inserting or removing whitespace adjacent to { or }. \$\endgroup\$ – Peter Taylor Jul 23 '14 at 9:54
  • \$\begingroup\$ @PeterTaylor Fixed those problems. (I think). \$\endgroup\$ – tbodt Jul 23 '14 at 15:49
  • \$\begingroup\$ Fixed some of them. You still need to add exceptions for { or } inside a string literal or comment, including definitions for what constitutes a string literal or comment (since it varies between languages). \$\endgroup\$ – Peter Taylor Jul 24 '14 at 15:06
  • \$\begingroup\$ @PeterTaylor oh, now I understand what you meant. \$\endgroup\$ – tbodt Jul 24 '14 at 15:51
  • \$\begingroup\$ @tbodt I'd like to take over this challenge if you don't plan on posting it \$\endgroup\$ – musicman523 Jun 26 '17 at 23:29
  • \$\begingroup\$ @musicman523 nah I think i'll post it \$\endgroup\$ – tbodt Jun 26 '17 at 23:46
  • \$\begingroup\$ imo the first code snippet is better than the latter \$\endgroup\$ – Okx Jun 27 '17 at 10:01
2
\$\begingroup\$

RoboCops and Robbers

A while ago we made some code to golf brain-flak for us. Eventually the code got so good that us humans could no longer compete against it.

Now the code has turned against it and its your job to stop it. You need to out golf the robots. They've already golfed all the numbers so you need to write some Brain-Flak code that pushes a positive number to the stack, but is shorter than the code produced by these two bots:

  • The Python, This bot eats numbers for breakfast and caches them for lunch, it still is the top scoring bot on the challenge and its coming for you.

  • The Number Cruncher, based on Neil's top scoring Perl answer, made from boiling hot JavaScript and raw HTML this bot takes no prisoners.

Since we need to stop these rampaging robots as soon as possible you need to come up with the smallest number you can to beat them.

Rules

  • You must write a program to push a number to the stack in Brain-Flak.

  • It must be shorter than the code produced by both of the two bots above when asked to produce the same number

  • Your answer must be stack clean (must push the same number regardless of the contents of the stack) and must not use [].

  • Your score will be the number you produce, with a lower score being better.

  • In the event of a tie where two people have the same number the person with the shorter code will win, if that does not resolve then the first earlier will win.

\$\endgroup\$
9
  • \$\begingroup\$ Why the ban on []? Irresponsible usage is banned by the immediately preceding condition. \$\endgroup\$ – CalculatorFeline Jun 30 '17 at 2:15
  • \$\begingroup\$ @CalculatorFeline The original question the bots came from also banned it. \$\endgroup\$ – Wheat Wizard Mod Jun 30 '17 at 2:16
  • \$\begingroup\$ This seems so obviously a dupe of the question it links that I'm wondering whether I missed something, because I can't think why you'd put in the effort to sandbox it. \$\endgroup\$ – Peter Taylor Jun 30 '17 at 7:18
  • \$\begingroup\$ @PeterTaylor I think you are missing something. The previous question was a meta golf where one writes a program to write Brain-Flak programs. In this challenge you write a single Brain-Flak program. Its basically a CNR where all the cops submissions are generated by bots. Please let me know if there is anything I can do to make it clearer, or if you still think this is a dupe. \$\endgroup\$ – Wheat Wizard Mod Jun 30 '17 at 13:07
  • \$\begingroup\$ Doesn't this lua answer have the best score? \$\endgroup\$ – nmjcman101 Jun 30 '17 at 14:19
  • \$\begingroup\$ @nmjcman101 Oh it does. I hadn't even seen that! I'll fix the question. Thanks. \$\endgroup\$ – Wheat Wizard Mod Jun 30 '17 at 14:20
  • \$\begingroup\$ Also I'm assuming that this would be posted as a single question, not an actual Cops thread and Robbers thread? \$\endgroup\$ – nmjcman101 Jun 30 '17 at 14:21
  • 1
    \$\begingroup\$ @nmjcman101 It would be posted as a single question. \$\endgroup\$ – Wheat Wizard Mod Jun 30 '17 at 14:22
  • \$\begingroup\$ @EinkornEnchanter, but the point of CNR is that the robber's answer does the same thing as the cop's answer. Any answer to this is essentially something which can be combined with the existing answers to the meta-golf to make a better answer to the meta-golf. You could effectively get answers to this question by posting a bounty on the existing one. \$\endgroup\$ – Peter Taylor Jun 30 '17 at 19:56
2
\$\begingroup\$

Deep-dichotomize a list

Given a list, dichotomize it (i.e. split it in half), then dichotomize both resulting sublists, etc., until you reach sublists of length 1.

For example, given [1,2,3,4,5,6,7,8]:

  Dichotomize: [[1,2,3,4],[5,6,7,8]]
  Map dichotomize: [[[1,2],[3,4]],[[5,6],[7,8]]]
  Map map dichotomize: [[[[1],[2]],[[3],[4]]],[[[5],[6]],[[7],[8]]]]
  We end here because we only have singletons

If the list has an odd length, the longest of the two lists should be the second one. For example, [1,2,3,4,5] is dichotomized into [[1,2],[3,4,5]].

The content of the list is irrelevant (you can use whatever you want). You can use any list-like representation of your language, as long as both the Input and the Output use the same representation.

Test cases

Input                          Output
[1]                            [1]
[1,2]                          [[1],[2]]
[1,2,3,4]                      [[[1],[2]],[[3],[4]]]
[1,2,3,4,5,6,7,8,9]            [[[[1],[2]],[[3],[4]]],[[[5],[6]],[[7],[[8],[9]]]]

Scoring

This is , so the shortest answer in bytes wins.

\$\endgroup\$
10
  • \$\begingroup\$ Does the output have to be a list/array? It seems that you're really building a binary tree, and being more flexible in the output would allow languages like Haskell with strict typing which doesn't allow lists of varying depth to participate. \$\endgroup\$ – Peter Taylor Jun 28 '17 at 10:19
  • \$\begingroup\$ @PeterTaylor To me, You can use any list-like representation of your language includes nested lists and so trees. Maybe I should be clearer. \$\endgroup\$ – Fatalize Jun 28 '17 at 10:22
  • \$\begingroup\$ I don't think a binary tree is really list-like. \$\endgroup\$ – Peter Taylor Jun 28 '17 at 10:23
  • \$\begingroup\$ Suggested tags: code-golf, array-manipulation, recursion. \$\endgroup\$ – Erik the Outgolfer Jun 28 '17 at 13:25
  • 1
    \$\begingroup\$ Third testcase is a bit off, a ] is missing at the end. \$\endgroup\$ – Erik the Outgolfer Jun 30 '17 at 12:58
  • \$\begingroup\$ "If the list has an odd length, the longest of the two lists should be the second one" seems like unnecessary fluff to me. \$\endgroup\$ – scatter Jun 30 '17 at 14:42
  • \$\begingroup\$ @Christian Why? \$\endgroup\$ – Fatalize Jun 30 '17 at 14:48
  • \$\begingroup\$ @Christian No it's not, how should I split [1, 2, 3, 4, 5] without that information? \$\endgroup\$ – Erik the Outgolfer Jun 30 '17 at 15:16
  • 1
    \$\begingroup\$ @Fatalize Because you could just as easily say it doesn't matter, whichever your language does by default is fine. \$\endgroup\$ – scatter Jun 30 '17 at 15:52
  • \$\begingroup\$ I also think it would be cleaner to allow odd splits to go whatever way. \$\endgroup\$ – xnor Jul 7 '17 at 5:07
2
\$\begingroup\$

Create a "Neverending" Quine

Your task is to create a program which, when run, outputs its source code repeatedly until stopped. You are allowed to have an extra newline between outputs.
NOTE: All standard loopholes are strictly forbidden. That means cheating quines, etc.


This is , so may the shortest answer win and the best programmer prosper...

\$\endgroup\$
2
  • \$\begingroup\$ Never mind. Found a duplicate. \$\endgroup\$ – ckjbgames Jun 30 '17 at 23:32
  • \$\begingroup\$ Please delete this proposal then and edit it down to a stub. Thanks! \$\endgroup\$ – hyper-neutrino Mod Jul 25 '17 at 0:26
2
\$\begingroup\$

It halts. But why?

Cops/Robbers section

The robbers/cops section can be found here.


Challenge

Cops

Your job is to write a program that always halts. It can do anything it likes, as long as, given any input, it eventually stops. You must also write a mathematical proof that it stops. Two weeks after you have posted your answer (since math is hard, we want to give the Robbers a chance to steal your academic success), you should edit in this mathematical proof. Once you have done so, you are safe, and your score will be the length of your program (in bytes). Whichever safe program has the lowest score wins!

Robbers

Your job is to write a mathematical proof that a given cops program halts, and post it as an answer. You must do so before the cop posts their proof.

You get 1 point for each post cracked, unless you crack it within 24 hours, in which case it is only 0.1 points (this is to prevent people from racking up points on easy answers). You obviously cannot crack your own submissions.

Notes

  1. Cops may not use undocumented or incorrectly documented features of the programming language they are using.
  2. Although the proofs will be written in the informal style common within mathematics (as opposed to completely formal proofs), they must theoretically be valid in the framework of ZFC. This will not come into play for most answers, seeing as most of mathematics can be formalized in ZFC, but some might if they use crazy metamathematical shenanigans (please do not do this (just kidding, go crazy kids)).
    • This means that cops must write programs that can be proven to halt in ZFC. This means, for example the program if isProofThatZFCisInconsistient(input) then infiniteLoop else stop) would be invalid, since although this program always halts (presumably), you cannot prove this fact in ZFC.
  3. Cops, your program is not safe until you post the proof.
\$\endgroup\$
3
  • 3
    \$\begingroup\$ This seems to be more a knowledge of obscure theorems contest than a programming contest. While the Curry-Howard correspondence says that the two are related, IMO this isn't really on topic. \$\endgroup\$ – Peter Taylor Jul 6 '17 at 13:30
  • \$\begingroup\$ @Peter Taylor well, you would also need to golf the obscure theorems. \$\endgroup\$ – PyRulez Jul 6 '17 at 14:09
  • \$\begingroup\$ ^ and obfuscation could come into play. \$\endgroup\$ – FlipTack Jan 3 '18 at 19:22
2
\$\begingroup\$

Don't step on a crack, or you'll break your mother's back


Earlier I was walking down the sidewalk in my town, which is made of concrete slabs and looks something like this (note: not my sidewalk). I decided to try to pace myself such that I didn't step on the little cracks between the concrete slabs. For simplicity, let's say:

  • Each slab is 4 feet long.
  • Each of my feet is 1 foot long.
  • Each crack has 0 width (just like your neighbors' dog).

My natural stride is about 3 feet, which worked out quite well:

3-foot strides

(Excuse my horrible MS Paint skills)

Then I got a little ambitious and decided to take 4-foot strides. This obviously worked out even more nicely (aside from making my legs feel weird):

4-foot strides

This got me thinking, what other lengths of strides could I take? One non-integer example would be 2⅔ feet:

2⅔-foot strides

I could go as short as 1-foot strides, though anything shorter than 1 foot would place my foot-long foot on every crack in the sidewalk. (I didn't do 1-foot strides because I would look weird shuffling down the sidewalk, and also because I was in a rush.)

In fact, there are 6 possible crack-avoiding strides up to four feet: 1, 1⅓, 2, 2⅔, 3, 4.

Challenge

Given a integer concrete slab length 0 < n < 100, output all stride lengths up to n that I could take on that theoretical sidewalk. Assume I can stretch my legs infinitely far (I am a mathematician, after all).

More mathematically, given an input integer 0 < n < 100, output all numbers 0 < k <= n such that no multiple of k, modulated by n, is greater than n - 1.

Expected outputs for inputs 1 through 9 (rounded to 4 decimal places):

1: [1]
2: [1, 2]
3: [1, 1.5, 2, 3]
4: [1, 1.3333, 2, 2.6667, 3, 4]
5: [1, 1.25, 1.6667, 2, 2.5, 3, 3.3333, 3.75, 4, 5]
6: [1, 1.2, 1.5, 2, 2.4, 3, 3.6, 4, 4.5, 4.8, 5, 6]
7: [1, 1.1667, 1.4, 1.75, 2, 2.3333, 2.8, 3, 3.5, 4, 4.2, 4.6667, 5, 5.25, 5.6, 5.8333, 6, 7]
8: [1, 1.1429, 1.3333, 1.6, 2, 2.2857, 2.6667, 3, 3.2, 3.4286, 4, 4.5714, 4.8, 5, 5.3333, 5.7143, 6, 6.4, 6.6667, 6.8571, 7, 8]
9: [1, 1.125, 1.2857, 1.5, 1.8, 2, 2.25, 2.5714, 3, 3.375, 3.6, 3.8571, 4, 4.5, 5, 5.1429, 5.4, 5.625, 6, 6.4286, 6.75, 7, 7.2, 7.5, 7.7143, 7.875, 8, 9]

The expected output for 99 can be found in this Gist. The length of each output corresponds to A002088.

Rules

  • The input will be a positive integer less than 100.
  • The output may be presented in any reasonable format. Entries can be represented as decimal numbers accurate to at least 3 decimal places, or as exact fractions if desired.
  • The output may be unsorted, but it may not contain duplicates.

This is , so the shortest code in bytes in each language wins.

\$\endgroup\$
4
  • \$\begingroup\$ It took me a bit to identify that a foot is 1 foot long. I'd make that more clear. \$\endgroup\$ – Nathan Merrill Jul 7 '17 at 17:52
  • \$\begingroup\$ @NathanMerrill For a second I thought that you were joking :P Should be more clear now. \$\endgroup\$ – ETHproductions Jul 7 '17 at 18:33
  • \$\begingroup\$ output should always be less or equal to input. am i underestood correctly \$\endgroup\$ – tsh Jul 7 '17 at 23:46
  • \$\begingroup\$ @tsh Right, I've clarified that a little more. \$\endgroup\$ – ETHproductions Jul 7 '17 at 23:52
2
\$\begingroup\$

Solve the Trolley Problem

Philosophers have long pondered the Trolley problem. Unfortunately, this no human has solved this problem yet. Luckily, as programmers we can use computers to solve the problem for us!

Your program will take as input a (finite) directed graph (with at most one edge from x to y, for any x and y), with a designated node, and a nonnegative integer attached to each edge (representing the number of people tied to that track). In addition, every node has at least one exit edge.

The trolley starts at the designated node. Each turn, if the trolley is at node x, the utilitarian selects an edge (x,y). The people on that edge die, and trolley is now at edge y. This process continues forever.

Note that people can only die once, so if the edge (x,y) has n people tied to it, and the trolley runs over them, say, 100 times, it will still only result in n deaths.

The utilitarian makes his choices in such a way as to minimize the number of people that die (which is guaranteed to be finite, since there are only finite people). Your program will output this number.

You may take the input graph in any reasonable way you like. For example, you could take it as a matrix, and count the designated node as the one labeled 0. Or you could use something like x1,y1,n1;x2,y2,n2;.... For example 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 to represent the standard trolley problem (with loops at the end).

Testcases:

  • 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (Go from 0 to a, a to c (killing one person), and then keep looping the trolley from c to c).
  • 0,0,1;0,a,5;a,a,0 -> 1 (Keep going from 0 to 0, running over 1 person for all eternity),
  • 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (note that the greedy solution of going to b would be incorrect))
  • 0,a,1;0,b,5;a,b,1;b,a,1 -> 3 (0 -> a -> b -> a -> b -> ...)
  • 0,a,1;0,b,1;a,a,0;b,b,0 -> 1 (Note that there are two different options that the utilitarian might take that both kill only one person)

This is , so the shortest answer wins! Good luck.

Notes: There will be no sick loop de loops and multitrack drifting is banned.

\$\endgroup\$
6
  • \$\begingroup\$ So basically: find the cycle of lowest weight? That's pretty similar to finding the cycle of greatest weight, which is equivalent (for integer weights) to codegolf.stackexchange.com/q/107274/194 \$\endgroup\$ – Peter Taylor Jul 22 '17 at 9:36
  • \$\begingroup\$ @Peter Taylor no, since you may have to kill lots of people to get to that cycle, or it might not be reachable at all. \$\endgroup\$ – PyRulez Jul 22 '17 at 12:26
  • \$\begingroup\$ Aha, so it's finding a rho of lowest weight. Still potentially quite similar in implementation, but certainly admits alternative approaches. It might improve clarity to explicitly describe the rho form of the paths to consider. \$\endgroup\$ – Peter Taylor Jul 22 '17 at 12:33
  • \$\begingroup\$ @Peter Taylor what is rho? \$\endgroup\$ – PyRulez Jul 22 '17 at 15:44
  • \$\begingroup\$ ρ , as in Pollard's rho which uses paths which eventually loop back on themselves to factor composite numbers. \$\endgroup\$ – Peter Taylor Jul 22 '17 at 16:08
  • \$\begingroup\$ You should delete this as it has been posted. \$\endgroup\$ – Erik the Outgolfer Jul 28 '17 at 19:41
2
\$\begingroup\$

An anagram chain

Your challenge is to create a program, P_0, that outputs P_1, that outputs P_2, that outputs... P_n, which finally outputs P_0. Every program in that chain has to be a permutation of every other program, and every program has to be distinct.

For example, if your program (P_0) was

abcd

And that generated another program (P_1)

badc

Which generated another program (P_2)

dabc

Which outputted the first program, you would have a anagram chain of length 3.

Your goal is to make as long a chain as possible, in as short a program as possible.

Your final score will be your chain length - in case there's a tie, the program with the shortest bytecount wins. If there's a tie again, the first poster wins.

Meta:

  • I need a better title. Any suggestions?
\$\endgroup\$
1
  • \$\begingroup\$ [Related]. Actually, I'm pretty sure this is a dupe of another challenge that I can't find at the moment. \$\endgroup\$ – Shaggy Jul 23 '17 at 10:13
2
\$\begingroup\$

Levenshtein distance using only SO titles

Pick 1 or as many titles as you wish from revisions of questions from Stack Overflow. You now have a tuple of all of the characters used in the titles you picked. You may add up to as many newline characters as titles you picked. Using exactly all the elements (characters) in this tuple (you may chose lower or upper versions of each character) write a program or a code snippet that computes the Levenshtein distance between two strings.

That's it. Happy title hunting!

Clarifications and rules:

Revisions

  • We define a revision as seen on https://stackoverflow.com/posts/XXX/revisions
  • for a question without any revision (not edited after being posted), the question itself counts as a revision
  • all revisions are eligible, from the initial posted question to the current version of the question
  • the revision must be created before 10PM 21 July GMT (before the time of posting this challenge on the sandbox)
  • only questions from Stack Overflow qualify (no meta, no other site)
  • deleted questions qualify (the only exception: spam questions don't qualify). I realize not everybody has access to deleted questions, but a question can become deleted after you post so I decided to allow it, especial considering the very large number of non-deleted questions: you have where to pick from.
  • you may pick one revision multiple times. You may pick multiple revisions from the same question.

Your tuple of characters

For instance you pick these hypothetical titles from valid revisions:

  • To be?
  • ...Or not to be? you pick this one 3x
  • Pls. help me!!

Then the tuple you have is this (between "):

"            !!..........????bbbbeeeeeehllmnnnoooooooOOOpPrrrsttttttT"

to which you may add up to 5 new line characters.

You must use all of these characters (nothing less, nothing more) to write your code. In this example your code must contain exactly 12 (space) characters, 2 ! characters, 10 . characters, 4 ? characters, 4 b/B characters etc.

Lower/upper case: regardless of the character case in the title, you may use any case you want for each. In this example you can use (4 b) or (3 b and 1 B) or (2 b and 2 B) or (1 b and 3 B) or (4 B). Upper/lower as defined on http://www.fileformat.info - Unicode data table

Here are all the character you must use in this example:

+----+-----+
|    |  12 |
|  ! |   2 |
|  . |  10 |
|  ? |   4 |
|  b |   4 |
|  e |   6 |
|  h |   1 |
|  l |   2 |
|  m |   1 |
|  n |   3 |
|  o |  10 |
|  p |   2 |
|  r |   3 |
|  s |   1 |
|  t |   7 |
| \n | 0-5 |
+----+-----+

Code

  • You may write a program or a function and use any of the standard methods of input/output.
  • input must be 2 strings
  • you can assume both of the 2 strings are not empty
  • you cannot take other input
  • output must be a number representing the Levenshtein distance between the two strings as defined on wikipedia. You may output leading and trailing white spaces (including new lines).
  • you must not output anything else
  • You may use any programming language, but note that these loopholes are forbidden by default

Score

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

Format

In order to make it easy on everybody, please:

  • link the revisions you use
  • show each title
  • show the final tuple of characters

Meta discussion:

  • Should I encourage/discourage/ban using titles already picked by someone else?
\$\endgroup\$
2
  • \$\begingroup\$ This seems easily abused using comments or other non-executing code. \$\endgroup\$ – KSmarts Jul 24 '17 at 15:17
  • 1
    \$\begingroup\$ @KSmarts yes, you would use comments and non executing code, but it will count to your score. If you need to pick a 20 chars title just to get a certain symbol and the rest of the characters you don't use (you put them after a comment start) then maybe that is not a good deal, isn't it? \$\endgroup\$ – bolov Jul 24 '17 at 15:59
2
\$\begingroup\$

Tell me my vocabulary words! Donated.

When taking textbook notes, I need to write down the vocabulary words and their definition. So your task is to write some code that will give me the vocabulary words and their definitions!

Vocabulary words are detonated with a * on both sides of them, like this: Sentences are .-delimited, meaning that after every . a new sentence starts. An example of a valid sentence would be: This sentence has a *vocab word* in it. The vocab word in the sentence is 'vocab word'.

Input: A string of text with some words marked with asterisks. Only valid inputs will be provided, meaning that only sentences with exactly two asterisks inside of them, and there is something between the asterisks.

Output: A list or delimited string where each item is in the following format: Vocabulary word: sentence. The Vocabulary word is the vocab word found in the sentence. The sentence must be the one with the emboldened vocabulary word in it. If there is any whitespace other than the s separating the words, it needs to be stripped.

Test cases:

Input: *Alan Turing* invented the Turing machine. A *Turing machine* is a machine that follows simple rules, but is capable of any computation.

Output: *Alan Turing*: *Alan Turing* invented the Turing machine.
        *Turing machine": A *Turing machine* is a machine that follows simple rules, but is capable of any computation.

Input: What is code-golf? *Code-golf* is the best site on the SE network. But what is SE, you ask? *SE* is a group of Q&A sites, with a system to prevent bad posts.

Output: *Code-golf*: *Code-golf* is the best site on the SE network.
        *SE*: *SE* is a group of Q&A sites, with a system to prevent bad posts.

\$\endgroup\$
5
  • \$\begingroup\$ So split on '.' and then filter to strings containing a *? Or can there be asterisks which don't mark vocabulary words? Should we trim whitespace at the start and end of the sentences? \$\endgroup\$ – Peter Taylor Apr 6 '17 at 9:54
  • \$\begingroup\$ @PeterTaylor A string surrounded by * is a vocab word, like this: *vocab word*. You need to format the outputted sentence correctly, and trim whitespace. I will edit when I have more time. \$\endgroup\$ – sporklpony Apr 6 '17 at 13:52
  • \$\begingroup\$ Are the following valid inputs or not? a) Unbalanced* asterisk; b) Empty ** vocabulary word; c) Vocabulary* word *has bad spacing. \$\endgroup\$ – Peter Taylor Apr 7 '17 at 10:05
  • \$\begingroup\$ Only the last one is valid. \$\endgroup\$ – sporklpony Apr 7 '17 at 13:25
  • \$\begingroup\$ The latest wording "only sentences with exactly two asterisks in them" suggests that there's no need to filter: just split on ., trim, and prepend Vocabulary word: to each sentence. \$\endgroup\$ – Peter Taylor Apr 7 '17 at 21:03
2
\$\begingroup\$

Base 32 RFC 4648 Compliant Alphabet!

When writing my handy-dandy totp/hotp token implementation in Python and Swift (ad: here), I encountered for the first time RFC 4648. There is a nice and long memo about RFC 4648, but I only had to focus on a very specific part of it: Page 8. If you are bored and want some enthralling reading, you can find this memo here, and a useful table here.

Basically, I was looking for the alphabet that could be used when base 32 decoding a String. Well, this is it: ABCDEFGHIJKLMNOPQRSTUVWXYZ234567, and padding, =. However, simply printing that is not the challenge –– that would be too simple1. Instead, we are going to print this (the comments are for your reference and do not need to be printed):

__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x00 - 0x0F or   0 -  15
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x10 - 0x1F or  16 -  31
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x20 - 0x2F or  32 -  47
__,__,26,27, 28,29,30,31, __,__,__,__, __, 0,__,__,  // 0x30 - 0x3F or  48 -  63
__, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,  // 0x40 - 0x4F or  64 -  79 
15,16,17,18, 19,20,21,22, 23,24,25,__, __,__,__,__,  // 0x50 - 0x5F or  80 -  95
__, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,  // 0x60 - 0x6F or  96 - 111
15,16,17,18, 19,20,21,22, 23,24,25,__, __,__,__,__,  // 0x70 - 0x7F or 112 - 127
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x80 - 0x8F or 128 - 143
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x90 - 0x9F or 144 - 159
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xA0 - 0xAF or 160 - 175
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xB0 - 0xBF or 176 - 191
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xC0 - 0xCF or 192 - 207
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xD0 - 0xDF or 208 - 223
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xE0 - 0xEF or 224 - 239
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xF0 - 0xFF or 240 - 255

There may be trailing spaces after every line, and trailing newlines after the last one.

Also, the single digit numbers can be written as 0[digit] instead of [space][digit]. However, be sure to include the spaces between the four groups.

By the way, the __ actually represent 255, but the former do not make me drown in a sea of digits.


1 Should the challenge be to just print that string?

Any other suggestions to make this challenge more interesting?

\$\endgroup\$
1
  • \$\begingroup\$ Perhaps get a list of characters (of any length) and print such a table? \$\endgroup\$ – ugoren Jul 29 '17 at 19:14
2
\$\begingroup\$

Modular multiplicative inverse

Your task is to given two integer numbers, a and b calculate the modular multiplicative inverse of a modulo b, if it exists.

The modular inverse of a modulo b is a number c such that ac ≡ 1 (mod b). This number is unique modulo b for any pair of a and b. It exists only if the greatest common divisor of a and b is 1.

The Wikipedia page for modular multiplicative inverse can be consulted if you require more information about the topic.

Input and Output

Input is given as either two integers or a list of two integers. Your program should output either a single number, the modular multiplicative inverse that is in the interval 0 < c < b, or a value indicating there is no inverse. The value can be anything, except a number in the range (0,b), and may also be an exception. The value should however be the same for cases in which there is no inverse.

0 < a < b can be assumed

Rules

  • The program should finish at some point, and should solve each test case in less than 60 seconds
  • Standard loopholes apply

Test cases

Test cases below are given in the format, a, b -> output

1, 2 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist

Scoring

This is code golf, so the shortest code for each language wins.

\$\endgroup\$
4
  • \$\begingroup\$ I would've thought this would be a duplicate, but it doesn't look like it is. In particular, this challenge is different. \$\endgroup\$ – isaacg Aug 20 '17 at 22:21
  • \$\begingroup\$ Clarification: Can answers throw an error if there is no inverse? Can they loop forever? \$\endgroup\$ – isaacg Aug 20 '17 at 22:21
  • \$\begingroup\$ @isaacg Thought that as well, was really surprised when I could not find any duplicate. \$\endgroup\$ – Halvard Hummel Aug 21 '17 at 6:14
  • \$\begingroup\$ @isaacg Added some clarification to the text. Allowed errors, but the answers should stop at some point. Also made them have to solve each test case in 60 seconds, as otherwise the challenge would become a bit easy (basically looping over all the possible values) \$\endgroup\$ – Halvard Hummel Aug 21 '17 at 6:16
2
\$\begingroup\$

Is this a valid Takuzu board?

Takuzu is a logic game in which you have to complete a grid with cells containing 0s and 1s. The grid must follow 3 rules:

  1. No three horizontal or vertical cells in a row can be the same.
  2. There must be an equal number of 0s and 1s in each row and column.
  3. No two rows can be the same, and no two columns can be the same.

Let's look at a finished grid:

0011
1100
0101
1010

As you can see, this board follows rule 1, 2 and 3. There are no three horizontal or vertical cells that are the same, all the rows and columns contain an equal number of 0s and 1s, and no two rows and no two columns are the same.

Let's look at a grid that isn't valid:

110100
010011
011010
101100
100011
001101

There's a bunch of problems with this grid. For example, row 5 has three 0s in a row, and column 2 has three 1s in a row, followed by three 0s. Therefore, this is not a valid grid.

Task:

Your task is to make a program which, given a 2D array of n * n 0s and 1s, verifies the board to see if it's a valid, finished Takuzu board.

Examples:

0011
1100
0101
1010

This board follows all the rules, and is therefore a valid Takuzu board. You must return a truthy value for this.

11
00

This is not a valid board - row 1 doesn't follow rule 2. You must return a falsey value for this.

Rules and Specs:

  • You can assume that all boards are square of dimensions n * n, where n is a positive even integer.
  • You can assume that all boards are finished.
  • You may take input as a 2D array containing values signifying 0 and 1, or as a string.
  • You must output consistent truthy and falsey values for truthy and falsey boards, and the values representing "truthy" and "falsey" cannot be the same.

This is , so shortest code in bytes wins!

\$\endgroup\$
5
  • \$\begingroup\$ 1. "No three horizontal or vertical grids in a row can be the same": there's only one grid. I propose rewording as "No horizontal or vertical line of three cells can be the same". 2. Related: codegolf.stackexchange.com/q/68646/194 , codegolf.stackexchange.com/q/118856/194 . Note that because this question works through a long example before stating very briefly that (in essence) the example is irrelevant to the question, it can very easily mislead people into thinking it's an exact dupe of the second of those related questions. \$\endgroup\$ – Peter Taylor Aug 27 '17 at 16:49
  • \$\begingroup\$ ...also note that the example you run through before giving the task can actually be performed by only using rule (2). \$\endgroup\$ – Jonathan Allan Aug 29 '17 at 6:47
  • \$\begingroup\$ @PeterTaylor Will fix the example and other points, I wasn't active for a while, sorry for the late reply. \$\endgroup\$ – clismique Aug 29 '17 at 6:48
  • 1
    \$\begingroup\$ @JonathanAllan Through fixing PeterTaylor's suggestion I also fixed yours :P \$\endgroup\$ – clismique Aug 29 '17 at 6:53
  • \$\begingroup\$ By "You must output distinct truthy and falsey values for truthy and falsey boards" do you mean "consistent" ones - i.e. the Truthy (falsey) value is to be the same for each time a valid (invalid) board is input? The normal definition of Truthy vs Falsey is language dependent: any values that conditionally evaluate as such (i.e. such that the equivalent of the pseudo-code if myVal then print("True!" else print("False!") works as expected). \$\endgroup\$ – Jonathan Allan Aug 29 '17 at 7:05
2
\$\begingroup\$

Reverse Maths Cycles

\$\endgroup\$
7
  • \$\begingroup\$ Seems interesting, but I would add some more to the spec. Maybe an intro, just to make it look less like a bunch of test cases. Also, I would do more explaining in words, rather than relying on the first test case to clarify what you mean. \$\endgroup\$ – Gryphon Jul 27 '17 at 5:01
  • \$\begingroup\$ 1. "apply each of the above functions to each element of an array" surely means that if the array has six elements, each operation should be executed six times, for a total of 36 operation evaluations. Yet the example only appears to perform 6 operation evaluations. 2. Some of the operations have corner cases which aren't specified. Do you guarantee that the input will never contain 0? If not, do you guarantee that we will never have to evaluate division by zero or 0^0? \$\endgroup\$ – Peter Taylor Aug 28 '17 at 14:07
  • \$\begingroup\$ @PeterTaylor 1) Bad wording, I'll fix that. It simply means that each value in both lists are "paired", so to say, with a function, which is then evaluated. 2) I think it would be easier to work with by saying there will never be a 0 in the input, I will clarify. \$\endgroup\$ – caird coinheringaahing Aug 28 '17 at 14:16
  • \$\begingroup\$ May we take input as a list of Strings instead? \$\endgroup\$ – Mr. Xcoder Sep 11 '17 at 18:26
  • \$\begingroup\$ @Mr.Xcoder if you want to, then yes. I'll edit that in \$\endgroup\$ – caird coinheringaahing Sep 11 '17 at 18:38
  • \$\begingroup\$ I feel like this is a good overall challenge, would be nice to see clever solutions \$\endgroup\$ – Mr. Xcoder Sep 11 '17 at 18:40
  • \$\begingroup\$ Also, I'd tag this arithmetic instead since it only involves basic arithmetic operations. \$\endgroup\$ – Mr. Xcoder Sep 11 '17 at 18:41
2
\$\begingroup\$

100 Letters is the Perfect Amount

Oxford dictionary lists the most commonly used English letters in the following order:

EARIOTNSLCUDPMHGBFYWKVXZJQ

And assigns each the following frequencies:

Distribution of the letters...

For the purpose of this challenge, the diagram will be simplified as follows:

z   1
q   1
x   1
j   1
k   1
v   1
b   2
p   2
y   2
g   2
f   2
w   2
m   3
u   3
c   3
l   4
d   4
r   5
h   6
s   6
n   6
i   6
o   7
a   8
t   9
e   12
TOT 100

Now, onto the task at hand; I've provided you all with a dictionary of words to choose from, using this dictionary of words choose as many as you want to output. However the catch is that you must have EXACTLY the count above of each letter in the output using 7-12 words.


Scoring

  • Your base score is the length of your code in bytes.
  • You are allowed to go over or under on the number of letters required, each letter above or under results in a +5 byte penalty.
  • If the number of words you've used is between 7 and 12, no penalty is incurred.
    • IF it exceeds 12, add 10 bytes per additional word.
    • IF it is less than 7, subtract 5 per missing word.

Rules

  • You may use any word from the provided dictionary.
  • Each word you output must be distinctively separated by either a space or a newline.
  • Once a word combination has been posted, you may not use more than 6 of that answer's words together in a new answer.
    • This will be enforced by post date.
  • This is
  • Your score will be as defined in the scoring section.
\$\endgroup\$
5
  • 1
    \$\begingroup\$ How can you get a meaningful penalty for going under the number of letters required when you must have AT LEAST the count above of each letter? \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 0:21
  • \$\begingroup\$ Also, who was Kolmognogniznornia? \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 0:22
  • \$\begingroup\$ @JonathanFrech he was the first Aztec man to invent the concept of speech. \$\endgroup\$ – Magic Octopus Urn Sep 19 '17 at 0:30
  • 2
    \$\begingroup\$ I'm not sure this is really kolmogorov-complexity: by design, a good answer will be incompressible. However, finding a good answer is going to involve a heavy computer search, and then the posted answer is going to be a string literal. That seems completely backwards: the interesting code should be what the question asks for. \$\endgroup\$ – Peter Taylor Sep 19 '17 at 7:39
  • \$\begingroup\$ @PeterTaylor was kinda going for something more unique, y'know? Sorta like my "5 favorite letters" challenge. \$\endgroup\$ – Magic Octopus Urn Mar 13 '18 at 20:47
2
\$\begingroup\$

Implement a BrainFlump interpreter

BrainFlump is the latest alternate memory model brainfuck-esque turing tarpit.

It operates on a memory model we call a "Dump", which is simply an un-ordered collection of integers, with a pointer indicating the current item to operate on. As it is "unordered", when moving to the next item, one is simply chosen at random (chosen uniformly between the items that are not the currently selected item) and the operation pointer is moved to that item.

Commands

+   #Increment the item at the pointer
-   #Decrement the item at the pointer
:   #Add a 0 to the dump, and move the pointer to it
;   #Move the pointer to a random item that is not the pointer's current position
(   #Skip to the matching ) if the item at the pointer is 0
)   #Skip to the matching ( if the item at the pointer is not 0
,   #Read a single character from STDIN and push its ascii value to the dump
    #This also moves the pointer to the new item
.   #Print the current item at the pointer modulo 127 as an ASCII character

Interpreter or Compiler?

BrainFlump is an interpreted language. Meaning your submission must take BrainFlump code as input, and return the expected output of the code.

This is as opposed to a compiler, which would take BrainFlump code as input, and return a compiled binary that returns the expected output.

Other notes

  • When the ; command is used if the dump contains only 1 item, a new 0 is pushed to the dump, and the pointer is moved to it
  • The . command does not pop the item from the dump
  • When the , command is used if STDIN has been exhausted, a new 0 is pushed to the dump, and the pointer is moved to it
  • Any item in the dump who's value is 0 is not considered to exist, unless it is the item at the pointer, therefore to "pop" an item from the dump, you simply set its value to 0
  • Nested loops are supported
  • The random number generator used for the interpreter does not have to be cryptographically secure, but must chose with uniformity.
  • BrainFlump does not support floating point numbers or negative integers. Attempting to decrement a number below 0 has no effect.
  • The maximum value of an item in the dump is 255

Examples/Testcases

brainf**k emulation

++++++(;++++++++;-);.

This should output 0

Explanation

++++++        #Increment the first item to 6
(             #While the item under the pointer is not 0
    ;         #Move to another item in the dump
              #    Note the first time this loop runs,
              #    this will insert a new item
    ++++++++  #Increment the new item by 8
    ;         #Switch to another item in the dump
              #    Note there are only 2 items currently,
              #    So this will switch to the only other
              #    item, the one we initially incremented to 6
    -         #Decrement the item
)             #Repeat the loop if the item is not 0
;             #Switch to the other item
              #    Note this switches the pointer back to
              #    The item we have been incrementing by
              #    8 each loop
.             #Output as ASCII character

This is effectively a 6*8 operation, followed by an output, and is nearly identical to brainf**k's ++++++[>++++++++<-]>. program, which also outputs 0.

Note, however, that brainf**k-esque dump manipulation is only deterministically possible if there are never more than 2 items in the dump.

Random output

+:++:+++:++++:+++++:;.

This will actually always output an unprintable character, however which character is output will be random each time, selected from: SOH, STX, EST, EOT, ENQ, ie ASCII characters 1-5. In a correctly implemented interpreter, this output should be uniformly random between the 5 possibilities.

Explanation

+      #Increment first item to 1
:      #Add new item and move to it
++     #Increment new item to 2
:      #Add new item and move to it
+++    #Increment new item to 3
:      #Add new item and move to it
++++   #Increment new item to 4
:      #Add new item and move to it
+++++  #Increment new item to 5
:      #Add new item and move to it
       #    Note this last item is added because ; will
       #    always switch to an item that is *not* the
       #    currently selected item
;      #Switch randomly to an item in the dump
.      #Output as ASCII character

To give a little more info on this, by the time the ; command is reached, the dump should look like this:

1 2 3 4 5 0
          ^

As ; always switches to a different item, the result will be the pointer at one of the non-zero items.

cat

,(.,)

Nice and simple, and identical to brainf**k's cat program.

For scoring purposes, you should use this gist as input when testing.

When will it end?

++++(,:+++++;++(;++++++;--):++++;---)

This program doesn't output anything, but runs for a non-deterministic amount of time.

Explanation

++++             #Increment first item to 4
(                #Start loop
    ,            #Read char from STDIN to new item in dump
    :+++++       #Push 5 to dump
    ;++          #Switch to random item in dump and add 2
    (            #Start loop
        ;++++++  #Switch to random item in dump and add 6
        ;--      #Switch to random item in dump and subtract 2
    )            #End loop
    :++++        #Push 4 to dump
    ;---         #Switch to random item in dump and subtract 3
)

This one is a little tricky, as ; will never switch to a 0 (Remember items with a value of 0 are considered to not exist)

The inner loop will only exit if ;-- switches to a number <= 2

The outer loop will only exit if ;--- switches to a number <= 3

Due to the inherent randomness of the language, this should always terminate... eventually.

For scoring purposes, you should use the exact string Hello, World! as input when testing.

Scoring

This is meaning the interpreter that on average runs the fastest, wins!

Scoring will be determined by running each of the 4 test-cases above 100 times, and determining an average runtime (due to the inherent randomness of the language, a high number of runs should be made to minimise anomalous results).

Then once you have an average for each testcase, sum the 4 times, and that is your final score. Lower is better

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

Count bicubic graphs

This question assumes basic knowledge of graph theory terminology.

A cubic graph is a simple graph whose vertices each have exactly 3 edges. A bipartite graph is a vertex whose vertices can be divided into two disjoint sets such that every edge is between a vertex in one set and a vertex in the other set. A bicubic graph is a graph which is both cubic and bipartite.

It is easy to show that a bicubic graph must have the same number of vertices in each of the bipartite halves, so the number of vertices must be even. It is also easy to show that it must have at least six vertices. The only bicubic graph with six vertices (up to isomorphism) is the so-called utility graph or K3,3:

The edges are the Cartesian product of two three-element sets of vertices

Input

A positive non-zero integer n.

Output

The number of bicubic graphs with 2n vertices, up to isomorphism.

Notes

  • The graphs are not required to be connected.
  • This sequence is OEIS A008325. However, hard-coding these values will be considered a breach of standard rules. You may hard-code for inputs of up to 3, but above that the code should follow the same paths and be correct assuming unbounded memory and time for any valid input. It seems unlikely that we will extend the sequence, but it's nonetheless a worthy stretch goal.

Test cases

Input  Output

1      0
2      0
3      1
4      1
5      2
6      6
7      14
8      41
9      157
10     725
11     4196
12     29816

Winning criterion

The fastest program wins. The primary win condition is the largest input for which correct output is given within 10 minutes. In case of ties, the time taken to compute the value for that input will be compared. If the difference is less than 20 seconds, the earlier answer wins.

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

All ASCII Art

Input

You will be given a set of x, y, and A pairs, where x and y represent a coordinate on a 2-d plain, and A is some character. You may take these pairs in any convenient format, e.g. a list of lists, three separate lists, a list of pairs of lists, etc.

Output

You will output a grid of spaces. However, at every coordinate specified in the input, the space should be replaced by the character. Basically, the input specifies the locations of characters, and you have to draw them.

Specifics

  • x and y may be either a coordinate or a row-column pair (e.g. the origin can be in the bottom left, with x increasing to the right and y increasing up, or the origin can be in the top left, with x increasing to the right and y increasing down).
  • All characters are guaranteed to be printable ASCII, and will never be a space.
  • x and y are >= 0
  • You may output trailing whitespace (but not infinitely). What matters is that the output visually looks like what the input specified, not the whitespace.

Test Cases

Test cases format (the test cases have the origin at the top left corner; this is optional, see specifics):

# of coordinates
row col char
row col char
...
-----------
output

Test cases:

2
0 0 :
0 1 )
-----------
:)

3
0 0 -
0 1 _
0 2 -
-----------
-_-

4
0 1 -
1 0 |
2 1 -
1 2 |
-----------
 - 
| |
 - 

11
0 0 (
0 1 ^
0 2 o
0 3 ^
0 4 )
1 1 /
1 2 |
1 3 \
2 2 |
3 1 /
3 3 \
-----------
(^o^)
 /|\
  |
 / \

Here is a Java program which can be used to test out inputs

Meta

\$\endgroup\$
2
  • \$\begingroup\$ Is (0,0) the top-left of the output image? It kinda looks that way from your examples, but that should be made clear. \$\endgroup\$ – AdmBorkBork Nov 3 '17 at 12:30
  • \$\begingroup\$ @AdmBorkBork it is for the test cases, but its meant to be optional... I'll clarify \$\endgroup\$ – Socratic Phoenix Nov 3 '17 at 12:43
2
\$\begingroup\$

RaceTrack Arena KOTH

(haven't come up with a very good title)

this koth is inspired by the pen and paper game Racetrack.

RaceTrack Movement

Racetrack (and this racetrack-inspired koth) use a distinctive vector based movement system.

all bots players are on a square grid.

initially, a cycle (this is what we will call bot players) will have no movement i.e. be completely motionless

However, after a cycle begins moving, it gains inertia; it will not stop moving in this direction unless it acts to stop moving.

On every turn, a cycle can change their speed on each axis (x and y) by -1, 0, or 1, and the same with y speed. this includes sticking with their current speed. This means that every turn, a cycle has 9 options of spaces to move to (excluding spaces which would cause them to crash)

enter image description here

for example, in this diagram, the cycle indicated by the red space, which has just moved from the brown space, has the option of the 9 green squares in the red-lined area, the main, more saturated, green square, along with the blue line, represents where it will end up staying on its inertial course

if, for some reason, the cycle wanted to come to a complete stop, it would take 5 turns, which is the Chebyshev distance between the inertia vector's end and the cycle.

[more tbd obviously]

don't downvote for the lack of content please

\$\endgroup\$
10
  • \$\begingroup\$ Can (like on the paper) every contestant see the whole arena, including other contestants' movements? As I remember, it's alternative moves rather than simultaneous and you crash if you end up on or cross other contestant's position or most recent motion line. How will the edge be defined? You crash if you end up outside OR if your motion line crosses outside area. Explain the rules in your post. You can have different rules, but if you keep alternative move the starting player will have advantage. So every contestant of this KOTH should have equal number of participation at each position. +1 \$\endgroup\$ – Heimdall Nov 11 '17 at 8:36
  • \$\begingroup\$ We don't know the first player has so much of an advantage; random positions are rather likely to have a much larger effect than the fact that player 1 can strategy steal, and even with non-randomised positions, playing with multiple players is very different in flavour from just two players, since playing against one player, their moves only make themselves better or worse, but in multiplayer another (dumb) player can unwittingly help you or harm you without regard to whether it does help them. Also I haven't decided on whether bots can see the whole playing field or if they have a top speed \$\endgroup\$ – Destructible Lemon Nov 12 '17 at 22:53
  • \$\begingroup\$ ... if there is a limit to their sight, it follows there has to be a limit to their speed, and even if there isn't an implemented, it's at least effectively a limit, since moving somewhere you can't see if there is a wall is not a great strategy. also there will probably be obstacles that act like walls, so the edge is not the only place to crash, btw. anyway, the definition of crash, is that a bot's movement line goes through a hazardous square. I suppose that touching a vortex can be considered a near miss \$\endgroup\$ – Destructible Lemon Nov 12 '17 at 22:55
  • \$\begingroup\$ that said, I guess there's no real reason not to randomise the turn order each game. \$\endgroup\$ – Destructible Lemon Nov 12 '17 at 23:09
  • \$\begingroup\$ Suppose you're the first, whatever your starting position. You accelerate so that you have maximum safe speed. Others won't accelerate to higher speed because that would cause them to crash at the turn (unless, as you put it, a dumb racer decides to overtake you anyway). Let's say the next turn is left. You'll go as far left as possible. Racers on your right will just lag behind. But racers on your left will only be able to keep up until you "cut the corner". They won't be able to stop you from doing so because at no point they will be ahead of you. But maybe some random debris on the path ... \$\endgroup\$ – Heimdall Nov 13 '17 at 10:49
  • \$\begingroup\$ Actually, dumb racing might be a good strategy... If you are allowed to have more than one bot in a race, one can be "dumb" to increase the other one's chances... \$\endgroup\$ – Heimdall Nov 13 '17 at 10:52
  • \$\begingroup\$ @Heimdall that strategy tends to be discouraged. making a simple bot is not, but making bots collude is frowned upon. \$\endgroup\$ – Destructible Lemon Nov 13 '17 at 23:33
  • \$\begingroup\$ So I guess the wall is made by placing a series of hazardous squares, and crashing means you're out of that race only. But how is crash between two racers defined and dealt with? \$\endgroup\$ – Heimdall Nov 16 '17 at 7:12
  • \$\begingroup\$ @Heimdall no offence, but I haven't actually made enough of the spec that I should be answering questions from you in the comments, especially since you have a rather inaccurate idea of the game (because i haven't specified). for example, it's not a race. \$\endgroup\$ – Destructible Lemon Nov 16 '17 at 8:29
  • \$\begingroup\$ Sorry, I'm a bit impatient. It's just I'm looking forward to your game which is still in the making, that's why I gave it +1. I assumed it was a race (or series of races) where the bots compete because it's based on that paper race. Also I was trying to be helpful by raising potential issues in order for the task to be well formed. \$\endgroup\$ – Heimdall Nov 16 '17 at 10:27
2
\$\begingroup\$

Bunnies in (three-dimensional) space

A panicked call has come in from the International Space Station: a psychological experiment has gone awry, and the astronauts have lost all their Stanford Bunnies. You have been tasked to come up with a way to get them as many replacements as possible.

 

a description of the plan

 

Because of the rush, NASA has just one rocket available for this mission: a Delta II Heavy with a box-shaped cargo hold (a "right cuboid", they called it) of length x, width y and height z, all even integers. Your job is finding out how many bunnies to bring - and how to pack them.

Input and output

Your program should take the dimensions of the cargo hold as arguments. It should then compute how many bunnies it can fit in there, producing output as follows:

  • A header line consisting of the length, width and height of the box, as integers, seperated by spaces. This is a copy of the input.
  • A line for every bunny fitted, containing the following as dotted floats, all seperated by spaces:
    • the position of the center of the bunny, relative to the center of the box, as x, y and z
    • the rotation of the bunny, as a rotation about the x, y and z axes, in that order (a.k.a. Tait–Bryan angles).

For example, a solution for a box of 4 × 6 × 8 units, with a single, un-rotated bunny in the center, would be described as follows:

4 6 8
0.0  0.0  0.0   0.0  0.0  0.0

A solution for a larger box of 12 × 8 × 8 units with two bunnies could look like this:

12 8 8
 4.5433 2.5843  1.4380 3.1415 0.0000 0.0000
-2.4839 1.3923 -1.9400 0.0000 0.0000 1.5707

...although your program will likely be able to fit more bunnies.

Dataset

This is the vertex data for the bunny. It is in Wavefront OBJ format, which means that every 'v' line describes a vertex (point in x, y, z space), and every 'f' line describes a triangle of vertices. Compared to the original Stanford Bunny model, this model has been translated so that its centerpoint is at the origin (0, 0, 0) and it fits snugly inside a unit cube.

Tips

  • You don't have to use the dataset above in your program - for example, you might want to simplify it more - but you should make sure that your output is correct when using the 'official' model.
  • Be careful with rounding, both during calculations and when outputting your result.
  • The Wavefront format can be imported into the free blender program if you want to see what it looks like (make sure to choose 'Z Up').
  • Your program does not have to be usable for other models: it can be a special-purpose bunny-fitting utility.

Rules and winner

  • A valid solution is one where, if you constructed a box of bunnies using the solution's description and the vertex data above, none of the bunnies would touch each other or the bounding box.
  • Your program has to be usable for box sizes other than the one below.
  • Your entry should run in less than, say, ten minutes on reasonable hardware.
  • The program must be self-contained: you can only use your language's standard libraries.
  • The winner is the program that succesfully fits the most bunnies in a box of 12 × 8 × 6. Include (a link to) your code, (a link to) a solution for that box size, and, if you made any, a picture of your solution.
\$\endgroup\$
6
  • 1
    \$\begingroup\$ I'd recommend against Unicode chars in the title. \$\endgroup\$ – Erik the Outgolfer Nov 17 '17 at 22:42
  • \$\begingroup\$ @EriktheOutgolfer Fixed! \$\endgroup\$ – Wander Nauta Nov 17 '17 at 22:43
  • 3
    \$\begingroup\$ Why only allowing the language's standard libraries? That seems like it would ban things like numpy for python, which may be useful for extra math functions. It's a standard loophole for people to make new libraries designed to solve a challenge anyway. \$\endgroup\$ – Rɪᴋᴇʀ Nov 18 '17 at 0:26
  • \$\begingroup\$ Also, is there a tie-breaker if 2 programs find the optimal solution? Shortest code? "Whoever submitted first" is likely fine but seems ugly to me, maybe fastest code? \$\endgroup\$ – Rɪᴋᴇʀ Nov 18 '17 at 0:29
  • \$\begingroup\$ @Riker: I added the self-contained rule to prevent people from grabbing an off-the-shelf implementation for the actual problem, or introduce wild dependencies that make it hard to reproduce results. You're right that numpy is generic enough that it could almost be considered part of the standard library, but I thought I had to draw the line somewhere. Do you think I should remove the rule altogether? \$\endgroup\$ – Wander Nauta Nov 18 '17 at 0:38
  • \$\begingroup\$ @Riker: A naive solution can fit 576 bunnies, and well-thought-out versions will likely score much much more, so I think the chance of two different approaches accidentally getting exactly the same score is quite slim. If there is an optimal solution (I'm actually not sure!) I'd be comfortable letting the first submitter to find it win. \$\endgroup\$ – Wander Nauta Nov 18 '17 at 0:47
2
\$\begingroup\$

Inside or Outside?

Given a point and a polygonial loop that is not self intersecting, determine whether the point is strictly inside or outside of the loop.

Details

  • The polygon is given as an ordered list of points cartesian coordinates.

  • The single point is given as a separate input, but you can also say that is e.g. always the first or always the last point in the list.

  • We only consider points with integral coordinates.

  • You can choose whatever representation is easiest to work with for you for instance a list of pairs, or two separate list for the x- and y-coordinates etc.

  • The list describes the polygon in positive orientation, that means the inside is always on the left side if you follow the points from the beginning to the end of the list. (You may choose to use the opposite orientation but please indicate if you do.)

  • A point is considered to be strictly on the inside, if it is not contained in the border of the polygon.

Examples

[(0,0),(0,2),(2,2),(2,0)]: (1,1) is strictly inside, all other points are outside
[(0,0),(0,2),(2,0)]: no point is strictly inside

more coming soon...

Meta:

  • Should I relax the strictly inside to just inside (i.e. a point on the border is also considered as inside)
  • Should I let the participants choose which version they prefer?
\$\endgroup\$
5
  • \$\begingroup\$ 1. Not necessarily convex or must be convex? 2. What you describe as "positive orientation" is the same as "in counter-clockwise order". 3. Does the point for testing for inside/outside have integral coordinate? \$\endgroup\$ – user202729 Nov 26 '17 at 14:42
  • \$\begingroup\$ The shape is arbitrary and the testing point does have integral coordinates too (see examples) \$\endgroup\$ – flawr Nov 26 '17 at 14:46
  • \$\begingroup\$ Seems that you flipped what "positive orientation" means. Keep this if that is what you want. / Proposed test case: (0,0),(0,5),(2,2),(5,0) → strictly inside integer points = (1,1),(1,2),(1,3),(2,1),(3,1) where the shape is a concave quadrilateral. \$\endgroup\$ – user202729 Nov 26 '17 at 14:58
  • \$\begingroup\$ Well the first one was incorrect, positive actually means counter clockwise. \$\endgroup\$ – flawr Nov 26 '17 at 19:37
  • \$\begingroup\$ 4. Does the flexiblity in input extend to allowing us to require the first vertex to be repeated at the end of the list? 5. The strictly inside vs inside issue might be best addressed by asking for a classification into strictly inside, on the perimeter, and strictly outside. This is slightly trickier, I think, because of the implication that you can't cast a ray to infinity and just ignore edges which are parallel to it. \$\endgroup\$ – Peter Taylor Nov 27 '17 at 10:37
1
21 22
23
24 25
114

You must log in to answer this question.

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