5
\$\begingroup\$

A number square containing the values 1, 2, 3, 4 looks like this:

12
34

To work out what a number square is, you first make four numbers by reading across the rows and across the columns; for the example above you would get 12, 34, 13 and 24, then you add them all up (12+34+13+24), giving you the value of the square.

However, there is a catch: the square your program outputs must output the lowest possible square. The way to calculate how 'low' the square is is like this:

  1. Take the top-left number, and place it in the variable a.
  2. Take the top-right number, double it and add the total to a.
  3. Take the bottom-left number, triple it and add the total to a.
  4. Take the bottom-right number, quadruple it and add the total to a.
  5. The variable a now holds how 'low' you square is!

Requirements

  • Your program must output the lowest possible number square, in the format that follows:

    ab
    cd
    

(where a, b, c and d are integers in the range 0-9).

  • The square will never contain a number multiple digits long (negative numbers as well). You don't have to handle that case.
  • You can take input, which will be the number the square should equal, as an argument, as function argument or from STDIN. Please specify how input should be given for your program.
  • If there is not a number square that equals what the input number, output nothing.
  • If two numbers squares are equally low and produce the same output, nothing should be output.

Rules

Test Cases

44 ==>
04
00
-----
2 ==>
00
01
-----
100 ==>
50
00

@MartinBüttner has also done a Pastebin with all the possible solutions.

Scoring

Programs are scored according to bytes. The usual character set is UTF-8, if you are using another please specify.

To win this challenge, try to get the least bytes!

Submissions

To make sure that your answer can be parsed, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 80765; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 53406; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
    languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang > b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
2
\$\begingroup\$

Pyth, 43 41 36 bytes

J.ms*VS4sbfqQsiR10sCBT^^UT2 2?tlJkhJ

Test suite.

Output as 2D array. ab/cd is represented as [[a, b], [c, d]].

How it works

J.ms*VS4sbfqQsiR10sCBT^^UT2 2?tlJkhJ

                      ^^UT2 2    Generate all number-squares
                                 with the above format.

          fqQsiR10sCBT

          f          T       Filter the squares as T:
                   CB            Yield [T, transpose(T)]
                  s              Yield T union transpose(T)
                                 We generated the rows and columns
                                 of the number square.
              iR10               Convert each from base10 array to int.
             s                   Sum.
           qQ                    Check if equal to the input.

J.ms*VS4sb

 .m      b         Find the squares (as b) in the filtered-result,
                   in which the following attains minimum:

        s              Flatten.
    *VS4               Multiply the first number by 1,
                               the second number by 2,
                                the third number by 3,
                           and the fourth number by 4.
   s                   Sum.
J                  Assign to the variable J.

                             ?tlJkhJ

                             ?         if
                              tlJ         length of J is not 1:
                                 k          output empty string
                                  hJ   else: output the first element of J
\$\endgroup\$
1
\$\begingroup\$

Pyth, 69 bytes

