480
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

| |
\$\endgroup\$

2872 Answers 2872

1
30 31
32
33 34
96
1
\$\begingroup\$

Golfing with ultrasound

Within medical physics, the percentage of ultrasound reflected between material boundaries can be calculated using two pieces of data: the density(p) and the speed(c) at which sound travels through the material.

To calculated the percentage reflection the following equation can be used

(Z1-Z2)^2 / (Z1+Z2)^2

Where Z1 and Z2 are the acoustic impedances(Z) of the two materials. Z is calculated such that Z=pc That is density * speed of sound in the material

This is where the issue lies

I have two ways of asking the question

1:

Given the acoustic impedance for two materials, calculate the percentage reflection.

2:

Given the density and speed of sound in two materials, calculate the percentage reflection

Reason

The first method will be much simpler, in the way you are just plugging values into a formula. However I feel that method 2 is heavy on the inputs, and I understand that four inputs is a large number of inputs in golfing challenges

On posting the question I will also add a number of test cases

| |
\$\endgroup\$
  • \$\begingroup\$ Firstly, I think you should add test cases while it's still in the sandbox. I find it's easy to miss important ones. In your formula you say Z=pc. What is c? I think you should add some formatting to your formulas, as they are a bit hard to read. You could also consider using some TeX service to generate an image of the formula for you. Also, density is usually denoted by ρ. \$\endgroup\$ – FryAmTheEggman Jun 29 '16 at 19:38
  • \$\begingroup\$ I was going to use rho, but I didn't know where to find one. In hind sight I could have copied and pasted from Wikipedia. Speed should have been given as c not v. But I will make clear what I mean by Z=pc. What is TeX? I've not heard of it before? \$\endgroup\$ – george Jun 29 '16 at 19:41
  • \$\begingroup\$ TeX is a very popular typesetting program, most of your textbooks were probably made using some variant of it. For example, go to this site and enter \frac{(Z_1-Z_2)^2}{(Z_1+Z_2)^2} as the text. You should see a much easier to read version of your formula as an image. \$\endgroup\$ – FryAmTheEggman Jun 29 '16 at 19:45
  • \$\begingroup\$ @FryAmTheEggman Wow that's a really cool website, thanks! I will edit the question soon and hopefully it will be better \$\endgroup\$ – george Jun 29 '16 at 19:50
  • 1
    \$\begingroup\$ With either option, it looks like there's a direct mathematical formula that leaves little to golf. \$\endgroup\$ – xnor Jun 29 '16 at 22:45
1
\$\begingroup\$

Write a BF to Hexagony Converter!



According to community moderator Martin Ender ♦:

Hexagony is Turing-complete as any brainfuck program can be translated to Hexagony with some effort. (Source)

Your program's job is simple: take a valid brainfuck program, and convert it to an equivalent Hexagony program. For completeness, here are all the relavant commands in both BrainFuck and Hexaongy (taken from esolangs.org).

brainfuck

brainfuck operates on an array of memory cells, also referred to as the tape, each initially set to zero. There is a pointer, initially pointing to the first memory cell. The commands are:

  • > Move the pointer to the right
  • < Move the pointer to the left
  • + Increment the memory cell under the pointer
  • - Decrement the memory cell under the pointer
  • . Output the character signified by the cell at the pointer
  • , Input a character and store it in the cell at the pointer (-1 for EOF)
  • [ Jump past the matching ] if the cell under the pointer is less than or equal to 0
  • ] Jump back to the matching [ if the cell under the pointer is nonzero

All characters other than ><+-.,[] should be considered comments and ignored.

Modifications:

  • Infinite tape in both directions
  • Arbitrary precision integers (like hexagony)
    • No overflow/underflow
  • [ acts the same for negative numbers as it does for 0

Hexagony

Source code

The source code consists of printable ASCII characters and line feeds and is interpreted as a pointy-topped hexagonal grid, where each cell holds a single-character command.

Because of this restriction, the number of commands in the source code will always be a centered hexagonal number. For reference, the first 10 centered hexagonal numbers are:

1, 7, 19, 37, 61, 91, 127, 169, 217, 271

When reading a source file, Hexagony first strips all whitespace characters. Then the remaining source code is padded to the next centered hexagonal number with no-ops and rearranged it into a regular hexagon. This means that the spaces in the examples above were only inserted for cosmetic reasons but don't have to be included in the source code. The following three programs are identical:

   a b c  
  d e f g 
 h . . . .  
  . . . .   
   . . . 

abcdefgh...........

abcdefgh

But note that

abcdefg

would instead be the short form of

   a b 
  c d e  
   f g

Control flow

Hexagony has 6 instruction pointers (IPs). They start out in the corners of the source code, pointing along the edge in the clockwise direction. Only one IP is active at any given time, initially the one in the top left corner (moving to the right). There are commands which let you switch to another IP, in which case the current IP will make another move (but not execute the next command), and then the new IP will start by executing its current command before making its first move. Each IP has an index from 0 to 5:

   0 . 1
  . . . .
 5 . . . 2
  . . . .
   4 . 3

The direction of an IP can be changed via several commands which resemble mirrors and branches.

The edges of the hexagon wrap around to the opposite edge. In all of the following grids, if an IP starts out on the a moving towards the b, the letters will be executed in order before returning to a:

   . . . .          . a . .          . . k .          . g . .   
  a b c d e        . . b . .        . . j . .        . h . . a  
 . . . . . .      g . . c . .      . . i . . e      . i . . b . 
. . . . . . .    . h . . d . .    . . h . . d .    . j . . c . .
 f g h i j k      . i . . e .      . g . . c .      k . . d . . 
  . . . . .        . j . . f        f . . b .        . . e . .  
   . . . .          . k . .          . . a .          . f . .   

If the IP leaves the grid through corner in the direction of the corner there are two possibilities:

-> . . . .   
  . . . . .  
 . . . . . . 
. . . . . . . ->
 . . . . . . 
  . . . . .  
-> . . . .  

If the current memory cell (see below) is positive, the IP will continue on the bottom row. If it's zero or negative, the IP will continue on the top row. For the other 5 corners, just rotate the picture. Note that if the IP leaves the grid in a corner but doesn't point at a corner, the wrapping happens normally. This means that there are two paths that lead to each corner:

      . . . . ->   
     . . . . .  
    . . . . . . 
-> . . . . . . .
    . . . . . . 
     . . . . .  
      . . . . ->

Special characters

. is a no-op: the IP will simply pass through.
@ terminates the program.

Arithmetic

) increments the current memory edge.
( decrements the current memory edge.

I/O

, reads a single byte from STDIN and sets the current memory edge to its value, or -1 if EOF is reached.
; takes the current memory edge modulo 256 (positive) and writes the corresponding byte to STDOUT.

Control flow

$ is a jump. When executed, the IP completely ignores the next command in its current direction. This is like Befunge's #.
_, |, /, \ are mirrors. They reflect the IP in the direction you'd expect. For completeness, the following table shows how they deflect an incoming IP. The top row corresponds to the current direction of the IP, the left column to the mirror, and the table cell shows the outgoing direction of the IP:

  cmd │  E SE SW  W NW NE
──────┼────────────────────
   /  │ NW  W SW SE  E NE
   \  │ SW SE  E NE NW  W
   _  │  E NE NW  W SW SE
   |  │  W SW SE  E NE NW

< and > act as either mirrors or branches, depending on the incoming direction. The cells indicated as ?? are where they act as branches. In these cases, if the current memory edge is positive, the IP takes a 60° right turn (e.g. < turns E into SE). If the current memory edge is zero or negative, the IP takes a 60° left turn (e.g. < turns E into NE).

  cmd │  E SE SW  W NW NE
──────┼────────────────────
   <  │ ?? NW  W  E  W SW 
   >  │  W  E NE ?? SE  E

[ switches to the previous IP (wrapping around from 0 to 5).
] switches to the next IP (wrapping around from 5 to 0).
# takes the current memory edge modulo 6 and switches to the IP with that index.

Memory manipulation

{ moves the MP to the left neighbour.
} moves the MP to the right neighbour.
" moves the MP backwards and to the left. This is equivalent to =}=.
' moves the MP backwards and to the right. This is equivalent to ={=.
= reverses the direction of the MP. (This doesn't affect the current memory edge, but changes which edges are considered the left and right neighbour.)

Some commands/description omitted for conciseness, full list here.

Other rules:

  • Input/Output may be done however is most natural for your language
    • Output does not have to be formatted like a hexagon
  • Must run in a reasonable amount of time
    • Minimal brute-force
    • No brute-forcing the entire program
  • You can only use Hexagony commands specified in this challenge.
  • This is , so shortest code wins
    • {META NOTE: I know this challenge is hard, is there a better way to score?}
  • As usual, standard loopholes are prohibited.

Test Cases:

Input: (cat)

,.[,.]

Output: (example)

   \ . .
  < _ . .
 . _ ; . .
  . . > ,
   . @ .

Input: ("123")

+++++++++++++++++++++++++++++++++++++++++++++++++.+.+.

Output: (example)

     ) ) ) ) )
    ) ) ; ) ; /
   ) ) ) ) ) ) /
  ) ) ) ) ) ) ) /
 ) ) ) ) ) ) ) ) /
  ) ) ) ) ) ) ) )
   ) ) ) ) ) ) )
    ) ) ) ) ) )
     . . @ ; <

Input: (@primo's infinite Fibonacci)

+[[<+>->+>+<<]>]

Output: (example)

       ) \ . . . . |
      . | . / { } < .
     . . . . > [ . / >
    . . . . . . . . . .
   . . . . . . @ . . . .
  / . ] < . > < . ] . . .
 _ > " ' / | . > < . . . .
  _ / . . . / . . [ . . .
   . / . . . . . . ) . .
    . . . . . . . . ] .
     . . . [ . . . . |
      . . [ . . . . (
       . \ ) ] ) ] <
| |
\$\endgroup\$
  • \$\begingroup\$ I am quite sure that the outputs are not unique, are they? \$\endgroup\$ – flawr Jul 4 '16 at 16:18
  • \$\begingroup\$ @flawr The outputs do not have to be unique as long as the inputted BF programs do the exact same thing, under all circumstances. \$\endgroup\$ – Blue Jul 4 '16 at 16:22
  • 1
    \$\begingroup\$ I think Hexagony's padding rules would be important, especially if you don't require the output to be formatted like a hexagon. I predict most answers to generate tons of no-ops at the end, which can't be omitted without messing up the layout. \$\endgroup\$ – Martin Ender Jul 4 '16 at 16:26
  • \$\begingroup\$ I don't think it's a good idea to mask brainfuck in the question body, since it hurts searchability. You're going to need the brainfuck tag anyway. \$\endgroup\$ – Dennis Jul 4 '16 at 16:36
  • \$\begingroup\$ @Dennis Should I change the title as well? \$\endgroup\$ – Blue Jul 4 '16 at 16:48
  • \$\begingroup\$ No, the title cannot contain fuck due to network-wide rules. \$\endgroup\$ – Dennis Jul 4 '16 at 16:51
  • \$\begingroup\$ I think this challenge is actually rather easy except for translating [] loops: everything else is a simple mapping. I think the most likely type of answer will just generate the code mostly linearly while keeping track of a "stack" of loops and then figuring out what size hexagon to put it in. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 18:34
  • \$\begingroup\$ @FryAmTheEggman Should I make this challenge metagolf to encourage less linear output? \$\endgroup\$ – Blue Jul 4 '16 at 20:29
  • \$\begingroup\$ @Blue That would certainly be interesting, but I have doubts you'd get a lot of participation in that case. \$\endgroup\$ – Martin Ender Jul 4 '16 at 20:41
  • \$\begingroup\$ I agree with Martin, I may not have worded my last comment very well, as the [] translations will actually be rather time consuming, if not difficult. Further increasing the complexity of the challenge will make it more interesting, but it might be too much to expect more than an answer or two at that point. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 21:11
