up vote
17
down vote

favorite

We define $V(x)$ as the list of distinct powers of $2$ that sum to $x$. For instance, $V(35)=[32,2,1]$.

By convention, powers are sorted here from highest to lowest. But it does not affect the logic of the challenge, nor the expected solutions.

Task

Given a semiprime $N$, replace each term in $V(N)$ with another list of powers of $2$ that sum to this term, in such a way that the union of all resulting sub-lists is an exact cover of the matrix $M$ defined as:

$$M_i,j=V(P)_i times V(Q)_j$$

where $P$ and $Q$ are the prime factors of $N$.

This is much easier to understand with some examples.

Example #1

For $N=21$, we have:

$V(N)=[16,4,1]$

$P=7$ and $V(P)=[4,2,1]$

$Q=3$ and $V(Q)=[2,1]$

$M=pmatrix8&4&2\4&2&1$

To turn $V(N)$ into an exact cover of $M$, we may split $16$ into $8+4+4$ and $4$ into $2+2$, while $1$ is left unchanged. So a possible output is:

$$[ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]$$

Another valid output is:

$$[ [ 8, 4, 2, 2 ], [ 4 ], [ 1 ] ]$$

Example #2

For $N=851$, we have:

$V(N)=[512,256,64,16,2,1]$

$P=37$ and $V(P)=[32,4,1]$

$Q=23$ and $V(Q)=[16,4,2,1]$

$M=pmatrix512&64&16\128&16&4\64&8&2\32&4&1$

A possible output is:

$$[ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]$$

Rules

Because factorizing $N$ is not the main part of the challenge, you may alternately take $P$ and $Q$ as input.

When several possible solutions exist, you may either return just one of them or all of them.

You may alternately return the exponents of the powers (e.g. $[[3,2,2],[1,1],[0]]$ instead of $[[8,4,4],[2,2],[1]]$).

The order of the sub-lists doesn't matter, nor does the order of the terms in each sub-list.

For some semiprimes, you won't have to split any term because $V(N)$ already is a perfect cover of $M$ (see A235040). But you still have to return a list of (singleton) lists such as $[[8],[4],[2],[1]]$ for $N=15$.

This is code-golf!

Test cases

 Input | Possible output
-------+-----------------------------------------------------------------------------
 9 | [ [ 4, 2, 2 ], [ 1 ] ]
 15 | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 21 | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
 51 | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
 129 | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
 159 | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 161 | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
 201 | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
 403 | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 851 | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 2307 | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]

edited Aug 6 at 15:34

asked Aug 6 at 15:02

Arnauld

61.6k575258

can we take P and Q instead of N?
â€“Â ngn
Aug 6 at 15:29

@ngn I'm going to say yes, because factorizing N is not the main part of the challenge.
â€“Â Arnauld
Aug 6 at 15:33

1

May we return the output flattened?
â€“Â Erik the Outgolfer
Aug 6 at 19:06

@EriktheOutgolfer ... The output flattened is just a partition of the input (1+2+2+4=9, for example). I don't think it should be allowed
â€“Â Mr. Xcoder
Aug 6 at 19:08

@EriktheOutgolfer I don't think it could be unambiguous this way, as the last term of a sub-list may be the same as the first term of the next one.
â€“Â Arnauld
Aug 6 at 19:08

Â |Â
show 2 more comments

up vote
17
down vote

favorite

We define $V(x)$ as the list of distinct powers of $2$ that sum to $x$. For instance, $V(35)=[32,2,1]$.

By convention, powers are sorted here from highest to lowest. But it does not affect the logic of the challenge, nor the expected solutions.

Task

$$M_i,j=V(P)_i times V(Q)_j$$

where $P$ and $Q$ are the prime factors of $N$.

This is much easier to understand with some examples.

Example #1

For $N=21$, we have:

$V(N)=[16,4,1]$

$P=7$ and $V(P)=[4,2,1]$

$Q=3$ and $V(Q)=[2,1]$

$M=pmatrix8&4&2\4&2&1$

To turn $V(N)$ into an exact cover of $M$, we may split $16$ into $8+4+4$ and $4$ into $2+2$, while $1$ is left unchanged. So a possible output is:

$$[ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]$$

Another valid output is:

$$[ [ 8, 4, 2, 2 ], [ 4 ], [ 1 ] ]$$

Example #2

For $N=851$, we have:

$V(N)=[512,256,64,16,2,1]$

$P=37$ and $V(P)=[32,4,1]$

$Q=23$ and $V(Q)=[16,4,2,1]$

$M=pmatrix512&64&16\128&16&4\64&8&2\32&4&1$

A possible output is:

$$[ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]$$

Rules

Because factorizing $N$ is not the main part of the challenge, you may alternately take $P$ and $Q$ as input.

When several possible solutions exist, you may either return just one of them or all of them.

You may alternately return the exponents of the powers (e.g. $[[3,2,2],[1,1],[0]]$ instead of $[[8,4,4],[2,2],[1]]$).

The order of the sub-lists doesn't matter, nor does the order of the terms in each sub-list.

For some semiprimes, you won't have to split any term because $V(N)$ already is a perfect cover of $M$ (see A235040). But you still have to return a list of (singleton) lists such as $[[8],[4],[2],[1]]$ for $N=15$.

This is code-golf!

Test cases

 Input | Possible output
-------+-----------------------------------------------------------------------------
 9 | [ [ 4, 2, 2 ], [ 1 ] ]
 15 | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 21 | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
 51 | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
 129 | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
 159 | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 161 | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
 201 | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
 403 | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 851 | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 2307 | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]

edited Aug 6 at 15:34

asked Aug 6 at 15:02

Arnauld

61.6k575258

can we take P and Q instead of N?
â€“Â ngn
Aug 6 at 15:29

@ngn I'm going to say yes, because factorizing N is not the main part of the challenge.
â€“Â Arnauld
Aug 6 at 15:33

1

May we return the output flattened?
â€“Â Erik the Outgolfer
Aug 6 at 19:06

@EriktheOutgolfer ... The output flattened is just a partition of the input (1+2+2+4=9, for example). I don't think it should be allowed
â€“Â Mr. Xcoder
Aug 6 at 19:08

@EriktheOutgolfer I don't think it could be unambiguous this way, as the last term of a sub-list may be the same as the first term of the next one.
â€“Â Arnauld
Aug 6 at 19:08

Â |Â
show 2 more comments

up vote
17
down vote

favorite

We define $V(x)$ as the list of distinct powers of $2$ that sum to $x$. For instance, $V(35)=[32,2,1]$.

By convention, powers are sorted here from highest to lowest. But it does not affect the logic of the challenge, nor the expected solutions.

Task

$$M_i,j=V(P)_i times V(Q)_j$$

where $P$ and $Q$ are the prime factors of $N$.

This is much easier to understand with some examples.

Example #1

For $N=21$, we have:

$V(N)=[16,4,1]$

$P=7$ and $V(P)=[4,2,1]$

$Q=3$ and $V(Q)=[2,1]$

