title: Executable haiku that outputs a haiku

text:
# Question
Title: Executable haiku that outputs a haiku
**Puzzle:**

Write a short, three-line program which:

* has 5/7/5 syllables per line when read aloud
* outputs a haiku when run.

An example of a program having the correct structure, but non-haiku output, is (Python):

```
>>> for x in range(3):
...     print "EXTERMINATE HUMANS"
... # I am a Dalek.
...
EXTERMINATE HUMANS
EXTERMINATE HUMANS
EXTERMINATE HUMANS

```

(The comment is a bit of a cop-out.)

This reads aloud as:

> for x in range three
>
> print EXTERMINATE HUMANS!
>
> I am a Dalek.

Any language is acceptable. For the purposes of reading aloud, symbols like `!@#$%^&*()_+` can be ignored if you want, or pronounced aloud, admitting something like Waka Waka Bang Splat. (I'm sure there will be a Perl entry like `!***(!:, )(*@@@#, )_(*)!.`)

Extra points if either the code or the output is especially funny, or especially zen.

---

Edit: If your language requires boilerplate before it can do anything interesting (`#include <iostream>`?) then I'm happy to ignore the boilerplate.

---

I've accepted Paul Richter's Common Lisp haiku on the grounds that it made me laugh for a good five minutes.

Honorable mention for Timwi's creative rule-bending (*compiler* output?!) and for the extremely memorable line `"Static void. I long for you."`

> Now this question ends;
>
> Many more haikus await.
>
> **Continue posting!**

# Answer
> 46 votes
## Common Lisp

Parentheses are silent!

Program:

```
((lambda (&rest foo)
   (list foo (cons 'truly foo) foo))
 'this 'is 'lisp 'haiku)

```

Read as:

```
lambda and rest foo
list foo cons truly foo foo
this is lisp haiku

```

Output:

```
((THIS IS LISP HAIKU) (TRULY THIS IS LISP HAIKU) (THIS IS LISP HAIKU))

```

# Answer
> 79 votes
# C#

Program:

```
#warning Lonesome
class _{
    static void Eye(long forYou='
        ){ /* My program ends here. */ ;}}

```

Read:

```
Warning: Lonesome class.
Static void. I long for you.
My program ends here.

```

*Compiler* output:

```
#warning: 'Lonesome'        (read: hash warning lonesome)
Empty character literal     (read: empty character lit’ral)
Newline in constant

```

# Answer
> 50 votes
## Piet, 867 executing color blocks

Grand Prize, you say? This has codel size of 2.

Output:

```
SPRING EVER RETURNS
NEVER EXACTLY THE SAME
THIS IS NOT A QUINE

```

This challenge was fun! I've written a Piet instruction encoder that takes instructions and translates them into a Piet script. It's short work from there to generate code to print a given string. I put a small (but effective) amount of effort into golfing the Piet code while only using single-codel instructions.

I then made a pixel font. For every pixel in a character, I blow it up into 4 codels: 2 black, and 2 executed. The first codel encountered is non-executing, so if a segment of a character has *n* pixels, for example, that corresponds to 2\*n\*-1 instructions.

The lines down the sides reverse the direction pointer and move it down by 2 pixels, taking it to the next row. Thus, instructions are reversed on every other line.

Once I had code to produce "text embedded in text", it gets fun. I probably wrote 20 haiku along the way, but I eventually settled. By tweaking the font; adding / removing serifs, rounding corners, changing height / width, etc., I was able to alter the total number of nonwhite pixels in the image such that the Piet code fit exactly into the image text.

Bonus! You can make your own quinelike haiku! http://pastebin.com/zxc9V3UX

# Answer
> 23 votes
## Perl

```
$_
= "Repeating myself"
;print"$_\nis like $_.\n$_.\n";

```

How to read it out loud:

```
dollar underscore
equals repeating myself
print nis like line noise.

```

Output:

```
Repeating myself
is like Repeating myself.
Repeating myself.

```

# Answer
> 19 votes
## INTERCAL

INTERCAL has limited output capabilities, but "limited capabilities" has never stopped me from writing an INTERCAL program!

```
DO READ OUT #18
+#3301
+#214
PLEASE GIVE UP

```

Please read \[out\] this as:

```
Do read out eighteen,
Three thousand three hundred one,
Two hundred fourteen.

```

(Note that my boilerplate is at the end of the program instead of at the beginning.)

The program produces the output:

```
XVIII

MMMCCCI

CCXIV

```

Which, when spoken aloud, goes:

```
Ex vee eye eye eye,
Em em em cee cee cee eye,
Cee cee ex eye vee.

```

# Answer
> 13 votes
## CoffeeScript

With tongue firmly in cheek, I present CoffeeScript:

```
here = "my haiku"
were_doomed() unless 1 is 1
alert Date.now()

```

Pronounced:

```
Here is my haiku
We're doomed unless one is one
alert date dot now

```

If your timing is right (!), your output might be e.g. 1337181872717, pronounced:

```
one three three seven
one eight one eight seven two
seven one seven

```

Considering my first run at this was one microsecond out from a valid haiku response, I think that's zen enough to qualify!

NB: I'd be happy to hear sufficiently zen alternatives for my first two (admittedly weak) lines.

# Answer
> 10 votes
# J

Program:

```
p:i.4
*:*:*:i.3
!8

```

Read (substituting verb names):

```
Prime Integers Four
Square Square Square Integers 3
Factorial Eight

```

Output (read numbers out loud):

```
2 3 5 7
0 1 256                          (Read: Zero One Two-Fifty-Six)
40320                            (Read: Forty Three-Twenty)

```

# Answer
> 8 votes
## Python

Code:

```
for _ in range(1,3):
    print 'Hi ' * 5, 'there ' *  2 * (-1+_)
print 'I now', 'go ' * 3

```

How to read:

```
for in range one three
print hi five there two one plus
print i now go three

```

Output:

```
Hi Hi Hi Hi Hi
Hi Hi Hi Hi Hi  there there
I now go go go

```

Working sample: http://ideone.com/hDniW

# Answer
> 7 votes
## logo

Here's a Haiku procedure that's also a quine procedure (easy because of logo's introspection capability)

```
to better_yourself
  printout "better_yourself
end ; as you began

```

Read as

> To better yourself
> Print out quote better yourself
> End as you began

# Answer
> 3 votes
# JavaScript (doesn't work in Firefox)

```
             (function haiku() { with (
console) log ((('' + haiku). // output
replace)     (/[ !-@{-~[-^]+/gim, ' ')); void haiku })()

```

works except for mozilla
javascript engine and shows
spelling after ran

# Answer
> 3 votes
## Ruby

```
"A ruby haiku.
Why, yes, it is."; print open(
__FILE__).read #this now, please.

```

Read as:

```
A ruby haiku.
Why, yes, it is. Print open
file. Read this now, please.

```

It doesn't flow very well, unfortunately. In my defense, it *is* 12:50am...

# Answer
> 3 votes
# Python

(Only read the first level of parentheses (not the second)).

Code and how to read:

```
for e in range(3):                      # for e in range three
    if True is False: what = then       # if true is false, what is then?
    print "oh " * (5 + 2 * (e & 1))     # print oh times _seven_

```

Output, probably most basic haiku in the world:

```
oh oh oh oh oh
oh oh oh oh oh oh oh
oh oh oh oh oh

```

# Answer
> 3 votes
# Python (2 entries)

## Entry 1: A haiku in time

You need to save this in a file and run it from the same directory. This haiku very slowly prints itself out to screen, a poem in words and time.

```
from time import sleep
for line in open(__file__):
  print line; sleep(len(line))

```

## Entry 2: A haiku without symbolism

This is similar to the above, but was an attempt to write a Python haiku that used just keywords and minimal brackets or substitutions of symbols (eg. `=` pronounced as "is").

```
if __file__ is not None:
 for line in open(__file__):
  print not False and line

```

# Answer
> 2 votes
# Tcl

Here's a self-documenting, self-outputting, example:

```
catch {me as I make}
proc unknown args {puts [read $args]}
[open [info script]]

```

# Answer
> 0 votes
# Vim

```
ia0 <esc><c-x>
YpA-<esc>
px5<c-x><c-x>

```

read as

```
i a zero x
Y p A hyphen escape
p x five x x

```

Writes:

```
a-1
a-1-
-7

```

read as:

```
a negative one
a minus one negative
negative seven

```

# Answer
> 0 votes
# Python 3

```
print(print.__doc__[:15])
print(print.__doc__[13:][:13])
print(print.__doc__[32])

```

Read as:

```
print print doc one five
print print doc one three one three
print print doc three two

```

Prints:

```
print(value, ..
..., sep=' ',
\

```

Read as:

```
print value dot dot
ellipses, sep equals blank
reverse solidus

```

---
Tags: code-challenge
---


title: Quick Golf: The Gold Leader

text:
# Question
Title: Quick Golf: The Gold Leader
## Challenge

Using data from the API here, output the names of the three countries with the most Olympic gold medals at the 2016 Rio Olympic Games (i.e. the first element of the returned list).

For example, at the time of posting (18:23 UTC+1, Monday, 15th August), the USA, the UK and China have the most gold medals, so the output would be:

```
United States
Great Britain
China

```

The country names must be separated by newlines and you may have a leading or trailing newlines.

Once the Olympics have finished, the program does not have to work as expected.

URL shorteners are disallowed but JSON parsing libraries are allowed.

**This is code golf, so the shortest code in bytes wins.**

I'm going to keep trying to get an Olympics themed challenge in here

## Leaderboard

```
var QUESTION_ID=89919,OVERRIDE_USER=30525;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# bash + w3m + grep + cut, ~~65~~ ~~59~~ ~~58~~ 54 bytes

```
w3m medalbot.com/api/v1/medals|grep -m3 m|cut -d\" -f4

```
* 6 bytes less thanks to @Joe's suggestions.
* 1 byte less thanks to @YOU.
* 4 bytes less thanks to @manatwork's suggestion that *the medalbot API seems to work without www. subdomain too*.
> 12 votes

# Answer
# C (+sockets), ~~433~~ ~~429~~ ~~280~~ ~~276~~ ~~270~~ 259 bytes

```
#define H"medalbot.com"
char**p,B[999],*b=B;main(f){connect(f=socket(2,1,getaddrinfo("www."H,"80",0,&p)),p[4],16);send(f,"GET http://"H"/api/v1/medals HTTP/1.1\r\nHost:"H"\r\n\r\n",69);read(f,b,998);for(f=3;f--;puts(p))b=strchr(p=strstr(++b,"_n")+9,34),*b=0;}

```

So it turns out that C isn't great at downloading resources from the internet and parsing them as JSON. Who knew?

This code is (naturally) super lax with error checking, so I guess if medalbot.com wanted to send malicious data they'd be able to trigger buffer overflows, etc. Also the latest code expects certain values for the constants (e.g. `AF_INET = 2`) which will *probably* be the case everywhere, but it's not guaranteed.

Here's the original code which isn't so fragile (but still isn't very robust or safe):

```
#include<netdb.h>
#define H"medalbot.com"
char*b,*B,d[999];struct addrinfo*p,h;main(f){h.ai_socktype=SOCK_STREAM;getaddrinfo("www."H,"80",&h,&p);f=socket(p->ai_family,p->ai_socktype,p->ai_protocol);connect(f,p->ai_addr,p->ai_addrlen);send(f,"GET http://"H"/api/v1/medals HTTP/1.1\r\nHost: "H":80\r\nConnection: close\r\n\r\n",92,0);recv(f,d,998,0);for(f=0,b=d;f<3;++f)B=strstr(b,"_n")+9,b=strchr(B,'}'),*strchr(B,'"')=0,puts(B);}

```

Breakdown:

```
                            // No imports needed whatsoever!
#define H"medalbot.com"     // Re-use the host in multiple places
char**p,                    // This is actually a "struct addrinfo*"
    B[999],                 // The download buffer (global to init with 0)
    *b=B;                   // A mutable pointer to the buffer

main(f){
    // Hope for the best: try the first suggested address with no fallback:
    // (medalbot.com runs on Heroku which has dynamic IPs, so we must look up the
    // IP each time using getaddrinfo)
    f=socket(2,1,getaddrinfo("www."H,"80",0,&p));
                            // 2 = AF_INET
                            // 1 = SOCK_STREAM
                            //     (may not match getaddrinfo, but works anyway)
                            // 0 = IP protocol (getaddrinfo returns 0 on success)
    connect(f,p[4],16);     // struct addrinfo contains a "struct sockaddr" pointer
                            // which is aligned at 32 bytes (4*8)

    // Send the HTTP request (not quite standard, but works. 69 bytes long)
    send(f,"GET http://"H"/api/v1/medals HTTP/1.1\r\nHost:"H"\r\n\r\n",69);
    // (omit flags arg in send and hope 0 will be assumed)

    read(f,b,998);          // Get first 998 bytes of response; same as recv(...,0)

    // Loop through the top 3 & print country names:
    // (p is re-used as a char* now)
    for(f=3;f--;puts(p))        // Loop and print:
        p=strstr(++b,"_n")+9,   //  Find "country_name": "
        b=strchr(p,34),         //  Jump to closing "
        *b=0;                   //  Set the closing " to \0
}

```

This isn't very nice for the server since we don't send `Connection: close\r\n` as part of the HTTP request. It also omits the `Accept` header since medalbot.com doesn't seem to be using compression in any case, and misses the space after `Host:` (again, the server seems to be OK with this). It doesn't seem as though anything else can be removed though.

---

Once the olympics end, the most likely behaviour for this program is to segfault trying to read memory location 9. Unless an evil hacker takes over the domain, in which case the most likely behaviour is for it to set some byte to 0 in the address info structs, which probably isn't too dangerous actually. But who can tell with these evil hackers?
> 13 votes

# Answer
## PowerShell v4+, ~~88~~ 69 bytes

```
(ConvertFrom-Json(iwr medalbot.com/api/v1/medals))[0..2].country_name

```

Uses `iwr` (the alias for `Invoke-WebRequest`) to grab the API. We feed that as the input parameter to the `ConvertFrom-Json` built-in that pulls the JSON text into a custom object array. We encapsulate that object array in parens, take the first three elements `[0..2]`, and take the `.country_name` of each thereof.

Requires at least v4+ for the multiple-object-properties, else we'd need to use something like `|Select "country_name"` instead. Requires at least v3+ for the `ConvertFrom-Json` built-in.

```
PS C:\Tools\Scripts\golfing> .\olympics-gold-leader.ps1
United States
Great Britain
China

```
> 12 votes

# Answer
# R, 98, 112, 108 bytes

golfed 4 thanks to @miff

```
a=jsonlite::fromJSON(readLines("http://www.medalbot.com/api/v1/medals"))
cat(a$c[order(-a$g)[1:3]],sep="\n")

```

First line imports data using a JSON library. Second line grabs the relevant country names. It sorts the countries by gold medals in increasing order, reverses the indices, and takes the first 3, printing them.
> 6 votes

# Answer
# JavaScript (ES6), 122 Bytes

```
fetch`http://www.medalbot.com/api/v1/medals`.then(a=>a.json()).then(b=>alert(b.slice(0,3).map(c=>c.country_name).join`\n`))

```

Due to a browser safety issue, this code must be run on `medalbot.com`. It does not however take advantage of that and could potentially be run elsewhere. Also note that I inserted the `\n` character, but am only counting is as one, because I could replace it with one

# Node.js (ES6), 173 Bytes

```
require("http").get("http://www.medalbot.com/api/v1/medals",s=>s.on("data",d=>t+=d,t="").on("end",q=>console.log(JSON.parse(t).slice(0,3).map(a=>a.country_name).join`\n`)))

```

This would have been so much shorter if the API returned the data all in one stretch, but since it returns in two sections, I must concatenate the parts and combine them, and then parse them.

# Node.js (ES6) + Request, 138 Bytes

```
require("request")("http://www.medalbot.com/api/v1/medals",(e,r,b)=>console.log(JSON.parse(b).slice(0,3).map(a=>a.country_name).join`\n`))

```

Better, but still not as good as the browser version. Thanks fetch API! Request is a popular HTTP client library used to simplify requests, and you can see that take effect here.
> 5 votes

# Answer
# bash \+ w3m \+ jq, ~~83~~ 59 bytes

```
w3m medalbot.com/api/v1/medals|jq -r '.[:3][].country_name'

```

Thanks to Jordan for three bytes.

Thanks to YOU for 24 more bytes! Turns out the data is sorted. Wow. :D
> 4 votes

# Answer
# Java 8, ~~261~~ 258 bytes

This uses a lambda to save a couple bytes and the net library to get the webpage. Other than that is just Java.

```
()->{try{for(int i=0;i<3;System.out.println(new java.util.Scanner(new java.net.URL("http://www.medalbot.com/api/v1/medals").openConnection().getInputStream()).useDelimiter("\\A").next().split("\n")[i++*9+3].replaceAll(".* \"|\",","")));}catch(Exception e){}}

```

Here is my (old) POJO for testing (and golfing):

```
class QuickGolf {
  static void f(h x){x.g();}
  static interface h{ void g(); }
  static void main(String[] args){
    f(
      ()->{try{for(int i=0;i<3;i++){System.out.println(new java.util.Scanner(new java.net.URL("http://www.medalbot.com/api/v1/medals").openConnection().getInputStream()).useDelimiter("\\A").next().split("\n")[i*9+3].substring(21).replace("\",",""));}}catch(Exception e){}}
    );
  }
}

```

---

**Update**

* **-3** \[16-08-17\] Move print statement *into* for loop
* **-5** \[16-08-16\] Improved regex replace
* **-9** \[16-08-16\] Removed `java.net` import
> 4 votes

# Answer
# JavaScript + jQuery, ~~114~~ 100 bytes

```
$.get("www.medalbot.com/api/v1/medals",a=>alert(a[0][c='country_name']+'\n'+a[1][c]+'\n'+a[2][c]))

```

For the reason of Cross Origin Requests, this must be run from the `medalbot.com` domain (with jQuery).

### History

* *-14 bytes thanks to @YetiCGN*
* *-2 bytes thanks to Yay295*
> 3 votes

# Answer
# Python 3, ~~202~~, 164 bytes.

Python 3 does not do short url/json handling. :/
Didn't realize the API already sorts by gold count

```
from urllib.request import*
import json
print('\n'.join(x['country_name']for x in json.loads(urlopen('http://www.medalbot.com/api/v1/medals').read().decode())[:3]))

```
> 3 votes

# Answer
# MATL, 67 bytes

```
'http://www.medalbot.com/api/v1/medals'Xi'(?<="c.+e": ")[^"]+'XX3:)

```

This doesn't work online because function `Xi` (`urlread`) is disallowed.

Example run:

```
>> matl
 > 'http://www.medalbot.com/api/v1/medals'Xi'(?<="c.+e": ")[^"]+'XX3:)
 >