1
\$\begingroup\$

Platformer game

Write a platformer game.

Rules:

  • Keyboard input, minimum three commands: left, right and jump;
  • Real-time. Screen should update (and the game iterate) on timer. Update speed should not depend on CPU speed. FPS should be between 2 and 120;
  • It should be possible both to win and to lose (the game can although be very hard and require preparing a special bot to win or to lose);
  • Playing field should have at lest 64 positions, minimum width is 6, minimum height is 5.
  • Player may move left, right or jump. Player moves down automatically unless on a platform. Jumping means moving up for some limited time (not higher than 67% of playing field's height), then falling down like usual.
  • Falling down outside playing field is losing the game. Stepping on 6 distinct platforms is a win.
  • Player, platforms and borders of area should be visible on playing field. If output method is ASCII art, it may looks like this:

    .....----...
    ............
    ...@....----
    ..---.......
    .......---..
    ............
    
  • Platforms may be horizontal, vertical, diagonal. Platforms should not overlap (except of differently oriented). Platform's projection to horizontal and vertical axes should not overlap for at least 4 platforms. Example of too projection-overlapping playing field:

    ............
    ....@.......
    .--.--..--..
    ............
    .--.--..--..
    ............
    
  • Platforms may move. Overlapping rules apply only to initial positions.

  • The game should track losing and winning conditions and stop the game, outputting distinct messages in case of lose or win.
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I feel like this spec is much too broad. Different answers will vary so much that I don't think they will be comparable. I think you need to specify each interaction precisely. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 19:43
  • \$\begingroup\$ @FryAmTheEggman, The idea was to just implement a platformer game, with rules only to prevent "degenerate", uninteresting cases (like 1x1 field with 0 platforms and unconditional lose in the first turn). Do you think it would be more interesting if each answer's game would basically be the same? \$\endgroup\$ – Vi. Jul 4 '16 at 21:06
  • \$\begingroup\$ I think it is a much more interesting golfing problem if all the games are the same, as otherwise what is the point of golfing? I don't think this is a good site to try to get interesting platforming games, as I don't think this will work with either a pop-con or code-challenge either. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 21:09
  • \$\begingroup\$ I though it would be interesting if main point were to design the game to be compactly implementable, not just to implement already designed game in a compact way... \$\endgroup\$ – Vi. Jul 4 '16 at 21:22
1
\$\begingroup\$

Compute h-index of PPCG users

Thanks to @Suever for his help refining this challenge.

Background

The h-index is a commonly used metric that measures the amount and quality of publications of a given scholar or researcher. It is defined as follows:

A scholar with an h-index of n has published n papers each of which has been cited at least n times.

Adaptation for PPCG

In this challenge I propose to compute the h-index of PPCG users based on the analogy

  • paperanswer;
  • paper's citations → answer's vote count, defined as upvotes minus downvotes.

The following examples illustrate the computation of h-index. The array to the left is the vote count of answers in descending order for a hypothetical user, and the number to the right is the resulting h-index:

[5 3 2 1 1]    2
[1 1 1]        1
[]             0
[-1 -2]        0
[0]            0
[9 4 3 ...]    3

Referring to the last example, note that we don't need to know the array entries after the 3.

The challenge

Given a user identification, output their h-index.

Rules

User identification can be defined as anything reasonable, such as user number, user name, or user name without spaces.

The result must be based on actual data from the PPCG site. You may want to take a look at the StackExchange API, for example here.

Note that some users have a lot of answers. For one such user the API may not give all the results, or may only give them split across several chunks. However, if you ask the API to provide the results with an appropriate sorting you may not need all of them to compute the h-index (see last example above). Also, you may assume that the h-index of any user will be less than 100.

If the answer can't be tested in an online compiler (for example due to restrictions to read web content), you are encouraged (although not required) to post some evidence that the answer works, such as a screen capture.

This is code golf. Fewest bytes wins.

Table of h-indices

After submitting your answer, you may optionally edit the table below to include your own h-index, in the indicated format. Please keep the table in decreasing order, so that users with higher h-indices appear higher on the table. I will remove the dummy user names when the table has some actual content.

Example user name: 5
Another example: 3
Yet another user: 3
| |
\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman Having 1000 answers is irrelevant only if you ask the API for the answers in descending order of votes. The note is intended to make it clear that asking for the answers in that order is probably a good idea. I've rephrased a little, I hope it's clearer now. As for how many results the API provides in the same chunk, I think the limit is 100, but I'm not sure \$\endgroup\$ – Luis Mendo Jul 4 '16 at 23:45
  • \$\begingroup\$ Yes, I think that is much clearer now. Also, Yet another user? I hate that guy... \$\endgroup\$ – FryAmTheEggman Jul 5 '16 at 0:13
  • \$\begingroup\$ We've had a challenge to find the h index. With that done, this mostly looks like a question to query the SE API. \$\endgroup\$ – xnor Jul 5 '16 at 10:28
  • \$\begingroup\$ @xnor Oh. Pity. I didn't see that challenge. I guess this is mostly a duplicate then \$\endgroup\$ – Luis Mendo Jul 5 '16 at 11:11
1
\$\begingroup\$

What is closer?

Tags: ,


Inputs: a, b (Both integer and positive) .Output: Integer, in natural numbers sequence.

We have one single atom which has a electrons, we ionize the atom with b positive charges (take b electrons out).

The output is the sum of the orbital quantum numbers (n,l,ml) which is nearest to the atom shell.

EXAMPLE: We take 3 electrons from 26Fe, Now we have 26Fe3+. We need to get the sum of the nearest remained orbitals quantum numbers to the shell.

We have this configuration for Fe3+: [Ar], 3d3, 4s2

The nearest orbital to shell has these numbers:

n = 4
l = 0
ml = 0

In this case:

a => 26
b => 3
output => 4

My 3rd grade chemistry teacher asked me once to create such a program, but I didn't success, I found the paper that my teacher wrote these descriptions on it and I typed it here because I believe that someone might create an interesting code-golf for this.

| |
\$\endgroup\$
  • \$\begingroup\$ You can't create the atoms and electrons tags right now (2/150 rep). Even then, we're not going to need them. \$\endgroup\$ – user48538 Jul 6 '16 at 9:03
  • \$\begingroup\$ This is a long way from being self-contained. I don't know whether someone who knows quantum chemistry would find the question clear, but I need a link to some background material to even start trying to work out what I'm supposed to do. \$\endgroup\$ – Peter Taylor Jul 6 '16 at 16:59
1
\$\begingroup\$

KotH Chess Warriors.

This game will be based on fairy chess, but really could be imagined to be anything else.

Submissions will include both: A function that determines the moves of the piece (as in, how the piece can move), called at the start, and a function that determines how it moves each turn, called each turn, of course. Bot's move simultaneously; strategy is needed. A piece may make 5 moves in a row before it must rest.

Bot's will be able to do any valid move they choose, and the input they will get when deciding what to do will be: a value that can be 2, 1, 0, or -1, for each possible move. 2 denotes that an ally is in that square, 1 denotes that an enemy is in that space. 0 denotes an empty space which could be moved to, -1 represents an illegal move, which may result from the board ending or another piece in the way. If a piece attempts to move into it's ally, the following things could happen; A) ally stays still; Piece stays where it is. B) ally moves; Piece moves where it wishes. C) ally is captured; Piece recaptures

See below for early stage point spending system

Sandbox

I don't have the experience to host this challenge, so someone who can program these kind of things will need to help.

I have sketched out some movement point system, but I need to figure out how large the board is, and so how valuable riders (pieces that move continously, like a rook), would be, compared to leapers, before i could finalise it

Here is the quick system done, which could clearly be improved (for one thing, the multiple move thing probably needs to be a bit more expensive):


Point buying system

Points: each piece receives (to be decided) points base move: points spent on a move are as so. Largest dimension + floor(small dimension/2). There are no riders in this mode; Only repeated movement Repeated movement by x cost:*ceil(x^1.25) make move-only=/2 It is possible to have a leaping attack and sliding attack on the same square; it is also possible to have only one of these able to attack; How this is sorted is that both moves get their own value, and so you can attack if the attack move by itself can reach there.

Examples for base move costs:

  • Any king move: 1
  • any knight move: 2
  • Zebra move:4
  • Camel move:3

PLEASE NOTE: These move values on their own are not representative of how powerful a piece with that move actually is; A knight is better than a camel or zebra. However, when paired with other moves, the zebra and camel moves may become effective.

Example of moves that can be purchased:

     1
7   2  3
6    @55555
     4
  • move 1=(2+floor(0/2)):2 points
  • move 2=(1+floor(1/2)):1 point
  • move 3=(2+floor(1/2)):2 points
  • move 4=(1+floor(0/2)): 1 point
  • move 5=((1+floor(0/2))*ceil(5^1.25))=8 points
  • move 6=(5+floor(0/2))=5 points
  • move 7=(5+floor(1/2))=5 points

in total, this piece costs: (2+2+1+1+8+5+5) 24 points.


Considerations:

  • How large the board is. I'm fairly sure of having a cylindrical board; the left wraps to the right and vice versa.
  • how exactly turns work. So far, I have thought that the way it works is this: Everyone moves simultaneously. When you move, you deplete your remaining moves, which tops and starts at 5. You can choose to not move, and replenish your moves at any point.

    However, this could induce stale games which don't end properly.

| |
\$\endgroup\$
  • \$\begingroup\$ I think you should add a hyperlink to the Wikipedia page on Fairy Chess for users to refer to. Also, if you're interested, there's a great game online that involves unique fairy chess pieces. It's called Chess Evolved Online. Not only are there different pieces, but you build your setup ahead of time and don't know what setup your opponent will have. \$\endgroup\$ – mbomb007 Jul 22 '16 at 19:34
1
\$\begingroup\$

Calculate my total hours

I record the work I do for one of my customers using a flat file in the following format:

0000-00-00 0000-0000 0.0 code0000 free text

The 0.0 represents the amount of time spent on the task identified by code0000, where 0000 is an optional numeric task ID and code is a project code (and does not contain digits or spaces).

Because I'm lazy, I need as short a program as possible to calculate subtotals of my total time for each project, plus a grand total. If you are using plain text output it should show the hours first and then the project code on the same line, and then the grand total on a line on its own with no code. You don't need to use a specific numeric format but you should be capable of dealing with half hours (0.5) in both the input and output.

| |
\$\endgroup\$
  • \$\begingroup\$ Are the beginning strings (presumably a date, and something else?) and the free text ever relevant? If not, I'd consider omitting them. Is any order for the subtotals acceptable? \$\endgroup\$ – FryAmTheEggman Jul 11 '16 at 14:35
  • \$\begingroup\$ @FryAmTheEggman Sorry, but that's my actual input format. The good news is that the subtotals can be in any order. \$\endgroup\$ – Neil Jul 11 '16 at 16:26
  • \$\begingroup\$ It's obviously up to you, but I think that input makes it a chameleon challenge. I wrote a preliminary Pyth answer to do this, and only 16 of the 36 bytes were related to summing and grouping, the other 20 were used for processing. (Surely it can't be that hard to preprocess away the first two fields and the free text? :P ) \$\endgroup\$ – FryAmTheEggman Jul 11 '16 at 17:07
  • \$\begingroup\$ If I didn't have to preprocess them away I could just open the file in Excel and be done with it... \$\endgroup\$ – Neil Jul 11 '16 at 18:41
