Kakuro-Kombinationen

Da ich mental nicht rechnen kann, habe ich oft Probleme mit dem Kakuro- Puzzle, bei dem das Opfer wiederholt herausfinden muss, welche unterschiedlichen Zahlen im Bereich von 1 bis 9 (einschließlich) sich zu einer anderen Zahl im Bereich von 1 bis 45 addieren, wenn Sie wissen, wie es gibt viele zahlen. Wenn Sie beispielsweise wissen möchten, wie Sie 23 aus 3 Zahlen erhalten, ist die einzige Antwort 6 + 8 + 9. (Dies ist die gleiche Idee wie bei Killer Sudoku, wenn Sie damit vertraut sind).

Manchmal haben Sie andere Informationen, wie zum Beispiel, dass die Zahl 1 nicht vorhanden sein kann. Um also 8 in nur 2 Zahlen zu erreichen, können Sie nur 2 + 6 und 3 + 5 verwenden (Sie können 4 + 4 nicht verwenden, da dies der Fall ist nicht verschieden). Alternativ kann es sein, dass Sie bereits eine 3 in der Lösung gefunden haben, und so muss 19 in 3 Zahlen 3 + 7 + 9 sein.

Ihre Aufgabe ist es, ein Programm zu schreiben, das alle möglichen Lösungen für ein bestimmtes Problem in einer strengen Reihenfolge und in einem strengen Layout auflistet.

Eingang

Ihre Lösung kann die Eingaben als einzelne ASCII-Zeichenfolge entweder über stdin, ein Befehlszeilenargument, ein Argument für eine Funktion, einen auf dem Stapel verbliebenen Wert oder den Wahnsinn Ihrer bevorzugten esoterischen Sprache empfangen. Die Zeichenfolge ist in der Form

number_to_achieve number_of_numbers_required list_of_rejected_numbers list_of_required_numbers

Die ersten beiden Argumente sind typische nicht negative Ganzzahlen zur Basis 10 ungleich Null im Bereich von 1 bis 45 bzw. 1 bis 9 (bei Verwendung eines Dezimalpunkts wäre die Eingabe ungültig). Die beiden Listen sind nur Ziffern, die ohne Begrenzung ineinander gereiht sind Keine bestimmte Reihenfolge ohne Wiederholung oder '0', wenn es sich um leere Listen handelt. Zwischen den Listen dürfen keine gemeinsamen Ziffern sein (außer 0). Die Begrenzer sind einzelne Leerzeichen.

Ausgabe

Ihre Ausgabe muss mit einer Zeile beginnen, die die Anzahl der möglichen Lösungen enthält. Ihr Programm muss durch Zeilenumbrüche getrennte Lösungen ausgeben, die nach immer wichtigeren Ziffern sortiert sind. Dabei wird jede Ziffer an die Stelle gesetzt, an der sie sich befinden würde, wenn Sie die Zahlen von 1 bis 9 aufführen würden. Die folgenden Beispiele werden dies hoffentlich klarer machen.

Wenn eine ungültige Eingabe bereitgestellt wird, ist es mir egal, was Ihr Programm tut, obwohl ich es vorziehen würde, wenn mein Bootsektor nicht auf Null gesetzt würde.

Beispiele

Für dieses Beispiel Eingabe

19 3 0 0

Die erwartete Ausgabe wäre

5
 2     89
  3   7 9
   4 6  9
   4  78 
    56 8 

Beachten Sie die Leerzeichen anstelle jeder "fehlenden" Nummer. Diese sind erforderlich. Ich mache mir keine Sorgen um Leerzeichen, hinter denen keine Nummer steht (wie die fehlenden 9en oben). Sie können davon ausgehen, dass bei jedem Ausdruck eine Mono-Space-Schriftart verwendet wird. Beachten Sie auch die Reihenfolge, in der zuerst Lösungen mit der kleinsten Ziffer und dann mit der kleinsten nächstkleineren Ziffer usw. aufgelistet werden.

Ein weiteres Beispiel, basierend auf dem obigen

19 3 57 9

Die erwartete Ausgabe wäre

