title: Adding Numbers with Regex

text:
# Question
Title: Adding Numbers with Regex
I want to try a new type of regex golf challenge, which asks you to solve nontrivial computational tasks with nothing but regex substitution. To make this more possible and less of a chore, you will be allowed to apply several substitutions, one after the other.

## The Challenge

We'll start simple: given a string containing two positive integers, as decimal numbers separated by a `,`, produce a string containing their sum, also as as a decimal number. So, very simply

```
47,987

```

should turn into

```
1034

```

Your answer should work for arbitrary positive integers.

## The Format

Every answer should be a *sequence* of substitution steps, each step consisting of a regex and a replacement string. Optionally, for each of those steps in the sequence, you may choose to repeat the substitution until the string stops changing. Here is an example submission (which does *not* solve the above problem):

```
Regex    Modifiers   Replacement   Repeat?
\b(\d)   g           |$1           No
|\d      <none>      1|            Yes
\D       g           <empty>       No

```

Given the input `123,456`, this submission would process the input as follows: the first substitution is applied once and yields:

```
|123,|456

```

Now the second substitution is applied in a loop until the string stops changing:

```
1|23,|456
11|3,|456
111|,|456
111|,1|56
111|,11|6
111|,111|

```

And lastly, the third substitution is applied once:

```
111111

```

Note that the termination criterion for loops is whether the string changes, not whether the regex found a match. (That is, it might also terminate if you find a match but the replacement is identical to the match.)

## Scoring

Your primary score will be the number of substitution steps in your submission. *Every **repeated** substitution will count for **10** steps.* So the above example would score `1 + 10 + 1 = 12`.

In the (not too unlikely) case of a tie, the secondary score is the sum of the sizes of all steps. For each step add the regex (*without* delimiters), the modifiers and the substitution string. For the above example this would be `(6 + 1 + 3) + (3 + 0 + 2) + (2 + 1 + 0) = 18`.

## Miscellaneous Rules

You may use any regex flavour (which you should indicate), but all steps must use the same flavour. Furthermore, you must *not* use any features of the flavour's host language, like replacement callbacks or Perl's `e` modifier, which evaluates Perl code. All manipulation must happen exclusively through regex substitution.

Note that it depends on your flavour and modifiers whether each single replacement replaces all occurrences or only a single one. E.g. if you choose the ECMAScript flavour, a single step will by default only replace one occurrence, unless you use the `g` modifier. On the other hand, if you're using the .NET flavour, each step will always replace all occurrences.

