title: Convert a HTML page into a mountain

text:
# Question
Title: Convert a HTML page into a mountain
**Task:** convert a HTML page into a mountain!

When HTML pages are indented, they can look like:

```
<div>
    <div>
        <div>
        </div>
        <div>
            <div>
            </div>
        </div>
    </div>
</div>

```

But to be honest, a mountain is more representative of this structure.

So we can rewrite it as:

```
     /\
  /\/  \
 /      \
/        \

```

The outermost slashes on the left and right correspond to the outer div - each pair of HTML tags should be represented as `/` for the starting tag and `\` for the ending tag - inside all tags are "higher", with the same structure.

**Input:**

* There will be no `<!DOCTYPE>`
* There will be no self-closing tags e.g. `<img />` or `<br />`
* There may be attributes or content inside the tags
* There may be spaces or tabs - your program should ignore these
* There will be no spaces between `<` or `</` and the tag name
* All input will be valid HTML

**Output** \- a mountain representing the tags as above.

*More testcases:*

Input:

```
<div id="123"> HI </div><a><span></span></a>

```

Output:

```
   /\
/\/  \

```

Input:

```
<body id="<"></body>

```

Output:

```
/\

```

# Answer
# HTML + CSS + JavaScript, 39 + 141 + 20 = 200 bytes

Outputs visually to the webpage. To allow this to work with special elements like `<body>`, all letters in the input are replaced.

```
p.innerHTML=prompt().replace(/\w/g,'a')
```

```
#p,#p *{display:flex;padding:0 0 1rem;align-items:flex-end;font-size:0}#p :before,#p :after{content:'/';font-size:1rem}#p :after{content:'\\'
```

```
<pre id=p>
```

---

# HTML + CSS + JavaScript, 10 + 103 + 20 = 133 bytes

Solution that works if there is no content within tags.

```
p.innerHTML=prompt()
```

```
#p,#p *{display:flex;padding:0 0 1em;align-items:flex-end}#p :before{content:'/'}#p :after{content:'\\'
```

```
<pre id=p>
```
> 14 votes

# Answer
# Javascript + JQuery, ~~275~~ 246 bytes

Saved 29 bytes thanks to Rick Hitchcock

```
j=(a,b,c,i)=>{s=(c=' '.repeat(b))+'/\n';for(i=0;V=a.children[i];i++){s=s+j(V,b+1)}return s+c+'\\\n';};f=s=>{s=j($(s)[0],0).split`
`;w=Math.max.apply(0,s.map(a=>a.length));o='';for(i=w-1;i>=0;i--){for(c=0;C=s[c];c++){o+=C[i]||' '}o+='\n'}alert(o)}

```

A pretty Naïve solution to the problem. Parses the HTML with JQuery's `$(string)`, then recursively builds a sideways mountain with the format:

```
/
 /
  children...
 \
\

```

Then rotates the resulting string counterclockwise, and alerts the result.

```
    j=(a,b,c,i)=>{s=(c=' '.repeat(b))+'/\n';for(i=0;V=a.children[i];i++){s=s+j(V,b+1)}return s+c+'\\\n';};f=s=>{s=j($(s)[0],0).split`
`;w=Math.max.apply(0,s.map(a=>a.length));o='';for(i=w-1;i>=0;i--){for(c=0;C=s[c];c++){o+=C[i]||' '}o+='\n'}return o}

update=_=>outp.textContent=f(inp.value)
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<textarea id=inp oninput=update()></textarea>
<pre id=outp></pre>
```
> 6 votes

# Answer
# HTML + JavaScript (ES6), 8 + 192 = 200 bytes

### JS

```
s=>[...(E.innerHTML=s,y=0,o=[],m=n=>1+[...n.children].map(m).join``+0)(E.firstChild)].map((c,x,a)=>{(o[y+=+c]||(o[y]=[...a].fill` `))[x]=`\\/`[c],y+=~-c})&&o.reverse().map(l=>l.join``).join`
`

```

### HTML

```
<a id=E>

```

```
f=

s=>[...(E.innerHTML=s,y=0,o=[],m=n=>1+[...n.children].map(m).join``+0)(E.firstChild)].map((c,x,a)=>{(o[y+=+c]||(o[y]=[...a].fill` `))[x]=`\\/`[c],y+=~-c})&&o.reverse().map(l=>l.join``).join`
`

console.log(f(`<div>
    <div>
        <div>
        </div>
        <div>
        </div>
        <div>
            <div>
            </div>
        </div>
    </div>
</div>`))
```

```
<a id=E>
```

## Less golfed

```
s=>{
    E.innerHTML=s,
    y=0,
    o=[],
    m=n=>1+[...n.children].map(m).join``+0,
    [...m(E.firstChild)].map((c,x,a)=>{
        y+=+c
        if(!o[y]) o[y]=[...a].fill` `
        o[y][x]=`\\/`[c]
        y+=~-c
    })
    return o.reverse().map(l=>l.join``).join`\n`
}

```
> 3 votes

# Answer
# 05AB1E, ~~38~~ ~~26~~ 23 bytes

```
¶¡εDð¢4÷s'/å_„\/sèú}ζR»

```

Try it online!

---

I am still golfing this. It assumes that in HTML you will always use 4 spaces for indentation, and does not work on "non-pretty" HTML. Not sure how to handle the "content" part, if this is invalid please edit the question to show an example with a node that has content.
> 1 votes

# Answer
# Charcoal, 28 bytes

```
≔¹ηＦ⮌θ«≡ι"≦¬η<Ｆη¿⁼ζ/←¶\↙/≔ιζ

```

Try it online! Link is to verbose version of code. Explanation:

```
≔¹η

```

The `h` variable is used to keep track of whether we are inside quotes.

```
Ｆ⮌θ«

```

Loop over the string in reverse order.

```
≡ι

```

Switch on the currenc character.

```
"≦¬η

```

If it's a `"` then toggle the quote flag.

```
<Ｆη

```

If it's a `<` and we're not inside quotes, then...

```
¿⁼ζ/

```

If the next character (previous in the loop because we're looping in reverse) is a `/`, then...

```
←¶\

```

Move up and draw a `\` leftwards, else...

```
↙/

```

Draw a `/` and move down and left.

```
≔ιζ

```

Remember the character for the next loop iteration.
> 0 votes

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


title: Celsius - Fahrenheit anagram

text:
# Question
Title: Celsius - Fahrenheit anagram
## Task

> Make a complete program or a function which calculates sum of all temperatures which, when written in Celsius and Fahrenheit scale, are anagram of each other.

## Description

For example, `275` degree Celsius = `527` degree Fahrenheit, and `527` is anagram of `275`. Non-integer temperatures (either in degree Celsius or degree Fahrenheit) and temperatures colder than 0 degree Celsius (like `-40C` = `-40F`) will *not* be considered.

## Input

Input is a temperature in format `([1-9][0-9]*)(C|F)` (example: `42F` = 42 degree Fahrenheit, `125C` = 125 degree Celsius, ...).

The program should be able to handle temperature less than `1000000C`.

## Output

Output is sum of all temperatures less than the temperature given by input, which, when written in Celsius and Fahrenheit scale, are anagram (without leading zeroes) of each other. Output will be two integers separated by a space. The first one will be the sum in degree Celsius, and the second one will be the sum in degree Fahrenheit.

If there's no such temperature, return or output `0 0`.

## Example

* Input : `42C`
    + There's no such temperature
    + Output : `0 0`
* Input : `300C`
    + There's one temperature : `275C` = `527F`
    + Output : `275 527`
* Input : `10000F`
    + There're three temperatures : `275C` = `527F`, `2345C` = `4253F`, and `4685C` = `8465F`
    + Output : `7305 13245`

# Answer
## GolfScript, 65 61 characters

```
)\~{32- 9/5*}@70=*5/),0.@{.5*.`$@9*32+.`$@=:f*@+\f*@+\}%]' '*

```

*Edit:* incorporating the reduce operation into the loop saved 4 characters
> 1 votes

# Answer
## C# - 166

Due to the small number of matches, I thought it might be easier to hardcode the outputs:

```
void F(string i){int n=int.Parse(i.Substring(0,i.Length-1));
n=i.Last()=='C'?n:5*(n-32)/9;
Console.Write(n>4685?"7305 13245":n>2345?"2620 4780":n>275?"275 527":"0 0");}

```

### Edit: 352

To do it right requires a bit more work. Here's a first attempt at using a whole pile of linq:

```
using System;
using System.Linq;
class P{static void Main(string[] i)
{
   int n=int.Parse(i[0].Substring(0,i[0].Length-1));
   n=i[0].Last()=='C'?n:5*(n-32)/9;
   var q=Enumerable.Range(1,n).Where(x=>new string(((decimal)x*9/5+32).ToString().OrderBy(y=>y).ToArray())==new string(x.ToString().OrderBy(y=>y).ToArray()));
   Console.Write(q.Sum()+" "+q.Sum(x=>x*9/5+32));
}}

```

Maybe the 'use a pile of linq instead of a loop' approach hurt me too much. I'll try and shorten it.

### Edit 2: 356

Since I'm already way behind in raw count, here's a one-liner from hell:

```
Console.Write(Enumerable.Range(1,i.Last()=='C'?int.Parse(i.Substring(0,i.Length-1)):5*(int.Parse(i.Substring(0,i.Length-1))-32)/9).Where(x=>new string(((decimal)x*9/5+32).ToString().OrderBy(y=>y).ToArray())==new string(x.ToString().OrderBy(y=>y).ToArray())).Aggregate("0 0",(a,t)=>(int.Parse(a.Split(' ')[0])+t)+" "+(int.Parse(a.Split(' ')[1])+t*9/5+32)))

