title: Score counter for Skat

text:
# Question
Title: Score counter for Skat
You task is to write a small program, that counts the points of a Skat hand. A Skat deck has cards 7 to 10, Jack, Queen, King and Ace (called Unter, Ober, König and Daus). We use the German suits, which have Acorns, Leaves, Hearts and Bells instead of Clubs, Spades, Hearts and Diamonds. The points are determined by the number on the card:

* 7, 8 and 9 are 0 points
* Unter is 2 points
* Ober is 3 points
* König is 4 points
* 10 is 10 points
* Daus is 11 points.

### Input / Output

The input format consists of two symbols, the first one represents the value, while the second one stands for the suit:

* 7, 8 and 9 stand for them self
* 0 (zero) stands for 10
* Unter, Ober, König and Daus are named after their first letters (U, O and D)
* The same for Acorns, Leaves, Hearts and Bellys (A, L, H and B)

The input is a single line of cards, separated by a single whitespace. You may take the input from anywhere, command line arguments are okay too. The output is the value of the hand, either printed out or returned as an exit code. The output of your program must show an error, if any card appears twice in the hand. (So `7A 0L 7A` must return an error instead of `10`). It is also okay to quit with an exit code of 255 instead of showing an error, if this is the default way of your program to output the result.

### Examples

* `7A 8A 9A UA OA KA 0A DA 7L 8L 9L UL OL KL 0L DL 7H 8H 9H UH OH KH 0H DH 7B 8B 9B UB OB KB 0B DB` gives *120*
* `7A 8L 0K DB 8L` gives an error
* `UA OB DL KH` gives *20*

### Rules

* Code golf: The shortest code wins
* Usual code golf rules apply
* The program has to work for all hands, not just the examples
* GIGO: If the input is invalid, the output may be arbitrary

# Answer
## APL (~~54~~ 48)

There *has* to be a shorter way of selecting the card value, but I don't see it.

```
(+/12-'D0.....KOU.'⍳⊃¨A)÷A≡∪A←↓A⍴⍨2,⍨2÷⍨⍴A←⍞~' '

```

You get a `DOMAIN ERROR` if there's a duplicate card.

Explanation:

* `A←⍞~' '`: store () into `A` a line of user input () without (`~`) the spaces.
* `2,⍨2÷⍨⍴A`: a two-element list, containing the length of () `A` divided by (`÷⍨`) 2, followed by (`,⍨`) the number 2. (So, if the input is `UA OB DL KH` the list is (4, 2)).
* `↓A⍴⍨`: define a matrix (), with the dimensions of that list, containing the values of A. Then join the elements of its rows together (), giving a list of lists, for example `['UA','OB','DL','KH']`.
* `A←`: Store this list in A.
* `A≡∪A`: `∪A` is the list of unique elements in A. If this is equal to A, there are no duplicates and this returns 1, otherwise 0.
* `÷`: divide what's on the left (which does the actual calculation) by the result of the equality test. So if there are no duplicates, the score is unchanged, and if there are duplicates you get a `DOMAIN ERROR` because of the division by zero.
* `⊃¨A`: A list giving the first element () of each element (`¨`) of A. So this drops the suit letter, leaving the score letter. (`UODK`)
* `'D0.....KOU.'⍳`: gives the index of each of the score letters in this string, returns 12 for values not in the string. (`10 9 1 8`)
* `+/12-`: subtract all of these from 12, and then add them together. (`2 + 3 + 11 + 4 = 20`)

---
> 2 votes

# Answer
## Ruby 1.9, 52 characters

Input via command line arguments. I'm assuming the error message when having duplicate cards doesn't matter, so it just complains about an eval/type conversion error.

```
p eval$*.uniq!||$*.map{|i|"..UOK#$<.0D"=~/#{i}?/}*?+

```

Example usage:

```
$ ruby1.9 skatscore.rb 7A 8A 9A UA OA KA 0A DA 7L 8L 9L UL OL KL 0L DL 7H 8H 9H UH OH KH 0H DH 7B 8B 9B UB OB KB 0B DB
120

$ ruby1.9 skatscore.rb 7A 7A
skatscore.rb:1:in `eval': can't convert Array into String (TypeError)
    from skatscore.rb:1:in `<main>'

```
> 10 votes

# Answer
### Scala, 87 82 characters

```
args.distinct(args.size-1);println(args.map(a=>1+" UOK     0D".indexOf(a(0))).sum)

```

Throws an exception on repeated cards.
> 6 votes

# Answer
# Haskell, ~~122~~ ~~108~~ 107 characters

```
import List
main=interact$f.words
f x|nub x==x=show$sum$map(maybe 0 id.(`elemIndex`"  UOK     0D").head)x

```
> 4 votes

# Answer
### GolfScript ~~54~~ ~~53~~ 52

**Edit 1:**

I just discovered an error in the code. It did not detect duplicate cards if the duplicates were the first two in the input (because I was using the `*` fold operator and not the `/` each operator for the first loop).

Now I fixed the code and also managed to strip off 1 char in the process. Here's the new version:

```
' '/{1$1$?){]?}{\+}if}/2%{"UOK0D"\?).0>+.4>5*+}%{+}*

```

The input has to be on the stack as a string, in the specified format (example: `'7A UA DA'`).

In case the input is valid, the program prints the total value of the cards.

In case there's at least one duplicate card, the program throws the following exception:

```
(eval):1:in `block in initialize': undefined method `class_id' for nil:NilClass (NoMethodError)

```

**Edit 2:**

After seeing this post on the meta site, I decided to post a description of the code. This also helped me find and fix an error. So, here goes:

```
# Initially, we epect the input string to be on the stack
# Example: "7A UA DA"

' '/            # split the input string by spaces
                # now we have on the stack an array of strings
                # (in our example: ["7A" "UA" "DA"])

# {1$1$?)!{\+}{]?}if}/  -> this piece of code checks for duplicate cards
#
# The trailing symbol (/) is the 'each' operator, meaning that the
# preceding code block (enclosed in curly brackets) will be executed
# for every cards in the previous array.
#
# Before each execution of the code block, the current card value
# is pushed on the stack.
#
# Basically what this code does is concatenate cards into a string
# and checks whether the current card is contained in the accumulated
# value.
#
# So, for each card, this is what we execute:

1$              # copies the concatenated string on top of the stack
                # (initially this is an empty string)

1$              # copies the current card on top of the stack

?               # returns (places on the stack) the 0-based index where
                # the current card is found in the concatenated string
                # or -1 if not found

)               # increments the topmost stack value
                # Now we have 0 if the card is not a duplicate
                # or a value greater than 0 otherwise

{]?}{\+}if      # if the current stack value is non-0 (duplicate)
                # then execute the first code {]?} (generates an error)
                # Otherwise, if the card is valid, execute the {\+} block.
                # What this code does is essentially concatenate the current
                # card value:
                #    \ -> swaps the two topmost stack values; now we have
                #         the concatenated string and the current card value
                #    + -> this is the concatenation operator

# After the previous code block finishes execution (in case the input is)
# valid, we end up having the concatenated card values on the stack
# In our example, this value is "DAUAUB7A".

# The next code fragment is the one that computes the card values
# This is the code: 2%{"UOK0D"\?).0>+.4>5*+}%{+}*

# And this is how it can be broken down:

2%              # takes only the even indexed chars from the existing string
                # in our case, "DAUA7A" -> "DU7"
                # Only these characters are important for determining the
                # card values.

# The following piece of code is:
# {"UOK0D"\?).0>+.4>5*+}%

# This code performs a map; it takes the individual chars,
# computes the corresponding numeric value for each of them and outputs an
# array containing those values

# This is achieved using the map operator (%) which evaluates the preceding
# code block, delimited by curly braces, so, essentially this is the code that
# computes the value for a card:
# "UOK0D"\?).0>+.4>5*+
# It can be broken down like this:

"UOK0D"         # pushes the "UOK0D" string on the stack
\               # swaps the two topmost stack values
                # Now, these values are: "UOK0D" and "l"
                # (where "l" represents the current letter
                # that gives the card its value: U,O,K,0,D,7,8...)

?               # Find the index of the card's letter in the
                # "UOK0D" string.
                # Remember, this is 0-based index, or -1 if not found.

)               # increment the index value
                # Now we have the following value:
                #     1 if the card is U
                #     2 if the card is O
                #     3 if the card is K
                #     4 if the card is 0
                #     5 if the card is D
                #     0 if it is anything else

.0>+            # if the current value is greater than 0,
                # add 1 to it.

.4>5*+          # if the current value is greater than 4,
                # add 5 to it.

# Passing through these steps, we now have the following value:
#     2  if the card is U
#     3  if the card is O
#     4  if the card is K
#     10 if the card is 0
#     11 if the card is D
#     0  if it is anything else
# This is the exact value we were looking for.

# Now we have an array containing the value of each card.
# in our example, [0, 2, 11]
# The next piece of code is easy:

{+}*            # uses the * (fold) operator to add up all the
                # values in the array.

