title: Let's build a race car track!

text:
# Question
Title: Let's build a race car track!
**Introduction**

My niece wants to make a race car track. She has wooden parts that fit together to form the track. Each part is square shaped and contains a different shape. I'll use the pipe drawing characters to illustrate:

* : the road that goes vertically
* : the road that goes horizontally
* : the roads that turn in a direction
* : A bridge with an underpass

Curiously, there are no t-junction pieces.

Here's an example of a possible race car track:

```
┌─┐
│ │┌─┐
│ └┼─┘
└──┘

```

The rules for a valid race car track are as follows:

* There can't be any roads that go to nowhere.
* It must form a loop (and all the pieces must be part of the same loop).
* At the bridges / underpasses, you can't turn (so you have to go straight through them).

Unfortunately, the race car track pieces my niece and I have are limited. But we definitely want to use all of them in the track. Write a **program** that, given a list of what pieces are in our inventory, outputs a race car track that uses all of those pieces.

**Input Description**

We'd like the input to come in via STDIN, command line arguments, file reading, or a user input function (such as `raw_input` or `prompt`). The input is comma separated positive integers in the form

```
│,─,┌,┐,└,┘,┼

```

where each of those represent the amount of that particular piece we have. So for instance the input:

```
1,1,1,1,1,1,1

```

would mean that we had one of each piece.

**Output Description**

Output a race car track using the pipe drawing characters listed above. The race car track should use exactly the number of each piece specified in the input -- no more, and no less. There will be at least one valid race car track for every input.

**Example Inputs and Outputs**

Input: `3,5,2,2,2,2,1`

A possible output:

```
┌─┐
│ │┌─┐
│ └┼─┘
└──┘

```

Input: `0,0,1,4,4,1,3`

A possible output:

```
 ┌┐
 └┼┐
  └┼┐
   └┼┐
    └┘

```

# Answer
> 5 votes
# Ruby 664 ~~671 677 687 701~~ (678 bytes)

```
_={│:[1,4],─:[2,8],┌:[4,8],┐:[4,2],└:[1,8],┘:[1,2],┼:[1,4,2,8]}
s=->a,l,b{l==[]&&a==[]?b:(l.product(l).any?{|q,r|q,r=q[0],r[0];(q[0]-r[0])**2+(q[1]-r[1])**2>a.size**2}?!0:(w,f=l.pop
w&&v=!a.size.times{|i|y=_[x=a[i]]
f&&y&[f]==[]||(k=l.select{|p,d|w!=p||y&[d]==[]}
(y-[f]).map{|d|z=[w[0]+(d<2?-1:(d&4)/4),w[1]+(d==2?-1:d>7?1:0)]
g=d<3?d*4:d/4
b[z]?_[b[z]]&[g]!=[]||v=0:k<<[z,g]}
v||r=s[a[0...i]+a[i+1..-1],k,b.merge({w=>x})]
return r if r)}))}
c=eval"[#{gets}]"
r=s[6.downto(0).map{|i|[_.keys[i]]*c[i]}.flatten,[[[0,0],nil]],{}]
h=j=k=l=0
r.map{|w,_|y,x=w
h>x&&h=x
j>y&&j=y
k<x&&k=x
l<y&&l=y}
s=(j..l).map{|_|' '*(k-h+1)}
r.map{|w,p|y,x=w
s[y-j][x-h]=p.to_s}
puts s

```

This is not the shortest program I could come up with, but I sacrificed some brevity for execution speed.

You can experiment with the program here. Note that ideone has an execution time limit, so for inputs consisting of more than about 12 pieces, the program will probably time out.

There's also a test suite for the program. Note that the last two tests are disabled on ideone, due to the time limit mentioned above. To enable these tests, delete the `x_` prefix from their names.

The program finds a solution using Depth-first search; it places pieces one at a time and keeps tracks of loose ends. The search stops when there are no more loose (unconnected) ends and all pieces have been placed.

This is the ungolfed program:

```
N, W, S, E = 1, 2, 4, 8

# given a direction, find the opposite
def opposite (dir)
  dir < 3 ? dir * 4 : dir / 4
end

# given a set of coordinates and a direction,
# find the neighbor cell in that direction
def goto(from, dir)
  y, x = from

  dx = case dir
  when W then -1
  when E then 1
  else 0
  end

  dy = case dir
  when N then -1
  when S then 1
  else 0
  end

  [y+dy, x+dx]
end

CONNECTIONS = {
  ?│ => [N, S],
  ?─ => [W, E],
  ?┌ => [S, E],
  ?┐ => [S, W],
  ?└ => [N, E],
  ?┘ => [N, W],
  ?┼ => [N, S, W, E],
}

BuildTrack =-> {
  piece_types = CONNECTIONS.keys
  piece_counts = gets.split(?,).map &:to_i

  pieces = 6.downto(0).map{|i|piece_types[i]*piece_counts[i]}.join.chars

  def solve (available_pieces, loose_ends=[[[0,0],nil]], board={})

    return board if loose_ends==[] and available_pieces==[]

    # optimization to avoid pursuing expensive paths
    # which cannot yield a result.
    # This prunes about 90% of the search space
    c = loose_ends.map{ |c, _| c }
    not_enough_pieces = c.product(c).any? { |q, r|
      ((q[0]-r[0])**2+(q[1]-r[1])**2) > available_pieces.size**2
    }
    return if not_enough_pieces

    position, connect_from = loose_ends.pop

    return unless position

    available_pieces.size.times do |i|
      piece = available_pieces[i]

      remaining_pieces = available_pieces[0...i] + available_pieces[i+1..-1]

      piece_not_connected_ok = connect_from && CONNECTIONS[piece] & [connect_from] == []
      next if piece_not_connected_ok

      new_loose_ends = loose_ends.select  { |pos, dir|
        # remove loose ends that may have been
        # fixed, now that we placed this piece
        position != pos || CONNECTIONS[piece] & [dir] == []
      }

      invalid_placement = false

      (CONNECTIONS[piece]-[connect_from]).map do |dir|
        new_pos = goto(position, dir)
        new_dir = opposite(dir)

        if board[new_pos]
          if CONNECTIONS[board[new_pos]] & [new_dir] != []
            # do nothing; already connected
          else
            # going towards an existing piece
            # which has no suitable connection
            invalid_placement = true
          end
        else
          new_loose_ends << [new_pos, new_dir]
        end
      end

      next if invalid_placement

      new_board = board.merge({position => piece})

      result = solve(remaining_pieces, new_loose_ends, new_board)
      return result if result
    end
    nil
  end

  def print_board board
    min_x = min_y = max_x = max_y = 0

    board.each do |position, _|
      y, x = position
      min_x = [min_x, x].min
      min_y = [min_y, y].min
      max_x = [max_x, x].max
      max_y = [max_y, y].max
    end

    str = (min_y..max_y).map{|_|
      ' ' * (max_x - min_x + 1)
    }

    board.each do |position, piece|
      y, x = position
      str[y-min_y][x-min_x] = piece
    end
    puts str
  end

  print_board(solve(pieces))
}

```

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


title: XKCD: Keyboard Mash Anomalies

text:
# Question
Title: XKCD: Keyboard Mash Anomalies
Another XKCD inspired competition. This one is based on Keyboard Mash.

Given a input string, identify the anomalous characters, assuming that the majority have been typed on a single row of the standard US QWERTY keyboard. Input strings can contain shifted key strokes, but they will not contain carriage returns (Enter), CTRL/ALT affected characters, spaces, tabs and backspaces (because that would be silly). The number pad will not be considered as part of the keyboard for this challenge.

The challenge is to output the characters that aren't on the same keyboard row as the majority of individual characters in the single string. The output should contain each anomalous character only once and no other characters.

In the case of a equal count of anomalous characters across two or more rows, the tie break is determined in this order:

* Shortest unique list
* Top most row

**Input**

A string through either STDIN, ARGV or a function parameter

**Output**

A string to STDOUT or a function return. It should have each anomalous character only once, but does not need to be ordered.

**Examples**

> **Input:** FJAFJKLDSKF7KFDJ
> **Output:** 7
>
> **Input:** ASDF11111
> **Output:** ASDF
>
> **Input:** lkjrhsDdftkjhrksRjd
> **Output:** rtR
>
> **Input:** }\*3%&2098@$2k234#@$M
> **Output:** }
>
> Topmost row list returned
> **Input:** ASD!@#Vcx
> **Output:** !@#
>
> Shortest unique list returned
> **Input:** ASdf1233qwER
> **Output:** 123
>
> Topmost shortest list returned
> **Input:** 12334QWTTSDFDSXVVBBX
> **Output:** QWT

This is code golf, so shortest entry wins.

# Answer
# CJam, ~~111~~ ~~89~~ ~~88~~ ~~86~~ ~~84~~ 83 bytes

```
la9*~"{}qwertyuiop ;':asdfghjkl ,./<>?zxcvbnm"{_32^}%_'ÿ,^a\S%+{[f&s\e|__|]:,}$0=&

```

Try it online in the CJam interpreter.

### How it works

```
la9*~     e# Push the input 9 times on the stack.

"{}qwertyuiop ;':<STX>asdfghjkl ,./<>?zxcvbnm"

{_32^}%   e# XOR a copy of each character with 32.
_'<DEL>,^ e# Push a string of all ASCII characters that are missing.
a\        e# Wrap it in an array.
S%+       e# Split the string at spaces and concatenate with the array.
{         e# Sort the chunks according to the following:
  [       e#
    f&s   e# Push the string of characters from the input that are in this chunk.
    \e|   e# If the result is empty, replace it with the input.
    __|   e# Push a copy with duplicates removed.
  ]       e# Collect both strings in an array.
  :,      e# Replace each string with its length.
}$        e#
0=        e# Retrieve the minimum.
&         e# Intersect it with the input.

```
> 8 votes

# Answer
# CJam, ~~90 88 86 84~~ 83 bytes

This is just a straight forward implementation.

```
" qwertyuiop[] asdfghjkl;': zxcvbnm<>?,./"_32f^.\_'¦,^\+S%qf{_@--}{},{__&]:,}$0=_&

```

Try it online here . Pastebin
> 8 votes

---
Tags: code-golf
---


title: Visit each drifting tracker

text:
# Question
Title: Visit each drifting tracker
Your job is to replace the battery packs on many floating fish tracking devices in the shortest time. You must leave your base in the base helicopter and visit each tracker once, then return to the base.

Finding the optimum route is known to be hard, but there is an additional difficulty! Each tracker has a drift velocity (which will be assumed to be a constant for the day).

*This is the standard travelling salesman problem with the added challenge of moving nodes. It should be easy to find a valid tour. The primary challenge is in developing an algorithm to find a near-optimal tour. I predict that it will not be possible to find a perfect tour with the current N=300 (but I would love to be proved wrong).*

### Rules

Your program will be supplied with a string of tracker data on STDIN or via a command line argument. You should find a route that visits each tracker exactly once and returns to base. The output should be a white space separated list of tracker ID:time pairs.

* Position is given in Centimetres (cm).
* Time is measured in seconds starting with t=0.
* Velocity is given in cm/sec.
* Each tracker ID is 1 to 8 upper case letters.
* The base with ID "BASE" is located at `(0,0)`.
* All number values for input and output use signed integers.
* The input is one or more white space or slash separated trackers.
* Each tracker will have `ID:x,y,vx,vy` format (eg: `A:566,-344,-5,11`)
* At time t, a tracker will be at `(x+vx*t, y+vy*t)`.
* The helicopter must never exceed 5000 cm/sec speed (180 km/hr).
* The output should be white space separated visits in time order.
* Each visit should be in ID:time format (eg: `A:5723`)
* The last visit in your output must be the base (eg: `BASE:6120`)
* If more than one tracker is at the same position, it takes zero time to move between them.
* The standard loopholes are forbidden.

### Example dataset

```
A:77000,88000,-120,80 B:52000,-12000,0,-230 C:-140000,-23000,-270,110

```

Example non-optimal solution:

```
A:30 B:60 C:120 BASE:160

```

Note that `A:30 B:60 C:120 BASE:130` would be invalid because the helicopter would have to fly at 17268 cm/sec to get back to base in 10 seconds.

