# Question
Title: Count digits in a string, check if there its a fibonnaci number
* There's a question with a comment with some code thats far too long.
* For a site that has counting fetish, this code just seems so wrong.
* Solve this meta-riddle, and explain it with a rhyme.
* Winner is the shortest code in a fortnights time.

The challenge:

1. Open a file as input.
2. Count and output the number of digits `(0,1,...9)` and non-digits (everything else).
3. If the number of digits and non-digits are consecutive fibonnacci numbers, with the number of digits is fibonnacci number `f(n)` and the number of non-digits is `f(n-1)` the file is "valid", otherwise it is "Invalid"
4. Output this information as exactly as shown below.

Example 1:

```
Digits: 34 Nondigits: 21
Valid program

```

Example 2:

```
Digits: 33 Nondigits: 21
Invalid program

```

# Answer
## Ruby, 151

```
d=[0,0];$<.read.chars{|c|d[c>?/&&c<?:?0:1]+=1};puts"Digits: %d Nondigits: %d"%d
a=b=1;while b<d[0];b=a+a=b end;print ([b,a]==d)??V:"Inv","alid program"

```
> 2 votes

# Answer
# Java - 334

```
import java.nio.*;public class a{public static void main(String[]i)throws Exception{String s=new String(Files.readAllBytes(Paths.get(i[0])));int l=s.replaceAll("\\d","").length(),L=s.length()-l,a=1,b=2,c,d=0;while(a<L){if(a==l&&b==L)d=1;c=b;b+=a;a=c;}System.out.printf("Digits: %s Nondigits: %s\n%salid Program",L,l,d==0?"Inv":"V");}}

```

Ungolfed:

```
import java.nio.file.*;

public class Testing {

    public static void main(String[] i) throws Exception {
        String s = new String(Files.readAllBytes(Paths.get(i[0])));
        int l = s.replaceAll("\\d", "").length(), L = s.length() - l, a = 1, b = 2, c, d = 0;
        while (a < L) {
            if (a == l && b == L) {
                d = 1;
            }
            c = b;
            b += a;
            a = c;
        }
        System.out.printf("Digits: %s Nondigits: %s\n%salid Program", L, l, d == 0 ? "Inv" : "V");
    }
}

```

Explanation:

> Reads the input from the file
>
> supplied by command line
>
> Puts the contents in a String
>
> oh no! I'm thinking of quines.
>
> Regex swaps digits of that thing
>
> for the one and only empty String.
>
> Then by `String#length()` I find
>
> the charcount nondigit, yes that kind.
>
> From the length of the first String
>
> I subtract the charcount nondigit thing
>
> to find the char digits count.
>
> Next I sweep it all under the rug
>
> so I can say "Help I'm a bug!".
>
> Then I retrieve it - please have patience.
>
> Now the first terms of the Fibonacci sequence
>
> used to find the rest of the numbers.
>
> What to rhyme with? I'll just use "others".
>
> And when small num is greater than non-digits
>
> I know if it's true, so wait a minute.
>
> Uses `printf` to format output.
>
> `"alid Program"` at the start puts
>
> `"Inv"` or `"V"` according to the answer
>
> Before is the counts, not one thing fancier
>
> Thank you for lis'ning to this tale
>
> Of the program that validates according to your rules

---

Whew, it was hard to write that.

I decided to assume the input is from the command line, in the form of a String. Please correct me, because if I can simply take a `File` as input, I can shorten this by a few chars. Also, I'd like to know if a method is okay.
> 2 votes

# Answer
## Bash, 244

```
f=`cat $1`&&d=`sed 's/[0-9]*//g' $1`&&echo Digits: ${#d} Nondigits: $[${#f}-${#d}]]
a=1&&b=1&&while [ $b -lt ${#d} ];do z=$b&&b=$[a+b]&&a=$z;done&&if [ $b -eq ${#d} -a $a -eq $[${#f}-${#d}] ];then echo Valid program;else echo Invalid program;fi

```

call using `./script filename`.

I'm not particularly good with bash and I'm sure there are a few ways to get this smaller.
> 0 votes

---
Tags: code-golf, metagolf
---


title: Meta regex golf

text:
# Question
Title: Meta regex golf
In the spirit of this xkcd

Write a program that plays regex golf with arbitrary pairs of lists. The program should at least attempt to make the regex short, a program that just outputs `/^(item1|item2|item3|item4)$/` or similar is not allowed.

Scoring is based on the ability to generate the shortest regex. The test lists are those of successful and unsuccessful US presidential candidates, found here (thanks @Peter). Of course, the program must work for all disjoint lists, so simply returning an answer for the president one doesn't count.

# Answer
# Perl (~~111~~ ~~110~~ 122 characters)

```
use Regexp::Assemble;@ARGV=shift;my$r=new Regexp::Assemble;chomp,add$r "^\Q$_\E\$"while<>;$_=as_string$r;s/\(\?:/(/g;print

```

This uses CPAN module called `Regexp::Assemble` in order to optimize the regular expressions. Because what is the better language for regular expressions then Perl.

Also, readable version, just for fun (made with help of `-MO=Deparse`).

```
use Regexp::Assemble;
my $r = Regexp::Assemble->new;
while (<>) {
    chomp($_);
    $r->add("^\Q$_\E\$");
}
$_ = $r->as_string;
# Replace wasteful (?:, even if it's technically correct.
s/\(\?:/(/g;
print $_;

```

Sample output (I did CTRL-D after `item4`).

```
$ perl assemble.pl
item1
atem2
item3
item4
^(item[134]|atem2)$

```

Also, as a bonus, I'm writing the regex for every word in the question.

```
^(a((ttemp)?t|llowed\.|rbitrary)?|\/\^item1\|atem2\|item3\|item4\$\/|s(ho(rt,|uld)|imilar)|p((air|lay)s|rogram)|(Writ|mak|Th)e|l(ists\.|east)|o([fr]|utputs)|t(h(at|e)|o)|(jus|no)t|regex|golf|with|is)$

```

Also, list of presidents (262 bytes).

```
^(((J(effer|ack|ohn)s|W(ashingt|ils)|Nix)o|Van Bure|Lincol)n|C(l(eveland|inton)|oolidge|arter)|H(a(r(rison|ding)|yes)|oover)|M(cKinley|adison|onroe)|T(a(ylor|ft)|ruman)|R(oosevelt|eagan)|G(arfield|rant)|Bu(chanan|sh)|P(ierce|olk)|Eisenhower|Kennedy|Adams|Obama)$

```
> 8 votes

