title: Meta Golf Challenge

text:
# Question
Title: Meta Golf Challenge
On that challenge you have to solve that challenge.

# Contest is over! Check the end of the question

**Specs:**

1. Write the smallest code (Any language\*).
2. The score of an answer is the sum of:
    * Code length **without whitespace**.
    * Number of answers using that same language squared.
    * Length of the name of the biggest language on the contest minus the length of your language.
    * Downvotes minus Upvotes (a.k.a. minus Total of Votes)
3. Write the position of the users and the score.
4. Each user can write only one answer.
5. The lowest score wins.

---

**Testing:**

So, at the end of the contest, a possible input could be (STDIN):

The columns are: Username, Language, Code length(w/o whitespace) and TotalVotes

```
UserA Python 100 1
UserB Perl 30 2
UserC Java 500 3
UserD Brainfuck 499 4
UserE Perl 29 5

```

If your user name has spaces like "My User Name" it'll become "MyUserName" so the input will always have **exactly 4 columns**.

The output will be (STDOUT):

```
1 UserE 33
2 UserB 37
3 UserA 103
4 UserD 496
5 UserC 503

```

Explanation:

```
User  P  N^2  L   V
 A   100  1   3  -1
 B    30  4   5  -2
 C   500  1   5  -3
 D   499  1   0  -4
 E    29  4   5  -5

```

Brainfuck is the largest name with 9 chars (`9 - 9 = 0`).

Perl and Java have 4 chars (`9 - 4 = 5`).

Python has 6 chars (`9 - 6 = 3`).

Perl has 2 entries so each get 4 extra points.

---

**About languages:**

The name of the language must contain only English letters (i.e. \[A-Za-z\]) and those which don't fit that must be "translated" to something else.

By the end of the contest, every language must have it's representation (You may propose better representations)

Examples:

```
Python3      -> Python
Ruby1.9      -> Ruby
Shell Script -> Shell
C++          -> Cpp
C#           -> CSharp
><>          -> Fish

```

---

# Deadline: August 20, 2011 00:00 UTC

> At the end of the contest, the winner must use his/her program to find the winner. It's allowed to non winners to use their programs to find the winner and tell him/her to use his/her program to find the winner. :)

The winner (see above) gets the answer accepted!

\*The Whitespace language has the unfair advantage of being able to introduce unlimited complexity without a penalty on the character count. Answers written in Whitespace may be on the contest but can't win.

If you can make the logic of your program in *whitespaces*, you also can't win. That's a subjective topic, but if your program can increase considerably in size without being penalized, it falls in that condition.

---

# Final Input

Alphabetical order of names (as of Aug 20th 2011 UTC 00:00)

```
boothby Sage 41 9
Harpyon Python 203 4
JBernardo Python 184 7
JoeyAdams PostgreSQL 225 6
jpjacobs AWK 269 4
Lowjacker Ruby 146 2
PeterTaylor Golfscript 82 4
rmackenzie CommonLisp 542 2
shesek Javascript 243 3
userunknown Scala 252 1

```

As both mine and boothby's answers are not allowed to win, the winner should proclaim himself the winner by editing this question and posting the final output below.

# Final Output

```
1 boothby 39
2 PeterTaylor 79
3 Lowjacker 151
4 JBernardo 185
5 Harpyon 207
6 JoeyAdams 220
7 shesek 241
8 userunknown 257
9 jpjacobs 273
10 rmackenzie 541

```

# Answer
> 11 votes
## Golfscript, 83 chars (82 not counting whitespace)

```
n/{},{' ':s/}%.{1=}%\{~~\~\-\.`{=}+4$\,,.*\,-+2${,}%$)\;+[\]}%$\;.,,]zip{~)s@~s@n}%

```

Explanation:

```
# Split the string containing all the input on newlines
n/
# Remove empty lines
{},
# Split each line on spaces (storing the space character in variable s)
{' ':s/}%
# We now have an array of arrays of words. Duplicate it, filter the copy to contain
# only the second word of each array, and reorder with the array of second words first
.{1=}%\
# Map each line
{
    # Unpack the array ["user" "lang" "length" "votes"] and evaluate the integers
    ~~\~\
    # Subtract votes from length and bring "lang" to the top
    -\
    # Create a function to match the string "lang"
    .`{=}+
    # Stack is currently [array of langs] "user" (length-votes) "lang" {"lang"=}
    # Duplicate the array of langs and apply the match function as a filter
    4$\,
    # Get the length of the array of matches and square it
    ,.*
    # Stack is [array of langs] "user" (length-votes) "lang" (num with lang)^2
    # Bring the "lang" to the top, get its length, subtract and add
    \,-+
    # Stack is [array of langs] "user" (score-length of longest lang)
    # Get an array of length of language names and sort it
    2${,}%$
    # Drop it apart from the largest value, and add that to the score
    )\;+
    # Package the "user" score from the top of the stack as [score "user"]
    [\]
}%
# Sort. Since each element is a [score "user"] value, this will sort by score.
$
# Discard the [array of langs].
\;
# Stack is an array of [score "user"] arrays. Get its length and create an array of the
# same length which counts from 0.
.,,
# Group and zip, so we go from [[score0 "user0"] ... [scoren "usern"]] [0 ... n] to
# [[[score0 "user0"] 0] ... [[scoren "usern"] n]]
]zip
# Map each [[scorei "useri"] i]
{
    # Expand, increment i (so we count from 1 rather than 0), add a space
    ~)s
    # Bring the [scorei "useri"] to the top, unpack, add a space
    @~s
    # Bring the scorei to the top, add a newline
    @n
}%
# We now have an array [[1 " " "userA" " " scoreA "\n"] ... [n " " "userZ" " " scoreZ "\n"]
# so Golfscript's standard output formatting does the rest

```

# Answer
> 15 votes
**Sage: 48 42 41 non-whitespace (60246 bytes total)**

Just to be a prick:

```
s = '   '
for c in '<lots of whitespace>'.split(s):
    s+=chr(len(c))
exec s

```

Note that the first line should be equivalent to `s='\t'`, but the SE code block translates the tab to 4 spaces.

The whitespace unpacks to:

```
exec preparse("""
import sys
instances = {}
maxlen = 0
inputs = [line.split() for line in sys.stdin.readlines()]
for i in [0..len(inputs)-1]:
    user, language, length, votes = inputs[i]
    if language in instances:
        instances[language]+=1
    else:
        instances[language]=1
    if len(language) > maxlen:
        maxlen = len(language)

scoresheet = []
for i in [0..len(inputs)-1]:
    user, language, length, votes = inputs[i]
    length = int(length)
    votes = int(votes)
    score = length + (maxlen - len(language)) + instances[language]*instances[language] - votes
    scoresheet.append((score,user))

scoresheet.sort(reverse=False)
for user, score in scoresheet:
    print user, score""")

```

Note that my use of `[0..len(inputs)-1]` ensures that this isn't a Python script, since Sage is a superpython\*. Unfortunately, exec falls back on Python... so I've gotta preparse it.

edit 1: splitting on tabs, not newlines -- what was I thinking? edit 2: made the code easier on the eyes, and recycled the splitting tab by pushing another 'newline' to the whitespace

\*ok, not quite: we break xor

# Answer
> 11 votes
## Python, 184

That's why I love spaces.

```
import          sys
x = sys.stdin.read(
    ).split()
z = x [  1 : : 4  ]
for i , ( j , k
) in enumerate (
      sorted (
       zip (
        [
      int(i)
    - int(j) +
  z.count(k) ** 2
+ max(map(len, z)) -
      len(k)
  for i, j, k in
       zip (
    x[2 : : 4],
    x[3 : : 4],
         z
         )
         ],
     x[ : : 4]
         )
         ),
         1
         ):
   print i, k, j

```

It's much more readable!

# Answer
> 7 votes
## PostgreSQL - 225 non-space characters

**242 → 225:** Replaced subqueries with windowing clauses.

```
\set QUIET 1
\t
\a
\f ' '
CREATE TEMPORARY TABLE t (u TEXT, l TEXT, c INT, v INT);
\copy t FROM PSTDIN WITH DELIMITER ' ';
SELECT row_number() OVER (ORDER BY score), *
    FROM (SELECT u,
                 c
                 + count(*) OVER (PARTITION BY l)^2
                 + max(length(l)) OVER ()
                 - length(l)
                 - v AS score
                 FROM t) AS q

```

*tested on 9.2devel*

### Usage and output:

```
$ psql -f meta.sql < meta.in
1 UserE 33
2 UserB 37
3 UserA 103
4 UserD 496
5 UserC 503

```

# Answer
> 4 votes
## Python 2 - 210 203 non-space characters

```
import sys
e=enumerate
n=len
l=[x.split()for x in sys.stdin.readlines()]
for i,(x,y)in e(sorted((int(x[2])-int(x[3])+n(list(y for y in l if y[1]==x[1]))**2+max(n(x[1])for x in l)-n(x[1]),i)for i, x in e(l))):print i+1,l[y][0],x

```

### Usage and output:

```
$ cat meta.txt | python meta.py
1 UserE 33
2 UserB 37
3 UserA 103
4 UserD 496
5 UserC 503

```

# Answer
> 4 votes
## AWK, 277 269 non-space characters

Used `in` to cut 8 chars.

Spaced version and commented version:

```
{
        # read in user strings
        u[NR]=$0
        # count number of times language has been used
        l[$2]+=1
}

END{
        # get maximum language length
        M=0
        X=NR
        for (g in l){
                f=length(g)
                if(f>M)
                        M=f
        }
        # get score for user i
        for(i in u){
                split(u[i],c)
                s[i]=c[3]+l[c[2]]^2+M-length(c[2])-c[4]
        }
        # sort scores and users
        for(i=2;i<=X;++i){
                for(j=i;s[j-1]>s[j];--j){
                        t=s[j]
                        x=u[j]
                        s[j]=s[j-1]
                        u[j]=u[j-1]
                        s[j-1]=t
                        u[j-1]=x
                }
        }
        # output
        for(i=1;i<=X;++i){
                split(u[i],c)
                print i,c[1],s[i]
        }
}

```

usage:

```
awk -f meta.awk data.txt

```

# Answer
> 4 votes
# Common Lisp - 546

**(when golfed boy consolidating parenthesis, not counting spaces)**

```
;;;; This is an answer to Code-Golf question
;;;; 3203/meta-golf-challenge
;;;; By using Common Lisp I plan to have the longest
;;;; Language-name while I cannot hope to have the
;;;; lowest character count due to Lisp's
;;;; linguistic tradition I can avoid the 16 or 25-pt
;;;; penalty atached to being the 4th or 5th PY
;;;; based answer.

(defun f (i)
 (loop for e in y do
  (if (eq i (nth 0 e))
   (return (nth 1 e))
  )
 )
)

(setf x
 (loop for l = (read-line () () () ())
  while l collect (loop for i = 0 then (1+ j)
                   as j = (position #\Space l :start i)
                   collect (subseq l i j) while j)
 )
)

(setf y
 (loop for a in x collect
  (list
   (+
    (read-from-string (nth 2 a))
    (expt (reduce #'+ (loop for b in x collect (if (string= (nth 1 a) (nth 1 b)) 1 0) ) ) 2 )
    (+ 5 (- (reduce #'min (loop for b in x collect (length (nth 1 b)))) (length (nth 1 a))))
    (* -1 (read-from-string (nth 3 a)))
   )
   (car a)
  )
 )
)

(setf g
 (sort (loop for c in y collect (nth 0 c)) #'<)
)

(loop for i = 0 then (1+ i) while (< i (length g)) do
 (setf a (nth i g))
 (format t "~A ~A ~A~%" (1+ i) (f a) a)
)

```

Heavily golfed, my common lisp solution was and is the longest on the board. So I decided to cheat a bit by writing a significantly shorter bootloader and claiming that as my submission. ~~(I consider @Boothby's submission to be a precedent in favor of this behavior)~~

Major thanks to **Peter Taylor** for his help squeezing every last char out of this bootstrapper.

# BASH - 35

```
wget -q goo.gl/R4R54
cat -|clisp l.lsp

```

**Usage**: cat ./test0 | bash ./btstrp.sh

**Joey Adams** pointed out that this is not a fair solution because I can "arbitrarily increase the complexity of your solution without a corresponding increase in code size", a point not clearly expressed in the spec.

# Answer
> 3 votes
## Ruby, 146 characters + 4 spaces

```
b=$<.map &:split
puts b.map{|u,l,c,v|[b.map{|_,n|n.size}.max-l.size+b.count{|_,n|n==l}**2+eval(c+?-+v),u]}.sort.map.with_index{|(s,u),i|[i+1,u,s]*' '}

```

# Answer
> 3 votes
# JavaScript, 243 chars

```
for(g=0,H="length",i=J.split("\n"),p=[],l={};i[H]&&p.push(a=i.pop().split(" "));)
    X=a[1],X[H]>g&&(g=X[H]),l[X]=l[X]+1||1
for(i=-1;m=p[++i];)p[i]=[m[0],+m[2]+Math.pow(l[m[1]],2)+(g-m[1][H])-m[3]]
p.sort(function(a,b){return a[1]<b[1]?-1:1}).join("\n")

```

Longer than most of the other solutions... but the best I could come up with in JavaScript.

## Usage

Input should be in a J variable. For example, open a console and write:

```
J="UserA Python 100 1\nUserB Perl 30 2\nUserC Java 500 3\nUserD Brainfuck 499 4\nUserE Perl 29 5";
for(g=0,H="length",i=J.split("\n"),p=[],l={};i[H]&&p.push(a=i.pop().split(" "));)
    X=a[1],X[H]>g&&(g=X[H]),l[X]=l[X]+1||1
for(i=-1;m=p[++i];)p[i]=[m[0],+m[2]+Math.pow(l[m[1]],2)+(g-m[1][H])-m[3]]
p.sort(function(a,b){return a[1]<b[1]?-1:1}).join("\n")

```

# CoffeScript, 177 chars

About the same logic, in CoffeScript:

```
g=0;H="length";l={};([A,+C+Math.pow(l[B],2)+(g-B[H])-D] for [A,B,C,D] in for a in J.split "\n" then [_,X]=a=a.split " ";X[H]>g&&g=X[H];l[X]=l[X]+1||1;a).sort((a,b)->`a[1]<b[1]?-1:1`).join "\n"

```

# Answer
> 3 votes
# Scala 269 266 252 without blanks and newlines.

```
val b = io.Source.stdin.getLines.toList.map (_.split (" "))
b.map (a => {
  val l = b.filter (_(1) .equals ( a(1))).size
  a(0) -> (a (2).toInt + l * l + (b.map (x => x(1).length).max - a(1).length) - a(3).toInt)
}).sortBy (_._2).zipWithIndex .map (m => m._2 + " " + m._1._1 + " "+ m._1._2).mkString ("\n")

```

Invocation:

```
cat user.lst | scala -i metagolf.scala

```

### updates:

* simplified (l =\> l.foo) -\> (\_.foo)
* invocation
* Gareths hint of stdin

my solution:

```
* 0 boothby 39
1 PeterTaylor 79
2 Lowjacker 151
* 3 JBernardo 185
4 Harpyon 207
5 JoeyAdams 220
6 shesek 241
7 userunknown 257
8 jpjacobs 273
9 rmackenzie 541

```

\*) out of contest

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


title: Program to Spoonerise words

text:
# Question
Title: Program to Spoonerise words
A spoonerisation is swapping the first letter/pronounceable syllable of two or more words.

**Example**: A lack of pies = A pack of lies. Bad salad = Sad ballad (ish) :)