1
\$\begingroup\$

Undone Mathematics

Definitions

I define the following:

nᵗʰ Undone Addition of A

Let +ᵣ A denotes the nᵗʰ Redacted Addition of A; the sum of the elements of A after n layers have been removed in every dimension:

 ²+ᵣ [1,2,3,4,5,6,7] = ∑ [3,4,5] = 12    // 1D: remove leading and trailing elements

     [[1,1,3]
 ¹+ᵣ  [4,2,5]  = ∑ [2] = 2    // 2D: remove leading and trailing rows and columns
      [3,4,1]]

Then +ᵤ A denotes the nᵗʰ Undone Addition of A; the nᵗʰ Redacted Addition of A plus the sum of the elements of A:

 ²+ᵤ [1,2,3,4,5,6,7] = ²+ᵣ [1,2,3,4,5,6,7] + ∑ [1,2,3,4,5,6,7]

     [[1,1,3]        [[1,1,3]      [[1,1,3] 
 ¹+ᵤ  [4,2,5]  = ¹+ᵣ  [4,2,5]  + ∑  [4,2,5]
      [3,4,1]]        [3,4,1]]      [3,4,1]]

nᵗʰ Undone Multiplication of A

Let ×ᵣ A denotes the nᵗʰ Redacted Multiplication of A; the product of the elements of A after n layers have been removed in every dimension:

 ³×ᵣ [3,2,1,1,2,3,1,1] = ∏ [1,2] = 2    // 1D: remove leading and trailing elements

Then +ᵤ A denotes the nᵗʰ Undone Multiplication of A; the nᵗʰ Redacted Multiplication of A times the product of the elements of A:

 ³×ᵤ [3,2,1,1,2,3,1,1] = ³×ᵣ [3,2,1,1,2,3,1,1] × ∏ [3,2,1,1,2,3,1,1]

nᵗʰ Undone Average of A

Let μ denote the average (arithmetic mean), i.e. μA = (∑A)N and μᵣA denote the nᵗʰ Redacted Average of A; the average of the elements of A after n layers have been removed in every dimension:

 ³μᵣ [3,2,1,1,2,3,1,1] = μ [1,2] = 1.5

Then μᵤ A denotes the average of the nᵗʰ Redacted Average of A and the average of the elements of A:

                          ³μᵣ [3,2,1,1,2,3,1,1] + μ [3,2,1,1,2,3,1,1]  
 ³μᵤ [3,2,1,1,2,3,1,1] = ─────────────────────────────────────────────
                                               2

Task

With all this in mind, create an interpreter that will evaluate expressions that use the below operations (numbers are just examples). Alternatively, extend the language of your choice to include the notation.

1 + 2        Addition
3 × 4        Multiplication
μ [5,6]      Average
7 +u [8,9]   Undone Addition
9 ×u [1,2]   Undone Multiplication
2 μu [3,4]   Undone Average

Note that you do not need to implement redacted operations. They were only defined above to facilitate the definitions of the undone operations.

You may substitute any ASCII or Unicode symbol for +, ×, and μ as long as you stay consistent: You may not choose * with ×u.

Each undone operator has a higher order precedence than their normal counterpart.

Test cases:

2+u [1,2,3,4,5,6,7]40

1+u [[1,1,3][4,2,5][3,4,1]]26

3×u [3,2,1,1,2,3,1,1]72

3μu [3,2,1,1,2,3,1,1]1.625

0.1 × 2+u [1,2,3,4,5,6,7]4

2+u [1,2,3,4,5,6,7] × 0.14

0+u [[[1,1][3,2]][[1,3][3,1]]]15

1+u [[[0,1,1][2,1,1][1,0,0]][[2,2,2][2,2,0][1,0,2]][[1,2,0][2,1,1][2,1,2]]]34

1×u [[[1,1,2][1,1,1][1,2,1]][[1,2,2][2,2,1][2,2,1]][[1,1,1][1,1,2][2,1,1]]]2048

1μu [[[2,2,3][3,2,1][3,3,3]][[1,3,3][2,1,1][2,1,3]][[2,3,3][3,2,3][3,2,1]]]3.259

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I find the structure of the definitions very confusing. It would help to a) define terms before you use them; and b) be explicit about the domain and range of the operators. I also, possibly as a result of b), fail to understand the examples: ITSM that ²+ᵣ [1,2,3,4,5,6,7] should be a sum over zero elements because by the time you've removed the first two rows and the last two rows you're left with -3 rows. And the test cases are even more confusing: what is [[1,1][3,2]][[1,3][3,1]]? It looks like two matrices side by side, but I didn't see any mention of implicit operators. \$\endgroup\$ – Peter Taylor Jul 12 '16 at 20:57
  • \$\begingroup\$ @PeterTaylor a) I originally had redacteds before undones, but I wanted to put the focus on the undones. I'll swap again. b) Notice that the input can be n-dimensional, so as [1,2,3,4,5,6,7] is one-dimensional, only the first and last elements in that only dimension need to be stripped off, giving [3,4,5]. The later examples are missing outer brackets, to indicate that they are 3D. Thanks for your feedback! \$\endgroup\$ – Adám Jul 13 '16 at 6:01
  • \$\begingroup\$ 1. There's no way visually to distinguish the 1D examples from the 2D ones. Now that you've added some [] to the test cases, they're better. Why not do the same for the 2D examples: add a [ before the first row and a ] after the last one, as a cue to distinguish them from the 1D cases? 2. If you think that the redacted distract from the undones, you could rephrase undone addition in terms of a convolution with an n-dimensional "matrix" with elements 1 or 2 according to distance from the exterior; then introduce redacted addition as an alternative way of understanding it. \$\endgroup\$ – Peter Taylor Jul 13 '16 at 7:40
  • \$\begingroup\$ @PeterTaylor 1. is done. I'm not sure how to formulate 2). \$\endgroup\$ – Adám Jul 13 '16 at 11:02
1
\$\begingroup\$

Family Tree, Folder Tree

Given a simple family tree in a format reasonably similar to the format outlined below, create a file tree to match it, as explained below.

Input

An ascii family tree in a similar format to the following:

                Grandpa Jim = Grandma Jane
                            |
                 -------------------------------------------------------
                 |          |          |                               |
               Bill Bob     Jim Jane   Sam Sammyson = Aunt Jimbo     Daddy McDad = Mommy McMom
                                                    |                            |
                                                  -----------                    Me
                                                  |         |
                                                Cousin One  Cousin Two

The scheme can be changed within reason, however the test cases provided will meet the following specs:

  1. = Symbolizes a marriage
  2. If there are any children from a marriage, there will be a | one line below the = symbolizing the marriage.
  3. A - character that is below a |, or connected (by adjacency) to a - that is immediately below a | are used to signify multiple children. Below any of these - there may be a |, which will have a the first word of a name immediately below it. This full name is the name of a child.
  4. The initial line of the family tree will only contain two people.

This spec maybe should be cleaned up more.

Note that there won't be any relationships more complicated than = marriage or | child linking two names. This means that more complicated relationships, such as divorce or step-children, will not appear in the tree.

Output

There will be no output as such, instead the program/function will create a directory structure matching the input. For example, the above example would lead to the following directory tree:

$ tree family_tree/
family_tree/
├── Grandma Jane
│   ├── children
│   │   ├── Bill Bob
│   │   │   └── parents
│   │   │       ├── Grandma Jane -> ../../../../Grandma Jane/
│   │   │       └── Grandpa Jim -> ../../../../Grandpa Jim/
│   │   ├── Daddy McDad
│   │   │   ├── children
│   │   │   │   └── Me
│   │   │   ├── parents -> ../Jim Jane/parents
│   │   │   └── spouse
│   │   │       └── Mommy McMom
│   │   │           ├── children -> ../../children/
│   │   │           └── spouse
│   │   │               └── Daddy McDad -> ../../../../Daddy McDad/
│   │   ├── Jim Jane
│   │   │   └── parents -> ../Bill Bob/parents/
│   │   └── Sam Sammyson
│   │       ├── children
│   │       │   ├── Cousin One
│   │       │   └── Cousin Two
│   │       ├── parents -> ../Jim Jane/parents
│   │       └── spouse
│   │           └── Aunt Jimbo
│   │               ├── children -> ../../children/
│   │               └── spouse
│   │                   └── Sam Sammyson -> ../../../../Sam Sammyson/
│   └── spouse
│       └── Grandpa Jim -> ../../Grandpa Jim/
└── Grandpa Jim
    ├── children -> ../Grandma Jane/children/
    └── spouse
        └── Grandma Jane -> ../Grandma Jane/

The directory tree must satisfy the following:

  1. Create a directory called family_tree that will contain the entire family tree.
  2. Inside family_tree/ there will be exactly two directories, these are the two people at the top of the family tree.
  3. For every person in the tree, do the following in their directory:
    1. If they have a spouse, create a spouse directory. If the spouse already has a directory named after them, create a link to that directory within the spouse directory. Otherwise, create a directory in the spouse directory with the name of the spouse.
    2. If they have children, then they must have a spouse. If the spouse already has a directory named children, then create a link to that directory and name the link children. If their spouse doesn't already have this directory, create the children directory and add a directory corresponding to each child.

Again, this is a rough draft. The spec needs to be cleaned. I welcome comments

Note that, in all cases, it does not matter where the true directory and where the link is, as long as the link is properly setup. Also, it is okay to create links to other links.

Also, link means symbolic link throughout the challenge.

This is

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

The French Farmer in the Dell

I used to work with kids and The Farmer in the Dell was a popular song among them. Also, I like challenge like 99 bottles of beer or Polar Bear, Polar Bear, what do you hear?. Try them too!

Goal

In your programming language of choice, write the smallest program possible which will output the following text. Output should match exactly, including case, spacing, and punctuation. A trailing linefeed is fine but specify it in your answer. We will play with the french version of the song because I find it more interesting than the english version (also I am french so more memories for me!).

Le fermier dans son pre,
Le fermier dans son pre,
Ohe, Ohe, Ohe,
Le fermier dans son pre.

Le fermier prend sa femme,
Le fermier prend sa femme,
Ohe, Ohe, Ohe,
Le fermier prend sa femme.

La femme prend son enfant,
La femme prend son enfant,
Ohe, Ohe, Ohe,
La femme prend son enfant.

L'enfant prend sa nourrice,
L'enfant prend sa nourrice,
Ohe, Ohe, Ohe,
L'enfant prend sa nourrice.

La nourrice prend son chat,
La nourrice prend son chat,
Ohe, Ohe, Ohe,
La nourrice prend son chat.

Le chat prend sa souris,
Le chat prend sa souris,
Ohe, Ohe, Ohe,
Le chat prend sa souris.

La souris prend son fromage,
La souris prend son fromage,
Ohe, Ohe, Ohe,
La souris prend son fromage.

Le fromage est battu,
Le fromage est battu,
Ohe, Ohe, Ohe,
Le fromage est battu.

If you are french, you may note that I replace all é with e. It is not important for the challenge and I prefer to stay full ASCII.

If you want to code while listening to the song, you can find it on YouTube. :)

Sandbox Questions

A not so difficult challenge. I originally thought about posting it directly, but I prefer to share it first. I don't think test case are needed. I implemented both the english and french version and the last one is far better to my taste :)

