# Question
Title: Find all integer pairs that produce a given Loeschian number
Inspired by and drawns from Is this number Loeschian?

> A positive integer \\$k\\$ is a **Loeschian number** if
>
> * \\$k\\$ can be expressed as \\$i^2 + j^2 + i\times j\\$ for \\$i\\$, \\$j\\$ integers.
>
> For example, the first positive Loeschian numbers are: \\$1\\$ (\\$i=1, j=0\\$); \\$3\\$ (\\$i=j=1\\$); \\$4\\$ (\\$i=2, j=0\\$); \\$7\\$ (\\$i=2, j=1\\$); \\$9\\$ (\\$i=-3, j=3\\$)1; ... Note that \\$i, j\\$ for a given \\$k\\$ are not unique. For example, \\$9\\$ can also be generated with \\$i=3, j=0\\$.
>
> Other equivalent characterizations of these numbers are:
>
> * \\$k\\$ can be expressed as \\$i^2 + j^2 + i\times j\\$ for \\$i, j\\$ non-negative integers. (For each pair of integers \\$i, j\\$ there's a pair of non-negative integers that gives the same \\$k\\$)
> * There is a set of \\$k\\$ contiguous hexagons that forms a tesselation on a hexagonal grid (see illustrations for \\$k = 4\\$ and for \\$k = 7\\$). (Because of this property, these numbers find application in mobile cellular communication networks.)
> * See more characterizations in the OEIS page of the sequence.

The first few Loeschian numbers are

```
0, 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25, 27, 28, 31, 36, 37, 39, 43, 48, 49, 52, 57, 61, 63, 64, 67, 73, 75, 76, 79, 81, 84, 91, 93, 97, 100, 103, 108, 109, 111, 112, 117, 121, 124, 127, 129, 133, 139, 144, 147, 148, 151, 156, 157, 163, 169, 171, 172, 175, 181, 183, 189, 192...

```

1while (\\$i=-3, j=3\\$) produces 9, stick to non-negative integers, so (\\$i=0, j=3\\$).

Loeschian numbers also appear in determining if a coincident point in a pair of rotated hexagonal lattices is closest to the origin?

## The challenge

Given a **non-negative integer** \\$k\\$, output all pairs of non-negative integers \\$i, j\\$ such that \\$i^2 + j^2 + i\times j=k\\$. If none are found (i.e. \\$k\\$ is not Loeschian) then return nothing or some suitable flag *other than* \\$(0, 0)\\$ since that produces the first Loeschian number, \\$0\\$.

For reversed order pairs like \\$(0, 4)\\$ and \\$(4, 0)\\$ either include both, or one member of the pair, but it should be the same for all cases (i.e. not sometimes one and other times both).

The program or function should handle (say in less than a minute) inputs up to \\$100,000\\$, or up to data type limitations.

This is code golf so shortest code wins.

## Test cases

```
 in       out
 0      (0, 0)
 1      (0, 1), (1, 0)
 3      (1, 1)
 4      (0, 2), (2, 0)
 9      (0, 3), (3, 0)
 12     (2, 2)
 16     (0, 4), (4, 0)
 27     (3, 3)
 49     (0, 7), (3, 5), (5, 3), (7, 0)
 147    (2, 11), (7, 7), (11, 2)
 169    (0, 13), (7, 8), (8, 7), (13, 0)
 196    (0, 14), (6, 10), (10, 6), (14, 0)
 361    (0, 19), (5, 16), (16, 5), (19, 0)
 507    (1, 22), (13, 13), (22, 1)
 2028   (2, 44), (26, 26), (44, 2)
 8281   (0, 91), (11, 85), (19, 80), (39, 65), (49, 56), (56, 49), (65, 39), (80, 19), (85, 11), (91, 0)
 12103  (2, 109), (21, 98), (27, 94), (34, 89), (49, 77), (61, 66), (66, 61), (77, 49), (89, 34), (94, 27), (98, 21), (109, 2)

```

# Answer
> 7 votes
# 05AB1E, 11 9 bytes

*Thanks to @ovs for -2!*

```
ÝãʒãÀ¦POQ

```

Oh my, I am getting in the hang of code golfing!

Prints a list of all the valid pairs (e.g `[[1, 0], [0, 1]]`). If there are none, the list is empty (`[]`). Also outputs both of any reverse integer pairs.

Try it online!

## How?

You may count this as a port of the other answers, but I took a look only at the Husk answer before writing the program!

```
Ý             # Push a list of all numbers from 0 to the input.
 ã            # Push the cartesian power of lists. (Basically, finding all possible pairs)
  ʒ           # For each pair...
   ãÀ¦        # Find all other permutations of the pair.
      P       # Multiply each permutation.
       O      # Add the products.
        Q     # If the result is not equal to the input, yeet (throw) them from the list.
              # Automatically print the pairs not yeeted.

```

# Answer
> 5 votes
# Jelly, ~~11~~ ~~10~~ 9 bytes

```
Żp`ḋÄ$=¥Ƈ

```

Try it online!

Outputs `[]` for non-Loeschian numbers

-1 byte thanks to Sisyphus

Not particularly efficient, but that can be fixed for an additional 2 bytes.

Uses the fact that a Loeschian number can be expressed as \\$i\times i + j\times(i+j)\\$ by using Jelly’s vectorisation and cumulative sum.

## How it works

```
Żp`ḋÄ$=¥Ƈ - Main link. Takes n on the left
Ż         - Yield [0, 1, ..., n]
 p`       - Cartesian product with itself, yielding [[0, 0], [0, 1], ..., [n, n]]
       ¥Ƈ - Filter the pairs, keeping those where the following is true:
     $=   -   The pair equals n after the following is done:
    Ä     -     Cumulative sum. Yield [i, i+j]
   ḋ      -     Dot product with [i, j]; Yields i×i + j×(i+j)

```

# Answer
> 5 votes
# Husk, ~~15~~ 13 bytes

```
fo=¹§+Πṁ□π2…0

```

Try it online!

-2 bytes from Zgarb.

Outputs `[]` for non-Loeschians.

## Explanation

```
fo=¹§+Πṁ□π2…0
           …0 range from 0..n
         π2   create all possible pairs using 0..n
fo            filter by the following two functions:
    §         f: fork: § f g h x = f (g x) (h x)
     +           add
       ṁ□        sum of squares
      Π          and fold by multiplication
  =¹          g: is that equal to 1?

```

# Answer
> 5 votes
# Haskell, 46 bytes

```
f x|l<-[0..x]=[(i,j)|i<-l,j<-l,i*i+j*j+i*j==x]

```

Try it online!

# Answer
> 4 votes
# Japt, 13 bytes

```
ô ï f@¶Xx²+X×

```

Try it

```
ô ï f@¶Xx²+X×     :Implicit input of integer U
ô                 :Range [0,U]
  ï               :Cartesian product
    f             :Filter by
     @            :Passing each X through the following function
      ¶           :  Is U equal to
       Xx         :  X reduced by addition
         ²        :  After squaring each
          +X×     :  Plus X reduced by multiplication

```

# Answer
> 4 votes
# Wolfram Language (Mathematica), 46 bytes

```
Solve[i^2+j^2+i*j==#&&i>=j>=0,{i,j},Integers]&

```

Try it online!

# Answer
> 4 votes
# Scala, ~~64~~ 62 bytes

```
k=>0.to(k)flatMap(i=>0.to(k)filter(j=>i*i+j*j+i*j==k)map(i->))

```

Try it online!

Thanks to user for -2

# Answer
> 3 votes
# Perl 5, ~~81~~ ~~77~~ 74 bytes

```
sub{map{$i=$_;grep{$k==$i**2+$i*$_+$_**2&&($_=[$i,$_])}$i..$k}0..($k=pop)}

```

Try it online!

A bit ungolfed:

```
sub f {
  my $k=pop;                      #gangnam style, k=pop from input
  grep { $k==pop@$_ }             #pop last of three elems
                                  #...in the candidate array
                                  #...and return as result
                                  #...if last = i*i+i*j+j*j = k
  map  {                          #two loops from 0 to sqrt $k
    my $i=$_;                     #outer loop var
    map {
      my $j=$_;                   #inner loop var
      [$i, $j, $i*$i+$i*$j+$j*$j] #result candidate
    }
    0..sqrt$k                     #or  $i..sqrt$k  to return only i<=j
  }
  0..sqrt$k
}

```

Note: Saving bytes by removing the two sqrt makes it run A LOT slower, but it will still return the correct result.

# Answer
> 3 votes
# Scala, 53 bytes

```
| =>for(i<-0 to|;j<-0 to|if| ==i*i+j*j+i*j)yield(i,j)

```

Try it online!

# Answer
> 3 votes
# C (gcc), 75 bytes

```
i,j;f(x){for(i=j=x;~j;i-=!i?j--,-x:1)i*i+j*j+i*j-x||printf("(%d,%d)",i,j);}

```

Try it online!

# Answer
> 3 votes
## Python 3 - ~~79~~ 70 Bytes

Just the trivial solution to get started with Python 3

~~```
k=9  # not counted

```

```
def f(k):
    a=range(k);return [(i,j) for i in a for j in a if k==i*i+j*j+i*j]

```

```
print(f(k))   # not counted

```
Try it online!
~~

---

**Thanks to @Jakque**

lambda, testing framework in TIO, spaces, `k+1`, factorization

```
lambda k:[(i,j)for i in range(k+1)for j in range(k+1)if(i+j)*i+j*j==k]

```

Try it online!

# Answer
> 2 votes
# JavaScript (V8), 57 bytes

Prints the pairs \\$(x,y),\\:x\le y\\$.

```
n=>{for(y=n+1;x=y--;)for(;x--;)x*x+y*y+x*y-n||print(x,y)}

```

Try it online!

# Answer
> 2 votes
# Charcoal, 25 bytes

```
ＮθＦ⊕₂θＦ⊕ι¿⁼θ⁻Ｘ⁺ικ²×ικＩ⟦ικ

```

Try it online! Link is to verbose version of code. Only outputs those pairs where `i>=j`.  speeds the code up so that the larger test cases complete within a minute, but it is not needed for smaller test cases. Explanation:

```
Ｎθ

```

Input `k`.

```
Ｆ⊕₂θ

```

Loop `i` from `0` to `√k` inclusive.

```
Ｆ⊕ι

```

Loop `j` from `0` to `i` inclusive.

```
¿⁼θ⁻Ｘ⁺ικ²×ικ

```

If `k=(i+j)²-ij`, then...

```
Ｉ⟦ικ

```

Output `i` and `j` on separate lines.

Just for fun, here's a 73-byte Retina 1.0 answer that only finds nontrivial solutions (i.e. neither `i` nor `j` is zero):

```
.+
*
L$w`^((_)+)(?=(?<-2>\1)+(?(2)$.)(_(_)*)(?<-4>\1\3)*$(?(4).))
$.1 $.3

```

Try it online! Very slow, so don't try anything over about 500.

# Answer
> 2 votes
# Wolfram Language (Mathematica), 42 bytes

```
Array[(+##)^2-##&,{#,#}+1,0]~Position~#-1&

```

Try it online!

Gets slow on larger inputs.

```
Array[          (* Create a table of *)
(+##)^2-##&,    (* (i+j)^2-i j *)
{#,#}+1,0]      (* for i,j = 0...k *)
~Position~#-1   (* and find where that expression equals k *)

```

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


# Question
Title: Interquine - Two programs that output each other in a loop
Program A outputs program B's code when run, and B outputs A's source.

Requirements:

* Only one language across both programs
* Programs are different. One program that outputs itself does not qualify.
* Both programs are non-empty, or at least 1 byte in length. Trailing newlines in both source and output are ignored
* ~~stdin is closed.~~ Do not read anything (so **you can't read the source** and manipulate it). Output goes to stdout.
**Edit:** stdin is connected to `/dev/null`. You can order it be closed if clarified.
* Do not use `random` functions.

Additional:

* Give explanations if possible

Score is **total length**. Trailing newline does not count if it doesn't affect the program.

# Answer
> 19 votes
## CJam, 13 + 13 = 26 bytes

```
{sYZe\"_~"}_~

```

Try it online!

Outputs

```
{sZYe\"_~"}_~

```

### Explanation

```
{       e# Standard quine framework, leaves a copy of the block on the stack
        e# for the block itself to process.
  s     e# Stringify the block.
  YZe\  e# Swap the characters at indices 2 and 3, which are Y and Z themselves.
  "_~"  e# Push the "_~" to complete the quine.
}_~

```

Since `e\` is commutative in its second and third operand, the other program does exactly the same, swapping `Z` and `Y` back into their original order.

# Answer
> 17 votes
# CJam, ~~11 + 13 = 24~~ 11 + 12 = 23 bytes

```
"N^_p"
N^_p

```

Try it online!

Outputs:

```
"N^_p
"
N^_p

```

The output has 13 bytes, but:

> Trailing newline does not count if it doesn't affect the program.

So I changed the space to a newline to take advantage of that.

It is based on the shortest CJam proper quine:

```
"_p"
_p

```

And `N^` is to xor the string with a newline, which adds a newline if there isn't a newline, and remove it if there is, for a string that each character is unique.

I think I have seen that quine in the quine question, but I couldn't find it.

# Answer
> 12 votes
# RProgN 2, 3 + 3 = 6 bytes

First program:

```
0
1

```

Try it online!

Second program:

```
1
0

```

Try it online!

-2 thanks to Martin Ender.

# Answer
> 6 votes
# C, 95 + 95 = 190 bytes

*Thanks to @immibis for saving 16\*2 bytes!*

```
char*s="char*s=%c%s%c;main(i){i=%d^1;printf(s,34,s,34,i);}";main(i){i=1^1;printf(s,34,s,34,i);}

```

Try it online!

Outputs:

```
char*s="char*s=%c%s%c;main(i){i=%d^1;printf(s,34,s,34,i);}";main(i){i=0^1;printf(s,34,s,34,i);}

```

Try it online!

Which outputs:

```
char*s="char*s=%c%s%c;main(i){i=%d^1;printf(s,34,s,34,i);}";main(i){i=1^1;printf(s,34,s,34,i);}

```

# Answer
> 6 votes
# Javascript, 67+67=134 bytes

1st program:

```
alert(eval(c="`alert(eval(c=${JSON.stringify(c)},n=${+!n}))`",n=0))

```

2nd program:

```
alert(eval(c="`alert(eval(c=${JSON.stringify(c)},n=${+!n}))`",n=1))

```

This is based on Herman Lauenstein's answer to Tri-interquine

# Javascript (Invalid - reads source code), ~~75+75=150~~ ~~61+61=122~~ ~~58+58=116~~ 50+50=100 bytes

*saved 20 bytes thanks to Tushar, 6 bytes thanks to Craig Ayre, and saved 16 bytes thanks to kamoroso94*

1st program:

```
f=_=>alert(("f="+f).replace(0,a=>+!+a)+";f()");f()

```

2nd program:

```
f=_=>alert(("f="+f).replace(1,a=>+!+a)+";f()");f()

```

Swaps the 1s with the 0s and vice versa. They both do the same thing, just producing different output because of their source code.

# Answer
> 5 votes
## Python 2, 63+63 = 126 bytes

Try it online

First program:

```
A='A=%r;print A[:23]%%A+A[29:35]23:29]';print A[:23]%A+A[23:29]

```

outputs:

```
A='A=%r;print A[:23]%%A+A[29:35]23:29]';print A[:23]%A+A[29:35]

```

Second program:

```
A='A=%r;print A[:23]%%A+A[29:35]23:29]';print A[:23]%A+A[29:35]

```

Outputs:

```
A='A=%r;print A[:23]%%A+A[29:35]23:29]';print A[:23]%A+A[23:29]

```

# Answer
> 4 votes
# JavaScript (JsShell), 35 + 34 = 69 bytes

1:

```
(f=x=>print(`(f=${f})(${-x})`))(-1)

```

2:

```
(f=x=>print(`(f=${f})(${-x})`))(1)

```

# Answer
> 3 votes
# Underload, 32+32=64 bytes

```
(a~a*(:^)*S)(~(a)~a*^a(:^)**S):^

```

Try it online!

```
(~(a)~a*^a(:^)**S)(a~a*(:^)*S):^

```

Try it online!

# Answer
> 3 votes
# Mathematica, 43 + 44 = 87 bytes

```
(Print[#1[#0[#1, -#2]]] & )[HoldForm, -1 1]

```

and

```
(Print[#1[#0[#1, -#2]]] & )[HoldForm, -(-1)]

```

# Answer
> 3 votes
# asmutils sh, 16+16 bytes, abusing the "stdin is closed" rule.

```
#!/bin/sh
tr x y

```

Since stdin is closed and sh will open its script to the first available handle (rather than move it to a high numbered handle like modern shells do), tr ends up reading from a copy of the script without having ever opened it.

This interquine is payload capable but inserting a payload is tricky.

In addition, this original version abuses some crazy bug in the ancient kernel I used in those days. (I don't know what's up with that kernel--I found out later on it had different major and minor numbers for devices too.) If you fix the ABI changes that broke asmutils the interquine still won't work. I forget if asmutils sh has exec or not, but if it does, this is a modern version:

```
exec dd skip=0 | tr x y

```

This abuses a deliberate bug in asmutils dd; it has a performance optimization it calls llseek for skip if it can, but to save a byte it passes SEEK\_SET rather than SEEK\_CUR. This results in garbage on stderr but the interquine on stdout. Asmutils dd doesn't have an option to suppress the stderr spam.

# Answer
> 2 votes
# \>\<\>, 16 + 16 = 32 bytes

```
":1-}80.r   !#o#

```

and

```
#o#!   r.08}-1:"

```

Try it online!

This works by using a jump in the program, the first programs jump will skip the reverse of the stack (if it reversed the stack it would be a quine). The second program doesn't skip the reverse but was it's already reversed by the flow of the program then it'll create the originial.

This code will end in an error.

# Answer
> 1 votes
## LOGO, 65 + 66 = 131 bytes

```
apply [(pr ? ` [[,? ,-?2]] )] [[apply [(pr ? ` [[,? ,-?2]] )]] 1]

```

and

```
apply [(pr ? ` [[,? ,-?2]] )] [[apply [(pr ? ` [[,? ,-?2]] )]] -1]

```

# Answer
> 1 votes
## Common Lisp, 58 characters

```
#1=(let((*print-circle* t))(print'(write '#1# :circle t)))

```

... or 24 characters if you don't mind assuming `*print-circle*` is globally set to `T` :

```
#1=(print '(write '#1#))

```

The printed representation of the code is read as a cyclic structure, where `#1#` points back to the cons cell following `#1=`. We quote programs so that they are not executed. Since `*print-circle*` is T, the REPL takes care to emit such reader variables during printing; this is what the above code prints, and returns:

```
#1=(write '(print '#1#))

```

When we evaluate the above code, it prints:

```
#1=(print '(write '#1#))

```

If you want to stick with the default value for `*print-circle*`, which is NIL in a conforming implementation, then you'll have to rebind the variable temporarily:

```
#1=(let((*print-circle* t))(print'(write '#1# :circle t)))

```

Inside the body of the LET, we print things with `*print-circle*` being T. So we obtain:

```
#1=(write
    '(let ((*print-circle* t))
       (print '#1#))
    :circle t)

```

As you can see, the new program doesn't rebind `*print-circle*`, but since we are using `write`, which is the low-level function called by `print`, we can pass additional arguments such as `:circle`. The code then works as expected:

```
#1=(let ((*print-circle* t))
     (print '(write '#1# :circle t)))

```

However, you need to execute the above programs as a script, not inside a REPL, because even though you print things while taking care of circular structures, both `write` and `print` also returns the value being printed; and in a default REPL, the value is also being printed, but outside of the dynamic context where `*print-circle*` is T.

# Answer
> 1 votes
# RProgN 2, 7 + 7 = 14 bytes

I wanted to try to show off a better usage of RProgN, rather than just abusing print orders...

```
1
«\1\-

```

and...

```
0
«\1\-

```

## Explained

```
1   # Push the constant, 1. (Or 0, depending on the program)

«\1\-
«       # Define a function from this to the matching », in this case there isn't any, so define it from this to the end of the program, then continue processing.
 \      # Flip the defined function under the constant.
  1\-   # Get 1 - Constant.

```

Because this prints the stack upside down, the new constant is printed first, then the stringifed version of the function is printed.

Try it online!

# Answer
> 1 votes
# Python 3, 74+74=148 bytes

```
a='a=%r;b=%r;print(b%%(b,a))';b='b=%r;a=%r;print(a%%(a,b))';print(b%(b,a))

```

and

```
b='b=%r;a=%r;print(a%%(a,b))';a='a=%r;b=%r;print(b%%(b,a))';print(a%(a,b))

```

~~i don't understand it either~~

# Answer
> 1 votes
# \>\<\>, 12 + 12 = 24 bytes

```
'3d*!|o|!-c:

```

and

```
':c-!|o|!*d3

```

Try it online!

Both programs use a wrapping string literal to add the code to the stack, then produce the `'` command through different methods. When printing the stack it pushes the code backwards, however the `'` stays at the front. There are several variations that produce the `'`; `3d*`, `d3*`, `00g`, `:c-` when paired with `3d*` and `:9-` when paired with `00g`.

A too similar solution to post, in Befunge-98 for 13\*2 bytes

```
"2+ck, @,kc+2

```

# Answer
> 1 votes
# Stax, 18+20=38 bytes

```
"Vn|^34bL"Vn|^34bL

```

Run and debug online!

```
"Vn|^34bL
"Vn|^34bL

```

Run and debug online!

## Explanation

Added for completeness. Port of @jimmy23013's CJam answer. Toggles the newlines using set xor.

# Answer
> 0 votes
# Javascript (ES6), 36 + 36 = 72 bytes

Program 1:

```
f=n=>('f='+f).replace(/4|5/g,n=>n^1)

```

Program 2:

```
f=n=>('f='+f).replace(/5|4/g,n=>n^1)

```

These programs work by cloning themselves and replace `5` with `4` and `4` with `5`

```
console.log((
    f=n=>('f='+f).replace(/4|5/g,n=>n^1)
)())
console.log((
    f=n=>('f='+f).replace(/5|4/g,n=>n^1)
)())
```

# Answer
> 0 votes
# Klein, ~~26~~ 24 bytes

```
<:3+@+3<:"

```

Try it online!

## Explanation

This works the same as my Klein Quine, where it prints the source backwards followed by a `"`, the last one got away with this by being palindromic, so all we need to do is make it non-palindromic without damaging its functionality. By switching `<` and `:` we were able to do this without interfering with functionality.

# Answer
> 0 votes
# Pari/GP, 36 + 36 = 72 bytes

```
(f=(x)->print1("(f="f")("1-x")"))(1)

```

Try it online!

```
(f=(x)->print1("(f="f")("1-x")"))(0)

```

Try it online!

# Answer
> 0 votes
# Python 2, 42 + 43 = 85 bytes,

# Python 3, 44 + 45 = 89 bytes

## Python 2 (85 bytes):

```
a='a=%r,-%d;print a[0]%%a',-1;print a[0]%a    # Program 1: 42 bytes
a='a=%r,-%d;print a[0]%%a',--1;print a[0]%a   # Program 2: 43 bytes

```

Try it online!

## Python 3 (89 bytes):

```
a='a=%r,-%d;print(a[0]%%a)',-1;print(a[0]%a)    # Program 1: 44 bytes
a='a=%r,-%d;print(a[0]%%a)',--1;print(a[0]%a)   # Program 2: 45 bytes

```

Try it online!

## How it works? :

I started from the standard `a='a=%r;print(a%%a)';print(a%a)` quine. But instead of having `a` equal only to a string, I have `a` equal to a tuple regrouping a sting and an integer. I add the char `-` in front of my integer:

* if it is equal to `-1`, `-%d` will be equal to `--1`
* if it is equal to `--1`, `%d` will evaluate it as 1 so `-%d` will be equal to `-1`

## Edits:

I found aferwards this pretty elegant solution. Not better, just elegant. (58 + 58 = 116 bytes):

```
a="print'a=%r;exec a.lower()'%a.swapcase()";exec a.lower() # 58 char each
a="PRINT'A=%R;EXEC A.LOWER()'%A.SWAPCASE()";exec a.lower() # 116 bytes in total

```

Try it online!

---
Tags: code-golf, quine
---


# Question
Title: Bring my memories about Geronimo Stilton back
If you have read in your childhood a Geronimo Stilton's book, I am sure that you remember the style of the text, sometimes the words were decorated for making the act of reading more funny for kids: example.

But when you are an adult you don't have that little entertainment in your readings... why? In a nostalgic attack I have decided to make an algorithm to create that output with every text in the world.

It's not very similar, but it's curious.

## Idea:

Make a program that with an input like this:

```
It was in the morning of June 21, and I had just set
paw in the office. Right away I could tell it wasn't
going to be a good day. My staff was running
around like a pack of rats in a maze. And everyone
was complaining about something.
"Geronimo, the air-conditioner's broken!"
yelled my secretary, Mousella MacMouser.
"Geronimo, we are run out of coffee!" shrieked
Blasco Tabasco, one of my designers.
"Geronimo, the computers are all down!"
cried my proofreader. Mickey Misprint.

```

Create an output like this:

or this:

(These outputs are images because there are two ways to create the output, show it in your program some way or create an output HTML like mine.) This is my raw output:

```
<font face="Verdana">It was in the morning of June 21, and I had just set </br>
paw in the <b><font face="Comic Sans MS" size="5" style="color:rgb(111,229,136);">office</font></b>. Right away I could tell it wasn't </br>
going to be a good day. My staff was <b><font face="Comic Sans MS" size="5" style="color:rgb(77,170,241);">running</font></b> </br>
around like a pack of rats in a maze. And everyone </br>
was complaining about something. </br>
"Geronimo, the air-conditioner's broken!" </br>
<b><font face="Comic Sans MS" size="5" style="color:rgb(174,152,239);">yelled</font></b> my secretary, Mousella MacMouser. </br>
"Geronimo, we are run out of coffee!" shrieked </br>
Blasco Tabasco, one of my <b><font face="Comic Sans MS" size="5" style="color:rgb(101,139,153);">designers</font></b>. </br>
"Geronimo, the computers are all down!" </br>
cried my <u><font face="Comic Sans MS" size="5" style="color:rgb(70,164,71);">proofreader</font></u>. Mickey Misprint. </br>
</font>

```

## Algorithm:

I have made an example of the algorithm (not golfed) in Java: Here is it This is the list of steps that you have to follow starting whit the base input:

1. Start catching a random word in position 5-20(words)
2. If the word is less or equals to 3 char long (e.g. `her`, `a`) catch the next word until you find someone whit more than 3 char
3. "Clean the word", the transformed word cant contain characters like `"` or `.`. The modified word has to starts and end whit \[A-Z\]\[a-z\] and only whit that characters so... clean it if you need is the 3th step

```
Examples of this step:
if you word is    | word cleaned
------------------|----------------
"Geronimo,        | Geronimo
final.            | final
air-conditioner   | air-conditioner  (Don't remove special characters inside the word)

```
4. Put it randomly (1/3 cases) in **bold**, *cursive* or underlined (Only one at the same time for word)
5. Give the word a bigger size than the rest of the text (how much big is your election)
6. Give the word a random color (Try to make this in the widest range of colors that you can, in my code creates an RGB with Java random function in every color that goes from 0 to 255)
7. Give the word any font... (What you want, doesn't matter what you use but must be different to the text font)
8. From this word repeat the 1st step for grab a new one random word next to this

Example of algorithm:

```
In step one by a random decision between 5 and 20 you have to start in word 7 for example:
It was in the morning of *June* 21, and I had just set
paw in the office.

On time that you have modified that word you start again the random function and
you add the result to your actual position for get the next word... the result
of the random function this time has been 8:
It was in the morning of *June* 21, and I had just set
paw *in* the office.

But that word is 2 char long and the next one too so we take the word "office"
It was in the morning of *June* 21, and I had just set
paw in the *office.*

Office has a point at the end, lets clean it:
It was in the morning of *June* 21, and I had just set
paw in the *office*.

And the last step is modify this last word

```

Rules

* As I have said, **the output can be show in your program** (or directly in HTML if you use JavaScript or something like that) **or outputs an HTML text whit all the properties in it**.
* The **structure of the HTML can be as you want, as long as when you execute it the result should follow the rules**. Basically, you don't have to make it like my example output.
* The **base font and size can be what you want**, I have used Verdana in my example because I think that the output is more... "beautiful"? and my code is not golfed.
* If you can, put a picture to the executed HTML in your solution please.
* In reference to the randomness, the only thing that is relevant is that **the output text has different colors, styles and words every time you run the program**, if there some options are more probable (for example red is more probable than green as a color) that doesn't matter.
* And in reference to the randomness of the colors, **it's not necessary that all colors are contemplated in the output, try to put the most colors you can**... I know that this is not very mathematically precise because is a problem to talk about colors when there are so much ways to create them (RGB, hexadecimal, HSV...) so I'm going to try to put a "minimal" rule:
* **Lets say that the "extreme" colors must have non 0 probability**, for example in RGB I mean that this colors are mandatory: `0,0,0` `255,255,255` `255,0,0` `0,255,0` `0,0,255` `255,0,255` `0,255,255` `255,255,0` but if you want you can use too the colors in between (That is the principal idea) And **if for some reason you cant use that rule of extreme colors have in mind that at least the output must be 8 different colors**.
* This is code golf, so the shortest code wins.

# Answer
> 3 votes
# JavaScript (Node.js), ~~246 244~~ 232 bytes

```
f=(i,j=p=0,r=_=>Math.random()*3|0,q=_=>p+=4+r()*5,x=q())=>i.replace(/[-'\w]+/g,m=>j++==p?(m[3]?[q(),`<${s="bis"[r()]} style="font:2em monospace;color:rgb(${[r()*85,r()*85,r()*85]})">${m}</${s}>`]:[++p,m])[1]:m).replace(/\n/g,"<br>")

```

Try it online!

*Saved ~~2~~ 8 bytes thanks to @ophact!*
*Saved 6 bytes thanks to @EliteDaMyth!*

---

Returns the resulting text with HTML-formatting applied.

(Ab)uses a RegExp-replacer to modify the picked words. If anyone is interested, I'd be happy to add an explanation, if requested.

---

```
f=(i,j=p=0,r=_=>Math.random()*3|0,q=_=>p+=4+r()*5,x=q())=>i.replace(/[-'\w]+/g,m=>j++==p?(m[3]?[q(),`<${s="bis"[r()]} style="font:2em monospace;color:rgb(${[r()*85,r()*85,r()*85]})">${m}</${s}>`]:[++p,m])[1]:m).replace(/\n/g,"<br>")

var c = `It was in the morning of June 21, and I had just set
paw in the office. Right away I could tell it wasn't
going to be a good day. My staff was running
around like a pack of rats in a maze. And everyone
was complaining about something.
"Geronimo, the air-conditioner's broken!"
yelled my secretary, Mousella MacMouser.
"Geronimo, we are run out of coffee!" shrieked
Blasco Tabasco, one of my designers.
"Geronimo, the computers are all down!"
cried my proofreader. Mickey Misprint.`;

document.write(f(c));
```

# Answer
> 2 votes
# JavaScript (Node.js), ~~459...~~ 375 bytes

```
m=>`<p>${(g=(t,M=Math.random,c=_=>M()*255|0,o=c(),p=c(),q=c(),y='biu'[M()*3|0],x=(N,F)=>N.replace(/[a-zA-Z]|(?<=[a-zA-Z]).(?=[a-zA-Z])/g,F),T=t.length<20,z=_=>T?0:x(t[B=4+M()*15|0],G=>G)[3]?B:z())=>T?t:(t[C=z()]=x(t[C],Y=>`<${y} style=font-size:20;font-family:sans-serif;color:rgb(${[o,p,q]})>${Y}</${y}>`))&&t.slice(0,20).concat(g(t.slice(20))))(m.split(/\s/)).join` `}</p>`

```

Try it online!

Wow. Just wow. I'm probably missing a really obvious golf here. This is probably the longest program I have ever written, after "Help me count the omer".

## How does this work?

Wraps an immediate invocation of `g`, a recursive function, inside a `p` tag.

In `g`, we initialize multiple arguments: `t`, which is an array of words, `M`, the built-in random function, and then `c` which returns a random integer from 0 to 255. This is followed by three invocations used as the color of the word (each call to `g` only replaces one word). We also set the "effect" used on the modified word. Next, the function `x` is where the magic happens: takes a word and a callback and replaces all alphabetical letters and special characters sandwiched between alphabetical letters with a call to the callback. I'm not a regular expressions expert, but luckily I knew enough about lookbehinds and lookaheads to implement the `replace`. This saved 47 bytes because before I was using a lengthy `test` condition.

We also create `z` which finds a random number whose corresponding word has at least 4 characters.

Function body: if the length of `t` is less than 20, return `t` unchanged, otherwise set `t[C=z()]` (the random word) to a call to `x` with that word and a special HTML generator as a callback. We also use an `&&` so that rather than returning an assignment, we return a concatenation of the new `t` and a recursive call with `t.slice(20)`. Note that using spread operators saves no bytes.

`g` is then invoked with `m.split(/\s/)` and joined with a space.

---
Tags: code-golf, string, random
---


title: Tips for golfing in Subleq

text:
# Question
Title: Tips for golfing in Subleq
Subleq is a programming language with **only one** instruction. Each instruction contains 3 parameters. Code and data space is the same. How it works:

```
A B C

```

A, B and C are signed ints. Instructions are executed in the next way:

```
*B = *B - *A
if(*B <= 0) goto C;

```

One post is one tip. Write your tips for Subleq here!

Online interpreter, assembler and C to Subleq converter

# Answer
> 5 votes
# Third Argument in Output Command is Extra Memory

Subleq specifies output with the three word command `x -1 y`, where x is the address of the value to be output. Unlike other Subleq commands, execution will proceed to the next command in all cases and `y` is ignored. This means it is available to be used for memory.

For example `0:2 -1 65` will print the "A" (CHAR(65)) stored in 2: and then proceed to 3:.

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


# Question
Title: Connecting the Dots: Counting n²-gons in the n×n Grid
The recent volume of MAA's Mathematics Magazine had an article "Connecting the Dots: Maximal Polygons on a Square Grid" by Sam Chow, Ayla Gafni, and Paul Gafni about making (very convex) \\$n^2\\$-gons where each vertex is a different point of the \\$n \times n\\$ grid.

> One is not allowed to have two consecutive segments be collinear, since that would merge two sides of the polygon.

For example, the following images are from Figures 2 and 10 in the Chow, Gafni, Gafni paper, which show a \\$49\\$-gon on the \\$7 \times 7\\$ grid of dots and a \\$100\\$-gon on the \\$10 \times 10\\$ grid of dots:

In the paper, the authors show that it is possible to form these \\$n^2\\$-gons for all integers \\$n \geq 2\\$ except for \\$n=3\\$ and \\$n=5\\$.

# Challenge

This challenge will have you count the number of "essentially different" \\$n^2\\$-gons on the \\$n \times n\\$ grid, where two polygons are considered the same if you can reflect or rotate one to match the other.

To score this, I will run the code on my machine—a 2017 MacBook with an Intel chip and 8GB of RAM—for five minutes with increasing sizes of \\$n\\$. Your score will be the maximum value of \\$n\\$ that your program can produce, and ties will be broken by the amount of time it took to get to that value.

# Small test cases

(From the Chow, Gafni, Gafni paper.)

* When \\$n = 2\\$ there is only one \\$4\\$-gon, the square.
* When \\$n = 3\\$ there are no \\$9\\$-gons.
* When \\$n = 4\\$ there is only one \\$16\\$-gon:

* When \\$n = 5\\$ there are no \\$25\\$-gons.

# Answer
# Python 3 + Z3, N=5

Not 100% sure if this is correct. Basically a standard SAT/SMT coding of the Hamiltonian cycle problem, with additional clauses to block intersecting diagonals and collinear segments. Each time a solution is found all of its distinct rotations/flips are blocked. I've run it up to N=6 (2120 solutions found), which took 30 minutes.

Edit: I just realized that this only allows edges between adjacent grid points, but this restriction wasn't intended by the challenge. Oh well, I'll leave it up for now.

```
import collections
import heapq
import itertools
import math
import random
import time
import sys
import z3

show_paths = len(sys.argv) >= 2 and 'show' in sys.argv[1]

if show_paths:
    import numpy as np
    import pylab as plt
    from matplotlib import collections  as mc

    def show_path(path):
        lines = list(zip(path, path[1:] + path[:1]))
        c = np.array([(1, 0, 0, 1), (0, 1, 0, 1), (0, 0, 1, 1)])
        lc = mc.LineCollection(lines, colors=c, linewidths=2)
        fig, ax = plt.subplots()
        ax.add_collection(lc)
        ax.autoscale()
        ax.margins(0.1)
        plt.show()

def compute_min_distances(C, distance_matrix, starting_points, banned):
    min_distances = collections.defaultdict(lambda: float('inf'))
    open_set = []
    for i in starting_points:
        state = (i, C[i])
        min_distances[state] = 1
        open_set.append((1, state))
    while open_set:
        d, state = open_set.pop()
        if d > min_distances[state]:
            continue
        i, delta = state
        x0, y0 = c0 = C[i]
        for j, _ in distance_matrix[i]:
            if j in banned:
                continue
            x1, y1 = c1 = C[j]
            delta1 = (x1 - x0, y1 - y0)
            if delta in (delta1, (x0 - x1, y0 - y1)):
                continue
            state = (j, delta1)
            if d + 1 < min_distances[state]:
                min_distances[state] = d + 1
                heapq.heappush(open_set, (d + 1, state))
    distance_array = [float('inf') for _ in distance_matrix]
    distance_array[0] = 0
    for (i, _), d in min_distances.items():
        distance_array[i] = min(distance_array[i], d)
    return distance_array

def point_orientations(p, n):
    for (x, y) in (p, p[::-1]):
        for x1 in (x, n - 1 - x):
            for y1 in (y, n - 1 - y):
                yield (x1, y1)

def path_orientations(path, n):
    orientations = list(zip(*map(lambda p: point_orientations(p, n), path)))
    for o in orientations:
        i = o.index((0, 0))
        if o[i - 1] == (0, 1):
            o = o[::-1]
            i = (len(o) - 1) - i
        if o[(i + 1) % len(o)] != (0, 1):
            continue
        yield o[i:] + o[:i]

start_time = time.time()
for N in itertools.count(2):
    print("starting n = %d..." % N)
    solver = z3.Solver()
    C = [(x, y) for x in range(N) for y in range(N)]
    C_inv = {c : i for i, c in enumerate(C)}
    bit_width = math.ceil(math.log(N * N + 1, 2))
    P = [z3.BitVec('P_%d' % i, bit_width) for i in range(N * N)]
    V = [z3.BitVec('V_%d' % i, bit_width) for i in range(N * N)]
    for v in V:
        solver.add(z3.ULT(v, N * N))
    A = [[] for _ in range(N * N)]
    for i, (x, y) in enumerate(C):
        for dx, dy in itertools.product(range(-1, 2), repeat=2):
            if not (dx or dy):
                continue
            try:
                A[i].append(C_inv[(x + dx, y + dy)])
            except KeyError:
                pass
    H = [[(j, z3.Bool('H_%d_%d' % (i, j))) for j in A[i]] for i in range(N * N)]
    start = C_inv[(0, 1)]
    min_distances = compute_min_distances(C, H, [start], {0})
    end0, end1 = C_inv[(1, 0)], C_inv[(1, 1)]
    min_distances_rev = compute_min_distances(C, H, [end0, end1], {0, start})
    for i, (d0, d1) in enumerate(zip(min_distances, min_distances_rev)):
        if i not in (0, start):
            solver.add(z3.UGE(P[i], d0))
            solver.add(z3.ULE(P[i], N * N - d1))
    H_t = [[] for _ in range(N * N)]
    for i, row in enumerate(H):
        x0, y0 = C[i]
        for j, v in row:
            H_t[j].append(v)
            if i == 0:
                e = P[j] == 1
            elif j == 0:
                e = P[i] == (N * N - 1)
            else:
                e = P[j] == (P[i] + 1)
            clauses = [V[i] == j, e]
            x1, y1 = C[j]
            dy = y1 - y0
            dx = x1 - x0
            blocked = []
            if dy and dx:
                x_m = min(x0, x1)
                y_m = min(y0, y1)
                if dy == dx:
                    blocked.append(((x_m + 1, y_m), (x_m, y_m + 1)))
                else:
                    blocked.append(((x_m, y_m), (x_m + 1, y_m + 1)))
                blocked.append(blocked[-1][::-1])
            x2 = x1 + dx
            y2 = y1 + dy
            if all(0 <= c < N for c in (x2, y2)):
                blocked.append(((x1, y1), (x2, y2)))
            for (c0, c1) in blocked:
                k = C_inv[c0]
                l = C_inv[c1]
                clauses.append(z3.Not(next(w for m, w in H[k] if m == l)))
            solver.add(z3.Implies(v, z3.And(*clauses)))
    solver.add(P[0] == 0)
    solver.add(P[start] == 1)
    for row in H_t:
        solver.add(z3.PbEq([(v, 1) for v in row], 1))
    solutions = set()
    old_len = 0
    while solver.check() == z3.sat:
        model = solver.model()
        successors = [int(str(model.eval(v))) for v in V]
        path = [0]
        while len(path) < N * N:
            path.append(successors[path[-1]])
        path = tuple(C[i] for i in path)

        if show_paths:
            show_path(path)

        orientations = set(path_orientations(path, N))
        assert not any(reoriented in solutions for reoriented in orientations)
        solutions.add(path)
        for reoriented in orientations:
            successor = {}
            for p0, p1 in zip(reoriented, reoriented[1:] + reoriented[:1]):
                successor[C_inv[p0]] = C_inv[p1]
            solver.add(z3.Not(z3.And(*[v == successor[i] for i, v in enumerate(V)])))
        s = "%d solutions found so far... (%.1f seconds elapsed)" % (len(solutions), time.time() - start_time)
        sys.stdout.write(s + max(0, old_len - len(s)) * ' ' + '\r')
        sys.stdout.flush()
        old_len = len(s)
    sys.stdout.write(' ' * old_len + '\r')
    sys.stdout.flush()
    end_time = time.time()
    print("%d solution%s found for n = %d in %.2g seconds" % (len(solutions), 's' * (len(solutions) != 1), N, end_time - start_time))
    start_time = end_time

```
> 4 votes

# Answer
Work in progress... Still far over the 5 minute deadline set by OP, but already sharing some code to show what I have done so far.

Output:

```
N=6
Found 2956807 solutions in 12953858177 iterations.
Running time 41 minutes 17 seconds.

```

(Note that the previous version reported 9358354 without filtering rotation/mirroring. It appears that version had too aggressive pruning of the search tree. Unfortunately, less pruning in this version increased the running time a lot)

The strategy is to simply brute-force all possible paths as fast as possible and apply some pruning rules to cut the search tree short. The most effective pruning rule is to enforce that edge points are visited in clock-wise order.

For efficiency, I use a lookup table for all possible lines starting from a each grid point. And another lookup table to check what other lines are blocked/crossed by a certain line. I use 1D arrays instead of 2D containers/arrays.

My first experiments were in Java, which I later ported to C++ in the hope that that would be faster. Guess what, this only saved a few percent. Modern Java is very fast and comparable to C++ (for this use-case at least).

Contrary the code of @user1502040, my code not only considers lines between adjacent points, but between any two points (as long as there are no other intermediate points on that line). That gives some nice arbitrary paths. For example:

As suggested by @PeterKagey, for each solution found I generate all 8 permutations (mirroring/rotating) and use lexicographical sorting to see if we found the "lowest" solution of these eight. If not, we ignore the solution and trust we will find the lowest solution later during the search.

Below is the unpolished, work-in-progress code. While the program is running, it will update the `output/progress.html` file every 5 seconds to show a diagram with the current search path. If you open this file in a browser, the browser will automatically keep refreshing the page.

In addition, it will save an `output/solution-xyz.html` file every few solutions. This enables you to sample a few example solutions.

To be continued...

```
// To compile:
//    $ g++ -Wall --std=c++11 -DNDEBUG -O3 ConnectingTheDots.cpp \
//          -o ConnectingTheDots
//
// Examples:
//    N=2
//    Found 1 solutions in 4 iterations.
//    Running time 0 minutes 0 seconds.
//
//    N=3
//    Found 0 solutions in 9 iterations.
//    Running time 0 minutes 0 seconds.
//
//    N=4
//    Found 1 solutions in 422 iterations.
//    Running time 0 minutes 0 seconds.
//
//    N=5
//    Found 0 solutions in 376217 iterations.
//    Running time 0 minutes 0 seconds.
//
//    N=6
//    Found 2956807 solutions in 12953858177 iterations.
//    Running time 41 minutes 17 seconds.
//
// Improvement opportunities:
//
// - Parallelize: a brute-force search is trivial to run massively parallel on
//   all available CPU cores. Use POSIX pthread to create worker threads.
//
// - Data locality: lookup tables currently use 32-bit integers and have large
//   ROW_SIZEs. This reduces data locality and thus memory caching. Ideas:
//       - Consider using 8-bit resp. 16-bit integers (for N <= 8)
//       - Store data consecutively in array and use row pointers.
//
// - Roll back: making a step and rolling it back involves selectively saving
//   and restoring parts of the state. The overhead of this bookkeeping is
//   large. Perhaps it is faster to blindly copy the entire state.
//
//   To make the copy fast, we could condense the state into a smaller memory
//   footprint (at the cost of some bit masking and shifting). For example, the
//   pointAvailable[] and lineAvailable[] boolean arrays could be bitmaps which
//   makes them 32x times smaller.
//
// - Island pruning rule: when the path waves from an edge point inward and
//   then back to the next edge point, it may not enclose an unvisited point.
//   These islands can never be visited. Beware that the island must be really
//   enclosed. Just checking neighbouring points is not enough, since sharp
//   "spikes" can still reach far away isolated points.

#include <stdlib.h>
#include <stdio.h>
#include <algorithm> // std::min
#include <time.h>
#include <sys/stat.h>   // mkdir

// User-specified dimensions
const int N = 6;

// Calculated dimensions
const int MAX_POS = N*N;
const int MAX_LINE = MAX_POS*MAX_POS;

/** ---------------------------------------------------------------------------
 * Class to check whether two line segments intersect.
 * 2D integer coordinates only.
 *
 * Reference:
 *  https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
 *  http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
 */
class Intersect {
public:
   /**
    * Check whether lines p1q1 and p2q2 cross eachother.
    *
    * @return `true` if crossed
    */
   static bool isCrossed(int p1, int q1, int p2, int q2) {
      assert(p1 >= 0 && p1 < MAX_POS);
      assert(q1 >= 0 && q1 < MAX_POS);
      assert(p2 >= 0 && p2 < MAX_POS);
      assert(q2 >= 0 && q2 < MAX_POS);
      assert(p1 != q1);
      assert(p2 != q2);

      // endpoints may touch
      if (p1 == p2 || p1 == q2 || q1 == p2 || q1 == q2) return false;

      // convert point IDs to 2D coordinates
      int p1x = p1 % N; int p1y = p1 / N;
      int q1x = q1 % N; int q1y = q1 / N;
      int p2x = p2 % N; int p2y = p2 / N;
      int q2x = q2 % N; int q2y = q2 / N;

      // Find the four orientations needed for general and
      // special cases
      int o1 = orientation(p1x, p1y, q1x, q1y, p2x, p2y);
      int o2 = orientation(p1x, p1y, q1x, q1y, q2x, q2y);
      int o3 = orientation(p2x, p2y, q2x, q2y, p1x, p1y);
      int o4 = orientation(p2x, p2y, q2x, q2y, q1x, q1y);

      // General case
      if (o1 != o2 && o3 != o4) return true;

      // Special Cases
      // p1, q1 and p2 are colinear and p2 lies on segment p1q1
      if (o1 == 0 && onSegment(p1x, p1y, p2x, p2y, q1x, q1y)) return true;

      // p1, q1 and q2 are colinear and q2 lies on segment p1q1
      if (o2 == 0 && onSegment(p1x, p1y, q2x, q2y, q1x, q1y)) return true;

      // p2, q2 and p1 are colinear and p1 lies on segment p2q2
      if (o3 == 0 && onSegment(p2x, p2y, p1x, p1y, q2x, q2y)) return true;

      // p2, q2 and q1 are colinear and q1 lies on segment p2q2
      if (o4 == 0 && onSegment(p2x, p2y, q1x, q1y, q2x, q2y)) return true;

      return false; // Doesn't fall in any of the above cases
   }

private:
   /**
    * To find orientation of ordered triplet (p, q, r).
    *
    * @return 0 --> p, q and r are colinear
    *       1 --> Clockwise
    *       2 --> Counterclockwise
    */
   static int orientation(int px, int py, int qx, int qy, int rx, int ry) {
      int val = (qy - py)*(rx - qx) - (qx - px)*(ry - qy);

      if (val == 0) return 0; // colinear
      return (val > 0) ? 1 : 2; // clock or counterclock wise
   }

   /**
    * Given three colinear points p, q, r, the function checks if
    * point q lies on line segment 'pr'.
    *
    * @return `true` if point q lies on line segment pr
    */
   static bool onSegment(int px, int py, int qx, int qy, int rx, int ry) {
      if (qx <= std::max(px, rx) && qx >= std::min(px, rx) &&
          qy <= std::max(py, ry) && qy >= std::min(py, ry)) {
         return true;
      }
      return false;
   }
};

/** ---------------------------------------------------------------------------
 * Lookup table with all possible connections.
 */
class LinesLookupTable {
public:
   /**
    * Build look up table.
    */
   void build() {
      assert(ROW_SIZE >= (N*N)-1);
      lines = new int[MAX_POS*ROW_SIZE];

      // iterate point i over grid
      for (int i = 0; i < MAX_POS; i++) {
         int x = i%N;
         int y = i/N;

         int nrLines = 0;

         // iterate point j over grid
         for (int j = 0; j < MAX_POS; j++) {
            if (i == j) continue;

            int dx = (j%N) - x;
            int dy = (j/N) - y;

            // not allowed to have another point on the line
            bool isValid = true;
            for (int div = 2; div < N; div++) {
               if ((abs(dx) % div) == 0 &&
                  (abs(dy) % div) == 0) {
                  isValid = false;
                  break;
               }
            }
            if (!isValid) continue;

            // found a valid line
            assert(nrLines < ROW_SIZE);
            lines[i*ROW_SIZE + nrLines++] = j;
         }

         // write end of list marker
         assert(nrLines < ROW_SIZE);
         lines[i*ROW_SIZE + nrLines] = -1;
      }
   }

   /**
    * Get list of lines connecting specified position.
    * @param position   start position
    * @return array with connecting positions, terminated by -1
    */
   const int *getLines(int position) const {
      assert(position >= 0 && position < MAX_POS);
      return &lines[position*ROW_SIZE];
   }

private:
   static const int  ROW_SIZE = 64;
   int               *lines;
};

/** ---------------------------------------------------------------------------
 * Create line ID based on two points.
 * We choose a consistent order of begin and end point to prevent
 * double counting.
 *
 * @param p  begin point
 * @param q  end point
 */
inline int makeLineId(int p, int q) {
   assert(p >= 0 && p < MAX_POS);
   assert(q >= 0 && q < MAX_POS);
   return std::min(p, q)*MAX_POS + std::max(p, q);
}

/** ---------------------------------------------------------------------------
 * Lookup table with all other lines that are blocked by a certain line.
 */
class BlockedLookupTable {
public:
   BlockedLookupTable(LinesLookupTable *linesLookupTable_) :
      linesLookupTable(linesLookupTable_) {
   }

   /**
    * Build look up table.
    */
   void build() {
      blocked = new int[MAX_LINE*ROW_SIZE];

      // iterate point i over grid
      for (int i = 0; i < MAX_POS; i++) {
         // iterate point j over all lines connecting i
         const int *jp = linesLookupTable->getLines(i);
         for (int j = *jp++; j != -1; j = *jp++) {
            assert(j >= 0 && j < MAX_POS);
            int lineId = makeLineId(i, j);
            int nrBlocked = 0;

            // iterate point p over grid
            for (int p = 0; p < MAX_POS; p++) {
               // iterate point q over all lines connecting p
               const int *qp = linesLookupTable->getLines(p);
               for (int q = *qp++; q != -1; q = *qp++) {
                  assert(q >= 0 && q < MAX_POS);
                  int lineId2 = makeLineId(p, q);
                  if (lineId == lineId2) continue;

                  // check if line i-j crosses line p-q
                  if (Intersect::isCrossed(i, j, p, q)) {
                     assert(nrBlocked < ROW_SIZE);
                     blocked[lineId*ROW_SIZE + nrBlocked++] = lineId2;
                  }
               }
            }

            // block lines colinear with line i-j
            int dx = (j%N) - (i%N);
            int dy = (j/N) - (i/N);

            // extend out from i
            int x = (i%N) - dx;
            int y = (i/N) - dy;
            if (x >= 0 && x < N && y >= 0 && y < N) {
               int k = x + y*N;
               int lineId2 = makeLineId(i, k);
               assert(nrBlocked < ROW_SIZE);
               blocked[lineId*ROW_SIZE + nrBlocked++] = lineId2;
            }

            // extend out from j
            x = (j%N) + dx;
            y = (j/N) + dy;
            if (x >= 0 && x < N && y >= 0 && y < N) {
               int k = x + y*N;
               int lineId2 = makeLineId(j, k);
               assert(nrBlocked < ROW_SIZE);
               blocked[lineId*ROW_SIZE + nrBlocked++] = lineId2;
            }

            // write end of list marker
            assert(nrBlocked < ROW_SIZE);
            blocked[lineId*ROW_SIZE + nrBlocked] = -1;
         }
      }
   }

   /**
    * Get list of lines blocked by the specified line
    * @param lineId  line
    * @return array with blocked lines, terminated by -1
    */
   const int *getBlockedLines(int lineId) {
      assert(lineId >= 0 && lineId < MAX_LINE);
      assert(lineId/MAX_POS < lineId%MAX_POS);
      return &blocked[lineId*ROW_SIZE];
   }

private:
   static const int  ROW_SIZE = 512;
   LinesLookupTable   *linesLookupTable;
   int               *blocked;
};

/** ---------------------------------------------------------------------------
 * Class for printing paths to console and rendering path diagrams in HTML file
 */
class Output {
public:
   Output() :
      updateProgressTime(0) {
   }

   /**
    * Show current path.
    */
   void printPath(const int *path, int pathLen) {
      if (pathLen > 0) {
         printf("%d", path[0]);
         for (int i = 1; i < pathLen; i++) {
            printf(", %d", path[i]);
         }
      }
      if (pathLen < MAX_POS+1) {
         printf(", ...");
      }
      printf("\n");
   }

   /**
    * Periodically dump path to console, and redraw diagram in HTML file.
    */
   void updateProgress(const int *path, int pathLen) {
      if (updateProgressInterval > 0 &&
         time(NULL) >= updateProgressTime + updateProgressInterval) {

         printPath(path, pathLen);

         char filePath[256];
         snprintf(filePath, sizeof(filePath), "%s/%s", outputDir,
                  progressFile);
         drawPath(path, pathLen, filePath, true);

         updateProgressTime = time(NULL);
      }
   }

   /**
    * Draw solution diagram in HTML file.
    */
   void drawSolution(const int *path, int pathLen, int solutionId) {
      char fileName[256];
      snprintf(fileName, sizeof(fileName), solutionFile, solutionId);

      char filePath[256];
      snprintf(filePath, sizeof(filePath), "%s/%s", outputDir, fileName);

      drawPath(path, pathLen, filePath, false);
      printf("Written \"%s\"\n", filePath);
   }

private:
   static const int updateProgressInterval   = 5;  // in seconds (0=disable)
   static constexpr const char *outputDir    = "output";
   static constexpr const char *progressFile = "progress.html";
   static constexpr const char *solutionFile = "solution-%04d.html";

   time_t   updateProgressTime;

   /**
    * Ensure output directory exists.
    */
   void makeOutputDir() {
      struct stat st = {0};
      if (stat(outputDir, &st) == -1) {
         if (mkdir(outputDir, 0775)) {
            perror("Failed to create output directory");
            exit(-1);
         }
      }
   }

   /**
    * Draw current (partial) path in SVG diagram and embed in HTML file.
    * @param filePath   directory and file name of HTML file
    * @param refresh    if `true` the HTML file will periodically reload in the
    *                   browser
    */
   void drawPath(const int *path, int pathLen, const char *filePath,
                 bool refresh) {
      makeOutputDir();

      char tempFilePath[256];
      snprintf(tempFilePath, sizeof(tempFilePath), "%s.tmp", filePath);
      FILE *fp = fopen(tempFilePath, "w");
      if (fp == NULL) {
         perror("Failed to create file");
         return;
      }
      fprintf(fp, "<!DOCTYPE html>\n");
      fprintf(fp, "<html>\n");
      if (refresh) {
         fprintf(fp, "<head>\n");
         fprintf(fp, "<meta http-equiv=\"refresh\" content=\"%d\" />\n",
                 updateProgressInterval+1);
         fprintf(fp, "</head>\n");
      }

      fprintf(fp, "<body>\n");
      fprintf(fp, "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\""
                  " width=\"%.1f\" height=\"%.1f\">\n", N*100.0, N*100.0);
      for (int y = 0; y < N; y++) {
         for (int x = 0; x < N; x++) {
            fprintf(fp, "<circle cx=\"%.1f\" cy=\"%.1f\" r=\"5.0\" "
                        "fill=\"black\" />\n", 50.0 + x*100.0, 50.0 + y*100.0);
         }
      }
      for (int i = 0; i+1 < pathLen; i++) {
         int x1 = path[i]%N;
         int y1 = path[i]/N;
         int x2 = path[i+1]%N;
         int y2 = path[i+1]/N;
         fprintf(fp, "<polyline points=\"%.1f,%1.f %.1f,%.1f\" "
                     "style=\"fill:none;stroke:#000000;stroke-width:2.0;\" "
                     "/>\n",
            50.0 + x1*100.0, 50.0 + y1*100.0,
            50.0 + x2*100.0, 50.0 + y2*100.0);
      }
      fprintf(fp, "</svg>\n");
      fprintf(fp, "</body>\n");
      fprintf(fp, "</html>\n");
      fclose(fp);
      rename(tempFilePath, filePath);
   }
};

/** ---------------------------------------------------------------------------
 * Search all possible paths.
 */
class Solver {
public:
   Solver(
      LinesLookupTable *linesLookupTable_,
      BlockedLookupTable *blockedLookupTable_,
      Output *output_):

      linesLookupTable(linesLookupTable_),
      blockedLookupTable(blockedLookupTable_),
      output(output_) {
   }

   /**
    * Search all possible paths
    */
   void solve() {
      buildNextEdgePointTable();

      pointAvailable = new bool[MAX_POS];
      for (int i = 0; i < MAX_POS; i++) {
         pointAvailable[i] = (nextEdgePoint[i] == -1);
      }
      pointAvailable[N] = false; // end of edge
      pointAvailable[nextEdgePoint[0]] = true;

      lineAvailable = new bool[MAX_LINE];
      for (int i = 0; i < MAX_LINE; i++) {
         lineAvailable[i] = true;
      }

      path = new int[MAX_POS+1];
      pathLen = 0;

      nrIterations = 0;
      nrSolutions = 0;
      path[pathLen++] = 0;
      pointAvailable[0] = false;
      recurseNextStep(0);

      printf("Found %llu solutions in %llu iterations.\n",
         nrSolutions, nrIterations);
   }

private:
   LinesLookupTable    *linesLookupTable;
   BlockedLookupTable  *blockedLookupTable;
   Output              *output;

   int                 *nextEdgePoint;
   bool                *pointAvailable;
   bool                *lineAvailable;
   unsigned long long   nrSolutions;
   int                 *path;
   int                  pathLen;
   unsigned long long   nrIterations;

   /**
    * Build nextEdgePoint[] lookup table
    */
   void buildNextEdgePointTable() {
      nextEdgePoint = new int[MAX_POS];
      for (int i = 0; i < MAX_POS; i++) {
         nextEdgePoint[i] = -1;
      }
      int prev = 0;
      for (int x = 1; x < N; x++) {
         int y = 0;
         int point = y*N + x;
         nextEdgePoint[prev] = point;
         prev = point;
      }
      for (int y = 1; y < N; y++) {
         int x = N-1;
         int point = y*N + x;
         nextEdgePoint[prev] = point;
         prev = point;
      }
      for (int x = N-2; x >= 0; x--) {
         int y = N-1;
         int point = y*N + x;
         nextEdgePoint[prev] = point;
         prev = point;
      }
      for (int y = N-2; y >= 1; y--) {
         int x = 0;
         int point = y*N + x;
         nextEdgePoint[prev] = point;
         prev = point;
      }
   }

   /**
    * Iterate over all possible next steps starting at current position.
    * @param i  current 1D position
    */
   void recurseNextStep(int i) {
      nrIterations++;
      if (pathLen == MAX_POS) {
         // We are ready to make the last hop. Check if we can close the loop.
         closeLoop(i);
      } else {
         int blockedLines[256];
         int nrBlockedLines = 0;
         bool isDeadEnd = true;

         // Iterate over all possible next steps 'j' starting at
         // current position 'i'.
         const int *jp = linesLookupTable->getLines(i);
         for (int j = *jp++; j >= 0; j = *jp++) {
            assert(j >= 0 && j < MAX_POS);

            // target point still available?
            if (pointAvailable[j]) {

               // line to target point still available?
               int lineId = makeLineId(i, j);
               assert(lineId >= 0 && lineId < MAX_LINE);
               if (lineAvailable[lineId]) {

                  // found a valid next step
                  path[pathLen++] = j;
                  isDeadEnd = false;

                  // mark points and lines as used, but keep track of
                  // changes so we can roll them back later
                  lineAvailable[lineId] = false;
                  const int *bp = blockedLookupTable->getBlockedLines(lineId);
                  for (int lineId2 = *bp++; lineId2 != -1; lineId2 = *bp++) {
                     assert(lineId2 >= 0 && lineId2 < MAX_LINE);
                     if (lineAvailable[lineId2]) {
                        assert(nrBlockedLines < 256);
                        blockedLines[nrBlockedLines++] = lineId2;
                        lineAvailable[lineId2] = false;
                     }
                  }
                  pointAvailable[j] = false;

                  // make sure edge points are visited in order
                  if (nextEdgePoint[j] != -1) {
                     assert(!pointAvailable[nextEdgePoint[j]]);
                     pointAvailable[nextEdgePoint[j]] = true;
                  }

                  // search next step
                  recurseNextStep(j);

                  // roll back changes
                  if (nextEdgePoint[j] != -1) {
                     pointAvailable[nextEdgePoint[j]] = false;
                  }
                  pointAvailable[j] = true;
                  pathLen--;
                  while (nrBlockedLines > 0) {
                     nrBlockedLines--;
                     int lineId2 = blockedLines[nrBlockedLines];
                     assert(lineId2 >= 0 && lineId2 < MAX_LINE);
                     lineAvailable[lineId2] = true;
                  }
                  assert(lineId >= 0 && lineId < MAX_LINE);
                  lineAvailable[lineId] = true;
               }
            }
         }

         if (isDeadEnd) {
            output->updateProgress(path, pathLen);
         }
      }
   }

   /**
    * Try to close the loop back to position 0.
    * @param position   current 1D position
    */
   void closeLoop(int i) {
      // Iterate over all possible next steps 'j' starting at
      // current position 'i'.
      const int *jp = linesLookupTable->getLines(i);
      for (int j = *jp++; j >= 0; j = *jp++) {
         assert(j >= 0 && j < MAX_POS);
         if (j != 0) continue;

         // line to target point still available?
         int lineId = makeLineId(i, j);
         if (lineAvailable[lineId]) {
            path[pathLen++] = j;

            // found a valid loop! Now check if this is the "lowest" of all
            // equivalent paths.
            if (isLowestSolution()) {
               // Sample some random paths by drawing every few solutions.
               // for N=6, we will find 2956807 solutions. Aim for 100 examples.
               if ((nrSolutions % 29568) == 0) {
                  output->drawSolution(path, pathLen, nrSolutions);
               }

               nrSolutions++;
            }

            pathLen--;
         }
      }
   }

   /**
    * Check whether the solution found is the "lowest" equivalent solution
    * when sorted lexicographically.
    *
    * By rotating and mirroring each path can result in up to 8 equivalent
    * paths. We choose the lexicographically lowest solution as the "main"
    * solution.
    *
    * @returns `true` if the current path equals lowest equivalent path
    */
   bool isLowestSolution() {
      assert(pathLen >= MAX_POS);

      int rotatedPath[MAX_POS+1];
      memcpy(rotatedPath, path, pathLen*sizeof(rotatedPath[0]));

      for (int permutation = 1; permutation < 8; permutation++) {
         // rotate clockwise
         for (int i = 0; i < pathLen; i++) {
            int x = rotatedPath[i]%N;
            int y = rotatedPath[i]/N;

            int rotX = N-1-y;
            int rotY = x;

            rotatedPath[i] = rotY*N + rotX;
         }

         // after 4 rotations we are upright again. Now mirror horizontally.
         // note after mirroring the path runs counter-clockwise. We therefore
         // also need to reverse the order of the points visited
         if (permutation == 4) {
#ifndef NDEBUG
            // assert we are upright again
            for (int i = 0; i < pathLen; i++) {
               assert(path[i] == rotatedPath[i]);
            }
#endif
            int mirroredPath[MAX_POS+1];
            for (int i = 0; i < pathLen; i++) {
               int x = rotatedPath[i]%N;
               int y = rotatedPath[i]/N;

               int rotX = N-1-x;
               int rotY = y;

               mirroredPath[pathLen-1-i] = rotY*N + rotX;
            }
            memcpy(rotatedPath, mirroredPath, pathLen*sizeof(rotatedPath[0]));
         }

         if (comparePaths(path, rotatedPath) > 0) return false;
      }

      // of all 8 permutations, the current path is the "lowest" (or equal
      // to some of the permutations in case of symmetric, but since the path
      // generator will only generate that path once, it is not a problem).
      return true;
   }

   /**
    * Compare two paths.
    * Assumes path A starts at point 0, path B can start anywhere.
    *
    * @return -1 if A < B, +1 if A > B
    */
   int comparePaths(const int *pathA, const int *pathB) {
      assert(pathA[0] == 0);

      // find point 0 in path B
      int offset;
      for (offset = 0; offset < MAX_POS && pathB[offset] != 0; offset++);
      assert(pathB[offset] == 0);

      // compare path A with path B
      for (int i = 0, j = offset; i < MAX_POS; i++, j = (j+1) % MAX_POS) {
         if (pathA[i] < pathB[j]) return -1;
         if (pathA[i] > pathB[j]) return +1;
      }
      return 0;
   }
};

/** ---------------------------------------------------------------------------
 * Main program
 */
int main() {
   LinesLookupTable    *linesLookupTable;
   BlockedLookupTable  *blockedLookupTable;
   Output              *output;
   Solver              *solver;

   time_t startTime = time(NULL);

   linesLookupTable   = new LinesLookupTable();
   blockedLookupTable = new BlockedLookupTable(linesLookupTable);
   output             = new Output();
   solver             = new Solver(linesLookupTable, blockedLookupTable,
                                   output);
   printf("N=%d\n", N);

   linesLookupTable->build();
   blockedLookupTable->build();
   solver->solve();

   int seconds = time(NULL) - startTime;
   printf("Running time %d minutes %d seconds.\n", seconds/60, seconds%60);

   return 0;
}

```
> 3 votes

---
Tags: sequence, geometry, combinatorics, grid, fastest-code
---


title: Has My Pie Been Bisected?

text:
# Question
Title: Has My Pie Been Bisected?
Write a program or function that takes in a nonempty list of positive integers. You may assume it is input in a reasonable convenient format such as `"1 2 3 4"` or `[1, 2, 3, 4]`.

The numbers in the input list represent the slices of a full pie chart where each slice size is proportional to its corresponding number and all slices are arranged around the chart in the order given.

For example, the pie for `1 2 3 4` is:

The question your code must answer is: **Is the pie chart ever bisected?** That is, is there ever a perfectly straight line from one side of the circle to the other, splitting it symmetrically in two?

You need to **output a truthy value if there is at least one bisector and output a falsy value if there are none**.

In the `1 2 3 4` example there is a bisection between `4 1` and `2 3` so the output would be truthy.

But for input `1 2 3 4 5` there is no bisector so the output would be falsy:

# Additional Examples

Arranging numbers differently may remove bisectors.
e.g. `2 1 3 4` → falsy:

If only one number is in the input list the pie is not bisected.
e.g. `10` → falsy:

There may be multiple bisectors. As long as there are more than zero the output is truthy.
e.g. `6 6 12 12 12 11 1 12` → truthy: (there are 3 bisectors here)

Bisections may exist even if they are not visually obvious.
e.g. `1000000 1000001` → falsy:

e.g. `1000000 1000001 1` → truthy:

(Thanks to nces.ed.gov for generating the pie charts.)

# Test Cases

```
Truthy
1 2 3 4
6 6 12 12 12 11 1 12
1000000 1000001 1
1 2 3
1 1
42 42
1 17 9 13 2 7 3
3 1 2
10 20 10

Falsy
1 2 3 4 5
2 1 3 4
10
1000000 1000001
1
1 2
3 1 1
1 2 1 2 1 2
10 20 10 1

```

# Scoring

The shortest code in bytes wins. Tiebreaker is earlier answer.

# Answer
# J, 18 bytes

5 bytes thanks to Dennis.

```
+/e.[:,/2*+/\-/+/\

```

@HelkaHomba: Nope.

### Usage

```
>> f =: +/e.[:,/2*+/\-/+/\
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

```

### Ungolfed

```
black_magic  =: +/\-/+/\
doubled_bm   =: 2 * black_magic
flatten      =: ,/
sum          =: +/
is_member_of =: e.
f =: sum is_member_of monadic flatten doubled_bm

```

---

## Previous 23-byte version:

```
[:+/[:+/+/=+:@-/~@(+/\)

```

### Usage

```
>> f =: [:+/[:+/+/=+:@-/~@(+/\)
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

```

### Ungolfed

```
black_magic =: -/~@(+/\)
double      =: +:
equals      =: =
sum         =: +/
monadic     =: [:
of          =: @
f =: monadic sum monadic sum (sum equals double of black_magic)

```

---

## Explanation

The sum of all substrings is calculated by the black\_magic. The `+/\` calculate the partial sums.

For example, `a b c d` becomes `a a+b a+b+c a+b+c+d`.

The `-/~` then constructs a subtraction table based on the input, so `x y z` becomes:

```
x-x x-y x-z
y-x y-y y-z
z-x z-y z-z

```

When applied to `a a+b a+b+c a+b+c+d`, the result would be:

```
    0  -b -b-c -b-c-d
    b   0   -c   -c-d
  b+c   c    0     -d
b+c+d c+d    d      0

```

This calculated the sums of all the substrings which does not contain `a`.

This guarantees to be enough, since if one bisection contains `a`, the other bisection will not contain `a` and also will not wrap around.
> 12 votes

# Answer
# Jelly, ~~9~~ 8 bytes

```
Ḥ+\©_Sf®

```

Return a non-empty list (truthy) or an empty list (falsy). Try it online! or verify all test cases.

### How it works

```
Ḥ+\©_Sf®  Main link. Argument: A (list)

Ḥ         Double all integers in A.
 +\       Take the cumulative sum of 2A.
   ©      Copy; store the result in the register.
    _S    Subtract the sum of A from each partial sum of 2A.
      f®  Filter; intersect this list with the list in the register.

```
> 10 votes

# Answer
# Julia, ~~34~~ ~~30~~ 29 bytes

```
!x=sum(x)∈cumsum!(x,2x).-x'

```

*Thanks to @GlenO for golfing off 1 byte!*

Try it online!

### How it works

After storing the cumulative sum of **2x** in **x**, we subtract the row vector **x'** from the column vector **x**, yielding the matrix of all possible differences. Essentially, this computes the sums of all adjacent subarrays of **x** that do not contain the first value, their negatives, and **0**'s in the diagonal.

Finally, we test if the sum of the original array **x** belongs to the generated matrix. If this is the case, the sum of at least one of the adjacent sublists is equal to exactly halve of the sum of the entire list, meaning that there is at least one bisector.
> 7 votes

# Answer
## Haskell, 41 bytes

```
f l=elem(sum l/2)$scanr(:)[]l>>=scanl(+)0

```

The idea is to check whether there is a sublist of `l` whose sum equals `sum l/2`. We generate the sums of these sublists as `scanr(:)[]l>>=scanl(+)0`. Let's look at how this works with `l=[1,2,3]`

```
>> scanr(:)[]l
[[1,2,3],[2,3],[3],[]]
-- the suffixes of l

>> scanl(+)0 [2,3,4]
[0,2,5,9]
-- the cumulative sums of the input

>> scanr(:)[]l>>=scanl(+)0
[0,1,3,6,0,2,5,0,3,0]
-- the cumulative sums of the suffixes of l, flattened to a single list

```

**Old 43 bytes:**

```
f l|c<-scanl1(+)l=elem(sum l/2)$(-)<$>c<*>c

```

Generates the list `c` of cumulative sums. Then, checks if any two of these sums differ by `sum l/2` by checking if it is an element of the list of differences `(-)<$>c<*>c`.
> 6 votes

# Answer
## Python 2, 64 bytes

```
f=lambda l,s=0:l>[]and(sum(l)==s)|f(l[1:],s+l[0])|f(l,s+l.pop())

```

Recursively tries to remove elements from the front or end until the sum of what remains equals the sum of what was deleted, which is stored is `s`. Takes time exponential in the list length.

Dennis saved 3 bytes with `pop`.
> 5 votes

# Answer
# Pyth, ~~10~~ 9 bytes

```
}sQmysd.:

```

Test it in the Pyth Compiler.

### How it works

```
       .:  Generate the list of all adjacent sublists.
   m       Map over the result:
     sd       Add the integers of the sublist.
    y         Double the sum.
 sQ        Compute the sum of the input.
}          Check if it belongs to the list of doubled sublist sums.

```
> 4 votes

# Answer
# Python 2, ~~76~~ ~~74~~ ~~70~~ 66 bytes

```
def f(x):n=sum(x);print n in[2*sum(x[k/n:k%n])for k in range(n*n)]

```

*Thanks to @xnor for golfing off ~~4~~ 8 bytes!*

Test it on Ideone. (larger test cases excluded)
> 4 votes

# Answer
## Actually, 21 bytes

```
;Σ@2*;lR@τ╗`╜V♂Σi`Míu

```

Try it online!

This program prints out a `0` for false cases, and a positive integer for true cases.

Explanation:

```
;Σ@2*;lR@τ╗`╜V♂Σi`Míu
;Σ                     sum of copy of input
  @2*                  double values in other copy
     ;lR               copy, range(1, len(input)+1)
        @τ             append other copy to itself
          ╗            save in reg0
           `╜V♂Σi`M    map: generate cyclic cumulative sums
                   íu  1-based index of sum of input (0 if not found)

```

## Non-competing version, 10 bytes

```
;Σ@2*σ;)-∩

```

Try it online!

This program outputs an empty list for false cases and a non-empty list otherwise. It is essentially a port of Dennis's Jelly answer. It is non-competing because the cumulative sum and vectorized difference functionality post-date the challenge.

Explanation:

```
;Σ@2*σ;)-∩
;Σ          sum of copy of input
  @2*       multiply values in other copy by 2
     σ;     two copies of cumulative sum
       )-   subtract sum of input from each element in one copy
         ∩  set intersection with other copy