Challenge: Write a program to spoonerise two words in the shortest characters possible.

Rules:

1. If the first letter is a consonant, you must include subsequent letters until you reach a vowel. (e.g. 'thanks' - the th gets removed and put on the front of the other word).
2. With words that start with vowels, do not remove anything from the start of the word.

Good luck :)

---

**UPDATE:** Multiple word spoonerisms are not strictly applicable, however from a programatic view we must cater for them so this is the rule: **Every word must change.** Example:

Weird Keen Monkey -\> Meird Ween Konkey **OR** Keird Meen Wonkey **NOT** Meird **Keen** Wonkey

Also 'y' is treated as a **vowel** (just to simplify things a bit)

# Answer
> 3 votes
## Ruby (60) (61) (93) (80) (75) (71) (69 / 57)

Program changed to handle the new requirement of handling multiple words.

EDIT: Golfed down to 80. 75. 71. 69.

```
w=[];gets.gsub(/(\S*?)([aeiouy]\S*)/i){w+=[$2,' ',$1]};$><<w.pop+w*''

```

If we're only spoonerizing words that start with a consonant, here's a solution in 73. 65. (I realized I can just use scan instead of gsub.) 57.

```
$><<gets.gsub(p=/\b[^aeiouy\s]+/i){($'+$`+$&).scan(p)[0]}