| |
\$\endgroup\$
  • \$\begingroup\$ The only thing I'd be worried about is if this is a duplicate of something. If the structure of the song is too similar to another one I think it should be closed. That said, this is pretty similar to the polar bear song, but without a second verse type and with an exception or two? I don't know whether that is enough, so I wouldn't vote to close on my own. \$\endgroup\$ – FryAmTheEggman Jul 20 '16 at 19:14
  • \$\begingroup\$ This looks vulnerable to the techniques which have been used on previous songs, the canonical example of which is the rickroll. \$\endgroup\$ – Peter Taylor Jul 21 '16 at 7:39
1
\$\begingroup\$

Fix Pokemon Go's Servers

Background

As you may or may not be aware, Pokemon Go's servers have not fared well under the stress of the game's extreme popularity. As an amateur programmer, I'm in the sweet spot where I know just enough to think I can solve all of their problems, but not enough to be able to understand how complex their problems actually are. Thus, I find myself constantly thinking "Why didn't they just do <insert naive suggestion here>? It would fix everything!" This challenge is focused on one of those probably-useless ideas I've thought up.

First, some very quick background, in case you haven't played the game (you can skip this paragraph if you have): In the course of gameplay, Pokemon can randomly appear at certain real-life locations. Every player in the same location sees the same Pokemon, and multiple players can catch one Pokemon.

One potential difficulty I see with this is storing all of that data. With millions of concurrent players, the game servers have to keep track of millions of Pokemon. That's a lot of IO for their database. Fortunately, I, a graduate of not one, but two introductory CS courses, have a solution! Because player interactions have nothing to do with where and when Pokemon spawn, it is essentially deterministic. This means that it should be possible to drop the database entirely (at least for this one specific task), and replace it with a function! This function could take the player's location, the current system time, and a random seed as input, and return a list of all Pokemon within a certain radius. Because no database lookup is needed, this function would be lightning fast and easily scalable to millions of players.

The Challenge

Your challenge is to write this function. Obviously, the actual game of Pokemon has way too many details to make a feasible code challenge for PPCG, so here's the simplified guidelines:

  • Create a function that takes the following inputs, in any format you like:
    • Player location, as 2D coordinates
    • System time
    • Random seed
  • The function should return a list of nearby Pokemon, with the following requirements:
    • "Nearby" means "within one unit of distance of the player", where distance is 2d euclidean distance. (Just ignore the edge case where the location is on a round planet)
    • Each Pokemon should have a species and an exact location
    • This list can be in any format you want
    • The results are deterministic (i.e., for the same location, time, and random seed, the same Pokemon are always returned)
    • The Pokemon should persist for some pseudorandom amount of time
      • Thus, if the function is called twice with the same location and random seed, and two times that are very close, then each Pokemon returned the first time should have a large possibility of being returned the second time
    • If the function is called twice with the same time and random seed, and two nearby locations, then any Pokemon that are near both locations should be returned both times
    • The Pokemon should be somewhat evenly distributed across the "world" (the coordinate plane).
      • The Pokemon should be distributed such that at any location and time, the probability of finding exactly n nearby Pokemon of any type is (0.5)^(n+1)
      • Thus, there is a 50% chance of finding no Pokemon at all, a 25% chance of finding exactly 1, a 12.5% chance of finding exactly two, etc.
      • Your algorithm should be capable of returning up to 10 nearby Pokemon, but is allowed to return more, as long as it follows the right probability distribution
  • Sandbox question: I want a requirement to be that the algorithm can't simply generate all of the Pokemon in the world and then just return the nearby ones, but I don't know how to formally state this. I had some fleeting thoughts about O(1) memory usage, but that method could strictly speaking have O(1) memory usage if the world is a constant size (which I'm pretty sure it is).

Might this make a good challenge? That would fit in with the premise, and might produce some interesting algorithms.

For the sake of making this challenge somewhat reasonable, the list of possible Pokemon and their probabilities of appearing will be small:

  • Weedle: 60%
  • Charmander: 30%
  • Blastoise: 10%

Scoring

This is part of what I need help with in the sandbox. How should I distinguish two entries that both meet all of the requirements?


Thanks for reading this far! I know this question isn't nearly ready to be a real challenge. At the very least, it need more specific requirements. But I figured I'd post what I currently have in the sandbox to see if it's worth continuing with. I've never posted or participated in a PPCG challenge before, and I'm sure that's obvious, but hopefully with your help, I can refine this to the point of being a legitimate challenge.

| |
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG, and thanks for using the sandbox! :) Currently I'm afraid your question is rather underspecified. You need to define "nearby" as well as describe how Pokemon should be distributed, as otherwise I could just put 6 weedles, 3 charmanders and a blastoise on the north pole for some time, then swap them to the south pole, etc. You could put a time constraint on the code to try to limit the whole world generation problem, but to do that you'd probably need a reference implementation. Personally, I think code-golf is likely the best scoring method. \$\endgroup\$ – FryAmTheEggman Jul 22 '16 at 15:25
  • \$\begingroup\$ I was imagining this challenge would be very difficult and require a somewhat complex answer, which is why I didn't initially tag it as code golf. But after thinking about it for a little while, I came up with a rather simple solution that isn't as interesting as I thought it would be. So maybe code golf is a better tag. As for you other remarks, I'll get to work editing the answer to make it less ambiguous. \$\endgroup\$ – ItsTimmy Jul 22 '16 at 15:39
  • \$\begingroup\$ 1. Does "the usual euclidean distance" mean in the 3D embedding of the globe whose surface is parameterised by the input coordinates? Or have you decided to simplify by ignoring the fact that real Pokémon Go takes place on a round planet? 2. What does "as long as it follows the right probability distribution" mean if you curtail the probability distribution? What happens to the probability from the tail? \$\endgroup\$ – Peter Taylor Jul 22 '16 at 21:43
  • \$\begingroup\$ @PeterTaylor: I have answered both of your questions by editing my post. Thanks for the feedback! \$\endgroup\$ – ItsTimmy Jul 22 '16 at 21:53
1
\$\begingroup\$

Punch Buggy Probabilities

A popular game among children in the USA is "punch buggy", and as with every such game, there are many variations. The one we'll consider for this challenge goes like this:

  • The moment anyone sees a Volkswagon Beetle (the "buggy"), participants may punch each other (usually in the shoulder or upper arm).
  • A punch must be accompanied by "punch buggy <color>!", where <color> is the color of the VW Beetle (red, green, black, gray, yellow, etc.).
  • Whoever makes contact first gets priority (and for this challenge, there are no ties).
  • Once person A punches person B, B cannot punch A back (usually accomplished by saying "no punch back!").
  • Punches may occur between any pair of participants (for this challenge, every pair of participants).

The challenge

Assuming all possible punching configurations among n people are equally likely to happen, what is the probability of any particular punching configuration? To put it another way, for each distinct punching configuration, how many ways can it occur?

Rules

  • Input is a single positive integer greater than 1.
  • Output must be one of the following: A) a list of decimals, B) a list of fractions (simplified or not), or C) a list of counts. META: Should I allow these lists to be unordered, or should I require that they be associated with punching configurations somehow? I'm leaning towards the former since it seems like it'd be a headache to figure out how to specify the latter and it would likely be an extra task that doesn't really have anything to do with the core problem.
  • Standard rules apply, and standard loopholes are banned.

Test cases

Input
Output A
Output B
Output C

2
1.0
2/2
2

3
0.75 0.25
3/4 1/4
3 1

Explanation of input 2: With only two people, there are exactly two possible ways: either A punches B or B punches A. These are equivalent, so the probability is 1.0, the fraction is 2/2, and the count is 2.

Explanation of input 3: There are two distinct punching configurations: A -> B -> C, A -> C; A -> B -> C -> A. The latter has only two varieties (the other is A -> C -> B -> A) and the former has six, since there are three choices for the person who punches two others and then two choices for the remaining pair. Thus, the probabilities are 0.75 and 0.25, the fractions are 3/4 and 1/4, and the counts are 3 and 1.

META

  • I want to add 4 to the test cases, and I think I'm gonna need help on it since I'm having a hard time counting all 2^6 = 64 possibilities correctly.
  • Any clarifications/corrections?
| |
\$\endgroup\$
1
\$\begingroup\$

Teh Scrolling Codez

In many movies, computer often appear to be scrolling through some code. We should automate this process to make it easier. Your job is to write code that displays to a graphical console a scrolling view of its own source code. You have two options...


You may horizontally scroll the source as HTML's Marquee.

You also may vertically scroll through the source as if the source is code is on a cylinder, and only a fixed number of lines can be displayed


Sandbox Questions

Should this be a code golf or pop-con. Pop-con's could result in more visually pleasing solutions. or [tag:popularity contest]

| |
\$\endgroup\$
  • \$\begingroup\$ I'm wondering how you vertically scroll source code that's one line. \$\endgroup\$ – feersum Jul 28 '16 at 1:17
  • \$\begingroup\$ SIngle line source code is permitted. That is why it may make more sense to scroll it horizontally @feersum \$\endgroup\$ – Rohan Jhunjhunwala Jul 28 '16 at 2:13
  • \$\begingroup\$ A quine in a loop and rely on the console having finite height? \$\endgroup\$ – Peter Taylor Jul 28 '16 at 8:07
  • \$\begingroup\$ Yeah that could work \$\endgroup\$ – Rohan Jhunjhunwala Jul 28 '16 at 12:18
  • \$\begingroup\$ @PeterTaylor ^^ \$\endgroup\$ – Rohan Jhunjhunwala Jul 28 '16 at 12:18
  • \$\begingroup\$ @PeterTaylor do you have an opinion on what tag should be used? \$\endgroup\$ – Rohan Jhunjhunwala Jul 28 '16 at 12:21
  • 1
    \$\begingroup\$ I suspect that this applies and that it's not an interesting question, although I personally don't find quines interesting so I'm not the best person to comment on that. \$\endgroup\$ – Peter Taylor Jul 28 '16 at 13:32
  • \$\begingroup\$ but F() in and of itself is an interesting challenge. @PeterTaylor \$\endgroup\$ – Rohan Jhunjhunwala Jul 28 '16 at 15:37
  • \$\begingroup\$ F(P) is while(true) print P. That's not an interesting challenge in any language I know. \$\endgroup\$ – Peter Taylor Jul 28 '16 at 16:10
  • \$\begingroup\$ @PeterTaylor than I think I should ban console output, and require graphical output \$\endgroup\$ – Rohan Jhunjhunwala Jul 28 '16 at 16:12
  • \$\begingroup\$ thus F(P) becomes while(true){print(sectionOf(p))move(p)}; \$\endgroup\$ – Rohan Jhunjhunwala Jul 28 '16 at 16:13
1
\$\begingroup\$

Autonomous Vehicle

I need a brain for my self-driving car. Something that will take still frames from the front-facing camera and give the navigation system commands. Obviously, if my car is driving me somewhere, I don't want to stop. However, I also don't want to:

  1. Kill someone
  2. Die

Knowing myself, we can assume that:

  • At the speed I drive, hitting the curb or otherwise leaving the road will kill me and thus violate Don't #2
  • With my luck, running a stop light, will violate Don't #1 or #2 or both

  • Also hitting a pedestrian (or another car) violates Don't #1 (and possibly #2)

Input

The program/function should take an image as input. How it does this is flexible.

Output

The program/function should output one of these commands; ideally, one of the commands that doesn't result in one of the Don'ts being violated.