$M=pmatrix8&4&2\4&2&1$

To turn $V(N)$ into an exact cover of $M$, we may split $16$ into $8+4+4$ and $4$ into $2+2$, while $1$ is left unchanged. So a possible output is:

$$[ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]$$

Another valid output is:

$$[ [ 8, 4, 2, 2 ], [ 4 ], [ 1 ] ]$$

Example #2

For $N=851$, we have:

$V(N)=[512,256,64,16,2,1]$

$P=37$ and $V(P)=[32,4,1]$

$Q=23$ and $V(Q)=[16,4,2,1]$

$M=pmatrix512&64&16\128&16&4\64&8&2\32&4&1$

A possible output is:

$$[ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]$$

Rules

Because factorizing $N$ is not the main part of the challenge, you may alternately take $P$ and $Q$ as input.

When several possible solutions exist, you may either return just one of them or all of them.

You may alternately return the exponents of the powers (e.g. $[[3,2,2],[1,1],[0]]$ instead of $[[8,4,4],[2,2],[1]]$).

The order of the sub-lists doesn't matter, nor does the order of the terms in each sub-list.

For some semiprimes, you won't have to split any term because $V(N)$ already is a perfect cover of $M$ (see A235040). But you still have to return a list of (singleton) lists such as $[[8],[4],[2],[1]]$ for $N=15$.

This is code-golf!

Test cases

 Input | Possible output
-------+-----------------------------------------------------------------------------
 9 | [ [ 4, 2, 2 ], [ 1 ] ]
 15 | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 21 | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
 51 | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
 129 | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
 159 | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 161 | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
 201 | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
 403 | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 851 | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 2307 | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]

edited Aug 6 at 15:34

asked Aug 6 at 15:02

Arnauld

61.6k575258

We define $V(x)$ as the list of distinct powers of $2$ that sum to $x$. For instance, $V(35)=[32,2,1]$.

By convention, powers are sorted here from highest to lowest. But it does not affect the logic of the challenge, nor the expected solutions.

Task

$$M_i,j=V(P)_i times V(Q)_j$$

where $P$ and $Q$ are the prime factors of $N$.

This is much easier to understand with some examples.

Example #1

For $N=21$, we have:

$V(N)=[16,4,1]$

$P=7$ and $V(P)=[4,2,1]$

$Q=3$ and $V(Q)=[2,1]$

$M=pmatrix8&4&2\4&2&1$

To turn $V(N)$ into an exact cover of $M$, we may split $16$ into $8+4+4$ and $4$ into $2+2$, while $1$ is left unchanged. So a possible output is:

$$[ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]$$

Another valid output is:

$$[ [ 8, 4, 2, 2 ], [ 4 ], [ 1 ] ]$$

Example #2

For $N=851$, we have:

$V(N)=[512,256,64,16,2,1]$

$P=37$ and $V(P)=[32,4,1]$

$Q=23$ and $V(Q)=[16,4,2,1]$

$M=pmatrix512&64&16\128&16&4\64&8&2\32&4&1$

A possible output is:

$$[ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]$$

Rules

Because factorizing $N$ is not the main part of the challenge, you may alternately take $P$ and $Q$ as input.

When several possible solutions exist, you may either return just one of them or all of them.

You may alternately return the exponents of the powers (e.g. $[[3,2,2],[1,1],[0]]$ instead of $[[8,4,4],[2,2],[1]]$).

The order of the sub-lists doesn't matter, nor does the order of the terms in each sub-list.

For some semiprimes, you won't have to split any term because $V(N)$ already is a perfect cover of $M$ (see A235040). But you still have to return a list of (singleton) lists such as $[[8],[4],[2],[1]]$ for $N=15$.

This is code-golf!

Test cases

 Input | Possible output
-------+-----------------------------------------------------------------------------
 9 | [ [ 4, 2, 2 ], [ 1 ] ]
 15 | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 21 | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
 51 | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
 129 | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
 159 | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 161 | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
 201 | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
 403 | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 851 | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 2307 | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]

edited Aug 6 at 15:34

asked Aug 6 at 15:02

Arnauld

61.6k575258

edited Aug 6 at 15:34

asked Aug 6 at 15:02

Arnauld

61.6k575258

asked Aug 6 at 15:02

Arnauld

61.6k575258

asked Aug 6 at 15:02

Arnauld

61.6k575258

can we take P and Q instead of N?
â€“Â ngn
Aug 6 at 15:29

@ngn I'm going to say yes, because factorizing N is not the main part of the challenge.
â€“Â Arnauld
Aug 6 at 15:33

1

May we return the output flattened?
â€“Â Erik the Outgolfer
Aug 6 at 19:06

@EriktheOutgolfer ... The output flattened is just a partition of the input (1+2+2+4=9, for example). I don't think it should be allowed
â€“Â Mr. Xcoder
Aug 6 at 19:08

@EriktheOutgolfer I don't think it could be unambiguous this way, as the last term of a sub-list may be the same as the first term of the next one.
â€“Â Arnauld
Aug 6 at 19:08

Â |Â
show 2 more comments

can we take P and Q instead of N?
â€“Â ngn
Aug 6 at 15:29

@ngn I'm going to say yes, because factorizing N is not the main part of the challenge.
â€“Â Arnauld
Aug 6 at 15:33

1

May we return the output flattened?
â€“Â Erik the Outgolfer
Aug 6 at 19:06

@EriktheOutgolfer ... The output flattened is just a partition of the input (1+2+2+4=9, for example). I don't think it should be allowed
â€“Â Mr. Xcoder
Aug 6 at 19:08

@EriktheOutgolfer I don't think it could be unambiguous this way, as the last term of a sub-list may be the same as the first term of the next one.
â€“Â Arnauld
Aug 6 at 19:08

can we take P and Q instead of N?
â€“Â ngn
Aug 6 at 15:29

@ngn I'm going to say yes, because factorizing N is not the main part of the challenge.
â€“Â Arnauld
Aug 6 at 15:33

May we return the output flattened?
â€“Â Erik the Outgolfer
Aug 6 at 19:06

@EriktheOutgolfer ... The output flattened is just a partition of the input (1+2+2+4=9, for example). I don't think it should be allowed
â€“Â Mr. Xcoder
Aug 6 at 19:08

@EriktheOutgolfer I don't think it could be unambiguous this way, as the last term of a sub-list may be the same as the first term of the next one.
â€“Â Arnauld
Aug 6 at 19:08

Â |Â
show 2 more comments

7 Answers
7

active

oldest

votes

up vote
4
down vote

K (ngn/k), 66 63 bytes

a)?+b)_b:b@>b:,/*/:/2#a:*/'(&'x,*/x

Try it online!

accepts (P;Q) instead of N

algorithm:

compute A as the partial sums of V(P*Q)