### Test dataset

```
AA:-164247,-378265,182,113
AB:-1494514,-385520,-25,80
AC:-744551,832058,-13,-123
AD:-930133,1598806,97,177
AE:-280777,-904936,-48,305
AF:-855362,-10456,-21,-89
AG:880990,154342,175,-100
AH:-319708,-623098,172,-17
AI:620018,-626908,-19,-164
AJ:-990505,164998,18,-120
AK:379998,310955,191,59
AL:-977441,-130531,107,-234
AM:-766893,14659,162,-198
AN:-502564,-95651,261,306
AO:661306,-98839,231,263
AP:-788211,254598,24,-249
AQ:851834,-1004246,-45,75
AR:698289,-965536,-8,-134
AS:-128295,701701,180,-241
AT:1423336,1359408,-6,173
AU:445274,-527619,231,319
AV:358132,-781522,26,-132
AW:736129,807327,0,-137
AX:-174581,-337407,133,180
AY:-1533760,-215500,144,-111
AZ:-383050,82658,221,-14
BA:-1650492,548674,89,-63
BB:54477,-906358,440,181
BC:891003,623700,326,102
BD:-393270,1732108,155,-97
BE:411090,-859170,93,163
BF:554962,-298575,480,-100
BG:-695530,475438,244,283
BH:93622,-958266,153,-127
BI:-403222,389691,323,329
BJ:1585132,98244,-156,71
BK:713912,484912,158,97
BL:-1612876,317391,-5,-131
BM:-725126,-320766,30,-105
BN:-76091,-381451,-172,95
BO:-483752,970905,16,-170
BP:1585890,91873,-173,-19
BQ:-815696,-342359,-64,-121
BR:-129530,-606673,-66,-94
BS:-339974,-561442,-35,271
BT:1277427,1258031,13,-5
BU:1246036,-743826,144,-200
BV:494745,-522944,211,309
BW:776786,586255,6,-146
BX:-847071,-792238,-142,-199
BY:748038,863976,6,-109
BZ:-667112,634959,221,-174
CA:888093,900097,-107,-56
CB:113938,-1031815,-167,134
CC:-626804,504649,2,-151
CD:866724,941177,311,221
CE:-1632084,-1957347,38,116
CF:774874,804277,-4,-152
CG:468675,-239063,437,-141
CH:-1352217,-388519,-86,70
CI:-1006,921538,-6,-179
CJ:-1866469,68979,-1,133
CK:-1036883,1962287,124,-62
CL:760226,858123,478,56
CM:764838,493113,-27,-155
CN:-642231,-387271,48,198
CO:430643,646456,8,-138
CP:268900,-82440,294,-114
CQ:-1518402,-1782748,123,62
CR:5487,980492,-30,-151
CS:-749712,494682,-1,-113
CT:-1144956,124994,84,120
CU:-1855045,-612779,30,-35
CV:416593,-57062,-67,-140
CW:-1970914,-1984034,-27,153
CX:-606767,629298,-49,-144
CY:-792900,-696850,0,-123
CZ:1561820,-450390,37,21
DA:579688,355017,-186,-153
DB:1178674,1247470,-86,-54
DC:483389,-837780,321,27
DD:468021,-992185,20,253
DE:-38126,-386917,270,250
DF:707678,189200,-59,-179
DG:-1428781,1326135,-29,-148
DH:-1943667,1645387,22,140
DI:-399820,626361,29,-132
DJ:-2657,170549,94,-169
DK:-331601,917405,104,157
DL:1965031,350999,158,-114
DM:902640,986090,-66,-140
DN:540679,-544126,15,-121
DO:-524120,411839,-48,-120
DP:-134995,-876166,191,-128
DQ:359872,-991469,-164,-186
DR:-186713,-309507,14,-86
DS:1846879,-585704,133,64
DT:169904,945363,298,70
DU:-218003,-1001110,-70,109
DV:316261,266341,-63,-89
DW:551059,55754,-4,-94
DX:-514965,305796,304,-100
DY:162176,485230,-90,83
DZ:675592,-1508331,119,-20
EA:656886,38516,257,-111
EB:-201090,678936,5,-161
EC:-920170,-503904,-8,158
ED:-728819,-401134,-83,154
EE:-611398,-320235,-5,-102
EF:-612522,-259240,14,-154
EG:662225,-808256,478,165
EH:-468284,-720421,234,316
EI:-958544,-161691,-12,-97
EJ:839898,-631917,-25,-159
EK:745130,598504,-72,132
EL:412250,-456628,13,-104
EM:-737096,374111,172,35
EN:726052,-385153,-45,31
EO:-888906,-495174,24,-170
EP:-518672,-685753,-14,-102
EQ:440153,-211801,-46,-180
ER:464493,-1637507,-3,154
ES:701248,-512422,-33,-83
ET:-795959,426838,-29,-117
EU:307451,978526,445,124
EV:800833,66796,15,-176
EW:-623452,299065,-30,-117
EX:15142,-363812,445,245
EY:-701669,-556515,-8,-136
EZ:-1772225,890097,-140,-104
FA:-948887,-882723,-11,-157
FB:387256,-128751,151,7
FC:1066595,-641933,31,-23
FD:-823274,-812209,-67,-172
FE:923612,536985,21,-123
FF:-886616,-808114,-26,-153
FG:411924,-518931,-7,-138
FH:945677,-1038311,174,-59
FI:913968,81871,-5,-139
FJ:625167,708120,-44,-90
FK:-405348,893926,-10,-93
FL:-58670,415334,170,-155
FM:326285,671439,426,-237
FN:-775332,-81583,4,-164
FO:280520,360899,2,-150
FP:-406095,133747,26,170
FQ:-990214,-342198,30,-112
FR:938869,801354,397,198
FS:-7527,36870,-23,-111
FT:999332,-956212,143,16
FU:-86215,792355,-49,-87
FV:144427,378536,-4,-136
FW:-786438,638084,28,-77
FX:903809,903424,-102,-132
FY:-36812,-126503,16,-159
FZ:-1083903,1001142,-29,-110
GA:857943,-120746,135,-3
GB:545227,-151166,239,127
GC:-356823,674293,106,90
GD:977846,1003667,-53,106
GE:-866551,180253,-1,-170
GF:-688577,289359,-24,-161
GG:-256928,-481626,169,109
GH:590910,829914,25,-170
GI:568114,735446,-34,-172
GJ:1756516,-655660,140,138
GK:-1683894,-1417741,-163,-84
GL:-201976,-703352,201,217
GM:-271187,-836075,-24,-141
GN:809929,793308,70,324
GO:-403617,58364,432,-191
GP:-94316,227063,148,28
GQ:-930345,1587220,-129,-142
GR:-433897,58058,-75,255
GS:-780984,114024,-12,-160
GT:-403102,-1425166,158,-84
GU:-449829,-414404,-27,-125
GV:556480,72387,-34,306
GW:-959629,326929,327,-91
GX:250741,-992373,94,-121
GY:702250,1612852,-41,38
GZ:853191,857773,-62,-105
HA:674500,-225890,7,-152
HB:-1890026,-179534,-23,49
HC:398363,681200,31,-26
HD:-1896372,113239,-51,25
HE:599213,137473,10,-31
HF:-34537,750768,-18,-179
HG:-959544,-430584,-33,-117
HH:1283773,1606578,-8,-80
HI:-866804,108513,180,-74
HJ:765654,115993,23,-22
HK:554000,130015,18,-32
HL:-470089,-407430,38,191
HM:366977,556677,18,-134
HN:175829,545309,29,-146
HO:-263163,-235953,3,-169
HP:727495,567716,6,-135
HQ:121304,-9150,81,-157
HR:-1789095,-471348,-73,-9
HS:-799974,819873,51,-64
HT:-985175,1774422,70,-10
HU:516368,-227142,-33,-117
HV:655503,350605,-6,-92
HW:733506,-1967066,197,-62
HX:1339705,-1227657,-195,44
HY:-384466,-1932882,7,-93
HZ:-394466,-459287,132,95
IA:120512,-1673367,28,-167
IB:1294647,-1112204,35,133
IC:883230,734086,144,54
ID:-95269,435577,30,148
IE:-378105,-1147004,-6,190
IF:366040,-132989,339,-61
IG:-397775,-410802,-1,-84
IH:849353,-181194,-98,45
II:774834,-56456,-177,21
IJ:-441667,576716,-51,-82
IK:-309799,-673582,-34,-99
IL:605784,-903045,-179,103
IM:-379218,-958590,-6,262
IN:982984,947942,212,-28
IO:-477749,-472771,474,44
IP:-1381284,-1273520,131,139
IQ:672901,1298275,-116,150
IR:-816582,-693425,121,-265
IS:809060,-66216,-45,-165
IT:655913,723612,6,-102
IU:70578,-546308,496,219
IV:558122,41452,-20,-103
IW:237612,-1605017,154,170
IX:-1120980,-471873,-181,-134
IY:-1385384,36137,-14,15
IZ:1401932,-1692315,103,115
JA:1339559,1534224,123,46
JB:-963572,-554932,-13,-153
JC:1422496,-213462,-97,-63
JD:-74743,-909157,277,273
JE:-1364398,911720,185,-19
JF:831273,-645419,-61,-147
JG:-308025,-297948,-59,-107
JH:-737466,-424236,419,219
JI:234767,971704,375,89
JJ:-715682,-871436,395,-54
JK:-296198,-466457,11,227
JL:277311,-661418,27,-124
JM:113477,-763303,-61,-142
JN:198929,881316,358,67
JO:864028,-1735917,-168,-162
JP:193352,-46636,12,-171
JQ:-374301,967915,-27,-98
JR:-900576,1585161,-14,-154
JS:-855414,-201048,24,-150
JT:473630,412948,-80,68
JU:-358039,-730839,-18,47
JV:677652,-670825,-63,-146
JW:536063,-734897,-86,57
JX:344532,-594945,143,230
JY:218390,42085,406,-154
JZ:222495,-933383,440,-29
KA:993576,490730,448,13
KB:1383947,-1637102,-146,-175
KC:181730,-314093,-20,47
KD:1400934,502742,-77,-126
KE:1239862,1152873,144,102
KF:-156867,290487,5,-92
KG:947301,958346,-12,-124
KH:-1873578,815339,194,167
KI:1181091,882850,89,-122
KJ:-825910,-452543,369,9
KK:548963,-358292,390,117
KL:-940596,-200000,125,296
KM:463530,905548,-70,-95
KN:-7507,263613,-7,-145
KO:172069,-457358,-40,-113
KP:-206484,-214043,172,-4
KQ:620049,1844897,-158,192
KR:-988657,612294,452,-125
KS:-802234,611144,-34,-178
KT:231136,-858200,123,129
KU:1557166,943150,105,114
KV:-229389,-440910,-71,123
KW:-135216,1346978,15,136
KX:-43852,521638,-38,279
KY:112655,441642,-8,-105
KZ:525746,-216262,8,-124
LA:-985825,-345745,33,187
LB:-839408,-319328,-6,-136
LC:-12208,1899312,-168,149
LD:156476,-902318,69,325
LE:976731,-427696,310,165
LF:-809002,-255961,312,235
LG:-899084,484167,5,57
LH:-748701,426117,256,-21
LI:-711992,148901,-49,24
LJ:-519051,-440262,22,-105
LK:-310550,283589,88,151
LL:244046,-1751273,5,29
LM:1350149,-1524193,-96,-158
LN:-706211,-585853,-63,-122

```

### Verifier

A program similar to the following verifier will be used to check the answers. You can use this program to check your answers before posting.