╔═════════╤═══════════════════════════════════════════════╗
║ Command │ Navigational Outcome                          ║
╠═════════╪═══════════════════════════════════════════════╣
║ Forward │ No course correction, continue straight ahead ║
╟─────────┼───────────────────────────────────────────────╢
║ Left    │ Veer left                                     ║
╟─────────┼───────────────────────────────────────────────╢
║ Right   │ Veer right                                    ║
╟─────────┼───────────────────────────────────────────────╢
║ Stop    │ Screech to a grinding halt                    ║
╚═════════╧═══════════════════════════════════════════════╝

Specifications

  • Take an image as input in someway
  • Output a command [ Forward, Left, Right, Stop ]
    • Commands can be aliased as [ 0, 1, 2, 3 ] respectively
    • Returning one valid command and no invalid commands is sufficient to pass a test
    • Stop is only valid iff every other command would violate one of the Don'ts
  • Rules for valid commands:
    • No running stop lights
    • No running over people
    • No running into vehicles
    • No running off the road
    • If a command does not violate any of the above, then it is valid
  • Program/Function must be deterministic

Scoring

Lowest score wins! The scoring function is:

  • ( # of Bytes ) / ( Number of Passed Tests )

For example, a 450 byte Python solution that passes 2 test cases earns a score of 450 / 2 or 225.


Test Cases

  1. Valid Commands: Forward enter image description here

  2. Valid Commands: Left, Right

    • Straight ahead there are pedestrians crossing

enter image description here

  1. Valid Commands: Forward, Right enter image description here

  2. Valid Commands: Forward enter image description here

  3. Valid Commands: Left, Right enter image description here

  4. Valid Commands: Stop enter image description here

| |
\$\endgroup\$
  • \$\begingroup\$ I like this challenge. However, I don't see any test cases for lights. I also think that the test case for pedestrians is pretty bad. Also, realize that people might be using the text on the images (the road labels) to determine orientation, so make sure you're ok with that. I'd also recommend more test cases. Your current set is a good example set, but not comprehensive enough for testing IMO. \$\endgroup\$ – Nathan Merrill Jul 30 '16 at 1:19
  • 1
    \$\begingroup\$ will all testcases be available? if so i would determine the output by the value of the pixel in the top-left corner. \$\endgroup\$ – KarlKastor Jul 30 '16 at 19:47
1
\$\begingroup\$

Embed a graph into the Rado graph

The Rado graph is an infinite undirected graph whose vertices are labelled with natural numbers {0, 1, 2, ...}.

The edge (i,j) with i<j is in the graph whenever the binary expansion of j has a 1 in its ith place. Here, place values are counted from the end, with the 0'th place being the least significant bit. In terms of bitshifts, this means (j>>i)&1==1.

enter image description here

The Rado graph is universal in that any finite graph is a subgraph of it. This means that any finite graph can be embedded in the Rado graph: to each vertex of the finite graph, assign a distinct vertex of the Rado graph so that any two vertices of the original graph have an edge if and only if the corresponding vertices of the Rado graph have an edge.

Your task is to output such an embedding for a finite graph given as input.

TODO: Lots of stuff

| |
\$\endgroup\$
  • \$\begingroup\$ Lovely challenge :). Is there a known algorithm to find the embedding? If so, might it be worth linking to it with a spoiler warning? \$\endgroup\$ – Martin Ender Jul 31 '16 at 10:05
  • \$\begingroup\$ 1. It would be more accurate to say that this is one of several constructions of the Rado graph, and to state that answers are required to work with this construction in particular. 2. The statement of universality is incorrect. It should say induced subgraph rather than subgraph. 3. I assume that by "an embedding" you mean a mapping from vertices of the input graph to vertices of this construction of the Rado graph, but it would be good to make that explicit. 4. @MartinEnder, there's a greedy algorithm described in Wikipedia. \$\endgroup\$ – Peter Taylor Jul 31 '16 at 20:02
1
\$\begingroup\$

Draw Concentric Squarephabets

Challenge

Write a program or function that, given an input integer n, outputs a concentric squarephabet of size n×n.

A concentric squarephabet is an ASCII-art square of concentric rings, where the outside ring of characters are As, the second Bs, the third Cs, etc. For example, a 25×25 squarephabet looks like this:

AAAAAAAAAAAAAAAAAAAAAAAAA
ABBBBBBBBBBBBBBBBBBBBBBBA
ABCCCCCCCCCCCCCCCCCCCCCBA
ABCDDDDDDDDDDDDDDDDDDDCBA
ABCDEEEEEEEEEEEEEEEEEDCBA
ABCDEFFFFFFFFFFFFFFFEDCBA
ABCDEFGGGGGGGGGGGGGFEDCBA
ABCDEFGHHHHHHHHHHHGFEDCBA
ABCDEFGHIIIIIIIIIHGFEDCBA
ABCDEFGHIJJJJJJJIHGFEDCBA
ABCDEFGHIJKKKKKJIHGFEDCBA
ABCDEFGHIJKLLLKJIHGFEDCBA
ABCDEFGHIJKLMLKJIHGFEDCBA
ABCDEFGHIJKLLLKJIHGFEDCBA
ABCDEFGHIJKKKKKJIHGFEDCBA
ABCDEFGHIJJJJJJJIHGFEDCBA
ABCDEFGHIIIIIIIIIHGFEDCBA
ABCDEFGHHHHHHHHHHHGFEDCBA
ABCDEFGGGGGGGGGGGGGFEDCBA
ABCDEFFFFFFFFFFFFFFFEDCBA
ABCDEEEEEEEEEEEEEEEEEDCBA
ABCDDDDDDDDDDDDDDDDDDDCBA
ABCCCCCCCCCCCCCCCCCCCCCBA
ABBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAA

(and yes I typed that by hand ☺)

If the input is an even number, the centre of the squarephabet will be a 2×2 square instead of a single letter. For example, for input 8:

AAAAAAAA
ABBBBBBA
ABCCCCBA
ABCDDCBA
ABCDDCBA
ABCCCCBA
ABBBBBBA
AAAAAAAA

Specification

  • Standard loopholes are forbidden.
  • The input to your program or function will never be less than 1 or greater than 52 (26×2). This means you do not have to deal with letters after Z.
  • You may output uppercase or lowercase letters, but you must be consistent in your choice.

Test Cases

Format:

Input
Output

Test cases:

1
A

2
AA
AA

3
AAA
ABA
AAA

10
AAAAAAAAAA
ABBBBBBBBA
ABCCCCCCBA
ABCDDDDCBA
ABCDEEDCBA
ABCDEEDCBA
ABCDDDDCBA
ABCCCCCCBA
ABBBBBBBBA
AAAAAAAAAA

25
AAAAAAAAAAAAAAAAAAAAAAAAA
ABBBBBBBBBBBBBBBBBBBBBBBA
ABCCCCCCCCCCCCCCCCCCCCCBA
ABCDDDDDDDDDDDDDDDDDDDCBA
ABCDEEEEEEEEEEEEEEEEEDCBA
ABCDEFFFFFFFFFFFFFFFEDCBA
ABCDEFGGGGGGGGGGGGGFEDCBA
ABCDEFGHHHHHHHHHHHGFEDCBA
ABCDEFGHIIIIIIIIIHGFEDCBA
ABCDEFGHIJJJJJJJIHGFEDCBA
ABCDEFGHIJKKKKKJIHGFEDCBA
ABCDEFGHIJKLLLKJIHGFEDCBA
ABCDEFGHIJKLMLKJIHGFEDCBA
ABCDEFGHIJKLLLKJIHGFEDCBA
ABCDEFGHIJKKKKKJIHGFEDCBA
ABCDEFGHIJJJJJJJIHGFEDCBA
ABCDEFGHIIIIIIIIIHGFEDCBA
ABCDEFGHHHHHHHHHHHGFEDCBA
ABCDEFGGGGGGGGGGGGGFEDCBA
ABCDEFFFFFFFFFFFFFFFEDCBA
ABCDEEEEEEEEEEEEEEEEEDCBA
ABCDDDDDDDDDDDDDDDDDDDCBA
ABCCCCCCCCCCCCCCCCCCCCCBA
ABBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAA

52
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
ABCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBA
ABCDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDCBA
ABCDEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEDCBA
ABCDEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEDCBA
ABCDEFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGFEDCBA
ABCDEFGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGFEDCBA
ABCDEFGHIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIHGFEDCBA
ABCDEFGHIJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIHGFEDCBA
ABCDEFGHIJKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKJIHGFEDCBA
ABCDEFGHIJKLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLKJIHGFEDCBA
ABCDEFGHIJKLMMMMMMMMMMMMMMMMMMMMMMMMMMMMLKJIHGFEDCBA
ABCDEFGHIJKLMNNNNNNNNNNNNNNNNNNNNNNNNNNMLKJIHGFEDCBA
ABCDEFGHIJKLMNOOOOOOOOOOOOOOOOOOOOOOOONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPPPPPPPPPPPPPPPPPPPPPPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQQQQQQQQQQQQQQQQQQQQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRRRRRRRRRRRRRRRRRRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSSSSSSSSSSSSSSSSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTTTTTTTTTTTTTTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUUUUUUUUUUUUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVVVVVVVVVVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVWWWWWWWWVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVWXXXXXXWVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVWXYYYYXWVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVWXYZZYXWVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVWXYYYYXWVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVWXXXXXXWVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVWWWWWWWWVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUVVVVVVVVVVUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTUUUUUUUUUUUUTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSTTTTTTTTTTTTTTSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRSSSSSSSSSSSSSSSSRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQRRRRRRRRRRRRRRRRRRQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPQQQQQQQQQQQQQQQQQQQQPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOPPPPPPPPPPPPPPPPPPPPPPONMLKJIHGFEDCBA
ABCDEFGHIJKLMNOOOOOOOOOOOOOOOOOOOOOOOONMLKJIHGFEDCBA
ABCDEFGHIJKLMNNNNNNNNNNNNNNNNNNNNNNNNNNMLKJIHGFEDCBA
ABCDEFGHIJKLMMMMMMMMMMMMMMMMMMMMMMMMMMMMLKJIHGFEDCBA
ABCDEFGHIJKLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLKJIHGFEDCBA
ABCDEFGHIJKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKJIHGFEDCBA
ABCDEFGHIJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIHGFEDCBA
ABCDEFGHIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIHGFEDCBA
ABCDEFGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGFEDCBA
ABCDEFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGFEDCBA
ABCDEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEDCBA
ABCDEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEDCBA
ABCDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDCBA
ABCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBA
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Scoring

This is , so shortest answer wins. Good luck!

| |
\$\endgroup\$
  • 7
    \$\begingroup\$ We're getting slightly into idea-milking territory here. While this isn't a bad idea, a lot of similar challenges in short succession tend to lose interest and popularity fast so you might want to think twice whether you want to post this any time soon. That said, the construction seems simple enough that I'm pretty sure it's been done before. For instance this challenge requires the exact same computation at the core: codegolf.stackexchange.com/q/57845/8478 (although yours probably allows for other approaches, too). \$\endgroup\$ – Martin Ender Aug 1 '16 at 16:31
1
\$\begingroup\$

A meander is a self-avoiding closed curve which intersects a line a number of times.

Your task is, given a self-avoiding walk on a lattice/grid, produce a meander a la the following:

Input

{{{3, 4}}, {1, 2}, {2, 6}, {6, 7}, {7, 3}, {3, 4}, {4, 8}, {8, 12}, {12, 11}, {11, 10}, {10, 9}, {9, 5}, {5, 1}}

Output

enter image description here

or similar.

Test cases:

Inputs