United States
Great Britain
China

```

### Explanation

This reads the contents as a string and then applies the regex `'(?<="c.+e": ")[^"]+'` to extract country names. The regex uses look-behind with `"c.+e"` instead of `"country_name"` to reduce code length.

```
'http://www.medalbot.com/api/v1/medals'   % Push string representing the URL
Xi                                        % Read URL contents as a string
'(?<="c.+e": ")[^"]+'                     % String for regex matching
XX                                        % Apply regex
3:)                                       % Get first 3 results

```
> 3 votes

# Answer
# Python 2, 120 113 bytes

```
from urllib import*
for x in list(urlopen("http://www.medalbot.com/api/v1/medals"))[3:26:9]:
    print x[21:-4]

```

Thanks @Nick T and @Value Ink
> 3 votes

# Answer
# PHP, ~~205 139 124 116 111~~ 109 bytes

I just wanted to use the new spaceship operator for PHP 7 once (**EDIT**: It's superfluous, as sorting isn't required):

```
<?$d=json_decode(file_get_contents('http://www.medalbot.com/api/v1/medals'),1);usort($d,function($a,$b){$g='gold_count';return$b[$g]<=>$a[$g];});$c='country_name';foreach([0,1,2]as$i){echo$d[$i][$c]."\n";}

```

If we omit the unneccesary sorting step and assume the API delivers the data already sorted by gold\_count descending (as it would seem), we can shorten this further:

```
while($i<3)echo json_decode(file_get_contents('http://medalbot.com/api/v1/medals'))[+$i++]->country_name."
";

