1 people like it.

Brute Force Solutions to Viral Math Problem From Vietnam

Solution to Viral Math Problem From Vietnam explained on: http://mindyourdecisions.com/blog/2015/05/20/viral-math-problem-from-vietnam-are-you-smarter-than-an-8-year-old/#.VXhmhs-eDRY

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 

    open System

    let isFractional n =
        n <> (Decimal.Truncate n)

    let correct n =
        //round after 20th digit after decimal point to fix propagation of floating point errors
        Decimal.Round(n, 20) 

    let resultAndWhetherItHasFractionalSubResults (n : list<decimal>) = 
        let result = n.[0] + 13M * n.[1] / n.[2] + n.[3] + 12M * n.[4]  - n.[5] - 11M + n.[6] * n.[7] / n.[8] - 10M
        let hasFractionalSubResults = isFractional (correct(n.[1] / n.[2])) || isFractional (correct(n.[7] / n.[8]))
        (correct result, hasFractionalSubResults) //return tuple
        
    let ``1st solution in blog post`` = resultAndWhetherItHasFractionalSubResults ([1; 2; 6; 4; 7; 8; 3; 5; 9]  |> List.map (fun n -> n |> decimal))

    // source: http://stackoverflow.com/questions/286427/calculating-permutations-in-f
    let rec permute list taken = 
      seq { 
        if Set.count taken = List.length list 
            then yield List.empty 
        else
            for element in list do
              if not (Set.contains element taken) then 
                for permutation in permute list (Set.add element taken)  do
                  yield element::permutation 
        } |> List.ofSeq
    
    //returns solutions as tuple in the form of ((input, (result, hasFractionalSubResults))
    let solutions allowFractionalSubResults= 
        let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9] |> List.map (fun n -> n |> decimal)
        permute numbers Set.empty 
        |> List.map (fun input -> (input, resultAndWhetherItHasFractionalSubResults input)) 
        |> List.filter (fun (input, (result, hasFractionalSubResults)) -> result = 66M && (allowFractionalSubResults || (not hasFractionalSubResults)))


    let ``solutions WITH fractional sub-results`` = solutions  true
    let ``number of solutions WITH fractional sub-results`` = ``solutions WITH fractional sub-results`` |> List.length

    let ``solutions WITHOUT fractional sub-results`` = solutions  false
    let ``number of solutions WITHOUT fractional sub-results`` = ``solutions WITHOUT fractional sub-results`` |> List.length

OUTPUT*

...

val ( 1st solution in blog post ) : decimal * bool = (66.00000000000000000000M, true)

...