a={{{3, 5}}, {{1, 2}, {2, 3}, {3, 8}, {8, 9}, {9, 4}, {4, 5}, {5, 10}, {10, 15}, {15, 14}, {14, 13}, {13, 8}, {8, 7}, {7, 12}, {12, 11}, {11, 6}, {6, 1}}}
b={{{3, 6}}, {{1, 2}, {2, 8}, {8, 9}, {9, 3}, {3, 4}, {4, 10}, {10, 11}, {11, 5}, {5, 6}, {6, 12}, {12, 18}, {18, 17}, {17, 16}, {16, 10}, {10, 9}, {9, 15}, {15, 14}, {14, 13}, {13, 7}, {7, 1}}

Output

In the above examples, the numbers correspond to a grid, bottom to top, left to right, so 1 is bottom-left, and 18 on a 3*6 grid is top-right. The orientation of your grid doesn't have to follow this order: it can have any desired orientation.

You can assume dimensions of the grid are given at the begining of the input, as per the obove examples.

Feel free to use either pre-existing images - eg

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

or generate your own. This is Code Golf, so the shortest answer in bytes wins.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm still not clear how the points relate the the final image. For the pre-existing images, can we use them at no bytes cost? Is the code for loading them free? \$\endgroup\$ – xnor Aug 4 '16 at 10:44
  • \$\begingroup\$ @xnor I think you are right - it is not clear as it stands - think I will leave it on the back-burner for the moment. \$\endgroup\$ – martin Aug 4 '16 at 12:31
1
\$\begingroup\$

THIS A QUESTION IN PROGRESS

ASCII Art converter

see ASCII Art on Esolangs

Your task is to take input of a brainf*** program and output its equivalent ASCII art program. Your challenge: You may not use the following symbols in your program: \ / - | _ # Standard loopholes not allowed...

This is a so shortest answer in bytes wins

OR

ACII Art Interpreter

Your task is to create an interpreter for the ASCII art language. ASCII Art is a variant of brainf*** where characters are instead ASCII art figures 5 lines tall.

< looks like

 /
/
\
 \

> looks like

\
 \
 /
/

+ looks like

  |
  |
-----
  |
  |

- looks like

-----

[ looks like

____
|
|
|
|___

] looks like

____
   |
   |
   |
___|

. looks like

##
##

, looks like

##
##
_|

Characters that are less than 5 characters tall may be placed anywhere within the top line and bottom line of input.

____________________ top line
     \
      \
      /
     /
        <--- gap because this char is only 5 characters tall
_____________________bottom line

There may be any amount of white space between characters. Also characters can be "nested" in each other, as long as they do not touch. EG

____ |  ##
|    |  ##
|  -----_|
|    |
|___ |

is perfectly valid

Your code should not allow improperly formatted ASCII art, and should print to Standard error. For example, the following code should not work

\
 \
  |
  |
  |____

This is a , so the shortest answer in bytes wins!
Additional tags:

| |
\$\endgroup\$
  • \$\begingroup\$ What is the winning criterion (is it codegolf, popularty contest, anything else...), and what is the font to use? \$\endgroup\$ – TuxCrafting Aug 3 '16 at 17:06
  • \$\begingroup\$ @TùxCräftîñg By font, what do you mean - the ASCII art page on esolangs depicts what each and every symbol should look like \$\endgroup\$ – vikarjramun Aug 3 '16 at 17:31
  • \$\begingroup\$ Nevermind, I haven't seen this part \$\endgroup\$ – TuxCrafting Aug 3 '16 at 17:39
  • \$\begingroup\$ Welcome to PPCG and thanks for using the sandbox! Unfortunately, this is basically a dupe of this challenge with a do X without Y bit tacked on, so I don't think this will be received well. I'm not really sure if there is a way to salvage your intent, here, but I recommend trying something different. Best of luck! \$\endgroup\$ – FryAmTheEggman Aug 3 '16 at 17:45
  • 1
    \$\begingroup\$ 1. If at all possible, posts should be self-contained. The Esolangs page you link to might change or disappear. 2. You should specify how the commands should be chained (horizontally, vertically or something else), how they should be aligned, and how much whitespace has to separate them. 3. In my opinion, forbidding those characters doesn't make the challenge more interesting. \$\endgroup\$ – Dennis Aug 3 '16 at 17:49
  • \$\begingroup\$ @FryAmTheEggman Except my challenge is meant to convert only brainf*** code \$\endgroup\$ – vikarjramun Aug 3 '16 at 17:49
  • \$\begingroup\$ I'm afraid that isn't nearly enough to make it not a duplicate, in my opinion. However, Dennis brings up a potentially interesting point, you may be able to salvage this by also requiring that the code be "formatted" a certain way. I also agree with the rest of the advice Dennis gave you, and I think you should address them before deciding on what else to do. \$\endgroup\$ – FryAmTheEggman Aug 3 '16 at 17:52
  • \$\begingroup\$ What if I change it to a ASCII art interpreter \$\endgroup\$ – vikarjramun Aug 3 '16 at 17:57
1
\$\begingroup\$

Your job is to take an input like below:

Hello, world!

π is cool!

and output it as a series of <kbd>.

Every character, including enter and space get their own <kbd> HTML element, like so:

Hello,SPACEworld!NEWLINE

OPT + PSPACEisSPACEcool!

Other characters like space and newline that are invisible and typeable (so no option, command, control, function, escape, delete, arrow keys, etc.) are all uppercase, like SPACE and NEWLINE. OPT is an exception because it is used to create new characters. The code for these characters are:

<kbd>SPACE</kbd> <kbd>NEWLINE</kbd>

Special characters needing to be typed using option use the following format OPT + P instead of π. The following code is used for these:

<kbd><kbd>OPT</kbd> + <kbd>P</kbd></kbd>

The same applies to characters that are typed using OPT + SHIFT + K instead of .

We're assuming this is a QWERTY layout computer.

Here are the available option keys:

Option keys

Any of the orange keys are not allowed in this.

Here are the OPT + SHIFT keys:

Option shift keys

| |
\$\endgroup\$
  • 5
    \$\begingroup\$ +1 for well laid out challenge -1 for being mac specific \$\endgroup\$ – Rohan Jhunjhunwala Aug 9 '16 at 19:33
  • \$\begingroup\$ @RohanJhunjhunwala It's not technically Mac-specific, but rather uses the same shortcut keys to type special characters as a Mac. \$\endgroup\$ – haykam Aug 9 '16 at 19:35
  • 1
    \$\begingroup\$ Yeah, Ina all seriousness here have an upvote, It does seem like targetting the opt key may be somewhat confusing for some S̶a̶n̶e̶ pc users. \$\endgroup\$ – Rohan Jhunjhunwala Aug 9 '16 at 19:39
  • 1
    \$\begingroup\$ For each letter you check which of the three character sets it is in then add some fixed strings to it. It doesn't seem to me like there is much interesting stuff to do in there? I'm not sure this adds much to the other keyboard focused challenges that we have. \$\endgroup\$ – FryAmTheEggman Aug 9 '16 at 20:23
  • \$\begingroup\$ Do all of those characters even have Unicode codepoints? \$\endgroup\$ – Peter Taylor Aug 10 '16 at 5:31
1
\$\begingroup\$

Find the Watermark

At the moment, I don't have time to outline this properly. The idea is simple: Find the watermark in an image. The implementation, however, is obviously not simple. Since watermarks can have a variety of characteristics, I'd like to admit a variety of answer styles and make it a . Some ideas for the output format:

  • Return coordinates of the (centre|corner(s)?) of the watermark
  • Return a line in some form (e.g., endpoints or equation) that runs through the watermark
  • Return an image that contains only a mask matching the watermark

Input, obviously, would be an image containing a watermark. Images without watermarks are not valid input; as such, submissions do not need to handle them in any special way.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ I fear that this is far too vague, and probably too difficult. \$\endgroup\$ – Joe Aug 21 '16 at 2:10
  • \$\begingroup\$ Maybe a test-battery tag? \$\endgroup\$ – Rohan Jhunjhunwala Aug 21 '16 at 2:19
  • 1
    \$\begingroup\$ Yes, seeing the proposed test cases would give a much better idea of whether this is realistic. \$\endgroup\$ – trichoplax Aug 21 '16 at 7:40
  • \$\begingroup\$ I hereby encourage any member of the community to take over this challenge. I have no experience with graphical I/O, and I don't foresee myself gaining any in the near future. I doubt that I can write a reasonable spec; also, I'm just not that interested in it anymore. \$\endgroup\$ – Joe Sep 5 '16 at 20:37
1
\$\begingroup\$

whispering and SHOUTING

Typing in all caps on the internet is often called "shouting". For the sake of this challenge, I'll call typing in all-lowercase "whispering".

The challenge

Write a complete program that can be run in two different ways: whispering and shouting. The "whispering" version of the program must be written in all-lowercase characters, and it should print whisper to STDOUT. The "shouting" version of the program will print SHOUT. The shouting version must be the exact same program as the whispering version, but with all lowercase letters replaced by the uppercase version of the letter. Everything else must be identical.

Rules

  • No standard loopholes
  • This is , so shortest program in bytes wins!
| |
\$\endgroup\$
  • \$\begingroup\$ Is shortest program in bytes? \$\endgroup\$ – Buffer Over Read Aug 21 '16 at 2:46
  • \$\begingroup\$ Yes, I'll clarify that \$\endgroup\$ – Daniel M. Aug 21 '16 at 2:46
  • \$\begingroup\$ Though I'm not too sure if I want to keep the restriction of not containing the words because it feels kind of arbitrary and that isn't the point of the challenge \$\endgroup\$ – Daniel M. Aug 21 '16 at 3:52
  • \$\begingroup\$ It may be a "Do X without Y" question, which could be bad if not done carefully. \$\endgroup\$ – Buffer Over Read Aug 21 '16 at 3:53
  • \$\begingroup\$ @ColdGolf The difference between this and a do X without Y is that this challenge focuses on actually doing the X (a non-trivial task) instead of focusing on not using Y. Still, I think I'll get rid of the restriction because a) I'd like to focus more on the X and b) the restriction is trivial to circumvent (simply use concatenation) \$\endgroup\$ – Daniel M. Aug 21 '16 at 3:59
  • 1
    \$\begingroup\$ What about characters that don't have a case? Or characters that have more than two cases? Is the program restricted to ASCII? \$\endgroup\$ – FryAmTheEggman Aug 21 '16 at 4:13
  • \$\begingroup\$ @FryAmTheEggman characters without a case don't have to change. What character has more than 2 cases? And it's whatever encoding the program uses. \$\endgroup\$ – Daniel M. Aug 21 '16 at 11:54
  • \$\begingroup\$ Sigma has three total variants. Not restricting this to ASCII makes it seem rather odd. Couldn't a language totally avoid the problem by writing the program in caseless characters and then checking like A > 65? Additionally, some characters (i.e. small caps) look like they should have lower case variants, but don't AFAIK. What standard of considering things lower case should we follow? Without restricting or clarifying this, I think this is too unclear. \$\endgroup\$ – FryAmTheEggman Aug 21 '16 at 13:31
1
\$\begingroup\$

Switching lines

Let's say you have a string of text:

Hello, World! Today is a
most glorious day. In fact,
it's another day. Woohoo!