```

Note: The line break within the string is intentional to save a byte from \n

## History

* Ommitted some quotes and braces that will throw notice's, removed the $c variable for country\_name index. Thanks to @manatwork for these tipps to save even more characters.
* Thanks to @jeroen for pointing out the shorter while loop, also switched to object access to go from 124 to 116
* Saved 5 more bytes by calling the API within the loop. Granted, it takes longer and clobbers the API, but it's Code Golf. Needs PHP 5.5 to work because of array dereferencing.
* Saved 2 more bytes by removing the short open tag, as per this meta answer
> 2 votes

# Answer
# Ruby, ~~97~~ 79 + `-rnet/http` (11) = 90 bytes

Uses a modification of the regex pattern from Luis Mendo's MATL answer, further optimized by @Jordan, since Ruby doesn't support quantifiers in lookbehinds.

-18 bytes from @Jordan.

```
puts Net::HTTP.get("www.medalbot.com","/api/v1/medals").scan(/"c.+"(.+)"/)[0,3]

```
> 2 votes

# Answer
# Mathematica ~~96~~ 66 bytes

@alephalpha found a way to work directly from the file (without saving it), thereby saving 30 bytes!

```
Import["http://www.medalbot.com/api/v1/medals","RawJSON"][[;;3,2]]

```

`Import` imports the file as a Raw JSON file. `[[;;3,2]]`takes rows 1-3, second entry (country name).
> 2 votes

# Answer
# PowerShell, 60

```
(iwr medalbot.com/api/v1/medals|convertfrom-json)[0..2]|% c*

```

Same basic idea as TimmyD (didn't see their answer before I posted), but quite a bit shorter :-)
> 2 votes

# Answer
# BASH + w3m + core utils, 70 bytes

```
w3m www.medalbot.com/api/v1/medals|grep -m3 tr|cut -f6- -d\ |tr -d \",

```

Looks like the output comes sorted already. Just need to throw out all of the extra text.
> 1 votes

# Answer
## CJam (57 bytes)

```
"http://www.medalbot.com/api/v1/medals"gN/3>9%3<{'"/3=N}%

```

Online demo not available because it fetches content from the web. This cheats by not actually parsing JSON, but assuming that the structure won't change. (But then so do most of the existing answers, in different ways).
> 1 votes

# Answer
# Java 8 ~~386~~ ~~384~~ 459 bytes

2 bytes saved from @Easterly Irk

My first code golf submission so I'm sure there's a way to save plenty of bytes, but oh well :)

It uses Gson to read the JSON

Requires:

```
import java.util.*;
import java.io.*;

```

Golfed code:

```
void p()throws Exception{List<A> a=new com.google.gson.Gson().fromJson(new InputStreamReader((InputStream)((new java.net.URL("http://www.medalbot.com/api/v1/medals").openConnection())).getContent()),new com.google.gson.reflect.TypeToken<List<A>>(){}.getType());a.sort((b,c)->c.gold_count.compareTo(b.gold_count));for(int i=0;i<3;)System.out.println(a.get(i++).country_name);}class A{String country_name;Integer gold_count;}

```

Ungolfed Code:

```
void p() throws Exception {
    List<A> a = new com.google.gson.Gson().fromJson(new InputStreamReader((InputStream)((new java.net.URL("http://www.medalbot.com/api/v1/medals").openConnection())).getContent()),new com.google.gson.reflect.TypeToken<List<A>>(){}.getType());
    a.sort((b, c) -> c.gold_count.compareTo(b.gold_count));
    for(int i=0; i<3;)
        System.out.println(a.get(i++).country_name);
}

class A {
    String country_name;
    Integer gold_count;
}

```
> 1 votes

# Answer
# Python 2, 117 bytes

```
from requests import *
for x in get('http://www.medalbot.com/api/v1/medals').json()[:3]:
    print(x['country_name'])

```
> 1 votes

# Answer
# Clojure, 122 bytes

```
(fn[](mapv #(println(%"country_name"))(take 3(read-string(.replace(slurp"http://www.medalbot.com/api/v1/medals")":""")))))

```

No JSON library used :). Reads string from the URL, replaces colons with empty string and evals the string which results into Clojure map. Takes first 3 elements and maps eagerly function which prints `country_name` property of each elements.
> 1 votes

# Answer
# Kotlin (Script), ~~125~~ ~~121~~ 119 bytes

```
java.net.URL("http://medalbot.com/api/v1/medals").readText().lines().filter{'m' in it}.take(3).map{println(it.split('"')[3])}

```

Runnable with `kotlinc -script <filename>` or through IDEA as \*.kts file.

now, if we make a VERY big assumption about the format, including numbers of lines, we can trim it to:

```
java.net.URL("http://medalbot.com/api/v1/medals").readText().lines().slice(setOf(3,12,21)).map{println(it.split('"')[3])}

```

or even

```
java.net.URL("http://medalbot.com/api/v1/medals").readText().lines().slice(3..21 step 9).map{println(it.split('"')[3])}

```

Thanks to folks at Kotlin slack team for helping me trim a couple dozens of bytes!
> 1 votes

# Answer
## R, 97 95 bytes

```
t=rjson::fromJSON(f="http://www.medalbot.com/api/v1/medals")
for(i in 1:3)cat(t[[c(i,2)]],"\n")

```

Little improvement over user5957401's answer, no sorting required, and shorter library name. Also my first attempt at golfing ;)
> 1 votes

# Answer
## Javascript 167 bytes

```
x=new XMLHttpRequest();x.open("GET","http://www.medalbot.com/api/v1/medals",false);x.send()
i=-3;while(i++)console.log(JSON.parse(x.responseText)[i+2]["country_name"])

```
> 0 votes

---
Tags: code-golf, parsing, internet
---


title: Check if input is permutation of source

text:
# Question
Title: Check if input is permutation of source
# Inspired by Input ∩ Source Code.

---

# Task

* Your task is to determine whether the input is a permutation of the source code.

# Input

* A string. Input is flexible; it should be able to handle the character encoding used for the source code.

# Output

* You may only have two possible outputs, one when the input is a permutation of the source code, and one when it is not. Those outputs maybe be of any length (including 0) but must be distinct, consistent, and deterministic.

# Specs

* Similar to challenges, the program/function may not read its own source code and 0-byte solutions are not allowed.

# Example

If your source code is `ppcg`, then an input of `cpgp` or `ppcg` would be a permutation of the source code while `cpg` or `cggp` or `caqp` or `cpaqr` would not be.

# Answer
> 1 votes
## Python 2.7, ~~135~~ 112 bytes

```
print sorted(list(input()))==sorted(list('\''*7+'\\'*3+'print sorted(list(input()))==sorted(list(*7+*3+*2))'*2))

```

---
Tags: code-golf, string, quine, permutations
---


title: Identify a string from its substrings

text:
# Question
Title: Identify a string from its substrings
## Introduction

I've previously created two challenges where the idea is to reconstruct an object using as few query-type operations as possible; this will be the third.

## The task

Your inputs shall be a non-empty string `S` over the alphabet `abc` and its length, and your output shall be `S`. With no restrictions, this would of course be a trivial task; the catch is that you're not allowed to access `S` directly. The only thing you're allowed to do to `S` is to call the function `num_occur(T, S)`, where `T` is some other string, and `num_occur` counts the number of occurrences of `T` in `S`. Overlapping occurrences are counted as distinct, so `num_occur(T, S)` really returns the number of indices `i` such that

```
S[i, i+1, …, i+length(T)-1] == T
```

For example, `num_occur("aba", "cababaababb")` will return `3`. Note also that `num_occur(S, S)` will return `1`. The result of `num_occur("", S)` is undefined, and you should not call the function on an empty string.

In short, you should write a function or program that takes `S` and `length(S)` as inputs, calls `num_occur` on some shorter strings and `S` some number of times, reconstructs `S` from that information and returns it.

## Rules and scoring

Your goal is to write a program that makes as few calls to `num_occur` as possible. In this repository, you will find a file called `abc_strings.txt`. The file contains 100 strings, each on its own line, between lengths 50 and 99. Your score is the **total number of calls to `num_occur` on these inputs**, lower score being better. Your solution will preferably keep track of this number as it runs, and print it upon finishing. The strings are generated by choosing uniformly random letters from `abc`; you are allowed to optimize for this method of generating the strings, but **not** the strings themselves.

There is no time limit, except that you should run your solution on the test cases before submitting it. You solution should work for any valid input `S`, not just the test cases.

You are encouraged to share your implementation of `num_occur` too, if you're not using someone else's. To get the ball rolling, here's an implementation in Python:

```
def num_occur(needle, haystack):
    num = 0
    for i in range(len(haystack) - len(needle) + 1):
        if haystack[i : i + len(needle)] == needle:
            num += 1
    return num

```

# Answer
> 6 votes
## Javascript, ~~14325~~ 14311 calls

We start with an empty string and go our way recursively by adding a new letter at the end or at the beginning of the current string while we still have at least one match.

All previous results from `numOccur()` are saved in the `sym` object and we use this data to reject immediately any new string that can't possibly be a candidate.

**EDIT**: Because we always start with `'a'`, we always know the exact number of `a` in the string. We use this information to end the process earlier when we detect that only a sequence of `a` is missing. Also fixed the regular expression which was invalid in Chrome and IE.

```
var test = [
  'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
  // etc.
];
var call = 0;

function guess(S, len) {
  var sym = {};
  recurse(S, len, "", sym);
  return sym.result;
}

function recurse(S, len, s, sym) {
  var dictionary = [];

  if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
    if(s.length == len) {
      sym.result = s;
    }
    else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
      dictionary = [ Array(len - s.length + 1).join('a') ];
    }
    else {
      dictionary = [ "a", "b", "c" ];
    }
    dictionary.some(function(e) {
      return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
    });
    return true;
  }
  return false;
}

function isCandidate(s, sym) {
  return sym[s] === undefined && Object.keys(sym).every(function(k) {
    return count(s, k) <= sym[k];
  });
}

function count(s0, s1) {
  return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
  call++;
  return count(S, s);
}

test.forEach(function(S) {
  if(guess(S, S.length) != S) {
    console.log("Failed for: '" + S + "'");
  }
});
console.log(call + " calls");

```

Full executable snippet below.

```
var test = [
  'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
  'caccbbababbaaaccbcabbaabaabcacabacaababcabcbbacaac',
  'bbbbaacabcabacaccaaaabaaacaacabbcbacabaccbbcbabbcbc',
  'abbcbcbccbccaacaccaccaabaccbbcabaaccabccbbbabbbcabc',
  'aabacbbbcaaabcccaccccbcaabcacaccbabbbcccacabaaababca',
  'bccbbaaccaaccacabaaaabbbbaababacabaaabacbcacbbbbabaa',
  'bbbcbcabbacbaacbacabcbabbacacbbcbcabbaabbbccbacaaacac',
  'ccbcbbbaaaaaccbaacbabbbcbccbabaabccbcbcbcbabcbbccacba',
  'aacbcbcabcbcbccbabbacacbcaaababbbcacaacaccbabbbbabcaac',
  'bcabacaabbacccacaabcaaacbcbcbacabbababcabbbbacbaaaabbb',
  'abbaccccabbbcbbaacccacbcaacababaccabbabbacbbbaabaacbaba',
  'cabbacabacccabcabacbaacbaababcaccbacbaaaacbbabbbccabbbb',
  'bcabccaaabcbaaccaabccbbcbabaccababbbaccccacaaccaccacbcab',
  'abbcbabaacbcbbabbccccbccabcbbaccacbabcacbaacbccbcabcccbc',
  'bcbacabbaabcccabccacbcbccbcbbbccacbbccaabaacccccbcabaaccc',
  'baccbcacaccacbbbcccbaaacbaccacbbacbbbaccccacbabcbbbaacabb',
  'bcccabaaaabcbbbaaccbcaccbaabacccaaacbaabaccccacabaccacbcac',
  'baabcbbcaabcacbabbcacccbcabbabaacbbbababbbbbccccccbcbbcbcc',
  'bacacbbabbcbbcaacabcccccbbacabcaabbbcbbabaacbcbbaccaaacbbac',
  'ccabccbccbaaacbcccccabacbbabbbbccbccccabaabaabbaacbabcabbcb',
  'abbaccbcaabacbbacabaabbcbacbacacabccbbcccaccbbacbbbaacbaccab',
  'bbbbaaabababcccbbbababacbacbaabbabccacccaaacabaccababaccbcac',
  'bbcbbbbcccaccbbbcbcaaccbcacaabbbbabaaabbbaaacbbaaccbacaccabbb',
  'cacabcabcbcbbbbcabbbccccccccacaaabaacbcaabbabcacbcbcccccacaab',
  'babbcacabaabbccabcbbaacccaaccbabcbbcbcbbbcabbcccbcacbabccaccac',
  'ccbbcbcbcaacbcaaccacbcaabbbcbbaccbbabacacccccaccaababcacccccba',
  'bcccbcacccccabccabccbcbccaccaaacbcacabaabcbcccaccaaaabbcacbbcaa',
  'cbbcacbbacaacbabccaabbaabacacbcbcbabcaccabbbbcabbbabaaacccaabcc',
  'aabbaacccaaacbcaabcabaabbbaababbbbcbacabbbbbbbbccaccccbbaccbbaaa',
  'abbcccabbabbaccccaacbabbccccbbbbccaaacaabacbabbabcabacbaabcbcacb',
  'bcacbccccaacbbcaccbcbcbbabacabacabbcaaabbccabcccbaacabcbbcacababb',
  'acabacaabcabbcccccbcacaccccbccaaaacacbbbccbcaabaacbbbacabcbcaabca',
  'caabbaccaacbbcbaacbcabccacacabbcbcbbacabbbaacccaacccabaaaccbbacbaa',
  'baaabbcbbbaacabacbcaaacabbacaacbacabbcabcccbabcbbacacbbababccacabc',
  'abbbacbaabcabbcabbbabaababbaabcacbabbaababcabbbccccbcaacbbcccabaccb',
  'caaababcacccaccababaccbabbccaabbbbbabaabcabccbabbbbbbcbacbabcbcccbb',
  'abbbcaaaaacaaacbbbcbacabbcbbbccacaccacacabacacbbccbbbcbaccabbcbaabbc',
  'bacacbcccabcabaabacccbcaaabcabbbcccaacbabacbaabbcccacaacbabbcacbaabb',
  'bacaaaccbaababbbbbcaabcabaacccabacccbabcbccbbcbcaacbbaabcaccaaaacaabb',
  'bbacaacccaaacacccbbacbcbbaaaccccabbbbcbbbabaaaaccbccaababaccbbccacaca',
  'aacccccbabaccbcbcbbaccbacbcbacaababaaaccbaaabaabcccccacbbaabcccaababcc',
  'babacacbbbacbbbbbabbabababacabacaaacbbccaccabacaacbabbbaccacccbcaaabbb',
  'bcaccabbabbcbcabccbbcaacbbcbacbcabaaaaaacaaacaccbcaaccaaccacbaccacaabbc',
  'acbcbbcbbaacbbbabbaabacabbcccabacabcabacccacbcaacacabcaaaabbabcccbcbabb',
  'ccbcbcccbccbbbabaabbaababbcbacacbcbaacaccccccbcbacacbcabaaaacaacbbbbacba',
  'cccbcbaaabcbbcbabbbaccabbabcacbaccbcababbababcbcaccabbbccabaabaaccccacbb',
  'bbabcbcaabbacaabcababbbccbccccaaaabaccbbbbababbcabbabbaccaaaabbcbbbcbaccc',
  'cbacaccaaaacaacbbcbbacaccabacaacacaacaacabccaaaccccacaaaaabcbcabaabaacccb',
  'bcacbccabcccabababbbbcabaacabcbbaacaaaabbbacccaaabccbaabcbbabbbcccabaabbbb',
  'cbccacabaaacabbccbacabccacabcbaccbababcccabbabbbbbbccbaabbaacaacaaaabcbabb',
  'abcbcabbcabaababccbcacabbcbcabcaabbbabbcaaabaaaaacbaabaaababccacbabcbaccbab',
  'aabbabbbcacaaaabcbcabccccacbacbccacacaabccacccaaacacbcccaabbbccacacbbccbbac',
  'caacbbccacaaaacabaacbcaaaccbbabbcacababbbabcbccbaabccaababbcbacbccababbcbbbc',
  'aaabaaaabbbbbcbbbacabccbaaaaabaacbacbcccbccacccacaaacaccbbabcbcccbbccccabbcb',
  'cccccacacbacbbcbbcabcbaabbcbbbacabcbbccccaaacabcababbcaaccaabccabaccbcaccbaba',
  'ccaaaccbccacabcacaccbccaabacacabaabbbaacbcacaacbaaabbbbabbabcccabcabbaccacacc',
  'cbbbcaccbcacccbacccaaaabacaacccbcbcbabbbaababacccccccabbaaabbcbaabbbbbbaaaaaaa',
  'ccbcbcbaabbccabbabbccbacbabacbcacbccacaabbcacaaccabbbbcbacbbcaaabaabccaacccacb',
  'caaabcabaacbbabcbccabcacbbcccabcacbbcaabaacaaabbbcacaaccaccaaaacaaccbbaaaacaaac',
  'bbacacbbaaaacbcabbbbbaabacaccabcbabbccbbbabbbacccababbcababcbbcacbababbbaaabcca',
  'bbacbbacacaccccbabbbbcabbcccbcacaabbcabbccaaaaabcbbcccaccbcbbbccabcbaccacbacbaba',
  'baccbcababbacabcbabacaababbaabcabbcbcbccabacbbaaaaabacaaacaacbacbcabacabaaccbcab',
  'accacccabccbabcbcbaababacabcabbcaccbccabbabcbcabbaabccacbbbbcaacbccaababbababbaba',
  'bbcccbcbcbccccbcaaccaaacacbbaacbcccbbcabbbccabaacbacaaaccbcbaacababaccacbcbaaccac',
  'acbccccaabcabbbcbbccbccbacbcabcccacbcabbaacbababbbcbbccacbacccbbbaccbaaaabbbabaccb',
  'babcacaccbccbaaabaabbbaabcaabaaccccacaacbaccbcbabbbbbbabcbbbbacbacbabcbbbacbbbbbbc',
  'caabcaaaaabacccacbbbaabaabccaabcbaabbcbcbbbccbabbccbcbabbbbccacbcbcbacaaccccacbbabc',
  'bbaaabbabccaccacbcbbccaaaaababbacccbabcbacabacbaacbcabaaacacaaaaacaaacabbbbccabbbca',
  'bbcbccababbbaabbabcbbaacbccbaacbababbabcbaaccbcbcabacaabacaacabcababbaaabbbbbbccccbb',
  'acabcabccaaccccacbcaabaccacaaabcbabbabbaccbbaaacacabcabbcabababaccccbcbabaacbbcccbab',
  'bacaaaaacbcacbbbaaaaabbbbcbbcbbbcaccccbacaccbbcbabbbccbaaabbcbaccacacbcbcacbcbaaabacc',
  'bbcaabccbcaccbabbacbaacacccccaabbbccbccbbbcccbacaaaccccbccbbbbabccaaacaabbbbacaacabab',
  'aaaccccbbabbcacabaacacbabbcacbcccbcbaaacaabaabacbbaabcbbbbbcacbaccaacaacbccacbbcacbbaa',
  'bbcacabcbbcbabbabbbacaaabcabbbbacbacbabacbbbbbabacabbabaabcabbaabbbaaccbcabcababcaaacc',
  'ccccbaacbbcaccaccbaaacaccbabbabaabbababcacacaaccbbcbccaaaaaaacbccacbacbabbbabcabaabaabb',
  'abacacbaccacaaacaccbcbabcaacbccaccbbacbabcababcaabcaabcbcabbcbacabaaaaaabaccccbbbcbabac',
  'ccccacbaaabaaacabbabacbbacbabcbbcaaaaacaccacabcaacabcbcbcaccabcaaccbaccabcccbccacccbacbc',
  'bcaabcaacacccbcababccacacbccccccbbaaabacabbcbbbcbaaacbbacababbaccccacbbcbacaacbabcbaccbc',
  'cbcbbaabacbaacbbcabbbbaccbaabbacbcccaaabbabacabbbababcaabcacbaccacacaccbbbbcbcbbaaacbcbba',
  'ccbcabcaabcbabbbcbcbbabacabacbbaccbbcbcabcaccaaccbaccbaacacacbbaacaaaaabcaaaacbcccbcccaaa',
  'cbbababacbbabbabaabaaaabcacbacbcccbacbccbbcaabcabaccacccbbcaacacccccaccabaabccacbaccabaaba',
  'cbbbaaacaccbcabccacbccabacbcbcccccacaccbbcccbcbbbaababcaaaacaabbbccbacbaccabccccbbbcaaaabb',
  'bbabbacaaccacccbbcabbacbcbabcccaccacbacbccababbbcacbabbbcabbbbacabcabcbaacbaabcbccacaaaccbc',
  'babcbaabccabcabaaabcaaaabaaaaccbcbcacbbbccaccccaacbcbabbbaaaccacaaabacbbabbcacbcaaaaabaabab',
  'acbabbccacaccabccbcbabacccbabbaacbccbcaabccbcbababccacbbbaabbaaaababbcaaaaabccbacbbcacbcacba',
  'cbccbbaacacccacacacbbbcbbccabcaaaabbcacacacaccbacaacbcbcbccaacaaaaaacbacacbabbbcccabbbbababa',
  'cabaabaccbbcccabaccbbacbcabbbbbaccccccbcbcbcbbccbaaabbbbcabacabccaacbcbcbabccbbcabacababccaab',
  'bccaacbabcbccaccbabcbbcbaaccbaacabbcabbbacbbccabcabccabccbacbaacbccabccaabaaabcaababacacccaac',
  'aacabcccaaccacbbcbbbbacaacacbcbcaabbcbbacbabcbccaabcbbbbaabccbbbacaababcabaacaccababacbcbccbba',
  'caaabbcbcbcabccccacacaaababbacbabacbaaccbcbabbaaacbbccccaaaabbccbcabcbccbbaaccbbbabcaabcbbbcab',
  'aacbbcbbcbaccccbaaaabcbaaabaaacaacaaacacacabaaabacbaaaacccbaaabbbcbbbacbcbccabccaabbaabcbcbccba',
  'abaccbcacabbbbacabaacaccbcbaabbaccaabbbbbababbbcbbbbacaacabbbabcaccbacabbabcbbacbbaaccbcbacaabc',
  'aacaaaacccabcccacacbaaccccababcaccaccacbbbacabccbbcbbbacaccbbbbbaabacbacbcbcabccaaccababacaabcbb',
  'baabbabaaccabcbbabcacccccaabbccbccbcaacbbbccccbbcbacaabcccccbbabbabbcacbbccbcacabbbbaaaaccbcacca',
  'aabacbaacbbccabbbacbcbbbabacaacccabbcabacacaaaabbcbbbcbbbcababbccbbacbbabcaacbacbbcaabbbcbaaaccaa',
  'aacabaaccaaabcacccabbaabbcacbabccacabaccaaaaccccccaabcbbbaabcbcccacaccbcaaacaaaabaababccbbbcccaac',
  'bcaccbcacaccbacbcccbcbbcabaabbabcccbaaababbbabbcbcbcaabbabbccccbabccabbccccabaaabccbacabccabbbacaa',
  'ccaacbabcccbabacabaccccbcbbcccbbbacbbbcccacababccbbaaaaababbabccbccabcccbccabaccbcbcacbbbaacabccaa',
  'caccbababcbcbabccabcbbaccbbbabcbacbcbcbcabcbacbcacabbcaabbbbbbbcbbaabcacccbcaabccacbccbbcccaabcbcac',
  'bbcccaabacbacbccbbbbbaabccaaabbaabcaabbcbabbbaabcbcbacbaccabacacaaaababccaaaccacaabaabcacbcaccbaabb'
];
var call = 0;

function guess(S, len) {
  var sym = {};
  recurse(S, len, "", sym);
  return sym.result;
}

function recurse(S, len, s, sym) {
  var dictionary = [];

  if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
    if(s.length == len) {
      sym.result = s;
    }
    else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
      dictionary = [ Array(len - s.length + 1).join('a') ];
    }
    else {
      dictionary = [ "a", "b", "c" ];
    }
    dictionary.some(function(e) {
      return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
    });
    return true;
  }
  return false;
}

