Python program for Domino Solitaire














































Python program for Domino Solitaire




                   Python program for  Domino Solitaired




Description:

In Domino Solitaire, you have a grid with two rows and many columns. Each square in the grid contains an integer. You are given a supply of rectangular 2 1 tiles, each of which exactly covers two adjacent squares of the grid. You have to place tiles to cover all the squares in the grid such that each tile covers two squares and no pair of tiles overlap.

The score for a tile is the difference between the bigger and the smaller number that are covered by the tile. The aim of the game is to maximize the sum of the scores of all the tiles.

Here is an example of a grid, along with two different tilings and their scores.



The score for Tiling 1 is 12 = (9%u22128)+(6%u22122)+(7%u22121)+(3%u22122) while the score for Tiling 2 is 6 = (8%u22126)+(9%u22127)+(3%u22122)+(2%u22121). There are other tilings possible for this grid, but you can check that Tiling 1 has the maximum score among all tilings.

Your task is to read the grid of numbers and compute the maximum score that can be achieved by any tiling of the grid.

Solution hint

Recursively find the best tiling, from left to right. You can start the tiling with one vertical tile or two horizontal tiles. Use dynamic programming to evaluate the recursive expression efficiently.

Input format

The first line contains one integer N, the number of columns in the grid. This is followed by 2 lines describing the grid. Each of these lines consists of N integers, separated by blanks.

Output format

A single integer indicating the maximum score that can be achieved by any tiling of the given grid






Source Code:




def solve(l1,l2):

    n = len(l1)

    

    if n == 0:

        return(0)


    ans = [0 for i in range(n+1)]

    

    ans[n-1] = max(l1[n-1],l2[n-1]) - min(l1[n-1],l2[n-1])


    for i in range(n-2,-1,-1):

        vert = max(l1[i],l2[i]) - min(l1[i],l2[i]) + ans[i+1]

        horz = max(l1[i],l1[i+1]) - min(l1[i],l1[i+1]) + max(l2[i],l2[i+1]) - min(l2[i],l2[i+1]) + ans[i+2]

        ans[i] = max(vert,horz)


    return(ans[0])


nstr = input()

# Value of n not needed in Python

#  n = int(nstr.strip())


# Read and parse first row of numbers

line1str = input().strip()

line1strlist = line1str.split()

line1 = []

for s in line1strlist:

    line1.append(int(s))


# Read and parse second row of numbers

line2str = input().strip()

line2strlist = line2str.split()

line2 = []

for s in line2strlist:

    line2.append(int(s))


print(solve(line1,line2))



Output:


4
8 6 2 3
9 7 1 2
12





Output Screens:



4
8 6 2 3
9 7 1 2


More Articles of Bhanu Prakash Reddy M:

Name Views Likes
Python Geolocation with GeoIP2 1190 61
Python Geoip2 Modules 1237 34
Python Geoip Enriching MMDB files 1088 16
Python Geoip2 Configuring geolocation 1160 24
Python Random Module 1039 22
Python GeoIP2 Precision Services 1065 24
GeoIP - MaxMind GeoIP2 API 1566 21
Python Generate secure random numbers 1055 41
Python - Generic output formatting 716 11
Python - Prims minimum spanning tree 807 22
Python Program for Choosing Balls 1367 17
Python - Dijkstras shortest path algorithm 1452 24
Python Cryptographic Secure hashes and message digests 1168 65
Python program for Smallest Palindrome 1822 13
Python program for Friends on Facebook 1253 21
Python Cryptographic Generating tokens 975 13
Python - Cookies in CGI 1608 23
Python - Stream Encoding and Decoding 999 16
Python program for frequency is a function that takes as input a list of integers and returns a pair of the form (minfreqlist,maxfreqlist) 1682 42
Python - Stateless Encoding and Decoding in Binary data service 821 22
Python Binary Data Services 789 92
Python CGI Environment Variables 864 20
Python GeoIP2 JavaScript Client API 1103 33
Python - CGI Programming 629 39
Python program for panagram 1364 30
Plotting Series in Python 1273 24
GeoIP in PYTHON 1358 23
Python Concrete exceptions 1140 12
Python Geoip Maxmind 1206 34
Python Random module --2 939 18
Python-- Programs 1176 14
Python Types of Anonymous IPs and How They Affect Your Business 1049 19
Python Cryptographic Introduction 991 11
Geoip-IP geolocation information in Python. 1241 15
Python Geoip Database Reader Exceptions 1185 30
Python Data Changes to GeoIP Legacy 972 10
Python - Binary Data Services - 2 721 33
Python Program for Rotate Matrix Elements 1141 11
Python Program post-order traversal of a tree without using recursion 902 22
Python Program In-order traversal of a tree without using recursion 1151 28
Python MaxMind GeoIP2 1312 33
Python The Easy Way to Use MaxMind GeoIP 1546 25
Python Program 1277 20
Python GeoIP2 Databases with HAProxy Enterprise 1053 25
Python The Knights tour problem 1790 47
Python User-defined Exceptions 897 57
Python Program pre-order traversal of a tree without using recursion 1019 29
Python - Standard Encodings in Binary Data service 753 29
Python Binary Data Service Error Handlers 696 51
Python program for Domino Solitaire 2005 22
Python Built-in Exceptions 938 13
CGI Programming-2 860 49
GeoIP -- Flask. 1368 15
Python IP Geolocation 1018 13
Python Concrete exceptions part-2 1329 28

Comments