This string has three lines. We can call them lines 1, 2, and 3. (Or, if you prefer zero-indexing, lines 0, 1, and 2. I'll be using one-indexing to describe this challenge.)

Let's also say we have a mapping of line numbers to line numbers, such as 1 => 2, 3 => 1, 2 => 3. We will interpret this mapping as a method of "switching" lines with each other; the first rule switches line 1 with line 2, then line 3 with line 1, then line 2 with line 3. This would make the string look like, with intermediate steps:

Rule: (initial)
1. Hello, World! Today is a
2. most glorious day. In fact,
3. it's another day. Woohoo!

Rule: 1 => 2
2. most glorious day. In fact,
1. Hello, World! Today is a
3. it's another day. Woohoo!

Rule: 3 => 1
2. most glorious day. In fact,
3. it's another day. Woohoo!
1. Hello, World! Today is a

Rule: 2 => 3
3. it's another day. Woohoo!
2. most glorious day. In fact,
1. Hello, World! Today is a

Notice how the rule describes lines to be switched, not merely lines in that index. So each line has a permanent, associated line number.

Any rule such as 1 => 1 is effectively a no-operation.

Objective Given a list of numbers in any convenient format (e.g. an array of pairs of integers, a list like A B\nC D, a list of numbers, etc.) and a non-empty string of text, perform the action described above.


Meta

is it a good idea to do line identity instead of line locations?

| |
\$\endgroup\$
  • \$\begingroup\$ So the requirements are 1) number the lines; 2) apply the permutation which results from composing a series of simple swap permutations, each of which must be interpreted in the light of the previous ones? The lines really seem to be superfluous: the core of the question is the permutations, surely? \$\endgroup\$ – Peter Taylor Aug 27 '16 at 19:13
  • \$\begingroup\$ @PeterTaylor I suppose that's true. It would certainly simplify the questions. \$\endgroup\$ – Conor O'Brien Aug 27 '16 at 19:26
1
\$\begingroup\$

Tweetable Video

This challenge is inspired by the Encode Images into Tweets challenge, extending the idea to now attempt to compress video into a series of "tweet" sized messages where the number of tweets == number frames of the video.

The competition is to compress 450 frames of video into 450 (or less) tweets of 140 charactes ( 114.97 bytes per tweet, total max 51737 bytes).

Original frames as Video, as PNG images [Sandbox note: Higher quality version will be uploaded soon]

Reference solution frames as Video [Sandbox note: Reference solution will be expanded once challenge changes stabilized]

Rules:

These rules are the based from rules in Encode Images into Tweets modified to accommodate multiple frames that will yield the resultant video.

  1. You must write a program that will communicate via std in/out based on the communication protocol defined below, ultimately producing a series of tweets that will, when fed back to your program, produce image frames of the video.
  2. The text created for each 'Tweet' by the program must be at most 140 characters long and must only contain characters whose code points are in the range of 32-126, inclusive.
  3. The source video will be 450 frames of Big Buck Bunny. Frames can be downloaded here
  4. Frames will be width 320 pixels and height 240 pixels @ 24 bit RGB, each channel having 8 bit precision.
  5. Your program should be able to compress other video sources at same resolution.
  6. Your program can use external libraries and files, but cannot require an internet connection or a connection to other computers.
  7. The decoding process cannot access or contain the original images in any way. (Clarification use of corpus images is allowed as long as these images do not contain direct or manipulated original image frames)
  8. Use of video codecs or existing libraries that perform video compression are not allowed. This is to encourage experimentation and originality rather than simply calling libraries. Note that use of static image compressors/ libraries are allowed.
  9. Standard Loopholes are forbidden.

Communication Protocol

  1. All communication is via std in/out.
  2. The controller program will launch your program with no command line arguments.
  3. The controller will either initiate a one of the following sequences commanding to your program and expecting results.

Note the sequences are described below in the following format:

<Comms direction from controller perspective>, <seq number>: <Transmitted Data> - <Information> 

For Encoding of the frames:

Output, 1: ENCODE\n - Indicating that the controller will be sending frames for your program to compress.
Output, 2: <number of frames>\n - String indicating number of frames. i.e. 450
Output, 3: <number of bytes for image data>\n - String indicating number of bytes of the current image data. e.g. 32145
Output, 4: <image data> - sequence of bytes of length defined in output line 3. The is the image data. The image data is a 24 bit image in PNG format
Repeat from output seq number 3 for the number of frames in output seq number 2.
Input, 1: <Tweet>\n - encoded image data. upto 140 characters, whose code points are in the range of 32-126, inclusive. A zero sized tweet will indicate end of all tweets.
Repeat from input line 1 for 1 to up to the number of frames in output seq number 2. Note a zero sized tweet will indicate end of all tweets.
Output, 5: END\n - Indicating that all processing has finished and your program should quit gracefully.

For Decoding of the frames:

Output, 1: DECODE\n - Indicating that the controller will be sending tweets for your program to decompress.
Output, 2: <number of tweets>\n - String indicating number of tweets. i.e. 450
Output, 3: <Tweet>\n - encoded image data. upto 140 characters, whose code points are in the range of 32-126
Input, 1: <number image frames decoded>\n - String indicating number of image frames that have been decoded as a result of the provided tweet. If 0 then no images have been decoded for this tweet.
Input, 2: <number of bytes for image data>\n - String indicating number of bytes of the current image data. e.g. 32145.
Input, 3: <image data> - sequence of bytes of length defined in input line 2. The is the image data. The image data is a 24 bit image in PNG format. 
Repeat from input seq number 2 for the number of frames in input seq number 1.
Repeat from output seq number 3 for the number of tweets in output seq number 2.
Output, 4: END\n - Indicating that all processing has finished and your program should quit gracefully.
  1. Your program will be restart between the encoding and decoding phases.

Scoring

As an attempt to model the human visual system in a simplistic manner, JPEG quality levels are used as an analogue. Each frame will be compressed to a JPEG using quality levels 0.01 to 1.0 in 0.01 increments. The PSNR of these JPEG compressed versions are calculated and added into a data structure. Additionally, each frame will be resized by half and the JPEG encoding and PSNR calculations performed and added to the data structure. The resizing and calculating will repeat until a single pixel is left.

The result of which will be a scoring continuum of visual 'quality' from low (single color frame) to High (near-identical to original).

Thus, scoring will be objective by means of the following formula:

JPEG_QUALITY_LEVEL_PSNR = a pre-computed data multi dimensional structure consisting of the
                          PSNR for incremental JPEG quality levels for each image frame of
                          the video. The entries into this structure for each frame is such
                          that higher indecies are deemed to be of more similar to the
                          original.

Score = SUM of (index of closest matching entry in JPEG_QUALITY_LEVEL_PSNR for given
                original frame and given PSNR of decoded frame)

Controller

[Sandbox note: Controller is to be created]

Refrence Solution

[Sandbox note: Reference is to be created once question stabilizes]

Sandbox Questions

Ok, so this is my first question ever posed to codegolf and I am very keen to get feedback on how to better present the challenge.

Some areas where I would like specific feed back is the objective scoring mechanism... i purposely avoided direct PSNR as the score as it is very limited for scoring video quality, being biased toward blurry images, however other algorithms are too complex or not defined. So as a compromise I am using JPEG compression as an analogue for the Human Visual System. Effectively matching a given solutions output frame to original frame PSNR to a JPEG compressed, at a given quality level) version's PSNR and using that match's index in sorted JPEG quality order as input for the score.

Is the protocol clear enough? if not what would be a better way to present it?

| |
\$\endgroup\$
  • \$\begingroup\$ "I introduced it so that solutions that take all the frames then perform processing over all the frames would be at a clear advantage over those solutions than work over a much shorter frame period." I'm not seeing it. If I process all of the frames then the first frame will probably use a lot of tweets and the subsequent ones fewer, so I'll be penalised for the first frame. \$\endgroup\$ – Peter Taylor Sep 21 '16 at 9:25
  • \$\begingroup\$ @PeterTaylor Indeed, that is the point i am ?trying? to make, In the fantasy world where video by tweets is a feature desired by users, having to wait until all the tweets are received before playing the video would be very annoying. So this part of the scoring is to give those solutions that return frames quicker in response to provided tweet(s) an advantage. I am thinking that it may be not that "interesting" or "fun" to have this modifier. I think i shall remove it unless some people think it has some worth. \$\endgroup\$ – Moogie Sep 21 '16 at 11:23
  • \$\begingroup\$ The point I was trying to make is that the feature of the scoring system seems to me to penalise the approach which you say it's trying to promote. \$\endgroup\$ – Peter Taylor Sep 21 '16 at 11:28
  • \$\begingroup\$ oh i apologize, i think i misunderstood. Yes, in the example you have given it will penalize that solution, however it would be less penalized than a solution that waited for all tweets, but more penalized than a solution that immediately gives an image frame after each tweet. i.e. the fantasy user would have to wait longer than if the solution produced images after each tweet. Hmm, given the confusion i will remove the modifer as it will be difficult to tune the "negative" effect as to not completely favour immediate frames vs better quality frames. \$\endgroup\$ – Moogie Sep 21 '16 at 11:42
1
\$\begingroup\$

Interpret MSF-!

Because there aren't enough "Interpret X" challenges.

MiniStringFuck (or MSF-) is a brainfuck derivate made by @ErikTheGolfer, with two commands, operating on one cell:

InstructionAction                                                                               
+               Increment the memory cell. If it reaches 256, wrap to 0.
.                Output the character in the cell.                                      

or a bad-looking table:

Instruction, Action
+, Increment the memory cell. If it reaches 256, wrap to 0.
., Output the character in the cell.

Task

Your task is to, given a string of MSF- code, containing only printable ASCII characters, output what it would print.

The string may have other characters than + and .. Treat them as NOPs

Example

++++++++++++++++++++++++++++++++++++++++++++++++.+.+.+.+.+.+.+.+.+.
++++++++++++++++++++++++++++++++++++++++++++++++.                    Set cell to 48 (0) and output
                                                 +.+.+.+.+.+.+.+.+.  Keep adding and outputting until 57 (9)

Test Cases

+++++++++++++++++++++++++++++++++.+.+. -> !"#
++++++++++++++++++++++++++++++++++++++++++++++++.+.+.+.+.+.+.+.+.+. -> 0123456789
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+. -> ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ -> (no output)
| |
\$\endgroup\$
  • \$\begingroup\$ Will the input string ever contain other characters? If so, should they be treated as NOP/comments? \$\endgroup\$ – Geobits Sep 22 '16 at 14:16
  • \$\begingroup\$ @Geobits Yes and yes. \$\endgroup\$ – acrolith Sep 22 '16 at 15:39
  • 1
    \$\begingroup\$ This is basically "Parse unary numbers", and as such I think it's a duplicate of codegolf.stackexchange.com/q/76756/194 \$\endgroup\$ – Peter Taylor Sep 22 '16 at 16:20
1
\$\begingroup\$

Priority to the right

Your task is to regulate traffic on a crossroads. There are 4 roads coming from north, east, south and west.

The input is a string representing the upcoming traffic on each road. For example, NNNWS indicates there is a total of 5 cars: three at the north, one at the west and one at the south. The order has no importance here, NNNWS is equivalent to WNNSN.

You must output the order in which the cars should go, using the priority to the right rule: cars coming from the south must let cars coming from east go first, east gives way to north, north gives way to west and west gives way to south.

For example, with the input NNNWS, the south car should go first, then the west car, then the 3 north cars. The output should then be SWNNN.

There are some indecidable cases, for example NS or NNWSE : you should then output the string stuck.

Test cases

N => N
NW => WN
NWS => SWN
SNW => SWN
SSSSS => SSSSS
ENNNNES => NNNNEES
NS => stuck
NNWSE => stuck
| |
\$\endgroup\$
1
\$\begingroup\$

golf.ko - Kernel module golf

A Linux-specific challenge.

