# Question
Title: Solve the Global Debt, the Code Golf way
The leaders of the world have met and have finally admitted that the best (and only) way of resolving global economic woes is to take stock of how much they owe each other and just pay each other off with huge cheques. They have hired you (ironically, at the lowest contract rate possible) to work out the best means of doing so.

After much deliberation, and asking someone to draw a simple example they've come up with the following spec.

Each country is represented by their ISO 3166-1 alpha-2 code: `US` for the USA, `AU` for Australia, `JP` for Japan, `CN` for China and so on...

1. A ledger is drawn up as a series of country entries and the amounts owing to each country.
2. Each country's entry starts off with their domain ID a colon, and how much they have in surplus/deficit (in billions of Euro), followed by a semicolon, then a coloned comma-separated list of the countries and how much (in billions of Euro) they owe.
3. If a country owes nothing to another country, no mention of that country is entered after that semicolon separator.
4. Deficits are indicated as negative numbers, surplus is indicated as a positive number.
5. Values can also be floats.
6. The ledger must be taken from STDIN. The end of the ledger is indicated by a carriage return on a blank line. The tally must be delivered to STDOUT.

An example of a ledger:

```
Input:
AU:8;US:10,CN:15,JP:3
US:14;AU:12,CN:27,JP:14
CN:12;AU:8,US:17,JP:4
JP:10;AU:6,US:7,CN:10

```

The system then works out how much each country owes and is owed and determines their surplus/deficit, for example, for AU:

AU = 8 (current surplus) -10 (to US) -15 (to CN) -3 (to JP) +12 (from US) +8 (from CN) +6 (from JP) = 6

When all the computing is done, a tally must be shown:

```
Output:
AU:6
US:-5
CN:35
JP:8

```

Your job is to create this system, capable of taking any number of ledger entries for any number of countries and capable of determining how much each country has in deficit/surplus when everything is paid out.

