Led Clock State Change
The Problem and the Data
Suppose you have an old display for a digital clock. Out of pure curiosity, you wonder as the clock cycles through its display, how many times LEDs need to have their states changed. To see a display, you might look at the digital clock that you found in your basement or at the font given on the following web page:
https://www.dafont.com/ds-digital.font
You will need to write a java assignment scripts to determine answers to several questions about the number of state changes that happen in LEDs in a single digit of a clock display through a display cycle.
Think of the font as specifying an edge-weighted graph where the vertices of the graph are the digits 0 through 9 and the edge weights are the number of different LEDs between the two digits connected by the edge. Then, construct an adjacency matrix for that graph and also a few smaller adjacency matrixes for testing purposes (so that you can work out answers by hand to give yourself confidence that the answers your program generates are correct).
Stage D: Evaluating the Cost of a Counting Cycle
Decide on the font that you will use. Define the adjacency matrix for the graph corresponding to the font you’ve chosen as a constant in your code.
Write a function that takes as parameters and adjacency matrix and a path (where a path is a list of vertices which will be just numbered in this case) and returns the length (or cost) of that path.
Call your function on the path [0,1,2,3,4,5,6,7,8,9,0]. Note that this path is one complete cycle counting the way we normally count. Verify that you get the same result if you used a different starting and ending point by calling your function on the path [9,0,1,2,3,4,5,6,7,8,9].
Stage C: Best and Worst Cycles
Now suppose that out of pure curiosity, you wonder about the cost if you re-arranged the order of the symbols (so that they werent just 0,1,2,3,4,5,6,7,8,9), what the “cost” would be. Write a function that determines (and prints) the lowest and the highest costs for all of the possible rearrangements of the symbols.
Note that if you use 9 as your starting and ending point in a path (which is fine since when thinking about a cycle, any starting point will do) then you can generate all of the cycles by generating permutations of nine digits between 0 and 8 inclusive as lists and prepending and appending 9 to said lists.
Stage B: Counting Cycles of Each Cost
Again, suppose your curiosity overflows and you want to know how many cycles there are with each of the possible costs of cycles. Since you now know the costs of the best and worst cycle, you can write a function that counts how many cycles of each cost between the best and worst cost (inclusive) there are. Do so and have it display a table of these costs.
Solution:
import random,sys,csv
sys.setrecursionlimit(1000000)
D=[[0,4,3,3,4,3,2,3,1,2],
[4,0,6,3,2,5,6,1,5,4],
[3,6,0,2,6,4,3,4,2,3],
[3,3,2,0,3,4,3,2,2,1],
[4,2,6,3,0,3,4,3,3,2],
[3,5,4,4,3,0,1,4,2,1],
[3,1,4,2,3,4,0,5,1,2],
[3,1,4,2,3,4,5,0,4,3],
[1,5,2,2,3,2,1,4,0,1],
[2,4,3,1,2,1,2,3,1,0]]
def cost(path,D):
ans=0
if len(path)==0:
return 0
for i in range(len(path)-1):
ans+=D[path[i]][path[i+1]]
return ans
BEST=[]
def permutations(L,ans=[],visited=[False for _ in range(10)]):
if all(visited):
L.append(list(ans))
else:
for i in range(10):
if not visited[i]:
ans.append(i)
visited[i]=True
permutations(L,ans,visited)
visited[i]=False
ans.pop()
def best(D):
L=list()
permutations(L)
return min([(cost(l,D),list(l)) for l in L])
def worst(D):
L=list()
permutations(L)
return max([(cost(l,D),list(l)) for l in L])
def count(D):
L=list()
permutations(L)
cos=dict()
for l in L:
c=cost(l,D)
if cos.get(c) == None:
cos[c]=1
else:
cos[c]+=1
for i,j in sorted(cos.items()):
print(i,j)
def tocsv(D):
L=list()
permutations(L)
cos=dict()
for l in L:
c=cost(l,D)
if cos.get(c) == None:
cos[c]=1
else:
cos[c]+=1
with open('output.csv','w') as file:
writer=csv.writer(file, delimiter=';',quotechar='|', quoting=csv.QUOTE_MINIMAL)
writer.writerows(sorted(cos.items()))