function isCandidate(s, sym) {
  return sym[s] === undefined && Object.keys(sym).every(function(k) {
    return count(s, k) <= sym[k];
  });
}

function count(s0, s1) {
  return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
  call++;
  return count(S, s);
}

test.forEach(function(S) {
  if(guess(S, S.length) != S) {
    console.log("Failed for: '" + S + "'");
  }
});
console.log(call + " calls");
```

# Answer
> 4 votes
# Python, 15205 calls

```
def findS(S, len_s, alphabeth = "abc"):
    if len_s == 0:
        return ""
    current = ""
    add_at_start = True
    while len(current) < len_s:
        worked = False
        for letter in alphabeth:
            if add_at_start:
                current_new = current + letter
            else:
                current_new = letter + current
            if num_occur(current_new, S) > 0:
                current = current_new
                worked = True
                break
        if not worked:
            add_at_start = False
    return current

```

This submission is most likely suboptimal, because it only uses `num_occur` to check if a string is a substring of `S`, and it never uses it to actually count the amount of substrings.

The algorithm works by storing a string `current` which is built up to be equal to `S` in the end. Here are all the steps in the algorithm:

1. We set `current` equal to `''`
2. Go through each letter in the alphabet, and do the following:

2.1. Create a new string `current_new`, and set it equals to `current` followed by the letter.

2.2. Check if `current_new` is included in `S` by running `num_occur` on it and see if the result is greater than one.

2.3. If `current_new` is included in `S`, set `current` to `current_new` and go back to step 2. Else, we go to the next letter.
3. If the length of `current` is equal to the length of `S` we can say that we are done. Else, we go back to step 2, but modify step 2.1 to make `current_new` equal to the letter followed by `current` instead. When we reach this step again, we are done.

# Answer
> 4 votes
# Python 2, ~~14952~~ 14754 calls

Very similar to the first answer, but doesn't try next characters which result in impossible substrings that:

* we know from `num_occur` that they don't occur in the target (from previous calls)
* we already used the substring more often than it occurs according to `num_occur`

~~(will add counting of substrings in a minute)~~ done

```
def get_that_string(h,l,alpha = "abc"):
    dic = {}
    s = ""
    ##costs 1 additional call per example, but its worth it
    char_list = [num_occur(j,h) for j in alpha[:-1]]
    char_list.append(l - sum(char_list))
    for y, z in zip(char_list,alpha):
        dic[z] = y
    end_reached = False
    while len(s) < l:
        for t in alpha:
            if not end_reached:
                neu_s = s + t
                substrings = [neu_s[i:]   for i in range(len(neu_s))]
            else:
                neu_s = t + s
                substrings = [neu_s[:i+1] for i in range(len(neu_s))]
            ## Test if we know that that can't be the next char
            all_in_d = [suff for suff in substrings if suff in dic.keys()]
            poss=all(map(dic.get,all_in_d))
            if poss:
                if not neu_s in dic.keys():
                    dic[neu_s] = num_occur(neu_s,h)
                if dic[neu_s] > 0:
                    s=neu_s
                    for suff in all_in_d:
                        dic[suff] -= 1
                    break
        else:
            end_reached = True
    ##print s
    return s

## test suite start
import urllib

def num_occur(needle, haystack):
    global calls
    calls += 1
    num = 0
    for i in range(len(haystack) - len(needle) + 1):
        if haystack[i : i + len(needle)] == needle:
            num += 1
    return num

calls = 0
url = "https://raw.githubusercontent.com/iatorm/random-data/master/abc_strings.txt"
inputs = urllib.urlopen(url).read().split("\n")
print "Check: ", inputs == map(lambda h: get_that_string(h, len(h)), inputs)
print "Calls: ", calls

```

# Answer
> 4 votes
# Python ~~12705~~ 12632 calls

1. make a list of 2 characters strings occurrences
2. sort the list
3. build the string trying the most probable character first, don't test if there is only one possibility
4. update the list
5. if the list is empty it is finished else step 2

*I used Loovjo function skeleton. I never code in Python I needed a bootsrap*

**EDIT:**
*Added code for one character length strings*
*Added code to reject already matched patterns*

```
def finds(S):

    if len(S) == 0:
            return ""
    if len(S) == 1
            if num_occur("a",S) == 1 :
                         return "a"
            if num_occur("b",S) == 1 :
                         return "b"
            return "c"
    tuples=[]
    alphabet=[ "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb"]
    for s in alphabet : tuples.append( (num_occur(s,S), s) )

    sum=0
    for (i,s) in tuples :   sum+=i
    tuples.append( (len(S)-sum-1, "cc") )
    tuples.sort(key=lambda x:(-x[0],x[1]))

    (i, current) = tuples[0]
    tuples[0] = (i-1, current)

    add_at_start = True
    nomatch=[]
    while len(tuples) > 0:
            worked = False
            tuples.sort(key=lambda x:(-x[0],x[1]))
            count=0
            if not add_at_start :
                    for (n, s) in tuples :
                            if s[0]==current[-1:] :         count+=1
            for i in range(len(tuples)):
                    (n, s)=tuples[i]
                    if add_at_start:
                            if current[0] == s[1] :
                                    current_new = s[0] + current
                                    possible=True
                                    for nm in nomatch :
                                            lng=len(nm)
                                            if current_new[0:lng] == nm :
                                                    possible=False
                                                    break
                                    if possible and num_occur(current_new, S) > 0:
                                            current = current_new
                                            worked = True
                                    else :
                                            nomatch.append(current_new)
                    else:
                            if current[-1:] == s[0] :
                                    current_new =  current + s[1]
                                    possible=True
                                    for nm in nomatch :
                                            lng=len(nm)
                                            if current_new[-lng:] == nm :
                                                    possible=False
                                                    break
                                    if count == 1 or (possible and num_occur(current_new, S) > 0) :
                                            current = current_new
                                            worked = True
                                    else :
                                            nomatch.append(current_new)
                    if worked :
                            if n == 1:
                                    del tuples[i]
                            else    :
                                    tuples[i] = (n-1, s)
                            break
            if not worked:
                    add_at_start = False
    return current

```

---
Tags: string, fewest-operations
---


# Question
Title: Compute the polyomino capacity of a rectangle
Write a program or function that takes as input three positive integers `x`, `y`, and `a` and returns or outputs the maximum number of whole `a✕1` rectangles that can be packed (axis-aligned) into an `x✕y` rectangle. Although the result will always be an integer, the program need not give the result using an integer type; in particular, floating-point outputs are acceptable. Use of standard loopholes is forbidden. Answers are scored in bytes including the cost of non-standard compiler flags or other marks.

Sample inputs and outputs:

```
 x,  y,  a -> result
--------------------
 1,  1,  3 ->      0
 2,  2,  3 ->      0
 1,  6,  4 ->      1
 6,  1,  4 ->      1
 1,  6,  3 ->      2
 6,  1,  3 ->      2
 2,  5,  3 ->      2
 5,  2,  3 ->      2
 3,  3,  3 ->      3
 3,  4,  3 ->      4
 4,  3,  3 ->      4
 4,  4,  3 ->      5
 6,  6,  4 ->      8
 5,  7,  4 ->      8
 7,  5,  4 ->      8
 6,  7,  4 ->     10
 7,  6,  4 ->     10
 5,  8,  3 ->     13
 8,  5,  3 ->     13
12, 12,  8 ->     16
12, 13,  8 ->     18
13, 12,  8 ->     18
 8,  8,  3 ->     21
12, 12,  5 ->     28
13, 13,  5 ->     33

```

---

In response to a question in the comments, note that some optimal packings may not be obvious at first glance. For instance, the case `x=8`, `y=8`, and `a=3` has solutions that look like this:

```
||||||||
||||||||
||||||||
---||---
---||---
|| ||---
||------
||------

```

(8 + 2 + 2 = 12 vertical placements and 2 + 3 + 4 = 9 horizontal placements gives 12 + 9 = 21 placements in total.)

# Answer
> 8 votes
## Python 2, 53 bytes

```
lambda p,q,n:p/n*q+q/n*(p%n)-min(0,n-p%n-q%n)*(p>n<q)

```

Adapts the formula given in this paper, which is:

```
def f(p,q,n):a=p%n;b=q%n;return(p*q-[a*b,(n-a)*(n-b)][a+b>=n and p>=n and q>=n])/n

```

---
Tags: code-golf, math, number-theory, packing, polyomino
---


title: Curiosity killed the cat?

text:
# Question
Title: Curiosity killed the cat?
Some people say curiosity killed the cat. Other say it was the box and poison. The RSPCA say Erwin Schrödinger needs to lose the right to own pets.

With animal rights activists outside his house. The ~~cat murderer~~ scientist Schrödinger has finally come up with his greatest invention. A special, radioactive mix of unobtanium and handwavium that can have any half life, and a single gram of the product is capable of killing any living creature. Unfortunately, when he tried to test it on his final cat: Bob, he forgot that cats have 9 lives, and so would need 9 grams to kill. With some water but no food, poor Bob will live exactly 1 week (7 days) if the product doesn't kill him first.

The task: Given an input of a mass in milligrams and a half-life in milliseconds - both integers which can exceed 2^31, write a program that outputs whether or not the mystery super product kills the cat, or if it's 1 week time limit expires first. Assume true/yes/1/anything specified in the answer is for when he does not die from starvation.

For the product to kill him, a total of 9 grams must decay. So out of a sample of 18 grams, 1 half-life must pass. If the sample contains less than or equal to 9 grams, this will never be achieved, and so it can be immediately assumed 1 week will pass before 9 grams decays.

You may assume:

* Bob dies the microsecond 9 grams has decayed.
* The change is mass due to decay does not matter.
* All days and times follow generally accepted earth time.
* The box Bob is sealed in is unbreakable and unopenable, so there is no chance of death from other causes.
* Oxygen is also no issue.
* If both happen at the exact same time either output is acceptable.
* All inputs should be below 2^63-1

Test cases:

Example:

```
18000 604800001