```

Old program (two words only):

```
p='(.*?)([aeiou].+)';puts gets.gsub(/#{p} #{p}/i,'\3\2 \1\4')

```

# Answer
> 1 votes
## Haskell, 81

```
f[(a,b),(c,d)]=unwords[c++b,a++d]
main=interact$f.map(break(`elem`"aeiou")).words

```

# Answer
> 1 votes
## Ruby, 57 56

This only works for the original problem (with only two words).

```
$><<gets.sub(/#{r='([^aeiou]*)(.+)'} #{r}/i,'\3\2 \1\4')

```

# Answer
> 1 votes
## Perl, 43 (question v1), 91 79 (question v2) \[107 to handle numerals in the phrase\]

**v1**

Run with `-p` option (counted as 3 chars).

```
$p='([^aeiou]*)(.+)';s/$p $p/$3$2 $1$4/i

```

Same technique as the Ruby answers.

Using `-p` saves 9 characters over bracketing the code with `$_=<>;` and `;print` for explicit IO.

**v2**

Run with `-lp` (counted as 4 chars).

```
push@a,$1while s/\b([^ aeiouy\d]+)(?=[aeiouy])/$n++/ei;unshift@a,pop@a;s/(\d+)/$a[$1]/g

```

Rotates all the consonant-starts of words one word forward.

*Updated:* Add vowel lookahead, so it handles "to the nth degree" more gracefully ("do te nth thegree", not "do te th nthegree").

*Numerals:* user unknown asked about handling "There is no winner in 2011", because of the numerals. Adding markers around the numbers my solution uses, it can handle that:

```
push@a,$1while s/\b([^ aeiouy\0\d]+)(?=[aeiouy])/"\0".$n++."\0"/ei;unshift@a,pop@a;s/\0(\d+)\0/$a[$1]/g

```

Small question, big discussion....

# Answer
> 1 votes
## J, 77

*Answers the original version of the question, "spoonerise two words"; a solution for the changed question may follow.*

Couldn't shrink this to compete with the Ruby answers, so fell back on my more-familiar Perl.

```
exit([:;3 1 2 0 4{[:,({.@I.@e.&'aeiouAEIOU'({.;' ';~}.)]);._2@,&' ')&.stdin''

```
* `,&' '` appends a space
* `(`...`);._2` splits on the last character (the space) and applies the parenthesized code to each element (i.e., each word)
* `{. @ I. @ e.&'aeiouAEIOU'` finds the index of the first vowel in that word
* `({.;' ';~}.)` splits the word into leading consonants (if any) and a tail, with a space at the end (each in a "box", so J doesn't pad them to matching lengths)
* `,` flattens the 2r x 3c matrix formed by the preceding into a 6-element list
* `3 1 2 0 4{` takes all those elements but the trailing space, swapping the lead segments of the words
* `;` unboxes and concatenates the elements
* `(`...`)&.stdin''` does roughly the same as Perl's `-p`, reading stdin and echoing the result of "..." to stdout
* the explicit `exit` suppresses J's prompt for more input

# Answer
> 0 votes
### CSharp - 236

```
List<string> f(string w) {var t="aeiou".ToCharArray();var q=w.Split(' ').Where(c=>!t.Contains(c[0]));var i=q.Count()-1;return q.Select(c=>q.Select(x=>x.Substring(0,x.IndexOfAny(t))).ToList()[i--]+c.Substring(c.IndexOfAny(t))).ToList();}

```

# Answer
> 0 votes
## Scala 244

```
val s=readLine
def f(a:String,b:String)=a.replaceAll("^[^aeiouy]+",b.replaceAll("[aeiouy].*",""))
val l=("((^| )[^aeiouyAEIOUY]+)([^ ]+)".r findAllIn s map(_.trim)).toList
println(s.replaceAll(l(0),f(l(0),l(1))).replaceAll(l(1),f(l(1),l(0))))

```

My code contains 4 `y` (one of them lowercase) to handle `why` and `rythm` in a useful manner.

---

### Scala 248, updated for new challenge (change *all* consonantic words)

```
val w=readLine.split(" ")
val c=w.filter(_.matches("[^aeiouyAEIOUY].*"))
val l=c.size
var k=0
println((for(i<-0 to w.size-1)yield{if(w(i)==c(k%l)){k+=1
c(k-1).replaceAll("^[^aeiouy]+",c(k%l).replaceAll("[aeiouy].*",""))}else w(i)}).mkString(" "))

```

### ungolfed, and test cases:

```
val samples = List ("bad salad", "I tell smooth", "Sentence with vowel in the end", "tain bruck is faboo")
def konsInit (s: String) = s.matches ("[^aeiouyAEIOUY].*")
def flipInit (a: String, b: String) = a.replaceAll ("^[^aeiouy]+", b.replaceAll ("[aeiouy].*", ""))
def spoonize (sentence: String) {
  val words = sentence.split (" ")
  val kwords = words.filter (konsInit);
  val len = kwords.size
  var k = 0
  val spoonies = for (i <- 0 to words.size-1) yield {
    if (words (i) == kwords (k%len)) {
      k += 1
      flipInit (kwords (k-1), kwords (k%len))
    } else words (i)
  }
  println (spoonies.mkString (" "))
}
samples.foreach (spoonize)

```

> sad balad
> I smell tooth
> wentence vith thowel in Se end

The last example can't be shown.

---
Tags: code-golf, string, word-puzzle, natural-language
---


title: What comes next?

text:
# Question
Title: What comes next?
Given a space-separated list of integers, your task is to find the next integer in the sequence. Each integer in the sequence is the result of applying a single mathematical operation(`+`,`-`,`*` or `/`) to the previous integer, and each sequence is made up of a variable number of such operations (but no more than 10). No sequence will be longer than half the length of the sequence of integers, so you'll have each sequence of operations appear at least twice for confirmation.
**Input** will be via stdin (or `prompt` for JavaScript solutions).

Here are some explanatory examples.

**Input:**

```
1 3 5 7 9 11

```

**Output:**

```
13

```

Fairly easy, this one. All values are previous value `+2`.

**Input:**

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

```

**Ouput:**

```
8

```

Two steps in this sequence, `+2` then `-1`.

**Input:**

```
2 6 7 3 9 10 6 18 19 15 45 46

```

**Output:**

```
42

```

Three steps - `*3`, `+1`, `-4`.

## Test cases

Here are few more test cases:

Input:

```
1024 512 256 128 64 32 16

```

Output:

```
8

```

Input:

```
1 3 9 8 24 72 71 213 639

```

Output:

```
638

```

Input:

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

```

Output:

```
4

```

Input:

```
1 2 4 1 3 9 5 8 32 27 28 56 53 55 165 161 164 656 651 652 1304

```

Output:

```
1301

```

I have an ungolfed Scala solution (42 lines) that I will post in a couple of days.

This is code-golf - shortest answer wins.

# Answer
> 12 votes
## Golfscript, 203 138 chars

```
~]0{).2$.);[\(;]zip\/zip{.{~-}%.&({-}+\{;{.0={.~\%{.~%{;0}{~/{/}+}if}{~\/{*}+}if}{~!{;}*}if}%.&(\{;;0}/}{\;}if}%.{!}%1?)!{0}*}do\@)\,@%@=~

```

This uses far more `if`s than a standard Golfscript program, and its operation is pretty cryptic, so here's a commented (but not ungolfed other than by the addition of whitespace and comments) version:

```
~]0
# Loop over guesses L for the length of the sequence
{
    # [x0 ... xN] L-1
    ).
    # [x0 ... xN] L L
    2$.);[\(;]zip
    # [x0 ... xN] L L [[x0 x1][x1 x2]...[x{N-1} xN]]
    \/zip
    # [x0 ... xN] L [[[x0 x1][xL x{L+1}]...][[x1 x2][x{L+1} x{L+2}]...]...]
    {
        # [x0 ... xN] L [[xi x{i+1}][x{i+L} x{i+L+1}]...]
        # Is there an operation which takes the first element of each pair to the second?
        # Copy the pairs, work out each difference, and remove duplicates
        .{~-}%.&
        # Turn the first difference into an operation
        ({-}+\
        # If there was more than one unique difference, look for a multiplication
        {
            ;
            # [x0 ... xN] L [[xi x{i+1}][x{i+L} x{i+L+1}]...]
            # Do something similar, but working out multiplicative factors
            # Note that if we have [0 0] it could be multiplication by anything, so we remove it.
            # However, they can't all be [0 0] or we'd have only one unique difference
            {
                # [0     0   ] =>
                # [0     _   ] => 0     # a "false" value, because it can't possibly be multiplication
                # [a     a.b'] => {b'*}
                # [a'.b  b   ] => {a'/}
                # [_     _   ] => 0     # ditto
                # This is the obvious place to look for further improvements
                .0={.~\%{.~%{;0}{~/{/}+}if}{~\/{*}+}if}{~!{;}*}if
            }%.&
            # If we have one unique multiplication, even if it's false, keep it.
            # Otherwise discard them and replace them with false.
            (\{;;0}/
        }
        # There was only one unique difference. Discard the pairs
        {\;}if
        # operation - one of 0, {d+}, {m*}, {M/}
    }%
    # [x0 ... xN] L [op0 ... op{L-1}]
    # Is any of the operations false, indicating that we couldn't find a suitable operation?
    .{!}%1?
    # [x0 ... xN] L [op0 ... op{L-1}] idxFalse
    # If idxFalse is -1 then all the ops are ok, and we put a false to exit the loop
    # Otherwise one op failed, so we leave the array of ops, which is non-false, to be popped by the do.
    )!{0}*
}do
# [x0 ... xN] L [op0 ... op{L-1}]
\@)\,@%@=~
# op{(len(Xs)-1)%L} (Xs[-1])

```

My original submission was the following at 88 chars:

```
~]:x;2.{;).(2base(;{[{--}{@*\.!+/}]=}%[x.(;2$]zip\,<{~++}%x,.@[*x\]zip<{~~}%)\x(;=!}do\;

```

However, this tries to calculate the operations from the first occurrence of each, so if the operation is multiplication or division and the argument the first time round is 0 it breaks.

# Answer
> 6 votes
## Haskell, ~~276~~ ~~261~~ ~~259~~ ~~257~~ 243 characters

Here is my inefficient solution. It works on unbounded (and bounded) integers. This solution happens to work correctly with non-exact division (eg: `5 / 2 = 2`).

```
import Control.Monad
main=interact$show.n.q read.words
f=flip
q=map
_%0=0
x%y=div x y
s b=[1..]>>=q cycle.(f replicateM$[(+),(*),(%)]>>=f q[-b..b].f)
m l x s=[y!!l|y<-[scanl(f($))(x!!0)s],x==take l y]
n x=(s(maximum$q abs x)>>=m(length x)x)!!0

```

How it works: I create every possible sequence of (possible) operations. Then I test against the input sequence of numbers to see if the generated sequence will create the input. If it does, return the next number in the sequence. The code will always return an answer that is derived from a shortest sequence of operations. This happens because the list of operation sequences is generated in that order. It's arbitrary (but consistent) on deciding between ties. For example the code returns `6` or `8` for the sequence `2 4`.

Ungolfed:

```
import Control.Monad

main :: IO ()
main = print . next . map read . words =<< getLine

opSequences :: Integral a => a -> [[a -> a]]
opSequences bound = [1 ..] >>= map cycle . (`replicateM` (ops >>= (`map` args) . flip))
  where
    ops = [(+), (*), \x y -> if y == 0 then 0 else div x y]
    args = [-bound .. bound]

match :: (MonadPlus m, Integral a) => [a] -> [a -> a] -> m a
match ns opSeq = guard (ns == take len ms) >> return (ms !! len)
  where
    n0 = ns !! 0
    len = length ns
    ms = scanl (flip ($)) n0 opSeq

next :: Integral a => [a] -> a
next ns = (opSequences bound >>= match ns) !! 0
  where
    bound = maximum $ map abs ns

```

# Answer
> 6 votes
**Python, ~~333~~ ~~366~~ ~~...~~ ~~315~~ ~~303~~ ~~278~~ ~~269~~ ~~261~~ 246 chars**

```
n=map(float,raw_input().split())
y=len(n)-1
l=1
def O(f):
 p,q=n[f:y:l],n[f+1::l]
 for a,b in zip(p,q):
    for x in((b-a).__add__,(b/(a or 1)).__mul__):
     if map(x,p)==q:return x
while 1:
 if all(map(O,range(l))):print int(O(y%l)(n[y]));break
 l+=1

```

Creates operation with first pair of numbers and check it on other pairs. Stores all operations, and if all of them succeed then applies appropriate operation on list last element.

Edited: passes evil test:-) Now search for operation on all positions.

# Answer
> 4 votes
## Python, 309 305 295 279 chars

Handles all of the original test cases, as well as Peter Taylor's gnarly `0 0 1 2 3 6 7 14` one:

```
l=map(int,raw_input().split())
i=v=0
while v<1:
 v=i=i+1
 for j in range(i):
    p=zip(l[j::i],l[j+1::i])
    d,r=set(q[1]-q[0]for q in p),set(q[1]*1./(q[0]or 1)for q in p if any(q))
    m,n=len(d)<2,len(r)<2
    v*=m+n
    if(len(l)-1)%i==j:s=l[-1]+d.pop()if m else int(l[-1]*r.pop())
print s

```

Ungolfed, with debugging output (very helpful in verifying correctness):

```
nums = map(int,raw_input().split())
result = None

for i in range(1,len(nums)/2+1):
    print "-- %s --" % i
    valid = 1
    for j in range(i):
        pairs = zip(nums[j::i], nums[j+1::i])
        print pairs

        diffs = [pair[1] - pair[0] for pair in pairs]
        # this is the tough bit: (3, 6) -> 2, (0, 5) -> 5, (5, 0) -> 0, (0, 0) ignored
        ratios = [float(pair[1])/(pair[0] or 1) for pair in pairs if pair[0] != 0 or pair[1] != 0]

        if len(set(diffs))==1:
            print "  can be diff", diffs[0]
            if (len(nums) - 1) % i == j:
                result = nums[-1] + diffs.pop()
        elif len(set(ratios))==1:
            print "  can be ratio", ratios[0]
            if (len(nums) - 1) % i == j:
                result = int(nums[-1]*ratios.pop())
        else:
            print "** invalid period **"
            valid=0
    if valid and result is not None:
        break

print result

```

Usage:

```
echo 0 0 1 2 3 6 7 14 | python whatcomesnext.py

```

# Answer
> 3 votes
## Ruby 1.9 (437) (521) (447) (477)

Works for all test cases, including the "evil" one. I'll golf it more later.

EDIT: I realized there's another case that I wasn't handling properly - when the continuation needs to use the "mystery" operation. The sequence `2 0 0 -2 -4 -6` was initially returning 0 instead of -12. I've now fixed that.

EDIT: Fixed a couple more edge cases and cut down the code to 447.

EDIT: Ugh. Had to add some code to handle other "evil" sequences such as `0 0 0 6 18 6 12`

```
def v(c,q);t=*q[0];q.size.times{|i|f=c[z=i%k=c.size]
f=c[z]=(g=q[z+k])==0??_:((h=q[z+k+1])%g==0?"*(#{h/g})":"/(#{g/h})")if f==?_
t<<=f==?_?(a=q[i];b=q[i+1].nil?? 0:q[i+1];(a==0&&b==0)||(a!=0&&(b%a==0||a%b==0))?b:0):eval(t.last.to_s+f)}
*r,s=t
(p s;exit)if q==r
end
s=gets.split.map &:to_i
n=[[]]
((s.size-1)/2).times{|i|a,b=s[i,2]
j=["+(#{b-a})"]
j<<=?_ if a==0&&b==0
j<<="*#{b/a}"if a!=0&&b%a==0
j<<="/#{a/b}"if a*b!=0&&a%b==0
n=n.product(j).map(&:flatten)
n.map{|m|v(m*1,s)}}

```

# Answer
> 1 votes
## Scala

This is the solution I came up with:

```
object Z extends App{var i=readLine.split(" ").map(_.toInt)
var s=i.size
var(o,v,f)=(new Array[Int](s),new Array[Double](s),1)
def d(p:Int,j:Array[Int]):Unit={if(p<=s/2){def t(){var a=new Array[Int](s+1)
a(0)=i(0)
for(l<-0 to s-1){o(l%(p+1))match{case 0=>a(l+1)=a(l)+v(l%(p+1)).toInt
case _=>a(l+1)=(a(l).toDouble*v(l%(p+1))).toInt}}
if(a.init.deep==i.deep&&f>0){f^=f
println(a.last)}}
o(p)=0
v(p)=j(1)-j(0)
t
d(p+1,j.tail)
o(p)=1
v(p)=j(1).toDouble/j(0).toDouble
t
d(p+1,j.tail)}}
d(0,i)
i=i.tail
d(0,i)}

```

Ungolfed:

```
object Sequence extends App
{
    var input=readLine.split(" ").map(_.toInt)
    var s=input.size
    var (ops,vals,flag)=(new Array[Int](s),new Array[Double](s),1)
    def doSeq(place:Int,ints:Array[Int]):Unit=
    {
        if(place<=s/2)
        {
            def trysolution()
            {
                var a=new Array[Int](s+1)
                a(0)=input(0)
                for(loop<-0 to s-1)
                {
                    ops(loop%(place+1))match
                    {
                        case 0=>a(loop+1)=a(loop)+vals(loop%(place+1)).toInt
                        case _=>a(loop+1)=(a(loop).toDouble*vals(loop%(place+1))).toInt
                    }
                }
                if(a.init.deep==input.deep&&flag>0)
                {
                    flag^=flag
                    println(a.last)
                }
            }
            ops(place)=0
            vals(place)=ints(1)-ints(0)
            trysolution
            doSeq(place+1,ints.tail)
            ops(place)=1
            vals(place)=ints(1).toDouble/ints(0).toDouble
            trysolution
            doSeq(place+1,ints.tail)
        }
    }
    doSeq(0,input)
    input=input.tail
    doSeq(0,input)
}

```

# Answer
> 1 votes
### Scala 936

```
type O=Option[(Char,Int)]
type Q=(O,O)
type L=List[Q]
val N=None
def t(a:Int,b:Int):Q=if(a>b)(Some('-',a-b),(if(b!=0&&b*(a/b)==a)Some('/',a/b)else N))else
(Some('+',b-a),(if(a!=0&&a*(b/a)==b)Some('*',b/a)else N))
def w(a:Q,b:Q)=if(a._1==b._1&&a._2==b._2)a else
if(a._1==b._1)(a._1,N)else
if(a._2==b._2)(N,a._2)else(N,N)
def n(l:L):Q=l match{case Nil=>(N,N)
case x::Nil=>x
case x::y::Nil=>w(x,y)
case x::y::xs=>n(w(x,y)::xs)}
def z(l:L,w:Int)=for(d<-1 to w)yield
n(l.drop(d-1).sliding(1,w).flatten.toList)
def h(s:L):Boolean=s.isEmpty||(s(0)!=(N,N))&& h(s.tail)
def j(s:L,i:Int=1):Int=if(h(z(s,i).toList))i else j(s,i+1)
def k(b:Int,o:Char,p:Int)=o match{case'+'=>b+p
case'-'=>b-p
case'*'=>b*p
case _=>b/p}
val e=getLine
val i=e.split(" ").map(_.toInt).toList
val s=i.sliding(2,1).toList.map(l=>t(l(0),l(1)))
val H=n(s.drop(s.size%j(s)).sliding(1,j(s)).flatten.toList)
val c=H._1.getOrElse(H._2.get)
println (k(i(i.size-1),c._1,c._2))

```

ungolfed:

```
type O = Option[(Char, Int)]

def stepalize (a: Int, b: Int): (O, O) = (a > b) match {
   case true => (Some('-', a-b), (if (b!=0 && b * (a/b) == a) Some ('/', a/b) else None))
   case false=> (Some('+', b-a), (if (a!=0 && a * (b/a) == b) Some ('*', b/a) else None)) }

def same (a: (O, O), b: (O, O)) = {
  if (a._1 == b._1 && a._2 == b._2) a else
  if (a._1 == b._1) (a._1, None) else
  if (a._2 == b._2) (None, a._2) else
  (None, None)}

def intersection (lc: List[(O, O)]): (O, O) = lc match {
  case Nil => (None, None)
  case x :: Nil => x
  case x :: y :: Nil => same (x, y)
  case x :: y :: xs  => intersection (same (x, y) :: xs)}

def seriallen (lc: List[(O, O)], w: Int= 1) =
  for (d <- 1 to w) yield
    intersection (lc.drop (d-1).sliding (1, w).flatten.toList)

def hit (s: List[(O, O)]) : Boolean = s match {
  case Nil => true
  case x :: xs => (x != (None, None)) && hit (xs)}

def idxHit (s: List[(O, O)], idx: Int = 1) : Int =
  if (hit (seriallen (s, idx).toList)) idx else
    idxHit (s, idx+1)

def calc (base: Int, op: Char, param: Int) = op match {
  case '+' => base + param
  case '-' => base - param
  case '*' => base * param
  case _   => base / param}

def getOp (e: String) = {
  val i = e.split (" ").map (_.toInt).toList
  val s = i.sliding (2, 1).toList.map (l => stepalize (l(0), l(1)))
  val w = idxHit (s)
  val hit = intersection (s.drop (s.size % w).sliding (1, w).flatten.toList)
  val ci = hit._1.getOrElse (hit._2.get)
  val base = i(i.size - 1)
  println ("i: " + i + " w: " + w + " ci:" + ci + " " + calc (base, ci._1, ci._2))
}

val a="1 3 5 7 9 11"
val b="1 3 2 4 3 5 4 6 5 7 6"
val c="2 6 7 3 9 10 6 18 19 15 45 46"
val d="1024 512 256 128 64 32 16"
val e="1 3 9 8 24 72 71 213 639"
val f="1 2 3 4 5 2 3 4 5 6 3 4 5 6 7"
val g="1 2 4 1 3 9 5 8 32 27 28 56 53 55 165 161 164 656 651 652 1304"
val h="0 0 1 2 3 6 7 14"
val i="0 0 0 0 1 0 0 0 0 1 0"

List (a, b, c, d, e, f, g, h, i).map (getOp)

```

Fails miserably on Peter Taylor's `h`, but I don't see the possibility to heal the program in a reasonable amount of time.

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


# Question
Title: Descending Sort using Standard Ascending Sort Function
Taking an array of records. For example

```
[
name: 'eventA', timestamp: '2011-08-27 15:34:00',
name: 'eventB', timestamp: '2011-08-28 13:31:00',
name: 'eventC', timestamp: '2011-08-29 10:34:00',
name: 'eventD', timestamp: '2011-08-30 16:36:00',
]

```

How can I sort these by timestamp in a descending using a standard natural ascending sort algorithm built into most languages. E.g.

E.g C#: `collection.Sort(record => record.timestamp)` Python: `sort(collection, lambda record: record.timetstamp)`

You can not use the `sortByDescending` methods, of course most languages have them (or a flag to sort fn for descending)

Somehow have to transform the `record.timestamp` so that it sorts descending

Solution 1: Parse the date into a Date object provided by most languages and get time in milliseconds/seconds since 1970. Minus the amount from 0 to get the negated value and sort by this.

Extra points for no expensive date conversions

# Answer
## Haskell

```
sortByDescending cmp = sortBy (flip cmp)

```

### Example:

```
import Data.List
import Data.Function
import Data.Maybe
import Data.Time.LocalTime
import Data.Time.Parse      -- requires module strptime

data Record = Record {
    name      :: String,
    timestamp :: LocalTime
} deriving Show

sortByDescending cmp = sortBy (flip cmp)

sortByTimestampDescending :: [Record] -> [Record]
sortByTimestampDescending = sortByDescending (compare `on` timestamp)

parseExample :: (String, String) -> Record
parseExample (n,t) = Record n (fst $ fromJust $ strptime "%Y-%m-%d %H:%M:%S" t)

examples :: [Record]
examples = map parseExample
    [("eventA", "2011-08-27 15:34:00")
    ,("eventB", "2011-08-28 13:31:00")
    ,("eventC", "2011-08-29 10:34:00")
    ,("eventD", "2011-08-30 16:36:00")]

main = mapM_ print $ sortByTimestampDescending examples

```

### Output:

```
Record {name = "eventD", timestamp = 2011-08-30 16:36:00}
Record {name = "eventC", timestamp = 2011-08-29 10:34:00}
Record {name = "eventB", timestamp = 2011-08-28 13:31:00}
Record {name = "eventA", timestamp = 2011-08-27 15:34:00}

```
> 4 votes

# Answer
## D

```
retro(sort!"a.timestamp<b.timestamp"(array));

```

or

```
retro(schwartzSort!"a.timestamp"(array));

```

(you need to import std.algorithm and std.range)

though honestly reversing an array without a build-in function is simple as it is

```
int i=0,j=arr.length;while(i<--j)swap(arr[i++],arr[j]);

```

or without a swap function:

```
int i=0,j=arr.length;while(i<--j){auto tmp=arr[i];arr[i++]=arr[j];arr[j]=tmp;}

```
> 0 votes

# Answer
### Scala:

```
val src = """name: 'eventA', timestamp: '2011-08-27 15:34:00', name: 'eventB', timestamp: '2011-08-28 13:31:00', name: 'eventC', timestamp: '2011-08-29 10:34:00', name: 'eventD', timestamp: '2011-08-30 16:36:00'"""

class NT (name: String, val n: String, time: String, val ts: String)
val nts = src.split ("[,:] ").sliding (4, 4).map (l =>
    new NT (l(0), l(1), l(2), l(3))).toList
nts.sortWith ((a, b) => a.ts < b.ts).reverse.foreach (k =>
    println (k.ts + " " + k.n))

```

Result:

```
'2011-08-30 16:36:00' 'eventD'
'2011-08-29 10:34:00' 'eventC'
'2011-08-28 13:31:00' 'eventB'
'2011-08-27 15:34:00' 'eventA'

```
> 0 votes

---
Tags: code-challenge, sorting, rosetta-stone
---


title: Maximize order of operations

text:
# Question
Title: Maximize order of operations
Here's a problem to which I don't know the answer. Suppose you have an ordered list of integers with an operator in between each consecutive pair. Let's restrict ourselves to three operations that are closed over the integers, namely addition, multiplication and subtraction. Is there a good way to find the order we should perform the operations such that the expression evaluates to the maximum value?

For example, given the input `5 * 5 - 3 + 8 * -2` the correct order is to first perform the addition leading to `5 * 5 - 11 * -2`, then perform the last multiplication leading to `5 * 5 - -22`, then perform the subtraction leading to `5 * 27`, then perform the final multiplication giving `135`, which is maximal.

The question is: does there exist a reasonably efficient way to find this answer? I can see some tricks that might help a little, but I can also see some roadblocks.

Here's a program in python that computes the solution in the dumb recursive O(2^n) fashion. It might be helpful to check answers.

```
def find_max(x):
    if len(x) == 1:
        return x[0]
    y = [find_max(contract(x, i)) for i in xrange(len(x)//2)]
    return max(y)

def contract(x, i):
    return x[:2*i] + [do_op(*x[2*i:2*i + 3])] + x[2*i + 3:]

def do_op(left, op, right):
    return {"+": left + right, "-": left - right, "*": left * right}[op]

init = [int(x) if i%2 == 0 else x for i,x in enumerate(raw_input().split())]
print find_max(init)

```

Usage: `python findmax.py < in.txt` where `in.txt` contains a sequence like `4 * -3 + 6 - 2 * 10`.

Is there a significantly faster way?

# Answer
## Haskell, *O*(n3)

```
import Data.Array

data Op = Plus | Minus | Times

exampleTerms :: [Integer]
exampleTerms = [5, 5, 3, 8, -2]

exampleOps :: [Op]
exampleOps = [Times, Minus, Plus, Times]

main = print $ maximalOrder exampleTerms exampleOps

type MinMax = (Integer, Integer)

-- Given an operator and minimal/maximal values for left- and right-hand sides,
-- compute the minimal/maximal value of the expressions joined together with this operator.
combine :: Op -> MinMax -> MinMax -> MinMax
combine Plus  (lmin, lmax) (rmin, rmax) = (lmin + rmin, lmax + rmax)
combine Minus (lmin, lmax) (rmin, rmax) = (lmin - rmax, lmax - rmin)
combine Times (lmin, lmax) (rmin, rmax) = (minimum ps, maximum ps)
    where ps = [lmin * rmin, lmin * rmax, lmax * rmin, lmax * rmax]

maximalOrder :: [Integer] -> [Op] -> Integer

maximalOrder []    _                 = error "maximalOrder: No terms"
maximalOrder terms ops
    | length terms /= length ops + 1 = error "maximalOrder: Mismatched terms/ops lists."

maximalOrder terms ops = snd $ minMax 0 (termCount - 1) where
    termCount :: Int
    termCount = length terms

    termsA :: Array Int Integer
    termsA = array (0, termCount-1) $ zip [0..] terms

    opsA :: Array Int Op
    opsA = array (0, termCount-2) $ zip [0..] ops

    dp :: Array (Int, Int) MinMax
    dp = array ((0,0), (termCount-1,termCount-1))
         [((start, end), minMax start end)
             | start <- [0..termCount-1], end <- [start..termCount-1]]

    minMax :: Int -> Int -> MinMax
    minMax start end
        | start == end =
            let x = termsA ! start
            in (x,x)
        | otherwise =
            let xs = [combine (opsA ! i) (dp ! (start,i)) (dp ! (i+1,end)) | i <- [start..end-1]]
            in (minimum (map fst xs), maximum (map snd xs))

```

This computes the minimal and maximal values of every substring in the expression, by going through each intervening operator and finding the minimal/maximal result of treating that operator as the root of the expression. It collects these results into the overall minimal and maximal values for this substring.

This algorithm runs in O(n3) time and uses O(n2) space. Finding the minimal/maximal value of an expression string, once its substrings have been visited, takes O(*len*), where *len* is the length of the substring. The minimal/maximal value of every substring needs to be computed:

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

```

In this case, it takes 5\*1 + 4\*2 + 3\*3 + 2\*4 + 1\*5. In general, the number of operations grows in a cubic fashion.

At the heart of the algorithm is the `combine` function, which takes an operator and the minimal/maximal values of each of its operands, and produces the minimal/maximal results.

To maximize the result:

* If adding two numbers, maximize both arguments.
* If subtracting two numbers, maximize the left argument and minimize the right argument.
* If multiplying two numbers, try the following:

+ Maximize both arguments. This gives us the maximal result when multiplying two positive numbers.
    + Minimize both arguments. This gives us the maximal result when multiplying two negative numbers, since a negative times a negative equals a positive.
    + Minimize the left argument and maximize the right argument, or vice versa. We'd rather multiply two positives or two negatives and get a positive result, but if we have to multiply a positive and a negative and get a negative result, we want it to be as close to zero as possible. To do so, we minimize the positive number and maximize the negative number.
> 5 votes

---
Tags: code-challenge
---


title: Knock down walls in a maze

text:
# Question
Title: Knock down walls in a maze
### Rules:

In this game you start at the top of a rectangular grid of size N x M made up of walls and open spaces. The input is N lines of M characters, where a `.` specifies an open space and a `x` specifies a wall. Your program should output the smallest number K such that there exists a path from the top left corner to the bottom right corner (no diagonals) that crosses K walls.

For example, given the input:

```
..x..
..x..
xxxxx
..x..
..x..

```

your program should output `2`.

### Other examples:

output `4`:

```
xxxxx
x.x.x
x.x.x
x..xx

```

output `0`:

```
.xxxxxxxx
.x...x...
.x.x.x.x.
.x.x...x.
...xxxxx.

```

output `6`:

```
xx
xx
xx
xx
xx

```

### Extra tidbits:

If it makes your life easier, you can specify N and M as command line parameters.

Extra credit if you can have your program print out the path in some form or another.

# Answer
## Ruby 1.9 (235) (225) (222) (214)

I don't know if this is shorter than a program based on Dijkstra, but I figured I would try a different approach. This uses regex in a loop to mark each space with the minimal number of walls required to reach it.

```
w=".{#{/\s/=~s=$<.read}}?"
j="([.x])"
s[0]=v=s[0]<?x??0:?1
(d=v[-1];n=v.succ![-1]
0while(s.sub!(/#{j}(#{w+d})/m){($1<?x?d: n)+$2}||s.sub!(/(#{d+w})#{j}/m){$1+($2<?x?d: n)}))while/#{j}/=~q=s[-2]
p v.to_i-(q==n ?0:1)

```

Input is specified as a file on the command line, i.e.

```
> ruby1.9.1 golf.rb maze.txt

```

Ungolfed:

```
# read in the file
maze = $<.read

# find the first newline (the width of the maze)
width = /\s/ =~ maze

# construct part of the regex (the part between the current cell and the target cell)
spaces = ".{#{width}}?"

# construct another part of the regex (the target cell)
target = "([.x])"

# set the value of the first cell, and store that in the current wall count
maze[0] = walls = (maze[0] == "x" ? "1" : "0")

# loop until the goal cell is not "." or "x"
while /#{target}/ =~ (goal = s[-2])

  # store the current wall count digit and the next wall count digit, while incrementing the wall count
  current = walls[-1]; next = walls.succ![-1]

  # loop to set all the reachable cells for the current wall count
  begin

    # first regex handles all cells above or to the left of cells with the current wall count
    result = s.sub!(/#{target}(#{spaces + current})/m) {
      ($1 == 'x' ? next : current) + $2
    }

    # second regex handles all cells below or to the right of cells with the current wall count
    result = result || s.sub!(/(#{current + spaces})#{target}/m) {
      $1 + ($2 == 'x' ? next : current)
    }
  end while result != nil
end

# we reached the goal, so output the wall count if the goal was a wall, or subtract 1 if it wasn't
puts walls.to_i - (goal == next ? 0 : 1)

```
> 3 votes

# Answer
**Python ~~406~~ ~~378~~ ~~360~~ ~~348~~ 418 chars**

```
import sys
d={}
n=0
for l in open(sys.argv[1]):
 i=0
 for c in l.strip():m=n,i;d[m]=c;i+=1
 n+=1
v=d[0,0]=int(d[0,0]=='x')
X=lambda *x:type(d.get(x,'.'))!=str and x
N=lambda x,y:X(x+1,y)or X(x-1,y)or X(x,y+1)or X(x,y-1)
def T(f):s=[(x,(v,N(*x))) for x in d if d[x]==f and N(*x)];d.update(s);return s
while 1:
 while T('.'):pass
 v+=1
 if not T('x'):break
P=[m]
s,p=d[m]
while p!=(0,0):P.insert(0,p);x,p=d[p]
print s, P

```

Simplified Dijkstra, since moves with weight are on `x` field. It is done in "waves", first loop with finding `.` fields touching front and set them on same weight, than once find `x` fields touching front and set them on `+1` weight. Repeat while there are no more unvisited fields.

At the end we know weight for every field.

Input is specified as a file on the command line:

```
python m.py m1.txt

```

**Update:** prints path.
> 2 votes

# Answer
## Perl 5.10 (164)

```
undef$/;$_=<>;/\n/;$s="(.{$-[0]})?";substr$_,0,1,($n=/^x/||0);
until(/\d$/){1while s/([.x])($s$n)/$n+($1eq x).$2/se
+s/$n$s\K[.x]/$n+($&eq x)/se;$n++}
/.$/;print"$&\n"

```

Very much along the same lines as migimaru's solution, only with that extra Perl touch. 5.10 is needed for `\K` in `s///`.
> 2 votes

# Answer
C++ version (~~610~~ ~~607~~ ~~606~~ 584)

```
#include<queue>
#include<set>
#include<string>
#include<iostream>
#include<memory>
#define S second
#define X s.S.first
#define Y s.S.S
#define A(x,y) f.push(make_pair(s.first-c,make_pair(X+x,Y+y)));
#define T typedef pair<int
using namespace std;T,int>P;T,P>Q;string l;vector<string>b;priority_queue<Q>f;set<P>g;Q s;int m,n,c=0;int main(){cin>>m>>n;getline(cin,l);while(getline(cin,l))b.push_back(l);A(0,0)while(!f.empty()){s=f.top();f.pop();if(X>=0&&X<=m&&Y>=0&&Y<=n&&g.find(s.S)==g.end()){g.insert(s.S);c=b[X][Y]=='x';if(X==m&&Y==n)cout<<-(s.first-c);A(1,0)A(-1,0)A(0,1)A(0,-1)}}}

```

Implements Dijkstra's algorithm.

Un-golfed:

```
#include<queue>
#include<set>
#include<string>
#include<iostream>
#include<memory>

using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>Q;

int main()
{
    int             m,n;
    string          line;
    vector<string>  board;

    cin >> m >> n;getline(cin,l);
    while(getline(cin,line))
    {
        board.push_back(line);
    }

    priority_queue<Q>   frontList;
    set<P>              found;
    frontList.push(make_pair(0,make_pair(0,0)));
    while(!frontList.empty())
    {
        Q s=frontList.top();
        frontList.pop();
        if(   s.second.first>=0
           && s.second.first<=m
           && s.second.second>=0
           && s.second.second<=n
           && found.find(s.second)==found.end()
        )
        {
            found.insert(s.second);
            int c=board[s.second.first][s.second.second]=='x';
            if(  s.second.first==m
              && s.second.second==n
            )
            {   cout<<-(s.first-c);
            }
            frontList.push(make_pair(s.first-c,make_pair(s.second.first+1,s.second.second)));
            frontList.push(make_pair(s.first-c,make_pair(s.second.first-1,s.second.second)));
            frontList.push(make_pair(s.first-c,make_pair(s.second.first,s.second.second+1)));
            frontList.push(make_pair(s.first-c,make_pair(s.second.first,s.second.second-1)));
        }
    }
}

```
> 1 votes

---
Tags: code-golf, maze
---


title: Forking Factorials

text:
# Question
Title: Forking Factorials
This golf requires a factorial calculation be split up among multiple threads or processes.

Some languages make this easier to coordinate than others, so it is lang agnostic. Ungolfed example code is provided, but you should develop your own algorithm.

The goal of the contest is to see who can come up with the shortest (in bytes, not seconds) multicore factorial algorithm for calculating N! as measured by votes when the contest closes. There should be a multicore advantage, so we'll require that it should work for N ~ 10,000. Voters should vote down if the author fails to provide a valid explanation of how it spreads out the work among processors/cores and vote up based on golf conciseness.

For curiosity, please post some performance numbers. There may be a performance vs golf score tradeoff at some point, go with golf so long as it meets the requirements. I'd be curious to know when this occurs.

You may use normally available single core big integer libraries. For instance, perl is usually installed with bigint. However, note that simply calling a system provided factorial function won't normally split the work across multiple cores.

You must accept from STDIN or ARGV the input N and output to STDOUT the value of N!. You may optionally use a 2nd input parameter to also provide the number of processors/cores to the program so it doesn't do what you'll see below :-) Or you may design explicitly for 2, 4, whatever you have available.

I will post my own oddball perl example below, previously submitted on Stack Overflow under Factorial Algorithms in Different Languages. It is not golf. Numerous other examples were submitted, many of them golf but many not. Because of share-alike licensing, feel free to use the code in any examples in the link above as a starting point.

Performance in my example is lackluster for a number of reasons: it uses too many processes, too much string/bigint conversion. As I said it is an intentionally oddball example. It will calculate 5000! in under 10 seconds on a 4 core machine here. However, a more obvious two liner for/next loop can do 5000! on one of the four processors in 3.6s.

**You'll definitely have to do better than this:**

```
#!/usr/bin/perl -w
use strict;
use bigint;
die "usage: f.perl N (outputs N!)" unless ($ARGV[0] > 1);
print STDOUT &main::rangeProduct(1,$ARGV[0])."\n";
sub main::rangeProduct {
    my($l, $h) = @_;
    return $l    if ($l==$h);
    return $l*$h if ($l==($h-1));
    # arghhh - multiplying more than 2 numbers at a time is too much work
    # find the midpoint and split the work up :-)
    my $m = int(($h+$l)/2);
    my $pid = open(my $KID, "-|");
      if ($pid){ # parent
        my $X = &main::rangeProduct($l,$m);
        my $Y = <$KID>;
        chomp($Y);
        close($KID);
        die "kid failed" unless defined $Y;
        return $X*$Y;
      } else {
        # kid
        print STDOUT &main::rangeProduct($m+1,$h)."\n";
        exit(0);
    }
}

```

My interest in this is simply (1) alleviating boredom; and (2) learning something new. This isn't a homework or research problem for me.

Good luck!

# Answer
> 7 votes
## Mathematica

A parallel-capable function :

```
 f[n_, g_] := g[Product[N@i, {i, 1, n, 2}] Product[N@i, {i, 2, n, 2}]]

```

Where g is `Identity` or `Parallelize` depending on the type of process required

For the timing test, we'll slightly modify the function, so it returns the real clock time.

```
f[n_, g_] := First@AbsoluteTiming[g[Product[N@i,{i,1,n,2}] Product[N@i,{i,2,n,2}]]]

```

And we test both modes (from 10^5 up to 9\*10^5): (only two kernels here)

```
ListLinePlot[{Table[f[i, Identity],    {i, 100000, 900000, 100000}],
              Table[f[i, Parallelize], {i, 100000, 900000, 100000}]}]

```

Result:

# Answer
> 7 votes
# Haskell: 209 200 198 177 chars

### 176 167 source + 33 10 compiler flag

This solution is pretty silly. It applies product in parallel to a value of type `[[Integer]]`, where the inner lists are at most two items long. Once the outer list is down to at most 2 lists, we flatten it and take the product directly. And yes, the type checker needs something annotated with Integer, otherwise it won't compile.

```
import Control.Parallel.Strategies
s(x:y:z)=[[x,y::Integer]]++s z;s x=[x]
p=product
f n=p$concat$(until((<3).length)$s.parMap rseq p)$s[1..n]
main=interact$show.f.read

```

(Feel free to read the middle part of `f` between `concat` and `s` as "until I heart the length")

Things seemed like they were going to be pretty good since parMap from Control.Parallel.Strategies makes it pretty easy to farm this out to multiple threads. However, it looks like GHC 7 requires a whopping 33 chars in command line options and environment vars to actually enable the threaded runtime to use multiple cores (which I included in the total). Unless I am missing something, which is possible *definitely the case*. (**Update**: the threaded GHC runtime appears to use N-1 threads, where N is the number of cores, so no need to fiddle with run time options.)

To compile:

```
ghc -threaded prog.hs

```

Runtime, however, was pretty good considering the ridiculous number of parallel evaluations being sparked and that I didn't compile with -O2. For 50000! on a dual-core MacBook, I get:

```
SPARKS: 50020 (29020 converted, 1925 pruned)

INIT  time    0.00s  (  0.00s elapsed)
MUT   time    0.20s  (  0.19s elapsed)
GC    time    0.12s  (  0.07s elapsed)
EXIT  time    0.00s  (  0.00s elapsed)
Total time    0.31s  (  0.27s elapsed)

```

Total times for a few different values, the first column is the golfed parallel, the second is the naive sequential version:

```
          Parallel   Sequential
 10000!      0.03s        0.04s
 50000!      0.27s        0.78s
100000!      0.74s        3.08s
500000!      7.04s       86.51s

```

For reference, the naive sequential version is this (which was compiled with -O2):

```
factorial :: Integer -> Integer
factorial n = product [1..n]
main = interact $ show.factorial.read

```

# Answer
> 6 votes
## Java, 523 519 434 430 429 chars

```
import java.math.*;public class G extends Thread{BigInteger o,i,r=BigInteger.ONE,h;G g;G(BigInteger O,int
I,int n){o=O;i=new BigInteger(""+I);if(n>1)g=new G(O.subtract(r),I,n-1);h=n==I?i:r;start();}public void
run(){while(o.signum()>0){r=r.multiply(o);o=o.subtract(i);}try{g.join();r=r.multiply(g.r);}catch(Exception
e){}if(h==i)System.out.println(r);}public static void main(String[] args){new G(new BigInteger(args[0]),4,4);}}

```

The two 4s in the final line are the number of threads to use.

50000! tested with the following framework (ungolfed version of the original version and with a handful fewer bad practices - although it's still got plenty) gives (on my 4-core Linux machine) times

```
7685ms
2338ms
1361ms
1093ms
7724ms

```

Note that I repeated the test with one thread for fairness because the jit might have warmed up.

```
import java.math.*;

public class ForkingFactorials extends Thread { // Bad practice!
    private BigInteger off, inc;
    private volatile BigInteger res;

    private ForkingFactorials(int off, int inc) {
        this.off = new BigInteger(Integer.toString(off));
        this.inc = new BigInteger(Integer.toString(inc));
    }

    public void run() {
        BigInteger p = new BigInteger("1");
        while (off.signum() > 0) {
            p = p.multiply(off);
            off = off.subtract(inc);
        }
        res = p;
    }

    public static void main(String[] args) throws Exception {
        int n = Integer.parseInt(args[0]);
        System.out.println(f(n, 1));
        System.out.println(f(n, 2));
        System.out.println(f(n, 3));
        System.out.println(f(n, 4));
        System.out.println(f(n, 1));
    }

    private static BigInteger f(int n, int numThreads) throws Exception {
        long now = System.currentTimeMillis();
        ForkingFactorials[] th = new ForkingFactorials[numThreads];
        for (int i = 0; i < n && i < numThreads; i++) {
            th[i] = new ForkingFactorials(n-i, numThreads);
            th[i].start();
        }
        BigInteger f = new BigInteger("1");
        for (int i = 0; i < n && i < numThreads; i++) {
            th[i].join();
            f = f.multiply(th[i].res);
        }
        long t = System.currentTimeMillis() - now;
        System.err.println("Took " + t + "ms");
        return f;
    }
}

```

Java with bigints is not the right language for golfing (look at what I have to do just to construct the wretched things, because the constructor which takes a long is private), but hey.

It should be completely obvious from the ungolfed code how it breaks up the work: each thread multiplies an equivalence class modulo the number of threads. The key point is that each thread does roughly the same amount of work.

# Answer
> 6 votes
## Ruby - 111 + 56 = 167 characters

This is a two file script, the main file (`fact.rb`):

```
c,n=*$*.map(&:to_i)
p=(0...c).map{|k|IO.popen("ruby f2.rb #{k} #{c} #{n}")}
p p.map{|l|l.read.to_i}.inject(:*)

```

the extra file (`f2.rb`):

```
c,h,n=*$*.map(&:to_i)
p (c*n/h+1..(c+1)*n/h).inject(:*)

```

Simply takes the number of processes and number to calculate as args and splits the work up into ranges that each process can calculate individually. Then multiplies the results at the end.

This really shows how much slower Rubinius is to YARV:

Rubinius:

```
time ruby fact.rb 5 5000 #=> 61.84s

```

Ruby1.9.2:

```
time ruby fact.rb 5 50000 #=> 3.09s

```

(Note the extra `0`)

# Answer
> 5 votes
### CSharp - ~~206~~ 215 chars

```
using System;using System.Numerics;using System.Threading.Tasks;class a{static void Main(){var n=int.Parse(Console.ReadLine());var r=new BigInteger(1);Parallel.For(1,n+1,i=>{lock(this)r*=i;});Console.WriteLine(r);}}

```

Splits up the calculation with the C# Parallel.For() functionality.

Edit; Forgot lock

Execution times:

```
n = 10,000, time: 59ms.
n = 20,000, time: 50ms.
n = 30,000, time: 38ms.
n = 40,000, time: 100ms.
n = 50,000, time: 139ms.
n = 60,000, time: 164ms.
n = 70,000, time: 222ms.
n = 80,000, time: 266ms.
n = 90,000, time: 401ms.
n = 100,000, time: 424ms.
n = 110,000, time: 501ms.
n = 120,000, time: 583ms.
n = 130,000, time: 659ms.
n = 140,000, time: 832ms.
n = 150,000, time: 1143ms.
n = 160,000, time: 804ms.
n = 170,000, time: 653ms.
n = 180,000, time: 1031ms.
n = 190,000, time: 1034ms.
n = 200,000, time: 1765ms.
n = 210,000, time: 1059ms.
n = 220,000, time: 1214ms.
n = 230,000, time: 1362ms.
n = 240,000, time: 2737ms.
n = 250,000, time: 1761ms.
n = 260,000, time: 1823ms.
n = 270,000, time: 3357ms.
n = 280,000, time: 2110ms.

```

# Answer
> 4 votes
## Scala (345 266 244 232 214 characters)

Using Actors:

```
object F extends App{import actors.Actor._;var(t,c,r)=(args(1).toInt,self,1:BigInt);val n=args(0).toInt min t;for(i<-0 to n-1)actor{c!(i*t/n+1 to(i+1)*t/n).product};for(i<-1 to n)receive{case m:Int=>r*=m};print(r)}

```

Edit - removed references to `System.currentTimeMillis()`, factored out `a(1).toInt`, changed from `List.range` to `x to y`

Edit 2 - changed the `while` loop to a `for`, changed the left fold to a list function that does the same thing, relying on implicit type conversions so the 6 char `BigInt` type appears only once, changed println to print

Edit 3 - found out how to do multiple declarations in Scala

Edit 4 - various optimizations I've learned since I first did this

Ungolfed version:

```
import actors.Actor._
object ForkingFactorials extends App
{
    var (target,caller,result)=(args(1).toInt,self,1:BigInt)
    val numthreads=args(0).toInt min target
    for(i<-0 to numthreads-1)
        actor
        {
            caller ! (i*target/numthreads+1 to(i+1)*target/numthreads+1).product
        }
    for(i<-1 to numthreads)
        receive
        {
            case m:Int=>result*=m
        }
    print(result)
}

```

# Answer
> 4 votes
## Perl, 140

Takes *`N`* from standard input.

```
use bigint;$m=<>;open A,'>',
undef;$i=$p=fork&&1;$n=++$i;
{$i+=2;$n*=$i,redo if$i<=$m}
if($p){wait;seek A,0,0;$_=<A
>;print$n*$_}else{print A$n}

```

**Features:**

* computation split: evens on one side and odds on the other (anything more complex than that would need a lot of characters to balance the computation load appropriately.
* IPC using a shared anonymous file.

**Benchmark:**

* 10000! is printed in 2.3s forked, 3.4s unforked
* 100000! is printed in 5'08.8 forked, 7'07.9 unforked

# Answer
> 3 votes
### Scala-2.9.0 170

```
object P extends App{
def d(n:Int,c:Int)=(for(i<-1 to c)yield(i to n by c)).par
println((BigInt(1)/: d(args(0).toInt,args(1).toInt).map(x=>(BigInt(1)/: x)(_*_)))(_*_))}

```

### ungolfed:

```
object ParallelFactorials extends App
{
  def distribute (n: Int, cores: Int) = {
    val factorgroup = for (i <- 1 to cores)
      yield (i to n by cores)
    factorgroup.par
  }

  val parallellist = distribute (args(0).toInt, args(1).toInt)

  println ((BigInt (1) /: parallellist.map (x => (BigInt(1) /: x) (_ * _)))(_ * _))

}

```

The factorial of 10 is computed on 4 cores by generating 4 Lists:

* 1 5 9
* 2 6 10
* 3 7
* 4 8

which are multiplied in parallel. There would have been a simpler approach to distribute the numbers:

```
 (1 to n).sliding ((n/cores), (n/cores)

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

But the distribution wouldn't be that good - the smaller numbers would all end in the same list, the highest in another one, leading to the longer computation in the last list (for high Ns, the last thread wouldn't be almost empty, but at least contain (N/cores)-cores elements.

Scala in version 2.9 contains parallel Collections, which handle the parallel invocation themselves.

# Answer
> 2 votes
## Erlang - 295 characters.

First thing I've ever written in Erlang so I wouldn't be surprised if someone could easily halve this:

```
-module(f).
-export([m/2,f/4]).
m(N,C)->g(N,C,C,[]).
r([],B)->B;
r(A,B)->receive{F,V}->r(lists:delete(F,A),V*B)end.
s(H,L)->spawn(f,f,[self(),H,L,1]).
g(N,1,H,A)->r([s(N div H,1)|A],1);
g(N,C,H,A)->g(N,C-1,H,[s(N*C div H,N*(C-1) div H)|A]).
f(P,H,H,A)->P!{self(),A};
f(P,H,L,A)->f(P,H-1,L,A*H).

```

Uses the same threading model as my earlier Ruby entry: splits the range up into sub-range and multiplies the ranges together in seperate threads then multiplies the results back in the main thread.

I wasn't able to figure out how to get escript working so just save as `f.erl` and open up erl and run:

```
c(f).
f:m(NUM_TO_CALC, NUM_OF_PROCESSES).

```

with appropriate substitutions.

Got around 8s for 50000 in 2 processes and 10s for 1 process, on my MacBook Air (dual-core).

Note: Just noticed it freezes if you attempt more processes than the number to factorialize.

---
Tags: code-golf
---


title: Arithmetic Golf: Reach 2011

text:
# Question
Title: Arithmetic Golf: Reach 2011
**This is an challenge.** Your goal is to reach the number 2011 as quickly as possible, or to get as close to it as you can.

**Rules:**

* A "hole" consists of a rectangular grid of digits (0-9).
* Your total starts at 0.
* You may start at any digit on the grid. This is your first "stroke."
* For each subsequent stroke, you may move to any immediately adjacent digit (up, left, down, right). However, you may not move to a digit that you have used before.
* With each stroke, you will use your current total and the digit at your current position as operands (the total is always the first operand), and apply one of the four basic arithmetic operations (+ - * /). The result will become your new total.
* If your total becomes 2011, your score for the course is the number of strokes.
* If you have no more valid moves, your score is your current number of strokes + your total's distance from 2011.
* You may also choose at any time to stop, and your score will be your current number of strokes + your total's distance from 2011.

**Input:**

* You will read in a file containing data for each "hole." Alternatively, you may accept the input through stdin or an equivalent.
* Each hole will consist of H rows of W digits, for a grid of size WxH. H and W may vary per hole.
* The holes will be separated by a single blank line.
* In the spirit of golf, the competition will consist of 18 holes, but your program should be able to handle any number of them.

**Output:**

* For each hole, your program should output the position of the starting digit. The position should be given as `(row, col)` where the top-left is `(0, 0)`.
* For each stroke, your program should output the chosen operation, the current digit, and the resulting total.
* At the end of each hole, whether you reach 2011 or not, your program should output your number of strokes and your score for the hole (usually the same as the number of strokes).
* For testing purposes, you may also find it helpful to output your path on each board indicating which digits were used. However, you will not be required to provide this output for the competition.

**Notes:**

* For any given hole, your program should always start at the same position and choose the same route (i.e., no random choices). The starting position does not need to be the same for every hole.
* The total is not limited to the integers. That is, if you divide 4023 by 2, your total would become 2011.5, and you would still be .5 away from the goal.
* Your program should run in a "reasonable" amount of time.
* For purposes of verifiability, your program should be runnable on an online interpreter such as ideone.com.
* The winner is the program that has the lowest overall score for the entire course. If there is a tie, the tying programs will play a new course, hole-for-hole, with the lowest scorers advancing until there is only one winner. If there is still a tie after the tiebreaker course, the program submitted first will win.

**Deadline:**

* The current deadline for this competition is September 10, 2011. This deadline may be extended, depending on interest.

**Sample input:**

```
14932875921047
60438969014654
56398659108239
90862084187569
94876198569386
14897356029523

```

**Sample output:**

```
Start: (3, 7)
+4=4
*9=36
*9=324
*6=1944
+9=1953
+8=1961
+8=1969
+9=1978
+6=1984
+8=1992
+8=2000
+8=2008
+4=2012
-1=2011
Strokes: 14
Score: 14

14932875921047
6043....014654
563..65.108239
90..208.187569
94.76198569386
...97356029523

```

**Sample output (compact):**

```
Start: (3, 7)
+4=4 *9=36 *9=324 *6=1944 +9=1953 +8=1961 +8=1969 +9=1978 +6=1984 +8=1992 +8=2000 +8=2008 +4=2012 -1=2011
Strokes: 14   Score: 14

```

**Sample input:**

```
0346092836
1986249812
3568086343
5509828197
4612486355
3025745681
7685047124
2098745313

```

**Sample output:**

```
Start: (4, 7)
+3=3
*6=18
*5=90
+7=97
*5=485
*4=1940
+7=1947
+8=1955
+9=1964
+8=1972
+6=1978
+7=1985
+3=1988
+4=1992
+5=1997
+5=2002
+5=2007
+3=2010
+1=2011
Strokes: 19
Score: 19

0346092836
.986249812
..68086343
..09828197
.61248..55
.02574.681
...504.124
20.....313

```

**Sample input:**

```
9876
5432
1098
7654
3210

```

**Sample output:**

```
Start: (2, 2)
+9=9
*8=72
*4=288
*5=1440
+6=1446
+7=1453
+3=1456
+2=1458
+1=1459
Strokes: 9
Score: 561

9876
5432
10..
....
....

```

**Sample input:**

```
39857205
74493859
02175092
54239112
39209358
34568905

```

**Sample output:**

```
Start: (0, 0)
+3=3
*7=21
*4=84
*4=336
-1=335
*2=670
/3=(670/3)
*9=2010
+1=2011

.9857205
...93859
02.75092
54....12
39209358
34568905

```

## Results

Unfortunately, there were only two contestants, but I'll post the results.

```
#1 - Howard (1881)
#2 - Gareth (5442)

```

The first half of the course consisted of roughly "normal" holes, generated mostly randomly. The second half was more challenging, as the holes contained more "sand traps" (sections deliberately filled with low numbers, especially 0s).

```
**Howard**
01) 5 - 5
02) 5 - 5
03) 6 - 6
04) 6 - 7
05) 6 - 7
06) 6 - 6
07) 5 - 5
08) 5 - 5
09) 6 - 6
10) 9 - 10
11) 5 - 8
12) 8 - 8
13) 6 - 7
14) 8 - 9
15) 7 - 12
16) 20 - 1665
17) 29 - 66
18) 30 - 44
Front 9) 52
Back  9) 1829
Full 18) 1881