```
> 4 votes

# Answer
# Python 2, 47 bytes

```
k=t=1
for x in input():t<<=x;k|=t*t
print k&k/t

```

Try it online!

I'm back 2.75 years later to beat my old solution by over 25% using a new method.

This 1-byte longer version is a little clearer.

```
k=t=0
for x in input():t+=x;k|=4**t
print k&k>>t

```

Try it online!

The idea is to store the set of cumulative sums `t` as bits of `k`, setting bit `2*t` to indicate that `t` is a cumulative sum. Then, we check if any two cumulative sums differ by half the list sum (final `t`) by bit-shifting `k` this much and doing bitwise `&` with the original to see the result is nonzero (truthy).
> 4 votes

# Answer
# MATL, 10 bytes

```
EYst!-Gs=z

```

The output is the number of bisectors.

**Try it online!**

### Explanation

Same approach as Dennis' Julia answer.

```
E       % Implicit input. Multiply by 2 element-wise
Ys      % Cumulative sum
t!-     % Compute all pairwise differences. Gives a 2D array
Gs      % Sum of input
=       % Test for equality, element-wise
z       % Number of nonzero elements. Implicit display

```
> 3 votes

# Answer
# Ruby, ~~60~~ 53 bytes

```
->a{a.any?{r=eval a*?+;a.rotate!.any?{|i|0==r-=2*i}}}

