September 24, 2009 at 6:57 am
Hi all,
I know its difficult to explain but i will try my best. we have location grid which has 4 rows A,B,C,D and 10 columns (A1 to A10,B1 to B10, C1 o C10,D1 to D10) and here is the table structure for this grid:-
Table Name:- Locations
Columns :- location varchar(10)
filled bit
In this table , if location is empty , filled is 0 and if location is filled, filled is 1 .
For example:- A1 0
A2 1
and so on. now lets start with problem(puzzle)
I have to find 3 consecutive locations which are empty to place an big order in it. for example:- if C3,C4,C5 are not filled, i can place my order in these 3 locations.
Now my thinking is:-
1. first scan all rows a,B,C,D for 3 consecutive locations that are empty.
2. then select one of the rows to put in order.
i am trying to work on this logic but still no success yet. so thought to post it here. please help me out with this.
September 24, 2009 at 8:52 am
Your problem is easier if you normalise your data as follows:
CREATE TABLE #Location (
Row char(1) NOT NULL,
Col tinyint NOT NULL,
Filled bit NOT NULL,
CONSTRAINT PK_Location PRIMARY KEY (Row, Col)
)
It is simple to derive a temporary table with the above structure from your table data, if that is necessary, but if you are able to change your base table schema, then I recommend something like the normalised structure above.
Here is a way to generate some test data:
INSERT INTO #Location (Row, Col, Filled)
SELECT R.Id, C.Id,
CASE WHEN (CHECKSUM(NEWID()) > 0) THEN 1 ELSE 0 END
FROM (
SELECT 1 UNION ALL
SELECT 2 UNION ALL
SELECT 3 UNION ALL
SELECT 4 UNION ALL
SELECT 5 UNION ALL
SELECT 6 UNION ALL
SELECT 7 UNION ALL
SELECT 8 UNION ALL
SELECT 9 UNION ALL
SELECT 10
) C(Id)
CROSS JOIN (
SELECT 'A' UNION ALL
SELECT 'B' UNION ALL
SELECT 'C' UNION ALL
SELECT 'D'
) R(Id)
Here is one way to retrieve a list of (Row, Col) pairs where there are at least @n consecutive unfilled slots starting at column Col.
/* Number of slots per row */
DECLARE @Slots int
SELECT @Slots = 10
/* Number of consecutive unfilled slots required */
DECLARE @n int
SELECT @n = 3
SELECT L1.Row, L1.Col,
COALESCE((
SELECT MIN(L2.Col) FROM #Location L2
WHERE (L1.Row = L2.Row)
AND (L2.Col > L1.Col)
AND (L2.Filled = 1)
), @Slots + 1) - L1.Col AS FreeSlots
FROM #Location L1
WHERE (L1.Filled = 0)
AND (@n L1.Col)
AND (L2.Filled = 1)
), @Slots + 1) - L1.Col)
From these results, there are several possible ways to select one group of consecutive slots.
E.g. the following query returns a row where the Col value of initial free slot is a minimum.
SELECT TOP 1 L1.Row, L1.Col
FROM #Location L1
WHERE (L1.Filled = 0)
AND (@n L1.Col)
AND (L2.Filled = 1)
), @Slots + 1) - L1.Col)
ORDER BY Col, Row
I'm assuming that you're using SQL Server 2000. If you are using SQL Server 2005 or SQL Server 2008, there are some other possible solutions using the ROW_NUMBER() function to find consecutive sequences.
EDIT: Removed duplicate local variable declarations in script
September 24, 2009 at 9:28 am
Thank You sir, this works great. but in above solution it gives me first empty 3 locations(In example below:- B7,B8,B9). Here is my scenario:-
A1 0
A2 0
A3 1
A4 1
A5 1
A6 0
A7 0
A8 1
A9 0
A10 0
B1 1
B2 1
B3 1
B4 1
B5 1
B6 1
B7 0
B8 0
B9 0
B10 1
C1 1
C2 1
C3 1
C4 0
C5 0
C6 0
C7 1
C8 1
C9 1
C10 1
D1 0
D2 0
D3 0
D4 1
D5 1
D6 1
D7 0
D8 0
D9 0
D10 1
Now from the above structure of table , you can see that Row B is empty so i can find 3 locations here and so in Rows C and D. But i want to select here Row C becuase then i can keep Row B open for more bigger orders that can consume 4 or 5 or 6 locations!
This is scenario can you help me with this. i need some algorithm that can give me consecutive number of locations free for an order which can consume any number of locations(provided number of locations given )
September 24, 2009 at 11:32 pm
I'm not 100% confident that I understand what you are trying to do, but I think that you are looking for the shortest consecutive sequence of unfilled slots where the number of slots is greater or equal to @n (say 3). Therefore, you are optimally looking for a consecutive sequence of precisely @n unfilled slots. If so, the following amended version of my previous query should do the job. I have added a left self join in order to retrieve only unfilled slots that are immediately preceded in the row by a filled slot (or are in column position 1).
/* Number of slots per row */
DECLARE @Slots int
SELECT @Slots = 10
/* Number of consecutive unfilled slots required */
DECLARE @n int
SELECT @n = 3
SELECT TOP 1 L1.Row, L1.Col,
COALESCE((
SELECT MIN(L2.Col) FROM #Location L2
WHERE (L1.Row = L2.Row)
AND (L2.Col > L1.Col)
AND (L2.Filled = 1)
), @Slots + 1) - L1.Col AS FreeSlots
FROM #Location L1
LEFT OUTER JOIN #Location L0
ON (L0.Row = L1.Row AND L0.Col = L1.Col - 1)
WHERE (L1.Filled = 0)
AND (L0.Filled = 1 OR L1.Col = 1)
AND (@n L1.Col)
AND (L2.Filled = 1)
), @Slots + 1) - L1.Col)
ORDER BY FreeSlots, L1.Col, L1.Row
September 25, 2009 at 12:24 am
Out of interest, an alternative and probably better solution on SQL Server 2005 is to use the ROW_NUMBER() function to help identify consecutive sequences of unfilled slots. Please note that following code is untested as I currently don't have access to a SQL Server 2005 instance.
DECLARE @n int
SELECT @n = 3
;WITH cteUnfilledSlots AS (
SELECT Row, Col,
Col - ROW_NUMBER() OVER (PARTITION BY Row ORDER BY Col) AS Seq
FROM #Location
WHERE (Filled = 0)
)
SELECT TOP 1
Row, MIN(Col) AS Col, COUNT(*) AS FreeSlots
FROM cteUnfilledSlots
GROUP BY Row, Seq
HAVING COUNT(*) >= @n
ORDER BY FreeSlots, Col, Row
September 25, 2009 at 3:06 am
Here's another way to do it in SQL Server 2000, that uses a similar concept as the ROW_NUMBER() function method that can be used in SQL Server 2005. This query uses the IDENTITY function in a SELECT INTO query to generate sequence numbers. In the inner aggregate query in the final SELECT staement, grouping rows by the difference between this sequence number and the column number is used to identify consecutive sequences of unfilled slots. Since this version requires a temporary table, I have started from your original table structure rather than my denormalised structure, but it could be made to work with either.
/* Create table */
CREATE TABLE #Location (
Location varchar(10) NOT NULL,
Filled bit NOT NULL
)
/* Populate with test data */
INSERT INTO #Location (Location, Filled)
SELECT R.Id + CONVERT(varchar(9), C.Id),
CASE WHEN (CHECKSUM(NEWID()) > 0) THEN 1 ELSE 0 END
FROM (
SELECT 1 UNION ALL
SELECT 2 UNION ALL
SELECT 3 UNION ALL
SELECT 4 UNION ALL
SELECT 5 UNION ALL
SELECT 6 UNION ALL
SELECT 7 UNION ALL
SELECT 8 UNION ALL
SELECT 9 UNION ALL
SELECT 10
) C(Id)
CROSS JOIN (
SELECT 'A' UNION ALL
SELECT 'B' UNION ALL
SELECT 'C' UNION ALL
SELECT 'D'
) R(Id)
SELECT * FROM #Location
/* Create work table of unfilled slots including sequence number */
SELECT IDENTITY(int, 1, 1) AS Seq,
SUBSTRING(Location, 1, 1) AS Row,
CONVERT(int, SUBSTRING(Location, 2, 9)) AS Col
INTO #UnfilledSlots
FROM #Location
WHERE (Filled = 0)
/* Specify number of consecutive unfilled slots required */
DECLARE @n int
SELECT @n = 3
/* Find suitable location */
SELECT T.Row + CONVERT(varchar(9), T.Col) AS Location, T.FreeSlots
FROM (
SELECT TOP 1
Row, MIN(Col) AS Col, COUNT(*) AS FreeSlots
FROM #UnfilledSlots
GROUP BY Row, Col - Seq
HAVING COUNT(*) >= @n
ORDER BY FreeSlots, Col, Row
) T
Viewing 6 posts - 1 through 5 (of 5 total)
You must be logged in to reply to this topic. Login to reply