6
\$\begingroup\$

Introduction

Classes have started! And so does the boredom. I decided to doodle in my notebook and started to draw some dots in (IMO) an aesthetically pleasing way. I came up with these numbers: Dot Numbers

based on these conditions:
Given (n, m)
1) There must be n dots
2) All dots must lie on an m by m lattice
3) The position of the dots must minimize the spread* from the top left corner
4) The configuration of the dots must be diagonally symmetric as pictured:
Symmetry Example

*Spread (in this context) is defined as the sum of the distances from the top left dot position (whether or not there is a dot there). For example, the spread of the example above is 0 + 1 + 2 + 1 + √2 + 2 + 2√2 = 6 + 3√2

The Challenge

Come up with an algorithm using that uses natural numbers n and m (where it will always be that n <= m^2) to generate a configuration of dots that follow all the rules above.

Input can be received via STDIN, command-line argument, or function parameter.

Output the pattern to STDOUT or return a string with newlines. Any two different characters may be used in the output. (e.g.

110
100
000

is the same as

**-
*--
---

Shortest Code in Bytes Wins

Example

STDIN: 6 3
STDOUT:

***
**_
*__

The Challenge has Ended!!!

After seven days I decided to declare the winner, but first some special awards!
Fastest code goes to... orlp with his submission in Pyth !
Slowest code goes to... orlp with his submission in Pyth !
Most straightforward code goes to... orlp with his submission in Pyth !
Most confusing code goes to... orlp with his submission in Pyth !
Longest Code goes to... orlp with his submission in Pyth !

And last but not least

Shortest code goes to......... orlp with his submission in Pyth !

Congratulations!

\$\endgroup\$
7
  • \$\begingroup\$ I updated the conditions so that 10 3 will never be an input. Also 0 is not a natural number so 0 0 will also never be an input \$\endgroup\$ Sep 15, 2015 at 0:32
  • 2
    \$\begingroup\$ natural numbers is ambiguous. The set-theoretic definition of natural number, e.g., includes 0. To avoid confusion, it's preferable to use (strictly) positive integers. \$\endgroup\$
    – Dennis
    Sep 15, 2015 at 3:26
  • \$\begingroup\$ @Dennis Also, if one specifically wants to include zero, nonnegative integers are a good choice. \$\endgroup\$ Sep 15, 2015 at 4:47
  • \$\begingroup\$ What if there there are several valid solutions? E.g. 24 6. \$\endgroup\$ Sep 15, 2015 at 8:37
  • \$\begingroup\$ @steveverrill I think they're sqrt(1^2+2^2)=sqrt(5) \$\endgroup\$
    – Cabbie407
    Sep 15, 2015 at 16:13

1 Answer 1

3
\$\begingroup\$

Pyth, 37 bytes

jc:*d*QQiRQhos.aMNf.Am}_dTT.c^UQ2vzNQ

Slow solution. Generates all possible pairs of [0, m), generate all possible n-combinations of those pairs (without repetition). Filter each combination of pairs such that if P is in the combination, so is reverse(P). This guarantees diagonal symmetry. Sort by the sum of distances to the origin. Decode the pairs of numbers as base-m numbers, giving a list of indices. Create a string of spaces except for those indices, putting quotation marks instead. Finally chop into m pieces and join by newlines. Creates outputs like such:

""""
"""
""
"
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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