multiply each V(P) with each V(Q), sort the products in descending order (let's call that R), and compute their partial sums B

find the positions of those elements in B that also occur in A; cut R right after those positions

edited Aug 6 at 18:39

answered Aug 6 at 15:51

ngn

6,59312154

add a commentÂ |Â

up vote
3
down vote

Jelly, 24 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢

A monadic link accepting a list of two integers [P, Q] which yields one possible list of lists as described in the question.

Try it online! (footer prints a string representation to show the list as it really is)

Or see the test-suite (taking a list of N and reordering results to be like those in the question)

How?

We may always slice up the elements of $M$ from lowest up, greedily (either there is a $1$ in $M$ or we had an input of $4$, when $M=[[4]]$) in order to find a solution.

^{Note: the code collects all (one!) such solutions in a list and then takes the head (only) result - i.e. the final head is necessary as the partitions are not of all possible orderings.}

BÃ¡Â¹ÂšTÃ¢Â€Â™2* - Link 1, powers of 2 that sum to N: integer, N e.g. 105
B - binary [1,1,0,1,0,0,1]
 Ã¡Â¹Âš - reverse [1,0,0,1,0,1,1]
 T - truthy indices [1,4,6,7]
 Ã¢Â€Â™ - decrement [0,3,5,6]
 2 - literal two 2
 * - exponentiate [1,8,32,64]

ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢ - Main Link: list of two integers, [P,Q]
ÃƒÂ‡Ã¢Â‚Â¬ - call last Link (1) as a monad for Ã¢Â‚Â¬ach
 / - reduce with:
 ÃƒÂ¾ - table with:
 ÃƒÂ— - multiplication
 F - flatten
 Ã¡Â¹Â¢ - sort
 Ã…Â’Ã¡Â¹Â– - all partitions
 Ã†Â‡ - filter keep if:
 Ã‰Â— - last three links as a dyad:
 Ã‚Â§ - sum each
 } - use right...
 P - ...value: product (i.e. PÃƒÂ—Q)
 ÃƒÂ‡ - ...do: call last Link (1) as a monad
 Ã¢ÂÂ¼ - equal? (non-vectorising so "all equal?")
 Ã¡Â¸Â¢ - head

answered Aug 7 at 0:28

Jonathan Allan

47k433157

add a commentÂ |Â

up vote
3
down vote

Python 2, 261 233 232 231 bytes

g=lambda n,r=,i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
 V=[[v]for v in g(p*q)];i=j=0
 for m in sorted(-a*b for a in g(p)for b in g(q)):
	v=V[i]
	while-m<v[j]:v[j:j+1]=[v[j]/2]*2
	i,j=[i+1,i,0,j+1][j+1<len(v)::2]
 return V

Try it online!

1 byte from Jo King; and another 1 byte due to Kevin Cruijssen.

Takes as input p,q. Pursues the greedy algorithm.

edited Aug 8 at 7:31

answered Aug 7 at 2:19

Chas Brown

3,855317

-k-1 can be ~k.
â€“Â Jonathan Frech
Aug 7 at 14:33

The i,j assignment can be i,j=[i+1,i,0,j+1][j+1<len(v)::2] for -1 byte
â€“Â Jo King
Aug 8 at 7:20

@Jo King: Hahaha! That is twisted!
â€“Â Chas Brown
Aug 8 at 7:24

while v[j]>-m can be while-m<v[j]
â€“Â Kevin Cruijssen
Aug 8 at 7:29

@Kevin Cruijssen: Yes, indeed. Thx!
â€“Â Chas Brown
Aug 8 at 7:32

add a commentÂ |Â

up vote
2
down vote

Jelly, 41 bytes

Ã…Â’Ã¡Â¹Â—l2Ã„ÂŠÃ†Â‘$Ã†Â‡
PÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃƒÂ‡Ã¢Â‚Â¬Ã…Â’pÃ‚ÂµÃ‚Â³ÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃ†ÂŠÃ¢Â‚Â¬Ã…Â’pZPÃ¡Â¹Â¢Ã¢ÂÂ¼FÃ¡Â¹Â¢$Ã‚ÂµÃ†Â‡

Try it online!

Should probably be much shorter (some parts feel very repetitive; especially ÃƒÂ‡IP$Ã†Â‡, but I don't know how to golf it). Explanation to come after further golfing. Returns all possible solutions in case multiple exist and takes input as $[P, Q]$.

edited Aug 6 at 18:39

answered Aug 6 at 18:31

Mr. Xcoder

29.4k756192

Not that it is a problem, but it's not exactly fast, is it? :)
â€“Â Arnauld
Aug 6 at 18:59

@Arnauld It uses roughly 3 integer partition functions in a single run :) Of course it is not too fast
â€“Â Mr. Xcoder
Aug 6 at 19:04

Now waiting to be outgolfed. I think it's possible in sub-35/30, but I don't think I'll be able to do anything much shorter
â€“Â Mr. Xcoder
Aug 6 at 19:15

add a commentÂ |Â

up vote
2
down vote

Jelly, 34 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
PÃƒÂ‡Ã…Â’Ã¡Â¹Â—ÃƒÂ¦Ã¡Â¸ÂŸ2Ã¢ÂÂ¼Ã†ÂŠÃ†Â‡Ã¢Â‚Â¬Ã…Â’pÃ¡ÂºÂŽÃ¡Â¹Â¢Ã¢ÂÂ¼Ã¡Â¹Â¢}ÃŠÂ‹Ã†Â‡ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/Ã¡ÂºÂŽÃ†ÂŠ

Try it online!

Input format: [P, Q] (the TIO link above doesn't accept this, but a single number instead, to aid with the test cases).

Output format: List of all solutions (shown as grid representation of 3D list over TIO).

Speed: Turtle.

answered Aug 6 at 19:17

Erik the Outgolfer

29.2k42697

add a commentÂ |Â

up vote
1
down vote

Pyth, 27 bytes

Inspired by Jonathan Allan's crushing of my Jelly solution. Takes $N$ as input.

L^2x1jb2;hfqyQsMT./S*M*FyMP

Try it here!

edited Aug 7 at 14:21

answered Aug 7 at 14:11

Mr. Xcoder

29.4k756192

add a commentÂ |Â

up vote
1
down vote

Haskell, 281 195 bytes

import Data.List
r=reverse.sort
n#0=
n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=
m!x=m!!0:tail m!(x-m!!0)
m%=
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))

edited Aug 8 at 7:00

answered Aug 7 at 20:32

ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²

822116

1

Here are some tips: Defining operators instead of binary functions is cheaper, rearranging guards and pattern-matching can save you (==), use 1>0 instead of True and don't use where. Also n' can be shortened.. With this you can save 72 bytes: Try it online!
â€“Â BWO
Aug 7 at 21:21

Btw. you should check out the Haskell tips section if you havent.
â€“Â BWO
Aug 7 at 21:22

I had a look at the guard situation again, another 13 bytes off: Try it online!
â€“Â BWO
Aug 7 at 23:15

@OMÃ¡Â—Âº, thank you. I'm new to haskell, so this looks for me as magic tricks
â€“Â ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²
Aug 8 at 7:01