For languages which have different substitution methods for single and global replacement (e.g. Ruby's `sub` vs. `gsub`), assume that single replacement is the default and treat global replacement like a `g` modifier.

## Testing

If your chosen flavour is either .NET or ECMAScript, you can use Retina to test your submission (I'm being told, it works on Mono, too). For other flavours, you will probably have to write a small program in the host language which applies the substitutions in order. If you do, please include this test program in your answer.

# Answer
> 33 votes
# .NET flavor, score:2

```
Regex        Modifiers  Replacement  Repeat?
<empty>      <none>     9876543210   No
<see below>  x          <empty>      No

```

I'm not bothered to golf it yet, and `x` is just for ignoring whitespaces.

It firstly insert `9876543210` at each position, then delete the original characters and the characters those are not the current digit of the sum.

The big regex (1346 bytes without whitespaces and comments):

```
# If the length of the left number <= right number, delete every digit on the left.
.(?=.*,(?<=^(?<len>.)*,)(?<-len>.)*(?(len)(?!)))|

# Do the opposite if it is not the case.
.(?<=(?(len)(?!))(?<-len>.)*(?=(?<len>.)*$),.*)|

# Remove leading zeros.
(?<=(^|,).{9})0|

# Delete everything that is not the current digit of the sum.
.(?!
    # For digits in the left part:
    (?<cur>.){0,9}               # cur = the matched digit
    (?=(.{11})*,)                # and find the position before the next digit.
    (?<first>)                   # first = true
    (                            # Loop on the less significant digits:
        (?<cur>){10}             # cur += 10
        (?<=                     # cur -= the current digit in this number.
            (
                0|^|
                1(?<-cur>)|
                2(?<-cur>){2}|
                3(?<-cur>){3}|
                4(?<-cur>){4}|
                5(?<-cur>){5}|
                6(?<-cur>){6}|
                7(?<-cur>){7}|
                8(?<-cur>){8}|
                9(?<-cur>){9}
            )
            .{10}
        )
        (?=
            (?<pos>.{11})*,      # pos = which digit it is.
            .*$(?<=              # cur -= the current digit in the other number.
                (
                    0|,|
                    1(?<-cur>)|
                    2(?<-cur>){2}|
                    3(?<-cur>){3}|
                    4(?<-cur>){4}|
                    5(?<-cur>){5}|
                    6(?<-cur>){6}|
                    7(?<-cur>){7}|
                    8(?<-cur>){8}|
                    9(?<-cur>){9}
                )
                .{10}
                (?(pos)(?!))     # Assert pos = 0.
                                 # Skip pos input digits from the end.
                                 # But stop and set pos = 0 if the comma is encountered.
                ((?<-pos>\d{11})|(?<=(?>(?<-pos>.)*),.{10}))*
            )
        )
        (?(first)                # If first:
            (?>((?<-cur>){10})?) #  cur -= 10 in case there is no carry.
                                 #  Assert cur = 0 or 1, and if cur = 1, set cur = 10 as carry.
            (?(cur)(?<-cur>)(?(cur)(?!))(?<cur>){10})
            (?<-first>)          #  first = false
        |                        # Else:
                                 #  cur is 10 or 20 at the beginning of an iteration.
                                 #  It must be 1 to 11 to make the equation satisfiable.
            (?<-cur>)            #  cur -= 1
            (?(cur)              #  If cur > 0:
                                 #   cur -= max(cur, 9)
                (?(cur)(?<-cur>)){9}
                (?(cur)          #   If cur > 0:
                                 #    Assert cur = 1 (was 11) and set cur = 10.
                    (?<-cur>)(?(cur)(?!))(?<cur>){10}
                |                #   Else:
                    .*(?=,)      #    cur was 2 to 10, break from the loop.
                )
            )                    #  Else cur is 0 (was 1) and do nothing.
        )
        (.{11}|,)                # Jump to the next digit.
    )*(?<=,)(?(cur)(?!))         # End the loop if it is the last digit, and assert cur = 0.
|
    # Do the same to the right part. So the sum will be calculated two times.
    # Both are truncated to the original length of the number on that side + 1.
    # Only the sum on the longer side will be preserved in the result.
    (?<cur>\d){0,9}
    (?=(\d{11})*$)
    (?<first>)
    (
        (?<cur>){10}
        (?<=
            (
                0|,|
                1(?<-cur>)|
                2(?<-cur>){2}|
                3(?<-cur>){3}|
                4(?<-cur>){4}|
                5(?<-cur>){5}|
                6(?<-cur>){6}|
                7(?<-cur>){7}|
                8(?<-cur>){8}|
                9(?<-cur>){9}
            )
            .{10}
        )
        (?=
            (?<pos>.{11})*$
            (?<=
                (
                    0|^|
                    1(?<-cur>)|
                    2(?<-cur>){2}|
                    3(?<-cur>){3}|
                    4(?<-cur>){4}|
                    5(?<-cur>){5}|
                    6(?<-cur>){6}|
                    7(?<-cur>){7}|
                    8(?<-cur>){8}|
                    9(?<-cur>){9}
                )
                .{10}
                (?(pos)(?!))
                ((?<-pos>\d{11})|(?<=^.{10})(?=(?>(?<-pos>.)*)))*
                ,.*
            )
        )
        (?(first)
            (?>((?<-cur>){10})?)
            (?(cur)(?<-cur>)(?(cur)(?!))(?<cur>){10})
            (?<-first>)
        |
            (?<-cur>)
            (?(cur)
                (?(cur)(?<-cur>)){9}
                (?(cur)
                    (?<-cur>)(?(cur)(?!))(?<cur>){10}
                |
                    .*$(?<end>)
                )
            )
        )
        (.{11}|$(?<end>))
    )*(?<-end>)(?(cur)(?!))
)

```

This made me think of the final level of Manufactoria... But I think .NET regex, which is obviously no longer "regular", can solve any problems in PH. And this is just an algorithm in L.

# Answer
> 6 votes
### Score: 24

I think this works...

```
Regex                                                                                Modifiers   Replacement             Repeat?
(?|(\d*)(\d)(,\d*)(\d)|(^,?\d*)(\d)|, |^,)                                                                                <none>      $1$3 $2$4               Yes
$                                                                                <none>      ;111111111234567890     No
0|(?|(;.*)|9(?=.*(1{9}))|8(?=.*(1{8}))|7(?=.*(1{7}))|6(?=.*(1{6}))|5(?=.*(1{5}))|4(?=.*(1{4}))|3(?=.*(111))|2(?=.*(11)))    g           $1                      No
 1{10}                                                                                <none>      1                       Yes
 (?|1{9}(?=.*(9))|1{8}(?=.*(8))|1{7}(?=.*(7))|1{6}(?=.*(6))|1{5}(?=.*(5))|1{4}(?=.*(4))|1{3}(?=.*(3))|1{2}(?=.*(2))|)       g            $1                     No
 (?!\d)(?=.*(0))| |;.*                                                                                g           $1                      No

```

I haven't spent much time golfing the individual regular expressions yet. I will try to post an explanation soon, but it's getting late now. In the meantime, here's the result between each step:

```
'47,987'
' 9 48 77'
' 9 48 77;111111111234567890'
' 111111111 111111111111 11111111111111;111111111234567890'
'1  111 1111;111111111234567890'
'1  3 4;111111111234567890'
'1034'

```

Full perl program:

```
$_ = <>;
chomp;

do {
    $old = $_;
    s/(?|(\d*)(\d)(,\d*)(\d)|(^,?\d*)(\d)|, |^,)/$1$3 $2$4/;
} while ($old ne $_);

s/$/;111111111234567890/;

s/0|(?|(;.*)|9(?=.*(1{9}))|8(?=.*(1{8}))|7(?=.*(1{7}))|6(?=.*(1{6}))|5(?=.*(1{5}))|4(?=.*(1{4}))|3(?=.*(111))|2(?=.*(11)))/$1/g;

do {
    $old = $_;
    s/ 1{10}/1 /;
} while ($old ne $_);

s/ (?|1{9}(?=.*(9))|1{8}(?=.*(8))|1{7}(?=.*(7))|1{6}(?=.*(6))|1{5}(?=.*(5))|1{4}(?=.*(4))|1{3}(?=.*(3))|1{2}(?=.*(2))|)/ $1/g;

s/ (?!\d)(?=.*(0))| |;.*/$1/g;

print "$_\n";

```

# Answer
> 5 votes
### Any regex flavor, 41

```
    s/0/d/g
    ...
    s/9/dxxxxxxxxx/g
rep s/xd/dxxxxxxxxxxx/g
    s/[d,]//g
rep s/(^|d)xxxxxxxxxx/xd/g
    s/(^|d)xxxxxxxxx/9/g
    ...
    s/(^|d)x/1/g
    s/d/0/g

```

Let's try unary. `d` serves for a digit order separator, `x` stores the value. First we unarise each digit, then we squeeze the x10 multipliers to the left, then drop all separators, then back-insert the multipliers, then convert each order back to digits.

# Answer
> 5 votes
# .NET Regex, 14

Not as good as user23013's solution, but it was fun. None of the replacements have modifiers.

The reason for the .NET regex isn't because of balancing groups for once — I just tested with Retina, which uses .NET, and I also found that the variable length lookbehinds helped a lot.

## Replacement 1 (repeat = no)

Regex:

```
\d(?=\d+$)|\d(?=\d+,)|\d(?=,(\d+)$)|(?<=(\d+),\d*)\d$

```

Replacement

```
0$1$2

```

Swap the two numbers, padding to have the same number of leading zeroes.

## Replacement 2 (repeat = no)

Regex:

```
(\d+)

```

Replacement:

```
 $1

```

Add a space before each number

## Replacement 3 (repeat = no)

```
$

```

Replacement:

```
&0 ~00000 ~00101 ~00202 ~00303 ~00404 ~00505 ~00606 ~00707 ~00808 ~00909 ~01001 ~01102 ~01203 ~01304 ~01405 ~01506 ~01607 ~01708 ~01809 ~01910 ~02002 ~02103 ~02204 ~02305 ~02406 ~02507 ~02608 ~02709 ~02810 ~02911 ~03003 ~03104 ~03205 ~03306 ~03407 ~03508 ~03609 ~03710 ~03811 ~03912 ~04004 ~04105 ~04206 ~04307 ~04408 ~04509 ~04610 ~04711 ~04812 ~04913 ~05005 ~05106 ~05207 ~05308 ~05409 ~05510 ~05611 ~05712 ~05813 ~05914 ~06006 ~06107 ~06208 ~06309 ~06410 ~06511 ~06612 ~06713 ~06814 ~06915 ~07007 ~07108 ~07209 ~07310 ~07411 ~07512 ~07613 ~07714 ~07815 ~07916 ~08008 ~08109 ~08210 ~08311 ~08412 ~08513 ~08614 ~08715 ~08816 ~08917 ~09009 ~09110 ~09211 ~09312 ~09413 ~09514 ~09615 ~09716 ~09817 ~09918 ~10001 ~10102 ~10203 ~10304 ~10405 ~10506 ~10607 ~10708 ~10809 ~10910 ~11002 ~11103 ~11204 ~11305 ~11406 ~11507 ~11608 ~11709 ~11810 ~11911 ~12003 ~12104 ~12205 ~12306 ~12407 ~12508 ~12609 ~12710 ~12811 ~12912 ~13004 ~13105 ~13206 ~13307 ~13408 ~13509 ~13610 ~13711 ~13812 ~13913 ~14005 ~14106 ~14207 ~14308 ~14409 ~14510 ~14611 ~14712 ~14813 ~14914 ~15006 ~15107 ~15208 ~15309 ~15410 ~15511 ~15612 ~15713 ~15814 ~15915 ~16007 ~16108 ~16209 ~16310 ~16411 ~16512 ~16613 ~16714 ~16815 ~16916 ~17008 ~17109 ~17210 ~17311 ~17412 ~17513 ~17614 ~17715 ~17816 ~17917 ~18009 ~18110 ~18211 ~18312 ~18413 ~18514 ~18615 ~18716 ~18817 ~18918 ~19010 ~19111 ~19212 ~19313 ~19414 ~19515 ~19616 ~19717 ~19818 ~19919

```

Add a carry bit (the `&0`) as well as the giant lookup table of `<c> <a> <b> <carry of a+b+c> <last digit of a+b+c>`.

## Replacement 4 (repeat = yes)

Regex:

```
(?<=(\d),.*(\d)&)(\d)(?=.*~\3\1\2(.))|(\d)(?=,.*\d&)|(?<=\d,.*)(\d)(?=&)|^(?=.* .*(\d),.*(\d)&(\d).*~\9\7\8.(.))

```

Replacement:

```
$4$10

```

Keep taking the last digits of each number, and find their (sum, carry). Put the sum at the start of the string and replace the carry.

## Replacement 5 (repeat = no)

Regex:

```
^0*| .*

```

Replacement:

```
<empty>

```

Clean up.

# Example run

```
Repl no.        String
(input)         1428,57
1               000057,001428
2                000057, 001428
3                000057, 001428&0 <lookup table>
4               5 00005, 00142&1 <lookup table>
4               85 0000, 0014&0 <lookup table>
4               485 000, 001&0 <lookup table>
4               1485 00, 00&0 <lookup table>
4               01485 0, 0&0 <lookup table>
4               001485 , &0 <lookup table>
5               1485

```

---

<sup>(By combining a few of the steps I can get 12, but since it gets pretty messy and won't win anyway I think I'll keep this more elegant version up instead.)</sup>

# Answer
> 4 votes
**Score: ~~50~~ ~~40~~ ~~31~~ 21**

Thanks for this excellent challenge. This solution isn't very elegant, but, given the restrictions, I couldn't see any way to handle a digit generically in the output.

This solution features capture groups that sometimes don't match and relies on them being empty when that occurs. This works in Perl, though it normally produces a warning.

```
Regex 1:     (((((((((9)|8)|7)|6)|5)|4)|3)|2)|1)|0
Modifiers:   g
Replacement: <$1$2$3$4$5$6$7$8$9>
Repeat:      no

Regex 2:     (.*)<(\d*)>(,.*)<(\d*)>|(.*)<(\d*)>(.*)|(?:(^[^<]*)b(\d*)c)?(b)\d{9}(\d)(\d*)(c)
Modifiers:   none
Replacement: \8\1\5\3b$9$11\2\6\4c\7$10$12$13
Repeat:      yes

Regexes 3-12: ,?baaaaaaaaac
Modifiers:    g
Replacement:  9 etc. (one for each digit)

```

Full Perl code sample, with explanation and printing of intermediate results:

```
no warnings;
use 5.16.0;

$_ = '47,987';

#Convert numbers to beans
s/(((((((((9)|8)|7)|6)|5)|4)|3)|2)|1)|0/<$1$2$3$4$5$6$7$8$9>/g;

say;
my $last;

#Combine pairs of digits, starting with least significant.
do {
    $last=$_;
    s/(.*)<(\d*)>(,.*)<(\d*)>|(.*)<(\d*)>(.*)|(?:(^[^<]*)b(\d*)c)?(b)\d{9}(\d)(\d*)(c)/\8\1\5\3b$9$11\2\6\4c\7$10$12$13/;
    say;
}
while ($last ne $_);

#Convert beans back to numbers.
s/,?b\d{9}c/9/g;
s/,?b\d{8}c/8/g;
s/,?b\d{7}c/7/g;
s/,?b\d{6}c/6/g;
s/,?b\d{5}c/5/g;
s/,?b\d{4}c/4/g;
s/,?b\d{3}c/3/g;
s/,?b\d{2}c/2/g;
s/,?b\d{1}c/1/g;
s/,?bc/0/g;

say;

```

*Update: I was able to combine two of the looping regexes together, saving 10.*

*Update 2: I managed to crack the input digit conversion with a single regex.*

*Update 3: I reduced to a single looping regex.*

---
Tags: code-challenge, string, arithmetic, regular-expression
---


title: HTML2JSON Converter

text:
# Question
Title: HTML2JSON Converter
## *Edit*

I have posted a 250 lines reference implementation for review at CR, discussing the major class of the code. Download the complete Visual Studio 2013, .NET 4.5 source code (10 kB) from my server.

## Story

This is based on a real world puzzle.

A colleague had a very old program. It was announced to be discontinued by the company and then it was really discontinued in 2009. Now I should use that program as well, but it is full of bugs and I refused to use it. Instead I wanted to help my colleague and converted the content into a reusable format so we could import it to any other program.

The data is in a database, but the scheme is horrible because it creates new tables every now and then, so doing a SQL export was not feasible. The program also does not have an export functionality. But it has a reporting capability. Bad luck: reporting to Excel fails, because the output is larger than the 65.000 lines allowed by the only old excel format it supports. The only option left was reporting to HTML.

## Task

Given

* input is a HTML document
* it seems to be created by Microsoft Active Report, which shouldn't really matter. But for the sake of equality, your code must not use any Active Report specific library to parse the HTML (if such a thing exists)
* The reports is hierarchically structured in either 2 or 3 levels.
* the HTML is horrible (IMHO), it consists of DIVs and SPANs only, each having a @style attribute specified. The *left* position of the style at a SPAN can be used to detect the indentation, which allows conclusions to get the number of levels.
* there is always one SPAN which defines the key. The key is formatted in bold and ends with a colon (use whatever you want to detect it)
* The key may be followed by another SPAN which defines the value. If the value is not present, it shall be considered as an empty string.
* if a key reappears on the same level, that's the start of a new item

you

* create a valid JSON file as output
* the JSON needn't be pretty-printed, just valid
* non-breaking spaces can be converted to normal spaces or be Unicode 00A0
* remove the NOBR tags from the output
* ignore any unneeded information like the page number (last SPAN in a DIV), HEAD and STYLE before the first DIV
* use the key as the property name (remove the trailing colon and the spaces)
* use the value as the property value
* create an array property called `Children` for the items on the next level

As far as I can tell, the HTML is technically ok. All tags are closed etc. but it's not XHTML. You needn't do any error checking on it.

Side note: I don't need your code to solve a task or homework. I have already implemented a converter but to a different output format.

## Rules

Code Golf. The shortest code wins. Hopefully the task is complex enough to make it hard for special golfing languages so that other languages have a chance as well.

Libraries are allowed. Loophole libraries specially crafted for this task shall be downvoted.

Answer with shortest code on 2015-03-14 gets accepted.

## Sample

The code shall be able to process all kinds of reports the program produces, so do not hard code any keys or values. Here's an anonymized 2 page except of one of the reports.

```

        <title>
            ActiveReports Document
        </title><meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8" />

                <nobr>Requirement Name:</nobr>
                <nobr>Activate Golf</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>Average</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Activate Golf</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Activate Golf Settings</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>Add Balls</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>Low</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>High</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Download Golf Puzzles from Internet</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>Add Player</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>Average</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Golf Upload Puzzles to Server</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>GLFD</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>High</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Page 1 of 115</nobr>

                <nobr>Requirement Name:</nobr>
                <nobr>Count dimples</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>Low</nobr>
                <nobr>Status:</nobr>
                <nobr>Failed</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Low</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Add dimples</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Create divot</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Repair divot</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Modify divot</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>Use iron</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>High</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Go fairway</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Analyze trajectory</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Collect ball</nobr>
                <nobr>Test Name:</nobr>
                <nobr>Exchange ball</nobr>
                <nobr>Requirement Name:</nobr>
                <nobr>你好</nobr>
                <nobr>Description:</nobr>
                <nobr>Risk:</nobr>
                <nobr>High</nobr>
                <nobr>Status:</nobr>
                <nobr>In Progress</nobr>
                <nobr>Priorität QA:</nobr>
                <nobr>Average</nobr>
                <nobr>Page 2 of 115</nobr>

```

Expected JSON Output (handcrafted, please correct me if I added a typo):

```
{
    "Children":
    [
        {
            "RequirementName": "Activate Golf",
            "Description": "",
            "Risk": "Average",
            "Status": "In Progress",
            "PrioritätQA": "Average",
            "Children":
            [
                {
                    "TestName": "Activate Golf"
                },
                {
                    "TestName": "Activate Golf Settings"
                }
            ]
        },
        {
            "RequirementName": "Add Balls",
            "Description": "",
            "Risk": "Low",
            "Status": "In Progress",
            "PrioritätQA": "High",
            "Children":
            [
                {
                    "TestName": "Download Golf Puzzles from Internet"
                }
            ]
        },
        {
            "RequirementName": "Add Player",
            "Description": "",
            "Risk": "Average",
            "Status": "In Progress",
            "PrioritätQA": "Average",
            "Children":
            [
                {
                    "TestName": "Golf Upload Puzzles to Server"
                }
            ]
        },
        {
            "RequirementName": "GLFD",
            "Description": "",
            "Risk": "High",
            "Status": "In Progress",
            "Priorität QA": "Average",
            "Children":
            [
            ]
        },
        {
            "RequirementName": "Count dimples",
            "Description": "",
            "Risk": "Low",
            "Status": "Failed",
            "PrioritätQA": "Low",
            "Children":
            [
                {
                    "TestName": "Add dimples"
                },
                {
                    "TestName": "Create divot"
                },
                {
                    "TestName": "Repair divot"
                },
                {
                    "TestName": "Modify divot"
                }
            ]
        },
        {
            "RequirementName": "Use iron",
            "Description": "",
            "Risk": "High",
            "Status": "In Progress",
            "PrioritätQA": "Average",
            "Children":
            [
                {
                    "TestName": "Go fairway"
                },
                {
                    "TestName": "Analyze trajectory"
                },
                {
                    "TestName": "Collect ball"
                },
                {
                    "TestName": "Exchange ball"
                }
            ]
        },
        {
            "RequirementName": "你好",
            "Description": "",
            "Risk": "High",
            "Status": "In Progress",
            "PrioritätQA": "Average",
            "Children":
            [
            ]
        }
    ]
}

```

# Answer
> 2 votes
# VBScript 819 (if line endings count as 1)

VBScript is a Microsoft scripting language unrelated to VBA, VB.net or legacy VB6

For those of you that have never seen it:

VBScript is NOT designed for golfing and I am not great at golfind anyway so the best I can do is 819. If you see a way to make it shorter please comment.

To run this code use:

```
cscript //nologo //u html2json.vbs < html2json.html > html2json.json

```

This code does not indent the json properly but keeping the indent level would have made it even longer. The other thing that differs from the example json is that this code doesn't produce empty Children arrays that aren't there in the html - I hope that's ok. Here is the code:

```
Set W=WScript
Set S=W.Stdin
W.Echo"{"
Do
While InStr(a,":abs")<1
a=S.Readline
If a=""Then W.Echo"}]}":W.Quit
Wend
Do
If InStr(a,">Page&")<1Then
a=Replace(a," "," ")
Do
B=InStr(a,"&#")+2
If B<3Then Exit Do
C=InStr(B,a,";")
a=Left(a,B-3)&Chr(Mid(a,B,C-B))&Mid(a,C+1)
Loop
D=InStr(a,"<nobr>")+6
E=InStr(D,a,"</nobr>")
V=Mid(a,D,E-D)
F=InStr(a,"top:")+4
G=InStr(F,a,"in;")
T=Mid(a,F,G-F)
If T=U Then
W.Echo X&""""&K&""":"""&V&"""":X=","
K=""
Else
If K<>""Then W.Echo X&""""&K&""":""""":X=","
K=Left(V,Len(V)-1)
K=Replace(K," ","")
P=InStr(a,"left:")+5
Q=InStr(P,a,"in;")
L=Mid(a,P,Q-P)
If L>M Then W.Echo X&"""Children"":[":X=""Else If Abs(T-U)>.3And U>0Then W.Echo"}":X=","
If L<M Then W.Echo"]}":X=","
If Abs(T-U)>.3Then W.Echo X&"{":X=""
End If
End If
a=S.Readline
Loop While InStr(a,">Page ")<0
U=T
M=L
Loop

```

# Answer
> 0 votes
## C# - 1716

Ok, this one was rather simple for me, but that might be the reason why it is not very short. I just golfed the reference implementation (including all parts, not only the part that is posted on Code Review):

```
namespace System{using Collections.Generic;using Globalization;using IO;using Linq;using ExCSS;using HtmlAgilityPack;using Newtonsoft.Json;class J:JsonConverter{Dictionary<string,string>P=new Dictionary<string,string>();List<J>C=new List<J>();decimal L;J V{get;set;}static void Main(string[]a){J j=new J();j.H(a[0]);File.WriteAllText(a[1],JsonConvert.SerializeObject(j,j));}public override void WriteJson(JsonWriter w,object o,JsonSerializer s){J j=(J)o;w.WriteStartObject();foreach(var p in j.P){w.WritePropertyName(p.Key);w.WriteValue(p.Value);}if(j.C.Count>0){w.WritePropertyName("Children");w.WriteStartArray();foreach(J c in j.C)s.Serialize(w,c);w.WriteEndArray();}w.WriteEndObject();}public override object ReadJson(JsonReader r,Type t,object o,JsonSerializer s){return o;}public override bool CanConvert(Type o){return o==typeof(J);}void H(string f){var h=new HtmlDocument();h.LoadHtml(File.ReadAllText(f));J v=this;foreach(var p in h.DocumentNode.Descendants().Where(x=>(x.Name=="div"&&x.Ancestors("div").Any()))){var k="";foreach(var s in p.Descendants().Where(x=>x.Name=="span")){var d=new Parser().Parse(".d{"+s.Attributes["style"].Value+"}").StyleRules[0].Declarations;var t=Net.WebUtility.HtmlDecode(s.Descendants("nobr").First().InnerText);if(!d.Any(a=>a.Name=="font-weight"&&a.Term+""=="bold")){A(ref v,k,t);k="";}else{A(ref v,k,"");k=t.Trim(':');foreach(var l in from a in d where a.Name=="left"select decimal.Parse(a.Term.ToString().Replace("in",""),new NumberFormatInfo{NumberDecimalSeparator="."})){while(v.L>l)v=v.V;if(l>v.L){J c=new J{L=l,V=v};v.C.Add(c);v=c;}}}}}}void A(ref J j,string k,string v){if(k=="")return;if(j.P.ContainsKey(k)){J s=new J{L=j.L,V=j.V};j.V.C.Add(s);j=s;}j.P.Add(k,v);}}}

```

---
Tags: code-golf, json
---


title: Ambiguous Roman Numeral Magic Squares

text:
# Question
Title: Ambiguous Roman Numeral Magic Squares
The king of Ancient Rome is having difficulties determining if a magic square is valid or not, because the magic square he is checking does not include any separators between the numbers. He has hired a software engineer to help him determine if a magic square is valid or not.

**Input Description**

Input comes in on STDIN or command line arguments. You cannot have the input pre-initialised in a variable (e.g. "this program expects the input in a variable `x`"). Input is in the following format:

```
<top>,<middle>,<bottom>

```

Each of `<top>`, `<middle>`, and `<bottom>` is a string that will only ever contain the uppercase characters `I`, `V`, and `X`. It will not contain spaces or any other characters. Each string represents three Roman numerals, thus resulting in a 3x3 matrix of numbers. However, these Roman numerals may (but not necessarily) be *ambiguous*. Allow me to illustrate this with an example. Consider the following example row of three Roman numerals, with no spaces between each number:

```
IVIIIIX

```

Because there are no spaces between the letters, there are two possibilites to the numbers here:

* 1, 8, 9 (`I VIII IX`)
* 4, 3, 9 (`IV III IX`)

When you consider that all three rows of the matrix can be ambigious, there is the potential for there to be many different 3x3 matrixes from a single input.

Note that sequences such as 1, 7, 1, 9 (`I VII I IX`) are not possible because each row will always represent three Roman numerals. Also note that the Roman numerals must be valid, so sequences such as 1, 7, 8 (`I VII IIX`) are also not possible.

**Output Description**

Output:

* An integer `A`, where `A` is the number of unique 3x3 matrixes that can be formed from the ambigious input, and:
* A **truthy** value if *any* of the unique 3x3 matrixes form a magic square, or:
* A **falsy** value if *none* of the unique 3x3 matrixes form a magic square.

The truthy and falsy values must be consistent. They are seperated by a comma.

Some explanation is required on what is counted as unique. As long as a matrix does not have exactly the same numbers in exactly the same positions as a previously found matrix, it is counted as unique. This means that reflections, etc. of previously found matrixes are counted as unique.

**Example Inputs and Outputs**

In these examples, I use `true` as my truthy value and `false` as my falsy value.

Input: `VIIIIVI,IIIVVII,IVIXII` Output: `24,true` (The magic triangle is 8-1-6, 3-5-7, 4-9-2.)

Input: `IIIXVIII,IVIII,VIIII` Output: `210,false`

**Extras**

* You are not allowed to use inbuilt Roman Numeral conversion functions if your chosen language has one.

# Answer
# Perl, 219 ~~237~~

Line breaks added for clarity.

```
#!perl -p
%x=(I,1,IV,4,V,5,IX,9,X,10);
$a="(X{0,3}(?:V?I{1,3}|I?V|IX)|X{1,3})"x3;
m*^$a,$a,$a$(?{
  @z=map"$$_",0..9;
  $r|=!grep$x-$_,map{$x=eval s/./ $z[$&]/gr=~s/IX|IV|\S/+$x{$&}/gr}123,456,789,147,258,369,159,357;
  ++$-
})^*;
$_="$-,$r"

```

Test me.
> 4 votes

# Answer
# Prolog - 686

```
:-lib(util),lib(sd). r(S,R):-string_list(S,L),g(L,R). g(L,[N1,N2,N3]):-append(L1,X,L),append(L2,L3,X),n(L1,N1),n(L2,N2),n(L3,N3). n([73,86],4). n([73,88],9). n([73,73,73],3). n([73,73],2). n([73],1). n([86],5). n([86|N],D):-n(N,E),E<4,D is E+5. n([88|N],D):-n(N,E),D is E+10. n([88],10). m(M,[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3]):-split_string(M,",","",[X,Y,Z]),r(X,[X1,X2,X3]),r(Y,[Y1,Y2,Y3]),r(Z,[Z1,Z2,Z3]). a(L):-alldifferent(L),L=[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3],l(X1,X2,X3,T),l(Y1,Y2,Y3,T),l(Z1,Z2,Z3,T),l(X1,Y1,Z1,T),l(X2,Y2,Z2,T),l(X3,Y3,Z3,T). l(A,B,C,T):-T is A+B+C. p:-read_line(S),findall(L,m(S,L),A),length(A,C),findall(L,(member(L,A),a(L)),B),(B=[_|_]->R=true;R=false),writeln((C,R)).

```

# Ungolfed

```
% I : 73
% V : 86
% X : 88
:-lib(util).
:-lib(sd).
r(S,R) :- string_list(S,L), g(L,R).
g(L,[N1,N2,N3]):-
    append(L1,X,L),
    append(L2,L3,X),
    n(L1,N1),n(L2,N2),n(L3,N3).
n([73,86],4).
n([73,88],9).
n([73,73,73],3).
n([73,73],2).
n([73],1).
n([86],5).
n([86|N],D):-n(N,E),E<4,D is E+5.
n([88|N],D):-n(N,E), D is E+10.
n([88],10).
m(M,[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3]) :-
    split_string(M,",","",[X,Y,Z]),
    r(X,[X1,X2,X3]),
    r(Y,[Y1,Y2,Y3]),
    r(Z,[Z1,Z2,Z3]).
a(L) :-
    alldifferent(L),
    L=[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3],
    l(X1,X2,X3,T),
    l(Y1,Y2,Y3,T),
    l(Z1,Z2,Z3,T),
    l(X1,Y1,Z1,T),
    l(X2,Y2,Z2,T),
    l(X3,Y3,Z3,T).
l(A,B,C,T):-T is A+B+C.
p :- read_line(S),
     findall(L,m(S,L),A),
     length(A,C),
     findall(L,(member(L,A),a(L)),B),
     (B=[_|_]->R=true;R=false),
     writeln((C,R)).

```

Of course, `p` could also be defined as:

```
p :- read_line(S),
     findall(L,m(S,L),A),
     length(A,C),
     findall(L,(member(L,A),a(L)),B),
     writeln(C),
     B=[_|_].

```

In that case, the environment would say 'Yes' or 'No' after writing the number of squares.

# Example

Using eclipse.

```
[eclipse 105]: p.
 VIIIIVI,IIIVVII,IVIXII
24, true

[eclipse 106]: p.
 IIIXVIII,IVIII,VIIII
210, false

```

Example results for the second one are pasted here.
> 4 votes

# Answer
## Python, 442 chars

```
R=range
L=len
S=sum
N={}
for i in R(40):
 r="";j=i
 while j>9:r+="X";j-=10
 if j>8:r+="IX";j-=9
 if j>4:r+="V";j-=5
 if j>3:r+="IV";j-=4
 N[r+"III"[:j]]=i
a,b,c=map(lambda x:sum([[Z]*all(Z)for i in R(L(x))for j in R(L(x))for Z in[map(N.get,(x[:i],x[i:j],x[j:]))]],[]),raw_input().split(","))
print L(a)*L(b)*L(c),any(S(x)==S(y)==S(z)==S(q[::3])==S(q[1::3])==S(q[2::3])==S(q[::4])==S(q[2:-1:2])for x in a for y in b for z in c for q in[x+y+z])

```

The code first builds `N` which is a mapping from roman numeral string to its value for all possible numbers we might need. Splits each line into three in every possible way and checks which of the resulting triples all have mappings in `N`. The final `any` sees if any combination is a magic square.
> 2 votes

# Answer
# Haskell, 451 429 423 bytes

```
import Data.List
(#)=splitAt
(%)=map
w=length
r"X"=10
r('X':a)=10+r a
r a=case elemIndex a["I","II","III","IV","V","VI","VII","VIII","IX"]of Just i->i+1;_->0
s l=[r%[a,b,c]|x<-[2..w l],y<-[1..x],let(d,c)=x#l;(a,b)=y#d,r a*r b*r c>0]
e[a,b,c]=a==b&&a==c
p[l,m,n]=[1|a<-l,b<-m,c<-n,e$sum%[a,b,c],e$sum%(transpose[a,b,c])]
f i=(show$product$w%(s%i))++","++(show$0<(w$p$s%i))
q ','='\n'
q a=a
i=getLine>>=putStrLn.f.lines.map q

```

Usage:

```
*Main> i                           -- repl prompt, call i
VIIIIVI,IIIVVII,IVIXII             -- input via STDIN
24,True                            -- output
*Main> i
IIIXVIII,IVIII,VIIII
210,False

```

About 70 bytes just to get the input and output format right.

The function `r` converts a roman number (given as a string) to an integer (if it's not a valid roman number `0` is returned). `s` splits a string of roman digits into 3 substring and keeps those triples with valid roman numbers and converts them via `r` to integers . `e` checks if all integers of a three element list are equal. `p` takes three strings of roman digits, splits them via `s` into lists of integers, combines one integer of each list to triples and keeps those with equal sums in all directions. `f` calculates the number of valid matrices and checks if `p` returns the empty list (no valid solution) or not (valid solution exists). The main function `i` reads the input from STDIN, converts it to a list of strings (`q` helps by replacing `,` with `\n`) and calls `p`.
> 2 votes

# Answer
# R, ~~489~~ ~~474~~ 464

This got a lot bigger than I wanted, but I suspect I can golf it down a bit.

It uses a brute force method, by calculating all the possible Roman Numeral combinations and their corresponding digits.

Once that is done it compares the input to the Roman Numeral list and gets the possible digits.

From there it goes through each matrix of numbers and test for the magic square, finally outputting the result.

```
s=strsplit;e=expand.grid;P=paste0;d=do.call;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[n];p=d(P,e(r,r,r));n=d(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=F;N=nrow(C);for(n in 1:N){T=matrix(strtoi(unlist(C[n,])),nr=3);E=E||length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1};P(N,',',any(E))

```

Test Run. It waits for input once pasted into the RGui.

```
> e=expand.grid;l=length;s=strsplit;P=paste0;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[-40];p=do.call(P,e(r,r,r));n=do.call(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=c();N=nrow(C);for(n in 1:N){T=matrix(as.integer(unlist(C[n,])),nr=3);E=c(E,length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1)};paste(N,',',any(E))
VIIIIVI,IIIVVII,IVIXII
[1] "24 , TRUE"
> e=expand.grid;l=length;s=strsplit;P=paste0;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[-40];p=do.call(P,e(r,r,r));n=do.call(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=c();N=nrow(C);for(n in 1:N){T=matrix(as.integer(unlist(C[n,])),nr=3);E=c(E,length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1)};paste(N,',',any(E))
IIIXVIII,IVIII,VIIII
[1] "210 , FALSE"
>

```
> 1 votes

---
Tags: code-golf, roman-numerals
---


# Question
Title: Gotta Match Them All! Write a regex to match the original 151 Pokemon but no subsequent Pokemon
The original 151 Pokemon, in an array format suitable for initializers:

```
["Bulbasaur", "Ivysaur", "Venusaur", "Charmander", "Charmeleon", "Charizard", "Squirtle", "Wartortle", "Blastoise", "Caterpie", "Metapod", "Butterfree", "Weedle", "Kakuna", "Beedrill", "Pidgey", "Pidgeotto", "Pidgeot", "Rattata", "Raticate", "Spearow", "Fearow", "Ekans", "Arbok", "Pikachu", "Raichu", "Sandshrew", "Sandslash", "Nidorina", "Nidoqueen", "Nidoran", "Nidorino", "Nidoking", "Clefairy", "Clefable", "Vulpix", "Ninetales", "Jigglypuff", "Wigglytuff", "Zubat", "Golbat", "Oddish", "Gloom", "Vileplume", "Paras", "Parasect", "Venonat", "Venomoth", "Diglett", "Dugtrio", "Meowth", "Persian", "Psyduck", "Golduck", "Mankey", "Primeape", "Growlithe", "Arcanine", "Poliwag", "Poliwhirl", "Poliwrath", "Abra", "Kadabra", "Alakazam", "Machop", "Machoke", "Machamp", "Bellsprout", "Weepinbell", "Victreebel", "Tentacool", "Tentacruel", "Geodude", "Graveler", "Golem", "Ponyta", "Rapidash", "Slowpoke", "Slowbro", "Magnemite", "Magneton", "Farfetch'd", "Doduo", "Dodrio", "Seel", "Dewgong", "Grimer", "Muk", "Shellder", "Cloyster", "Gastly", "Haunter", "Gengar", "Onix", "Drowzee", "Hypno", "Krabby", "Kingler", "Voltorb", "Electrode", "Exeggcute", "Exeggutor", "Cubone", "Marowak", "Hitmonlee", "Hitmonchan", "Lickitung", "Koffing", "Weezing", "Rhyhorn", "Rhydon", "Chansey", "Tangela", "Kangaskhan", "Horsea", "Seadra", "Goldeen", "Seaking", "Staryu", "Starmie", "Mr. Mime", "Scyther", "Jynx", "Electabuzz", "Magmar", "Pinsir", "Tauros", "Magikarp", "Gyarados", "Lapras", "Ditto", "Eevee", "Vaporeon", "Jolteon", "Flareon", "Porygon", "Omanyte", "Omastar", "Kabuto", "Kabutops", "Aerodactyl", "Snorlax", "Articuno", "Zapdos", "Moltres", "Dratini", "Dragonair", "Dragonite", "Mewtwo", "Mew"]

```

I have omitted the male-female Nidoran distinction because it shouldn't affect any regex generation.

And all subsequent Pokemon:

```
["Chikorita", "Bayleef", "Meganium", "Cyndaquil", "Quilava", "Typhlosion", "Totodile", "Croconaw", "Feraligatr", "Sentret", "Furret", "Hoothoot", "Noctowl", "Ledyba", "Ledian", "Spinarak", "Ariados", "Crobat", "Chinchou", "Lanturn", "Pichu", "Cleffa", "Igglybuff", "Togepi", "Togetic", "Natu", "Xatu", "Mareep", "Flaaffy", "Ampharos", "Bellossom", "Marill", "Azumarill", "Sudowoodo", "Politoed", "Hoppip", "Skiploom", "Jumpluff", "Aipom", "Sunkern", "Sunflora", "Yanma", "Wooper", "Quagsire", "Espeon", "Umbreon", "Murkrow", "Slowking", "Misdreavus", "Unown", "Wobbuffet", "Girafarig", "Pineco", "Forretress", "Dunsparce", "Gligar", "Steelix", "Snubbull", "Granbull", "Qwilfish", "Scizor", "Shuckle", "Heracross", "Sneasel", "Teddiursa", "Ursaring", "Slugma", "Magcargo", "Swinub", "Piloswine", "Corsola", "Remoraid", "Octillery", "Delibird", "Mantine", "Skarmory", "Houndour", "Houndoom", "Kingdra", "Phanpy", "Donphan", "Porygon2", "Stantler", "Smeargle", "Tyrogue", "Hitmontop", "Smoochum", "Elekid", "Magby", "Miltank", "Blissey", "Raikou", "Entei", "Suicune", "Larvitar", "Pupitar", "Tyranitar", "Lugia", "Ho-Oh", "Celebi", "Treecko", "Grovyle", "Sceptile", "Torchic", "Combusken", "Blaziken", "Mudkip", "Marshtomp", "Swampert", "Poochyena", "Mightyena", "Zigzagoon", "Linoone", "Wurmple", "Silcoon", "Beautifly", "Cascoon", "Dustox", "Lotad", "Lombre", "Ludicolo", "Seedot", "Nuzleaf", "Shiftry", "Taillow", "Swellow", "Wingull", "Pelipper", "Ralts", "Kirlia", "Gardevoir", "Surskit", "Masquerain", "Shroomish", "Breloom", "Slakoth", "Vigoroth", "Slaking", "Nincada", "Ninjask", "Shedinja", "Whismur", "Loudred", "Exploud", "Makuhita", "Hariyama", "Azurill", "Nosepass", "Skitty", "Delcatty", "Sableye", "Mawile", "Aron", "Lairon", "Aggron", "Meditite", "Medicham", "Electrike", "Manectric", "Plusle", "Minun", "Volbeat", "Illumise", "Roselia", "Gulpin", "Swalot", "Carvanha", "Sharpedo", "Wailmer", "Wailord", "Numel", "Camerupt", "Torkoal", "Spoink", "Grumpig", "Spinda", "Trapinch", "Vibrava", "Flygon", "Cacnea", "Cacturne", "Swablu", "Altaria", "Zangoose", "Seviper", "Lunatone", "Solrock", "Barboach", "Whiscash", "Corphish", "Crawdaunt", "Baltoy", "Claydol", "Lileep", "Cradily", "Anorith", "Armaldo", "Feebas", "Milotic", "Castform", "Kecleon", "Shuppet", "Banette", "Duskull", "Dusclops", "Tropius", "Chimecho", "Absol", "Wynaut", "Snorunt", "Glalie", "Spheal", "Sealeo", "Walrein", "Clamperl", "Huntail", "Gorebyss", "Relicanth", "Luvdisc", "Bagon", "Shelgon", "Salamence", "Beldum", "Metang", "Metagross", "Regirock", "Regice", "Registeel", "Latias", "Latios", "Kyogre", "Groudon", "Rayquaza", "Jirachi", "Deoxys", "Turtwig", "Grotle", "Torterra", "Chimchar", "Monferno", "Infernape", "Piplup", "Prinplup", "Empoleon", "Starly", "Staravia", "Staraptor", "Bidoof", "Bibarel", "Kricketot", "Kricketune", "Shinx", "Luxio", "Luxray", "Budew", "Roserade", "Cranidos", "Rampardos", "Shieldon", "Bastiodon", "Burmy", "Wormadam", "Mothim", "Combee", "Vespiquen", "Pachirisu", "Buizel", "Floatzel", "Cherubi", "Cherrim", "Shellos", "Gastrodon", "Ambipom", "Drifloon", "Drifblim", "Buneary", "Lopunny", "Mismagius", "Honchkrow", "Glameow", "Purugly", "Chingling", "Stunky", "Skuntank", "Bronzor", "Bronzong", "Bonsly", "Mime Jr.", "Happiny", "Chatot", "Spiritomb", "Gible", "Gabite", "Garchomp", "Munchlax", "Riolu", "Lucario", "Hippopotas", "Hippowdon", "Skorupi", "Drapion", "Croagunk", "Toxicroak", "Carnivine", "Finneon", "Lumineon", "Mantyke", "Snover", "Abomasnow", "Weavile", "Magnezone", "Lickilicky", "Rhyperior", "Tangrowth", "Electivire", "Magmortar", "Togekiss", "Yanmega", "Leafeon", "Glaceon", "Gliscor", "Mamoswine", "Porygon-Z", "Gallade", "Probopass", "Dusknoir", "Froslass", "Rotom", "Uxie", "Mesprit", "Azelf", "Dialga", "Palkia", "Heatran", "Regigigas", "Giratina", "Cresselia", "Phione", "Manaphy", "Darkrai", "Shaymin", "Arceus", "Victini", "Snivy", "Servine", "Serperior", "Tepig", "Pignite", "Emboar", "Oshawott", "Dewott", "Samurott", "Patrat", "Watchog", "Lillipup", "Herdier", "Stoutland", "Purrloin", "Liepard", "Pansage", "Simisage", "Pansear", "Simisear", "Panpour", "Simipour", "Munna", "Musharna", "Pidove", "Tranquill", "Unfezant", "Blitzle", "Zebstrika", "Roggenrola", "Boldore", "Gigalith", "Woobat", "Swoobat", "Drilbur", "Excadrill", "Audino", "Timburr", "Gurdurr", "Conkeldurr", "Tympole", "Palpitoad", "Seismitoad", "Throh", "Sawk", "Sewaddle", "Swadloon", "Leavanny", "Venipede", "Whirlipede", "Scolipede", "Cottonee", "Whimsicott", "Petilil", "Lilligant", "Basculin", "Sandile", "Krokorok", "Krookodile", "Darumaka", "Darmanitan", "Maractus", "Dwebble", "Crustle", "Scraggy", "Scrafty", "Sigilyph", "Yamask", "Cofagrigus", "Tirtouga", "Carracosta", "Archen", "Archeops", "Trubbish", "Garbodor", "Zorua", "Zoroark", "Minccino", "Cinccino", "Gothita", "Gothorita", "Gothitelle", "Solosis", "Duosion", "Reuniclus", "Ducklett", "Swanna", "Vanillite", "Vanillish", "Vanilluxe", "Deerling", "Sawsbuck", "Emolga", "Karrablast", "Escavalier", "Foongus", "Amoonguss", "Frillish", "Jellicent", "Alomomola", "Joltik", "Galvantula", "Ferroseed", "Ferrothorn", "Klink", "Klang", "Klinklang", "Tynamo", "Eelektrik", "Eelektross", "Elgyem", "Beheeyem", "Litwick", "Lampent", "Chandelure", "Axew", "Fraxure", "Haxorus", "Cubchoo", "Beartic", "Cryogonal", "Shelmet", "Accelgor", "Stunfisk", "Mienfoo", "Mienshao", "Druddigon", "Golett", "Golurk", "Pawniard", "Bisharp", "Bouffalant", "Rufflet", "Braviary", "Vullaby", "Mandibuzz", "Heatmor", "Durant", "Deino", "Zweilous", "Hydreigon", "Larvesta", "Volcarona", "Cobalion", "Terrakion", "Virizion", "Tornadus", "Thundurus", "Reshiram", "Zekrom", "Landorus", "Kyurem", "Keldeo", "Meloetta", "Genesect", "Chespin", "Quilladin", "Chesnaught", "Fennekin", "Braixen", "Delphox", "Froakie", "Frogadier", "Greninja", "Bunnelby", "Diggersby", "Fletchling", "Fletchinder", "Talonflame", "Scatterbug", "Spewpa", "Vivillon", "Litleo", "Pyroar", "Flabébé", "Floette", "Florges", "Skiddo", "Gogoat", "Pancham", "Pangoro", "Furfrou", "Espurr", "Meowstic", "Honedge", "Doublade", "Aegislash", "Spritzee", "Aromatisse", "Swirlix", "Slurpuff", "Inkay", "Malamar", "Binacle", "Barbaracle", "Skrelp", "Dragalge", "Clauncher", "Clawitzer", "Helioptile", "Heliolisk", "Tyrunt", "Tyrantrum", "Amaura", "Aurorus", "Sylveon", "Hawlucha", "Dedenne", "Carbink", "Goomy", "Sliggoo", "Goodra", "Klefki", "Phantump", "Trevenant", "Pumpkaboo", "Gourgeist", "Bergmite", "Avalugg", "Noibat", "Noivern", "Xerneas", "Yveltal", "Zygarde", "Diancie"]

```

# Answer
# Most flavours, ~~332~~ ~~331~~ ~~326~~ ~~325~~ 304 bytes

```
tly|glo|pix|y.?t|key|d.*sh|dod|iw|ung|r.*me|sa?.r$|ras|abr|aic|mac|g.e.*t|t.i?o$|wb|z..d|wg|kh|rs.a|le?s|lld|a.ow|yh|pn|(or.+o|g.*le|(gm|ub.?|o.l|(id.+|a.+n|olt|onc).).).$|^(..(.([lx]?$|g.y|fa|i?ka)|an?s|yd|eg)|.?ra?[bt]|vi.*e|f.?ar|ko|gy)|(t.r.|rt|ow.*|v|w).e|[kt]a.*u|g.l[abd]|e(ak|no|n.a|.dr|o.t|.*od)

```

Thanks to EMBLEM I had to revamp and restart, building a regex with a back-and-forth relay of manual part selection and Peter Norvig's golfer. Saved a whole bunch of bytes, and probably more is still possible, so I guess it was worth it?

Tested on Regex101 (includes `hoopa` and `volcanion`, since they aren't matched anyway)

If anyone's wondering, `seel` is the biggest pain to match, thanks to `registeel` and `seedot` in the other list. Other hard-to-match Pokemon include `hitmonchan` (thanks to `hitmontop` and `chandelure/donphan`),`jolteon` (thanks to `joltik` and half the `eevee` evolutions) and `porygon` (thanks to `flygon` and `porygon2/porygon-z`)
> 16 votes

---
Tags: code-golf, regular-expression
---


# Question
Title: Digit sum of central binomial coefficients
The task is simply to see how much faster you can calculate n choose n/2 (for even n) than the builtin function in python. Of course for large n this is a rather large number so rather than output the whole number you should output the sum of the digits. For example, for `n = 100000`, the answer is `135702`. For `n=1000000` it is `1354815`.

Here is the python code:

```
from scipy.misc import comb
def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n / 10
   return r
sum_digits(comb(n,n/2,exact=True))

```

Your score is `(highest n on your machine using your code)/(highest n on your machine using my code)`. Your code must terminate in 60 seconds or less.

Your program must give the correct output for all even n: 2 \<= n \<= (your highest n)

You can't use any builtin code or libraries which calculate binomial coefficients or values which can quickly be transformed into binomial coefficients.

You can use any language of your choice.

---

**Leading answer** The current leading answer with an amazing 680.09 is by justhalf.

# Answer
> 9 votes
# C++ (GMP) - (287,000,000 / 422,000) = 680.09

Shamelessly combine Kummer's Theorem by xnor and GMP by qwr. ~~Still not even close to the Go solution, not sure why.~~

**Edit:** Thanks Keith Randall for the reminder that multiplication is faster if the number is similar in size. I implemented multi-level multiplication, similar to memory coalescing concept on memory management. And the result is impressive. What used to take 51s, now takes only 0.5s (i.e., 100-fold improvement!!)

```
OLD CODE (n=14,000,000)
Done sieving in 0.343s
Done calculating binom in 51.929s
Done summing in 0.901s
14000000: 18954729

real    0m53.194s
user    0m53.116s
sys 0m0.060s

NEW CODE (n=14,000,000)
Done sieving in 0.343s
Done calculating binom in 0.552s
Done summing in 0.902s
14000000: 18954729

real    0m1.804s
user    0m1.776s
sys 0m0.023s

```

The run for `n=287,000,000`

```
Done sieving in 4.211s
Done calculating binom in 17.934s
Done summing in 37.677s
287000000: 388788354

real    0m59.928s
user    0m58.759s
sys 0m1.116s

```

The code. Compile with `-lgmp -lgmpxx -O3`

```
#include <gmpxx.h>
#include <iostream>
#include <time.h>
#include <cstdio>

const int MAX=287000000;
const int PRIME_COUNT=15700000;

int primes[PRIME_COUNT], factors[PRIME_COUNT], count;
bool sieve[MAX];
int max_idx=0;

void run_sieve(){
    sieve[2] = true;
    primes[0] = 2;
    count = 1;
    for(int i=3; i<MAX; i+=2){
        sieve[i] = true;
    }
    for(int i=3; i<17000; i+=2){
        if(!sieve[i]) continue;
        for(int j = i*i; j<MAX; j+=i){
            sieve[j] = false;
        }
    }
    for(int i=3; i<MAX; i+=2){
        if(sieve[i]) primes[count++] = i;
    }
}

mpz_class sum_digits(mpz_class n){
    clock_t t = clock();
    char* str = mpz_get_str(NULL, 10, n.get_mpz_t());
    int result = 0;
    for(int i=0;str[i]>0;i++){
        result+=str[i]-48;
    }
    printf("Done summing in %.3fs\n", ((float)(clock()-t))/CLOCKS_PER_SEC);
    return result;
}

mpz_class nc2_fast(const mpz_class &x){
    clock_t t = clock();
    int prime;
    const unsigned int n = mpz_get_ui(x.get_mpz_t());
    const unsigned int n2 = n/2;
    unsigned int m;
    unsigned int digit;
    unsigned int carry=0;
    unsigned int carries=0;
    mpz_class result = 1;
    mpz_class prime_prods = 1;
    mpz_class tmp;
    mpz_class tmp_prods[32], tmp_prime_prods[32];
    for(int i=0; i<32; i++){
        tmp_prods[i] = (mpz_class)NULL;
        tmp_prime_prods[i] = (mpz_class)NULL;
    }
    for(int i=0; i< count; i++){
        prime = primes[i];
        carry=0;
        carries=0;
        if(prime > n) break;
        if(prime > n2){
            tmp = prime;
            for(int j=0; j<32; j++){
                if(tmp_prime_prods[j] == NULL){
                    tmp_prime_prods[j] = tmp;
                    break;
                } else {
                    mpz_mul(tmp.get_mpz_t(), tmp.get_mpz_t(), tmp_prime_prods[j].get_mpz_t());
                    tmp_prime_prods[j] = (mpz_class)NULL;
                }
            }
            continue;
        }
        m=n2;
        while(m>0){
            digit = m%prime;
            carry = (2*digit + carry >= prime) ? 1 : 0;
            carries += carry;
            m/=prime;
        }
        if(carries>0){
            tmp = 0;
            mpz_ui_pow_ui(tmp.get_mpz_t(), prime, carries);
            for(int j=0; j<32; j++){
                if(tmp_prods[j] == NULL){
                    tmp_prods[j] = tmp;
                    break;
                } else {
                    mpz_mul(tmp.get_mpz_t(), tmp.get_mpz_t(), tmp_prods[j].get_mpz_t());
                    tmp_prods[j] = (mpz_class)NULL;
                }
            }
        }
    }
    result = 1;
    prime_prods = 1;
    for(int j=0; j<32; j++){
        if(tmp_prods[j] != NULL){
            mpz_mul(result.get_mpz_t(), result.get_mpz_t(), tmp_prods[j].get_mpz_t());
        }
        if(tmp_prime_prods[j] != NULL){
            mpz_mul(prime_prods.get_mpz_t(), prime_prods.get_mpz_t(), tmp_prime_prods[j].get_mpz_t());
        }
    }
    mpz_mul(result.get_mpz_t(), result.get_mpz_t(), prime_prods.get_mpz_t());
    printf("Done calculating binom in %.3fs\n", ((float)(clock()-t))/CLOCKS_PER_SEC);
    return result;
}

int main(int argc, char* argv[]){
    const mpz_class n = atoi(argv[1]);
    clock_t t = clock();
    run_sieve();
    printf("Done sieving in %.3fs\n", ((float)(clock()-t))/CLOCKS_PER_SEC);
    std::cout << n << ": " << sum_digits(nc2_fast(n)) << std::endl;
    return 0;
}

```

# Answer
> 7 votes
## Go, 33.96 = (16300000 / 480000)

```
package main

import "math/big"

const n = 16300000

var (
    sieve     [n + 1]bool
    remaining [n + 1]int
    count     [n + 1]int
)

func main() {
    println("finding primes")
    for p := 2; p <= n; p++ {
        if sieve[p] {
            continue
        }
        for i := p * p; i <= n; i += p {
            sieve[i] = true
        }
    }

    // count net number of times each prime appears in the result.
    println("counting factors")
    for i := 2; i <= n; i++ {
        remaining[i] = i
    }
    for p := 2; p <= n; p++ {
        if sieve[p] {
            continue
        }

        for i := p; i <= n; i += p {
            for remaining[i]%p == 0 { // may have multiple factors of p
                remaining[i] /= p

                // count positive for n!
                count[p]++
                // count negative twice for ((n/2)!)^2
                if i <= n/2 {
                    count[p] -= 2
                }
            }
        }
    }

    // ignore all the trailing zeros
    count[2] -= count[5]
    count[5] = 0

    println("listing factors")
    var m []uint64
    for i := 0; i <= n; i++ {
        for count[i] > 0 {
            m = append(m, uint64(i))
            count[i]--
        }
    }

    println("grouping factors")
    m = group(m)

    println("multiplying")
    x := mul(m)

    println("converting to base 10")
    d := 0
    for _, c := range x.String() {
        d += int(c - '0')
    }
    println("sum of digits:", d)
}

// Return product of elements in a.
func mul(a []uint64) *big.Int {
    if len(a) == 1 {
        x := big.NewInt(0)
        x.SetUint64(a[0])
        return x
    }
    m := len(a) / 2
    x := mul(a[:m])
    y := mul(a[m:])
    x.Mul(x, y) // fast because x and y are about the same length
    return x
}

// return a slice whose members have the same product
// as the input slice, but hopefully shorter.
func group(a []uint64) []uint64 {
    var g []uint64
    r := uint64(1)
    b := 1
    for _, x := range a {
        c := bits(x)
        if b+c <= 64 {
            r *= x
            b += c
        } else {
            g = append(g, r)
            r = x
            b = c
        }
    }
    g = append(g, r)
    return g
}

// bits returns the number of bits in the representation of x
func bits(x uint64) int {
    n := 0
    for x != 0 {
        n++
        x >>= 1
    }
    return n
}

```

Works by counting all the prime factors in the numerator and denominator and canceling matching factors. Multiplies the leftovers to get the result.

More than 80% of the time is spent in converting to base 10. There's got to be a better way to do that...

# Answer
> 6 votes
## Python 3 (8.8 = 2.2 million / 0.25 million)

This is in Python, which isn't known for speed, so you can probably do better porting this to another language.

Primes generator taken from this StackOverflow contest.

```
import numpy
import time

def primesfrom2to(n):
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[       k*k/3     ::2*k] = False
            sieve[k*(k-2*(i&1)+4)/3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]

t0 = time.clock()

N=220*10**4
n=N//2

print("N = %d" % N)
print()

print("Generating primes.")
primes = primesfrom2to(N)

t1 = time.clock()
print ("Time taken: %f" % (t1-t0))

print("Computing product.")
product = 1

for p in primes:
    p=int(p)
    carries = 0
    carry = 0

    if p>n:
        product*=p
        continue

    m=n

    #Count carries of n+n in base p as per Kummer's Theorem
    while m:
        digit = m%p
        carry = (2*digit + carry >= p)
        carries += carry
        m//=p

    if carries >0:
        for _ in range(carries):
            product *= p

    #print(p,carries,product)

t2 = time.clock()
print ("Time taken: %f" % (t2-t1))

print("Converting number to string.")

# digit_sum = 0
# result=product

# while result:
    # digit_sum+=result%10
    # result//=10

digit_sum = 0
digit_string = str(product)

t3 = time.clock()
print ("Time taken: %f" % (t3-t2))

print("Summing digits.")
for d in str(digit_string):digit_sum+=int(d)

t4 = time.clock()
print ("Time taken: %f" % (t4-t3))
print ()

print ("Total time: %f" % (t4-t0))
print()
print("Sum of digits = %d" % digit_sum)

```

The main idea of the algorithm is to use Kummer's Theorem to get the prime-factorization of the binomial. For each prime, we learn the highest power of it that divides the answer, and multiply the running product by that power of the prime. In this way, we only need to multiply once for each prime in the prime-factorization of the answer.

**Output showing time breakdown:**

```
N = 2200000
Generating primes.
Time taken: 0.046408
Computing product.
Time taken: 17.931472
Converting number to string.
Time taken: 39.083390
Summing digits.
Time taken: 1.502393

Total time: 58.563664

Sum of digits = 2980107

```

Surprisingly, most of the time is spent converting the number to a string to sum its digits. Also surprisingly, converting to a string was much faster than getting digits from repeated `%10` and `//10`, even though the whole string must presumably be kept in memory.

Generating the primes takes negligible time (and hence I don't feel unfair copying existing code). Summing digits is fast. The actual multiplication takes one third of the time.

Given that digit summing seems to be the limiting factor, perhaps an algorithm to multiply numbers in decimal representation would save time in total by shortcutting the binary/decimal conversion.

# Answer
> 3 votes
## Java (score 22500 / 365000 = 0.062)

I don't have Python on this machine, so if someone could score this I would be grateful. If not, it will have to wait.

The basis of this implementation is
$$\binom{2n}{n} = \sum\_{k=0}^n \binom{n}{k}^2$$

The bottleneck is the addition to compute the relevant section of Pascal's triangle (90% of running time), so using a better multiplication algorithm wouldn't really help.

Note that what the question calls `n` is what I call `2n`. The command-line argument is what the question calls `n`.

```
public class CodeGolf37270 {
    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("Usage: java CodeGolf37270 <n>");
            System.exit(1);
        }

        int two_n = Integer.parseInt(args[0]);
        // \binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2
        // Two cases:
        //   n = 2m: \binom{4m}{2m} = \binom{2m}{m}^2 + 2\sum_{k=0}^{m-1} \binom{2m}{k}^2
        //   n = 2m+1: \binom{4m+2}{2m+1} = 2\sum_{k=0}^{m} \binom{2m+1}{k}^2
        int n = two_n / 2;
        BigInt[] nCk = new BigInt[n/2 + 1];
        nCk[0] = new BigInt(1);
        for (int k = 1; k < nCk.length; k++) nCk[k] = nCk[0];
        for (int row = 2; row <= n; row++) {
            BigInt tmp = nCk[0];
            for (int col = 1; col < row && col < nCk.length; col++) {
                BigInt replacement = tmp.add(nCk[col]);
                tmp = nCk[col];
                nCk[col] = replacement;
            }
        }

        BigInt central = nCk[0]; // 1^2 = 1
        int lim = (n & 1) == 1 ? nCk.length : (nCk.length - 1);
        for (int k = 1; k < lim; k++) central = central.add(nCk[k].sq());
        central = central.add(central);
        if ((n & 1) == 0) central = central.add(nCk[nCk.length - 1].sq());

        System.out.println(central.digsum());
    }

    private static class BigInt {
        static final int B = 1000000000;
        private int[] val;

        public BigInt(int x) {
            val = new int[] { x };
        }

        private BigInt(int[] val) {
            this.val = val;
        }

        public BigInt add(BigInt that) {
            int[] left, right;
            if (val.length < that.val.length) {
                left = that.val;
                right = val;
            }
            else {
                left = val;
                right = that.val;
            }

            int[] sum = left.clone();
            int carry = 0, k = 0;
            for (; k < right.length; k++) {
                int a = sum[k] + right[k] + carry;
                sum[k] = a % B;
                carry = a / B;
            }
            while (carry > 0 && k < sum.length) {
                int a = sum[k] + carry;
                sum[k] = a % B;
                carry = a / B;
                k++;
            }
            if (carry > 0) {
                int[] wider = new int[sum.length + 1];
                System.arraycopy(sum, 0, wider, 0, sum.length);
                wider[sum.length] = carry;
                sum = wider;
            }

            return new BigInt(sum);
        }

        public BigInt sq() {
            int[] rv = new int[2 * val.length];
            // Naive multiplication
            for (int i = 0; i < val.length; i++) {
                for (int j = i; j < val.length; j++) {
                    int k = i+j;
                    long c = val[i] * (long)val[j];
                    if (j > i) c <<= 1;
                    while (c > 0) {
                        c += rv[k];
                        rv[k] = (int)(c % B);
                        c /= B;
                        k++;
                    }
                }
            }

            int len = rv.length;
            while (len > 1 && rv[len - 1] == 0) len--;
            if (len < rv.length) {
                int[] rv2 = new int[len];
                System.arraycopy(rv, 0, rv2, 0, len);
                rv = rv2;
            }

            return new BigInt(rv);
        }

        public long digsum() {
            long rv = 0;
            for (int i = 0; i < val.length; i++) {
                int x = val[i];
                while (x > 0) {
                    rv += x % 10;
                    x /= 10;
                }
            }
            return rv;
        }
    }
}

```

# Answer
> 2 votes
# GMP - 1500000 / 300000 = 5.0

Although this answer won't compete against sieves, sometimes short code can still get results.

```
#include <gmpxx.h>
#include <iostream>

mpz_class sum_digits(mpz_class n)
{
    char* str = mpz_get_str(NULL, 10, n.get_mpz_t());
    int result = 0;
    for(int i=0; str[i]>0; i++)

    result += str[i] - 48;

    return result;
}

mpz_class comb_2(const mpz_class &x)
{
    const unsigned int k = mpz_get_ui(x.get_mpz_t()) / 2;
    mpz_class result = k + 1;

    for(int i=2; i<=k; i++)
    {
        result *= k + i;
        mpz_divexact_ui(result.get_mpz_t(), result.get_mpz_t(), i);
    }

    return result;
}

int main()
{
    const mpz_class n = 1500000;
    std::cout << sum_digits(comb_2(n)) << std::endl;

    return 0;
}

```

# Answer
> 2 votes
## Java, custom big integer class: 32.9 (120000000 / 365000)

The main class is pretty straightforward:

```
import java.util.*;

public class PPCG37270 {
    public static void main(String[] args) {
        long start = System.nanoTime();

        int n = 12000000;
        if (args.length == 1) n = Integer.parseInt(args[0]);

        boolean[] sieve = new boolean[n + 1];
        int[] remaining = new int[n + 1];
        int[] count = new int[n + 1];

        for (int p = 2; p <= n; p++) {
            if (sieve[p]) continue;
            long p2 = p * (long)p;
            if (p2 > n) continue;
            for (int i = (int)p2; i <= n; i += p) sieve[i] = true;
        }

        for (int i = 2; i <= n; i++) remaining[i] = i;
        for (int p = 2; p <= n; p++) {
            if (sieve[p]) continue;
            for (int i = p; i <= n; i += p) {
                while (remaining[i] % p == 0) {
                    remaining[i] /= p;
                    count[p]++;
                    if (i <= n/2) count[p] -= 2;
                }
            }
        }

        count[2] -= count[5];
        count[5] = 0;

        List<BigInt> partialProd = new ArrayList<BigInt>();
        long accum = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = count[i]; j > 0; j--) {
                long tmp = accum * i;
                if (tmp < 1000000000L) accum = tmp;
                else {
                    partialProd.add(new BigInt((int)accum));
                    accum = i;
                }
            }
        }
        partialProd.add(new BigInt((int)accum));
        System.out.println(prod(partialProd).digsum());
        System.out.println((System.nanoTime() - start) / 1000000 + "ms");
    }

    private static BigInt prod(List<BigInt> vals) {
        while (vals.size() > 1) {
            int n = vals.size();
            List<BigInt> next = new ArrayList<BigInt>();
            for (int i = 0; i < n; i += 2) {
                if (i == n - 1) next.add(vals.get(i));
                else next.add(vals.get(i).mul(vals.get(i+1)));
            }
            vals = next;
        }
        return vals.get(0);
    }
}

```

It relies on a big integer class which is optimised for multiplication and `toString()`, both of which are significant bottlenecks in an implementation with `java.math.BigInteger`.

```
/**
 * A big integer class which is optimised for conversion to decimal.
 * For use in simple applications where BigInteger.toString() is a bottleneck.
 */
public class BigInt {
    // The base of the representation.
    private static final int B = 1000000000;
    // The number of decimal digits per digit of the representation.
    private static final int LOG10_B = 9;

    public static final BigInt ZERO = new BigInt(0);
    public static final BigInt ONE = new BigInt(1);

    // We use sign-magnitude representation.
    private final boolean negative;

    // Least significant digit is at val[off]; most significant is at val[off + len - 1]
    // Unless len == 1 we guarantee that val[off + len - 1] is non-zero.
    private final int[] val;
    private final int off;
    private final int len;

    // Toom-style multiplication parameters from
    // Zuras, D. (1994). More on squaring and multiplying large integers. IEEE Transactions on Computers, 43(8), 899-908.
    private static final int[][][] Q = new int[][][]{
        {},
        {},
        {{1, -1}},
        {{4, 2, 1}, {1, 1, 1}, {1, 2, 4}},
        {{8, 4, 2, 1}, {-8, 4, -2, 1}, {1, 1, 1, 1}, {1, -2, 4, -8}, {1, 2, 4, 8}}
    };
    private static final int[][][] R = new int[][][]{
        {},
        {},
        {{1, -1, 1}},
        {{-21, 2, -12, 1, -6}, {7, -1, 10, -1, 7}, {-6, 1, -12, 2, -21}},
        {{-180, 6, 2, -80, 1, 3, -180}, {-510, 4, 4, 0, -1, -1, 120}, {1530, -27, -7, 680, -7, -27, 1530}, {120, -1, -1, 0, 4, 4, -510}, {-180, 3, 1, -80, 2, 6, -180}}
    };
    private static final int[][] S = new int[][]{
        {},
        {},
        {1, 1, 1},
        {1, 6, 2, 6, 1},
        {1, 180, 120, 360, 120, 180, 1}
    };

    /**
     * Constructs a big version of an integer value.
     * @param x The value to represent.
     */
    public BigInt(int x) {
        this(Integer.toString(x));
    }

    /**
     * Constructs a big version of a long value.
     * @param x The value to represent.
     */
    public BigInt(long x) {
        this(Long.toString(x));
    }

    /**
     * Parses a decimal representation of an integer.
     * @param str The value to represent.
     */
    public BigInt(String str) {
        this(str.charAt(0) == '-', split(str));
    }

    /**
     * Constructs a sign-magnitude representation taking the entire span of the array as the range of interest.
     * @param neg Is the value negative?
     * @param val The base-B digits, least significant first.
     */
    private BigInt(boolean neg, int[] val) {
        this(neg, val, 0, val.length);
    }

    /**
     * Constructs a sign-magnitude representation taking a range of an array as the magnitude.
     * @param neg Is the value negative?
     * @param val The base-B digits, least significant at offset off, most significant at off + val - 1.
     * @param off The offset within the array.
     * @param len The number of base-B digits.
     */
    private BigInt(boolean neg, int[] val, int off, int len) {
        // Bounds checks
        if (val == null) throw new IllegalArgumentException("val");
        if (off < 0 || off >= val.length) throw new IllegalArgumentException("off");
        if (len < 1 || off + len > val.length) throw new IllegalArgumentException("len");

        this.negative = neg;
        this.val = val;
        this.off = off;
        // Enforce the invariant that this.len is 1 or val[off + len - 1] is non-zero.
        while (len > 1 && val[off + len - 1] == 0) len--;
        this.len = len;

        // Sanity check
        for (int i = 0; i < len; i++) {
            if (val[off + i] < 0) throw new IllegalArgumentException("val contains negative digits");
        }
    }

    /**
     * Splits a string into base-B digits.
     * @param str The string to parse.
     * @return An array which can be passed to the (boolean, int[]) constructor.
     */
    private static int[] split(String str) {
        if (str.charAt(0) == '-') str = str.substring(1);

        int[] arr = new int[(str.length() + LOG10_B - 1) / LOG10_B];
        int i, off;
        // Each element of arr represents LOG10_B characters except (probably) the last one.
        for (i = 0, off = str.length() - LOG10_B; off > 0; off -= LOG10_B) {
            arr[i++] = Integer.parseInt(str.substring(off, off + LOG10_B));
        }
        arr[i] = Integer.parseInt(str.substring(0, off + LOG10_B));
        return arr;
    }

    public boolean isZero() {
        return len == 1 && val[off] == 0;
    }

    public BigInt negate() {
        return new BigInt(!negative, val, off, len);
    }

    public BigInt add(BigInt that) {
        // If the signs differ, then since we use sign-magnitude representation we want to do a subtraction.
        boolean isSubtraction = negative ^ that.negative;

        BigInt left, right;
        if (len < that.len) {
            left = that;
            right = this;
        }
        else {
            left = this;
            right = that;

            // For addition I just care about the lengths of the arrays.
            // For subtraction I want the largest absolute value on the left.
            if (isSubtraction && len == that.len) {
                int cmp = compareAbsolute(that);
                if (cmp == 0) return ZERO; // Cheap special case
                if (cmp < 0) {
                    left = that;
                    right = this;
                }
            }
        }

        if (right.isZero()) return left;

        BigInt result;
        if (!isSubtraction) {
            int[] sum = new int[left.len + 1];
            // A copy here rather than using left.val in the main loops and copying remaining values
            // at the end gives a small performance boost, probably due to cache locality.
            System.arraycopy(left.val, left.off, sum, 0, left.len);

            int carry = 0, k = 0;
            for (; k < right.len; k++) {
                int a = sum[k] + right.val[right.off + k] + carry;
                sum[k] = a % B;
                carry = a / B;
            }
            for (; carry > 0 && k < left.len; k++) {
                int a = sum[k] + carry;
                sum[k] = a % B;
                carry = a / B;
            }
            sum[left.len] = carry;

            result = new BigInt(negative, sum);
        }
        else {
            int[] diff = new int[left.len];
            System.arraycopy(left.val, left.off, diff, 0, left.len);

            int carry = 0, k = 0;
            for (; k < right.len; k++) {
                int a = diff[k] - right.val[right.off + k] + carry;
                // Why did anyone ever think that rounding positive and negative divisions differently made sense?
                if (a < 0) {
                    diff[k] = a + B;
                    carry = -1;
                }
                else {
                    diff[k] = a % B;
                    carry = a / B;
                }
            }
            for (; carry != 0 && k < left.len; k++) {
                int a = diff[k] + carry;
                if (a < 0) {
                    diff[k] = a + B;
                    carry = -1;
                }
                else {
                    diff[k] = a % B;
                    carry = a / B;
                }
            }

            result = new BigInt(left.negative, diff, 0, k > left.len ? k : left.len);
        }

        return result;
    }

    private int compareAbsolute(BigInt that) {
        if (len > that.len) return 1;
        if (len < that.len) return -1;

        for (int i = len - 1; i >= 0; i--) {
            if (val[off + i] > that.val[that.off + i]) return 1;
            if (val[off + i] < that.val[that.off + i]) return -1;
        }

        return 0;
    }

    public BigInt mul(BigInt that) {
        if (isZero() || that.isZero()) return ZERO;

        if (len == 1) return that.mulSmall(negative ? -val[off] : val[off]);
        if (that.len == 1) return mulSmall(that.negative ? -that.val[that.off] : that.val[that.off]);

        int shorter = len < that.len ? len : that.len;
        BigInt result;
        // Cutoffs have been hand-tuned.
        if (shorter > 300) result = mulToom(3, that);
        else if (shorter > 28) result = mulToom(2, that);
        else result = mulNaive(that);

        return result;
    }

    BigInt mulSmall(int m) {
        if (m == 0) return ZERO;
        if (m == 1) return this;
        if (m == -1) return negate();

        // We want to do the magnitude calculation with a positive multiplicand.
        boolean neg = negative;
        if (m < 0) {
            neg = !neg;
            m = -m;
        }

        int[] pr = new int[len + 1];
        int carry = 0;
        for (int i = 0; i < len; i++) {
            long t = val[off + i] * (long)m + carry;
            pr[i] = (int)(t % B);
            carry = (int)(t / B);
        }
        pr[len] = carry;
        return new BigInt(neg, pr);
    }

    // NB This truncates.
    BigInt divSmall(int d) {
        if (d == 0) throw new ArithmeticException();
        if (d == 1) return this;
        if (d == -1) return negate();

        // We want to do the magnitude calculation with a positive divisor.
        boolean neg = negative;
        if (d < 0) {
            neg = !neg;
            d = -d;
        }

        int[] div = new int[len];
        int rem = 0;
        for (int i = len - 1; i >= 0; i--) {
            long t = val[off + i] + rem * (long)B;
            div[i] = (int)(t / d);
            rem = (int)(t % d);
        }

        return new BigInt(neg, div);
    }

    BigInt mulNaive(BigInt that) {
        int[] rv = new int[len + that.len];
        // Naive multiplication
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < that.len; j++) {
                int k = i + j;
                long c = val[off + i] * (long)that.val[that.off + j];
                while (c > 0) {
                    c += rv[k];
                    rv[k] = (int)(c % B);
                    c /= B;
                    k++;
                }
            }
        }

        return new BigInt(this.negative ^ that.negative, rv);
    }

    private BigInt mulToom(int k, BigInt that) {
        // We split each number into k parts of m base-B digits each.
        // m = ceil(longer / k)
        int m = ((len > that.len ? len : that.len) + k - 1) / k;

        // Perform the splitting and evaluation steps of Toom-Cook.
        BigInt[] f1 = this.toomFwd(k, m);
        BigInt[] f2 = that.toomFwd(k, m);

        // Pointwise multiplication.
        for (int i = 0; i < f1.length; i++) f1[i] = f1[i].mul(f2[i]);

        // Inverse (or interpolation) and recomposition.
        return toomBk(k, m, f1, negative ^ that.negative, val[off], that.val[that.off]);
    }

    // Splits a number into k parts of m base-B digits each and does the polynomial evaluation.
    private BigInt[] toomFwd(int k, int m) {
        // Split.
        BigInt[] a = new BigInt[k];
        for (int i = 0; i < k; i++) {
            int o = i * m;
            if (o >= len) a[i] = ZERO;
            else {
                int l = m;
                if (o + l > len) l = len - o;
                // Ignore signs for now.
                a[i] = new BigInt(false, val, off + o, l);
            }
        }

        // Evaluate
        return transform(Q[k], a);
    }

    private BigInt toomBk(int k, int m, BigInt[] f, boolean neg, int lsd1, int lsd2) {
        // Inverse (or interpolation).
        BigInt[] b = transform(R[k], f);

        // Recomposition: add at suitable offsets, dividing by the normalisation factors
        BigInt prod = ZERO;
        int[] s = S[k];
        for (int i = 0; i < b.length; i++) {
            int[] shifted = new int[i * m + b[i].len];
            System.arraycopy(b[i].val, b[i].off, shifted, i * m, b[i].len);
            prod = prod.add(new BigInt(neg ^ b[i].negative, shifted).divSmall(s[i]));
        }

        // Handle the remainders.
        // In the worst case the absolute value of the sum of the remainders is s.length, so pretty small.
        // It should be easy enough to work out whether to go up or down.
        int lsd = (int)((lsd1 * (long)lsd2) % B);
        int err = lsd - prod.val[prod.off];
        if (err > B / 2) err -= B / 2;
        if (err < -B / 2) err += B / 2;
        return prod.add(new BigInt(err));
    }

    /**
     * Multiplies a matrix of small integers and a vector of big ones.
     * The matrix has a implicit leading row [1 0 ... 0] and an implicit trailing row [0 ... 0 1].
     * @param m The matrix.
     * @param v The vector.
     * @return m v
     */
    private BigInt[] transform(int[][] m, BigInt[] v) {
        BigInt[] b = new BigInt[m.length + 2];
        b[0] = v[0];
        for (int i = 0; i < m.length; i++) {
            BigInt s = ZERO;
            for (int j = 0; j < m[i].length; j++) s = s.add(v[j].mulSmall(m[i][j]));
            b[i + 1] = s;
        }
        b[b.length - 1] = v[v.length - 1];

        return b;
    }

    /**
     * Sums the digits of this integer.
     * @return The sum of the digits of this integer.
     */
    public long digsum() {
        long rv = 0;
        for (int i = 0; i < len; i++) {
            int x = val[off + i];
            while (x > 0) {
                rv += x % 10;
                x /= 10;
            }
        }
        return rv;
    }
}

```

The big bottleneck is naïve multiplication (60%), followed by the other multiplication (37%) and the sieving (3%). The `digsum()` call is insignificant.

Performance measured with OpenJDK 7 (64 bit).

# Answer
> 1 votes
# Java (2,020,000/491,000) = 4.11

**updated, previously 2.24**

Java `BigInteger` isn't the fastest number cruncher, but it's better than nothing.

The basic formula for this seems to be `n! / ((n/2)!^2)`, but that seems like a bunch of redundant multiplication.

You can get a significant speedup by eliminating all prime factors found in both the numerator and denominator. To do this, I first run a simple prime sieve. Then for each prime, I keep a count of what power it needs to be raised to. Increment each time I see a factor in the numerator, decrement for the denominator.

I handle twos separately (and first), since it's easy to count/eliminate them before factoring.

Once that's done, you have the minimum amount of multiplications necessary, which is good because BigInt multiply is *slow*.

```
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class CentBiCo {
    public static void main(String[] args) {
        int n = 2020000;
        long time = System.currentTimeMillis();
        sieve(n);
        System.out.println(sumDigits(cbc(n)));
        System.out.println(System.currentTimeMillis()-time);
    }

    static boolean[] sieve;
    static List<Integer> primes;
    static void sieve(int n){
        primes = new ArrayList<Integer>((int)(Math.sqrt(n)));
        sieve = new boolean[n];
        sieve[2]=true;
        for(int i=3;i<sieve.length;i+=2)
            if(i%2==1)
                sieve[i] = true;
        for(int i=3;i<sieve.length;i+=2){
            if(!sieve[i])
                continue;
            for(int j=i*2;j<sieve.length;j+=i)
                sieve[j] = false;
        }
        for(int i=2;i<sieve.length;i++)
            if(sieve[i])
                primes.add(i);
    }

    static int[] factors;
    static void addFactors(int n, int flip){
        for(int k=0;primes.get(k)<=n;){
            int i = primes.get(k);
            if(n%i==0){
                factors[i] += flip;
                n /= i;
            } else {
                if(++k == primes.size())
                    break;
            }
        }
        factors[n]++;
    }

    static BigInteger cbc(int n){
        factors = new int[n+1];
        int x = n/2;
        for(int i=x%2<1?x+1:x+2;i<n;i+=2)
            addFactors(i,1);
        factors[2] = x;
        for(int i=1;i<=x/2;i++){
            int j=i;
            while(j%2<1 && factors[2] > 1){
                j=j/2;
                factors[2]--;
            }
            addFactors(j,-1);
            factors[2]--;
        }
        BigInteger cbc = BigInteger.ONE;
        for(int i=3;i<factors.length;i++){
            if(factors[i]>0)
                cbc = cbc.multiply(BigInteger.valueOf(i).pow(factors[i]));
        }
        return cbc.shiftLeft(factors[2]);
    }

    static long sumDigits(BigInteger in){
        long sum = 0;
        String str = in.toString();
        for(int i=0;i<str.length();i++)
            sum += str.charAt(i)-'0';
        return sum;
    }
}

```

Oh, and the output sum for n=2020000 is `2735298`, for verification purposes.

# Answer
> 1 votes
# Python 2 (PyPy), 1,134,000 / 486,000 = 2.32

```
#/!usr/bin/pypy
n=input(); a, b, c=1, 1, 2**((n+2)/4)
for i in range(n-1, n/2, -2): a*=i
for i in range(2, n/4+1): b*=i
print sum(map(int, str(a*c/b)))

```

### Result: 1,537,506

Fun fact: The bottleneck of your code is adding the digits, not computing the binomial coefficient.

---
Tags: fastest-code, number-theory
---


title: Spiral Programming

text:
# Question
Title: Spiral Programming
Write a named function or program that accepts a single integer N and prints (to STDOUT) or returns (as a string) the first N bars of the spiral below, beginning with the vertical bar in the center and spiraling clockwise outward.

```
        _______________
       / _____________ \
      / / ___________ \ \
     / / / _________ \ \ \
    / / / / _______ \ \ \ \
   / / / / / _____ \ \ \ \ \
  / / / / / / ___ \ \ \ \ \ \
 / / / / / / / _ \ \ \ \ \ \ \
/ / / / / / / / \ \ \ \ \ \ \ \
| | | | | | | | | | | | | | | |
\ \ \ \ \ \ \___/ / / / / / / /
 \ \ \ \ \ \_____/ / / / / / /
  \ \ \ \ \_______/ / / / / /
   \ \ \ \_________/ / / / /
    \ \ \___________/ / / /
     \ \_____________/ / /
      \_______________/ /

```

You may assume that 0 \< N \<= 278. Your output cannot contain any whitespace in front of the leftmost character of the spiral. You may optionally print a single trailing newline.

For an input of 10, the correct output is

```
   _
  / \
  | |
\___/

```

For an input of 2, the correct output is

```
/
|

```

For an input of 20, the correct output is

```
  ___
 / _ \
/ / \ \
| | | |
\___/ /

```

An output that would be incorrect because the leftmost character is preceded by whitespace is

```
       ___
      / _ \
     / / \ \
     | | | |
     \___/ /

```

The winner is the shortest submission, in bytes.

# Answer
# CJam - 156 / 147

```
L{[W1]{:I0'|{IIW*:J'/}X*[0J'_]X2*I+*[J0_]I1={\}*{J_'\}X*0I0}%L*3/{~_{[UV@]a3$+}{;@}?V@+:V;U@+:U;}/}A,1>fX]ri=_z::e<2<f{[\\]z::-}$_W=0=)S50*a*\{~3$3$=\tt}/N*

```

Try it online

It works with inputs from 1 to 378 inclusive (100 more than required)

Using the latest committed (publicly available in hg) but unreleased CJam code at the time this challenge was posted, the solution can be shortened to 147 characters:

```
L{[W1]{:I0'|{IIW*:J'/}X*[0J'_]X2*I+*[J0_]I1={\}*{J_'\}X*0I0}%L*3/{~_{[UV@]a3$+}{;@}?V@+:V;U@+:U;}/}A,1>fX]ri=_:.e<2<f.-$_W=0=)S50*a*\{~3$3$=\tt}/N*

```

**Explanation:**

The program iteratively constructs all the spirals as arrays of \[x y character\] starting with `[0 0 '|]`, gets the requested spiral, adjusts the coordinates so that the minimum x and y are 0, creates a matrix of spaces (with the correct number of rows and 50 columns) then sets the characters from the spiral and joins the rows with newlines.

```
L                   start with an empty array (spiral no. 0)
{…}A,1>fX           for X in 1..9 (A=10)
                    each X represents a full 360° tour with groups of X /'es and \'es
    [W1]{…}%        transform the array [-1 1] (W=-1) applying the block to each item
                    the block generates a series of triplets dx, dy, character
                    note: dx is down, dy is right; -1 handles ↑↗→↘, 1 handles ↓↙←↖
        :I          store the current item in I
        0'|         add 0 and |, which will form a triplet with the previous I
        {…}X*       repeat X times
            IIW*    add I and -I
            :J'/    also store -I in J, and add /
        [0J'_]      make an array [0 J _]
        X2*I+*      repeat the array X*2+I times
        [J0_]       make an array [J 0 0]
                    (a 0 instead of a character means only changing the position)
        I1={\}*     if I=1, swap the two arrays (the position adjustment is different
                    for the upper and lower horizontal sections)
        {…}X*       repeat X times
            J_'\    add J, J and \
        0I0         add 0, I and 0 (another position adjustment)
    L*              flatten the array (since we added a few inner arrays)
    3/              split into [dx dy char] triplets
    {…}/            for each triplet
        ~_          dump the 3 items on the stack and duplicate the character
        {…}         if the character is not 0
            [UV@]   make an array [U V char] (U and V are initially 0)
                    U represents "x" and V represents "y"
            a3$+    add it as an element to a copy of the previous spiral
        {…}         else
            ;@      pop the character and bring the previous spiral to the top
        ?           end if
        V@+:V;      V+=dy
        U@+:U;      U+=dx
]                   put all the spirals in an array
ri=                 read token, convert to integer and get that spiral
_z::e<              copy the spiral and get a triplet with the minimum values
2<                  keep only the first 2 items (xmin and ymin)
f{…}                for each triplet and the array [xmin ymin]
    [\\]z::-        subtract xmin and ymin from x and y in the triplet
                    (in the latest CJam code this is simply ".-")
$                   sort the spiral (putting the triplets in order by x then y)
_W=0=)              get the maximum (updated) x and increment it
S50*                make a string of 50 spaces
a*                  put it in an array and repeat it xmax+1 times
                    this is the initial matrix of spaces
\                   swap with the spiral
{…}/                for each triplet in the spiral
    ~               dump the 3 items (x y char) on the stack
    3$3$=           copy the matrix and x, and get the x'th row
    \t              swap with the character and put that character in the y'th position
    t               put the modified row in the x'th position in the matrix
N*                  join the matrix rows with newlines

```
> 5 votes

# Answer
# Python 2, ~~290~~ 289

It's probably really bad, but I tried :D

The output contains trailing spaces, but that is not forbidden in the spec.

**Update:** saved 1 byte with changing `\n`  to `;`.

```
m=x=y=c=0
l,f=1,[31*[' ']for t in[0]*31]
for i in[0]*input():
 k=m%4;f[14+y+(2<m<6)][14+x-(m>3)],x,y,c='|/_\\'[k],x+(k>0)*(2*(4>m)-1),y+(k!=2)*(2*(2<m<6)-1),c+1
 if(c==l)*(m%2)+(k==0)+(k==2)*(c==2*l-1+m//3):m,c,l=(m+1)%8,0,l+m//7
print'\n'.join(''.join(e[16-l*2:])for e in f if[' ']*31!=e)

```
> 8 votes

# Answer
# JavaScript (ES6) 257 ~~288 321~~

**Edit** Steps merged.
**Edit** Golfed code fiddling to cut some more char

Build the output iteratively into the r array, keeping track of current x and y position and current direction. When the x or y position is \< 0 the whole r array is readjusted.

Main variables:

* r result array or rows
* x,y current position.
* s current direction (0..7) (or current state)
* d current symbol to draw (0..3) -\> '|\\\_/'
* l runnig position on the current sequence (down to 0)
* w current spiral radius (more or less)

```
F=n=>
  (w=>{
    for(r=b=[],s=y=x=d=0;n--;
      d&&--l||((s=s+1&7,d=s&3)?l=d-2?w:s/2-2+w+w:w+=!s))
      s>0&s<4?++x:s>4?x?--x:r=r.map(v=>' '+v):b+='  ',
      q=r[s>2&s<6?++y:y]||b,
      r[y]=(q+b).slice(0,x)+'|/_\\'[d]+q.slice(x+1),
      s<2|s>6?y?--y:r=[,...r]:x+=!d*2,x-=!d
  })(1)||r.join('\n')

```

**Ungolfed**

```
F=n=>{
  var r=[], s,x,y,d,w,l, q
  for(l=w=1, s=x=y=d=0; n--;)
  {
    if (s>2 && s<6) ++y; // right side, inc y before drawing

    if (x < 0) // too left, adjust
    {
      r = r.map(v=>' '+v) // shift all to right
      ++x; // move current position to right
    }
    if (y < 0) // too up
    {
      r = [q='',...r] // shift all to bottom
      ++y; // move current position to bottom
    }
    q = r[y] || ''; // current row, if undefined convert to empty string
    r[y] = (q+' '.repeat(x)).slice(0,x) + '|/_\\'[d] + q.slice(x+1); // add current symbol in the x column

    if (s<2 || s>6) --y; // left side, dec y after drawing

    if (s>0 && s<4) // always change x after drawing
      ++x;
    else if (s > 4)
      --x;

    --l; // decrement current run
    if (l == 0) // if 0, need to change direction
    {
      s = (s+1) % 8; // change direction
      d = s % 4; // change symbol
      if (d == 0)
      {
        // vertical direction, adjust x and if at 0 increase radius
        l = 1 // always 1 vertical step
        if (s == 0)
          ++x, ++w
        else
          --x
      }
      else
      {
        if (d != 2)
        {
          l = w; // diaagonal length is always w
        }
        else if (s == 2)
        {
          l = w+w-1 // top is radius * 2 -1
        }
        else
        {
          l = w+w+1 // bottom is radius * 2 +1
        }
      }
    }
  }
  return r.join('\n')
}

```

**Test** In Firefox/FireBug console (or JSFiddle thx @Rainbolt)

```
;[1, 2, 10, 20, 155, 278].forEach(x=>console.log(F(x)))

```

*Output*

```
|

/
|

   _
  / \
  | |
\___/

  ___
 / _ \
/ / \ \
| | | |
\___/ /

      ___________
     / _________ \
    / / _______ \ \
   / / / _____ \ \ \
  / / / / ___ \ \ \ \
 / / / / / _ \ \ \ \ \
/ / / / / / \ \ \ \ \ \
| | | | | | | | | | | |
\ \ \ \ \___/ / / / /
 \ \ \ \_____/ / / /
  \ \ \_______/ / /
   \ \_________/ /
    \___________/

        _______________
       / _____________ \
      / / ___________ \ \
     / / / _________ \ \ \
    / / / / _______ \ \ \ \
   / / / / / _____ \ \ \ \ \
  / / / / / / ___ \ \ \ \ \ \
 / / / / / / / _ \ \ \ \ \ \ \
/ / / / / / / / \ \ \ \ \ \ \ \
| | | | | | | | | | | | | | | |
\ \ \ \ \ \ \___/ / / / / / / /
 \ \ \ \ \ \_____/ / / / / / /
  \ \ \ \ \_______/ / / / / /
   \ \ \ \_________/ / / / /
    \ \ \___________/ / / /
     \ \_____________/ / /
      \_______________/ /

```
> 4 votes

# Answer
# Pyth, ~~166~~ 165

I just translated my Python answer to Pyth, with my not-great Pyth skills. The resulting vomit is below.

```
Jm*31]d*31dK0=G0=H0=Y1VQ X@J++14H&<2K<K6+14-G<3K@"|/_\\"%K4~G*<0%K4-*2>4K1~H*n2%K4-*2&<2K>6K1~Z1I||&qZY%K2!%K4&q2%K4qZ+-*2Y1/K3~Y/K7=K%+1K8=Z0;jbmj>d-16*2Ykfn*31]dTJ

```
> 2 votes

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


# Question
Title: C golfing tips - returning 0 without return statement
I'm looking for some solution in returning values in main function, I need to shorten my program more, `return 0` takes too much characters of my code, I need to return 0, or my code fails. I know that in C there can be no `return` statement, and then program will use result of last operation - but on which operations I can 'really' shorten my code? At the moment I found `brk(0)` as shortest return.

```
main(n){while(~scanf("%i",&n))printf("%i ",n*~n/-2);brk(0);}

```

# Answer
You don't need to do anything.

This assumption:

> then program will use result of last operation

is erroneous. If there is no `return` statement, `main` returns 0. It is *not* dependent on whatever might be left over in registers or anything like that.

From the standard:

> **5.1.2.2.3 Program termination**
>
> If the return type of the `main` function is a type compatible with `int`, a return from the initial call to the `main` function is equivalent to calling the `exit` function with the value returned by the `main` function as its argument; reaching the `}` that terminates the `main` function **returns a value of 0.** If the return type is not compatible with `int`, the termination status returned to the host environment is unspecified.

(emphasis mine)

Your program's `main` already returns zero, or something is wrong somewhere else.
> 8 votes

# Answer
To be precise, the return value is generally dependent not on any previous "operation", but on the return value of the last function call. You are hoping that the function dumps a 0 into the EAX register, and that it stays there when `main` returns.

You may be able to get better mileage out of `atoi`/`atol` and `gets` here. When `gets` hits EOF without reading a line, it returns a null pointer. Then, `atol` will return 0 upon receiving a null pointer as input. Since 0 is not an allowed value for `n`, this can be used as the loop condition, as well as the way to drop 0 into the appropriate register.

```
main(n){while(n=atol(gets(??????)))printf("%i ",n*~n/-2);}

```

The only problem is to find some memory for `gets` to write on. I'm not familiar with the Unix-specific library functions such as `brk`, but surely you can find something 6 characters or less (needed for an overall shortening) which returns `char*` or `void*` among all the cruft.
> 2 votes

---
Tags: code-golf, tips, c
---


# Question
Title: Is there a shorter way to assign one of two variables in Python?
This is a question for golfing in .

In multiple golfs I've done in Python, a fixed value is assigned to one of two variables chosen by a Boolean. The chosen variable is overwritten by the given value, and the other is unchanged.

*17 chars:*

```
if b:y=z
else:x=z

```

Assigning a conditional value is easy, but assigning to a conditional variable seems clunky. I'm wondering if there's a shorter way I'm missing.

This would be easy if `x,y` were instead a list `L`, but assume the context requires referring to the variables enough that writing `L[0]` and `L[1]` is prohibitive. Converting takes too long:

*20 chars:*

```
L=[x,y];L[b]=z;x,y=L

```

The fastest way I know is with a Python 2 `exec`, which is bizarre:

*16 chars, Python 2:*

```
exec"xy"[b]+"=z"

```

Tuple-choosing seems to be longer:

*18, 19, 18, 18 chars:*

```
x,y=b*(x,z)or(z,y)
x,y=[z,x,y,z][b::2]
y,x=[y,z,x][b:b+2]
y,x,*_=[y,z,x][b:]   # Python 3

```

Is there some shorter method or character-saving optimization? You can assume `b` is `0` or `1`, not just Falsey or Truthy, and also make assumptions about the data types and values if it helps.

# Answer
## 12 chars/assignment + 9 chars of overhead

```
V=vars()     # do once at the start of the program
V["xy"[b]]=z

```

Note that this only works at global scope, it does not work inside a function.
> 26 votes

# Answer
## 14 chars, Python 2

```
exec"xy=z"[b:]

```

The two variables are `y` and `xy`. If b=0, this sets `xy=z`. If b=1, this sets `y=z`. This will be worth it if `xy` is used no more than once elsewhere in the code.
> 19 votes

# Answer
## 15 chars, Python 2

```
exec`b`[0]+"=z"

```

Requires that the variables be called `F` and `T` rather than `x` and `y`, and that `b is False` or `b is True`, rather than being the equal numbers `0` or `1`.

This saves a char from `"xy"[b]` by instead taking the first letter of the string representation of `b`, which is `T` or `F`.
> 15 votes

---
Tags: code-golf, tips, python
---