title: Output a number in PrettyFont

text:
# Question
Title: Output a number in PrettyFont
I've designed a new font which I call PrettyFont. I've put much much time into perfecting it, but since I'm a working man I don't have time to finish it. Therefore it only contains 4 characters right now. One day when I've become rich it will become my life-long goal to finish it, but for now...

This is PrettyFont: (0, 1, 2, 3)

```
####  ##  #### ####
#  #   #  #  #    #
#  #   #    #   ###
#  #   #   #      #
####  ### #### ####

```

Each character is 4 pixels wide and 5 pixels high. Now! I want you to write me a program that outputs a number in PrettyFont so I can start sending designs to print.

**Rules:**

The input is a string number in base 4 (only characters 0-3), for example "01321". The program should be able to handle at least 10 characters in the string. BONUS points is given to the program that takes an actual base 10 integer instead of a string. *EDIT* clarification: the integer bonus means that one can enter any base 10 number, like 54321, and the program will convert it to base 4 and output it (in this case 31100301).

The output will be the number printed with PrettyFont. Example input and output:

```
> "321"
####
   #
 ###
   #
####

####
#  #
  #
 #
####

 ##
  #
  #
  #
 ###

```

Huge bonus to the program that can output it in a single row-fashion like this:

```
> "321"
#### ####  ##
   # #  #   #
 ###   #    #
   #  #     #
#### ####  ###

```

The '#' character is not a requirement, and can be replaced by any character.

In vertical output, an empty row is required between each PrettyFont character. If anyone makes the horizontal output, one white space character ' ' or a tab character is required between each PrettyFont character.

This is code golf, shortest code wins! (I need it short because my office computer has limited storage.)

# Answer
# k (~~118 117 72 71 69~~ 66 chars)

~~I haven't made much of an effort to golf this yet~~ but it achieves the desired horizontal output in not too many chars:

```
-1'" "/:'+(5 4#/:4 20#"# "@,/0b\:'0x066609ddd806db00e8e0)"I"$'0:0;

```

Takes input from stdin, prints output to stdout.

edit: By implementing a form of compression on the output "bitmap", I've reduced it to 72. The bitmap is now built by converting 64bit ints to binary and mapping the 0s and 1s to "#" or " ". ~~I could do it from hex like a few of the other solutions but I think this would end up longer~~. Turns out hex is better.

Sample output for 012301:

```
####  ##  #### #### ####  ##
#  #   #  #  #    # #  #   #
#  #   #    #   ### #  #   #
#  #   #   #      # #  #   #
####  ### #### #### ####  ###

```

//edit: -6 char
> 11 votes

# Answer
## Python3 (124)

```
s=input();[print(*["".join(" #"[0xf171ff429f72226f999f>>(20*int(x)+4*y+i)&1]for i in(3,2,1,0))for x in s])for y in range(5)]

```

Sorry, vertical was not interesting for me.

```
???/golf.py
1230012301203012030102301230
 ##  #### #### #### ####  ##  #### #### ####  ##  #### #### #### ####  ##  #### #### #### ####  ##  #### #### #### ####  ##  #### #### ####
  #  #  #    # #  # #  #   #  #  #    # #  #   #  #  # #  #    # #  #   #  #  # #  #    # #  #   #  #  # #  #    # #  #   #  #  #    # #  #
  #    #   ### #  # #  #   #    #   ### #  #   #    #  #  #  ### #  #   #    #  #  #  ### #  #   #  #  #   #   ### #  #   #    #   ### #  #
  #   #      # #  # #  #   #   #      # #  #   #   #   #  #    # #  #   #   #   #  #    # #  #   #  #  #  #      # #  #   #   #      # #  #
 ### #### #### #### ####  ### #### #### ####  ### #### #### #### ####  ### #### #### #### ####  ### #### #### #### ####  ### #### #### ####

```
> 10 votes

# Answer
## J, 84 82 81 80 75 69 characters

```
' #'{~(,4,.(4*".,' ',.1!:1[1)+/i.4){"1#:63231 37521 37415 37441 63487

```

Takes input from the keyboard:

```
   ' #'{~(,4,.(4*".,' ',.1!:1[1)+/i.4){"1#:63231 37521 37415 37441 63487 63487
0123210
 ####  ##  #### #### ####  ##  ####
 #  #   #  #  #    # #  #   #  #  #
 #  #   #    #   ###   #    #  #  #
 #  #   #   #      #  #     #  #  #
 ####  ### #### #### ####  ### ####

```

Magic numbers FTW (or for the second place in this case) :-)
> 10 votes

# Answer
# C - 164 151 characters horizontal

On IDEone: http://ideone.com/gljc3

The code (164 bytes):

```
i,j;main(){char n[99];gets(n);for(;j<5;++j){for(i=0;n[i];++i)printf("%.4s ","#####  # ##   #  ### #     #"+4*("01110233340135006460"[(n[i]-48)*5+j]-48));puts("");}}

```

# EDIT - 151 bytes

I added the suggestions from the comments and then some. It isn't exactly safe (0-length array that I `gets()` in to...) though.

```
char i,j=5,n[];main(){for(gets(n);j--;)for(i=puts("");n[i];printf("%.4s ","#####  # ##   #  ### #     #"+4*(0x1A600BA136E0248>>15*n[i++]-720+3*j&7)));}

```

Note, `i=puts("")` is undefined behavior since I'm treating `void` as `int`! It consistently returns `0` on my version of MinGW, but it returns `1` on the compiler IDEOne uses.

# Accepts decimal, outputs base 4 (167 bytes)

```
char i,j=5,n[];main(p){for(itoa(atoi(gets(n)),n,4);j--;)for(i=puts("");n[i];printf("%.4s ","#####  # ##   #  ### #     #"+4*(0x1A600BA136E0248>>15*n[i++]-720+3*j&7)));}

```
> 8 votes

# Answer
# Ruby, *0123* chars + a bonus (\[0123\] vs '#')

```
f=15
0.upto(4){|n|$*[0].chars{|x|$><<"%4s "%eval(:f6ff929192279241f7ff[x.to_i+4*n]).to_i.to_s(2).tr(?0,' ').tr(?1,x)}
puts}

```

Example:

```
% ruby ./font.rb 01231231
0000  11  2222 3333  11  2222 3333  11
0  0   1  2  2    3   1  2  2    3   1
0  0   1    2   333   1    2   333   1
0  0   1   2      3   1   2      3   1
0000  111 2222 3333  111 2222 3333  111
% ruby ./font.rb 01231231102020103201301203212302230
0000  11  2222 3333  11  2222 3333  11   11  0000 2222 0000 2222 0000  11  0000 3333 2222 0000  11  3333 0000  11  2222 0000 3333 2222  11  2222 3333 0000 2222 2222 3333 0000
0  0   1  2  2    3   1  2  2    3   1    1  0  0 2  2 0  0 2  2 0  0   1  0  0    3 2  2 0  0   1     3 0  0   1  2  2 0  0    3 2  2   1  2  2    3 0  0 2  2 2  2    3 0  0
0  0   1    2   333   1    2   333   1    1  0  0   2  0  0   2  0  0   1  0  0  333   2  0  0   1   333 0  0   1    2  0  0  333   2    1    2   333 0  0   2    2   333 0  0
0  0   1   2      3   1   2      3   1    1  0  0  2   0  0  2   0  0   1  0  0    3  2   0  0   1     3 0  0   1   2   0  0    3  2     1   2      3 0  0  2    2      3 0  0
0000  111 2222 3333  111 2222 3333  111  111 0000 2222 0000 2222 0000  111 0000 3333 2222 0000  111 3333 0000  111 2222 0000 3333 2222  111 2222 3333 0000 2222 2222 3333 0000

```

# EDIT: Ruby, 87 chars

```
0.upto(4){|n|$*[0].bytes{|x|$><<"%04b0"%:f6ff929192279241f7ff[x-48+4*n].to_i(16)}
puts}

```
> 7 votes

# Answer
# Ruby

## Vertical: 116 characters

```
f="f999f62227f924ff171f".chars.map{|c|c.hex.to_s(2).rjust(4).tr"01"," #"}
$<.chars{|c|i=c.to_i*5;$><<f[i,5]*$/+$/*2}

```

Sample run:

```
bash-4.2$ echo -n 321 | ruby -e 'f="f999f62227f924ff171f".chars.map{|c|c.hex.to_s(2).rjust(4).tr"01"," #"};$<.chars{|c|i=c.to_i*5;$><<f[i,5]*$/+$/*2}'
####
   #
 ###
   #
####

####
#  #
  #
 #
####

 ##
  #
  #
  #
 ###

```

## Horizontal: ~~150~~ 148 characters

```
f="f999f62227f924ff171f".chars.map{|c|c.hex.to_s(2).rjust(4).tr"01"," #"}
o=(0..4).map{""}
$<.chars{|c|5.times{|j|o[j]<<f[c.to_i*5+j]+" "}}
$><<o*$/

```

Sample run:

```
bash-4.2$ echo -n 321 | ruby -e 'f="f999f62227f924ff171f".chars.map{|c|c.hex.to_s(2).rjust(4).tr "01"," #"};o=(0..4).map{""};$<.chars{|c|5.times{|j|o[j]<<f[c.to_i*5+j]+" "}};$><<o*$/'
#### ####  ##
   # #  #   #
 ###   #    #
   #  #     #
#### ####  ###

```
> 5 votes

# Answer
# Mathematica 174 145 139 118 119 123 chars

Now works with input in base 10 (Integer bonus). Earlier versions can be found in edits.

---

**Using ArrayPlot**:

With `ArrayPlot` we can directly convert the 1's and 0's to black and white squares, saving a few chars in the process. For example, with n = 58021, which is **32022211** in base 4:

```
i = IntegerDigits; i[n, 4] /. Thread@Rule[0~Range~3, ArrayPlot /@ ((PadLeft[#, 4] & /@ i[#, 2]) & /@ (i@{89998, 62227, 89248, 81718} /. {8 -> 15}))]

```

---

**Explanation**

Input is program parameter, `n`.

Zero can be represented by `{{1,1,1,1},{1,0,0,1},{1,0,0,1},{1,0,0,1},{1,1,1,1}` or by the hex counterpart `f999f`.

The expression, `f999f62227f924ff171f`, holds the information to display all the numbers {0,1,2,3}. (Note: it begins with `f999f`, which as we noted, is zero in disguise.) Because Mathematica does not recognize this as a number, I used `89998622278924881718` (in four integer strings) instead, broke up the number into its integer digits, and then used 15 in every place an 8 appeared. (That allowed me to use digits instead of strings throughout.)
> 4 votes

# Answer
## *Mathematica*, ~~112~~ ~~107~~ 103

My take on David's method.

```
i=IntegerDigits;Grid/@i@n/.Thread[0~Range~3->("#"i[i@#/.8->15,2,4]&/@{89998,62227,89248,81718}/.0->"")]

```

### 105 with the BONUS:

(for `n = 54321`)

```
i=IntegerDigits;Grid/@n~i~4/.Thread[0~Range~3->("#"i[i@#/.8->15,2,4]&/@{89998,62227,89248,81718}/.0->"")]

```
> 3 votes

# Answer
## APL (~~58~~ 57)

```
{' #'[1+5 4⍴1022367 401959 1020495 988959[1+⍎⍵]⊤⍨20⍴2]}¨⍞

```

Output:

```
0123
 ####   ##   ####  ####
 #  #    #   #  #     #
 #  #    #     #    ###
 #  #    #    #       #
 ####   ###  ####  ####

```
> 3 votes

# Answer
# Python 2.7

## Vertical 160

```
for i in input():print['****\n*  *\n*  *\n*  *\n****',' ** \n  * \n  * \n  * \n***','****\n*  *\n  * \n *  \n****','****\n   *\n ***\n   *\n****'][int(i)]+'\n'

```

## Horizontal 234 216

```
x=[['****\n*  *\n*  *\n*  *\n****',' ** \n  * \n  * \n  * \n ***','****\n*  *\n  * \n *  \n****','****\n   *\n ***\n   *\n****'][int(i)]for i in input()]
for i in range(5):print' '.join([y.split('\n')[i]for y in x])

```

Both take input as a quoted string on stdin

example:
$./pretty
"0123"
> 2 votes

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


title: Breakout in half an hour

text:
# Question
Title: Breakout in half an hour
When I was a young teen I had a very boastful friend who claimed he could code up breakout in half an hour. Half an hour later he had done a great job but it didn't quite work. This challenge is to see in 2013 how short it is possible to code this classic game. For the purposes of the competition there need only be one level and no score keeping is needed. The game should be controlled from the keyboard (right and left is all that is needed) but the bricks need to be destroyed correctly and the ball has to bounce in the usual way.

You can choose any programming language you like as well as any free (in both sense) libraries. The code should run in linux.

To inspire you, here is a bare bones and completely ungolfed version of the game in python by Leonel Machava from http://codentronix.com/2011/04/14/game-programming-with-python-and-pygame-making-breakout/ .