No worries :) In case you have questions, feel free to ask in Of Monads and Men.
â€“Â BWO
Aug 8 at 12:15

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f170077%2fsplit-the-bits%23new-answer', 'question_page');

);

Post as a guest

Name

7 Answers
7

active

oldest

votes

7 Answers
7

active

oldest

votes

up vote
4
down vote

K (ngn/k), 66 63 bytes

a)?+b)_b:b@>b:,/*/:/2#a:*/'(&'x,*/x

Try it online!

accepts (P;Q) instead of N

algorithm:

compute A as the partial sums of V(P*Q)

multiply each V(P) with each V(Q), sort the products in descending order (let's call that R), and compute their partial sums B

find the positions of those elements in B that also occur in A; cut R right after those positions

edited Aug 6 at 18:39

answered Aug 6 at 15:51

ngn

6,59312154

add a commentÂ |Â

up vote
4
down vote

K (ngn/k), 66 63 bytes

a)?+b)_b:b@>b:,/*/:/2#a:*/'(&'x,*/x

Try it online!

accepts (P;Q) instead of N

algorithm:

compute A as the partial sums of V(P*Q)

multiply each V(P) with each V(Q), sort the products in descending order (let's call that R), and compute their partial sums B

find the positions of those elements in B that also occur in A; cut R right after those positions

edited Aug 6 at 18:39

answered Aug 6 at 15:51

ngn

6,59312154

add a commentÂ |Â

up vote
4
down vote

K (ngn/k), 66 63 bytes

a)?+b)_b:b@>b:,/*/:/2#a:*/'(&'x,*/x

Try it online!

accepts (P;Q) instead of N

algorithm:

compute A as the partial sums of V(P*Q)

multiply each V(P) with each V(Q), sort the products in descending order (let's call that R), and compute their partial sums B

find the positions of those elements in B that also occur in A; cut R right after those positions

edited Aug 6 at 18:39

answered Aug 6 at 15:51

ngn

6,59312154

K (ngn/k), 66 63 bytes

a)?+b)_b:b@>b:,/*/:/2#a:*/'(&'x,*/x

Try it online!

accepts (P;Q) instead of N

algorithm:

compute A as the partial sums of V(P*Q)

multiply each V(P) with each V(Q), sort the products in descending order (let's call that R), and compute their partial sums B

find the positions of those elements in B that also occur in A; cut R right after those positions

edited Aug 6 at 18:39

answered Aug 6 at 15:51

ngn

6,59312154

edited Aug 6 at 18:39

answered Aug 6 at 15:51

ngn

6,59312154

answered Aug 6 at 15:51

ngn

6,59312154

answered Aug 6 at 15:51

ngn

6,59312154

add a commentÂ |Â

up vote
3
down vote

Jelly, 24 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢

A monadic link accepting a list of two integers [P, Q] which yields one possible list of lists as described in the question.

Try it online! (footer prints a string representation to show the list as it really is)

Or see the test-suite (taking a list of N and reordering results to be like those in the question)

How?

We may always slice up the elements of $M$ from lowest up, greedily (either there is a $1$ in $M$ or we had an input of $4$, when $M=[[4]]$) in order to find a solution.

^{Note: the code collects all (one!) such solutions in a list and then takes the head (only) result - i.e. the final head is necessary as the partitions are not of all possible orderings.}

BÃ¡Â¹ÂšTÃ¢Â€Â™2* - Link 1, powers of 2 that sum to N: integer, N e.g. 105
B - binary [1,1,0,1,0,0,1]
 Ã¡Â¹Âš - reverse [1,0,0,1,0,1,1]
 T - truthy indices [1,4,6,7]
 Ã¢Â€Â™ - decrement [0,3,5,6]
 2 - literal two 2
 * - exponentiate [1,8,32,64]

ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢ - Main Link: list of two integers, [P,Q]
ÃƒÂ‡Ã¢Â‚Â¬ - call last Link (1) as a monad for Ã¢Â‚Â¬ach
 / - reduce with:
 ÃƒÂ¾ - table with:
 ÃƒÂ— - multiplication
 F - flatten
 Ã¡Â¹Â¢ - sort
 Ã…Â’Ã¡Â¹Â– - all partitions
 Ã†Â‡ - filter keep if:
 Ã‰Â— - last three links as a dyad:
 Ã‚Â§ - sum each
 } - use right...
 P - ...value: product (i.e. PÃƒÂ—Q)
 ÃƒÂ‡ - ...do: call last Link (1) as a monad
 Ã¢ÂÂ¼ - equal? (non-vectorising so "all equal?")
 Ã¡Â¸Â¢ - head

answered Aug 7 at 0:28

Jonathan Allan

47k433157

add a commentÂ |Â

up vote
3
down vote

Jelly, 24 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢

A monadic link accepting a list of two integers [P, Q] which yields one possible list of lists as described in the question.

Try it online! (footer prints a string representation to show the list as it really is)

Or see the test-suite (taking a list of N and reordering results to be like those in the question)

How?

We may always slice up the elements of $M$ from lowest up, greedily (either there is a $1$ in $M$ or we had an input of $4$, when $M=[[4]]$) in order to find a solution.

^{Note: the code collects all (one!) such solutions in a list and then takes the head (only) result - i.e. the final head is necessary as the partitions are not of all possible orderings.}

BÃ¡Â¹ÂšTÃ¢Â€Â™2* - Link 1, powers of 2 that sum to N: integer, N e.g. 105
B - binary [1,1,0,1,0,0,1]
 Ã¡Â¹Âš - reverse [1,0,0,1,0,1,1]
 T - truthy indices [1,4,6,7]
 Ã¢Â€Â™ - decrement [0,3,5,6]
 2 - literal two 2
 * - exponentiate [1,8,32,64]

ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢ - Main Link: list of two integers, [P,Q]
ÃƒÂ‡Ã¢Â‚Â¬ - call last Link (1) as a monad for Ã¢Â‚Â¬ach
 / - reduce with:
 ÃƒÂ¾ - table with:
 ÃƒÂ— - multiplication
 F - flatten
 Ã¡Â¹Â¢ - sort
 Ã…Â’Ã¡Â¹Â– - all partitions
 Ã†Â‡ - filter keep if:
 Ã‰Â— - last three links as a dyad:
 Ã‚Â§ - sum each
 } - use right...
 P - ...value: product (i.e. PÃƒÂ—Q)
 ÃƒÂ‡ - ...do: call last Link (1) as a monad
 Ã¢ÂÂ¼ - equal? (non-vectorising so "all equal?")
 Ã¡Â¸Â¢ - head

answered Aug 7 at 0:28

Jonathan Allan

47k433157

add a commentÂ |Â

up vote
3
down vote

Jelly, 24 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢

A monadic link accepting a list of two integers [P, Q] which yields one possible list of lists as described in the question.

Try it online! (footer prints a string representation to show the list as it really is)

Or see the test-suite (taking a list of N and reordering results to be like those in the question)

How?

We may always slice up the elements of $M$ from lowest up, greedily (either there is a $1$ in $M$ or we had an input of $4$, when $M=[[4]]$) in order to find a solution.

