449
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Suggestion: instead of having a notice on the top answer ("note: if you are..."), you'd better just put a moderator notice below the question \$\endgroup\$ – nicael Mar 19 '18 at 19:35
  • 3
    \$\begingroup\$ @nicael We can only choose from three post notices: citation needed, current event, and insufficient explanation. \$\endgroup\$ – Dennis Apr 7 '18 at 14:43
  • \$\begingroup\$ If you remove a post but didn't post it you can replace the text body with [](lots of text here to reach the min chars) to make it much smaller when removed \$\endgroup\$ – Christopher Apr 13 '18 at 17:54
  • 5
    \$\begingroup\$ @Christopher Please don't do that for old proposals. It clutters the first page with an answer nobody cares about anymore, instead of staying hidden on page 10 where it will bother nobody. \$\endgroup\$ – Dennis Apr 13 '18 at 18:17
  • \$\begingroup\$ @Dennis ? what are you talking about. As if if you didn't post it like you just removed you own sandbox because dupe or something \$\endgroup\$ – Christopher Apr 13 '18 at 18:18
  • 4
    \$\begingroup\$ @Christopher If your proposal is still on the first few pages, you can replace the proposal with a stub to save vertical space on these pages. However, if your proposal is already on page 10, editing your proposal will bump it to page 1, where space is more precious than on page 10. \$\endgroup\$ – Dennis Apr 13 '18 at 18:21
  • \$\begingroup\$ @Dennis ohh that makes sense \$\endgroup\$ – Christopher Apr 13 '18 at 18:25
  • \$\begingroup\$ codegolf.meta.stackexchange.com/questions/12599/… \$\endgroup\$ – Redwolf Programs Apr 17 '18 at 17:38
  • 1
    \$\begingroup\$ Maybe it's time to consider cleaning some of this up a bit. There's just too much to go through and some of these proposals are years old and obviously not going anywhere (even some of the good ones). Perhaps cull anything that is two years old and has likewise been inactive for as long? \$\endgroup\$ – ouflak Aug 6 '18 at 9:07
  • 1
    \$\begingroup\$ @ouflak You can sort posts by "active". That seems to resolve all of the problems you describe. \$\endgroup\$ – FryAmTheEggman Sep 27 '18 at 19:04
  • \$\begingroup\$ I already posted this, but codegolf.stackexchange.com/questions/176599/… \$\endgroup\$ – 2br-2b Nov 27 '18 at 2:38
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ It seems like there is a rollback war with moderators and the Community user to add and remove the featured tag. \$\endgroup\$ – smileycreations15 Mar 21 at 21:13
  • 3
    \$\begingroup\$ @smileycreations15 That's unfortunately unavoidable. Community is an automatic script, and, since most featured questions are only temporarily so, it assumes that we don't want this question to be featured forever. However, we do, so a mod has to edit the tag in every now and then. \$\endgroup\$ – Erik the Outgolfer Mar 24 at 15:22
  • 3
    \$\begingroup\$ @EriktheOutgolfer Yeah. Maybe they can create a special [featured-pin] tag which will both feature it and pin it from removal by the Community user. \$\endgroup\$ – smileycreations15 Mar 24 at 17:20

2477 Answers 2477

0
\$\begingroup\$

Find the duration of a worst-case brute-force attack

Given the following information about a 7-bit ASCII-encoded password and the computer that will crack it with a brute-force attack:

  • Length of the password in characters
  • Charset size (i.e total count of the possible characters one character in the password can be)
  • Number of passwords the computer can test in one second millisecond (rounded down)

Write the shortest program that finds out how long the attack will take in the worst-case scenario where the computer tries all possible passwords.

  • The output is the duration in this format: years months days hours minutes seconds milliseconds
    • One "month" is 30 days long.
    • Fractions of milliseconds are rounded up.
    • You can assume that the cracking finishes immediately if it takes less than 50 milliseconds, and make the program print out Instant in such cases.
    • Similarly, the cracking can be considered Neverending if it takes more than 292 billion years.
  • The program can output using any method, from merely printing to STDOUT to causing a kernel panic/bluescreen with the duration as the error message.
  • The input method to get the info about the password/the machine can be anything, as well. Don't use standard loopholes though.
  • It's not enforced, but strongly encouraged to write a standalone program.

Here's how to calculate the charset size:

  • Start with 0.
  • If there's a digit (in the password), add 10.
  • If there's a lowercase letter, add 26.
  • If there's an uppercase letter, add another 26.
  • If there's punctuation, add 32 (7-bit ASCII has this many punctuation characters).
  • If there's a whitespace character, add 2. Whitespace characters are horizontal tab (0x09) and space (0x20).
  • Any other character counts as non-printable (including backspace (0x08), DEL (0x7F), line feed (0x0A) and carriage return (0x0D)). Add 29 if there's any of them.

Count of all possible passwords is (charset size)password length.