**Gareth**
01) 9 - 10
02) 33 - 173
03) 8 - 8
04) 11 - 16
05) 7 - 84
06) 17 - 17
07) 9 - 10
08) 8 - 8
09) 15 - 15
10) 16 - 16
11) 12 - 32
12) 18 - 164
13) 34 - 335
14) 10 - 10
15) 26 - 447
16) 78 - 78
17) 1 - 2010
18) 1 - 2009
Front 9) 341
Back  9) 5101
Full 18) 5442

```

The course used can be found on pastebin.

@Howard: I ran your program with the lower number of paths due to limits on ideone. If your full version gives significantly different results, let me know the scores and the relative running time of the program.

# Answer
### Java - The Why-Not-Try-It-The-Easy-Way-Approach

Here is my first submission for this problem. I don't know if it qualifies for ai-player because it is more "artifical clumsiness". Maybe I can do better but I think it is hard to beat it on most grids.

The program just takes paths and operations calculated by a *very complicated and clever algorithm* (no, it's not random ;-) It will give you the same result every time) and compares all of them to find the best one.

Input must be given on STDIN. You can see the examples running here (note: number of paths reduced).

The output for above holes is

```
Start: (4, 0)
+9=9
*4=36
*8=288
*7=2016
-6=2010
Strokes: 5
Score: 6

