559
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

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

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

4199 Answers 4199

1
47 48
49
50 51
140
1
\$\begingroup\$

Continue the sequence

As we all know, there are a lot of integer sequences in the world. What if we could create one program to figure out the next few items in any given sequence? That would be pretty cool, right? Well, I'm pretty sure we can't create a program that does every sequence, but we can at least do most of the simple ones.

Challenge

Your challenge is to create a program or function that takes in 5 integers in any reasonable format (array, string, separate arguments, etc.), and returns/outputs the next 5 integers in the sequence.

Rules

  • Your submission must be deterministic; that is, the output should be the same every time for the same input.
  • You may not use a built-in for determining the next items. (cough Mathematica cough)

Scoring

To score a submission:

  1. Take the value of each single output integer minus the expected output.
  2. Take the square root of the absolute value of each of these.
  3. Take the average of the result and add one.
  4. Multiply your byte count by this number.

For example, if the only test case were 1,2,3,4,5 => 6,7,8,9,10, and your 15-byte submission outputs 6,7,8,10,6, your score would be:

1,2. abs(6 - 6) = 0, sqrt(0) = 0
     abs(7 - 7) = 0, sqrt(0) = 0
     abs(8 - 8) = 0, sqrt(0) = 0
     abs(10 - 9) = 1, sqrt(1) = 1
     abs(7 - 10) = 4, sqrt(4) = 2
3.   0 + 0 + 0 + 1 + 2 = 3
     3 / 5 = 0.6; 0.6 + 1 = 1.6
4.   15 bytes * 1.6 = 24

Thus, your score would be 24.

Lowest score wins.

Test cases

2,2,2,2,2 => 2,2,2,2,2
1,2,3,4,5 => 6,7,8,9,10
109,117,125,133,141 => 149,157,165,173,181
1,2,4,8,16 => 32,64,128,256,512
1,10,100,1000,10000 => 100000,1000000,10000000,100000000,1000000000
1,2,3,5,8 => 13,21,34,55,89
2,1,3,4,7 => 11,18,29,47,76
1,3,6,10,15 => 21,28,36,45,55
1,4,9,16,25 => 36,49,64,81,100
8,7,6,5,4 => 3,2,1,0,-1
1,0,1,0,1 => 0,1,0,1,0
1,2,3,2,1 => 2,3,2,1,2
512,256,128,64,32 => 16,8,4,2,1
1,11,111,1111,11111 => 111111,1111111,11111111,111111111,1111111111
1,21,321,4321,54321 => 654321,7654321,87654321,987654321,10987654321
1,2,6,24,120 => 720,5040,40320,362880,3628800

I will create a GitHub Gist with all of the test cases before posting.

Sandbox questions

Currently, I'm looking for suggestions for:

  • a better name
  • more tags
  • more sequences

Feel free to post any other questions/notes you have.

1 This will be replaced with the actual number of test cases when this is posted.

