title: Telling time in French

text:
# Question
Title: Telling time in French
Bonjour, PPCG ! Quelle heure est-il ? This means what time is it in French, for that is exactly what this challenge is about.

Telling time in French (at least formally) is a bit different from telling time in English. Telling the time starts out with *Il est* (It is). Then, you put the hour followed by *heures* (o'clock). (In case you don't know French numbers, here's a list: http://blogs.transparent.com/french/french-numbers-learn-how-to-count-from-1-to-1000/). If it is 1 o'clock, do *une heure* for this. For noon, use *midi* (with no heures), and for midnight use *minuit*.

Unless the minutes is 00, you then follow it with the number of minutes. There are a few exceptions to this however. For 15 minutes, you want to say *et quart*, and for 30 minutes you want to say *et demi*. For anything after 30 minutes, you increase the hour number by one, then add the word *moins* and 60 - the minutes. So 6:40 P.M is *Il est sept heures moins vingt* (vingt = 20). 45 minutes would be *moins le quart*.

Finally, you end it with the time of day. For the morning (1 A.M to 12 P.M), you say *du matin*. For the afternoon (subjective, but I'll define it as 1 P.M to 5 P.M), you say *de l'apres-midi* (technically there should be an accent above the e, but eh). And for night (5 P.M to 12 A.M) you say *du soir*. Note that for midnight and noon (*minuit* and *midi*) you don't put any of these afterwards -- the time of day is implied based on which one you use.

As you've probably already ascertained, the challenge here is to print out the current local time in French using these rules. Here's what sample output should look like at assorted times. (The time in the parenthesis does not have to be printed obviously, it's just there so you know what times are):

```
Il est sept heures du matin. (7:00 A.M)
Il est deux heures de l'apres-midi. (2:00 P.M)
Il est une heure du matin. (1:00 A.M)
Il est huit heures du soir. (8:00 P.M)
Il est midi. (12:00 P.M, Noon)
Il est minuit. (12:00 A.M, Midnight)
Il est cinq heures vingt du soir. (5:20 P.M)
Il est six heures et quart du matin. (6:15 A.M)
Il est neuf heures et demi du matin. (9:30 A.M)
Il est quatre heures moins dix de l'apres-midi. (3:50 P.M, not 4:50!)
Il est midi moins le quart. (11:45 A.M)

```

This is code-golf, so shortest code wins. Good luck!

EDIT: The period is required.

# Answer
## PHP - ~~521~~ 473 bytes

I've added some newlines for readability:

```
$w=split(A,'AuneAdeuxAtroisAquatreAcinqAsixAseptAhuitAneufAdixAonzeAdouzeAtreizeA
quatorzeAAseizeAdix-septAdix-huitAdix-neufAvingtAvingt et une');$h=idate('H');if(
$r=($m=idate('i'))>30){$h=++$h%24;$m=60-$m;}echo'Il est '.($h?$h==12?midi:$w[$h%12]
.' heure'.($h%12<2?'':s):minuit).($r?' moins':'').($m==15?($r?' le ':' et ').quart
:($m==30?' et demi':($m?' '.($m<22?$w[$m]:"$w[20]-".$w[$m%10]):''))).($h%12?($h-=$r
)<12?' du matin':($h<17?" de l'après-midi":' du soir'):'').'.';

```

The method used to converting a number to its numeral in French is inspired by this answer on an other challenge by edc65.

Here is the ungolfed version:

```
/** Define numerals **/
$numerals = [
    '', 'une', 'deux', 'trois', 'quatre',
    'cinq', 'six', 'sept', 'huit', 'neuf',
    'dix', 'onze', 'douze', 'treize', 'quatorze',
    '', 'seize', 'dix-sept', 'dix-huit', 'dix-neuf',
    'vingt', 'vingt et une'
];

/** Get current time **/
$hours = idate('H');
$minutes = idate('i');

/** Check if we need to count in reverse **/
$reverse = $minutes > 30;
if ($reverse) {
    $hours = ($hours + 1) % 24;
    $minutes = 60 - $minutes;
}

echo 'Il est ';

/** Print hours **/
if ($hours === 12) {
    echo 'midi';
}
else if ($hours === 0) {
    echo 'minuit';
}
else
{
    echo $numerals[$hours % 12] .' heure';
    if ($hours % 12 !== 1) {
        echo 's';
    }
}

/** Print minutes **/
if ($reverse) {
    echo ' moins';
}

if ($minutes === 15)
{
    if ($reverse) {
        echo ' le ';
    }
    else {
        echo ' et ';
    }

    echo 'quart';
}
else if ($minutes === 30) {
    echo ' et demi';
}
else if ($minutes !== 0)
{
    echo ' ';

    if ($minutes < 22) {
        echo $numerals[$minutes];
    }
    else {
        echo $numerals[20] .'-'. $numerals[$minutes % 10];
    }
}

/** Print daytime **/
if ($hours % 12 !== 0)
{
    if ($reverse) {
        --$hours;
    }

    if ($hours < 12) {
        echo ' du matin';
    }
    else if ($hours < 17) {
        echo " de l'après-midi";
    }
    else {
        echo ' du soir';
    }
}

echo '.';

```
> 4 votes

# Answer
# Python 3, ~~586~~ ~~547~~ ~~556~~ ~~506~~ ~~505~~ ~~502~~ ~~498~~ ~~497~~ 493 Bytes

My first attempt at golfing anything. I’m really not sure about the way I choose, especially the `n` list. But I wanted to give it a try.

```
from datetime import*;t=datetime.now()
n='/une/deux/trois/quatre/cinq/six/sept/huit/neuf/dix/onze/douze/treize/quatorze/et quart/seize/dix-sept/dix-huit/dix-neuf/vingt//et demi'.split('/')
n[21:22]=['vingt-'+i for i in['et-une']+n[2:10]]
h,m=t.hour,t.minute;s=h//12;h%=12
e=' d'+('u matin',("e l'après-midi","u soir")[h>4])[s]
try:m=' '[:m]+n[m]
except:m=' moins '+(n[60-m],'le quart')[m==45];h+=1
e,h=('',e,('minuit','midi')[h//12^s],n[h]+' heures'[:h+5])[h%12>0::2]
print('Il est',h+m+e+'.')

```

Ungolfed:

```
from datetime import datetime

time = datetime.now()
numbers = [
    '', 'une', 'deux', 'trois', 'quatre',
    'cinq', 'six', 'sept', 'huit', 'neuf',
    'dix', 'onze', 'douze', 'treize', 'quatorze',
    'et quart', 'seize', 'dix-sept', 'dix-huit', 'dix-neuf',
    'vingt', 'vingt-et-une', 'vingt-deux', 'vingt-trois', 'vingt-quatre',
    'vingt-cinq', 'vingt-six', 'vingt-sept', 'vingt-huit', 'vingt-neuf',
    'et demi']

status, hour = divmod(time.hour, 12)
if status:
    ending = " du soir" if h>4 else " de l’après-midi"
else:
    ending = " du matin"

try:
    if not time.minute:
        minutes = ""
    else:
        minutes = " " + numbers[time.minute]
except IndexError:
    hour += 1
    if time.minute == 45:
        minutes = " moins le quart"
    else:
        minutes = " moins " + numbers[60 - time.minute]

if hour%12:    # 'whole' hours
    hours = numbers[hour] + " heures"
    if hour == 1:
        # removing extra 's'
        hours = hours[:-1]
else:          # midnight or noon
    ending = ""
    if (hour == 12 and status) or (hour == 0 and status == 0):
        hours = "minuit"
    else:
        hours = "midi"

print('Il est', hours + minutes + ending + '.')

```
> 4 votes

# Answer
# Javascript (ES6), ~~506~~ 495 bytes

Edit: Compressed `a` to save a few bytes.

```
a=`
un
j
k
yre
h
six
w
v
p}
onldoultreilyorl
seize}-w}-v}-p~~ et un{j{k{yre{h{six{w{v{p
et demi`,[...`hjklpvwy{}~`].map((x,w)=>a=a.split(x).join(`cinq|deux|trois|ze
|neuf|huit|sept|quat|~-|
dix|
vingt`.split`|`[w])),a=a.split`
`,alert(`Il est ${(e=(d=((b=(z=new Date).getHours())+(y=(c=z.getMinutes())>30))%24)%12)?a[e]+` heure${e-1?"s":""}`:d?'midi':'minuit'} ${y?"moins ":""}${y?c-45?a[60-c]:'le quart':c-15?a[c]:'et quart'}${e?[' du matin'," de l'apres-midi",' du soir'][(b>12)+(b>16)]:""}.`)

```

Explanation:

```
a = 'compressed string of french numbers with 'et demi' for 30 and 15 removed';
a = // code that decompresses a

// a,b,c,d,e,y,z are all inlined into the first expression that uses them
z = new Date();
b = z.getHours();
c = z.getMinutes();
y = c > 30; // true if 60 - minutes, false otherwise
d = (b + y) % 24; // the next hour if y
e = d % 12; // is it not noon and not midnight?

alert(
    "Il est " +
    // add the hour
    // if d is not 0 or 12, add d + 'heure(s)'
    (e ? a[e] + ` heure${e-1?"s":""}` : d ? 'midi' : 'minuit') +
    " " +
    (y ? "moins " : "") + // add 'moins' if necessary

    ( // add the minute
      y? // necessary to subtract from 60?
        c-45?
          a[60-c] // add normal number word
          :'le quart' // handle special case for 45
        :c-15?
          a[c] // add normal word
          :'et quart' // handle special case for 15
    ) +
    ( // select appropriate ending
      e? // is it not noon and not midnight?
        // create array of endings
        [" du matin"," de l'apres-midi"," du soir"]
          // selects item 0 if b in [0, 12], item 1 if b in [13, 16] and item 2 if b > 16
          [(b > 12) + (b > 16)]
        :"" // if it's noon or midnight, no ending is necessary
    ) +
    "." // add period
)

```
> 3 votes

# Answer
# **C, ~~860 835~~ 794 bytes**

Absolutely horrendous, but can probably be made even shorter. Many newlines were added for formatting purposes on this site. The actual source code has newlines after the #includes and #defines, but everything starting from char\* to the last w(".\n");} are all in one line. I shortened it by removing the values from 22,...,29 in the string array, instead reusing the strings for 2,...,9 and prepending a "vingt-" when appropriate. (I really hope I didn't introduce a bug!)

```
#include <sys/time.h>
#define w printf
#define q tm_min
#define r tm_hour
char*a[]={"minuit","une","deux","trois","quatre","cinq","six","sept","huit","neuf","dix",
"onze","douze","treize","quatorze","quart","seize","dix-sept","dix-huit","dix-
neuf","vingt","vingt-et-une",0,0,0,0,0,0,0,0,"demi"};
h=1,s=1,m,e,l,t,p,o,v;struct tm j;
main(){struct timeval i;gettimeofday(&i,0);localtime_r(&i.tv_sec,&j);
j.q>30?m=1,++j.r,j.q=60-j.q:j.q==15||j.q==30?e=1:0;j.q>21&&j.q<30?v=1:0;
j.r%12?j.r<12?t=1:j.r-m<17?p=1:(o=1):0;
j.q==15&&m?l=1:0;j.r%12?j.r%12==1?s=0:0:(h=0,s=0);
w("Il est ");j.r==12?w("midi"):w("%s",a[j.r%12]);h?w(" heure"):0;s?w("s"):0;
m?w(" moins"):0;e?w(" et"):0;l?w(" le"):0;
j.q?v?w(" vingt-"):w(" "),w("%s",a[j.q-20*v]):0;
t?w(" du matin"):p?w(" de l'apres-midi"):o?w(" du soir"):0;w(".\n");}

```

Like this:

```
#include <sys/time.h>
#define w printf
#define q tm_min
#define r tm_hour
char*a[]={"minuit","une","deux","trois","quatre","cinq","six","sept","huit","neuf","dix","onze","douze","treize","quatorze","quart","seize","dix-sept","dix-huit","dix-neuf","vingt","vingt-et-une",0,0,0,0,0,0,0,0,"demi"};h=1,s=1,m,e,l,t,p,o,v;struct tm j;main(){struct timeval i;gettimeofday(&i,0);localtime_r(&i.tv_sec,&j);j.q>30?m=1,++j.r,j.q=60-j.q:j.q==15||j.q==30?e=1:0;j.q>21&&j.q<30?v=1:0;j.r%12?j.r<12?t=1:j.r-m<17?p=1:(o=1):0;j.q==15&&m?l=1:0;j.r%12?j.r%12==1?s=0:0:(h=0,s=0);w("Il est ");j.r==12?w("midi"):w("%s",a[j.r%12]);h?w(" heure"):0;s?w("s"):0;m?w(" moins"):0;e?w(" et"):0;l?w(" le"):0;j.q?v?w(" vingt-"):w(" "),w("%s",a[j.q-20*v]):0;t?w(" du matin"):p?w(" de l'apres-midi"):o?w(" du soir"):0;w(".\n");}

```

Ungolfed version, with no "space optimizations" (also pretty ugly):

```
#include <stdio.h>
#include <string.h>
#include <time.h>

#include <sys/time.h>

int main(int argc, char *argv[])
{
        struct timeval tv;
        struct tm local_time;
        char *nums[] = {"minuit", "une", "deux", "trois", "quatre", "cinq", "six", "sept", "huit", "neuf", "dix", "onze", "douze", "treize", "quatorze", "quart", "seize", "dix-sept", "dix-huit", "dix-neuf", "vingt", "vingt-et-une", "vingt-deux", "vingt-trois", "vingt-quatre", "vingt-cinq", "vingt-six", "vingt-sept", "vingt-huit", "vingt-neuf", "demi"};
        int heure = 1;
        int s = 1;
        int moins = 0;
        int et = 0;
        int le = 0;
        int matin = 0, aprem = 0, soir = 0;

        memset(&local_time, 0, sizeof local_time);
        gettimeofday(&tv, NULL);
        localtime_r(&tv.tv_sec, &local_time);

#if 0
        local_time.tm_min = atoi(argv[1]);
        local_time.tm_hour = atoi(argv[2]);
#endif
        if (local_time.tm_min > 30) {
                moins = 1;
                local_time.tm_hour += 1;
                local_time.tm_min = 60 - local_time.tm_min;
        } else if (local_time.tm_min == 15 || local_time.tm_min == 30) {
                et = 1;
        }

        if (local_time.tm_hour % 12) {
                if (local_time.tm_hour < 12)
                        matin = 1;
                else if (local_time.tm_hour < 17)
                        aprem = 1;
                else if (local_time.tm_hour == 17 && moins)
                        aprem = 1;
                else
                        soir = 1;
        }

        if (local_time.tm_min == 15 && moins)
                le = 1;

        if (local_time.tm_hour % 12 == 0) {
                heure = 0;
                s = 0;
        } else if (local_time.tm_hour % 12 == 1) {
                s = 0;
        }

        printf("Il est ");

        if (local_time.tm_hour == 12)
                printf("midi");
        else
                printf("%s", nums[local_time.tm_hour % 12]);

        if (heure)
                printf(" heure");

        if (s)
                printf("s");

        if (moins)
                printf(" moins");

        if (et)
                printf(" et");

        if (le)
                printf(" le");

        if (local_time.tm_min)
                printf(" %s", nums[local_time.tm_min]);

        if (matin)
                printf(" du matin");
        else if (aprem)
                printf(" de l'apres-midi");
        else if (soir)
                printf(" du soir");

        printf(".\n");
        return 0;
}

```

(The #if 0 stuff was just for testing different time values through the command-line).
> 2 votes

---
Tags: code-golf, string, date, natural-language
---


title: Numbers as Circular Graphics

text:
# Question
Title: Numbers as Circular Graphics
First, study this puzzle to get a feel for what you will be producing.

Your challenge is to write a program or function which will output a circular graphic like the ones from the puzzle, given a (base 10) number between 1 and 100 (inclusive). This is similar to this challenge, except that you will be producing a graphic rather than roman numerals. The following circles represent the numbers 1-10, from left to right:

As the answer to the puzzle states, your graphic should read like a roman numeral from the inside-out, where the line thickness represents the roman numeral symbols and the entire graphic represents the number. For your reference, here are the line thicknesses which you will need. Each line should have a 3px padding between it and the next.

```
Number  Roman Numeral   Line Width
1       I               1px
5       V               3px
10      X               5px
50      L               7px
100     C               9px

```

Please post a sample or two of your output. Assume input is correct, standard loopholes, etc and so forth. This is code golf, so fewest bytes win. In the event of a tie, most votes win. Good luck!

# Answer
## Mathematica - ~~166~~ 181 bytes

A bit more concise than the other Mathematica answer, thanks in part to a more point-free style.

```
c = Characters; r = Riffle;
Graphics[r[{0, 0}~Disk~# & /@ Reverse@Accumulate[
    l = {3} ~Join~ r[2 Position[c@"IVXLC", #][[1, 1]] - 1 & /@
        c@IntegerString[#, "Roman"], 3]], {White, Black}],
    ImageSize -> 2 Total@l] &

```

All whitespace is for clarity only. This defines an anonymous function which returns the desired graphic.

## Animation

Generating an animated GIF of the number circles is trivial in Mathematica, which has built-in functions for animating and exporting sequences of arbitrary objects. Assuming the above code has just been executed,

```
Table[Show[%@n, PlotRange -> {{-100, 100}, {-100, 100}},
    ImageSize -> 200], {n, 1, 399, 1}];
Export["animcircles.gif", %]

```

## Example Output
> 15 votes

# Answer
# Common Lisp - ~~376~~ ~~331~~ 304 bytes

```
(use-package(car(ql:quickload'vecto)))(lambda(n o &aux(r 3)l p)(map()(lambda(c)(setf l(position c" I V X L C D M")p(append`((set-line-width,l)(centered-circle-path 0 0,(+(/ l 2)r))(stroke))p)r(+ r l 3)))(format()"~@R"n))(with-canvas(:width(* 2 r):height(* 2 r))(translate r r)(map()'eval p)(save-png o)))

```

# Examples

(1) (24)

(104) (1903) (3999)

## Animation

For numbers from 1 to 400:

**NB:** For the record, this animation is done as follows:

I have a modified version of the code, named `rings` which returns the width of the produced image. Hence, the result of the the following loop is the maximum size, here **182**:

```
 (loop for x from 1 to 400
       maximize (rings x (format nil "/tmp/rings/ring~3,'0d.png" x)))

```

The whole loop takes 9.573 seconds. That gives approximately 24ms for each integer. Then, in a shell:

```
 convert -delay 5 -loop 0 -gravity center -extent 182x182 ring*png anim.gif

```

## Ungolfed

```
(ql:quickload :vecto)
(use-package :vecto)

(lambda (n o)
  (loop with r = 3
        for c across (format nil "~@R" n)
        for l = (1+ (* 2(position c"IVXLCDM")))
        for h = (/ l 2)
        collect `(,(incf r h),l) into p
        do (incf r (+ h 3))
        finally (with-canvas(:width (* 2 r) :height (* 2 r))
                  (loop for (x y) in p
                        do (set-line-width y)
                           (centered-circle-path r r x)
                           (stroke))
                  (save-png o))))

```

## Explanations

* The function takes an integer `N` between 1 and 3999 and a filename
* I use `(format nil "~@R" N)` to convert from decimal to roman. For example:

```
 (format nil "~@R" 34) => "XXXIV"

```

The `~@R` format control string is specified to work for integers between 1 and 3999. That's why there is a limitation for the range of allowed inputs.
* I iterate over the resulting string to build a list `P` containing `(radius width)` couples, for each numeral C.

+ The width is a simple linear mapping: I use the constant string "IVXLCDM" to compute the position of C in it. Multiplying by two and adding one, we obtain the desired value:

    ```
           (1+ (* 2 (position c "IVXLCDM")))

    ```

    This is however done slightly differently in the golfed version:

    ```
           (position c " I V X L C D M")

    ```
    + The computation of each radius takes into account the width of each ring as well as empty spaces between rings. Without any speed optimization, computations remain precise because they are not based on floats, but rational numbers.

    *Edit*: I changed the parameters to comply with the padding rules.
* Once this is done, I know the required size of the resulting canvas (twice the latest computed radius).
* Finally, I draw a circle for each element of `P` and save the canvas.
> 15 votes

# Answer
## HTML+JQuery, 288

**HTML**

```
<canvas>

```

**JS**

```
    r=3;w=9;c=$('canvas').get(0).getContext('2d')
    for(i=prompt(),e=100;e-.1;e/=10){
    if((x=Math.floor(i/e)%10)==4)d(w)+d(w+2)
    else if(x==9)d(w)+d(w+4)
    else{if(x>4)d(w+2)
    for(j=x%5;j;j--)d(w)}
    w-=4}
    function d(R){c.lineWidth=R
    c.beginPath()
    c.arc(150,75,r+=R/2,0,7)
    c.stroke()
    r+=R/2+3}

```

```
r=3;w=9;c=$('canvas').get(0).getContext('2d')
for(i=prompt(),e=100;e-.1;e/=10){
if((x=Math.floor(i/e)%10)==4)d(w)+d(w+2)
else if(x==9)d(w)+d(w+4)
else{if(x>4)d(w+2)
for(j=x%5;j;j--)d(w)}
w-=4}
function d(R){c.lineWidth=R
c.beginPath()
c.arc(150,75,r+=R/2,0,7)
c.stroke()
r+=R/2+3}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
<canvas>
```

Fiddle
> 8 votes

# Answer
# Java, 565

```
import java.awt.*;class Z{public static void main(String[]s){int i=new Byte(s[0]),j=i/10,k=i%10;String t="",u;if(j>8)t="59";if(j>9)t="9";if(j==4)t="57";else if(j<9){t=j>4?"7":"";j-=j>4?5:0;if(j>0)t+="5";if(j>1)t+="5";if(j>2)t+="5";}if(k>8)t+="15";if(k==4)t+="13";else if(k<9){t+=k>4?"3":"";k-=k>4?5:0;if(k>0)t+="1";if(k>1)t+="1";if(k>2)t+="1";}u=t;Frame f=new Frame(){public void paint(Graphics g){g.setColor(Color.BLACK);int x=0;for(char c:u.toCharArray()){int z=c-48,q=x;for(;x<q+z;)g.drawOval(99-x,99-x,x*2,x++*2);x+=3;}}};f.setSize(200,200);f.setVisible(1>0);}}

```

## Examples

### 15

### 84

### 93

Formatted nicely:

```
import java.awt.*;
class Z {
    public static void main(String[] s) {
        int i = new Byte(s[0]), j = i / 10, k = i % 10;
        String t = "", u;
        if (j > 8)
            t = "59";
        if (j > 9)
            t = "9";
        if (j == 4) {
            t = "57";
        } else if (j < 9) {
            t = j > 4 ? "7" : "";
            j -= j > 4 ? 5 : 0;
            if (j > 0)
                t += "5";
            if (j > 1)
                t += "5";
            if (j > 2)
                t += "5";
        }
        if (k > 8)
            t += "15";
        if (k == 4) {
            t += "13";
        } else if (k < 9) {
            t += k > 4 ? "3" : "";
            k -= k > 4 ? 5 : 0;
            if (k > 0)
                t += "1";
            if (k > 1)
                t += "1";
            if (k > 2)
                t += "1";
        }
        u = t;
        Frame f = new Frame() {
            public void paint(Graphics g) {
                g.setColor(Color.BLACK);
                int x = 0;
                for (char c : u.toCharArray()) {
                    int z = c - 48, q = x;
                    for (; x < q + z;) {
                        g.drawOval(99 - x, 99 - x, x * 2, x++ * 2);
                    }
                    x += 3;
                }
            }
        };
        f.setSize(200, 200);
        f.setVisible(1 > 0);
    }
}

```
> 5 votes

# Answer
## Mathematica 9 - 301 249 bytes

:D It feels cheaty to use the built-in converting to Roman numerals, but hey.

```
l=Length;k=Characters;r@n_:=(w=Flatten[Position[k@"IVXLC",#]*2-1&/@k@IntegerString[n,"Roman"]];Show[Table[Graphics@{AbsoluteThickness@w[[i]],Circle[{0,0},(Join[{0},Accumulate[3+w]]+3)[[i]]+w[[i]]/2]},{i,Range@l@w}],ImageSize->{(Total@w+(l@w)*3)*2}])

```

(When I did this last night I didn't have much time, but I realized it could be golfed down way more. And I also took some hints from David Zhang... :D Thanks!)

A bit more clearly:

```
l=Length;
k=Characters;
r@n_:=
    (
    w=Flatten[Position[k@"IVXLC",#]*2-1&/@k@IntegerString[n,"Roman"]];
    Show[Table[Graphics@{AbsoluteThickness@w[[i]],Circle[{0,0},(Join[{0},Accumulate[3+w]]+3)[[i]]+w[[i]]/2]},{i,Range@l@w}],ImageSize->{(Total@w+(l@w)*3)*2}]
    )

```

This is a function that you can call like this:

```
r[144]

```

Or, you can show the results from values **a** to **b** with: `Table[r[i],{i,a,b}]`

*Note*: This only works for values up to 399.
> 3 votes

# Answer
# Python 2, ~~322~~ 296

The script reads the number to be converted from stdin, and outputs the image as SVG markup.

.. I use 'red' instead of 'black', because it saves 2 chars :)

Here are some samples : for 23 : http://jsfiddle.net/39xmpq49/ for 42 : http://jsfiddle.net/7Ls24q9e/1/

```
i=input();r=9
def R(n,p):
 global r,i;i-=n;print '<circle r="{0}" stroke-width="{1}"/>'.format(r,p);r+=p+3
print '<svg viewBox="-50 -50 99 99" fill="none" stroke="red">',[[R(n,int(p)) for p in s*int(i/n)] for n,s in zip([100,90,50,40,10,9,5,4,1],'9/59/7/57/5/15/3/13/1'.split('/'))]and'','</svg>'

```
> 1 votes

# Answer
# JavaScript ~~342~~ ~~334~~ 308

```
function R(n){var v=document,o=[],x=1,c=v.body.appendChild(v.createElement('canvas')).getContext('2d')
while(n)v=n%10,y=x+2,o=[[],[x],[x,x],[x,x,x],[x,y],[y],[y,x],[y,x,x],[y,x,x,x],[x,x+=4]][v].concat(o),n=(n-v)/10
v=3
while(x=o.shift())c.lineWidth=x,c.beginPath(),c.arc(150,75,v+x/2,0,7),c.stroke(),v+=x+3}

for (var i = 1; i <= 100; i++) {
  R(i);
}
```
> 1 votes

---
Tags: code-golf, graphical-output, number, roman-numerals
---


title: Ode Golf - Letter Deletions

text:
# Question
Title: Ode Golf - Letter Deletions
Given a dictionary file (a text file containing a word or phrase on each line, with possible punctuation but no numbers; lines are alphabetized), you must output each combination of words where one letter can be removed from a word to make another; the removed letter should be encased in parentheses.

For example, the input

```
cat
cart
code
golf
ode
verify
versify

```

should give an output of

```
ca(r)t
(c)ode
ver(s)ify

```

Multiple ways to get the same pair must only be displayed once. You can output `scra(p)ped` or `scrap(p)ed`, but not both.

The output should be ordered *alphabetically* by the longer entry;

```
mart
mar
mat
ma

```

should have an output of

```
ma(r)
ma(t)
ma(r)t
mar(t)

```

and the latter two could be in either order.

The dictionary file may include capitalizations, spaces, hyphens, or apostrophes; these should be ignored. For instance,

```
inlay
in-play

```

should produce `in(p)lay`. Your output should all be in the same case. Extra whitespace is allowed.

Input can be STDIN or from a file; it is separated by newlines. Output can be return value of a function or STDOUT (or written to a file if you wanted).

This is , so the shortest code in bytes wins.

(This is my first challenge on PPCG - let me know if I've done anything wrong and I'll fix it.)

# Answer
> 1 votes
# Perl -an0, 101+3 bytes

```
@F=sort{length$a<=>length$b}map{s/\W//g;lc}@F;map{$`.$'~~@F?print"$`($1)$'\n":$\while/(.)(?!\1)/g}@F;

```

where

* `@F` is the dictionary, stored in an array, provided by runtime flag magic. *(b-oost, BoO#@%@#$%$#@T)*
* `map{s/\W//g;lc}@F` removes all symbols from the words and turns everything lowercase. *(boost, boot)*
* `sort{length$b<=>length$a}` sorts on length. *(boot, boost)*
* `map{ (...) while/(.)(?!\1)/g}@F` matches all characters that aren't followed up by the same character *(\[b\]oot, bo\[o\]t,boo\[t\],...)*
* `print"$`($1)$'\n"` prints the parts that precede, parenthesize, and succeed a match... *(boo(s)t)*
* `if $`.$'~~@F` ...if the concatenation of everything before and after the match is in the dictionary. *(\[boo\]s\[t\])*

# Answer
> 5 votes
# JavaScript (ES6), 225

A function with a string parameter, no input from file. I asked OP if this could be valid.

Test running the snippet in an EcmaScript 6 compliant browser (implementing arrow functions, template string, spread operator - Firefox, maybe Safari or MS Edge, not Chrome)

```
f=t=>t.split`
`.map(w=>(d[k=w.replace(/\W/g,'').toLowerCase()]={},k),d={},r=[]).map(w=>[...w].map((c,i,v)=>(d[v[i]='',x=v.join``]&&!d[x][w]&&r.push(d[x][w]=(v[i]=`(${c})`,v.join``)),v[i]=c)))&&r.sort((a,b)=>a.length-b.length)

// LESS GOLFED

Q=t=>{
  // convert to canonical form and put in a dictionary
  // each value in the dictionary is an hashtable tha will store the list
  // of words that can generate the current word, removing a letter
  d={},
  t=t.split`\n`.map(w=>(k=w.replace(/\W/g,'').toLowerCase(),d[k]={},k))
  r=[], // result array
  t.forEach(w =>
    [...w].forEach((c,i,v)=>( // for each letter in word, try to remove
      v[i]='', x=v.join``, // build string with missing letter
      v[i]='('+c+')', y=v.join``, // and build string with brackets
      v[i]=c, // restore the current letter
      d[x] && // if the word with removed letter is present in the dictionary
      !d[x][w] && // and not already from the same generating word
         r.push(d[x][w]=y) // update dictionary and add word to result array
    ))
  )
  return r.sort((a,b)=>a.length-b.length) // sort result by length
}

// TEST
function test() { R.innerHTML=f(I.value) }
```

```
textarea { height: 20em }
```

```
Test <button onclick="test()">-></button>
<span id=R></span>
<br><textarea id=I>cat
cart
code
golf
node
scraped
scrapped
verify
versify
mart
mar
mat
ma</textarea>
```

# Answer
> 3 votes
# Ruby, 173

```
->d{o=[]
c={}
d=d.sort_by{|w|[w.size,w]}.map{|w|w=w.upcase.gsub /[^A-Z]/,''
c[w]=l=1
w.size.times{|i|p,x,s=w[0...i],w[i],w[i+1..-1]
c[p+s]&&l!=x&&o<<p+"(#{w[i]})"+s
l=x}}
o}

```

Test it here: http://ideone.com/86avbe

Readable version here: http://ideone.com/ynFItB

# Answer
> 1 votes
# Ruby, 211

I decided I'd take a different approach to solve this, using regex.

```
->d{o=[]
d.map{|x|x.upcase!.gsub! /[-' ]/,''}
d.map{|x|(x.size+1).times{|i|o+=d.map{|w|w.b.sub! /(#{x[0...i]})(.)(#{x[i..-1]})/,'\1(\2)\3'if w[i]!=w[i+1]}}}
o.compact.sort_by{|w|[w.size,w.gsub(/[()]/,'')]}.uniq}

```

# Answer
> 0 votes
# Perl 5, 210

The code loads the input in an sorted array, and checks for each value against all values in the array that are 1 byte longer.

```
map{@W=split//,$w=$_;map{@X=split//,$x=$_;if(@W+1==@X){$i=0;while($W[$i]eq$X[$i]&&$i<@W){$i++}$c=$X[$i];$e=substr($w,$i);print substr($w,0,$i)."($c)$e\n",if substr($x,$i+1)eq$e}}@D}@D=sort(map{s/[^\w]//g;lc}<>)

```

### Test

```
$ perl dictionairy_same_words.pl dictionairywords.txt
ca(r)t
in(p)lay
ma(r)
ma(t)
mar(t)
ma(r)t
(c)ode
ver(s)ify

```

# Answer
> 0 votes
# Haskell, 201 bytes

```
import Data.List
import Data.Char
a#(b:c)=(a,b,c)
g a=[l++'(':m:')':n|x<-a,((l,m,n):_)<-[[o|o@(i,j,k)<-zipWith(#)(inits x)$init$tails x,elem(i++k)a]]]
f=sortOn length.g.map(filter isLetter.map toLower)

```

I'm not sure what input format is allowed. `f` takes a list of strings. If only a single string (with nl separated words) is allowed, add `.lines` to `f` (+6 bytes).

Usage example:

```
f ["cat","cart","code","golf","od-e","verify","versify","on","s-o-n","Scrapped","scraped"]

["(s)on","ca(r)t","(c)ode","ver(s)ify","scra(p)ped"]

```

How it works: turn every word to lowercase and keep only the letters. Split every word `x` into two parts at every possible position and make triples `(i,j,k)` where `i` is the first part, `j` is the first character of the second part and `k` is the tail of the second part. Keep the triples where `i++k` also appears in the word list. If this list is non-empty, take the first element, call it `(l,m,n)`. Turn all those list heads into the required output format by surrounding `m` with `()` and putting it between `l` and `n`.

---
Tags: code-golf, string
---


title: Lisp Extraction Mission

text:
# Question
Title: Lisp Extraction Mission
In Lisp style languages, a list is usually defined like this:

```
(list 1 2 3)

```

For the purposes of this challenge, all lists will only contain positive integers or other lists. We will also leave out the `list` keyword at the start, so the list will now look like this:

```
(1 2 3)

```

We can get the first element of a list by using `car`. For example:

```
(car (1 2 3))
==> 1

```

And we can get the original list with the first element removed with `cdr`:

```
(cdr (1 2 3))
==> (2 3)

```

Important: `cdr` will always return a list, even if that list would have a single element:

```
(cdr (1 2))
==> (2)
(car (cdr (1 2)))
==> 2

```

Lists can also be inside other lists:

```
(cdr (1 2 3 (4 5 6)))
==> (2 3 (4 5 6))

```

Write a program that returns code that uses `car` and `cdr` to return a certain integer in a list. In the code that your program returns, you can assume that the list is stored in `l`, the target integer is in `l` somewhere, and that all the integers are unique.

Examples:

Input: `(6 1 3) 3`

Output: `(car (cdr (cdr l)))`

Input: `(4 5 (1 2 (7) 9 (10 8 14))) 8`

Output: `(car (cdr (car (cdr (cdr (cdr (cdr (car (cdr (cdr l))))))))))`

Input: `(1 12 1992) 1`

Output: `(car l)`

# Answer
# CJam, 59

```
q"()""[]"er~{:AL>{0jA1<e_-_A(?j'l/"(car l)"@{2'dt}&*}"l"?}j

```

Try it online

**Explanation:**

```
q                 read the input
"()""[]"er        replace parentheses with square brackets
~                 evaluate the string, pushing an array and a number
{…}j              calculate with memoized recursion using the array as the argument
                   and the number as the memozied value for argument 0
  :A              store the argument in A
  L>              practically, check if A is an array
                   if A is a (non-empty) array, compare with an empty array
                   (result 1, true)
                   if A is a number, slice the empty array from that position
                   (result [], false)
    {…}           if A is an array
      0j          get the memoized value for 0 (the number to search)
      A1<         slice A keeping only its first element
      e_          flatten array
      -           set difference - true iff the number was not in the array
      _           duplicate the result (this is the car/cdr indicator)
      A(          uncons A from left, resulting in the "cdr" followed by the "car"
      ?           choose the cdr if the number was not in the flattened first item,
                   else choose the car
      j           call the block recursively with the chosen value as the argument
      'l/         split the result around the 'l' character
      "(car l)"   push this string
      @           bring up the car/cdr indicator
      {…}&        if true (indicating cdr)
        2'dt      set the character in position 2 to 'd'
      *           join the split pieces using the resulting string as a separator
    "l"           else (if A is not an array) just push "l"
                   (we know that when we get to a number, it is the right number)
    ?             end if

```
> 1 votes

# Answer
# Common Lisp, 99

The following 99 bytes solution is a CL version of the nice Scheme answer.

```
(defun g(l n &optional(o'l))(if(eql n l)o(and(consp l)(or(g(car l)n`(car,o))(g(cdr l)n`(cdr,o))))))

```

I originally tried to make use of `position` and `position-if`, but it turned out to be not as compact as I would have liked (209 bytes):

```
(lambda(L x &aux(p'l))(labels((f(S &aux e)(cons(or(position x S)(position-if(lambda(y)(if(consp y)(setf e(f y))))S)(return-from f()))e)))(dolist(o(print(f L))p)(dotimes(i o)(setf p`(cdr,p)))(setf p`(car,p)))))

```

### Expanded

```
(lambda
  (l x &aux (p 'l))
  (labels ((f (s &aux e)
             (cons
              (or (position x s)
                  (position-if
                   (lambda (y)
                     (if (consp y)
                         (setf e (f y))))
                   s)
                  (return-from f nil))
              e)))
    (dolist (o (print (f l)) p)
      (dotimes (i o) (setf p `(cdr ,p)))
      (setf p `(car ,p)))))

```

### Example

```
(funcall *fun* '(4 5 (1 2 (7) 9 (10 8 14))) 14)

```

The list is quoted, but if you really want, I can use a macro. The returned value is<sup>\[1\]</sup>:

```
(CAR (CDR (CDR (CAR (CDR (CDR (CDR (CDR (CAR (CDR (CDR L)))))))))))

```

For tests, I used to generate a lambda form where `l` was a variable:

```
(LAMBDA (#:G854) (CAR (CDR (CDR (CAR (CDR (CDR (CDR (CDR (CAR (CDR (CDR #:G854))))))))))))

```

Calling this with the original list returns 14.

---

\[1\] `(caddar (cddddr (caddr l)))` would be nice too
> 10 votes

# Answer
# Retina, ~~170~~ ~~142~~ ~~125~~ ~~115~~ ~~114~~ ~~87~~ ~~84~~ ~~83~~ ~~75~~ ~~73~~ ~~70~~ ~~69~~ ~~68~~ 67 bytes

Yay, ~~less than 50% of~~ more than 100 bytes off my first attempt. :)

```
\b(.+)\b.* \1$
(
^.
l
\(
a
+`a *\)|\d

d
+`(.*[l)])(\w)
(c$2r $1)

```

To run the code from a single file, use the `-s` flag.

I'm still not convinced this is optimal... I won't have a lot of time over the next few days, I will add an explanation eventually.
> 9 votes

# Answer
# Pyth, 62 bytes

```
JvXz"() ,][")u?qJQG&=J?K}Quu+GHNY<J1)hJtJ++XWK"(cdr "\d\aG\)\l

```

Try it online: Demonstration or Test Suite

### Explanation:

The first bit `JvXz"() ,][")` replaces the chars `"() "` with the chars `"[],"` in the input string, which ends up in a representation of a Python-style list. I evaluate it and store it in `J`.

Then I reduce the string `G = "l"` with `u...\l`. I apply the inner function `...` repeatedly to `G`, until the value of `G` doesn't change anymore and then print `G`.

The inner function does the following: If `J` is already equal to the input number, than don't modify `G` (`?qJQG`). Otherwise I'll flatten the the list `J[:1]` and check if the input number is in that list and save this to the variable `K` (`K}Quu+GHNY<J1)`). Notice that Pyth doesn't have a flatten operator, so this is takes quite a few bytes. If `K` is true, than I update J with `J[0]`, otherwise with `J[1:]` (`=J?KhJtJ`). And then I replace `G` with `"(cdr G)"` and replace the `d` the `a`, if `K` is true (`++XWK"(cdr "\d\aG\)`).
> 5 votes

# Answer
## Scheme (R5RS), 102 bytes

```
(let g((l(read))(n(read))(o'l))(if(pair? l)(or(g(car l)n`(car,o))(g(cdr l)n`(cdr,o)))(and(eq? n l)o)))

```
> 5 votes

# Answer
## PHP - 177 bytes

I've added some newlines for readability:

```
function f($a,$o,$n){foreach($a as$v){if($n===$v||$s=f($v,$o,$n))return
'(car '.($s?:$o).')';$o="(cdr $o)";}}function l($s,$n){echo f(eval(strtr
("return$s;",'() ','[],')),l,$n);}

```

Here is the ungolfed version:

```
function extractPhp($list, $output, $number)
{
    foreach ($list as $value)
    {
        if (is_int($value))
        {
            if ($value === $number) {
                return '(car '. $output .')';
            }
        }
        else
        {
            $subOutput = extractPhp($value, $output, $number);
            if ($subOutput !== null) {
                return '(car '. $subOutput .')';
            }
        }

        $output = '(cdr '. $output .')';
    }
}

function extractLisp($stringList, $number)
{
    $phpCode = 'return '. strtr($stringList, '() ','[],') .';';
    $list = eval($phpCode);
    echo extractPhp($list, 'l', $number);
}

```
> 1 votes

# Answer
# Haskell, ~~190~~ 188 bytes

`l "(4 5 (1 2 (7) 9 (10 8 14)))" 8`

evaluates to

`"(car (cdr (car (cdr (cdr (cdr (cdr (car (cdr (cdr l))))))))))"`

```
l(h:s)n=c$i(show n)s""""
i n(h:s)t l|h>'/'&&h<':'=i n s(t++[h])l|t==n='a':l|h=='('=j$'a':l|h==')'=j$tail$dropWhile(=='d')l|0<1=j$'d':l where j=i n s""
c[]="l"
c(h:s)="(c"++h:"r "++c s++")"

```
> 1 votes

# Answer
# Common Lisp, ~~168~~ 155 bytes

Some stupid recursion thing, it could probably be condensed a bit more:

```
(lambda(l e)(labels((r(l o)(setf a(car l)d(cdr l)x`(car,o)y`(cdr,o))(if(equal e a)x(if(atom a)(r d y)(if(find e l)(r d y)(if d(r d y)(r a x)))))))(r l'l)))

```

Pretty printed:

```
(lambda (l e)
  (labels ((r (l o)
             (setf a (car l) d (cdr l)
                   x `(car ,o) y `(cdr ,o))
             (if (equal e a) x
                 (if (atom a)
                     (r d y)
                     (if (find e l)
                         (r d y)
                         (if d
                             (r d y)
                             (r a x)))))))
    (r l 'l)))

```
> 0 votes

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


title: 3-D Antiferromagnetism

text:
# Question
Title: 3-D Antiferromagnetism
A while ago, we had a challenge related to antiferromagnetism (AF) in two dimensions. Now, on a 2-d square lattice, antiferromagnetic is antiferromagnetic, and that is all there is to it. Moving to other lattice types or higher dimensionality, things get more interesting. Here, we will explore the second route: magnetic order on the 3-d cubic lattice1.

We will consider the following spin patterns, as illustrated in the figure. The cubes are repeated periodically in every direction (“periodic boundary conditions”).

* *G-type* is the most straightforward generalization from 2-D AF: antiferromagnetic in all directions
* *A-type:* antiferromagnetically coupled ferromagnetic planes
* *C-type*: ferromagnetically coupled antiferromagnetic planes (a.k.a “checkerboard”)
* *D-type:* criss-crossing stripes
* *E-type* and *F-type:*ferrimagnetic planes”?
* *B-type* is ferromagnetic (FM) order

adapted from E. Dagotto, *Nanoscale phase separation and colossal magnetoresistance*

# The challenge

Your code should take a string as input specifying a magnetic order and a lattice plane, and output the spin arrangement on that plane, in the orientation specified below. Output should be “drawn“ in some sense: writing to STDOUT, graphical output, or similar; a function returning a string is not enough.

You must support at least A-, C-, and G-type (the more familiar AF arrangements); B-, E-, and F-type may be supported optionally. Your score will be code length per order type supported.

## Input

Input will be of the form `S (a b c)`, i.e., a token *S* specifying the order type, a space, and three integers *a,b,c* defining a lattice plane, enclosed in parentheses and delimited by spaces.

The string *S* will be either “AF-*T*” with *T* ∈ {A, C, D, E, F, G} for the antiferromagnetic cases, or “FM” in the ferromagnetic case (B).

We define the following coordinate system relative to the figure: the x-axis points to the right, the y-axis into the screen, and the z-axis upwards; the origin is the lower left front corner of the cube, and the lattice parameter (the side length of the cube) will be 1.

For simplicity, exactly one of the integers *a,b,c* will be nonzero. The plane of projection is perpendicular to the corresponding axis and displaced from the origin by that number of unit cells.2 To get the proper orientation, look along the axis of displacement in positive/negative direction according to the displacement, and rotate such that the first in-plane axis (alphabetically: *y* for the *yz*-plane, *x* otherwise) increases to the right. Examples are given below.

## Output

On the selected plane, the spins are arranged on a square lattice. Your code should draw 2×2 spins (the “magnetic unit cell”) on this plane, taking into account the periodicity and the proper orientation.

### A ↑ by any other name …

Spin “up” and “down” are just names,3 and I do not want to limit your artistic freedom. Choose any (visually distinguishable) symbols for the spin directions you like, they only have to be consistent and laid out on a “square” lattice (as rectangular as necessary according to output format). You can use ASCII/Unicode art, graphical output, what have you. Leading or trailing white space does not matter.

## Examples of input, valid output, and orientation

```
A (0 0 1)  C (1 0 0)  D (0 0 2)  E (0 1 0)  F (0 -2 0)  G (0 0 7)
   - -       ↓  ↑        ud         0 1       ->  ->        •
   - -       ↓  ↑        ud         1 0       ->  <-       •

  --> x      --> y      --> x      ^ z         --> x       --> x
  |          |          |          |           |           |
  V y        V z        V y        --> x       V z         V y

```

# Scoring

Your score is *B/O*, the length *B* of your code in bytes divided by the number of patterns *O* your code supports (*O* is between 3 and 7). Smallest score wins.

In your answer, please indicate (i) code length, (ii) supported orders, and (iii) sample output, and (iv) the correspondence of your symbols with `+` and `-` in the figure, if yours are different.

1. Which is the analogue of the square lattice in three dimensions. The general term would be “hypercubic”.

2. They are a perverted variation of Miller indices.

3. We are being strictly non-relativistic here.

# Answer
> 1 votes
# Ruby Rev 1, 176/7 = 25.14

Problem with negative inputs fixed: `m>>9&2` shifts the characters by 2 when `m` is negative.

Magic strings with non-ASCII characters proved problematic: they produced syntax errors. So I just compressed the data to a hexadecimal number instead.

```
a=gets.delete("()").split
m=e=0
4.times{|i|m+=b=a[i].to_i;b>0&&e=i-1}
4.times{|c|print 0xFFF9935871769>>568-a[0].ord*8+(" j\204\316"[c-(m>>9&2)].ord>>e*3&7^m%2<<e)&1,"
"[c%2]}

```

# Ruby Rev 0, 174/7 = 24.86

work in progress. I just realized I missed a rule: I have to flip the output vertically when the input is negative. Once checked and clarified I will golf the magic strings / arrays down to single characters.

```
a=gets.delete("()").split
m=e=0
4.times{|i|m+=b=a[i].to_i;b>0&&e=i-1}
" j\204\316".bytes{|c|print [15,255,153,53,135,23,105][a[0].ord-65]>>(c>>e*3&7^m%2<<e)&1,c==106?"\n":''}

```

The first magic string contains 4 bytes, corresponding to the first, second, third and 4th symbol to be printed. Each is a 3-digit octal number indicating which bit of the data in the array should be displayed. The table looks like this. Note that the odd values differ from the even ones by a power of 2 so only the even values need be stored. Fortunately the z values never exceed 3, so it's possible to get the 3 octal digits into 1 byte.

```
nonzero digit    x    y    z
                02   45   01
even            46   01   23

                13   67   45
odd             57   23   67

```

**Output**

I use 1 for +, 0 for - . I didnt bother with the output for B because it's just plain 1's.

```
A 1 0 0
11
00
A 2 0 0
11
00
A 0 1 0
00
11
A 0 2 0
00
11
A 0 0 1
00
00
A 0 0 2
11
11

C 1 0 0
01
01
C 2 0 0
10
10
C 0 1 0
01
01
C 0 2 0
10
10
C 0 0 1
10
01
C 0 0 2
10
01

D 1 0 0
00
10
D 2 0 0
11
10
D 0 1 0
00
10
D 0 2 0
11
10
D 0 0 1
11
00
D 0 0 2
10
10

E 1 0 0
10
01
E 2 0 0
11
00
E 0 1 0
01
10
E 0 2 0
00
11
E 0 0 1
00
01
E 0 0 2
11
10

F 1 0 0
10
00
F 2 0 0
11
10
F 0 1 0
00
10
F 0 2 0
10
11
F 0 0 1
10
00
F 0 0 2
11
10

G 1 0 0
01
10
G 2 0 0
10
01
G 0 1 0
10
01
G 0 2 0
01
10
G 0 0 1
01
10
G 0 0 2
10
01

```

# Answer
> 2 votes
# Octave, 809/7 ≈ 115.57

This is a reference implementation supporting all 7 order types (not quite, since it does not parse the input string), ungolfed.

Output for all distinct inputs is available for download. Assuming the implementation is correct, there are 13 distinct outputs, two of which are unique; one more occurs twice; all others at least four times.

```
format plus "+-."

A = ones(2,2,2);
A(:,:,2) = -1;

B = ones(2,2,2);

C(:,:,1) = [ 1 -1; -1  1];
C(:,:,2) = C(:,:,1);

D(:,:,1) = [ 1  1; -1 -1];
D(:,:,2) = D(:,:,1)';

E(:,:,1) = [ 1  1;  1 -1];
E(:,:,2) = -E(:,:,1);

F(:,:,1) = E(:,:,1);
F(:,:,2) = [ 1 -1; -1 -1];

G(:,:,1) = C(:,:,1);
G(:,:,2) =-G(:,:,1);

function SP = afmproj(S, idx)
  dim = find(idx)(1);
  idx = idx(dim);
  sgn = sign(idx);
  idx = mod(idx, 2) + 1;

  switch dim
    case 1
      SP = S(idx,:,:); flp = sgn==+1;
    case 2
      SP = S(:,idx,:); flp = sgn==-1;
    case 3
      SP = S(:,:,idx); flp = sgn==+1;
  endswitch

  SP = rot90(reshape(SP,2,2));

  if flp
    SP = flipud(SP);
  endif
endfunction

function afmproj_pretty(Str, S, idx)
  printf('%s (%2i %2i %2i)\n', Str, idx);
  disp(afmproj(S, idx));
  disp('')
endfunction

```

---
Tags: code-golf, ascii-art, graphical-output, physics
---


title: Crack a Vigenère Cipher

text:
# Question
Title: Crack a Vigenère Cipher
A Vigenère Cipher is encrypted by repeating a keyword to be the length of the plaintext, and summing each character in that text with the corresponding letter in the plaintext modulo 26. (using A=0,B=1 etc.)

For example, if the keyword is `LEMON` and the plaintext is `ATTACKATDAWN`, then the key is repeated to form `LEMONLEMONLE`, which is summed with the plaintext to form the ciphertext, `LXFOPVEFRNHR`.

Write a program or function which, given a list of words and a ciphertext, outputs all possible plaintexts for that ciphertext, such that the plaintext is the concatenation of words in the list, and the key is also a word from the list.

All words use only upper-case letters `A` to `Z`.

**Your code must run in polynomial time** with respect to the total length of the ciphertext and words list.

Shortest code (in bytes) wins.

# Example Inputs/Outputs

The input/output format for your program is flexible, but here I'm giving the list of words separated by commas followed by the ciphertext as input, and the output is the list of plaintexts separated by commas.

## Inputs

```
LEMON,ATTACK,AT,DAWN,BUNNY
LXFOPVEFRNHR

A,AA,AAA,AAAA,AAAAA,AAAAAA,AAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

XHQT,GIXIIR,QTIA,AZXO,KSECS,THIS,CIPHER,IS,EASY,TO,CRACK,CODE,GOLF
ZVTXIWAMKFTXKODDZCNWGQV

A,B,C,D,E,F,G,H,Z
DBCCBHF

A,AA
AAA

```

## Outputs

```
ATTACKATDAWN

(none)

THISCIPHERISEASYTOCRACK,XHQTGIXIIRQTIAAZXOKSECS

BZAAZFD,CABBAGE,DBCCBHF

AAA

```

# Answer
> 2 votes
# *Doesn’t respect specifications* – OCaml - 118 bytes

I’ll get back to it when I’ll have time on my hand.

```
open Char;;
fun m->List.map(fun k->String.mapi(fun i c->chr(65+(code c-code k.[i mod String.length k]+26)mod 26))m);;

```

> `- : string -> string list -> string list = <fun>`

As the function type shows, the function expect as arguments:

* a string: the encoded message
* a list of strings: the keys

It returns a list of strings, the messages as decoded by each string in the same order.

The function is anonymous, you can call it by inserting putting it inside parentheses (i.e. 2 bytes) and entering its arguments as follows:

```
open Char;;
(fun m->List.map(fun k->String.mapi(fun i c->chr(65+(code c-code k.[i mod String.length k]+26)mod 26))m)"ZVTXIWAMKFTXKODDZCNWGQV"["XHQT";"GIXIIR";"QTIA";"AZXO";"KSECS";"THIS";"CIPHER";"IS";"EASY";"TO";"CRACK";"CODE";"GOLF"];;

```

## Ungolfed

```
(* unshift the character x back to what it was before being shifted by k *)
(* Char.chr and Char.code translate from ASCII int to char and back      *)
(* '+ 26' because the modulo operator can return negative numbers -__-   *)
open Char;;
let unshift k x = chr ( 65 + (code x - code k + 26) mod 26 );;
(* Use the n-th character of the key to decrypt x, loops when necessary  *)
let unshiftWithKeyAtPos key n x = unshift key.[n mod String.length key] x;;

(* Maps unshiftWithKeyAtPos key i x for each position i in cipherText    *)
(* where x = cipherText.[i] is the i-th character of cipherText.         *)
let decrypt key cipherText = String.mapi (unshiftWithKeyAtPos key) cipherText;;

(* Maps decrypt cipherText key for each key in keyList                   *)
let tryHard cipherText keyList = List.map (fun key -> decrypt key cipherText) keyList;;

(* And finally, call the function                                        *)
let hiddenMessage = "LXFOPVEFRNHR";;
let keys = ["LEMON";"CODE";"GOLF"];;
tryHard hiddenMessage keys;;

```

# Answer
> 1 votes
# Python 2.7 - 235

Example solution to start things off. Should be pretty easy to beat.
Input is given as a python tuple from stdin (ex. `(["A","AA"],"AAA")`.

```
W,c=input();M={}
def s(t,r):M[t]=r;return r
g=lambda t:M[t]if t in M else not t or s(t,any(t.startswith(w)and g(t[len(w):])for w in W))
print filter(g,set(''.join(chr((ord(a)-ord(w[i%len(w)]))%26+65)for i,a in enumerate(c))for w in W))

```

---
Tags: code-golf, cryptography, restricted-complexity
---


title: Make a (software) modem!

text:
# Question
Title: Make a (software) modem!
# Objective

Design a **mo**dulator/**dem**odulator pair to accurately transmit data as quickly as possible over simulated plain old telephone service (POTS).

# Steps

1. Generate some random (`/dev/random` or the like) data that will take 3-4 seconds to transmit
2. Modulate the data with your modulator to produce an audio file
3. Pass the audio file through the POTS simulator. If you don't have Python/Scipy you can upload a file with the form, or do a JSON API request.
4. Demodulate the audio file back to binary data
5. Validate that the input and output are equal-ish\* (limit 1 out of every 1000 bits can be corrupted)
6. Score is number of bits transmitted divided by the length of the audio file (bits/second)

# Rules

* Input file must be 3-4 seconds, 44.1 kHz, mono.
* Run the simulator with an SNR of 30 dB (it's default)
* The demodulator must reconstruct the transmitted data with a bit error rate of no more than 10<sup>-3</sup> (1 per thousand bits).
* No digital compression is allowed (i.e. zipping the data. It's outside the scope of the challenge.)
* No attempting to shove data into frequencies above 4 kHz. (My filters aren't perfect, but they're reasonably POTS-like with a relatively small number of taps.)
* If your modem protocol requires a short preamble (no more than 1 second) to synchronize/calibrate the receiver, it isn't penalized.
* If possible, *please host the audio file* somewhere accessible so we can listen to a cacophony of beeps and boops.

# Example

Here's an **example notebook** that demonstrates the modulation/demodulation with simple "on-off keying" (audio samples included!).

It would score 100 (bits/second). Note that it's transmitting with a much worse 5 dB SNR.

# Answer
> 7 votes
# MATLAB, 1960 bps

Here is my updated attempt:

```
fs = 44100; %44.1kHz audio rate
fc = 2450;  %2.45kHz carrier - nice fraction of fs!
fsym = fc/5; %symbol rate

tmax = 4; %about 4 seconds worth

preamblesyms = 6;

t = 1/fs:1/fs:(tmax+preamblesyms/fsym);

symbols = preamblesyms+fsym*tmax;
symbollength = length(t)/symbols;
bits = symbols*3;
bitstream = [zeros(1,preamblesyms*3),rand(1,bits-preamblesyms*3)>0.5]; %Add a little preamble of 18 bits
data = bin2dec(char(reshape(bitstream,3,symbols)'+'0'))';

greycode = [0 1 3 2 6 7 5 4];

%Encode the symbols using QAM8 - we use effectively grey code so that
%adjacent symbols in the constellation have only one bit difference
%(minimises error rate)
encoded = zeros(2,symbols);
encoded(1,data==1) = 1/sqrt(2);
encoded(1,data==3) = 1;
encoded(1,data==2) = 1/sqrt(2);
encoded(1,data==7) = -1/sqrt(2);
encoded(1,data==5) = -1;
encoded(1,data==4) = -1/sqrt(2);
encoded(2,data==0) = 1;
encoded(2,data==1) = 1/sqrt(2);
encoded(2,data==2) = -1/sqrt(2);
encoded(2,data==6) = -1;
encoded(2,data==7) = -1/sqrt(2);
encoded(2,data==4) = 1/sqrt(2);

%Modulate onto carrier
carrier = [sin(2*pi*fc*t);cos(2*pi*fc*t)];
signal = reshape(repmat(encoded(1,:)',1,symbollength)',1,[]);
signal(2,:) = reshape(repmat(encoded(2,:)',1,symbollength)',1,[]);
modulated = sum(signal.*carrier)';

%Write out an audio file
audiowrite('audio.wav',modulated,fs);

%Wait for the user to run through the POTS simulator
input('');

%Read in the filtered data
filtered=audioread('audio.pots-filtered.wav')';

%Recover the two carrier signals
preamblecos = filtered(symbollength+1:symbollength*2);
preamblesin = filtered(symbollength+1+round(symbollength*3/4):symbollength*2+round(symbollength*3/4));

%Replicated the recovered carriers for all symbols
carrierfiltered = [repmat(preamblesin,1,symbols);repmat(preamblecos,1,symbols)];

%Generate a demodulation filter (pass up to 0.66*fc, stop at 1.33*fc
%(really we just need to kill everything around 2*fc where the alias ends up)
d=fdesign.lowpass('Fp,Fst,Ap,Ast',0.05,0.1,0.5,60);
Hd = design(d,'equiripple');

%Demodulate the incoming stream
demodulated = carrierfiltered .* [filtered;filtered];
demodulated(1,:)=filtfilt(Hd.Numerator,1,demodulated(1,:));
demodulated(2,:)=filtfilt(Hd.Numerator,1,demodulated(2,:));

%Split signal up into bit periods
recovereddemodulated=[];
recovereddemodulated(1,:,:) = reshape(demodulated(1,:),symbollength,symbols);
recovereddemodulated(2,:,:) = reshape(demodulated(2,:),symbollength,symbols);

%Extract the average level for each bit period. Only look at the second
%half to account for slow rise times in the signal due to filtering
recoveredsignal=mean(recovereddemodulated(1,round(symbollength/2):symbollength,:));
recoveredsignal(2,:)=mean(recovereddemodulated(2,round(symbollength/2):symbollength,:));

%Convert the recovered signal into a complex number.
recoveredsignal=recoveredsignal(2,:) + 1j*recoveredsignal(1,:);

%Determine the magnitude and angle of the symbol. The phase is normalised
%to pi/4 as that is the angle between the symbols. Rounding this to the
%nearest integer will tell us which of the 8 phases it is closest to
recoveredphase = round(angle(recoveredsignal)/(pi/4));
recoveredphase = mod(recoveredphase+8,8)+1; %Remap to an index in the grey code vector.

%Determine the symbol in the QAM8 constellation
recoveredencoded=greycode(recoveredphase);
recoveredencoded(1:preamblesyms)=0; %Assume the preamble is correct for comparison

%Turn it back in to a bit stream
bitstreamRecovered = reshape(dec2bin(recoveredencoded)'-'0',1,[]);

%And check if they are all correct...
if(all(bitstream==bitstreamRecovered))
    disp(['Woop, ' num2str(fsym*4) 'bps']);
else
    error('Its corrupt Jim.');
end

```

Since my first attempt, I have played around a bit. There is now a small preamble at the beginning (18 bit periods, but could be shorter) which contains just a cosine wave. I extract this and replicated it to create correctly phased sine and cosine carriers for demodulation - as it is a very short preamble, I haven't counted it in the bit rate as per your instructions.

Also since the first attempt I am now using a QAM8 constellation to achieve 3 bits per symbol instead of 2. This effectively doubles the transfer rate. So with a ~2.4kHz carrier I am now achieving 1960bps.

I've also improved the symbol detection so that the averaging doesn't get affected by slow rise times caused by the filtering - basically only the second half of each bit period is averaged to remove the impact of rise times.

Still nowhere near the 40kbps theoretical channel bandwidth from the Shannon-Hartley theory (assuming the 30dB SNR)

Just for those that like *horrible* sounds, this is the new entry:

---

And in case anyone is interested, this is the previous 960bps entry

---
Tags: code-challenge, audio
---


title: Perform a Pluto flyby

text:
# Question
Title: Perform a Pluto flyby
Congratulations! You've just been hired by NASA to work on the new Horizons 2 project.

Sadly, there have been huge budget cuts recently, so the top management has decided to fake the whole planned Pluto flyby (as they did for the moon landings in the 70s).

Your task is to write a program that will accept as input a date in the format `yyyymmdd`, and will provide a fake photograph of Pluto for this date. You can assume the entered date will be in the year 2015 or 2016.

The photograph is a 15x15 grid of ASCII characters. The characters on the grid have their x- and y-coordinates within the range `[-7, 7]` \- the top-left character is at `(-7, -7)` while the bottom-right character is at `(7, 7)`.

The photograph will be computed with the following rules:

* The probe will be the nearest to Pluto on 25/12/2015
* The distance `d` to Pluto is given by this formula : `square root of ((difference in days to christmas) ^ 2 + 10)`
* The radius `r` of Pluto's image on the photo is given by : `22 / d`
* A character with coordinates `(x, y)` on the grid must be set to `#` if `x^2 + y^2 <= r^2` ; it must be set to space otherwise.
* There are stars at positions `(-3, -5)`, `(6, 2)`, `(-5, 6)`, `(2, 1)`, `(7, -2)`. Stars are represented by a dot `.`, and they are of course hidden by Pluto.

One more thing: The NASA board has come to the conclusion that the discovery of life on Pluto would likely result in a substantial budget increase. Your program should then add clues of life on Pluto:

* When the distance to Pluto is \<= 4, add a plutonian at coordinates `(-3,-1)` : `(^_^)`

*Example photograph for input `20151215`: (Your code should have all the newlines as this code does)*

```

    .

       #      .
      ###
     #####
      ###.
       #     .

  .

```

*Photograph for input `20151225`:*

```

    #######
   #########
  ###########
 #############
 #############.
 ###(^_^)#####
 #############
 #############
 #############
 #############
  ###########
   #########
  . #######

```

As a comparison, here's a photo of Pluto's satellite Hydra as taken by New Horizons. Differences are hardly noticeable with our ASCII art.

This is code golf, so the shortest code in bytes wins!

# Answer
> 3 votes
# JavaScript (ES6), 237 bytes

```
f=(n)=>(t=new Date('201'+n[3],n[4]+n[5],n[6]+n[7])/864e5-403805/24,r=484/(t*t+10),(g=(i)=>(++i<8?(h=(j)=>(i*i+j*j<=r?r>30.25&!~i&&'(^_^)'[j+3]||'#':~'p-3-5p62p-56p21p7-2'.indexOf('p'+j+i)?'.':' ')+(++j<8?h(j):''))(-7)+'\n'+g(i):''))(-8))

```

Live demo. Run in Firefox.

## Original version

```
f=function(n) {
    t = (new Date('201'+n[3],''+n[4]+n[5],''+n[6]+n[7]) // Find the time difference in milliseconds,
    - new Date(2015,12,25)) / 864e5;                    // then divide by 86400000 to convert to days.

    r=22 / Math.sqrt(t*t+10);                           // Calculate the radius.

    s=[]; // s is the array that contains each line as a string.

    for(i=-7;i<8;i++)               // Loop through rows.
        for(j=-7,s[i+7]='';j<8;j++) // Loop through columns, appending one character per column.
                                    // s is zero based, so add 7 to the row.
            s[i+7]+=i*i+j*j<=r*r ?  // Choose which character to add to s.
            (r>5.5&i==-1&&'(^_^)'[j+3]||'#') :  // Add a '#' if the position is inside the radius.
                                                // If distance < 4, then the radius > 5.5
                                                // Then add the face at the right position.
            {'-3-5':1,'62':1,'-56':1,'21':1,'7-2':1} // Add the stars if outside. Create an associative array.
            [j+''+i]?'.':' ';                        // If i concat j is in the array, the expression will be 1,
                                                     // which is truthy, else it will be undefined, which is falsey.
    return s.join`\n` // Join all the rows with a new-line.
}

```

## Golfing

This was fun to golf.

I don't need to create a Date object, so I hardcoded the value in milliseconds to save 13 bytes:

```
t=(new Date('201'+n[3],n[4]+n[5],n[6]+n[7])-new Date(2015,12,25))/864e5 // Before
t=new Date('201'+n[3],n[4]+n[5],n[6]+n[7])/864e5-403805/24 // After

```

Replace the associative array with a delimited string to eliminate 9 bytes:

```
{'-3-5':1,'62':1,'-56':1,'21':1,'7-2':1}[j+''+i]?'.':' ' // Before
~'p-3-5p62p-56p21p7-2'.indexOf('p'+j+i)?'.':' ' // After

```

The biggest refactor was replacing the for loops with nested, recursive IIFEs to knock off 10 bytes:

```
s=[];for(i=-7;i<8;i++)for(j=-7,s[i+7]='';j<8;j++)s[i+7]+= /* Chooses char at i,j */ ;return s.join`\n` // Before
(g=(i)=>(++i<8?(h=(j)=>( /* Chooses char at i,j */ )+(++j<8?h(j):''))(-7)+'\n'+g(i):''))(-8) // After

```

I also got rid of `Math.sqrt` for 8 more bytes.

```
r=22/Math.sqrt(t*t+10),(g=(i)=>(++i<8?(h=(j)=>(i*i+j*j<=r*r?r>5.5 // Before
r=484/(t*t+10),(g=(i)=>(++i<8?(h=(j)=>(i*i+j*j<=r?r>30.25 // After

```

## Issues

~~I could only get the correct photograph for the test cases by changing the closest date to 2015/12/24, and I don't know if the problem lies in my code or the question. Please clarify and I will update my answer.~~

~~Here is my output using the differences from 2015/12/25.~~

Edit: Updated answer to use Christmas as the closest date.

Photograph for "20151215":

```

        .

           #      .
          ###
         #####
          ###.
           #     .

      .

```

Photograph for "20151225":

```

        #######
       #########
      ###########
     #############
     #############.
     ###(^_^)#####
     #############
     #############
     #############
     #############
      ###########
       #########
      . #######

```

# Answer
> 3 votes
# C# 4.0, 393 bytes

```
string p(string s){int i=Convert.ToInt32(s),Y=i/10000,m,x,y;s="";i-=Y*10000;m=i/100;i-=m*100;double d=Math.Sqrt(Math.Pow((new DateTime(2015,12,25)-new DateTime(Y,m,i)).Days,2)+10);string o,k=".-3-5.62.-56.21.7-2";for(y=-7;y<8;y++){for(x=-7;x<8;x++){o="#";if(d<=4&&x==-3&&y==-1){o="(^_^)";x+=4;}s+=Math.Pow(x,2)+Math.Pow(y,2)<=Math.Pow(22/d,2)?o:k.Contains("."+x+y)?".":" ";}s+="\n";}return s;}

```

## Example:

```
string userInput = Console.ReadLine();
Console.WriteLine(p(userInput));

```

## Output:

```
20151216

    .

      ###     .
     #####
     #####
     #####
      ###    .

  .

20151224

     #####
   #########
  ###########
  ###########
 #############.
 ###(^_^)#####
 #############
 #############
 #############
  ###########
  ###########
   #########
  .  #####

```

# Answer
> 2 votes
## CJam, 165 bytes

```
q'-%:i~\0\({X1=29W$2%-X7<X+2%30+?+}fX+\2%-359 6?+:DD*A+mq:Z22Z/_*:R-7:Y];F{-7:X;F{XX*YY*+R>XYF*+[-78II+85H-23]#)'.S?Z4<Y-1=X-4>X2<&&&X-3="(^_^)"L?'#??X):X;}*NY):Y;}*

```

The first part computes the day difference and stores it in the `D` variable. The rest is a double loop that iterates through `X` and `Y`.

Test it here

---
Tags: code-golf, ascii-art, date
---


title: Fill the Screen with Wang Tiles

text:
# Question
Title: Fill the Screen with Wang Tiles
It has been proven that the following 13 square Wang tiles always tile the plane aperiodically. This means that when the squares are arranged in a grid with all neighboring sides the same color, a translation of the pattern will never match up with itself.

We'll represent each tile textually by a 3×3 grid filled with spaces at the center and corners, and the numbers 1 through 5 instead of the colors red, green, blue, yellow, grey, at the edges:

```
 2      2      2      1      1      1      4      3      2      2      4      3      2
1 2    1 3    2 3    2 1    3 1    3 2    4 4    4 4    4 5    4 5    5 5    5 5    5 4
 3      2      3      2      3      2      1      2      1      4      1      2      2

```

# Goal

Your task is to write a program that takes in a width and height and outputs a valid Wang tile grid with those dimensions. A valid tiling is one in which all the adjacent tile edges have the same color (or number). The smallest program in bytes wins.

Your input should come from stdin or command line arguments and output should go to stdout. The exact input format can be anything reasonably obvious, like `>>> wangtiler 3 2`. The width and height are always positive integers.

### Example (width = 3, height = 2)

Notice that when we layout the textual tiles the neighboring edges form necessary redundant pairs of digits:

```
 1  2  1
2 11 22 1
 2  3  2
 2  3  2
4 55 55 4
 1  2  2

```

<sup>(This is NOT the proper output format.)</sup>

We can compress these horizontally and vertically to get:

```
 1 2 1
2 1 2 1
 2 3 2
4 5 5 4
 1 2 2

```

This compressed format is the proper output format you must use. The odd numbered lines must include their trailing space.

# Graphical Bonus

Instead of having any textual output, your program may output an image of the tiled grid. The graphical tiles must be made up of four 45-45-90 triangles arranged in a square and use five easily distinguishable colors like the tiles above. The black borders are not required. The graphical tiles must be at least 32×32 pixels in size. No "compression" is applied to them.

**Example bonus image:** (same grid as example above)

The bonus is worth minus 150 bytes.

# Notes

* You must use this set of 13 tiles.
* Tiles may not be rotated.
* Tiles may appear any number of times (including none at all).
* You may assume a valid tiling with any dimensions is possible.

# Answer
> 12 votes
### GolfScript, 200 characters

```
~\:W*):R;1,{)\:C"=QCy_~{MTKAis]?OyJE?~WvM"[64 2400]{base}/@{>}+,{:T;[C,W<!{C W~)=T 64/^8/8%}*C,W%0>{C-1=64/T^8%}*]0-!},1<.!!{1,+}*+.,R<}do);W/.0={' '\512/8%`}%n@{.[.0=8%\{' '\64/8%}/n]\{' '\8/8%`}%n}/

```

ASCII version with no graphic output. Give the input on STDIN - try here. The code uses a plain backtracking approach and fills the space line by line.

Examples:

```
> 3 2
 1 2 1
2 1 2 1
 2 3 2
5 4 4 5
 2 2 1

> 8 5
 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2
 2 3 2 3 2 3 2 3
5 4 4 5 5 4 4 5 5
 2 2 4 2 2 2 4 2
5 4 5 5 4 5 4 4 5
 2 1 1 2 1 2 1 1
1 3 2 1 2 1 3 2 1
 2 2 2 3 2 2 2 2
5 4 5 4 4 5 4 5 4
 2 1 2 2 1 2 1 2

```

### Graphical Bonus, score 122, 272 characters - 150 bonus

```
~\:W*):R;1,{)\:C"=QCy_~{MTKAis]?OyJE?~WvM"[64 2400]{base}/@{>}+,{:T;[C,W<!{C W~)=T 64/^8/8%}*C,W%0>{C-1=64/T^8%}*]0-!},1<.!!{1,+}*+.,R<}do);W["P3\n"32W*" "3$,32*n 1n]\{{:^;512:X;16,{[^8%]1$*[^X/8%]31*@.+>[^64/8%]31*++32<}:F%8:X;16,-1%{F}%+}%zip{{+}*{8+2base(;~}%' '*n}/}/

```

Same basic code with a different output formatter. The output is an image in PPM format (i.e. simply redirect the output to a file `image.ppm`). The colors are slightly different than the tiles in the question, but clearly distinguishable (1-\>blue, 2-\>green, 3-\>cyan, 4-\>red, 5-\>magenta).

16x12 example:

# Answer
> 17 votes
## Python (565 - 150 = 415)

Btw... it seems that we can't naively just decide the next tile by the its left and top tile. There's some combination of tiles that will fit each other.
This solution fills in left-\>right, top-\>down brute forces through all possible combinations and backtracks if a tile cannot fit in.

For more info about the 13 tile proof: An aperiodic set of 13 Wang tiles

Width and Height are specified by `W` and `H`

Red, Green, Blue, Yellow and Noir specified by `R`, `G`, `B`, `Y` and `N`

```
import Image,sys
W,H=map(int,sys.argv[1:])
R=99
G=R<<8
B=G<<8
Y=G+R
N=0
s="RGB";u=32;g=[[0,0]]*W*H;k=f=0
def t(c):i=Image.new(s,(2,2));k=i.load();q=16;k[1,0],k[1,1],k[0,1],k[0,0]=c;return i.resize([64]*2).rotate(45).crop((q,q,q+u,q+u))
while k<H*W:
 z=g[k][1];v=-1;j=k/W;i=k%W
 while z<13:
    l=map(eval,"GGGRRRYBGGYBGGBBRRGYYNNNNYBGBGBGRGRYRGGRRGGBBYYYYNNN"[z::13])
    if(j<1or g[(j-1)*W+i][0][2]==l[0])and(i<1or g[j*W+i-1][0][1]==l[3]):g[k]=[l,z+1];v=1;z=99
    z+=1
 g[k][1]*=(v>0);k+=v
m=Image.new(s,(W*u,H*u))
for e in g:m.paste(t(e[0]),(f%W*u,(f/W)*u));f+=1
m.show()

```

Output. Not the actual color scheme... cuz too glaring. This might make some interesting interior decor patterns...:

# Answer
> 3 votes
# Haskell, 208 bytes

```
p x|x<2/3=(3!x)3"3212"3
p x=(0.5!x)1"45423"2
f=floor
(k!x)l s m=do{i<-[0,x..];[' ',s!!(2+f(i+x)-f i)]}:do{i<-[0,l*x..];s!!mod(f i)m:" "}:p(k*x)
t n=take$2*n+1
main=do(w,h)<-readLn;putStr.unlines.t h$t w<$>p 1

```

No searching, just math. Example run: given `(8,5)` on stdin, outputs

```
 2 2 2 2 2 2 2 2
4 5 4 5 4 5 4 5 4
 1 2 1 2 1 2 1 2
3 2 3 2 3 2 3 2 3
 2 3 2 3 2 3 2 3
4 5 5 4 4 5 5 4 4
 4 2 2 2 4 2 2 2
4 4 5 4 5 5 4 5 4
 1 1 2 1 1 2 1 2
3 2 1 3 2 1 3 2 3
 2 2 2 2 2 2 2 3

```

Run online at Ideone

---
Tags: code-golf, graphical-output, kolmogorov-complexity, geometry, tiling
---


# Question
Title: Tiling a 2^N by 2^N Grid with L-Shaped Trominoes
When students are first taught about the proof technique of mathematical induction, a common example is the problem of tiling a 2N×2N grid with L-shaped trominoes, leaving one predetermined grid space empty. (N is some nonnegative integer.)

I will leave it to you to go over the proof if you do not already know it. There are many resources that discuss it.

Your task here is to write a program that takes in a value for N, as well as the coordinates of the grid space to leave empty, and prints an ASCII representation of the resulting tromino tiled grid.

The character `O` will fill the empty space, and the 4 rotations of our tromino will look like this:

```
|
+-

 |
-+

-+
 |

+-
|

```

(Yes, it can be ambiguous which `+` goes with which `-` and `|` for certain arrangements, but that's ok.)

Your program must work for N = 0 (for a 1×1 grid) up to at least N = 8 (for a 256×256 grid). It will be given x and y values that are the coordinates for the `O`:

* x is the horizontal axis. x = 1 is the left grid edge, x = 2N is the right grid edge.
* y is the vertical axis. y = 1 is the top grid edge, y = 2N is the bottom grid edge.

Both x and y are always in the range \[1, 2N\].

So for a given N, x, and y, your program must print a 2N×2N grid, tiled completely with L-shaped trominoes, except for the x, y grid coordinate which will be an `O`.

## Examples

If N = 0, then x and y must both be 1. The output is simply

```
O

```

If N = 1, x = 1, and y = 2, the output would be

```
-+
O|

```

N = 2, x = 3, y = 2:

```
+--+
||O|
|+-|
+--+

```

N = 2, x = 4, y = 1:

```
+-|O
||+-
|+-|
+--+

```

N = 3, x = 3, y = 6 (e.g. the image on this page):

```
+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
||O|-+||
|+-||-+|
+--++--+

```

## Details

* You may write a function that takes the 3 integers instead of writing an entire program. It should print or return the grid string.
* Take input from stdin, command line, (or function args if you write function).
* The output may optionally contain a single training newline.
* You are not *required* to use the tiling method that the proof normally suggests. It only matters that the grid is filled with L-shaped trominoes besides the `O`. (Trominoes may not be cut or go out of the grid bounds.)

**The shortest code in bytes wins. Tiebreaker is earlier post.** (Handy byte counter.)

# Answer
> 2 votes
# Haskell, 250 240 236 bytes

```
c=cycle
z o(#)(x,y)=zipWith o(1#x)(2#y)
f n x y=unlines$(z(+)(\m w->[c[0,m]!!div(w-1)(2^(n-k))|k<-[1..n]])(x,y),"O")%n
(_,x)%0=[x]
((p:o),x)%k=z(++)(\_ q->((o,x):c[(c[3-q],[" |-+| +--+ |+-|"!!(4*p+q)])])!!abs(p-q)%(k-1))=<<[(0,1),(2,3)]

```

This follows the inductive solution to the problem closely. The point to mark is represented by a sequence of numbers from 0 to 3 which indicate which quadrant holds the point at each zoom level; this is initially calculated by the expression starting with z(+). The operator (%) combines pictures for the four quadrants into a single picture. Pictures for the unmarked quadrants are generated by drawing marked quadrants with the mark somewhere near the middle, drawn with a mark of "+-|" as appropriate to build the central L tile.

Funny business: For golf reasons, the subexpression

```
\m w->[c[0,m]!!div(w-1)(2^(n-k))|k<-[1..n]]

```

(which more or less computes the bit sequence for a number) is hilariously inefficient --- it determines if w / 2^p is odd or even by looking up the (w / 2^p)th element of a list.

*Edit:* Saved 10 bytes by inlining the bit calculation and replacing an if/then/else with an indexing operation.

*Edit2:* Saved four more bytes by switching a function back to an operator. @randomra, the race is on!

Demo:

```
λ> putStr $ f 4 5 6
+--++--++--++--+
|+-||-+||+-||-+|
||+--+||||+--+||
+-|+-|-++-|-+|-+
+-||-+-++--+||-+
||+-O||||-+|-+||
|+-||-+|-+|||-+|
+--++--+||-++--+
+--++-|-+|-++--+
|+-|||+--+|||-+|
||+-|+-||-+|-+||
+-||+--++--+||-+
+-|+-|-++-|-+|-+
||+--+||||+--+||
|+-||-+||+-||-+|
+--++--++--++--+

```

# Answer
> 8 votes
# C, 399 bytes

```
char*T=" |-+ | +-| ",*B;w;f(N,x,y,m,n,F,h,k,i,j){w=B?F=0,w:1<<N|1;char b[N?w*w:6];for(k=w;k--;)b[k*w-1]=10;B=!B?F=1,m=0,n=0,x--,y--,b:B;if(N>1){h=1<<N-1;i=x>--h,j=y>h;while(++k<4)if(k%2-i||k/2-j)f(N-1,!(k%2)*h,!(k/2)*h,m+k%2*(h+1),n+k/2*(h+1));f(1,h&i,h&j,m+h,n+h);h++;f(N-1,x-h*i,y-h*j,m+h*i,n+h*j);}else while(++k<4)B[w*(n+k/2)+m+k%2]=T[5*x+2*y+k];if(F)B[y*w+x]=79,B[w*w-w-1]=0,puts(N?B:"O"),B=0;}

```

No one's come forward with anything yet, so I'll offer up a meager solution. Mark my words, this is not the end. This will get shorter.

We define a function `f` that takes 10 arguments, but you need only call it with `f(N, X, Y)`. Output goes to stdout.

Here's a readable version:

```
char*T=" |-+ | +-| ",*B;
w;
f(N,x,y,m,n,F,h,k,i,j){
    w=B?F=0,w:1<<N|1;
    char b[N?w*w:6];
    for(k=w;k--;)
        b[k*w-1]=10;
    B=!B?F=1,m=0,n=0,x--,y--,b:B;
    if(N>1){
        h=1<<N-1;
        i=x>--h,j=y>h;
        while(++k<4)
            if(k%2-i||k/2-j)
                f(N-1,!(k%2)*h,!(k/2)*h,m+k%2*(h+1),n+k/2*(h+1));
        f(1,h&i,h&j,m+h,n+h);
        h++;
        f(N-1,x-h*i,y-h*j,m+h*i,n+h*j);
    }
    else
        while(++k<4)
            B[w*(n+k/2)+m+k%2]=T[5*x+2*y+k];
    if(F)B[y*w+x]=79,B[w*w-w-1]=0,puts(N?B:"O"),B=0;
}

```

A taste of output for `f(3, 2, 7)`:

```
+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
|-+|-+||
|O|||-+|
+--++--+

```

It's a fairly simple recursive algorithm to fill the grid. I may upload an animation of the algorithm drawing trominoes since I think it's pretty neat. As usual, feel free to ask questions and shout at me if my code breaks!

Try it online!

# Answer
> 8 votes
# Python 3, ~~276~~ ~~265~~ 237 bytes

My first Python golf so I'm sure there is a lot of room for improvement.

```
def f(n,x,y,c='O'):
 if n<1:return c
 *t,l,a='x|-+-|',2**~-n;p=(a<x)+(a<y)*2
 for i in 0,1,2,3:t+=(p-i and f(n-1,1+~i%2*~-a,1+~-a*(1-i//2),l[p+i])or f(n-1,1+~-x%a,1+~-y%a,c)).split(),
 u,v,w,z=t;return'\n'.join(map(''.join,zip(u+w,v+z)))

```

10 bytes saved thanks to @xnor and 6 more bytes thanks to @Sp3000.

The function returns a string. Example usage:

```
>>>print(f(3,3,6))
+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
||O|-+||
|+-||-+|
+--++--+

```

# Answer
> 4 votes
# JavaScript (ES6) 317 ~~414~~

A lot of work to golf, but still quite long.

```
T=(b,x,y)=>
  (F=(d,x,y,f,t=[],q=y<=(d>>=1)|0,
      b=d?x>d
       ?q
         ?F(d,x-d,y,0,F(d,1,1,2))
         :F(d,1,d,2,F(d,x-d,y-d))
       :F(d,1,d,1-q,F(d,1,1,q)):0,
      r=d?(x>d
         ?F(d,d,d,1-q,F(d,d,1,q))
         :q
           ?F(d,x,y,1,F(d,d,1,2))
           :F(d,d,d,2,F(d,x,y-d))
      ).map((x,i)=>x.concat(b[i])):[[]]
    )=>(r[y-1][x-1]='|+-O'[f],r.concat(t))
  )(1<<b,x,y,3).join('\n').replace(/,/g,'')

```

Run snippet to test (better looking using Unicode block characters - but even a bit longer)

```
T=(b,x,y)=>
  (F=(d,x,y,f,t=[],q=y<=(d>>=1)|0,
      b=d?x>d
       ?q
         ?F(d,x-d,y,0,F(d,1,1,6))
         :F(d,1,d,6,F(d,x-d,y-d))
       :F(d,1,d,q,F(d,1,1,q+1)):0,
      r=d?(x>d
         ?F(d,d,d,q+3,F(d,d,1,q+4))
         :q
           ?F(d,x,y,1,F(d,d,1,6))
           :F(d,d,d,6,F(d,x,y-d))
      ).map((x,i)=>x.concat(b[i])):[[]]
    )=>(
    r[y-1][x-1]='┐│┘┌│└─O'[f],r.concat(t)
  ))(1<<b,x,y,7).join('\n').replace(/,/g,'')

loop=_=>{
  var x=X.value|0, y=Y.value|0, n=N.value|0;

  var b=1<<n, cur=1<<(n+n);
  (L=_=>{
    --cur;
    O.innerHTML=T(n,(cur&(b-1))+1,(cur>>n)+1);
    cur&&setTimeout(L,100);
  })()
}

tile=_=>{
  var x=X.value|0, y=Y.value|0, n=N.value|0;
  O.innerHTML=T(n,x,y);
}

tile()
```

```
input { width: 3em }
pre { font-size: 10px; line-height: 10px }
```

```
N: <input id=N value=4> X: <input id=X value=5> Y: <input id=Y value=3>
<button onclick="tile()">Tile</button>
<button onclick="loop()">Loop</button>
<pre id=O></pre>
```

# Answer
> 1 votes
# IDL 8.3+, 293 bytes

This is too long, I'm trying to cut it down but I haven't gotten there yet.

```
function t,n,x,y
m=2^n
c=['|','+','-']
b=replicate('0',m,m)
if m eq 1 then return,b
h=m/2
g=h-1
k=[1:h]
o=x gt h
p=y gt h
q=o+2*p
if m gt 2then for i=0,1 do for j=0,1 do b[i*h:i*h+g,j*h:j*h+g]=t(n-1,i+2*j eq q?x-i*h:k[i-1],i+2*j eq q?y-j*h:k[j-1])
b[g+[1-o,1-o,o],g+[p,1-p,1-p]]=c
return,b
end

```

Outputs:

```
IDL> print,t(1,1,2)
- +
0 |
IDL> print,t(2,3,2)
+ - - +
| | 0 |
| + - |
+ - - +
IDL> print,t(2,4,1)
+ - | 0
| | + -
| + - |
+ - - +
IDL> print,t(3,3,6)
+ - - + + - - +
| + - | | - + |
| | + - - + | |
+ - | - + | - +
+ - - + | | - +
| | 0 | - + | |
| + - | | - + |
+ - - + + - - +

```

And, uh... just for fun...

```
IDL> print,t(6,8,9)
+ - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - +
| + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + |
| | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | |
+ - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - +
+ - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - +
| | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | |
| + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + |
+ - - + + - | - + | - + + - - + + - - + + - | - + | - + + - - + + - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - +
+ - - + + - | 0 | | - + + - - + + - - + + - - + | | - + + - - + + - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - +
| + - | | | + - - + | | | - + | | + - | | - + | - + | | | - + | | + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + |
| | + - | + - | | - + | - + | | | | + - - + | | | - + | - + | | | | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | |
+ - | | + - - + + - - + | | - + + - | - + | - + + - - + | | - + + - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - +
+ - | + - | - + + - | - + | - + + - - + | | - + + - | - + | - + + - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - +
| | + - - + | | | | + - - + | | | - + | - + | | | | + - - + | | | | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | |
| + - | | - + | | + - | | - + | - + | | | - + | | + - | | - + | | + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + |
+ - - + + - - + + - - + + - - + | | - + + - - + + - - + + - - + + - - + + - - + + - - + + - | - + | - + + - - + + - - + + - - +
+ - - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - - +
| + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + | | + - | | - + | | + - | | - + | - + | | | - + | | + - | | - + |
| | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | | | | + - - + | | | | + - - + | | | - + | - + | | | | + - - + | |
+ - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - + + - | + - | - + + - | - + | - + + - - + | | - + + - | - + | - +
+ - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - + + - | | + - - + + - - + | | - + + - | - + | - + + - - + | | - +
| | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | | | | + - | + - | | - + | - + | | | | + - - + | | | - + | - + | |
| + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + | | + - | | | + - - + | | | - + | | + - | | - + | - + | | | - + |
+ - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + | | - + + - - +
+ - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + | | - + + - - + + - - + + - | - + | - + + - - +
| + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | - + | - + | | | - + | | + - | | | + - - + | | | - + |
| | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - - + | | | - + | - + | | | | + - | + - | | - + | - + | |
+ - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | - + | - + + - - + | | - + + - | | + - - + + - - + | | - +
+ - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - - + | | - + + - | - + | - + + - | + - | - + + - | - + | - +
| | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | - + | - + | | | | + - - + | | | | + - - + | | | | + - - + | |
| + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | - + | | | - + | | + - | | - + | | + - | | - + | | + - | | - + |
+ - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - - + + - - + + - - + + - - + + - - +
+ - - + + - - + + - - + + - - + + - - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + + - - + + - - + + - - + + - - +
| + - | | - + | | + - | | - + | | + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + | | + - | | - + | | + - | | - + |
| | + - - + | | | | + - - + | | | | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | | | | + - - + | | | | + - - + | |
+ - | + - | - + + - | - + | - + + - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - + + - | + - | - + + - | - + | - +
+ - | | + - - + + - - + | | - + + - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - + + - | | + - - + + - - + | | - +
| | + - | + - | | - + | - + | | | | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | | | | + - | + - | | - + | - + | |
| + - | | | + - - + | | | - + | | + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + | | + - | | | + - - + | | | - + |
+ - - + + - | + - | - + + - - + + - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - | - + | - + + - - +
+ - - + + - | | + - - + + - - + + - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + | | - + + - - +
| + - | | | + - | + - | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | - + | - + | | | - + |
| | + - | + - | | | + - - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - - + | | | - + | - + | |
+ - | | + - - + + - | + - | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | - + | - + + - - + | | - +
+ - | + - | - + + - | | + - - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - - + | | - + + - | - + | - +
| | + - - + | | | | + - | + - | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | - + | - + | | | | + - - + | |
| + - | | - + | | + - | | | + - | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | - + | | | - + | | + - | | - + |
+ - - + + - - + + - - + + - | | + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - - +
+ - - + + - - + + - - + + - | + - | - + + - - + + - - + + - - + + - - + + - - + + - - + + - | - + | - + + - - + + - - + + - - +
| + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + | | + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + |
| | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | | | | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | |
+ - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - + + - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - +
+ - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - + + - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - +
| | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | | | | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | |
| + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + | | + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + |
+ - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - +
+ - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - + + - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - +
| + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + |
| | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | |
+ - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - +
+ - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - +
| | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | |
| + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + |
+ - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - +

```

# Answer
> 0 votes
# Ruby Rev 1, 288

As an anonymous lambda literal. Shown in test program (the lambda literal is `->(n,a,b){...}` )

```
g=
->(n,a,b){
$x=a-1
$y=b-1
$a=Array.new(m=2**n){"|"*m}
def t(u,v,m,r,f)
(m/=2)==1?$a[v+1-r/2%2][u,2]='-+-'[r%2,2]:0
if m>1
4.times{|i|i==r ?t(u+m/2,v+m/2,m,r,0):t(u+i%2*m,v+i/2*m,m,3-i,0)}
f>0?t(u+r%2*m,v+r/2*m,m,2*$x/m&1|$y*4/m&2,1):0
end
end
t(0,0,m,2*$x/m|$y*4/m,1)
$a[$y][$x]='O'
$a
}

n=gets.to_i
a=gets.to_i
b=gets.to_i
puts(g.call(n,a,b))

```

# Ruby Rev 0, 330 ungolfed

Currently the only golfing I'm claiming is elimination of comments, unnecessary newlines and indents.

This is my first proper algorithm encoded in Ruby and it's been hard work. I'm sure there's at least 50 characters than can be eliminated, but I've done enough for now. There are some real horrors, for example the input. That can probably be fixed by a function or lambda instead of a program, but the inner function `t` that draws the trominoes still needs access to the global variables. I'll have to figure out the syntax for that.

A feature of my answer which is not present in the others, is that I initialize an array of strings with `|` characters. That means I only have to draw the `+-` or `-+`, which are next to each other on the same line.

```
m=2**gets.to_i                                         #get n and store 2**n in m
$x=gets.to_i-1                                         #get x and y, and...
$y=gets.to_i-1                                         #convert from 1-indexed to 0-indexed
$a=Array.new(m){"|"*m}                                 #array of m strings length m, initialized with "|"

def t(u,v,m,r,f)                                       #u,v=top left of current field. r=0..3= quadrant containing O. f=flag to continue surrounding O
  m/=2
  if m==1 then $a[v+1-r/2%2][u,2] ='-+-'[r%2,2];end    #if we are at char level, insert -+ or +- (array already initialized with |'s)
  if m>1 then                                          #at higher level, 4 recursive calls to draw trominoes of next size down
    4.times{|i| i==r ? t(u+m/2,v+m/2,m,r,0):t(u+i%2*m,v+i/2*m,m,3-i,0)}
    f>0?t(u+r%2*m,v+r/2*m,m,2*$x/m&1|$y*4/m&2,1):0     #then one more call to fill in the empty quadrant (this time f=1)
  end
end

$a[$y][$x]='O'                                         #fill in O
t(0,0,m,2*$x/m&1|$y*4/m&2,1)                           #start call. 2*x/m gives 0/1 for left/right quadrant, similarly 4*y/m gives 0/2 for top/bottom

puts $a                                                #dump array to stdout, elements separated by newlines.

```

# Answer
> 0 votes
# Haskell, 170 bytes

```
r=reverse
g n s x y|n<1=[s]|x>k=r<$>g n s(2^n+1-x)y|y>k=r$g n s x$2^n+1-y|0<1=zipWith(++)(h s x y++h"-"k 1)$h"|"1 k++h"+"1 1 where m=n-1;k=2^m;h=g m
f n x=unlines.g n"O"x

```

Run online at Ideone

Example run:

```
*Main> putStr(f 3 3 6)
+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
||O|-+||
|+-||-+|
+--++--+

```

---
Tags: code-golf, ascii-art, geometry, grid, tiling
---