Pchełki SQL, odcinek 7: 1000

Pisałem niedawno o zagadnieniu wyszukiwania trójek liczb trzycyfrowych sumujących się dokładnie do 1000, z dziewięciu różnych cyfr.

Butter zapodał w komentarzach przykładowe rozwiązanie w SQL-u, a także zasugerował, że można by je zoptymalizować pod kątem wydajności. Kod, który podał, wykonywał się u mnie około czterech i pół minuty.

Siadłem więc do tematu i oto urodziła się kolejna pchełka SQL. Mój kod pokrywa się w większości z pomysłem Buttera, podrasowałem go tylko tu i ówdzie.

Po pierwsze, pozbyłem się kosztownych operacji na stringach.

Po drugie, dodałem warunek odrzucający liczby, w których na pozycji setek znajdują się cyfry nie sumujące się dokładnie do dziesięciu (włączając w to ewentualne przeniesienie z pozycji dziesiątek).

Po trzecie wreszcie, pozbyłem się duplikatów (korzystając z naprzemienności dodawania, zredukowałem ilość trójek na wyjściu z 1080 do 180)

W ten oto sposób powstał kod, który wykonuje się w niecałe pół sekundy. Oto on:

with licz as
( select 0 x
  union all select x + 1
  from licz
  where x < 9
)
, jed as
( select
	l1.x x1,
	l2.x x2,
	l3.x x3,
	(l1.x + l2.x + l3.x) / 10 as jed10 
  from licz l1, licz l2, licz l3
  where
	l1.x <> l2.x and
	l1.x <> l3.x and
	l2.x <> l3.x
	and
	(l1.x + l2.x + l3.x) % 10 = 0
	and
	(l1.x < l2.x and l2.x < l3.x)
) 
, dzie as
( select
	jed.x1 jx1,
	jed.x2 jx2,
	jed.x3 jx3,
	l1.x dx1,
	l2.x dx2,
	l3.x dx3,
	(jed10 + l1.x + l2.x + l3.x) / 10 as dzie10 
  from licz l1, licz l2, licz l3, jed
  where
	l1.x <> l2.x and
	l1.x <> l3.x and
	l2.x <> l3.x
	and
	l1.x not in (jed.x1, jed.x2, jed.x3) and
	l2.x not in (jed.x1, jed.x2, jed.x3) and
	l3.x not in (jed.x1, jed.x2, jed.x3)
    and 
	10 - ((l1.x + l2.x + l3.x) % 10) = jed10
  )
 , setki as (
  select
	l1.x sx1,
	l2.x sx2,
	l3.x sx3,
	dzie.dx1,
	dzie.dx2,
	dzie.dx3,
	dzie.jx1,
	dzie.jx2,
	dzie.jx3
  from licz l1, licz l2, licz l3, dzie
  where
	l1.x <> l2.x and
	l1.x <> l3.x and
	l2.x <> l3.x
	and
	0 not in (l1.x, l2.x, l3.x)
	and
	l1.x not in (dzie.dx1, dzie.dx2, dzie.dx3, dzie.jx1, dzie.jx2, dzie.jx3) and
	l2.x not in (dzie.dx1, dzie.dx2, dzie.dx3, dzie.jx1, dzie.jx2, dzie.jx3) and
	l3.x not in (dzie.dx1, dzie.dx2, dzie.dx3, dzie.jx1, dzie.jx2, dzie.jx3)
	and
	10-((l1.x+l2.x+l3.x) % 10) = dzie10
)
select
	sx1 * 100 + dx1 * 10 + jx1 l1,
	sx2 * 100 + dx2 * 10 + jx2 l2,
	sx3 * 100 + dx3 * 10 + jx3 l3
from setki
where sx1 * 100 + dx1 * 10 + jx1 + sx2 * 100 + dx2 * 10 + jx2 + sx3 * 100 + dx3 * 10 + jx3 = 1000;

Odrobina wyjaśnień:

Pierwsze CTE (licz), generuje jednokolumnową listę liczb od zera do dziewięciu.

Drugie CTE (jed) generuje wszystkie trójki ostatnich cyfr (czyli cyfr na pozycji jednostek) takie, że:
– ich suma dzieli się przez 10
– są posortowane rosnąco (właśnie tutaj usuwamy duplikaty!)
– są różne
Oprócz tego w tym CTE wyliczamy również cyfrę przeniesienia do kolumny dziesiątek (jed10), która wynosi zawsze 1 lub 2.

Trzecie CTE (dzie) zwraca siedem kolumn: trzy kolumny z poprzedniego CTE (a więc kolumna jedności), trzy kolumny z cyframi dziesiątek, oraz wartość przeniesienia do kolumny setek. Uwzględniamy tutaj wartość przeniesienia z kolumny jedności, zapewniamy, że wszystkie cyfry mają być różne (a także różne od tych użytych w kolumnie jedności), oraz że ich suma, wraz z nadmiarem przeniesionym z kolumny jedności, ma być podzielna przez 10.

Czwarte CTE (setki) robi dokładnie to samo co poprzednie, z tą tylko różnicą, że wykluczamy zero (liczba trzycyfrowa nie może zaczynać się od zera).

Wreszcie końcowe zapytanie zwraca te z liczb, których suma wynosi tysiąc.

Ciekawostką jest, że faktycznie – jak poprawnie odgadł B – jedyną cyfrą, którą można wyeliminować z zakresu 0-9 jest ósemka; w tym przypadku suma pozostałych cyfr wynosi 37 a więc – zgodnie z rozważaniami pokazanymi przez B – da się takie trójki zbudować.


Liczba słów w tym wpisie: 750

Sprawdź też

Pchełki SQL: leniwe przestępne

Zaskakująco prosta metoda na sprawdzenie przestępności roku.

Pchełki SQL: ROW_NUMBER() bez sortowania

Rzecz o tym, jak nie posortować danych w SQL-u.

Zapisz się
Powiadom o
guest
15 komentarzy
Inline Feedbacks
Zobacz wszystkie komentarze
15
0
Zapraszam do skomentowania wpisu.x
()
x