2
 2     89
   4 6  9

Beachten Sie, dass jedes Ergebnis eine 9 und kein Ergebnis eine 5 oder 7 enthält.

Wenn es zum Beispiel keine Lösungen gibt

20 2 0 0

Dann sollten Sie nur eine einzelne Zeile mit einer 0 darauf ausgeben.

0

Ich habe das Parsen der Eingabe absichtlich zum Spaß dieser Frage gemacht. Dies ist Code-Golf, möge die kürzeste Lösung gewinnen.

GolfScript, 88 Zeichen

~[[]]10,:T{{1$+}+%}/\{\0+`-!}+,\{0`+\`&!}+,\{\,=}+,\{\{+}*=}+,.,n@{1T>''*T@-{`/' '*}/n}/

Eine einfache Implementierung in GolfScript. Übernimmt Eingaben von STDIN oder Stack.

Der Code kann hier getestet werden .

Code mit einigen Kommentaren:

### evaluate the input string
~                     

### build all possible combinations of 0...9
[[]]              # start with set of empty combination
10,:T             #
{                 # for 0..9
  {1$+}+%         #   copy each item of set and append current digit to this copy
}/                # end for

### only keep combination which the digits given as last argument (minus 0)
\{                # start of filter block
  \0+`            #   add zero to combination and make string out of it
  -!              #   subtract from last argument -> check argument contains any
                  #     excess characters
}+,               # end of filter block


### remove any combination which contains either 0 or any digit from 2nd last argument
\{                # start of filter block
  0`+             #   take argument and append 0
  \`              #   stringify combination
  &!              #   check if no characters are common
}+,               # end of filter block

### filter for correct length
\{                # start of filter block
  \,              #   calc length of combination
  =               #   check if equal to second argument
}+,               # end of filter block

### filter for correct sum
\{                # start of filter block
  \{+}*           #   sum all digits of combination
  =               #   compare with first argument
}+,               # end of filter block

### output
.,                # determine size of set
n                 # append newline
@{                # for each combination in set
  1T>''*          #   generate "123456789"
  T@-             #   generate anti-set of current combination  
  {`/' '*}/       #   replace (in the string) each digit within the 
                  #   anti-combination with a space characters
  n               #   append newline
}/                # end for

JavaScript (E6) 172 180 275 296

Als (testbare) Funktion mit 1 String-Argument und Rückgabe der angeforderten Ausgabe. Damit eine echte Ausgabeänderung mit alert () und der gleichen Byte-Anzahl zurückgegeben wird, muss jedoch beachtet werden, dass die Schriftart für Warnungen keine Monospace-Schriftart ist.

F=i=>{
  [t,d,f,m]=i.split(' ');
  for(l=0,r='',k=512;--k;!z&!h&!o&&(++l,r+=n))
    for(z=n='\n',h=d,o=t,b=i=1;i<=9;b+=b)
      z-=~(b&k?(--h,o-=i,n+=i,f):(n+=' ',m)).search(i++);
  return l+r
}

Test In FireFox oder Firebug - Konsole

console.log(['19 3 0 0','19 3 57 9','19 3 57 4','20 2 0 0'].map(x=>'\n'+x+'\n' +F(x)).join('\n'))

Testausgang:

19 3 0 0
5
 2     89
  3   7 9
   4 6  9
   4  78 
    56 8 

19 3 57 9
2
 2     89
   4 6  9

19 3 57 4
1
   4 6  9

20 2 0 0
0

Ungolfed

F=i=>{
  [target, digits, forbidden, mandatory]=i.split(' ')

  result = '', nsol=0
  for (mask = 0b1000000000; --mask > 0;)
  {
    cdigits = digits
    ctarget = target
    bit = 1
    numbers = ''
    for (digit = 9; digit > 0; bit += bit, digit--)
    {

      if (bit & mask)
      {
        if (forbidden.search(digit)>=0) break;
        cdigits--;
        ctarget -= digit;
        numbers = digit + numbers;
      }
      else
      {
        if (mandatory.search(digit)>=0) break;
        numbers = ' '+numbers;
      }
    }
    if (ctarget==0 && cdigits == 0)
    {
        result += '\n'+numbers
        nsol++
    }
  }
  return nsol + result
}