# This leaves the total value of the cards on the stack,
# which is exactly what we were looking for (0+2+11=13).

# Golfscript is awesome! :-)

```
> 2 votes

# Answer
## Python, 114 characters

```
i=input().split();print(sum(int(dict(zip('7890UOKD','000A234B'))[x[0]],16)for x in i)if len(i)<=len(set(i))else'')

```

Unfortunately, the `index` method of lists in Python raises an error if an element isn't found rather than returning a negative value, and importing `defaultdict` would require more characters than it would save.
> 1 votes

# Answer
eTeX, 201 characters (not counting the two irrelevant linebreaks)

```
\def~#1#2{\catcode`#113\lccode`~`#1\lowercase{\def~}##1 {\ifcsname
#1##1 ~\D\fi\if\csname#1##1 ~\fi+"#2}}~70~80~90~0A~U2~O3~K4~DB\def
\a[#1]{\let~\endcsname\write6{^^J \the\numexpr#1 }\end}\expandafter\a

```

Used as `etex filename.tex [UA OB DL KH]`. Putting the argument in brackets is necessary: otherwise, eTeX has no way of determining that we reached the end of the argument list.

EDIT: as allowed in the statement of the question, incorrect input can cause (an) error. For instance, `etex filename.tex [OK]` crashes horribly (because `K` is not a valid color).
> 1 votes

# Answer
## PowerShell, 79 ~~80~~

```
($a=$args|sort)|%{$s+=(10,11+4..0)['0DKOU'.IndexOf($_[0])]}
$s/("$a"-eq($a|gu))

```

Throws »Attempted to divide by zero.« if cards appear twice.
> 1 votes

---
Tags: code-golf, card-games
---


title: Play a perfect game of Mu Torere

text:
# Question
Title: Play a perfect game of Mu Torere
# Background

Mu Torere is a game that is one of only two known to be played by the Maori people of New Zealand before European influence. This makes it a very unique game in that it has an "objective winning criterion" and rules of play that are different from most other games in existence.

Gameplay:

The board is an octagon. There are connections between each adjacent vertex, and there is a center node that is connected to all of the vertices. At any point in time, eight of the nine nodes are occupied by stones. At the start, there are four white stones and four black stones that are each take up one half of the octagon, with the center node empty. Black moves first.

Each turn, a player can move one of his stones along one of the 16 edges from one node to the empty node. A stone can only be moved from an outer node to the center node if the stone is next to an opponent's stone.

A player loses when he is unable to make a legal move, which occurs when there is no edge connecting a stone to the empty node.

Here is a website that explains the rules (with a diagram) and offers some analysis.

# The Challenge

Your challenge is to write the shortest program that can play a perfect game of Mu Torere against a human opponent. Your program should be able to display and update the game board, make moves and receive moves from a human opponent. Most importantly, it should play a perfect game.

## Perfect Game?

Yes, perfect game. I've been doing some game analysis, and I found that the game lasts for an infinite amount of time if played perfectly by both sides. This means that your program should never lose. Also, your program should be able to force a win whenever the human opponent makes a mistake that allows the program to force a win. As for how your program finds the perfect move, this is up to you.

## Details

After each move (and at the start of the game), your program should print the game board. However you choose to display the board, it must show all of the nodes and be fully connected (all 16 connection lines should be drawn with no crossed lines). At the start, the board should have the correct starting position. One way of accomplishing this is by making the game board a square.

```
w-w-w
|\|/|
b-o-w
|/|\|
b-b-b

```

The two colors are black and white, or dark/light. The board must show which nodes are occupied by which player's pieces, such as marking them with a "b" or "w", and which node is vacant. Participants are encouraged (but not required) to make the game board more graphical, rather than plain text.

Your game board should have a numbering system that gives each node a unique number. You may choose to number the board any way you like, but it should be explained in your answer or by the program. The square board can be numbered as follows:

```
1-2-3
|\|/|
4-5-6
|/|\|
7-8-9

```

The human is the first to move. His input will be a single number. This will be the number of the node where the moved stone currently is. If I wanted to move a stone from node 4 to an empty node 5, I will type a `4`. The 5 is implied as it is the only empty node.

Assume that the human will always make a legal move.

After the human makes his move, an updated board should be printed. After your program decides on a legal move, it should print another updated board, and then wait for the human to enter another move.

Your program should terminate once it has won.

## Notes

Standard code golf rules apply, no accessing external files, etc., etc. Also, I'm going to impose a flexible time limit of 15 seconds (on a reasonable machine) for your program to make each of its moves. As stated, this game has the possibility to form infinite loops, and I don't want a depth-first search getting into an infinite loop.

# Answer
### Ruby, 390 chars

```
o=->s,c{f=s=~/o/;[*0..8].select{|t|s[t]==c&&(t<1||(t+6)%8+1==f||t%8+1==f||f<1&&(s[(t+6)%8+1]!=c||s[t%8+1]!=c))}.map{|t|k=s*1;k[f]=c;k[t]=?o;k}}
v=->s,c,h{f=o[s,c];f==[]?0:h<1?1:2-f.map{|t|v[t,c>?b??b:?w,h-1]}.min}
q=->g{puts"1-2-3\n|\\|/|\n8-0-4\n|/|\\|\n7-6-5\n".tr"0-8",g;$>.flush}
q[g="obbbbwwww"]
(g.tr!?o,?b;g[gets.to_i]=?o;q[g];q[g=o[g,?w].sort_by{|q|v[q,?w,5]}[-1]])while v[g,?b,5]>0

```

An implementation in ruby which directly calculates the game tree (which takes quite some code) and thus always plays optimally. The board positions are spiraling outwards as shown in the following figure:

```
1 - 2 - 3
| \ | / |
8 - 0 - 4
| / | \ |
7 - 6 - 5

```
> 7 votes

# Answer
## bash and friends (463 447 chars)

```
t(){ tr 0-8a-i $b$b
}
p(){ t<<E
0-1-2
|\|/|
3-4-5
|/|\|
6-7-8

E
}
g(){ b=`tr $x$e $e$x<<<012345678|t`
p
e=$x
}
b=bbbbowwww
e=4
m=0
p
while [ $m != 5 ]&&read x;do
g
m=0
for y in {0..8};do
s=0
S=05011234
grep -E "w.*($y$e|$e$y)"<<<${b:$y:1}30125876340142548746>/dev/null&&for p in wow.\*/ww wow.\*/w bbo.\*/b obb.\*/b www wbw .
do
((s++))
tr $y$e $e$y<<<3012587630/4e|t|grep $p>/dev/null&&break
done
s=${S:$s:1}
[ $s -gt $m ]&&m=$s x=$y
done
g
done

```

Human plays as `b`, computer as `w`. Board position is numbered as in the here doc at the top. It turns out that the heuristics to play a perfect game are surprisingly simple.

On the other hand, losing down the interesting path is quite hard. http://ideone.com/sXJPy demonstrates the shortest possible suicide against this bot. Note that the extra 0 at the end is to test that it breaks out of the loop correctly.
> 5 votes

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


title: Anti-aliasing ASCII art

text:
# Question
Title: Anti-aliasing ASCII art
## Background

ASCII art is the practice of creating images by using ASCII text to form shapes.

Aliasing is the effect created by the large "pixels" of ASCII art, which are the size of characters. The image becomes blocky and hard to see. Anti-aliasing removes this effect by creating a gradient and by softening the hard edges of the ASCII art.

# The Challenge

Your challenge is to write the shortest program possible that will take a piece of ASCII art and will output a version that has been anti-aliased.

## What sort of anti-aliasing?

All of the ASCII art will consist of two types of symbols: Spaces and non-whitespace. For each non-whitespace character, your program must determine whether it is in a position where it need to be anti-aliased. If it is, then you need to replace it with the correct character. If it isn't, then the character stays the same.

How do you know if a character needs to be anti-aliased? The answer depends on the characters that are immediately above, below, left, and right of the character (**not the diagonals**). Here is a chart of when anti-aliasing is required, where `?` and `x` can stand for any non-whitespace character.

```
 x? ->  d?
 ?      ?

?x  -> ?b
 ?      ?

 ?      ?
?x  -> ?F

 ?      ?
 x? ->  Y?

 x  ->  ;   Note: This character has been changed from _ to ;
 ?      ?

 ?      ?
 x  ->  V

?x  -> ?>

 x? ->  <?

 x  ->  @

```

## Input (and example pre-anti-aliasing ASCII art)

First, there will be two lines of input (to STDIN), a number H followed by a number W. There will then be H lines of exactly W characters each (excluding the newline). These following lines will be the ASCII art that needs to be anti-aliased. Here is an example input (not beautiful, but a test):

```
7
9
  888888
 888888
999 98  7
 666666
  666666
   6666
    6

```

## Output (and example anti-aliased art)

Your program should output to STDOUT the ASCII art (of the same dimensions), which has been anti-aliased. Here is the output for the above input. Notice how the the border characters are treated as bordering whitespace.

```
  d8888>
 d8888F
<99 98  @
 Y6666b
  Y6666>
   Y66F
    V

```

This might not look that good (due to the space between lines in the code block), it looks better with larger ASCII art, and the quality depends on the exact font used.

# Another Example

Input

```
12
18
   xx  xxx  xxx
  xxxx  xxx  xxx
 xxxxxx  xxx  xxx
xxx  xxx  xxx  xxx
xxxx xxx  xxx  xxx
 xxxxxx  xxx  xxx
  xxxx  xxx  xxx
x  xx  xxx  xxx  x
xx    xxx  xxx  xx
xxx  xxx  xxx  xxx
xxxx  xxx  xxx  xx
xxxxx  xxx  xxx  x

```

Output

```
   db  <xb  <xb
  dxxb  Yxb  Yxb
 dxxxxb  Yxb  Yxb
dxx  xxb  xxb  xxb
Yxxb xxF  xxF  xxF
 YxxxxF  dxF  dxF
  YxxF  dxF  dxF
;  YF  dxF  dxF  ;
xb    dxF  dxF  dx
xxb  <xF  <xF  <xx
xxxb  Yxb  Yxb  Yx
Yxxx>  Yx>  Yx>  V

```

# Rules, Restrictions, and Notes

Your program should be written in printable ASCII characters only, so that we can make art out of the programs. Other than that, the standard code-golf rules apply.

# Answer
> 9 votes
### Ruby, 180 168 characters

```
gets
w=1+gets.to_i
f=*(readlines*"").chars
f.zip(f[1..-1]+s=[" "],s+f,s*w+f,f[w..-1]+s*w){|a,*b|$><<"@;V#{a}>bF#{a}<dY#{a*5}"[a>" "?(b.map{|y|y>" "?1:0}*"").to_i(2):3]}

```

Another Ruby implementation which takes a zip approach. You can see the second example running online.

*Edit:* Using `readlines` saves 12 characters.

# Answer
> 6 votes
### Ruby ~~275~~ ~~265~~ ~~263~~ ~~261~~ ~~258~~ ~~254~~ ~~244~~ ~~243~~ ~~214~~ ~~212~~ 207

```
H=0...gets.to_i
W=0...gets.to_i
G=readlines
z=->x,y{(H===y&&W===x&&' '!=G[y][x])?1:0}
H.map{|j|W.map{|i|l=G[j][i]
G[j][i]="@V;#{l}>Fb#{l}<Yd#{l*5}"[z[i+1,j]*8+z[i-1,j]*4+z[i,j+1]*2+z[i,j-1]]if' '!=l}}
puts G

```

Sample 1: http://ideone.com/PfNMA

Sample 2: http://ideone.com/sWijD

# Answer
> 5 votes
## Python, 259 chars

```
H=input()
W=input()+1
I=' '.join(raw_input()for i in' '*H)
for i in range(H):print''.join(map(lambda(s,a,b,c,d):(s*5+'dY<'+s+'bF>'+s+';V@'+' '*16)[16*(s==' ')+8*(a==' ')+4*(b==' ')+2*(c==' ')+(d==' ')],zip(I,I[1:]+' ',' '+I,I[W:]+' '*W,' '*W+I))[i*W:i*W+W-1])

```

The program reads the input into a single string `I` (with spaces separating the lines), zips up a list of 5-tuples containing the character and its four surrounding characters, then looks up the result character using string indexing.

# Answer
> 4 votes
Javascript, 410 characters:

```
function(t){m={"10110":"b","11100":"d","01101":"Y","00111":"F","10100":";","00101":"V","00110":">","01100":"<","00100":"@"},d="join",l="length",t=t.split('\n').splice(2),t=t.map(function(x)x.split('')),f=function(i,j)t[i]?(t[i][j]||' ')==' '?0:1:0;for(o=t[l];o--;){for(p=t[o][l];p--;){y=[f(o+1,p),f(o,p+1),f(o,p),f(o,p-1),f(o-1,p)],t[o][p]=m[y[d]('')]||t[o][p]}}t=t.map(function(x)x[d](''))[d]('\n');return t;}

```

ungolfed:

```
function(t){
    m={
        "10110":"b",
        "11100":"d",
        "01101":"Y",
        "00111":"F",
        "10100":";",
        "00101":"V",
        "00110":">",
        "01100":"<",
        "00100":"@"
    },
    d="join",
    l="length",
    t=t.split('\n').splice(2),
    t=t.map(function(x) x.split('')),
    f=function(i,j) t[i]?(t[i][j]||' ')==' '?0:1:0;

    for(o=t[l];o--;){
        for(p=t[o][l];p--;){
            y=[f(o+1,p),f(o,p+1),f(o,p),f(o,p-1),f(o-1,p)],

            t[o][p]=m[y[d]('')]||t[o][p]
        }
    }
    t=t.map(function(x)x[d](''))[d]('\n');
    return t;
}

```

Original, ~~440 characters~~:

```
function (t){m={"10110":"b","11100":"d","01101":"Y","00111":"F","10100":";","00101":"V","00110":">","01100":"<","00100":"@"},s="split",d="join",l="length",t=t[s]('\n').splice(2),t=t.map(function(x) x[s]('')),f=function(i,j)i<0||i>=t[l]?0:(j<0||j>=t[i][l]?0:t[i][j]==' '?0:1);for(o=t[l];o--;){for(p=t[o][l];p--;){y=[f(o+1,p),f(o,p+1),f(o,p),f(o,p-1),f(o-1,p)],h=m[y[d]('')];if(h){t[o][p]=h}}}t=t.map(function(x) x[d](''))[d]('\n');return t;}

```

N.B. I've assumed that the first two input lines are actually irrelevant and the size of the following lines are a correct. I'm also reckoning I might be able to chop a few more chars off this when I get a chance!

# Answer
> 3 votes
## PHP - ~~359~~ ~~330~~ ~~282~~ ~~268~~ 257 characters

```
<?php
$i=fgets(STDIN)+0;$w=fgets(STDIN)+1;$s='';$m='@<;d>0b0VY00F000';
for(;$i--;)$s.=fgets(STDIN);
for(;++$i<strlen($s);){
$b=trim($s[$i])?0:15;
foreach(array($i+1,$i+$w,$i-1,$i-$w)as$k=>$x)
$b|=pow(2,$k)*(isset($s[$x])&&trim($s[$x]));
echo $m[$b]?$m[$b]:$s[$i];}

```

# Answer
> 2 votes
# Python, 246 241

```
H=input();W=1+input()
S=' '
o=W*S
F=o+'\n'.join((raw_input()+o)[:W-1]for k in range(H))+o
print ''.join((16*x+'@;<d>b'+2*x+'V'+x+'Y'+x+'F'+3*x)[
16*(x>S)|8*(a>S)|4*(l>S)|2*(r>S)|(b>S)]for
x,a,l,r,b in zip(F[W:-W],F,F[W-1:],F[W+1:],F[2*W:]))

```

WC and test on sample 2, diffed with the output of the Ruby solution at the top:

```
t:~$ wc trans.py && python trans.py < lala2 > o && diff -q o ruby_out2_sample
  2 11 241 trans.py
t:~$

```

# Answer
> 1 votes
## C# ~~591~~ 563

```
string A(string t){var s=new StringReader(t);var h=int.Parse(s.ReadLine());var w=int.Parse(s.ReadLine());var lines=s.ReadToEnd().Split(new[]{"\r\n"},StringSplitOptions.None).Select(x=>x.ToCharArray()).ToArray();for(var i=0;i<h;i++)for(var j=0;j<w;j++){var c=lines[i][j];if(c==' ')continue;var n=(i>0?(lines[i-1][j]!=' '?1:0):0)+(i<h-1?(lines[i+1][j]!=' '?2:0):0)+(j>0?(lines[i][j-1]!=' '?4:0):0)+(j<w-1?(lines[i][j+1]!=' '?8:0):0);lines[i][j]=new[]{'@','V',';',c,'>','F','b',c,'<','Y','d',c,c,c,c,c}[n];}return string.Join("\r\n",lines.Select(l=>new string(l)));}

```

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


# Question
Title: Program that determines whether an int is greater or lesser
Write a program which prompts a user to input two integers A and B, the program should determine whether A is greater than or lesser than B without the use of greater than \[\>\] or less than \[\<\] operators (and similar operators or methods like .compare) and should output :

```
Integer A is greater than B.

Rules  : No Brainfuck.

```

Should work for negative numbers. Signed int. Code's for equality isn't necessary.

Edited Again.

# Answer
> 10 votes
## Javascript

Here's the basic format of all the solutions. This case returns `true` if `a>b` and `false` otherwise:

```
function greaterThan(a,b){
    c=a;//Copy a
    while(true){
        if(b==a){
            return false;
        }
        if(b==c){
            return true;
        }
        a++;//Approaches b if a<b
        c--;//Approaches b if a>b
    }
}

```

**Warning:** Since we didn't need to support the `A==B` case, the next 3 solutions will lock up for those inputs. Thus, don't fill in equal or empty numbers at the prompts in the test fiddles, unless of course you like pushing red buttons that say "Do **NOT** push!!!"

**149 chars** \- Fiddle: Conforms EXACTLY to specs ;)

`for(A=B='A',C='B',a=c=prompt(A),b=prompt(C);b!=c++||(B=C),b!=a--||(A=C),A==B;);alert("Integer "+B+" is Greater than "+A+".\n\n\nRules : No Brainfuck.")`

**74 chars** \- Fiddle: Prompts user for 2 numbers, alerts '-1' if 1st\<2nd, '1' if 2nd\>1st:

```
for(A=0,a=c=prompt(),b=prompt();b!=c++||(A=-1),b!=a--||(A=1),!A;);alert(A)

```

**54 chars** \- Fiddle: Function that takes 2 parameters and returns `true` if `A > B`, `false` if `A < B`, and, of course, locks up if `A==B`.

```
function a(a,b){for(c=a;b!=++a&&b!=--c;);return b!=a;}

```

# Answer
> 6 votes
# Python

```
from sys import argv as s
a,b=int(s[1]), int(s[2])
if a==b:
 print 'They are the same!'
else:
 print 'Integer A is greater than B.' if (abs(a-b)==a-b) else 'Integer B is greater than A.'

```

# Python - 73 characters

if inputs as arguments is acceptable as 'input', it is only 73 characters:

```
def c(a,b):
 if a==b:
  return 'They are the same!'
 else:
  return 'Integer A is greater than B.' if (abs(a-b)==a-b) else 'Integer B is greater than A.'

```

if the weak inequality is all we care about, and we don't have to take input, it's shorter (33 characters):

```
print a if (abs(a-b)==a-b) else b

```

# Answer
> 5 votes
## C

```
#include<stdio.h>

int main(int argc, char** argv) {
    int a, b;
    long long c;
    double d;
    printf("A: ");
    scanf("%d", &a);
    printf("B: ");
    scanf("%d", &b);
    c = (long long)a - (long long)b;
    if (c == 0) {
        puts("Integer A is equal to B.");
    }
    else {
        d = *(double*)&c;
        if (d == d) {
            puts("Integer A is greater than B.");
        }
        else {
            puts("Integer B is greater than A.");
        }
    }

    return 0;
}

```

It was golfed but then I realized this wasn't a golf. So now it's not. ;)

To understand how this works, you have to understand how numbers are integers and floats are represented, bitwise, and how the CPU operates on them.

I'm starting out by getting two 32-bit signed integers. They are stored as ints to bound the input. I then cast them to long longs, basically converting them to 64-bit integers, and then subtract. This subtraction is important. If A is larger than B, the result will be positive. If they're equal, the result is 0, and if B is larger than A, the result is negative. The negative case is the key, here, because of how it's represented as an integer in memory. A negative integer is stored as a 2's complement, and since these are 64-bit integers, we'll have at least one DWord of 1s in the MSBs in memory. I then store that into a 64-bit double variable, turning it into a double value with the same bit encoding. If it is negative, this double value is a NaN. By IEEE floating point rules, comparing a NaN with itself will always result in `false`, which indicates that A \< B.

And of course, a simple zero check can add an equivalence check to the algorithm.

**EDIT:** This now works for very large and very small ints. It requires a 64-bit compiler, where `long long` is defined as having a size of 8 bytes. Unfortunately, gcc in Cygwin didn't do the trick, so I had to use Visual Studio. But, it works. This, I found, does not work for very large and very small 32-bit integers. I will be investigating a solution.

# Answer
> 4 votes
## Python

```
r="less"
try:(input()-input())**.5;r="greater"
except:pass
print "Integer A is",r,"than B"

```

# Answer
> 3 votes
## Scala

Based on the revised question:

```
object G extends App
{
    def g(i:BigInt,j:BigInt)=
    {
        def q(a:BigInt,b:BigInt):String=
        {
            if(a==0)
                "Integer B is greater than A."
            else
                if(b==0)
                    "Integer A is greater than B."
                else
                    q(a+1,b-1)
        }
        if(i!=j)q(i-j,i-j)else"A and B are equal"
    }
    val(a,b)=(readLine("A: ").toInt,readLine("B: ").toInt)
    println(g(a,b))
}

```

# Answer
> 3 votes
Since most of the questions about the spec have been answered, here's a solution in C#. If the size of the ints isn't 32-bit then `int` needs changing for a suitable type.

```
namespace Sandbox {
    class Program {
        private static int _Compare(int a, int b) {
            if (a == b) return 0;
            int sgnA = (a & int.MinValue) == int.MinValue ? -1 : 1;
            int sgnB = (b & int.MinValue) == int.MinValue ? -1 : 1;
            // If they have different signs then the negative one is smaller.
            if (sgnA != sgnB) return sgnA;
            // If they're both non-negative then the difference won't overflow.
            // If they're both negative, then the different won't overflow. Worst case is (-1) - int.MinValue = int.MaxValue
            return ((a - b) & int.MinValue) == int.MinValue ? -1 : 1;
        }

        public static void Main(string[] args) {
            if (args.Length == 0) {
                // Test mode.
                int[] cases = new int[] {
                    int.MinValue,
                    int.MinValue + 1,
                    int.MinValue + 2,
                    int.MinValue / 2 - 2,
                    int.MinValue / 2 - 1,
                    int.MinValue / 2,
                    int.MinValue / 2 + 1,
                    int.MinValue / 2 + 2,
                    -2, -1, 0, 1, 2,
                    int.MaxValue / 2 - 2,
                    int.MaxValue / 2 - 1,
                    int.MaxValue / 2,
                    int.MaxValue / 2 + 1,
                    int.MaxValue / 2 + 2,
                    int.MaxValue - 2,
                    int.MaxValue - 1,
                    int.MaxValue,
                };
                foreach (int _a in cases) {
                    foreach (int _b in cases) {
                        int _cmp = _Compare(_a, _b);
                        Console.WriteLine(string.Format("{0}\t{1}\t{2}\t{3}", _a, _b, _cmp, _cmp == _a.CompareTo(_b) ? "OK" : "Error"));
                    }
                }
            }
            eise if (args.Length != 2) {
                Console.Error.WriteLine("Expected two arguments.");
            }
            else {
                int a, b;
                if (!int.TryParse(args[0], out a) || !int.TryParse(args[1], out b)) { Console.Error.WriteLine("Both arguments must be integers"); return; }

                int cmp = _Compare(a, b);
                Console.WriteLine(cmp == -1 ? "Integer A is less than B" : cmp == 0 ? "Integer A equals B" : "Integer A is greater than B");
            }
        }
    }
}

```

All of the test cases pass.

# Answer
> 3 votes
## Scala:

```
object G extends Application {
  def g (a: Byte, b: Byte) = (a & -128, b & -128) match {
        case (0, 0) => if (((a - b) & -128) != 0) "<" else ">"
        case (x, 0) => "<"
        case (0, x) => ">"
        case _ => if (((b-a) & -128) != 0) ">" else "<"
  }
  val r = g (readByte, readByte)
  println ("A is " + (if (r==">") "greater than" else "less than") + " B")
}

```

Since `ints` vary from language to language, I choosed Bytes here, because it allowed me to do exhaustive testing.

Of course it can easily be adapted to short/int/long, with Int.MIN\_VALUE etc. instead of -128.

The 4 cases test for

* both values are positive
* only first
* only second
* none of them

It took me 60 minutes to golf it down to 297 chars, until I noticed, that it isn't a golf! And another 10 minutes for hitting 80x `undo` (real programmers don't do backups).

# Answer
> 3 votes
## Javascript: (108 chars without spaces)

```
function C(a,b) {
    var d=a-b,
        z=!!(d/Math.abs(d)+ 1),
        m=z?a:b,
        n=z?b:a;
    return 'Integer '+m+' is greater than '+n;
}

```

tests:

```
console.log( C (1, 3) );    // Integer 3 is greater than 1
console.log( C (3, 2) );    // Integer 3 is greater than 2
console.log( C (-3, -8) );  // Integer -3 is greater than -8
console.log( C (-9, 0) );   // Integer 0 is greater than -9

```

Code for equality is not required, so I didn't do it.

# Answer
> 2 votes
## Ada, 76 Characters

```
function C(A,B:Integer)return Integer is
begin return (A-B)/abs(A-B);end C;

```

returns -1 for A smaller than B, and 1 for A bigger than B.

for A=B an exception will be raised, but the behaviour in this case isn't specified in the task description.

# Answer
> 2 votes
## D (51 chars)

```
int d(int a,int b){return a-b?(a-b)&-1<<31?-1:1:0;}

```

using signed representation

returns `-1`,`0`,`1` for `less than`, `equals to` and `greater than` resp.

with reading from user: **91 chars**

```
import std.stdio;void main(){int a,b;readf("%d %d",&a,&b);writeln(a-b?(a-b)&-1<<31?-1:1:0);}

```

# Answer
> 1 votes
## PHP

PHP's too verbose for a task this simple, but I'm in PHP mode so I'll go ahead:

```
function d($a,$b){return $a-$b;}
// Returns a negative number if $a < $b, positive if $a > $b, 0 if $a == $b

```

If you need it to always return the same values, then

```
function d($a,$b){return ($d=$a-$b)?$d/abs($d):0;}
// Returns -1 if $a < $b, 1 if $a > $b, 0 if $a == $b

```

If you want it to output text, you could do something like:

```
function d($a,$b){$d=$a-$b;echo !$d?'equal':(abs($d)==$d)?'greater than':'less than';}

```

# Answer
> 1 votes
## Objective-C - 161 chars + full string

This solution prompts the user, gets the value, and then returns the full string.

Usage - self-explanitory, it requests a with 'a?' and then once inputted, requests b with 'b?'.

```
int a,b,x;char c='A';NSLog(@"a?");scanf("%i",&a);NSLog(@"b?");scanf("%i",&b);
x=(a-b/abs(a-b)==1);NSLog(@"Integer %c is greater than integer %c.",c+!x,c+x);

```

And readable version (with whitespace)

```
int a,b,x;
char c = 'A';
NSLog(@"a?");
scanf("%i", &a);
NSLog(@"b?");
scanf("%i", &b);
x = (a-b/abs(a-b) == 1);
NSLog(@"Integer %c is greater than integer %c.", c+!x, c+x);

```

Output:

```
Computer: a?
Me: 2
Computer: b?
Me: 3
Computer: Integer B is greater than integer A.

```

# Answer
> 1 votes
## Haskell, 150 characters

```
main=putStr.g.f.map read.words=<<getLine
f[a,b]|b`elem`dropWhile(/=a)[(minBound::Int)..]="BA"|0<1="AB"
g[x,y]="Integer "++x:" is greater than "++y:"."

```

I could use `Integer` and do subtraction, but I felt like dealing with overflow problems that arise from using `Int`.

Note there is a `<` in the code, but it is used to compare a constant expression (one character less than writing `True`).

# Answer
> 1 votes
## C

```
void AgB(int a, int b) {
(( 2 * a + 1) / (2 * b + 1) == 0) ? printf("Integer B is greater than A\n") : printf("Integer A is greater than B\n");}

```

# Answer
> 1 votes
## Python alt-way

```
#!/usr/bin/python

import sys
a, b = map(int, sys.argv[1:3])
s = '==' if (a == b) else '<' if (str(a-b)[0] == '-') else '>'
print 'a(%d) %s b(%d)' % (a, s, b)

```

# Answer
> 1 votes
If equility is not matter, just doing `sorted([A,B]) != [A,B]` should do, so

```
a=[input(),input()];print"A is "+["less","great"][sorted(a)!=a]+"er than B"

```

Tests

```
>>> a=[input(),input()];print"A is "+["less","great"][sorted(a)!=a]+"er than B"
1
2
A is lesser than B
>>> a=[input(),input()];print"A is "+["less","great"][sorted(a)!=a]+"er than B"
2
1
A is greater than B
>>> a=[input(),input()];print"A is "+["less","great"][sorted(a)!=a]+"er than B"
-1
-2
A is greater than B
>>> a=[input(),input()];print"A is "+["less","great"][sorted(a)!=a]+"er than B"
-2
-1
A is lesser than B

```

# Answer
> 1 votes
## Python, 152 characters

Conforms to the letter with the specification.

No cheating with conditionals of any kind, including equality. The `abs` call probably has a conditional hidden, if I weren't golfing I would do `x/=int(math.sqrt(x*x))` as the third line.

```
i=input
x=i("A")-i("B")
x/=abs(x)
print "Integer",chr((131-x)/2),"is greater than",chr((131+x)/2)+".\n\n\n\nRules  : No Brainfuck."

```

# Answer
> 1 votes
## BF, handles negative zero

I figured it would be fun to invent a language for the job, using characters `<` and `>` for something completely unrelated to inequality comparison.

```
# parse first number (space delimited)
+>,---------------------------------------------
[<->[->+<]]<[->+>,---------------------------------------------<<]>
>+++++++++++++[
  <<[->>>+<<<]>>----------------
  [-<<+>>]>[-<<<++++++++++>>>]<
  ,--------------------------------]
# parse second number (newline delimited)
+>,---------------------------------------------
[<->[->+<]]<[->+>,---------------------------------------------<<]>
>+++++++++++++++++++++++++++++++++++[
  <<[->>>+<<<]>>--------------------------------------
  [-<<+>>]>[-<<<++++++++++>>>]<
  ,----------]
# handle minus signs
<[<<[-<[->+<]>>[-<<+>>]<[->+<]>>-<<]>>[-<[-]<<+>>>]]
<<[-<[-]>>+<]
# compare
<+>>+[-<<-[>]>]
# report
>[[-]++++++++++++++++++++++++++++++
     ++++++++++++++++++++++++++++++.<]
<<<[[-]+++++++++++++++++++++++++++++++
       +++++++++++++++++++++++++++++++.>]

```

For a brief summary of operators: `<` and `>` move the cursor backward/forward; `+`/`-` increment/decrement the value of the number pointed to by the cursor (hereafter referred to as "the accumulator"); `[]` iterate while the accumulator is non-null; `,` reads a byte from input to the accumulator; `.` writes the accumulator to the output. Anything else is ignored, which provides a cool way to implement comments, that can even be made to look like comments in other scripting languages.

Handles negative numbers by checking for the following cases:

* if both numbers are signed negative, swap them
* if only one number is negative, zero it out and increment the other one
* else just leave them alone

This lets us compare zero with negative zero (`-0 < 0`). Equality is not handled.

Funny how I/O takes more than twice the space the math does.

# Answer
> 1 votes
# Python, 86

```
a,b=input('A,B')
print 'Integer A is %s than B.'%('less'if abs(a-b)-a+b else'greater')

```

# Answer
> 1 votes
## FORTRAN 77

I guess good old Fortran arithmetic if does not violate the requirements of the question. Here it is

```
      PROGRAM TEST
      READ *, A
      READ *, B
      IF (B-A) 99,100,101
99    PRINT *, 'Integer A is greater than B'
      GOTO 102
100   PRINT *, 'they are equal'
      GOTO 102
101   PRINT *, 'Integer B is greater than A'
102   STOP
      END

```

# Answer
> 1 votes
C# approach with 44 chars. I just subtract a from b and check if there is a minues in the result string:

```
bool c(int a, int b){return ("" + (b - a))[0] == 0x2d;}

```

# Answer
> 0 votes
# *C (K&R) - 49 chars*

This is indeed trivial...

```
a,b;main(){scanf("%d%d",&a,&b);printf("%d",a-b);}

```

negative result if a \> b, positive if a \< b, 0 if equal

**EDIT:** This answer corresponds to the very first specs of the question, when golfing was required and the output was not restricted to specific phrases.

# Answer
> 0 votes
## Haskell - 18 characters

```
main=print.compare

```

Returns GT if a \> b, LT if a \< b.

Or since this question's output is completely unspecified, I can do

```
main=print.(-)

```

which returns a negative number if a \< b, or a positive number if a \> b.

EDIT: I didn't see what the exact output has to be (see below)

```
main = print.f
f x y|q==GT=g b|q==LT=g c where q=compare x y
a="Integer A is "
b="greater than"
c="less than"
e=" B."
g x=a++x++e

```

BTW, this golf sucks.

# Answer
> 0 votes
## Perl

```
for(0..9){
 $s.=("2"x$_)."1".("0"x(9-$_))
}
for(0..9){
  $a=$_;
  for(0..9){
   $c[$a][$_]=chop$s
  }
}
$_=<>;
$b=<>;
$l=length;
$_="0"x length$b.$_;
$b="0"x$t.$b;
for(1..$l){
 $e.=chop;$f.=chop$b
}
$g="Integer A is";
$h=" than Integer B";
for(1..$l){
 $t=$c[$_][$b];
 if($t==2){die"$g less$h"}
 if($t==0){die"$g greater$h"}
}

```

This creates a look-up array for all of the comparisons of each digit. It then takes two unsigned integers as input. It makes them the same length. It then compares them one digit at a time using the look-up array. I am sure it could be made a lot shorter.

# Answer
> 0 votes
## JavaScript (65)

Enter in Mozilla Firefox's Web Console:

```
'Integer A is '+(eval(prompt())>>>31?'less':'greater')+' than B.'

```

The user should separate the two signed integers (which should each fit in 31 bits) with " - ". The program takes the difference and checks the sign bit.

---
Tags: code-challenge
---


title: Line through Polygon

text:
# Question
Title: Line through Polygon
**Input**: A line of the standard slope-and-intercept form: `mx+b`, as well as a set of Cartesian points determining the vertices of a polygon. Assume that the x and y values of the points will be integers.

**Output**: A boolean, which is true if the line enters or touches the polygon, and is false otherwise.

This is a little tricky, so I'll give a clue: turn the vertices that determine an edge into lines.

**Test Cases**
`2x+3 (1,2) (2,5) (5,10) -> False`
`5x+0 (5,10) (2,10) (2,-10) (5,-10) -> True`
`0.5x+3.1 (1, 2), (-1, 2), (5, 8), (6, 7), (2, 10) -> True`

Shortest **or** most creative code wins. I don't know too many languages, so explain your algorithm in your post. Good luck!

# Answer
## J, 80 characters

```
('True';'False'){~*/2=/\0>_2(]-1{y+0{y*[)/\2}.[y=.".'-_x + ( , ) 'charsub 1!:1[1

```

Takes input from the keyboard in the format specified in the question. It uses the algorithm suggested by Peter Taylor in the comments to the question.

Explanation (bearing in mind that J is read from right to left):

`1!:1[1` waits for a line of input from the keyboard.

`'-_x + ( , ) 'charsub` replaces all occurances of `x`,`+`,`(`,`,` and `)` with a space and replaces `-` with `_`. This turns the input into a list of numbers (with `_` in front of the negative numbers as required for J).

`".` reads in the list as an array instead of a string.

`y=.` assigns the list to the variable `y`.

`2}.` removes the first 2 elements of the list.

`_2(...)/\` takes each pair of numbers and applies the verb in the brackets to them.

`]-1{y+0{y*[` calculates `mx+c` with the `x` from this pair of numbers and takes the result out of the `y` from this pair of numbers.

`0>` checks if each returned number is less than `0`.

At this point we have a list of `1`s and `0`s depending on whether each point is above or below the line.

`2=/\` takes each pair and checks if they are equal.

Now, if all points are on the same side of the line we have all `1`s otherwise there are `0`s in there somewhere.

`*/` multiplies all the `1`s and `0`s together.

Now we have `0` if the points fall on both sides of the line and `1` and they all fall on the same side of the line.

`{~` uses the `1` or `0` as an index into the list `('True';'False')` returning the required output.
> 0 votes

# Answer
### Ruby, 103 101 characters

```
m,b,*q=gets.scan(/[\d\.]+/).map{|t|t.to_f}
s=t=!0
q.each_slice(2){|x,y|x=x*m+b;s|=x<=y;t|=x>=y}
p s&t

```

Input is on STDIN in the form specified in the question while output goes to STDOUT.
> 4 votes

# Answer
### Scala ~~255:~~ 224

```
object P extends App{
val(m,p)=(args(0).split("[^0-9-.]").filter(!_.isEmpty)).map(_.toFloat)splitAt 2
def v(l:Array[Float])=(l(1)-m(0)*l(0)-m(1))*(l(3)-m(0)*l(2)-m(1))<=0
println((p.drop(p.size-2)++p).sliding(4,2) exists v)}

```

Using splitAt, inspired by Howard. :) Before:

```
object P extends App{
val f=args(0).split("[^0-9-.]").filter(!_.isEmpty)
val m=f.take(2).map(_.toFloat)
val p=f.drop(2).map(_.toInt)
def v(l:Array[Int])=(l(1)-m(0)*l(0)-m(1))*(l(3)-m(0)*l(2)-m(1))<=0
println((p.drop(p.size-2)++p).sliding(4,2).exists(v))
}

```

How:

```
val f=args(0).split("[^0-9-.]").filter(!_.isEmpty)

```
* Line 2 just splits and filters away everything which isn't part of float or int, since we don't need '(' and ',' and such to identify our parameters - position is enough.
* m is shorthand for mn in m\*x+n, the values m and n are floats.
* p is the polygon values.
* v is the verify function

Assume we have f(x) = mx + n and the line pq:

```
               f(x)=mx+n
 |            /
 |          / |
 |p  *'--,,'  |
 |   |   / ''-* q
 |   | /
 |   /
 | /
 /___________________

```

f(x) crosses only by random the origin in this example. For the two points of the polygon p and q we can for px calculate f(px) and it can lay to the south or to the north of py, the real value of the polygon, or lay exactly on it.

If both calculated values f(px) and f(qx) are on the same side, north or south, the line doesn't cross.

So we have two values for the function:

```
val a = m*px+n
val b = m*qx+n

```

`if (a == py || b == qy)` the function line touches one of the points.

`if ((a < py && b > py) || (a > py && b < py))` they are on different sides, and cross as well. We can express this by substracting:

```
d1 = py - a
d2 = qy - b

if (( d1 == 0 || d2 == 0 || (sign (d1) != sign(d2))) ...

```

If the signs are different, the multiplication will return a negative value, and if they match, it returns a positive value. If one of the values is 0, the product is null. So we can condense the whole question to:

```
d1 * d2 <= 0

```

And that's what the verify-method v does.

The values of the polygon are (x1, y1), (x2, y2), ...(xn, yn), but they are flattened to x1, y1, x2, y2, ...xn, yn. The drop-statement takes the last 2 of them and prepends them to the front, to build a closed shape (xn, yn -\> x1, y1). Sliding (4, 2) takes 4 values and advances for a step size of 2 through the collection. If a pair of xy exists, for which the verify function returns true, the line crosses the polygon or touches it.

Now I have to understand why the Ruby solution is so much shorter. Okay - a few less type declarations, shorter conversions. No println, no object, no App. Similar approach.

Invocation:

```
 scala P "0.5x+3.1 (1, 2), (-1, 2), (5, 8), (6, 7), (2, 10)"

```
> 2 votes

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


# Question
Title: Universal (rule-bending) Code Golf solver
Code golf always involves some answers that bend the rules more or less by breaking constraints that the challengers took for granted or just haven't thought about and didn't list in the rules. One of these interesting loopholes is the possibility to output *more* than the challenge asks for to get a better result.

Taking this to extremes, we can write an universal code golf solver that prints the desired output — if you don't care that it might take ages and outputs lots of other stuff before and after it.

All we need to output is a sequence that is guaranteed to contain every possible subsequence. For this code golf, this will be the Ehrenfeucht-Mycielski sequence:

> The sequence starts with the three bits 010; each successive digit is formed by finding the longest suffix of the sequence that also appears earlier within the sequence, and complementing the bit following the most recent earlier appearance of that suffix.
>
> Every finite subsequence of bits occurs contiguously, infinitely often within the sequence
>
> The first few digits of the sequence are:
>
> > 010011010111000100001111... (sequence A038219 in OEIS).

Combining 8 bits of the sequence to a byte, we'll get ASCII output that we can output to the screen or to a file and that contains *every possible finite output*. The program will output parts of pi, the lyrics of “Never gonna give you up”, some nice ASCII art, its own source code, and everything else you could want it to output.

For testing correctness, here are hashes for the first 256 bytes of the sequence:

```
MD5: 5dc589a06e5ca0cd9280a364a456d7a4
SHA-1: 657722ceef206ad22881ceba370d32c0960e267f

```

The first 8 bytes of the sequence in hexadecimal notation are:

```
4D 71 0F 65 27 46 0B 7C

```

Rules:

* Your program must output the Ehrenfeucht-Mycielski sequence (nothing else), combining 8 bits to a byte/ASCII character.
* Shortest program (character count) wins. Subtract 512 from your character count if you manage to generate the sequence in linear time per generated byte.

# Answer
> 7 votes
## C, –110 chars

This version of the program uses the linear-runtime algorithm to generate the sequence. Subtracting 512 from the 402 chars in the program gives a total of negative 110.

```
#define C v=calloc(7,8),v->p=p
#define G(F,K)u->F[d[K]]
#define S(F,T)G(f,T)=F,G(t,T)=T,G(n,T)=
struct{int p,f[2],t[2];void*n[2];}r,*u,*v,*w;char*d,c;p,b,h,i,j,k;
main(s){for(;d=++p-s?d:realloc(d,s*=2);){d[i=p]=b;c+=c+b;p%8||putchar(c);
for(u=&r;b=u->p,u->p=p,w=G(n,k=i);S(i,k)v=G(n,k),u=v)for(h=G(f,k),j=G(t,k);j>h;--i,--j)
if(d[i]-d[j]){S(i,k)C;u=v;S(h,j)w;S(0,i)C;b=w->p;goto x;}S(0,i)C;x:b=1-d[b+1];}}

```

As per the problem, the program runs in an infinite loop, which necessitates lots of memory allocation, and using `realloc()` to keep the sequence contiguous can contribute to heap fragmentation. You can improve the program's memory usage by replacing `calloc(7,8)` on the first line with `calloc(1,sizeof*v)`. This will help especially on a 32-bit machine, where 56 is likely too large by a factor of two.

The code is kind of unreadable, and not in an interesting way; for that I apologize. Frankly, even the ungolfed version isn't terribly clear:

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

typedef struct branch branch;
typedef struct node node;

struct branch {
    int from, to;
    node *next;
};

struct node {
    int pos;
    branch br[2];
};

static node root = { 0 };

static unsigned char *data = NULL;
static int endpos = 0;
static int size = 1;

static node *mknode(void)
{
    node *n;

    n = calloc(1, sizeof *n);
    n->pos = endpos;
    return n;
}

static branch *getbranch(node *n, int p)
{
    return &n->br[data[p]];
}

static void setbranch(node *n, int from, int to, node *next)
{
    n->br[data[to]].next = next;
    n->br[data[to]].from = from;
    n->br[data[to]].to = to;
}

int main(void)
{
    node *u, *v, *w;
    int follower, from, i, i0, j;
    int out, b;

    out = b = 0;
    for (;;) {
        ++endpos;
        if (endpos == size) {
            size *= 2;
            data = realloc(data, size);
        }
        data[endpos] = b;
        out = (out << 1) | b;
        if (endpos % 8 == 0) {
            putchar(out);
            out = 0;
        }

        i = endpos;
        u = &root;
        for (;;) {
            follower = u->pos + 1;
            u->pos = endpos;
            w = getbranch(u, i)->next;
            if (!w)
                break;
            i0 = i;
            from = getbranch(u, i0)->from;
            for (j = getbranch(u, i0)->to ; j > from ; --j) {
                if (data[i] != data[j]) {
                    /* divide branch */
                    v = mknode();
                    setbranch(u, i, i0, v);
                    u = v;
                    setbranch(u, from, j, w);
                    setbranch(u, 0, i, mknode());
                    follower = w->pos + 1;
                    goto bitfound;
                }
                --i;
            }
            v = getbranch(u, i0)->next;
            setbranch(u, i, i0, v);
            u = v;
        }
        /* extend branch */
        setbranch(u, 0, i, mknode());

      bitfound:
        b = 1 - data[follower];
    }
}

```

(The ungolfed code above is based on the code written by Grzegorz Herman and Michael Soltys, as referenced in the problem description, and from Soltys' home page.)

Thanks to @schnaader and @r.e.s. for reporting a bug in the initial version.

# Answer
> 6 votes
### Ruby, 109 104 101 94 characters

```
s=?0
loop{s=(s[/(.*).*\1/][/.#{$1}/]<?1??1:?0)+s
s.size&7<1&&$><<[s.reverse.to_i(2)].pack(?C)}

```

Implementation in Ruby using regular expressions for suffix search. Since it takes quite a long time until out-of-memory the program has to be terminated by the user.

*Edit:* I just noticed that it is enough to start with the sequence `0`.

*Edit 2:* The proposal of r.e.s. saves 2 characters, some others because we do not have to cut out a single byte before `pack`.

# Answer
> 4 votes
## Perl, 95 chars

I actually had a halfway decent version of this at first. Then as I golfed, each version got slower. Increasingly slower.

```
$|=$_="010";
y///c%8||print pack"B*",/(.{8})$/while/(.+)$(?(?{m|.*$^N(.)|})(?{$_.=1-$^N})|(?!))/

```

The first three characters (`$|=`) aren't necessary, strictly speaking ... but without that there, you'd typically have to wait for the script to finish generating a full 4096 bytes before you'd see any of the output. And that would take hours. Maybe centuries; I'm not sure. Did I mention that this program's performance kind of deteriorates over time? So because of that I kind of felt compelled to include them in the count.

On the other hand, this script has one of the ugliest regexes I've ever created, so I think I'm proud of it.

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


title: Reversing base numbers

text:
# Question
Title: Reversing base numbers
Where input is binary, convert it to a decimal number (base 10), reverse the decimal number and output it. Vice versa for decimal (base 10) input: reverse it, convert it to binary and output the binary number.

**Sample Input**:

```
00000001
00000010
255
00011000

```

**Sample Output**

```
1
2
1000101000
42

```

other **Sample Input**

```
78
35
01011001
231

```

other **Sample Output**

```
01010111
00110101
98
10000100

```

# Answer
## Ruby, 68 characters

```
puts$<.map{|i|i[/[^01\s]/]?"%08b"%i.reverse: i.to_i(2).to_s.reverse}

```

Uses stdin/stdout, interprets lines that consist only of 1s, 0s and whitespace as binary numbers, everything else as decimal.
> 4 votes

# Answer
## JavaScript, ~~140~~ 199 bytes

```
(function(x){s=x.split("\n"),r=b='';for(i in s)r+='\n'+(s[i].replace(/[01]*/g,b)?
(s[i].split(b).reverse().join(b)-0).toString(2):(parseInt(s[i],2)+"")
.split(b).reverse().join(b));return r.trim()})('1\n10\n255\n11000')

```

Excluding input. It requires, however, that there are no numbers present in the input which are base 10 and only have `1`s / `0`s in them.
> 2 votes

# Answer
# perl - 90 89

```
map{print reverse(/^[01]+$/?unpack"N",pack"B*",sprintf"%032d",$_:sprintf"%b",$_).$/}@ARGV

```

Any number containing only 1's and 0's is considered binary.
Funny how so much more code is required for bin-\>dec vs. dec-\>bin...
> 2 votes

# Answer
# Python - 117 characters

```
while 1:
 x=raw_input()
 if(not(False in map(lambda x:x in ("1","0"),s))):print int(x,2)
 else:print bin(int(x))[2:]

```

This golf relies heavily on the fact that python counts a single space as a full indentation. Note that this golf IS NOT ERROR-PROOF. While functional, it will throw an EOFError when there is no input. Protecting against this requires an extra 30 characters.

# Changelog

**v0** \- 120 chars

**v1** \- 117 chars - changes "While True" to "While 1"
> 1 votes

# Answer
Quite frankly, i still don't get the testcase for `255`, i'll mend my solution when the OP corrects/expands the description.

My Solution is based of *rmckenzie*

### Python - 84 bytes

```
while 1:
 x=raw_input()
 print all(i<"2"for i in x)and int(x,2)or bin(int(x))[2::]

```
> 1 votes

# Answer
### bash 67

```
b(){ [[ $1 =~ ^[01]*$ ]]&& s="i"||s="o";echo $s"base=2;$1"|bc|rev;}

```
> 0 votes

# Answer
## J, 60 characters

```
((1&":@#:@(10&#.@|.)`(|.@":@#.))@.(0=[:+/1<[))".;' ',.1!:1[1

```
> 0 votes

---
Tags: code-golf, conversion
---


title: Words from periodic table of elements

text:
# Question
Title: Words from periodic table of elements
Back when I was a freshman in highschool taking chemistry, I'd look at the periodic table of elements and spell dirty words out with the number of the elements (HeCK would be 2619, 2-6-19).

I was thinking about this the other day when I saw an amazing shirt that spelled out BeEr (4-68)

So my codegolf challenge is shortest program to output a list of words you can spell with the periodic table of elements AND the number code that would represent that word.

/usr/share/dict/words or whatever dictionary you want to use for the word list. If you're using a "non-standard" word list, let us know what it is!

# Answer
> 6 votes
## GolfScript (339 303 302 301 294 chars)

```
n/{{{32|}%}:L~['']{{`{\+}+'HHeLiBeBCNOFNeNaMgAl
PSClArKCa TiVCrMnFe

ZnGaGeAsSeBrKrRbSrYZr
MoTcRuRhPdAgCd

TeIXe
BaLaCePrNdPmSmEuGdTbDy
ErTm
Lu
TaWRe
IrPtAuHgTl

AtRnFrRaAcThPaU

AmCm

EsFmMd
LrRfDbSg

MtDsRg
UutFl
Lv'{[1/{.0=96>{+}*}/]}:S~:^/}%.{L}%2$?.){=S{^?}%`+p 0}{;{L.,2$<=},.}if}do}%;

```

With credit to PhiNotPi whose observation on unnecessary elements allowed me to save 33 chars.

This is IMO much more idiomatic GolfScript than the previous recursive approach.

Note that I allow words in the dictionary to be mixed case (`L` is a function to lower-case text on the assumption that it doesn't matter if non-alpha characters get broken) but reject any with apostrophes or accents.

Since this is code golf, I've optimised for code length rather than speed. This is horrendously slow. It expects the word list to be supplied at stdin and outputs to stdout in the format:

```
"ac[89]"
"accra[89 6 88]"
"achebe[89 2 4]"
...

```

(lower-casing any mixed-case input words for which it finds a match).

If you're more interested in the elements than the numbers per se, for the low low price of 261 253 chars you can use

```
n/{{{32|}%}:L~['']{{`{\+}+'HHeLiBeBCNOFNeNaMgAlPSClArKCaTiVCrMnFeZnGaGeAsSeBrKrRbSrYZrMoTcRuRhPdAgCdTeIXeBaLaCePrNdPmSmEuGdTbDyErTmLuTaWReIrPtAuHgTlAtRnFrRaAcThPaUAmCmEsFmMdLrRfDbSgMtDsRgUutFlLv'[1/{.0=96>{+}*}/]/}%.{L}%2$?.){=p 0}{;{L.,2$<=},.}if}do}%;

```

which gives output like

```
"Ac"
"AcCRa"
"AcHeBe"
...

```

# Answer
> 3 votes
# Ruby - 547 393

New version, thanks for the suggestions:

```
e='HHeLiBeBCNOFNeNaMgAlSiPSClArKaCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo'.scan(/[A-Z][a-z]*/).map &:upcase
r="(#{e.join ?|})"
$<.each{|w|(i=0;i+=1 until w=~/^#{r*i}$/i
$><<w;p$~.to_a[1..-1].map{|m|e.index(m.upcase)+1})if w=~/^#{r}+$/i}

```

---

```
e=%w{h he li be b c n o f ne na mg al si p s cl ar ka ca sc ti v cr mn fe co ni cu zn ga ge as se br kr rb sr y zr nb mo tc ru rh pd ag cd in sn sb te i xe cs ba la ce pr nd pm sm eu gd tb dy ho er tm yb lu hf ta w re os ir pt au hg tl pb bi po at rn fr ra ac th pa u np pu am cm bk cf es fm md no lr rf db sg bh hs mt ds rg cn uut fl uup lv uus uuo}
x = "(#{e.join(?|)})"
regex = /^#{x}+$/i
File.foreach('/usr/share/dict/words'){|w|
if w=~/^#{x}+$/i
puts w
i=1
i+=1 until w=~/^#{x*i}$/i
puts $~[1..-1].map{|m|e.index(m.downcase)+1}.join ?-
end
}

```

uses regexes. slow, and much room for improvement but i must go now :-)

# Answer
> 2 votes
## Python 710 (357 + 261 + 92)

```
e=". h he li be b c n o f ne na mg al si p s cl ar k ca sc ti v cr mn fe co ni cu zn ga ge as se br kr rb sr y zr nb mo tc ru rh pd ag cd in sn sb te i xe cs ba la ce pr nd pm sm eu gd tb dy ho er tm yb lu hf ta w re os ir pt au hg tl pb bi po at rn fr ra ac th pa u np pu am cm bk cf es fm md no lr rf db sg bh hs mt ds rg cn uut fl uup lv uus uuo".split()

i=e.index
def m(w,p=("",[])):
 if not w:return p
 x,y,z=w[0],w[:2],w[:3]
 if x!=y and y in e:
    a=m(w[2:],(p[0]+y,p[1]+[i(y)]))
    if a:return a
 if x in e:
    b=m(w[1:],(p[0]+x,p[1]+[i(x)]))
    if b:return b
 if z in e:
    c=m(w[3:],(p[0]+z,p[1]+[i(z)]))
    if c:return c

f=open('/usr/share/dict/words','r')
for l in f:
 x=m(l[:-1])
 if x:print x[0],x[1]
f.close()

```

There's sure to be room for improvement in there somewhere. It's also worth noting that the second level of indentation uses the tab character.

It takes just over 5 seconds (on my computer) to go through the whole dictionary, producing output like this:

```
acaciin [89, 89, 53, 49]
acacin [89, 89, 49]
acalycal [89, 13, 39, 6, 13]
...

```

By adding another **18** characters, you can get output with the right capitalization:

```
e=". H He Li Be B C N O F Ne Na Mg Al Si P S Cl Ar K Ca Sc Ti V Cr Mn Fe Co Ni Cu Zn Ga Ge As Se Br Kr Rb Sr Y Zr Nb Mo Tc Ru Rh Pd Ag Cd In Sn Sb Te I Xe Cs Ba La Ce Pr Nd Pm Sm Eu Gd Tb Dy Ho Er Tm Yb Lu Hf Ta W Re Os Ir Pt Au Hg Tl Pb Bi Po At Rn Fr Ra Ac Th Pa U Np Pu Am Cm Bk Cf Es Fm Md No Lr Rf Db Sg Bh Hs Mt Ds Rg Cn Uut Fl Uup Lv Uus Uuo".split()

i=e.index
def m(w,p=("",[])):
 if not w:return p
 w=w.capitalize()
 x,y,z=w[0],w[:2],w[:3]
 if x!=y and y in e:
    a=m(w[2:],(p[0]+y,p[1]+[i(y)]))
    if a:return a
 if x in e:
    b=m(w[1:],(p[0]+x,p[1]+[i(x)]))
    if b:return b
 if z in e:
    c=m(w[3:],(p[0]+z,p[1]+[i(z)]))
    if c:return c

OUTPUT:

AcAcIIn [89, 89, 53, 49]
AcAcIn [89, 89, 49]
AcAlYCAl [89, 13, 39, 6, 13]
...

```

You can also check individual words:

```
>>> m("beer")
('beer', [4, 68])

```

# Answer
> 0 votes
## Python - 1328 (975 + 285 chars of code + 68 dictionary code)

```
t1={'c':6,'b':5,'f':9,'i':53,'h':1,'k':19,'o':8,'n':7,'p':15,
's':16,'u':92,'w':74,'v':23,'y':39}
t2={'ru':44,'re':75,'rf':104,'rg':111,'ra':88,'rb':37,
'rn':86,'rh':45,'be':4,'ba':56,'bh':107,'bi':83,
'bk':97,'br':35,'os':76,'ge':32,'gd':64,'ga':31,
'pr':59,'pt':78,'pu':94,'pb':82,'pa':91,'pd':46,
'cd':48,'po':84,'pm':61,'hs':108,'ho':67,'hf':72,
'hg':80,'he':2,'md':101,'mg':12,'mo':42,'mn':25,
'mt':109,'zn':30,'eu':63,'es':99,'er':68,'ni':28,
'no':102,'na':11,'nb':41,'nd':60,'ne':10,'np':93,
'fr':87,'fe':26,'fl':114,'fm':100,'sr':38,'kr':36,
'si':14,'sn':50,'sm':62,'sc':21,'sb':51,'sg':106,
'se':34,'co':27,'cn':112,'cm':96,'cl':17,'ca':20,
'cf':98,'ce':58,'xe':54,'lu':71,'cs':55,'cr':24,
'cu':29,'la':57,'li':3,'lv':116,'tl':81,'tm':69,
'lr':103,'th':90,'ti':22,'te':52,'tb':65,'tc':43,
'ta':73,'yb':70,'db':105,'dy':66,'ds':110,'at':85,
'ac':89,'ag':47,'ir':77,'am':95,'al':13,'as':33,
'ar':18,'au':79,'zr':40,'in':49}
t3={'uut':113,'uuo':118,'uup':115,'uus':117}
def p(s):
 o=0;b=0;a=[];S=str;l=S.lower;h=dict.has_key;L=len
 while o<L(s):
  D=0
  for i in 1,2,3:exec('if h(t%d,l(s[o:o+%d])) and b<%d:a+=[S(t%d[s[o:o+%d]])];o+=%d;b=0;D=1'%(i,i,i,i,i,i))
  if D==0:
   if b==3 or L(a)==0:return
   else:b=L(S(a[-1]));o-=b;a.pop()
 return '-'.join(a)

```

For the dictionary part:

```
f=open(input(),'r')
for i in f.readlines():print p(i[:-1])
f.close()

```

# Answer
> 0 votes
## C, 775 771 chars

```
char*e[]={"h","he","li","be","b","c","n","o","f","ne","na","mg","al","si","p","s","cl","ar","k","ca","sc","ti","v","cr","mn","fe","co","ni","cu","zn","ga","ge","as","se","br","kr","rb","sr","y","zr","nb","mo","tc","ru","rh","pd","ag","cd","in","sn","sb","te","i","xe","cs","ba","la","ce","pr","nd","pm","sm","eu","gd","tb","dy","ho","er","tm","yb","lu","hf","ta","w","re","os","ir","pt","au","hg","tl","pb","bi","po","at","rn","fr","ra","ac","th","pa","u","np","pu","am","cm","bk","cf","es","fm","md","no","lr","rf","db","sg","bh","hs","mt","ds","rg","cn","uut","fl","uup","lv","uus","uu",0};
b[99],n;
c(w,o,l)char*w,*o,**l;{
    return!*w||!strncmp(*l,w,n=strlen(*l))&&c(w+n,o+sprintf(o,",%d",l-e+1),e)||*++l&&c(w,o,l);
}
main(){
    while(gets(b))c(b,b+9,e)&&printf("%s%s\n",b,b+9);
}

```

**Input**: Word per line, must be lowercase. `usr/share/dict/words` is fine.
**Output**: Word and numbers, e.g.: `acceptances,89,58,15,73,7,6,99`

**Logic**:
`c(w,o,l)` checks the word `w`, starting with element `l`.
Two-way recursion is used - if the first element matches the head of the element list, check the remainer of `w` against the full element list. If this match fails, check the word against the tail of the list.
The buffer `o` accumulates the element numbers along the successful path. After a match, it will contain the list of numbers, and is printed.

**Issues**:
The list isn't encoded efficiently - too much `"` and `,`". But this way it's easy to use. I'm sure it can be much improved, without too much cost in code.

---
Tags: code-golf
---