^{Note: the code collects all (one!) such solutions in a list and then takes the head (only) result - i.e. the final head is necessary as the partitions are not of all possible orderings.}

BÃ¡Â¹ÂšTÃ¢Â€Â™2* - Link 1, powers of 2 that sum to N: integer, N e.g. 105
B - binary [1,1,0,1,0,0,1]
 Ã¡Â¹Âš - reverse [1,0,0,1,0,1,1]
 T - truthy indices [1,4,6,7]
 Ã¢Â€Â™ - decrement [0,3,5,6]
 2 - literal two 2
 * - exponentiate [1,8,32,64]

ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢ - Main Link: list of two integers, [P,Q]
ÃƒÂ‡Ã¢Â‚Â¬ - call last Link (1) as a monad for Ã¢Â‚Â¬ach
 / - reduce with:
 ÃƒÂ¾ - table with:
 ÃƒÂ— - multiplication
 F - flatten
 Ã¡Â¹Â¢ - sort
 Ã…Â’Ã¡Â¹Â– - all partitions
 Ã†Â‡ - filter keep if:
 Ã‰Â— - last three links as a dyad:
 Ã‚Â§ - sum each
 } - use right...
 P - ...value: product (i.e. PÃƒÂ—Q)
 ÃƒÂ‡ - ...do: call last Link (1) as a monad
 Ã¢ÂÂ¼ - equal? (non-vectorising so "all equal?")
 Ã¡Â¸Â¢ - head

answered Aug 7 at 0:28

Jonathan Allan

47k433157

Jelly, 24 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢

A monadic link accepting a list of two integers [P, Q] which yields one possible list of lists as described in the question.

Try it online! (footer prints a string representation to show the list as it really is)

Or see the test-suite (taking a list of N and reordering results to be like those in the question)

How?

We may always slice up the elements of $M$ from lowest up, greedily (either there is a $1$ in $M$ or we had an input of $4$, when $M=[[4]]$) in order to find a solution.

^{Note: the code collects all (one!) such solutions in a list and then takes the head (only) result - i.e. the final head is necessary as the partitions are not of all possible orderings.}

BÃ¡Â¹ÂšTÃ¢Â€Â™2* - Link 1, powers of 2 that sum to N: integer, N e.g. 105
B - binary [1,1,0,1,0,0,1]
 Ã¡Â¹Âš - reverse [1,0,0,1,0,1,1]
 T - truthy indices [1,4,6,7]
 Ã¢Â€Â™ - decrement [0,3,5,6]
 2 - literal two 2
 * - exponentiate [1,8,32,64]

ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/FÃ¡Â¹Â¢Ã…Â’Ã¡Â¹Â–Ã‚Â§Ã¢ÂÂ¼ÃƒÂ‡}Ã‰Â—Ã†Â‡PÃ¡Â¸Â¢ - Main Link: list of two integers, [P,Q]
ÃƒÂ‡Ã¢Â‚Â¬ - call last Link (1) as a monad for Ã¢Â‚Â¬ach
 / - reduce with:
 ÃƒÂ¾ - table with:
 ÃƒÂ— - multiplication
 F - flatten
 Ã¡Â¹Â¢ - sort
 Ã…Â’Ã¡Â¹Â– - all partitions
 Ã†Â‡ - filter keep if:
 Ã‰Â— - last three links as a dyad:
 Ã‚Â§ - sum each
 } - use right...
 P - ...value: product (i.e. PÃƒÂ—Q)
 ÃƒÂ‡ - ...do: call last Link (1) as a monad
 Ã¢ÂÂ¼ - equal? (non-vectorising so "all equal?")
 Ã¡Â¸Â¢ - head

answered Aug 7 at 0:28

Jonathan Allan

47k433157

answered Aug 7 at 0:28

Jonathan Allan

47k433157

answered Aug 7 at 0:28

Jonathan Allan

47k433157

answered Aug 7 at 0:28

Jonathan Allan

47k433157

add a commentÂ |Â

up vote
3
down vote

Python 2, 261 233 232 231 bytes

g=lambda n,r=,i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
 V=[[v]for v in g(p*q)];i=j=0
 for m in sorted(-a*b for a in g(p)for b in g(q)):
	v=V[i]
	while-m<v[j]:v[j:j+1]=[v[j]/2]*2
	i,j=[i+1,i,0,j+1][j+1<len(v)::2]
 return V

Try it online!

1 byte from Jo King; and another 1 byte due to Kevin Cruijssen.

Takes as input p,q. Pursues the greedy algorithm.

edited Aug 8 at 7:31

answered Aug 7 at 2:19

Chas Brown

3,855317

-k-1 can be ~k.
â€“Â Jonathan Frech
Aug 7 at 14:33

The i,j assignment can be i,j=[i+1,i,0,j+1][j+1<len(v)::2] for -1 byte
â€“Â Jo King
Aug 8 at 7:20

@Jo King: Hahaha! That is twisted!
â€“Â Chas Brown
Aug 8 at 7:24

while v[j]>-m can be while-m<v[j]
â€“Â Kevin Cruijssen
Aug 8 at 7:29

@Kevin Cruijssen: Yes, indeed. Thx!
â€“Â Chas Brown
Aug 8 at 7:32

add a commentÂ |Â

up vote
3
down vote

Python 2, 261 233 232 231 bytes

g=lambda n,r=,i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
 V=[[v]for v in g(p*q)];i=j=0
 for m in sorted(-a*b for a in g(p)for b in g(q)):
	v=V[i]
	while-m<v[j]:v[j:j+1]=[v[j]/2]*2
	i,j=[i+1,i,0,j+1][j+1<len(v)::2]
 return V

Try it online!

1 byte from Jo King; and another 1 byte due to Kevin Cruijssen.

Takes as input p,q. Pursues the greedy algorithm.

edited Aug 8 at 7:31

answered Aug 7 at 2:19

Chas Brown

3,855317

-k-1 can be ~k.
â€“Â Jonathan Frech
Aug 7 at 14:33

The i,j assignment can be i,j=[i+1,i,0,j+1][j+1<len(v)::2] for -1 byte
â€“Â Jo King
Aug 8 at 7:20

@Jo King: Hahaha! That is twisted!
â€“Â Chas Brown
Aug 8 at 7:24

while v[j]>-m can be while-m<v[j]
â€“Â Kevin Cruijssen
Aug 8 at 7:29

@Kevin Cruijssen: Yes, indeed. Thx!
â€“Â Chas Brown
Aug 8 at 7:32

add a commentÂ |Â

up vote
3
down vote

Python 2, 261 233 232 231 bytes

g=lambda n,r=,i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
 V=[[v]for v in g(p*q)];i=j=0
 for m in sorted(-a*b for a in g(p)for b in g(q)):
	v=V[i]
	while-m<v[j]:v[j:j+1]=[v[j]/2]*2
	i,j=[i+1,i,0,j+1][j+1<len(v)::2]
 return V

Try it online!

1 byte from Jo King; and another 1 byte due to Kevin Cruijssen.