```

For 9 grams to decay, exactly 1 half life must pass (18000/2 = 9000 milligrams or 9 grams). 1 half life is 604800001 milliseconds, or 168 hours and 1 millisecond, or exactly 1 week and 1 millisecond. Since Bob dies of hunger at exactly 1 week, the output is false as he died from hunger just before the 9 gram product limit was reached

```
8000 40000 false

70000 800 true

18000 604800000 either

18000 604800001 false

18000 604799999 true

1 1 false

100000 1 true

1000000000 1000000000 true

```

Scoring: Naturally we want Bob's suffering to end quickly, and so a shorter half-life is best. Half-life and byte both end in E, so clearly the shortest byte count wins.

# Answer
# Python 3, 33 bytes

```
lambda a,b:a-a*.5**(6048e5/b)>9e3

```

Explanation:

```
         6048e5         # number of milliseconds in 1 week
               /b       # half-lifes per week
  a*.5**(        )      # mgs of substance remaining after 1 week
a-                      # mgs of substance decayed after one week
                  >9e3  # return true if more than 9000mgs has decayed in 1 week

```

Try here
> 9 votes

# Answer
# Fourier, 51 bytes

I have to admit that I don't fully understand this program... Mainly just a translation of TheNumberOne's Python code.

```
oI~M~NI~H604800000~G>H{1}{G/H^(M/2~Mi^~i)N-M>9000@o}

```

Note this is the first program that I've written for PPCG which uses `@`, the clear output function.

**Try it online!**
> 5 votes

# Answer
## CJam (22 bytes)

```
q~dX.5@6048e5\/#-*9e3>

```

Online demo

### Dissection

A quick explanation of the maths: if the halflife is `λ` then after time `t` the proportion of the radioactive material remaining is `(1/2)^(t/λ)`, so the proportion decayed is `1 - (1/2)^(t/λ)`.

```
q~d         e# Parse input, ensuring that the later division will use doubles
X.5@6048e5\ e# Rearrange stack to: m 1 0.5 6048e5 λ
/#-*        e# Div, pow, sub, mul, giving the total mass decayed after a week
9e3>        e# Is it OVER 9000! ?

```
> 5 votes

# Answer
## Actually, 20 bytes

```
5╤:6048*/1½ⁿ1-*93╤*<

```

Try it online!

Explanation:

```
5╤:6048*/1½ⁿ1-*93╤*<
5╤                    10**5
  :6048               6048
       *              6048*10**5 (milliseconds in 1 week)
        /             divide by half-life
         1½ⁿ          (1/2)**(^)
            1-        1-(^) (% of sample decayed after 1 week)
              *       multiply by sample mass (mass decayed after 1 week)
               93╤*   9*10**3 (9000)
                   <  is 9000 < sample mass decayed?

```
> 4 votes

# Answer
# Dyalog APL, 19 bytes

```
9E3≤⊣-⊣×.5*6048E5÷⊢

```

`9E3≤` is 9000 smaller than or equal to

`⊣-` the left argument (mass) minus

`⊣×` the left argument times

`.5*` ½ to the power of

`6048E5÷⊢` 604800000 divided by the right argument (half-life)

No need for parentheses, as APL is strictly right-to-left.

TryAPL online!
> 3 votes

---
Tags: code-golf, math
---


title: Chess conversion

text:
# Question
Title: Chess conversion
There's quite a lot of work that's been done in the world of chess. For example, there is a standardized file format, `.pgn`, that describes a chess game, including the list of moves. Additionally, there's another file format `.fen`, that describes a board position. **The challenge today is to convert a list of chess moves (in algebraic notation) to a board position.**

# Definitions

* Position `[a-h][1-8]`: Given by appending the row (file) and the column (rank). Defines one of the 64 possible positions on the board.
* Piece`[KQRBNP]?`: Represents the **K**ing, **Q**ueen, **R**ook, **B**ishop, K**N**ight, **P**awn. In algebraic notation, `P` is not used. When used on a board, letters are uppercase if they are White, otherwise lowercase.
* Move `[KQRBN]?[a-h]?[1-8]?x?[a-h][1-8](=[KQRBN])?(+*?)?|O-O(-O)`: A piece followed by the position it is moving to.
    + If the piece is ambiguous, then the row, or the column, or both are given.
    + If the piece is capturing a piece, then `x` is placed between the piece and the position.
    + If the move is a castling, then `O-O` is given for king-side, otherwise `O-O-O`.
    + If a pawn is being promoted, the move is appended with `=` followed by the piece it is being promoted to.
    + If a move puts the king in check, it is appended with a `+`.
    + If a move puts the king in checkmate, its appended with `#`.
    + The color of the piece is determined by the turn number (White and black alternate turns, starting with black.)
* Board`(([1-8]|[KQRBNPkqrbnp])*\/){8}`: Rows are given by listing the pieces in row order. If there are empty squares, each run of empty square is given using the length of the run. Rows are separated using `/`

A board's initial position is `rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR`, which represents:

```
rnbqkbnr
pppppppp

PPPPPPPP
RNBQKBNR

```

You need to take a list of Moves and return a Board. You can assume that your input is valid.

# Examples

```
                     -> rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
e4                   -> rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR
e4,c5                -> rnbqkbnr/pp1ppppp/8/2p5/4P3/8/PPPP1PPP/RNBQKBNR
e4,d5,exd5,e5        -> rnbqkbnr/ppp2ppp/8/3Pp3/8/8/PPPP1PPP/RNBQKBNR
e4,d5,exd5,e5,dxe6   -> rnbqkbnr/ppp2ppp/4P3/8/8/8/PPPP1PPP/RNBQKBNR
e4,d5,exd5,e5,dxe6,Bc5,Nf3,Nf6,d4,Nc6,dxc5,Ne5,h4,h5,Nh2,Neg4 -> r1bqk2r/ppp2pp1/4Pn2/2P4p/6nP/8/PPP2PPN/RNBQKB1R
e4,d5,exd5,e5,dxe6,Bc5,Nf3,Nf6,d4,Nc6,dxc5,Ne5,h4,h5,Nh2,Neg4,g3,Nxf2,Qd4,N6g4 -> r1bqk2r/ppp2pp1/4P3/2P4p/3Q2nP/6P1/PPP2n1N/RNB1KB1R
e4,d5,exd5,e5,dxe6,Bc5,Nf3,Nf6,d4,Nc6,dxc5,Ne5,h4,h5,Nh2,Neg4,g3,Nxf2,Qd4,N6g4,Bf4,O-O -> r1bq1rk1/ppp2pp1/4P3/2P4p/3Q1BnP/6P1/PPP2n1N/RN2KB1R
e4,d5,exd5,e5,dxe6,Bc5,Nf3,Nf6,d4,Nc6,dxc5,Ne5,h4,h5,Nh2,Neg4,g3,Nxf2,Qd4,N6g4,Bf4,O-O,Na3,Nxh1,O-O-O,Qg5,exf7+ -> r1b2rk1/ppp2Pp1/8/2P3qp/3Q1BnP/N5P1/PPP4N/2KR1B1n
e4,d5,exd5,e5,dxe6,Bc5,Nf3,Nf6,d4,Nc6,dxc5,Ne5,h4,h5,Nh2,Neg4,g3,Nxf2,Qd4,N6g4,Bf4,O-O,Na3,Nxh1,O-O-O,Qg5,exf7+,Kh7,Bxg5,Rd8,f8=Q -> r1br1Q2/ppp3pk/8/2P3Bp/3Q2nP/N5P1/PPP4N/2KR1B1n
e4,d5,exd5,e5,dxe6,Bc5,Nf3,Nf6,d4,Nc6,dxc5,Ne5,h4,h5,Nh2,Neg4,g3,Nxf2,Qd4,N6g4,Bf4,O-O,Na3,Nxh1,O-O-O,Qg5,exf7+,Kh7,Bxg5,Rd8,f8=Q,Ngf2,c6,Rd7,cxd7,b6,d8=Q,c6,Q4d6,Ba6,Qd8f6 -> r4Q2/p5pk/bppQ1Q2/6Bp/7P/N5P1/PPP2n1N/2KR1B1n
e4,d5,exd5,e5,dxe6,Bc5,Nf3,Nf6,d4,Nc6,dxc5,Ne5,h4,h5,Nh2,Neg4,g3,Nxf2,Qd4,N6g4,Bf4,O-O,Na3,Nxh1,O-O-O,Qg5,exf7+,Kh7,Bxg5,Rd8,f8=Q,Ngf2,c6,Rd7,cxd7,b6,d8=Q,c6,Q4d6,Ba6,Qd8f6,Rb8,Qdd8,b5,Qc5,b4,Qxb8,bxa3,Rd3,Nxd3+,Kd1,axb2,Bh3,b1=Q+,Kd2,Qxa2,Qh6+,gxh6,Qcd6,Qa1,Qbc7+,Kh8,Qdd8# -> 3Q3k/p1Q5/b1p4p/6Bp/7P/3n2PB/2PK3N/q6n

```

This is a , so make your answers as short as possible!

# Answer
> 4 votes
## Javascript (ES6), ~~1024~~ 995 bytes

This is an early and still bulky attempt. I just stopped optimizing it when the 1K limit was reached.

It's probably not bullet-proof and only considers promotions to a Queen. But it does pass the test case.

*Edit: 995 bytes - a few obvious optimizations*

**Source**

```
F=i=>{B=[];b=0;X=[8,2,4,12,16,4,2,8,1];for(n=120;n--;B[n]=n<8?X[n]|32:n<24?33:n>111?X[n-112]
:n>95|0);Y=j=>(M[j]?M[j].charCodeAt(0)-97:8)|(M[++j]?(8-M[j])*16:128);G=_=>(F&8||!(F&7^f&7))
&&(F&128||!(F&112^f&112))&&B[f]==p;Z=d=>{for(k=f,u=1;(k+=d)!=T;)u&=!B[k]};Q=(j,...D)=>D.some
(d=>(j&2?!((f-T)%d)&&(Z(f<T?d:-d),u):T-f==d||(j&&f-T==d))&&(S=f));i.split(',').forEach(m=>{
if(m[0]=='O'){S=b?4:116;m[4]?(T=S-2,B[S-1]=B[S-4],B[S-4]=0):(T=S+2,B[S+1]=B[S+3],B[S+3]=0)}
else{M=m.match(/([B-R])?([a-h])?(\d)?x?([a-h])?(\d)?(=Q)?/);p=X["QKBNRP".indexOf(M[1]||'P')+
3]|b;F=Y(2);M[4]?T=Y(4):(T=F,F=136);for(f=120,S=0;f--;)G()&&(p&4&&Q(2,15,17),p&8&&Q(2,1,16),
p&2&&Q(1,14,18,31,33),p&16&&Q(1,1,15,16,17),p&1&&Q(0,b-16,2*b-32));for(f=120;p&1&&!S&&f--;)
G()&&Q(0,b-15,b-17);B[S]&1&&(S-T)%16&&!B[T]&&(B[T+16-b]=0)}B[T]=B[S];B[S]=0;M[6]&&(B[T]^=13)
;b^=32});for(r='',y=0;y<8;y++){for(x=z=0;x<8;x++)(b=B[y*16+x])?(p=".PN.B...R...Q...K"[b&31],
r+=(z||'')+(b&32?p.toLowerCase():p),z=0):z++;r+=(z||'')+(y<7?'/':'')}return r}

```

**Full executable snippet**