```
# PPCG: Visiting each drifting tracker
# Answer verifier for Python 2.7
# Usage: python verify.py infile outfile [-v]
# Infile has the given input string. Outfile has the solution string.
# v1.0 First release.

import sys, re
VERBOSE = ('-v' in sys.argv)
fi, fo = sys.argv[1:3]

def error(*msg):
    print ' '.join(str(m) for m in ('ERROR at:',) + msg)
    sys.exit()

indata = open(fi).read().strip()
trackdata = [re.split('[:,]', node) for node in re.split('[ /]', indata)]
trackers = dict((node.pop(0), map(int, node)) for node in trackdata)
shouldvisit = set(trackers.keys() + ['BASE'])

visittexts = open(fo).read().split()
visitpairs = [node.split(':') for node in visittexts]
visits = [(label, int(time)) for label,time in visitpairs]

fmt = '%10s '*5
if VERBOSE:
    print fmt % tuple('ID Time Dist Tdiff Speed'.split())
prevpos = (0, 0)
prevtime = 0
visited = set()
for ID, time in visits:
    if ID in visited:
        error(ID, 'Already visited!')
    tdiff = time - prevtime
    if tdiff < 0:
        error(ID, 'Time should move forward!')
    if ID == 'BASE':
        newpos = (0, 0)
    else:
        if ID not in trackers:
            error(ID, 'No such tracker')
        x, y, vx, vy = trackers[ID]
        newpos = (x+vx*time, y+vy*time)
    if newpos == prevpos:
        dist = speed = 0
    else:
        dist = ((newpos[0]-prevpos[0])**2 + (newpos[1]-prevpos[1])**2) ** 0.5
        if tdiff == 0:
            error(ID, 'Helicopters shouldn\'t teleport')
        speed = dist / tdiff
        if speed > 5000:
            error(ID, 'Helicopter can\'t fly at', speed)
    if VERBOSE:
        print fmt % (ID, time, int(dist), tdiff, int(speed))
    visited.add(ID)
    prevpos = newpos
    prevtime = time

if ID != 'BASE':
    error(ID, 'Must finish at the BASE')
if visited != shouldvisit:
    error((shouldvisit - visited), 'Not visited')

print 'Successful tour in %u seconds.' % time

```

### Scoring

Your score will be your final time in seconds. Lower is better. The winner will be the answer with the fastest time on the test dataset after the return to base. In the result of a tie, the earliest entry will win.

Please post solutions with a "Language, Score: NNN" title, the code, and the output solution string (with several visits per line prefered).

# Answer
# Python, Score: ~~20617~~ 17461

I do not have much experience with these types of problems and don't really know what the best known methods are, but I used a method which I've had moderate success with in the past and I'm interested to see how it compares to other answers.

```
from __future__ import division
from math import *
import itertools

class Visitor:
    def __init__(self,data):
        self.trackers = self.parse(data)
        self.weights = {}
        avg = 0
        for key in self.trackers:
            x,y,vx,vy = self.trackers[key]
            w = hypot(vx,vy)**2
            self.weights[key] = w
            avg += w
        avg /= len(self.trackers)
        for key in self.weights:
            self.weights[key] += avg

    def parse(self,data):
        result = {}
        for line in data.split('\n'):
            id,vars = line.split(':')
            x_str,y_str,vx_str,vy_str = vars.split(',')
            result[id] = (int(x_str),int(y_str),int(vx_str),int(vy_str))
        return result

    def convert(self,path,final):
        result = ""
        total_time = 0
        for (id,time) in path:
            total_time+=time
            result += "%s:%s "%(id,total_time)
        return result + "BASE:"+str(final)

    def time_to(self,target,begin,offset=0):
        bx,by,dx,dy = begin
        tx,ty,vx,vy = target
        bx+=dx*offset
        by+=dy*offset
        tx+=vx*offset
        ty+=vy*offset

        t = 0
        for inter in [1000,100,20,10,4,1]:
            speed = 5001
            while speed > 5000:
                t += inter
                cx,cy = tx+vx*t,ty+vy*t
                speed = hypot(bx-cx,by-cy)/t
            if speed == 5000:
                return time
            t -= inter
        return t+1

    def path_initial(self):
        print 'Creating Initial Path'
        path = []
        tracks = self.trackers.copy()
        remaining = self.trackers.keys()
        px,py = 0,0
        distance = 0

        def score(id):
            if len(remaining) == 1:
                return 1
            t = self.time_to(tracks[id],(px,py,0,0))
            all_times = [self.time_to(tracks[id],tracks[k],t) for k in remaining if k != id]
            return t*len(all_times)/sum(all_times)/self.weights[id]

        while remaining:
            print "\t{0:.2f}% ".format(100-100*len(remaining)/len(tracks))
            next = min(remaining,key=score)
            t = self.time_to(tracks[next],(px,py,0,0))
            path.append((next,t))
            for k in tracks:
                ix,iy,ivx,ivy = tracks[k]
                tracks[k] = (ix+ivx*t,iy+ivy*t,ivx,ivy)
            px,py = tracks[next][:2]
            remaining.remove(next)

        return path

    def path_time(self,ids):
        path = []
        total_time = 0
        tracks = self.trackers.copy()
        px,py = 0,0
        distance = 0
        for i in ids:
            t = self.time_to(tracks[i],(px,py,0,0))
            path.append((i,t))
            total_time += t
            for k in tracks:
                ix,iy,ivx,ivy = tracks[k]
                tracks[k] = (ix+ivx*t,iy+ivy*t,ivx,ivy)
            px,py = tracks[i][:2]
        return path,total_time+int(hypot(px,py)/5000+1)

    def find_path(self,b=4):
        initial = self.path_initial()
        current_path,current_time = self.path_time([c[0] for c in initial])
        pos = None
        last_path = None
        last_time = None

        count = 1
        while last_path != current_path:
            print 'Pass',count
            best_path,best_time = [c[0] for c in current_path],current_time
            for i in range(len(current_path)-b):
                print "\t{0:.2f}% ".format(100*i/(len(current_path)-b))
                sub = best_path[i:i+b]
                for s in itertools.permutations(sub):
                    new = best_path[:]
                    new[i:i+b]=s
                    npath,ntime = self.path_time(new)
                    if ntime < best_time:
                        best_path = new
                        best_time = ntime

            last_path,last_time = current_path,current_time
            current_path,current_time = self.path_time(best_path)
            count += 1
        return self.convert(current_path,current_time)

import sys
in_fname,out_fname = sys.argv[1:3]
with open(in_fname) as infile:
    visitor = Visitor(infile.read())
s = visitor.find_path()
print s
with open(out_fname,"w") as file:
    file.write(s)

```

Firstly note that this always tries to maximize the speed between nodes, getting as close to 5000 cm/s as an integral value allows. I don't know if this is necessarily optimal, but removing a degree of freedom obviously makes things much simpler.

The initial step is to create an path by simply choosing one target after another. In this decision each target is weighted negatively by how far the target is from the current position and weighted positively by the average distance from the target to all the remaining possible nodes. This way it tries to go for targets that are closer to it *relative* to other nodes.

Once it has created an initial path, it loops through it, taking every consecutive `b` nodes and testing the new path time for every permutation of these nodes.\* It repeats this process until doing so makes no change to the path.

\*The default value of `b` is `4`, however the value given as my score is my result for running it with `b=6`. I may run it with higher values and update my score accordingly later.

**Edit:**

I made a small modification to the deciding process of the initial path which now weights faster targets as higher priority. This seems to be a very significant improvement.

---

To run it simply use

```
visit.py infile.txt outfile.txt

```

(I would also suggest using `pypy` or something as it does take some time to run)

Example output:

```
FS:8 JY:58 CP:86 FB:110 IF:113 CG:149 BF:173 KK:179 BV:209 AU:218 IU:276 KC:314 EX:319 DE:340 IO:414 EH:445 BS:475 HZ:482 HL:514 JH:528 KJ:563 EE:577 EF:584 CN:601 LF:634 AM:645 GS:680 KL:693 GE:705 AP:725 HI:734 GW:775 CX:828 KR:836 EM:858 LH:871 BZ:890 IJ:896 BG:945 BO:959 FK:970 JQ:984 KX:1049 CR:1061 BI:1078 CI:1089 ID:1117 HF:1128 AN:1191 DX:1211 KF:1213 AZ:1238 KN:1257 GO:1324 HQ:1338 JP:1351 LD:1387 JD:1407 EQ:1424 BB:1500 JZ:1580 DC:1621 EG:1733 LE:1813 BJ:1901 KD:1911 FM:1934 AO:1977 CL:2152 KU:2195 FR:2206 CD:2270 KE:2282 EU:2333 JI:2380 JN:2412 DB:2436 DT:2450 GN:2553 AT:2646 JA:2708 BC:2860 KA:2988 DL:3098 GJ:3165 DS:3201 EA:3353 AG:3385 GA:3418 GB:3504 KI:3543 IN:3638 IC:3708 BK:3737 AK:3811 KG:3854 BY:3882 JX:3920 GL:3988 AA:4007 DD:4018 CO:4040 GI:4053 HM:4059 IH:4063 GG:4072 HN:4100 KP:4156 EN:4164 CM:4195 FL:4212 AS:4229 DW:4250 IV:4267 DJ:4302 DF:4314 AH:4338 HU:4352 EL:4393 ER:4403 HX:4419 FG:4447 JL:4464 JV:4487 AV:4506 AI:4518 JF:4531 EJ:4567 DP:4589 GX:4610 AR:4619 BH:4649 JJ:4760 IW:4839 EV:4861 FI:4900 JC:4919 KT:4984 BW:5001 HP:5014 HV:5041 HK:5058 HE:5061 GH:5075 BP:5082 CF:5094 AW:5110 IT:5132 DM:5160 GZ:5172 FJ:5204 FX:5211 AX:5298 HC:5315 GP:5358 BE:5441 HJ:5450 FE:5490 IB:5592 CZ:5649 FT:5756 IZ:5804 FH:5877 BU:5992 HW:6080 DZ:6256 GT:6431 LM:6552 KB:6630 IA:6652 IR:6739 JO:6832 HY:6887 DQ:6994 FA:7071 FF:7093 FD:7148 BX:7271 GK:7480 IX:7617 EZ:7938 HD:8064 HB:8115 CH:8125 GQ:8176 AB:8241 DG:8277 BN:8347 IY:8397 FZ:8437 CB:8446 JR:8512 II:8576 BA:8613 IL:8625 DU:8650 AC:8687 CS:8743 CC:8817 AJ:8864 EW:8898 DO:8919 ET:8942 AF:8981 KS:9021 DA:9028 EI:9035 GF:9077 JG:9101 FQ:9133 BR:9154 LB:9193 FN:9225 GU:9235 JS:9249 IK:9251 EP:9261 EY:9308 CY:9314 EO:9370 GM:9407 JM:9422 AL:9536 HO:9650 FY:9731 IS:9782 DN:9847 HA:9859 KZ:9922 LL:9985 ES:10014 FO:10056 FV:10106 KY:10182 DI:10215 DV:10263 EB:10340 CQ:10376 DR:10419 AY:10454 IG:10532 BM:10559 CV:10591 LJ:10594 KO:10616 JB:10820 LN:10903 HG:10947 BQ:10988 BL:11100 CU:11140 CE:11235 FU:11380 JU:11397 FW:11419 KM:11448 JW:11479 CA:11549 HS:11594 AQ:11709 IP:11813 JE:11964 HH:12033 BD:12095 BT:12223 GC:12376 LK:12459 DK:12611 KH:12690 AD:12887 GV:12938 KQ:13265 LC:13452 DH:13597 GR:13635 IQ:13748 AE:13763 KW:13967 JK:14080 IM:14145 LA:14232 EK:14290 FP:14344 GD:14395 GY:14472 CT:14532 IE:14650 EC:14771 DY:14807 CJ:14966 ED:15002 CW:15323 HR:15546 LI:15913 KV:16117 JT:16227 LG:16249 HT:16450 CK:16671 FC:17080 BASE:17461

```
> 4 votes

# Answer
# Python 3, score = 21553

The program uses a naive greedy approach. It always calculates where should it go to catch a tracker (any of them) in the shortest time possible. Runs in a couple seconds.