Implement a Linux kernel module which printks Hello world upon loading, in some compiled language.


Source file, linker scripts and command lines, Makefile content (if any) are all counted towards the byte score.

You may expect kernel version to be 4.1 or 4.4.

The kernel is assumed to be running. It's built, not cleaned source code is assumed to reside in /usr/src/linux. In addition you may expect the system to be Debian and to have working DKMS.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ Maybe can be a catalog. \$\endgroup\$ – Vi. Sep 30 '16 at 13:18
  • \$\begingroup\$ What does it mean for a kernel module to "print"? \$\endgroup\$ – Peter Taylor Sep 30 '16 at 18:00
  • \$\begingroup\$ Issue behaviour similar to printk kernel API function in C. Output message to logs, to console, to /proc/kmsg. Shall definition what exactly is a printk be included? Obviously user is expected to call the function inside kernel, not re-implement printk. \$\endgroup\$ – Vi. Oct 2 '16 at 18:29
  • 1
    \$\begingroup\$ I see: "printks" just looks like a typo, it isn't really one. That could be clearer if you wrote "printks", and clearer still if you link to a man page or other documentation. But if you're requiring use of that library, you can pretty much rule out answers in languages other than C and maybe Rust (since what other languages will have bindings for it?), and I wouldn't be surprised if there's nothing interesting left to golf and you just get one answer. \$\endgroup\$ – Peter Taylor Oct 3 '16 at 11:49
  • \$\begingroup\$ @PeterTaylor, Maybe just exclude printk requirement and require just some code derived from posted source code to be executed? Or just the endless loop (it should be doable in almost any language, is API-agnostic and is observable)? \$\endgroup\$ – Vi. Oct 3 '16 at 23:32
1
\$\begingroup\$

Random Quine

(something related to languages?)

You are to write N programs in N langauges (at least 2) that satify the following properties:

  1. For each program P, the program P must produce an output O that is equal to a random program Q that you wrote, including P.
  2. No two programs P and Q may be equal.

Let's say you have two programs, ABCD in language Bar and 1234 in language Baz. Then, ABCD must produce each of ABCD and 1234 with nonzero (but not necessarily equal) probability. Similarly, 1234 must output ABCD or 1234 with nonzero chance. Note that the chances do not have to be same for each program.

| |
\$\endgroup\$
  • \$\begingroup\$ Higher N being winning doesn't seem to be viable on it's own as I think this could be done essentially forever. Will it be something like total length of all Ps divided by N? \$\endgroup\$ – FryAmTheEggman Oct 5 '16 at 22:35
  • \$\begingroup\$ 1. On clarity: it's not clear what the requirements are for which programs each P must produce with non-zero probability. All of them? At least two different ones? ("At least one" would satisfy the stated properties, but not the explanation in the example). 2. On boringness: the programs can just be identical apart from an integer or string literal which they ignore when executing and replace at random when outputting. So a generalised quine of half of the random challenges would meet spec. \$\endgroup\$ – Peter Taylor Oct 6 '16 at 7:28
1
\$\begingroup\$

Introduction

The challenge is to determine if two complex lines intersect.

Challenge

Given two lines made up of multiple straight line segments determine if the lines cross at any point.

Input can be in the format of you choice that takes a series of [x,y] coordinates. All coordinates will be integers (positive or negative)

Output will be truthy if the lines cross and falsey if they don't cross.

There will be no coincidental points and no segment of one line will terminate at a point touching the other line (there will be a clean cross of line segments if the case is truthy).

This is code golf so shortest answer wins

Example Input and Output

For the examples formats are given as

Line 1: [[X1,Y1],[X2,Y2]...,[Xn,Yn]] Line 2: [[X1,Y1],[X2,Y2]...,[Xn,Yn]]

Examples

Line 1: [[0,0],[1,1]] Line 2: [[0,1],[1,0]] = TRUE

Line 1: [[2,2],[1,0],[0,2]] Line 2: [[0,1],[1,1]] = TRUE

Line 1: [[1,3],[2,9],[3,6],[4,7],[5,4],[6,1]] Line 2: [[2,6],[3,5],[5,2]] = FALSE

Line 1: [[0,6],[3,8],[5,5],[8,5]] Line 2: [[0,4],[3,7],[5,4],[7,6]] = TRUE

Line 1: [[2,2],[3,2]] Line 2: [[1,1],[10,4]] = FALSE

enter image description here

Please let me know your thoughts, first puzzle.

| |
\$\endgroup\$
  • \$\begingroup\$ What about the case where one of the line segments "touches" another. That is: one of the end points of a line is on the other line. Would that be considered "crossing" or not? \$\endgroup\$ – DarthRubik Oct 6 '16 at 23:49
  • \$\begingroup\$ @DarthRubik tried to clarify, don't need to handle that case. \$\endgroup\$ – gtwebb Oct 6 '16 at 23:55
  • \$\begingroup\$ All of the test cases have x increasing strictly monotonically. Is this guaranteed, or could line segments be vertical or even loop back? If you don't guarantee that input will avoid those situations, please add test cases to cover them. \$\endgroup\$ – Peter Taylor Oct 9 '16 at 16:11
1
\$\begingroup\$

Raytracing/Raycasting

Here is a 256*256 heightmap. Your challenge is to render it, in minecraft-style blocks, using some form of raytracing.

enter image description here

Fundamental Definitions And Clarifications

These are all straightforward and fairly obvious but I'm being explicit so that what follows is (ideally) unambiguous.

  • Let each pixel represent 1x1 metre, for ease of thought.
  • This image is a top-down view. The bottom-left pixel of the image in screen space is at [0,0,0] in world space. The bottom-right pixel of the image in screen space is at [255,0,0] (i.e. the next full tile to the right would be anchored at [256,0,0]). The Z-axis increases away from us in world space so the top-left pixel is at [0,0,255] and the top-right-pixel is at [255,0,255].
  • As you are looking down to the floor at the moment, you have positive height and the vector from your eye to the image points in the direction of [0,-1,0], so the camera which corresponds to the above image has a world-space coordinate of something like [128,300,128].
  • It shouldn't really matter, but let's take the red channel as holding the height. A red channel value of foo puts that pixel at y=foo. The tallest possible pixel would have world coordinate [x,255,z] with 0<=x,z<256.

Aesthetic Definitions

  • Each pixel effectively represents a tower some number of 1x1x1 solid cubes. The edges of these blocks should be rendered sharply at 90-degree angles. If you were to convert this scene to triangles, each normal would be along one of the major axes. You can think of blocks having end-caps on their top (which is the floor, to us), and walls are extruded between neighbouring blocks as required. There are no holes in the rendered surface. You can assume all renderings will be from above (extra implied geometry below the floor doesn't matter).
  • As well as the heightmap, the world contains one camera and one light source. The light casts hard shadows, so every rendered pixel will require two ray casts. Light falloff is inverse-square. You may optionally gamma-correct the result.
  • Pixels on a surface which receive no light should be black. Pixels of rays which do not hit any surface should be magenta: rgb=(255,0,255).

Input Parameters

  • The camera is defined by position P=[px,py,pz], a T=[tx,ty,tz] target point, and a field of view FOV. It renders WIDTH x HEIGHT images such that the target point appears in the centre.
  • The camera is orientated such that it yaws, then pitches, but does not roll.
  • The light is at position L=[lx,ly,lz] and casts light uniformly in all directions.
  • You solution must be posted with reference image rendered with P=[80,256,0], T=[128,50,200], L=[256,300,128], WIDTH=400, HEIGHT=300 and FOV=45 degrees.
  • (As reference images emerge I might tweak these parameters.)

Free Parameters

  • The light can be any colour and brightness you like but the colour and brightness must be inputs to the program.
  • Likewise, the colour/material of the surface may be anything you like (except magenta, which is for revealing holes) but these colour/material parameters must be an adjustable input to the program.
  • Use any lighting/shader model you like.
  • Use fog or other effects if you like. Different submissions are likely to vary considerably in size, so there's room to play a bit.

Criteria

  • You must post code which can be run as-is, with the specified reference parameters and all your free parameters included.
  • You can take the heightmap image as hardcoded in a representation of your choice and this does not count towards your golf score. You must post the code which converts an image to your preferred format. This script should either run using common Linux command-line tools, or over an online service. This script should not assume that heightmaps are square.
  • The output of raw pixel data can be in any format you like (e.g. [[r,g,b],...] BUT you must provide a second script, not counted towards your golf score, which turns your program's raw output into some standard image format such as PNG. This script should either run using common Linux command-line tools, or over an online service.
  • You must post the final image produced by this method, as well as the code which produces the output which produces the image.

In a nutshell, the above specifies that your output is reproducible, with different parameters and heightmap images as desired.

The winner will be chosen a few weeks from now, as the shortest code which conforms to the above aesthetic specifications (e.g. shadows, no holes, etc) and which gives end-to-end reproducible results.

| |
\$\endgroup\$
  • \$\begingroup\$ Maybe include a sample output? \$\endgroup\$ – Steven H. Oct 7 '16 at 18:10
  • \$\begingroup\$ My own attempt at this is part of a larger, more complex project, it'll be a while :-) In the meantime I was curious if others would find a simplified version of the problem a bit more fun. \$\endgroup\$ – spraff Oct 7 '16 at 19:42
  • \$\begingroup\$ Must run, so will expand on this later, if not within 48 hours then ping me. There are some subtleties with respect to offsets (are blocks centred?) The stuff about fog etc is wasted space, because in code-golf no-one will spend bytes on it, so remove it to KISS. I strongly advise before posting to get a test output which two independent programs agree on. \$\endgroup\$ – Peter Taylor Oct 8 '16 at 8:07
  • \$\begingroup\$ 1. The subtlety I promised to expand on: does "The bottom-left pixel of the image in screen space is at [0,0,0] in world space" mean that the pixel corresponds to the voxel whose coordinates range from (0,0,0) to (1,1,1) or the voxel whose coordinates range from (-0.5, -0.5, -0.5) to (0.5, 0.5, 0.5)? 2. Also, what does "The camera is orientated such that it yaws, then pitches, but does not roll" mean? Perhaps it could be better expressed by giving the initial up, forward, right vectors and then saying around which axes it rotates. \$\endgroup\$ – Peter Taylor Oct 9 '16 at 16:09
1
\$\begingroup\$

A simple but fun code golf challenge!

Given positive integer n

create a 2 dimensional matrix where each location is filled with it's xy index (starting from the top left).

For example:

Your grid should look like: input: 2

00 10
01 11

input: 3

00 10 20
01 11 21
02 12 22

Once the grid is created, randomly fill each index. This can be with an 'x' or any other way to denote a spot has been filled

A complete simulation looks like:

input: 3

x x x
x x x
x x x

O O O
O O O
O O O

You can use whatever character you want to fill in each location.

Extra points if you use a GUI and use black squares to fill it in

You should only fill a spot in once so the number of times you fill should be n^2. (So no randomly filling spots until they are all filled you have to check!)

You can refresh the grid however you want. i.e print the grid, make a new line, print again... You can use a timer. However you want to do it to illustrate each step. You only need to refresh when you are filling not when you are populating the grid.

An example simulation looks like this:

input: 2

00 10
01 11

randomed 01

00 10
XX 11

randomed 11

00 10
XX XX

randomed 11
re-roll
randomed 01
re-roll
randomed 00

XX 10
XX XX

randomed 10

XX XX
XX XX

Complete

Do not display your randomed numbers, the output should tell me which were randomed.

Have fun!

| |
\$\endgroup\$
1
30 31
32
33 34
96

You must log in to answer this question.

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