Start: (3, 3)
+9=9
*8=72
*4=288
*7=2016
-5=2011
Strokes: 5
Score: 5

Start: (0, 2)
+7=7
*8=56
*4=224
-0=224
*9=2016
-5=2011
Strokes: 6
Score: 6

Start: (2, 3)
+7=7
*9=63
*4=252
*8=2016
-5=2011
Strokes: 5
Score: 5

```

The program itself is given below (it makes use of lots of static declarations - don't try this at home).

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

public class Main {

    // DEBUG=true displays progress
    private static final boolean DEBUG = false;

    // Number of paths to try
    private static final int PATHS = 10000000;

    // Saves the number grid
    static int[][] grid;

    // start position
    static int startx;
    static int starty;

    // used digits and operations
    static int[] ns = new int[1024];
    static int[] ops = new int[1024];

    // current best score and output for this score
    static double bestScore;
    static String best;

    // a random number generator
    static Random random;

    public static void main(String[] args) throws IOException {
        BufferedReader cons = new BufferedReader(new InputStreamReader(System.in));

        String[] conLines = new String[1024];
        int numLines = 0;

        while (true) {
            String line = cons.readLine();
            if (line == null || line.isEmpty()) {
                // already some lines found
                if (numLines > 0) {
                    // prepare grid and run algorithm
                    prepareGrid(conLines, numLines);
                    findBest();
                    System.out.println(best);
                }
                numLines = 0;
            } else {
                conLines[numLines++] = line;
            }
            if (line == null)
                break;
        }
    }

    private static void findBest() {
        random = new Random(1);
        bestScore = 9999e99;
        for (int k = 0; k < PATHS; k++) {
            int sx = startx = random.nextInt(grid.length);
            int sy = starty = random.nextInt(grid[0].length);
            doStep(0, 1, 0, sx, sy);
        }
    }

    private static void doStep(int num, int den, int steps, int sx, int sy) {
        // consume the digit at the current position
        ns[steps] = grid[sx][sy];
        grid[sx][sy] = -1;

        // choose random operation and apply to total=num/den
        ops[steps] = num == 0 || ns[steps] == 0 ? random.nextInt(2) : random.nextInt(4);
        if (ops[steps] == 0) {
            num -= den * ns[steps];
        } else if (ops[steps] == 1) {
            num += den * ns[steps];
        } else if (ops[steps] == 2) {
            den *= ns[steps];
            int g = gcd(num, den);
            if (g > 1) {
                num /= g;
                den /= g;
            }
        } else if (ops[steps] == 3) {
            num *= ns[steps];
            int g = gcd(num, den);
            if (g > 1) {
                num /= g;
                den /= g;
            }
        }

        // calculate score for path up to now and save it if best
        double score = steps + 1 + Math.abs(2011 - num / (double) den);
        if (score < bestScore) {
            bestScore = score;
            best = String.format("Start: (%d, %d)\n", starty, startx);
            int nn = 0;
            int dn = 1;
            for (int k = 0; k <= steps; k++) {
                if (ops[k] == 0) {
                    nn -= dn * ns[k];
                } else if (ops[k] == 1) {
                    nn += dn * ns[k];
                } else if (ops[k] == 2) {
                    dn *= ns[k];
                    int g = gcd(nn, dn);
                    if (g > 1) {
                        nn /= g;
                        dn /= g;
                    }
                } else if (ops[k] == 3) {
                    nn *= ns[k];
                    int g = gcd(nn, dn);
                    if (g > 1) {
                        nn /= g;
                        dn /= g;
                    }
                }
                best += String.format(dn == 1 ? "%c%d=%d\n" : "%c%d=%d/%d\n", "-+/*".charAt(ops[k]), ns[k], nn, dn);
            }
            best += String.format("Strokes: %d\n", steps + 1);
            best += dn == 1 ? String.format("Score: %d\n", (int) (score + 0.05)) : String.format("Score: %f\n", score);
            if (DEBUG) {
                System.out.println(best);
                printGrid(grid);
                System.out.println();
            }
        }

        if (steps + 2 < bestScore) {
            // choose any direction and go on
            int dir = random.nextInt(4);
            int nx = sx;
            int ny = sy;
            int b = 0;
            while (b < 4) {
                if (dir == 0 && sx > 0 && grid[sx - 1][sy] >= 0) {
                    nx = sx - 1;
                    break;
                } else if (dir == 1 && sx < grid.length - 1 && grid[sx + 1][sy] >= 0) {
                    nx = sx + 1;
                    break;
                } else if (dir == 2 && sy > 0 && grid[sx][sy - 1] >= 0) {
                    ny = sy - 1;
                    break;
                } else if (dir == 3 && sy < grid[0].length - 1 && grid[sx][sy + 1] >= 0) {
                    ny = sy + 1;
                    break;
                }
                b++;
                dir++;
            }

            // if further step possible
            if (b < 4) {
                doStep(num, den, steps + 1, nx, ny);
            }
        }

        // put back the digit
        grid[sx][sy] = ns[steps];
    }

    // helper function calculating gcd
    private static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    // helper function reading the grid from an array of strings
    private static void prepareGrid(String[] data, int numLines) {
        grid = new int[data[0].length()][numLines];
        for (int y = 0; y < numLines; y++) {
            for (int x = 0; x < data[y].length(); x++) {
                grid[x][y] = (int) (data[y].charAt(x) - '0');
            }
        }
    }

    // helper function printing the grid
    private static void printGrid(int[][] grid) {
        for (int y = 0; y < grid[0].length; y++) {
            for (int x = 0; x < grid.length; x++) {
                System.out.print(grid[x][y] < 0 ? '.' : (char) ('0' + grid[x][y]));
            }
            System.out.println();
        }
    }
}

```

