water_jars.AStar.GetResult() - Code Metrics - KenMercusLai/checkio - Measure and Improve Code Quality continuously with Scrutinizer

water_jars.AStar.GetResult() A
last analyzed 2022-05-11 09:02 UTC

↳ Parent: water_jars

Complexity

Conditions

Size

Total Lines	2
Code Lines	2

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	1
eloc	2
nop	2
dl	0
loc	2
rs	10
c	0
b	0
f	0

gFirst = 0
gSecond = 0


class AStar(object):
    def __init__(self, Goal):
        self.Goal = Goal

    def Heuristic(self, Node):
        raise NotImplementedError

    def GetResult(self, Node):
        raise NotImplementedError

    def Search(self, StartNode):
        OpenSet = set()
        ClosedSet = set()
        StartNode.H = self.Heuristic(StartNode)
        OpenSet.add(StartNode)
        while OpenSet:
            Current = min(OpenSet, key=lambda o: o.G + o.H)
            if self.Goal(Current.Status):
                return self.GetResult(Current)
            OpenSet.remove(Current)
            ClosedSet.add(Current)
            for Node in Current.PossibleNextNodes():
                if Node.Status in [i.Status for i in ClosedSet]:
                    continue
                if Node.Status in [i.Status for i in OpenSet]:
                    index = [i.Status for i in OpenSet].index(Node.Status)
                    if Node.G < list(OpenSet)[index].G:
                        list(OpenSet)[index].G = Node.G
                        list(OpenSet)[index].Parent = Node.Parent
                else:
                    Node.H = self.Heuristic(Node)
                    if Node.SelfCheck:
                        OpenSet.add(Node)
        return None


class AStarNode(object):
    def __init__(self, Status, G, Parent):
        self.G = G
        self.H = None
        self.Parent = Parent
        self.Status = Status
        self.Comment = None

    def SelfCheck(self):
        if self.G and self.H and self.Status:
            return True
        else:
            print(self.G)
            print(self.H)
            print(self.Parent)
            print(self.Status)
            print(self.Comment)
            assert 1 == 0

    def PossibleNextNodes(self):
        raise NotImplementedError


class WaterJarPuzzle(AStar):
    def __init__(self, Goal):
        super(WaterJarPuzzle, self).__init__(Goal)

    def Heuristic(self, Node):
        return 0

    def GetResult(self, Node):
        Result = []
        while Node.Parent:
            Result.insert(0, Node.Comment)
            Node = Node.Parent
        return Result


class WaterJarPuzzleNode(AStarNode):
    def __init__(self, Status, G, Parent):
        super(WaterJarPuzzleNode, self).__init__(Status, G, Parent)

    def PossibleNextNodes(self):
        result = []
        # empty first
        NewNode = WaterJarPuzzleNode((0, self.Status[1]), self.G + 1, self)
        NewNode.Comment = '10'
        result.append(NewNode)
        # empty second
        NewNode = WaterJarPuzzleNode((self.Status[0], 0), self.G + 1, self)
        NewNode.Comment = '20'
        result.append(NewNode)
        # fill first jar
        if self.Status[0] < gFirst:
            NewNode = WaterJarPuzzleNode((gFirst, self.Status[1]), self.G + 1, self)
            NewNode.Comment = '01'
            result.append(NewNode)
        # fill second jar
        if self.Status[1] < gSecond:
            NewNode = WaterJarPuzzleNode((self.Status[0], gSecond), self.G + 1, self)
            NewNode.Comment = '02'
            result.append(NewNode)
        # first -> second
        if self.Status[1] < gSecond:

            if (gSecond - self.Status[1]) >= self.Status[0]:
                NewNode = WaterJarPuzzleNode((0, sum(self.Status)), self.G + 1, self)
            else:
                NewNode = WaterJarPuzzleNode(
                    (self.Status[0] - (gSecond - self.Status[1]), gSecond),
                    self.G + 1,
                    self,
                )
            NewNode.Comment = '12'
            result.append(NewNode)
        # second -> first
        if self.Status[0] < gFirst:

            if (gFirst - self.Status[0]) >= self.Status[1]:
                NewNode = WaterJarPuzzleNode((sum(self.Status), 0), self.G + 1, self)
            else:
                NewNode = WaterJarPuzzleNode(
                    (gFirst, self.Status[1] - (gFirst - self.Status[0])),
                    self.G + 1,
                    self,
                )
            NewNode.Comment = '21'
            result.append(NewNode)
        return result