```

Generates all possible partitions by taking every rotation of the input array and then taking all slices of length 1..`n`, where `n` is the size of the input array. Then checks if there exists any partition with a sum half the total sum of the input array.
> 3 votes

# Answer
# Vyxal, 6 bytes

```
¦Dt½-∩

```

Try it Online!

As in Jelly, a list is falsy iff it is empty.

```
¦         Push the cumulative sums
 D        three times.
  t       Take the last one,
   ½      halve it,
    -     subtract it from each of the cumulative sums,
     ∩    and take the intersection of the differences and the cumulative sums.

```
> 3 votes

# Answer
## JavaScript (ES6), 83 bytes

```
a=>a.map(_=>a.slice(--n).map(m=>s.push(t+=m),t=0),s=[],n=a.length)&&s.includes(t/2)

```

Generates all possible sums, then checks to see whether half of the last sum (which is the sum of the whole list) appears in the list. (Generating the sums in the slightly awkward order to arrange for the sum I need to be last saves 4 bytes.)
> 2 votes

# Answer
# Dyalog APL, 12 bytes

```
+/∊2×+\∘.-+\

```

Test it with TryAPL.

### How it works

```
+/∊2×+\∘.-+\  Monadic function train. Right argument: y (vector)

     +\   +\  Yield the cumulative sum of y.
       ∘.-    Compute all differences of all partial sums.
              This computes the sums of all adjacent subvectors of y that do not
              contain the first value, their negatives, and 0's in the diagonal.
   2×         Multiply all differences by 2.