*Edit:* Just did a small performance optimization. We don't need to follow a path anymore if it's length already exceeds the best score found so far.
> 2 votes

# Answer
## Scala

```
object Main
{
    def main(args:Array[String])
    {
        var input=io.Source.stdin.getLines.toArray

        while(!input.isEmpty)
        {
            var hole=input.takeWhile(_!="").map(_.map(x=>Integer.parseInt(x.toString)).toArray).toArray
            input=input.dropWhile(_!="")
            if(!input.isEmpty)
                input=input.tail

            var (height,width)=(hole.size,hole.head.size)
            var bestscore=10000000
            var bestrunoutput=""
            var currentval=0
            var output=""
            var exit=false
            var c:Array[Array[Int]]=Array(Array(0))
            var(steps,xnow,ynow)=(0,0,0)

            def getNeighbours(x:Int,y:Int,c:Array[Array[Int]]):Array[(Int,Int,Int)]=
                (for(a<- -1 to 1;b<- -1 to 1;if(Math.abs(a)!=Math.abs(b) && x+b>=0 && x+b<width && y+a>=0 && y+a<height)) yield (c(y+a)(x+b),x+b,y+a)).toArray.sortBy(_._1).reverse

            for(y<-0 until height;x<-0 until width)
            {
                c=hole.map(_.clone)
                exit=false
                steps=0
                xnow=x
                ynow=y

                currentval=c(ynow)(xnow)
                output="Start: ("+y+","+x+")\n+"+currentval+"="+currentval+"\n"
                while(!exit)
                {
                    var neighbours=getNeighbours(xnow,ynow,c)
                    while(neighbours.size>0 && (neighbours.head._1*currentval>2011 || neighbours.head._1<2))
                        neighbours=neighbours.drop(1)
                    if(neighbours.size==0)
                    {
                        neighbours=getNeighbours(xnow,ynow,c)
                        while(neighbours.size>0 && (neighbours.head._1+currentval>2011 || neighbours.head._1==0))
                            neighbours=neighbours.drop(1)
                        if(neighbours.size==0)
                        {
                            exit=true
                        }
                        else
                        {
                            currentval+=neighbours.head._1
                            c(ynow)(xnow)=0
                            output+="+"+neighbours.head._1+"="+currentval+"\n"
                        }
                    }
                    else
                    {
                        currentval*=neighbours.head._1
                        c(ynow)(xnow)=0
                        output+="*"+neighbours.head._1+"="+currentval+"\n"
                    }
                    if(!exit)
                    {
                        xnow=neighbours.head._2
                        ynow=neighbours.head._3
                    }
                    steps+=1
                }
                output+="Strokes: "+steps+"\nScore: "+(steps+2011-currentval)+"\n"

                if(steps+2011-currentval<bestscore)
                {
                    bestscore=steps+2011-currentval
                    bestrunoutput=output
                }
            }

            println(bestrunoutput)
        }
        println
    }
}

```