Takes as input p,q. Pursues the greedy algorithm.

edited Aug 8 at 7:31

answered Aug 7 at 2:19

Chas Brown

3,855317

Python 2, 261 233 232 231 bytes

g=lambda n,r=,i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
 V=[[v]for v in g(p*q)];i=j=0
 for m in sorted(-a*b for a in g(p)for b in g(q)):
	v=V[i]
	while-m<v[j]:v[j:j+1]=[v[j]/2]*2
	i,j=[i+1,i,0,j+1][j+1<len(v)::2]
 return V

Try it online!

1 byte from Jo King; and another 1 byte due to Kevin Cruijssen.

Takes as input p,q. Pursues the greedy algorithm.

edited Aug 8 at 7:31

answered Aug 7 at 2:19

Chas Brown

3,855317

edited Aug 8 at 7:31

answered Aug 7 at 2:19

Chas Brown

3,855317

answered Aug 7 at 2:19

Chas Brown

3,855317

answered Aug 7 at 2:19

Chas Brown

3,855317

-k-1 can be ~k.
â€“Â Jonathan Frech
Aug 7 at 14:33

The i,j assignment can be i,j=[i+1,i,0,j+1][j+1<len(v)::2] for -1 byte
â€“Â Jo King
Aug 8 at 7:20

@Jo King: Hahaha! That is twisted!
â€“Â Chas Brown
Aug 8 at 7:24

while v[j]>-m can be while-m<v[j]
â€“Â Kevin Cruijssen
Aug 8 at 7:29

@Kevin Cruijssen: Yes, indeed. Thx!
â€“Â Chas Brown
Aug 8 at 7:32

add a commentÂ |Â

-k-1 can be ~k.
â€“Â Jonathan Frech
Aug 7 at 14:33

The i,j assignment can be i,j=[i+1,i,0,j+1][j+1<len(v)::2] for -1 byte
â€“Â Jo King
Aug 8 at 7:20

@Jo King: Hahaha! That is twisted!
â€“Â Chas Brown
Aug 8 at 7:24

while v[j]>-m can be while-m<v[j]
â€“Â Kevin Cruijssen
Aug 8 at 7:29

@Kevin Cruijssen: Yes, indeed. Thx!
â€“Â Chas Brown
Aug 8 at 7:32

-k-1 can be ~k.
â€“Â Jonathan Frech
Aug 7 at 14:33

The i,j assignment can be i,j=[i+1,i,0,j+1][j+1<len(v)::2] for -1 byte
â€“Â Jo King
Aug 8 at 7:20

@Jo King: Hahaha! That is twisted!
â€“Â Chas Brown
Aug 8 at 7:24

while v[j]>-m can be while-m<v[j]
â€“Â Kevin Cruijssen
Aug 8 at 7:29

@Kevin Cruijssen: Yes, indeed. Thx!
â€“Â Chas Brown
Aug 8 at 7:32

add a commentÂ |Â

up vote
2
down vote

Jelly, 41 bytes

Ã…Â’Ã¡Â¹Â—l2Ã„ÂŠÃ†Â‘$Ã†Â‡
PÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃƒÂ‡Ã¢Â‚Â¬Ã…Â’pÃ‚ÂµÃ‚Â³ÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃ†ÂŠÃ¢Â‚Â¬Ã…Â’pZPÃ¡Â¹Â¢Ã¢ÂÂ¼FÃ¡Â¹Â¢$Ã‚ÂµÃ†Â‡

Try it online!

edited Aug 6 at 18:39

answered Aug 6 at 18:31

Mr. Xcoder

29.4k756192

Not that it is a problem, but it's not exactly fast, is it? :)
â€“Â Arnauld
Aug 6 at 18:59

@Arnauld It uses roughly 3 integer partition functions in a single run :) Of course it is not too fast
â€“Â Mr. Xcoder
Aug 6 at 19:04

Now waiting to be outgolfed. I think it's possible in sub-35/30, but I don't think I'll be able to do anything much shorter
â€“Â Mr. Xcoder
Aug 6 at 19:15

add a commentÂ |Â

up vote
2
down vote

Jelly, 41 bytes

Ã…Â’Ã¡Â¹Â—l2Ã„ÂŠÃ†Â‘$Ã†Â‡
PÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃƒÂ‡Ã¢Â‚Â¬Ã…Â’pÃ‚ÂµÃ‚Â³ÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃ†ÂŠÃ¢Â‚Â¬Ã…Â’pZPÃ¡Â¹Â¢Ã¢ÂÂ¼FÃ¡Â¹Â¢$Ã‚ÂµÃ†Â‡

Try it online!

edited Aug 6 at 18:39

answered Aug 6 at 18:31

Mr. Xcoder

29.4k756192

Not that it is a problem, but it's not exactly fast, is it? :)
â€“Â Arnauld
Aug 6 at 18:59

@Arnauld It uses roughly 3 integer partition functions in a single run :) Of course it is not too fast
â€“Â Mr. Xcoder
Aug 6 at 19:04

Now waiting to be outgolfed. I think it's possible in sub-35/30, but I don't think I'll be able to do anything much shorter
â€“Â Mr. Xcoder
Aug 6 at 19:15

add a commentÂ |Â

up vote
2
down vote

Jelly, 41 bytes

Ã…Â’Ã¡Â¹Â—l2Ã„ÂŠÃ†Â‘$Ã†Â‡
PÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃƒÂ‡Ã¢Â‚Â¬Ã…Â’pÃ‚ÂµÃ‚Â³ÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃ†ÂŠÃ¢Â‚Â¬Ã…Â’pZPÃ¡Â¹Â¢Ã¢ÂÂ¼FÃ¡Â¹Â¢$Ã‚ÂµÃ†Â‡

Try it online!

edited Aug 6 at 18:39

answered Aug 6 at 18:31

Mr. Xcoder

29.4k756192

Jelly, 41 bytes

Ã…Â’Ã¡Â¹Â—l2Ã„ÂŠÃ†Â‘$Ã†Â‡
PÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃƒÂ‡Ã¢Â‚Â¬Ã…Â’pÃ‚ÂµÃ‚Â³ÃƒÂ‡IP$Ã†Â‡Ã¡Â¹ÂªÃ†ÂŠÃ¢Â‚Â¬Ã…Â’pZPÃ¡Â¹Â¢Ã¢ÂÂ¼FÃ¡Â¹Â¢$Ã‚ÂµÃ†Â‡

Try it online!

edited Aug 6 at 18:39

answered Aug 6 at 18:31

Mr. Xcoder

29.4k756192

edited Aug 6 at 18:39

answered Aug 6 at 18:31

Mr. Xcoder

29.4k756192

answered Aug 6 at 18:31

Mr. Xcoder

29.4k756192

answered Aug 6 at 18:31

Mr. Xcoder

29.4k756192

Not that it is a problem, but it's not exactly fast, is it? :)
â€“Â Arnauld
Aug 6 at 18:59

