title: insertspacesbetweenwords

text:
# Question
Title: insertspacesbetweenwords
In this challenge, your input is a string of lower-case letters like this:

```
insertspacesbetweenwords

```

and a dictionary like the that from my other challenge. You may assume that the dictionary file contains only lower-case letters and line-feed characters. Furthermore, the last character in the dictionary file is a line-feed character and the entries are sorted alphabetically.

Write a function that given these two strings, returns a single string containing all possible ways to insert spaces between some of the characters in the input string, such that the words created are all in the dictionary. Each possibility shall be terminated with a line-feed character. Some lines of the output for the example are:

```
insert spaces between words
insert space s between words
insert spaces between word s
insert space s between word s
insert spaces be tween words

```

The order of the output lines doesn't matter.

This is codegolf, the usual scoring rules apply, standard loopholes are verboten.

# Answer
> 5 votes
# Haskell, ~~113 107 105 88 87~~ 86 bytes

Works for empty inputs too (but gives an empty string as output).

```
s!d=unlines[w|w<-map concat$mapM(\c->[[c],[' ',c]])s,all(`elem`lines d).words$w,w>"!"]

```

Defines an infix binary function `!`. Call it like this:

```
"abababbaab" ! "ab\nba\na\nbab\n"

```

Result:

```
"ab ab ab ba ab\nab a bab ba ab\na bab ab ba ab\na ba bab ba ab\n"

```

### Explanation

The idea is to split the left input string `s` into words by inserting spaces in all possible ways, and keep those that consist of words of the dictionary `d`. A leading space is checked by comparing to the string `"!"`.

```
s!d=                           -- Define the string s!d by
 unlines                       -- joining with line-breaks
  [w|w<-                       -- the strings w obtained by
    map concat$                -- concatenating each list of strings
    mapM(\c->[[c],[' ',c]])s,  -- obtained by replacing each letter 'c' of s by
                               -- either "c" or " c",
   all(`elem`lines d).         -- such that only lines of d
    words$w,                   -- occur as words in w, and
   w>"!"]                      -- w is lexicographically larger than "!",
                               -- which here means that w does not begin with a space.

```

# Answer
> 8 votes
# Python 3, 88

```
f=lambda x,w,s=[]:[x or print(*s)]+[x.find(y)or f(x[len(y):],w,s+[y])for y in w.split()]

```

String to split is `x`, the dictionary string is `w`.

The idea is to repeatedly check which strings `y` of the dictionary are a prefix for the current string `x`. The expression `x.find(y)` evaluates to the Falsey `0` only if `x` starts with `y` (substrings not present give `-1`), so the short-circuiting of `or` makes the function recurse down only when the prefixes matches. The prefix is chopped off with `x[len(y):]` and the list of subwords is updated in `s`.

When the whole string `x` has been consumed, we print the subwords `s`, automatically joined by spaces.

---
Tags: code-golf, word-puzzle
---


title: Your Language in a Box

text:
# Question
Title: Your Language in a Box
# Now with BONUS for run-time placement.

Write a program to fill a text box with the identifiers used in your program while keeping your program small. With all the identifiers you have used (excluding those *you* created) in your program, fill a 12x6 box with as many as you can. You get extra points for identifiers that cross over (crossword style), but they can't join end to end.

## Output

Your program should print (to stdout) a 12x6 character box with your packed identifiers and a `#` border. The box should have columns labeled with letter A-L and the rows 1-6 (spaced like the example below). Then print a line for each identifier used. Each line will have the location of the first letter, the identifier itself, and the score. The score is equal to the number of letters in the identifier with a possible '+bonus' added. The identifier gets a 5 point bonus for each letter shared with a crossing identifier. The final line reports 'TOTAL: ' and the sum of the identifier scores. An example output for a possible Python program would look like this:

```
   ABCDEFGHIJKL
  ##############
1 #  pinsert   #
2 #  o         #
3 #  print     #
4 #    not     #
5 #            #
6 #import      #
  ##############
C1 pop 3+5
D1 insert 6
C3 print 5+10
E3 in 2+10
E4 not 3+5
A6 import 6
TOTAL: 55

```

Notes:

* Identifiers can be unattached (like `import` above).
* You cannot join `pop` and `print` inline with `poprint`.
* The string `in` inside `insert` cannot be used. Joining words must be orthogonal.
* Identifiers can be placed next to each other (like `pop` and `insert` above).

Your answer should include your program output with your source code and a title consisting of the language name and your score.

## Score

Your score for the challenge will the the puzzle score squared divided by the size of your source code (in bytes). Eg: The puzzle above with a 300 byte program would score `55*55/300 = 10.08`. Highest score wins.

## Rules

* You can use any identifier in your program that is not defined by you. Keywords, class names, method names, library names, and built-in function names are examples of eligible identifiers.
* EDITED: You may only use standard libraries that are included with the minimum language release. Extended language packages and the use of external libraries (are now) forbidden. The huge range of libraries with extensive lists of identifiers would unbalance this challenge. If you are unsure of how this works with your language, please leave a question in the comments.
* Identifiers must consist of \[a-zA-Z\_\] characters only and have at least 2 characters.
* You may only use each identifier once in the puzzle.
* Identifiers can only be used left to right or downwards.

## Dynamic Bonus!

If your code determines where to place identifiers at run time, the shared letter bonus will be 20 instead of 5. You may list which identifiers will used, but your code must decide where in the box to place them. Your code must also calculate and print the score list. If your placements depend on the *ordering* of the identifier list, hard-coded pairings, or other non-dynamic placement short-cuts, you are not eligible for the Dynamic Bonus.

In the example output above, the puzzle score for a run-time placement program would become 145. Then if the code was 800 bytes, the score would be `145*145/800 = 26.28`.

The Dynamic Bonus is designed to reward clever algorithms instead of static hard-coded solution strings, and compensate for the larger resulting source code size.

EDITS:

* Changed libraries used to only those in the minimum language release.
* Added the dynamic bonus option.

# Answer
> 2 votes
## STATA, 387^2 / 677 = 221.2