val ( solutions WITH fractional sub-results ) : (decimal list (decimal bool)) list = [([1M; 2M; 6M; 4M; 7M; 8M; 3M; 5M; 9M], (66.00000000000000000000M, true)); ([1M; 2M; 6M; 4M; 7M; 8M; 5M; 3M; 9M], (66.00000000000000000000M, true)); ([1M; 3M; 2M; 4M; 5M; 8M; 7M; 9M; 6M], (66.0M, true)); ([1M; 3M; 2M; 4M; 5M; 8M; 9M; 7M; 6M], (66.0M, true)); ([1M; 3M; 2M; 9M; 5M; 6M; 4M; 7M; 8M], (66.0M, true)); ([1M; 3M; 2M; 9M; 5M; 6M; 7M; 4M; 8M], (66.0M, true)); ([1M; 3M; 4M; 7M; 6M; 5M; 2M; 9M; 8M], (66.00M, true)); ([1M; 3M; 4M; 7M; 6M; 5M; 9M; 2M; 8M], (66.00M, true)); ([1M; 3M; 6M; 2M; 7M; 9M; 4M; 5M; 8M], (66.0M, true)); ([1M; 3M; 6M; 2M; 7M; 9M; 5M; 4M; 8M], (66.0M, true)); ([1M; 3M; 9M; 4M; 7M; 8M; 2M; 5M; 6M], (66.00000000000000000000M, true)); ([1M; 3M; 9M; 4M; 7M; 8M; 5M; 2M; 6M], (66.00000000000000000000M, true)); ([1M; 4M; 8M; 2M; 7M; 9M; 3M; 5M; 6M], (66.0M, true)); ([1M; 4M; 8M; 2M; 7M; 9M; 5M; 3M; 6M], (66.0M, true)); ([1M; 5M; 2M; 3M; 4M; 8M; 7M; 9M; 6M], (66.0M, true)); ([1M; 5M; 2M; 3M; 4M; 8M; 9M; 7M; 6M], (66.0M, true)); ([1M; 5M; 2M; 8M; 4M; 7M; 3M; 9M; 6M], (66.0M, true)); ([1M; 5M; 2M; 8M; 4M; 7M; 9M; 3M; 6M], (66.0M, true)); ([1M; 5M; 3M; 9M; 4M; 2M; 7M; 8M; 6M], (66.00000000000000000000M, true)); ([1M; 5M; 3M; 9M; 4M; 2M; 8M; 7M; 6M], (66.00000000000000000000M, true)); ([1M; 8M; 3M; 7M; 4M; 5M; 2M; 6M; 9M], (66.00000000000000000000M, true)); ([1M; 8M; 3M; 7M; 4M; 5M; 6M; 2M; 9M], (66.00000000000000000000M, true)); ([1M; 9M; 6M; 4M; 5M; 8M; 3M; 7M; 2M], (66.0M, true)); ([1M; 9M; 6M; 4M; 5M; 8M; 7M; 3M; 2M], (66.0M, true)); ([1M; 9M; 6M; 7M; 5M; 2M; 3M; 4M; 8M], (66.0M, true)); ([1M; 9M; 6M; 7M; 5M; 2M; 4M; 3M; 8M], (66.0M, true)); ([2M; 1M; 4M; 3M; 7M; 9M; 5M; 6M; 8M], (66.00M, true)); ([2M; 1M; 4M; 3M; 7M; 9M; 6M; 5M; 8M], (66.00M, true)); ([2M; 3M; 6M; 1M; 7M; 9M; 4M; 5M; 8M], (66.0M, true)); ([2M; 3M; 6M; 1M; 7M; 9M; 5M; 4M; 8M], (66.0M, true)); ([2M; 4M; 8M; 1M; 7M; 9M; 3M; 5M; 6M], (66.0M, true)); ([2M; 4M; 8M; 1M; 7M; 9M; 5M; 3M; 6M], (66.0M, true)); ([2M; 6M; 9M; 8M; 5M; 1M; 4M; 7M; 3M], (66.00000000000000000000M, true)); ([2M; 6M; 9M; 8M; 5M; 1M; 7M; 4M; 3M], (66.00000000000000000000M, true)); ([2M; 8M; 6M; 9M; 4M; 1M; 5M; 7M; 3M], (66.00000000000000000000M, true)); ([2M; 8M; 6M; 9M; 4M; 1M; 7M; 5M; 3M], (66.00000000000000000000M, true)); ([2M; 9M; 6M; 3M; 5M; 1M; 4M; 7M; 8M], (66.0M, true)); ([2M; 9M; 6M; 3M; 5M; 1M; 7M; 4M; 8M], (66.0M, true)); ([3M; 1M; 4M; 2M; 7M; 9M; 5M; 6M; 8M], (66.00M, true)); ([3M; 1M; 4M; 2M; 7M; 9M; 6M; 5M; 8M], (66.00M, true)); ([3M; 2M; 1M; 5M; 4M; 7M; 8M; 9M; 6M], (66M, true)); ([3M; 2M; 1M; 5M; 4M; 7M; 9M; 8M; 6M], (66M, true)); ([3M; 2M; 4M; 8M; 5M; 1M; 7M; 9M; 6M], (66.0M, true)); ([3M; 2M; 4M; 8M; 5M; 1M; 9M; 7M; 6M], (66.0M, true)); ([3M; 2M; 8M; 6M; 5M; 1M; 7M; 9M; 4M], (66.00M, true)); ([3M; 2M; 8M; 6M; 5M; 1M; 9M; 7M; 4M], (66.00M, true)); ([3M; 5M; 2M; 1M; 4M; 8M; 7M; 9M; 6M], (66.0M, true)); ([3M; 5M; 2M; 1M; 4M; 8M; 9M; 7M; 6M], (66.0M, true)); ([3M; 6M; 4M; 9M; 5M; 8M; 1M; 7M; 2M], (66.0M, true)); ([3M; 6M; 4M; 9M; 5M; 8M; 7M; 1M; 2M], (66.0M, true)); ([3M; 9M; 2M; 8M; 1M; 5M; 6M; 7M; 4M], (66.0M, true)); ([3M; 9M; 2M; 8M; 1M; 5M; 7M; 6M; 4M], (66.0M, true)); ([3M; 9M; 6M; 2M; 5M; 1M; 4M; 7M; 8M], (66.0M, true)); ([3M; 9M; 6M; 2M; 5M; 1M; 7M; 4M; 8M], (66.0M, true)); ([4M; 2M; 6M; 1M; 7M; 8M; 3M; 5M; 9M], (66.00000000000000000000M, true)); ([4M; 2M; 6M; 1M; 7M; 8M; 5M; 3M; 9M], (66.00000000000000000000M, true)); ([4M; 3M; 2M; 1M; 5M; 8M; 7M; 9M; 6M], (66.0M, true)); ([4M; 3M; 2M; 1M; 5M; 8M; 9M; 7M; 6M], (66.0M, true)); ([4M; 3M; 9M; 1M; 7M; 8M; 2M; 5M; 6M], (66.00000000000000000000M, true)); ([4M; 3M; 9M; 1M; 7M; 8M; 5M; 2M; 6M], (66.00000000000000000000M, true)); ([4M; 9M; 6M; 1M; 5M; 8M; 3M; 7M; 2M], (66.0M, true)); ([4M; 9M; 6M; 1M; 5M; 8M; 7M; 3M; 2M], (66.0M, true)); ([5M; 1M; 2M; 9M; 6M; 7M; 3M; 4M; 8M], (66.0M, true)); ([5M; 1M; 2M; 9M; 6M; 7M; 4M; 3M; 8M], (66.0M, true)); ([5M; 2M; 1M; 3M; 4M; 7M; 8M; 9M; 6M], (66M, true)); ([5M; 2M; 1M; 3M; 4M; 7M; 9M; 8M; 6M], (66M, true)); ([5M; 3M; 1M; 7M; 2M; 6M; 8M; 9M; 4M], (66M, true)); ([5M; 3M; 1M; 7M; 2M; 6M; 9M; 8M; 4M], (66M, false)); ([5M; 4M; 1M; 9M; 2M; 7M; 3M; 8M; 6M], (66M, true)); ([5M; 4M; 1M; 9M; 2M; 7M; 8M; 3M; 6M], (66M, true)); ([5M; 4M; 8M; 9M; 6M; 7M; 1M; 3M; 2M], (66.0M, true)); ([5M; 4M; 8M; 9M; 6M; 7M; 3M; 1M; 2M], (66.0M, true)); ([5M; 7M; 2M; 8M; 3M; 9M; 1M; 6M; 4M], (66.0M, true)); ([5M; 7M; 2M; 8M; 3M; 9M; 6M; 1M; 4M], (66.0M, true)); ([5M; 9M; 3M; 6M; 2M; 1M; 7M; 8M; 4M], (66M, false)); ([5M; 9M; 3M; 6M; 2M; 1M; 8M; 7M; 4M], (66M, true)); ([6M; 2M; 8M; 3M; 5M; 1M; 7M; 9M; 4M], (66.00M, true)); ([6M; 2M; 8M; 3M; 5M; 1M; 9M; 7M; 4M], (66.00M, true)); ([6M; 3M; 1M; 9M; 2M; 5M; 7M; 8M; 4M], (66M, false)); ([6M; 3M; 1M; 9M; 2M; 5M; 8M; 7M; 4M], (66M, true)); ([6M; 9M; 3M; 5M; 2M; 1M; 7M; 8M; 4M], (66M, false)); ([6M; 9M; 3M; 5M; 2M; 1M; 8M; 7M; 4M], (66M, true)); ([7M; 1M; 4M; 9M; 6M; 5M; 2M; 3M; 8M], (66.00M, true)); ([7M; 1M; 4M; 9M; 6M; 5M; 3M; 2M; 8M], (66.00M, true)); ([7M; 2M; 8M; 9M; 6M; 5M; 1M; 3M; 4M], (66.00M, true)); ([7M; 2M; 8M; 9M; 6M; 5M; 3M; 1M; 4M], (66.00M, true)); ([7M; 3M; 1M; 5M; 2M; 6M; 8M; 9M; 4M], (66M, true)); ([7M; 3M; 1M; 5M; 2M; 6M; 9M; 8M; 4M], (66M, false)); ([7M; 3M; 2M; 8M; 5M; 9M; 1M; 6M; 4M], (66.0M, true)); ([7M; 3M; 2M; 8M; 5M; 9M; 6M; 1M; 4M], (66.0M, true)); ([7M; 3M; 4M; 1M; 6M; 5M; 2M; 9M; 8M], (66.00M, ...)); ...] val ( number of solutions WITH fractional sub-results ) : int = 136 val ( solutions WITHOUT fractional sub-results ) : (decimal list (decimal bool)) list = [([5M; 3M; 1M; 7M; 2M; 6M; 9M; 8M; 4M], (66M, false)); ([5M; 9M; 3M; 6M; 2M; 1M; 7M; 8M; 4M], (66M, false)); ([6M; 3M; 1M; 9M; 2M; 5M; 7M; 8M; 4M], (66M, false)); ([6M; 9M; 3M; 5M; 2M; 1M; 7M; 8M; 4M], (66M, false)); ([7M; 3M; 1M; 5M; 2M; 6M; 9M; 8M; 4M], (66M, false)); ([9M; 3M; 1M; 6M; 2M; 5M; 7M; 8M; 4M], (66M, false))] val ( number of solutions WITHOUT fractional sub-results ) : int = 6 end

