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ć.

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

15 komentarzy do "Pchełki SQL, odcinek 7: 1000"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
butter
Gość

przyznaje się bez bicia – robiłem to tylko dla [poprawnego?] wyniku. Wydajność faktycznie mogła by być lepsza. Btw:

0 not in (l1.x, l2.x, l3.x) można zastąpić l1.x * l2.x * l3.x !=0 [ale czy jest szybsze – nie wiem ;)]

Butter

MiSzA
Gość

Skoro Ty taki mistrz zagwozdek jesteś, to może pomożesz mi z moim problemem parainformatycznym. Akcja dzieje się w Excelu. Mamy tabelę, powiedzmy 20×10, choć to akurat jest nieistotne i podaje tylko dla pełnej plastyki opisu. W tabelę wpisujemy liczby od 1 do 99 (w kolejności losowej). Jeśli zadanie wykona się poprawnie, żadna liczba się nie powtarza. Niestety wielokrotnie się mylę i tu pytanie. Jaka formuła znajdzie mi w tabeli liczbę lub liczby, które się powtarzają? Ewentualnie liczby z zakresu 1 do 99, których brakuje?

butter
Gość

jak masz tabele 10×20 to nie ma bata, żeby liczby 1-99 się nie powtarzały ;).

W nowym excelu [>=2007] masz: formatowanie warunkowe / reguły wyróżniania komórek / duplikujące się wartości.

jeśli chcesz sprawdzić unikalność wartości, to użyj: =LICZ.JEŻELI(obszar_przeszukiwania;wartość)

MiSzA
Gość

Tabela zawiera puste komórki panowie 🙂

Formuła LICZ.JEŻELI ciut na piechotę, ale załatwi sprawę. Dzięki serdeczne.

Spróbowałbym jeszcze tego formatowania warunkowego, ale … nie wiem gdzie tą opcje znaleźć. No co? Nie każdy jest informatykiem 😉

MiSzA
Gość
No nie przyjacielu, manipulujesz moją wypowiedzią. Druga cytowana wypowiedź faktycznie nie jest najszczęśliwiej sformułowana, choć jak najbardziej prawdziwa. Niemniej potrafię zrozumieć skąd nieporozumienie. Natomiast pierwszą zakończyłem pytaniem: "Jaka formuła znajdzie mi w tabeli liczbę lub liczby, które się powtarzają? Ewentualnie liczby z zakresu 1 do 99, których brakuje?" I to było szukanym w zadaniu. Butte, załapał 😉 Ale. Żeby nie było, że do rabego po pomoc poszedł i jeszcze psioczy. Dzięki śliczne za pomoc. W pracy excela mam archaicznego na formatowanie warunkowe szans nie ma. Z licz.jeżeli też nie jest łatwo, bo office angielski i nie mogę odnaleźć odpowiadającej formuły.… Więcej »
Butter
Gość

jedn[..] where

l1.x l2.x and l1.x l3.x and l2.x l3.x

[..]

and (l1.x < l2.x and l2.x < l3.x)

imho te 2 warunki są redundantne – wystarczy 2gi

wpDiscuz