```
"""
 bricka (a breakout clone)
 Developed by Leonel Machava <leonelmachava@gmail.com>

 http://codeNtronix.com
"""
import sys
import pygame

SCREEN_SIZE   = 640,480

# Object dimensions
BRICK_WIDTH   = 60
BRICK_HEIGHT  = 15
PADDLE_WIDTH  = 60
PADDLE_HEIGHT = 12
BALL_DIAMETER = 16
BALL_RADIUS   = BALL_DIAMETER / 2

MAX_PADDLE_X = SCREEN_SIZE[0] - PADDLE_WIDTH
MAX_BALL_X   = SCREEN_SIZE[0] - BALL_DIAMETER
MAX_BALL_Y   = SCREEN_SIZE[1] - BALL_DIAMETER

# Paddle Y coordinate
PADDLE_Y = SCREEN_SIZE[1] - PADDLE_HEIGHT - 10

# Color constants
BLACK = (0,0,0)
WHITE = (255,255,255)
BLUE  = (0,0,255)
BRICK_COLOR = (200,200,0)

# State constants
STATE_BALL_IN_PADDLE = 0
STATE_PLAYING = 1
STATE_WON = 2
STATE_GAME_OVER = 3

class Bricka:

    def __init__(self):
        pygame.init()

        self.screen = pygame.display.set_mode(SCREEN_SIZE)
        pygame.display.set_caption("bricka (a breakout clone by codeNtronix.com)")

        self.clock = pygame.time.Clock()

        if pygame.font:
            self.font = pygame.font.Font(None,30)
        else:
            self.font = None

        self.init_game()

    def init_game(self):
        self.lives = 3
        self.score = 0
        self.state = STATE_BALL_IN_PADDLE

        self.paddle   = pygame.Rect(300,PADDLE_Y,PADDLE_WIDTH,PADDLE_HEIGHT)
        self.ball     = pygame.Rect(300,PADDLE_Y - BALL_DIAMETER,BALL_DIAMETER,BALL_DIAMETER)

        self.ball_vel = [5,-5]

        self.create_bricks()

    def create_bricks(self):
        y_ofs = 35
        self.bricks = []
        for i in range(7):
            x_ofs = 35
            for j in range(8):
                self.bricks.append(pygame.Rect(x_ofs,y_ofs,BRICK_WIDTH,BRICK_HEIGHT))
                x_ofs += BRICK_WIDTH + 10
            y_ofs += BRICK_HEIGHT + 5

    def draw_bricks(self):
        for brick in self.bricks:
            pygame.draw.rect(self.screen, BRICK_COLOR, brick)

    def check_input(self):
        keys = pygame.key.get_pressed()

        if keys[pygame.K_LEFT]:
            self.paddle.left -= 5
            if self.paddle.left < 0:
                self.paddle.left = 0

        if keys[pygame.K_RIGHT]:
            self.paddle.left += 5
            if self.paddle.left > MAX_PADDLE_X:
                self.paddle.left = MAX_PADDLE_X

        if keys[pygame.K_SPACE] and self.state == STATE_BALL_IN_PADDLE:
            self.ball_vel = [5,-5]
            self.state = STATE_PLAYING
        elif keys[pygame.K_RETURN] and (self.state == STATE_GAME_OVER or self.state == STATE_WON):
            self.init_game()

    def move_ball(self):
        self.ball.left += self.ball_vel[0]
        self.ball.top  += self.ball_vel[1]

        if self.ball.left <= 0:
            self.ball.left = 0
            self.ball_vel[0] = -self.ball_vel[0]
        elif self.ball.left >= MAX_BALL_X:
            self.ball.left = MAX_BALL_X
            self.ball_vel[0] = -self.ball_vel[0]

        if self.ball.top < 0:
            self.ball.top = 0
            self.ball_vel[1] = -self.ball_vel[1]
        elif self.ball.top >= MAX_BALL_Y:
            self.ball.top = MAX_BALL_Y
            self.ball_vel[1] = -self.ball_vel[1]

    def handle_collisions(self):
        for brick in self.bricks:
            if self.ball.colliderect(brick):
                self.score += 3
                self.ball_vel[1] = -self.ball_vel[1]
                self.bricks.remove(brick)
                break

        if len(self.bricks) == 0:
            self.state = STATE_WON

        if self.ball.colliderect(self.paddle):
            self.ball.top = PADDLE_Y - BALL_DIAMETER
            self.ball_vel[1] = -self.ball_vel[1]
        elif self.ball.top > self.paddle.top:
            self.lives -= 1
            if self.lives > 0:
                self.state = STATE_BALL_IN_PADDLE
            else:
                self.state = STATE_GAME_OVER

    def show_stats(self):
        if self.font:
            font_surface = self.font.render("SCORE: " + str(self.score) + " LIVES: " + str(self.lives), False, WHITE)
            self.screen.blit(font_surface, (205,5))

    def show_message(self,message):
        if self.font:
            size = self.font.size(message)
            font_surface = self.font.render(message,False, WHITE)
            x = (SCREEN_SIZE[0] - size[0]) / 2
            y = (SCREEN_SIZE[1] - size[1]) / 2
            self.screen.blit(font_surface, (x,y))

    def run(self):
        while 1:
            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    sys.exit

            self.clock.tick(50)
            self.screen.fill(BLACK)
            self.check_input()

            if self.state == STATE_PLAYING:
                self.move_ball()
                self.handle_collisions()
            elif self.state == STATE_BALL_IN_PADDLE:
                self.ball.left = self.paddle.left + self.paddle.width / 2
                self.ball.top  = self.paddle.top - self.ball.height
                self.show_message("PRESS SPACE TO LAUNCH THE BALL")
            elif self.state == STATE_GAME_OVER:
                self.show_message("GAME OVER. PRESS ENTER TO PLAY AGAIN")
            elif self.state == STATE_WON:
                self.show_message("YOU WON! PRESS ENTER TO PLAY AGAIN")

            self.draw_bricks()

            # Draw paddle
            pygame.draw.rect(self.screen, BLUE, self.paddle)

            # Draw ball
            pygame.draw.circle(self.screen, WHITE, (self.ball.left + BALL_RADIUS, self.ball.top + BALL_RADIUS), BALL_RADIUS)

            self.show_stats()

            pygame.display.flip()

if __name__ == "__main__":
    Bricka().run()

```

I will accept the answer with the highest number of votes in exactly one week. Extra extra points if anyone can make a version in half an hour :)

**Update** The answer are great but... surely there are more people who want to show off their favourite language to play breakout! Come on **python/perl/Haskell/crazy language** experts :)

**Winners** And the winner is.. Ray. However, extra extra points go to... Schmiddty for completing the task in under 30 minutes! I would still love to see implementations in other languages however.

# Answer
# Python 3 with Pygame and PIL / many hours

After playing other answers, that has simple level config, an idea came to me: The level can be initialized be an image.

So I make this one. To play it, you draw an image that contains many **convex** polygons, like this: image example http://imgbin.org/images/11634.png

The black color will be parsed as walls and the lowest block will be the player. Save it as `break-windows.png` and then run with command:

```
python3 brcki.py break-windows.png

```

Another feature is that the collision detection is very precise. I use binary-search to do it. When two objects collide, time goes back until nothing collide so that the exact collide time and point will be detected. With this tecnique, the ball can go very fast while the bounce effect is still realistic.

Here is `brcki.py`. I know it's a bit too long to be a golf. But isn't that insteresting playing on your own image?

```
import pygame as pg
import itertools
import Image
from random import randint
from math import pi,sin,cos,atan2

norm = lambda c:c/abs(c)
times = lambda c,d:(c*d.conjugate()).real
cross = lambda c,d:(c*d.conjugate()).imag

class Poly:
    def __init__(self, ps, c, color=0):
        assert isinstance(c, complex)
        for p in ps:
            assert isinstance(p, complex)
        self.c = c
        self.ps = ps
        self.boundR = max(abs(p) for p in ps)
        self.ns = [norm(ps[i]-ps[i-1])*1j for i in range(len(ps))]
        self.color = color

class Ball(Poly):
    def __init__(self, r, c, v):
        n = int(1.5*r)
        d = 2*pi/n
        ps = [r * (cos(i*d)+sin(i*d)*1j) for i in range(n)]
        super().__init__(ps, c)
        self.v = v
        self.r = r
        self.color = ColorBall

class Player(Poly):
    def __init__(self, ps, c, color=0):
        super().__init__(ps, c, color)
        self.v = 0+0j

pg.display.init()
W, H = 600, 700
ColorBG = pg.Color(0xffffffff)
ColorBall = pg.Color(0x615ea6ff)
ColorBrick = pg.Color(0x555566ff)
FPS = 40
BallR, BallV = 15, 120+640j
PlayerV = 300

Bc, Bi, Bj = W/2+H*1j, 1+0j, -1j

def phy2scr(p):
    p = Bc + p.real * Bi + p.imag * Bj
    return round(p.real), round(p.imag)

def hittest(dt, b, plr, Ps)->'(dt, P) or None':
    t0, t1, t2 = 0, dt, dt
    moveon(dt, b, plr)
    if not existhit(b, Ps): return None
    while t1 - t0 > 1e-2:
        t3 = (t0 + t1)/2
        moveon(t3 - t2, b, plr)
        if existhit(b, Ps): t1 = t3
        else: t0 = t3
        t2 = t3
    moveon(t1 - t2, b, plr)
    P = next(P for P in Ps if collide(b, P))
    moveon(t0 - t1, b, plr)
    assert not existhit(b, Ps)
    return (t1, P)

def existhit(b, Ps)->'bool':
    return any(collide(b, P) for P in Ps)

def inside(p, P)->'bool':
    return all(times(p-q-P.c, n)>=0 for q,n in zip(P.ps,P.ns))

def collide(P1, P2)->'bool':
    if abs(P1.c - P2.c) > P1.boundR + P2.boundR + 1:
        return False
    return any(inside(P1.c + p, P2) for p in P1.ps) \
            or any(inside(P2.c + p, P1) for p in P2.ps)

def moveon(dt, *ps):
    for p in ps:
        p.c += p.v * dt

def hithandle(b, P):
    hp, n = hitwhere(b, P)
    b.v -= 2 * n * times(b.v, n)

def hitwhere(b, P)->'(hitpoint, norm)':
    c = P.c
    for p in P.ps:
        if abs(b.c - p - c) < b.r + 1e-1:
            return (p+c, norm(b.c - p - c))
    minD = 100
    for p, n in zip(P.ps, P.ns):
        d = abs(times(b.c - p - c, -n) - b.r)
        if d < minD:
            minD, minN = d, n
    n = minN
    return (b.c + n * b.r, -n)

def draw(sur, P):
    pg.draw.polygon(sur, P.color, [phy2scr(p + P.c) for p in P.ps])

def flood_fill(img, bgcolor):
    dat = img.load()
    w, h = img.size
    mark = set()
    blocks = []
    for x0 in range(w):
        for y0 in range(h):
            if (x0, y0) in mark: continue
            color = dat[x0, y0]
            if color == bgcolor: continue
            mark.add((x0, y0))
            stk = [(x0, y0)]
            block = []
            while stk:
                x, y = stk.pop()
                for p1 in ((x-1,y),(x,y-1),(x+1,y), (x,y+1)):
                    x1, y1 = p1
                    if x1 < 0 or x1 >= w or y1 < 0 or y1 >= h: continue
                    if dat[p1] == color and p1 not in mark:
                        mark.add(p1)
                        block.append(p1)
                        stk.append(p1)
            block1 = []
            vis = set(block)
            for x, y in block:
                neig = sum(1 for p1 in ((x-1,y),(x,y-1),(x+1,y), (x,y+1)) if p1 in vis)
                if neig < 4: block1.append((x, y))
            if len(block1) >= 4: blocks.append((dat[x0, y0], block1))
    return blocks

def place_ball(b, plr):
    c = plr.c
    hl, hr = 0+0j, 0+300j
    # assume:
    # when b.c = c + hl, the ball overlaps player
    # when b.c = c + hr, the ball do not overlaps player
    while abs(hr - hl) > 1:
        hm = (hl + hr) / 2
        b.c = c + hm
        if collide(b, plr): hl = hm
        else: hr = hm
    b.c = c + hr

def pixels2convex(pixels):
    """
    convert a list of pixels into a convex polygon using Gramham Scan.
    """
    c = pixels[0]
    for p in pixels:
        if c[1] > p[1]:
            c = p
    ts = [(atan2(p[1]-c[1], p[0]-c[0]), p) for p in pixels]
    ts.sort()
    stk = []
    for x, y in ts:
        while len(stk) >= 2:
            y2, y1 = complex(*stk[-1]), complex(*stk[-2])
            if cross(y1 - y2, complex(*y) - y1) > 0:
                break
            stk.pop()
        stk.append(y)
    if len(stk) < 3: return None
    stk.reverse()
    return stk

def img2data(path) -> "(ball, player, brckis, walls)":
    """
    Extract polygons from the image in path.
    The lowest(with largest y value in image) polygon will be
    the player. All polygon will be converted into convex.
    """
    ColorWall = (0, 0, 0)
    ColorBG = (255, 255, 255)
    print('Start parsing image...')
    img = Image.open(path)
    w, h = img.size

    blocks = flood_fill(img, ColorBG)
    brckis = []
    walls = []
    player = None
    def convert(x, y):
        return x * W / float(w) - W/2 + (H - y * H / float(h))*1j

    for color, block in blocks:
        conv = []
        conv = pixels2convex(block)
        if conv is None: continue
        conv = [convert(x, y) for x, y in conv]
        center = sum(conv) / len(conv)
        p = Poly([c-center for c in conv], center, color)
        if color == ColorWall:
            walls.append(p)
        else:
            brckis.append(p)
            if player is None or player.c.imag > center.imag:
                player = p
    ball = Ball(BallR, player.c, BallV)
    print('Parsed image:\n  {0} polygons,\n  {1} vertices.'.format(
        len(walls) + len(brckis),
        sum(len(P.ps) for P in itertools.chain(brckis, walls))))
    print('Ball: {0} vertices, radius={1}'.format(len(ball.ps), ball.r))
    brckis.remove(player)
    player = Player(player.ps, player.c, player.color)
    place_ball(ball, player)
    return ball, player, brckis, walls

def play(config):
    scr = pg.display.set_mode((W, H), 0, 32)
    quit = False
    tm = pg.time.Clock()
    ball, player, brckis, walls = config
    polys = walls + brckis + [player]
    inputD = None
    while not quit:
        dt = 1. / FPS
        for e in pg.event.get():
            if e.type == pg.KEYDOWN:
                inputD = {pg.K_LEFT:-1, pg.K_RIGHT:1}.get(e.key, inputD)
            elif e.type == pg.KEYUP:
                inputD = 0
            elif e.type == pg.QUIT:
                quit = True
        if inputD is not None:
            player.v = PlayerV * inputD + 0j

        while dt > 0:
            r = hittest(dt, ball, player, polys)
            if not r: break
            ddt, P = r
            dt -= ddt
            hithandle(ball, P)
            if P in brckis:
                polys.remove(P)
                brckis.remove(P)
        if ball.c.imag < 0: print('game over');quit = True
        if not brckis: print('you win');quit = True
        scr.fill(ColorBG)
        for p in itertools.chain(walls, brckis, [player, ball]):
            draw(scr, p)
        pg.display.flip()
        tm.tick(FPS)

if __name__ == '__main__':
    import sys
    play(img2data(sys.argv[1]))

```
> 8 votes

# Answer
# Javascript/KineticJS

Here's a "working" version in 28 minutes, but it's not exactly playable (the collision logic is too slow). http://jsfiddle.net/ukva5/5/