```
> 1 votes

# Answer
## Mathematica, 77

I wish I could get this shorter, but working with function names like `IntegerDigits` I think this is about the best I can do.

```
 Grid@{Total@Select[{#,9/5#+32}&~Array~#,SameQ@@(Sort@IntegerDigits@#&)/@#&]}&

```
> 1 votes

# Answer
## Perl, 182 characters

```
sub F{5*($_[0]-32)/9}sub C{$_[0]*9/5+32}sub O{join'',sort split//,shift}<>=~/.$/;$c=$&;@s=(0,0);map{$v=&$c($_);if(O($_)==O($v)){$s[0]+=$_;$s[1]+=$v;}}0..$`;@s=sort{$a<=>$b}@s;say"@s"

```
> 0 votes

# Answer
# MATL, ~~44~~ 47 bytes

```
0&)Uqw70=?32- 5*9/]OOhw:"@t9*5/32+VY@Um?@4MhvXs

```

Try it online!

*(+3 bytes to output `0 0` for no such temperatures (instead of empty output).)*
> 0 votes

---
Tags: code-golf
---


title: Expand the Binomial

text:
# Question
Title: Expand the Binomial
## Challenge

Given three numbers \\$a\\$, \\$b\\$, and \\$n\\$, you must expand \\$(a + bx)^n\\$ in ascending powers of \\$x\\$ up to \\$x^3\\$.

## Binomial Expansion

***Note that this method is an approximation***

The binomial expansion works like so:

```
(a + bx)^n = a^n(1 + bx/a)^n
           = a^n(1 + n(bx/a) + n(n -1)(bx/a)^2/2! + n(n-1)(n-1)(bx/a)^3/3!)

```

Or, more readable:

$$\begin{align} (a+bx)^n &= a^n\left(1+\frac{b}{a}x\right)^n\\ &\approx a^n\left(1 + n\left(\frac{b}{a}x\right)+ \frac{n(n-1)}{2!}\left(\frac{b}{a}x\right)^2 + \frac{n(n-1)(n-2)}{3!}\left(\frac{b}{a}x\right)^3\right) \end{align}$$

Which simplifies down to an expression in the form

$$\alpha + \beta x + \gamma x^2 + \delta x^3$$

Where \\$\alpha\\$, \\$\beta\\$, \\$\gamma\\$ and \\$\delta\\$ are constants which you must calculate.

These constants should be given to at least 3 decimal places where appropriate (i.e. 1.2537 should be output instead of 1.25, but 1.2 can be output if the answer is exactly 1.2).

You must then output these four constants in a list (in order as they appear in the final equation). This list may be separated however you wish.

# Input

The inputs \\$a\\$ and \\$b\\$ will be integers in the range -100 to 100 inclusive where \\$a \neq 0\\$.

\\$n\\$ will be given to one decimal place and will be in the range \\$-2 \leq n \leq 2\\$

# Examples

## `a = 1, b = 6, n = -1.0`

```
1, -6, 36, -216

```

## `a = 3, b = 2, n = 2.0`

```
9, 12, 4, 0

```

## `a = 5, b = 4, n = 0.3`

```
1.621, 0.389, -0.109, 0.049

```

# Winning

The shortest code in bytes wins.

# Answer
## Mathematica, ~~45~~ 37 bytes

It turns out that `Binomial` threads over lists!

```
Binomial[#3,r={0,1,2,3}]#2^r#^(#3-r)&

```

Each of `Binomial[#3,r={0,1,2,3}]`, `#2^r` and `#^(#3-r)` returns a length-4 list, which are implicitly multiplied together term-by-term, giving the binomial coefficients.

---

Old solution (45 bytes):

```
FoldList[#~D~x/#2&,(#+#2x)^#3,Range@3]/.x->0&

```

And a 43-byte solution that works except when `n = 0`:

```
Series[(#+#2x)^#3,{x,0,3}][[3]]~PadRight~4&

```
> 4 votes

# Answer
# Haskell, ~~80 74 64 63~~ 62 bytes

I've tried many more sophisticated approaches, but they all were longer than the straightforward approach. (In meantime golfed down a bit.)

Thanks for -1 byte @Laikoni!

```
(a#b)n|c<-b/a=(*a**n)<$>1:c*n:map(n*(n-1)*c*c*)[1/2,c*(n-2)/6]

```

Try it online!
> 4 votes

# Answer
# Haskell, 46 bytes

```
(a%b)n=scanl(*)(a**n)[(n-i+1)/i*b/a|i<-[1..3]]

```

Try it online!

Expresses the ratios of consecutive terms, and uses them to recover the terms by `scanl(*)` starting with the first term `a*n`. The ratios have form `(n-i+1)/i*b/a`.
> 4 votes

# Answer
# Casio BASIC, 144 bytes

```
?→A
?→B
?→N
B÷A→B
A^N→A
A((N(N-1))÷2!×B²)→S
A((N(N-1)(N-2)÷3!×B³)→T
N×B×A→N
ClrText
Locate 1,1,A
Locate 1,2,N
Locate 1,3,S
Locate 1,4,T

```

Output is in a line like so:

```
34.5
20
11
56.85

```
> 3 votes

# Answer
# JavaScript, ~~55~~ ~~53~~ 50 bytes

```
(a,b,n)=>[s=a**n,s*=n*(b/=a),s*=--n*b/2,s*--n*b/3]

```

```
~~(a,b,n)=>a?[s=a**n,s*=n*(b/=a),s*=--n*b/2,s*--n*b/3]:(t=[0,0,0,0])|n>3?t:(t[n]=b**n,t)~~
```
> 1 votes

# Answer
# MATL, 30 bytes

```
^li1G/3:"t@^2G@:q-HM/p*w]x4$h*

```

Try it online!

Input in `a`, `n`, `b` order.
> 1 votes

# Answer
# Pari/GP, 29 bytes

```
(a,b,n)->Vec((a+b*x)^n)[1..4]

```

Try it online!
> 1 votes

# Answer
# Axiom, 80 bytes

```
h(a,b,n)==(v:=series((a+b*x)^(n::Fraction INT));[coefficient(v,i)for i in 0..3])

```

exercises

```
(91) -> h(1,6,-1.0)
...
   (91)  [1,- 6,36,- 216]
                                            Type: List Expression Integer
(92) -> h(3,2,2.0)
   (92)  [9,12,4,0]
                                            Type: List Expression Integer
(93) -> h(5,4,0.3)
                  10+-+3     10+-+3    10+-+3
          10+-+3 6 \|5     42 \|5   476 \|5
   (93)  [ \|5  ,-------,- --------,---------]
                    25        625     15625
                                            Type: List Expression Integer
(94) -> map(numeric, %)
   (94)
   [1.6206565966 927624351, 0.3889575832 0626298443, - 0.1089081232 9775363564,
    0.0493716825 6164831482 4]
                                                         Type: List Float

```
> 0 votes

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


title: Upgoat or Downgoat?

text:
# Question
Title: Upgoat or Downgoat?
Given an image of a goat, your program should best try to identify whether the goat is upside down, or not.

## Examples

These are examples of what the input may be. Not actual inputs

Input:

Output: `Downgoat`

## Spec

Your program should be at most 30,000 bytes

* The input will contain the full goat
* The picture will always contain a goat
* If the goat is upside down, output `Downgoat`, otherwise `Upgoat`

Input will be however you can take an image as an input (file name, base64 of the image, etc.)

Don't rely on the image name or other metadata for containing "Upgoat" or "Downgoat" as the gist file names are just for reference.

---

*Please don't hardcode*. It's boring, I can't enforce it completely but I can ask nicely.

## Test Cases

Gist with images. images beginning with `downgoat` have `Downgoat` output and images beginning with `upgoat` have `Upgoat` output.

Second Batch of Test Cases Make sure to test your images on all the test cases. These images are a `jpg`s. The image sizes do vary but not by *that* much.

---

**Note:** A few test cases may be added before accepting an answer to avoid answers which hardcode and to check the general performance of the program.

Bonus points for getting my avatar correct :P

## Scoring

Score is a percent which can be calculated by: `(number_correct / total) * 100`

# Answer
# Mathematica, 100%, 141 bytes

```
f@x_:=Count[1>0]@Table[ImageInstanceQ[x,"caprine animal",RecognitionThreshold->i/100],{i,0,50}];If[f@#>f@ImageReflect@#,"Up","Down"]<>"goat"&

```

Well, this feels more than a little like cheating. It's also incredibly slow as well as being very silly. Function `f` sees roughly how high you can set the Recognition threshold in one of Mathematica's computer vision builtins, and still recognise the image as a Caprine animal.

We then see whether the image or the flipped image is more goaty. Works on your profile image only because tie is broken in favour of downgoat. There are probably loads of ways this could be improved including asking it if the image represents Bovids or other generalisations of the Caprine animal entity type.

Answer as written scores 100% for the first testing set and 94% for the second testing set, as the algorithm yields an inconclusive result for goat 1. This can be raised back up to 100% at the expense of an even longer computational time by testing more values of `RecognitionThreshold`. Raising from `100` to `1000` sufficies; for some reason Mathematica thinks that's a very ungoaty image! Changing the recognition entity from Caprine animal to Hoofed Mammal also seems to work.

## Ungolfed:

```
goatness[image_] := Count[
                      Table[
                        ImageInstanceQ[
                          image, Entity["Concept", "CaprineAnimal::4p79r"],
                          RecognitionThreshold -> threshold
                        ],
                        {threshold, 0, 0.5, 0.01}
                      ],
                      True
                    ]

Function[{image},
  StringJoin[
    If[goatness[image] > goatness[ImageReflect[image]],
      "Up",
      "Down"
    ],
    "goat"
  ]
]

```

---

# Alternative solution, 100% + bonus

```
g[t_][i_] := ImageInstanceQ[i, "caprine animal", RecognitionThreshold -> t]
f[i_, l_: 0, u_: 1] := Module[{m = (2 l + u)/3, r},
  r = g[m] /@ {i, ImageReflect@i};
  If[Equal @@ r,
   If[First@r, f[i, m, u], f[i, l, m]],
   If[First@r, "Up", "Down"] <> "goat"
   ]
  ]

```

This one uses the same strategy as before, but with a binary search over the threshold. There are two functions involved here:

* `g[t]` returns whether or not its argument is a goaty image with threshold `t`.
* `f` takes three parameters: an image, and an upper and lower bound on the threshold. It is recursive; it works by testing a threshold `m` between the upper and lower thresholds (biased towards the lower). If the image and the reflected image are both goaty or non-goaty, it eliminates the lower or upper part of the range as appropriate and calls itself again. Otherwise, if one image is goaty and the other is non-goaty, it returns `Upgoat` if the first image is goaty and `Downgoat` otherwise (if the second, reflected image is goaty).

The function definitions deserves a little explanation. First, function application is left-associative. This means that something like `g[x][y]` is interpreted as `(g[x])[y]`; "the result of `g[x]` applied to `y`."

Second, assignment in Mathematica is roughly equivalent to defining a replacement rule. That is, `f[x_] := x^2` does *not* mean "declare a function named `f` with parameter `x` that returns `x^2`;" its meaning is closer to, "whenever you see something like `f[ ... ]`, call the thing inside `x` and replace the whole thing with `x^2`."

Putting these two together, we can see that the definition of `g` is telling Mathematica to replace any expression of the form `(g[ ... ])[ ... ]` with the right-hand side of the assignment.

When Mathematica encounters the expression `g[m]` (in the second line of `f`), it sees that the expression does not match any rules that it knows and leaves it unchanged. Then it matches the `Map` operator `/@`, whose arguments are `g[m]` and the list `{i, ImageReflect@i}`. (`/@` is infix notation; this expression is exactly equivalent to `Map[g[m], { ... }]`.) The `Map` is replaced by applying its first argument to each element of its second argument, so we get `{(g[m])[i], (g[m])[ ... ]}`. Now Mathematica sees that each element matches the definition of `g` and does the replacement.

In this way we got `g` to act like a function that returns another function; that is, it acts roughly like we wrote:

```
g[t_] := Function[{i}, ImageInstanceQ[i, "caprine animal", RecognitionThreshold -> t]]

```

(Except in this case `g[t]` on its own evaluates to a `Function`, whereas before `g[t]` on its own was not transformed at all.)

The final trick I use is an optional pattern. The pattern `l_ : 0` means "match any expression and make it available as `l`, or match nothing and make `0` available as `l`." So, if you call `f[i]` with one argument (the image to test) it is as if you had called `f[i, 0, 1]`.

Here is the test harness I used:

```
gist = Import["https://api.github.com/gists/3fb94bfaa7364ccdd8e2", "JSON"];
{names, urls} = Transpose[{"filename", "raw_url"} /. Last /@ ("files" /. gist)];
images = Import /@ urls;
result = f /@ images
Tally@MapThread[StringContainsQ[##, IgnoreCase -> True] &, {names, result}]
(* {{True, 18}} *)

user = "items" /.
           Import["https://api.stackexchange.com/2.2/users/40695?site=codegolf", "JSON"];
pic = Import[First["profile_image" /. user]];
name = First["display_name" /. user];
name == f@pic
(* True *)

```
> 350 votes

# Answer
# JavaScript, 93.9%

```
var solution = function(imageUrl, settings) {

  // Settings
  settings = settings || {};
  var colourDifferenceCutoff = settings.colourDifferenceCutoff || 0.1,
      startX = settings.startX || 55,
      startY = settings.startY || 53;

  // Draw the image to the canvas
  var canvas = document.createElement("canvas"),
      context = canvas.getContext("2d"),
      image = new Image();
  image.src = imageUrl;
  image.onload = function(e) {
    canvas.width = image.width;
    canvas.height = image.height;
    context.drawImage(image, 0, 0);

    // Gets the average colour of an area
    function getColour(x, y) {

      // Get the image data from the canvas
      var sizeX = image.width / 100,
          sizeY = image.height / 100,
          data = context.getImageData(
            x * sizeX | 0,
            y * sizeY | 0,
            sizeX | 0,
            sizeY | 0
          ).data;

      // Get the average of the pixel colours
      var average = [ 0, 0, 0 ],
          length = data.length / 4;
      for(var i = 0; i < length; i++) {
        average[0] += data[i * 4] / length;
        average[1] += data[i * 4 + 1] / length;
        average[2] += data[i * 4 + 2] / length;
      }
      return average;
    }

    // Gets the lightness of similar colours above or below the centre
    function getLightness(direction) {
      var centre = getColour(startX, startY),
          colours = [],
          increment = direction == "above" ? -1 : 1;
      for(var y = startY; y > 0 && y < 100; y += increment) {
        var colour = getColour(startX, y);

        // If the colour is sufficiently different
        if(
          (
            Math.abs(colour[0] - centre[0]) +
            Math.abs(colour[1] - centre[1]) +
            Math.abs(colour[2] - centre[2])
          ) / 256 / 3
          > colourDifferenceCutoff
        ) break;
        else colours.push(colour);
      }

      // Calculate the average lightness
      var lightness = 0;
      for(var i = 0; i < colours.length; i++) {
        lightness +=
          (colours[i][0] + colours[i][1] + colours[i][2])
          / 256 / 3 / colours.length;
      }

      /*
      console.log(
        "Direction:", direction,
        "Checked y = 50 to:", y,
        "Average lightness:", lightness
      );
      */
      return lightness;
    }

    // Compare the lightness above and below the starting point
    //console.log("Results for:", imageUrl);
    var above = getLightness("above"),
        below = getLightness("below"),
        result = above > below ? "Upgoat" : "Downgoat";
    console.log(result);
    return result;
  };
};
```

```
<div ondrop="event.preventDefault();r=new FileReader;r.onload=e=>{document.getElementById`G`.src=imageUrl=e.target.result;console.log=v=>document.getElementById`R`.textContent=v;solution(imageUrl);};r.readAsDataURL(event.dataTransfer.files[0]);" ondragover="event.preventDefault()" style="height:160px;border-radius:12px;border:2px dashed #999;font-family:Arial,sans-serif;padding:8px"><p style="font-style:italic;padding:0;margin:0">Drag & drop image <strong>file</strong> (not just link) to test here... (requires HTML5 browser)</p><image style="height:100px" id="G" /><pre id="R"></pre></div>
```

## Explanation

Simple implementation of @BlackCap's idea of checking where the light is coming from.

Most of the goats are in the centre of their images, and their bellies are always darker than their backs because of the sunlight. The program starts at the middle of the image and makes a note of the colour. It then gets the average lightness of the pixels above and below the centre up to where the colour is different to the colour at the centre (when the body of the goat ends and the background starts). Whichever side is lighter determines whether it is an upgoat or a downgoat.

Fails for downgoat 9 and upgoats 7 and 9 in the second test case.
> 78 votes

# Answer
# Java, ~~93.9%~~ 100%

This works by determining the row contrast in the upper and lower part of the image. I assume that the contrast in the bottom half of the image is bigger for 2 reasons:

* the 4 legs are in the bottom part
* the background in the upper part will be blurred because it is usually the out-of-focus-area

I determine the contrast for each row by calculating the difference of neighboring pixel values, squaring the difference, and summing all squares.

## Update

Some images from the second batch caused problems with the original algorithm.

### upgoat3.jpg

This image was using transparency which was ignored previously. There are several possibilities to solve this problem, but I simply chose to render all images on a 400x400 black background. This has the following advantages:

* handles images with alpha channel
* handles indexed and grayscale images
* improves performance (no need to process those 13MP images)

### downgoat8.jpg/upgoat8.jpg

These images have exaggerated detail in the body of the goat. The solution here was to blur the image in vertical direction only. However, this generated problems with images from the first batch, which have vertical structures in the background. The solution here was to simply count differences which exceed a certain threshold, and ignore the actual value of the difference.

Shortly said, the updated algorithm looks for areas with many differences in images that after the preprocessing look like this:

```
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.image.BufferedImage;
import java.awt.image.Raster;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;

public class UpDownGoat {
    private static final int IMAGE_SIZE = 400;
    private static final int BLUR_SIZE = 50;

    private static BufferedImage blur(BufferedImage image) {
        BufferedImage result = new BufferedImage(image.getWidth(), image.getHeight() - BLUR_SIZE + 1,
                BufferedImage.TYPE_INT_RGB);
        for (int b = 0; b < image.getRaster().getNumBands(); ++b) {
            for (int x = 0; x < result.getWidth(); ++x) {
                for (int y = 0; y < result.getHeight(); ++y) {
                    int sum = 0;
                    for (int y1 = 0; y1 < BLUR_SIZE; ++y1) {
                        sum += image.getRaster().getSample(x, y + y1, b);
                    }
                    result.getRaster().setSample(x, y, b, sum / BLUR_SIZE);
                }
            }
        }
        return result;
    }

    private static long calcContrast(Raster raster, int y0, int y1) {
        long result = 0;
        for (int b = 0; b < raster.getNumBands(); ++b) {
            for (int y = y0; y < y1; ++y) {
                long prev = raster.getSample(0, y, b);
                for (int x = 1; x < raster.getWidth(); ++x) {
                    long current = raster.getSample(x, y, b);
                    result += Math.abs(current - prev) > 5 ? 1 : 0;
                    prev = current;
                }
            }
        }
        return result;
    }

    private static boolean isUp(File file) throws IOException {
        BufferedImage image = new BufferedImage(IMAGE_SIZE, IMAGE_SIZE, BufferedImage.TYPE_INT_RGB);
        Graphics2D graphics = image.createGraphics();
        graphics.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BICUBIC);
        graphics.drawImage(ImageIO.read(file), 0, 0, image.getWidth(), image.getHeight(), null);
        graphics.dispose();
        image = blur(image);
        int halfHeight = image.getHeight() / 2;
        return calcContrast(image.getRaster(), 0, halfHeight) < calcContrast(image.getRaster(),
                image.getHeight() - halfHeight, image.getHeight());
    }

    public static void main(String[] args) throws IOException {
        System.out.println(isUp(new File(args[0])) ? "Upgoat" : "Downgoat");
    }
}

```
> 66 votes

# Answer
## Python 3, 91.6%

-edited with the new test cases

set filename to the goat picture you wish to test. It uses a kernel to make an image top/bottom asymmetric.I tried the sobel operator, but this was better.

```
from PIL import Image, ImageFilter
import statistics
k=(2,2,2,0,0,0,-2,-2,-2)
filename='0.png'
im=Image.open(filename)
im=im.filter(ImageFilter.Kernel((3,3),k,1,128))
A=list(im.resize((10,10),1).getdata())
im.close()
a0=[]
aa=0
for y in range(0,len(A)):
    y=A[y]
    a0.append(y[0]+y[1]+y[2])
aa=statistics.mean(a0)
if aa<383.6974:
    print('Upgoat')
else:
    print('Downgoat')

```
> 42 votes

# Answer
# Python 3, OpenCV with Hough Transform, 100%

My original idea was to detect the vertical lines of the goat's legs and determine its vertical position relative to the body and horizon.

As it turns out, in all the images, the ground is extremely noisy, making lots of Canny edge detection output and corresponding detected lines from the Hough transform. My strategy was then to determine whether the horizontal lines lie in the upper or lower half of the image, which was enough to solve the problem.

```
# Most of this code is from OpenCV examples
import cv2
import numpy as np

def is_upgoat(path):
    img = cv2.imread(path)
    height, width, channels = img.shape
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    edges = cv2.Canny(gray, 100, 200, apertureSize=3)

    lines = cv2.HoughLines(edges, 1, np.pi/180, 200, None, 0, 0, np.pi/2-0.5, np.pi/2+0.5)
    rho_small = 0

    for line in lines:
        rho, theta = line[0]
        a = np.cos(theta)
        b = np.sin(theta)
        x0 = a*rho
        y0 = b*rho
        x1 = int(x0 + 5000*(-b))
        y1 = int(y0 + 5000*(a))
        x2 = int(x0 - 5000*(-b))
        y2 = int(y0 - 5000*(a))

        if rho/height < 1/2: rho_small += 1
        cv2.line(img,(x1,y1),(x2,y2),(0,0,255),1, cv2.LINE_AA)

    output_dir = "output/"
    img_name = path[:-4]
    cv2.imwrite(output_dir + img_name + "img.jpg", img)
    cv2.imwrite(output_dir + img_name + "edges.jpg", edges)

    return rho_small / len(lines) < 1/2

for i in range(1, 10):
    downgoat_path = "downgoat" + str(i) + ".jpg"
    print(downgoat_path, is_upgoat(downgoat_path))

for i in range(1, 10):
    upgoat_path = "upgoat" + str(i) + ".jpg"
    print(upgoat_path, is_upgoat(upgoat_path))

```

Here's the entire function without outputting images:

```
def is_upgoat(path):
    img = cv2.imread(path)
    height, width, channels = img.shape
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    edges = cv2.Canny(gray, 100, 200, apertureSize=3)

    lines = cv2.HoughLines(edges, 1, np.pi/180, 200, None, 0, 0, np.pi/2-0.5, np.pi/2+0.5)
    rho_small = 0

    for line in lines:
        rho, theta = line[0]
        if rho/height < 1/2: rho_small += 1

    return rho_small / len(lines) < 1/2

```

Downgoat1 edges:

Downgoat1 lines:

Upgoat2 edges and lines:

The method even worked well on particularly noisy images. Here's downgoat3 edges and lines:

---

# Addendum

It turns out median blur and adaptive Gaussian thresholding before the Hough Transform works much better than Canny edge detection, mostly since median blur is good in noisy areas. However the problems of my original approach immediately are clear: prominent background lines are detected, as well as the goat's face in some pictures.

```
def is_upgoat2(path):
    img = cv2.imread(path)
    #height, width, channels = img.shape
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    gray = cv2.medianBlur(gray, 19)
    thresh = cv2.adaptiveThreshold(gray, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
                                   cv2.THRESH_BINARY_INV, 11, 2)

    lines = cv2.HoughLinesP(thresh, 1, np.pi / 180, threshold=100,
                            minLineLength=50, maxLineGap=10)

    vert_y = []
    horiz_y = []
    for line in lines:
        x1, y1, x2, y2 = line[0]
        # Vertical lines
        if x1 == x2 or abs((y2-y1)/(x2-x1)) > 3:
            vert_y.append((y1+y2)/2)
            cv2.line(img, (x1, y1), (x2, y2), (0, 255, 0), 2)

        # Horizontal lines
        if x1 != x2 and abs((y2-y1)/(x2-x1)) < 1/3:
            horiz_y.append((y1+y2)/2)
            cv2.line(img, (x1, y1), (x2, y2), (0, 0, 255), 2)

    print(np.median(vert_y), np.median(horiz_y))

```

Here's downgoat8:

Contours (code not shown) detect the top edge of the goat (spine) pretty well but fail to get the entire shape.

**Further research:** OpenCV has Haar-feature based object detection which is usually used for things like cars and faces, but it could probably work for goats too, given their distinctive shape.

2D Feature recognition looks promising (template matching won't work because of scaling and rotation) but I'm too lazy to figure out OpenCV for C++.
> 26 votes

# Answer
## Python 3, numpy, scikit, 100%

This code runs a goat-trained image classifier against a single filename, printing out 'Upgoat' or 'Downgoat'. The code itself is one line of python3, preceded by a single gigantic string, and an import line. The giant string is actually the goat-trained classifier, which is unpickled at runtime and given the input image for classification.

The classifier was created by using the TPOT system, from Randal Olson and team at the University of Pennsylvania. TPOT helps to evolve machine-learning image classifier pipelines using genetic programming. Basically it uses artificial selection to choose various parameters and types of classification to work best with the input data you give it, so you don't have to know much about machine learning to get a pretty good pipeline setup. https://github.com/EpistasisLab/tpot . TPOT runs on top of scikit-learn, of INRIA et al, http://scikit-learn.org/stable/

I gave TPOT about a hundred goat images that I found on the internet. I chose ones that looked relatively similar to the goats in Test, i.e. "in a field", from the side, without much else going on in the image. The output of this TPOT process was basically a scikit-learn ExtraTreesClassifier object. This image classifier, after being trained (or 'fit') on my goats, was pickled into the huge string. The string, then, contains not just classifier code, but the "imprint" of the training of all the goat images it was trained on.

I cheated slightly during training, by including the 'goat standing on a log' test image in the training images, but it still works pretty well on generic goat-in-a-field images. There seems to be a tradeoff - the longer I let TPOT run, the better classifier it created. However, better classifiers also seem to be 'bigger' and eventually run up against the 30,000 byte limit given by @Downgoat in the golf game. This program as it stands is currently at about 27kbytes. Please note that the 'second group' of test images is broken, as is the 'backup link', so I'm not sure how it would do on them. If they were to be repaired, I would probably start over, rerun TPOT and feed it a bunch of new images, and see if I could create a new classifier under 30k bytes.

Thanks

```
import pickle,bz2,base64,numpy,sys,skimage.transform,skimage.io
s='''
[encoded data, 26320 characters]
'''
print(['','Up','Down'][int(pickle.loads(bz2.decompress(base64.b64decode(s))).predict(numpy.array([skimage.transform.resize(skimage.io.imread(sys.argv[1],as_grey=True),(24,12),mode='constant').flatten()]))[0])]+'goat')
```

---

update: per request here is the training data, resized to 24x12 and combined into a single image for ease of upload/presentation. its over a hundred images. http://deeplearning.net/datasets/ , http://www.vision.caltech.edu/Image\_Datasets/Caltech256/, duckduckgo image search, google image search, etc
> 15 votes

# Answer
# Scikit-learn with Random Forests, 100%

The tried-and-true approach is convnets, but random forests can perform very well out-of-the-box (few parameters to tune). Here I show some general techniques in image classification tasks.

I started off with 100 images of goats for training I found through Google Images (AFAIK none in the training data match the test data). Each image is rescaled to 20x16 in grayscale, then the array is flattened to produce one row in a 2D array. A flipped version of the image is also added as a row for the training data. I did not need to use any data augmentation techniques.

Then I feed the 2D array into the random forest classifier and call predict to produce 50 decision trees. Here is the (messy) code:

```
RESIZE_WIDTH = 20
RESIZE_HEIGHT = 16

def preprocess_img(path):
    img = cv2.imread(path, 0)  # Grayscale
    resized_img = cv2.resize(img, (RESIZE_WIDTH, RESIZE_HEIGHT))
    return resized_img

def train_random_forest(downgoat_paths, upgoat_paths, data_paths):
    assert len(data_paths) == 100
    # Create blank image grid
    img_grid = np.zeros((10*RESIZE_HEIGHT, 10*RESIZE_WIDTH), np.uint8)

    # Training data
    TRAINING_EXAMPLES = 2*len(data_paths)
    train_X = np.zeros((TRAINING_EXAMPLES, RESIZE_WIDTH*RESIZE_HEIGHT), np.uint8)
    train_y = np.zeros(TRAINING_EXAMPLES, np.uint8)

    TEST_EXAMPLES = len(downgoat_paths) + len(upgoat_paths)
    test_X = np.zeros((TEST_EXAMPLES, RESIZE_WIDTH*RESIZE_HEIGHT), np.uint8)
    test_y = np.zeros(TEST_EXAMPLES, np.uint8)

    for i, data_path in enumerate(data_paths):
        img = preprocess_img(data_path)

        # Paste to grid
        ph = (i//10) * RESIZE_HEIGHT
        pw = (i%10) * RESIZE_WIDTH
        img_grid[ph:ph+RESIZE_HEIGHT, pw:pw+RESIZE_WIDTH] = img
        flipped_img = np.flip(img, 0)

        # Add to train array
        train_X[2*i,], train_y[2*i] = img.flatten(), 1
        train_X[2*i+1,], train_y[2*i+1] = flipped_img.flatten(), 0

    cv2.imwrite("grid.jpg", img_grid)

    clf = RandomForestClassifier(n_estimators=50, verbose=1)
    clf.fit(train_X, train_y)
    joblib.dump(clf, 'clf.pkl')

    for i, img_path in enumerate(downgoat_paths + upgoat_paths):
        test_X[i,] = preprocess_img(img_path).flatten()
        test_y[i] = (i >= len(downgoat_paths))

    predict_y = clf.predict(test_X)
    print(predict_y)
    print(test_y)
    print(accuracy_score(predict_y, test_y))

    # Draw tree 0
    tree.export_graphviz(clf.estimators_[0], out_file="tree.dot", filled=True)
    os.system('dot -Tpng tree.dot -o tree.png')

def main():
    downgoat_paths = ["downgoat" + str(i) + ".jpg" for i in range(1, 10)]
    upgoat_paths = ["upgoat" + str(i) + ".jpg" for i in range(1, 10)]
    data_paths = ["data/" + file for file in os.listdir("data")]

    train_random_forest(downgoat_paths, upgoat_paths, data_paths)

```

Here is the first decision tree (though since the model is in an ensemble, it is not particularly useful)
> 13 votes

---
Tags: code-challenge, image-processing, classification, test-battery
---


# Question
Title: Products that equal a sum and vice versa
A fun pair of equivalences is *1 + 5 = 2 · 3* and *1 · 5 = 2 + 3*. There are many like these, another one is *1 + 1 + 8 = 1 · 2 · 5* and *1 · 1 · 8 = 1 + 2 + 5*. In general a product of *n* positive integers equals a sum of *n* positive integers, and vice versa.

In this challenge you must generate all such combinations of positive integers **for an input *n \> 1***, excluding permutations. You can output these in any reasonable format. For example, all the possible solutions for *n = 3* are:

```
(2, 2, 2) (1, 1, 6)
(1, 2, 3) (1, 2, 3)
(1, 3, 3) (1, 1, 7)
(1, 2, 5) (1, 1, 8)

```

The program that can generate the most combinations for the highest *n* in one minute on my **2GB RAM**, 64-bit Intel Ubuntu laptop wins. If your answer uses more than 2GB of RAM or is written in a language I can not test with freely available software, I will not score your answer. I will test the answers in two weeks time from now and choose the winner. Later non-competing answers can still be posted of course.

Since it's not known what the full sets of solutions for all *n* are, you are allowed to post answers that generate incomplete solutions. However if another answer generates a (more) complete solution, **even if their maximum *n* is smaller**, that answer wins.

---

# To clarify, here's the scoring process to decide the winner:

1. I will test your program with n=2, n=3, etc... I store all your outputs and stop when your program takes more than a minute or more than 2GB RAM. Each time the program is run for a given input n, it will be terminated if it takes more than 1 minute.
2. I look at all the results for all programs for n = 2. If a program produced less valid solutions than another, that program is eliminated.
3. Repeat step 2 for n=3, n=4, etc... The last program standing wins.

# Answer
# C (gcc), n = 50000000 with 6499 results in 59 s

To avoid producing over a terabyte of output consisting almost entirely of 1s, a sequence of (say) 49999995 1s is abbreviated as `1x49999995`.

```
#include <stdio.h>
#include <stdlib.h>

static int n, *a1, k1 = 0, *a2, k2 = 0, s1, p1, *factor;

static void out() {
  if (s1 == p1) {
    for (int i = 0; i < k1 && i < k2; i++) {
      if (a1[i] < a2[i])
        return;
      else if (a1[i] > a2[i])
        break;
    }
  }

  for (int i = 0; i < k1; i++)
    printf("%d ", a1[i]);
  printf("1x%d | ", n - k1);
  for (int i = 0; i < k2; i++)
    printf("%d ", a2[i]);
  printf("1x%d\n", n - k2);
}

static void gen2(int p, int s, int m);

static void gen3(int p, int s, int m, int x, int q) {
  int r = s - n + k2 + 2;
  int d = factor[q];
  do {
    if (x * d <= m)
      x *= d;
    q /= d;
  } while (q % d == 0);
  do {
    if (q == 1) {
      a2[k2++] = x;
      gen2(p / x, s - x, x);
      k2--;
    } else {
      gen3(p, s, m, x, q);
    }
    if (x % d != 0)
      break;
    x /= d;
  } while (p / (x * q) >= r - x * q);
}

static void gen2(int p, int s, int m) {
  int n2 = n - k2;
  if (p == 1) {
    if (s == n2)
      out();
  } else if (n2 >= 1 && m > 1) {
    int r = s - n2 + 1;
    if (r < 2 || p < r)
      return;
    if (m > r)
      m = r;
    if (factor[p] <= m)
      gen3(p, s, m, 1, p);
  }
}

static void gen1(int p, int s, int m) {
  int n1 = n - k1;
  p1 = p;
  s1 = s + n1;
  gen2(s1, p1, s + n1 + 1 - n);
  if (n1 != 0) {
    int *p1 = &a1[k1++];
    for (int x = 2; x <= m && p * x <= s + x + n1 - 1; x++) {
      *p1 = x;
      gen1(p * x, s + x, x);
    }
    k1--;
  }
}

int main(int argc, char **argv) {
  if (argc < 2)
    return 1;
  n = atoi(argv[1]);
  if (n < 2)
    return 1;
  a1 = malloc(n * sizeof(int));
  a2 = malloc(n * sizeof(int));
  factor = calloc(4 * n - 1, sizeof(int));
  for (int p = 2; p < 4 * n - 1; p++)
    if (factor[p] == 0) {
      factor[p] = p;
      for (int i = p; i <= (4 * n - 2) / p; i++)
        factor[p * i] = p;
    } else if (factor[p] < factor[p / factor[p]]) {
      factor[p] = factor[p / factor[p]];
    }
  gen1(1, 0, 3 * n - 1);
  return 0;
}

```

Try it online!
> 4 votes

# Answer
# Mathematica, n=293 with 12 solutions

OP changed the challenge and asks for input
Here is the new code that takes any n as input
For n=293 you get the 12 solutions

```
If[#<5,Union[Sort/@Select[Tuples[{1,2,3,4,5,6,7,8,9},{#}],Tr@#==Times@@#&]],For[a=1,a<3,a++,For[b=a,b<3,b++,For[c=b,c<5,c++,For[d=c,d<10,d++,For[e=d,e<300,e++,If[Tr[s=Join[Table[1,#-5],{a,b,c,d,e}]]==Times@@s,Print[s]]]]]]]]&

```

**input**

> \[n\]

You can test this algorithm on Wolfram Sandbox which is an online **freely available software**
Just follow the link, paste the code (ctrl+v),**paste input at the end of the code** and press shift+enter to run.
You will get all my solutions in seconds

Here is also Try it online! in C++(gcc)
(Many thanks to @ThePirateBay for supporting and translating my code to a free language)

this program generates only solutions of the form {a,b,c}{a,b,c}
which means a+b+c=a\*b\*c

**It takes 1 sec to compute**

the twelve solutions are:

> {1,1...,1,1,1,2,293} {1,1...,1,1,1,2,293}
> {1,1...,1,1,1,3,147} {1,1...,1,1,1,3,147}
> {1,1...,1,1,1,5,74} {1,1...,1,1,1,5,74}
> {1,1...,1,1,2,2,98} {1,1...,1,1,2,2,98}
> {1,1...,1,1,2,3,59} {1,1...,1,1,2,3,59}
> {1,1...,1,1,2,5,33} {1,1...,1,1,2,5,33}
> {1,1...,1,1,2,7,23} {1,1...,1,1,2,7,23}
> {1,1...,1,1,2,8,20} {1,1...,1,1,2,8,20}
> {1,1...,1,1,3,3,37} {1,1...,1,1,3,3,37}
> {1,1...,1,1,3,4,27} {1,1...,1,1,3,4,27}
> {1,1...,1,1,3,7,15} {1,1...,1,1,3,7,15}
> {1,1...,1,2,2,6,13} {1,1...,1,2,2,6,13}
> 3 votes

# Answer
# Python 2, n=175, 28 results in 59s

Made it a little slower using a reduction factor 2, but gets more solutions starting with n=83

I get results for n up to 92 on TIO in a single run.

```
def submats(n, r):
    if n == r:
        return [[]]
    elif r > 6:
        base = 1
    else:
        base = 2
    mx = max(base, int(n*2**(1-r)))

    mats = []
    subs = submats(n, r+1)
    for m in subs:
        if m:
            mn = m[-1]
        else:
            mn = 1
        for i in range(mn, mx + 1):
            if i * mn < 3*n:
                mats += [m + [i]]
    return mats

def mats(n):
    subs = []
    for sub in submats(n, 0):
        sum = 0
        prod = 1
        for m in sub:
            sum += m
            prod *= m
        if prod > n and prod < n*3:
            subs += [[sub, sum, prod]]
    return subs

def sols(n):
    mat = mats(n)
    sol = [
        [[1]*(n-1)+[3*n-1],[1]*(n-2)+[2,2*n-1]],
    ]
    if n > 2:
        sol += [[[1]*(n-1)+[2*n+1],[1]*(n-2)+[3,n]]]
    for first in mat:
        for second in mat:
            if first[2] == second[1] and first[1] == second[2] and [second[0], first[0]] not in sol:
                sol += [[first[0], second[0]]];
    return sol

```

Try it online!
> 2 votes

# Answer
# Mathematica, n=19 with 11 solutions

this is my new answer according to OP's new criteria

```
(SOL = {};
For[a = 1, a < 3, a++,
For[b = a, b < 3, b++,
For[c = b, c < 5, c++,
 For[d = c, d < 6, d++,
  For[e = d, e < 3#, e++,
   For[k = 1, k < 3, k++,
    For[l = k, l < 3, l++,
     For[m = l, m < 5, m++,
      For[n = m, n < 6, n++, For[o = n, o < 3#, o++,
        s = Join[Table[1, # - 5], {a, b, c, d, e}];
        t = Join[Table[1, # - 5], {k, l, m, n, o}];
        If[Tr[s[[-# ;;]]] == Times @@ t[[-# ;;]] &&
          Tr[t[[-# ;;]]] == Times @@ s[[-# ;;]],
         AppendTo[SOL,{s[[-#;;]],t[[-#;;]]}]]]]]]]]]]]];
Union[SortBy[#,Last]&/@SOL])&

```

if you give an input \[n\] at the end, the program displays the solutions

here are my results (on my old laptop 64-bit 2.4GHz)

> n-\>solutions
> 2 -\> 2
> 3 -\> 4
> 4 -\> 3
> 5 -\> 5
> 6 -\> 4
> 7 -\> 6
> 8 -\> 5
> 9 -\> 7
> 10 -\> 7
> 11 -\> 8
> 12 -\> 6 (in 17 sec)
> 13 -\> 10 (in 20 sec)
> 14 -\> 7 (in 25 sec)
> 15 -\> 7 (in 29 sec)
> 16 -\> 9 (in 34 sec)
> 17 -\> 10 (in 39 sec)
> 18 -\> 9 (in 45 sec)
> 19 -\> 11 (in 51 sec)
> 20 -\> 7 (in 58 sec)
> 1 votes

# Answer
# Ruby, n=12 gets 6 solutions

At least on TIO, usual results for 1 up to 11

```
->n{
  arr=[*1..n*3].product(*(0..n-2).map{|x|
    [*1..[n/3**x,2].max]|[1]
  }).select{|a|
    a.count(1) >= n-4
  }.map(&:sort).uniq
  arr.product(arr).map(&:sort).uniq.select{|r|
    r[0].reduce(&:+) == r[1].reduce(&:*) &&
    r[0].reduce(&:*) == r[1].reduce(&:+)
  }
}

```

Try it online!

Gets 10 results under a minute for n=13 on my laptop.
> 1 votes

# Answer
## Haskell, a lot of solutions fast

```
import System.Environment

pr n v = prh n v v

prh 1 v l = [ [v] | v<=l ]
prh n 1 _ = [ take n $ repeat 1 ]
prh _ _ 1 = []
prh n v l = [ d:r | d <-[2..l], v `mod` d == 0, r <- prh (n-1) (v`div`d) d ]

wo n v = [ (c,k) | c <- pr n v, let s = sum c, s>=v,
                   k <- pr n s, sum k == v, s>v || c>=k ]

f n = concatMap (wo n) [n+1..3*n]

main = do [ inp ] <- getArgs
          let results = zip [1..] $ f (read inp)
          mapM_ (\(n,s) -> putStrLn $ (show n) ++ ": " ++ (show s)) results

```

`f` computes the solutions, the `main` function adds getting the input from the command line and some formatting and counting.
> 1 votes

# Answer
# Haskell, n=10 with 2 solutions

```

import           Data.List

removeDups = foldl' (\seen x -> if x `elem` seen then seen else x : seen) []
removeDups' = foldl' (\seen x -> if x `elem` seen then seen else x : seen) []

f n= removeDups $ map sort filterSums
  where maxNumber = 4
        func x y = if (((fst x) == (fst.snd$y)) && ((fst y) == (fst.snd$x)))
                     then [(snd.snd$x),(snd.snd$y)]
                     else [[],[]]
        pOf = removeDups' $ (map sort (mapM (const [1..maxNumber]) [1..n]))
        sumOf = map (\x->((sum x),((product x), x))) pOf
        filterSums = filter (\x-> not$(x == [[],[]])) (funcsumOfsumOf)

```

This performs like crap, but I at least fixed it so I am actually addressing the challenge now!

Try it online!
> 0 votes

# Answer
# Axiom, n=83 in 59 seconds here

```
-- copy the below text in the file name "thisfile.input"
-- and give something as the command below in the Axiom window:
-- )read C:\Users\thisuser\thisdirectory\thisfile

)cl all
)time on

-- controlla che l'array a e' formato da elementi  a.i<=a.(i+1)
tv(a:List PI):Boolean==(for i in 1..#a-1 repeat if a.i> a.(i+1) then return false;true)

-- funzione incremento: incrementa a, con #a=n=b/3,sotto la regola di "reduce(+,a)+#a-1>=reduce(*,a)"
-- e che n<reduce(*,a)<3*n ed reduce(+,a)<3*n
inc3(a:List PI):INT==
   i:=1; n:=#a; b:=3*n
   repeat
      if i>n  then return 0
      x:=reduce(*,a)
      if x>=b then a.i:=1
      else
          y:=reduce(+,a)
          if y>b then a.i=1
          else if y+n-1>=x then
                      x:=x quo a.i
                      a.i:=a.i+1
                      x:=x*a.i
                      if tv(a) then break
                      else a.i:=1
          else a.i:=1
      i:=i+1
   if x<=n then return inc3(a) -- x<=n non va
   x

-- ritorna una lista di liste di 4 divisori di n
-- tali che il loro prodotto e' n
g4(n:PI):List List PI==
  a:=divisors(n)
  r:List List PI:=[]
  for i in 1..#a repeat
     for j in i..#a repeat
        x:=a.i*a.j
        if x*a.j>n then break
        for k in j..#a repeat
            y:=x*a.k
            if y*a.k>n then break
            for h in k..#a repeat
                z:=y*a.h
                if z=n  then r:=cons([a.h,a.k,a.j,a.i],r)
                if z>=n then break
  r

-- ritorna una lista di liste di 3 divisori di n
-- tali che il loro prodotto e' n
g(n:PI):List List PI==
  a:=divisors(n)
  r:List List PI:=[]
  for i in 1..#a repeat
     for j in i..#a repeat
        x:=a.i*a.j
        if x*a.j>n then break
        for k in j..#a repeat
            y:=x*a.k
            if y=n  then r:=cons([a.k,a.j,a.i],r)
            if y>=n then break
  r

-- cerca che [a,b] nn si trovi gia' in r
searchr(r:List List List PI,a:List PI,b:List PI):Boolean==
  aa:=sort(a); bb:=sort(b)
  for i in 1..#r repeat
      x:=sort(r.i.1);y:=sort(r.i.2)
      if x=aa and y=bb then return false
      if x=bb and y=aa then return false
  true

-- input n:PI
-- ritorna r, tale che se [a,b] in r
-- allora #a=#b=n
--        ed reduce(+,a)=reduce(*,b) ed reduce(+,b)=reduce(*,a)
f(n:PI):List List List PI==
  n>100000 or n<=1 =>[]
  a:List PI:=[]; b:List PI:=[]; r:List List List PI:=[]
  for i in 1..n repeat(a:=cons(1,a);b:=cons(1,b))
  if n~=72 and n<86 then  m:=min(3,n)
  else                    m:=min(4,n)
  q:=reduce(*,a)
  repeat
    w:=reduce(+,a)
    if n~=72 and n<86 then x:= g(w)
    else                   x:=g4(w)
    if q=w then r:=cons([copy a, copy a],r)
    for i in 1..#x repeat
           for j in 1..m repeat
                  b.j:=(x.i).j
           -- per costruzione abbiamo che reduce(+,a)= prodotto dei b.i=reduce(*,b)
           -- manca solo di controllare che reduce(+,b)=reduce(*,a)=q
           if reduce(+,b)=q and searchr(r,a,b) then r:=cons([copy a, copy b],r)
    q:=inc3(a)
    if q=0 then break
  r

```

results:

```
 for i in 2..83 repeat output [i, # f(i)]
   [2,2][3,4][4,3][5,5][6,4][7,6][8,5][9,7][10,7][11,8][12,6][13,10][14,7][15,7]
   [16,10][17,10][18,9][19,12][20,7][21,13][22,9][23,14][24,7][25,13][26,11]
   [27,10][28,11][29,15][30,9][31,16][32,11][33,17][34,9][35,9][36,13][37,19]
   [38,11][39,14][40,12][41,17][42,11][43,20][44,12][45,16][46,14][47,14][48,13]
   [49,16][50,14][51,17][52,11][53,20][54,15][55,17]
   [56,14][57,20][58,17][59,16][60,15][61,28][62,15][63,16][64,17][65,18]
   [66,14][67,23][68,20][69,19][70,13][71,18][72,15][73,30][74,15][75,17][76,18]
   [77,25][78,16][79,27][80,9][81,23][82,17][83,26]

 f 3
    [[[1,2,5],[8,1,1]],[[1,3,3],[7,1,1]],[[1,2,3],[1,2,3]],[[2,2,2],[6,1,1]]]
                                     Type: List List List PositiveInteger
                                   Time: 0.07 (IN) + 0.05 (OT) = 0.12 sec

```

The way for run above text in Axiom, would be, copy all that text in a file, save the file with the name: Name.input, in a Axiom window use ")read absolutepath/Name".
results: (# f(i) finds the length of the array f(i), that is the number of solutions)
> 0 votes

---
Tags: integer, fastest-code
---


title: Calculate the Trump Tax

text:
# Question
Title: Calculate the Trump Tax
If elected president, Donald Trump plans to implement a system of four income tax brackets (full details can be found on his website here). Your job is to take two inputs, annual income and filing status (single, married, or head of household), and output the income tax that must be paid.

# Income Tax Brackets

(We are only interested in the income tax rate; you can ignore the long-term capital gain rate).

Note that income taxes are computed using *marginal rates* — that is, you only pay the bracket rate for the portion that exceeds the bracket's minimum amount.

For example, a single filer making $45,000 a year would pay 0% on the first $25,000, and 10% on the $20,000 after that, for a total of $2,000 in taxes.

A married couple filing jointly for $500,000 would count 25% only on the amount exceeding $300,000, and add $45,000 to that to account for the income earned in lower brackets (which is 10% of $50,000 plus 20% of $200,000).

# Input/Output

Input/Output is flexible. You can take input as command-line arguments or prompt for inputs, as well as either return or output/display the result. The inputs and output must be numbers, but you are free to determine what the second number would be (for example, 0 = single, 1 = married, 2 = head of household). Just don't be ridiculous - **Single digit numbers only**.

Also, functionality for decimal inputs (i.e. including cents) is undefined, so you only have to worry about integer inputs. For your output, you may either output a decimal value or round it to the nearest whole number.

# Test Cases

Although the second number's range can be flexible as stated above, these test cases assume that 0 = single, 1 = married, and 2 = head of household:

```
25000  0 --> 0
37501  2 --> 0.1 or 0
51346  1 --> 134.6 or 135
75000  0 --> 7500
75000  1 --> 2500
123456 2 --> 13441.2 or 13441
424242 0 --> 91060.5 or 91061

```

# Answer
> 7 votes
# Pyth, 32 bytes

```
*c@_j270588 6shS,6ca0tQ*12500E20

```

Test suite.

* 2 = single
* 4 = married
* 3 = head of household

## Some ridiculous encodings:

### Previous 6-byte:

```
JQ.vCE

```

Test suite.

* 74892585093965377905208487730659359537614936740881725652453863997600444976 = single
* 74892585093965377905208487730659359537614936740881725652668629404830675504 = married
* 74892585093965377905208487730659359537614936740881725652526490039149933104 = head of household

Encodes the whole program into the second number.

### Previous 24-byte:

```
JjE^T6*c@tJhS,7shctQhJ20

```

Test suite.

* 25000000000000000000002000004000004000004000004000005 = single
* 50000000000000000000002000004000004000004000004000005 = married
* 37500000000000000000002000004000004000004000004000005 = head of household

### Previous 26-byte:

```
*c@_j270588 6shS,6ca0tQE20

```

Test suite.

* 25000 = single
* 50000 = married
* 37500 = head of household

# Answer
> 5 votes
# TI-Basic, 34 32 bytes

Variable `F` is filing status where 2 = single, 3 = head of household, and 4 = married. Also, E is the scientific E.

```
Prompt I,F:4I/F>E5{.5,1,3:.1Isum(Ans{1,1,.5

```

Explanation:

```
Prompt I,F          get input into I and F
4I/F               converts the income so it fits the married tax bracket
    >E5{.5,1,3     gives a list like {0 0 0}, {1 0 0}, {1 1 0}, or {1 1 1} based on bracket
   sum(Ans{1,1,.5  Multiplies previous list by {1 1 .5} and sums it
.1I                Previous number is 0 1 2 or 2.5, so multiply by .1 and then by income

```

# Answer
> 1 votes
## JavaScript (ES6), 52 bytes

```
(i,m,g=b=>i>b&&(i-=b)/10)=>g(m=15e4/m)+g(m)+g(m*4)/2

```

Key:

```
6 = Single
3 = Married
4 = Head

```

# Answer
> 0 votes
# Stax, 24 bytes

```
ï¥Ωü+àqGZvwJ╫BMwbë↕)bÿ╠»

```

Run and debug it

\begin{align}\text{Single}&\mapsto 2\\ \text{Married}&\mapsto4\\ \text{Head of Household}&\mapsto3 \end{align}

Outputs a fraction.

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


title: Play a game of Dice Cricket

text:
# Question
Title: Play a game of Dice Cricket
Dice Cricket is a game I was introduced to as a child and have used as a way to pass time for years since. I couldn't find a Wikipedia page so I'll explain the rules below.

# Dice Cricket Rules

## Premise

Dice Cricket is a game similar to scoring a game of cricket as you watch it but rather than *watching* and recording the result, you are *rolling a die* and recording the result.

The results are recorded in a table as displayed at the bottom.

## Display

Dice Cricket uses a specific display to show all the information happening.

The table has 11 rows. Each row represents a batter. The layout of the row is explained below.

```
+------+------------------------------+---------+-----+
| Name |    Runs                      | How Out |Score|
+------+------------------------------+---------+-----+

```
* Name: The name must be a string made up entirely of letters, upper or lower case
* Runs: A batter can face 30 balls. Each ball can be one of `1 2 4 6 . /`. This will be explained in more detail below
* How Out: The way the batter was out. Can be any of `Bowled, LBW (Leg Before Wicket), Caught, Retired or Not Out`
* Score: The sum of all numbers in `Runs`

## How the Game Works

In a game, there are always 2 batters out on the pitch. The first player is by default the current batter and the second in the "off" batter.

A game is made up of "balls": each ball in a cricket match is represented by a dice roll. Each roll does a different command:

* 1,2,4 and 6 make the batter score that much. If 1 is rolled, the current batter becomes the "off" batter and the "off" batter becomes the current
* 3 is a "dot ball", meaning that nothing happens. It is represented in the `Runs` section as a `.` and scores 0. A `0` may not be used to represent it.
* 5 is a wicket. If 5 is rolled, the current batter is "out", This means that a `/` is added to the runs and from then on, the batter cannot score anymore runs. The batter is then swapped with the next batter who has not batted. The `How Out` section is a random choice of the possible ways to get out: `Bowled, LBW, Caught`

Example for a wicket (this is just for clarity, this isn't how its outputted)

```
player a is on 4,6,2,6,4
player b is on 6,4,2,6,6
player c hasn't batted
player a is current batter

WICKET!!!

player a is on 4,6,2,6,4,/
player b in on 6,4,2,6,6
player c is on NOTHING
player c is current batter

```

Every 6 balls, the two batters switch; the current batter becomes the "off" batter and the "off" batter becomes the current batter

If the `Runs` section is filled (30 balls), the batter is out and the `How Out` section is set to `Retired`. A `/` **isn't** placed at the end of the `Runs` box.

# Actual Challenge (yes all that was rules of the game)

Your challenge is to output a completed table (like the example at the end), given a list of names. The contents of the output should contain only the table and/or leading or trailing whitespace.

## Rules

* Standard loopholes are disallowed
* All 11 players should have something in the `Runs` section.
* Only 1 player can be `Not Out`. Every other non-retired player should be out of a choice of `[Bowled, LBW, Caught]`
* The names can be any length between 1 and 6 that matches the regex `A-Za-z`
* The final line in the table should be the total line (see example)
* You don't have to align the text in the table in any way, but the row and column separators must be aligned.

## Example

```
Input:
['Fred', 'Sonya', 'David', 'Ben', 'Cody', 'Hazel', 'Nina', 'Kim', 'Cath', 'Lena', 'Will']
Output:
+------+------------------------------+---------+-----+
| Name | Runs                         | How Out |Total|
+------+------------------------------+---------+-----+
|Fred  |.662/                         | Caught  | 14  |
+------+------------------------------+---------+-----+
|Sonya |1164/                         | Caught  | 12  |
+------+------------------------------+---------+-----+
|David |/                             |   LBW   |  0  |
+------+------------------------------+---------+-----+
|Ben   |424/                          |   LBW   | 10  |
+------+------------------------------+---------+-----+
|Cody  |62/                           | Bowled  |  8  |
+------+------------------------------+---------+-----+
|Hazel |/                             |   LBW   |  0  |
+------+------------------------------+---------+-----+
|Nina  |161.6226166..44261442/        | Caught  | 64  |
+------+------------------------------+---------+-----+
|Kim   |11/                           | Caught  |  2  |
+------+------------------------------+---------+-----+
|Cath  |6.21/                         |   LBW   |  9  |
+------+------------------------------+---------+-----+
|Lena  |/                             | Bowled  |  0  |
+------+------------------------------+---------+-----+
|Will  |2                             | Not Out |  2  |
+------+------------------------------+---------+-----+
|               Total Runs                      | 121 |
+-----------------------------------------------+-----+

```

# Answer
> 2 votes
# Python 3, ~~650~~ ~~621~~ ~~582~~ ~~572~~ 588 bytes

```
from random import*
h=str
c=h.center
a='+'.join(map('-'.__mul__,[0,6,30,9,5,0]))+'\n'
b=lambda x,r=6:x.ljust(r,' ')
j=''.join
t=lambda a:sum(map(int,a[:-1].replace(*'.0')))
P=print
def s(i=30):
 while i:x=choice('12.4/6');yield x;i=('/'!=x)*~-i
def f(n,T=0):
 n=[*map(b,n)]
 P(a+f'| Name | Runs{" "*25}| How Out |Total|')
 for x in n[:-1]:S=j(s());T+=t(S);P(a,x,b(S,30),c(choice(['Bowled','LBW','Caught']),9),c(h(t(S)),5),sep='|',end='|\n')
 S=j(s());P(a,n[-1],b(S,30),' Not Out ',c(h(t(S)),5),sep='|',end='|\n');P(a+f'|{15*" "}Total Runs{15*" "}       |{c(h(T),5)}|\n+{47*"-"}+{5*"-"}+')

```

Try it online!

Well, it's been over 24 hours and this took me about an hour to whip up, so I hope I'm not FGITW'ing anyone, and I haven't golfed in Python in a while, so this was fun (although this is the second time I've answered one of my own questions with a long Python answer)

Please feel free to post golf suggestions, Python isn't my best language for golfing.

-68 bytes thanks to FlipTack!

-8 bytes thanks to Mr. Xcoder

+16 bytes due to a bug

# Answer
> 1 votes
# Charcoal, ~~277~~ 255 bytes

```
≔Ｅ¹¹⟦⟦⟧⁰Ｓ⟧θ≔⮌θηＷ⊖Ｌη«≔⊟ηι≔‽12.4/6ζ⊞υζ⊞§ι⁰ζ≔⎇⁼ζ/⁺²‽³⁼³⁰Ｌ§ι⁰ζ¿ζ§≔ι¹ζ⊞ηι¿⊖Ｌη¿⁼¬﹪Ｌυ⁶¬εＦ⟦⊟η⊟η⟧⊞ηκ»”|⁴Ｂ\[⎇⁻℅↧Ｔ`⁵·5ＫＭＫ⟲M≦»→´⁶_⭆∨Ｒ▷↥l⁹KＧ…≦”Ｆθ«◨⊟ι⁷◨Σ§ι⁰¦³²§⪪”(3⪪⪫⧴πＺJL:∨ＸＩ±ＵＲＤ↗Σ9⟦FZ∕↖l⪪”⁷⊟ι◧ＩΣＥ⊟ιΣκ⁶⸿⸿»”|ＱºWＰD⟧zＮφ[v？Π'vＧ”◧ＩΣＥυΣι²⁸Ｊ±¹±¹ＦＥ¹³⁻²⁷⊗ι«Ｂ⁵⁵ιＢ⁴⁹ι¿‹ι²⁷«Ｂ³⁹ιＢ⁸ι

```

Try it online! Link is to verbose version of code. Explanation:

```
≔Ｅ¹¹⟦⟦⟧⁰Ｓ⟧θ

```

Read in the 11 names (input is flexible: JSON, space separated, or newline separated) and create an array `q` of 11 batters, represented by their balls (as an array), status (as an integer) and name.

```
≔⮌θη

```

Create a reversed copy of the batters `h`. This represents the batters that are not out. The last two elements are the off and current batters.

```
Ｗ⊖Ｌη«

```

Repeat while there are at least two batters available.

```
≔⊟ηι

```

Extract the current batter to `i`.

```
≔‽12.4/6ζ

```

Generate a random ball in `z`.

```
⊞υζ

```

Add it to the overall list of balls using the predefined empty list `u`.

```
⊞§ι⁰ζ

```

Add it to the current batter's balls.

```
≔⎇⁼ζ/⁺²‽³⁼³⁰Ｌ§ι⁰ζ

```

If the ball is a `/`, then generate a random status `2..4`, otherwise if this is the batter's 30th ball then set the status to `1` otherwise `0`.

```
¿ζ§≔ι¹ζ⊞ηι

```

If the batter is out then store the batter's status otherwise put the batter back in to bat.

```
¿⊖Ｌθ¿⁼¬﹪ΣＥηＬκ⁶¬ζ

```

If there are at least two batters left, and the batter was out xor 6 balls have been played, then...

```
Ｆ⟦⊟η⊟η⟧⊞ηκ»

```

...take the off and current batters and put them back in reverse order.

```
”|⁴Ｂ\[⎇⁻℅↧Ｔ`⁵·5ＫＭＫ⟲M≦»→´⁶_⭆∨Ｒ▷↥l⁹KＧ…≦”

```

Print the header.

```
Ｆθ«

```

Loop over the batters.

```
◨⊟ι⁷

```

Print the batter's name.

```
◨Σ§ι⁰¦³²

```

Print the batter's balls.

```
§⪪”(3⪪⪫⧴πＺJL:∨ＸＩ±ＵＲＤ↗Σ9⟦FZ∕↖l⪪”⁷⊟ι

```

Print the batter's status by indexing into the string `Not OutRetiredBowled Caught LBW` split into substrings of length 7.

```
◧ＩΣＥ⊟ιΣκ⁶

```

Print the batter's score.

```
⸿⸿»

```

Move to the start of the next line but one.

```
”|ＱºWＰD⟧zＮφ[v？Π'vＧ”◧ＩΣＥυΣι²⁸

```

Print the total.

```
Ｊ±¹±¹ＦＥ¹³⁻²⁷⊗ι«Ｂ⁵⁵ιＢ⁴⁹ι¿‹ι²⁷«Ｂ³⁹ιＢ⁸ι

```

Draw boxes around everything.

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


title: Circular Keyboard Spiral

text:
# Question
Title: Circular Keyboard Spiral
This is a QWERTY keyboard.

```
Q W E R T Y U I O P
 A S D F G H J K L
  Z X C V B N M

```

We can "spiral out" on this keyboard, starting from G. The spiral will start at G, go to H, then to Y, then to T, then F, then V, then B, then N, then J, then U, then R, then D, then C,... etc. Your challenge is to, given a number 1 ≤ **N** ≤ 26, output the first **N** characters in this spiral. (If you are confused, refer to the pictures at the end of the post.)

The catch? Your program's score is proportional to the indices of characters found inside the spiral!

## Scoring

1. For every letter (case-insensitive) in your code, add the index of that character in the spiral to your score (starting from 1).
2. For every character not in the spiral, add 10 to your score.
3. The lowest score wins.

For example, the program `print("Hello, World!")` has a score of 300.

For your convenience, I have written an automatic program grader.

```
var SPIRAL = "GHYTFVBNJURDCMKIESXLOWAZPQ";
function grade(program) {
    var score = 0;
    for(var i = 0; i < program.length; i++) {
        if(/^[A-Za-z]$/.test(program[i])) {
            score += SPIRAL.indexOf(program[i].toUpperCase()) + 1;
        }
        else {
            score += 10;
        }
    }
    return score;
}

input.oninput = function() {
    output.value = "Your program's score is: " + grade(input.value);
}
```

```
textarea { width: 500px; height: 6em; font-style: monospace; }
```

```
<textarea id="input"></textarea>
<textarea disabled id="output"></textarea>
```

## Other rules

* Your submission may be a program or function.
* You may take **N** starting at 0 or 1 and ending at 25 or 26, respectively, but the outputs should still begin with "G" and end with "GHYTFVBNJURDCMKIESXLOWAZPQ".
* You must output the characters in the spiral **in order**.
* If a function, you may return a list of characters instead of a string.
* You may have one trailing newline following the output.
* You may use lowercase letters instead of uppercase letters, or a combination of both.

## Test cases

```
number -> output
1 -> G
2 -> GH
5 -> GHYTF
12 -> GHYTFVBNJURD
15 -> GHYTFVBNJURDCMK
24 -> GHYTFVBNJURDCMKIESXLOWAZ
26 -> GHYTFVBNJURDCMKIESXLOWAZPQ

```

## Pictures

The spiral superimposed:

# Answer
# Japt, ~~304~~ ~~264~~ 162 points

*Saved 40 points thanks to @ConorO'Brien*

```
;î"历锋㫿鮹㿬崴ꨜꎋΞ"csG

```

Test it online!

In order to save as many points as possible, the entire string is condensed into 9 Unicode chars by interpreting each run of 3 letters as a base-36 number, then converting to a code point. The program itself takes this compressed string (which costs 110 points, including the quotes) and maps each `c`harcode by converting it to a `s`tring in base-36 (`G` after the `;` at the beginning). `î` takes the first {input} chars of this, which is implicitly printed.
> 14 votes

# Answer
# C, score: 544

```
g(g){write(1,"GHYTFVBNJURDCMKIESXLOWAZPQ",g);}

```

Try it online!
> 11 votes

# Answer
# Spiral, score:  ~~61921~~   ~~5127~~   ~~4715~~   ~~4655~~  4191

```
4.X~>v+^#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v
   X *   X X X X X X X X X X X X X X X X X X X X X X X X X
   ! >   h y t f V b n j u [ ( 1 3 2 ) ] U J N B F T Y H G
0;vgv*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*vvv****v+^v+^v+^v+^*v++4
    X X X X X X X X X X X X X X X X X X X X X X X X X X
    v v v v v v v v v v v v v v v v v v v v v v v v v v
    Y y J F V u t U [ G H B n 3 N 2 j ) h g f ] ( 1 b T

```

An interpreter can be found here.

**Explanation:**

```
P.X~ZZ*v+^#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v
   X       X X X X X X X X X X X X X X X X X X X X X X X X X
   !       h y t f V b n j u r d c m k i e s x l o w a z p q
0;vgv*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*v*****************************************************************vP
    X X X X X X X X X X X X X X X X X X X X X X X X X X
    v v v v v v v v v v v v v v v v v v v v v v v v v v
    z y x w V u t s r q p o n m l k j i h g f e d c b a

```

The program begins at the `0` character on the fourth line. The first piece of code to run is `0;vg`. `;` takes a number as input and places it in the stack. `v` places what is in the register (a zero) into the stack. It will be used as the counter. `g` is a label, when it is reached, the control jumps to the other occurence of the letter `g` in the code.

So this is where the control is now:

```
X
v
g

```

Since there is whitespace in all other directions, the instruction pointer starts moving upwards. `v` places a zero into the stack, and `X` pops it from the stack immediately. Because the popped value is zero, the instruction pointer moves to `X` (otherwise it would treat it as whitespace).

By default, the control flow is in turn-right mode, so now when it reaches the junction, the instruction pointer turns to the right. `v` yet again pushes a zero into the stack, `*` increments the register by one.

```
v*v*v
  X
  v
  g

```

The next `v` places what is in the register (number 1) into the stack, the instruction pointer attempts to turn to the right, hitting the next `X`. The value just added to the stack is popped and placed in the register. Because it is non-zero, `X` is not entered, and the IP proceeds to the next `*` on the right instead, again incrementing the value in the register.

```
v*v*v*v*v
X X X X X
v v v v v
i h g f e

```

This happens again and again until we reach the end of this part and the line of `*`s begins. By now the value in the register is 6, which is ASCII letter `g` minus ASCII letter `a`. Thus with a line of 97 `*`s we increment the value in the register to 103, which matches the letter `g` we want to print. `v` pushes it into the stack, and `P` is another label upon hitting which we jump to the other `P` on the first line of the code.

Here `.` pops the value from the stack and prints it as a character. After that `X` pops the extraneous zero from the stack, then `~` compares the two remaining values in the stack (the values being the counter and the input value). If the values are the same, the operator places zero in the stack (otherwise -1 or 1). Again, the control attempts to turn right. `X` pops the value of the comparison from the stack, if it is zero, `X`, and after it `!` is entered, terminating the program.

```
P.X~ZZ*v+^
   X
   !

```

Otherwise the IP continues to the `Z`, which is a label which in this case jumps only one step to the right. The reason for doing this is that jumping sets the value in the register back to zero. `*` increments the register and `v` places the resulting 1 into the stack. `+` pops the two top elements of the stack (the 1 and the counter), adds them, and places the result in the stack (in effect this increments the counter by one). `^` copies the result from the stack to the register without removing it from the stack.

`#` decrements the value in the register by one, `v` pushes the decremented value to the stack, the IP attempts to turn to the right, and the `X` pops the value from the stack. If the value is non-zero the IP keeps moving to the east, decrementing the value in the register, until it hits zero, and the IP enters an `X` branch.

```
#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v#v
 X X X X X X X X X X X X X X X X X X X X X X X X X
 h y t f V b n j u r d c m k i e s x l o w a z p q

```

The branch leads to a label corresponding to the value of the counter. Upon hitting the label, the control jumps to the other occurence of the label in the section where we started with the label `g`, starting another iteration. As with the `g`, the value in the register gets incremented up to the ASCII value of the letter we need to print. Then the character is printed and the counter incremented, another label is selected. This happens until after the last iteration the counter equals the input, and the program terminates.

**Edit:**

```
P.X~Zv+^
   X *
   ! Z

```

Achieves the same thing as

```
P.X~ZZ*v+^
   X
   !

```

but with less whitespace.

**Edit 2:**

```
vv****v+^v+^v+^v+^*v++P

```

Can be used instead of:

```
*****************************************************************vP

```
> 10 votes

# Answer
# Haskell, 471

```
(`take`"GHYTFVBNJURDCMKIESXLOWAZPQ")

```

Try it online!

This is a bit of a benchmark, I feel like there must be a better way, but its the best I've found so far.

## Explanation

I suppose I should explain this for those not familiar with Haskell too well. The function `take` takes the first n elements of the list. It is called like this:

```
take n list

```

We want to take the first n elements of the sting `"GHYTFVBNJURDCMKIESXLOWAZPQ"`, so we want something like

```
f n=take n"GHYTFVBNJURDCMKIESXLOWAZPQ"

```

We can do better though, we can infix `take` using backticks

```
f n=n`take`"GHYTFVBNJURDCMKIESXLOWAZPQ"

```

And now this can be made pointfree

```
(`take`"GHYTFVBNJURDCMKIESXLOWAZPQ")

```
> 6 votes

# Answer
# Jelly, 211 score

19 bytes

```
“eȷÞ('¢ạẓkȮV’œ?ØAðḣ

```

Try it online!

saved a bunch of score thanks to Emigna's suggestion to use `œ?` :D
> 5 votes

# Answer
# TI-Basic (TI-84 Plus CE), ~~454~~ 432 points

```
sub("GHYTFVBNJURDCMKIESXLOWAZPQ",1,Ans

```

-22 points from Conor O'Brien

Run with `5:prgmNAME`.

Returns/prints the `sub`string from `1` to `Ans` (the number input).

TI-Basic is a tokenized langauge, so I'm scoring this by the byte values of the tokens.

`sub(` is 0xbb 0x0c, so 20

`"` is 0x2a, so `*`, so 10\*2=20

Uppercase letters don't change, so the string is 351

`,` is 0x2b, so `+`, so 10\*2=20

`1` is 0x31, so `1`, so 10

`Ans` is 0x72, which is `r`, so 11

20 + 20 + 351 + 20 + 10 + 11 = 432
> 4 votes

# Answer
# Befunge, Score: 531

```
QPZAWOLXSEIKMCDRUJNBVFTYHG"&\>,# 1#\-# :# _@

```

I feel this challenge would have been more interesting if the output had to be in a spiral as well.
> 4 votes

# Answer
# Vim, ~~461~~ 418

```
CGHYTFVBNJURDCMKIESXLOWAZPQg^[G@" D

```

Thanks @pacholik for -43 score!

Try it online!
> 4 votes

# Answer
# Python 3, score = ~~762~~ 753

1-based input. This is worse than the trivial approach, since it uses 37 non-letters. It is somewhat interesting, though.

*-9 thanks to Leo.*

```
h=lambda g:g and h(g-1)+chr(65+int('GYGGYHGYYGYTGTYHGYGGHGGTGHGYGYGFGHGGYGGHHGGHHYYGHGHGGYFGGYHGGTHGHTGGGGGFGGVHGT'[g*3-3:g*3],35)%26)or''

```

Try it online!
> 3 votes

# Answer
# 05AB1E, score: 204

```
.•3ŽγY
₁ùÐÁo0ª ’ö:•£

```

Try it online!
> 3 votes

# Answer
# Brainf\**k, score = 2690

Input a single byte ranging from `0x1` to `0x1a`.

```
>>++++>+++>>>>++++++++++[<+<-<+>>>-]<<--<+++>>>++>->+++++++++++>++++++>-------->---->-->>---------->--------->+++++>++++++++>--->+>----------->+++++++++>------->+++++++>++++++++++++>----->------>+>>+++++++[<+++++++++++[<[[+<]+<]>->[[>]>]<<<-]>-]<<[-]>,[[<]<.[-]>+[>]<-]

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog), score: 391

```
↑∘'GHYTFVBNJURDCMKIESXLOWAZPQ'

```

Try it online!

The only use for Latin letters in Dyalog is in variable names and some system functions. Apart from that, only glyphs and some Greek letters are used.
> 2 votes

# Answer
# Python 3, 522

```
lambda g:"GHYTFVBNJURDCMKIESXLOWAZPQ"[:g]

```

Try it online!

An anonymous lambda utilizing Python's slicing of strings (`"asdf"[:i]` gets the first `i` characters of `"asdf"`)
> 1 votes

# Answer
# Clojure, ~~484~~ 474 points

-10 points because apparently a `%` can exist after a number without a space separating them!? I might have to go back over and improve some submissions.

```
#(subs"ghytfvbnjurdcmkiesxlowazpq"0%)

```

An anonymous function. Basically a Clojure port of what's already been posted. Scores nicely! I think this is the first Clojure program I've ever written that doesn't contain a single space.

```
(defn spiral [n]
  ; Substring the hardcoded list, going from index 0 to n
  (subs "ghytfvbnjurdcmkiesxlowazpq" 0 n))

```
> 1 votes

# Answer
# Ly, 521 points

```
"QPZAWOLXSEIKMCDRUJNBVFTYHG"ns[,spol];

```

Try it online!

I don't feel as though this is optimizable.
> 1 votes

# Answer
# Bash, score: 465

```
cut -b-$1<<<GHYTFVBNJURDCMKIESXLOWAZPQ

```

Try it online!
> 1 votes

# Answer
# Husk, 293 bytes

```
↑¨ghytfvb⌋ȷÜdcmkÏexl⁰Λzpq

```

This is the shortest one I could find, next closer `¨gHYtfvB⌋ȷÜdCmkÏex←ẆAzpq¨` for a score of 293..

Try it online!

### Explanation

Brute-force search, turns out all lower-case gave the best score. It's basically the same as @Wheat Wizard's solution, `take` () on a compressed string (`¨`).
> 1 votes

# Answer
# Common Lisp, score: 580

```
(subseq"GHYTFVBNJURDCMKIESXLOWAZPQ"0(read))

```

Try it online!
> 1 votes

# Answer
# Excel, 490 points

```
=LEFT("GHYTFVBNJURDCMKIESXLOWAZPQ",A1)

```

Convention for Excel ansers is to take input from `A1`. Changing this to `G1` cuts 22 points (468).

```
=LEFT("GHYTFVBNJURDCMKIESXLOWAZPQ",G1)

```
> 1 votes

# Answer
# C#, score 546

```
g=>"GHYTFVBNJURDCMKIESXLOWAZPQ".Substring(0,g);

```
> 1 votes

# Answer
## Rust, score 443

It is not often that Rust is good at code golf but here it beats many languages

```
|g|&"GHYTFVBNJURDCMKIESXLOWAZPQ"[..g]

```
> 1 votes

# Answer
# Golang, score 861

```
func g(g int){io.WriteString(os.Stdout,"GHYTFVBNJURDCMKIESXLOWAZPQ"[0:g])}

```

Play it online !
> 1 votes

# Answer
# Javascript ES6, 527 points

```
g=>`GHYTFVBNJURDCMKIESXLOWAZPQ`.slice(0,g)

```

## Try it !

```
f=g=>`GHYTFVBNJURDCMKIESXLOWAZPQ`.slice(0,g)

input.oninput = function() {
    output.value = f(input.value);
}
```

```
textarea { width: 500px; height: 6em; font-style: monospace; }
```

```
<textarea id="input"></textarea>
<textarea disabled id="output"></textarea>
```
> 1 votes

# Answer
# PHP, 590 points

```
<?=substr(GHYTFVBNJURDCMKIESXLOWAZPQ,0,$argv[1]);

```

Try it online!
> 1 votes

# Answer
# PHP, score 584

fiddled a bit with the dictionary; the fact that xoring the string cuts it off rendered `substr` obsolete.

```
<?=">1 -?/;73,+=:420<*!56.8#)("^str_repeat(y,$argv[1]);

```

Try it online.
> 1 votes

# Answer
## Perl, score 568 517

*Thanks to Nahuel Fouilleul for saving 51 points.*

```
($_)=GHYTFVBNJURDCMKIESXLOWAZPQ=~/.{$_}/g

```

Try it online!
> 0 votes

# Answer
# Mathematica, 528

```
"GHYTFVBNJURDCMKIESXLOWAZPQ"~StringTake~#&

```

Try it online!
> 0 votes

# Answer
# Pyth, score: 371

```
<"GHYTFVBNJURDCMKIESXLOWAZPQ

```

Try it here.

## How?

```
<"GHYTFVBNJURDCMKIESXLOWAZPQ"Q   implicit string end, implicit input
<                            Q   first Q(=input) elements ...
 "GHYTFVBNJURDCMKIESXLOWAZPQ"    ... of this string

```
> 0 votes

# Answer
# Ruby, 453 points

```
->g{'GHYTFVBNJURDCMKIESXLOWAZPQ'[0,g]}

```

Try it online!
> 0 votes

# Answer
# \>\<\>, 558+16= 574 points

```
<;v? : <{"GHYTFVBNJURDCMKIESXLOWAZPQ"
  >$o1-^

```

Uses the `-v` flag to push input onto the stack.

Pushes the spiral onto the stack in reverse order, then rotates the input to the top. Then, while the top of the stack is non-zero, prints the next letter and decrements the top of the stack.

Try it online!
> 0 votes

# Answer
# Pyth, 261 points

```
<."AZJ{Û§zoÆæÏýú

```

**Try it here!**

This outputs uppercase letter. For lowercase, you can try the alternative 261 byter.
> 0 votes

# Answer
# Julia 0.6, score 433

```
g->"GHYTFVBNJURDCMKIESXLOWAZPQ"[1:g]

```

Try it online!
> 0 votes

---
Tags: ascii-art, code-challenge, keyboard
---


# Question
Title: Find the longest path, avoiding obstacles in a 2D plane
## The Scenario

You are given a matrix of size m x n (width x height) with m\*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can move vertically or horizontally, but can visit each spot only once. The goal is to cover as much area/spots as possible, avoiding obstacles.

## Input

A 2D Matrix consisting of 0s and 1s and the coordinates of starting point.

Example Matrix1:

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

```

Example Matrix2:

```
0(0,0) 0(0,1) 1(0,2) 0(0,3) 0(0,4)
0(1,0) 1(1,1) 0(1,2) 0(1,3) 0(1,4)
0(2,0) 0(2,1) 0(2,2) 1(2,3) 0(2,4)
0(3,0) 1(3,1) 0(3,2) 0(3,3) 0(3,4)
0(4,0) 0(4,1) 1(4,2) 0(4,3) 0(4,4)

```

The coordinates shown above, next to matrix elements is for explanation only. They are nothing but array indices. Actual input would just be the matrix. for example1 the input is just,

```
0 1 0
0 0 0
1 0 0

```

Input for example2,

```
0 0 1 0 0
0 1 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0

```

Starting Point (0,0).

## Output

Output should be a line containing comma separated *moves*. A *move* is a space separated direction (n,s,e,w) and number of units of movement in the direction (range 1-1000).

Example output for the matrix in example1 would be,

```
s 1,e 1,s 1,e 1,n 2

(0,0) --> (1,0) --> (1,1) --> (2,1) --> (2,2) --> (1,2) --> (0,2)

```

and for the matrix in example2 would be,

```
s 2,e 2,n 1,e 1,n 1,e 1,s 4,w 1,n 1,w 1

(0,0) --> (1,0) --> (2,0) --> (2,1) --> (2,2) --> (1,2) --> (1,3) --> (0,3) --> (0,4) --> (1,4) --> (2,4) --> (3,4) --> (4,4) --> (4,3) --> (3,3) --> (3,2)

```

which is the longest path, visiting each coordinate only once and avoiding those coordinates with obstacles.

## Objective Winning Criteria

Should compute the distance efficiently(efficient: performance wise, fast program basically) for huge matrices (Of order say, 500x500). One which computes the fastest wins (All submissions run on my machine, for fairness). No restrictions on number of bytes!

Here is a 20x20 matrix which can be used to get some idea of the performace, for tuning purposes.

```
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0

```

# Answer
> 8 votes
## Python 3, `2619 bytes` (90 LOC), ~6 seconds (20x20)

```
#!/usr/bin/env python

import networkx as nx

class input(object):
    def __init__(self,world_string):
        rows=world_string.split("\n")
        column_count=len(rows[0])
        blocked_cells=[]
        x=0
        y=-1
        for row in rows:
            if len(row)>column_count:
                column_count=len(row)
            y+=1
            for column in row:
                if column=='1':
                    blocked_cells.append((y,x))
                x+=1
            x=0
        self.matrix=world(len(rows),column_count)
        self.block_graph(blocked_cells)
        self.matrix.add_sink()

    def block_graph(self,block_list):
        for cell in block_list:
            self.matrix.block_cell(cell)

class world(object):
    SINK="END"

    def __init__(self, rows=3, columns=3):
        self.graph=nx.grid_2d_graph(rows, columns)
        for e in self.graph.edges():
            self.graph[e[0]][e[1]]["weight"]=-1.0

    def block_cell(self,node):
        neighbours=list(self.graph[node].keys())
        for linked_node in neighbours:
            self.graph.remove_edge(node,linked_node)

    def add_sink(self):
        matrix=self.graph.nodes()[:]
        self.graph.add_node(world.SINK)
        for source_cell in matrix:
            self.graph.add_edge(source_cell, world.SINK, weight=1.0)

class algorithm(object):
    SOURCE=(0,0)
    def find_path(graph):
        def _heuristic(current, target):
            if current==target:return 0.0
            cost=nx.astar_path(graph, algorithm.SOURCE,current,lambda x,y:1)
            return -1 * len(cost)
        path=nx.astar_path(graph, algorithm.SOURCE, world.SINK, _heuristic)
        return path[:-1]

class output(object):
    directions={
        ( 1,  0)  : "n",
        (-1,  0)  : "s",
        ( 0,  1)  : "w",
        ( 0, -1)  : "e"
    }

    def edge_to_direction(source_node, dest_node):
        row_delta=source_node[0]-dest_node[0]
        column_delta=source_node[1]-dest_node[1]
        return output.directions[(row_delta, column_delta)]

    def path_to_directions(path):
        result=""
        for step in range(len(path)-1):
            result+=output.edge_to_direction(path[step],path[step+1])
        return result

    def simplify_directions(directions):
        directions+="\0"
        count=0
        result=""
        last=""
        for d in directions:
            if d!=last or d is "\0":
                result+="{} {},".format(last, count)
                count=0
                last=""
            if count==0:
                last=d
                count=1
                continue
            if d==last:
                count+=1
        return result[3:-1]

if __name__=='__main__':
    contents="010\n000\n100"    #read from file?

    data=input(contents).matrix.graph
    result_path=algorithm.find_path(data)
    directions=output.path_to_directions(result_path)
    directions=output.simplify_directions(directions)
    print(directions+"\n")
    print(str(result_path)[1:-1].replace('), (',') --> (').replace(', ',','))

```

## Performance

I ran this solution (on my old Core i3 laptop) on the 20x20 '*performance*' example input and it ran in around ~6 seconds (of course, YMMV). I am **SURE** there are ways to do this faster, probably by orders of magnitude. However, I didn't feel like re-writing my own A\* algorithm in assembly and renting some time slices on a super computer!

## About this Code

## The Idea

The idea for this approach comes from my answer over here in Code Review. You can also read a little bit more about it and the end of my answer here.

## Dependencies

As you may have notice by the (rather prominent) line `import networkx as nx` \- this code relies upon the Python NetworkX module to function. So do \>`pip install networkx` if you get import errors when running.

## Breakdown of Solution Elements by Lines of Code

I also thought it would be interesting (and it was), after Don Muesli's comment (particularly the part "*a significant part of the efffort\[sic\] is formatting the output*"), to **examine** how much of the code is for various things.

**Breakdown**:

* 39 lines (or 43.33%) of the lines of code in the program are concerned with parsing the input and constructing/weighting the graph data structure.
* 37 lines (approx. 41%) directly relate *solely* to displaying and formatting the desired **output**!
* 5 lines (5.5%) are 'other' stuff, which relates to *running the program* (shebang line, imports, the `if __name__=="__main__"`..., etc).
* And 9 (yes.. nine) lines of code (or *just* 10%) **actually relates to the algorithm usage**.

**Obligatory Pie Chart**:

##

---

## About the Approach

As I mentioned above, most of the idea for this approach comes from my answer over on Code Review regarding this problem.

The process itself is relatively straightforward:

1. Transform the given matrix into an undirected graph data structure
2. Annotate (*i.e.* add weights) the edges of that graph
3. Add a "sink" node - to be used as a *search target*
4. Add (weighted) edges between all nodes and the sink node
5. Use a Graph Search Algorithm (in this case A\*)

So, taking the 3x3 matrix from the question for example. The transformation into a graph would yield something like the following:

(**Note:** the 'blocked' nodes do not have any edges)

Step 2; *imagine* each green line in the above picture has a *weight* of `-1`.

Next, for step 3 and 4 together (I didn't want to have to make another picture), take a look at the following graph:

And again *imagine* the edges are weighted, only red lines are *weighted* `+1`.

We can then apply the A-star algorithm from the NetworkX library to this graph, using the custom *heuristic* function. This makes the search algorithm score paths in an inverse manner (longest path rather than shortest). And the **longest** path will be the one that visits the *most* cells of the problem matrix!

# Answer
> 1 votes
# Clingo, 202 seconds for 20×20

This problem is NP-complete, even if you were to guarantee that all `0`s are used, so your dreams of a program that runs efficiently for 500×500 may be a little bit unrealistic.

(The other answer using A\* search doesn’t find the optimal solution, even on the 3×3 example case, because A\* never revisits a node that was previously found on a different path.)

```
#script (python)

import clingo
import itertools
import sys

def main(prg):
    matrix = [list(line.split()) for line in sys.stdin]

    def data():
        for i, row in enumerate(matrix):
            for j, cell in enumerate(row):
                if cell == '0':
                    yield f'cell(({i}, {j})).\n'

    def on_model(model):
        step = {}
        for atom in prg.symbolic_atoms:
            if atom.symbol.name == 'step' and model.contains(atom.symbol):
                a, d, b = atom.symbol.arguments
                step[a] = d, b
        moves = []
        a = clingo.Tuple((0, 0))
        while step[a][1] != clingo.Tuple((0, 0)):
            d, a = step[a]
            moves.append(d)
        print(len(moves) + 1)
        print(','.join(f'{d} {len(list(g))}' for d, g in itertools.groupby(moves)))

    prg.add('data', [], ''.join(data()))
    prg.ground([('base', []), ('data', [])])
    prg.solve(on_model=on_model)

#end.

#program base.

dir(s, (1, 0); e, (0, 1); n, (-1, 0); w, (0, -1)).
adj((X, Y), D, (X+DX, Y+DY)) :- cell((X, Y)), dir(D, (DX, DY)), cell((X+DX, Y+DY)).
adj(A, end, (0, 0)) :- cell(A).
{step(A, D, B) : adj(A, D, B)} = 1 :- visit(A).
:- visit(B), {step(A, D, B) : adj(A, D, B)} != 1.
visit((0, 0)).
visit(B) :- step(A, D, B).
:~ visit(A). [-1, A]

#show step/3.

```

### Demo

```
$ clingo -q longest.lp < 20x20.in
clingo version 5.2.2
Reading from longest.lp
Solving...
1

2
s 1
3
s 2
4
s 3
5
e 3,s 1
6
e 3,s 2
7
e 3,s 3
9
e 3,s 5
…
264
s 4,e 1,n 4,e 2,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,w 1,n 1,w 1,s 3,e 1,n 1,e 1,s 12,e 1,n 13,e 2,s 1,e 2,n 7,e 1,s 2,e 2,n 1,w 1,n 1,e 4,s 5,w 1,s 1,e 1,s 1,w 2,s 1,e 2,s 1,w 1,s 1,e 1,s 1,w 2,s 1,w 1,s 2,w 1,n 3,e 1,n 1,e 1,n 1,w 1,n 3,e 1,n 1,w 1,n 1,e 2,n 3,w 1,s 2,w 3,s 1,e 1,s 1,w 1,s 1,e 1,s 4,w 1,n 2,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 3,s 1,e 1,n 3,e 1,n 1,e 1,s 2,w 1,s 1,e 1,s 1,w 1,s 2,w 1,n 1,w 2,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 2,n 1,e 1,s 1,e 3,n 2,e 2,n 1,e 2,s 3,e 1,n 1,e 1,n 6,w 1,n 1,e 1,n 9,w 1,n 1,e 1,n 1,w 2,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 2
265
s 4,e 1,n 4,e 2,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,w 1,n 1,w 1,s 3,e 1,n 1,e 1,s 12,e 1,n 13,e 2,s 1,e 2,n 7,e 1,s 2,e 2,n 1,w 1,n 1,e 4,s 5,w 1,s 1,e 1,s 1,w 2,s 1,e 2,s 1,w 1,s 1,e 1,s 1,w 2,s 1,w 1,s 2,w 1,n 3,e 1,n 1,e 1,n 1,w 1,n 3,e 1,n 1,w 1,n 1,e 2,n 3,w 1,s 2,w 3,s 1,e 1,s 1,w 1,s 1,e 1,s 4,w 1,n 2,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 3,s 1,e 1,n 3,e 1,n 1,e 1,s 2,w 1,s 1,e 1,s 1,w 1,s 2,w 1,n 1,w 2,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 2,n 1,e 1,s 1,e 3,n 2,e 2,n 1,e 2,s 1,e 1,s 1,w 1,s 1,e 2,n 3,w 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 2,s 15
OPTIMUM FOUND

Models       : 99
  Optimum    : yes
Optimization : -265
Calls        : 1
Time         : 201.664s (Solving: 201.56s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 201.602s

```

The final output line (above `OPTIMUM FOUND`) corresponds to the following path through 265 nodes:

```
• ┌───┐ 1 0 1 ┌─┐ ┌───────┐ 1 0 1 ┌───┐
│ │ ┌─┘ 1 0 1 │ │ └─┐ ┌─┐ │ 1 0 1 └─┐ │
│ │ └─┐ 1 0 1 │ └───┘ │ │ │ 1 0 1 ┌─┘ │
│ │ ┌─┘ 1 0 1 │ ┌─────┘ │ │ 1 0 1 └─┐ │
└─┘ └─┐ 1 0 1 │ └─┐ ┌───┘ │ 1 0 1 ┌─┘ │
┌─┐ ┌─┘ 1 0 1 │ ┌─┘ └─┐ ┌─┘ 1 0 1 └─┐ │
│ └─┘ ┌───┐ 1 │ └─┐ ┌─┘ └─┐ 1 0 1 ┌─┘ │
│ ┌─┐ │ 1 └───┘ 1 │ │ ┌───┘ 1 0 1 └─┐ │
└─┘ │ │ 1 0 1 ┌─┐ │ │ └───┐ 1 0 1 ┌─┘ │
0 1 │ │ 1 1 1 │ │ │ └─┐ ┌─┘ 1 0 1 └─┐ │
0 1 │ │ 1 1 1 │ └─┘ ┌─┘ └─┐ 1 0 1 ┌─┘ │
0 1 │ │ 1 1 1 └─┐ ┌─┘ ┌───┘ 1 0 1 └─┐ │
0 1 │ │ 1 1 1 ┌─┘ │ ┌─┘ ┌─┐ 1 0 1 ┌─┘ │
0 1 │ │ 1 1 1 └─┐ │ │ ┌─┘ │ 1 0 1 └─┐ │
0 1 │ │ 1 1 1 ┌─┘ └─┘ │ ┌─┘ 1 0 1 ┌─┘ │
0 1 │ │ 1 1 1 └─────┐ │ └─┐ 1 0 1 └─┐ •
0 1 │ │ 1 1 1 ┌───┐ └─┘ ┌─┘ 1 ┌───┐ └─┐
0 1 │ │ 1 1 1 └─┐ └───┐ │ ┌───┘ 1 └─┐ │
0 1 │ │ 1 1 1 ┌─┘ ┌─┐ └─┘ │ 1 0 1 ┌─┘ │
0 1 └─┘ 1 1 1 └───┘ └─────┘ 1 0 1 └───┘

```

---
Tags: fastest-code, path-finding
---