```
import re

class tracker:
    def __repr__(s):
        return str([s.id,s.x,s.y,s.vx,s.vy])

def dist2(e,t):
    return (e.x+t*e.vx-x)**2+(e.y+t*e.vy-y)**2

def closest(x,y,t,tr):
    tp=0
    while 1:
        min_dist2,min_ind=min((dist2(e,t+tp),ind) for ind,e in enumerate(tr))
        if min_dist2<(tp*5000)**2:
            be=tr[min_ind]
            return be.x+(t+tp)*be.vx,be.y+(t+tp)*be.vy,min_ind,t+tp
        tp+=1

tr=[] #x,y,vx,vy,id
with open('tracklist') as f:
    for l in f.read().split():
        a=tracker()
        a.id,data=l.split(':')
        a.x,a.y,a.vx,a.vy=[int(s) for s in data.split(',')]
        tr+=[a]
x,y,gx,gy=0,0,0,0
t=0
r=[] #id,time
while tr:
    x,y,ti,t=closest(x,y,t,tr)
    r+=[(tr[ti].id,t)]
    #print(len(tr),t,tr[ti].id)
    del tr[ti]
    if not tr and r[-1][0]!='BASE':
            a=tracker()
            a.id,a.x,a.y,a.vx,a.vy='BASE',0,0,0,0
            tr+=[a]
print(*[re[0]+':'+str(re[1]) for re in r])

```

Route:

```
FS:8 DJ:34 KN:53 GP:70 KF:89 LK:119 BI:149 IJ:181 DI:195 GC:218 EB:247 AS:272 KX:281 HF:301 FU:320 CI:348 CR:362 DK:420 JQ:443 FK:459 BO:475 BG:531 BZ:549 CX:567 KR:586 FW:600 KS:622 LG:638 CS:674 ET:694 GW:719 GF:738 LI:747 AP:769 HI:778 GS:797 KL:812 GE:818 AJ:841 AF:878 LA:903 EI:919 EC:942 AL:953 JS:962 ED:982 FN:990 AM:1026 CN:1028 HL:1061 BS:1078 KV:1094 BN:1105 JK:1119 JH:1127 HZ:1162 EH:1172 DR:1186 HO:1205 KJ:1228 JG:1231 IG:1249 AE:1261 IM:1284 JU:1294 IK:1322 DU:1336 IE:1353 GM:1386 JJ:1421 CB:1444 BR:1472 AH:1511 KO:1546 IL:1594 FG:1611 KT:1631 EL:1636 JW:1645 DD:1671 BE:1685 ES:1706 DN:1732 AI:1765 JV:1770 JF:1802 AQ:1815 EJ:1827 JZ:1880 HX:1916 AR:1976 IW:2005 ER:2027 GX:2045 BH:2054 AV:2087 JL:2118 DP:2166 JM:2229 DQ:2297 GT:2338 LL:2398 IA:2481 JO:2533 KB:2646 LM:2682 HW:2735 DZ:2861 FH:2975 BU:3027 IZ:3034 FT:3137 DC:3170 IB:3193 FC:3242 GO:3285 JC:3319 IO:3339 CP:3382 IF:3442 EA:3444 BB:3459 AG:3484 GA:3518 KD:3574 FE:3601 JD:3616 BP:3629 HJ:3651 BW:3662 HP:3673 HE:3698 HV:3701 HK:3704 DX:3720 CM:3731 FL:3755 EN:3776 DW:3784 IV:3799 KP:3824 FO:3857 FV:3892 KC:3899 DV:3911 II:3933 KY:3934 HN:3978 GG:4004 IH:4016 HM:4021 GI:4027 CO:4039 AZ:4056 AA:4073 GL:4096 GH:4115 CF:4131 AW:4145 IT:4162 DM:4185 GZ:4193 FX:4221 FJ:4229 LH:4250 AX:4272 LD:4289 HC:4312 CA:4340 LF:4376 DB:4444 AN:4505 GD:4548 GV:4616 BD:4660 EK:4681 ID:4755 FP:4831 DY:4845 JE:4885 CT:4943 JR:4995 FZ:5087 BA:5131 IY:5189 AB:5227 CH:5265 HB:5312 HD:5358 EZ:5433 CJ:5598 GQ:5642 DG:5705 AC:5877 DO:5960 EW:5980 CC:6018 IP:6026 DA:6055 AY:6124 EE:6135 BM:6156 LJ:6197 EF:6236 GU:6256 EP:6283 CQ:6313 EY:6319 CY:6334 EO:6357 JB:6420 LN:6456 HG:6495 BQ:6512 CE:6546 CU:6636 BL:6694 CW:6822 HR:6908 IX:7087 GK:7239 BX:7438 FD:7558 FF:7615 FA:7640 LB:7784 FQ:7826 CV:7955 FY:8018 JP:8058 IS:8090 KZ:8136 HQ:8177 EV:8210 HA:8254 FI:8340 HU:8471 DF:8495 EQ:8587 HY:8799 IR:8932 KG:9512 BY:9523 EM:9703 HH:9763 BT:9850 JX:9973 BK:10091 IC:10129 AK:10203 GB:10350 GJ:10436 IN:10463 DS:10577 DL:10789 JY:11049 FM:11146 CG:11213 BF:11363 KA:11783 EG:11886 CL:11966 IU:12107 EU:12210 EX:12271 FR:12418 CD:12652 AO:12901 AU:12976 BV:13022 DE:13154 KE:13262 KU:13303 JA:13366 DT:13620 JN:13804 LE:13831 BC:13879 JI:13914 KK:14134 FB:14869 CZ:14975 KI:15161 CK:15670 HT:15870 GY:15992 JT:16216 BJ:16275 HS:16636 KM:16813 KW:17719 AD:17965 AT:18082 KH:18226 GN:18841 DH:19723 IQ:19760 GR:19948 KQ:20117 LC:20351 BASE:21553

```
> 3 votes

---
Tags: code-challenge, path-finding
---


title: Fibonacci domino tiling

text:
# Question
Title: Fibonacci domino tiling
There's classic combinatorial result that the number of ways to tile a `2*n` strip by `1*2` dominoes is the nth Fibonacci number. You goal is to print all the tilings for a given `n`, drawn with dashes and vertical lines like these 8 tilings for `n=5`:

```
|————
|————

——|——
——|——

|||——
|||——

————|
————|

||——|
||——|

|——||
|——||

——|||
——|||

|||||
|||||

```

You are to provide a program or named function that take `n` as input and prints the required output. Fewest bytes wins.

**Input**

A number `n` between `1` and `10` inclusive via STDIN or function input.

**Output**

Print every possible domino tilings of the `2*n` strip, drawn horizontally. The tilings may be in any order, but each should appear exactly once. They must be separated by a blank line.

A vertical domino is made of two vertical bars (`|`) and a horizontal domino is made of two em dashes (). You may use hyphens (`-`) in place of em dashes to stay in ASCII.

You can do anything with whitespace as long as the printed output looks the same.

# Answer
> 5 votes
# C, 106

**Golfed version**

```
f(n){
  for(int i,h=n*2<<n;h--;(i/3|i/3*2)-i||(putchar(i>>h%n&1?45:124),h%n||puts(h%(n*2)?"":"\n")))
    i=h/2/n;
}

```

**Original version**

```
i,j,n;
main(){
  scanf("%d",&n);
  for(i=1<<n;i--;)if((i/3|i/3*2)==i){
    for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("");
    for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("\n");
  }
}

```

**How it works**

The variable `i` runs from `1<<n-1` down to 0, producing all possible binary numbers with `n` digits. 0 encodes for `|` and 1 encodes for `-`. We are interested in numbers that contain 1's in pairs. Obviously such numbers are divisible by 3.

When a number is divided by 3, the original number can be recovered by multiplying the result by 2 and adding it to itself (effectively mutliplying by 3.) Most numbers will require a carry, but when the process is carried out on the numbers of interest, no carry is required, so in these cases only, OR can be used instead of addition. This is used to test for the numbers of interest, as they are the only ones where the expression `i/3|i/3*2` returns the original value of `i`. See example below.

`1111`=15 ---\> `0101`=5 ---\> `1111`=15 (valid, `0101|1010`==`0101+1010`)

`1001`=9 ---\> `0011`=3 ---\> `0111`=7 (invalid, `0011|0110` != `0011+0110`)

The test value is always equal or less than the original value. As numbers that are not multiples of 3 also return a number less than the original when divided by 3 then multipled by 3, the test gives the desired FALSE on these numbers too.

In the original version a couple of loops in `j` are used to scan through the bits of `i` and produce the output. In the golfed version a single `for` loop is used, in which `h` runs through all numbers from `(n*2)*(1<<n)-1` down to 0. Values of `i` are generated by `h/2/n`. The variable `j` is no longer used, as the equivalent quantity is obtained from `h%n`. The use of `n*2` enables both lines to be printed from the same loop, with some nifty multiplexing in the `puts` statement to print either one or two newlines at the end of the row.

Note that the meat of this is in the increment position of the `for()` bracket and therefore gets executed *after* the `i=h/2/h`.

**Sample output n=6:**

```
$ ./a
6
------
------

----||
----||

--|--|
--|--|

--||--
--||--

--||||
--||||

|----|
|----|

|--|--
|--|--

|--|||
|--|||

||----
||----

||--||
||--||

|||--|
|||--|

||||--
||||--

||||||
||||||

```

# Answer
> 3 votes
# CJam, ~~33~~ 27 bytes

```
LN{_'|f+@"——"f++}ri*\;{_N}/

```

*Thanks to @jimmy23013 for golfing off 6 bytes!*

Try it online!

### Background

This is an iterative implementation of a recursive algorithm:

The possible tilings for *n* can be obtained by adding a vertical domino to the possible tilings for *n - 1* and two horizontal dominos to the possible tilings for *n - 2*.

This way, the number of tilings for *n* is the sum of the numbers of tilings for *n - 1* and *n - 2*, i.e., the *nth* Fibonacci number.

### How it works

```
LN                                " A:= [''] B:= ['\n']                         ";
  {             }ri*              " Repeat int(input()) times:                  ";
   _'|f+                          "   C = copy(B); for T ∊ C: T += '|'          ";
              @                   "   Swap A and B.                             ";
               "——"f+             "   for T ∊ B: T += "——"                      ";
                     +            "   B = C + B                                 ";
                        \;        " Discard A.                                  ";
                          {_N}/   " for T ∊ B: print T, T + '\n'                ";

```

### Example run

```
$ alias cjam='java -jar cjam-0.6.2.jar'

$ cjam domino.cjam <<< 3
|||
|||

——|
——|

|——
|——

$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done1
2
3
5
8
13
21
34
55
89

```

# Answer
> 2 votes
# CJam, ~~42~~ 37 bytes

```
3li:L#,{3b"——|"2/f=s}%{,L=},_&{N+_N}/

```

I've counted the dashes as one byte each since the question allows to replace them with ASCII hyphens.

Try it online.

# How it works

To obtain all possible tilings of **2 × L**, we iterate over all non-negative integers **I \< 3L**, making even digits in base 3 correspond to horizontal dominos and odd digits to vertical ones.

Since each **I** has **L** or less digits in base 3, this generates all possible ways of covering the **2 × L** strip. All that's left is to filter out the coverings that are bigger or smaller than **2 × L** and print the remaining coverings.

```
3li:L#,      " Read an integer L from STDIN and push A := [ 0 1 ... (3 ** N - 1) ].       ";
{            " For each integer I in A:                                                   ";
  3b         " Push B, the array of I's base 3 digits.                                    ";
  "——|"2/    " Push S := [ '——' '|' ].                                                    ";
  f=         " Replace each D in B with S[D % 2] (the modulus is implicit).               ";
  s          " Flatten B.                                                                 ";
}%           " Collect the result in an array R.                                          ";
{,L=},       " Filter R so it contains only strings of length L.                          ";
_&           " Intersect R with itself to remove duplicates.                              ";
{N+_N}/      " For each string T in B, push (T . '\n') twice, followed by '\n'.           ";

```

# Example run

```
$ cjam domino.cjam <<< 3
|——
|——

——|
——|

|||
|||

$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done
1
2
3
5
8
13
21
34
55
89

```

# Answer
> 2 votes
# Haskell, 89 bytes

```
f(-1)=[]
f 0=[""]
f n=map('|':)(f$n-1)++map("--"++)(f$n-2)
g=unlines.(>>= \x->[x,x,""]).f

```

`f` is a function that given a number returns a list of one lines of all the possible Fibonacci tilings of length n possible. it doesn't matter that it returns one line, because both lines of all tilings are the same.