```
(function (con, wid, hei, brk) {
    var stage = new Kinetic.Stage({
        container: con,
        width: wid,
        height: hei
    }),
        bricks = new Kinetic.Layer(),
        brks = brk.bricks,
        bX = wid / 2 - brk.width * brks[0].length / 2,
        bY = brk.height,
        mov = new Kinetic.Layer(),
        ball = new Kinetic.Circle({
            x: wid / 4,
            y: hei / 2,
            radius: 10,
            fill: 'black'
        }),
        paddle = new Kinetic.Rect({
            x:wid/2-30,
            y:hei*9/10,
            width:60,
            height:10,
            fill:'black'
        }),
        left = false,
        right = false;

    mov.add(ball);
    mov.add(paddle);
    stage.add(mov);

    paddle.velocity = 5;

    ball.angle = Math.PI/4;
    ball.velocity = 3;
    ball.bottom = function(){
        var x = ball.getX();
        var y = ball.getY();
        return {x:x, y:y+ball.getRadius()};
    };
    ball.top = function(){
        var x = ball.getX();
        var y = ball.getY();
        return {x:x, y:y-ball.getRadius()};
    };
    ball.left = function(){
        var x = ball.getX();
        var y = ball.getY();
        return {x:x-ball.getRadius(), y:y};
    };
    ball.right = function(){
        var x = ball.getX();
        var y = ball.getY();
        return {x:x+ball.getRadius(), y:y};
    };
    ball.update = function(){
        ball.setX(ball.getX() + Math.cos(ball.angle)*ball.velocity);
        ball.setY(ball.getY() + Math.sin(ball.angle)*ball.velocity);
    };
    paddle.update = function(){
        var x = paddle.getX();
        if (left) x-=paddle.velocity;
        if (right) x+= paddle.velocity;

        paddle.setX(x);
    };

    for (var i = 0; i < brks.length; i++) {
        for (var j = 0; j < brks[i].length; j++) {
            if (brks[i][j]) {
                bricks.add(new Kinetic.Rect({
                    x: bX + j * brk.width + .5,
                    y: bY + i * brk.height + .5,
                    width: brk.width,
                    height: brk.height,
                    stroke: 'black',
                    strokeWidth: 1,
                    fill: 'gold'
                }));
            }
        }
    }
    stage.add(bricks);

    $(window).keydown(function(e){
        switch(e.keyCode){
            case 37:
                left = true;
                break;
            case 39:
                right = true;
                break;
        }
    }).keyup(function(e){
        switch(e.keyCode){
            case 37:
                left = false;
                break;
            case 39:
                right = false;
                break;
        }
    });

    (function loop(){
        ball.update();
        paddle.update();

        if (paddle.intersects(ball.bottom())){
            ball.setY(paddle.getY()-ball.getRadius());
            ball.angle = -ball.angle;
        }
        if (ball.right().x > wid){
            ball.setX(wid - ball.getRadius());
            ball.angle = Math.PI - ball.angle;
        }
        if (ball.left().x < 0){
            ball.setX(ball.getRadius());
            ball.angle = Math.PI - ball.angle;
        }
        if (ball.top().y < 0){
            ball.setY(ball.getRadius());
            ball.angle = -ball.angle;
        }

        for(var i = bricks.children.length; i--;){
            var b = bricks.children[i];
            if (b.intersects(ball.top()) || b.intersects(ball.bottom())){
                ball.angle = -ball.angle;
                b.destroy();
            }
            else if (b.intersects(ball.left()) || b.intersects(ball.right())){
                ball.angle = Math.PI-ball.angle;
                b.destroy();
            }
        }

        stage.draw();

        webkitRequestAnimationFrame(loop);
    })()

})('b', 640, 480, {
    width: 80,
    height: 20,
    bricks: [
        [1, 1, 1, 1, 1, 1],
        [1, 1, 0, 0, 1, 1],
        [1, 1, 1, 1, 1, 1]
    ]
});

```

I'll work on making the game snappier now. :)

**Note:** Works only in webkit browsers right now. I'll add a shim so it will work in any HTML5 ready browser eventually.

**Updates:**

1. http://jsfiddle.net/ukva5/6/ more playable
2. http://jsfiddle.net/ukva5/7/ random bricks, faster ball
3. http://jsfiddle.net/ukva5/8/ random brick health
4. http://jsfiddle.net/ukva5/12/show/light/ stopping point for the day.
> 4 votes

# Answer
# Processing, 400 characters

Didn't manage to do it in 30min, but here's a surf'd version. The ball is square and if you press any other key than left/right it jumps fully right, but it was shorter and the spec didn't say anything against it ;).

```
int x,y=999,u,v,p=300,q=580,i,l,t;long g;void setup(){size(720,600);}void draw(){background(0);if(keyPressed)p=min(max(p+8*(keyCode&2)-8,0),630);rect(p,q,90,20);for(i=0;i<64;i++)if((g>>i&1)<1){l=i%8*90;t=i/8*20+40;if(x+20>l&&x<l+90&&y+20>t&&y<t+20){v=-v;g|=1l<<i;}rect(l,t,90,20);}if(x+20>p&&x<p+90&&y+20>q)v=-abs(v);if(y<0)v=-v;if(x<0||x>700)u=-u;if(y>600){x=y=400;u=v=3;}x+=u;y+=v;rect(x,y,20,20);}

```

With proper names & some whitespace for clarity, that's:

```
int ballX, ballY=999, speedX, speedY, paddleX=300, paddleY=580;
long bricks;

void setup() {
  size(720, 600);
}

void draw() {
  background(0);
  if(keyPressed) paddleX = min(max(paddleX+8*(keyCode^37)-8,0),630);
  rect(paddleX, paddleY, 90, 20);
  for(int i=0; i<64; i++) {
    if((bricks>>i&1)<1) {
      int brickX=i%8*90, brickY=i/8*20+40;
      if(ballX+20>brickX && ballX<brickX+90 && ballY+20>brickY && ballY<brickY+20) {
        speedY = -speedY;
        bricks |= 1l<<i;
      }
      rect(brickX, brickY, 90, 20);
    }
  }
  if(ballX+20>paddleX && ballX<paddleX+90 && ballY+20>paddleY) speedY = -abs(speedY);
  if(ballY<0) speedY = -speedY;
  if(ballX<0 || ballX>700) speedX = -speedX;
  if(ballY>600) {
    ballX = ballY = 400;
    speedX = speedY = 3;
  }
  ballX += speedX; ballY += speedY;
  rect(ballX, ballY, 20, 20);
}

```
> 3 votes

# Answer
## Elm, 1 hour 44 minutes

I tried to do it in half an hour, but overshot a little. To try to save time, I used circles for everything (paddle, ball, bricks). This avoided the many cases needed to implement circle/rectangle collision, but required some vector math to compute the resulting direction.

To run, go to http://elm-lang.org/edit/, paste the code into the editor, and click the "In Tab" button at the bottom.

```
import Keyboard

brickR = 30
ballR = 10
paddleY = 450
paddleR = 50

-- Initial (center) position of each brick
brickLayout = [(150,50), (250, 50), (350, 50), (450, 50),
            (100,100), (200,100), (300,100), (400,100), (500,100)]

brickForm = filled blue . circle brickR

-- Return True if the brick coordinate collides with the ball coordinate
brickVsBall brickPos ballPos =
    distance brickPos ballPos <= brickR + ballR

addVec (ax,ay) (bx,by) = (ax+bx, ay+by)
subVec (ax,ay) (bx,by) = (ax-bx, ay-by)
dot (ax,ay) (bx,by) = ax*bx + ay*by
magsq (x,y) = x*x + y*y
scaleVec s (x,y) = (x*s, y*s)
proj n v = scaleVec (dot v n / magsq n) n
flipV n v = v `subVec` scaleVec 2 (proj n v)
distance a b = sqrt $ magsq $ a `subVec` b

-- Only flip the velocity if headed "toward" the target, where n is a vector
-- pointing from the ball to the target.
bounceV n v =
    if v `dot` n > 0
       then v `subVec` scaleVec 2 (proj n v)
       else v

checkBricks ballPos ballV bricks =
    let (smashed, kept) = updateBricks ballPos [] [] bricks
     in (updateBallV ballPos ballV smashed, kept)

updateBricks ballPos smashed kept bricks = case bricks of
    [] -> (reverse smashed, reverse kept)
    (x:xs) ->
        if brickVsBall x ballPos
           then updateBricks ballPos (x:smashed) kept xs
           else updateBricks ballPos smashed (x:kept) xs

updateBallV ballPos ballV smashed = case smashed of
    []     -> ballV
    (x:xs) -> updateBallV ballPos (bounceV (x `subVec` ballPos) ballV) xs

checkPaddle paddleX ballPos ballV =
    let paddlePos = (paddleX,paddleY) in
    if distance ballPos paddlePos <= ballR + paddleR
       then bounceV (paddlePos `subVec` ballPos) ballV
       else ballV

checkWalls r (x,y) =
    let checkLeft  (vx,vy) = if x-r <= 0   && vx<0 then (0-vx,vy) else (vx,vy)
        checkRight (vx,vy) = if x+r >= 600 && vx>0 then (0-vx,vy) else (vx,vy)
        checkTop   (vx,vy) = if y-r <= 0   && vy<0 then (vx,0-vy) else (vx,vy)
     in checkLeft . checkRight . checkTop

-- type Scene = ([BrickPos], BallPos, BallV, PaddleX)
-- BallV is in pixels per frame

initScene = (brickLayout, (300,385), (0, 0-3), 300)

renderScene (bricks, ballPos, ballV, paddleX) =
    collage 600 500 $
    map brickForm bricks ++
    [ filled red $ circle ballR ballPos
    , filled black $ circle paddleR (paddleX,paddleY)
    ]

updateScene (bricks, ballPos, ballV, paddleX) arrows =
    let paddleX' = paddleX + arrows.x * 4
        (ballV1, bricks') = checkBricks ballPos ballV bricks
        ballV2 = checkPaddle paddleX' ballPos ballV1
        ballV' = checkWalls ballR ballPos ballV2
     in (bricks', ballPos `addVec` ballV', ballV', paddleX')

main =
    lift renderScene $
    foldp (\(t, arrows) scene -> updateScene scene arrows) initScene $
    lift2 (,) (every (second/60)) arrows

```
> 1 votes

---
Tags: popularity-contest, graphical-output
---


title: Print ASCII histogram

text:
# Question
Title: Print ASCII histogram
The challenge is to give as short code as possible to print an ASCII histogram of a set of data.

**Input.** The number of bins followed by a number of integers representing the data. The data are space separated.

**Output.** An ASCII histogram of the data using the specified number of bins.

**Score.** Number of characters in the code excluding trailing whitespace at the beginning or end of each line.

Example input.

```
2    2    3    4    2    2    5

```

Example output.

```
*
*
**
**

```

**Update.** The answers are all great although I can only ever imagine using the one in **R**. No python contribution?

# Answer
## APL ~~66~~ 51

```
' *'[1+(⌽⍳b)∘.≤v←+/(⍳b)∘.=⌈x[⍋x]÷(⌈/x←1↓v)÷b←↑v←⍎⍞]

```

Using the example I quoted in my comment on the question where the bin size is 2.25:

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

*
*
* **
****

```
> 6 votes

# Answer
### GolfScript, 57 55 52 characters

```
~](\$:?;:b,{{\?0=-b*?)\0=-)/=" *"=}+?%$}%zip{32-},n*

```

Taking input as single line from STDIN. Script can be tested online.

Example:

```
> 4 1 1 2 2 5 8 6 3
*
*
* *
****