I've tidied it up a little, fixed the bug that let the same number be used more than once for addition, and I've met the requirement (which I didn't spot before) to take multiple holes as input.

The algorithm is fairly simple:

```
For every possible start point:
    Find the highest value neighbour and try multiplying it
    If it's too high
        Try the next highest neighbour
        If there are no more neighbours
            Find the highest value neighbour and try adding it
            If it's too high
                Try the next highest neighbour
                If there are no more neighbours
                    End this attempt and calculate the score
Print out the attempt with the best score

```

Running in ideone.com:

**Input**

```
14932875921047
60438969014654
56398659108239
90862084187569
94876198569386
14897356029523

0346092836
1986249812
3568086343
5509828197
4612486355
3025745681
7685047124
2098745313

9876
5432
1098
7654
3210

39857205
74493859
02175092
54239112
39209358
34568905

```

**Output**

```
Start: (0,3)
+3=3
*9=27
*4=108
*3=324
*6=1944
+5=1949
+9=1958
+9=1967
+4=1971
+8=1979
+8=1987
+9=1996
+7=2003
+6=2009
+2=2011
Strokes: 15
Score: 15

Start: (6,6)
+7=7
*5=35
*4=140
*7=980
+8=988
+9=997
+8=1005
*2=2010
+1=2011
Strokes: 9
Score: 9

Start: (4,0)
+3=3
*7=21
*6=126
*5=630
+9=639
*3=1917
+7=1924
+8=1932
+9=1941
+5=1946
+4=1950
Strokes: 11
Score: 72

Start: (4,5)
+3=3
*9=27
*8=216
*9=1944
+9=1953
+5=1958
+7=1965
+9=1974
+5=1979
+8=1987
+9=1996
+4=2000
+7=2007
+3=2010
Strokes: 14
Score: 15

```

Looks like mine'll have to be content being weekend golf player compared to Howard's Tiger Woods. :-)
> 2 votes