`f` works by calling recursively on `n-1` and `n-2` and adding `"|"` and `"--"` (respectively) to the strings.

`g` is the function that answers the questions. it basically calls `f` on the input, doubles every string so that it would show two lines and joins them all by newlines.

**example output:**

```
*Main> putStrLn $ g 5
|||||
|||||

|||--
|||--

||--|
||--|

|--||
|--||

|----
|----

--|||
--|||

--|--
--|--

----|
----|

```

# Answer
> 2 votes
# JavaScript (E6) 102

Generate configurations from bit sequences, 0 -\> '--' and 1 -\> '|'.

```
F=n=>{
  for(i=0;(j=++i)<2<<n;s.length==1+n&&console.log('\n'+s+s))
    for(s='\n';j>1;j>>=1)s+=j&1?'|':'--';
}

```

**Test** In firefox/firebug console

```
F(5)

```

*Output*

```
|----
|----

--|--
--|--

----|
----|

|||--
|||--

||--|
||--|

|--||
|--||

--|||
--|||

|||||
|||||

```

# Answer
> 1 votes
# Haskell: 109 bytes

This is a translation of the well-known Haskell one-liner for lazily computing the sequence of Fibonacci numbers:

```
b=map.map.(++)
w=zipWith
z=w(++)
s=["\n"]:["|\n"]:z(b"--"s)(b"|"$tail s)
f=sequence_.map putStrLn.(w z s s!!)

```

The main sequence of tiling strings, ungolfed:

```
dominos = [""] : ["|"] : zipWith (++) ("--" `before` dominos) ("|" `before` tail dominos)
    where before = map . map . (++)

```

And the Fibonacci one-liner for comparison:

```
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

```

Usage example:

```
$ ghci fibtile
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( fibtile.hs, interpreted )
Ok, modules loaded: Main.
*Main> f 5
----|
----|

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

*Main>

```

# Answer
> 1 votes
# Cobra - 176

Can't wait till I've finished the Cobra golfing package.

```
def m(n)
    for t in.f(n),print t+t
def f(n,x='')as String*
    if x.length<n,for i in.f(n,x+'-').toList+.f(n,x+'|').toList,yield i
    else if not'-'in x.replace('--',''),yield x+'\n'

```

# Answer
> 1 votes
# J - 54 char

Function taking `n` as argument on the right.

```
0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2$,:)&.>'';,'|')

```

The main root of this golf is the `(];'--'&,"1@[,'|',"1])&>/`. This takes a list of tilings of length (N-2) and (N-1), and returns a list of tilings of length (N-1) and N. This is the standard Fibonacci recurrence, à la linear algebra. `];` returns the right list as the new left (as there is no change). `'--'&,"1@[` adds `--` tiles to the left list, while `'|',"1]` adds `|` tiles to the right list, and those together are the new right list.