J.x.mebm,ds.e*hksbdfqQssM[<2T>2T+hTePT+htTeT)m.[\04`dU10000k?qlJ1hhJk

Try it here!

Outputs the square as a 4-digit number.
Works by generating all possible squares, keeping the ones which have the given number and then getting the lowest one.

Detailed Explanation later, gonna try to find a shorter way to calculate the number of a square first.

\$\endgroup\$
  • 2
    \$\begingroup\$ 10000 -> ^T4 \$\endgroup\$ – Leaky Nun May 27 '16 at 10:22
1
\$\begingroup\$

Matlab(284)

Too much rules, too much bytes, i hate too much rules!

function h(n),f=mod(n,2);b=(n-11*f)/2;a=fix((n-2*b)/11);c=(mod(ceil(b/11),10)+1)*(b>99);b=b-c*11;a=a+2*c;u=min(fix(b/10),mod(b,10));r=min(u,fix((9-a)/2*(a<9)));a=a+2*r;b=b-11*r;if(a>18||b<0||a+2*(u-r)>9&a==8)return;end,u=(a>9);r=mod(a,10-u);[fix(b/10),max(u*9,r);min(u*9,r),mod(b,10)]
  • this is a straight-forward method without even calculating the lowest weight of a square, i will add an explanation once i online-fork it.

This is how it goes, as known that a square value ab+cd+ac+bd can be simplified algebrically as 11(b+c)+2*[ad]_dec where [ad] is a*10+d , with weights assigned by ops respectively as (W_a,W_d)=(1,4) and (W_b,W_c)=(2,3) .

Thus, assuming an initial value of [ad] set as maximal number written in two digits, any number subtracted from it must be a multiple of 11 to be added to (b+c), otherwise that would screw the general form that the square value must be written as.

Since [ad] is two digits number, the multiple of 11 subtracted from [ad] must hold same amount from both a and d, which means weights are decreased equally but not added to (b+c) equally because it is required to attribute the maximal number to the lowest upweighting number which is b. so b will receive an even number. See the picture below it is definitely clearer than my awkward wording:

enter image description here

See that a (ported) value is not addded gradually, but there is a mathematical condition for it , it is S=minimum_positive(9-(b+c),a,d)

For the rest of conditions, function doesnt output nothing when:

  • b+c exceeds 18
  • the square value is below 11 and odd
  • after adding the farce to (b+c), min(a,d) remains bigger than 1, and b+c = 8, this means there is a potential square value of weight 3+2 , which equals the weight 1+4 , two equivalent values is an exclusive option, and disqualifies the outputs (tbh i dont see any point behind this rule)
\$\endgroup\$
  • \$\begingroup\$ Wait... is this a closed form solution? \$\endgroup\$ – Leaky Nun May 28 '16 at 16:42
  • 1
    \$\begingroup\$ @LeakyNun yes , right direct forward without trying so much combinations, i will add an explanation as soon as i can \$\endgroup\$ – Abr001am May 28 '16 at 17:01
0
\$\begingroup\$

C (ANSI), 210 bytes

#define a (l/1000)+2*((l/100)%10)+3*((l%100)/10)+4*(l%10) 
main(g,o,l,f){g--;o=91;for(f=l=-1;l<10000;g==++l%100+l/100+(l%10)+((l/100)%10*10)+((l/1000)*10)+(l/    10%10)?a==o?f=-1:a<o?f=l,o=a:1:1);printf("%04i",f);}

Pretty much makes all possible squares and finds the lowest. Input is read in as number of arguments. Output is the square as a 4 digit number.

Ex: 8

./numberSquare 1 1 1 1 1 1 1 1
0004

Expanded Version:

calcScore(l){
    return (l/1000)+2*((l/100)%10)+3*((l%100)/10)+4*(l%10);
}

main(g,o,l,f){
    g-=2;
    o=91;
    for(f=l=-1;l<10000;l++){
        if(g==l%100+l/100+(l%10)+((l/100)%10*10)+((l/1000)*10)+(l/10%10))
            if(calcScore(l)==o)f=-1;
        else if(calcScore(l)<o)f=l,o=calcScore(l);
    }
    printf("%04i",f);
}
\$\endgroup\$
0
\$\begingroup\$

Haskell, 133 bytes

a#b=10*a+b
g n|l<-[(a+2*b+3*c+4*d,m)|m@[a,b,c,d]<-mapM id$[0..9]<$"aaaa",a#b+a#c+b#d+c#d==n]=[b|q@(a,b)<-l,all(\k@(j,_)->j>a||k==q)l]

Output is a four element list [a,b,c,d]. Usage example: map g [129..139] -> [[[1,9,0,5]],[],[[6,1,0,0]],[],[[5,3,0,0]],[],[[4,5,0,0]],[],[[3,7,0,0]],[],[[2,9,0,0]]].

How it works:

l<-[        ]                  -- let l be the list of all
  (a+2*b+3*c+4*d,m)|           -- pairs (score, matrix), where
     m@[a,b,c,d]<-             -- matrix m (= [a,b,c,d]) is drawn from     
       mapM id$[0..9]<$"aaaa", -- all permutations of the digits of length 4 and
       a#b+a#c+b#d+c#d==n      -- the matrix sum equals n

=[b|            ]              -- return a list of all matrices b, where
  q@(a,b)<-l                   -- the pair q = (a,b) is drawn from l and
    all(\k@(j,_)->j>a||k==q)l] -- a is minimal and unique
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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