Here are some applicable-in-real-life cases you can test your program with (let's assume the computer that will crack them can test 1 billion passwords per second, which equals to 1,000,000 passwords/millisecond):

  • 4 characters, charset size 10 (PIN) - 10,000 passwords, output is 0 0 0 0 0 0 1 or Instant
  • 8 characters, charset size 94 (at least one uppercase letter, one lowercase letter, one digit and one punctuation) - 6,095,689,385,410,816 passwords, output is 0 2 10 13 14 49 386
  • 10 characters, charset size 2 (weakest valid Discourse password, contains whitespace only) - 1024 passwords, output is 0 0 0 0 0 0 1 or Instant
  • 25 characters, charset size 26 (correcthorsebatterystaple) - 236,773,830,007,967,588,876,795,164,938,469,376 passwords, output is 7612327353651221350 2 14 0 26 4 939 or Neverending
  • 127 characters, charset size 96 (strongest password on newer Windows releases) - written below
  • 1024 characters, charset size 36 (4096-bit PGP key represented as a hexadecimal number) - written below

These are the stats of the maximum-strength Windows password:

Passwords: 560,333,510,486,846,899,384,847,242,571,130,277,659,458,884,466,874,695,582,912,274,460,529,559,443,783,341,570,989,525,270,653,136,186,432,110,439,597,936,820,880,106,519,625,601,191,574,799,863,912,148,304,962,133,852,037,202,160,056,511,510,962,873,278,300,126,526,144,267,006,137,180,032,492,751,016,171,207,701,495,935,943,049,216
Output: 18014837657113133339276210216407223432981574217685014647084370963880194169360318337544673523362047845500003550655797865897637169483847774934889398916928636347805229296463546812516445182705545212838429981490065783731353925307067135133992 5 15 19 58 55 944
Alternate output: Neverending

And these are the stats of the PGP key:

Passwords: 4,505,684,579,918,576,285,346,738,866,335,056,898,110,301,685,668,199,078,230,938,179,212,682,315,156,231,410,185,391,761,603,272,976,014,035,539,665,517,248,679,228,261,440,294,129,198,036,262,705,242,310,399,830,546,082,361,923,420,737,260,766,677,891,361,176,003,624,143,368,380,527,062,643,297,677,246,518,686,688,642,023,537,863,317,793,178,302,508,440,097,154,593,959,832,175,055,427,351,149,410,096,495,695,380,712,810,868,774,475,142,767,054,868,274,802,269,522,299,482,066,464,842,097,715,922,988,138,315,118,067,288,670,934,735,264,524,936,706,249,961,394,413,647,964,221,767,703,673,264,468,419,121,528,644,906,680,808,060,759,817,669,970,046,776,525,266,199,099,671,937,918,801,013,826,958,891,378,841,908,663,991,372,649,027,188,879,525,186,690,599,345,723,173,064,252,017,258,129,131,786,488,462,307,158,861,824,049,980,863,991,149,295,162,169,512,952,373,415,599,734,988,691,348,925,488,351,712,593,858,837,027,205,238,618,188,975,201,320,681,214,515,875,812,195,250,605,867,622,987,451,763,883,339,709,733,502,125,838,221,788,546,339,051,347,360,900,518,381,976,167,289,930,943,228,024,924,785,158,428,496,314,937,921,503,359,298,542,415,845,218,449,360,806,235,379,253,546,728,753,218,950,843,742,471,105,739,555,344,908,900,309,982,913,223,331,321,839,212,821,903,239,320,600,564,890,951,140,667,647,680,682,245,252,370,183,758,578,065,733,075,207,856,432,661,797,090,351,101,165,469,273,829,754,476,555,209,675,613,232,875,323,406,611,257,057,059,099,019,633,298,079,410,970,345,108,939,943,042,100,267,260,413,671,556,828,411,902,575,269,208,445,279,433,655,878,082,023,068,697,154,581,711,817,787,688,949,105,583,339,471,599,190,831,084,304,744,483,799,555,478,063,729,574,297,623,870,804,763,558,027,580,772,927,971,329,879,231,979,556,301,616,929,595,576,646,883,067,201,999,872,899,862,889,211,861,332,535,050,455,387,251,034,043,732,447,006,164,551,883,918,733,705,027,099,846,583,024,013,092,062,384,703,436,459,115,108,358,829,136,251,317,699,709,899,140,949,893,425,335,769,021,022,912,434,045,643,544,474,460,899,799,213,759,568,795,794,758,914,390,056,283,305,470,380,859,003,818,724,678,434,816
Output: 144858686339974803412639495445442930108998896787172038266169565946909796654971431654622934722327449074525319562291578211137739886840732034401886018044055761311424449664413690224320369299057721231224396352345948448015131278860508182828147139982752631922511354755096078964028889980704480936709984283352948061204198196785328857204061945957268141550998891534834171375541476907019128991072373909056348731183618329634024763694746476776233417623704464804027405450152026906721990999895827471385353870130056140660354679074035526421905828555132520211676677361401337091034117370453939870215183392876069255694823382473711006907851853458746913295694931911314073828877816349504523255816791677974298928074750103049081088894521647398444396729546431174466495229648516324713327536964168664025148591452750098101445502202880078966283755495859954505040675103796820824907455740718188735077328268047865426806174561044520100917915500979652319301547868727504821981520811835192875926630119576922600465887060849654310721522802609638109522185755307201898676461606130734024600227278608209698963323356340446015796148617903068964091403666193996894642822309315198786075754477250953946657292049336910661279747924178751224344877465829301109562043071275369906871767991229129085786546569052197642684662087651029574035646976531236521763373563846425925268656816387911380422031991615290633773786744123323731112880994579065426763237282889858685438654794679302568796507941872848896038602862540480809810919146613018187362072374644736799940064590439265446053422181856817801562474722208358918298576208528044087753034364036 10 24 22 32 4 679
Alternate output: Neverending

\$\endgroup\$
  • \$\begingroup\$ Is there any wrong information? \$\endgroup\$ – dorukayhan Jun 4 '16 at 20:43
  • \$\begingroup\$ Please provide proper test cases, i.e. with all input parameters (speed of computer is missing) and solutions, so that we can verify our programs. \$\endgroup\$ – nimi Jun 4 '16 at 22:36
  • 2
    \$\begingroup\$ Unless there's a good reason you should should go with our defaults and allow functions and programs . Don't allow loopholes. \$\endgroup\$ – nimi Jun 4 '16 at 22:42
  • 2
    \$\begingroup\$ IMO this challenge would be better if it allowed simply returning/outputting an integer number of milliseconds. As it is, the mixed-base conversion will be trivial for languages that have a builtin for it, and nearly as long as the code to compute the length of time (if not longer) for languages that don't. \$\endgroup\$ – Mego Jun 6 '16 at 8:51
  • \$\begingroup\$ You can see how many people agree with Mego's suggestion in the discussion on meta. \$\endgroup\$ – trichoplax Jun 6 '16 at 13:40
  • 2
    \$\begingroup\$ In response to "It's not enforced, but strongly encouraged to write a standalone program.": Elsewhere in the same discussion it recommends avoiding saying "ideally your code will.... That will just be ignored anyway (otherwise the code won't be competitive). Make a definite decision one way or the other rather than a recommendation. \$\endgroup\$ – trichoplax Jun 6 '16 at 13:46
0
\$\begingroup\$

Implement an HTTP Tunnel

I'm bored at work and stuck behind a draconian proxy.

They can take my other ports but they can never take my port 80 freedom!

Help me get all the internets!

This is a challenge.

requirements

  • a single web page that processes GET and POST data and produces output
  • if GET m=start
    • creates any files you feel are necessary (named pipes, scripts, what-have-you)
    • forks a process which will create a tcp connection
    • connects to host and port based on GET variables h and p
    • these variables should be cleansed so as not to allow command injection
  • if GET m=in
    • write the raw POST data to your forked process's tcp connection
  • if GET m=out
    • get all data available from the forked process's tcp connection and write as response
    • should always return right away (let's say, in less than 1 second)
  • if GET m=stop
    • kill your forked process
    • clean up any files it has created

Test data

my first instinct was to have this challenge be three separate pieces of code, a client which listens on a port locally and interacts with the web page, the web page itself, and a script which will be forked by the web page. your score would be the sum of all their byte counts. i decided to remove the last as the start process would likely have to create other files so why not have it create the script to run as well, and decided to remove the first option as well to make it nice and even.

is this a feasible challenge? i will add more explanations and test data soon i think. adding my own client would probably be helpful

\$\endgroup\$
  • \$\begingroup\$ HTTP is stateless, so this is a fundamentally broken way of designing a tunnel over it. I can't remember the exact headers, but there are ways in HTTP/1.1 of reusing a single connection for multiple bidirectional data transfers, and that would be the correct way of doing it. \$\endgroup\$ – Peter Taylor Jun 7 '16 at 11:02
  • \$\begingroup\$ That's why the "start" mode is going to have to fork another process to handle the actual connection. I have this working with my php script forking a nc process which reads and writes from named pipes. I'll post it later. Sure you could use Connection: keep-alive but that connection usually times out pretty quickly, you'd have to implement your own pings to keep it alive, and there's no guarantee how long it would stay alive for. \$\endgroup\$ – Nacht Jun 7 '16 at 23:28
0
\$\begingroup\$

Code Golfed Rosetta Code Code Golfer

(any others? maybe , and/or )

Browsing examples on the Rosetta Code site, I can't help but think that all the code is just so long-winded, inefficient and ...well, readable. Something needs to be done.

Challenge

Choose a language, then write a function that takes the example source code, in the same language, for specific tasks on Rosetta Code and returns a golfed version of that code.

Winner is the person who can golf the example tasks the most. However, this is a code golf challenge so the length of your own source matters too.

Rules

  1. Write a function in your chosen language that takes a string as input and returns a string as output (or equivalent - reading/writing to stdio or file, etc is also ok)
  2. Input is the source code implementation, in your chosen language, of the following three specific tasks as shown on Rosetta Code (your function runs three times, once for each):
  3. Output is a code golfed version of the input with identical functionality (again in the same language)
  4. If there is more than one implementation of a task for a specific language, you must use the first listed
  5. If your chosen language doesn't have an implementation for one of the tasks, then you need to add it yourself (following the Rosetta Code rules - don't go messing up their site just to get a better score here)
  6. With the exception of the rule above, you may not, in any way, modify the content or order of examples on Rosetta Code
  7. You must leave the logical flow of the algorithm mostly intact (eg. you can't simply replace the J quick sort code with /:~)

Scoring

Score for each individual task is calculated as the output character count as a percentage of the input character count. Implementation score for your own code is simply its character count. Total score for a submission is the sum of the three task scores, plus the implementation score.

Submission with the lowest score wins.

So, assuming your function is 100 chars long and running it against the test tasks gives you the output counts shown, your overall score would be calculated as follows:

 Task      | Input char count | Output char count | Score
-----------+------------------+-------------------+--------
 Quicksort |            600   |            400    |  67%
 Happy Nos |            400   |            200    |  50%
 GCD       |            200   |            150    |  75%
--------------------------------------------------+--------
 Implementation score:                            |  100
--------------------------------------------------+--------
 Overall score:                                   |  292

Things I'm not sure about...

Before I post this as a challenge, it would be good to get input on a few things:

  • Will the "if your language doesn't have an implementation" rule cause problems, or can people be trusted to provide sensible implementations that follow the intent of Rosetta Code and don't simply artificially improve their score on the challenge? Is it better just to deny entries from languages which don't already have implementations?
  • With scoring, obviously it's a balancing act, a really terse language will likely get a solid "implementation" score, but should be less able to improve the length of the examples, whereas a verbose language will be the opposite. So, the having too few "tasks" included in the challenge will benefit terse languages, and too many will benefit verbose languages. I want to find a middle ground, so does three tasks seem reasonable?
  • Will someone just find an edge case language which has a really easily golf-able Rosetta example, that will make it unbeatable?
\$\endgroup\$
  • \$\begingroup\$ In the given example score, if an empty program echos then it would be better. More worryingly, this seems to allow coding to the test cases. Are the programs required to do something sensible with inputs other than the three test cases? \$\endgroup\$ – Peter Taylor Jun 9 '16 at 9:42
  • \$\begingroup\$ @PeterTaylor - re: an empty program, I agree, this absolutely creates a minimum bar to beat, but even the most rudimentary whitespace stripping javascript function: (s) => {return s.replace(/[\s]{2,}/g,"");}; results in a score of 263, so my example score sheet is more the problem. \$\endgroup\$ – Alconja Jun 9 '16 at 11:09
  • \$\begingroup\$ @PeterTaylor - Re: coding to the tests, yes this is a bigger problem... The obvious solution is to simply include more tasks, since that would force people to target more generic things, rather than each individual task, but as stated the more you add the more you'll reward verbose languages (I think?)... One possible work around could be just to double things (i.e. have six tasks and make your implementation score, your code length x 2). \$\endgroup\$ – Alconja Jun 9 '16 at 11:11
0
\$\begingroup\$

Distance between two words

You are given an input of two strings consisting entirely of letter characters. The "distance" between two such strings is the number of operations from the following list that it takes in order to transform one word into the other:

  1. Adding a letter anywhere
  2. Removing a letter anywhere
  3. Changing a letter's case

Since your boss wants to avoid wear on the office keyboards as much as possible, you have to write a very short program to determine the distance between words so you can fix the typos.

\$\endgroup\$
  • 2
    \$\begingroup\$ Closely related. \$\endgroup\$ – Leaky Nun Jun 10 '16 at 13:56
  • \$\begingroup\$ Almost a duplicate of Leaky Nun's link. The only difference is that the linked challenge allows for straight substitution, whereas here it's two operations (a deletion and an insertion). \$\endgroup\$ – AdmBorkBork Jun 10 '16 at 13:59
  • \$\begingroup\$ Thanks guys, I had a brief look for dupes but couldn't find anything. If I come up with a good twist I'll edit the OP otherwise I suppose this is dead. \$\endgroup\$ – A Simmons Jun 10 '16 at 13:59
0
\$\begingroup\$

Cross Validated

(This challenge is almost complete, but something doesn't feel quite right)

Continuing the theme of using site names as challenges...

Your task

Write a program or function that accepts a string, and prints out the location, size, and validity of each cross in the string.

Definitions

  • Valid Cross- A cross where all four spokes of the cross are equal in length. The size of the cross is the number of segments of each cross.

Valid, size 0:

+

Valid, size 3:

   |
   |
   |
---+---
   |
   |
   |
  • Invalid cross- A cross where one or more spoke is a different length. The size is the number of segments of the longest spoke.

Invalid, size 2:

 |
 |
-+--
 |

Invalid, size 6:

+------

Rules

  • Each input will have one or more crosses.
  • The program should print out the location of the center of each cross. The location is zero-indexed and measured in characters/lines from the top left.
  • The size and validity, as defined above, of each cross should be printed out.
  • Each test case must pass without printing to STDERR.
  • Crosses will not overlap
  • Your program can take input via a string (with line breaks), an array of strings (each representing a line), or a 2d array of characters.
  • This is so shortest program, in bytes, wins

Test Cases

+ +-

(0,0) size 0, valid

(2,0) size 1, invalid

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

(3,3) size 3, valid

(9,5) size 4, invalid

(empty test case)

(must not crash or print to STDERR)

\$\endgroup\$
0
\$\begingroup\$

This question isn't fair.

I want you to tell me the chances of flipping an coin n times and ending up on tails.

Naturally this isn't a fair coin. In fact, it isn't even a standard unfair coin, where the chance of flipping tails is always p. This is a sticky coin, where the chance of the coin staying the same is p; the coin is fair at other times.

The coin starts off heads, so when n is 0 or p is 1 then the answer is always 0.

Your program or function should be capable of calculating the result to at least six significant digits.

This is , so the shortest program wins!

\$\endgroup\$
  • \$\begingroup\$ What does "the coin is fair at other times" mean? \$\endgroup\$ – Leaky Nun Jun 16 '16 at 13:12
  • \$\begingroup\$ @LeakyNun Sorry, I'm not sure what you're trying to ask there. A fair coin is one which is equally likely to produce heads or tails but there is no way of predicting which. This coin isn't always fair; a proportion of the time p it repeats the last result. \$\endgroup\$ – Neil Jun 16 '16 at 14:22
  • \$\begingroup\$ You said that the chance of the coin staying the same is p. Then, isn't the chance of it being different 1-p? So, do you mean that 1-p = 50%? \$\endgroup\$ – Leaky Nun Jun 16 '16 at 14:25
  • 1
    \$\begingroup\$ I think it means that the chance of the coin staying the same is p + (1-p)/2 and the chance of the coin changing is (1-p)/2. \$\endgroup\$ – Emigna Jun 16 '16 at 14:37
  • \$\begingroup\$ @LeakyNun Ah, sorry, the chance of it being sticky is p, and of being fair is ¬p. \$\endgroup\$ – Neil Jun 16 '16 at 15:24
  • \$\begingroup\$ Meaning, that the chance of it being the same is p+(1-p)/2 and the chance of it being different is (1-p)/2. What a meaningful obfuscation. \$\endgroup\$ – Leaky Nun Jun 16 '16 at 18:42
  • 2
    \$\begingroup\$ That means that the chance of it not changing is p + (1-p)/2 = (1+p)/2, and Sp3000's closed form needs changing to (1 - p^n)/2. It's still not exactly an interesting function to golf. \$\endgroup\$ – Peter Taylor Jun 16 '16 at 18:43
  • \$\begingroup\$ I can see I should have described the coin of having a chance q of flipping, and you needed to calculate the probability of an odd number of flips in n trials. \$\endgroup\$ – Neil Jun 16 '16 at 18:53
  • \$\begingroup\$ (Removed my previous comment because I misunderstood and thought the probabilities were p and 1-p for same/change, but ditto Peter's comment) \$\endgroup\$ – Sp3000 Jun 16 '16 at 22:59
0
\$\begingroup\$

"Optimize" a RegEx

Introduction

Inspired by atrociously large regex's like

/[0-9A-Za-z!@#$%&*()_\-+={[}\]|\:;"'<,>.?\/\\~`]+[0-9A-Za-z!@#$%&*()_\-+={[}\]|\:;"'<,>.?\/\\~`]*/g

I propose a challenge to create a string representing an optimized and sorted regex from an input string of characters expected to be matched.

Rules

  • only printable ASCII characters with code points 32 - 127 need to be supported:
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

The RegEx output string should:

  • Group 3 or more consecutive code points in the input string together like begin-end
  • Sort the characters and groups in order of ascending code point
  • Escape the literal character - to \- to differentiate it from a range

The RegEx output string should not:

  • Escape the characters !$()*+./=?[\]^{|}
  • Support any RegEx escape sequences like \w, \d or \s

Examples

Input:
helloworld
Output:
dehlorw

Input:
fedcabXZYVWU
Output:
U-Za-f

Input:
q0`p[|iOf(oc61TSr4dVwQ8m;%YDAPM*a/2j&h~u}
Output:
%&(*/-2468;ADMO-QSTVY[`acdfh-jmo-ruw|-~

Just so people can see what the last one's pattern is, here are the ASCII indices:

37,38,40,42,47-50,52,54,56,59,65,68,77,79-81,83,84,86,89,91,96,97,99,100,102,104-106,109,111-114,117,119,124-126

Spoiler Alert

Example implementation in JavaScript ES6:

f=s=>[...s] // spread string into array
  .sort() // sort array by ASCII indices
  .map(
    c=>c.charCodeAt() // convert each one to ASCII index
  ).reduce( // reduce sorted indices
    (p,c)=>(
      ~p[0][0]+c? // if last index is not one less than current index
        p.unshift([c]): // then start new run with this index
        p[0].unshift(c) // else continue existing run
      ,p
    ),
    [[]] // start reduce with empty run
  ).map( // map array of runs
    a=>(
      (
        a=a.map( // map each run
          n=>( // convert index back to ASCII
            c=String.fromCharCode(n),
            c=='-'? // if '-'
              '\-': // then escape it
              c
          )
        ),
        a.length>2? // if run has more than 2 indices
          [a[0],'-',a.pop()]: // keep only the begin and end
          a // else keep whole run
      ).reverse().join`` // reverse and join run
    )
  ).reverse().join`` // reverse and join array

\$\endgroup\$
  • 2
    \$\begingroup\$ This question seems to be about optimising regex character classes, not full regexes. Is that correct? \$\endgroup\$ – FryAmTheEggman Jun 17 '16 at 19:46
  • \$\begingroup\$ @FryAmTheEggman I suppose you could say that. That's a more wordy title though so I just kept it simple. \$\endgroup\$ – Patrick Roberts Jun 17 '16 at 19:47
  • \$\begingroup\$ I could understand not requiring any escaping on the grounds that it's a minor detail. I could understand requiring enough escaping to make this actually a useful tool. But it seems really odd to require escaping - but not ]. \$\endgroup\$ – Peter Taylor Jun 17 '16 at 22:07
  • \$\begingroup\$ @PeterTaylor I decided to escape only the characters that are necessary to determine whether an execution is correct or not. If you have an alternate suggestion, please feel free. \$\endgroup\$ – Patrick Roberts Jun 18 '16 at 1:53
0
\$\begingroup\$

Exercise your kids

I want you to output the nth verse of this kid's exercise song:

Head, and shoulders, knees and toes, knees and toes,
Head, and shoulders, knees and toes, knees and toes
And eyes and ears and mouth and nose,
Head, and shoulders, knees and toes, knees and toes.

Each verse is the same as the previous except that all occurrences of one word is masked by replacing it with a dash (you can use a two-byte dash of your choice) wherever it appears in the verse. The words are replaced in order however the word "and" is never replaced, therefore the next verse should look like this:

—, and shoulders, knees and toes, knees and toes,
—, and shoulders, knees and toes, knees and toes
And eyes and ears and mouth and nose,
—, and shoulders, knees and toes, knees and toes.

Also, the last verse should look like this:

—, and —, — and —, — and —,
—, and —, — and —, — and —
And — and — and — and —,
—, and —, — and —, — and —.

Your answer should specify whether n will range from 0 to 8 or 1 to 9.

\$\endgroup\$
  • 1
    \$\begingroup\$ Could you show us what the second verse would look like? \$\endgroup\$ – Leaky Nun Jun 21 '16 at 10:26
  • \$\begingroup\$ Although it can be deduced from the numbers, I'd recommend changing "one word is masked" to "all occurrences of one word are masked" to be explicit. \$\endgroup\$ – trichoplax Jun 21 '16 at 10:32
  • \$\begingroup\$ Is this a challenge involving Unicode as the main topic? If not, can we replace (U+2014) by a simple hyphen - (U+002D)? \$\endgroup\$ – Leaky Nun Jun 21 '16 at 10:34
  • \$\begingroup\$ @LeakyNun No, but you may replace it with a double hyphen, as that's still 2 bytes. \$\endgroup\$ – Neil Jun 21 '16 at 10:38
  • \$\begingroup\$ Actually, it is 3 bytes. \$\endgroup\$ – Leaky Nun Jun 21 '16 at 11:05
  • \$\begingroup\$ Something to note is that "and" is the only word in the verse that starts with the letter "a". That means something like \b(?!a)\w+ will have its first match be the word to replace each time. Also, I don't believe any of the words are prefixes/postfixes of each other, so once you have them you can blindly replace all occurrences of them. This isn't a problem or anything, I just wanted to make sure you knew in case you wanted it to be harder. \$\endgroup\$ – FryAmTheEggman Jun 21 '16 at 12:50
  • \$\begingroup\$ codegolf.stackexchange.com/q/100153/34718 \$\endgroup\$ – mbomb007 Nov 17 '16 at 15:27
0
\$\begingroup\$

Calculate the Average Squared Error

Given a line y = mx + b and a set of n points (xi, yi), find the average square error between the given line and each set of points.

Formula

Your goal is to create a function or program that given the values m, b, and the set of points (xi, yi), outputs the average square error according to the formula above.

Rules

  • This is so the shortest solution wins.
  • Builtins that compute this value are not allowed. This includes builtins that compute a result which is a scaled value of this.
  • Floating-point inaccuracies will not be counted against you.

Test Cases

tba

\$\endgroup\$
0
\$\begingroup\$

Index sum and strip my matrix

Given a matrix/2d array in your preferable language

Input:

  • The matrix will always have an odd length
  • The matrix will always be perfectly square
  • The matrix values can be any integer in your language (positive or negative)

Example:

1  2  3  4  5  6  7
2  3  4  5  6  7  8
3  4  50 6  7  8  9
4  5  6 100 8  9  10
5  6  7  8 -9  10 11
6  7  8  9  10 11 12
7  8 900 10 11 12 0

Definitions:

  • The "central number" is defined as the number that has the same amount of numbers to the left,right,up and down

In this case its middlemost 1000

  • The "outer shell" is the collection of numbers which their x and y index is or 0 or the matrix size

1  2  3  4  5  6  7
2                 8
3                 9
4                 10
5                 11
6                 12
7  8 900 10 11 12 0

Your task:

Add to the central number the sum of each row and column after multiplying the values in each by their 1-based index

A single row for example

4  5  6  7  8

for each number

number * index + number * index.....

4*1 + 5*2 + 6*3 + 7*4 + 8*5 => 100

example:

 2 -3 -9  4  7  1  5  => 61
-2  0 -2 -7 -7 -7 -4  => -141
 6 -3 -2 -2 -3  2  1  => -10
 8 -8  4  1 -8  2  0  => -20
-5  6  7 -1  8  4  8  => 144
 1  5  7  8  7 -9 -5  => 10
 7  7 -2  2 -7 -8  0  => -60
                         |
78 65 60 45 -15 -89 10   => 154
                     |
                     => -16
  • For all rows and columns you combine these values..
  • Now you sum these too => 154-16 = 138
  • You add that number to the "central number" and remove the "outer shell" of the matrix

 0 -2 -7 -7 -7     => -88
-3 -2 -2 -3  2     => -15
-8  4 1+138 -8  2  => 395
 6  7 -1  8  4     => 69
 5  7  8  7 -9     => 26

19 69 442 30 -26

do this untill you end up with a single number

-2 -2 -3     => -15
 4  1060 -8  => 2100
 7 -1  8     => 29

27 2115 5
  • Add 2114+2147 to 1060
  • Remove the "outer shell" and get 5321
  • Now we have a single number left

this is the output!

test cases:

-6

-6

-7 -1  8
-4 -6  7
-3 -6  6

2

 6  7 -2  5  1
-2  6 -4 -2  3
-1 -4  0 -2 -7
 0  1  4 -4  8
-8 -6 -5  0  2

-365

 8  3  5  6  6 -7  5
 6  2  4 -2 -1  8  3
 2  1 -5  3  8  2 -3
 3 -1  0  7 -6  7 -5
 0 -8 -4 -9 -4  2 -8
 8 -9 -3  5  7  8  5
 8 -1  4  5  1 -4  8

17611

-9 -7  2  1  1 -2  3 -7 -3  6  7  1  0
-7 -8 -9 -2  7 -2  5  4  7 -7  8 -9  8
-4  4 -1  0  1  5 -3  7  1 -2 -9  4  8
 4  8  1 -1  0  7  4  6 -9  3 -9  3 -9
-6 -8 -4 -8 -9  2  1  1 -8  8  2  6 -4
-8 -5  1  1  2 -9  3  7  2  5 -6 -1  2
-8 -5 -7 -4 -9 -2  5  0  2 -4  2  0 -2
-3 -6 -3  2 -9  8  1 -5  5  0 -4 -1 -9
-9 -9 -8  0 -5 -7  1 -2  1 -4 -1  5  7
-6 -9  4 -2  8  7 -9 -5  3 -1  1  8  4
-6  6 -3 -4  3  5  6  8 -2  5 -1 -7 -9
-1  7 -9  4  6  7  6 -8  5  1  0 -3  0
-3 -2  5 -4  0  0  0 -1  7  4 -9 -4  2

-28473770
\$\endgroup\$
  • \$\begingroup\$ yes, that is much better. hard when English is your 3rd language \$\endgroup\$ – downrep_nation Jun 21 '16 at 18:02
  • \$\begingroup\$ No worries, English is a pretty incomprehensible language no matter who is speaking it ;) Anyway, you identify the central number as "the zero", but the example you gave actually has two zeros. Perhaps change the array or change the wording to the "middlemost zero"? \$\endgroup\$ – FryAmTheEggman Jun 21 '16 at 18:07
  • \$\begingroup\$ For the process to work I think you need the matrix to be square, but I don't see a statement of that anywhere. \$\endgroup\$ – Peter Taylor Jun 21 '16 at 20:26
  • \$\begingroup\$ added that @FryAmTheEggman also changed \$\endgroup\$ – downrep_nation Jun 22 '16 at 16:52
0
\$\begingroup\$

White Water Rafting


This problem is about finding the best path through a bunch of rocks on a 5-column wide river, without crashing your raft. A river looks like this (* reprsents a rock):

. . . R .
. R . . .
R . . . .
. . R . .
R . . . .
. . . . R

Each row will contain exactly 1 rock, no more, no less. Your raft can start on any space without a rock.

You can't maneuver your raft too much, so as you travel down the river, there are only 3 next places you can go (x is the next space):

. . @ . .
. x x x .

If there is a rock in your way, you can't go there. Your raft can't fit through rocks that are diagonally adjacent to each other. You can't beach your raft either. Finally, you can't go anywhere that would result in you crashing your raft.

@ . . . .
R x . . .   <- Can't go on rock, can't go oob

R . . . .
. R @ . .
. . R X .   <- Can't go through diagonal rocks

. @ . R .
. R x . .   <- Can go through non-adjacent diagonals,
R . . . .      Can't go to dead end.

Because you don't have much space on the raft to write this code, shortest code wins.

Test cases:

Input:

. R . . .
. R . . .
. . . R .
. . . R .
R . . . .

Output:

R x . . .
. R x . .
. x . R .
x . . R .
R x . . .

Input:

R . . . .
R . . . .
R . . . .
R . . . .
R . . . .

Output:

R x . . .
R x . . .
R x . . .
R x . . .
R x . . .

Input:

. R . . .
. R . . .
. R . . .
. R . . .
R . . . .

Output:

. R x . .
. R x . .
. R x . .
. R x . .
R x . . .

Input:

. . . . R
. . . R .
. . R . .
. R . . .
. . R . .

Output:

x . . . R
x . . R .
x . R . .
x R . . .
x . R . .

Input:

. . . . R
. . . R .
. . R . .
. R . . .
R . . . .

Output:

[nothing] or [empty/blank array/matrix]

Notes:

  • Input can be in array of indexes, array of truthy/falsey values, or any other input format most comfortable to your language.
  • Output should indicate the left-most valid path.
  • Output can be in array of indexes, array of truthy/falsey values, or any other input format most comfortable to your language.
    • Output does not have to be in the same format as input.
    • Output nothing/(empty/blank) (array/matrix) if there is no valid path
  • Standard loopholes are forbidden by default.

This is my first challenge, so please let me know if I have left anything out or something is unclear.


Related problems

I couldn't find any dupe targets looking through , so I'll look again in and later.

\$\endgroup\$
  • \$\begingroup\$ I don't have 10 minutes now to sort through all of the dupe targets to work out which one is the most similar, but I guarantee that there is something similar enough that this is a dupe. \$\endgroup\$ – Peter Taylor Jun 23 '16 at 9:55
0
\$\begingroup\$

Cypher-o-mania!

The year is 19XX.

You are a spy of some distant country, and your job is to send messages across the globe.

Unfortunately, because, frankly, you suck at being a spy, you need a way to obfuscate your information, so that when the opposition catches you (which they will), they won't know what the heck is written.

How are you going to do this?

Your task is, using two inputs (the first input the encoding "cypher" and the second the message), encode the message.

This is how the encoding works:

  • The message only consists of the lowercase letters and the numerals.
  • Because there are 36 different characters in total, we will convert each individual letter of the message to "base 9" (a = 00, b = 01, c = 02... 8 = 37, 9 = 38). This will be called the FSO, or First-Stage Obfuscation.
    • For example, the message hello1 would then be translated to 07 04 12 12 15 28.
  • Each individual "bit" of the FSO is then stripped of its first part. This will be known as the SSO, or Second-Stage Obfuscation.
    • The example 07 04 12 12 15 28 is then translated to 7 4 2 2 5 8.
  • This is where the encoder comes in handy! The encoder will consist of a string of numbers 0 to 3 (e.g. 1212003).
  • You then add to the start of each digit of the encoder to the corresponding digit of the SSO. This is now the TSO, or Third-Stage Obfuscation.
    • The example 7 4 2 2 5 8 with the encoder 1212003 is then converted to 17 24 12 22 05 08.
    • With a shorter encoder (say 121), this step will "wrap around", so 7 4 2 2 5 8 with the encoder 121 will end up with 17 24 12 12 25 18.
  • We then change the TSO back into readable characters, using the same "base 9" method.
    • The two examples 17 24 12 22 05 08 and 17 24 12 12 25 18 will be converted to QWLUEI and QWLLXR respectively.

So, in summary:

Encoder: 121

Message: hello1

hello1 => 07 04 12 12 15 28 => 7 4 2 2 5 8 => 17 24 12 12 25 18 => QWLLXR

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

META

  • This is really confusing, and I don't really know how to phrase the "how the encoding works" bit better. Can anyone help me phrase this better? I can offer clarification on certain things if needed.
\$\endgroup\$
  • \$\begingroup\$ This is basically a mildly astandard and irreversible Vigenère cipher, so it's virtually a dupe of this question. (I would also say that it violates one of the key criteria for being a good question, which is to have a motivation. The backstory IMO isn't a motivation because it doesn't explain why anyone would want to implement or use what's really a supremely bad hash function). \$\endgroup\$ – Peter Taylor Jun 23 '16 at 13:36
  • \$\begingroup\$ @PeterTaylor Yeah, IK. I need a lot of things to fix with this question (I was extremely tired at the time, couldn't think of a nice backstory). Also, a few things about the dupe: ONE, it's 5 years ago, so there's bound to be some new answers out there (if it's even a dupe in the first place), and TWO, how is it a dupe? \$\endgroup\$ – Qwerp-Derp Jun 24 '16 at 10:55
  • \$\begingroup\$ It's the difference between for (i=0 to n-1) s[i] = handleWrapping(s[i] + k[i % klen]) and for (i=0 to n-1) s[i] = handleWrapping(s[i] % 9 + k[i % klen] * 9). As far as I'm concerned that's a very minor transformation. \$\endgroup\$ – Peter Taylor Jun 24 '16 at 11:03
  • \$\begingroup\$ @PeterTaylor Yeah, I kinda understand now. Still some questions, though. ONE: What language is that? TWO: Is there any way I could improve on my explaining? \$\endgroup\$ – Qwerp-Derp Jun 24 '16 at 11:22
  • \$\begingroup\$ 1. It's pseudocode, because I didn't want to faff around working out what escaping a less-than sign needs in comments. 2. I'm not quite sure what you're asking, but I would ditch this idea completely and try to find something more original. See e.g. meta.codegolf.stackexchange.com/q/1475/194 \$\endgroup\$ – Peter Taylor Jun 24 '16 at 11:49
  • \$\begingroup\$ @PeterTaylor Yeah, I can see those, but most of those ideas have been taken already, and I kinda want to move away from numbers for a bit and play around a bit with strings and whatnot. Any suggestions? \$\endgroup\$ – Qwerp-Derp Jun 24 '16 at 12:36
0
\$\begingroup\$

Regex golf: Match the Thu'um-s

Introduction

Skyrim is a game made by Bethesda and came out in 2011. One of the objectives of the game is to collect every 27 shouts (or Thu'um-s). In this challenge, you need to match every shout and nothing else.

Shouts

This is the list of the available shouts in the game:

Raan Mir Tah
Laas Yah Nir
Mid Vur Shaan
Feim Zii Gron
Gol Hah Dov
Od Ah Viing
Hun Kaal Zoor
Lok Vah Koor
Ven Gaar Nos
Zun Haal Viik
Faas Ru Maar
Mul Qah Diiv
Joor Zah Frul
Gaan Lah Haas
Su Grah Dun
Yol Toor Shul
Fo Krah Diin
Liz Slen Nus
Kaan Drem Ov
Krii Lun Aus
Rii Vaaz Zol
Tiid Klo Ul
Strun Bah Qo
Dur Neh Viir
Zul Mey Gut
Fus Ro Dah
Wuld Nah Kest

Additionally, every shout can have 3 levels depending on what the player collected so far, each level adds a new word to each shout, so you need to be able t match the separate words without the full shout.

The words need to be uppercase. A shout should only be matched, if it is a separate word, for example: Golf shouldn't be matched.

The separate words for the same shout in the order as in the list appear next to each other, then they need to be in the same match.

The input strings will only contain ASCII letters and spaces as word separators.

Test cases

The matched text is bold

Hydrogen Sulphur Krah Coal Gaan Lah Haas

one two three four Kaal six seven Joor Zah Frul eleven

red green blue Gol Hah orange purple Qo violet

Ran Miir Taah Raan Mir Tah raan mir tah

Golf Gol Middleage Mid

Rules

  • The answer should be a .NET type RegEx and should not contain any other langauge.

  • This is a code-golf, so the shortest answer in bytes wins

\$\endgroup\$
  • 2
    \$\begingroup\$ Very closely related. What if a word appears in lower case in the input? What if it appears inside another word like Golf? If the latter should not be matched please clarify what characters can be in the input and which of those are valid word delimiters. All that said, I don't see anyone coming up with a good way to compress the words within the limit framework of regex. \$\endgroup\$ – Martin Ender Jun 23 '16 at 12:18
  • \$\begingroup\$ @MartinEnder I clarified it a but \$\endgroup\$ – Bálint Jun 23 '16 at 13:16
  • 1
    \$\begingroup\$ Still doesn't say what characters can appear in the input and what characters count as word separators (I'm assuming only letters and spaces, and spaces are separators, but if that's your intention you should say so explicitly, and if not, you should add further test cases). Looks good otherwise. To prevent confusion you might want to say explicitly that people should submit only a regex and which flavours are allowed (and whether flavours like Perl are allowed to make use of their eval features to execute code in the hosting language). \$\endgroup\$ – Martin Ender Jun 23 '16 at 13:21
  • \$\begingroup\$ If only one language is allowed this would limit the participation in your question. I don't understand why it should be only one language. \$\endgroup\$ – george Jun 29 '16 at 19:38
  • \$\begingroup\$ @george I don't think you know what regex-golf is \$\endgroup\$ – Bálint Jun 29 '16 at 19:44
  • \$\begingroup\$ @Bálint Whoops I didn't see your title, my mistake. \$\endgroup\$ – george Jun 29 '16 at 19:47
0
\$\begingroup\$

Find all the Vampire numbers

Shamelessly stolen from https://stackoverflow.com/q/17352108

A "Vampire" number is defined as the product of two numbers of equal length (known as the "fangs") that uses the same digits as the two numbers being multiplied. Examples:

21 * 60 = 1260
15 * 93 = 1395
30 * 51 = 1530

Your task is to find all the Vampire numbers whose fangs have n digits.

This is , so the shortest solution wins.

\$\endgroup\$
  • \$\begingroup\$ What about double fangs, triple fangs etc? \$\endgroup\$ – Qwerp-Derp Jun 24 '16 at 11:30
  • \$\begingroup\$ @DerpfacePython Double fangs? But I suppose I could generalise it to m fangs of n digits if there's enough support (and if there are actually solutions!) \$\endgroup\$ – Neil Jun 24 '16 at 12:19
  • \$\begingroup\$ Related \$\endgroup\$ – FryAmTheEggman Jun 24 '16 at 13:23
  • \$\begingroup\$ @FryAmTheEggman My bad for not searching first. I might as well delete this. \$\endgroup\$ – Neil Jun 24 '16 at 14:14
  • \$\begingroup\$ I think all you have to do is add the double/triple fang thing and it probably is different enough? Not sure, but there is probably a way to get it to work. \$\endgroup\$ – FryAmTheEggman Jun 24 '16 at 14:20
0
\$\begingroup\$

Title TBD - Generate Emoticons :)

Your task is to create a program that generates the most emoticons using the least amount of code.

Rules

  • The only valid emoticons are listed on Wikipedia, under the heading Western/horizontal emoticons: List of emoticons page (version 722951221)
  • The output can be any format, as long as a delimiter exists between emoticons.

Scoring

  • Scores will reflect the character (not byte) count.
  • For every emoticon after 10 that is output by your program, subtract 1 from your score. Emoticons over 20, subtract 2, over 30 subtract 3, and so on.

Sandbox

Is the scoring fair/reasonable? Should I edit down the list/create a new list of acceptable emoticons?

\$\endgroup\$
0
\$\begingroup\$

Forecast Romantic Dates

Sort of inspired by this.

A Romantic date is a date that, when the year, month and day are converted to Roman Numerals the individual values contain no more than two symbols. For example, in YY-MM-DD format: the Romantic date 20-04-15 would become XX-IV-XV.

For the purpose of this challenge, years will only be tracked by the two least significant digits of the year, as otherwise the last Romantic date was in the 15th century. In addition, they wouldn't add much to the challenge as the omissions of the leap year every 400 years is irrelevant, as February the 29th is not a Romantic date.

Romantic dates

For your convenience, here is a list of all of the two digit numbers that can be represented with two or fewer symbols in Roman numerals:

[1, 2, 4, 5, 6, 9, 10, 11, 15, 20, 40, 50, 51, 55, 60]

These were determined using the "standard method" that negative groups would only be used with the symbols that are powers of ten and only on the values that are five or ten times that symbol's value. So I only combines with V and X for example.

Dates which include only numbers from this list are Romantic dates. For the purpose of this challenge, assume an ideal Western calendar: no dates are ever skipped or repeated, 12 months per year, and more than 20 days per month. Assume there is no year, month or day zero (i.e. year 99 loops to 1 not to 0).

Task

Given a date as input, output that date if it is Romantic, or output the next Romantic date.

Input and Output

You may accept input in any consistent ordering of year, month and day with any consistent separator. You may specify if the input should have the numbers padded to be two digits. If the numbers are padded, you may choose to have no separator. Your output must have the same form as your input.

Test Cases

The following test cases are all in the format YY MM DD, with no padding.

1 1 1 => 1 1 1
20 4 3 => 20 4 4
15 7 1 => 15 9 1
51 9 7 => 51 9 9
70 9 7 => 1 1 1
20 6 24 => 20 9 1
47 12 1 => 50 1 1
60 11 24 => 1 1 1

Here is the script that I used to generate these.

Sandbox

Did I miss any Romantic numbers? I just did that by hand.

Allow unary? I'm unsure about this because it sort of violates the reasoning behind Romantic dates for the values to have >2 symbols...

Should I explain more about parts of dates that are not useful? For example, the length of the months is entirely irrelevant as the later days are all skipped. My concern is that the current one feels clunky already

Should I allow both outputting the input if the date is already Romantic or the strictly next Romantic date (as long as it is consistent)? There doesn't seem to be much different, but I don't know if that'd be too broad? Personally leading towards allowing it.

I'm also somewhat tempted to make use of the silly title a bit more, but I'm not sure if that'd be going overboard.

Too boring / compression based? I've particularly been trying to think of a way for fewer results to wrap back around to 1.

\$\endgroup\$
  • \$\begingroup\$ That rule should be spelt out explicitly in the question, because although some people insist on it it's a modern innovation. There are actual Roman inscriptions which do use e.g. IC. \$\endgroup\$ – Peter Taylor Jun 24 '16 at 21:05
  • \$\begingroup\$ @PeterTaylor You're right, I originally left out the reasoning because I thought it might clutter up the spec, but I realise now I just left that comment undeleted to prevent people from asking the same question. I don't have time right now but I'll edit it in once I get a chance. Also, I figured it was better with this rule because I thought say VL was rather unintuitive, does that make sense or should I be more laissez-faire about it? \$\endgroup\$ – FryAmTheEggman Jun 24 '16 at 22:04
0
\$\begingroup\$

Stacks and Stacks and Stacks...

Write a program that, with the input as n, finds the first n-gonal and n-gonal pyramid number that is NOT 1.

n is guaranteed to be larger than or equal to 3.

Examples:

  • n = 3: 10
  • n = 4: 4900
  • n = 2: The output can be nothing, False, or anything that you want, just as long as it can be distinguished from an actual output.

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

Bonus:

  • If your code output both the name of the n-gon and the number: You get a big fat -50% off of your byte count (see below for examples).
    • n = 4: Square 4900
    • n = 3: Triangle 10
    • n = 5: Pentagon ??? (the ??? is a placeholder because I have no idea what the number is)

Meta:

  • Is the bonus a good idea?
\$\endgroup\$
  • \$\begingroup\$ I don't think the bonus is a good idea because 1) the name compression takes away from the original challenge and likely isn't worth it and 2) you haven't defined the naming scheme (e.g. 12-gon vs dodecagon) \$\endgroup\$ – Sp3000 Jun 26 '16 at 7:10
  • \$\begingroup\$ @Sp3000 Ah, OK. I really want to incorporate the use of strings in the challenge, but if the idea sucks, then I'll scrap it. Any further suggestions? \$\endgroup\$ – Qwerp-Derp Jun 26 '16 at 7:12
  • 2
    \$\begingroup\$ Adding strings just makes it feel like squeezing two challenges into one, unfortunately. I'd recommend posting the shape names as a separate challenge, but I see we have this challenge. As for suggestions, maybe 1) remove the part about n = 2, since you already say n is guaranteed to be at least 3 and 2) maybe make it explicit that the output should be both n-gonal and n-gonal pyramidal (and maybe explain, say, that 10 is the 4th triangular and 3rd triangular pyramid number) \$\endgroup\$ – Sp3000 Jun 26 '16 at 7:16
  • \$\begingroup\$ Hmm my other problem is - what happens if there's no solution for a given n? Note the only reason I'm asking is because the number of solutions for any n could be finite, e.g. A027568. (6 is 946, 8 is 1045, 10 is 175 and 11 is 23725 I believe) \$\endgroup\$ – Sp3000 Jun 26 '16 at 9:28
  • \$\begingroup\$ Yeah, that could be a problem... maybe a time limit? Or maybe check numbers up to a given range. \$\endgroup\$ – Qwerp-Derp Jun 28 '16 at 6:50
  • \$\begingroup\$ One alternative could be to allow solutions to potentially infinite loop/hit memory or recursion errors in the case of no solution/large solution. Numerical limit to check up to could work too, that'd probably be better than a time limit (since it reduces a dependency) \$\endgroup\$ – Sp3000 Jun 28 '16 at 9:02
  • \$\begingroup\$ @Sp3000 I would probably go with the numerical limit/memory limit thing, whichever comes first. But what about golfing/esoteric languages? There might not necessarily be a memory/numerical bound for those. \$\endgroup\$ – Qwerp-Derp Jun 29 '16 at 9:04
0
\$\begingroup\$

Pyth Meta-Golf Golf Battery

(now that's a name, isn't it?)

The Challenge

Write a program in a language of your choice that takes an input of code in the same language and outputs a code that does the same thing in Pyth (though not necessarily the shortest code).

Rules

Given the test battery set below, you should try to find the best way to minimize your score with the following rules:

  • You must minimize the source code of the submission.
    • You may not used compressed versions of the input source for each test; the Pyth code must be output procedurally.
    • The code must theoretically do the same conversion for any input code, not necessarily just these test cases.
  • You must minimize the input code of each test.
    • If an input is shown to be shortenable by without non-standard libraries of the submitted language, you must change it immediately to the shorter answer. If your answer does not support this change, then you must change your answer to accommodate.
  • You may not submit answers written in Pyth.

Scoring is done with the following equation:

(source code)*((Pyth src out, test 1)/(input src in, test 1)+(same for test 2)+...)

Objectives of each test

Test 1:

Output the string "Hello, world!".

Test 2:

Given an integer input, multiply that input by three and output it.

Test 3:

Quine. (must be a valid quine in the submitted language and in Pyth)

Test 4:

Produce infinite output.

Test 5:

Cat program.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'm not a Pyth expert, but I strongly suspect that what this asks is impossible in many languages. E.g. I understand that Python's multi-threading support is extremely limited. Even if true impossibility is not an option, answers in many languages won't fit inside the 30000-character limit. E.g. I don't think the grammar for Java fits inside the limit, let alone a lexer and parser. \$\endgroup\$ – Peter Taylor Jun 27 '16 at 9:56
  • 1
    \$\begingroup\$ I agree with Peter, that this seems like unless you use only trivial languages it probably won't be possible to answer. The scoring would also make this confusing: to make sure a solution is correct one would have to not only test 10 programs, you would also have to golf 5 programs. Further, there is a bit of a problem in Pyth's $ operator, which runs literal Python, which means you should probably ban Python as well. I'm not really sure of how to turn this into a good question, too heavily restricting the type of program seems to be the only way, but it also seems to defeat the purpose. \$\endgroup\$ – FryAmTheEggman Jun 27 '16 at 13:09
0
\$\begingroup\$

Don't even think about non-42-related numbers!


Introduction and Credit

We all love our Answer to the Ultimate Question of Life, the Universe, and Everything which, of course is 42. So let's take this unworthy Fibonacci-Sequence thingy and adapt it to be worthy of 42!

Specification

Input

The input will be a positive integer.

Output

The output will be either true or false.

What to do?

Your task is to implement the predicate that the number under consideration is an element of the generalized Fibonacci-Sequence given by:

a_1 = 14
a_2 = 42
a_n = 41 * a_{n-1} + 43 * a_{n-2}

Where 42 is the ultimate answer, 41 and 43 are the primes next to it and 14 is the preceding catalan number.

Potential corner cases

The number will always be greater than zero. Your program must pass all (32-bit) test vectors below.

Who wins?

This is code-golf so the shortest answer in bytes wins!
Standard rules apply of course.

Test Vectors

14 -> true
42 -> true
2324 -> true
4080622 -> true
97090 -> true
171480372 -> true
7 -> false
1 -> false
41 -> false
43 -> false
\$\endgroup\$
  • \$\begingroup\$ a_3 is already outside the range of 8-bit unsigned integers, a_6 is outside the range of 32-bit signed integers, and a_11 is outside the range of 64-bit signed integers. It would be worth addressing this issue and at least ensuring that languages which are inherently 8-bit can't just special-case the two values which they can handle. \$\endgroup\$ – Peter Taylor Jun 25 '16 at 21:58
  • \$\begingroup\$ @PeterTaylor I'm unsure how to formulate this without disqualifying legitimate approaches. Would saying "your program must pass all test vectors" (with 32-bit test vectors) also be considered OK for most people? \$\endgroup\$ – SEJPM Jun 25 '16 at 22:16
  • \$\begingroup\$ I feel like this is too much two separate challenges: one to test for membership in the sequence, and the other to takeWhile on a condition. I also suspect the sequence has a direct arithmetic membership test like the one where n is a Fibonacci number exactly if either 5*n*n+4 or 5*n*n-4 is a square. \$\endgroup\$ – xnor Jun 25 '16 at 23:27
  • \$\begingroup\$ What is takewhile? \$\endgroup\$ – Qwerp-Derp Jun 26 '16 at 7:02
  • \$\begingroup\$ @xnor, I originally only wanted to do the takeWhile, but needed a (mediumly) complex, interesting predicate, so I came up with this one. Of course I'm open to suggestion for more suitable interesting predicates. \$\endgroup\$ – SEJPM Jun 26 '16 at 10:18
  • \$\begingroup\$ @DerpfacePython, the higher-order functionality described in the second paragraph of "what to do?" is also called takewhile, I've clarified this though. \$\endgroup\$ – SEJPM Jun 26 '16 at 10:21
  • \$\begingroup\$ @SEJPM I think the other way -- to do a challenge about takeWhile, make the predicate as simple possible. Beware chameleon challenges and needless fluff. One clean condition would be integers being positive. \$\endgroup\$ – xnor Jun 26 '16 at 10:56
0
\$\begingroup\$

Compute the mincut of a graph

Given a graph, compute a division of the graph such that the edges stranded between the cut.

hayo mouseover readers; leave a comment if you see this!

Red line: a cut

Green line: a mincut

Input

The first line will contain the number of nodes. The rest of the lines will contain pairs of positive integer IDs separated by spaces showing connectedness between the nodes with those IDs. Here's an example; for a graph where 1 is connected to 2 and 2 is connected to 3:

3
1 2
2 3
  • You may assume that the nodes are numbered consecutively from one to the number of nodes.
  • However, you may not assume that the list of pairs of nodes is in any specific order.

Output

Simply output a comma-separated list of the IDs of the nodes of one of subgraphs created by the cut.

Additional Rules!

  • You cannot implement brute-force search. Other than that, feel free to use Karger's Algorithm* or another algorithm. Remember that Karger's algorithm is likely the easiest to implement.
  • Notice: you must run Karger's algorithm at least this many times to ensure a low chance of failure and a low chance of failure

*Karger's algorithm

For your convenience, I've included a simple description of Karger's algorithm.

  1. find two adjacent nodes and merge them into one node (so that all nodes that where connected to the original two nodes are connected to the new node), concatenating the labels
  2. repeat step one until there are only two nodes
  3. the result is any label of one of the nodes
  4. repeat steps 1-3 at least this many times to ensure a low probability of failure, and choose the result that occurs the most often
\$\endgroup\$
  • 1
    \$\begingroup\$ 1. Wouldn't it be better to take the graph as an adjacency matrix or list? 2. Your description of the minimum cut is somewhat confusing. 3. Karger's algorithm is probabilistic, which isn't allowed by our defaults (I don't think). Allowing probabilistic algorithms opens up a whole can of worms (for instance I could write a program that just returns a random cut) -- you should probably make it so that the algorithm must return the minimum cut two-thirds of the time or something similar if you want to allow them. \$\endgroup\$ – a spaghetto Jul 5 '16 at 0:07
  • \$\begingroup\$ @quartata 1. it's an adjacency list 2. yeah I need help with that 3. I made sure you had to repeat it insert some math equation here amount of times \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jul 5 '16 at 0:13
  • \$\begingroup\$ Sorry I misunderstood the input. \$\endgroup\$ – a spaghetto Jul 5 '16 at 0:14
  • \$\begingroup\$ Generally adjacency lists are done like [node1, connected_node1, connected_node2, ...] and not in pairs like you have it; this is more flexible and you don't have to specify the number of nodes (it is just the length of the input list) \$\endgroup\$ – a spaghetto Jul 5 '16 at 0:35
  • 2
    \$\begingroup\$ "You cannot implement brute-force search" is too vague. What about a basically brute force search that shortcuts some obviously wrong possibilities? I think what you want is a running time bound. \$\endgroup\$ – xnor Jul 5 '16 at 1:55
  • 1
    \$\begingroup\$ 1. The I/O description seems to assume that all answers will be programs taking input on stdin and writing output to stdout, but our defaults are more flexible. In particular, by default we allow answers to be functions which take arrays and return arrays. Comma-separating is also IMO unnecessarily constrained, especially as the input isn't comma-separated. \$\endgroup\$ – Peter Taylor Jul 5 '16 at 7:51
  • 1
    \$\begingroup\$ 2. "Feel free to use Karger's algorithm or another algorithm". There's an implicit licence here to use another non-deterministic algorithm, but although you give an explicit iteration count for Karger's algorithm you don't for e.g. randomised Kruskal's algorithm, which it's based on. 3. Besides which, in general I don't think that questions should tell people which algorithm to use. Specify the task and constraints (e.g. "Randomised algorithms are allowed, but must find the correct answer with probability at least foo. All answers must be polynomial-time"). \$\endgroup\$ – Peter Taylor Jul 5 '16 at 7:54
  • \$\begingroup\$ 4. But if you're going to include an algorithm description, be careful to get it right. Karger's algorithm is randomised, but in the description given there's no mention of where the random selection occurs or of what uniformity constraints are required to get the desired behaviour. \$\endgroup\$ – Peter Taylor Jul 5 '16 at 7:55
  • 1
    \$\begingroup\$ Food for thought: outputting the value of the min cut instead might lend to more approaches. Also, any rules on min cut/max flow/possibly other optimisation builtins? \$\endgroup\$ – Sp3000 Jul 5 '16 at 10:34
  • \$\begingroup\$ I'm going to add a story to this soon. \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jul 5 '16 at 13:55
0
\$\begingroup\$

Generate a random Vietnamese syllable

tags:


The Vietnamese syllable space is interesting, because it is huge.

TODO: Describe the space and why it is interesting.

Here's how such syllables are made:

The onset matches the regex ^([bcdđghklmnprstvx]|qu|[cgkpt]h|ng|tr)$

The vowel is one of the following massive list:

a à a' ã á a.
â â` â' â~ â´ â.
a. ă` ă' ă~ ă´ ă.
e è e' e~ é e.
ê ê` ê' ê~ ê´ ê.
i ì i' ĩ í i. ia iê
o ò o' õ ó o. oa oă oe
ô ô` ô' ô~ ô´ ô.
o' ò' o" õ' ó' o'.
u ù u' ũ ú u. ua uâ uê ui uô uo' uy
u' ù' u" ũ' ú' u'. u'a u'o'
y y` y' y~ ý y. ya yê

The coda matches the regex ^([iouycptmn]|ch|ng|nh)$

(thanks Peter Taylor!)

The onset, vowel and coda are concatenated to make the result syllable.

Objective

The objective is to generate random Vietnamese syllables. Your program has to take no input and as output include only the syllable, with an optional trailing new line.

Clarifications

  • Each syllable must be generated with a non zero probability.

I think it's unclear. Contributions are so much welcome.

\$\endgroup\$
  • \$\begingroup\$ 1. I'm not sure what you mean by can be with. 2. You don't mention randomness anywhere excwpt the clarification. 3. Object should probably be Objective. \$\endgroup\$ – Dennis Jul 3 '16 at 18:44
  • \$\begingroup\$ 1. c can also be with h means that h can follow c as the 2nd stage letter in the syllable. 2. Where should I also mention it? 3. Ah k :) \$\endgroup\$ – user48538 Jul 3 '16 at 18:46
  • \$\begingroup\$ If I'm reading this correcting then it can be vastly simplified by saying that the onset matches the regex ^([bcdđghklmnprstvx]|qu|[cgkpt]h|ng|tr)$, the vowel is one of a massive set of options (I don't see any benefit to splitting that into "stage 2" and "stage 3"), and the coda matches the regex ^([iouycptmn]|ch|ng|nh)$ \$\endgroup\$ – Peter Taylor Jul 4 '16 at 16:36
0
\$\begingroup\$

Let's play some Briscola

Briscola is an Italian game, played with a deck of 40 cards, divided in 4 suits - coins (denari - D), swords (spade - S), cups (coppe - C) and clubs (bastoni - B).

The values on the cards range numerically from one through seven, plus 3 special cards - knave (11), knight (12) and king (13).

Gameplay:

After the deck is shuffled, each player is dealt three cards. The next card is placed face up on the playing surface, and the remaining deck is placed face down. This card is the Briscola, and represents the trump suit for the game.

First player starts by playing one card face up on the playing surface. Each player subsequently plays a card in turn, until all players have played one card.

The winner of that hand is determined as follows: If any briscola (trump) has been played, the player who played the highest valued trump wins, else the player who played the highest card of the lead suit (suit of the first card played) wins.

Ranking

Briscola has a special type of ranking:

1   ace
3   three
13  king
12  knight
11  knave
7
6
5
4
2

Rules:

Standard loopholes apply.

Input:

As an input, you must accept 5 values (cards), in a reasonable format, for example:

briscola (trump card), 1. card, 2. card, 3. card, 4.card

Output:

You must output the winning card

Example input and output:

4S 7D 12B 13B 2S -> 2S
5D 1D 5D 12S 3C -> 1D
3B 2C 4S 5S 7D -> 2C
12D 3S 11B 1B 7S -> 3S
\$\endgroup\$
  • \$\begingroup\$ As mentioned in chat, I think this is probably a duplicate of this challenge. Just adding so other people don't have to go looking. \$\endgroup\$ – FryAmTheEggman Jul 6 '16 at 21:15
0
\$\begingroup\$

nth number that multiplies k equals its reverse

Tags: ,


It's quite simple, given n and k, output the nth number such that, if the number is multiplied by k and its digits reversed, it equals the original number. Both input and output are positive numbers.


The challenge originally is from Mego, posted on my broken challenge. Firstly, I used 4 instead of k, but based on my tests, only 1 and 4 values gives output, so I decided to put 4 instead of k, finally I put k back. But the challenge would be ruin with that putting "9"*(n-1) between 2178, so no loopholes will be permitted.

I just posted here for further discussions, suggestions and improvements.

\$\endgroup\$
  • \$\begingroup\$ Those numbers are positive right? \$\endgroup\$ – Fatalize Jul 6 '16 at 7:52
  • \$\begingroup\$ Please add some examples of expected outputs. \$\endgroup\$ – Fatalize Jul 6 '16 at 7:53
  • \$\begingroup\$ Also you might want to prevent people from hardcoding 2178 in any fashion in their code so that they have to compute the numbers, because it seems they all are of the form 21X...X78 where X...X is a series of nines (except for the first one, which is 0). \$\endgroup\$ – Fatalize Jul 6 '16 at 7:56
  • \$\begingroup\$ According to the community advises, I'm not allowed to prevent people use methods those work perfectly. \$\endgroup\$ – Ehsaan Jul 6 '16 at 8:23
  • \$\begingroup\$ Let's wait to see what others think. I personally don't think it's very interesting if people are allowed to hardcode the "format" of those numbers. \$\endgroup\$ – Fatalize Jul 6 '16 at 8:26
  • \$\begingroup\$ Me neither, I think the challenge isn't interesting at all. \$\endgroup\$ – Ehsaan Jul 6 '16 at 8:43
  • 1
    \$\begingroup\$ I think there's no good way to prevent hardcoding. Maybe making "4" were an input parameter as well would make solutions actually search for an answer? \$\endgroup\$ – xnor Jul 6 '16 at 9:01
  • \$\begingroup\$ @xnor You mean make 4 as k input? \$\endgroup\$ – Ehsaan Jul 6 '16 at 9:33
  • \$\begingroup\$ @Ehsaan Yes, exactly. \$\endgroup\$ – xnor Jul 7 '16 at 9:09
  • \$\begingroup\$ 9 works too: 1089 * 9 = 9801. \$\endgroup\$ – Neil Jul 10 '16 at 17:36
0
\$\begingroup\$

Write a program that can determine the median value of a read-only (static, const, immutable) sequence of unsorted numbers (array, list, stream) but minimises storage, without completely sacrificing speed.

The basic bracket is that if we copied all the values into a sorted list and then picked the middle one (or average of the middle pair), it would require storage of the whole sequence, so the storage would be 'n', and the performance would be O(n log n).

The score is the total cost of finding the median of 1 bn values, divided by 1 bn, at a cost of 8 per value stored, 1 per comparison or numerical operation and 1 per read, for the worst case. Thus if our insertion sort costs exactly n*log2(n), the for 1 bn values the total score is 1 for the read, 29.8 for the sort + 8 for the storage, for a total of 37.8.

If instead we skimmed the whole range to get the average (costing 1 for the read and 1 for the summation), we could then only store some portion of the range to sort; but then we would need a second pass to be sure that there were an equal number of values above and below this median (at the cost of another 2).

Lowest score wins, low-level languages (C/C++/D) only so that we can count the actual operations.

\$\endgroup\$
  • 3
    \$\begingroup\$ 1. It's not clear to me what counts as a "value stored" or a "read", and I think there are probably gray areas with "comparison or numerical operation" too. (E.g. in C is if (foo) a comparison?) 2. "The score is the total cost ... for the worst case." For any non-trivial algorithm, the full calculation of this score risks being longer than the code. There's a reason that complexity theorists deal with Landau notation rather than exact operation counts. \$\endgroup\$ – Peter Taylor Jul 7 '16 at 13:39
0
\$\begingroup\$

Reinventing the Modularization Wheel

In a language of your choice, implement a function or language construct that imports another file of the same language and executes it, making exported values from that file available to the calling file. If one already exists, you may not use it in your implementation.

For example, in Node, you would have to implement require() without using require(), even indirectly. In C, you would implement a function or construct equivalent to #include without using #include in the implementation. In Python, you would implement import. In client-side JavaScript, I suppose the closest equivalent would be <script src="..."></script>. So JavaScript implementations would be restricted to AJAX calls only, since <script> tags would not be allowed in the implementation.

This is not to say that you aren't allowed to use the built-in import at all, but only use them in the implementation. The intention here is to reinvent the wheel.

Requirements

  • Do not include the built-in modularization in any way in your import implementation.
  • Standard libraries only.
  • Byte-count includes the implementation itself, and any special changes that need to exist on the file being imported, if any.
  • The function or construct accepts a relative file path. As long as this is satisfied, you may extend the functionality of your modularization to have global imports, or even remote imports (like using a URL as input).
  • The imported file must have a construct for denoting values that must be exported. Only these values should be directly accessible from the calling file.
  • Using the built-in export function or construct of your language is acceptable, and if it is a built-in, it does not need to be included in your byte-count.
  • If your language does not have modularization, then implementing a mechanic for exporting should be included in your byte-count.
  • Document the usage of your function or construct.

This is and the shortest answer in bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Perhaps just restrict this to languages which support modularization to avoid loopholes \$\endgroup\$ – Downgoat Jul 7 '16 at 18:45
  • \$\begingroup\$ @Downgoat if people wanted to use a built-in for reading a plaintext file, and then use an eval()-like built-in to execute it in a way that exposes only denoted values (however you define that), I think it would be acceptable. What sort of loopholes do you foresee? \$\endgroup\$ – Patrick Roberts Jul 7 '16 at 18:49
0
\$\begingroup\$

Print a Pilcrow Scarecrow

Print the following ascii scarecrow using the pilcrow character

    ¶¶¶
   ¶¶¶¶¶
    ¶¶¶
    ¶¶¶  ¶
 ¶¶¶¶¶¶¶¶¶¶
    ¶¶¶
    ¶¶¶
   ¶ ¶ ¶
  ¶¶ ¶ ¶¶
     ¶
     ¶
¶¶¶¶¶¶¶¶¶¶¶
  • Padding must be with (space) and built with
  • Trailing padding is okay
  • Print to stdout
  • This is

\$\endgroup\$
0
\$\begingroup\$

It's time to unify!


Introduction

Wouldn't it be awesome if they whole world would be united and there would be no conflicts and disputes? Now while you can't unify nations, you certainly can unify expressions to resolve their unknown relation and conflicts.
Your mission is simple: Unify the world (of expressions)!
And of course, because you're lazy you want to do this with the least effort (read: code-length) possible.

Specification

Input

Your input will be a unification problem. You can format it however you want and need, as long as you don't encode additional information to what is given in the standard / example format. Encoding the number of arguments per function into the input is allowed but not mandatory, you can also just derive this from the input.

Example format:
Your first input will be list of function symbols, which is represented as a list of pairs of strings and non-negative integers.
Your second input will be a list of equalities (you may represent each as a string), which represent the unification problem. They will be represented as a list of strings as well. Anything which is not a parenthesis or an equality sign can be considered a variable. If the number of arguments is 0, parenthesis are omitted.

Example input: [("f",1),("g",2),("h",3),("a",0)], [x=f((g(a,y)),y=h(g(f(a),z),f(z),a)]

Output

The output is either some falsy value or something representing a list of equalities. It is allowed to use the empty list to indicate a falsy value.

What to do?

You need to unify the inputs you got. In the end there must only be variables on the left side of the equality-signs if the you didn't encounter an error. If you did you need to report it (-> false or empty list).

To do the unification, you can - but don't have to - use Martelli and Montanari's algorithm, which goes as follows:

E is always the (complete) set of equalities except the current one
x,y,z are variables, f,g,h are functions, t1,t2, ...,tn,s1,...,sn are arbitrary terms (compositions of functions and variables)
{x=x} E => E, e.g. if you encounter two equivalent variables, discard
{f(t1,...,tn)=f(s1,...,sn)} E => {t1=s1,t2=s2,...,tn=sn} E, e.g. if you encounter the same function on both sides, unify the arguments along with your rest
{f(t1,...,tn}=g(s1,...,sn)} E => Error, if the symbols are different, you can't succeed
{x=f(t1,...,tn)} E => {x=f(t1,...,tn)} E[x -> f(t1,...,tn)], e.g. if you see a variable equals a term, replace the variable with this term in all other expressions
{x=f(t1,...,tn)} E => Error, e.g. if any of the t1,..,tn contain x at some point
{f(t1,...,tn)=x} E => {x=f(t1,...,tn)} E, e.g. if you see a variable "naked" on the right side, swap the sides

Two step-by-step examples are provided below additionally to the test cases.

Corner Cases

You can get an empty list of function symbols, this means you have exclusively variables in the second input.
The input list of equalities will never be empty, your code does not need to handle this case.

Who wins?

This is code-golf so the shortest answer in bytes wins!
Standard rules apply of course.

Test-cases

All these test cases use the functions [("a",0),("b",0),("f",1),("g",1),("h",2)]

[x=b] -> [x=b]
[a=x] -> [x=a]
[a=b] -> []
[y=f(x)] -> [y=f(x)] 
[x=f(x)] -> []
[f(x)=f(y)] -> [x=y] 
[f(x)=g(y)] -> []
[h(x,y)=h(a,b)] -> [x=a,y=b] 
[x=f(z),y=f(a),x=y] -> [x=f(a),y=f(a),z=a]
[h(x,f(y))=z,z=h(f(y),v)] -> [x=f(y),v=f(y),z=h(f(y),f(y))]

Step-By-Step Example

Example 1: Test Case 9
[x=f(z),y=f(a),x=y] => (replace x in third equation with first x)
[x=f(z),y=f(a),f(z)=y] => (replace y in third equation)
[x=f(z),y=f(a),f(z)=f(a)] => (remove f's in third equation)
[x=f(z),y=f(a),z=a] => (replace the z in the first expression)
[x=f(a),y=f(a),z=a]

Example 2:
Let [("f",2),("g",2),("a",0),("b",0)] be your functions
[f(g(a,x),g(y,b)=f(x,g(v,w)),f(x,g(v,w))=f(g(x,a),g(v,b))] => (remove f in second equation)
[f(g(a,x),g(y,b)=f(x,g(v,w)),x=g(x,a),g(v,w)=g(v,b))] => (function symbol missmatch in equation 2)
[]
\$\endgroup\$
0
\$\begingroup\$

create a golfed down regexp that matches all substrings

inspired by Determine the "Luck" of a string where I found a way to golf almost 30 bytes at once
(with a falling trick for that challenge, but I still like the idea).

The word "lucky" contains 15 different substrings:

  • lucky
  • luck, ucky
  • luc, uck, cky
  • lu, uc, ck, ky
  • l, u, c, k, y

Challenge
Create a program or function that, for a given string s, creates the shortest possible regexp using basic PCRE syntax that matches and returns all substrings of s and nothing else.

  • code needs not to be case sensible
  • basic syntax means: alternatives, quantifiers, grouping and custom character classes (e.g. [abc])
  • other features (assertions, backreferences, recursion etc.) may be used, but are not required to qualify
  • the result may include delimiters and modifiers

The result for lucky would be l?ucky?|l?uc?|c?ky?|l|c|y.


  • is the description sufficient?
  • the challenge not too easy, not too hard?
  • any other hints you might have?
  • I will add test cases that expose possible bugs (like silly and digdug)
  • not sure yet if I will go for shortest code yet
\$\endgroup\$
0
\$\begingroup\$

Write a Gopher Interpreter

This code golf challenge will task you with writing an interpreter for an esolang I created a while back called Gopher, Details on the language can be found Here

Pass Conditions

This challenge requires you to create an Interpreter (Or you could go a step ahead and create a Compile/Transpiler) however for the code to pass as correct it must meet the following criteria

  • Take in a single input being the Gopher Code
  • Output the result of the Interpreted code

  • Invalid code does not need to be handled, however you may do so if you wish

  • As this is code-golf the smallest byte size wins

Example Input and Output

Input:

&++<'×<&÷+<^-<<×-<#!+<$@-<&@<×-<@++<@<.!<=

Output:

Hello World
\$\endgroup\$
  • \$\begingroup\$ Thanks for using the Sandbox! Anyway, you should add the relevant information on Gopher to the body of this post, as if your github account/repo dies or is changed people still need to be able to answer this question. \$\endgroup\$ – FryAmTheEggman Jul 11 '16 at 17:15
0
\$\begingroup\$

Having had a look, it seems there isn't a challenge for "Given any date, output the day of the week". Is that a challenge worth having?

Something like

"Given an input date, in the form dd/mm/yyyy, output the day of the week"

Shortest code wins

What do we think? perhaps this already exists and I didn't find it.

\$\endgroup\$
  • 3
    \$\begingroup\$ Duplicate \$\endgroup\$ – AdmBorkBork Jul 11 '16 at 14:04
  • 2
    \$\begingroup\$ Glad I checked! \$\endgroup\$ – Matt Jul 11 '16 at 14:05

You must log in to answer this question.

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