+/            Yield the sum of y.
  ∊           Test for membership.

```
> 2 votes

# Answer
# Jelly, 6 bytes

```
ÄḤf_¥S

```

Try it online!

Jelly has gained a single-byte builtin for cumulative sums since Dennis posted his solution, making it trivial to golf to 7 bytes. Turns out there's a lot of creative ways to tie 7, but to hit 6 all it takes is restructuring it with a dyadic chain.

```
 Ḥ        Double
Ä         the cumulative sums,
  f       then filter them by membership in
   _¥     the differences between them and
     S    the total sum.

```

As Dennis presumably observed, a difference of partial sums is the sum of a substring, and if a difference of partial sums is half the total sum, the difference of a partial sum and the total sum is another partial sum.
> 2 votes

# Answer
# C, 161 145 129 bytes

* saved few bytes thanks to @LeakyNun
* saved few bytes thanks to @ceilingcat

```
i;j;k;t;r;s;f(x,n)int*x;{for(t=i=k=r=0;i<n;)t+=x[i++];for(;++k<n;i=n)for(;i--;r|=2*s==t)for(s=0,j=i;j<i+k;)s+=x[j++%n];return r;}

```

**Ungolfed** try online

```
int f(int*x,int n)
{
    int t=0;

    for(int i=0;i<n;i++)
    {
        t += x[i];
    }

    for(int k=1;k<n;k++) // subset-size
    {
        for(int i=0,s;i<n;i++) // where to start
        {
            s=0;

            for(int j=i;j<i+k;j++) // sum the subset
            {
                s+=x[j%n];
            }

            if(2*s==t) return 1; // TRUE
        }
    }

    return 0; // FALSE
}