```
> 3 votes

# Answer
## J, ~~96~~ 86

```
(' *'{~|.@|:@(>/i.@(>./))@(}:@}:,{:@}:+{:)@(+/@(=/i.@>:@{.)~<.@({.*(%>./)@(-<./)@}.)))

```

In a little more readable format: http://pastebin.com/2CiaJXjC.

```
   (...) 2 2 3 4 2 2 5
*
*
**
**
   (...) 4 1 1 2 2 5 8 6 3
*
*
* *
****

```

Step by step on example values: http://pastebin.com/nXjGcq8L.
> 2 votes

# Answer
## R - ~~133~~ 122 characters

```
a=scan()
b=table(cut(a[-1],a[1]))
invisible(apply(cbind(sapply(b,function(x)c(rep(" ",max(b)-x),rep("*",x))),"\n"),1,cat))

```

When sourced, it prompts the user for input (because of `scan`), and output the ascii histogram.

```
> source('asciihist.R')
1: 2 2 3 4 5 2 2 5
9:
Read 8 items
*
* *
* *
* *

> source('asciihist.R')
1: 4 1 1 2 2 5 8 6 3
10:
Read 9 items
*
*
*   *
* * * *

```
> 1 votes

---
Tags: code-golf
---


# Question
Title: Multiples of 67 in a constructed array of arrays?
A triangle-shaped table is constructed such the first row is "1, 3, 5, 7, ..., 99"

Each subsequent row has the following properties:

* One less element than the row above
* Each element is the sum of the two elements above it

Like so:

```
1   3   5    7    9    11 ....
  4   8   12   16   20 ....
    ...............

```

This continues until the last row with one element.

How many elements are divisible by 67?

Fewest lines, chars, or whatever may win. Depends on ingenuity.

EDIT: the answer is 17 but you have to prove it.

ADDENDUM: I have three-line python code for this but try to beat it:

```
a = [[2*i+1 for i in range(50)]]
while len(a[-1])>1:a.append([a[-1][i]+a[-1][i+1] for i in range(len(a[-1])-1)])
print len([i for b in a for i in b if i%67==0])

```

# Answer
> 7 votes
## JavaScript: 91, 88 (thanks trinithis), 84, 77 (thanks again trinithis), 75 (thanks shesek), 74 Characters (thanks Shmiddty)

**91--\>88** \- See Trinithis's comment
**88--\>84** \- moved `j--` into conditional check.
**84--\>77** \- See trinithis's comment (removed `{}` from for loops, ignored first index of `a` array) plus some additional work (fixed logic for building arrays and incrementing counters)
**77--\>75** \- See Shesek's comment (instead of `(condition)&&val++`: `val+=(condition)`)
**75--\>74** \- See Shmiddty's comment (instead of `i=c=1,a=[]`: `a=[i=c=1]`)

Golfed:

```
for(a=[i=c=1];i<51;)for(a[i]=i*2-1,j=i++;j>1;)c+=1>(a[--j]=a[1+j]+a[j])%67

```

Ungolfed:

```
/**
 * i - counter for array index and array initialization
 * c - count of elements divisible by 67
 * a - array of numbers in diagonal bottom-to-right row.
 *        For example, here are the first 3 iterations:  [1], [4,3], [12,8,5]
 * j - index into array a
 */
for(a=[i=c=1];i<51;){
    a[i]=i*2-1;
    for(j=i++;j>1;){
        c+=1>(a[--j]=a[1+j]+a[j])%67
    }
}

```

Here's a fiddle for both as well as a test that outputs what is in the arrays for the first 3 iterations.

Note: I initialize the count to 1 because the first row \[1,3,5..67..97,99\] has one number divisible by 67. That way, I did not have to worry about checking the first row.

# Answer
> 7 votes
## Haskell - 86 chars

**98 → 92**: Use list comprehensions and `sum` instead of `filter` and `length`.

**92 → 86**: Convert nested list comprehensions into one, and change `==0` to `<1` (thanks st0le).

```
f s=zipWith(+)s$tail s
main=print$sum[1|r<-take 50$iterate f[1,3..99],n<-r,n`mod`67<1]

```

Ungolfed:

```
initialRow :: [Integer]
initialRow = [1,3..99]

nextRow :: (Num a) => [a] -> [a]
nextRow xs = zipWith (+) xs (tail xs)

triangle :: [[Integer]]
triangle = takeWhile (not . null) $ iterate nextRow initialRow

main = print $ length $ filter ((== 0) . (`mod` 67)) $ concat triangle

```

# Answer
> 5 votes
## Mathematica 82 chars

```
Count[Mod[#,67]==0&/@Flatten@NestList[2MovingAverage[#,2]&,Range[1,99,2],49],True]

-> 17

```

# Answer
> 4 votes
## Python 95 bytes

```
l,c=range(1,100,2),0
while l:c+=len([i for i in l if i%67<1]);l=map(sum,zip(l,l[1:]))
print c

```

# Answer
> 3 votes
# J, 48

```
1225-~+/,-.*67|((<:/|.)a)*(+1&|.)^:a>:2*a=:i.50x

```

Explanation (bits of it, anyway):

* a is 0 .. 49
* `>:2*a` is `1 3 5 ...`
* The verb `(+1&|.)` shifts a row and adds it to the original to get the desired next row (plus extras, since the result is still 50 elements).
* `(+1&|.)^:a>:2*a` gives 50 rows of results. Row one is `1 3 5` etc, row 2 is `4 8 12` etc.
* `((<:/|.)a)` is a 50x50 matrix of 1 1 ... 1 1, 1 1 ... 1 0 etc. down to 1 0 ... 0 0. This zeroes out the 1225 extras. (1225 is the 49th triangular number.)
* After taking mod 67 and counting, we subtract those 1225 zeroes that we know will be present.

# Answer
> 3 votes
## Python

85 bytes - thanks to st0le

```
l,c=range(1,100,2),0
while l:c+=sum(i%67<1for i in l);l=map(sum,zip(l,l[1:]))
print c

```

# Answer
> 1 votes
# C++ 133 131 125 chars, 2 Lines

```
#include<iostream>
__int64 c=1,s=1,r,a=2,e=51,i;int main(){for(;e;c=s+=s+a,a*=2)for(i=e--;--i;c+=a)c%67?0:r++;std::cout<<r;}

```

I'm not sure how portable this is with the use of `__int64`, if it does complains you can change it to `long long`.

## Ungolfed

```
#include<iostream>

__int64 curr,start=1,ret,add=2,end_line=50;
int main(){
    for(;end_line>0;end_line--,add*=2){
        curr=start;
        for(int i=1;i<=end_line;++i){
            if(curr%67){
            }else{
                ret++;
            }
            curr+=add;
        }
        start+=start+add;
    }
    std::cout<<ret;
}

```

# Answer
> 1 votes
## Ruby 113 bytes

```
l,c=(1..100).step(2).to_a,0
[c+=l.count{|i|i%67<1},l=l.zip(l[1..-1]).map{|x,y|x+y if y}.compact!]until[]==l
p c

```

# Answer
> 1 votes
# Q, 53 43

```
sum 0=(raze{1_msum[2]x}\[1+2*(!)50])mod 67

```

.

```
q)sum 0=(raze{1_msum[2]x}\[1+2*(!)50])mod 67
17i

```

Don't have to cast to long in q 3.0 which saved some characters.

# Answer
> 0 votes
### scala, 125 chars:

```
def s(v:Seq[Long]):Seq[Long]=if(v.size==1)v else
v++s(v.sliding(2).map(v=>v(0)+v(1)).toSeq)
s(1L to 99 by 2).count(_%67==0)

```

Since the first row contains the number 67, which is divisible by 67, and the next number, divisible by 67 is 2\*67 is bigger than 99, we know that we start with count = 1.

# Answer
> 0 votes
## Perl (84+1)

there might still be a way to shorten this :)

```
@q=grep$_%2,1..99;while(@q){$_%67or$c++for@q;$q[$_]+=$q[$_+1]for 0..$#q;pop@q}say$c

```

# Answer
> 0 votes
### GolfScript, 39 38 characters

```
100,{2%},0\{.{67%!},,@+\(\{.@+}%\;.}do

```

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


title: Swapping numbers

text:
# Question
Title: Swapping numbers
This is a common puzzle many of you have solved manually. Now this is the time to write an algorithm to solve the same.

There are equal number match sticks lined up in two different side facing each other's direction. There is a single empty space between them. Say something like the following figure (if total number of match sticks are 4).

Each stick can either slide one step in forward direction (if the immediate front space is free), or it can be jumped over one stick in their front, and land into the free space (if that space is free). The move in reverse direction is not possible (even the space is free). No reverse jump is also allowed. Only one move is allowed in one step.

Now, you have to write an algorithm to find the minimum steps required using which all the left hand side match sticks will land in right hand side and all the right hand side match sticks will land in left hand side.

For ex: If there are total 2 match sticks (1 in each side) then steps will be:

Note: In the above figure the left side stick been moved first. Another solution exists when the right side stick moves first. But for this problem, you have to give only one solution and that is also assuming that the left side stick moves first.

The following figure describes the moves with 4 match sticks (2 in each side):

Note: In the above figure the left side stick been moved first. Another solution exists when the right side stick moves first. But for this problem, you have to give only one solution and that is also assuming that the left side stick moves first.

\[Assumption: The input can be any even number between 02 to 14 (i.e. 1 to 7 match sticks in each side). For inputs outside this range, you do not need to do any validation, neither need to provide any error message. Note: In the output, each step is separated by a '|' (pipe) character. COBOL programmers should always assume PIC 9(2) as input size & may also assume the output to be fixed maximum length 450 characters, padded with spaces at right.\]

---

Sample Input:
```
02

```

Sample Output:

```
01To02|03To01|02To03|

```

---

Sample Input:
```
04

```

Sample Output:

```
02To03|04To02|05To04|03To05|01To03|02To01|04To02|03To04|

```

---

Sample Input:
```
06

```

Sample Output:

```
03To04|05To03|06To05|04To06|02To04|01To02|03To01|05To03|07To05|06To07|04To06|02To04|03To02|05To03|04To05|

```

# Answer
## APL 129

The code below takes screen input and outputs to the screen in the format specified:

```
n←n,n++\1↓z←(⌽z),((¯1*~2|n)×n⍴2),z←⌽∊(¯1*2|⍳n)×¨1,((⍳(n←.5×⍎⍞)-1)⍴¨2),¨1⋄(∊(((¯2↑¨'0',¨⍕¨n),¨⊂'To'),¨(¯2↑¨'0',¨⍕¨n-z)),¨⊂'|')~' '

```

A good third of the code is taken up formatting the output. The logic is complete by the occurrence of the ⋄ symbol in the code.

Below is the result for an input of 08 as a check:

```
04To05|06To04|07To06|05To07|03To05|02To03|04To02|06To04|08To06|09To08|07To09|05To07|03To05|01To03|02To01|04To02|06To04|08To06|07To08|05To07|03To05|04To03|06To04|05To06|

```
> 3 votes

# Answer
## Javascript 178 174 161

`prompt`s for `n` then `alert`s answer. (No `0` padding)

**Latest:**

```
t=1+(m=prompt(s=i='')/2);for(z=Math.abs;i++<m*2;)for(j=m-z(m-i),s+=(t+=a=(m%2^z(m+.5-i)%2-.5)*-2+1)+'To'+(t-a)+'|';j--;)s+=(t+=a=i%2*4-2)+'To'+(t-a)+'|';alert(s)

```

**2:**

```
z=Math.abs;t=m=prompt(o=[])/2;t++;for(s=i='';i++<m*2;)for(j=m-z(m-i),o.push((z(m+.5-i)%2-.5)?-1:1);j--;)o.push(i%2?2:-2);o.map(function(a){s+=(t+=a)+'To'+(t-a)+'|'});alert(s)

```

**1:**

```
t=m=prompt(o=[])/2+1;for(s=i='';++i<m;)for(j=i,o.push(i%2?-1:1);j--;)o.push(i%2?2:-2);o.concat(o.slice().reverse().slice(m-1)).map(function(a){s+=(t+=a)+'To'+(t-a)+'|'});alert(s)

```

This uses the concept that the pattern is mirrored:

```
Key
R='Jump Right'
r='Shift Right'
L='Jump Left'
l='Shift Left'
m='Move'
j='Jump'

```

So, where `n=2`, the pattern of movement is:

```
rLr
mjm

```

Which equates to

```
+1 -2 +1

```

This pattern repeats like so (`n=8`)

```
rLlRRrLLLlRRRRlLLLrRRlLr
mjmjjmjjjmjjjjmjjjmjjmjm
+1 -2 -1 +2 +2 +1 -2 -2 -2 -1 +2 +2 +2 +2 -1 -2 -2 -2 +1 +2 +2 -1 -2 +1

```

We can notice a few patterns here:

1. Movement alternates between left and right
2. The number of movements in a particular direction increases from 1 to `n/2`, which repeats 3 times, then decreases back to 1.
3. The type of movement alternates between shifting and jumping, the number of shifts in a row being a constant `1`, and the number of sequential jumps increasing from 1 to `n/2` then decreasing back to 1.
4. The summation of the movements is always 0. (Not sure if this is actually relevant)

`n=14`:

```
rLlRRrLLLlRRRRrLLLLLlRRRRRRrLLLLLLLrRRRRRRlLLLLLrRRRRlLLLrRRlLr
mjmjjmjjjmjjjjmjjjjjmjjjjjjmjjjjjjjmjjjjjjmjjjjjmjjjjmjjjmjjmjm

```

Sample output:

`f(2)`:

```
1To2|3To1|2To3|

```

`f(8)`:

```
4To5|6To4|7To6|5To7|3To5|2To3|4To2|6To4|8To6|9To8|7To9|5To7|3To5|1To3|2To1|4To2|6To4|8To6|7To8|5To7|3To5|4To3|6To4|5To6|

```

`f(40)`:

```
20To21|22To20|23To22|21To23|19To21|18To19|20To18|22To20|24To22|25To24|23To25|21To23|19To21|17To19|16To17|18To16|20To18|22To20|24To22|26To24|27To26|25To27|23To25|21To23|19To21|17To19|15To17|14To15|16To14|18To16|20To18|22To20|24To22|26To24|28To26|29To28|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|12To13|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|31To30|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|10To11|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|33To32|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|8To9|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|35To34|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|6To7|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|37To36|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|4To5|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|39To38|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|2To3|4To2|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|40To38|41To40|39To41|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|1To3|2To1|4To2|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|40To38|39To40|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|4To3|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|37To38|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|6To5|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|35To36|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|8To7|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|33To34|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|10To9|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|31To32|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|12To11|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|29To30|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|14To13|16To14|18To16|20To18|22To20|24To22|26To24|28To26|27To28|25To27|23To25|21To23|19To21|17To19|15To17|16To15|18To16|20To18|22To20|24To22|26To24|25To26|23To25|21To23|19To21|17To19|18To17|20To18|22To20|24To22|23To24|21To23|19To21|20To19|22To20|21To22|

```

Here's some pseudo code to demonstrate the method:

```
var mid=cursor=N/2,delta
cursor++                 // the cursor is where the empty space is.
for(i=0; i++<N;){
  delta = (mid%2^abs(mid+.5-i)%2-.5)*-2+1;  // 1 or -1
  print((cursor+delta) + 'To' + cursor + '|')
  cursor+=delta
  for(j=mid-abs(mid-i);j--;)
  {
    delta = i%2*4-2  // 2 or -2
    print((cursor+delta) + 'To' + cursor + '|')
    cursor+=delta
  }
}

```
> 3 votes

# Answer
# C - 216 213

My solution is based on two facts:

1. The "to" field is the "from" field of the previous move (since you always create an empty slot in the space you move from, and ou always move to an empty slot)
2. There is a very regular pattern to the distances and directions that are moved. For the first 3 test cases, they are:

`1 -2 1`

`1 -2 -1 2 2 -1 -2 1`

`1 -2 -1 2 2 1 -2 -2 -2 1 2 2 -1 -2 1`

With that in mind I basically just wrote a program to produce and continue that pattern. I'm pretty sure there must be a really beautiful and much more elegant recursive way to write this, but I haven't figured it out yet:

```
#include <stdio.h>

int main(int argc, const char *argv[])
{
   int upper_bound = atoi(argv[1]) / 2;
   int len;
   int from;
   int to = upper_bound + 1;
   int direction = 1;
   int i;

   for(len = 1; len <= upper_bound; ++len){
      for(i = len-1; i >=0; --i){
         from = to - direction*(1 + (i!=0));
         printf("%02dTo%02d|",from,to);
         to = from;
      }
      direction*=-1;
   }
   for(i=1; i < len; ++i){
      from = to - direction*2;
      printf("%02dTo%02d|",from,to);
      to = from;
   }
   direction*=-1;
   for(--len; len >= 0; --len){
      for(i = 0; i < len; ++i){
         from = to - direction*(1 + (i!=0));
         printf("%02dTo%02d|",from,to);
         to = from;
      }
      direction*=-1;
   }
   return 0;
}

```

And golfed (even though this was a code-challenge, not golf):

```
#define B {F=T-D*(1+(i!=0));printf("%02dTo%02d|",F,T);T=F;}D*=-1;
L,F,T,D,i;main(int U,char**A){U=atoi(A[1])/2;T=U+1;D=1;for(L=1;L<=U;++L){for(i=L-1;i>=0;--i)B}for(i=1;i<L;++i)B for(--L;L>=0;--L){for(i=0;i<L;++i)B}}

```

```
#define B {F=T-D*(1+(i!=0));printf("%02dTo%02d|",F,T);T=F;}D*=-1;
L,F,T,D,i;main(int U){scanf("%d",&U);U/=2;T=U+1;D=1;for(L=1;L<=U;++L){for(i=L-1;i>=0;--i)B}for(i=1;i<L;++i)B for(--L;L>=0;--L){for(i=0;i<L;++i)B}}

```
> 2 votes

# Answer
# Mathematica

This approach builds a `Nest`ed sequence of the size and direction of the moves, formatted as `{fromPosition,toPosition}`, beginning with position `n`, where `n` refers to the number of match pairs. It then `Fold`s the sequence into a function that begins with move `{n, n+1}`.

```
z@n_:=(p=1;h@t_:=Append[{Table[2 (-1)^t,{t}]},{(-1)^(t+1)}];
k=Join[Reverse@Drop[#,n],#]&[Flatten@Nest[Prepend[#,h[p++]]&,{},n]];
Fold[Append[#,{#[[-1,1]]-#2,#[[-1,1]]}]&,{{n,n+k[[1]]}},Rest@k])

```

---

```
z[1]

```

> {{1, 2}, {3, 1}, {2, 3}}

---

```
z[4]

```

> {{4, 5}, {6, 4}, {7, 6}, {5, 7}, {3, 5}, {2, 3}, {4, 2}, {6, 4}, {8, 6}, {9, 8}, {7, 9}, {5, 7}, {3, 5}, {1, 3}, {2, 1}, {4, 2}, {6, 4}, {8, 6}, {7, 8}, {5, 7}, {3, 5}, {4, 3}, {6, 4}, {5, 6}}

---

```
z[7]

```

> {{7, 8}, {9, 7}, {10, 9}, {8, 10}, {6, 8}, {5, 6}, {7, 5}, {9, 7}, {11, 9}, {12, 11}, {10,12}, {8, 10}, {6, 8}, {4, 6}, {3, 4}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, {13, 11}, {14, 13}, {12, 14}, {10, 12}, {8, 10}, {6, 8}, {4, 6}, {2, 4}, {1, 2}, {3, 1}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, {13, 11}, {15, 13}, {14, 15}, {12, 14}, {10, 12}, {8, 10}, {6, 8}, {4, 6}, {2, 4}, {3, 2}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, {13, 11}, {12, 13}, {10, 12}, {8, 10}, {6, 8}, {4, 6}, {5, 4}, {7, 5}, {9, 7}, {11, 9}, {10, 11}, {8, 10}, {6, 8}, {7, 6}, {9, 7}, {8, 9}}

---

**Visualizing the Swaps**

`r`, `b`, and `o` are images or a red match, a blue match, and no match, respectively.

The following formats the output from `z` to display the swaps with matches.

```
swaps[n_]:=FoldList[Grid[{Permute[#[[1,1]],Cycles[{#2}]],Range[2n+1]}]&,
Grid[{Join[Table[r,{n}],{o},Table[b,{n}]],Range[2n+1]}],z[n]]

swapMatches[n_]:=Grid[Partition[swaps[n],2,2,1,""],Dividers->All]

```

`swaps` produces a list of states by using the ordered pairs of `z` as commands to permute the initial list and subsequent lists.

```
swaps[1]

```

`swapMatches` displays the states in a grid.

```
swapMatches[2]

```

```
swapMatches[3]

```
> 2 votes

# Answer
## Javascript 191

```
function f(N) {
    n=N>>=i=c=a='1';n++
    s=z='0'
    for(k=b='34';i<N;k=i%2?a+=z+z:b+='44',i++)c=k+c
    t=''
    i=N*(N+1)/2
    l=2*i+N
    for(;l;n+=(i>=1?r=c[i-1]:i<=-N?c[-i-N]:k[1])-2,t+=(s=n>9?'':z)+n+a+'|',--l,--i)a='To'+s+n
    return t
}

```

Characters counted using `grep =|tr -d \ |wc -c`
> 0 votes

---
Tags: code-challenge
---


title: Bridges (Hashi)

text:
# Question
Title: Bridges (Hashi)
Unsolved puzzle:

Solved Puzzle:

### Rules

* Each circle with number must have as many lines from it as the number in the circle.
* It is not allowed to have more than two lines between two circles.
* The lines can not cross each other.
* All the lines must either be horizontal or vertical. It is not allowed to draw lines diagonally.
* All lines must be connected.

### Program Description

Write a program to input a bridges puzzle from a text file and output the solution

### Input file guidelines

The input file must display a number for the number of bridges connected and `.` for whitespace.

Example:

```
2.2.5.2.
.....1.3
6.3.....
.2..6.1.
3.1..2.6
.2......
1.3.5..3
.2.3..2.

```

### Output guidelines

Replace periods with

* `-` single horizontal line
* `=` double horizontal line
* `|` single vertical line
* `$` double vertical line

From the data file above, you should get this as output:

```
2 2-5=2
$ | $1-3
6=3 $  $
$2--6-1$
3|1 $2=6
|2| $  $
1|3=5--3
 2-3==2

```

# Answer
> 2 votes
### Ruby, 414 characters

```
h=->l,s,v{l[s.index(v)||s.size]}
c=->r,f{r[f].to_i-h[[1,2,0],'|$',r[f-N]]-h[[1,2,0],'-=',r[f-1]]-h[[1,2,0],'-=',r[f+1]]}
s=->r{(f=r=~/\./)&&(m=h[[2,4,25,25,25,31],w='|$-= ',a=r[f-N]]&h[[7,7,8,16,7,31],w,r[f-1]]
a=~/\d/&&m&=(0>d=c[r,f-N])?0:d<1?25:d<2?2:d<3?4:0
' |$-='.chars{|k|m&1>0&&(r[f]=k;s[r]);m=m>>1};r[f]='.')||r[-N..-1]=~/^ +$/&&$><<r[N..-N].tr("0",$/)}
N=1+((t=STDIN.read)=~/$/)
s[$/*N+t.tr($/,"0")+"."*N]

```

Example:

```
2.2.5.2.
.....1.3
6.3.....
.2..6.1.
3.1..2.6
.2......
1.3.5..3
.2.3..2.

2 2-5=2
$ | $1-3
6=3 $  $
$2--6-1$
3|1 $2=6
|2| $  $
1|3=5--3
 2-3==2

```

# Answer
> 2 votes
# Python: 1303 Characters

This is some super ugly code, and it isn't particularly efficient, but I believe it works:

```
import sys
from itertools import product,combinations
e=[]
p=[[[0,(c,r,o,[])][c!='.'] for o,c in enumerate(l.strip())] for r,l in enumerate(open(sys.argv[1]))]
r=range(len(p))
c=range(len(p[0]))
for i,j in combinations(product(r,c),2):
 if p[i[0]][i[1]] and p[j[0]][j[1]]:
  if i[0]==j[0] and abs(i[1]-j[1])>1:
    b=1
    g=range(min(i[1],j[1])+1,max(i[1],j[1]))
    for x in g:
     if p[i[0]][x]:b=0
    if b:e+=[(i,j,[i[0]],g,1)]
  if i[1]==j[1] and abs(i[0]-j[0])>1:
    b=1
    g=range(min(i[0],j[0])+1,max(i[0],j[0]))
    for x in g:
     if p[x][i[1]]:b=0
    if b:e+=[(i,j,g,[i[1]],0)]
def s(v,i,m):
 if i>=len(v):
  return None
 for j in [2,1,0]:
  v[i]=j
  q=dict(m)
  b=1
  for l in [0,1]:
   n=e[i][l]
   if not n in q:q[n]=0
   q[n]+=j
   y=int(p[n[0]][n[1]][0])
   if q[n]>y:b=0
  if not b:continue
  a=[d for b in range(i+1) for d in product(e[b][2],e[b][3]) if v[b]>0]
  if len(a)!=len(set(a)):continue
  if i==len(v)-1:
   g=1
   for l,z in product(r,c):
    n=p[l][z]
    if not n:continue
    if q[(n[1],n[2])]!=int(n[0]):g=0
   if g:return v
  u=s(v,i+1,q)
  if u:return u
for i,v in zip(e,s([None]*len(e),0,{})):
 if v>0:
  for j,k in product(i[2],i[3]):p[j][k]=[[['|','$'][v-1],['-','='][v-1]][i[4]]]
for l in p:
 for c in l:
  if not c:c=[' ']
  sys.stdout.write(c[0])
 print ""

```

Example:

```
$ cat problem
4.4.1
.....
4.6.2
.....
..1..
$ python bridges.py problem
4=4-1
$ |
4=6=2
  |
  1

```

# Answer
> 2 votes
# Python 3/ 1780C

This problem can be converted to the exact cover problem. We can use Knuth's AlgorithmX to solve the exact cover problem.

I'll post the details about converting from input data to a 0-1 matrix later. It's very interesting.

Solving exact cover problem with AlgorithmX is very fast. On my machine, the example was solved within 0.09 second, in 310 iterations. And the program can output all solutions.

```
import sys
from itertools import product as I
a=sys.stdin.read().split()
V=list
L=len
Z=enumerate
W=range
P=V(I(W(L(a)),W(L(a[0]))))
E={p:[]for p in P}
Q={(i,j):int(a[i][j])for i,j in P if'.'!=a[i][j]}
J=Q.items()
F=[]
for p,c in J:
 for i,j in((0,1),(1,0)):
  q=p[0]+i,p[1]+j;e=[p,0]
  while q in P:
   E[q]+=[e]
   if q in Q:e[1]=q;E[p]+=[e];F+=[e];break
   q=q[0]+i,q[1]+j
E={x:[x for x in y if x[1]!=0]for x,y in E.items()}
C=[E[p] for p in P if p not in Q and L(E[p])>1]
m=[]
T=L(Q)+4*L(F)+L(C)
s=0
l={}
for p,c in J:
 e=E[p];u=L(e)*2
 for t in I(*((0,1,2)for x in e)):
  if sum(t)!=c:continue
  r=[0]*T;r[s+u]=1
  for i,x in Z(t):k=s+i*2;r[k:k+2]=((1,1),(0,1),(0,0))[x]
  m+=[r]
 l[p]=s;s+=u+1
z=L(m)
for e in F:
 p,q=e;r=[0]*T;c,d=l[p]+E[p].index(e)*2,l[q]+E[q].index(e)*2;t=r[:];r[c]=r[d]=1
 for i,u in Z(C):r[T-L(C)+i]=int(e in u)
 t[c+1]=t[d+1]=1;m+=[r,t]

def I(x,d):
 y=d[x]
 while y!=x:yield y;y=d[y]
def A(c):
 L[R[c]],R[L[c]]=L[c],R[c]
 for x in I(c,D):
  for y in I(x,R):U[D[y]],D[U[y]]=U[y],D[y]
def B(c):
 for x in I(c,U):
  for y in I(x,L):U[D[y]],D[U[y]]=y,y
 L[R[c]],R[L[c]]=c,c
def S():
 c=R[h]
 if c==h:yield[]
 A(c)
 for r in I(c,D):
  for x in I(r,R):A(C[x])
  for t in S():yield[r[0]]+t
  for x in I(r,L):B(C[x])
 B(c)
L,R,U,D,C={},{},{},{},{}
h=T
L[h]=R[h]=D[h]=U[h]=h
for c in W(T):
 R[L[h]],R[c],L[h],L[c]=c,h,c,L[h];U[c]=D[c]=c
for i,l in Z(m):
 s=0
 for c in I(h,R):
  if l[c]:
   r=i,c;D[U[c]],D[r],U[c],U[r],C[r]=r,c,r,U[c],c
   if s==0:L[r]=R[r]=s=r
   R[L[s]],R[r],L[s],L[r]=r,s,r,L[s]
for s in S():
 b=V(map(V,a))
 for e in s:
  if e<z:continue
  (i,j),(x,y)=F[(e-z)//2]
  if j==y:
   for r in W(i+1,x):b[r][j]='|H'[b[r][j]=='|']
  else:
   for r in W(j+1,y):b[i][r]='-='[b[i][r]=='-']
 print('\n'.join(''.join(l)for l in b).replace('.',' '))

```

---
Tags: code-golf
---


title: Build a 12-hour digital clock

text:
# Question
Title: Build a 12-hour digital clock
In my essay "Use the 24-hour clock", I claim that trying to represent the 12-hour clock directly in data is a terrible exercise in patchy, inelegant programming:

> "No problem, we'll just use computers to do these calculations for us." Yes, but computers need to be programmed. And trying to account for AM and PM directly in a computer program, especially the extremely tricky way we've encoded it, with 12 representing 0, is prone to bugs and programming mistakes, which can cost millions at the airport in scheduling mishaps. As it is, it's much easier for computers to work in 24-hour time in internal calculations, and then convert the times to 12-hour time for easy human reading, instead of having to deal with dozens of notational issues as would be the case when using 12-hour time directly. In which case, why not just get rid of the whole 12-hour conversion and work with 24-hour time in the first place?

Here's your chance to prove me wrong. Your task is to build a `Clock` class that supports the following functions:

* `addHours(x)`, that advances the clock by `x` hours (or moves back `|x|` hours if `x` is negative)
* `addMinutes(x)`, that advances the clock by `x` minutes.
* `diffMinutes(c1, c2)` that gives the time difference from clock `c1` to clock `c2` in minutes (which always assumes that c1 and c2 are representing times in the same day). If `c2` is earlier than `c1`, the time should be negative.

and has the following *publicly accessible* variables:

* `hours`, which represents the hour digit of the clock, from 1 to 12.
* `minutes`, which represents the minute digit of the clock, from 0 to 59.
* `ampm`, which is `true` if the clock is AM and `false` if the clock is PM.

as well as a setter and getter method (e.g. `setHours(hours)` and `getHours()`) for each. (You may assume that the setters and getters will always be passed valid values.) The reason the variables must be publicly accessible is to ensure that the internal data representation of the clock is also in a 12-hour format, to fit the data representation of the clock described in the essay.

Your code must pass all the unit tests contained in this file (translated to the programming language of your choice) except for test 0.2, which should be removed for this problem. (If the descriptions of the corner cases and their resultant times start to make your head spin, that's good. It means that my point about the strangeness of the notation is verified. It certainly made *my* head spin trying to make sure I had all the corner cases covered.)

Your score is calculated based on the number of operators and function calls in your class code, rather than the number of characters (so don't golf your code, make it readable but still short). Lowest score wins, of course.

Note: This problem has a part 2, namely, to create a 12-hour clock that uses 24-hour time in its internal representation. If my hypothesis is true, the winner of that problem will have a much lower score than the winner of this problem.

# Answer
> 2 votes
## Python (38)

Full code with tests here. A ton of the tests were wrong, so I modified them. Most of the changes are marked with the string "patch" in a comment, but I'm sure I forgot to mark some.

It was completely unclear if `diffMinutes(a, b)` was `abs(a-b)`, `a-b` or `b-a`, so I went with `b-a` because I had to change less tests that way.

Also, `ampm` is a terrible variable name. `isAM` would be a far more readable name, and `isPM` would be preferable, as true and false are often associated with 1 and 0, and PM is a higher/later value.

The interesting part (getters and setters in the link above):

```
def getMinutesFromMidnight(clock):
    return clock.hours * 60 % 720 + 720 * (not clock.ampm) + clock.minutes

def diffMinutes(a,b):
    return getMinutesFromMidnight(b) - getMinutesFromMidnight(a)

class Clock(object):
    def __init__(self):
        self.hours = 12
        self.minutes = 0
        self.ampm = True

    def addHours(self, hours):
        self.addMinutes(hours * 60)

    def addMinutes(self, minutes):
        minutes = getMinutesFromMidnight(self) + minutes
        self.hours = minutes / 60 % 12 or 12
        self.minutes = minutes % 60
        self.ampm = minutes % 1440 < 720

```

---
Tags: atomic-code-golf
---


# Question
Title: Generate a number by using a given list of numbers and arithmetic operators
You are given a list of numbers `L = [17, 5, 9, 17, 59, 14]`, a bag of operators `O = {+:7, -:3, *:5, /:1}` and a number `N = 569`.

## Task

Output an equation that uses all numbers in `L` on the left-hand side and only the number `N` on the right-hand side. If this is not possible, output False. Example solution:

```
59*(17-5)-9*17+14 = 569

```

## Limitations and Clarification

* You may not concatenate numbers (`[13,37]` may not be used as `1337`)
* Only natural numbers and zero will appear in `L`.
* The order in `L` doesn't matter.
* You must use all numbers in `L`.
* Only the operators `+`,`-`,`*`,`/` will appear in `O`.
* `O` can have more operators than you need, but at least `|L|-1` operators
* You may use each operator any number of times up to the value in `O`.
* All four operations in `O` are the standard mathematical operations; in particular, `/` is normal division with exact fractions.

## Points

* The less points, the better
* Every character of your code gives you one point

You have to provide an un-golfed version that is easy to read.

## Background

A similar question was asked on Stack Overflow. I thought it might be an interesting code-golf challenge.

## Computational Complexity

As Peter Taylor said in the comments, you can solve subset sum with this:

1. You have an instance of subset sum (hence a set S of integers and a number x)
2. L := S + \[0, ..., 0\] (|S| times a zero), N := x, O := {+:|S|-1, \*: |S| - 1, /:0, -: 0}
3. Now solve this instance of my problem
4. The solution for subset sum is the numbers of S that don't get multiplied with zero.

If you find an Algorithm that is better than O(2^n), you prove that P=NP. As P vs NP is a Millennium Prize Problem and hence worth 1,000,000 US-Dollar, it is very unlikely that somebody finds a solution for this. So I removed this part of the ranking.

## Test cases

The following are not the only valid answers, other solutions exist, and are permitted:

* (`[17,5,9,17,59,14]`, `{+:7, -:3, *:5, /:1}`, `569`)
**=\>** `59 * (17-5)- 9 * 17 + 14 = 569`
* (`[2,2]`, `{'+':3, '-':3, '*':3, '/':3}`, `1`)
**=\>** `2/2 = 1`
* (`[2,3,5,7,10,0,0,0,0,0,0,0]`, `{'+':20, '-':20, '*':20, '/':20}`, `16`)
**=\>** `5+10-2*3+7+0+0+0+0+0+0+0 = 16`
* (`[2,3,5,7,10,0,0,0,0,0,0,0]`, `{'+':20, '-':20, '*':20, '/':20}`, `15`)
**=\>** `5+10+0*(2+3+7)+0+0+0+0+0+0 = 15`

# Answer
> 3 votes
# Python 2.7 / 478 chars

```
L=[17,5,9,17,59,14]
O={'+':7,'-':3,'*':5,'/':1}
N=569
P=eval("{'+l+y,'-l-y,'*l*y,'/l/y}".replace('l',"':lambda x,y:x"))
def S(R,T):
 if len(T)>1:
  c,d=y=T.pop();a,b=x=T.pop()
  for o in O:
   if O[o]>0 and(o!='/'or y[0]):
    T+=[(P[o](a, c),'('+b+o+d+')')];O[o]-=1
    if S(R,T):return 1
    O[o]+=1;T.pop()
  T+=[x,y]
 elif not R:
  v,r=T[0]
  if v==N:print r
  return v==N
 for x in R[:]:
  R.remove(x);T+=[x]
  if S(R,T):return 1
  T.pop();R+=[x]
S([(x,`x`)for x in L],[])

```

The main idea is to use postfix form of an expression to search. For example, `2*(3+4)` in postfix form will be `234+*`. So the problem become finding a partly permutation of `L`+`O` that evalates to `N`.

The following version is the ungolfed version. The stack `stk` looks like `[(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))]`.

```
L = [17, 5, 9, 17, 59, 14]
O = {'+':7, '-':3, '*':5, '/':1}
N = 569

P = {'+':lambda x,y:x+y,
     '-':lambda x,y:x-y,
     '*':lambda x,y:x*y,
     '/':lambda x,y:x/y}

def postfix_search(rest, stk):
    if len(stk) >= 2:
        y = (v2, r2) = stk.pop()
        x = (v1, r1) = stk.pop()
        for opr in O:
            if O[opr] > 0 and not (opr == '/' and v2 == 0):
                stk += [(P[opr](v1, v2), '('+r1+opr+r2+')')]
                O[opr] -= 1
                if postfix_search(rest, stk): return 1
                O[opr] += 1
                stk.pop()
        stk += [x, y]
    elif not rest:
        v, r = stk[0]
        if v == N: print(r)
        return v == N
    for x in list(rest):
        rest.remove(x)
        stk += [x]
        if postfix_search(rest, stk):
            return True
        stk.pop()
        rest += [x]
postfix_search(list(zip(L, map(str, L))), [])

```

---
Tags: code-golf, math, arithmetic, expression-building
---


title: Group adjacent values

text:
# Question
Title: Group adjacent values
The task is to group adjacent values from collection and output it as a new aggregated collection.

Consider we have following input:

```
Sequence
Number      Value
========    =====
1           9
2           9
3           15
4           15
5           15
6           30
7           9

```

The aim is to enumerate over Sequence Numbers and check if the next element has the same value. If yes, values are aggregated and so, desired output is as following:

```
Sequence    Sequence
Number      Number
From        To          Value
========    ========    =====
1           2           9
3           5           15
6           6           30
7           7           9

```

Build a code with following assumptions:

* Sequence Numbers are already ordered in input table.
* There can be gaps in Sequence Numbers. If input contains gaps, output should contain gaps too. For example input `1 99\n2 99\n4 99\n6 99`, output will be `1 2 99\n4 4 99\n6 6 99`.
* Assume Value is type of integer.
* It can be a full program or just a function.
* This cruft `(Sequence Sequence\n` ... `======== ======== =====\n)` is not a part of output. Output format is not defined; there should be a delimeter between values and between rows, so anyone can distinguish values and rows.

It's an extend of my StackOverflow question: https://stackoverflow.com/questions/14879197/linq-query-data-aggregation.

# Answer
# K, 43 38

{d:(x;0N,x;y)@\\:&~~':y;d\[1\]:(1\_d 1),\*|x;+d}

```
{a::*|x;+@[(x;{x,a};y)@\:&~~':y;1;1_]}

```

.

```
k){a::*|x;+@[(x;{x,a};y)@\:&~~':y;1;1_]}[1 2 3 4 5 6 7;9 9 15 15 15 30 9]
1 2 9
3 5 15
6 6 30
7 7 9

```

# Explanation

The function takes two vectors, `x` and `y`, as input

`a::*|x` takes the last value of `x` and assigns it to `a`.

`&~~':y` returns a list of indices where the `y` vector changes:

```
k){&~~':y}[1 2 3 4 5 6 7;9 9 15 15 15 30 9]
0 2 5 6

```

`(x;{x,a};y)` creates a three element list containing

1) the `x` vector,

2) the function `{x,a}` which takes an input variable `x`(not to be confused with the `x` vector which was input into the original function) and appends `a`, and

3) the `y` vector

`(x;{x,a};y)@\:&~~':y` takes this three element list and applies the indices to each element so that we return the `x` vector at those indices, the indices with `a` appended, and the `y` vector at those indices

```
k){b::*|x;(x;{x,b};y)@\:&~~':y}[1 2 3 4 5 6 7;9 9 15 15 15 30 9]
1 3 6 7
0 2 5 6 7
9 15 30 9

```

`@[(x;{x,a};y)@\:&~~':y;1;1_]` takes the matrix we've created and drops the first element of the second row.

```
k){b::*|x;@[(x;{x,b};y)@\:&~~':y;1;1_]}[1 2 3 4 5 6 7;9 9 15 15 15 30 9]
1 3  6  7
2 5  6  7
9 15 30 9

```

`+` then transposes the result

```
k){b::*|x;+@[(x;{x,b};y)@\:&~~':y;1;1_]}[1 2 3 4 5 6 7;9 9 15 15 15 30 9]
1 2 9
3 5 15
6 6 30
7 7 9

```
> 4 votes

# Answer
## *Mathematica*, ~~40~~ 47 / 40

Updated to handle the new rules:

```
#~Riffle~{##}[[-1,1]]&@@@Split[#,#2-#=={1,0}&]&

```

Example of use:

```
#~Riffle~{##}[[-1,1]]&@@@Split[#,#2-#=={1,0}&]& @
  {{1, 9}, {2, 9}, {3, 9}, {4, 15}, {5, 15}, {6, 30}, {7, 9}, {12, 9}}

```

> ```
> {{1, 3, 9}, {4, 5, 15}, {6, 6, 30}, {7, 7, 9}, {12, 12, 9}}
>
> ```

Or, since "There are no restrictions on input/output format":

```
#[[1,1]]|Last@#&/@Split[#,#2-#=={1,0}&]&

```

Which when used as above outputs:

> ```
> {1 | {3, 9}, 4 | {5, 15}, 6 | {6, 30}, 7 | {7, 9}, 12 | {12, 9}}
>
> ```
> 4 votes

# Answer
## J, ~~53~~ ~~48~~ 43

Explicit version (43 chars):

```
f=.4 :'|:(#&y,{.@:#&x)(1&,,:,&1)2(-.@=/\)x'

```

Tacit version (48 chars):

```
(|:@((#{.)~,{.@]#{:@[)[:(1&,,:,&1)2&(-.@=/\)@{:)

```

Ungolfed version:

```
(|:@(({.@[#~]),{:@[#~{.@])((1&,),:,&1)@(-.@(0&=)@(2&(-/\)@{:)))

```

Maybe not the best way, but had a lot of fun golfing it down.

```
   1 2 3 4 5 6 7 f 9 9 15 15 15 30 9
   or
   (...) 1 2 3 4 5 6 7,:9 9 15 15 15 30 9
1 2  9
3 5 15
6 6 30
7 7  9

```
> 3 votes

# Answer
# JavaScript, 106

```
function(c){for(var n={f:1,t:1,v:c[0]},r=[n],i=1,t;t=c[i++];)t^n.v?r.push(n={f:i,t:i,v:t}):n.t++;return r}

```

If input as a global called `c` is okay, then **101**:

```
eval.bind(0,'for(var n={f:1,t:1,v:c[0]},r=[n],i=1,t;t=c[i++];)t^n.v?r.push(n={f:i,t:i,v:t}):n.t++;r')

```
> 1 votes

# Answer
## Python, 86

```
n=input()
for s,v in n:
 i=1
 while[s+i,v]in n:n.remove([s+i,v]);i+=1
 print s,s+i-1,v

```
> 1 votes

# Answer
## APL 39

```
(p/n),((1⌽p)/n←⍎⍞),[1.1](p←1,2≠/v)/v←⍎⍞

```

The above takes screen input as the function runs via ←⍎⍞. If the vectors n and v are allowed to be predefined globals then the count reduces to 33:

```
(p/n),((1⌽p)/n),[1.1](p←1,2≠/v)/v

```

For n←1 2 3 4 5 6 7 and v←9 9 15 15 15 30 9

```
1 2  9
3 5 15
6 6 30
7 7  9

```
> 1 votes

# Answer
# Python 2 - 82

```
r=p=[]
for x,y in input():
 if[x-1,y]==p[1:]:p[1]=x
 else:p=[x,x,y];r+=[p]
print r

```

Example usage:

```
echo "[[1,9],[2,9],[3,15],[4,15],[5,15],[6,30],[7,9]]"|python2 values.py
[[1, 2, 9], [3, 5, 15], [6, 6, 30], [7, 7, 9]]
echo "[[1,99],[2,99],[4,99],[6,99]]"|python2 values.py
[[1, 2, 99], [4, 4, 99], [6, 6, 99]]

```
> 1 votes

# Answer
# Golfscript - 42

```
~(~@@.@{.~5$=\3$)=&{;)}{:*;@]p*~\.}if}/@]p

```

Examples:

```
echo "[[1 9][2 9][3 15][4 15][5 15][6 30][7 9]]"|ruby golfscript.rb values.gs
[1 2 9]
[3 5 15]
[6 6 30]
[7 7 9]

echo "[[1 99][2 99][4 99][6 99]]"|ruby golfscript.rb values.gs
[1 2 99]
[4 4 99]
[6 6 99]

```

Explanation:

It takes the first pair \[a b\], and puts b, a, a1=a and the rest of the array on the stack. Then for each pair \[x y\] it compares y with b and x with a1+1. If equal then discards \[x y\] and increments a1, else pops and remembers \[x y\], prints \[a a1 b\] and pushes y, x, x1=x. At the end it prints the last \[x x1 y\].
> 1 votes

# Answer
### GolfScript, 49/44 characters

```
~]2/{\.@.@~@~@=@@-)!&!{n\}*}*][n]%{.0=0=\-1=~]p}%

```

The solution takes input from STDIN and prints to STDOUT. If you transform the code into an expression working on lists it reduces to 44 characters.

```
{\.@.@~@~@=@@-)!&!{n\}*}*][n]%{.0=0=\-1=~]}%

```

Example:

```
1 9
2 9
3 15
4 15
5 15
6 30
7 9

[1 2 9]
[3 5 15]
[6 6 30]
[7 7 9]

```

This version does also work with gaps as required.

```
1 9
3 9
4 15
6 15
7 15

[1 1 9]
[3 3 9]
[4 4 15]
[6 7 15]

```
> 1 votes

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


# Question
Title: solve puzzle with a tweet? javascript (fun challenge)
the question is "complete this subtraction by replacing the asterisks with digits so the numbers 1-9 only appear once each"

```
 9**
-*4*
____
 **1

```

my code tries random numbers until it works, and displays the answer. here is the entire html app. I want one to fit in a tweet at 140 characters (not counting tags)

```
<script>
function r(){return Math.random()*9+1^0}
do{a=900+r()*10+r(),b=r()*100+40+r(),c=a-b,s=''+a+b+c
}while(c%10!=1||eval('for(i=0;i++<9;)if(s.indexOf(i)<0)1'))alert(s)
</script>

```

Is there any way to make this shorter, including with a different solution?

SOLVED!: Thanks Peter, Shmiddty and copy, currently I have 91 chars!

```
for(x=1;++x<999;)for(y=1;y<x;)/(?!.*0|.*(.).*\1)9...4...1/.test(s=''+x+y+(x-y++))&&alert(s)

```

# Answer
## JavaScript (118 110 102 96 95 99 98 93 chars)

```
for(x=1;x;x++)for(y=1;y<x;)/(?!.*0|.*(.).*\1)9...4...1/.test(s=''+x+y+(x-y++))&&alert(s,x=-1)

```

This will give the lexicographically smallest solution. Thanks to copy for 98-\>93.

You can enumerate all of them for 91 chars:

```
for(x=1;++x<999;)for(y=1;y<x;)/(?!.*0|.*(.).*\1)9...4...1/.test(s=''+x+y+(x-y++))&&alert(s)

```

Thanks to Shmiddty for pointing out a standard optimisation which slipped straight past me.

Allowing `0` as well, in \<2.5 tweets, here's the analysis:

```
9ab-c4d=ef1; b-d in {1,-9}; 2nd => d=9 so bd in {32,65,76,87}, no carry. a-f in {4,*-6} so af in {62,73,*06,*28}. 9-c=e or *8-c=e so ce in
{27,36,63,72} or *{08,26,35,53,62,80}. af in {62,73} => no ce. af in {06,28} => ce in {35,53}; 06 => bd=87; 28 => bd=76. So four solutions:
927-346=581; 927-546=381; 908-347=561; 908-547=361

```

Removing `0` shrinks the analysis to fit in two tweets:

```
9ab-c4d=ef1; b-d in {1,-9}; 2nd => d=9 so bd in {32,65,76,87}, no carry. a-f in {4,*-6} so af in {62,73,*28}. 9-c=e or *8-c=e so ce in
{27,36,63,72} or *{26,35,53,62}. af in {62,73} => no ce. af=28 => ce in {35,53} => bd=76. So 927-346=581; 927-546=381.

```
> 2 votes

# Answer
# k (116 chars)

It's possible in k... Returns all possible solutions. (Count ignores unnecessary whitespace).

```
{a:"9",','[;"1"]i@&:6=#:'i:?:'{,/x,/:\:y}/7#,:"8765320";
 b:"I"$0N 3#/:a[;i],'"4",'a[;4+i:!4];
 b@&:b[;2]='(-).'b[;0 1]}

```
> 1 votes

---
Tags: code-golf, puzzle-solver
---


title: Drawing 3d nets - Archimedean solids

text:
# Question
Title: Drawing 3d nets - Archimedean solids
I have a weakness for 3d nets which when cut out and folded allow you to make 3d shapes out of paper or card. The task is simple, written the shortest program you can that draws nets for the 13 Archimedean solids. The output should be an image file in any sensible format (png, jpg).

All thirteen shapes are described at http://en.wikipedia.org/wiki/Archimedean\_solid and in the following table taken from there.

**Input:** An integer from 1 to 13. Assume the shapes are numbered exactly as in the table above so that the "truncated tetrahedron" is number 1 and the "snub dodecahedron" is number 13.

**Output:** An image file containing the net for that shape. Just the outline including the internal lines is OK. There is no need to fill it in with colors

You can use any programming language you like as well as any library that was not made especially for this competition. Both should be available freely however (in both senses) online.

I will accept the answer with the smallest number of characters in exactly one week's time. Answers will be accepted whenever they come.

**(No) Winner yet.** Sadly no valid entrants. Maybe it is too hard?

# Answer
# Java, 1552

```
import java.awt.*;import java.awt.image.*;import java.io.*;import javax.imageio.*;class
A{public static void main(String[]x)throws
Exception{String[]a={"33623368356:356;66","33413341334535463547354735473444","33823382338:3586338>358>358>358?88","66456:466:466845684668466766","334144453546354635474746464646464647354634463446344744","88456:466:466:4668458<468<468<468:456846684668466788","33343535353231333535313133353447353434353534313133353447353545343535313133353447353545343444","33513351335233593554335433593554335935543359355433593559355835593559355935593455","33:233:233:433:B35:833:833:B35:833:B35:833:B35:833:B35:B35:833:B35:B35:B35:B35:C::","66566:576:57696869576969586969586:586969576969586857685868586766","334155453546354635463547594658465846584658473546354634463546344635463446354634463547584657465746574657473546344634463446344755","::456:466:466:466:466845:@46:@46:@46:@46:>4568466:4668466:4668466:4668466:4668466845:>46:>46:>46:>46:<45684668466846684667::","333531333434343132333434353531313335343434323232323334343435353231333133343556343434313233323335345935353532313331313132333233353535343557343133343556343434355934353535593432333234355935323335345935323335345935323335345935343459313334353455"};BufferedImage
m=new BufferedImage(1300,1300,1);Graphics2D g=m.createGraphics();g.translate(500,500);String
s=a[Integer.valueOf(x[0])-1];int f=1,i=0,n,t;while(i<s.length()){n=s.charAt(i++)-48;t=s.charAt(i++);while(t-->48){g.drawLine(0,0,20,0);g.translate(20,0);g.rotate(f*Math.PI*2/n);}f=-f;}ImageIO.write(m,"png",new File("o.png"));}}

```

Ungolfed:

```
import java.awt.Graphics2D;
import java.awt.geom.AffineTransform;
import java.awt.image.BufferedImage;
import java.io.File;

import javax.imageio.ImageIO;

public class A {
    static int f = 1;
    static Graphics2D g;

    static void fixtrans() {
        double[] m = new double[6];
        g.getTransform().getMatrix(m);
        for (int i = 0; i < 6; ++i) {
            if (Math.abs(m[i] - Math.round(m[i])) < 1e-5) {
                m[i] = Math.round(m[i]);
            }
        }
        g.setTransform(new AffineTransform(m));
    }

    static void d(String s) {
        for (int i = 0; i < s.length();) {
            int n = s.charAt(i++) - '0';
            int t = s.charAt(i++) - '0';
            for (int j = 0; j < t; ++j) {
                g.drawLine(0, 0, 20, 0);
                g.translate(20, 0);
                g.rotate(f * Math.PI * 2 / n);
                fixtrans(); // optional, straightens some lines
            }
            f = -f;
        }
    }

    public static void main(String[] args) throws Exception {
        String[] a = {
                "33623368356:356;66",
                "33413341334535463547354735473444",
                "33823382338:3586338>358>358>358?88",
                "66456:466:466845684668466766",
                "334144453546354635474746464646464647354634463446344744",
                "88456:466:466:4668458<468<468<468:456846684668466788",
                "33343535353231333535313133353447353434353534313133353447353545343535313133353447353545343444",
                "33513351335233593554335433593554335935543359355433593559355835593559355935593455",
                "33:233:233:433:B35:833:833:B35:833:B35:833:B35:833:B35:B35:833:B35:B35:B35:B35:C::",
                "66566:576:57696869576969586969586:586969576969586857685868586766",
                "334155453546354635463547594658465846584658473546354634463546344635463446354634463547584657465746574657473546344634463446344755",
                "::456:466:466:466:466845:@46:@46:@46:@46:>4568466:4668466:4668466:4668466:4668466845:>46:>46:>46:>46:<45684668466846684667::",
// bad          "333531333434343132333434353531313335343434323232323334343435353231333133343556343434313233323335345935353532313331313132333233353535343557343133343556343434355934353531333459343434355935323335345935323335345935323335345935323335345935353455"
                "333531333434343132333434353531313335343434323232323334343435353231333133343556343434313233323335345935353532313331313132333233353535343557343133343556343434355934353535593432333234355935323335345935323335345935323335345935343459313334353455"};

        BufferedImage img = new BufferedImage(1300, 1300, BufferedImage.TYPE_INT_RGB);
        g = img.createGraphics();
        g.translate(500, 500);
        d(a[Integer.parseInt(args[0]) - 1]);
        String f = args[0] + ".png";
        ImageIO.write(img, "png", new File(f));
    }
}

```

Results (trimmed, negated, joined and scaled):

The shapes are quite unusual :) but correct as far as I can tell (let me know if you find any errors). They were generated (in a separate program) by constructing the face graph and cutting cycles in a DFS.

I'm sure this can be golfed quite a lot more using e.g. python and turtle.

**Edit:** oops, the last case was self-intersecting a bit. I fixed the code (by hand), here's the updated image:
> 8 votes

# Answer
## Mathematica

Out of competition, not a free language

```
f[n_] := PolyhedronData[Sort[PolyhedronData["Archimedean",
                                             {"FaceCount", "StandardName"}]][[n, 2]],  "NetImage"]

```

Usage:

```
f /@ Range@13

```
> 6 votes

---
Tags: code-golf
---


title: Email validation

text:
# Question
Title: Email validation
Write a function or program to validate an e-mail address against RFC 5321 (some grammar rules found in 5322) with the relaxation that you can ignore comments and folding whitespace (`CFWS`) and generalised address literals. This gives the grammar

```
Mailbox              = Local-part "@" ( Domain / address-literal )

Local-part           = Dot-string / Quoted-string
Dot-string           = Atom *("."  Atom)
Atom                 = 1*atext
atext                = ALPHA / DIGIT /    ; Printable US-ASCII
                       "!" / "#" /        ;  characters not including
                       "$" / "%" /        ;  specials.  Used for atoms.
                       "&" / "'" /
                       "*" / "+" /
                       "-" / "/" /
                       "=" / "?" /
                       "^" / "_" /
                       "`" / "{" /
                       "|" / "}" /
                       "~"
Quoted-string        = DQUOTE *QcontentSMTP DQUOTE
QcontentSMTP         = qtextSMTP / quoted-pairSMTP
qtextSMTP            = %d32-33 / %d35-91 / %d93-126
quoted-pairSMTP      = %d92 %d32-126

Domain               = sub-domain *("." sub-domain)
sub-domain           = Let-dig [Ldh-str]
Let-dig              = ALPHA / DIGIT
Ldh-str              = *( ALPHA / DIGIT / "-" ) Let-dig

address-literal      = "[" ( IPv4-address-literal / IPv6-address-literal ) "]"
IPv4-address-literal = Snum 3("."  Snum)
IPv6-address-literal = "IPv6:" IPv6-addr
Snum                 = 1*3DIGIT
                       ; representing a decimal integer value in the range 0 through 255

```

Note: I've skipped the definition of `IPv6-addr` because this particular RFC gets it wrong and disallows e.g. `::1`. The correct spec is in RFC 2373.

### Restrictions

You may not use any existing e-mail validation library calls. However, you may use existing network libraries to check IP addresses.

If you write a function/method/operator/equivalent it should take a string and return a boolean or truthy/falsy value, as appropriate for your language. If you write a program it should take a single line from stdin and indicate valid or invalid via the exit code.

### Test cases

The following test cases are listed in blocks for compactness. The first block are cases which should pass:

```
email@domain.com
e@domain.com
firstname.lastname@domain.com
email@subdomain.domain.com
firstname+lastname@domain.com
email@123.123.123.123
email@[123.123.123.123]
"email"@domain.com
1234567890@domain.com
email@domain-one.com
_______@domain.com
email@domain.name
email@domain.co.jp
firstname-lastname@domain.com
""@domain.com
"e"@domain.com
"\@"@domain.com
email@domain
"Abc\@def"@example.com
"Fred Bloggs"@example.com
"Joe\\Blow"@example.com
"Abc@def"@example.com
customer/department=shipping@example.com
$A12345@example.com
!def!xyz%abc@example.com
_somename@example.com
_somename@[IPv6:::1]
fred+bloggs@abc.museum
email@d.com
?????@domain.com

```

The following test cases should not pass:

```
plainaddress
#@%^%#$@#$@#.com
@domain.com
Joe Smith <email@domain.com>
email.domain.com
email@domain@domain.com
.email@domain.com
email.@domain.com
email.email.@domain.com
email..email@domain.com
email@domain.com (Joe Smith)
email@-domain.com
email@domain..com
email@[IPv6:127.0.0.1]
email@[127.0.0]
email@[.127.0.0.1]
email@[127.0.0.1.]
email@IPv6:::1]
_somename@domain.com]
email@[256.123.123.123]

```

# Answer
## Python 3.3, 261

```
import re,ipaddress
try:v,p=re.match(r'^(?!\.)(((^|\.)[\w!#-\'*+\-/=?^-~]+)+|"([ !#-[\]-~]|\\[ -~])*")@(((?!-)[a-zA-Z\d-]+(?<!-)($|\.))+|\[(IPv6:)?(.*)\])(?<!\.)$',input()).groups()[7:];exec("if p:ipaddress.IPv%dAddress(p)"%(v and 6or 4))
except:v=5
print(v!=5)

```

Python 3.3 is needed for the ipaddress module, which is used to validate IPv4 and IPv6 addresses.

Less golfed version:

```
import re, ipaddress

dot_string = r'(?!\.)((^|\.)[\w!#-\'*+\-/=?^-~]+)+'
    # negative lookahead to check that string doesn't start with .
    # each atom must start with a . or the beginning of the string

quoted_string = r'"([ !#-[\]-~]|\\[ -~])*"'
    # - is used for character ranges (also in dot_string)

domain = r'((?!-)[a-zA-Z\d-]+(?<!-)($|\.))+(?<!\.)'
    # negative lookahead/lookbehind to check each subdomain doesn't start/end with -
    # each domain must end with a . or the end of the string
    # negative lookbehind to check that string doesn't end with .

address_literal = r'\[(IPv6:)?(.*)\]'
    # captures the is_IPv6 and ip_address groups

final_regex = r'^(%s|%s)@(%s|%s)$' % (dot_string, quoted_string, domain, address_literal)

try:
    is_IPv6, ip_address = re.match(final_regex, input(), re.VERBOSE).groups()[7:]
        # if input doesn't match, calling .groups() will throw an exception

    if ip_address:
        exec("ipaddress.IPv%dAddress(ip_address)" % (6 if is_IPv6 else 4))
            # IPv4Address or IPv6Address will throw an exception if ip_address isn't valid
except:
    is_IPv6 = 5

print(is_IPv6 != 5)
    # is_IPv6 is used as a flag to tell whether an exception was thrown

```
> 3 votes

# Answer
PHP 5.4.9, 495

```
function _($e){return preg_match('/^(?!(?>"?(?>\\\[ -~]|[^"])"?){255,})(?!"?(?>\\\[ -~]|[^"]){65,}"?@)(?>([!#-\'*+\/-9=?^-~-]+)(?>\.(?1))*|"(?>[ !#-\[\]-~]|\\\[ -~])*")@(?!.*[^.]{64,})(?>([a-z0-9](?>[a-z0-9-]*[a-z0-9])?)(?>\.(?2)){0,126}|\[(?:(?>IPv6:(?>([a-f0-9]{1,4})(?>:(?3)){7}|(?!(?:.*[a-f0-9][:\]]){8,})((?3)(?>:(?3)){0,6})?::(?4)?))|(?>(?>IPv6:(?>(?3)(?>:(?3)){5}:|(?!(?:.*[a-f0-9]:){6,})(?5)?::(?>((?3)(?>:(?3)){0,4}):)?))?(25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)(?>\.(?6)){3}))\])$/iD', $e);}

```

And just for further interest, here's one for RFC 5322 grammar which allows for nested CFWS and obsolete local-parts:

(764)

```
function _($e){return preg_match('/^(?!(?>(?1)"?(?>\\\[ -~]|[^"])"?(?1)){255,})(?!(?>(?1)"?(?>\\\[ -~]|[^"])"?(?1)){65,}@)((?>(?>(?>((?>(?>(?>\x0D\x0A)?[\t ])+|(?>[\t ]*\x0D\x0A)?[\t ]+)?)(\((?>(?2)(?>[\x01-\x08\x0B\x0C\x0E-\'*-\[\]-\x7F]|\\\[\x00-\x7F]|(?3)))*(?2)\)))+(?2))|(?2))?)([!#-\'*+\/-9=?^-~-]+|"(?>(?2)(?>[\x01-\x08\x0B\x0C\x0E-!#-\[\]-\x7F]|\\\[\x00-\x7F]))*(?2)")(?>(?1)\.(?1)(?4))*(?1)@(?!(?1)[a-z\d-]{64,})(?1)(?>([a-z\d](?>[a-z\d-]*[a-z\d])?)(?>(?1)\.(?!(?1)[a-z\d-]{64,})(?1)(?5)){0,126}|\[(?:(?>IPv6:(?>([a-f\d]{1,4})(?>:(?6)){7}|(?!(?:.*[a-f\d][:\]]){8,})((?6)(?>:(?6)){0,6})?::(?7)?))|(?>(?>IPv6:(?>(?6)(?>:(?6)){5}:|(?!(?:.*[a-f\d]:){6,})(?8)?::(?>((?6)(?>:(?6)){0,4}):)?))?(25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)(?>\.(?9)){3}))\])(?1)$/isD', $e);}

```

And if length-limits are not a requirement:

**RFC 5321** (414)

```
function _($e){return preg_match('/^(?>([!#-\'*+\/-9=?^-~-]+)(?>\.(?1))*|"(?>[ !#-\[\]-~]|\\\[ -~])*")@(?>([a-z0-9](?>[a-z0-9-]*[a-z0-9])?)(?>\.(?2)){0,126}|\[(?:(?>IPv6:(?>([a-f0-9]{1,4})(?>:(?3)){7}|(?!(?:.*[a-f0-9][:\]]){8,})((?3)(?>:(?3)){0,6})?::(?4)?))|(?>(?>IPv6:(?>(?3)(?>:(?3)){5}:|(?!(?:.*[a-f0-9]:){6,})(?5)?::(?>((?3)(?>:(?3)){0,4}):)?))?(25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)(?>\.(?6)){3}))\])$/iD', $e);}

```

**RFC 5322** (636)

```
function _($e){return preg_match('/^((?>(?>(?>((?>(?>(?>\x0D\x0A)?[\t ])+|(?>[\t ]*\x0D\x0A)?[\t ]+)?)(\((?>(?2)(?>[\x01-\x08\x0B\x0C\x0E-\'*-\[\]-\x7F]|\\\[\x00-\x7F]|(?3)))*(?2)\)))+(?2))|(?2))?)([!#-\'*+\/-9=?^-~-]+|"(?>(?2)(?>[\x01-\x08\x0B\x0C\x0E-!#-\[\]-\x7F]|\\\[\x00-\x7F]))*(?2)")(?>(?1)\.(?1)(?4))*(?1)@(?1)(?>([a-z\d](?>[a-z\d-]*[a-z\d])?)(?>(?1)\.(?1)(?5)){0,126}|\[(?:(?>IPv6:(?>([a-f\d]{1,4})(?>:(?6)){7}|(?!(?:.*[a-f\d][:\]]){8,})((?6)(?>:(?6)){0,6})?::(?7)?))|(?>(?>IPv6:(?>(?6)(?>:(?6)){5}:|(?!(?:.*[a-f\d]:){6,})(?8)?::(?>((?6)(?>:(?6)){0,4}):)?))?(25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)(?>\.(?9)){3}))\])(?1)$/isD', $e);}

```
> 2 votes

---
Tags: code-golf, string, decision-problem
---


# Question
Title: Build an adding machine using NAND logic gates
This is "programming" at its most fundamental.

Build a diagram of (two-wire) NAND logic gates that will take the input wires `A1`, `A2`, `A4`, `A8`, `B1`, `B2`, `B4`, `B8`, representing two binary numbers `A` to `B` from 0 to 15, and return values on the output wires `C1`, `C2`, `C4`, and `C8` representing `C`, which is the sum of `A` and `B` modulo 16.

Your score is determined by the number of NAND gates (1 point per gate). To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

* `NOT: 1`
* `AND: 2`
* `OR: 3`
* `XOR: 4`

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

Lowest score wins.

---

Updates:

**03-07 19:09:** Due to discussions with Jan Dvorak, it came to my attention that the total number of gates, constants and splits is always determined solely by the number of gates. Because of this, I have simplified the score requirement back down to simply the number of gates required.

# Answer
> 8 votes
# 31 gates

<sup>*\[created in Logisim\]*</sup>

---

The standard XOR-gate can be built with four NANDs. Tapping the first NAND provides us with a fairly compact half-adder with inverted carry:

```
hadder(A,B) => (sum, iCarry):

X = A^B

sum = (A^X)^(B^X)
iCarry = X

```

These can be combined into a 9-gate full adder:

```
fadder(A,B,C) => (sum, carry):

DD1 = hadder(A,B)
DD2 = hadder(DD1.sum, C)

sum = DD2.sum
carry = DD1.iCarry ^ DD2.iCarry

```

These combined yield a naive **36**-gate four-bit adder. Not bad.

Now, we inline all modules and perform these optimizations:

```
delete gates with no output (only the final gate)
0^x => 1                    (one gate, twice)
1^(1^x) => 0                (two gates, once)

```

for a grand total of **31 gates**.

---

Note that the count of splits and NAND-gates are intimately connected: Each 2-input NAND (larger are explicitly forbidden) takes two inputs and produces one output. Each 2-way split (let's assume larger splits are forbidden) takes one input and produces two outputs. Also, there are no unused outputs or floating inputs (let's assume constants are not allowed). If there are N more inputs than outputs, there must be N more NANDs than splits.

Thus, a 31-NAND 8=\>4 module will neccessarily have 27 2-way splits.

Here are the split cardinalities for the above adder just in case larger splits are allowed:

```
18x wire (no split)
  4x output
  14x XOR 2nd stage
16x 2-way split
  8x input
  6x H2 input
  2x last bit XOR 1st stage
4x  3-way split
  4x XOR 1st stage
1x  4-way split
  1x 1st bit XOR 1st stage; if constants are alloweed; this is a three-way split

```

---
Tags: atomic-code-golf, logic-gates
---


# Question
Title: Implement an IEEE 754 64-bit binary floating point number through integer manipulation
(I've tagged the question "C" for the time being, but if you're aware of another language that supports unions, you can also use that.)

Your task is to build the four standard mathematical operators `+ - * /` for the following struct:

```
union intfloat{
    double f;
    uint8_t h[8];
    uint16_t i[4];
    uint32_t j[2];
    uint64_t k;
    intfloat(double g){f = g;}
    intfloat(){k = 0;}
}

```

such that the operations themselves only ever manipulate or access the integer part (so no comparing with the double anytime during the operation either), and the result is exactly the same (or functionally equivalent, in the case of non-numeric results such as `NaN`) as if the corresponding mathematical operation had been applied straight to the `double` instead.

You may choose which integer part to manipulate, perhaps even using different ones among different operators. (You can also choose to remove the "unsigned" from any of the fields in the union, although I'm not sure whether you'd want to do that.)

Your score is the sum of the length of code in characters for each of the four operators. Lowest score wins.

For those of us unfamiliar with the IEEE 754 specification, here is an article about it on Wikipedia.

---

Edits:

**03-06 08:47** Added constructors to the intfloat struct. You are allowed to use them for testing, rather than manually setting the double / etc.

# Answer
> 11 votes
## C++, ~1500 chars

Expands the floats into an 8000-binary-digit fixed-point representation, does the operations on that, then converts back.

```
// an "expanded" float.
// n is nan, i is infinity, z is zero, s is sign.
// nan overrides inf, inf overrides zero, zero overrides digits.
// sign is valid unless nan.
// We store the number in fixed-point, little-endian.  Binary point is
// at N/2.  So 1.0 is N/2 zeros, one, N/2-1 zeros.
#define N 8000
struct E {
  int n;
  int i;
  int z;
  long s;
  long d[N];
};
#define V if(r.n|r.i|r.z)return r
// Converts a regular floating-point number to an expanded one.
E R(F x){
  long i,e=x.k<<1>>53,m=x.k<<12>>12;
  E r={e==2047&&m!=0,e==2047,e+m==0,x.k>>63};
  if(e)m+=1L<<52;else e++;
  for(i=0;i<53;i++)r.d[2925+e+i]=m>>i&1;
  return r;
}
E A(E x,E y){
  int i,c,v;
  if(x.s>y.s)return A(y,x);
  E r={x.n|y.n|x.i&y.i&(x.s^y.s),x.i|y.i,x.z&y.z,x.i&x.s|y.i&y.s|~x.i&~y.i&x.s&y.s};V;
  if(x.s^y.s){
    c=0;
    r.z=1;
    for(i=0;i<N;i++){
      v=x.d[i]-y.d[i]-c;
      r.d[i]=v&1;c=v<0;
      r.z&=~v&1;
    }
    if(c){x.s=1;y.s=0;r=A(y,x);r.s=1;}
  }else{
    c=0;
    for(i=0;i<N;i++){
      v=x.d[i]+y.d[i]+c;
      r.d[i]=v&1;c=v>1;
    }
  }
  return r;
}
E M(E x, E y){
  int i;
  E r={x.n|y.n|x.i&y.z|x.z&y.i,x.i|y.i,x.z|y.z,x.s^y.s};V;
  E s={0,0,1};
  for(i=0;i<6000;i++)y.d[i]=y.d[i+2000];
  for(i=0;i<4000;i++){
    if(x.d[i+2000])s=A(s,y);
    y=A(y,y);
  }
  s.s^=x.s;
  return s;
}
// 1/d using Newton-Raphson:
// x <- x * (2 - d*x)
E I(E d){
  int i;
  E r={d.n,d.z,d.i,d.s};V;
  E t={};t.d[4001]=1;
  for(i=N-1;i>0;i--)if(d.d[i])break;
  E x={0,0,0,d.s};x.d[N-i]=1;
  d.s^=1;
  for(i=0;i<10;i++)x=M(x,A(t,M(d,x)));
  return x;
}
// Convert expanded number back to regular floating point.
F C(E x){
  long i,j,e,m=0;
  for(i=N-1;i>=0;i--)if(x.d[i])break;
  for(j=0;j<N;j++)if(x.d[j])break;
  if(i>0&x.d[i-53]&(j<i-53|x.d[i-52])){E y={0,0,0,x.s};y.d[i-53]=1;return C(A(x,y));}
  if(i<2978){e=0;for(j=0;j<52;j++)m+=x.d[j+2926]<<j;}
  else if(i<5024){e=i-2977;for(j=0;j<52;j++)m+=x.d[i+j-52]<<j;}
  else x.i=1;
  if(x.z)e=m=0;
  if(x.i){e=2047;m=0;}
  if(x.n)e=m=2047;
  F y;y.k=x.s<<63|e<<52|m;return y;
}
// expand, do op, unexpand
F A(F x,F y){return C(A(R(x),R(y)));}
F S(F x,F y){y.k^=1L<<63;return A(x,y);}
F M(F x,F y){return C(M(R(x),R(y)));}
F D(F x,F y){return C(M(R(x),I(R(y))));}

```

I'm too lazy to remove all the spaces and newlines to get an exact golfed count, but it is about 1500 characters.

---
Tags: code-golf, c, c++, floating-point
---