@Arnauld It uses roughly 3 integer partition functions in a single run :) Of course it is not too fast
â€“Â Mr. Xcoder
Aug 6 at 19:04

Now waiting to be outgolfed. I think it's possible in sub-35/30, but I don't think I'll be able to do anything much shorter
â€“Â Mr. Xcoder
Aug 6 at 19:15

add a commentÂ |Â

Not that it is a problem, but it's not exactly fast, is it? :)
â€“Â Arnauld
Aug 6 at 18:59

@Arnauld It uses roughly 3 integer partition functions in a single run :) Of course it is not too fast
â€“Â Mr. Xcoder
Aug 6 at 19:04

Now waiting to be outgolfed. I think it's possible in sub-35/30, but I don't think I'll be able to do anything much shorter
â€“Â Mr. Xcoder
Aug 6 at 19:15

Not that it is a problem, but it's not exactly fast, is it? :)
â€“Â Arnauld
Aug 6 at 18:59

@Arnauld It uses roughly 3 integer partition functions in a single run :) Of course it is not too fast
â€“Â Mr. Xcoder
Aug 6 at 19:04

Now waiting to be outgolfed. I think it's possible in sub-35/30, but I don't think I'll be able to do anything much shorter
â€“Â Mr. Xcoder
Aug 6 at 19:15

add a commentÂ |Â

up vote
2
down vote

Jelly, 34 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
PÃƒÂ‡Ã…Â’Ã¡Â¹Â—ÃƒÂ¦Ã¡Â¸ÂŸ2Ã¢ÂÂ¼Ã†ÂŠÃ†Â‡Ã¢Â‚Â¬Ã…Â’pÃ¡ÂºÂŽÃ¡Â¹Â¢Ã¢ÂÂ¼Ã¡Â¹Â¢}ÃŠÂ‹Ã†Â‡ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/Ã¡ÂºÂŽÃ†ÂŠ

Try it online!

Input format: [P, Q] (the TIO link above doesn't accept this, but a single number instead, to aid with the test cases).

Output format: List of all solutions (shown as grid representation of 3D list over TIO).

Speed: Turtle.

answered Aug 6 at 19:17

Erik the Outgolfer

29.2k42697

add a commentÂ |Â

up vote
2
down vote

Jelly, 34 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
PÃƒÂ‡Ã…Â’Ã¡Â¹Â—ÃƒÂ¦Ã¡Â¸ÂŸ2Ã¢ÂÂ¼Ã†ÂŠÃ†Â‡Ã¢Â‚Â¬Ã…Â’pÃ¡ÂºÂŽÃ¡Â¹Â¢Ã¢ÂÂ¼Ã¡Â¹Â¢}ÃŠÂ‹Ã†Â‡ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/Ã¡ÂºÂŽÃ†ÂŠ

Try it online!

Input format: [P, Q] (the TIO link above doesn't accept this, but a single number instead, to aid with the test cases).

Output format: List of all solutions (shown as grid representation of 3D list over TIO).

Speed: Turtle.

answered Aug 6 at 19:17

Erik the Outgolfer

29.2k42697

add a commentÂ |Â

up vote
2
down vote

Jelly, 34 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
PÃƒÂ‡Ã…Â’Ã¡Â¹Â—ÃƒÂ¦Ã¡Â¸ÂŸ2Ã¢ÂÂ¼Ã†ÂŠÃ†Â‡Ã¢Â‚Â¬Ã…Â’pÃ¡ÂºÂŽÃ¡Â¹Â¢Ã¢ÂÂ¼Ã¡Â¹Â¢}ÃŠÂ‹Ã†Â‡ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/Ã¡ÂºÂŽÃ†ÂŠ

Try it online!

Input format: [P, Q] (the TIO link above doesn't accept this, but a single number instead, to aid with the test cases).

Output format: List of all solutions (shown as grid representation of 3D list over TIO).

Speed: Turtle.

answered Aug 6 at 19:17

Erik the Outgolfer

29.2k42697

Jelly, 34 bytes

BÃ¡Â¹ÂšTÃ¢Â€Â™2*
PÃƒÂ‡Ã…Â’Ã¡Â¹Â—ÃƒÂ¦Ã¡Â¸ÂŸ2Ã¢ÂÂ¼Ã†ÂŠÃ†Â‡Ã¢Â‚Â¬Ã…Â’pÃ¡ÂºÂŽÃ¡Â¹Â¢Ã¢ÂÂ¼Ã¡Â¹Â¢}ÃŠÂ‹Ã†Â‡ÃƒÂ‡Ã¢Â‚Â¬ÃƒÂ—ÃƒÂ¾/Ã¡ÂºÂŽÃ†ÂŠ

Try it online!

Input format: [P, Q] (the TIO link above doesn't accept this, but a single number instead, to aid with the test cases).

Output format: List of all solutions (shown as grid representation of 3D list over TIO).

Speed: Turtle.

answered Aug 6 at 19:17

Erik the Outgolfer

29.2k42697

answered Aug 6 at 19:17

Erik the Outgolfer

29.2k42697

answered Aug 6 at 19:17

Erik the Outgolfer

29.2k42697

answered Aug 6 at 19:17

Erik the Outgolfer

29.2k42697

add a commentÂ |Â

up vote
1
down vote

Pyth, 27 bytes

Inspired by Jonathan Allan's crushing of my Jelly solution. Takes $N$ as input.

L^2x1jb2;hfqyQsMT./S*M*FyMP

Try it here!

edited Aug 7 at 14:21

answered Aug 7 at 14:11

Mr. Xcoder

29.4k756192

add a commentÂ |Â

up vote
1
down vote

Pyth, 27 bytes

Inspired by Jonathan Allan's crushing of my Jelly solution. Takes $N$ as input.

L^2x1jb2;hfqyQsMT./S*M*FyMP

Try it here!

edited Aug 7 at 14:21

answered Aug 7 at 14:11

Mr. Xcoder

29.4k756192

add a commentÂ |Â

up vote
1
down vote

Pyth, 27 bytes

Inspired by Jonathan Allan's crushing of my Jelly solution. Takes $N$ as input.

L^2x1jb2;hfqyQsMT./S*M*FyMP

Try it here!

edited Aug 7 at 14:21

answered Aug 7 at 14:11

Mr. Xcoder

29.4k756192

Pyth, 27 bytes

Inspired by Jonathan Allan's crushing of my Jelly solution. Takes $N$ as input.

L^2x1jb2;hfqyQsMT./S*M*FyMP

Try it here!

edited Aug 7 at 14:21

answered Aug 7 at 14:11

Mr. Xcoder

29.4k756192

edited Aug 7 at 14:21

answered Aug 7 at 14:11

Mr. Xcoder

29.4k756192

answered Aug 7 at 14:11

Mr. Xcoder

29.4k756192

answered Aug 7 at 14:11

Mr. Xcoder

29.4k756192

add a commentÂ |Â

up vote
1
down vote

Haskell, 281 195 bytes

import Data.List
r=reverse.sort
n#0=
n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=
m!x=m!!0:tail m!(x-m!!0)
m%=
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))