\$\endgroup\$
15
  • \$\begingroup\$ Why the 100 byte limit? \$\endgroup\$
    – nimi
    Feb 10, 2016 at 20:45
  • \$\begingroup\$ @nimi The goal is to correctly predict as many sequences as possible while keeping the code fairly short. Does 100 bytes sound too short? \$\endgroup\$ Feb 10, 2016 at 20:47
  • 2
    \$\begingroup\$ ... well, 100 bytes of Pyth aren't 100 bytes of Java. Wordy languages will be quite handicapped. \$\endgroup\$
    – nimi
    Feb 10, 2016 at 20:51
  • \$\begingroup\$ @nimi True. How might I be able to fix this? \$\endgroup\$ Feb 10, 2016 at 20:51
  • \$\begingroup\$ Classical bonuses (although discouraged now) work better when relative compared to absolute. Maybe something like byte count * (2 - percentage solved), i.e. 2x bytes if 0%, 1x bytes if 100%, lowest score wins. But somehow we must prevent trivial answers like outputting the constant string 0 0 0 0 0 for 2x9 = 18 bytes. \$\endgroup\$
    – nimi
    Feb 10, 2016 at 21:00
  • 5
    \$\begingroup\$ Sequences are pretty arbitrary, so I'm having trouble seeing how this could go well. I get the feeling most submissions will just end up hardcoding in a set number of patterns, eg geometric progression, polynomial interpolation, and ignore ones which are too complex, eg Golomb. Also, standard loophole, but it might be worth mentioning explicitly that looking up things on, eg OEIS, is not okay. \$\endgroup\$
    – Sp3000
    Feb 10, 2016 at 21:48
  • \$\begingroup\$ @Sp3000 You have a good point there. What would you think about A) choosing a select number of sequence types, B) choosing a select number of types and making it code-golf, or C) just choosing a single type to focus on? \$\endgroup\$ Feb 11, 2016 at 16:11
  • \$\begingroup\$ I had a think about this, and I think what this challenge might need is 1) A fairly large test-battery covering a large variety of sequence types (e.g. OEIS), and 2) A tweak to the scoring system which takes into account how far off a number is (since getting 0 points for a guess that's just off by 1 seems a bit harsh). Just a thought though. \$\endgroup\$
    – Sp3000
    Feb 14, 2016 at 4:11
  • \$\begingroup\$ Regarding your options, I'm not a great fan of C since it changes the challenge completely, and might need dupe checking. There's no real need to limit the number of sequence types I think, as long as there's an incentive to be close with the guess rather than dead on. \$\endgroup\$
    – Sp3000
    Feb 14, 2016 at 4:12
  • \$\begingroup\$ Perhaps make it a [test-battery] with lots of test cases. That seems like the best way to score these types of languages. You may also want to disallow built-ins as I know Mathematica has a built-in to do this \$\endgroup\$
    – Downgoat
    Feb 15, 2016 at 17:09
  • \$\begingroup\$ @Sp3000 Yes, those are some very good thoughts. This is now a test-battery challenge, and the new scoring algorithm takes into account both the byte-count and the average of the sqrt-distances of the outputs. Does this seem like a decent way to score this challenge? \$\endgroup\$ Feb 15, 2016 at 18:02
  • \$\begingroup\$ @Downgoat This is now a test-battery challenge, and built-ins have been banned. Thanks! \$\endgroup\$ Feb 15, 2016 at 18:02
  • \$\begingroup\$ @nimi The scoring system has been completely rewritten. \$\endgroup\$ Feb 15, 2016 at 18:06
  • \$\begingroup\$ With respect to limiting the types of sequence, you need to be careful not to turn it into a dupe of codegolf.stackexchange.com/q/3485/194 \$\endgroup\$ Feb 15, 2016 at 19:09
  • \$\begingroup\$ @PeterTaylor Thanks, I'll keep that in mind. \$\endgroup\$ Feb 15, 2016 at 19:48
1
\$\begingroup\$

Compress by Replacement

You are to take an input string, and then turn it into another string with a list of replacements which would turn this new string into the input string. The catch is that you must output the smallest such alternate string + list of replacements you can.

The input string will be restricted to the following characters (Please note there is a space at the end and that semicolons are not allowed):

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:<=>?@[]^_`{|}~ 

The way the output is formatted is

CompressedString;tofind;toreplace;tofind;toreplace;...

An example output is 111222;1;abcd;2;efgh which outputs abcdabcdabcdefghefghefgh

The replacement rules are applied in the order they are shown in the output to avoid ambiguity.

Therefore, if one were to input abcdabcdabcdefghefghefgh (which has a length of 24). Then the output would be 111222;1;abcd;2;efgh with a length of 20 which is the shortest possible output for this input

Some other notes:

  • The replacement rules are restricted to the same character set that the input has. This means that if the input contained every possible letter except for the character h, then your replacement rule would only work if the tofind part of the rule is h
  • There may be situations where the input string is the shortest possible output, this is fine
  • The program doesn't have to be computationally efficient, as long as it does calculate the correct answer when it finishes, then it is valid
  • There are also occasionally multiple correct answers, any solution which has the smallest possible count is valid and you only need to output one solution, not all the valid solutions
  • The semicolons are included in the character count for the output

Some test cases:

'abcdabcdabcdabcdefghefghefghefgh' -> '11110000;1;abcd;0;efgh' or '00001111;1;efgh;0;abcd'
'this is a test. this is a test.' -> '0 0;0;this is a test.'
'there is no shortening in this one' -> 'there is no shortening in this one'
'01001001010100101010110101010101010110101010' -> '202030321332130;3;222;2;01' or '22331131210113;3;212;2;010' or '22212233230132;3;121;2;010' or '223233133301132;3;21;2;010' or '222323133310133;3;12;2;010' or '020203031332132;3;222;2;10'

This is codegolf, so shortest answer in bytes wins

Sandbox notes:

  • This takes a long time to brute force for anything longer than 40 characters with repeated substrings, so it may take a while for brute forced solutions to verify they are correct. Because of this, I was thinking this question might be better proposed as a "best algorithm" kind of puzzle to see who can make the best algorithm. What do you think?
  • Should I allow people to choose what delimiter is used to separate the output? Ideally what would happen is that they would just say 'I am assuming that , is not used and it is my delimeter for the output'.
  • Am I being too strict on the output? The aim was that you are trying to compress it only via replacements, and as a result want to output those replacements as short as you can, which this format is the smallest you can make.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 1. I don't understand what you mean by "The replacement rules are restricted to the same character set that the input has", even with the explanation. 2. A simplified version of this problem is NP-complete, so I'm not sure what "best algorithm" winning criterion you could use. 3. It would be good to have a test case where all optimal answers have a tofind which is more than one character (ensuring that answers solve the problem stated, not just that simplified version). \$\endgroup\$ Feb 17, 2016 at 16:40
  • \$\begingroup\$ Seems possible if you limited to a couple replacements. Otherwise, maybe a code challenge/fastest code version? \$\endgroup\$ Feb 17, 2016 at 18:44
  • \$\begingroup\$ 1. What i mean is, that the rules: 1;abcd;2;efgh for example, must only contain characters which were allowed in the input. So you can't use weird unicode characters or things to replace 2. I'd not heard of the simplified version of this problem. In fact I think that this may be more efficient, because some rules which may be valid in that problem would not be valid due to having to factor in the additional length of the semicolons, and 3. I don't believe I have such a solution available, maybe none exist like that? \$\endgroup\$ Feb 18, 2016 at 4:17
  • \$\begingroup\$ I think algorithm is a no-go from Peter's response since it does seem to be NP complete, maybe I could restrict it to be at most 3 replacements as per Michael Klein's suggestion \$\endgroup\$ Feb 18, 2016 at 4:20
1
\$\begingroup\$

Wring the changes

I want to ring Stedman Doubles, but I'm lazy so I want to get to a particular change and back as quickly as possible.

Change-ringing is essentially an enumeration of permutations of a set of small integers. To make the enumeration ringable, no bell can move more than one step in each permutation. A change therefore consists of some or all of the bells swapping places with adjacent bells.

Consider the case of five bells. Before changes start, the bells are rung in ascending numerical order, known as Rounds, which would be 12345. A typical change would then consist of leaving one bell in the same place while a double swap occurs between the remaining four bells, thus the name "Doubles". The bell that remains in the same place serves to notate the change. Note that this refers to the bell currently in that position, rather than the bell with that number.

In the case of Stedman the full notation is 3.1.5.3.1.3.1.3.5.1.3.1. If you repeat those 12 changes five times you will enumerate 60 changes before returning to Rounds. The first few changes are as follows:

[12345 Rounds]
 21354 (1,2 and 4,5 swap)
 23145 (1,3 and 5,4 swap; 2 was 1st so doesn't move)
 32415 (2,3 and 1,4 swap)
 23451 (3,2 and 1,5 swap; 4 was 3rd so doesn't move)

There are of course 120 permutations of five bells, so in order to access the other 60 changes, or simply for variety, Stedman allows for every sixth change to be altered by a call known as a Single, which causes the two bells currently in position 4 and 5 to stay in the same place instead of exchanging as they would normally do.

A touch is described by a sequence of letters describing whether each sixth change is Plain or a Single. It ends when it returns to Rounds, which need not be after a multiple of six changes, but it may not repeat any change, so 120 is the longest possible length of a touch of Stedman Doubles. For instance, a complete extent of all 120 changes could be rung using the touch PPPPPPPPPSPPPPPPPPPS.

Your challenge is to write a program or function that will calculate the shortest touch that includes a given change. Your input should be the change (you can expect it to be a valid change) as a string, and your output should be (in either order) the touch description (as a string of P and S characters) and also the number of changes (including the final rounds, so up to 120).

The score for this challenge shall be the length of your program, plus the lengths of the touches it finds for the following inputs:

13524
14235
14253
43215
53124

The Batch script @echo 120 PPPPPPPPPSPPPPPPPPPS would therefore score 630.

\$\endgroup\$
3
  • \$\begingroup\$ This could use a little background information. Ideally, the challenge should be self-contained and understandable by somebody who does not know what Stedman Doubles or change ringing is (such as myself). \$\endgroup\$
    – Dennis
    Feb 17, 2016 at 17:04
  • \$\begingroup\$ So in essence, we have a highly structured digraph of 60 vertices (corresponding to the order-60 group generated by P and S, which I assume is A5 but haven't checked); each of the 120 edges is labelled with 12 permutations (and each permutation therefore occurs on 12 edges, but symmetry), and we need to find the shortest cycle from 12345 which includes an edge labelled with the input permutation \$\endgroup\$ Feb 18, 2016 at 12:34
  • \$\begingroup\$ @PeterTaylor Close. You don't need a cycle as long as you reach the input permutation before you reach an edge labelled 12345 (or 12345 is labelled after the input on the same edge), and there are 4 generators as the meaning of P alternates between 42351 and 43152 and S between 42315 and 43125, so the group is generated by P1P2, P1S2, S1P2 and S1S2 (but I don't know what the group looks like, except that (P1P2)^5==I). \$\endgroup\$
    – Neil
    Feb 18, 2016 at 13:14
1
\$\begingroup\$

Implement floating-point square-root with integer addition, subtraction and bit-shifts only

Someone has broken your favourite language! Almost all arithmetic functions are now unusable. You've been left with integer addition, subtraction, bit-shifts (both left and right) and bitwise operators (AND, XOR, OR, NOT) only. If your language doesn't have bit-shifts you may substitute *2^i or /2^i for a cost of i each time. You need to write an efficient square-root function because it's been proven[citation needed] that every useful program uses square-root[dubious-discuss].

Your function will take one number (see format below), calculate its square-root and return the result. The last binary digit may either be consistently rounded down, or rounded to closest.

Rounding down:

...0(0)  ...0
...0(1)  ...0
...1(0)  ...1
...1(1)  ...1

Rounding to closest:

...0(0)  ...0
...0(1)  ...1
...1(0)  ...1
..01(1)  ..10, etc.

Scoring:

  • 1: Copy an integer (any length)
  • 2: Add or Increment
  • 2: Subtract or Decrement
  • 1: Greater-than, Less-than, Equal-to, etc.
  • 1: Check a bit
  • 1: Write a bit
  • 1: Bit-shift (left or right) by 1
  • 2: Bitwise operator (AND, XOR, OR, NOT)
  • n x (code + condition): Do-While
  • n x condition + (n - 1) x code: While (For can be implemented as While)
  • 0 (free): Jump to start or end of loop
  • 0 (free): Jump to start of function
  • 0 (free): Return from function

Since different languages use different number formats, the format used for scoring this challenge is as follows: 8 bits for the exponent, 32 bits for the mantissa. You don't have to use these lengths internally, just assume this is what it is for scoring purposes.

There will be no negative numbers or zero in the input, nor will you have to store a value of 0.0. Since the square root function always produces a number closer to 1, you don't need to worry about overflow or underflow. The Most Significant Bit of the mantissa will always be 1.

  • All floating point numbers will be stored and passed around as two unsigned integers, m and e
  • Bm and Be are the number of bits in m and e respectively
  • The value of the number is given by 2(e-Bm-2Be-1)m or 2^(e-Bm-2^(Be-1))*m
  • In your code Bm must be ≥ 32 and Be must be ≥ 8

The code will be scored assuming that Bm = 32 and Be = 8, so no penalty will be given if your code uses larger values.

 exponent   MSB          mantissa           LSB    decimal
[01111110] [10000000 00000000 00000000 00000000]   0.125
[01111111] [10000000 00000000 00000000 00000000]   0.25
[10000000] [10000000 00000000 00000000 00000000]   0.5
[10000001] [10000000 00000000 00000000 00000000]   1
[10000001] [10100000 00000000 00000000 00000000]   1.25
[10000010] [10000000 00000000 00000000 00000000]   2
[10000010] [11000000 00000000 00000000 00000000]   3
[10000011] [11100000 00000000 00000000 00000000]   7
[10000100] [10000000 00000000 00000000 00000000]   8
[10000100] [10010000 00000000 00000000 00000000]   9

Please include a version number for ease of reference. If you know the name of your method, please include it too, e.g. "Brute force", "Trial and error", etc. Increase the major number if your score changes, otherwise increase the minor number if your score is the same, e.g:

v1.0: Perl, Brute force - 108
v1.1: Perl, Brute force - 108
v1.2: Perl, Brute force - 108
v2.0: Perl, Brute force - 95
v2.1: Perl, Brute force - 95
v3.0: Perl, Brute force - 93

This is not , so you will be scored on the efficiency of your algorithm. If more than one answer is equally efficient, the oldest one will be in the lead. If editing your answer reduces your score, it also resets your time. The time is taken from your last minor version 0.


I'll probably need some fair test values that don't allow tuning for specific numbers.

Thoughts?

\$\endgroup\$
13
  • \$\begingroup\$ The nested superscript/subscript is hard to read. Can you pull out the offset? \$\endgroup\$ Feb 16, 2016 at 13:07
  • \$\begingroup\$ Someone has broken your favourite language \$\endgroup\$
    – wizzwizz4
    Feb 16, 2016 at 15:03
  • \$\begingroup\$ @wizzwizz4 Cute! The difference is that now your job is to fix it afterwards! \$\endgroup\$
    – CJ Dennis
    Feb 17, 2016 at 1:57
  • \$\begingroup\$ Thanks @PeterTaylor. Do you have any other suggestions? Does my scoring seem balanced? Have I forgotten any operations that might be needed? I've never done a fastest-algorithm challenge before so I want to make sure it is good. \$\endgroup\$
    – CJ Dennis
    Feb 17, 2016 at 2:12
  • \$\begingroup\$ Do X without Y challenges are generally frowned upon \$\endgroup\$
    – user45941
    Feb 17, 2016 at 4:01
  • \$\begingroup\$ @Mego This isn't always bad, "Do X without Y" can be good questions. Do you think this challenge isn't "meaty" enough? Please don't pigeon-hole it with a broad generality if you don't have specific gripes. If you think the entire concept is flawed, please clearly explain why. \$\endgroup\$
    – CJ Dennis
    Feb 17, 2016 at 4:22
  • \$\begingroup\$ @CJDennis I never said that I thought the challenge was flawed. I just wanted to point out that challenges of this type are generally frowned upon, and thus you may face some resistance/downvotes with this one. \$\endgroup\$
    – user45941
    Feb 17, 2016 at 4:24
  • \$\begingroup\$ @Mego OK. Understood. This is why I've posted it to the Sandbox first. I've had an upvote and no downvotes so far, and while no-one's said "This is brilliant!" no-one's panned it either. Any suggestions you have for improving it/making it more user friendly are welcome! \$\endgroup\$
    – CJ Dennis
    Feb 17, 2016 at 4:31
  • \$\begingroup\$ Is the unusual exponent bias intentional? What rounding is permitted? It's probably worth explicitly stating that since sqrt is always nearer to one, there's no need to worry about underflow or overflow in the output. \$\endgroup\$ Feb 17, 2016 at 6:53
  • \$\begingroup\$ That floating-point format looks suspiciously like that on the ZX81, which is convenient, as I actually wrote a fast floating point square root for it. If only I could remember it. \$\endgroup\$
    – Neil
    Feb 18, 2016 at 13:29
  • \$\begingroup\$ @PeterTaylor Are you saying the bias is strange because it doesn't have a -1? This is intentional as I believe it will make some methods easier without penalising others. \$\endgroup\$
    – CJ Dennis
    Feb 19, 2016 at 0:48
  • \$\begingroup\$ @Neil The format is based on the Amstrad CPC (but not identical), so I wouldn't be at all surprised if the format was similar or identical to the ZX81 (both using Z80 CPUs). As I remember a lot of software was easily ported between them. \$\endgroup\$
    – CJ Dennis
    Feb 19, 2016 at 0:51
  • \$\begingroup\$ I wasn't thinking it through enough. The -Bm is because of the implicit binary point in the explanation I'm more used to seeing. Ignore that point. \$\endgroup\$ Feb 19, 2016 at 6:39
1
\$\begingroup\$

xkcd's Fast Bogosort

This xkcd comic presents pseudocode for four very bad sorting algorithms: halfhearted merge sort, fast bogosort, job interview quicksort, and panic sort. Because the other three are too easy, impossible to decipher, or a danger to users, you'll be implementing fast bogosort.

Your code will take an array of positive integers in any convenient format, and will return or output the result of fast bogosort as defined below.

Let N be the binary logarithm of the length of the list, rounded to the nearest non-negative integer. Shuffle the list randomly N times. After each shuffle, if the list is fully sorted, return the result.

If no value has yet been returned, return the exact string Kernel Page Fault (Error Code: 2).

The output of your code must match the expected probabilities of this algorithm exactly, but does not need to follow the explicit steps stated.

Test cases

In the format Input -> Output (Probability)

[] -> Kernel Page Fault (Error Code: 2) (1)
[1] -> Kernel Page Fault (Error Code: 2) (1)
[1, 1] -> [1, 1] (1)
[1, 2] -> [1, 2] (1/2)
[1, 2] -> Kernel Page Fault (Error Code: 2) (1/2)
[1, 1, 1] -> [1, 1, 1] (1)
[1, 1, 2] -> [1, 1, 2] (5/9)
[1, 1, 2] -> Kernel Page Fault (Error Code: 2) (4/9)
[3, 2, 1] -> [1, 2, 3] (11/36)
[3, 2, 1] -> Kernel Page Fault (Error Code: 2) (25/36)
[8, 4, 2, 1] -> [1, 2, 4, 8] (47/576)
[8, 4, 2, 1] -> Kernel Page Fault (Error Code: 2) (529/576)
[7, 7, 7, 7, 7, 7, 7, 7] -> [7, 7, 7, 7, 7, 7, 7, 7] (1)

Meta

Any bad math in here? Any other good test cases I should add?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 1. The requirement to "match the expected probabilities of this algorithm exactly" needs to be relaxed slightly because most systems don't have perfect RNGs. 2. If you're allowing built-in sorts, the only interesting part is rounding the logarithm. And that's really the only difference to the bogosort question, so it's quite likely to be closed as a dupe. \$\endgroup\$ Feb 20, 2016 at 10:28
1
\$\begingroup\$

Remove Vowel

There is a word puzzle called Enter Vowel which looks a little like a crossword but the clues are simply the answers with all the vowels removed.

Your task will be to take a solved crossword and turn it back into the Enter Vowel clues. You can assume that the crossword consists of upper case letters, octothorpes and newlines. You can also assume that the crossword will be rectangular and that only octothorpes will appear on its borders.

The first step is of course to obscure the letters. Each letter should be replaced by a space, except those letters that begin a word, which should be replaced by an underline. Each underline is notionally numbered starting from 1.

To the right of the obscured grid you must then provide separate columns of across and down clues, but both sets of clues share the underline numbering, so that the numbers are not consecutive within each list of clues. The clues are simply the original words with the vowels removed.

Example:

###############
###PROGRAMMING#
###U####N######
###Z##CODE#####
###Z###########
#GOLF##########
###E###########
###S###########
###############

becomes

############### ACROSS      DOWN
###_    _     # 1. PRGRMMNG 1. PZZLS
### #### ###### 3. CD       2. ND
### ##_   ##### 4. GLF
### ###########
#_   ##########
### ###########
### ###########
###############

Extra whitespace is permissible as long as the general formatting is adhered to.

This is , so you need to remove as much code as you can.

\$\endgroup\$
4
  • \$\begingroup\$ The example given includes a full border of one line of #s. Can answers assume that this border will always be included? \$\endgroup\$ Feb 22, 2016 at 11:05
  • \$\begingroup\$ @PeterTaylor Unless you can suggest nicer ASCII or Unicode art to represent a crossword, then yes, I think the input should always have the border. \$\endgroup\$
    – Neil
    Feb 22, 2016 at 11:12
  • \$\begingroup\$ Then please make that explicit in the question, because it simplifies the answers. \$\endgroup\$ Feb 22, 2016 at 12:06
  • \$\begingroup\$ @PeterTaylor I also added that it will always be rectangular, because I wasn't sure that was sufficiently obvious. \$\endgroup\$
    – Neil
    Feb 22, 2016 at 13:35
1
\$\begingroup\$

Untangle the footnote labyrinths

enter image description here

Challenge

Your challenge is to create a program or function that untangles footnote labyrinths.

Input

The input will be made up of two parts:

  • A "main" string
  • A list of footnotes in the format (1. Footnote text)

Output

The output should be the "main" string with each footnote mark (represented with superscript tags <sup>1</sup>) replaced with its corresponding footnote. Examples:

This is some sample text.<sup>1</sup>
1. This is a sample footnote.

The "main" string has one footnote <sup>1</sup>; the 1 is replaced with the text of the footnote:

This is some sample text.<sup>This is a sample footnote.</sup>

Here's another one:

This is some sample text.<sup>1</sup>
1. This is a footnote.<sup>2</sup>
2. This is a nested footnote.

This time, the footnote has a footnote mark in it, which should be replaced as well:

This is some sample text.<sup>This is a footnote.<sup>This is a nested footnote.</sup></sup>

One more example:

Welcome to my lair!<sup>8</sup><sup><sup>3</sup></sup>
3. This footnote is not inserted.

Footnote 3 is inserted, but footnote 8 does not exist, so it's not modified:

Welcome to my lair!<sup>8</sup><sup><sup>This footnote is not inserted.</sup></sup>

You may assume:

  • Nested footnotes are not represented as <sup>1<sup>2</sup></sup>; rather as <sup>1</sup><sup><sup>2</sup></sup>.
  • There will be no circular references, i.e. 1. Abc<sup>1</sup> or 1. Abc<sup>2</sup> 2. Xyz<sup>1</sup>
  • The footnote numbers will only be 1 through 9.

You may not assume:

  • The footnote numbers will be consecutive, or in order. 2. Abc 1. Xyz and 9. Qwerty 4. Asdf are both valid.

Test cases

(One or more lines of input, empty line, output. Feel free to suggest a better format.)

This is some sample text.<sup>1</sup>
1. This is a sample footnote.

This is some sample text.<sup>This is a sample footnote.</sup>

_____________________________________________________________________

This is some sample text.<sup>1</sup>
1. This is a footnote.<sup>2</sup>
2. This is a nested footnote.

This is some sample text.<sup>This is a footnote.<sup>This is a nested footnote.</sup></sup>

_____________________________________________________________________

Studies have shown<sup>1</sup> that PPCG users are more likely to accept typos<sup>3</sup> than the correct spelling<sup>4<sup>5</sup></sup>.
1. Studies by an individual research group, not affiliated with PPCG in any way.
3. https://github.com/vihanb/PPCG-Design/pull/50
4. http://strawpoll.me/6847681/r
5. Very comprehensive studies.<sup>1</sup>

Studies have shown<sup>Studies by an individual research group, not affiliated with PPCG in any way.</sup> that PPCG users are more likely to accept typos<sup>https://github.com/vihanb/PPCG-Design/pull/50</sup> than the correct spelling<sup>http://strawpoll.me/6847681/r<sup>Very comprehensive studies.<sup>Studies by an individual research group, not affiliated with PPCG in any way.</sup></sup></sup>.

_____________________________________________________________________

Welcome to my lair!<sup>It's very cozy.</sup>
1. This footnote is not inserted.

Welcome to my lair!<sup>It's very cozy.</sup>

_____________________________________________________________________

Welcome to my lair!<sup>8</sup><sup><sup>3</sup></sup>
3. This footnote is not inserted.

Welcome to my lair!<sup>8</sup><sup><sup>This footnote is not inserted.</sup></sup>

This is code-golf, so shortest code in bytes wins.

\$\endgroup\$
4
  • \$\begingroup\$ Zgarb had a challenge that was either this or the exact opposite transformation. I'll try to look it up later. \$\endgroup\$ Feb 22, 2016 at 17:43
  • \$\begingroup\$ Ah yeah, the opposite. \$\endgroup\$ Feb 22, 2016 at 18:48
  • \$\begingroup\$ @Martin Interesting. Would that have any bearing on this challenge being a duplicate? \$\endgroup\$ Feb 23, 2016 at 2:24
  • \$\begingroup\$ No, it wouldn't. \$\endgroup\$ Feb 23, 2016 at 7:45
1
\$\begingroup\$

How long until a five-card-stud poker winning hand?

Background:

Five card stud is a variant of poker where the player is dealt a hand of five cards from a shoe of multiple standard 52-card decks. This hand is then used for play/scoring, following the table listed below.

{insert chart of poker hands}

We're going to play a variation of this as follows: The dealer selects five cards out of the shoe as the Hand to Beat. The dealer then shuffles all the remaining cards, and deals the player five cards. If the player wins, the game is over, else the player's cards are shuffled back into the shoe and the process repeats. We want to determine the expected number of hands that will need to be dealt before the player has a hand that will beat the dealer.

Challenge:

Given an input of the dealer's full five-card hand, and the number of decks in the original shoe, output the expected number of games before the player will have a hand that beats the dealer's.

Input:

  • A positive integer, 0 < n < 6 representing how many decks are in the shoe.
  • A numerical or string representation of the dealer's full five-card hand. You're allowed to choose the representative encoding, and the input format, but please specify that in your answer. Examples could be 3H 2C KC QH JD for a card-value/suit combination, or assign each card a numerical value from 1 to 52 (such as Ace of Spades = 1, Two of Spades = 2, ... King of Hearts = 52). Your choice.

Output:

  • A single numeric value representing the expected number of hands that need to be dealt before the player is dealt a winning hand.

Examples:

to be expanded

1 "2H 3C 4S 5C 7H" >
5 "22 33 45 17 8" >

Meta Discussion:

Related (abandoned) challenge - Generate random 7-carded poker hand for a given hand type

Since the related challenge isn't exactly a duplicate, I don't think the below apply, but I'll link them here for discussion purposes:
Duplicates with different restrictions or no restrictions
Is it OK to copy a question if the old one is long dead?
Can we make use of abandoned sandbox posts?
Closing old question as duplicate of a new one

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

Traffic Light Simulator 2016

In this challenge, you are in charge of all of the traffic lights in a busy city. It is your goal to move the traffic as efficiently as possible.

Definitions:

City: Everything you control. Contains a 10x10 square grid of intersections. All adjacent intersections are connected via roads, and intersections on an edge have 1 outside connection (2 on corners)

Tick: Measures time. For the first 10,000 ticks, 10 cars will span. The simulation ends after all cars have left the city.

Road: Moves cars from one intersection to another (or an outside connection). Roads have a length (in ticks).

Intersection: 12-way intersection. Connects 4 roads together, and allows cars to move from one road to one of the other 3. Only 1 car per direction can travel through at a time.

Traffic Light: Allows/Prevents cars from crossing an intersection. There are 12 lights (one for each direction) at each intersection. Lights can only be green (allows traffic) or red (prevents traffic). If a light is green, then any intersecting paths must have been red for at least 3 ticks.

Intersecting paths: Paths that cross or meet assuming right-side traffic. The following graph indicates when two paths intersect given your direction and the other lanes' directions.

Your        Left  Right Across
Direction  |L|R|A|L|R|A|L|R|A 
------------------------------
Left       |X   X|X   X|  X X
Straight   |X   X|X X X|X    
Right      |    X|     |X    

Car: Starts at a random outside connection, and travels the shortest path to another random outside connection. After reaching its destination, adds 1.05^(TravelDuration) to your score.

Outside connection: Has a Busyness, and spawns cars. The chance of an outside connection being randomly chosen is Busyness/Sum(Busyness of every connection)

Your goal:

I have provided a controller that will simulate the cars and the cities. You need to provide a function that returns a list of [x,y,Direction] tuples that indicates which lights you would like to toggle. Attempting to turn a green light with intersecting green lights will turn the intersecting lights red, and turn the light green after 3 turns.

After the simulation has run, your score is the sum of all cars' scores, lowest score wins.

\$\endgroup\$
2
  • \$\begingroup\$ Did anything ever come from this? This seems like it could be a fun challenge. \$\endgroup\$
    – nedla2004
    Feb 25, 2018 at 17:18
  • \$\begingroup\$ No. I'm not convinced that there are actually interesting solutions to be had, and the controller isn't trivial to write. If you want to take this challenge, feel free :) \$\endgroup\$ Feb 26, 2018 at 2:16
1
\$\begingroup\$

How Many Laps?

I was at my taekwondo training last night and the first thing we do when we start is a ~5 min jog around the gym to get warmed up. The problem is as follows. We run around the edge of the gym, everyone starting from wherever they like, and everyone jogs at a slightly different speed, so there is a lot of awkward passing as no one wants to have to ruin their flow by changing speed. So i started wondering, how many times will each person be overtaken?

The Question

Given a square of side lengths 15m, and a person starting at each corner of the square, running at speed n (m/s) how many times will each person be passed by someone else during a 5 min jog?

Input/Output

  • Input should take the form of 4 values that represent each persons average running speed( Assume their speed remains constant) accurate to 3 decimal places. The range of the input may be (0,5]. Input may be seperated by commas or spaces i.e 4.123,2.122,3.145,1.445
  • Output should be printed as 4 integers representing the number of times each person was overtaken by someone else, given in the same order as the input was supplied.

Test Cases

The input 1.3334 2.5334 1.1344 2.8531 can be visually represented as follows

1.3334 ------------ 2.5334
   |                   |
   |                   |
   |                   |
   |                   |
   |                   |
 2.8531 ------------ 1.1344 

Each of the numbers in the corner of the square represents a jogger and their speed running in a clockwise direction(Clockwise because of the order of the input). After 5 mins of jogging, how many times will each jogger have been overtaken by everyone else?

The output for this case would be 13 1 14 0 This basically means the first person( top left corner) will be overtaken 13 times. The second person(top right) will be overtaken once. third person(bottom right, and the slowest jogger) will be overtaken 14 times. The fourth person( bottom left, and the fastest) will not be overtaken by anyone, as they are the fastest. Here are some more test cases

  • Input: 5.3334 1.5334 1.5334 0.8531 Output: 0 19 19 28
  • Input: 0.1334 1.5334 2.5334 3.8531 Output: 37 16 6 0

Rules

  • This is code golf, shortest working program in bytes wins
  • Must be a fully working program
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You should really add an example, since this is very hard to imagine in your mind. Also don't forget testcases! \$\endgroup\$
    – Denker
    Feb 25, 2016 at 7:48
  • \$\begingroup\$ Haha yeah i thought someone would say that! I'm currently trying a few ideas as im not sure how to solve this myself yet! Once i have a way, ill ad some test cases \$\endgroup\$
    – SoloKix
    Feb 25, 2016 at 8:16
1
\$\begingroup\$

The broken minus parser

Sam is trying to create a new programming language, but is having a lot of trouble getting the parser right. For example,

4--5

evaluates correctly to 4 - (-5) = 9, but

4-5

is giving a result of -20!

After doing some digging around, Sam realises that their parser's grammar is ambiguous. In fact, it's actually interpreting 4-5 as 4 (-5), multiplication (by juxtaposition) between two numbers!

Here's some example inputs and outputs, to get a feel for what the parser's doing woeful wrong:

Input             Calculation                 Output
7                 7                           7
-7                (-7)                        -7
8-3               8 (-3)                      -24
8--3              8 - (-3)                    11
-8-3              (-8) (-3)                   24
-8--3             (-8) - (-3)                 -5
-4-5-2            (-4) (-5) (-2)              -40
-4--5-2           ((-4) - (-5)) (-2)          -2
-4-5--2           (-4) ((-5) - (-2))          12
-4--5--2          (-4) - (-5) - (-2)          3
1-4-5-9           1 (-4) (-5) (-9)            -180
1-4--5-9          1 ((-4) - (-5)) (-9)        -9
1--4-5--9         (1 - (-4)) ((-5) - (-9))    20
1--4--5--9        1 - (-4) - (-5) - (-9)      19

To be a bit more explicit, here's the rules followed by the parser, in order:

  1. Multiplication by juxtaposition: If possible, split the input into two valid parts a, b such that a is as short as possible. Return evaluate(a) * evaluate(b).

  2. Subtraction: If the input is of the form a-b where a, b are two valid parts, return evaluate(a) - evaluate(b), taking the - such that b is as short as possible.

  3. Unary negation: If the input is of the form -a where a is valid and does not start with a -, return -evaluate(a). In other words, unary negation can only be applied once.

  4. Digit: If the input consists of a single digit, return the corresponding integer.

If an input string fails to satisfy any of the above conditions, it is invalid. For example, the following strings are invalid:

(empty)
-
7-
--7
8---3

The task

Given a valid string consisting of 0123456789-, output the result as interpreted by Sam's broken parser. Invalid input is undefined behaviour. You may assume the usual code golf defaults for input and output, e.g. programs and functions are both okay.

Sandbox notes:

  • I'll work on the algorithm description a bit later so it doesn't sound so much like "just implement this".
  • Will add more test cases later.
  • Should eval-like functions be allowed? I'm not sure how much they'd help here
  • With the current rules, 42 would evaluate to 4*2=8. Would it be preferable to state that input will never have two or more digits in a row?
\$\endgroup\$
3
  • \$\begingroup\$ Doesn't rule 1 already cause 42 to be evaluated as 4*2=8 by having precedence above rule 4? \$\endgroup\$
    – xnor
    Feb 26, 2016 at 5:25
  • \$\begingroup\$ @xnor Ah true, yes it does (updated). I'm still tossing up whether 42 should be a valid test case - I'm wondering if it might be more interesting golfing-wise if you only ever had single digits... \$\endgroup\$
    – Sp3000
    Feb 26, 2016 at 5:34
  • \$\begingroup\$ I think eval-like functions should be allowed because it disallowing doesn't add much to the challenge \$\endgroup\$
    – Downgoat
    Feb 28, 2016 at 2:17
1
\$\begingroup\$

What can I buy in Catan?

Catan is a board game where players collect 5 commodities: brick, lumber, wool, grain and ore.

You can trade commodities in the following ways:

  • you can always sell 4 of one kind to buy 1 of any other kind
  • if you have 3-for-1 trading possibility you can sell 3 of one kind to buy 1 of any other kind
  • if you have a given commodity trading possibility you can sell 2 of the given commodity to buy 1 of any other kind

You can use your commodities to buy 4 things:

  • road costs 1 brick and 1 lumber
  • settlement costs 1 brick, 1 lumber, 1 wool and 1 grain
  • city costs 2 grain and 3 ore
  • development card costs 1 wool, 1 grain and 1 ore

The same costs in matrix form:

 |blwgo
-+-----
r|11
s|1111
c|   23
d|  111

Your task is to find out which of the four things a player could buy given his/her commodities and trading possibilities.

Input

Output

Examples

This is code golf so the shortest entry wins.

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

Transpose a paragraph

For some odd reason I want to transpose paragraphs. The basic idea of a transpose is that this:

a b
c d

Is changed to:

a c
b d

[more on the rules here]

Examples

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer suscipit, arcu
ut facilisis blandit, neque tellus consequat urna, in semper mi purus vel magna.
Nam placerat mauris ac varius dictum. Nunc placerat ipsum et lectus iaculis
feugiat. Aenean eget felis ac purus fermentum dapibus ac nec leo. Vestibulum
convallis euismod metus a gravida. In eu nisl facilisis, accumsan urna a,
consectetur mauris. Integer vitae lectus et justo vestibulum lobortis. Donec
quis erat est. Curabitur pellentesque mi purus, vel posuere nunc volutpat quis.
Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia
Curae; Maecenas ultrices, elit sed finibus euismod, lacus tortor hendrerit
libero, quis auctor risus mi in tortor. Vivamus finibus consectetur est, quis
ultricies metus congue sit amet. Ut non elit libero. Fusce efficitur nec ante ut
tempor. Proin vitae commodo tortor. In aliquam massa a nulla eleifend commodo. 

Lorem      ut         Nam        feugiat.   convallis  consectetu quis       Vestibulum Curae;     libero,    ultricies  tempor.   
ipsum      facilisis  placerat   Aenean     euismod    mauris.    erat       ante       Maecenas   quis       metus      Proin     
dolor      blandit,   mauris     eget       metus      Integer    est.       ipsum      ultrices,  auctor     congue     vitae     
sit        neque      ac         felis      a          vitae      Curabitur  primis     elit       risus      sit        commodo   
amet,      tellus     varius     ac         gravida.   lectus     pellentesq in         sed        mi         amet.      tortor.   
consectetu consequat  dictum.    purus      In         et         mi         faucibus   finibus    in         Ut         In        
adipiscing urna,      Nunc       fermentum  eu         justo      purus,     orci       euismod,   tortor.    non        aliquam   
elit.      in         placerat   dapibus    nisl       vestibulum vel        luctus     lacus      Vivamus    elit       massa     
Integer    semper     ipsum      ac         facilisis, lobortis.  posuere    et         tortor     finibus    libero.    a         
suscipit,  mi         et         nec        accumsan   Donec      nunc       ultrices   hendrerit  consectetu Fusce      nulla     
arcu       purus      lectus     leo.       urna       volutpat   posuere    est,       efficitur  eleifend  
vel        iaculis    Vestibulum a,         quis.      cubilia    quis       nec        commodo.  
\$\endgroup\$
2
  • \$\begingroup\$ Where did "vel" (at the bottom of column 1 in your output) come from? \$\endgroup\$
    – msh210
    Feb 29, 2016 at 6:47
  • \$\begingroup\$ I'm not exactly sure, but I don't (and won't) have time to fix it for a while. 1-2 months min. \$\endgroup\$
    – J Atkin
    Feb 29, 2016 at 21:08
1
\$\begingroup\$

Sort My Youtube Playlist

Help! My playlist is all unsorted! I need to sort it, but I can only move a video to the top or the bottom. I'd like to do this quickly so I need a solution with the minimum amount of moves. But I'm lazy and it seemed like a good fit, so I'm posting it here and now you have to do it! Now, since this is code golf, you have to do it in as few bytes as possible.

Input is a permutation of the values from 1 to n (where n is any number from 1 to ∞). Output is a list of moves that sorts the list. For example for input 1 3 2 4 a valid output would be 2D 3D (second element to bottom, third element to bottom)

Test cases:

Input         Possible Output
1 3 2 4       2D 3D
5 4 3 2 1     4D 3D 2D 1D
\$\endgroup\$
4
  • 3
    \$\begingroup\$ I'd flag as unclear. Input and output specifications? Test cases? Just a description is not enough. \$\endgroup\$
    – user48538
    Feb 29, 2016 at 16:43
  • \$\begingroup\$ I'm having trouble understanding the test cases. No matter which side I try as "bottom", neither one of the outputs seem to sort the inputs. \$\endgroup\$
    – Geobits
    Mar 1, 2016 at 15:16
  • \$\begingroup\$ For the first input, it is 1 3 2 4 1 2 4 3 1 2 3 4 For the second, 5 4 3 2 1 5 4 3 1 2 4 5 3 1 2 4 5 1 2 3 5 1 2 3 4 1 2 3 4 5 \$\endgroup\$ Mar 1, 2016 at 16:10
  • 1
    \$\begingroup\$ 1. "A list of values from 1 to n" without any other mention of n says nothing about whether or not there are duplicates. I think you mean "a permutation of the integers from 1 to n", but that needs to be explicit. 2. The top appears to be index 0 (or 1 in weird languages) and the bottom index n-1, but that needs to be explicit. 3. 2D seems to mean "move the value at index 2 to the bottom": "element 2" is far too easy to interpret as the element with value 2. 4. The first paragraph says "minimum amount of moves", but the second test case doesn't meet that criterion. \$\endgroup\$ Mar 1, 2016 at 21:12
1
\$\begingroup\$

Recompose a series of alternating binary sequences

This is the inverse of Decompose binary into alternating subsequences. The essence of this linked challenge is to convert a decimal integer to binary, split on adjacent 0s or 1s (like 010110001 would become 0101 10 0 01), and convert each subsequence back to decimal.

Let's take a sequence of positive integers in decimal, like

10 21 2 5 1 1 1 1 1 2 1 2 5 1 85 5 1 1 1 5 1 1

And convert each number to binary...

1010 10101 10 101 1 1 1 1 1 10 1 10 101 1 1010101 101 1 1 1 101 1 1

But wait, this is the inverse of the decomposition problem. The original binary representation was split where there were two adjacent 0s or 1s. Hence, if 10101 comes after 1010, then there must have been a leading 0. Adding these in results in this:

1010 010101 10 0101 1 1 1 1 1 10 01 10 0101 1 1010101 101 1 1 1 101 1 1

Which, after concatenation and converting back to decimal, gives 727429805944311 as the final answer.

The Task

Take a sequence of positive integers as input and output a single positive integer after recomposition.

The Details

  • Input may be in a sensible, human-readable format that is convenient for your language. All integers must be in decimal or unary, and no precomputation in the input is allowed.
  • Output must be a single positive integer, in either decimal or unary.

Test Cases

Input                Output
0                    0
1                    1
2                    2
1 1                  3
2 0                  4
5                    5
1 2                  6
1 1 1                7
2 0 0                8
2 1                  9
10                   10
1 2 2                50
1 2 2 0              100
1 1 1 1 10 0 0       1000
2 1 1 2 0 2 0 0 0    10000
1 2 2 1 1 2 2        12914
5 42 10 2 1          371017
\$\endgroup\$
5
  • \$\begingroup\$ "Easily" is a bit (read: very) subjective. Does retina count? Sed? I'd recommend just allowing unary, the problem doesn't seem like it would be easily solved in unary, so it shouldn't make much difference. \$\endgroup\$ Mar 7, 2016 at 16:43
  • \$\begingroup\$ @FryAmTheEggman: Good point. I'll edit both questions to say that. \$\endgroup\$ Mar 7, 2016 at 19:59
  • \$\begingroup\$ Can you edit this so it is comprehensible without reading another question? E.g.: "The original binary representation was split where there were two adjacent 0s or 1s." -- says who? \$\endgroup\$
    – msh210
    Mar 8, 2016 at 6:22
  • \$\begingroup\$ @msh210: How is it now? \$\endgroup\$ Mar 8, 2016 at 9:00
  • \$\begingroup\$ … Much better, thanks. \$\endgroup\$
    – msh210
    Mar 8, 2016 at 13:23
1
\$\begingroup\$

Count the Esolang Puns

| |

This challenge was inspired by this conversation in chat.

Introduction

Yesterday in chat, there was a conversation where several people extensively used esolang puns. @CᴏɴᴏʀO'Bʀɪᴇɴ kept a tally throughout to see who used the most puns. Your job will be to help him out by counting the puns.

Challenge

Your challenge will take several strings as input and output a list of scores. Input can be in a list, separated by newlines, etc. Output can be in any convenient format, in any order. Each string of input will be in the form user : message. Both user and message will only contain printable ASCII characters. You need to count the amount of language puns used in the message and add it to that user's tally. Use this list as the list of languages that count as "pun" languages. You may not read this list from external sources (webpage, file, etc.). In the case of a overlap of languages (ex. example contains the languages example and exam), count all of them (so the example would contain 2 languages). Language names are case insensitive while counting (retina and ReTinA are the same).

Example IO

Input (taken from the actual conversation):

AlexA. : @Mego He may be CJamming things
ConorO'Brien : I'm jelly >:I
GamrCorps : @AlexA. Argh! The Aura from the eclipse burned by Retinas. Good thing it didn't deal too much damage or I would RAGE!!!
ConorO'Brien : The hexagony, I'm losing.

Output:

[["AlexA.", 1], ["Conor'OBrien", 2], ["GamrCorps", 4]]

Meta Note: Ill add more IO when I get back in an hour or so.

\$\endgroup\$
6
  • \$\begingroup\$ So, its basically counting the instances of a substring? \$\endgroup\$ Mar 9, 2016 at 18:38
  • \$\begingroup\$ @NathanMerrill yes, counting the instances of several substrings, and outputting the total amount per person \$\endgroup\$
    – GamrCorps
    Mar 9, 2016 at 18:40
  • \$\begingroup\$ "You may hardcode that list in your program or read that webpage." Unless you're planning on deducting the hard-coded list from the score or similar, this gives an unfair advantage to languages that can read the webpage. \$\endgroup\$ Mar 9, 2016 at 18:41
  • \$\begingroup\$ Also, I'm assuming we should match the language names case-insensitively. \$\endgroup\$ Mar 9, 2016 at 18:46
  • \$\begingroup\$ @AquaTart Yes it should be case insensitive, I updated the post along with removing the ability to read from the web. \$\endgroup\$
    – GamrCorps
    Mar 9, 2016 at 18:48
  • \$\begingroup\$ Isn't most of this challenge compressing the list of languages? \$\endgroup\$
    – lirtosiast
    Mar 11, 2016 at 10:52
1
\$\begingroup\$

ACSII Cell Game

The ASCII Cell Game is a simple game where the player has a grid (5x10) of cells (| |):

_____________________
| | | |X| | | | | | |
---------------------
| | | | | | | | | | |
---------------------
| | | | | | | |X| | |
---------------------
| | | |X| | | | | | |
---------------------
| | | | | | | |X| | |
---------------------

Any cells marked with an X have died, and any cells with an O have been blocked. The object of the game is for the spread of X's to stop. The player inputs a point i.e. 1,5 and the computer places an O there. The Xs spread to all adjacent cells every 2 seconds.


Game Rules:

  1. This is traditional code golf with the shortest in bytes winning. I will test this on my computer.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The specification is not clear. Specify exactly what should happen to display the game board (does it need to update every iteration, or even display at all?); when the game ends (when every square is blocked?); whether players should be prevented from moving in an O or X square, etc. \$\endgroup\$
    – lirtosiast
    Mar 12, 2016 at 0:53
1
\$\begingroup\$

Infinite Hexagony Loops

In this challenge, we will be determining whether or not a restricted-source hexagony program terminates or loops forever.

Input

A hexagony program that contains only the

  • "Flow Control" characters: / | _ | > <

  • the no-op character: .

  • the program terminate character: @

Note that since every memory edge is zero for the duration of every program, there are no conditionals in this restricted source version of the language.

  • The side length of the hexagon may be any natural number.

  • You may assume that inputs are padded with no-op characters to fit the hexagon shape exactly (or you may strip all trailing no-ops as long as you do not change the hexagon size)

  • You may take the input in any reasonable fashion.

  • DESCRIPTIONS OF WHAT EACH OF THE FLOW CONTROL CHARACTERS DO WILL BE COMING SOON. IN THE MEANTIME, LOOK AT THE WIKI PAGE

Output

A truthy value if the program terminates. A falsy value otherwise.

A program "terminates" if the instruction pointer reaches a '@' character.

Test cases

Coming soon.

Scoring

\$\endgroup\$
1
  • \$\begingroup\$ I approve. Especially if there is a hexagony solution \$\endgroup\$ Sep 8, 2016 at 0:07
1
\$\begingroup\$

Zipdeck!

A few years ago I invented a simple card game named "Zip Deck". It's not that much fun for humans, but should be perfect for bots. This contest will be run in Python 3.

Zip Deck rules:

There are N players, and a deck with N*4 cards, numbered 0 to N*4-1. The deck is shuffled (Python's random.shuffle function) and each player is dealt a card. Everyone looks at their card, then, on the count of three, if you believe you have the highest card, say (return) "Zip Deck!"

If you do have the highest card and you said "Zip Deck", you win! You assign floor[C/4] points, divided between the other players any way you'd like, where C is the value of your card.

If either you said "Zip Deck" but don't have the high card, or you do have the high card but didn't say "Zip Deck", you take a penalty of floor[C/4] points (min 1).

The winner is the player with the fewest total points after a set number of rounds (as of now, N2 rounds, but that's subject to change if there are many, many entrants).

What You Do:

Write a bot! A bot is a descendant of the Player class. Your bot should have a function play that takes two parameters, card (the card you're dealt) and info (a dictionary with information about the state of the game). If your bot thinks it has the highest card, it should return an array containing the string "Zip Deck!" and a dictionary showing how it would assign points if it's correct. If you don't assign enough points, your bot will take the remainder; if you assign too many, instead all of the points will be given to your bot that round.

The info dictionary contains the following keys:

  • 'round': The current round, starting with zero. Maybe your bot wants to get more reckless when the game's about to end?
  • 'scores': A dictionary containing every player's current score.
  • 'last': A dictionary showing what everyone was dealt last round and what the bot returned (so an array with either an empty string or "Zip Deck!" plus their point allocation). Useful if you're trying to determine the other players' strategy.

An example info from one of my test runs:

{'scores': {0: 5, 1: 6, 2: 2, 3: 1}, 
'last': {0: [12, ['']], 1: [10, ['Zip Deck!', {2: 2}]], 2: [15, ['Zip Deck!', {1: 3}]], 3: [3, ['Zip Deck!', {1: 0}]]}, 
'round': 3}

Every Player also has two attributes that you can access, my_num (that player's number) and player_count (the total number of players). I've imported random already (naturally); if you want to use any other standard library, just let me know.

class YourBotHere(Player):
    def __init__(self, my_num, player_count):
        super(YourBotHere, self).__init__(my_num, player_count)
    def play(self, card, info):
        # Define your own play function for your class.

        # If you think you're highest, return an array where the first element is the
        # phrase "Zip Deck!", and the second is a dictionary for how you'd assign points
        # if you win.
        # E.g. ["Zip Deck!", {0: 2, 1: 2, 4: 1}]

        # If you don't think you're highest, return an array with one element, the empty
        # string (or anything that's not "Zip Deck!")

        return [""]

class Player(object):
    def __init__(self, my_num, player_count):
        self.my_num = my_num
        self.player_count = player_count

Example bots:

class Rando(Player):
    def __init__(self, my_num, player_count):
        super(Rando, self).__init__(my_num, player_count)
    def play(self, card, info):
        if random.random() > 0.5:
            target = {i for i in range(self.player_count)} - {self.my_num}
            target = random.choice(tuple(target))
            points = card//4
            return ["Zip Deck!", {target: points}]
        else:
            return [""]

class Serpentine(Player):
    # Zigs and zags, trying not to do the same thing too many times in a row.
    def __init__(self, my_num, player_count):
        super(Serpentine, self).__init__(my_num, player_count)
        self.two_back = True
        self.one_back = False
        self.targets = {i for i in range(self.player_count)} - {self.my_num}
    def play(self, card, info):
        if len(self.targets) == 0:
            self.targets = {i for i in range(self.player_count)} - {self.my_num}
        will_call = False
        if self.two_back == self.one_back:
            will_call = not self.two_back
        elif card/(self.player_count*4) > 0.8:
            will_call = True

        self.two_back = self.one_back
        self.one_back = will_call

        if will_call:
            target = self.targets.pop()
            return ["Zip Deck!", {target: card//4}]
        else:
            return [""]

Controller

The controller code can be found on my GitHub (along with most of these instructions again verbatim). [You can also see OrionBot, the one entry I got when I tried to run this competition in class; I'll remove it so that only PPCG bots are in the tournament before this goes live.] Intentionally bad or losing strategies are OK, but bots that attempt to crash the controller/cause an infinite loop will be disallowed, as are bots that collude or cooperate in any way.

Sandbox Concerns

First and most importantly, does everything in the rules write-up make sense? Are there any loopholes I haven't considered?

This game is straightforward enough that the winning strategy might be completely boring, but I don't think it's necessarily obvious that it will be. Also, I would have said that rock-paper-scissors-lizard-spock has a very clear and well-known best strategy in game-theoretic terms, and that challenge still saw a dizzying array of answers.

\$\endgroup\$
7
  • \$\begingroup\$ Hello, welcome to PPCG, and thanks for using the Sandbox! :) From what I can see, this looks alright, but I'd definitely leave it around a while to see what people think. I'd be concerned that the best strategy for calling "Zip Deck" might be random, in particular. Also, this game seems relatively simple, so if you feel like you could probably create a controller that passed the values as strings and allowed more than just python answers. Some other challenges have done that to great success e.g. Good Versus Evil \$\endgroup\$ Apr 4, 2016 at 23:18
  • \$\begingroup\$ Thank you! I'd love to open this up to more than just Python answers, but I haven't worked with the Subprocess. I'll have to spend some time with it to see if I can make it work. \$\endgroup\$ Apr 4, 2016 at 23:52
  • \$\begingroup\$ 1. As far as I can see, the rules don't actually state what values are on the cards. That's quite an important detail. 2. IMO you should restrict to no more than one entry per user and no cooperation between users. \$\endgroup\$ Apr 5, 2016 at 13:26
  • \$\begingroup\$ @PeterTaylor Good catch! I've updated accordingly. (The cards are valued from 0 to N*4-1) I feel like most King of the Hill challenges I've looked at allow players to submit multiple bots, though; has there been a problem with that in the past, beyond the obvious Soviet chess player issues? \$\endgroup\$ Apr 5, 2016 at 17:14
  • \$\begingroup\$ I've got a nice Communicator class in python. That said, I've actually moved away from Python for KoTHs because its slow, so its been a while since I used it, but it should be fairly unbuggy. \$\endgroup\$ Apr 5, 2016 at 17:53
  • \$\begingroup\$ Also, the reason that RPSLS got so many answers is because it was simple and had a pop-culture reference. Its hard making a spec that is simple and easy to read (I'm a terrible example, IMO), and unfortunately, I don't see any pop-cultureness in this challenge. That said, best of luck to your challenge! \$\endgroup\$ Apr 5, 2016 at 18:02
  • \$\begingroup\$ There has been intentional submission of entries which were intended to collude to the benefit of other entries in the past; my proposal is more extreme than any which has been implemented so far, but there have been other KotHs which explicitly prohibited collusion. I'm concerned that with this format where you can choose to whom you want to assign points if you win there is a greater than usual benefit to collusion. \$\endgroup\$ Apr 5, 2016 at 20:40
1
\$\begingroup\$

A Simple Card Game

Take 2 standard decks of cards, and 4 players. Shuffle the deck, and distribute the cards evenly among the 4 players. Each player will take one card in their hand (visible to only the player himself), and place the others on a stack in front of them.

Overview:
The goal is to collect all the cards. Taking turns, each player will play a card from either their hand, or hope for the best and play the first card from their stack. After all players have taken turns, the player with the highest card* will win that round and will collect the played cards. He will then start the next round.

Replenishing / losing / winning
If you play a card from your hand, you may draw the first card from your stack and place it in your hand. If you run out of cards on your stack, you may shuffle the cards you collected, and this will be your new stack. You will be removed from the game the moment you have played the last card (which is by definition from your hand) and do not win the consequent round. Last player standing wins the game.

*Highest card
The highest card is in principle determined by the standard sequence 2<3...<King. However, when someone plays an ace, the sequence becomes 4<...<Ace<2<3, i.e., 3 becomes the highest card. The winner is determined at the end of the round - the order of play is irrelevant.

If there's a tie, the 'winning' players do another round, and the final winning player will collect all the cards 'on the table', i.e., of all the tied rounds. Edge case: if you tie with your final card, you will lose after all, since you have no cards to play with after the tie.

Examples:
We have four players: Alice, Bob, Carol and Dave. Let's denote the cards by [1-12] where 1 is an ace.

A:  5, B: 9, C: 1, D: 8.   Winner: Carol.
C: 10  D: 4  A: 1, B: 2.   Winner: Bob (2 beats ace)
B: 11, C: 1, D: 4, A: 1.   Tie between Carol and Alice... (both aces)
C:  4, A: 3                Winner: Carol (she gets six cards).
C:  3, D: 2, A: 1, B: 6.   Winner: Carol (3 beats ace)

The challenge

Build a player that will win as many games as possible. You will receive 10 points for first place, 5 for second, 3 for third and 1 for last place. Your final score will be divided by the number of simulation runs I did, so you will score [1-10].

Your code must fit within [an amount of bytes to be determined; 1kiB?]

Sandbox questions:

  1. Would you consider participating? Why (not)? (challenge quality)
  2. What would be better?
    • A Java controller (each player extends the default Player class). Advantage: no I/O parsing required, just simple function calls. Disadvantage: excludes all other languages, lest a wrapper is made.
    • A STDIN/STDOUT controller (each player will receive input over STDIN, and return what they do on STDOUT). Advantage: virtually any language can compete. Disadvantage: possibly cumbersome I/O format to present the players with all relevant information.
\$\endgroup\$
9
  • \$\begingroup\$ 1. Why use standard decks of cards? The mechanic would be identical if the deck has 8 copies each of the numbers 0 to 12, and the special-cased parsing would be eliminated. 2. The weird stuff with the ace isn't adequately explained. E.g. what happens if the four players play, in order, 3, A, 3, A? \$\endgroup\$ Apr 7, 2016 at 13:40
  • \$\begingroup\$ @PeterTaylor Thanks for the feedback! 1) I did that to make it less abstract. Eventually, I will use 1-12 for coding the cards. 2) Is it better explained now? (in your case, the two players playing a '3' would tie and have another round) \$\endgroup\$
    – Sanchises
    Apr 7, 2016 at 14:48
  • \$\begingroup\$ Still not very clear, no. King < Ace when no-one plays an ace (and therefore it doesn't matter) and Ace < 2 when someone plays an ace, so that for all practical purposes Ace < 2 always? \$\endgroup\$ Apr 7, 2016 at 15:17
  • \$\begingroup\$ @PeterTaylor Oh wait, I see where the confusion comes from, my bad. Yes, you are right, and the latest edit should reflect that. Any comments on whether to use a Java controller or a STDIN/STDOUT one? \$\endgroup\$
    – Sanchises
    Apr 7, 2016 at 15:22
  • \$\begingroup\$ A Java controller can easily wrap a stdin/stdout one. You should be able to steal a wrapper from some existing koth. I'm still not entirely clear what's going on with the ace: is the full post-ace-play order 4<5<6<7<8<9<10<J<Q<K<A<2<3 ? \$\endgroup\$ Apr 8, 2016 at 7:20
  • \$\begingroup\$ @PeterTaylor Yes, exactly. I will try to make a wrapper then, thanks once again for the feedback. \$\endgroup\$
    – Sanchises
    Apr 8, 2016 at 7:44
  • \$\begingroup\$ Unless I'm wrong, it seems like you will never have more than one card in your hand, but the language you use implies that you can. Can you have more than one? If so, how? \$\endgroup\$ Apr 8, 2016 at 12:52
  • \$\begingroup\$ You mean the moment you have played the last card from your hand and do not win the consequent round? I meant to say "The moment you have played the last card (which will by definition be your hand card), ...", I'll fix that phrasing. Or is any other part of the spec also confusing? \$\endgroup\$
    – Sanchises
    Apr 8, 2016 at 13:01
  • \$\begingroup\$ Also, you refer to playing "a" card from your hand, which makes it sound like a choice. I would replace "a" with "the" in those cases. The only thing besides that that you could add is how you will determine a winner if you have, for example, N bots submitted, given that the game takes exactly 4 players. \$\endgroup\$ Apr 8, 2016 at 13:28
1
\$\begingroup\$

Compute the size of a binary tree iteratively

Introduction

Binary trees are easy to manipulate using recursion. For example, here is Java code that declares a binary tree and determines its size (the number of nodes it contains) recursively:

public class BinaryTree
{
  private Node root;

  /**
   * Constructs a search tree with the given root.
   *
   * @param the root node
   */
  public BinaryTree(Node root)
  {
    this.root = root;
  }

  /**
   * Gets the number of nodes in this tree.
   */
  public int size()
  {
    return size(root);
  }

  // private helper function
  private int size(Node node)
  {
    if (node == null)
      return 0;
    else
      return 1 + size(node.getLeftChild()) + size(node.getRightChild());
  }

The definition of Node is not shown. As you would expect, it has methods getLeftChild() and getRightChild() that either return other instances of Node or null. A Node does not have backlinks to its parent.

Challenge

Write a non-recursive function to determine the number of nodes in a binary tree. You should not make any assumptions about the ordering of the nodes; however, you can assume that a reasonable hash function exists on nodes such that you can expect O(1) access time using a hash table.

In addition to not calling itself, your function should not simulate recursion through a stack-like data structure, and it should not call any recursive functions. You may use standard data structures, such as a set that uses hash codes to determine membership.

Solutions will be judged by their efficiency. Specifically, they will be judged by their time complexity, with space complexity used as a tie-breaker.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Hi, welcome to PPCG and thanks for using the Sandbox! :) fastest-algorithm challenges are hard to run because they are hard to score well, just as an FYI. Also probably worth noting is that not all languages will have the same definition of binary tree. In addition, I'm not certain this is possible without "simulating recursion", arguably, any looping construct at all is also solvable through recursion, so I don't think that's really a good way to word this restriction. \$\endgroup\$ Apr 15, 2016 at 20:38
  • 1
    \$\begingroup\$ I think that by the standards of this site, this question should be considered a dupe of this one and therefore closed. (This is sad, because the older question is still semi-vandalised by its OP). \$\endgroup\$ Apr 15, 2016 at 21:01
  • \$\begingroup\$ Thanks for the feedback. I'll be back with a different question some time. \$\endgroup\$ Apr 15, 2016 at 22:03
1
\$\begingroup\$

Decimal to Troll

Discworld Trolls have a unique number system. From Wikipedia:

Trolls have a numeral system of their own, based on powers of 4.

The base numerals are one (1), two (2), three (3), many (4) and lots (16), which can be combined to form higher numbers.

When combined, each numeral's value is added to those of the others. Higher-valued numerals take priority over lower-valued ones, so that 4 is written "many" and not "two-two" or "three-one" and 20 is written "lots many" rather than "many many many many many". If there are no ones, twos or threes, the number is written with spaces between the numerals; if any exist a hyphen replaces the space between every numeral.

The Challenge

The challenge is to write a program that accepts a positive integer and outputs the equivalent troll counting string, including the correct separator (hyphen or space) based on the above rules.

Examples (including those from Wikipedia):

Input   Output
-----   ------
   1      one
   2      two
   3      three
   4      many
   5      many-one
  10      many-many-two
  20      lots many
  32      lots lots
 126      lots-lots-lots-lots-lots-lots-lots-many-many-many-two

This is code-golf, shortest answer wins.

\$\endgroup\$
3
  • \$\begingroup\$ Nice challenge! \$\endgroup\$
    – Leaky Nun
    Apr 18, 2016 at 12:20
  • 1
    \$\begingroup\$ I feel like this is a dupe of this challenge about money. I think the greedy algorithm still works, the only differences that I see between these is the I/O formats and the amounts to use, which I'm afraid don't sufficiently differentiate them, in my opinion. \$\endgroup\$ Apr 18, 2016 at 13:27
  • \$\begingroup\$ @FryAmTheEggman I can see the similarities, and yes, the repeating units in the output and separator are the main differences. But Discworld! :) Happy to withdraw it if consensus is it's too similar. \$\endgroup\$
    – Liesel
    Apr 19, 2016 at 1:48
1
\$\begingroup\$

Tron Bot Racing

It's time to begin annual Tron Racing Tournament. Create a bot that will steer your cycle to a victory!

Glossary

Board is a 100x100 square that wraps around its edges.

Game

Bots leave impassable trail. In the beginning of the game, all the bots participating (2 in case of a duel) are placed randomly thorough the map. Then, at the beginning of each turn, all bots must decide the direction they will chose next (Up, Down, Right, Left) based (or not) on the available data, which is the empty cells in each of the directions. If bot tries to move into an occupied cell, his turn is repeated until it makes a valid move. If after 10 tries bot still won't make a valid move, it dies. Game ends when all bots die. Score is the length of your trail.

Example:

. . . . . d . .
. . . b b b b .     Received data:
. . . b . u b .     L0 U3 R3 D3 T1
. . . b . u b .     
. . . b . u b .     Length of line of sight is `ceil(map_size/2) - 1`
r . . b b B r r     and it wraps around map edges.  
. . . . . d . .     u, r, d - lines of sight
. . . . . d . .     B - bot, b - bot's trail 

If bot decides to go Left (and will collide with his own trail), he is invoked one more time with Tries increased: `L0 U3 R3 D3 T2'.

Submissions

The engine is written in Node.js, so your bot should be a function in Javascript that accepts 1 argument (state array) and returns integer between 0 - 3 which corresponds to your chosen direction.

function RandomBot(state) {
  return Math.floor(Math.random() * 4);
}

0 - Left, 1 - Up, 2 - Right, 3 - Down

You can also write your bot in any other runnable language. It will be run every time a decision needs to be made, with data pushed into StdIn 3,3,0,2,1 and output (single integer) required at StdOut.

However, by using Javascript you have the advantage to use this to save data between runs.

Winner and conditions

Bots will be dueling with each other, each duel repeated 100 times. Standard loopholes apply.

Meta

How to create leaderboard? How to score wins and loses? Is there anything that can be improved? This is my first entry ever and I have already a working prototype. I have concerns with the data passed to bots. Maybe its too small? Anyway, let me know what do you think about it guys.

\$\endgroup\$
4
  • \$\begingroup\$ Similar \$\endgroup\$ Apr 20, 2016 at 10:57
  • \$\begingroup\$ Even more similar. Except for limited data/sight, it's a duplicate. \$\endgroup\$
    – Geobits
    Apr 20, 2016 at 13:56
  • \$\begingroup\$ I think that if the match would consist of bigger board and all the bots at once, it would be different enough to not be a duplicate. \$\endgroup\$
    – Are
    Apr 20, 2016 at 15:03
  • \$\begingroup\$ I agree that a free-for-all should be sufficiently different, especially given the limited sight. Then again, with that many walls floating around, it could end up being very hard to avoid an impossible trap. You might want to do some test runs with some naive bots to see what happens. \$\endgroup\$
    – Geobits
    Apr 21, 2016 at 2:29
1
\$\begingroup\$

Chopsticks

Overview (basically the wiki page)

Chopsticks is a game played with two hands and two people. Both start with one finger out on each hand, the finger count. On a player's turn, they must choose one of their opponent's hands. That opponent adds the player's finger count to the one on that hand (and extends that many fingers). Once a hand's finger count has reached five or more, that hand's finger count is reduced to 0 and can't be used. Once both hands are out, the opponent wins.

To make the game more interesting, there is a mechanic called splitting: A player may use his turn to divide both his hand counts differently than he/she already has. A valid move would be to split from a 2 and a 3 to a 4 and a 1. An invalid move would be to split from a 2 and a 3 to a 3 and a 2. It is illegal to bring a hand back to life like a bunch of my friends like to do, as in split from a 4 and a 0 (a hand that is out) to a 2 and a 2 (back in). I deem it legal (since the Wikipedia article didn't say anything about it) to get one of your hands out using splitting, such as going from 3 and 4 to 2 and 5 (out).

Challenge

Your task is to write a bot that will play chopsticks against another bot.

Input

Every time your bot takes a turn, it will be given its opponent's finger count and its own finger count in this format:

[opponent hand 1] [opponent hand 2] [own hand 1] [own hand 2]

There will be spaces in between each value as shown above. Each value will be an integer. The bot should remember the hand numbers, as it is important to the output.

Output

Your bot must take the data, decide what to do with it, and respond accordingly. Output is in this form:

[target hand] [attacking hand]

where [target] refers to the target opponent's hand and [hand] refers to the hand you are hitting the target with. A valid output would be 1, 2, which says that the bot wants to hit the opponent's first hand with its own second hand.

Problems and todo (sandbox)

  • I do not yet know how to make a program that handles all of this. I'll try to work on it.
  • There will be a bracket.
  • Should I make tweaks to the game to make it more suitable?
  • I may or may not follow through, but regardless I would like feedback.

Thanks.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ If I understand correctly, this is an alternating turn game with about 6125 states. It's therefore very likely that every submission will play perfectly. \$\endgroup\$ Apr 27, 2016 at 8:52
1
\$\begingroup\$

Visualize the Euclidean Algorithm by Tiling Rectangles

META: What's your opinion on moving this to a pop-con instead of a code-golf?


Suppose we have two positive integers, m and n. We can use Euclid's algorithm to calculate the greatest common divisor of these two numbers (the largest number that divides both numbers without a remainder). This is done by essentially taking successive subtractions of remainders until you reach zero. The linked Wikipedia article goes into much greater depth, and the mathematics behind it, for the curious.

Here, though, we're going to visualize the algorithm by taking a rectangle of size m x n and recursively tiling the rectangle with successively smaller and smaller squares until all space is consumed. The length of the side of the smallest square is thus the gcd(m,n).

Assuming m >= n, the first square is of size n x n, and is placed against the bottom edge. This repeats until a square does not fit, leaving a rectangle of size n x (m-kn) remaining, where k is how many n x n squares fit. That process then repeats on the newly-formed rectangle, starting on the left side, then the bottom, then the left, etc., until the original m x n rectangle is fully tiled.

Here's a beautifully done animated example, from that Wikipedia page, of 1071 and 462, showing the result to be 21.
By Proteins (Own work) CC BY-SA 3.0, via Wikimedia Commons.

Input

  • Two distinct positive integers, m and n, via any convenient input method. Without loss of generality, you can assume m > n (for example, if you take input as a tuple, your program can assume that the first element is always the larger of the two, and you don't need to test size).
  • Your implementation should be able to handle input up to your language's default int size (or equivalent).

Output

  • An image of at least 300px square, but no bigger than 1200px square, showing a rectangle of proportion m x n, tiled with successively smaller squares as described above. This means that for small inputs the rectangle will need to be stretched, and for large inputs the rectangle will need to be shrunk.
  • The image must be oriented so that m (the larger) is the vertical dimension and n is the horizontal.
  • Squares of the same size must be distinct. This could be done by coloring the squares differently from their neighbors, by enclosing each square in a border (as in the above animation), etc.
  • Output does not necessarily need to be in color, so long as the squares are distinct and understandable.
  • The image can be displayed on-screen or saved to a file.

Examples

[TODO]

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

You have an even number of identical balls. Half of them are "Light" balls and other half are "Heavy" balls which are heavier than the light balls for a unknown amount. You have to separate them into the "Light" box and a "Heavy" box using a scale instrument which tells you precisely for how much the left side is heavier than the right side when the balls are weighted on it.

Find a way to separate a given number of the balls with the minimal weightings as possible.

This is a challenge to programmatically reslove this question.


The solution should be an algorithm that would separate the given amount of balls with the least weightings as possible.

The Input can be any even number of balls, where the heavy balls will differ in weight from the light balls by a random amount. The balls are marked from 1 to n, and the "heavy" and "light" properties are assigned to all the balls randomly.

Now the program can take any number of balls and place it on the "right" side of a "scale" and then another amount of balls to be placed on the "left" side of the scale. It can read for how much exactly one side is heavier than the another, and then it can proceed to weight another set of balls until he can for sure tell for each numbered ball if it is "light" or "heavy". It should know how to process this in a least "weightings" or "uses of the scale" as possible.

So the goal is to write the most efficient program that can most efficiently separate the balls using the minimal amount of "weightings", and doing that for as many cases of given balls as possible.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ This seems too simple. The optimal algorithm is well-known to the point where it's a common interview question. It would just be a race to be the first to implement it in the chosen language. \$\endgroup\$
    – user45941
    Apr 29, 2016 at 19:17
  • \$\begingroup\$ @Mego Thank you for your review, Btw How would one write such an algorithm? Does something like that already exists? My main point of posting this was to answer that question, I would appriciate if you have any way of providing any help. \$\endgroup\$
    – Vepir
    Apr 29, 2016 at 19:25
  • \$\begingroup\$ @Mego The "interview" question you're thinking of is probably a version with one different weight, as pointed out in the linked question. This seems challenging enough; one could even consider comparing different numbers of balls. \$\endgroup\$
    – feersum
    Apr 29, 2016 at 20:45
  • 1
    \$\begingroup\$ What this needs to be a good question is some kind of output specification, e.g. giving the expected number of comparisons, an interactive protocol with the user giving comparison results, or some kind of tree decision representation. \$\endgroup\$
    – feersum
    Apr 29, 2016 at 20:47
  • \$\begingroup\$ I would just set a pivot ball (e.g. the first one) and compare everything else with it. Runtime complexity O(n). \$\endgroup\$
    – Leaky Nun
    Apr 30, 2016 at 14:36
  • \$\begingroup\$ @Kennylau but that is exactly the oposite of the solution. You would have then too many unecessary weightings, since the goal is to do it in least possible weightings no matter how complex the real solution might be \$\endgroup\$
    – Vepir
    Apr 30, 2016 at 15:11
1
\$\begingroup\$

How Many Colours?

Take a grid of ASCII art rectangles as input and output the minimum number of colours you would need to colour it in so that no two rectangles of the same colour are touching.

Rules

  • Input can be any type of grid format (multine string, array of strings, etc...).
  • Rectangles only count as touching if the inside is adjacent to the inside of another rectangle (see the bottom-left rectangle in the example).
  • You may use different characters to # and space, but if you do, please specify what you use in your answer.
  • The grid itself will always be rectangular.
  • Grid width and height will always be between 3 and 99.
  • Shortest code in bytes wins.

Example

The output for this input would be 3. An example arrangement of each colour 1 to 3 is labelled in the input below. Note how the bottom-left rectangle does not count as adjacent to the middle one.

#################
# 1  #      # 1 #
######      #   #
# 2  #  3   #####
#    #      #   #
######      # 2 #
# 3  ########   #
#    #  1   #   #
#################

Test Cases

TODO...

Links

Four Colour Theorem

Tags

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

Wheels on the Bus Go...

Scenario

There is a bus heading for an intersection. Usually that is when buses would stop and give way to traffic, but there's a bomb on the bus! The bomb blows up if the speed of the bus falls below 50 miles-per-hour. Find out what speed the bus needs to travel at to avoid crashing into the cars going through the intersection.

Input

  • Take a list of cars coming from the left and another list of cars coming from the right. The lists contain the distance of each car from the intersection as integers.
  • The distances will always be from 1 to 99 units.
  • There will always be 1 to 9 cars in either direction (2 to 18 total).

Output

  • The speed the bus must travel to make it through the intersection without hitting a car.
  • The speed can be an integer from 5 and to 9 which is the speed in miles-per-hour / 10.

Rules

  • Each iteration, every vehicle moves speed in mph / 10 units forwards. The "path" of a vehicle for each iteration includes it's position before the iteration, it's position after the iteration and every position in between.
  • The cars always travel at 40 mph.
  • A crash occurs when the path of the bus intersects the path of a car in the intersection.
  • The bus starts 20 units before the intersection.
  • Cars cannot crash into other cars.
  • The speed of each bus cannot change during the simulation. You can only give each bus one speed.
  • Only solvable inputs will be given.
  • Shortest code in bytes wins.

Example

TODO: Example doesn't make sense yet. Will complete later...

Here's an example using ASCII art to illustrate what would happen with this input and a bus speed of 6. Note: despite what it may look like, the intersection should behave as if it's size is only one unit.

  • B = Bus
  • . = Vehcile movement during iteration
  • C = Car

Input: [ ... ]

                  |     ^ |
                  |   | | |
------------------ ---     --------------
        <-                |    C . . . C
--  --  --  --  --         --  --  --  --
. C           C . |     .  . C     ->
------------------     --- --------------
                  |   |   |
                  |     B |
                  |   | . |
                  |     . |
                  |   | . |
                  |     . |
                  |   | . |
                  |     B |

Test Cases

TODO...

Tags

\$\endgroup\$
2
  • \$\begingroup\$ So a bus can never crash with another bus with a different unit digit in the distance, if they are moving from different roads? \$\endgroup\$
    – Leaky Nun
    May 1, 2016 at 15:16
  • \$\begingroup\$ @KennyLau There's only two roads, the sideways one and the up/down one. The only time buses from both roads will crash is if their paths overlap over the intersection. I'll try explaining it better when I edit it. \$\endgroup\$
    – user81655
    May 1, 2016 at 15:19
1
\$\begingroup\$

From Smiles to Molecular formula!


SMILES is an algorithm to represent chemical molecules in one-line ASCII.

In this challenge, we will only be dealing with purely organic chemicals.

  • All the Hydrogens are not represented.
  • All single bonds not represented, double bond is =, triple bond is #. For example, ethane is CC, ethene is C=C, ethyne is C#C.
  • Branches are represented by (). For example, isobutane is CC(C)C, acetone is CC(=O)C.
  • Cycles are represented by numbers. For example, cyclohexane is C1CCCCC1.
  • All other things are ignored in this challenge.

Your task is to determine the molecular formula of a molecule, given its SMILES representation.

Specs

Any reasonable input/output format.

These are all accepted, for formaldehyde:

  • CH2O
  • C1H2O1
  • CxHxxOx (unary)
  • CHHO
  • OCHH
  • OHCH

Scoring

This is . Shortest solution in bytes wins.

Testcases

input       output
C=O         CH2O
O=C=O       CO2
C1C(=O)CC1  C4H6O
C#CCC       C4H6
\$\endgroup\$
6
  • \$\begingroup\$ I think you need to tighten up the specs. "Reasonable" is, of course, wide open to interpretation. For example, it's left unclear if the ordering in the output matters. Is it always carbon, hydrogen, oxygen, in that order (omitted if not present, naturally)? Is it "unreasonable" to say OCH2? \$\endgroup\$
    – dcsohl
    May 2, 2016 at 13:20
  • \$\begingroup\$ @dcsohl Thanks, edited to allow that. \$\endgroup\$
    – Leaky Nun
    May 2, 2016 at 13:28
  • \$\begingroup\$ Are you sure about your examples? My reading of the Wikipedia page is that cyclehexane's SMILES description should contain 6 Cs, but your example only has 5. \$\endgroup\$ May 3, 2016 at 10:08
  • \$\begingroup\$ @PeterTaylor That was a typo, thanks. \$\endgroup\$
    – Leaky Nun
    May 3, 2016 at 14:16
  • \$\begingroup\$ Which elements do answers need to be able to handle? \$\endgroup\$ May 4, 2016 at 6:28
  • \$\begingroup\$ Also, can we assume that we won't be given aromatics so complicated that the cycle indication numbers go up to 10? \$\endgroup\$ May 4, 2016 at 7:16
1
\$\begingroup\$

The incremental Gijswijt's sequence

The Gijswijt's sequence G is a sequence where the next term is the maximal number of repeating blocks of terms going so far backward.

The first numbers of this series are: 1, 1, 2, 1, 1, 2, 2, 2, 3

The incremental Gijswijt's sequence I is a sequence of Gijswijt's indices where any term of this last sequence I(n) has an image in Gijswijt G(I(n)) that is greater or equal all terms that precede it in that sequence G .

In other terms, It is an increasing sequence of indexes i for which G(i) is at least as large as G(j) for any j < i. Thus it contains the index of every 1 up to the first 2, every 2 up to the first 3, etc

Example:

  G= 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3,...

  I= 1, 2, 3,       6, 7, 8, 9,                        18,                           28,                        37,...

Your program must output the most you can print from the starting of sequence until the delay between printing two consecutive terms exceeds 10 minutes, the actual number of outputs is your score.

For matter of reliability, the complete accurate "run-lengthed" G sequence must be linked through pastbin or any raw data repository.

the output will be so large to fit an int32 registry, so i suggest to print it modulo 1000007 or dont.

if the scores are not be divergent enough i will apply some salt, scoring is evaluated to N/T where T is executon time in seconds for the last term of sequence, the tie broken by the earlier post .

Only another 45 secs after the delay cap are given as an extra time.

\$\endgroup\$
14
  • \$\begingroup\$ I would VTC as unclear. \$\endgroup\$
    – Riker
    May 4, 2016 at 16:08
  • \$\begingroup\$ hmmm what is unclear ? \$\endgroup\$
    – Abr001am
    May 4, 2016 at 16:08
  • \$\begingroup\$ Winning criterion. until nothing appears in the console for 10 minutes is a bit vague. \$\endgroup\$
    – Riker
    May 4, 2016 at 16:08
  • \$\begingroup\$ 10 minutes from last output, is this what u asked me to clarify ? \$\endgroup\$
    – Abr001am
    May 4, 2016 at 16:10
  • \$\begingroup\$ "nothing appears" is a bit vague. I think you want something more like "the time to calculate the next term is > 10 minutes." \$\endgroup\$
    – Riker
    May 4, 2016 at 16:11
  • \$\begingroup\$ yes when it exceeds that cap, execution must be halted \$\endgroup\$
    – Abr001am
    May 4, 2016 at 16:12
  • \$\begingroup\$ .. I mean the wording in unclear. Can you say something like the time to calculate rather than the console is empty? \$\endgroup\$
    – Riker
    May 4, 2016 at 16:15
  • \$\begingroup\$ if that makes you contented .... \$\endgroup\$
    – Abr001am
    May 4, 2016 at 16:18
  • 1
    \$\begingroup\$ I found the definition rather hard to follow, and technically it defines an uncountable number of sequences. I suggest "The incremental Gijswijt's sequence is the (increasing) sequence of indexes i for which G(i) is at least as large as G(j) for any j < i. Thus it contains the index of every 1 up to the first 2, every 2 up to the first 3, etc. If you are familiar with the Records transform on integer sequences, this is effectively a Non-strict Records transform." \$\endgroup\$ May 7, 2016 at 8:55
  • 1
    \$\begingroup\$ "For matter of reliability, the complete accurate "run-lengthed" G sequence must be linked through pastbin or any raw data repository." Why? If it's generated by the same process, it would have the same bugs. If it isn't, I don't see the point of asking every single answer to include a pastebin link. "i suggest to print it modulo 1000007 or dont." Either make this a requirement or don't. It complicates comparison of answers to make it optional. "Only another 45 secs after the delay cap are given as an extra time." Extra time for what? \$\endgroup\$ May 7, 2016 at 8:59
  • \$\begingroup\$ @PeterTaylor 1. That is because it a contest for scores in increment, so any new record must be followed by a string of compressed numbers from the last terminus reached, until the new record using his own technique imagine the new score is 2 numbers far from the last result ? the algorithm must print a correct G series that is ground of I series. \$\endgroup\$
    – Abr001am
    May 7, 2016 at 10:47
  • \$\begingroup\$ 2. The numbers could be too big and unintelligible, so either print a remainder or the difference of two edges or print it all along the console modulo something. \$\endgroup\$
    – Abr001am
    May 7, 2016 at 10:49
  • \$\begingroup\$ 3. extra time for me to stop execution. \$\endgroup\$
    – Abr001am
    May 7, 2016 at 10:49
  • \$\begingroup\$ a compressed string of numbers * in the first note \$\endgroup\$
    – Abr001am
    May 7, 2016 at 11:31
1
47 48
49
50 51
140

You must log in to answer this question.

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