Mathematica, 239 Bytes

(Ich gebe zu, ich habe angefangen, daran zu arbeiten, als es noch im Sandkasten war.)

{t,n,a,b}=FromDigits/@StringSplit@i;Riffle[c=Cases[Union/@IntegerPartitions[t,n,Complement[r=Range@9,(d=IntegerDigits)@a]],k_/;(l=Length)@k==n&&(b==0||l[k⋂d@b]>0)];{(s=ToString)@l@c}~Join~((m=#;If[m~MemberQ~#,s@#," "]&/@r)&/@c),"\n"]<>""

Ungolfed

{t, n, a, b} = FromDigits /@ StringSplit@i;
Riffle[
  c = Cases[
    Union /@ IntegerPartitions[
      t, n, Complement[r = Range@9, (d = IntegerDigits)@a
       ]
      ],
    k_ /; (l = Length)@k == 
       n && (b == 0 || l[k ⋂ d@b] > 0)
    ];
  {(s = ToString)@l@c}~
   Join~((m = #; If[m~MemberQ~#, s@#, " "] & /@ r) & /@ c),
  "\n"] <> ""

Es erwartet, dass die Eingabezeichenfolge in gespeichert wird i.

Es ist ziemlich einfach. Zuerst wird die Eingabe analysiert. Dann nutze ich, IntegerPartitionsum herauszufinden, wie ich die erste Zahl in die zulässigen Zahlen aufteilen kann. Dann filtere ich alle Partitionen heraus, die Duplikate verwenden oder keine erforderlichen Nummern enthalten. Und dann erstelle ich für jede Lösung eine Liste von 1bis 9und konvertiere die vorhandenen Zahlen in ihre Zeichenfolgendarstellung und die anderen in Leerzeichen. Und dann verkette ich alles.

Groovy - 494 Zeichen

Große, nicht inspirierte Antwort, aber es verwendet Google Guava, um das "Power Set" zu generieren.

Golf gespielt:

@Grab(group='com.google.guava', module='guava', version='17.0')
m=(args.join(" ")=~/(\d+) (\d+) (\d+) (\d+)/)[0]
i={it as int}
n=i(m[1])
r=i(m[2])
j=[]
m[3].each{if(i(it))j<<i(it)}
q=[]
m[4].each{if(i(it))q<<i(it)}
d=1..9 as Set<Integer>
t=[]
com.google.common.collect.Sets.powerSet(d).each{x->
if(x.sum()==n&&x.size()==r&&x.disjoint(j)&&x.containsAll(q)) {
s="";for(i in 0..8){if(x.contains(i+1)){s+=(i+1) as String}else{s+=" "}};t<<s}
}
p={println it}
p t.size()
t.sort().reverse().each{p it}

Probeläufe:

$ groovy K.groovy 19 3 0 0 
5
 2     89
  3   7 9
   4 6  9
   4  78 
    56 8 
$ groovy K.groovy 19 3 5 0 
4
 2     89
  3   7 9
   4 6  9
   4  78 
$ groovy K.groovy 19 3 5 9
3
 2     89
  3   7 9
   4 6  9
$ groovy K.groovy 20 2 0 0 
0

Ungolfed:

@Grab(group='com.google.guava', module='guava', version='17.0')

m=(args.join(" ")=~/(\d+) (\d+) (\d+) (\d+)/)[0]
i={it as int}
n=i(m[1])
r=i(m[2])

j=[]
m[3].each{if(i(it))j<<i(it)}
q=[]
m[4].each{if(i(it))q<<i(it)}

d=1..9 as Set<Integer>
t=[]

com.google.common.collect.Sets.powerSet(d).each{ x ->
    if(x.sum()==n && x.size()==r && x.disjoint(j) && x.containsAll(q)) {
        s=""
        for(i in 0..8) {
            if(x.contains(i+1)){s+=(i+1) as String}else{s+=" "}
        }
        t<<s
    }
}

p={println it}
p t.size()
t.sort().reverse().each{p it}