edited Aug 8 at 7:00

answered Aug 7 at 20:32

ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²

822116

1

Here are some tips: Defining operators instead of binary functions is cheaper, rearranging guards and pattern-matching can save you (==), use 1>0 instead of True and don't use where. Also n' can be shortened.. With this you can save 72 bytes: Try it online!
â€“Â BWO
Aug 7 at 21:21

Btw. you should check out the Haskell tips section if you havent.
â€“Â BWO
Aug 7 at 21:22

I had a look at the guard situation again, another 13 bytes off: Try it online!
â€“Â BWO
Aug 7 at 23:15

@OMÃ¡Â—Âº, thank you. I'm new to haskell, so this looks for me as magic tricks
â€“Â ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²
Aug 8 at 7:01

No worries :) In case you have questions, feel free to ask in Of Monads and Men.
â€“Â BWO
Aug 8 at 12:15

add a commentÂ |Â

up vote
1
down vote

Haskell, 281 195 bytes

import Data.List
r=reverse.sort
n#0=
n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=
m!x=m!!0:tail m!(x-m!!0)
m%=
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))

edited Aug 8 at 7:00

answered Aug 7 at 20:32

ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²

822116

1

Here are some tips: Defining operators instead of binary functions is cheaper, rearranging guards and pattern-matching can save you (==), use 1>0 instead of True and don't use where. Also n' can be shortened.. With this you can save 72 bytes: Try it online!
â€“Â BWO
Aug 7 at 21:21

Btw. you should check out the Haskell tips section if you havent.
â€“Â BWO
Aug 7 at 21:22

I had a look at the guard situation again, another 13 bytes off: Try it online!
â€“Â BWO
Aug 7 at 23:15

@OMÃ¡Â—Âº, thank you. I'm new to haskell, so this looks for me as magic tricks
â€“Â ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²
Aug 8 at 7:01

No worries :) In case you have questions, feel free to ask in Of Monads and Men.
â€“Â BWO
Aug 8 at 12:15

add a commentÂ |Â

up vote
1
down vote

Haskell, 281 195 bytes

import Data.List
r=reverse.sort
n#0=
n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=
m!x=m!!0:tail m!(x-m!!0)
m%=
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))

edited Aug 8 at 7:00

answered Aug 7 at 20:32

ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²

822116

Haskell, 281 195 bytes

import Data.List
r=reverse.sort
n#0=
n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=
m!x=m!!0:tail m!(x-m!!0)
m%=
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))

edited Aug 8 at 7:00

answered Aug 7 at 20:32

ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²

822116

edited Aug 8 at 7:00

answered Aug 7 at 20:32

ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²

822116

answered Aug 7 at 20:32

ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²

822116

answered Aug 7 at 20:32

ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²

822116

1

Here are some tips: Defining operators instead of binary functions is cheaper, rearranging guards and pattern-matching can save you (==), use 1>0 instead of True and don't use where. Also n' can be shortened.. With this you can save 72 bytes: Try it online!
â€“Â BWO
Aug 7 at 21:21

Btw. you should check out the Haskell tips section if you havent.
â€“Â BWO
Aug 7 at 21:22

I had a look at the guard situation again, another 13 bytes off: Try it online!
â€“Â BWO
Aug 7 at 23:15

@OMÃ¡Â—Âº, thank you. I'm new to haskell, so this looks for me as magic tricks
â€“Â ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²
Aug 8 at 7:01

No worries :) In case you have questions, feel free to ask in Of Monads and Men.
â€“Â BWO
Aug 8 at 12:15

add a commentÂ |Â

1

Here are some tips: Defining operators instead of binary functions is cheaper, rearranging guards and pattern-matching can save you (==), use 1>0 instead of True and don't use where. Also n' can be shortened.. With this you can save 72 bytes: Try it online!
â€“Â BWO
Aug 7 at 21:21

Btw. you should check out the Haskell tips section if you havent.
â€“Â BWO
Aug 7 at 21:22

I had a look at the guard situation again, another 13 bytes off: Try it online!
â€“Â BWO
Aug 7 at 23:15

@OMÃ¡Â—Âº, thank you. I'm new to haskell, so this looks for me as magic tricks
â€“Â ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²
Aug 8 at 7:01

No worries :) In case you have questions, feel free to ask in Of Monads and Men.
â€“Â BWO
Aug 8 at 12:15

Here are some tips: Defining operators instead of binary functions is cheaper, rearranging guards and pattern-matching can save you (==), use 1>0 instead of True and don't use where. Also n' can be shortened.. With this you can save 72 bytes: Try it online!
â€“Â BWO
Aug 7 at 21:21

Btw. you should check out the Haskell tips section if you havent.
â€“Â BWO
Aug 7 at 21:22

I had a look at the guard situation again, another 13 bytes off: Try it online!
â€“Â BWO
Aug 7 at 23:15

@OMÃ¡Â—Âº, thank you. I'm new to haskell, so this looks for me as magic tricks
â€“Â ÃÂ•ÃÂ²ÃÂ³ÃÂµÃÂ½ÃÂ¸ÃÂ¹ ÃÂÃÂ¾ÃÂ²ÃÂ¸ÃÂºÃÂ¾ÃÂ²
Aug 8 at 7:01

No worries :) In case you have questions, feel free to ask in Of Monads and Men.
â€“Â BWO
Aug 8 at 12:15

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Category

Random preview

Split the bits!

Task

Example #1

Example #2

Rules

Test cases

Task

Example #1

Example #2

Rules

Test cases

Task

Example #1

Example #2

Rules

Test cases

Task

Example #1

Example #2

Rules

Test cases

7 Answers 7

K (ngn/k), 66 63 bytes

Jelly, 24 bytes

How?

Python 2, 261 233 232 231 bytes

Jelly, 41 bytes

Jelly, 34 bytes

Pyth, 27 bytes

Haskell, 281 195 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

7 Answers 7

7 Answers 7

K (ngn/k), 66 63 bytes

K (ngn/k), 66 63 bytes

K (ngn/k), 66 63 bytes

K (ngn/k), 66 63 bytes

Jelly, 24 bytes

How?

Jelly, 24 bytes

How?

Jelly, 24 bytes

How?

Jelly, 24 bytes

How?

Python 2, 261 233 232 231 bytes

Python 2, 261 233 232 231 bytes

Python 2, 261 233 232 231 bytes

Python 2, 261 233 232 231 bytes

Jelly, 41 bytes

Jelly, 41 bytes

Jelly, 41 bytes

Jelly, 41 bytes

Jelly, 34 bytes

Jelly, 34 bytes

Jelly, 34 bytes

Jelly, 34 bytes

Pyth, 27 bytes

Pyth, 27 bytes

Pyth, 27 bytes

Pyth, 27 bytes

Haskell, 281 195 bytes

Haskell, 281 195 bytes

Haskell, 281 195 bytes

Haskell, 281 195 bytes

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

7 Answers
7

7 Answers
7

7 Answers
7