namespace System
val isFractional : n:decimal -> bool

Full name: Script.isFractional
val n : decimal
Multiple items
type Decimal =
  struct
    new : value:int -> decimal + 7 overloads
    member CompareTo : value:obj -> int + 1 overload
    member Equals : value:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 3 overloads
    static val Zero : decimal
    static val One : decimal
    static val MinusOne : decimal
    static val MaxValue : decimal
    ...
  end

Full name: System.Decimal

--------------------
Decimal()
Decimal(value: int) : unit
Decimal(value: uint32) : unit
Decimal(value: int64) : unit
Decimal(value: uint64) : unit
Decimal(value: float32) : unit
Decimal(value: float) : unit
Decimal(bits: int []) : unit
Decimal(lo: int, mid: int, hi: int, isNegative: bool, scale: byte) : unit
Decimal.Truncate(d: decimal) : decimal
val correct : n:decimal -> decimal

Full name: Script.correct
Decimal.Round(d: decimal) : decimal
Decimal.Round(d: decimal, mode: MidpointRounding) : decimal
Decimal.Round(d: decimal, decimals: int) : decimal
Decimal.Round(d: decimal, decimals: int, mode: MidpointRounding) : decimal
val resultAndWhetherItHasFractionalSubResults : n:decimal list -> decimal * bool

