Kombinacje Kakuro

Ponieważ nie umiem wykonywać arytmetyki mentalnej, często mam problemy z łamigłówką Kakuro , która wymaga od ofiary wielokrotnego sprawdzania, które odrębne liczby z zakresu od 1 do 9 (włącznie) sumują się z innymi liczbami z zakresu od 1 do 45, jeśli wiesz, jak to zrobić istnieje wiele liczb. Na przykład, jeśli chcesz wiedzieć, jak uzyskać 23 z 3 liczb, jedyną odpowiedzią jest 6 + 8 + 9. (Jest to ten sam pomysł, co Killer Sudoku, jeśli znasz się na tym).

Czasami będziesz mieć inne informacje, takie jak to, że liczba 1 nie może być obecna, więc aby uzyskać 8 w zaledwie 2 liczbach, możesz użyć tylko 2 + 6 i 3 + 5 (nie możesz użyć 4 + 4, ponieważ są one nie wyraźne). Ewentualnie może się zdarzyć, że w rozwiązaniu znalazłeś już 3, więc coś takiego jak 19 na 3 liczbach musi być 3 + 7 + 9.

Twoim zadaniem jest napisanie programu, który wymienia wszystkie możliwe rozwiązania danego problemu, w ścisłej kolejności, w ścisłym układzie.

Wejście

Twoje rozwiązanie może odbierać dane wejściowe jako pojedynczy ciąg ASCII poprzez stdin, argument wiersza poleceń, argument funkcji, wartość pozostawioną na stosie lub dowolne szaleństwo, jakie stosuje Twój ulubiony ezoteryczny język. Ciąg jest w formie

number_to_achieve number_of_numbers_required list_of_rejected_numbers list_of_required_numbers

Pierwsze 2 argumenty to typowe nieujemne liczby całkowite niezerowe o podstawie 10 odpowiednio w zakresie od 1 do 45 i od 1 do 9 (użycie kropki dziesiętnej byłoby niepoprawnym wprowadzeniem), dwie listy są po prostu cyframi połączonymi ze sobą bez ograniczenia w brak konkretnego zamówienia bez powtórzeń lub „0”, jeśli są pustymi listami. Między listami nie może być żadnych cyfr wspólnych (z wyjątkiem 0). Ograniczniki to pojedyncze spacje.

Wynik

Dane wyjściowe muszą zaczynać się od wiersza zawierającego liczbę możliwych rozwiązań. Twój program musi wydrukować rozwiązania rozdzielane podziałami linii, posortowane według każdej coraz ważniejszej cyfry, gdzie każda cyfra jest umieszczana w miejscu, w którym byłaby, gdybyś podał liczby od 1 do 9. Miejmy nadzieję, że poniższe przykłady to wyjaśnią.

Jeśli podano nieprawidłowe dane wejściowe, nie dbam o to, co robi twój program, chociaż wolałbym, żeby nie zerowało mojego sektora rozruchowego.

Przykłady

Dla tego przykładowego wejścia

19 3 0 0

Oczekiwany wynik to

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

Zanotuj spacje zamiast każdego „brakującego” numeru, są one wymagane; Nie przejmuję się spacjami, które nie mają po sobie cyfr (takich jak brakujące 9 powyżej). Możesz założyć, że cokolwiek drukujesz, będzie używać czcionki mono-spacji. Zwróć także uwagę na kolejność, w której najpierw są wyświetlane rozwiązania z najmniejszą najmniejszą cyfrą, a następnie rozwiązania z najmniejszą kolejną najmniejszą cyfrą itp.

Kolejny przykład oparty na powyższym

19 3 57 9

Oczekiwany wynik to

2
 2     89
   4 6  9

Zauważ, że każdy wynik zawiera 9, a żaden wynik nie zawiera 5 lub 7.

Jeśli na przykład nie ma rozwiązań

20 2 0 0

Następnie powinieneś po prostu wypisać pojedynczy wiersz z 0.

0

Celowo parsowałem wejściową część zabawy tego pytania. To jest gra w golfa, może wygrać najkrótsze rozwiązanie.

GolfScript, 88 znaków

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

Prosta implementacja w GolfScript. Pobiera dane wejściowe ze STDIN lub stosu.

Kod można przetestować tutaj .

Kod z kilkoma komentarzami:

### 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

Jako funkcja (testowalna) z 1 argumentem ciągu i zwracaniem żądanego wyniku. Aby uzyskać rzeczywistą zmianę wyniku, zwracaj z alert (), taką samą liczbą bajtów, ale uwaga, czcionka alertu nie jest jednolita.

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
}

Testuj w FireFox lub konsoli FireBug

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'))

Wyjście testowe:

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

Nie golfił

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 bajtów

(Przyznaję, że zacząłem nad tym pracować, gdy był jeszcze w piaskownicy).

{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"]<>""

Nie golfił

{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"] <> ""

Oczekuje, że łańcuch wejściowy zostanie zapisany i.

To dość proste. Najpierw parsowanie danych wejściowych. Następnie używam, IntegerPartitionsaby dowiedzieć się, jak mogę podzielić pierwszą liczbę na dozwolone liczby. Następnie odfiltrowuję wszystkie partycje, które używają duplikatów lub nie zawierają wymaganych numerów. A następnie dla każdego roztworu utworzyć listę od 1celu 9i przekształcić obecne liczby do ich reprezentacji smyczkowy i innych w pomieszczeniach. A potem wszystko łączę.

Groovy - 494 znaków

Duża, nieinspirowana odpowiedź, ale używa Google Guava do generowania „zestawu mocy”.

Gra w golfa:

@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}

Przykładowe przebiegi:

$ 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

Nie golfowany:

@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}