```
F=i=>{B=[];b=0;X=[8,2,4,12,16,4,2,8,1];for(n=120;n--;B[n]=n<8?X[n]|32:n<24?33:n>111?X[n-112]:n>95|0);Y=j=>(M[j]?M[j].charCodeAt(0)-97:8)|(M[++j]?(8-M[j])*16:128);G=_=>(F&8||!(F&7^f&7))&&(F&128||!(F&112^f&112))&&B[f]==p;Z=d=>{for(k=f,u=1;(k+=d)!=T;)u&=!B[k]};Q=(j,...D)=>D.some(d=>(j&2?!((f-T)%d)&&(Z(f<T?d:-d),u):T-f==d||(j&&f-T==d))&&(S=f));i.split(',').forEach(m=>{if(m[0]=='O'){S=b?4:116;m[4]?(T=S-2,B[S-1]=B[S-4],B[S-4]=0):(T=S+2,B[S+1]=B[S+3],B[S+3]=0)}else{M=m.match(/([B-R])?([a-h])?(\d)?x?([a-h])?(\d)?(=Q)?/);p=X["QKBNRP".indexOf(M[1]||'P')+3]|b;F=Y(2);M[4]?T=Y(4):(T=F,F=136);for(f=120,S=0;f--;)G()&&(p&4&&Q(2,15,17),p&8&&Q(2,1,16),p&2&&Q(1,14,18,31,33),p&16&&Q(1,1,15,16,17),p&1&&Q(0,b-16,2*b-32));for(f=120;p&1&&!S&&f--;)G()&&Q(0,b-15,b-17);B[S]&1&&(S-T)%16&&!B[T]&&(B[T+16-b]=0)}B[T]=B[S];B[S]=0;M[6]&&(B[T]^=13);b^=32});for(r='',y=0;y<8;y++){for(x=z=0;x<8;x++)(b=B[y*16+x])?(p=".PN.B...R...Q...K"[b&31],r+=(z||'')+(b&32?p.toLowerCase():p),z=0):z++;r+=(z||'')+(y<7?'/':'')}return r}

console.log(F(
  "e4,d5,exd5,e5,dxe6,Bc5,Nf3,Nf6,d4,Nc6,dxc5,Ne5,h4,h5,Nh2,Neg4,g3,Nxf2,Qd4,N6g4,Bf4," +
  "O-O,Na3,Nxh1,O-O-O,Qg5,exf7+,Kh7,Bxg5,Rd8,f8=Q,Ngf2,c6,Rd7,cxd7,b6,d8=Q,c6,Q4d6,Ba6," +
  "Qd8f6,Rb8,Qdd8,b5,Qc5,b4,Qxb8,bxa3,Rd3,Nxd3+,Kd1,axb2,Bh3,b1=Q+,Kd2,Qxa2,Qh6+,gxh6," +
  "Qcd6,Qa1,Qbc7+,Kh8,Qdd8#"
));
```

---
Tags: code-golf, chess
---


title: Complexity-free Kolmogorov(-Smirnov)

text:
# Question
Title: Complexity-free Kolmogorov(-Smirnov)
In statistics, sometimes it's useful to know whether two data samples come from the same underlying distribution. One way to do this is to use the two-sample Kolmogorov-Smirnov test.

Your task will be to write a program that reads in two unsorted nonnegative integer arrays and calculates the main statistic used in the test.

---

Given an array `A` and a real number `x`, define the distribution function `F` by

```
F(A,x) = (#number of elements in A less than or equal to x)/(#number of elements in A)

```

Given two arrays `A1` and `A2`, define

```
D(x) = |F(A1, x) - F(A2, x)|

```

The two-sample Kolmogorov-Smirnov statistic is the maximum value of `D` over all real `x`.

## Example

```
A1 = [1, 2, 1, 4, 3, 6]
A2 = [3, 4, 5, 4]

```

Then:

```
D(1) = |2/6 - 0| = 1/3
D(2) = |3/6 - 0| = 1/2
D(3) = |4/6 - 1/4| = 5/12
D(4) = |5/6 - 3/4| = 1/12
D(5) = |5/6 - 4/4| = 1/6
D(6) = |6/6 - 4/4| = 0

```

The KS-statistic for the two arrays is `1/2`, the maximum value of `D`.

## Test cases

```
[0] [0] -> 0.0
[0] [1] -> 1.0
[1, 2, 3, 4, 5] [2, 3, 4, 5, 6] -> 0.2
[3, 3, 3, 3, 3] [5, 4, 3, 2, 1] -> 0.4
[1, 2, 1, 4, 3, 6] [3, 4, 5, 4] -> 0.5
[8, 9, 9, 5, 5, 0, 3] [4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9] -> 0.175824
[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7] [7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8] -> 0.363636

```

## Rules

* You may write a function or a full program. Input may be via STDIN or function argument, and output may be via STDOUT or return value.
* You may assume any unambiguous list or string format for the input, as long as it is consistent for both arrays
* On the off-chance that your language has a builtin for this, you may not use it.
* Answers need to be correct to at least 3 significant figures
* This is , so the program in the fewest bytes wins

# Answer
## APL (~~29~~ 24)

(Thanks to Zgarb for the extra inspiration.)

```
{⌈/|-⌿⍺⍵∘.(+/≤÷(⍴⊣))∊⍺⍵}

```

This is a function that takes the arrays as its left and right arguments.

```
      8 9 9 5 5 0 3 {⌈/|-⌿⍺⍵∘.(+/≤÷(⍴⊣))∊⍺⍵} 4 9 0 5 5 0 4 6 9 10 4 0 9
0.1758241758

```

Explanation:

```
{⌈/                                maximum of
   |                               the absolute value of
    -⌿                             the difference between
      ⍺⍵∘.(         )∊⍺⍵          for both arrays, and each element in both arrays
            +/≤                    the amount of items in that array ≤ the element
               ÷                   divided by
                (⍴⊣)              the length of that array
                          }

```
> 10 votes

# Answer
# J - 39

I'm sure can be shorten much more

```
f=:+/@|:@(>:/)%(]#)
>./@:|@((,f])-(,f[))

```

Usage

```
2 10 10 10 1 6 7 2 10 4 7 >./@:|@((,f])-(,f[)) 7 7 9 9 6 6 5 2 7 2 8
0.363636

```
> 4 votes

# Answer
# JavaScript (ES6) 99 ~~119 128~~

More or less straightforward JavaScript implementation~~, probably more golfable~~. In the F function I use \> instead of \<=, as abs(F(a)-F(b)) === abs((1-F(a))-(1-F(b)))

No more function definition as default parameer in this last edit.

As I said, it's straightforward. The F function is the F function, the D function is the unnamed function used in line 2. It's evaluated using .map for each value present in the two arrays, as the max value for `all` reals must be one of these. At last, the spread operator (...) is used to pass the D values array as a parameter list to the max function.

```
K=(a,b)=>Math.max(...a.concat(b).map(x=>
  Math.abs((F=a=>a.filter(v=>v>x).length/a.length)(a)-F(b))
))

```

**Test** In FireFox/FireBug console

```
;[[[0],[0]], [[0],[1]],
[[1, 2, 3, 4, 5],[2, 3, 4, 5, 6]],
[[3, 3, 3, 3, 3],[5, 4, 3, 2, 1]],
[[1, 2, 1, 4, 3, 6],[3, 4, 5, 4]],
[[8, 9, 9, 5, 5, 0, 3],[4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9]],
[[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7],[7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8]]]
.forEach(x=>console.log(x[0],x[1],K(x[0],x[1]).toFixed(6)))

```

*Output*

```
[0] [0] 0.000000
[0] [1] 1.000000
[1, 2, 3, 4, 5] [2, 3, 4, 5, 6] 0.200000
[3, 3, 3, 3, 3] [5, 4, 3, 2, 1] 0.400000
[1, 2, 1, 4, 3, 6] [3, 4, 5, 4] 0.500000
[8, 9, 9, 5, 5, 0, 3] [4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9] 0.175824
[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7] [7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8] 0.363636

```
> 3 votes

# Answer
# Python 3, ~~132~~ ~~108~~ ~~95~~ 88

```
f=lambda a,x:sum(n>x for n in a)/len(a)
g=lambda a,b:max(abs(f(a,x)-f(b,x))for x in a+b)

```

The input are 2 lists to the function `g`

Thanks to: Sp3000, xnor, undergroundmonorail

*Line 2, first call to `f` reads like "fax". I found that mildly amusing*
> 3 votes

# Answer
# CJam, ~~33~~ 31 bytes

```
q~_:+f{\f{f<_:+\,d/}}z{~-z}%$W=

```

Input is a CJam styles array of the two arrays.

Example:

```
[[8 9 9 5 5 0 3] [4 9 0 5 5 0 4 6 9 10 4 0 9]]

```

Output:

```
0.17582417582417587

```

Try it online here
> 2 votes

# Answer
## Matlab (121)(119)

This is a program that takes two lists throu stdin and prints the result to stdout. It is a strightfwd approcht and I tried to golf it as much as possible. `K(a)` returns a *function* that calculates `x -> F(a,x)`. Then the anonymous function `@(x)abs(g(x)-h(x))` which corresponds to the function `D` is applied to every possible integer of `0:max([a,b])` and the maximum of the results is displayed. (`arrayfun` does the same as `map` in other languages: it applies a function to every element of a array)

```
a=input('');b=input('');
K=@(a)@(x)sum(a<=x)/numel(a);
g=K(a);h=K(b);
disp(max(arrayfun(@(x)abs(g(x)-h(x)),0:max([a,b]))))

```
> 2 votes

# Answer
# Erlang, 96 Bytes

edc65's JavaScript solution ported to Erlang.

```
f(A,B)->F=fun(A,X)->length([V||V<-A,V>X])/length(A)end,lists:max([abs(F(A,X)-F(B,X))||X<-A++B]).

```

Test:

```
lists:foreach(fun ([H,T] = L) -> io:format("~p ~p~n", [L, w:f(H, T)]) end, [[[0],[0]], [[0],[1]],
        [[1, 2, 3, 4, 5],[2, 3, 4, 5, 6]],
        [[3, 3, 3, 3, 3],[5, 4, 3, 2, 1]],
        [[1, 2, 1, 4, 3, 6],[3, 4, 5, 4]],
        [[8, 9, 9, 5, 5, 0, 3],[4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9]],
        [[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7],[7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8]]]).

```

Output:

```
[[0],[0]] 0.0
[[0],[1]] 1.0
[[1,2,3,4,5],[2,3,4,5,6]] 0.20000000000000007
[[3,3,3,3,3],[5,4,3,2,1]] 0.4
[[1,2,1,4,3,6],[3,4,5,4]] 0.5
[[8,9,9,5,5,0,3],[4,9,0,5,5,0,4,6,9,10,4,0,9]] 0.17582417582417587
[[2,10,10,10,1,6,7,2,10,4,7],[7,7,9,9,6,6,5,2,7,2,8]] 0.36363636363636365

```
> 2 votes

# Answer
## STATA 215

This is 90% getting the input into a format that can be used because STATA already has a ksmirnov command.