```
> 1 votes

# Answer
# Haskell, 68 bytes

```
f l|x<-[0..length l]=any(sum l==)[2*(sum$take a$drop b l)|a<-x,b<-x]

```

The function `f` first creates a list of the sums of all the possible slices of the given list. Then it compares to the total sum of list elements. If we get at some point half of the total sum, then we know that we've got a bisection. I'm also using the fact that if you `take` or `drop` more elements than there are in the list, Haskell does not throw an error.
> 1 votes

# Answer
# APL, 25 chars

~~Assuming the list is given in `X ← 1 2 3 4`.~~

```
(+/X)∊∘.{2×+/⍺↑⍵↓X,X}⍨⍳⍴X←⎕

```

## Explanation:

First note that APL evaluates form right to left. Then:

* `X←⎕` takes the user input and stores it in `X`
* `⍴X` gives the length of `X`
* `⍳⍴X` the numbers from 1 to `⍴X`
* The  and  in `{2×+/⍺↑⍵↓X,X}` are the left and right argument to a dyadic function we are defining inside the braces.

+ Now for the `⍺↑⍵↓X,X` part: `X,X` just concatenates X with itself;  and  are take and drop.
    + `+/` reduces/folds `+` over the list on its right

So `2 {2×+/⍺↑⍵↓X,X} 1` = `2×+/2↑1↓X,X` = `2×+/2↑1↓1 2 3 4 1 2 3 4` =

= `2×+/2↑2 3 4 1 2 3 4` = `2×+/2 3` = `2×5` = `10`.
* `∘.brace⍨idx` is just `idx ∘.brace idx`. ( is the diagonal map; `∘.` is the outer product)

So this gives us a `⍴X` by `⍴X` matrix which contains twice the sums of all connected sublists.

```
 4  6  8  2
