11
\$\begingroup\$

Objective

I have a nice picture that I want to hang on my wall. And I want it to hang there in a spectacular way, so I chose to hang it on n nails where n is any positive integer.

But I'm also indecisive, so if I change my mind, I don't want a lot of trouble taking the picture down. Therefore, removing any one of the n nails should make the picture fall down. Did I mention that there is no friction in my house?

Can you help me?

Rules

  1. Your program must read the number n from stdin and print to stdout (or your language's equivalents).
  2. The output must be the solution according to the output specification without any other trailing or leading characters. However, trailing whitespace and/or newlines is acceptable.
  3. You must use exactly n nails.
  4. Assuming a friction-less world, your solution must fulfill the following conditions:
    1. Hanging the picture as described by your solution, the picture must not fall down.
    2. If any one of the nails is removed, the picture must fall down.
  5. Standard loopholes apply. In particular, you may not make requests to, e.g., the verification program to brute-force solutions.

Note that 4.2 already implies that all n nails must be involved.

Output Specification

  • All nails are named from left to right with the position they are in, starting at 1.
  • There are two fundamental ways to put the string around a nail: clockwise and counter-clockwise. We denote a clockwise step with > and a counter-clockwise step with <.
  • Everytime the string is put around a nail, it comes out on top of the nails, so skipping nails means the string will go across the top of the intermediate nails.
  • Every solution must start on nail 1 and end on nail n.
  • The output must consist of a sequence of steps wherein a step is a combination fo the nail's name and the direction in which to put the string around it.

Example Output

Here is an example output for n=5 and n=3:

1>4<3<2>4>5<          # n=5, incorrect solution
1>2<1<2>3<2<1>2>1<3>  # n=3, correct solution

And here is a visual representation of the incorrect solution for n=5 (awsumz gimp skillz)

Visual Representation

The correct solution for n=1 is simply 1> or 1<. For multiple nails, there can be different solutions. You must only output one since this is part of your score.

Verification

You can verify whether a solution is correct here: www.airblader.de/verify.php.

It uses a GET request, so you can call it directly if you want. For example, if foo is a file containing a solution on each line, you can use

cat foo | while read line; do echo `wget -qO- "www.airblader.de/verify.php?solution=$line" | grep "Passed" | wc -l`; done

If you believe a solution is correct but the verifier marks it as incorrect, please let me know!

Edit: And if your output is so long that a GET request won't cut it, let me know and I'll make a POST request version. :)

Scoring

This is code-golf. The score is the number of bytes of your source-code in UTF-8 encoding, e.g., use this tool. However, there is a potential bonus for every submission:

Run your program for all n in the range [1..20] and add the length of all outputs up to determine your output score. Subtract your output score from 6291370 to get the number of bonus points that you may deduct from your byte count to get your overall score. There is no penalty if your output score is higher than this number.

The submission with the lowest overall score wins. In the unlikely case of a tie, the tie breakers are in this order: higher bonus points, lower byte count, earlier submission date.

Please post both the individual parts (byte count, bonus points) of the score and the final score, e.g., "LOLCODE (44 - 5 = 39)".

Improve this question
\$\endgroup\$
17
  • 1
    \$\begingroup\$ Do > and < always guarantee that the string loops over the top of the nail? If so, can you post an example of a valid output for n>1? Also - what is the output for an input of n with no solutions? \$\endgroup\$
    – Comintern
    Aug 31, 2014 at 20:11
  • \$\begingroup\$ The string will always pass once over the nail, otherwise this nail would effectively not be involved. But it isn't a "full" loop as that would make it impossible (compare how 1> is drawn in the picture). And there is no n where no solution is possible. A valid solution for n=2 is 1>2<1<2>. \$\endgroup\$
    – Ingo Bürk
    Aug 31, 2014 at 20:24
  • 1
    \$\begingroup\$ I'm not sure I understand how that would fall. Wouldn't the string be wound like this? \$\endgroup\$
    – Comintern
    Aug 31, 2014 at 20:36
  • \$\begingroup\$ It's hard to explain in words. If you have some string, try it out :) or at least draw it with enough space. I might be able to make a little animation tomorrow if it's still hard to visualize. For today I'm afraid I'll have to say goodnight. ;) edit: just saw you drew it. Yes that is correct. Imagine carefully what happens if a nail is removed. Again, I'll make a small animation tomorrow otherwise. \$\endgroup\$
    – Ingo Bürk
    Aug 31, 2014 at 20:48
  • \$\begingroup\$ (one attempt in words: if 2 is removed, the entire right side can fall down freely. The loop that went around it can now be pulled across the top of 1 and then the entire string is free) \$\endgroup\$
    – Ingo Bürk
    Aug 31, 2014 at 20:51