The ultimate test is for you to use your code to resolve the debt owed between the following countries in the test case below. These figures were taken from BBC News as of June 2011. (http://www.bbc.com/news/business-15748696)

For the purposes of the exercise, I have used their respective GDP as their current surplus... Please bear in mind that this is strictly an exercise in code quality assurance... there will be no talk of global economic resolution here in this question... If you want to talk economics I'm sure there's another subdomain in SE that handles it...

```
US:10800;FR:440.2,ES:170.5,JP:835.2,DE:414.5,UK:834.5
FR:1800;IT:37.6,JP:79.8,DE:123.5,UK:227,US:202.1
ES:700;PT:19.7,IT:22.3,JP:20,DE:131.7,UK:74.9,US:49.6,FR:112
PT:200;IT:2.9,DE:26.6,UK:18.9,US:3.9,FR:19.1,ES:65.7
IT:1200;JP:32.8,DE:120,UK:54.7,US:34.8,FR:309,ES:29.5
IE:200;JP:15.4,DE:82,UK:104.5,US:39.8,FR:23.8
GR:200;DE:15.9,UK:9.4,US:6.2,FR:41.4,PT:7.5,IT:2.8
JP:4100;DE:42.5,UK:101.8,US:244.8,FR:107.7
DE:2400;UK:141.1,US:174.4,FR:205.8,IT:202.7,JP:108.3
UK:1700;US:578.6,FR:209.9,ES:316.6,IE:113.5,JP:122.7,DE:379.3

```

Now, be the economic savior of the world!

Rules:

1. Shortest code wins... this is code-golf after all...
2. Please provide your output of the major test case with your code answer...

# Answer
> 11 votes
# K, 66

```
{(((!)."SF"$+":"\:'*+a)-+/'d)+/d:"F"$(!).'"S:,"0:/:last'a:";"\:'x}

```

.

```
k)input:0:`:ledg.txt
k){(((!)."SF"$+":"\:'*+a)-+/'d)+/d:"F"$(!).'"S:,"0:/:last'a:";"\:'x} input
US| 9439.3
FR| 2598.9
ES| 852.1
PT| 90.1
IT| 887.5
IE| 48
GR| 116.8
JP| 4817.4
DE| 2903.7
UK| 1546.2

```

# Answer
> 10 votes
# Perl, 139 137 134 119 112

Here's another working piece of code... I will document it later.

**Golfed code**

With dictionary (112):

```
for(<>){~/:(.+);/g;$d{$c=$`}+=$1;$l=$';$d{$1}+=$2,$d{$c}-=$2while$l=~/(..):([^,]+)/g}print"$_:$d{$_}
"for keys%d

```

Without dictionary (137):

```
for($T=$t.=$_ for<>;$t=~/(..:)(.+);(.+)/g;print"$c$s\n"){$c=$1;$l=$3;$s=$2;$s-=$&while$l=~/[\d.]+/g;$s+=$1while$T=~/$c([\d.]+)(?!;|\d)/g}

```

**Output**

```
US:9439.3
FR:2598.9
ES:852.1
PT:90.1
IT:887.5
IE:48
GR:116.8
JP:4817.4
DE:2903.7
UK:1546.2

```

**See it in action!**

http://ideone.com/4iwyEP

# Answer
> 4 votes
# Python, 211 185 183

```
import sys,re;t,R,F=sys.stdin.read(),re.findall,float;S=lambda e,s:sum(map(F,R(e,s)))
for m in R('(..:)(.+);(.+)',t):print m[0]+`F(m[1])+S(m[0]+'([\d.]+)(?!;|\d)',t)-S('[\d.]+',m[2])`

```

Output with major test case:

```
US:9439.300000000001
FR:2598.9
ES:852.0999999999999
PT:90.09999999999997
IT:887.5
IE:48.0
GR:116.8
JP:4817.4
DE:2903.7
UK:1546.2000000000003

```

(test it here: http://ideone.com/CjWG7v)

# Answer
> 4 votes
# C - ~~257~~ 253 if no CR at end of line

Depends on sizeof(short)==2.

No check for buffer overflow.

```
#define C(c) x[*(short*)c]
main(i){double x[23131]={0},d;char*q,b[99],*(*s)()=strtok;for(;gets(b);)for(s(b,":"),C(b)+=atof(s(0,";"));q=s(0,":");C(b)-=d=(atof(s(0,","))),C(q)+=d);for(i=b[2]=0;i<23131;memcpy(b,&i,2),x[i]?printf("%s:%f\n",b,x[i++]):++i);}

```

## Output:

```
DE:2903.700000
IE:48.000000
UK:1546.200000
JP:4817.400000
FR:2598.900000
GR:116.800000
ES:852.100000
US:9439.300000
IT:887.500000
PT:90.100000

```

## Less golfed:

```
#define C(c) x[*(short*)c]

main(i)
{
    double x[23131]={0}, d;
    char *q, b[99], *(*s)()=strtok;
    for(;gets(b);)
        for(s(b, ":"),C(b)+=atof(s(0, ";"));
            q=s(0, ":");
            C(b)-=d=(atof(s(0, ","))), C(q)+=d) ;

    for(i=b[2]=0;
        i<23131;
        memcpy(b, &i, 2), x[i]?printf("%s:%f\n", b, x[i++]):++i) ;
}

```

# Answer
> 3 votes
## PHP - ~~338~~, 280

Should work with any version of PHP 5.

**Golfed**:

```
while(preg_match("#(..):(.+);(.*)#",fgets(STDIN),$m)){$l[$m[1]][0]=(float)$m[2];foreach(explode(",",$m[3])as$x){$_=explode(":",$x);$l[$m[1]][1][$_[0]]=(float)$_[1];}}foreach($l as$c=>$d)foreach($d[1]as$_=>$o){$l[$_][0]+=$o;$l[$c][0]-=$o;}foreach($l as$c=>$d)echo$c,":",$d[0],"\n";

```

**Un-golfed**:

```
<?php

while( preg_match( "#(..):(\d+);(.*)#", fgets( STDIN ), $m ) )
{
    $l[$m[1]][0] = (float)$m[2];

    foreach( explode( ",", $m[3] ) as $x )
    {
        $_ = explode( ":", $x );
        $l[$m[1]][1][$_[0]] = (float)$_[1];
    }
}

foreach( $l as $c => $d )
    foreach( $d[1] as $_ => $o )
    {
        $l[$_][0] += $o;
        $l[$c][0] -= $o;
    }

foreach( $l as $c => $d )
    echo $c, ":", $d[0], "\n";

```

**Output**:

```
US:9439.3
FR:2598.9
ES:852.1
PT:90.1
IT:887.5
IE:48
GR:116.8
JP:4817.4
DE:2903.7
UK:1546.2

```

# Answer
> 3 votes
## perl (184 characters)

**Code**

```
%c,%d,%e=();while(<>){$_=~/(..):(.+);(.*)/;$n=$1;$c{$1}=$2;for $i(split /,/,$3){$i=~/(..):(.+)/;$d{$1}+=$2;$e{$n}+=$2;}}for $i(keys %c){$c{$i}+=$d{$i}-$e{$i};print $i.":".$c{$i}."\n";}

```

**Output**

```
UK:1546.2
DE:2903.7
IT:887.5
FR:2598.9
PT:90.1
US:9439.3
JP:4817.4
ES:852.1
IE:48
GR:116.8

```

# Answer
> 3 votes
# Perl - ~~116~~ ~~114~~ 112

```
for(<>){($n,$m,@l)=split/[:;,]/;$h{$n}+=$m;$h{$n}-=$p,$h{$o}+=$p while($o,$p,@l)=@l}print"$_:$h{$_}\n"for keys%h

```

## Output:

```
GR:116.8
UK:1546.2
DE:2903.7
IE:48
IT:887.5
US:9439.3
PT:90.1
ES:852.1
FR:2598.9
JP:4817.4

```

## Ungolfed:

```
for(<>) {
    ($n, $m, @l)=split(/[:;,]/);
    $h{$n}+=$m;

    $h{$n}-=$p, $h{$o}+=$p while ($o,$p,@l)=@l
}
print "$_:$h{$_}\n" for keys%h

```

# Answer
> 3 votes
## AWK - 138 120

```
{l=split($0,h,"[:,;]");t[h[1]]+=h[2];for(i=3;i<l;i+=2){t[h[1]]-=h[i+1];t[h[i]]+=h[i+1]}}END{for(v in t){print v":"t[v]}}

```

And the results

```
$ cat data.withoutInputHeadline |awk -f codegolf.awk
IT:887.5
UK:1546.2
DE:2903.7
PT:90.1
ES:852.1
FR:2598.9
GR:116.8
Input:0
JP:4817.4
IE:48
US:9439.3

```

## Ungolfed

```
{
    l=split($0,h,"[:,;]");
    t[h[1]]+=h[2];
    for(i=3;i<l;i+=2){
        t[h[1]]-=h[i+1]
        t[h[i]]+=h[i+1]
    }
}
END{
    for(v in t){
        print v":"t[v]
    }
}

```

(test it here: http://ideone.com/pxqc07)

# Answer
> 3 votes
# C++ - 1254

```
#include<iostream>
#include<cstring>
#include<vector>
#include<sstream>
#include<cstdlib>
using namespace std;int main(){vector<string>input,countries,output;vector<double>results;string last_val;int j,k,i=0;cout<<"Input\n";do{getline(cin,last_val);if(last_val!=""){input.push_back(last_val);countries.push_back(last_val.substr(0,2));}}while(last_val!="");for(j=0;j<countries.size();j++){results.push_back(0);for(k=0;k<input.size();k++)input[k].substr(0, 2)==countries[j]?results[j]+=atof(input[k].substr((input[k].find(countries[j])+3),(input[k].find(',',input[k].find(countries[j]))-input[k].find(countries[j]))).c_str()):results[j]+=atof(input[k].substr((input[k].find(countries[j],3)+3),(input[k].find(',',input[k].find(countries[j]))-input[k].find(countries[j]))).c_str());}for(j=0;j<input.size();j++){for(k=0;k<countries.size();k++){if(input[j].substr(0,2)!=countries[k]){results[j]-=atof(input[j].substr((input[j].find(countries[k])+ 3),(input[j].find(',',input[k].find(countries[k]))-input[j].find(countries[j]))).c_str());}}}for(i=0;i<countries.size();i++){stringstream strstream;strstream<<countries[i]<<":"<<results[i];output.push_back(strstream.str().c_str());}cout<<"Output:\n";for(i=0;i<output.size();i++){cout<<output[i]<<'\n';}return 0;}

```

I realize the code is very long, but enjoyed the good fun. This is my first time code golfing, and I am new to C++, so suggestions for improving my code are much appreciated.

## Final Challenge Results

```
Output:
US:9439.3
FR:2598.9
ES:852.1
PT:90.1
IT:887.5
IE:48
GR:116.8
JP:4817.4
DE:2903.7
UK:1546.2

```

## Ungolfed Code

```
#include<iostream>
#include<cstring>
#include<vector>
#include<sstream>
#include<cstdlib>

using namespace std;

int main() {
  vector<string> input, countries, output;
  vector<double> results;
  string last_val;
  int i, j, k;

  cout << "Input\n";
  do {
    getline(cin, last_val);
    if(last_val != "") {
      input.push_back(last_val);
      countries.push_back(last_val.substr(0, 2));
    }
  } while(last_val != "");

  for(j = 0; j < countries.size(); j++) {
    results.push_back(0);
    for(k = 0; k < input.size(); k++) {
      if(input[k].substr(0, 2) == countries[j]) {
        results[j] += atof(input[k].substr((input[k].find(countries[j]) + 3),
                             (input[k].find(',', input[k].find(countries[j])) -
                              input[k].find(countries[j]))).c_str());
      } else {
        results[j] += atof(input[k].substr((input[k].find(countries[j], 3) + 3),
                             (input[k].find(',', input[k].find(countries[j])) -
                              input[k].find(countries[j]))).c_str());
      }
    }
  }

  for(j = 0; j < input.size(); j++) {
    for(k = 0; k < countries.size(); k++) {
      if(input[j].substr(0, 2) != countries[k]) {
        results[j] -= atof(input[j].substr((input[j].find(countries[k]) + 3),
                             (input[j].find(',', input[k].find(countries[k])) -
                              input[j].find(countries[j]))).c_str());
      }
    }
  }

  for(i = 0; i < countries.size(); i++) {
    stringstream strstream;
    strstream << countries[i] << ":" << results[i];
    output.push_back(strstream.str().c_str());
  }

  cout << "Output:\n";
  for(i = 0; i < output.size(); i++) {
    cout << output[i] << '\n';
  }

  return 0;
}

```

# Answer
> 2 votes
## Ruby - 225

First try in a challenge like this, sure it could be a lot better...

```
R=Hash.new(0)
def pd(s,o=nil);s.split(':').tap{|c,a|R[c]+=a.to_f;o&&R[o]-=a.to_f};end
STDIN.read.split("\n").each{|l|c,d=l.split(';');pd(c);d.split(',').each{|s|pd(s,c.split(':')[0])}}
puts R.map{|k,v|"#{k}: #{v}"}.join("\n")

```

And the results

```
$ cat data|ruby codegolf.rb
US: 9439.299999999997
FR: 2598.8999999999996
ES: 852.1
JP: 4817.4
DE: 2903.7
UK: 1546.2000000000003
IT: 887.5
PT: 90.09999999999998
IE: 48.0
GR: 116.8

```

# Answer
> 2 votes
# JavaScript(ES6) ~~175~~,~~166~~, ~~161~~, ~~156~~, ~~153~~147

**Golfed**

```
R={};prompt().split(/\s/).map(l=>{a=l.split(/[;,:]/);c=b=a[0];a.map(v=>b=!+v?v:(R[b]=(R[b]||0)+ +v c==b?b:R[c]-=+v))});for(x in R)alert(x+':'+R[x])

```

**Ungolfed**

```
R = {};
prompt().split(/\s/).map(l => {
    a = l.split(/[;,:]/);       // Split them all!!
                                // Now in a we have big array with Country/Value items
    c = b = a[0];               // c - is first country, b - current country
    a.map(v =>
         b = !+v ? v                 // If v is country (not a number), simply update b to it's value
                 : (R[b] = (R[b] ||0) + +v   // Safely Add value to current country
                   c == b ? c : R[c] -= +v)  // If current country is not first one, remove debth
    )
});
for (x in R) alert(x + ':' + R[x])

```

**Output**

```
US:9439.299999999997
FR:2598.8999999999996
ES:852.1
JP:4817.4
DE:2903.7
UK:1546.2000000000003
IT:887.5
PT:90.09999999999998
IE:48
GR:116.8

```

# Answer
> 2 votes
# JS, 254 240 245

```
z='replace';r={};p=eval(('[{'+prompt()+'}]')[z](/\n/g,'},{')[z](/;/g,','));for(i in p){l=p[i];c=0;for(k in l){if(!c){c=k;r[c]=0;}else{r[c]-=l[k];}};for(j in p){w=p[j][c];if(w!=null)r[c]+=w}};alert(JSON.stringify(r)[z](/"|{|}/g,'')[z](/,/g,'\n'))

```

Well..I know it is quite long but this is my second code golf.

Suggestions are welcome!

BTW, Interesting Javascript preserves the order of elements in hashmaps, so, even if p contains an array of dictionaries, I can iterate each dictionary as an array and I'm sure that the first element of a dict is the first inserted. (the name of the country referred to the current line)

## Ungolfed:

```
z='replace';
r={};
p=eval(('[{'+prompt()+'}]')[z](/\n/g,'},{')[z](/;/g,',')); // make the string JSONable and then evaluate it in a structure
for(i in p){
    l=p[i];
    c=0;
    for(k in l){
            if(!c){ // if c is not still defined, this is the country we are parsing.
                    c=k;
                    r[c]=0;
            }
            else r[c]-=l[k];
    };
    for(j in p){
            w=p[j][c];
            if(!w)  r[c]+=w
    }
};
alert(JSON.stringify(r)[z](/"|{|}/g,'')[z](/,/g,'\n')) # Stringify the structure, makes it new-line separated.

```

---

Note: the input is a `prompt()` which should be a single line. But if you copy/paste a multi line text (like the proposed input) in a `prompt()` window then `JS` read it all.

Output:

```
US:9439.3
FR:2598.9
ES:852.1
PT:90.09999999999998
IT:887.5
IE:48
GR:116.8
JP:4817.4
DE:2903.7000000000003
UK:1546.2

```

# Answer
> 1 votes
## Groovy 315

```
def f(i){t=[:];i.eachLine(){l=it.split(/;|,/);s=l[0].split(/:/);if(!z(s[0]))t.put(s[0],0);t.put(s[0],x(z(s[0]))+x(s[1]));(1..<l.size()).each(){n=l[it].split(/:/);t.put(s[0],x(z(s[0]))-x(n[1]));if(!z(n[0]))t.put(n[0],0);t.put(n[0],x(z(n[0]))+x(n[1]))}};t.each(){println it}};def x(j){j.toDouble()};def z(j){t.get(j)}

Output:
US=9439.299999999997
FR=2598.8999999999996
ES=852.1
JP=4817.4
DE=2903.7
UK=1546.2000000000003
IT=887.5
PT=90.09999999999998
IE=48.0
GR=116.8

```

**Ungolfed:**

```
input = """US:10800;FR:440.2,ES:170.5,JP:835.2,DE:414.5,UK:834.5
FR:1800;IT:37.6,JP:79.8,DE:123.5,UK:227,US:202.1
ES:700;PT:19.7,IT:22.3,JP:20,DE:131.7,UK:74.9,US:49.6,FR:112
PT:200;IT:2.9,DE:26.6,UK:18.9,US:3.9,FR:19.1,ES:65.7
IT:1200;JP:32.8,DE:120,UK:54.7,US:34.8,FR:309,ES:29.5
IE:200;JP:15.4,DE:82,UK:104.5,US:39.8,FR:23.8
GR:200;DE:15.9,UK:9.4,US:6.2,FR:41.4,PT:7.5,IT:2.8
JP:4100;DE:42.5,UK:101.8,US:244.8,FR:107.7
DE:2400;UK:141.1,US:174.4,FR:205.8,IT:202.7,JP:108.3
UK:1700;US:578.6,FR:209.9,ES:316.6,IE:113.5,JP:122.7,DE:379.3"""

ungolfed(input)

def ungolfed(i){
    def tallyMap = [:]
    i.eachLine(){
        def lineList = it.split(/;|,/)
        def target = lineList[0].split(/:/)

        if(!tallyMap.get(target[0])){tallyMap.put(target[0],0)}
        tallyMap.put(target[0],tallyMap.get(target[0]).toDouble() + target[1].toDouble())
        (1..lineList.size()-1).each(){ e ->
            def nextTarget = lineList[e].split(/:/)
            //subtract the debt
            tallyMap.put(target[0], (tallyMap.get(target[0]).toDouble() - nextTarget[1].toDouble()))
            //add the debt
            if(!tallyMap.get(nextTarget[0])){ tallyMap.put(nextTarget[0], 0) }
            tallyMap.put(nextTarget[0], (tallyMap.get(nextTarget[0]).toDouble() + nextTarget[1].toDouble()))
        }
    }
    tallyMap.each(){
        println it
    }
}

```

# Answer
> 1 votes
# PHP, 333

```
$a='';while(($l=trim(fgets(STDIN)))!='')$a.=$l.'\n';$a=rtrim($a,'\n');$p=explode('\n',$a);foreach($p as $q){preg_match('/^([A-Z]+)/',$q,$b);preg_match_all('/'.$b[0].':(\d+(?:\.\d+)?)/',$a,$c);$e=ltrim(strstr($q,';'),';');preg_match_all('/([A-Z]+)\:(\d+(?:\.\d+)?)/',$e,$d);echo $b[0].':'.(array_sum($c[1])-array_sum($d[2])).PHP_EOL;}

```

Ungolfed version :

```
$a='';
while(($l=trim(fgets(STDIN)))!='')
    $a .= $l.'\n';
$a = rtrim($a,'\n');
$p = explode('\n',$a);
foreach($p as $q){
    preg_match('/^([A-Z]+)/',$q,$b);
    preg_match_all('/'.$b[0].':(\d+(?:\.\d+)?)/',$a,$c);
    $e = ltrim(strstr($q,';'),';');
    preg_match_all('/([A-Z]+)\:(\d+(?:\.\d+)?)/', $e, $d);
    echo $b[0].':'.(array_sum($c[1])-array_sum($d[2])).PHP_EOL;
}

```

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


title: Android Lock Screen

text:
# Question
Title: Android Lock Screen
## Intro

You are sitting in a board room at the end of a long table. You look around and see Tim Cook, the Apple Board of Directors, the ghost of Steve Jobs, and Jack Donaghy. Apple has called this meeting because they have realized how much cooler the Android lock screen is, and they want to 1-UP them. Everyone in the room stares at you as Ghost Steve cries, "Help me, CodeGolf Man! You're my only hope!"

## The Problem

The Android lock screen is a 3 x 3 grid of dots that can be connected by swiping a finger from one dot to the next, creating a path. A password is considered any possible path that includes any number of dots, and excludes any number of dots. (On an actual phone, the path must be at least 4 dots long. For this challenge, ignore that restriction.) Apple plans to replace the 3 x 3 grid with an M x N grid, which is (M\*N)/9 times better!

Rules:

- A zero dot path is not a password, but a 1 dot path is
- A path can cross itself
- A path cannot cross directly over a dot without including that dot
- A dot can only be used once
- Paths that are identical by rotation are not the same password
- Paths that are identical but ordered in reverse are not the same password

For example, on a 3x3 grid with dots numbered from 1 to 9:

```
1 2 3
4 5 6
7 8 9

```

Some valid paths are:

```
1
3
7,2,3
1,5,9,2
1,8,6,5,4
4,2,3,5,6,7,8,9
5,9,6,4

```

And some invalid paths are:

```
1,3
1,9,5
7,5,4,7
4,6

```

Your input will be three numbers:

```
(M,N,d)

```

Where the grid is M x N, and d is the length of the path

```
1 <= M <= 16
1 <= N <= 16
1 <= d <= M * N

```

Your program or function will be given the input as a comma separated string, and it must return the number of possible passwords of that length. For example:

```
Input:  2,2,1
Output: 4
Input:  2,2,2
Output: 12
Input:  7,4,1
Output: 28

```

Standard code golf rules apply, shortest code wins!

```
//If I've made a mistake or the rules are unclear, please correct me!

```

# Answer
## Python - 170 bytes

```
from fractions import*
p=lambda m,n,d,l=0,s=set():d<1or sum([p(m,n,d-1,i,s|{i})for i in range(m*n)if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))])

```

I realize that the brackets inside `sum([...])` are not strictly necessary, but there's a large performance penalty for not including them.

Output for all 3x3s:

```
for i in range(4, 10):
  print p(3, 3, i)

```

Produces:

```
1624
7152
26016
72912
140704
140704

```

For testing/confirmation purposes, the first 6 values for a 4x5 board:

```
20
262
3280
39644
459764
5101232

```

4x5 is an interesting case to verify, because it has 2x2, 3x3, and 2x4 peg jumps.

---

### Brief Explanation

In general, this is an exhaustive search, with cumulative pruning. For example, because `p(3, 3, 4)` is 1624, `p(3, 3, 5)` will only check 8120 posibilities, rather than naïvely checking all 15120. Most of the logic is contained in the condition:

```
if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))

```

In plain english, this can be understood as:

```
If no pegs have been used yet
     OR
   the target peg has not yet been used
     AND
   each of the pegs directly between the target peg and the
   current peg (a.k.a. "jumped over") have already been used

```
> 14 votes

---
Tags: code-golf, number, combinatorics
---


# Question
Title: Books full of nonsense: Identify limericks
As we all know, limericks are short, five-line, occasionally-lewd poems with an AABBA rhyming scheme and an anapestic meter (whatever that is):

> Writing a Limerick's absurd
> Line one and line five rhyme in word
> And just as you've reckoned
> They rhyme with the second
> The fourth line must rhyme with the third

You are tasked to write the *shortest* program that, when fed an input text, prints whether it thinks that the input is a valid limerick. Input can either be on the command line or through standard input, at your option, and output could either be a simple "Y"/"N" or a confidence score, again at your option.

Here's another example of a correct limerick:

> There was a Young Lady whose eyes
> Were unique as to colour and size
> When she opened them wide
> People all turned aside
> And started away in surprise

But the poem below is clearly *not* a limerick, since it doesn't rhyme:

> There was an old man of St. Bees
> Who was stung in the arm by a wasp.
> When asked, "Does it hurt?"
> He replied, "No, it doesn't,
> I'm so glad that it wasn't a hornet."

Nor is this one, as the meter is all wrong:

> I heard of a man from Berlin
> Who hated the room he was in
> When I asked as to why
> He would say with a sigh:
> "Well, you see, last night there were a couple of hoodlums around who were celebrating the Bears winning the darned World Cup, and they were really loud so I couldn't sleep because of the din."

### Clues

Here are some of the clues you could use to decide whether or not your input is a limerick:

* Limericks are always five lines long.
* Lines 1, 2 and 5 should rhyme.
* Lines 3 and 4 should rhyme.
* Lines 1, 2 and 5 have around 3x3=9 syllables, while the third and fourth have 2x3=6 syllables

Note that none of these except the first are hard-and-fast: a 100% correctness rating is impossible.

### Rules

* Your entry should *at the very least* correctly categorize examples 1 through 3 in a deterministic fashion.
* You *are* allowed to use any programming language you would like, except of course programming languages specifically designed for this contest (see here).
* You *are not* allowed to use any library except your programming language's standard offerings.
* You *are* allowed to assume that this file, the CMU Sphinx pronounciation dictionary, is in a file called 'c' in the current directory.
* You are *not* allowed to hard-code for the test inputs: your program should be a general limerick categorizer.
* You *are* allowed to assume that the input is ASCII, without any special formatting (like in the examples), but your program should not be confused by interpunction.

### Bonuses

The following bonuses are available:

* Your program outputs its result as a limerick? Subtract **150 characters** length bonus!
* Your program also correctly identifies sonnets? Subtract **150 characters** extra length bonus!
* Your program outputs its result as a sonnet when used on a sonnet? Subtract **100 characters** additional extra length bonus!

### Finally...

Remember to mention which bonuses you think you deserve, if any, and subtract the bonus from your number of characters to arrive at your score. This is a *code golf* contest: the shortest entry (i.e. the entry with the lowest score) wins.

If you need more (positive) test data, check out the OEDILF or the Book of Nonsense. Negative test data should be easy to construct.

Good luck!

# Answer
> 8 votes
# Python: 400 - 150 - 150 = 100

The shortest script I could come up with is that one...

```
import re,sys;f,e,c=re.findall,lambda l,w:f('^'+w.upper()+'  (.+)',l),lambda*v:all([a[i]==a[v[0]]for i in v]);a=[sum([[e(l,w)[0].split()for l in open('c')if e(l,w)][0]for w in f(r'\w+',v)],[])[-2:]for v in sys.stdin];n=len(a);print n==14and c(0,3,4,7)*c(1,2,5,6)*c(8,11)*c(9,12)*c(10,13)*"Sonnet"or"For a critic\nOf limerick\nWell-equipped\nIs this script.\n%s limerick!"%(n==5and c(0,1,4)and c(2,3))

```

...but don't even try it. It parses the provided dictionary for every word it meets, thus being very slow. Also, an error is generated whenever a word is not in the dictionary.

The code still meets the requirements though: recognizing whether the text passed via *stdin* is a limerick, a sonnet, or neither of those.

With only 20 more characters, here is the optimized version:

```
import re,sys;f,e,c=re.findall,lambda l:f(r'^(\w+)  (.+)',l),lambda*v:all([a[i]==a[v[0]]for i in v]);d={e(l)[0][0]:e(l)[0][1].split()for l in open('c')if e(l)};a=[sum([d.get(w.upper(),[])for w in f(r'\w+',v)],[])[-2:]for v in sys.stdin];n=len(a);print n==14and c(0,3,4,7)*c(1,2,5,6)*c(8,11)*c(9,12)*c(10,13)*"Sonnet"or"For a critic\nOf limerick\nWell-equipped\nIs this script.\n%s limerick!"%(n==5and c(0,1,4)and c(2,3))

```

**Features**

* able to recognize sonnets (-150)
* answers to limericks with a limerick (-150)
* relatively fast: only one file parsing per execution

**Usage**

```
cat poem.txt | python poem-check.py

```

3 different outputs are possible:

* a limmerick saying the input is one if it is the case
* a limmerick saying the input is not one if it is the case
* "Sonnet" if the input is recognized as such

**Expanded code with explanations**

```
import re, sys

# just a shortened version of the 're.findall' function...
f = re.findall
# function used to parse a line of the dictionary
e = lambda l:f(r'^(\w+)  (.+)', l)

# create a cache of the dictionary, where each word is associated with the list of phonemes it contains
d = {e(l)[0][0]:e(l)[0][1].split(' ') for l in open('c') if e(l)}

# for each verse (line) 'v' found in the input 'sys.stdin', create a list of the phoneme it contains;
# the result array 'a' contains a list, each item of it corresponding to the last two phonemes of a verse
a = [sum([d.get(w.upper(), []) for w in f(r'\w+',v)],[])[-2:] for v in sys.stdin]

# let's store the length of 'a' in 'n'; it is actually the number of verses in the input
n = len(a)
# function used to compare the rhymes of the lines which indexes are passed as arguments
c = lambda*v:all([a[i] == a[v[0]] for i in v])

# test if the input is a sonnet, aka: it has 14 verses, verses 0, 3, 4 and 7 rhyme together, verses 1, 2, 5 and 6 rhyme together, verses 8 and 11 rhyme together, verses 9 and 12 rhyme together, verses 10 and 13 rhyme together
if n==14 and c(0,3,4,7) and c(1,2,5,6) and c(8,11) and c(9,12) and c(10,13):
    print("Sonnet")
else:
    # test if the input is a limerick, aka: it has 5 verses, verses 0, 1 and 4 rhyme together, verses 2 and 3 rhyme together
    is_limerick = n==5 and c(0,1,4) and c(2,3)
    print("For critics\nOf limericks,\nWell-equipped\nIs this script.\n%s limerick!", is_limmerick)

```

# Answer
> 2 votes
# ECMAScript 6 (138 points; try in Firefox):

`288` \- `150` points bonus for including limerick (pinched from @MathieuRodic).

```
a=i.split(d=/\r?\n/).map(x=>x.split(' '));b=/^\W?(\w+) .*? (\w+\d( [A-Z]+)*)$/;c.split('\r\n').map(x=>b.test(x)&&eval(x.replace(b,'d["$1"]="$2"')));e=f=>d[a[f][a[f].length-1]];alert('For critics\nOf limericks,\nWell-equipped\nIs this script.\n'+(a[4]&&e(0)==e(1)&e(0)==e(4))+' limerick!')

```

## Notes:

Expects the variable `c` to contain the contents of the dictionary file, as you can't read files in plain ECMAScript.

ECMAScript doesn't have standard input, but `prompt` is generally considered "standard input"; however, as `prompt` converts line breaks to spaces in most (if not all) browsers, I'm accepting input from the variable `i`.

## Ungolfed code:

```
// If you paste a string with multiple lines into a `prompt`, the browser replaces each line break with a space, for some reason.
//input = prompt();

// Split into lines, with each line split into words
lines = input.split('\n').map(x => x.split(' '));

dictionaryEntryRegEx = /^\W?(\w+) .*? (\w+\d( [A-Z]+)*)$/;
dictionary = {};
// Split it into
c.split(/\r?\n/).map(x => dictionaryEntryRegEx && eval(x.replace(dictionaryEntryRegEx, 'dictionary["$1"] = "$2"')));

// Get the last word in the line
getLastWordOfLine = (lineNumber) => dictionary[line[lineNumber][line[lineNumber].length - 1]]

alert('For critics\nOf limericks,\nWell-equipped\nIs this script.\n' + (lines[4] && getLastWordOfLine(0) === getLastWordOfLine(1) && getLastWordOfLine(0) === getLastWordOfLine(4)) + ' limerick!');

```

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


title: How many Sudoku puzzles exist?

text:
# Question
Title: How many Sudoku puzzles exist?
This is not a Sudoku solver, nor a Sudoku checker.

Your challenge is to write a function or script that, given as input the "block" size of a 2D Sudoku puzzle (which is 3 for the classic 9x9 board, 4 for a 16x16 board, etc.) will compute an approximation of the number of distinct puzzles (solutions) that exist for that size.

For example, given input 3, your program should print an approximation, to the desired precision, of the number 6,670,903,752,021,072,936,960 which is the known number of distinct 9x9 Sudoku puzzles, or 5,472,730,538 when taking into account the various symmetries. Your solution should state whether symmetries are counted or ignored.

"Desired precision" is left undefined: your program might run for a given time and then output its result, or compute it up to a given number of significant digits, or even run forever, printing better and better approximations. The point is that it should be possible to make it compute the result to any required precision, in a finite time. (So "42" is not an acceptable answer.) Restricting the precision of your result to the available machine floats is acceptable.

No accessing online resources, no storing the source code in the file name, etc.

---

PS: I know this is a Hard Problem (NP-complete if I'm not mistaken.) But this question is only asking for an approximate, statistical solution. For example you can try random configurations that satisfy one (or better two) constraints, compute how many of those exist and then check how often you get a puzzle that satisfies all three constraints. This will work in a decent time for small sizes (certainly for size=3 and possibly 4) but the algorithm should be generic enough to work for any size.

The best algorithm wins.

---

PS2: I changed from code-golf to code-challenge to better reflect the difficulty of the problem and encourage smarter solutions, over dumb but well-golfed ones. But since apparently "best algorithm" is unclear, let me try to define it properly.

Given enough time and disregarding constant factors (including CPU and intepreter speed), or equivalently, considering their asymptotical behaviour, **which solution would converge to the exact result the fastest?**

# Answer
> 3 votes
# C++

**What i will present here is an algorithm, illustrated with an example for a 3x3 case. It could theoretically be extended to the NxN case, but that would need a much more powerful computer and/or some ingenious tweaks. I will mention some improvements as I go through.**

Before going further, **let's note the symmetries of the Sudoku grid,** i.e. the transformations which lead to another grid in a trivial way. For block size 3, the symmetries are as follows:

Horizontal symmetry

```
**The N=3 sudoku is said to consist of 3 "bands" of 3 "rows" each**
permute the three bands: 3! permutations = 6
permute the rows in each band: 3 bands, 3! permutations each =(3!)^3=216

```

Vertical symmetry

```
**The N=3 sudoku is said to consist of 3 "stacks" of 3 "columns" each.**
the count is the same as for horizontal.

```

Note that horizontal and vertical reflections of the grid can be achieved by a combination of these, so they do not need to be counted. There is one more spatial symmetry to be considered, which is transposing, which is a factor of `2`. This gives the total spatial symmetry of

```
2*(N!*(N!)^N)^2 = 2*(6*216)^2=3359232 spatial symmetries for the case N=3.

```

Then there is another, very important symmetry, called relabelling.

```
Relabelling gives a further (N^2)!=9!=362880 symmetries for the case N=3. So the total
number of symmetries is 362880*3359232=1218998108160.

```

The total number of solutions cannot be found simply by multiplying the number of symmetry-unique solutions by this number, because there are a number (less than 1%) of automorphic solutions. That means that for these special solutions there is a symmetry operation that maps them to themselves, or multiple symmetry operations that map them to the same other solution.

**To estimate the number of solutions, I approach the problem in 4 steps:**

**1.Fill an array `r[362880][12]`with all possible permutations of the numbers 0 to 8.** (this is programming, and it is in C, so we are not going to use 1 to 9.) If you are astute you will notice that the second subscript is 12 not 9. This is because, while doing this, bearing in mind that we are going to consider this to be a "row" we also calculate three more integers `r[9,10,11] == 1<<a | 1<<b | 1<<c` where 9,10,11 refer to the first, second and third stack and a,b,c are the three numbers present in each stack for that row.

**2.Fill an array `b` with all possible solutions of a band of 3 rows.** To keep this reasonably small, only include those solutions where the top row is 012,345,678. I do this by brute force, by generating all possible middle rows and ANDing `r[0][10,11,12]` with `r[i][10,11,12]`. Any positive value means there are two identical numbers in the same square and the band is invalid. When there is a valid combination for the first two rows, I search the 3rd (bottom) row with the same technique.

I dimensioned the array as b\[2000000\]\[9\] but the program only finds 1306368 solutions. I did not know how many there were, so I left the array dimension like that. This is actually only half the possible solutions for a single band (verified on wikipedia), because I only scan the 3rd row from the current value for `i` upwards. The remaining half of the solutions can be found trivially by exchanging the 2nd and 3rd rows.

The way the information is stored in array `b` is a little confusing at first. instead of using each integer to store the numbers `0..8` found in a given position, here each integer considers one of the numbers `0..8` and indicates in which columns it can be found. thus `b[x][7]==100100001` would indicate that for solution x the number 7 is found in columns 0,5 and 8 (from right to left.) The reason for this representation is that we need to generate the rest of the possibilities for the band by relabelling, and this representation makes it convenient to do this.

**The two steps above comprise the setup and take about a minute (possibly less if I removed the unnecessary data output. The two steps below are the actual search.)**

**3 Search randomly for solutions for the first two bands that do not clash (i.e. do not have the same number twice in a given column.** We pick a random solution for band 1, assuming always permutation 0, and a random solution for band 2 with a random permutation. A result is normally found in less than 9999 tries (first stage hit rate in the thousands range) and takes a fraction of a second. By permutation, I mean that for the second band we take a solution from b\[\]\[\] where the first row is always 012,345,678 and relabel it so that any possible sequence of numbers on the first row is possible.

**4 When a hit is found in step 3, search for a solution for the third band which does not clash with the other two.** We do not want to make just one try, otherwise the processing time for step 3 would be wasted. On the other hand we do not want to put an inordinate amount of effort into this.

Just for fun, last night I did it the dumbest way possible, but it was still interesting (because it nothing for ages, then found large numbers of solutions in bursts.) It took all night to get one datapoint, even with the little hack `(!z)` I did to abort the last `k` loop as soon as we know this is not a valid solution (which makes it run nearly 9 times faster.) It found 1186585 solutions for the complete grid after searching all 362880 relabellings of all 1306368 canonical solutions for the last block, a total of 474054819840 possibilities. That's a hit rate of 1 in 400000 for the second stage. I will try again soon with a random search rather than a scan. It should give a reasonable answer in just a few million tries, which should take only a few seconds.

The overall answer should be (362880\*(1306368\*2))^3\*hit rate=8.5E35\*hit rate. By back calculating from the number in the question, I expect a hit rate of 1/1.2E14. What I've got so far with my single datapoint is 1/(400000\*1000) which is out by a factor of about a million. This could be an anomaly of chance, an error in my program, or an error in my math. I won't know which it is until I run a few more tests.

**I'll leave this here for tonight. The text is a bit scrappy, I will tidy it up soon and hopefully add some more results, and maybe a few words on how to make it faster and how to extend the concept to N=4. I don't think I'll be making too many more changes to my program, though :-)**

Ah.. the program:

```
#include "stdafx.h"
#define _CRT_RAND_S
#include <algorithm>
#include <time.h>

unsigned int n[] = { 0,1,2,3,4,5,6,7,8 }, r[362880][12], b[2000000][9],i,j,k,l,u,v,w,x,y,z;

int main () {

  //Run through all possible permutations of n[] and load them into r[][]
  i=0;
  do {
      r[i][9] = r[i][10] = r[i][11]=0;
      for (l = 0; l < 9; l++){
          r[i][l] = n[l];
          r[i][9 + l / 3] |= 1 << n[l];
      }
      if((i+1)%5040==0) printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
          ,r[i][0],r[i][1],r[i][2],r[i][3],r[i][4],r[i][5],r[i][6],r[i][7],r[i][8],r[i][9],r[i][10],r[i][11],r[i][9]+r[i][10]+r[i][11]);
      i++;
  } while ( std::next_permutation(n,n+9) );

  //Initialise b[][]
  for (l = 0; l<2000000; l++) for (k = 0; k<9; k++) b[l][k]=0;
  //fill b[][] with all solutions of the first band, where row0 ={0,1,2,3,4,5,6,7,8} and row1<row2
  l=0;
  for (i = 0; i<362880; i++)
  if (!(r[0][9] & r[i][9] | r[0][10] & r[i][10] | r[0][11] & r[i][11])){printf("%d %d \n",i,l);
     for (j=i; j<362880;j++)
       if(!(r[0][9]&r[j][9] | r[0][10]&r[j][10] | r[0][11]&r[j][11] | r[j][9]&r[i][9] | r[j][10]&r[i][10] | r[j][11]&r[i][11] )){
           for (k = 0; k < 9; k++){
               b[l][r[0][k]]|=1<<k;
               b[l][r[i][k]]|=1<<k;
               b[l][r[j][k]]|=1<<k;
            }
            l++;
       }
//        printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
//        ,r[i][0],r[i][1],r[i][2],r[i][3],r[i][4],r[i][5],r[i][6],r[i][7],r[i][8],r[i][9],r[i][10],r[i][11],r[i][9]+r[i][10]+r[i][11]);
//        printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
//        ,r[j][0],r[j][1],r[j][2],r[j][3],r[j][4],r[j][5],r[j][6],r[j][7],r[j][8],r[j][9],r[j][10],r[j][11],r[j][9]+r[j][10]+r[j][11]);
//        printf("%d %d %o %o %o %o %o %o %o %o %o \n",i,l,b[l][0],b[l][1],b[l][2],b[l][3],b[l][4],b[l][5],b[l][6],b[l][7],b[l][8]);
  }

  // find a random solution for the first 2 bands
  l=0;
  do{
      rand_s(&u); u /= INT_MIN / -653184; //1st band selection
      rand_s(&v); v /= INT_MIN / -181440; //2nd band permutation
      rand_s(&w); w /= INT_MIN / -653184; //2nd band selection
      z = 0;
      for (k = 0; k < 9; k++) z |= b[u][k] & b[w][r[v][k]];
      l++;
  } while (z);
  printf("finished random after %d tries \n",l);
  printf("found solution with top band %d permutation 0, and middle band %d permutation %d \n",u,w,v);
  getchar();

  // scan all possibilities for the last band
  l=0;
  for (i = 0; i < 362880; i++) for (j = 0; j < 1306368; j++){
              z=0;
              for(k=0;(k<9)&&(!z);k++) z|= b[u][k] & b[j][r[i][k]] | b[j][r[i][k]] & b[w][r[v][k]];
              if (!z){ l++; printf("solution %d : i= %d j=%d",l,i,j); }
  }
  printf("finished bottom band scan at %d millisec \n", clock()); getchar();
}

```

---
Tags: code-challenge, sudoku
---


title: Unicorn "Miner" CodeGolf

text:
# Question
Title: Unicorn "Miner" CodeGolf
This is a pretty cool CodeGolf challenge in the sense that you're only going to have a limited amount of time to do it. You need to build a program that "mines" StackOverflow unicoins. In order to do this, you need to perform just two HTTP requests. I'm not going to say how, to add to the fun.

The first person to do this gets a -10 on their score. Good luck! Also, if your doing this in JavaScript or similar, you don't need to account for the target browser's XSS, etc. prevention.

# Answer
> 6 votes
# Javascript, 104 (114 chars - 10 bonus)

All due credit here. Simply posting this to get the "first answer" -10 bonus ;-).

```
p='$.post("/unicoin/'
setInterval(p+'rock",function(o){'+p+'mine?rock="+o.rock,StackExchange.options.user)})',2e4)

```

setInterval accepts both functions and strings of code. After susbtituting the variable *p*, the following gets executed every 20 seconds:

```
$.post("/unicoin/rock", function(o) {
    $.post("/unicoin/mine?rock=" + o.rock, StackExchange.options.user)
}

```

---

Edits are welcome. I don't know well enough to really competitively golf this.

---
Tags: code-golf
---


title: Juggling by Numbers

text:
# Question
Title: Juggling by Numbers
Your task is to generate a valid juggling pattern by completing a given template. But first, you probably need to know how such a pattern is denoted.

## Introduction to Siteswap

Siteswap is the established notation for juggling patterns. It works by dividing the pattern into beats. At each beat your left and right hand alternate at throwing a ball. Each throw (i.e. each beat) is denoted by a number which indicates when that ball is thrown next - this corresponds directly to the height of the throw.

Let's look at some examples. See animations of all of these here.

### 3-Ball Cascade

The simplest 3-ball pattern. Each ball is thrown at every third beat (alternating hands). Writing out the beats this looks like follows (the ASCII lines connect two beats at which the same ball is thrown):

```
Beat     1 2 3 4 5 6 7 8 9
Hand     L R L R L R L R L
Siteswap 3 3 3 3 3 3 3 3 3
         └─┼─┼─┘ │ │
           └─┼───┘ │
             └─────┘

```

Note how every ball thrown at an `L` beat, is thrown next at an `R` beat.Siteswap patterns repeat implicitly, so this pattern is usually denoted as `333`, although simply `3` would also be sufficient.

### 441

Here is a slightly more complicated example with the siteswap **441**:

```
Beat     1 2 3 4 5 6 7 8 9
Hand     L R L R L R L R L
Siteswap 4 4 1 4 4 1 4 4 1
         │ │ └─┘ │ │
         └─┼─────┘ │
           └───────┘

```

Note how even-numbered throws go to the same hand they were thrown from, while odd-numbered throws go to the other hand.

### 423

Sometimes you just want to hold a ball through a beat instead of throwing it. All that means, that this ball is thrown the next time its this hand's turn - i.e. 2 beats later. So holding a ball is equivalent to a `2` in the pattern:

```
Beat     1 2 3 4 5 6 7 8 9
Hand     L R L R L R L R L
Siteswap 4 2 3 4 2 3 4 2 3
         │ └─┼─┘ │ │
         │   └───┼─┘
         └───────┘

```

### 50505

A `0` means that the current hand is empty at that beat, as this pattern shows:

```
Beat     1 2 3 4 5 6 7 8 9
Hand     L R L R L R L R L
Siteswap 5 0 5 0 5 5 0 5 0
         └───┼───┼─┘   │
             └───┼─────┘
                 └───────>

```

## Multiplex Juggling

This problem would be a bit too simple with vanilla siteswap though. Enter multiplex patterns! Multiplex juggling means that you throw multiple balls from one hand at the same time. For instance, in the above 3-ball cascade, if you were two throw an additional ball at every third beat, the pattern would become `[33]33` and look like this:

```
Beat     1    2 3 4    5 6 7    8 9
Hand     L    R L R    L R L    R L
Siteswap [33] 3 3 [33] 3 3 [33] 3 3
          └┴──┼─┼──┴┘  │ │
              └─┼──────┘ │
                └────────┘

```

Here is another example, where the multiplex throw has two different heights/lengths. It could be denoted as either `[34]11` or `[43]11`:

```
Beat     1    2 3 4    5 6 7    8 9
Hand     L    R L R    L R L    R L
Siteswap [43] 1 1 [43] 1 1 [43] 1 1
          ││  └─┴──┘│  │
          │└────────┘  │
          └────────────┘

```

(Note that the `1` thrown at beat `2` lands at beat `3` and is immediately thrown again (as another `1`) to land at beat `4` and be part of the second multiplex throw.)

*The siteswap for the animation at the beginning of this post was* `[53]15121`.

## Pattern Validity

For a pattern to be *semantically* valid the number of balls in a hand must always correspond to the number of throws indicated at that beat. This means, there must be no balls landing at a beat with a `0`, there must be only one ball landing at a beat with any other single digit, and there must be **n** balls landing at a multiplex beat, where **n** is the number of digits in that multiplex throw. The pattern must also be able to repeat seamlessly.

Examples of invalid patterns are `543` (all balls would land at the same beat), `240` (the `2` would land at the `0` beat) or `33[24]` (no ball lands at the multiplex beat, but two balls land at both of the other two beats).

## The Challenge

You will take a siteswap pattern which contains wildcards and output a valid pattern, with those wildcards filled in.

Take as **input (via stdin, command-line argument, file or function parameter)** a string of the format

```
n s

```

Where `n` is an integer indicating the number of balls to be used, and `s` is a siteswap pattern (*without* whitespace). You may assume that it is *syntactically* correct - all square brackets are matched and not nested, and there are no unexpected characters. All throws will be single-digit throws (`0` \- `9`). **However**, some *beats* may just be denoted as a `_`, which is to be filled in with a single or a multiplex throw in the output.

*Note:* something like `[_3]` will *not* be part of the input. Either the entire beat is missing or the entire beat is given.

Output a valid pattern, which can be juggled with the given number of balls and agrees with the input pattern in all the specified beats. If no valid pattern is possible with the given inputs, output `!`. **Output** will also be **via stdout, to a file or as a function return value.**

*Note:* The output must not contain unnecessary square brackets or zeroes in multiplex throws. So outputs containing `[3]` or `[03]` are not accepted, you have to output `3` instead. The order of digits in a multiplex throw is not relevant.

*Note:* You *may* omit patterns that are duplicates under cyclic permutations. E.g. for input `3 __` (note the two wildcards), both `42` and `24` are valid answers (among others), but they actually describe the same pattern. You can either output both or just one of them, but you'll have to do it consistently.

This is **code golf**, the shortest code wins (subject to bonuses listed at the bottom of the question).

You can use JugglingLab to play around with patterns to see if they are valid and what they look like.

### Examples

```
Input           Possible Outputs     Comments

3 _             3
                [21]
                [111]

3 4_3           423

4 4_2           4[51]2
                4[42]2
                4[321]2

3 _23_          6231
                4233
                323[31]
                2235
                223[41]
                0237
                023[43]
                [42]231
                [32]23[11]

```

```
4 5_3           !                    5 and 3 will both land at the third beat, but
                                     there is only a single throw at that beat. This
                                     cannot be fixed with any throw in the blank.

2 5_4           !                    Any possible throw in the wildcard (including a
                                     0) will make a pattern for at least 3 balls.

3 54_           !                    The only solution that would correspond to a
                                     3-ball pattern is 540, which is not semantically
                                     valid because the 5 and 4 both land at beat 3.
                                     There are valid solutions, but they require at
                                     least 4 balls.

```

### Bonuses

* If your answer can handle "digits" up to 35, denoted by letters (10 = A, 11 = B, ...), subtract **20 characters**. You may decide if those letters should be upper-case, lower-case or case-insensitive. (JugglingLab can handle them in lower-case if you want to look at some insane patterns.)
* If your answer outputs *all* valid solutions, subtract **20 characters**.

# Answer
## Python, 587 - 20 = 567 chars

```
from itertools import *
E,J,L,R,X=enumerate,''.join,len,range,list
def f(x):
 [u,p]=str.split(x);n=int(u);a=[[[x],x][type(x)==X]for x in eval("["+J(c if c=="["else"-1,"if c=="_"else c+","for c in p)+"]")];l,w=L(a),[i for i,x in E(a)if x==[-1]]
 for j in product([[0]]+X(chain(*[combinations_with_replacement(R(1,10),i+1)for i in R(n+1)])),repeat=L(w)):
  for k,m in zip(w,j):a[k]=m
  b=[0]*l
  for k,x in E(a):
   for y in x:b[(k+y)%l]+=1
  if all(x==L(y)for x,y in zip(b,a))&((sum(map(sum,a))/l)==n):
   u=0;yield J([['['+J(map(str,x))+']',str(x[0])][L(x)==1]for x in a])
 if u:yield"!"

```
> 7 votes

---
Tags: code-golf
---


# Question
Title: The Final Stand - Defeat the Zombie Horde
**Introduction**

You are alone on an island. The remainder of humanity is dead (probably due to the bug in user12345's code). The Zombie Pirate Horde has reached your island, and they are endless. It's time to kick ass or chew bubble gum, and you're all outta bubble gum.

**Problem**

Our doomsday scenario is described by 2 integers on a single line, `m` and `n`. On your island are outposts uniquely numbered from 1 to `m`. The following `n` lines each contain three integers, `x`, `y`, and `z`, separated by a space. `x` and `y` are the unique IDs of two outposts, and `z` is the number of zombies that will be encountered on the path between them.

When you travel a path, you lose `z` ammunition and you kill `z` zombies. If you travel the same path again, you will encounter the same number of zombies, unfortunately. All outposts generate +1 ammunition each time you travel a path. You begin with 100 ammunition at outpost 1. All outposts begin with 0 ammunition. You die immediately if no path exists for which your ammunition is greater than the number of zombies on that path, and the remainder of your ammunition is converted to kills. Such is your final stand.

Write a program that outputs the maximum number of zombies you can kill for a given scenario. If you can kill an infinite number of zombies, simply output `x`.

**Example Input**

```
5 6
1 2 4
2 3 4
3 1 4
2 4 10
2 5 10
1 1 50

```

**Example Output**

```
x

```

**Assumptions**

* A path will be between two valid outposts. That is to say 1 \<= `x`/`y` \<= `m`
* If a path between `x` and `y` is not listed, it cannot be traveled
* A path is bidirectional
* 1 \< `m` \<= 100
* 1 \< `n` \<= 500
* Input must be provided through stdin, read from a file, or accepted as a sole argument to the program, and it must exactly follow the format of the example
* The runtime of your program may be arbitrarily large but must be determinably finite

The code with the fewest characters wins!

# Answer
# Java ( *less* grotesque: 8415 5291 3301)

Ok. Basically, I'm embarrassed no-one has submitted a solution. So a few days ago I began trying to solve this problem, b/c it's great.. Follow that link to watch my progress on it via GitHub.

### Edit

New solver version, much more "golfed", with corrected cycle checker as identified by MT0. It also supports fast-forwarding routes, tuneable by changing how much memory is available to the VM. Latest **BIG** edit: realized that I had a few other small index errors and premature optimizations, that resulted in a failure to consider quite a large number of types of wins. So that's fixed, carefully. The new version is both smaller and below. For our reference route, `java -Xmx2GB ZombieHordeMin` does the trick quite nicely (be warned, it will take a while).

### Cool factoid

In a fascinating twist, there are MANY solutions at length 24, and my solver finds one different from MT0's, but identical in principle, except that it *starts* by visiting the the other outposts connected to `1`. Fascinating! Totally counter human intuition, but perfectly valid.

### Solution Highlights

So here's mine. It's (partially) golfed, b/c it's an exponential, almost-brute-force solver. I use an IDDFS (iterative deepening depth first search) algorithm, so it's a great general solver that doesn't skip, so it solves **both** parts of the OP's question, namely:

* If a winning route is found (infinite zombies), output 'x'.
* If all routes end in death (finite zombies), output the largest number of zombies killed.

Give it enough power, memory, and time, and it will do just that, even slow-death maps. I spent some more time improving this solver, and while more can be done, it's a bit better now. I also integrated MT0's advice on the best infinite-zombies solution, and removed several premature optimizations from my win-checker that prevented the previous version from finding it, and now I do in fact find a very similar solution to the one MT0 described.

A few other highlights:

* As mentioned, uses an IDDFS to find the shortest possible winning route.
* Since it is at core a DFS, it will also discover if every route ends in the death of our hero, and keeps track of the "best" route in terms of most zombies killed. Die a hero!
* I've instrumented the algorithm to make it more interesting to watch Removed for golfing purposes. Follow one of the links to github to see the ungolfed version.
* There are a number of comments throughout as well, so feel free to re-implement for your own solution building on my approach, or show me how it should be done!
* Memory-adaptive route fast-forwarding
    + Up to available system memory, will keep track of "end routes" that did not result in death.
    + Using a fancy route compression and decompression routine, progress from a prior iteration of IDDFS is restored to prevent rediscovery all prior visited routes.
    + As an intentional side-bonus, acts as a dead-end route cull. Dead end routes aren't stored, and will never be visited again in future depths of IDDFS.

## History of the solver

* I tried a bunch of one-step look-ahead algorithms, and while for very simple scenarios they would work, ultimately they fall flat.
* Then I tried a two-step look-ahead algorithm, which was.. unsatisfying.
* I then began building an n-step lookahead, when I recognized that this approach is reducible to DFS, yet DFS is far ... more elegant.
* While building the DFS, it occurred to me that IDDFS would ensure (a) find best HERO (death) route or (b) first winning cycle.
* Turns out building a win-cycle checker is easy, but I had to go through several very very wrong iterations before I got to a provably successful checker.
* Factored in MT0's win-path to remove three lines of premature optimization that made my algorithm blind to it.
* Added an adaptive route-caching algorithm that will use all the memory you give it to prevent unnecessary redoing of work between IDDFS calls, and also culls dead-end routes up to the limits of memory.

### The (golfed) code

On to the code (get the ungolfed version here or here):

```
import java.util.*;public class ZombieHordeMin{int a=100,b,m,n,i,j,z,y,D=0,R,Z,N;int p[][][];Scanner in;Runtime rt;int[][]r;int pp;int dd;int[][]bdr;int ww;int[][]bwr;int[][]faf;int ff;boolean ffOn;public static void main(String[]a){(new ZombieHordeMin()).pR();}ZombieHordeMin(){in=new Scanner(System.in);rt=Runtime.getRuntime();m=in.nextInt();N=in.nextInt();p=new int[m+1][m+1][N+1];int[]o=new int[m+1];for(b=0;b<N;b++){i=in.nextInt();j=in.nextInt();z=in.nextInt();o[i]++;o[j]++;D=(o[i]>D?o[i]:D);p[i][j][++p[i][j][0]]=z;if(i!=j)p[j][i][++p[j][i][0]]=z;D=(o[j]>D?o[j]:D);}m++;}void pR(){r=new int[5000][m+3];r[0][0]=a;Arrays.fill(r[0],1,m,1);r[0][m]=1;r[0][m+1]=0;r[0][m+2]=0;ww=-1;pp=dd=0;pR(5000);}void pR(int aMD){faf=new int[D][];ff=0;ffOn=true;for(int mD=1;mD<=aMD;mD++){System.out.printf("Checking len %d\n",mD);int k=ffR(0,mD);if(ww>-1){System.out.printf("%d x\n",ww+1);for(int win=0;win<=ww;win++)System.out.printf(" %d:%d,%d-%d",win,bwr[win][0],bwr[win][1],bwr[win][2]);System.out.println();break;}if(k>0){System.out.printf("dead max %d kills, %d steps\n",pp,dd+1);for(int die=0;die<=dd;die++)System.out.printf(" %d:%d,%d-%d",die,bdr[die][0],bdr[die][1],bdr[die][2]);System.out.println();break;}}}int ffR(int dP,int mD){if(ff==0)return pR(dP,mD);int kk=0;int fm=ff;if(ffOn&&D*fm>rt.maxMemory()/(faf[0][0]*8+12))ffOn=false;int[][]fmv=faf;if(ffOn){faf=new int[D*fm][];ff=0;}for(int df=0;df<fm;df++){dS(fmv[df]);kk+=pR(fmv[df][0],mD);}fmv=null;rt.gc();return kk==fm?1:0;}int pR(int dP,int mD){if(dP==mD)return 0;int rT=0;int dC=0;int src=r[dP][m];int sa=r[dP][0];for(int dt=1;dt<m;dt++){for(int rut=1;rut<=p[src][dt][0];rut++){rT++;r[dP+1][0]=sa-p[src][dt][rut]+r[dP][dt];for(int cp=1;cp<m;cp++)r[dP+1][cp]=(dt==cp?1:r[dP][cp]+1);r[dP+1][m]=dt;r[dP+1][m+1]=rut;r[dP+1][m+2]=r[dP][m+2]+p[src][dt][rut];if(sa-p[src][dt][rut]<1){dC++;if(pp<r[dP][m+2]+sa){pp=r[dP][m+2]+sa;dd=dP+1;bdr=new int[dP+2][3];for(int cp=0;cp<=dP+1;cp++){bdr[cp][0]=r[cp][m];bdr[cp][1]=r[cp][m+1];bdr[cp][2]=r[cp][0];}}}else{for(int chk=0;chk<=dP;chk++){if(r[chk][m]==dt){int fR=chk+1;for(int cM=0;cM<m+3;cM++)r[dP+2][cM]=r[dP+1][cM];for(;fR<=dP+1;fR++){r[dP+2][0]=r[dP+2][0]-p[r[dP+2][m]][r[fR][m]][r[fR][m+1]]+r[dP+2][r[fR][m]];for(int cp=1;cp<m;cp++)r[dP+2][cp]=(r[fR][m]==cp?1:r[dP+2][cp]+1);r[dP+2][m+2]=r[dP+2][m+2]+p[r[dP+2][m]][r[fR][m]][r[fR][m+1]];r[dP+2][m]=r[fR][m];r[dP+2][m+1]=r[fR][m+1];}if(fR==dP+2&&r[dP+2][0]>=r[dP+1][0]){ww=dP+1;bwr=new int[dP+2][3];for(int cp=0;cp<dP+2;cp++){bwr[cp][0]=r[cp][m];bwr[cp][1]=r[cp][m+1];bwr[cp][2]=r[cp][0];}return 0;}}}dC+=pR(dP+1,mD);if(ww>-1)return 0;}for(int cp=0;cp<m+3;cp++)r[dP+1][cp]=0;}}if(rT==dC)return 1;else{if(ffOn&&dP==mD-1)faf[ff++]=cP(dP);return 0;}}int[]cP(int dP){int[]cmp=new int[dP*2+3];cmp[0]=dP;cmp[dP*2+1]=r[dP][0];cmp[dP*2+2]=r[dP][m+2];for(int zip=1;zip<=dP;zip++){cmp[zip]=r[zip][m];cmp[dP+zip]=r[zip][m+1];}return cmp;}void dS(int[]cmp){int[]lv=new int[m];int dP=cmp[0];r[dP][0]=cmp[dP*2+1];r[dP][m+2]=cmp[dP*2+2];r[0][0]=100;r[0][m]=1;for(int dp=1;dp<=dP;dp++){r[dp][m]=cmp[dp];r[dp][m+1]=cmp[dP+dp];r[dp-1][cmp[dp]]=dp-lv[cmp[dp]];r[dp][m+2]=r[dp-1][m+2]+p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];r[dp][0]=r[dp-1][0]+r[dp-1][cmp[dp]]-p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];lv[cmp[dp]]=dp;}for(int am=1;am<m;am++)r[dP][am]=(am==cmp[dP]?1:dP-lv[am]+1);}}

```

Get the code from github here, to track any changes I make. Here are some other maps I used.

### Output example

Example output for reference solution:

```
    $ java -d64 -Xmx3G ZombieHordeMin > reference_route_corrected_min.out
    5 6 1 2 4 2 3 4 3 1 4 2 4 10 2 5 10 1 1 50
    Checking len 1
    Checking len 2
    Checking len 3
    Checking len 4
    Checking len 5
    Checking len 6
    Checking len 7
    Checking len 8
    Checking len 9
    Checking len 10
    Checking len 11
    Checking len 12
    Checking len 13
    Checking len 14
    Checking len 15
    Checking len 16
    Checking len 17
    Checking len 18
    Checking len 19
    Checking len 20
    Checking len 21
    Checking len 22
    Checking len 23
    Checking len 24
    25 x
     0:1,0-100 1:3,1-97 2:1,1-95 3:2,1-94 4:5,1-88 5:2,1-80 6:4,1-76 7:2,1-68 8:1,1-70 9:2,1-68 10:1,1-66 11:2,1-64 12:1,1-62 13:2,1-60 14:1,1-58 15:2,1-56 16:1,1-54 17:2,1-52 18:1,1-50 19:2,1-48 20:1,1-46 21:2,1-44 22:1,1-42 23:2,1-40 24:1,1-38

```

Read the route output like this: `step`:`source`,`route-to-get-here`-`ammo`. So in the above solution, you would read it as:

* At step `0`, at outpost `1` with ammo `100`.
* At step `1`, use route `1` to get to outpost `3` with ending ammo `97`
* At step `2`, use route `1` to get to outpost `1` with ending ammo `95`
* ...

### Closing notes

So, I hope I've made my solution harder to beat, but PLEASE TRY! Use it against me, add in some parallel processing, better graph theory, etc. A couple of things I figure could improve *this* approach:

* aggressively "reduce" loops to cut out needless retread as the algorithm progresses.
    + An example: in the example problem, consider the loops 1-2-3 and other permutations as "one step", so that we can make our way to end-cycle more quickly.
    + E.g. if you are at node 1, you can either (a) go to 2, (b) go to 1, (c) go through 1-2-3 as one step and so on. This would allow a solved to fold depth into breadth, increasing the number of routes at a particular depth but greatly speeding time-to-solution for long cycles.
* cull dead routes. My current solution doesn't "remember" that a particular route is dead-ended, and has to rediscover it every time. It would be better to keep track of the earliest moment in a route that death is certain, and never progress beyond it. did this...
* if careful, you could apply the dead route culling as a sub-route cull. By example, if 1-2-3-4 always results in death, and the solver is about to test the route 1-3-1-2-3-4, it should immediately stop descending that path as it is guaranteed to end in disappointment. It would still be possible to calculate # of kills, with some careful math.
* Any other solution that trades memory for time, or allows aggressive avoidance of following dead-end routes. did this too!
> 14 votes

# Answer
# Some abstract notes on a solution

*If I get time I'll convert this into an algorithm...*

For a given graph `G` then there exists a connected sub-graph `G'` which contains town `1`. If there is an infinite solution then there will exist a connected sub-graph `G''` of `G'` which contains `V` towns and `P` paths.

The paths `P` of `G''` can be partitioned such that `{p}` contains a path which has then minimal cost of all the paths in `P` and `P/{p}` is all the other paths (forming a spanning tree or possibly a cycle). If we assume that `p` is not a looping edge (connecting both ends to the same town) then it will connect two towns (`v1` and `v2`) and has cost `c` ammunition then you (the survivor) can then traverse from `v1` to `v2` and back at a total cost of `2c` ammunition and this will increase the ammunition in all the towns by 2 (for a total increase of `2|V|` within `G''` \- some of which will have been collected from `v1` and `v2`).

If you travel from `v1` to `v2` and back to `v1` multiple (`m`) times and then take a trip from `v1` along the edges `P/{p}` to visit all the towns other than `v1` and `v2` before returning to `v1` and this takes `n` paths to achieve (where `|P/{p}| ≤ n ≤ 2|P/{p}|` since you should never need to traverse a path more than twice) with a cost of `k` and the towns will gain `2m|V|` ammunition (again some of which will have been collected during traversal).

Given all this then you can tell if an infinite solution is potentially possible if then cost `k + 2mc` is equal or lower than the total reward `2(m+n)|V|`.

There is a additional complexity to the problem in that:

* you may need to travel from the starting town `1` to `{p}` on the first iteration and need to factor in this cost; and
* you also need to ensure that the `m` and `n` are low enough that you don't run out of ammunition before you can make it through the first iteration since the first iteration will have a higher cost than the subsequent iterations).

This leads to a 24 path cost neutral solution to the example in the question (the numbers are the towns visited):

```
1,3,1,3,1,3,1,3,1,3,1,3,1,3,1,3,1,3,2,4,2,5,2,3, ... and repeat ...

```
> 2 votes

---
Tags: code-golf
---


title: Protect my walls from these pesky doors

text:
# Question
Title: Protect my walls from these pesky doors
Doorknobs are great and all, but when you open a door, it always dents the walls around it. I need you to take input of ASCII art of a room, like this:

```
+---------+--X  --X    --+-----+
|       \     \   |\     |   \ |
|        \     \  | \    |    \|
|         X       |  \   |     X
|      /  |       |   \  X
|     /   |     \       /
|    /    |      \     /       |
+---X   --+-------X------+-----+

```

And output the room with doorstops, like this:

```
+---------+--X  --X    --+-----+
|       \  .  \   |\     |   \.|
|        \     \  | \   .|    \|
|         X       |  \   |     X
|      /  |       |.  \  X
|     /  .|     \       /
|.   /    |     .\     /       |
+---X   --+-------X------+-----+

```

Specification:

* The ASCII room (input) will consist of `+`, `-`, and `|`. These characters are purely cosmetic; they could all be `+`s but that would look horrible. It will also contain hinges (`X`) and doors (`/` or `\`).
* Doors are made up of `/` or `\`. Starting from the "hinge" character, which is `X`, they will go directly diagonally (change of 1 in `x` and 1 in `y`) for 2 or more units (characters).
* To find where to put the doorstop for a door (there is always only one doorstop per door), find the doorway for the door. The doorway will always start at one hinge, and go the same amount of spaces as the door's length up, down, left, or right from there. The next space after that will always be a wall. For example, in this door, the doorway is marked by `D`s:

```
   \
    \
---DDX-----

```

One the doorway is found, find out whether you need to go clockwise or counterclockwise to reach the door. For example, in that example door above, you have to go clockwise, and in this one, you must go counterclockwise:

```
   \ <-
    \  )
-----X  ---

```

Once you know which way to go, keep going that way (ignoring the door) until you reach a wall.

Here's a visualization of that for the example door above:

The blue is the doorway, the orange is finding that you must go clockwise, and the red is continuing to go clockwise until a wall is reached.

Once you reach a wall, go (the door's length) spaces from the hinge (`X`) on that wall, move one space away from the wall towards the door (so you don't place the doorstop right on the wall), and insert a `.` there. Here's the same example door showing how the doorstop is placed:

```
   \
    \  .
---DDX12---

```

Repeat for every door, and output the result! Use the example input at the top of this post as a test case to check if your program is valid.

Note that you do not have to handle doors that don't fit on their walls, such as:

```
|     /
|    /
|   /
|  /
+-X    --

```

Or:

```
     /
    /
   /
+-X   --
|
|

```
* This is , so the shortest code in bytes will win.

# Answer
> 4 votes
## Scala, 860 bytes

**Golfed**:

```
    object D extends App{val s=args(0)split("\n")
    val r=Seq(P(1,0),P(1,-1),P(0,-1),P(-1,-1),P(-1,0),P(-1,1),P(0,1),P(1,1))
    var m=r(0)
    val e=s.map(_.toCharArray)
    case class P(x:Int,y:Int){def u=x==0||h
    def h=y==0
    def p(o:P)=P(x+o.x,y+o.y)
    def o="\\/".contains(c)
    def w="-|+".contains(c)
    def c=try s(y)(x) catch {case _=>'E'}
    def n=r.filter(!_.u).map(d => d.j(p(d))).sum
    def j(t:P):Int=if(t.o)1+j(p(t))else 0
    def q=if(c=='X'){m=this
    r.filter(_.u).map{d=>if(p(d).c==' '&&p(P(d.x*(n+1),d.y*(n+1))).w)d.i}}
    def i:Unit=Seq(r++r,(r++r).reverse).map(l=>l.drop(l.indexOf(this)+1)).map(_.take(4)).filter(_.exists(a=>a.p(m)o))(0).grouped(2).foreach{p=>if(p(1)p(m)w){p(0)add;return}}
    def add=if(r.filter(_.h).map(p(_)p(m)).exists(_.w))e(y*m.n+m.y)(x+m.x)='.'else e(y+m.y)(x*m.n+m.x)='.'}
    val f=args(0).size
    Array.tabulate(f,f){(i,j)=>P(i,j)q}
    e.map(_.mkString).map(println)}

```

**Un-golfed**:

```
    object DoorknobCleanVersion extends App {
            val s = args(0) split ("\n")

            val r = Seq(P(1, 0), P(1, -1), P(0, -1), P(-1, -1), P(-1, 0), P(-1, 1), P(0, 1), P(1, 1))
            val HorizontalDirections = r.filter(_.isHorizontal)

            var hinge = r(0)
            val result = s.map(_.toCharArray)

            type I = Int
            case class P(x: Int, y: Int) {
                    def isCardinal = x == 0 || isHorizontal
                    def isHorizontal = y == 0

                    override def toString = x + "," + y

                    def p(o: P) = P(x + o.x, y + o.y)

                    def isDoor = Seq('\\', '/').contains(charAt)
                    def isWall = Seq('-', '|', '+').contains(charAt)

                    def charAt = try s(y)(x) catch { case _ => 'E' }

                    def doorLength = r.filter(!_.isCardinal).map(d => d.recursion2(p(d))).sum

                    def recursion2(currentPosition: P): Int =
                            if (currentPosition.isDoor)
                                    1 + recursion2(p(currentPosition))
                            else
                                    0

                    def findDoorway =
                            if (charAt == 'X') {
                                    hinge = this
                                    r.filter(_.isCardinal).map { d =>
                                            if (p(d).charAt == ' ' && p(P(d.x * (doorLength + 1), d.y * (doorLength + 1))).isWall)
                                                    d.getCorrectRotation2
                                    }
                            }

                    def getCorrectRotation2: Unit = Seq(r ++ r, (r ++ r).reverse).map(l => l.drop(l.indexOf(this) + 1))
                            .map(_.take(4))
                            .filter(_.exists(a => a.p(hinge)isDoor))(0)
                            .grouped(2)
                            .foreach {
                                    p =>
                                            if (p(1) p (hinge)isWall) {
                                                    p(0)add;
                                                    return
                                            }
                            }

                    def add =
                            if (HorizontalDirections.map(p(_) p (hinge)).exists(_.isWall))
                                    result(y * hinge.doorLength + hinge.y)(x + hinge.x) = '.'
                            else
                                    result(y + hinge.y)(x * hinge.doorLength + hinge.x) = '.'

            }

            val size = args(0).size
            Array.tabulate(size, size) { (i, j) => P(i, j).findDoorway }

            result.map(_.mkString).map(println)
    }

```

Using OOP was definitely the wrong approach here, in hindsight. If I could do it again I would definitely go with a bunch of hardcoded truth tables.

---
Tags: code-golf
---