10 14 10  6
18 16 14 12
20 20 20 20

```

The last thing we have to do is to check if the sum of `X` is somewhere inside this matrix.
* Which we do with `(+/X)∊matrix`.
> 1 votes

# Answer
# Brachylog, 6 bytes

```
sj+~+?

```

Try it online!

Outputs through success or failure, printing `true.` or `false.` if run as a program.

```
s         A contiguous sublist of the input
 j        with all of its items duplicated
  +       sums to
   ~+     the sum of the elements of
     ?    the input.

```
> 1 votes

# Answer
## Mathematica, 48 bytes

```
!FreeQ[Outer[Plus,#,-#],Last@#/2]&@Accumulate@#&

```

Anonymous function, similar in action to the numerous other answers.

`Outer[Plus, #, -#]`, when acting on `Accumulate@#` (which in turn acts on the input list, giving a list of successive totals) generates essentially the same table, as at the bottom of Leaky Nun's answer.

`!FreeQ[..., Last@#/2]` checks if `(Last@#)/2` is *not* absent from the resulting table, and `Last@#` is the last of the successive totals, i.e. the sum of all elements of the input list.

If this answer is somewhat interesting, it is not because of a new algorithm, but more about the tricks specific to Mathematica; e.g. `!FreeQ` is nice, compared to `MemberQ`, since it does not require a flattening of the table it checks *and* it saves a byte.
> 0 votes

# Answer
# APL(NARS), chars 95, bytes 190

```
{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}

```

Consider one array of input of 4 elements: 1 2 3 4. How we can choose the useful for this exercise partition of that set? Afther some think the partition of these 4 elements we can use are descrived in the binary number on the left:

```
0001,0010,0100,1000 2^(0..4) 1 2 4  8
0011,0110,1100,                3 6 12
0111,1110,                       7 14
1111                               15

```

(1001 or 1011 ecc could be in that set but already we have 0110 and 0100 ecc) so one hat just to write one function that from the number of element of the input array build these binary numbers... it would be:

```
c←{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}

```

that from input 1 2 4 8 \[2^0..lenBytesArgument-1\] find 3 6 12, 7 14, 15; so find binary of these numbers and using them find the right partitions of the input array...I tested c function only for that input 4 elements, but seems it is ok for other number of elements...

test:

```
  f←{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}
  f¨(1 2 3 4)(6 6 12 12 12 11 1 12)(1000000 1000001 1)(1 2 3)(1 1)(42 42)
1 1 1 1 1 1
  f¨(1 2 3 4 5)(2 1 3 4)(,10)(1000000 1000001)(,1)(1 2)(3 1 1)
0 0 0 0 0 0 0

```
> 0 votes

---
Tags: code-golf, math, arithmetic, combinatorics, decision-problem
---


title: The Computer Thief

text:
# Question
Title: The Computer Thief
You wake up and find out that your computer has been stolen! You have a few sensors and scanners, but unfortunately, the footage is incomplete, so you want to find and rank your suspects for further investigation.

Your computer is a rectangle, and your camera caught a bunch of people walking around with packages; however, there's a gift shop near your house so you can't be sure (and the camera footage doesn't seem to show if anyone went into your house). Based on that information, you want to determine who most likely stole your computer.

## Challenge

You will be given the dimensions of your computer and a list of (rectangular) gifts at the store by their dimensions. You will also be given a list of packages that people are holding as rectangle dimensions.

You are then to rank them by suspicion. A gift is said to fit in a package if its width and height are less than or equal to the package's width and height respectively, or height and width respectively. That is, basically whether or not it is a smaller rectangle, but with right-angle rotations allowed. If someone's package cannot fit your computer, then they have absolutely **no suspicion**. Otherwise, the more gifts they can fit, the less suspicious (basically, if they're carrying a larger package, it's more likely that they are just carrying a large gift rather than your computer).

(A formal way to describe this I guess would be: given a rectangle A, a list of rectangles B, and a list of rectangles C, sort C in increasing order of how many rectangles in B fit in each item, or infinity if A cannot fit in it, sort it to the end; then, group equal elements)

## Input

The input needs to contain the dimensions of your computer, the dimensions of all of the gifts, and the dimensions of each person's package. You can take these in any reasonable format.

Out of all gifts and your computer, no two items will have the same dimensions. No two people will have the same package dimensions. Both of these conditions are true even with rotation (so, no 2x3 and 3x2 gifts).

## Output

The output should be a two-dimensional list, where each sub-list contains people with the same suspicion level (order does not matter within a sub-list), and the sub-lists are sorted by suspicion level either up or down. You can output this in any reasonable format; as a 2D list, lines of lists, lines of space-separated values, etc.

You may either represent a person by their package dimensions (in either order, because it's unique), or by their index in the input list (you can choose any n-indexing).

You may either output all totally unsuspicious people as the last sublist or exclude them entirely (must be consistent). You may not have any empty sublists.

## Worked Example

Let your computer have dimensions `[3, 5]`. Let the gifts have dimensions `[2, 4], [2, 5], [3, 4], [3, 6], [4, 5], [4, 6]`. Let the people have packages of dimensions `[2, 4], [3, 5], [4, 6], [2, 7], [3, 6], [4, 5]`.

First, let's see who isn't suspicious. `[2, 4]` and `[2, 7]` cannot fit `[3, 5]` because the width is too small (`2 < min(3, 5)`).

Next, let's count.

`[3, 5]` can fit `[2, 4], [2, 5], [3, 4], [3, 5]`. Thus, their suspicion is 4 (3 gifts plus your computer), which turns out to be the most suspicious.

`[3, 6]` can fit `[2, 4], [2, 5], [3, 4], [3, 5], [3, 6]`, so their suspicion is 5. `[4, 5]` can fit `[2, 4], [2, 5], [3, 4], [3, 5], [4, 5]`, so their suspicion is also 5.

`[4, 7]` can fit `[2, 4], [2, 5], [3, 4], [3, 5], [3, 6], [4, 5], [4, 6]`, so their suspicion is 7. Since they could be carrying any of the gifts, they are the least suspicious.

Thus, a valid output would be `[[1], [4, 5], [2], [0, 3]]` (including the non-suspicious people in at the end in a sublist, in 0-indexing).

A reference implementation is provided here. The input contains three sections; the first is the computer, the second is the gifts, and the third is the packages. The output contains a brief explanation of each suspicion level, and at the end, it provides four valid output formats. These are not the only valid ones, but they would be valid.

## Rules and Specifications

* No dimensions will be smaller than 1, and all dimensions are integers. There may be no people or no gifts.
* You may demand the dimensions to be inputted in any order. Since the orientation does not matter anywhere in this challenge, you can choose any reasonable and consistent way of inputting these two numbers.
* Standard loopholes apply, as always.
* Since your computer was stolen, you'll need to write and run your code by hand. Since shorter code runs faster obviously1, and you need to do it manualy, you need to make your code as short as possible. Thus, the shortest code in bytes wins (this is a challenge).

1this is a joke

# Answer
> 5 votes
# Python 2, ~~143~~ ~~120~~ 119 bytes

-20 bytes by assuming the smaller dimension is always given first.
-1 bytes thanks to dingledooper!

Takes input as `computer, gifts, packages` from *STDIN*. Outputs as a list of of lists of package dimensions in descending suspicion levels. Does not include unsuspicious packages.

```
c,g,p=input()
r=[[]for _ in g+p]
for y in p:A,B=y;x=[a-A<1>b-B for a,b in[c]+g];r[sum(x)]+=[y]*x[0]
print filter(len,r)

```

Try it online!

# Answer
> 4 votes
# JavaScript (ES2021), 113 bytes

```
(d,g,p)=>p.map(([W,H],i)=>(o[-[d,...g].map(([w,h])=>t+=w>W|h>H&&h>W|w>H,t=0)[0]|t]??=[]).push(i),o=[])&&o.flat(0)

```

No TIO available.

https://jsfiddle.net/2s9xobkd/

Based on Arnauld‘s solution.

# Answer
> 3 votes
# JavaScript (Node.js),~~269~~ ~~252~~ 248 bytes

```
([x,y],p,g)=>[...(h=p.map(([X,Y],i)=>[i,(X>Y?Y:X)<(x>y?y:x)||g.map(([W,H])=>t+=(X>W|Y>H)&(Y>W|X>H),t=1)&&t]).sort((a,b)=>a[1]-b[1]).reduce((r,a,i)=>i&&a[1]==(I=r[r.length-1])[0][1]?(I.push(a),r):[...r,[a]],[]).map(x=>x.map(y=>y[0]))).slice(1),h[0]]

```

Very slightly less messy.

Try it online!

# Answer
> 3 votes
# JavaScript (ES10),  ~~129~~  124 bytes

*-5 bytes by swithing to ES10 and using `.flat(0)`, as suggested by @tsh*

Expects `([computer_w, computer_h], gifts, packages)`.

```
(d,g,p)=>p.map(([W,H],i)=>(o[g.map(y=>t+=3*(F=([w,h])=>w>W|h>H&&h>W|w>H)(d)|!F(y),t=0)|t]=o[t]||[]).push(i),o=[])&&o.flat(0)

```

Try it online!

### How?

For each package with dimensions \\$(W,H)\\$ and for each gift with dimensions \\$(w,h)\\$ among \\$N\\$ distinct gifts:

* we add 3 points to the package score if it can't fit the computer
* we add 1 point to the package score if it can fit both the computer and the gift
* we don't add any point to the package score if it can fit the computer but not the gift

So the score of a package that can't fit the computer is always \\$3N\\$ and the score of a package that can fit it is in \\$\[0\dots N\]\\$.

Higher scores are less suspicious.

# Answer
> 3 votes
# , 36 bytes

Takes `packages` as left argument and `computer, gifts` as right argument:

```
[(</.~/:~.@])[:({."1%~1#.])*/@:>:"1/

```

Try it online!

### How it works

* `*/@:>:"1/` a table of "can package fit computer/gift?"
* `1#.]` sum columns: the numbers of computer/gifts a package can fit
* `{."1%~` divided by 0 iff the package cannot fit the computer, otherwise divided by 1. So unsuspicious people get a score of infinity, because that's how division works. :-)
* `</.~` group the people by their scores
* `~.@]` the unique scores
* `/:` order the groups by the unique scores, lower scores first

# Answer
> 3 votes
# Jelly, 10 bytes

```
>Ẹ¥þ-SḢ?€Ġ

```

Try it online!

A dyadic link taking the computer and gifts as a single list `[computer, gift, gift, …]` as the left argument and the packages as the right argument. Returns a list of sublists in in increasing order of suspicion starting with those who are not suspicious at all. Like Jelly does normally, this uses 1-indexing.

## Explanation

```
  ¥þ       | For each pairing of computer/gift and package:
>          | - Greater than (vectorises)
 Ẹ         | - Any
      Ḣ?€  | For each package, is the head (i.e. computer) too big?
    -      | - If yes, -1
     S     | - If no, the sum of the remaining gifts that don’t fit
         Ġ | Group indices by their values in ascending order

```

# Answer
> 2 votes
# , ~~84~~ 81 bytes

```
function(i,j)split(seq(a=x<-apply(j,2,function(a,s=!colSums(a<i))sum(s/s[1]))),x)

```

Try it online!

Takes input as two matrices: \\$i\\$ holds items (computer dimensions in the first column, gift dimensions in subsequent columns), \\$j\\$ holds package dimensions.

Output is a list (from most suspicious to non-suspicious) with 1-indexed people IDs.

Thanks for -3 bytes to Nick Kennedy.

# Answer
> 1 votes
# Charcoal, 46 bytes

```
≔Ｅζ∨±∨›⌊θ⌊ι›⌈θ⌈ιＬΦη∨›⌊λ⌊ι›⌈λ⌈ιεＷ⁻ευ⊞υ⌈ιＩＥυ⌕Ａει

```

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

```
≔Ｅζ∨±∨›⌊θ⌊ι›⌈θ⌈ιＬΦη∨›⌊λ⌊ι›⌈λ⌈ιε

```

For each package, count the number of gifts that don't fit in the package, or -1 if the computer doesn't fit in the package.

```
Ｗ⁻ευ⊞υ⌈ι

```

Sort in descending order of the numbers of gifts that don't fit.

```
ＩＥυ⌕Ａει

```

Output the indices of packages grouped by the numbers of gifts that don't fit.

# Answer
> 1 votes
# Core Maude, ~~594~~ ~~571~~ 472 bytes

```
in linear
mod C is inc LIST{Set{IndexPair}}*(sort IndexPair to D). vars A B C : D
. vars N M P Q : Nat . vars S T U X Y :[D]. op p : D D D ~> D . op f : D D D
~> Nat . eq X empty = X . ceq p(A,S,X(B,C,T)Y)= p(A,S,X(B,T)C Y)if f(C,A,S)>
f(B,A,S). ceq p(A,S,X(B,T)(C,U)Y)= p(A,S,X T(B,C,U)Y)if f(B,A,S)>= f(C,A,S). eq
p(A,S,X)= X[owise]. ceq f((N,M),A,((P,Q),S))= s f((N,M),A,S)if N >= P /\ M >=
Q . eq f((N,M),(P,Q),S)= if N < P or M < Q then s | S | else 0 fi[owise]. endm

```

### Example Session

```
Maude> red p(
>     (3, 5),
>     ((2, 4), (2, 5), (3, 4), (3, 6), (4, 5), (4, 6)),
>     ((2, 4), (3, 5), (4, 6), (2, 7), (3, 6), (4, 5))
> ) .
Advisory: <standard input>, line 7 (mod C): collapse at top of X empty may
    cause it to match more than you expect.
result NeList{Set{IndexPair}}: (3,5) (3,6, 4,5) (4,6) (2,4, 2,7)

```

### Ungolfed

```
in linear

mod C is
    inc LIST{Set{IndexPair}} * (
        sort IndexPair to D
    ) .

    vars A B C : D .
    vars N M P Q : Nat .
    vars S T U X Y : [D] .

    op p : D D D ~> D .
    op f : D D D ~> Nat .

    eq X empty = X .

    ceq p(A, S, X (B, C, T) Y) = p(A, S, X (B, T) C Y) if f(C, A, S) > f(B, A, S) .
    ceq p(A, S, X (B, T) (C, U) Y) = p(A, S, X T (B, C, U) Y) if f(B, A, S) >= f(C, A, S) .
    eq p(A, S, X) = X [owise] .

    ceq f((N, M), A, ((P, Q), S)) = s f((N, M), A, S) if N >= P /\ M >= Q .
    eq f((N, M), (P, Q), S) = if N < P or M < Q then s | S | else 0 fi [owise] .
endm

```

This program accepts input as a three-argument function `p`:

1. The dimensions of the computer
2. The set of dimensions of the gifts
3. The set of dimensions of the people's packages

All dimensions must be given smaller side first as comma-separated pairs. The second and third arguments must be comma-separated sets of dimensions (since order doesn't matter and there are guaranteed no repeats).

The output format is list of sets. Each set represents a group of the packages at that "suspicion level". I chose output the dimensions rather than the indexes because Maude doesn't have a reasonable indexed array module.

---

**Edit.** Completely rewritten to save 23 bytes.

Saved 99 bytes by replacing the bespoke dimension module `D` with `IndexPair` from the `linear.maude` standard library.

# Answer
> -1 votes
# Haskell, 86 bytes

```
(n#p)c g=filter(>[])[[j|j<-p,c?j,sum[1|k<-g,k?j]==i]|i<-[0..n]]
[x,y]?[z,w]=x<=z&&y<=w

```

Try it online!

The relevant function is `(#)`, which takes as input the number of packages `n` and the list of packages `p`, the computer `c` and the list of gifts `g`. It returns a list of groups of packages, sorted from the most suspicious group to the least suspicious group. Each box/item is represented as a list `[w,h]`, with `w<=h`.

---
Tags: code-golf, array
---