sobota, stycznia 09, 2016

2016 będzie rokiem "nietypowym"

W odróżnieniu do swoich sąsiadów nie pozwala na stworzenie równania:
10_9_8_7_6_5_4_3_2_1=2016
Za to już taki rok poprzedni, pozwala na powstanie równania:
10*9*8*7/6/5*4*3-2+1=2015
Także, kolejny rok na to pozwoli:
10*9*8*7/6/5*4*3+2-1=2017

Okazuje się, że od 1970 roku do 2100 będzie łącznie 12 lat, które pozwolą na zapisanie się równaniami (takimi na liczbach całkowitych).

Oto one:
10*9*8+7*6*5*4*3/2-1=1979
10*9*8+7*6*5*4*3/2*1=1980
10*9*8+7*6*5*4*3/2+1=1981
10*9*8*7/6/5*4*3-2-1=2013
10*9*8*7/6/5*4*3-2*1=2014
10*9*8*7/6/5*4*3-2+1=2015
10*9*8*7/6/5*4*3+2-1=2017
10*9*8*7/6/5*4*3+2*1=2018
10*9*8*7/6/5*4*3+2+1=2019
10*9*8/7/6*5*4*3*2-1=2039
10*9*8/7/6*5*4*3*2*1=2040
10*9*8/7/6*5*4*3*2+1=2041

2016 jest tutaj jeszcze o tyle nietypowy, że jest jedynym rokiem w tym okresie, który jest otoczony z obu stron blokami lat równaniowalnych ;-)

A skąd to wiem?
Bo policzyłem* tym oto programikiem w Scala'i ;-)

package pl.przemelek.equation

import scala.annotation.tailrec

object ResolveFor2016 {

  def increase(operators: Array[Int]) {
    @tailrec    
    def inc(idx:Int, operators:Array[Int]) {
      operators(idx)=operators(idx)+1      if (operators(idx) > 3) {
        operators(idx) = 0        inc(idx + 1, operators)
      }
    }
    inc(0,operators)
  }

  def testFor(year:Int,operators: Array[Int]): Boolean = {
    val numbers = Array(10,9,8,7,6,5,4,3,2,1)

    def mul(list:List[Int]):List[Int] = list match {
      case h :: Nil => h::Nil      
      case a :: 2 :: b :: tail => mul((a*b)::tail)
      case a :: 3 :: b :: tail => mul((a/b)::tail)
      case a :: 0 :: b :: tail => a::0::mul(b::tail)
      case a :: 1 :: b :: tail => a::1::mul(b::tail)
    }

    @tailrec
    def sum(list:List[Int]):Int = list match {
      case a :: Nil => a
      case a :: 0 :: b :: tail => sum(a+b::tail)
      case a :: 1 :: b :: tail => sum(a-b::tail)
    }

    var list = List[Int]()
    for (i <- 0 to 18) {
      list=list++List(if (i%2==1) operators(i/2) else numbers(i/2))
    }
    list = mul(list)
    val s = sum(list)
    s==year
  }

  def check(year:Int) {
    def show(operators:Array[Int]): Unit = {
      val numbers = Array(10,9,8,7,6,5,4,3,2,1)
      val opers = "+,-,*,/".split(",")
      for (i <- 0 to 18) {
        print(if (i%2==1) opers(operators(i/2)) else numbers(i/2))
      }
    }
    val operators = Array.fill(10){0};

    var finish = false;

    while (!finish && operators(9)==0) {
      finish = testFor(year,operators)
      if (finish) {
        show(operators)
        println("="+year)
      }
      increase(operators)
    }
  }

  def main(args: Array[String]) {
    // 10 _ 9 _ 8 _ 7 _ 6 _ 5 _ 4 _ 3 _ 2 _ 1 = 2016    
    for (year <- 1970 to 2100) {
      check(year)
    }
  }
}

Całkiem miła zabawka na "po chorobie" ;-)
Pozwoliła mi na przetestowanie pewnych mechanizmów ze Scala'i.

Ten program nie jest napisany po bożemu, bo używam var'ów i side-efectów, nie wszędzie robię tail recursion, ale już coś robi.
Chętnie przyjmę krytykę :-)

Podoba mi się możliwość zrobienia takich strasznych rzeczy jak to co robią mul i sum z pattern matchingiem.

Program też poważny problem algorytmiczny ;-) bo zamiast w testFor sprawdzać wszystkie lata od razu, dla każdego układu operatorów, to ja sprawdzam każdy układ operatorów dla każdego roku. Głównie przez to, że najpierw sprawdzałem czy da się takie równanie zbudować dla 2016, a później zaciekawiły mnie lata w około ;-)

Chytrze uniknąłem zabawy w budowanie drzewa przez ohydny manewr z budowaniem równania jako listy.... 

Scala to nadal nie jest mój język, ale nauczę się go, bo wroga trzeba poznać ;-)

Inspiracją do całego programu był tytuł postu Petera Norviga.


* - komputer policzył.



Podobne postybeta
Potworność ;-) czyli mnożenie w 90 liniach ;-)
Motanie kodu - czyli co wynika z chęci zarządzania zadaniami
Plus dla Scala, minus dla Groovy ;-)
SleepAdvisor - komórka pomaga w wyspaniu się ;-)
Go dla Java'owca ;-) odcinek 2 "kontenery dwa ;-)"