---
Tags: code-challenge, math, ai-player
---


title: Optimal Othello/Reversi Move

text:
# Question
Title: Optimal Othello/Reversi Move
This is a challenge: **Given a specific board in the game of Othello (Reversi), find a move for Black that will capture the maximum number of White pieces.**

(Obviously, this may not be the true "optimal" play for Black, but to keep things simple we are only interested in finding the move that will capture the most pieces.)

If you are unfamiliar with the rules of Othello (Reversi), you may refer to: http://en.wikipedia.org/wiki/Reversi

* Input will be provided as a file, or through stdin (your choice).
* You may assume that the board will be a standard 8x8 size.
* Black pieces will be indicated by `b` and White pieces will be indicated by `w`. Empty spaces will be indicated by `.`
* The input may not necessarily be a valid board reachable by the rules of the game. Regardless, you must still find the optimal move following the rules of the game.
* Your program must output the move by Black that will capture the most White pieces. If there is a tie, you may choose to output any (or all) of the moves. If there is no valid move, your program must indicate so by outputting `x`.
* Your output can be provided as a coordinate, such as `(3,4)`, or in algebraic notation, such as `b5`. When submitting your answer, please clearly indicate your output format and specify where your coordinate system starts from.

Sample input:

```
........
..b.....
...b....
...wwww.
...wb...
........
........
........

```

Sample output in (row,col) format, with (0,0) in the top-left corner:

```
(5,3)

```

Sample input:

```
........
......w.
.wwwwww.
.wwwwww.
.wwwwww.
.wwwwww.
.b....b.
........

```

Sample output in algebraic notation, with a1 in the bottom-left corner:

```
b7

```

Sample input:

```
........
........
..bbbb..
..bwwb..
..bwwb..
..bbbb..
........
........

```

Sample output:

```
x

```

This is code golf, so the shortest solution will be accepted.

# Answer
## Python, 184 chars

```
import os,re
M=os.read(0,99)
s=0
t='x'
for p in range(72):
 c=sum(len(re.match(r'\.w+b|',M[p::d]).group()[2:])for d in(-10,-9,-8,-1,1,8,9,10))
 if c>s:s=c;t='(%d,%d)'%(p/9,p%9)
print t

```

Coordinates are given as (y,x) with (0,0) in the upper left.

```
$ ./othello.py < othello1
(5,3)
$ ./othello.py < othello2
(1,1)
$ ./othello.py < othello3
x

```
> 2 votes

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


title: A Mere Bagatelle

text:
# Question
Title: A Mere Bagatelle
## The challenge

Given a bagatelle board like the one below:

```
|                    |
|    /\            / |
|      \            /|
|  \      \ /\    \  |
|   \   /       \    |
|\     /   /  \      |
|   \            / \ |
|    \               |
|  \    / \ /\    \  |
|\     /   /  \     /|
|                /   |
|    /\         /  / |
|              /     |
|\     /   /  /      |
|                    |
----------------------

```

your task is to turn a list of 'throws' into a score.

The board will always be 20 characters (plus 2 edges) wide, but of variable height. Each 'throw' is a number representing where the ball falls into the board, starting at 0 for the far left up to 19 for the far right. Each ball will fall straight down unless it encounters a `/` or a `\`. Encountering a `/` shifts the ball one column to the left, and a `\` shifts the ball one column to the right. After being shifted, the ball continues straight down as before. The score for a throw is dependant on where the ball hits the bottom of the board.

The scores for each finishing position are as follows:

```
|                    |
----------------------
 01234567899876543210

```

and are the same for all boards. The first and last rows will always be empty. The ball is guaranteed to reach the bottom regardless of where it is dropped from, so there will be no boards where it can get trapped by `\/`,`\|` or `|/` combinations.

## Input

Input will be on STDIN, and will consist of the board followed by a blank line followed by a space separated list of numbers representing the throws.

## Output

Ouput should be the total score for the given game.

## A couple of examples

**Input**

```
|                    |
| \                  |
|  \                 |
|   \                |
|    \               |
|     \              |
|      \             |
|       \            |
|        \           |
|         \          |
|          \         |
|           \        |
|            \       |
|             \      |
|              \     |
|               \    |
|                \   |
|                 \  |
|                    |
|                    |
----------------------

1 4 2 19 0 2 4 3 17 13 16

```

**Output**

```
9

```

**Input**

```
|                    |
| \                / |
|  \              /  |
|   \            /   |
|    \          /    |
|     \        /     |
|      \      /      |
|       \    /       |
|        \  /        |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
----------------------

15 10 3 8 18 19 0 6 7 10

```

**Output**

```
72

```

**Input**

```
|                    |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
| ////////////////// |
| \\\\\\\\\\\\\\\\\\ |
|                    |
----------------------

1 4 18 17 14 2 0 19 15

```

**Output**

```
18

```

## Test scripts

I've used some test scripts written by Joey and Ventero (I hope they don't mind...) to create some tests for this task:-

Usage: `./test [your program and its arguments]`

This is codegolf - shortest solution wins.

# Answer
## GolfScript, 60 59 chars

```
n/{},)\);{1>:x,,{.x=31%4%(+}%}%[10,.-1%+]+0@[~]{2${=}/+}/\;

```

I was so tempted to write a solution which works by redefining the symbols `/`, `\`, and `space`, but it's actually quite expensive (especially once you can no longer use the original `\`).

`31%4%(` is nicked from Keith Randall's solution and maps the ASCII codes for `space`, `/`, and `\` to `0`, `-1`, `1` respectively. (See edit history).
> 3 votes

# Answer
## Python 2, 147 132 130 chars

```
import sys
s=0
l=list(sys.stdin)
for t in l[-1].split():
 p=int(t)+1
 for r in l[:-3]:p-=" /".find(r[p])
 s+=min(p-1,20-p)
print s
```
> 4 votes

# Answer
## Python, 165 159 chars

```
import sys
A=list(sys.stdin)
C=range(10)
C+=C[::-1]
for L in A[-4::-1]:C=[C[i+ord(L[i+1])%31%4-1]for i in range(20)]
print sum(C[int(x)]for x in A[-1].split())

```

It starts with a row of scores and works its way from the bottom up, computing what the scores would be for balls starting at each row.
> 3 votes

# Answer
## Ruby, 123 117 115 107 99 98 97

```
*b,_,_,n=*$<
p eval n.split.map{|k|i=k.to_i+1
b.map{|l|i-='\ /'.index(l[i])-1}
[i-1,20-i].min}*?+

```
> 3 votes

---
Tags: code-golf
---


title: Regex validating regex

text:
# Question
Title: Regex validating regex
Build a regex that will accept a regex string as input and check if it's valid. Basically, your regex should be able to validate itself. (Any invalid regex should not be validated, so you can't use `.*`. ;))

Your flavor must be fully supported by *well known* implementations (Perl, sed, grep, gawk, etc), and it must fully support what those implementations support. \[Don't worry about the lawyer speak; I'm just trying to remove any possible loopholes for the smart\***es.\]

---

I'd it, but I'm worried it'll give an edge to those who know and use non-feature-rich flavors. Or are my worries unfounded?

# Answer
> 27 votes
## Ruby

I tried to match the actual syntax of Ruby's regex flavor as much as possible, but there are a few quirks: it accepts a few lookbehinds that are actually invalid (like `(?<=(?<!))`), and it recognizes empty character ranges like `D-A`. The latter could be fixed for ASCII, but the regex is long enough as it is.

```
\A(?<main>
    (?!
        \{(\d+)?,(\d+)?\} # do not match lone counted repetition
    )
    (?:
        [^()\[\]\\*+?|<'] | # anything but metacharacters
        (?<cclass>
            \[ \^? (?: # character class
                (?: # character class
                    [^\[\]\\-] | # anything but square brackets,  backslashes or dashes
                    \g<esc> |
                    \[ : \^? (?: # POSIX char-class
                        alnum | alpha | word | blank | cntrl | x?digit | graph | lower | print | punct | space | upper
                    ) : \] |
                    - (?!
                        \\[dwhsDWHS]
                    ) # range / dash not succeeded by a character class
                )+ |
                \g<cclass> # more than one bracket as delimiter
            ) \]
        ) |
        (?<esc>
            \\[^cuxkg] | # any escaped character
            \\x \h\h? | # hex escape
            \\u \h{4} | # Unicode escape
            \\c . # control escape
        ) |
        \\[kg] (?:
            < \w[^>]* (?: > | \Z) |
            ' \w[^']* (?: ' | \Z)
        )? | # named backrefs
        (?<! (?<! \\) \\[kg]) [<'] | # don't match < or ' if preceded by \k or \g
        \| (?! \g<rep> ) | # alternation
        \( (?: # group
            (?:
                \?
                (?:
                    [>:=!] | # atomic / non-capturing / lookahead
                    (?<namedg>
                        < [_a-zA-Z][^>]* > |
                        ' [_a-zA-Z][^']* ' # named group
                    ) |
                    [xmi-]+: # regex options
                )
            )?
            \g<main>*
        ) \) |
        \(\?<[!=] (?<lbpat>
            (?! \{(\d+)?,(\d+)?\} )
            [^()\[\]\\*+?] |
            \g<esc>  (?<! \\[zZ]) |
            \g<cclass> |
            \( (?: # group
                (?:
                    \?: |
                    \? \g<namedg> |
                    \? <[!=]
                )?
                \g<lbpat>*
            ) \) |
            \(\?\# [^)]* \)
        )* \)
        |
        \(\? [xmi-]+ \) # option group
        (?! \g<rep> )
        |
        \(\?\# [^)]*+ \) # comment
        (?! \g<rep> )
    )+
    (?<rep>
        (?:
            [*+?] | # repetition
            \{(\d+)?,(\d+)?\} # counted repetition
        )
        [+?]? # with a possessive/lazy modifier
    )?
)*\Z

```

Unreadable version:

```
\A(?<main>(?!\{(\d+)?,(\d+)?\})(?:[^()\[\]\\*+?|<']|(?<cclass>\[\^?(?:(?:[^\[\]\\-]|\g<esc>|\[:\^?(?:alnum|alpha|word|blank|cntrl|x?digit|graph|lower|print|punct|space|upper):\]|-(?!\\[dwhsDWHS]))+|\g<cclass>)\])|(?<esc>\\[^cuxkg]|\\x\h\h?|\\u\h{4}|\\c.)|\\[kg](?:<\w[^>]*(?:>|\Z)|'\w[^']*(?:'|\Z))?|(?<!(?<!\\)\\[kg])[<']|\|(?!\g<rep>)|\((?:(?:\?(?:[>:=!]|(?<namedg><[_a-zA-Z][^>]*>|'[_a-zA-Z][^']*')|[xmi-]+:))?\g<main>*)\)|\(\?<[!=](?<lbpat>(?!\{(\d+)?,(\d+)?\})[^()\[\]\\*+?]|\g<esc>(?<!\\[zZ])|\g<cclass>|\((?:(?:\?:|\?\g<namedg>|\?<[!=])?\g<lbpat>*)\)|\(\?#[^)]*\))*\)|\(\?[xmi-]+\)(?!\g<rep>)|\(\?#[^)]*+\)(?!\g<rep>))+(?<rep>(?:[*+?]|\{(\d+)?,(\d+)?\})[+?]?)?)*\Z

```

---
Tags: code-challenge, regular-expression
---