def checkio(first, second, goal):
    global gFirst, gSecond
    gFirst = first
    gSecond = second
    Puzzle = WaterJarPuzzle(lambda x, g=goal: g in x)
    startNode = WaterJarPuzzleNode((0, 0), 0, None)
    return Puzzle.Search(startNode)


if __name__ == '__main__':
    # This part is using only for self-checking and not necessary for
    # auto-testing
    def check_solution(func, initial_data, max_steps):

        first_volume, second_volume, goal = initial_data
        actions = {
            "01": lambda f, s: (first_volume, s),
            "02": lambda f, s: (f, second_volume),
            "12": lambda f, s: (
                f - (second_volume - s if f > second_volume - s else f),
                second_volume if f > second_volume - s else s + f,
            ),
            "21": lambda f, s: (
                first_volume if s > first_volume - f else s + f,
                s - (first_volume - f if s > first_volume - f else s),
            ),
            "10": lambda f, s: (0, s),
            "20": lambda f, s: (f, 0),
        }
        first, second = 0, 0
        result = func(*initial_data)
        if len(result) > max_steps:
            print("You answer contains too many steps. It can be shorter.")
            return False
        for act in result:
            if act not in actions.keys():
                print("I don't know this action {0}".format(act))
                return False
            first, second = actions[act](first, second)
        if goal == first or goal == second:
            return True
        print("You did not reach the goal.")
        return False

    assert check_solution(checkio, (5, 7, 6), 10), "Example"
    assert check_solution(checkio, (3, 4, 1), 2), "One and two"


1		gFirst = 0
2		gSecond = 0
3
4
5		class AStar(object):
6		def __init__(self, Goal):
7		self.Goal = Goal
8
9		def Heuristic(self, Node):
10		raise NotImplementedError
11
12		def GetResult(self, Node):
13		raise NotImplementedError
14
15		def Search(self, StartNode):
16		OpenSet = set()
17		ClosedSet = set()
18		StartNode.H = self.Heuristic(StartNode)
19		OpenSet.add(StartNode)
20		while OpenSet:
21		Current = min(OpenSet, key=lambda o: o.G + o.H)
22		if self.Goal(Current.Status):
23		return self.GetResult(Current)
24		OpenSet.remove(Current)
25		ClosedSet.add(Current)
26		for Node in Current.PossibleNextNodes():
27		if Node.Status in [i.Status for i in ClosedSet]:
28		continue
29		if Node.Status in [i.Status for i in OpenSet]:
30		index = [i.Status for i in OpenSet].index(Node.Status)
31		if Node.G < list(OpenSet)[index].G:
32		list(OpenSet)[index].G = Node.G
33		list(OpenSet)[index].Parent = Node.Parent
34		else:
35		Node.H = self.Heuristic(Node)
36		if Node.SelfCheck:
37		OpenSet.add(Node)
38		return None
39
40
41		class AStarNode(object):
42		def __init__(self, Status, G, Parent):
43		self.G = G
44		self.H = None
45		self.Parent = Parent
46		self.Status = Status
47		self.Comment = None
48
49		def SelfCheck(self):
50		if self.G and self.H and self.Status:
51		return True
52		else:
53		print(self.G)
54		print(self.H)
55		print(self.Parent)
56		print(self.Status)
57		print(self.Comment)
58		assert 1 == 0
59
60		def PossibleNextNodes(self):
61		raise NotImplementedError
62
63
64		class WaterJarPuzzle(AStar):
65		def __init__(self, Goal):
66		super(WaterJarPuzzle, self).__init__(Goal)
67
68		def Heuristic(self, Node):
69		return 0
70
71		def GetResult(self, Node):
72		Result = []
73		while Node.Parent:
74		Result.insert(0, Node.Comment)
75		Node = Node.Parent
76		return Result
77
78
79		class WaterJarPuzzleNode(AStarNode):
80		def __init__(self, Status, G, Parent):
81		super(WaterJarPuzzleNode, self).__init__(Status, G, Parent)
82
83		def PossibleNextNodes(self):
84		result = []
85		# empty first
86		NewNode = WaterJarPuzzleNode((0, self.Status[1]), self.G + 1, self)
87		NewNode.Comment = '10'
88		result.append(NewNode)
89		# empty second
90		NewNode = WaterJarPuzzleNode((self.Status[0], 0), self.G + 1, self)
91		NewNode.Comment = '20'
92		result.append(NewNode)
93		# fill first jar
94		if self.Status[0] < gFirst:
95		NewNode = WaterJarPuzzleNode((gFirst, self.Status[1]), self.G + 1, self)
96		NewNode.Comment = '01'
97		result.append(NewNode)
98		# fill second jar
99		if self.Status[1] < gSecond:
100		NewNode = WaterJarPuzzleNode((self.Status[0], gSecond), self.G + 1, self)
101		NewNode.Comment = '02'
102		result.append(NewNode)
103		# first -> second
104	View Code Duplication	if self.Status[1] < gSecond:
		0 ignored issues – show Duplication introduced 2019-02-08 12:03 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