3 Answers 3

Reset to default
5
\$\begingroup\$

GolfScript (51 67 bytes + (7310 7150 - 6,291,370) = -6,284,153)

~,{.,({.,.[1]*{(\(@++}@((*1=/{C}%.~+2/-1%{~'<>'^}%*}{[~)'>']}if}:C~

This is based on Chris Lusby Taylor's* recursive commutator construction, better expounded in Picture-Hanging Puzzles, Demaine et al., Theory of Computing Systems 54(4):531-550 (2014).

Outputs for the first 20 inputs:

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

NB I think that the longer answers will fail the online test because it uses GET rather than POST and URLs are not guaranteed to be handled correctly if they're longer than 255 chars.

There are two tweaks on the standard construction:

  1. In order to ensure that it finishes on the last nail, I actually form the commutator [x_1, x_2^-1] instead of [x_1, x_2].
  2. Following xnor's example, I don't split 50-50. It turns out that to balance it so the larger numbers are used less frequently** the ideal split is according to A006165. I'm using David Wilson's observation to calculate it.

* No relation, as far as I'm aware.
** Well, within the same recursive commutator approach. I'm not claiming to have solved the open problem of proving it optimal.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ About URL: Yes, I thought about that. So far nothing came up, so I decided to leave it to allow scripting the check more easily. \$\endgroup\$
    – Ingo Bürk
    Sep 1, 2014 at 16:33
  • \$\begingroup\$ Also +1 just for the reference. I didn't know a paper on this existed, but always suspected it might! \$\endgroup\$
    – Ingo Bürk
    Sep 1, 2014 at 16:34
  • \$\begingroup\$ @IngoBürk, it's quite a recent paper, so I assumed that it was that which gave you the idea. Interesting to know that it wasn't. \$\endgroup\$
    – Peter Taylor
    Sep 1, 2014 at 16:36
  • \$\begingroup\$ I learned about this puzzle about 6 years or so ago when I was visiting the math faculty of the university on an "open day" kind of thing, the year before I started studying mathematics. Loved it eversince! \$\endgroup\$
    – Ingo Bürk
    Sep 1, 2014 at 16:38
4
\$\begingroup\$

Python 2 (208 bytes + (7230 - 6,291,370) = -6,283,932)

def f(a,b):
 if a<b+2:return[a]
 m=(a+b+1)/2
 while all(8*x!=2**len(bin(x))for x in[a-m,m-b]):m+=1
 A=f(a,m);B=f(m,b)
 return[-x for x in A+B][::-1]+B+A 
print"1<1>"+"".join(`abs(x)`+"<>"[x>0]for x in f(input(),0))

The function f recursively makes an answer by combining half-solutions as A^{-1}*B^{-1}*A*B, represents inverses by negation. f(a,b) is a solution for the numbers in the half-open interval [a,b).

Edit: To comply with the requirement to start with 1 and end with n, I flipped the order to always end with n by using reversed intervals, and simply append "1<1>" to the beginning.

Edit: Saved 136 symbols in output by rounding the other way in picking intervals, causing intervals with larger numbers (and so likelier to have two digits) to be shorter.

Edit: Saved 100 symbols by splitting the intervals unevenly so the one with larger numbers is shorter. This doesn't lengthen the number of operations used as long as the lengths never cross powers of 2.

Edit: Reintroduced favorable rounding, -50 symbols, 2+ code chars.

Outputs for 1 through 20:

1<1>1>
1<1>1<2<1>2>
1<1>2<1<2>1>3<1<2<1>2>3>
1<1>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>
1<1>3<2<1<2>1>3>1<2<1>2>5<4<5>4>2<1<2>1>3<1<2<1>2>3>4<5<4>5>
1<1>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>5<6<5>6>
1<1>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>7<6<5<6>5>7>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>7<5<6<5>6>7>
1<1>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>
1<1>5<4<5>4>3<2<1<2>1>3>1<2<1>2>4<5<4>5>2<1<2>1>3<1<2<1>2>3>9<8<9>8>7<6<7>6>8<9<8>9>6<7<6>7>3<2<1<2>1>3>1<2<1>2>5<4<5>4>2<1<2>1>3<1<2<1>2>3>4<5<4>5>7<6<7>6>9<8<9>8>6<7<6>7>8<9<8>9>
1<1>6<5<6>5>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>10<9<10>9>8<7<8>7>9<10<9>10>7<8<7>8>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>5<6<5>6>8<7<8>7>10<9<10>9>7<8<7>8>9<10<9>10>
1<1>7<6<5<6>5>7>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>7<5<6<5>6>7>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>11<10<11>10>9<8<9>8>10<11<10>11>8<9<8>9>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>7<6<5<6>5>7>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>7<5<6<5>6>7>9<8<9>8>11<10<11>10>8<9<8>9>10<11<10>11>
1<1>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>
1<1>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>13<12<13>12>11<10<9<10>9>11>9<10<9>10>12<13<12>13>10<9<10>9>11<9<10<9>10>11>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>11<10<9<10>9>11>9<10<9>10>13<12<13>12>10<9<10>9>11<9<10<9>10>11>12<13<12>13>
1<1>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>14<13<14>13>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>13<14<13>14>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>14<13<14>13>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>13<14<13>14>
1<1>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>15<14<13<14>13>15>13<14<13>14>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>14<13<14>13>15<13<14<13>14>15>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>15<14<13<14>13>15>13<14<13>14>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>14<13<14>13>15<13<14<13>14>15>
1<1>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>16<15<16>15>14<13<14>13>15<16<15>16>13<14<13>14>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>14<13<14>13>16<15<16>15>13<14<13>14>15<16<15>16>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>16<15<16>15>14<13<14>13>15<16<15>16>13<14<13>14>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>14<13<14>13>16<15<16>15>13<14<13>14>15<16<15>16>
1<1>9<8<9>8>7<6<7>6>8<9<8>9>6<7<6>7>5<4<5>4>3<2<1<2>1>3>1<2<1>2>4<5<4>5>2<1<2>1>3<1<2<1>2>3>7<6<7>6>9<8<9>8>6<7<6>7>8<9<8>9>3<2<1<2>1>3>1<2<1>2>5<4<5>4>2<1<2>1>3<1<2<1>2>3>4<5<4>5>17<16<17>16>15<14<15>14>16<17<16>17>14<15<14>15>13<12<13>12>11<10<11>10>12<13<12>13>10<11<10>11>15<14<15>14>17<16<17>16>14<15<14>15>16<17<16>17>11<10<11>10>13<12<13>12>10<11<10>11>12<13<12>13>5<4<5>4>3<2<1<2>1>3>1<2<1>2>4<5<4>5>2<1<2>1>3<1<2<1>2>3>9<8<9>8>7<6<7>6>8<9<8>9>6<7<6>7>3<2<1<2>1>3>1<2<1>2>5<4<5>4>2<1<2>1>3<1<2<1>2>3>4<5<4>5>7<6<7>6>9<8<9>8>6<7<6>7>8<9<8>9>13<12<13>12>11<10<11>10>12<13<12>13>10<11<10>11>17<16<17>16>15<14<15>14>16<17<16>17>14<15<14>15>11<10<11>10>13<12<13>12>10<11<10>11>12<13<12>13>15<14<15>14>17<16<17>16>14<15<14>15>16<17<16>17>
1<1>10<9<10>9>8<7<8>7>9<10<9>10>7<8<7>8>6<5<6>5>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>8<7<8>7>10<9<10>9>7<8<7>8>9<10<9>10>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>5<6<5>6>18<17<18>17>16<15<16>15>17<18<17>18>15<16<15>16>14<13<14>13>12<11<12>11>13<14<13>14>11<12<11>12>16<15<16>15>18<17<18>17>15<16<15>16>17<18<17>18>12<11<12>11>14<13<14>13>11<12<11>12>13<14<13>14>6<5<6>5>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>10<9<10>9>8<7<8>7>9<10<9>10>7<8<7>8>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>5<6<5>6>8<7<8>7>10<9<10>9>7<8<7>8>9<10<9>10>14<13<14>13>12<11<12>11>13<14<13>14>11<12<11>12>18<17<18>17>16<15<16>15>17<18<17>18>15<16<15>16>12<11<12>11>14<13<14>13>11<12<11>12>13<14<13>14>16<15<16>15>18<17<18>17>15<16<15>16>17<18<17>18>
1<1>11<10<11>10>9<8<9>8>10<11<10>11>8<9<8>9>7<6<5<6>5>7>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>7<5<6<5>6>7>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>9<8<9>8>11<10<11>10>8<9<8>9>10<11<10>11>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>7<6<5<6>5>7>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>7<5<6<5>6>7>19<18<19>18>17<16<17>16>18<19<18>19>16<17<16>17>15<14<15>14>13<12<13>12>14<15<14>15>12<13<12>13>17<16<17>16>19<18<19>18>16<17<16>17>18<19<18>19>13<12<13>12>15<14<15>14>12<13<12>13>14<15<14>15>7<6<5<6>5>7>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>7<5<6<5>6>7>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>11<10<11>10>9<8<9>8>10<11<10>11>8<9<8>9>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>7<6<5<6>5>7>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>7<5<6<5>6>7>9<8<9>8>11<10<11>10>8<9<8>9>10<11<10>11>15<14<15>14>13<12<13>12>14<15<14>15>12<13<12>13>19<18<19>18>17<16<17>16>18<19<18>19>16<17<16>17>13<12<13>12>15<14<15>14>12<13<12>13>14<15<14>15>17<16<17>16>19<18<19>18>16<17<16>17>18<19<18>19>
1<1>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>20<19<20>19>18<17<18>17>19<20<19>20>17<18<17>18>16<15<16>15>14<13<14>13>15<16<15>16>13<14<13>14>18<17<18>17>20<19<20>19>17<18<17>18>19<20<19>20>14<13<14>13>16<15<16>15>13<14<13>14>15<16<15>16>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>12<11<12>11>10<9<10>9>11<12<11>12>9<10<9>10>4<3<4>3>2<1<2>1>3<4<3>4>1<2<1>2>8<7<8>7>6<5<6>5>7<8<7>8>5<6<5>6>2<1<2>1>4<3<4>3>1<2<1>2>3<4<3>4>6<5<6>5>8<7<8>7>5<6<5>6>7<8<7>8>10<9<10>9>12<11<12>11>9<10<9>10>11<12<11>12>16<15<16>15>14<13<14>13>15<16<15>16>13<14<13>14>20<19<20>19>18<17<18>17>19<20<19>20>17<18<17>18>14<13<14>13>16<15<16>15>13<14<13>14>15<16<15>16>18<17<18>17>20<19<20>19>17<18<17>18>19<20<19>20>
Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ This will get you an amazing (negative) score. I fully expected negative scores. I'll fix the verify script later and check your solutions then. \$\endgroup\$
    – Ingo Bürk
    Sep 1, 2014 at 6:47
  • \$\begingroup\$ As pointed out in the comments, this is currently invalid because the output must end with the last nail :( \$\endgroup\$
    – Ingo Bürk
    Sep 1, 2014 at 15:21
  • 2
    \$\begingroup\$ Oh, I missed that, I'll just append a vestigial n>n< then. \$\endgroup\$
    – xnor
    Sep 1, 2014 at 15:41
  • 1
    \$\begingroup\$ The online checker currently doesn't accept a final nail that's two digits. \$\endgroup\$
    – xnor
    Sep 1, 2014 at 16:06
  • \$\begingroup\$ I fixed it. I probably should've written some tests for it… :) (edit: the script fails for your n=1 solution now. working on it) \$\endgroup\$
    – Ingo Bürk
    Sep 1, 2014 at 16:17
1
\$\begingroup\$

C - (199 bytes - 0) = 199

p,n,i;main(int x,char **a){for(n=atoi(a[x=i=1]);i<n;i++)x=x*2+2;int o[x];*o=1;for(x=2;n/x;o[++p]=-x++)for(o[i=(++p)]=x;i;o[++p]=-o[--i]);for(i=0;i<=p;printf("%d%s",abs(o[i]),(o[i]<0)?"<":">"),i++);}

With line breaks:

p,n,i;
main(int x,char **a)
{
    for(n=atoi(a[x=i=1]);i<n;i++)
        x=x*2+2;
    int o[x];
    *o=1;
    for(x=2;n/x;o[++p]=-x++)
        for(o[i=(++p)]=x;i;o[++p]=-o[--i]);
    for(i=0;i<=p;printf("%d%s",abs(o[i]),(o[i]<0)?"<":">"),i++);
}

Probably a fairly naive algorithm given that I don't know that much about knot theory. Basically just adds the next higher number, then reverses the whole instruction set to unwind it. This would likely much more concise in a language that handles sets better...

The total output length for n in the range [1..20] was 6,291,370 bytes of output (3,145,685 instructions). This was huge enough that I only posted sample outputs for n in the range [1..10].

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 6,291,370 is exactly the correct number I wanted to post. I accidentally only posted the number for n=20, not the sum of all. I'll have to crank it down to [1..10]. \$\endgroup\$
    – Ingo Bürk
    Sep 1, 2014 at 5:51
  • \$\begingroup\$ I decided to leave the scoring as is, but drop the requirement to post output. So your score would now be 199 + 0 = 199. \$\endgroup\$
    – Ingo Bürk
    Sep 1, 2014 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.