Having some logic issues with a "split detector"

Help and Feedback Scripting Support
#1

Greetings! So for awhile now I’ve been trying to develop a split checker function for my bowling game. Since this issue is purely logic-based, I’m gonna try my best to fully explain what I did in my code, and what goal I’m trying to achieve here. I’m also going to post the code on pastebin because I always have issues trying to format my code correctly if I post it on my threads directly, hope that’s okay.

So, one way I wanted to start making this system is to put all of the standing pins into groups, which would be tables within a table. And, the end theory, if there’s 2 or more groups of pins found in the pin_groups table, I would then return true as it was calculated to be a split. You’ll notice in the code I have a pins_touching table, and what that is is that for each pin, there’s pins that can be around it. Those pins are specified in this table. I use this to determine if there’s touching pins standing that can be connected to a pin, and if so, that pin can be added to the same group as the pin in the loop. After the loop finishes running, if no connection can be made, then a new pin group is made with whatever pin was being tested.

I finally got this code working, however, I noticed it often makes multiple groups of pins when really there should only be one. An example of this is that I put up the entire back row of pins, so that’s four, all next to each other. For whatever reason, the code determined there were two groups of pins there, the two to the left side, and the two to the right side. Made no sense to me…

Probably a long, wordy, and poorly explained post. I could also answer any questions if I need to specify further, apologies for that. I have a hard time trying to explain logical issues with my code…

Thanks for reading!

Here’s the code local touching_pins = { ["Pin2"] = {["Pin3"] = true,["Pin4"] = true,["Pin5"] = - Pastebin.com

EDIT: It’s also worth mentioning that the standing_pins table is the table that is passed into the is_split function. (Those are the pins that the code iterates through and makes pin groups out of them)

1 Like
#2

The problem must be from the loops, I’m quite having hard time understanding, are you able of explaining more information about this so that we can see if I’m able of working it out?

1 Like
#3

Hey, thanks for the response. I meant to check back here a bit earlier, but I actually just now solved the issue. I believe the main problem was due to not iterating through all the pins in numerical order, which potentially causes multiple pin groups to be made when there should only be one.

Thanks for the response though!

1 Like
#4

I think you’ll want to construct some sort of connectivity graph between the pins, and then from there just count the number of components.

just fyi your algorithm fails if it visits 7->9->8->10 (remember that dicts aren’t iterated in the order that its entries are declared!) because 7 and 9 are assigned to different groups initially.

Even if they’re iterated in order it wouldn’t work . Something like 6, 7, 8, 9 may still be separated into two groups, for example.

1 Like
#5

You know how I mentioned needing to construct some sort of graph? It looks like it’s unnecessary since you already have a “connectivity graph” defined as touching_pins!

Here’s some code which counts the number of groups in your pins and returns true if it’s >= 2.

local touching_pins = {
    -- I don't know much about bowling. Shouldn't Pin1 have an entry here, too?
    -- If it shouldn't then replace this with {}
    ["Pin1"] = {["Pin2"] = true, ["Pin3"]= true};
    ["Pin2"] = {["Pin3"] = true,["Pin4"] = true,["Pin5"] = true};
    ["Pin3"] = {["Pin2"] = true,["Pin5"] = true,["Pin6"] = true};
    ["Pin4"] = {["Pin2"] = true,["Pin5"] = true,["Pin7"] = true,["Pin8"] = true};
    ["Pin5"] = {["Pin2"] = true,["Pin3"] = true,["Pin4"] = true,["Pin6"] = true,["Pin8"] = true,["Pin9"] = true};
    ["Pin6"] = {["Pin3"] = true,["Pin5"] = true,["Pin9"] = true,["Pin10"] = true};
    ["Pin7"] = {["Pin4"] = true,["Pin8"] = true};
    ["Pin8"] = {["Pin4"] = true,["Pin5"] = true,["Pin7"] = true,["Pin9"] = true};
    ["Pin9"] = {["Pin5"] = true,["Pin6"] = true,["Pin8"] = true,["Pin10"] = true};
    ["Pin10"] = {["Pin6"] = true,["Pin9"] = true};
}

function is_split(pins)
	local components = 0
	local visited = {}
	-- perform a depth-first traversal on pinId
	-- recursively mark pins that are next to pinId as visited.
	local function dfs(pinId)
		visited[pinId] = true
		-- for every pin that CAN be adjacent to pinId...
		local possible_adjacents = touching_pins[pinId]
		for adjPinId, _ in next, possible_adjacents do
			-- if that pin actually exists and we haven't visited it before, then
			-- visit it.
			if pins[adjPinId] and not visited[adjPinId] then
				dfs(adjPinId)
			end
		end
	end
	
	for pinId, _ in next, pins do
		-- if pinId hasn't been visited by a previous dfs, then do a dfs on that pin
		-- and increment the number of components that we've found so far.
		if not visited[pinId] then
			components = components + 1
			dfs(pinId)
		end
	end
	
	return components >= 2
end
2 Likes
#6

tl;dr: you overlooked the fact that a pin can be a member of two groups at the same time, which causes you to overlook the second group.

What’s supposed to happen:

  • Pin7 creates a new group
  • Pin8 is a member of Pin7, so this is added to that group
  • Pin9 is a member of Pin8, so this is added to that group
  • Pin10 is a member of Pin9, so this is added to that group

One clean group is returned

Using XAXA’s first example:

  1. Pin7 creates a new group
  2. Pin9 is not a member of any currently existing group, so a new group is made
  3. Pin8 is a member of both Pin7 and Pin9, so this is added to the first group
  4. Pin10 is a member of Pin9, so this is added to that group

Two groups are returned

Using XAXA’s second example:

  1. Pin6 creates a new group
  2. Pin7 is not a member of any currently existing group, so a new group is made
  3. Pin8 is a member of Pin7, so this is added to that group
  4. Pin9 is a member of both Pin6 and Pin8, so this is added to the first group

Two groups are returned

As you can see from these examples, the problem with your function is that it overlooks the fact that a pin can be a member of two separate groups, causing it to be biased towards one group and therefore creating a problem.

Your solution would be an implementation to merge two groups together, so the workflow would look like this:

  1. Pin7 creates a new group
  2. Pin9 is not a member of any currently existing group, so a new group is made
  3. Pin8 is a member of both Pin7 and Pin9, so both groups are merged together, and this is added to that group
  4. Pin10 is a member of Pin9, so this is added to that group.

…or XAXA’s connectivity graph. Whichever one works…

1 Like