105		if (gSecond - self.Status[1]) >= self.Status[0]:
106		NewNode = WaterJarPuzzleNode((0, sum(self.Status)), self.G + 1, self)
107		else:
108		NewNode = WaterJarPuzzleNode(
109		(self.Status[0] - (gSecond - self.Status[1]), gSecond),
110		self.G + 1,
111		self,
112		)
113		NewNode.Comment = '12'
114		result.append(NewNode)
115		# second -> first
116	View Code Duplication	if self.Status[0] < gFirst:
		0 ignored issues – show Duplication introduced 2019-02-08 12:03 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
117		if (gFirst - self.Status[0]) >= self.Status[1]:
118		NewNode = WaterJarPuzzleNode((sum(self.Status), 0), self.G + 1, self)
119		else:
120		NewNode = WaterJarPuzzleNode(
121		(gFirst, self.Status[1] - (gFirst - self.Status[0])),
122		self.G + 1,
123		self,
124		)
125		NewNode.Comment = '21'
126		result.append(NewNode)
127		return result
128
129
130		def checkio(first, second, goal):
131		global gFirst, gSecond
132		gFirst = first
133		gSecond = second
134		Puzzle = WaterJarPuzzle(lambda x, g=goal: g in x)
135		startNode = WaterJarPuzzleNode((0, 0), 0, None)
136		return Puzzle.Search(startNode)
137
138
139		if __name__ == '__main__':
140		# This part is using only for self-checking and not necessary for
141		# auto-testing
142	View Code Duplication	def check_solution(func, initial_data, max_steps):
		0 ignored issues – show Duplication introduced 2019-02-08 09:44 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
143		first_volume, second_volume, goal = initial_data
144		actions = {
145		"01": lambda f, s: (first_volume, s),
146		"02": lambda f, s: (f, second_volume),
147		"12": lambda f, s: (
148		f - (second_volume - s if f > second_volume - s else f),
149		second_volume if f > second_volume - s else s + f,
150		),
151		"21": lambda f, s: (
152		first_volume if s > first_volume - f else s + f,
153		s - (first_volume - f if s > first_volume - f else s),
154		),
155		"10": lambda f, s: (0, s),
156		"20": lambda f, s: (f, 0),
157		}
158		first, second = 0, 0
159		result = func(*initial_data)
160		if len(result) > max_steps:
161		print("You answer contains too many steps. It can be shorter.")
162		return False
163		for act in result:
164		if act not in actions.keys():
165		print("I don't know this action {0}".format(act))
166		return False
167		first, second = actions[act](first, second)
168		if goal == first or goal == second:
169		return True
170		print("You did not reach the goal.")
171		return False
172
173		assert check_solution(checkio, (5, 7, 6), 10), "Example"
174		assert check_solution(checkio, (3, 4, 1), 2), "One and two"
175

KenMercusLai / checkio

water_jars.AStar.GetResult() A last analyzed 2022-05-11 09:02 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

water_jars.AStar.GetResult() A
last analyzed 2022-05-11 09:02 UTC