I got lazy and just wanted to output something that works before trying to get it with optimal score. I'll probably update it later as I fit more words in, and I'm open to suggestions from anyone that uses STATA (which doesn't seem very popular on CodeGolf). STATA is really good about having a lot of two letter commands/parameters. Also, usually most can be shortened to save characters/fit better (i.e. display can be display, displa, displ, disp, dis, or di). Also, the capture means that it suppresses output and error messages. So the entire while loop has 0 output.

```
cap infile using a,us(b)
cap while _rc>0{
ls
cap ge c=1 if 0<1
so c
egen d=rownonmiss(c),str
regres c d
notes
clist,noh no
li,compress
dec c,g(f)
do a
}
gl e=";;;ABCDEFGHIJKL ;;############## 1;#rownonmissdo# 2;#e;hd;o;notes# 3;#geii;hif_rc;# 4;#r;ls;clist;;# 5;#egen;ailu;;;# 6;#slcompress;;# ;;############## A1;rownonmiss;10+30 K1;do;2+5 H2;notes;5+20 A3;ge;2+5 G3;if;2+5 I3;_rc;3+15 C4;ls;2+10 F4;clist;5+20 A5;egen;4+20 C6;compress;8+20 A1;regres;6+15 C1;while;5+15 F1;noh;3+5 H1;infile;6+25 I1;so;2+10 J1;str;3+15 K1;dec;3+15 D2;dis;3+5 I3;_s;2+10 F4;cap;3+10 G4;li;2+5 B5;gl;2+5 D5;no;2+10 I5;us;2+5 TOTAL:;387"
token $e
forv x=1/34{
dis subinstr(``x'',";"," ",.)_s(0)
}

```

generates

```
   ABCDEFGHIJKL
  ##############
1 #rownonmissdo#
2 #e hd o notes#
3 #geii hif_rc #
4 #r ls clist  #
5 #egen ailu   #
6 #slcompress  #
  ##############
A1 rownonmiss 10+30
K1 do 2+5
H2 notes 5+20
A3 ge 2+5
G3 if 2+5
I3 _rc 3+15
C4 ls 2+10
F4 clist 5+20
A5 egen 4+20
C6 compress 8+20
A1 regres 6+15
C1 while 5+15
F1 noh 3+5
H1 infile 6+25
I1 so 2+10
J1 str 3+15
K1 dec 3+15
D2 dis 3+5
I3 _s 2+10
F4 cap 3+10
G4 li 2+5
B5 gl 2+5
D5 no 2+10
I5 us 2+5
TOTAL: 387

```

# Answer
> 3 votes
# Python, 1342 / 349 = 50.02

If I have understood the rules correctly, this should be a valid submission.

```
from sys import *
stdout.write("""   ABCDEFGHIJKL
  ##############
1 #from   f  i #
2 #  r   not t #
3 #      write #
4 #  s   import#
5 #  y   False #
6 #  stdout    #
  ##############
A1 from 4+5
C1 or 2+5
H1 format 6+25
K1 iter 4+10
G2 not 3+5
G3 write 5+10
C4 sys 3+5
G4 import 6+10
G5 False 5+5
C6 stdout 6+10
TOTAL 134
""".format(not False or iter([])))

```

You can really just keep incrementing your score by adding more identifiers: the size of the program increases linearly (by approx. twice the identifier length), while the score increases approximately by the square of the identifier length. Then the challenge becomes more how to cram most keywords into the square instead of how to write a *short* program to do it.

# Answer
> 0 votes
# Perl, 7282 / 639 = 829.4

Oh well, this is not valid, missed that I have to have the identifiers in my code.

```
#!perl -l
use B::Keywords'@Symbols','@Barewords';
use List::Util shuffle;
srand 45502;
@b=@a=shuffle map{push@{+length},$_;$_}grep/^[a-z]{2,}$/,@Symbols,@Barewords;
$z=$"x12 .$/;$z x=6;
$s=length,$z=~s/ {$s}/$_/&&($_=0)for@a;
$_=$z;$"='|';
sub f{join'',/(.)(?=@_.*(\n))/sg}$_=f".{12}(.)"x5;
s/@a/$v=length$&;$tot+=$v*21;$r.=(map{m!.!;map{$&.$_}1..7}A..L)[@-]." $& $v+".($v*20)."\n";uc$&/ge;
$_=f".{6}(.)"x11;
s/@b/$v=length$&;$b=$&=~y!A-Z!!;$tot+=$v+$b*20;$c=lc$&;$r.=(map{m!.!;map{$_.$&}A..M}1..6)[@-]." $c $v+".($b*20)."\n";uc$&/ige;
$_=$z;
s/
/#
/mg;
s/^/++$l.' #'/mge;
print'   ',A..L,'
  ','#'x14,'
',$_,'  ','#'x14,"
${r}TOTAL: $tot"

```

This requires a perl reflection module (`B::Keywords`). Can be installed on ubuntu with `sudo apt-get install libb-keywords-perl`. With the seed given in the code above it generates the 728 answer:

```
   ABCDEFGHIJKL
  ##############
1 #dumplogforqr#
2 #lcfirstbreak#
3 #socketshmctl#
4 #requiregiven#
5 #lengthgmtime#
6 #getserventdo#
  ##############
B1 uc 2+40
C2 fc 2+40
F3 tr 2+40
G1 gt 2+40
I1 or 2+40
J1 recv 4+80
L4 ne 2+40
A1 dump 4+20
E1 log 3+20
H1 for 3+40
K1 qr 2+0
A2 lcfirst 7+60
H2 break 5+40
A3 socket 6+40
G3 shmctl 6+20
A4 require 7+20
H4 given 5+40
A5 length 6+0
G5 gmtime 6+20
A6 getservent 10+0
K6 do 2+0
TOTAL: 728

```

Note that different versions of perl may have different RNG and different keyword list, but it should be easy to find a seed with a comparable result.

---
Tags: code-challenge, crossword
---


# Question
Title: The number of reachable snake orientations
**This challenge is not about the game Snake.**

Imagine a 2d snake formed by drawing a horizontal line of length `n`. At integer points along its body, this snake can rotate its body by 90 degree. If we define the front of the snake to be on the far left to start with, the rotation will move the back part of the snake and the front part will stay put. By doing repeated rotations it can make a lot of different snake body shapes.

## Rules

1. One part of the snake's body can't overlap another.
2. It has to be possible to reach the final orientation without any parts of the snake's body overlapping in between. Two points that touch are counted as overlapping in this problem.
3. I regard a snake and its reverse as being the same shape.

## Task

> Up to rotation, translation and mirror symmetry, what is the total number of different snake body shapes that can be made?

**Example of a rotation of part of the snakes body.** Imagine `n=10` and the snake is in its start orientation of a straight line. Now rotate at point `4` 90 degrees counter-clockwise. We get the snake from `4` to `10` (the tail of the snake) lying vertically and the snake from `0` to `4` lying horizontally. The snake now has one right angle in its body.

Here are some examples thanks to Martin Büttner.

We start with the horizontal snake.

Now we rotate from position 4.

We end up after the rotation in this orientation.

Now let us consider this orientation of a different snake.

We can now see an illegal move where there would be an overlap caused during the rotation.

## Score

Your score is the largest `n` for which your code can solve the problem in less than one minute on my computer.

When a rotation happens it will move one half of the snake with it. We do have to worry about whether any of this part which is rotated might overlap a part of the snake during the rotation. For simplicity we can assume the snake has width zero. You can only rotate at a particular point in snake up to 90 degrees clockwise of counter clockwise. For, you can never full fold the snake in two as that would have involved two rotations at the same point in the same direction.

## Shapes that can't be made

A simple example of a shape that can't be made is a capital `T`. A more sophisticated version is

(Thank you to Harald Hanche-Olsen for this example)

In this example all the adjacent horizontal lines are 1 apart as are the vertical ones. There is therefore no legal move from this position and as the problem is reversible there is therefore no way to get there from the starting position.

## Languages and libraries

You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.

**My machine** The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.

# Answer
> 5 votes
# Python 3 - provisional score: n=11 (n=13 with PyPy\*)

Since there have been no answers in the first week, here is an example in Python to encourage competition. I've tried to make it reasonably readable so that inefficiencies can be identified easily to give ideas for other answers.

# Approach

* Start with the straight snake and find all the positions that can be legally reached in one move.
* Find all the positions that can be legally reached from those positions, that haven't already been identified.
* Repeat until no more can be found, and return the number of positions found altogether.

# Code

*(now with some doctests and asserts after my incorrect first attempt)*

```
'''
Snake combinations

A snake is represented by a tuple giving the relative orientation at each joint.
A length n snake has n-1 joints.
Each relative orientation is one of the following:

0: Clockwise 90 degrees
1: Straight
2: Anticlockwise 90 degrees

So a straight snake of length 4 has 3 joints all set to 1:

(1, 1, 1)

x increases to the right
y increases upwards

'''

import turtle

def all_coords(state):
    '''Return list of coords starting from (0,0) heading right.'''
    current = (1, 0)
    heading = 0
    coords = [(0,0), (1,0)]
    for item in state:
        heading += item + 3
        heading %= 4
        offset = ((1,0), (0,1), (-1,0), (0,-1))[heading]
        current = tuple(current[i]+offset[i] for i in (0,1))
        coords.append(current)
    return coords

def line_segments(coords, pivot):
    '''Return list of line segments joining consecutive coords up to pivot-1.'''
    return [(coords[i], coords[i+1]) for i in range(pivot+1)]

def rotation_direction(coords, pivot, coords_in_final_after_pivot):
    '''Return -1 if turning clockwise, 1 if turning anticlockwise.'''
    pivot_coord = coords[pivot + 1]
    initial_coord = coords[pivot + 2]
    final_coord = coords_in_final_after_pivot[0]
    initial_direction = tuple(initial_coord[i] - pivot_coord[i] for i in (0,1))
    final_direction = tuple(final_coord[i] - pivot_coord[i] for i in (0,1))
    return (initial_direction[0] * final_direction[1] -
            initial_direction[1] * final_direction[0]
            )

def intersects(arc, line):
    '''Return True if the arc intersects the line segment.'''
    if line_segment_cuts_circle(arc, line):
        cut_points = points_cutting_circle(arc, line)
        if cut_points and cut_point_is_on_arc(arc, cut_points):
            return True

def line_segment_cuts_circle(arc, line):
    '''Return True if the line endpoints are not both inside or outside.'''
    centre, point, direction = arc
    start, finish = line
    point_distance_squared = distance_squared(centre, point)
    start_distance_squared = distance_squared(centre, start)
    finish_distance_squared = distance_squared(centre, finish)
    start_sign = start_distance_squared - point_distance_squared
    finish_sign = finish_distance_squared - point_distance_squared
    if start_sign * finish_sign <= 0:
        return True

def distance_squared(centre, point):
    '''Return the square of the distance between centre and point.'''
    return sum((point[i] - centre[i]) ** 2 for i in (0,1))

def cut_point_is_on_arc(arc, cut_points):
    '''Return True if any intersection point with circle is on arc.'''
    centre, arc_start, direction = arc
    relative_start = tuple(arc_start[i] - centre[i] for i in (0,1))
    relative_midpoint = ((relative_start[0] - direction*relative_start[1])/2,
                         (relative_start[1] + direction*relative_start[0])/2
                         )
    span_squared = distance_squared(relative_start, relative_midpoint)
    for cut_point in cut_points:
        relative_cut_point = tuple(cut_point[i] - centre[i] for i in (0,1))
        spacing_squared = distance_squared(relative_cut_point,
                                           relative_midpoint
                                           )
        if spacing_squared <= span_squared:
            return True

def points_cutting_circle(arc, line):
    '''Return list of points where line segment cuts circle.'''
    points = []
    start, finish = line
    centre, arc_start, direction = arc
    radius_squared = distance_squared(centre, arc_start)
    length_squared = distance_squared(start, finish)
    relative_start = tuple(start[i] - centre[i] for i in (0,1))
    relative_finish = tuple(finish[i] - centre[i] for i in (0,1))
    relative_midpoint = tuple((relative_start[i] +
                               relative_finish[i]
                               )*0.5 for i in (0,1))
    determinant = (relative_start[0]*relative_finish[1] -
                   relative_finish[0]*relative_start[1]
                   )
    determinant_squared = determinant ** 2
    discriminant = radius_squared * length_squared - determinant_squared
    offset = tuple(finish[i] - start[i] for i in (0,1))
    sgn = (1, -1)[offset[1] < 0]
    root_discriminant = discriminant ** 0.5
    one_over_length_squared = 1 / length_squared
    for sign in (-1, 1):
        x = (determinant * offset[1] +
             sign * sgn * offset[0] * root_discriminant
             ) * one_over_length_squared
        y = (-determinant * offset[0] +
             sign * abs(offset[1]) * root_discriminant
             ) * one_over_length_squared
        check = distance_squared(relative_midpoint, (x,y))
        if check <= length_squared * 0.25:
            points.append((centre[0] + x, centre[1] + y))
    return points

def potential_neighbours(candidate):
    '''Return list of states one turn away from candidate.'''
    states = []
    for i in range(len(candidate)):
        for orientation in range(3):
            if abs(candidate[i] - orientation) == 1:
                state = list(candidate)
                state[i] = orientation
                states.append(tuple(state))
    return states

def reachable(initial, final):
    '''
    Return True if final state can be reached in one legal move.

    >>> reachable((1,0,0), (0,0,0))
    False

    >>> reachable((0,1,0), (0,0,0))
    False

    >>> reachable((0,0,1), (0,0,0))
    False

    >>> reachable((1,2,2), (2,2,2))
    False

    >>> reachable((2,1,2), (2,2,2))
    False

    >>> reachable((2,2,1), (2,2,2))
    False

    >>> reachable((1,2,1,2,1,1,2,2,1), (1,2,1,2,1,1,2,1,1))
    False

    '''
    pivot = -1
    for i in range(len(initial)):
        if initial[i] != final[i]:
            pivot = i
            break

    assert pivot > -1, '''
        No pivot between {} and {}'''.format(initial, final)
    assert initial[pivot + 1:] == final[pivot + 1:], '''
        More than one pivot between {} and {}'''.format(initial, final)

    coords_in_initial = all_coords(initial)
    coords_in_final_after_pivot = all_coords(final)[pivot+2:]
    coords_in_initial_after_pivot = coords_in_initial[pivot+2:]
    line_segments_up_to_pivot = line_segments(coords_in_initial, pivot)

    direction = rotation_direction(coords_in_initial,
                                   pivot,
                                   coords_in_final_after_pivot
                                   )

    pivot_point = coords_in_initial[pivot + 1]

    for point in coords_in_initial_after_pivot:
        arc = (pivot_point, point, direction)
        if any(intersects(arc, line) for line in line_segments_up_to_pivot):
            return False
    return True

def display(snake):
    '''Display a line diagram of the snake.

    Accepts a snake as either a tuple:

    (1, 1, 2, 0)

    or a string:

    "1120"

    '''
    snake = tuple(int(s) for s in snake)
    coords = all_coords(snake)

    turtle.clearscreen()
    t = turtle.Turtle()
    t.hideturtle()
    s = t.screen
    s.tracer(0)

    width, height = s.window_width(), s.window_height()

    x_min = min(coord[0] for coord in coords)
    x_max = max(coord[0] for coord in coords)
    y_min = min(coord[1] for coord in coords)
    y_max = max(coord[1] for coord in coords)
    unit_length = min(width // (x_max - x_min + 1),
                      height // (y_max - y_min + 1)
                      )

    origin_x = -(x_min + x_max) * unit_length // 2
    origin_y = -(y_min + y_max) * unit_length // 2

    pen_width = max(1, unit_length // 20)
    t.pensize(pen_width)
    dot_size = max(4, pen_width * 3)

    t.penup()
    t.setpos(origin_x, origin_y)
    t.pendown()

    t.forward(unit_length)
    for joint in snake:
        t.dot(dot_size)
        t.left((joint - 1) * 90)
        t.forward(unit_length)
    s.update()

def neighbours(origin, excluded=()):
    '''Return list of states reachable in one step.'''
    states = []
    for candidate in potential_neighbours(origin):
        if candidate not in excluded and reachable(origin, candidate):
            states.append(candidate)
    return states

def mirrored_or_backwards(candidates):
    '''Return set of states that are equivalent to a state in candidates.'''
    states = set()
    for candidate in candidates:
        mirrored = tuple(2 - joint for joint in candidate)
        backwards = candidate[::-1]
        mirrored_backwards = mirrored[::-1]
        states |= set((mirrored, backwards, mirrored_backwards))
    return states

def possible_snakes(snake):
    '''
    Return the set of possible arrangements of the given snake.

    >>> possible_snakes((1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1))
    {(1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1)}

    '''
    reached = set()
    candidates = set((snake,))

    while candidates:
        candidate = candidates.pop()
        reached.add(candidate)
        new_candidates = neighbours(candidate, reached)
        reached |= mirrored_or_backwards(new_candidates)
        set_of_new_candidates = set(new_candidates)
        reached |= set_of_new_candidates
        candidates |= set_of_new_candidates

    excluded = set()
    final_answers = set()
    while reached:
        candidate = reached.pop()
        if candidate not in excluded:
            final_answers.add(candidate)
            excluded |= mirrored_or_backwards([candidate])

    return final_answers

def straight_derived_snakes(length):
    '''Return the set of possible arrangements of a snake of this length.'''
    straight_line = (1,) * max(length-1, 0)
    return possible_snakes(straight_line)

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    import sys
    arguments = sys.argv[1:]
    if arguments:
        length = int(arguments[0])
    else:
        length = int(input('Enter the length of the snake:'))
    print(len(straight_derived_snakes(length)))

```

# Results

On my machine the longest snake that can be calculated in under 1 minute is length 11 (or length 13 with PyPy\*). This is obviously just a provisional score until we find out what the official score is from Lembik's machine.

For comparison, here are the results for the first few values of n:

```
 n | reachable orientations
-----------------------------
 0 | 1
 1 | 1
 2 | 2
 3 | 4
 4 | 9
 5 | 22
 6 | 56
 7 | 147
 8 | 388
 9 | 1047
10 | 2806
11 | 7600
12 | 20437
13 | 55313
14 | 148752
15 | 401629
16 | 1078746
17 | MemoryError (on my machine)

```

Please let me know if any of these turn out to be incorrect.

If you have an example of an arrangement that should not be able to be unfolded, you can use the function `neighbours(snake)` to find any arrangements reachable in one step, as a test of the code. `snake` is a tuple of joint directions (0 for clockwise, 1 for straight, 2 for anticlockwise). For example (1,1,1) is a straight snake of length 4 (with 3 joints).

# Visualisation

To visualise a snake you have in mind, or any of the snakes returned by `neighbours`, you can use the function `display(snake)`. This accepts a tuple like the other functions, but since it is not used by the main program and therefore does not need to be fast, it will also accept a string, for your convenience.

`display((1,1,2,0))` is equivalent to `display("1120")`

As Lembik mentions in the comments, my results are identical to OEIS A037245 which does not take into account intersections during rotation. This is because for the first few values of n there is no difference - all shapes that do not self-intersect can be reached by folding a straight snake. The correctness of the code can be tested by calling `neighbours()` with a snake that cannot be unfolded without intersection. Since it has no neighbours it will contribute only to the OEIS sequence, and not to this one. The smallest example I am aware of is this length 31 snake that Lembik mentioned, thanks to David K:

`(1,1,1,1,2,1,2,1,1,1,1,1,1,2,1,1,1,2,1,1,2,2,1,0,1,0,1,1,1,1)`

`display('111121211111121112112210101111')` gives the following output:

> **Tip:** If you resize the display window and then call display again, the snake will be fitted to the new window size.

I'd love to hear from anyone who has a shorter example with no neighbours. I suspect that the shortest such example will mark the smallest n for which the two sequences differ.

---

*\*Note that each increment of n takes very roughly 3 times as long, so increasing from n=11 to n=13 requires almost 10 times the time. This is why PyPy only allows increasing n by 2, even though it runs considerably faster than the standard Python interpreter.*

# Answer
> 2 votes
# C++11 - nearly working :)

After reading this article, I collected bits of wisdom from that guy who apparently worked for 25 years on the less complicated problem of counting self-avoiding paths on a square lattice.

```
#include <cassert>
#include <ctime>
#include <sstream>
#include <vector>
#include <algorithm> // sort

using namespace std;

// theroretical max snake lenght (the code would need a few decades to process that value)
#define MAX_LENGTH ((int)(1+8*sizeof(unsigned)))

#ifndef _MSC_VER
#ifndef QT_DEBUG // using Qt IDE for g++ builds
#define NDEBUG
#endif
#endif

#ifdef NDEBUG
inline void tprintf(const char *, ...){}
#else
#define tprintf printf
#endif

void panic(const char * msg)
{
    printf("PANIC: %s\n", msg);
    exit(-1);
}

// ============================================================================
// fast bit reversal
// ============================================================================
unsigned bit_reverse(register unsigned x, unsigned len)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16)) >> (32-len);
}

// ============================================================================
// 2D geometry (restricted to integer coordinates and right angle rotations)
// ============================================================================

// points using integer- or float-valued coordinates
template<typename T>struct tTypedPoint;

typedef int    tCoord;
typedef double tFloatCoord;

typedef tTypedPoint<tCoord> tPoint;
typedef tTypedPoint<tFloatCoord>  tFloatPoint;

template <typename T>
struct tTypedPoint {
    T x, y;

    template<typename U> tTypedPoint(const tTypedPoint<U>& from) : x((T)from.x), y((T)from.y) {} // conversion constructor

    tTypedPoint() {}
    tTypedPoint(T x, T y) : x(x), y(y) {}
    tTypedPoint(const tTypedPoint& p) { *this = p; }
    tTypedPoint operator+ (const tTypedPoint & p) const { return{ x + p.x, y + p.y }; }
    tTypedPoint operator- (const tTypedPoint & p) const { return{ x - p.x, y - p.y }; }
    tTypedPoint operator* (T scalar) const { return{ x * scalar, y * scalar }; }
    tTypedPoint operator/ (T scalar) const { return{ x / scalar, y / scalar }; }
    bool operator== (const tTypedPoint & p) const { return x == p.x && y == p.y; }
    bool operator!= (const tTypedPoint & p) const { return !operator==(p); }
    T dot(const tTypedPoint &p) const { return x*p.x + y * p.y; } // dot product
    int cross(const tTypedPoint &p) const { return x*p.y - y * p.x; } // z component of cross product
    T norm2(void) const { return dot(*this); }

    // works only with direction = 1 (90° right) or -1 (90° left)
    tTypedPoint rotate(int direction) const { return{ direction * y, -direction * x }; }
    tTypedPoint rotate(int direction, const tTypedPoint & center) const { return (*this - center).rotate(direction) + center; }

    // used to compute length of a ragdoll snake segment
    unsigned manhattan_distance(const tPoint & p) const { return abs(x-p.x) + abs(y-p.y); }
};

struct tArc {
    tPoint c;                        // circle center
    tFloatPoint middle_vector;       // vector splitting the arc in half
    tCoord      middle_vector_norm2; // precomputed for speed
    tFloatCoord dp_limit;

    tArc() {}
    tArc(tPoint c, tPoint p, int direction) : c(c)
    {
        tPoint r = p - c;
        tPoint end = r.rotate(direction);
        middle_vector = ((tFloatPoint)(r+end)) / sqrt(2); // works only for +-90° rotations. The vector should be normalized to circle radius in the general case
        middle_vector_norm2 = r.norm2();
        dp_limit = ((tFloatPoint)r).dot(middle_vector);
        assert (middle_vector == tPoint(0, 0) || dp_limit != 0);
    }

    bool contains(tFloatPoint p) // p must be a point on the circle
    {
        if ((p-c).dot(middle_vector) >= dp_limit)
        {
            return true;
        }
        else return false;
    }
};

// returns the point of line (p1 p2) that is closest to c
// handles degenerate case p1 = p2
tPoint line_closest_point(tPoint p1, tPoint p2, tPoint c)
{
    if (p1 == p2) return{ p1.x, p1.y };
    tPoint p1p2 = p2 - p1;
    tPoint p1c =  c  - p1;
    tPoint disp = (p1p2 * p1c.dot(p1p2)) / p1p2.norm2();
    return p1 + disp;
}

// variant of closest point computation that checks if the projection falls within the segment
bool closest_point_within(tPoint p1, tPoint p2, tPoint c, tPoint & res)
{
    tPoint p1p2 = p2 - p1;
    tPoint p1c = c - p1;
    tCoord nk = p1c.dot(p1p2);
    if (nk <= 0) return false;
    tCoord n = p1p2.norm2();
    if (nk >= n) return false;
    res = p1 + p1p2 * (nk / n);
    return true;
}

// tests intersection of line (p1 p2) with an arc
bool inter_seg_arc(tPoint p1, tPoint p2, tArc arc)
{
    tPoint m = line_closest_point(p1, p2, arc.c);
    tCoord r2 = arc.middle_vector_norm2;
    tPoint cm = m - arc.c;
    tCoord h2 = cm.norm2();
    if (r2 < h2) return false; // no circle intersection

    tPoint p1p2 = p2 - p1;
    tCoord n2p1p2 = p1p2.norm2();

    // works because by construction p is on (p1 p2)
    auto in_segment = [&](const tFloatPoint & p) -> bool
    {
        tFloatCoord nk = p1p2.dot(p - p1);
        return nk >= 0 && nk <= n2p1p2;
    };

    if (r2 == h2) return arc.contains(m) && in_segment(m); // tangent intersection

    //if (p1 == p2) return false; // degenerate segment located inside circle
    assert(p1 != p2);

    tFloatPoint u = (tFloatPoint)p1p2 * sqrt((r2-h2)/n2p1p2); // displacement on (p1 p2) from m to one intersection point

    tFloatPoint i1 = m + u;
    if    (arc.contains(i1) && in_segment(i1)) return true;
    tFloatPoint i2 = m - u;
    return arc.contains(i2) && in_segment(i2);
}

// ============================================================================
// compact storage of a configuration (64 bits)
// ============================================================================
struct sConfiguration {
    unsigned partition;
    unsigned folding;

    explicit sConfiguration() {}
    sConfiguration(unsigned partition, unsigned folding) : partition(partition), folding(folding) {}

    // add a bend
    sConfiguration bend(unsigned joint, int rotation) const
    {
        sConfiguration res;
        unsigned joint_mask = 1 << joint;
        res.partition = partition | joint_mask;
        res.folding = folding;
        if (rotation == -1) res.folding |= joint_mask;
        return res;
    }

    // textual representation
    string text(unsigned length) const
    {
        ostringstream res;

        unsigned f = folding;
        unsigned p = partition;

        int segment_len = 1;
        int direction = 1;
        for (size_t i = 1; i != length; i++)
        {
            if (p & 1)
            {
                res << segment_len * direction << ',';
                direction = (f & 1) ? -1 : 1;
                segment_len = 1;
            }
            else segment_len++;

            p >>= 1;
            f >>= 1;
        }
        res << segment_len * direction;
        return res.str();
    }

    // for final sorting
    bool operator< (const sConfiguration& c) const
    {
        return (partition == c.partition) ? folding < c.folding : partition < c.partition;
    }
};

// ============================================================================
// static snake geometry checking grid
// ============================================================================
typedef unsigned tConfId;

class tGrid {
    vector<tConfId>point;
    tConfId current;
    size_t snake_len;
    int min_x, max_x, min_y, max_y;
    size_t x_size, y_size;

    size_t raw_index(const tPoint& p) { bound_check(p);  return (p.x - min_x) + (p.y - min_y) * x_size; }
    void bound_check(const tPoint& p) const { assert(p.x >= min_x && p.x <= max_x && p.y >= min_y && p.y <= max_y); }

    void set(const tPoint& p)
    {
        point[raw_index(p)] = current;
    }
    bool check(const tPoint& p)
    {
        if (point[raw_index(p)] == current) return false;
        set(p);
        return true;
    }

public:
    tGrid(int len) : current(-1), snake_len(len)
    {
        min_x = -max(len - 3, 0);
        max_x = max(len - 0, 0);
        min_y = -max(len - 1, 0);
        max_y = max(len - 4, 0);
        x_size = max_x - min_x + 1;
        y_size = max_y - min_y + 1;
        point.assign(x_size * y_size, current);
    }

    bool check(sConfiguration c)
    {
        current++;
        tPoint d(1, 0);
        tPoint p(0, 0);
        set(p);
        for (size_t i = 1; i != snake_len; i++)
        {
            p = p + d;
            if (!check(p)) return false;
            if (c.partition & 1) d = d.rotate((c.folding & 1) ? -1 : 1);
            c.folding >>= 1;
            c.partition >>= 1;
        }
        return check(p + d);
    }

};

// ============================================================================
// snake ragdoll
// ============================================================================
class tSnakeDoll {
    vector<tPoint>point; // snake geometry. Head at (0,0) pointing right

    // allows to check for collision with the area swept by a rotating segment
    struct rotatedSegment {
        struct segment { tPoint a, b; };
        tPoint  org;
        segment end;
        tArc    arc[3];
        bool extra_arc; // see if third arc is needed

        // empty constructor to avoid wasting time in vector initializations
        rotatedSegment(){}
        // copy constructor is mandatory for vectors *but* shall never be used, since we carefully pre-allocate vector memory
        rotatedSegment(const rotatedSegment &){ assert(!"rotatedSegment should never have been copy-constructed"); }

        // rotate a segment
        rotatedSegment(tPoint pivot, int rotation, tPoint o1, tPoint o2)
        {
            arc[0] = tArc(pivot, o1, rotation);
            arc[1] = tArc(pivot, o2, rotation);
            tPoint middle;
            extra_arc = closest_point_within(o1, o2, pivot, middle);
            if (extra_arc) arc[2] = tArc(pivot, middle, rotation);
            org = o1;
            end = { o1.rotate(rotation, pivot), o2.rotate(rotation, pivot) };
        }

        // check if a segment intersects the area swept during rotation
        bool intersects(tPoint p1, tPoint p2) const
        {
            auto print_arc = [&](int a) { tprintf("(%d,%d)(%d,%d) -> %d (%d,%d)[%f,%f]", p1.x, p1.y, p2.x, p2.y, a, arc[a].c.x, arc[a].c.y, arc[a].middle_vector.x, arc[a].middle_vector.y); };

            if (p1 == org) return false; // pivot is the only point allowed to intersect
            if (inter_seg_arc(p1, p2, arc[0]))
            {
                print_arc(0);
                return true;
            }
            if (inter_seg_arc(p1, p2, arc[1]))
            {
                print_arc(1);
                return true;
            }
            if (extra_arc && inter_seg_arc(p1, p2, arc[2]))
            {
                print_arc(2);
                return true;
            }
            return false;
        }
    };

public:
    sConfiguration configuration;
    bool valid;

    // holds results of a folding attempt
    class snakeFolding {
        friend class tSnakeDoll;
        vector<rotatedSegment>segment; // rotated segments
        unsigned joint;
        int direction;
        size_t i_rotate;

        // pre-allocate rotated segments
        void reserve(size_t length)
        {
            segment.clear(); // this supposedly does not release vector storage memory
            segment.reserve(length);
        }

        // handle one segment rotation
        void rotate(tPoint pivot, int rotation, tPoint o1, tPoint o2)
        {
            segment.emplace_back(pivot, rotation, o1, o2);
        }
    public:
        // nothing done during construction
        snakeFolding(unsigned size)
        {
            segment.reserve (size);
        }
    };

    // empty default constructor to avoid wasting time in array/vector inits
    tSnakeDoll() {}

    // constructs ragdoll from compressed configuration
    tSnakeDoll(unsigned size, unsigned generator, unsigned folding) : point(size), configuration(generator,folding)
    {
        tPoint direction(1, 0);
        tPoint current = { 0, 0 };
        size_t p = 0;
        point[p++] = current;
        for (size_t i = 1; i != size; i++)
        {
            current = current + direction;
            if (generator & 1)
            {
                direction.rotate((folding & 1) ? -1 : 1);
                point[p++] = current;
            }
            folding >>= 1;
            generator >>= 1;
        }
        point[p++] = current;
        point.resize(p);
    }

    // constructs the initial flat snake
    tSnakeDoll(int size) : point(2), configuration(0,0), valid(true)
    {
        point[0] = { 0, 0 };
        point[1] = { size, 0 };
    }

    // constructs a new folding with one added rotation
    tSnakeDoll(const tSnakeDoll & parent, unsigned joint, int rotation, tGrid& grid)
    {
        // update configuration
        configuration = parent.configuration.bend(joint, rotation);

        // locate folding point
        unsigned p_joint = joint+1;
        tPoint pivot;
        size_t i_rotate = 0;
        for (size_t i = 1; i != parent.point.size(); i++)
        {
            unsigned len = parent.point[i].manhattan_distance(parent.point[i - 1]);
            if (len > p_joint)
            {
                pivot = parent.point[i - 1] + ((parent.point[i] - parent.point[i - 1]) / len) * p_joint;
                i_rotate = i;
                break;
            }
            else p_joint -= len;
        }

        // rotate around joint
        snakeFolding fold (parent.point.size() - i_rotate);
        fold.rotate(pivot, rotation, pivot, parent.point[i_rotate]);
        for (size_t i = i_rotate + 1; i != parent.point.size(); i++) fold.rotate(pivot, rotation, parent.point[i - 1], parent.point[i]);

        // copy unmoved points
        point.resize(parent.point.size()+1);
        size_t i;
        for (i = 0; i != i_rotate; i++) point[i] = parent.point[i];

        // copy rotated points
        for (; i != parent.point.size(); i++) point[i] = fold.segment[i - i_rotate].end.a;
        point[i] = fold.segment[i - 1 - i_rotate].end.b;

        // static configuration check
        valid = grid.check (configuration);

        // check collisions with swept arcs
        if (valid && parent.valid) // ;!; parent.valid test is temporary
        {
            for (const rotatedSegment & s : fold.segment)
            for (size_t i = 0; i != i_rotate; i++)
            {
                if (s.intersects(point[i+1], point[i]))
                {
                    //printf("! %s => %s\n", parent.trace().c_str(), trace().c_str());//;!;
                    valid = false;
                    break;
                }
            }
        }
    }

    // trace
    string trace(void) const
    {
        size_t len = 0;
        for (size_t i = 1; i != point.size(); i++) len += point[i - 1].manhattan_distance(point[i]);
        return configuration.text(len);
    }
};

// ============================================================================
// snake twisting engine
// ============================================================================
class cSnakeFolder {
    int length;
    unsigned num_joints;
    tGrid grid;

    // filter redundant configurations
    bool is_unique (sConfiguration c)
    {
        unsigned reverse_p = bit_reverse(c.partition, num_joints);
        if (reverse_p < c.partition)
        {
            tprintf("P cut %s\n", c.text(length).c_str());
            return false;
        }
        else if (reverse_p == c.partition) // filter redundant foldings
        {
            unsigned first_joint_mask = c.partition & (-c.partition); // insulates leftmost bit
            unsigned reverse_f = bit_reverse(c.folding, num_joints);
            if (reverse_f & first_joint_mask) reverse_f = ~reverse_f & c.partition;

            if (reverse_f > c.folding)
            {
                tprintf("F cut %s\n", c.text(length).c_str());
                return false;
            }
        }
        return true;
    }

    // recursive folding
    void fold(tSnakeDoll snake, unsigned first_joint)
    {
        // count unique configurations
        if (snake.valid && is_unique(snake.configuration)) num_configurations++;

        // try to bend remaining joints
        for (size_t joint = first_joint; joint != num_joints; joint++)
        {
            // right bend
            tprintf("%s -> %s\n", snake.configuration.text(length).c_str(), snake.configuration.bend(joint,1).text(length).c_str());
            fold(tSnakeDoll(snake, joint, 1, grid), joint + 1);

            // left bend, except for the first joint
            if (snake.configuration.partition != 0)
            {
                tprintf("%s -> %s\n", snake.configuration.text(length).c_str(), snake.configuration.bend(joint, -1).text(length).c_str());
                fold(tSnakeDoll(snake, joint, -1, grid), joint + 1);
            }
        }
    }

public:
    // count of found configurations
    unsigned num_configurations;

    // constructor does all the work :)
    cSnakeFolder(int n) : length(n), grid(n), num_configurations(0)
    {
        num_joints = length - 1;

        // launch recursive folding
        fold(tSnakeDoll(length), 0);
    }
};

// ============================================================================
// here we go
// ============================================================================
int main(int argc, char * argv[])
{
#ifdef NDEBUG
    if (argc != 2) panic("give me a snake length or else");
    int length = atoi(argv[1]);
#else
    (void)argc; (void)argv;
    int length = 12;
#endif // NDEBUG

    if (length <= 0 || length >= MAX_LENGTH) panic("a snake of that length is hardly foldable");

    time_t start = time(NULL);
    cSnakeFolder snakes(length);
    time_t duration = time(NULL) - start;

    printf ("Found %d configuration%c of length %d in %lds\n", snakes.num_configurations, (snakes.num_configurations == 1) ? '\0' : 's', length, duration);
    return 0;
}

```

## Building the executable

Compile with **`g++ -O3 -std=c++11`**
I use MinGW under Win7 with g++4.8 for "linux" builds, so portability is not 100% guaranteed.

It also works (sort of) with a standard MSVC2013 project

By undefining **`NDEBUG`**, you get traces of algorithm execution and a summary of found configurations.

## Performances

with or without hash tables, Microsoft compiler performs miserably: g++ build is **3 times faster**.

The algorithm uses practically no memory.

Since collision check is roughly in O(n), computation time should be in O(nk<sup>n</sup>), with k slightly lower than 3.
On my i3-2100@3.1GHz, n=17 takes about 1:30 (about 2 million snakes/minute).

I am not done optimizing, but I would not expect more than a x3 gain, so basically I can hope to reach maybe n=20 under an hour, or n=24 under a day.

Reaching the first known unbendable shape (n=31) would take between a few years and a decade, assuming no power outages.

## Counting shapes

A **N** size snake has **N-1** joints.
Each joint can be left straight or bent to the left or right (3 possibilities).
The number of possible foldings is thus 3<sup>N-1</sup>.
Collisions will reduce that number somewhat, so the actual number is close to 2.7<sup>N-1</sup>

However, many such foldings lead to identical shapes.

two shapes are identical if there is either a **rotation** or a **symetry** that can transform one into the other.

Let's define a **segment** as any straight part of the folded body.
For instance a size 5 snake folded at 2nd joint would have 2 segments (one 2 units long and the second 3 units long).
The first segment will be named **head**, and the last **tail**.

By convention we orient the snakes's head horizontally with the body pointing right (like in the OP first figure).

We designate a given figure with a list of signed segment lengths, with positive lengths indicating a right folding and negative ones a left folding.
Initial lenght is positive by convention.

## Separating segments and bends

If we consider only the different ways a snake of length N can be split into segments, we end up with a repartition identical to the compositions of N.

Using the same algorithm as shown in the wiki page, it is easy to generate all the 2<sup>N-1</sup> possible ***partitions*** of the snake.

Each partition will in turn generate all possible foldings by applying either left or right bends to all of its joints. One such folding will be called a **configuration**.

All possible partitions can be represented by an integer of N-1 bits, where each bit represents the presence of a joint. We will call this integer a ***generator***.

## Pruning partitions

By noticing that bending a given partition from the head down is equivalent to bending the symetrical partition from the tail up, we can find all couples of symetrical partitions and eliminate one out of two.
The generator of a symetrical partition is the partition's generator written in reverse bit order, which is trivially easy and cheap to detect.

This will eliminate almost half of the possible partitions, the exceptions being the partitions with "palindromic" generators that are left unchanged by bit reversal (for instance 00100100).

## Taking care of horizontal symetries

With our conventions (a snake starts pointing to the right), the very first bend applied to the right will produce a family of foldings that will be horizontal symetrics from the ones that differ only by the first bend.

If we decide that the first bend will always be to the right, we eliminate all horizontal symetrics in one big swoop.

## Mopping up the palindromes

These two cuts are efficient, but not enough to take care of these pesky palindromes.
The most thorough check in the general case is as follows:

consider a configuration C with a palindromic partition.

* if we *invert* every bend in C, we end up with a horizontal symetric of C.
* if we *reverse* C (applying bends from the tail up), we get the same figure rotated right
* if we both reverse and invert C, we get the same figure rotated left.

We could check every new configuration against the 3 others. However, since we already generate only configurations starting with a right turn, we only have one possible symetry to check:

* the inverted C will start with a left turn, which is by construction impossible to duplicate
* out of the reversed and inverted-reversed configurations, only one will start with a right turn.
That is the only one configuration we can possibly duplicate.

## Eliminating duplicates without any storage

My initial approach was to store all configurations in a huge hash table, to eliminate duplicates by checking the presence of a previously computed symetric configuration.

Thanks to the aforementioned article, it became clear that, since partitions and foldings are stored as bitfields, they can be compared like any numerical value.
So to eliminate one member of a symetric pair, you can simply compare both elements and systematically keep the smallest one (or the greatest one, as you like).

Thus, testing a configuration for duplication amounts to computing the symetric partition, and if both are identical, the folding. No memory is needed at all.

## Order of generation

Clearly collision check will be the most time-consuming part, so reducing these computations is a major time-saver.

A possible solution is to have a "ragdoll snake" that will start in a flat configuration and be gradually bent, to avoid recomputing the whole snake geometry for each possible configuration.

By choosing the order in which configurations are tested, so that at most a ragdoll is stored for each total number of joints, we can limit the number of instances to N-1.

I use a recursive scan of the sake from the tail down, adding a single joint at each level. Thus a new ragdoll instance is built on top of the parent configuration, with a single aditional bend.

This means bends are applied in a sequential order, which seems to be enough to avoid self-collisions in almost all cases.

When self-collision is detected, the bends that lead to the offending move are applied in all possible orders until legit folding is found or all combinations are exhausted.

## Static check

Before even thinking about moving parts, I found it more efficient to test the static final shape of a snake for self-intersections.

This is done by drawing the snake on a grid. Each possible point is plotted from the head down. If there is a self-intersection, at least a pair of points will fall on the same location. This requires exactly N plots for any snake configuration, for a constant O(N) time.

The main advantage of this approach is that the static test alone will simply select valid self-avoiding paths on a square lattice, which allows to test the whole algorithm by inhibiting dynamic collision detection and making sure we find the correct count of such paths.

## Dynamic check

When a snake folds around one joint, each rotated segment will sweep an area whose shape is anything but trivial.
Clearly you can check collisions by testing inclusion within all such swept areas individually. A global check would be more efficient, but given the areas complexity I can't think of any (except maybe using a GPU to draw all areas and perform a global hit check).

Since the static test takes care of the starting and ending positions of each segment, we just need to check intersections with the ***arcs*** swept by each rotating segments.

After an interesting discussion with trichoplax and a bit of JavaScript to get my bearings, I came up with this method:

To try to put it in a few words, if you call

* **C** the center of rotation,
* **S** a rotating segment of arbitrary lenght and direction that does not contain **C**,
* **L** the line prolongating **S**
* **H** the line orthogonal to **L** passing through **C**,
* **I** the intersection of **L** and **H**,

<sub>(source: free.fr)</sub>

For any segment that does not contain **I**, the swept area is bound by 2 arcs (and 2 segments already taken care of by the static check).

If **I** falls within the segment, the arc swept by I must also be taken into account.

This means we can check each unmoving segment against each rotating segment with 2 or 3 segment-with-arc intersections

I used vector geometry to avoid trigonometric functions altogether.
Vector operations produce compact and (relatively) readable code.

Segment-to-arc intersection requires a floating point vector, but the logic should be immune to rounding errors.
I found this elegant and efficient solution in an obscure forum post. I wonder why it is not more widely publicized.

## Does it work?

Inhibiting dynamic collision detection produces the correct self-avoiding paths count up to n=19, so I'm pretty confident the global layout works.

Dynamic collision detection produces consistent results, though the check of bends in different order is missing (for now).
As a consequence, the program counts snakes that can be bent from the head down (i.e. with joints folded in order of increasing distance from the head).

---
Tags: code-challenge, combinatorics, counting
---


title: Factorize it! ...badly

text:
# Question
Title: Factorize it! ...badly
A curious kid uses a program which can factorize a number or an expression into the following form: `p1^e1 * p2^e2 * ... * pn^en` . Exponents equal to `1` are omitted e.g. `360 = 2^3 * 3^2 * 5`

The kid types this output into the program as new input but they don't understand the `^` sign so sometimes they skip one or more of those concatenating the corresponding prime-base and exponent. E.g. `(360 =) 2^3 * 3^2 * 5 => 2^3 * 32 * 5 (= 1280)`

Because of these mistakes she might get a different factorization which they can input again (with skipping 0 or more `^`'s). They repeat the process until the factorization doesn't change anymore (maybe there are no more `^`'s or they copied the output correctly).

You should write a program or function which given an integer `n` (`n>1`) outputs all the possible numbers in increasing order whose factorization could be the one the kid ended up with (including `n`). E.g. for input `16` the possible final factorizations are `(16 =) 2^4, (24 =) 2^3 * 3, (23*3 =) 3 * 23`

## Input details:

* input is a single integer bigger than `1`
* no input will be given which generates output number greater than `2^31-1`
* no input will be given which generates more than `1000` output numbers

## Output details:

* a list of integers in a convenient form for your language

## Examples:

Input =\> Output

```
11    => 11
16    => 16 24 69
360   => 140 360 770 1035 1219 1280 2875 3680
605   => 560 605 840 2415
2048  => 211 2048
58564 => 230 456 1311 2508 9975 12768 13794 20748 58564 114114 322102

```

This is code-golf so shortest program wins.

# Answer
# CJam - 66

```
ria{_{:XmF{1=1>},La\{a1$\f++}/La-{XI{~#}%:*/I{si}%:**}fI}%|}1e3*$p

```

Try it at http://cjam.aditsu.net/

**Explanation:**

```
ria                       read token, convert to integer and wrap in array
{…}1e3*                   repeat 1000 times
    _                     duplicate array
    {…}%                  transform each array item (number) using the block
        :X                store the number in X
        mF                factorize with exponents
        {1=1>},           keep only the factors with exponent > 1
        La\{a1$\f++}/     get all the subsets (*)
        La-               remove the empty subset
        {…}fI             for I = each subset of prime factors with exponent > 1
            XI{~#}%:*/    divide X by all the factors in I
            I{si}%:**     multiply with the primes from I
                          concatenated with their exponents
    |                     add the new numbers to the array, removing duplicates
$                         sort
p                         print the final array

```

(\*) Thanks Martin
> 5 votes

# Answer
# Ruby, 219

To get this started:

```
s=->(x){A=[];def k(x)A<<x
y=Prime.prime_division x;n=0..y.size-1
n.each{|i|n.to_a.combination(i+1).each{|c|c.each{|z|v=y.dup
v[z][1]>1?v[z]=[v[z].join.to_i,1]:next
k v.inject(1){|s,b|s*b[0]**b[1]}}}}end;k x;A.uniq.sort}

```

Creates a function s returning an Array of numbers.

https://ideone.com/iOMGny

Use it like this:

```
#usage

#load from the standard library
require"prime"

#read from stdin and print to stdout
p s.call $<.read.to_i

```

So much fun writing this all of this on a mobile phone...
> 4 votes

# Answer
# Perl, 193 bytes

```
sub R{my($k,$v,@z)=@_;map{$k**$v*$_,$v>1?($k.$v)*$_:()}@z?R(@z):1}
@q=(0+<>);
while($x=pop@q){
my%f;@r=sort{$a<=>$b}@r,$x;
for(2..$x){$x/=$_,$f{$_}++while$x%$_<1}
$_~~@r||push@q,$_ for R%f
}
print"@r"

```

Newlines are just added for readability.

The for loop factorises the next number (`$x`) into a hash (`%f`) of primes and powers. The recursive function (`R`) uses this hash to generate all the numbers that could be attained by removing `^` signs. These numbers are added to a queue (`@q`), and the process is repeated by the outer while loop. Each number from the queue is also kept in a unique, sorted array (`@r`) for printing.
> 3 votes

# Answer
# Pyth, ~~46~~ ~~45~~ 44

```
Su{smmu*/N^T/PdTv+`T`/PdTkdyft/PdT{PdGU^T3]Q

```

Try it here.

Fixed the multiple `^` bug. For instance:

```
Input:  58564
Output: [230, 456, 1311, 2508, 9975, 12768, 13794, 20748, 58564, 114114, 322102]

```

Note that this code relies on a couple of bugfixes to the official compiler that were pushed after the question was asked. However, it does not use any new language features.
> 3 votes

---
Tags: code-golf, number, primes
---


title: Hexadecimal To Decimal

text:
# Question
Title: Hexadecimal To Decimal
Read input of up to 8 characters presented as hexadecimal number and print this number as decimal number. In case that input can not be presented as hexadecimal input it has to print 0

**Rules:**
It is not allowed to use any function that takes or returns strings/characters, beside function that reads string/char from input and return strings/char as-is, function that takes integer and prints that integer to output as decimal number and function (if needed) that takes character and return its ASCII/UNICODE represented integer.

Shortest code wins

Example input
`C0cAc01a`

output
`3234512922`

# Answer
> 7 votes
## Ruby, 74 characters

```
n=0;p gets.gsub(/./).all?{|x|n=n*16+(x>?9?9:0)+x.ord%16;/[\da-f]/i=~x}?n:0

```

Input must be given on STDIN. With command line option `-ln` (counted as 4) it can be shortened to 69 characters.

```
n=0;p chars.all?{|x|n=n*16+(x>?9?9:0)+x.ord%16;/[\da-f]/i=~x}?n:0

```

# Answer
> 4 votes
# Haskell, ~~114~~ 106

```
x#y=16*x+mod y 16
main=getLine>>=print.maybe 0(foldl(#)0).mapM(`lookup`zip"ABCDEF0123456789abcdef"[-6..])

```

Handles input of arbitrary size.

# Answer
> 3 votes
## c -- 181

Input passed on the commandline (one argument only). Relies on K&R function typing defaults. ASCII specific, but has ***no*** reliance on the language or library to know how to parse numbers. Lots of characters given up to specifying a large integer type for this purpose.

```
#include <stdio.h>
main(int c,char**v){unsigned long b=0;char*d=v[1]-1,e;while(e=*++d){
e-=(e>96)?87:(e>64)?55:(e>57)?33:(e>47)?48:0;if(e>15){b=0;break;}
b=b*16+e;}printf("%lu\n",b);}

```

## Ungolfed:

```
#include <stdio.h>
main(int c,char**v){
  unsigned long b=0;
  char*d=v[1]-1,e;
  while(e=*++d){
    if(e>'`')e-=87; // reduce lowercase letters to 10--
    if(e>'@')e-=55; // reduce uppercase letters to 10--
    if(e>'9')e-=33; // reduce punctioation immediately above the
                      // digits so it does not iterfere
    if(e>'/')e-='0';// reduce digits to 0-9
    if(e>15){b=0;break;} // terminate immediately on bad input
    b=b*16+e;
  }
printf("%lu\n",b);}

```

## Validation:

```
$ gcc -o dehex dehex_golfed.c
$ ./dehex C0cAc01a
3234512922
$ ./dehex 1
1
$ ./dehex 1f
31
$ ./dehex g
0
$ ./dehex 1g
1
$ ./dehex 1:2
0

```

# Answer
> 3 votes
## JavaScript, 127 119 characters (thanks trinithis!)

Code-Golfed:

```
function f(n){for(o=i=0,c=1;l=n[i++];)o*=16,l=l.charCodeAt(0),o+=l-(l>96?87:l>64?55:48);return /[\W_g-z]/i.test(n)?0:o}

```

Formatted:

```
function hexToDec(hexChars) {
    //Iterate through hex chars
    for (dec=i=0,count = 1; hexChar = hexChars[i++];) {
        dec *= 16;
        hexCharCode = hexChar.charCodeAt(0);

        //Get the hex number and add it
        hex = hexCharCode;
        if(hexCharCode > 96){
            hex -= 87;//For lower case letters
        } else if (hexCharCode > 64){
            hex -= 55;//For upper case letters
        } else {
            hex -= 48;//For numbers
        }
        dec += hex;
    }

    //Return 0 if invalid, decimal value otherwise
    if(/[\W_g-z]/i.test(hexChars)){
        return 0;
    }
    return dec;
}

```

# Answer
> 2 votes
## Ruby 1.9 (84)

```
gets.chomp!;n=0;p~/[^0-9A-Fa-f]/?0:($_.chars{|c|o=c.ord-48;n=16*n+(o>9?o%32-7:o)};n)

```

If we're allowed to use command line options, this is shortened to 72 characters + 4 for `-ln`:

```
n=0;p~/[^0-9A-Fa-f]/?0:($_.chars{|c|o=c.ord-48;n=16*n+(o>9?o%32-7:o)};n)

```

# Answer
> 2 votes
## Python, 106 characters

```
n=0
e=9e9
for c in raw_input():n=n*16+ord(c)-[e,48,e,55,e,87,e][sum(c>x for x in'/9@F`f')]
print[n,0][n<0]

```

# Answer
> 2 votes
## Scheme, 24 chars

```
(string->number(read)16)

```

I hope this is not considered cheating. If it is:

```
(string->number(string-append "#x"(read)))

```

String to number conversion is mandatory.

In Scheme, if your program is not simple, something is wrong and you should start over until it is made simple. Scheme's power relies on removing restrictions instead of adding features so that the language can be easily extended. Scheme is, with Lisp-derived languages, a programmable programming language.

# Answer
> 1 votes
## D 194 chars

```
void main(string[] a){ulong r;foreach(c;a[1]){switch(c){case '0'..'9':r+=c-'0';break;case 'a'..'f':r+=c-'a'+10;break;case 'A'..'F':r+=c-'A'+10;break;default: write(0); return;}r*=16;}write(r);}

```

I could get some profit by replacing the char literals with the numerals and get thus get rid of the +10 for the `a-f` but this doesn't depend on char encoding though D defines ascii support IIRC

# Answer
> 1 votes
## Mathematica, 64

By the rules:

```
FromDigits[#-If[#<58,48,If[#<97,55,87]]&/@ToCharacterCode@#,16]&

```

# Answer
> 1 votes
# JavaScript, 48 chars

```
function h(n){return 0/0==+("0x"+n)?0:+("0x"+n)}

```

## Formatted + Uncompressed

```
function h(n){
    if(+("0x"+n)==NaN) {
        return 0;
    }
    else {
        return +("0x"+n);
    }
}

```

> The plus operator set before a string converts it into a **decimal** number. So I just had to prepend a "0x" and return 0 if it isn't a valid number to conform the rules.

# Answer
> 0 votes
# Groovy, 74

```
i={it.inject(0){a,v->a*16L+('0123456789abcdef'.indexOf(v.toLowerCase()))}}

```

test case:

```
assert 3234512922 == i('C0cAc01a')

```

Not sure I understood the rules, though.

# Answer
> 0 votes
## Perl, 39 characters

```
print<>=~m/^[[:xdigit:]]{1,8}$/?hex$&:0

```

I kind of feel weird doing it this way in Perl but I believe it follows the rules, since the `hex()` function is a language construct and not a library function. If not...

## Perl, 64 characters

```
print<>!~m/^[[:xdigit:]]{1,8}$/?0:unpack 'L',reverse pack'H8',$&

```

I hope is fine.

# Answer
> 0 votes
**C# - 192 189**

oldschool, uses Console arguments for input, Console.WriteLine() for output. could possibly save a few chars, but can't get rid of most lengthy keywords. Makes evil use of foreach, ternary operator madness, bitwise complement ~ and signedness. Reads any length input and aborts on bad characters (\[^0-9a-fA-F\]).

```
namespace _{class _{static void Main(string[]a){long b=0;foreach(int c in a.Length>0?a[0]:"")b=b<<4|(c-'0'<10?c-'0':c-'A'<6?c-'A'+10:c-'a'<6?c-'a'+10:~0L);System.Console.Write(b<0?0:b);}}}

```

A little deobfuscated (old ver):

```
using System;
namespace CodeGolf
{
    class Program
    {
        static void Main()
        {
            long ret = 0;
            int nextChar;

            while ((nextChar = Console.Read()) != '\r')
            {
                ret <<= 4;
                ret |= nextChar - '0' < 10 ?
                        nextChar - '0' :
                        nextChar - 'A' < 6 ?
                            nextChar - 'A' + 10 :
                            nextChar - 'a' < 6 ?
                                nextChar - 'a' + 10 :
                                ~0L;
            }

            Console.WriteLine(ret < 0 ? 0 : ret);
        }
    }
}

```

Would love to see a C# implementation in hardcore MSIL ;)

# Answer
> 0 votes
# Python, 98 chars

```
print sum(16**n*i for i,n in zip(((ord(c)|32)-[48,87][c>'9']for c in raw_input()[::-1]),range(9)))

```

A one-liner with the nifty bonus that you can use characters \> 'f' for shorthand notation, e.g 'g' counts for 16, 'h' for 17 etc :D

# Answer
> 0 votes
# Mathematica 93 92 chars

```
Fold[16 #1 + #2 &, 0,ToExpression[Characters@n /. Thread@Rule["a"~CharacterRange~"f", 10~Range~15]]]

```

Not as streamlined as Mr.Wizard's answer, but I'll include it for variety. It makes use of no native base conversion routines. There is a shortcoming in my answer: I assumed that characters `a` to `f` would be given in lowercase.

# Answer
> 0 votes
## Perl - 77 chars

```
@h{0..9,'a'..'f'}=0..15;$n+=$h{lc$_}*16**($a++-1)for reverse split//,<>;say$n

```

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


title: Navigate text with arrow keys

text:
# Question
Title: Navigate text with arrow keys
# Background

Most (halfway decent) text editors allow you to navigate text using the arrow keys. Up and down allow you to navigate lines, while left and right move across a line but also wrap around. Furthermore, if the line is shorter than your cursor's X position, the cursor appears at the end of the line but returns to the same X position if you keep moving up or down. Perhaps the following visual explanation will help:

## Examples Of Motion

A simple sample of text could look like this. The cursor will be inserted between two characters in this text, or at an end.

```
-----
---
------

let's put the cursor here:

X-----
---
------

move down (v):

-----
X---
------

move left (<):

-----X
---
------

v

-----
---X
------

v (notice how the X position of the cursor has been maintained)

-----
---
-----X-

^

-----
---X
------

>  (more line wrapping)

-----
---
X------

<

-----
---X
------

^ (the X-position from earlier is no longer maintained due to the left-right motion)

---X--
---
------

```

# The Challenge

Given several lines of ASCII test, find the shortest path from the start location to the end location. The start location is represented by `^` and the end location is represented by `$`, and there will only be one of each. These aren't considered part of the text and don't contribute to that line's "length."

The input will consist of several non-blank lines of text. Output will be a series of `^v<>` characters that show one of the shortest paths. You may optionally assume an additional newline at the end of each, but that is not included as part of the navigable text.

You can write a program or named function. The winner will be the shortest submission, measured in bytes.

## Example I/O

```
^Squares
are
fun$ny

vv<v  (which is better than the naive vv>>>)

Squares
^are
funny$

<vv

Alp$habet^
Song

v<^

Mary had a little lamb,
His fleece was white as snow,
And$ everywhere that ^Mary went,
The lamb was sure to go.

^^>>>>v>>>

$^degenerate case

(no output)

```

# Answer
> 7 votes
# CJam, 139 bytes

Well this took many hours to come to something that feels done. It feels like the time it takes to aggressively optimize CJam code is something larger than *O(n)* with respect to the size of the code...

You can try it online, but for any input for which the best path is at least 6 operations or so, you should probably try it offline with a faster interpreter.

Squished:

```
q_'$-_'^-:T;'^#\'^-'$#W{)2$5Y$5b+{:D[L"_T<W%_N#)_@>N+N#X-Ue>+-"_"W%-U"--2'<t2'>t'++'(')]=~0e>T,e<D3/1$T<N\+W%N#X?:X;}/2$-}g5b{" ^v<>"=}%]W=

```

Expanded and commented:

```
q               "Read the input";
_'$-            "Remove the end marker";
_'^-:T;         "Remove the start marker and save the text";
'^#             "With only the end marker removed, locate the start marker";
\'^-'$#         "With only the start marker removed, locate the end marker";
W               "Initialize the path number to -1";
{               "Do...";
  )               "Increment the path number";
  2$              "Initialize the cursor position to that of the start marker";
  5Y$5b+          "Convert the path number to base 5, then add a leading 5
                   (the leading 5 will act to initialize the column memory)";
  {:D             "For each digit in the path digit string:";
    [               "Begin cases:";
      L               "0: Do nothing";
      "_T<W%_N#)_@>N+N#X-Ue>+-"
"REFS: [   1   ][  2  ][ 3 ]45
                       1: [1] Calculate the distance to the end of the previous
                              line (0 if no such line)
                          [2] Calculate the length of the previous line (0 if
                              no such line)
                          [3] Calculate the distance to move backwards in the
                              previous line as the maximum of the length of the
                              previous line minus the column memory and 0
                          [4] Calculate the total distance to move as the sum
                              of [1] and [3]
                          [5] Subtract [4] from the cursor position";
      _"W%-U"-        "2: Start with a base of the logic of case 1, but with a
                          few operations adjusted.";
      -2'<t2'>t       "   [1] Calculate the distance to the *start* of the
                              *next* line (0 if no such line)
                          [2] Calculate the length of the *next* line (0 if no
                              such line)
                          [3] Calculate the distance to move *forwards* in the
                              *next* line as the *minimum* of the length of the
                              *next line* and *the column memory*
                          [4] Calculate the total distance to move as the sum
                              of [1] and [3]";
      '++             "   [5] *Add* [4] *to* the cursor position";
      '(              "3: Decrement the cursor position";
      ')              "4: Increment the cursor position";
    ]=~             "Execute the case corresponding to the path digit mod 5";
    0e>T,e<         "Clamp the cursor position to [0, text length]";
    D3/             "Check if the path digit is not 0, 1, or 2...";
    1$T<N\+W%N#     "Calculate the current column";
    X?:X;           "If the above check succeeded, update the column memory";
  }/              "End for each";
  2$-             "Subtract the end marker position from the cursor position";
}g              "... While the above subtraction is nonzero";
5b              "Convert the path number to base 5";
{" ^v<>"=}%     "Map each digit in the path string to its operation symbol";
]W=             "Clean up";

```

Overall, this is a pretty straightforward solution. It "executes" the digits of the base-5 representation of a path number that is incremented every iteration, starting with 0, until a path works. The digits `1`-`4` map to the operations up, down, left, and right, and `0` does nothing. The first iteration using a path of just `0` catches the degenerate case. All other paths that contain a `0` are never selected because they're just versions of already-tested paths with added no-ops.

The state is modeled in as minimalistic of a way as possible: the text with start and end markers removed, the cursor position in the text, and the "column memory." Newlines are mostly treated like any other character, so there's no concept of a row, and the cursor position is just an index. This makes moving left and right dead simple, which are just implemented as decrement and increment (with clamping to the size of the text). Moving up and down is a bit trickier, but still manageable.

Code reuse was a pretty vital optimization tactic. Examples of this include:

* Writing the code for moving up in a way such that it's smaller to generate the code for moving down at runtime than to write its own code. This is done by copying the code for moving up and removing/replacing a few characters.
* Updating the "column memory" is done conditionally based on the path digit divided by 3 instead of it being coded into the logic of the operation. This also allows initialization of the column memory by adding a dummy `5` operation to the start of the path string, which also just so happens to use the `0` no-op logic due to circular array indexing and there being only 5 defined operations.

Overall, I'm very happy with how this came out. This is definitely the most work I've put into a code golf answer to date (for something that fits into a tweet!?). The run time is pretty abysmal, though. CJam isn't exactly the fastest language to begin with and this algorithm has a complexity of something like *O(m\*5n)*, where *m* is the size of the input and *n* is the size of the output. Good thing speed doesn't count!

# Answer
> 2 votes
# Python 2: 446

```
Q=input().split('\n');
def g(c):l=[l for l in Q if c in l][0];return Q.index(l),l.index(c)
a,b=g('^');c,d=g('$');Q=map(len,Q);Q[a]-=1;Q[c]-=1
if a==c:d-=b<d;b-=d<b
t=-1
while Q:
 l=[];T=t=t+1;x,y,z=a,b,b
 while T:l+=[T%5]*(T%5>0);T/=5
 for T in l:A=":x+=T+T-3;y=min(Q[x],z)";B="x<len(Q)-1";exec"if "+["","x"+A,B+A,"y:y=z=y-1\nelif x:x-=1;y=z=Q[x]","y<Q[x]:y=z=y+1\nelif "+B+":x+=1;y=z=0"][T]
 if(x,y)==(c,d):print''.join(' ^v<>'[x]for x in l);Q=0

```

Straightforward solution. I'm performing a breadth-first search. `t` iterates over all different paths. I convert `t` into base `5`, but only use the entries, which are nonzero. `1` is up, `2` is down, `3` is left and `4` is right.

I keep the current position of the cursor in 3 variables `x`, `y` and `z`. `x` is the line, `y` the column position, and `z` the 'hidden' column position, if you go up or down and the line is too short. Lots of ifs decide, how the variable change during a move.

Preprocessing is really lengthy, the first 4 lines perform only this task.

The long testcase takes a really long time. The algorithm has a complexity of O(N\*5^N), where N is the length of the shortest solution.

Usage: Input the lines as a single string (lines seperated by `\n`) like `"Alp$habet^\nSong"`

# Answer
> 1 votes
# CJam - 274

No answer yet? Ok, here's one :)

```
qN/_{0:V;{_'^={[UVV]:B;;}{'$={[UV]:E;}{V):V;}?}?}/U):U;}/"^$"f-:,:A;{:X0=[X0=(_A=X2=_@e<\]X?}:U;{:X0=A,(=X[X0=)_A=X2=_@e<\]?}:D;{:X1=[X~;(_]{X0=[X0=(_A=_]X?}?}:L;{:X1=X0=A=={X0=A,(=X[X0=)0_]?}[X~;)_]?}:R;[[BM]]{_{0=2<E=},_{0=1=o0}{;[{"U^DvL<R>"2/\f{[~@1/~@\+@@~\]}~}/]1}?}g;

```

Try it at http://cjam.aditsu.net/ ... except for the Mary example or something of that size, you'll probably want the java interpreter.

---
Tags: code-golf
---