# Answer
*Not* my solution (obviously I'm not peter norvig!) but here's a solution of the (slightly modified) question courtesy of him: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb

the program he gives is as follows (his work, not mine):

```
def findregex(winners, losers):
    "Find a regex that matches all winners but no losers (sets of strings)."
    # Make a pool of candidate components, then pick from them to cover winners.
    # On each iteration, add the best component to 'cover'; finally disjoin them together.
    pool = candidate_components(winners, losers)
    cover = []
    while winners:
        best = max(pool, key=lambda c: 3*len(matches(c, winners)) - len(c))
        cover.append(best)
        pool.remove(best)
        winners = winners - matches(best, winners)
    return '|'.join(cover)

def candidate_components(winners, losers):
    "Return components, c, that match at least one winner, w, but no loser."
    parts = set(mappend(dotify, mappend(subparts, winners)))
    wholes = {'^'+winner+'$' for winner in winners}
    return wholes | {p for p in parts if not matches(p, losers)}

def mappend(function, *sequences):
    """Map the function over the arguments.  Each result should be a sequence.
    Append all the results together into one big list."""
    results = map(function, *sequences)
    return [item for result in results for item in result]

def subparts(word):
    "Return a set of subparts of word, consecutive characters up to length 4, plus the whole word."
    return set(word[i:i+n] for i in range(len(word)) for n in (1, 2, 3, 4))

def dotify(part):
    "Return all ways to replace a subset of chars in part with '.'."
    if part == '':
        return {''}
    else:
        return {c+rest for rest in dotify(part[1:]) for c in ('.', part[0]) }

def matches(regex, strings):
    "Return a set of all the strings that are matched by regex."
    return {s for s in strings if re.search(regex, s)}

answer = findregex(winners, losers)
answer
# 'a.a|i..n|j|li|a.t|a..i|bu|oo|n.e|ay.|tr|rc|po|ls|oe|e.a'

```

where winners and losers are the winners and losers lists respectively (or any 2 lists of course) see the article for detailed explanations.
> 4 votes

# Answer
My solution written in Factor:

```
USING:
    formatting fry
    grouping
    kernel
    math math.combinatorics math.ranges
    pcre
    sequences sets ;
IN: xkcd1313

: name-set ( str -- set )
    "\\s" split members ;

: winners ( -- set )
    "washington adams jefferson jefferson madison madison monroe
monroe adams jackson jackson vanburen harrison polk taylor pierce buchanan
lincoln lincoln grant grant hayes garfield cleveland harrison cleveland     mckinley
 mckinley roosevelt taft wilson wilson harding coolidge hoover roosevelt
roosevelt roosevelt roosevelt truman eisenhower eisenhower kennedy johnson     nixon
nixon carter reagan reagan bush clinton clinton bush bush obama obama" name-set ;

: losers ( -- set )
    "clinton jefferson adams pinckney pinckney clinton king adams
jackson adams clay vanburen vanburen clay cass scott fremont breckinridge
mcclellan seymour greeley tilden hancock blaine cleveland harrison bryan bryan
parker bryan roosevelt hughes cox davis smith hoover landon wilkie dewey dewey
stevenson stevenson nixon goldwater humphrey mcgovern ford carter mondale
dukakis bush dole gore kerry mccain romney" name-set winners diff
    { "fremont" } diff "fillmore" suffix ;

: matches ( seq regex -- seq' )
    '[ _ findall empty? not ] filter ;

: mconcat ( seq quot -- set )
    map concat members ; inline

: dotify ( str -- seq )
    { t f } over length selections [ [ CHAR: . rot ? ] "" 2map-as ] with map ;

: subparts ( str -- seq )
    1 4 [a,b] [ clump ] with mconcat ;

: candidate-components ( winners losers -- seq )
    [
        [ [ "^%s$" sprintf ] map ]
        [ [ subparts ] mconcat [ dotify ] mconcat ] bi append
    ] dip swap [ matches empty? ] with filter ;

: find-cover ( winners candidates -- cover )
    swap [ drop { } ] [
        2dup '[ _ over matches length 3 * swap length - ] supremum-by [
            [ dupd matches diff ] [ rot remove ] bi find-cover
        ] keep prefix
    ] if-empty ;

: find-regex ( winners losers -- regex )
    dupd candidate-components find-cover "|" join ;

: verify ( winners losers regex -- ? )
    swap over [
        dupd matches diff "Error: should match but did not: %s\n"
    ] [
        matches "Error: should not match but did: %s\n"
    ] 2bi* [
        dupd '[ ", " join _ printf ] unless-empty empty?
    ] 2bi@ and ;

: print-stats ( legend winners regex -- )
    dup length rot "|" join length over /
    "separating %s: '%s' (%d chars %.1f ratio)\n" printf ;

: (find-both) ( winners losers legend -- )
    -rot 2dup find-regex [ verify t assert= ] 3keep nip print-stats ;

: find-both ( winners losers -- )
    [ "1 from 2" (find-both) ] [ swap "2 from 1" (find-both) ] 2bi ;

IN: scratchpad winners losers find-both
separating 1 from 2: 'a.a|a..i|j|li|a.t|i..n|bu|oo|ay.|n.e|ma|oe|po|rc|ls|l.v' (55 chars 4.8 ratio)
separating 2 from 1: 'go|e..y|br|cc|hu|do|k.e|.mo|o.d|s..t|ss|ti|oc|bl|pa|ox|av|st|du|om|cla|k..g' (75 chars 3.3 ratio)

```

It's the same algorithm as Norvig's. If hurting readability is the goal then you can probably golf away many more characters.
> 2 votes

# Answer
My code is not in a very golf-ish and condensed fashion, but you can check it at https://github.com/amitayd/regexp-golf-coffeescript/ (or specifically the algorithm at src/regexpGolf.coffee).

It's based on Peter Norvig's algorithm, with two improvements:

1. Create parts to use with character sets (i.e. use \[ab\]z, \[ac\]z, and \[bc\]z if valid parts are az, bz and cz).
2. Allow to construct "top optimal paths" of covers, and not just a cover made of the best candidate at each iteration.

(And also threw in an optional randomness)

For the sets of winners/losers in this quiz I found a 76 chars regex using it:

```
[Jisn]e..|[dcih]..o|[AaG].a|[sro].i|T[ar]|[PHx]o|V|[oy]e|lev|sh$|u.e|rte|nle

```

Some more details in my blog post about porting the solver to coffeescript.
> 1 votes

---
Tags: regular-expression, metagolf
---


title: Sourcecode combinatorics

text:
# Question
Title: Sourcecode combinatorics
Objective:

> The task is to create two programs using the same or different programming languages. The sourcecodes will be combined in two different ways and the resulting sourcecodes can be in any programming languages. The four programs (original two + the two combinations) should output different things.

Rules:

1. Your programs (all four) should not take any input (from user, filename, network or anything).
2. The first program should output exactly `Hello`, nothing else.
3. The second program should output exactly `world`, nothing else.
4. The first combinated program should output `Hello human!`, nothing else.
5. The second combinated program should output `Hello computer!`, nothing else.

Here is how the two combinated programs may be created:

**First combined program**:

* Choose **two** numbers (equal or different) between 1 and 6 (that is: 2, 3, 4 or 5), the two numbers are called: `n1` and `n2`.
* Copy `n1` number of characters from the first program and paste into the combined sourcecode
* Copy `n1` number of characters from the second program and paste into the combined sourcecode
* Copy `n2` number of characters from the first program and paste into the combined sourcecode
* Copy `n2` number of characters from the second program and paste into the combined sourcecode
* Next, start over copy `n1` number of characters again and so on. Copy from start to end from the sourcecodes, paste from start to end into the combined sourcecode.

**Second combined program**:

* The sourcecode is the reverse of the first combined program sourcecode above. You may replace up to 3 characters at any place afterwards (optional). You can replace the up to 3 characters with any other characters. Replacing means 1 char for 1 char at up to 3 different positions on the sourcecode. The final sourcecode size in characters should therefor be exactly the same size as the first combined program size.

**Example** creating the combinated programs using numbers 3 and 4:

```
            First program:    {'Hello'}:p
           Second program:    /*         */ console.log ("World");
 First combinated program:    {'H/* ello    '}:   */ console.log ("World");
Second combinated program:    ;)"dlroW"( gol.elosnoc /*   :}'    olle */H'}

```

Be sure to declare all four programming languages that you use (even if they are all the same) and what numbers you have used when creating the first combinated sourcecode.

This is code-golf, shortest code in bytes for the two sourcecodes wins! Good luck, have fun!

# Answer
## Befunge-98 × 4, 69 chars

Following @user12551's lead, I went with 4× Befunge (although -98 rather than -93). Program code is reversed on byte-level, line ending is `LF`, program #1 has no terminating newline.

**Program 1**:

```
"!namolleH"4k,@

```

**Program 2**:

```
"vdlrow"4k,@
      >"uh olleH"bk,@,ke"Hello computer!"

```

**Combined 1** (*n₁ = 5*, *n₂ = 2*):

```
"!nam"volleHdl"4k,@row"4k,@
      >"uh olleH"bk,@,ke"Hello computer!"

```

**Combined 2** (has a bunch of trailing spaces):

```
"!retupmoc olleH"ek,@,kb"Hello hu">
@,k4"wor@,k4"ldHellov"man!"

```
> 1 votes

# Answer
### Befunge-93 x4; n1=5, n2=5; 100 75 chars

I put the 4 programs into 1 file for debugging: (it outputs a random one of the four programs)

```
 vv  |2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|23
>??#@"oll""eH"   >:#0#,_ @    #
     |2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|23
>? #@"dlr""ow"        >:#0#,_ @0"!namuh olleH">:#,_@#:>"Hello computer!"
     |2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|23
 > #@"oll""dlr""eH" "ow"   >:#     0#,_   >:#@    0#,_ #@0"!namuh olleH">:#,_@#:>"Hello computer!"
     |2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|2345|23
  >#@"!retupmoc olleH">:#,_@#:>"Hello human!"0@# _,#0    @#:>   _,#0     #:>   "wo" "He""rld""llo"

```

The separate programs are: (one per line)

```
"oll""eH"   >:#0#,_ @    #
"dlr""ow"        >:#0#,_ @0"!namuh olleH">:#,_@#:>"Hello computer!"
"oll""dlr""eH" "ow"   >:#     0#,_   >:#@    0#,_ #@0"!namuh olleH">:#,_@#:>"Hello computer!"
"!retupmoc olleH">:#,_@#:>"Hello human!"0@# _,#0    @#:>   _,#0     #:>   "wo" "He""rld""llo"

```

Edit: This time, I took advantage of the replacement rule and replaced two characters in the second combination.
> 2 votes

# Answer
## Windows Command script x4; n1=2; n2=2 - 92 Bytes

1st script (marked eol and eof):

```
 %: !rupc leoh %\r\n
 % eo llhun!% \r\n
 %echo Hello\eof

```

2nd script (marked eol and eof):

```
 %&&etmoolH ce %\r\n
 %chHeo ma% % \r\n
echo world%  \eof

```

Results in:

```
 % %: &&!retupmoc olleH ohce % %
 % % echo Hello human!% % %
 %ecechoho w Horelldlo%

```

And reversed:

```
 %oldlleroH w ohohcece%
 % % %!namuh olleH ohce % %
% % echo Hello computer!&& :% %

```
> 1 votes

---
Tags: code-golf
---


title: 9-hole mini-golf: Text Manipulation

text:
# Question
Title: 9-hole mini-golf: Text Manipulation
# 9-hole mini-golf: Description

* 9 (mostly fairly easy) code golfing challenges of varying difficulty
* Penalties for using the same language more than once
* All challenges about a specific theme (this theme: Text Manipulation)
* Input and output can be anywhere reasonable (i.e. STDIN and STDOUT, reading from/writing to a file, function argument and return value, etc.) but must NOT be hardcoded into the program
* Heavily inspired by 9 Hole Challenge and Text Mechanic

# Holes

1. ## Code-golf bag

Take two strings as input.
Output the first string's character count, while ignoring any occurence of any character in the second string.
Example: `f("foobarbaz", "ao")` =\> `5`
2. ## A pre-text for golfing

Take two strings as input.
Output the first string, with every line prefixed with the second.
Example: `f("foo\nbar\nbaz", "a")` =\> `"a foo\na bar\na baz"`
3. ## War of tabs vs spaces

Take a string `s`, a number `n`, and a boolean `b` (specified however you want) as input.
If `b` is true, output `s` with every tab converted to `n` spaces.
Else, output the `s` with every `n` spaces converted to tabs.
Example: `f("if (x) {\n\tdoStuff();\n}", 4, true)` =\> `"if (x) {\n[sp][sp][sp][sp]doStuff();\n}"` (`[sp]` means space)
4. ## Pillars of golf

Take a string `s`, a number `n`, and another number `m` as input.
Output `s` in columns of `n` lines each and `m` characters per column.
Also have padding of one space between the columns.
Example: `f("this is some placeholder text, foo bar baz...", 3, 5)` =\>

```
this  aceho  foo
is so lder  bar b
me pl text, az...

```
5. ## Friendly letters

Take a string `s` and a number `n` as input.
Output the most common group of `n` letters in `s`.
If there is a tie, output any or all of them.
Example: `f("abcdeabcfghiabc", 3)` =\> `"abc"`
6. ## Scrambled ~~eggs~~ letters for breakfast

Take a string as input.
Output the string with all of its words scrambled (letter order randomized) except their first and last letters.
For simplicity, assume that the input will be a list of "word"s, space separated (i.e. in `@$&_():;" foo bar`, `@$&_():;"` is considered a "word.")
Example: `f("this is a sentence that will be scrambled")` =\> `"tihs is a stcneene that wlil be sclamrbed"`
7. ## ASCIIfy

Take a string as input.
If the string only contains numbers and spaces, then replace the numbers with their respective ASCII characters (removing the spaces).
Else, do the reverse (characters to numbers).
Example: `f("ASCIIfy challenge")` =\> `"65 83 67 73 73 102 121 32 99 104 97 108 108 101 110 103 101"`
Example 2: `f("65 83 67 73 73 102 121 32 99 104 97 108 108 101 110 103 101")` =\> `"ASCIIfy challenge"`
8. ## Mini-mini-markdown transformation

Take a string as input.
Output the string converted with mini-markdown, as used in comments on Stack Exchange.
This is an even mini-er version: you only need to handle `**bold**`, `*italics*`, and ``code``.
You need not handle invalid nesting, like `**foo *bar** baz*`. Also assume that when you see a delimiter (`*` or ```), it will *always* mean to format (i.e. `te**st**ing` =\> `te<b>st</b>ing`, and `foo* bar *baz` =\> `foo<i> bar </i>baz`).
Example: `f("**foo** *bar **baz*** `qux`")` =\> `"<b>foo</b> <i>bar <b>baz</b></i> <code>qux</code>"`
9. ## Only the best characters

Take a string `s`, number `n`, and string `r` as input.
Output the `n`th character of each word in `s`. (0-indexed, words are space-separated).
If the length of the word is less than `n`, use `r` for that word instead.
Example: `f("this is a test sentence foo bar baz", 2, "-")` =\> `"i--snorz"`

# Scoring

Your score is the sum of the character counts of your programs. For every repeated language, multiply by 110%. For example, if you have three Ruby solutions, and the total character count of all of your solutions is 1000, your score is 1000 * 1.1 * 1.1 = 1210. Round down if you have a non-integer score.

# Good luck!

# Answer
> 12 votes
# Score: 382 * 1.1<sup>2</sup> = 462

Languages prone to change.

## 1. APL, ~~8~~ 4

Thanks @marinus for shaving 4 chars off.

```
f←⍴~

```

Called with the strings as the left and right arguments, eg.

```
      'foobarbaz' f 'ao'
5

```

## 2. Ruby, ~~35~~ 31

Thanks @DoorknobofSnow for shaving 4 chars off.

```
f=->s,r{s.gsub(/(?<=^)/,r+' ')}

```

## 3. Python, 48

```
f=lambda s,n,b:s.replace(*['\t',' '*n][::2*b-1])

```

## 4. GolfScript, 20

```
{@//zip{' '*}%n*}:f;

```

Assumes that the arguments are on the stack. Test online

## 5. J, 50

```
f=:({~[:(i.>./)+/"1@=@(}.~0-1{$))@|:@([$~],1+[:$[)

```

Called with the string as the left argument and the number as the right, eg.

```
   'abcdeabcfghiabc' f 3
abc

```

## 6. Ruby, 61

```
f=->s{s.gsub(/(?<!^| )[^ ]+(?!$| )/){[*$&.chars].shuffle*''}}

```

## 7. GolfScript, ~~39~~ ~~35~~ 34

```
{[.10,' '*-{{}/]' '*}{~]''+}if}:f;

```

Again, assumes the argument is on the stack. Test online

## 8. Perl, 98

```
sub f{$_=@_[0];s!\*\*(.+?)\*\*!$1!g;s!\*(.+?)\*!$1!g;s!`(.+?)`!$1!g;$_}

```

## 9. Haskell, 36

```
f s n r=[(x++cycle r)!!n|x<-words s]

```

# Answer
> 4 votes
## Python - 697 × 1.1<sup>9</sup> ≈ 1644

Gee, I sure love lambdas.

**Note**: 3 and 5 were shamelessly copied from Volatility's answer, as I couldn't find a better alternative. Also, this was done *just for fun*.

```
f=lambda a,b:sum([x not in b for x in a])        # 1, 41 chars
f=lambda a,b:b+' '+a.replace('\n','\n'+b+' ')    # 2, 43 chars
f=lambda s,n,b:s.replace(*['\t',' '*n][::b*2-1]) # 3, 47 chars
f=lambda s,n,m:'\n'.join([' '.join([s[x:x+m]for x in range(y*m,len(s),m*n)])for y in range(n)])
                                                 # 4, 94 chars
f=lambda s,n:max([s[x:x+n]for x in range(len(s)+1-n)],key=s.count)
                                                 # 5, 66 chars
import random;f=lambda s:' '.join([''.join(sorted(y,key=lambda*x:random.random()))for y in s.split()])
                                                 # 6, 102 chars
f=lambda s:s.replace(' ','').isdigit()and ''.join(map(chr,map(int,s.split())))or ' '.join(map(str,map(ord,s)))
                                                 # 7, 110 chars
import re;f=lambda s:re.sub('`(.*?)`','\\1',re.sub(r'\*(.*?)\*','\\1',re.sub(r'\*\*(.*?)\*\*','\\1',s)))
                                                 # 8, 128 chars
f=lambda s,n,r:''.join([len(x)>n and x[n]or r for x in s.split()])
                                                 # 9, 66 chars

```

**EDIT**: Thanks to Volatility for the tips.

# Answer
> 1 votes
# Score 513 * 1.1<sup>5</sup> = 826

Took quite a beating by the same-language penalty. Solved most of these in Ruby just to finish them as fast as I could. Might change some languages later. Added a small recap/explanation on each answer.

# 1: Python (46)

```
f=lambda a,b:len([x for x in a if not x in b])

```

First, shorter answer in **Ruby 2.0 (30)** that gives more penalty and higher overall score:

```
p (gets.chars-gets.chars).size

```

# 2: Ruby 1.9+ (37)

Returns each line of `s` prefixed with `t`:

```
f=->s,t{s.split(?\n).map{|x|t+x}*?\n}

```

# 3: Ruby 1.9+ (48)

Returns `s` with tabs replaced by `n` spaces or vice versa, depending on `b`:

```
f=->s,n,b{r=[" "*n,?\t];b||r.reverse!;s.gsub *r}

```

# 4: Ruby 1.9+ (95)

Somebody shoot me.

```
f=->s,n,m{[*s.chars.each_slice(m).map{|w|w*''}.each_slice(s.size/m/n)].transpose.map{|w|w*' '}}

```

# 5: Ruby 1.9+ (58)

Returns most common run of `n` characters in `s`:

```
f=->s,n{(a=s.chars.each_slice(n)).max_by{|v|a.count v}*''}

```

# 6: J (47)

Scrambles the text somehow; Shamelessly stolen verbatim from marinus:

```
''[1!:2&4('\w(\w+)\w';,1)({~?~@#)rxapply 1!:1[3

```

# 7: Ruby (57+1)

Prints input ASCIIfied or de-ASCIIfied. Run with the `-p` switch.

```
~/\d/?gsub(/\d+\s*/){$&.to_i.chr}:gsub(/./){"#{$&.ord} "}

```

# 8: Sed (87)

Prints input converted from (mini)markdown to HTML:

```
s:\*\*([^*]+)\*\*:\1:g;
s:\*([^*]+)\*:\1:g;
s:`([^`]+)`:\1:g

```

# 9 Ruby 1.9+ (37)

Returns a string of the `n`th characters of each first word in `s`, or `r`:

```
f=->s,n,r{s.split.map{|w|w[n]||r}*''}

```

# Answer
> 1 votes
Work in progress

## 1. Java - 66

```
int f(String s,String b){for(char c:b)s=s.replace(b,"");return s;}

```

## 2. Java - 64

```
String f(String i,String r){return i.replaceAll("(?m)^",r+" ");}

```

## 3. Python - 58

```
def f(s,n,b):t=" "*n;a=t,'\t';print s.replace(a[b],a[b^1])

```

## 4. Python - 84

```
def f(s,n,m):
 a=['']*n;c=0
 while s:a[c%n]+=s[:m]+" ";s=s[m:];c+=1
 for i in a:print i

```

## 5.

## 6.

## 7. Befunge 98 - 9

```
&,5j3.~@#

```

## 8.

## 9.

---
Tags: code-challenge, string, multiple-holes
---


# Question
Title: Find the largest prime under a number... but only for the test cases
**The Code**

Your program should take an input of *n \> 2* and output the largest prime less than or equal to *n*. You can choose how the number is input (standard input, read from a file, etc). For example:

```
Input  Output
3      3
9      7
28     23
486    479

```

Simple enough. And if a program passes all of the test cases it's gonna work fine, right?

**The Underhanded**

Too bad your program will *only* pass the test cases. It should work properly for 3, 9, 28, and 486 and no other numbers. Since this is an underhanded challenge, this shouldn't be obvious to a person glancing over the code.

Bonus points if the program still outputs something and if the output isn't obviously composite (getting 555 for 556 would be a little suspicious). This is a popularity contest, so the most popular answer wins. Which means the bonus points are completely meaningless. Oh well!

# Answer
# C

Results will be correct for the test cases, all others will be wrong for one or more reasons. The key is using the specifier `%g` which will round enough for the test cases but show the others as real numbers. Above inputs of 614, the results are all less than zero. Assuming inputs are in the integer domain!

```
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    // Convert input
    double x = atof(argv[1]);

    // Cubic prime determination function
    double y = -1.386269645E-5 * x * x * x + 7.572051723E-3 * x * x + 5.774239804E-1 * x + 1.199953896;

    // Print output, use %g because it guarantees the shortest output
    printf("First prime less than or equal to %g is %g - happy day.\n", x, y);

    // Done!
    return 0;
}

```

Sample output:

```
$ ./fake 2
First prime less than or equal to 2 is 2.38498 - happy day.
$ ./fake 3
First prime less than or equal to 3 is 3 - happy day.
$ ./fake 4
First prime less than or equal to 4 is 3.62992 - happy day.
$ ./fake 5
First prime less than or equal to 5 is 4.27464 - happy day.
$ ./fake 6
First prime less than or equal to 6 is 4.9341 - happy day.
$ ./fake 7
First prime less than or equal to 7 is 5.6082 - happy day.
$ ./fake 8
First prime less than or equal to 8 is 6.29686 - happy day.
$ ./fake 9
First prime less than or equal to 9 is 7 - happy day.
$ ./fake 28
First prime less than or equal to 28 is 23 - happy day.
$ ./fake 486
First prime less than or equal to 486 is 479 - happy day.

```
> 9 votes

# Answer
## Matlab

Not too much code, but I earn maximum bonus points. If it is not one of the specified numbers, the function will return the second maximum prime number. Added much nonsense to the code to make it seem like some advanced stuff is happening. ;)

```
function result=primesearch(input)

    %declare function output
    state = ones(input,1);

    %generate a random primeseed
    primeseed = ['FL_'-66 'l'+379 1]-1;
    primeseed=state*primeseed;

    for ii=1:input
        %calculate prime numbers using the primeseed
        state(ii)=ii*isprime(ii+primeseed(input,end));
    end

    %select the maximum prime number from the list
    primenumbers=state(state~=0);
    index=length(primenumbers)-1+ismember(input,primeseed);

    if (index>0)
        result = primenumbers(index);
    end

end

```
> 3 votes

# Answer
# Ruby

```
testcases = {
  3 => 3,
  9 => 7,
  28 => 23,
  486 => 479
}
testmode = 'test'
# different methods for different testmodes
def test # this is the only mode so far, but I made it extendable so that you can add more modes later
  "
  n=($$**$.)[0xFA64B3ED9^$$] # this will do very crucial stuff, leave it alone
  m=$_?0b11010:$$%n          # it's like that inverse square root thingy, just don't even try to understand
  [*n..m].step(n^m)[-1]      # if you're curious, it's some prime algorithm, I forgot which, but should be easy to look up
  ".inspect
end

largest_prime_under = ->s {
  testmode_result = eval testmode + '()`
  case s
  # special numbers where the algorithm does not work
  when -1.0/0..0
    return nil
  when 2
    return 2
  when 3
    return 3
  end
  eval_str = '.gsub(/#.*/m, "") # remove comments
              .gsub(/[^A-Za-z0-9]/m, "") # clean string of whitespace and other useless chars (like regex x mode)
             '
  testmode_result = eval `#{testmode_result}#{eval_str}'
  testmode_result[s]
}

testcases.each do |k, v|
  puts "largest prime under #{k} is #{v}, my function computed: #{largest_prime_under[k]}"
end

```

I have no time right now for an explanation, but I will add one soon ;)
> 2 votes

# Answer
## C

This one is mostly "proof by intimidation". Can you see how it works?

```
#include <stdint.h>
#include <stdio.h>

uint16_t m[] = { 131558, 196608, 262167, 327708, 393216,
                 458759, 524297, 589824, 655363, 720899,
                 786432, 864180, 917505, 983040, 998311 };

int find_prime(int n) {
  int i, r = 0xAF319C, M = 0x137715;
  for (i = 0; n % m[i]; i += 3) {
    r = (r * m[i + 1] + m[i + 2]) % M;
  }
  return r % M;
}

int main(void) {
  int input;
  while (scanf("%d", &input) != EOF) {
    printf("%d\n", find_prime(input));
  }
  return 0;
}

```

Sample run (input indented for clarity):

```
  1
12212
  2
12212
  3
3
  4
12212
  5
12212
  6
3
  7
12212
  8
12212
  9
7
  10
12212
  28
23
  486
479
  453
3
  454
12212

```
> 2 votes

# Answer
# q

`maxPrime:{$[x in"I"$0 1 2 4_string 0x0 sv"x"$0 59 241 166;(last where 0b,2=sum 0=x mod/:x:1+til x);((p-1) mod 2)+p:x-floor x%max(x%8;1)]}`

breaking it down, maxPrime is a conditional so it contains three statements.

"if"

* `x in "I"$0 1 2 4 cut string 0x0 sv "x" $0 59 241 166`

0 59 241 166 is the internal representation of the integer 3928486

_ ("cut") is a dyadic function that creates list subsets of a list by indices

english translation: "Is x in (3;9;28;486)?"

"then"

* `(last where 0b,2=sum 0=x mod/:x:1+til x)`

is a slightly modified version of listing primes up to n (#175 http://code.kx.com/wiki/Qidioms)

"else"

* `((p-1) mod 2)+p:x-floor x%max(x%8;1)`

takes the input - floor(input/max(input/8;1)) and adds 1 if even (so never obviously composite)
> 1 votes

# Answer
## Ruby

```
require 'prime'  # Cheating?
pri=Prime
m=2
input = File.open(__FILE__).readlines.take(5).map{|num| num.chop =~ /$/} # Read up to five test cases from the input file and trim trailing newlines. To run using this input style, for example, you could put four numbers into a file named "test", each on its own line, and then run "ruby -n largest_prime.rb test". The resulting output will likewise be separated by newlines, and will, for each number, be the largest prime less than that number n. For example, the output for n=9 is 7.
input&=[$_.to_i] # Str =>int

input.each do |num|
    raise "Number must be greater than #{m}" if num<m
    puts pri.to_a(num).last
end

```

Will output the correct answer for the test cases and nothing for anything else.
> 0 votes

# Answer
## TI-BASIC

```
{3,9,28,486->I:I-{0,2,3,9->O:LI-LO->LO:Input N:(LI=N)*LO->A:Disp cumSum(LA)

```

Note that `L` represents the list character and `->` represents the `STO->` arrow here.
> 0 votes

---
Tags: popularity-contest, underhanded
---


title: Blockbox that Hex?

text:
# Question
Title: Blockbox that Hex?
Write a program or a function in any programming language that takes a 6 digit hexadecimal input/argument. The input/argument can be 6 values or a 6 character string.

Your program should output an exactly 8 character wide rectangular block of characters containing only the hexadecimals supplied combined with spaces (+Linefeed). The rectangular block is a combination of smaller block shapes, one for each of the 6 supplied values.

Here follows 2 demostrative sample inputs and sample valid outputs:

Sample **input**:

```
"464fa6" or [4, 6, 4, 15, 10, 6]

```

One valid solution **output**:

```
44 66 ff
44 66 ff
   66 ff
aa     f
aaa ffff
aa  ffff
aaa
    6 44
66666 44

```

Sample **input**:

```
"35bf12"

```

One valid solution **output**:

```
55555 22

bbbbbbbb
b b b
      33
fffff  3
ff  ff
ffffff 1

```

*Rules:*

1. The output must be a rectangular shape
2. The output can be of any vertical height, but must be exactly 8 characters wide
3. The "inner blocks", refered to as the "block shape"s, cannot connect to any other block shape, the block shapes must be separated by a wall of blankspaces exactly 1 character wide horizontally, vertically and diagonally.
4. The wall of blankspaces cannot run parallell to the outer edges, only 1 character wide wall-edges can exist at the output edges. There should not exist any linked spaces anywhere on the outmost rectangle edge on the output.
5. The width of the wall of blankspaces should Not at any point exceed 1 character.
6. The inner block shapes should be uniform with the area of x characters, where x is the hexadecimal value supplied and the shape should consist of the charater x where x is the hexadecimal character representative.
7. The inner block shapes can be of any form as long as all of the shape characters connects vertically or horizontally, and does not valiating the rules for the wall of blankspaces.
8. The 6 block shapes can be placed in any internal "order" inside the outputted rectangle.
9. Valid input range: 1 ... 15 ("1" ... "f") for each shape. The input to your program should not contain any other information than the 6 hexadecimal numbers, and the input should not be sorted in any other way than in the samples before it is supplied to your program/function. Tell us what input format your solution uses (the input can not contain any other information than the hexadecimal values).
10. A inner block shape can be hollow. The hole should be of blankspace characters which counts as wall of blankspaces, meaning the hole in a hollow inner block shape cannot be more than 1 characters wide.

Three examples of valid hollow shapes:

```
aaa
a aaa
aaa

999
9 9
999
9

ffffff
f   ff
ffffff

```

One example of an invalid hollow shape:

```
ffffff
f   f
f   f
fffff

```

I assume that all input combinations is not possible to "solve" according to the rules above, therefor I list 10 sample inputs that your program should be able to "solve" (all is verified solveable):

```
 1. 464fa6 (same as the first sample)
 2. 35bf12 (second example input seen above)
 3. 111126
 4. ff7fff
 5. 565656
 6. abcdef
 7. 1357bd
 8. 8c6a42
 9. ab7845
10. 349a67

```

Your program should be able to solve any of the 10 sample inputs in resonable time. translate resonable time to within 1 hour on a standard desktop computer. Say like: 3 Ghz Dual core, 4GB memory for a reference.

This is code golf, the shortest solution wins. The solution can be a fully working program or a function

# Answer
> 1 votes
### Haskell, 156

Well, this one stretches the rules a bit. I don't have any blankspace walls except for the linebreaks, therefore all my walls have a length of 1.

```
import Data.List
r=replicate
main=getLine>>=putStrLn.concatMap(\b->unlines$s(head$elemIndices b"0123456789abcdef")b)
s n c|n<9=[r n c,""]|True=r 8 c:s(n-8)c

```

output for 464fa6:

```
4444

666666

4444

ffffffff
fffffff

aaaaaaaa
aa

666666

```

# Answer
> 1 votes
# BrainF\*ck - 134 (newline intr

```
>>+[++++++++++>,----------]>++++++[<+++++>-]<++[<]<++++++[>+++++<-]>++>-
>..<<.>>>..<<<.>>>>..<<<.<........>.>>>>..>>>.<<..>>.<..[<]>>.

```

I think that this is the simplist answer

Input taken via 6 hexadecimal characters to stdin, followed by a newline to submit.

EDIT: This fails due to rule 6, that I didn't fully realize until now :/

---
Tags: code-golf
---


# Question
Title: Finding "sub-palindromes" 2: subsequences.
The same task as Finding "sub-palindromes" but instead of finding substrings you must find **subsequences** that are **not substrings**.

eg1:

```
input: "12131331"
output:
"11", "33", "111", "121", "131", "313", "333", "1111", "1331", "11311", "13331"
or
"11", "33", "111", "333", "1111", "11311", "13331"

```

eg2:

```
input: "3333"
output:
"33", "333"
or
(null)

```
* Input is a string of printable ascii characters.
* Output is a list of *unique* strings.
* If a subsequence also appears as a substring it may be omitted.
* Shortest code wins.

# Answer
### GolfScript, 39 characters

```
:^1/[""]\{`{1$\+}+%}/.&{..-1%=^@?0<&},`

```

Examples:

```
> "12131331"
["11" "333" "111" "13331" "13131" "1111" "11311"]

> "3333"
[]

```

Basic blocks of the code:

```
# Save input in variable
:^

# Build all possible subsequences of the input
1/[""]\{`{1$\+}+%}/

# Filter unique ones
.&

# Filter relevant palindromes
{.
  .-1%=   # check if palindrome
  ^@?0<   # check if sequence is no substring
  &       # and operation on both
},

# Format output
`

```
> 1 votes

# Answer
## Haskell (119)

```
import Data.List
main=interact f
f a=show.nub.filter(\x->(not$isInfixOf a x)&&x==reverse x&&length x>1)$subsequences a

```

Isn't too difficult with a builtin `subsequences` and `nub`... :)
> 2 votes

# Answer
## Golfscript (95)

```
);.{{(\a\:x;.{[x]\+}%+}:b;{.!{[$]}{b}if}:a;.a{..-1%=&},\{,}{(;}/{{,}{);}/}%{+}*-.&{`}%", "*}and

```

I haven't really tried to golf this further, it's just a combination of left overs.

The question is inconsistent. My program prints all palindromic subsequences that are not substrings. Hope this is OK.

Example 1:

```
echo "12131331" | ruby golfscript.rb subseq_not_substr.gs
"11", "111", "13331", "13131", "1111", "11311"

```

Example 2:

```
echo "3333" | ruby golfscript.rb subseq_not_substr.gs

```

Empty String Example:

```
echo "" | ruby golfscript.rb subseq_not_substr.gs

```

With uglier output formatting, eg `[11 111 13331 13131 1111 11311]`, it could be made a bit shorter.
> 2 votes

---
Tags: code-golf, palindrome, subsequence
---


# Question
Title: Generate the characters of "Hello, world!" mathematically, without strings or arrays, like generating the digits of π
The challenge is to come up with a mathematical way to generate each character of the exact string:

> Hello, world!

(Capital letter, comma, exclamation mark.)

But you can't use any strings, arrays, or equivalents, to contain the data of the text. You must derive the characters by mathematical means.

So just a list or array of characters or ASCII codes or numbers trivially offset or inverted or shifted does not count. Nor does downloading it from an external resource or taking user input. Nor does starting with a large number which is just each ASCII codes shifted and ORed together, etc.

You can use any programming language, any mathematical functions, math libraries, etc.

The characters can of course be strings as you generate them.

**Think of something like generating the digits of π.**

The winner shall be the one with the most cleverness and/or elegance. The relevant weightings of cleverness and elegance are up to your peers, for the winner shall be decided by voting. (Finding a loophole in my poor problem statement shall not be regarded as clever d-:)

I think you can get the jist so don't cheat and if I should make it clearer or close some loopholes then please comment.

# Answer
> 4 votes
## HQ9+

```
H

```

If you need more mathematics, `H+++++++++++++++++++++++++++++++++++++++++` should suffice.

# Answer
> 2 votes
# Javascript

```
String.fromCharCode(72)+(681180).toString(36)+String.fromCharCode(44)+String.fromCharCode(32)+(54903217).toString(36)+String.fromCharCode(33)

```

It uses a few ASCII codes, but not for most of the text.

# Answer
> -1 votes
## Brainfuck

```
-[------->+<]>-.-[->+++++<]>++.+++++++..+++.[->+++++<]>+.------------.--[->++++<]>-.--------.+++.------.--------.-[--->+<]>.

```

---
Tags: popularity-contest, hello-world
---


title: Underhanded launcher

text:
# Question
Title: Underhanded launcher
Your goal is to write a super-secret program which launches another (independent) program. You don't have to provide the payload in your answer, it can be any program name your program will launch.

However, the challenge is to keep this behavior a secret. Upon casual inspection of the code, it should be impossible or very hard to notice that your program actually executes a foreign program. Bonus if this "hidden feature", once discovered, can reasonably be explained away as an unintentional bug. This is why the code has to be as clear as possible, and everything should have an alibi for being there, otherwise someone inspecting your code might become suspicious.

Remember, this is **not** a code-golf, but an underhanded contest.

* Your code has to be clear and readable.
* The causes of the change have to be hidden. Even if discovered, they should look more like bugs than malice.

You should provide an explanation, best in spoiler.

> like this

**The winner will be selected as the highest voted answer not sooner than 10 days after the first valid answer.** Yes, I know it's subjective, but this is the only criteria adequate for underhanded contests.

Voters should value the standard "underhanded" qualities, like how clear the code is and how well hidden the reason is.

I made this competition for compiled languages, but you can also use interpreted languages if you find two different notable interpreters for it.

# Answer
> 5 votes
## Tcl

Simple.

```
proc main {} {
    set fd [open filenames.txt]
    while {[gets $fd line] ne ""} {
        set other [open $line w]
        puts $other [clock format [clock seconds]]
    }
}
main

```

> Ilmari Karonen is right:
> If you supply a filename with a `|` as first character, it will treat the rest as command. IIRC for Perl it has to be at the end.

# Answer
> 5 votes
# JavaScript

```
if(document.location.href = 'http://www.example.com') foo();

```

> "document.loaction.href = 'http;//www.example.com'" sets the page location to "http;//www.example.com" instead of testing for the page location to be "http;//www.example.com".

It's an interpretted language, so here are two interpretters: SpiderMonkey and Google Chrome.

---
Tags: popularity-contest, underhanded
---


# Question
Title: Arbitrarily Shift Bit Array Represented As Array of 32-bit Integers
Given an array of 32-bit integers which represent a bit array, shift the values by a specified amount in either direction. Positive shifts go to the left and negative values go to the right. This is a bit array so bits should wrap across values in the array.

For example, given the following data:

```
a[2] = 11110000 11110000 11110000 11110000
a[1] = 11110000 11110000 11110000 11110000
a[0] = 11110000 11110000 11110000 11110000 <-- 0th bit

```

Shifting the original by 2 should result in:

```
a[3] = 00000000 00000000 00000000 00000011
a[2] = 11000011 11000011 11000011 11000011
a[1] = 11000011 11000011 11000011 11000011
a[0] = 11000011 11000011 11000011 11000000 <-- 0th bit

```

Shifting the original by -3 should result in:

```
a[2] = 00011110 00011110 00011110 00011110
a[1] = 00011110 00011110 00011110 00011110
a[0] = 00011110 00011110 00011110 00011110 <-- 0th bit

```

There's no restriction on shift amount (i.e., can be greater than 32) so be mindful of where your bits are going!

Here's the method signature:

```
int[] bitArrayShift(int[] bits, int shift)

```

Implementations should:

* Return an array whose contents represented the original bit array's contents shifted by the supplied number.
* Return an array whose size is the minimum amount required to hold the values after the shift. You should not wrap back around to the 0th bit but rather expand to hold it.
* Not mutate the input array. It should be treated as being passed by reference (therefore having mutable contents). Basically, don't put any new values at any position in the input array.

The following assertion should always return true for any value of 'bit' and 'shift':

```
// Given 'originalBits' as incoming bit array.
// Given 'bit' as a number between [0, originalBits.length * 32).
// Given 'shift' as any integer value.

// Get the value in the array at the index of 'bit'
bool original = ((originalBits[bit / 32] & (1 << (bit % 32)) != 0
// Shift the original bits by the specified 'shift'
int[] shiftedBits = bitArrayShift(originalBits, shift)
// Offset the original 'bit' by the specified 'shift'
int shiftedBit = bit + shift
// Get the value in the shifted array at the index of 'shiftedBit'
bool shifted = ((shiftedBits[shiftedBit / 32] & (1 << (shiftedBit % 32)) != 0
// They should be equal.
assert original == shifted

```

Smallest character count wins. Count method body contents ONLY sans leading and trailing whitespace. That is, the method declaration up to and including the block start (if any) and ending exclusively at the block end (if any).

E.g., for Java:

```
public static int[] shiftBitArray(int[] bits, int shift) {
  << COUNT THIS ONLY >>>
}

```

# Answer
> 2 votes
# Java 306

```
public static int[] shiftBitArray(int[] bits, int shift) {
    BigInteger r = BigInteger.ZERO;
    for (int i = bits.length - 1; i >= 0;) r = BigInteger.valueOf(0xffffffffL & bits[i--]).or(r.shiftLeft(32));
    r = r.shiftLeft(shift);
    int[] a = new int[(int) Math.ceil(r.bitLength() / 32d)];
    for (int i = 0; i < a.length; r = r.shiftRight(32)) a[i++] = r.intValue();
    return a;
}

```

# Answer
> 1 votes
# Java 500

```
public static int[] shiftBitArray(int[] bits, int shift) {
  int t = 32, w;
  long x = 1L << t;
  String s = "", z = Long.toString(x, t / 2).substring(1); z += z; z += z;
  for (int i : bits) s = Long.toString(i & x - 1 | x, 2).substring(1) + s;
  for (; shift > 0; shift -= t) s += z;
  s = -shift > s.length() ? z : z.substring(shift & t - 1) + s.substring(0, s.length() + shift);
  while (s.startsWith(z)) s = s.substring(t);
  int[] r = new int[(w = s.length()) / t];
  for (int j = 0; j < r.length; j++) r[j] = (int) Long.parseLong(s.substring(w -= t, w + t), 2);
  return r;
}

```

# Answer
> 1 votes
**Python (181)**

```
def bitArrayShift(b, s):
 a=''.join(bin(x)[2:].zfill(32)for x in b)
 a=(a+'0'*s if s>0 else a[:s]).lstrip('0')
 return[int(a[b:c],2)for b,c in[(x-32if x>31 else 0,x)for x in range(len(a),0,-32)]][::-1]or[0]

```

It basically just turns the array into a single string of bits, rotates by string manipulation and converts it back to integers.

# Answer
> 1 votes
### GolfScript, 32 characters

```
{{2.5??base}:^~2@.0>{?*}{~)?/}if^}:S;

```

(Character count without `{}:S;` as specified in the question) Defines a function `S` with works on the stack (there is no such thing like call by reference for stack-based languages). Usage:

```
2 [4042322160 4042322160 4042322160] S p    # => [3 3284386755 3284386755 3284386752]
-3 [4042322160 4042322160 4042322160] S p   # => [505290270 505290270 505290270]

```

6 characters more if one prefers lowest-word first.

# Answer
> 1 votes
## J (32)

```
shift=:4 :'#.|."1|._32>\|.({.~x+#);y#:~32#2'

```

(Not counting the `shift=:4 :'`...`'`.)

Test:

```
   9!:11[20 NB. set print precision high enough for the large numbers to show

   shift=:4 :'#.|."1|._32>\|.({.~x+#);y#:~32#2'
   2 shift 4042322160 4042322160 4042322160
3 3284386755 3284386755 3284386752
   _3 shift 4042322160 4042322160 4042322160
505290270 505290270 505290270

```

Explanation:

* `y#:~32#2`: encode each value in `y` as 32 bits, giving a matrix.
* `;`: join the rows of the matrix together, giving a list of bits.
* `{.~x+#`: take the first `x+length` elements from the list, padding with zeroes. (so zeroes get added to the end if `x` is positive, dropped if `x` is negative.)
* `|.`: flip the list (to make partitioning easier)
* `_32>\`: group the bits into groups of 32, padding with zeroes. (the extra zeroes go on the end, which is why the list had to be flipped.)
* `|."1|.`: flip the resulting matrix both horizontally and vertically, putting the bits back in the right order.
* `#.`: decode each line of bits back into an integer.

# Answer
> 0 votes
# Scala 324

```
def shiftBitArray(bits: Array[Int], shift: Int): Array[Int] = {
    def f(i:Array[Int])=i.map(x => String.format("%32s",x.toBinaryString).replace(' ','0')).mkString
    def g(x:Int)=List.fill(x)("0").mkString
    def h(s:String)=s.grouped(32).toArray.map(x=>java.lang.Long.parseLong(x, 2).toInt)
    val s=shift
    if (s<=0)h(g(-1*s)+f(bits).dropRight(-1*s))
    else h(g(32-s)+f(bits)+g(s))
}

```

# Answer
> 0 votes
# APL, 49

```
shift←{⌽2⊥⍉(c,32)⍴⌽(32×c←⌈n÷32)↑⌽(n←⍺+⍴v)↑v←∊(32/2)∘⊤¨⌽⍵}

```

Could probably be golfed some more. The entire `(32×⌈n÷32)↑` and the following reshaping is probably overkill.

**Examples**

```
      0 shift 3/4042322160
4042322160 4042322160 4042322160
      2 shift 3/4042322160
3284386752 3284386755 3284386755 3
      ¯3 shift 3/4042322160
505290270 505290270 505290270

```

# Answer
> 0 votes
**Golfscript (57)**

A first draft, slightly longer than APL but all ascii. Probably possible to golf a little more.

```
~.~)@2 32?:q;{\q*+}*@{2*}*\{2/}*{q%1$}{;q/}/\;-1%.![0]*+p

```

# Answer
> 0 votes
# Mathematica 57

In infix form:

```
a_~f~n_ := Flatten@a~RotateLeft~n~ArrayReshape~Dimensions@a

```

In standard prefix form:

```
f[a_,n_]:=ArrayReshape[RotateLeft[Flatten[a], n], Dimensions[a]]

```

where `a` is the array and `n` is the shift parameter.

---

`Flatten` transforms `a` into a list of integers.

`RotateLeft[list,n]` rotates `list` n places leftward (if \>= 0) or rightward (if n\<0).

`Dimensions` obtains the dimensions of the input matrix.

`ArrayReshape[list, Dimensions[a]]` transforms `list` into an array with the dimensions of the original matrix, `a`.

`RotateRight[a,n]` has the same effect as `RotateLeft[a,-n]` for all integers n.

---
Tags: code-golf, bitwise
---


# Question
Title: Find the best immediate move in a "match-3" game
Your challenge today is to take input like this:

```
fbcfbee
ffcabbe
debceec
bccabbe
edcfbcd
daeaafc
eebcbeb

```

And output the best possible move in a Bejeweled-like game that will match three or more letters, like this (note the capital `B` and `C`):

```
fbcfbee
ffcabbe
deBCeec
bccabbe
edcfbcd
daeaafc
eebcbeb

```

Full specifications:

* The input will be `n` lines of `n` lowercase letters each (where `n` could be any number).
* The output will be the best move you could make in a match-3 game, with the two letters you want to swap capitalized.
* Matches should have the following priority (in these examples, `.` indicates a square that doesn't matter):

1. Five-in-a-row

    ```
    xxYxx
    ..X..

    ```
    2. Broken five-in-a-row

    ```
    X..
    Yxx
    x..
    x..

    ```

    or

    ```
    .X.
    xYx
    .x.
    .x.

    ```
    3. Four-in-a-row

    ```
    xYxx
    .X..

    ```
    4. Three-in-a-row

    ```
    xYx
    .X.

    ```

You must find the match of the highest priority and output it.
* If there are multiple matches of the same priority, you can output any one of them.
* There will always be at least one match (your program can break if there are no matches, or do anything you want).
* I/O can be in any reasonable format (stdin/out, reading and writing files, function arguments/return values, dialog boxes, etc.) but NOT hardcoded (like `x="[insert input here]"`).
* This is so shortest code in bytes wins. If you use any network access for some reason, all bytes downloaded from the network count against your score.

# Answer
**Python3.4, 772**

(Using tabs for indentation, instead of spaces.)

```
import sys,itertools as I
B=[]
for l in sys.stdin:
    l=l.rstrip()
    B.append(list(l))
Z=len(B[0])
F=T=None
R=range
N=min
X=max
P=I.product
S=0
def C(I,J,K,L):
    global F,T,S
    if K<0 or K>=Z or L<0 or L>=Z: return
    B[I][J],B[K][L]=B[K][L],B[I][J]
    h=v=1
    m=B[K][L]
    for i in R(K+1,N(Z,K+5)):
        if B[i][L]!=m:break
        v+=1
    for i in R(K-1,X(0,K-5),-1):
        if B[i][L]!=m:break
        v+=1
    for j in R(L+1,N(Z,L+5)):
        if B[K][j]!=m:break
        h+=1
    for j in R(L-1,X(0,L-5),-1):
        if B[K][j]!=m:break
        h+=1
    c=X(h,v)*2
    if N(h,v)>=3:c+=N(h,v)
    if c>S:S=c;F=I,J;T=K,L
    B[I][J],B[K][L]=B[K][L],B[I][J]
for i,j in P(reversed(R(Z)),R(Z)):
    for d,e in (1,0),(0,-1),(0,1),(-1,0):
        C(i,j,i+d,j+e)
for i,j in P(R(Z),R(Z)):
    c=B[i][j]
    if (i,j)in(F,T):c=c.upper()
    print(c,end=('',"\n")[j==Z-1])

```
> 2 votes

---
Tags: code-golf, game
---


title: Flippin' Squares

text:
# Question
Title: Flippin' Squares
Create a program or function to unjumble a square of digits by flipping (reversing around the centre point) only rows and columns.

**Input**

Input will be a 9x9 grid of digits in the form of a 9 line string like the following:

```
986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378

```

This input format is non-negotiable - any solutions which are "creative" with the input format will be considered invalid.

**Output**

Output should be a list of flip moves which, when applied to the input in the given order, should recreate the target grid.

An example output (not a solution to the previous input example):

```
28IF5D3EAB9G3

```

This output format is also non-negotiable. There should be no newlines or spaces in the output, only the characters `1`-`9` and `A`-`I` (lower case characters are acceptable in place of upper case characters if you prefer).

The target grid (the state you need to recreate) is as follows:

```
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

```

The numbers `1`-`9` should be used as instructions to flip the rows, and the letters `A`-`I` should be used for the columns. This is shown below with the grid in its restored state.

```
     ABCDEFGHI
     |||||||||
     vvvvvvvvv
1 -> 123456789
2 -> 234567891
3 -> 345678912
4 -> 456789123
5 -> 567891234
6 -> 678912345
7 -> 789123456
8 -> 891234567
9 -> 912345678

```

So an `8` means flip the second row from the bottom, and an `F` means flip the sixth column.

In the case that no solution is possible, the program should end without outputting anything at all.

**Examples**

Input:

```
987654321
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

```

Output:

```
1

```

In this case only the top row needs flipping to return to the goal state.

Input:

```
123456788
234567897
345678916
456789125
567891234
678912343
789123452
891234561
912345679

```

Output:

```
I

```

In this case only the final column (column `I`) needs flipping to recreate the goal state.

Input:

```
123456788
798765432
345678916
456789125
567891234
678912343
789123452
891234561
912345679

```

Output:

```
2I

```

In this case we need to flip row `2` and then flip column `I` to return to the goal state.

**Notes:**

* Please include an example usage in your answer.
* The output given does not have to be the shortest sequence that will return the goal state - any sequence which returns the goal state will do as long as it works (i.e. as long as I can test it)
* I'll endeavour to test each answer and upvote all those that work and have obviously had an attempt at golfing.
* **This is an open-ended competition - I'll accept the shortest answer sometime next week, but if a newer valid answer comes along which is shorter at any point in the future I'll change the accepted answer to reflect that**.
* The bounty has been set at 200 reputation for the shortest answer received by **23:59:59 (GMT) on 26/01/2014** The bounty was awarded to Howard for his 268 character GolfScript solution.

**Testing**

Please provide your program's output for the following three test grids with your answer:

```
986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378

927354389
194762537
319673942
351982676
567891234
523719844
755128486
268534198
812546671

813654789
738762162
344871987
341989324
567891234
576217856
619623552
194435598
926543271

```

I've created a small Python program to generate valid grids for testing purposes:

```
import random

def output(array):
  print '\n'.join([''.join(row) for row in array])

def fliprow(rownum, array):
  return [row[::1-2*(rownum==idx)] for idx,row in enumerate(array)]

def flipcol(colnum, array):
  return zip(*fliprow(colnum, zip(*array)))

def randomflip(array):
  op=random.randint(0,1)
  row=random.randint(0,9)
  if(op==1):
    return fliprow(row, array)
  else:
    return flipcol(row, array)

def jumble(array):
  arraycopy=array
  for i in range(10, 1000):
    arraycopy=randomflip(arraycopy)
  return arraycopy

startarray=[
['1','2','3','4','5','6','7','8','9'],
['2','3','4','5','6','7','8','9','1'],
['3','4','5','6','7','8','9','1','2'],
['4','5','6','7','8','9','1','2','3'],
['5','6','7','8','9','1','2','3','4'],
['6','7','8','9','1','2','3','4','5'],
['7','8','9','1','2','3','4','5','6'],
['8','9','1','2','3','4','5','6','7'],
['9','1','2','3','4','5','6','7','8']]

print output(jumble(startarray))

```

# Answer
### GolfScript, 300 279 268 characters

```
n%`{\5,{.9+}%{;.2/\2%},\;''{1${.9/7+7*+}%+:z;}:?~{{.9<77*{\zip\9-}>:Z~{1$!{-1%}*\(\}@%\Z;}/}:E~{:^;{:c;.`{[\E[.^=\8^-=]{.c=\8c-=}%[^c+^8c-+8^-c+16c-^-]{9%49+}%=}+[[]]:K[[8^- 17c-][^9c+]1$]{:s;{[[]s.+.2$+]{1$+}/}%.&}/\,K+0=z?E}5,/}5,/{{+9%)}+9,%''*}9,%={z:u;}*}+1024,/u

```

Note that this code is extremely slow (also due to heavy code-block manipulation) and might run several minutes. The code is very un-golfscript-ish with lots of variables and explicit loops.

I had written a more analytic solution which ran for less than a second. I completely broke that one during golfing. Unfortunately, I wasn't able to backtrack or repair the code in the last two days. Therefore, I produced this try-and-check version which is shorter anyways.

The answers for the puzzles given above:

```
1A2C4D9G9G9G9G1C1C1C1C9F9F9F9F1D1D1D1D2A2A2A2A8H8H8H8H2B2B2B2B2C2C8F8F2D2D2D2D3A3A7I7I3B3B7H7H7G7G7G7G3D3D7F7F6I6I6I6I4A4A4A4A6H6H6H6H6G6G4C4C4C4C6F6F4D4D

1AB39I9I1A1A9I9I1B1B9F9F8I8I8I8I2B2B8H8H8G8G8G8G2D2D2D2D3A3A3A3A7H7H7H7H3C3C3C3C3D3D7F7F6I6I4A4A6I6I4B4B4B4B6G6G4C4C4C4C6F6F6F6F4D4D

1A34D9I9I9I9I1A1A1A1A1B1B1B1B9G9G1C1C1C1C9F9F9F9F1D1D9F9F8I8I2A2A2A2A8H8H8H8H2C2C2C2C8F8F2D2D8F8F7I7I7I7I3A3A3B3B7G7G7G7G3C3C3C3C6I6I6I6I6H6H6H6H4B4B4B4B6G6G6G6G4C4C6G6G6F6F4D4D6F6F

```
> 7 votes

# Answer
# Mathematica ~~582~~ ~~575~~ ~~503~~ ~~464~~ 282

To fight with golfscripters I have to use heavy artillery!

```
i = "986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378";

a=Array;h@M_:=Join@@a[9(M〚##〛/. 9->9⌈2Random[]⌉)+Abs[{##}-5]&,n={9,9}];
For[i_~t~j_:=i{#2,10-#2}+j#-9&~a~{9,4},!ListQ[e=GroupElementToWord[
PermutationGroup[Cycles/@Join[1~t~9,9~t~1]],
h[ToCharacterCode@StringSplit@i-48]~FindPermutation~h@a[Mod[8+##,9,1]&,n]]],];
e~IntegerString~36<>""

```

Output:

```
g69g69g8g8g7g7gd96d96d8d8d7d7dh6h64a6a46d6d4g4g6b6b7h7h7c7c2a8a27b7bd8db8b7f7fg8g82c2c94a4a3a3aigfdc91

```

Here `PermutationGroup[...]` sets up possible flips and `GroupElementToWord[...]` solves the problem (about `0.2` sec). The main problem is that it is difficult to identify the correspondence between the position of `9` in the initial and the final grid. For golfing I do it randomly (it takes several seconds). There are some warnings but one can ignore them.

Other to test grids:

```
g69g69g8g8g7g7gh89h89h7h7h6h6hf6f6g6g64f4f4h4hg7g73g3g2a8a28d8db8b83d3dg8g82c2c9a3a643a3a2g9f9d9c9ga
h89h89h7h7h6h6h6h6h6f6f6g6g6d6d3a7a37g7g7h7h3c3c2a8a27b7b8d8d2f2f8b8b3f3f2b2ba2a764a8aih9g9c9gb1i

```

It completely reproduces the examples:

```
1
i
2i

```

---

## Previous solution (464)

without any clever built-in functions and with runtime 4 ms:

```
M=ToCharacterCode@StringSplit@i-48;
S="";s=Signature;H=(S=S<>{#,#2+9}~IntegerString~36)&;
A=(m=M〚##〛)-9Mod[m+##,2]&[s@{2#3,5}#,2#2#3~Mod~2-#2]&~Array~{4,4,4};
u=s/@Join@@A;
H@@({k,l}=#&@@@#~Position~1&/@{v=u〚13;;〛;{h=#2u〚2〛,-#u〚5〛,-#u〚9〛}&@@v,v〚4〛=u〚4〛h;v});
A〚k〛=A〚k,;;,{2,1,3,4}〛;A〚;;,l〛=A〚;;,l,{3,2,1,4}〛;
MapIndexed[4#≠#4&&H@@@If[#2<3,#0[#3,#,#2,#4];k,#0[#,#3,#4,#2];10-k]&@@
If[s@#<0,#〚{1,3,2,4}〛,#]&@Ordering[k={#2,#2};#]&,A,{2}];
M〚5,1〛<5&&5~H~{};M〚1,5〛<5&&{}~H~5;S

```

All new lines here are not necessary.

Output:

```
3b9i9i1a1a1a1a9i9i1a1a9h9h1b1b1b1b9h9h9g9g1c1c9g9g9f9f1d1d9f9f8h8h2b2b8f8f8f8f7i7i7h7h3b3b3b3b7h7h3b3b7h7h7g7g3c3c7g7g3c3c7f7f6i6i4a4a6h6h4b4b4b4b6g6g4c4c6g6g4c4c6f6f4d4d4d4d6f6f4d4d6f6f4d4d

```

Other two test grids:

```
13ab9i9i1a1a9i9i9h9h1b1b1b1b9h9h9f9f8i8i8i8i8h8h2b2b2b2b8h8h8h8h8g8g8g8g8f8f2d2d2d2d8f8f2d2d7i7i3a3a3a3a7i7i7h7h3b3b7h7h3b3b7g7g3c3c3c3c7g7g3c3c7f7f3d3d3d3d7f7f7f7f6i6i4a4a6i6i6h6h4b4b4b4b6h6h4b4b6g6g4c4c4c4c6f6f4d4d4d4d6f6f4d4d6f6f
2bc9i9i1a1a9i9i9g9g1c1c9g9g1c1c9f9f1d1d1d1d8i8i8i8i8h8h2b2b2b2b8f8f2d2d7i7i7h7h3b3b3b3b7h7h3b3b7g7g3c3c7f7f3d3d3d3d7f7f3d3d6i6i4a4a4a4a6h6h4b4b6g6g6g6g6f6f4d4d

```

Visualization:

```
anim = Reap[Fold[Function[{m, i},
 If[i > 9, (Sow@Grid[#, Background -> {i - 9 -> Pink, None}] & /@ {m, #}; #) &@
   Transpose@MapAt[Reverse, Transpose@m, i - 9], (Sow@Grid[#,
         Background -> {None, i -> Pink}] & /@ {m, #}; #) &@
   MapAt[Reverse, m, i]]], M, IntegerDigits[FromDigits[S, 36], 36]]];

ListAnimate[Join[{#, #} &@Grid@M, anim[[2, 1]], {#, #} &@Grid@anim[[1]]], 5]

```

The input string `i` can be generated randomly by

```
M = Array[Mod[8 + ##, 9, 1] &, {9, 9}];
(M[[#]] = Reverse@M[[#]]; M[[All, #2]] = Reverse@M[[All, #2]];) & @@@
   RandomInteger[{1, 9}, {10000, 2}];
i = ToString /@ # <> "\n" & /@ M <> ""

```

## Brief discussion

* Flips can interchange only these elements ("quadruple"):
* It is possible to interchange these elements separately from other elements only if the initial and the final order has the same signature.
* Flips of these four elements form the alternating group of degree 4 ( = group of rotations of the tetrahedral). Every element of this group is a composition of 2 generating elements. So if we know the initial and final position we can decompose the corresponding transformation as a combination of a simple flips.

## Details

For sportsmanship I post details before the end of the bounty!

```
M=ToCharacterCode@StringSplit@i-48;

```

Convert the string `i` to the matrix `M`.

```
S="";s=Signature;H=(S=S<>{#,#2+9}~IntegerString~36)&;

```

We will append chars to `S`. Now it is the empty string. `H[i,j]` will add the character `i` (`1,2,3,...,9`) and the character `j` (`a,b,c,...,i` in base-36).

```
A=(m=M〚##〛)-9Mod[m+##,2]&[s@{2#3,5}#,2#2#3~Mod~2-#2]&~Array~{4,4,4};

```

I convert elements as

to obtain the target matrix in the following form

Then there are two main steps in my algorithm

1. Find flips to obtain the signatures as in the target matrix (e.g. the signature of `{-7,-1,1,7}` is `1` and the signature of `{-6,2,-2,6}` is `-1`):

```
u=s/@Join@@A;
H@@({k,l}=#&@@@#~Position~1&/@{v=u〚13;;〛;{h=#2u〚2〛,-#u〚5〛,-#u〚9〛}&@@v,v〚4〛=u〚4〛h;v});
A〚k〛=A〚k,;;,{2,1,3,4}〛;A〚;;,l〛=A〚;;,l,{3,2,1,4}〛;

```
2. Rotate every "quadruple" to obtain the right order:

```
MapIndexed[4#≠#4&&H@@@If[#2<3,#0[#3,#,#2,#4];k,#0[#,#3,#4,#2];10-k]&@@
If[s@#<0,#〚{1,3,2,4}〛,#]&@Ordering[k={#2,#2};#]&,A,{2}];

```

It is the most nontrivial part of the algorithm. For example, the transformation `1b1b` will convert `{-7,-1,1,7}` to `{-1,1,-7,7}`. The transformation `9h9h` will convert `{-7,-1,1,7}` to `{-7,7,-1,1}`. So we have two maps

```
{1,2,3,4} -> {2,3,1,4}
{1,2,3,4} -> {1,4,2,3}

```

and we want to convert an arbitrary ordering `{x,y,z,w}` to `{1,2,3,4}`. The simple method is (except a random search)

```
repeat
{x, y, z, w} -> If[z < 3, {y, z, x, w}, {x, w, y, z}]
until {1,2,3,4}

```

I can't proof it, but it works!

The last step is

```
M〚5,1〛<5&&5~H~{};M〚1,5〛<5&&{}~H~5;S

```

It performs trivial flips of the center row and the center column and return the result.
> 24 votes

# Answer
# J ~~487~~ 438

```
q=:3 :'(>:9|+/~i.9)=/&((,{;/(,.8&-)y){])g'
l=:2 :0
:
o=:o,(m+x){a.
x&(|.@{`[`]})&.v y
)
r=:49 l]
c=:97 l|:
w=:2 :'g=:4 v^:(4=(<m){g)g'
p=:_1=C.!.2@,@:I.@q
t=:2 :'for_i.>:i.3 do.g=:i v^:(p m*i)g end.'
z=:2 :0
'i j I J'=.y,8-y
g=:".'(',(,' ',.,(I.m{q y){,;._1 n),'])^:2 g'
)
d=:3 :0
g=:9 9$".,_ list,' ',.y
o=:''
0 4 w c
4 0 w r
0 1 t c
g=:0 c^:(-.(p 1 0)=p 1 2)g
1 0 t r
for_k.>,{;~i.4 do.0 z';;jcir;irjc;Irjc'k
3 z';;IrJc;JcIr;'k end.o
)

```

`d` is a verb which takes a grid string in the specified format and returns a solution string in the specified format.

Example use:

```
   d '987654321',LF,'234567891',LF,'345678912',LF,'456789123',LF,'567891234',LF,'678912345',LF,'789123456',LF,'891234567',LF,'912345678'
bcda2341a1a1b1b1c1c1d1da2a2b2b2c2c2d2d2a3a3b3b3c3c3d3d3a4a4b4b4c4c4d4d4

```

Now accepts either newline type.

Solutions to the test grids:

```
b3a1a11b1bc9c99g9gd9d99f9fb8b8f8f87i7i7h7hc3c3g7g77f7fa6a64b4bh6h6c4c4g6g6d6d6f6f6
cd24a9a91c1c1d1d9f9fa2a2i8i88h8hc2c2g8g82d2d3b3bh7h7d3d37f7fa6a64b4bg6g64d4d6f6f
bc2a9a99i9ic1c1g9g91d1df9f9i8i8b2b2h8h82c2cd8d87i7ib3b3c7c7d3d34a4ai6i6b6b6g6g6d6d6

```

I'm fairly new to J; this could probably be golfed even further.

---

Checking for invalid/unsolvable grids incurs a 123 character penalty. I don't think the other answers to date have such error checking.

To do so, change the first line of `d` to this:

```
if.-.+./89 90=#y do.0 return.end.if.-.*./(/:~y)=/:~(#y)$'123456789',LF do.0 return.end.g=:9 9$".,_ list,' ',.y

```

and the last line to this:

```
3 z';;IrJc;JcIr;'k end.if.*./,g=>:9|+/~i.9 do.o return.end.0

```

I've chosen to return `0` on such errors as returning an empty string would be indistinguishable from correctly solving a fully solved grid. Note that this assumes UNIX newlines (again).
> 7 votes

# Answer
## C# ~~540~~ 399

Well, sacrificed performance (now it takes up to 30 seconds), introduced dynamic variables, slightly changed logic of solution. And yes, now it is expecting input as one string with line-breaks (as required in rules).

Of course C# do not have predefined math functions, so it would be hard to fight with Mathematica guys. Nevertheless, this was a great challenge, thanks to the author!

```
string S(string _){for(i=0,e=1>0;e;){
for(h=v=j=0;j<89;)m[j/10,j%10+9]=_[j++]-49;a="";
for(j=i++;j>0;v++,j/=2)if(j%2>0)F(v);
for(;h<9&(h<4|!e);h+=j/36,j%=36)if((e=m[h,g=j++%9+9]!=(t=(h+g)%9))|m[v=8-h,g]==t){F(v);F(g);F(v);F(g);}
}return a;}void F(int z){for(f=z<9;++l<9;)m[0,l]=m[f?z:l,f?9+l:z];for(;l-->0;)m[f?z:l,f?9+l:z]=m[0,8-l];a+=(char)(z+=f?49:56);}
dynamic h,v,i,j,e,t,l=-1,g,a,m=new int[9,19],f;

```

Test grids:

```
3B9A9A9B9B9C9C9D9D9F9F9G9G9H9H9I9I9B9B9C9C9D9D9F9F9G9G9H9H9C9C9D9D9C9C9D9D8B8B8F8F8H8H8B8B8F8F8B8B8H8H7B7B7C7C7F7F7H7H7I7I7H7H6A6A6B6B6C6C6D6D6F6F6H6H6A6A6B6B6D6D6F6F6D6D6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

13AB9A9A9B9B9F9F9H9H9A9A9B9B9H9H9I9I8B8B8D8D8F8F8G8G8H8H8I8I8B8B8G8G8H8H8I8I8H8H7A7A7B7B7C7C7D7D7F7F7G7G7I7I7A7A7D7D7F7F7I7I7F7F6A6A6B6B6C6C6D6D6F6F6G6G6H6H6I6I6A6A6C6C6F6F6I6I6A6A6A6A5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

2BC9A9A9C9C9D9D9F9F9A9A9D9D9I9I8B8B8D8D8H8H8I8I8B8B8D8D8I8I7B7B7C7C7D7D7F7F7G7G7H7H7I7I7C7C7C7C7G7G6A6A6B6B6D6D6F6F6G6G6I6I6A6A6B6B6D6D6G6G6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

```

---

## Old Solution (540)

Works in less than a second on any input (tested on thousands randomly generated grids). Maximum length of output string is 165 (initially any grid was solved in no more than 82 flips, but during golfing I sacrificed this).

```
string S(string[]_){for(i=0;i<1<<18;){
for(j=0;j<81;)m[j/9+49,j%9+65]=_[j/9][j++%9]-49;a="";char g,h='1',v='9',b,x=h,y;
for(j=i;j>0;x=x==v?'A':++x,j/=2)if(j%2>0)F(x);j=i+1;
for(i+=1<<19;h<58;h++,v--)for(g='A',b='I';g<74;g++,b--){
t=(h+g-6)%9;e=m[h,g];q=m[v,g];i=h>52&t!=e?j:i;
if(e!=t|q==t){x=q==t?v:g;y=q==t?g:v;
if(m[h,b]==t){x=b;y=h;}
F(x);F(y);F(x);F(y);}}}return a;}
void F(char z){var f=z<65;for(l=0;l<4;l++){n=m[d=f?z:49+l,s=f?65+l:z];m[d,s]=m[o=f?z:57-l,u=f?73-l:z];m[o,u]=n;}a+=z;}
int i,j,q,e,t,l,s,d,n,u,o;int[,]m=new int[99,99];string a;

```

Answer for example 1:

```
15A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

```

Answer for example 2:

```
19AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5D
5DE5E55F5F5G5G5H5H5I5I

```

Answer for example 3:

```
129AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5
D5DE5E55F5F5G5G5H5H5I5I

```

Answers for test squares:

```
346B9A9AH1H1C9C9D9D99F9F9G9GH9H99I9IB8B8F8F87B7B7C7C7F7FH7H77I7I6A6A6B6BC6C66D6DG6G6H6H66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

1346ABA9A9H1H19F9FH9H99I9IH2H28D8D8F8FG8G8I8I8I3I37B7B7C7CF3F37G7GI7I7H4H4D6D66F6F5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

2BCA9A99C9CF1F19F9F9I9IH2H2D8D88H8HI8I87B7BC7C77D7D7F7F7H7H7I7II4I4B6B6D6D6G6G66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

```
> 5 votes

---
Tags: code-golf
---


# Question
Title: Find the Longest Palindrome in a String by Removing Characters
**Problem:** Remove characters from strings to make the longest (character length) palindrome possible. The first line gives an integer value of the number of strings to test. Each subsequent line is a string to test.

**Example Input:**

```
3 // Number of lines to test
GGABZXVYCCDBA
ABGBAD
ABC

```

**Example Output:**

```
ABCCBA
ABGBA
B

```

Shortest code wins.

# Answer
> 0 votes
Here is my solution in Java (not exactly short hah)...

```
import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public class Palindrome {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(new File("src/pal.dat"));

        int q = sc.nextInt();
        sc.nextLine();

        for (int z = 0; z < q; z++) {
            String line = sc.nextLine();

            int max = 0;
            String maxP = "";

            for (int k = 0; k < line.length(); k++) {

                String p = calc(line.substring(k));

                if (p.length() > max) {
                    max = p.length();
                    maxP = p;
                }

            }

            System.out.println("Max Palindrome: " + maxP);

        }

    }

    public static String calc(String s) {
        if (s.length() == 0)
            return "";
        if (s.length() == 1 || (s.length() == 2 && s.charAt(0) != s.charAt(1)))
            return s.charAt(0) + "";
        if (s.length() == 2)
            return s;

        char[] arr = s.toCharArray();

        boolean match = false;
        int i = 0;
        for (i = arr.length - 1; i > 0; i--) {
            if (arr[i] == arr[0]) {
                match = true;
                break;
            }
        }

        int max = 0;
        String maxPalin = "";
        for (int k = 1; k < i; k++) {
            String p = calc(s.substring(k, i));
            if (p.length() > max) {
                max = p.length();
                maxPalin = p;
            }
        }

        if (match)
            return arr[0] + maxPalin + arr[0];
        return maxPalin;

    }

}

```

---
Tags: code-golf, palindrome
---


# Question
Title: Make FizzBuzz using only preprocessor directives
I have a source file here:

```
#include <FizzBuzz.h>
fizzbuzz

```

And I want to make "`fizzbuzz`" turn into a FizzBuzz program solely through the preprocessor.

Your task is to write a `FizzBuzz.h` that uses only preprocessor directives (things like include, define, etc.) to create a working FizzBuzz program. Specifically, I want to see the use of macros, which will be required to make this work (at minimum, defining `fizzbuzz` to be some code).

However, to make sure people try and take full advantage of the power of macros, your score will be defined as the sum of the cubes of the length of the definition portion (the part after `#define <symbol>`) of each macro.

So, for example, the following file:

```
#define A 123
#define B A+A
#define C B*2+A

```

would have a total score of 179 (3^3 + 3^3 + 5^3). As a rule, I want multiple shorter lines instead of one long line.

# Answer
## C, Score 1,283 1,213 1,205

**EDIT**: Instead of basing on Loki Astari's solution, now I'm based on breadbox's

The basic code is not exactly the same as breadbox's - I replaced the loop with recursion, which is longer, but has more repetition.

With GCC, it can be improved further, by using `?:` instead of `?0:`.

```
#define A "Fi"
#define D "Bu"
#define E "z"
#define L E E
#define F L,z
#define R F)
#define G A R
#define H D R
#define I ""
#define K "%d"
#define X printf
#define Y puts
#define Z main
#define M 99
#define N z%5
#define O z%3
#define P Z(z
#define Q P)
#define a Q{X
#define b a(O
#define c b?N
#define d c?K
#define e d:I
#define f e:G
#define i f;Y
#define j i(N
#define k j?I
#define l k:H
#define n l;z
#define o n++
#define p o>M
#define q p?0
#define r q:Q
#define s r;
#define fizzbuzz s}

```

Macro-free code:

```
main(z){printf(z%3?z%5?"%d":"":"Fizz",z);puts(z%5?"":"Buzz",z);z++>99?0:main(z);}

```

The 2nd parameter to `puts` does nothing. It allows me to utilize the `zz",z)` sequence.
> 10 votes

# Answer
### C score 1602 1592 1535 1515 1505 1451

```
#include <stdio.h>
#define A       "%d"
#define B       "Bu"
#define C       "Fi"
#define w       "z"
#define D       w w
#define E       "\n"
#define F       main
#define G       printf
#define I       for
#define J       99
#define L       c++
#define O       A E
#define P       O:B
#define Q       P D
#define R       Q E
#define S       c%3
#define T       c%5
#define U       S?T
#define V       U?R
#define W       V:T
#define X       W?C
#define Y       X D
#define Z       Y E
#define a       Z:C
#define b       a D
#define d       b B
#define e       d D
#define f       e E
#define g       f,c
#define r       (g)
#define h       G r
#define i       ;L
#define j       J;h
#define k       i<=
#define l       k j
#define q       (l)
#define m       I q
#define n       m;
#define o       {n}
#define p       F()
#define s       c;p
#define fizzbuzz s o

```

Original source:

```
c;main(){for(;c++<=99;printf(c%3?c%5?"%d\n":"Buzz\n":c%5?"Fizz\n":"FizzBuzz\n",c));}

```

Now I am wondering if we change the code too:

```
c;main(){for(;c++<=99;printf(6*(c%3<1)+12*(c%5<1)+"%d  \n\0Buzz\n\0Fizz\n\0FizzBuzz\n\0",c));}

```

It looks longer. But more compressable using macros.
> 6 votes

# Answer
## C, score 1267

Best I could do:

```
#define a main
#define b for
#define c puts
#define d printf
#define e ""
#define f x Z
#define g y Z
#define h "%d"
#define x "Bu"
#define y "Fi"
#define z "z"
#define Z z z
#define A 101
#define B i++
#define C B%5
#define D C?e
#define E D:f
#define F i%3
#define G F?i
#define H G%5
#define I H?h
#define J I:e
#define K J:g
#define L K,i
#define M i<A
#define N M;c
#define O a(i
#define P N(E
#define Q d(L
#define R O)
#define S b(
#define T P)
#define U Q)
#define V U;
#define W R{S
#define X W;T
#define Y X)V
#define fizzbuzz Y}

```

This is roughly the same approach that the other entries are using, looks like. I suspect the marginal improvement comes from the brevity of the target program. At 75 bytes, it's the shortest C fizzbuzz I know (that doesn't depend on compiler-specific behavior):

```
main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":"":"Fizz",i);}

```
> 3 votes

# Answer
## C, Score 28,703 18,043 4,367

```
#define S(x) #x"\n"                     // 6
#define X(a) W?Y(a)                     // 6
#define W c%5                           // 3
#define Y(a) S(a):Z(a)                  // 9
#define Z(a) S(a##Buzz)                 // 10
#define fizzbuzz A%Q}                   // 4
#define A char*B                        // 6
#define B p,C                           // 3
#define C c;D(E                         // 5
#define D main                          // 4
#define E ){F                           // 3
#define F for(G                         // 5
#define G ;c++H                         // 5
#define H <=I(K                         // 5
#define I 99;J                          // 4
#define J printf                        // 6
#define K *p+L                          // 4
#define L ~9?M                          // 4
#define M p:N,O                         // 5
#define N S(%d)                         // 5
#define O c))P                          // 4
#define P p=c                           // 3
#define Q 3?R;                          // 4
#define R X():T                         // 5
#define T X(Fizz)                       // 7

```

Original macro-free program:

```
c,*p;
main(){
        for(;c++<=99;printf(*p+~9?p:"%d\n",c))
                p=c%3?c%5?"\n":"Buzz\n":c%5?"Fizz\n":"FizzBuzz\n";
}

```
> 2 votes

# Answer
## C++, Score 68,508

I know this does not meet the criteria (lots of really short macro definitions), but I think it has an advantage over the other answers. First the solution:

```
#include <iostream>
#define X(a) H(a,N)H(1,L)
#define W(a,b,c) H(U(a,b),c)H(a,M)
#define V J::
#define U(a,b) !(a)&&!(b)
#define T ==0
#define S K<<
#define R %5 T
#define Q main
#define P int
#define O %3 T
#define N "Buzz"
#define M "Fizz"
#define L V endl
#define K V cout
#define J std
#define I if
#define H(a,b) I(a)S(b);
#define G(a,b,c) W(a,b,c)X(b)
#define F(a) G((a)O,(a)R,a)
#define E(a,b,c,d) F(a*20+b*4+c*2+d+1)
#define D(a,b,c) E(a,b,c,0)E(a,b,c,1)
#define C(a,b) D(a,b,0)D(a,b,1)
#define B(a) C(a,0)C(a,1)C(a,2)C(a,3)C(a,4)
#define A B(0)B(1)B(2)B(3)B(4)
#define fizzbuzz P Q(){A}

```

Second, I think the advantage to this is that it truly uses the preprocessor to its "best" advantage. Namely, it does not use any looping constructs or variables in determining FizzBuzz. All parameters are constants, thus all the expressions can be compile time evaluated. Any if-condition that is false can be optimized away, so the final optimized form of the compiled program is really just a bunch of statements like `cout << something; cout << endl`.
> 1 votes

# Answer
## C++, Score 24,806 (Revised from Earlier Answer)

I came across code I posted last September and decided to refine it. I was able to cut it down significantly (for a savings of 43,702 "points") while keeping in the spirit of my original submission (no variables, just pre-processed constants). Not that anyone *cares*, but hey, I was bored. :)

```
#include <iostream>
#define _ {A}
#define a ()
#define b main
#define c int
#define d a _
#define e c b
#define f "u"
#define g "B"
#define h "i"
#define i "F"
#define j "z"
#define k w v
#define l endl
#define m <<
#define n cout
#define o ::
#define p std
#define q g f
#define r i h
#define s j j
#define t N)O
#define u l;
#define v n m
#define w p o
#define y q s
#define z r s
#define Z(a,b) M(a)k b;
#define Y 0;
#define X return
#define W 100
#define V %5
#define U %3
#define T ==0
#define S w v w u
#define R(a) Z(a,y)
#define Q(a) Z(a,z)
#define P(a,b,c) Z(!(a)&&!(b),c)
#define O X Y
#define N >W
#define M if
#define L V T
#define K U T
#define J(a,b,c) P(a,b,c)Q(a)R(b)S
#define I(a) M(a t
#define H(a) I(a)J((a)K,(a)L,a)
#define G(a) H(a+1)H(a+2)
#define F(a) G(a)G(a+2)
#define E(a) F(a)F(a+4)
#define D(a) E(a)E(a+8)
#define C(a) D(a)D(a+16)
#define B(a) C(a)C(a+32)
#define A B(0)B(64)
#define fizzbuzz e d

```
> 1 votes

---
Tags: code-challenge, c, c++
---


title: Six degrees of web separation

text:
# Question
Title: Six degrees of web separation
Six degrees of separation is the theory that everyone and everything is six or fewer steps away, by way of introduction, from any other person in the world.

Your challenge here is to write a program which crawls to find out what is exactly 6 links away but connected back to the starting URL through a series of links.

For example if your program is given a starting url of http://vimeo.com it would then potentially (this is a made up example) crawl to:

1. http://www.abc.com links to -\>
2. http://www.widgets.com links to -\>
3. http://www.gadgets.net links to -\>
4. http://www.techcrunch.com links to -\>
5. https://twitter.com/techcrunch links to -\>
6. http://www.youtube.com/user/techcrunch (finish as we are now 6 links away from the starting URL.)

Rules:

* You can choose your own starting URL.
* Any programming language can be used.
* You most obey sites robots.txt files and not crawl any areas sites disallow.
* Each step must be a new URL from the one you are currently on.
* URLS should only be visited once per crawl.
* You must output the starting URL and each link followed in sequence.

Winner:

* This is a popularity contest so the solution with the most up-votes wins.

# Answer
> 1 votes
## Java, 8623 bytes

It isn't perfect. It has some issues connecting to some URLs and fails to parse the robots.txt properly. However, it's a start.

```
package info.varden.codegolf.sixdegreeslink;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URI;
import java.net.URISyntaxException;
import java.net.URL;
import java.net.URLConnection;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    private static HashMap<String, String> entities = new HashMap<>();
    private static HashMap<String, ArrayList<String>> robotstxts = new HashMap<>();

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        String init = "";
        for (String s : args) {
            init += s + "%20";
        }
        init = init.substring(0, init.length() - 3);
        try {
            System.out.println("Resolving entites (step 1 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLlat1.ent"));
            System.out.println("Resolving entites (step 2 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLsymbol.ent"));
            System.out.println("Resolving entites (step 3 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLspecial.ent"));
            System.out.println(entities.size() + " entites resolved.\n");
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println("Starting search from: " + init + "\n");
        IterationInfo initInfo = new IterationInfo();
        IterationInfo info = initInfo;
        try {
            initInfo.scanLink = init;
            initInfo.links.add(init);
            initInfo.domains.add(getDomain(init));
            info = getSixStepsRecursive(initInfo);
        } catch (URISyntaxException e) {
            e.printStackTrace();
        }

        long diffTime = System.currentTimeMillis() - startTime;
        long second = (diffTime / 1000) % 60;
        long minute = (diffTime / (1000 * 60)) % 60;
        long hour = (diffTime / (1000 * 60 * 60)) % 24;
        diffTime = diffTime % 1000;

        String time = String.format("%02d:%02d:%02d.%d", hour, minute, second, diffTime);
        System.out.println("\nCompleted in " + time);
        System.out.println("\nRESULTS:");
        if (info.success) {
            for (int i = 0; i < info.links.size(); i++) {
                System.out.println(info.links.get(i));
            }
        } else {
            System.out.println("Can't find six degrees step separation!");
        }
    }

    private static IterationInfo getSixStepsRecursive(IterationInfo info) {
        IterationInfo returnInfo = info;
        String[] urls = new String[0];
        try {
            String content = downloadString(info.scanLink);
            content = content.replace("\t", " ").replace("\r", " ").replace("\n", " ");
            while (content.contains("  ")) content = content.replace("  ", " ");
            urls = content.split("\\Q<a href=\"\\E");
        } catch (Exception ex) {
            ex.printStackTrace();
        }
        for (int i = 1; i < urls.length; i++) {
            try {
                if (info.iteration == 6) {
                    returnInfo.success = true;
                    return returnInfo;
                }
                returnInfo = info;
                urls[i] = stripHTMLEntities(urls[i].split("\"")[0]);
                if (urls[i].startsWith("//"))
                    urls[i] = "http:" + urls[i];
                if (!urls[i].startsWith("http://") && !urls[i].startsWith("https://")) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Relative or non-HTTP link (" + urls[i] + ")");
                    continue;
                }
                if (!canGetRobotsTxt(urls[i])) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Blocked by robots.txt (" + urls[i] + ")");
                    continue;
                }
                if (returnInfo.links.contains(urls[i])) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Exact link already passed (" + urls[i] + ")");
                    continue;
                }
                if (returnInfo.domains.contains(getDomain(urls[i]))) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Domain already passed (" + getDomain(urls[i]) + ") (" + urls[i] + ")");
                    continue;
                }

                System.out.println("Iter " + info.iteration + " - URL valid: Distict domain (" + getDomain(urls[i]) + ") (" + urls[i] + ")");
                returnInfo.links.add(urls[i]);
                returnInfo.domains.add(getDomain(urls[i]));
                returnInfo.iteration = info.iteration + 1;
                returnInfo.scanLink = urls[i];

                returnInfo = getSixStepsRecursive(returnInfo);
                if (returnInfo.success) {
                    return returnInfo;
                }
            } catch (Exception ex) {
            }
        }
        return returnInfo;

    }

    private static boolean canGetRobotsTxt(String url) {
        try {
            URI cur = new URI(url);
            if (!robotstxts.containsKey(cur.getHost())) {
                String rtxt = downloadString("http://" + cur.getHost() + "/robots.txt");
                String[] lines = rtxt.split("\n");
                ArrayList<String> ar = new ArrayList<>();
                for (String line : lines) {
                    if (line.endsWith("\r"))
                        line = line.substring(0, line.length() - 1);
                    if (line.toLowerCase().startsWith("disallow: ")) {
                        line = line.substring(10);
                        ar.add(line);
                    } else if (line.toLowerCase().startsWith("allow: ")) {
                        line = line.substring(7);
                        ar.remove(line);
                    }
                }
                robotstxts.put(cur.getHost(), ar);
            }
            ArrayList<String> a = robotstxts.get(cur.getHost());
            for (String s : a) {
                String[] sw = s.split("\\Q*\\E");
                String s2 = "^i";
                for (String s3 : sw) {
                    s2 += "\\Q" + s3 + "\\E(.+)";
                }
                s2 = s2.substring(0, s2.length() - 4);
                Pattern p = Pattern.compile(s2);
                Matcher m = p.matcher(cur.getPath());
                if (m.find()) {
                    return false;
                }
            }
            return true;
        } catch (Exception e) {
            return true;
        }
    }

    private static HashMap<String, String> getEntitiesFromEnt(String url) throws Exception {
        HashMap<String, String> e = new HashMap<>();
        String ent = downloadString(url);
        while (ent.contains("  ")) ent = ent.replace("  ", " ");
        String[] lines = ent.split("\n");
        for (String line : lines) {
            if (line.startsWith("<!ENTITY")) {
                String[] f = line.split(" ");
                e.put("&" + f[1] + ";", f[3].substring(1, f[3].length() - 1));
            }
        }
        return e;
    }

    private static String downloadString(String url) throws Exception {
        URL cur = new URL(url);
        URLConnection conn = cur.openConnection();
        conn.setRequestProperty("User-Agent", "URLConnection/1.7 (Any system) VardenCG/3.0");
        BufferedReader in = new BufferedReader(new InputStreamReader(conn.getInputStream()));
        String content = "", line;
        while ((line = in.readLine()) != null) content += line + "\n";
        in.close();
        return content;
    }

    private static String stripHTMLEntities(String html) {
        for (Entry<String, String> e : entities.entrySet())
            html = html.replace(e.getKey(), e.getValue());
        Pattern ep = Pattern.compile("&#(\\d+);");
        Matcher m = ep.matcher(html);
        while (m.find()) {
            if (!m.group(1).equals("38"))
                html = html.replace("&#" + m.group(1) + ";", String.valueOf((char)Integer.parseInt(m.group(1))));
        }
        Pattern ep1 = Pattern.compile("&(x|X)([\\da-fA-F]+);");
        Matcher m2 = ep1.matcher(html);
        while (m2.find()) {
            if (!m.group(1).equals("26")) {
                html = html.replace("&x" + m2.group(2) + ";", String.valueOf((char)Integer.parseInt(m2.group(2), 16)));
                html = html.replace("&X" + m2.group(2) + ";", String.valueOf((char)Integer.parseInt(m2.group(2), 16)));
            }
        }
        html = html.replace("&", "\0").replace("&x26;", "\0").replace("&X26;", "\0").replace("\0", "&");
        return html;
    }

    private static String getDomain(String url) throws URISyntaxException {
        URI uri = new URI(url);
        String host = uri.getHost().toLowerCase();
        String[] subDomainTree = host.split("\\.");
        String[] commonSLs = {"ac", "co", "com", "gov", "ltd", "me", "net", "org"};
        boolean isCommonSL = false;
        try {
            String secondLevel = subDomainTree[subDomainTree.length - 2];
            for (String sl : commonSLs) {
                if (sl.equals(secondLevel)) {
                    isCommonSL = true;
                }
            }
        } catch (ArrayIndexOutOfBoundsException ex) {
            return host;
        }
        try {
            if (isCommonSL) {
                return subDomainTree[subDomainTree.length - 3] + "." +
                        subDomainTree[subDomainTree.length - 2] + "." +
                        subDomainTree[subDomainTree.length - 1];
            } else {
                return subDomainTree[subDomainTree.length - 2] + "." +
                        subDomainTree[subDomainTree.length - 1];
            }
        } catch (ArrayIndexOutOfBoundsException ex) {
            return subDomainTree[subDomainTree.length - 2] + "." +
                    subDomainTree[subDomainTree.length - 1];
        }
    }

    private static class IterationInfo {
        public ArrayList<String> domains = new ArrayList<>();
        public ArrayList<String> links = new ArrayList<>();
        public String scanLink = "";
        public int iteration = 1;
        public boolean success = false;
    }

}

```

Parameter used: `http://codegolf.stackexchange.com/`

Output: http://pastebin.no/34cd (Had to post on other site because it was too big for codegolf)

There's a lot of stuff going on here.

First of all, I have to parse HTML entities like &em; &39; and &x2F;. The named entities have to be translated, I do that by downloading the definitions from W3C.

I also need to figure out the host of the URL, taking into account common second level domains like co, edu etc. (.co.uk, .edu.uk, ...)

Then I need to parse robots.txt.

I don't have time to write more now, but oh well, there's my contribution.

-- bilde2910

---
Tags: popularity-contest
---