Full name: Script.resultAndWhetherItHasFractionalSubResults
val n : decimal list
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
Multiple items
val decimal : value:'T -> decimal (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.decimal

--------------------
type decimal = Decimal

Full name: Microsoft.FSharp.Core.decimal

--------------------
type decimal<'Measure> = decimal

Full name: Microsoft.FSharp.Core.decimal<_>
val result : decimal
val hasFractionalSubResults : bool
val ( 1st solution in blog post ) : decimal * bool

Full name: Script.( 1st solution in blog post )
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val n : int
val permute : list:'a list -> taken:Set<'a> -> 'a list list (requires comparison)

Full name: Script.permute
Multiple items
val list : 'a list (requires comparison)

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val taken : Set<'a> (requires comparison)
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
  interface IComparable
  interface IEnumerable
  interface IEnumerable<'T>
  interface ICollection<'T>
  new : elements:seq<'T> -> Set<'T>
  member Add : value:'T -> Set<'T>
  member Contains : value:'T -> bool
  override Equals : obj -> bool
  member IsProperSubsetOf : otherSet:Set<'T> -> bool
  member IsProperSupersetOf : otherSet:Set<'T> -> bool
  ...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>
val count : set:Set<'T> -> int (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.count
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val empty<'T> : 'T list

Full name: Microsoft.FSharp.Collections.List.empty
val element : 'a (requires comparison)
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val contains : element:'T -> set:Set<'T> -> bool (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.contains
val permutation : 'a list (requires comparison)
val add : value:'T -> set:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.add
val ofSeq : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
val solutions : allowFractionalSubResults:bool -> (decimal list * (decimal * bool)) list

Full name: Script.solutions
val allowFractionalSubResults : bool
val numbers : decimal list
val empty<'T (requires comparison)> : Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.empty
val input : decimal list
val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
val ( solutions WITH fractional sub-results ) : (decimal list * (decimal * bool)) list

Full name: Script.( solutions WITH fractional sub-results )
val ( number of solutions WITH fractional sub-results ) : int

Full name: Script.( number of solutions WITH fractional sub-results )
val ( solutions WITHOUT fractional sub-results ) : (decimal list * (decimal * bool)) list

Full name: Script.( solutions WITHOUT fractional sub-results )
val ( number of solutions WITHOUT fractional sub-results ) : int

Full name: Script.( number of solutions WITHOUT fractional sub-results )

More information

Link:http://fssnip.net/r9
Posted:9 years ago
Author:HK
Tags: f#

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.