We iterate that over and over `n` times (that's the `@[&0`) and start with the empty tiling and the single tiling of length 1. Then we return the first of the pair with `0{::`. Meaning, if we run it zero times, we just return the first i.e. the empty tiling. If we run it `n` times, we calculate up to the `n` and (`n`+1) pair, but discard the latter. It's extra work but less characters.

The `(1 2$,:)` is something J has to do in order to make the tilings in the lists easily extendable. We make the left starting list be a 1-item list of a 2-row matrix of characters, each row having length 0. The right starting list is the same, but has the rows be of length 1, filled with `|`. Then, we add the new tiles to each row, and append the lists of matrices when we're joining the two sets of tilings together. It's a simple application of a concept J calls rank: essentially manipulating the dimensionality of its arguments, and implicitly looping when necessary.

```
   0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2$,:)&.>'';,'|')5
----|
----|

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

```

Try it for yourself at tryj.tk.

# Answer
> 1 votes
# Python 3: 70 bytes

```
f=lambda n,s="\n":n>0and f(n-1,"|"+s)==f(n-2,"--"+s)or n or print(s*2)

```

Recursively builds all possible strings `s` representing one row of dominos, which are duplicated and printed. Starting `s` as the newline character makes the blank line happen automatically.

The `==` between the two calls for `f` is just to perform both function calls. These usually return `None` because they just print, and `==` is one of few operators defined for `None`.

The `and`s and `or`s are to produce the right short-circuiting behavior to reproduce the `if`s and `else`s of the ungolfed code.

**Ungolfed:**

```
def f(n,s="\n"):
 if n==-1:pass
 elif n==0: print(s*2)
 else: f(n-1,"|"+s);f(n-2,"--"+s)

```

# Answer
> 1 votes
# Retina, 44 bytes

*Note: Retina is younger than this challenge.*

```
+`([-|]*)11(1*#)
$1|1$2$1--$2
1
|
.*?#
$0$0#

```

Takes input in unary with a trailing newline.

Each line should go to its own file and `#` should be changed to newline in the file. This is impractical but you can run the code as is as one file with the `-s` flag, keeping the `#` markers (and changing the newline to `#` in the input too). You can change the `#`'s back to newlines in the output for readability if you wish. E.g.:

```
> echo 1111# | retina -s fib_tile | tr # '\n'
||||
||||

||--
||--

|--|
|--|

--||
--||

----
----

```

Method:

* Starting from the input we swap every line with two other: one with the first `1` change to `|` and one with the first two `1`'s changed to `--`. We do this until we have lines with at least two `1`'s.
* When there are only single `1`'s left we changed those to `|`'s.
* We double each line and add an extra newline to it and we get the desired output.

---
Tags: code-golf, math, ascii-art, combinatorics, tiling
---


title: Matchstick Equations

text:
# Question
Title: Matchstick Equations
Your task in this challenge is to analyize a given "Matchstick Equation" like this one...

... and to find out whether it can be turned into a valid equation by rearranging the matches. If so, you are to output the least number of moves to do so and the resulting equation.

## Input

The input is a String that can be read from STDIN, taken as a function argument or even be stored in a file. It is an equation that represents a matchstick arrangement and can be described using the following EBNF:

```
input = term, "=", term ;
term = number | (term, ("+" | "-"), term) ;
number = "0" | (numeralExceptZero , {numeral}) ;
numeralExceptZero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
numeral = "0" | numeralExceptZero ;

```

An example for a valid input would be `3+6-201=0+0+8`.

## Task

Consider the following illustration where each matchstick has a number assigned:

We now map each input symbol to the corresponding matchstick positions as follows:

```
0 ↦ 1,2,3,4,5,6
1 ↦ 4,5
2 ↦ 2,3,5,6,8
3 ↦ 3,4,5,6,8
4 ↦ 1,4,5,8
5 ↦ 1,3,4,6,8
6 ↦ 1,2,3,4,6,8
7 ↦ 4,5,6
8 ↦ 1,2,3,4,5,6,8
9 ↦ 1,3,4,5,6,8
- ↦ 8
+ ↦ 8,10
= ↦ 7,9

```

Each input formula can be turned into a matchstick arrangement. For example, the equation "45+6=92" becomes

where unused matchsticks are greyed out. Your task is to find out the least number of matchsticks that have to be rearranged in order to make the equation valid.

## Output

We distinguish between three possible cases:

* If the input is not valid (i.e. it doesn't satisfy the above EBNF), output whatever you want.
* Otherwise, if there are ways to turn the equation into a valid one by rearranging the matchsticks, you have to output *both* the minimum number of rearrangements *and* the corresponding equation. Just as the input, the outputted equation must also satisfy the given EBNF. In the above example, the correct output would be `1` and `46+6=52`. If there are multiple possibilities for the resulting equation, output any of them.
* Otherwise (so if the input is valid but there is no way to make the equation true), you have to output `-1`.

## Details

* You are not allowed to remove or to add matches. That means, if the input is built of `n` matchsticks, the output must also consist of exactly `n` matchsticks.
* "Empty" matchstick-blocks are only allowed at the end and the beginning of an equation, not in the middle. So, for example, turning `7-1=6` into `7 =6-1` by simply removing `-1` from the left side and adding it on the right side with just 3 matchstick rearrangements is not allowed.
* Since I don't really see the mapping from numbers to matchstick positions as an interesting part of this challenge, for a plus of **20 bytes**, you may either

+ access a file in which the mapping `(number/operation ↦ matchstick positions)` is stored in any reasonable way, or
    + if your programming language supports a `Map` datatype, assume that you have access to a map that is preinitialized with the `(number/operation ↦ matchstick positions)`-mapping. This map may for example look like that: `{(0,{1,2,3,4,5,6}),(1,{4,5}),(2,{2,3,5,6,8}),(3,{3,4,5,6,8}), ..., (-,{8}),(+,{8,10}),(=,{7,9})}`

## Examples

**Input:** `1+1=3`**Output:** `1` and `1+1=2`

**Input:** `15+6=21`**Output:** `0` and `15+6=21`

**Input:** `1=7`**Output:** `-1`

**Input:** `950-250=750`**Output:** `2` and `990-240=750`

**Input:** `1-2=9`**Output:** `1` and `1+2=3`

**Input:** `20 + 3=04`**Output:** anything

## Winner

This is , so the shortest correct answer (in bytes) wins. The winner will be chosen one week after the first correct answer is posted.

# Answer
> 6 votes
# Javascript, 1069 Bytes

### I've tested it with quite a few test equations and it seems to work all of the time now...

```
function w(t){function B(c,f){d=(c.length>f.length?f:c).split("");e=(c.length>f.length?c:f).split("");longer=Math.max(d.length,e.length);if(0!==d.length&&0!==e.length){c=[];for(x in d)for(y in c[x]=[],e)c[x][y]=1<y-x?-1:function(c,n){r=0;for(j in n)-1<c.indexOf(n[j])&&r++;return c.length+n.length-2*r}(a[d[x]],a[e[y]]);return v=function(f,n){for(var h=f.length-2;0<=h;h--)c[n.length-1][h]+=c[n.length-1][h+1];for(h=f.length-2;0<=h;h--)for(var q=0;q<n.length-1;q++)1>=h-q&&(c[q][h]+=-1==c[q][h+1]?c[q+1][h+1]:Math.min(c[q+1][h+1],c[q][h+1]));return c[0][0]/2}(e,d)}return-1}a=[[1,2,3,4,5,6],[4,5],[2,3,5,6,8],[3,4,5,6,8],[1,4,5,8],[1,3,4,6,8],[1,2,3,4,6,8],[4,5,6],[1,2,3,4,5,6,8],[1,3,4,5,6,8]];a["+"]=[8,0];a["-"]=[8];a["="]=[7,9];a[" "]=[];l=0;p=[];u=[];r=/^([1-9]\d*|0)([+-]([1-9]\d*|0))*=([1-9]\d*|0)([+-]([1-9]\d*|0))*$/;b=/(=.*=|[+=-]{2,}|^[+=-])/;if(!t.match(r))return-1;g=function(c,f,t){if(0===t&&f.match(r)&&eval(f.replace("=","==")))c.push(f);else for(var n in a)t>=a[n].length&&" "!=n&&!(f+n).match(b)&&g(c,f+n,t-a[n].length)};g(p,"",function(c){m=0;for(var f in c)m+=a[c[f]].length;return m}(t.split("")));for(var z in p)k=B(t,p[z]),u[k]||(u[k]=[]),u[k].push(p[z]);for(var A in u)return[A,u[A]];return-1}

```

Well this is my first time ever submitting an answer, so I don't see myself winning. This is basically a brute force method to figure out all answers and then it grabs and returns the smallest ones in an array. with the first argument being the length and the second being an array with the outputs.

if the input is "1-2=9" the output is \[1,\["1+2=3","7-2=5"\]\]

and here is the uncompressed code:

```
function ms(s) {
a=[[1,2,3,4,5,6],[4,5],[2,3,5,6,8],[3,4,5,6,8],[1,4,5,8],[1,3,4,6,8],[1,2,3,4,6,8],[4,5,6],[1,2,3,4,5,6,8],[1,3,4,5,6,8]];
a["+"] = [8, 0];
a["-"] = [8];
a["="] = [7, 9];
a[" "] = [];
l = 0;
p = [];
u = [];
r = /^([1-9]\d*|0)([+-]([1-9]\d*|0))*=([1-9]\d*|0)([+-]([1-9]\d*|0))*$/;
b = /(=.*=|[+=-]{2,}|^[+=-])/;
if (!s.match(r)) return -1;
function f(g,h)
{
    d=(g.length>h.length?h:g).split('');
    e=(g.length>h.length?g:h).split('');
    longer=Math.max(d.length, e.length);
    if(0!==d.length&&0!==e.length)
    {
        g=[];
        for(x in d)
        {
            g[x]=[];
            for(y in e)
            {
                g[x][y]=(y-x>1)?-1:function(g, h){r=0;for(j in h)if(g.indexOf(h[j])>-1)r++;return g.length+h.length-2*r;}(a[d[x]],a[e[y]]);
            }
        }
        v=function(d,e)
        {
        for(var y=d.length-2;y>=0;y--) g[e.length-1][y]+=g[e.length-1][y+1];
        for(var y=d.length-2;y>=0;y--)
            for(var x=0;x<e.length-1;x++)
                if(y-x<=1)
                    g[x][y]+=g[x][y+1]==-1?g[x+1][y+1]:Math.min(g[x+1][y+1], g[x][y+1]);
        return g[0][0]/2}(e,d)
        return v
    }
    return -1;
}
g=function(n, s, i){if (i===0 && s.match(r) && eval(s.replace('=','=='))){n.push(s);return;}for (var c in a) if(i>=a[c].length && c!=" " && !(s+c).match(b)) g(n, s+c, i-a[c].length);};
g(p, "", function(q){m=0;for(var t in q)m+=a[q[t]].length;return m}(s.split('')));
for (var i in p)
{
    k=f(s, p[i]);
    if (!u[k]) u[k] = [];
    u[k].push(p[i]);
}
for (var q in u) return [q, u[q]];
return -1;
}

```

Warning: Don't do equations like 950-250=750 it uses ~45 Matchsticks and because this code uses brute force it will cause javascript to hang.

# Answer
> 1 votes
# Perl, 334

Fairly fast as long as the solution is reachable in 1 or 2 moves. When there is no solution you are up for a long wait even in the smallest case of `1=7`.

```
#!perl -p
@y=map{sprintf"%010b",$_}63,24,118,124,89,109,111,56,127,125,64,192,768;
$y{$z{$y[$c++]}=$_}=$y[$c]for 0..9,qw(- + =);
$"="|";$l=s/./$y{$&}/g;$x{$_}=1;for$m(0..y/1//){
last if$_=(map"$m $_",grep{s/@y/$z{$&}/g==$l&&/^\d.*\d$/&!/\D\D/&!/\b0\d/&y/=//==1&&eval s/=/==/r}keys%x)[0];
$_=-1;s/0/"$`1$'"=~s!1!$x{"$`0$'"}=1!ger/eg for keys%x}

```

Example:

```
$ time perl ~/matchstick.pl <<<950-250=750
2 990-250=740

real    0m39.835s
user    0m39.414s
sys 0m0.380s

```

This will not find solutions that change the length of the equasion like `11=4` -\> `2 11=11`, but I am not sure it this would be allowed.

---
Tags: code-golf
---


title: Solve the Magic Hexagon

text:
# Question
Title: Solve the Magic Hexagon
A magic hexagon is a hexagon where every row and every diagonal add up to the same value. In this case the value is 38. Each number from 1 to 19 must be used exactly once.

This image shows a solution but I want a program that derives this result.

Your challenge is to solve the magic hexagon as fast as possible. You must derive the result yourself, no hard-coding.

# Answer
## C++

Uses some macros to enumerate the possible values. (A-S, assigned lexicographically in the problem image.) `m` is a bitmask of values that have been used so far.

```
#include <stdio.h>
#define LOOP(V) for(int V=1;V<20;V++){if(m&1<<V){m&=~(1<<V);
#define ENDLOOP(V) m|=1<<V;}}
#define SET(V,e) int V=e;if(m&1<<V){m&=~(1<<V);
#define UNSET(V) m|=1<<V;}
int main() {
  int m=1048574;
  LOOP(A);
  LOOP(B);
  SET(C,38-A-B);
  LOOP(D);
  SET(H,38-A-D);
  LOOP(G);
  SET(L,38-C-G);
  LOOP(E);
  SET(F,38-D-E-G);
  LOOP(I);
  SET(M,38-B-E-I);
  SET(Q,38-H-M);
  LOOP(J);
  SET(N,38-C-F-J-Q);
  SET(R,38-D-I-N);
  SET(S,38-Q-R);
  SET(P,38-L-S);
  SET(K,38-B-F-P);
  SET(O,38-M-N-P);
  printf("%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d\n",A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S);
  UNSET(O);
  UNSET(K);
  UNSET(P);
  UNSET(S);
  UNSET(R);
  UNSET(N);
  ENDLOOP(J);
  UNSET(Q);
  UNSET(M);
  ENDLOOP(I);
  UNSET(F);
  ENDLOOP(E);
  UNSET(L);
  ENDLOOP(G);
  UNSET(H);
  ENDLOOP(D);
  UNSET(C);
  ENDLOOP(B);
  ENDLOOP(A);
}

```

Runs in 30msec and generates the following:

```
3 17 18 19 7 1 11 16 2 5 6 9 12 4 8 14 10 13 15
3 19 16 17 7 2 12 18 1 5 4 10 11 6 8 13 9 14 15
9 11 18 14 6 1 17 15 8 5 7 3 13 4 2 19 10 12 16
9 14 15 11 6 8 13 18 1 5 4 10 17 7 2 12 3 19 16
10 12 16 13 4 2 19 15 8 5 7 3 14 6 1 17 9 11 18
10 13 15 12 4 8 14 16 2 5 6 9 19 7 1 11 3 17 18
15 13 10 14 8 4 12 9 6 5 2 16 11 1 7 19 18 17 3
15 14 9 13 8 6 11 10 4 5 1 18 12 2 7 17 16 19 3
16 12 10 19 2 4 13 3 7 5 8 15 17 1 6 14 18 11 9
16 19 3 12 2 7 17 10 4 5 1 18 13 8 6 11 15 14 9
18 11 9 17 1 6 14 3 7 5 8 15 19 2 4 13 16 12 10
18 17 3 11 1 7 19 9 6 5 2 16 14 8 4 12 15 13 10

```

The 4th line is the example solution.
> 7 votes

# Answer
So this somewhat ugly code crashes spectacularly in the REPL (its own words!), but compiles and executes fine.

Uppercase letters indicate values, I pick from the set to iterate over them. Lowercase letters are generated. z = 38 - X - Y for example, and e = 38 - X - A. With e and J we get n and so on.

```
/**
    X Y z
   A B c d
  e f g h i
   J k l m
    n o p
*/
object MagicHexagon extends App {

  val set =(1 to 19)toSet

  // row 1
  for (x <- set;
    y <-(set - x);
    z = 38 - y - x;
    dummy <- ((set - x - y) -- (set - x - y - z));
    rest1=(set - x - y - z);
    a <- rest1;
    e = 38 - x - a;
    dummy2 <- ((rest1 - a) -- (rest1 - a - e));
    j <- rest1 - a - e;
    n = 38 - e - j;
    dummy3 <- ((rest1 - a - e - j) -- (rest1 - a - e - j - n));
    b <- rest1 - a - e - n;
    rest2=(rest1 - a - e - j - n - b);
    f = 38 - y - b - j;
    dummy4 <- ((rest2) -- (rest2 - f));
    c <- rest2 - f;
    d = 38 - a - b - c;
    dummy5 <- ((rest2 - f - c) -- (rest2 - f - c - d));
    i = 38 - z - d;
    dummy6 <- ((rest2 - f - c - d) -- (rest2 - f - c - d - i));
    rest3 = rest2 - f - c - d - i;
    g <- rest3;
    h = 38 - e - f - g - i;
    dummy7 <- ((rest3 - g) -- (rest3 - g - h));
    k = 38 - z - c - g - n;
    dummy8 <- ((rest3 - g - h) -- (rest3 - g - h - k));
    o = 38 - a - f - k;
    rest4 = (rest3 - g - h - k - o);
    dummy9 <- ((rest3 - g - h - k) -- rest4);
    m = 38 - y - c - h;
    dummyA <- (rest4 -- (rest4 - m));
    p = 38 - i - m;
    dummyB <- (rest4 - m) -- (rest4 - m - p);
    l = 38 - j - k - m;
    dummyC <- (rest4 - m - p) -- (rest4 - m - p - l);
    buf = List( List("  ",x,y,z), List(" ",a,b,c,d), List("",e,f,g,h,i), List(" ",j,k,l,m), List("  ",n,o,p))) {
       println (buf.map (_.mkString ("", ", ", "")).mkString ("\n"))
      println ()
    }
}

```

The dummy-variables are a kind of hack to allow the loop to terminate prematurely if a generated value doesn't match one of the left values from the set, especially 0 or negative values must be avoided.

Result:

```
scala MagicHexagon
  , 10, 12, 16
 , 13, 4, 2, 19
, 15, 8, 5, 7, 3
 , 14, 6, 1, 17
  , 9, 11, 18

  , 10, 13, 15
 , 12, 4, 8, 14
, 16, 2, 5, 6, 9
 , 19, 7, 1, 11
  , 3, 17, 18

  , 9, 11, 18
 , 14, 6, 1, 17
, 15, 8, 5, 7, 3
 , 13, 4, 2, 19
  , 10, 12, 16

  , 9, 14, 15
 , 11, 6, 8, 13
, 18, 1, 5, 4, 10
 , 17, 7, 2, 12
  , 3, 19, 16

  , 3, 19, 16
 , 17, 7, 2, 12
, 18, 1, 5, 4, 10
 , 11, 6, 8, 13
  , 9, 14, 15

  , 3, 17, 18
 , 19, 7, 1, 11
, 16, 2, 5, 6, 9
 , 12, 4, 8, 14
  , 10, 13, 15

  , 18, 11, 9
 , 17, 1, 6, 14
, 3, 7, 5, 8, 15
 , 19, 2, 4, 13
  , 16, 12, 10

  , 18, 17, 3
 , 11, 1, 7, 19
, 9, 6, 5, 2, 16
 , 14, 8, 4, 12
  , 15, 13, 10

  , 16, 19, 3
 , 12, 2, 7, 17
, 10, 4, 5, 1, 18
 , 13, 8, 6, 11
  , 15, 14, 9

  , 16, 12, 10
 , 19, 2, 4, 13
, 3, 7, 5, 8, 15
 , 17, 1, 6, 14
  , 18, 11, 9

  , 15, 13, 10
 , 14, 8, 4, 12
, 9, 6, 5, 2, 16
 , 11, 1, 7, 19
  , 18, 17, 3

  , 15, 14, 9
 , 13, 8, 6, 11
, 10, 4, 5, 1, 18
 , 12, 2, 7, 17
  , 16, 19, 3

```

Runs in 17s on 7y'o' Laptop.
> 1 votes

# Answer
It takes 121 seconds to run and is incredibly inefficient.

Any tips to improve efficiency would be appreciated instead of down votes.

## C#

```
static void Main(string[] args)
    {
        DateTime time = DateTime.Now;
        int n1 = 0, n2 = 0, n3 = 0, n4 = 0, n5 = 0, n6 = 0, n7 = 0, n8 = 0, n9 = 0, n10 = 0, n11 = 0, n12 = 0, n13 = 0, n14 = 0, n15 = 0, n16 = 0, n17 = 0, n18 = 0, n19 = 0;

            List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
            List<int> c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19;

            c1 = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };

            for (int x1 = 0; x1 < c1.Count; x1++ )
            {
                n1 = c1[x1];
                c2 = c1.Select(i => i).ToList();
                c2.Remove(n1);
                for (int x2 = 0; x2 < c2.Count; x2++)
                {
                    n2 = c2[x2];
                    c3 = c2;
                    c3 = c2.Select(i => i).ToList();
                    c3.Remove(n2);
                    for (int x3 = 0; x3 < c3.Count; x3++)
                    {
                        n3 = c3[x3];

                        if (n1 + n2 + n3 == 38)
                        {
                            c4 = c3.Select(i => i).ToList();
                            c4.Remove(n3);
                            for (int x4 = 0; x4 < c4.Count; x4++)
                            {
                                n4 = c4[x4];
                                c5 = c4.Select(i => i).ToList();
                                c5.Remove(n4);
                                for (int x5 = 0; x5 < c5.Count; x5++)
                                {
                                    n5 = c5[x5];
                                    c6 = c5.Select(i => i).ToList();
                                    c6.Remove(n5);
                                    for (int x6 = 0; x6 < c6.Count; x6++)
                                    {
                                        n6 = c6[x6];
                                        c7 = c6.Select(i => i).ToList();
                                        c7.Remove(n6);
                                        for (int x7 = 0; x7 < c7.Count; x7++)
                                        {
                                            n7 = c7[x7];

                                            if(n4 + n5 + n6 + n7 == 38)
                                            {
                                                c8 = c7.Select(i => i).ToList();
                                                c8.Remove(n7);
                                                for (int x8 = 0; x8 < c8.Count; x8++)
                                                {
                                                    n8 = c8[x8];

                                                    if(n1 + n4 + n8 == 38)
                                                    {
                                                        c9 = c8.Select(i => i).ToList();
                                                        c9.Remove(n8);
                                                        for (int x9 = 0; x9 < c9.Count; x9++)
                                                        {
                                                            n9 = c9[x9];
                                                            c10 = c9.Select(i => i).ToList();
                                                            c10.Remove(n9);

                                                            for (int x10 = 0; x10 < c10.Count; x10++)
                                                            {
                                                                n10 = c10[x10];
                                                                c11 = c10.Select(i => i).ToList();
                                                                c11.Remove(n10);
                                                                for (int x11 = 0; x11 < c11.Count; x11++)
                                                                {
                                                                    n11 = c11[x11];
                                                                    c12 = c11.Select(i => i).ToList();
                                                                    c12.Remove(n11);

                                                                    for (int x12 = 0; x12 < c12.Count; x12++)
                                                                    {
                                                                        n12 = c12[x12];

                                                                        if(n8 + n9 + n10 + n11 + n12 == 38)
                                                                        {
                                                                            if(n3 + n7 + n12 == 38)
                                                                            {
                                                                                c13 = c12.Select(i => i).ToList();
                                                                                c13.Remove(n12);
                                                                                for (int x13 = 0; x13 < c13.Count; x13++)
                                                                                {
                                                                                n13 = c13[x13];

                                                                                if (n2 + n5 + n9 + n13 == 38)
                                                                                {
                                                                                c14 = c13.Select(i => i).ToList();
                                                                                c14.Remove(n13);
                                                                                for (int x14 = 0; x14 < c14.Count; x14++)
                                                                                {
                                                                                n14 = c14[x14];
                                                                                c15 = c14.Select(i => i).ToList();
                                                                                c15.Remove(n14);
                                                                                for (int x15 = 0; x15 < c15.Count; x15++)
                                                                                {
                                                                                n15 = c15[x15];
                                                                                c16 = c15.Select(i => i).ToList();
                                                                                c16.Remove(n15);

                                                                                for (int x16 = 0; x16 < c16.Count; x16++)
                                                                                {
                                                                                n16 = c16[x16];

                                                                                if (n13 + n14 + n15 + n16 == 38)
                                                                                {
                                                                                if (n2 + n6 + n11 + n16 == 38)
                                                                                {
                                                                                c17 = c16.Select(i => i).ToList();
                                                                                c17.Remove(n16);
                                                                                for (int x17 = 0; x17 < c17.Count; x17++)
                                                                                {
                                                                                n17 = c17[x17];

                                                                                if (n3 + n6 + n10 + n14 + n17 == 38)
                                                                                {
                                                                                c18 = c17.Select(i => i).ToList();
                                                                                c18.Remove(n17);
                                                                                for (int x18 = 0; x18 < c18.Count; x18++)
                                                                                {
                                                                                n18 = c18[x18];

                                                                                if (n4 + n9 + n14 + n18 == 38)
                                                                                {
                                                                                if (n7 + n11 + n15 + n18 == 38)
                                                                                {
                                                                                c19 = c18.Select(i => i).ToList();
                                                                                c19.Remove(n18);
                                                                                n19 = c19[0];
                                                                                if(n17 + n18 + n19 == 38)
                                                                                {
                                                                                if(n1 + n5 + n10 + n15 + n19 == 38)
                                                                                {
                                                                                if(n12 + n16 + n19 == 38)
                                                                                {
                                                                                Console.Out.WriteLine("Success");
                                                                                Console.Out.WriteLine(n1);
                                                                                Console.Out.WriteLine(n2);
                                                                                Console.Out.WriteLine(n3);
                                                                                Console.Out.WriteLine(n4);
                                                                                Console.Out.WriteLine(n5);
                                                                                Console.Out.WriteLine(n6);
                                                                                Console.Out.WriteLine(n7);
                                                                                Console.Out.WriteLine(n8);
                                                                                Console.Out.WriteLine(n9);
                                                                                Console.Out.WriteLine(n10);
                                                                                Console.Out.WriteLine(n11);
                                                                                Console.Out.WriteLine(n12);
                                                                                Console.Out.WriteLine(n13);
                                                                                Console.Out.WriteLine(n14);
                                                                                Console.Out.WriteLine(n15);
                                                                                Console.Out.WriteLine(n16);
                                                                                Console.Out.WriteLine(n17);
                                                                                Console.Out.WriteLine(n18);
                                                                                Console.Out.WriteLine(n19);
                                                                                }

                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }

                        }
                    }
                }
            }
            Console.Out.WriteLine(DateTime.Now - time);
            Console.In.Read();
    }

```
> 0 votes

# Answer
39 ms, 363k recurrence calls. Greetings Lukasz.

Java code:

```
package game_numbers;

public class Numbers {
    public static int counter=0;

public static byte get_next(byte[] numbers)
    {
    byte elem=0;
    int i=0;
    do
        {
        elem=numbers[i];
        i++;
        }
    while(elem==0 && i<19) ;
    return elem;
    }

// main recur alg

public static boolean findNext(byte[] gameBoard, byte[] numbers)
   {
    boolean found = false;
    byte tmpNumbers[] = copyNumbers(numbers);
    byte elem = get_next(tmpNumbers);

    do
        {
        counter++;
        tmpNumbers = removeFromNumbers(tmpNumbers, elem);
        gameBoard = putOnBoard(gameBoard,elem);
        //printBoard(gameBoard);
        if(match(gameBoard))
            {
            numbers = removeFromNumbers(numbers, elem);
            if(win(numbers))
                found=true;
            else
                {
                found=findNext(gameBoard, numbers);
                if( !found)
                    {
                    gameBoard = removeFromBoard(gameBoard);
                    numbers = addToNumbers(numbers, elem);
                    }
                }
            }
        else
            removeFromBoard(gameBoard);

        elem=get_next(tmpNumbers);
        }
    while (elem!=0 && !found) ;

return found;
}

private static byte[] addToNumbers(byte[] numbers1, byte elem) {
    numbers1[elem-1] = elem;
    return numbers1;
}

private static byte[] copyNumbers(byte[] numbers) {
byte[] newNumbers={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

for(byte i=0; i<19; i++)
    newNumbers[i] = numbers[i];

return newNumbers;
}

private static void printBoard(byte[] gameBoard) {
    System.out.println();
    for(byte temp: gameBoard)
    {
    System.out.print(temp + " ");
    }

}

private static boolean win(byte[] numbers) {

if( get_next(numbers) == 0)
    return true;
else
    return false;
}

private static byte[] removeFromNumbers(byte[] numbers1, byte elem) {
    numbers1[elem-1] = 0;
    return numbers1;
}

private static byte[] removeFromBoard(byte[] gameBoard) {
byte i=0;
while( gameBoard[i] > 0 )
    i++;
gameBoard[i-1] = 0;
return gameBoard;
}

//evaluation function
private static boolean match(byte[] gameBoard) {

byte SUM = 38;

// mapping of permutation to board game

//spiral from outside - quick 300k
byte a=gameBoard[0];
byte b=gameBoard[1];
byte c=gameBoard[2];
byte g=gameBoard[3];
byte l=gameBoard[4];
byte p=gameBoard[5];
byte t=gameBoard[6];
byte s=gameBoard[7];
byte r=gameBoard[8];
byte m=gameBoard[9];
byte h=gameBoard[10];
byte d=gameBoard[11];
byte e=gameBoard[12];
byte f=gameBoard[13];
byte k=gameBoard[14];
byte o=gameBoard[15];
byte n=gameBoard[16];
byte i=gameBoard[17];
byte j=gameBoard[18];

/*     /a|b|c\
      /d|e|f|g\
     /h|i|j|k|l\
      \m|n|o|p/
       \r|s|t/
*/

if( checkVeriables3(a,b,c) == SUM)
    if (checkVeriables4(d,e,f,g) == SUM)
        if (checkVeriables5(h,i,j,k,l) == SUM)
            if (checkVeriables4(m,n,o,p) == SUM)
                if (checkVeriables3(r,s,t) == SUM)
                    if (checkVeriables3(a,d,h) == SUM)
                        if (checkVeriables4(b,e,i,m) == SUM)
                            if (checkVeriables5(c,f,j,n,r) == SUM)
                                if (checkVeriables4(g,k,o,s) == SUM)
                                    if (checkVeriables3(l,p,t) == SUM)
                                        if (checkVeriables3(c,g,l) == SUM)
                                            if (checkVeriables4(b,f,k,p) == SUM)
                                                if (checkVeriables5(a,e,j,o,t) == SUM)
                                                    if (checkVeriables4(d,i,n,s) == SUM)
                                                        if (checkVeriables3(h , m , r) == SUM) return true;
return false;

}

private static byte checkVeriables5(byte h, byte i, byte j, byte k, byte l) {
byte SUM=38;
if (h==0) return SUM;
if (i==0) return SUM;
if (j==0) return SUM;
if (k==0) return SUM;
if (l==0) return SUM;

SUM=(byte)(h+i+j+k+l);

return SUM;
}

private static byte checkVeriables4(byte h, byte i, byte j, byte k) {
    byte SUM=38;
    if (h==0) return SUM;
    if (i==0) return SUM;
    if (j==0) return SUM;
    if (k==0) return SUM;

    SUM=(byte)(h+i+j+k);

    return SUM;
}

private static byte checkVeriables3(byte h, byte i, byte j) {
    byte SUM=38;
    if (h==0) return SUM;
    if (i==0) return SUM;
    if (j==0) return SUM;

    SUM=(byte)(h+i+j);

    return SUM;
}

private static byte[] putOnBoard(byte[] gameBoard, byte elem) {
    byte i=0;
    while( gameBoard[i] > 0 )
        i++;
    gameBoard[i] = elem;
    return gameBoard;

}

public static void main(String[] args)
    {

    byte[] availableNumbers={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
    byte[] gameBoard={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    boolean found = false;
    long time = System.currentTimeMillis();

    while (!found)
        {
        found = findNext(gameBoard,availableNumbers);
        }

    long time1 = System.currentTimeMillis();
    for(byte temp: gameBoard)
        System.out.print(temp + " ");

    System.out.println();
    System.out.println("runing time:" + (time1-time));
    System.out.println("number of recurrence calls:" + counter);
    }
}

```
> 0 votes

---
Tags: code-golf, fastest-code, puzzle-solver, hexagonal-grid
---


title: Supersonic domino tilings

text:
# Question
Title: Supersonic domino tilings
### Task

Write a program that reads three integers **m**, **n** either from STDIN or as command-line arguments, prints all possible tilings of a rectangle of dimensions **m × n** by **2 × 1** and **1 × 2** dominos and finally the number of valid tilings.

Dominos of an individual tiling have to be represented by two dashes (`-`) for **2 × 1** and two vertical bars (`|`) for **1 × 2** dominos. Each tiling (including the last one) has to be followed by a linefeed.

For scoring purposes, you also have to accept a flag from STDIN or as command line argument that makes your program print only the number of valid tilings, but not the tilings itself.

Your program may not be longer than 1024 bytes. It has to work for all inputs such that **m × n ≤ 64**.

(Inspired by Print all domino tilings of 4x6 rectangle.)

### Example

```
$ sdt 4 2
----
----

||--
||--

|--|
|--|

--||
--||

||||
||||

5
$ sdt 4 2 scoring
5

```

### Scoring

Your score is determined by the execution time of your program for the input **8 8** with the flag set.

To make this a *fastest code* rather than a *fastest computer* challenge, I will run all submissions on my own computer (Intel Core i7-3770, 16 GiB PC3-12800 RAM) to determine the official score.

Please leave detailed instructions on how to compile and/or execute your code. If you require a specific version of your language's compiler/interpreter, make a statement to that effect.

I reserve the right to leave submissions unscored if:

* There is no free (as in beer) compiler/interpreter for my operating system (Fedora 21, 64 bits).
* Despite our efforts, your code doesn't work and/or produces incorrect output on my computer.
* Compilation or execution take longer than an hour.
* Your code or the only available compiler/interpreter contain a system call to `rm -rf ~` or something equally fishy.

### Leaderboard

I've re-scored all submissions, running both compilations and executions in a loop with 10,000 iterations for compilation and between 100 and 10,000 iterations for execution (depending on the speed of the code) and calculating the mean.

These were the results:

```
User          Compiler   Score                              Approach

jimmy23013    GCC (-O0)    46.11 ms =   1.46 ms + 44.65 ms  O(m*n*2^n) algorithm.
steveverrill  GCC (-O0)    51.76 ms =   5.09 ms + 46.67 ms  Enumeration over 8 x 4.
jimmy23013    GCC (-O1)   208.99 ms = 150.18 ms + 58.81 ms  Enumeration over 8 x 8.
Reto Koradi   GCC (-O2)   271.38 ms = 214.85 ms + 56.53 ms  Enumeration over 8 x 8.

```

# Answer
> 5 votes
# C

A straightforward implementation...

```
#include<stdio.h>
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0;
char r[100130];
void w(i,x,o){
    int j,k;
    j=(1<<b)-1&~x;
    if(i<a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&j/2&-o;j=k&-k;k&=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j)
        if(countonly)
            m++;
        else{
            if(c==b)
                for(k=0;k<b;r[k++,l++]=10)
                    for(j=0;j<a;j++)
                        r[l++]=45+79*!((s[j]|s[j+1])&(1<<k));
            else
                for(j=0;j<a;r[j++,l++]=10)
                    for(k=0;k<b;k++)
                        r[l++]=124-79*!((s[j]|s[j+1])&(1<<k));
            r[l++]=10;
            if(l>=100000){
                fwrite(r,l,1,stdout);
                l=0;
            }
        }
}

int main(){
    scanf("%d %d %d",&a,&b,&countonly);
    c=b;
    if(a<b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    w(0,0,1);
    if(countonly)
        printf("%llu\n",m);
    else if(l)
        fwrite(r,l,1,stdout);
}

```

### The cheating version

```
#include<stdio.h>
#include<string.h>
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0,d[256];
char r[100130];
void w2(){
    int i,j,k,x;
    memset(d,0,sizeof d);
    d[0]=1;
    j=0;
    for(i=0;i<a-1;i++){
        for(k=1;k<(1<<(b-1));k*=2)
            for(x=0;x<(1<<(b-2));x++)
                d[(x+x/k*k*3+k*3)^j]+=d[(x+x/k*k*3)^j];
        j^=(1<<b)-1;
    }
    for(x=0;x<(1<<b);x++)
        if((x/3|x/3*2)==x)
            m+=d[x^((1<<b)-1)^j];
    printf("%llu\n",m);
}

void w(i,x,o){
    int j,k;
    j=(1<<b)-1&~x;
    if(i<a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&j/2&-o;j=k&-k;k&=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j){
        if(c==b)
            for(k=0;k<b;r[k++,l++]=10)
                for(j=0;j<a;j++)
                    r[l++]=45+79*!((s[j]|s[j+1])&(1<<k));
        else
            for(j=0;j<a;r[j++,l++]=10)
                for(k=0;k<b;k++)
                    r[l++]=124-79*!((s[j]|s[j+1])&(1<<k));
        r[l++]=10;
        if(l>=100000){
            fwrite(r,l,1,stdout);
            l=0;
        }
    }
}

int main(){
    scanf("%d %d %d",&a,&b,&countonly);
    c=b;
    if(a<b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    if(countonly)
        w2();
    else{
        w(0,0,1);
        if(l)
            fwrite(r,l,1,stdout);
    }
}

```

### Explanation of the faster algorithm

It scans from left to right, and maintain the state `d[i][j]`, where:

* `i` is in `[0,m)`, which means the current column.
* `j` is a bit vector of size `n`, where the bit would be 1 if the corresponding position in column `i` is already occupied before starting working on this column. I.e. it is occupied by the right half of a `--`.
* `d[i][j]` is the total number of different tilings.

Then say `e[i][j]` = the sum of `d[i][k]` where you can put vertical dominoes base on `k` to form a `j`. `e[i][j]` would be the number of tilings where each 1 bit in `j` is occupied by anything but the left half of a `--`. Fill them with `--` and you'll get `d[i+1][~j]` = `e[i][j]`. `e[m-1][every bit being 1]` or `d[m][0]` is the final answer.

A naive implementation will get you the time complexity somewhere near `g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n)` (already fast enough if n=m=8). But you can instead firstly loop for each possible domino, and try to add it to every tiling that can have this domino added, and merge the result to the original array `d` (like the algorithm for the Knapsack problem). And this becomes O(n\*2^n). And everything else are implementation details. The whole code runs in O(m\*n\*2^n).

# Answer
> 3 votes
# C

After a round of optimizations, and adapted for the modified rules:

```
typedef unsigned long u64;

static int W, H, S;
static u64 RM, DM, NSol;
static char Out[64 * 2 + 1];

static void place(u64 cM, u64 vM, int n) {
  if (n) {
    u64 m = 1ul << __builtin_ctzl(cM); cM -= m;

    if (m & RM) {
      u64 nM = m << 1;
      if (cM & nM) place(cM - nM, vM, n - 1);
    }

    if (m & DM) {
      u64 nM = m << W;
      vM |= m; vM |= nM; place(cM - nM, vM, n - 1);
    }
  } else if (S) {
    ++NSol;
  } else {
    char* p = Out;
    for (int y = 0; y < H; ++y) {
      for (int x = 0; x < W; ++x) { *p++ = vM & 1 ? '|' : '-'; vM >>= 1; }
      *p++ = '\n';
    }
    *p++ = '\0';
    puts(Out);
    ++NSol;
  }
}

int main(int argc, char* argv[]) {
  W = atoi(argv[1]); H = atoi(argv[2]); S = (argc > 3);

  int n = W * H;
  if (n & 1) return 0;

  for (int y = 0; y < H; ++y) {
    RM <<= W; RM |= (1ul << (W - 1)) - 1;
  }
  DM = (1ul << (W * (H - 1))) - 1;

  place(-1, 0, n >> 1);
  printf("%lu\n", NSol);

  return 0;
}

```

I started bumping into the length limit of 1024 characters, so I had to reduce the readability somewhat. Much shorter variable names, etc.

Build instructions:

```
> gcc -O2 Code.c

```

Run with solution output enabled:

```
> ./a.out 8 8 >/dev/null

```

Run with only solution count:

```
> ./a.out 8 8 s

```

Some comments:

* With the larger test example, I do want optimization now. While my system is different (Mac), around `-O2` seems to be good.
* The code has gotten slower for the case where output is generated. This was a conscious sacrifice for optimizing the "count only" mode, and for reducing the code length.
* There will be a few compiler warnings because of missing includes and external declarations for system functions. It was the easiest way to get me to below 1024 characters in the end without making the code totally unreadable.

Also note that the code still generates the actual solutions, even in "count only" mode. Whenever a solution is found, the `vM` bitmask contains a `1` for the positions that have a vertical bar, and a `0` for positions with a horizontal bar. Only the conversion of this bitmask into ASCII format, and the actual output, is skipped.

# Answer
> 1 votes
# C

The concept is to first find all possible arrangements of horizontal dominoes in a row, store them in `r[]` and then organize them to give all possible arrangements of vertical dominoes.

The code for positioning the horizontal dominoes in a row is modified from this answer of mine: https://codegolf.stackexchange.com/a/37888/15599. It's slow for the wider grids but that isn't a problem for the 8x8 case.

The innovation is in the way the rows are assembled. If the board has an odd number of rows it is turned through 90 degrees in the input parsing, so it now has an even number of rows. Now I place some vertical dominoes across the centreline. Because of symmetry, if there are `c` ways of arranging the remaining dominoes in the bottom half, there must also be `c` ways of arranging the remaining dominoes in the top half, meaning that for a given arrangement of vertical dominoes on the centreline, there are `c*c` possible solutions. Therefore only the centreline plus one half of the board is analysed when the program is required to print only the number of solutions.

`f()` builds the table of possible arrangements of horizontal dominoes, and scans through the possible arrangements of vertical dominoes on the centreline. it then calls recursive function `g()` which fills in the rows. If printing is required, function `h()` is called to do this.

`g()` is called with 3 parameters. `y` is the current row and `d` is the direction (up or down) in which we are filling the board from the centre outwards. `x` contains a bitmap indicates the vertical dominoes that are incomplete from the previous row. All possible arrangements of dominoes in a row from r\[\] are tried. In this array, a 1 represents a vertical domino and a pair of zeroes a horizontal domino. A valid entry in the array must have at least enough 1's to finish any incomplete vertical dominoes from the last row: `(x&r[j])==x`. It may have more 1's which indicates that new vertical dominoes are being started. For the next row, then, we need only the new dominoes so we call the procedure again with `x^r[j]`.

If an end row has been reached and there are no incomplete vertical dominoes hanging of the top or bottom of the board `x^r[j]==0` then the half has been succesfully completed. If we are not printing, it is sufficient to complete the bottom half and use `c*c` to work out the total number of arrangements. If we are printing, it will be necessary to complete also the top half and then call the printing function `h()`.

**CODE**

```
unsigned int W,H,S,n,k,t,r[1<<22],p,q[64];
long long int i,c,C;

//output: ascii 45 - for 0, ascii 45+79=124 | for 1
h(){int a;
  for(a=n;a--;a%W||puts(""))putchar(45+(q[a/W]>>a%W)%2*79);
  puts("");
}

g(y,d,x){int j;
  for(j=0;j<p;j++)if((x&r[j])==x){
    q[y]=r[j];
    if(y%(H-1)==0){
       (x^r[j])==0?
        y?c++,S||g(H/2-1,-1,i):h()
       :0;
    }else{
      g(y+d,d,x^r[j]);
    }

  }
}

e(z){int d;
  for(d=0;z;d++)z&=z-1;return n/2+1+d&1;
}

f(){
  //k=a row full of 1's
  k=(1ULL<<W)-1;

  //build table of possible arrangements of horizontal dominoes in a row;
  //flip bits so that 1=a vertical domino and save to r[]
  for(i=0;i<=k;i++)(i/3|i/3<<1)==i?r[p++]=i^k:0;

  //for each arrangement of vertical dominoes on the centreline, call g()
  for(i=0;i<=k;i++)e(i)?c=0,g(H/2,1,i),C+=c*c:0;
  printf("%llu",C);
}

main(int argc, char* argv[]) {
  W = atoi(argv[1]); H = atoi(argv[2]); S = (argc > 3);
  1-(n=W*H)%2?
      H%2?W^=H,H^=W,W^=H,t=1:0,f()
    :puts("0");

}

```

Note that input with an odd number of rows and even number of columns is turned though 90 degrees in the parsing phase. If this is unacceptable, the printing function `h()` can be changed to accomodate it. (EDIT: not required, see comments.)

EDIT: A new function `e()` has been used to check the parity of `i` (i.e the number of dominoes straddling the centreline.) The parity of `i` (the number of half-dominoes on the centreline protruding into each half of the board) must be the same as the oddness of the total number of spaces in each half (given by `n/2`) because only then can the dominoes fill all available space. This edit eliminates half the values of i and therefore makes my program approximately twice as fast.

---
Tags: math, fastest-code, combinatorics, tiling
---