```
di _r(a)
di _r(b)
file open q using "b.c",w
forv x=1/wordcount($a){
file w q "1,"(word($a,`x'))_n
}
forv x=1/wordcount($b){
file w q "2,"(word($b,`x'))_n
}
file close q
insheet using "b.c"
ksmirnov v2,by(v1)
di r(D)

```
> 2 votes

# Answer
## R, 65 bytes

```
f=function(a,b){d=c(a,b);e=ecdf(a);g=ecdf(b);max(abs(e(d)-g(d)))}

```

This function takes two vectors as arguments and returns the maximum difference of their empirical cumulative distribution functions.

If built-ins were allowed, it would reduce to mere 12 bytes:

```
ks.test(a,b)

```
> 2 votes

# Answer
# Mathematica, ~~76 73~~ 63

Mathematica has the built-in function `KolmogorovSmirnovTest`, but I won't use it here.

```
k=N@MaxValue[Abs[#-#2]&@@(Tr@UnitStep[x-#]/Length@#&/@{##}),x]&

```

Usage:

```
k[{1, 2, 1, 4, 3, 6}, {3, 4, 5, 4}]

```

> 0.5
> 1 votes

# Answer
Quick implementation in Python 3.4.2 (79 bytes):

```
F=lambda A,x:len([n for n in A if n<=x])/len(A)
D=lambda x:abs(F(A1,x)-F(A2,x))

```

Example:

```
>>> A1 = [-5, 10, 8, -2, 9, 2, -3, -4, -4, 9]
>>> A2 = [-5, -3, -10, 8, -4, 1, -7, 6, 9, 5, -7]
>>> D(0)
0.045454545454545414

```
> 0 votes

# Answer
## Java - 633 622 Bytes

Ok,first up, trying to get better at java so thats why i tried it in java, I know i'll never do well, but eh, its fun. second, I honestly thought i could do this in way less, then i got to the stage where there were doubles everywhere, and the method declarations meant using methods only saved 4-5 chars in total. in short, i'm a bad golfer.

edit: usage format\> java K "2,10,10,10,1,6,7,2,10,4,7" "7,7,9,9,6,6,5,2,7,2,8"

```
import java.lang.*;
class K{public static void main(String[]a){double[]s1=m(a[0]);double[]s2=m(a[1]);
int h=0;if(H(s1)<H(s2))h=(int)H(s2);else h=(int)H(s1);double[]D=new double[h];
for(int i=0;i<h;i++){D[i]=Math.abs(F(s1,i)-F(s2,i));}System.out.println(H(D));}
static double[]m(String S){String[]b=S.split(",");double[]i=new double[b.length];
for(int j=0;j<b.length;j++){i[j]=new Integer(b[j]);}return i;}
static double H(double[]i){double t=0;for(int j=0;j<i.length;j++)
{if(i[j]>t)t=i[j];}return t;}
static double F(double[]A,int x){double t=0;double l=A.length;
for(int i=0;i<l;i++){if(A[i]<=x)t++;}return t/l;}}

```
> 0 votes

# Answer
# Haskell ~~96~~ 83

```
l=fromIntegral.length
a%x=l(filter(<=x)a)/l a
a!b=maximum$map(\x->abs$a%x-b%x)$a++b

```

(!) is the kolmogorov-smirnov function which takes two lists
> 0 votes

# Answer
# R, 107 bytes

Different Approach

```
f=function(a,b){e=0
d=sort(unique(c(a,b)))
for(i in d-min(diff(d))*0.8)e=max(abs(mean(a<i)-mean(b<i)),e)
e}

```

Ungolfed

```
f=function(a,b){
    e=0
    d=sort(unique(c(a,b)))
    d=d-min(diff(d))*0.8
    for(i in d) {
        f=mean(a<i)-mean(b<i)
        e=max(e,abs(f))
    }
    e
}

```
> 0 votes

---
Tags: code-golf, array
---


title: Narayana-Zidek-Capell numbers

text:
# Question
Title: Narayana-Zidek-Capell numbers
Generate the *n*th Narayana-Zidek-Capell number given an input *n*. Fewest bytes win.

f(1)=1, f(n) is the sum of the previous floor(n/2) Narayana-Zidek-Capell terms.

Test Cases:

```
f(1)=1

f(9)=42

f(14)=1308

f(15)=2605

f(23)=664299

```

# Answer
# Jelly, ~~11~~ 10 bytes

```
HĊrµṖß€Sȯ1

```

Try it online!

Takes `n` as argument and prints the result.

### Explanation

```
H              divide input by 2
 Ċ             round up to get first n to recurse
  r            inclusive range from that to n
   µ           (chain separator)
    Ṗ          remove n itself from the range
     ß€        call self recursively on each value in the range
       S       sum results
        ȯ1     if sum was zero, return one

```
> 7 votes

# Answer
# Ruby, ~~34~~ 32 bytes

This uses a formula from the OEIS page for the Narayana-Zidek-Cappell numbers.

**Edit:** Got rid of parentheses using operator precedence with thanks to feersum and Neil.

```
f=->x{x<4?1:2*f[x-1]-x%2*f[x/2]}

```
> 7 votes

# Answer
# Python 2, ~~48~~ ~~42~~ ~~38~~ 36 bytes

Algorithm taken from the OEIS page. `n<3` may be changed to `n<4` with no effect. Returns the `n`th number, where `n` is a positive integer.

```
a=lambda n:n<3or 2*a(n-1)-n%2*a(n/2)

```

**Try it online**
> 6 votes

# Answer
## 05AB1E, 16 bytes

An iterative solution as 05AB1E doesn't have functions.

```
X¸sGDN>;ï£Os‚˜}¬

X¸               # initialize a list with 1
  sG          }  # input-1 number of times do
    D            # duplicate current list
     N>;ï£       # take n/2 elements from the list
          O      # sum those elements
           s‚˜   # add at the start of the list
               ¬ # get the first element and implicitly print

```

Try it online
> 5 votes

# Answer
# C, 38

A translation of the OEIS algorithm. There's just not enough C code around here!

```
f(n){return n<3?:2*f(n-1)-n%2*f(n/2);}

```
> 5 votes

# Answer
# Python 3, 67 bytes

```
def f(n):
 x=1,
 for i in range(n):x+=sum(x[-i//2:]),
 print(x[-1])

```

A function that takes input via argument and prints to STDOUT. This is a direct implementation of the definition.

**How it works**

```
def f(n):               Function with input target term index n
 x=1,                   Initialise term list x as tuple (1)
 for i in range(n):...  For all term indices in [0,n-1]...
 x[-i//2:]              ..yield the previous floor(i/2) terms...
 x+=sum(...)            ...and append their sum to x
 print(x[-1])           Print the last term in x, which is the nth term

```

Try it on Ideone
> 4 votes

# Answer
# Pyth, 12 bytes

```
L|syM>/b2Ub1

```

Try it online. Test suite.

Defines a function `y(n)` that returns the `n`th Narayana-Zidek-Capell-number.
> 3 votes

# Answer
# Mathematica, 38 bytes

```
If[#<4,1,2#0[#-1]-#~Mod~2#0[(#-1)/2]]&

```

Anonymous function. Takes as input and returns () as output. Based off of the Ruby solution.
> 3 votes

# Answer
## Haskell, 34 bytes

```
f 1=1
f n=sum$f<$>[n-div n 2..n-1]

```

Usage example: `f 14` -\> `1308`.

A direct implementation of the definition.
> 2 votes

# Answer
# Java, 63 Bytes

```
int z(int n){return n<3?1:n%2>0?(2*z(n-1)-z(n/2)):(2*z(n-1));}

```
> 2 votes

# Answer
# Go, 63 bytes

```
func f(i int) int{if(i<4){return 1};return 2*f(i-1)-i%2*f(i/2)}

```

Pretty much a direct port from the C answer
> 1 votes

# Answer
# PHP, 81 bytes

This is a full program without recursion. A recursive function can be defined in 52 bytes (it might be possible to beat that) but that's just a pretty boring port of sherlock9's answer (and it errors if you ask for f(100) or more) so I'm putting up this longer and more interesting version

```
<?php for($i=$argv[1];$j=$i;$i--)for(;--$j*2>=$i;)$a[$j]+=$a[$i]?:1;echo$a[1]?:1;

```

Causes many (O\[n\]) notices but that's fine.
> 0 votes

# Answer
# R, 55 bytes

```
x[1]=1;for(i in 2:10){x[i]=sum(x[i-1:floor(i/2)])};x[9]

```

Change `10` in the `for` loop and `x[9]` to get whichever index the user wants.
> 0 votes

# Answer
# JavaScript, ~~54~~ 52

```
f=n=>Math.round(n<3?1:2*f(n-1)-n%2*f(parseInt(n/2)))

```

Based on the  answer.

* Saved 2 bytes by using `parseInt` instead of `Math.floor`
> 0 votes

# Answer
## Maple, ~~46~~ 44 bytes

```
`if`(n<4,1,2*f(n-1)-(n mod 2)*f(floor(n/2)))

```

Usage:

```
> f:=n->`if`(n<4,1,2*f(n-1)-(n mod 2)*f(floor(n/2)));
> seq( f(i), i = 1..10 );
  1, 1, 1, 2, 3, 6, 11, 22, 42, 84

```
> 0 votes

# Answer
# R, 63 bytes

```
f=function(n,a=0)if(n<2)1 else{for(i in n-1:(n%/%2))a=a+f(i);a}

```

`a=0` is added as a default because it saves me two curly brackets. Function recursively calls itself as needed.
> 0 votes

---
Tags: code-golf, math, sequence
---


title: Generate random PESEL number

text:
# Question
Title: Generate random PESEL number
From Wikipedia:

> **PESEL** is the national identification number used in Poland since 1979. It always has 11 digits, identifies just one person and cannot be changed to another one.
>
> It has the form of YYMMDDZZZXQ, where YYMMDD is the date of birth (with century encoded in month field), ZZZ is the personal identification number, X denotes sex (even number for females, odd number for males) and Q is a control digit, which is used to verify whether a given PESEL is correct or not.
>
> Having a PESEL in the form of ABCDEF GHIJK, one can check the vailidity of the number by computing the following expression:
>
> A\*1 + B\*3 + C\*7 + D\*9 + E\*1 + F\*3 + G\*7 + H\*9 + I\*1 + J\*3
>
> Then the last digit of the result should be subtracted from 10. If the result of the last operation is not equal to the last digit of a given PESEL, the PESEL is incorrect. This system works reliably well for catching one-digit mistakes and digit swaps.

Provide **a short program to generate random, valid PESEL number**:

1. It has to be a PESEL a person born in either 20th or 21st century
2. The birth birth date has to be random but doesn't have to validate leap years or number of days in a month (i.e. the numbers representing the day number have to be between `01` and `31`)
3. All valid PESELs in this date range (01.01.1990-31.12.2099) must be possible
4. The shortest code (i.e. complete program code), in bytes, wins.

# Answer
# Perl, 162 bytes

```
@a=map{$==rand 10}0..9;$"='';$a[5]%=2if($a[4]%=4)==3;"@a[4,5]"||$a[5]++;$a[3]=($a[2]%=4)%2?$a[3]%3:1+$a[3]%9;$f=9;for(@a){$x+=$f*$_;$f-=$f%10==7?4:2}print@a,$x%10

```

## Ungolfed:

```
# Array with random digits
# ------------------------
@a = map { $= = rand 10} 0..9;
# do not insert a space, if arrays are interpolated into strings
$" = ''; #"

# Day correction
# --------------
# The day must be in the range of "01" to "31":
# * map first digit to "0" to "3": $a[4] %= 4
# * map second digit to "0" to "1" if first digit is "3"
$a[5] %= 2 if ($a[4] %= 4 ) == 3;
# * set day to "01" if day is "00"
"@a[4,5]" || $a[5]++;

# Month correction
# ----------------
# The month must be in the range "01" to "12" or "21" to "32"
# to get a valid month and century:
# * map the month to "00" to "39"
# * if the first digit is odd (catching both centuries at once)
#   * then map the second digit to "0" to "2"      (for months: 10..12)
#   * otherwise map the second digit to "1" to "9" (for months: 01-09)
$a[3] = ($a[2] %= 4) % 2 ? $a[3] % 3: 1 + $a[3] % 9;

# Calculate the control digit
# ---------------------------
# Because of the modulo 10 operations, the formula for the calculation
# of the control digit is rewritten from
# Q = (10 - ((A + 3B + 7C + 9D + E + 3F + 7G + 9H + I + J) % 10)) % 10
# to
# Q = (9A + 7B + 3C + D - E - 3F -7G - 9H - 11I - 11J) % 10
$f = 9;
for (@a) {
    $x += $f * $_;
    $f -= $f % 10 == 7 ? 4 : 2
}

# Print the result and control digit
print @a, $x % 10

# TEST section
# ------------

;$Q = $x % 10; # remember control digit in $Q

# Pretty print PESEL
print "\n\n",
  "YY MM DD ZZZ X Q\n",
  "@a[0,1] @a[2,3] @a[4,5] @a[6,7,8] $a[9] $Q\n";
print "\n";

# Pretty print the date
$month = "@a[2,3]";
$century = "??";
$century = "19" if $month >= 1 and $month <= 12;
$century = "20" if $month >= 21 and $month <= 32;
printf "Date: $century@a[0,1]-%02d-@a[4,5]\n", $month % 20;
print "\n";

# Pretty print the gender
print "Gender: ", $a[9] % 2 ? "male" : "female", "\n";
print "\n";

# Calculate the control date the official way
print "Control digit:\n";
$sum = 0;
$f = 0;
for (my ($i, $f) = (0, 1); $i<10; $i++, $f+=2) {
    $f %= 10;
    $f += 2 if $f == 5;
    printf "  $a[$i] * $f = %2d\n", $a[$i] * $f;
    $sum += $a[$i] * $f;
}
print "  ", "-" x 10, "\n";
printf "  %10d\n", $sum;
printf "  $Q = (10 - ($sum % 10)) % 10 = %d\n", (10 - ($sum % 10)) % 10;

```

## Examples

```
83102570819

YY MM DD ZZZ X Q
83 10 25 708 1 9

Date: 1983-10-25

Gender: male

Control digit:
  8 * 1 =  8
  3 * 3 =  9
  1 * 7 =  7
  0 * 9 =  0
  2 * 1 =  2
  5 * 3 = 15
  7 * 7 = 49
  0 * 9 =  0
  8 * 1 =  8
  1 * 3 =  3
  ----------
         101
  9 = (10 - (101 % 10)) % 10 = 9

```

```
20233143600

YY MM DD ZZZ X Q
20 23 31 436 0 0

Date: 2020-03-31

Gender: female

Control digit:
  2 * 1 =  2
  0 * 3 =  0
  2 * 7 = 14
  3 * 9 = 27
  3 * 1 =  3
  1 * 3 =  3
  4 * 7 = 28
  3 * 9 = 27
  6 * 1 =  6
  0 * 3 =  0
  ----------
         110
  0 = (10 - (110 % 10)) % 10 = 0

```
> 2 votes

# Answer
# Mathematica ~~247~~ 270

A bit long but there are many details to take into consideration:

* Allow any valid birth date between Jan. 1, 1900 and Dec. 31, 2099; Feb. 29 included in leap years.
* Pad all numbers left with zeros: e.g. Month 3 becomes "03" so any PESEL will have exactly 11 digits.
* Add 20 to month if in 21st century (2000-2099)

## Ungolfed

Below the components are named for convenience.

```
g:=Module[{year,month,day,centuryIncrement,id,controlDigit,pesel},
{year,month,day}=DatePlus[{1900,1,1},RandomInteger[73048]];
centuryIncrement=20*Boole[year>= 2000];
Print[Row@{{year,month,day},"  ",DateString[{year,month,day},{"MonthName"," ","Day",", ","Year"}]},
"\ncentury increment: ",centuryIncrement,
"\nID: ",id=PadLeft[IntegerDigits@RandomInteger[999],3],
"\nsex: ",sex=RandomInteger[1]];
f=Flatten[{{IntegerDigits@year,PadLeft[IntegerDigits[month+centuryIncrement],2],
PadLeft[IntegerDigits@day,2]},id,sex}][[3;;12]];
Print["control digit: ",controlDigit=Mod[10-IntegerDigits[Tr@Thread[Times[f,{1,3,7,9,1,3,7,9,1,3}]]][[-1]],10],
"\nPESEL: ",""<>ToString/@PadLeft[Append[f,controlDigit]]]]

```

## Examples

```
g

```

> {1931,2,9} February 09, 1931
> century increment: 0
> ID: {0,8,8}
> sex: 0
> control digit: 9
> PESEL: 31020908809

---

```
g

```

> {2067,6,27} June 27, 2067
> century increment: 20
> ID: {9,0,8}
> sex: 0
> control digit: 1 PESEL: 67262790801

---

```
g

```

> {1967,9,5} September 05, 1967
> century increment: 0
> ID: {5,0,0}
> sex: 0
> control digit: 2
> PESEL: 67090550002

---

## Golfed

```
g:=Module[{y,m,d,i=IntegerDigits,p=PadLeft,r=RandomInteger},{y,m,d}=DatePlus[{1900,1,1},r[73048]];
f=Flatten[{{i@y,p[i[m+20*Boole[y>= 2000]],2],p[i@d,2]},p[i@r[999],3],r[1]}][[3;;12]];
""<>ToString/@p[Append[f,Mod[10-i[Tr@Thread[Times[f,{1,3,7,9,1,3,7,9,1,3}]]][[-1]],10]]]]

```
> 1 votes

# Answer
# PHP, 151

```
echo($n=date("ymd",rand(-2e9,4e9)).rand(101,999).rand()%10).(10-($n[0]+3*$n[1]+7*$n[2]+9*$n[3]+$n[4]+3*$n[5]+7*$n[6]+9*$n[7]+$n[8]+3*$n[9])%10);

```

See it in action: http://ideone.com/DYeXf9
> 0 votes

# Answer
# Mathematica, 220

This generates random date between 1900-01-01 and 2099-12-31, but it does not check whether the number of days in the month is valid.

Value for gender ranges from 0 - 9.

This is as few characters as I could get it:

```
r=RandomInteger;a=r@9;b=r@9;m=r@11+1+r@1*20;c=Floor[m/10];d=m~Mod~10;n=r@30+1;e=Floor[n/10];f=n~Mod~10;g=r@9;h=r@9;i=r@9;j=r@9;k=Mod[10-Mod[a+3b+7c+9d+e+3f+7g+9h+i+3j,10],10];StringJoin[ToString/@{a,b,c,d,e,f,g,h,i,j,k}]
```

## Sample output:

```
04020506179
```

```
34230487249
```

```
26321891950
```

```
45260298217
```

## Ungolfed:

```
r=RandomInteger;

a=r@9; (*year*)
b=r@9;

month=r@11+1+r@1*20;
c=Floor[month/10];
d=month~Mod~10;

day=r@30+1;
e=Floor[day/10];
f=day~Mod~10;

g=r@9; (*personal ID*)
h=r@9;
i=r@9;

j=r@9; (*gender*)

k=Mod[10-Mod[a+3b+7c+9d+e+3f+7g+9h+i+3j,10],10]; (*control digit*)

StringJoin[ToString/@{a,b,c,d,e,f,g,h,i,j,k}]
```
> 0 votes

# Answer
# Mathematica, 157 chars

```
""<>ToString/@Join[#,{Mod[-#.{1,3,7,9,1,3,7,9,1,3},10]}]&@Flatten@{IntegerDigits[#,10,2]&/@RandomChoice@DateRange[{1990,1,1},{2099,12,31}],9~RandomInteger~4}

```
> 0 votes

# Answer
## Matlab, 156 bytes

```
a=datestr(693961+randi(73049),'yyyymmdd');a(5)=a(5)+2*(a(1)>49);A=a(3:8)-48;b=randi(10,1,4);[[A b mod(10-mod(sum(('1379137913'-48).*[A b]),10),10)]+48 '']

```

Ungolfed with some explanation:

```
a=datestr(693961+randi(73049),'yyyymmdd');
  -- generates date serial number in desired range and converts do string
a(5)=a(5)+2*(a(1)>49);
  -- modifies the first digit of the month if year >= 2000 (first digit >1)
A=a(3:8)-48;
  -- gets the "YYMMDD" part and converts from string to array of numbers
b=randi(10,1,4)-1;
  -- gets remaining 4 random digits ("ZZZX")
[[A b mod(10-mod(sum(('1379137913'-48).*[A b]),10),10)]+48 '']
  -- computes the last digit and converts the whole thing to string

```
> 0 votes

---
Tags: code-golf, number, random, generation
---


title: Is this square symmetrical?

text:
# Question
Title: Is this square symmetrical?
Write a program or function that takes in a 4×4 text grid consisting of exactly 4 `A`'s, 4 `B`'s, 4 `C`'s, and 4 `D`'s, such as:

```
ACDC
BBCA
BADD
ABCD

```

The `ABCD`'s may be in any arrangement but there will always be 4 of each. You can assume the input is valid. If desired you can also assume it has a trailing newline and/or that it comes as one line in reading order, e.g. `ACDCBBCABADDABCD`. You may also replace the characters `ABCD` with `0123` or `1234` respectively, if desired (but that's all).

Output a truthy value if the text grid has any form of reflective or rotational symmetry. Specifically:

* If there is a central horizontal line of symmetry. e.g.

```
BACD
BACD
BACD \___ bottom mirrors top
BACD /

```
* If there is a central vertical line of symmetry. e.g.

```
BCCB
DAAD
CAAC
BDDB
  \/___ right mirrors left

```
* If there is a diagonal line of symmetry (in either direction). e.g.

```
     ___ diagonally mirrored
    /
ABDC
BACD
DCAB
CDBA
    \___ diagonally mirrored

```
* If there is 90° rotational symmetry. e.g.

```
BDAB
ACCD    same if rotated 90 degrees (or 180 or 270)
DCCA
BADB

```
* If there is 180° rotational symmetry. e.g.

```
DBCA
BDCA    same if rotated 180 degrees
ACDB
ACBD

```

(Note that translational symmetry doesn't come into play here.)

Output a falsy value if the grid doesn't have one of the symmetries mentioned above. e.g. the very first example grid.

**The shortest code in bytes wins.**

# Answer
## CJam, 16 bytes

```
{{z_W%_}4*;])e=}

```

An unnamed block which expects the input as a list of four strings on top of the stack and leaves a `0` (falsy) for asymmetric inputs and a positive integer (truthy) for symmetric inputs.

Test it here. Or run a full test suite.

### Explanation

The symmetries of the square are the elements of the dihedral group of order 8 (which are just the 4 rotations of the square and the same 4 rotations of some reflected version of the square). It's not possible to generate this group from repeated application of a single permutation. But two reflections always give some rotation. Hence, the entire group can be generated by alternating between two reflections four times. (We just need to make sure that the two reflections give the 90 degree or 270 degree rotation, not 0 or 180.)

The challenge asks whether the input square is equal to any of the other 7 symmetries. So this answer just generates all of them and then checks whether the input is among the others.

```
{      e# Run this block 4 times.
  z_   e# Transpose the grid and duplicate it. (This is one type of reflection.)
  W%_  e# Reverse the lines and duplicate it. (This is another type of
       e# reflection. Together they rotate the grid by 90 degrees.)
}4*    e# The last element will be the original grid again.
;      e# Discard one copy of that original grid.
]      e# Wrap all symmetries in a list.
)      e# Pull off the original grid.
e=     e# Count how many times it appears among the other symmetries.

```

To see how the repeated application of `z` and `W%` generates all symmetries, have a look at this "diagram":

```
     0123
     4567
     89ab
     cdef

     original

 z   048c       W%       37bf
-->  159d  ----------->  26ae
     26ae                159d
     37bf                048c

     diag. refl.         rot. 90 degrees ccw

 z   3210       W%       fedc
-->  7654  ----------->  ba98
     ba98                7654
     fedc                3210

     vert. refl.        rot. 180 degrees

 z   fb73       W%       c840
-->  ea62  ----------->  d951
     d951                ea62
     c840                fb73

     antidiag. refl.     rot. 270 degrees ccw

 z   cdef       W%       0123
-->  89ab  ----------->  4567
     4567                89ab
     0123                cdef

     horiz. refl.        original

```
> 17 votes

# Answer
# Pyth, 11 bytes

```
<7.u?%Y2CN_

```

Test suite

This uses Martin's transpose and reverse technique, but with a twist. While other solutions have explicitly generated all 8 symmetries, then counted the number of appearances of the original, this program uses Pyth's `.u` function.

The `.u` function is the "Apply until repeat is found". In this case, we alternately transpose and reverse until a repetition happens, then accumulate the results into a list. Then, I remove the last 7 values, so there will only be a value remaining if there were no symmetries, and the first repetition happened after all 8 reflections and repetitions were generated.

Explanation:

```
<7.u?%Y2CN_
<7.u?%Y2CN_NQ    Implicit variables
                 Q = eval(input())
  .u        Q    Starting with Q, apply the following until a repeat occurs,
                 then accumulate all values into a list.
    ?%Y2         If the iteration number is odd
        CN       Transpose
          _N     Else reverse
<7               Remove the last 7 results

```
> 8 votes

# Answer
## 05AB1E, 13 bytes

```
4Fø€JÂD}\\)¹å

```

**Explanation**

Uses the method expertly explained by Martin in his CJam answer.

```
4F     }       # 4 times do:
  ø€J          # zip and join each
     ÂD        # bifurcate, duplicate
        \\     # delete the top 2 items on the stack
          )    # wrap stack in list
           ¹å  # check if input is in that list

```

Try it online
> 5 votes

# Answer
# Dyalog APL, ~~37~~ ~~19~~ 17 bytes

@ngn reduced it by 20 bytes!

```
8>≢(∪⊢,⌽¨,⍉¨)⍣≡⊂⎕

```

TryAPL online!
> 4 votes

# Answer
# Perl, ~~61~~ 60 bytes

Includes +3 for `-p0a`

Give input square on STDIN, prints 0 for no symmetry, otherwise some positive number

```
./symmetry.pl
DBCA
BDCA
ACDB
ACBD
^D

```

`symmetry.pl`:

```
#!/usr/bin/perl -p0a
s,.,chop$F[$i++/($j-4?1:4)%4],eg;$\+=$$_++;++$j<8&&redo}{

```
> 4 votes

# Answer
# Brachylog, ~~38~~ 36 bytes

```
@eL:1fbeL
(L;?:raL)(.;L$\.;L$/.;Lr.)

```

Try it online!

This expects a list of strings as input. This prints either `true.` or `false.`.

### Explanation

* Main predicate:

```
@eL    Split each line into a list of chars ; call that list of lists L
:1f    Find all symmetries
b      Remove the first one (the identity)
eL     L is an element of that list of symmetries

```
* Predicate 1: Output is one of the 8 symmetries of the input.

```
(
    L             L = Input
;             Or
    ?:raL         L = reverse all lines of the input
)
(
    .             Output = L
;             Or
    L$\.          Output = transpose of L
;             Or
    L$/.          Output = antitranspose of L
;             Or
    Lr.           Output = reverse of L
)

```
> 3 votes

# Answer
# TSQL, ~~229~~ 225 bytes

Be aware TSQL has no build-in for rotating, so this is part the code.

Returning -1 for true 0 for false

**Golfed:**

```
DECLARE @1 char(16)='BCCBDAADCAACBDDB'

DECLARE @i INT=0,@ char(16)=0WHILE @i<16SELECT
@=substring(@1,@i*4%16+@i/4+1,1)+@,@i+=1SELECT~count(*)/2FROM (SELECT
left(x,8)a,right(x,4)b,substring(x,9,4)c
FROM(values(@1),(@))x(x))x
WHERE a in(reverse(b+c),b+c,reverse(c+b))

```

**Ungolfed:**

```
DECLARE @1 char(16)='BCCBDAADCAACBDDB'

DECLARE @i INT=0,@ char(16)=0
WHILE @i<16
  SELECT @=substring(@1,@i*4%16+@i/4+1,1)+@,@i+=1
SELECT~count(*)/2
FROM
  (SELECT left(x,8)a,right(x,4)b,substring(x,9,4)c
   FROM(values(@1),(@))x(x))x
WHERE a in(reverse(b+c),b+c,reverse(c+b))

```

**Fiddle**
> 3 votes

# Answer
# Python 2, ~~154~~ 146 bytes

Checks if any of the necessary transformations is equivalent to the original using numpy arrays. Input is taken as a list of four strings.

```
from numpy import*
A=array(map(list,input()))
R=rot90
T=transpose(A)
print any([all(A==Z)for Z in(A[:,::-1],A[::-1],R(A),R(A,2),R(A,3),T,R(T,2))])

```

**Try it online**

Taking input as a single string is one char longer, with `A=array(list(input())).reshape(4,4)`. `A[:,::-1]` is the same as `fliplr(A)`. `A[::-1]` is the same as `flipud(A)`.
> 2 votes

# Answer
# Python 3, 99 bytes

```
def f(x):
 t=x;c=[]
 for i in range(7):*t,=[map(''.join,zip(*t)),t[::-1]][i%2];c+=t,
 return x in c

```

A function that takes input, via argument, of a list of strings and returns `True` or `False` as relevant.

This uses the same approach as @MartinEnder's answer.

**How it works**

```
def f(x)                Function with input list of strings x
 t=x;c=[]               Initilaise temporary square t and combination list c
 for i in range(7):...  For i in range [0,6]:
 [...][i%2]              If i is even:
 zip(*t)                  transpose(t)
 *t,=map(''.join,...)     t = t with each line concatenated (such that t is in the same
                          format as x)
                         Else:
 *t,=t[::-1]              t = reverse(t)
 c+=t,                   Append t to c
 return x in c           Return True if x is in c else return False

```

Try it on Ideone
> 2 votes

# Answer
## JavaScript (ES6), 131 bytes

```
s=>[...`0101010`].map(c=>+c?``+b.reverse():`${b=b.map((s,i)=>s.replace(/./g,(_,j)=>b[j][i]))}`,b=a=s.match(/..../g)).includes(``+a)

```

17 bytes could be removed if you pass an array of 4 strings directly. I tried bit-twiddling (input in `"0123301223011230"` format) but that took me 199 bytes:

```
s=>[...'0101010'].map(c=>r=+c?r<<24&255<<24|r<<8&255<<16|r>>8&255<<8|r>>>24:r&0xc0300c03|r<<6&806093568|r<<12&3075<<16|r<<18&3<<24|r>>6&0xc0300c|r>>12&49200|r>>18&192,r=n=parseInt(s,4)|0).includes(n)

```
> 2 votes

---
Tags: code-golf, string, decision-problem, grid, geometry
---